Article

Continuous Verifiable Delay Functions

Authors:

Ilan Komargodski,

Rafael PassAuthors Info & Claims

Advances in Cryptology – EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part III

Pages 125 - 154

https://doi.org/10.1007/978-3-030-45727-3_5

Published: 10 May 2020 Publication History

Abstract

We introduce the notion of a continuous verifiable delay function (cVDF): a function g which is (a) iteratively sequential—meaning that evaluating the iteration of g (on a random input) takes time roughly t times the time to evaluate g, even with many parallel processors, and (b) (iteratively) verifiable—the output of can be efficiently verified (in time that is essentially independent of t). In other words, the iterated function is a verifiable delay function (VDF) (Boneh et al., CRYPTO ’18), having the property that intermediate steps of the computation (i.e., for ) are publicly and continuously verifiable.

We demonstrate that cVDFs have intriguing applications: (a) they can be used to construct that only require an initial random seed (and no further unpredictable sources of randomness), (b) enable where any part of the VDF computation can be verifiably outsourced, and (c) have deep complexity-theoretic consequences: in particular, they imply the existence of depth-robust moderately-hard Nash equilibrium problem instances, i.e. instances that can be solved in polynomial time yet require a high sequential running time.

Our main result is the construction of a cVDF based on the repeated squaring assumption and the soundness of the Fiat-Shamir (FS) heuristic for . We highlight that when viewed as a (plain) VDF, our construction requires a weaker FS assumption than previous ones (earlier constructions require the FS heuristic for either super-logarithmic round proofs, or for arguments).

References

[1]

Chia network. https://chia.net/. Accessed 17 May 2019

[2]

Ethereum foundation. https://www.ethereum.org/. Accessed 17 May 2019

[3]

Protocol labs. https://protocol.ai/. Accessed 17 May 2019

[4]

VDF research effort. https://vdfresearch.org/. Accessed 17 May 2019

[5]

Abbot, T., Kane, D., Valiant, P.: On algorithms for Nash equilibria (2004). http://web.mit.edu/tabbott/Public/final.pdf. Accessed 18 Sept 2019

[6]

Barak, B.: How to go beyond the black-box simulation barrier. In: 42nd IEEE Symposium on Foundations of Computer Science, FOCS, pp. 106–115 (2001)

[7]

Bennett CH Time/space trade-offs for reversible computation SIAM J. Comput. 1989 18 4 766-776

[8]

Bitansky, N., Goldwasser, S., Jain, A., Paneth, O., Vaikuntanathan, V., Waters, B.: Time-lock puzzles from randomized encodings. In: Innovations in Theoretical Computer Science, ITCS, pp. 345–356 (2016)

[9]

Bitansky, N., Paneth, O., Rosen, A.: On the cryptographic hardness of finding a Nash equilibrium. In: Guruswami, V. (ed.) IEEE 56th Symposium on Foundations of Computer Science, FOCS, pp. 1480–1498 (2015)

[10]

Boneh D, Bonneau J, Bünz B, and Fisch B Shacham H and Boldyreva A Verifiable delay functions Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 757-788

[11]

Boneh, D., Bünz, B., Fisch, B.: A survey of two verifiable delay functions. IACR Cryptology ePrint Archive 2018, 712 (2018)

[12]

Boneh D and Naor M Bellare M Timed commitments Advances in Cryptology — CRYPTO 2000 2000 Heidelberg Springer 236-254

[13]

Cai, J., Lipton, R.J., Sedgewick, R., Yao, A.C.: Towards uncheatable benchmarks. In: 8th Structure in Complexity Theory Conference, pp. 2–11. IEEE Computer Society (1993)

[14]

Chen X, Deng X, and Teng S Settling the complexity of computing two-player Nash equilibria J. ACM 2009 56 3 14:1-14:57

[15]

Choudhuri, A.R., Hubáček, P., Kamath, C., Pietrzak, K., Rosen, A., Rothblum, G.N.: Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In: 51st ACM SIGACT Symposium on Theory of Computing, STOC, pp. 1103–1114 (2019)

[16]

Choudhuri, A.R., Hubáček, P., Kamath, C., Pietrzak, K., Rosen, A., Rothblum, G.N.: PPAD-hardness via iterated squaring modulo a composite. IACR Cryptology ePrint Archive 2019, 667 (2019)

[17]

Chung, K., Lin, H., Pass, R.: Constant-round concurrent zero knowledge from P-certificates. In: 54th IEEE Symposium on Foundations of Computer Science, FOCS, pp. 50–59 (2013)

[18]

Cohen B and Pietrzak K Nielsen JB and Rijmen V Simple proofs of sequential work Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 451-467

[19]

Daskalakis C, Goldberg PW, and Papadimitriou CH The complexity of computing a Nash equilibrium Commun. ACM 2009 52 2 89-97

[20]

Döttling, N., Garg, S., Malavolta, G., Vasudevan, P.N.: Tight verifiable delay functions. IACR Cryptology ePrint Archive 2019, 659 (2019)

[21]

Döttling N, Lai RWF, and Malavolta G Ishai Y and Rijmen V Incremental proofs of sequential work Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 292-323

[22]

Dwork C and Naor M Brickell EF Pricing via processing or combatting junk mail Advances in Cryptology — CRYPTO 1992 1993 Heidelberg Springer 139-147

[23]

De Feo, L., Masson, S., Petit, C., Sanso, A.: Verifiable delay functions from supersingular isogenies and pairings. IACR Cryptology ePrint Archive 2019, 166 (2019)

[24]

Fiat A and Shamir A Odlyzko AM How to prove yourself: practical solutions to identification and signature problems Advances in Cryptology — CRYPTO 1986 1987 Heidelberg Springer 186-194

[25]

Garg S, Pandey O, and Srinivasan A Robshaw M and Katz J Revisiting the cryptographic hardness of finding a nash equilibrium Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 579-604

[26]

Goldreich O and Krawczyk H Paterson MS On the composition of zero-knowledge proof systems Automata, Languages and Programming 1990 Heidelberg Springer 268-282

[27]

Goldwasser, S., Kalai, Y.T.: On the (in)security of the Fiat-Shamir paradigm. In: 44th IEEE Symposium on Foundations of Computer Science, FOCS, pp. 102–113 (2003)

[28]

Hubáček, P., Yogev, E.: Hardness of continuous local search: query complexity and cryptographic lower bounds. In: 28th ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1352–1371 (2017)

[29]

Jerschow, Y.I., Mauve, M.: Non-parallelizable and non-interactive client puzzles from modular square roots. In: 6th International Conference on Availability, Reliability and Security, ARES1, pp. 135–142. IEEE Computer Society (2011)

[30]

Kaliski, B.: PKCS #5: password-based cryptography specification version 2.0 (2000)

[31]

Kitagawa F, Nishimaki R, and Tanaka K Nielsen JB and Rijmen V Obfustopia built on secret-key functional encryption Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 603-648

[32]

Komargodski I and Segev G Coron J-S and Nielsen JB From Minicrypt to Obfustopia via private-key functional encryption Advances in Cryptology – EUROCRYPT 2017 2017 Cham Springer 122-151

[33]

Lenstra AK and Wesolowski B Trustworthy public randomness with sloth, unicorn, and trx IJACT 2017 3 4 330-343

[34]

Lin, H., Pass, R., Soni, P.: Two-round and non-interactive concurrent non-malleable commitments from time-lock puzzles. In: 58th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 576–587 (2017)

[35]

Lund C, Fortnow L, Karloff HJ, and Nisan N Algebraic methods for interactive proof systems J. ACM 1992 39 4 859-868

[36]

Mahmoody, M., Moran, T., Vadhan, S.P.: Publicly verifiable proofs of sequential work. In: Innovations in Theoretical Computer Science, ITCS, pp. 373–388 (2013)

[37]

Mahmoody, M., Smith, C., Wu, D.J.: A note on the (im)possibility of verifiable delay functions in the random oracle model. ePrint p. 663 (2019)

[38]

Megiddo N and Papadimitriou CH On total functions, existence theorems and computational complexity Theor. Comput. Sci. 1991 81 2 317-324

[39]

Papadimitriou CH On the complexity of the parity argument and other inefficient proofs of existence J. Comput. Syst. Sci. 1994 48 3 498-532

[40]

Pietrzak, K.: Simple verifiable delay functions. In: 10th Innovations in Theoretical Computer Science Conference, ITCS, pp. 60:1–60:15 (2019)

[41]

Rabin, M.O.: Digitalized signatures and public key functions as intractable as factoring. Technical report, TR-212, LCS, MIT, Cambridge, MA (1979)

[42]

Rabin MO Transaction protection by beacons J. Comput. Syst. Sci. 1983 27 2 256-267

[43]

Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto (1996, manuscript)

[44]

Valiant P Canetti R Incrementally verifiable computation or proofs of knowledge imply time/space efficiency Theory of Cryptography 2008 Heidelberg Springer 1-18

[45]

Wesolowski B Ishai Y and Rijmen V Efficient verifiable delay functions Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 379-407

[46]

Zhandry M Robshaw M and Katz J The magic of ELFs Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 479-508

Cited By

Choudhuri AGoel AHegde AJain A(2024)Homomorphic Secret Sharing with Verifiable EvaluationTheory of Cryptography10.1007/978-3-031-78023-3_20(614-650)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78023-3_20
Zawia AHasan M(2024)ChronoCloak: An Integrated Solution for Mitigating Premature Disclosure in Oblivious Digital DisseminationInformation Security10.1007/978-3-031-75757-0_12(232-251)Online publication date: 24-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-75757-0_12
Baum CDavid BPagnin ETakahashi A(2024)CaSCaDE: (Time-Based) Cryptography from Space Communications DElaySecurity and Cryptography for Networks10.1007/978-3-031-71070-4_12(252-274)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71070-4_12
Show More Cited By

Index Terms

Continuous Verifiable Delay Functions
1. Security and privacy
  1. Cryptography
2. Theory of computation
  1. Computational complexity and cryptography
  2. Design and analysis of algorithms

Index terms have been assigned to the content through auto-classification.

Recommendations

Efficient Verifiable Delay Functions
Abstract
We construct a verifiable delay function (VDF). A VDF is a function whose evaluation requires running a given number of sequential steps, yet the result can be efficiently verified. They have applications in decentralised systems, such as the ...
Verifiable Random Functions: Relations to Identity-Based Key Encapsulation and New Constructions

In this paper we show a relation between the notions of verifiable random functions (VRFs) and identity-based key encapsulation mechanisms (IB-KEMs). In particular, we propose a class of IB-KEMs that we call VRF-suitable, and we propose a direct ...
Publicly verifiable ciphertexts
Advances in Security for Communication Networks

In many applications where encrypted traffic flows from an open public domain to a protected private domain there exists a gateway that bridges these two worlds, faithfully forwarding all incoming traffic to the receiver. We observe that the notion of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Advances in Cryptology – EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part III

May 2020

822 pages

ISBN:978-3-030-45726-6

DOI:10.1007/978-3-030-45727-3

Editors:
Anne Canteaut
Équipe-projet COSMIQ, Inria, Paris, France
,
Yuval Ishai
Computer Science Department, Technion, Haifa, Israel

© International Association for Cryptologic Research 2020.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 10 May 2020

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Choudhuri AGoel AHegde AJain A(2024)Homomorphic Secret Sharing with Verifiable EvaluationTheory of Cryptography10.1007/978-3-031-78023-3_20(614-650)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78023-3_20
Zawia AHasan M(2024)ChronoCloak: An Integrated Solution for Mitigating Premature Disclosure in Oblivious Digital DisseminationInformation Security10.1007/978-3-031-75757-0_12(232-251)Online publication date: 24-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-75757-0_12
Baum CDavid BPagnin ETakahashi A(2024)CaSCaDE: (Time-Based) Cryptography from Space Communications DElaySecurity and Cryptography for Networks10.1007/978-3-031-71070-4_12(252-274)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71070-4_12
Ng LChatzigiannis PLe DMinaei MKumaresan RZamani M(2024)A Plug-and-Play Long-Range Defense System for Proof-of-Stake BlockchainsComputer Security – ESORICS 202410.1007/978-3-031-70903-6_3(45-64)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70903-6_3
Chia NChung KHsieh YLin HLin YShen Y(2023)On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian SimulationProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.33(1-45)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.33
Hoffmann CHubáček PKamath CKrňák T(2023)(Verifiable) Delay Functions from Lucas SequencesTheory of Cryptography10.1007/978-3-031-48624-1_13(336-362)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48624-1_13
Tan TSharma VLi ZSzalachowski PZhou J(2023)ZKBdf: A ZKBoo-Based Quantum-Secure Verifiable Delay Function with Prover-SecretApplied Cryptography and Network Security Workshops10.1007/978-3-031-41181-6_29(530-550)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-41181-6_29
Baum CDavid BDowsley RKishore RNielsen JOechsner S(2023)CRAFT: Composable Randomness Beacons and Output-Independent Abort MPC From TimePublic-Key Cryptography – PKC 202310.1007/978-3-031-31368-4_16(439-470)Online publication date: 7-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-31368-4_16
Abusalah HCini V(2023)An Incremental PoSW for General Weight DistributionsAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30617-4_10(282-311)Online publication date: 23-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30617-4_10
Han RYu JZhang RHerlihy MNarula N(2022)Analysing and Improving Shard Allocation Protocols for Sharded BlockchainsProceedings of the 4th ACM Conference on Advances in Financial Technologies10.1145/3558535.3559783(198-216)Online publication date: 19-Sep-2022
https://dl.acm.org/doi/10.1145/3558535.3559783
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten