TY - GEN
T1 - A Structural Attack on Block-Anti-Circulant UOV at SAC 2019
AU - Furue, Hiroki
AU - Kinjo, Koha
AU - Ikematsu, Yasuhiko
AU - Wang, Yacheng
AU - Takagi, Tsuyoshi
N1 - Funding Information:
Acknowledgments. This work was supported by JST CREST Grant JPMJCR14D6, JSPS KAKENHI Grant Number 19K20266, and 18J20866.
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - At SAC 2019, Szepieniec and Preneel proposed a new variant of the Unbalanced Oil and Vinegar signature scheme (UOV) called block-anti-circulant UOV (BAC-UOV). In this scheme, the matrices representing the quadratic parts of the public key are designed to be block-anti-circulant matrices, which drastically reduces its public key size compared to UOV that originally has a relatively large public key size. In this paper, we show that this block-anti-circulant property enables us to do a special linear transformation on variables in the public key polynomials. By executing the UOV attack on quadratic terms in partial variables of the resulting polynomial system, we obtain a polynomial system with less quadratic terms, which can be algebraically solved faster than the plain direct attack. Our proposed attack reduces the bit complexity of breaking BAC-UOV by about 20% compared with the previously known attacks. For example, the complexity of our proposed attack on 147-bit BAC-UOV parameter (claimed security level II in NIST PQC project by its authors) can be reduced only to 119 bits.
AB - At SAC 2019, Szepieniec and Preneel proposed a new variant of the Unbalanced Oil and Vinegar signature scheme (UOV) called block-anti-circulant UOV (BAC-UOV). In this scheme, the matrices representing the quadratic parts of the public key are designed to be block-anti-circulant matrices, which drastically reduces its public key size compared to UOV that originally has a relatively large public key size. In this paper, we show that this block-anti-circulant property enables us to do a special linear transformation on variables in the public key polynomials. By executing the UOV attack on quadratic terms in partial variables of the resulting polynomial system, we obtain a polynomial system with less quadratic terms, which can be algebraically solved faster than the plain direct attack. Our proposed attack reduces the bit complexity of breaking BAC-UOV by about 20% compared with the previously known attacks. For example, the complexity of our proposed attack on 147-bit BAC-UOV parameter (claimed security level II in NIST PQC project by its authors) can be reduced only to 119 bits.
UR - http://www.scopus.com/inward/record.url?scp=85083992130&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85083992130&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-44223-1_18
DO - 10.1007/978-3-030-44223-1_18
M3 - Conference contribution
AN - SCOPUS:85083992130
SN - 9783030442224
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 323
EP - 339
BT - Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020, Proceedings
A2 - Ding, Jintai
A2 - Tillich, Jean-Pierre
PB - Springer
T2 - 11th International Conference on Post-Quantum Cryptography, PQCrypto 2020
Y2 - 15 April 2020 through 17 April 2020
ER -