## CryptoDB

### Melissa Chase

#### Affiliation: Microsoft Research, USA

#### Publications

**Year**

**Venue**

**Title**

2019

CRYPTO

Reusable Non-Interactive Secure Computation
📺
Abstract

We consider the problem of Non-Interactive Two-Party Secure Computation (NISC), where Rachel wishes to publish an encryption of her input x, in such a way that any other party, who holds an input y, can send her a single message which conveys to her the value f(x, y), and nothing more. We demand security against malicious parties. While such protocols are easy to construct using garbled circuits and general non-interactive zero-knowledge proofs, this approach inherently makes a non-black-box use of the underlying cryptographic primitives and is infeasible in practice.Ishai et al. (Eurocrypt 2011) showed how to construct NISC protocols that only use parallel calls to an ideal oblivious transfer (OT) oracle, and additionally make only a black-box use of any pseudorandom generator. Combined with the efficient 2-message OT protocol of Peikert et al. (Crypto 2008), this leads to a practical approach to NISC that has been implemented in subsequent works. However, a major limitation of all known OT-based NISC protocols is that they are subject to selective failure attacks that allows a malicious sender to entirely compromise the security of the protocol when the receiver’s first message is reused.Motivated by the failure of the OT-based approach, we consider the problem of basing reusable NISC on parallel invocations of a standard arithmetic generalization of OT known as oblivious linear-function evaluation (OLE). We obtain the following results:We construct an information-theoretically secure reusable NISC protocol for arithmetic branching programs and general zero-knowledge functionalities in the OLE-hybrid model. Our zero-knowledge protocol only makes an absolute constant number of OLE calls per gate in an arithmetic circuit whose satisfiability is being proved. We also get reusable NISC in the OLE-hybrid model for general Boolean circuits using any one-way function.We complement this by a negative result, showing that reusable NISC is impossible to achieve in the OT-hybrid model. This provides a formal justification for the need to replace OT by OLE.We build a universally composable 2-message reusable OLE protocol in the CRS model that can be based on the security of Paillier encryption and requires only a constant number of modular exponentiations. This provides the first arithmetic analogue of the 2-message OT protocols of Peikert et al. (Crypto 2008).By combining our NISC protocol in the OLE-hybrid model and the 2-message OLE protocol, we get protocols with new attractive asymptotic and concrete efficiency features. In particular, we get the first (designated-verifier) NIZK protocols for NP where following a statement-independent preprocessing, both proving and verifying are entirely “non-cryptographic” and involve only a constant computational overhead. Furthermore, we get the first statistical designated-verifier NIZK argument for NP under an assumption related to factoring.

2016

CRYPTO

2016

ASIACRYPT

2016

JOFC

2012

ASIACRYPT

2008

EPRINT

Delegatable Anonymous Credentials
Abstract

We construct an efficient delegatable anonymous credential system. Users can anonymously and unlinkably obtain credentials from any authority, delegate their credentials to other users, and prove possession of a credential $L$ levels away from the given authority. The size of the proof (and time to compute it) is $O(Lk)$, where $k$ is the security parameter. The only other construction of delegatable anonymous credentials (Chase and Lysyanskaya, Crypto 2006) relies on general non-interactive proofs for NP-complete languages of size $k \Omega(2^{L})$.
We revise the entire approach to constructing anonymous credentials
and identify \emph{randomizable} zero-knowledge proof of knowledge
systems as the key building block. We formally define the notion of
randomizable non-interactive zero-knowledge proofs, and give the first construction by showing how to appropriately rerandomize Groth and Sahai (Eurocrypt 2008) proofs. We show that such proof systems, in combination with an appropriate authentication scheme and a few other protocols, allow us to construct delegatable anonymous credentials. Finally, we instantiate these building blocks under appropriate assumptions about groups with bilinear maps.

2007

EPRINT

Non-Interactive Anonymous Credentials
Abstract

In this paper, we introduce P-signatures. A P-signature scheme
consists of a signature scheme, a commitment scheme, and (1) an
interactive protocol for obtaining a signature on a committed value;
(2) a non-interactive proof system for proving that the
contents of a commitment has been signed; (3) a non-interactive proof
system for proving that a pair of commitments are commitments to the
same value. We give a definition of security for P-signatures and
show how they can be realized under appropriate assumptions about
groups with bilinear map. Namely, we make extensive use of the
powerful suite of non-interactive proof techniques due to Groth and Sahai.
Our P-signatures enable, for the first time, the design of a practical
non-interactive anonymous credential system whose security does not
rely on the random oracle model. In addition, they may serve as a useful building block for other privacy-preserving authentication mechanisms.

2006

EPRINT

On Signatures of Knowledge
Abstract

In a traditional signature scheme, a signature $\sigma$ on a message $m$ is issued under a public key $\pk$, and can be interpreted as follows: "The owner of the public key $\pk$ and its corresponding secret key has signed message $m$." In this paper we consider schemes that allow one to issue signatures on behalf of any NP statement, that can be interpreted as follows: "A person in possession of a witness $w$ to the statement that $x \in L$ has signed message $m$." We refer to such schemes as \emph{signatures of knowledge}.
We formally define the notion of a signature of knowledge. We begin by extending the traditional definition of digital signature schemes, captured by Canetti's ideal signing functionality, to the case of signatures of knowledge. We then give an alternative definition in terms of games that also seems to capture the necessary properties one
may expect from a signature of knowledge. We then gain additional
confidence in our two definitions by proving them equivalent.
We construct signatures of knowledge under standard complexity assumptions in the common-random-string model.
We then extend our definition to allow signatures of knowledge to be \emph{nested} i.e., a signature of knowledge (or another accepting
input to a UC-realizable ideal functionality) can itself serve as a
witness for another signature of knowledge. Thus, as a corollary, we obtain the first \emph{delegatable} anonymous credential system, i.e., a system in which one can use one's anonymous credentials as a secret key for issuing anonymous credentials to others.

#### Program Committees

- Crypto 2020
- Asiacrypt 2019
- Eurocrypt 2019
- Eurocrypt 2018
- Eurocrypt 2017
- Crypto 2016
- TCC 2016
- PKC 2016
- Crypto 2015
- PKC 2015
- Eurocrypt 2013
- TCC 2011
- PKC 2011
- Crypto 2008

#### Coauthors

- Masayuki Abe (2)
- Shashank Agrawal (3)
- Foteini Baldimtsi (1)
- Mira Belenkiy (4)
- Jan Camenisch (2)
- Nishanth Chandran (3)
- Bernardo David (2)
- Yevgeniy Dodis (1)
- Georg Fuchsbauer (1)
- Chaya Ganesh (1)
- Alexander Healy (1)
- Yuval Ishai (1)
- Seny Kamara (1)
- Markulf Kohlweiss (10)
- Daniel Kraschewski (1)
- Tianren Liu (1)
- Feng-Hao Liu (2)
- Anna Lysyanskaya (11)
- Tal Malkin (1)
- Mary Maller (1)
- Sarah Meiklejohn (6)
- Payman Mohassel (1)
- Ryo Nishimaki (4)
- Miyako Ohkubo (2)
- Rafail Ostrovsky (2)
- Leonid Reyzin (1)
- Hovav Shacham (2)
- Vinod Vaikuntanathan (2)
- Ivan Visconti (2)
- Keita Xagawa (2)