# Improved Cryptanalysis of a Fully Homomorphic Symmetric Encryption Scheme

Authors: Quanbo Qu; Baocang Wang; Yuan Ping; Zhili Zhang
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Homomorphic encryption is widely used in the scenarios of big data and cloud computing for supporting calculations on ciphertexts without leaking plaintexts. Recently, Li et al. designed a symmetric homomorphic encryption scheme for outsourced databases. Wang et al. proposed a successful key-recovery attack on the homomorphic encryption scheme but required the adversary to know some plaintext/ciphertext pairs. In this paper, we propose a new ciphertext-only attack on the symmetric fully homomorphic encryption scheme. Our attack improves the previous Wang et al.’s attack by eliminating the assumption of known plaintext/ciphertext pairs. We show that the secret key of the user can be recovered by running lattice reduction algorithms twice. Experiments show that the attack successfully and efficiently recovers the secret key of the randomly generated instances with an overwhelming probability.


---

## Body

## 1. Introduction

With the rapid development of big data, the significance of privacy and security issues was highly regarded. A series of cryptoghraphic applications, such as fair electronic transaction [1], outsourcing data classification [2], lightweight security system of Internet of Things [3], mobile Ecommerce [4], and data mining based on homomorphic encryption, have been proposed.Homomorphic encryption schemes allow users to meaningfully calculate ciphertexts without knowing the underlying plaintexts. For example, the RSA cryptosystem [5] (Pallier cryptosystem [6], respectively) only supports homomorphic multiplications (additions, respectively) on ciphertexts. In 2009, Gentry [7] designed the first fully homomorphic encryption scheme with ideal lattices. Thereafter, significant efforts had been performed to improve the efficiency of homomorphic encryption schemes [8–10]. However, all the known fully homomorphic encryptions are criticized for the high ciphertext expansion and ciphertext refreshing costs and hence cannot be directly used in practice. So researchers designed some cryptographic schemes with homomorphic properties dedicated to some concrete computing scenarios [11–15].Recently, Li et al. [16] designed a symmetric homomorphic encryption scheme for outsourced databases that allow multiple data owners to efficiently share their data securely without compromising the privacy of the data. However, Wang et al. [17] observed that if some plaintext/ciphertext pairs were succesfully overdropped, one can efficiently recover the corresponding secret key of the scheme from the obtained plaintext/ciphertext pairs.In practical scenarios, it may be difficult for the adversary to capture plaintext/ciphertext pairs. In this paper, we propose a new efficient cryptanalytic attack on Li et al.’s homomorphic encryption scheme. The attack consists of two stages. In the first stage, we separate the parts of the ciphertexts, which contain no secret keys. In the second stage, we separate the parts of the ciphertexts, which contain neither secret key s nor q. Thus s and q can be calculated during an acceptable time. The whole attack needs only several ciphertexts without corresponding plaintexts.This paper is organised as follows. In Section2, we review Li et al.’s symmetric homomorphic encryption scheme and introduce the concept of lattice. In Section 3, we propose our attack and give the experimental results. In Section 4, we conclude our work.


## 2. Preliminaries

### 2.1. Notations

In this paper, the symbolZ is used to denote the ring of integer. Matrices are represented with bold upper-case characters like B, while vectors are represented with bold lower-case characters like v. All of the vectors in this paper are represented as row vectors. The symbol v means the length of vector v under the Euclidean norm, while the symbol |p|2 means the bit length of integer p.The symbol≪ means “much less than”,i.e. if a≪b, the ratio a/b is a negligible function negl(λ) of the security parameter λ. In mathematics, a negligible function μ(x) means that for any polynomial function poly(x), there exists an integer Nc such that for any x>Nc, (1)μx<1polyx.


### 2.2. Symmetric Homomorphic Encryption

The symmetric homomorphic encryption scheme proposed by Li et al. comprises these three algorithms as follows:(i)
Key generation algorithm  KeyGen()(2)s,q,p←KeyGenλ.Input a security parameterλ, this algorithm outputs a secret key SK=(s,q) and a public parameter p, where q≪p.(ii)
Encryption algorithm  E()(3)c=ESK,m,d=sdrq+mmod⁡p.Input a secret keySK, a plaintext m∈Fq and a parameter d, this algorithm outputs a ciphertext c=E(SK,m,d). Notice that the parameter r should satisfy |r|2+|q|2<|p|2.(iii)
Decryption algorithm  D()(4)m=DSK,c,d=c×s-dmod⁡pmod⁡q.Input a secret keySK, a ciphertext c∈Fp and the ciphertext’s degree d, this algorithm outputs a ciphertext c←E(SK,m,d). The proof of the correctness is simple:(5)DSK,c,d=c×s-dmod⁡pmod⁡q=sdrq+mmod⁡p×s-dmod⁡pmod⁡q=rq+mmod⁡q=m.Notice that the correctness of(rq+m)(mod⁡q)=m requires q≪p and |r|2+|q|2<|p|2.The symmetric homomorphic encryption scheme proposed by Li et al. supports homomorphic addition and multiplication and is used to construct their secure outsourced comparison scheme and privacy-preserving mining solutions. Though our attack needs no homomorphic properties, we still list a brief proof, for the reason that it implies the setting of parameters.(i)
Homomorphic addition: For the ciphertext c1,c2 of two plaintexts m1,m2, we have (6)c1+c2mod⁡p=sd1r1q+m1mod⁡p+sd2r2q+m2mod⁡p=sd1r1+r2q+m1+m2mod⁡p,d1=d2.The correct decryption ofc1+c2 requires d1=d2 and (r1+r2)q+m1+m2<p.(ii)
Homomorphic multiplication: For the ciphertext c1,c2 of two plaintexts m1,m2, we have (7)c1×c2mod⁡p=sd1r1q+m1mod⁡p×sd2r2q+m2mod⁡p=sd1+d2r1r2q2+r1qm2+r2qm1+m1×m2mod⁡p=sd1+d2r1r2q+r1m2+r2m1q+m1×m2mod⁡p.The correct decryption ofc1×c2 requires (r1r2q+r1m2+r2m1)q+m1×m2<p.


### 2.3. Lattice

Anm-dimension lattice L can be regarded as a set of all integer coefficient linear combinations of basis vectors {b1,b2,…,bm}, that is L(B)=v=∑i=1m‍aibi∣ai∈Z,bi∈Rn. If m=n, we call that L is a full-rank lattice.One of the most famous problems involving lattice is the shortest vector problem (SVP). Given a basis of a lattice, the goal is to find one non-zero vector, which has the shortest lengthv. Some approximation algorithms are usually used for solving SVP as oracles, such as LLL and BKZ algorithms. The LLL algorithm is developed by A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovasz [18] in 1982. Given a basis of a lattice, the LLL algorithm outputs a reduced basis, which has a smaller size by Gram-Schmidt orthogonalization. It has various applications in cryptanalysis and other fields, such as integer programming and finding integer relations.


## 2.1. Notations

In this paper, the symbolZ is used to denote the ring of integer. Matrices are represented with bold upper-case characters like B, while vectors are represented with bold lower-case characters like v. All of the vectors in this paper are represented as row vectors. The symbol v means the length of vector v under the Euclidean norm, while the symbol |p|2 means the bit length of integer p.The symbol≪ means “much less than”,i.e. if a≪b, the ratio a/b is a negligible function negl(λ) of the security parameter λ. In mathematics, a negligible function μ(x) means that for any polynomial function poly(x), there exists an integer Nc such that for any x>Nc, (1)μx<1polyx.


## 2.2. Symmetric Homomorphic Encryption

The symmetric homomorphic encryption scheme proposed by Li et al. comprises these three algorithms as follows:(i)
Key generation algorithm  KeyGen()(2)s,q,p←KeyGenλ.Input a security parameterλ, this algorithm outputs a secret key SK=(s,q) and a public parameter p, where q≪p.(ii)
Encryption algorithm  E()(3)c=ESK,m,d=sdrq+mmod⁡p.Input a secret keySK, a plaintext m∈Fq and a parameter d, this algorithm outputs a ciphertext c=E(SK,m,d). Notice that the parameter r should satisfy |r|2+|q|2<|p|2.(iii)
Decryption algorithm  D()(4)m=DSK,c,d=c×s-dmod⁡pmod⁡q.Input a secret keySK, a ciphertext c∈Fp and the ciphertext’s degree d, this algorithm outputs a ciphertext c←E(SK,m,d). The proof of the correctness is simple:(5)DSK,c,d=c×s-dmod⁡pmod⁡q=sdrq+mmod⁡p×s-dmod⁡pmod⁡q=rq+mmod⁡q=m.Notice that the correctness of(rq+m)(mod⁡q)=m requires q≪p and |r|2+|q|2<|p|2.The symmetric homomorphic encryption scheme proposed by Li et al. supports homomorphic addition and multiplication and is used to construct their secure outsourced comparison scheme and privacy-preserving mining solutions. Though our attack needs no homomorphic properties, we still list a brief proof, for the reason that it implies the setting of parameters.(i)
Homomorphic addition: For the ciphertext c1,c2 of two plaintexts m1,m2, we have (6)c1+c2mod⁡p=sd1r1q+m1mod⁡p+sd2r2q+m2mod⁡p=sd1r1+r2q+m1+m2mod⁡p,d1=d2.The correct decryption ofc1+c2 requires d1=d2 and (r1+r2)q+m1+m2<p.(ii)
Homomorphic multiplication: For the ciphertext c1,c2 of two plaintexts m1,m2, we have (7)c1×c2mod⁡p=sd1r1q+m1mod⁡p×sd2r2q+m2mod⁡p=sd1+d2r1r2q2+r1qm2+r2qm1+m1×m2mod⁡p=sd1+d2r1r2q+r1m2+r2m1q+m1×m2mod⁡p.The correct decryption ofc1×c2 requires (r1r2q+r1m2+r2m1)q+m1×m2<p.


## 2.3. Lattice

Anm-dimension lattice L can be regarded as a set of all integer coefficient linear combinations of basis vectors {b1,b2,…,bm}, that is L(B)=v=∑i=1m‍aibi∣ai∈Z,bi∈Rn. If m=n, we call that L is a full-rank lattice.One of the most famous problems involving lattice is the shortest vector problem (SVP). Given a basis of a lattice, the goal is to find one non-zero vector, which has the shortest lengthv. Some approximation algorithms are usually used for solving SVP as oracles, such as LLL and BKZ algorithms. The LLL algorithm is developed by A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovasz [18] in 1982. Given a basis of a lattice, the LLL algorithm outputs a reduced basis, which has a smaller size by Gram-Schmidt orthogonalization. It has various applications in cryptanalysis and other fields, such as integer programming and finding integer relations.


## 3. The Proposed Attack

### 3.1. Main Idea

Defineriq+mi as ai, and cic1-1 as fi. Our attack has two stages. In the first stage, we construct a lattice L(F) with f’s and run the LLL algorithm to obtain a short vector, which contains a’s. In the second stage, we construct a lattice L(A) with a’s and run the LLL algorithm again to obtain a short vector which contains r’s. It is obvious that the secret key (sd,q) can be computed as sd=ca-1mod⁡p and q=a/rmod⁡p. Notice that there is no need for the plaintexts m’s in the attack.


### 3.2. Details

In this part, we give a specification of the attack in Algorithm1. The input of the attack algorithm contains a set of ciphertexts c=c1,…,ck and the modular p of the encryption scheme without plaintexts m’s. The output of the attack algorithm contains sd and q which can be used to decrypt ciphertexts.Algorithm 1:The Attack Algorithm.
Input:  k ciphertexts c1,⋯,ck Output:  private key (sd,q) for  i=2  to  k  do fi=cic1-1 end for SetL(F) with f’s f=LLL_reduction(L(F)) a1=|(f)k| for  i=1  to  k-1  do ai+1=|(f)i| end for SetL(A) with a’s a=LLL_reduction(L(A)) r1=|(a)k| for  i=1  to  k-1  do ri+1=(|(a)i|+r1∗ai+1)/a1 end for Computesd=c1a1-1mod⁡p Computeq=a1/r1mod⁡p return  (sd,q)In the first stage, the latticeL(F) is constructed as (8)F=p0⋯000p⋯00⋮⋮⋱⋮⋮00⋯p0-f2-f3⋯-fk1=v1v2⋮vk.Thus a short vector v∈L(F) could be expressed as(9)v=x1v1+x2v2+⋯+xk-1vk-1+xkvk=x1p-xkf2,x2p-xkf3,…,xk-1p-xkfk,xk.Through LLL’s algorithm, we could obtain a short vectorf∈L(F).Claim 1.
Parametersa2,…,ak are close to |(f)1|,…,|(f)k-1|, while a1 is close to |(f)k|, where (f)i means the i’th entry of the output vector f.Sketch of Proof. Suppose that fia1=ai+tip, then we have fi/p-ti/a1=ai/(a1p). Because |a|≪|p|, ai/(a1p)≈1/p<negl(λ). Hence, values of f2/p,…,fk/p are close to those of t2/a1,…,tk/a1. Because |xi-1p-xkfi| is small, we can obtain that xi-1/xk-fi/p<negl(λ). Hence, values of x1/xk,…,xk-1/xk are close to those of f2/p,…,fk/p. Since t2/a1,…,tk/a1 and x1/xk,…,xk-1/xk are both close to f2/p,…,fk/p, we obtain that values of t2/a1,…,tk/a1 are close to x1/xk,…,xk-1/xk. With a non-negligible probability, x1,…,xk-1 equal t2,…,tk, and xk is equal to a1.As|a1| is close to |xk|, we have xk≈|a1| or xk≈-|a1|. Considering |a|,|x|≪p, we believe that |a|<p/2, thus a1≈|xk|. Similarly, as |xi-1p-xkfi| is small, we have |xi-1p-xkfi|=(xi-1p-xkfi)mod⁡p=-xkfimod⁡p or |xi-1p-xkfi|=-(xi-1p-xkfi)mod⁡p=xkfimod⁡p, i.e. |xi-1p-xkfi|=|xk|fimod⁡p, thus ai+1=a1fi+1mod⁡p≈|xk|fi+1≈(f)i,i=1,…,k-1.In the second stage, the latticeL(A) is constructed as (10)A=a10⋯000a1⋯00⋮⋮⋱⋮⋮00⋯a10-a2-a3⋯-ak1=w1w2⋮wk.Thus a short vector w∈L(A) could be expressed as(11)w=y1w1+y2w2+⋯+yk-1wk-1+ykwk=y1a1-yka2,y2a1-yka3,…,yk-1a1-ykak,yk.Through LLL’s algorithm, we could obtain a short vectora∈L(A).Claim 2.
Parametersr1,r2,…,rk are close to |(a)k|,(|(a)1|+r1∗a2)/a1,…,(|(a)k-1|+r1∗ak)/a1, where (a)i means the i’th entry of the output vector a.Sketch of Proof. Considering ai=riq+mi, we have ai/a1=(riq+mi)/(r1q+m1)≈(riq)/(r1q)=ri/r1. Hence, values of a2/a1,…,ak/a1 are close to those of r2/r1,…,rk/r1.Because|yi-1a1-ykai| is small, we can obtain that yi-1/yk-ai/a1<negl(λ). Hence, values of y1/yk,…,yk-1/yk are close to those of a2/a1,…,ak/a1. Since r2/r1,…,rk/r1 and y1/yk,…,yk-1/yk are both close to a2/a1,…,ak/a1, we obtain that values of r2/r1,…,rk/r1 are close to y1/yk,…,yk-1/yk. With a non-negligible probability, y1,…,yk-1 equal r2,…,rk, and yk is equal to r1.Likewise, we haver1=|(a)k| and ri+1=(|(a)i|+r1∗ai+1)/a1,i=1,…,k-1.Since we have recovered all thea’s and r’s, the secret key (sd,q) could be simply computed as sd=ciai-1 and q=ai/ri. Parameters c1,a1 and r1 are used to compute (sd,q) in the algorithm.


### 3.3. Experiments

We run our proposed cryptanalytic algorithm on a personal computer using NTL library [19]. The environment is listed as follows:(i)
CPU: Intel(R) Core (TM) i3-7100 3.90GHz(ii)
RAM: 4.00GB(iii)
OS: Windows 10 64bitNotice that the output of the attack algorithm issd. In [16], the parameter d is calledciphertext degree and is believed to be a small positive integer. It means that we could collect enough d-degree ciphertexts we need, and it is not difficult to recover s from sd. For the d-degree ciphertexts, the encryption and decryption algorithms only require sd rather than s. Thus, it is sufficient to break the scheme if we can recover sd. For convenience, we suppose the parameter d=1 in the encryption algorithm. When d≠1, our algorithm still works correctly.The results are given in Table1. As a result of the approximation, the chance of success is relavant to |q|2, |r|2, and |m|2. The best situation is when |q|2≈|r|2 and |m|≪|rq|. To make it easier to understand our proposed attack, we give an example to illustrate the procedure of the algorithm in Table 2. The parameters are set as |p|2=256, |q|2=64, |r|2=64, and m≤q/256.Table 1
Results in experiments with different parameters.
| p | 2 | q | 2 | r | 2 m k Instances Successes Average Time 256 64 64 ≤ q / 256 20 100 98 28.65s 256 64 64 ≤ q / 64 20 100 10 29.20s 256 64 96 ≤ q / 256 20 100 23 39.70s 256 64 48 ≤ q / 256 20 100 2 25.09s 256 48 48 ≤ q / 32 20 100 51 20.56sTable 2
Example for|p|2=256.
The Encryption Scheme KeyGen p 9667660090081161853810342777895287998619 4318084870939447026698628675235799451 q 17957200991146257161 s 5710889004555322387 d 1 E ( ) m 1 47863226783593508 r 1 13683909070104700313 c 1 1403306518881428241485832704008411265962 802817946162878687 ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ m 20 8614814073974658 r 20 15727429030749794270 c 20 1612872723066650760854493964947953343890 747803002904919536  The Cryptanalytic Algorithm The First Stage v 1 -199463957636154746239994027808094961893 ⋯ ⋯ v 20 245724705516439382626385136850318784901 The Second Stage w 1 -233711443236476253781580056731358133 ⋯ ⋯ w 20 13683909070104700313 s 5710889004555322387 q 17957200991146257161Firstly, we compute all thef’s with the input ciphertexts (c1,…,ck). Secondly, we use LLL algorithm to obtain a short vector for solving all a’s. Thirdly, we use LLL algorithm again to obtain a short vector for solving all r’s. Finally, we compute secret key (s,q) with a’s and r’s.In practice, the first rowf (a, respectively) of the reduced basis of L(F) (L(A), respectively) which is a row vector with a short norm; thus we regard it as the short vector v (w, respectively) we need.The chance of success depends on the bit lengths ofr, q, and m. In the first stage, |a|≪|p| requires |rq|≪|p|. In the second stage, ai/a1=(riq+mi)/(r1q+m1)≈(riq)/(r1q)=ri/r1 requires |m|≪|rq|. Thus we need to hold |m|≪|rq|≪|p|. Besides, the recovery of q from a also limit the setting of parameters. Notice that a=rq+m, where 0≤m<q. If m<r, the result of a/r is equal to q. However, when |r|2<|q|2, we cannot confirm that 0≤m<r. In conclusion, the best situation is when |r|≈|q| and |r| is slightly greater than |q|.


### 3.4. Complexity Analysis

We start with some simple conclusions about computational complexity.(1)
The computational complexity of modular inverse modulop is Olog3p.(2)
The computational complexity of modular multiplication modulop is Olog2p.(3)
The computational complexity of the LLL algorithm isON5log2B [20], where N is the dimension of the lattice, and B is the maximum length of input basis under the Euclidean norm.Combining (1) and (2), we can conclude that the computational complexity of calculatingf’s, r’s, s, and q is Olog3p. In our attack, N=k and B≤(k-1)p2+1. We can obtain the computational complexity of the LLL algorithm(12)ON5log2B=Ok5log2k-1p2+1=Ok5log2kp2=Ok512log⁡k+log⁡p2=O14k5log2k+k5log⁡klog⁡p+k5log2p.Because k<p, we can obtain log⁡k<log⁡p, thus ON5log2B=Ok5log2p.In practice, the computational complexity of our attack is mainly dependent on that of the LLL algorithm. For example, suppose thatk5log2p≤log3p we can obtain log⁡p≥k5. If we set k=20, then log⁡p≥205≈221. It means that p is a 221-bit-length prime, while the bit length of the prime we usually use is 2048=211 or 4096=212.Above all, the computational complexity of our attack algorithm isOk5log2p. Obviously, it is worse than the complexity Olog4p of Wang et al.’s attack [17]; however, our attack eliminates the assumption of known plaintext/ciphertext pairs.


### 3.5. Discussions

Notice that in the attack algorithm, the output of the LLL algorithm is a vector, such asf and a, rather than a reduced basis. We regard the first row vector of an LLL-reduced basis as the goal short vector. We explain the reason below.Anδ-LLL-reduced B=b1,b2,…,bn has two important properties:(1)
∀1≤i≤n,j<i,|μi,j|≤1/2,(2)
∀1≤i≤n,δb~i2≤μi+1,i2b~i2+b~i+12,whereB~=b~1,b~2,…,b~n is the Gram-Schmidt orthogonalization of B=b1,b2,…,bn, and the coefficient μi,j=〈bi,b~j〉/〈b~j,b~j〉.From these two properties, we can conclude that(13)b~1≤2n-1/2λ1L,where λ1(L) is the length of the shortest non-zero vector in L(B). Please refer to [21] for more detailed introduction and proof.The efficiency of our attack algorithm is mainly subject to the parameterk. Smaller k implies a greater chance of success for the reason that a’s and r’s can be recovered from the LLL algorithm easier while the runtime of the LLL algorithm rises rapidly. In our experiment, we recommend that k should be set as 20 considering both the chance of success and the runtime. In addition, the chance of success is also limited by sizes of r, q, and m.Table3 gives a comparision of Wang et al’s attack and ours. Although the bit lengths of the parameters |p|2,|q|2 and |r|2 are close but different, the average time of Wang et al’s is much less than ours. However, the improved attack algorithm eliminates the assumption of known plaintext/ciphertext pairs, thus a ciphertext-only adversary can break the encryption scheme through this way.Table 3
Comparision of Wang et al.’s Attack and Ours.
| p | 2 | q | 2 | r | 2 Chance of Success Average Time Plaintexts Needed? Attack in [17] 241 80 40 98% 0.1292s Yes Our Attack 256 64 64 98% 28.65s No


## 3.1. Main Idea

Defineriq+mi as ai, and cic1-1 as fi. Our attack has two stages. In the first stage, we construct a lattice L(F) with f’s and run the LLL algorithm to obtain a short vector, which contains a’s. In the second stage, we construct a lattice L(A) with a’s and run the LLL algorithm again to obtain a short vector which contains r’s. It is obvious that the secret key (sd,q) can be computed as sd=ca-1mod⁡p and q=a/rmod⁡p. Notice that there is no need for the plaintexts m’s in the attack.


## 3.2. Details

In this part, we give a specification of the attack in Algorithm1. The input of the attack algorithm contains a set of ciphertexts c=c1,…,ck and the modular p of the encryption scheme without plaintexts m’s. The output of the attack algorithm contains sd and q which can be used to decrypt ciphertexts.Algorithm 1:The Attack Algorithm.
Input:  k ciphertexts c1,⋯,ck Output:  private key (sd,q) for  i=2  to  k  do fi=cic1-1 end for SetL(F) with f’s f=LLL_reduction(L(F)) a1=|(f)k| for  i=1  to  k-1  do ai+1=|(f)i| end for SetL(A) with a’s a=LLL_reduction(L(A)) r1=|(a)k| for  i=1  to  k-1  do ri+1=(|(a)i|+r1∗ai+1)/a1 end for Computesd=c1a1-1mod⁡p Computeq=a1/r1mod⁡p return  (sd,q)In the first stage, the latticeL(F) is constructed as (8)F=p0⋯000p⋯00⋮⋮⋱⋮⋮00⋯p0-f2-f3⋯-fk1=v1v2⋮vk.Thus a short vector v∈L(F) could be expressed as(9)v=x1v1+x2v2+⋯+xk-1vk-1+xkvk=x1p-xkf2,x2p-xkf3,…,xk-1p-xkfk,xk.Through LLL’s algorithm, we could obtain a short vectorf∈L(F).Claim 1.
Parametersa2,…,ak are close to |(f)1|,…,|(f)k-1|, while a1 is close to |(f)k|, where (f)i means the i’th entry of the output vector f.Sketch of Proof. Suppose that fia1=ai+tip, then we have fi/p-ti/a1=ai/(a1p). Because |a|≪|p|, ai/(a1p)≈1/p<negl(λ). Hence, values of f2/p,…,fk/p are close to those of t2/a1,…,tk/a1. Because |xi-1p-xkfi| is small, we can obtain that xi-1/xk-fi/p<negl(λ). Hence, values of x1/xk,…,xk-1/xk are close to those of f2/p,…,fk/p. Since t2/a1,…,tk/a1 and x1/xk,…,xk-1/xk are both close to f2/p,…,fk/p, we obtain that values of t2/a1,…,tk/a1 are close to x1/xk,…,xk-1/xk. With a non-negligible probability, x1,…,xk-1 equal t2,…,tk, and xk is equal to a1.As|a1| is close to |xk|, we have xk≈|a1| or xk≈-|a1|. Considering |a|,|x|≪p, we believe that |a|<p/2, thus a1≈|xk|. Similarly, as |xi-1p-xkfi| is small, we have |xi-1p-xkfi|=(xi-1p-xkfi)mod⁡p=-xkfimod⁡p or |xi-1p-xkfi|=-(xi-1p-xkfi)mod⁡p=xkfimod⁡p, i.e. |xi-1p-xkfi|=|xk|fimod⁡p, thus ai+1=a1fi+1mod⁡p≈|xk|fi+1≈(f)i,i=1,…,k-1.In the second stage, the latticeL(A) is constructed as (10)A=a10⋯000a1⋯00⋮⋮⋱⋮⋮00⋯a10-a2-a3⋯-ak1=w1w2⋮wk.Thus a short vector w∈L(A) could be expressed as(11)w=y1w1+y2w2+⋯+yk-1wk-1+ykwk=y1a1-yka2,y2a1-yka3,…,yk-1a1-ykak,yk.Through LLL’s algorithm, we could obtain a short vectora∈L(A).Claim 2.
Parametersr1,r2,…,rk are close to |(a)k|,(|(a)1|+r1∗a2)/a1,…,(|(a)k-1|+r1∗ak)/a1, where (a)i means the i’th entry of the output vector a.Sketch of Proof. Considering ai=riq+mi, we have ai/a1=(riq+mi)/(r1q+m1)≈(riq)/(r1q)=ri/r1. Hence, values of a2/a1,…,ak/a1 are close to those of r2/r1,…,rk/r1.Because|yi-1a1-ykai| is small, we can obtain that yi-1/yk-ai/a1<negl(λ). Hence, values of y1/yk,…,yk-1/yk are close to those of a2/a1,…,ak/a1. Since r2/r1,…,rk/r1 and y1/yk,…,yk-1/yk are both close to a2/a1,…,ak/a1, we obtain that values of r2/r1,…,rk/r1 are close to y1/yk,…,yk-1/yk. With a non-negligible probability, y1,…,yk-1 equal r2,…,rk, and yk is equal to r1.Likewise, we haver1=|(a)k| and ri+1=(|(a)i|+r1∗ai+1)/a1,i=1,…,k-1.Since we have recovered all thea’s and r’s, the secret key (sd,q) could be simply computed as sd=ciai-1 and q=ai/ri. Parameters c1,a1 and r1 are used to compute (sd,q) in the algorithm.


## 3.3. Experiments

We run our proposed cryptanalytic algorithm on a personal computer using NTL library [19]. The environment is listed as follows:(i)
CPU: Intel(R) Core (TM) i3-7100 3.90GHz(ii)
RAM: 4.00GB(iii)
OS: Windows 10 64bitNotice that the output of the attack algorithm issd. In [16], the parameter d is calledciphertext degree and is believed to be a small positive integer. It means that we could collect enough d-degree ciphertexts we need, and it is not difficult to recover s from sd. For the d-degree ciphertexts, the encryption and decryption algorithms only require sd rather than s. Thus, it is sufficient to break the scheme if we can recover sd. For convenience, we suppose the parameter d=1 in the encryption algorithm. When d≠1, our algorithm still works correctly.The results are given in Table1. As a result of the approximation, the chance of success is relavant to |q|2, |r|2, and |m|2. The best situation is when |q|2≈|r|2 and |m|≪|rq|. To make it easier to understand our proposed attack, we give an example to illustrate the procedure of the algorithm in Table 2. The parameters are set as |p|2=256, |q|2=64, |r|2=64, and m≤q/256.Table 1
Results in experiments with different parameters.
| p | 2 | q | 2 | r | 2 m k Instances Successes Average Time 256 64 64 ≤ q / 256 20 100 98 28.65s 256 64 64 ≤ q / 64 20 100 10 29.20s 256 64 96 ≤ q / 256 20 100 23 39.70s 256 64 48 ≤ q / 256 20 100 2 25.09s 256 48 48 ≤ q / 32 20 100 51 20.56sTable 2
Example for|p|2=256.
The Encryption Scheme KeyGen p 9667660090081161853810342777895287998619 4318084870939447026698628675235799451 q 17957200991146257161 s 5710889004555322387 d 1 E ( ) m 1 47863226783593508 r 1 13683909070104700313 c 1 1403306518881428241485832704008411265962 802817946162878687 ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ m 20 8614814073974658 r 20 15727429030749794270 c 20 1612872723066650760854493964947953343890 747803002904919536  The Cryptanalytic Algorithm The First Stage v 1 -199463957636154746239994027808094961893 ⋯ ⋯ v 20 245724705516439382626385136850318784901 The Second Stage w 1 -233711443236476253781580056731358133 ⋯ ⋯ w 20 13683909070104700313 s 5710889004555322387 q 17957200991146257161Firstly, we compute all thef’s with the input ciphertexts (c1,…,ck). Secondly, we use LLL algorithm to obtain a short vector for solving all a’s. Thirdly, we use LLL algorithm again to obtain a short vector for solving all r’s. Finally, we compute secret key (s,q) with a’s and r’s.In practice, the first rowf (a, respectively) of the reduced basis of L(F) (L(A), respectively) which is a row vector with a short norm; thus we regard it as the short vector v (w, respectively) we need.The chance of success depends on the bit lengths ofr, q, and m. In the first stage, |a|≪|p| requires |rq|≪|p|. In the second stage, ai/a1=(riq+mi)/(r1q+m1)≈(riq)/(r1q)=ri/r1 requires |m|≪|rq|. Thus we need to hold |m|≪|rq|≪|p|. Besides, the recovery of q from a also limit the setting of parameters. Notice that a=rq+m, where 0≤m<q. If m<r, the result of a/r is equal to q. However, when |r|2<|q|2, we cannot confirm that 0≤m<r. In conclusion, the best situation is when |r|≈|q| and |r| is slightly greater than |q|.


## 3.4. Complexity Analysis

We start with some simple conclusions about computational complexity.(1)
The computational complexity of modular inverse modulop is Olog3p.(2)
The computational complexity of modular multiplication modulop is Olog2p.(3)
The computational complexity of the LLL algorithm isON5log2B [20], where N is the dimension of the lattice, and B is the maximum length of input basis under the Euclidean norm.Combining (1) and (2), we can conclude that the computational complexity of calculatingf’s, r’s, s, and q is Olog3p. In our attack, N=k and B≤(k-1)p2+1. We can obtain the computational complexity of the LLL algorithm(12)ON5log2B=Ok5log2k-1p2+1=Ok5log2kp2=Ok512log⁡k+log⁡p2=O14k5log2k+k5log⁡klog⁡p+k5log2p.Because k<p, we can obtain log⁡k<log⁡p, thus ON5log2B=Ok5log2p.In practice, the computational complexity of our attack is mainly dependent on that of the LLL algorithm. For example, suppose thatk5log2p≤log3p we can obtain log⁡p≥k5. If we set k=20, then log⁡p≥205≈221. It means that p is a 221-bit-length prime, while the bit length of the prime we usually use is 2048=211 or 4096=212.Above all, the computational complexity of our attack algorithm isOk5log2p. Obviously, it is worse than the complexity Olog4p of Wang et al.’s attack [17]; however, our attack eliminates the assumption of known plaintext/ciphertext pairs.


## 3.5. Discussions

Notice that in the attack algorithm, the output of the LLL algorithm is a vector, such asf and a, rather than a reduced basis. We regard the first row vector of an LLL-reduced basis as the goal short vector. We explain the reason below.Anδ-LLL-reduced B=b1,b2,…,bn has two important properties:(1)
∀1≤i≤n,j<i,|μi,j|≤1/2,(2)
∀1≤i≤n,δb~i2≤μi+1,i2b~i2+b~i+12,whereB~=b~1,b~2,…,b~n is the Gram-Schmidt orthogonalization of B=b1,b2,…,bn, and the coefficient μi,j=〈bi,b~j〉/〈b~j,b~j〉.From these two properties, we can conclude that(13)b~1≤2n-1/2λ1L,where λ1(L) is the length of the shortest non-zero vector in L(B). Please refer to [21] for more detailed introduction and proof.The efficiency of our attack algorithm is mainly subject to the parameterk. Smaller k implies a greater chance of success for the reason that a’s and r’s can be recovered from the LLL algorithm easier while the runtime of the LLL algorithm rises rapidly. In our experiment, we recommend that k should be set as 20 considering both the chance of success and the runtime. In addition, the chance of success is also limited by sizes of r, q, and m.Table3 gives a comparision of Wang et al’s attack and ours. Although the bit lengths of the parameters |p|2,|q|2 and |r|2 are close but different, the average time of Wang et al’s is much less than ours. However, the improved attack algorithm eliminates the assumption of known plaintext/ciphertext pairs, thus a ciphertext-only adversary can break the encryption scheme through this way.Table 3
Comparision of Wang et al.’s Attack and Ours.
| p | 2 | q | 2 | r | 2 Chance of Success Average Time Plaintexts Needed? Attack in [17] 241 80 40 98% 0.1292s Yes Our Attack 256 64 64 98% 28.65s No


## 4. Conclusion

In this paper, we propose a new attack algorithm on the symmetric homomorphic encryption scheme presented by Li et al. Our attack can recover the secret key pair from several ciphertexts without plaintexts. In our experiment, the attack an be finished during an acceptable period of time with recovering most of the secret key in the generated instances. For the cases|p|2=256,|q|2=|r|2=64,m≤q/256, the key-recovery cryptanalytic algorithm only takes about 29 seconds. Although the running time and the opportunity of success depend on the sizes of parameters, the attack algorithm can still be used in real practice to recover secret key pairs.



---

*Source: 8319508-2019-06-02.xml*