## CryptoDB

### Ke Yang

#### Affiliation: Google Inc

#### Publications

**Year**

**Venue**

**Title**

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

TCC

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

On Simulation-Sound Trapdoor Commitments
Abstract

We study the recently introduced notion of a simulation-sound trapdoor
commitment (SSTC) scheme. In this paper, we present a new, simpler
definition for an SSTC scheme that admits more efficient constructions
and can be used in a larger set of applications. Specifically, we
show how to construct SSTC schemes from any one-way functions, and how
to construct very efficient SSTC schemes based on specific
number-theoretic assumptions. We also show how to construct
simulation-sound, non-malleable, and universally-composable
zero-knowledge protocols using SSTC schemes, yielding, for instance,
the most efficient universally-composable zero-knowledge protocols
known. Finally, we explore the relation between SSTC schemes and
non-malleable commitment schemes by presenting a sequence of
implication and separation results, which in particular imply that
SSTC schemes are non-malleable.

2001

EPRINT

On the (Im)possibility of Obfuscating Programs
Abstract

Informally, an {\em obfuscator} $O$ is an (efficient,
probabilistic) ``compiler'' that takes as input a program (or
circuit) $P$ and produces a new program $O(P)$ that has the
same functionality as $P$ yet is ``unintelligible'' in some sense.
Obfuscators, if they exist, would have a wide variety of
cryptographic and complexity-theoretic applications, ranging from
software protection to homomorphic encryption to
complexity-theoretic analogues of Rice's theorem. Most of these
applications are based on an interpretation of the
``unintelligibility'' condition in obfuscation as meaning that
$O(P)$ is a ``virtual black box,'' in the sense that anything
one can efficiently compute given $O(P)$, one could also
efficiently compute given oracle access to $P$.
In this work, we initiate a theoretical investigation of
obfuscation. Our main result is that, even under very
weak formalizations of the above intuition, obfuscation
is impossible. We prove this by constructing a family of
functions $F$ that are {\em \inherently
unobfuscatable} in the following sense: there is a
property $\pi : F \rightarrow \{0,1\}$ such that (a) given {\em
any program} that computes a function $f\in F$, the
value $\pi(f)$ can be efficiently computed, yet (b) given
{\em oracle access} to a (randomly selected) function
$f\in F$, no efficient algorithm can compute $\pi(f)$
much better than random guessing.
We extend our impossibility result in a number of ways, including
even obfuscators that (a) are not necessarily computable in
polynomial time, (b) only {\em approximately} preserve the
functionality, and (c) only need to work for very restricted
models of computation ($TC_0$). We also rule out several
potential applications of obfuscators, by constructing
``unobfuscatable'' signature schemes, encryption schemes, and
pseudorandom function families.

#### Coauthors

- Boaz Barak (2)
- Juan A. Garay (8)
- Oded Goldreich (2)
- Russell Impagliazzo (2)
- Philip D. MacKenzie (11)
- Manoj Prabhakaran (3)
- Michael K. Reiter (1)
- Steven Rudich (2)
- Amit Sahai (2)
- Salil P. Vadhan (2)