Stefano Tessaro - US grants

Present-day cryptography crucially relies on secret-key cryptography, the setting where communicating parties use a shared secret key, hidden to the attacker, to securely encrypt and/or authenticate data. Secret-key cryptography is based on standardized efficient algorithms known as cryptographic primitives, such as block ciphers and hash functions. These act as building blocks for so-called modes of operations, cryptographic algorithms achieving strong security goals for encryption and authentication, and which are orders of magnitude faster than public-key ones.

This project addresses the two shortcomings of current symmetric key cryptography, namely the lack of provable security for existing block ciphers and the lack of flexibility due to fixed parameters in existing implementations of primitives. The project develops new provably secure ciphers with strong security guarantees under the assumption that an attacker only has black box access to a simple underlying component. The investigator explores a new formal model that captures tradeoffs between local computation and key-dependent access in cryptographic attacks, and develops new modes of operation with improved security under this new viewpoint. The project will have broad impact on society by laying the foundations for the development of secret key cryptography which is used to secure modern communications and commerce.

Organizations and companies often archive high volumes of versioned digital datasets. There are research challenges and opportunities for developing integrated archival and search support needed for data preservation, electronic discovery, and regulatory compliance. Since versioned datasets contain highly repetitive content, deduplication can reduce the storage demand by an order of magnitude or more; however such an optimization is resource-intensive. After deduplication, the structure of an inverted index for versioned data becomes complex and it is expensive to search relevant results. This project will study low-cost solutions for compact archiving and indexing and develop efficient algorithms and systems techniques for searching versioned datasets. It will also consider that the archived data can be stored in an untrusted server environment and investigate tradeoffs in efficiency and privacy-preservation for search. The developed solutions will bring significant computing and storage cost advantages for application users involving large-scale versioned data management and search. The developed software will be made public for research communities. The research effort will be integrated with an educational plan containing research mentoring, instruction improvement, and outreach activities.

This project will be focused on studying key challenges and cost-sensitive technical aspects in integrated archival and search support for managing large versioned datasets. The main tasks include efficient software architecture and optimization for detecting duplicated content on a cloud cluster architecture, fast multi-phase search with a hybrid index structure to exploit content similarity and query characteristics, and an efficient privacy-preserving framework with top result ranking.

Outsourcing storage to the cloud has become more widespread in recent years; however, cloud storage services are constantly exposed to a number of non-trivial adversarial threats. This work addresses security risks arising from the leakage of access patterns, which is the ability of an adversary to detect when the same item is accessed repeatedly on a storage server, which has been shown to substantially impact data privacy. This project develops CloudORAM, the first provably-secure fully concurrent and asynchronous oblivious storage system that relies on simple tree-based Oblivious RAM (ORAM) techniques, the state-of-the-art cryptographic solution for hiding access patterns.

CloudORAM's system architecture uses a trusted proxy node processing concurrent accesses, from potentially multiple clients, to an untrusted server to hide access patterns. CloudORAM also outperforms existing systems in terms of performance, storage requirements, and scalability, while being substantially simpler to describe and deploy due to the tree-based ORAM structure. This project develops better combinatorial techniques to reduce bandwidth consumption in ORAM-based storage solutions as well as proofs of concept for new oblivious storage systems without the need of a trusted proxy node, and presents the first comprehensive formal framework to formalize and prove security of oblivious storage systems.

Cryptography is essential to ensure confidentiality and integrity of information. Due to their practicality, symmetric algorithms ­­ where the same secret key is used by the sender and the recipient ­­ underlie most practical deployments of cryptographic techniques. However, also as a result of this, symmetric cryptography suffers from an inherent tension between real ­world efficiency demands and provable security guarantees. This project investigates new technical advances aimed at narrowing the gap between provable security and the practical demands of symmetric cryptography.

The project develops new cryptographic algorithms and proof techniques, drawing from techniques in theoretical computer science, applied mathematics, and information theory. This involves the study of combinatorial problems whose solutions yield security proofs for existing and new encryption paradigms, and the development of new provably secure methods to encrypt data from arbitrary domains. The project identifies widely deployed cryptographic methods without provable security guarantees, introduces new assumptions on their components and new frameworks to validate their security with proofs, and explores the trade­off between efficiency and security of symmetric cryptographic algorithms. The project will organize an annual cryptography academy targeted at economically disadvantaged high-school students, to increase their interest and representation in computing.

Cryptography provides the basic tools to guarantee confidentiality and integrity of data. It hence plays a pivotal role in securing our digital infrastructure, and in enforcing the right for privacy of individuals. The development of secure cryptographic techniques is however difficult and error-prone, as unknown attack strategies need to be taken into account. To overcome this, modern cryptography advocates the paradigm of provable security, where threat models are precisely formalized using the language of mathematics, and the security of cryptosystems is proved within these models. This project aims to develop a better quantitative approach to provable security. The research of this project yields a better understanding of in-use cryptography, therefore contributing to the safer deployment of existing cryptographic solutions, as well as the support of future standardization processes. The educational component of this project includes the development of a comprehensive program to educate undergraduate students in the proper use of cryptography, and to use cryptography as a vehicle for outreach.

This project develops better theory to prove rigorous lower bounds on the combination of time and memory needed by the attacker. This allows us to better compare cryptographic solutions, and to favor those which, for equal time resources, require the largest amount of memory in order to be compromised. Concretely, this project contributes along two different fronts. The first direction extends the theory of memory-hard functions, which are functions that are moderately hard to compute with respect to some combination of time and memory resources. This project introduces better hardness metrics as well as new security targets for memory-hard functions, and analyze new constructions. The second direction revisits the security of various schemes in symmetric cryptography, and provides lower bounds on the complexity of adversaries breaking them both in terms of time and memory storage, in the setting where some underlying component of scheme is modeled as ideal.

The project studies advanced general techniques to accomplish tasks in a privacy-preserving manner. For example, these techniques enable two or more mutually distrusting entities to interact over a network to perform a joint computation on their private data, without revealing this data to each other. Many of these tools have been developed in the context of theoretical cryptography, and only recently started finding their way towards adoption. The project?s novelties are new viewpoints and techniques in the developments of these tools which take inspiration from the analysis of more conventional in-use cryptographic functionalities (like encryption). The project?s impacts are the validation of existing solutions, the development of more efficient and more secure solutions, and initiating new lines of theoretical research.

More concretely, this project introduces a new vista on zero-knowledge proofs and multi-party computation, aimed at understanding the trade-off between the concrete efficiency and the concrete security of these protocols. The goal is to analyze existing solutions, but also to propose new ones with better security and/or efficiency. While, in principle, many existing analyses can be re-examined to be made concrete, the project focuses on questions that also capture challenging technical barriers encountered in the process of giving concrete guarantees which are as precise as possible, and this, in turn, motivates new lines of theoretical research. The concrete analysis developed in this project further informs and guides the deployment of the advanced cryptographic techniques examined. As part of the broader impacts, the investigators have an outreach component aimed at training teachers and ambassadors to promote studies in STEM using cryptography.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.