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=3163 q=3697 M=6045283 N=11693611 PHI=11686752 Challenge: 781 Proof: 8494942 Proof^N (mod N): 781 Zero knowledge proof of safe Paillier == Now trying with an incorrect value of N=p^2 == p=3163 M=9991921 N=10004569 Challenge: 3072 Proof: 2998433 Proof^N (mod N): 5674331 No Zero knowledge proof of safe Paillier
and:
p=338866964140043411468873848695275241571 q=303416071899795017719693767589867444787 M=2667416890610086376756756543888369247051051012931162538919083196037004544533 N=102817683155980671680331235902830578322249490715746792929396448502149929640377 PHI=102817683155980671680331235902830578321607207679706954500207880885864786954020 Challenge: 5778954262180670354 Proof: 17541698715363339637339111063123573377678392333813998745320388206205518554463 Proof^N (mod N): 5778954262180670354 Zero knowledge proof of safe Paillier == Now trying with an incorrect value of N=p^2 == p=338866964140043411468873848695275241571 M=114830819385489467364932280308566871929518427848663364068580836562831305581761 N=114830819385489467364932280308566871930873895705223537714456331957612406548041 Challenge: 3182905517568311201 Proof: 101673933567844850137914416419994421527326217936079135451976555636417860079774 Proof^N (mod N): 80939508196207850652294141501902064755098489726530492563801723952829877603051 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]