Which is the smallest, cyclic in 3 directions, consistent structure of random values which can be hidden at the adversaries machine? (some comparison)

Question

Or more general each member can be part of up to three 2D locally euclidean planes of 2 different dimensions each.

(each of those planes is cyclic in two orthogonal directions, like a torus)

Given just one member it could look like a node network:
(just one node with some neighborhood displayed here. Those neighbors have again neighbors not displayed here)
(left: 1 plane, right intersection of 2 planes)
intersection of 3 planes:

Despite that there need to be some deterministic way to map the neighborhood of a node to planar graphs at those three 2D euclidean planes (with constant node density). So adjacent node neighbors tend to be neighbors as well and have no $n$-neighborhood growth which needs e.g. hyperbolic space for representation.
Starting at one node $n$ and (mainly) following one direction of progression will lead to the same node again after (in best case) $C_n$ steps. So it's cyclic with cycle length $C_n$. In best case this is equal for all nodes in all directions. But to be less strict some variation is possible as long the cycle length is similar to nearby nodes.

The goal:
Finding such a structure which minimizes the cycle length $C$ (best $\le 2^{50}$) and the total node count $N$ (best case $N=C^3$ or $\le 2^{150}$) while keeping it as hard as possible to compute the relation in between two random nodes (best $\ge O(C^2)$ and $O(\sqrt[3]{N^2})$ or in numbers $\ge 2^{100}$)

---

Specialized to cryptographic methods:

As far as I know in cryptography there are only structures which are more specialized or partly more general than such a structure described above.
If e.g. the number of neighbors from one node is set to a fixed value of 6 we get a structure like this:
(left: intersection of 3 planes at a single node/number, right: every node/number has this structure here)

This can be achieved with 3 generators and a suitable $\bmod P$ as listed below.
For each kind I will add some reasons why it doesn't work out and (my) related threads for more details.

---

Comparison to tested cryptographic methods:

1. Three generators $q,r,s$ with $\bmod P = 2\cdot Q \cdot R \cdot S +1$ and $q^Q \equiv r^R \equiv s^S \equiv 1 \bmod P$ $\text{ } $[1]

   • $-$ $P$ need to be very big to avoid factorization $\gg 2^{150}$
   • $-$ with knowing the cycle sizes it can be reduced to a much easier problem with Pohlig–Hellman algorithm

2. Elliptic curves with 3 generators $F,G,H$ and with this values $i \cdot F + j \cdot G + k \cdot H$ [1] [2]

   • $-$ the cycle size for each direction is across the whole domain
   • $+$ only relatively small numbers needed
   • $-$ but still a domain/cycle size of $2^{200}$ needed (target cycle size only $2^{50}$)

3. AES or similar block cipher:

   • $-$ separated in multiple cycles with unknown size, only distribution is known [1]
   • $-$ one per direction? $\rightarrow $ domain of $2^{300}$ needed and can be reduces to a single dimension problem
   • $-$ concatenate 3 AES to a single member? $\rightarrow $ big $n$-neighborhood, similar to just using random values $\rightarrow $ a match at alternating AES128 (ECB-mode) can be found after $\approx {2^{64}}$ steps of progression [2]

4. 3 directional sequence $s_{ijk} = s_0^{\textstyle \beta^i\gamma^j\delta^k} \bmod (N=P\cdot Q)$ - hard to solve because $\phi(N)$ unkown

   • for $N=(2\cdot p +1)\cdot (2\cdot q +1)$ with gens. $\beta, \gamma, \delta$ primitive roots of $p,q$ [1]
     • $+$ $O(\sqrt[2]{C^3})$ (as far as I know)
     • $-$ but only if $\phi(N)$ is unknown. To reach $100$-bit security $N$ need to be around $2000$-bit size and with this $p, q$ and the cycle size also increases
   • for $N=(2\cdot p_s \cdot p_b +1)\cdot (2\cdot q_s \cdot q_b +1)$ projected to $\frac{(p_s-1)}{2}\cdot \frac{(q_s-1)}{2}$ with $\gcd(e,\phi(N)) \ne 1$ but $e$ hard to factorize [2], $\beta,\gamma,\delta$ related to power of $e$
     • $+$ $O(\sqrt[2]{C^3})$ (as far as I know) iff $C$ unknown
     • $-$ almost instant if cycle length $C$ is known (which is easy to derive for target values). $C$ would need to be $>2^{100}$

5. Geometry reflection over finite field (triangles [1], tetrahedron [2] - both no solution) or more general a chain of matrix multiplication. To let the $n$-neighborhood not growing too fast they need to be invariant over the order of their multiplication. So they can be reduced to $A^iB^jC^k$ - but so far I couldn't find any such matrices which also made $i,j,j$ hard to determine

   • $-$ either too many $n$-neighbors or too easy to compute the indices

---

Question: Can it be done better? Can less than $N=2^{200}$ values be distributed along 3 dimensions with a cycle size of less than $C=2^{65}$ each while finding the relation in between two members does take at least $2^{100}$ steps of computation (for most cases)?
For this it need to be harder than $O(\sqrt{N})$ (with $N<2^{200}$ and $C<2^{65}$)

---

Further notes:

• besides 3 directions in forward direction their inverse in backwards direction also need to exist. All should have about the same computation time. (edit: similar to fgrieu idea it would be sufficient if two directions (and their inverse) have same computation time. Changing which two directions are easy to compute can require more computation time)
• in best case all valid random values can generate the same structure. But a small ($<\approx 10$) set of disjoint similar structures (like in 4.) is also possible.
• in use case a random starting value will be generated and iteratively expended with its closest neighbors (after this the neighbors of neighbors and so on). They finally resulting (after (almost) endless time for generation) into the same consistent (secret) structure. It should be as hard as possible to prioritize any direction of progression to reach a certain target value faster. So generating just random points will not work out. The next values generated should always be close to those which have already been generated. That also means generating the $i-$th next value is not needed (as it usually can be done with generators), one step in one direction is sufficient (like in AES/block-cipher)
• no stretching function like only count every $n$-th member as valid (to increase security (higher member size $N$) with constant true member size $\frac{N}{n}$). This will already be used. It should - technically speaking - possible (if someone really want it) to generate a full cycle in one direction on a standard PC in a small number of CPU-years. With this the cycle size need to be smaller than $2^{60}$. But finding the relation in between any two target values should be infeasible in next 50 years. Finding it for some combinations is fine, it's even good to have. As far as I know about $2^{100}$ computations steps is a suitable boundary for this.
• a computation step means any kind of basic operation (+-*/^) applied at two values $<N$
• those structure members can be anything like numbers, vectors, strings, matrices, even ascii art pictures would work out. There only need to be some function to generate a pseudo-random value without leaking security related information. Generating multiple of them should not reveal any information about the relation in between them. So something like $g^r$ with a generator $g$ and $r$ the random value would not work out. Generating them don't need to be that fast, $<20$sec at a standard PC is sufficient.
• the adversaries will be equal to the normal user. He has access to all the source code, run time variables, keys, variables and so on. As the target cycle length $C$ is quite small we can also consider it known by the adversary.

---

Update: Related to fgrieu's comment:

We want an undirected connected graph of N nodes [?with a representation of a vertex n as a triplet of coordinates (are coordinates integers?)?]

Yes, but those coordinates have no global origin. If we want to find a path from $n_1$ to $n_2$ we start at $n_1$ and compute it's neighborhood. Those have coordinates related to $n_1$. E.g. $(0,1,0)$ could mean we started at $n_1$ and applied the progression for the 2nd dimension once.
The node offset in between $n_1$ and $n_2$ is symmetric and invariant for every $n_i$ we are starting from.
As they are cyclic in each dimension the offset can only be $+/-$ half the cycle size (in euclidean space) for each coordinate.
Integers aren't necessary. Real numbers also work as long computers can approximate them good enough to distinguish in between different nodes.
The net lies at a 3-Torus so we can interpret the offset also as angle difference.

To be clear just generating random coordinates does not work out. They always need to be close to those already generated. Only exception is the starting node. Those need to be generated by random. Given two such starting nodes (and all internal variables) there should be no hint about the best direction of progression.

There should be some procedure to move from one node to another along graph edges, which when iterated leads to cycle of length $C_n$ when starting from n

Starting at $n$ and (mainly) moving forward in one direction (and e.g. not that many times back again) we can reach $n$ again after $C_n$ steps. This need to be possible for at least 2 orthogonal directions and not more than 3 (forward and backward each).

Given two random vertices it should be hard to find a path between the two, requiring effort on the tune of $\Omega(\sqrt[3]{N^2})$

It also can be harder but I think this is not possible in normal cryptographic structures with fixed neighborhood. In general nets it could be harder. The main problem is finding something which is not reducible to a single dimension problem of size $C$ as the target value is too small for that. That also means $C$ is known to the adversary (as it can be quickly tested).
But if I'm not mixing up notation it should be $o(C^2+C)$ (for fixed neighborhood, line-plane intersection always possible) and $\Omega(\sqrt{N})$ and $\Omega(C^{1.5})$ (the mean number of steps) else $N,C$ need to be too big.

$C_n$ needs to be on the tune of $O(\sqrt[3]{N})$ [but is that an upper bound or a lower bound for Cn?].

Both. Not like as the shown method using EC where $N\approx C_n$ and not like the method using two AES where $C_n$ could be $1$.
There can be something like $O(\sqrt[3]{N}\cdot f(\log(N)))$. The main goal is to get a $\max(C_n) < 2^{65}$ (and $\min(C_n) \ge 2^{50}$ (else to easy afaik)) with $N<2^{200}$ and finding from random $n_1$ to $n_2$ should take (in most cases) at least $2^{100}$ steps of progression (but possible, up to $\approx 10$ subsets are Ok).

---

related JAAAY's comment:

euclidean locallity or hyberbolic planes

In other words the neighborhood growth can't be too fast.
With (a lot of free time) we could draw the neighborhood structure onto sheets of paper (=euclidean plane).
We can measure a (euclidean) distance in between nodes with our ruler. No matter of how many neighbors of neighbors we draw the mean distance in between nodes should stay (about) equal.
If we tape two opposite paper edges together we can simulate the cycle property for one direction. Considering this option the (min) distance in between two specific nodes is always equal - no matter were we started drawing this structure. (After drawing the full cycle in two direction we have to cut the paper to the proper size. At the border we continue the measure at the opposite border of the paper).

One node can only be on up to 3 sheets. If multiple numbers are on two different sheets (2-tori) they all lay on one line (1-torus) - like at the intersection of two 2-tori.

---

Update related to answer from fgrieu
For better overview here a slightly modified version of V2 (for similar cost progress in two directions): $$f(d_1,d_2,c) = \begin{cases}(d_1+1 \bmod \sqrt{s}, d_2,c)\\(d_1 , d_2+1\bmod \sqrt{s},c)\end{cases}$$ with $c\in [0,s^2)$ With connection $$D(t-1-E(d_1+d_2\cdot \sqrt{s}+c\cdot s)) = v$$ Valid connection if $v<s^3$ and decoded $(d_1',d_2',c')$ hold $(c \bmod 3) \ne (c' \bmod3)$

pros:

• cycle size $\sqrt{s}$ and total node count $s^3$ can be as small as desired
• easy to compute in 2 directions
• unique points
• well defined connections/wormlinks in between nodes

cons:

• big difference in between cycle size $\sqrt{s}$ and total plane count $s^2$
• path finding among a single plane is trivial
  • Given 2 random nodes they can quickly be tested if they are part of the same plane
  • Given 1 node of a plane all other nodes of this plane can be computed in $O(1)$
• intersection of two planes are just single points instead of a $1$-torus. Multiple intersections at one cycle conflict with requirements. To fix this we can use some kind of selection function among all $\sqrt{s}$ values (works due to $\sqrt{s}$ is quite small).
• progression function only has a chance to proceed which leads to much computation time not used for progression and is easy to parallelise for the adversary.
• while finding a connection every jump makes the whole plane as possible targets for the other side

With this a node can only have one connection. If we use 3 BC and compute: $$D_j(t-1-E_i(d_1+d_2\cdot \sqrt{s}+c\cdot s)) = v$$ The $i$'th BC is used if $c \bmod 3 = i$. Besides $v<s^3$ the decoded point $(d_1',d_2',c')$ also need to hold $(c' \bmod 3) = j$ if the $D_j$ decryption of the $j$-th BC has been used.
Afaik this should have no significant impact on security, or?

Afaik2 the security should be close to $O(s^{1.8})$ for all of those. More details about that can be found here.

---

Not optimal but better than all other tested so far. Ideas about making it harder to check if two random points are among the same plane, reducing the ratio between cycle size $\sqrt{s}$ and plane count $s^2$ or alternative approaches are (still) welcome.
Thanks again to fgrieu and all other reader.

Answer 1

Something half baked. Let $s$ be some integer, multiple of $3$, in the order of $2^{50}$. Let the set be triplets $(x,y,z)\in[0,s)^3$, with $N=s^3\approx2^{150}$ elements. Define $$f(x,y,z)=\begin{cases}(x+3\bmod s,y,z)&\text{ if }x+y+z\bmod3=0\\(x,y+3\bmod s,z)&\text{ if }x+y+z\bmod3=1\\(x,y,z+3\bmod s)&\text{ if }x+y+z\bmod3=2\\\end{cases}$$

Iterating $f$ from any starting point yields a cycle of $C_{(x,y,z)}=s/3$. There are $3s^2$ such so-far disjoint cycles, $s^2$ in each direction of the torus.

There remains to connect the cycles, thru rare "wormlinks".

---

V1: Define that point $(x,y,z)$ connects to point $(x',y',z')$ thru a wormlink iff

• $H(x+s\,y+s^2z)\equiv H(x'+s\,y'+s^2z')\pmod t$ for $H$ some wide hash (SHA-256 will do) and $t\gg s^3$ some parameter.
• and $(x,y,z)\ne(x',y',z')$ and $f(x,y,z)\ne(x',y',z')$ and $f(x',y',z')\ne(x,y,z)$ (that is the points are distinct and not connected thru a regular link)

We want $t$ large enough that with overwhelming probability the set is connected, but low enough that it's computationally difficult to navigate. The right ballpark might be $t\approx s^{3.8}$ or something on that tune.

---

V2: With a possibly keyed block cipher that allows to find where a point connects to (if it does). Make (per Format Preserving Encryption) a block cipher from $[0,t)$ to $[0,t)$ for even $t\gg2s^3$, with encryption $E$ and decryption $D$. Point $(x,y,z)$ connects to $(x',y',z')$ thru a wormlink iff

• $E(x+s\,y+s^2z)+E(x'+s\,y'+s^2z')=t-1$
• $f(x,y,z)\ne(x',y',z')$ and $f(x',y',z')\ne(x,y,z)$ (that is the points are not connected thru a regular link; having $t$ even ensures they are distinct).

To find the point connecting to $(x,y,z)$, compute $D(t-1-E(x+s\,y+s^2z))$, and if that's in $[0,t)$ decode that to $(x',y',z')$, and check $f(x,y,z)\ne(x',y',z')$ and $f(x',y',z')\ne(x,y,z)$.

The larger $t$, the least connected the set is. Again I'd try $t\approx s^{3.8}$ and refine from there.

It might be possible to tweak things so that every cycle demonstrably has a minimum number of wormlinks, allowing to make less wormlinks while keeping the set connected with overwhelming probability.