Paper 2020/1189

Signatures of Knowledge for Boolean Circuits under Standard Assumptions (Full version)

Karim Baghery, Alonso González, 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.

Note: This report has the same content (with minor modifications) as Report 2020/1063 that was accidentally withdrawn.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. Africacrypt 2020
DOI
10.1007/978-3-030-51938-4_2
Keywords
NIZKSignaturesBilinear GroupsCircuitSat
Contact author(s)
zaira pindado @ upf edu
History
2020-09-30: received
Short URL
https://ia.cr/2020/1189
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1189,
      author = {Karim Baghery and Alonso González and Zaira Pindado and Carla Ràfols},
      title = {Signatures of Knowledge for Boolean Circuits under Standard Assumptions (Full version)},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1189},
      year = {2020},
      doi = {10.1007/978-3-030-51938-4_2},
      note = {\url{https://eprint.iacr.org/2020/1189}},
      url = {https://eprint.iacr.org/2020/1189}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.