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?



1 Answer 1


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, 2014 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, 2014 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, 2014 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.