About VOX/FOX

VOX is family a post-quantum signature algorithms submitted to NIST Post-Quantum Cryptography Project on May 31th, 2023. It has been designed by: Benoît Cogliati, Jean-Charles Faugère, Pierre-Alain Fouque, Louis Goubin, Robin Larrieu, Gilles Macario-Rat, Brice Minaud and Jacques Patarin.

The VOX family includes a specific instantiation called “VOX-F” (or Full VOX, nicknamed “FOX”) that does not use the QR technique and allows to obtain easier security arguments.

Due to attacks on the QR technique (see the Updates/News section below for more details), FOX is at present our main version of VOX.

VOX/FOX is based on multivariate cryptography (UOV problem and the problem of solving algebraic equations).

Updates / News

• Version 1.0 (31/05/2023): Initial specification of the VOX family, including a specific instantiation called “VOX-F” (or Full VOX, nicknamed “FOX”) that does not use the QR technique and allows to obtain easier security arguments.
• Version 1.0a (27/07/2023): Clarification added in the matrix representation of the linear mappings and their operations on vectors.
• Version 1.1 (17/05/2024): In-depth analysis of the impact of rectangular attacks and other attacks led us to abandon the “Quotient Ring” (QR) structure, so that rank defects can no longer be exploited. This new specification focuses on “VOX-F” (or Full VOX, nicknamed “FOX”) with optimized parameters for the targeted I, III, V security levels, and a detailed performance analysis.

Why FOX?

• With FOX, we have short signatures.
• We have very fast verification performance (see the performance table below).
• We have nice arguments of security.
• FOX is a variant of UOV, a multivariate scheme that has been extensively analyzed for more than twenty years, and for which no major attack has been found.
• It uses a new trick called ^+, which can only increase the security at a moderate performance cost.

Security arguments for FOX

Thanks to the ^+ trick, it is possible to follow two opposite strategies.

First, one can use this security increase to reduce parameter sizes, and try to use more aggressive optimizations.

Second, one can keep a secure UOV instance, and then further enhance its security with the ˆ+ variant.

In the design of FOX, we chose the second approach. Thus, FOX has very conservative parameters. Moreover, we selected our parameter sets so that the cost of canceling the added random polynomials for two public equations is the same as breaking the underlying UOV problem.

FOX: a UOV-based hash-and-sign signature scheme

FOX is a UOV-based hash-and-sign signature scheme from the Multivariate Quadratic (MQ) family, built around a new variant proposed by Faugère, Macario-Rat, Patarin, and Perret under the name UOVˆ+ [pdf].

While the quadratic forms of a UOV public key have a large common isotropic subspace, which is unusual for a random quadratic system, UOVˆ+ adds a small number of uniformly random quadratic forms to the public keys to hide this subspace. For the same parameter sizes, UOVˆ+ is then more secure than the corresponding UOV instance.

Hence, FOX can keep all benefits of UOV, such as small signature sizes, fast signature generation, and extremely fast verification, while also offering an additional security guarantee.

As an illustration, the size of the signature is only 124 bytes for FOX-I with security level I for public key size 50.3 Kbytes. The verification time is very good and we can sign 277 messages per second if the secret key is decompressed.

FOX Parameters

We define the parameters for each variant of FOX according to the three security levels defined by the NIST.

The size of the signature (|sig|), the public key (|cpk|), the secret key (|sk|) and the compressed secret key (|csk|) are expressed in bytes.

Performance (C Intel x86-64 and AVX2)

Using the reference implementation on a common laptop computer (11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz , TurboBoost enabled), FOX achieves the following performance:

All the timings are given in milliseconds (ms) and in cycles (c)

Using AVX2 implementation on a common laptop computer (11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz , TurboBoost enabled), FOX achieves the following performance:

All the timings are given in milliseconds (ms) and in cycles (c)

The verification time is very good and we can sign 277 messages per second if the secret key is decompressed and 236 otherwise.

Resources

(Version 2024-05-17): .

• VOX specification v1.1 [pdf]: In-depth analysis of the impact of rectangular attacks and other attacks led us to abandon the “Quotient Ring” (QR) structure, so that rank defects can no longer be exploited. This new specification focuses on “VOX-F” (or Full VOX, nicknamed “FOX”) with optimized parameters for the targeted I, III, V security levels, and a detailed performance analysis.
• VOX/FOX source files [zip] (source code C+AVX2)
• VOX/FOX KAT files [zip]

(Version 2023-07-28): .

• VOX specification v1.0a [pdf]: Clarification added in the matrix representation of the linear mappings and their operations on vectors.

(Version 2023-05-31): .

• VOX specification v1.0 [pdf]
• VOX source files [zip] (specification, source code C+AVX2+Flint, performance tool)
• VOX KAT files [zip]
• Simpler implementation in Flint [zip].
• VOX Full submission package [zip] (specification, source code C+AVX2+Flint, performance tool and test vectors)