Special Soundness in the Random Oracle Model
Authors
Douglas Wikström
Douglas Wikström
KTH Royal Institute of Technology, Stockholm, Sweden
dog at kth dot se
dog at kth dot se
Abstract
We generalize the optimal knowledge extractor for constant-round special sound protocols presented by Wikström (2018) to a knowledge extractor for the corresponding non-interactive Fiat-Shamir proofs in the random oracle model and give an exact analysis of the extraction error and running time.
Relative the interactive case the extraction error and the running time are both asymptotically increased by a multiplicative factor equal to the number of oracle queries made by the prover.
Through carefully chosen notation, novel concepts, and a technical lemma, we effectively recast the extraction problem of the notoriously complex non-interactive case to the interactive case. Thus, our approach may be of independent interest.
References
[ACK21]
Thomas Attema, Ronald Cramer, and Lisa Kohl. A Compressed $\varSigma $-Protocol Theory for Lattices. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part II, volume 12826 of Lecture Notes in Computer Science, pages 549–579. 2021. Springer. DOI: 10.1007/978-3-030-84245-1_19
[AFK22]
Thomas Attema, Serge Fehr, and Michael Klooß. Fiat-Shamir Transformation of Multi-round Interactive Proofs. In Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part I, volume 13747 of Lecture Notes in Computer Science, pages 113–142. 2022. Springer. DOI: 10.1007/978-3-031-22318-1_5
[AL21]
Martin R. Albrecht and Russell W. F. Lai. Subtractive Sets over Cyclotomic Rings - Limits of Schnorr-Like Arguments over Lattices. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part II, volume 12826 of Lecture Notes in Computer Science, pages 519–548. 2021. Springer. DOI: 10.1007/978-3-030-84245-1_18
[AS08]
Noga Alon and Joel H. Spencer. The Probabilistic Method, Third Edition. Wiley-Interscience series in discrete mathematics and optimization. Wiley 2008.
[Bab85]
László Babai. Trading Group Theory for Randomness. In Robert Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 421–429. 1985. ACM. DOI: 10.1145/22145.22192
[BCC+16]
Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, volume 9666 of Lecture Notes in Computer Science, pages 327–357. 2016. Springer. DOI: 10.1007/978-3-662-49896-5_12
[BG92]
Mihir Bellare and Oded Goldreich. On Defining Proofs of Knowledge. In Ernest F. Brickell, editor, Advances in Cryptology - CRYPTO '92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings, volume 740 of Lecture Notes in Computer Science, pages 390–420. 1992. Springer. DOI: 10.1007/3-540-48071-4_28
[BGR98]
Mihir Bellare, Juan A. Garay, and Tal Rabin. Fast Batch Verification for Modular Exponentiation and Digital Signatures. In Kaisa Nyberg, editor, Advances in Cryptology - EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 - June 4, 1998, Proceeding, volume 1403 of Lecture Notes in Computer Science, pages 236–250. 1998. Springer. DOI: 10.1007/BFb0054130
[BL04]
Boaz Barak and Yehuda Lindell. Strict Polynomial-Time in Simulation and Extraction. SIAM J. Comput., 33(4):738–818, 2004. DOI: 10.1137/S0097539703427975
[BN06]
Mihir Bellare and Gregory Neven. Multi-signatures in the plain public-Key model and a general forking lemma. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, Alexandria, VA, USA, October 30 - November 3, 2006, pages 390–399. 2006. ACM. DOI: 10.1145/1180405.1180453
[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, CCS '93, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, November 3-5, 1993., pages 62–73. 1993. ACM. DOI: 10.1145/168588.168596
[CDS94]
Ronald Cramer, Ivan Damgård, and Berry Schoenmakers. Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO '94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, pages 174–187. 1994. Springer. DOI: 10.1007/3-540-48658-5_19
[dPLS19]
Rafaël del Pino, Vadim Lyubashevsky, and Gregor Seiler. Short Discrete Log Proofs for FHE and Ring-LWE Ciphertexts. In Dongdai Lin and Kazue Sako, editors, Public-Key Cryptography - PKC 2019 - 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Beijing, China, April 14-17, 2019, Proceedings, Part I, volume 11442 of Lecture Notes in Computer Science, pages 344–373. 2019. Springer. DOI: 10.1007/978-3-030-17253-4_12
[FS86]
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, Santa Barbara, California, USA, 1986, Proceedings, volume 263 of Lecture Notes in Computer Science, pages 186–194. 1986. Springer. DOI: 10.1007/3-540-47721-7_12
[FS01]
Jun Furukawa and Kazue Sako. An Efficient Scheme for Proving a Shuffle. In Joe Kilian, editor, Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings, volume 2139 of Lecture Notes in Computer Science, pages 368–387. 2001. Springer. DOI: 10.1007/3-540-44647-8_22
[GMR89]
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge Complexity of Interactive Proof Systems. SIAM J. Comput., 18(1):186–208, 1989. DOI: 10.1137/0218012
[Gol00]
Oded Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, New York, NY, USA 2000.
[HKR19]
Max Hoffmann, Michael Klooß, and Andy Rupp. Efficient Zero-Knowledge Arguments in the Discrete Log Setting, Revisited. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11-15, 2019, pages 2093–2110. 2019. ACM. DOI: 10.1145/3319535.3354251
[JT20]
Joseph Jaeger and Stefano Tessaro. Expected-Time Cryptography: Generic Techniques and Applications to Concrete Soundness. In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part III, volume 12552 of Lecture Notes in Computer Science, pages 414–443. 2020. Springer. DOI: 10.1007/978-3-030-64381-2_15
[Nef01]
C. Andrew Neff. A verifiable secret shuffle and its application to e-voting. In Michael K. Reiter and Pierangela Samarati, editors, CCS 2001, Proceedings of the 8th ACM Conference on Computer and Communications Security, Philadelphia, Pennsylvania, USA, November 6-8, 2001., pages 116–125. 2001. ACM. DOI: 10.1145/501983.502000
[PS96]
David Pointcheval and Jacques Stern. Security Proofs for Signature Schemes. In Ueli M. Maurer, editor, Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding, volume 1070 of Lecture Notes in Computer Science, pages 387–398. 1996. Springer. DOI: 10.1007/3-540-68339-9_33
[Sch91]
Claus-Peter Schnorr. Efficient Signature Generation by Smart Cards. J. Cryptology, 4(3):161–174, 1991. DOI: 10.1007/BF00196725
[Wik05]
Douglas Wikström. A Sender Verifiable Mix-Net and a New Proof of a Shuffle. In Bimal K. Roy, editor, Advances in Cryptology - ASIACRYPT 2005, 11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, December 4-8, 2005, Proceedings, volume 3788 of Lecture Notes in Computer Science, pages 273–292. 2005. Springer. DOI: 10.1007/11593447_15
[Wik18]
Douglas Wikström. Special Soundness Revisited. IACR Cryptol. ePrint Arch., 2018:1157, 2018.
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
Douglas Wikström, Special Soundness in the Random Oracle Model. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/avivommol.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.