The Uber-Knowledge Assumption: A Bridge to the AGM
Authors
Balthazar Bauer, Pooya Farshim, Patrick Harasser, Markulf Kohlweiss
Balthazar Bauer
Université de Versailles Saint-Quentin-en-Yvelines, France
balthazar dot bauer at ens dot fr
balthazar dot bauer at ens dot fr
Pooya Farshim
IOG, Switzerland
Durham University, United Kingdom
pooya dot farshim at gmail dot com
Durham University, United Kingdom
pooya dot farshim at gmail dot com
Patrick Harasser
Technical University of Darmstadt, Germany
patrick dot harasser at tu-darmstadt dot de
patrick dot harasser at tu-darmstadt dot de
Markulf Kohlweiss
University of Edinburgh, United Kingdom
IOG, United Kingdom
mkohlwei at ed dot ac dot uk
IOG, United Kingdom
mkohlwei at ed dot ac dot uk
Keywords:
Knowledge assumption
Standard model
Generic-group model
Algebraic-group model
Groth16
KZG commitment
Abstract
The generic-group model (GGM) and the algebraic-group model (AGM) have been exceptionally successful in proving the security of many classical and modern cryptosystems. These models, however, come with standard-model uninstantiability results, raising the question of whether the schemes analyzed under them can be based on firmer standard-model footing.
We formulate the uber-knowledge (UK) assumption, a standard-model assumption that naturally extends the uber-assumption family to knowledge-type problems. We justify the soundness of UK in both the bilinear GGM and the bilinear AGM. Along the way we extend these models to account for hashing into groups, an adversarial capability that is available in many concrete groups—In contrast to standard assumptions, hashing may affect the validity of knowledge assumptions. These results, in turn, enable a modular approach to security in the GGM and the AGM.
As example applications, we use the UK assumption to prove knowledge soundness of Groth's zero-knowledge SNARK (EUROCRYPT 2016) and of KZG polynomial commitments (ASIACRYPT 2010) in the standard model, where for the former we reuse the existing proof in the AGM without hashing.
References
[AGHO11]
Masayuki Abe, Jens Groth, Kristiyan Haralambiev, and Miyako Ohkubo. Optimal Structure-Preserving Signatures in Asymmetric Bilinear Groups. In Phillip Rogaway, editor, Advances in Cryptology – CRYPTO 2011, volume 6841 of Lecture Notes in Computer Science, pages 649–666. August 2011. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-22792-9_37
[BB04]
Dan Boneh and Xavier Boyen. Short Signatures Without Random Oracles. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology – EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 56–73. May 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-24676-3_4
[BBG05]
Dan Boneh, Xavier Boyen, and Eu-Jin Goh. Hierarchical Identity Based Encryption with Constant Size Ciphertext. In Ronald Cramer, editor, Advances in Cryptology – EUROCRYPT 2005, volume 3494 of Lecture Notes in Computer Science, pages 440–456. May 2005. Springer, Berlin, Heidelberg. DOI: 10.1007/11426639_26
[BCC+17]
Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, and Eran Tromer. The Hunting of the SNARK. Journal of Cryptology, 30(4):989–1066, October 2017. DOI: 10.1007/s00145-016-9241-9
[BCCT12]
Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In Shafi Goldwasser, editor, ITCS 2012: 3rd Innovations in Theoretical Computer Science, pages 326–349. January 2012. Association for Computing Machinery. DOI: 10.1145/2090236.2090263
[BD14]
James Birkett and Alexander W. Dent. Security Models and Proof Strategies for Plaintext-Aware Encryption. Journal of Cryptology, 27(1):139–180, January 2014. DOI: 10.1007/s00145-012-9141-6
[BDPV08]
Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. On the Indifferentiability of the Sponge Construction. In Nigel P. Smart, editor, Advances in Cryptology – EUROCRYPT 2008, volume 4965 of Lecture Notes in Computer Science, pages 181–197. April 2008. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-78967-3_11
[Ber67]
Elwyn R. Berlekamp. Factoring polynomials over finite fields. The Bell System Technical Journal, 46(8):1853–1859, October 1967. DOI: 10.1002/j.1538-7305.1967.tb03174.x
[BFHO22]
Balthazar Bauer, Pooya Farshim, Patrick Harasser, and Adam O'Neill. Beyond Uber: Instantiating Generic Groups via PGGs. In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022: 20th Theory of Cryptography Conference, Part III, volume 13749 of Lecture Notes in Computer Science, pages 212–242. November 2022. Springer, Cham. DOI: 10.1007/978-3-031-22368-6_8
[BFL20]
Balthazar Bauer, Georg Fuchsbauer, and Julian Loss. A Classification of Computational Assumptions in the Algebraic Group Model. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, Part II, volume 12171 of Lecture Notes in Computer Science, pages 121–151. August 2020. Springer, Cham. DOI: 10.1007/978-3-030-56880-1_5
[BFS16]
Mihir Bellare, Georg Fuchsbauer, and Alessandra Scafuro. NIZKs with an Untrusted CRS: Security in the Face of Parameter Subversion. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology – ASIACRYPT 2016, Part II, volume 10032 of Lecture Notes in Computer Science, pages 777–804. December 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-53890-6_26
[BFS20]
Benedikt Bünz, Ben Fisch, and Alan Szepieniec. Transparent SNARKs from DARK Compilers. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part I, volume 12105 of Lecture Notes in Computer Science, pages 677–706. May 2020. Springer, Cham. DOI: 10.1007/978-3-030-45721-1_24
[BHK14]
Mihir Bellare, Viet Tung Hoang, and Sriram Keelveedhi. Cryptography from Compression Functions: The UCE Bridge to the ROM. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology – CRYPTO 2014, Part I, volume 8616 of Lecture Notes in Computer Science, pages 169–187. August 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-44371-2_10
[Bla06]
John Black. The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-Based Hash Function. In Matthew J. B. Robshaw, editor, Fast Software Encryption – FSE 2006, volume 4047 of Lecture Notes in Computer Science, pages 328–340. March 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11799313_21
[BP04a]
Mihir Bellare and Adriana Palacio. The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols. In Matthew Franklin, editor, Advances in Cryptology – CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 273–289. August 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-28628-8_17
[BP04b]
Mihir Bellare and Adriana Palacio. Towards Plaintext-Aware Public-Key Encryption without Random Oracles. In Pil Joong Lee, editor, Advances in Cryptology – ASIACRYPT 2004, volume 3329 of Lecture Notes in Computer Science, pages 48–62. December 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-30539-2_4
[BR93]
Mihir Bellare and Phillip Rogaway. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In Dorothy E. Denning, Raymond Pyle, Ravi Ganesan, Ravi S. Sandhu, and Victoria Ashby, editors, ACM CCS 93: 1st Conference on Computer and Communications Security, pages 62–73. November 1993. ACM Press. DOI: 10.1145/168588.168596
[BR06]
Mihir Bellare and Phillip Rogaway. The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs. In Serge Vaudenay, editor, Advances in Cryptology – EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 409–426. 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11761679_25
[Bro01]
Daniel R. L. Brown. The Exact Security of ECDSA. http://grouper.ieee.org/groups/1363/. Contributions to IEEE P1363a. January 2001.
[BRS02]
John Black, Phillip Rogaway, and Thomas Shrimpton. Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. In Moti Yung, editor, Advances in Cryptology – CRYPTO 2002, volume 2442 of Lecture Notes in Computer Science, pages 320–335. August 2002. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45708-9_21
[BV98]
Dan Boneh and Ramarathnam Venkatesan. Breaking RSA May Not Be Equivalent to Factoring. In Kaisa Nyberg, editor, Advances in Cryptology – EUROCRYPT'98, volume 1403 of Lecture Notes in Computer Science, pages 59–71. 1998. Springer, Berlin, Heidelberg. DOI: 10.1007/BFb0054117
[CCS07]
Liqun Chen, Zhaohui Cheng, and Nigel P. Smart. Identity-based key agreement protocols from pairings. International Journal of Information Security, 6(4):213–241, January 2007. DOI: 10.1007/s10207-006-0011-9
[CDMP05]
Jean-Sébastien Coron, Yevgeniy Dodis, Cécile Malinaud, and Prashant Puniya. Merkle-Damgård Revisited: How to Construct a Hash Function. In Victor Shoup, editor, Advances in Cryptology – CRYPTO 2005, volume 3621 of Lecture Notes in Computer Science, pages 430–448. August 2005. Springer, Berlin, Heidelberg. DOI: 10.1007/11535218_26
[CFF+21]
Matteo Campanelli, Antonio Faonio, Dario Fiore, Anaïs Querol, and Hadrián Rodríguez. Lunar: A Toolbox for More Efficient Universal and Updatable zkSNARKs and Commit-and-Prove Extensions. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, Part III, volume 13092 of Lecture Notes in Computer Science, pages 3–33. December 2021. Springer, Cham. DOI: 10.1007/978-3-030-92078-4_1
[CGH98]
Ran Canetti, Oded Goldreich, and Shai Halevi. The Random Oracle Methodology, Revisited (Preliminary Version). In 30th Annual ACM Symposium on Theory of Computing, pages 209–218. May 1998. ACM Press. DOI: 10.1145/276698.276741
[CHM+20]
Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, and Nicholas P. Ward. Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part I, volume 12105 of Lecture Notes in Computer Science, pages 738–768. May 2020. Springer, Cham. DOI: 10.1007/978-3-030-45721-1_26
[CS98]
Ronald Cramer and Victor Shoup. A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack. In Hugo Krawczyk, editor, Advances in Cryptology – CRYPTO'98, volume 1462 of Lecture Notes in Computer Science, pages 13–25. August 1998. Springer, Berlin, Heidelberg. DOI: 10.1007/BFb0055717
[Dam92]
Ivan Damgård. Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks. In Joan Feigenbaum, editor, Advances in Cryptology – CRYPTO'91, volume 576 of Lecture Notes in Computer Science, pages 445–456. August 1992. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-46766-1_36
[Den02]
Alexander W. Dent. Adapting the Weaknesses of the Random Oracle Model to the Generic Group Model. In Yuliang Zheng, editor, Advances in Cryptology – ASIACRYPT 2002, volume 2501 of Lecture Notes in Computer Science, pages 100–109. December 2002. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-36178-2_6
[Den06a]
Alexander W. Dent. The Cramer-Shoup Encryption Scheme Is Plaintext Aware in the Standard Model. In Serge Vaudenay, editor, Advances in Cryptology – EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 289–307. 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11761679_18
[Den06b]
Alexander W. Dent. The Hardness of the DHK Problem in the Generic Group Model. Cryptology ePrint Archive, Report 2006/156. 2006.
[DL78]
Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193–195, June 1978. DOI: 10.1016/0020-0190(78)90067-4
[EHK+13]
Alex Escala, Gottfried Herold, Eike Kiltz, Carla Ràfols, and Jorge Villar. An Algebraic Framework for Diffie-Hellman Assumptions. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, Part II, volume 8043 of Lecture Notes in Computer Science, pages 129–147. August 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-40084-1_8
[FFK+23]
Antonio Faonio, Dario Fiore, Markulf Kohlweiss, Luigi Russo, and Michal Zajac. From Polynomial IOP and Commitments to Non-malleable zkSNARKs. In Guy N. Rothblum and Hoeteck Wee, editors, TCC 2023: 21st Theory of Cryptography Conference, Part III, volume 14371 of Lecture Notes in Computer Science, pages 455–485. 2023. Springer, Cham. DOI: 10.1007/978-3-031-48621-0_16
[FGJ18]
Nils Fleischhacker, Vipul Goyal, and Abhishek Jain. On the Existence of Three Round Zero-Knowledge Proofs. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, Part III, volume 10822 of Lecture Notes in Computer Science, pages 3–33. 2018. Springer, Cham. DOI: 10.1007/978-3-319-78372-7_1
[FKL18]
Georg Fuchsbauer, Eike Kiltz, and Julian Loss. The Algebraic Group Model and its Applications. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part II, volume 10992 of Lecture Notes in Computer Science, pages 33–62. August 2018. Springer, Cham. DOI: 10.1007/978-3-319-96881-0_2
[FPS20]
Georg Fuchsbauer, Antoine Plouviez, and Yannick Seurin. Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic Group Model. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part II, volume 12106 of Lecture Notes in Computer Science, pages 63–95. May 2020. Springer, Cham. DOI: 10.1007/978-3-030-45724-2_3
[FS87]
Amos Fiat and Adi Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Andrew M. Odlyzko, editor, Advances in Cryptology – CRYPTO'86, volume 263 of Lecture Notes in Computer Science, pages 186–194. August 1987. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-47721-7_12
[GK16]
Shafi Goldwasser and Yael Tauman Kalai. Cryptographic Assumptions: A Position Paper. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A: 13th Theory of Cryptography Conference, Part I, volume 9562 of Lecture Notes in Computer Science, pages 505–522. January 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-49096-9_21
[GM17]
Jens Groth and Mary Maller. Snarky Signatures: Minimal Signatures of Knowledge from Simulation-Extractable SNARKs. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology – CRYPTO 2017, Part II, volume 10402 of Lecture Notes in Computer Science, pages 581–612. August 2017. Springer, Cham. DOI: 10.1007/978-3-319-63715-0_20
[GPS06]
Stephen D. Galbraith, Kenneth G. Paterson, and Nigel P. Smart. Pairings for Cryptographers. Cryptology ePrint Archive, Report 2006/165. 2006.
[Gro10]
Jens Groth. Short Pairing-Based Non-interactive Zero-Knowledge Arguments. In Masayuki Abe, editor, Advances in Cryptology – ASIACRYPT 2010, volume 6477 of Lecture Notes in Computer Science, pages 321–340. December 2010. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-17373-8_19
[Gro16]
Jens Groth. On the Size of Pairing-Based Non-interactive Arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 305–326. May 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-49896-5_11
[GS22]
Jens Groth and Victor Shoup. On the Security of ECDSA with Additive Key Derivation and Presignatures. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology – EUROCRYPT 2022, Part I, volume 13275 of Lecture Notes in Computer Science, pages 365–396. 2022. Springer, Cham. DOI: 10.1007/978-3-031-06944-4_13
[GT21]
Ashrujit Ghoshal and Stefano Tessaro. Tight State-Restoration Soundness in the Algebraic Group Model. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part III, volume 12827 of Lecture Notes in Computer Science, pages 64–93, Virtual Event. August 2021. Springer, Cham. DOI: 10.1007/978-3-030-84252-9_3
[GWC19]
Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. Cryptology ePrint Archive, Report 2019/953. 2019.
[HKT11]
Thomas Holenstein, Robin Künzler, and Stefano Tessaro. The equivalence of the random oracle model and the ideal cipher model, revisited. In Lance Fortnow and Salil P. Vadhan, editors, 43rd Annual ACM Symposium on Theory of Computing, pages 89–98. June 2011. ACM Press. DOI: 10.1145/1993636.1993650
[HT98]
Satoshi Hada and Toshiaki Tanaka. On the Existence of 3-Round Zero-Knowledge Protocols. In Hugo Krawczyk, editor, Advances in Cryptology – CRYPTO'98, volume 1462 of Lecture Notes in Computer Science, pages 408–423. August 1998. Springer, Berlin, Heidelberg. DOI: 10.1007/BFb0055744
[HT99]
Satoshi Hada and Toshiaki Tanaka. On the Existence of 3-Round Zero-Knowledge Protocols. Cryptology ePrint Archive, Report 1999/009. 1999.
[Jou04]
Antoine Joux. A One Round Protocol for Tripartite Diffie–Hellman. Journal of Cryptology, 17(4):263–276, September 2004. DOI: 10.1007/s00145-004-0312-y
[KLT16]
Aggelos Kiayias, Feng-Hao Liu, and Yiannis Tselekounis. Practical Non-Malleable Codes from $\ell$-more Extractable Hash Functions. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016: 23rd Conference on Computer and Communications Security, pages 1317–1328. October 2016. ACM Press. DOI: 10.1145/2976749.2978352
[KLX22]
Julia Kastner, Julian Loss, and Jiayu Xu. On Pairing-Free Blind Signature Schemes in the Algebraic Group Model. In Goichiro Hanaoka, Junji Shikata, and Yohei Watanabe, editors, PKC 2022: 25th International Conference on Theory and Practice of Public Key Cryptography, Part II, volume 13178 of Lecture Notes in Computer Science, pages 468–497. March 2022. Springer, Cham. DOI: 10.1007/978-3-030-97131-1_16
[KM07]
Neal Koblitz and Alfred J. Menezes. Another Look at “Provable Security”. Journal of Cryptology, 20(1):3–37, January 2007. DOI: 10.1007/s00145-005-0432-z
[KZG10]
Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-Size Commitments to Polynomials and Their Applications. In Masayuki Abe, editor, Advances in Cryptology – ASIACRYPT 2010, volume 6477 of Lecture Notes in Computer Science, pages 177–194. December 2010. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-17373-8_11
[Lep02]
Matthew Lepinski. On the Existence of 3-Round Zero-Knowledge Proofs. Master's thesis, Massachusetts Institute of Technology, June 2002.
[Lip22]
Helger Lipmaa. A Unified Framework for Non-universal SNARKs. In Goichiro Hanaoka, Junji Shikata, and Yohei Watanabe, editors, PKC 2022: 25th International Conference on Theory and Practice of Public Key Cryptography, Part I, volume 13177 of Lecture Notes in Computer Science, pages 553–583. March 2022. Springer, Cham. DOI: 10.1007/978-3-030-97121-2_20
[LPS23]
Helger Lipmaa, Roberto Parisella, and Janno Siim. Algebraic Group Model with Oblivious Sampling. In Guy N. Rothblum and Hoeteck Wee, editors, TCC 2023: 21st Theory of Cryptography Conference, Part IV, volume 14372 of Lecture Notes in Computer Science, pages 363–392. 2023. Springer, Cham. DOI: 10.1007/978-3-031-48624-1_14
[Mau05]
Ueli M. Maurer. Abstract Models of Computation in Cryptography (Invited Paper). In Nigel P. Smart, editor, 10th IMA International Conference on Cryptography and Coding, volume 3796 of Lecture Notes in Computer Science, pages 1–12. December 2005. Springer, Berlin, Heidelberg. DOI: 10.1007/11586821_1
[MBKM19]
Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019: 26th Conference on Computer and Communications Security, pages 2111–2128. November 2019. ACM Press. DOI: 10.1145/3319535.3339817
[Nao03]
Moni Naor. On Cryptographic Assumptions and Challenges (Invited Talk). In Dan Boneh, editor, Advances in Cryptology – CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 96–109. August 2003. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-45146-4_6
[Nec94]
Vassiliy Ilyich Nechaev. Complexity of a Determinate Algorithm for the Discrete Logarithm. Mathematical Notes, 55(2):165–172, February 1994. DOI: 10.1007/BF02113297
[PHGR13]
Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. Pinocchio: Nearly Practical Verifiable Computation. In 2013 IEEE Symposium on Security and Privacy, pages 238–252. May 2013. IEEE Computer Society Press. DOI: 10.1109/SP.2013.47
[PV05]
Pascal Paillier and Damien Vergnaud. Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log. In Bimal K. Roy, editor, Advances in Cryptology – ASIACRYPT 2005, volume 3788 of Lecture Notes in Computer Science, pages 1–20. December 2005. Springer, Berlin, Heidelberg. DOI: 10.1007/11593447_1
[RLB+08]
Andy Rupp, Gregor Leander, Endre Bangerter, Alexander W. Dent, and Ahmad-Reza Sadeghi. Sufficient Conditions for Intractability over Black-Box Groups: Generic Lower Bounds for Generalized DL and DH Problems. In Josef Pieprzyk, editor, Advances in Cryptology – ASIACRYPT 2008, volume 5350 of Lecture Notes in Computer Science, pages 489–505. December 2008. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-89255-7_30
[RS20]
Lior Rotem and Gil Segev. Algebraic Distinguishers: From Discrete Logarithms to Decisional Uber Assumptions. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020: 18th Theory of Cryptography Conference, Part III, volume 12552 of Lecture Notes in Computer Science, pages 366–389. November 2020. Springer, Cham. DOI: 10.1007/978-3-030-64381-2_13
[RZ21]
Carla Ràfols and Arantxa Zapico. An Algebraic Framework for Universal and Updatable SNARKs. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part I, volume 12825 of Lecture Notes in Computer Science, pages 774–804, Virtual Event. August 2021. Springer, Cham. DOI: 10.1007/978-3-030-84242-0_27
[Sch80]
Jack T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701–717, October 1980. DOI: 10.1145/322217.322225
[Sha05]
Hovav Shacham. New Paradigms in Signature Schemes. PhD thesis, Stanford University, December 2005.
[Sho97]
Victor Shoup. Lower Bounds for Discrete Logarithms and Related Problems. In Walter Fumy, editor, Advances in Cryptology – EUROCRYPT'97, volume 1233 of Lecture Notes in Computer Science, pages 256–266. May 1997. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-69053-0_18
[Zha22]
Mark Zhandry. To Label, or Not To Label (in Generic Groups). In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, Part III, volume 13509 of Lecture Notes in Computer Science, pages 66–96. August 2022. Springer, Cham. DOI: 10.1007/978-3-031-15982-4_3
[Zip79]
Richard Zippel. Probabilistic algorithms for sparse polynomials. In Edward W. Ng, editor, Symbolic and Algebraic Computation – EUROSAM 1979, volume 72 of Lecture Notes in Computer Science, pages 216–226. June 1979. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-09519-5_73
[ZZ23]
Cong Zhang and Mark Zhandry. The Relationship Between Idealized Models Under Computationally Bounded Adversaries. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology – ASIACRYPT 2023, Part VI, volume 14443 of Lecture Notes in Computer Science, pages 390–419. December 2023. Springer, Singapore. DOI: 10.1007/978-981-99-8736-8_13
[ZZK22]
Cong Zhang, Hong-Sheng Zhou, and Jonathan Katz. An Analysis of the Algebraic Group Model. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022, Part IV, volume 13794 of Lecture Notes in Computer Science, pages 310–322. December 2022. Springer, Cham. DOI: 10.1007/978-3-031-22972-5_11
PDF
History
Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Balthazar Bauer, Pooya Farshim, Patrick Harasser, and Markulf Kohlweiss, The Uber-Knowledge Assumption: A Bridge to the AGM. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/anr-zoja5.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.