Revocable and Linkable Ring Signature

In this paper, we construct a revocable and linkable ring signature (RLRS) scheme, which enables a revocation authority to revoke the anonymity of the real signer in linkable ring signature scheme under any circumstances. In other words, the revocability of RLRS is mandatory. The proposed RLRS scheme inherits the desired properties of group signature (anonymity revocation) and linkable ring signature (spontaneous group formation and linkability). In addition, we proved the security of our scheme in the random oracle model. We also provided a revocable ring confidential transaction protocol based on our RLRS scheme, which embedded the revocability in ring confidential transaction protocol.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic €32.70 /Month

Buy Now

Price includes VAT (France)

eBook EUR 42.79 Price includes VAT (France)

Softcover Book EUR 52.74 Price includes VAT (France)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

Short Repudiable Ring Signature: Constant Size and Less Overhead

Chapter © 2023

Cryptanalysis of a non-interactive deniable ring signature scheme

Article 11 April 2020

Ring Signature

Chapter © 2019

References

  1. Abe, M., Ohkubo, M., Suzuki, K.: 1-out-of-n signatures from a variety of keys. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 415–432. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36178-2_26ChapterGoogle Scholar
  2. Au, M.H., Chow, S.S.M., Susilo, W., Tsang, P.P.: Short linkable ring signatures revisited. In: Atzeni, A.S., Lioy, A. (eds.) EuroPKI 2006. LNCS, vol. 4043, pp. 101–115. Springer, Heidelberg (2006). https://doi.org/10.1007/11774716_9ChapterGoogle Scholar
  3. Au, M.H., Liu, J.K., Susilo, W., Yuen, T.H.: Constant-size ID-based linkable and revocable-iff-linked ring signature. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 364–378. Springer, Heidelberg (2006). https://doi.org/10.1007/11941378_26ChapterGoogle Scholar
  4. Au, M.H., Liu, J.K., Susilo, W., Yuen, T.H.: Certificate based (linkable) ring signature. In: Dawson, E., Wong, D.S. (eds.) ISPEC 2007. LNCS, vol. 4464, pp. 79–92. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72163-5_8ChapterGoogle Scholar
  5. Au, M.H., Liu, J.K., Susilo, W., Yuen, T.H.: Secure ID-based linkable and revocable-iff-linked ring signature with constant-size construction. Theoret. Comput. Sci. 469, 1–14 (2013) ArticleMathSciNetGoogle Scholar
  6. Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_26ChapterGoogle Scholar
  7. Brenig, C., Accorsi, R., Müller, G.: Economic analysis of cryptocurrency backed money laundering. In: ECIS (2015) Google Scholar
  8. Cayrel, P.-L., Lindner, R., Rückert, M., Silva, R.: A lattice-based threshold ring signature scheme. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 255–272. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14712-8_16ChapterGoogle Scholar
  9. Changlun, Z., Yun, L., Dequan, H.: A new verifiable ring signature scheme based on Nyberg-Rueppel scheme. In: 2006 8th International Conference on Signal Processing, vol. 4. IEEE (2006) Google Scholar
  10. FBI: Bitcoin virtual currency: Unique features present distinct challenges for deterring illicit activity. Intelligence Assessment (2012) Google Scholar
  11. Fujisaki, E.: Sub-linear size traceable ring signatures without random oracles. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 393–415. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19074-2_25ChapterGoogle Scholar
  12. Fujisaki, E., Suzuki, K.: Traceable ring signature. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 181–200. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71677-8_13ChapterGoogle Scholar
  13. Herranz, J., Sáez, G.: Forking lemmas for ring signature schemes. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 266–279. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24582-7_20ChapterGoogle Scholar
  14. Houben, R., Snyers, A.: Cryptocurrencies and blockchain: legal context and implications for financial crime, money laundering and tax evasion (2018) Google Scholar
  15. Huang, X., et al.: Cost-effective authentic and anonymous data sharing with forward security. IEEE Trans. Comput. 64(4), 971–983 (2015) ArticleMathSciNetGoogle Scholar
  16. Lee, K.C., Wen, H.A., Hwang, T.: Convertible ring signature. IEE Proc.-Commun. 152(4), 411–414 (2005) ArticleGoogle Scholar
  17. Liu, D.Y., Liu, J.K., Mu, Y., Susilo, W., Wong, D.S.: Revocable ring signature. J. Comput. Sci. Technol. 22(6), 785–794 (2007) ArticleMathSciNetGoogle Scholar
  18. Liu, J.K., Au, M.H., Susilo, W., Zhou, J.: Linkable ring signature with unconditional anonymity. IEEE Trans. Knowl. Data Eng. 26(1), 157–165 (2013) ArticleGoogle Scholar
  19. Liu, J.K., Wei, V.K., Wong, D.S.: Linkable spontaneous anonymous group signature for ad hoc groups. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 325–335. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27800-9_28ChapterGoogle Scholar
  20. Liu, J.K., Wong, D.S.: On the security models of (threshold) ring signature schemes. In: Park, C., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 204–217. Springer, Heidelberg (2005). https://doi.org/10.1007/11496618_16ChapterGoogle Scholar
  21. Liu, J.K., Wong, D.S.: Linkable ring signatures: security models and new schemes. In: Gervasi, O., et al. (eds.) ICCSA 2005. LNCS, vol. 3481, pp. 614–623. Springer, Heidelberg (2005). https://doi.org/10.1007/11424826_65ChapterGoogle Scholar
  22. Liu, J.K., Wong, D.S.: Solutions to key exposure problem in ring signature. IJ Netw. Secur. 6(2), 170–180 (2008) Google Scholar
  23. Liu, J.K., Yeo, S.L., Yap, W., Chow, S.S.M., Wong, D.S., Susilo, W.: Faulty instantiations of threshold ring signature from threshold proof-of-knowledge protocol. Comput. J. 59(7), 945–954 (2016) ArticleMathSciNetGoogle Scholar
  24. Liu, J.K., Yuen, T.H., Zhou, J.: Forward secure ring signature without random oracles. In: Qing, S., Susilo, W., Wang, G., Liu, D. (eds.) ICICS 2011. LNCS, vol. 7043, pp. 1–14. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25243-3_1ChapterGoogle Scholar
  25. Lv, J., Wang, X.: Verifiable ring signature. In: Proceedings of DMS 2003-The 9th International Conference on Distribted Multimedia Systems, pp. 663–667 (2003) Google Scholar
  26. Nakamoto, S., et al.: Bitcoin: a peer-to-peer electronic cash system (2008) Google Scholar
  27. Noether, S.: Ring signature confidential transactions for monero. IACR Cryptology ePrint Archive 2015, 1098 (2015) Google Scholar
  28. Rivest, R.L., Shamir, A., Tauman, Y.: How to leak a secret. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 552–565. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_32ChapterGoogle Scholar
  29. Rivest, R.L., Shamir, A., Tauman, Y.: How to leak a secret: theory and applications of ring signatures. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol. 3895, pp. 164–186. Springer, Heidelberg (2006). https://doi.org/10.1007/11685654_7ChapterGoogle Scholar
  30. Tsang, P.P., Au, M.H., Liu, J.K., Susilo, W., Wong, D.S.: A suite of non-pairing ID-based threshold ring signature schemes with different levels of anonymity (extended abstract). In: Heng, S.-H., Kurosawa, K. (eds.) ProvSec 2010. LNCS, vol. 6402, pp. 166–183. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16280-0_11ChapterGoogle Scholar
  31. Tsang, P.P., Wei, V.K.: Short linkable ring signatures for e-voting, e-cash and attestation. In: Deng, R.H., Bao, F., Pang, H.H., Zhou, J. (eds.) ISPEC 2005. LNCS, vol. 3439, pp. 48–60. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31979-5_5ChapterGoogle Scholar
  32. Tsang, P.P., Wei, V.K., Chan, T.K., Au, M.H., Liu, J.K., Wong, D.S.: Separable linkable threshold ring signatures. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 384–398. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30556-9_30ChapterGoogle Scholar
  33. Van Saberhagen, N.: Cryptonote v 2.0 (2013) Google Scholar
  34. Xiong, H., Chen, Z., Li, F.: Bidder-anonymous english auction protocol based on revocable ring signature. Expert Syst. Appl. 39(8), 7062–7066 (2012) ArticleGoogle Scholar
  35. Yuen, T.H., Liu, J.K., Au, M.H., Susilo, W., Zhou, J.: Threshold ring signature without random oracles. In: ASIACCS 2011, pp. 261–267. ACM (2011) Google Scholar
  36. Yuen, T.H., Liu, J.K., Au, M.H., Susilo, W., Zhou, J.: Efficient linkable and/or threshold ring signature without random oracles. Comput. J. 56(4), 407–421 (2013). https://doi.org/10.1093/comjnl/bxs115ArticleGoogle Scholar

Author information

Authors and Affiliations

  1. Faculty of IT, Monash University, Melbourne, Australia Xinyu Zhang, Joseph K. Liu, Ron Steinfeld, Veronika Kuchta & Jiangshan Yu
  1. Xinyu Zhang
You can also search for this author in PubMed Google Scholar You can also search for this author in PubMed Google Scholar You can also search for this author in PubMed Google Scholar You can also search for this author in PubMed Google Scholar You can also search for this author in PubMed Google Scholar

Corresponding author

Editor information

Editors and Affiliations

  1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China Zhe Liu
  2. Computer Science Department, Columbia University, New York, NY, USA Moti Yung

Appendix A. Revocable Ring Confidential Transaction

Appendix A. Revocable Ring Confidential Transaction

In Appendix A, we present a revocable ring confidential transaction protocol based on our RLRS scheme.

\(\mathtt (\lambda )\) : Let \(\mathbb \) be a group of prime order q such that underlying discrete logarithm problem is intractable. Let \(H_1 : \^* \rightarrow \mathbb _q\) and \(H_2 : \^* \rightarrow \mathbb \) be two hash functions, and g, h are two generators in \(\mathbb \) . The public parameters are \(param = \<\mathbb , g, h, q, H_1, H_2\>\)

\(\mathtt (param)\) : Randomly choose \(x \in \mathbb _q\) and compute \(y = g^x \pmod \) . The secret key is \(sk = x\) and the corresponding public key is \(pk = y\)

\(\mathtt (a, pk)\) : Given an amount a and a coin address pk, randomly choose \(r \in \mathbb _q\) and compute \(C = h^a g^r \pmod \) , where the coin in address pk is denoted as \(cn_ = C\) and the corresponding coin key \(ck = r\) . The public information of an account is \(act = (y,C)\) and the secrete information is \(ask = (x,r)\) .

\(\mathtt (A_s, R, m, t, \mathbb , M, pk_)\) : On input the spender s’s a set of m accounts \(A_s\) , a set of t output accounts R, a set of n group public keys \(\mathbb \) such that \(\mathbb = Y_1, \dots , Y_n\) , a transaction string M, and a revocation authority’s public key \(pk_ = \tilde\) . The spender s can spend his/her m accounts to t output accounts by performing following steps:

  1. 1. The spender s parses \(A_s = \\>_\) into \(\<(y_s^, C_s^), \dots , (y_s^, C_s^)\>\) and \(K_s = \\>_\) into \(\<(x_s^, r_s^), \dots , (x_s^, r_s^)\>\) where \(\ = g^>\>_\) and \(\ = h^>g^>\>_\)
  2. 2. Denote R as a set of output accounts where \(R = \^\>_\) , spender s randomly chooses \(r_1, \dots , r_t \in \mathbb _q\) and computes \(C_^j = h^g^\) for \(j \in [t]\) where \(a_^ + \dots + a_^ = a_s^ + \dots + a_s^\)
  3. 3. The spender s uses a public key encryption scheme \(ENC_(\cdot )\) with public key pk to compute the cipher text \(ctxt_j = ENC_^>(r_j)\) for \(j \in [t]\) and send \(\_\) to the corresponding receiver’s address.
  4. 4. In order to ensure that the amount of output coins equal to input coins, the spender s creates a new public key

$$\begin y_s^ = \frac<\prod _^m (y_s^\cdot C_s^)><\prod _^t C_^>. \end$$ Since \(a_^ + \dots + a_^ = a_s^ + \dots + a_s^\) , the \(m+1\) public key is $$\begin y_s^ = g^^m (x_s^ + r_s^) - \sum _^t r_j> = g^ \end$$
  1. (a) \(CT_1^ = g^\) ,
  2. (b) \(CT_2^ = \tilde^y_s^\) ,
  3. (c) Combine the cipher text \(CX_k = (CT_1^, CT_2^)\) .
  1. (a) \(a_^ = g^\) and \(a_^ = (\frac)^\) ,
  2. (b) \(c_^\prime = H_1(\mathbb , L, M, \, \dots , \)\) ,
  3. (c) \(\bar_^ = g^\) and \(\bar_^ = h_k^\) ,
  4. (d) \(c_^ <\prime \prime >= H_1(\mathbb , L, M, \<\bar_^, \bar_^\>, \dots , \<\bar_^, \bar_^\>)\) .
  1. (a) For \(i = s+1, \dots , n, 1, \dots , s-1\) , randomly pick \(v_^, \dots , v_^\) and \(v_^, \dots , v_^ \in \mathbb _q\) and compute:
  2. (b) \(a_^ = g^(CT_1^)^\) and \(a_^ = \tilde^^>(\frac)^\) for \(k \in [m+1]\) ,
  3. (c) \(c_^\prime = H_1(\mathbb , L, M, \, \dots , \)\) ,
  4. (d) \(\bar_^ = g^(y_i^)^>\) and \(\bar_^ = h_k^L_k^<(c_i^<\prime \prime >)>\) for \(k \in [m+1]\) ,
  5. (e) \(c_^ <\prime \prime >= H_1(\mathbb , L, M, \<\bar_^, \bar_^\>, \dots , \<\bar_^, \bar_^\>)\) .
  1. (a) \(v_^ = t_1^ - c_s^\prime u_k\) ,
  2. (b) \(v_^ = t_2^ - c_s^<\prime \prime >x_s^\) .

\(\mathtt (n, \mathbb , \sigma , M)\) : The algorithm takes the input of a group \(\mathbb = \\) of n groups of public keys, a signature \(\sigma \) , and a transaction string M. To verify a transaction, the verifier computes follows:

\(\mathtt (n, \mathbb , sk_, \sigma )\) : The algorithm receives a set \(\mathbb = \\) of n groups of public keys, a revocation authority’s private key \(sk_ = \tilde\) , and a valid signature \(\sigma \) . The revocation authority with the knowledge of secret key \(\tilde\) corresponding to \(\tilde\) decrypts the \(m+1\) ciphertexts to get \(m+1\) public keys which belong to the real spender as follows

  1. 1. For \(k = 1, \dots , m+1\) , parse \(CT_k = (CT_1^, CT_2^)\) .
  2. 2. Get the k-th public key \(y_s^ <\prime (k)>= CT_2^ / CT_1^>>\) and output all public keys into a set of \(Y_s^\prime = \, \dots , y_s^<\prime (m+1)>\>\) .
  3. 3. There exists a public key vector \(Y_s \in \mathbb \) such that \(Y_s = Y_s^\prime \) .