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 ₁, e ₂) such that e = 2e ₁ e ₂ + 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 ⁴) 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. 1)
  - 11. Gordon, J.: ‘Strong primes are easy to find’, Adv. Criptol. – Eurocrypt, 1984, 84, pp. 216–223.
2. 2)
  - 5. Dodis, Y., Kiayias, A., Nicolosi, A., Shoup, V.: ‘Anonymous Identification in Ad Hoc Groups’. EUROCRYPT, 2004 (LNCS, 3027), pp. 609–626.
3. 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. 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. 5)
  - 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. 410–424.
6. 6)
  - 13. Friedlander, J., Iwaniec, H.: ‘Applications to linear sequences (57)’ (American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2010).
7. 7)
  - 1. Gerlach, J., Gasser, U.: ‘Three case studies from Switzerland: E-voting’ (Berkman Center Research Publication No. 2009-03.1, 2009).
8. 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. 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)
  - 10. Ateniese, G., Camenisch, J., Joye, M., Tsudik, G.: ‘A practical and provably secure coalition-resistant group signature scheme’. CRYPTO, 2000 (LNCS, 1880), pp. 255–270.
11. 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. 12)
  - 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. 325–335.
13. 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).

Efficient ways of prime number generation for ring signatures

References

Related content