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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aigner, M., Ziegler, G.: Proofs from the Book, vol. 274. Springer (2010). https://link.springer.com/book/10.1007/978-3-642-00856-6
van Baarsen, A., Stevens, M.: On time-lock cryptographic assumptions in abelian hidden-order groups. Cryptology ePrint Archive, Report 2021/1184 (2021)
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)
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
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
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
Boneh, D., Bünz, B., Fisch, B.: A survey of two verifiable delay functions. Cryptology ePrint Archive, Report 2018/712 (2018)
Buchmann, J., Schmidt, A.: Computing the structure of a finite abelian group. Math. Comput. 74(252), 2017–2026 (2005)
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
Buchmann, J., Williams, H.C.: A key-exchange system based on imaginary quadratic fields. J. Cryptol. 1(2), 107–118 (1988)
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
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
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
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
Dusart, P.: Autour de la fonction qui compte le nombre de nombres premiers. Ph.D. thesis, Université de Limoges (1998)
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
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
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
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
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)
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
Nechaev, V.: Complexity of a determinate algorithm for the discrete logarithm. Math. Notes 55(2), 165–172 (1994)
Pietrzak, K.: Simple verifiable delay functions. In: ITCS. LIPIcs, vol. 124, pp. 1–15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
Rabin, M.O.: Digitalized signatures and public-key functions as intractable as factorization. Tech. Rep. Massachusetts Inst. Technol. Cambridge Lab Comput. Sci. (1979)
Rabin, M.O.: Transaction protection by beacons. J. Comput. Syst. Sci. 27(2), 256–267 (1983)
Rivest, R., Shamir, A., Wagner, D.: Time-lock puzzles and timed-release crypto. Tech. Rep. Massachusetts Inst. Technol. (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. Lecture Notes in Computer Science, vol. 12172. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_17
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
Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701–717 (1980)
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
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
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
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 International Association for Cryptologic Research
About this paper
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)