The following algorithm is supposed to implement Pk according to the following description:
To cast a vote, a voter posts an unsigned mes- sage 〈Enc(s; KTT), Enc(v; KTT), Pw, Pk〉 [...] Pk, implemented by adapting a proof due to Camenisch and Stadler [9], shows that the submitter simultaneously knows s and v. This defends against an adversary who attempts to post functions of previously cast votes. https://www.cs.cornell.edu/projects/civitas/papers/clarkson_civitas.pdf end of page 7, and beginning of page 8
[9] is https://sci-hub.reatk.com/10.1007/bfb0052252#gsc.tab=0
The algorithm:
/* * Public inputs o ElGamal parameters (p,g) o Encrypted capability = (a1,b1) o Encrypted choice = (a2,b2) o Vote context ctx o Let proof environment E = (g,a1,b1,a2,b2,ctx) * Prover private inputs: o alpha1, alpha2 s.t. ai = g^{alphai} * Prover: o Select r1,r2 at random from Z_q o Compute: + c = hash(E,g^r1,g^r2) + s1 = r1 - c*alpha1 mod p + s2 = r2 - c*alpha2 mod p * Prover -> Verifier: (c,s1,s2) * Verifier: o Check c = hash(E, g^s1 * a1^c, g^s2 * a2^c) */ Unfortunately I couldn't write a passing test for the implemented code. As that code is scattered around multiple places and uses a customized BigInt implementation, I have reimplemented the above algorithm the same way as the code in question implements it. You can find it below.
My questions:
- should the above algorithm work as described in the papers?
- As I understand, a1 in the algorithm is s in the paper, and a2 is v. Am I correct?
- I changed the proof environment into a single random BigInt in the below code for brewity, assuming that it does not change the main point of the algorithm. Is this assumption okay?
- I guess that the main point is checking that g^r1==g^s1 * a1^c and g^r2==g^s2 * a2^c. Should those equalities really hold?
- The original code used q (from the Schnorr group described by (p,q,g)) instead of p for modulo in some places. Is it because the Schnorr signature is the underlying algorithm, and basically exponents are elements of Z_q, while the bases are elements of the Schnorr group? The below code uses p and q the same way as the original.
- I have embedded all constants in the code. p,q and g are the El Gamal parameters described above, all other constants are effectively random.
BigInteger hash(BigInteger a, BigInteger b, BigInteger c) throws NoSuchAlgorithmException { MessageDigest digest = MessageDigest.getInstance("SHA-256"); digest.update(a.toByteArray()); digest.update(b.toByteArray()); digest.update(c.toByteArray()); return new BigInteger(digest.digest()); } BigInteger fromBase64(String base64) { return new BigInteger(Base64.getDecoder().decode(base64)); } @Test @DisplayName("algorithm check") void algorithmTest() throws NoSuchAlgorithmException { BigInteger p = fromBase64( "AIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAQ0gWk4zQiy9p87hS+sgNkxYr5okLM6HhXFTu2eUFgf5BQjju2YsvFhOXce4yJ00rsGSGeZAg5bT1Z45SdexGMevXEdCZrADRdikYU0ZLFTN7UWopWgLXd3DBfu3CY2fzwYzq0YWS0bzJ3cQA4fSAyFdU+Tekcd3vwQlkthh7WJW0VCYF1hGFdiGt9/aDQ7cDrW+fqbg4xrUN+wKoFbEHNHomUkGMaXsGyM9vyLCjtp9Jf/UXQSU9X+jAJS+Y7VXyEa9/ifHxsjAExE5RYpNWzqgjJRoiADVL1XeoqvdL/ltcEhAeq3TnhHNIi7cEGQZSGCvSVMiDPn2JBUeY8AswihwZhI7IiqroysQy6UcsZ45oACaVH0ZYSMSIvuGimPhqv0OVbR95lXipxaoHlygq8pLWJWlgVj9KIQQG1wTnD80liudqIdQ+/yuo10YxtGacmC7YxB/atrTgbJ8V/wRDRQw=="); BigInteger g = fromBase64( "az5EMeordK3a0VbjoUsKeo/++OHFs5WaRLw6hW8Ezu7D1Egid0U3Obtzpn0GG8UHQjJnHINqwK6bX6RXBlVfsDmiKS2lgvWrL53vSPXtZfFIC/307vWLV2RymA9TQaGZ5d4q7O7l2KHNUx+ecK6QVqKqj46IXjwaYzKQXNg2NfwQGfj7dBTaoGHE401pdoHfyLfluAF3k4ZT6imEoIbe4Ar7ybYdI5eJYn96/hoyLouux8jI1LE+Oe7+eI1M5WK30TPbGKVaon4KPnfLYp8+HTloYb/jlNFLckqdZchKa765pBRjvNu+7MmYpHmqBlLuCLd4sBbD//Sy/aHPnxyccZM0MMwRPSSM0NKO8UuXkCEmRSI6gvdwyIk6FwsB8bF4ksvBAMSfN8gJd7rv1t9B46OByCs8YNuL1eJH1wJThwpUf1iAXPjFCkvrR4fm+lOeIYCGhBkEO1pB2sRzTulRVEadM6bFwo2N5eZb3ymPfERXogTVmljtdzxlAao9vBgk"); BigInteger q = fromBase64("ALEbdrNCujCQI0Y4f38yusJkfR1nVqT95/P/H2z28zIH"); BigInteger alpha1 = fromBase64("eaUSELMHNaE="); BigInteger alpha2 = fromBase64("eOmnTcKMIpE="); BigInteger a1 = g.modPow(alpha1, p); BigInteger a2 = g.modPow(alpha2, p); BigInteger E = fromBase64("N8WtyRCrye3u8iDSDnKjAob9Wr/fMDqx3x3FE+OyDkM="); BigInteger r1 = fromBase64("JY+s34cV7ybeZLEpACLziJ3ZTb5fiCoGkx7duQSKvms="); BigInteger r2 = fromBase64("POILzE0M8iAYB1dCQW44j2oeofu6U7JMxnxoboocpBI="); BigInteger c = hash(E, g.modPow(r1, p), g.modPow(r2, p)).mod(q); BigInteger s1 = r1.subtract(c.multiply(alpha1).mod(q)).mod(q); BigInteger s2 = r2.subtract(c.multiply(alpha2).mod(q)).mod(q); BigInteger ss1 = g.modPow(s1, p).multiply(a1.modPow(c, p)).mod(p); BigInteger ss2 = g.modPow(s2, p).multiply(a2.modPow(c, p)).mod(p); assertEquals(s1, ss1); assertEquals(s2, ss2); BigInteger x = hash(E, ss1, ss2).mod(q); assertEquals(c, x); } 