With zero-knowledge proofs we can implement a proof of exponentiation, and where Peggy can prove to Victor that she knows the required exponentiation. One method was produced by Wesolowski [1].
Proof of Exponent (Wesolowski theory) |
Theory
With zero-knowledge proofs we can implement a proof of exponentiation, and where Peggy can prove to Victor that she knows the required exponentiation. One method was produced by Wesolowski [1]. In this case, Peggy and Victor know three values \(u, w\) and \(x\) and where Peggy must prove that she still knows the value of:
\(w=u^x\)
Peggy will prove to Victor that she still knows the values of \(u\) and \(x\), based on a challenge. Intially Victor generates an \(n\)-bit prime number (\(\ell\)) and passes it to Victor. Victor then computes a quotient and an residue with:
\(q = \frac{x}{\ell}\)
and:
\(x = q \ell + r\)
Victor then sends (\(Q\)) of:
\(Q=u^q\)
Victor then computes:
\(r = x \pmod \ell\)
And will accept the proof if:
\(Q^{\ell} u^r = w\)
Some sample code is:
from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes import random bits=128 l = getPrime(bits, randfunc=get_random_bytes) # Let's have 256-bit secrets: u=random.getrandbits(256) x=random.getrandbits(256) w = pow(u,x,l) # w=u^x print ("Number of bits in prime: ",bits) print ("\nShared values:") print ("u=",u) print ("x=",x) print ("w=u^x=",w) print ("\nVictor sends a prime number: ") print ("l=",l) # Calculate quotient and remainder given the field defined by l q = x // l r=(x-q*l) % l print ("\nPeggy computes: ") print ("r ",r) print ("q ",q) Q = pow(u,q,l) print ("\nPeggy sends: ") print ("Q=",Q) print ("\nVictor computes:") r = x % l val = (pow(Q,l,l)*pow(u,r,l)) % l print ("r=",r) print ("W=",val) if (val==w): print ("\nPeggy has proven she knows the exponent") else: print ("\nPeggy has not proven!")
A sample run is for a 50-bit prime is:
Number of bits in prime: 40 Shared values: u= 747928275865920789256262220304502983888458002668 x= 313565762925725881639612239834454289063265823890 w=u^x= 433673225066 Victor sends a prime number: l= 1027609977899 Peggy computes: r 286526565143 q 305140831316981534411129837053779953 Peggy sends: Q= 169278881060 Victor computes: r= 286526565143 W= 433673225066 Peggy has proven she knows the exponent
and for a 128-bit prime:
Number of bits in prime: 128 Shared values: u= 871099049751051030108191308808675033057999611672 x= 185871529540445608195483850035176276960561236304 w=u^x= 274775912440089851853630671795286921121 Victor sends a prime number: l= 297430982894651276354747757132230733199 Peggy computes: r 197569314430857361231838138593496856330 q 624923226 Peggy sends: Q= 253549519259347024546961723016442617103 Victor computes: r= 197569314430857361231838138593496856330 W= 274775912440089851853630671795286921121 Peggy has proven she knows the exponent
Reference
[1] Benjamin Wesolowski. Efficient verifiable delay functions. Cryptology ePrint Archive, Report 2018/623, 2018. [here].