A Survey of Two Verifiable Delay Functions Using Proof of Exponentiation
Authors
Dan Boneh, Benedikt Bünz, Ben Fisch
Dan Boneh
Stanford University, Stanford, U.S.A
dabo at cs dot stanford dot edu
dabo at cs dot stanford dot edu
Benedikt Bünz
New York University, New York, U.S.A
bbuenz at gmail dot com
bbuenz at gmail dot com
Ben Fisch
Yale University, New Haven, U.S.A
benafisch at gmail dot com
benafisch at gmail dot com
Abstract
A verifiable delay function (VDF) is an important tool used for adding delay in decentralized applications. This paper surveys and compares two beautiful verifiable delay functions, one due to Pietrzak, and the other due to Wesolowski, In addition, we provide a new computational proof of security for one of them, present an attack on an incorrect implementation of the other, and compare the complexity assumptions needed for both schemes.
References
[AFK23]
Thomas Attema, Serge Fehr, and Michael Klooß.
Fiat-shamir transformation of multi-round interactive proofs (extended version).
Journal of Cryptology, 36(4):36, October 2023.
https://doi.org/10.1007/s00145-023-09478-y.
[AGL+23]
Arasu Arun, Chaya Ganesh, Satya V. Lokam, Tushar Mopuri, and Sriram Sridhar.
Dew: A transparent constant-sized polynomial commitment scheme.
In Alexandra Boldyreva and Vladimir Kolesnikov, editors, PKC 2023: 26th International Conference on Theory and Practice of Public Key Cryptography, Part II, volume 13941 of Lecture Notes in Computer Science, 542–571. May 2023. Springer, Heidelberg.
https://doi.org/10.1007/978-3-031-31371-4_19.
[AVD22]
Vidal Attias, Luigi Vigneri, and Vassil Dimitrov.
Efficient verification of the wesolowski verifiable delay function for distributed environments.
2022.
[AZ23]
Knud Ahrens and Jens Zumbrägel.
DEFEND: towards verifiable delay functions from endomorphism rings.
IACR Cryptol. ePrint Arch., pages 1537, 2023.
[BBBF18]
Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch.
Verifiable delay functions.
In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part I, volume 10991 of Lecture Notes in Computer Science, 757–788. August 2018. Springer, Heidelberg.
https://doi.org/10.1007/978-3-319-96884-1_25.
[BBF19]
Dan Boneh, Benedikt Bünz, and Ben Fisch.
Batching techniques for accumulators with applications to IOPs and stateless blockchains.
In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, Part I, volume 11692 of Lecture Notes in Computer Science, 561–586. August 2019. Springer, Heidelberg.
https://doi.org/10.1007/978-3-030-26948-7_20.
[BFS20]
Benedikt Bünz, Ben Fisch, and Alan Szepieniec.
Transparent SNARKs from DARK compilers.
In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part I, volume 12105 of Lecture Notes in Computer Science, 677–706. May 2020. Springer, Heidelberg.
https://doi.org/10.1007/978-3-030-45721-1_24.
[BGJ+16]
Nir Bitansky, Shafi Goldwasser, Abhishek Jain, Omer Paneth, Vinod Vaikuntanathan, and Brent Waters.
Time-lock puzzles from randomized encodings.
In Madhu Sudan, editor, ITCS 2016: 7th Conference on Innovations in Theoretical Computer Science, 345–356. January 2016. Association for Computing Machinery.
https://doi.org/10.1145/2840728.2840745.
[BH01]
Johannes Buchmann and Safuat Hamdy.
A survey on IQ cryptography.
In Public-Key Cryptography and Computational Number Theory, 1–15. 2001.
https://doi.org/10.1515/9783110881035.1.
[BHR+21]
Alexander R. Block, Justin Holmgren, Alon Rosen, Ron D. Rothblum, and Pratik Soni.
Time- and space-efficient arguments from groups of unknown order.
In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part IV, volume 12828 of Lecture Notes in Computer Science, 123–152. Virtual Event, August 2021. Springer, Heidelberg.
https://doi.org/10.1007/978-3-030-84259-8_5.
[BKSW20]
Karim Belabas, Thorsten Kleinjung, Antonio Sanso, and Benjamin Wesolowski.
A note on the low order assumption in class group of an imaginary quadratic number fields.
2020.
[BN06]
Mihir Bellare and Gregory Neven.
Multi-signatures in the plain public-key model and a general forking lemma.
In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, ACM CCS 2006: 13th Conference on Computer and Communications Security, 390–399. October / November 2006. ACM Press.
https://doi.org/10.1145/1180405.1180453.
[BN22]
Joseph Bonneau and Valeria Nikolaenko.
Public randomness and randomness beacons.
2022.
[BS22]
Dan Boneh and Victor Shoup.
A graduate course in applied cryptography, version 0.6.
Cambridge, 2022.
[But18]
Vitalik Buterin.
STARKs, part 3: into the weeds.
2018.
[CL84]
Henri Cohen and Hendrik W Lenstra.
Heuristics on class groups of number fields.
In Number Theory Noordwijkerhout 1983, pages 33–62.
Springer, 1984.
[CLR24]
Kostas Kryptos Chalkias, Jonas Lindstrøm, and Arnab Roy.
An efficient hash function for imaginary class groups.
2024.
[Cop97]
Don Coppersmith.
Small solutions to polynomial equations, and low exponent RSA vulnerabilities.
Journal of Cryptology, 10(4):233–260, September 1997.
https://doi.org/10.1007/s001459900030.
[CP18]
Bram Cohen and Krzysztof Pietrzak.
Simple proofs of sequential work.
In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, Part II, volume 10821 of Lecture Notes in Computer Science, 451–467. April / May 2018. Springer, Heidelberg.
https://doi.org/10.1007/978-3-319-78375-8_15.
[DGMV20]
Nico Döttling, Sanjam Garg, Giulio Malavolta, and Prashant Nalini Vasudevan.
Tight verifiable delay functions.
In Clemente Galdi and Vladimir Kolesnikov, editors, SCN 20: 12th International Conference on Security in Communication Networks, volume 12238 of Lecture Notes in Computer Science, 65–84. September 2020. Springer, Heidelberg.
https://doi.org/10.1007/978-3-030-57990-6_4.
[DMPS19]
Luca De Feo, Simon Masson, Christophe Petit, and Antonio Sanso.
Verifiable delay functions from supersingular isogenies and pairings.
In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology – ASIACRYPT 2019, Part I, volume 11921 of Lecture Notes in Computer Science, 248–277. December 2019. Springer, Heidelberg.
https://doi.org/10.1007/978-3-030-34578-5_10.
[EV07]
Jordan Ellenberg and Akshay Venkatesh.
Reflection principles and bounds for class group torsion.
International Mathematics Research Notices, 2007.
https://doi.org/10.1093/imrn/rnm002.
[FS87]
Amos Fiat and Adi Shamir.
How to prove yourself: Practical solutions to identification and signature problems.
In Andrew M. Odlyzko, editor, Advances in Cryptology – CRYPTO'86, volume 263 of Lecture Notes in Computer Science, 186–194. August 1987. Springer, Heidelberg.
https://doi.org/10.1007/3-540-47721-7_12.
[HHK+22]
Charlotte Hoffmann, Pavel Hubácek, Chethan Kamath, Karen Klein, and Krzysztof Pietrzak.
Practical statistically-sound proofs of exponentiation in any group.
In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, Part II, volume 13508 of Lecture Notes in Computer Science, 370–399. August 2022. Springer, Heidelberg.
https://doi.org/10.1007/978-3-031-15979-4_13.
[JMRR21]
Samuel Jaques, Hart Montgomery, Razvan Rosie, and Arnab Roy.
Time-release cryptography from minimal circuit assumptions.
In Progress in Cryptology – INDOCRYPT 2021, volume 13143 of Lecture Notes in Computer Science, 584–606. Springer, 2021.
https://doi.org/10.1007/978-3-030-92518-5_26.
[KMT22]
Dmitry Khovratovich, Mary Maller, and Pratyush Ranjan Tiwari.
MinRoot: candidate sequential function for ethereum VDF.
2022.
[LM19]
Russell W. F. Lai and Giulio Malavolta.
Subvector commitments with application to succinct arguments.
In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, Part I, volume 11692 of Lecture Notes in Computer Science, 530–560. August 2019. Springer, Heidelberg.
https://doi.org/10.1007/978-3-030-26948-7_19.
[LMPR23]
Gaëtan Leurent, Bart Mennink, Krzysztof Pietrzak, and Vincent Rijmen.
Analysis of MinRoot: public report.
2023.
[LW17]
Arjen K Lenstra and Benjamin Wesolowski.
Trustworthy public randomness with sloth, unicorn, and trx.
International Journal of Applied Cryptography, 3(4):330–343, 2017.
https://doi.org/10.1504/IJACT.2017.089354.
[Mao01]
Wenbo Mao.
Timed-release cryptography.
In Serge Vaudenay and Amr M. Youssef, editors, SAC 2001: 8th Annual International Workshop on Selected Areas in Cryptography, volume 2259 of Lecture Notes in Computer Science, 342–358. August 2001. Springer, Heidelberg.
https://doi.org/10.1007/3-540-45537-X_27.
[MLQ23]
Liam Medley, Angelique Faye Loe, and Elizabeth A. Quaglia.
SoK: delay-based cryptography.
In CSF 2023: IEEE 36th Computer Security Foundations Symposium, 169–183. July 2023. IEEE Computer Society Press.
https://doi.org/10.1109/CSF57540.2023.00028.
[MSW20]
Mohammad Mahmoody, Caleb Smith, and David J. Wu.
Can verifiable delay functions be based on random oracles?
In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, ICALP 2020: 47th International Colloquium on Automata, Languages and Programming, volume 168 of LIPIcs, 83:1–83:17. July 2020. Schloss Dagstuhl.
https://doi.org/10.4230/LIPIcs.ICALP.2020.83.
[Pie19]
Krzysztof Pietrzak.
Simple verifiable delay functions.
In Avrim Blum, editor, ITCS 2019: 10th Innovations in Theoretical Computer Science Conference, volume 124, 60:1–60:15. January 2019. LIPIcs.
https://doi.org/10.4230/LIPIcs.ITCS.2019.60.
[RS20]
Lior Rotem and Gil Segev.
Generically speeding-up repeated squaring is equivalent to factoring: sharp thresholds for all generic-ring delay functions.
In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, Part III, volume 12172 of Lecture Notes in Computer Science, 481–509. August 2020. Springer, Heidelberg.
https://doi.org/10.1007/978-3-030-56877-1_17.
[RSW96]
Ronald Rivest, Adi Shamir, and David Wagner.
Time-lock puzzles and timed-release crypto.
1996.
[SB20]
István András Seres and Péter Burcsi.
A note on low order assumptions in RSA groups.
2020.
[SBK24]
István András Seres, Péter Burcsi, and Péter Kutas.
How (not) to hash into class groups of imaginary quadratic fields?
2024.
[Sha69]
Daniel Shanks.
Class number, a theory of factorization, and genera.
In Proc. Sympos. Pure Math., volume 29, 415–440. Amer. Math. Soc., 1969.
https://doi.org/10.1090/pspum/020/0316385.
[Sha19]
Barak Shani.
A note on isogeny-based hybrid verifiable delay functions.
2019.
[TSL+23]
Teik Guan Tan, Vishal Sharma, Zengpeng Li, Pawel Szalachowski, and Jianying Zhou.
ZKBdf: a ZKBoo-based quantum-secure verifiable delay function with prover-secret.
In Applied Cryptography and Network Security Workshops – ACNS satellite workshops 2023, volume 13907 of Lecture Notes in Computer Science, 530–550. Springer, 2023.
https://doi.org/10.1007/978-3-031-41181-6_29.
[Wes19]
Benjamin Wesolowski.
Efficient verifiable delay functions.
In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, Part III, volume 11478 of Lecture Notes in Computer Science, 379–407. May 2019. Springer, Heidelberg.
https://doi.org/10.1007/978-3-030-17659-4_13.
[Wes20]
Benjamin Wesolowski.
Efficient verifiable delay functions.
Journal of Cryptology, 33(4):2113–2147, October 2020.
https://doi.org/10.1007/s00145-020-09364-x.
PDF
History
Submitted: 2024-01-08
Accepted: 2024-03-05
Published: 2024-04-09
Accepted: 2024-03-05
Published: 2024-04-09
How to cite
Dan Boneh, Benedikt Bünz, and Ben Fisch, A Survey of Two Verifiable Delay Functions Using Proof of Exponentiation. IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/av7tudhdj.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.