Title: Error Correction in the Bounded Storage Model

We initiate a study of Maurer's bounded storage model (J. Cryptology, 1992) in presence of transmission errors (and perhaps other types of errors) that cause different parties to have inconsistent views of the public random source. Such errors seem inevitable in any implementation of the model. All previous schemes and protocols in the model assume a perfectly consistent view of the public source from all parties, and do not function correctly in presence of errors.

In this talk, we provide a general paradigm to construct secure and error-resilient private-key encryption and message authentication schemes in the bounded storage model that tolerate a _constant_ fraction of errors, and meanwhile attain the near optimal parameters of Vadhan's construction (J. Cryptology, 2004) in the errorless case.

Title: A Cryptographic Model for Access Control

The main objective of this report is to bridge the different notions of security that are used in common cryptographic models and in common models of access control. Very roughly, cryptographic models usually assume that the communication channels are adversarially controlled, but some of the participants can be trusted to honestly follow the protocol. The notion of security in such models is meant to protect these honest participants, and it is typically assumed that the other participants are under full adversarial control.

In contrast, common access-control models have very few participants that can be trusted to follow the protocol (if any), but it is assumed that "the system" has control over the communication channels between participants. An important security notion in such models is \emph{confinement}, whereby even misbehaving participants cannot leak their secrets across some pre-defined boundaries.

In this work we devise a cryptographic model for access control. This model refines common cryptographic models by accounting for the communication channels between the (non-honest) participants and the adversary, thereby making it possible to capture the notion of confinement. We also show a simple cryptographic protocol and prove that it realizes that model. The protocol is a small modification of the capability-based protocol underlying the proposed standard for object stores.

(Joint work with Paul Karger and Dalit Naor.)

Title: Fuzzy Commitment

I will talk briefly about the application to biometric data of a cryptographic primitive called "fuzzy commitment." Fuzzy commitment is effectively a form of cryptographic hashing that is tolerant of the errors inherent in biometric authentication systems. I will devote much of the talk to an explanation of why good cryptographic treatment of biometric data may be important, particularly in light of the imminent deployment of biometrics-enabled passports and identity cards by national governments. I'll also discuss an ongoing effort at RSA Labs to apply fuzzy commitment to iriscodes in particular.

Title: Randomness Extraction and Key Derivation Using Common Pseudorandom Modes

A common cryptographic task is to extract pseudorandom bits from sources that only contain partially-secret partially-random bits. Such is the case when deriving a strong cryptographic key out of a weak source of randomness (e.g., sampling system events, using an imperfect random number generator, etc) or when deriving a key from a Diffie-Hellman value. Well-known constructions of such extractors exist in the literature, some of which make potentially practical solutions to the problem (for example, constructions based on universal hashing). Yet, these extractors are seldom used in practice; instead practitioners prefer to use readily-available unkeyed cryptographic hash functions, such as SHA-1, for the extraction task.

In the design of the IPsec Key Exchange (IKE) protocol we introduced an extraction mechanism based on practical pseudorandom modes (CBC-MAC and HMAC), where the pseudorandom function is keyed with a random BUT KNOWN value. In this work we study the analytical properties of such extractors, and argue that they constitute a better analytical and practical choice for extraction than the current practice of using unkeyed hash functions.

Based on joint work with Y. Dodis, R. Gennaro, J. Hastad, and T. Rabin.

Title: Cryptographic Mechanisms to Secure Routing Protocols

Current routing protocols are highly susceptible to attack, as even misconfigurations can lead to network-wide connectivity outages. We will discuss attacks against Internet and wireless ad hoc network routing protocols, and discuss cryptographic techniques to defend against these attacks.

Title: Smart Theory Meets Smartcard Practice

We'll discuss several theoretical cryptographic problems coming from the specific practical constraints associated to smartcards (memories, computing power, communications). In particular,

- use of unsecure memory with secure processor,

- outside-aided cryptographic computations,

- trusted downloading of programs,

- remote verification of data integrity inside the smartcard.

Title: What's the Worst That Could Happen?

Communications security systems depend completely on the security of the underlying cryptographic primitives on which they are built. However, these primitives are always imperfect, sometimes badly flawed and occasionally completely broken. In this talk, we will examine the impact on important communication security protocols if attacks--even partial ones--were to be found on our core cryptographic primitives.

Title: Recent Progress in Anonymous Communication

We summarize three recent results in anonymous communication technologies.

1. A technique, called "fragility", that discourages mix administrators from selectively disclosing input-to-output message correspondences (e.g., for profit), presuming that the mix administrators are motivated to protect the privacy of some communications through the mix (e.g., their own).
2. A simulation-based analysis of timing attacks on mix-based systems, and new techniques for better defending against them.
3. A new method for implementing an anonymous message service using a technique called "private push and pull". This technique permits the oblivious insertion of labeled messages into a distributed database, and the oblivious retrieval of messages that match a provided keyword.

Title: Cryptographic Hashing: Blockcipher-based Constructions Revisited

Thanks largely to recent attacks on MD5, SHA-0 and the like, cryptographic hash functions are now attracting a lot of attention. Now seems like an appropriate time to revisit these objects and remind ourselves of what they are, what they are supposed to do for us, and how we go about constructing them. We will do this, giving special attention to blockcipher-based hash functions, their security models and performance.

Title: Efficient Privacy-preserving Information Sharing: Set Intersection and Threshold Set Intersection

In this talk, we will present our new approach on privately computing set intersection and threshold set intersections, and their real-world applications. Our approach has much lower communication complexity in both honest-but-curious case and the malicious case than previous work. Our threshold set intersection protocol is the first one that does not require the expensive secure circuit computation.

Title: Breakthrough-Resistant Cryptography

The security of our most common cryptographic protocols rests on the security of a very small set of atomic primitives. In the face of new cryptanalytic breakthroughs, each of these fundamental building blocks presents a single point of failure with the potential to undermine the security of entire systems. In this talk, we will present compositions and protocols that remain secure even if some of their underlying primitives fail.

Title: The Risks of Electronic Voting

Recent election problems have sparked great interest in managing the election process through the use of electronic voting systems. While computer scientists, for the most part, have been warning of the perils of such action, vendors have forged ahead with their products, claiming increased security and reliability. Many municipalities have adopted electronic systems, and the number of deployed systems is rising. For these new computerized voting systems, neither source code nor the results of any third-party certification analyses have been available for the general population to study, because vendors claim that secrecy is a necessary requirement to keep their systems secure. Recently, however, the source code for a voting system from Diebold, a major manufacturer, appeared on the Internet. Diebold currently has around 30% of the market for electronic voting systems in the U.S.

This unique opportunity for independent scientific analysis of voting system source code demonstrates the fallacy of the closed-source argument for such a critical system. Our analysis shows that this voting system is far below even the most minimal security standards applicable in other contexts. We highlight several issues including unauthorized privilege escalation, incorrect use of cryptography, vulnerabilities to network threats, and poor software development processes. For example, common voters, without any insider privileges, can cast unlimited votes without being detected by any mechanisms within the voting terminal. Furthermore, we show that even the most serious of our outsider attacks could have been discovered without the source code. In the face of such attacks, the usual worries about insider threats are not the only concerns; outsiders can do the damage. That said, we demonstrate that the insider threat is also quite considerable. We conclude that, as a society, we must carefully consider the risks inherent in electronic voting, as it places our very democracy at risk.

Title: Privacy-Preserving Bayesian Network Structure Computation on Distributed Heterogeneous Data

As more and more activities are carried out using computers and computer networks, the amount of potentially sensitive data stored by business, governments, and other parties increases. Different parties may wish to benefit from cooperative use of their data, but privacy regulations and other privacy concerns may prevent the parties from sharing their data. Privacy-preserving data mining provides a solution by creating distributed data mining algorithms in which the underlying data is not revealed. We present a privacy-preserving protocol for a particular data mining task: learning the Bayesian network structure for distributed heterogeneous data. In this setting, two parties owning confidential databases wish to learn the structure of a Bayesian network on the combination of their databases without revealing anything about their data to each other. We give an efficient and privacy-preserving version of the K2 algorithm to construct the structure of a Bayesian network for the parties' joint data.

(Joint work with Zhiqiang Yang.)