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

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

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.