Paper 2023/1822

Rectangular Attack on VOX

Gilles Macario-Rat, Orange Labs
Jacques Patarin, Thales Group and UVSQ
Benoit Cogliati, Thales Group
Jean-Charles Faugère
Pierre-Alain Fouque, Université de Rennes
Louis Gouin, Université de Versailles-Saint-Quentin en Yvelines
Robin Larrieu, CryptoNext Security
Brice Minaud, Inria and Ecole normale supérieure

VOX has been submitted to the NIST Round 1 Additional Signature of the Post-Quantum Signature Competition in June 2023. VOX is a strengthened variant of UOV which uses the Quotient-Ring (QR) setting to reduce the public-key size. At the end of August 2023, Furue and Ikamatsu posted on the NIST mailing-list a post, indicating that the parameters of VOX can be attacked efficiently using the rectangular attack in the QR setting. In this note, we explain the attack in the specific case of VOX, we detail the complexity, and show that as Furue and Ikematsu indicated, the attack can be completely avoided by adding one more constraint on the parameter selection. Finally, we show that this constraint does not increase the sizes of the public keys or signature.

Available format(s)
Public-key cryptography
Publication info
Multivariate CryptographyRectangular AttackUOVQR
Contact author(s)
gilles macariorat @ orange com
Jacques Patarin @ thalesgroup com
benoit-michel cogliati @ thalesgroup com
jcf @ cryptonext-security com
Pierre-Alain Fouque @ univ-rennes fr
Louis Goubin @ uvsq fr
Robin Larrieu @ cryptonext-security com
Brice Minaud @ gmail com
2023-12-02: revised
2023-11-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gilles Macario-Rat and Jacques Patarin and Benoit Cogliati and Jean-Charles Faugère and Pierre-Alain Fouque and Louis Gouin and Robin Larrieu and Brice Minaud},
      title = {Rectangular Attack on VOX},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1822},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.