Suppose Bob has a DSA key pair, and Alice has Bob's public key. Is there any secure way that Alice can send Bob a message only he can read if Bob can not send any reply?

I think the answer is no, since DSA is only for messaging signing, so can only be used for things like authentication and Diffie-Hellman key exchange.

  • 1
    $\begingroup$ DSA can't be used for DH key exchange. If it could you could implement ElGamal upon it. DSA can only be used to authenticate DH key-exchanges. Am I reading your question right as: Can I somehow turn DSA into a public key encryption scheme? - What do you mean by "if Bob can not send any reply"? $\endgroup$ – SEJPM Jul 19 '15 at 18:12
  • 1
    $\begingroup$ DSA is used only used for signing. So you are right. RSA can be used both for encrypting and signing. With DSA you have also non-repudiation (can not be used for key-exchange). $\endgroup$ – 111 Jul 19 '15 at 18:13
  • $\begingroup$ So if Alice were sending Bob a message in the mail, for example. A back and forth exchange is not possible. And oops with the DH thing! I thought the messages involved in DH needed to be signed? $\endgroup$ – AndrewH Jul 19 '15 at 18:15
  • 1
    $\begingroup$ DH by itself doesn't define the usage of signatures. However safe applications of DH require signatures. DSA also hashes the message always before signing it so there's no way in turning it an encryption scheme. $\endgroup$ – SEJPM Jul 19 '15 at 18:31

Let me first answer your actual question (and then I'll proceed to answer something slightly different that I think will be informative and helpful). Your question asks whether it's possible to use only a DSA key. Technically speaking, this is of course possible. The reason is that a DSA key has exactly the same format as an ElGamal key. No one forces you to use the key with the proper algorithm. (I know that this is a bit stupid, but it will be more meaningful after what follows below.) Just note that if you use the key both for DSA signing and for ElGamal encryption then you may have security problems, and you need to formally prove that this combination is OK. (By the way, this is all OK since Alice already has Bob's public key, so there is no problem of authenticating the key, etc.)

Despite the above answer, I have a feeling that what you are really asking is whether or not it's possible to use signatures alone in order to securely encrypt (in the public key setting, without a shared symmetric key). I'll translate it to "is it possible to use signatures alone to get key exchange" since key exchange is more relaxed than public-key encryption.

This is an excellent question. The first problem with the question is "how to formalize using one primitive to get another". The naive way of doing this is saying that if A exists then B exists. So, your question would be: is the following statement true "if signatures exist then key exchange exists". However, we believe that both signatures exist and key exchange exists, which if true, makes the statement logically true irrespective of any connection between signatures and key exchange. This led Impagliazzo and Rudich in their groundbreaking work Limits on the Provable Consequences of One 􏰀way Permutations to define that one primitive implies another if one can be constructed from the other using a black-box reduction (and in a world where no other crypto exists, which can be achieved by giving the adversary an NP-oracle to solve all NP problems, for example). Note that most (but not all) reductions in crypto are black box. It is beyond the scope here to define black box, but for here it suffices to say that the primitive is used based on its input/output functionality only, and the reduction uses the adversary in a black-box way as well.

Now, back to your question. The answer is no. Impagliazzo and Rudich proved that one-way functions do not imply key exchange in this setting. Stated differently, it is impossible to construct a black box reduction from one-way functions to key exchange. Noting now that signatures can be constructed from one-way functions only (One-Way Functions are Necessary and Sufficient for Secure Signatures, Rompel), this implies that there exists no black-box reduction from signatures to key exchange. I remark that this result by Impagliazzo and Rudich holds in the presence of an eavesdropping adversary only, so it has nothing to do with man-in-the-middle attacks or anything like that.

Let's conclude by going back to DSA. Note that it is possible to use a DSA key to get key exchange; as I said, just use it for El Gamal. However, this is exactly the difference. My use of DSA is not black box. Rather, I am utilizing the number-theoretic properties and the structure of the DSA key. Thus, this does not contradict the result of Impagliazzo and Rudich.

  • $\begingroup$ Excellent answer as well! You may want to add some reference (e.g. Rompel) to make it clear that signatures can be constructed from one-way functions only (in your second last paragraph). $\endgroup$ – DrLecter Jul 20 '15 at 7:19
  • $\begingroup$ @MaartenBodewes I'm not sure what you mean. What do you mean by generating a hash on one side and using the result on both sides? $\endgroup$ – Yehuda Lindell Jul 20 '15 at 12:45
  • $\begingroup$ I think that as long as the signature generation and verification is performed in the right order that black box key derivation is not possible. I've reused RSA signature generation/verification before but that meant using the public key for generation and the private key for verification - abusing some gaps in the API. Still, I think there is some grey area between using a black box and just the key information that is not completely covered by this answer (although I don't think tricks like above could work for DSA). $\endgroup$ – Maarten Bodewes Jul 20 '15 at 13:03
  • $\begingroup$ (and yes, this was for a proof of concept, not a actual product, I'm not that mad) $\endgroup$ – Maarten Bodewes Jul 20 '15 at 13:05
  • $\begingroup$ Wow! I must admit that a lot of that was over my head. The context that I ask my question is that of github users' public keys (most of which are either RSA or DSA) and whether it's possible to leave them a secure message without them actively negotiating a key to use. $\endgroup$ – AndrewH Jul 20 '15 at 23:22

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.