Efficient ways of prime number generation for ring signatures

Efficient ways of prime number generation for ring signatures

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.


    1. 1)
      • 1. Gerlach, J., Gasser, U.: ‘Three case studies from Switzerland: E-voting’ (Berkman Center Research Publication No. 2009-03.1, 2009).
    2. 2)
      • 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. 5372.
    3. 3)
    4. 4)
      • 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. 4860.
    5. 5)
      • 5. Dodis, Y., Kiayias, A., Nicolosi, A., Shoup, V.: ‘Anonymous Identification in Ad Hoc Groups’. EUROCRYPT, 2004 (LNCS, 3027), pp. 609626.
    6. 6)
      • 6. Camenisch, J., Stadler, M.: ‘Efficient group signature schemes for large groups (extended abstract)’. B.S. Kaliski Jr. (Ed.), CRYPTO, Springer, Heidelberg, 1997 (LNCS, 1294), pp. 410424.
    7. 7)
    8. 8)
      • 8. Liu, J.K., Wei, V.K., Wong, D.S.: ‘Linkable spontaneous anonymous group signature for ad hoc groups’. ACISP'04, 2004 (LNCS, 3108), pp. 325335.
    9. 9)
    10. 10)
      • 10. Ateniese, G., Camenisch, J., Joye, M., Tsudik, G.: ‘A practical and provably secure coalition-resistant group signature scheme’. CRYPTO, 2000 (LNCS, 1880), pp. 255270.
    11. 11)
      • 11. Gordon, J.: ‘Strong primes are easy to find’, Adv. Criptol. – Eurocrypt, 1984, 84, pp. 216223.
    12. 12)
    13. 13)
      • 13. Friedlander, J., Iwaniec, H.: ‘Applications to linear sequences (57)’ (American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2010).

Related content

This is a required field
Please enter a valid email address