International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Shai Halevi

Affiliation: IBM Research

Publications

Year
Venue
Title
2020
TCC
Can a Blockchain Keep a Secret? 📺
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
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
Craig Gentry Shai Halevi
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
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 📺
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 📺
Shai Halevi Victor Shoup
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
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.
2017
EUROCRYPT
2017
ASIACRYPT
2017
TCC
2016
CRYPTO
2016
TCC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
TCC
2015
EUROCRYPT
2015
CRYPTO
2015
CRYPTO
2014
CRYPTO
2014
CRYPTO
2014
EUROCRYPT
2014
EUROCRYPT
2014
TCC
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
PKC
2013
PKC
2013
CRYPTO
2013
ASIACRYPT
2013
EUROCRYPT
2012
TCC
2012
EUROCRYPT
2012
CRYPTO
2012
PKC
2011
PKC
2011
TCC
2011
CRYPTO
2011
EUROCRYPT
2011
ASIACRYPT
2010
EPRINT
A Simple BGN-type Cryptosystem from LWE
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
CRYPTO
2010
EUROCRYPT
2010
EUROCRYPT
2010
EPRINT
i-Hop Homomorphic Encryption and Rerandomizable Yao Circuits
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
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
TCC
2009
CRYPTO
2009
EPRINT
Attacking Cryptographic Schemes Based on "Perturbation Polynomials"
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
TCC
2008
TCC
2008
JOFC
2008
EUROCRYPT
2008
CRYPTO
2008
EPRINT
Threshold RSA for Dynamic and Ad-Hoc Groups
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
Shai Halevi Tal Rabin
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
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
CRYPTO
2007
EPRINT
Invertible Universal Hashing and the TET Encryption Mode
Shai Halevi
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
JOFC
2007
EPRINT
Smooth Projective Hashing and Two-Message Oblivious Transfer
Shai Halevi Yael Tauman Kalai
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
TCC
Ad-Hoc Constructions
Shai Halevi
2007
EPRINT
Security under Key-Dependent Inputs
Shai Halevi Hugo Krawczyk
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
CRYPTO
2006
CRYPTO
2006
TCC
2006
EPRINT
Mitigating Dictionary Attacks on Password-Protected Local Storage
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
EUROCRYPT
2005
TCC
2005
TCC
2005
EPRINT
A sufficient condition for key-privacy
Shai Halevi
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
Boaz Barak Shai Halevi
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
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
Shai Halevi
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
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
EUROCRYPT
2004
TCC
2004
EPRINT
EME*: extending EME to handle arbitrary-length messages with associated data
Shai Halevi
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
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
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
CRYPTO
2003
EUROCRYPT
2003
EPRINT
A Parallelizable Enciphering Mode
Shai Halevi Phillip Rogaway
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
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
Shai Halevi Phillip Rogaway
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
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
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
CRYPTO
2002
FSE
2002
EPRINT
Scream: a software-efficient stream cipher
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
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
ASIACRYPT
2001
EPRINT
An observation regarding Jutla's modes of operation
Shai Halevi
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.
2000
CRYPTO
2000
EUROCRYPT
2000
EUROCRYPT
2000
JOFC
1999
CRYPTO
1999
EUROCRYPT
1999
EPRINT
Public-key cryptography and password protocols
Shai Halevi Hugo Krawczyk
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
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.
1999
JOFC
1998
CRYPTO
1998
EPRINT
The Random Oracle Methodology, Revisited
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
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
Shai Halevi Silvio Micali
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
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.
1997
CRYPTO
1997
CRYPTO
1997
FSE
1996
CRYPTO
1996
EPRINT
Collision-Free Hashing from Lattice Problems
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
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.
1995
CRYPTO

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)