11
$\begingroup$

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.)

Improve this question
$\endgroup$

3 Answers 3

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ DH provides no authentication. $\endgroup$
    – Smit Johnth
    Commented Apr 4, 2013 at 19:39
  • 3
    $\begingroup$ @SmitJohnth: actually, in this case, it does, at least it does cryptographically bind the authenticated message to the public key. In standard DH, both sides pick an ephemeral exponent, and send the public value to the other side; there is nothing inherent in the DH protocol that binds the public value to any identity (and hence that needs to be added somehow). In my proposal, the public value is the public key; a third party cannot generate a message which will authenticate. How the public key is bound to the 'identity' is out of the scope of the protocol; all PK systems have to handle it $\endgroup$
    – poncho
    Commented Apr 4, 2013 at 19:49
  • $\begingroup$ But you don't know whom the key belongs. But if you say you use signed DH, all will be fine. $\endgroup$
    – Smit Johnth
    Commented Apr 4, 2013 at 20:19
  • 4
    $\begingroup$ @SmitJohnth: if you look at the original question, Paulo asked for a single message protocol where the first step was that "Bob can construct a message using ... Alice's public key." That means that Bob is assumed to somehow know Alice's public key (and know that it is, indeed, Alice's). That he knows that is indeed important; however, as far as this protocol is concerned, it is a problem that has already been somehow solved. $\endgroup$
    – poncho
    Commented Apr 4, 2013 at 22:21
6
$\begingroup$

What you want is exactly one of the use cases of ring signatures.

A ring signature scheme allows you to choose an ad-hoc group of public keys and compute a signature in such a way, that it could have been created by any holder of one of the corresponding secret keys but by nobody else.

The privacy of the construction from the paper linked above is perfect. I.e. even for unbounded adversaries it is impossible to decide, which secret key was used to construct the signature. However the signature remains computationally unforgeable.

When set up with a group of only two public keys, you will get exactly the security guarantee you want. You can be sure that the other other party signed the message (because you know that you did not sign it yourself) but you are unable to prove that to any third party.

Maybe I need to explain this more clearly:

Assume that all parties have a keypair and all public keys are known to all parties. Then to generate a ring signature for the group {Alice, Bob, Carl} all Alice needs is the public keys of Bob and Carls, as well as her own secret key.

The nature of the resulting signature is then that it might have been produced using either $\{sk_A,pk_B,pk_C\}$, $\{pk_A,sk_B,pk_C\}$, or $\{pk_A,pk_B,sk_C\}$ and nobody can tell which of the three it was.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the answer, I learned something new today. Ring signatures as described in the linked article are a generalization of what I wanted, yes. $\endgroup$
    – Paŭlo Ebermann
    Commented Dec 14, 2012 at 23:34
1
$\begingroup$

Here's another idea, which seems to be quite similar to poncho's solution, but uses RSA keys:

Bob writes his message $P$, creates a random symmetric key $K$ and uses a MAC to calculate a MAC tag $T$ for the message. He signs only this key $K$ with his private RSA key, and also encrypts it with Alice's public key.

The transmitted message consists of the plaintext, the MAC tag, the encrypted MAC key and Bob's encrypted signature of the MAC key: $(P, T, Enc_{Alice}(K, Sig_{Bob}(K))$. (If the message shouldn't be transmitted as plaintext, a key derivation function could be used to generate both a MAC and a symmetric encryption key from $K$, to respectively encrypt and authenticate the message.)

Mallory will not be able to modify the message plaintext (since she doesn't know the MAC key), Alice will be able to verify that the message is really from Bob (he signed the MAC key), but she can't prove the fact to anybody else (the MAC key is symmetric and can be used to create MAC tags for arbitrary messages created by Alice).

This scheme could presumably be used with existing asymmetric, asynchronous schemes like PGP.

Please don't go ahead and use this, though - somebody who actually knows what they are doing should verify it first.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Depending on the actual signature algorithm, one might be able to extract $K$ from $Sig_{Bob}(K)$. In that case Mallory knows the MAC key and can modify the message (and tag). If so, either use $Enc_{Alice}(Sig_{Bob}(K))$, or sign only a hash of $K$. $\endgroup$
    – Paŭlo Ebermann
    Commented Aug 23, 2013 at 15:40
  • $\begingroup$ Doesn't appear to answer the question: one requirement is "Alice can construct the same message using her private key (maybe also her public one) and Bob's public key". How is Alice supposed to generate $Sig_{Bob}(K)$? $\endgroup$
    – poncho
    Commented Aug 23, 2013 at 15:47
  • $\begingroup$ @poncho: That's correct, Alice can't create exactly the same message. However, since by the protocol, K is randomly chosen for every message, the only information that can't be repudiated by bob is "at some point, Bob authenticated a message using K". Depending on the application, that might be acceptable. $\endgroup$
    – lxgr
    Commented Aug 23, 2013 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.