[en] Verifiable Delay Functions (VDF) are a class of cryptographic primitives aiming to guarantee a minimum computation time, even for an adversary with massive parallel computational power. They are useful in blockchain protocols, and several practical candidates have been proposed based on exponentiation in a large finite field: Sloth++, Veedo, MinRoot. The underlying assumption of these constructions is that computing an exponentiation xe requires at least log2e sequential multiplications. In this work, we analyze the security of these algebraic VDF candidates. In particular, we show that the latency of exponentiation can be reduced using parallel computation, against the preliminary assumptions.
Research center :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > CryptoLUX – Cryptography NCER-FT - FinTech National Centre of Excellence in Research
Disciplines :
Computer science
Author, co-author :
BIRYUKOV, Alexei ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS) ; Unilu - University of Luxembourg [LU] > Interdisciplinary Centre for Security, Reliability and Trust > Cryptolux
Fisch, Ben; Yale University, New Haven, United States
Ga\u00EBtan Leurent is supported by project Cryptanalyse from\u00A0PEPR Cybers\u00E9curit\u00E9 (22-PECY-0010). Alex Biryukov was funded in part by the Luxembourg National Research Fund (FNR), project CryptoFin C22/IS/17415825.
Commentary :
New Frontiers of Digital and Automated Finance; Trust and Security
Adleman, L.M.: A subexponential algorithm for the discrete logarithm problem with applications to cryptography (abstract). In: 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29-31 October 1979, pp. 55–60. IEEE Computer Society (1979). https://doi.org/10.1109/SFCS.1979.2
Adleman, L.M., Kompella, K.: Using smoothness to achieve parallelism (abstract). In: 20th ACM STOC, pp. 528–538. ACM Press (May 1988). https://doi.org/10.1145/62212.62264
Adrian, D., et al.: Imperfect forward secrecy: How Diffie-Hellman fails in practice. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015, pp. 5–17. ACM Press (Oct 2015). https://doi.org/10.1145/2810103.2813707
Ahrens, K., Zumbrägel, J.: DEFEND: towards verifiable delay functions from endomorphism rings. In: IACR Cryptol. ePrint Arch, p. 1537 (2023). https://eprint.iacr.org/2023/1537
Arun, A., Bonneau, J., Clark, J.: Short-lived Zero-Knowledge Proofs and Signatures. In: Agrawal, S., Lin, D. (eds.) Advances in Cryptology – ASIACRYPT 2022: 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5–9, 2022, Proceedings, Part III, pp. 487–516. Springer Nature Switzerland, Cham (2022). https://doi.org/10.1007/978-3-031-22969-5_17
Atabaki, A.H., et al.: Integrating photonics with silicon nanoelectronics for the next generation of systems on a chip. Nature 556(7701), 349–354 (2018). https://doi.org/10.1038/s41586-018-0028-z
Bach, E.: How to generate factored random numbers. SIAM J. Comput. 17(2), 179–193 (1988). https://doi.org/10.1137/0217012
Barrett, P.: Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 311–323. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_24
Biryukov, A., et al.: Cryptanalysis of algebraic verifiable delay functions. Cryptology ePrint Archive (2024), full version
Blum, M.: Coin flipping by telephone. In: Proceedings of the IEEE Spring COMPCOM, pp. 133–137 (1982)
Boneh, D., Bonneau, J., Bünz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology – CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part I, pp. 757–788. Springer International Publishing, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_25
Boneh, D., Franklin, M.K.: Efficient generation of shared RSA keys (extended abstract). In: Kaliski Jr., B.S. (ed.) CRYPTO’97. LNCS, vol. 1294, pp. 425–439. Springer, Heidelberg (Aug 1997). https://doi.org/10.1007/BFb0052253
Brent, R.P., Kung, H.T.: A regular layout for parallel adders. IEEE Trans. Comput. 31(3), 260–264 (1982). https://doi.org/10.1109/TC.1982.1675982
Brent, R.P., Rung, H.: A systolic algorithm for integer GCD computation. In: 1985 IEEE 7th Symposium on Computer Arithmetic (ARITH), pp. 118–125. IEEE (1985)
Chen, M., et al.: Multiparty generation of an RSA modulus. In: Micciancio, D., Ristenpart, T. (eds.) Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part III, pp. 64–93. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_3
Cline, D., Dryja, T., Narula, N., CommitO: Clockwork: An exchange protocol for proofs of non front-running (2020)
Coppersmith, D., Shparlinski, I.: On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping. J. Cryptol. 13, 339–360 (2000)
De Feo, L., Masson, S., Petit, C., Sanso, A.: Verifiable delay functions from supersingular isogenies and pairings. In: Galbraith, S.D., Moriai, S. (eds.) Advances in Cryptology – ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8–12, 2019, Proceedings, Part I, pp. 248–277. Springer International Publishing, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_10
Deb, S., Kannan, S., Tse, D.: PoSAT: proof-of-work availability and unpredictability, without the work. In: Borisov, N., Diaz, C. (eds.) Financial Cryptography and Data Security: 25th International Conference, FC 2021, Virtual Event, March 1–5, 2021, Revised Selected Papers, Part II, pp. 104–128. Springer Berlin Heidelberg, Berlin, Heidelberg (2021). https://doi.org/10.1007/978-3-662-64331-0_6
Dickman, K.: On the frequency of numbers containing prime factors of a certain relative magnitude. Arkiv for matematik, astronomi och fysik 22(10), A–10 (1930)
Fisch, B.: Tight proofs of space and replication. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 324–348. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_12
Gordon, D.M.: Discrete logarithms in GF(P) using the number field sieve. SIAM J. Discret. Math. 6(1), 124–138 (1993). https://doi.org/10.1137/0406010
Hazay, C., Mikkelsen, G.L., Rabin, T., Toft, T., Nicolosi, A.A.: Efficient RSA key generation and threshold paillier in the two-party setting. J. Cryptol. 32(2), 265–323 (Apr2019). https://doi.org/10.1007/s00145-017-9275-7
Herold, G., et al.: Statement regarding the public report on the analysis of minroot. https://ethresear.ch/t/statement-regarding-the-public-report-on-the-analysis-of-minroot/16670 (Sep 2023)
Khovratovich, D., Maller, M., Tiwari, P.R.: MinRoot: Candidate sequential function for ethereum VDF. Cryptology ePrint Archive, Report 2022/1626 (2022). https://eprint.iacr.org/2022/1626
Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: a provably secure proof-of-stake blockchain protocol. In: Katz, J., Shacham, H. (eds.) Advances in Cryptology – CRYPTO 2017: 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part I, pp. 357–388. Springer International Publishing, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_12
Kothapalli, A., Setty, S., Tzialla, I.: Nova: recursive zero-knowledge arguments from folding schemes. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology – CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part IV, pp. 359–388. Springer Nature Switzerland, Cham (2022). https://doi.org/10.1007/978-3-031-15985-5_13
Lenstra, A.K., Wesolowski, B.: A random zoo: sloth, unicorn, and trx. Cryptology ePrint Archive, Report 2015/366 (2015). https://eprint.iacr.org/2015/366
Lenstra, A.K., Wesolowski, B.: Trustworthy public randomness with sloth, unicorn, and trx. Int. J. Appl. Cryptogr. 3(4), 330–343 (2017) https://doi.org/10.1504/IJACT.2017.10010315
Lenstra, H.W.: Factoring integers with elliptic curves. Ann. Math. 126(3), 649–673 (1987). http://www.jstor.org/stable/1971363
Mahmoody, M., Moran, T., Vadhan, S.P.: Publicly verifiable proofs of sequential work. In: Kleinberg, R.D. (ed.) ITCS 2013, pp. 373–388. ACM (Jan 2013). https://doi.org/10.1145/2422436.2422479
Mahmoody, M., Smith, C., Wu, D.J.: Can verifiable delay functions be based on random oracles? In: Czumaj, A., Dawar, A., Merelli, E. (eds.) ICALP 2020. LIPIcs, vol. 168, pp. 83:1–83:17. Schloss Dagstuhl (Jul 2020). https://doi.org/10.4230/LIPIcs.ICALP.2020.83
Montgomery, H.L., Vaughan, R.C.: Multiplicative number theory I: Classical theory. No. 97, Cambridge university press (2007)
Pietrzak, K.: Simple verifiable delay functions. In: Blum, A. (ed.) ITCS 2019. vol. 124, pp. 60:1–60:15. LIPIcs (Jan 2019). https://doi.org/10.4230/LIPIcs.ITCS.2019.60
Pohlig, S.C., Hellman, M.E.: An improved algorithm for computing logarithms over gf(p) and its cryptographic significance (corresp.). IEEE Trans. Inf. Theory 24(1), 106–110 (1978). https://doi.org/10.1109/TIT.1978.1055817
Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock Puzzles and Timed-release Crypto. Technical Report, Massachusetts Institute of Technology (1996)
Rotem, L., Segev, G.: Generically speeding-up repeated squaring is equivalent to factoring: sharp thresholds for all generic-ring delay functions. In: Micciancio, D., Ristenpart, T. (eds.) Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part III, pp. 481–509. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_17
Savage, J.E.: Models of Computation, vol. 136. Addison-Wesley Reading, MA (1998)
Schindler, P., Judmayer, A., Hittmeir, M., Stifter, N., Weippl, E.R.: RandRunner: Distributed randomness from trapdoor VDFs with strong uniqueness. In: NDSS 2021. The Internet Society (Feb 2021)
Shamir, A.: Factoring large numbers with the TWINKLE Device: (extended abstract). In: Koç, Ç.K., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems: First InternationalWorkshop, CHES’99 Worcester, MA, USA, August 12–13, 1999 Proceedings, pp. 2–12. Springer Berlin Heidelberg, Berlin, Heidelberg (1999). https://doi.org/10.1007/3-540-48059-5_2
Shani, B.: A note on isogeny-based hybrid verifiable delay functions. Cryptology ePrint Archive, Report 2019/205 (2019). https://eprint.iacr.org/2019/205
Shanks, D.: Class number, a theory of factorization, and genera. In: Proceedings of the Symp. Math. Soc., 1971. vol. 20, pp. 415–440 (1971)
Shparlinski, I.: Number theoretic methods in cryptography: Complexity lower bounds, vol. 17. Birkhäuser (2012)
Sorenson, J.: Polylog depth circuits for integer factoring and discrete logarithms. Inf. Comput. 110(1), 1–18 (1994)
Sorenson, J.: Two fast GCD algorithms. J. Algorithms 16(1), 110–144 (1994). https://doi.org/10.1006/jagm.1994.1006
Sreedhar, K., Horowitz, M., Torng, C.: A fast large-integer extended GCD algorithm and hardware design for verifiable delay functions and modular inversion. IACR TCHES 2022(4), 163–187 (2022). https://doi.org/10.46586/tches.v2022.i4.163-187
Valiant, L.G.: A scheme for fast parallel communication. SIAM J. Comput. 11(2), 350–361 (1982). https://doi.org/10.1137/0211027
Wallace, C.S.: A suggestion for a fast multiplier. IEEE Trans. Electron. Comput. 13(1), 14–17 (1964). https://doi.org/10.1109/PGEC.1964.263830
Wang, P.S.: A p-adic algorithm for univariate partial fractions. In: Wang, P.S. (ed.) Proceedings of the Symposium on Symbolic and Algebraic Manipulation, SYMSAC 1981, Snowbird, Utah, USA, August 5-7, 1981, pp. 212–217. ACM (1981). https://doi.org/10.1145/800206.806398
Wesolowski, B.: Efficient verifiable delay functions. In: Ishai, Y., Rijmen, V. (eds.) Advances in Cryptology – EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part III, pp. 379–407. Springer International Publishing, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_13
Wiener, M.J.: The full cost of cryptanalytic attacks. J. Cryptol. 17(2), 105–124 (2004). https://doi.org/10.1007/s00145-003-0213-5
