Encrypted-Input Obfuscation of Image Classifiers

We consider the problem of protecting image classifiers simultaneously from inspection attacks (i.e., attacks that have read access to all details in the program’s code) and black-box attacks (i.e., attacks where have input/output access to the program’s code). Our starting point is cryptographic program obfuscation, which guarantees some provable security against inspection attacks, in the sense that any such attack is not significantly more successful than a related black-box attack. We actually consider the recent model of encrypted-input cryptographic program obfuscation, which uses a key shared between the obfuscation deployer and the input encryptor to generate the obfuscated program. In this model we design an image classifier program and an encrypted-input obfuscator for it, showing that the classifier program is secure against both inspection and black-box attacks, under the existence of symmetric encryption schemes. We evaluate the accuracy of our classifier and show that it is significantly better than the random classifier and not much worse than more powerful classifiers (e.g., k-nearest neighbor) for which however no efficient obfuscator is known.

Part of this 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.

Authors and Affiliations

1. Peraton Labs, Basking Ridge, NJ, USA

   Giovanni Di Crescenzo, Lisa Bahler & Brian A. Coan

2. New Jersey Institute of Technology, Newark, NJ, USA

   Kurt Rohloff

3. Duality Technology Inc., Newark, NJ, USA

   David B. Cousins & Yuriy Polyakov

Corresponding author

Correspondence to Giovanni Di Crescenzo .

Editors and Affiliations

1. University of Calgary, Calgary, AB, Canada

   Ken Barker

2. State University of New York at Canton, Canton, NY, USA

   Kambiz Ghazinour

A Basic Notations and Definitions

The expression \(\{0,1\}^n\) denotes the set of n-bit strings, where n is a positive integer. If S is a set, the expression \(x\leftarrow S\) denotes the probabilistic process of uniformly and independently choosing x from S. If A is an algorithm, the expression \(y\leftarrow A(x_1,x_2,\ldots )\) denotes the probabilistic process of running algorithm A on input \(x_1,x_2,\ldots \) and any random coins, and obtaining y as output.

A function \(\epsilon \) over the set of natural numbers \(\mathbb {N}\) is negligible in n if for every polynomial p, there exists an \(n_0\) such that \(\epsilon (n)<1/p(n)\), for all integers \(n\ge n_0\).

Two distribution ensembles \(\{D^0_\sigma :\sigma \in \mathbb {N}\}\) and \(\{D^1_\sigma :\sigma \in \mathbb {N}\}\) are computationally indistinguishable if for any efficient algorithm A, the quantity

is negligible in \(\sigma \) (i.e., no efficient algorithm can distinguish if a random sample came from one distribution or the other).

B Cryptographic Program Obfuscation: Previous Models

1.1 B.1 Cryptographic Program Obfuscation: Original Model

Cryptographic program obfuscation schemes are usually defined as a pair of algorithms: an obfuscation generator and an obfuscation evaluator. On input the original program, the obfuscation generator returns an obfuscated version of it, called the obfuscated program. On input the obfuscated program and a program input, the obfuscation evaluator, returns an output, which is intended to be the same as the original program’s output for this program input. Program obfuscation schemes are required to satisfy the following requirements: preserving the same computation, adding low runtime overhead and offering the same security as a (virtual) black box. The latter says, informally, that any efficient adversary’s output bit on input the obfuscated program can be efficiently simulated given access to a black box computing the program. Now we proceed more formally.

Definition 1

We define a program obfuscation scheme for family of functions F as a pair (oGen, oEval) of algorithms satisfying the following syntax

1. 1.

   on input parameter values pv, sv of function \(f_{pv,sv}\in F\), the obfuscation generator algorithm oGen returns an output, denoted as gout, which is intended to be an obfuscated version of \(f_{pv,sv}\).

2. 2.

   on input parameter values pv and the obfuscation gout, the obfuscation evaluator algorithm oEval returns an output, which we denote as eout, which is intended to be the original program’s output, when run on input x;

and the following requirements:

1. 1.

   Computation Correctness: Except with very small probability, it holds that \(eout=f_{pv,sv}(x)\).

2. 2.

   Low Runtime Overhead: oGen’s runtime is only polynomially slower than the circuit computing \(f_{pv,sv}\).

3. 3.

   Virtual-Black-Box Obfuscation: Any efficient adversary’s output bit on input the obfuscated program can be efficiently simulated given access to a black box computing the program. A bit more formally: for any efficient adversary Adv given pv, gout as input, there exists an efficient simulator algorithm Sim given pv as input and given oracle access to a black box computing \(f_{pv,sv}\), such that the probability that Adv returns 1 and the probability that Sim returns 1 only differ by a negligible amount.

1.2 B.2 Cryptographic Obfuscation of Classifiers

We review the definition of cryptographic obfuscation of classifiers, from [9].

In line with the Kerckhoff’s principle of modern cryptography, this definition assumes that the description of algorithms CTrain and CMatch is known to an adversary, while the dataset ds and the matching auxiliary input maux returned by CTrain are not. An intrusion attack to a classifier is defined as an attack capable of obtaining the matching auxiliary input maux returned by CTrain on input ds and a class number c. Accordingly, classifiers are defined so that an intrusion attack does not leak any true/false property about maux, other than what possibly leaked by the capability of performing remote calls to algorithm CMatch\((\cdot ,maux)\). In other words, the classifier CMatch\((\cdot ,maux)\) would look to an adversary very much like a virtual black box, in the sense of Definition 1. Specifically, this intrusion-resiliency notion for classifiers says that an adversary’s 1-bit output obtained when given as input the output maux of algorithm CTrain can be simulated, up to a small error, by the output of an efficient algorithm Sim that does not know maux but can query the algorithm CMatch as an oracle. More formally, the classifier (CTrain, CMatch) satisfies intrusion resiliency with respect to dataset distribution D if for all probabilistic polynomial-time algorithms A, there exists a probabilistic polynomial-time algorithm Sim with black-box access to Cmatch\((\cdot ,maux)\) such that the quantity

is negligible in the security parameter k, where the probability experiments \(\mathrm{AdvExp}_\mathrm{A},\mathrm{SimExp}_\mathrm{Sim}\) are detailed below.

1.3 B.3 Encrypted-Input Obfuscation: The Model

This model, introduced in [10], extends the original 2-algorithm model of program obfuscation (including an obfuscation generator an an obfuscation evaluator, as reviewed in Appendix B.1) to a 4-algorithm model that additionally includes a key generator and an input encryptor. The key generator returns a random key to be used by the obfuscation generator to generate its obfuscation of the program and by the input encryptor to generate an encrypted input on which the obfuscation evaluator can be run. The changes to the computation correctness requirement are only of syntactic nature. The runtime requirements extend to the input generation algorithm as well. The obfuscation property is strengthened in that the adversary’s output on input the obfuscated program can be efficiently simulated by an algorithm given only public information and, in particular, without need for black-box access to the original program.

Definition 2

Let F be a family of functions. We define an encrypted-input program obfuscator for F as a 4-tuple (kGen, oGen, iEnc, oEval) of algorithms satisfying the following syntax:

1. 1.

   on input a security parameter, the key generator algorithm kGen returns a random key k

2. 2.

   on input k, and parameter values pv, sv of function \(f_{pv,sv}\in F\), the obfuscation generator algorithm oGen returns an output, denoted as gout, which is intended to be an obfuscated version of \(f_{pv,sv}\), and an output, denoted as iaux, intended to be an auxiliary input for the input encryptor algorithm.

3. 3.

   on input k, parameter values pv of function \(f_{pv,sv}\in F\), auxiliary input iaux, and input x, the input encryptor algorithm iEnc returns an output, denoted as iout, intended to be an encrypted version of input x to function \(f_{pv,sv}\);

4. 4.

   on input parameter values pv, the obfuscation gout and the encrypted input iout, the obfuscation evaluator algorithm oEval returns an output, which we denote as eout, which is intended to be the original program’s output, when run on input x;

and the following requirements:

1. 1.

   Computation Correctness: Except with very small probability, it holds that \(eout=f_{pv,sv}(x)\).

2. 2.

   Low Runtime Overhead: the sum of iEnc and oGen’s runtime is only polynomially slower than the circuit computing \(f_{pv,sv}\).

3. 3.

   Simulated-view Obfuscation: The obfuscated program returned by algorithm oGen can be efficiently simulated given only the program’s public parameters. Formally, there exists a polynomial-time algorithm Sim such that for any function \(f_{pv,sv}\) from the class of function F, and any distribution hD returning secret parameter values sv with high min-entropy, the distributions \(D_{view}\) and \(D_{sim}\) are computationally indistinguishable, where

   $$\begin{aligned} D_{view} \, =&\{sv\leftarrow hD;\, k\leftarrow kGen(1^\sigma ); gout\leftarrow oGen(k,pv,sv)\,:\, gout\}, \\ D_{sim} \, =&\{gout\leftarrow Sim(1^\sigma ,pv)\,:\, gout\}. \end{aligned}$$

CEncrypted-Input Classifier Obfuscation: Formal Model

Let F be a function and let MC = (CTrain,CMatch) a matching classifier for F, as defined in Sect. 2.1. The public parameter values of MC, denoted as pv(MC), are available to all parties, including an attacker. The secret parameter values of MC, denoted as sv(MC), are only available to the obfuscation generator. In our model, we will consider the description of CTrain and CMatch as being known to the attacker, while the dataset, the secret data sample and its class as unknown to the attacker. Thus, we have that pv = (desc(CTrain), desc(CMatch), n, N) and \(sv=(ds,cl,d_0,c_0)\), where \(c_0=cF(d_0)\). An encrypted-input obfuscator for MC is defined as a 4-tuple of algorithms: a key generator, an obfuscation generator, an input encryptor, and an obfuscation evaluator; which need to satisfy 3 properties: computation correctness, low runtime overhead and simulated-view obfuscation.

Definition 3

Let F be a function and let MC = (CTrain, CMatch) be a matching classifier for F. We define an encrypted-input program obfuscator for matching classifier MC as a 4-tuple icO = (kGen, oGen, iEnc, oEval) of algorithms satisfying the following syntax

1. 1.

   on input a security parameter, the key generator algorithm kGen returns a random key k

2. 2.

   on input key k, public parameter values pv(MC) and secret parameter values sv(MC) for classifier MC, the obfuscation generator algorithm oGen returns an output, denoted as gout, which is intended to be an obfuscated version of MC, and an output, denoted as iaux, which is intended to be an encryption auxiliary input for the input encryptor algorithm iEnc.

3. 3.

   on input key k, public parameter values pv(MC) for MC, encryption auxiliary input iaux, and data input d, the input encryptor algorithm iEnc returns an output, denoted as iout, which is intended to be an encrypted version of input d to algorithm CMatch;

4. 4.

   on input public parameter values pv(MC), the obfuscation gout and the encrypted input iout, the obfuscation evaluator algorithm oEval returns an output, which we denote as eout. The latter is intended to be equal to CMatch’s output, when run on input d, maux, where maux has been returned by algorithm CTrain on input \(ds,cl,d_0\);

and the following requirements:

1. 1.

   Computation Correctness: Except with very small probability, it holds that \(eout=\) CMatch(d, maux), where \(maux=\) CTrain\((ds,cl,d_0)\).

2. 2.

   Low Runtime Overhead: the sum of iEnc and oGen’s runtime is not significantly slower than the program computing CMatch with public parameter values pv(MC) and secret parameter values sv(MC).

3. 3.

   Simulated-view Obfuscation: The obfuscated program returned by algorithm oGen can be efficiently simulated given only the program’s public parameters pv(MC). Formally, there exists a polynomial-time algorithm Sim such that for any matching classifier MC for function F, and any distribution hD returning secret parameter values sv(MC) with high min-entropy, the distributions \(D_{view}\) and \(D_{sim}\) are computationally indistinguishable, where

   • \(D_{view} \, = \{sv(MC)\leftarrow hD;\, k\leftarrow kGen(1^n);\)

     \(\qquad \qquad gout\leftarrow oGen(k,pv(MC),sv(MC))\,:\, gout\},\)

   • \(D_{sim} \, = \{gout\leftarrow Sim(1^n,pv(MC))\,:\, gout\}\).

Reprints and permissions

© 2021 IFIP International Federation for Information Processing

Policies and ethics