New Variants of the Square-Vinegar Signature Scheme
Keywords:
Multivariate cryptography, Square-vinegar signature scheme, Odd characteristic (es)
Downloads
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
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.
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).
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}
}
How to Cite
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Download Citation
Article abstract page views
Downloads
License
Copyright (c) 2011 Revista Colombiana de Matemáticas
This work is licensed under a Creative Commons Attribution 4.0 International License.