## CryptoDB

### Rosario Gennaro

#### Affiliation: City College - CUNY

#### Publications

**Year**

**Venue**

**Title**

2018

CRYPTO

Threshold Cryptosystems from Threshold Fully Homomorphic Encryption
📺
Abstract

We develop a general approach to adding a threshold functionality to a large class of (non-threshold) cryptographic schemes. A threshold functionality enables a secret key to be split into a number of shares, so that only a threshold of parties can use the key, without reconstructing the key. We begin by constructing a threshold fully-homomorphic encryption scheme (ThFHE) from the learning with errors (LWE) problem. We next introduce a new concept, called a universal thresholdizer, from which many threshold systems are possible. We show how to construct a universal thresholdizer from our ThFHE. A universal thresholdizer can be used to add threshold functionality to many systems, such as CCA-secure public-key encryption (PKE), signature schemes, pseudorandom functions, and others primitives. In particular, by applying this paradigm to a (non-threshold) lattice signature system, we obtain the first single-round threshold signature scheme from LWE.

2018

TCC

Fine-Grained Secure Computation
Abstract

This paper initiates a study of Fine Grained Secure Computation: i.e. the construction of secure computation primitives against “moderately complex” adversaries. We present definitions and constructions for compact Fully Homomorphic Encryption and Verifiable Computation secure against (non-uniform)
$$\mathsf {NC}^1$$
adversaries. Our results do not require the existence of one-way functions and hold under a widely believed separation assumption, namely
$$\mathsf {NC}^{1}\subsetneq \oplus \mathsf {L}/ {\mathsf {poly}}$$
. We also present two application scenarios for our model: (i) hardware chips that prove their own correctness, and (ii) protocols against rational adversaries potentially relevant to the Verifier’s Dilemma in smart-contracts transactions such as Ethereum.

2012

ASIACRYPT

2010

EPRINT

Okamoto-Tanaka Revisited: Fully Authenticated Diffie-Hellman with Minimal Overhead
Abstract

Okamoto-Tanaka Revisited: Fully Authenticated Diffie-Hellman with Minimal Overhead
The Diffie-Hellman protocol (DHP) is one of the most studied protocols in cryptography. Much work has been dedicated to armor the original protocol against active attacks while incurring a minimal performance overhead relative to the basic (unauthenticated) DHP. This line of work has resulted in some remarkable protocols, e.g., MQV, where the protocol's communication cost is identical to that of the basic DHP and the computation overhead is small. Unfortunately, MQV and similar 2-message ``implicitly authenticated" protocols do not achieve full security against active attacks since they cannot provide forward secrecy (PFS), a major security goal of DHP, against active attackers.
In this paper we investigate the question of whether one can push the limits of authenticated DHPs even further, namely, to achieve communication complexity as in the original DHP (two messages with a single group element per message), maintain low computational overhead, and yet achieve full PFS against active attackers in a provable way. We answer this question in the affirmative by resorting to an old and elegant key agreement protocol: the Okamoto-Tanaka protocol \cite{okta}. We present a variant of the protocol (denoted mOT) which achieves the above minimal communication, incurs a computational overhead relative to the basic DHP that is practically negligible, and yet achieves full provable key agreement security, including PFS, against active attackers. Moreover, due to the identity-based properties of mOT, even the sending of certificates (typical for authenticated DHPs) can be avoided in the protocol.
As additional contributions, we apply our analysis to prove the security of a recent multi-domain extension of the Okamoto-Tanaka protocol by Schridde et al. and show how to adapt mOT to the (non id-based) certificate-based setting.

2008

EPRINT

Threshold RSA for Dynamic and Ad-Hoc Groups
Abstract

We consider the use of threshold signatures in ad-hoc and dynamic groups such as MANETs ("mobile ad-hoc networks"). While the known threshold RSA signature schemes have several properties that make them good candidates for deployment in these scenarios, we show that none of these schemes is practical enough for realistic use in these highly-constrained environments. In particular, this is the case of the most efficient of these threshold RSA schemes, namely, the one due to Shoup. Our contribution is in presenting variants of Shoup's protocol that overcome the limitations that make the original protocol unsuitable for dynamic groups. The resultant schemes provide the efficiency and flexibility needed in ad-hoc groups, and add the capability of incorporating new members (share-holders) to the group of potential signers without relying on central authorities. Namely, any threshold of existing members can cooperate to add a new member. The schemes are efficient, fully non-interactive and do not assume broadcast.

2008

EPRINT

Strongly-Resilient and Non-Interactive Hierarchical Key-Agreement in MANETs
Abstract

Key agreement is a fundamental security functionality by which pairs of nodes agree on shared keys to be used for protecting their pairwise communications. In this work we study key-agreement schemes that are well-suited for the mobile network environment.
Specifically, we describe schemes with the following haracteristics:
-- Non-interactive: any two nodes can compute a unique shared secret
key without interaction;
-- Identity-based: to compute the shared secret key, each node only
needs its own secret key and the identity of its peer;
-- Hierarchical: the scheme is decentralized through a
hierarchy where intermediate nodes in the hierarchy can derive the secret keys for each of its children without any limitations or prior knowledge on the number of such children or their identities;
-- Resilient: the scheme is fully resilient against compromise of
{\em any number of leaves} in the hierarchy, and of a threshold number of nodes in each of the upper levels of the hierarchy.
Several schemes in the literature have three of these four properties, but the schemes in this work are the first to possess all four. This makes them well-suited for environments such as MANETs and tactical networks which are very dynamic, have significant bandwidth and energy constraints, and where many nodes are vulnerable to compromise. We provide rigorous analysis of the proposed schemes and discuss implementations aspects.

2007

EPRINT

Faster and Shorter Password-Authenticated Key Exchange
Abstract

This paper presents an improved password-based authenticated key exchange protocols in the common reference string model. Its security proof requires no idealized assumption (such as random oracles).
The protocol is based on the GL framework introduced by Gennaro and Lindell, which generalizes the KOY key exchange protocol of Katz et al.\ Both the KOY and the GL protocols use (one-time) signatures as a
non-malleability tool in order to prevent a man-in-the-middle attack against the protocol. The efficiency of the resulting protocol is negatively affected, since if we use regular signatures, they require a large amount of computation (almost as much as the rest of the protocol) and further computational assumptions. If one-time signatures are used, they substantially increase the bandwidth requirement.
Our improvement avoids using digital signatures altogether, replacing them with faster and shorter message authentication codes. The crucial idea is to leverage as much as possible the non-malleability of the encryption scheme used in the protocol, by including various values into the ciphertexts as {\em labels}. As in the case of the GL framework, our protocol can be efficiently instantiated using either the DDH, Quadratic Residuosity or N-Residuosity Assumptions.
For typical security parameters our solution saves as much as 12 Kbytes of bandwidth if one-time signatures are implemented in \GL with
fast symmetric primitives. If we use number-theoretic signatures in the GL framework, our solution saves several large exponentiations (almost a third of the exponentiations computed in the GL protocol). The end result is that we bring provable security in the realm of password-authenticated key exchange one step closer to practical.

2006

EPRINT

Independent Zero-Knowledge Sets
Abstract

We define and construct Independent Zero-Knowledge Sets (ZKS) protocols. In a ZKS protocols, a Prover commits to a set $S$, and for any $x$, proves non-interactively to a Verifier if $x \in S$ or $x \notin S$ without revealing any other information about $S$.
In the {\em independent} ZKS protocols we introduce, the adversary is
prevented from successfully correlate her set to the one of a honest prover. Our notion of independence in particular implies that the
resulting ZKS protocol is non-malleable.
On the way to this result we define the notion of {\em independence} for commitment schemes. It is shown that this notion implies non-malleability, and we argue that this new notion has the potential to
simplify the design and security proof of non-malleable commitment schemes.
Efficient implementations of ZKS protocols are based on the notion of mercurial commitments. Our efficient constructions of independent
ZKS protocols requires the design of {\em new} commitment schemes that are simultaneously independent (and thus non-malleable) and mercurial.

2006

EPRINT

Deniable Authentication and Key Exchange
Abstract

We extend the definitional work of Dwork, Naor and Sahai from deniable authentication to deniable key-exchange protocols. We then use these definitions to prove the deniability features of SKEME and SIGMA, two natural and efficient protocols which serve as basis for the Internet Key Exchange (IKE) protocol. The two protocols require distinct approaches to their deniability analysis, hence highlighting important definitional issues as well as necessitating different tools in the analysis.
SKEME is an encryption-based protocol for which we prove full deniability based on the plaintext awareness of the underlying encryption scheme. Interestingly SKEME's deniability is possibly the first ``natural'' application which essentially requires plaintext awareness (until now this notion has been mainly used as a tool for proving chosen-ciphertext security); in particular this use of plaintext awareness is not tied to the random oracle model.
SIGMA, on the other hand, uses non-repudiable signatures for authentication and hence cannot be proven to be fully deniable. Yet we are able to prove a weaker, but meaningful, ``partial deniability" property: a party may not be able to deny that it was ``alive" at some point in time but can fully deny the contents of its communications and the identity of its interlocutors.
We remark that the deniability of SKEME and SIGMA holds in a concurrent setting and does not essentially rely on the random oracle model.

2005

EUROCRYPT

2005

EPRINT

Tag-KEM/DEM: A New Framework for Hybrid Encryption
Abstract

This paper presents a novel framework for the generic construction of hybrid encryption schemes which produces more efficient schemes than the ones known before. A previous framework introduced by Shoup combines a key encapsulation mechanism (KEM) and a data encryption mechanism (DEM). While it is sufficient to require both components to be secure against chosen ciphertext attacks (CCA-secure), Kurosawa and Desmedt showed a particular example of KEM that is not CCA-secure but can be securely combined with a specific type of CCA-secure DEM to
obtain a more efficient, CCA-secure hybrid encryption scheme. There are also many other efficient hybrid encryption schemes in the literature that do not fit Shoup's framework. These facts serve as motivation to seek another framework.
The framework we propose yields more efficient hybrid scheme, and in addition provides insightful explanation about existing schemes that do not fit into the previous framework. Moreover, it allows immediate
conversion from a class of threshold public-key encryption to a hybrid one without considerable overhead, which may not be possible in the previous approach.

2004

ASIACRYPT

2004

EPRINT

Secure Hashed Diffie-Hellman over Non-DDH Groups
Abstract

We show that in applications that use the Diffie-Hellman (DH) transform but
take care of hashing the DH output (as required, for example, for secure
DH-based encryption and key exchange) the usual requirement to work over a
DDH group (i.e., a group in which the Decisional Diffie-Hellman assumption
holds) can be relaxed to only requiring that the DH group contains a large
enough DDH subgroup. In particular, this implies the security of (hashed)
Diffie-Hellman over non-prime order groups such as $Z_p^*$. Moreover, our
results show that one can work directly over $Z_p^*$ without requiring any
knowledge of the prime factorization of $p-1$ and without even having to
find a generator of $Z_p^*$.
These results are obtained via a general characterization of DDH groups in
terms of their DDH subgroups, and a relaxation (called $t$-DDH)
of the DDH assumption via computational entropy.
We also show that, under the short-exponent
discrete-log assumption, the security of the hashed Diffie-Hellman transform
is preserved when replacing full exponents with short exponents.

2004

EPRINT

A Note on An Encryption Scheme of Kurosawa and Desmedt
Abstract

Recently Kurosawa and Desmedt
presented a new hybrid encryption scheme which
is secure against adaptive chosen-ciphertext attack. Their scheme is a
modification of the Cramer-Shoup encryption scheme. Its major advantage with
respect to Cramer-Shoup is that it saves the computation of one exponentiation
and produces shorter ciphertexts.
However, the proof presented by Kurosawa and Desmedt relies on the use of
information-theoretic key derivation and message authentication functions.
In this note we present a different proof of security
which shows that the Kurosawa-Desmedt
scheme can be instantiated with any computationally secure
key derivation and message authentication functions, thus extending
the applicability of their paradigm, and improving its efficiency.

2003

EPRINT

Secure Multiplication of Shared Secrets in the Exponent
Abstract

We present a new protocol for the following task. Given
tow secrets a,b shared among n players, compute the value
g^{ab}.
The protocol uses the generic BGW approach for multiplication
of shared secrets, but we show that if one is computing
``multiplications in the exponent'' the polynomial randomization
step can be avoided (assuming the Decisional Diffie-Hellman Assumption
holds). This results in a non-interactive and more efficient protocol.

2003

EPRINT

A Framework for Password-Based Authenticated Key Exchange
Abstract

In this paper we present a general framework for password-based
authenticated key exchange protocols, in the common reference
string model. Our protocol is actually an abstraction of the key
exchange protocol of Katz et al.\ and is based on the recently
introduced notion of smooth projective hashing by Cramer and
Shoup. We gain a number of benefits from this abstraction. First,
we obtain a modular protocol that can be described using just
three high-level cryptographic tools. This allows a simple and
intuitive understanding of its security. Second, our proof of
security is significantly simpler and more modular. Third, we are
able to derive analogues to the Katz et al.\ protocol under
additional cryptographic assumptions. Specifically, in addition to
the DDH assumption used by Katz et al., we obtain protocols under
both the Quadratic and $N$-Residuosity assumptions. In order to
achieve this, we construct new smooth projective hash functions.

2003

EPRINT

Multi-Trapdoor Commitments and their Applications to Non-Malleable Protocols
Abstract

We introduce the notion of multi-trapdoor commitments
which is a stronger form of trapdoor commitment schemes.
We then construct two very efficient instantiations of
multi-trapdoor commitment schemes, based on the Strong
RSA Assumption and the recently introduced Strong Diffie-Hellman
Assumption.
The main applications of our result are non-malleable
trapdoor commtiments and a compiler} that takes any proof of knowledge
and transforms it into one which is secure against a concurrent
man-in-the-middle attack. Such a proof of knowledge immediately
yields concurrently secure identification protocols.
When using our number-theoretic istantiations, the non-malleable
commitment and the
compiler are very efficient (require no more than
four exponentiations). The latter also maintains the round complexity of
the original proof of knowledge; it works in the common reference string
model, which in any case is necessary to prove security of proofs
of knowledge under this kind of attacks. Compared to previously
known efficient solutions, ours is a factor of two faster.

2000

EPRINT

Lower Bounds on the Efficiency of Generic Cryptographic Constructions
Abstract

We present lower bounds on the efficiency of
constructions for Pseudo-Random Generators (PRGs) and
Universal One-Way Hash Functions (UOWHFs) based on
black-box access to one-way permutations. Our lower bounds are tight as
they match the efficiency of known constructions.
A PRG (resp. UOWHF) construction based on black-box access is
a machine that is given oracle access to a permutation. Whenever
the permutation is hard to invert, the construction is hard to break.
In this paper we give lower bounds on the
number of invocations to
the oracle by the construction.
If $S$ is the assumed security of the oracle permutation $\pi$
(i.e. no adversary of size $S$ can invert $\pi$ on a fraction
larger than $1/S$ of its inputs)
then a PRG (resp. UOWHF) construction that
stretches (resp. compresses) its input by $k$ bits must query $\pi$
in $q=\Omega(k/\log S)$ points. This matches known constructions.
Our results are given in an extension of the Impagliazzo-Rudich
model. That is, we prove that a proof of the existence of PRG (resp. UOWHF)
black-box constructions that beat our lower bound would imply
a proof of the unconditional existence of such construction
(which would also imply $P \neq NP$).

1999

EPRINT

Secure Hash-and-Sign Signatures without the Random Oracle
Abstract

We present a new signature scheme which is existentially unforgeable
under chosen message attacks, assuming some variant of the RSA conjecture.
This scheme is not based on "signature trees", and instead it uses
the so called "hash-and-sign" paradigm. It is unique in that the
assumptions made on the cryptographic hash function in use are well
defined and reasonable (although non-standard). In particular, we
do not model this function as a random oracle.
We construct our proof of security in steps. First we describe and
prove a construction which operates in the random oracle model. Then
we show that the random oracle in this construction can be replaced
by a hash function which satisfies some strong (but well defined!)
computational assumptions. Finally, we demonstrate that these assumptions
are reasonable, by proving that a function satisfying them exists under
standard intractability assumptions.

1998

CRYPTO

1998

EPRINT

An Efficient Non-Interactive Statistical Zero-Knowledge Proof System for Quasi-Safe Prime Products
Abstract

We present efficient zero-knowledge proof systems for quasi-safe
prime products and other related languages. Quasi-safe primes are a
relaxation of safe primes, a class of prime numbers useful in many
cryptographic applications.
Our proof systems achieve higher security and better
efficiency than all previously known ones.
In particular, all our proof systems are perfect or statistical
zero-knowledge, meaning that even a computationally
unbounded adversary cannot extract any information
from the proofs.
Moreover, our proof systems are extremely efficient because they do
not use general reductions to NP-complete problems, can be easily
parallelized preserving zero-knowledge, and are non-interactive for
computationally unbounded provers. The prover can also be efficiently
implemented given some trapdoor information and using very little
interaction.
We demonstrate the applicability of quasi-safe primes
by showing how they can be effectively used in the
context of RSA based undeniable signatures to enforce
the use of ``good'' public keys, i.e.,
keys such that if a signer can convince a recipient
of the validity of a signature, then he won't be able to
subsequently deny the same signature in case of a dispute.

1998

EPRINT

Secure Distributed Storage and Retrieval
Abstract

In his well-known Information Dispersal Algorithm paper, Rabin showed
a way to distribute information in n pieces among n servers in such a
way that recovery of the information is possible in the presence of up
to t inactive servers. An enhanced mechanism to enable construction
in the presence of malicious faults, which can intentionally modify
their pieces of the information, was later presented by Krawczyk.
Yet, these methods assume that the malicious faults occur only at
reconstruction time. <P>
In this paper we address the more general problem of secure storage
and retrieval of information (SSRI), and guarantee that also the
process of storing the information is correct even when some of the
servers fail. Our protocols achieve this while maintaining the
(asymptotical) space optimality of the above methods. <P>
We also consider SSRI with the added requirement of confidentiality,
by which no party except for the rightful owner of the information is
able to learn anything about it. This is achieved through novel
applications of cryptographic techniques, such as the distributed
generation of receipts, distributed key management via threshold
cryptography, and ``blinding.'' <P>
An interesting byproduct of our scheme is the construction of a secret
sharing scheme with shorter shares size in the amortized sense. An
immediate practical application of our work is a system for the secure
deposit of sensitive data. We also extend SSRI to a ``proactive''
setting, where an adversary may corrupt all the servers during the
lifetime of the system, but only a fraction during any given time
interval.

#### Program Committees

- Crypto 2019
- Crypto 2015
- Crypto 2014
- Asiacrypt 2013
- PKC 2013
- TCC 2013
- Eurocrypt 2013
- PKC 2012
- PKC 2011
- Eurocrypt 2010
- PKC 2009
- PKC 2008
- Crypto 2007
- PKC 2006
- TCC 2005
- Eurocrypt 2004
- Eurocrypt 2002
- Asiacrypt 2001
- Crypto 1999

#### Coauthors

- Masayuki Abe (3)
- Scott Ames (1)
- Siavosh Benabbas (1)
- Dan Boneh (1)
- Emmanuel Bresson (1)
- Matteo Campanelli (1)
- Ran Canetti (1)
- Dario Catalano (11)
- Ronald Cramer (1)
- Dana Dachman-Soled (1)
- Yvo Desmedt (1)
- Yevgeniy Dodis (1)
- Joan G. Dyer (1)
- Nelly Fazio (2)
- Dario Fiore (4)
- Juan A. Garay (1)
- Craig Gentry (2)
- Steven Goldfeder (1)
- Shai Halevi (6)
- Johan Håstad (1)
- Carmit Hazay (2)
- Nick Howgrave-Graham (3)
- William E. Skeith III (1)
- Yuval Ishai (1)
- Aayush Jain (1)
- Stanislaw Jarecki (7)
- Charanjit S. Jutla (1)
- Jonathan Katz (1)
- Sam Kim (1)
- Hugo Krawczyk (20)
- Kaoru Kurosawa (4)
- Eyal Kushilevitz (1)
- Darren Leigh (1)
- Yehuda Lindell (2)
- Anna Lysyanskaya (1)
- Tal Malkin (2)
- Silvio Micali (3)
- Daniele Micciancio (2)
- Antonio Nicolosi (1)
- Luca Nizzardo (2)
- Bryan Parno (2)
- Valerio Pastro (1)
- Irippuge Milinda Perera (1)
- Tal Rabin (24)
- Mario Di Raimondo (5)
- Peter M. R. Rasmussen (1)
- Mariana Raykova (1)
- Steffen Reidt (1)
- Pankaj Rohatgi (1)
- Amit Sahai (1)
- Berry Schoenmakers (1)
- Victor Shoup (5)
- Jeffrey S. Sorensen (2)
- Ravi Sundaram (1)
- Luca Trevisan (1)
- Yevgeniy Vahlis (1)
- Konstantinos Vamvourellis (1)
- Muthuramakrishnan Venkitasubramaniam (1)
- Daniel Wichs (1)
- Stephen D. Wolthusen (1)
- William S. Yerazunis (1)