Dissertation Defense: Mohammad Zaheri Darkahi
Candidate Name: Mohammad Zaheri Darkahi
Major: Computer Science
Advisor: Adam O’Neill, Ph.D.
Title: Stronger Security for Practical Encryption Schemes
Despite recent advances in cryptography, security analyses of encryption schemes fall short of ruling out some possible attacks. Here we study two such types of attacks: selective-opening attacks (SOA) and attacks making use of the code of hash functions employed by the protocol rather than treating them as “black-boxes.”
Selective opening attacks are attacks where the adversary has the ability to “open” the ciphertexts of its choice. For instance, consider the scenario where the adversary sees the encrypted emails sent to Alice and is able to break into some of the senders’ machines and obtain the underlying emails. The question is what one can say about security of the other encrypted emails. The study of such attacks was initiated by Dwork et al. (Journal of the ACM 2003). However, it was only considered for the randomized encryption (R-PKE, where encryption algorithm is randomized). Here we extend the study of selective opening attacks to deterministic encryption (D-PKE, where encryption algorithm is deterministic).
Bellare, Dowlsey, and Keelveedhi (PKC 2015) were first to study SOA in the deterministic setting and showed that a certain “simulation-based” definition of selective- opening security (SOA) is impossible to achieve for D-PKE. However, their notion seems overly demanding and they left it open to formulate an achievable definition. We start our work on SOA in the deterministic setting by answering this open question and giving a new “comparison-based” security notion which we call D-SO-CPA. We then proceed to give constructions meeting this new notion.
We next explore attacks making use of the code of hash functions. Hash functions are very important building blocks of practical schemes used on the Internet. Unfortunately, many practical schemes are not shown to be immune to attacks making use of the code of hash functions that practical schemes use. Rather, they are shown to be secure in a model where hash functions are “truly random” functions. This model is called the random oracle (RO) model and was first introduced by Bellare and Rogaway (CCS 1993). The RO model has been enormously enabling in the design of practical protocols for various goals; examples include public-key encryption, digital signatures, and identity-based encryption. However, Canetti et al. (Journal of the ACM 2004) show that there exist RO model schemes for which any instantiation of truly random functions yields a scheme that can be broken efficiently by the adversary that has access to the code of instantiated hash functions. This result shows that practical schemes are not necessarily immune to such attacks.
We study the effects of such attacks on practical schemes. Specifically, we study the classical encryption transforms OAEP (EUROCRYPT 1994) and (slightly tweaked) Fujasaki-Okamoto (EUROCRYPT 1998). We show that, under suitable assumptions, there exist standard model hash functions that suffice to prevent such attacks on these encryption transforms. Our hash functions are obtained via a new unified paradigm. The core idea obfuscates an extremely lossy function, a notion introduced by Zhandry (CRYPTO 2016).