Why does the UOV submission to NIST need a 16 byte salt in each signature?

[Scott Fluhrer (sfluhrer)]

TL;DR: why does UOV need a 16 byte salt in each signature?  It would appear to be secure without it.

Background

The round 2 NIST submission for Unbalanced Oil and Vinegar (UOV; https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-2/spec-files/uov-spec-round2-web.pdf ) generates a random 16 byte salt for each signature.  This salt is used in two ways:

• The message hash also includes the salt, ensuring that each message hash is different, even if you sign the same message repeatedly
• The salt is used (along with a secret seed) to generate the vinegar variables.

Because of this first usage, the salt must be included in the signature (so that the verifier can compute the same message hash).  16 bytes extra in a signature might not seem to be much, except that UOV has tiny signatures – the smallest parameter set (uov-Is) has a 96 byte signature, 16 bytes of which is the salt.  Hence, that parameter set could have an 80 byte signature, if the salt were not present.  A 20% overhead would appear to be significant (at least to me).

My question

So, why do we need to include the salt in the message hash (and thus in the signature)?  It’s not there to avoid relying on collision resistance of the hash (the message/salt combination is in the wrong order).  According to https://eprint.iacr.org/2023/059.pdf, the salt is there “to protect against side-channel and fault injection attacks” (section 2, Signing).  However, it is not clear to me if it is required for that.  After all, we already have the vinegar variables which are randomly selected, and those would appear to defend against both attacks.  For example, a side channel attack that would depend on a repeated hash would attack line 10 of UOV.sign (figure 2 of the NIST submission); however the both Lx and y of that equation would appear to be effectively randomized (because they both depend on the vinegar variables v), and it’s unclear how a repeated t value (which is not secret) would be useful to any side channel attack.  Similarly, a fault attack based on repeated hashes would not appear to be fruitful, because the v values, which the entire signature depends on, are also different for each signature.

I don’t have anything against belt-and-suspenders protection if the cost is low – I’m not sure if the costs are, in fact, low in this case.

So, is there something I’m missing?

[niux_d...@icloud.com]

Because UOV relies on finding the preimage of a quadratic function for signing, and because not all images have a preimage, a randomization factor is needed.

-- 
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/PH3PPFA3FE8A23F5B69C05ABE38EAB7B45AC1222%40PH3PPFA3FE8A23F.namprd11.prod.outlook.com.

[wa...@beullens.com]

Hi Scott,

 

Yes, if you don't care about side-channel or fault injection attacks (or if you can protect against them is some better way) you can omit the salt to reduce the signature size. IMO the proper way to do this would be to remove the salt from the message hash AND remove it from Expand_v to derive the vinegar variables.

 

In your question you seem to suggest to remove the salt only from the message hash (to reduce the signature size), but keep in the Expand_v to get some protection against side channels and fault injection attacks.

The problem with this approach is that an attacker can then obtain arbitrarily large multi-collisions for the UOV trapdoor, just by asking for many signatures on the same message. This is not something that can be simulated without knowing the secret key.

 

As far as we know, giving this extra ability (the ability to get multi-collisions I mean) doesn't lead to any new attacks, so one could still go with this approach. But the 16-bytes of signature wouldn't be free. They would come at the cost of introducing this extra attack vector. (which is not really explored in the literature as far as I know)

 

Speaking for myself,

Ward

--

[Scott Fluhrer (sfluhrer)]

I am not disagreeing on the need to use a random salt to select the vinegar variables (the second use case in my list).  We need to select the vinegar variables secretly, and basing it on a short seed (and a secret value from the private key) is as good a way as any (and running into a singularity is not an issue - if we do, we increment a counter and generate fresh vinegar values).  And, for that usage, we don't need to include it in the signature.

Instead, I'm wondering about the need to use the salt in the message hash, that is, to compute the internal 't' variable.  That has nothing to do with the matrix being singular; it's not involved in computing it.

---

From: niux_d...@icloud.com <niux_d...@icloud.com>
Sent: Wednesday, April 15, 2026 8:36 AM
To: Scott Fluhrer (sfluhrer) <sflu...@cisco.com>
Cc: pqc-...@list.nist.gov <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Why does the UOV submission to NIST need a 16 byte salt in each signature?

[Scott Fluhrer (sfluhrer)]

If I understood you correctly (and I would ask for forgiveness if I didn't), you would prefer to remove randomness from the vinegar selection, and instead make it a function of the message and a secret value (and the counter); hence making the signature algorithm deterministic.

That strikes me as asking for a fault attack.  One approach that would come to mind - ask for the signature of the same message twice, and for one of them, fault the generation of one of the vinegar values.  Then (assuming that neither result in a singular matrix), the two signatures will differ by that one vinegar value (and some vector in the oil space).  That sounds dangerous.

If we do that again for a different message (and faulting the same vinegar variable), that would result in two more signatures that differ in that one vinegar value (and some other vector in the oil space).

I would expect that, from those four signatures, you could recover a vector from the oil space, and I believe it's game over after that.

---

From: ward via pqc-forum <pqc-...@list.nist.gov>
Sent: Wednesday, April 15, 2026 9:20 AM
To: Scott Fluhrer (sfluhrer) <sflu...@cisco.com>; pqc-...@list.nist.gov <pqc-...@list.nist.gov>
Subject: RE: [pqc-forum] Why does the UOV submission to NIST need a 16 byte salt in each signature?

[Javier Verbel]

Hi, 

Another implication of removing the salt (not related to side-channel or fault injection) will be that the upper-bound of the statistical distance between signatures of the same message and random vectors will change from ~1/q (in the original variant with the salt) to ~ 1 in the new variant without the salt.

Best,
Javier  

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/PH3PPFA3FE8A23F11EDA3B21C330914B160C1222%40PH3PPFA3FE8A23F.namprd11.prod.outlook.com.

[wa...@beullens.com]

I said "*If you don't care about side-channel or fault injection attacks*, then you can omit the salt everywhere". But in general we do care about attacks like the one you mentioned, which is why we decided to have the salt in the specification. I'm definitely not proposing to get rid of it.

 

Your proposal of only removing the salt from the message hash, but not from the "vinegar hash" is a bit dangerous for the reason that I tried to explain in my previous email: it allows the adversary to get arbitrarily big multi-collisions against the trapdoor.