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).
Paillier Square Free Proof 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 random values as a challenge (\(x)), and passes this to Peggy. She then computes:
\(y = x^{M} \pmod N \)
Peggy passes this back to Victor and Victor then checks that:
\(x=y^N \mod N \)
If this equals the value that was sent, 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" "os" "strconv" crypto "github.com/coinbase/kryptology/pkg/core" ) func main() { nobits:=5 argCount := len(os.Args[1:]) if argCount > 0 { nobits,_ = strconv.Atoi(os.Args[1]) } p, _ := rand.Prime(rand.Reader, nobits) q:=p for { q, _ = rand.Prime(rand.Reader, nobits) if p.Cmp(q) != 0 { break } } 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))) M, _ := crypto.Inv(N, PHI) x, _ := rand.Int(rand.Reader, new(big.Int).SetUint64(uint64(math.Pow(2, float64(nobits))))) proof, _ := crypto.Exp(x, M, N) fmt.Printf("p=%s\n", p) fmt.Printf("q=%s\n", q) fmt.Printf("M=%s\n", M) fmt.Printf("N=%s\n", N) fmt.Printf("PHI=%s\n", PHI) fmt.Printf("\nChallenge:\t%v\n", x) fmt.Printf("Proof:\t%v\n", proof) lhs, _ := crypto.Exp(proof, N, N) fmt.Printf("Proof^N (mod N):\t%v\n", lhs) proven := true if lhs.Cmp(x) != 0 { 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))) M, _ = crypto.Inv(N, PHI) x, _ = rand.Int(rand.Reader, new(big.Int).SetUint64(uint64(math.Pow(2, float64(nobits))))) proof, _ = crypto.Exp(x, M, N) fmt.Printf("p=%s\n", p) fmt.Printf("M=%s\n", M) fmt.Printf("N=%s\n", N) fmt.Printf("\nChallenge:\t%v\n", x) fmt.Printf("Proof:\t%v\n", proof) lhs, _ = crypto.Exp(proof, N, N) fmt.Printf("Proof^N (mod N):\t%v\n", lhs) proven = true if lhs.Cmp(x) != 0 { 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=56873 q=51899 M=38396571 N=2951651827 PHI=2951543056 Challenge: 11890 Proof: 197271729 Proof^N (mod N): 11890 Zero knowledge proof of safe Paillier == Now trying with an incorrect value of N=p^2 == p=56873 M=3234310641 N=3234538129 Challenge: 40075 Proof: 1820886043 Proof^N (mod N): 2627629548 No Zero knowledge proof of safe Paillier
and:
p=60289 q=65147 M=3808946483 N=3927647483 PHI=3927522048 Challenge: 12020 Proof: 1915113617 Proof^N (mod N): 12020 Zero knowledge proof of safe Paillier == Now trying with an incorrect value of N=p^2 == p=60289 M=3634522369 N=3634763521 Challenge: 54274 Proof: 1017250282 Proof^N (mod N): 3295752459 No Zero knowledge proof of safe Paillier
Coding
Reference
[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. [here]