In Paillier we pick two large prime numbers (\(p\) and \(q\))). We then calculate a modulus (\(N=pq\)) and \(\phi(N)=(p-1)(q-1)\). We then make sure that \(gcd(pq,\phi(N))=1\). Overall Pallier can be used to create partial homomorphic encryption. In this case we will use a HVZK (Honest Verifier Zero Knowledge) method for Peggy to prove the Victor that she has generated a modulus which is secure (that is, it is square free).
HVZK (Honest Verifier Zero Knowledge) using Paillier and Kryptology |
Background
And so to understand how we can prove that a secure Pailler key pair has been generated? Overall we can use the methods in the Kryptography library to implement the privacy-preserving methods in [1]:
The focus of the paper is to proven that a suitable private key has been created, so that the public key has all the possible values within the given field, and without leaking anything about the private key. In Paillier, we pick two large prime numbers (\(p\) and \(q\)). We then calculate a modulus (\(N=pq\)) and \(\phi(N)=(p−1)(q−1)\). We then make sure that \(gcd(pq,\phi(N))=1\).
One of the key properties is to prove that the value of N is square free (that is, it does not have a factor that is a square). Overall, Victor - the verifier - will not be able to factorize the modulus (\(N\)), so will have to trust Peggy in the creation of a secure modulus. For example, Peggy could cheat, and rather than creating \(N=p.q\), she could create \(N=p.p\), and which is p squared (\(N=p^2\)). This will produce a weak key. The method is defined here:
Overall Pallier can be used to create partial homomorphic encryption.
In Paillier, Peggy picks two large prime numbers (\(p\) and \(q\)). She then calculates a modulus (\(N=pq\)) and \(\phi(N)=(p-1)(q-1)\). Now Victor wants Peggy to prove that the modulus is square-free. For the proof Peggy computes:
\(M=N^{-1} \pmod {\phi(N)}\)
In an interactive proof, Victor (the verifier) then generates a number of random values as challenges (\(x_i\)), and passes these to Peggy. She then computes:
\(y_i = x_i^{M} \pmod N \)
Peggy passes these back to Victor and Victor then checks that:
\(x_i=y_i^N \mod N \)
for all values of \(i\). If these are all true, Peggy has proven that the modulus is square-free, as she should not be able to generate the proofs if she has cheated. Overall, we can make this non-interactive (NI), by allowing Peggy the chance to create her own challenges, and then present these with the proofs.
Coding
The outline coding using the library from the Krytology library:
package main import ( "crypto/rand" "fmt" "math" "math/big" crypto "github.com/coinbase/kryptology/pkg/core" ) func main() { p, _ := rand.Prime(rand.Reader, 128) q, _ := rand.Prime(rand.Reader, 128) N := new(big.Int).Mul(p, q) PHI := new(big.Int).Mul(new(big.Int).Sub(p, big.NewInt(1)), new(big.Int).Sub(q, big.NewInt(1))) PsfProofLength := 5 // 1. M = N^{-1} mod \phi(N) M, _ := crypto.Inv(N, PHI) // 2. Generate challenges x := make([]*big.Int, PsfProofLength) for i := 0; i < PsfProofLength; i++ { x[i], _ = rand.Int(rand.Reader, new(big.Int).SetUint64(uint64(math.Pow(2, 64)))) } proof := make([]*big.Int, PsfProofLength) // 3. Create proofs y_i = x_i^M mod N for i, xj := range x { yi, _ := crypto.Exp(xj, M, N) proof[i] = yi } fmt.Printf("p=%s\n", p) fmt.Printf("q=%s\n", q) fmt.Printf("N=%s\n", N) fmt.Printf("PHI=%s\n", PHI) fmt.Printf("\nChallenges:\t%v\n", x) fmt.Printf("Proof:\t%v\n", proof) proven := true for j, xj := range x { // 4. Proof: yj^N == x mod N return false lhs, _ := crypto.Exp(proof[j], N, N) if lhs.Cmp(xj) != 0 { fmt.Printf("Failed at %d\n", j) proven = false } } if proven == true { fmt.Printf("\nZero knowledge proof of safe Paillier\n") } else { fmt.Printf("\nNo Zero knowledge proof of safe Paillier\n") } fmt.Printf("\n\n== Now trying with an incorrect value of N=p^2 ==\n") N = new(big.Int).Mul(p, p) PHI = new(big.Int).Mul(new(big.Int).Sub(p, big.NewInt(1)), new(big.Int).Sub(p, big.NewInt(1))) proof = make([]*big.Int, PsfProofLength) // 3. Create proofs y_i = x_i^M mod N for i, xj := range x { yi, _ := crypto.Exp(xj, M, N) proof[i] = yi } fmt.Printf("p=%s\n", p) fmt.Printf("N=%s\n", N) fmt.Printf("PHI=%s\n", PHI) fmt.Printf("\nChallenges:\t%v\n", x) fmt.Printf("Proof:\t%v\n", proof) proven = true for j, xj := range x { // 4. Proof: yj^N == x mod N return false lhs, _ := crypto.Exp(proof[j], N, N) if lhs.Cmp(xj) != 0 { fmt.Printf("[Failed at %d]", j) proven = false } } if proven == true { fmt.Printf("\nZero knowledge proof of safe Paillier\n") } else { fmt.Printf("\nNo Zero knowledge proof of safe Paillier\n") } }
A sample run is:
p=272607875711507234568172267871128963309 q=295946972516113719350378532078127656991 N=80677475500869576284216027503952826078439882763776608467923415825330976343219 PHI=80677475500869576284216027503952826077871327915548987514004865025381719722920 Challenges: [6175083952328541262 8170758500240932032 690144035803220448 5251383100325791414 7491250541467116415] Proof: [11964768429949674995906973048072290410298740842351249440155864963629295066643 2404036667536209695550094652200905842055096939969209457294393748537640760745 40213555573116455989223390360860064550186560820959033554469884782324844562896 52274994561541289937830320424416180467927177634778522999370893526641867564866 48843463049104864058386473913402375195965387767392969916582915710419561820741] Zero knowledge proof of safe Paillier == Now trying with an incorrect value of N=p^2 == p=272607875711507234568172267871128963309 N=74315053899940576031754513999406594897046717010370080236134373721813068229481 PHI=74315053899940576031754513999406594896501501258947065766998029186070810302864 Challenges: [6175083952328541262 8170758500240932032 690144035803220448 5251383100325791414 7491250541467116415] Proof: [48347497314044952093421350958061044670781973850949883675536730894971919557470 10658399863087440754746008212552663340496243739712655818209208097999235794672 32586614850160003802408771853260820571836860873070529326104339164882528234538 57983605267606520649471600773805506019743872785122299504104128122615372714735 2095494264165920873205461901730045396708273073195597895993911748465314990906] [Failed at 0][Failed at 1][Failed at 2][Failed at 3][Failed at 4] No Zero knowledge proof of safe Paillier
Coding
[1] Goldberg, S., Reyzin, L., Sagga, O., & Baldimtsi, F. (2019, December). Efficient noninteractive certification of RSA moduli and beyond. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 700-727). Springer, Cham.