One way recurrence O(N)->O(1)

Imagine we have a random number generator where g(n+1) = f(g(n)), where f is some function (e.g linear recurrence).

I'm trying to find a system where it's fast to find many steps in the future immediately, whereas it's hard or impossible to work out a previous state.

for example, if I know state = X at time t, I would like to calculate state at t+n steps in the future, done in order O(1) rather than having to iterate n times.

I'm assuming state has an implicit modulo of around some power of 2 so it must be restrainted to a given number of bits at each time.

Does anyone know of a system that could provide this?
Many thanks.

• I think to calculate that in constant time you need periodicity, but periodicity also implies that you can calculate previous states as well, however a dynamic system can become periodic over time, so it's not true that you will get a correct previous result every time. – Pavel Oct 17 '15 at 20:46
• You want a cryptographic pseudo-random number generator with an additional gimmick. What research have you done in this direction? – Raphael Oct 18 '15 at 9:02
• Hi, I just answered my question (way below) a few minutes before you answered. – Zaphod1001 Oct 18 '15 at 9:04

There are two answers: one that solves your problem, and one that answers your question. I'll start with the first. One way to make sure that previous states cannot be backtracked from generated numbers is to mask the true state. Here's how it works. You take your $b$-bit number $x_t$ to be the true state at time $t$, but the number your RNG generates is $x_t \text{ mod } m$, where $m$ is much less than $2^b$. Then you can specify $g$ to be $x_{t+1} = a \cdot x_t \text{ mod } n$, with $a$ and $n$ large numbers that are relatively coprime.

This way, if you collect the numbers generated by this RNG, you need at least a couple of data points before you can make educated guesses about $x_t$, and even then it's not easy. The period of the RNG is $n$.

The answer to your question about whether there exist easy-to-compute functions that are hard to invert is an open question, known as the existence of one-way-functions. Existence is known to imply P $\not=$ NP, so it probably won't be resolved for some time. That's for functions that are easy to compute in one iteration; functions that allow an arbitrary amount of time steps to be computed is a question on a whole other level.

Of course, if you relax the question to mean a function whose inverse requires, say, $\Omega(b^2)$ time to invert, rather than superpolynomial time, there are options. For example, you could keep the function $x_{t+1}=a\cdot x_t \text{ mod }n$. To invert that function, you need to find the the multiplicative inverse of $a \text{ mod } n$. This takes $O(b^2)$ time. Then you will be able to compute $x_{t}$ given any $x_{t+1}$ in, again $O(b^2)$ time, as $x_t = x_{t+1} \cdot a^{-1} \text{ mod }n$.

This function is easy to compute for several steps, if you are willing to do some precomputation. Note that $x_{t+1} = a \cdot x_t$ and $x_{t+2} = a\cdot x_{t+1} = a^2 x_{t}$, so $x_{t+k} = a^{k} \cdot x_t$. Now you can precompute $a, a^2, \ldots, a^k$ up to some $k$, and from then on you will be able to compute $a_{t+j}, 1 \leq j \leq k$ efficiently.

• Thank you. I should note that the $x_{t+1} = a\cdot x_t \text{ mod } n$ function takes $O(b^2)$ time. Moreover, the inverse can be computed for any $x_t$ very quickly by computing the mult. inverse of $a$ (this is a mistake I have now corrected), so this function probably doesn't do much of what you want, unless you mask the state like I suggested, or in some other way. – Lieuwe Vinkhuijzen Oct 18 '15 at 11:17
• Nice to see you on SE Lieuwe, it's a small world :) (Orson from Leiden here.) – orlp Oct 18 '15 at 18:11
• You mention that, with your scheme, it's not possible to predict the state of the RNG given its outputs. Do you have any citation for that? Your are building a truncated linear congruential generator, and there are many attacks in the cryptographic literature on such things. I think the conventional wisdom among cryptographers would be that linear congruential generators are probably not a promising basis for a scheme that must resist attack. – D.W. Oct 24 '15 at 9:59

It's possible to construct a public/private keypair and an update function $f:S \to S$ with the properties that:

• computing $f$ takes $O(1)$ operations, given the public key;

• with the private key, you can compute $f^{n}$ (i.e., iterate $f$ $n$ times) in $O(\lg n)$ operations. In other words, anyone with the private key can compute the state at time $t+n$ from the state at time $t$ in $O(\lg n)$ operations -- not quite $O(1)$, but close.

• without knowing the private key, you cannot invert $f$ (you can't go backwards)

• with knowledge of the private key, it is possible to invert $f$ (to go backwards)

The primary drawback is that the private key allows both fast iteration and inversion. For some applications this might be OK; only you can tell whether it will work for you.

The function $f$ is just squaring modulo $N$, where $N$ is a RSA modulus ($N$ is the public key; the factorization of $N$ is the private key). See https://crypto.stackexchange.com/a/15141/351 for more details.

(A follow up to the accepted answer, to some degree...)

Using a hash function in this way is somewhat equivalent to fast forwarding a pseudorandom number generator.

A linear congruential generator (LCG) can be skipped ahead and back [link], in fact many PRNG's can be skipped/jumped ahead [link]. The problem with fast-forwarding any hash/PRNG is that if you know the cycle period (which you do with most PRNGs), you can effectively move back 1 state by fast-forwarding (period−1) steps.

Thus if we found a way to, say, move forward quickly with SHA-256, then the first person to correctly estimate its cycle period would also have the ability to move backward as well.

The only fix for this is to have a system with a huge number of varied cycles. E.g. having 256 bits worth of different cycles lengths, which each cycle being 64 to 256 bits in cycle length, fitting in 512 bits of state.

There is no known way of doing this, but should one be found, you've solved multiple comp-sci and cryptology problems, and made efficient signing of messages trivial.

tl;dr - if you can go forward and calculate its cycle length, you can go backward.

• 1. A linear congruential can be skipped ahead, but it's also trivial to go backwards: instead of multiplying by a constant $c$, you multiply by its multiplicative inverse $c^{-1}$ (the inverse modulo whatever your modulus is). For linear congruential generators, you can go backwards even if the period is not known. 2. I don't think it's true there is no known way of doing this, if by "this" you mean to have a system with a huge number of varied cycles. That said, having varied cycle lengths is not enough to allow "fast-forwarding". – D.W. Oct 24 '15 at 10:01