3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ What do you mean by prohibit? $\endgroup$
    – Ievgeni
    Jun 23, 2021 at 12:30
  • $\begingroup$ $\implies$Reduction from signatures to encryption? $\endgroup$
    – kelalaka
    Jun 23, 2021 at 15:03
  • 1
    $\begingroup$ This could be Rivest's classic Chaffing&Winnowing although he proposes small packets not (necessarily) single bits, and he calls it an alternative to rather than a form of encryption. It was published largely as an opposition to the US government's policy at the time of prohibiting most export encryption while allowing signature and authentication. $\endgroup$ Jun 24, 2021 at 0:16

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, yes, Winnowing and Chaffing was what I had read. $\endgroup$
    – fadedbee
    Jun 24, 2021 at 6:47
  • $\begingroup$ Strangely, that paper was one of the first that I ever read in cryptography :-). $\endgroup$ Jun 24, 2021 at 7:00
1
$\begingroup$

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).
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This is incorrect. Signature schemes do not require trapdoor functions or trapdoor permutations. They can be constructed from one-way functions only. Also, the question isn't whether one can use the encryption scheme as is, but whether you can construct one from the other. Thus the fact that they have different security requirement doesn't answer the question. $\endgroup$ Jun 24, 2021 at 6:41
  • $\begingroup$ @YehudaLindell Professor, It is an honur to meet you here:). Recently, I'm studying how to modify the zk-SNARK method to be used into anonymous authentication scheme, but no clew :(. Could you give me some ideas to promote my research? Ha,ha, it is a luxury question I thought. $\endgroup$
    – ming alex
    Jun 24, 2021 at 7:49
  • $\begingroup$ Pleasure to meet you too! If I understand your goal, you want to get a short anonymous authentication scheme. I am not an expert in that area, and I assume you are familiar with the body of work by Anna Lysyanskaya, Jan Camenisch, and Jens Groth in the area. Sorry I can't help much, but best of luck! $\endgroup$ Jun 24, 2021 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.