Authentication and deniability 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:


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


Bob receives P, M':


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


Do you see any holes in this?

Thanks!
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.