AF: Small: A Theory of Cryptography and the Physical World

AF：小：密码学理论和物理世界

• 批准号: 0916574
• 负责人: Amit Sahai
• 金额: $ 40万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916574&HistoricalAwards=false
• 关键词: AF; Small; Theory; Cryptography; Physical

The traditional goal of cryptography is to design cryptographic algorithms for well-defined tasks, such as public-key encryption. We propose to study the following conceptually intriguing question: when can we embed a cryptographic function into a function which was not designed for this purpose, say a function created by nature?In a more abstract setting, the collection of possible concepts or ?objects? is represented by a function class {f_c}, where c is a description of the (unknown) object. We do not have control over the function class {f_c}, but rather it is given by ?nature?. We assume that an object c is chosen (by ?nature?) from a distribution which has a sufficiently large entropy. Each input x represents a different measurement, or ?query?, that can be made to the object. The goal is to design an algorithm for learning c (or a ?good approximation? of c) by making queries x and observing the answers y = f_c(x). The algorithm should have the following nontrivial hiding property. Any computationally bounded eavesdropper who only observes the sequence of queries and responses (x,y) cannot learn any ?useful information? about c.

密码学的传统目标是为明确定义的任务（如公钥加密）设计密码算法。我们建议研究以下概念上有趣的问题：我们什么时候可以嵌入一个加密函数到一个函数，这不是为此目的而设计的，说一个功能创建的性质？在一个更抽象的设置，可能的概念或集合？物件？由函数类{f_c}表示，其中c是（未知）对象的描述。我们不能控制函数类{f_c}，而是由下式给出：自然？我们假设一个对象c被选择（由？性质？）从一个熵足够大的分布中每个输入x代表不同的测量，或者？查询？，可以对物体做出的改变。我们的目标是设计一个学习c（或a？好近似？通过查询x并观察答案y = f_c（x），该算法应具有以下非平凡隐藏属性。任何只观察查询和响应序列（x，y）的计算有限的窃听者不能学习任何东西？有用的信息？关于C。