jpeg resistance of various post-quantum signature schemes

The discussion revolves around the concept of "jpeg resistance" in post-quantum signature schemes, a term coined to describe a signature scheme's resilience against an attacker's ability to find a complete signature and public key for a partially specified signature and full message. Traditional hash-based signatures such as schoolbook Winternitz one-time signatures, forest-of-trees few-time signatures, and Merkle trees are not jpeg resistant because their validation process involves recomputing the public key or Merkle tree root from the signature and message. This allows any arbitrary signature to be validated by simply setting the public key to match the recomputed value.

RFC 8391 XMSS, a standardized hash-based signature scheme, introduces an additional layer of security by incorporating the public key into the hash of the message before signing. This modification significantly limits an attacker’s ability to manipulate the public key, thereby enhancing jpeg resistance. In contrast, RFC 8391 XMSSMT, an extension of XMSS, is less jpeg resistant due to its structure as a certificate chain of XMSS signatures. Although the top XMSSMT public key is hashed into the message signed, this only secures the first XMSS signature in the chain, leaving subsequent signatures vulnerable to manipulation since their roots are not bound.

SLH-DSA (FIPS 205, formerly SPHINCS+) operates on a similar principle to XMSSMT but utilizes a variant of XMSS signatures in a certificate chain ending with a FORS public key that signs the final message. The jpeg resistance in SLH-DSA stems from the inability to tamper with the first XMSS keypair, allowing for approximately ⅞ of the signature to be chosen arbitrarily provided the first XMSS keypair is honestly generated and used to sign the recalculated root.

ML-DSA (FIPS 204, formerly Dilithium) employs a Fiat–Shamir transform of a module-lattice identification scheme, where the commitment and response mechanism allows for significant portions of the signature to be freely chosen by setting certain components of the private key to zero. This approach, while breaking jpeg resistance, remains difficult to detect due to the selective zeroing of components.

Falcon, another scheme discussed, leverages small polynomials in its private key to compute signatures. The technique mentioned involves manipulating the encoding of a component of the signature (s2) to construct a new public key or to directly set the public key using the signature component s2. This method suggests potential vulnerabilities in Falcon's jpeg resistance, though it also notes that modifying the hashing process to involve the hash of the public key could mitigate these attacks.

Each of these schemes demonstrates varying degrees of vulnerability to the jpeg resistance concept, highlighting the ongoing challenge of securing digital signatures against evolving cryptographic threats.