Statistical Zeroizing Attack: Cryptanalysis of Candidates of BP Obfuscation over GGH15 Multilinear Map

We present a new cryptanalytic algorithm on obfuscations based on GGH15 multilinear map. Our algorithm, statistical zeroizing attack, directly distinguishes two distributions from obfuscation while it follows the zeroizing attack paradigm, that is, it uses evaluations of zeros of obfuscated programs.

Our attack breaks the recent indistinguishability obfuscation candidate suggested by Chen et al. (CRYPTO’18) for the optimal parameter settings. More precisely, we show that there are two functionally equivalent branching programs whose CVW obfuscations can be efficiently distinguished by computing the sample variance of evaluations.

This statistical attack gives a new perspective on the security of the indistinguishability obfuscations: we should consider the shape of the distributions of evaluation of obfuscation to ensure security.

In other words, while most of the previous (weak) security proofs have been studied with respect to algebraic attack model or ideal model, our attack shows that this algebraic security is not enough to achieve indistinguishability obfuscation. In particular, we show that the obfuscation scheme suggested by Bartusek et al. (TCC’18) does not achieve the desired security in a certain parameter regime, in which their algebraic security proof still holds.

The correctness of statistical zeroizing attacks holds under a mild assumption on the preimage sampling algorithm with a lattice trapdoor. We experimentally verify this assumption for implemented obfuscation by Halevi et al. (ACM CCS’17).

1. 1.

   That is, our attack is lying outside the considered attack class in [4].

2. 2.

   The difference of variance is even not enough to distinguish. For example, the distributions that 0 with overwhelming probability cannot be efficiently distinguished though these can have any variance.

3. 3.

   Though there is a general transformation from permutation branching program into Type I branching program [10, Claim 6.2], this induces the bookend vector of the form \((\mathbf{v}|-\mathbf{v})\) rather than the implicitly supposed bookend \(\varvec{1}^{1 \times w}\) in CVW obfuscation. If we directly obfuscate permutation branching programs, the functionality of them is all-rejection. Indeed, if we obfuscate permutation branching programs using CVW obfuscation as this trivial functionality (without transformation), the iO security for these trivial BPs can be proven by the proof technique of [7].

4. 4.

   As noted in the remark of introduction, it is assumed implicitly that \(\mathbf{v}= \varvec{1}^{1\times w}\) for the targeted BP, while the definition of Type I BP uses \(\mathbf{v}\in \{ 0,1\}^{1\times w}\).

5. 5.

   Indeed, the attack requires the condition \(\sigma ^4 < m^\ell /n^{\ell +1}\).

6. 6.

   We also verify the correctness of the attack itself for [23], but with large entry BPs. It requires very large number of samples (say \(2^{20}\) but polynomially many) to verify the attack with binary entry BPs, which is not easy to experiment because the obfuscation/evaluation of [23] takes long time (say few minutes to obtain one evaluation).

We sincerely thank to James Bartusek, Fermi Ma and anonymous reviewers of Eurocrypt 2019 for noting the errors in the earlier version of this paper. We also thank to the anonymous reviewers of Crypto 2019 for their careful comments.

The authors of Seoul National University were supported by Institute for Information & communication Technology Promotion (IITP) grant funded by the Korea government (MSIT) (No. 2016-6-00598, The mathematical structure of functional encryption and its analysis), and the ARO and DARPA under Contract No. W911NF-15-C-0227. The author of ENS de Lyon was supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).

Authors and Affiliations

1. Department of Mathematical Sciences, SNU, Seoul, Republic of Korea

   Jung Hee Cheon, Wonhee Cho, Minki Hhan & Jiseung Kim

2. Research Institute of Mathematics (RIM), SNU, Seoul, Republic of Korea

   Jung Hee Cheon

3. Cryptolab, Seoul, Republic of Korea

   Jung Hee Cheon

4. ENS de Lyon, Laboratoire LIP (U. Lyon, CNRS, ENSL, INRIA, UCBL), Lyon, France

   Changmin Lee

Corresponding author

Correspondence to Jiseung Kim .

Editors and Affiliations

1. Georgia Institute of Technology, Atlanta, GA, USA

   Alexandra Boldyreva

2. University of California at San Diego, La Jolla, CA, USA

   Daniele Micciancio

A Simple GGH15 Obfuscation

We briefly describe the construction of single input BP obfuscation based GGH15 without safeguard.

For an index to input function \(\mathsf{inp}:[h] \rightarrow [\ell ]\), let

be a single input BP.

For parameters \(w,m,q,B \in {\mathbb {N}}\) and \(\sigma \in {\mathbb {R}}^{+}\), the BP obfuscation based GGH15 consists of the matrices and input function, namely

In this case, the matrix \(\mathbf{T}\) in the abstract model is the identity matrix and \(\mathbf{S}= \mathbf{A}_0\). The output of the obfuscation at \(\mathbf{x}\) is computed as follows: compute the matrix \(\mathbf{A}_0 \cdot \prod _{i=1}^h\mathbf{D}_{i,x_{\mathsf{inp}(i)}} \bmod q\) and compare its \(\Vert \cdot \Vert _{\infty }\) to a zerotest bound B. If it is less than B, outputs zero. Otherwise, outputs 1.

The algorithm to construct an obfuscated program \(\mathcal {O}(\mathbf{P})\) proceeds as follows:

• Sample matrices \((\mathbf{A}_i,\tau _i) \leftarrow \mathsf{TrapSam}(1^w, 1^m, q)\) for \(i=0,1,\cdots ,h-1\), \(\mathbf{A}_h \leftarrow U({{\mathbb {Z}}}_{q}^{w \times m})\) and \(\mathbf{E}_{i,b} \leftarrow \chi ^{w \times m}\) where \(\chi \) is a distribution related to the hardness of LWE problem.

• By using the trapdoor \(\tau _i\), sample matrices

  $$\begin{aligned} \mathbf{D}_{i,b} \in {{\mathbb {Z}}}^{m \times m}\leftarrow \mathsf{Sample}(\mathbf{A}_{i-1},\tau _{i-1},\mathbf{P}_{i,b}\cdot \mathbf{A}_i + \mathbf{E}_{i,b},\sigma ) \text { with } 1\le i \le h. \end{aligned}$$

• Output matrices \(\{\mathbf{A}_0, \{\mathbf{D}_{i,b} \in {{\mathbb {Z}}}^{m \times m}\}_{i\in [h],b \in \{0,1\}} \}\).

Then, we observe the product \(\mathcal {O}(\mathbf{P})(\mathbf{x}) = [\mathbf{A}_0 \cdot \prod _{i=1}^h\mathbf{D}_{i,x_{\mathsf{inp}(i)}}]_q\) is equal to

over \({{\mathbb {Z}}}_q\). If \(\prod _{i=1}^h \mathbf{P}_{i,x_{\mathsf{inp}(i)}} = {\varvec{0}}^{w \times w}\), then \(\mathcal {O}(\mathbf{P})(\mathbf{x})\) can be regarded as a summation of matrices over integers instead of \({{\mathbb {Z}}}_q\) under the certain choice of parameters as follows

since the infinity norm of the above matrix is less than \(B \ll q\). Note that the evaluation values only rely on the matrices \(\mathbf{P}_{i,b}\), \(\mathbf{E}_{i,b}\) and \(\mathbf{D}_{i,b}\). Thus, the evaluation result depends on the message matrices \(\mathbf{P}_{i,b}\).

Suppose that we have two functionally equivalent BPs \(\mathbf{M}= \{ \mathbf{M}_{i,b}\}_{i \in [h], b \in \{0,1\}}\) and \(\mathbf{N}= \{ \mathbf{N}_{i,b}\}_{i \in [h], b \in \{0,1\}}\) satisfies

and an obfuscated program \(\mathcal {O}(\mathbf{P})\). The goal of adversary is to determine whether \(\mathbf{P}\) is \(\mathbf{M}\) or not. For all \(\mathbf{x}\in \{0,1 \}^{\ell }\), the evaluation of the obfuscation is of the form

Note that they correspond to the distributions \(\mathcal {D}_\mathbf{M}\) and \(\mathcal {D}_\mathbf{N}\) for a fixed vector \(\mathbf{x}\). These equations show the difference of two distributions in this case.

B Modified CVW Obfuscation

We give a modification of CVW obfuscation, which can obfuscate the permutation matrix branching programs. This modification is, as far as we know, robust against all existing attacks. We first describe the transformation of branching programs. Then, we describe the modification of CVW obfuscation.

1.1 B.1 Transformation of Branching Programs

We first introduce the transformation from single-input permutation matrix branching programs to Type I BP. This transformation is applicable to BPs which outputs 0 when the product of BP matrices is the identity matrix. The output of transformation is a new branching program that outputs 0 when the product of BP matrices is the zero matrix. Through this transformation, the width of branching program is doubled. Note that this is adapted version of [10, Claim 6.2].

We are given a branching program with input size \(\ell \)

where the evaluation of \(\mathbf{P}\) at \(\mathbf{x}\in \{0,1\}^{\ell }\) is computed by

Then the transformation is done by changing branching program matrices as

and the evaluation is similar but uses new vectors \(\mathbf{v}' = (\mathbf{v}|-\mathbf{v})\) and \(\mathbf{w}' = (\mathbf{w}| \mathbf{w})\) for \(\mathbf{v},\mathbf{w}\in {{\mathbb {Z}}}^w\):

We will choose \(\mathbf{v}\) and \(\mathbf{w}\) as random Gaussian vectors. Note that the resulting branching program is also a permutation BP.

1.2 B.2 Modification of CVW Obfuscation

We give here how to modify the CVW obfuscation to be applicable to the resulting permutation BPs of the above transform. We also assume that the index length \(h =(\lambda +1)\cdot \ell \) and the index-to-input function satisfies \(\mathsf{inp}(i) = (i \mod \ell )\) as in the CVW obfuscation. We also assume that the BP is \((\lambda +1)\)-input repetition BP as in the original construction. The changed parts are written in red. Note that the targeted BPs have width 2w. Thus we set \(t:=(2w+2n\ell )\cdot n\).

• Sample bundling matrices \(\{\mathbf{R}_{i,b} \in {{\mathbb {Z}}}^{2n\ell \times 2n\ell }\}_{i \in [h], b \in \{0,1\} }\) such that \((\varvec{1}^{1 \times 2\ell }\otimes \mathbf{I}^{n\times n})\cdot \mathbf{R}_{\mathbf{x}'}\cdot (\varvec{1}^{2\ell \times 1}\otimes \mathbf{I}^{n\times n}) = \varvec{0}\) \(\iff \) \(\mathbf{x}' \in \bar{\omega }(\{ 0,1\}^{\ell })\) for all \(\mathbf{x}' \in \{ 0,1\}^{h}\). More precisely, \(\mathbf{R}_{i,b}\) is a block diagonal matrix \(\mathsf{diag}( \mathbf{R}^{(1)}_{i,b},\mathbf{R}^{(2)}_{i,b},\cdots ,\mathbf{R}^{(\ell )}_{i,b})\). Each \(\mathbf{R}^{(k)}_{i,b} \in {{\mathbb {Z}}}^{2n \times 2n}\) is one of the following three cases.

  $$\begin{aligned} \mathbf{R}^{(k)}_{i,b} = {\left\{ \begin{array}{ll} \mathbf{I}^{2n \times 2n} &{} \text { if } \mathsf{inp}(i) \ne k \\ \begin{pmatrix} \tilde{\mathbf{R}}^{(k)}_{i,b} &{} \\ {} &{} \mathbf{I}^{n \times n} \end{pmatrix} , \tilde{\mathbf{R}}^{(k)}_{i,b} \leftarrow \mathcal {D}_{{{\mathbb {Z}}},\sigma }^{n \times n} &{} \text { if } \mathsf{inp}(i) = k \text { and } i \le \lambda \ell \\ \begin{pmatrix} -\mathbf{I}^{n \times n} &{} \\ {} &{} \displaystyle \prod _{j=0}^{\lambda -1} \tilde{\mathbf{R}}^{(k)}_{k+j\ell ,b} \end{pmatrix}&\text { if } \mathsf{inp}(i) = k \text { and } i > \lambda \ell \end{array}\right. } \end{aligned}$$

• Sample matrices \(\{\mathbf{S}_{i,b} \leftarrow \mathcal {D}^{n \times n}_{{{\mathbb {Z}}}, \sigma } \}_{i \in [h], b \in \{0,1\}}\), bookend vectors \(\mathbf{v}\leftarrow \mathcal {D}_{{{\mathbb {Z}}},\sigma }^w\) and \(\mathbf{w}\leftarrow \mathcal {D}_{{{\mathbb {Z}}},\sigma }^w\) and compute

  $$\begin{aligned}&\mathbf{J}:= ({(\mathbf{v}|-\mathbf{v}|\varvec{1}^{1 \times 2n\ell })} \otimes \mathbf{I}^{n\times n}) \in {{\mathbb {Z}}}^{n \times t} \\&{\hat{\mathbf{S}}}_{i,b} : = \begin{pmatrix} \mathbf{P}_{i,b} \otimes \mathbf{S}_{i,b} &{} \\ {} &{} \mathbf{R}_{i,b} \otimes \mathbf{S}_{i,b} \end{pmatrix} \in {{\mathbb {Z}}}^{t \times t} \\&\mathbf{L}:= ({(\mathbf{w}| \mathbf{w}| \varvec{1}^{1\times 2n\ell })^T}\otimes \mathbf{I}^{n\times n}) \in {{\mathbb {Z}}}^{t \times n} \end{aligned}$$

• Sample \((\mathbf{A}_i,\tau _i) \leftarrow \mathsf{TrapSam}(1^t,1^m,q)\) for \(0 \le i \le h-1\), \(\mathbf{A}_h \leftarrow U({{\mathbb {Z}}}^{n \times n}_q)\), \( \{\mathbf{E}_{i,b} \leftarrow \mathcal {D}^{t \times m}_{{{\mathbb {Z}}}, \sigma }\}_{i \in [h-1], b \in \{0,1\} }\) and \(\{\mathbf{E}_{h,b}\leftarrow \mathcal {D}^{t \times n}_{{{\mathbb {Z}}}, \sigma } \}_{b \in \{0,1\}}\).

• Run \(\mathsf{Sample}\) algorithms to obtain

  $$\begin{aligned}&\mathbf{D}_{i,b} \in {{\mathbb {Z}}}^{m \times m}\leftarrow \mathsf{Sample}(\mathbf{A}_{i-1},\tau _{i-1},\hat{\mathbf{S}}_{i,b}\cdot \mathbf{A}_i + \mathbf{E}_{i,b},\sigma ) \text { for } 1\le i \le h-1, \\&\mathbf{D}_{h,b} \in {{\mathbb {Z}}}^{m \times n} \leftarrow \mathsf{Sample}(\mathbf{A}_{h-1},\tau _{h-1},{\hat{\mathbf{S}}}_{h,b} \cdot \mathbf{L}\cdot \mathbf{A}_h + \mathbf{E}_{h,b},\sigma ). \end{aligned}$$

• Define \(\mathbf{A}_{\mathbf{J}}\) as a matrix \(\mathbf{J}\cdot \mathbf{A}_0 \in {{\mathbb {Z}}}^{n \times m}\) and outputs matrices

  $$\begin{aligned} \left\{ \mathsf{inp}, \mathbf{A}_{\mathbf{J}}, \{\mathbf{D}_{i,b}\}_{i \in [h], b \in \{0,1\}} \right\} . \end{aligned}$$

We omit the procedure and correctness of evaluation that are almost the same as the original one.

C Assumptions of Lattice Preimage Sampling

In this section we provide the experimental results of Assumption 1. Our experiments are built upon the preimage sampling algorithm in the [24], an implementation of BP obfuscation [23].^{Footnote 6} The results imply that the variance and kurtosis move almost the same as one assumed independency, the correctness of attack only requires much relaxed assumption (Table 1).

Reprints and permissions

© 2019 International Association for Cryptologic Research

Policies and ethics