Career: Cryptography, Proof Checking and Approximation

注：该职业奖是职业奖CCR-96-24560的伙伴项目，“面向实践的可证明的安全”，加州大学戴维斯分校。该项目侧重于(1)可证明的安全性和概率证明检查领域，旨在开发实用的，但已证明的安全协议；(2)概率证明检查（PCP）应用于NP-hard优化问题的非逼近性结果的推导。所考察的问题不能通过某种从理论到实践的“技术转移”来解决；相反，理论原理必须用于开发新模型和解决新问题。面向实践的可证明安全技术的应用被应用于以下问题：会话密钥分发，使用块密码以可证明地实现基本加密目标，以及通过密钥托管或其他手段在个人隐私和执法之间取得平衡。在PCP领域，研究的问题包括确定Max Clique近似性的紧密结果，以及Max SNP问题的改进结果。这项职业补助金的综合教育计划包括发展：(a)以合理的协议设计原则为基础的新本科和研究生课程，以及大学/工业联合培训项目；(b)本科算法设计课程，教授用于确定良好近似解的证明检查技术，并将其应用于NP-hard优化问题

NOTE: This CAREER award is a companion project to the CAREER award CCR-96-24560, ``Practice-Oriented Provable Security'', University of California, Davis. This project focuses on the areas of (1) provable security and probabilistic proof checking with orientation towards developing practical, but proven secure protocols and (2) probabilistic proof checking (PCP) with application to the derivation of nonapproximability results for NP-hard optimization problems. The problems examined cannot be solved by some kind of ``technology transfer'' from theory to practice; rather the theoretical principles have to be used to develop new models and solve new problems. Applications of the techniques of practice-oriented provable security are applied to such problems as: session key distribution, use of block cyphers to provably achieve basic cryptographic goals, and balancing between individual privacy and law enforcement, via key escrow or other means. In the area of PCP, the problems studied include determining tight results for the approximability of Max Clique, and improved results for Max SNP problem. The Integrated Educational Plan of this CAREER grant includes developing: (a) new undergraduate and graduate courses in principles of sound protocol design, with joint university/industrial training projects; and (b) an undergraduate algorithm design course in which proof checking tehniques for determining good approximate solutions are taught and applied to NP-hard optimization problems.***