Special Soundness Revisited
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 and abstract the problem of extracting a witness from a prover of a special sound protocol into a combinatorial problem induced by a sequence of matroids and a predicate, and present a parametrized algorithm for solving this problem.
The parametrization provides a tight tradeoff between the running time and the extraction error of the algorithm, which allows optimizing the parameters to minimize: the soundness error for interactive proofs, or the extraction time for proofs of knowledge.
In contrast to previous work we bound the distribution of the running time and not only the expected running time. Tail bounds give a tighter analysis when applied recursively and a concentrated running time.
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
[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
[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.
[Gro03]
Jens Groth. A Verifiable Secret Shuffle of Homomorphic Encryptions. In Yvo Desmedt, editor, Public Key Cryptography - PKC 2003, 6th International Workshop on Theory and Practice in Public Key Cryptography, Miami, FL, USA, January 6-8, 2003, Proceedings, volume 2567 of Lecture Notes in Computer Science, pages 145–160. 2003. Springer. DOI: 10.1007/3-540-36288-6_11
[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
[Jan17]
Svante Janson. Tail bounds for sums of geometric and exponential variables. 2017.
[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
[KL81]
Bernhard Korte and László Lovász. Mathematical Structures Underlying Greedy Algorithms. In Ferenc Gécseg, editor, Fundamentals of Computation Theory, FCT'81, Proceedings of the 1981 International FCT-Conference, Szeged, Hungary, August 24-28, 1981, volume 117 of Lecture Notes in Computer Science, pages 205–209. 1981. Springer. DOI: 10.1007/3-540-10854-8_22
[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
[Sch91]
Claus-Peter Schnorr. Efficient Signature Generation by Smart Cards. J. Cryptology, 4(3):161–174, 1991. DOI: 10.1007/BF00196725
[Sho04]
Victor Shoup. Sequences of games: a tool for taming complexity in security proofs. IACR Cryptology ePrint Archive, 2004:332, 2004.
[TW10]
Björn Terelius and Douglas Wikström. Proofs of Restricted Shuffles. In Daniel J. Bernstein and Tanja Lange, editors, Progress in Cryptology - AFRICACRYPT 2010, Third International Conference on Cryptology in Africa, Stellenbosch, South Africa, May 3-6, 2010. Proceedings, volume 6055 of Lecture Notes in Computer Science, pages 100–113. 2010. Springer. DOI: 10.1007/978-3-642-12678-9_7
[Wal44]
Abraham Wald. On Cumulative Sums of Random Variables. Ann. Math. Statist., 15(3):283–296, September 1944. DOI: 10.1214/aoms/1177731235
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 Revisited. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/aep2c3w9p.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.