Introduction

The protocol

Properties

Conclusion

An Homomorphic LWE based E-voting Scheme
I. Chillotti1

1

N. Gama1,22

M. Georgieva33

M. Izabachène44

PQCrypto 2016 - Fukuoka (Japan)

February 26, 2016

1 / 25

Introduction

The protocol

Properties

Conclusion

Table of contents

Introduction
The protocol
Properties
Conclusion

2 / 25

Introduction

The protocol

Properties

Conclusion

Table of contents

Introduction
The protocol
Properties
Conclusion

3 / 25

Introduction

The protocol

Properties

Conclusion

E-voting
Electronic Voting (E-voting): "would like to be" the electronic

analogue of the paper voting procedure.
Common properties:• Privacy• Veriability• Correctness

Examples in the litterature:• Mix-net based• Homomorphic based

Post Quantum scheme

4 / 25

Introduction

The protocolProperties

Conclusion

The playersv
Users/Voters
1. Can vote (after registration)
2. Can verify that their vote has
been cast and counted

Bulletin Board BB
1. Checks and adds the ballots
2. Performs public operations

Authority A1
1. Registration of the voters

Trustees T

1. Set up the decryption keys
2. Compute the final election
result5 / 25

IntroductionThe protocol

Properties

Conclusion

The structure of an E-voting scheme

Setup Phase

1) Set the parameters
2) Registration of voters

Voting Phase

1) Product and send ballots
2) Process the BB

Tallying Phase

1) Decrypt the result...and everyone can verify the result!

6 / 25

Introduction

The protocol

Properties

Conclusion

Table of contents

Introduction
The protocol
Properties
Conclusion

7 / 25

Introduction

The protocol

Properties

Conclusion

Helios: based on ElGamal
Helios relies on an additive homomorphic encryption scheme

El Gamal over a group hgi and secret sE(µ) := (g r , g µ g s·r ) for some large random r

ThenE(µ1 ) · E(µ2 ) = E(µ1 + µ2 )(Decryption is feasible if µ1 , µ2 are not too large)

8 / 25

Introduction

The protocol

Properties

Conclusion

Main idea
Cand 1

Cand 2

Cand 3

Voter 1

E(1),E(0),E(0)Voter 2

E(0),E(0),E(1)Voter 3

E(1),E(0),E(0)Voter 4

E(0),E(1),E(0)Voter 5E(1),E(0),E(0)vvvvv

9 / 25

Introduction

The protocol

Properties

Conclusion

Main idea
Cand 1

Cand 2

Cand 3

Voter 1E(1),E(0),E(0)Voter 2

E(0),E(0),E(1)Voter 3

E(1),E(0),E(0)Voter 4

E(0),E(1),E(0)Voter 5E(1),E(0),E(0)(Enc. Result)E(3),E(1),E(1)(Dec. Result)

3,

1,1v
v
v
v
v

9 / 25

Introduction

The protocol

Properties

Conclusion

Main idea
Cand 1

Prove that only registered
Cand
2 can
Cand
3 (once)
users
vote

E(1),E(0),E(0)E(0),
v ProveVoter
that 2ballots
havecorrect
Voter
3 shape E(1),v theE(0),E(1)vvv

Voter 1

Voter 4E(0),Voter 5E(1),

E(0),
E(0)
Prove thatE(0)the operations
E(1),are well performed
E(0),E(0)Prove that the final(Enc. Result)decryption
is correct

E(3),E(1),Ensure that the trustees(Dec.decryptResult)the sum,3,and not 1,
individual ballots

E(1)

1

etc...

9 / 25

Introduction

The protocol

Properties

Conclusion

How to vote?
Heliosv ∈ [0, ` − 1]
(00 , . . . , 0v−1 , 1v , 0v+1 , . . . , 0`−1 )(00 , . . . , 0v−1 , 100v , 0v+1 , . . . , 0`−1 )(10 , . . . , 0v−1 , 1v , 1v+1 , . . . , 0`−1 )Our protocolv ∈ [0, ` − 1] with ` = 2k
Decomposition of v in base 2 :(b0 , . . . , bk−1 )Bootstrapp(b0 , . . . , bk−1 )To ensure that theballot has this shape, aNIZK proof is needed!

Homomorphic (⊕, ∧)(00 , . . . , 0v−1 , 1v , 0v+1 , . . . , 0`−1 )

10 / 25

Introduction

The protocol

Properties

Conclusion

Overview of the scheme
Registration
Voter(b0 , . . . , bk−1 )publicper ballotBB(b0 , . . . , bk−1 )1) Initial bootstrap2) Homomorphic expansion
3) Final bootstrap(00 , . . . , 0v−1 , 1v , 0v+1 , . . . , 0`−1 )all ballots(r0 , r1 , . . . , r`−1 )+11 / 25

Introduction

The protocol

Properties

Conclusion

Candidate for Homomorphic Encryption
Fully Homomorphic Encryption+
Fast Bootstrapping

Solution:
LWE-based schemes + [DM15] bootstrapping• Final step: generalized version of [DM15]
1. Non binary messages

2. Lower noise amplitude

3 Post quantum: LWE (plus other PQ blocks)

12 / 25

Introduction

The protocol

Properties

Conclusion

LWE
LWE Symmetric Encryption

2/3

1/30
Example: M = {0, 1/3, 2/3} mod 1µ = 1/3 mod 1 ∈ M

13 / 25

Introduction

The protocol

Properties

Conclusion

LWE
LWE Symmetric Encryption

2/3

1/30( , ϕ)Example: M = {0, 1/3, 2/3} mod 1µ = 1/3 mod 1 ∈ M

LWE Encryption

1. Choose ϕ = µ + Gaussian Error

13 / 25

Introduction

The protocol

Properties

Conclusion

LWE
LWE Symmetric Encryption

2/3

1/3
a0(a, ϕ)Example: M = {0, 1/3, 2/3} mod 1µ = 1/3 mod 1 ∈ M

LWE Encryption

1. Choose ϕ = µ + Gaussian Error
2. Choose a random mask a ∈ Tn
13 / 25

Introduction

The protocol

Properties

Conclusion

LWE
LWE Symmetric Encryption

secret key: s ∈ {0, 1}n2/3

1/3
ab=a·s+ϕ0(a, ϕ)a(a, b)Example: M = {0, 1/3, 2/3} mod 1µ = 1/3 mod 1 ∈ M

LWE Encryption

1. Choose ϕ = µ + Gaussian Error
2. Choose a random mask a ∈ Tn
3. Return the locked representation (a, b)
13 / 25

Introduction

The protocol

Properties

Conclusion

LWE
LWE Symmetric Encryption

secret key: s ∈ {0, 1}na(a, b)

LWE Decryption

13 / 25

Introduction

The protocol

Properties

Conclusion

LWE
LWE Symmetric Encryption

secret key: s ∈ {0, 1}na

ϕ=b−a·s(a, ϕ)a(a, b)

LWE Decryption
1. Unlock the representation (a, ϕ)

13 / 25

Introduction

The protocol

Properties

Conclusion

LWE
LWE Symmetric Encryption

secret key: s ∈ {0, 1}n2/3

1/3a0(a, ϕ)ϕ=b−a·sa(a, b)

LWE Decryption
1. Unlock the representation (a, ϕ)
2. Round ϕ to the nearest message µ ∈ M
13 / 25

Introduction

The protocol

Properties

Conclusion

LWE
LWE Symmetric Encryption

secret key: s ∈ {0, 1}nab=a·s+ϕ
ϕ=b−a·s(a, ϕ)a(a, b)

Trivial LWE samples• LWE samples with mask a = 0 are trivial.

13 / 25

Introduction

The protocol

Properties

Conclusion

LWE
LWE Symmetric Encryption

secret key: s ∈ {0, 1}na0b=a·s+ϕ
ϕ=b−a·sa0(a, b)(a, ϕ)

Trivial LWE samples• LWE samples with mask a = 0 are trivial.
• They never occur in general...but are still worth mentionning!
13 / 25

Introduction

The protocol

Properties

Conclusion

LWE
LWE Symmetric Encryption

secret key: s ∈ {0, 1}na0b = Sorry,a·s+ϕ=b−a·snoϕmodq today!

a0(a, b)(a, ϕ)

Trivial LWE samples• LWE samples with mask a = 0 are trivial.
• They never occur in general...but are still worth mentionning!
13 / 25

Introduction

The protocol

Properties

Conclusion

LWE
Homomorphic Properties

a+a0a+a0b0ba=+a0=
ϕ0

ϕ
µµ0

αα0b + b0a+a0
ϕ + ϕ0µ00 = µ + µ0√00
α = α2 + α02

NAND achieved by composing additions and bootstrapping→ with NAND we can evaluate every circuit!
14 / 25

Introduction

The protocol

Properties

Conclusion

LWE
LWE Asymmetric Encryption

pk

a1

a2

a3...

am

15 / 25

Introduction

The protocol

Properties

Conclusion

LWE
LWE Asymmetric Encryption

pk0a1a2++...

a3...

+am=aCan be done on the public view, without knowing sk

15 / 25

Trustees use trapdoors
to produce and publish
PVCTs
Introduction
The protocol
Properties

Conclusion⇒ anyone can verify the decrypted result

Overview

publicBB(r0 , r1 , . . . , r`−1 )16 / 25

Introduction

The protocol

Properties

Conclusion

LWE and PVCT

It is possible to prove the correct decryption without revealing
any information on the secret?
Publicly Veriable Ciphertext Trapdoors (PVCT)
Combining [GPV08] and [MP12]

pka1a−2·same message

a2+3·a3+0·...

... −1·am=0

PVCT(small combination of pk)
17 / 25

Introduction

The protocol

Properties

Conclusion

Decrypting the result
The PVCT :• Does not reveal anything about the secret s (using [GPV08])• Proves the decryption of the ciphertext• Does not decrypt anything else
Finding a PVCT requires to invert aone-way SIS function
But there is a trapdoor solution [MP12]
Setup phase: trustees generate• Secret keys (concatenated LWE)
• The trapdoors
18 / 25

Trustees use trapdoors
to produce and publish
PVCTs
Introduction
The protocol
Properties

Conclusion⇒ anyone can verify the decrypted result

Decrypting the result

publicBB(r0 , r1 , . . . , r`−1 )VerifyTally
Public

PVCTs
Tally

(r0 , r1 , . . . , r`−1 )19 / 25

Introduction

The protocol

Properties

Conclusion

Table of contents

Introduction
The protocol
Properties
Conclusion

20 / 25

Introduction

The protocol

Properties

Conclusion

Properties

Correctness

Verifiability

Privacy?

Assumption: Bootstrapping as a random oracle

21 / 25

Introduction

The protocol

Properties

Conclusion

Table of contents

Introduction
The protocol
Properties
Conclusion

22 / 25

Introduction

The protocol

Properties

Conclusion

Summary and performance
Registration

TrusteesVoter(b0 , . . . , bk−1 )One-way bootstrap
publicper ballot(r0 , r1 , . . . , r`−1 )PVCTs(r0 , r1 , . . . , r`−1 )BB(b0 , . . . , bk−1 )1) Initial bootstrap2) Homomorphic expansion
3) Final bootstrap(00 , . . . , 0v−1 , 1v , 0v+1 , . . . , 0`−1 )all ballots(r0 , r1 , . . . , r`−1 )+23 / 25

Introduction

The protocol

Properties

ConclusionSummary and performance
Registration

Trustees

Voter(b0(`), . . encryptions. , bk−1 )k = log2
One-way bootstrap
publicper ballotBB(b0 , . . . , bk−1 )1) Initial bootstrap2) Homomorphic expansion
3) Final bootstrap(00 , . . . , 0v−1 , 1v , 0v+1 , . . . , 0`−1 )all ballots(r0 , r1 , . . . , r`−1 )+(r0 , r1 , . . . , r`−1 )PVCTs(r0 , r1 , . . . , r`−1 )1) Voters:- k bootstraps
2) BB (per ballot):- k bootstraps to verify- k initial bootstraps- (k × `) NAND gates- ` final bootstraps
Homomorphic sum +3) Trustees (each) :- ` generations of PVCTs
23 / 25

Introduction

The protocol

Properties

Conclusion

Conclusion
Homomorphic Encrypt
Security
Secret sharing
Honest Trustees
Ballot shape
Correct decrypt

HeliosOur protocol

Additive
DL (ElGamal )ShamirFully
Lattice-based (LWE )Concatenated LWE

66%

1

Initial NIZK proof
Final NIZK proof

Full domain
PVCT3 Any attempt of cheating is publicly detected
Open problems and future work• Prove the same strong privacy without relying on the assumption• Additional properties• Implement the scheme in practice

24 / 25

Introduction

The protocol

Properties

Conclusion

Arigato!

m.s.n.

25 / 25