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)
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&gt;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)&lt;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&gt;=p)
      x -= p;
  }
  while( x&gt;=2*N || x&lt;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.