Non-Interactive Proof of DLEQ using the Decision Diffie-Hellman (DDH) Assumption

Here’s my Sunday morning doodle:

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(gx)==log_h(hx), 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 a 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 checks that log_g(g^x)==log_h(h^x). Peggy first creates her secret (x), and then calculates:

Next Peggy creates a non-interactive challenge (c) and which is a hash of g,xG,h,xH,vG,vH and N:

and computes:

z=cx+r

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:

and then should compute the same challenge:

If c1==c, it has been verified, and that Peggy has proven that she still knows x. This works because:

All of this holds if g and h are in Qn and which is the subgroup of squares in (Z/nZ)*) [1]. This is known as the Decision Diffie-Hellman (DDH) proof, and where g and h are selected from Qn. Basically, a value (x belongs to Qn if gcd(x, N) = 1, and there is a y for x=y^2 (mod N).

Overall the method is based on the technique described in “Practical Threshold Signatures” by Shoup [paper][1].

Coding

The code implementation is [here]:

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 [here]:

Secret (x): 2314238621677985015678995395194273437072566548380233438108628431433347108913== Parameters == 
N: 4345168612223189753214327734015020835550428205948026244497988001885023245149
g: 3279682408872081559748453551150127933967213373394786941062528344533326463652
h: 1569736132337556106438262321257449765362412912066998950831042180950925860069
gx: 2981598504626674179407881346199522779264552148482577408563902859265946325680
hx: 424744822582851930363605013376094482256664168661392367593354625257431551932

== Generate NIZKP == 
c: 168886357222469079450243567177123105580
z: 8468687259225155781733973059773759736965044939978677575662810411988601824091525418475031316128645350508584215789222492535358205390299615754810819583109037

== Verify ==
Verified: true

Conclusions

Go Zero!

If you want to understand Qn — the subgroup of squares in (Z/nZ), try here:

(Z/nZ)* — the multiplicative group of Z / nZ and Qn — the subgroup of squares in (Z/nZ)*

The Decision Diffie-Hellman (DDH) assumption defines that with random values of g,h∈Qn, it is hard from g^a (mod N) and h^b (mod N), to decide if a≡b (mod 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.