Paper 2023/1351
Bicameral and Auditably Private Signatures
Abstract
This paper introduces Bicameral and Auditably Private Signatures (BAPS) -- a new privacy-preserving signature system with several novel features. In a BAPS system, given a certified attribute $\mathbf{x}$ and a certified policy $P$, a signer can issue a publicly verifiable signature $\Sigma$ on a message $m$ as long as $(m, \mathbf{x})$ satisfies $P$. A noteworthy characteristic of BAPS is that both attribute $\mathbf{x}$ and policy $P$ are kept hidden from the verifier, yet the latter is convinced that these objects were certified by an attribute-issuing authority and a policy-issuing authority, respectively. By considering bicameral certification authorities and requiring privacy for both attributes and policies, BAPS generalizes the spirit of existing advanced signature primitives with fine-grained controls on signing capabilities (e.g., attribute-based signatures, predicate signatures, policy-based signatures). Furthermore, BAPS provides an appealing feature named auditable privacy, allowing the signer of $\Sigma$ to verifiably disclose various pieces of partial information about $P$ and $\mathbf{x}$ when asked by auditor(s)/court(s) at later times. Auditable privacy is intrinsically different from and can be complementary to the notion of accountable privacy traditionally incorporated in traceable anonymous systems such as group signatures. Equipped with these distinguished features, BAPS can potentially address interesting application scenarios for which existing primitives do not offer a direct solution. We provide rigorous security definitions for BAPS, following a ``sim-ext'' approach. We then demonstrate a generic construction based on commonly used cryptographic building blocks, which employs a sign-then-commit-then-prove design. Finally, we present a concrete instantiation of BAPS, that is proven secure in the random oracle model under lattice assumptions. The scheme can handle arbitrary policies represented by polynomial-size Boolean circuits and can address quadratic disclosing functions. In the construction process, we develop a new technical building block that could be of independent interest: a zero-knowledge argument system allowing to prove the satisfiability of a certified-and-hidden Boolean circuit on certified-and-committed inputs.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in ASIACRYPT 2023
- Keywords
- new primitivesignaturesbicameralityauditable privacyfine-grained information disclosureZK for hidden circuits
- Contact author(s)
-
khoa @ uow edu au
partha @ uow edu au
wsusilo @ uow edu au
yanhong xu @ sjtu edu cn - History
- 2023-09-11: approved
- 2023-09-11: received
- See all versions
- Short URL
- https://ia.cr/2023/1351
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1351, author = {Khoa Nguyen and Partha Sarathi Roy and Willy Susilo and Yanhong Xu}, title = {Bicameral and Auditably Private Signatures}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1351}, year = {2023}, url = {https://eprint.iacr.org/2023/1351} }