Skip to main content
Top

2021 | OriginalPaper | Chapter

A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV

Authors : Hiroki Furue, Yasuhiko Ikematsu, Yutaro Kiyomura, Tsuyoshi Takagi

Published in: Advances in Cryptology – ASIACRYPT 2021

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The unbalanced oil and vinegar signature scheme (UOV) is a multivariate signature scheme that has essentially not been broken for over 20 years. However, it requires the use of a large public key; thus, various methods have been proposed to reduce its size. In this paper, we propose a new variant of UOV with a public key represented by block matrices whose components correspond to an element of a quotient ring. We discuss how it affects the security of our proposed scheme whether or not the quotient ring is a field. Furthermore, we discuss their security against currently known and newly possible attacks and propose parameters for our scheme. We demonstrate that our proposed scheme can achieve a small public key size without significantly increasing the signature size compared with other UOV variants. For example, the public key size of our proposed scheme is 85.8 KB for NIST’s Post-Quantum Cryptography Project (security level 3), whereas that of compressed Rainbow is 252.3 KB, where Rainbow is a variant of UOV and is one of the third-round finalists of the NIST PQC project.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Literature
1.
go back to reference Bardet, M.: Étude des systèms algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. Ph.D. thesis, Université Pierre et Marie Curie-Paris VI (2004) Bardet, M.: Étude des systèms algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. Ph.D. thesis, Université Pierre et Marie Curie-Paris VI (2004)
2.
go back to reference Bardet, M., Faugère, J.-C., Salvy, B.: Complexity of Gröbner basis computation for semi-regular overdetermined sequences over \(\mathbb{F}_2\) with solutions in \(\mathbb{F}_2\). Research Report, INRIA (2003) Bardet, M., Faugère, J.-C., Salvy, B.: Complexity of Gröbner basis computation for semi-regular overdetermined sequences over \(\mathbb{F}_2\) with solutions in \(\mathbb{F}_2\). Research Report, INRIA (2003)
3.
go back to reference Bardet, M., Faugère, J.-C., Salvy, B., Yang, B.-Y.: Asymptotic behavior of the index of regularity of quadratic semi-regular polynomial systems. In: 8th International Symposium on Effective Methods in Algebraic Geometry (2005) Bardet, M., Faugère, J.-C., Salvy, B., Yang, B.-Y.: Asymptotic behavior of the index of regularity of quadratic semi-regular polynomial systems. In: 8th International Symposium on Effective Methods in Algebraic Geometry (2005)
4.
go back to reference Bettale, L., Faugère, J.-C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol. 3, 177–197 (2009)MathSciNetCrossRef Bettale, L., Faugère, J.-C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol. 3, 177–197 (2009)MathSciNetCrossRef
7.
go back to reference Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symbol. Comput. 24(3–4), 235–265 (1997) Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symbol. Comput. 24(3–4), 235–265 (1997)
8.
go back to reference Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: ITCS 2012, pp. 309–325. ACM (2012) Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: ITCS 2012, pp. 309–325. ACM (2012)
9.
go back to reference Buchberger, B.: Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal. Ph.D. thesis, Universität Innsbruck (1965) Buchberger, B.: Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal. Ph.D. thesis, Universität Innsbruck (1965)
12.
go back to reference Ding, J., et al.: Rainbow signature schemes proposal for NIST PQC project (round 3 version) Ding, J., et al.: Rainbow signature schemes proposal for NIST PQC project (round 3 version)
15.
go back to reference Ding, J., Zhang, Z., Deaton, J., Schmidt, K., Vishakha, FNU.: New attacks on lifted unbalanced oil vinegar. In: Second PQC Standardization Conference 2019, NIST (2019) Ding, J., Zhang, Z., Deaton, J., Schmidt, K., Vishakha, FNU.: New attacks on lifted unbalanced oil vinegar. In: Second PQC Standardization Conference 2019, NIST (2019)
16.
go back to reference 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)MathSciNetCrossRef 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)MathSciNetCrossRef
17.
go back to reference 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) 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)
20.
go back to reference Garey, M.-R., Johnson, D.-S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, W.H, San Francisco (1979) Garey, M.-R., Johnson, D.-S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, W.H, San Francisco (1979)
21.
go back to reference Grover, L.-K.: A fast quantum mechanical algorithm for database search. In: STOC 1996, pp. 212–219. ACM (1996) Grover, L.-K.: A fast quantum mechanical algorithm for database search. In: STOC 1996, pp. 212–219. ACM (1996)
22.
go back to reference Hashimoto, Y.: Minor improvements of algorithm to solve under-defined systems of multivariate quadratic equations. IACR Cryptology ePrint Archive: Report 2021/1045 (2021) Hashimoto, Y.: Minor improvements of algorithm to solve under-defined systems of multivariate quadratic equations. IACR Cryptology ePrint Archive: Report 2021/1045 (2021)
25.
go back to reference Lyubashevsky, V., et al.: CRYSTALS-DILITHIUM signature schemes proposal for NIST PQC project (round 2 version) Lyubashevsky, V., et al.: CRYSTALS-DILITHIUM signature schemes proposal for NIST PQC project (round 2 version)
28.
go back to reference NIST: Status report on the first round of the NIST post-quantum cryptography standardization process. NIST Internal Report 8240, NIST (2019) NIST: Status report on the first round of the NIST post-quantum cryptography standardization process. NIST Internal Report 8240, NIST (2019)
29.
go back to reference NIST: Status report on the second round of the NIST post-quantum cryptography standardization process. NIST Internal Report 8309, NIST (2020) NIST: Status report on the second round of the NIST post-quantum cryptography standardization process. NIST Internal Report 8309, NIST (2020)
32.
go back to reference Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC 2005, pp. 84–93. ACM (2005) Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC 2005, pp. 84–93. ACM (2005)
34.
go back to reference Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRef Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRef
Metadata
Title
A New Variant of Unbalanced Oil and Vinegar Using Quotient Ring: QR-UOV
Authors
Hiroki Furue
Yasuhiko Ikematsu
Yutaro Kiyomura
Tsuyoshi Takagi
Copyright Year
2021
DOI
https://doi.org/10.1007/978-3-030-92068-5_7

Premium Partner