Career: Cryptography, Proof Checking and 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.***