Can one have an authentic, but repudiable, message without a previously shared secret? 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 &amp; 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.)
There's an obvious solution using DH: Alice has a private key $a$ and a public key $g^a$; Bob has a private key $b$ and a public key $g^b$.

When Bob sends a message, he computes the shared secret value $(g^a)^b$, converts that into a MAC key (possibly using a nonce to prevent key reuse), computes the MAC of the message, and sends the message and the MAC (and any nonce) to Alice.

When Alice receives the message, she computes the shared secret value $(g^b)^a$, converts that into a MAC key, and verifies the MAC.

Now, Eve cannot modify the message, because she doesn't know the MAC key, because she can't solve the DH problem based on the public keys $g^a$ and $g^b$.

Alice can validate that the message was sent by Bob.  However, she can't prove it to anyone else, even if she were willing to expose her private key, because she is just as able to generate that message as Bob was.