# Efficient Lattice-Based Signcryption in Standard Model

Authors: Jianhua Yan; Licheng Wang; Lihua Wang; Yixian Yang; Wenbin Yao
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Signcryption is a cryptographic primitive that can perform digital signature and public encryption simultaneously at a significantly reduced cost. This advantage makes it highly useful in many applications.
However, most existing signcryption schemes are seriously challenged by the booming of quantum
computations. As an interesting stepping stone in the post-quantum cryptographic community, two lattice-based
signcryption schemes were proposed recently. But both of them were merely proved to be secure in
the random oracle models. Therefore, the main contribution of this paper is to propose a new lattice-based
signcryption scheme that can be proved to be secure in the standard model.


---

## Body

## 1. Introduction

In many situations, we need to simultaneously realize confidentiality, integrity, authentication, and non-repudiation. There are generally two approaches to accomplish this task: the signature-then-encryption approach and signcryption proposed by Zheng [1]. Compared with the former, signcryption can perform both signature and encryption simultaneously at a lower cost. Hence, the signcryption scheme is more appropriate in many environments such as smart cards, mobile communications, and electronic commerce. Up to date, many efficient signcryption schemes [2–6] have been designed based on various assumptions in number theory. However, the cryptography based on number theory has been seriously challenged due to the booming of quantum computation. Under this situation, many researchers make efforts to probe new cryptosystems based on new security fundamentals, such as quantum cryptography [7–9], chaos cryptography [10, 11], DNA cryptography [12], and so forth. However, as far as we know, there is no efficient signcryption schemes based on these new fundamentals. Therefore, we have to pay our attention to another new upsurging branch of modern cryptography—post-quantum cryptography, including lattice-based cryptography, code-based cryptography, hash-based cryptography, and multivariate cryptography [13].Recently, Li et al. [14] (LMK12) and Wang et al. [15] (WHW12) have succeeded in designing signcryption schemes based on lattice. Lattice-based cryptography has been regarded as the most attractive option for resisting quantum attacks. Meanwhile, it has many important advantages. Firstly, the security of lattice-based cryptography is based on worst-case hardness of lattice problems, while the previous cryptography constructed on number theory is based on average-case hardness. Secondly, the main operations in a lattice-based cryptographic scheme are addition and multiplications over a moderate modulus (say not larger than1024). Thus, taking a long-term look, lattice-based cryptosystems can be performed extremely rapid, compared to the currently used cryptosystems (such as RSA) in which the exponentiations over a huge modulus (say not less than21024) are always involved.However, both of Li et al.’s scheme and Wang et al.’s scheme are merely proved to be secure in the random oracle model. After the publication of Canetti’s critical statement on provable security reduction based on random oracles (ROMs) [16], it is always an interesting practice to design/prove cryptographic schemes that are not based on ROMs. In this paper, we construct a lattice-based signcryption scheme and present its security reductions without using ROMs. Our original ideas can be formulated as follows. The lattice generated by [17] has advantages in small trapdoor and small public key, but its public key encryption scheme can only achieve CCA1 security. The challenger cannot reply the decryption queries for the ciphertext with the first tupleμidentical to the first tupleμ0in the challenge ciphertext in phase two. Moreover, the ciphertext of [17] is malleable. One of the typical methods for transforming an encryption scheme from CCA1 to CCA2 is to make use of a one time strongly unforgeable signature to ensure the nonmalleability of ciphertexts. However, this method will increase the ciphertext length and encryption/decryption time. We setμto be the hash valueH(r,σ),whereris a random number butσis the signature generated in the signcryption process. The domain ofμis big enough such that the probability that the first tuple in the ciphertext generated normally is equal toμ0is negligible. Hence, the challenger can reply the decryption queries in phase two. Further, we use CCA security of the symmetric encryption and collision resistance of hash functionHto prevent the malleability of ciphertext. In the proving process, the hash functionHcan be replaced with a chameleon hash functionHc, so the challenger can generateμ0to form challenge ciphertext. If there exists an adversary who can forge a valid ciphertext, he/she can find a collision ofHc. The probability for the above event is negligible according to [18], so our signcryption scheme can achieve CCA2 security. The strong unforgeability of the signcryption can be obtained by the strong unforgeability of the original signature. In summary, the proposed scheme is(i)
indistinguishable againstinner adaptively chosen ciphertext attacks (IND-CCA2) under the learning with errors (LWE) assumption in the standard model,(ii)
strongly unforgeable againstinner adaptively chosen message attacks (SUF-CMA) under small integer solution (SIS) assumption in the standard model.Here, the term “inner” means that in the IND-CCA2 (resp., SUF-CMA) game, the sender (resp., receiver) who possesses the signing (resp., decryption) key is allowed to launch the corresponding attacks. Apparently, an “inner” attacker is much stronger than outer ones. Thus, the inner security of our proposal also implies its outer security. In addition, our scheme has the advantages both in computational cost and in public/private keys size. That is, our main contribution can be summarized in Table1. In order to make the trapdoors to be consistent, we construct a chameleon hash function by using the new trapdoor technique of [17], that may be of independent interest. In fact, our chameleon hash function is similar with the one in [19]. Although the chameleon hash function in [19] can be used in our scheme, it will lead to use two different kinds trapdoors technique and reduce efficiency.Table 1
Performance comparison.
Versus schemes
Ciphertext length
Computational cost
Public/private keys size
Public parameter size
security
WHW12 [15]
↘
↘
↘
↘
↗
LMK12 [14]
≈
↘
↘
↗
↗The rest of this paper is organized as follows. In Section2, the necessary preliminaries on lattice-based cryptographic assumptions and algorithms are introduced. In Section 3, the security models of signcryption, including the IND-CCA2 game and SUF-CMA game, are reviewed. In Section 4, the main contribution, that is, the proposed lattice-based signcryption scheme is presented in detail, followed by the proof on its consistency. The security proofs are given in Section 5 and the performance comparisons are given in Section 6. Finally, the concluding remarks are given in Section 7.


## 2. Preliminaries

Throughout this paper, we denote the set of integers byℤ, residue classmodqbyℤq, the real numbers byℝ,and real interval[0,1)by𝕋. The expressionℤn(resp.ℤqn,ℝn) denotes vectors space onℤ(resp.ℤq,ℝ) in which every vector hasnelements. Similarly, the expressionℤn×m(resp.ℤqn×m,ℝn×m) denotes matrice space onℤ(resp.ℤq,ℝ) in which every matrix hasnrows andmcolumns. We denote the set{1,2,…,k}by[k], for an integerk>0. The symbol “∣” denotes strings concatenation operators and “∥” denotes matrice concatenation operators. The vectors are denoted by lower-case and bold letters (e.g.,x), matrices by upper-case and bold letters (e.g.,A), and the Gram-Schmidt orthogonalization ofAbyA~. The order for a matrix’s column vectors can be interchangeable. The functions1(·)denotes the largest singular value of a matrix. For a given distributionχover space𝒫, we uses←$χ(𝒫)to denote thatsis picked at random from the space𝒫according to the distributionχ. If the sampling space𝒫is specified from the context, we also simply uses∈χors←$χto denote the same meaning. Also, we uses←$U(P)to denote thatsis picked at random from the space𝒫according to the uniform distribution.


### 2.1. Lattice and Gaussian Distribution

Definition 1 (Lattice).
Ann-dimensional latticeΛis a discrete additive subgroup ofℝm(m≥n). Formally, letB={b1,b2,…,bn}benlinearly independent vectors. The lattice generated byBis
(1)Λ=ℒ(B)={Bx=Σi=1nxibi∣x∈ℤn},
whereBis called a basis forΛ. In many cryptographic applications, a particular family which is calledq-ary integer lattices is frequently used. For positive integersn,m(≥n) andqand matrixA∈ℤqn×m, theq-ary lattices are defined by
(2)Λ⊥(A)={z∈ℤm:Az=0modq},Λ(At)={z∈ℤm:∃s∈ℤqns.t.z=Atsmodq}.For integersn>0andq>2, some probability distributionχoverℤqand a vectors∈ℤqn,As,χis defined as the distribution of(a,ats+x)onℤqn×ℤq, whereaandxare chosen uniformly fromℤqnandχ, respectively.Definition 2 (Learning with Errors (LWE) [23]).
For an integerq=q(n)and a distributionχonℤq, the target of learning with errorsLWEq,χis to distinguish with nonnegligible probability between the distributionAs,χand the uniform distribution onℤqn×ℤqby accessing the oracle for the given distribution, wheres←$U(ℤqn).Forα∈ℝ+,Ψαis defined as the distribution on𝕋of a normal variable with mean0and standard deviationα/2π, reduced modulo1. When normal variablexobeys distributionΨα,Ψ¯αis the discretized normal distribution onℤqof random variable⌊q·x⌉modq, where⌊⌉denotes rounding.Proposition 3 (hardness of LWE [23]).
Letα=α(n)∈(0,1)andq=q(n)be a prime to satisfyαq>2n. If there is an efficient (possibly quantumn) algorithm that can solveLWEq,Ψ¯α, then there is an efficient quantum algorithm for approximatingSIVPγwithinO~(n/α)factors (referring to [24] for its hardness) in the worst case.Definition 4 (Small Integer Solution (SIS) [18]).
Given an integerq, a realβ>0and a matrixA∈ℤqn×m, the goal ofSISq,βis to find a nonzero integer vectorz∈ℤmto satisfyAz=0modqand∥z∥≤β.Proposition 5 (hardness of SIS Theorem 5.16 [18]).
For any polyboundedm,β=poly(n),and for any primeq≥β·ω(nlogn), the average-case problemSISq,βis as hard as approximating the SIVP problem (among others) in the worst case to within certainγ=β·O~(n)factors.Definition 6 (Gaussian measure [18]).
Given any vectorc,x, and reals>0, let
(3)ρs,c(x)=e-π∥(x-c)/s∥2
be a Gaussian function aroundcwith parameters. Its total measure is∫x∈ℝn‍ρs,c(x)dx=sn. The probability density function of the corresponding continuous Gaussian distribution is defined as
(4)∀x∈ℝn,Ds,c(x)=ρs,c(x)sn.
Whenc=0, it is always omitted.Definition 7 (discrete Gaussian distribution [18]).
For any vectorc, reals>0, and latticeΛ, the distribution
(5)∀x∈Λ,DΛ,s,c(x)=Ds,c(x)Ds,c(Λ)=ρs,c(x)ρs,c(Λ)
is called discrete Gaussian distribution overΛ.Proposition 8 (Claim 5.3 [23]).
LetK>1be a constant, and letm>Knlogqbe an integer. The columns of a uniformly randomA∈ℤqn×mgenerate all ofℤqn, except with2-Ω(n)probability.Proposition 9.
LetBbe a basis ofΛ⊥(A), whereA∈ℤqn×mand the columns ofAgenerateℤqn. Lets≥∥B~∥ω(logn).(1)
(Theorem3.1 [20]) Letx←Dℤm,s; the distribution ofy=Ax∈ℤqnisnegl(n)-far from the uniform distribution overℤqn, and the conditional distribution ofxgivenyisDΛy⊥(A),s.(2)
(Lemma4.4 [18])Prx~DΛ,s,v{∥x-v∥>sn}≤((1+ϵ)/(1-ϵ))·2-n.According to nonasymptotic theory of random matrices [25], we have the following lemma.Proposition 10 (Lemma 2.9 [17]).
For anyδ-sub-Gaussian with parametersrandom matrixA∈ℝn×mand any realt>0, there is a constantk>0, such thats1(A)≤ks·(m+n+t)with at least probability1-2δe-πt2.


### 2.2.  Universal Hashes and Chameleon Hashes

In general, we hope a hash function used in cryptographic schemes to be collision resistant. But in our construction, we need further assumptions on involved hashes. One is universal property and another is the so-called Chameleon property.Definition 11 (universal hash functions [26]).
We say that a family of hash functionsℋ={h:𝒳→𝒴}is universal if for every distinct pairx,x'∈𝒳,Prh←ℋ[h(x)=h(x′)]=1/|𝒴|holds.In addition, a kind of specifical hash named chameleon hash introduced by Krawczyk and Rabin [27] is used in our work. The chameleon hash functions have the following four properties: (1) efficient forward computation, (2) standard collision-resistance property, (3) uniformity property, and (4) chameleon property. We will construct a chameleon hash family based on the lattice-trapdoor technique given in [17] and prove it has the above properties in Section 4.1; hence we do not describe these properties here in detail.


### 2.3. Related Algorithms for Inverting and Sampling

Micciancio and Peikert [17] proposed new, simpler, easy-to-implement and more efficient methods to generate and utilize “strong trapdoors” in cryptographic lattices. These methods include specialized algorithms for inverting LWE, which are important for encryption and signature.Firstly, we introduce the related matrices. Letgt=[1,2,4,…,2k-1]∈ℤq1×k,k∈ℕ. Define matrixSkas
(6)Sk=[2q0-12q1-1⋱⋮⋱2qk-2-1qk-1]∈ℤk×k.
The matrixSkcan be easily constructed in the following two cases: (1) whenqis a power of 2, letk=⌈logq⌉,qi=0for0≤i≤k-2,andqk-1=2; (2) whenqis not a power of 2,qiis theith bit ofq. In the former,∥Sk~∥=2and in the latter∥Sk~∥<3by Lemma 4.3 of [17]. It can be verified thatSkis a basis forΛ⊥(gt).LetgG(s,e)=s·gt+etmodq. Givenb∈ℤk-1modqthere exist efficient algorithms to finds∈ℤqande∈ℤksuch thatbt=gG(s,e), whene∈[-q/4,q/4)k=𝒫1/2(q·Sk~-t). There are two cases forq:qis a power of2or not. In the former case, Algorithm 1 can finish this task.Algorithm 1:InvertG(b).
Input:
Vector b∈ℤk, where bt=[b0,…,bk-1].
Output:
Scalar s∈ℤq and a vector e∈ℤk.
(1)s←0;
(2)forj=k-1; k≥0; step -1  do
(3)if  (b𝒾-2𝒾·s)∈[-q/4,q/4)modq  then
(4)t=0;
(5)else
(6)t=1;
(7)end if
(8)s=s+t·2k-1-j;
(9)e𝒾=b𝒾-2𝒾·s∈[-q/4,q/4);
(10)end for
(11)  Outputs∈ℤq and e=(e0,…,ek-1)∈[-q/4,q/4)k⊂ℤk.In the latter case, the above algorithm can work, but the interval for error vectoreneeds to be changed into[-q/23,q/23)k=𝒫1/2(q·Sk~-t). For convenience, the algorithm for the latter case is also called InvertG.The primitive vectorgtand the corresponding latticeΛ(gt)basisSkcan be used to construct parity-check matrixGand matrixSas follows. It follows thatGis a primitive matrix, andSis a basis for latticeΛ⊥(G):
(7)G=[⋯gt⋯⋯gt⋯⋱⋯gt⋯]∈ℤqn×nk,S=[SkSk⋱Sk]∈ℤqnk×nk.Definition 12.
Given matricesA∈ℤqn×mandT∈ℤqm0×knand invertible matrixM∈ℤqn×nfor positive integersn,m,m0,k, ifA[TI]=MGand∥T∥is small enough,Tis called aG-trapdoor ofAcorresponding toM.Given a functiongG(s^,e^)=s^tG+e^tmodqwith suitably smalle^∈ℤnk, an efficient oracle𝒪(b∈ℤqnk)for invertinggG(s^,e^)can be achieved by calling Algorithm 1 forntimes.Given an LWE instancebt=gA(s,e)=stA+etmodqwith suitably smalle∈ℤmand theG-trapdoorTwith corresponding matrixM, Algorithm 2 can recoversande.Algorithm 2:Invert𝒪 (T, A, b, MI).
Input:
Parity-check matrix A∈ℤqn×m;
G-trapdoor T∈ℤm0×kn of A and corresponding invertible tag MI∈ℤqn×n;
Vector bt = gA (s, e) for suitably small e  ∈ℤm.
Output:
Vectors s and e.
(1) Computeb^t = bt[TI];
(2) Obtain (s^, e^) by calling 𝒪(b^);
(3) Returnss = MI-ts^ and e = b−  Ats.Finally, we recall the algorithms, denoted by SampleD and due to Peikert [28], for sampling from Gaussian distribution with short basis.The mechanism of [17] for generating a trapdoor is different from that of [29]. As a result, it uses a new algorithm but also named SampleD to sample from a discrete Gaussian overΛu⊥(A)in [17], in which Algorithm 3 is called. It is used in signature and delegation. For distinction, let us call it SampleDG. The reader can refer to Theorem 5.5 of [17] for the correctness (Algorithm 4).Algorithm 3:SampleD(B, c, r, Σ).
Input:
Offline phase: Basis B of a q-ary integer Λ=L(B); rounding parameter r=ω(logn);
positive definite covariance matrix Σ≥r2·(4BBt+I);
Online phase: a vector c∈ℤn;
Output:
Vector v∈  Λ +c drawn from a distribution within negl(n) statistical distance of DΛ+c,Σ;
Offline phase:
(1) ComputeZ=q·B-1∈ℤn×n;
(2) LetΣ1= 2r2·BBt, let Σ2= Σ− Σ1≥ r2·(2BBt)+I, and compute some MB1=Σ2-r2;
(3) Choosey from Dℤn,Σ2 by letting y←⌊B1·D1⌉r;
Online phase:
(4) Returnx←⌊Z(c-y)/q⌉r.Algorithm 4:SampleDG(T, A0, MI, y, s).
Input:
Offline phase:
(i) Trapdoor matrixT∈Zqm0×w;
(ii) Partial parity-check matrixA0∈ℤqn×m0;
(iii) Positive definiteΣ≥[TI](2+ΣG)[Tt∥I], for example, any Σ=s2≥(s1(T)2+1)(s1(ΣG)+2).
Online phase:
(i) Invertible tagMI∈ℤqn×m defining A=[A0∥MIG-A0T];
(ii) Syndromey∈ℤqn.
Output:
A vector x, which is statistically close to DΛ(1/y)(A),rΣ.
Offline phase:
(1) ComputeΣp=Σ-[TI]ΣG[Tt∥I]≥2[TI][Tt∥I], choose vector p←Dℤm,rΣp;
(2) ParseP=[P1P2] where p1∈ℤm0, p2∈ℤw. Compute w0=A0(p1-Tp2)∈ℤqn and w=GP2∈ℤqn;
Online phase:
(3) Computev←MI-1(y-w0)-w=MI-1(y-Ap)∈ℤqn;
(4) Choosez←DΛ(1/V)(G),rΣG by calling SampleD(Sk,v,r,ΣG) see Algorithm 3;
(5) Returnx=p+[TI]z.


## 2.1. Lattice and Gaussian Distribution

Definition 1 (Lattice).
Ann-dimensional latticeΛis a discrete additive subgroup ofℝm(m≥n). Formally, letB={b1,b2,…,bn}benlinearly independent vectors. The lattice generated byBis
(1)Λ=ℒ(B)={Bx=Σi=1nxibi∣x∈ℤn},
whereBis called a basis forΛ. In many cryptographic applications, a particular family which is calledq-ary integer lattices is frequently used. For positive integersn,m(≥n) andqand matrixA∈ℤqn×m, theq-ary lattices are defined by
(2)Λ⊥(A)={z∈ℤm:Az=0modq},Λ(At)={z∈ℤm:∃s∈ℤqns.t.z=Atsmodq}.For integersn>0andq>2, some probability distributionχoverℤqand a vectors∈ℤqn,As,χis defined as the distribution of(a,ats+x)onℤqn×ℤq, whereaandxare chosen uniformly fromℤqnandχ, respectively.Definition 2 (Learning with Errors (LWE) [23]).
For an integerq=q(n)and a distributionχonℤq, the target of learning with errorsLWEq,χis to distinguish with nonnegligible probability between the distributionAs,χand the uniform distribution onℤqn×ℤqby accessing the oracle for the given distribution, wheres←$U(ℤqn).Forα∈ℝ+,Ψαis defined as the distribution on𝕋of a normal variable with mean0and standard deviationα/2π, reduced modulo1. When normal variablexobeys distributionΨα,Ψ¯αis the discretized normal distribution onℤqof random variable⌊q·x⌉modq, where⌊⌉denotes rounding.Proposition 3 (hardness of LWE [23]).
Letα=α(n)∈(0,1)andq=q(n)be a prime to satisfyαq>2n. If there is an efficient (possibly quantumn) algorithm that can solveLWEq,Ψ¯α, then there is an efficient quantum algorithm for approximatingSIVPγwithinO~(n/α)factors (referring to [24] for its hardness) in the worst case.Definition 4 (Small Integer Solution (SIS) [18]).
Given an integerq, a realβ>0and a matrixA∈ℤqn×m, the goal ofSISq,βis to find a nonzero integer vectorz∈ℤmto satisfyAz=0modqand∥z∥≤β.Proposition 5 (hardness of SIS Theorem 5.16 [18]).
For any polyboundedm,β=poly(n),and for any primeq≥β·ω(nlogn), the average-case problemSISq,βis as hard as approximating the SIVP problem (among others) in the worst case to within certainγ=β·O~(n)factors.Definition 6 (Gaussian measure [18]).
Given any vectorc,x, and reals>0, let
(3)ρs,c(x)=e-π∥(x-c)/s∥2
be a Gaussian function aroundcwith parameters. Its total measure is∫x∈ℝn‍ρs,c(x)dx=sn. The probability density function of the corresponding continuous Gaussian distribution is defined as
(4)∀x∈ℝn,Ds,c(x)=ρs,c(x)sn.
Whenc=0, it is always omitted.Definition 7 (discrete Gaussian distribution [18]).
For any vectorc, reals>0, and latticeΛ, the distribution
(5)∀x∈Λ,DΛ,s,c(x)=Ds,c(x)Ds,c(Λ)=ρs,c(x)ρs,c(Λ)
is called discrete Gaussian distribution overΛ.Proposition 8 (Claim 5.3 [23]).
LetK>1be a constant, and letm>Knlogqbe an integer. The columns of a uniformly randomA∈ℤqn×mgenerate all ofℤqn, except with2-Ω(n)probability.Proposition 9.
LetBbe a basis ofΛ⊥(A), whereA∈ℤqn×mand the columns ofAgenerateℤqn. Lets≥∥B~∥ω(logn).(1)
(Theorem3.1 [20]) Letx←Dℤm,s; the distribution ofy=Ax∈ℤqnisnegl(n)-far from the uniform distribution overℤqn, and the conditional distribution ofxgivenyisDΛy⊥(A),s.(2)
(Lemma4.4 [18])Prx~DΛ,s,v{∥x-v∥>sn}≤((1+ϵ)/(1-ϵ))·2-n.According to nonasymptotic theory of random matrices [25], we have the following lemma.Proposition 10 (Lemma 2.9 [17]).
For anyδ-sub-Gaussian with parametersrandom matrixA∈ℝn×mand any realt>0, there is a constantk>0, such thats1(A)≤ks·(m+n+t)with at least probability1-2δe-πt2.


## 2.2.  Universal Hashes and Chameleon Hashes

In general, we hope a hash function used in cryptographic schemes to be collision resistant. But in our construction, we need further assumptions on involved hashes. One is universal property and another is the so-called Chameleon property.Definition 11 (universal hash functions [26]).
We say that a family of hash functionsℋ={h:𝒳→𝒴}is universal if for every distinct pairx,x'∈𝒳,Prh←ℋ[h(x)=h(x′)]=1/|𝒴|holds.In addition, a kind of specifical hash named chameleon hash introduced by Krawczyk and Rabin [27] is used in our work. The chameleon hash functions have the following four properties: (1) efficient forward computation, (2) standard collision-resistance property, (3) uniformity property, and (4) chameleon property. We will construct a chameleon hash family based on the lattice-trapdoor technique given in [17] and prove it has the above properties in Section 4.1; hence we do not describe these properties here in detail.


## 2.3. Related Algorithms for Inverting and Sampling

Micciancio and Peikert [17] proposed new, simpler, easy-to-implement and more efficient methods to generate and utilize “strong trapdoors” in cryptographic lattices. These methods include specialized algorithms for inverting LWE, which are important for encryption and signature.Firstly, we introduce the related matrices. Letgt=[1,2,4,…,2k-1]∈ℤq1×k,k∈ℕ. Define matrixSkas
(6)Sk=[2q0-12q1-1⋱⋮⋱2qk-2-1qk-1]∈ℤk×k.
The matrixSkcan be easily constructed in the following two cases: (1) whenqis a power of 2, letk=⌈logq⌉,qi=0for0≤i≤k-2,andqk-1=2; (2) whenqis not a power of 2,qiis theith bit ofq. In the former,∥Sk~∥=2and in the latter∥Sk~∥<3by Lemma 4.3 of [17]. It can be verified thatSkis a basis forΛ⊥(gt).LetgG(s,e)=s·gt+etmodq. Givenb∈ℤk-1modqthere exist efficient algorithms to finds∈ℤqande∈ℤksuch thatbt=gG(s,e), whene∈[-q/4,q/4)k=𝒫1/2(q·Sk~-t). There are two cases forq:qis a power of2or not. In the former case, Algorithm 1 can finish this task.Algorithm 1:InvertG(b).
Input:
Vector b∈ℤk, where bt=[b0,…,bk-1].
Output:
Scalar s∈ℤq and a vector e∈ℤk.
(1)s←0;
(2)forj=k-1; k≥0; step -1  do
(3)if  (b𝒾-2𝒾·s)∈[-q/4,q/4)modq  then
(4)t=0;
(5)else
(6)t=1;
(7)end if
(8)s=s+t·2k-1-j;
(9)e𝒾=b𝒾-2𝒾·s∈[-q/4,q/4);
(10)end for
(11)  Outputs∈ℤq and e=(e0,…,ek-1)∈[-q/4,q/4)k⊂ℤk.In the latter case, the above algorithm can work, but the interval for error vectoreneeds to be changed into[-q/23,q/23)k=𝒫1/2(q·Sk~-t). For convenience, the algorithm for the latter case is also called InvertG.The primitive vectorgtand the corresponding latticeΛ(gt)basisSkcan be used to construct parity-check matrixGand matrixSas follows. It follows thatGis a primitive matrix, andSis a basis for latticeΛ⊥(G):
(7)G=[⋯gt⋯⋯gt⋯⋱⋯gt⋯]∈ℤqn×nk,S=[SkSk⋱Sk]∈ℤqnk×nk.Definition 12.
Given matricesA∈ℤqn×mandT∈ℤqm0×knand invertible matrixM∈ℤqn×nfor positive integersn,m,m0,k, ifA[TI]=MGand∥T∥is small enough,Tis called aG-trapdoor ofAcorresponding toM.Given a functiongG(s^,e^)=s^tG+e^tmodqwith suitably smalle^∈ℤnk, an efficient oracle𝒪(b∈ℤqnk)for invertinggG(s^,e^)can be achieved by calling Algorithm 1 forntimes.Given an LWE instancebt=gA(s,e)=stA+etmodqwith suitably smalle∈ℤmand theG-trapdoorTwith corresponding matrixM, Algorithm 2 can recoversande.Algorithm 2:Invert𝒪 (T, A, b, MI).
Input:
Parity-check matrix A∈ℤqn×m;
G-trapdoor T∈ℤm0×kn of A and corresponding invertible tag MI∈ℤqn×n;
Vector bt = gA (s, e) for suitably small e  ∈ℤm.
Output:
Vectors s and e.
(1) Computeb^t = bt[TI];
(2) Obtain (s^, e^) by calling 𝒪(b^);
(3) Returnss = MI-ts^ and e = b−  Ats.Finally, we recall the algorithms, denoted by SampleD and due to Peikert [28], for sampling from Gaussian distribution with short basis.The mechanism of [17] for generating a trapdoor is different from that of [29]. As a result, it uses a new algorithm but also named SampleD to sample from a discrete Gaussian overΛu⊥(A)in [17], in which Algorithm 3 is called. It is used in signature and delegation. For distinction, let us call it SampleDG. The reader can refer to Theorem 5.5 of [17] for the correctness (Algorithm 4).Algorithm 3:SampleD(B, c, r, Σ).
Input:
Offline phase: Basis B of a q-ary integer Λ=L(B); rounding parameter r=ω(logn);
positive definite covariance matrix Σ≥r2·(4BBt+I);
Online phase: a vector c∈ℤn;
Output:
Vector v∈  Λ +c drawn from a distribution within negl(n) statistical distance of DΛ+c,Σ;
Offline phase:
(1) ComputeZ=q·B-1∈ℤn×n;
(2) LetΣ1= 2r2·BBt, let Σ2= Σ− Σ1≥ r2·(2BBt)+I, and compute some MB1=Σ2-r2;
(3) Choosey from Dℤn,Σ2 by letting y←⌊B1·D1⌉r;
Online phase:
(4) Returnx←⌊Z(c-y)/q⌉r.Algorithm 4:SampleDG(T, A0, MI, y, s).
Input:
Offline phase:
(i) Trapdoor matrixT∈Zqm0×w;
(ii) Partial parity-check matrixA0∈ℤqn×m0;
(iii) Positive definiteΣ≥[TI](2+ΣG)[Tt∥I], for example, any Σ=s2≥(s1(T)2+1)(s1(ΣG)+2).
Online phase:
(i) Invertible tagMI∈ℤqn×m defining A=[A0∥MIG-A0T];
(ii) Syndromey∈ℤqn.
Output:
A vector x, which is statistically close to DΛ(1/y)(A),rΣ.
Offline phase:
(1) ComputeΣp=Σ-[TI]ΣG[Tt∥I]≥2[TI][Tt∥I], choose vector p←Dℤm,rΣp;
(2) ParseP=[P1P2] where p1∈ℤm0, p2∈ℤw. Compute w0=A0(p1-Tp2)∈ℤqn and w=GP2∈ℤqn;
Online phase:
(3) Computev←MI-1(y-w0)-w=MI-1(y-Ap)∈ℤqn;
(4) Choosez←DΛ(1/V)(G),rΣG by calling SampleD(Sk,v,r,ΣG) see Algorithm 3;
(5) Returnx=p+[TI]z.


## 3. Signcryption: Primitive and Security Models

Signcryption was invented in 1996 but was first disclosed to the public at CRYPTO 1997 [1]. Signcryption is a public key cryptographic method that achieves unforgeability and confidentiality simultaneously with significantly smaller overhead than that required by “digital signature followed by public key encryption.” It does this by signing and encrypting a message in a single step, fulfilling a cryptographer’s dream to “kill two birds with one stone” [1, 3]. Signcryption techniques are now a global standard for data protection [30].The primitive of signcryption provides confidentiality of the message against all entities except the intended receiver and meanwhile it provides the authenticity of the sender (i.e., the signer) for the intended receiver. It is clear that the authenticity embedded in the signcryption primitive is unidirectional, instead of bidirectional. In particular, if an intended receiver can forge a signature on behalf of some signer, he/she can plant some false evidence against the signer and then encrypt the signature for himself/herself. By doing so, the singer is incriminated. Therefore, in considering the security of signcryption, we should take into account the orthogonal combination of two kinds of attackers (i.e., inner attackers and outer attackers) and two protection goals (i.e., unforgeability and confidentiality). In 2005, Dent [31, 32] gave comprehensive elaborations on the inner security and outer security of signcryption. With the purpose of providing a handy consult for the security reduction given latter, we give a review on the security models of signcryption from LMK12 [14], in which we merely formulated the security models against inner attacker because in general an inner attacker is much stronger than an outer ones.Definition 13 (signcryption).
A signcryption scheme consists of the following four algorithms.(i)
Setup(1n): this is an initialization algorithm that should be executed only once by any honest user in the system. It takes as input the security parameter1nand outputs the public parameters𝒫pthat are shared by all users in the system.(ii)
KeyGen(1n,𝒫p): this is a key generation algorithm that should be executed by each user only once. It takes as inputs the security parameter1nas well as the public parameters𝒫pand outputs the public/private key pair(PK,SK)wherePKwill be published publicly whileSKwill be kept known only to the user himself/herself. (In sequel, let us assume that the sender’s public/private key pair is(PKs,SKs), while the receiver’s is(PKr,SKr).)(iii)
Signcrypt(u,PKr,PKs,SKs): this is a signcryption algorithm that should be executed by a senders whenever he/she wants to send a message to someone. It takes as inputs a messageu, the intended receiver’s public keyPKr,and the sender’s public/private key pair(PKs,SKs)and outputs a signcryption ciphertextC.(iv)
Unsigncrypt(C,PKr,SKr,PKs): this is a unsigncryption algorithm that should be executed by a receiver. It takes as inputs a signcryption ciphertextcand the receiver’s public/private key pair(PKr,SKr), as well as the sender’s public keyPKs, and outputs a plaintextuor⊥.Definition 14 (consistency of signcryption).
We say that a signcryption scheme defined above is consistent if the following probability(8)Pr[𝒫p⟵Setup(1n);(PKr,SKr)⟵KeyGen(1n,𝒫p);(PKs,SKs)⟵KeyGen(1n,𝒫p);C⟵Signcrypt(u,PKr,PKs,SKs);u′⟵Unsigncrypt(C,SKr,PKs):u′=u]=1-ϵ(n)
is exponentially close to 1; that is,ϵ(n)is negligible with respect ton.To capture the confidentiality of a signcryption defined above, we need to introduce a game, denoted byGame IND-CCA2, between a challenger𝒞and an adversary𝒜as follows.Game IND-CCA2
(i)
Initial:𝒞runsSetup(1k)algorithm to produce public parameter𝒫pand then generates his/her own public/private keys(PKr*,SKr*)by runningKeyGen(1n,𝒫p)algorithm. Finally,𝒞givesPKr*and𝒫pto𝒜.
(ii)
Phase  1:𝒜can perform polynomially bounded unsigncryption queries in an adaptive manner and𝒞responds accordingly. More precisely,𝒜’s query is specified by a triple(C,PKs)and𝒞’s responds with the corresponding plaintextuifCis a valid signcryption ciphertext with respect to the receiver’s public keyPKr*and sender’s public keyPKsor⊥otherwise.
(iii)
Challenge:𝒜chooses two equal length plaintextsu0,u1and sends(u0,u1,PKs*,SKs*)to𝒞, and𝒞tosses a fair coinb∈{0,1}and setsC*←Signcrypt(ub,PKr*,PKs*,SKs*). Finally,𝒞sends𝒜the challenged signcryption ciphertextC*.
(iv)
Phase  2: phase 1 is repeated with the restriction that𝒜is not allowed to ask unsigncryption query on triple(C*,PKs*).
(v)
Guess:𝒜outputs a bitb′as his/her guessing onb.Then, the advantage of𝒜to win Game IND-CCA2 is defined asAdv(𝒜)=|Pr[b=b′]-(1/2)|.Definition 15 (confidentiality of signcryption).
A signcryption scheme is said to be indistinguishable against inner chosen ciphertext attacks (IND-CCA2), if there is no probabilistic polynomial time adversary that can winGame IND-CCA2 with nonnegligible advantage.To capture the (strong) unforgeability of a signcryption defined above, we need to introduce another game, denoted byGame SUF-CMA, between a challenger𝒞and a forgeryℱas follows.Game SUF-CMA
(i)
Initial:𝒞runsSetup(1k)algorithm to produce public parameter𝒫pand then generates his/her own public/private keys(PKs*,SKs*)by runningKeyGen(1n,𝒫p)algorithm. Finally,𝒞givesPKs*and𝒫ptoℱ.
(ii)
Singcrypt query:ℱcan perform polynomially bounded signcryption queries in an adaptive manner. More precisely,ℱ’s query is specified by a pair(u,PKr)and𝒞’s responds withC←Signcrypt(u,PKr,PKs*,SKs*). (Here,PKris the intended receiver’s public key and the corresponding private keySKris known toℱ. Furthermore,ℱis allowed to either obtain(PKr,SKr)by calling the algorithmKeyGen(1n,𝒫p)or pick them randomly.)
(iii)
Forgery:ℱoutputs a tuple(u*,C*,PKr*,SKr*)with the restriction that𝒞never responds toℱwithC*for answeringℱ’s signcryption query on(u*,PKr*).Then, the advantage ofℱto win Game SUF-CMA is defined as
(9)Adv(ℱ)=Pr[u*=Unsigncrypt(C*,PKr*,SKr*,PKs*)].Definition 16 (strong unforgeability of signcryption).
A signcryption scheme is said to be strongly unforgeable against inner adaptively chosen message attacks (SUF-CMA), if no probabilistic polynomial time adversary can winGame SUF-CMA with nonnegligible advantage.


## 4. Proposed Lattice-Based Signcryption Scheme

In this section, we firstly present a chameleon hash function based on the lattice-trapdoor technique given in [17]. Next, based on the signature scheme and the encryption scheme given in [17], we propose a signcryption scheme. Finally, we prove the consistency of the proposed scheme. Note that, the matricesG,S,Skused in this section are as in Section 2.3.


### 4.1. Building Block: Lattice-Based Chameleon Hash Functions

According to [33, 34], we know that by using a chameleon hash function, one can transfer an SUF-SMA secure signature scheme to an SUF-CMA secure one. To guarantee the consistency of the proposed scheme, we need to construct a chameleon hash function based on lattice-based trapdoors of given in [17]. In fact, it is a analogue to the scheme based on the trapdoors given in [29].Letn≥1,q≥2,m0=O(nlogq), andk=O(logq)be integers. Let integerl>0be message length. For matricesN(0)∈ℤqn×l,N(z)∈ℤqn×m0, andT~Dℤ,ω(logn)m0×nkand invertible matrixM∈ℤqn×nconstructN(1)=[N(z)∥N(y)]=[N(z)∥-N(z)T+MG]∈ℤqn×mandN=[N(0)∥N(1)]. Letsbe a Gaussian parameter satisfyings≈5s1(T)ω(logn)suggested by [17]. Define a message spaceℳ={0,1}land random spaceℛ=Dℤm,s(then, forr∈ℛ,∥r∥≤smholds with overwhelming probability according to Proposition 9 items (2)) and𝒴∈𝕫qn. Foru∈ℳandr∈ℛ, using matrixNdefine hash functionHN:ℳ×ℛ→𝒴as
(10)HN(u,r)=N(0)u+N(1)r.Lemma 17.
The familyℋ={HN}(under the uniform distribution overℋ) is a family of chameleon hash functions, assuming the hardness ofSISq,βforβ2=l+4s2m.Proof.
It is enough to prove the hash familyℋ={HN}has the four properties described in Section 2.2.
For efficient forward computation. Clearly, given a messageu∈ℳandr∈ℛ, eachHN(u,r)is efficiently computable.
For collision-resistance property. Assuming that it is easy to find a collision[u∥r]≠[u′∥r′]∈ℳ×ℛforHN, thenx=[u-u′∥r-r′]≠0is a solution forNx=0, and according to the triangle inequality, we have that∥x∥2≤l+4s2m. It implies thatxis also a solution for the instanceNofSISq,β. This contradicts the hardness ofSISq,βforβ=l+4s2m. Therefore, the hash family is collision-resistant.
For uniformity property, we first show the matrixNis uniform. The matrixN(z)is uniform, soN(z)Tis also uniform whenT~Dℤ,ω(logn)m0×nkisnegl(n)-far from uniform (cf. Section 6.2 of [17]). On the other hand, the matrixMGis fixed whenMis fixed. Consequently, the matrixN(1)isnegl(n)-far from uniform. On the other hand,N(0)is uniform; henceNisnegl(n)-far from uniform. It is clear that given anym∈ℳandr←Dℤm,sand each matrixNgenerated as above, the distribution ofHN(m,r)is negligible far from the uniform distribution overℋ×𝒴by Proposition 9 items (1).
For chameleon property. Givenu,u′∈ℳandr∈ℛ, one withG-trapdoorTcan easily findr′∈ℛsatisfyingHN(u,r)=HN(u′,r′)as follows: computey=HN(u,r)-N(0)u′, and then sample preimager′=SampleDG(T,N(z),M,y,s).Lemma 18.
The above chameleon hash family is universal; for every distinctu,u′∈ℳand distinctr,r′∈ℛ,PrHN←ℋ[HN(u,r)=HN(u′,r′)]=q-n.Proof.
Assuming thatHN(u,r)=HN(u′,r′), it follows thatN(1)r′=HN(u,r)-N(0)u′. Whenu,r,u′is fixed, the vectorz=HN(u,r)-N(0)u′is a fixed element inℤqn.
The matrixN(1)is uniform as described above. Form0=O(nlogq),m=m0+nk≥2nlogq, the columns ofN(1)∈ℤqn×mgenerateℤqnwith overwhelming probability by Proposition 8. In addition,s≥∥S~∥ω(logn)andr′~Dℤm,s, whereSis as in Section 2.3.
It follows thatN(1)r′is uniform overℤqn(up to negligible statistical distance) by Proposition 9 items (1). Consequently,Pr[N(1)r′=z]=q-n. In other words,PrHN←ℋ[HN(u,r)=HN(u′,r′)]=q-n.


### 4.2.  Signcryption Scheme

In [17], Micciancio and Peikert gave a special collector (MP collector) that maps elements from a certain ringℜinto matricesH∈ℤqn×nas required by their trapdoor construction. Let us call it MP Collector and denote it byħ:ℜ→ℤqn×n. Given a monic degree-nirreducible polynomialf(x)=xn+fn-1xn-1+⋯+f0∈ℤ[x], a ring can be defined asℜ=ℤ[x]/(f(x))and the elements ofℜcan be represented as vectors inℤnrelative to the standard basis of monomials1,x,…,xn-1. Now, given a ring elementa(x)=a0+a1x+⋯+an-1xn-1∈ℜ,ħ(a)can be constructed as follows:
(11)h(0)=(a0,a1,…,an-1),h(i)=(0,h0(i-1),…,hn-2(i-1))-hn-2(i-1)(f0,f1,…,fn-1),
for0≤i<n, whereh(i)is theith column ofħ(a). Clearly,ħhas the following properties. Firstly,ħis a ring homomorphism, namely,ħ(x1)-ħ(x2)=ħ(x1-x2)forx1,x2∈ℜ. Secondly, multiplication by a ring elementa∈ℜcan be represented by the matrixħ(a); furthermore, the product coefficients vector equals∑i=0n-1‍biha(i), whereha(i)is theith column ofħ(a)andbiis theith coefficient of ring element. Thirdly,ħ(x)∈GLn(q)if and only ifxis a unit ofℜ, whereGLn(q)is a group composed of the invertible elements inℤqn×n. Finally, the ringℜhas “units difference” property, namely, for anyxi,xj∈ℜ*(ℜ*denotes the units set inℜ),xi-xj∈ℜ*.Our signcryption scheme consists of the following four algorithms. Note that we also adopt a symmetrical encryption schemeΠ=(𝒦,ℰ,𝒟)(with keyspace𝒦, encryption algorithmℰ,and decryption algorithm𝒟) in our construction.(i)
Setup(1n): Suppose the security parameter is1n. Then, the the public parameters𝒫pfor the system can be specified as follows.
(1)
G∈ℤqn×nkis the matrix as defined in Section 2.3, whereq=pe=poly(n)is a prime power and is large enough (cf. [17]).(2)
k=O(logq)=O(logn).(3)
m0=O(nk),m=m0+nk,m1=m0+2nk,and suitablel>0.(4)
α∈(0,1)is an LWE error rate, such that1/α=O(nk)·ω(logn).(5)
s′≥5·ω(logn).(6)
A monic degree-nirreducible polynomialf(x)=xn+fn-1xn-1+⋯+f0∈ℤp[x]and a ring defined asℜ=ℤq[x]/(f(x)).(7)
4 hash functions:
(a)
H0:{0,1}*×ℤqn×m→{0,1}λis a collision-resistant hash function, whereλ<n(p-1);(b)
H1:ℤqm1→{0,1}lis a universal hash function;(c)
HF:{0,1}l×ℤqm→ℜ*is chosen from a universal family, whereFis a matrix inℤqn×(l+m). More precisely,F=[F(0)∥F(1)]∈ℤqn×l×ℤqn×m, andF(0)(resp.,F(1)) has the same distribution withN(0)(resp.,N(1)) described in Section 4.1 (note that the elements inℜcan be represented by vectors inℤqn);(d)
H2:{0,1}nk×ℤ2qm→{0,1}n·k′is a universal hash function with suitably specifiedk′.(8)
An ordered matrix set𝔅={B(0),…,B(λ)}whereB(i)←$U(ℤqn×nk)for0≤i≤λ.(9)
ss=O(λnk)ω(logn)2is the Gaussian parameter for signature.(10)
An arbitary basisQ∈ℤnk×nkforΛ=Λ(Gt).(11)
MP Collectorħ:R→ℤqn×n.(ii)
KeyGen(1n,𝒫p): any user can generate his/her public keyPKand private keySKas follows.
(a)
SampleA(0)←$ℤqn×m0andT←$Dℤ,ω(logn)m0×nk;(b)
EvaluateA(1)=-A(0)T;(c)
LetPK≜A=[A(0)∥A(1)]∈ℤqn×mandSK≜T.(iii)
Signcrypt(u,Ar,As,Ts): a sender with public/private key pair(As,Ts)can send a signcryption ciphertextcon some messageuto a receiver with public keyAras follows.
(1)
Sign messageuto obtain(σ,r1), as follows.
(a)
Computeh=H0(u,Ar),A′=B(0)+∑i∈[λ]‍hiB(i)and then build
(12)As(h)=[As∥A′]∈ℤn×m1,whereh=(h1,…,hλ)∈{0,1}λis the binary representation ofh.(b)
Construct chameleon hash function according to the method in Section4.1. Concretely, replaceN(1),N(0),MwithAs, arbitrarylcolumns ofA′,I∈ℤqn×n, respectively. The others are invariant. The hash function is denoted asHAs(h).(c)
Sampler1←$Dℤnk,ss.(d)
Computehr=HAs(h)(h,r1).(e)
Sampley←$Dℤnk,ssand computey′=hr-A′y.(f)
Sampleσor←SampleDG(Ts,As(0),I,y′,ss), whereI∈ℤn×nis identity matrix.(g)
Letσ=(σor,y).(2)
Parseσ=(σ1,σ2)such thatσ1∈{0,1}nkand denote the remainder asσ2.(3)
Computew=H1(σ).(4)
Encryptσ1as follows.
(a)
Samplee0←$Dℤ,αqm0and evaluatesr=∥e0∥2+m0(αq)2·ω(logn).(b)
Samplee1←$Dℤ,srnk, and lete=(e0,e1).(c)
Sampler2←$Dℤnk,s′, then computeμ=HF(w,r2),and constructAr(μ)=[Ar(0)∥Ar(1)+ħ(μ)G].(d)
Encodeσ1asσ1′=encode(σ1)=Qσ1∈ℤnk.(e)
Choose a vectors←$ℤqnuniformly and let
(13)bt=2(stAr(μ)modq)+et+(0,σ1′)tmod2q.(5)
Encryptuas follows.
(a)
Letk′=H2(σ1,b)∈𝒦.(b)
Letc=ℰk′(u∣σ2∣r1∣r2).(6)
Output the signcryption ciphertext(μ,b,c).(iv)
Unsigncrypt(C,Ar,Tr,As): upon receiving a signcryption ciphertext(μ,b,c)from a sender with the public keyAs, the receiver with the private keyTrperforms the following steps.
(1)
Decrypt(μ,b)to achieveσ1as follows.
(a)
Ifμ=0, output⊥and then abort; otherwise continue.(b)
CallInvert𝒪(Tr,Ar(μ),b,ħ(μ))to obtain(z~,e~), wherez~∈ℤqnande~=(e~0,e~1)∈ℤm0×ℤnk.(c)
If∥e~0∥≥αqm0or∥e~1∥≥αq2m0nk·ω(logn)output⊥and abort; otherwise continue.(d)
Letv=b-e~mod2qand then parsevas(v1,v2)∈ℤ2qm0×ℤ2qnk.(e)
Ifv1∉2Λ((Ar0)t), output⊥and abort; otherwise, continue.(f)
Letσ~1=Q-1(vt[TrI]mod2q).(2)
Decryptcas follows.
(a)
Computek′=H2(σ~1,b)∈𝒦.(b)
Computeu~|σ~2|r~1|r~2=𝒟k′(c).(3)
Check the integrity of ciphertext as follows.
(a)
Obtainσ~by composingσ~1,σ~2, and then computew~=H1(σ~).(b)
Ifμ≠HF(w~,r~2)output⊥and abort; otherwise, continue.(c)
If∥r~2∥≥s′moutput⊥and abort; otherwise, continue.(4)
Verifying the sender’s authenticity as follows.
(a)
Computeh~=H0(u~,Ar)and then buildAs(h~)=[As∥B(0)+∑i∈[λ]‍h~iB(i)], whereh~=(h~1,…,h~λ)∈{0,1}λis the binary representation ofh~.(b)
Ifσ~>ssm1output⊥and abort; otherwise, continue.(c)
Computeh~r~=HAs(h~)(h~,r~1).(d)
IfAs(h~)σ~=h~r~then outputu~; otherwise, output⊥.


### 4.3.  Consistency and Unsigncryption Error

Theorem 19 (consistency).
The above signcryption scheme can unsigncrypt correctly with1-2-Ω(n)probability.Proof.
We analyze the procedure along the unsigncryption algorithm, when a valid ciphertextcp=(μ,b,c)is input to the unsigncryption.
Firstly, we demonstrate that the correctσ1can be obtained with overwhelming probability in step (1) of unsigncryption.(i)
Firstly, let us prove that after calling(z~,e~)←Invert𝒪(Tr,Ar(μ),b,ħ(μ)), the probability ofe~=eis overwhelming, whereeis the vector used in Signcrypt algorithm. At first, we need to show that this calling can work; that is,Tris aG-trapdoor forAr(μ). For convenience, letRI=[TrI]. BecauseQis a basis ofΛ(Gt), there must exist a matrixQ′∈ℤqn×nksuch thatQ=GtQ′. As a result,
(14)b^tmodq=btRI=(2(stAr(μ)modq)+et+(0,σ′))RI=(2(st[Ar(0)∥-Ar(0)Ts+ħ(μ)G]modq)+(e0,e1)t+(0,(Qσ1)t)(st[Ar(0)∥-Ar(0)Ts+ħ(μ)G]modq))RI=2(stħ(μ)Gmodq)+(e0tTs+e1t)+(GtQ′σ1)t=(2st+σ1tQ′ħ(μ)-1)ħ(μ)G+(e0tTr+e1t).Clearly, theb^tis the form ofgG(s^,e^)for some(s^,e^); namely,Tris aG-trapdoor forAr(μ). As a result, a vectore~∈ℤmcan be returned. We next demonstrate the probability that the probability fore~=eis overwhelming by callingInvert𝒪(Algorithm 2). Clearly, if the𝒪(b^)inInvert𝒪can return desired value,Invert𝒪can obtain desirede. The oracle𝒪(b^)is realized by calling InvertG (Algorithm 1); consequently, it only needs to prove the constraint condition is satisfied, that is, the error vectore0tTr+e1t∈𝒫1/2(q·Sk~-t), referring to Section 2.3 for the definition ofSk. Becausee0~Dℤ,αqm0,e1~Dℤ,srnkforsr=∥e0∥2+m0(αq)2·ω(logn), it follows that∥e0∥<αqm0and∥e1∥<αq2m0nkω(logn)except with probability2-Ω(n)by Proposition 9 items (2). When the parameters are set as in Setup and the sender’s public/private keys are produced as in KeyGen, it follows that the maximum singular value forTrsatisfiess1(Tr)≤O(nk)·ω(logn)except probability2-Ω(n)according to Proposition 10. Lete=(e0,e1); it follows that∥etRI∥≤∥e0tTr∥+∥e1t∥<αq·O(nk)·ω(logn)<O(q)∈𝒫1/2(q·Sk~-t)except probability2-Ω(n), because1/α=O(nk)·ω(logn)is large enough.
(ii)
Secondly, when the correcteis obtained, the test in step (c) can be passed and the analysis is included in the above proof.(iii)
Thirdly, in step (e), forv=(v0,v1)=b-emod2q, it follows thatv0∈2Λ(A0t)as desired.(iv)
Finally, in step (f),vtRI=2(stħ(μ)Gmodq)+(Qσ1)tmod2q; as a result,vtRIand(Qσ1)tare in the identical coset, so the decryption can obtainσ1exactly.
Next, after obtaining correctσ1andbvia step (1), we get the correct key used for symmetrical encryption, so we can obtain correct(μ,σ2,r1,r2)in step (2), and the verification for hash values in step (3) can be passed.
Finally, let us analyze step (4). Specifically, we prove that the signature verification can be passed with overwhelming probability. By now, we have got correct(σ,r1)that is a signature foru, and we only need to prove that it is valid. First, we evaluate the probability forσ≤ssm1.σ=[σory], whereσoris obtained by calling the algorithm SampleDG. It is known by SampleDG thatAs(0)σor=y′and∥σor∥≤ssmwith probability1-2-Ω(n)by Proposition 9 items (2). On the other hand,y≤ssnkwith probability1-2-Ω(n)by the same lemma. Therefore,σ≤ssm1with probability1-2-Ω(n). Second,
(15)As(h)σ=[As∥A′][σory]=y′+A′y=hr=HAs(h)(H0(u,Ar),r).
Consequently, the signature is valid with probability1-2-Ω(n).


## 4.1. Building Block: Lattice-Based Chameleon Hash Functions

According to [33, 34], we know that by using a chameleon hash function, one can transfer an SUF-SMA secure signature scheme to an SUF-CMA secure one. To guarantee the consistency of the proposed scheme, we need to construct a chameleon hash function based on lattice-based trapdoors of given in [17]. In fact, it is a analogue to the scheme based on the trapdoors given in [29].Letn≥1,q≥2,m0=O(nlogq), andk=O(logq)be integers. Let integerl>0be message length. For matricesN(0)∈ℤqn×l,N(z)∈ℤqn×m0, andT~Dℤ,ω(logn)m0×nkand invertible matrixM∈ℤqn×nconstructN(1)=[N(z)∥N(y)]=[N(z)∥-N(z)T+MG]∈ℤqn×mandN=[N(0)∥N(1)]. Letsbe a Gaussian parameter satisfyings≈5s1(T)ω(logn)suggested by [17]. Define a message spaceℳ={0,1}land random spaceℛ=Dℤm,s(then, forr∈ℛ,∥r∥≤smholds with overwhelming probability according to Proposition 9 items (2)) and𝒴∈𝕫qn. Foru∈ℳandr∈ℛ, using matrixNdefine hash functionHN:ℳ×ℛ→𝒴as
(10)HN(u,r)=N(0)u+N(1)r.Lemma 17.
The familyℋ={HN}(under the uniform distribution overℋ) is a family of chameleon hash functions, assuming the hardness ofSISq,βforβ2=l+4s2m.Proof.
It is enough to prove the hash familyℋ={HN}has the four properties described in Section 2.2.
For efficient forward computation. Clearly, given a messageu∈ℳandr∈ℛ, eachHN(u,r)is efficiently computable.
For collision-resistance property. Assuming that it is easy to find a collision[u∥r]≠[u′∥r′]∈ℳ×ℛforHN, thenx=[u-u′∥r-r′]≠0is a solution forNx=0, and according to the triangle inequality, we have that∥x∥2≤l+4s2m. It implies thatxis also a solution for the instanceNofSISq,β. This contradicts the hardness ofSISq,βforβ=l+4s2m. Therefore, the hash family is collision-resistant.
For uniformity property, we first show the matrixNis uniform. The matrixN(z)is uniform, soN(z)Tis also uniform whenT~Dℤ,ω(logn)m0×nkisnegl(n)-far from uniform (cf. Section 6.2 of [17]). On the other hand, the matrixMGis fixed whenMis fixed. Consequently, the matrixN(1)isnegl(n)-far from uniform. On the other hand,N(0)is uniform; henceNisnegl(n)-far from uniform. It is clear that given anym∈ℳandr←Dℤm,sand each matrixNgenerated as above, the distribution ofHN(m,r)is negligible far from the uniform distribution overℋ×𝒴by Proposition 9 items (1).
For chameleon property. Givenu,u′∈ℳandr∈ℛ, one withG-trapdoorTcan easily findr′∈ℛsatisfyingHN(u,r)=HN(u′,r′)as follows: computey=HN(u,r)-N(0)u′, and then sample preimager′=SampleDG(T,N(z),M,y,s).Lemma 18.
The above chameleon hash family is universal; for every distinctu,u′∈ℳand distinctr,r′∈ℛ,PrHN←ℋ[HN(u,r)=HN(u′,r′)]=q-n.Proof.
Assuming thatHN(u,r)=HN(u′,r′), it follows thatN(1)r′=HN(u,r)-N(0)u′. Whenu,r,u′is fixed, the vectorz=HN(u,r)-N(0)u′is a fixed element inℤqn.
The matrixN(1)is uniform as described above. Form0=O(nlogq),m=m0+nk≥2nlogq, the columns ofN(1)∈ℤqn×mgenerateℤqnwith overwhelming probability by Proposition 8. In addition,s≥∥S~∥ω(logn)andr′~Dℤm,s, whereSis as in Section 2.3.
It follows thatN(1)r′is uniform overℤqn(up to negligible statistical distance) by Proposition 9 items (1). Consequently,Pr[N(1)r′=z]=q-n. In other words,PrHN←ℋ[HN(u,r)=HN(u′,r′)]=q-n.


## 4.2.  Signcryption Scheme

In [17], Micciancio and Peikert gave a special collector (MP collector) that maps elements from a certain ringℜinto matricesH∈ℤqn×nas required by their trapdoor construction. Let us call it MP Collector and denote it byħ:ℜ→ℤqn×n. Given a monic degree-nirreducible polynomialf(x)=xn+fn-1xn-1+⋯+f0∈ℤ[x], a ring can be defined asℜ=ℤ[x]/(f(x))and the elements ofℜcan be represented as vectors inℤnrelative to the standard basis of monomials1,x,…,xn-1. Now, given a ring elementa(x)=a0+a1x+⋯+an-1xn-1∈ℜ,ħ(a)can be constructed as follows:
(11)h(0)=(a0,a1,…,an-1),h(i)=(0,h0(i-1),…,hn-2(i-1))-hn-2(i-1)(f0,f1,…,fn-1),
for0≤i<n, whereh(i)is theith column ofħ(a). Clearly,ħhas the following properties. Firstly,ħis a ring homomorphism, namely,ħ(x1)-ħ(x2)=ħ(x1-x2)forx1,x2∈ℜ. Secondly, multiplication by a ring elementa∈ℜcan be represented by the matrixħ(a); furthermore, the product coefficients vector equals∑i=0n-1‍biha(i), whereha(i)is theith column ofħ(a)andbiis theith coefficient of ring element. Thirdly,ħ(x)∈GLn(q)if and only ifxis a unit ofℜ, whereGLn(q)is a group composed of the invertible elements inℤqn×n. Finally, the ringℜhas “units difference” property, namely, for anyxi,xj∈ℜ*(ℜ*denotes the units set inℜ),xi-xj∈ℜ*.Our signcryption scheme consists of the following four algorithms. Note that we also adopt a symmetrical encryption schemeΠ=(𝒦,ℰ,𝒟)(with keyspace𝒦, encryption algorithmℰ,and decryption algorithm𝒟) in our construction.(i)
Setup(1n): Suppose the security parameter is1n. Then, the the public parameters𝒫pfor the system can be specified as follows.
(1)
G∈ℤqn×nkis the matrix as defined in Section 2.3, whereq=pe=poly(n)is a prime power and is large enough (cf. [17]).(2)
k=O(logq)=O(logn).(3)
m0=O(nk),m=m0+nk,m1=m0+2nk,and suitablel>0.(4)
α∈(0,1)is an LWE error rate, such that1/α=O(nk)·ω(logn).(5)
s′≥5·ω(logn).(6)
A monic degree-nirreducible polynomialf(x)=xn+fn-1xn-1+⋯+f0∈ℤp[x]and a ring defined asℜ=ℤq[x]/(f(x)).(7)
4 hash functions:
(a)
H0:{0,1}*×ℤqn×m→{0,1}λis a collision-resistant hash function, whereλ<n(p-1);(b)
H1:ℤqm1→{0,1}lis a universal hash function;(c)
HF:{0,1}l×ℤqm→ℜ*is chosen from a universal family, whereFis a matrix inℤqn×(l+m). More precisely,F=[F(0)∥F(1)]∈ℤqn×l×ℤqn×m, andF(0)(resp.,F(1)) has the same distribution withN(0)(resp.,N(1)) described in Section 4.1 (note that the elements inℜcan be represented by vectors inℤqn);(d)
H2:{0,1}nk×ℤ2qm→{0,1}n·k′is a universal hash function with suitably specifiedk′.(8)
An ordered matrix set𝔅={B(0),…,B(λ)}whereB(i)←$U(ℤqn×nk)for0≤i≤λ.(9)
ss=O(λnk)ω(logn)2is the Gaussian parameter for signature.(10)
An arbitary basisQ∈ℤnk×nkforΛ=Λ(Gt).(11)
MP Collectorħ:R→ℤqn×n.(ii)
KeyGen(1n,𝒫p): any user can generate his/her public keyPKand private keySKas follows.
(a)
SampleA(0)←$ℤqn×m0andT←$Dℤ,ω(logn)m0×nk;(b)
EvaluateA(1)=-A(0)T;(c)
LetPK≜A=[A(0)∥A(1)]∈ℤqn×mandSK≜T.(iii)
Signcrypt(u,Ar,As,Ts): a sender with public/private key pair(As,Ts)can send a signcryption ciphertextcon some messageuto a receiver with public keyAras follows.
(1)
Sign messageuto obtain(σ,r1), as follows.
(a)
Computeh=H0(u,Ar),A′=B(0)+∑i∈[λ]‍hiB(i)and then build
(12)As(h)=[As∥A′]∈ℤn×m1,whereh=(h1,…,hλ)∈{0,1}λis the binary representation ofh.(b)
Construct chameleon hash function according to the method in Section4.1. Concretely, replaceN(1),N(0),MwithAs, arbitrarylcolumns ofA′,I∈ℤqn×n, respectively. The others are invariant. The hash function is denoted asHAs(h).(c)
Sampler1←$Dℤnk,ss.(d)
Computehr=HAs(h)(h,r1).(e)
Sampley←$Dℤnk,ssand computey′=hr-A′y.(f)
Sampleσor←SampleDG(Ts,As(0),I,y′,ss), whereI∈ℤn×nis identity matrix.(g)
Letσ=(σor,y).(2)
Parseσ=(σ1,σ2)such thatσ1∈{0,1}nkand denote the remainder asσ2.(3)
Computew=H1(σ).(4)
Encryptσ1as follows.
(a)
Samplee0←$Dℤ,αqm0and evaluatesr=∥e0∥2+m0(αq)2·ω(logn).(b)
Samplee1←$Dℤ,srnk, and lete=(e0,e1).(c)
Sampler2←$Dℤnk,s′, then computeμ=HF(w,r2),and constructAr(μ)=[Ar(0)∥Ar(1)+ħ(μ)G].(d)
Encodeσ1asσ1′=encode(σ1)=Qσ1∈ℤnk.(e)
Choose a vectors←$ℤqnuniformly and let
(13)bt=2(stAr(μ)modq)+et+(0,σ1′)tmod2q.(5)
Encryptuas follows.
(a)
Letk′=H2(σ1,b)∈𝒦.(b)
Letc=ℰk′(u∣σ2∣r1∣r2).(6)
Output the signcryption ciphertext(μ,b,c).(iv)
Unsigncrypt(C,Ar,Tr,As): upon receiving a signcryption ciphertext(μ,b,c)from a sender with the public keyAs, the receiver with the private keyTrperforms the following steps.
(1)
Decrypt(μ,b)to achieveσ1as follows.
(a)
Ifμ=0, output⊥and then abort; otherwise continue.(b)
CallInvert𝒪(Tr,Ar(μ),b,ħ(μ))to obtain(z~,e~), wherez~∈ℤqnande~=(e~0,e~1)∈ℤm0×ℤnk.(c)
If∥e~0∥≥αqm0or∥e~1∥≥αq2m0nk·ω(logn)output⊥and abort; otherwise continue.(d)
Letv=b-e~mod2qand then parsevas(v1,v2)∈ℤ2qm0×ℤ2qnk.(e)
Ifv1∉2Λ((Ar0)t), output⊥and abort; otherwise, continue.(f)
Letσ~1=Q-1(vt[TrI]mod2q).(2)
Decryptcas follows.
(a)
Computek′=H2(σ~1,b)∈𝒦.(b)
Computeu~|σ~2|r~1|r~2=𝒟k′(c).(3)
Check the integrity of ciphertext as follows.
(a)
Obtainσ~by composingσ~1,σ~2, and then computew~=H1(σ~).(b)
Ifμ≠HF(w~,r~2)output⊥and abort; otherwise, continue.(c)
If∥r~2∥≥s′moutput⊥and abort; otherwise, continue.(4)
Verifying the sender’s authenticity as follows.
(a)
Computeh~=H0(u~,Ar)and then buildAs(h~)=[As∥B(0)+∑i∈[λ]‍h~iB(i)], whereh~=(h~1,…,h~λ)∈{0,1}λis the binary representation ofh~.(b)
Ifσ~>ssm1output⊥and abort; otherwise, continue.(c)
Computeh~r~=HAs(h~)(h~,r~1).(d)
IfAs(h~)σ~=h~r~then outputu~; otherwise, output⊥.


## 4.3.  Consistency and Unsigncryption Error

Theorem 19 (consistency).
The above signcryption scheme can unsigncrypt correctly with1-2-Ω(n)probability.Proof.
We analyze the procedure along the unsigncryption algorithm, when a valid ciphertextcp=(μ,b,c)is input to the unsigncryption.
Firstly, we demonstrate that the correctσ1can be obtained with overwhelming probability in step (1) of unsigncryption.(i)
Firstly, let us prove that after calling(z~,e~)←Invert𝒪(Tr,Ar(μ),b,ħ(μ)), the probability ofe~=eis overwhelming, whereeis the vector used in Signcrypt algorithm. At first, we need to show that this calling can work; that is,Tris aG-trapdoor forAr(μ). For convenience, letRI=[TrI]. BecauseQis a basis ofΛ(Gt), there must exist a matrixQ′∈ℤqn×nksuch thatQ=GtQ′. As a result,
(14)b^tmodq=btRI=(2(stAr(μ)modq)+et+(0,σ′))RI=(2(st[Ar(0)∥-Ar(0)Ts+ħ(μ)G]modq)+(e0,e1)t+(0,(Qσ1)t)(st[Ar(0)∥-Ar(0)Ts+ħ(μ)G]modq))RI=2(stħ(μ)Gmodq)+(e0tTs+e1t)+(GtQ′σ1)t=(2st+σ1tQ′ħ(μ)-1)ħ(μ)G+(e0tTr+e1t).Clearly, theb^tis the form ofgG(s^,e^)for some(s^,e^); namely,Tris aG-trapdoor forAr(μ). As a result, a vectore~∈ℤmcan be returned. We next demonstrate the probability that the probability fore~=eis overwhelming by callingInvert𝒪(Algorithm 2). Clearly, if the𝒪(b^)inInvert𝒪can return desired value,Invert𝒪can obtain desirede. The oracle𝒪(b^)is realized by calling InvertG (Algorithm 1); consequently, it only needs to prove the constraint condition is satisfied, that is, the error vectore0tTr+e1t∈𝒫1/2(q·Sk~-t), referring to Section 2.3 for the definition ofSk. Becausee0~Dℤ,αqm0,e1~Dℤ,srnkforsr=∥e0∥2+m0(αq)2·ω(logn), it follows that∥e0∥<αqm0and∥e1∥<αq2m0nkω(logn)except with probability2-Ω(n)by Proposition 9 items (2). When the parameters are set as in Setup and the sender’s public/private keys are produced as in KeyGen, it follows that the maximum singular value forTrsatisfiess1(Tr)≤O(nk)·ω(logn)except probability2-Ω(n)according to Proposition 10. Lete=(e0,e1); it follows that∥etRI∥≤∥e0tTr∥+∥e1t∥<αq·O(nk)·ω(logn)<O(q)∈𝒫1/2(q·Sk~-t)except probability2-Ω(n), because1/α=O(nk)·ω(logn)is large enough.
(ii)
Secondly, when the correcteis obtained, the test in step (c) can be passed and the analysis is included in the above proof.(iii)
Thirdly, in step (e), forv=(v0,v1)=b-emod2q, it follows thatv0∈2Λ(A0t)as desired.(iv)
Finally, in step (f),vtRI=2(stħ(μ)Gmodq)+(Qσ1)tmod2q; as a result,vtRIand(Qσ1)tare in the identical coset, so the decryption can obtainσ1exactly.
Next, after obtaining correctσ1andbvia step (1), we get the correct key used for symmetrical encryption, so we can obtain correct(μ,σ2,r1,r2)in step (2), and the verification for hash values in step (3) can be passed.
Finally, let us analyze step (4). Specifically, we prove that the signature verification can be passed with overwhelming probability. By now, we have got correct(σ,r1)that is a signature foru, and we only need to prove that it is valid. First, we evaluate the probability forσ≤ssm1.σ=[σory], whereσoris obtained by calling the algorithm SampleDG. It is known by SampleDG thatAs(0)σor=y′and∥σor∥≤ssmwith probability1-2-Ω(n)by Proposition 9 items (2). On the other hand,y≤ssnkwith probability1-2-Ω(n)by the same lemma. Therefore,σ≤ssm1with probability1-2-Ω(n). Second,
(15)As(h)σ=[As∥A′][σory]=y′+A′y=hr=HAs(h)(H0(u,Ar),r).
Consequently, the signature is valid with probability1-2-Ω(n).


## 5. Security Proofs

Before giving the proofs on the confidentiality and unforgeability of the proposed scheme, we need at first to prove the following lemma.Lemma 20.
For a given unitμ*∈ℜ=ℤq[x]/(f(x)), ifu←${0,1}*,r2←$Dℤm,s′, and(σ,r1)is a signature obtained in step (1) of the Signcrypt algorithm, then the probability forHF(H1(σ),r2)=μ*is negligible. More precisely,Pr[HF(H1(σ),r2)=μ*∣u←${0,1}*]=Ω(q-n).Proof.
We first evaluate the number of units in the above ringℜ. As defined in [17], the monic degree-npolynomialf(x)=xn+fn-1xn-1+⋯+f0∈ℤ[x]is irreducible modulo every primepdividingq. Becausef(x)is irreducible,(f(x))is maximum ideal andℤp[x]/(f(x))is a field according to Chinese remainder theorem. An elementa∈ℜis a unit if and only if it is nonzero modulo any primepdividingq. Assume thatqhas prime factorsp1,p2,…,pt. The amount of elements which are zero modulo prime factorpiisq/pi+1. By inclusion-exclusion principle, the amount of units inℜis
(16)qn-[(qp1+1)n+(qp2+1)n+⋯+(qpt+1)n]+[(q(p1p2)+1)n+(q(p1p3)+1)n+⋯+(q(pt-1pt)+1)n]+⋯+(-1)t(q(p1p2⋯pt)+1)n(17)≈qn-[(qp1)n+(qp2)n+⋯+(qpt)n]+[(q(p1p2))n+(q(p1p3))n+⋯+(q(pt-1pt))n]+⋯+(-1)t(q(p1p2⋯pt))n(18)=qn-[qnp1n+qnp2n+⋯+qnptn]+[qn((p1np2n))+qn((p1np3n))+⋯+qn((pt-1nptn))]+⋯+(-1)tqn(p1np2n⋯ptn)=qn(1-1p1n)(1-1p2n)⋯(1-1ptn)=O(qn),
where the approximating from (17) to (18) is implied by thatqis large enough. In the proposed scheme,q=peandqn-(q/p+1)n≈qn-(q/p)n=qn(1-1/pn). On the other hand, the hash functionsH1andHFare both universal. Based on the above two reasons, this lemma holds.Theorem 21 (confidentiality).
The proposed signcryption is indistinguishable against inner adaptively chosen ciphertext attack (IND-CCA2) assuming the decision-LWEq,α′problem (forα′=α/3≥2n/q) is intractable.Proof.
At first, let us define the following game sequence between a challenger𝒞and an adversary𝒜.(i)
The gameG0is exactly the IND-CCA2 attack with the system as described in Section 3.(ii)
In gameG1, the challenger change the way to construct the receiver’s public keyArand the way to answer unsigncryption queries. The receiver’s public keyAris produced as follows. At the start of the game, chooseAr(0),Tras in gameG0and letT=Tr, next chooseμ0←ℜ, and then constructAr=[Ar(0)∥-Ar(0)T-ħ(μ0)G]. The challenger gives the adversaryAras the sender’s public key. Whenever𝒜invokes a unsigncryption query on(c′,As,Ts)=((μ,b,c),As,Ts),𝒞responds as normal except that in step (1) of Unsigncrypt algorithm, the decryption for(μ,b)is changed as follows.
(1)
Decrypt(μ,b)to achieveσ1as follows.
(a′)
Ifμ=0orμ=μ0, output⊥and then abort; otherwise continue.(b′)
CallInvert𝒪(Tr,Ar(μ),b,ħ(μ-μ0))to obtain(z~,e~), wherez~∈ℤqnande~=(e~0,e~1)∈ℤm0×ℤnk.(c)
If∥e~0∥≥αqm0or∥e~1∥≥αq2m0nk·ω(logn)output⊥and abort; otherwise continue.(d)
Letv=b-e~mod2qand then parsevas(v1,v2)∈ℤ2qm0×ℤ2qnk.(e)
Ifv1∉2Λ((Ar0)t), output⊥and abort; otherwise, continue.(f′)
Letσ~1=Q-1(vt[T^I]mod2q)whereT^is an arbitrary solution ofAr(0)T^=A0T-ħ(μ0)G.(ii)
In gameG2, the challenger only changes hash functionHFand the method to produce challenge ciphertext(μ*,b*,c*)as follows. The change for hash functionHFis as follows. The challenger replaces the hash functionHFwith a chameleon hash functionHEwithout revealing the trapdoor, where the matrixE=[E(0)∥E(1)]∈ℤqn×l×ℤqn×mandE(0)(resp.,E(1)) has the same distribution withF(0)(resp.,F(1)). The challenge ciphertext is produced as follows. The adversary provides two equal length messagesu0,u1and the sender’s public/private keysAs*,Ts*. The challenger tosses a fair coinrc∈{0,1}, and then signcryptsurcwith a slightly change. The challenger signsurcnormally to obtain(σ,r1), next choosesμ*=μ0, and then choosesr2such thatμ*=HE(H1(σ),r2)(𝒞can do this since he/she knows the trapdoor of the chameleon hashHE). The subsequent signcryption operation is the same asG1.(iii)
In gameG3, the challenger continues to change the how the challenge ciphertext(μ*,b*,c*)is created. Concretely, only the way to produceb*is changed as follows. The challenger normally choosess←$ℤqn,e0←Dℤm0,αqand letb0t=2(stAr(0)modq)+e0tmod2q. Next, choosee^←$Dℤnk,αqmω(logn)and letb1t=-b0tTr+e^t+(Qσ1)tmod2q. Let(b*)t=(b0t,b1t). All the others are same as in gameG2.(iv)
In gameG4, the challenger continues to change the challenge ciphertext. The challenger choosesb0←$ℤ2qm0uniformly. All the others are identical toG3.
Then, this theorem is implied by the indistinguishability between two successive gamesGiandGi+1(i=0,1,2,3) that are presented in Lemmas 22, 23, 24, and 25, respectively.Lemma 22.
The adversary’s views in gameG0and gameG1are statistically indistinguishable. Meanwhile,G1can unsigncrypt correctly (with overwhelming probability).Proof.
We first prove the indistinguishability for public key. Givenμ0∈ℜ*,F(μ0)∈GLn(q)is a fixed matrix. On the other hand,Ar(0)Trisnegl(n)-uniform by leftover hash lemma. Therefore,Ar(0)Tr-ħ(μ0)Gisnegl(n)-uniform. Consequently, the value ofμ0is statistically hidden from the adversary and the distribution of public key inG0andG1is statistically indistinguishable.
Next, we illustrate the challenger𝒞in the gameG1can unsigncrypt correctly and𝒞’s unsigncryption behavior inG0andG1is indistinguishable from the view of the adversary𝒜. When the ciphertext queried is not valid, both games will abort. Therefore, we only need to analyze the case for a valid ciphertext. In the unsigncryption process of gameG1, only the decryption forμ,b(i.e., public key decryption process) is changed. Therefore, it is enough to prove the correctness of public key decryption. At first, ifμ=0, both games will output⊥. Otherwise, there are two cases forμ:μ≠μ0or not.
We firstly analyze the former. In this case, both games callInvert𝒪to obtain(z,e)such thatbt=ztAr(μ)+etmodq(refer to Section 4.3). In gameG1,
(19)Ar(μ)=[Ar(0)∥-Ar(0)T-ħ(μ0)G+ħ(μ)G]=[Ar(0)∥-Ar(0)T+ħ(μ-μ0)G].
Clearly, conditioned onμ≠μ0,ħ(μ-μ0)∈ℤqn×nis invertible according to the “unit differences” onℜ, which is necessary for callingInvert𝒪. It also follows thatTis theG-trapdoor forAr(μ)corresponding to invertible tagħ(μ-μ0). Therefore, the challenger needs to replaceMI=ħ(μ)withMI=ħ(μ-μ0)when callingInvert𝒪. In step (c), if there iseobtained from step (b′) that satisfies the constraint condition, it follows thatet[TI]∈𝒫1/2(q·Sk-t)in both games, whereSkhas been defined in Section 2.3. Therefore, thisecan be obtained by callingInvert𝒪in both games; otherwise, if there is no such ane, both games will output⊥. In step (e), ifv1∉2Λ((Ar(0))t), both games output⊥; otherwise, there exists∈Zqnandσ1′∈ℤ2qnksuch that
(20)vt=bt-et=2(stAr(μ)modq)+(0,σ1′)tmod2q.
In step (f) of gameG0,𝒞computes
(21)Q-1(vt[TI]mod2q)=Q-1(2(stħ(μ)Gmodq)+σ1′tmod2q),
while in step (f′) of gameG1,𝒞does as follows: first, find anyT^such thatAr(0)T^=-Ar(0)T-ħ(μ0)G, and then, compute
(22)Q-1(vt[T^I]mod2q)=Q-1(2(stħ(μ)Gmodq)+σ1′tmod2q).
Clearly,vt[TrI]inG0,vt[T^I]inG1,andσ1′tare in the same cosetΛ(Gt)/2Λ(Gt);thereforeG0andG1can both decrypt the desired value.
We next discuss the latter case; that is,μ=μ0. In this case, gameG1cannot unsigncrypt becauseħ(μ-μ0)is not invertible, but sinceμ0is unknown to the adversary inG1, the probability forμ=μ0is negligible according to Lemma 20. Based on the above analysis, the gamesG0andG1are indistinguishable.Lemma 23.
The adversary’s views in gameG2and gameG1are statistically indistinguishable.Proof.
At first, because the matrices used for constructing hash functionsHEandHFhave identical distribution, the gamesG2andG1are statistically indistinguishable when the hash function is replaced. Although the way for producing the challenge ciphertext(μ*,b*,c*)inG2is changed, the adversary cannot distinguishμ*=μ0fromμ*=HE(w,r2)without knowingμ0,w,r2in advance, considering thatHEis universal andμ0is random selected.Lemma 24.
The adversary’s views in gameG3and gameG2are statistically indistinguishable.Proof.
The key idea of this lemma’s proof is similar to a section in Theorem 6.3 of [17]. The change of challenge ciphertext inG3is only at the public encryption section, more precisely, only the componentb=(b0,b1)∈ℤ2qm0×ℤ2qnkas described above. The distribution ofb0in both games is identical. With respect tob1, in gameG2,
(23)b1t=2(-stAr(0)Trmodq)+e1t+(Qσ1)tmod2q,
wheree1~Dℤm0,s, fors=∥e0∥2+m0(αq)2ω(logn). In gameG3,
(24)b1t=-b0tTr+e^t+(Qσ1)tmod2q=2(-stAr(0)Trmodq)+(e0tTr+e^t)+(Qσ1)tmod2q.
It only needs to prove that the statistical distance betweene0tTr+e^tande1tis negligible. ExpressTras(t1,t2,…,tnk)∈ℤm0×nk, whereti~Dℤnk,ω(logn). On the other hande^~Dℤ,αqmω(logn). It follows that for fixede0,〈e0,ti〉+e^iisnegl(n)-far fromDℤ,s1fors12=(∥e0∥2+m0(αq)2)ω(logn)2according to Corollary 3.10 of [23] and Theorem 3.1 of [28]. In other words,b1inG3has distributionnegl(n)-far fromb1inG2. Consequently, the challenge ciphertext(μ*,b*,c*)in both gamesG3andG2is statistically indistinguishable.Lemma 25.
The adversary’s views in gameG4and gameG3are computationally indistinguishable and the adversary’s advantage inG4is negligible, assuming that the decision-LWEq,α′problem (forα′=α/3≥2n/q) is intractable.Proof.
The idea of this lemma’s proof is similar to a section in Theorem 6.3 of [17]. In order to show the indistinguishability, a method to discretize LWE is needed. Concretely,As,α′is a LWE instance overℤqn×𝕋. TheOssamples (fors∈ℤqn)(α,b=〈s,α〉/q+emod1)can be transformed to(α,2〈s,α〉modq+e′mod2q)∈ℤqn×ℤ2qby mappingb↦2qb+Dℤ-2qb,s, fore′←Dℤ,αqands2=(αq)2-(2α′q)2≥4n≥ηϵ(ℤ)2according to Theorem 3.1 of [28]. Clearly, by the above mapping, the uniform instanceO$overℤqn×𝕋is mapped to the uniform distribution overℤqn×ℤ2q.
In gameG3,(Ar(0),b0)is in fact an instance ofOs. In gameG4,(Ar(0),b0)is an uniform random instanceO$overℤqn×m0×ℤ2qn. Because LWE is pseudorandom, the above discretized distribution is also pseudorandom under the constraint condition forα′=α/3≥2n/q. Therefore, under discretized LWE assumption, the gamesG4andG3are computationally indistinguishable.
Next, we analyze the adversary’s advantage in the gameG4. According to leftover hash lemma,(Ar(0),b0,A0Tr,b0Tr)isnegl(n)-uniform, when choosingTras inG4. Therefore, the challenge ciphertext has at mostnegl(n)-far distribution when encrypting any different messages. Consequently, the adversary’s advantage inG4is negligible.Theorem 26 (unforgeability).
In standard model, the proposed signcryption is strongly unforgeable against inner adaptively chosen message attacks (SUF-CMA) assuming thatSISq,βfor large enoughβ=O(λ(nk)3/2)·ω(logn)3is hard.Proof.
We prove it by contradiction. If an adversaryℱcan forge a signcryption in the proposed scheme, then the simulator can forge a signature of the above SUF-CMA signature scheme used in the proposed scheme.
Initial:𝒞gets public parameter𝒫pand his/her public/private keys(As*,Ts*)by running successively the algorithms Setup and KeyGen and then𝒞givesAs*and𝒫ptoℱ.
Singcrypt query: in this phase, the adversaryℱcan perform polynomially bounded signcryption queries as follows. Whenℱsubmits a message (uand a intended receiver’s public keyAr) for querying. (For convenience, we denote the intended receiver’s private key byTr).𝒞gets a signcryption value byc′←Signcrypt(u,Ar,As*,SKs*)and givesc′toℱ.
Forgery:ℱoutputs a receivers public/private keys(Ar*,Tr*)and a fresh ciphertextc*=(u,b,c)under the sender’s public keyAs*and the receiver’s private keyTr*. Becausec*is a valid ciphertext,𝒞does what follows.(1)
Decrypt(u,b)withTr*to obtainσ1.(2)
DecryptcwithH2(σ1,b)to obtain(u∣σ2∣r1∣r2).(3)
Combineσ1andσ2to obtainσ.
In the proposed scheme, we use the signature scheme of [17]. However the syndromeyin the signature scheme is replaced by a chameleon hash value of the messageuand some randomr. For convenience, the signature scheme involving a chameleon hash function is calledMPcsignature scheme. The signature scheme of [17] is SUF-SMA in the standard model assuming the hardness ofSISq,βfor large enoughβ=O(λ(nk)3/2)·ω(logn)3;therefore theMPcsignature scheme is SUF-CMA in the standard model according to [33, Lemma 2.3] or [34, Lemma 2.1].
Becausec*is a valid ciphertext,(σ,r1)is a validMPcsignature on messageu. Now, we have got a contradiction. Consequently, the proposed signcryption scheme is also SUF-CMA assuming the hardness ofSISq,βforβ=O(λ(nk)3/2)·ω(logn)3.


## 6. Performance Analysis and Simulations

This section compares the ciphertext length, computational cost, key size, and so forth in the proposed scheme with that in the normal signature-then-encryption diagram and the existing signcryption schemes based on lattice.The dimension of public keysA∈ℤqn×mneed to be declared firstly. Assuming that the security parameternis the same in LMK12 [14], WHW12 [15], and ours. In LMK12 [14] and WHW12 [15], the public/private keys for signature and encryption are all generated by the approach in [29], and the dimensionmmeetsm′=6nlogq. In our scheme, the trapdoor generation algorithm is the approach proposed in [17]. In order to meet the conditions: statistically close to uniform and computationally pseudorandom, let dimensionm=2nlogqfor public key inℤqn×m. For convenience, the moduloqis assumed to be same in the three schemes, although theqin our scheme might be smaller than that in LMK12 [14] and WHW12 [15]. It needs to be illustrated that the signature scheme used in ours is that proposed in [17]. The matrix used in it is inℤn×m1, wherem1=m+nkfork=logq.


### 6.1. Comparison with Signature-Then-Encryption Diagram

First, we compare on ciphertext length. When we send anl′-bit length message, the normal signature-then-encryption diagram uses [17] to sign, and the signature length is approximatelym1logqbits. It uses [17] to encrypt the plaintext, and the ciphertext length is
(25)⌈l′(nk)⌉[nlogq+mlog2q]≈2l′logq,
but this can only achieve CCA1 security. Aiming to achieve CCA2 security, a good candidate is to produce one time signature (OTS) for the ciphertext. For efficiency, it can achieve this target to sign for the hash value of ciphertext. The signature length of OTS is alsom1logq. In this way, the total sum of bits is about
(26)m1logq+⌈l′(nk)⌉(nlogq+mlogq)+m1logq≈6nlog2q+2l′logq.
In our scheme, the form of ciphertext is(μ,b,c). In a ciphertext,cis the ciphertext for(u∣σ2∣r1∣r2)with a symmetric encryption scheme whose plaintext and ciphertext are of equal length. The length forμ,b,σ2is (ablout)nlogq,mlog2q, andm1logq, respectively. In the following discussion, we assume that the bits need for representing a variable nearly equals to its min-entropy. Becauser1←$Dℤnk,ss(see Section 4.2), its min-entropy is aboutnkby Proposition 9 items (2). As a result, the length ofr1is aboutnkbits. In a similar way, the length ofr2is aboutnk. Consequently, the ciphertext length of our scheme is about
(27)l′+nlogq+mlog2q+(nlogq+m1logq-nk+nk+nk)≈5nlog2q+l′.
The ciphertext length of ours is shorter than that of the signature-then-encryption diagram. Furthermore, the longer the length of the plaintext is, the larger our advantage is.Second, we compare on the computational cost. We first compare on signcryption. The computational cost of the signature-then-encryption diagram mainly consists of the cost of signature and that of public key encryption. The cost of signature is two pre-image sampling by using Algorithm4. The public key encryption needs roughly⌈l′/(nk)⌉times. The main computational cost of our scheme consists of the following: the cost of signature, the cost of public key encryption, and the cost of symmetrical encryption. Because the cost of symmetrical encryption (resp., decryption) is much smaller than the public key encryption (resp., decryption) and signature (resp., verification for signature), it can be ignored. The cost of signature is also a preimage sampling by using Algorithm 4. The public key encryption is one time. Clearly, the computational cost of Signcrypt is far less than that of the signature-then-encryption diagram. With the growth of plaintext length, the advantage in the total computational cost of our Signcrypt becomes larger.Next, we compare onUnsigncrypt. Our public decryption and signature verification are both one time, while the signature-then-encryption diagram needs⌈l′/(nk)⌉times and two times, respectively. From the above analysis, the computational cost of Signcrypt and the ciphertext length are much lower those of than the signature-then-encryption diagram, in particular for long plaintext.


### 6.2.  Comparison with the Schemes of LMK12 [14] and WHW12 [15]

Due to employing simpler, tighter, and more efficient trapdoors, our scheme inherits some advantages from the technique suggested by [17]. Now, let us compare the ciphertext length, computational cost, public key size, private key size, security model and security, and so forth among our scheme and the existing lattice-based signcryption schemes such as LMK12 [14] and WHW12 [15].Firstly, we compare on ciphertext length. The ciphertext of WHW12 [15] is the form(b1,b2,…,bl0)wherel0is big enough (say,l0≥80) such that2-l0is negligible. The length ofbiism′logq=6nlog2qfori∈[l0]. Consequently, the total length of ciphertext isl′+6l0nlog2q. The ciphertext of LMK12 [14] is the form of(c,r,u). The length ofrcan be omitted since its length is much smaller than the length ofcoru. The length ofuism′logq=6nlog2qand the length ofcis equal to the length of plaintext. As a result, the ciphertext length of LMK12 [14] is aboutl′+6nlog2q. Our ciphertext length is alsol′+5nlog2q(see Section 6.1).Secondly, we compare the public parameter size. Since in WHW12 [15] scheme and our proposal, the public parameters include several matrices, while in LMK12 [14] scheme the public parameters just include some scales such asn,m′,andq, it is convenient to merely count the representation size for the involved matrices. The role of the parameterλin the proposed scheme is the same asl0in WHW12 [15], and we replace it withl0for convenience. Then, the public parameter sizes of WHW12 [15] and ours are2(l0-1)nm′logq=12(l0-1)n2log2qandl0nmlogq=2l0n2log2q, respectively, while the public parameter size of LMK12 [14] can be neglected. Thirdly, we compare the public/private keys size, that is, the bits number needed for representing the keys. The public key size of WHW12 [15] is2nm′logq=12n2log2q, and the private key size is2m′2logq=72n2log3q. The public key size of LMK12 [14] isnmlogq=6n2log2qand the private key size ism′2logq=36n2log3q. The public key size of ours isnmlogq=2n2log2q, and the private key size ism0nklogq=m0nlog2q=n2log3q, wherem0=nlogq(see Section 4.2).Finally, let us compare on computational cost. Without loss of generality, the cost of all hash calculation in WHW12 [15] and LMK12 [14] and general hashesH0,H1, andH2in our scheme are not considered. However, the hashes in our scheme with special structures, such asHFandHAs(h), are taken into account. In detail, our analysis is given below.(i)
First, we compare on the computational cost ofSigncrypt. In WHW12 [15], the signature cost is one time preimage sampling (PIS) with complexityΩ(n2log2q)[17]; in addition, the cost of its public key encryption isl0nm′=6l0n2logqmultiplication operations overℤq,6l0nlogqaddition operations overℤqplus(l0-1)m′=6(l0-1)nlogqdiscrete Gaussian samples (DGS); moreover, the cost of symmetric encryption istℰ. In LMK12 [14], the cost of its signature is also one time preimage sampling. However, his scheme used preimage obtained from signature as Gaussian error of public key encryption by utilizing the technique in [35] and need not discrete Gaussian sample. As a result, the cost of its public key encryption isnm′=6n2logqmultiplication operations overℤqand6nlogqaddition operations overℤq. In addition, his symmetric encryption realized by XOR operation and the corresponding cost can be neglected. In our scheme, the cost of the signature is one time preimage sampling by using Algorithm 4 with complexityO(nlogq)[17], and the cost of symmetric encryption istℰ. The cost of public key encryption is about8n2logq+n2log2qmultiplications overℤqplusl0/2·n2log2qadditions overℤqand7nlogqDGS.(ii)
Next, we compare on the computational cost ofUnsigncrypt. In the three schemes, all algorithms Unsigncrypt involve the multiplications overℤq, additions overℤq,and symmetric decryption operations. The unsigncryption cost of WHW12 [15] is72n2log2q+(l0+6)n2logqmultiplications overℤqplus6l0nlogqadditions overℤq. The unsigncryption cost of LMK12 [14] is72n2log2q+6n2logqmultiplications overℤqplus6nlogqadditions overℤq. The cost of our unsigncryption is about9n2logq+3n2log2qmultiplications overℤqandl0/2·n2log2qadditions overℤq. The symmetric decryption in WHW12 [15] and ours is unspecified and in LMK12 [14] is XOR operation. Although the involved symmetric decryption is apparently more expensive than the involved XOR operation in LMK12 [14] scheme, the experiments show that this cost is very small.To summarize, the above comparisons can be collected in Table2. An overview of this table can also be abstracted in Table 1.Table 2
Performance comparison with WHW12 [15] and LMK12 [14].
WHW12 [15]
LMK12 [14]
Ours
Cipher length in bits
l
′
+
6
l
0
n
log
2
q
l
′
+
6
n
log
2
q
l
′
+
5
n
log
2
q
public para. size in bits
12
(
l
0
-
1
)
n
2
log
2
q
0
l
0
n
2
log
2
q
public key size in bits
12
n
2
log
2
q
6
n
2
log
2
q
2
n
2
log
2
q
private key size in bits
72
n
2
log
3
q
36
n
2
log
3
q
n
2
log
3
q
Sigcry cost
DGS*
6
(
l
0
-
1
)
n
log
q
0
7
n
log
q
PIS†
1 PIS of [20]
1 PIS of [20]
1 PIS of [17]
×
ℤ
q
‡
6
l
0
n
2
log
q
6
n
2
log
q
8
n
2
l
o
g
q
+
n
2
log
2
q
+
ℤ
q
*
*
6
l
0
n
log
q
6
n
log
q
l
0
/
2
·
n
2
log
2
q
Unsc cost
×
ℤ
q
‡
72
n
2
log
2
q
+
(
l
0
+
6
)
n
2
log
q
72
n
2
log
2
q
+
6
n
2
log
q
9
n
2
log
q
+
3
n
2
log
2
q
+
ℤ
q
*
*
6
(
l
0
-
1
)
n
log
q
6
n
log
q
l
0
/
2
·
n
2
log
2
q
Security
Model
RO
RO
ST
Conf.***
IND-CCA2
IND-CCA2
IND-CCA2
UF.#
SUF-CMA
SUF-CMA
SUF-CMA
*Discrete Gaussian sampling, that is, SampleZ: zi←Dℤ,si′,ci′ in [20], †preimage sampling,  ‡multiplication over 𝕫q, **addition over 𝕫q, ***confidentiality, #unforgeability.


### 6.3. Simulations

Our simulation environments are given below:(i)
CPU: Intel(R) Core(TM) i7 860 @CPU 2.79 GHz;(ii)
RAM: 8 G;(iii)
OS: Win 7, 64 bit;(iv)
programming platform: Visual Studio 2008.We conduct 7 simulations with different parameter settings. These settings, given in Table3, are suggested from [21], [22], and [17], respectively. In particular, under the suggestion of [17], to break a related lattice-based cryptosystem, one needs about246core-year computation time by using the state-of-the-art in lattice basis reduction [36, 37] on a 64-bit 1.86 GHz Xeon platform. Note that with the purpose to achieve the same security level, the lattice dimensionsns are different by using different lattice generation techniques.Table 3
Parameter Settings.
Settings no.
1
2
3
4
5
6
7
LMK/WHW
n
128
136
192
214
256
320
436
q
2053
2003
4093
16381
4093
4093
232
m
8448
8976
13824
17976
18432
23040
466644
Ours
n
128
136
192
214
256
320
284
q
2048
2048
4096
16384
4096
4096
2
24
m
2816
2992
4608
5992
6144
7680
13812
Referred
[21]
[22]
[21]
[22]
[21]
[21]
[17]Then, for each setting, we perform random signcryption and unsigncryption 100 times and then collect the average time cost for signcryption and unsigncryption. The results are given in Table4 and illustrated in Figures 1 and 2. Note that in these figures, we adopt logarithmic coordinates with the purpose to give visible changes on those data that are different hugely.Table 4
Average signcryption/unsigncryption time (s).
Settings no.
1
2
3
4
5
6
7
LMK
Signcrypt
1.69
1.929
4.514
7.626
8.048
12.53
5434.248
Unsigncrypt
1.624
1.715
4.062
6.922
7.251
11.72
4515.09
WHW
Signcrypt
4.025
4.535
9.173
14.068
15.3
23.47
5688.381
Unsigncrypt
2.5635
2.813
6.756
10.431
12.0712
18.415
4695.269
Ours
Signcrypt
0.489
0.547
1.283
1.991
2.212
3.476
9.309
Unsigncrypt
0.454
0.522
1.257
2.175
2.229
3.48
10.954Figure 1
Average signcryption speed.Figure 2
Average unsigncryption speed.From Tables2, 4, 5, and 6 and Figures 1, 2, 3, 4, 5, and 6, we can see that our improvements are observably as follows.(i)
Under the settings 1~6, the average signcryption time of our scheme increases slowly from 0.489 s to 3.476 s, about 3 times and 5~13 times faster than Li’s scheme and Wang’s scheme, respectively. Under these settings, the average unsigncryption time of our scheme increases slowly from 0.454 s to 3.48 s, about 3 times and 260 times faster than Li’s scheme and Wang’s scheme, respectively.(ii)
Under the setting 7, the average signcryption time of our scheme is 9.309 s, about 580 times faster than Li’s scheme and Wang’s scheme. Under this setting, the average unsigncryption time of our scheme is 10.954 s, about 400 times and 33000 times faster than Li’ scheme and Wang’s scheme, respectively.Table 5
Average matrix computation cost in signcryption/unsigncryption (s).
Settings no.
1
2
3
4
5
6
7
Li
Signcrypt
0.012
0.014
0.03
0.044
0.053
0.09
2.248
Unsigncrypt
1.624
1.715
4.062
6.922
7.251
11.72
4515.09
Wang
Signcrypt
0.975
1.138
2.428
3.553
4.294
7.271
179.971
Unsigncrypt
2.5635
2.813
6.756
10.431
12.0712
18.415
4695.269
Ours
Signcrypt
0.316
0.356
0.857
1.307
1.504
2.384
7.506
Unsigncrypt
0.454
0.522
1.257
2.175
2.229
3.48
10.954Table 6
Average sampling cost in signcryption.
Settings no.
1
2
3
4
5
6
7
Li
PIS
1.678
1.915
4.484
7.582
7.995
12.44
5432
DGS
0
0
0
0
0
0
0
Wang
PIS
1.678
1.915
4.484
7.582
7.995
12.44
5432
DGS
1.372
1.482
2.261
2.933
3.011
3.759
76.41
Ours
PIS
0.155
0.171
0.399
0.659
0.67
1.045
1.748
DGS
0.018
0.02
0.027
0.025
0.038
0.047
0.055Figure 3
Average matrix computation cost in signcryption.Figure 4
Average matrix computation cost in unsigncryption.Figure 5
Average preimage sampling cost in signcryption.Figure 6
Average discrete gaussian sampling cost in signcryption (s).To understand the above huge difference on the performance of our scheme, Li’s scheme, and Wang’s scheme, we would like to give the following further explanations. The time cost of signcryption is mainly occupied by three categories of computation:(1)
matrix operations, including modular addition between matrices and modular multiplication among matrices and vectors,(2)
preimage sampling,(3)
discrete Gaussian sampling.First, in our signcryption process, the time cost of matrix operations is mainly occupied in step 4(d) and 1(a) (see Section4.2). Since step 1(a) is directly related to messages that are to be signcrypted, this is not an easy method to optimize this step; say by using precomputation. However, step 4(d) can be optimized since the matrixQhas nonzero entries merely in the main and the second diagonals. By utilizing this feature, we reduce the computation cost of step 4(d) fromn3log3qmultiplications to2nlogqmultiplications. The performance comparisons on average matrix computation cost in signcryption and unsigncryption are given in Table 5 and Figures 3 and 4, respectively. Second, both Li and Wang use the preimage sampling technique given in [20] and its complexity isΩ(n2log2q), while we use the preimage sampling technique given in [17], where the sample oracle is instantiated by the technique given in [28], and its complexity is reduced to𝒪(nlogq). Third, our signcryption process needs to perform5nlogqtimes Gaussian sampling, while Wang’s signcryption needs to perform in total6l0nlogqtimes Gaussian sampling, wherel0should enable2-l0to be negligible; sayl0≥80. Note that Li’s signcryption reuses preimages as Gaussian error vectors and thus does not need further Gaussian sampling. The performance comparisons on average sampling cost, including the cost for preimage sampling and the cost for discrete Gaussian sampling, are collected in Table 6 and depicted in Figures 5 and 6. Note that in unsigncryption process, there is no sampling cost.


## 6.1. Comparison with Signature-Then-Encryption Diagram

First, we compare on ciphertext length. When we send anl′-bit length message, the normal signature-then-encryption diagram uses [17] to sign, and the signature length is approximatelym1logqbits. It uses [17] to encrypt the plaintext, and the ciphertext length is
(25)⌈l′(nk)⌉[nlogq+mlog2q]≈2l′logq,
but this can only achieve CCA1 security. Aiming to achieve CCA2 security, a good candidate is to produce one time signature (OTS) for the ciphertext. For efficiency, it can achieve this target to sign for the hash value of ciphertext. The signature length of OTS is alsom1logq. In this way, the total sum of bits is about
(26)m1logq+⌈l′(nk)⌉(nlogq+mlogq)+m1logq≈6nlog2q+2l′logq.
In our scheme, the form of ciphertext is(μ,b,c). In a ciphertext,cis the ciphertext for(u∣σ2∣r1∣r2)with a symmetric encryption scheme whose plaintext and ciphertext are of equal length. The length forμ,b,σ2is (ablout)nlogq,mlog2q, andm1logq, respectively. In the following discussion, we assume that the bits need for representing a variable nearly equals to its min-entropy. Becauser1←$Dℤnk,ss(see Section 4.2), its min-entropy is aboutnkby Proposition 9 items (2). As a result, the length ofr1is aboutnkbits. In a similar way, the length ofr2is aboutnk. Consequently, the ciphertext length of our scheme is about
(27)l′+nlogq+mlog2q+(nlogq+m1logq-nk+nk+nk)≈5nlog2q+l′.
The ciphertext length of ours is shorter than that of the signature-then-encryption diagram. Furthermore, the longer the length of the plaintext is, the larger our advantage is.Second, we compare on the computational cost. We first compare on signcryption. The computational cost of the signature-then-encryption diagram mainly consists of the cost of signature and that of public key encryption. The cost of signature is two pre-image sampling by using Algorithm4. The public key encryption needs roughly⌈l′/(nk)⌉times. The main computational cost of our scheme consists of the following: the cost of signature, the cost of public key encryption, and the cost of symmetrical encryption. Because the cost of symmetrical encryption (resp., decryption) is much smaller than the public key encryption (resp., decryption) and signature (resp., verification for signature), it can be ignored. The cost of signature is also a preimage sampling by using Algorithm 4. The public key encryption is one time. Clearly, the computational cost of Signcrypt is far less than that of the signature-then-encryption diagram. With the growth of plaintext length, the advantage in the total computational cost of our Signcrypt becomes larger.Next, we compare onUnsigncrypt. Our public decryption and signature verification are both one time, while the signature-then-encryption diagram needs⌈l′/(nk)⌉times and two times, respectively. From the above analysis, the computational cost of Signcrypt and the ciphertext length are much lower those of than the signature-then-encryption diagram, in particular for long plaintext.


## 6.2.  Comparison with the Schemes of LMK12 [14] and WHW12 [15]

Due to employing simpler, tighter, and more efficient trapdoors, our scheme inherits some advantages from the technique suggested by [17]. Now, let us compare the ciphertext length, computational cost, public key size, private key size, security model and security, and so forth among our scheme and the existing lattice-based signcryption schemes such as LMK12 [14] and WHW12 [15].Firstly, we compare on ciphertext length. The ciphertext of WHW12 [15] is the form(b1,b2,…,bl0)wherel0is big enough (say,l0≥80) such that2-l0is negligible. The length ofbiism′logq=6nlog2qfori∈[l0]. Consequently, the total length of ciphertext isl′+6l0nlog2q. The ciphertext of LMK12 [14] is the form of(c,r,u). The length ofrcan be omitted since its length is much smaller than the length ofcoru. The length ofuism′logq=6nlog2qand the length ofcis equal to the length of plaintext. As a result, the ciphertext length of LMK12 [14] is aboutl′+6nlog2q. Our ciphertext length is alsol′+5nlog2q(see Section 6.1).Secondly, we compare the public parameter size. Since in WHW12 [15] scheme and our proposal, the public parameters include several matrices, while in LMK12 [14] scheme the public parameters just include some scales such asn,m′,andq, it is convenient to merely count the representation size for the involved matrices. The role of the parameterλin the proposed scheme is the same asl0in WHW12 [15], and we replace it withl0for convenience. Then, the public parameter sizes of WHW12 [15] and ours are2(l0-1)nm′logq=12(l0-1)n2log2qandl0nmlogq=2l0n2log2q, respectively, while the public parameter size of LMK12 [14] can be neglected. Thirdly, we compare the public/private keys size, that is, the bits number needed for representing the keys. The public key size of WHW12 [15] is2nm′logq=12n2log2q, and the private key size is2m′2logq=72n2log3q. The public key size of LMK12 [14] isnmlogq=6n2log2qand the private key size ism′2logq=36n2log3q. The public key size of ours isnmlogq=2n2log2q, and the private key size ism0nklogq=m0nlog2q=n2log3q, wherem0=nlogq(see Section 4.2).Finally, let us compare on computational cost. Without loss of generality, the cost of all hash calculation in WHW12 [15] and LMK12 [14] and general hashesH0,H1, andH2in our scheme are not considered. However, the hashes in our scheme with special structures, such asHFandHAs(h), are taken into account. In detail, our analysis is given below.(i)
First, we compare on the computational cost ofSigncrypt. In WHW12 [15], the signature cost is one time preimage sampling (PIS) with complexityΩ(n2log2q)[17]; in addition, the cost of its public key encryption isl0nm′=6l0n2logqmultiplication operations overℤq,6l0nlogqaddition operations overℤqplus(l0-1)m′=6(l0-1)nlogqdiscrete Gaussian samples (DGS); moreover, the cost of symmetric encryption istℰ. In LMK12 [14], the cost of its signature is also one time preimage sampling. However, his scheme used preimage obtained from signature as Gaussian error of public key encryption by utilizing the technique in [35] and need not discrete Gaussian sample. As a result, the cost of its public key encryption isnm′=6n2logqmultiplication operations overℤqand6nlogqaddition operations overℤq. In addition, his symmetric encryption realized by XOR operation and the corresponding cost can be neglected. In our scheme, the cost of the signature is one time preimage sampling by using Algorithm 4 with complexityO(nlogq)[17], and the cost of symmetric encryption istℰ. The cost of public key encryption is about8n2logq+n2log2qmultiplications overℤqplusl0/2·n2log2qadditions overℤqand7nlogqDGS.(ii)
Next, we compare on the computational cost ofUnsigncrypt. In the three schemes, all algorithms Unsigncrypt involve the multiplications overℤq, additions overℤq,and symmetric decryption operations. The unsigncryption cost of WHW12 [15] is72n2log2q+(l0+6)n2logqmultiplications overℤqplus6l0nlogqadditions overℤq. The unsigncryption cost of LMK12 [14] is72n2log2q+6n2logqmultiplications overℤqplus6nlogqadditions overℤq. The cost of our unsigncryption is about9n2logq+3n2log2qmultiplications overℤqandl0/2·n2log2qadditions overℤq. The symmetric decryption in WHW12 [15] and ours is unspecified and in LMK12 [14] is XOR operation. Although the involved symmetric decryption is apparently more expensive than the involved XOR operation in LMK12 [14] scheme, the experiments show that this cost is very small.To summarize, the above comparisons can be collected in Table2. An overview of this table can also be abstracted in Table 1.Table 2
Performance comparison with WHW12 [15] and LMK12 [14].
WHW12 [15]
LMK12 [14]
Ours
Cipher length in bits
l
′
+
6
l
0
n
log
2
q
l
′
+
6
n
log
2
q
l
′
+
5
n
log
2
q
public para. size in bits
12
(
l
0
-
1
)
n
2
log
2
q
0
l
0
n
2
log
2
q
public key size in bits
12
n
2
log
2
q
6
n
2
log
2
q
2
n
2
log
2
q
private key size in bits
72
n
2
log
3
q
36
n
2
log
3
q
n
2
log
3
q
Sigcry cost
DGS*
6
(
l
0
-
1
)
n
log
q
0
7
n
log
q
PIS†
1 PIS of [20]
1 PIS of [20]
1 PIS of [17]
×
ℤ
q
‡
6
l
0
n
2
log
q
6
n
2
log
q
8
n
2
l
o
g
q
+
n
2
log
2
q
+
ℤ
q
*
*
6
l
0
n
log
q
6
n
log
q
l
0
/
2
·
n
2
log
2
q
Unsc cost
×
ℤ
q
‡
72
n
2
log
2
q
+
(
l
0
+
6
)
n
2
log
q
72
n
2
log
2
q
+
6
n
2
log
q
9
n
2
log
q
+
3
n
2
log
2
q
+
ℤ
q
*
*
6
(
l
0
-
1
)
n
log
q
6
n
log
q
l
0
/
2
·
n
2
log
2
q
Security
Model
RO
RO
ST
Conf.***
IND-CCA2
IND-CCA2
IND-CCA2
UF.#
SUF-CMA
SUF-CMA
SUF-CMA
*Discrete Gaussian sampling, that is, SampleZ: zi←Dℤ,si′,ci′ in [20], †preimage sampling,  ‡multiplication over 𝕫q, **addition over 𝕫q, ***confidentiality, #unforgeability.


## 6.3. Simulations

Our simulation environments are given below:(i)
CPU: Intel(R) Core(TM) i7 860 @CPU 2.79 GHz;(ii)
RAM: 8 G;(iii)
OS: Win 7, 64 bit;(iv)
programming platform: Visual Studio 2008.We conduct 7 simulations with different parameter settings. These settings, given in Table3, are suggested from [21], [22], and [17], respectively. In particular, under the suggestion of [17], to break a related lattice-based cryptosystem, one needs about246core-year computation time by using the state-of-the-art in lattice basis reduction [36, 37] on a 64-bit 1.86 GHz Xeon platform. Note that with the purpose to achieve the same security level, the lattice dimensionsns are different by using different lattice generation techniques.Table 3
Parameter Settings.
Settings no.
1
2
3
4
5
6
7
LMK/WHW
n
128
136
192
214
256
320
436
q
2053
2003
4093
16381
4093
4093
232
m
8448
8976
13824
17976
18432
23040
466644
Ours
n
128
136
192
214
256
320
284
q
2048
2048
4096
16384
4096
4096
2
24
m
2816
2992
4608
5992
6144
7680
13812
Referred
[21]
[22]
[21]
[22]
[21]
[21]
[17]Then, for each setting, we perform random signcryption and unsigncryption 100 times and then collect the average time cost for signcryption and unsigncryption. The results are given in Table4 and illustrated in Figures 1 and 2. Note that in these figures, we adopt logarithmic coordinates with the purpose to give visible changes on those data that are different hugely.Table 4
Average signcryption/unsigncryption time (s).
Settings no.
1
2
3
4
5
6
7
LMK
Signcrypt
1.69
1.929
4.514
7.626
8.048
12.53
5434.248
Unsigncrypt
1.624
1.715
4.062
6.922
7.251
11.72
4515.09
WHW
Signcrypt
4.025
4.535
9.173
14.068
15.3
23.47
5688.381
Unsigncrypt
2.5635
2.813
6.756
10.431
12.0712
18.415
4695.269
Ours
Signcrypt
0.489
0.547
1.283
1.991
2.212
3.476
9.309
Unsigncrypt
0.454
0.522
1.257
2.175
2.229
3.48
10.954Figure 1
Average signcryption speed.Figure 2
Average unsigncryption speed.From Tables2, 4, 5, and 6 and Figures 1, 2, 3, 4, 5, and 6, we can see that our improvements are observably as follows.(i)
Under the settings 1~6, the average signcryption time of our scheme increases slowly from 0.489 s to 3.476 s, about 3 times and 5~13 times faster than Li’s scheme and Wang’s scheme, respectively. Under these settings, the average unsigncryption time of our scheme increases slowly from 0.454 s to 3.48 s, about 3 times and 260 times faster than Li’s scheme and Wang’s scheme, respectively.(ii)
Under the setting 7, the average signcryption time of our scheme is 9.309 s, about 580 times faster than Li’s scheme and Wang’s scheme. Under this setting, the average unsigncryption time of our scheme is 10.954 s, about 400 times and 33000 times faster than Li’ scheme and Wang’s scheme, respectively.Table 5
Average matrix computation cost in signcryption/unsigncryption (s).
Settings no.
1
2
3
4
5
6
7
Li
Signcrypt
0.012
0.014
0.03
0.044
0.053
0.09
2.248
Unsigncrypt
1.624
1.715
4.062
6.922
7.251
11.72
4515.09
Wang
Signcrypt
0.975
1.138
2.428
3.553
4.294
7.271
179.971
Unsigncrypt
2.5635
2.813
6.756
10.431
12.0712
18.415
4695.269
Ours
Signcrypt
0.316
0.356
0.857
1.307
1.504
2.384
7.506
Unsigncrypt
0.454
0.522
1.257
2.175
2.229
3.48
10.954Table 6
Average sampling cost in signcryption.
Settings no.
1
2
3
4
5
6
7
Li
PIS
1.678
1.915
4.484
7.582
7.995
12.44
5432
DGS
0
0
0
0
0
0
0
Wang
PIS
1.678
1.915
4.484
7.582
7.995
12.44
5432
DGS
1.372
1.482
2.261
2.933
3.011
3.759
76.41
Ours
PIS
0.155
0.171
0.399
0.659
0.67
1.045
1.748
DGS
0.018
0.02
0.027
0.025
0.038
0.047
0.055Figure 3
Average matrix computation cost in signcryption.Figure 4
Average matrix computation cost in unsigncryption.Figure 5
Average preimage sampling cost in signcryption.Figure 6
Average discrete gaussian sampling cost in signcryption (s).To understand the above huge difference on the performance of our scheme, Li’s scheme, and Wang’s scheme, we would like to give the following further explanations. The time cost of signcryption is mainly occupied by three categories of computation:(1)
matrix operations, including modular addition between matrices and modular multiplication among matrices and vectors,(2)
preimage sampling,(3)
discrete Gaussian sampling.First, in our signcryption process, the time cost of matrix operations is mainly occupied in step 4(d) and 1(a) (see Section4.2). Since step 1(a) is directly related to messages that are to be signcrypted, this is not an easy method to optimize this step; say by using precomputation. However, step 4(d) can be optimized since the matrixQhas nonzero entries merely in the main and the second diagonals. By utilizing this feature, we reduce the computation cost of step 4(d) fromn3log3qmultiplications to2nlogqmultiplications. The performance comparisons on average matrix computation cost in signcryption and unsigncryption are given in Table 5 and Figures 3 and 4, respectively. Second, both Li and Wang use the preimage sampling technique given in [20] and its complexity isΩ(n2log2q), while we use the preimage sampling technique given in [17], where the sample oracle is instantiated by the technique given in [28], and its complexity is reduced to𝒪(nlogq). Third, our signcryption process needs to perform5nlogqtimes Gaussian sampling, while Wang’s signcryption needs to perform in total6l0nlogqtimes Gaussian sampling, wherel0should enable2-l0to be negligible; sayl0≥80. Note that Li’s signcryption reuses preimages as Gaussian error vectors and thus does not need further Gaussian sampling. The performance comparisons on average sampling cost, including the cost for preimage sampling and the cost for discrete Gaussian sampling, are collected in Table 6 and depicted in Figures 5 and 6. Note that in unsigncryption process, there is no sampling cost.


## 7. Conclusions

In this paper, we proposed a signcryption scheme in the standard model based on lattice hard problems. The scheme is proven to be indistinguishable against inner adaptively chosen ciphertext attacks under LWE assumption and strongly unforgeable against inner adaptively chosen message attacks under SIS assumption. Moreover, by using simpler, tighter, and more efficient trapdoors suggested by Micciancico and Perkeit, the cost of our scheme is much lower than existing lattice-based signcryption schemes. Another attractive problem is designing an efficient identity-based signcryption scheme in the standard model.



---

*Source: 702539-2013-11-28.xml*