A logarithmic size revocable linkable ring signature for privacy-preserving blockchain transactions

Abstract

Monero uses ring signatures to protect users’ privacy. However, Monero’s anonymity covers various illicit activities, such as money laundering, as it becomes difficult to identify and punish malicious users. Therefore, it is necessary to regulate illegal transactions while protecting the privacy of legal users. We present a revocable linkable ring signature scheme (RLRS), which balances the privacy and supervision for privacy-preserving blockchain transactions. By setting the role of revocation authority, we can trace the malicious user and revoke it in time. We define the security model of the revocable linkable ring signature and give the concrete construction of RLRS. We employ accumulator and ElGamal encryption to achieve the functionalities of revocation and tracing. In addition, we compress the ring signature size to the logarithmic level by using non-interactive sum arguments of knowledge (NISA). Then, we prove the security of RLRS, which satisfies anonymity, unforgeability, linkability, and non-frameability. Lastly, we compare RLRS with other ring signature schemes. RLRS is linkable, traceable, and revocable with logarithmic communication complexity and less computational overhead. We also implement RLRS scheme and the results show that its verification time is 1.5s with 500 ring members.

Keywords

Ring signature / Accumulator / Revocable / Logarithmic size

CRediT authorship contribution statement

Yanqi Zhao: Writing - original draft. Jie Zhang: Writing - original draft. Xiaoyi Yang: Writing - original draft. Minghong Sun: Formal analysis, Data curation. Yuxin Zhang: Data curation. Yong Yu: Writing - review & editing. Huilin Li: Writing - review & editing.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgments

This work is supported by the National Key R&D Program of China (2022YFB2701500), the National Natural Science Foundation of China (62272385, 62202375), Shaanxi Distinguished Youth Project (2022JC-47), the Major Program of Shandong Provincial Natural Science Foundation for the Fundamental Research (ZR2022ZD03), the Key Research and Development Program of Shaanxi (2024GX-ZDCYL-01-09, 2024GX-ZDCYL-01-15), Young Talent Fund of Association for Science and Technology in Shaanxi, China (20220134), Scientific Research Program Funded by Shaanxi Provincial Education Department, China (24JK0653).

References

[1] Y. Chen, H. Chen, Y. Zhang, M. Han, M. Siddula, Z. Cai, A survey on blockchain systems: Attacks, defenses, and privacy preservation, High-Confid. Comput. 2 (2) (2022) 100048.

[2] N.V. Saberhagen, Cryptonote v 2.0, 2013, http://cryptonote.org/whitepaper.pdf.

[3] R.L. Rivest, A. Shamir, Y. Tauman,How to leak a secret, in:Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9-13, 2001, Proceedings, vol. 2248, Springer, 2001, pp. 552-565, http://dx.doi.org/10.1007/3-540-45682-1_32.

[4] V.K.W. Joseph K. Liu, D.S. Wong, Linkable spontaneous anonymous group signature for ad hoc groups, IACR Cryptol. EPrint Arch. 3108 (2004) 325-335, http://dx.doi.org/10.1007/978-3-540-27800-9_28.

[5] M.O. Masayuki Abe, K. Suzuki, 1-out-of-n signatures from a variety of keys, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 87-A (1) (2004) 131-140.

[6] J. Herranz, G. Sáez,Forking lemmas for ring signature schemes, in:Progress in Cryptology - INDOCRYPT 2003, 4th International Conference on Cryptology in India, New Delhi, India, December 8-10, 2003, Proceedings,in:Lecture Notes in Computer Science, vol. 2904, Springer, 2003, pp. 266-279, http://dx.doi.org/10.1007/978-3-540-24582-7_20.

[7] Y. Zhang, Y. Hu, J. Xie, M. Jiang, Efficient ring signature schemes over NTRU lattices, Secur. Commun. Netw. 9 (2016) 5252-5261, http://dx.doi.org/10.1002/SEC.1694.

[8] T.N. Nguyen, A.T. Ta, H.Q. Le, D.H. Duong, W. Susilo, F. Guo, K. Fukushima, S. Kiyomoto, Efficient unique ring signatures from lattices, IACR Cryptol. EPrint Arch. (2022) 1070, URL https://eprint.iacr.org/2022/1070.

[9] F. Zhang, K. Kim,ID-based blind signature and ring signature from pairings, in:Advances in Cryptology - ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1-5, 2002, Proceedings,in:Lecture Notes in Computer Science, vol. 2501, Springer, 2002, pp. 533-547, http://dx.doi.org/10.1007/3-540-36178-2_33.

[10] D. Boneh, C. Gentry, B. Lynn, H. Shacham, Aggregate and verifiably encrypted signatures from bilinear maps, in: E. Biham (Ed.), Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings,in: Lecture Notes in Computer Science, vol. 2656, Springer, 2003, pp. 416-432, http://dx.doi.org/10.1007/3-540-39200-9_26.

[11] J.S. Emmanuel Bresson, M. Szydlo,Threshold ring signatures and applications to ad-hoc groups, in:Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings,in:Lecture Notes in Computer Science, vol. 2442, Springer, 2002, pp. 465-480, http://dx.doi.org/10.1007/3-540-45708-9_30.

[12] J.K. Liu, S.L. Yeo, W. Yap, S.S.M. Chow, D.S. Wong, W. Susilo, Faulty instantiations of threshold ring signature from threshold proof-of-knowledge protocol, Comput. J. 59 (7) (2016) 945-954, http://dx.doi.org/10.1093/COMJNL/BXV098.

[13] J. Lv, X. Wang, Verifiable ring signature, in:Proc. of DMS 2003-the 9th International Conference on Distribted Multimedia Systems, 2003, pp. 663-667.

[14] M. Naor, Deniable ring authentication, in:Advances in Cryptology- CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings,in:Lecture Notes in Computer Science, vol. 2442, Springer, 2002, pp. 481-498, http://dx.doi.org/10.1007/3-540-45708-9_31.

[15] W. Susilo, Y. Mu, Non-interactive deniable ring authentication, in: Information Security and Cryptology - ICISC 2003, 6th International Conference, Seoul, Korea, November 27-28, 2003, Revised Papers, in: Lecture Notes in Computer Science, vol. 2971, Springer. 2003, pp. 386-401, http://dx.doi.org/10.1007/978-3-540-24691-6_29.

[16] J.K. Liu, D.S. Wong,Linkable ring signatures: Security models and new schemes,in:Computational Science and Its Applications - ICCSA 2005, International Conference, Singapore, May 9-12, 2005, Proceedings, Part II, in:Lecture Notes in Computer Science, vol. 3481, Springer, 2005, pp. 614-623, http://dx.doi.org/10.1007/11424826_65.

[17] P.P. Tsang, V.K. Wei,Short linkable ring signatures for E-voting, E-cash and attestation, in:Information Security Practice and Experience, First International Conference, ISPEC 2005, Singapore, April 11-14, 2005, Proceedings,in:Lecture Notes in Computer Science, vol. 3439, Springer, 2005, pp. 48-60, http://dx.doi.org/10.1007/978-3-540-31979-5_5.

[18] E. Fujisaki, K. Suzuki,Traceable ring signature, in:Public Key Cryptography - PKC 2007, 10th International Conference on Practice and Theory in Public-Key Cryptography, Beijing, China, April 16-20, 2007, Proceedings,in:Lecture Notes in Computer Science, vol. 4450, Springer, 2007, pp. 181-200, http://dx.doi.org/10.1007/978-3-540-71677-8_13.

[19] W.S. Man Ho Au, T.H. Yuen, Secure ID-based linkable and revocable-iff-linked ring signature with constant-size construction, Theoret. Comput. Sci. 469 (2013) 1-14, http://dx.doi.org/10.1016/J.TCS.2012.10.031.

[20] D.Y.W. Liu, J.K. Liu, Y. Mu, W. Susilo, D.S. Wong, Revocable ring signature, J. Comput. Sci. Tech. 22 (6) (2007) 785-794, http://dx.doi.org/10.1007/S11390-007-9096-5.

[21] A. Kumar, C. Fischer, S. Tople, P. Saxena,A traceability analysis of monero’s blockchain, in:Computer Security - ESORICS 2017-22nd European Symposium on Research in Computer Security, Oslo, Norway, September 11-15, 2017, Proceedings, Part II, in:Lecture Notes in Computer Science, vol. 10493, Springer, 2017, pp. 153-173, http://dx.doi.org/10.1007/978-3-319-66399-9_9.

[22] S. Sun, M.H. Au, J.K. Liu, T.H. Yuen, D. Gu, RingCT 2.0: A compact accumulator-based (linkable ring signature) protocol for blockchain cryptocurrency monero, IACR Cryptol. EPrint Arch. (2017) 921.

[23] T.H. Yuen, S. Sun, J.K. Liu, M.H. Au, M.F. Esgin, Q. Zhang, D. Gu, RingCT 3.0 for blockchain confidential transaction: Shorter size and stronger security, in: J. Bonneau, N. Heninger (Eds.), Financial Cryptography and Data Security - 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10-14, 2020 Revised Selected Papers, in: Lecture Notes in Computer Science, vol. 12059, Springer, 2020, pp. 464-483, http://dx. doi.org/10.1007/978-3-030-51280-4_25.

[24] J. Groth, M. Kohlweiss, One-out-of-many proofs: Or how to leak a secret and spend a coin, in: E. Oswald, M. Fischlin (Eds.), Advances in Cryptology- EUROCRYPT 2015- 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part II, in: Lecture Notes in Computer Science, vol. 9057, Springer, 2015, pp. 253-280, http://dx.doi.org/10.1007/978-3-662-46803-6_9.

[25] B.E. Diamond, Many-out-of-many proofs and applications to anonymous zether, in: 42nd IEEE Symposium on Security and Privacy, SP 2021, San Francisco, CA, USA, 24-27 May 2021, IEEE, 2021, pp. 1800-1817, http://dx.doi.org/10.1109/SP40001.2021.00026.

[26] T.H. Yuen, M.F. Esgin, J.K. Liu, M.H. Au, Z. Ding, DualRing: Generic construction of ring signatures with efficient instantiations, in: T. Malkin, C. Peikert (Eds.), Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part I, in: Lecture Notes in Computer Science, vol. 12825, Springer, 2021, pp. 251-281, http://dx.doi.org/10.1007/978-3-030-84242-0_10.

[27] J. Bootle, K. Elkhiyaoui, J. Hesse, Y. Manevich,DualDory: Logarithmic-verifier linkable ring signatures through preprocessing,in:Computer Security - ESORICS 2022 - 27th European Symposium on Research in Computer Security, Copenhagen, Denmark, September 26-30, 2022, Proceedings, Part II, in:Lecture Notes in Computer Science, vol. 13555, Springer, 2022, pp. 427-446, http://dx.doi.org/10.1007/978-3-031-17146-8_21.

[28] Z. Bao, D. He, Y. Liu, C. Peng, Q. Feng, M. Luo,Quartet: A logarithmic size linkable ring signature scheme from DualRing,in:Cyberspace Safety and Security - 14th International Symposium, CSS 2022, Xi’an, China, October 16-18, 2022, Proceedings,in:Lecture Notes in Computer Science, vol. 13547, 2022, pp. 56-70, http://dx.doi.org/10.1007/978-3-031-18067-5_5.

[29] M. Feng, C. Lin, W. Wu, D. He, SM2-DualRing: Efficient SM2-based ring signature schemes with logarithmic size, Comput. Stand. Interfaces 87 (2024) 103763, http://dx.doi.org/10.1016/J.CSI.2023.103763.

[30] J. Bootle, A. Cerulli, P. Chaidos, E. Ghadafi, J. Groth, C. Petit,Short accountable ring signatures based on DDH, in:Computer Security - ESORICS 2015 - 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part I, in:Lecture Notes in Computer Science, vol. 9326, Springer, 2015, pp. 243-265, http://dx.doi.org/10.1007/978-3-319-24174-6_13.

[31] X. Zhang, J.K. Liu, R. Steinfeld, V. Kuchta, J. Yu,Revocable and linkable ring signature, in: Information Security and Cryptology - 15th International Conference, Inscrypt 2019, Nanjing, China, December 6-8, 2019, Revised Selected Papers, in: Lecture Notes in Computer Science, vol. 12020, Springer, 2019, pp. 3-27, http://dx.doi.org/10.1007/978-3-030-42921-8_1.

[32] A. Fraser, E.A. Quaglia, Report and trace ring signatures, in: M. Conti, M. Stevens, S. Krenn (Eds.), Cryptology and Network Security - 20th International Conference, CANS 2021, Vienna, Austria, December 13-15, 2021, Proceedings,in: Lecture Notes in Computer Science, vol. 13099, Springer, 2021, pp. 179-199, http://dx.doi.org/10.1007/978-3-030-92548-2_10.

[33] Y. Li, W. Wang, D. Zhang, X. Han, One-time and revocable ring signature with logarithmic size in blockchain, IACR Cryptol. EPrint Arch. (2023) 1633.

[34] H.-j. Song, T. Kim, Y.-W. Hwang, D. Seo, I.-Y. Lee, A study on dynamic group signature scheme with threshold traceability for blockchain, High-Confid. Comput. 4 (2) (2024) 100163.

[35] J. Tian, Y. Zhao, X. Yang, X. Zhao, R. Chen, Y. Yu, Identity-based threshold (multi) signature with private accountability for privacy-preserving blockchain, High-Confid. Comput. (2024) 100271.

[36] K. Hara, A logarithmic-sized accountable ring signature scheme in the standard model, Theoret. Comput. Sci. 997 (2024) 114516, http://dx.doi.org/10.1016/J.TCS.2024.114516.

[37] S. Agrawal, C. Ganesh, P. Mohassel, Non-interactive zero-knowledge proofs for composite statements, in:Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III, in:Lecture Notes in Computer Science, vol. 10993, Springer, 2018, pp. 643-673, http://dx.doi.org/10.1007/ 978-3-319-96878-0_22.

[38] A. Fiat, A. Shamir, How to prove yourself: Practical solutions to identification and signature problems,in: A. M. Odlyzko (Ed.), Advances in Cryptology - CRYPTO ’86, Santa Barbara, California, USA, 1986, Proceedings,in: Lecture Notes in Computer Science, vol. 263, Springer, 1986, pp. 186-194, http://dx.doi.org/10.1007/3-540-47721-7_12.

[39] J. Bootle, A. Cerulli, P. Chaidos, J. Groth, C. Petit, Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting, in: M. Fischlin, J. Coron (Eds.), Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, in: Lecture Notes in Computer Science, vol. 9666, Springer, 2016, pp. 327-357, http://dx.doi.org/10.1007/978-3-662-49896-5_12.

[40] M.H. Au, P.P. Tsang, W. Susilo, Y. Mu, Dynamic universal accumulators for DDH groups and their application to attribute-based anonymous credential systems, in: M. Fischlin (Ed.), Topics in Cryptology - CT-RSA 2009, the Cryptographers’ Track at the RSA Conference 2009, San Francisco, CA, USA, April 20-24, 2009. Proceedings, in: Lecture Notes in Computer Science, vol. 5473, Springer, 2009, pp. 295-308, http://dx.doi.org/10.1007/978-3-642-00862-7_20.

[41] J. Katz, Y. Lindell, Introduction to Modern Cryptography, Chapman & Hall, 2021.