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.

Number of bits in prime:  128Shared 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 satisfies w = u^{2^t}.

References

[1] Benjamin Wesolowski. Efficient verifiable delay functions. Cryptology ePrint Archive, Report 2018/623, 2018. https://eprint.iacr.org/2018/623.

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