# STP-LWE: A Variant of Learning with Error for a Flexible Encryption

Authors: Bo Gao; Yanfeng Shi; Chunli Yang; Lixiang Li; Licheng Wang; Yixian Yang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We construct a flexible lattice based scheme based on semitensor product learning with errors (STP-LWE), which is a variant of learning with errors problem. We have proved that STP-LWE is hard when LWE is hard. Our scheme is proved to be secure against indistinguishable chosen message attacks, and it can achieve a balance between the security and efficiency in the hierarchical encryption systems. In addition, our scheme is almost as efficient as the dual encryption in GPV08.


---

## Body

## 1. Introduction

Lattices and lattice-based cryptography have become a hot research topic in public key cryptography in recent years. Lattice-based cryptography is attracted from provable worst-case hardness guarantees, good asymptotic efficiency and parallelism, and resistance to quantum attacks [1]. The first provably secure lattice based encryption AD is present by Ajtai and Dwork based on the worst-case hardness of lattice problems [2]. After that, several constructions have been proposed [3, 4]. In 2004, Regev improved ADGGH to R04 based on a harder lattice problem. But its huge key size is unacceptable [5]. To overcome its disadvantage, Regev successively constructed Regev05 based on learning with errors (LWE) problem, which can be quantum reduced from traditional SIVPγ problem [6]. Since LWE problem has been proved to be amazingly versatile, a multitude of cryptographic schemes have been proposed, such as the basis for secure public-key encryption under both chosen-plaintext [6] and chosen-ciphertext attacks [7, 8], oblivious transfer [9], identity-based encryption [10], various forms of leakage-resilient cryptography [11], and fully homomorphic encryption [12].In some applications, such as hierarchical encryption systems, the users in different levels will use private keys with different lengths [13]. They will retrieve their private key from their domain PKG, who has previously requested their domain secret key from the root PKG. In traditional encryptions, the PKG must save all security parameters and public parameters related to the different lengths of keys for the users in different domains [14]. So how to construct a flexible encryption scheme to bring a balance between the security and efficiency requirements is an open problem.Semitensor product (STP), as a new algebraic approach, is a generalization of the matrix product from the equal dimension case to the multiple dimension case, and it is designed to deal with higher-dimensional data as well as multilinear mappings [15]. Recently, STP is applied widely in control theory [16] and physics [17–19]. However, to the best of our knowledge, all the works in cryptography field based on STP are related to Boolean functions. A method for the conversion between the truth table and the polynomial expression of Boolean functions was proposed [20]. In [21], the authors did research on nonlinear feedback shift register (NLFSR), including the calculation of numbers of fixed points and cycles with different lengths of state sequences generated.In this paper, we propose a variant of LWE problem called STP-LWE problem, which is essential to extend the standard LWE problem by using STP. In STP-LWE problem, the dimension of public matrixA may not be equal to the secret s. The hardness of STP-LWE can be reduced to the standard LWE problem. In this paper, we will take advantage of the properties of STP-LWE to construct the STP-GPV dual cryptosystem based on the dual encryption in GPV08 [22]. The new scheme is more flexible in hierarchical encryption systems since we can flexibly balance the security and efficiency by adjusting the length of messages with the static security parameter.The rest of this paper is organized as follows. We first introduce some basic concepts of lattices in Section2. In Section 3, we detail STP product and STP-LWE problem. In Section 4, we propose the STP-GPV dual cryptosystem and analyze the correctness and security. In Section 5, we discuss the efficiency of the STP-GPV dual cryptosystem. Finally, discussions and conclusions are presented in Section 6.


## 2. Preliminaries

In this section, we briefly describe the basic concepts about lattices and the learning with errors (LWE) problem.


### 2.1. Notation

We denote the set of real numbers byℝ and the set of integers by ℤ. For a positive integer n, [n] denotes {1,…,n}. By convention, vectors are assumed to be in column form and written using bold lowercase letters, for example, x. The ith component of x will be denoted by xi. Matrices are written as bold capital letters, for example, X, and the ith column vector of a matrix X is denoted by xi. The length of a matrix is the norm of its longest column ∥X∥=max⁡i∥xi∥. We use standard big-O notation to classify the growth of functions and say that f(n)=O~(g(n)) if f(n)=O(g(n)·log⁡cn) for some fixed constant c. We let poly(n) be an unspecified function f(n)=O(nc) for some constants c. A negligible function, denoted generically by negl(n), is a function f(n) such that f(n)=o(n-c) for some fixed constant c We say that a probability (or fraction) is overwhelming if it is 1-negl(n) The statisticaldistance between two distributions X and Y over a countable domain D is defined to be (1/2)∑d∈D‍|X(d)-Y(d)|.


### 2.2. Lattices and Gaussian Measures

A lattice is a discrete additive subgroup ofℝn. Let B={b1,…,bn}⊂ℝn consist of n linearly independent vectors. The n-dimensional latticeΛ generated by the basis B is
(1)Λ=ℒ(B)={Bc=∑i∈[n]ci·bi:c∈ℤn}.For any (ordered) setS={s1,…,sn}⊂ℝn of linearly independent vectors, let S~={s~1,…,s~n} be its Gram-Schmidt orthogonalization, defined iteratively in the following way: s~1=s1, and for each i=2,…,n, s~i is the component of si orthogonal to span(s1,…,si-1). Clearly, ∥s~i∥≤∥si∥.The following useful lemma says that any full-rank set of vectors in a lattice can be efficiently converted to a basis of the lattice, without increasing the lengths of the Gram-Schmidt vectors.Lemma 1 (see [23]).
There is a deterministic polynomial-time algorithm that, given an arbitrary basisB of a n-dimensional lattice Λ=ℒ(B) and a full-rank set of lattice vectors S⊂Λ, the output is a basis T of Λ such that ∥t~i∥≤∥s~i∥ for all i∈[n].
The dual lattice ofΛ, denoted Λ*, is defined as Λ*={x∈ℝn:∀v∈Λ,〈x,v〉∈ℤ}. By symmetry, it can be seen that (Λ*)*=Λ. If B is a basis of Λ, the dual basis B*=(B-1)T is in fact a basis of Λ*.The following standard fact relates to the Gram-Schmidt orthogonalizations of a basis and its dual (the proof can be found in [5]).Lemma 2.
Let{b1,…,bn} be an ordered basis, and let {d1,…,dn} be its dual basis in reversed order (i.e., di=bn-i+1*). Then d~i=b~i/∥bi∥2 for all i∈[n]. In particular, ∥d~i∥=1/∥b~i∥.We now review the Gaussian measures over lattices. For anys>0, the Gaussian function on ℝn centered at c with parameter s is defined as
(2)∀x∈ℝn,ρs,c(x)=exp⁡(-π∥x-c∥2s2).The subscriptss and c are taken to be 1 and 0 (resp.,) when omitted.For anyc∈ℝn, real s>0, andn-dimensional lattice Λ, the discrete Gaussian distribution over Λ is defined as
(3)∀x∈Λ,DΛ,s,c(x)=ρs,c(x)ρs,c(Λ),
where ρs,c(Λ)=∑x∈Λ‍ρs,c(x).Micciancio and Regev [24] proposed a lattice quantity called the smoothing parameter.Definition 3 (see [24]).
For anyn-dimensional lattice Λ and a positive real ϵ>0, the smoothing parameter ηϵ(Λ) is the smallest real s>0 such that ρ1/s(Λ*∖0)≤ϵ, where ρ1/s(Λ*∖0)=∑x∈Λ*∖0‍ρ1/s,0(x).A bound on the smoothing parameter is also given in [24].Lemma 4 (see [25]).
For any n-dimensional latticeΛ and real ϵ>0, one has
(4)ηϵ(Λ)≤log⁡(2n/(1+1/ϵ))/πλ1∞(Λ*).
Then for anyω(log⁡⁡n) function, there is a negligible ϵ(n) for which ηϵ(Λ)≤ω(log⁡⁡n)/λ1∞(Λ*).We notice that a sample from a discrete Gaussian with parameters is at most sn away from its center (in the ℓ2 norm), with overwhelming probability.Lemma 5 (see [24]).
For any n-dimensional latticeΛ, c∈span(Λ), real ϵ∈(0,1), and s≥ηϵ(Λ),
(5)Prx~DΛ,s,c[∥x-c∥>sn]≤1+ϵ1-ϵ·2-n.


### 2.3. Some Lattice Problems

We now redescribe the learning with errors (LWE) problem [6].For an integerq≥2, some probability distribution χ over ℤq, an integer dimension n∈ℤ+, and a vector s∈ℤqn, define 𝒜s,χ as the distribution on ℤqn×ℤq of the variable (a,aTs+x), where a←ℤqn and x←χ are uniform and independent, and all operations are performed in ℤq.Definition 6 (LWE).
For an integerq=q(n) and a distribution χ on ℤq, the goal of the (average-case) learningwitherrors problem LWEq,χ is to distinguish (with nonnegligible probability) between the distribution 𝒜s,χ for some uniform (secret) s←ℤqn and the uniform distribution on ℤqn×ℤq (via oracle access to the given distribution). In other words, if LWE is hard, then the collection of distributions 𝒜s,χ is pseudorandom.𝕋
=
ℝ
/
ℤ as the group of reals [0,1) with mod 1 addition. For α∈ℝ+, Ψα is the distribution on 𝕋 of a normal variable with mean 0 and standard deviation α/2π, reduced modulo 1. For any probability distribution ϕ over 𝕋 and an integer q∈ℤ+ its discretization ϕ¯ is the discrete distribution over ℤq of the random variable ⌊q·Xϕ⌉mod⁡q, where Xϕ has distribution ϕ.Then, we recall two standard worst-case approximation problems on lattices. In both problems,γ=γ(n) is the approximation factor as a function of the dimension.Definition 7 (see [24] shortest vector problem (decision version)).
An input toGapSVPγ is a basis B of a full-rank n-dimensional lattice. It is a YES instance if λ1(ℒ(B))≤d and is a NO instance if λ1(ℒ(B))>γ(n)·d, where disarationalnumber.Definition 8 (see [24] shortest independent vectors problem).
An input toSIVPγ is a full-rank basis B of an n-dimensional lattice. The goal is to output a set of n linearly independent lattice vectors S⊂ℒ(B) such that ∥S∥≤γ(n)·λn(ℒ(B)).Regev demonstrated that for certain moduloq and Gaussian error distributions χ, LWEq,χ is as hard as several standard worst-case lattice problems using a quantum algorithm.Proposition 9 (see [6]).
Letα=α(n)∈(0,1) and let q=q(n) be a prime such that α·q>2n. If there exists an efficient (possibly quantum) algorithm that solves LWEq,Ψ¯α, then there exists an efficient quantum algorithm for approximating SIVP and GapSVP in the l2 norm, in the worst case, within O~(n/α) factors.
The result can be subsequently extended to SIVP and GapSVP in anylp norm, 2≤p≤∞, for essentially the same O~(n/α) approximation factors [25].


## 2.1. Notation

We denote the set of real numbers byℝ and the set of integers by ℤ. For a positive integer n, [n] denotes {1,…,n}. By convention, vectors are assumed to be in column form and written using bold lowercase letters, for example, x. The ith component of x will be denoted by xi. Matrices are written as bold capital letters, for example, X, and the ith column vector of a matrix X is denoted by xi. The length of a matrix is the norm of its longest column ∥X∥=max⁡i∥xi∥. We use standard big-O notation to classify the growth of functions and say that f(n)=O~(g(n)) if f(n)=O(g(n)·log⁡cn) for some fixed constant c. We let poly(n) be an unspecified function f(n)=O(nc) for some constants c. A negligible function, denoted generically by negl(n), is a function f(n) such that f(n)=o(n-c) for some fixed constant c We say that a probability (or fraction) is overwhelming if it is 1-negl(n) The statisticaldistance between two distributions X and Y over a countable domain D is defined to be (1/2)∑d∈D‍|X(d)-Y(d)|.


## 2.2. Lattices and Gaussian Measures

A lattice is a discrete additive subgroup ofℝn. Let B={b1,…,bn}⊂ℝn consist of n linearly independent vectors. The n-dimensional latticeΛ generated by the basis B is
(1)Λ=ℒ(B)={Bc=∑i∈[n]ci·bi:c∈ℤn}.For any (ordered) setS={s1,…,sn}⊂ℝn of linearly independent vectors, let S~={s~1,…,s~n} be its Gram-Schmidt orthogonalization, defined iteratively in the following way: s~1=s1, and for each i=2,…,n, s~i is the component of si orthogonal to span(s1,…,si-1). Clearly, ∥s~i∥≤∥si∥.The following useful lemma says that any full-rank set of vectors in a lattice can be efficiently converted to a basis of the lattice, without increasing the lengths of the Gram-Schmidt vectors.Lemma 1 (see [23]).
There is a deterministic polynomial-time algorithm that, given an arbitrary basisB of a n-dimensional lattice Λ=ℒ(B) and a full-rank set of lattice vectors S⊂Λ, the output is a basis T of Λ such that ∥t~i∥≤∥s~i∥ for all i∈[n].
The dual lattice ofΛ, denoted Λ*, is defined as Λ*={x∈ℝn:∀v∈Λ,〈x,v〉∈ℤ}. By symmetry, it can be seen that (Λ*)*=Λ. If B is a basis of Λ, the dual basis B*=(B-1)T is in fact a basis of Λ*.The following standard fact relates to the Gram-Schmidt orthogonalizations of a basis and its dual (the proof can be found in [5]).Lemma 2.
Let{b1,…,bn} be an ordered basis, and let {d1,…,dn} be its dual basis in reversed order (i.e., di=bn-i+1*). Then d~i=b~i/∥bi∥2 for all i∈[n]. In particular, ∥d~i∥=1/∥b~i∥.We now review the Gaussian measures over lattices. For anys>0, the Gaussian function on ℝn centered at c with parameter s is defined as
(2)∀x∈ℝn,ρs,c(x)=exp⁡(-π∥x-c∥2s2).The subscriptss and c are taken to be 1 and 0 (resp.,) when omitted.For anyc∈ℝn, real s>0, andn-dimensional lattice Λ, the discrete Gaussian distribution over Λ is defined as
(3)∀x∈Λ,DΛ,s,c(x)=ρs,c(x)ρs,c(Λ),
where ρs,c(Λ)=∑x∈Λ‍ρs,c(x).Micciancio and Regev [24] proposed a lattice quantity called the smoothing parameter.Definition 3 (see [24]).
For anyn-dimensional lattice Λ and a positive real ϵ>0, the smoothing parameter ηϵ(Λ) is the smallest real s>0 such that ρ1/s(Λ*∖0)≤ϵ, where ρ1/s(Λ*∖0)=∑x∈Λ*∖0‍ρ1/s,0(x).A bound on the smoothing parameter is also given in [24].Lemma 4 (see [25]).
For any n-dimensional latticeΛ and real ϵ>0, one has
(4)ηϵ(Λ)≤log⁡(2n/(1+1/ϵ))/πλ1∞(Λ*).
Then for anyω(log⁡⁡n) function, there is a negligible ϵ(n) for which ηϵ(Λ)≤ω(log⁡⁡n)/λ1∞(Λ*).We notice that a sample from a discrete Gaussian with parameters is at most sn away from its center (in the ℓ2 norm), with overwhelming probability.Lemma 5 (see [24]).
For any n-dimensional latticeΛ, c∈span(Λ), real ϵ∈(0,1), and s≥ηϵ(Λ),
(5)Prx~DΛ,s,c[∥x-c∥>sn]≤1+ϵ1-ϵ·2-n.


## 2.3. Some Lattice Problems

We now redescribe the learning with errors (LWE) problem [6].For an integerq≥2, some probability distribution χ over ℤq, an integer dimension n∈ℤ+, and a vector s∈ℤqn, define 𝒜s,χ as the distribution on ℤqn×ℤq of the variable (a,aTs+x), where a←ℤqn and x←χ are uniform and independent, and all operations are performed in ℤq.Definition 6 (LWE).
For an integerq=q(n) and a distribution χ on ℤq, the goal of the (average-case) learningwitherrors problem LWEq,χ is to distinguish (with nonnegligible probability) between the distribution 𝒜s,χ for some uniform (secret) s←ℤqn and the uniform distribution on ℤqn×ℤq (via oracle access to the given distribution). In other words, if LWE is hard, then the collection of distributions 𝒜s,χ is pseudorandom.𝕋
=
ℝ
/
ℤ as the group of reals [0,1) with mod 1 addition. For α∈ℝ+, Ψα is the distribution on 𝕋 of a normal variable with mean 0 and standard deviation α/2π, reduced modulo 1. For any probability distribution ϕ over 𝕋 and an integer q∈ℤ+ its discretization ϕ¯ is the discrete distribution over ℤq of the random variable ⌊q·Xϕ⌉mod⁡q, where Xϕ has distribution ϕ.Then, we recall two standard worst-case approximation problems on lattices. In both problems,γ=γ(n) is the approximation factor as a function of the dimension.Definition 7 (see [24] shortest vector problem (decision version)).
An input toGapSVPγ is a basis B of a full-rank n-dimensional lattice. It is a YES instance if λ1(ℒ(B))≤d and is a NO instance if λ1(ℒ(B))>γ(n)·d, where disarationalnumber.Definition 8 (see [24] shortest independent vectors problem).
An input toSIVPγ is a full-rank basis B of an n-dimensional lattice. The goal is to output a set of n linearly independent lattice vectors S⊂ℒ(B) such that ∥S∥≤γ(n)·λn(ℒ(B)).Regev demonstrated that for certain moduloq and Gaussian error distributions χ, LWEq,χ is as hard as several standard worst-case lattice problems using a quantum algorithm.Proposition 9 (see [6]).
Letα=α(n)∈(0,1) and let q=q(n) be a prime such that α·q>2n. If there exists an efficient (possibly quantum) algorithm that solves LWEq,Ψ¯α, then there exists an efficient quantum algorithm for approximating SIVP and GapSVP in the l2 norm, in the worst case, within O~(n/α) factors.
The result can be subsequently extended to SIVP and GapSVP in anylp norm, 2≤p≤∞, for essentially the same O~(n/α) approximation factors [25].


## 3. STP-LWE

### 3.1. Semitensor Product

In this section, we introduce the semitensor product (STP) of matrices. The STP-formalism of matrices not only is a generalization of a conventional matrix product, but also makes all the fundamental properties of the conventional matrix product remain true.Definition 10 (see [15]).
(
1
) Let a be a row vector of dimension kl, and let b be a column vector of dimension l. Then we split a into l equal-size blocks named a1,…,al, which are row vectors of dimension k. Define a semitensor product, denoted by ⋉, as
(6)a⋉b=∑i=1l‍aibi∈ℝkbT⋉aT=∑i=1l‍bi(ai)T∈ℝk.
(
2
) Let P∈Mr×l and Q∈Ms×t. If either l is a factor of s, say kl=s and denote it by P≺kQ, or s is a factor of l, say l=ks and denote it by P≻kQ, then define the STP of P and Q, denoted by W=P⋉Q, as the following: W consists of r×t blocks as W=(Wij) and each block is
(7)Wij=Pi⋉Qj,i=1,…,r,j=1,…,t,
where Pi is the ith row of P and Qj is the jth column of Q.The dimension of the STP of two matrices can be described by deleting the largest common factor of the dimensions of the two factor matrices; for example,(8)Pr×kl⋉Ql×t=(P(Q⊗Ik))r×kt,Pr×l⋉Qkl×t=((P⊗Ik)Q)kr×t,
where ⊗ is the Kronecker product and Ik is the identity matrix.If the related products are well defined, the STP satisfies the following laws.(1)
Distributive rule is as follows:(9)P⋉(αQ+βW)=αP⋉Q+βP⋉W,(αQ+βW)⋉P=αQ⋉P+βW⋉P,
where α,β∈ℝ.(2)
Associative rule is as follows:(10)P⋉(Q⋉W)=(P⋉Q)⋉W.


### 3.2. STP-LWE

In this section, we propose a new hardness problem that is called STP-LWE problem which is based on the STP product. The main idea is that we replace the ordinary multiplication of LWE problem with STP. A distribution𝒜s,χ,χ,…,χ︸k should be introduced before giving the definition of STP-LWE problem.For an integerq≥2 and some probability distribution χ over ℤq, an integer dimension n∈ℤ+, and a vector s∈ℤqn/k, define 𝒜s,χ,χ,…,χ︸k as the distribution on ℤqn×ℤq×ℤq×⋯×ℤq︸k of the variable (a,aT⋉s+(x1,x2,…,xk)), where a←ℤqn is uniform and x1,x2,…,xk←χ are independent, and all operations are performed in ℤq.Definition 11 (decisionn/k-dimensional STP-LWE problem).
For an integerq=q(n) and a distribution χ on ℤq, the goal of the decision version (average case) STP-LWEq,χ,χ,…,χ︸k is to distinguish (with nonnegligible probability) between the distribution 𝒜s,χ,χ,…,χ︸k for some uniform (secret) s←ℤqn/k and the uniform distribution on ℤqn×ℤq×ℤq×⋯×ℤq︸k (via oracle access to the given distribution).Definition 12 (searchn/k-dimensional STP-LWE problem).
For an integerq=q(n) and a distribution χ on ℤq, the goal of the search version (average case) STP-LWEq,χ,χ,…,χ︸k is to find the vector s∈ℤqn/k giving a sample (a,aT⋉s+(x1,x2,…,xk)) from the distribution 𝒜s,χ,χ,…,χ︸k.The STP-LWE problem is a generalization of the primal LWE problem. It is obvious that the decisionn/k-dimensional STP-LWE problem and the search n/k-dimensional STP-LWE problem are equal to the primal LWE problem when k=1. The STP-LWE problem could be shown in the form of matrices, consisting of m vectors, and each vector is an instance of LWE problem. Then an instance of STP-LWE problem can be express as (A,AT⋉s+(x1,x2,…,xk)), where A∈ℤqn×m, s∈ℤqn/k is a secret vector, and (x1,x2,…,xk) are from the distribution χm The following theorem shows the hardness of search version n/k-dimensional STP-LWE problem.Theorem 13.
The search versionn/k-dimensional STP-LWEq,χ,χ,…,χ︸k problem is hard under the assumption that LWEq,χ is hard.Proof.
We use proof by contradiction to prove this theorem.
Case
1. Let k=2; then given a search version STP-LWEq,χ,χ instance [b1,b2]=AT⋉s+[x1,x2], where b1,b2∈ℤqm and x1,x2←χm. Suppose we find the vector s∈ℤqn/2 is an easy thing.
Based on the property of STP, we haveAT⋉s=AT(s⊗I2)=AT(s1,s2), where
(11)s1=s⊗[10]=[s10⋮sn20],s2=s⊗[01]=[0s1⋮0sn/2].
Therefore, [b1,b2]=AT⋉s+[x1,x2] can be written as
(12)[b1,b2]=AT[s1,s2]+[x1,x2].
It is equivalent to
(13)ATs1+x1=b1,ATs2+x2=b2.
It is easy to see that this equation contains two LWEq,χ instances. From the assumption that it is a simple question to find the vector s∈ℤqn/2 in the search version STP-LWEq,χ,χ instance [b1,b2]=AT⋉s+[x1,x2], then (13) is also easily solved. That is, the LWEq,χ instance can be solved. This apparently contradicts with the hardness assumption of LWEq,χ problem.
Case2. It is clear that when k>2, n/k-dimensional the STP-LWE problem still holds. The proof of this case is similar to Case 1. This completes the proof.With the increase ofk value, the security of the n/k-dimensional STP-LWE problem will be reduced. In order to prevent this from happening, n/k in the STP-LWE problem must match the security requirements when the scheme can be reduced to lattice problems resisted to the quantum computing. In GPV08 [22], n/k should be larger than 2nlog⁡⁡q


## 3.1. Semitensor Product

In this section, we introduce the semitensor product (STP) of matrices. The STP-formalism of matrices not only is a generalization of a conventional matrix product, but also makes all the fundamental properties of the conventional matrix product remain true.Definition 10 (see [15]).
(
1
) Let a be a row vector of dimension kl, and let b be a column vector of dimension l. Then we split a into l equal-size blocks named a1,…,al, which are row vectors of dimension k. Define a semitensor product, denoted by ⋉, as
(6)a⋉b=∑i=1l‍aibi∈ℝkbT⋉aT=∑i=1l‍bi(ai)T∈ℝk.
(
2
) Let P∈Mr×l and Q∈Ms×t. If either l is a factor of s, say kl=s and denote it by P≺kQ, or s is a factor of l, say l=ks and denote it by P≻kQ, then define the STP of P and Q, denoted by W=P⋉Q, as the following: W consists of r×t blocks as W=(Wij) and each block is
(7)Wij=Pi⋉Qj,i=1,…,r,j=1,…,t,
where Pi is the ith row of P and Qj is the jth column of Q.The dimension of the STP of two matrices can be described by deleting the largest common factor of the dimensions of the two factor matrices; for example,(8)Pr×kl⋉Ql×t=(P(Q⊗Ik))r×kt,Pr×l⋉Qkl×t=((P⊗Ik)Q)kr×t,
where ⊗ is the Kronecker product and Ik is the identity matrix.If the related products are well defined, the STP satisfies the following laws.(1)
Distributive rule is as follows:(9)P⋉(αQ+βW)=αP⋉Q+βP⋉W,(αQ+βW)⋉P=αQ⋉P+βW⋉P,
where α,β∈ℝ.(2)
Associative rule is as follows:(10)P⋉(Q⋉W)=(P⋉Q)⋉W.


## 3.2. STP-LWE

In this section, we propose a new hardness problem that is called STP-LWE problem which is based on the STP product. The main idea is that we replace the ordinary multiplication of LWE problem with STP. A distribution𝒜s,χ,χ,…,χ︸k should be introduced before giving the definition of STP-LWE problem.For an integerq≥2 and some probability distribution χ over ℤq, an integer dimension n∈ℤ+, and a vector s∈ℤqn/k, define 𝒜s,χ,χ,…,χ︸k as the distribution on ℤqn×ℤq×ℤq×⋯×ℤq︸k of the variable (a,aT⋉s+(x1,x2,…,xk)), where a←ℤqn is uniform and x1,x2,…,xk←χ are independent, and all operations are performed in ℤq.Definition 11 (decisionn/k-dimensional STP-LWE problem).
For an integerq=q(n) and a distribution χ on ℤq, the goal of the decision version (average case) STP-LWEq,χ,χ,…,χ︸k is to distinguish (with nonnegligible probability) between the distribution 𝒜s,χ,χ,…,χ︸k for some uniform (secret) s←ℤqn/k and the uniform distribution on ℤqn×ℤq×ℤq×⋯×ℤq︸k (via oracle access to the given distribution).Definition 12 (searchn/k-dimensional STP-LWE problem).
For an integerq=q(n) and a distribution χ on ℤq, the goal of the search version (average case) STP-LWEq,χ,χ,…,χ︸k is to find the vector s∈ℤqn/k giving a sample (a,aT⋉s+(x1,x2,…,xk)) from the distribution 𝒜s,χ,χ,…,χ︸k.The STP-LWE problem is a generalization of the primal LWE problem. It is obvious that the decisionn/k-dimensional STP-LWE problem and the search n/k-dimensional STP-LWE problem are equal to the primal LWE problem when k=1. The STP-LWE problem could be shown in the form of matrices, consisting of m vectors, and each vector is an instance of LWE problem. Then an instance of STP-LWE problem can be express as (A,AT⋉s+(x1,x2,…,xk)), where A∈ℤqn×m, s∈ℤqn/k is a secret vector, and (x1,x2,…,xk) are from the distribution χm The following theorem shows the hardness of search version n/k-dimensional STP-LWE problem.Theorem 13.
The search versionn/k-dimensional STP-LWEq,χ,χ,…,χ︸k problem is hard under the assumption that LWEq,χ is hard.Proof.
We use proof by contradiction to prove this theorem.
Case
1. Let k=2; then given a search version STP-LWEq,χ,χ instance [b1,b2]=AT⋉s+[x1,x2], where b1,b2∈ℤqm and x1,x2←χm. Suppose we find the vector s∈ℤqn/2 is an easy thing.
Based on the property of STP, we haveAT⋉s=AT(s⊗I2)=AT(s1,s2), where
(11)s1=s⊗[10]=[s10⋮sn20],s2=s⊗[01]=[0s1⋮0sn/2].
Therefore, [b1,b2]=AT⋉s+[x1,x2] can be written as
(12)[b1,b2]=AT[s1,s2]+[x1,x2].
It is equivalent to
(13)ATs1+x1=b1,ATs2+x2=b2.
It is easy to see that this equation contains two LWEq,χ instances. From the assumption that it is a simple question to find the vector s∈ℤqn/2 in the search version STP-LWEq,χ,χ instance [b1,b2]=AT⋉s+[x1,x2], then (13) is also easily solved. That is, the LWEq,χ instance can be solved. This apparently contradicts with the hardness assumption of LWEq,χ problem.
Case2. It is clear that when k>2, n/k-dimensional the STP-LWE problem still holds. The proof of this case is similar to Case 1. This completes the proof.With the increase ofk value, the security of the n/k-dimensional STP-LWE problem will be reduced. In order to prevent this from happening, n/k in the STP-LWE problem must match the security requirements when the scheme can be reduced to lattice problems resisted to the quantum computing. In GPV08 [22], n/k should be larger than 2nlog⁡⁡q


## 4. Our Scheme

In this section, we give a variant of GPV dual cryptosystem. First, we recall the dual cryptosystem in GPV08 [22]. Then, we give our construction based on n/k-dimensional STP-LWE problem. Meanwhile, the correctness and security are also shown.


### 4.1. GPV Dual Cryptosystem

It is parameterized by somer≥ω(log⁡m), which specifies the discrete Gaussian distribution 𝔻ℤm,r from which secret keys are chosen. All the users share a common matrix A∈ℤqn×m (an implicit input to all algorithms) chosen uniformly at random, which is the index of the function fA(e)=Aemod⁡q. All the operations are performed over ℤq.(i)
DualKeyGen: choose an error vector e←Dℤm,r (i.e., the input distribution to fA), as the secret key. The public key is the syndrome u=fA(e).(ii)
DualEnc(u,b): to encrypt a bit b∈{0,1}, choose s←ℤqn uniformly and p=ATs+x∈ℤqm, where x←χm. Output the ciphertext (p,c=uTs+x+b·⌊q/2⌋)∈ℤqm×ℤq, where x←χ.(iii)
DualDec(e,(p,c)): compute b′=c-eTp∈ℤq. Output 0 if b′ is closer to 0 than to ⌊q/2⌋ modulo q; otherwise output 1.The correctness and security are given in GPV08 [22], and readers can refer to it for more details.


### 4.2. STP-GPV Dual Cryptosystem

Our public-key dual cryptosystem is based onn/k-dimensional STP-LWE problem, and we let k=2. It is parameterized by some r≥ω(log⁡m), which specifies the discrete Gaussian distribution 𝔻ℤm/2,r from which secret keys are chosen. All the users share a common matrix A∈ℤqn×m (an implicit input to all algorithms) chosen uniformly at random, which is the index of the function fA(e)=A⋉emod⁡q. All the operations are performed over ℤq.(i)
VarKeyGen: choose an error vector e←Dℤm/2,r (i.e., the input distribution to fA), which is the secret key. The public key is the syndrome u=fA(e)=A⋉e, and let u=[u1,u2],whereu1,u2←ℤqn.(ii)
VarEnc(u1,u2,b1,b2): to encrypt two bits b1,b2∈{0,1}, choose s←ℤqn uniformly and p=ATs+x∈ℤqm, where x←χm. Output the ciphertext (p,c1=u1Ts+x1+b1·⌊q/2⌋,c2=u2Ts+x2+b2·⌊q/2⌋)∈ℤqm×ℤq×ℤq, where x1,x2←χ.(iii)
VarDec(e,(p,c1,c2)): compute [b1′,b2′]T=[c1,c2]T-eT⋉p∈ℤq. Output 0 if b1′ and b2′ are closer to 0 than to ⌊q/2⌋ modulo q; otherwise output 1.


### 4.3.  Correctness and Security

The correctness of our scheme is mainly inherited by GPV dual cryptosystem. We can show the correctness as follows:(14)[b1′,b2′]T=[c1,c2]T-eT⋉p∈ℤq=[u1Ts+x1+b1·⌊q/2⌋,u2Ts+x2+b2·⌊q/2⌋]T-eT⋉(ATs+x)=[u1Ts,u2Ts]T+[x1,x2]T+[b1·⌊q/2⌋,b2·⌊q/2⌋]T-[eT⋉ATs]-[eT⋉x].Since[eT⋉ATs]=[A⋉e]Ts=[u1,u2]Ts=[u1Tu2T]s=[u1Tsu2Ts]=[u1Ts,u2Ts]T and  [x1,x2]T-[eT⋉x]=[x1,x2]T-[eT⊗I2]x, let δ1=[10], δ2=[01], [x1,x2]T-[eT⋉x]=[x1,x2]T-[eTδ1x,eTδ2x]T=[x1-eTδ1x,x2-eTδ2x]T. Based on GPV08, we have ∥x1-eTδ1x∥≤q/5 and ∥x2-eTδ2x∥≤q/5. Therefore, ∥[x1,x2]T-[eT⋉x]∥∞=max⁡{∥x1-eTδ1x∥,∥x2-eTδ2x∥}≤q/5.The security of this scheme is similar to that of the GPV dual cryptosystem; that is, our scheme is CPA-secure and anonymous under then/k-dimensional LWEq,χ assumption.


## 4.1. GPV Dual Cryptosystem

It is parameterized by somer≥ω(log⁡m), which specifies the discrete Gaussian distribution 𝔻ℤm,r from which secret keys are chosen. All the users share a common matrix A∈ℤqn×m (an implicit input to all algorithms) chosen uniformly at random, which is the index of the function fA(e)=Aemod⁡q. All the operations are performed over ℤq.(i)
DualKeyGen: choose an error vector e←Dℤm,r (i.e., the input distribution to fA), as the secret key. The public key is the syndrome u=fA(e).(ii)
DualEnc(u,b): to encrypt a bit b∈{0,1}, choose s←ℤqn uniformly and p=ATs+x∈ℤqm, where x←χm. Output the ciphertext (p,c=uTs+x+b·⌊q/2⌋)∈ℤqm×ℤq, where x←χ.(iii)
DualDec(e,(p,c)): compute b′=c-eTp∈ℤq. Output 0 if b′ is closer to 0 than to ⌊q/2⌋ modulo q; otherwise output 1.The correctness and security are given in GPV08 [22], and readers can refer to it for more details.


## 4.2. STP-GPV Dual Cryptosystem

Our public-key dual cryptosystem is based onn/k-dimensional STP-LWE problem, and we let k=2. It is parameterized by some r≥ω(log⁡m), which specifies the discrete Gaussian distribution 𝔻ℤm/2,r from which secret keys are chosen. All the users share a common matrix A∈ℤqn×m (an implicit input to all algorithms) chosen uniformly at random, which is the index of the function fA(e)=A⋉emod⁡q. All the operations are performed over ℤq.(i)
VarKeyGen: choose an error vector e←Dℤm/2,r (i.e., the input distribution to fA), which is the secret key. The public key is the syndrome u=fA(e)=A⋉e, and let u=[u1,u2],whereu1,u2←ℤqn.(ii)
VarEnc(u1,u2,b1,b2): to encrypt two bits b1,b2∈{0,1}, choose s←ℤqn uniformly and p=ATs+x∈ℤqm, where x←χm. Output the ciphertext (p,c1=u1Ts+x1+b1·⌊q/2⌋,c2=u2Ts+x2+b2·⌊q/2⌋)∈ℤqm×ℤq×ℤq, where x1,x2←χ.(iii)
VarDec(e,(p,c1,c2)): compute [b1′,b2′]T=[c1,c2]T-eT⋉p∈ℤq. Output 0 if b1′ and b2′ are closer to 0 than to ⌊q/2⌋ modulo q; otherwise output 1.


## 4.3.  Correctness and Security

The correctness of our scheme is mainly inherited by GPV dual cryptosystem. We can show the correctness as follows:(14)[b1′,b2′]T=[c1,c2]T-eT⋉p∈ℤq=[u1Ts+x1+b1·⌊q/2⌋,u2Ts+x2+b2·⌊q/2⌋]T-eT⋉(ATs+x)=[u1Ts,u2Ts]T+[x1,x2]T+[b1·⌊q/2⌋,b2·⌊q/2⌋]T-[eT⋉ATs]-[eT⋉x].Since[eT⋉ATs]=[A⋉e]Ts=[u1,u2]Ts=[u1Tu2T]s=[u1Tsu2Ts]=[u1Ts,u2Ts]T and  [x1,x2]T-[eT⋉x]=[x1,x2]T-[eT⊗I2]x, let δ1=[10], δ2=[01], [x1,x2]T-[eT⋉x]=[x1,x2]T-[eTδ1x,eTδ2x]T=[x1-eTδ1x,x2-eTδ2x]T. Based on GPV08, we have ∥x1-eTδ1x∥≤q/5 and ∥x2-eTδ2x∥≤q/5. Therefore, ∥[x1,x2]T-[eT⋉x]∥∞=max⁡{∥x1-eTδ1x∥,∥x2-eTδ2x∥}≤q/5.The security of this scheme is similar to that of the GPV dual cryptosystem; that is, our scheme is CPA-secure and anonymous under then/k-dimensional LWEq,χ assumption.


## 5. Performance

The GPV dual cryptosystem and our scheme are implemented in Matlab 2010 in Windows 7 Service Pack1 64 bits operating system. We use a desktop which has a 4-core Intel(R) Core (TM) i3-2120 processor running at 3.30 GHz and 2 GB of RAM.In this section, we analyze the efficiency of the above schemes from the following two aspects. On one hand, we compare the size of public keys, private keys, and ciphertext expansion of GPV dual cryptosystem with our scheme. From the Table1, the efficiency of our algorithm and the ciphertext expansion rate has significant advantage compared with GPV dual cryptosystem. On the other hand, we compare the time cost of VarKeyGen, VarEnc, and VarDec with the GPV dual cryptosystem and the STP-GPV dual cryptosystem. Table 2 has demonstrated the time of key generation, encryption, and decryption for 1 bit in GPV dual cryptosystem, and the time of key generation encryption and decryption for 1 time (which encryption and decryption 2 bits) in STP-GPV dual cryptosystem. The experimental parameters are depicted as follows: n=250, m=8000, and q=127 We obtain these results by running 100 times VarKeyGen, VarEnc, and VarDec and taking the averages.Table 1
k
Size of public key in bits
Size of private key in bits
Ciphertext expansion rate
GPV08
1
n
log
⁡
q
m
log
⁡
q
m
+
1
Ours
2
2
n
log
⁡
q
m
2
log
⁡
q
m
2
+
1Table 2
k
Time of VarKeyGen in seconds
Time of VarEnc in seconds
Time of VarDec in seconds
GPV08
1
7.746
0.4641
0.001225
Ours
2
3.860
0.2369
0.000817By experiments, it is proved that the key generation time and encryption time of our scheme are only half of that of the GPV dual cryptosystem’s, while the decryption time is roughly equal to GPV dual cryptosystem’s.


## 6. Discussion and Conclusions

In this section, we applyn/k-dimensional STP-LWE in the GPV dual cryptosystem problem and build an extended GPV dual cryptosystem. We know that the size of the secret key space varies inversely with the value of k in this proposed extended cryptosystem. For different k∈ℤ, secret keys of length m/k should satisfy the following security requirements. The first restrict is that the value of m/k should be greater than 2nlog⁡⁡q in order to resist the lattice-based reduction algorithm. In this paper, since we pick n=250, m=8000, and q=127, we should choose k<3.The second condition is that the private key should satisfy the inequalityqm/k>280 in order to resist brute-force attacks. Considering the value n, m, and q, we require k<700. The following table lists the time of key generation, encryption, and decryption for one time in 5 different security levels.In Table3, it shows that the time of key generation and the time required for encryption one bit plaintext is reduced gradually with the increasing value of k. At the same time, the time for decrypting one bit ciphertext in different security levels has changed a little.Table 3
k
Time of VarKeyGen
VarEnc for 1 time
VarEnc for 1 bit
VarDec for 1 time
VarDec for 1 bit
5
1.396
0.1552
0.03104
8.17
e
-
4
1.634
e
-
4
10
0.7361
0.1448
0.01448
1.14
e
-
3
1.14
e
-
4
50
0.2253
0.1438
0.002876
7.201
e
-
3
1.44
e
-
4
100
0.06797
0.1465
0.001465
1.3305
e
-
2
1.331
e
-
4
500
0.01594
0.1555
0.000311
6.3646
e
-
2
1.273
e
-
4In this paper, we construct a flexible lattice based scheme based on STP-LWE, which is a variant of learning with errors problem. Our scheme can achieve a balance between the security and efficiency in the hierarchical encryption systems. By using STP-GPV dual cryptosystem, the whole system can reset the security level for messages with the same security parameter.



---

*Source: 341490-2014-04-14.xml*