Abstract: We study Pseudorandom Number Generators (PRNGs) based on block ciphers and hash functions. We first give a general security framework for PRNGs that takes into consideration the attacks that users are concerned about in practice. We then analyze the most popular ones, including the ANSI X9.17 PRNG and the FIPS 186 PRNG. Our results also suggest ways in which these PRNGs can be made more efficient and more secure.
Ref: Extended abstract to appear in Advances in Cryptology - Eurocrypt 2002 Proceedings, Lecture Notes in Computer Science Vol. ??, L. Knudsen ed., Springer-Verlag, 2002.
Full paper: Available soon.
Abstract: We consider a novel security requirement of encryption schemes that we call ``key-privacy'' or ``anonymity''. It asks that an eavesdropper in possession of a ciphertext not be able to tell which specific key, out of a set of known public keys, is the one under which the ciphertext was created, meaning the receiver is anonymous from the point of view of the adversary. We investigate the anonymity of known encryption schemes. We prove that the El Gamal scheme provides anonymity under chosen-plaintext attack assuming the Decision Diffie-Hellman problem is hard and that the Cramer-Shoup scheme provides anonymity under chosen-ciphertext attack under the same assumption. We also consider anonymity for trapdoor permutations. Known attacks indicate that the RSA trapdoor permutation is not anonymous and neither are the standard encryption schemes based on it. We provide a variant of RSA-OAEP that provides anonymity in the random oracle model assuming RSA is one-way. We also give constructions of anonymous trapdoor permutations, assuming RSA is one-way, which yield anonymous encryption schemes in the standard model.
Ref: Extended abstract appears in Advances in Cryptology - Asiacrypt 2001 Proceedings, Lecture Notes in Computer Science Vol. ??, C. Boyd ed., Springer-Verlag, 2001.
Full paper: Available soon.
Abstract: We investigate several alternate characterizations of pseudorandom functions (PRFs) and pseudorandom permutations (PRPs) in a concrete security setting. By analyzing the concrete complexity of the reductions between the standard notions and the alternate ones, we show that the latter, while equivalent under polynomial-time reductions, are weaker in the concrete security sense. With these alternate notions, we argue that it is possible to get better concrete security bounds for certain PRF/PRP-based schemes. As an example, we show how using an alternate characterization of a PRF could result in tighter security bounds for some types of message authentication codes. We also use this method to give a simple concrete security analysis of the counter mode of encryption. In addition, our results provide some insight into how injectivity impacts pseudorandomness.
Ref: Extended abstract to appear in Advances in Cryptology - Asiacrypt 2000 Proceedings, Lecture Notes in Computer Science Vol. ??, T. Okamoto ed., Springer-Verlag, 2000.
Full paper: Extended abstract available as postscript.
New Paradigms for Constructing Symmetric Encryption Schemes
Secure Against Chosen-Ciphertext Attack
Authors:
A. Desai
Abstract: The paradigms currently used to realize symmetric encryption schemes secure against adaptive chosen ciphertext attack (CCA) try to make it infeasible for an attacker to forge ``valid'' ciphertexts. This is achieved by either encoding the plaintext with some redundancy before encrypting or by appending a MAC to the ciphertext. We suggest schemes which are provably secure against CCA, and yet every string is a ``valid'' ciphertext. Consequently, our schemes have a smaller ciphertext expansion than any other scheme known to be secure against CCA. Our most efficient scheme is based on a novel use of ``variable-length'' pseudorandom functions and can be efficiently implemented using block ciphers. We relate the difficulty of breaking our schemes to that of breaking the underlying primitives in a precise and quantitative way.
Ref: Extended abstract appears in Advances in Cryptology - Crypto 2000 Proceedings, Lecture Notes in Computer Science Vol. 1880, M. Bellare ed., Springer-Verlag, 2000.
Full paper: Available as compressed postscript or postscript.
The Security of All-Or-Nothing Encryption: Protecting
Against Exhaustive Key Search
Authors:
A. Desai
Abstract: We investigate the all-or-nothing encryption paradigm which was introduced by Rivest as a new mode of operation for block ciphers. The paradigm involves composing an all-or-nothing transform (AONT) with an ordinary encryption mode. The goal is to have secure encryption modes with the additional property that exhaustive key-search attacks on them are slowed down by a factor equal to the number of blocks in the ciphertext. We give a new notion concerned with the privacy of keys that provably captures this key-search resistance property. We suggest a new characterization of AONTs and establish that the resulting all-or-nothing encryption paradigm yields secure encryption modes that also meet this notion of key privacy. A consequence of our new characterization is that we get more efficient ways of instantiating the all-or-nothing encryption paradigm. We describe a simple block-cipher-based AONT and prove it secure in the Shannon Model of a block cipher. We also give attacks against alternate paradigms that were believed to have the above key-search resistance property.
Ref: Extended abstract appears in Advances in Cryptology - Crypto 2000 Proceedings, Lecture Notes in Computer Science Vol. 1880, M. Bellare ed., Springer-Verlag, 2000.
Full paper: Available as compressed postscript or postscript.
Relations Among Notions of Security for Public-Key Encryption
Schemes
Authors:
M. Bellare ,
A. Desai ,
D. Pointcheval and
P. Rogaway
Abstract: We compare the relative strengths of popular notions of security for public key encryption schemes. We consider the goals of indistinguishability and non-malleability, each under chosen plaintext attack and two kinds of chosen ciphertext attack. For each of the resulting pairs of definitions we prove either an implication (every scheme meeting one notion must meet the other) or a separation (there is a scheme meeting one notion but not the other, assuming the first notion can be met at all). We similarly treat plaintext awareness, a notion of security in the random oracle model. An additional contribution of this paper is a new definition of non-malleability which we believe is simpler than the previous one.
Ref: Extended abstract is in Advances in Cryptology- Crypto 98 Proceedings, Lecture Notes in Computer Science Vol. 1462, H. Krawcyzk ed., Springer-Verlag, 1998.
Full paper: Available as postscript or pdf.
Slides: Available as postscript.
A Concrete Security Treatment of Symmetric Encryption: Analysis of the DES
Modes of Operation
Authors:
M. Bellare ,
A. Desai ,
E. Jokipii and
P. Rogaway
Abstract: We study notions and schemes for symmetric (ie.~private key) encryption in a concrete security framework.
We give several different notions of security and analyze the concrete complexity of reductions among them. Next we provide concrete security analyses of methods of encrypting using a block cipher, including two of the most popular methods, Cipher Block Chaining and Counter Mode. We establish tight bounds (meaning matching upper bounds and attacks) on the success of adversaries as a function of their resources.
Ref: Extended abstract is in Proceedings of 38th Annual Symposium on Foundations of Computer Science, IEEE, 1997.
Full paper: Available as postscript or pdf.
Slides: Available as postscript.
Back