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("\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 ==\n") N = new(big.Int).Mul(p, p) 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("\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=270687973518578505565415405737000039073 q=257249955799016440228578495409022605621 N=69634469222979653234172683771742436079989844506557653984050202964417269429333 Challenges: [4081915935819674866 7771834100878098077 751264372287560595 2842735999033168006 7640337853609011269] Proof: [50435949939125356734448386472848825637556576314789568135738799086963342327643 31720993722613141193100505387271108203865379781445917333528576411234490230500 12653758356315023215448847476701793996982334653034010273085131899334796194060 48118982018046864055030109025646020142133766426657922350814969528361615654715 38226047933305492579517173344332311379210622377414734095219761814113391295203] Zero knowledge proof of safe Paillier == Now trying with an incorrect value of N=p^2 == p=270687973518578505565415405737000039073 N=73271979007594658294666696598301800297000725997572228428121296723603526699329 Challenges: [4081915935819674866 7771834100878098077 751264372287560595 2842735999033168006 7640337853609011269] Proof: [19975224459901857656135089565983769109448528927762085267349342509390604341631 24943057169194765248327047967044522982293285623133752715304277467996372772319 16119190415362227893150734039413661341338905449326132690238754927325923084590 55532960836051320099319111843342098269888632554045034362219544875067444434746 41762585546059243749074436758293995718813533802740277734508993464550887820621] [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.