{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/45499"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/45499","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Physical one-way functions","abstract":"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 firnctions 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.","abstract_html":"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 firnctions 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.","abstract_has_math":false,"creators":["Pappu, Ravikanth Srinivasa"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Architecture. Program In Media Arts and Sciences","school":null,"contributors":[],"advisors":["Neil A. Gershenfeld."],"committee_chairs":[],"committee_members":[],"year":2001,"date_issued":"2001","date_published":"2001","updated_at":"2026-07-22T22:21:35Z","subjects":["Architecture. Program In Media Arts and Sciences"],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/45499","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Neil A. Gershenfeld."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Architecture. Program In Media Arts and Sciences"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Architecture. Program In Media Arts and Sciences"]},{"key":"dc:creator","label":"Author","values":["Pappu, Ravikanth Srinivasa"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2009-04-29T17:51:06Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2009-04-29T17:51:06Z"]},{"key":"dc:date.issued","label":"Date","values":["2001"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Architecture. Program In Media Arts and Sciences"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/45499"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph. D.)--Massachusetts Institute of Technology, School of Architecture and Planning, Program in Media Arts and Sciences, 2001.","Includes bibliographical references (p. 149-154)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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 firnctions 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.","(cont.) 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 offabrication 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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Physical one-way functions"]}]}],"canonical_facts":{"dc:contributor.advisor":["Neil A. Gershenfeld."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Architecture. Program In Media Arts and Sciences"],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Architecture. Program In Media Arts and Sciences"],"dc:creator":["Pappu, Ravikanth Srinivasa"],"dc:date.accessioned":["2009-04-29T17:51:06Z"],"dc:date.available":["2009-04-29T17:51:06Z"],"dc:date.issued":["2001"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, School of Architecture and Planning, Program in Media Arts and Sciences, 2001.","Includes bibliographical references (p. 149-154)."],"dc:description.abstract":["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 firnctions 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.","(cont.) 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 offabrication 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."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/45499"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Architecture. Program In Media Arts and Sciences"],"dc:title":["Physical one-way functions"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:35Z"}