Reduction from signatures to encryption? Is it possible to construct an (asymmetric) encryption scheme from a signature scheme?

If the signature scheme is deterministic and allows existential forgery (e.g. RSA), then the answer is yes (create a forgery (m, sig); encrypt plaintexts using AES with sig as the key; send m in clear to the signer along with ciphertexts, who can then compute sig and decrypt these ciphertexts) .

I am interested in similar reductions for probabilistic signature schemes.

What should the properties of a probabilistic signature scheme be so that it can be used for encryption?
Let's first define a few things. Precise definitions are needed because your question is a bit ill-defined, and it seems that you are somewhat cheating.

Some definitions

Traditionally, we define a signature system as the combination of three algorithms:


G: key generation; given a "security parameter" t (e.g. the intended key size), yields a key pair (x, y) (x is the private key, y is the public key).
S: signature generation: given a message m (from a given space of messages M) and x, outputs a signature s.
V: signature verification: given m, y and s, outputs true or false.


It is supposedly infeasible to do forgeries, i.e., given y but not x, find (m, s) such that V(m, y, s) = true. Existential forgeries are "untargetted" forgeries where the attacker does not get to choose m arbitrarily.

On forgeries and "cheating"

Forgeries are bad, and a signature algorithm which accepts forgeries (existential or not) is considered to be broken. No "standard" signature algorithm accepts existential forgeries. In particular, RSA, as specified by PKCS#1, does not, even when using the "old style" v1.5 padding, which is deterministic: no method is known to generate a number s which, when raised to the public exponent, yields a proper PKCS#1 padding (beginning with 0x00 0x01 followed by eight or more 0xFF bytes). Moreover, the message m is first hashed, and even if you could find a s which produces, when exponentiated, a properly padded hash value, you would still be hard pressed to compute the corresponding m.

So, assuming that you want to apply your method on RSA, you are not talking about "RSA, the signature algorithm"; you need to remove the padding and the hash function, at which point you have the RSA core modular exponentiation, also known as "RSA, the trapdoor permutation". A trapdoor permutation can be used quite immediately for asymmetric encryption. In that sense you are "cheating".

@PulpSpy uses a different cheat, by assuming that he can publish the private key, and keep the public key secret. This may work with RSA, but only if the signature engine (the one which produces the signatures) accepts to work with a "private" key expressed as a raw private exponent and modulus, without knowledge of the modulus factors. "Normal" RSA implementation use the standard private key format, which includes the factors because this speeds up quite a bit private key operations (by a factor of about 4, thanks to the Chinese Remainder Theorem). Also, the "public" key needs to be kept secret, which implies a big exponent, not the usual 3 or 65537; there again, an existing RSA "verifier" implementation may refuse to work.

Rewriting the problem

I suggest the following definition of the problem: let (G, S, V) be a signature system. A key pair is generated; the key holder (Alice) maintains x (the private key) secret, in a box which computes S. The only way to use x is to execute S, which produces a signature on a given message m. The public key y is known by everybody, and Bob has some strong assurance that y is Alice's key through an unspecified mechanism (e.g. a certificate), but there is no other value which is thus unambiguously linked to Alice. Is there a way for Bob to use y in order to convey a confidential message to Alice ?

Note that clause about "no other value". If we allow Alice to publish other data, she could generate a transient key pair for an asymmetric encryption or key exchange algorithm, which Bob would just use (this is how it is actually done in S/MIME when the certificated key of a user is only for signatures). Correspondingly, we are after an asynchronous solution (Bob does all the job in one go, and only then sends the whole to Alice; otherwise, in an interactive protocol, Alice could "cheat" by sending a transient key pair).

For the interest of the exercise, we allow Alice and Bob to input precomputed hash values into S and V: no need to find messages m such that h(m) "works", we accept hand-crafted "hash values" which did not involve a hash computation at all.

With the question stated as above, there is now a good reason why this cannot work with signatures schemes based on a non-interactive zero-knowledge proof. A ZK proof is a protocol in which a prover demonstrates to a verifier knowledge of the solution of a given "problem". The protocol is said to be zero-knowledge because the transcript of the protocol is unconvincing: it is possible, without knowing the actual solution of the problem, to build a fake conversation between a "prover" and a "verifier", and there is no way to distinguish between a fake conversation and a real conversation with the true prover. In that sense, no information about the secret data leaks to the outside. A ZK protocol can be turned into a signature scheme: in a normal ZK protocol, the prover sends one or several commitments, then the verifier sends a challenge, to which the prover can respond in a way which is satisfying with regards to the committed values. It "suffices" to compute the challenge from the commitments using an appropriate one-way function, to make the protocol non-interactive; if a message is also used as additional input to the one-way function, then we have a signature algorithm.

This category of signature algorithm includes all the discrete logarithm-based signature schemes: ElGamal signatures, DSA, ECDSA, Schnorr... (they actually use a slightly weakened variant of ZK dubbed "computational zero-knowledge" because their ZKness is relative to the hardness of some operation, here the discrete logarithm).

The point of the ZK property is that producing the signature leaks no information about the signature key, except that the signing box knows it. For an asymmetric encryption or key exchange scheme, Alice must be able to extract at least one bit of extra information from is signing black box. Here, everybody knows that Alice owns the private key, and any signature generated by S will say nothing more. Therefore, there is nothing that Alice can do with S and what Bob sent her, that will yield any information suitable for a key exchange.

Rewriting this as a properly formal proof looks like hard work. So, right now, what I wrote above is merely "intuition". It means that I find it improbable that one could find a (non-cheating) way of turning an ECDSA-signing-box into a key exchange mechanism.