New Variants of the Square-Vinegar Signature Scheme

This paper proposes two ways to fix the broken Square-Vinegar signature scheme. We give heuristic arguments as well as experimental evidence to support the security claims. The first variant, Square-Vinegar with Embedding, uses a simple modification that nonetheless changes the nature of the public key polynomials. The second, 2-Square-Vinegar, is a more significant overhaul of the construction, using a bivariate secret map instead of a univariate one.

New Variants of the Square-Vinegar Signature Scheme Nuevas variantes del esquema de firmas Square-Vinegar JOHN B. BAENA1, CRYSTAL LEE CLOUGH2, JINTAI DING3

1Universidad Nacional de Colombia, Medellín, Colombia. Email:jbbaena@unal.edu.co 
2Thomas More College, Crestview Hills, United States. Email:crystal.clough@gmail.com 
3University of Cincinnati, Cincinnati, United States. Email: jintai.ding@uc.edu

---

Abstract

This paper proposes two ways to fix the broken Square-Vinegar signature scheme. We give heuristic arguments as well as experimental evidence to support the security claims. The first variant, Square-Vinegar with Embedding, uses a simple modification that nonetheless changes the nature of the public key polynomials. The second, 2-Square-Vinegar, is a more significant overhaul of the construction, using a bivariate secret map instead of a univariate one.

Key words: Multivariate cryptography, Square-vinegar signature scheme, Odd characteristic.

---

2000 Mathematics Subject Classification: 11T71, 11Y40.

---

Resumen

Este artículo propone dos maneras de arreglar el esquema de firmas Square-Vinegar, el cual ha sido roto. Suministramos argumentos heurísticos, así como evidencia experimental para apoyar nuestras afirmaciones sobre seguridad. La primera variante, Square-Vinegar con inmersión, a pesar de usar una modificación simple, cambia la naturaleza de los polinomios de la clave pública. La segunda, 2-Square-Vinegar, es una revisión más significativa de la construcción, con una función secreta bivariada en lugar de una univariada.

Palabras clave: Criptografía multivariada, esquema de firmas Square-Vinegar, característica impar.

---

Texto completo disponible en PDF

---

References

[1] J. Baena, C. Clough, and J. Ding, Square-Vinegar Signature Scheme, `Proceedings of the 2nd International Workshop on Post-Quantum Cryptography - PQCrypto2008´, (2008), Lecture Notes in Computer Science, Springer, p. 17-30.

[2] O. Billet and G. Macario-Rat (2009), Cryptanalysis of the Square Cryptosystems, `ASIACRYPT´, p. 451-468.

[3] N. T. Courtois, M. Daum, and P. Felke, On the security of HFE, HFEv- and Quartz, `Public key cryptography-PKC 2003´, (2002), Vol. 2567, Lecture Notes in Comput. Sci., Springer, Berlin, Germany, p. 337-350.

[4] J. Ding, D. Schmidt, and F. Werner, Algebraic Attack on HFE Revisited, `ISC Information Security, 11th International Conference, ISC 2008, Taipei, Taiwan, September 15-18, 2008. Proceedings´, (2008), Vol. 5222 ofLecture Notes in Computer Science, Springer, p. 215-227.

[5] V. Dubois, Pierre-Alain Fouque, A. Shamir, and J. Stern, Practical Cryptanalysis of SFLASH, `CRYPTO´, (2007), p. 1-12.

[6] M. R. Garey, D. S. Johnson, and others, Computers and Intractability: A Guide to the Theory of NP-completeness, WH Freeman San Francisco, 1979.

[7] A. Kipnis and A. Shamir, Cryptanalysis of the Oil and Vinegar Signature Scheme, `Advances in Cryptology-CRYPTO '98 (Santa Barbara, CA, 1998)´, 1998, Vol. 1462 of Lecture Notes in Comput. Sci., Springer, Berlin, Germany, p. 257-266.

[8] A. Kipnis and A. Shamir, Cryptanalysis of the HFE Public key Cryptosystem by Relinearization, `Advances in Cryptology-CRYPTO '99 (Santa Barbara, CA)´, 1999, Vol. 1666 of Lecture Notes in Comput. Sci., Springer, Berlin, Germany, p. 19-30.

[9] J. Patarin, Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms, `Advances in Cryptology-EUROCRYPT 96´, (1996), Vol. 1070 of Lecture Notes in Computer Science, Springer-Verlag, p. 33-48.

[10] J. Patarin, `Oil and Vinegar Signature Scheme´, Dagstuhl Workshop on Cryptography, (1997).

[11] J. Patarin, N. Courtois, and L. Goubin, QUARTZ, 128-bit Long Digital Signatures, `Topics in cryptology-CT-RSA 2001 (San Francisco, CA)´, 2001, Vol. 2020 of Lecture Notes in Comput. Sci., Springer, Berlin, Germany, p. 282-297.

[12] C. Wolf and B. Preneel, Asymmetric Cryptography: Hidden Field Equations, `European Congress on Computational Methods in Applied Sciences and Engineering´, (2004).

(Recibido en febrero de 2011. Aceptado en octubre de 2011)

---

Este artículo se puede citar en LaTeX utilizando la siguiente referencia bibliográfica de BibTeX:

@ARTICLE{RCMv45n2a04, 
    AUTHOR  = {Baena, John B. and Clough, Crystal Lee and Ding, Jintai}, 
    TITLE   = {{New Variants of the Square-Vinegar Signature Scheme}}, 
    JOURNAL = {Revista Colombiana de Matemáticas}, 
    YEAR    = {2011}, 
    volume  = {45}, 
    number  = {2}, 
    pages   = {147--166} 
}