Uogólnienie schematu GGH13 na szyfrowanie macierzy. Używa NTRU Prime i szyfrowania macierzy opartego na lemacie Ishai i Kushilevitza. Tym razem po angielksu.

Abstract. We propose a generalization of the obfuscation scheme based on GGH13 multilinear map, which security is based on the hardness of NTRU problem. In 2014 Bernstein et al. proposed NTRU Prime scheme, which in contradiction to NTRU Classic and NTRU NTT uses irreducible polynomial to create quotient ring. It enables us to represent plaintext program as a sequence of matrices over a finite field in our scheme. To encrypt matrices over a field we use perfectly secure encryption proposed by Ishai and Kushievitz (also used for program obfuscation with ADP representation by Bartusek et al. We use specially designed block matrices to annihilate noisy terms during evaluation of encrypted program. The security of the scheme is based on the matrix version of NTRU Problem and perfect security of encryption method. The efficiency of the scheme is derived from NTRU Prime efficiency, which uses Karatsuba multiplication to gain speed comparable to NTT implementations.

Introduction

Obfuscation is focused on encrypting functions, which are in general non-commutative. Using non-commutative algebraic structures seem to be natural approach to achieve that goal. Linearized functions may be presented as a product of matrices. In known solutions each matrix encrypts the value of fixed input variable and the function to be performed on that value. We give to the user matrices encrypting different values (typically bit values 0 or 1 for each input binary variable of obfuscated program), which he may choose during the program execution. User can choose only input values, while performed function is determined and kept secret. At the end of computations, thanks to public parameters of obfuscation scheme, user may decrypt the result.

There are three main obfuscation schemes based on multilinear maps: CLT13, GGH13 and GGH15. GGH13 and GGH15 are based on hard program in lattice-based cryptography, while CLT13 is integer-based version of GGH13 scheme and is not post-quantum. All schemes use matrix branching program representation, that using Barrington Theorem encodes a logic circuit of depth $d$ into product of at most $4^d$ matrices. Thanks to this result, one can embed arbitrary computations into the multiplicative group of matrices. The type of operations performed is then hidden in matrix elements and becomes a secret after encryption. The exponential growth of size such a representation is a main bottleneck of known obfuscation schemes.

Preliminaries

In this section we present main cryptographic tools to be used in the scheme. We do not introduce GGH13 multilinear map and obfuscation scheme, which have many details and are well described in previous papers.

NTRU prime

NTRU Prime was proposed by Bernstein et al. as an alternative for using cyclotomic polynomials in ideal-lattice-based cryptography. Instead, authors recommend to use irreducible polynomials with large Galois groups of extended finite fields (cyclotomic polynomials of degree $2^n$ used in NTRU NTT are reducible over any finite field and have small Galois groups). They especially recommend using irreducible polynomial $x^p-x-1$ and the finite field $R = \mathbb{Z}_q[x]/(x^p-x-1)$, where $p$ and $q$ are properly selected prime numbers. Authors proposed many selections of well chosen primes in the paper, while the first choice is $p=761$ and $q=4591$. NTRU Prime removes unnecessary algebraic structure, which have NTRU NTT quotient rings. As authors argue: having a much larger Galois group means that the polynomial will have at most a small number of roots in any field of reasonable degree, which eliminates all known methods of efficiently performing computations with more than a small number of automorphisms needed to perform attacks. They also emphasize, that there are no ring homomorphisms from $R$ to any smaller nonzero ring (some attacks start by applying such homomorphisms).

In application to program obfuscation, using NTRU Prime as a security guarantee let us represent the program by matrices over a field (not over a ring). In consequence we can use the concept of the rank of a matrix and encryption method proposed by Ishai and Kushilevitz.

NTRU prime matrix version

Problem NTRU was stated as the basis of NTRU cryptosystem. It can be reduced to the Shortest Vector Problem in ideal lattices (depending on the chosen polynomial ring $R$).

Definition: NTRU Problem Let $R$ be a polynomial ring and let $f,g \in R$ be polynomials of small norm and $h \in R$ be a polynomial such that:

\[f \cdot h = g \pmod{q}.\]

Knowing $h$ and $q$, find $f$ and $g$ of a small norm.

Matrix version of NTRU cryptosystem, based on matrix NTRU Problem was proposed by Coglianese and Goi \cite{matru} and by Nayak et al. \cite{matrix-ntru}. These and other NTRU generalization are described in the article \cite{ntru-general}.

Definition: Matrix NTRU Problem Let $M_k(R)$ be a ring of quadratic matrices of dimension $k$ over a polynomial ring $R$ and let $F,G \in M(R)$ be matrices of small norm and $H \in M_k(R)$ be a matrix such that:

\[F \cdot H = G \pmod{q}.\]

Knowing $H$ and $q$, find $F$ and $G$ of a small norm.

If matrix $H$ would be a circulant matrix corresponding to multiplication by polynomial $h$, the Matrix NTRU Problem could be presented as many parallel instances of NTRU problem:

\[f_1 \cdot H = g_1 \pmod{q},\] \[f_2 \cdot H = g_2 \pmod{q},\] \[\vdots\] \[f_k \cdot H = g_k \pmod{q},\]

where $k$ is dimension of matrices. However, Matrix NTRU Problem does not specify that matrix $H$ is circulant, which makes it more general.

Matrix norms

In GGH13 cryptosystem, to compare sizes of elements of polynomial ring, authors proposed to use maximum norm. For a polynomial $p$ the norm $|p|$ equals the absolute value of maximal polynomial coefficient. For matrix version of a cryptosystem, we propose to use norm maximum for matrices over ring of polynomials, defined as the absolute value of maximal polynomial coefficient for all matrix elements (polynomials).

Lemma Let $M_1$ and $M_2$ be $k \times k$ matrices over polynomial ring $R = \mathbb{Z}[x]/\langle f \rangle$, where $deg(f)=n$. Then:

\[\| M_1 \cdot M_2 \| \leqslant k \cdot poly(n) \cdot \| M_1 \| \cdot \| M_2 \|.\]

Proof Assuming that all polynomials has equal (maximal) coefficients, when multiplying two polynomials we get polynomial of maximal coefficient equal to $poly(n) \cdot |M_1| \cdot |M_2|$ (in GGH13 authors use cyclotomic ring in which for polynomials $a,b$ they use bound for their norm $|a\cdot b| \leqslant n \cdot |a| \cdot |b|$ it might be different for other polynomial $f$, but the norm growth will still be polynomial in $n$). Every element of product matrix is a sum of $k$ products of two polynomials, giving result stated in the Lemma.

Obfuscation scheme

Proposed obfuscation scheme is a generalization of GGH13 obfuscation scheme. We change parameters of the scheme and the encryption method, but obfuscation scheme and its technical details remains the same as in the GGHRSW scheme \cite{gghrsw13}. Apart form obfuscated program, we need to obfuscate the dummy program and subtract resulting matrices in the end. To counteract mixed-input attacks we need to use safeguards as in the original scheme (with an additional role described in the section Security).

In GGH13 obfuscation scheme matrix elements are encrypted in a following way:

\[m_i \rightarrow enc(m_i) = \frac{r_i g + m_i}{z_i} \pmod{q}.\]

As matrix multiplication is not commutative, we cannot divide the message’s coset by random matrix $Z_i$ (corresponding to element $z_i$ in one-dimensional scheme). Instead we multiply from both sides by matrices $Z_i$ and $Z_{i+1}^{-1}$:

\[M_i \rightarrow enc(M_i) = Z_i \cdot (R_i G + M_i) \cdot Z_{i+1}^{-1} \pmod{q}.\]

Please notice, that for random invertible matrices $Z_i$ and $Z_{i+1}$ we use encryption method proposed by Ishai and Kushilevitz. However, while for the numbers encryption is multiplicatively homomorphic, it is not true for matrices as:

\[enc(M_i) \cdot enc(M_{i+1}) = Z_i \cdot (R_i G + M_i) \cdot (R_{i+1} G + M_{i+1}) \cdot Z_{i+2}^{-1} =\] \[Z_i \cdot ((R_i G R_{i+1} + M_i R_{i+1}) G + R_i G M_{i+1} + M_i M_{i+1}) \cdot Z_{i+2}^{-1} \pmod{q}.\]

Encoding matrices

For simplicity of notation we consider encoding of only one matrix of each pair. The second matrix is encoded analogously with random parameters changed. We assume that matrices $M_i’$ (for $1 \leqslant i \leqslant K$) forming program are permutation matrices from the group $S_5$ (as in Barrington Theorem) multiplied by integer safeguards $M_i = t_i \cdot M_i’$ to counteract known attacks (see section Security). We encode matrices forming the program in a following way:

\[encode(M_1) = \left(\begin{array}{cc} R_{11} & R_{12} \\ R_{13} & R_{14} \\ \end{array}\right) \cdot \left(\begin{array}{cc} 0 & 0 \\ 0 & G \\ \end{array}\right) + \left(\begin{array}{cc} 0 & 0 \\ M_1 & 0 \\ \end{array}\right) = \left(\begin{array}{cc} 0 & R_{12} G\\ M_1 & R_{14} G\\ \end{array}\right),\] \[encode(M_i) = \left(\begin{array}{cc} R_{i1} & R_{i2} \\ R_{i3} & R_{i4} \\ \end{array}\right) \cdot \left(\begin{array}{cc} 0 & 0 \\ 0 & G \\ \end{array}\right) + \left(\begin{array}{cc} M_i & 0 \\ 0 & 0 \\ \end{array}\right) = \left(\begin{array}{cc} M_i & R_{i2} G\\ 0 & R_{i4} G\\ \end{array}\right),\] \[encode(M_K) = \left(\begin{array}{cc} R_{K1} & R_{K2} \\ R_{K3} & R_{K4} \\ \end{array}\right) \cdot \left(\begin{array}{cc} 0 & 0 \\ 0 & G \\ \end{array}\right) + \left(\begin{array}{cc} R_x & M_K \\ R_y & 0 \\ \end{array}\right) = \left(\begin{array}{cc} R_x & R_{K2} G + M_K\\ R_y & R_{K4} G\\ \end{array}\right).\]

Please notice that the product has the form:

\[encode(M_1) \cdot encode(M_2) = \left(\begin{array}{ll} 0 & R_{12} G\\ M_1 & R_{14} G\\ \end{array}\right) \cdot \left(\begin{array}{cc} M_2 & R_{22} G\\ 0 & R_{24} G\\ \end{array}\right) =\] \[= \left(\begin{array}{ll} 0 & R_{12} G \cdot R_{24} G\\ M_1 \cdot M_2 & M_1 \cdot R_{22}G + R_{14}G \cdot R_{24}G\\ \end{array}\right) = \left(\begin{array}{cc} 0 & R_{p22} G\\ M_1 \cdot M_2 & R_{p24}G\\ \end{array}\right),\]

which has the same structure as first encoded matrix and may be further multiplied by encoded matrices $M_i$. The last multiplication is different and the final product of matrices has the form:

\[\left(\begin{array}{cc} 0 & R_{p(K-1)2} G\\ \prod_{i=1}^{K-1} M_i & R_{p(K-1)4}G\\ \end{array}\right) \cdot \left(\begin{array}{cc} R_x & R_{K2} G + M_K\\ R_y & R_{K4} G\\ \end{array}\right) =\] \[= \left(\begin{array}{cc} R_{p(K-1)2} G \cdot R_y & R_{p(K-1)2} G \cdot R_{K4} G \\ \prod_{i=1}^{K-1} M_i \cdot R_x + R_{p(K-1)4}G \cdot R_y & \prod_{i=1}^{K-1} M_i \cdot R_{K2} G + \prod_{i=1}^{K} M_i + R_{p(K-1)4}G \cdot R_{K4} G\\ \end{array}\right) =\] \[= \left(\begin{array}{cc} R_{pK1} & R_{pK2} G \\ R_{pK3} & R_{pK4} G + \prod_{i=1}^{K} M_i \\ \end{array}\right).\]

If the final product of matrices $\prod_{i=1}^{K} M_i$ belongs to left ideal generated by $G$, the lower-right block of product of encoded matrices should also belong to the ideal. This property will be checked using zero-testing parameter, during the evaluation of encrypted program.

It is crucial that all encoded matrices are full rank. It is true, assuming that program consists of permutation matrices (as in Barrington Theorem).

Encrypting matrices

All encoded matrices are being encrypted using Lemma stated by Ishai and Kushilevitz applied to extended finite fields.

Lemma 1 Let $q$ be a power of a prime number and $\mathbb{Z}{q}$ be a finite field. For arbitrary matrix $A \in M{k \times k}(\mathbb{Z}q)$ and uniformly random invertible matrices $R,~S \in M{k \times k}(\mathbb{Z}_q)$ the distribution of a product $R \cdot A \cdot S$ depends only on the rank of matrix $A$.

As all matrices forming encoded program are full rank, encrypted matrices are indistinguishable from random full rank matrices.

Zero-testing

After performing all planed multiplications we achieve a ciphertext of a form:

\[U = Z_0 \cdot \prod_{i=1}^K encode(M_i) \cdot Z_K^{-1} \pmod{q}.\]

To test if result of computations is zero we multiply the result by public zero-test parameter:

\[p_{zt} = Z_K \cdot encode(G^{-1}) \cdot H \pmod{q},\]

where:

\[encode(G^{-1}) = \left(\begin{array}{cc} 0 & 0 \\ 0 & G^{-1} \\ \end{array}\right),\]

such that:

\[encode(G) \cdot encode(G^{-1}) = encode(Id).\]

After performing multiplication we get the result:

\(W = U \cdot p_{zt} = Z_0 \cdot \left (R \cdot encode(G) + \prod M_i' \right) encode(G^{-1}) \cdot H =\) \(= Z_0 \cdot \left (R \cdot encode(Id) + \prod_{i=1}^K encode(M_i) \cdot encode(G^{-1}) \right) \cdot H \pmod{q}.\)

It can be presented in the block form as follows:

\[W = \left(\begin{array}{cc} Z_{01} & Z_{02} \\ Z_{03} & Z_{04} \\ \end{array}\right) \cdot \left( \left(\begin{array}{cc} 0 & R_{pK2} \\ 0 & R_{pK4} \\ \end{array}\right) + \left(\begin{array}{cc} 0 & 0\\ 0 & \prod_{i=1}^K M_i \cdot G^{-1} \\ \end{array}\right) \right) \cdot \left(\begin{array}{cc} H_{1} & H_{2} \\ H_{3} & H_{4} \\ \end{array}\right).\]

If the resulting matrix $W$ has a small norm, we conclude that the matrix product must belong to ideal generated by G and hence the output is zero, otherwise it represents nonzero coset of ideal generated by G and the output is one. As the random blocks are chosen to be small, the only block that needs to be examined is the one containing product $ \prod_{i=1}^K M_i \cdot G^{-1}$.

Proof of correctness

According to previous sections the final result of computations is of the form:

\[U = Z_0 \cdot C \cdot Z_K^{-1} \pmod{q},\]

where $C = \prod_{i=1}^K encode(M_i) \cdot encode(G)$ and has a block form:

\[C = \left(\begin{array}{cc} C_1 & C_2 \\ C_3 & C_4 \\ \end{array}\right) = \left(\begin{array}{cc} R_{pK1} & R_{pK2} G \\ R_{pK3} & R_{pK4} G + \prod_{i=1}^{K} M_i \\ \end{array}\right).\]

Multiplied by public zero-test parameter:

\[W = U \cdot p_{zt} = Z_0 \cdot C \cdot encode(G^{-1}) \cdot H \pmod{q}.\]

Let’s analyze two possibilities:

1. $C_4$ belongs to ideal $I = \langle G \rangle$,

2. $C_4$ represents nonzero coset of ideal $I$.

We would like to show, that in case 1:

\[\|W\| = \|Z_0 \cdot C \cdot encode(G^{-1}) \cdot H \| \leqslant q^{\frac{3}{4}}\]

and in case 2:

\[\|W\| \approx q.\]

Ciphertext belonging to the ideal

First inequality can be achieved by proper choice of parameters:

\[\|Z_0 \cdot C \cdot encode(G^{-1}) \cdot H \| \leqslant poly(k) \cdot poly(n) \cdot \|Z_0 \| \cdot \|C \cdot encdoe(G^{-1})\| \cdot \|H\| \stackrel{(1)}{\leqslant}\] \[\stackrel{(1)}{\leqslant} poly(k) \cdot poly(n) \cdot \|Z_0 \| \cdot \|C\| \cdot \|H\|,\]

where $k$ is matrix dimension and $n$ is a degree of polynomial used for construction of ring $R_q$. If we choose random matrices $Z_0$ and $H$ having norm smaller than $q^{\frac{1}{4}}$ and if we assume that the norm of ciphertext $C$ must be always lower than $q^{\frac{1}{8}}$ (from the construction), then the norm of $W$ is lower than $q^{\frac{5}{8}}$, which is lower than $q^{\frac{3}{4}}$ with additional margin. Inequality $(1)$ follows from the fact that if $C_2$ and $C_4$ lie in the ideal generated by $G$, then they have a forms: $C_2 = C_2’\cdot G$ and $C_4 = C_4’\cdot G$ for some matrices $C_2’$ and $C_4’$ respectively. In consequence:

\[C \cdot encode(G^{-1}) = \left(\begin{array}{cc} C_1 & C_2' G \\ C_3 & C_4' G \\ \end{array}\right) \cdot \left(\begin{array}{cc} 0 & 0 \\ 0 & G^{-1} \\ \end{array}\right) = \left(\begin{array}{cc} 0 & C_2' \\ 0 & C_4' \\ \end{array}\right),\]

and:

\[\|C \cdot encode(G^{-1})\| = \|C'\| \leqslant \|C' \cdot encode(G)\| = \|C\|,\]

because both norms $|C_2’|$, $|C_4’|$ and $|encode(G)|$ are much lower then $q$ and there are no modular reductions during multiplication.

Ciphertext not belonging to the ideal

Trying to prove case 2, we have encountered many problems with lack of factorization in matrix rings. Eventually, we managed to show its correctness for matrices:

\[G = g \cdot Id = \left(\begin{array}{cccc} g & 0 & \cdots & 0 \\ 0 & g & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & g \\ \end{array}\right) ,~~~ G^{-1} = g^{-1} \cdot Id = \left(\begin{array}{cccc} g^{-1} & 0 & \cdots & 0 \\ 0 & g^{-1} & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & g^{-1} \\ \end{array}\right)\]

by considering individual matrix elements. For more complicated matrices $G$, the prove should be analogical, but more complicated due to the fact that ideal $I$ related to matrix ideal generated by $\langle G \rangle=M(I)$ would have many generators. To analyze the structure of matrix elements, we first write matrices in their block form and then specify equations describing individual elements.

Transition to block matrices

Let’s consider block form matrix $W = U \cdot p_{zt}$:

\[W = \left(\begin{array}{cc} Z_{01} & Z_{02} \\ Z_{03} & Z_{04} \\ \end{array}\right) \cdot \left( \left(\begin{array}{cc} 0 & R_{pK2} \\ 0 & R_{pK4} \\ \end{array}\right) + \left(\begin{array}{cc} 0 & 0 \\ 0 & \prod_{i=1}^K M_i \cdot G^{-1} \\ \end{array}\right) \right) \cdot \left(\begin{array}{cc} H_{1} & H_{2} \\ H_{3} & H_{4} \\ \end{array}\right).\]

As random matrices are chosen to have sufficiently small norms, we only need to consider the yellow block matrix $\prod_{i=1}^K M_i \cdot G^{-1}$, which depends on the product of matrices that lies or not in ideal generated by $G$.

Let’s consider the matrix:

\[W_M = \left(\begin{array}{cc} W_{M1} & W_{M2} \\ W_{M3} & W_{M4} \\ \end{array}\right) = \left(\begin{array}{cc} Z_{01} & Z_{02} \\ Z_{03} & Z_{04} \\ \end{array}\right) \cdot \left(\begin{array}{cc} 0 & 0\\ 0 & \prod_{i=1}^K M_i \cdot G^{-1} \\ \end{array}\right) \cdot \left(\begin{array}{cc} H_{1} & H_{2} \\ H_{3} & H_{4} \\ \end{array}\right) = .\] \[= \left(\begin{array}{cc} Z_{02} \cdot \left( \prod_{i=1}^K M_i \cdot G^{-1} \right) \cdot H_3 & Z_{02} \cdot \left( \prod_{i=1}^K M_i \cdot G^{-1} \right) \cdot H_4 \\ Z_{04} \cdot \left( \prod_{i=1}^K M_i \cdot G^{-1} \right) \cdot H_3 & Z_{04} \cdot \left( \prod_{i=1}^K M_i \cdot G^{-1} \right) \cdot H_4 \\ \end{array}\right).\]

Because norm of $W_M$ depends on the norm of its biggest element and resulting block matrices have the same structure, we can focus our attention on the first block only (for others conclusions will be the same).

Transition to matrix elements

Let’s consider the first block matrix:

\[W_{M1} = Z_{02} \cdot \left( \prod_{i=1}^k M_i \cdot G^{-1} \right) \cdot H_3 = g^{-1} \cdot Z_{02} \cdot \prod_{i=1}^k M_i \cdot H_3 \pmod{q}\]

and let’s take a look at its elements. To focus attention, let’s consider the first element of matrix $W_{M1}$, which is of the form:

\[w_1 = g^{-1} \cdot \sum_{i=1}^l \sum_{j=1}^l z_{1j} \cdot m_{ji} \cdot h_{i1} \pmod{q},\]

where $Z_{02} = (z_{ij})$ and $H_2=(h_{ij})$ and assuming that all matrices are quadratic of dimension $l$. In consequence:

\[w_1 g = \sum_{i=1}^l \sum_{j=1}^l z_{1j} \cdot m_{ji} \cdot h_{i1} \pmod{q}.\]

We give a sketch of the prove for Lemma 2 similar to lemma in GGH13 multilinear map. We assume that matrices being encrypted are permutation matrices (which has only binary elements 0 or 1) multiplied by integer safeguards (defined in the Section Security). In consequence matrix elements are either 0 or $t$, for some integer~$t$.

Lemma 2 Suppose $m_{ij} \in {0,t}$ for positive integer $t$ and suppose that:

\[w_k g = \sum_{i=1}^l \sum_{j=1}^l z_{kj} \cdot m_{ji} \cdot h_{ik} \pmod{q}\]

for $1 \leqslant k \leqslant l^2$ and $|w_k g|$ and $|\sum_{i=1}^l \sum_{j=1}^l z_{kj} \cdot m_{ji} \cdot h_{ik}|$ are smaller than $q/2$, for random elements $z_{kj}$ and $h_{ik}$ that does not belong to $\langle g \rangle$. Then with overwhelming probability all elements $m_{ij}$ belong to ideal $\langle g \rangle$.

Proof Assuming that both norms are smaller than $q/2$ the equation holds over $R$, not only over $R_q$. Let’s assume that there exists an element $m_{rs}$ that does not belong to $\langle g \rangle$.

1. For random elements $z_{1r}$ and $h_{1r}$ the product $z_{1r} \cdot m_{rs} \cdot h_{1r}$ is random element from ideal $\langle t \rangle$ (all factors are non-zero, because otherwise they would belong to $\langle g \rangle$) and it specifies the layer relative to the ideal $\langle g \rangle$. The layer specified by one element is non-zero, but there may be other non-zero $m_{ji}$ specifying other layers. The sum of those layers may be trivial, in which case the sum of elements would belong to the ideal $\langle g \rangle$. What is the probability that it happens?

2. The sum is a random element from the ideal $\langle t \rangle \subset R=\mathbb{Z}[x]/\langle f(x) \rangle$ and the question is: what is the probability that random element from $\langle t \rangle$ belongs to $\langle g \rangle$? Assuming that we have chosen $t$ that does not divide $g$, the element $s \cdot t \in \langle g \rangle$ if only if $s \in \langle g \rangle$. In consequence, the question may be stated more generally: what is the probability that random element from $R$ belongs to $\langle g \rangle$?

3. To answer the question we consider lattice connected with ideal $\langle g \rangle$ and its determinant (volume of its fundamental domain), which determines the density of the lattice elements in the entire space. According to the determinant of lattice $L$ given by basis $\mathcal{B}$ may be computed as follows:

\[det(L(\mathcal{B})) = \sqrt{det(B^T B)},\]

where $B$ is the matrix, which columns contains coefficients of vectors from the basis $\mathcal{B}$. For quadratic matrices $det(B^T\cdot B) = det(B^T) \cdot det(B)$ and $det(B)=det(B^T)$. In consequence:

\[det(L(\mathcal{B})) = det(B).\]

For a cyclic lattice corresponding to ideal $\langle g \rangle$ the basis consists of vectors:

\[\mathcal{B} = \{g \cdot x^i \pmod{f}~|~ 0 \leqslant i < l \}.\]

Assuming that $g$ is a polynomial of degree $n$ with coefficients $g_0,~g_1,\ldots g_{n-1}$ its basis matrix is of the form:

\[B = \begin{bmatrix} g_0 & g_1 & g_2 & \ldots & g_{n-2} & g_{n-1} \\ g_{n-1} & g_0 & g_1 & \ldots & g_{n-3} & g_{n-2}\\ \vdots & \vdots & \vdots & \ldots & \vdots & \vdots \\ g_1 & g_2 & g_3 &\ldots & g_{n-1} & g_0 \\ \end{bmatrix}.\]

Using the formula on a matrix determinant for matrix $A=(a_{ij})$:

\[det(A) = \sum_{\sigma \in S_n} sgn(\sigma) \cdot \prod_{i=1}^{n} a_{i\sigma_{i}},\]

for right choice of generator g, with one coefficient significantly bigger then others,

we can estimate the size $det(B) \approx |g|^n$.

1. The density of points from the ideal (which determines probability that randomly chosen point lies in the ideal) equals the inverse of the determinant:

\[Pr = \frac{1}{det(B)} \approx \|g\|^{-n}.\]

1. Assuming that considered events are independent, probability that $l^2$ elements of matrix $W_M$ depending on every $m_{ij}$ do not belong to ideal is:

\[Pr_{m} = \left ( \frac{1}{det(B)} \right )^{l^2} \approx \|g\|^{-n \cdot l^2}.\]

The probability depends on matrix dimension $l$ and chosen ideal generator $g$. Using Barrington Theorem we use matrices of dimension $l=5$, so $l^2=25$. Even for very small determinant $det(L(\mathcal{B}))=2$ the probability of error is lower than $2^{-25}$. For the right choice of the generator $g$, probability exponentially tends to 0 with its degree $n$ tending to infinity.

In accordance with Lemma 2 if $|w_k g|$ and $|\sum^l_{i=1} \sum^l_{j=1} z_{kj} \cdot m_{ji} \cdot h_{ik}|$ are smaller than $q/2$, elements $m_{ij}$ belong to ideal with overwhelming probability.

If elements does not belong to ideal, then with overwhelming probability either $|w_k g|>q/2$ or $|\sum^l_{i=1} \sum^l_{j=1} z_{kj} \cdot m_{ji} \cdot h_{ik}|>q/2$.

We will show taht in the first cases norm of ciphertext $|w_k|>q^{3/4}$ and in consequence $|W_M|>q^{3/4}$, while the second case is contradictory with assumption on the ciphertext size.

1. Assume that $|w_k g|>q/2$. Then:

\[\|w_k\| \cdot \|g\| \cdot poly(n) \geqslant \|w_k g\| > q/2\]

and in consequence:

\[\|w_k\| \geqslant \frac{\|w_k g\|}{\|g\| \cdot poly(n) } > \frac{q/2}{\|g\| \cdot poly(n)} > q^{3/4}.\]

We chose $|g| = poly(n)$, and $q$ is superpolynomial regarding $q$, so the inequality is correct.

1. Assume that $|\sum_{i=1}^l \sum_{j=1}^l z_{kj} \cdot m_{ji} \cdot h_{ik}|>q/2$. Then:

\[l^2 \cdot max_{i,j,k} \|z_{kj} \cdot m_{ji} \cdot h_{ik}\| \geqslant \|\sum_{i=1}^l \sum_{j=1}^l z_{kj} \cdot m_{ji} \cdot h_{ik}\|>q/2.\]

Estimating norms:

\[l^2 \cdot poly(n) \cdot max_{j,k}\|z_{kj}\| \cdot max_{i,j}\| m_{ji} \| \cdot max_{i,k}\| h_{ik}\| >q/2\]

and in consequence:

\[\|C\| > max_{i,j}\| m_{ji} \| > \frac{q/2}{l^2 \cdot poly(n) \cdot max_{j,k}\|z_{kj}\| \cdot max_{i,k}\| h_{ik}\|} \approx q^{1/2},\]

which is a contradiction with assumption that norm of ciphertext matrix is smaller than $q^{1/8}$.

Security

Security of proposed scheme is based on two computationally hard problems: problem of matrix decomposition for full rank matrices and a generalization of NTRU problem for matrices.

Security against algebraic attacks

The attack technique used for GGH13 cryptosystem was to compute the quotient of ciphertexts: \(h = \frac{enc(m_{10})}{enc(m_{11})} = \frac{r_{10} \cdot g + m_{10}}{r_{10} \cdot g + m_{10}}\) and solve NTRU problem for them, using the fact that the parameters of a~scheme are too small. Trying to use the same technique to attack a matrix version of a cryptosystem cannot be used, because of non-commutation of a scheme. The quotient of ciphertext corresponding to the matrices from the same pair would give as a result the following conjugation:

\[\begin{multline*} H = (Z_{i-1} \cdot (R_{i0} \cdot G' + M_{i0}') \cdot Z_i^{-1}) \cdot (Z_{i-1} \cdot (R_{i1} \cdot G' + M_{i1}') \cdot Z_i^{-1})^{-1} = \\ = Z_{i-1} \cdot (R_{i0} \cdot G' + M_{i0}') \cdot (R_{i1} \cdot G' + M_{i1}')^{-1} \cdot Z_{i-1}^{-1}. \end{multline*}\]

Please notice, that matrices $Z_{i},~Z_{i}^{-1}$ were shortened, but matrices $Z_{i-1},Z_{i-1}^{-1}$ still exists in the quotient. Matrices $Z_i$ for $i>0$ are random, invertible matrices and with overwhelming probability have a big norm. We cannot see a way how to break the scheme in this setting. The only thing the attacker can deduce, are eigenvalues of the product:

\[(R_{i0} \cdot G' + M_{i0}') \cdot (R_{i1} \cdot G' + M_{i1}')^{-1}\]

that are the same as eigenvalues of $H$ from Jordan Theorem. But as long as $R_{i0}$ and $R_{i1}$ are uniformly random and because we are using the inverse of matrix from the right side of equation, properties of private matrices $G’,~M_{10}’$ and $M_{11}’$ are well hidden.

The only matrix with a~fairly small norm is matrix $Z_0$ (its norm has to be smaller than $q^{1/4}$ for the correctness of a scheme). The matrix:

\[H = Z_0 \cdot (R_{i0} \cdot G' + M_{i0}') \cdot (R_{i1} \cdot G' + M_{i1}')^{-1} \cdot Z_{0}^{-1} \pmod{q}\]

may be seen as a quotient of two matrices of a small norm, which are hard to find due to hardness of Matrix NTRU Problem (Definition \ref{dfn:mat-ntru})). Please notice, that if we would matrix $Z_0$ that is not invertible, the attack would be not possible. However, in that case we cannot use Lemma \ref{lem:matrices-extended} as a security guarantee.

Attacks using zero test parameter

Zero test parameter:

\[p_{zt} = Z_K \cdot G'^{-1} \cdot H \pmod{q},\]

hides the information about the inverse of generator matrix $G’^{-1}$. It should also be impossible to extract information about random invertible matrix $Z_K$. Matrix $G’^{-1}$ has rank $k/2$ (where $k$ defines its dimension) and $Z_K$ and $H$ are random full rank matrices ($H$ does not even has to be invertible). Knowing $p_{zt}$ we cannot deduce anything more than information about $G’^{-1}$ rank, which follows from Lemma~\ref{lem:matrices-extended}.

Please notice, that $p_{zt}$ may be multiplied by the different encrypted products of matrices $M_x$ and $M_y$ giving following matrices in result:

\[enc(M_x') \cdot p_{zt} = Z_0 \cdot (R_x \cdot G' + M_x') \cdot G'^{-1} \cdot H \pmod{q},\] \[enc(M_y') \cdot p_{zt} = Z_0 \cdot (R_y \cdot G' + M_y') \cdot G'^{-1} \cdot H \pmod{q}.\]

One can compute:

\[\begin{multline*} (enc(M_x') \cdot p_{zt}) \cdot (enc(M_{K1}')^{-1} \cdot p_{zt}) = \\ = Z_0 \cdot (R_x \cdot G' + M_x') \cdot (R_y \cdot G' + M_y')^{-1} \cdot Z_0^{-1} \pmod{q}. \end{multline*}\]

As in previous section, we get a quotient of to matrices of small norm (matrix $Z_0$ has to have small norm, for the ciphertext to be decrypted correctly) and security of recovering secret parameters depends on the computational hardness of Matrix NTRU Problem (Definition \ref{dfn:mat-ntru}).

The necessity of using safeguards

Attacker may evaluate program dishonestly and subtract matrices from the same pair:

\[\begin{multline*} M_{diff} = Z_{i-1} \cdot (R_{i0} \cdot encode(G) + M_{i0}) \cdot Z_i - Z_{i-1} \cdot (R_{i1} \cdot encode(G) + M_{i1}) \cdot Z_i = \\ = Z_{i-1} \cdot \left( (R_{i0}-R_{i1}) \cdot encode(G) + (M_{i0}-M_{i1})\right) \cdot Z_i = \\ = Z_{i-1} \cdot \begin{bmatrix} (M_{i0}-M_{i1}) & (B_{i0}-B_{i1}) G \\ \overline{0} & (D_{i0}-D_{i1}) G \end{bmatrix} \cdot Z_i, \end{multline*}\]

for random matrices:

\[R_{ij} = \begin{bmatrix} A_{ij} & B_{ij} \\ C_{ij} & D_{ij} \end{bmatrix}.\]

If the resulting matrix $M_{diff}$ does not have a full rank, the attacker will know that the middle matrix also has lower rank. Subtracting random matrices with overwhelming probability does not influence the rank of the middle matrix, but subtracting plaintext matrices may influence the rank. We assume that plaintext matrices are the permutation matrices (representing permutations from group $S_5$) and they have binary elements. If two matrices has ones in the same place the rank of the resulting matrix will be lower and attacker can gain that information.

Fortunately, in GGH13 obfuscation scheme encrypted matrices are multiplied by scalars to counteract mix-input attacks. If matrices $M_{i0}$ and $M_{i1}$ are multiplied by random scalars, then the difference is not 0, but the difference of the scalars and the rank of the matrix remains unchanged.

Efficiency

The efficiency of a scheme depends on the efficiency o multiplying matrices over polynomial ring, consisting in many parallel polynomial multipliactions. The efficiency of computations in the ring $R$ is described in detail in the paper \cite{ntru-prime}. Authors used Karatsuba multiplication instead of NTT-based multiplication, getting results comparable with NTT implementations.

The exact parameters of a scheme depend on the size of a program being encrypted.

Conclusions

We proposed idea of generalization of GGH13 obfuscation scheme immune to known attacks. We encrypt matrices as a whole, not element by element as in original scheme. We used alternative formulation of NTRU problem in the finite fields (used earlier in NTRU Prime cryptosystem) and perfect securely encryption of matrices of specified rank, defined by Ishai and Kushilevitz. There remain many details of a scheme to be specified in the future. Especially how to choose generators of matrix ideals and proof of correctness for more complicated generators, then ones proposed in this article.