Paper 2023/1351

Bicameral and Auditably Private Signatures

Khoa Nguyen, University of Wollongong
Partha Sarathi Roy, University of Wollongong
Willy Susilo, University of Wollongong
Yanhong Xu, Shanghai Jiao Tong University
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.