International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Erez Petrank

Publications

Year
Venue
Title
2010
EPRINT
On Achieving the "Best of Both Worlds" in Secure Multiparty Computation
Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Protocols designed under this assumption provide ``full security'' (and, in particular, guarantee output delivery and fairness) when this assumption holds; unfortunately, these protocols are completely insecure if this assumption is violated. On the other hand, protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a \emph{single} party is dishonest. It is natural to wonder whether it is possible to achieve the ``best of both worlds'': namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) but show some positive results regarding what \emph{can} be achieved.
2010
EPRINT
Black-Box Constructions of Protocols for Secure Computation
It is well known that secure computation without an honest majority requires computational assumptions. An interesting question that therefore arises relates to the way such computational assumptions are used. Specifically, can the secure protocol use the underlying primitive (e.g., a one-way trapdoor permutation) in a {\em black-box} way, treating it as an oracle, or must it be {\em nonblack-box} (by referring to the code that computes the primitive)? Despite the fact that many general constructions of cryptographic schemes refer to the underlying primitive in a black-box wayonly, there are some constructions that are inherently nonblack-box. Indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive). In this paper, we study whether such nonblack-box use is essential. We answer this question in the negative. Concretely, we present a \emph{fully black-box reduction} from oblivious transfer with security against malicious parties to oblivious transfer with security against semi-honest parties. As a corollary, we get the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which only make a {\em black-box} use of semi-honest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption.
2006
CRYPTO
2003
CRYPTO
2003
CRYPTO
2003
EUROCRYPT
2002
EPRINT
Efficient and Concurrent Zero-Knowledge from any public coin HVZK protocol
Daniele Micciancio Erez Petrank
We show how to efficiently transform any public coin honest verifier zero knowledge proof system into a proof system that is concurrent zero-knowledge with respect to any (possibly cheating) verifier via black box simulation. By efficient we mean that our transformation incurs only an additive overhead, both in terms of the number of rounds and the computational and communication complexity of each round, independently of the complexity of the original protocol. Moreover, the transformation preserves (up to negligible additive terms) the soundness and completeness error probabilities. The new proof system is proved secure based on the Decisional Diffie-Hellman (DDH) assumption, in the standard model of computation, i.e., no random oracles, shared random strings, or public key infrastructure is assumed. In addition to the introduction of a practical protocol, this construction provides yet another example of ideas in plausibility results that turn into ideas in the construction of practical protocols. We prove our main result by developing a mechanism for simulatable commitments that may be of independent interest. In particular, it allows a weaker result that is interesting as well. We present an efficient transformation of any honest verifier public-coin computational zero-knowledge proof into a (public coin) computational zero-knowledge proof secure against any verifier. The overhead of this second transformation is minimal: we only increase the number of rounds by 3, and increase the computational cost by 2 public key operations for each round of the original protocol. The cost of the more general transformation leading to concurrent zero knowledge is also close to optimal (for black box simulation), requiring only omega(log n) additional rounds (where n is a security parameter and omega(log n) can be any superlogarithmic function of n (e.g., log(n)log^*(n)), and omega(log n) additional public key operations for each round of the original protocol.
2001
ASIACRYPT
2001
EPRINT
Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds
We show that any concurrent zero-knowledge protocol for a non-trivial language (i.e., for a language outside $\BPP$), whose security is proven via black-box simulation, must use at least $\tilde\Omega(\log n)$ rounds of interaction. This result achieves a substantial improvement over previous lower bounds, and is the first bound to rule out the possibility of constant-round concurrent zero-knowledge when proven via black-box simulation. Furthermore, the bound is polynomially related to the number of rounds in the best known concurrent zero-knowledge protocol for languages in $\NP$.
2000
EPRINT
Concurrent Zero-Knowledge in Poly-logarithmic Rounds
Joe Kilian Erez Petrank
A proof is concurrent zero-knowledge if it remains zero-knowledge when run in an asynchronous environment, such as the Internet. It is known that zero-knowledge is not necessarily preserved in such an environment; Kilian, Petrank and Rackoff have shown that any {\bf 4} rounds zero-knowledge interactive proof (for a non-trivial language) is not concurrent zero-knowledge. On the other hand, Richardson and Kilian have shown that there exists a concurrent zero-knowledge argument for all languages in NP, but it requires a {\bf polynomial} number of rounds. In this paper, we present a concurrent zero-knowledge proof for all languages in NP with a drastically improved complexity: our proof requires only a poly-logarithmic, specifically, $\omega(\log^2 k)$ number of rounds. Thus, we narrow the huge gap between the known upper and lower bounds on the number of rounds required for a zero-knowledge proof that is robust for asynchronous composition.
2000
JOFC
1998
CRYPTO
1998
JOFC
1997
EPRINT
CBC MAC for Real-Time Data Sources
Erez Petrank Charles Rackoff
The Cipher Block Chaining (CBC) Message Authentication Code (MAC) is an authentication method which is widely used in practice. It is well known that the naive use of CBC MAC for variable length messages is not secure, and a few rules of thumb for the correct use of CBC MAC are known by folklore. The first rigorous proof of the security of CBC MAC, when used on fixed length messages, was given only recently by Bellare, Kilian and Rogaway. They also suggested variants of CBC MAC that handle variable length messages but in these variants the length of the message has to be known in advance (i.e., before the message is processed). We study CBC authentication of real time applications in which the length of the message is not known until the message ends, and furthermore, since the application is real-time, it is not possible to start processing the authentication only after the message ends. We first present a variant of CBC MAC, called {\em double MAC} (DMAC) which handles messages of variable unknown lengths. Computing DMAC on a message is virtually as simple and as efficient as computing the standard CBC MAC on the message. We provide a rigorous proof that its security is implied by the security of the underlying block cipher. Next, we argue that the basic CBC MAC is secure when applied to prefix free message space. A message space can be made prefix free by authenticating also the (usually hidden) last character which marks the end of the message.
1997
EPRINT
Identity Escrow
Joe Kilian Erez Petrank
We introduce the notion of escrowed identity, an application of key-escrow ideas to the problem of identification. In escrowed identity, one party, A, does not give his identity to another party B, but rather gives him information that would allow an authorized third party, E, to determine A's identity. However, B receives a guarantee that E can indeed determine A's identity. We give protocols for escrowed identity based on the El-Gamal (signature and encryption) schemes and on the RSA function. A useful feature of our protocol is that after setting up A to use the system, E is only involved when it is actually needed to determine A's identity.

Program Committees

TCC 2005
Asiacrypt 2004
Crypto 2002
Crypto 2001