How does a public key authenticator work? (as opposed to public key signatures)

Question

In the documentation for djbs library NaCl under the headline Security model you can read that the library provides public key authentication without non-repudiability (http://nacl.cr.yp.to/box.html). How is this possible when the parties have no shared symmetrical secret?

Answer 1

Skimming the NaCl PDF I think they just generate such a shared secret.

In an interesting fashion:

Section 5: Alice, using Alice’s secret key a and Bob’s public key B, computes a 32-byte secret k. Bob can compute the same secret using Bob’s secret key b and Alice’s public key A.

Using that shared key they then seed a pseudorandom generator. The first 32 bytes of which are used as the authenticator secret. And the rest of which are used for actual encryption.

DJB's definition

DJB's definition on Google groups:

What is a public-key authenticator? It's a secret-key authenticator, with a key derived from g^xy, where g^x and g^y are the public keys of the sender and the receiver.

If you were already planning to encrypt the message, using another key derived from g^xy, then you don't have to do any extra public-key work. A secret-key authenticator is easier to implement than a public-key signature, and it takes less CPU time to compute.

I guess if he had named it "public-key derived authenticator" instead then the idea might have been more obvious.