SNOVA, a multivariate signature scheme

Short answer: SNOVA is a multivariate digital signature scheme that builds the structure of a matrix ring over a finite field into Unbalanced Oil and Vinegar (UOV), which its authors and a 2024 cryptanalysis paper say sharply cuts the public key size compared with UOV. It is a candidate, not a settled design: the 2024 paper reports that some of the submitted parameters do not meet their claimed security levels, and the authors' site says the scheme was reformulated in response to cryptanalysis. Treat the figures below as the authors' claims and listings, not independent verification.

What SNOVA is

The 2024 ePrint paper describes SNOVA as a multivariate signature scheme submitted to an additional post-quantum signature call that began in 2022. It says SNOVA is constructed by incorporating the structure of the matrix ring over a finite field into the UOV signature scheme, so that the core of its public key is a UOV public key whose coefficients are matrices. The paper says UOV is considered a fundamental multivariate scheme because it has no fatal attacks so far and uses simple algorithms, but that it has the drawback of a large public key compared with other post-quantum designs such as lattice-based ones.

The authors' website describes SNOVA as a variant of UOV designed to operate over noncommutative rings for efficiency and a smaller public key. It says a key-randomness alignment technique lets the scheme adapt to noncommutative rings without being hurt by their noncommutativity. Open Quantum Safe lists its main cryptographic assumption as multivariate quadratic equations, oil and vinegar.

Reported sizes

The Open Quantum Safe listing gives parameter sets with claimed security levels 1, 3 and 5, for the Round 2 specification version. For example, it lists SNOVA_24_5_4 with a public key of 1016 bytes, a secret key of 48 bytes and a signature of 248 bytes, and SNOVA_37_17_2 with a 9842-byte public key and a 124-byte signature. It also lists a larger set, SNOVA_56_25_2, with a 31266-byte public key and a 178-byte signature. These are the listing's figures for specific parameter sets and a specific specification version.

Cryptanalysis and changes

The 2024 paper recalls the construction, reconsiders its security analysis, and investigates key recovery attacks on the core part of the public key in detail. Its abstract says that, due to this analysis, some parameters of SNOVA as submitted do not satisfy the claimed security levels.

The authors' site says the scheme was reformulated in response to cryptanalysis during earlier evaluation rounds. It says the newer reformulation extends the signature to rectangular matrices, giving a scheme defined by seven parameters, lets the whipping dimension and the number of equations be chosen independently, and remains backward compatible with the Round 2 version. It also says recent research characterizes SNOVA as applying a whipping transformation, similar to MAYO, to a structured UOV public key. These are the authors' own descriptions.

Limits

This post does not assess the security of any parameter set. The listed sizes may change between specification versions, and the authors' site and the Open Quantum Safe page describe different versions. SNOVA is not a standard.

FAQ

What is SNOVA based on?

UOV, using matrix ring structure, according to the 2024 paper and the authors' site.

Why was it proposed?

The 2024 paper says UOV has a large public key, and SNOVA is described as dramatically reducing it.

Is SNOVA secure?

The 2024 paper reports that some submitted parameters do not meet their claimed security levels. The authors say they reformulated the scheme in response to cryptanalysis.

How big are the keys and signatures?

Open Quantum Safe lists, for SNOVA_24_5_4, a 1016-byte public key and a 248-byte signature, for one specification version.

How does it relate to MAYO?

The authors' site says SNOVA can be characterized as applying a whipping transformation similar to MAYO's to a structured UOV public key.