## CryptoDB

### Anna Lysyanskaya

#### Affiliation: Brown University

#### Publications

**Year**

**Venue**

**Title**

2019

TCC

Fully Homomorphic NIZK and NIWI Proofs
Abstract

In this work, we define and construct fully homomorphic non-interactive zero knowledge (FH-NIZK) and non-interactive witness-indistinguishable (FH-NIWI) proof systems. We focus on the NP complete language L, where, for a boolean circuit C and a bit b, the pair $$(C,b)\in L$$ if there exists an input $$\mathbf {w}$$ such that $$C(\mathbf {w})=b$$. For this language, we call a non-interactive proof system fully homomorphic if, given instances $$(C_i,b_i)\in L$$ along with their proofs $$\varPi _i$$, for $$i\in \{1,\ldots ,k\}$$, and given any circuit $$D:\{0,1\}^k\rightarrow \{0,1\}$$, one can efficiently compute a proof $$\varPi $$ for $$(C^*,b)\in L$$, where $$C^*(\mathbf {w}^{(1)},\ldots ,\mathbf {w}^{(k)})=D(C_1(\mathbf {w}^{(1)}),\ldots ,C_k(\mathbf {w}^{(k)}))$$ and $$D(b_1,\ldots ,b_k)=b$$. The key security property is unlinkability: the resulting proof $$\varPi $$ is indistinguishable from a fresh proof of the same statement. Our first result, under the Decision Linear Assumption (DLIN), is an FH-NIZK proof system for L in the common random string model. Our more surprising second result (under a new decisional assumption on groups with bilinear maps) is an FH-NIWI proof system that requires no setup.

2014

CRYPTO

2014

EPRINT

2009

EPRINT

Framework for Analyzing Optimistic Fair Exchange with Distributed Arbiters
Abstract

Fair exchange is one of the most fundamental problems in secure distributed computation. Alice has something that Bob wants, and Bob has something that Alice wants. A fair exchange protocol would guarantee that, even if one of them maliciously deviates from the protocol, either both of them get the desired content, or neither of them do. It is known that no two-party protocol can guarantee fairness in general; therefore the presence of a trusted arbiter is necessary. In optimistic fair exchange, the arbiter only gets involved in case of faults. To reduce the trust put in an arbiter, it is natural to consider employing multiple arbiters.
Avoine and Vaudenay (AV) [6] employ multiple autonomous arbiters in their optimistic fair exchange protocol which uses timeout mechanisms. They leave two open questions: (1) Can an optimistic fair exchange protocol without timeouts provide fairness when employing multiple autonomous arbiters? (2) Can any other optimistic fair exchange protocol with timeouts achieve better bounds on the number of honest arbiters required? In this paper, we answer both questions negatively. To answer these questions, we define a general class of optimistic fair exchange protocols with multiple arbiters, called distributed arbiter fair exchange (DAFE) protocols. Informally, in a DAFE protocol, if a participant fails to send a correctly formed message, the other party must contact some subset of the arbiters and get correctly formed responses from them. The arbiters do not talk to each other, but only to Alice and Bob. We prove that no DAFE protocol can exist. However, our impossibility results can be overcome in the timeout model (where all arbiters have access to loosely synchronized clocks) and also in case the arbiters can communicate (e.g., using secure multi-party computation with Omega(n^2) communication).

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.

2008

EPRINT

Usable Optimistic Fair Exchange
Abstract

Fairly exchanging digital content is an everyday problem. It has been shown that fair exchange cannot be done without a trusted third party (called the Arbiter). Yet, even with a trusted party, it is still non-trivial to come up with an efficient solution, especially one that can be used in a p2p file sharing system with a high volume of data exchanged.
We provide an efficient optimistic fair exchange mechanism for bartering digital files, where receiving a payment in return to a file (buying) is also considered fair. The exchange is optimistic, removing the need for the Arbiters involvement unless a dispute occurs. While the previous solutions employ costly cryptographic primitives for every file or block exchanged, our protocol employs them only once per peer, therefore achieving O(n) efficiency improvement when n blocks are exchanged between two peers. The rest of our protocol uses very efficient cryptography, making it perfectly suitable for a p2p file sharing system where tens of peers exchange thousands of blocks and they do not know beforehand which ones they will end up exchanging. Thus, for the first time, a provably secure (and privacy respecting when payments are made using e-cash) fair exchange protocol is being used in real bartering applications (e.g., BitTorrent) [14] without sacrificing performance.

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.

2006

EPRINT

How to Win the Clone Wars: \\ Efficient Periodic n-Times Anonymous Authentication
Abstract

We create a credential
system that lets a user anonymously authenticate at most $n$ times in
a single time period. A user withdraws a dispenser of $n$ e-tokens.
She shows an e-token to a verifier to authenticate herself; each
e-token can be used only once, however, the dispenser automatically
refreshes every time period.
The only prior solution to this problem,
due to Damg{\aa}rd et al.~[DDP05], uses protocols that are a factor of $k$ slower for the user and verifier, where $k$ is the security parameter.
Damg{\aa}rd et al. also only support one authentication per time
period, while we support $n$. Because our construction is based on
e-cash, we can use existing techniques to identify a cheating user,
trace all of her e-tokens, and revoke her dispensers. We also offer a
new anonymity service: glitch protection for basically honest users
who (occasionally) reuse e-tokens. The verifier can always recognize
a reused e-token; however, we preserve the anonymity of users who do
not reuse e-tokens too often.

2005

EPRINT

Steganography with Imperfect Samplers
Abstract

The goal of steganography is to pass secret messages by disguising
them as innocent-looking covertexts. Real world stegosystems are
often broken because they make invalid assumptions about the system's
ability to sample covertexts. We examine whether it is possible to
weaken this assumption. By modeling the covertext distribution as a
stateful Markov process, we create a sliding scale between real world
and provably secure stegosystems. We also show that insufficient
knowledge of past states can have catastrophic results.

2005

EPRINT

Compact E-Cash
Abstract

This paper presents efficient off-line anonymous e-cash schemes
where a user can withdraw a wallet containing 2^l coins each of which she can spend unlinkably. Our first result is a scheme, secure under the strong RSA and the y-DDHI assumptions, where the complexity of the withdrawal and spend operations is O(l+k)
and the user's wallet can be stored using O(l+k) bits, where k is a security parameter.
The best previously known schemes require at least one of these complexities to
be O(2^l k).
In fact, compared to previous e-cash schemes, our whole wallet of 2^l coins
has about the same size as one coin in these schemes.
Our scheme also offers exculpability
of users, that is, the bank can prove to third parties that a user has
double-spent.
We then extend our scheme to our second result, the first e-cash scheme that provides traceable coins without a trusted third party.
That is, once a user has double spent one of the 2^l coins in her wallet, all her spendings of these coins can be traced.
We present two alternate constructions. One construction shares the same complexities with our first result but requires a strong bilinear map assumption that is only conjectured to hold on MNT curves. The second construction works on more general types of elliptic curves, but the price for this is that the complexity of the spending and of the withdrawal protocols becomes O(lk) and O(lk + k^2) bits, respectively, and wallets take O(lk) bits of storage.
All our schemes are secure in the random oracle model.

2004

EPRINT

On the Composition of Authenticated Byzantine Agreement
Abstract

A fundamental problem of distributed computing is that of
simulating a secure broadcast channel, within the setting of a
point-to-point network. This problem is known as Byzantine
Agreement (or Generals) and has been the focus of much research.
Lamport et al. showed that in order to achieve Byzantine Agreement
in the standard model, more than 2/3 of the participating
parties must be honest. They further showed that by augmenting the
network with a public-key infrastructure for digital signatures,
it is possible to obtain protocols that are secure for any number
of corrupted parties. The problem in this augmented model is
called "authenticated Byzantine Agreement".
In this paper we consider the question of concurrent, parallel and
sequential composition of authenticated Byzantine Agreement
protocols. We present surprising impossibility results showing
that:
* If an authenticated Byzantine Agreement protocol remains
secure under parallel or concurrent composition (even for just two
executions), then more than 2/3 of the participating parties
must be honest.
* Deterministic authenticated Byzantine Agreement protocols that
run for $r$ rounds and tolerate 1/3 or more corrupted parties,
can remain secure for at most $2r-1$ sequential executions.
In contrast, we present randomized protocols for authenticated
Byzantine Agreement that remain secure under sequential
composition, for {\em any}\/ polynomial number of executions. We
exhibit two such protocols. In the first protocol, the number of
corrupted parties may be any number less than 1/2 (i.e., an
honest majority is required). In the second protocol, any number
of parties may be corrupted; however, the overall number of
parties must be limited to $O(\log k/\log\log k)$, where $k$ is
the security parameter (and so all parties run in time that is
polynomial in $k$). Finally, we show that when the model is
further augmented so that unique and common session identifiers
are assigned to each concurrent session, then any polynomial
number of authenticated Byzantine agreement protocols can be
concurrently executed, while tolerating any number of corrupted
parties.

2004

EPRINT

ID-Based Encryption for Complex Hierarchies with Applications to Forward Security and Broadcast Encryption
Abstract

A forward-secure encryption scheme protects secret keys from exposure by evolving the keys with time. Forward security has several unique requirements in Hierarchical Identity-Based Encryption (HIBE) scheme: (1) users join dynamically; (2) encryption
is joining-time-oblivious; (3) users evolve secret keys autonomously.
We present a scalable forward-secure HIBE scheme satisfying the above properties. Note that a naive combination of Gentry-Silverberg HIBE scheme with the forward-secure Public-Key Encryption scheme by Canetti, Halevi and Katz would not meet the requirements. We also show how our fs-HIBE scheme can be
used to construct a forward-secure public-key Broadcast Encryption
scheme, which protects the secrecy of prior transmissions in the Broadcast Encryption setting. We further generalize fs-HIBE into a collusion-resistant Multiple Hierarchical ID-Based Encryption scheme, which can be used for secure communications with entities having multiple roles in Role-Based Access Control. The security of our schemes is based on the Bilinear Diffie-Hellman assumption in the random oracle model.

2003

EPRINT

Sequential Aggregate Signatures from Trapdoor Permutations
Abstract

An aggregate signature scheme (recently proposed by Boneh, Gentry,
Lynn and Shacham) is a method for combining $n$ signatures from $n$
different signers on $n$ different messages into one signature of unit
length. We propose \emph{sequential aggregate signatures}, in which
the set of signers is ordered. The aggregate signature is computed by
having each signer, in turn, add his signature to it. We show how to
realize this in such a way that the size of the aggregate signature is
independent of $n$. This makes sequential aggregate signatures a
natural primitive for certificate chains, whose length can be reduced
by aggregating all signatures in a chain. We give a construction
based on families of certified trapdoor permutations, and show how to
instantiate our scheme based on RSA.

2003

EPRINT

Forward-Secure Hierarchical ID-Based Cryptography
Abstract

We present a forward-secure hierarchical identity-based encryption (FHIBE) scheme, which is based on the hierarchical identity-based encryption (HIBE) scheme by Gentry and Silverberg. Canetti, Halevi and Katz presented a forward-secure public key encryption scheme based on HIBE scheme. They give the formal definition of Binary Encryption Tree (BET), which is a relaxed version of HIBE and is essential to their forward-secure encryption.We unify their idea with HIBE scheme, and present a forward-secure hierarchical identity-based encryption scheme. In the FHIBE scheme, secret keys of each entity on the hierarchy are updated at regular intervals throughout the lifetime of the system; furthermore, exposure of an entity's secret key corresponding to a given interval does not enable an adversary to break the ancestors of the entity for any prior time period. Entities can join in the hierarchy at any time and at any position, and are able to update their secret keys on their own once they are initialized by their parent entities. These features are important in the distributed settings.
The forward-secure hierarchical identity-based encryption scheme can be generalized into a collusion resistant multiple hierarchical identity-based encryption (MHIBE) scheme, where a message can be encrypted under multiple identities of a user.

2002

EPRINT

Asynchronous Verifiable Secret Sharing and Proactive Cryptosystems
Abstract

Verifiable secret sharing is an important primitive in
distributed cryptography. With the growing interest in the
deployment of threshold cryptosystems in practice, the
traditional assumption of a synchronous network has to be
reconsidered and generalized to an asynchronous model.
This paper proposes the first \emph{practical} verifiable secret
sharing protocol for asynchronous networks. The protocol creates
a discrete logarithm-based sharing and uses only a quadratic
number of messages in the number of participating servers. It
yields the first asynchronous Byzantine agreement protocol in
the standard model whose efficiency makes it suitable
for use in practice. Proactive cryptosystems are another
important application of verifiable secret sharing. The second part of this paper introduces proactive cryptosystems in
asynchronous networks and presents an efficient protocol for
refreshing the shares of a secret key for discrete
logarithm-based sharings.

2001

EUROCRYPT

2001

EPRINT

An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation
Abstract

A credential system is a system in which users can obtain
credentials from organizations and demonstrate possession of these
credentials. Such a system is anonymous when transactions carried out by the
same user cannot be linked. An anonymous credential system is of significant
practical relevance because it is the best means of providing privacy for
users. In this paper we propose a practical anonymous credential system that
is based on the strong RSA assumption and the decisional Diffie-Hellman
assumption modulo a safe prime product and is considerably superior to
existing ones:
(1) We give the first practical solution that allows
a user to unlinkably demonstrate possession of a credential as many times as
necessary without involving the issuing organization.
(2) To prevent misuse of anonymity, our scheme is the first to offer optional
anonymity revocation for particular transactions.
(3) Our scheme offers separability: all organizations can choose their
cryptographic keys independently of each other.
Moreover, we suggest more effective means of preventing users from sharing their
credentials, by introducing {\em all-or-nothing} sharing: a user who allows a
friend to use one of her credentials once, gives him the ability to use all of
her credentials, i.e., taking over her identity. This is implemented by a new
primitive, called {\em circular encryption}, which is of independent interest,
and can be realized from any semantically secure cryptosystem in the random
oracle model.

2001

EPRINT

Efficient Revocation of Anonymous Group Membership
Abstract

An accumulator scheme, introduced be Benaloh and de Mare
and further studied by Bari{\'c} and Pfitzmann, is an algorithm that
allows to hash a large set of inputs into one short value, called the
\textit{accumulator}, such that there is a short witness that a given
input was incorporated into the accumulator.
We put forward the notion of \textit{dynamic accumulators}, i.e., a method
that allows to dynamically add and delete inputs from the accumulator,
such that the cost of an add or delete is independent on the number of
accumulated values. We achieve this under the strong RSA assumption. For
this construction, we also show an efficient zero-knowledge protocol for
proving that a committed value is in the accumulator.
In turn, our construction of dynamic accumulator enables efficient
membership revocation in the anonymous setting. This method applies
to membership revocation in group signature schemes, such as the one
due to Ateniese et al., and efficient revocation of
credentials in anonymous credential systems, such as the one due to
Camenisch and Lysyanskaya. Using our method,
allowing revocation does not alter the complexity of any operations of
the underlying schemes. In particular, the cost of a group signature
verification or credential showing increases by only a small constant
factor, less than 2. All previously known methods (such as the ones
due to Bresson and Stern and Ateniese and Tsudik incurred an increase in these costs that was
linear in the number of members.

2000

EPRINT

Threshold Cryptography Secure Against the Adaptive Adversary, Concurrently
Abstract

A threshold cryptosystem or signature scheme is a system with $n$ participants
where an honest majority can successfully decrypt a message or issue a
signature, but where the security and functionality properties of the
system are retained even as
the adversary corrupts up to $t$ players.
We present the novel technique of a committed proof,
which is a new general tool that enables security of threshold
cryptosystems in the presence of the adaptive adversary.
We also put forward a new measure of security for threshold schemes
secure in the adaptive adversary model: security under concurrent
composition.
Using committed proofs, we construct concurrently and adaptively secure
threshold protocols for a variety of cryptographic applications.
In particular, based on the recent scheme by Cramer-Shoup, we
construct adaptively secure threshold cryptosystems secure against
adaptive chosen ciphertext attack under the DDH intractability
assumption.

#### Program Committees

- Crypto 2020
- TCC 2018
- Crypto 2018
- Eurocrypt 2017
- PKC 2015
- Asiacrypt 2013
- Eurocrypt 2011
- TCC 2011
- Asiacrypt 2010
- Eurocrypt 2009
- Crypto 2009
- Eurocrypt 2008
- Asiacrypt 2007
- Eurocrypt 2007
- PKC 2007
- TCC 2005
- PKC 2005
- Eurocrypt 2004
- Crypto 2003

#### Coauthors

- Prabhanjan Ananth (1)
- Foteini Baldimtsi (1)
- Mira Belenkiy (4)
- Christian Cachin (1)
- Jan Camenisch (14)
- Melissa Chase (11)
- Dana Dachman-Soled (2)
- Apoorvaa Deshpande (1)
- Yevgeniy Dodis (1)
- Nelly Fazio (1)
- Nils Fleischhacker (2)
- Rosario Gennaro (1)
- Alexander Healy (1)
- Susan Hohenberger (4)
- Stanislaw Jarecki (1)
- Yael Tauman Kalai (1)
- Jonathan Katz (2)
- Markulf Kohlweiss (8)
- Alptekin Küpçü (2)
- Klaus Kursawe (1)
- Anja Lehmann (2)
- Yehuda Lindell (1)
- Moses Liskov (1)
- Feng-Hao Liu (1)
- Tal Malkin (2)
- Sarah Meiklejohn (3)
- Mira Meyerovich (3)
- Silvio Micali (4)
- Gregory Neven (2)
- Chris Peikert (1)
- Tal Rabin (2)
- Leonid Reyzin (4)
- Dominique Schröder (2)
- Hovav Shacham (4)
- Adam Smith (1)
- Reto Strobl (1)
- Nikos Triandopoulos (1)
- Danfeng Yao (2)