Is there a way to use a one-way hash function for both sides to "ratchet" an asymmetric keypair?

Question

Is there any way to derive a series of asymmetric keys, such as using a one-way hashing function, where both sides can predict the next in the sequence?

Detailed Scenario:

Imagine a chat application where two people, Alice and Bob, are sending messages -- each with the agreement to delete any messages received 7 days after they are sent. And let's assume that some attacker is recording all of the encrypted communications between them. The goal is to prevent an attacker who compromises a phone from getting more than 7 days of messages, either from the phone, or using any copy of a key on the phone. Protecting against this requires both Alice and Bob to do two things:

1. Encrypt each message with a different key
2. Delete each message after 7 days
3. Also delete the key used to decrypt the message after 7 days

If they don't delete the key, then when the attacker compromises the phone, they can decrypt any previous messages from their historical record of the encrypted communications.

Partial Solution:

One way this could be done is for each side to publish a new asymmetric public key every day, with the promise that "any message encrypted to this public key (for me to decrypt with its corresponding private key) will be deleted, along with the private key used to decrypt it, on YYYY-MM-DD". So, each side would receive the updated key every day, and encrypt messages to that public key (or more likely, use that public key to encrypt and deliver an ephemeral symmetric key used for all messages in that 24 hour range). So long as both sides deleted their message after 7 days, and the recipient deleted their copy of the private key for that day (along with any ephemeral key), then forward secrecy would be maintained: compromising a device would only reveal at most 7 days of messages.

Problem:

The problem with that solution is it requires both sides to be in constant communication, in order to receive a daily key update from the other side. If Alice were to go offline for, say, a month, then Bob wouldn't know which of Alice's public keys to encrypt a new message with.

Solution / Question:

Which brings me to my question:

Is there any way to derive a series of asymmetric keys, such as using a one-way hashing function, where both sides can predict the next in the sequence?

This is easy with a symmetric key: if you have the key for N=1 in the sequence, both sides can apply the same hash function, and generate the key for N=2 in the sequence. I'm wondering if there is any equivalent for asymmetric keys, where:

• Alice applies a one-way hash function to Alice's private key for N=1, to generate a private key for N=2
• Bob applies a one-way hash function to Alice's public key for N=1, to generate a public key for N=2

If so, then both Alice and Bob could anticipate what key will be used for any future date by both "advancing" their side of the asymmetric keypair, even if they lose contact with the other side for extended periods of time.

Thanks!

PS: I'm aware there are other ways to solve this, such as by having each side publish a pool of "pre-keys" that are allocated out as necessary. I'm specifically asking about if there's any way to directly ratchet both the public and private key.

Answer 1

Is there any way to derive a series of asymmetric keys, such as using a one-way hashing function, where both sides can predict the next in the sequence?

Here is one way, based on elliptic curves (or finite field based on discrete logs); one such public key encryption method is the Integrated Encyption Scheme. Now, it does have the drawback that if the attacker learns a prior public key, he can then (with knowledge of the current private key), he can learn the prior private key. However, this limitation may still be acceptable to you.

In such a scheme, there is a private key (which is an integer $p$ in the range $[0, q)$), and the public key is a point $P = p \cdot G$ (where $\cdot$ is point multiplication if you're using elliptic curves, and exponentiation, more commonly written as $G^p$ if you're using a finite field group).

To ratchet the key forward, the two sides would compute:

• Private key: $p' = hash(P) \times p \bmod q$
• Public key: $P' = hash(P) \cdot P$

(where $hash$ is a cryptographic hash function).

This works, in that the relationship between the new public key $P'$ and new private key $p'$ still holds; $p' \cdot G = hash(P) \times p \cdot G = hash(P) \cdot P = P'$.

In addition, it is ratcheting; given $p'$, you cannot recover $p$ without knowing the hash of $P$ (and we assumed that he doesn't know that)