Allen School postdoctoral researcher Joseph Jaeger and visiting researcher Nirvan Tyagi, a Ph.D. student at Cornell Tech, received the Best Paper by Early Career Researchers Award at the 40th Annual International Cryptology Conference (Crypto 2020) organized by the International Association for Cryptologic Research (IACR). Jaeger and Tyagi, who have been working with professor Stefano Tessaro of the Allen School’s Theory and Cryptography groups, earned the award for presenting a new approach to proving multi-user security in “Handling Adaptive Compromise for Practical Encryption Schemes.”
Jaeger and Tyagi set out to explore a classic problem in cryptography: How can the security of multi-party communication be assured in cases where an adversary is able to adaptively compromise the security of particular parties? In their winning paper, the authors aim to answer this question by presenting a new, extensible framework enabling formal analyses of multi-user security of encryption schemes and pseudorandom functions in cases where adversaries are able to adaptively compromise user keys. To incorporate an adversary’s ability to perform adaptive compromise, they expanded upon existing simulation-based, property-based security definitions to yield new definitions for simulation-based security under adaptive corruption in chosen plaintext attack (SIM-AC-CPA) and chosen ciphertext attack (SIM-AC-CCA) scenarios. Jaeger and Tyagi also introduced a new security notion for pseudorandom functions (SIM-AC-PRF), to simulate adaptive compromise for one of the basic building blocks of symmetric encryption schemes. This enabled the duo to pursue a modular approach that reduces the complexity of the ideal model analysis by breaking it into multiple steps and splitting it from the analysis of the high-level protocol — breaking from tradition in the process.
“Traditional approaches to formal security analysis are not sufficient to prove confidentiality in the face of adaptive compromise, and prior attempts to address this gap have been shown to be impractical and error-prone,” explained Jaeger. “By employing idealized primitives combined with a modular approach, we avoid the pitfalls associated with those methods. Our framework and definitions can be used to prove adaptive security in a variety of well-studied models, and they are easily applied to a variety of practical encryption schemes employed in real-world settings.”
One of the schemes for which they generated a positive proof was BurnBox, a system that enables users to temporarily revoke access from their devices to files stored in the cloud to preserve their privacy during compelled-access searches — for example, when an agent at a border crossing compels a traveler to unlock a laptop or smartphone to view its contents. In another analysis, the authors applied their framework to prove the security of a commonly used searchable symmetric encryption scheme for preserving the confidentiality of data and associated searches stored in the cloud. In both of the aforementioned examples, Jaeger and Tyagi showed that their approach produced simpler proofs while avoiding bugs contained in previous analyses. They also discussed how their framework could be extended beyond randomized symmetric encryption schemes currently in use to more modern nonce-based encryption — suggesting that their techniques will remain relevant and practical as the use of newer security schemes becomes more widespread.
“Joseph and Nirvan’s work fills an important void in the cryptographic literature and, surprisingly, identifies important aspects in assessing the security of real-world cryptographic systems that have been overlooked,” said Tessaro. “It also defines new security metrics according to which cryptographic systems ought to be assessed, and I can already envision several avenues of future research.”
Read the full research paper here.
Congratulations to Joseph and Nirvan!