Skip to main content
Springer Nature Link
Log in

On Time-Lock Cryptographic Assumptions in Abelian Hidden-Order Groups

  • Conference paper
  • First Online:
Advances in Cryptology – ASIACRYPT 2021 (ASIACRYPT 2021)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 13091))

Abstract

In this paper we study cryptographic finite abelian groups of unknown order and hardness assumptions in these groups. Abelian groups necessitate multiple group generators, which may be chosen at random. We formalize this setting and hardness assumptions therein. Furthermore, we generalize the algebraic group model and strong algebraic group model from cyclic groups to arbitrary finite abelian groups of unknown order. Building on these formalizations, we present techniques to deal with this new setting, and prove new reductions. These results are relevant for class groups of imaginary quadratic number fields and time-lock cryptography build upon them.

Research partially funded by NWO/TKI Grant 628.009.014.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 99.00
Price excludes VAT (USA)
Softcover Book
USD 129.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Aigner, M., Ziegler, G.: Proofs from the Book, vol. 274. Springer (2010). https://link.springer.com/book/10.1007/978-3-642-00856-6

  2. van Baarsen, A., Stevens, M.: On time-lock cryptographic assumptions in abelian hidden-order groups. Cryptology ePrint Archive, Report 2021/1184 (2021)

    Google Scholar 

  3. Biehl, I., Buchmann, J., Hamdy, S., Meyer, A.: A signature scheme based on the intractability of computing roots. Des. Codes Cryptogr. 25(3), 223–236 (2002)

    Article  MathSciNet  Google Scholar 

  4. Block, A.R., Holmgren, J., Rosen, A., Rothblum, R.D., Soni, P.: Time- and space-efficient arguments from groups of unknown order. In: CRYPTO (4). LNCS, vol. 12828, pp. 123–152. Springer (2021). https://link.springer.com/chapter/10.1007/978-3-030-84259-8_5

  5. Boneh, D., Bonneau, J., Bunz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology. LNCS, vol. 10991. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_25

  6. Boneh, D., Bunz, B., Fisch, B.: Batching techniques for accumulators with applications to IOPs and stateless blockchains. In: Boldyreva, A., Micciancio, D. (eds.) Advances in Cryptology. LNCS, vol. 11692. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_20

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

    Google Scholar 

  8. Buchmann, J., Schmidt, A.: Computing the structure of a finite abelian group. Math. Comput. 74(252), 2017–2026 (2005)

    Article  MathSciNet  Google Scholar 

  9. Buchmann, J., Vollmer, U.: Binary quadratic forms - an algorithmic approach, Algorithms and computation in mathematics, vol. 20. Springer (2007). https://link.springer.com/book/10.1007/978-3-540-46368-9

  10. Buchmann, J., Williams, H.C.: A key-exchange system based on imaginary quadratic fields. J. Cryptol. 1(2), 107–118 (1988)

    Article  MathSciNet  Google Scholar 

  11. Bünz, B., Fisch, B., Szepieniec, A.: Transparent snarks from DARK compilers. In: EUROCRYPT (1). LNCS, vol. 12105, pp. 677–706. Springer (2020). https://link.springer.com/chapter/10.1007/978-3-030-45721-1_24

  12. Cohen, H., Lenstra, H.: Heuristics on class groups of number fields. In: Number Theory Noordwijkerhout 1983, pp. 33–62. Springer (1984). https://link.springer.com/chapter/10.1007/BFb0099440

  13. Damgard, I., Fujisaki, E.: A statistically-hiding integer commitment scheme based on groups with hidden order. In: Zheng, Y. (eds.) Advances in Cryptology. LNCS, vol. 2501. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36178-2_8

  14. Damgard, I., Koprowski, M.: Generic lower bounds for root extraction and signature schemes in general groups. In: Knudsen, L.R. (eds.) Advances in Cryptology. LNCS, vol. 2332. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_17

  15. Dusart, P.: Autour de la fonction qui compte le nombre de nombres premiers. Ph.D. thesis, Université de Limoges (1998)

    Google Scholar 

  16. Ephraim, N., Freitag, C., Komargodski, I., Pass, R.: Continuous verifiable delay functions. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology. LNCS, vol. 12107. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_5

  17. Fuchsbauer, G., Kiltz, E., Loss, J.: The algebraic group model and its applications. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology. Lecture Notes in Computer Science, vol. 10992. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_2

  18. Katz, J., Loss, J., Xu, J.: On the security of time-lock puzzles and timed commitments. In: Pass, R., Pietrzak, K. (eds.) Theory of Cryptography. TCC 2020. LNCS, vol. 12552. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_14

  19. Landerreche, E., Stevens, M., Schaffner, C.: Non-interactive cryptographic timestamping based on verifiable delay functions. In: Financial Cryptography. LNCS, vol. 12059, pp. 541–558. Springer (2020). https://link.springer.com/chapter/10.1007/978-3-030-51280-4_29

  20. Lindhurst, S.: Computing roots in finite fields and groups, with a jaunt through sums of digits. Ph.D. thesis, The University of Wisconsin–Madison (1997)

    Google Scholar 

  21. Maurer, U., Wolf, S.: Lower bounds on generic algorithms in groups. In: Nyberg, K. (eds.) Advances in Cryptology. LNCS, vol. 1403. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054118

  22. Nechaev, V.: Complexity of a determinate algorithm for the discrete logarithm. Math. Notes 55(2), 165–172 (1994)

    Google Scholar 

  23. Pietrzak, K.: Simple verifiable delay functions. In: ITCS. LIPIcs, vol. 124, pp. 1–15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

    Google Scholar 

  24. Rabin, M.O.: Digitalized signatures and public-key functions as intractable as factorization. Tech. Rep. Massachusetts Inst. Technol. Cambridge Lab Comput. Sci. (1979)

    Google Scholar 

  25. Rabin, M.O.: Transaction protection by beacons. J. Comput. Syst. Sci. 27(2), 256–267 (1983)

    Article  MathSciNet  Google Scholar 

  26. Rivest, R., Shamir, A., Wagner, D.: Time-lock puzzles and timed-release crypto. Tech. Rep. Massachusetts Inst. Technol. (1996)

    Google Scholar 

  27. 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. Lecture Notes in Computer Science, vol. 12172. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_17

  28. Rotem, L., Segev, G., Shahaf, I.: Generic-group delay functions require hidden-order groups. In: EUROCRYPT (3). LNCS, vol. 12107, pp. 155–180. Springer (2020). https://link.springer.com/chapter/10.1007/978-3-030-45727-3_6

  29. Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701–717 (1980)

    Article  MathSciNet  Google Scholar 

  30. Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (eds.) Advances in Cryptology. LNCS, vol. 1233. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_18

  31. Wesolowski, B.: Efficient verifiable delay functions. In: Ishai, Y., Rijmen, V. (eds.) Advances in Cryptology. LNCS, vol. 11478. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_13

  32. Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (eds.) Symbolic and Algebraic Computation. LNCS, vol. 72. Springer, Heidelberg (1979). https://doi.org/10.1007/3-540-09519-5_73

Download references

Author information

Authors and Affiliations

  1. CWI, Cryptology Group, Amsterdam, The Netherlands

    Aron van Baarsen & Marc Stevens

Authors
  1. Aron van Baarsen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marc Stevens
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Aron van Baarsen or Marc Stevens .

Editor information

Editors and Affiliations

  1. NTT Corporation, Tokyo, Japan

    Mehdi Tibouchi

  2. Nanyang Technological University, Singapore, Singapore

    Huaxiong Wang

Rights and permissions

Reprints and permissions

Copyright information

© 2021 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

van Baarsen, A., Stevens, M. (2021). On Time-Lock Cryptographic Assumptions in Abelian Hidden-Order Groups. In: Tibouchi, M., Wang, H. (eds) Advances in Cryptology – ASIACRYPT 2021. ASIACRYPT 2021. Lecture Notes in Computer Science(), vol 13091. Springer, Cham. https://doi.org/10.1007/978-3-030-92075-3_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-92075-3_13

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-92074-6

  • Online ISBN: 978-3-030-92075-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation