Cryptography Schema¶
Title: Voting Protocol Cryptography Schema
Status: Proposed
Authors: - Alex Pozhylenkov alex.pozhylenkov@iohk.io
Created: 2024-09-06
Abstract¶
This voting protocol is based on this paper and on this specification, so all formal definitions described in this document you can find there. It provides a fully anonymous, secured, verifiable schema of casting votes and performing tally process for executing "Catalyst" fund events.
Motivation¶
Specification¶
Preliminaries¶
The protocol is based around the following entities:
- Proposal - voting subject on which each voter will be cast their votes.
- Proposal voting options - a proposal options array, e.g. \([Yes, No, Abstain]\).
- Voting committee - a special trusted entity, which perform tally process and revealing the results of the tallying. Such committee consists of the 1 person.
- Voters - actors who actually performing the voting by posting ballots with their voting choices.
- Election public key \(pk\) - committees generated public key, which is shared across all voters and used for vote's encryption and tallying processes.
- Voter's voting power - an integer value which defines a voting power for a specific voter. This value could be equals to \(1\) for every voter, so everyone would be equal in their voting rights. Or it could be defined based on their stake in the blockchain, which is more appropriate for web3 systems.
Important to note that the protocol defined for single proposal. Obviously, it could be easily scaled for a set of proposals, performing protocol steps in parallel.
Initial setup¶
Before any voting will start an initial setup procedure should be performed.
- Define an array of voting options/choices for a proposal, e.g. \([Yes, No, Abstain]\).
- Voting committee must generate a shared election public key \(pk\) and distribute it among voters. A corresponding private key (secret share) \(sk\) will be used to perform tally.
- Define for each voter their own voting power. Basically this step could be done at any point of time, but before the tally.
- As most of the crypto algorithms are group dependent (more about this you can read in appendix A), it is needed to specifically define which cryptographically secure group would be used.
- Define a hash function which will be used by the underlying crypto algorithms.
- Define a commitment key \(ck\), which will be used during the voter proof generation and verification procedures.
Vote¶
A voter could cast a vote for some proposal. To do that, obviously, a voting choice should be made and encoded in specific format. For achieving anonymity this voting choice must be homomorphically encrypted, using the specific election public key \(pk\), so afterwards voting committee could perform tally. It is also important for the voter to generate a cryptographically secured proof, that he has generated and encrypted a vote correctly and according to the protocol, and everyone would be able to verify it. So we will preserve anonymity without lacking transparency and correctness.
Voting choice¶
For some proposal, voter generates a unit vector \(\mathbf{e}_i\),
the length of such vector must be equal to the amount of the voting options of the proposal.
\(i\) corresponds to the proposal voting choice and
defines that the \(i\)-th component of the unit vector equals to \(1\)
and the rest components are equals to \(0\).
And it stands as an identifier of the unit vector and could varies \(0 \le i \le M - 1\),
\(M\) - amount of the voting options.
E.g. proposal has voting options \([Yes, No, Abstain]\):
- \(\mathbf{e}_0\) equals to \((1,0,0)\) corresponds to \(Yes\)
- \(\mathbf{e}_1\) equals to \((0,1,0)\) corresponds to \(No\)
- \(\mathbf{e}_2\) equals to \((0,0,1)\) corresponds to \(Abstain\)
Lets \(e_{i,j}\) denote as an each component value of the unit vector \(\mathbf{e}_i\).
Where \(i\) is a unit vector's identifier as it was described before,
\(j\) index of the unit vector's component, which could varies \(1 \le j \le M\),
\(M\) - amount of the voting options and equals to the length of the unit vector.
Using such notation unit vector \(\mathbf{e}_i\) could be defined as
E.g. for the unit vector \(\mathbf{e}_0 = [1,0,0]\) components would be defined as follows:
- \(e_{0, 0}\) equals to \(1\)
- \(e_{0, 1}\) equals to \(0\)
- \(e_{0, 2}\) equals to \(0\)
Vote encryption¶
After the choice is done (described in section), vote must be encrypted using shared election public key \(pk\).
To achieve that, Lifted ElGamal encryption algorithm is used ElGamalEnc,
noted as \(VoteEnc(message, randomness, public \; key)\).
More detailed description of the lifted ElGamal algorithm
you can find in the appendix B.
\(VoteEnc(message, randomness, public \; key)\) algorithm produces
a ciphertext \(c\) with the generated randomness \(r\) as a result.
\begin{equation}
c, r = VoteEnc(message, public \; key)
\end{equation}
To encrypt previously generated unit vector \(\mathbf{e}_i\) (\(i\) - voting choice identifier),
for each vector component value \(e_{i,j}\) generate a corresponding randomness.
Lets denote randomness value as \(r_j\),
where \(j\) is the same vector component's index \(j\) value, \(e_{i, j} => r_j\).
Then, for each vector component \(e_{i,j}\) with the corresponding randomness \(r_j\), perform encryption algorithm applying shared election public key \(pk\). \begin{equation} c_j, r_j = VoteEnc(e_{i,j}, pk) \end{equation}
As a result getting a vector \(\mathbf{c}\) of ciphertext values \(c_f\), with the size equals of the size \(\mathbf{e}_t\) unit vector, equals to the amount of the voting options. Lets denote this vector as: \begin{equation} \mathbf{c}, \mathbf{r} = [(c_0, r_0), \ldots, (c_{M-1}, r_{M-1})] = (VoteEnc(e_{i,j}, pk), \ldots, VoteEnc(e_{i,M - 1}, pk)) \end{equation}
where \(M\) is the voting options amount and \(i\) is the index of the voting choice.
This is a first part of the published vote for a specific proposal.
Voter's proof¶
After the voter's choice is generated and encrypted, it is crucial to prove that encoding and encryption are formed correctly (i.e. that the voter indeed encrypt a unit vector).
Because by the definition of the encryption algorithm \(VoteEnc(message, public \; key)\) encrypts any message value, it is not restricted for encryption only \(0\) and \(1\) values (as it was stated in the previous section, unit vector components only could be \(0\) or \(1\)). That's why it is needed to generate such a proof, so everyone could validate a correctness of the encrypted vote data, without revealing a voting choice itself.
To achieve that a some sophisticated ZK (Zero Knowledge) algorithm is used, noted as \(VoteProof(\mathbf{c}, \mathbf{e}_i, \mathbf{r}, pk, ck)\). It takes an encrypted vote vector \(\mathbf{c}\), an original vote unit vector \(\mathbf{e}_i\), a randomness vector \(\mathbf{r}\), which was used during encryption algorithm \(VoteEnc\) a shared election public key \(pk\) and a commitment key \(ck\). As a result it generates a proof value \(\pi\). \begin{equation} \pi = VoteProof(\mathbf{c}, \mathbf{e}_i, \mathbf{r}, pk, ck) \end{equation}
So to validate a \(VoteCheck(\mathbf{c}, \pi, pk, ck)\) procedure should be used,
which takes an encrypted vote \(\mathbf{c}\), corresponded proof \(\pi\),
the same shared election public key \(pk\) and a commitment key \(ck\)
as arguments and returns true or false,
is it valid or not.
\begin{equation}
true | false = VoteCheck(\mathbf{c}, \pi, pk, ck)
\end{equation}
A more detailed description of how \(VoteProof\), \(VoteCheck\) work you can find in the appendix D.
Vote publishing¶
After all these procedures are done, a final step is to publish an encrypted vote \(\mathbf{c}\) and voter's proof \(\pi\) corresponded to this choice. It could be published using any public channel, e.g. blockchain, ipfs or through p2p network.
Tally¶
After voters performed voting procedure and encrypted votes are published, tally could be executed by the voting committee. Important to note, voting committee doing tally does not revealing personal voting choices.
By the result of tally procedure means
an accumulated sum of voting power for each voting option of the proposal,
based on published votes.
E.g.:
- proposal with voting options \([Yes, No, Abstain]\)
- two different voters with their voting power:
- "Alice" with voting power \(10\)
- "Bob" with voting power \(30\)
- these voter's published their choices on this proposal:
- "Alice" voted \(Yes\)
- "Bob" voted \(No\)
- final result would be the following:
- \(Yes\) accumulated \(10\)
- \(No\) accumulated \(30\)
- \(Abstain\) accumulated \(0\)
So to replicate the same process but securely, based on the set of encrypted votes \(\mathbf{c}\), a special \(Tally\), \(TallyDec\) and \(TallyProof\) algorithms are used.
Homomorphic tally¶
To perform homomorphic tally of the encrypted set of votes, \(Tally\) algorithm is used which described in appendix C. It takes as an input the following:
- \([\mathbf{c_1}, \mathbf{c_2}, \ldots, \mathbf{c}_{N}]\) - an array of all published encrypted vote's.
- \([\alpha_1, \alpha_2, \ldots, \alpha_N]\) - an array of corresponded voter's voting power.
- \(i\) - voting option index.
Where \(N\) - votes amount.
And produce an encrypted tally result for voting option \(i\). \begin{equation} er_i = Tally(i, [\mathbf{c_1}, \mathbf{c_2}, \ldots, \mathbf{c_N}], [\alpha_1, \alpha_2, \ldots, \alpha_N]) \end{equation}
E.g. a proposal with voting choices \([Yes, No]\), votes \([\mathbf{c_1}, \mathbf{c_2}]\), voting powers \([\alpha_1, \alpha_2]\) and election secret key \(sk\).
- Encrypted result for option \(Yes\): \(er_1 = Tally(1, [\mathbf{c_1}, \mathbf{c_2}], [\alpha_1, \alpha_2])\).
- Encrypted result for option \(No\): \(er_2 = Tally(2, [\mathbf{c_1}, \mathbf{c_2}], [\alpha_1, \alpha_2])\)
Tally decryption¶
To decrypt each calculated tally result from the previous step, \(TallyDec\) is used, which is technically a common \(ElGamalDec\) algorithm described in appendix B. It takes as an input the following:
- \(sk\) - an election private key held by voting committee.
- \(er_i\) - an encrypted tally result for the specific voting option defined for a proposal.
It produces a decrypted tally result for the voting option of a proposal. \begin{equation} r_i = ElGamalDec(er_i, sk) = TallyDec(er_i, sk) \end{equation}
This decrypted tally result is an exact result of the voting procedure, which represents an outcome of the election process.
E.g. a proposal with voting choices \([Yes, No]\), encrypted tally results \([er_1, er_2]\) and election secret key \(sk\).
- Decrypted result for option \(Yes\): \(r_1 = TallyDec(er_1, sk)\).
- Decrypted result for option \(No\): \(r_2 = TallyDec(er_2, sk)\)
Tally proof¶
An important step for bringing transparency and exclude misbehaving from the voting committee, a corresponded proof for each decrypted tally result must be generated.
It is necessary to verify that encrypted tally was decrypted exactly by using committee secret key, and not any other. So the publicly published decrypted tally result (a final tally result) actually is correct and represents a proper election outcome.
To do that, a sophisticated ZK (Zero Knowledge) \(TallyProof\) algorithm is used. Which proofs that a provided encrypted tally result value \(er\) was decrypted into tally result \(r\) using the exact secret key \(sk\), which is corresponded to the already known shared election public key \(pk\). \begin{equation} \pi = TallyProof(er, sk) \end{equation}
So to validate a \(TallyCheck(er, r, pk, \pi)\) procedure should be used,
which takes an encrypted tally result \(er\), decrypted tally result \(r\),
election public key \(pk\) and corresponded proof \(\pi\)
as arguments and returns true or false,
is it valid or not.
\begin{equation}
true | false = TallyCheck(er, r, pk, \pi)
\end{equation}
A more detailed description of how \(TallyProof\), \(TallyCheck\) work you can find in the appendix E.
Tally publishing¶
After all these procedures are done, a final step is to publish an encrypted tally results \(er_i\), decrypted tally results \(r_i\) and tally proofs \(\pi_i\) corresponded for each voting option of some proposal. It could be published using any public channel, e.g. blockchain, ipfs or through p2p network.
A: Group Definition¶
Important to note that some crypto algorithms, which are described below, are group \(\mathbb{G}\) dependant.
More detailed about groups you can find at section 8.2.1 section on this book.
Therefore, the generalized notation of the group operation used - \(\circ\).
And defined as follows:
- For all \(a, b \in \mathbb{G}\), \(a \circ b = c\), where \(c \in \mathbb{G}\).
- For all \(a \in \mathbb{G}\), and \(n \in \mathbb{Z}\), \(a^n = a \circ a \ldots \circ a\) (\(n\) - times).
- There is an element noted as \(1\), called neutral element, such that \(a \circ 1 = a\), for all \(a \in \mathbb{G}\).
- For each element \(a \in \mathbb{G}\) exists \(a^{-1} \in \mathbb{G}\), called the inversed of \(a\), such that \(a \circ a^{-1} = a^{-1} \circ a = 1\).
B: Lifted ElGamal Encryption/Decryption¶
Lifted ElGamal encryption schema is defined over
any cyclic group \(\mathbb{G}\) of order \(q\) with group generator \(g\) (\(g \in \mathbb{G}\)).
It could be multiplicative group of integers modulo \(n\) or some elliptic curve over the finite field group.
More detailed how group operations are defined, described in appendix A.
Encryption¶
Lifted ElGamal encryption algorithm takes as arguments:
- \(m\) - message (\(m \in \mathbb{Z}_q\))
- \(r\) - randomness (\(r \in \mathbb{Z}_q\))
- \(pk\) - public key (\(pk \in \mathbb{G}\))
\(c\) - is a resulted ciphertext which consists of two elements \(c_1, c_2 \in \mathbb{G}\).
Decryption¶
Lifted ElGamal decryption algorithm takes as arguments:
- \(c\) - ciphertext,
- \(sk\) - secret key (\(sk \in \mathbb{Z}_q\))
\(m\) - an original message which was encrypted on the previous step, \(Dlog(x)\) is a discrete logarithm of \(x\). Note that since \(Dlog\) is not efficient, the message space should be a small set, say \(m \in \{0,1\}^{\xi}\), for \(\xi \le 30\).
C: Homomorphic Tally¶
Homomorphic tally schema is defined over any cyclic group \(\mathbb{G}\) of order \(q\) with group generator \(g\) (\(g \in \mathbb{G}\)).
More detailed how group operations are defined, described in appendix A.
Homomorphic tally algorithm takes as arguments:
- \(i\) - voting choice index
- \([\mathbf{c_1}, \mathbf{c_2}, \ldots, \mathbf{c_N}]\) - an array of encrypted votes vector's, where \(N\) - votes amount
- \([\alpha_1, \alpha_2, \ldots, \alpha_N]\) - an array of corresponded voter's voting power, where \(N\) - votes amount
Where \(c_{j, i}\) - an encrypted corresponded \(i\)-th vector's component of the encrypted vote \(\mathbf{c_j}\). As it was stated in this section each encrypted vote is a vector \(\mathbf{c_j} = (c_{j, 1}, \ldots, c_{j, M})\), \(M\) - number of voting choices.
\(er_i\) noted as encrypted tally result for the provided \(i\)-th voting choice. As it is not an open decrypted value yet, it needs a decryption procedure corresponded for which encryption one was made.
Important to note that the resulted value \(er_i\) is a ciphertext, the same as \(c_{j, i}\). So \(er_i = (er_{i, 1}, er_{i, 2})\) consists of elements \(er_{i, 1}, er_{i, 2} \in \mathbb{G}\). Operations which are applied for pair \(c_{j, i} \circ c_{j+1, i}\), actually means the following:
So \(\circ\) operation applied separately for each corresponding items of the ciphertexts \(c_{j, i}, c_{j+1, i}\) and in the result we are getting a new ciphertext.
D: Non-Interactive ZK Vote Proof¶
Non-Interactive ZK (Zero Knowledge) Vote Proof algorithm helps to solve only one problem, to prove that the encrypted voting choice is exactly a some unit vector, which consists of only one is \(1\) value and others are \(0\).
A more detailed and formal description you can find in the section 2.4 of this paper.
It is assumed that the original encryption and decryption is performing by ElGamal scheme. It means that all described operations is also group dependent (more about groups described in appendix A).
Prover¶
The prover algorithm takes as arguments:
- \(\mathbf{c} = (c_0, \ldots, c_{M-1})\) - encrypted vote (a vector of ciphertext), where \(M\) is amount of voting options.
- \(\mathbf{e}_i = (e_{i,0},\ldots, e_{i,M-1})\) - original voting choice, a unit vector, where \(M\) is amount of voting options and \(i\) is an index of the voting choice.
- \(\mathbf{r} = (r_0, \ldots, r_{M-1})\) - a vector of randomnesses, which was used during encryption.
- \(pk\) - is a public key, which was used to encrypt a unit vector.
- \(ck \in \mathbb{G}\) - a commitment key.
So basically here is the relation between all these values: \begin{equation} \mathbf{c} = (c_1, \ldots, c_M) = (VoteEnc(e_{i,1}, r_1, pk), \ldots, VoteEnc(e_{i,M}, r_M, pk)) \end{equation}
Important to note that the following notation would be used \(\{a_i\}\) - which is a set of some elements \(a_i\).
\(\pi\) is the final proof. To compute it, prover needs to perform the next steps:
- If the number of voting options \(M\) is not a perfect power of \(2\), extend the vector \(\mathbf{c}\) with \(c_j = VoteEnc(0, 0, pk)\), where \(N\) is a perfect power of \(2\), \(j \in [M, \ldots, N - 1]\). So the resulted \(\mathbf{c} = (c_1, \ldots, c_M, \{c_j\})\).
- Let \(i_k\) is a bit value of the \(i\)-th binary representation (little-endian order), where \(k \in [0, log_2(N) - 1]\). E.g. \(i=3\) and \(N=8, log_2(N) = 3\), its binary representation \(i=011\), \(i_0=1, i_1=1, i_2=0\).
- For \(l \in [0, \ldots, log_2(N)-1]\) generate a random values \(\alpha_l, \beta_l, \gamma_l, \delta_l, \in \mathbb{Z}_q\).
- For \(l \in [0, \ldots, log_2(N)-1]\) calculate, where \(g\) is the group generator:
- \(I_l = g^{i_l} \circ ck^{\alpha_l}, I_l \in \mathbb{G}\).
- \(B_l = g^{\beta_l} \circ ck^{\gamma_l}, B_l \in \mathbb{G}\).
- \(A_l = g^{i_l * \beta_l} \circ ck^{\delta_l}, A_l \in \mathbb{G}\).
- Calculate a first verifier challenge \(ch_1 = H(ck, pk, \{c_j\}, \{I_l\}, \{B_l\}, \{A_l\})\), where \(H\) is a hash function, \(j \in [0, \ldots, N-1]\) and \(l \in [0, \ldots, log_2(N)-1]\).
- For \(j \in [0, \ldots, N-1]\) calculate polynomials
in the following form \(p_j(x) = e_{i, j}*x^{log_2(N)} + \sum_{l=0}^{log_2(N)-1} p_{j,l} * x^l\):
- \(j_l\) is a bit value of the \(j\)-th binary representation (same as was described in step
2). - \(z_l^{1} = i_l * x + \beta_l\).
- \(z_l^{0} = x - z_l^{1} = (1 - i_l)*x - \beta_l\).
- Calculate the polynomial itself \(p_j(x) = \prod_{l=0}^{log_2(N)-1} z_l^{j_l}\)
- \(j_l\) is a bit value of the \(j\)-th binary representation (same as was described in step
- For \(l \in [0, \ldots, log_2(N)-1]\) generate a random \(R_l \in \mathbb{Z}_q\).
- For \(l \in [0, \ldots, log_2(N)-1]\) compute
\(D_l = VoteEnc(sum_l, R_l, pk)\),
where \(sum_l = \sum_{j=0}^{N-1}(p_{j,l} * ch_1^j)\)
and \(p_{j,l}\) - corresponding coefficients of the polynomial \(p_j(x)\) calculated on step
7. - Calculate a second verifier challenge \(ch_2 = H(ch_1, \{D_l\})\), where \(H\) is a hash function and \(l \in [0, \ldots, log_2(N)-1]\).
- For \(l \in [0, \ldots, log_2(N)-1]\) calculate:
- \(z_l = i_l * ch_2 + \beta_l, z_l \in \mathbb{Z}_q\).
- \(w_l = \alpha_l * ch_2 + \gamma_l, w_l \in \mathbb{Z}_q\).
- \(v_l = \alpha_l * (ch_2 - z_l) + \delta_l, v_l \in \mathbb{Z}_q\).
- Calculate
\(R=\sum_{j=0}^{N-1}(r_j * (ch_2)^{log_2(N)} * (ch_1)^j) + \sum_{l=0}^{log_2(N)-1}(R_l * (ch_2)^l)\),
where \(r_j\) original random values which was used to encrypt \(c_j\)
and \(R_l\) random values generated in step
8.
Finally, the proof is \(\pi = (\{I_l\}, \{B_l\}, \{A_l\}, \{D_l\}, \{z_l\}, \{w_l\}, \{v_l\}, R)\), where \(l \in [0, \ldots, log_2(N)-1]\).
Verifier¶
The verifier algorithm takes as arguments:
- \(\mathbf{c} = (c_0, \ldots, c_{M-1})\) - encrypted vote (a vector of ciphertext), where \(M\) is amount of voting options.
- \(\pi\) - a prover's proof generated on the previous step
- \(pk\) - is a public key, which was used to encrypt a unit vector.
- \(ck \in \mathbb{G}\) - a commitment key, same which was used by the prover.
As a result algorithm will return true or false,
is the verification was succeeded or not respectively.
Knowing that \(\pi\) equals to \((\{I_l\}, \{B_l\}, \{A_l\}, \{D_l\}, \{z_l\}, \{w_l\}, \{v_l\}, R)\), verifier needs to perform the next steps:
- If the number of voting options \(M\) is not a perfect power of \(2\), extend the vector \(\mathbf{c}\) with \(c_j = VoteEnc(0, 0, pk)\), where \(N\) is a perfect power of \(2\), \(j \in [M, \ldots, N - 1]\). So the resulted \(\mathbf{c} = (c_1, \ldots, c_M, \{c_j\})\).
- Calculate the first verifier challenge \(ch_1 = H(ck, pk, \{c_j\}, \{I_l\}, \{B_l\}, \{A_l\})\), where \(H\) is a hash function, \(j \in [0, \ldots, N-1]\) and \(l \in [0, \ldots, log_2(N)-1]\).
- Calculate a second verifier challenge \(ch_2 = H(ch_1, \{D_l\})\), where \(H\) is a hash function and \(l \in [0, \ldots, log_2(N)-1]\).
- For \(l \in [0, \ldots, log_2(N)-1]\) verify that the following statements are
true, where \(g\) is the group generator:- \((I_l)^{ch_2} \circ B_l == g^{z_l} \circ ck^{w_l}\).
- \((I_l)^{ch_2 - z_l} \circ A_l == g^{0} \circ ck^{v_l}\).
- Calculate the following \(Left = VoteEnc(0, R, pk)\). Note that the \(Left\) is a ciphertext, \(Left = (Left_1, Left_2)\).
- Note that \(D_l\) is a ciphertext,
\(D_l = (D_{l,1}, D_{l,2})\), for \(l \in [0, \ldots, log_2(N)-1]\)
calculate the following:
- \(Right2_1 = (D_{0,1})^{ch_2^{0}} \circ \ldots \circ (D_{log_2(N) - 1,1})^{ch_2^{log_2(N) - 1}}\).
- \(Right2_2 = (D_{0,2})^{ch_2^{0}} \circ \ldots \circ (D_{log_2(N) - 1,2})^{ch_2^{log_2(N) - 1}}\).
- For \(j \in [0, \ldots, N-1]\) calculate the \(p_j(ch_2)\),
where \(p_j\) is a prover's defined polynomial defined in step
7:- \(j_l\) is a bit value of the \(j\)-th binary representation.
- \(z_l^1 = z_j\).
- \(z_l^0 = ch_2 - z_j^1\).
- \(p_j(ch_2) = \prod_l^{log_2(N)-1} z_l^{j_l}\).
- For \(j \in [0, \ldots, N-1]\) calculate the \(P_j = VoteEnc(-p_j(ch_2), 0, pk)\). Note that the \(P_j\) is a ciphertext, \(P_j = (P_{j,1}, P_{j,2})\).
- Note that \(C_j\) is a ciphertext,
\(C_j = (C_{j,1}, C_{j,2})\), for \(j \in [0, \ldots, N-1]\)
calculate:
- \(Right1_{j,1} = (C_{j,1})^{ch_2^{log_2(N)}} \circ (P_{j,1})^{ch_1^{j}}\).
- \(Right1_{j,2} = (C_{j,2})^{ch_2^{log_2(N)}} \circ (P_{j,2})^{ch_1^{j}}\).
- \(Right1_{1} = Right1_{j,1} \circ \ldots \circ Right1_{N - 1, 1}\).
- \(Right1_{2} = Right1_{j,2} \circ \ldots \circ Right1_{N - 1, 2}\).
- Verify that the following statements are
true:- \(Right1_{1} \circ Right2_1 == Left_1\).
- \(Right1_{2} \circ Right2_2 == Left_2\).
If step 4 and 10 returns true so the final result is true otherwise return false.
E: Non-Interactive ZK Tally Proof¶
Non-Interactive ZK (Zero Knowledge) Tally Proof algorithm helps to solve only one problem, to prove that the specific encrypted message was decrypted into the specific resulted value, using exactly that secret key, which is corresponds to the some shared public key.
It is a slightly modified version of the algorithm described in the sections Fig. 10 and 2.1.5 of this paper.
It is assumed that the original encryption and decryption is performing by ElGamal scheme. It means that all described operations is also group dependent (more about groups described in appendix A).
Prover¶
The prover algorithm takes as arguments:
- \(enc\) - an encrypted message (ciphertext).
- \(sk\) - a secret key which was used to decrypt a message \(enc\).
\(\pi\) is the final proof. To compute it, prover needs to perform the next steps:
- Take the first element of the ciphertext \(enc = (enc_1, enc_2)\).
- Calculate \(d = enc_1^{sk}, \quad d \in \mathbb{G}\).
- Generate a random value \(\mu, \quad \mu \in \mathbb{Z}_q\).
- Compute \(A_1 = g^{\mu}\), where \(g\) is the group generator (\(A_1 \in \mathbb{G}\)).
- Compute \(A_2 = (enc_1)^{\mu}, \quad A_2 \in \mathbb{G}\).
- Compute \(с = H(pk, d, g, enc_1, A_1, A_2)\), where \(pk\) is a corresponding public key of \(sk\), \(H\) is a hash function.
- Compute \(z = sk * с + \mu, \quad z \in \mathbb{Z}_q\).
Finally, the proof is \(\pi = (с, z)\).
Verifier¶
The verifier algorithm takes as arguments:
- \(enc\) - an encrypted message (ciphertext).
- \(dec\) - a decrypted message from the encrypted ciphertext \(enc\).
- \(pk\) - a public key corresponded to the \(sk\) which was supposedly used to decrypt a message \(enc\).
- \(\pi\) - a prover's proof generated on the previous step.
As a result algorithm will return true or false,
is the verification was succeeded or not respectively.
Knowing that \(\pi\) equals to \((с, z)\), verifier needs to perform the next steps:
- Take the first and second elements \(enc_1, enc_2\) of the ciphertext \(enc = (enc_1, enc_2)\).
- Calculate \(d = enc_2 \circ g^{-dec}, \quad d \in \mathbb{G}\).
- Calculate \(A_1 = g^{z} \circ pk^{-c}, \quad A_1 \in \mathbb{G}\).
- Calculate \(A_2 = enc_1^{z} \circ d^{-c}, \quad A_2 \in \mathbb{G}\).
- Compute \(с2 = H(pk, d, g, enc_1, A_1, A_2)\), where \(g\) is the group generator.
- Verify \(с == с2\).
If step 6 returns true so the final result is true otherwise return false.