Conference Papers

Possibility of continuous source fuzzy extractors

Lowen and I just received word of acceptance of our recent work to ISIT.  This papers asks whether you can build a universal fuzzy extractor for all high fuzzy min-entropy distributions.  That is, can we have one construction that always just works.  Unfortunately, the answer is negative.  It is possible to artificially construct families of distributions that are impossible to simultaneously secure.  This paper shares a lot of techniques with prior work of myself, Reyzin, and Smith.  Excited to talk about these techniques more with the information theory community!

DOCSDN: Dynamic and Optimal Configuration of Software-Defined Networks

New work on finding good network configurations with Tim, Devon, and Laurent.  This will appear this year at ACISP.

Abstract—Networks are designed with functionality, security, performance, and cost in mind. Tools exist to check or optimize individual properties of a network. These properties may conflict, so it is not always possible to run these tools in series to find a configuration that meets all requirements. This leads to network administrators manually searching for a configuration.

This need not be the case. In this paper, we introduce a layered framework for optimizing network configuration for functional and security requirements. Our framework is able to output configurations that meet reachability, bandwidth, and risk requirements. Each layer of our framework optimizes over a single property. A lower layer can constrain the search problem of a higher layer allowing the framework to converge on a joint solution.

Our approach has the most promise for software-defined networks which can easily reconfigure their logical configuration. Our approach is validated with experiments over the fat tree topology, which is commonly used in data center networks. Search terminates in between 1-5 minutes in experiments. Thus, our solution can propose new configurations for short term events such as defending against a focused network attack.

Iris Segmentation using CNNs

Sohaib (who’s awesome!) just gave his first presentation on performing iris segmentation using fully convolutional neural nets. The paper was published at AMV 2018 which is a workshop at ACCV.

AbstractThe extraction of consistent and identifiable features from an image of the human iris is known as iris recognition. Identifying which pixels belong to the iris, known as segmentation, is the first stage of iris recognition. Errors in segmentation propagate to later stages. Current segmentation approaches are tuned to specific environments. We propose using a convolution neural network for iris segmentation. Our algorithm is accurate when trained in a single environment and tested in multiple environments. Our network builds on the Mask R-CNN framework (He et al., ICCV 2017). Our approach segments faster than previous approaches including the Mask R-CNN network. Our network is accurate when trained on a single environment and tested with a different sensors (either visible light or near-infrared). Its accuracy degrades when trained with a visible light sensor and tested with a near-infrared sensor (and vice versa). A small amount of retraining of the visible light model (using a few samples from a near-infrared dataset) yields a tuned network accurate in both settings. For training and testing, this work uses the Casia v4 Interval, Notre Dame 0405, Ubiris v2, and IITD datasets.

Environmentally Keyed Malware

Our paper (with Jeremy Blackthorne, Ben Kaiser, and Bulent Yener) on how malware authenticates was  published at Latincrypt 2017.  Abstract below:

Abstract: Malware needs to execute on a target machine while simultaneously keeping its payload confidential from a malware analyst. Standard encryption can be used to ensure the confidentiality, but it does not address the problem of hiding the key. Any analyst can find the decryption key if it is stored in the malware or derived in plain view.

One approach is to derive the key from a part of the environment which changes when the analyst is present. Such malware derives a key from the environment and encrypts its true functionality under this key.

In this paper, we present a formal framework for environmental authentication. We formalize the interaction between malware and analyst in three settings: 1) blind: in which the analyst does not have access to the target environment, 2) basic: where the analyst can load a single analysis toolkit on an effected target, and 3) resettable: where the analyst can create multiple copies of an infected environment. We show necessary and sufficient conditions for malware security in the blind and basic games and show that even under mild conditions, the analyst can always win in the resettable scenario.

Catching MPC Cheaters

Our paper (with Rob Cunningham and Sophia Yakoubov) on augmenting security of MPC will be published at ICITS 2017.  Abstract below:

Abstract: Secure multi-party computation (MPC) protocols do not completely prevent malicious parties from cheating and disrupting the computation. A coalition of malicious parties can repeatedly cause the computation to abort or provide an input that does not correspond to reality. We augment MPC with three new properties to discourage cheating. First is a strengthening of identifiable abort, called completely identifiable abort, where all parties who do not follow the protocol will be identified as cheaters by each honest party, even if there are more cheaters than honest parties. The second is completely identifiable auditability, which means that a third party can, given the computation output and its additive share decomposition, determine whether the computation was performed correctly (and who cheated if it was not) by looking at a transcript of the computation.  The third is openability, which means that a distinguished coalition of parties can recover the MPC inputs in the extreme setting when the parties are discovered to have lied about their inputs (e.g. by a real-world event contradicting the output of the MPC).

We construct the first (efficient) MPC protocol achieving these properties.  Our scheme is built on the SPDZ protocol (Damgard et al., Crypto 2012), which leverages an offline (computation-independent) pre-processing phase to speed up the online computation. Our protocol is optimistic: it has the same communication and computation complexity in the online phase as SPDZ when no parties cheat. If cheating does occur, each honest party performs only local computation to identify cheaters.

Our main technical tool is a new locally identifiable secret sharing scheme (as defined by Ishai, Ostrovsky, and Zikas (TCC 2012)) which we call commitment enhanced secret sharing, or CESS. Each CESS share contains an additive share (as in SPDZ), and additionally includes linearly homomorphic commitments to every additive share. Each CESS share also contains the decommitment value for the commitment to the corresponding additive share. These commitments enable local identification during reconstruction; by the binding property of the commitment scheme, no party should be able to convince any other party of the validity of an altered additive share.  CESS enables MPC with completely identifiable abort; all parties whose claimed output shares do not match their output share commitments are identified as cheaters.

The work of Baum, Damgard, and Orlandi (SCN 2014) introduces the concept of auditability, which allows a third party to verify that the computation was executed correctly, but not to identify the cheaters if it was not.  We enable the third party to identify the cheaters by augmenting the scheme of Baum, Damg{\aa}rd, and Orlandi with CESS. We add openability through the use of verifiable encryption and specialized zero-knowledge proofs.

SoK: Cryptographically Protected Database Search

Excited to announce that our paper on protected database search will be appear at 2017 IEEE Security and Privacy.

Joint work with Mayank Varia, Arkady Yerukhimovich, Emily Shen, Ariel Hamlin, Vijay Gadepally, Richard Shay, John, Darby Mitchell, and Robert K. Cunningham


Protected database search systems cryptographically isolate the roles of reading from, writing to, and administering the database. This separation limits unnecessary administrator access and protects data in the case of system breaches. Since protected search was introduced in 2000, the area has grown rapidly; systems are offered by academia, start-ups, and established companies.

However, there is no best protected search system or set of techniques. Design of such systems is a balancing act between security, functionality, performance, and usability. This challenge is made more difficult by ongoing database specialization, as some users will want the functionality of SQL, NoSQL, or NewSQL databases. This database evolution will continue, and the protected search community should be able to quickly provide functionality consistent with newly invented databases.

At the same time, the community must accurately and clearly characterize the tradeoffs between different approaches. To address these challenges, we provide the following contributions:

1) An identification of the important primitive operations across database paradigms. We find there are a small number of \emph{base} operations that can be used and combined to support a large number of database paradigms.

2) An evaluation of the current state of protected search systems in implementing these base operations. This evaluation describes the main approaches and tradeoffs for each base operation. Furthermore, it puts protected search in the context of unprotected search, identifying key gaps in functionality.

3) An analysis of attacks against protected search for different base queries.

4) A roadmap and tools for transforming a protected search system into a protected database, including an open-source performance evaluation platform and initial user opinions of protected search.

Pseudoentropic Isometries

I was excited to join the paper Pseudoentropic Isometries: A New framework for fuzzy extractor reusability by Quentin Alamélou, Paul-Edmond Berthier, Chloe Cachet, Stéphane Cauchie, Benjamin Fuller, Philippe Gaborit, and Sailesh Simhadri.  This paper describes how to use the random oracle to build a reusable fuzzy extractor that corrects a linear fraction of errors.  Presented at AsiaCCS 2018.  The abstract is below.


Fuzzy extractors (Dodis et al., Eurocrypt 2004) turn a noisy secret into a stable, uniformly distributed key. Reusable fuzzy extractors remain secure when multiple keys are produced from a single noisy secret (Boyen, CCS 2004). Boyen proved that any information-theoretically secure reusable fuzzy extractor is subject to strong limitations. Simoens et al. (IEEE S&P, 2009) then showed deployed constructions suffer severe security breaks when reused. Canetti et al. (Eurocrypt 2016) proposed using computational security to sidestep this problem. They constructed a computationally secure reusable fuzzy extractor for the Hamming metric that corrects a sublinear fraction of errors.

We introduce a generic approach to constructing reusable fuzzy extractors. We define a new primitive called a reusable pseudoentropic isometry that projects an input metric space to an output metric space. This projection preserves distance and entropy even if the same input is mapped to multiple output metric spaces. A reusable pseudoentropy isometry yields a reusable fuzzy extractor by 1) randomizing the noisy secret using the isometry and 2) applying a traditional fuzzy extractor to derive a secret key.

We propose reusable pseudoentropic isometries for the set difference and Hamming metrics. The set difference construction is built from composable digital lockers (Canetti and Dakdouk, Eurocrypt 2008) yielding the first reusable fuzzy extractor that corrects a linear fraction of errors. For the Hamming metric, we show that the second construction of Canetti et al. (Eurocrypt 2016) can be seen as an instantiation of our framework. In both cases, the pseudoentropic isometry’s reusability requires noisy secrets distributions to have entropy in each symbol of the alphabet.

Lastly, we implement our set difference solution and describe two use cases.

When are Fuzzy Extractors Possible?

Benjamin Fuller, Leonid Reyzin, and Adam Smith. When are Fuzzy Extractors Possible? Asiacrypt 2016.


Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a high-entropy secret into the same uniformly distributed key. A minimum condition for the security of the key is the hardness of guessing a value that is similar to the secret, because the fuzzy extractor converts such a guess to the key.

We define fuzzy min-entropy to quantify this property of a noisy source of secrets. Fuzzy min-entropy measures the success of the adversary when provided with only the functionality of the fuzzy extractor, that is, the \emph{ideal} security possible from a noisy distribution. High fuzzy min-entropy is necessary for the existence of a fuzzy extractor.

We ask: is high fuzzy min-entropy a sufficient condition for key extraction from noisy sources? If only computational security is required, recent progress on program obfuscation gives evidence that fuzzy min-entropy is indeed sufficient. In contrast, information-theoretic fuzzy extractors are not known for many practically relevant sources of high fuzzy min-entropy.

In this paper, we show that fuzzy min-entropy is also sufficient for information-theoretically secure fuzzy extraction. For every source distribution W for which security is possible we give a secure fuzzy extractor.

Our construction relies on the fuzzy extractor knowing the precise distribution of the source W. A more ambitious goal is to design a single extractor that works for all possible sources. We show that this more ambitious goal is impossible: we give a family of sources with high fuzzy min-entropy for which no single fuzzy extractor is secure. This result emphasizes the importance of accurate models of high entropy sources.

Reusable Fuzzy Extractors for Low-Entropy Distributions

Ran Canetti, Benjamin Fuller, Omer Paneth, Leonid Reyzin, and Adam Smith.  Reusable Fuzzy Extractors for Low-Entropy Distributions. Eurocrypt 2016.

Previous titles were “Reusable Fuzzy Extractors via Digital Lockers” and “Key Derivation From Noisy Sources With More Errors Than Entropy.”


Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a secret into the same uniformly distributed key. To eliminate noise, they require an initial enrollment phase that takes the first noisy reading of the secret and produces a nonsecret helper string to be used in subsequent readings. Reusable fuzzy extractors (Boyen, CCS 2004) remain secure even when this initial enrollment phase is repeated multiple times with noisy versions of the same secret, producing multiple helper strings (for example, when a single person’s biometric is enrolled with multiple unrelated organizations).

We construct the first reusable fuzzy extractor that makes no assumptions about how multiple readings of the source are correlated (the only prior construction assumed a very specific, unrealistic class of correlations). The extractor works for binary strings with Hamming noise; it achieves computational security under assumptions on the security of hash functions or in the random oracle model. It is simple and efficient and tolerates near-linear error rates.

Our reusable extractor is secure for source distributions of linear min-entropy rate. The construction is also secure for sources with much lower entropy rates–lower than those supported by prior (nonreusable) constructions–assuming that the distribution has some additional structure, namely, that random subsequences of the source have sufficient minentropy. We show that such structural assumptions are necessary to support low entropy rates.

We then explore further how different structural properties of a noisy source can be used to construct fuzzy extractors when the error rates are high, providing a computationally secure and an information-theoretically secure construction for large-alphabet sources.