{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:20:37Z","timestamp":1761621637595,"version":"build-2065373602"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,8,12]],"date-time":"2025-08-12T00:00:00Z","timestamp":1754956800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,12]],"date-time":"2025-08-12T00:00:00Z","timestamp":1754956800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Weizmann Institute of Science"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2025,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>It is well known that several cryptographic primitives cannot be achieved without a common reference string (CRS). Those include, for instance, non-interactive zero-knowledge for NP, or maliciously secure computation in fewer than four rounds. The security of those primitives heavily relies on the assumption that the trusted authority, who generates the CRS, does not misuse the randomness used in the CRS generation. However, we argue that there is no such thing as an unconditionally trusted authority and every authority must be held accountable for any trust to be well-founded. Indeed, a malicious authority can, for instance, recover private inputs of honest parties given transcripts of the protocols executed with respect to the CRS it has generated. While eliminating trust in the trusted authority may not be entirely feasible, can we at least move towards achieving some notion of accountability? We propose a new notion in which, if the CRS authority releases the private inputs of protocol executions to others, we can then provide a publicly-verifiable proof that certifies that the authority misbehaved.  We study the feasibility of this notion in the context of non-interactive zero knowledge and two-round secure two-party computation.<\/jats:p>","DOI":"10.1007\/s00145-025-09548-3","type":"journal-article","created":{"date-parts":[[2025,8,12]],"date-time":"2025-08-12T19:27:02Z","timestamp":1755026822000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Towards Accountability in CRS Generation"],"prefix":"10.1007","volume":"38","author":[{"given":"Prabhanjan","family":"Ananth","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0846-9773","authenticated-orcid":false,"given":"Gilad","family":"Asharov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hila","family":"Dahari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vipul","family":"Goyal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,12]]},"reference":[{"key":"9548_CR1","doi-asserted-by":"crossref","unstructured":"P. Ananth, A.R. Choudhuri, A. Jain, A new approach to round-optimal secure multiparty computation. in Annual International Cryptology Conference, (Springer, 2017). pp. 468\u2013499","DOI":"10.1007\/978-3-319-63688-7_16"},{"key":"9548_CR2","doi-asserted-by":"crossref","unstructured":"P. Ananth, A. Deshpande, Y.T. Kalai, A. Lysyanskaya, Fully homomorphic NIZK and NIWI proofs. in Theory of Cryptography TCC 2019, vol. 11892 (Springer, 2019), pp. 356\u2013385","DOI":"10.1007\/978-3-030-36033-7_14"},{"key":"9548_CR3","doi-asserted-by":"crossref","unstructured":"G. Asharov, C. Orlandi, Calling out cheaters: covert security with public verifiability. in Advances in Cryptology\u2014ASIACRYPT 2012, vol. 7658, (Springer, 2012), pp. 681\u2013698","DOI":"10.1007\/978-3-642-34961-4_41"},{"key":"9548_CR4","unstructured":"Z. Brakerski, N. D\u00f6ttling, S. Garg, G. Malavolta, Factoring and pairings are not necessary for IO: circular-secure LWE suffices. IACR Cryptol. ePrint Arch., 2020: 1024 (2020)"},{"key":"9548_CR5","doi-asserted-by":"crossref","unstructured":"M. Blum, P. Feldman, S. Micali, Non-interactive zero-knowledge and its applications (extended abstract). in Symposium on Theory of Computing (STOC), (ACM, 1988), pp. 103\u2013112.","DOI":"10.1145\/62212.62222"},{"key":"9548_CR6","doi-asserted-by":"crossref","unstructured":"M. Bellare, G. Fuchsbauer, A. Scafuro, Nizks with an untrusted CRS: security in the face of parameter subversion. in Adv. Cryptol. ASIACRYPT 2016, 10032: 777\u2013804 (2016)","DOI":"10.1007\/978-3-662-53890-6_26"},{"key":"9548_CR7","doi-asserted-by":"crossref","unstructured":"B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, K. Yang, On the (IM) possibility of obfuscating programs. in CRYPTO, (Springer, 2001), pp. 1\u201318","DOI":"10.1007\/3-540-44647-8_1"},{"key":"9548_CR8","doi-asserted-by":"crossref","unstructured":"B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S.P. Vadhan, K. Yang, On the (IM)possibility of obfuscating programs. in Advances in Cryptology\u2014CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19\u201323, 2001, Proceedings, volume 2139 of Lecture Notes in Computer Science, (Springer, 2001), pp. 1\u201318.","DOI":"10.1007\/3-540-44647-8_1"},{"key":"9548_CR9","doi-asserted-by":"crossref","unstructured":"S. Badrinarayanan, V. Goyal, A. Jain, Y.T. Kalai, D. Khurana, A. Sahai, Promise zero knowledge and its applications to round optimal MPC. In Annual International Cryptology Conference, (Springer, 2018), pp. 459\u2013487","DOI":"10.1007\/978-3-319-96881-0_16"},{"key":"9548_CR10","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, S. Halevi, A. Polychroniadou, Four round secure computation without setup. in Theory of Cryptography Conference, (Springer, 2017), pp. 645\u2013677","DOI":"10.1007\/978-3-319-70500-2_22"},{"key":"9548_CR11","doi-asserted-by":"crossref","unstructured":"F. Benhamouda, H. Lin, k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits. in Annual International Conference on the Theory and Applications of Cryptographic Techniques, (Springer, 2018), pp. 500\u2013532","DOI":"10.1007\/978-3-319-78375-8_17"},{"key":"9548_CR12","doi-asserted-by":"crossref","unstructured":"B. Barak, S.J. Ong, S.P. Vadhan, Derandomization in cryptography. in Advances in Cryptology\u2014CRYPTO 2003, vol. 2729 (Springer, 2003), pp. 299\u2013315","DOI":"10.1007\/978-3-540-45146-4_18"},{"issue":"1","key":"9548_CR13","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R Canetti","year":"2000","unstructured":"R. Canetti, Security and composition of multiparty cryptographic protocols. J. Cryptol., 13(1), 143\u2013202 (2000)","journal-title":"J. Cryptol."},{"key":"9548_CR14","doi-asserted-by":"crossref","unstructured":"A.R. Choudhuri, M. Ciampi, V. Goyal, A. Jain, R. Ostrovsky, Round optimal secure multiparty computation from minimal assumptions. in Theory of Cryptography\u2014TCC \u201920, 2020. to appear.","DOI":"10.1007\/978-3-030-64378-2_11"},{"key":"9548_CR15","doi-asserted-by":"crossref","unstructured":"R. Canetti, M. Fischlin, Universally composable commitments. in Annual International Cryptology Conference, (Springer, 2001), pp. 19\u201340","DOI":"10.1007\/3-540-44647-8_2"},{"key":"9548_CR16","doi-asserted-by":"crossref","unstructured":"B. Chor, A. Fiat, M. Naor, Tracing traitors. in Advances in Cryptology\u2014CRYPTO \u201994, vol. 839, (Springer, 1994), pp. 257\u2013270.","DOI":"10.1007\/3-540-48658-5_25"},{"key":"9548_CR17","doi-asserted-by":"crossref","unstructured":"R. Canetti, E. Kushilevitz, Y. Lindell, On the limitations of universally composable two-party computation without set-up assumptions. in International Conference on the Theory and Applications of Cryptographic Techniques, (Springer, 2003), pp. 68\u201386","DOI":"10.1007\/3-540-39200-9_5"},{"key":"9548_CR18","doi-asserted-by":"crossref","unstructured":"R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai, Universally composable two-party and multi-party secure computation. in ACM Symposium on Theory of Computing (STOC), (2002), pp. 494\u2013503","DOI":"10.1145\/509907.509980"},{"key":"9548_CR19","doi-asserted-by":"crossref","unstructured":"C. Dwork, M. Naor, Zaps and their applications. in Found. Comput. Sci. FOCS, 283\u2013293 (2000)","DOI":"10.1109\/SFCS.2000.892117"},{"issue":"1","key":"9548_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539792230010","volume":"29","author":"Uriel Feige","year":"1999","unstructured":"U. Feige, D. Lapidot, A. Shamir, Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput., 29(1), 1\u201328, (1999)","journal-title":"SIAM J. Comput."},{"key":"9548_CR21","doi-asserted-by":"crossref","unstructured":"G. Fuchsbauer, Subversion-zero-knowledge snarks. in Public-Key Cryptography\u2014PKC 2018, vol 10769, (Springer, 2018), pp. 315\u2013347","DOI":"10.1007\/978-3-319-76578-5_11"},{"issue":"3","key":"9548_CR22","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1137\/14095772X","volume":"45","author":"S Garg","year":"2016","unstructured":"S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, B. Waters, Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM J. Comput., 45(3), 882\u2013929 (2016)","journal-title":"SIAM J. Comput."},{"key":"9548_CR23","doi-asserted-by":"crossref","unstructured":"S. Garg, V. Goyal, A. Jain, A. Sahai, Bringing people of different beliefs together to do UC. in Theory of Cryptography - TCC 2011, vol 6597, (Springer, 2011), pp. 311\u2013328","DOI":"10.1007\/978-3-642-19571-6_19"},{"key":"9548_CR24","doi-asserted-by":"crossref","unstructured":"V. Goyal, J. Katz, Universally composable multi-party computation with an unreliable common reference string. in Theory of Cryptography, TCC 2008, vol. 4948, (Springer, 2008), pp. 142\u2013154","DOI":"10.1007\/978-3-540-78524-8_9"},{"issue":"1","key":"9548_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00195207","volume":"7","author":"O Goldreich","year":"1994","unstructured":"O. Goldreich, Y. Oren, Definitions and properties of zero-knowledge proof systems. J. Cryptol., 7(1), 1\u201332, (1994).","journal-title":"J. Cryptol."},{"key":"9548_CR26","doi-asserted-by":"crossref","unstructured":"J. Groth, R. Ostrovsky, Cryptography in the multi-string model. in CRYPTO 2007, vol. 4622, (Springer, 2007) pp. 323\u2013341","DOI":"10.1007\/978-3-540-74143-5_18"},{"key":"9548_CR27","doi-asserted-by":"crossref","unstructured":"J. Groth, R. Ostrovsky, A. Sahai, Non-interactive zaps and new techniques for NIZK. in CRYPTO 2006, vol 4117 (Springer, 2006), pp. 97\u2013111","DOI":"10.1007\/11818175_6"},{"key":"9548_CR28","doi-asserted-by":"crossref","unstructured":"V. Goyal, Reducing trust in the PKG in identity based cryptosystems. in CRYPTO 2007, vol 4622, (Springer, 2007), pp. 430\u2013447","DOI":"10.1007\/978-3-540-74143-5_24"},{"key":"9548_CR29","doi-asserted-by":"crossref","unstructured":"R. Gay, R. Pass, Indistinguishability obfuscation from circular security. in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, (2021), pp. 736\u2013749","DOI":"10.1145\/3406325.3451070"},{"key":"9548_CR30","doi-asserted-by":"crossref","unstructured":"J. Groth, A. Sahai, Efficient non-interactive proof systems for bilinear groups. in N.P. Smart, editor, Advances in Cryptology\u2014EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13\u201317, 2008. Proceedings, volume 4965 of Lecture Notes in Computer Science, (Springer, 2008), pp. 415\u2013432","DOI":"10.1007\/978-3-540-78967-3_24"},{"key":"9548_CR31","doi-asserted-by":"crossref","unstructured":"S. Garg, A. Srinivasan, Two-round multiparty secure computation from minimal assumptions. in Theory Appl. Cryptograph. Tech. (TCC), 468\u2013499 (2018)","DOI":"10.1007\/978-3-319-78375-8_16"},{"key":"9548_CR32","doi-asserted-by":"crossref","unstructured":"S. Halevi, C. Hazay, A. Polychroniadou, M. Venkitasubramaniam, Round-optimal secure multi-party computation. in Annual International Cryptology Conference, (Springer, 2018), pp. 488\u2013520","DOI":"10.1007\/978-3-319-96881-0_17"},{"key":"9548_CR33","doi-asserted-by":"crossref","unstructured":"O. Horvitz, J. Katz, Universally-composable two-party computation in two rounds. in A. Menezes, editor, Advances in Cryptology\u2014CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings, volume 4622 of Lecture Notes in Computer Science, (Springer, 2007), pp. 111\u2013129","DOI":"10.1007\/978-3-540-74143-5_7"},{"key":"9548_CR34","doi-asserted-by":"crossref","unstructured":"A. Jain, H. Lin, A. Sahai, Indistinguishability obfuscation from well-founded assumptions. in S. Khuller, V.V. Williams, editors, STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21\u201325, 2021, (ACM, 2021), pp. 60\u201373","DOI":"10.1145\/3406325.3451093"},{"key":"9548_CR35","doi-asserted-by":"crossref","unstructured":"J. Katz, R. Ostrovsky, Round-optimal secure two-party computation. in Annual International Cryptology Conference, (Springer, 2004), pp. 335\u2013354","DOI":"10.1007\/978-3-540-28628-8_21"},{"key":"9548_CR36","doi-asserted-by":"crossref","unstructured":"E. Kiltz, J. Pan, H. Wee, Structure-preserving signatures from standard assumptions, revisited. in Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology\u2014CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16\u201320, 2015, Proceedings, Part II, volume 9216 of Lecture Notes in Computer Science, (Springer, 2015) pp. 275\u2013295,","DOI":"10.1007\/978-3-662-48000-7_14"},{"key":"9548_CR37","doi-asserted-by":"crossref","unstructured":"M. Luby, Pseudorandomness and cryptographic applications. Princeton computer science notes. (Princeton University Press, Princeton, 1996)","DOI":"10.1515\/9780691206844"},{"key":"9548_CR38","doi-asserted-by":"crossref","unstructured":"P. Mukherjee, D. Wichs, Two round multiparty computation via multi-key FHE. in Advances in Cryptology\u2014EUROCRYPT 2016, vol. 9666 (Springer, 2016), pp. 735\u2013763","DOI":"10.1007\/978-3-662-49896-5_26"},{"key":"9548_CR39","doi-asserted-by":"crossref","unstructured":"R. Pass, Simulation in quasi-polynomial time, and its application to protocol composition. in Advances in Cryptology\u2014EUROCRYPT 2003, vol. 2656, (Springer, 2003), pp. 160\u2013176","DOI":"10.1007\/3-540-39200-9_10"},{"key":"9548_CR40","doi-asserted-by":"crossref","unstructured":"C. Peikert, V. Vaikuntanathan, B. Waters, A framework for efficient and composable oblivious transfer. in Advances in Cryptology\u2014CRYPTO 2008, vol. 5157 (Springer, 2008), pp. 554\u2013571","DOI":"10.1007\/978-3-540-85174-5_31"},{"issue":"3","key":"9548_CR41","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1137\/15M1030108","volume":"50","author":"A Sahai","year":"2021","unstructured":"A. Sahai, B. Waters, How to use indistinguishability obfuscation: deniable encryption, and more. SIAM J. Comput., 50(3), 857\u2013908, (2021).","journal-title":"SIAM J. Comput."},{"key":"9548_CR42","doi-asserted-by":"crossref","unstructured":"H. Wee, D. Wichs, Candidate obfuscation via oblivious LWE sampling. in Annual International Conference on the Theory and Applications of Cryptographic Techniques, (Springer, 2021), pp. 127\u2013156","DOI":"10.1007\/978-3-030-77883-5_5"},{"key":"9548_CR43","doi-asserted-by":"crossref","unstructured":"A.C.C. Yao, How to generate and exchange secrets (extended abstract). in 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27\u201329 October 1986, (IEEE Computer Society, 1986), pp. 162\u2013167","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-025-09548-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-025-09548-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-025-09548-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:16:27Z","timestamp":1761621387000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-025-09548-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,12]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["9548"],"URL":"https:\/\/doi.org\/10.1007\/s00145-025-09548-3","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"type":"print","value":"0933-2790"},{"type":"electronic","value":"1432-1378"}],"subject":[],"published":{"date-parts":[[2025,8,12]]},"assertion":[{"value":"26 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"29"}}