You probably heard the term “PUF”, or “physically unclonable function” before (if not, you should look it up!). A PUF is a physical object that is virtually impossible to clone using state-of-the-art fabrication technology. It exhibits functional characteristics that are very hard to predict, and, by virtue of being unpredictable, are hard to duplicate. (Think of it like a black box that implements a truly random function.) The reason for the unpredictability of a PUF’s behavior is nearly uncontrollable elements in the semiconductor fabrication process. A PUF is an integrated circuit (IC); the fabrication process for ICs involves steps that are very hard to control, and as such results in unpredictable differences even among two ICs created from the same blueprint. PUFs are designed in a way that leverages precisely these unpredictable factors. In contrast to a regular IC whose behavior we wish to completely determine at the time of manufacture, we actually seek unpredictability in the behavior of a PUF.
How do we leverage such an object to create an “unclonable” chip? Hardware security researchers have been pursuing this question for more than a decade, under the purview of a technique called “logic locking”. The premise is the following: a chip designer can leverage the unpredictability of a PUF to build read-proof - albeit expensive – storage, for a binary value of arbitrary length. (The designer can of course build read-proof storage big enough to hold a description of the entire chip in some form, then have a “circuit executor” read the description from the read-proof memory and run it, but this would not truly be a “custom” IC.) Suppose the designer now transforms the chip description so it’s incomprehensible unless the designer enters a certain value into the read-proof memory. We now have a custom IC that doesn’t reveal its function.
In my latest joint work with researchers at the University of Waterloo, New York University and Google, we describe one such mechanism, in which we leverage two recently discovered cryptographic primitives: puncturable pseudorandom functions and indistinguishability obfuscators. The intuition behind the idea is this: suppose we are able to come up with an efficient way to describe the truth table of a Boolean function, and that we then XOR each entry of the truth table with a random bit. The result will reveal nothing about the function itself. But how do we do this efficiently? It turns out that Xoring a circuit that computes the function with a (puncturable) pseudorandom function and applying an indistinguishability obfuscator to the result does exactly this. Of course, we don’t know yet what the overhead of this construction is, but we can expect it to be huge. It’s definitely an avenue worth exploring however.
If you’re interested in working with me on implementing a custom IC that doesn’t reveal its function, let me know!
Related Persons
