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

密码学的传统目标是为定义良好的任务（如公钥加密）设计密码学算法。我们建议研究以下概念上有趣的问题：什么时候我们可以将一个加密函数嵌入到一个不是为此目的而设计的函数中，比如一个自然产生的函数？在一个更抽象的环境中，可能的概念或对象的集合？由函数类{f_c}表示，其中c是（未知）对象的描述。我们无法控制函数类{f_c}，而是由“自然”赋予的。我们假设一个对象c是从一个具有足够大熵的分布中（根据“自然”）选择的。每个输入x代表一个不同的测量，或“查询”。，可以对物体做出的。我们的目标是设计一个算法来学习c(或a ？好的近似?c)通过查询x并观察答案y = f_c(x)。该算法应具有以下非平凡隐藏属性。任何计算有限的窃听者谁只观察查询和响应（x,y）的序列不能学习任何？有用的信息吗?关于c。

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.