Supersingular Isogeny-based Ring Signature

Abstract

The increasing demand for secure and anonymous transactions raises the popularity of ring signatures, which is a digital signature scheme that allows identifying a group of possible signers without revealing the identity of the actual signer. This paper presents efficient supersingular isogeny-based ring signature and linkable ring signature schemes that will find potential applications in post-quantum technologies. We develop the ring signature scheme by applying the Fiat-Shamir transform on the sigma protocol for a ring which we obtain from the supersingular isogeny-based interactive zero-knowledge identification scheme by adopting the scheme for a ring. We also extend our ring signature protocol with an additional parameter, i.e., a tag that provides to detect if a signer issues two signatures concerning the same ring by preserving anonymity and linkable anonymity. The signature size of our ring signature protocols increases logarithmically in the size of the ring thanks to the Merkle trees. We show the security proofs and efficiency analyses of the protocols offered. Moreover, we provide the implementation results of the supersingular isogeny-based ring signature, which offers small signature sizes for NIST post-quantum security levels.

Keywords

• linkable ring signature
• post-quantum cryptography
• ring signature
• supersingular isogeny

Supporting Institution

TUBITAK

Project Number

120E06

Thanks

M. Sheikhi Garjan was a postdoctoral researcher at Middle East Technical University during a period of this research and would like to thank the Institute of Applied Mathematics Cryptography Department for the hospitality. N. G. Orhon Kılıc ̧ was supported by the Council of Higher Education (YOK) 100/2000 CoHE Ph.D. Scholarship and would like to thank the Council of Higher Education. A part of this paper was written while M. Cenk was visiting the University of Waterloo and would like to thank the Department of Combinatorics & Optimization for hospitality.

References

1. R. L. Rivest, A. Shamir, and Y. Tauman, “How to leak a secret,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2001, pp. 552– 565.
2. J. K. Liu, V. K. Wei, and D. S. Wong, “Linkable spontaneous anonymous group signature for ad hoc groups,” in Australasian Conference on Information Security and Privacy. Springer, 2004, pp. 325–335.
3. P. P. Tsang and V. K. Wei, “Short linkable ring signatures for e-voting, e-cash and attestation,” in International Conference on Information Security Practice and Experience. Springer, 2005, pp. 48–60.
4. M. Chase and A. Lysyanskaya, “On signatures of knowledge,” in Annual International Cryptology Conference. Springer, 2006, pp. 78–96.
5. Y. Dodis, A. Kiayias, A. Nicolosi, and V. Shoup, “Anonymous identification in ad hoc groups,” in International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2004, pp. 609–626.
6. M. Abe, M. Ohkubo, and K. Suzuki, “1-out-of-n signatures from a variety of keys,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2002, pp. 415–432.
7. J. Groth and M. Kohlweiss, “One-out-of-many proofs: Or how to leak a secret and spend a coin,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2015, pp. 253–280.
8. J.HerranzandG.Sa ́ez, “Forkinglemmasforringsignature schemes,” in International Conference on Cryptology in India. Springer, 2003, pp. 266–279.

9. J. K. Liu and D. S. Wong, “Linkable ring signatures: Security models and new schemes,” in International Conference on Computational Science and Its Applications. Springer, 2005, pp. 614–623.
10. A. Bender, J. Katz, and R. Morselli, “Ring signatures: Stronger definitions, and constructions without random oracles,” in Theory of Cryptography Conference. Springer, 2006, pp. 60–79.
11. L. Nguyen, “Accumulators from bilinear pairings and applications,” in Cryptographers’ track at the RSA conference. Springer, 2005, pp. 275–292.
12. H. Shacham and B. Waters, “Efficient ring signatures without random oracles,” in International Workshop on Public Key Cryptography. Springer, 2007, pp. 166–180.
13. S. S. Chow, S.-M. Yiu, and L. C. Hui, “Efficient identity-based ring signature,” in International Conference on Applied Cryptography and Network Security. Springer, 2005, pp. 499– 512.
14. M. Backes, N. Do ̈ttling, L. Hanzlik, K. Kluczniak, and J. Schneider, “Ring signatures: Logarithmic-size, no setup—from standard assumptions,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2019, pp. 281–311.
15. D. Derler, S. Ramacher, and D. Slamanig, “Post-quantum zero-knowledge proofs for accumulators with applications to ring signatures from symmetric-key primitives,” in International Conference on Post-Quantum Cryptography. Springer, 2018, pp. 419–440.
16. J. Katz, V. Kolesnikov, and X. Wang, “Improved non-interactive zero-knowledge with applications to post-quantum signatures,” in Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018, pp. 525–537.
17. D. H. Duong, H. T. Tran, W. Susilo, et al., “An efficient multivariate threshold ring signature scheme,” Computer Standards & Interfaces, vol. 74, p. 103489, 2020.
18. M. S. E. Mohamed and A. Petzoldt, “Ringrainbow–an efficient multivariate ring signature scheme,” in International Conference on Cryptology in Africa. Springer, 2017, pp. 3–20.
19. C. Baum, H. Lin, and S. Oechsner, “Towards practical lattice-based one-time linkable ring signatures,” in International Conference on Information and Communications Security. Springer, 2018, pp. 303–322.
20. W. Beullens, S. Katsumata, and F. Pintore, “Calamari and falafl: Logarithmic (linkable) ring signatures from isogenies and lattices,” 2020.
21. M. F. Esgin, R. K. Zhao, R. Steinfeld, J. K. Liu, and D. Liu, “Matrict: efficient, scalable and post-quantum blockchain confidential transactions protocol,” in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 2019, pp. 567–584.
22. B. Libert, S. Ling, K. Nguyen, and H. Wang, “Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2016, pp. 1–31.
23. W. A. A. Torres, R. Steinfeld, A. Sakzad, J. K. Liu, V. Kuchta, N. Bhattacharjee, M. H. Au, and J. Cheng, “Post-quantum one-time linkable ring signature and application to ring confidential transactions in blockchain (lattice ringct v1. 0),” in Australasian Conference on Information Security and Privacy. Springer, 2018, pp. 558–576.
24. L.DeFeo,D.Jao, and J.Pluˆt, “Towardsquantum-resistant cryptosystems from supersingular elliptic curve isogenies,” Journal of Mathematical Cryptology, vol. 8, no. 3, pp. 209–247, 2014.
25. C. Costello, P. Longa, and M. Naehrig, “Efficient algorithms for supersingular isogeny diffie-hellman,” in Annual International Cryptology Conference. Springer, 2016, pp. 572–601.
26. J. H. Silverman, The arithmetic of elliptic curves. Springer Science & Business Media, 2009, vol. 106.
27. D. Jao and L. De Feo, “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies,” in International Workshop on Post-Quantum Cryptography. Springer, 2011, pp. 19–34.
28. C. D. de Saint Guilhem, P. Kutas, C. Petit, and J. Silva, “Se ́ta: Supersingular encryption from torsion attacks,” 2019.
29. S. D. Galbraith, C. Petit, and J. Silva, “Identification protocols and signature schemes based on supersingular isogeny problems,” Journal of Cryptology, vol. 33, no. 1, pp. 130–175, 2020.
30. Y.Yoo, R.Azarderakhsh, A.Jalali, D.Jao, and.Soukharev, “A post-quantum digital signature scheme based on supersingular isogenies,” in International Conference on Financial Cryptography and Data Security. Springer, 2017, pp. 163–181.
31. J. Ve ́lu, “Isogenies entre courbes elliptiques,” Communica- tions de lA ́cademie royale des Sciences de Paris, vol. 273, p. 238–241, 1971.
32. D. Jao and V. Soukharev, “Isogeny-based quantum-resistant undeniable signatures,” in International Workshop on Post-Quantum Cryptography. Springer, 2014, pp. 160–179.
33. M. S. Srinath and V. Chandrasekaran, “Isogeny-based quantum- resistant undeniable blind signature scheme.” IACR Cryptology ePrint Archive, vol. 2016, p. 148, 2016.