0
$\begingroup$

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:
enter image description here _ enter image description here

enter image description here _ enter image description here

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.

$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ J. Doe : I fixed a $N$ into $p$. A $p$ can be found: about half of primes $p$ such that $q=(p-1)/2$ prime (such $p$ are called safe primes) are such that $2^q\bmod p=p-1$; square and you get $2^{2q}\bmod p=1$ per Fermat's little theorem. We must iterate modulo $p\gg N$ many times for one step of $f$ because otherwise $f$ is going to be too fast. $\endgroup$ – fgrieu Dec 23 '19 at 14:44
  • $\begingroup$ @ fgrieu: with $\mod p$ and $=p-1$ it make sense now. Before marking it as solution I will do some more thinking about the estimate and its impact in security. It would be too nice if all works that nice. There need to be some problem somewhere. $\endgroup$ – J. Doe Dec 23 '19 at 22:06
  • $\begingroup$ I did some testing. As expected the mean step size is about $P/N$, the smallest value $log_2( (P-N)/N)$. Not sure about the theoretical largest possible value. In tests so far it was about 10 times larger than the mean (rare case, below <5 times more common). $\endgroup$ – J. Doe Dec 28 '19 at 23:41
  • $\begingroup$ @ fgrieu: not all primes work. E.g. $p_1 = 2000303$. It is a safe primes but with $p_1$ not all values between $N$ and $2N$ are part of the cycle. So unless some very rare (any exists?) exceptions $2$ need to be primitive root of $p$ as well. Trivial but I forgot it during searching some safe primes. $\endgroup$ – J. Doe Dec 28 '19 at 23:42
  • $\begingroup$ About security: As far as I understood the permutation $g$ has no direct input in security because the true value $v$ is always known. It's just to shift values to target range. Given values $v, v'$ it is hard to compute the exact amount of steps from one to the other. However the estimate function described above is quite easy. In target app even knowing it is probably in 5% range of the total cycle length (or not) has some high benefit of knowing it. So it's not the optimal solution but the best I got so far and its also an answer to the question. ty for those ideas again. $\endgroup$ – J. Doe Dec 28 '19 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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