1 Introduction
In traditional public key settings (Rivest et al., 1978; ElGamal, 1985), a public key infrastructure (PKI) is required to manage users’ certificates, which are issued by a trusted certificate authority (CA) to offer the link relationships between users’ identities and the associated public keys. When a party would like to use the other party’s public key, she/he must first inquire and validate the certificate of the other party using the public key infrastructure. Typically, certificate management in such a public key infrastructure is pricey.
To simplify certificate management in traditional public key settings, Shamir (1984) presented the notion of identity (ID)-based public key settings while Boneh and Franklin (2001) realized the ID-based public key setting from the Weil pairing and presented the first ID-based encryption scheme. For the cryptographic schemes (Tseng et al., 2016; Tsai et al., 2017) under ID-based public key settings, a trusted private key generator (PKG) is responsible to generate private keys of all users, but such settings suffer from the key escrow problem. To solve the key escrow problem, Al-Riyami and Paterson (2003) proposed a new public key paradigm, namely, certificateless public key setting. Nevertheless, both ID-based and certificateless public key settings did not employ public key certificates so that both public key settings must offer extra revocation mechanisms to revoke compromised users from the public key settings. Fortunately, several studies (Tseng and Tsai, 2012; Tsai and Tseng, 2015; Hung et al., 2016b; Tseng et al., 2018; Wu et al., 2018) have well addressed the revocation problem of ID-based and certificateless public key settings.
The other solution resolving the key escrow problem in ID-based public key settings is the notion of certificate-based public key settings, which is presented by Gentry (2003). In the meantime, it also simplifies certificate management and the complexity of public key infrastructure, in traditional public key settings. In Gentry’s certificate-based public key setting, a user independently generates the associated private/public keys while sending the public key to a certificate authority (CA). By the user’s public key and identity information, the CA generates a certificate and sends it to the user. For the revocation problem, the CA may update non-revoked users’ certificates periodically without requiring extra revocation mechanisms. When a user would like to decrypt a ciphertext or sign a message, the user must own both private key and valid certificate. Numerous certificate-based cryptographic studies have been proposed, such as certificate-based encryption schemes (Galindo et al., 2008; Lu and Li, 2014; Gao et al., 2015) and certificate-based signature schemes (Li et al., 2007; Wu et al., 2009; Li et al., 2012; Hung et al., 2016a).
As we all know, the security of cryptographic mechanisms must be based on the difficulties or assumptions of some hard problem. Typically, most of the existing cryptographic schemes/protocols under aforementioned public key settings are mainly relied on the difficulties of the discrete logarithm and factorization problems with large prime numbers. Unfortunately, both problems will be resolved when quantum computers come true in the future. In such a case, those cryptographic schemes/protocols based on both hard problems would become insecure (Shor, 1997). Recently, researchers have constructed several new mathematical approaches to withstand quantum attacks. Lattice-based cryptography is one of the main candidates for post-quantum cryptography because of its efficiency and security (Bernstein, 2009).
1.1 Related Work
Under traditional public key settings, Goldreich et al. (1997) proposed the first signature and encryption schemes from lattices. Afterward, several lattice-based signature schemes (Gentry et al., 2008; Lyubashevsky, 2009, 2012) were proposed to enhance security and performance. Gentry et al. (2008) adopted the Gaussian sampling technique to generate a user’s private key while employing the hash-and-sign approach to sign a message. In such a case, the size of the resulting private key is too large while the computation cost of the signing process is inefficient. To improve the signing performance, Lyubashevsky (2009) employed the Fiat-Shamir transformation technique to generate signatures. Furthermore, Lyubashevsky (2012) proposed the other lattice-based signature scheme which uses the rejection sampling technique to sign a message while reducing the signature size.
By employing Gentry et al.’s private key generation method (Gentry et al., 2008), Ruckert (2010) presented two ID-based signature schemes from lattices. Both schemes were, respectively, proved to be secure in the random oracle model and the standard model. However, the sizes of private key and the resulting signature are still lengthy. To improve the security and performance, lattice-based IBS schemes (Liu et al., 2013; Tian and Huang, 2014) were proposed. For the revocation problem of ID-based public key settings, Xiang (2015) adopted the binary tree structure to construct a revocable ID-based signature scheme from lattices. In addition, by the revocation technique in Tseng and Tsai (2012), Tseng et al. (2018), Hung et al. (2017a) employed the NTRU lattices in Ducas et al. (2014) to shorten the private key and signature sizes.
Tian and Huang (2015) proposed the first lattice-based certificateless signature scheme. They also employed Gentry et al.’s method (Gentry et al., 2008) to generate users’ private keys so that the sizes of private key and the resulting signature turn out to be lengthy. Very recently, Hung et al. (2017b) employed the revocation technique of certificateless public key setting in Tsai and Tseng (2015), Hung et al. (2016b) to present the first lattice-based revocable certificateless signature scheme while improving the performance of Tain and Huang’s scheme.
In the past, there is little work on the design of certificate-based signature (CBS) scheme over lattices. Indeed, Tian and Huang (2015) also presented the first CBS scheme from lattices. The proposed scheme was proved to be existential unforgeability against adaptive chosen message attacks in the random oracle model. In addition, as Tain and Huang’s lattice-based certificateless signature scheme, their CBS scheme from lattices also employs the same method in Gentry et al. (2008) to generate private key. The form of a user’s private key generated in Gentry et al. (2008) consists of two matrices ${\mathbf{M}_{1}}\in {Z_{q}^{{n_{1}}\times k}}$ and ${\mathbf{M}_{2}}\in {Z_{q}^{{n_{2}}\times k}}$, where ${n_{1}},{n_{2}}>5k\log q$ and q is a prime number. Hence, in Tain and Huang’s CBS scheme, the size of the resulting signature is also lengthy. In such a case, their scheme is inefficient.
1.2 Contribution and Organization
In the paper, a new and efficient certificate-based signature (CBS) scheme from lattices is proposed. In our scheme, a user’s certificate and private key are generated by using Ducas et al.’s key extract algorithm over NTRU lattices in Ducas et al. (2014). Instead of Gentry et al.’s key extract algorithm over GPV lattices Gentry et al., 2008, Ducas et al.’s key extract algorithm employed a particular sampling algorithm to produce short trapdoor (private key or certificate). Furthermore, we employ the rejection sampling technique to sign a message. The size of the resulting signature is also shortened. Hence, our CBS scheme from lattices has shorter private key and signature sizes than Tain and Huang’s CBS scheme from lattices (Tian and Huang, 2015). Under the short integer solution (SIS) assumption from lattices (Micciancio and Regev, 2007), the proposed CBS scheme is shown to be existential unforgeability against adaptive chosen message attacks for two adversaries, namely, Type I (general attacker) and Type II (malicious CA). Performance comparisons are made to demonstrate that the proposed CBS scheme from lattices is better than the previous lattice-based CBS schemes.
The rest of the paper is organized as follows. In Section 2, we present several preliminaries. The framework and security notions for CBS schemes are given in Section 3. A new and efficient CBS scheme from lattices is presented in Section 4. In Section 5, the security of the proposed CBS scheme is demonstrated. In Section 6, we present performance comparisons. In Section 7, conclusions are given.
2 Preliminaries
Here, we present several preliminaries that include notations, concepts of lattices, Gaussion distribution, Gaussion sampling algorithm, rejection sampling algorithm, and security assumptions over lattices.
2.1 Notations
Several parameters throughout this article are defined as follows:
-
• N: a specific power-of-two integer.
-
• Z: the set of integers.
-
• R: the set of real values.
-
• ${Z_{q}}$: the set of integers in the interval $[-q/2,q/2)$, where q is a positive integer.
-
• ${R_{q}}$: ${R_{q}}={Z_{q}}[X]/({X^{N}}+1)$, which is a ring of polynomials with coefficients in ${Z_{q}}$ modulo ${X^{N}}+1$.
-
• ${R^{N}},{Z^{N}},{Z_{q}^{N}},{R_{q}^{N}}$: a N-vector (or N elements) of $R,Z,{Z_{q}}$ and ${R_{q}}$, respectively.
-
• x: a vector.
-
• X: a matrix.
-
• $\| \mathbf{x}\| $: $\| \mathbf{x}\| =\sqrt{\textstyle\sum {\mathbf{x}_{i}^{2}}}$ denotes the Euclidean norm of a vector x.
-
• $\| \mathbf{X}{\| _{\infty }}$: $\| \mathbf{X}{\| _{\infty }}=\max [\| {\mathbf{X}_{i}}\| ]$ denotes the maximum norm of all columns of a matrix X.
2.2 Anticirculant Matrices
Here, we introduce the definition (Definition 1) of an anticirculant matrix and its properties (Lemma 1) as follows.
Definition 1.
An $N\times N$ anticirculant matrix of $f\in {R_{q}}$ is a Toeplitz matrix represented by
\[ {\mathbf{C}_{N}}(f)=\left[\substack{(f)\\ {} (x\cdot f)\\ {} \vdots \\ {} ({x^{N-1}}\cdot f)}\right]=\left[\begin{array}{c@{\hskip4.0pt}c@{\hskip4.0pt}c@{\hskip4.0pt}c@{\hskip4.0pt}c}{f_{0}}\hspace{1em}& {f_{1}}\hspace{1em}& {f_{2}}\hspace{1em}& \cdots \hspace{1em}& {f_{N-1}}\\ {} -{f_{N-1}}\hspace{1em}& {f_{0}}\hspace{1em}& {f_{1}}\hspace{1em}& \cdots \hspace{1em}& {f_{N-2}}\\ {} \vdots \hspace{1em}& \vdots \hspace{1em}& \vdots \hspace{1em}& \vdots \hspace{1em}& \vdots \\ {} -{f_{1}}\hspace{1em}& -{f_{2}}\hspace{1em}& \cdots \hspace{1em}& \cdots \hspace{1em}& {f_{0}}\end{array}\right],\]
where $f={\textstyle\sum _{i=0}^{N-1}}{f_{i}}{x_{i}}\in {R_{q}}$. In the sequel, ${\mathbf{C}_{N}}(f)$ is abbreviated as $\mathbf{C}(f)$.Lemma 1 (See Ducas et al., 2014).
Let ${\mathbf{C}_{N}}(f)$ and ${\mathbf{C}_{N}}(g)$ be anticirculant matrices, we have ${\mathbf{C}_{N}}(f)+{\mathbf{C}_{N}}(g)={\mathbf{C}_{N}}(f+g)$ and ${\mathbf{C}_{N}}(f)\cdot {\mathbf{C}_{N}}(g)={\mathbf{C}_{N}}(f\cdot g)$, where $f,g\in {R_{q}}$.
2.3 Lattice and NTRU Lattice
A lattice is a full-rank subgroup of ${R^{n}}$ and an NTRU lattice is convolution modular lattices with a particularly efficient class, which are defined as follows.
Definition 2.
Let $\mathbf{B}=\{{\mathbf{v}_{1}},{\mathbf{v}_{2}},\dots ,{\mathbf{v}_{n}}\}$ be the basis of the n-dimensional lattice Λ, where ${\mathbf{v}_{1}},{\mathbf{v}_{2}},\dots ,{\mathbf{v}_{n}}\in {R^{n}}$ and n are linearly independent vectors. The lattice Λ generated by the basis B is defined as below:
Definition 3.
Let f, g $\in {R_{q}}$, $h=g\ast {f^{-1}}$ and q is a positive integer. The NTRU lattice ${\Lambda _{h,q}}=\{(u,v)\in {R_{q}^{2}}|u+v\ast h=0\}$ is a full-rank lattice of ${Z_{q}^{2N}}$. Indeed, the lattice ${\Lambda _{h,q}}$ may be generated by these rows (vectors) of
\[ {\mathbf{A}_{h,q}}=\left[\begin{array}{c@{\hskip4.0pt}c}-{\mathbf{C}_{N}}(h)\hspace{1em}& {\mathbf{I}_{N}}\\ {} q{\mathbf{I}_{N}}\hspace{1em}& {\mathbf{O}_{N}}\end{array}\right],\]
where ${\mathbf{O}_{N}}$ is the $N\times N$ null matrix and ${\mathbf{I}_{N}}$ is the $N\times N$ unit matrix.Indeed, the basis ${\mathbf{A}_{h,q}}$ is not well suitable to solve the general lattice problem when h is a uniform distribution in ${R_{q}}$. Thus, Hoffstein et al. (2003) constructed the other appropriate basis of ${\Lambda _{h,q}}$ as
\[ {\mathbf{B}_{f,g}}=\left[\begin{array}{c@{\hskip4.0pt}c}\mathbf{C}(g)\hspace{1em}& -\mathbf{C}(f)\\ {} \mathbf{C}(G)\hspace{1em}& -\mathbf{C}(F)\end{array}\right],\]
where $F,G\in {R_{q}}$ such that $f\ast G-g\ast F=q$. Indeed, ${\mathbf{B}_{f,g}}$ is a short basis for ${\Lambda _{h,q}}$ and has the following properties. Lemma 2 (See Ducas et al., 2014).
If $f,g,F,G\in {R_{q}}$ such that $f\ast G-g\ast F=q$ and $h=g\ast {f^{-1}}$, the short basis, ${\mathbf{B}_{f,g}}$ may generate the same NTRU lattice ${\Lambda _{h,q}}$ generated by the basis , ${\mathbf{A}_{h,q}}$ while satisfying $\| {\mathbf{B}_{f,g}}\| \leqslant \| {\mathbf{A}_{h,q}}\| $.
Lemma 3 (See Ducas et al., 2014).
Let N and q be a power-of-two integer and a prime, respectively. There exists a probabilistic polynomial-time (PPT) algorithm $\mathbf{TrapGen}(q,N)$ that may generate two polynomials f and g while computing $h=g\ast {f^{-1}}$, and output a short trapdoor basis ${\mathbf{B}_{f,g}}$ of ${\Lambda _{h,q}}$. It is worth mentioning that h is statistically close to be uniform in ${R_{q}}$ and publicly published.
2.4 Gaussian Distribution and Sampling Technique
In this section, we define the Gaussian distributions and sampling technique, which are useful tools for lattice-based cryptography.
Definition 4.
The continuous Gaussian distribution over ${R^{N}}$ with the centre $\mathbf{c}\in {R^{N}}$ and the standard deviation $s>0$, is defined as
Definition 5.
For any lattice $\Lambda \in {Z^{N}}$, the discrete Gaussian distribution over ${Z^{N}}$ with the standard deviation $s>0$ and the centre $\mathbf{c}\in {Z^{N}}$, is defined as ${D_{\mathbf{c},s}^{N}}(\mathbf{x})={\rho _{\mathbf{c},s}^{N}}(\mathbf{x})/{\rho _{\mathbf{c},s}^{N}}(\Lambda )$, where $\mathbf{x}\in {Z^{N}}$ and ${\rho _{\mathbf{c},s}^{N}}(\Lambda )={\textstyle\sum _{\mathbf{x}\in \Lambda }}{\rho _{\mathbf{c},s}^{N}}(\mathbf{x})$. In the sequel, ${\rho _{0,s}^{N}}$ and ${D_{0,s}^{N}}$ are abbreviated as ${\rho _{s}^{N}}$ and ${D_{s}^{N}}$ respectively.
For the discrete Gaussian distribution ${D_{\mathbf{c},\sigma }^{N}}(\mathbf{x})$, Lyubashevsky (2012) gave two properties as follows.
Lemma 4 (See Lyubashevsky, 2012).
Let $\mathbf{c}\in {Z^{N}}$.
-
(1) If $\sigma =\omega (\| \mathbf{c}\| \sqrt{\log N})$, we have Pr[$\mathbf{x}\in {D_{\sigma }^{N}};{D_{\sigma }^{N}}(\mathbf{x})/{D_{\mathbf{c},\sigma }^{N}}(\mathbf{x})=O(1)]=1-{2^{-\omega (\log N)}}$.
-
(2) If $\alpha >0$ and $\sigma =\alpha \| \mathbf{c}\| $, we have Pr[$\mathbf{x}\in {D_{\sigma }^{N}};{D_{\sigma }^{N}}(\mathbf{x})/{D_{\mathbf{c},\sigma }^{N}}(\mathbf{x})<{e^{12/\alpha +1/(2{\sigma ^{2}})}}]=1-{2^{-100}}$.
In the following, let us introduce the Gaussian sampling technique over general lattices. Indeed, one takes a noise vector from a Gaussian distribution and adds this noise vector to a lattice, she/he may obtain a distribution which is very close to uniform distribution (Micciancio and Regev, 2007). Based on this fact, Gentry et al. (2008) proposed a trapdoor (private key) generation algorithm by using the Gaussian sampling technique from lattices. Furthermore, Ducas et al. (2014) improved Gentry et al.’s trapdoor generation algorithm to propose a specific sampling algorithm over NTRU lattices to reduce the private key size by using a short basis ${\mathbf{B}_{f,g}}$ generated in Lemma 2. Ducas et al.’s trapdoor generation algorithm has the following property.
Lemma 5 (See Ducas et al., 2014).
Let ${\mathbf{B}_{f,g}}$ be a short basis of an N-dimensional lattice Λ. Let ${\tilde{\mathbf{B}}_{f,g}}$ be the Gram–Schmidt orthogonalization of ${\mathbf{B}_{f,g}}$. If $s\geqslant \| {\tilde{\mathbf{B}}_{f,g}}\| \omega (\sqrt{\log N})$ and $0<\varepsilon <1$, we have
\[ Pr\big[\| \mathbf{x}-\mathbf{c}\| >s\sqrt{N}\big]\leqslant \frac{1+\varepsilon }{1-\varepsilon }{2^{-N}}\hspace{1em}\textit{for any}\hspace{2.5pt}\mathbf{c}\in {Z^{N}}\hspace{2.5pt}\textit{and}\hspace{2.5pt}\mathbf{x}\in {D_{\mathbf{c},s}^{N}}.\]
And there exists an PPT algorithm $\mathbf{GauSample}({\mathbf{B}_{f,g}},s,\mathbf{c})$ that produces a distribution statistically close to ${D_{\mathbf{c},s}^{N}}$.
2.5 Rejection Sampling Technique
In our CBS scheme from lattices, we employ the rejection sampling technique to sign a message. The rejection sampling technique was proposed by Lyubashevsky (2012). Its idea is to make the distribution of a resulting signature be independent of the signing key. In addition, the rejection sampling technique requires just a few matrix-vector multiplications and rejection samplings so that it is simple and efficient. The idea of the rejection sampling technique works as follows. If a signer with the signing key S would like to generate a signature σ on a message m, the signer first chooses a random vector y from some distribution (i.e. Gaussian distribution) and computes the candidate signature z. Namely, the signer first uses the signing key S to multiply the resulting vector c of some function with inputting message m and then adds the random vector y, denoted as $\mathbf{z}=\mathbf{S}\mathbf{c}+\mathbf{y}$. Without loss of generality, let the distribution ${D_{\sigma }^{N}}(\mathbf{x})$ be the target distribution and the signature is the distribution vector ${D_{\mathbf{S}\mathbf{c},\sigma }^{N}}(\mathbf{x})$. If ${D_{\sigma }^{N}}(\mathbf{x})\leqslant M\cdot {D_{\mathbf{S}\mathbf{c},\sigma }^{N}}(\mathbf{x})$ for all x, then the candidate signature z may be generated with probability ${D_{\sigma }^{N}}(\mathbf{z})/M\cdot {D_{\mathbf{S}\mathbf{c},\sigma }^{N}}(\mathbf{z})$. If the resulting signature does not satisfy the above condition, then the signature z will be rejected. The expected number of times that the process generates a valid signature is M.
2.6 SIS Assumption from Lattices
Here, we present a mathematical assumption, called the short integer solution (SIS) assumption from lattices. The difficulty of the SIS problem is equal to that of the worst-case of short independent vector problem (SIVP) up to a polynomial approximation factor (Ajtai, 1996). The SIS problem and assumption are defined as follows.
Definition 6.
${\mathrm{SIS}_{q,N,\beta }}$ problem: let q be a positive integer, β be a real number, and ${f_{1}},{f_{2}},\dots ,{f_{N}}$ be polynomials chosen uniformly and independently from ${R_{q}}$. The ${\mathrm{SIS}_{q,N,\beta }}$ problem is to find non-zero integers ${r_{1}},{r_{2}},\dots ,{r_{N}}$ such that ${\textstyle\sum _{i=1}^{N}}{r_{i}}{f_{i}}=0$ mod q and $\| ({r_{1}},{r_{2}},\dots ,{r_{N}})\| \leqslant \beta $.
Definition 7.
${\mathrm{SIS}_{q,N,\beta }}$ assumption: for the ${\mathrm{SIS}_{q,N,\beta }}$ problem defined above, there exists no probabilistic polynomial-time adversary A with non-negligible probability who can find such non-zero integers ${r_{1}},{r_{2}},\dots ,{r_{N}}$.
By Ducas et al. (2014), the SIS problem on NTRU lattices is to find a pair $({\mathbf{z}_{1}},{\mathbf{z}_{2}})$ such that ${\mathbf{z}_{1}}+h\ast {\mathbf{z}_{2}}=0$ and $\| ({\mathbf{z}_{1}},{\mathbf{z}_{2}})\| \leqslant \beta $. The statistical distance between the distribution of $h=g/f$ and the uniform distribution of ${R_{q}}$ is negligible (Stehle and Steinfeld, 2013).
3 Framework and Adversary Model of CBS
In this section, the framework and adversary model of certificate-based signature (CBS) schemes are defined here. They are identical to the framework and adversary model in Li et al. (2007), Wu et al. (2009), Li et al. (2012), Hung et al. (2016a).
In a CBS scheme, there are two kinds of roles, namely, users (signers/verifiers) and a trusted certificate authority (CA). A user independently generates her/his private/public key pair and sends the public key to the CA. And, the CA uses a system private key to generate and send the associated certificate to the user. An CBS scheme consists of five algorithms, namely, Setup, User key generation, Certificate extract, Sign and Verify algorithms defined as follows.
Definition 8.
A certificate-based signature (CBS) scheme consists of five algorithms:
-
– Setup algorithm is probabilistic, which is performed by the CA. It takes as input a security parameter and returns the system private key ${S_{\mathit{CA}}}$ and public parameters PP. The system private key ${S_{\mathit{CA}}}$ is kept secret by the CA itself.
-
– User key generation algorithm is probabilistic, which is performed by users. It takes as input the identity $\mathit{ID}$ of a user and returns the associated private key ${S_{\mathit{ID}}}$ and public key ${P_{\mathit{ID}}}$. In addition, it also publishes the public key ${P_{\mathit{ID}}}$ in a public directory.
-
– Certificate extract algorithm is deterministic, which is performed by the CA. It takes as input the system private key ${S_{\mathit{CA}}}$, the public parameters PP and a user’s identity $\mathit{ID}$ with public key ${P_{\mathit{ID}}}$, and returns the associated certificate ${C_{\mathit{ID}}}$ to the user.
-
– Sign algorithm is probabilistic, which is performed by users. It takes as input a message m, her/his private key ${S_{\mathit{ID}}}$ and certificate ${C_{\mathit{ID}}}$, and returns a signature ρ.
-
– Verify algorithm is deterministic, which is performed by users. It takes as input a signature ρ, a message m and a user’s identity $\mathit{ID}$ with the public key ${P_{\mathit{ID}}}$, and outputs either “accept” or “reject”.
In the following, we define the existential unforgeability of CBS schemes against adaptive chosen-message attacks (EUF-CBS-ACMA). The EUF-CBS-ACMA attacks consist of two types of adversaries, namely, Type I and Type II adversaries.
-
• Type I adversary (uncertified entity): This adversary is a general attacker (uncertified entity) who can obtain secret key of any entity. Meanwhile, it is allowed to acquire certificate of any entity, except the certificate of an attacking target entity.
-
• Type II adversary (honest-but-curious CA): This adversary acts as the honest-but-curious CA so that it holds the system private key ${S_{\mathit{CA}}}$ and can generate certificate of any entity. Meanwhile, it is allowed to acquire secret key of any entity, except the secret key of an attacking target entity.
In the following, an adversary model of CBS schemes against the EUF-CBS-ACMA attacks is presented.
Definition 9.
An CBS scheme provides existential unforgeability against adaptive chosen-messageattacks (EUF-CBS-ACMA) if no probabilistic polynomial-time (PPT) adversary A has a non-negligible advantage in the following game played between a challenger C and the adversary A.
-
– Setup. The challenger C runs the Setup algorithm to generate the system private key ${S_{\mathit{CA}}}$ and public parameters PP. In addition, PP is sent to A. If A is of Type I adversary, ${S_{\mathit{CA}}}$ is kept secret by C. If A is of Type II adversary, C sends the system private key ${S_{\mathit{CA}}}$ to A.
-
– Queries. The adversary A may adaptively issue the following queries to the challenger C. It is worth mentioning that if A is of Type II adversary, it does not need to issue the certificate extract query since Type II adversary knows the system private key ${S_{\mathit{CA}}}$ and may compute the certificates of all the users.
-
• User key generation query(ID). C performs the User key generation algorithm to return the associated private key ${S_{\mathit{ID}}}$ and public key ${P_{\mathit{ID}}}$ of the user with identity ID to A.
-
• Certificate extract query(ID, ${P_{\mathit{ID}}}$). C performs the Certificate extract algorithm to return the associated certificate ${C_{\mathit{ID}}}$ of the user with identity ID to A.
-
• Corruption query(ID). C returns the associated private key ${S_{\mathit{ID}}}$ of the user with identity ID to A.
-
• Public key replacement query(ID, ${P^{\prime }_{\mathit{ID}}}$). The adversary A chooses a new public key ${P^{\prime }_{\mathit{ID}}}$ for the user with identity ID. C records this public key replacement in a public directory. Meanwhile, it denotes that A knows the associated private key ${S_{\mathit{ID}}}$ of the user with identity ID.
-
• Sign query(m, ID). Given a message m and identity ID with the public key ${P_{\mathit{ID}}}$, C generates a valid signature ρ and returns it to A.
-
-
– Forgery. Finally, the adversary A produces a signature tuple $({\rho ^{\ast }}$, ${m^{\ast }}$, ${\mathit{ID}^{\ast }},$ ${P_{{\mathit{ID}^{\ast }}}})$. The advantage of A is defined as the probability that A wins the game. We say that A wins the game if the following conditions hold.
-
(1) The response of the Verify algorithm on $({\rho ^{\ast }}$, ${m^{\ast }}$, ${\mathit{ID}^{\ast }},$ ${P_{{\mathit{ID}^{\ast }}}})$ is “accept”.
-
(2) $({m^{\ast }},{\mathit{ID}^{\ast }})$ has never been issued in the sign query.
-
(3) If A is of Type I adversary, ${\mathit{ID}^{\ast }}$ has never been issued in the Certificate extract query.
-
(4) If A is of Type II adversary, it does not know the private key of the attacking target entity ${\mathit{ID}^{\ast }}$, namely, ${\mathit{ID}^{\ast }}$ has never been issued in the User key generation, Public key replacement and Corruption queries.
-
4 An Efficient CBS Scheme from Lattices
Here, we propose a new and efficient CBS scheme from lattices. By the framework defined in Section 3, the proposed CBS scheme consists of five algorithms as below.
-
– Setup algorithm: Assume that N, q and λ are, respectively, a security parameter, a large prime and a positive integer while setting two standard deviations $s>0$ and $\sigma >0$. The CA runs $\mathbf{TrapGen}(q,N)$ in Lemma 3 to produce two polynomials f and g and compute $h=g\ast {f^{1}}$, where $f,g\in {R_{q}}$ and $\| f\| $, $\| g\| <s\sqrt{N}$ while h is statistically close to be uniform in ${R_{q}}$. In the meantime, the CA also produces is a short trapdoor basis ${\mathbf{B}_{f,g}}$ of the lattice ${\Lambda _{h,q}}$, which is viewed as the system private key ${S_{\mathit{CA}}}$. The CA chooses two values ${p_{1}}$, ${p_{2}}\in {Z_{q}^{N}}$ and sets the system public key as $(h$, ${p_{1}}$, ${p_{2}})$. In addition, the CA selects two hash functions ${H_{1}}$:${\{0,1\}^{\ast }}\times {Z_{q}^{N}}$ $\to {Z_{q}^{N}}$ and ${H_{2}}$:${\{0,1\}^{\ast }}$ $\times {Z_{q}^{N}}$ $\times {Z_{q}^{N}}$ $\to \{\mathbf{v}:\mathbf{v}\in {\{-1,0,1\}^{N}},\| \mathbf{v}{\| _{1}}\leqslant \lambda \}$, where $\| \mathbf{v}{\| _{1}}$ denotes the amount of non-zero elements of v. Finally, the CA sets the public parameters $PP=\langle N,\lambda ,s,\sigma ,q,h,{p_{1}},{p_{2}},{H_{1}},{H_{2}}\rangle $.
-
– User key generation algorithm: The user with identity $\mathit{ID}$ sets her/his private key ${S_{\mathit{ID}}}=({\mathbf{s}_{1}},{\mathbf{s}_{2}})$, which is randomly and uniformly chosen from ${\{-d,\dots ,0,\dots ,d\}^{N}}$, where $1\leqslant d\leqslant 31$. Meanwhile, the user computes the associated public key ${P_{\mathit{ID}}}={p_{1}}\ast {\mathbf{s}_{1}}+{p_{2}}\ast {\mathbf{s}_{2}}$.
-
– Certificate extract algorithm: Upon receiving the identity $\mathit{ID}$ and public key ${P_{\mathit{ID}}}$ of a user, the CA computes ${T_{\mathit{ID}}}$ = ${H_{1}}(ID,{P_{\mathit{ID}}})\in {z_{q}^{N}}$ and generates the user’s certificate ${C_{\mathit{ID}}}=({\mathbf{s}_{3}},{\mathbf{s}_{4}})$ such that ${\mathbf{s}_{3}}+h\ast {\mathbf{s}_{4}}={T_{\mathit{ID}}}$ and $\| ({\mathbf{s}_{3}},{\mathbf{s}_{4}})\| <s\sqrt{2N}$ by running $\mathbf{GauSample}(\mathbf{B},s,({T_{\mathit{ID}}},0))$ in Lemma 5. The CA returns the certificate ${C_{\mathit{ID}}}=({\mathbf{s}_{3}},{\mathbf{s}_{4}})$ to the user via a secure channel.
-
– Sign algorithm: Given a message $m\in {\{0,1\}^{\ast }}$, the user with the private key ${S_{\mathit{ID}}}=({\mathbf{s}_{1}},{\mathbf{s}_{2}})$ and certificate ${C_{\mathit{ID}}}=({\mathbf{s}_{3}},{\mathbf{s}_{4}})$ randomly selects ${\mathbf{y}_{1}},{\mathbf{y}_{2}},{\mathbf{y}_{3}}$ and ${\mathbf{y}_{4}}$ from the distribution ${D_{\sigma }^{N}}$, and computes the following values:\[\begin{array}{r@{\hskip4.0pt}c@{\hskip4.0pt}l}\mathbf{c}& =& {H_{2}}(m,{p_{1}}\ast {\mathbf{y}_{1}},{p_{2}}\ast {\mathbf{y}_{2}},{\mathbf{y}_{3}}+h\ast {\mathbf{y}_{4}});\\ {} {\mathbf{z}_{1}}& =& {\mathbf{y}_{1}}+{\mathbf{s}_{1}}\ast \mathbf{c};\\ {} {\mathbf{z}_{2}}& =& {\mathbf{y}_{2}}+{\mathbf{s}_{2}}\ast \mathbf{c};\\ {} {\mathbf{z}_{3}}& =& {\mathbf{y}_{3}}+{\mathbf{s}_{3}}\ast \mathbf{c};\\ {} {\mathbf{z}_{4}}& =& {\mathbf{y}_{4}}+{\mathbf{s}_{4}}\ast \mathbf{c},\end{array}\]where $\| ({\mathbf{z}_{1}},{\mathbf{z}_{2}},{\mathbf{z}_{3}},{\mathbf{z}_{4}})\| \leqslant 2\sigma \sqrt{4N}$. If $\| ({\mathbf{z}_{1}},{\mathbf{z}_{2}},{\mathbf{z}_{3}},{\mathbf{z}_{4}})\| \leqslant 2\sigma \sqrt{4N}$ does not hold, the user reruns this algorithm. By (Lyubashevsky, 2012), there exists a constant $M=O(1)$ such that the user can produce such a signature $\rho =({\mathbf{z}_{1}},{\mathbf{z}_{2}},{\mathbf{z}_{3}},{\mathbf{z}_{4}},\mathbf{c})$ with probability min(${D_{\sigma }^{4N}}(\mathbf{z})/M{D_{v,\sigma }^{4N}}(\mathbf{z}),1$), where and
-
– Verify algorithm: Given a signature $\rho =({\mathbf{z}_{1}},{\mathbf{z}_{2}},{\mathbf{z}_{3}},{\mathbf{z}_{4}},\mathbf{c})$, a message m and a user’s identity $\mathit{ID}$ with public key ${P_{\mathit{ID}}}$, a verifier validates the signature by the equality\[ \mathbf{c}={H_{2}}(m,{p_{1}}\ast {\mathbf{z}_{1}}+{p_{2}}\ast {\mathbf{z}_{2}}-{P_{\mathit{ID}}}\ast \mathbf{c},{\mathbf{z}_{3}}+h\ast {\mathbf{z}_{4}}-{T_{\mathit{ID}}}\ast \mathbf{c}).\]If the equality holds, the algorithm returns “accept”. Otherwise, the algorithm returns “reject”. The correctness of the equality follows by\[\begin{aligned}{}& {H_{2}}(m,{p_{1}}\ast {\mathbf{z}_{1}}+{p_{2}}\ast {\mathbf{z}_{2}}-{P_{\mathit{ID}}}\ast \mathbf{c},{\mathbf{z}_{3}}+h\ast {\mathbf{z}_{4}}-{T_{\mathit{ID}}}\ast \mathbf{c})\\ {} & \hspace{1em}={H_{2}}(m,{p_{1}}\ast ({\mathbf{y}_{1}}+{\mathbf{s}_{1}}\ast \mathbf{c})+{p_{2}}\ast ({\mathbf{y}_{2}}+{\mathbf{s}_{2}}\ast \mathbf{c})-({p_{1}}\ast {\mathbf{s}_{1}}+{p_{2}}\ast {\mathbf{s}_{2}})\ast \mathbf{c},\\ {} & \hspace{2em}{\mathbf{y}_{3}}+{\mathbf{s}_{3}}\ast \mathbf{c}+h\ast ({\mathbf{y}_{4}}+{\mathbf{s}_{4}}\ast \mathbf{c})-({\mathbf{s}_{3}}+h\ast {\mathbf{s}_{4}})\ast \mathbf{c})\\ {} & \hspace{1em}={H_{2}}(m,{p_{1}}\ast {\mathbf{y}_{1}}+{p_{2}}\ast {\mathbf{y}_{2}},{\mathbf{y}_{3}}+h\ast {\mathbf{y}_{4}}).\end{aligned}\]
5 Security Analysis
According to the framework and adversary model of CBS schemes, the signing key of a user with identity $\mathit{ID}$ include two components, namely, the private key ${S_{\mathit{ID}}}$ and the associated certificate ${C_{\mathit{ID}}}$. By the EUF-CBS-ACMA game aforementioned in Definition 9, there are two kinds of adversaries, namely, Type I adversary (uncertified entity) and Type II adversary (honest-but-curious CA). Type I adversary is a general attacker without knowing the system private key ${S_{\mathit{CA}}}$ so that it did not compute the certificate of an attacking target entity. Type II adversary acts as the honest-but-curious CA so that it holds the system private key ${S_{\mathit{CA}}}$, but does not know the private key of the attacking target entity.
The security analysis of the proposed CBS scheme is formally proved as follows. In Theorem 1, we prove that our CBS scheme from lattices is secure against Type I adversary (uncertified entity). Theorem 2 shows that the proposed CBS scheme is secure against Type II adversary (honest-but-curious CA).
Theorem 1.
Let two hash functions ${H_{1}}$ and ${H_{2}}$ be random oracles controlled by a challenger in the EUF-CBS-ACMA game. If there exists a probabilistic polynomial-time (PPT) adversary A (Type I adversary, general attacker) with non-negligible probability who can break our CBS scheme over lattices, an algorithm C can be constructed to solve the SIS problem from lattices with non-negligible probability $(1-{2^{-\omega (\log N)}})\varepsilon $, where N is the security parameter.
Proof.
Assume that N, q and λ are, respectively, a security parameter, a large prime and a positive integer while setting two standard deviations $s>0$ and $\sigma >0$. Assume that the algorithm C be a challenger in the EUF-CBS-ACMA game while receiving a random instance $(q,2N,2\lambda s\sqrt{2N}+4\sigma \sqrt{2N})$ of the SIS problem. In the following, we demonstrate that the challenger C may obtain a non-zero vector solution $({\mathbf{u}_{1}},{\mathbf{u}_{2}})\in {R_{q}^{2}}$ of the SIS problem if the adversary A with non-negligible probability ε who can break our CBS scheme.
-
– Setup. As the Setup algorithm in the proposed CBS scheme, C randomly chooses ${p_{1}},{p_{2}}\in {Z_{q}^{N}}$ and $h\in {R_{q}}$ while controlling the random oracles ${H_{1}}$ and ${H_{2}}$. C sets the public parameters $PP$=$\langle N,\lambda ,s,\sigma ,q,h,{p_{1}},{p_{2}},{H_{1}},{H_{2}}\rangle $ and sends them to A. Initially, C constructs three empty lists ${L_{1}}$, ${L_{2}}$ and ${L_{S}}$.
-
– Queries. A may issue several queries to C adaptively as below:
-
• ${H_{1}}$ $query$: Let ${L_{1}}$ consist of tuples of the form $\langle {\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}},{C_{{\mathit{ID}_{i}}}},{T_{{\mathit{ID}_{i}}}}\rangle $. For the query along with $({\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}})$, C returns a response to this query by the following procedures.
-
1. Search $({\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}})$ in ${L_{1}}$. If the tuple is found, it means that this query has been already issued and the same answer ${T_{{\mathit{ID}_{i}}}}$ is sent to A.
-
2. Otherwise, randomly select ${\mathbf{s}_{i3}},{\mathbf{s}_{i4}}\in {D_{s}^{N}}$ such that $\| ({\mathbf{s}_{i3}},{\mathbf{s}_{i4}})\| <s\sqrt{2N}$, and compute ${T_{{\mathit{ID}_{i}}}}={\mathbf{s}_{i3}}+h\ast {\mathbf{s}_{i4}}$. Finally, C adds $\langle {\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}},{C_{{\mathit{ID}_{i}}}}=({\mathbf{s}_{i3}},{\mathbf{s}_{i4}}),{T_{{\mathit{ID}_{i}}}}\rangle $ in ${L_{1}}$ and sends ${T_{{\mathit{ID}_{i}}}}$ to A.
-
-
• ${H_{2}}$ query: Let ${L_{2}}$ consist of tuples of the form $\langle {m_{j}},{v_{j}},{w_{j}},{\mathbf{c}_{j}}\rangle $. For the query along with $({m_{j}},{v_{j}},{w_{j}})$, C returns a response to this query by the following procedures.
-
1. Search $({m_{j}},{v_{j}},{w_{j}})$ in ${L_{2}}$. If the tuple is found, it means that this query has been already issued and the same answer ${\mathbf{c}_{j}}$ is sent to A.
-
2. Otherwise, randomly select ${\mathbf{c}_{j}}\in {Z_{q}^{N}}$. Finally, C adds $\langle {m_{j}},{v_{j}},{w_{j}},{\mathbf{c}_{j}}\rangle $ in ${L_{2}}$ and sends ${\mathbf{c}_{j}}$ to A.
-
-
• User key generation query: Let ${L_{S}}$ consist of tuples of the form $\langle {\mathit{ID}_{i}},{S_{{\mathit{ID}_{i}}}},{P_{{\mathit{ID}_{i}}}}\rangle $. For the query along with ${\mathit{ID}_{i}}$, C returns a response to this query by the following procedures.
-
1. Search ${\mathit{ID}_{i}}$ in ${L_{S}}$. If the tuple is found, it means that this query has been already issued and the same answer ${S_{{\mathit{ID}_{i}}}}=({\mathbf{s}_{i1}},{\mathbf{s}_{i2}})$ is sent to A.
-
2. Otherwise, randomly select ${\mathbf{s}_{i1}},{\mathbf{s}_{i2}}\in {\{-d,\dots ,0,\dots ,d\}^{N}}$, where $1\leqslant d\leqslant 31$, and compute the public key ${P_{{\mathit{ID}_{i}}}}=({p_{1}}\ast {\mathbf{s}_{i1}}+{p_{2}}\ast {\mathbf{s}_{i2}})$ Finally, C adds $\langle {\mathit{ID}_{i}},{S_{{\mathit{ID}_{i}}}},{P_{{\mathit{ID}_{i}}}}\rangle $ in ${L_{S}}$ and sends ${S_{{\mathit{ID}_{i}}}}=({\mathbf{s}_{i1}},{\mathbf{s}_{i2}})$ to A.
-
-
• Certificate extract query: For the query along with (${\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}}$), C returns a response to this query by the following procedures.
-
1. Search (${\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}}$) in ${L_{1}}$. If the tuple is found, it means that this query has been already issued and the same answer ${C_{{\mathit{ID}_{i}}}}$ is sent to A.
-
2. Otherwise, issue the ${H_{1}}$ query to obtain the tuple $\langle {\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}},{C_{{\mathit{ID}_{i}}}},{T_{{\mathit{ID}_{i}}}}\rangle $ and return ${C_{{\mathit{ID}_{i}}}}$ to A.
-
-
• Corruption query: For the query along with ${\mathit{ID}_{i}}$, C returns a response to this query by the following procedures.
-
1. Search ${\mathit{ID}_{i}}$ in ${L_{S}}$. If the tuple is found, it means that this query has been already issued and the same answer ${S_{{\mathit{ID}_{i}}}}$ is sent to A.
-
2. Otherwise, issue the User key generation query to obtain the tuple $\langle {\mathit{ID}_{i}},{S_{{\mathit{ID}_{i}}}},{P_{{\mathit{ID}_{i}}}}\rangle $ and return ${S_{{\mathit{ID}_{i}}}}$ to A.
-
-
• Public key replacement query: A issues this query along with a new public key ${P^{\prime }_{{\mathit{ID}_{i}}}}$ of ${\mathit{ID}_{i}}$ to replace the old public key ${P_{{\mathit{ID}_{i}}}}$, C replaces the ${P_{{\mathit{ID}_{i}}}}$ of $\langle {\mathit{ID}_{i}},{S_{{\mathit{ID}_{i}}}},{P_{{\mathit{ID}_{i}}}}\rangle $ in ${L_{S}}$ with ${P^{\prime }_{{\mathit{ID}_{i}}}}$.
-
• Sign query: For the query along with a message ${m_{j}}$ and (${\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}}$), the challenger C performs the following procedures to generate a valid signature.
-
1. Respectively search ${\mathit{ID}_{i}}$ in ${L_{1}}$ and ${L_{S}}$ to get the tuples $\langle {\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}},{C_{{\mathit{ID}_{i}}}},{T_{{\mathit{ID}_{i}}}}\rangle $ and $\langle {\mathit{ID}_{i}},{S_{{\mathit{ID}_{i}}}},{P_{{\mathit{ID}_{i}}}}\rangle $
-
2. Randomly choose ${\mathbf{c}_{j}}\in \{\mathbf{v}:\mathbf{v}\in {\{-1,0,1\}^{N}},\| \mathbf{v}{\| _{1}}\leqslant \lambda \}$ and ${\mathbf{z}_{1}},{\mathbf{z}_{2}},$ ${\mathbf{z}_{3}}$, ${\mathbf{z}_{4}}\in {D_{\sigma }^{N}}$ such that $\| ($ ${\mathbf{z}_{1}},{\mathbf{z}_{2}},$ ${\mathbf{z}_{3}}$, ${\mathbf{z}_{4}})\| \leqslant 2\sigma \sqrt{4N}$, and compute ${v_{j}}$ = ${p_{1}}\ast {\mathbf{z}_{1}}$ + ${p_{2}}\ast {\mathbf{z}_{2}}$ - ${P_{{\mathit{ID}_{i}}}}\ast {\mathbf{c}_{j}}$ and ${w_{j}}$ = ${\mathbf{z}_{3}}$ + $h\ast {\mathbf{z}_{4}}$ - ${T_{{\mathit{ID}_{i}}}}\ast {\mathbf{c}_{j}}$.
-
3. Send the signature $\rho =({\mathbf{z}_{1}},{\mathbf{z}_{2}},$ ${\mathbf{z}_{3}}$, ${\mathbf{z}_{4}},{\mathbf{c}_{j}})$ to A while adding $\langle {m_{j}},{v_{j}},{w_{j}},{\mathbf{c}_{j}}\rangle $ in ${L_{2}}$. Note that the signature ρ is valid because the following equality holds:
-
-
-
– Forgery. Finally, the adversary A generates a signature tuple (${\mathbf{z}_{1}^{\ast }},{\mathbf{z}_{2}^{\ast }},$ ${\mathbf{z}_{3}^{\ast }}$, ${\mathbf{z}_{4}^{\ast }},{\mathbf{c}^{\ast }})$ on some message ${m^{\ast }}$ for some ${\mathit{ID}^{\ast }}$.
Assume that A may generate a valid signature ${\rho ^{\ast }}$ = (${\mathbf{z}_{1}^{\ast }},{\mathbf{z}_{2}^{\ast }},$ ${\mathbf{z}_{3}^{\ast }}$, ${\mathbf{z}_{4}^{\ast }},{\mathbf{c}^{\ast }})$. By the Forking lemma (Pointcheval and Stern, 2000), the challenger C can generate the other valid signature (${\mathbf{z}^{\prime }_{1}},{\mathbf{z}^{\prime }_{2}},$ ${\mathbf{z}^{\prime }_{3}}$, ${\mathbf{z}^{\prime }_{4}},{\mathbf{c}^{\prime }})$ such that ${\mathbf{c}^{\ast }}\ne {\mathbf{c}^{\prime }}$ by the same random tape with different hash value of ${H_{2}}$ $query$. Because (${\mathbf{z}_{1}^{\ast }},{\mathbf{z}_{2}^{\ast }},$ ${\mathbf{z}_{3}^{\ast }}$, ${\mathbf{z}_{4}^{\ast }},{\mathbf{c}^{\ast }})$ and (${\mathbf{z}^{\prime }_{1}},{\mathbf{z}^{\prime }_{2}},$ ${\mathbf{z}^{\prime }_{3}}$, ${\mathbf{z}^{\prime }_{4}},{\mathbf{c}^{\prime }})$ are two valid signatures on the message ${m^{\ast }}$ for (${\mathit{ID}^{\ast }}$, ${P_{{\mathit{ID}^{\ast }}}}$), we can obtain the equality
\[\begin{aligned}{}& {H_{2}}\big({m^{\ast }},{p_{1}}\ast {\mathbf{z}_{1}^{\ast }}+{p_{2}}\ast {\mathbf{z}_{2}^{\ast }}-{P_{{\mathit{ID}^{\ast }}}}\ast {\mathbf{c}^{\ast }},{\mathbf{z}_{3}^{\ast }}+h\ast {\mathbf{z}_{4}^{\ast }}-{T_{{\mathit{ID}^{\ast }}}}\ast {\mathbf{c}^{\ast }}\big)\\ {} & \hspace{1em}={H_{2}}\big({m^{\ast }},{p_{1}}\ast {\mathbf{z}^{\prime }_{1}}+{p_{2}}\ast {\mathbf{z}^{\prime }_{2}}-{P_{{\mathit{ID}^{\ast }}}}\ast {\mathbf{c}^{\prime }},{\mathbf{z}^{\prime }_{3}}+h\ast {\mathbf{z}^{\prime }_{4}}-{T_{{\mathit{ID}^{\ast }}}}\ast {\mathbf{c}^{\prime }}\big),\end{aligned}\]
which reduces to
\[ {\mathbf{z}_{3}^{\ast }}+h\ast {\mathbf{z}_{4}^{\ast }}-{T_{{\mathit{ID}^{\ast }}}}\ast {\mathbf{c}^{\ast }}={\mathbf{z}^{\prime }_{3}}+h\ast {\mathbf{z}^{\prime }_{4}}-{T_{{\mathit{ID}^{\ast }}}}\ast {\mathbf{c}^{\prime }}.\]
Since ${T_{{\mathit{ID}^{\ast }}}}={\mathbf{s}_{3}}+h\ast {\mathbf{s}_{4}}$, we have
\[\begin{aligned}{}& {\mathbf{z}_{3}^{\ast }}+h\ast {\mathbf{z}_{4}^{\ast }}-({\mathbf{s}_{3}}+h\ast {\mathbf{s}_{4}})\ast {\mathbf{c}^{\ast }}={\mathbf{z}^{\prime }_{3}}+h\ast {\mathbf{z}^{\prime }_{4}}-({\mathbf{s}_{3}}+h\ast {\mathbf{s}_{4}})\ast {\mathbf{c}^{\prime }};\\ {} & {\mathbf{z}_{3}^{\ast }}-{\mathbf{z}^{\prime }_{3}}-{\mathbf{s}_{3}}\big({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}\big)+h\ast \big({\mathbf{z}_{4}^{\ast }}-{\mathbf{z}^{\prime }_{4}}-{\mathbf{s}_{4}}\big({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}\big)\big)=0;\\ {} & (1,h)\ast \big({\mathbf{z}_{3}^{\ast }}-{\mathbf{z}^{\prime }_{3}}-{\mathbf{s}_{3}}\big({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}\big),{\mathbf{z}_{4}^{\ast }}-{\mathbf{z}^{\prime }_{4}}-{\mathbf{s}_{4}}\big({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}\big)\big)=0.\end{aligned}\]
Afterward, C sets $({\mathbf{u}_{1}},{\mathbf{u}_{2}})=({\mathbf{z}_{3}^{\ast }}-{\mathbf{z}^{\prime }_{3}}-{\mathbf{s}_{3}}({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}),{\mathbf{z}_{4}^{\ast }}-{\mathbf{z}^{\prime }_{4}}-{\mathbf{s}_{4}}({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}))$.If we have $\| ({\mathbf{z}_{3}^{\ast }}-{\mathbf{z}^{\prime }_{3}},{\mathbf{z}_{4}^{\ast }}-{\mathbf{z}^{\prime }_{4}})\| \leqslant 4\sigma \sqrt{2N}$ and $\| ({\mathbf{s}_{3}},{\mathbf{s}_{4}})\| $ ⩽ $s\sqrt{2N}$ with overwhelming probability, we can obtain $\| ({\mathbf{u}_{1}},{\mathbf{u}_{2}})\| \leqslant 2\lambda s\sqrt{2N}$ + $4\sigma \sqrt{2N}$. As stated in Lemma 3, the distribution of $h=g/f$ is statistically close to the uniform distribution of ${R_{q}}$ (Stehle and Steinfeld, 2013). The SIS problem on NTRU lattice is to find a pair $({\mathbf{u}_{1}},{\mathbf{u}_{2}})\in {R_{q}^{2}}$ such that ${\mathbf{u}_{1}}+h\ast {\mathbf{u}_{2}}=0$ and $\| ({\mathbf{u}_{1}},{\mathbf{u}_{2}})\| $ ⩽ β, where β is $2\lambda s\sqrt{2N}$ + $4\sigma \sqrt{2N}$. According to the same probability analysis in Lyubashevsky (2012), since A can break our CBS scheme with non-negligible probability ε, we may construct the challenger C to solve the SIS problem with non-negligible probability$(1-{2^{-\omega (\log N)}})\varepsilon $. □
Theorem 2.
Let two hash functions ${H_{1}}$ and ${H_{2}}$ are random oracles controlled by a challenger in the EUF-CBS-ACMA game. If there exists an PPT adversary A (Type II adversary, honest-but-curious CA) with non-negligible probability ε who can break our CBS scheme from lattices, an algorithm C can be constructed to resolve the SIS problem from lattices with non-negligible probability $(1-{2^{-\omega (\log N)}})\varepsilon $, where N is the security parameter.
Proof.
Assume that N, q and λ are, respectively, a security parameter, a large prime and a positive integer while setting $1\leqslant d\leqslant 31$ and two standard deviations $s>0$ and $\sigma >0$. Assume that the algorithm C be a challenger in the EUF-CBS-ACMA game while receiving a random instance $(q,2N,2\lambda d\sqrt{2N}+4\sigma \sqrt{2N})$ of the SIS problem. In the following, we demonstrate that the challenger C may obtain a non-zero vector solution $({\mathbf{u}_{1}},{\mathbf{u}_{2}})\in {R_{q}^{2}}$ of the SIS problem if the adversary A with non-negligible probability ε who can break our CBS scheme.
-
– Setup. As the Setup algorithm in the proposed CBS scheme, C sets the public parameters $PP=\langle N,\lambda ,s,\sigma ,q,h,{p_{1}},{p_{2}},{H_{1}},{H_{2}}\rangle $, where ${H_{1}}$ and ${H_{2}}$ are random oracles. C also produces a short trapdoor basis B of the lattice ${\Lambda _{h,q}}$, which is viewed as the system private key ${S_{\mathit{CA}}}$. In the meantime, the system private key ${S_{\mathit{CA}}}$ and the public parameters $PP=\langle N,\lambda ,s,\sigma ,q,h,{p_{1}},{p_{2}},{H_{1}},{H_{2}}\rangle $ are sent to A. Initially, C constructs three empty lists ${L_{1}}$, ${L_{2}}$ and ${L_{S}}$.
-
– Queries. A may issue several queries to C adaptively as below:
-
• ${H_{1}}$ query: Let ${L_{1}}$ consist of tuples of the form $\langle {\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}},{C_{{\mathit{ID}_{i}}}},{T_{{\mathit{ID}_{i}}}}\rangle $. For the query along with $({\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}})$, C returns a response to this query by the following procedures.
-
1. Search $({\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}})$ in ${L_{1}}$. If the tuple is found, it means that this query has been already issued and the same answer ${T_{{\mathit{ID}_{i}}}}$ is sent to A.
-
2. Otherwise, randomly select ${T_{{\mathit{ID}_{i}}}}\in {Z_{q}^{N}}$ and perform $\mathbf{GauSample}(\mathbf{B},\mathbf{s},({T_{\mathit{ID}}},0))$ to get ${\mathbf{s}_{i3}},{\mathbf{s}_{i4}}\in {D_{s}^{N}}$ such that $\| ({\mathbf{s}_{i3}},{\mathbf{s}_{i4}})\| <s\sqrt{2N}$. Finally, the challenger C adds $\langle {\mathit{ID}_{i}},{P_{{\mathit{ID}_{i}}}},{C_{{\mathit{ID}_{i}}}}=({\mathbf{s}_{i3}},{\mathbf{s}_{i4}}),{T_{{\mathit{ID}_{i}}}}\rangle $ in ${L_{1}}$ and sends ${T_{{\mathit{ID}_{i}}}}$ to A.
-
-
• User key generation query: Let ${L_{S}}$ consist of tuples of the form $\langle {\mathit{ID}_{i}},{S_{{\mathit{ID}_{i}}}},{P_{{\mathit{ID}_{i}}}}\rangle $. For the query along with ${\mathit{ID}_{i}}$, C returns a response to this query by the following procedures.
-
1. Search ${\mathit{ID}_{i}}$ in ${L_{S}}$. If the tuple is found, it means that this query has been already issued and the same answer ${S_{{\mathit{ID}_{i}}}}=({\mathbf{s}_{i1}},{\mathbf{s}_{i2}})$ is sent to A.
-
2. Otherwise, randomly select ${\mathbf{s}_{i1}},{\mathbf{s}_{i2}}\in {\{-d,\dots ,0,\dots ,d\}^{N}}$, where $1\leqslant d\leqslant 31$, and compute the public key ${P_{{\mathit{ID}_{i}}}}=({p_{1}}\ast {\mathbf{s}_{i1}}+{p_{2}}\ast {\mathbf{s}_{i2}})$ Finally, C adds $\langle {\mathit{ID}_{i}},{S_{{\mathit{ID}_{i}}}},{P_{{\mathit{ID}_{i}}}}\rangle $ in ${L_{S}}$ and sends ${S_{{\mathit{ID}_{i}}}}=({\mathbf{s}_{i1}},{\mathbf{s}_{i2}})$ to A.
-
-
• Certificate extract query: As the response of User key generation query in Theorem 1.
-
• Corruption query: As the response of User key generation query in Theorem 1.
-
• Public key replacement query: A issues this query along with a new public key ${P^{\prime }_{{\mathit{ID}_{i}}}}$ of ${\mathit{ID}_{i}}$ to replace the old public key ${P_{{\mathit{ID}_{i}}}}$, C replaces the ${P_{{\mathit{ID}_{i}}}}$ of $\langle {\mathit{ID}_{i}},{S_{{\mathit{ID}_{i}}}},{P_{{\mathit{ID}_{i}}}}\rangle $ in ${L_{S}}$ with ${P^{\prime }_{{\mathit{ID}_{i}}}}$.
-
• Sign query: As the response of User key generation query in Theorem 1.
-
-
– Forgery. Finally, the adversary A generates a signature tuple (${\mathbf{z}_{1}^{\ast }},{\mathbf{z}_{2}^{\ast }},$ ${\mathbf{z}_{3}^{\ast }}$, ${\mathbf{z}_{4}^{\ast }},{\mathbf{c}^{\ast }})$ on some message ${m^{\ast }}$ for some ${\mathit{ID}^{\ast }}$.
Assume that A may generate a valid signature ${\rho ^{\ast }}=({\mathbf{z}_{1}^{\ast }},{\mathbf{z}_{2}^{\ast }},$ ${\mathbf{z}_{3}^{\ast }}$, ${\mathbf{z}_{4}^{\ast }},{\mathbf{c}^{\ast }})$. By the Forking lemma (Pointcheval and Stern, 2000), the challenger C can generate the other valid signature (${\mathbf{z}^{\prime }_{1}},{\mathbf{z}^{\prime }_{2}},{\mathbf{z}^{\prime }_{3}},{\mathbf{z}^{\prime }_{4}},{\mathbf{c}^{\prime }})$ such that ${\mathbf{c}^{\ast }}\ne {\mathbf{c}^{\prime }}$ by the same random tape with different hash value of ${H_{2}}$ query. Because (${\mathbf{z}_{1}^{\ast }},{\mathbf{z}_{2}^{\ast }},{\mathbf{z}_{3}^{\ast }},{\mathbf{z}_{4}^{\ast }},{\mathbf{c}^{\ast }}$) and (${\mathbf{z}^{\prime }_{1}},{\mathbf{z}^{\prime }_{2}},{\mathbf{z}^{\prime }_{3}},{\mathbf{z}^{\prime }_{4}},{\mathbf{c}^{\prime }})$ are two valid signatures on the message ${m^{\ast }}$ for (${\mathit{ID}^{\ast }}$, ${P_{{\mathit{ID}^{\ast }}}}$), we can obtain the equality
\[\begin{aligned}{}& {H_{2}}\big({m^{\ast }},{p_{1}}\ast {\mathbf{z}_{1}^{\ast }}+{p_{2}}\ast {\mathbf{z}_{2}^{\ast }}-{P_{{\mathit{ID}^{\ast }}}}\ast {\mathbf{c}^{\ast }},{\mathbf{z}_{3}^{\ast }}+h\ast {\mathbf{z}_{4}^{\ast }}-{T_{{\mathit{ID}^{\ast }}}}\ast {\mathbf{c}^{\ast }}\big)\\ {} & \hspace{1em}={H_{2}}\big({m^{\ast }},{p_{1}}\ast {\mathbf{z}^{\prime }_{1}}+{p_{2}}\ast {\mathbf{z}^{\prime }_{2}}-{P_{{\mathit{ID}^{\ast }}}}\ast {\mathbf{c}^{\prime }},{\mathbf{z}^{\prime }_{3}}+h\ast {\mathbf{z}^{\prime }_{4}}-{T_{{\mathit{ID}^{\ast }}}}\ast {\mathbf{c}^{\prime }}\big),\end{aligned}\]
which reduces to
\[ {p_{1}}\ast {\mathbf{z}_{1}^{\ast }}+{p_{2}}\ast {\mathbf{z}_{2}^{\ast }}-{P_{{\mathit{ID}^{\ast }}}}\ast {\mathbf{c}^{\ast }}={p_{1}}\ast {\mathbf{z}^{\prime }_{1}}+{p_{2}}\ast {\mathbf{z}^{\prime }_{2}}-{P_{{\mathit{ID}^{\ast }}}}\ast {\mathbf{c}^{\prime }}.\]
Since ${P_{{\mathit{ID}_{i}}}}={p_{1}}\ast {\mathbf{s}_{i1}}+{p_{2}}\ast {\mathbf{s}_{i2}}$, we have
\[\begin{aligned}{}& {p_{1}}\ast {\mathbf{z}_{1}^{\ast }}+{p_{2}}\ast {\mathbf{z}_{2}^{\ast }}-({p_{1}}\ast {\mathbf{s}_{i1}}+{p_{2}}\ast {\mathbf{s}_{i2}})\ast {\mathbf{c}^{\ast }}\\ {} & \hspace{1em}={p_{1}}\ast {\mathbf{z}^{\prime }_{1}}+{p_{2}}\ast {\mathbf{z}^{\prime }_{2}}-({p_{1}}\ast {\mathbf{s}_{i1}}+{p_{2}}\ast {\mathbf{s}_{i2}})\ast {\mathbf{c}^{\prime }};\\ {} & {p_{1}}\ast \big({\mathbf{z}_{1}^{\ast }}-{\mathbf{z}^{\prime }_{1}}\big)+{p_{2}}\ast \big({\mathbf{z}_{2}^{\ast }}-{\mathbf{z}^{\prime }_{2}}\big)-{p_{1}}\ast {\mathbf{s}_{i1}}\big({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}\big)-{p_{2}}\ast {\mathbf{s}_{i2}}\big({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}\big)=0;\\ {} & {p_{1}}\ast \big({\mathbf{z}_{1}^{\ast }}-{\mathbf{z}^{\prime }_{1}}-{\mathbf{s}_{i1}}\big({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}\big)\big)+{p_{2}}\ast \big({\mathbf{z}_{2}^{\ast }}-{\mathbf{z}^{\prime }_{2}}-{\mathbf{s}_{i2}}\big({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}\big)\big)=0;\\ {} & ({p_{1}},{p_{2}})\ast \big({\mathbf{z}_{1}^{\ast }}-{\mathbf{z}^{\prime }_{1}}-{\mathbf{s}_{i1}}\big({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}\big),{\mathbf{z}_{2}^{\ast }}-{\mathbf{z}^{\prime }_{2}}-{\mathbf{s}_{i2}}\big({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}\big)\big)=0.\end{aligned}\]
Afterward, C sets $({\mathbf{u}_{1}},{\mathbf{u}_{2}})=({\mathbf{z}_{1}^{\ast }}-{\mathbf{z}^{\prime }_{1}}-{\mathbf{s}_{i1}}({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}),{\mathbf{z}_{2}^{\ast }}-{\mathbf{z}^{\prime }_{2}}-{\mathbf{s}_{i2}}({\mathbf{c}^{\ast }}-{\mathbf{c}^{\prime }}))$.If we have $\| ({\mathbf{z}_{1}^{\ast }}-{\mathbf{z}^{\prime }_{1}},{\mathbf{z}_{2}^{\ast }}-{\mathbf{z}^{\prime }_{2}})\| \leqslant 4\sigma \sqrt{2N}$ and $\| ({\mathbf{s}_{1}},{\mathbf{s}_{2}})\| \leqslant 2d\lambda \sqrt{2N}$ with overwhelming probability, we can obtain $\| ({\mathbf{u}_{1}},{\mathbf{u}_{2}})\| \leqslant 2d\lambda \sqrt{2N}+4\sigma \sqrt{2N}$. As stated in Lemma 3, the distribution of $h=g/f$ is statistically close to the uniform distribution of ${R_{q}}$ (Stehle and Steinfeld, 2013). The SIS problem on NTRU lattice is to find a pair $({\mathbf{u}_{1}},{\mathbf{u}_{2}})\in {R_{q}^{2}}$ such that ${\mathbf{u}_{1}}+h\ast {\mathbf{u}_{2}}=0$ and $\| ({\mathbf{u}_{1}},{\mathbf{u}_{2}})\| \leqslant beta$, where β is $2d\lambda \sqrt{2N}+4\sigma \sqrt{2N}$. According to the same probability analysis in Lyubashevsky (2012), since A can break our CBS scheme with non-negligible probability ε, we may construct the challenger C to solve the SIS problem with non-negligible probability $(1-{2^{-\omega (\log N)}})\varepsilon $. □
6 Comparisons
Table 1 lists the comparisons between Tian and Huang’s CBS scheme (Tian and Huang, 2015) and our CBS scheme in terms of lattice type, private key size/bit-length and signature size/bit- length. For the generation of a user’s private key, Tian and Huang’s CBS scheme adopted the GPV lattice in Gentry et al. (2008), instead, our proposed CBS scheme employed Ducas et al.’s sampling algorithm over NTRU lattices (Ducas et al., 2014). For both the private key size and signature size under the same security parameters N=512, $q\approx {2^{26}}$, $k=512$, $\lambda =14$ and $d=31$, our scheme is better than those of Tian and Huang’s CBS scheme. By Lyubashevsky (2012), we have ${n_{1}}>2N\log q$, ${n_{2}}>64+N\log q$, ${s_{1}}=\sqrt{{n_{1}}}\omega (\sqrt{\log N})$, ${s_{2}}=\sqrt{{n_{2}}}\omega (\sqrt{\log N})$, ${\sigma _{1}}=12{s_{1}}\lambda {n_{1}}$, ${\sigma _{2}}=12{s_{2}}\lambda {n_{2}}$, $s={N^{5/2}}\sqrt{2q}\omega (\sqrt{\log N})$, $\sigma =12s\lambda N$ while choosing ${n_{1}}=38400$ and ${n_{2}}=25600$. According to Table 1, our scheme is much better than Tian and Huang’s CBS scheme in terms of private key and signature sizes.
Table 1
Comparisons between Tian and Huang’s CBS scheme and ours.
| Tian and Huang’s CBS scheme (Tian and Huang, 2015) | Our CBS scheme | |
| Lattice type | GPV lattice | NTRU lattice |
| Private key size | $2{n_{1}}k\log ({s_{1}}\sqrt{{n_{1}}})+2{n_{2}}k\log ({s_{2}}\sqrt{{n_{2}}})$ | $4N\log (s\sqrt{N})$ |
| Private key bit-length | 595222811 | 85166 |
| Signature size | ${n_{1}}\log (12{\sigma _{1}})+{n_{2}}\log (12{\sigma _{2}})+\lambda (\log k+1)$ | $4N\log (12\sigma )+\lambda (\log N+1)$ |
| Signature bit-length | 675496 | 87161 |
7 Conclusions
Lattice-based cryptography is an important candidate for post-quantum cryptography. In the paper, a new and efficient CBS scheme from lattices was proposed, which possesses the merits of both CBS scheme and lattice-based cryptography. Based on the SIS assumption from lattices and in the random oracle model, we formally demonstrated the security of our lattice-based CBS scheme against Type I adversary (general attackers) and Type II adversary (the honest-but-curious CA), namely, achieving existential unforgeability against adaptive chosen message attacks for both adversaries. Comparisons with the previous CBS schemes from lattices were given to demonstrate the merits of our proposed CBS scheme in terms of private key size and signature size.
