Protecting against coercion in online elections

(sk, pk)

pk

Announced on election day

c = Enc(pk, m; r)

randomness

“A” or “B”

(sk, pk)

c

check that c = Enc(pk, “A”; r)

c = Enc(pk, A; r)

Protecting against coercion in online elections

An attack:

(sk, pk)

c

check that c = Enc(pk, “A”; r)

c = Enc(pk, A; r)

Protecting against coercion in online elections

A successful attack in this model:

the attacker is able to give instructions on how to encrypt the desired vote, and then check correctness upon intercepting.

(sk, pk)

c

check that c = Enc(pk, “A”; r)

c = Enc(pk, A; r)

This kind of attack (in this model) is impossible to prevent classically

Protecting against coercion in online elections

c

c

(sk, pk)

pk

The quantum setting:

classical

Desired

Property

Crucial difference: Randomness can be inherent to the quantum process

Protecting against coercion in online elections

What do we mean by “proof”?

What do we mean by “computational task”?

The “inability to prove”

Does there exist a computational task such that:

• it can be accomplished efficiently, but
• no “proof” can be provided efficiently ?

The “inability to prove”

Does there exist a computational task such that:

• it can be accomplished efficiently, but
• no “proof” can be provided efficiently ?

[C., Goldwasser, Vazirani ‘22]

The proof of quantumness task we already considered has this property.

An encryption scheme such that it is intractable to produce:

• a valid encryption c of m, AND
• a proof that c is a valid encryption of m

sk = trapdoor

The encryption scheme

such that…

sk = trapdoor

The encryption scheme

such that

sk = trapdoor

The encryption scheme

such that

sk = trapdoor

The encryption scheme

What about the other property? �It is intractable to produce both:

• a valid encryption c of m, AND
• a proof that c is a valid encryption of m

Doing both simultaneously is equivalent to being able to encrypt correctly and prove correctness of the encryption!

What if we allow quantum communication?

(sk, pk)

c

check that c = Enc(pk, “A”; r)

c = Enc(pk, A; r)

Our scheme with classical ciphertexts prevents

coercion in the following setting:

Crucially: coercion happens before pk is announced!

What if we allow quantum communication?

(sk, pk)

c

check that c = Enc(pk, “A”; r)

c = Enc(pk, A; r)

Our scheme with classical ciphertexts prevents

coercion in the following setting:

What if coercion happens after pk is announced?

What if we allow quantum communication?

(sk, pk)

c

check that voter sent the same c

c

With classical ciphertexts, there is no hope

to prevent coercion in this setting:

What if coercion happens after pk is announced?

What if we allow quantum communication?

(sk, pk)

c

check that voter sent the same c

c

What about quantum ciphertexts?

What if coercion happens after pk is announced?

What if we allow quantum communication?

(sk, pk)

check that voter sent the same

What about quantum ciphertexts?

What if coercion happens after pk is announced?

What if we allow quantum communication?

(sk, pk)

What about quantum ciphertexts?

What if coercion happens after pk is announced?

What if we allow quantum communication?

(sk, pk)

What about quantum ciphertexts?

What if coercion happens after pk is announced?

What if we allow quantum communication?

(sk, pk)

What about quantum ciphertexts?

What if coercion happens after pk is announced?

check that this state is the original one

But wait.. the attacker doesn’t have

the original state anymore, so how does it check?

Presumably the attacker knows an

efficient way to prepare it. This is sufficient.

What if we allow quantum communication?

(sk, pk)

What about quantum ciphertexts?

What if coercion happens after pk is announced?

check that this state is the original one

The only hope to prevent coercion is that the

attacker cannot efficiently prepare the original state.

We can come up with a scheme with this property!

sk = trapdoor

The encryption scheme (previously)

sk = trapdoor

The new encryption scheme

How to prepare this?

sk = trapdoor

The new encryption scheme

Decryption:

Perform the measurement that distinguishes

and

Can be done efficiently using the trapdoor.

Crucially: Without knowing the trapdoor, it’s hard

to prepare two copies of the same ciphertext!

sk = trapdoor

The new encryption scheme

Decryption:

Perform the measurement that distinguishes

and

Can be done efficiently using the trapdoor.

Crucially: Without knowing the trapdoor, it’s hard

to prepare two copies of the same ciphertext! �(since this allows to find a collision with constant probability)

The new encryption scheme

(sk, pk)

(sk, pk)

Can flip the received state

by applying a Z gate!

The new encryption scheme

(sk, pk)

Can flip the received state

by applying a Z gate!

Unable to tell whether a flip happened!

Why?

The new encryption scheme