Cryptology ePrint Archive: Report 2020/1063
Signatures of Knowledge for Boolean Circuits under Standard Assumptions
Karim Baghery and Alonso González and Zaira Pindado and Carla Rŕfols
Abstract: 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.
Category / Keywords: cryptographic protocols / NIZK, Signatures, Bilinear Groups, CircuitSat
Original Publication (with major differences): AFRICACRYPT 2020
DOI: 10.1007/978-3-030-51938-4_2
Date: received 2 Sep 2020, last revised 3 Sep 2020, withdrawn 23 Sep 2020
Contact author: zaira pindado at upf edu
Available format(s): (-- withdrawn --)
Version: 20200923:102825 (All versions of this report)
Short URL: ia.cr/2020/1063
[ Cryptology ePrint archive ]