Is it possible to construct an (asymmetric) encryption scheme from a signature s

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.