Journal of Information Security and Cryptography (Enigma)
Email this article Proposal of Enhancement for Quartz Digital Signature
Abstract
Today, we see a large dependence on systems
developed with cryptography. Especially in terms of public key
cryptosystems, which are widely used on the Internet. However,
public key cryptography was threatened and new sources began
to be investigated when Shor in 1997 developed a polynomial
time algorithm for factoring integers and to compute the discrete
logarithm with a quantum computer. In this context, Patarin
proposed Hidden Field Equations (HFE), a trapdoor based on
𝓜𝓜𝓜𝓜 (𝓜𝓜ultivariate 𝓠𝓠uadratic) and IP (Isomorphism of
Polynomials) problems. Such problems are not affected by the
Shor algorithm, moreover 𝓜𝓜𝓜𝓜 Problem was proved by Patarin
and Goubin to be NP-complete. Despite the basic HFE has been
broken, there are variants that are secure, obtained by a generic
modification. The Quartz – digital signature scheme based on
HFEv-, with special choice of parameters – is a good example of
this resistance to algebraic attacks aimed at the recovery of the
private key, because even today it remains secure. Furthermore,
it also generates short signatures. However, Joux and Martinet,
based on axioms of Birthday Paradox Attack, proved that Quartz
is malleable, showing that if the adversary has a valid pair
(message, signature), he can get a second signature with 𝟐𝟐𝟓𝟓𝟓𝟓
computations and 𝟐𝟐𝟓𝟓𝟓𝟓 calls to the signing oracle, so that the
estimated current security standards are at least 𝟐𝟐𝟏𝟏𝟏𝟏𝟏𝟏. Thus,
based on Quartz, we present a new digital signature scheme,
achieving the adaptive chosen message attacks that make calls to
the random oracle, with a security level estimated at 𝟐𝟐𝟏𝟏𝟏𝟏𝟏𝟏. Our
cryptosystem also provides an efficiency gain in signature
verification algorithm and vector initializations that will be used
for signing and verification algorithms. Furthermore we provide
an implementation of Original Quartz and Enhanced Quartz in
the Java programming language.
Keywords
Full Text:
PDF (Português (Brasil))References
Elaine Barker and Allen Roginsky. NIST Special Publication 800-131a
- Transitions: Recommendation for Transitioning the Use of
Cryptographic Algorithms and Key Lengths. Technical report, National
Institute of Standards and Technology, NIST, U.S. Department of
Commerce, Washington DC.
http://csrc.nist.gov/publications/nistpubs/800-131A/sp800-131A.pdf,
Último acesso em 09/07/2013.
Mihir Bellare and Phillip Rogaway. The exact security of digital
signatures: How to sign with RSA and Rabin. In U. Maurer, editor,
Advances in Cryptology - EUROCRYPT 96 Proceedings, volume 1070
of Lecture Notes in Computer Science, pages 399–416. Springer-
Verlag, 1996.
Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, editors.
Post-Quantum Cryptography. Springer, 2009.
Luk Bettale, Jean-Charles Faugère, and Ludovic Perret. Cryptanalysis
of HFE, multi-HFE and variants for odd and even characteristic.
Designs, Codes and Cryptography, pages 1–52, 2012.
Charles Bouillaguet, Hsieh-Chung Chen, Chen-Mou Cheng, Tung
Chou, Ruben Niederhagen, Adi Shamir, and Bo-Yin Yang. Fast
Exhaustive Search for Polynomial Systems in 𝔽𝔽2. In Stefan Mangard
and François-Xavier Standaert, editors, Cryptographic Hardware and
Embedded Systems, CHES 2010, volume 6225 of Lecture Notes in
Computer Science, pages 203–218. Springer Berlin Heidelberg, 2010.
Charles Bouillaguet, Jean-Charles Faugère, Pierre-Alain Fouque, and
Ludovic Perret. Practical Cryptanalysis of the Identification Scheme
Based on the Isomorphism of Polynomial with One Secret Problem. In
Dario Catalano, Nelly Fazio, Rosario Gennaro, and Antonio Nicolosi,
editors, Public Key Cryptography - PKC 2011, volume 6571 of Lecture
Notes in Computer Science, pages 473–493. Springer Berlin
Heidelberg, 2011.
An Braeken, Christopher Wolf, and Bart Preneel. A study of the
security of Unbalanced Oil and Vinegar signature schemes. Cryptology
ePrint Archive, Report 2004/222. http://eprint.iacr.org/2004/222, 2004.
Último acesso em 11/06/2013.
Jean charles Faugère. A new efficient algorithm for computing Gröbner
Bases without reduction to zero (F5). In ISSAC 02: Proceedings of the
International Symposium on Symbolic and Algebraic
Computation, pages 75–83, 2002.
Nicolas Courtois, Louis Goubin, Willi Meier, and Jean-Daniel Tacier.
Solving underdefined systems of multivariate quadratic equations. In
David Naccache and Pascal Paillier, editors, Public Key Cryptography,
volume 2274 of Lecture Notes in Computer Science, pages 211–227.
Springer Berlin Heidelberg, 2002.
Nicolas Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir.
Efficient algorithms for solving overdefined systems of multivariate
polynomial equations. In Bart Preneel, editor, Advances in Cryptology -
EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer
Science, pages 392–407. Springer Berlin Heidelberg, 2000.
Nicolas T. Courtois. The security of Hidden Field Equations (HFE). In
David Naccache, editor, Topics in Cryptology - CT-RSA 2001, volume
of Lecture Notes in Computer Science, pages 266–281. Springer
Berlin Heidelberg, 2001.
Nicolas T. Courtois. Generic Attacks and the Security of Quartz. In
YvoG. Desmedt, editor, Public Key Cryptography - PKC 2003, volume
of Lecture Notes in Computer Science, pages 351–364. Springer
Berlin Heidelberg, 2002.
Nicolas T. Courtois. Short signatures, provable security, generic attacks
and computational security of multivariate polynomial schemes such as
HFE, QUARTZ and SFLASH. Cryptology ePrint Archive, Report
/143. http://eprint.iacr.org/2004/143, 2004. Versão extendida e
revista do artigo Generic Attacks and the Security of Quartz publicado
no PKC 2003. Último acesso em 12/06/2013.
Nicolas T. Courtois, Louis Goubin, and Jacques Patarin. Quartz, na
asymmetric signature scheme for short signatures on PC. Primitive
specification and supporting documentation (second revised version),
David Deutsch. Quantum theory, the Church-Turing principle and the
universal quantum computer. Proceedings of the Royal Society of
London Ser. A, A400:97–117, 1985.
Jintai Ding, Jason E. Gower, and Dieter Schmidt. Multivariate public
key cryptosystems, volume 25 of Advances in information security.
Springer, 2006.
Jintai Ding and TimothyJ. Hodges. Inverting HFE systems is quasipolynomial
for all fields. In Phillip Rogaway, editor, Advances in
Cryptology - CRYPTO 2011, volume 6841 of Lecture Notes in
Computer Science, pages 724–742. Springer Berlin Heidelberg, 2011.
Jintai Ding and Dieter Schmidt. Cryptanalysis of HFEv and Internal
Perturbation of HFE. In Serge Vaudenay, editor, Public Key
Cryptography - PKC 2005, volume 3386 of Lecture Notes in Computer
Science, pages 288–301. Springer Berlin Heidelberg, 2005.
Jintai Ding, Dieter Schmidt, and Fabian Werner. Algebraic attack on
HFE revisited. In Tzong-Chen Wu, Chin-Laung Lei, Vincent Rijmen,
and Der-Tsai Lee, editors, Information Security, volume 5222 of
Lecture Notes in Computer Science, pages 215–227. Springer Berlin
Heidelberg, 2008.
Emmanuelle Dottax and École Normale Supérieure. Tweak reviews:
ES-IGN, RSA-PSS, QUARTZ and SFLASH.
NES/DOC/ENS/WP1/018/1. Technical report, Commission of the
European Communities, out 2002. Último acesso em 04/07/2013.
Jean-Charles Faugère. Algebraic cryptanalysis of HFE using gröbner
bases, February 2003.
Jean-Charles Faugère and Antoine Joux. Algebraic cryptanalysis of
Hidden Field Equation (HFE) cryptosystems using gröbner bases. In
Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, volume
of Lecture Notes in Computer Science, pages 44–60. Springer
Berlin Heidelberg, 2003.
Adam Thomas Feldmann. A survey of attacks on Multivariate
Cryptosystems. Master’s thesis, University of Waterloo, Ontario,
Canada, 2005.
Patrick Felke. On the Affine Transformations of HFE-Cryptosystems
and Systems with Branches. Cryptology ePrint Archive, Report
/367. http://eprint.iacr.org/2004/367, 2004. Último acesso em
/07/2013.
Python Software Foundation. 14.1. hashlib – Secure hashes and
message digests. https://docs.python.org/2/library/hashlib.html, 2015.
Último acesso em 31/01/2015.
Python Software Foundation. pysha3 0.3.
https://pypi.python.org/pypi/pysha3/, 2015. Último acesso em
/01/2015.
A.S. Fraenkel and Y. Yesha. Complexity of problems in games, graphs
and algebraic equations. Discrete Applied Mathematics, 1(1–2):15–30,
September 1979.
Michael R. A. Garey and David S. Johnson. Computers and
Intractability: A Guide to the Theory of NP-Completeness. A Series of
Books in the Mathematical Sciences. W. H. Freeman, 1979.
Henri Gilbert and Marine Minier. Cryptanalysis of SFLASH. In LarsR.
Knudsen, editor, Advances in Cryptology - EUROCRYPT 2002, volume
of Lecture Notes in Computer Science, pages 288–298. Springer
Berlin Heidelberg, 2002.
Louis Granboulan, Antoine Joux, and Jacques Stern. Inverting HFE is
Quasipolynomial. In Cynthia Dwork, editor, Advances in Cryptology -
CRYPTO 2006, volume 4117 of Lecture Notes in Computer Science,
pages 345–356. Springer Berlin Heidelberg, 2006.
Shu jen Chang, Ray Perlner, William E. Burr, Meltem Sönmez Turan,
John M. Kelsey, Souradyuti Paul, and Lawrence E. Bassham. NIST
Interagency or Internal Reports 7896: Third-Round Report of the SHA-
Cryptographic Hash Algorithm Competition. Technical report,
National Institute of Standards and Technology, NIST, U.S.
Department of Commerce, Washington DC.
http://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf, 2012.
Último acesso em 09/07/2013.
Xin Jiang, Jintai Ding, and Lei Hu. Kipnis-shamir attack on HFE
revisited. In Dingyi Pei, Moti Yung, Dongdai Lin, and Chuankun Wu,
editors, Information Security and Cryptology, volume 4990 of Lecture
ENIGMA — Brazilian Journal of Information Security and C 15 ryptography, Vol. 1, No. 2, Sep. 2015
Notes in Computer Science, pages 399–411. Springer Berlin
Heidelberg, 2008.
Antoine Joux and Gwenaëlle Martinet. Some weaknesses in Quartz
Signature Scheme. NES/DOC/ENS/WP5/026/1. Technical report,
Commission of the European Communities, jan 2003. Último acesso
em 12/06/2013.
Aviad Kipnis, Jacques Patarin, and Louis Goubin. Unbalanced Oil and
Vinegar signature schemes. In Jacques Stern, editor, Advances in
Cryptology - EUROCRYPT 99, volume 1592 of Lecture Notes in
Computer Science, pages 206–222. Springer Berlin Heidelberg, 1999.
Aviad Kipnis and Adi Shamir. Cryptanalysis of the HFE Public Key
Cryptosystem by Relinearization. In CRYPTO 99: Proceedings of the
th Annual International Cryptology Conference on Advances in
Cryptology, pages 19–30, London, UK, 1999. Springer-Verlag.
Dongdai Lin, Jean-Charles Faugère, Ludovic Perret, and Tianze Wang.
On enumeration of polynomial equivalence classes and their
application to MPKC. Cryptology ePrint Archive, Report 2011/055.
http://eprint.iacr.org/2011/055, 2011. Último acesso em 29/06/2013.
Gwenaëlle Martinet and École Normale Supérieure. QUARTZ, FLASH
and SFLASH. NES/DOC/ENS/WP3/006/2. Technical report,
Commission of the European Communities, mar 2001. Último acesso
em 14/06/2013.
NESSIE. Final report of European project IST-1999-12324: New
European Schemes for Signatures, Integrity, and Encryption (NESSIE),
(Abril de 2004).
https://www.cosic.esat.kuleuven.be/nessie/Bookv015.pdf. Technical
report, Commission of the European Communities, Abril 2004. Último
acesso em 10/06/2013.
Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and
Quantum Information: 10th Anniversary Edition. Cambridge University
Press, 2010.
NIST. FIPS 186-3: Digital Signature Standard (DSS). Technical report,
National Institute of Standards and Technology, NIST, U.S.
Department of Commerce, Washington DC.
http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf, 2009.
Último acesso em 16/07/2013.
Jacques Patarin. Cryptanalysis of the Matsumoto and Imai Public Key
Scheme of Eurocrypt’88. In Don Coppersmith, editor, Advances in
Cryptology - CRYPT0 95, volume 963 of Lecture Notes in Computer
Science, chapter 20, pages 248–261. Springer Berlin / Heidelberg,
Berlin, Heidelberg, July 1995.
Jacques Patarin. Hidden Field Equations (HFE) and Isomorphisms of
Polynomials (IP): Two new families of asymmetric algorithms. In Ueli
Maurer, editor, Advances in Cryptology - EUROCRYPT 96, volume
of Lecture Notes in Computer Science, pages 33–48. Springer-
Verlag, 12–16 May 1996.
Jacques Patarin. Hidden Field Equations (HFE) and Isomorphisms of
Polynomials (IP): Two new families of asymmetric algorithms -
Extended Version, 1996.
Jacques Patarin, Nicolas T. Courtois, and Louis Goubin. QUARTZ,
-bit Long Digital Signatures. In David Naccache, editor, Topics in
Cryptology - CT-RSA 2001, volume 2020 of Lecture Notes in Computer
Science, pages 282–297. Springer Berlin Heidelberg, 2001.
Jacques Patarin and Louis Goubin. Trapdoor one-way permutations and
Multivariate Polynomials - Extended Version. In Proc. of ICICS 97,
LNCS 1334, pages 356–368. Springer, 1997.
Albrecht Petzoldt, Stanislav Bulygin, and Johannes Buchmann.
CyclicRainbow – A Multivariate Signature Scheme with a Partially
Cyclic Public Key. In Guang Gong and KishanChand Gupta, editors,
Progress in Cryptology - INDOCRYPT 2010, volume 6498 of Lecture
Notes in Computer Science, pages 33–48. Springer Berlin Heidelberg,
Albrecht Petzoldt, Stanislav Bulygin, and Johannes Buchmann.
Selecting parameters for the Rainbow Signature Scheme. In Nicolas
Sendrier, editor, Post-Quantum Cryptography, volume 6061 of Lecture
Notes in Computer Science, pages 218–240. Springer Berlin
Heidelberg, 2010.
Koichi Sakumoto, Taizo Shirai, and Harunaga Hiwatari. On provable
security of UOV and HFE Signature Schemes against Chosen-Message
Attack. In Bo-Yin Yang, editor, Post-Quantum Cryptography, volume
of Lecture Notes in Computer Science, pages 68–82. Springer
Berlin Heidelberg, 2011.
Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization
and Discrete Logarithms on a Quantum Computer. SIAM Journal on
Computing, 26(5):1484–1509, 1997.
Routo Terada. Segurança de dados: Criptografia em redes de
computador. Blucher, 2ª revisada e ampliada edition, 2008.
Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. Finding collisions in
the full SHA-1. In Advances in Cryptology - CRYPTO 2005: 25th
Annual International Cryptology Conference, Santa Barbara,
California, USA, August 14-18, 2005, Proceedings, volume 3621 of
Lecture Notes in Computer Science, pages 17–36. Springer, 2005.
Christopher Wolf. Implementing QUARTZ in java. Draft for the 3rd
NESSIE Workshop. http://www.christopher-wolf.de/ql/quartzJava.pdf,
Último acesso em 05/07/2013.
Christopher Wolf. QuartzLight in Java. http://www.christopherwolf.
de/ql/, 2002. Último acesso em 17/07/2013.
Christopher Wolf. Multivariate Quadratic Polynomials in Public Key
Cryptography. PhD thesis, Katholieke Universiteit Leuven – Faculteit
Ingenieurswetenschappen - Departement Elektrotechniek (ESAT),
Christopher Wolf and Bart Preneel. Taxonomy of Public Key Schemes
based on the problem of Multivariate Quadratic equations. Cryptology
ePrint Archive, Report 2005/077. http://eprint.iacr.org/2005/077, 2005.
Último acesso em 28/06/2013.
Takanori Yasuda, Kouichi Sakurai, and Tsuyoshi Takagi. Reducing the
Key Size of Rainbow using non-commutative rings. In Orr Dunkelman,
editor, Topics in Cryptology – CT-RSA 2012, volume 7178 of Lecture
Notes in Computer Science, pages 68–83. Springer Berlin Heidelberg,
DOI: https://doi.org/10.17648/enig.v2i1.35
Refbacks
- There are currently no refbacks.
This site is licensed with the Creative Commons Atribuição-NãoComercial-SemDerivações 4.0 Internacional
