The Newton Channel

Simmons asked whether there exists a signature scheme with a broadband covert channel that does not require the sender to compromise the security of her signing key. We answer this question in the affirmative; the ElGamal signature scheme has such a channel. Thus, contrary to popular belief, the design of the DSA does not maximise the covert utility of its signatures, but minimises them. Our construction also shows that many discrete log based systems are insecure: they operate in more than one group at a time, and key material may leak through those groups in which discrete log is easy. However, the DSA is not vulnerable in this way.