Human Oriented Cryptography & Security
Xavier Boyen, Halting Password Puzzles – Hard-to-break Encryption from Human-memorable Keys, in USENIX Security Symposium SECURITY '07, 2007.
Perhaps paradoxically, we argue that the venerable concept of salted iterated hashing, utilized almost universally for deriving cryptographic keys from human-memorable passwords, does not provide the best possible security against brute-force offline dictionary attacks. We introduce the stronger notion of Halting Key Derivation Function, and show how it can improve the security of any real-world password-based encryption system. The principle is to let people attach to their password a secret (and forgettable) cryptographic delay, and condition the key derivation to halt after the hidden delay only when unlocked by the correct password. This design not only increases by a couple of bits the effective strength of any password that we feed to it, but also presents operational advantages that further enhance its long-term security. We demonstrate an actual implementation that interfaces nicely with existing encryption software, and quantify the exact security attained.
Xavier Boyen,
New Paradigms for Password Security (abstract from the keynote lecture),
to appear
in Australasian Conference on Information Security and Privacy ACISP '08,
2008.
Departing from the password protocols and practices in use since the early nineties, we advocate a new approach to password security that maximizes the protection offered to a human user against any attacker, whether rogue or trusted. We show how to reach the toughest attainable security from the meekest memorable secrets, online and offline, using cryptographically sound yet eminently practical techniques.
Dan Boneh and Xavier Boyen, On the Impossibility of Efficiently Combining Collision Resistant Hash Functions, in Advances in Cryptology CRYPTO '06, 2006.
Suppose that we have a number of allegedly collision resistant hash functions at our disposal. To hedge our bets against future attacks on some of these functions, we wish to create a hybrid new function that will be collision resistant as long as at least one of the original functions remains secure. A simple way to achieve this is to evaluate the functions independently and concatenate their outputs. Using a generic argument, we show that this is the best we can do, if we evaluate each function only once: there is no more efficient way to combine multiple hash functions into a single function that will generically preserve collision resistance.
Xavier Boyen, Mesh Signatures, in Advances in Cryptology EUROCRYPT '07, 2007.
We define mesh signature as a modular and expressive generalization of ring signatures, which are non-repudiable anonymous signatures on behalf of a crowd. Unlike ring signatures, mesh signatures are constructed modularly from atomic signatures without requiring the private keys, and express complex access structures beyond mere disjunctions. In particular, certificate chains may be substituted for public keys that are kept off the record. Our mesh signatures are compact and unconditionally anonymous, and subsume the most efficient ring signatures with everlasting anonymity without random oracles or trusted setup authority.
Xavier Boyen and Brent Waters, Full-Domain Subgroup Hiding and Constant-Size Group Signatures, in Public Key Cryptography PKC '07, 2007. **Best paper award**
We present a very practical constant-size group signature scheme, and prove its security under reasonable assumptions in bilinear groups of composite order, in the standard model. We achieve constant size by extending a non-interactive witness-indistinguishable proof technique for knowledge of single bits to integers in the full domain, which allows us to construct a signer's proof of membership to the group, atomically, rather than bit by bit as in our earlier scheme.
Xavier Boyen, Hovav Shacham, Emily Shen, and Brent Waters, Forward-Secure Signatures with Untrusted Update, in ACM Computer and Communications Security CCS '06, 2006.
We introduce and implement forward secure signatures with untrusted update. In forward secure signatures, signing keys are frequently updated in an non-reversible manner to ensure that signatures emitted prior to a breach remain trustworthy. Unfortunately, this typically conflicts with the customary practice of encrypting signing keys with a passphrase, used to lessen the chance of exposure in the first place. To reconcile these requirements, we introduce the notion of untrusted update on the encrypted signing key itself, without decryption. We give an example implementation to demonstrate the real-world practicality of our scheme.
Xavier Boyen and Brent Waters, Compact Group Signatures Without Random Oracles, in Advances in Cryptology EUROCRYPT '06, 2006.
We construct the first practical and efficient group signature scheme that is provably secure in the standard model. Our scheme is simple and easy to implement using bilinear pairings. We prove its security without random oracles based on two mild assumptions in bilinear groups: the familiar Computational Diffie-Hellman assumption, and the Subgroup Decision assumption which is closely related to Factoring.
Dan Boneh, Xavier Boyen, and Hovav Shacham, Short Group Signatures, in Advances in Cryptology CRYPTO '04, 2004.
We construct a short and practical group signature scheme whose signatures have approximately the size of standard RSA signatures with the same security. We prove security in the random oracle model using a variant of the security definition for group signatures recently given by Bellare, Micciancio, and Warinschi. Security is based on two complexity assumptions in bilinear groups: the recently proposed Strong Diffie-Hellman (SDH) assumption, and a new assumption called the Decision Linear assumption.
Dan Boneh and Xavier Boyen, Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups, in Journal of Cryptology, online edition 2007, print edition 2008.
This is an augmented full version of the following original paper:
Short Signatures Without Random Oracles.
Among many improvements, we introduce a slightly weaker and more general version of the Strong Diffie-Hellman assumption, and give a proof of the BB short signature scheme based on this weaker assumption.
Dan Boneh and Xavier Boyen, Short Signatures Without Random Oracles, in Advances in Cryptology EUROCRYPT '04, 2004.
We describe a short signature scheme which is existentially unforgeable under a chosen message attack without using random oracles. The security of our scheme depends on a new complexity assumption we call the Strong Diffie-Hellman assumption. This assumption has similar properties to the Strong RSA assumption, which was previously used to construct signature schemes without random oracles; however the signatures generated by our scheme are much shorter and simpler.
Xavier Boyen, Yevgeniy Dodis, Jonathan Katz, Rafail Ostrovsky, and Adam Smith, Secure Remote Authentication Using Biometric Data, in Advances in Cryptology EUROCRYPT '05, 2005.
We present two efficient techniques enabling the use of biometric data to achieve mutually authenticated key exchange over an completely insecure, adversarially controlled channel. The first is based on a new notion of tamper-resistant 'robust' fuzzy extractor, which we construct in the random oracle model; the second implements an error-tolerant extension to the Katz-Ostrovsky-Yung password authenticated key exchange protocol, in the standard model.
Xavier Boyen, Reusable Cryptographic Fuzzy Extractors, in ACM Computer and Communications Security CCS '04, 2004.
This paper studies the security implications of applying a "fuzzy extractor" — a reproducible randomness extractor that operates on noisy non-uniform input — multiple times on the same secret, which is almost unavoidable when the secret is a biometric. We propose stringent security models where the adversary can query a fuzzy extractor oracle for chosen perturbations of the secret it holds. We give generic feasibility theorems based on coding and symmetry considerations, and show the security of certain constructions. We then describe a remote biometric authentication protocol where the proving party need not remember or carry anything other than her fuzzy secret.
Xavier Boyen, Miniature CCA2 PK Encryption : Tight Security Without Redundancy, in Advances in Cryptology ASIACRYPT '07, 2007.
We present a very compact public-key cryptosystem secure against adaptive chosen-ciphertext attacks, with no explicit redundancy, and with a tight random-oracle reduction to a static Diffie-Hellman hardness assumption. The novel "dual one-time pad" structure makes the system self-contained and very easy to implement.
Dan Boneh, Xavier Boyen, and Shai Halevi, Chosen Ciphertext Secure Public Key Threshold Encryption Without Random Oracles, in Topics in Cryptology CT-RSA '06, 2006.
We describe a simple non-interactive chosen ciphertext secure threshold encryption system, built from on a threshold version of the Boneh-Boyen IBE and the Canetti-Halevi-Katz IBE-to-CCA2 transformation. We flesh out the many details of the construction and its security proof.
Xavier Boyen, Qixiang Mei, and Brent Waters, Direct Chosen Ciphertext Security from Identity-Based Techniques, in ACM Computer and Communications Security CCS '05, 2005.
We describe a very simple technique that leverages the properties of certain identity-based encryption schemes to obtain chosen ciphertext security in the standard model, without resorting to external primitives such as signatures or authentication codes. Our technique works with the Boneh-Boyen and Waters IBE systems, and relies on a property of the Boneh-Boyen simulation proof shared by these systems that makes it possible for an IBE ciphertext to authenticate itself.
Xavier Boyen,
A Tapestry of Identity-Based Encryption: Practical Frameworks Compared,
in Int. J. Applied Cryptography IJACT 1(1),
2008.
This updated review of identity-based encryption algorithms first provides a classification and characterization of the various approaches, and goes on to describe in further details an optimized instantiation of each of the main paradigms, with reducibility to practice as the principal optimization parameter. The survey concludes with an evaluation of the relative strengths and weaknesses of each construction, according to a number of theoretical and practical criteria, spanning the range from abstract security reduction issues to concrete algebraic implementation concerns.
Xavier Boyen, General Ad Hoc Encryption from Exponent Inversion IBE, in Advances in Cryptology EUROCRYPT '07, 2007.
We present a classification of existing identity-based encryption schemes, and remark that the most efficient schemes to date, such as BB2 and SK, belong to a class that is not known to support any the many extensions afforded by the BB1 scheme in particular. We define the Exponent Inversion class of IBE schemes, and give an abstraction from which it is easy to build many ad hoc extensions, such as Hierarchical and Fuzzy IBE, provided that a few general conditions are met.
Xavier Boyen and Brent Waters, Anonymous Hierarchical Identity-Based Encryption (Without Random Oracles), in Advances in Cryptology CRYPTO '06, 2006.
We show that the Anonymous Hierarchical Identity-Based Encryption (A-HIBE) primitive exists and give a practical construction which we prove secure in the standard model. As a bonus, this gives us a very efficient Anonymous IBE that is the first such scheme with a proof of security in the standard model. The security of both schemes is based solely on the Decision Linear assumption in (symmetric or asymmetric) bilinear groups.
Dan Boneh, Xavier Boyen, and Eu-Jin Goh, Hierarchical Identity Based Encryption with Constant Size Ciphertext, in Advances in Cryptology EUROCRYPT '05, 2005.
We construct a Hierarchical Identity Based Encryption (HIBE) system whose ciphertext length is short and independent of the depth of the hierarchy. Security proofs are given under a new complexity assumption, called Bilinear Diffie-Hellman Exponent, which generalizes the Bilinear Diffie-Hellman Inversion assumption. We describe numerous applications of the new construction; these include a very efficient broadcast cryptosystem, a time capsule, and the most efficient forward secure public key and HIBE systems to date.
Dan Boneh and Xavier Boyen, Secure Identity Based Encryption Without Random Oracles, in Advances in Cryptology CRYPTO '04, 2004.
We present a fully secure Identity Based Encryption scheme whose proof of security does not hinge upon the random oracle heuristic. Security is based on the decisional version of the now classic Bilinear Diffie-Hellman assumption. We view our construction as an existence proof that resolves an open problem posed by Boneh and Franklin in 2001.
Dan Boneh and Xavier Boyen, Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles, in Advances in Cryptology EUROCRYPT '04, 2004.
We construct two efficient Identity Based Encryption (IBE) and Hierarchical IBE (HIBE) systems without using random oracles. We provide tight proofs of security of both systems in the slightly weaker sense of security against selective identity attacks, in which the adversary must commit ahead of time to the identity that it intends to attack. We also turn both constructions into practical and secure IBE systems in the stronger sense of security against adaptive identity attacks, in the standard model, under some security penalty.
Xavier Boyen, Multipurpose Identity-Based Signcryption: A Swiss Army Knife for Identity-Based Cryptography, in Advances in Cryptology CRYPTO '03, 2003.
A combined Identity-Based Signature/Encryption system with multiple security properties is presented. The scheme allows Alice to sign a message and encrypt it for Bob ("confidentiality") in such a way that the ciphertext does not reveal anything about their identities ("anonymity"); upon receipt, Bob is convinced that he is Alice's intended addressee ("authentication") but is unable to prove this to a third party ("unlinkability"); nevertheless, the decrypted message bears a signature by Alice that anyone can verify ("non-repudiation"). The construction is based on the Bilinear Diffie-Hellman assumption, and proved secure in the random oracle model.
Xavier Boyen, Identity-Based Signcryption, invited book chapter, to appear in (eds.) A. Dent, Y. Zheng, Practical Signcryption, Springer.
This book chapter defines the identity-based signcryption primitive, discusses its advantages and disadvantages over the regular public-key notion, and presents a formal security model that captures the multiple and sometimes contradictory security objectives that one could seek from it. A construction that meets a maximal set of security properties will provide a concrete example, and a brief survey of the literature will conclude the chapter.
Xavier Boyen, Robust and Reusable Fuzzy Extractors, invited book chapter, in (eds.) P. Tuyls, B. Skoric, T. Kevenaar, Security with Noisy Data, Springer, 2007.
This book chapter briefly introduces a couple of security notions for error-tolerant randomness extractors, or fuzzy extractors. The first notion, robustness, addresses the threat of active attacks in the context of remote biometric authentication. The second notion, reusability, concerns the possibility of reusing the same fuzzy secret in multiple instances of a protocol, which is important in biometric applications.
Xavier Boyen, A Promenade through the New Cryptography of Bilinear Pairings, invited short survey, in IEEE Information Theory Workshop ITW '06, 2006.
In this short piece, we take an informal walk through the Why, the What, and the How of bilinear pairings in cryptography. We briefly review the nature of these mathematical objects, as well as some of their recent uses in cryptographic constructions.