CAREER: Separations in Cryptography

自从1949年香农的开创性工作以来，密码学一直建立在未经证实的计算复杂性之上。如果设计背后的假设被证明是错误的，加密系统的安全性可能会崩溃。因此，将加密系统的安全性建立在最弱的假设上是至关重要的。寻找最小假设的一个主要组成部分是将加密任务与比结构中使用的假设弱的假设“分开”。鉴于最近密码学的发展，将追求以下两个方向：新技术：一个形式化的模型来抽象密码学证明的属性和证明分离的技术是必要的。然而，以前研究的模型并没有考虑到密码学中一些最有用的最新技术，而是主要关注统一、黑盒和经典（非量子）证明技术。该项目的一个主要目标是开发新的基础来模拟这些新的加密技术。新任务和假设：最近密码学经历了一场探索高度结构化加密任务可行性的革命，即使这是以使用新引入的假设为代价的。该项目的第二个主要目标是加深我们对实现这些任务所必需的假设的理解。一个密切相关的目标是确定这些新任务之间的相对力量。为了传播上述思想并产生更广泛的影响，该项目将包括教育活动，如：课程开发，向高中生推广以激励他们攻读理论计算机科学和密码学学位，以及指导研究生和本科生。

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.