patternMinor
One way recurrence O(N)->O(1)
Viewed 0 times
onewayrecurrence
Problem
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'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.
Solution
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.
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.
Context
StackExchange Computer Science Q#48352, answer score: 7
Revisions (0)
No revisions yet.