Image for post
Image for post
Photo by Austin Distel on Unsplash

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

Image for post
Image for post

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

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 satisfies w = u^{2^t}.

Image for post
Image for post

References

[1] Benjamin Wesolowski. Efficient verifiable 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

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store