Signatures of Knowledge for Boolean Circuits Under Standard Assumptions

This paper constructs unbounded simulation sound proofs for boolean circuit satisfiability under standard assumptions with proof size [Formula: see text] 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. Our new scheme can be used to construct the most efficient Signature-of-Knowledge based on standard assumptions that also can be composed universally with other cryptographic protocols/primitives.