Top

Applicable Algebra in Engineering, Communication and Computing

Published in:

01-08-2013 | Original Paper

A multivariate based threshold ring signature scheme

Authors: Albrecht Petzoldt, Stanislav Bulygin, Johannes Buchmann

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 3-4/2013

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In Sakumoto et al. (CRYPTO 2011, LNCS, vol 6841. Springer, Berlin, pp 706–723, 2011), 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.

previous article List decoding of repeated codes

next article E-commerce of digital items and the problem of item validation: introducing the concept of reversible degradation

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

To achieve given levels of security, it might be necessary to run the identification scheme several (say \(r\)) times. In this case, the challenge is given as \(Ch={\fancyscript{R}}(m, \mathrm{com}_1, \ldots , \mathrm{com}_M)\) and the signature has the form \(\sigma =(\mathrm{com}_1, \ldots , \mathrm{com}_r, Rsp_1, \ldots , Rsp_r)\).

In practice this is realized by a collision- and pre-image resistant hash function.

In fact, an affine system is called regular if and only if its homogeneous part of highest degree is regular [3]. From this definition one can obtain complexity estimates for affine systems.

For 193 rounds (corresponds to 80 bit security) the length of the hash value must be \(\ge 386\) bits.

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)CrossRef

Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): Post Quantum Cryptography. Springer, Berlin (2009)MATH

Bettale, L., Faugère, J.C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol. 177–197 (2009)

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)

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)

Boyen, X.: Mesh signatures. In: EUROCRYPT 2007, LNCS vol. 4515, pp. 210–227. Springer, Berlin (2007)

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)

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)

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)

10.

Ding, J., Gower, J.E., Schmidt, D.: Multivariate Public Key Cryptosystems. Springer, Berlin (2006)MATH

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)

12.

Fiat, A., Shamir, A.: How to Prove Yourself. In: CRYPTO 1986, LNCS vol. 263, pp. 186–194. Springer, Berlin (1986)

13.

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)MATH

14.

Kipnis, A., Shamir, A.: Cryptanalysis of the oil and vinegar signature scheme. In: Krawzyck, H. (ed.) CRYPTO 1998, LNCS vol. 1462, pp. 257–266. Springer, Heidelberg (1998)

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)

17.

Pointcheval, P., Stern, J.: Security proofs for signature schemes. In: EUROCRYPT 96, LNCS vol. 1070, pp. 387–398. Springer, Berlin (1996)

18.

Sakumoto, K.: Public-key identification schemes based on multivariate cubic polynomials. In: PKC 2012, LNCS vol. 7293, pp. 172–189. Springer, Berlin (2012)

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)

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)MathSciNetMATHCrossRef

Title: A multivariate based threshold ring signature scheme
Authors: Albrecht Petzoldt
Stanislav Bulygin
Johannes Buchmann
Publication date: 01-08-2013
Publisher: Springer Berlin Heidelberg
Published in: Applicable Algebra in Engineering, Communication and Computing / Issue 3-4/2013
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-013-0190-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3-4/2013

On transitive parallelisms of $$PG(3,4)$$ P G ( 3 , 4 )

Permutation decoding of codes from generalized Paley graphs

On optimal binary codes with unbalanced coordinates

Classification of the odd sets in $$\hbox {PG}(4,4)$$ PG ( 4 , 4 ) and its application to coding theory

List decoding of repeated codes

E-commerce of digital items and the problem of item validation: introducing the concept of reversible degradation

Premium Partner