3
$\begingroup$

Is there an asymmetric cryptographically secure pseudo random number generator in which the public key only goes backward? For example, I'd like to generate 5,000 digits, then provide the public key and RNG state to another party. Then they'd generate the same digits backward from 5,000 to 1. The second party should not be able to calculate the digits from 5,001 onward.

Edit: Here's a working demo of DannyNiu's RSA approach.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ This might be an XY question. What's the problem you're trying to solve? $\endgroup$
    – forest
    Commented Jun 2, 2019 at 3:29
  • 1
    $\begingroup$ @forest Well I am envisioning a game where players unlock randomly generated content. A lot of it. It wouldn't be ideal to store the definitions for that content in a database because of storage limitations. Being able to give them a key and let them generate the content dynamically would bypass that problem. They can't go forward because they could cheat. $\endgroup$
    – skibulk
    Commented Jun 2, 2019 at 5:07
  • $\begingroup$ Note that, depending on your exact needs, you might be able to use a plain old iterated cryptographic hash function instead. Sure, you can only iterate those in one direction, but if you know you'll only ever need a limited number (say, less than a million) of pseudorandom numbers, you can just start at the end of the sequence and work backwards, generating each number by hashing the one the follows it in the sequence. And if you cached the value of, say, every 1000th number in a database, this might still be faster than using RSA. $\endgroup$
    – Ilmari Karonen
    Commented Jun 3, 2019 at 22:49
  • $\begingroup$ (Ps. A fancier caching scheme should let you generate $n$ hashes one at a time in reverse order using only $O(n \log n)$ time and $O(\log n)$ storage.) $\endgroup$
    – Ilmari Karonen
    Commented Jun 3, 2019 at 22:58
  • 1
    $\begingroup$ @skibulk: Yes, if I understood you correctly. Basically, choose $a_0$ at random and generate $a_1, \dots, a_n$ as e.g. $a_i = \text{SHA-256}(a_{i-1})$. Then, if you send $a_k$ to the user (for some $0 \le k \le n$), they can generate $a_k, \dots, a_n$ on their own, but they can't generate $a_j$ for any $j < k$ until you send them $a_{k'}$ for some $k' \le j$. The (optional) caching is just so you don't have to start the iteration over from $a_0$ again every time you want to reveal another (earlier) element of the sequence. $\endgroup$
    – Ilmari Karonen
    Commented Jun 4, 2019 at 8:18

1 Answer 1

Reset to default
2
$\begingroup$

Disclaimer: I've not verified the security of my proposal.

You can achieve that in two ways: one pre-quantum, using RSA-like scheme, another post-quantum, using multivariate system.

  1. The RSA version.

Generate an RSA key pair, keep the private key $(N,d)$ to yourself, give the public key $(N,e)$ to the second party.

To generating new numbers, calculate $x_{i+1} = x_i^d \pmod N$. This way, the second party can go backwards from known $x_i$ by calculating $x_{i-1} = x_i^e \pmod N$

  1. The multivariate version.

This version is significantly more heavy-weight than the RSA version. Although there are several multivariate signature schemes in the NIST PQC "Competition" (it seems difficult to build secure encryption scheme using MV), many of them uses exotic methods to compress the public key, which may be optional depending on your use-case.

In its simple form, you have a public multivariate system $P$ which is the composition of private components $S \circ F \circ T$ where $F$ is a easily solvable quadratic system, and $S$ and $T$ are linear.

To generate new random numbers,

  1. Calculate $u = S^{-1}(x_i)$

  2. Solve $u = F(v)$ and choose arbitrary $v$

  3. Calculate $x_{i+1} = T^{-1}(v)$

The second party can reverse it with $x_{i-1} = P(x_i)$

As mentioned by poncho in the comment, the solved $v$ may not be a unique solution, but that's not a problem because any generated $x_{i+1}$ satisfies $x_i = P(x_{i+1})$.

Edit

It seems you're not quite familiar with the notations.

In $x_{i\pm1}$, the $i\pm1$ is the subscript, so in terms familiar to programmers, it's x[i+1] or x[i-1].

$x_i$ is the current state of the PRNG. Since that is the output of some arithmetic operations, its bit pattern is not fully uniformly random (i.e. may fail some sophisticated statistic tests), so you may need to truncate it and/or hash it, to obtain some quality random bits - hashing is also done by the TLS protocol for the same reason.

And yes, it's an iterative generator, but I'm not sure what you mean by "algebraic", and why you believe it'd be inefficient in the second comment.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thanks DannyNiu. If I'm understanding correctly, the "±1" is not actually factored into the equation? It is just a label that indicates we're referring to the next or previous state X. What is the proper way to initialize the PRNG state? Will any number between 0 and the RSA Modulus work? I have posted a demo below, but it isn't working quite yet. $\endgroup$
    – skibulk
    Commented Jun 3, 2019 at 3:16
  • 1
    $\begingroup$ One problem with multivariate schemes is that they don't actually implement bijections; instead, in the public direction, there will be multiple preimages that map to the same postimage (and hence in the private direction, a possible preimage will often have multiple possible postimages). That may make you CSPRNG problematic to make it work in the backwards direction, even with the private key $\endgroup$
    – poncho
    Commented Jun 3, 2019 at 3:18
  • 1
    $\begingroup$ @skibulk Yes, it's just a label. And any number between 2 and the RSA modulus will work, 0 and 1 will not make your PRNG advance. $\endgroup$
    – DannyNiu
    Commented Jun 3, 2019 at 3:24
  • $\begingroup$ @DannyNiu: my understanding of the problem was that, when going backwards, you recover the previous states, not just a set of plausible ones... $\endgroup$
    – poncho
    Commented Jun 3, 2019 at 11:53
  • 2
    $\begingroup$ Oh, I misunderstood your construction; however, the fundamental issue still remains (just in the opposite direction of what I original thought); $F$ isn't a permutation, and so what do you do if $F^{-1}(u)$ doesn't exist? $\endgroup$
    – poncho
    Commented Jun 3, 2019 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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