Join Log in
Score:3
fadedbee avatar Crypto

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

br flag
fadedbee

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?

168
3 + 3
Ievgeni avatar
cn flag
Ievgeni
What do you mean by prohibit?
0
Reply
kelalaka avatar
in flag
kelalaka
$\implies$[Reduction from signatures to encryption?](https://crypto.stackexchange.com/q/148/18298)
0
Reply
dave_thompson_085 avatar
cn flag
dave_thompson_085
This could be [Rivest's classic Chaffing&Winnowing](https://people.csail.mit.edu/rivest/pubs.html#Riv98a) 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.
1
Reply
Score:3
Yehuda Lindell avatar Crypto
us flag
Yehuda Lindell

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.

0 + 2
fadedbee avatar
br flag
fadedbee
Thanks, yes, Winnowing and Chaffing was what I had read.
0
Reply
Yehuda Lindell avatar
us flag
Yehuda Lindell
Strangely, that paper was one of the first that I ever read in cryptography :-).
0
Reply
Score:1
ming alex avatar Crypto
in flag
ming alex

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.

0 + 3
Yehuda Lindell avatar
us flag
Yehuda Lindell
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.
0
Reply
ming alex avatar
in flag
ming alex
@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.
0
Reply
Yehuda Lindell avatar
us flag
Yehuda Lindell
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!
0
Reply
Score:1
fgrieu avatar Crypto
ng flag
fgrieu

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).
0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.