Cryptanalysis of the Lifted Unbalanced Oil Vinegar Signature Scheme
Pages 279 - 298
Abstract
In 2017, Ward Beullens et al. submitted Lifted Unbalanced Oil and Vinegar (LUOV) [4], a signature scheme based on the famous multivariate public key cryptosystem (MPKC) called Unbalanced Oil and Vinegar (UOV), to NIST for the competition for post-quantum public key scheme standardization. The defining feature of LUOV is that, though the public key works in the extension field of degree r of, the coefficients of come from . This is done to significantly reduce the size of . The LUOV scheme is now in the second round of the NIST PQC standardization process.
In this paper we introduce a new attack on LUOV. It exploits the “lifted” structure of LUOV to reduce direct attacks on it to those over a subfield. We show that this reduces the complexity below the targeted security for the NIST post-quantum standardization competition.
References
[1]
Bettale L, Faugère J-C, and Perret L Hybrid approach for solving multivariate systems over finite fields J. Math. Cryptol. 2009 3 3 177-197
[2]
Bettale, L., Faugère, J.-C., Perret, L.: Solving polynomial systems over finite fields: improved analysis of the hybrid approach. In: Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, pp. 67–74 (2012)
[3]
Beullens, W., Preneel, B., Szepieniec, A., Vercauteren, F.: LUOV: signature scheme proposal for NIST PQC project (round 2 version) (2018)
[4]
Beullens W and Preneel B Patra A and Smart NP Field lifting for smaller UOV public keys Progress in Cryptology – INDOCRYPT 2017 2017 Cham Springer 227-246
[5]
Boyer, B., Eder, C., Faugère, J.-C., Lachartre, S., Martani, F.: GBLA: Gröbner basis linear algebra package. In: Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, pp. 135–142 (2016)
[6]
Buchberger B A theoretical basis for the reduction of polynomials to canonical forms ACM SIGSAM Bull. 1976 10 3 19-29
[7]
Cheng, C.-M., Chou, T., Niederhagen, R., Yang, B.-Y.: Solving quadratic equations with XL on parallel architectures - extended version. Cryptology ePrint Archive, Report 2016/412 (2016). https://eprint.iacr.org/2016/412
[8]
Coppersmith D Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm Math. Comput. 1994 62 205 333-350
[9]
Courtois N, Klimov A, Patarin J, and Shamir A Preneel B Efficient algorithms for solving overdefined systems of multivariate polynomial equations Advances in Cryptology — EUROCRYPT 2000 2000 Heidelberg Springer 392-407
[10]
Czypek, P.: Implementing multivariate quadratic public key signature schemes on embedded devices. Ph.D. thesis, Citeseer (2012)
[11]
Ding, J., Buchmann, J., Mohamed, M.S.E., Mohamed, W.S.A.E., Weinmann, R.-P.: MutantXL. In: Talk at the First International Conference on Symbolic Computation and Cryptography (SCC 2008) (2008)
[12]
Ding J, Gower JE, and Schmidt D Multivariate Public Key Cryptosystems 2006 Boston Springer
[13]
Ding J and Hodges TJ Rogaway P Inverting HFE systems is quasi-polynomial for all fields Advances in Cryptology – CRYPTO 2011 2011 Heidelberg Springer 724-742
[14]
Ding, J., Kleinjung, T.: Degree of regularity for HFE-. IACR Cryptology ePrint Archive, 2011:570 (2011)
[15]
Ding J and Petzoldt A Current state of multivariate cryptography IEEE Secur. Priv. 2017 15 4 28-36
[16]
Ding J and Schmidt D Ioannidis J, Keromytis A, and Yung M Rainbow, a new multivariable polynomial signature scheme Applied Cryptography and Network Security 2005 Heidelberg Springer 164-175
[17]
Ding J and Yang B-Y Gaborit P Degree of regularity for HFEv and HFEv- Post-Quantum Cryptography 2013 Heidelberg Springer 52-66
[18]
Ding J, Yang B-Y, Chen C-HO, Chen M-S, and Cheng C-M Bellovin SM, Gennaro R, Keromytis A, and Yung M New differential-algebraic attacks and reparametrization of rainbow Applied Cryptography and Network Security 2008 Heidelberg Springer 242-257
[19]
Ding, J., Zhang, Z., Deaton, J., Vishakha: The singularity attack to the multivariate signature scheme HIMQ-3. Cryptology ePrint Archive, report 2019/895 (2019). https://eprint.iacr.org/2019/895
[20]
Dubois V and Gama N Abe M The degree of regularity of HFE systems Advances in Cryptology - ASIACRYPT 2010 2010 Heidelberg Springer 557-576
[21]
Eder C and Faugère J-C A survey on signature-based algorithms for computing Gröbner bases J. Symb. Comput. 2017 80 719-784
[22]
Faugère J-C A new efficient algorithm for computing Gröbner bases (F4) J. Pure Appl. Algebra 1999 139 1–3 61-88
[23]
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, pp. 75–83 (2002)
[24]
Galkin, V.: Termination of original F5 (2012)
[25]
Gallagher, P.: Digital signature standard (DSS). Federal Information Processing Standards Publications, vol. FIPS, pp. 186–183 (2013)
[26]
Jiang X, Ding J, and Hu L Pei D, Yung M, Lin D, and Wu C Kipnis-Shamir attack on HFE revisited Information Security and Cryptology 2008 Heidelberg Springer 399-411
[27]
Johnson DS and Garey MR Computers and Intractability: A Guide to the Theory of NP-Completeness 1979 New York WH Freeman
[28]
Kipnis A and Shamir A Krawczyk H Cryptanalysis of the oil and vinegar signature scheme Advances in Cryptology — CRYPTO ’98 1998 Heidelberg Springer 257-266
[29]
Lidl R and Niederreiter H Finite Fields 1997 Cambridge Cambridge University Press
[30]
Matsumoto T, Imai H, et al. Barstow D et al. Public quadratic polynomial-tuples for efficient signature-verification and message-encryption Advances in Cryptology — EUROCRYPT 88 1988 Heidelberg Springer 419-453
[31]
Mohamed MSE, Cabarcas D, Ding J, Buchmann J, and Bulygin S Lee D and Hong S MXL: an efficient algorithm for computing Gröbner bases of zero-dimensional ideals Information, Security and Cryptology – ICISC 2009 2010 Heidelberg Springer 87-100
[32]
Mohamed MSE, Ding J, Buchmann J, and Werner F Garay JA, Miyaji A, and Otsuka A Algebraic attack on the MQQ public key cryptosystem Cryptol. Netw. Secur. 2009 Heidelberg Springer 392-401
[33]
Mohamed MSE, Mohamed WSAE, Ding J, and Buchmann J Buchmann J and Ding J MXL2: solving polynomial equations over GF(2) using an improved mutant strategy Post-Quantum Cryptography 2008 Heidelberg Springer 203-215
[34]
National Institute of Standards and Technology: Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. Technical report, National Institute of Standards and Technology (2017)
[35]
Patarin J Coppersmith D Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt88 Advances in Cryptology — CRYPT095 1995 Heidelberg Springer 248-261
[36]
Patarin, J.: The oil and vinegar algorithm for signatures. In: Dagstuhl Workshop on Cryptography 1997 (1997)
[37]
Petzoldt A, Bulygin S, and Buchmann J Catalano D, Fazio N, Gennaro R, and Nicolosi A Linear recurring sequences for the UOV key generation Public Key Cryptography – PKC 2011 2011 Heidelberg Springer 335-350
[38]
Rivest RL, Shamir A, and Adleman L A method for obtaining digital signatures and public-key cryptosystems Commun. ACM. 1978 21 2 120-126
[39]
Shor PW Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer SIAM Rev. 1999 41 2 303-332
[40]
Stallings W Cryptography and Network Security, 4/E 2006 London Pearson Education India
[41]
Thomae E and Wolf C Fischlin M, Buchmann J, and Manulis M Solving underdetermined systems of multivariate quadratic equations revisited Public Key Cryptography – PKC 2012 2012 Heidelberg Springer 156-171
[42]
Wolf C and Preneel B Equivalent keys in multivariate quadratic public key systems J. Math. Cryptol. 2011 4 4 375-415
[43]
Yang B-Y, Chen C-HO, Bernstein DJ, and Chen J-M Biryukov A Analysis of QUAD Fast Software Encryption 2007 Heidelberg Springer 290-308
[44]
Yang B-Y and Chen J-M Wang H, Pieprzyk J, and Varadharajan V Theoretical analysis of XL over small fields Information Security and Privacy 2004 Heidelberg Springer 277-288
[45]
Yeh, J.Y.-C., Cheng, C.-M., Yang, B.-Y.: Operating degrees for XL vs. F/F for generic with number of equations linear in that of variables. In: Fischlin, M., Katzenbeisser, S. (eds.) Number Theory and Cryptography. LNCS, vol. 8260, pp. 19–33. Springer, Heidelberg (2013).
Recommendations
Cryptanalysis and Improvement of a Certificateless Multi-proxy Signature Scheme
Certificateless cryptography is a new type of public key cryptography, which removes the certificate management problem in traditional public key cryptography and the key escrow problem in identity-based public key cryptography. Multi-proxy signature is ...
Cryptanalysis of a Generalized Ring Signature Scheme
The concept of ring signature was first introduced by Rivest et al. in 2001. In a ring signature, instead of revealing the actual identity of the message signer, it specifies a set of possible signers. The verifier can be convinced that the signature ...
Cryptanalysis of Xia-You group signature scheme
Special issue: Software engineering education and trainingGroup signature is a variant of digital signatures, which allows members of a group to sign messages anonymously on behalf of he group. The application of group signatures includes e-voting, e-bidding and e-cash. Recently, Xia and You proposed an ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Aug 2020
838 pages
© International Association for Cryptologic Research 2020.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 17 August 2020
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 31 Dec 2024