Are there signatures that don't have subliminal channels?

Are there signatures that don't have subliminal channels and also don't require commitments or zero-knowledge proofs?

DSA or Schnorr signatures need a nonce which can leak valuable information. There are derandomization schemes, but the verifier can't check that the signer used them without extra steps.

Is there a signature that avoids these problems?

According to this answer, RSA with the "usual" "padding scheme, described in PKCS#1 as the
'old-style, v1.5' padding," can be made to satisfy that; one would need to specify NULL or omission
and require that the public exponent's prime factors are all easily
findable and sufficiently bigger than the 4th root of the modulus.

• It's a de randomization scheme. The problem is that the verifier can't be sure it was used.
– hanh
Dec 20 '14 at 10:07
• That's a ... fairly general definition of "a de randomization scheme". $\:$ The verifier can "be sure it was used" by putting the signature "through the modular exponentiation which is at the core of RSA", and checking whether or not the output is equal to what the first three steps produce. $\;\;\;\;$
– user991
Dec 20 '14 at 10:16
• Indeed. In addition to PKCS#1v1.5, there are ISO/IEC 9796-2 schemes 1 and 3 (with defined-in-advance parameters such as choice of hash), and the defunct ISO/IEC 9796(-1), which are RSA-based signature schemes such that a single valid signature exists for any signed message, implying there is no subliminal channel.
– fgrieu
Dec 20 '14 at 10:29