A Structural Attack on Block-Anti-Circulant UOV at SAC 2019

Hiroki Furue, Koha Kinjo, Yasuhiko Ikematsu, Yacheng Wang, Tsuyoshi Takagi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationPost-Quantum Cryptography - 11th International Conference, PQCrypto 2020, Proceedings
EditorsJintai Ding, Jean-Pierre Tillich
Number of pages17
ISBN (Print)9783030442224
Publication statusPublished - 2020
Event11th International Conference on Post-Quantum Cryptography, PQCrypto 2020 - Paris, France
Duration: Apr 15 2020Apr 17 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12100 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference11th International Conference on Post-Quantum Cryptography, PQCrypto 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A Structural Attack on Block-Anti-Circulant UOV at SAC 2019'. Together they form a unique fingerprint.

Cite this