On the (In)Security of the BUFF Transform

The BUFF transform is a generic transformation for digital signature schemes, with the purpose of obtaining additional security properties beyond standard unforgeability, e.g., exclusive ownership and non-resignability. In the call for additional post-quantum signatures, these were explicitly mentioned by the NIST as "additional desirable security properties", and some of the submissions indeed refer to the BUFF transform with the purpose of achieving them, while some other submissions follow the design of the BUFF transform without mentioning it explicitly. In this work, we show the following negative results regarding the non-resignability property in general, and the BUFF transform in particular. In the plain model, we observe by means of a simple attack that any signature scheme for which the message has a high entropy given the signature does not satisfy the non-resignability property (while non-resignability is trivially not satisfied if the message can be efficiently computed from its signature). Given that the BUFF transform has high entropy in the message given the signature, it follows that the BUFF transform does not achieve non-resignability whenever the random oracle is instantiated with a hash function, no matter what hash function. When considering the random oracle model (ROM), the matter becomes slightly more delicate since prior works did not rigorously define the non-resignability property in the ROM. For the natural extension of the definition to the ROM, we observe that our impossibility result still holds, despite there having been positive claims about the non-resignability of the BUFF transform in the ROM. Indeed, prior claims of the non-resignability of the BUFF transform rely on faulty argumentation. On the positive side, we prove that a salted version of the BUFF transform satisfies a slightly weaker variant of non-resignability in the ROM, covering both classical and quantum attacks, if the entropy requirement in the (weakened) definition of non-resignability is statistical; for the computational variant, we show yet another negative result.

from [CDF + 21], which reduces non-resignability of the BUFF transform to Φ-non-malleability of the random oracle (where the latter, however, is not satisfied), carries over to the salted BUFF transform when considering the weaker variant of non-resignability and a correspondingly weaker and salted variant of Φ-non-malleability, and considering the entropy requirement to be statistical. Then, the main technical challenge lies in proving that the random oracle satisfies the considered weaker and salted variant of Φ-non-malleability.

We note that the considered weaker version of the non-resignability property, where the auxiliary information is computed without access to the random oracle, is still meaningful since in typical scenarios this auxiliary information is not chosen by the attacker but by the application, and so if in the considered application the computation of the auxiliary information does not depend on the random oracle, the weaker notion is sufficient (in the ROM).

Yet again on the negative side, we show that the above result on the salted version of the BUFF transform satisfying the weakened variant of the non-resignability property does not carry over in case the entropy requirement in the definition of the non-resignability property is computational (by means of the HILL entropy), as proposed and considered in [CDF + 21].

Conclusion. Altogether, our work shows that the non-resignability property for digital signature schemes, introduced in [JCCS19], later formalized in [CDF + 21], and explicitly mentioned by NIST as an "additional desirable security property" in their call for additional post-quantum signatures, is a very delicate security notion, and whether it is achieved (by one or another construction)-or even achievable at all-depends on subtle choices in the formal definition. Furthermore, our work shows that we actually have only very limited positive results so far.

Addendum. In reaction to our work, the authors of [CDF + 21] have updated their work. We briefly discuss this update [CDF + 23] on page 21.

We briefly recall that, for a random variable X, specified by its probability distribution P X , the guessing probability is given by guess(X) := max x P X (x), and the min-entropy by H ∞ (X) := -log guess(X). As usual, the log is in base 2.

In a similar spirit, for a pair of random variables (X, Z), specified by their joint distribution P XZ , the conditional guessing probability guess(X | Z) is defined as

with the natural understanding that guess(X | Z = z) = max x P X|Z (x | z), and the conditional min-entropy

Thus, in other words, H ∞ (X | Z) := -log z P Z (z)2 -H∞(X|Z=z)

The HILL entropy is a computational variant of the above min-entropy. First, we recall that for two random variables X and Y , the computational distance δ s (X, Y ) := max C