## CryptoDB

### Shafi Goldwasser

#### Affiliation: MIT

#### Publications

**Year**

**Venue**

**Title**

2014

EPRINT

2010

EPRINT

Circular and Leakage Resilient Public-Key Encryption Under Subgroup Indistinguishability (or: Quadratic Residuosity Strikes Back)
Abstract

The main results of this work are new public-key encryption schemes
that, under the quadratic residuosity (QR) assumption (or
Paillier's decisional composite residuosity (DCR) assumption), achieve key-dependent message security as well as high resilience to secret key leakage and high resilience to the presence of auxiliary input information.
In particular, under what we call the {\it subgroup
indistinguishability assumption}, of which the QR and DCR are special
cases, we can construct a scheme that has:
* Key-dependant message (circular) security.
Achieves security even when encrypting affine functions of its
own secret-key (in fact, w.r.t. affine ``key-cycles'' of predefined
length). Our scheme also meets the requirements for extending
key-dependant message security to broader classes of functions
beyond affine functions using the techniques of [BGK, ePrint09] or [BHHI, ePrint09].
* Leakage resiliency.
Remains secure even if any adversarial low-entropy (efficiently computable) function of the secret-key is given to the adversary. A proper selection of parameters allows for a ``leakage rate'' of $(1-o(1))$ of the length of the secret-key.
* Auxiliary-input security.
Remains secure even if any sufficiently \emph{hard to invert} (efficiently computable) function of the secret-key is given to the adversary.
Our scheme is the first to achieve key-dependant security and
auxiliary-input security based on the DCR and QR assumptions.
Previous schemes that achieved these properties relied either
on the DDH or LWE assumptions. The proposed scheme is also the first to achieve leakage resiliency for leakage rate $(1-o(1))$ of the secret-key length, under the QR assumption. We note that leakage resilient schemes under the DCR and the QR assumptions, for the restricted case of composite modulus product of safe primes, were implied by the work of [NS, Crypto09], using hash proof systems. However, under the QR assumption, known constructions of hash proof systems only yield a leakage rate of $o(1)$ of the secret-key length.

2008

EPRINT

How to Protect Yourself without Perfect Shredding
Abstract

Erasing old data and keys is an important tool in cryptographic protocol design. It is useful in many settings, including proactive security, adaptive security, forward security, and intrusion resilience. Protocols for all these settings typically assume the ability to perfectly erase information. Unfortunately, as amply demonstrated in the systems literature, perfect erasures are hard to implement in practice.
We propose a model of partial erasures where erasure instructions leave almost all the data erased intact, thus giving the honest players only a limited capability for disposing of old data. Nonetheless, we provide a general compiler that transforms any secure protocol using perfect erasures into one that maintains the same security properties when only partial erasures are available. The key idea is a new redundant representation of secret data which can still be computed on, and yet is rendered useless when partially erased. We prove that any such a compiler must incur a cost in additional storage, and that our compiler is near optimal in terms of its storage overhead.

2003

EPRINT

On the (In)security of the Fiat-Shamir Paradigm
Abstract

In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security are substantially more inefficient and complicated in design.
In 1996, Pointcheval and Stern proved that the signature schemes
obtained by the Fiat-Shamir transformation are secure in the so called `Random Oracle Model'. The question is: does the proof of the security of the Fiat-Shamir transformation in the Random Oracle Model, imply that the transformation yields secure signature schemes in the ``real-world"?
In this paper we answer this question negatively. We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir methodology produces {\bf insecure} digital signature schemes for {\bf any} implementation of the `Random Oracle Model' in the `real-world' by a function ensemble.

2002

EPRINT

Secure Computation Without Agreement
Abstract

It has recently been shown that authenticated Byzantine agreement,
in which more than a third of the parties are corrupted, cannot be
securely realized under concurrent or parallel (stateless)
composition. This result puts into question any usage of
authenticated Byzantine agreement in a setting where many
executions take place. In particular, this is true for the whole
body of work of secure multi-party protocols in the case that a
third or more of the parties are corrupted. This is because these
protocols strongly rely on the extensive use of a broadcast
channel, which is in turn realized using authenticated Byzantine
agreement. We remark that it was accepted folklore that the use of
a broadcast channel (or authenticated Byzantine agreement) is
actually essential for achieving meaningful secure multi-party
computation whenever a third or more of the parties are corrupted.
In this paper we show that this folklore is false. We present a
mild relaxation of the definition of secure computation allowing
abort. Our new definition captures all the central security issues
of secure computation, including privacy, correctness and
independence of inputs. However, the novelty of the definition is
in {\em decoupling} the issue of agreement from these issues. We
then show that this relaxation suffices for achieving secure
computation in a point-to-point network. That is, we show that
secure multi-party computation for this definition can be achieved
for {\em any} number of corrupted parties and {\em without} a
broadcast channel (or trusted preprocessing phase as required for
running authenticated Byzantine agreement). Furthermore, this is
achieved by just replacing the broadcast channel in known
protocols with a very simple and efficient echo-broadcast
protocol. An important corollary of our result is the ability to
obtain multi-party protocols that remain secure under composition,
without assuming a broadcast channel.

2001

EPRINT

Resettably-Sound Zero-Knowledge and its Applications
Abstract

Resettably-sound proofs and arguments remain sound even when the
prover can reset the verifier, and so force it to use the same
random coins in repeated executions of the protocol. We show that
resettably-sound zero-knowledge {\em arguments} for NP exist
if collision-resistant hash functions exist. In contrast,
resettably-sound zero-knowledge {\em proofs} are possible only
for languages in P/poly.
We present two applications of resettably-sound zero-knowledge
arguments. First, we construct resettable zero-knowledge arguments
of knowledge for NP, using a natural relaxation of the
definition of arguments (and proofs) of knowledge. We note that,
under the standard definition of proofs of knowledge, it is
impossible to obtain resettable zero-knowledge arguments of
knowledge for languages outside BPP. Second, we construct a
constant-round resettable zero-knowledge argument for NP in the
public-key model, under the assumption that collision-resistant
hash functions exist. This improves upon the sub-exponential
hardness assumption required by previous constructions.
We emphasize that our results use non-black-box zero-knowledge
simulations. Indeed, we show that some of the results are {\em
impossible} to achieve using black-box simulations. In
particular, only languages in BPP have resettably-sound
arguments that are zero-knowledge with respect to black-box
simulation.

2000

EPRINT

Identification Protocols Secure Against Reset Attacks
Abstract

We provide identification protocols that are secure even
when the adversary can reset the internal state and/or randomization source of
the user identifying itself, and when executed in an asynchronous environment
like the Internet that gives the adversary concurrent access to instances of
the user. These protocols are suitable for use by devices (like smartcards)
which when under adversary control may not be able to reliably maintain their
internal state between invocations.

1999

EUROCRYPT

1999

EPRINT

Resettable Zero-Knowledge
Abstract

We introduce the notion of Resettable Zero-Knowledge
(rZK), a new security measure for cryptographic protocols which
strengthens the classical notion of zero-knowledge. In essence, an
rZK protocol is one that remains zero knowledge even if an adeversary
can interact with the prover many times, each time resetting the
prover to its initial state and forcing him to use the same random
tape.
Under general complexity asumptions, which hold for example if the
Discrete Logarithm Problem is hard, we construct (1) rZK proof-systems
for NP: (2) constant-round resettable witness-indistinguishable
proof-systems for NP; and (3) constant-round rZK arguments for NP in
the public key model where verifiers have fixed, public keys
associated with them.
In addition to shedding new light on what makes zero knowledge
possible (by constructing ZK protocols that use randomness in a
dramatically weaker way than before), rZK has great relevance to
applications. Firstly, we show that rZK protocols are closed under
parallel and concurrent execution and thus are guaranteed to be secure
when implemented in fully asynchronous networks, even if an adversary
schedules the arrival of every message sent. Secondly, rZK protocols
enlarge the range of physical ways in which provers of a ZK protocols
can be securely implemented, including devices which cannot reliably
toss coins on line, nor keep state betweeen invocations. (For
instance, because ordinary smart cards with secure hardware are
resattable, they could not be used to implement securely the provers
of classical ZK protocols, but can now be used to implement securely
the provers of rZK protocols.)

1998

EPRINT

On the possibility of basing Cryptography on the assumption that $P \neq NP$
Abstract

Recent works by Ajtai and by Ajtai and Dwork
bring to light the old (general) question of whether it is
at all possible to base the
security of cryptosystems on the assumption that $\P\neq\NP$.
We discuss this question and in particular review and extend
a two-decade old result of Brassard regarding this question.
Our conclusion is that the question remains open.

1998

EPRINT

A Random Server Model for Private Information Retrieval (or How to Achieve Information Theoretic PIR Avoiding Data Replication)
Abstract

Private information retrieval (PIR) schemes enable users to obtain
information from databases while keeping their queries secret from the
database managers. We propose a new model for PIR, utilizing
auxiliary random servers to provide privacy services for database
access. In this model, prior to any on-line communication where users
request queries, the database engages in an initial preprocessing
setup stage with the random servers. Using this model we achieve the
first PIR information theoretic solution in which the database does
not need to give away its data to be replicated, and with minimal
on-line computation cost for the database. This solves privacy and
efficiency problems inherent to all previous solutions.
In particular, all previous information theoretic PIR schemes required
multiple replications of the database into separate entities which are
not allowed to communicate with each other; and in all previous
schemes (including ones which do not achieve information theoretic
security), the amount of computation performed by the database on-line
for every query is at least linear in the size of the database.
In contrast, in our solutions the database does not give away its
contents to any other entity; and after the initial setup stage, which
costs at most O(n log n) in computation, the database needs to
perform only O(1) amount of computation to answer questions of users
on-line. All the extra on-line computation is done by the auxiliary
random servers.

1996

EPRINT

Collision-Free Hashing from Lattice Problems
Abstract

Recently Ajtai described a construction of one-way functions whose
security is equivalent to the difficulty of some well known approximation
problems in lattices. We show that essentially the same
construction can also be used to obtain collision-free hashing.

1996

EPRINT

Verifiable Partial Key Escrow
Abstract

One of the main objections to existing proposals for key escrow is that the
individual's privacy relies on too high a level of trust in the law enforcement
agencies. In particular, even if the government is trustworthy today, it may be
replaced by an un-trustworthy government tomorrow which could immediately and
suddenly recover the secret keys of all users.

1996

EPRINT

Public-Key Cryptosystems from Lattice Reduction Problems
Abstract

We present a new proposal for a trapdoor one-way function, from which
we derive public-key encryption and digital signatures.
The security of the new construction is based on the
conjectured computational difficulty of lattice-reduction problems,
providing a possible alternative to existing
public-key encryption algorithms
and digital signatures such as RSA and DSS.

1992

CRYPTO

1984

CRYPTO

#### Program Committees

- Crypto 2009
- Eurocrypt 2005
- Eurocrypt 1997
- Asiacrypt 1991
- Crypto 1988
- Crypto 1986

#### Coauthors

- Adi Akavia (1)
- Pablo Azar (1)
- Boaz Barak (1)
- Donald Beaver (1)
- Mihir Bellare (7)
- Michael Ben-Or (2)
- Allison Bishop (1)
- Nir Bitansky (5)
- Manuel Blum (1)
- Raphael Bost (1)
- Elette Boyle (2)
- Zvika Brakerski (4)
- Ran Canetti (8)
- Nishanth Chandran (1)
- Hao Chen (1)
- Alessandro Chiesa (2)
- Wutichai Chongchitmate (1)
- Benny Chor (1)
- Aloni Cohen (2)
- Henry Cohn (1)
- Lenore Cowen (1)
- Ronald Cramer (1)
- Yevgeniy Dodis (1)
- Dror Eiger (1)
- Marc Fischlin (2)
- Juan A. Garay (1)
- Yael Gertner (1)
- Oded Goldreich (11)
- S. Dov Gordon (1)
- Vipul Goyal (1)
- Robbert de Haan (1)
- Shai Halevi (5)
- Johan Håstad (1)
- Ioana Ivan (1)
- Abhishek Jain (2)
- Yael Tauman Kalai (9)
- Jonathan Katz (1)
- Dmitriy Kharchenko (1)
- Joe Kilian (2)
- Saleet Klein (1)
- Leonid A. Levin (1)
- Dah-Yoh Lim (1)
- Huijia Lin (2)
- Yehuda Lindell (3)
- Feng-Hao Liu (1)
- Tal Malkin (1)
- Silvio Micali (8)
- Daniele Micciancio (1)
- Rafail Ostrovsky (2)
- Omer Paneth (2)
- Sunoo Park (2)
- Chris Peikert (1)
- Oxana Poburinnaya (1)
- Raluca Ada Popa (1)
- Raluca A. Popa (1)
- Charles Rackoff (1)
- Ronald L. Rivest (1)
- Phillip Rogaway (1)
- Alon Rosen (1)
- Guy N. Rothblum (6)
- Aviad Rubinstein (2)
- Amit Sahai (1)
- Elaine Shi (1)
- Yael Tauman (1)
- Stefano Tessaro (1)
- Eran Tromer (2)
- Stephen Tu (1)
- Vinod Vaikuntanathan (8)
- Erez Waisbard (1)
- Brent Waters (1)
- Daniel Wichs (1)
- Avi Wigderson (1)
- David A. Wilson (1)
- Andrew Chi-Chih Yao (1)
- Nickolai Zeldovich (1)
- Hong-Sheng Zhou (1)
- Vassilis Zikas (1)