Career: Cryptography, Proof Checking and Approximation

职业：密码学、证明检查和近似

• 批准号: 9624439
• 负责人: Mihir Bellare
• 金额: $ 20万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-07-01 至 2000-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9624439&HistoricalAwards=false
• 关键词: Career; Cryptography; Proof; Checking; Approximation

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.***

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