RingRainbow – an efficient multivariate ring signature scheme. (English) Zbl 1367.94331
Joye, Marc (ed.) et al., Progress in cryptology – AFRICACRYPT 2017. 9th international conference on cryptology in Africa, Dakar, Senegal, May 24–26, 2017. Proceedings. Cham: Springer (ISBN 978-3-319-57338-0/pbk; 978-3-319-57339-7/ebook). Lecture Notes in Computer Science 10239, 3-20 (2017).
Summary: Multivariate cryptography is one of the main candidates for creating post-quantum cryptosystems. Especially in the area of digital signatures, there exist many practical and secure multivariate schemes. However, there is a lack of more advanced schemes, such as schemes for oblivious transfer and signature schemes with special properties. While, in the last years, a number of multivariate ring signature schemes have been proposed, all of these have weaknesses in terms of security or efficiency. In this paper we propose a simple and efficient technique to extend arbitrary multivariate signature schemes to ring signature schemes and illustrate it using the example of Rainbow. The resulting scheme provides perfect anonymity for the signer (as member of a group), as well as shorter ring signatures than all previously proposed post-quantum ring signature schemes.
For the entire collection see [Zbl 1362.94001].
For the entire collection see [Zbl 1362.94001].
References:
| [1] | Aguilar, C.; Cayrel, PL; Gaborit, P.; Laguillaumie, F., A new efficient threshold ring signature scheme based on coding theory, IEEE Trans. Inf. Theory, 57, 7, 4833-4842, 2011 · Zbl 1365.94396 · doi:10.1109/TIT.2011.2145950 |
| [2] | Asaar, MR; Salmasizadeh, M.; Susilo, W., A short identity-based proxy ring signature scheme from RSA, Comput. Stand. Interfaces, 38, 144-151, 2015 · doi:10.1016/j.csi.2014.10.002 |
| [3] | Bender, A., Katz, J., Morselli, R.: Ring signatures: stronger definitions and constructions without random oracles. IACR eprint 2005/304 |
| [4] | Bernstein, DJ; Buchmann, J.; Dahmen, E., Post Quantum Cryptography, 2009, Heidelberg: Springer, Heidelberg |
| [5] | Bogdanov, A.; Eisenbarth, T.; Rupp, A.; Wolf, C.; Oswald, E.; Rohatgi, P., Time-area optimized public-key engines: \( \cal{MQ} \)-cryptosystems as replacement for elliptic curves?, Cryptographic Hardware and Embedded Systems - CHES 2008, 45-61, 2008, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-540-85053-3_4 |
| [6] | Chen, AI-T; Chen, M-S; Chen, T-R; Cheng, C-M; Ding, J.; Kuo, EL-H; Lee, FY-S; Yang, B-Y; Clavier, C.; Gaj, K., SSE implementation of multivariate PKCs on modern x86 CPUs, Cryptographic Hardware and Embedded Systems - CHES 2009, 33-48, 2009, Heidelberg: Springer, Heidelberg · Zbl 1290.94055 · doi:10.1007/978-3-642-04138-9_3 |
| [7] | Cayrel, P-L; Lindner, R.; Rückert, M.; Silva, R.; Abdalla, M.; Barreto, PSLM, A lattice-based threshold ring signature scheme, Progress in Cryptology - LATINCRYPT 2010, 255-272, 2010, Heidelberg: Springer, Heidelberg · Zbl 1285.94046 · doi:10.1007/978-3-642-14712-8_16 |
| [8] | Ding, J.; Gower, JE; Schmidt, DS, Multivariate Public Key Cryptosystems, 2006, USA: Springer, USA · Zbl 1105.94006 |
| [9] | Ding, J.; Schmidt, D.; Ioannidis, J.; Keromytis, A.; Yung, M., Rainbow, a new multivariable polynomial signature scheme, Applied Cryptography and Network Security, 164-175, 2005, Heidelberg: Springer, Heidelberg · Zbl 1126.68393 · doi:10.1007/11496137_12 |
| [10] | Franklin, M.; Zhang, H.; Sadeghi, A-R, Unique ring signatures: a practical construction, Financial Cryptography and Data Security, 162-170, 2013, Heidelberg: Springer, Heidelberg · Zbl 1524.94081 · doi:10.1007/978-3-642-39884-1_13 |
| [11] | Fujisaki, E.; Kiayias, A., Sub-linear size traceable ring signatures without random oracles, Topics in Cryptology - CT-RSA 2011, 393-415, 2011, Heidelberg: Springer, Heidelberg · Zbl 1284.94138 · doi:10.1007/978-3-642-19074-2_25 |
| [12] | Garey, MR; Johnson, DS, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, New York: W.H. Freeman and Company, New York · Zbl 0411.68039 |
| [13] | Kravitz, D.: Digital signature algorithm. US patent 5231668, July 1991 |
| [14] | Kipnis, A.; Patarin, J.; Goubin, L.; Stern, J., Unbalanced oil and vinegar signature schemes, Advances in Cryptology — EUROCRYPT’99, 206-222, 1999, Heidelberg: Springer, Heidelberg · Zbl 0933.94031 |
| [15] | Miura, H.; Hashimoto, Y.; Takagi, T.; Gaborit, P., Extended algorithm for solving underdefined multivariate quadratic equations, Post-Quantum Cryptography, 118-135, 2013, Heidelberg: Springer, Heidelberg · Zbl 1306.94076 · doi:10.1007/978-3-642-38616-9_8 |
| [16] | Petzoldt, A.; Bulygin, S.; Buchmann, J., A multivariate based threshold ring signature scheme, Appl. Algebra Eng. Commun. Comput., 24, 3-4, 255-275, 2012 · Zbl 1283.94101 |
| [17] | Petzoldt, A.; Bulygin, S.; Buchmann, J.; Sendrier, N., Selecting parameters for the rainbow signature scheme, Post-Quantum Cryptography, 218-240, 2010, Heidelberg: Springer, Heidelberg · Zbl 1286.94084 · doi:10.1007/978-3-642-12929-2_16 |
| [18] | Petzoldt, A.; Bulygin, S.; Buchmann, J.; Gong, G.; Gupta, KC, CyclicRainbow – a multivariate signature scheme with a partially cyclic public key, Progress in Cryptology - INDOCRYPT 2010, 33-48, 2010, Heidelberg: Springer, Heidelberg · Zbl 1294.94069 · doi:10.1007/978-3-642-17401-8_4 |
| [19] | Petzoldt, A.; Bulygin, S.; Buchmann, J., A multivariate threshold ring signature scheme, AAECC, 25, 3-4, 255-275, 2012 |
| [20] | Petzoldt, A.; Bulygin, S.; Buchmann, J.; Gaborit, P., Fast verification for improved versions of the UOV and rainbow signature schemes, Post-Quantum Cryptography, 188-202, 2013, Heidelberg: Springer, Heidelberg · Zbl 1306.94086 · doi:10.1007/978-3-642-38616-9_13 |
| [21] | Petzoldt, A.; Chen, M-S; Yang, B-Y; Tao, C.; Ding, J.; Iwata, T.; Cheon, JH, Design principles for HFEv-based multivariate signature schemes, Advances in Cryptology - ASIACRYPT 2015, 311-334, 2015, Heidelberg: Springer, Heidelberg · Zbl 1396.94094 · doi:10.1007/978-3-662-48797-6_14 |
| [22] | Rivest, RL; Shamir, A.; Adleman, L., A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21, 2, 120-126, 1978 · Zbl 0368.94005 · doi:10.1145/359340.359342 |
| [23] | Rivest, RL; Shamir, A.; Tauman, Y.; Boyd, C., How to leak a secret, Advances in Cryptology — ASIACRYPT 2001, 552-565, 2001, Heidelberg: Springer, Heidelberg · Zbl 1064.94558 · doi:10.1007/3-540-45682-1_32 |
| [24] | Shor, P., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26, 5, 1484-1509, 1997 · Zbl 1005.11065 · doi:10.1137/S0097539795293172 |
| [25] | Sakumoto, K.; Shirai, T.; Hiwatari, H.; Rogaway, P., Public-key identification schemes based on multivariate quadratic polynomials, Advances in Cryptology - CRYPTO 2011, 706-723, 2011, Heidelberg: Springer, Heidelberg · Zbl 1283.94104 · doi:10.1007/978-3-642-22792-9_40 |
| [26] | Thomae, E.; Wolf, C.; Fischlin, M.; Buchmann, J.; Manulis, M., Solving underdetermined systems of multivariate quadratic equations revisited, Public Key Cryptography - PKC 2012, 156-171, 2012, Heidelberg: Springer, Heidelberg · Zbl 1290.94134 · doi:10.1007/978-3-642-30057-8_10 |
| [27] | Wang, L.L.: A new multivariate-based ring signature scheme. In: Proceeedings of ISCCCA (2013) |
| [28] | Wang, S.; Ma, R.; Zhang, Y.; Wang, X., Ring signature scheme based on multivariate public key cryptosystems, Comput. Math. Appl., 62, 3973-3979, 2011 · Zbl 1236.94083 · doi:10.1016/j.camwa.2011.09.052 |
| [29] | Wang, S., Zhao, R.: Lattice-based ring signature scheme under the random oracle model (2014). CoRR abs/1405.3177 |
| [30] | Yang, B-Y; Chen, J-M; Chen, Y-H; Joye, M.; Quisquater, J-J, TTS: high-speed signatures on a low-cost smart card, Cryptographic Hardware and Embedded Systems - CHES 2004, 371-385, 2004, Heidelberg: Springer, Heidelberg · Zbl 1104.68502 · doi:10.1007/978-3-540-28632-5_27 |
| [31] | Zhang, J.; Zhao, Y.; Au, MH; Carminati, B.; Kuo, C-CJ, A new multivariate based threshold ring signature scheme, Network and System Security, 526-533, 2014, Cham: Springer, Cham |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
