## CryptoDB

### Leonid Reyzin

#### Affiliation: Boston University

#### Publications

**Year**

**Venue**

**Title**

2018

PKC

A Unified Framework for Trapdoor-Permutation-Based Sequential Aggregate Signatures
Abstract

We give a framework for trapdoor-permutation-based sequential aggregate signatures (SAS) that unifies and simplifies prior work and leads to new results. The framework is based on ideal ciphers over large domains, which have recently been shown to be realizable in the random oracle model. The basic idea is to replace the random oracle in the full-domain-hash signature scheme with an ideal cipher. Each signer in sequence applies the ideal cipher, keyed by the message, to the output of the previous signer, and then inverts the trapdoor permutation on the result. We obtain different variants of the scheme by varying additional keying material in the ideal cipher and making different assumptions on the trapdoor permutation. In particular, we obtain the first scheme with lazy verification and signature size independent of the number of signers that does not rely on bilinear pairings.Since existing proofs that ideal ciphers over large domains can be realized in the random oracle model are lossy, our schemes do not currently permit practical instantiation parameters at a reasonable security level, and thus we view our contribution as mainly conceptual. However, we are optimistic tighter proofs will be found, at least in our specific application.

2012

ASIACRYPT

2010

EPRINT

Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets
Abstract

Consider two parties holding samples from correlated distributions W and W', respectively, that are within distance t of each other in some metric space. These parties wish to agree on a uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK that they can use to generate a sequence of session keys {R_j} using multiple pairs {W_j, W'_j}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors.
Our results improve upon previous work in several respects:
-- The best previous solution for the keyless case with no errors (i.e., t=0) requires the min-entropy of W to exceed 2n/3, where n is the bit-length of W. Our solution applies whenever min-entropy of W exceeds the minimal possible} threshold n/2, and yields a longer key.
-- Previous solutions for the keyless case in the presence of errors (i.e., t>0) required random oracles. We give the first constructions (for certain metrics) in the standard model.
-- Previous solutions for the keyed case were stateful. We give the first stateless solution.

2008

EPRINT

An Improved Robust Fuzzy Extractor
Abstract

We consider the problem of building robust fuzzy extractors, which allow two parties holding similar random variables W, W' to agree on a secret key R in the presence of an active adversary. Robust fuzzy extractors were defined by Dodis et al. in Crypto 2006 to be noninteractive, i.e., only one message P, which can be modified by an unbounded adversary, can pass from one party to the other. This allows them to be used by a single party at different points in time (e.g., for key recovery or biometric authentication), but also presents an additional challenge: what if R is used, and thus possibly observed by the adversary, before the adversary has a chance to modify P. Fuzzy extractors secure against such a strong attack are called post-application robust.
We construct a fuzzy extractor with post-application robustness that extracts a shared secret key of up to (2m-n)/2 bits (depending on error-tolerance and security parameters), where n is the bit-length and m is the entropy of W. The previously best known result, also of Dodis et al., extracted up to (2m-n)/3 bits (depending on the same parameters).

2007

EUROCRYPT

2007

EPRINT

Saving Private Randomness in One-Way Functions and Pseudorandom Generators
Abstract

Can a one-way function f on n input bits be used
with fewer than $n$ bits while retaining comparable hardness of
inversion? We show that the answer to this fundamental question is
negative, if one is limited black-box reductions.
Instead, we ask whether one can save on secret random bits
at the expense of more public random bits.
Using a shorter secret input is highly desirable, not only
because it saves resources, but also because it can yield
tighter reductions from higher-level primitives to one-way functions.
Our first main result
shows that if the number of output elements of f is at most
$2^k$, then a simple construction using pairwise-independent hash
functions results in a new one-way function that uses
only k secret bits. We also demonstrate that it is not the knowledge of security of f, but rather of its structure, that enables the savings: a black-box reduction cannot, for a general f, reduce the secret-input length, even given the knowledge that security of f is only $2^{-k}$; nor can a black-box reduction use fewer than k secret input bits when f has $2^k$ distinct outputs.
Our second main result is an application of the public-randomness approach: we show
a construction of a pseudorandom generator based on any
regular one-way function with output range of known size $2^k$. The construction requires a seed of only 2n+O(k\log k) bits
(as opposed to O(n \log n) in previous constructions); the savings
come from the reusability of public randomness.
The secret part of the seed is of length only k
(as opposed to n in previous constructions), less than the length of
the one-way function input.

2004

EPRINT

Upper and Lower Bounds on Black-Box Steganography
Abstract

We study the limitations of steganography when the sender is not using any properties of the underlying channel beyond its entropy and the ability to sample from it. On the negative side, we show that the number of samples the sender must obtain from the channel is exponential in the rate of the stegosystem. On the positive side, we present the first secret-key stegosystem that essentially matches this lower bound regardless of the entropy of the underlying channel. Furthermore, for high-entropy channels, we present the first secret-key stegosystem that matches this lower bound statelessly (i.e., without requiring synchronized state between sender and receiver).

2003

EPRINT

Sequential Aggregate Signatures from Trapdoor Permutations
Abstract

An aggregate signature scheme (recently proposed by Boneh, Gentry,
Lynn and Shacham) is a method for combining $n$ signatures from $n$
different signers on $n$ different messages into one signature of unit
length. We propose \emph{sequential aggregate signatures}, in which
the set of signers is ordered. The aggregate signature is computed by
having each signer, in turn, add his signature to it. We show how to
realize this in such a way that the size of the aggregate signature is
independent of $n$. This makes sequential aggregate signatures a
natural primitive for certificate chains, whose length can be reduced
by aggregating all signatures in a chain. We give a construction
based on families of certified trapdoor permutations, and show how to
instantiate our scheme based on RSA.

2003

EPRINT

Simple Stateless Steganography
Abstract

We put forward the first secret-key steganographic construction that is
both black-box (i.e., the sender need not have knowledge of the
channel beyond the ability to sample from it) and stateless (i.e.,
the sender and the recipient need not maintain synchronized state when
sending multiple bits). Both of these properties are important: the first
because in many settings it is unrealistic to assume detailed knowledge of
the underlying channel distribution, and the second because maintaining
synchronized state between the sender and the recipient is particularly
problematic in steganography, where communication to resynchronize will
alert the adversary.
For channels of sufficient entropy, our construction is more efficient than
previous black-box constructions. Moreover, it is the first one to
provide a
tradeoff between the number of samples the encoder needs and the rate at
which hiddentext is transmitted.

2003

EPRINT

Physically Observable Cryptography
Abstract

Complexity-theoretic cryptography considers only abstract notions of computation, and hence cannot protect against attacks that exploit the information leakage (via electromagnetic fields, power consumption, etc.) inherent in the physical execution of any cryptographic algorithm. Such "physical observation attacks" bypass the impressive barrier of mathematical security erected so far, and successfully break mathematically impregnable systems. The great practicality and the inherent availability of physical attacks threaten the very relevance of complexity-theoretic security.
To respond to the present crisis, we put forward physically observable cryptography: a powerful, comprehensive, and precise model for defining and delivering cryptographic security against an adversary that has access to information leaked from the physical execution of cryptographic algorithms.
Our general model allows for a variety of adversaries. In this paper, however, we focus on the strongest possible adversary, so as to capture what is cryptographically possible in the worst possible, physically observable setting. In particular, we
-- consider an adversary that has full (and indeed adaptive) access to any leaked information;
-- show that some of the basic theorems and intuitions of traditional cryptography no longer hold in a physically observable setting; and
-- construct pseudorandom generators that are provably secure against all physical-observation attacks.
Our model makes it easy to meaningfully restrict the power of our general physically observing adversary. Such restrictions may enable schemes that are more efficient or rely on weaker assumptions, while retaining security against meaningful physical observations attacks.

2003

EPRINT

Breaking and Repairing Optimistic Fair Exchange from PODC 2003
Abstract

In PODC 2003, Park, Chong, Siegel and Ray [PCSR03] proposed an optimistic protocol for fair exchange, based on RSA signatures. We show that their protocol is *totally breakable* already in the registration phase: the honest-but-curious arbitrator can easily determine the signer's secret key.
On a positive note, the authors of [PCSR03] informally introduced a connection between fair exchange and "sequential two-party multisignature schemes" (which we call two-signatures), but used an insecure two-signature scheme in their actual construction. Nonetheless, we show that this connection *can* be properly formalized to imply *provably secure* fair exchange protocols. By utilizing the state-of-the-art non-interactive two-signature of Boldyreva (PKC 2003), we obtain an efficient and provably secure (in the random oracle model) fair exchange protocol, which is based on GDH signatures of Boneh, Lynn and Shacham (Asiacrypt 2001).
Of independent interest, we introduce a unified model for non-interactive fair exchange protocols, which results in a new primitive we call *verifiably committed signatures*. Verifiably committed signatures generalize (non-interactive) verifiably encrypted signatures and two-signatures, both of which are sufficient for fair exchange.

2003

EPRINT

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
Abstract

We provide formal definitions and efficient secure techniques for
-- turning noisy information into keys usable for any cryptographic application, and, in particular,
-- reliably and securely authenticating biometric data.
Our techniques apply not just to biometric information, but to any keying material that, unlike traditional cryptographic keys, is (1) not reproducible precisely and (2) not distributed uniformly. We propose two primitives: a fuzzy extractor reliably extracts nearly uniform randomness R from its input; the extraction is error-tolerant in the sense that R will be the same even if the input changes, as long as it remains reasonably close to the original. Thus, R can be used as a key in a cryptographic application. A secure sketch produces public information about its input w that does not reveal w, and yet allows exact recovery of w given another value that is close to w. Thus, it can be used to reliably reproduce error-prone biometric inputs without incurring the security risk inherent in storing them.
We define the primitives to be both formally secure and versatile, generalizing much prior work. In addition, we provide nearly optimal constructions of both primitives for various measures of "closeness" of input data, such as Hamming distance, edit distance, and set difference.

2002

EPRINT

Better than BiBa: Short One-time Signatures with Fast Signing and Verifying
Abstract

One-time signature schemes have found numerous applications: in ordinary, on-line/off-line, and forward-secure signatures. More recently, they have been used in multicast and broadcast authentication. We propose a one-time signature scheme with very efficient signing and verifying, and short signatures. Our scheme is well-suited for broadcast authentication, and, in fact, can be viewed as an improvement of the BiBa one-time signature (proposed by Perrig in CCS 2001 for broadcast authentication).

2002

EPRINT

SiBIR: Signer-Base Intrusion-Resilient Signatures
Abstract

We propose a new notion of intrusion-resilient signature schemes, which generalizes and improves upon both forward-secure [And97,BM99] and key-insulated [DKXY02] signature schemes.
Specifically, as in the prior notions, time is divided into predefined time periods (e.g., days); each signature includes the number of the time time period in which it was generated; while the public key remains the same, the secret keys evolve with time. Also, as in key-insulated schemes, the user has two modules, signer and home base: the signer generates signatures on his own, and the base is needed only to help update the signer's key from one period to the next.
The main strength of intrusion-resilient schemes, as opposed to prior notions, is that they remain secure even after arbitrarily many compromises of both modules, as long as the compromises are not simultaneous. Moreover, even if the intruder does compromise both modules simultaneously, she will still be unable to generate any signatures for the previous time periods.
We provide an efficient intrusion-resilient signature scheme, provably secure in the random oracle model based on the strong RSA assumption.
We also discuss how such schemes can eliminate the need for certificate revocation in the case of on-line authentication.

2002

EPRINT

On the Power of Claw-Free Permutations
Abstract

Probabilistic Signature Scheme (PSS), Full Domain Hash (FDH) and
several of their variants are widely used signature schemes, which can
be formally analyzed in the random oracle model. These schemes output
a signature of the form (f^{-1}(y),pub), where y somehow depends
on the message signed (and pub) and f is some public trapdoor
permutation (typically RSA). Interestingly, all these signature
schemes can be proven {\em asymptotically} secure for an {\em
arbitrary} trapdoor permutation f, but their {\em exact} security
seems to be significantly better for {\em special} trapdoor
permutations like RSA. This leads to two natural questions:
(1) can the asymptotic security analysis be improved with general
trapdoor permutations?; and, if not, (2) what {\em general
cryptographic assumption} on f --- enjoyed by specific functions
like RSA --- is ``responsible'' for the improved security?
We answer both these questions. First, we show that if f is a
``black-box'' trapdoor permutation, then the poor exact security is
unavoidable. More specifically, the ``security loss'' for general
trapdoor permutations is \Omega(q_hash), where q_hash is the
number of random oracle queries made by the adversary (which could be
quite large). On the other hand, we show that all the security
benefits of the RSA-based variants come into effect once f comes
from a family of {\em claw-free permutation} pairs. Our results
significantly narrow the current ``gap'' between general trapdoor
permutations and RSA to the ``gap'' between trapdoor permutations and
claw-free permutations. Additionally, they can be viewed as the first
{\em security/efficiency} separation between these basic cryptographic
primitives. In other words, while it was already believed that certain
cryptographic objects {\em can} be build from claw-free permutations
but {\em not} from general trapdoor permutations, we show that certain
important schemes (like FDH and PSS) provably work with {\em either},
but enjoy a much better tradeoff between security and efficiency when
deployed with claw-free permutations.

2002

EPRINT

Forward-Secure Signatures with Fast Key Update
Abstract

In regular digital signatures, once the secret key is compromised, all signatures, even those that were issued by the honest signer before the compromise, will not be trustworthy any more. Forward-secure signatures have been proposed to address this major shortcoming.
We present a new forward-secure signature scheme, called KREUS, with several advantages. It has the most efficient Key Update of all known schemes, requiring just a single modular squaring. Our scheme thus enables more frequent Key Update and hence allows shorter time periods, enhancing security: fewer signatures might become invalid as a result of key compromise. In addition, the on-line component of signing is also very efficient, consisting of a single multiplication. We precisely analyze the total signer costs and show that they are lower when the number of signatures per time period is small; the advantage of our scheme increases considerably as the number of time periods grows.
Our scheme's security relies on the Strong-RSA assumption and the random-oracle-based Fiat-Shamir transform.

2002

EPRINT

An Improved Pseudorandom Generator Based on Hardness of Factoring
Abstract

We present a simple to implement and efficient pseudorandom generator based on the factoring assumption. It outputs more than pn/2 pseudorandom bits per p exponentiations, each with the same base and an exponent shorter than n/2 bits. Our generator is based on results by Hastad, Schrift and Shamir [HSS93], but unlike their generator and its improvement by Goldreich and Rosen [GR00], it does not use hashing or extractors, and is thus simpler and somewhat more efficient.
In addition, we present a general technique that can be used to speed up pseudorandom generators based on iterating one-way permutations. We construct our generator by applying this technique to results of [HSS93]. We also show how the generator given by Gennaro [Gen00] can be simply derived from results of Patel and Sundaram [PS98] using our technique.

2001

EPRINT

Forward-Secure Signatures with Optimal Signing and Verifying
Abstract

Ordinary digital signatures have an inherent weakness: if the secret key is leaked, then all signatures, even the ones generated before the leak, are no longer trustworthy. Forward-secure digital signatures were recently proposed to address this weakness: they ensure that past signatures remain secure even if the current secret key is leaked.
We propose the first forward-secure signature scheme for which both signing and verifying are as efficient as for one of the most efficient ordinary signature schemes (Guillou-Quisquater): each requiring just two modular exponentiations with a short exponent. All previously proposed forward-secure signature schemes took significantly longer to sign and verify than ordinary signature schemes.
Our scheme requires only fractional increases to the sizes of keys and signatures, and no additional public storage. Like the underlying Guillou-Quisquater scheme, our scheme is provably secure in the random oracle model.

2000

EPRINT

A New Forward-Secure Digital Signature Scheme
Abstract

We improve the Bellare-Miner (Crypto '99) construction of signature
schemes with forward security in the random oracle model. Our scheme
has significantly shorter keys and is, therefore, more practical. By
using a direct proof technique not used for forward-secure schemes
before, we are able to provide better security bounds for the original
construction as well as for our scheme.
Bellare and Miner also presented a method for constructing such schemes
without the use of the random oracle. We conclude by proposing an
improvement to their method and an additional, new method for accomplishing
this.

1999

EPRINT

Improving the Exact Security of Digital Signature Schemes
Abstract

We provide two contributions to exact security analysis of
digital signatures:
We put forward a new method of constructing Fiat-Shamir-like
signature schemes that yields better "exact security" than the original
Fiat-Shamir method; and
we extend exact security analysis to "exact cost-security analysis" by
showing that digital signature schemes with "loose security" may be
preferable for reasonable measures of cost.

#### Program Committees

- Eurocrypt 2019
- TCC 2017
- Eurocrypt 2017
- TCC 2016
- Crypto 2014
- Eurocrypt 2013
- CHES 2012
- Crypto 2011
- Crypto 2010
- TCC 2008
- PKC 2006
- TCC 2005
- Crypto 2005

#### Coauthors

- Michel Abdalla (2)
- Hamza Abusalah (1)
- Divesh Aggarwal (1)
- Joël Alwen (2)
- Kyle Brogle (1)
- Ran Canetti (5)
- Melissa Chase (1)
- Binyi Chen (1)
- Yilei Chen (3)
- Bram Cohen (1)
- Nenad Dedic (6)
- Yevgeniy Dodis (8)
- Pierre-Alain Dupont (1)
- Sebastian Faust (1)
- Benjamin Fuller (6)
- Craig Gentry (1)
- Sharon Goldberg (2)
- Danny Harnik (2)
- Alexander Healy (1)
- Julia Hesse (1)
- Chun-Yuan Hsiao (2)
- Gene Itkis (7)
- Zahra Jafargholi (1)
- Bhavana Kanukurthi (2)
- Jonathan Katz (2)
- Danylo Khilko (1)
- Anton Kozlov (1)
- Moses Liskov (1)
- Chi-Jen Lu (1)
- Anna Lysyanskaya (4)
- Tal Malkin (1)
- Xianrui Meng (1)
- Silvio Micali (9)
- Eric Miles (1)
- Moni Naor (1)
- Adam O'Neill (2)
- Rafail Ostrovsky (1)
- Adam O’Neill (1)
- Omer Paneth (2)
- Dimitrios Papadopoulos (1)
- Krzysztof Pietrzak (2)
- David Pointcheval (1)
- Tal Rabin (1)
- Zulfikar Ramzan (1)
- Natan Reyzin (1)
- Ronald L. Rivest (1)
- Ron D. Rothblum (1)
- Scott Russell (4)
- Hovav Shacham (2)
- Emily Shen (1)
- Adam Smith (7)
- Stefano Tessaro (1)
- Eran Tromer (1)
- Salil P. Vadhan (1)
- Vinod Vaikuntanathan (1)
- Sachin Vasant (1)
- Sophia Yakoubov (2)
- Asaf Ziv (1)