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

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.

• 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. Commented Aug 5, 2023 at 16:18
• 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$ ].
– fgrieu
Commented Aug 5, 2023 at 16:54
• @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!
– P S
Commented Aug 5, 2023 at 17:10
• 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.
– fgrieu
Commented Aug 5, 2023 at 17:11
• 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) Commented Aug 6, 2023 at 17:35

$$\mathrm{ballot}=(v+\mathrm{random\_number}\cdot c)^e\bmod n$$
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.