## CryptoDB

### Juan A. Garay

#### Publications

**Year**

**Venue**

**Title**

2020

EUROCRYPT

Resource-Restricted Cryptography: Revisiting MPC Bounds in the Proof-of-Work Era
📺
Abstract

Traditional bounds on synchronous Byzantine agreement (BA) and secure multi-party computation (MPC) establish that in absence of a private correlated-randomness setup, such as a PKI,
protocols can tolerate up to $t<n/3$ of the parties being malicious. The introduction of ``Nakamoto style'' consensus, based on Proof-of-Work (PoW) blockchains, put forth a somewhat different flavor of BA,
showing that even a majority of corrupted parties
can be tolerated as long as the majority of the computation resources remain at honest hands. This assumption on honest majority of some resource was also extended to other resources such as stake, space, etc., upon which blockchains achieving Nakamoto-style consensus were built that violated the $t<n/3$ bound in terms of number of party corruptions. The above state of affairs
begs the question of whether the seeming mismatch is due to different goals and models, or whether the resource-restricting paradigm can be generically used to circumvent the $n/3$ lower bound.
In this work we study this question and formally demonstrate
how the above paradigm changes the rules of the game in cryptographic definitions.
First, we abstract the core properties that the resource-restricting paradigm offers by means of a functionality {\em wrapper}, in the UC framework, which when applied to a standard point-to-point network restricts the ability (of the adversary) to send new messages. We show that such a wrapped network can be implemented using the resource-restricting paradigm---concretely, using PoWs and honest majority of computing power---and that the traditional $t<n/3$ impossibility results fail when the parties have access to such a network. Our construction is in the {\em fresh} Common Reference String (CRS) model---i.e., it assumes a CRS which becomes available to the parties at the same time as to the adversary.
We then present constructions for BA and MPC, which given access to such a network tolerate $t<n/2$ corruptions without assuming a private correlated randomness setup. We also show how to remove the freshness assumption from the CRS by leveraging the power of a random oracle. Our MPC protocol achieves the standard notion of MPC security, where parties might have dedicated roles, as is for example the case in Oblivious Transfer protocols. This is in contrast to existing solutions basing MPC on PoWs, which associate roles to pseudonyms but do not link these pseudonyms with the actual parties.

2020

EUROCRYPT

Broadcast-Optimal Two-Round MPC
📺
Abstract

An intensive effort by the cryptographic community to minimize the round complexity of secure multi-party computation (MPC) has recently led to optimal two-round protocols from minimal assumptions. Most of the proposed solutions, however, make use of a broadcast channel in every round, and it is unclear if the broadcast channel can be replaced by standard point-to-point communication in a round-preserving manner, and if so, at what cost on the resulting security.
In this work, we provide a complete characterization of the trade-off between number of broadcast rounds and achievable security level for two-round MPC tolerating arbitrarily many active corruptions. Specifically, we consider all possible combinations of broadcast and point-to-point rounds against the three standard levels of security for maliciously se- cure MPC protocols, namely, security with identifiable, unanimous, and selective abort. For each of these notions and each combination of broadcast and point-to-point rounds, we provide either a tight feasibility or an infeasibility result of two-round MPC. Our feasibility results hold assuming two-round OT in the CRS model, whereas our impossibility results hold given any correlated randomness.

2020

TCC

Blockchains from Non-Idealized Hash Functions
📺
Abstract

The formalization of concrete, non-idealized hash function properties sufficient to prove the security of Bitcoin and related protocols has been elusive, as all previous security analyses of blockchain protocols have been
performed in the random oracle model. In this paper we identify three such properties, and then construct a blockchain protocol whose security can be reduced to them in the standard model assuming a common reference string (CRS).
The three properties are: {\em collision resistance}, {\em computational randomness extraction} and {\em iterated hardness}. While the first two properties have been extensively studied,
iterated hardness has been empirically
stress-tested since the rise
of Bitcoin; in fact,
as we demonstrate in this paper,
any attack against it
(assuming the other two properties hold)
results in an attack against Bitcoin.
In addition, iterated hardness
puts forth a new class of search problems which we term {\em iterated search problems} (ISP).
ISPs enable the concise and modular specification of blockchain protocols, and
may be of independent interest.

2019

JOFC

Probabilistic Termination and Composability of Cryptographic Protocols
Abstract

When analyzing the round complexity of multi-party protocols, one often overlooks the fact that underlying resources, such as a broadcast channel, can by themselves be expensive to implement. For example, it is well known that it is impossible to implement a broadcast channel by a (deterministic) protocol in a sublinear (in the number of corrupted parties) number of rounds. The seminal works of Rabin and Ben-Or from the early 1980s demonstrated that limitations as the above can be overcome by using randomization and allowing parties to terminate at different rounds, igniting the study of protocols over point-to-point channels with probabilistic termination and expected constant round complexity. However, absent a rigorous simulation-based definition, the suggested protocols are proven secure in a property-based manner or via ad hoc simulation-based frameworks, therefore guaranteeing limited, if any, composability. In this work, we put forth the first simulation-based treatment of multi-party cryptographic protocols with probabilistic termination. We define secure multi-party computation (MPC) with probabilistic termination in the UC framework and prove a universal composition theorem for probabilistic termination protocols. Our theorem allows to compile a protocol using deterministic termination hybrids into a protocol that uses expected constant round protocols for emulating these hybrids, preserving the expected round complexity of the calling protocol. We showcase our definitions and compiler by providing the first composable protocols (with simulation-based security proofs) for the following primitives, relying on point-to-point channels: (1) expected constant round perfect Byzantine agreement, (2) expected constant round perfect parallel broadcast, and (3) perfectly secure MPC with round complexity independent of the number of parties.

2018

PKC

Bootstrapping the Blockchain, with Applications to Consensus and Fast PKI Setup
Abstract

The Bitcoin backbone protocol (Eurocrypt 2015) extracts basic properties of Bitcoin’s underlying blockchain data structure, such as “common prefix” and “chain quality,” and shows how fundamental applications including consensus and a robust public transaction ledger can be built on top of them. The underlying assumptions are “proofs of work” (POWs), adversarial hashing power strictly less than 1/2 and no adversarial pre-computation—or, alternatively, the existence of an unpredictable “genesis” block.In this paper we first show how to remove the latter assumption, presenting a “bootstrapped” Bitcoin-like blockchain protocol relying on POWs that builds genesis blocks “from scratch” in the presence of adversarial pre-computation. Importantly, the round complexity of the genesis block generation process is independent of the number of participants.Next, we consider applications of our construction, including a PKI generation protocol and a consensus protocol without trusted setup assuming an honest majority (in terms of computational power). Previous results in the same setting (unauthenticated parties, no trusted setup, POWs) required a round complexity linear in the number of participants.

2014

EPRINT

2008

EPRINT

Sound and Fine-grain Specification of Cryptographic Tasks
Abstract

The Universal Composability (UC) framework, introduced by Canetti,
allows for the design of cryptographic protocols satisfying strong
security properties, such as non-malleability and preservation of
security under (concurrent) composition. In the UC framework (as in
several other frameworks), the security of a protocol carrying out a
given task is formulated via the ``trusted-party paradigm,'' where
the protocol execution is compared with an ideal process where the
outputs are computed by a trusted party that sees all the inputs. A
protocol is said to securely carry out a given task if running the
protocol with a realistic adversary amounts to ``emulating'' the
ideal process with the appropriate trusted party. In the UC
framework the program run by the trusted party is called an {\em
ideal functionality}.
However, while this simulation-based security formulation provides
strong security guarantees, its usefulness is contingent on the
properties and correct specification of the realized ideal
functionality, which, as demonstrated in recent years by the
coexistence of complex, multiple functionalities for the same task
as well as by their ``unstable'' nature, does not seem to be an easy
task. On the other hand, the more traditional, {\em gamed-based}
definitions of cryptographic tasks, although providing a less
satisfying level of security (stand-alone executions, or executions
in very controlled settings), have been successful in terms of
formalizing as well as capturing the underlying task's natural
properties.
In this paper we address this gap in the security modeling of
cryptographic properties, and introduce a general methodology for
translating game-based definitions of properties of cryptographic
tasks to syntactically concise ideal functionality programs.
Moreover, taking advantage of a suitable algebraic structure of the
space of our ideal functionality programs, we are able to
``accumulate'' ideal functionalities based on many different
game-based security notions. In this way, we can obtain a
well-defined mapping of all the game-based security properties of a
cryptographic task to its corresponding UC counterpart. In addition,
the methodology allows us to ``debug'' existing ideal
functionalities, establish relations between them, and make some
critical observations about the modeling of the ideal process in the
UC framework. We demonstrate the power of our approach by applying
our methodology to a variety of basic cryptographic tasks, including
commitments, digital signatures, public-key encryption, zero-knowledge proofs, and oblivious transfer.
Instrumental in our translation methodology is the new notion of a
{\em canonical functionality class} for a cryptographic task which
is endowed with a bounded semilattice structure. This structure
allows the grading of ideal functionalities according to the level
of security they offer as well as their natural joining, enabling
the modular combination of security properties.

2008

EPRINT

Somewhat Non-Committing Encryption and Efficient Adaptively Secure Oblivious Transfer
Abstract

Designing efficient cryptographic protocols tolerating adaptive
adversaries, who are able to corrupt parties on the fly as the
computation proceeds, has been an elusive task. Indeed, thus far no
\emph{efficient} protocols achieve adaptive security for general
multi-party computation, or even for many specific two-party tasks
such as oblivious transfer (OT). In fact, it is difficult and
expensive to achieve adaptive security even for the task of
\emph{secure communication}, which is arguably the most basic task
in cryptography.
In this paper we make progress in this area. First, we introduce a
new notion called \emph{semi-adaptive} security which is slightly
stronger than static security but \emph{significantly weaker than
fully adaptive security}. The main difference between adaptive and
semi-adaptive security is that, for semi-adaptive security, the
simulator is not required to handle the case where \emph{both}
parties start out honest and one becomes corrupted later on during
the protocol execution. As such, semi-adaptive security is much
easier to achieve than fully adaptive security. We then give a
simple, generic protocol compiler which transforms any
semi-adaptively secure protocol into a fully adaptively secure one.
The compilation effectively decomposes the problem of adaptive
security into two (simpler) problems which can be tackled
separately: the problem of semi-adaptive security and the problem of
realizing a weaker variant of secure channels.
We solve the latter problem by means of a new primitive that we call
{\em somewhat non-committing encryption} resulting in significant
efficiency improvements over the standard method for realizing
(fully) secure channels using (fully) non-committing encryption.
Somewhat non-committing encryption has two parameters: an
equivocality parameter $\ell$ (measuring the number of ways that a
ciphertext can be ``opened'') and the message sizes $k$. Our
implementation is very efficient for small values $\ell$,
\emph{even} when $k$ is large. This translates into a very efficient
compilation of many semi-adaptively secure protocols (in particular,
for a task with small input/output domains such as bit-OT) into a
fully adaptively secure protocol.
Finally, we showcase our methodology by applying it to the recent
Oblivious Transfer protocol by Peikert \etal\ [Crypto 2008], which
is only secure against static corruptions, to obtain the first
efficient (expected-constant round, expected-constant number of
public-key operations), adaptively secure and composable bit-OT
protocol.

2007

EPRINT

Almost-everywhere Secure Computation
Abstract

Secure multi-party computation (MPC) is a central problem in cryptography. Unfortunately, it is well known that MPC is possible if and only if the underlying communication network has very large connectivity---specifically, $\Omega(t)$, where $t$ is the number of potential corruptions in the network. This impossibility result renders existing MPC results far less applicable in practice, since most deployed networks have in fact a very small degree.
In this paper, we show how to circumvent this impossibility result and achieve meaningful security guarantees for graphs with small degree (such as expander graphs and several other topologies). In fact, the notion we introduce, which we call {\em almost-everywhere MPC}, building on the notion of almost-everywhere agreement due to Dwork, Peleg, Pippenger and Upfal, allows the degree of the network to be much smaller than the total number of allowed corruptions. In essence, our definition allows the adversary to {\em implicitly} wiretap some of the good nodes by corrupting sufficiently many nodes in the ``neighborhood'' of those nodes. We show protocols that satisfy our new definition, retaining both correctness and privacy for most nodes despite small connectivity, no matter how the adversary chooses his corruptions.
Instrumental in our constructions is a new model and protocol for the {\em secure message transmission} (SMT) problem, which we call {\em SMT by public discussion}, and which we use for the establishment of pairwise secure channels in limited connectivity networks.

2006

EPRINT

Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions
Abstract

Searchable symmetric encryption (SSE) allows a party to outsource the storage of
his data to another party in a private manner, while maintaining the ability to
selectively search over it. This problem has been the focus of active research
and several security definitions and constructions have been proposed. In this
paper we review existing security definitions, pointing out their shortcomings,
and propose two new stronger definitions which we prove equivalent. We then
present two constructions that we show secure under our new definitions.
Interestingly, in addition to satisfying stronger security guarantees, our
constructions are more efficient than all previous constructions.
Further, prior work on SSE only considered the setting where only the owner of
the data is capable of submitting search queries. We consider the natural
extension where an arbitrary group of parties other than the owner can submit
search queries. We formally define SSE in this multi-user setting, and
present an efficient construction.

2005

EPRINT

Resource Fairness and Composability of Cryptographic Protocols
Abstract

We introduce the notion of {\em resource-fair} protocols.
Informally, this property states that if one party learns the
output of the protocol, then so can all other parties, as long as
they expend roughly the same amount of resources. As opposed to
similar previously proposed definitions, our definition follows
the standard simulation paradigm and enjoys strong composability
properties. In particular, our definition is similar to the
security definition in the universal composability (UC) framework,
but works in a model that allows any party to request additional
resources from the environment to deal with dishonest parties that
may prematurely abort.
In this model we specify the ideally fair functionality as
allowing parties to ``invest resources'' in return for outputs,
but in such an event offering all other parties a fair deal. (The
formulation of fair dealings is kept independent of any particular
functionality, by defining it using a ``wrapper.'') Thus, by
relaxing the notion of fairness, we avoid a well-known
impossibility result for fair multi-party computation with
corrupted majority; in particular, our definition admits
constructions that tolerate arbitrary number of corruptions. We
also show that, as in the UC framework, protocols in our framework
may be arbitrarily and concurrently composed.
Turning to constructions, we define a ``commit-prove-fair-open''
functionality and design an efficient resource-fair protocol that
securely realizes it, using a new variant of a cryptographic
primitive known as ``time-lines.'' With (the fairly wrapped
version of) this functionality we show that some of the existing
secure multi-party computation protocols can be easily transformed
into resource-fair protocols while preserving their security.

2004

EPRINT

Efficient and Secure Multi-Party Computation with Faulty Majority and Complete Fairness
Abstract

We study the problem of constructing secure multi-party computation
(MPC) protocols that are {\em completely fair} --- meaning that either
all the parties learn the output of the function, or nobody does ---
even when a majority of the parties are corrupted. We first propose a
framework for fair multi-party computation, within which we formulate
a definition of secure and fair protocols. The definition follows the
standard simulation paradigm, but is modified to allow the protocol to
depend on the runing time of the adversary. In this way, we avoid a
well-known impossibility result for fair MPC with corrupted majority;
in particular, our definition admits constructions that tolerate up to
$(n-1)$ corruptions, where $n$ is the total number of parties. Next,
we define a ``commit-prove-fair-open'' functionality and construct an
efficient protocol that realizes it, using a new variant of a
cryptographic primitive known as ``time-lines.'' With this
functionality, we show that some of the existing secure MPC protocols
can be easily transformed into fair protocols while preserving their
security.
Putting these results together, we construct efficient, secure MPC
protocols that are completely fair even in the presence of corrupted
majorities. Furthermore, these protocols remain secure when
arbitrarily composed with any protocols, which means, in particular,
that they are concurrently-composable and non-malleable. Finally, as
an example of our results, we show a very efficient protocol that
fairly and securely solves the socialist millionaires' problem.

2004

EPRINT

Efficient and Universally Composable Committed Oblivious Transfer and Applications
Abstract

Committed Oblivious Transfer (COT) is a useful cryptographic primitive
that combines the functionalities of bit commitment and oblivious
transfer. In this paper, we introduce an extended version of COT
(ECOT) which additionally allows proofs of relations among committed
bits, and we construct an efficient protocol that securely realizes an
ECOT functionality in the universal-composability (UC) framework in
the common reference string (CRS) model. Our construction is more
efficient than previous (non-UC) constructions of COT, involving only
a constant number of exponentiations and communication rounds. Using the ECOT functionality as a building block, we construct efficient UC protocols for general two-party and multi-party functionalities (in the CRS model), each gate requiring a constant number of ECOT's.

2003

EPRINT

Strengthening Zero-Knowledge Protocols using Signatures
Abstract

Recently there has been an interest in zero-knowledge protocols
with stronger properties, such as concurrency, unbounded simulation
soundness, non-malleability, and universal composability.
In this paper, we show a novel technique to convert a large class of
existing honest-verifier zero-knowledge protocols into ones with these
stronger properties in the common reference string model.
More precisely, our technique utilizes a signature scheme
existentially unforgeable against adaptive chosen-message attacks, and
transforms any $\Sigma$-protocol (which is honest-verifier
zero-knowledge) into an unbounded simulation sound concurrent
zero-knowledge protocol. We also introduce $\Omega$-protocols,
a variant of $\Sigma$-protocols for which our technique further
achieves the properties of non-malleability and/or universal
composability.
In addition to its conceptual simplicity, a main advantage of
this new technique over previous ones is that
it avoids the Cook-Levin theorem, which tends to be rather
inefficient. Indeed, our technique allows for very efficient
instantiation based on the security of some efficient
signature schemes and standard number-theoretic assumptions.
For instance, one instantiation of our technique yields a
universally composable zero-knowledge protocol under the
Strong RSA assumption, incurring an overhead of a small
constant number of exponentiations, plus the generation of two
signatures.

2003

EPRINT

Timed Fair Exchange of Standard Signatures
Abstract

In this paper we show how to achieve timed fair exchange of digital
signatures of standard type.
Timed fair exchange (in particular, contract signing)
has been considered before, but only for Rabin and RSA signatures
of a special kind.
Our construction follows the gradual release paradigm, and works on
a new ``time'' structure that we call a {\em mirrored time-line.}
Using this structure, we design a protocol for the timed fair exchange
by two parties of arbitrary values (values lying on their respective
mirrored time-lines). Finally, we apply the blinding techniques of
Garay and Jakobsson to turn this protocol into a protocol for the timed
fair exchange of standard signatures.
The length of these mirrored time-lines makes another problem apparent, which
is making sure that the underlying sequence has a period large enough
so that cycling is not observed.
We also show how to construct these structures
so that, under reasonable assumptions, this is indeed the case.

2002

EPRINT

Timed Release of Standard Digital Signatures
Abstract

In this paper we investigate the timed release of standard digital signatures, and demonstrate how to do it for RSA, Schnorr and DSA signatures. Such signatures, once released, cannot be distinguished from signatures of the same type obtained without a timed
release, making it transparent to an observer of the end result.
While previous work has allowed timed release of signatures,
these have not been standard, but special-purpose signatures.
Building on the recent work by Boneh and Naor on timed commitments,
we introduce the notion of a reusable time-line, which,
besides allowing the release of standard signatures, lowers the session costs of existing timed applications.

2002

EPRINT

Efficient and Player-Optimal Strong Consensus
Abstract

In the {\em strong consensus} problem,
$n$ players attempt to reach agreement on a value initially held
by {\em one of the good players}, despite the (malicious) behavior
of up to $t$ of them. Although the problem is closely related to the
standard consensus problem (aka Byzantine agreement),
the only known solution with the optimal number of players requires exponential
computation and communication in the unconditional setting.
In this paper we study this problem, and present {\em efficient} protocols
and tight lower bounds for several standard distributed computation models
--- unconditional, computational, synchronous, and asynchronous.

1998

EPRINT

Fast Batch Verification for Modular Exponentiation and Digital Signatures
Abstract

Many tasks in cryptography (e.g., digital signature
verification) call for verification of a basic operation like modular
exponentiation in some group: given (g,x,y) check that g<sup>x</sup>=y.
This is typically done by re-computing g<sup>x</sup> and checking we get y.
We would like to do it differently, and faster.
The approach we use is batching. Focusing first on the basic modular
exponentiation operation, we provide some probabilistic batch verifiers, or
tests, that verify a sequence of modular exponentiations significantly faster
than the naive re-computation method. This yields speedups for several
verification tasks that involve modular exponentiations.
Focusing specifically on digital signatures, we then suggest a weaker notion of
(batch) verification which we call ``screening.'' It seems useful for many
usages of signatures, and has the advantage that it can be done very fast;
in particular, we show how to screen a sequence of RSA signatures at the
cost of one RSA verification plus hashing.

1998

EPRINT

Secure Distributed Storage and Retrieval
Abstract

In his well-known Information Dispersal Algorithm paper, Rabin showed
a way to distribute information in n pieces among n servers in such a
way that recovery of the information is possible in the presence of up
to t inactive servers. An enhanced mechanism to enable construction
in the presence of malicious faults, which can intentionally modify
their pieces of the information, was later presented by Krawczyk.
Yet, these methods assume that the malicious faults occur only at
reconstruction time. <P>
In this paper we address the more general problem of secure storage
and retrieval of information (SSRI), and guarantee that also the
process of storing the information is correct even when some of the
servers fail. Our protocols achieve this while maintaining the
(asymptotical) space optimality of the above methods. <P>
We also consider SSRI with the added requirement of confidentiality,
by which no party except for the rightful owner of the information is
able to learn anything about it. This is achieved through novel
applications of cryptographic techniques, such as the distributed
generation of receipts, distributed key management via threshold
cryptography, and ``blinding.'' <P>
An interesting byproduct of our scheme is the construction of a secret
sharing scheme with shorter shares size in the amortized sense. An
immediate practical application of our work is a system for the secure
deposit of sensitive data. We also extend SSRI to a ``proactive''
setting, where an adversary may corrupt all the servers during the
lifetime of the system, but only a fraction during any given time
interval.

#### Program Committees

- Eurocrypt 2019
- Eurocrypt 2016
- Crypto 2014 (Program chair)
- Crypto 2013 (Program chair)
- Crypto 2012
- TCC 2011
- PKC 2009
- PKC 2008
- PKC 2007
- Eurocrypt 2006
- PKC 2006
- PKC 2005
- Eurocrypt 2004
- Eurocrypt 2003
- Crypto 2002

#### Coauthors

- Christian Badertscher (1)
- Mihir Bellare (2)
- Nishanth Chandran (2)
- Wutichai Chongchitmate (1)
- Ran Cohen (3)
- Sandro Coretti (3)
- Reza Curtmola (1)
- Matthias Fitzi (5)
- Matthew K. Franklin (1)
- Ran Gelles (2)
- Rosario Gennaro (1)
- Clint Givens (1)
- Shafi Goldwasser (1)
- Shyamnath Gollakota (1)
- Martin Hirt (1)
- Yuval Ishai (2)
- Markus Jakobsson (2)
- David S. Johnson (2)
- Charanjit S. Jutla (1)
- Seny Kamara (1)
- Jonathan Katz (1)
- Aggelos Kiayias (8)
- Ranjit Kumaresan (1)
- Nikos Leonardos (3)
- Philip D. MacKenzie (9)
- Ueli Maurer (3)
- Rafail Ostrovsky (10)
- Giorgos Panagiotakos (3)
- Carl Pomerance (1)
- Manoj Prabhakaran (3)
- Tal Rabin (3)
- C. Pandu Rangan (1)
- Berry Schoenmakers (1)
- K. Srinathan (1)
- Jessica Staddon (1)
- Björn Tackmann (2)
- Daniel Tschudi (1)
- S. Harsha Vardhan (1)
- José Villegas (1)
- Hoeteck Wee (1)
- Daniel Wichs (2)
- Avishai Wool (1)
- Ke Yang (8)
- Moti Yung (2)
- Hong-Sheng Zhou (3)
- Vassilis Zikas (10)