© The Institution of Engineering and Technology
The authors describe two different algorithms to perform efficiently the ring signature keys generation. Given an integer size, l, their algorithms find efficiently (memory and time, respectively) two distinct l/2-bit primes (e 1, e 2) such that e = 2e 1 e 2 + 1 will be a prime integer. With a naïve algorithm one only needs to store O(l) bits (more specifically, only one l/2-integer), and need, in average, O(l 4) basic l-bit operations. With the second algorithm, one not only improves this computational complexity O(l 7/2), but also needs to use, in average, O(l 3/2) bits. The authors consider these algorithms useful for implementing ring signatures in mobile devices where there exist strong time and space constraints.
References
-
-
1)
-
11. Gordon, J.: ‘Strong primes are easy to find’, Adv. Criptol. – Eurocrypt, 1984, 84, pp. 216–223.
-
2)
-
5. Dodis, Y., Kiayias, A., Nicolosi, A., Shoup, V.: ‘Anonymous Identification in Ad Hoc Groups’. EUROCRYPT, 2004 (, 3027), pp. 609–626.
-
3)
-
3. Liu, J.K., Au, M.H., Susilo, W., Zhou, J.: ‘Linkable ring signature with unconditional anonymity’, IEEE Trans. Knowl. Data Eng., 2014, 26, (1), pp. 157–165 (doi: 10.1109/TKDE.2013.17).
-
4)
-
12. Rabin, M.O.: ‘Probabilistic algorithm for testing primality’, J. Number Theory, 1980, 12, (1), pp. 128–138 (doi: 10.1016/0022-314X(80)90084-0).
-
5)
-
6. Camenisch, J., Stadler, M.: ‘Efficient group signature schemes for large groups (extended abstract)’. . (Ed.), CRYPTO, Springer, Heidelberg, 1997 (, 1294), pp. 410–424.
-
6)
-
13. Friedlander, J., Iwaniec, H.: ‘Applications to linear sequences (57)’ (American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2010).
-
7)
-
1. Gerlach, J., Gasser, U.: ‘Three case studies from Switzerland: E-voting’ (Berkman Center Research Publication No. 2009-03.1, 2009).
-
8)
-
7. Goldwasser, S., Micali, S., Rackoff, C.: ‘The knowledge complexity of interactive proof systems’, SIAM J. Comput., 1989, 18, (1), pp. 186–208 (doi: 10.1137/0218012).
-
9)
-
4. Tsang, P.P., Wei, V.K.: ‘Short linkable ring signatures for e-voting, e-cash and attestation’. Proc. of the First Int. Conf. on Information Security Practice and Experience (ISPEC'05), 2005, pp. 48–60.
-
10)
-
10. Ateniese, G., Camenisch, J., Joye, M., Tsudik, G.: ‘A practical and provably secure coalition-resistant group signature scheme’. CRYPTO, 2000 (, 1880), pp. 255–270.
-
11)
-
2. Madise, Ü., Vinkel, P.: ‘Internet voting in Estonia: from constitutional debate to evaluation of experience over six elections’. Regulating eTechnologies in the European Union, Springer International Publishing, 2014, pp. 53–72.
-
12)
-
8. Liu, J.K., Wei, V.K., Wong, D.S.: ‘Linkable spontaneous anonymous group signature for ad hoc groups’. ACISP'04, 2004 (, 3108), pp. 325–335.
-
13)
-
9. Camenisch, J., Lysyanskaya, A.: ‘A signature scheme with efficient protocols’, Secur. Commun. Netw., 2002, 2576, pp. 268–289 (doi: 10.1007/3-540-36413-7_20).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2014.0547
Related content
content/journals/10.1049/iet-ifs.2014.0547
pub_keyword,iet_inspecKeyword,pub_concept
6
6