2026-04-17T12:55:03Zhttps://recercat.cat/oai/request

oai:recercat.cat:10230/729252026-03-31T17:31:41Zcom_2072_6col_2072_452952

2026-03-31T17:31:41Z urn:hdl:10230/72925 Signatures of knowledge for boolean circuits under standard assumptions Baghery, Karim González, Alonso Pindado, Zaira Ràfols, Carla NIZK Signatures Bilinear groups CircuitSat This paper constructs unbounded simulation sound proofs for boolean circuit satisfiability under standard assumptions with proof size O(n+d) bilinear group elements, where d is the depth and n is the input size of the circuit. Our technical contribution is to add unbounded simulation soundness to a recent NIZK of González and Ràfols (ASIACRYPT'19) with very small overhead. We give two different constructions: the first one is more efficient but not tight, and the second one is tight. Our new scheme can be used to construct Signatures of Knowledge based on standard assumptions that also can be composed universally with other cryptographic protocols/primitives. As an independent contribution we also detail a simple formula to encode Boolean circuits as Quadratic Arithmetic Programs. 2026-03-31T17:31:41Z 2026-03-31T17:31:41Z 2026-03-30T10:34:52Z 2026-03-30T10:34:52Z 2022 2026-03-30T10:34:51Z info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion https://hdl.handle.net/10230/72925 Theoretical Computer Science. 2022 May;916(1):86-110 © 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). http://creativecommons.org/licenses/by-nc-nd/4.0/ info:eu-repo/semantics/openAccess Elsevier