# 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  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] 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 [2] Liqin Qian, Xiwang Cao. Character sums over a non-chain ring and their applications. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020134 [3] Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225 [4] Johannes Kellendonk, Lorenzo Sadun. Conjugacies of model sets. Discrete & Continuous Dynamical Systems - A, 2017, 37 (7) : 3805-3830. doi: 10.3934/dcds.2017161 [5] Didier Bresch, Thierry Colin, Emmanuel Grenier, Benjamin Ribba, Olivier Saut. A viscoelastic model for avascular tumor growth. Conference Publications, 2009, 2009 (Special) : 101-108. doi: 10.3934/proc.2009.2009.101 [6] Ondrej Budáč, Michael Herrmann, Barbara Niethammer, Andrej Spielmann. On a model for mass aggregation with maximal size. Kinetic & Related Models, 2011, 4 (2) : 427-439. doi: 10.3934/krm.2011.4.427 [7] Martin Bohner, Sabrina Streipert. Optimal harvesting policy for the Beverton--Holt model. Mathematical Biosciences & Engineering, 2016, 13 (4) : 673-695. doi: 10.3934/mbe.2016014 [8] Juan Manuel Pastor, Javier García-Algarra, Javier Galeano, José María Iriondo, José J. Ramasco. A simple and bounded model of population dynamics for mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 53-70. doi: 10.3934/nhm.2015.10.53 [9] Chin-Chin Wu. Existence of traveling wavefront for discrete bistable competition model. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 973-984. doi: 10.3934/dcdsb.2011.16.973 [10] Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089 [11] Alba Málaga Sabogal, Serge Troubetzkoy. Minimality of the Ehrenfest wind-tree model. Journal of Modern Dynamics, 2016, 10: 209-228. doi: 10.3934/jmd.2016.10.209 [12] Raghda A. M. Attia, Dumitru Baleanu, Dianchen Lu, Mostafa M. A. Khater, El-Sayed Ahmed. Computational and numerical simulations for the deoxyribonucleic acid (DNA) model. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021018 [13] Seung-Yeal Ha, Jinwook Jung, Jeongho Kim, Jinyeong Park, Xiongtao Zhang. A mean-field limit of the particle swarmalator model. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021011 [14] Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183 [15] Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1 [16] Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623 [17] Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367 [18] Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021035 [19] Guirong Jiang, Qishao Lu. The dynamics of a Prey-Predator model with impulsive state feedback control. Discrete & Continuous Dynamical Systems - B, 2006, 6 (6) : 1301-1320. doi: 10.3934/dcdsb.2006.6.1301 [20] Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401

2019 Impact Factor: 0.734