Physical one-way functions

By P. Ravikanth, Stephen A. Benton. 2001

1,132 citations recorded by the source corpus.

Modern cryptography relies on algorithmic one-way functions—numerical functions which are easy to compute but very difficult to invert. This dissertation introduces physical one-way functions and physical one-way hash functions as primitives for physical analogs of cryptosystems. Physical one-way functions are defined with respect to a physical probe and physical system in some unknown state. A function is called a physical one-way function if (a) there exists a deterministic physical interaction between the probe and the system which produces an output in constant time; (b) inverting the function using either computational or physical means is difficult; (c) simulating the physical interaction is computationally demanding and (d) the physical system is easy to make but difficult to clone. Physical one-way hash functions produce fixed-length output regardless of the size of the input. These hash functions can be obtained by sampling the output of physical one-way functions. For the system described below, it is shown that there is a strong correspondence between the properties of physical one-way hash functions and their algorithmic counterparts. In particular, it is demonstrated that they are collision-resistant and that they exhibit the avalanche effect, i.e., a small change in the physical system causes a large change in the hash value. An inexpensive prototype authentication system based on physical one-way hash functions is designed, implemented, and analyzed. The prototype uses a disordered three-dimensional microstructure as the underlying physical system and coherent radiation as the probe. It is shown that the output of the interaction between the physical system and the probe can be used to robustly derive a unique tamper-resistant identifier at a very low cost per bit. The explicit use of three-dimensional structures marks a departure from prior efforts. Two protocols, including a one-time pad protocol, that illustrate the utility of these hash functions are presented and potential attacks on the authentication system are considered. Finally, the concept of fabrication complexity is introduced as a way of quantifying the difficulty of materially cloning physical systems with arbitrary internal states. Fabrication complexity is discussed in the context of an idealized machine—a Universal Turing Machine augmented with a fabrication head—which transforms algorithmically minimal descriptions of physical systems into the systems themselves. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/c80460c741362038b3e366313414b2edcaa015a4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Phase control algorithms for focusing light through turbid media (2007, background): “i.e., it has no correlation with the incident wavefront [ 15 ].”
Modeling attacks on physical unclonable functions (2010, methodology): “This includes any identification, authentication, key exchange or digital rights management protocols, such as the ones described in [1, 2, 6 , 7, 11].”
Squealing Euros: Privacy Protection in RFID-Enabled Banknotes (2003, background): “A number of researchers have investigated the use of distinctive characteristics of physical media as \ngerprin ts" to prevent device or object cloning, e.g., [12, 22 ].”
New Shielding Functions to Enhance Privacy and Prevent Misuse of Biometric Templates (2003, background): “cryptography to name our role players, we will say that prover Peggy allows verifier Victor to measure her object [ 1 ] or physiological parameters [2] called "Prop." We are not only interested in security breaches due to a dishonest Peggy, but also in those resulting from an unreliable Victor.”
Read-Proof Hardware from Protective Coatings (2006, methodology): “In order to make read-proof hardware, we build further on the idea of Physical Unclonable Functions introduced in [ 11 ] and further extended in [17].”
Design and Implementation of PUF-Based "Unclonable" RFID ICs for Anti-Counterfeiting and Security Applications (2008, methodology): “For example, Pappu proposed an optical PUF, which uses the speckle patterns of optical medium for laser light [ 8 ].”
Physically Unclonable Functions: A Study on the State of the Art and Future Research Directions (2010, methodology): “A formalization of this concept was introduced in the very beginning of the twenty-first century, first as physical one-way functions [41, 42 ], physical random functions [13], and finally as physical(ly) unclonable functions or PUFs.”
Physical One-Way Functions (2002, methodology): “In the embodiment described here [20, 21], we used a λ = 632.”
Extended abstract: The butterfly PUF protecting IP on every FPGA (2008, background): “Since their introduction in [ 15 ], [16], PUFs have received considerable attention from the security community because of the unclonability and randomness properties inherent to them.”
Physical Unclonable Functions for Device Authentication and Secret Key Generation (2007, methodology): “For example, Pappu proposed an optical PUF, which uses the speckle patterns of optical medium for laser light [ 12 ].”
Optical Techniques for Information Security (2009, methodology): “Various forms of optical security techniques such as XOR encoding using polarization [15] or generation of random numbers based on speckle patterns [ 30 ] have been presented by researchers.”