DLEQ - Non-interactive zero-knowledge (NIZK) proofs for the equality (EQ) of discrete logarithms (DL)We can use Non-interactive zero-knowledge (NIZK) proofs, and where Peggy (the 'Prover') just has to prove that she still knows her secret. For this Victor (the 'Verifier') can send Peggy a challenge, and where Peggy can prove that she can provide a solution for it. Peggy creates a secret value (\(x\)) and has two bases of \(g\) and \(h\). She then creates two values \(g^x\) and \(h^x\), and can check that \(log_{g}(g^x) == log_{h}(h^x)\). |
Some basics
Before we start, let's do some simple logarithm rules. Two basic rules that were defined by John Napier are::
\(g^x.g^y = g^{x+y} \)
\({g^x}y = g^{xy} \)
In discrete logarithms, with then perform a \(\pmod p\) operation and where \(p\) is a prime number. And so we have:
\(A = g^x.g^y \pmod p= g^{x+y} \pmod p \)
Method
We can use Non-interactive zero-knowledge (NIZK) proofs, and where Peggy (the 'Prover') just has to prove that she still knows her secret. In an interactive version, Victor (the 'Verifier') sends Peggy a challenge, and where Peggy can prove that she can provide a solution for it. In a non-interactive version, Peggy can create her own challenge. Initally, Peggy creates a secret value (\(x\)) and has two bases of \(g\) and \(h\). She then creates two values \(g^x\) and \(h^x\), and can check that \(log_{g}(g^x) == log_{h}(h^x)\). Initially Peggy creates:
\(xG=g^x \pmod p\)
\(xH=h^x \pmod p\)
Without considerable expense when the size of the prime number is large (such as for over 1,024 bits), the value of \(x\) cannot be discovered from \(g^x\) or \(h^x\). For the non-interactive proof, Peggy generates a random value (\(v\)) and computes:
\(vG=g^v \pmod p \)
\(vH=h^v \pmod p \)
\(c=Hash(vG || vH || g || h)\)
and then:
\(r=v-x.c \pmod {p-1}\)
The proof is then (\(xG, xH, r, c)\), and the values of \(g\), \(h\) and \(p\) will also be public. Victor will prove this by computing:
\(v_1=g^r . xG^c \pmod p\)
\(v_2=h^r . xH^c \pmod p\)
\(c_1=Hash(v_1 || v_2 || g || h)\)
If \(c==c_1\), the proof is valid.
This works because:
\(v_1=g^r . xG^c = g^r g^{xc} = g^{r+xc}= g^{v-xc+xc} = g^v \pmod p \)
\(v_2=h^r . xH^c = h^r h^{xc} = h^{r+xc}= h^{v-xc+xc} = h^v \pmod p\)
Over the method is based on the technique described in "Wallet Databases with Observers - David Chaum and Torben Pryds Pedersen" and defined in this [paper] here:
Outline
In the following we will use SHA-256 for the hash, and convert each of the values into byte arrays. For example we can convert \(vG\) into a byte array of bitsize/8 bytes with vG.to_bytes(bitsize//8,"big"), and where we have a big endian arrangement. The "||" operation is byte concatenate, and which is just implemented with "+" in Python:
import hashlib import sys import random import libnum p=997 def dleq(g, xG, h, xH, x) -> [int, int]: """ DLEQ... discrete logarithm equality Proof xG = G**x and xH = H**x without revealing x """ v = random.getrandbits(bitsize) %p vG = pow(g,v,p) vH = pow(h,v,p) c1=hashlib.sha256() c1.update(vG.to_bytes(bitsize//8,"big")+vH.to_bytes(bitsize//8,"big")+g.to_bytes(bitsize//8,"big")+h.to_bytes(bitsize//8,"big")) c = int.from_bytes(c1.digest(), "big") %p r = (v - x * c) % (p-1) return c, r def dleq_verify(g,xG,h,xH, c, r) -> bool: # v1 = r*G+c*xG # v2 = r*H+c*xH v1 = (pow(g,r,p)*pow(xG,c,p)) % p # v1=g^r g^(xc)= g^{r+cx} = g^{v-cx+cx}} = g^v v2 = (pow(h,r,p)*pow(xH,c,p)) %p c1=hashlib.sha256() c1.update(v1.to_bytes(bitsize//8,"big")+v2.to_bytes(bitsize//8,"big")+g.to_bytes(bitsize//8,"big")+h.to_bytes(bitsize//8,"big")) c1 = int.from_bytes(c1.digest(), "big") %p return c == c1 bitsize=128 if (len(sys.argv)>1): bitsize=int(sys.argv[1]) p=libnum.generate_prime(bitsize) x=random.getrandbits(bitsize) % p g =random.getrandbits(bitsize) % p h = random.getrandbits(bitsize) % p xG=pow(g,x,p) xH=pow(h,x,p) c,r = dleq(g,xG,h,xH,x) rtn=dleq_verify(g,xG,h,xH,c,r) print("== DLEQ (with discrete logs) ===") print(f"Secret: {x}") print(f"p: {p}") print(f"\ng {g}\nh {h}") print(f"g^x {xG}\nh^x {xH}") print(f"\nr {r}\nc {c}") print(f"Proven {rtn}") xG = 2*g rtn=dleq_verify(g,xG,h,xH,c,r) print(f"\nNow trying with incorrect proof") print(f"Proven {rtn}")
A sample run for 64-bit primes:
== DLEQ === Secret: 8226441489057554051 p: 14312102784525063139 g 1432205245299627649 h 1058739418500529656 g^x 7369471065254115060 h^x 6372925570753712066 r 4550682446127323237 c 5831082032206369735 Proven True Now trying with incorrect proof Proven False
and for 512-bit primes:
== DLEQ === Secret: 4485923188924488412770095380084849302359769199219096921170805950233341673039507161998488923082887225958486548919069894042865192224684466800184387418144578 p: 10230815590986016812047309420680505393360441133418520160704811548022578456158580345721760786630989892998747886706490392737716774229655732916369444120480187 g 7929877076908562502316486448368602866215898966493039131680085215597578644481201738567710044283149594248296095486527916650843450010811632410794845598912745 h 1381406091123889617542991225438794380465883840037416312798346438002064792574539898627890768749394931716046279784580490628368171280639918054321448689664433 g^x 2973733723359334947565285084278690365837720254903897779894080144528129155486503303461212284682135822682572314528337823319340443631638156598275813982940222 h^x 1890122968958225767129143110782554241532636340757736170130650192038155592188639366093084038642150642798077442715613551026445162669168485502155742328468755 r 2635232827407747635198519416549648131317415797442254037983046372285289997593843768207483238960999153029489818189173613905695172543688810022597278409695679 c 51564139126147450624294160277058132351029000945450970191196652769905165621350 Proven True Now trying with incorrect proof Proven False