Proposal of Enhancement for Quartz Digital Signature
Ewerton R. Andrade, Routo Terada Β· Journal of Information Security and Cryptography (Enigma) Β· 2016
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.