Score:2

Crypto

Prove with ZKP that I have encrypted a message $v + random\_number\cdot c$ given an RSA public key?

Purushotam Sangroula

8/5/24, 3:51 PM

I want to create an application in which users can cast vote to blockchain in encrypted form using RSA. The private key will be revealed only after completion of the election.

My major use case is as follows:

There will be certain number of candidates, $c$. So voter has to choose a number from $1$ to c, lets say his choice is $v$;
Encrypted votes will be: $ballot = v^e$;
Since there are finitely small $v$, $v^e$ is deterministic and anybody can determine the vote with a quick brute-force;
So I would like to introduce randomness by, $ballot = (v + random\_number \cdot c)^e$;
I plan to remove randomness after decryption by: $(v + random\_number \cdot c) \bmod c = v$.

How is it possible to create a zero knowledge proof that I have honestly computed $(v + random\_number \cdot c)^e$?

Any other solution such as one using zk-SNARK's would also be acceptable.

1 + 8

discrete-logarithm

zero-knowledge-proofs

voting

Maarten Bodewes

8/5/24, 4:18 PM

I've re-edited most of your question, please validate that the contents are still OK, as the edit was rather extensive. I didn't change the wording of the steps.

fgrieu

8/5/24, 4:54 PM

I guess we need to read $\mathrm{ballot}=(v+\mathrm{random\_number}\cdot c)^e\bmod n$. Also, since $0<v\le c$ \[rather than $0\le v<c$ \], decryption must be by $v=((\mathrm{ballot}^d\bmod n)-1\bmod c)+1$ \[rather than $v=(\mathrm{ballot}^d\bmod n)\bmod c$ \].

Purushotam Sangroula

8/5/24, 5:10 PM

@fgrieu-onstrike I think you are correct. But lets keep it simple for people suggesting the solutions. You may propose a solution for zkp for you approach. Thanks!

fgrieu

8/5/24, 5:11 PM

Independently: any integer in $|1,n)$ is of the form $v+\mathrm{random\_number}\cdot c$ for some $v\in[1,c]$ and some $\mathrm{random\_number}\in\mathbb N$. Therefore, with the current definition of $\mathrm{ballot}$ which does not restrict the upper range of range of $\mathrm{random\_number}$ \[beyond, implicitly, insuring $v+\mathrm{random\_number}\cdot c<n$ \], any $\mathrm{ballot}\in[1,n)$ could be honestly computed. Thus what's to be ZK-proven is knowledge of $v$ matching $\mathrm{ballot}$. Perhaps we should restrict the range of $\mathrm{random\_number}$ ? I don't see a ZKP either way.

Purushotam Sangroula

8/5/24, 7:04 PM

@fgrieu-onstrike One thing I would like to prove is that voter follows our rule of generating ballot (v+random_number⋅c)^e, where random_number acts as a blinding factor. I do not want voters to simply do something like this: (v)^e. Or I do not want followers of a candidate to run a secret campaign and form ballot by using a common random_number. If it happens then they can influence the running tally.

poncho

8/6/24, 1:57 AM

@PS: so, you'll looking for a proof that the 'random number' is, in fact, random? And, what is the actual goal? If it's to ensure that the ballots are secret, well, anyone could just announce (outside of the protocol) what their vote as, and there's nothing the protocol can do to prevent that.

Purushotam Sangroula

8/6/24, 5:20 PM

@poncho in that regard, that will be some ethical issue and people may or may not believe such claims. But here at least we do not want people to be able to show with proof that I voted for you or some one else.

poncho

8/6/24, 5:35 PM

However, with the current RSA encryption scheme, if they published their vote and their random number, anyone can verify that their published vote is correct. Hence, what you'd need is some way where they don't know their random number (and not just be able to prove that it is, in some sense, random). That sounds like it needs some sort of interactive encryption protocol - for any noninteractive one, they could publish the random coins they used to encrypt (which would be verifiable just like the original RSA scheme was)

Score:0

Crypto

fgrieu

8/8/24, 9:15 AM

$\mathrm{ballot}=(v+\mathrm{random\_number}\cdot c)^e\bmod n$
We do not want people to be able to show with proof that I voted for you or some one else.

Under these two premises, we can't let the voter perform the computation of $\mathrm{ballot}$. Argument: they can keep a copy of the integer $m=v+\mathrm{random\_number}\cdot c$ that they raise to the power $e$ modulo $n$, and reveal $m$. Then anyone can find $v$ from $m$, and verify $m^e\bmod n=\mathrm{ballot}$, thus be convinced that $\mathrm{ballot}$ corresponds to $v$.

If we want to keep the definition of $\mathrm{ballot}$, one option is to use a trusted device capable of performing random number generation and RSA encryption, such as a Smart Card, to turn $v$ into $\mathrm{ballot}$, with internal generation of $\mathrm{random\_number}$.

The device can also provide a signature of $\mathrm{ballot}$. Together with a PKI, that provides a static, publicly verifiable proof that $\mathrm{ballot}$ was generated by that device. Or/and if we insist on less convenient ZKP for some reason, the device can, conditionally to having performed that voting operation and being submitted a $\mathrm{ballot}$ that it generated, provide a standard ZKP that it knows some device-unique secret, which in some sense is a ZKP that $\mathrm{ballot}$ was generated as prescribed.

This shall not be construed as a recommendation to use such trusted device or protocol. On the contrary: my opinion is that whatever voting device should be fully understandable and auditable by a large fraction of the voting audience.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Prove with ZKP that I have encrypted a message $v + random\_number\cdot c$ given an RSA public key?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.