Towards a fully homomorphic symmetric cipher scheme resistant to plain-text/cipher-text attacks

Abstract

Users’ privacy becomes nowadays an important need and a big challenge for a lot of enterprises and service providers especially after adopting the cloud migration strategy. Thus, Homomorphic Encryption (HE) came as a novel cryptographic approach that enables users’ privacy at the cloud side by allowing computation over encrypted data. Existing HE schemes are based on either symmetric or asymmetric encryption algorithms. While asymmetric HE schemes provide the high and the required level of security, they suffer from high computational complexity and high storage overhead making a big majority of them not practical for real world applications. On the other hand, symmetric schemes assure the required efficiency, but they are vulnerable to attacks and especially the known plain-text/cipher-text attacks making their usage limited in practical implementation. The main objective of this paper is to design a new symmetric HE variant that provides the desired level of efficiency in implementation and the immunity against data breaches especially the known plain-text/cipher-text attacks. The proposed scheme, named Homomorphic Hybrid Symmetric Encryption Scheme (HHSES), which is based on combining the homomorphic behavior of two well-known symmetric encryption schemes that are the MORE (Matrix Operation for Randomization and Encryption) approach and the Domingo Ferrer (DF) scheme. The performance analysis of HHSES confirms its efficiency for real-world applications in comparison with a big variety of existing and well known symmetric and asymmetric schemes. A main drawback of HHSES is the cipher-text dimension expansion after the homomorphic multiplication since homomorphic operations are restricted to polynomial operations over the matrices. Therefore, to fix this issue, we propose a specific Key Switching (KS) technique after the homomorphic multiplication that reduces the cipher-texts’ dimension without altering its homomorphic behavior and the primitive classified data. Security analysis of the new scheme also verifies its immunity against different types of attacks and especially the known plain-text/cipher-text attacks. Another important contribution in this work is the optimization of the HHSES encryption and decryption procedures by making them parallelized using the Chinese Remainder Theorem (CRT). The implementation results have shown that the proposed optimization technique reduces the execution time of the HHSE encryption and decryption algorithms with a ratio close to $\frac {1}{2}$. To the best of our knowledge, HHSES is the first symmetric HE scheme immune against the known/chosen plain-text/cipher-text attacks.

Appendices

Appendix A:: Invertible Secret Matrix Generation

Different Steps for generating the invertible matrix K in [12] are given by the following: Starting from a matrix

$$ k =\begin{bmatrix} a&b\\ c&d\\ \end{bmatrix} $$

its corresponding determinant Det(k) = ad − bc, assume that Det(k) = ad − bc = 1 and a = d. Under the conditions listed above we have: a² − bc = 1, so bc = a² − 1 = (a + 1)(a − 1), than we can write b = a + 1 and c = a − 1. As a result, the matrix k is given by the following form:

$$ k =\begin{bmatrix} a& a+1\\ a-1&a\\ \end{bmatrix} $$

(36)

Since Det(k) = 1, the matrix k is obviously invertible, and k^− 1 is

$$ k^{-1} =\begin{bmatrix} a&-(a+1)\\ -(a-1)&a\\ \end{bmatrix} $$

(37)

If the parameter a is replaced by sub matrix A, we get

$$ K =\begin{bmatrix} A& A+I\\ A-I&A\\ \end{bmatrix} $$

(38)

where I and A are the identity matrix and a non-zero matrix of size n/2 respectively. Additionally, the elements of A can be freely chosen from any Galois field such that K is full rank. However, having a matrix K constructed from four sub-matrices (A,B,C and D), $K=\begin {bmatrix} A& B\\ C&D\\ \end {bmatrix}$, the inverse of this matrix when A = D, B = A + I and C = A − I can be proven since the determinant of K is given by:

$$ \begin{array}{lll} Det(K)&=&Det(A)\times Det(D-CA^{-1} B)\\ &=& Det(A)\times Det(A-(A-I) A^{-1} (A+I) )\\ &=& Det(A)\times Det(A-(I-A^{-1})(A+I) )\\ &=& Det(A)\times Det(A-(A+I-I-A^{-1} ) )\\ &=& Det(A)\times Det(A^{-1} )\\ &=& Det(A)\times \frac{1}{Det(A)}\\ &=&1 \end{array} $$

(39)

Since Det(K) = 1, the matrix K is always invertible and its inverse integer matrix K^− 1 is:

$$ K^{-1} =\begin{bmatrix} A& -A-I\\ -A+I&A\\ \end{bmatrix} $$

(40)

As a result, building a secret invertible matrix K of dimension n × n, where n is always even is done by selecting a nonzero random sub matrix A of dimension n/2, and by applying the matrix forms listed respectively in (38) and (40), K and K^− 1 are obtained.

Appendix B: Attack on the Invertible Matrix Model

The vulnerability detected by the authors of [34] resides in using (38) while creating the invertible secret key K. As explained previously in Appendix A, the invertible matrix K has the following form: $\begin {bmatrix} A& A+I\\ A-I&A\\ \end {bmatrix}$ wheredim(K) is[n × n] and $dim(A)=dim(I)=\displaystyle {[\frac {n}{2} \times \frac {n}{2}]}$, thus the attack is based on the the two following principles:

• 1. Principle 1: the attacker does not know the matrix A, but given a plain-text vector m = [m₁,m₂,....,m_n] with its corresponding cipher-text matrix C of dimension [n × n], he knows that the eigen-vector of C associated to the i^th plain-text m_i has the following form: $\begin {bmatrix} A(i) \\-A(i)+e_{i} \end {bmatrix}$ for $\displaystyle {1 \leq i \leq \frac {n}{2}}$ and $\begin {bmatrix} -A(\displaystyle {i-\frac {n}{2}}) -\displaystyle {e_{i -\frac {n}{2}}} \\A(\displaystyle {i-\frac {n}{2}}) \end {bmatrix}$ for $\displaystyle {\frac {n}{2} < i \leq n}.$

• 2. Principle 2: setting C_1,1, C_1,2, C_2,1 and C_2,2 four sub-matrices of $C=\begin {bmatrix} C_{1,1}, C_{1,2}\\ C_{2,1} C_{2,2} \end {bmatrix}$, the attacker can deduce the following equalities for $\displaystyle {1 \leq i \leq \frac {n}{2}}$ and $\displaystyle {\frac {n}{2} < j \leq n}$:

  $$ \begin{bmatrix} C_{1,1}, C_{1,2}\\C_{2,1},C_{2,2} \end{bmatrix}. \begin{bmatrix} A(i)\\ -A(i)+e_{i} \end{bmatrix}=m_{i}.\begin{bmatrix} A(i)\\ -A(i)+e_{i} \end{bmatrix} $$

  (41)
  $$ \begin{bmatrix} C_{1,1}, C_{1,2}\\C_{2,1},C_{2,2} \end{bmatrix}. \begin{bmatrix} -A(\displaystyle{j-\frac{n}{2}}) -\displaystyle{e_{j -\frac{n}{2}}} \\A(\displaystyle{j-\frac{n}{2}}) \end{bmatrix}=m_{j}.\begin{bmatrix} -A(\displaystyle{j-\frac{n}{2}}) -\displaystyle{e_{j -\frac{n}{2}}} \\A(\displaystyle{j-\frac{n}{2}}) \end{bmatrix} $$

  (42)

By linearizing the two (41) and (42) and setting up $j=i+\displaystyle {\frac {n}{2}}$, the attacker can build the following relation given by:

$$ (-C_{1,1}+C_{1,2}-C_{2,1}+C_{2,2})=(m_{i}-m_{i+\frac{n}{2}}).e_{i} $$

(43)

Let D = (−C_1,1 + C_1,2 − C_2,1 + C_2,2). It is clear that for every $1 \leq i \leq \displaystyle {\frac {n}{2}}$, the i − th column of D is the i − th canonical vector multiplied by a difference of two eigen-values of C. Thus the matrix D, that can be computed using only one cipher-text, is a diagonal matrix, whose entries leak differences of eigen-values of C.

Revealing a plain-text vector, in this case, is given by the following steps:

• 1. Step1: let δ_i = D(i,i) denotes the i − th entry on the diagonal of D.

• 2. Step2: let the characteristic polynomial p(x) = CharPoly(C)(x) of the cipher-text C.

• 3. Step3: given that the roots of p(x) are the elements of the plain-text vector m, the attacker defines n new polynomials p_−i(x) and p_i(x) for $\displaystyle {1\leq i \leq \displaystyle {\frac {n}{2}}}$ as p_−i(x) = p(x − δ_i) and p_i(x) = p(x + δ_i)

• 4. Step 4: for any $1 \leq i \leq \displaystyle {\frac {n}{2}}$, m_i must be a root of p_−i(x), Thus m_i will also be root of gcd(p(x),p_−i(x)).