Bob wants to send a message to Alice, such that Alice can be sure that the message came from Bob, but can't prove it to anyone else.
If I understand right, this means that the same message could have possibly also been constructed by Alice, but not by Eve (who can observe, change, remove and inject messages).
The usual solution would be a MAC using a shared secret, but suppose there is no such shared secret (for example, as Bob and Alice didn't communicate before).
We can provide, however, a public-key infrastructure of some kind, so Alice and Bob know (or can obtain securely) each other's public keys. (Maybe multiple keys per owner, if needed.)
Is it possible to create some (non-interactive, i.e. single-message) protocol such that the following conditions are fulfilled?
- Bob can construct a message using only his private key (maybe also his public one) and Alice's public key.
- Alice can use her private key (maybe also her public one) and Bob's public key to verify that this message is from Bob.
- Eve, who knows neither Bob's nor Alice's private key, can't construct a message which will pass Alice's check.
- Alice can construct the same message using her private key (maybe also her public one) and Bob's public key.
What kind of primitives are needed here?
I don't require Bob's message to be encrypted, but your protocol might do so, if this is easier to realize. I only care about the authentication & repudiation part.
(If these conditions are not sufficient or not necessary for authentication without non-repudiation, please point this out, too.)
(This question is inspired by Can I use PGP to sign a message without providing cryptographic non-repudation?, which asks for a solution of a similar problem using OpenPGP and signatures, but doesn't actually specify the requirements. This one is wider and more on a theoretical level.)