Author: Ben Fuller

DSKE: Dynamic Set Key Encryption

Posted on by

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

Posted on by

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.

ASE: Authenticated Statement Exchange

Posted on by

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

Posted on by

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.