Looking for an algorithm which has a cyclic 'chain'-function which only allows the computation of next, previous element and in addition to that also a shift by a small amount of constants.

Example 1 which is close to:

Given a prime $P$ with prime root $g$, starting at a value $n_0 > 0 \mod P$
For each value at index $i$ there are formulas to compute the next and previous value:

$n_{i+1} = n_i \cdot g \mod P$
$n_{i-1} = n_i \cdot g^{-1} \mod P$

Also let $c$ be a constant. Every value can be shifted by $c$ indices.
$n_{i+c} = n_i \cdot g^c \mod P$
$n_{i-c} = n_i \cdot (g^c)^{-1} \mod P$

Other than in example this should only be possible for a small amount of constants compared to total amount of possible results.

Example 2 which is close to:

Common block cipher encryption algorithms have a function to compute the next value (plain text->cipher text) and previous (cipher text-> plain text). Those functions can be modified to a 'chain-function' where the new plain text is the current cipher text (and vice versa).

All block cipher encryption algorithms I know of can only compute next and previous value. Are there any which have some kind of shortcuts to skip ahead by a constant $c$?

Some more requirements

As in this example case the order of execution should not matter. If next value of previous is computed the result should be equal.

Computation time of next, previous and all possible constants need to be about equal. Computation time of a shift other than those values need to be multiple of that. E.g. if the shift is $42$ and $c=10$, so the shift $=4c+2$ the computation time need to be $6$ times that long ($>6$ or $42$ times that long also OK).

If next value gets computed over and over again the result need pass the starting value again. It need to be a cycle with $N$ elements. $N$ don't need to be a certain value but next to one.

Some more use case related requirements

For target use case optimal constant count would be two ($c,d$). For constant $c$ optimal and max value would be $c<=floor(\sqrt[3] N)$ and for constant $d<=floor(\sqrt[2] N)$. If those constants are smaller than the max/optimal value by a factor the product of those factors need be smaller than about 100,000 for any $N$.

There need to be a way to produce a (pseudo)-random starting value $n_0$ without the usage of other important values, e.g. it could be just a random value between $1$ and $N$. Given two such values it should be hard to compute one out of the other using the functions for next, previous, constant-shift. Close to brute force.

An attacker has access to source code and all run-time variables.

Alternative way

Instead of the capability of shifting each value by a constant it is also possible that only a fraction of possible values have this property. If that's the case there also need to be an efficient function which can evaluate if given value is such one.


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.