## CryptoDB

### Giovanni Di Crescenzo

#### Publications

**Year**

**Venue**

**Title**

2006

EPRINT

Concurrently Non-Malleable Zero Knowledge in the Authenticated Public-Key Model
Abstract

We consider a type of zero-knowledge protocols that are of interest
for their practical applications within networks like the Internet:
efficient zero-knowledge arguments of knowledge that remain secure
against concurrent man-in-the-middle attacks. As negative results in
the area of concurrent non-malleable zero-knowledge imply that
protocols in the standard setting (i.e., under no setup assumptions)
can only be given for trivial languages, researchers have studied
such protocols in models with setup assumptions, such as the common
reference string (CRS) model. This model assumes that a reference
string is honestly created at the beginning of all interactions and
later available to all parties (an assumption that is satisfied, for
instance, in the presence of a trusted party).
A growing area of research in Cryptography is that of reducing the
setup assumptions under which certain cryptographic protocols can be
realized. In an effort to reduce the setup assumptions required for
efficient zero-knowledge arguments of knowledge that remain secure
against concurrent man-in-the-middle attacks, we consider a model,
which we call the Authenticated Public-Key (APK) model. The APK
model seems to significantly reduce the setup assumptions made by the CRS model
(as no trusted party or honest execution of a centralized algorithm
are required), and can be seen as a slightly stronger variation of
the Bare Public-Key (BPK) model from \cite{CGGM,MR}, and a
weaker variation of the registered public-key model used in \cite{BCNP}.
We then define and study man-in-the-middle attacks in the APK model.
Our main result is a constant-round concurrent non-malleable
zero-knowledge argument of knowledge for any polynomial-time
relation (associated to a language in $\mathcal{NP}$), under the
(minimal) assumption of the existence of a one-way function family.
We also show time-efficient instantiations of our protocol, in which
the transformation from a 3-round honest-verifier zero-knowledge
argument of knowledge to a 4-round concurrently non-malleable
zero-knowledge argument of knowledge for the same relation incurs
only $\mathcal{O}(1)$ (precisely, a {\em small} constant) additional
modular exponentiations, based on known number-theoretic
assumptions. Furthermore, the APK model is motivated by the
consideration of some man-in-the-middle attacks in models with setup
assumptions that had not been considered previously and might be of
independent interest.
We also note a negative result with respect to further reducing the
setup assumptions of our protocol to those in the (unauthenticated)
BPK model, by showing that concurrently non-malleable zero-knowledge
arguments of knowledge in the BPK model are only possible for
trivial languages.

2004

CRYPTO

2003

EPRINT

Public Key Encryption with keyword Search
Abstract

We study the problem of searching on data that is encrypted using a
public key system. Consider user Bob who sends email to user Alice
encrypted under Alice's public key. An email gateway wants to test
whether the email contains the keyword `urgent' so that it could
route the email accordingly. Alice, on the other hand does not wish
to give the gateway the ability to decrypt all her messages. We define
and construct a mechanism that enables Alice to provide a key to the
gateway that enables the gateway to test whether the word `urgent'
is a keyword in the email without learning anything else about the
email. We refer to this mechanism as <I>Public Key Encryption with
keyword Search</I>. As another example, consider a mail server that
stores various messages publicly encrypted for Alice by others. Using
our mechanism Alice can send the mail server a key that will enable
the server to identify all messages containing some specific keyword,
but learn nothing else. We define the concept of public key
encryption with keyword search and give several constructions.

2001

EPRINT

Efficient and Non-Interactive Non-Malleable Commitment
Abstract

We present new constructions of non-malleable commitment schemes, in
the public parameter model (where a trusted party makes parameters
available to all parties), based on the discrete logarithm or RSA
assumptions. The main features of our schemes are: they achieve
near-optimal communication for arbitrarily-large messages and are
non-interactive. Previous schemes either required (several rounds of)
interaction or focused on achieving non-malleable commitment based on
general assumptions and were thus efficient only when committing to a
single bit. Although our main constructions are for the case of
perfectly-hiding commitment, we also present a communication-efficient,
non-interactive commitment scheme (based on general assumptions) that
is perfectly binding.

1998

EPRINT

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof
Abstract

The input to the Graph Clustering Problem
consists of a sequence of integers $m_1,...,m_t$
and a sequence of $\sum_{i=1}^{t}m_i$ graphs.
The question is whether the equivalence classes,
under the graph isomorphism relation,
of the input graphs have sizes which match the input sequence of integers.
In this note we show that this problem has a (perfect) zero-knowledge
interactive proof system.
This result improves over <a href="http:../1996/96-14.html">record 96-14</a>,
where a parametrized (by the sequence of integers)
version of the problem was studied.

1998

EPRINT

Security amplification by composition: The case of doubly-iterated, ideal ciphers
Abstract

We investigate, in the Shannon model, the security of constructions
corresponding to double and (two-key) triple DES. That is, we
consider F<sub>k1</sub>(F<sub>k2</sub>(.)) and
F<sub>k1</sub>(F<sub>k2</sub><sup>-1</sup>(F<sub>k1</sub>(.))) with
the component functions being ideal ciphers. This models the
resistance of these constructions to ``generic'' attacks like meet
in the middle attacks.
We obtain the first proof that composition actually
increases the security in some meaningful sense. We compute a bound
on the probability of breaking the double cipher as a function of
the number of computations of the base cipher made, and the number
of examples of the composed cipher seen, and show that the success
probability is the square of that for a single key cipher. The
same bound holds for the two-key triple cipher. The first bound
is tight and shows that meet in the middle is the best possible
generic attack against the double cipher.

1994

ASIACRYPT

#### Program Committees

- PKC 2007
- Asiacrypt 2006
- PKC 2003
- Crypto 2002
- Asiacrypt 2002

#### Coauthors

- William Aiello (2)
- Mihir Bellare (2)
- Carlo Blundo (1)
- Dan Boneh (2)
- Mike Burmester (1)
- Bren Cavallo (1)
- Stefano D'Amiano (2)
- Yi Deng (1)
- Yvo Desmedt (1)
- Antonio Giorgio Gaggia (1)
- Oded Goldreich (1)
- Yuval Ishai (1)
- Delaram Kahrobaei (1)
- Jonathan Katz (2)
- Dongdai Lin (1)
- Richard J. Lipton (1)
- Tal Malkin (1)
- Tatsuaki Okamoto (1)
- Rafail Ostrovsky (9)
- Giuseppe Persiano (7)
- Sivaramakrishnan Rajagopalan (1)
- Amit Sahai (1)
- Alfredo De Santis (4)
- Vladimir Shpilrain (1)
- Adam Smith (2)
- Ugo Vaccaro (1)
- Ramarathnam Venkatesan (2)
- Ivan Visconti (2)
- Shabsi Walfish (1)
- Moti Yung (1)