Reveal all information up to n-th message

Is there a way to generate a sequence of keys that have the property that exposing any of those keys will reveal all previous keys, but no future key?

I'm thinking about an application that sends an encrypted message every day, and sometimes I want to disclose to some other party the content of all past messages at any point in time, but without revealing any future message.

A possible way would be to hash some data x times, and than use the final hash for the first message, the x-1th hash as key for the second message, x-2th hash as key for the second message and so on. Revealing to any party the x-n key allows them to just hash it many times to obtain all the keys between x and x-n with no access to any later keys. But that limits the application in the total number of messages and requires a lot of work to be done beforehand. Maybe there is a much better way?

• Encrypt the old key under the new key and publish the ciphertext (for every key update) and the newest key you want to leak? May 22, 2018 at 20:00

Is there a way to generate a sequence of keys that have the property that exposing any of those keys will reveal all previous keys, but no future key?

One possibility: select a hard to factor value $n = pq$; publish the value $n$ (or include it with each day's "key"), and keep the factorization secret. It'll make things easier if you select $p \equiv q \equiv 3 \pmod 4$

Then, select a random quadratic residue $r_0$ (which you can do by selecting a random value $t$ and computing $r_0 = t^2 \bmod n$)

Then, for each day's secret $r_i$, you can compute the next day's secret $r_{i+1} = \sqrt{r_i} \bmod n$ (that is, a modular square root); there are four such square roots; you'll want the one which is a quadratic residue.

That's actually easier than it sounds; if you took my advice about about $p \equiv q \equiv 3 \pmod 4$, then all you need to do is compute:

$$r_{i+1} \mod p = r_i^{(p+1)/4} \mod p$$

$$r_{i+1} \mod q = r_i^{(q+1)/4} \mod q$$

And combine $r_{i+1} \mod p$ and $r_{i+1} \mod q$ using CRT to reconstruct $r_{i+1}$

• Computing next keys is as difficult as factoring $n$
• Computing previous keys is easy, as $r_{i-1} = r_i^2 \bmod n$