Logic Locking of Boolean Circuits: Provable Hardware-Based Obfuscation from a Tamper-Proof Memory

Today’s integrated circuits are subject to a variety of attacks. Logic Locking is an area of hardware security that attempts to prevent reverse-engineering of integrated circuits based on a tamper-resistant memory. Despite significant attention from the research literature, no rigorous cryptographic modeling of logic locking and associated provable secure solutions have been proposed.

Based on the observation that logic locking can be seen as a special case of hardware-based cryptographic program obfuscation, we propose rigorous definitions, borrowing approaches from modern cryptography (and, specifically, cryptographic program obfuscation), for both tamper-proof memories and logic locking of boolean circuits. We then prove two positive results: (1) the existence of a circuit computationally indistinguishable from a random oracle, assuming the existence of a pseudo-random function and of a tamper-proof memory, and (2) logic locking of general polynomial-size boolean circuits, assuming the existence of a pseudo-random generator and a tamper-proof memory.

Our paper shows the possibility of provably boosting the capability of constructing a physical memory with a suitable tamper-resistant property into hardware-based obfuscation of any boolean circuit, as well as a practical hardware-based realization of a random oracle.

Authors and Affiliations

1. Perspecta Labs, Basking Ridge, NJ, USA

   Giovanni Di Crescenzo

2. New York University, New York, NY, USA

   Abhrajit Sengupta & Muhammad Yasin

3. New York University, Abu Dhabi, UAE

   Ozgur Sinanoglu

Corresponding author

Correspondence to Giovanni Di Crescenzo .

Editors and Affiliations

1. Polytechnic University of Bucharest, Bucharest, Romania

   Emil Simion

2. École Normale Supérieure, Paris, France

   Rémi Géraud-Stewart

The first author’s work was supported by the Defense Advanced Research Projects Agency (DARPA) via U.S. Army Research Office (ARO), contract number W911NF-15-C-0233. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation hereon. Disclaimer: The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of DARPA, ARO or the U.S. Government.

A Pseudo-random Generators and Functions

We recall the formal notions of pseudo-random generators and functions used in the cryptography literature.

Pseudo-random generators are stretching functions whose output is computationally indistinguishable from a random string of the same length. A function \(prG_{\sigma ,m}:\{0,1\}^\sigma \rightarrow \{0,1\}^m\), is a stretching function if \(m>\sigma \). Let \(\epsilon _{prg}\) be a function negligible in the security parameter \(\sigma \). We say that a family of functions \(prG=\{prG_{\sigma ,m}:\sigma \in {\mathcal N}\}\) is a family of \(\epsilon _{prg}\)-pseudo-random generators if each \(prG_{\sigma ,m}\) is a stretching function and if for any efficient adversary Adv, the difference \(|p_r-p_{prG}|\) is smaller than \(\epsilon _{prg}(\sigma )\), where

1. 1.

   \(p_r=\{r\leftarrow \{0,1\}^m\,:\,Adv(r)=1\}\); and

2. 2.

   \(p_{prg}=\{s\leftarrow \{0,1\}^\sigma ;z\leftarrow prG_{\sigma ,m}(s)\,:\,Adv(z)=1\}\).

Families of \(\epsilon _{prg}\)-pseudo-random generators, for negligible functions \(\epsilon _{prg}\), have been constructed from any family of one-way functions [18], from any of a number of number-theoretic hard problems (e.g., [7]), as well as through more practical heuristic constructions (e.g., [21]).

We say that a function \(R_{n,m}:\{0,1\}^n\rightarrow \{0,1\}^m\) is a random function (over n-bit inputs and with m-bit outputs) if it is randomly chosen among all functions with n-bit inputs and m-bit outputs. In a random function \(R_{n,m}\), for any input string \(x\in \{0,1\}^n\), the output string \(R_{n,m}(x)\in \{0,1\}^m\) is uniformly and independently distributed. We say that a family of functions \(\{R_{n,m}:n,m\in {\mathcal N}\}\) is a family of random functions if each function \(R_{n,m}\) is a random function over n-bit inputs and with m-bit outputs. As a consequence, an adversary querying \(R_n\) on several input strings and obtaining the corresponding output strings still cannot predict the output string \(R_{n,m}(x)\) corresponding to a new input string x, better than by randomly choosing a string of the same length. As any logical description of a random function over \(\{0,1\}^n\) inputs requires \(\varOmega (2^n)\) space, families of random functions cannot be efficiently represented as a circuit (unless n is small). Pseudo-random functions [15] are widely used to approximate the properties of random functions. Their evaluation only requires a short random key, and their pseudo-randomness property holds as long as the key is kept secret.

A function \(prF_{n,m}:\{0,1\}^\kappa \times \{0,1\}^n\rightarrow \{0,1\}^m\) is a keyed function (over n-bit inputs and with m-bit outputs) if for each \(k\in \{0,1\}^\kappa \), the function \(prF_{n,m}(k,\cdot )\), also denoted \(prF_k(\cdot )\), is a function with n-bit inputs and m-bit outputs.

For any \(n,m\in {\mathcal N}\), let \(Rand_{n,m}\) be the set of all functions \(R_{n,m} : \{0,1\}^n\rightarrow \{0,1\}^m\) and let \(prF_k : \{0,1\}^n\rightarrow \{0,1\}^m\) be a keyed function. Consider the following probabilistic experiment Init:

1. 1.

   Uniformly choose \(R_n\) from \(Rand_{n,m}\); and

2. 2.

   uniformly choose k from \(\{0,1\}^\kappa \).

Let \(\epsilon _{prf}\) be a function negligible in the security parameter. We say that a family of functions \(prF=\{prF_{n,m}:n\in {\mathcal N}\}\) is a family of \(\epsilon _{prf}\)-pseudo-random functions if for any efficient oracle adversary Adv, the difference \(|p_R-p_{prF}|\) is smaller than \(\epsilon _{prf}\), where

1. 1.

   \(p_R=\{Init;O(\cdot )\leftarrow R_{n,m}(\cdot );A^O(1^n)=1\}\); and

2. 2.

   \(p_{prF}=\{Init;O(\cdot )\leftarrow prF_{n,m}(k,\cdot );A^O(1^n)=1\}\).

In other words, pseudo-random functions are computationally indistinguishable from random functions with the same input and output lengths.

B Universal Circuits

In [30] it was proved that there exists a universal circuit \(c_u\) that can compute the output of any input circuit c on its input string x. Since circuit c is encoded as a binary string before being given as input to \(c_u\), we re-state below this property of universal circuits with a natural constraint on the size of the input circuit c, which, in turn, implies a constraint on the length of the (conventional) binary encoding of c.

First, let \(\mathcal {C}_{\ell _x,g}\) be the class of circuits that take as input an \(\ell _x\)-bit input string x, have size at most \(g(\ell _x)\) gates, for some polynomial g, and return a 1-bit output. Also, fix a conventional encoding of a circuit c from \(\mathcal {C}_{\ell _x,g}\) as a binary string, and assume that any such circuit c is encoded into a string, denoted as b(c), of length at most \(\ell _c\). Then, the universal circuit \(c_u\) for circuits in \(\mathcal {C}_{\ell _x,g}\) is formally defined as a circuit with the following properties:

1. 1.

   it takes as input an \(\ell _x\)-bit string x and a \(\ell _c\) string b(c)

2. 2.

   b(c) is the binary encoding of a boolean circuit c with at most \(g(\ell _x)\) gates and \(\ell _x\)-bit inputs

3. 3.

   \(c_u(b(c),x)=c(x)\) for all possible inputs c, x.

The result in [30] can be restated as follows:

Theorem 3

[30] Let g be a polynomial. There exists (constructively) an universal circuit \(c_u\) for circuits in \(\mathcal {C}_{\ell _x,g}\) with size \(O((\ell _c+\ell _x)\log (\ell _c+\ell _x))\).

We note that in principle the description of a universal circuit \(c_u\) might leak some information about the original circuit c, such as, for instance, the polynomial g used to describe the number of gates in c. For instance, a universal circuit for circuits in \(\mathcal {C}_{\ell _x,g}\) with \(g_1(\ell _x)\) gates might be easily distinguishable from a universal circuit for circuits in \(\mathcal {C}_{\ell _x,g}\) with \(g_2(\ell _x)\) gates, if polynomials \(g_1,g_2\) are different, while satisfying \(g_i(\ell _x)\le g(\ell _x)\), for \(i=1,2\). Since our goal is to design a logic locking scheme for all circuits in the class \(\mathcal {C}_{\ell _x,g}\), we will need the following size indistinguishability property of universal circuits for circuits in \(\mathcal {C}_{\ell _x,g}\): for any two pairs \((\ell _1,g_1)\) and \((\ell _2,g_2)\) such that \(\ell _i\le \ell _x\) and \(g_i\le g\), for \(i=1,2\), it holds that the universal circuit generated for circuits in the subclass \(\mathcal {C}_{\ell _1,g_1}\) and the universal circuit generated for circuits in the subclass \(\mathcal {C}_{\ell _2,g_2}\) are equal.

We note that simple padding techniques can be used to transform any universal circuit into one that satisfies size indistinguishability. For instance, a circuit with \(\ell _1\le \ell \) inputs and \(g_1\le g\) gates might be padded with inputs and gates (that do not change the computation) so to have exactly \(\ell \) inputs and g gates before generating the universal circuit. In the rest of the paper, we will assume such a procedure and therefore that all universal circuits satisfy size indistinguishability. Moreover, we will also assume that given a universal circuit for circuits in class \(\mathcal {C}_{\ell _x,g}\), it is possible to derive the length \(\ell _c\) of the binary representation b(c) of the original circuit c from the class.

C Proof that (KeyGen1, LockGen1) Satisfies Theorem 1

We prove that our logic locking scheme (KeyGen1, LockGen1) from Sect. 3 satisfies Theorem 1 by proving that it satisfies the 4 properties of Definition 3: computation correctness, lock security, efficient circuit and memory size.

Computation Correctness and Efficiency Properties. The correctness of the computation is a direct consequence of the definition of pseudo-random functions. That is, an adversary finding, with non-negligible probability, an x such that \(prF_{n,m}(x)\ne c(x)\) can be used to distinguish pseudo-random functions from random functions. With respect to circuit size, we observe that the locked circuit contains the circuit for the pseudo-random function prF and the circuit for retrieval from tpM, and therefore the logic locking scheme satisfies \(t'\)-efficient circuit size, for \(t'\le O(t_{prf}+t_{tpm}+\lambda )\). With respect to memory size, we observe that the locked circuit only stores the key length for pseudo-random function \(prF_{n,m}\) on the tamper-proof memory and therefore the logic locking scheme satisfies \(\lambda '\)-efficient memory size, for \(\lambda '\ge \kappa \).

Lock Security. Let c be a Boolean circuit. If rP is a random process, we let \(Pr_{lock}[rP]\) denote the probability that \(c_{adv}=c\) after a sequential execution of the following 3 processes:

• \(k\leftarrow \) KeyGen\((1^\lambda ),\)

• \(b\leftarrow \) tpMStore\((1^\lambda ,k;tpM)\),

• rP.

We prove the lock security property by a hybrid argument [16], where, informally speaking, we evaluate and compare the success probability of adversary Adv or a related algorithm \(Adv'\) in guessing circuit c in the following 4 “worlds”, where L denotes a logical abstraction function:

1. 1.

   Adv has read access to \(c',L(tpM)\) and oracle access to \(c'(k,\cdot )\);

2. 2.

   Adv has read access to \(c',1^\lambda \) and oracle access to \(c'(k,\cdot )\);

3. 3.

   Adv has read access to \(c',1^\lambda \) and oracle access to a random oracle \(R_{n,m}\); and

4. 4.

   \(Adv'\), an efficient algorithm depending on Adv, has read access to \(c',1^\lambda \).

More formally, we first define the following random processes:

• \(rP_1\) = “\(c_{adv}\leftarrow Adv^{c'(k,\cdot )}(c',L(tpM))\)”,

• \(rP_2\) = “\(c_{adv}\leftarrow Adv^{c'(k,\cdot )}(c',1^\lambda )\)”,

• \(rP_3\) = “\(c_{adv}\leftarrow Adv^{R_{n,m}}(c',1^\lambda )\)”,

• \(rP_4\) = “\(c_{adv}\leftarrow Adv'(c',1^\lambda )\)”.

Then we obtain the following lemmas.

Lemma 1

\(p_0=Pr_{lock}[rP_1]\) and \(p_1=Pr_{lock}[rP_4]\)

Proof

The first equality directly follows from definitions of \(p_0\) and \(rP_1\). The second equality directly follows from definitions of \(p_1\) and \(rP_4\), and by setting the simulator algorithm Sim as equal to \(Adv'\). \(\blacksquare \)

Lemma 2

\(|Pr_{lock}[rP_1]-Pr_{lock}[rP_2]|\le \epsilon _{tpm}\), for some \(\epsilon _{tpm}\) negligible in \(\sigma \).

Proof

Let \(p_0,p_1\) be the probability quantities defined in Definition 2. By the definitions of \(rP_1,rP_2\), we observe that \(Pr_{lock}[rP_1]=p_0\) and \(Pr_{lock}[rP_1]=p_1\). Then the lemma follows as a direct application of Definition 2 for the tamper-proof security of tpM. \(\blacksquare \)

Lemma 3

\(|Pr_{lock}[rP_2]-Pr_{lock}[rP_3]|\le \epsilon _{prf}\), for some \(\epsilon _{prf}\) negligible in \(\sigma \).

Proof

We first observe that the difference between \(rP_2\) and \(rP_3\) only consists of the oracle to which Adv has oracle access. Specifically, in \(rP_2\), Adv has access to locked circuit \(c'(k,\cdot )\), an oracle that evaluates the circuit \(c'\) for pseudo-random function prF with key k, while in \(rP_3\), Adv has access to a random oracle \(R_{n,m}\). Moreover, in both \(rP_2\) and \(rP_3\), Adv has read access to unlocked circuit \(c'\) and \(1^\lambda \). Then we can directly apply the pseudo-randomness property of prF, and obtain that Adv can only distinguish the two worlds with at most negligible probability \(\epsilon _{prf}\). \(\blacksquare \)

Lemma 4

For any efficient algorithm Adv, there exists an efficient algorithm \(Adv'\) such that \(Pr_{lock}[rP_4]=Pr_{lock}[rP_3]\).

Proof

Consider algorithm Adv in random process \(rP_3\). Then, define algorithm \(Adv'\) as the algorithm that runs Adv and, in this execution, simulates the answers to Adv’s queries to the random oracle as random strings (for new queries) or previously generated random strings (for repeated queries); finally, \(Adv'\) returns the same output as Adv. Since the simulation performed by \(Adv'\) of the random oracle answers is perfect, we have that \(Adv'\) guesses the original circuit c in \(rP_4\) with the same probability that Adv guesses the original circuit c in \(rP_3\), and thus \(Pr_{lock}[rP_4]=Pr_{lock}[rP_3]\), from which the lemma follows. \(\blacksquare \)

Finally, we use these lemmas to conclude the proof that the logic locking scheme satisfies Definition 3. Specifically, we have that

where the first equality follows from Lemma 1, the first inequality follows by applying the triangle inequality, the second inequality follows from Lemma 2, the third inequality follows from Lemma 3, the fourth inequality follows from Lemma 4, and the fifth inequality follows from assumptions on \(\epsilon _{tpm},\epsilon _{prf}\).

D Proof that (KeyGen2, LockGen2) Satisfies Theorem 2

The proof that our logic locking scheme (KeyGen2, LockGen2) satisfies Theorem 2 follows the same structure as the proof of Theorem 1. Specifically, we prove that it satisfies the 4 properties of Definition 3: computation correctness, lock security, efficient circuit size and efficient memory size.

Computation Correctness. The correctness of the computation of the locked circuit follows directly from the definition and properties of universal circuits.

Efficiency Properties. With respect to circuit size, we observe that the locked circuit contains the circuit for the pseudo-random generator prG, the circuit for retrieval from tpM, and circuit gates for computing the xor between two strings of length \(\ell _c\), and therefore the logic locking scheme satisfies \(t'\)-efficient circuit size, for \(t'=O(t_{prg}+t_u+t_{tpm}+\lambda )\). With respect to memory size, we observe that the locked circuit only stores the key length for pseudo-random generator \(prG_{\sigma ,m}\) on the tamper-proof memory and therefore the logic locking scheme satisfies \(\lambda '\)-efficient memory size, for \(\lambda '\ge \sigma \).

Lock Security. The proof for this property is structured very similarly as in the proof for Theorem 1. Thus, it suffices to discuss the differences, which are mainly in the definitions for the worlds and relative random processes used in the proof’s hybrid argument. The main technical difference in the proof is in the simulation argument, as described in the proof of Lemma 7. As before, we evaluate and compare the success probability of adversary Adv or a related efficient algorithm \(Adv'\) in guessing circuit c in the following 4 “worlds”:

1. 1.

   Adv has read access to \(c'_y,L(tpM)\) and oracle access to \(c'_y(k,\cdot )\);

2. 2.

   Adv has read access to \(c'_y,1^\lambda \) and oracle access to \(c'_y(k,\cdot )\);

3. 3.

   Adv has read access to \(c'_z,1^\lambda \), for some random \(\ell _c\)-bit string z, and oracle access to \(c'_y(k,\cdot )\); and

4. 4.

   \(Adv'\), an efficient algorithm depending on Adv, has oracle access to \(c'_y(k,\cdot )\).

Denote as \(p_{adv,i}\) the probability that Adv correctly guesses c in world i, for \(i=1,2,3,4\), after the same random processes used in Definition 3. We note that \(p_{adv,1}=p_0\), by definition. Then, the proof is obtained by combining, similarly as in the proof for Theorem 1, the following lemmas.

Lemma 5

\(|p_{adv,1}-p_{adv,2}|\le \epsilon _{tpm}\), for some function \(\epsilon _{tpm}\) negligible in \(\sigma \).

Proof

This follows by Definition 2 since tpM is \(\epsilon _{tpm}\)-secure. \(\blacksquare \)

Lemma 6

\(|p_{adv,2}-p_{adv,3}|\le \epsilon _{prg}\), for some function \(\epsilon _{prg}\) negligible in \(\sigma \).

Proof

This follows by observing that \(c'_z\) is computationally indistinguishable from \(c'_y\) since z is random and y is pseudorandom, by the pseudo-randomness of prG. \(\blacksquare \)

Lemma 7

\(|p_{adv,3}-p_{adv,4}|=0\).

Proof

This follows from the simulatability property of the universal circuit. Specifically, we observe that for any efficient adversary Adv, who is given the length of the (unknown) original circuit c, we can construct an efficient adversary \(Adv'\) that simulates \(c'_z\) as follows:

• derive length \(\ell _c\) of the binary representation b(c) of circuit c

• randomly choose \(z\in \{0,1\}^{\ell _c}\)

• define \(c'_z\) as the circuit that has string z hardwired and, on input x, k:

     computes \(w=z\) xor \(prG_{\sigma ,m}(k)\)

     computes and outputs \(c_u(w,x)\).

• return: \(c'_z\)

By code inspection, we note that the simulation is perfect, in the sense that the distribution of circuit \(c'_z\) returned by \(Adv'\) in world 4 is identical to the distribution of \(c'_z\) returned by Adv in world 3. The lemma follows. \(\blacksquare \)

Lemma 8

\(p_{adv,4}=\text{ Prob }\left[ \,c_{sim}=c\,\right] \).

Proof

This follows directly from the above definition of \(p_{adv,4}\) and of \(\text{ Prob }\left[ \,c_{sim}=c\,\right] \) in Definition 3, and by setting the simulator algorithm Sim as equal to algorithm \(Adv'\) in the proof of Lemma 7. \(\blacksquare \)

Finally, we use these lemmas to conclude the proof that the logic locking scheme satisfies Definition 3, similarly as done for the scheme underlying Theorem 1. Specifically, we have that

where the first equality follows from Lemma 8, the first inequality follows by applying the triangle inequality, the second inequality follows from Lemma 5, the third inequality follows from Lemma 6, the fourth inequality follows from Lemma 7, and the fifth inequality follows from assumptions on \(\epsilon _{tpm},\epsilon _{prg}\).

Reprints and permissions

© 2020 Springer Nature Switzerland AG

Policies and ethics