One-Round Cat Exchange

Suppose two parties have generated public/private keypairs and published their public keys. Non-interactive key exchange (NIKE) allows them to agree on a shared secret key without interaction.

This is the internet, so let's demonstrate with cats. The private key is represented by a male cat, and the corresponding public key by a female cat of the same colour. Alice generates a keypair and publishes her public key, and Bob does the same.

Now Alice can obtain Bob's public key, and combine it with her private key to generate a shared secret key. Alice's private key is a male cat, and Bob's public key is a female cat, so they make a shared secret kitten. As anyone with basic knowledge of feline genetics knows, two cats of different colours will have offspring in the colour of the parent whose colour has the largest hex value, with spots in the colour of the parent with the smaller hex value.

Bob used his private key and Alice's public key to generate the shared key. These kittens look the same, so Alice and Bob now have a shared secret key. Great! However this process always generates the same key, which is a problem if the key is compromised. One-round key exchange (ORKE) can help. At the cost of one round of interaction, Alice and Bob can have a whole litter of kittens.

In this week's study group Bin presented a generic construction of ORKE from NIKE published by Bergsma, Jager and Schwenk at PKC this year. The construction makes use of a deterministic strong signature scheme and a PRF.

The users generate NIKE keypairs as before, but now also generate signing keys.

To generate a shared session key, they generate temporary NIKE keypairs, and sign the temporary public key.

After receiving the other party's signed temporary public key, they can compute a shared secret key. First they check the signature is valid, and then they begin computing four NIKE keys using each possible permutation of temporary and long-term NIKE keys available.

Though Alice and Bob compute the second and third keys in a different order, this doesn't matter since the final key is computed through the commutative XOR operation. In fact the session key isn't just the XOR of the four NIKE keys - the NIKE keys are used as keys for a PRF evaluated at a common point derived from the long-term public keys, and the outputs XORed - but why let details clutter cartoon cats. The scheme is secure in a version of the enhanced CK security model for key exchange, and is standard model secure if instantiated with standard model secure components. The proof is quite straightfoward, ignoring the complexities of the security model itself, and you can check it out on eprint.