Keywords

1 Introduction

Digital signature schemes are very important and significant primitives for constructing secure systems and are used in most of real world applications and security protocols. The proxy signature scheme is a kind of digital signature scheme firstly proposed by Mambo et al. [12] in 1996. It can be widely used in different situations, such as e-election, cloud computing, e-commerce etc. In proxy signature scheme, an original signer can delegate his signing rights to a proxy signer to sign on any document for a period of time. The proxy signer constructs a proxy private key by using the information given to him. Then he can use his signing rights to sign any document with his proxy private key by using a normal digital signature scheme. After getting the message and signatures from proxy signer, the verifier gets the public proxy key and verifies the correctness of signatures by using a normal digital signature scheme. After the concept of a proxy signature scheme proposed by Mambo et al., many effective proxy signature schemes [9, 10, 17, 22, 25, 27] etc. have been proposed by researchers based on discrete logarithmic problem (DLP). In 2007, Y.S. Kim and J.H. Chang [8] proposed a new type of digital signature scheme using DLP and they called it self proxy signature scheme. The idea behind self proxy signature is to keep the private key secret and generate temporary proxy keys to sign on any document on behalf of original key. So, in a self proxy signature scheme, a user Alice can delegates her signing rights to herself recursively. By using a self proxy signature scheme, the user Alice can generate many proxy public and private key pairs and can use them simultaneously. He can revoke the temporary private and public keys pair easily. Due to this fact, Kim et al. [8] considered their self proxy signature scheme for practical purposes and secure since their scheme satisfies all the security requirements of a proxy signature scheme. But, due to Shor’s algorithm [18, 19], schemes based on DLP are not safe against quantum computers. Additionally, this scheme was analysed later in 2012 by S. Mashhadi [14, 24]. They showed that an adversary can forge a valid self proxy signature for any message by using different ways and proposed an improvement to remove the pointed out security leaks in Kim et al.’s scheme. After Kim et al. [8] scheme, several self proxy schemes have been proposed . As like, in 2010, Salevi et al. proposed ID Based self proxy signatures [16]. They gave a formal security model for identity based self proxy signatures and showed that the scheme by Kim et al. [8] is existentially forgeable. They proposed a generic identity based self proxy signature scheme and proved the security in random oracle assumption. Later, in 2012, V. Verma also gave identity based version of a self proxy signature scheme with warrant [23]. Later, in 2013, Tahat et al. [21] proposed an efficient self proxy signature scheme based on ECDLP(elliptic curve discrete logarithm problem). They claimed that their scheme require less number of operations than Mashhadi scheme [14] and so is more efficient than Mashhadi scheme. The discrete logarithm problem is no more intractable after the quantum computers become reality. Therefore it is quite better to construct a scheme based on lattices, since lattices are considered as the best and strongest candidate for post quantum cryptography. The cryptographic schemes based on lattices are supported by worst case hardness assumption and Bernstein’s conjuncture [1] that lattice can withstand quantum attacks. The running time of lattice based scheme are quadratic polynomial in respect of cubic polynomial of DLP and Factoring based scheme. The NTRU lattices [4,5,6,7] are better than general lattices. With general lattices, a scheme can suffer with large key sizes and large signature sizes. By motivating and considering all these facts, here, we are proposing a self proxy signature scheme relies on NTRU lattices in this paper and prove that it holds all the security requirements like distinguishability, unforgeability, verifiability and undeniabilty.

Rest of the sections in this paper is organized as follows. In Sect. 11.2, we give some required preliminaries used in our proposed scheme and then some related work (Kim and Chang self proxy scheme) is described in Sect. 11.3. The proposed self proxy signature scheme over NTRU lattices is given in Sect. 11.4. In Sect. 11.5, we provide a formal security proof for our scheme. Finally, in section 5 we conclude the paper.

2 Preliminaries

2.1 Notations

We will use the following notations throughout the paper-N is being security parameter and some power of 2. R is a polynomial ring \( \frac {Z[X]}{X^N+1} \). The polynomials in ring R have degree N − 1. Rq is a polynomial ring R with coefficients in Zq i.e. \( \frac {Z_q[X]}{X^N+1} \). q is a large modulus to which each coefficient is reduced. The polynomial f is the NTRU’s private key polynomial and g is a polynomial used for generating the public key of NTRU cryptosystem [5, 6] from its private key f. The operation ⋆  is convolution multiplication operation. The polynomial h is NTRU’s public key, given by \( h = f_q^{-1} \star g \) mod q. ||x|| denotes the Euclidean norm of x and ||x||1 is l1 − norm which is given by \( || x ||{ }_1 = \sum _{i=1}^N | x |{ }_i \).

2.2 Definitions

We are giving some definitions that are very useful in this article.

Definition 1 (Self Proxy Signature Scheme)

A self proxy signature scheme consists of the following algorithms—(assume Alice is the signer and Bob is the verifier.)

  1. 1.

    Setup: In this algorithm, Alice generates her private and public key pair as in a normal digital signature scheme.

  2. 2.

    ProxyKeyGen: Here, Alice constructs her temporary self proxy private and public key pair for a given time period. She publishes the proxy public key publicly available and can be revoked publicly.

  3. 3.

    SelfProxySignGen: The signer Alice here generates the signature on a message by using her private self proxy key and sends the signature and message pair to a verifier.

  4. 4.

    SelfProxysignVfy: The verifier Bob (say) using public proxy key checks the signature and message for verification.

Definition 2 (Secure Self Proxy Signature Scheme)

A self proxy signature scheme is called secure if it satisfies following properties.

  1. 1.

    Undeniability: According to this property, a signer can not repudiate that he signed the document.

  2. 2.

    Verifiability: According to this property, a self proxy signature should be verified by anyone.

  3. 3.

    Unforgeability: No one can generate the valid self proxy signature except the original signer.

  4. 4.

    Distinguish-ability: The self proxy signatures should be distinguishable from normal signatures.

Definition 3 (NTRU Lattice)

The NTRU lattice related to h and q is a full rank lattice in \( \mathbb {Z}^{2N} \), given by

$$\displaystyle \begin{aligned} L_{h,q}=\{(u, v) : u + v \star h = 0 \ mod \ q \}. \end{aligned}$$

The NTRU lattices are generated by the rows of the matrix

$$\displaystyle \begin{aligned} A_{h,q} = \begin{bmatrix} \mathcal{A}_{N,q}(h) & I_N \\ qI_N & O_N \end{bmatrix} \end{aligned}$$

where \(\mathcal {A}_N(h)\) is an anti-circulant matrix whose ith row contains of the coefficients of the polynomial hxi mod .

2.3 Gaussian on Lattices

Discrete Gaussian Distribution: Gaussian sampling is a method given by Gentry et al. [3] to use a short basis as a trapdoor without revealing any information about the short basis. The N − dimensional Gaussian distribution

$$\displaystyle \begin{aligned} \rho_{s,c}(x) = e^{- \pi \frac{||(x-c)||{}^2}{s^2}} \end{aligned}$$

where s ∈ Rm is standard deviation and vector c ∈ Zm is center.

For any lattice L, ρs,c(L) =∑x ∈ L ρs,c(x). The probability mass function of the discrete Gaussian distribution is DL,s,c(x) = ρs,c(x)/s,c(L).

Some Important Results about discrete Gaussian distribution [ 11 , 15 ]:

  1. 1.

    For a real positive α and any v ∈ Zm, if \( \sigma = \omega (||v||\sqrt {log m}) \), then

    $$\displaystyle \begin{aligned} \text{Pr}[ x \leftarrow D_\sigma^m : \frac{D_\sigma^m(x)}{D_{\sigma,\upsilon}^m (x)} < e^{\frac{12}{\alpha} + \frac{1}{2 \alpha^2}}] = 1-2^{100} \end{aligned}$$

    where ω(.) is the non-asymptotic tight lower bound. If σ = α||v||, then

    $$\displaystyle \begin{aligned} \text{Pr}[ x \leftarrow D_\sigma^m : \frac{D_\sigma^m(x)}{D_{\sigma, \upsilon}^m (x)} = O(1)] = 1-2^{\omega(logm)} \end{aligned}$$
  2. 2.

    For any σ > 0 and positive integer m,

    $$\displaystyle \begin{aligned} \text{Pr}[ x \leftarrow D_\sigma^1 : ||x|| > 12 \sigma ] < 2^{-100} \end{aligned}$$
    $$\displaystyle \begin{aligned} \text{Pr}[ x \leftarrow D_\sigma^m : ||x|| > 2 \sigma \sqrt{m}] < 2^{-m} \end{aligned}$$
  3. 3.

    For given any N −dimensional lattice L, center c ∈ RN, ε > 0 and s > 2ηε(L), for any x ∈ L,

    $$\displaystyle \begin{aligned} D_{L,s,c}(x) \leq \frac{1+\varepsilon}{1-\varepsilon} 2^{-N} \end{aligned}$$

    where 2ηε(L) is the smoothing parameter of lattice L.

2.4 Master Key Generation

Master key generation algorithm is the most important part of a lattice based signature scheme because it generates secret keys. It works as follows:___________________________________________Algorithm-1 MasterKeyGen(N, q)___________________________________________Input : N, q ∈ Z, σ > 0Output : \( (msk,mpk) \in R^{2N \times 2N} \times R_q^\star \)1 Sample f and g from \( D_{Z^N, \sigma } \)2 if \( ||f||> \sigma \sqrt {N} \) or \( ||g||> \sigma \sqrt {N} \) or f ( mod \( q) \notin R_q^\star \) or g ( mod \( q) \notin R_q^\star \) then3 Restart4 end if5 if max( \( ||( g, -f )||, ||(\frac {g \overline {f}}{f \overline {f} + g \overline {g}})|| ) > 1.17 \sqrt {g} \) then6 Restart 7 end if8 Define \( \rho _f = \prod _{i=2}^{n-1} f(x^i)\) mod (xN + 1) and ρg similarly.9 Compute kf and kg satisfy ρf f + kf(xN + 1) = Rf, ρg f + kg(xN + 1) = Rg where Rf = resultant(f, xN + 1), Rg = resultant(g, xN + 1)10 if (Rf, Rg) ≠ 1 then11 Restart12 end if13 Find α and β satisfy αRf + βRg = 1 by extended Euclidean algorithm i.e. (αρf)f + (βρg)g = 1 + k(xN + 1)14 Let F = qβρg, G = qαρf, then f ⋆ G − g ⋆ F = q.15 return KGC’s public key mpk = h = f−1 g, KGC’s secret keys msk as

$$\displaystyle \begin{aligned} msk = B = \begin{bmatrix} \mathcal{A}(g) & -\mathcal{A}(f) \\ \mathcal{A}(G) & -\mathcal{A}(F) \\ \end{bmatrix} \end{aligned}$$

where \( \mathcal {A}(g) \), \( -\mathcal {A}(f) \), \( \mathcal {A}(G) \), \( -\mathcal {A}(F) \) are anti-circulant matrices whose ith row contains the coefficients of the polynomial gxi mod (XN + 1), fxi mod (XN + 1), Gxi mod (XN + 1) and Fxi mod (XN + 1), respectively.__________________________________Note. In our proposed scheme, we are assuming KGC as signer Alice itself.

2.5 Hardness Assumption

Our signature scheme relies on small integer solution (SIS) problem and approximate shortest vector problem over NTRU lattices.

Definition 4 (SIS (Small Integer Solution) Problem Over Ring)

\( R (SIS_{q,m, \beta }^{\phi }) \). With the parameters q, m, ϕ and β, SIS problem can be defined as—If we are given m uniformly and independently chosen polynomials a1, a2, …, am in Rq, then to find non-zero \( t \in \overline {a} \) satisfying the conditions ||t||≤ β where \( \overline {a} = \{ (t_1,t_2,\ldots ,t_m) \in R^m \) such that ∑i ti ai = 0 mod q}.

Definition 5 (SIS Problem Over NTRU Lattices)

\((SIS_{q,1,2,\beta }^{\kappa }) \). Stehle and Steinfeld [20] showed that statistical distance between R∗ and the distribution of \( h=\frac {g}{f} \) is 210N q−⌊𝜖N⌋, which is negligible.

For SIS problem on NTRU lattice, set \( R = \frac {Z[x]}{x^{N+1}} \) and let κ be distribution that chooses small f and g according to sampling algorithm Sampler(B, σ, c), \( A_{h,q} = (h,1) \in R_{q}^{1 \times 2} \) and \( h=\frac {g}{f} \). The problem is to find (z1, z2) that satisfies the conditions Ah,q(z1, z2)T = 0 mod q and ||(z1, z2)||≤ β.

Definition 6 (γ Approximate Shortest Vector Problem)

(γ − SVP). For the NTRU lattice Lh,q generated by the basis Ah,q, the shortest vector problem is to find the vector (u, v) ∈ Lh,q such that ||(u, v)||≤||(s, t)||, (s, t) ∈ Lh,q. So, γ − SVP is to find the vector (u, v) ∈ Lh,q such that ||(u, v)||≤ γλ1 Lh,q, where λ1 Lh,q is the successive minimum of Lh,q.

Remark 1

According to the definitions of γ − SVP and \( (SIS_{q,1,2,\beta }^{\kappa }) \), smallest integer solution problem is equal to the approximate shortest vector problem when \( \frac {\beta }{\lambda _1 L_{h,q}} = \gamma \). Hence, our proposed scheme relies on the hardness of approximate shortest vector problem on the NTRU lattices against polynomial time algorithms and approximate shortest vector problem γ −SVP is a NP-hard problem with γ < 1 + 1/n𝜖 [2].

3 The Proposed Self Proxy Signature Over NTRU Lattice

We are presenting here a new self proxy signature scheme over NTRU lattices. Only two candidates are participating in the proposed self proxy signature scheme, an original signer Alice and a verifier Bob. The proposed scheme have three probabilistic polynomial time algorithms, Setup, SelfProxySignKeyGen, SelfProxySignGen and a deterministic algorithm SelfProxySignV fy algorithm. The underlying hardness of the proposed scheme is the hardness of γ −SVP and SIS problem over NTRU lattices. These algorithms are as follows :

  1. 1.

    Setup (N): Here we consider the same parameter setup as given in [26]. On input of the security parameter N, this algorithm outputs the public parameters as follows:

    Let q =  Poly( N)(q ≥ 3), \( \varepsilon \in \big ( 0, \frac {ln N}{ln q} \big ), s = \Omega (N^{3/2} \sigma ) \), where Ω(.) is the asymptotic lower bound and Poly(N) is the polynomial function of security parameter N. Then,

    1. 1.

      Choose two hash functions \( H_1 : \{0,1\}^\star \rightarrow Z_q^{N \times k} \) and H2 : {0, 1}⋆ →{v : v ∈{−1, 0, 1}k, ||v||1 ≤ k}(k being a positive integer).

    2. 2.

      Run the algorithm MasterKeyGen to generate system’s master key (msk, mpk).

    3. 3.

      Public parameters of our proxy signature system are (N, q, H1, H2).

    The signer Alice computes t = H1(IDA), where IDA is Alice’s identity and sets her private signing key SK = (S1, S2) such that S1 + S2 ⋆ h = t by using master secret key msk and applying Sampler(B, σ, (t, 0)).

  2. 2.

    SelfProxySignKeyGen: In this phase, signer Alice constructs a message warrant W and the temporary self proxy signing private and public key pair with her original signing key SK = (S1, S2) as follows:

    Alice construct a warrant W consists of public key of signer Alice and a valid time period T i.e. W = (PK, T).

    For constructing self proxy keys, Alice first chooses \( r_1, r_2 \in _R Z_q^{N \times k} \) randomly and computes r1 + r2 ⋆ h = u and makes u is a public quantity. Then, she sets her self proxy private signing key SKsp = (S3, S4) with S3 = S1 tH1(W) − r1 and S4 = S2 tH1(W) − r2. The self proxy signing public key is PKsp = t2 H1(W) − u.

  3. 3.

    SelfProxySignGen: Let m be the message to be signed. The self proxy signature on message m is generated as follows.

    1. 1.

      Randomly select \( y_1, y_2 \in D_{Z^N,~\sigma } \).

    2. 2.

      Compute U = H2(y1 + y2 h, m)

    3. 3.

      Now, the signer computes Z1 = S3 U + y1 and Z2 = S4 U + y2.

    4. 4.

      The signer generates the triplets (Z1, Z2, U) with probability \( min \big ( \dfrac {D_{Z^N,~\sigma }}{M D_{Z^N,~\sigma , SK_{sp}U}}, 1 \big ) \), where M = O(1).

    5. 5.

      Now, As a result, (W, Z1, Z2, U) is defined as the self proxy signature on message m of signer Alice by using temporary self proxy signing key.

  4. 4.

    SelfProxySignVefy: Now, after obtaining self proxy signature from the signer, the verifier verifies the signature in the following manner.

    1. 1.

      Obtain the public key of signer from the public ID board.

    2. 2.

      Verify whether \( ||Z_1,Z_2|| \leq 2s \sqrt {2N} \) and H2(hZ2 + Z1 − [t2 − u]H1(W)U, m) = U holds or not. If holds, then accept the signature as a valid signature, otherwise reject it.

Correctness: The correctness of the scheme is given as follows hZ2 + Z1 − [t2 H1(W) − u]U= h(S4 U + y2) + (S3 U + y1) − [t2 H1(W) − u]U= hS4 U + hy2 + S3 U + y1 − [t2 H1(W) − u]U= (hS4 + S3)U + (hy2 + y1) − [t2 H1(W) − u]U= [(hS2 t + S1 t)H1(W) − (r2 ⋆ h + r1)]U + (hy2 + y1) − [t2 H1(W) − u]U= [(hS2 + S1)tH1(W) − u]U + (hy2 + y1) − [t2 H1(W) − u]U= [t2 H1(W) − u]U + (hy2 + y1) − [t2 H1(W) − u]U= (hy2 + y1)Hence, H2(hZ2 + Z1 − [t2 H1(W) − u]U, m) = U.

By combining the results of [11], the distribution of Zi is very close to \( D_{Z^N,s} \). Therefore, we have \( ||Z_i||< 2s\sqrt {N} \) by the result of [15] with a probability of at least 1 − 2N. Hence, the inequality \( ||Z_1,Z_2|| \leq 2s \sqrt {2N} \) is with an overwhelming probability.

4 Security Analysis

In this section we describe that the proposed scheme satisfies all security properties of a self proxy signature scheme.

Theorem 1

The proposed self proxy signature scheme entertains the unforgeability property.

Proof

The proposed self proxy signature scheme relies on SIS problem ( or in particular γ − SV P). The security against forgeability is explained as follows :

We are assuming that an attacker wants to forge the self proxy signature. He can mount attack on the scheme in two manners—the first manner is to compute the private self proxy key SKsp, and the second manner is to forge the valid self proxy signature without the self proxy private key. In the first way, the attacker has to compute SKsp from PKsp or to generate SKsp with the help of the information (W, Z1, Z2, U) that is transferred from signer to verifier. Howbeit, it is computationally difficult to compute SKsp from PKsp or from (W, Z1, Z2, U) because it is SIS problem over NTRU lattices. Therefore, it is computationally hard to compute SKsp for the attacker. In the second manner, the attacker has to get the valid signature (Z1, Z2, U) on the message document m without the private key SKsp. Since the second condition for verification is also a SIS problem over NTRU lattices, so attacker has to solve SIS problem to forge the signature [26].

Since both the two attacks are not viable, therefore, it is computationally difficult to the attacker to forge the self proxy signature. Therefore, the proposed scheme holds the unforgeability property. □

Theorem 2

The self proxy signature scheme satisfies the undeniability property.

Proof

As the requirement of undeniability property, the signer can not repudiate the valid message and its signature. In our proposed self proxy signature scheme, at the time of verification of the self proxy signature (W, Z1, Z2, U), the warrant W is also checked, and the publicly available information t2 and u of the proxy signer and the master’s public key h are used in the verification step. Therefore, the signer can not deny after signing on any message. □

Theorem 3

The self proxy signature scheme holds the distinguish-ability property.

Proof

In the proposed self proxy signature scheme, the signer’s identity, temporary public key and message warrant are used at the verification step of the self proxy signature (W, Z1, Z2, U). Thus, we can assume it as a self proxy signature instead of a normal signature. Hence, anyone can distinguish the self proxy signatures from normal signatures. If the signer sign the document with his original keys, the verification process will not hold. Therefore, the proposed signature scheme holds the distinguish-ability property. □

Theorem 4

The proposed self proxy signature scheme entertains the verifiability property.

Proof

A scheme is said to be verifiable if the verifier can be assured of the signer’s agreement on the signed message. In the proposed scheme, the verification phase is done with the help of the signer’s identity and temporary public key. Therefore, any verifier can verify the signer’s agreement on the signed message. Moreover, the verifier can recover the self proxy public key by public information. Hence, the proposed scheme satisfies the verifiability property. □

5 Conclusion

We proposed a new self proxy signature over NTRU lattices which is secure against quantum computer. Using this scheme, a user can delegate his signing right to himself for a period of time. The signer can have several ephemeral public and private key pairs and use them simultaneously. Our signature scheme is secure because it entertains all the security properties—verifiability, undeniability, distinguish-ability and unforgeability of a proxy signature scheme.