# American Institute of Mathematical Sciences

May  2020, 14(2): 207-232. doi: 10.3934/amc.2020016

## Efficient traceable ring signature scheme without pairings

 School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410114, China

* Corresponding author: Ke Gu

Received  February 2018 Revised  March 2019 Published  May 2020 Early access  September 2019

Fund Project: This work is supported by the National Natural Science Foundations of China (No.61402055), the Hunan Provincial Natural Science Foundation of China (No.2018JJ2445) and the Open Research Fund of Key Laboratory of Network Crime Investigation of Hunan Provincial Colleges (No.2017WLFZZC003)

Although currently several traceable (or linkable) ring signature schemes have been proposed, most of them are constructed on pairings. In this paper, we present an efficient traceable ring signature (TRS) scheme without pairings, which is based on the modified EDL signature (first proposed by D.Chaum et al. in Crypto 92). Compared with other ring signature schemes, the proposed scheme does not employ pairing computation and has some computational advantages, whose security can be reduced to the computational Diffie-Hellman (CDH) and decisional Diffie-Hellman (DDH) assumptions in the random oracle model. Also, the proposed scheme is similar to certificateless signature scheme, where user and key generating center make interaction to generate ring key. We give a formal security model for ring signature and prove that the proposed scheme has the properties of traceability and anonymity.

Citation: Ke Gu, Xinying Dong, Linyu Wang. Efficient traceable ring signature scheme without pairings. Advances in Mathematics of Communications, 2020, 14 (2) : 207-232. doi: 10.3934/amc.2020016
##### References:

show all references

##### References:
Performance comparisons of the Six Schemes
 Signature Size Signing Cost Verification Cost Scheme [40] $O(n)$ $(4\cdot n+3)\cdot e_1+2\cdot n\cdot m_1$ $4\cdot n\cdot e_1+n\cdot m_1$ Scheme [55] $O(n)$ $(28\cdot n+9)\cdot m_3+(22\cdot n+14)\cdot a$ $28\cdot n\cdot m_3+19\cdot n\cdot a$ Scheme [25] $O(\sqrt{n})$ $(n+9)\cdot e_1+(n+2)\cdot m_1$ $(2\cdot n+3)\cdot e_1+2\cdot n\cdot m_1+9\cdot p$ Scheme [26] $O(n)$ $(5\cdot n-1)e_1+(3\cdot n-2)\cdot m_1$ $5\cdot n\cdot e_1+3\cdot n\cdot m_1$ Scheme [4] $O(1)$ $7\cdot e_1+7\cdot m_1$ $9\cdot e_1+5\cdot m_1+7\cdot e_2+8\cdot m_2+12\cdot p$ Our Scheme $O(1)$ $5\cdot e_1+(n+1)\cdot m_1$ $4\cdot e_1+(n+3)\cdot m_1$
 Signature Size Signing Cost Verification Cost Scheme [40] $O(n)$ $(4\cdot n+3)\cdot e_1+2\cdot n\cdot m_1$ $4\cdot n\cdot e_1+n\cdot m_1$ Scheme [55] $O(n)$ $(28\cdot n+9)\cdot m_3+(22\cdot n+14)\cdot a$ $28\cdot n\cdot m_3+19\cdot n\cdot a$ Scheme [25] $O(\sqrt{n})$ $(n+9)\cdot e_1+(n+2)\cdot m_1$ $(2\cdot n+3)\cdot e_1+2\cdot n\cdot m_1+9\cdot p$ Scheme [26] $O(n)$ $(5\cdot n-1)e_1+(3\cdot n-2)\cdot m_1$ $5\cdot n\cdot e_1+3\cdot n\cdot m_1$ Scheme [4] $O(1)$ $7\cdot e_1+7\cdot m_1$ $9\cdot e_1+5\cdot m_1+7\cdot e_2+8\cdot m_2+12\cdot p$ Our Scheme $O(1)$ $5\cdot e_1+(n+1)\cdot m_1$ $4\cdot e_1+(n+3)\cdot m_1$
Other comparisons of the Six Schemes
 Cryptography Traceability Model Scheme [40] Public Key No random oracle Scheme [55] Public Key No random oracle Scheme [25] Public Key Yes without random oracle Scheme [26] Public Key Yes random oracle Scheme [4] Identity-Based Yes random oracle Our Scheme Public Key Yes random oracle
 Cryptography Traceability Model Scheme [40] Public Key No random oracle Scheme [55] Public Key No random oracle Scheme [25] Public Key Yes without random oracle Scheme [26] Public Key Yes random oracle Scheme [4] Identity-Based Yes random oracle Our Scheme Public Key Yes random oracle
 [1] Philip Lafrance, Alfred Menezes. On the security of the WOTS-PRF signature scheme. Advances in Mathematics of Communications, 2019, 13 (1) : 185-193. doi: 10.3934/amc.2019012 [2] Meenakshi Kansal, Ratna Dutta, Sourav Mukhopadhyay. Group signature from lattices preserving forward security in dynamic setting. Advances in Mathematics of Communications, 2020, 14 (4) : 535-553. doi: 10.3934/amc.2020027 [3] Yang Lu, Quanling Zhang, Jiguo Li. An improved certificateless strong key-insulated signature scheme in the standard model. Advances in Mathematics of Communications, 2015, 9 (3) : 353-373. doi: 10.3934/amc.2015.9.353 [4] Satoshi Kosugi, Yoshihisa Morita. Phase pattern in a Ginzburg-Landau model with a discontinuous coefficient in a ring. Discrete and Continuous Dynamical Systems, 2006, 14 (1) : 149-168. doi: 10.3934/dcds.2006.14.149 [5] Yang Lu, Jiguo Li. Forward-secure identity-based encryption with direct chosen-ciphertext security in the standard model. Advances in Mathematics of Communications, 2017, 11 (1) : 161-177. doi: 10.3934/amc.2017010 [6] Joseph G. Conlon, André Schlichting. A non-local problem for the Fokker-Planck equation related to the Becker-Döring model. Discrete and Continuous Dynamical Systems, 2019, 39 (4) : 1821-1889. doi: 10.3934/dcds.2019079 [7] Koray Karabina, Edward Knapp, Alfred Menezes. Generalizations of Verheul's theorem to asymmetric pairings. Advances in Mathematics of Communications, 2013, 7 (1) : 103-111. doi: 10.3934/amc.2013.7.103 [8] José Moreira, Marcel Fernández, Miguel Soriano. On the relationship between the traceability properties of Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (4) : 467-478. doi: 10.3934/amc.2012.6.467 [9] Neal Koblitz, Alfred Menezes. Another look at security definitions. Advances in Mathematics of Communications, 2013, 7 (1) : 1-38. doi: 10.3934/amc.2013.7.1 [10] Isabelle Déchène. On the security of generalized Jacobian cryptosystems. Advances in Mathematics of Communications, 2007, 1 (4) : 413-426. doi: 10.3934/amc.2007.1.413 [11] Sumit Kumar Debnath, Tanmay Choudhury, Pantelimon Stănică, Kunal Dey, Nibedita Kundu. Delegating signing rights in a multivariate proxy signature scheme. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021016 [12] Lisa C. Jeffrey and Frances C. Kirwan. Intersection pairings in moduli spaces of holomorphic bundles on a Riemann surface. Electronic Research Announcements, 1995, 1: 57-71. [13] Stefanella Boatto. Curvature perturbations and stability of a ring of vortices. Discrete and Continuous Dynamical Systems - B, 2008, 10 (2&3, September) : 349-375. doi: 10.3934/dcdsb.2008.10.349 [14] Jie Xu, Lanjun Dang. An efficient RFID anonymous batch authentication protocol based on group signature. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1489-1500. doi: 10.3934/dcdss.2019102 [15] Jintai Ding, Zheng Zhang, Joshua Deaton. The singularity attack to the multivariate signature scheme HIMQ-3. Advances in Mathematics of Communications, 2021, 15 (1) : 65-72. doi: 10.3934/amc.2020043 [16] Fioralba Cakoni, Heejin Lee, Peter Monk, Yangwen Zhang. A spectral target signature for thin surfaces with higher order jump conditions. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2022020 [17] Palash Sarkar, Subhadip Singha. Verifying solutions to LWE with implications for concrete security. Advances in Mathematics of Communications, 2021, 15 (2) : 257-266. doi: 10.3934/amc.2020057 [18] Roberto Civino, Riccardo Longo. Formal security proof for a scheme on a topological network. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021009 [19] Riccardo Aragona, Alessio Meneghetti. Type-preserving matrices and security of block ciphers. Advances in Mathematics of Communications, 2019, 13 (2) : 235-251. doi: 10.3934/amc.2019016 [20] Archana Prashanth Joshi, Meng Han, Yan Wang. A survey on security and privacy issues of blockchain technology. Mathematical Foundations of Computing, 2018, 1 (2) : 121-147. doi: 10.3934/mfc.2018007

2020 Impact Factor: 0.935