Document Open Access Logo

Revisiting the Uber Assumption in the Algebraic Group Model: Fine-Grained Bounds in Hidden-Order Groups and Improved Reductions in Bilinear Groups

Author Lior Rotem

PDF
Thumbnail PDF

File

LIPIcs.ITC.2022.13.pdf
  • Filesize: 0.62 MB
  • 13 pages

Document Identifiers

Author Details

Lior Rotem
  • School of Computer Science and Engineering, Hebrew University of Jerusalem, Israel

Funding

Supported by the Adams Fellowship Program of the Israel Academy of Sciences and Humanities and by the European Union’s Horizon 2020 Framework Program (H2020) via an ERC Grant (Grant No. 714253).

Cite AsGet BibTex

Lior Rotem. Revisiting the Uber Assumption in the Algebraic Group Model: Fine-Grained Bounds in Hidden-Order Groups and Improved Reductions in Bilinear Groups. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITC.2022.13

Abstract

We prove strong security guarantees for a wide array of computational and decisional problems, both in hidden-order groups and in bilinear groups, within the algebraic group model (AGM) of Fuchsbauer, Kiltz and Loss (CRYPTO '18). As our first contribution, we put forth a new fine-grained variant of the Uber family of assumptions in hidden-order groups. This family includes in particular the repeated squaring function of Rivest, Shamir and Wagner, which underlies their time-lock puzzle as well as the main known candidates for verifiable delay functions; and a computational variant of the generalized BBS problem, which underlies the timed commitments of Boneh and Naor (CRYPTO '00). We then provide two results within a variant of the AGM, which show that the hardness of solving problems in this family in a less-than-trivial number of steps is implied by well-studied assumptions. The first reduction may be applied in any group (and in particular, class groups), and is to the RSA assumption; and our second reduction is in RSA groups with a modulus which is the product of two safe primes, and is to the factoring assumption. Additionally, we prove that the hardness of any computational problem in the Uber family of problems in bilinear groups is implied by the hardness of the q-discrete logarithm problem. The parameter q in our reduction is the maximal degree in which a variable appears in the polynomials which define the specific problem within the Uber family. This improves upon a recent result of Bauer, Fuchsbauer and Loss (CRYPTO '20), who obtained a similar implication but for a parameter q which is lower bounded by the maximal total degree of one of the above polynomials. We discuss the implications of this improvement to prominent group key-exchange protocols.

Subject Classification

ACM Subject Classification
  • Security and privacy → Cryptography
  • Theory of computation → Cryptographic primitives
Keywords
  • Algebraic group model
  • Uber assumption
  • Bilinear groups
  • Hidden-order groups

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Michel Abdalla, Manuel Barbosa, Tatiana Bradley, Stanislaw Jarecki, Jonathan Katz, and Jiayu Xu. Universally composable relaxed password authenticated key exchange. In Advances in Cryptology - CRYPTO '20, pages 278-307, 2020. Google Scholar
  2. Michel Abdalla, Manuel Barbosa, Jonathan Katz, Julian Loss, and Jiayu Xu. Algebraic adversaries in the universal composability framework. In Advances in Cryptology - ASIACRYPT '21, pages 311-341, 2021. Google Scholar
  3. Michel Abdalla, Fabrice Benhamouda, and Philip MacKenzie. Security of the J-PAKE password-authenticated key exchange protocol. In IEEE Symposium on Security and Privacy, pages 571-587, 2015. Google Scholar
  4. Divesh Aggarwal and Ueli Maurer. Breaking RSA generically is equivalent to factoring. In Advances in Cryptology - EUROCRYPT '09, pages 36-53, 2009. Google Scholar
  5. Thomas Agrikola, Dennis Hofheinz, and Julia Kastner. On instantiating the algebraic group model from falsifiable assumptions. In Advances in Cryptology - EUROCRYPT '20, pages 96-126, 2020. Google Scholar
  6. Benedikt Auerbach, Federico Giacon, and Eike Kiltz. Everybody’s a target: Scalability in public-key encryption. In Advances in Cryptology - EUROCRYPT '20, pages 475-506, 2020. Google Scholar
  7. Balthazar Bauer, Georg Fuchsbauer, and Julian Loss. A classification of computational assumptions in the algebraic group model. In Advances in Cryptology - CRYPTO '20, pages 121-151, 2020. Google Scholar
  8. Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security, pages 62-73, 1993. Google Scholar
  9. Elwyn Ralph Berlekamp. Factoring polynomials over large finite fields. Mathematics of Computation, 24(111):713-735, 1970. Google Scholar
  10. David Bernhard, Marc Fischlin, and Bogdan Warinschi. On the hardness of proving CCA-security of signed ElGamal. In Public-Key Cryptography - PKC ,16, pages 47-69, 2016. Google Scholar
  11. LenIngrid Biehl, Johannes Buchmann, Safuat Hamdy, and Andreas Meyer. A signature scheme based on the intractability of computing roots. Designs, Codes and Cryptography, 25(3):223-236, 2002. Google Scholar
  12. Lenore Blum, Manuel Blum, and Michael Shub. A simple unpredictable pseudo-random number generator. SIAM Journal on Computing, 15(2):364-383, 1986. Google Scholar
  13. Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. Verifiable delay functions. In Advances in Cryptology - CRYPTO '18, pages 757-788, 2018. Google Scholar
  14. Dan Boneh, Xavier Boyen, and Eu-Jin Goh. Hierarchical identity based encryption with constant size ciphertext. In Advances in Cryptology - EUROCRYPT '05, pages 440-456, 2005. Google Scholar
  15. Dan Boneh, Benedikt Bünz, and Ben Fisch. A survey of two verifiable delay functions. Cryptology ePrint Archive, Report 2018/712, 2018. Google Scholar
  16. Dan Boneh, Justin Drake, Ben Fisch, and Ariel Gabizon. Efficient polynomial commitment schemes for multiple points and polynomials. Cryptology ePrint Archive, Report 2020/081, 2020. Google Scholar
  17. Dan Boneh and Moni Naor. Timed commitments. In Advances in Cryptology - CRYPTO '00, pages 236-254, 2000. Google Scholar
  18. Dan Boneh and Ramarathnam Venkatesan. Breaking RSA may not be equivalent to factoring. In Advances in Cryptology - EUROCRYPT '98, pages 59-71, 1998. Google Scholar
  19. Xavier Boyen. The Uber-assumption family - A unified complexity framework for bilinear groups. In Proceedings of the 2nd International Conference on Pairing-based Cryptography, pages 39-56, 2008. Google Scholar
  20. Emmanuel Bresson, Olivier Chevassut, and David Pointcheval. Provably authenticated group diffie-hellman key exchange - the dynamic case. In Advances in Cryptology - ASIACRYPT '01, pages 290-309, 2001. Google Scholar
  21. Emmanuel Bresson, Olivier Chevassut, and David Pointcheval. Provably secure authenticated group diffie-hellman key exchange. ACM Transactions on Information and System Security, 10(3):10:1-10:45, 2007. Google Scholar
  22. Emmanuel Bresson, Olivier Chevassut, David Pointcheval, and Jean-Jacques Quisquater. Provably authenticated group diffie-hellman key exchange. In Proceedings of the 8th ACM Conference on Computer and Communications Security, pages 255-264, 2001. Google Scholar
  23. Johannes Buchmann and Safuat Hamdy. A survey on IQ cryptography. In In Proceedings of Public Key Cryptography and Computational Number Theory, pages 1-15, 2001. Google Scholar
  24. Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Noah Vesely, and Nicholas Ward. Marlin: Preprocessing zkSNARKs with universal and updatable SRS. In Advances in Cryptology - EUROCRYPT '20, pages 738-768, 2020. Google Scholar
  25. Geoffroy Couteau and Dominik Hartmann. Shorter non-interactive zero-knowledge arguments and ZAPs for algebraic languages. In Advances in Cryptology - CRYPTO '20, pages 768-798, 2020. Google Scholar
  26. Ivan Damgård and Maciej Koprowski. Generic lower bounds for root extraction and signature schemes in general groups. In Advances in Cryptology - EUROCRYPT '02, pages 256-271, 2002. Google Scholar
  27. Alexander W. Dent. Adapting the weaknesses of the random oracle model to the generic group model. In Advances in Cryptology - ASIACRYPT '02, pages 100-109, 2002. Google Scholar
  28. Georg Fuchsbauer, Eike Kiltz, and Julian Loss. The algebraic group model and its applications. In Advances in Cryptology - CRYPTO '18, pages 33-62, 2018. Google Scholar
  29. Georg Fuchsbauer, Antoine Plouviez, and Yannick Seurin. Blind Schnorr signatures and signed ElGamal encryption in the algebraic group model. In Advances in Cryptology - EUROCRYPT '20, pages 63-95, 2020. Google Scholar
  30. Juan A. Garay and Markus Jakobsson. Timed release of standard digital signatures. In Financial Cryptography, pages 190-207, 2002. Google Scholar
  31. Juan A. Garay, Philip D. MacKenzie, Manoj Prabhakaran, and Ke Yang. Resource fairness and composability of cryptographic protocols. In Proceedings of the 4th Theory of Cryptography Conference, pages 404-428, 2006. Google Scholar
  32. Juan A. Garay and Carl Pomerance. Timed fair exchange of standard signatures. In Financial Cryptography, pages 190-207, 2003. Google Scholar
  33. Ashrujit Ghoshal and Stefano Tessaro. Tight state-restoration soundness in the algebraic group model. In Advances in Cryptology - CRYPTO '21, pages 64-93, 2021. Google Scholar
  34. Sergey Gorbunov, Leonid Reyzin, Hoeteck Wee, and Zhenfei Zhang. Pointproofs: Aggregating proofs for multiple vector commitments. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 2007-2023, 2020. Google Scholar
  35. Julia Kastner, Julian Loss, and Jiayu Xu. On pairing-free blind signature schemes in the algebraic group model. To appear in Public-Key Cryptography –- PKC '22 (available at https://eprint.iacr.org/2020/1071.pdf), 2022.
  36. Jonathan Katz and Yehuda Lindell. Introduction to modern cryptography (2nd edition). Chapman & Hall/CRC press, 2014. Google Scholar
  37. Jonathan Katz, Julian Loss, and Jiayu Xu. On the security of time-lock puzzles and timed commitments. In Proceedings of the 18th Theory of Cryptography Conference, pages 390-413, 2020. Google Scholar
  38. Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: Zero-knowledge SNARKs from linear-size universal and updatable structured reference strings. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 2111-2128, 2019. Google Scholar
  39. Taiga Mizuide, Atsushi Takayasu, and Tsuyoshi Takagi. Tight reductions for Diffie-Hellman variants in the algebraic group model. In Topics in Cryptology - CT-RSA '19, pages 169-188, 2019. Google Scholar
  40. Pascal Paillier and Damien Vergnaud. Discrete-log-based signatures may not be equivalent to discrete log. In Advances in Cryptology - ASIACRYPT '05, pages 1-20, 2005. Google Scholar
  41. Krzysztof Pietrzak. Simple verifiable delay functions. In Proceedings of the 10th Conference on Innovations in Theoretical Computer Science, pages 60:1-60:15, 2019. Google Scholar
  42. Michael Oser Rabin. Probabilistic algorithms in finite fields. SIAM Journal on Computing, 9(2):273-280, 1980. Google Scholar
  43. R. L. Rivest, A. Shamir, and D. A. Wagner. Time-lock puzzles and timed-release crypto, 1996. Google Scholar
  44. Lior Rotem and Gil Segev. Algebraic distinguishers: From discrete logarithms to decisional uber assumptions. In Proceedings of the 18th Theory of Cryptography Conference, pages 366-389, 2020. Google Scholar
  45. Lior Rotem and Gil Segev. Generically speeding-up repeated squaring is equivalent to factoring: Sharp thresholds for all generic-ring delay functions. In Advances in Cryptology - CRYPTO '20, pages 481-509, 2020. Google Scholar
  46. Aron van Baarsen and Marc Stevens. On time-lock cryptographic assumptions in abelian hidden-order groups. In Advances in Cryptology - ASIACRYPT '21, pages 367-397, 2021. Google Scholar
  47. Benjamin Wesolowski. Efficient verifiable delay functions. In Advances in Cryptology - EUROCRYPT '19, pages 379-407, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact