Xavier Boyen, Identity-Based Signcryption, invited chapter, to appear in (eds.) A. Dent, Y. Zheng, Practical Signcryption, Springer, 2009.
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, Generalized IBE in the Exponent-Inversion Framework, invited chapter, in (eds.) M. Joye, G. Neven, Identity-Based Encryption, IOS Press, 2008.
This book chapter studies the class of Exponent-Inversion IBE, exemplified by the BB2 and SK schemes. It demonstrates how any basic IBE scheme in this family can be extended generically into powerful extensions such as Hierarchical and Attribute-based IBE, akin to the similar extensions that already exist in the Commutative-Blinding IBE framework.
Xavier Boyen, Flexible IBE and Beyond in the Commutative-Blinding Framework, invited chapter, in (eds.) M. Joye, G. Neven, Identity-Based Encryption, IOS Press, 2008.
This book chapter studies the class of Commutative-Blinding IBE, defined by the BB1 scheme and its numerous extensions. This chapter starts by giving a comparison between the three main approaches to IBE from pairings as we currently know them, and then gives a brief overview of how the properties of this framework have been exploited to generalize the BB1 template into a broad variety of Super-IBE schemes.
Xavier Boyen, The Uber-Assumption Family – A Unified Complexity Framework for Bilinear Groups, invited paper, in International Conference on Pairing-based Cryptography PAIRING '08, 2008.
This exposition paper explains the BBG “uber-assumption” framework, whose afferent security results in the generic-group model have been used by many authors as a litmus test, to gauge the strength and plausibility of various new hardness assumptions in bilinear groups.
Xavier Boyen, New Paradigms for Password Security (abstract from the keynote lecture), invited abstract, 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.
Xavier Boyen, A Tapestry of Identity-Based Encryption: Practical Frameworks Compared, invited article, 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, Robust and Reusable Fuzzy Extractors, invited 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 paper, 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.
Xavier Boyen,
HPAKE : Password Authentication Secure Against Cross-Site User Impersonation,
in Cryptology And Network Security CANS '09,
2009.
How should we authenticate ourselves on the Internet? We propose an asymmetric password-based remote mutual authentication protocol for use between a human client and a machine server. On the client side, it requires no storage other than a small password, and it is robust to the reuse of the same password with multiple and potentially malicious servers. In practice, our proposal offers a much more secure alternative to typical password system designs, as it explicitly addresses the ubiquitous threat of “cross-site impersonation” that arises when someone chooses to reuse a common password with more than one entity.
Xavier Boyen, Hidden Credential Retrieval from a Reusable Password, in ACM Symposium on InformAtion, Computer & Communication Security ASIACCS '09, 2009.
We take another look at the common problem of how to store and retrieve one's online credentials, using only a human-memorable password, and making the weakest possible trust assumption on the remote repository. After analyzing the various shortcomings of several naive solutions, we propose a formal security model that captures the peculiar threats faced by the user in this endeavor. Based on this model, we show how some very ancient protocols such as unique blind signatures provide an elegant and practical solution for our task, and quantify how much of a challenge outsider and insider adversaries will be faced when trying to crack the secret. To the best of our knowledge, this paper offers the first formal study of minimally trusted credential repositories for roaming users, and has immediate applications for ad-hoc single-sign-on internet authentication.
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.
Michel Abdalla, Xavier Boyen, Céline Chevalier, and David Pointcheval, Distributed Public-Key Cryptography from Weak Secrets, in Public Key Cryptography PKC '09, 2009.
Human-memorable passwords and public-key cryptography generally do not mix: this is because the public key, necessarily available to the adversary, provides an easy way for such adversary to conduct an offline dictionary attack against the password. What if, instead, the private key were created from not one but many passwords held by different users? In this paper, we show how to do this in a secure manner, using distributed protocols that in particular never require the users to share their passwords with anyone else, even the other participants. We start by defining general functionalities for key-pair generation and private-key-based computations in the UC model, and then show how to realize them by giving distributed password-based protocols for the ElGamal cryptosystem. Our protocols run over adversarially controlled channels, are reasonably efficient given the nature of the problem, and generalize easily to other and more complex tasks, such as distributed signature and identity-based encryption most notably.
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, 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.
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 and Cécile Delerablée, Expressive Subgroup Signatures, in Security and Cryptography for Networks SCN '08, 2008.
We define and construct a collective signature that blends the revocable anonymity of group signatures with the expressiveness of mesh signatures. These new signatures retain the user enrollment and revocable anonymity properties of group signatures, but allow any subgroup of users collectively to issue signatures, while hiding or revealing precisely how they derive the capacity to do so on behalf of the group.
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 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.
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, 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, 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.
Shweta Agrawal and Xavier Boyen,
Identity-Based Encryption from Lattices in the Standard Model,
Manuscript,
2009.
We construct the first provably secure identity-based encryption system from lattices in the standard model.