Proof of Exponentiation using Wesolowski’s Theory

With zero-knowledge proofs we can implement a proof of exponentiation, and where Peggy can prove to Victor that she knows the required…

Proof of Exponentiation using Wesolowski’s Method

With zero-knowledge proofs we can implement a proof of exponentiation, and where Peggy can prove to Victor that she knows the required exponentiation. For this, we can significantly reduce the computation required, as we can define the field in which the calculations are performed in. But field we define that there are a limit number of outputs from a calculation, as we perform them with a (mod N) operation (and where the values go from 0 to N-1). The smaller the number of bits in N, the less time it will take to compute.

One method was produced by Wesolowski’s [1], and which is defined in Dan Boneh’s paper [2]:

So let’s look at the Wesolowski method and how it reduces the complexity of the zero-knowledge proof process. First, Peggy and Victor know three values u, w and x and where:

w=u^x

Peggy will prove to Victor that she still knows the values of u and x, based on a challenge. Initially, Victor generates an n-bit prime number (l) and passes it to Victor. Victor then computes a quotient and a residue of x given our n-bit prime number, with:

q=x/l

and:

x=ql+r

Victor then sends (Q) of:

Q=u^q (mod l)

Victor then computes:

r=x (mod l)

And will accept the proof if:

Q^l u^r=w

A sample of the code is:

A sample run is [here]:

Number of bits in prime:  128

Shared values:
u= 724344246685237324594883523846158072601724787874
x= 547734540830014782431283202202713039802985747397
w=u^x= 238782518159789218222694692120029338665

Victor sends a prime number: 
l= 296352719987870864011244230554561688627

Peggy computes: 
r  215487843639236261332429467563846617173
q  1848252112

Peggy sends: 
Q= 243826098549616820202795998041856248447

Victor computes:
r= 215487843639236261332429467563846617173
W= 238782518159789218222694692120029338665

Peggy has proven she knows the exponent

Conclusions

We need to change the way we prove things, such as our passwords. The method defined here does some magic and allows Peggy to prove a secret to Victor. In Wesolowski’s paper, he introduces a triple (u, w, t) that satisﬁes w = u^{2^t}.

References

[1] Benjamin Wesolowski. Eﬃcient veriﬁable delay functions. Cryptology ePrint Archive, Report 2018/623, 2018. https://eprint.iacr.org/2018/623.

[2] Boneh, D., Bünz, B., & Fisch, B. (2019, August). Batching techniques for accumulators with applications to iops and stateless blockchains. In Annual International Cryptology Conference (pp. 561–586). Springer, Cham. https://eprint.iacr.org/2018/1188.pdf