This page presents succinct summaries of most of my academic papers, grouped by theme. Links in the publication titles provide access to dedicated pages with the latest version of each work.

See also my chronological roster — or go back to my homepage.

Themes

1.  Cryptology, Security, and Privacy

*   Conference Proceedings

Xavier Boyen and Xiaofeng Chen, Proceedings of the 5th International Conference on Provable Security — PROVSEC 2011, LNCS 6980, Xi'An, China, 2011.

1a.  Lattice-based Cryptography

— by invitation —

Xavier Boyen, Expressive Encryption Systems from Lattices (abstract from the invited lecture), invited paper, in Cryptography and Network Security - CANS '11, 2011.

We review and draw a unifying picture of the several approaches to expressive encryption systems that have recently appeared from lattices, and explore the innovative techniques that underpin them.

Provably Secure Schemes

  Xavier Boyen, Attribute-Based Functional Encryption on Lattices, in Theory of Cryptography Conference - TCC '13, 2013. (To appear)

We introduce a broad lattice manipulation technique for expressive cryptography, and use it to realize functional encryption for access structures from post-quantum hardness assumptions. Specifically, we build an efficient key-policy attribute-based encryption scheme, and prove its security in the selective sense from learning-with-errors intractability in the standard model.

Shweta Agrawal, Xavier Boyen, Vinod Vaikuntanathan, Panagiotis Voulgaris, and Hoeteck Wee, Functional Encryption for Threshold Function (or, Fuzzy IBE) from Lattices, in Public Key Cryptography - PKC '12, 2012.

We construct “Fuzzy” Identity Based Encryption from the hardness of the standard Learning With Errors (LWE) problem in the standard model, thereby providing one of the first examples of advanced-functionality cryptosystem from lattices that goes “beyond IBE”. Our construction is made possible by observing how to realize, in the peculiar world of lattices, certain special properties that secret sharing schemes need to satisfy in order to discriminate close but imperfect matches between key and ciphertext.

Shweta Agrawal, Dan Boneh, and Xavier Boyen, Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE, in Advances in Cryptology - CRYPTO '10, 2010.

We construct an alternative basis delegation mechanism for Ajtai's hard lattices, that works not by considering larger and larger superlattices of increasing dimensions, but by applying slightly lossy transformations on the given lattice “in place” i.e. without changing its dimension. Armed with this new tool, we construct an entirely new kind of hierarchical identity-based encryption system in the standard model. Its distinguishing feature is that the ciphertext dimension does not increase as one walks down the hierarchy.

Xavier Boyen, Lattice Mixing and Vanishing Trapdoors – A Framework for Fully Secure Short Signatures and More, in Public Key Cryptography - PKC '10, 2010.

We extend the recent Agrawal-Boneh-Boyen identity-based mechanism from selective to adaptive security, in the standard model. Our approach is a distant relative of that of Waters in bilinear groups. However it avoids a number of earlier difficulties by exploiting some elegant mathematical features specific to lattices. Namely, we observe the existence of naturally “nice” distributions that are propitious to building efficient adaptive simulators. As a direct application, we offer the most efficient (to date) fully secure signature scheme based on a classic assumption in the standard model, and make connections to IBE.

Shweta Agrawal, Dan Boneh, and Xavier Boyen, Efficient Lattice (H)IBE in the Standard Model, in Advances in Cryptology - EUROCRYPT '10, 2010.

By contrast to the earlier “bit-by-bit” identity-based key extraction mechanism, we propose an “all-at-once” construction that is vastly more efficient in almost every respect. From it we build a selectively secure IBE scheme that is almost as compact as the best known random-oracle scheme, but in the standard model. We further make the case that our basic IBE construction is open to many extensions: based on a couple of concurrent results, we notably describe (1) how to implement efficient hierarchies and (2) how to prove full adaptive security.

Shweta Agrawal and Xavier Boyen, Identity-Based Encryption from Lattices in the Standard Model, 2009.

We construct the first (though not only) provably secure identity-based encryption system from lattices in the standard model. It is based on a very straightforward though quite inefficient bit-by-bit parsing of the recipient identity. At least two similar constructions have appeared independently and concurrently to ours.

1b.  Pairing-based Cryptography

— by invitation —

Xavier Boyen, Identity-Based Signcryption, invited chapter, in (eds.) A. Dent, Y. Zheng, Practical Signcryption, Springer, 2010.

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, A Tapestry of Identity-Based Encryption: Practical Frameworks Compared, invited article, in Int. J. Applied Cryptography, inaugural issue, 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, 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.

Identifier-Based Crypto

Dan Boneh and Xavier Boyen, Efficient Selective Identity-Based Encryption Without Random Oracles, in Journal of Cryptology, online edition 2010, print edition 2011.

This is an augmented full version of the following original paper:
 *    Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles.
The present version has been significantly updated, and the two main schemes (now called BB1 and BB2, following usage) have been generalized in several ways. We show among other things that the native schemes can be used in full adaptive-security mode, with a simple parameter tweak, while remaining practical.

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.

Public-Key Encryption

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.

Anonymity in Groups

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 – How to Leak a Secret with Unwitting and Unwilling Participants, 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.

Practical Signatures

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.

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

Basic Primitives

Xavier Boyen and Brent Waters, Shrinking the Keys of Discrete-Log-Type Lossy Trapdoor Functions, in Applied Cryptography ans Network Security - ACNS '10, 2010.

We propose a compression technique that significantly reduces the size of the public key in the Peikert-Waters lossy trapdoor construction. Our technique applies to the discrete-log realization of the lossy trapdoor, which we must instantiate in a bilinear group in order to carry out the compression. The final key size is reduced from cubic to quadratic in the security parameter, giving us the most compact lossy trapdoor of the discrete-log type (though factoring-based ones are even more compact).

1c.  Network-oriented Security

Network Signatures

Shweta Agrawal, Dan Boneh, Xavier Boyen, and David Mandell Freeman, Preventing Pollution Attacks in Multi-source Network Coding, in Public Key Cryptography - PKC '10, 2010.

Network coding is a method for achieving channel capacity in networks. The key idea is to allow network routers to linearly mix packets as they traverse the network so that recipients receive linear combinations of packets. Network coded systems are vulnerable to pollution attacks where a single malicious node floods the network with bad packets and prevents the receiver from decoding correctly. Cryptographic defenses to these problems are based on homomorphic signatures and MACs. These proposals, however, cannot handle mixing of packets from multiple sources, which is needed to achieve the full benefits of network coding. In this paper we address integrity of multi-source mixing. We propose a security model for this setting and provide a generic construction.

1d.  Human-oriented Privacy

— by invitation —

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.

Distributed Public-Key

Xavier Boyen, Céline Chevalier, Georg Fuchsbauer, and David Pointcheval, Strong Cryptography from Weak Secrets – Building Efficient PKE and IBE from Distributed Passwords, in Progress in Cryptology - AFRICACRYPT '10, 2010.

In this paper we revisit the previously introduced notion of distributed public-key cryptography from weak secrets (such as independent short passwords held by a small group of friends). Whereas the earlier result was mostly definitional with a proof of concept that relied on certain generic and very inefficient simulation-sound zero-knowledge proof systems, here we show how to construct such systems very efficiently from pairings, and based only on the linear assumption in the standard model. Our solution applies to a large class of ElGamal-type cryptosystems in bilinear groups. In particular, we make the efficient and highly extensible Boneh-Boyen identity-based encryption framework “password-based”: the central authority becomes virtual, and its master key is replaced by a distributed collection of weak secrets.

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.

Stand-Alone Passwords

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.

Real-Life Solutions

Hristo Bojinov, Dan Boneh, Xavier Boyen, and Elie Bursztein, Kamouflage: Loss-Resistant Password Management, in Computer Security - ESORICS '10, 2010.

We introduce Kamouflage: a new architecture for building theft-resistant password managers. Generally, a master password is used to encrypt a multitude of user credentials. With Kamouflage, we attempt to make even incorrect decryptions look like plausible credentials. An attacker who steals a laptop or cell phone with a Kamouflage-based password manager is thus forced to carry out a considerable amount of online trials before obtaining any user credentials. We implemented our proposal as a replacement for the built-in Firefox password manager, and provide performance measurements and the results from experiments with large real-world password sets to evaluate the feasibility and effectiveness of our approach. Kamouflage is well suited to become a standard architecture for password managers on mobile devices.

1e.  Theory of Security

— by invitation —

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.

Hash Combiners

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.

Noise and Biometrics

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.

1f.  Financial Cryptography

Online Currency

Simon Barber, Xavier Boyen, Elaine Shi, and Ersin Uzun, Bitter to Better : How to Make Bitcoin a Better Currency, in Financial Cryptography - FC '12, 2012.

We take a critical look at Bitcoin, an innovative decentralized online currency and transaction scheme. Among other contributions, we identify a number of latent security threats, and show how to leverage the transactional contract formation principles of Bitcoin to realize a peer-to-peer exchange whereby true transaction anonymity can be achieved.

2.  Artificial Intelligence

Ph.D. Thesis

Xavier Boyen, Inference and Learning in Complex Stochastic Processes, Doctoral Dissertation, Computer Science Department, Stanford University, 229 pages, 2002. (Published in 2003.)

This thesis expands upon results originally published in the following articles:
 *    Tractable Inference for Complex Stochastic Processes,
 *    Approximate Learning of Dynamic Models,
 *    Exploiting the Architecture of Dynamic Systems,
 *    Discovering the Hidden Structure of Complex Dynamic Systems.
A concise abstract is available.

Machine Learning

Xavier Boyen, Nir Friedman, and Daphne Koller, Discovering the Hidden Structure of Complex Dynamic Systems, in Uncertainty in Artificial Intelligence - UAI '99, 1999.

We construct algorithms for learning the parameters and the structure of complex stochastic processes from raw data sequences. Our method endows the Structural Expectation-Maximization (SEM) statistical learning algorithm with the ability to recognize long-range correlations in a temporal data stream, and create hidden state variables in order to account for such correlations. The knowledge it acquires is neatly synthesized into a Dynamic Bayesian Network (DBN) graphical model that most likely explains the learning data.

Xavier Boyen and Daphne Koller, Approximate Learning of Dynamic Models, in Advances in Neural Information Processing Systems - NIPS '98, 1998.

We show how to greatly improve the efficiency of learning partially observable structured stochastic processes with hardly any impact on quality, thanks to two approximations with theoretical justifications. The first approximation allows the inference engine found at the core of most partial observability learners to operate on much larger models. The second approximation greatly speeds up the collection of statistics over long time series by focusing on short time windows centered on each instant of interest. We justify and demonstrate these ideas on the Forward-Backward algorithm based on Expectation-Minimization for learning the parameters of DBNs with a given structure, both in offline and online settings.

Probabilistic Reasoning

Xavier Boyen and Daphne Koller, Exploiting the Architecture of Dynamic Systems, in National Conference on Artificial Intelligence - AAAI '99, 1999.

We define and analyze the notions of weak and sparse interaction between the subprocesses in a structured multivariate stochastic process. We show how to exploit these notions in order to identify good approximations for the approximate filtering algorithm given by Boyen and Koller for discrete-time complex processes reprensented as Dynamic Bayesian Networks.

Xavier Boyen and Daphne Koller, Tractable Inference for Complex Stochastic Processes, in Uncertainty in Artificial Intelligence - UAI '98, 1998.

We present the first efficient and provably accurate approximate filtering algorithm for structured multivariate stochastic processes that evolve over time. By using a lossy representation focused on the information-rich regions of the instantaneous state distribution, we obtain an algorithm that remains usable in cases where it would be infeasible to reprensent the distribution exactly. We give an information-theoretic proof that the approximation errors decay exponentially with the passage of time, resulting in a total expected error that remains bounded by a fixed constant at all times. The error bound is highly dependent on the amount of process structure that the approximate inference algorithm is allowed to exploit.

3.  Miscellany

Computational Geometry

Xavier Boyen, Nina Mishra, and Liadan O'Callaghan, Towards the Visualization of Overlapping Sets, in DIMACS Computational Geometry Workshop, 2002.

We briefly define and study some issues regarding the geometry of graphs arising in the context of creating visual representations of overlapping sets of elements.

Note: non-academic writings such as standards and patents are not listed here.

Unless indicated otherwise, these pages and documents are Copyright © Xavier Boyen; all rights reserved in all countries.
Back to Xavier's homepage