Cryptography Laboratory at Columbia University

Strengthening Cryptography by Reducing Assumptions about the Adversary
The project challenges the traditional cryptographic assumptions about the limitations of the adversary, such as the assumption that the adversary has no access whatsoever to the legitimate parties' secret keys. The project will investigate the strongest existing models, design new models, develop protocols, and explore the limits of what is possible to achieve, for several types of strong and realistic attacks, including chosen ciphertext attack, key tampering attacks, and key exposure attacks.
Privacy-preserving Learning:
Mitsubishi Electric Research laboratories (MERL).
Cross-Leveraging Cryptography and Learning Theory
The project proposes a detailed study of the connections between cryptography and learning. Very roughly speaking, cryptography is about manipulating and encoding information so that it is difficult to reconstruct the initial information, while learning theory is about efficiently extracting information from some unknown object. This duality means that ideas and results from each area can potentially be leveraged to make progress in the other area. The first main goal of the project is to obtain new cryptographic results based on the presumed hardness of various problems in computational learning theory. Work along these lines will include constructing and applying cryptographic primitives such as public-key cryptosystems and pseudorandom generators from learning problems that are widely believed to be hard, and exploring the average-case learnability of well-studied concept classes such as decision trees and DNF formulas. The second main goal of the project is to obtain new learning results via cryptography. The PIs will work to develop privacy-preserving learning algorithms; to establish computational hardness of learning various Boolean function classes using tools from cryptography; to obtain computational separations between pairs of well-studied learning models; and to explore the foundational assumptions of what are the minimal hardness assumptions required to prove hardness of learning.
Foundations of Public-Key Encryption: From Weak Notions to Strong Ones
The project investigates the possibility of realizing strong notions of public-key encryption from weaker ones. Starting from the standard semantic security definition given in the 1980s, guaranteeing security against a passive adversary seeing the ciphertext the project explores the construction of public key encryption secure against non-malleability attacks, guaranteeing that it is infeasible to modify a ciphertext into another ciphertext of a related message. Furthermore, the possibility of constructing a public key encryption secure against the stronger chosen ciphertext attack, protecting against an active adversary who may gain some access to the decryption algorithm, is investigated. These stronger notions of security are crucial for current cryptographic applications, yet despite much work in the area, their relation to the standard notion is not well understood, and it is not known whether chosen ciphertext attack security requires stronger computational assumptions than weaker notions. A construction that, given any subroutine for a semantically secure encryption scheme, computes a strong (non-malleable or chosen-ciphertext-attack secure) encryption scheme, would be a major result in cryptography, both from the theoretical perspective (providing a construction from minimal assumptions), and the practical one (providing the benefits of ease of implementation and modularity, as well as efficiency). Furthermore, such a result would allow basing the strong encryption schemes on a large array of computational assumptions which are currently only known to imply standard encryption schemes (e.g., factoring, elliptic curves, lattices).
Tamper Proofing Cryptographic Operations
This project focuses on the development of cryptographic mathematical models and constructions that address realistic security requirements at the implementation level. This is a fundamental problem as cryptographic security formalisms are often criticized for lack of relevance given the wide range of attacks available at the implementation level. Indeed, traditional cryptographic attacks are restricted in the way private data can be accessed; hence, the security of systems relying on such constructs is contingent on external non-cryptographic means for enforcing the necessary tamper resilience. Unfortunately, this physical tamper resistance is either too expensive or unreliable. The research extends models of cryptographic attacks to include various forms of private data tampering and access and brings the theory of cryptographic constructions closer to security concerns in practice. In particular, the tamper proofing of a wide set of cryptographic primitives is considered in an extended adversarial setting, such as digital signatures, public key encryption, secure function evaluation, as well as arbitrary cryptographic functions. This research thus explores the boundaries of what is achievable algorithmically and practically through cryptographic means.
Privacy Preserving Sharing of Network Trace Data
The Department of Homeland Security (DHS) is supporting a new three-year project in cooperation with BAE Systems National Security Solutions Inc. The team will develop a next-generation network-trace anonymization tool that preserves individual and organizational privacy while still allowing cross-trace correlation for detection, understanding, and prevention of complex attacks and other network behavior. The tool will rely on three techniques that will be developed at Columbia University: (1) Hidden Markov Model (HMM)-based clustering will be used to divide raw network traces into groups for which statistical and other properties can be preserved across the anonymized equivalents; (2) more aggressive application- and definition-specific anonymization will prevent recovery and attribution of private topology, flow, and content information under attack; and (3) efficient and application-specific secure computation will allow this clustering and anonymization without centralizing or revealing the contents of individual raw traces during the clustering stage. These anonymization techniques will be evaluated against large sets of real-world traces, implemented and ruggedized. The resulting tool, which will be released under an open-source license for use in DHS PREDICT and other public cooperative-security efforts, will make next-generation anonymization broadly available to the security community, and will encourage greater sharing of useful trace data, without compromising privacy.
Anonymous and Private Database Searching
IARPA supports this project to investigate how to search databases while providing privacy to both the searcher and the subjects of the database. The goal of the program is to develop and demonstrate practical, sound methods for the use of private information retrieval techniques in Intelligence Community systems, allowing a client to search a database for information of interest, while providing privacy to both sides: protecting other data of the information provider, and the nature of the client's interests. Specifically, the objective of this project is to investigate algorithms and systems that enable secure searches over encrypted data, and that are simultaneously practical and usable while providing concrete, provable security and privacy guarantees. In particular, we will investigate: (a) mechanisms for secure encrypted database searches; (b) theoretical foundations and new definitions of security for private information retrieval that offer different security/efficiency tradeoffs; (c) searchable secure email that protects messages-at-rest while allowing for private searches, resistant against even active adversaries; and (d) encrypted document comparison and tracking using n-grams encoded in encrypted Bloom filters. According to the IARPA mission statement, "The Intelligence Advanced Research Projects Activity (IARPA) invests in high-risk/high-payoff research that has the potential to provide our nation with an overwhelming intelligence advantage over future adversaries."
Key Evolving Signatures
New York Software Industry Association (NYSIA) sponsors this project on key-evolving signatures. Digital signatures play an essential role in securing financial Internet transactions, including private and authenticated communication, electronic commerce and other applications. However, all signature-based systems are vulnerable to the key exposure problem, which in practice is a far more likely cause of compromise than cryptanalysis. The objective of the project is to investigate the feasibility, performance, and correct use of key-evolving signatures, a new type of signatures which has recently emerged in the cryptographic community as a potentially realistic way to mitigate key exposure attacks. In particular, the project will study intrusion resilient signatures, the strongest key-evolving mechanism to date, which allows to contain the damage to a single time period, with no other consequences for earlier or later uses of the key.