2
$\begingroup$

Let $X$ be a sequence element list of (pseudo) random values generated by a RNG and $x_i \in X$ a member of it. The period length is $k = |X|$ and it is a cyclic generator. For $i>k$ the value $x_i = x_{((i-1) \mod k)+1}$ (the list of random value outputs repeats again after $k$ values)

Now is there any such RNG with a sum of zero (of selected elements) :

$$0 =\sum_{j=1}^k \delta(x_j)\cdot g(x_j)$$

with $$e_m =\sum_{j=1}^m \delta(x_j)\cdot g(x_j)$$ $$s =\sum_{j=1}^k \delta(x_j)\cdot x_j$$ $$c =\sum_{j=1}^k \delta(x_j)$$

using $\delta()$ as a selection function (selects by value). $$\delta(x_j) =\begin{cases} 1 &\quad\text{if $x_j$ should be part of the sum} \\ 0 &\quad\text{else} \\ \end{cases}$$ $\delta\ could be e.g. only values which are less than a number or end with a 7 or have integer root or...what ever you like (but not index related)

an $g()$ as a modifier function to accomplish a sum of 0. That could be e.g.: $$g_1(x) = x \mod P$$ $$g_2(x) = x -s/c$$


Target values and restrictions:
+Amount of unneeded computations should be small: $$k/c < 10$$ +Number of unique values of partial sum should be as many as possible $$|\{e_m, 0 < m <= k\}|=u$$ $$u/c > 0.6$$ +Computation time of $\delta, g$ should not increase during run time +able to scale
+there should exists no efficient way to compute $x_i$ or $g_i$ for given $i$ (except $i=k$ or $i=v+k$ for known $x_v$) or index $i$ for given value $w=x_i$ (source code and runtime variables are known by the attacker, some linear speedup of $<10$ times is allowed)
+The RNG need to be started at different seeds but still generating all elements in $X$ in the same order. Some seeds may generate a different $X'$ with different values and/or order. Not more than 4 of those $X$ is allowed.
+There need to be a way to randomly pick a seed for the RNG
+Number of possible seeds $>=c/2$ +random value type can be integer, real, complex, vector, .... anything your like but it need to be representable in binary format


Outro & Example
With formulas above I tried to generalize the question.
A valid solution would also be a RNG which produces a permutation of all values between $1$ and $N$.
For Example $N=2^8-1=255$. The sum of those would be $N \cdot (N+1)/2$. To accomplish a zero sum
$\delta(x)$ could just be $1$ all the time and $g(x) = x \mod (P=2^7)$
If now for some reason the RNG produces all values from $1$ to $300$
$\delta(x)$ could only be $1$ for $x$ with a highest leading bit of $0$. With this it only sum up values from $0$ to $255$ again.

$\endgroup$
  • $\begingroup$ I don't understand the selection function what does "if $x_i$ is a part of the sum" mean? Which sum? Do you want to find a subset $J$ of the index set $\{1,\ldots,k\}$ where $\delta(x_i)=1$ if and only if $i \in J$? And what is the set $X$? Subset of reals? Integers? $\endgroup$ – kodlu Nov 27 '19 at 3:10
  • $\begingroup$ @kodlu Given a pseudo random number generator with a seed then $X$ is a list of all random numbers the RNG generates until it generates the same sequence of length $k$ again. The first number of such a RNG generates would be $x_1$, the 2nd $x_2$ and so on ($X = [x_1,x_2,x_3, ... ,x_k]$). The random values can be integer,real,complex numbers, vectors,..whatever you like but it need to be computed at a common PC so values need to be stored in binary system of limited length. $\endgroup$ – J. Doe Nov 27 '19 at 13:36
  • $\begingroup$ @kodlu The sum of all selected values should be zero:$0 =\sum_{j=1}^k \delta(x_j)\cdot g(x_j)$. The selection function$\delta$ is not by index. It is by value. E.g. only sum up values which are less than a number or end with a 7 or have integer root or... whatever you like. The selected values are a subset of $S=\{X\}$ with size$|S| <= k$, with $\{X\}$ all unique values of list$X$. If the modifier function $g()$ is applied to all selected values ($\forall x_j \in X \land \in S_{selected}$, with $S_{selected} = \{\forall s_i \in S, \text{with} \delta(s_i)=1\}$) the sum of those should be zero. $\endgroup$ – J. Doe Nov 27 '19 at 13:48
  • $\begingroup$ @fgrieu explicit form can be generalize to 'there should be no faster way known to compute the $i$'th element than iterate to it '. Linear speedups $<10$ times are ok. As far as I know it need to be bound to $x_{i+1} = f(x_i) $ . Other internal states or values are possible but they won't be hidden. Users have interest to find index $i$ themself and share all internal variables. Use case: Two users which start at different seed should not know the index of a value generated by the other users RNG. (the index for their own RNG to generate the other users value (at know index of their RNG)) $\endgroup$ – J. Doe Nov 27 '19 at 14:13
  • $\begingroup$ You should edit the question and include these details. $\endgroup$ – kodlu Nov 27 '19 at 20:53

Your Answer

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

Browse other questions tagged or ask your own question.