DLEQ - NIZK proofs for the equality (EQ) of discrete logarithms (DL) within subgroup of squares in (Z/nZ)*We can use Non-interactive zero-knowledge (NIZK) proofs, and where Peggy (the 'Prover') just has to prove that she still knows her secret (\(x\)). For equality (EQ) of discrete logarithms, we can prove that \(log_{g}(g^x) == log_{h}(h^x)\), and where Peggy does not have to reveal \(x\). For this, Peggy (the 'Prover') can send Victor (the 'Verifier') a challenge and a response (\(c,z\)). From this, Victor can verify that the proof is correct, and that she still knows \(x\). Eve cannot generate a valid proof, unless she knows \(x\). In this case we will implement a Non-interactive zero-knowledge (NIZK) proof for the equality (EQ) of discrete logarithms (DL) within subgroup of squares in (Z/nZ)* [1] - known as the Decision Diffie-Hellman (DDH) assumption. |
Method
Peggy creates a secret value (\(x\)) and then we creates two values \(g^x\) and \(h^x\), and sends these to Victor. Victor can then check that \(log_{g}(g^x) == log_{h}(h^x)\). Peggy first creates her secret (\(x\)), and then calculates:
\(g_x=g^x \pmod N\)
\(h_x=h^x \pmod N\)
\(g_r=g^r \pmod N\)
\(h_r=h^r \pmod N\)
Next Peggy creates a non-interactive challenge (\(c\)) and which is a hash of \(g,xG,h, xH,vG,vH\) and \(N\):
\(c = H(g,g_x,h,h_x,g_r,h_r,N)\)
and computes:
\(z= cx+r \pmod N\)
The proof this then \((z,c)\) Overall, Eve cannot construct a valid pair of \(z,c\) unless she knows \(x\).
Victor then proves that Peggy still knows the secret (\(x\)) by first recovering:
\(g_r=\frac{g^Z}{ {(g^x)}^c } \pmod N\)
\(h_r=\frac{h^Z}{ {(h^x)}^c } \pmod N\)
and then should compute the same challenge:
\(c_1 = H(g,g_x,h,h_x,g_r,h_r,N)\)
If \(c_1 == c\), it has been verified, and that Peggy has proven that she still knows \(x\).
This works because:
\( \frac{g^Z}{ {{(g^x)}^c} } = \frac{g^{cx+r)}}{g^{cx}} = g^{cx+r-cx} = g^r = g_r \pmod N \)
\( \frac{h^Z}{ {{(h^x)}^c} } = \frac{h^{cx+r)}}{h^{cx}} = h^{cx+r-cx} = h^r = h_r \pmod N\)
All of this holds if \(g\) and \(h\) are in \(Q_n\) and which is the subgroup of squares in (Z/nZ)* [1]. This is known as the Decision Diffie-Hellman (DDH), and where \(g\) and \(h\) are selected from \(Q_n\). Basically, a value (\(x\) belongs to \(Q_n\) if gcd(x, N) = 1, and there is a \(y\) for \(x = y^2 \pmod N\).
Overall the method is based on the technique described in "Practical Threshold Signatures" by Shoup [paper][1].
Outline
The code implementation is:
package main import ( "crypto/rand" "fmt" "math/big" "github.com/cloudflare/circl/zk/qndleq" ) func main() { const testTimes = 1 << 8 const SecParam = 128 one := big.NewInt(1) max := new(big.Int).Lsh(one, 256) N, _ := rand.Int(rand.Reader, max) if N.Bit(0) == 0 { N.Add(N, one) } x, _ := rand.Int(rand.Reader, N) g, _ := qndleq.SampleQn(rand.Reader, N) h, _ := qndleq.SampleQn(rand.Reader, N) gx := new(big.Int).Exp(g, x, N) hx := new(big.Int).Exp(h, x, N) proof, _ := qndleq.Prove(rand.Reader, x, g, gx, h, hx, N, SecParam) rtn := proof.Verify(g, gx, h, hx, N) fmt.Printf("Secret (x): %v\n", x) fmt.Printf("\n== Parameters ==\n") fmt.Printf("N: %v\n", N) fmt.Printf("g: %v\n", g) fmt.Printf("h: %v\n", h) fmt.Printf("gx: %v\n", gx) fmt.Printf("hx: %v\n", hx) // Given g, h in Qn (the subgroup of squares in (Z/nZ)*), it holds // gx = g^x mod N // hx = h^x mod N // x = Log_g(g^x) = Log_h(h^x) fmt.Printf("\n== Generate NIZKP ==\n") fmt.Printf("c: %v\n", proof.C) fmt.Printf("z: %v\n", proof.Z) fmt.Printf("\n== Verify ==\n") fmt.Printf("Verified: %v\n", rtn) }
A sample run is:
Secret (x): 2314238621677985015678995395194273437072566548380233438108628431433347108913 == Parameters == N: 4345168612223189753214327734015020835550428205948026244497988001885023245149 g: 3279682408872081559748453551150127933967213373394786941062528344533326463652 h: 1569736132337556106438262321257449765362412912066998950831042180950925860069 gx: 2981598504626674179407881346199522779264552148482577408563902859265946325680 hx: 424744822582851930363605013376094482256664168661392367593354625257431551932 == Generate NIZKP == c: 168886357222469079450243567177123105580 z: 8468687259225155781733973059773759736965044939978677575662810411988601824091525418475031316128645350508584215789222492535358205390299615754810819583109037 == Verify == Verified: true
If you want to understand Qn — the subgroup of squares in (Z/nZ), try here: [here]. The Decision Diffie-Hellman (DDH) assumption defines that with random vaues of \(g,h \in Q_n\), it is hard from \(g^a \pmod N\) and \(h^b \pmod N\), to decide if \(a \equiv b \pmod N\).
Reference
[1] Shoup, V. (2000). Practical threshold signatures. In Advances in Cryptology—EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques Bruges, Belgium, May 14–18, 2000 Proceedings 19 (pp. 207-220). Springer Berlin Heidelberg.