Reduction from signatures to encryption?

Question

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?

Answer 1

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.

Answer 2

In principle, the answer is no, with an asterisk. Signature schemes are equivalent to one-way functions under black-box reductions. Public-key encryption scheme implies the existence of key agreement.

Impagliazzo & Rudich famously proved that there is no black-box reduction from one-way functions to key agreement. That means there is no subroutine-respecting way of transforming a one-way function (equivalently, a signature scheme) into a key agreement scheme. They have not ruled out the possibility of a very clever way to use the code of a signature scheme to construct a key agreement scheme, but this seems highly unlikely (not to mention that such techniques are typically highly impractical).

Note: FYI, I originally answered this having misread the question to refer to symmetric-key encryption. In that case, the answer is yes:

Any signature scheme can be converted in a black-box way to yield a symmetric-key encryption scheme. Both of the two primitives are equivalent to one-way functions under black-box reductions.

One way to do it:

1. A signature scheme yields a one-way function in a very straight-forward way. More specifically, the following function is one-way: on input $x$, interpret $x$ as random coins to give as input to the key generation algorithm of the signature scheme. Give the resulting verification key as output of the (one-way) function.

2. A one-way function yields a pseudorandom function, using the GGM construction.

3. A pseudorandom function $f$ yields a symmetric-key encryption scheme in a very easy way. Let $s$ be the secret. Then to encrypt a message $m$, choose a random $r$ and give $(r, n \oplus f(s,r))$ as the ciphertext.

   3a. If you don't like that, you could instead plug the pseudorandom function into a Feistel network (Luby-Rackoff construction) to obtain a strong pseudorandom permutation (i.e., a block cipher) and use a good block cipher mode.

MACs can also be constructed from one-way functions, so you can pretty much get any kind of symmetric-key cryptography, and symmetric-key CCA security is no barrier.

Interestingly, nothing about this construction uses the signing algorithm -- just the asymmetry of the signature scheme's key generation is enough.

Answer 3

Chaffing and Winnowing creates a symmetric encryption scheme from a symmetric MAC:

http://people.csail.mit.edu/rivest/chaffing-980701.txt

I suppose you could apply the same technique to your problem—send each bit of your message separately, obscured by the presence of chaff, and send signatures indicating which are the message bits. This assumes that the public (verification) key is secret and known only to the intended recipient and that you can't tell which bits have valid signatures on them without it.

Warning: this is just off the cuff—I haven't thought this through very much.

Answer 4

First in response to your example. In proving a encryption scheme is secure, you have to assume that an adversary has at least as much computational power as the participants. Therefore if Alice is sending a message to Bob, and Alice can find a forgery, then the adversary can as well. Since the signature is deterministic, the adversary now has the key and can decrypt the messages. (You could argue that Alice's forgery is easier to find since she chooses the message and so it may be secure in a gap group where existential is easy and selective is hard.)

Next, there are different types of reductions. I will use a blackbox reduction. This means we use the signature/verification functions without any knowledge of how they work but we are allowed to supply wrong inputs to the functions: for example, submitting a key where we should a message or submitting a signing key where we should use a verification key.

A public key encryption scheme can be built from a blackbox non-deterministic signature scheme as follows:

• Bob generates a signing key and verification key.
• Bob makes the signing key public and the verification key private (opposite of typical).
• Alice takes her message and will encrypt it bit-by-bit.
• Alice takes the first bit.
  • If it is 0: Alice generates a random string, signs the string with Bob's key, and outputs the string and signature.
  • If it is 1: Alice generates a random string, generates a fake signature, and outputs the string and fake signature.
• Bob receives the pairs of strings and uses his private verification key to see if the signatures are valid (decrypts a 0) or invalid (decrypts a 1).

Informally, an adversary has two lines of attack. One is to see if the pairs of strings are valid, however assuming the signature scheme is secure, this will not work without the verification key (see fineprint). The second is to sign the strings with the signing key and see if the signatures match what Alice sent. This will not work because the signature is randomized and the signatures will overwhelmingly never match.

Fineprint: my signature scheme assumes there is a verification key and without the key, you cannot verify the signature. This is not the case for all signature schemes, in particular ones based on pairings (eg BLS) where verification is public and does not require a key. On second thought, it is not even the case for DSA where the verification key is easily computed from the signing key. I guess it only works for RSA (and similar) signatures.

Answer 5

Wait, is the goal for Bob to encrypt messages to Alice (who holds the secret signing key) or for Alice to encrypt messages to Bob (who knows Alice's public key)? If it is the former, then I can't think of any way around Thomas Pornin's excellent argument above. If it is the latter, and if we grant my assumption that nobody else apart from Bob knows Alice's public key, then my proposal above based on Chaffing And Winnowing might work.