Abstract
The unbalanced oil and vinegar signature scheme (UOV), which is one of the multivariate signature schemes, is expected to be secure against quantum attacks. To achieve cryptosystem security in a practical manner, we need to deal with security against physical attacks such as fault attacks, which generate computational errors to lead to security failures. In this study, we propose a new fault attack on UOV using faults occurring on the secret key. The proposed attack first recovers a part of the linear map of the secret key by utilizing faults occurring on the secret key, and then transforms the public key system. As a result, the proposed attack reduces a given public key system into one with fewer variables than the original system. After applying our proposed attack, the secret key can be recovered with less complexity than the original system by using an existing key recovery attack. Our simulation results show that, for two practical parameter sets satisfying 100-bit security, the proposed attack can reduce the given system into one with only 90-bit security with a probability of approximately \(80\sim 90\)%. We also show that the proposed attack achieves a smaller resulting system than the above case with lower probability, and that such a system can be broken even more efficiently.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bettale, L., Faugère, J.-C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Crypto. 3, 177–197 (2009)
Beullens, W.: Improved cryptanalysis of UOV and rainbow. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 348–373. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_13
Beullens, W.: Breaking rainbow takes a weekend on a laptop. IACR Cryptology ePrint Archive: Report 2022/385 (2022)
Beullens, W., Preneel, B.: Field lifting for smaller UOV public keys. In: Patra, A., Smart, N.P. (eds.) INDOCRYPT 2017. LNCS, vol. 10698, pp. 227–246. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71667-1_12
Bogdanov, A., Eisenbarth, T., Rupp, A., Wolf, C.: Time-area optimized public-key engines: \(\cal{MQ}\)-cryptosystems as replacement for elliptic curves? In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 45–61. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85053-3_4
Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_27
Czypek, P., Heyse, S., Thomae, E.: Efficient implementations of MQPKS on constrained devices. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 374–389. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33027-8_22
Chen, A.I.-T., et al.: SSE implementation of multivariate PKCs on modern x86 CPUs. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 33–48. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04138-9_3
Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–175. Springer, Heidelberg (2005). https://doi.org/10.1007/11496137_12
Ding, J., Yang, B.-Y., Chen, C.-H.O., Chen, M.-S., Cheng, C.-M.: New differential-algebraic attacks and reparametrization of rainbow. In: Bellovin, S.M., Gennaro, R., Keromytis, A., Yung, M. (eds.) ACNS 2008. LNCS, vol. 5037, pp. 242–257. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68914-0_15
Faugère, J.-C.: A new efficient algorithm for computing Gr\(\rm \ddot{o}\)bner bases (F4). J. Pure Appl. Algebra 139(1–3), 61–88 (1999)
Faugère, J.-C.: A new efficient algorithm for computing Gr\(\rm \ddot{o}\)bner bases without reduction to zero (F5). In: ISSAC 2002, pp. 75–83. ACM (2002)
Garey, M.-R., Johnson, D.-S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)
Hashimoto, Y., Takagi, T., Sakurai, K.: General fault attacks on multivariate public key cryptosystems. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 1–18. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_1
Kipnis, A., Patarin, J., Goubin, L.: Unbalanced oil and vinegar signature schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206–222. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_15
Kipnis, A., Shamir, A.: Cryptanalysis of the oil and vinegar signature scheme. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 257–266. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055733
Krämer, J., Loiero, M.: Fault attacks on UOV and rainbow. In: Polian, I., Stöttinger, M. (eds.) COSADE 2019. LNCS, vol. 11421, pp. 193–214. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-16350-1_11
Mus, K., Islam, S., Sunar, B.: QuantumHammer: a practical hybrid attack on the LUOV signature scheme. In: CCS 2020, pp. 1071–1084. ACM (2020)
NIST: Post-quantum cryptography CSRC. https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization
NIST: Status report on the second round of the NIST post-quantum cryptography standardization process. NIST Internal Report 8309, NIST (2020)
Park, A., Shim, K.-A., Koo, N., Han, D.-G.: Side-channel attacks on post-quantum signature schemes based on multivariate quadratic equations - rainbow and UOV -. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018(3), 500–523 (2018)
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)
Shim, K.-A., Koo, N.: Algebraic fault analysis of UOV and Rainbow with the leakage of random vinegar values. IEEE Trans. Inf. Forensics Secur. 15, 2429–2439 (2020)
Shim, K.-A., Lee, S., Koo, N.: Efficient implementations of Rainbow and UOV using AVX2. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2022(1), 245–269 (2022)
Yang, B.-Y., Chen, J.-M., Courtois, N.T.: On asymptotic security estimates in XL and Gröbner bases-related algebraic cryptanalysis. In: Lopez, J., Qing, S., Okamoto, E. (eds.) ICICS 2004. LNCS, vol. 3269, pp. 401–413. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30191-2_31
Yang, B.-Y., Chen, O.C.-H., Bernstein, D.J., Chen, J.-M.: Analysis of QUAD. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 290–308. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74619-5_19
Acknowledgements
This work was supported by JST CREST Grant Number JPMJCR2113, Japan, and JSPS KAKENHI Grant Number JP21J20391, Japan.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Furue, H., Kiyomura, Y., Nagasawa, T., Takagi, T. (2022). A New Fault Attack on UOV Multivariate Signature Scheme. In: Cheon, J.H., Johansson, T. (eds) Post-Quantum Cryptography. PQCrypto 2022. Lecture Notes in Computer Science, vol 13512. Springer, Cham. https://doi.org/10.1007/978-3-031-17234-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-17234-2_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-17233-5
Online ISBN: 978-3-031-17234-2
eBook Packages: Computer ScienceComputer Science (R0)