×

A multivariate based threshold ring signature scheme. (English) Zbl 1283.94101

Summary: In [Crypto 2011, Lect. Notes Comput. Sci. 6841, 706–723 (2011; Zbl 1283.94104)], K. Sakumoto et al. presented a new multivariate identification scheme, whose security is based solely on the MQ-problem of solving systems of quadratic equations over finite fields. In this paper we extend this scheme to a threshold ring identification and signature scheme. Our scheme is the first multivariate scheme of this type and generally one of the first multivariate signature schemes with special properties. Despite of the fact that we need more rounds to achieve given levels of security, the signatures are at least twice shorter than those obtained by other post-quantum (e.g. code-based) constructions. Furthermore, our scheme offers provable security, which is quite a rare fact in multivariate cryptography.

MSC:

94A62 Authentication, digital signatures and secret sharing
94A60 Cryptography

Citations:

Zbl 1283.94104
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aguilar, C., Cayrel, P.L., 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] Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): Post Quantum Cryptography. Springer, Berlin (2009) · Zbl 1155.81007
[3] Bettale, L., Faugère, J.C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol. 177-197 (2009) · Zbl 1183.94021
[4] Bogdanov, A., Eisenbarth, T., Rupp, A., Wolf, C.: Time-area optimized public-key engines: -cryptosystems as replacement for elliptic curves? In: CHES, LNCS vol. 5154, pp. 45-61. Springer, Berlin (2008) · Zbl 1365.94396
[5] Bouillaguet, C., Chen, H.-C., Cheng, C.-M., Chou, T., Niederhagen, R., Shamir, A., Yang, B.-Y.: Fast exhaustive search for polynomial systems in F2. In: CHES 2010, LNCS vol. 6225, pp. 203-218. Springer, Berlin (2010) · Zbl 1297.94055
[6] Boyen, X.: Mesh signatures. In: EUROCRYPT 2007, LNCS vol. 4515, pp. 210-227. Springer, Berlin (2007) · Zbl 1141.94342
[7] Bresson, E., Stern, J., Szydlo, M.: Threshold ring signatures and their application to ad-hoc groups. In: CRYPTO 2002, LNCS vol. 2442, pp. 465-480. Springer, Berlin (2002) · Zbl 1026.94544
[8] Cayrel, P.L., Lindner, R., Rückert, M., Silva, R.: A lattice-based threshold ring signature scheme. In: LATINCRYPT 2010, LNCS vol. 6212, pp. 255-272. Springer, Berlin (2010) · Zbl 1285.94046
[9] Chen, A.I.T., Chen, M.-S., Chen, T.-R., Cheng, C.-M., Ding, J., Kuo, E.L.-H., Lee, F.Y.-S., Yang, B.-Y.: SSE implementation of multivariate pkcs on modern x86 cpus. In: CHES 2009, LNCS vol. 5747, pp. 33-48. Springer, Berlin (2009) · Zbl 1290.94055
[10] Ding, J., Gower, J.E., Schmidt, D.: Multivariate Public Key Cryptosystems. Springer, Berlin (2006) · Zbl 1105.94006
[11] Faugère, J.C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: ISSAC 2002, pp. 75-83. ACM Press, New York (2002) · Zbl 1072.68664
[12] Fiat, A., Shamir, A.: How to Prove Yourself. In: CRYPTO 1986, LNCS vol. 263, pp. 186-194. Springer, Berlin (1986) · Zbl 0931.94030
[13] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979) · Zbl 0411.68039
[14] Kipnis, A.; Shamir, A.; Krawzyck, H. (ed.), Cryptanalysis of the oil and vinegar signature scheme, 257-266 (1998), Heidelberg · Zbl 0931.94030
[15] Liu, J.K., Wei, V.K., Wong, D.S.: A separable threshold ring signature scheme. In: ICISC 2003, LNCS vol. 2971, pp. 352-369. Springer, Berlin (2003)
[16] Nachef, V., Patarin, J., Volte, E.: Zero-knowledge for multivariate polynomials. In: Latincrypt 2012, LNCS vol. 7533, pp. 194-213. Springer, Berlin (2012) · Zbl 1304.94104
[17] Pointcheval, P., Stern, J.: Security proofs for signature schemes. In: EUROCRYPT 96, LNCS vol. 1070, pp. 387-398. Springer, Berlin (1996) · Zbl 1304.94106
[18] Sakumoto, K.: Public-key identification schemes based on multivariate cubic polynomials. In: PKC 2012, LNCS vol. 7293, pp. 172-189. Springer, Berlin (2012) · Zbl 1290.94127
[19] Sakumoto, K., Shirai, T., Hiwatari, H.: Public-key identification schemes based on multivariate quadratic polynomials. In: CRYPTO 2011, LNCS vol. 6841, pp. 706-723. Springer, Berlin (2011) · Zbl 1283.94104
[20] Shor, P.W.: 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
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.