Signature that can only be verified by author and recipient - without pre-shared key

Question

Desiderata:

• Alice wants to send a message to Bob for him to keep and to be able to refer to, such that Bob can be certain that the message came from Alice and was not tampered with.

• Alice also wishes to store a copy of the message such that she can refer to it in future, and be sure that it has not been tampered with.

• Some time after Bob has verified Alice's message, Mallory obtains access, on an ongoing basis, to copies of all information that Alice and Bob possess or receive (including plaintexts and signatures/MACs), aside from secrets Alice and Bob store in their minds.

• Despite Mallory's access to all this information, Mallory still cannot prove that Alice ever signed the message.

Context:

• Alice rightfully trusts that Bob's public OpenPGP key is indeed Bob's.

• Alice and Bob both keep their OpenPGP private keys out of Mallory's reach (e.g. using OpenPGP smart cards).

My question: regardless of whether OpenPGP is used in the solution, can Alice achieve her desiderata?

Answer 1

As long as Bob keeps his private key secret you can simply encrypt everything which only Bob should see with Bobs public key. This also includes the signature, i.e. when sending a mail from Alice to Bob:

• encrypt the mail with Bobs public key
• make a detached signature for this mail using Alice private key
• encrypt this detached signature using Bobs public key
• include this encrypted signature with the mail

Since Bobs private key is needed to get back to the original signature and this key is still secret, Mallory will not be able to get the original signature and thus cannot validate it. Bob instead can verify the signature.

Of course the whole procedure depends on the idea that Mallory can at most get access to the original message sent from Alice to Bob and never to the original signature.

As for the requirement that Alice wants to keep a copy of the message: there are several ways to do this and I don't see that this requirement needs to be part of the process. But to not uselessly leak information she might want to refrain from using their widely known public key for this.

Answer 2

The question is really about deniable authentication. There might be more than one way for the desiderata to be satisfied in the context given. For example, Alice and Bob could follow this protocol:

Alice creates an OpenPGP signing key-pair with a fake name. She sends an encrypted email to Bob with the "public" key attached and instructs him to keep that key but not to publish it, not to associate it with her, and to destroy the email to which the it was attached. Alice also keeps a copy of that "public" key for herself.

Alice then signs her plaintext with the private key from that key-pair and sends a copy of the plaintext and signature to Bob, also keeping copies of both for herself. She then destroys the private key.

Bob and Alice are thereafter able to use the "public" key, together with the secret knowledge in their mind that this key corresponds to a private key that was only ever controlled by Alice, in order to verify the integrity and source of the message.

Once Bob has complied with Alice's first message, it no longer matters whether Mallory has access to copies of the information Bob receives, stores and processes outside his brain.

Similarly, once Alice has destroyed the private key, it no longer matters whether Mallory has access to copies of the information Alice receives, stores and processes outside her brain.

Because Mallory does not know the secret of who controlled the private key that signed Alice's plaintext, all Mallory can tell is that someone signed the plaintext: Mallory cannot prove who that person was.

Unfortunately, once Mallory has access to copies of the information Alice and Bob receive, store, and process outside their brains, Alice and Bob can no longer achieve deniable authentication for future messages. That weakness might be a problem for any protocol, however.