2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Encrypt the old key under the new key and publish the ciphertext (for every key update) and the newest key you want to leak? $\endgroup$
    – SEJPM
    May 22 '18 at 20:00
4
$\begingroup$

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}$

This addresses your problem, as:

  • Computing next keys is as difficult as factoring $n$

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

  • You can compute next keys as long as you want

$\endgroup$
2
  • 1
    $\begingroup$ Is there a name for such a scheme? $\endgroup$
    – blues
    May 23 '18 at 4:41
  • $\begingroup$ @blues: I don't know of a specific name, no. $\endgroup$
    – poncho
    May 23 '18 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.