The security of cryptographic tasks is formally defined by precisely specifying the physical assumptions regarding the attack model, and cryptographic protocols are proven secure based on well-defined computational intractability assumptions. Understanding what the minimal computational and physical assumptions are for secure cryptographic protocols is of central importance to this study which will address the following problems: 1. New Barriers for Computational Assumptions: There exists a large body of work on, so-called, black-box separations aiming at elucidating when a cryptographic task cannot be based on a particular computational assumption using certain black-box proof techniques. However, many known constructions and proofs of security do not fall into the framework of such techniques, and as such it is not clear to what extent such separations represent a real barrier. One of the principal goals of this proposal is to develop a framework for providing non-black-box separations between cryptographic tasks and assumptions. 2. New Barriers for Physical Assumptions: Formal definitions of security make explicit assumptions about how the adversary can access or modify information exchanged during a cryptographic process. Traditionally, it is assumed that the attacker participates in a single execution of a protocol, does not get to see the internal state of honest parties, and does not get to tamper with the internal state of honest parties. Recent work has focused on relaxing the first two assumptions. Another principal goal of this proposal is to investigate to what extent the third physical assumption regarding tampering may be weakened.
Progress in this area could have broad impacts on barriers not only in cryptography but also computational complexity and secure systems. The research focusing on physical assumptions bears a promise to have broader impacts on hardware design. The results of this work will be widely disseminated via conferences, journals, workshops, and invited talks, and incorporated into the PI graduate courses.
