I have the following problem: Alice wants to send Bob a message such that Bob knows it is from Alice but at the same time he cannot prove that Alice send him this message.

The solution I came up with, using RSA, is:

  1. Alice picks a random key K, and encrypts the message M using this key K. M'= aes(K, M)
  2. Alice hashes K and Bob's public key to get H. H = sha(K + Bob's Public Key)
  3. Alice signes H using her private key. S = rsa_sign(Alice's private key, H)
  4. Alice encrypts K and S using Bob's public key. P = rsa_encprypt(Bob's public key, K + S)
  5. Alice sends P, M' to Bob

Bob receives P, M':

  1. Uses his private key to get K, S.
  2. Uses Alice's public key to verify S
  3. Uses K to decrypt M'.

Do you see any holes in this?



In step 2 for Alice, what is the purpose of including Bob's public key in the hash? you can include a timestamp to prevent replay attacks instead.

In step 2 for Bob, there is a typo - should use Alice's public key instead of her private key.

Actually your protocol is similar to PGP, and I dont think it provides deniability because if Bob can prove that the public key belongs to Alice then the owner of the private key is most likely Alice.

  • $\begingroup$ Bob's step 2. You are right! Fixed it. Regarding Step 2 for Alice. It is there so Bob cannot use K to encode another message and send it to Eve pretending it was from Alice to Eve. Regarding deniability, Bob can prove that Alice sent him a message, but he cannot prove it was M, since having access to K allows him to construct any message he wants. $\endgroup$ – user11693 Jan 29 '14 at 2:27
  • 1
    $\begingroup$ oh I see.. So that was the reason the message M wasn't included in the hash. Then this leads to another issue, Bob cannot be sure that the received message was unmodified since encryption alone does not provide integrity. $\endgroup$ – jingyang Jan 29 '14 at 3:14
  • $\begingroup$ Hmm. Good point! I guess I will have to work that out as well. Thanks! Do you see any other holes? $\endgroup$ – user11693 Jan 29 '14 at 21:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.