Most block ciphers encrypt a plaintext deterministically into a ciphertext which allows decryption in the opposite direction. Now, instead of encrypting just one plaintext, I'm looking for a cyclic 'chain-function' which starts at a random value and always allows computation of the previous and next element. In addition to that, it needs to be associative with another such function, so the order of execution has no impact on the result.
An example which is close to what I am looking for:
(Note: It's not a normal block cipher since it has other properties.)
If we have e.g. a prime $P$ and two prime roots $g,h$ as generators. We can generate a set of numbers with:
$n_{i+1,j} = n_{i,j} \cdot g \mod P$
$n_{i,j+1} = n_{i,j} \cdot h \mod P$
We can start with a random number $n_{0,0}> 0 \mod P$.
This set is cyclic in $i$ and $j$.
For every generators $g,h$ we can find the inverse elements $g^{-1}, h^{-1}$ which allows to compute:
$n_{i-1,j} = n_{i,j} \cdot g^{-1} \mod P$
$n_{i,j-1} = n_{i,j} \cdot h^{-1} \mod P$
So given an element ($x$) we can also compute the next and previous element in direction $i$ and $j$. Let's call those functions $f_{i+1},f_{i-1},f_{j+1},f_{j-1}$
For the example above that would be e.g.:
$f_{i+1}(x) = x \cdot g \mod P$
In this example case the order of execution does not matter, those functions are associative to each other, so e.g.:
$f_{j+1}(f_{i-1}(x))=f_{i-1}(f_{j+1}(x))$
So far so good, but in contrast to normal block cipher function this example case also has a shortcut to compute the element $n_{i,j}$ with:
$n_{i,j} =n_{0,0} \cdot g^i h^j \mod P$
Which should not be so for the use case.
Looking for:
I'm looking for a cryptographic function (or set of) which allows me to compute $f_{i+1},f_{i-1},f_{j+1},f_{j-1}$ of a given value, but without an efficient way to compute the $i$'th or $j$'th value like the example above.
To get e.g. the $i$'th value we should need to compute the $i-1$ values before (or more general $\mathcal{O}(i)$ times normal computation time ).
Block cipher encryption functions deliver this for one direction. But do there exist any for multiple directions or multiple functions which are associative to each other?
For the sake of simplicity, the example case only had 2 directions ($i,j$). Target use case has 3 ($i,j,k$).
Some more requirements:
Those functions $f_{d+1}$,$f_{d-1}, d \in\{i,j,k\}$ also need to be deterministic, so they need to hold for any value $x$ in the chain:
$f_{d+1}(f_{d-1}(x)) = f_{d-1}(f_{d+1}(x)) = x$
The time for computation being about same:
$\mathcal{O}(f_{d+1}) \equiv \mathcal{O}(f_{d-1})$
Also, same in each direction ($e \in\{i,j,k\}$):
$\mathcal{O}(f_{d+1}) \equiv \mathcal{O}(f_{e+1})$
Moreover, the cycle size in each direction ($s_i,s_j,s_k$) should somehow be manageable. I'm looking for a certain target size (related to computation speed, size $>=2^{16}, <\approx 2^{64}$ each). Their sizes don't need to be equal, but at least very close to one another.
Given two elements it should be hard to produce the second element starting from the first by applying the functions $f_{d+/-1}$ on it. The only way should be to brute force and compute one element until the other is found. That should be also true if those two given values are each initial values. Due to small cycle size, security needs to scale with $\mathcal{O}(s_i \cdot s_j \cdot s_k)$ and not just $\mathcal{O}(\max(s_i,s_j,s_k))$, as it does in the example above.
There needs to be a way to produce a (pseudo) random initial value $n_{0,0,0}$ which is independent of those functions $f_{d+/-1}$. E.g. just a random number in the given region. The number of possible random values needs to be at least $\approx 2^{32}$ or more (which would be better). For two different initial values all values which can be produced with $f_{d+/-1}$ need to be (locally) equal or different (to some degree). In total, all possible initial values need to map to less than 100,000 different arrangements of variables. If there is more than $1$ set (which is OK as well) it should be hard to figure out if one initial value produces the same set as another.
User/attacker has access to the source code and all runtime variables.
