Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.
Sign up to join this community
I have read up on Digital signature and it is stated that it provides non-repudation.
Assuming Alice signs the message using her private key and sends it to Bob, Bob can use Alice's public key to verify the signature hence Alice cannot deny sending the message. This only proves that Alice is the sender of the message.
How can Alice have proof that Bob has received the message sent from Alice?
In practice, unless Bob sends a signed receipt, you are out of luck.
The underlying cryptographic problem is called fair exchange. If you consider a network protocol such that Alice and Bob want to send each other some data elements (e.g. in your case an email from Alice to Bob, and a receipt from Bob to Alice; but it also works as a model for payments), then Alice and Bob will send messages. Let's call ma the element that is to be conveyed from Alice to Bob, and mb the element that should go from Bob to Alice. When the exchange protocol is played, at some point in the sequence of messages, Alice will obtain enough information to be able to rebuild mb. That point will be immediately after reception by Alice of some protocol message from Bob; before the message, Alice does not know enough to rebuild ma, and after she does. Similarly, Bob will also obtain enough information to rebuild mb right after having received some message from Alice.
The tricky point is that there is no such thing as simultaneity. You cannot ensure for two remote people (Alice and Bob) to send messages at the same time. Thus, Alice and Bob get all they need at necessarily distinct moments. Suppose that Alice gets her element first; then she may simply stop responding at that point. Bob will never get the element from Alice, while Alice got the one from Bob. The exchange is unfair.
To get some intuition about what I explain above: suppose a simple protocol by which Alice sends an email to Bob, then Bob sends a signed receipt. In that case, Bob could get the email and refuse to send the receipt; Alice would have no proof. To fix that, you may want to design the protocol such that Bob sends the receipt first, and then Alice sends the email. In that case, Alice could cheat by getting a receipt from Bob, then refusing to complete the protocol and send the email.
What I mean here is that the flaw is fundamental. There can be no two-party protocol, however complex and convoluted, that ensures a fair exchange. This is because of the lack of simultaneity.
Now impossibility results have never discouraged people from trying. There are mostly two methods to get a fair exchange protocol:
Make it so that cheaters pay for it. For instance, Alice sends an encrypted email to Bob, with a symmetric key Ka. Bob sends an encrypted email to Alice, with a symmetric key Kb. Alice and Bob then send each other the keys, bit by bit, one at a time. Either may bail out of the protocol at any time, with a partial key knowledge, and try to complete decryption through exhaustive search of the missing key bits. A cheater will then have an advantage over the other, but only by one bit in the resulting brute force. There is some remaining unfairness, but only a small one.
For such a protocol to work, some additional mathematics must be thrown at it, so that Alice and Bob may prove to each other that the "encrypted messages" they sent are the genuine things, and not some chunks of random junk. There are a lot of details to care about.
Have a trusted third party. This is the model of existing postal services around the World. Alice gives the letter to the postal service; the postman then ensures that Bob will get the letter only after having signed the receipt. This works because both Alice and Bob trust the postman: Bob knows that the postman will give him the letter, and thus has no problem with signing the receipt before having the letter in his hands; Alice knows that the postman will not give the letter to Bob without receiving a receipt first, and the postman will send the receipt back to Alice.
Standard emails follow neither method right now. Some people are running Web-based services in which they play the role of the trusted third-party; I am not sure any of them has reached any level of significant commercial success. I am not aware of any deployed in the wild implementation of a cryptographic fair exchange protocol.
TL;DR Anyone can send a message and say it is from Alice if it is not signed; there is no way for Alice to prove that she didn't send those unsigned messages. However, Alice can prove she sent a message by signing it with a private key. Similarly, anyone can say Bob read a message, and Bob can't prove he didn't. But Bob can prove he read a message by signing it with his private key.
A small side point, I'm going to make a distinction here between having received and read a message. I can send an email to your mail server, (and the network will confirm that it was sent), but if your server is ignoring all incoming data, even though the network says it was received by your firewall, it doesn't mean the mail server actually read the message or has access to it in any way.
In good cryptography, it's assumed everyone can receive the message, but only the indented recipient can read it. Even though Alice here isn't actually encrypting specifically for Bob, we will assume that the message is posted in some public way that it guarantees that Bob could receive it if he wanted to, but encrypted so only Bob can read it (even though you might not technically encrypt it, just require Bob to log into Gmail with his username and password, but the same principle).
In such a case, there is no way for Bob to prove he hasn't received the message; after all, Bob could download (receive) the email from Alice from the mail server to his computer, but not actually open (read) it. If the message was encrypted, he could save the message and his private key to a non-networked computer and decrypt and read it there, burning the computer after he is done. No one could know if he successfully successfully decrypted and read the message or not.
However, at any time, Bob can prove that he has read the message by signing the decrypted message Alice sent, and sending back the signature. The only way he could have access to and sign the decrypted version (which would include having read the non-encrypted email from his Gmail account) was if he had read it.
Addendum: Ideally, Bob would sign the message with his own private key, but this isn't strictly necessary. As long as the message "encrypted" (or sent securely) in some way that only Bob can read it, the only one that could possibly have access to and sign the "decrypted" message is Bob*. If the message is not encrypted or sent securely, anyone could sign Alice's message with any key, claiming to be Bob that signed it.
* Technically, there is a second person who could sign the decrypted message: since Alice wrote the email to Bob, she has access to the unencrypted message and could sign it, claiming to be Bob. If she just wants to know if Bob read her message, this would be silly of her to do. However, if Alice wants to prove to the authorities that it was Bob that read her email, Bob would need to sign the decrypted message with his private key (which Alice would not have access to).
If you want to require Bob to let Alice know whenever Bob has received a message, as far as I know there isn't any such system built into the most common cryptographic systems. You would need to go outside of cryptography for a bit and require a server which tracks every time a message is downloaded from it.
For instance, Alice could send a secret URL to Bob that tells him where he can find the message. When Bob opens that URL, the server on the other end tracks that Bob has accessed the URL, sends a receipt to Alice, and sends the data to Bob. If you want to be pedantic, there is always the possibility that Bob says the URL request didn't complete, and although he sent a request for a message, there was a network problem, and he never received and read the data.
This next part was supposed to be a comment, not part of the answer, but is too long for the comment field:
You could devise an elaborate cryptographic system where each time Bob accesses the URL he receives (1) a single character of the message and (2) a small bit of data he has to sign with his private key. He stores the character (appending it to the data he has already received), and then signs and sends back the bit of data to get the next character of the message.
Alice can therefore prove exactly which characters in the message Bob has received. Well, almost exactly. Keep in mind, Bob could always say "I received 499 characters, but not the 500th character, therefore I didn't get the entire message." assuming he refused to send back the proof of work for the last character he received.
Alice could also do this on a per-message basis rather than a per-character basis. In each message, Alice sends instructions on how to decrypt the text message (perhaps including a one-time pad). She can never prove that Bob has read the latest message she sent, but if she can prove that Bob has read a single message, she can prove that Bob read every message before that one.
There is only one way for Alice to truly prove that Bob has received her message:
Even with asymmetric keying, you can only have reasonable assurances that the communication channel is secure and that the intended recipient is receiving your messages.
You can guarantee that Alice's private key was used to encrypt a message. You can guarantee that Bob's private key was used to sign receipt of a message. What you cannot prove is whether Alice or Bob were the bearers of those keys at the time of transmission.
My point is, there is no way to -mathematically- guarantee secure communication of distributed messages. Your best case scenario smashes face first into a brick asymptote that cannot be overcome, so words such as "proof" and "guarantee" should be avoided. Your best case scenario is "Ehh, that's close enough."
The only way for Alice to guarantee that Bob receives her message is to physically hand it to him, and that only holds true if Alice can physically identify Bob, unfailingly.
