[messaging] MPHFs for public key lookup?

[Jason A. Donenfeld]

Howdy y'all,

I'm not sure if this is the right list for this sort of inquiry. If
not, scream at me and I'll go away. If I'm in the right place, read
onward.

Assume a client/server architecture over UDP. A client sends a
handshake message to the server. The server responds. They go back and
forth. After a few handshakes, they've established two ephemeral
symmetric keys for sending and receiving packets. The server has also
transmitted to the client an unsigned integer that indexes into the
server's array of currently valid symmetric keys. Processing works as
such:

Client message {
    u32 index;
    u8 ciphertext[len];
}

When the server receives it, it does something like:

if (msg->index > max_index)
   return FAILURE;
client_key = keys[msg->index];
AEAD_DECRYPT(msg->ciphertext, client_key);

This is basically what IPSec does with its "Security Parameter Index"
in the header.

So okay, that works well. Now let's play the same exercise for public
keys during an initial handshake, and things get a bit trickier.

Let's say the server has a list ahead of time of valid accepted client
pubkeys. If key = DH_POINT_MULTIPLY(client private key, server public
key, some_other_shared_param), the client sends the result of
AEAD("something", key).

The server then, upon receiving this message, does the following:

for (int i = 0; i < max_clients; ++i) {
   key = DH_POINT_MULTIPLY(server private key, clients[i].public_key,
clients[i].some_other_shared_param);
   if (AEAD_DECRYPT(ciphertext, key) == success)
         return clients[i];
}
return NULL;

In otherwords, it's forced to try every one. So we optimize. This
time, the client sends its public key along with the message. Now the
server can do this:

for (i = 0; i < max_clients; ++i) {
   if (memcmp(clients[i].public_key, msg.public_key)) continue;
   key = DH_POINT_MULTIPLY(server private key, clients[i].public_key,
clients[i].some_other_shared_param);
   if (AEAD_DECRYPT(ciphertext, key) == success)
         return clients[i];
   return NULL;
}
return NULL;

That's a little more efficient. But I don't like that memcmp in there.
So let's throw everything in a hash table instead. But actually, we
can optimize that even further: let's generate a function, mphf(key),
that maps public keys 0..n to integers 0..n, in any order, but
utilizing all the integers. This is called a minimal perfect hash
function. The idea is we compute the mphf function once, and then we
can simply do this for each incoming packet:

index = mphf(msg.public_key);
if (index == -1)
    return NULL;
client = clients[index];
key = DH_POINT_MULTIPLY(server private key, clients[i].public_key,
clients[i].some_other_shared_param);
if (AEAD_DECRYPT(ciphertext, key) == success)
    return client
return NULL;

So my question is: is anyone aware of this being done anyplace?
(Anyone have a nice standalone C implementation of an MPHF generator?)
Or is this sort of thing usually implemented with different tricks?

And then, further, is there a clever way of doing this that might
actually preserve identity hiding in the protocol (not featured
above)?

Thanks,
Jason