Since the seminal work of Shannon in 1949 cryptography has been founded on unproven computational complexity. The security of cryptographic systems could fall apart if the assumptions behind their design turn out to be false. Thus, it is crucial to base the security of crypto-systems on weakest possible assumptions. A main component of finding minimal assumptions is to ``separate'' cryptographic tasks from assumptions that are weaker than those used in constructions. In light of recent developments in cryptography, the following two directions will be pursued: New Techniques: A formal model to abstract the properties of cryptographic proofs and techniques is necessary to prove separations. Previously studied models, however, do not consider some of the most useful recent techniques in cryptography and mainly focus on uniform, black-box, and classical (non-quantum) proof techniques. A major goal of this project is to develop new foundations to model these new cryptographic techniques. New Tasks and Assumptions: Recently cryptography has gone through a revolution of exploring feasibility of highly structured crypto tasks, even if this comes at the cost of using newly introduced assumptions. The second major goal of this project is to deepen our understanding of the assumptions necessary for achieving these tasks. A closely related goal is to identify the relative power of these new tasks among themselves.
To disseminate the above ideas and achieve broader impact, the project will include educational activities such as: course development, outreach to high school students to motivate them pursue degrees in theoretical computer science and cryptography, and mentoring graduate as well as undergraduate students.
CAREER: Separations in Cryptography