1. 9

  2. 13

    The construction allows to encrypt messages without key negotiation and in such a way that a later compromise of both client and server will not be enough to recover the message (if both server and client delete everything they are supposed to delete by the protocol and do not store the plaintext of the message, of course).

    A very very higlevel overview of the construction (note that I haven’t verified the details and definitely haven’t traced all the references/dependencies!):

    Hierarchical Key Encapsulation Mechanisms have been known for some time. The idea is that you have a tree, you have a key in each vertex and each key allows easy recreation of all its descendants — but having access to all the tree except the ancestors of some key doesn’t allow to recreate the key or attack the messages signed by this key. At the same time, there is a single public key that allows you to encrypt in a way that requires a key from a certain position in the tree to decrypt.

    Such a tree of keys allows you to build puncturable encryption. If you care about the nodes on some level, and you initially store the root key, you can lose exactly the ability to access a single key/node. To do that, you look at the path to the node, save all the sibling keys of vertices on this path, then forget the root key. Every node except the deleted one has the first position where it differs — the corresponding sibling will be saved. This puncturing construction is quite similar to what happens when you want to change a single leaf in a purely functional binary tree. If you need to remove more nodes, you again consider the path to the node to delete, save the recoverable siblings of the keys on this path, and remove nodes on the path if they were previously saved.

    Now each client basically picks a random node at a predetermined level and encrypts the message for this node. The server decrypts the message and then removes its ability to decrypt messages for the selected node.

    Each message requires the server to store a number of sibling keys proportional to the depth of the tree used, and failure risk is exponentially small in the depth parameter.

    1. 1

      I would only like to say thank you for your comprehensive and very grok-able summary (I felt more than a simple “upvote” was needed – apologies for noise!)