{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:01:34Z","timestamp":1778292094216,"version":"3.51.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T00:00:00Z","timestamp":1732579200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T00:00:00Z","timestamp":1732579200000},"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":["J Cryptol"],"published-print":{"date-parts":[[2025,1]]},"DOI":"10.1007\/s00145-024-09532-3","type":"journal-article","created":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T17:34:18Z","timestamp":1732642458000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Compact Proofs of Partial Knowledge for Overlapping CNF Formulae"],"prefix":"10.1007","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-6975-0851","authenticated-orcid":false,"given":"Gennaro","family":"Avitabile","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0557-9969","authenticated-orcid":false,"given":"Vincenzo","family":"Botta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0836-1735","authenticated-orcid":false,"given":"Daniele","family":"Friolo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2379-8564","authenticated-orcid":false,"given":"Daniele","family":"Venturi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2381-5846","authenticated-orcid":false,"given":"Ivan","family":"Visconti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,26]]},"reference":[{"key":"9532_CR1","doi-asserted-by":"crossref","unstructured":"Masayuki Abe, Miguel Ambrona, Andrej Bogdanov, Miyako Ohkubo, and Alon Rosen. Non-interactive composition of sigma-protocols via share-then-hash. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT\u00a02020, Part\u00a0III, volume 12493 of LNCS, pages 749\u2013773, Daejeon, South Korea, December\u00a07\u201311, 2020. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-030-64840-4_25"},{"key":"9532_CR2","doi-asserted-by":"crossref","unstructured":"Masayuki Abe, Miguel Ambrona, Andrej Bogdanov, Miyako Ohkubo, and Alon Rosen. Acyclicity programming for sigma-protocols. In Kobbi Nissim and Brent Waters, editors, TCC\u00a02021, Part\u00a0I, volume 13042 of LNCS, pages 435\u2013465, Raleigh, NC, USA, November\u00a08\u201311, 2021. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-030-90459-3_15"},{"key":"9532_CR3","doi-asserted-by":"crossref","unstructured":"Masayuki Abe, Miyako Ohkubo, and Koutarou Suzuki. 1-out-of-n signatures from a variety of keys. In Yuliang Zheng, editor, ASIACRYPT\u00a02002, volume 2501 of LNCS, pages 415\u2013432, Queenstown, New Zealand, December\u00a01\u20135, 2002. Springer, Heidelberg, Germany.","DOI":"10.1007\/3-540-36178-2_26"},{"key":"9532_CR4","doi-asserted-by":"crossref","unstructured":"Thomas Attema, Ronald Cramer, and Serge Fehr. Compressing proofs of k-out-of-n partial knowledge. In Tal Malkin and Chris Peikert, editors, CRYPTO\u00a02021, Part\u00a0IV, volume 12828 of LNCS, pages 65\u201391, Virtual Event, August\u00a016\u201320, 2021. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-030-84259-8_3"},{"key":"9532_CR5","doi-asserted-by":"crossref","unstructured":"Gennaro Avitabile, Vincenzo Botta, Daniele Friolo, and Ivan Visconti. Efficient proofs of knowledge for threshold relations. In Vijayalakshmi Atluri, Roberto Di Pietro, Christian\u00a0Damsgaard Jensen, and Weizhi Meng, editors, ESORICS\u00a02022, Part\u00a0III, volume 13556 of LNCS, pages 42\u201362, Copenhagen, Denmark, September\u00a026\u201330, 2022. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-031-17143-7_3"},{"key":"9532_CR6","doi-asserted-by":"crossref","unstructured":"Carsten Baum, Alex\u00a0J. Malozemoff, Marc\u00a0B. Rosen, and Peter Scholl. Mac\u2019n\u2019cheese: Zero-knowledge proofs for boolean and arithmetic circuits with nested disjunctions. In Tal Malkin and Chris Peikert, editors, CRYPTO\u00a02021, Part\u00a0IV, volume 12828 of LNCS, pages 92\u2013122, Virtual Event, August\u00a016\u201320, 2021. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-030-84259-8_4"},{"key":"9532_CR7","doi-asserted-by":"crossref","unstructured":"Mihir Bellare and Oded Goldreich. On defining proofs of knowledge. In Ernest\u00a0F. Brickell, editor, CRYPTO\u201992, volume 740 of LNCS, pages 390\u2013420, Santa Barbara, CA, USA, August\u00a016\u201320, 1993. Springer, Heidelberg, Germany.","DOI":"10.1007\/3-540-48071-4_28"},{"key":"9532_CR8","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas\u00a0P. Ward. Aurora: Transparent succinct arguments for R1CS. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT\u00a02019, Part\u00a0I, volume 11476 of LNCS, pages 103\u2013128, Darmstadt, Germany, May\u00a019\u201323, 2019. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-030-17653-2_4"},{"key":"9532_CR9","doi-asserted-by":"crossref","unstructured":"Benedikt B\u00fcnz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In 2018 IEEE Symposium on Security and Privacy, pages 315\u2013334, San Francisco, CA, USA, May\u00a021\u201323, 2018. IEEE Computer Society Press.","DOI":"10.1109\/SP.2018.00020"},{"key":"9532_CR10","doi-asserted-by":"crossref","unstructured":"Matteo Campanelli, Dario Fiore, and Ana\u00efs Querol. LegoSNARK: Modular design and composition of succinct zero-knowledge proofs. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 2075\u20132092, London, UK, November\u00a011\u201315, 2019. ACM Press.","DOI":"10.1145\/3319535.3339820"},{"key":"9532_CR11","doi-asserted-by":"crossref","unstructured":"Michele Ciampi, Giuseppe Persiano, Alessandra Scafuro, Luisa Siniscalchi, and Ivan Visconti. Improved OR-composition of sigma-protocols. In Eyal Kushilevitz and Tal Malkin, editors, TCC\u00a02016-A, Part\u00a0II, volume 9563 of LNCS, pages 112\u2013141, Tel Aviv, Israel, January\u00a010\u201313, 2016. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-662-49099-0_5"},{"key":"9532_CR12","doi-asserted-by":"crossref","unstructured":"Michele Ciampi, Giuseppe Persiano, Alessandra Scafuro, Luisa Siniscalchi, and Ivan Visconti. Online\/offline OR composition of sigma protocols. In Marc Fischlin and Jean-S\u00e9bastien Coron, editors, EUROCRYPT\u00a02016, Part\u00a0II, volume 9666 of LNCS, pages 63\u201392, Vienna, Austria, May\u00a08\u201312, 2016. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-662-49896-5_3"},{"key":"9532_CR13","unstructured":"Ronald Cramer. Modular Design of Secure yet Practical Cryptographic Protocols. PhD thesis, University of Amsterdam, January 1997."},{"key":"9532_CR14","doi-asserted-by":"crossref","unstructured":"Ronald Cramer, Ivan Damg\u00e5rd, and Berry Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Yvo Desmedt, editor, CRYPTO\u201994, volume 839 of LNCS, pages 174\u2013187, Santa Barbara, CA, USA, August\u00a021\u201325, 1994. Springer, Heidelberg, Germany.","DOI":"10.1007\/3-540-48658-5_19"},{"key":"9532_CR15","doi-asserted-by":"crossref","unstructured":"Ronald Cramer, Rosario Gennaro, and Berry Schoenmakers. A secure and optimally efficient multi-authority election scheme. In Walter Fumy, editor, EUROCRYPT\u201997, volume 1233 of LNCS, pages 103\u2013118, Konstanz, Germany, May\u00a011\u201315, 1997. Springer, Heidelberg, Germany.","DOI":"10.1007\/3-540-69053-0_9"},{"key":"9532_CR16","doi-asserted-by":"crossref","unstructured":"Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew\u00a0M. Odlyzko, editor, CRYPTO\u201986, volume 263 of LNCS, pages 186\u2013194, Santa Barbara, CA, USA, August 1987. Springer, Heidelberg, Germany.","DOI":"10.1007\/3-540-47721-7_12"},{"key":"9532_CR17","unstructured":"Aarushi Goel, Matthew Green, Mathias Hall-Andersen, and Gabriel Kaptchuk. Stacking sigmas: A framework to compose $$\\Sigma $$-protocols for disjunctions. Cryptology ePrint Archive, Report 2021\/422, 2021. https:\/\/eprint.iacr.org\/2021\/422."},{"key":"9532_CR18","doi-asserted-by":"crossref","unstructured":"Aarushi Goel, Matthew Green, Mathias Hall-Andersen, and Gabriel Kaptchuk. Stacking sigmas: A framework to compose $$\\Sigma $$-protocols for disjunctions. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT\u00a02022, Part\u00a0II, volume 13276 of LNCS, pages 458\u2013487, Trondheim, Norway, May\u00a030\u00a0\u2013\u00a0June\u00a03, 2022. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-031-07085-3_16"},{"key":"9532_CR19","doi-asserted-by":"crossref","unstructured":"Aarushi Goel, Mathias Hall-Andersen, Gabriel Kaptchuk, and Nicholas Spooner. Speed-stacking: Fast sublinear zero-knowledge proofs for disjunctions. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT\u00a02023, Part\u00a0II, volume 14005 of LNCS, pages 347\u2013378, Lyon, France, April\u00a023\u201327, 2023. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-031-30617-4_12"},{"key":"9532_CR20","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems (extended abstract). In 17th ACM STOC, pages 291\u2013304, Providence, RI, USA, May\u00a06\u20138, 1985. ACM Press.","DOI":"10.1145\/22145.22178"},{"key":"9532_CR21","doi-asserted-by":"crossref","unstructured":"Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-S\u00e9bastien Coron, editors, EUROCRYPT\u00a02016, Part\u00a0II, volume 9666 of LNCS, pages 305\u2013326, Vienna, Austria, May\u00a08\u201312, 2016. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"9532_CR22","doi-asserted-by":"crossref","unstructured":"Jens Groth and Markulf Kohlweiss. One-out-of-many proofs: Or how to leak a secret and spend a coin. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT\u00a02015, Part\u00a0II, volume 9057 of LNCS, pages 253\u2013280, Sofia, Bulgaria, April\u00a026\u201330, 2015. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-662-46803-6_9"},{"key":"9532_CR23","doi-asserted-by":"crossref","unstructured":"David Heath and Vladimir Kolesnikov. Stacked garbling for disjunctive zero-knowledge proofs. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT\u00a02020, Part\u00a0III, volume 12107 of LNCS, pages 569\u2013598, Zagreb, Croatia, May\u00a010\u201314, 2020. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-030-45727-3_19"},{"key":"9532_CR24","doi-asserted-by":"crossref","unstructured":"David Heath, Vladimir Kolesnikov, and Stanislav Peceny. Garbling, stacked and staggered - faster k-out-of-n garbled function evaluation. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT\u00a02021, Part\u00a0II, volume 13091 of LNCS, pages 245\u2013274, Singapore, December\u00a06\u201310, 2021. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-030-92075-3_9"},{"key":"9532_CR25","doi-asserted-by":"crossref","unstructured":"Markus Jakobsson, Kazue Sako, and Russell Impagliazzo. Designated verifier proofs and their applications. In Ueli\u00a0M. Maurer, editor, EUROCRYPT\u201996, volume 1070 of LNCS, pages 143\u2013154, Saragossa, Spain, May\u00a012\u201316, 1996. Springer, Heidelberg, Germany.","DOI":"10.1007\/3-540-68339-9_13"},{"key":"9532_CR26","doi-asserted-by":"crossref","unstructured":"Peter\u00a0Bro Miltersen, Jaikumar Radhakrishnan, and Ingo Wegener. On converting CNF to DNF. Theor. Comput. Sci., 347(1-2):325\u2013335, 2005.","DOI":"10.1016\/j.tcs.2005.07.029"},{"key":"9532_CR27","doi-asserted-by":"crossref","unstructured":"Rotem Tsabary. Fully secure attribute-based encryption for t-CNF from LWE. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO\u00a02019, Part\u00a0I, volume 11692 of LNCS, pages 62\u201385, Santa Barbara, CA, USA, August\u00a018\u201322, 2019. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-030-26948-7_3"},{"key":"9532_CR28","doi-asserted-by":"crossref","unstructured":"Yibin Yang, David Heath, Carmit Hazay, Vladimir Kolesnikov, and Muthuramakrishnan Venkitasubramaniam. Batchman and robin: Batched and non-batched branching for interactive ZK. In Weizhi Meng, Christian\u00a0Damsgaard Jensen, Cas Cremers, and Engin Kirda, editors, ACM CCS 2023, pages 1452\u20131466, Copenhagen, Denmark, November\u00a026\u201330, 2023. ACM Press.","DOI":"10.1145\/3576915.3623169"},{"key":"9532_CR29","doi-asserted-by":"crossref","unstructured":"Gongxian Zeng, Junzuo Lai, Zhengan Huang, Yu\u00a0Wang, and Zhiming Zheng. DAG-$$\\Sigma $$: A DAG-based sigma protocol for relations in CNF. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT\u00a02022, Part\u00a0II, volume 13792 of LNCS, pages 340\u2013370, Taipei, Taiwan, December\u00a05\u20139, 2022. Springer, Heidelberg, Germany.","DOI":"10.1007\/978-3-031-22966-4_12"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09532-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-024-09532-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-024-09532-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T21:33:18Z","timestamp":1739309598000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-024-09532-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,26]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["9532"],"URL":"https:\/\/doi.org\/10.1007\/s00145-024-09532-3","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,26]]},"assertion":[{"value":"7 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 November 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"7"}}