## CryptoDB

### Shai Halevi

#### Affiliation: IBM Research

#### Publications

**Year**

**Venue**

**Title**

2020

TCC

Can a Blockchain Keep a Secret?
📺
Abstract

Blockchains are gaining traction and acceptance, not just for cryptocurrencies, but increasingly as an architecture for distributed computing.
In this work we seek solutions that allow a \emph{public} blockchain to act as a trusted long-term repository of secret information:
Our goal is to deposit a secret with the blockchain, specify how it is to be used (e.g., the conditions under which it is released), and have the blockchain keep the secret and use it only in the specified manner (e.g., release only it once the conditions are met).
This simple functionality enables many powerful applications, including signing statements on behalf of the blockchain, using it as the control plane for a storage system, performing decentralized program-obfuscation-as-a-service, and many more.
Using proactive secret sharing techniques, we present a scalable solution for implementing this functionality on a public blockchain, in the presence of a mobile adversary controlling a small minority of the participants.
The main challenge is that, on the one hand, scalability requires that we use small committees to represent the entire system, but, on the other hand, a mobile adversary may be able to corrupt the entire committee if it is small.
For this reason, existing proactive secret sharing solutions are either non-scalable or insecure in our setting.
We approach this challenge via "player replaceability", which ensures the committee is anonymous until after it performs its actions.
Our main technical contribution is a system that allows sharing and re-sharing of secrets among the members of small dynamic committees, without knowing who they are until after they perform their actions and erase their secrets. Our solution handles a fully mobile adversary corrupting roughly 1/4 of the participants at any time, and is scalable in terms of both the number of parties and the number of time intervals.

2019

TCC

On Fully Secure MPC with Solitary Output
Abstract

We study the possibility of achieving full security, with guaranteed output delivery, for secure multiparty computation of functionalities where only one party receives output, to which we refer as solitary functionalities. In the standard setting where all parties receive an output, full security typically requires an honest majority; otherwise even just achieving fairness is impossible. However, for solitary functionalities, fairness is clearly not an issue. This raises the following question: Is full security with no honest majority possible for all solitary functionalities?We give a negative answer to this question, by showing the existence of solitary functionalities that cannot be computed with full security. While such a result cannot be proved using fairness-based arguments, our proof builds on the classical proof technique of Cleve (STOC 1986) for ruling out fair coin-tossing and extends it in a nontrivial way.On the positive side, we show that full security against any number of malicious parties is achievable for many natural and useful solitary functionalities, including ones for which the multi-output version cannot be realized with full security.

2019

TCC

Compressible FHE with Applications to PIR
Abstract

Homomorphic encryption (HE) is often viewed as impractical, both in communication and computation. Here we provide an additively homomorphic encryption scheme based on (ring) LWE with nearly optimal rate ($$1-\epsilon $$ for any $$\epsilon >0$$). Moreover, we describe how to compress many Gentry-Sahai-Waters (GSW) ciphertexts (e.g., ciphertexts that may have come from a homomorphic evaluation) into (fewer) high-rate ciphertexts.Using our high-rate HE scheme, we are able for the first time to describe a single-server private information retrieval (PIR) scheme with sufficiently low computational overhead so as to be practical for large databases. Single-server PIR inherently requires the server to perform at least one bit operation per database bit, and we describe a rate-(4/9) scheme with computation which is not so much worse than this inherent lower bound. In fact it is probably less than whole-database AES encryption – specifically about 2.3 mod-q multiplication per database byte, where q is about 50 to 60 bits. Asymptotically, the computational overhead of our PIR scheme is $$\tilde{O}(\log \log \mathsf {\lambda }+ \log \log \log N)$$, where $$\mathsf {\lambda }$$ is the security parameter and N is the number of database files, which are assumed to be sufficiently large.

2019

ASIACRYPT

Homomorphic Encryption for Finite Automata
Abstract

We describe a somewhat homomorphic GSW-like encryption scheme, natively encrypting matrices rather than just single elements. This scheme offers much better performance than existing homomorphic encryption schemes for evaluating encrypted (nondeterministic) finite automata (NFAs). Differently from GSW, we do not know how to reduce the security of this scheme from LWE, instead we reduce it from a stronger assumption, that can be thought of as an inhomogeneous variant of the NTRU assumption. This assumption (that we term iNTRU) may be useful and interesting in its own right, and we examine a few of its properties. We also examine methods to encode regular expressions as NFAs, and in particular explore a new optimization problem, motivated by our application to encrypted NFA evaluation. In this problem, we seek to minimize the number of states in an NFA for a given expression, subject to the constraint on the ambiguity of the NFA.

2018

CRYPTO

Round-Optimal Secure Multi-Party Computation
📺
Abstract

Secure multi-party computation (MPC) is a central cryptographic task that allows a set of mutually distrustful parties to jointly compute some function of their private inputs where security should hold in the presence of a malicious adversary that can corrupt any number of parties. Despite extensive research, the precise round complexity of this “standard-bearer” cryptographic primitive is unknown. Recently, Garg, Mukherjee, Pandey and Polychroniadou, in EUROCRYPT 2016 demonstrated that the round complexity of any MPC protocol relying on black-box proofs of security in the plain model must be at least four. Following this work, independently Ananth, Choudhuri and Jain, CRYPTO 2017 and Brakerski, Halevi, and Polychroniadou, TCC 2017 made progress towards solving this question and constructed four-round protocols based on non-polynomial time assumptions. More recently, Ciampi, Ostrovsky, Siniscalchi and Visconti in TCC 2017 closed the gap for two-party protocols by constructing a four-round protocol from polynomial-time assumptions. In another work, Ciampi, Ostrovsky, Siniscalchi and Visconti TCC 2017 showed how to design a four-round multi-party protocol for the specific case of multi-party coin-tossing.In this work, we resolve this question by designing a four-round actively secure multi-party (two or more parties) protocol for general functionalities under standard polynomial-time hardness assumptions with a black-box proof of security.

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).

2018

TCC

Best Possible Information-Theoretic MPC
Abstract

We reconsider the security guarantee that can be achieved by general protocols for secure multiparty computation in the most basic of settings: information-theoretic security against a semi-honest adversary. Since the 1980s, we have elegant solutions to this problem that offer full security, as long as the adversary controls a minority of the parties, but fail completely when that threshold is crossed. In this work, we revisit this problem, questioning the optimality of the standard notion of security. We put forward a new notion of information-theoretic security which is strictly stronger than the standard one, and which we argue to be “best possible.” This notion still requires full security against dishonest minority in the usual sense, and adds a meaningful notion of information-theoretic security even against dishonest majority.We present protocols for useful classes of functions that satisfy this new notion of security. Our protocols have the unique feature of combining the efficiency benefits of protocols for an honest majority and (most of) the security benefits of protocols for dishonest majority. We further extend some of the solutions to the malicious setting.

2014

CRYPTO

2014

EUROCRYPT

2010

EPRINT

A Simple BGN-type Cryptosystem from LWE
Abstract

We construct a simple public-key encryption scheme that supports polynomially many additions and one multiplication, similar to the cryptosystem of Boneh, Goh, and Nissim (BGN). Security is based on the hardness of the learning with errors (LWE) problem, which is known to be as hard as certain worst-case lattice problems.
Some features of our cryptosystem include support for large message space, an easy way of achieving formula-privacy, a better message-to-ciphertext expansion ratio than BGN, and an easy way of multiplying two encrypted polynomials. Also, the scheme can be made identity-based and leakage-resilient (at the cost of a higher message-to-ciphertext expansion ratio).

2010

EPRINT

i-Hop Homomorphic Encryption and Rerandomizable Yao Circuits
Abstract

Homomorphic encryption (HE) schemes enable computing functions on encrypted data, by means of a public $\Eval$ procedure that can be applied to ciphertexts. But the evaluated ciphertexts so generated may differ from freshly encrypted ones. This brings up the question of whether one can keep computing on evaluated ciphertexts. An \emph{$i$-hop} homomorphic encryption scheme is one where $\Eval$ can be called on its own output up to $i$~times, while still being able to decrypt the result. A \emph{multi-hop} homomorphic encryption is a scheme which is $i$-hop for all~$i$. In this work we study $i$-hop and multi-hop schemes in conjunction with the properties of function-privacy (i.e., $\Eval$'s output hides the function) and compactness (i.e., the output of $\Eval$ is short). We provide formal definitions and describe several constructions.
First, we observe that "bootstrapping" techniques can be used to convert any (1-hop) homomorphic encryption scheme into an $i$-hop scheme for any~$i$, and the result inherits the function-privacy and/or compactness of the underlying scheme. However, if the underlying scheme is not compact (such as schemes derived from Yao circuits) then the complexity of the resulting $i$-hop scheme can be as high as $k^{O(i)}$.
We then describe a specific DDH-based multi-hop homomorphic encryption scheme that does not suffer from this exponential blowup. Although not compact, this scheme has complexity linear in the size of the composed function, independently of the number of hops. The main technical ingredient in this solution is a \emph{re-randomizable} variant of the Yao circuits. Namely, given a garbled circuit, anyone can re-garble it in such a way that even the party that generated the original garbled circuit cannot recognize it. This construction may be of independent interest.

2010

EPRINT

Composable Security Analysis of OS Services
Abstract

We provide an analytical framework for analyzing basic integrity properties of file systems, namely the binding of files to filenames and writing capabilities. A salient feature of our modeling and analysis is that it is *composable*: In spite of the fact that we analyze the filesystem in isolation, security is guaranteed even when the file system operates as a component within an arbitrary, and potentially adversarial system. Such secure composability properties seem essential when trying to assert the security of large systems.
Our results are obtained by adapting the *Universally Composable* (UC) security framework to the analysis of software systems. Originally developed for cryptographic protocols, the UC framework allows the analysis of simple components in isolation, and provides assurance that these components maintain their behavior when combined in a large system, potentially under adversarial conditions.

2009

EPRINT

Attacking Cryptographic Schemes Based on "Perturbation Polynomials"
Abstract

We show attacks on several cryptographic schemes that have recently been proposed for achieving various security goals in sensor networks. Roughly speaking, these schemes all use "perturbation polynomials" to add "noise" to polynomial-based systems that offer information-theoretic security, in an attempt to increase the resilience threshold while maintaining efficiency. We show that the heuristic security arguments given for these modified schemes do not hold, and that they can be completely broken once we allow even a slight extension of the parameters beyond those achieved by the underlying information-theoretic schemes.
Our attacks apply to the key predistribution scheme of Zhang et al. (MobiHoc~2007), the access-control schemes of Subramanian et al. (PerCom~2007), and the authentication schemes of Zhang et~al. (INFOCOM~2008).

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

Degradation and Amplification of Computational Hardness
Abstract

What happens when you use a partially defective bit-commitment protocol to commit to the same bit many times? For example, suppose that the protocol allows the receiver to guess the committed bit with advantage $\eps$, and that you used that protocol to commit to the same bit more than $1/\eps$ times. Or suppose that you encrypted some message many times (to many people), only to discover later that the encryption scheme that you were using is partially defective, and an eavesdropper has some noticeable advantage in guessing the encrypted message from the ciphertext. Can we at least show that even after many such encryptions, the eavesdropper could not have learned the message with certainty?
In this work we take another look at amplification and degradation of computational hardness. We describe a rather generic setting where one can argue about amplification or degradation of computational hardness via sequential repetition of interactive protocols, and prove that in all the cases that we consider, it behaves as one would expect from the corresponding information theoretic bounds. In particular, for the example above we can prove that after committing to the same bit for $n$ times, the receiver's advantage in guessing the encrypted bit is negligibly close to $1-(1-\eps)^n$.
Our results for hardness amplification follow just by observing that some of the known proofs for Yao's lemmas can be easily extended also to handle interactive protocols. On the other hand, the question of hardness degradation was never considered before as far as we know, and we prove these results from scratch.

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

Invertible Universal Hashing and the TET Encryption Mode
Abstract

This work describes a mode of operation, TET, that turns a regular block cipher into a length-preserving enciphering scheme for messages of (almost) arbitrary length. When using an n-bit block cipher, the resulting scheme can handle input of any bit-length between n and 2^n and associated data of arbitrary length.
The mode TET is a concrete instantiation of the generic mode of operation that was proposed by Naor and Reingold, extended to handle tweaks and inputs of arbitrary bit length. The main technical tool is a construction of invertible ``universal hashing'' on wide blocks, which is as efficient to compute and invert as polynomial-evaluation hash.

2007

EPRINT

Smooth Projective Hashing and Two-Message Oblivious Transfer
Abstract

We present a general framework for constructing two-message oblivious transfer protocols using a modification of Cramer and Shoup's notion of smooth projective hashing (2002). This framework is an abstraction of the two-message oblivious transfer protocols of Naor and Pinkas (2001) and Aiello et al. (2001), whose security is based on the Decisional Diffie Hellman Assumption. In particular, we give two new oblivious transfer protocols. The security of one is based on the Quadratic Residuosity Assumption, and the security of the other is based on the $N$'th Residuosity Assumption. Our security guarantees are not simulation based, but are similar to the guarantees of the aforementioned two constructions. Compared to other applications of smooth projective hashing, in our context we must deal also with maliciously chosen parameters, which raises new technical difficulties.
We also improve on prior constructions of factoring-based smooth universal hashing, in that our constructions *do not require that the underlying RSA-composite is a product of safe primes*. In fact, we observe that the safe-prime requirement is unnecessary for many prior constructions. In particular, we observe that the factoring-based CCA secure encryption schemes due to Cramer-Shoup, Gennaro-Lindell and Camenisch-Shoup remain secure even if the underlying RSA-composite is not a product of safe primes. (This holds for the schemes based on the Quadratic Residuosity Assumption as well as the ones based on the $N$'th Residuosity Assumption.)

2007

EPRINT

Security under Key-Dependent Inputs
Abstract

In this work we re-visit the question of building cryptographic primitives that remain secure even when queried on inputs that depend on the secret key. This was investigated by Black, Rogaway, and Shrimpton in the context of randomized encryption schemes and in the random oracle model. We extend the investigation to deterministic symmetric schemes (such as PRFs and block ciphers) and to the standard model. We term this notion "security against key-dependent-input attack", or KDI-security for short. Our motivation for studying KDI security is the existence of significant real-world implementations of deterministic encryption (in the context of storage encryption) that actually rely on their building blocks to be KDI secure.
We consider many natural constructions for PRFs, ciphers, tweakable ciphers and randomized encryption, and examine them with respect to their KDI security. We exhibit inherent limitations of this notion and show many natural constructions that fail to be KDI secure in the standard model, including some schemes that have been proven in the random oracle model. On the positive side, we demonstrate examples where some measure of KDI security can be provably achieved (in particular, we show such examples in the standard model).

2006

EPRINT

Mitigating Dictionary Attacks on Password-Protected Local Storage
Abstract

We address the issue of encrypting data in local storage using a key that is derived from the user's password. The typical solution in use today is to derive the key from the password using a cryptographic hash function. This solution provides relatively weak protection, since an attacker that gets hold of the encrypted data can mount an off-line dictionary attack on the user's password, thereby recovering the key and decrypting the stored data.
We propose an approach for limiting off-line dictionary attacks in this setting without relying on secret storage or secure hardware. In our proposal, the process of deriving a key from the password requires the user to solve a puzzle that is presumed to be solvable only by humans (e.g, a CAPTCHA). We describe a simple protocol using this approach: many different puzzles are stored on the disk, the user's password is used to specify which of them need to be solved, and the encryption key is derived from the password and the solutions of the specified puzzles. Completely specifying and analyzing this simple protocol, however, raises a host of modeling and technical issues, such as new properties of human-solvable puzzles and some seemingly hard combinatorial problems. Here we analyze this protocol in some interesting special cases.

2005

EPRINT

A sufficient condition for key-privacy
Abstract

The notion of key privacy for encryption schemes was defined formally by Bellare, Boldyreva, Desai and Pointcheval in Asiacrypt 2001. This notion seems useful in settings where anonymity is important. In this short note we describe a (very simple) sufficient condition for key privacy. In a nutshell, a scheme that provides data privacy is guaranteed to provide also key privacy if the distribution of a *random encryption of a random message* is independent of the public key that is used for the encryption.

2005

EPRINT

A model and architecture for pseudo-random generation with applications to /dev/random
Abstract

We present a formal model and a simple architecture for robust pseudorandom generation that ensures resilience in the face of an
observer with partial knowledge/control of the generator's entropy source. Our model and architecture have the following properties:
1 Resilience: The generator's output looks random to an observer with no knowledge of the internal state. This holds even if that observer has complete control over data that is used to refresh the internal state.
2 Forward security: Past output of the generator looks random to an observer, even if the observer learns the internal state at a later time.
3 Backward security/Break-in recovery: Future output of the generator looks random, even to an observer with knowledge of the current state, provided that the generator is refreshed with data of sufficient entropy.
Architectures such as above were suggested before. This work differs
from previous attempts in that we present a formal model for robust
pseudo-random generation, and provide a formal proof within this model
for the security of our architecture. To our knowledge, this is the
first attempt at a rigorous model for this problem.
Our formal modeling advocates the separation of the *entropy extraction* phase from the *output generation* phase. We argue that the former is information-theoretic in nature, and could therefore rely on combinatorial and statistical tools rather than on cryptography. On the other hand, we show that the latter can be implemented using any standard (non-robust) cryptographic PRG.
We also discuss the applicability of our architecture for applications such as /dev/(u)random in Linux and pseudorandom generation on smartcards.

2005

EPRINT

Enforcing Confinement in Distributed Storage and a Cryptographic Model for Access Control
Abstract

This work is concerned with the security of the standard T10 OSD protocol, a capability-based protocol for object stores designed by the OSD SNIA working group. The Object Store security protocol is designed to provide access control enforcement in a distributed storage setting such as a Storage Area Network (SAN) environment. In this work we consider in particular the ability of the OSD protocol to enforce *confinement*, which is the property that even misbehaving participants can not leak secret information across predefined boundaries.
We observe that being a "pure capability" protocol, the plain vanilla OSD protocol is incapable of enforcing confinement. We show, however, that given a trustworthy infrastructure for authentication and secure channels, the protocol can be used in a manner that achieves the desired property (and does not require any change in the message format). Thus we demonstrate that object stores can in principle be used in a standard fashion in applications that require protection against leakage of secret data.
Having identified a problem and proposed a solution, we proceed to prove formally that the proposed protocol indeed meets all its security goals. In the process we refine common cryptographic models in order to be able to reason about confinement, and then devise a precise model for a distributed capability-based access-control mechanism. To our knowledge, this is the first time such a model for access-control is defined in a cryptographic setting, and defining it highlights what can and cannot be achieved by such mechanisms.

2005

EPRINT

A plausible approach to computer-aided cryptographic proofs
Abstract

This paper tries to sell a potential approach to making the process of writing and verifying our cryptographic proofs less prone to errors. Specifically, I advocate creating an automated tool to help us with the mundane parts of writing and checking common arguments in our proofs. On a high level, this tool should help us verify that two pieces of code induce the same probability distribution on some of their common variables.
In this paper I explain why I think that such a tool would be useful, by considering two very different proofs of security from the literature and showing the places in those proofs where having this tool would have been useful. I also explain how I believe that this tool can be built. Perhaps surprisingly, it seems to me that the functionality of such tool can be implemented using only ``static code analysis'' (i.e., things that compilers do).

2005

EPRINT

Universally Composable Password-Based Key Exchange
Abstract

We propose and realize a definition of security for password-based key exchange within the framework of universal composability (UC), thus providing security guarantees under arbitrary composition with other protocols. In addition, our definition captures some aspects of the problem that were not adequately addressed by most prior notions. For instance, our definition does not assume any underlying probability distribution on passwords, nor does it assume independence between passwords chosen by different parties. We also formulate a definition of password-based secure channels, and show how to realize such channels given any password-based key exchange protocol.
The password-based key exchange protocol shown here is in the common reference string model and relies on standard number-theoretic assumptions. The components of our protocol can be instantiated to give a relatively efficient solution which is conceivably usable in practice. We also show that it is impossible to satisfy our definition in the "plain" model (e.g., without a common reference string).

2004

EPRINT

EME*: extending EME to handle arbitrary-length messages with associated data
Abstract

This work describes a mode of operation, EME*, that turns a regular block cipher into a length-preserving enciphering scheme for messages of (almost) arbitrary length. Specifically, the resulting scheme can handle any bit-length, not shorter than the block size of the underlying cipher, and it also handles associated data of arbitrary bit-length. Such a scheme can either be used directly in applications that need encryption but cannot afford length expansion, or serve as a convenient building block for higher-level modes.
The mode EME* is a refinement of the EME mode of Halevi and Rogaway, and it inherits the efficiency and parallelism from the original EME.

2004

EPRINT

Adaptively-Secure, Non-Interactive Public-Key Encryption
Abstract

Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of already-corrupted parties. Ideally, an adaptively-secure encryption scheme should, like standard public-key encryption, allow arbitrarily-many parties to use a single encryption key to securely encrypt arbitrarily-many messages to a given receiver who maintains only a single short decryption key. However, it is known that these requirements are impossible to achieve: no non-interactive encryption scheme that supports encryption of an unbounded number of messages and uses a single, unchanging decryption key can be adaptively secure.
Impossibility holds even if secure data erasure is possible.
We show that this limitation can be overcome by updating the decryption key over time and making some mild assumptions about
the frequency of communication between parties. Using this approach,
we construct adaptively-secure, completely non-interactive encryption
schemes supporting secure encryption of arbitrarily-many messages from
arbitrarily-many senders. Our schemes additionally provide
forward security and security against chosen-ciphertext attacks.

2004

EPRINT

Hardness amplification of weakly verifiable puzzles
Abstract

Is it harder to solve many puzzles than it is to solve just one? This
question has different answers, depending on how you define puzzles.
For the case of inverting one-way functions it was shown by Yao that
solving many independent instances simultaneously is indeed harder
than solving a single instance (cf. the transformation from weak to
strong one-way functions). The known proofs of that result, however,
use in an essential way the fact that for one-way functions, verifying
candidate solutions to a given puzzle is easy. We extend this result
to the case where solutions are efficiently verifiable only by
the party that generated the puzzle. We call such puzzles weakly
verifiable. That is, for weakly verifiable puzzles we show that if no
efficient algorithm can solve a single puzzle with probability more
than $\eps$, then no efficient algorithm can solve $n$ independent
puzzles simultaneously with probability more than $\eps^n$. We also
demonstrate that when the puzzles are not even weakly verifiable,
solving many puzzles may be no harder than solving a single one.
Hardness amplification of weakly verifiable puzzles turns out to be
closely related to the reduction of soundness error under parallel
repetition in computationally sound arguments. Indeed, the proof of
Bellare, Impagliazzo and Naor that parallel repetition reduces
soundness error in three-round argument systems implies a result
similar to our first result, albeit with considerably worse
parameters. Also, our second result is an adaptation of their proof
that parallel repetition of four-round systems may not reduce the
soundness error.

2003

EPRINT

A Parallelizable Enciphering Mode
Abstract

We describe a block-cipher mode of operation, EME, that turns an
n-bit block cipher into a tweakable enciphering scheme that acts
on strings of mn bits, where m \in [1..n]. The mode is parallelizable, but as serial-efficient as the non-parallelizable mode CMC. EME can be used to solve the disk-sector encryption problem. The algorithm entails two layers of ECB encryption and a "lightweight mixing" in between. We prove EME secure, in the reduction-based sense of modern cryptography. We motivate some of the design choices in EME by showing that a few
simple modifications of this mode are insecure.

2003

EPRINT

A Forward-Secure Public-Key Encryption Scheme
Abstract

Cryptographic computations are often carried out on insecure devices
for which the threat of key exposure represents a serious and
realistic concern. In an effort to mitigate the damage caused by
exposure of secret keys stored on such devices, the paradigm of
\emph{forward security} was introduced. In a forward-secure scheme,
secret keys are updated at regular periods of time; exposure of the
secret key corresponding to a given time period does not enable an
adversary to ``break'' the scheme (in the appropriate sense) for
any \emph{prior} time period. A number of constructions of
forward-secure digital signature schemes, key-exchange protocols,
and symmetric-key schemes are known.
We present the first non-trivial constructions of (non-interactive)
forward-secure public-key encryption schemes. Our main construction
achieves security against chosen-plaintext attacks under the decisional
bilinear Diffie-Hellman assumption in the standard model. This
scheme is practical, and all parameters grow at most logarithmically
with the total number of time periods. We also give a slightly more
efficient scheme in the random oracle model. Both our schemes can be
extended to achieve security against chosen-ciphertext attacks and to
support an unbounded number of time periods.
Toward our goal, we introduce the notion of \emph{binary tree
encryption} and show how to construct a binary tree encryption scheme
in the standard model. This new primitive may be of independent
interest. In particular, we use it to construct the first known example
of a (hierarchical) identity-based encryption scheme that is secure
in the standard model. (Here, however, the notion of security we
achieve is slightly weaker than what is achieved in some previous constructions
in the random oracle model.)

2003

EPRINT

A Tweakable Enciphering Mode
Abstract

We describe a block-cipher mode of operation, CMC, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m>=2. When the underlying block cipher is secure in the sense of a strong pseudorandom permutation (PRP), our scheme is secure in the sense of tweakable, strong PRP. Such an object can be used to encipher the sectors of a disk, in-place, offering security as good as can be obtained in this setting. CMC makes a pass of CBC encryption, xors in a mask, and then makes a pass of CBC decryption; no universal hashing, nor any other non-trivial operation beyond the block-cipher calls, is employed.
Besides proving the security of CMC we initiate a more general investigation of tweakable enciphering schemes, considering issues like the non-malleability of these objects.

2003

EPRINT

On the random-oracle methodology as applied to length-restricted signature schemes
Abstract

In earlier work, we described a ``pathological'' example of a signature scheme that is secure in the random-oracle model, but for which no secure implementation exists. For that example, however, it was crucial that the scheme is able to sign "long messages" (i.e., messages whose
length is not a-priori bounded). This left open the possibility that
the Random Oracle Methodology is sound with respect to signature schemes
that sign only "short" messages (i.e., messages of a-priori bounded length, smaller than the length of the keys in use), and are "memoryless" (i.e., the only thing kept between different signature
generations is the initial signing-key). In this work, we extend our negative result to address such signature schemes. A key ingredient in our proof is a new type of interactive proof systems, which may be of independent interest.

2003

EPRINT

Chosen-Ciphertext Security from Identity-Based Encryption
Abstract

We show how to construct a CCA-secure public-key encryption scheme
from any CPA-secure identity-based encryption (IBE) scheme. Our
conversion from IBE to a CCA-secure scheme is simple,
efficient, and provably secure in the standard model (i.e., security
of the resulting scheme does not rely on the random oracle model).
In addition, the resulting scheme achieves CCA security even if the
underlying IBE scheme satisfies only a ``weak'' notion of security
which is known to be achievable in the standard model based on the
bilinear Diffie-Hellman assumption. Thus, our results yield a new
construction of CCA-secure public-key encryption in the
standard model. Interestingly, the resulting scheme avoids any
non-interactive proofs of ``well-formedness'' which were shown to
underlie all previously-known constructions.
We also extend our technique to obtain a simple and reasonably efficient
method for securing any BTE scheme against adaptive chosen-ciphertext
attacks. This, in turn, yields more efficient constructions of CCA-secure
(hierarchical) identity-based and forward-secure encryption schemes in the
standard model.
Our results --- building on previous black-box separations ---
rule out black-box constructions of IBE from CPA-secure public-key encryption.

2002

EPRINT

Scream: a software-efficient stream cipher
Abstract

We report on the design of Scream, a new software-efficient stream
cipher, which was designed to be a ``more secure SEAL''. Following SEAL, the design of Scream resembles in many ways a block-cipher design. The new cipher is roughly as fast as SEAL, but we believe that it offers a significantly higher security level. In the process of designing this cipher, we re-visit the SEAL design paradigm, exhibiting some tradeoffs and limitations.

2002

EPRINT

Cryptanalysis of stream ciphers with linear masking
Abstract

We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly random process. Roughly, the ciphers to which this method applies consist of a ``non-linear process'' (say, akin to a round function in block ciphers), and a ``linear process'' such as an LFSR (or even fixed tables). The output of the cipher can be the linear sum of both processes. To attack such ciphers, we look for any property of the ``non-linear process'' that can be distinguished from random. In addition, we look for a linear combination of the linear process that vanishes. We then consider the same linear combination applied to the cipher's output, and try to find traces of the distinguishing property.
In this report we analyze two specific ``distinguishing properties''. One is a linear approximation of the non-linear process, which we demonstrate on the stream cipher SNOW. This attack needs roughly $2^{95}$ words of output, with work-load of about $2^{100}$. The other is a ``low-diffusion'' attack, that we apply to the cipher Scream-0. The latter attack needs only about $2^{43}$ bytes of output, using roughly $2^{50}$ space and $2^{80}$ time.

2001

EPRINT

An observation regarding Jutla's modes of operation
Abstract

Recently, Jutla suggested two new modes of operation for block ciphers. These modes build on traditional CBC and ECB
modes, respectively, but add to them masking of the outputs and inputs. Jutla proved that these masking operations considerably
strengthen CBC and ECB modes. In particular, together with a simple checksum, the modified modes ensure not only confidentiality, but
also authenticity. Similar modes were also suggested by Gligor and Donsecu and by Rogaway.
In Jutla's proposal (as well as in some of the other proposals), the masks themselves are derived from an IV via the same block
cipher as used for the encryption (perhaps with a different key). In this work we note, however, that the function for deriving these masks
need not be cryptographic at all. In particular, we prove that a universal hash function (a-la-Carter-Wegman) is sufficient for this
purpose.

1999

EPRINT

Public-key cryptography and password protocols
Abstract

We study protocols for strong authentication and key exchange in asymmetric
scenarios where the authentication server possesses a pair of private and
public keys while the client has only a weak human-memorizable password
as its authentication key. We present and analyze several simple password
protocols in this scenario, and show that the security of these protocols
can be formally proven based on standard cryptographic assumptions.
Remarkably, our analysis shows optimal resistance to off-line password
guessing attacks under the choice of suitable public key encryption
functions. In addition to user authentication, we enhance our protocols
to provide two-way authentication, authenticated key exchange, defense
against server's compromise, and user anonymity. We complement these
results with a proof that public key techniques are unavoidable for
password protocols that resist off-line guessing attacks.
As a further contribution, we introduce the notion of public passwords
that enables the use of the above protocols in situations where the
client's machine does not have the means to validate the server's
public key. Public passwords serve as "hand-held certificates" that
the user can carry without the need for special computing devices.

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

EPRINT

The Random Oracle Methodology, Revisited
Abstract

We take a critical look at the relationship between the security of
cryptographic schemes in the Random Oracle Model, and the security of the
schemes that result from implementing the random oracle by so called
"cryptographic hash functions".
The main result of this paper is a negative one: There exist signature and
encryption schemes that are secure in the Random Oracle Model, but for which
any implementation of the random oracle results in insecure schemes.
In the process of devising the above schemes, we consider possible definitions
for the notion of a "good implementation" of a random oracle, pointing out
limitations and challenges.

1998

EPRINT

Maintaining Authenticated Communication in the Presence of Break-ins
Abstract

We study the problem of maintaining authenticated communication over untrusted
communication channels, in a scenario where the communicating parties may be
occasionally and repeatedly broken into for transient periods of time. Once
a party is broken into, its cryptographic keys are exposed and perhaps
modified. Yet, we want parties whose security is thus compromised to regain
their ability to communicate in an authenticated way aided by other parties.
In this work we present a mathematical model for this highly adversarial
setting, exhibiting salient properties and parameters, and then describe
a practically-appealing protocol for the task of maintaining authenticated
communication in this model.
A key element in our solution is devising {\em proactive distributed signature
(PDS) schemes} in our model. Although PDS schemes are known in the literature,
they are all designed for a model where authenticated communication and
broadcast primitives are available. We therefore show how these schemes can be
modified to work in our model, where no such primitives are available a-priori.
In the process of devising the above schemes, we also present a new definition
of PDS schemes (and of distributed signature schemes in general). This
definition may be of independent interest.

1998

EPRINT

More on Proofs of Knowledge
Abstract

The notion of proofs of knowledge is central to cryptographic
protocols, and many definitions for it have been proposed. In this work
we explore a different facet of this notion, not addressed by prior
definitions. Specifically, prior definitions concentrate on capturing
the properties of the verifier, and do not pay much attention to the
properties of the prover.
Our new definition is strictly stronger than previous ones, and captures
new and desirable properties. In particular, it guarantees prover
feasibility, that is, it guarantees that the time spent by the prover
in a proof of knowledge is comparable to that it spends in an "extraction"
of this knowledge. Our definition also enables one to consider meaningfully
the case of a single, specific prover.

1998

EPRINT

Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems
Abstract

The heart of the task of building public key cryptosystems is viewed
as that of ``making trapdoors;'' in fact, public key cryptosystems and
trapdoor functions are often discussed as synonymous. How accurate is
this view? In this paper we endeavor to get a better understanding of
the nature of ``trapdoorness'' and its relation to public key
cryptosystems, by broadening the scope of the investigation: we look
at general trapdoor functions; that is, functions that are not
necessarily injective (ie., one-to-one). Our first result is somewhat
surprising: we show that non-injective trapdoor functions (with
super-polynomial pre-image size) can be constructed {from} any one-way
function (and hence it is unlikely that they suffice for public key
encryption). On the other hand, we show that trapdoor functions with
polynomial pre-image size are sufficient for public key encryption.
Together, these two results indicate that the pre-image size is a
fundamental parameter of trapdoor functions. We then turn our
attention to the converse, asking what kinds of trapdoor functions can
be constructed from public key cryptosystems. We take a first step by
showing that in the random-oracle model one can construct injective
trapdoor functions from any public key cryptosystem.

1996

EPRINT

Collision-Free Hashing from Lattice Problems
Abstract

Recently Ajtai described a construction of one-way functions whose
security is equivalent to the difficulty of some well known approximation
problems in lattices. We show that essentially the same
construction can also be used to obtain collision-free hashing.

1996

EPRINT

Public-Key Cryptosystems from Lattice Reduction Problems
Abstract

We present a new proposal for a trapdoor one-way function, from which
we derive public-key encryption and digital signatures.
The security of the new construction is based on the
conjectured computational difficulty of lattice-reduction problems,
providing a possible alternative to existing
public-key encryption algorithms
and digital signatures such as RSA and DSS.

#### Program Committees

- Eurocrypt 2019
- Eurocrypt 2016
- TCC 2015
- Crypto 2013
- PKC 2013
- TCC 2011
- Asiacrypt 2009
- Crypto 2009
- Crypto 2009
- Eurocrypt 2008
- Asiacrypt 2007
- Eurocrypt 2007
- TCC 2006
- Crypto 2005
- Eurocrypt 2005
- PKC 2002
- Eurocrypt 2001
- Crypto 2000

#### Coauthors

- Shweta Agrawal (1)
- Martin R. Albrecht (1)
- Boaz Barak (1)
- Mihir Bellare (2)
- Fabrice Benhamouda (1)
- Nir Bitansky (2)
- John Black (1)
- Dan Boneh (4)
- Zvika Brakerski (3)
- Ran Canetti (22)
- Dario Catalano (1)
- Suresh Chari (1)
- Yilei Chen (1)
- Don Coppersmith (5)
- Jean-Sébastien Coron (3)
- Yevgeniy Dodis (3)
- Sanjam Garg (6)
- Nicholas Genise (1)
- Rosario Gennaro (6)
- Craig Gentry (33)
- Oded Goldreich (7)
- Shafi Goldwasser (5)
- Sergey Gorbunov (4)
- François Grieu (1)
- William Eric Hall (2)
- Mike Hamburg (1)
- Carmit Hazay (1)
- Amir Herzberg (2)
- Nick Howgrave-Graham (1)
- Yuval Ishai (3)
- Abhishek Jain (1)
- Charanjit S. Jutla (8)
- Yael Tauman Kalai (2)
- Paul A. Karger (1)
- Jonathan Katz (10)
- Ilan Komargodski (1)
- Hugo Krawczyk (10)
- Ted Krovetz (1)
- Eyal Kushilevitz (3)
- Tancrède Lepoint (3)
- Baiyu Li (1)
- Chengyu Lin (1)
- Huijia Lin (1)
- Yehuda Lindell (3)
- Steve Lu (1)
- Philip D. MacKenzie (2)
- Hemanta K. Maji (2)
- Nikolaos Makriyannis (1)
- Silvio Micali (2)
- Daniele Micciancio (1)
- Eric Miles (2)
- Steven Myers (1)
- David Naccache (1)
- Dalit Naor (1)
- Valeria Nikolaenko (2)
- Rafail Ostrovsky (2)
- Birgit Pfitzmann (1)
- Benny Pinkas (1)
- Antigoni Polychroniadou (2)
- Tal Rabin (12)
- Charles Rackoff (1)
- Mariana Raykova (7)
- Steffen Reidt (1)
- Leonid Reyzin (1)
- Phillip Rogaway (4)
- Ron D. Rothblum (1)
- Guy N. Rothblum (1)
- Arnay Roy (2)
- Amit Sahai (9)
- Gil Segev (2)
- Victor Shoup (4)
- Nigel P. Smart (3)
- Michael Steiner (5)
- Julien P. Stern (1)
- Mehdi Tibouchi (3)
- Salil P. Vadhan (2)
- Vinod Vaikuntanathan (7)
- Marten van Dijk (1)
- Wietse Venema (1)
- Muthuramakrishnan Venkitasubramaniam (1)
- Dhinakaran Vinayagamurthy (2)
- Brent Waters (1)
- Daniel Wichs (5)
- Stephen D. Wolthusen (1)
- Eylon Yogev (1)
- Mark Zhandry (2)