{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,2]],"date-time":"2026-09-02T09:25:20Z","timestamp":1788341120161,"version":"build-2803163510"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T00:00:00Z","timestamp":1691452800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T00:00:00Z","timestamp":1691452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2023,10]]},"abstract":"Abstract<\/jats:title>The celebrated Fiat\u2013Shamir transformation turns any public-coin interactive proof into a non-interactive one, which inherits the main security properties (in the random oracle model) of the interactive version. While originally considered in the context of 3-move public-coin interactive proofs, i.e., so-called$$\\varSigma $$<\/jats:tex-math>\u03a3<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-protocols, it is now applied to multi-round protocols as well. Unfortunately, the security loss for a$$(2\\mu + 1)$$<\/jats:tex-math>(<\/mml:mo>2<\/mml:mn>\u03bc<\/mml:mi>+<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-move protocol is, in general, approximately$$Q^\\mu $$<\/jats:tex-math>Q<\/mml:mi>\u03bc<\/mml:mi><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, whereQ<\/jats:italic>is the number of oracle queries performed by the attacker. In general, this is the best one can hope for, as it is easy to see that this loss applies to the$$\\mu $$<\/jats:tex-math>\u03bc<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-fold sequential repetition of$$\\varSigma $$<\/jats:tex-math>\u03a3<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-protocols, but it raises the question whether certain (natural) classes of interactive proofs feature a milder security loss. In this work, we give positive and negative results on this question. On the positive side, we show that for$$(k_1, \\ldots , k_\\mu )$$<\/jats:tex-math>(<\/mml:mo>k<\/mml:mi>1<\/mml:mn><\/mml:msub>,<\/mml:mo>\u2026<\/mml:mo>,<\/mml:mo>k<\/mml:mi>\u03bc<\/mml:mi><\/mml:msub>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-special-sound protocols (which cover a broad class of use cases), the knowledge error degrades linearly inQ<\/jats:italic>, instead of$$Q^\\mu $$<\/jats:tex-math>Q<\/mml:mi>\u03bc<\/mml:mi><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. On the negative side, we show that fort<\/jats:italic>-foldparallel repetitions<\/jats:italic>of typical$$(k_1, \\ldots , k_\\mu )$$<\/jats:tex-math>(<\/mml:mo>k<\/mml:mi>1<\/mml:mn><\/mml:msub>,<\/mml:mo>\u2026<\/mml:mo>,<\/mml:mo>k<\/mml:mi>\u03bc<\/mml:mi><\/mml:msub>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-special-sound protocols with$$t \\ge \\mu $$<\/jats:tex-math>t<\/mml:mi>\u2265<\/mml:mo>\u03bc<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>(and assuming for simplicity thatt<\/jats:italic>andQ<\/jats:italic>are integer multiples of$$\\mu $$<\/jats:tex-math>\u03bc<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>), there is an attack that results in a security loss of approximately\u00a0$$\\frac{1}{2} Q^\\mu \/\\mu ^{\\mu +t}$$<\/jats:tex-math>1<\/mml:mn>2<\/mml:mn><\/mml:mfrac>Q<\/mml:mi>\u03bc<\/mml:mi><\/mml:msup>\/<\/mml:mo>\u03bc<\/mml:mi>\u03bc<\/mml:mi>+<\/mml:mo>t<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00145-023-09478-y","type":"journal-article","created":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T11:02:27Z","timestamp":1691492547000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Fiat\u2013Shamir Transformation of Multi-Round Interactive Proofs (Extended Version)"],"prefix":"10.1007","volume":"36","author":[{"given":"Thomas","family":"Attema","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Serge","family":"Fehr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Kloo\u00df","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,8,8]]},"reference":[{"key":"9478_CR1","first-page":"513","volume-title":"CRYPTO 2020, Part III, LNCS","author":"T Attema","year":"2020","unstructured":"T. Attema, R. Cramer, Compressed $$\\varSigma $$-protocol theory and practical application to plug & play secure algorithmics, in D. Micciancio, T. Ristenpart, editor, CRYPTO\u00a02020, Part\u00a0III. LNCS, vol. 12172 (Springer, Heidelberg, 2020), pp. 513\u2013543"},{"key":"9478_CR2","doi-asserted-by":"crossref","unstructured":"T. Attema, R. Cramer, L. Kohl, A compressed $$\\varSigma $$-protocol theory for lattices, in T. Malkin, C. Peikert, editors, CRYPTO\u00a02021, Part\u00a0II, Virtual Event, August 2021. LNCS, vol. 12826 (Springer, Heidelberg, 2021), pp. 549\u2013579","DOI":"10.1007\/978-3-030-84245-1_19"},{"key":"9478_CR3","doi-asserted-by":"crossref","unstructured":"T. Attema, R. Cramer, M. Rambaud, Compressed $$\\varSigma $$-protocols for bilinear group arithmetic circuits and application to logarithmic transparent threshold signatures, in M. Tibouchi, H. Wang, editors ASIACRYPT\u00a02021, Part\u00a0IV. LNCS, vol. 13093 (Springer, Heidelberg, 2021), pp. 526\u2013556","DOI":"10.1007\/978-3-030-92068-5_18"},{"issue":"2","key":"9478_CR4","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1145\/214392.214402","volume":"11","author":"JH Ahrens","year":"1985","unstructured":"J.H. Ahrens and U. Dieter. Sequential random sampling. ACM Trans. Math. Softw., 11(2):157\u2013169, 1985","journal-title":"ACM Trans. Math. Softw."},{"key":"9478_CR5","doi-asserted-by":"crossref","unstructured":"T. Attema, S. Fehr, Parallel repetition of $$(k_1,\\dots ,k_{\\mu })$$-special-sound multi-round interactive proofs, in Y. Dodis, T. Shrimpton, editors, CRYPTO. Lecture Notes in Computer Science, vol. 13507(Springer, 2022), pp. 415\u2013443","DOI":"10.1007\/978-3-031-15802-5_15"},{"key":"9478_CR6","doi-asserted-by":"crossref","unstructured":"T. Attema, S. Fehr, M. Kloo\u00df, Fiat-Shamir transformation of multi-round interactive proofs, in Theory of Cryptography Conference (TCC) (2022)","DOI":"10.1007\/978-3-031-22318-1_5"},{"key":"9478_CR7","doi-asserted-by":"crossref","unstructured":"S. Ames, C. Hazay, Y. Ishai, M. Venkitasubramaniam, Ligero: lightweight sublinear arguments without a trusted setup, in B.M. Thuraisingham, D. Evans, T. Malkin, D. Xu, editors, ACM CCS 2017. (ACM Press, October\/November 2017), pp. 2087\u20132104","DOI":"10.1145\/3133956.3134104"},{"key":"9478_CR8","doi-asserted-by":"crossref","unstructured":"M.R. Albrecht, R.W.F. Lai, Subtractive sets over cyclotomic rings - limits of Schnorr-like arguments over lattices, in T. Malkin, C. Peikert, editors, CRYPTO\u00a02021, Part\u00a0II, Virtual Event, August 2021. LNCS, vol. 12826 (Springer, Heidelberg, 2021), pp. 519\u2013548","DOI":"10.1007\/978-3-030-84245-1_18"},{"key":"9478_CR9","doi-asserted-by":"crossref","unstructured":"B. B\u00fcnz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, G. Maxwell, Bulletproofs: Short proofs for confidential transactions and more, in 2018 IEEE Symposium on Security and Privacy. (IEEE Computer Society Press, May 2018), pp. 315\u2013334","DOI":"10.1109\/SP.2018.00020"},{"key":"9478_CR10","doi-asserted-by":"crossref","unstructured":"J. Bootle, A. Cerulli, P. Chaidos, J. Groth, C. Petit, Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting, in M. Fischlin, J.-S. Coron, editors, EUROCRYPT\u00a02016, Part\u00a0II. LNCS, vol. 9666 (Springer, Heidelberg, 2016), pp. 327\u2013357","DOI":"10.1007\/978-3-662-49896-5_12"},{"key":"9478_CR11","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, A. Chiesa, M. Riabzev, N. Spooner, M. Virza, N.P. Ward, Aurora: transparent succinct arguments for R1CS, in Y. Ishai, V. Rijmen, editors, EUROCRYPT\u00a02019, Part\u00a0I. LNCS, vol. 11476 (Springer, Heidelberg, 2019), pp. 103\u2013128","DOI":"10.1007\/978-3-030-17653-2_4"},{"key":"9478_CR12","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, A. Chiesa, N. Spooner, Interactive oracle proofs. in M. Hirt, A.D. Smith, editors, TCC\u00a02016-B, Part\u00a0II. LNCS, vol. 9986 (Springer, Heidelberg, October\/November 2016), pp. 31\u201360","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"9478_CR13","doi-asserted-by":"crossref","unstructured":"B. B\u00fcnz, B. Fisch, A. Szepieniec, Transparent SNARKs from DARK compilers, in A. Canteaut, Y. Ishai, editors, EUROCRYPT\u00a02020, Part\u00a0I. LNCS, vol. 12105 (Springer, Heidelberg, 2020), pp. 677\u2013706","DOI":"10.1007\/978-3-030-45721-1_24"},{"key":"9478_CR14","doi-asserted-by":"crossref","unstructured":"A.R. Block, J. Holmgren, A. Rosen, R.D. Rothblum, P. Soni, Time- and space-efficient arguments from groups of unknown order, in T. Malkin, C, Peikert, editors, CRYPTO\u00a02021, Part\u00a0IV, Virtual Event, August 2021. LNCS, vol. 12828 (Springer, Heidelberg, 2021), pp.123\u2013152","DOI":"10.1007\/978-3-030-84259-8_5"},{"key":"9478_CR15","doi-asserted-by":"crossref","unstructured":"M. Bellare, R. Impagliazzo, M. Naor, Does parallel repetition lower the error in computationally sound protocols? in 38th FOCS, October 1997. (IEEE Computer Society Press, 1997), pp. 374\u2013383","DOI":"10.1109\/SFCS.1997.646126"},{"key":"9478_CR16","doi-asserted-by":"crossref","unstructured":"B. Barak, Y. Lindell, Strict polynomial-time in simulation and extraction, in 34th ACM STOC, May 2002. (ACM Press, 2002), pp. 484\u2013493","DOI":"10.1145\/509907.509979"},{"key":"9478_CR17","doi-asserted-by":"crossref","unstructured":"J. Bootle, V. Lyubashevsky, N.K. Nguyen, G. Seiler, A non-PCP approach to succinct quantum-safe zero-knowledge, in D. Micciancio, T. Ristenpart, editors, CRYPTO\u00a02020, Part\u00a0II. LNCS, vol. 12171 (Springer, Heidelberg, 2020), pp. 441\u2013469","DOI":"10.1007\/978-3-030-56880-1_16"},{"key":"9478_CR18","doi-asserted-by":"crossref","unstructured":"M. Bellare, G. Neven, Multi-signatures in the plain public-key model and a general forking lemma, in A. Juels, R.N. Wright, S. De Capitani di Vimercati, editors, ACM CCS 2006, October\/November 2006, (ACM Press, 2006), pp. 390\u2013399","DOI":"10.1145\/1180405.1180453"},{"key":"9478_CR19","doi-asserted-by":"crossref","unstructured":"R. Canetti, Y. Chen, J. Holmgren, A. Lombardi, G.N. Rothblum, R.D. Rothblum, D. Wichs, Fiat\u2013Shamir: from practice to theory, in M. Charikar, E. Cohen, editors, 51st ACM STOC, June 2019. (ACM Press, 2019), pp. 1082\u20131090","DOI":"10.1145\/3313276.3316380"},{"key":"9478_CR20","doi-asserted-by":"crossref","unstructured":"A. Chiesa, P. Manohar, N. Spooner, Succinct arguments in the quantum random oracle model, in D. Hofheinz, A. Rosen, editors, TCC\u00a02019, Part\u00a0II. LNCS, vol. 11892 (Springer, Heidelberg, 2019), pp. 1\u201329","DOI":"10.1007\/978-3-030-36033-7_1"},{"key":"9478_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8643-8","volume-title":"Non-Uniform Random Variate Generation","author":"L Devroye","year":"1986","unstructured":"L. Devroye. Non-Uniform Random Variate Generation. (Springer, Berlin, 1986)"},{"key":"9478_CR22","doi-asserted-by":"crossref","unstructured":"J. Don, S. Fehr, C. Majenz, C. Schaffner, Security of the Fiat\u2013Shamir transformation in the quantum random-oracle model, in A. Boldyreva, D. Micciancio, editors, CRYPTO\u00a02019, Part\u00a0II. LNCS, vol. 11693 (Springer, Heidelberg, 2019), pp. 356\u2013383","DOI":"10.1007\/978-3-030-26951-7_13"},{"key":"9478_CR23","doi-asserted-by":"crossref","unstructured":"R. del Pino, V. Lyubashevsky, G. Seiler, Short discrete log proofs for FHE and ring-LWE ciphertexts, in D. Lin, K. Sako, editors, PKC\u00a02019, Part\u00a0I. LNCS, vol. 11442 (Springer, Heidelberg, 2019), pp. 344\u2013373","DOI":"10.1007\/978-3-030-17253-4_12"},{"key":"9478_CR24","doi-asserted-by":"crossref","unstructured":"A. Fiat, A. Shamir, How to prove yourself: pactical solutions to identification and signature problems, in A.M. Odlyzko, editor, CRYPTO\u201986, LNCS, vol. 263. (Springer, Heidelberg, 1987), pp. 186\u2013194","DOI":"10.1007\/3-540-47721-7_12"},{"key":"9478_CR25","doi-asserted-by":"crossref","unstructured":"C. Gentry, S. Halevi, V. Lyubashevsky, Practical non-interactive publicly verifiable secret sharing with thousands of parties, in O. Dunkelman, S. Dziembowski, editors, EUROCRYPT\u00a02022, Part\u00a0I, May\/June 2022. LNCS, vol. 13275 (Springer, Heidelberg, 2022), pp. 458\u2013487.","DOI":"10.1007\/978-3-031-06944-4_16"},{"key":"9478_CR26","doi-asserted-by":"crossref","unstructured":"C. Ganesh, H. Khoshakhlagh, M. Kohlweiss, A. Nitulescu, M. Zajac, What makes Fiat\u2013Shamir zkSNARKs (updatable SRS) simulation extractable? in SCN. Lecture Notes in Computer Science, vol. 13409 (Springer, Berlin, 2022), pp. 735\u2013760","DOI":"10.1007\/978-3-031-14791-3_32"},{"key":"9478_CR27","doi-asserted-by":"crossref","unstructured":"A. Ghoshal, S. Tessaro, Tight state-restoration soundness in the algebraic group model, in T. Malkin, C. Peikert, editors, CRYPTO\u00a02021, Part\u00a0III, Virtual Event, August 2021. LNCS, vol. 12827 (Springer, Heidelberg, 2021), pp. 64\u201393","DOI":"10.1007\/978-3-030-84252-9_3"},{"key":"9478_CR28","doi-asserted-by":"crossref","unstructured":"M. Hoffmann, M. Kloo\u00df, A. Rupp, Efficient zero-knowledge arguments in the discrete log setting, revisited. in L. Cavallaro, J. Kinder, X. Wang, J. Katz, editors, ACM CCS 2019, November 2019 (ACM Press, 2019), pp. 2093\u20132110","DOI":"10.1145\/3319535.3354251"},{"issue":"6","key":"9478_CR29","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1145\/367766.368159","volume":"5","author":"TG Jones","year":"1962","unstructured":"T.G. Jones. A Note on Sampling a Tape-File. Commun. ACM, 5(6):343, 1962.","journal-title":"Commun. ACM"},{"key":"9478_CR30","doi-asserted-by":"crossref","unstructured":"J. Jaeger, S. Tessaro. Expected-time cryptography: generic techniques and applications to concrete soundness, in R. Pass, K. Pietrzak, editors, TCC\u00a02020, Part\u00a0III, LNCS, vol. 12552 (Springer, Heidelberg, 2020), pp. 414\u2013443","DOI":"10.1007\/978-3-030-64381-2_15"},{"key":"9478_CR31","volume-title":"The Art of Computer Programming, Volume II: Seminumerical Algorithms","author":"DE Knuth","year":"1969","unstructured":"D.E. Knuth. The Art of Computer Programming, Volume II: Seminumerical Algorithms. Addison-Wesley, Boston 1969."},{"key":"9478_CR32","doi-asserted-by":"crossref","unstructured":"M. Maller, S. Bowe, M. Kohlweiss, S. Meiklejohn, Sonic: zero-knowledge SNARKs from linear-size universal and updatable structured reference strings, in L. Cavallaro, J. Kinder, X. Wang, J. Katz, editors, ACM CCS, November 2019, (ACM Press, 2019), pp. 2111\u20132128","DOI":"10.1145\/3319535.3339817"},{"key":"9478_CR33","doi-asserted-by":"crossref","unstructured":"D. Pointcheval, J. Stern, Security proofs for signature schemes, in U.M. Maurer, editor, EUROCRYPT\u201996. vol. 1070, LNCS. (Springer, Heidelberg, 1996), pp. 387\u2013398","DOI":"10.1007\/3-540-68339-9_33"},{"key":"9478_CR34","doi-asserted-by":"crossref","unstructured":"D. Unruh, Post-quantum security of Fiat\u2013Shamir, in T. Takagi. T. Peyrin, editors, ASIACRYPT\u00a02017, Part\u00a0I, December 2017. LNCS, vol. 10624. (Springer, Heidelberg, 2017).","DOI":"10.1007\/978-3-319-70694-8_3"},{"issue":"1","key":"9478_CR35","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1145\/23002.23003","volume":"13","author":"Jeffrey Scott Vitter","year":"1987","unstructured":"J.S. Vitter, An efficient algorithm for sequential random sampling. ACM Trans. Math. Softw., 13(1):58\u201367, 1987.","journal-title":"ACM Trans. Math. Softw."},{"key":"9478_CR36","unstructured":"D. Wikstr\u00f6m, Special soundness revisited. Cryptology ePrint Archive, Report 2018\/1157, 2018. https:\/\/eprint.iacr.org\/2018\/1157"},{"key":"9478_CR37","unstructured":"D. Wikstr\u00f6m, Special soundness in the random oracle model. Cryptology ePrint Archive, Report 2021\/1265, 2021. https:\/\/eprint.iacr.org\/2021\/1265."},{"key":"9478_CR38","doi-asserted-by":"crossref","unstructured":"R.S. Wahby, I. Tzialla, A. Shelat, J. Thaler, M. Walfish, Doubly-efficient zkSNARKs without trusted setup, in 2018 IEEE Symposium on Security and Privacy, May 2018 (IEEE Computer Society Press, 2018), pp. 926\u2013943","DOI":"10.1109\/SP.2018.00060"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09478-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-023-09478-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09478-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T21:28:11Z","timestamp":1729891691000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-023-09478-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,8]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["9478"],"URL":"https:\/\/doi.org\/10.1007\/s00145-023-09478-y","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,8]]},"assertion":[{"value":"14 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 June 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 July 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 August 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"36"}}