Is there a method to encrypt relations in between values of a cyclic value set and generate values out of this set with pseudo RNG? (all at user PC)

Question

Is there a pseudo RNG and function $f$ with
1.) The RNG produces a value $v_0$ out of $N$ different values (set $S$).
2.) Independent of the RNG the function $f$ generates $v_{i+1}=f(v_i)$

Requirements:
$\bullet$ $v_{i+N} = v_i$
$\bullet$ $\forall i$: $\{v_{i+k}, 1\le k \le N\} = S$
$\bullet$ $v_{i+j} = f^j(v_i)$ so it needs $O(N)$ computations (hard to compute)

All this is computed at the users PC. He has access to all variables. Given two random values genereated by the RNG the user should not know how to compute the second out of the first (= how often $f$ need to be applied).

Question: Is there any cryptographic method which has such conditions?

---

Further notes:
(*..) ... in further text means an optional simplificaion

$\bullet$ each $v_0$ is part of the same cycle (*or part of one out of a max of 10 cycles of equal size (+/-5%))

$\bullet$ There should exit no faster way to compute $v_{i+j}$ out of $v_{i}$ except in $j$ $(\mod n)$ steps (or $N-j$ steps) (*linear speed up of less than 5 times is ok)
$\bullet$ (*The result set of function $f$ can be larger than those $N$ values (up to ~1000 times)(and with this the cycle size) but there need to exists an efficient function to prove if it is one of those $N$ values.)

$\bullet$ There need to be an efficient way to (pseudo) randomly generate values $v_0$ (*not all values in $S$ need to be generated by the RNG but at least $N^{2/3}$)
$\bullet$ (*The RNG dont need to be uniform distributed among those $N$ values (but it can). It's fine if no probability of one value is much higher than 1000 times than any of a subset containing 80% of all values.)

---

Examples

$\bullet$Using unknown methods:
A random cyclic permutation (with cycle size N) with function $f$ which generates the next value in that cycle and the RNG could be a random number between 1 and $N$.

$\bullet$Too easy to compute:
The discrete logarithm in $\mathbb{Z}/N\mathbb{Z}$ with prime $N$ and a primitive root $g$ as generator with $f(v)=v⋅g$. The RNG would just give a random value between $1$ and $N−1$. If now the user gets two such random values he does not know how to compute one out of the other (how often multiply with $g$) even if he knows all internal variables. But it can be solved in about $O(\sqrt{N})$ steps. For small numbers that would be too fast to compute. I'm looking for something similar but with $O(N)$ (or bigger).

---

Example use case:
_

_

The green square is value $v_0$ generated by the RNG.
A-F are members of set $S$.
The relation from one value to the next is equal in each picture (modulo 9).
E.g. to get from value D to E it is always 1 square to the right and 1 below.
If now $N=80$ and $f$ delivers the next value in the cyclic permutation (with size N) the following blue square can be generated like:
with $v_{i+1} = f(v_i)$ then shift horizontal $= v_{i+1} \mod 9$ and vertically $= \operatorname{roundDown}(v_{i+1}/9)$

This can lead to multiple values at same position but values which are close in cycle also share almost equal other values. Values at the other end of the cycle still share more than half of the values. This property is not needed, equal values all the time would be better.

If now given only two random values e.g. D and G it should be as hard as possible to derive the position of G starting at D.

The grid will be 3D and about 100k x 100k x 100k tiles. Neeed about $10^{12}$ unique values. Only need to be safe for standard PC (>10.000 hour compute time, not supercomputer, grid, hardware)

Besides the 'next' function $f$ also the inverse can exists. Except just a single function also a function for each dimension can exists. If that's the case only the adjacent square gets computed. It need to be independent of the order of function execution and there should exist no (easy) way to reduce a given value to its dimension values. Else finding the way between two random values would be too easy.

Answer 1

If evaluating $f$ uses computer time $t$, a brute force attack takes on average time $Nt/2$. To have this larger than $T=36\cdot10^6$ seconds, with $N\approx10^{12}$, we need $t>72\cdot10^{-6}$, that is some hundred thousands CPU instructions. Artificialy slowing down the implementation of $f$ in the program won't help. $f$ must be inherently slow so that it is slow for the attacker; and controllably slow so that we can tune the compromize between security and speed of the user program.

The example application suggests that $S$ is a haphazard subset of a larger set with $M\approx10^{15}$ elements. We'll take it as $[0,M)$, with $M\ge2N$.

I aim only at a reduced version of the security requirement: Given two random values produced by the RNG, a guess of the number of steps of $f$ to go from one to the other, if made with much less than $T$ seconds of compute time, has low probability to be exact. Towards that:

• Choose an integer parameter $\alpha$ (a larger one will slow $f$). Find a prime $p\approx\alpha N$ with $q=(p-1)/2$ prime ($p$ is a safe prime and $q$ a Sophie Germain prime), and also $2^q\bmod p=p-1$ (and perhaps $\log_2p$ unremarkably close to a simple fraction).
• Define the function $b$ on the set $[1,p)$ as $x\mapsto b(x)=2x\bmod p$. The function $b$ is a cyclic permutation of $[1,p)$.
• Define the function $c$ on the set $[N,2N)$ that iteratively applies $b$ (at least once) until the result is in $[N,2N)$, and returns this result. The function $c$ is a cyclic permutation of $[N,2N)$. See note for implementation.
• Build a permutation $g$ of $[0,M)$ using a standard Format-Preserving Encryption technique. $S$ is the set of integers $v$ in $[0,M)$ with $N\le g^{-1}(v)<2N$.
• Define the RNG as drawing $u$ uniformly at random in $[N,2N)$ and returning $g(u)$.
• Define function $f$ over the set $S$ as $f(v)=g(c(g^{-1}(v)))$. It cycles over the $N$ elements of $S$ in exactly $N$ steps.

Given random $v$, $v’$ produced by the RNG, it is possible to estimate how many steps of $f$ are necessary to go from $v$ to $v’$: we compute $u=g^{-1}(v)$ and $u’=g^{-1}(v’)$, then $y=u^{-1}\,u’\bmod p$, then solve for $x$ the Discrete Logarithm Problem $2^x\bmod p=y$ (this remains easy, given the order of magnitude of $N$ and $\alpha$). A reasonable guess of how many steps of $f$ are necessary to go from $v$ to $v’$ is $x\,N/p$ rounded to the nearest integer. However that estimate has low probability to be exact for moderate $alpha$ (much less than $N$), and I have some hope that markedly improving it has some sizable cost.

Note: there are time/memory trade-offs possible for evaluation of $c$ faster than the trivial:

uint64_t c(uint64_t x) {
  do {
    x += x;
    if (x>=p)
      x -= p;
  }
  while( x>=2*N || x<N );
return x;
}

and the program should use these, in order to increase $\alpha$ inasmuch as functionally tolerable, maximizing the cost of a brute force attack.