## CryptoDB

### Erez Petrank

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

On Achieving the "Best of Both Worlds" in Secure Multiparty Computation
Abstract

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
Abstract

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.

2002

EPRINT

Efficient and Concurrent Zero-Knowledge from any public coin HVZK protocol
Abstract

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

EPRINT

Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds
Abstract

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
Abstract

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.

1997

EPRINT

CBC MAC for Real-Time Data Sources
Abstract

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
Abstract

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

#### Coauthors

- Niv Buchbinder (1)
- Ran Canetti (1)
- Tzafrir Cohen (1)
- Iftach Haitner (1)
- Yuval Ishai (4)
- Jonathan Katz (1)
- Joe Kilian (7)
- Eyal Kushilevitz (3)
- Yehuda Lindell (3)
- Daniele Micciancio (2)
- Kobbi Nissim (1)
- Charles Rackoff (2)
- Alon Rosen (1)