International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Ke Yang

Affiliation: Google Inc

Publications

Year
Venue
Title
2011
JOFC
2006
TCC
2006
JOFC
2005
EPRINT
Resource Fairness and Composability of Cryptographic Protocols
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
EUROCRYPT
2004
TCC
2004
EPRINT
Efficient and Secure Multi-Party Computation with Faulty Majority and Complete Fairness
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
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
EUROCRYPT
2003
EPRINT
Strengthening Zero-Knowledge Protocols using Signatures
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
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
CRYPTO
2001
EPRINT
On the (Im)possibility of Obfuscating Programs
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.