{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T10:14:41Z","timestamp":1772878481330,"version":"3.50.1"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031780103","type":"print"},{"value":"9783031780110","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T00:00:00Z","timestamp":1733097600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T00:00:00Z","timestamp":1733097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-78011-0_6","type":"book-chapter","created":{"date-parts":[[2024,12,1]],"date-time":"2024-12-01T20:01:58Z","timestamp":1733083318000},"page":"158-188","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Untangling the\u00a0Security of\u00a0Kilian\u2019s Protocol: Upper and\u00a0Lower Bounds"],"prefix":"10.1007","author":[{"given":"Alessandro","family":"Chiesa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcel","family":"Dall\u2019Agnol","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziyi","family":"Guan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicholas","family":"Spooner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eylon","family":"Yogev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,2]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Attema, T., Cramer, R.: Compressed $$\\sigma $$-protocol theory and practical application to plug & play secure algorithmics. In: Proceedings of the 40th Annual International Cryptology Conference, pp. 513\u2013543. CRYPTO\u00a02020 (2020)","DOI":"10.1007\/978-3-030-56877-1_18"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Attema, T., Cramer, R., Kohl, L.: A compressed $$\\sigma $$-protocol theory for lattices. In: Proceedings of the 41st Annual International Cryptology Conference, pp. 549\u2013579. CRYPTO\u00a02021 (2022)","DOI":"10.1007\/978-3-030-84245-1_19"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Attema, T., Fehr, S.: Parallel repetition of $$(k_1, \\ldots , k_\\mu )$$-special-sound multi-round interactive proofs. In: Proceedings of the 42nd Annual International Cryptology Conference, pp. 415\u2013443. CRYPTO\u00a02022 (2022)","DOI":"10.1007\/978-3-031-15802-5_15"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Barak, B., Goldreich, O.: Universal arguments and their applications. SIAM J. Comput. 38(5), 1661\u20131694 (2008). preliminary version appeared in CCC\u00a02002","DOI":"10.1137\/070709244"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Bellare, M., Dai, W.: The multi-base discrete logarithm problem: tight reductions and non-rewinding proofs for Schnorr identification and signatures. In: Progress in Cryptology \u2013 INDOCRYPT 2020. pp. 529\u2013552 (2020)","DOI":"10.1007\/978-3-030-65277-7_24"},{"key":"6_CR6","doi-asserted-by":"publisher","unstructured":"Bellare, M., Palacio, A.: GQ and schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks. In: Yung, M. (ed.) Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, 18-22 August 2002, Proceedings. Lecture Notes in Computer Science, vol.\u00a02442, pp. 162\u2013177. Springer (2002). https:\/\/doi.org\/10.1007\/3-540-45708-9_11","DOI":"10.1007\/3-540-45708-9_11"},{"key":"6_CR7","doi-asserted-by":"publisher","unstructured":"Ben-David, S.: Probabilistically checkable arguments for all NP. In: Joye, M., Leander, G. (eds.) Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, 26-30 May 2024, Proceedings, Part III. Lecture Notes in Computer Science, vol. 14653, pp. 345\u2013374. Springer (2024). https:\/\/doi.org\/10.1007\/978-3-031-58734-4_12","DOI":"10.1007\/978-3-031-58734-4_12"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Proceedings of the 14th Theory of Cryptography Conference, pp. 31\u201360. TCC\u00a02016-B (2016)","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Kaplan, Y., Kopparty, S., Meir, O., Stichtenoth, H.: Constant rate PCPs for Circuit-SAT with sublinear query complexity. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pp. 320\u2013329. FOCS\u00a02013 (2013)","DOI":"10.1109\/FOCS.2013.42"},{"issue":"4","key":"6_CR10","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1002\/rsa.20120","volume":"28","author":"E Ben-Sasson","year":"2006","unstructured":"Ben-Sasson, E., Sudan, M.: Robust locally testable codes and products of codes. Random Struct. Algorithms 28(4), 387\u2013402 (2006)","journal-title":"Random Struct. Algorithms"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Block, A.R., Garreta, A., Tiwari, P.R., Zajac, M.: On soundness notions for interactive oracle proofs, p.\u00a01256 (2023)","DOI":"10.1007\/s00145-024-09520-7"},{"key":"6_CR12","unstructured":"Bronfman, L., Rothblum, R.D.: PCPS and instance compression from a cryptographic lens. In: Braverman, M. (ed.) 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA. LIPIcs, vol.\u00a0215, pp. 30:1\u201330:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Catalano, D., Fiore, D.: Vector commitments and their applications. In: Proceedings of the 16th International Conference on Practice and Theory in Public Key Cryptography, pp. 55\u201372. PKC\u00a02013 (2013)","DOI":"10.1007\/978-3-642-36362-7_5"},{"key":"6_CR14","unstructured":"Chiesa, A., Dall\u2019Agnol, M., Guan, Z., Spooner, N., Yogev, E.: Untangling the security of Kilian\u2019s protocol: upper and lower bounds. IACR Cryptol. ePrint Arch., 1434 (2024). https:\/\/eprint.iacr.org\/2024\/1434"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Chiesa, A., Ma, F., Spooner, N., Zhandry, M.: Post-quantum succinct arguments: breaking the quantum rewinding barrier. In: Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science, pp. 49\u201358. FOCS\u00a02021 (2021)","DOI":"10.1109\/FOCS52979.2021.00014"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Chiesa, A., Manohar, P., Spooner, N.: Succinct arguments in the quantum random oracle model. In: Proceedings of the 17th Theory of Cryptography Conference, pp. 1\u201329. TCC\u00a02019 (2019), available as Cryptology ePrint Archive, Report 2019\/834","DOI":"10.1007\/978-3-030-36033-7_1"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Chiesa, A., Yogev, E.: In: Proceedings of the 41st Annual International Cryptology Conference, pp. 711\u2013741. CRYPTO\u00a02021 (2021)","DOI":"10.1007\/978-3-030-84242-0_25"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Chiesa, A., Yogev, E.: Tight security bounds for micali\u2019s SNARGs. In: Proceedings of the 19th Theory of Cryptography Conference, pp. 401\u2013434. TCC\u00a02021 (2021)","DOI":"10.1007\/978-3-030-90459-3_14"},{"key":"6_CR19","unstructured":"Chiesa, A., Yogev, E.: Building cryptographic proofs from hash functions (2024). https:\/\/github.com\/hash-based-snargs-book"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Fuchsbauer, G., Plouviez, A., Seurin, Y.: Blind Schnorr signatures and signed ElGamal encryption in the algebraic group model. In: Advances in Cryptology \u2013 EUROCRYPT 2020, pp. 63\u201395 (2020)","DOI":"10.1007\/978-3-030-45724-2_3"},{"key":"6_CR21","unstructured":"Ishai, Y., Mahmoody, M., Sahai, A., Xiao, D.: On zero-knowledge PCPs: limitations, simplifications, and applications (2015). http:\/\/www.cs.virginia.edu\/~mohammad\/files\/papers\/ZKPCPs-Full.pdf"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Raz, R.: Probabilistically checkable arguments. In: Proceedings of the 29th Annual International Cryptology Conference, pp. 143\u2013159. CRYPTO\u00a02009 (2009)","DOI":"10.1007\/978-3-642-03356-8_9"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pp. 723\u2013732. STOC\u00a01992 (1992)","DOI":"10.1145\/129712.129782"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Kilian, J., Petrank, E., Tardos, G.: Probabilistically checkable proofs with zero knowledge. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 496\u2013505. STOC\u00a01997 (1997)","DOI":"10.1145\/258533.258643"},{"key":"6_CR25","unstructured":"Krenn, S., Orr\u00f9, M.: Proposal: $$\\sigma $$-protocols (2021). https:\/\/docs.zkproof.org\/pages\/standards\/accepted-workshop4\/proposal-sigma.pdf"},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"Lai, R.W.F., Malavolta, G.: Subvector commitments with application to succinct arguments. In: Proceedings of the 39th Annual International Cryptology Conference, pp. 530\u2013560. CRYPTO\u00a02019 (2019)","DOI":"10.1007\/978-3-030-26948-7_19"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Lombardi, A., Ma, F., Spooner, N.: Post-quantum zero knowledge, revisited or: how to do quantum rewinding undetectably. In: Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science, pp. 851\u2013859. FOCS\u00a02022 (2022)","DOI":"10.1109\/FOCS54457.2022.00086"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253\u20131298 (2000. preliminary version appeared in FOCS\u00a01994","DOI":"10.1137\/S0097539795284959"},{"key":"6_CR29","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/s001450010003","volume":"13","author":"D Pointcheval","year":"2000","unstructured":"Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. J. Cryptol. 13, 361\u2013396 (2000)","journal-title":"J. Cryptol."},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Rotem, L., Segev, G.: Tighter security for schnorr identification and signatures: a high-moment forking lemma for $$\\sigma $$-protocols. In: Proceedings of the 41st Annual International Cryptology Conference, pp. 222\u2013250. CRYPTO\u00a02021 (2021)","DOI":"10.1007\/978-3-030-84242-0_9"},{"key":"6_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-030-17253-4_13","volume-title":"Public-Key Cryptography \u2013 PKC 2019","author":"A Scafuro","year":"2019","unstructured":"Scafuro, A., Siniscalchi, L., Visconti, I.: Publicly verifiable proofs from blockchains. In: Lin, D., Sako, K. (eds.) PKC 2019. LNCS, vol. 11442, pp. 374\u2013401. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17253-4_13"},{"key":"6_CR32","doi-asserted-by":"publisher","unstructured":"Scafuro, A., Siniscalchi, L., Visconti, I.: Publicly verifiable zero knowledge from (collapsing) blockchains. In: Garay, J.A. (ed.) Public-Key Cryptography - PKC 2021 - 24th IACR International Conference on Practice and Theory of Public Key Cryptography, Virtual Event, 10-13 May 2021, Proceedings, Part II. LNCS, vol. 12711, pp. 469\u2013498. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-75248-4_17","DOI":"10.1007\/978-3-030-75248-4_17"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Proceedings of the 9th Annual International Cryptology Conference, pp. 239\u2013252. CRYPTO\u00a0\u201989 (1989)","DOI":"10.1007\/0-387-34805-0_22"},{"issue":"3","key":"6_CR34","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00196725","volume":"4","author":"CP Schnorr","year":"1991","unstructured":"Schnorr, C.P.: Efficient signature generation by smart cards. J. Cryptol. 4(3), 161\u2013174 (1991)","journal-title":"J. Cryptol."},{"key":"6_CR35","doi-asserted-by":"crossref","unstructured":"Segev, G., Sharabi, A., Yogev, E.: Rogue-instance security for batch knowledge proofs. In: Proceedings of the 23th Theory of Cryptography Conference, pp. 121\u2013157. TCC\u00a02023 (2023)","DOI":"10.1007\/978-3-031-48615-9_5"},{"key":"6_CR36","doi-asserted-by":"crossref","unstructured":"Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Proceedings of the 16th International Conference on the Theory and Application of Cryptographic Techniques, pp. 256\u2013266. EUROCRYPT\u00a01997 (1997)","DOI":"10.1007\/3-540-69053-0_18"},{"key":"6_CR37","doi-asserted-by":"crossref","unstructured":"Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time\/space efficiency. In: Proceedings of the 5th Theory of Cryptography Conference, pp. 1\u201318. TCC\u00a02008 (2008)","DOI":"10.1007\/978-3-540-78524-8_1"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-78011-0_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,1]],"date-time":"2024-12-01T20:02:16Z","timestamp":1733083336000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-78011-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,2]]},"ISBN":["9783031780103","9783031780110"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-78011-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,2]]},"assertion":[{"value":"2 December 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Milan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 December 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 December 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}