International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: "Bifurcated Cryptography" Folding Competing Cryptosystems into a Single Scheme: On Accountability vs. Anonymity in Private Signatures

Benoit Libert , CNRS and ENS de Lyon, France
Khoa Nguyen , Nanyang Technological University, Singapore
Thomas Peters , FNRS and UCLouvain, Belgium
Moti Yung , Google llc and Columbia University, USA
DOI: 10.1007/978-3-030-77883-5_18 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2021
Abstract: Over the development of modern cryptography, often, alternative cryptographic schemes are developed to achieve goals that in some important respect are orthogonal. Thus, we have to choose either a scheme which achieves the first goal and not the second, or vice versa. This results in two types of schemes that compete with each other. In the basic area of user privacy, specifically in anonymous (multi-use credentials) signing, such an orthogonality exists between anonymity and accountability. The conceptual contribution of this work is to reverse the above orthogonality by design, which essentially typifies the last 25 years or so, and to suggest an alternative methodology where the opposed properties are carefully folded into a single scheme. The schemes will support both opposing properties simultaneously in a bifurcated fashion, where: - First, based on rich semantics expressed over the message's context and content, the user, etc., the relevant property is applied point-wise per message operation depending on a predicate; and - Secondly, at the same time, the schemes provide what we call ``branch-hiding;'' namely, the resulting calculated value hides from outsiders which property has actually been locally applied. Specifically, we precisely define and give the first construction and security proof of a ``Bifurcated Anonymous Signature'' (BiAS): A scheme which supports either absolute anonymity or anonymity with accountability, based on a specific contextual predicate, while being branch-hiding. This novel signing scheme has numerous applications not easily implementable or not considered before, especially because: (i) the conditional traceability does 'not' rely on a trusted authority as it is (non-interactively) encapsulated into signatures; and (ii) signers 'know' the predicate value and can make a conscious choice at each signing time. Technically, we realize BiAS from homomorphic commitments for a general family of predicates that can be represented by bounded-depth circuits. Our construction is generic and can be instantiated in the standard model from lattices and, more efficiently, from bilinear maps. In particular, the signature length is independent of the circuit size when we use commitments with suitable efficiency properties.
Video from EUROCRYPT 2021
  title={"Bifurcated Cryptography" Folding Competing Cryptosystems into a Single Scheme: On Accountability vs. Anonymity in Private Signatures},
  author={Benoit Libert and Khoa Nguyen and Thomas Peters and Moti Yung},