## CryptoDB

### Victor Shoup

#### Publications

**Year**

**Venue**

**Title**

2020

TCC

Security analysis of SPAKE2+
📺
Abstract

We show that a slight variant of Protocol SPAKE2+, which was presented but not analyzed in [Cash, Kiltz, Shoup 2008], is a secure *asymmetric* password-authenticated key exchange protocol (PAKE), meaning that the protocol still provides good security guarantees even if a server is compromised and the password file stored on the server is leaked to an adversary. The analysis is done in the UC framework (i.e., a simulation-based security model), under the computational Diffie-Hellman (CDH) assumption, and modeling certain hash functions as random oracles. The main difference between our variant and the original Protocol SPAKE2+ is that our variant includes standard key confirmation flows; also, adding these flows allows some slight simplification to the remainder of the protocol. Along the way, we also (i) provide the first proof (under the same assumptions) that a slight variant of Protocol SPAKE2 from [Abdalla, Pointcheval 2005] is a secure *symmetric* PAKE in the UC framework (previous security proofs were all in the weaker BPR framework [Bellare, Pointcheval, Rogaway 2000]); (ii) provide a proof (under very similar assumptions) that a variant of Protocol SPAKE2+ that is currently being standardized is also a secure asymmetric PAKE; (iii) repair several problems in earlier UC formulations of secure symmetric and asymmetric PAKE.

2018

CRYPTO

Faster Homomorphic Linear Transformations in HElib
📺
Abstract

HElib is a software library that implements homomorphic encryption (HE), with a focus on effective use of “packed” ciphertexts. An important operation is applying a known linear map to a vector of encrypted data. In this paper, we describe several algorithmic improvements that significantly speed up this operation: in our experiments, our new algorithms are 30–75 times faster than those previously implemented in HElib for typical parameters.One application that can benefit from faster linear transformations is bootstrapping (in particular, “thin bootstrapping” as described in [Chen and Han, Eurocrypt 2018]). In some settings, our new algorithms for linear transformations result in a $$6{\times }$$6× speedup for the entire thin bootstrapping operation.Our techniques also reduce the size of the large public evaluation key, often using 33%–50% less space than the previous HElib implementation. We also implemented a new tradeoff that enables a drastic reduction in size, resulting in a $$25{\times }$$25× factor or more for some parameters, paying only a penalty of a 2–$$4{\times }$$4× times slowdown in running time (and giving up some parallelization opportunities).

2010

EPRINT

Simple and Efficient Public-Key Encryption from Computational Diffie-Hellman in the Standard Model
Abstract

This paper proposes practical chosen-ciphertext secure public-key encryption systems that are provably secure under the computational Diffie-Hellman assumption, in the standard model. Our schemes are conceptually simpler and more efficient than previous constructions.
We also show that in bilinear groups the size of the public-key can be shrunk from n to 2\sqrt{n} group elements, where n is the security parameter.

2010

PKC

2010

EPRINT

Credential Authenticated Identification and Key Exchange
Abstract

Secure two-party authentication and key exchange are fundamental problems.
Traditionally, the parties authenticate each other by means of
their identities, using a public-key infrastucture (PKI).
However, this is not always feasible or desirable:
an appropriate PKI may not be available,
or the parties may want to remain anonymous, and not reveal
their identities.
To address these needs,
we introduce the notions of credential-authenticated identification (CAID) and
key exchange (CAKE), where the compatibility of the parties'
\emph{credentials}
is the criteria for authentication, rather than the parties' \emph{identities}
relative to some PKI.
We formalize CAID and CAKE in the universal composability (UC) framework,
with natural ideal functionalities,
and we give practical,
modularly designed protocol realizations.
We prove all our protocols UC-secure in the adaptive corruption model
with erasures, assuming a common reference string (CRS).
The proofs are based on standard cryptographic assumptions and do not rely on random oracles.
CAKE includes password-authenticated key exchange (PAKE) as a special case,
and we present two new PAKE protocols.
The first one is interesting in that it is uses completly different
techniques than known practical PAKE protocols, and also achieves
UC-security in the adaptive corruption model with erasures;
the second one
is the
first practical PAKE protocol
that provides a meaningful form of resilience against
server compromise
without relying on random oracles.

2009

EUROCRYPT

2008

EPRINT

The Twin Diffie-Hellman Problem and Applications
Abstract

We propose a new computational problem called the twin Diffie-Hellman problem. This problem is closely related to the usual (computational) Diffie-Hellman problem and can be used in many of the same cryptographic constructions that are based on the Diffie-Hellman problem. Moreover, the twin Diffie-Hellman problem is at least as hard as the ordinary Diffie-Hellman problem. However, we are able to show that the twin Diffie-Hellman problem remains hard, even in the presence of a decision oracle that recognizes solutions to the problem this is a feature not enjoyed by the ordinary Diffie-Hellman problem. In particular, we show how to build a certain trapdoor test that allows us to effectively answer such decision oracle queries without knowing any of the corresponding discrete logarithms. Our new techniques have many applications. As one such application, we present a new variant of ElGamal encryption with very short ciphertexts, and with a very simple and tight security proof, in the random oracle model, under the assumption that the ordinary Diffie-Hellman problem is hard. We present several other applications as well, including: a new variant of Diffie and Hellmans non-interactive key exchange protocol; a new variant of Cramer-Shoup encryption, with a very simple proof in the standard model; a new variant of Boneh-Franklin identity-based encryption, with very short ciphertexts; a more robust version of a password-authenticated key exchange protocol of Abdalla and Pointcheval.

2008

EPRINT

A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks
Abstract

Recently, at Crypto 2008, Boneh, Halevi, Hamburg, and Ostrovsky (BHHO)
solved the long-standing open problem of ``circular encryption,''
by
presenting a public key encryption scheme
and proving that it
is semantically secure against key dependent chosen plaintext attack (KDM-CPA security)
under standard assumptions (and without resorting to random oracles).
However, they left as an open problem that of designing
an encryption scheme that \emph{simultaneously} provides security
against both key dependent chosen plaintext \emph{and} adaptive chosen ciphertext
attack (KDM-CCA2 security).
In this paper, we solve this problem.
First, we show that by applying the Naor-Yung ``double encryption''
paradigm, one can combine
any KDM-CPA secure scheme with any (ordinary) CCA2 secure scheme,
along with an appropriate non-interactive zero-knowledge proof,
to obtain a KDM-CCA2 secure scheme.
Second, we give a concrete instantiation that makes use
the above KDM-CPA secure scheme of BHHO,
along with a generalization of the Cramer-Shoup CCA2 secure
encryption scheme,
and recently developed
pairing-based NIZK proof systems.
This instantiation increases the complexity of the BHHO
scheme by just a small constant factor.

2006

EPRINT

Stateful Public-Key Cryptosystems: How to Encrypt with One 160-bit Exponentiation
Abstract

We show how to significantly speed-up the encryption portion
of some public-key cryptosystems by the simple expedient of allowing a
sender to maintain state that is re-used across different encryptions.
In particular we present stateful versions of the DHIES and
Kurosawa-Desmedt schemes that each use only one exponentiation to
encrypt, as opposed to two and three respectively in the original
schemes, yielding the fastest discrete-log based public-key encryption
schemes known in the random-oracle and standard models respectively.
The schemes are proven to meet an appropriate extension of the
standard definition of IND-CCA security that takes into account novel
types of attacks possible in the stateful setting.

2005

EUROCRYPT

2005

JOFC

2004

EPRINT

Sequences of games: a tool for taming complexity in security proofs
Abstract

This paper is a brief tutorial on a technique for structuring security proofs as sequences of games.

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.

2002

EUROCRYPT

2002

EPRINT

Efficient Computation Modulo a Shared Secret with Application to the Generation of Shared Safe-Prime Products
Abstract

We present a new protocol for efficient distributed computation modulo a
shared secret. We further present a protocol to distributively generate a
random shared prime or safe prime that is much more efficient than
previously known methods. This allows to distributively compute shared RSA
keys, where the modulus is the product of two safe primes, much more
efficiently than was previously known.

2002

EPRINT

Practical Verifiable Encryption and Decryption of Discrete Logarithms
Abstract

This paper presents a variant of the new public key encryption of Cramer and Shoup based on Paillier's decision composite residuosity assumption, along with an efficient protocol for verifiable encryption of discrete logarithms. This is the first verifiable encryption system that provides chosen ciphertext security and avoids inefficient cut-and-choose proofs. This has numerous applications, including fair exchange and key escrow. We also present efficient protocols for verifiable decryption, which has applications to, e.g., confirmer signatures. The latter protocols build on a new protocol for proving whether or not two discrete logarithms are equal that is of independent interest. Prior such protocols were either inefficient or not zero-knowledge.

2001

EPRINT

Optimistic Asynchronous Atomic Broadcast
Abstract

This paper presents a new protocol
for atomic broadcast in an asynchronous network with
a maximal number of Byzantine failures.
It guarantees both safety and liveness without
making any timing assumptions or using any type of failure detector.
Under normal circumstances, the protocol runs in an optimistic mode,
with extremely low message and computational complexity -- essentially,
just performing a Bracha broadcast for each request.
In particular, no
potentially expensive public-key cryptographic operations are used.
In rare circumstances, the protocol may briefly
switch to a pessimistic mode,
where both the message and computational complexity
are significantly higher than in the optimistic mode,
but are
still reasonable.

2001

EPRINT

Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack
Abstract

A new public key encryption scheme, along with several variants,
is proposed and analyzed.
The scheme and its variants are quite practical, and are proved
secure
against adaptive chosen ciphertext attack under standard
intractability assumptions.
These appear to be the first public-key encryption schemes
in the literature that are simultaneously practical and provably secure.

2001

EPRINT

Secure and Efficient Asynchronous Broadcast Protocols
Abstract

Reliable broadcast protocols are a fundamental building block for
implementing replication in fault-tolerant distributed systems. This paper
addresses secure service replication in an asynchronous environment with a
static set of servers, where a malicious adversary may corrupt up to a
threshold of servers and controls the network. We develop a formal model
using concepts from modern cryptography, present modular definitions for
several broadcast problems, including reliable, atomic, and secure causal
broadcast, and present protocols implementing them. Reliable broadcast is a
basic primitive, also known as the Byzantine generals problem, providing
agreement on a delivered message. Atomic broadcast imposes additionally a
total order on all delivered messages. We present a randomized atomic
broadcast protocol based on a new, efficient multi-valued asynchronous
Byzantine agreement primitive with an external validity condition.
Apparently, no such efficient asynchronous atomic broadcast protocol
maintaining liveness and safety in the Byzantine model has appeared
previously in the literature. Secure causal broadcast extends atomic
broadcast by encryption to guarantee a causal order among the delivered
messages. Threshold-cryptographic protocols for signatures, encryption, and
coin-tossing also play an important role.

2001

EPRINT

A Proposal for an ISO Standard for Public Key Encryption
Abstract

This document is an initial proposal for a draft for a forthcoming
ISO standard on public-key encryption.
It is hoped that this proposal will serve as a basis for discussion,
from which a consensus for a standard may be formed.

2001

EPRINT

Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption
Abstract

We present several new and fairly practical public-key
encryption schemes and prove them secure against adaptive
chosen ciphertext attack. One scheme is based on
Paillier's Decision Composite Residuosity (DCR)
assumption, while another is based in the classical
Quadratic Residuosity (QR) assumption. The analysis is in
the standard cryptographic model, i.e., the security of
our schemes does not rely on the Random Oracle model.
We also introduce the notion of a universal hash
proof system. Essentially, this is a special kind of
non-interactive zero-knowledge proof system for an NP
language. We do not show that universal hash
proof systems exist for all NP languages, but we do
show how to construct very efficient universal hash
proof systems for a general class of group-theoretic
language membership problems.
Given an efficient universal hash proof system for a
language with certain natural cryptographic
indistinguishability properties, we show
how to construct an efficient public-key encryption
schemes secure against adaptive chosen ciphertext attack
in the standard model. Our construction only uses the
universal hash proof systemas a primitive: no other
primitives are required, although even more efficient
encryption schemes can be obtained by using hash
functions with appropriate collision-resistance
properties.
We show how to construct efficient universal hash proof
systems for languages related to the DCR and QR
assumptions. From these we get corresponding public-key
encryption schemes that are secure under these assumptions.
We also show that the Cramer-Shoup encryption scheme
(which up until now was the only practical
encryption scheme that could be proved secure against
adaptive chosen ciphertext attack under a reasonable
assumption, namely, the Decision Diffie-Hellman assumption)
is also a special case of our general theory.

2000

EPRINT

ACE: The Advanced Cryptographic Engine
Abstract

This document describes
the Advanced Cryptographic Engine (ACE).
It specifies a public key encryption
scheme as well as a
digital signature scheme
with enough detail to ensure interoperability between different
implementations.
These schemes are almost as efficient as commercially used schemes,
yet unlike such schemes, can be proven secure under reasonable
and well-defined
intractability assumptions.
A concrete security analysis of both schemes is presented.

2000

EPRINT

Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement using Cryptography
Abstract

Byzantine agreement requires a set of parties in a distributed system to
agree on a value even if some parties are corrupted. A new protocol for
Byzantine agreement in a completely asynchronous network is presented that
makes use of cryptography, specifically of threshold signatures and
coin-tossing protocols. These cryptographic protocols have practical and
provably secure implementations in the ``random oracle'' model. In
particular, a coin-tossing protocol based on the Diffie-Hellman problem is
presented and analyzed.
The resulting asynchronous Byzantine agreement protocol is both practical
and theoretically nearly optimal because it tolerates the maximum number of
corrupted parties, runs in constant expected time, has message
and communication complexity close to the optimum, and uses a trusted dealer
only in a setup phase, after which it can process a virtually unlimited
number of transactions.
The protocol is formulated as a transaction processing service in a
cryptographic security model, which differs from the standard
information-theoretic formalization and may be of independent interest.

2000

EPRINT

OAEP Reconsidered
Abstract

The OAEP encryption scheme was introduced by Bellare and Rogaway
at Eurocrypt '94.
It converts any trapdoor permutation scheme into a public-key
encryption scheme.
OAEP is widely believed to provide
resistance against adaptive chosen ciphertext attack.
The main justification for this belief is a supposed proof of security
in the random oracle model, assuming the underlying
trapdoor permutation scheme is one way.
This paper shows conclusively that this justification is invalid.
First, it observes that there appears to be a non-trivial gap in the
OAEP security proof.
Second,
it proves that this gap cannot be filled,
in the sense that
there can be no standard "black box" security reduction
for OAEP.
This is done by proving that there exists an oracle
relative to which the general OAEP scheme is insecure.
The paper also presents a new scheme OAEP+, along with
a complete proof of security in the random oracle model.
OAEP+ is essentially just as efficient as OAEP,
and even has a tighter security reduction.
It should be stressed that these results do not
imply that a particular instantiation of OAEP, such as RSA-OAEP, is insecure.
They simply undermine the original justification for its security.
In fact, it turns out -- essentially by accident,
rather than by design -- that RSA-OAEP is secure in the random oracle
model; however, this fact relies on special algebraic properties
of the RSA function, and not on the security
of the general OAEP scheme.

1999

EPRINT

Signature Schemes Based on the Strong RSA Assumption
Abstract

We describe and analyze a new digital signature scheme.
The new scheme is quite efficient, does not require the the signer
to maintain any state, and can be proven secure against adaptive
chosen message attack under a reasonable intractability assumption,
the so-called Strong RSA Assumption.
Moreover, a hash function can be incorporated into the scheme
in such a way that it is also secure in the random oracle model
under the standard RSA Assumption.

1999

EPRINT

Practical Threshold Signatures
Abstract

We present an RSA threshold signature scheme. The scheme enjoys the following
properties:
it is unforgeable and robust;
in the random oracle model, assuming the RSA problem is hard;
signature share generation and verification is completely non-interactive;
the size of an individual signature share is bounded by a constant
times the size of the RSA modulus.

1999

EPRINT

A Composition Theorem for Universal One-Way Hash Functions
Abstract

In this paper we present a new scheme for constructing
universal one-way hash functions that hash arbitrarily long messages
out of universal one-way hash functions that hash fixed-length messages.
The new construction is extremely simple and is also very efficient,
yielding shorter keys than previously proposed composition
constructions.

1999

EPRINT

On Formal Models for Secure Key Exchange
Abstract

A new formal security model for session key exchange protocols is
proposed, and several efficient protocols are analyzed in this model.
Our new model is in the style of multi-party simulatability: it
specifies the service and security guarantees that a key exchange
protocol should provide to higher-level protocols as a simple,
natural, and intuitive interface to which a high-level protocol
designer can program. The relationship between this new model and
previously proposed models is explored, and in particular, several
flaws and shortcomings in previously proposed models are discussed.
The model also deals with anonymous users---that is, users who do not
have public keys, but perhaps have passwords that can be used to
authenticate themselves within a secure session.

1998

CRYPTO

1998

EPRINT

A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack
Abstract

A new public key cryptosystem is presented that is provably secure
against adaptive chosen ciphertext attack.
The scheme is quite practical, and the proof of security relies
only on standard intractability assumptions.

1997

EPRINT

Optimistic fair Exchange of Digital Signatures
Abstract

We present a new protocol that allows two players to exchange digital
signatures (including RSA and DSS) over the Internet in a fair way, so
that either each player gets the other's signature, or neither player
does. One obvious application is where the signatures represent items
of value, for example, an electronic check or airline ticket; the
protocol can also be adapted to exchange encrypted data. The protocol
relies on a trusted third party, but is "optimistic," in that the
third party is only needed in cases where one player attempts to cheat
or simply crashes. This is an important property, as it greatly
reduces the load on the third party, which in particular facilitates
a more robust and secure implementation of the third party.

1996

EPRINT

Private Information Storage
Abstract

We consider the setting of hiding information through the use of
multiple databases that do not interact with one another. Previously,
in this setting solutions for retrieval of data in the efficient
manner were given, where a user achieves this by interacting with all
the databases. We consider the case of both writing and
reading. While the case of reading was well studied before, the case
of writing was previously completely open. In this paper, we show how
to implement both read and write operations. As in the previous
papers, we measure, as a function of k and n the amount of
communication required between a user and all the databases for a
single read/write operation, and achieve efficient read/write schemes.
Moreover, we show a general reduction from reading database scheme to
reading and writing database scheme, with the following guarantees:
for any k, given a retrieval only k-database scheme with communication
complexity R(k,n) we show a (k+1) reading and writing database scheme
with total communication complexity O(R(k,n) * (log n)^{O(1)}). It
should be stressed that prior to the current paper no trivial
(i.e. sub-linear) bounds for private information storage were known.

#### Program Committees

- TCC 2010
- PKC 2008
- TCC 2007
- Crypto 2005 (Program chair)
- Crypto 2003
- Crypto 2000
- Eurocrypt 1999
- CHES 1999

#### Coauthors

- Masayuki Abe (1)
- Joy Algesheimer (2)
- N. Asokan (2)
- Donald Beaver (1)
- Mihir Bellare (1)
- Christian Cachin (4)
- Jan Camenisch (9)
- Nathalie Casati (2)
- David Cash (3)
- Nishanth Chandran (2)
- Ronald Cramer (6)
- Yvo Desmedt (1)
- Yevgeniy Dodis (2)
- Joan Feigenbaum (1)
- Rosario Gennaro (5)
- Thomas Groß (2)
- Shai Halevi (4)
- Kristiyan Haralambiev (2)
- Dennis Hofheinz (1)
- Tibor Jager (2)
- Aggelos Kiayias (1)
- Eike Kiltz (5)
- Tadayoshi Kohno (1)
- Stephan Krenn (1)
- Kaoru Kurosawa (2)
- Klaus Kursawe (5)
- Antonio Nicolosi (1)
- Rafail Ostrovsky (1)
- Frank Petzold (2)
- Aviel D. Rubin (1)
- Thomas Schweinberger (1)
- Michael Waidner (2)
- Shabsi Walfish (1)