Can you create an encryption algorithm from a signing algorithm, or vice versa?

Question

I remember reading, a few years ago, that you couldn't prohibit encryption without prohibiting signing, as you can always make a public key encryption algorithm from a signing algorithm.

(It might be that you can always make a signing algorithm from a public key encryption algorithm.)

Furthermore I remember than this operated bitwise, so that each bit needed to be signed in some manner in order to encrypt a message.

Obviously such algorithms would be horribly inefficient, but are they possible?

Answer 1

There is confusion here between the symmetric and asymmetric worlds. For symmetric, it is indeed true that it's possible to build encryption from message authentication and vise versa. Theoretically this is trivial since both primitives imply one-way functions, and one-way functions suffice for constructing both symmetric encryption and MACs. A more direct solution, where you are given only black box access to the MAC was presented by Rivest in a paper called Winnowing and Chaffing by Ron Rivest.

Your question relates to the asymmetric setting. In this setting, encryption indeed implies signatures since one-way functions suffice for constructing digital signatures. However, there are black-box separations that show that public-key encryption cannot be built from one-way functions (or even one-way permutations or hash functions). Thus, a major breakthrough would be needed for this. For example, we know how to build digital signatures from hash functions, but we cannot build public-key encryption from hash functions (when looking at the hash function as a black box).

In short, the answer is no. You cannot in general build public-key encryption from digital signatures (via black-box constructions). The question of whether this could be done nonblack-box is open, but it would be hugely surprising if yes.

Answer 2

you can always make a public key encryption algorithm from a signing algorithm

I think this statement either

• was made for asymmetric crypto blackboxes with a textbook RSA in mind, but is wrong: we can't turn an RSASSA-PSS, DSA, ECDSA, or EdDSA signing blackbox into a decryption box for any secure asymmetric encryption algorithm.
• was made for asymmetric crypto algorithms, but still is wrong in theory (e.g. Lamport signature), even if sort of true in practice (it's easy to turn RSA signature to encryption; that possible for ECDSA, e.g. ECIES).
• has drifted from a true statement for symmetric crypto blackboxes: that one can make strong symmetric encryption from strong MAC, which is correct (we can build a Feistel cipher).

Answer 3

In the aspect of theory, Encryption and signatrue scheme both are on the basis of one-way function, which can prevent ciphertext and signature from revealing and forgery respectively. Therefore, at this point, it seems that converting between the two could be possible, such as RSA, elgmal in textbook, etc.

Howerver, in practice, duo to the security requirements of the two are totally different, such that for a encryption scheme, it should meet IND-CCA security; but for a signing scheme, it should meet UF-CMA security.

So, generally speaking, the type of mathematical assumption the two based on is also different:

1. The encryption scheme always based on decisional assumptions, such as DDH, DLP, etc., to confuse the adversary that whether the ciphertext c is the encryption result of $m_1$ or $m_0$. Thus, we can conclude that the encryption algorithm should be probabilistic.
2. The signing scheme always based on computational assumptions, such as CDH, SDH, etc., to prevent the adversary from forging a valid signature. we also can conclude that the signing algorithm should be deterministic.

This is my opinion about your question, not detailed but should be able to answer your question.