Abstract
In this paper we propose a signature scheme based on two intractable problems, namely the integer factorization problem and the discrete logarithm problem for elliptic curves. It is suitable for applications requiring long-term security and provides smaller signatures than the existing schemes based on the integer factorization and integer discrete logarithm problems.
Access provided by Autonomous University of Puebla. Download chapter PDF
Similar content being viewed by others
Keywords
- Digital signature
- Integer factorization
- Elliptic curve discrete logarithm
- Supersingular elliptic curves
- Pairing
- Map to point function
- Long-term security
1 Introduction
Many applications of the Information Technology, such as encryption of sensitive medical data or digital signatures for contracts, need long-term cryptographic security. Unfortunately, today’s cryptography provides strong tools only for short-term security [5]. Especially, digital signatures do not guarantee the desired long-term security. In order to achieve this goal Maseberg [20] suggested the use of more than one sufficiently independent signature schemes. Thus, if one of them is broken, then it can be replaced by a new secure one. Afterward the document has to be re-signed. Again we have more than one valid signatures of our document. Of course, a drawback of the method is that the document has to be re-signed.
In order to avoid this problem, it may be interesting for applications with long-term, to base the security of cryptographic primitives on two difficult problems, so if any of these problems is broken, the other will still be valid and hence the signature will be protected. We propose in this paper an efficient signature scheme built taking into account this constraint. The following signature scheme is based on the integer factorization problem and the discrete logarithm problem on a supersingular elliptic curve. Remark that these two problems have similar resistance to attack, thus they can coexist within the same protocol. The use of a supersingular curve allows us to easily build a pairing that we use to verify the signature.
Several signature schemes combining the intractability of the integer factorization problem and integer discrete logarithm problem were proposed but they have proved either to be enough to solve the one of two problems for breaking the system or to have other security problems [6, 9, 16–19, 22, 27]. An interesting scheme based on the above problems is GPS [8]. Furthermore, some recent such schemes are given in [12, 13, 19, 24, 25, 27].
In Sect. 2 we describe the infrastructure for the implementation of the scheme. Then we present the key generation, the generation of a signature and the verification. In Sect. 3 we show how to build an elliptic curve adapted to the situation and how to define a valuable pairing on it. In Sect. 4 we address the problem of the map to point function and give a practical solution. We deal with the performance of our scheme and compare it with others in Sect. 5. In Sect. 6 we give a complete example that shows that the establishment of such a system can be made in practice. In Sect. 7 we study the security of the scheme. Finally Sect. 8 concludes the paper.
2 The Proposed Signature Scheme
In this section we present our signature scheme.
2.1 Public and Private Key Generation
A user \(\mathcal{A}\), who wants to create a public and a private key selects:
-
1.
primes p 1 and p 2 such that the factorization of \(n = p_{1}p_{2}\) is unfeasible;
-
2.
an elliptic curve E over a finite field \(\mathbb{F}_{q}\), a point \(P \in E(\mathbb{F}_{q})\) with ord(P) = n and an efficiently computable pairing e n such that e n (P, P) is a primitive nth root of 1;
-
3.
g ∈ { 1, …, n − 1} with \(\gcd (g,n) = 1\), a ∈ { 1, …, ϕ(n) − 1} and computes Q = g a P;
-
4.
two one-way, collision-free hash functions, \(h:\{ 0,1\}^{{\ast}}\rightarrow \{ 0,\ldots,n - 1\}\) and \(H:\{ 0,1\}^{{\ast}}\rightarrow <P>,\) where < P > is the subgroup of \(E(\mathbb{F}_{q})\) generated by P.
\(\mathcal{A}\) publishes the elliptic curve E, the pairing e n , and the hash functions h and H. The public key of \(\mathcal{A}\) is (P, Q, g, n) and his private key \((a,p_{1},p_{2})\).
2.2 Signature Generation
The user \(\mathcal{A}\) wants to sign a message m ∈ { 0, 1}∗. Then he chooses at random k, l ∈ { 1, …, ϕ(n) − 1} such that \(k + l = a\). Next, he computes
Let x(S) be the x-coordinate of S and b a bit determining S. The signature of m is (s, x(S), b).
2.3 Verification
Suppose that (s, x, b) is the signature of m. The receiver uses b in order to determine y such that S = (x, y) is a point of \(E(\mathbb{F}_{q})\). He accepts the signature if and only if
Proof of Correctness of Verification.
Suppose that the signature (x, s, b) is valid and S = (x, y) is a point of \(E(\mathbb{F}_{q})\). Then we get
Suppose now we have a couple (s, S), where s ∈ { 1, …, ϕ(n)} and S ∈ < P > , such that
Since H(m), S ∈ < P > , there are u, v ∈ { 0, …, n − 1} such that S = uP and H(m) = vP. Thus we get
The element e n (P, P) is a primitive nth root of 1 and so, we obtain
Putting \(l = a + h(m) + n - s\ \mathrm{mod}\ \phi (n)\) and \(k = a - l\ \mathrm{mod}\ \phi (n)\), we get
It follows that (s, x(S), b) is the signature of m (where b is a bit determining S).
3 The Elliptic Curve and the Pairing
In this section we show how we can construct an elliptic with the desired properties in order to implement our signature scheme. This task is achieved by the following algorithm:
-
1.
select two large prime numbers p 1 and p 2 such that the factorization of p 1 − 1, p 2 − 1 are known and the computation of the factorization of \(n = p_{1}p_{2}\) is unfeasible;
-
2.
select a random prime number p and compute m = ord n (p);
-
3.
find, using the algorithm of [4], a supersingular elliptic curve E over \(\mathbb{F}_{p^{2m}}\) with trace t = 2p m;
-
4.
return \(\mathbb{F}_{p^{2m}}\) and E.
Since the trace of E is t = 2p m, we get \(\vert E(\mathbb{F}_{p^{2m}})\vert = (p^{m} - 1)^{2}\). On the other hand, we have m = ord n (p), whence n | p m − 1, and so n is a divisor of \(\vert E(\mathbb{F}_{p^{2m}})\vert\). Therefore \(E(\mathbb{F}_{p^{2m}})\) contains a subgroup of order n.
By Bróker [4, Theorem 1.1], we obtain, under the assumption that the Generalized Riemman Hypothesis is true, that the time complexity of Step 3 is \(\tilde{O}((\log p^{2m})^{3})\). Furthermore, since the factorization of \(\phi (n) = (p_{1} - 1)(p_{2} - 1)\) is known, the time needed for the computation of m is \(O((\log n)^{2}/\log \log n)\) [15, Section 4.4].
For the implementation of our signature scheme we also need a point P with order n and an efficiently computable pairing e n such that e n (P, P) is a primitive nth root of 1. The Weil pairing does not fulfill this requirement and also, in many instances, the Tate pairing; the same happens for the eta pairing (the eta and omega pairings can be computed only on the ordinary elliptic curves) [1, 10, 28]. Let ε n be one of the previous pairings on E[n]. Following the method introduced by Verheul [23], we use a distortion map ϕ such that the points P and ϕ(P) is a generating set for E[n] and we consider the pairing \(e_{n}(P,Q) =\epsilon _{n}(P,\phi (Q)).\) The algorithm of [7, Section 6] provides us a method for the determination of P and ϕ.
Another method for the construction of the elliptic curve E which is quite efficient in practice is given by the following algorithm:
-
1.
draw at random a prime number p 1 of a given size l (for example, l is 1024 bits);
-
2.
draw at random a number p 2 of size l;
-
3.
repeat p 2 = NextPrime(p 2) until \(4p_{1}p_{2} - 1\) is prime;
-
4.
return \(p = 4p_{1}p_{2} - 1\).
It is not proved that this algorithm will stop with a large probability. This is an open problem which is for p 1 = 2 the Sophie Germain number problem. But in practice we obtain a result p which is a prime of length 2l.
Since p ≡ 3 (mod 4), the elliptic curve defined over \(\mathbb{F}_{p}\) by the equation
where − a is not a square in \(\mathbb{F}_{p}\), is supersingular with \(p + 1 = 4p_{1}p_{2}\) points. By Vladut [26, Theorem 2.1], the group \(E(\mathbb{F}_{p})\) is either cyclic or \(E(\mathbb{F}_{p}) \simeq \mathbb{Z}/2p_{1}p_{2}\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}\). In each case the group \(E(\mathbb{F}_{p})\) has only one subgroup of order \(n = p_{1}p_{2}\), and this subgroup is cyclic.
If ε n is one of the Weil, Tate, or eta pairings on E[n], then we use the distortion map \(\phi (Q) =\phi (x,y) = (-x,iy)\) with \(i^{2} = -1\) (cf. [14]) and so, we obtain the following pairing: \(e_{n}(P,Q) =\epsilon _{n}(P,\phi (Q)).\)
4 The Map to Point Function
Let G be the subgroup of order \(n = p_{1}p_{2}\) of \(E(\mathbb{F}_{q})\) introduced in the previous section. In order to sign using the discrete logarithm problem on this group, we have to define a hash function into the group G, namely a map to point function. This problem was studied by various authors giving their own method, for example in [3] or [11]. We give here the following solution. Let us denote by \(\vert n\vert = \lfloor \log _{2}(n)\rfloor + 1\) the size of n. Let h be a key derivation function, possibly built using a standard hash function. We recall that h maps a message M and a bitlength l to a bit string h(M, l) of length l. Moreover we will suppose that h acts as a good pseudo-random generator. Let Q be a generator of the group G. Let us denote by \((T_{i})_{i\geq 0}\) the sequence of bit strings defined by T 0 = 0 and for i ≥ 1
where \(i =\sum _{ j=0}^{u}a_{j}2^{j}\) and a u = 1.
To map the message m to a point H(m) we run the following algorithm:
i: = 0;
Repeat
k: = h(m | | T i , | n | );
\(i:= i + 1\);
Until k < n;
Output H(M) = k. Q;
This Las Vegas algorithm has a probability zero to never stop. In practice this algorithm stops quickly, namely as \(2^{\vert n\vert -1} <n <2^{\vert n\vert }\) then the expected value of the number of iterations is < 2. If one can find a collision for H it is easy to find a collision for h.
5 Performance Analysis
In this section we analyze the performance of our scheme. The computation of s requires two additions modulo ϕ(n). The computation of S needs a modular exponentiation g l (mod n) and the computations of H(m) and g l H(m). Note that the computation of g l mod n and k + n mod ϕ(n) can be done off-line. Thus, the signature generation requires only a modular addition and a point multiplication on the elliptic curve. The signature verification needs two modular exponentiations, two points multiplications on the elliptic curves, and two pairing computations. Moreover note that the length of the signature of a message is the double of its length.
The signature generation in the GPS scheme [8] needs only one modular exponentiation and the signature verification two. The signature length is the triple of the message length. The most efficient of the schemes given in [12, 13, 19, 24, 25, 27] requires three modular exponentiations for the signature generation and four modular exponentiations for the signature verification. The signature length of the above schemes is larger than the double of the message length.
Hence we see that the signature length in our scheme is smaller than that in GPS and the other schemes. Moreover, the performance of the proposed algorithm is competitive to the performance of the above schemes.
6 Example
In this section we give an example of our signature scheme. We consider the 1024-bits primes
and
We take \(n = p_{1}p_{2}\). The number \(q = 4n - 1\) is a prime. Since q ≡ 3 (mod 4), the elliptic curve E defined by the equation \(y^{2} = x^{3} + x\) over \(\mathbb{F}_{q}\) is supersingular. The point P = (x(P), y(P)), where \(x(P) = 2^{1500} + 2\) and
has order n. We take g = 2,
and we compute
Next, we compute \(Q = g^{a}P = (x(Q),y(Q))\), where
and
Therefore (P, Q, 2, n) and \((a,p_{1},p_{2})\) are a public key and the corresponding private key for our signature scheme. Moreover, we can use the Tate pairing with the distortion map \(\phi (x,y) = (-x,iy)\) with \(i^{2} = -1\).
7 Security of the Scheme
In this section we shall discuss the security of our system. First, we remark that if an attacker wants to compute the private key \((a,p_{1},p_{2})\) from the public key, he has to factorize n and to compute the discrete logarithm g a of Q to the base P and next to calculate the discrete logarithm a of g a to the base g in the group \(\mathbb{Z}_{n}\). Note that an algorithm which computes the discrete logarithm modulo n implies an algorithm which breaks the Composite Diffie–Hellman key distribution scheme for n and any algorithm which breaks this scheme for a non-negligible proportion of the possible inputs can be used to factorize n [2, 21].
In order to study the security of the scheme we are going to look at the two worst cases:
-
1.
the factorization problem is broken but the elliptic curve discrete logarithm problem is not;
-
2.
the elliptic curve discrete logarithm problem is broken but the factorization problem is not.
In each case we will prove that if an attacker is able to generate a valid signature for any given message m, then it is able to solve, in the first case the elliptic curve discrete logarithm problem and in the second case the factorization problem.
-
1.
Let us suppose that the attacker is able to factorize n. Then he can compute ϕ(n). But he is unable to compute a since a is protected by the elliptic curve discrete logarithm problem and by the discrete logarithm problem modulo n, because the only known relation involving a is Q = g a P. So, in order to produce a valid signature of a message m the attacker has only two possibilities: he can arbitrary choose k, and then he can compute s but not S, or choose arbitrary l and he can compute S but not s.
-
2.
Let us suppose now that the attacker is able to solve the elliptic curve discrete logarithm problem. Then he can compute g a but as the factorization problem is not broken the discrete logarithm problem modulo n is not broken and consequently he cannot compute a (cf. the beginning of this section). Then as in (1) he cannot compute simultaneously s and S.
8 Conclusion
In this paper we defined a signature system based on two difficult arithmetic problems. In the framework chosen, these problems have similar resistance to known attacks. We explained how to implement in practice all the basic functions we need for the establishment and operation of this system. This strategy has an interest in any application that includes a signature to be valid for long. Indeed, it is hoped that if any of the underlying problems is broken, the other will still be valid. In this case, the signature should be regenerated with a new system, without the chain of valid signatures being broken. Finally, the signature length of our scheme is smaller than that of the schemes based on integer factorization and integer discrete logarithm problems, and its performance is competitive to that of these schemes.
References
Barreto, P.S.L., Galbraith, S.D., Ó’hÉigeartaigh, C., Scott, M.: Efficient pairing computation on supersingular Abelian varieties. Des. Codes Crypt. 42, 239–271 (2007)
Biham, E., Boneh, D., Reingold, O.: Breaking generalized Diffie-Hellman is no easier than factoring. Inf. Proces. Lett. 70, 83–87 (1999)
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. Lect. Notes Comput. Sci. 2248, 514–532 (2001)
Bróker, R.: Constructing supersingular elliptic curves. J. Combin. Number Theory 1(3), 269–273 (2009)
Buchmann, J., May, A., Vollmer, U.: Perspectives for cryptographic long term security. Commun. ACM 49(9), 50–55 (2006)
Chen, T.-H., Lee, W.-B., Horng, G.: Remarks on some signature schemes based on factoring and discrete logarithms. Appl. Math. Comput. 169, 1070–1075 (2005)
Galbraith, S.D., Rotger, V.: Easy decision Diffie-Hellman groups. LMS J. Comput. Math. 7, 201–218 (2004)
Girault, M., Poupard, G., Stern, J.: Global Payment System (GPS): un protocole de signature à la volée. In: Proceedings of Trusting Electronic Trade, 7–9 June 1999
Harn, L.: Enhancing the security of ElGamal signature scheme. IEE Proc. Comput. Digital 142(5), 376 (1995)
Hess, F., Smart, N.P., Vercauteren, F.: The Eta pairing revisited. IEEE Trans. Inf. Theory 52(10), 4595–4602 (2006)
Icart, T.: How to Hash into elliptic curves. In: CRYPTO 2009. Lecture Notes in Computer Science, vol. 5677, pp. 303–316. Springer, New York (2009)
Ismail, E.S., Tahat, N.M.F., Ahmad, R.R.: A new digital signature scheme based on factoring and discrete logarithms. J. Math. Stat. 4(4), 22–225 (2008)
Ismail, E.S., Tahat, N.M.F.: A new signature scheme based on multiple hard number theoretic problems. ISRN Commun. Netw. 2011, 3 pp. (2011). Article ID 231649. http://dx.doi.org/10.5402/2011/231649
Joux, A.: The weil and tate pairings as building blocks for public key cryptosystems (Survey). In: ANTS 2002. Lecture Notes in Computer Science, vol. 2369, pp. 20–32. Springer, Berlin (2001)
Karagiorgos, G., Poulakis, D.: Efficient algorithms for the basis of finite Abelian groups. Discret. Math. Algoritm. Appl. 3(4), 537–552 (2011)
Lee, N.Y.: Security of Shao’s signature schemes based on factoring and discrete logarithms. IEE Proc. Comput. Digital Tech. 146(2), 119–121 (1999)
Lee, N.Y., Hwang, T.: The security of He and Kiesler’s signature scheme. IEE Proc. Comput. Digital Tech. 142(5), 370–372 (1995)
Li, J., Xiao, G.: Remarks on new signature scheme based on two hard problems. Electron. Lett. 34(25), 2401 (1998)
Madhur, K., Yadav, J.S., Vijay, A.: Modified ElGamal over RSA Digital Signature Algorithm (MERDSA). Int. J. Adv. Res. Comput. Sci. Softw. Eng. 2(8), 289–293 (2012)
Maseberg, J.S.: Fail-safe konzept fur public-key infrastrukturen. Thesis, Technische Universitat Darmstadt (2002)
McCurley, K.S.: A key distibution system equivalent to factoring. J. Cryptol. 1, 95–105 (1988)
Shao, Z.: Security of a new digital signature scheme based on factoring and discrete logarithms. Int. J. Comput. Math. 82(10), 1215–1219 (2005)
Verheul, E.: Evidence that XTR is more secure than supersingular elliptic curve cryptosystems. In: Advances in Cryptology-Eurocrypt ’01. Lecture Notes in Computer Science, vol. 2045, pp. 195–210. Springer, New York (2001)
Verma, S., Sharma, B.K.: A new digital signature scheme based on two hard problems. Int. J. Pure Appl. Sci. Technol. 5(2), 55–59 (2011)
Vishnoi, S., Shrivastava, V.: A new digital signature algorithm based on factorization and discrete logarithm problem. Int. J. Comput. Trends Tech. 3(4), 653–657 (2012)
Vladut, S.: Cyclicity statistics for elliptic curves over finite fields. Finite Fields Appl. 5(1), 13–25 (1999)
Wei, S.: A new digital signature scheme based on factoring and discrete logarithms. In: Progress on Cryptography. Kluwer International Series in Engineering and Computer Science, vol. 769, pp. 107–111. Kluwer Academic Publishers, Boston (2004)
Zhao, C.-A., Xie, D., Zhang, F., Zhang, J., Chen, B.-L.: Computing bilinear pairing on elliptic curves with automorphisms. Des. Codes Crypt. 58, 35–44 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Poulakis, D., Rolland, R. (2015). A Digital Signature Scheme Based on Two Hard Problems. In: Daras, N., Rassias, M. (eds) Computation, Cryptography, and Network Security. Springer, Cham. https://doi.org/10.1007/978-3-319-18275-9_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-18275-9_19
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18274-2
Online ISBN: 978-3-319-18275-9
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)