Our work will appear with about proceedings at Allerton 2014. This work was subsequently published in Reusable Fuzzy Extractors for Low-Entropy Distributions.
Papers
Papers
Robust Keys from Physical Unclonable Functions
Merrielle Spain, Benjamin Fuller, Kyle Ingols, and Robert Cunningham. Robust Keys from Physical Unclonable Functions. IEEE Symposium on Hardware Oriented Security and Trust, 2014.
Abstract
Weak physical unclonable functions (PUFs) can instantiate read-proof hardware tokens (Tuyls et al. 2006, CHES) where benign variation, such as changing temperature, yields a consistent key, but invasive attempts to learn the key destroy it. Previous approaches evaluate security by measuring how much an invasive attack changes the derived key (Pappu et al. 2002, Science). If some attack insufficiently changes the derived key, an expert must redesign the hardware. An unexplored alternative uses software to enhance token response to known physical attacks. Our approach draws on machine learning. We propose a variant of linear discriminant analysis (LDA), called PUF LDA, which reduces noise levels in PUF instances while enhancing changes from known attacks. We compare PUF LDA with standard techniques using an optical coating PUF and the following feature types: raw pixels, fast Fourier transform, short-time Fourier transform, and wavelets. We measure the true positive rate for valid detection at a 0% false positive rate (no mistakes on samples taken after an attack). PUF LDA improves the true positive rate from 50% on average (with a large variance across PUFs) to near 100%. While a well-designed physical process is irreplaceable, PUF LDA enables system designers to improve the PUF reliability-security tradeoff by incorporating attacks without redesigning the hardware token.
A Unified Approach to Deterministic Encryption
Our work A Unified Approach to Deterministic Encryption has been expanded and accepted into the Journal of Cryptology. This contains expanded results from the TCC version. The full version is also online
Computational Fuzzy Extractors
Benjamin Fuller, Xianrui Meng, and Leonid Reyzin. Computational Fuzzy Extractors. Asiacrypt 2013.
Abstract
Fuzzy extractors derive strong keys from noisy sources. Their security is defined information- theoretically, which limits the length of the derived key, sometimes making it too short to be useful. We ask whether it is possible to obtain longer keys by considering computational security, and show the following.
-Negative Result: Noise tolerance in fuzzy extractors is usually achieved using an information reconciliation component called a “secure sketch.” The security of this component, which directly affects the length of the resulting key, is subject to lower bounds from coding theory. We show that, even when defined computationally, secure sketches are still subject to lower bounds from coding theory. Specifically, we consider two computational relaxations of the information-theoretic security requirement of secure sketches, using conditional HILL entropy and unpredictability entropy. For both cases we show that computational secure sketches cannot outperform the best information-theoretic secure sketches in the case of high-entropy Hamming metric sources.
-Positive Result: We show that the negative result can be overcome by analyzing computational fuzzy extractors directly. Namely, we show how to build a computational fuzzy extractor whose output key length equals the entropy of the source (this is impossible in the information-theoretic setting). Our construction is based on the hardness of the Learning with Errors (LWE) problem, and is secure when the noisy source is uniform or symbol-fixing (that is, each dimension is either uniform or fixed). As part of the security proof, we show a result of independent interest, namely that the decision version of LWE is secure even when a small number of dimensions has no error.
DSKE: Dynamic Set Key Encryption
Galen Pickard, Roger Khazan, Benjamin Fuller, and Joseph Cooley. DSKE: Dynamic Set Key Encryption. LCN Workshop on Security in Communication Networks 2012.
Abstract
In this paper, we present a novel paradigm for studying the problem of group key distribution, use it to analyze existing key distribution schemes, and then present a novel scheme for group key distribution which we call “Dynamic Set Key Encryption,” or DSKE. DSKE meets the demands of a tactical environment while relying only on standard cryptographic primitives. Our “set key” paradigm allows us to focus on the underlying problem of establishing a confidential communication channel shared by a group of users, without concern for related security factors like authenticity and integrity, and without the need to consider any properties of the group beyond a list of its members. This separation of concerns is vital to our development and analysis of DSKE, and can be applied elsewhere to simplify the analyses of other group key distribution schemes.
A Unified Approach to Deterministic Encryption
Our work A Unified Approach to Deterministic Encryption is appearing at ICITS 2012 without proceedings. This work previously appeared at TCC 2012.
A Unified Approach to Deterministic Encryption
Benjamin Fuller, Adam O’Neill, and Leonid Reyzin. A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy. Theory of Cryptography 2012.
Abstract
This paper addresses deterministic public-key encryption schemes (DE), which are designed to provide meaningful security when only source of randomness in the encryption process comes from the message itself. We propose a general construction of DE that unifies prior work and gives novel schemes. Specifically, its instantiations include:
- The first construction from any trapdoor function that has sufficiently many hardcore bits.
- The first construction that provides “bounded” multi-message security (assuming lossy trapdoor functions).
The security proofs for these schemes are enabled by three tools that are of broader interest:
- A weaker and more precise sufficient condition for semantic security on a high-entropy message distribution. Namely, we show that to establish semantic security on a distribution M of messages, it suffices to establish indistinguishability for all conditional distribution M|E, where E is an event of probability at least 1/4. (Prior work required indistinguishability on all distributions of a given entropy.)
- A result about computational entropy of conditional distributions. Namely, we show that conditioning on an event E of probability p reduces the quality of computational entropy by a factor of p and its quantity by log_2 1/p.
- A generalization of leftover hash lemma to correlated distributions.
We also extend our result about computational entropy to the average case, which is useful in reasoning about leakage-resilient cryptography: leaking \lambda bits of information reduces the quality of computational entropy by a factor of 2^\lambda and its quantity by \lambda.
Computational Entropy and Information Leakage
My master’s thesis has been defended and approved by BU. It is titled Computational Entropy and Information Leakage. The majority of results (though not all) were subsequently incorporated into A Unified Approach to Deterministic Encryption which was published at TCC 2012.
ASE: Authenticated Statement Exchange
Benjamin Fuller, Roger Khazan, Joseph Cooley, and Galen Pickard. ASE: Authenticated Statement Exchange. IEEE Network Computing and Applications 2010. Best paper award.
Abstract
Applications often re-transmit the same data, such as digital certificates, during repeated communication instances. Avoiding such superfluous transmissions with caching, while complicated, may be necessary in order to operate in low-bandwidth, high-latency wireless networks or in order to reduce communication load in shared, mobile networks.
This paper presents a general framework and an accompanying software library, called “Authenticated Statement Exchange” (ASE), for helping applications implement persistent caching of application specific data. ASE supports secure caching of a number of predefined data types common to secure communication protocols and allows applications to define new data types to be handled by ASE.
ASE is applicable to many applications. The paper describes the use of ASE in one such application, secure group chat. In a recent real-use deployment, ASE was instrumental in allowing secure group chat to operate over low-bandwidth satellite links.
GROK: A Practical System for Securing Group Communications
Joseph Cooley, Roger Khazan, Benjamin Fuller, and Galen Pickard. GROK: A Practical System for Securing Group Communications. IEEE Network Computing and Applications 2010. Best paper nominee.
Abstract
We have designed and implemented a general-purpose cryptographic building block, called GROK, for securing communication among groups of entities in networks composed of high-latency, low-bandwidth, intermittently connected links. During the process, we solved a number of non-trivial system problems. This paper describes these problems and our solutions, and motivates and justifies these solutions from three viewpoints: usability, efficiency, and security. The solutions described in this paper have been tempered by securing a widely-used group-oriented application, group text chat. We implemented a prototype extension to a popular text chat client called Pidgin and evaluated it in a real-world scenario. Based on our experiences, these solutions are useful to designers of group-oriented systems specifically, and secure systems in general.