Score:3

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

at flag

Or more general each member can be part of up to three 2D locally euclidean planes of 2 different dimensions each.
[pic1]
(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)
enter image description here enter image description here intersection of 3 planes:
enter image description here


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)
intersection of 3 planes at a single node/number. Each generator is equal to one direction of progression. A plane is all possible values by using two generators other than at the more general structure above any number/node has the same structure here. So every number has 3*2 possibilities of progression with 3 generators and their inverses
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.
  • 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.
  • in target use case these members will serve as seeds for RNG's. The structure of those members as an arrangement for those seeds. Some random number sequences generated by those RNG's will be better than other. If single very good of them have been found it should be as hard as possible to connect them (= compute one out of the other).
  • 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.
  • some more tested techniques : cellular automaton (no inverse), tessellation (not deterministic or too easy to solve), homomorphic encryption (no overflow/cycle, not working if all at adversary PC ).

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.

J. Doe avatar
at flag
questions about details or what is meant, hints for better/shorter problem description or ideas which might work are also welcome
fgrieu avatar
ng flag
Tentative summary/request for clarification. We want an undirected connected graph of $N$ nodes [?with a representation of a vertex $n$ as a triplet of coordinates (are coordinates integers?)?]. 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})$. 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$. $C_n$ needs to be on the tune of $\mathcal O(\sqrt[3]N)$ [but is that an upper bound or a lower bound for $C_n$?].
JAAAY avatar
us flag
Answering to @fgrieu's comment will help a lot.
JAAAY avatar
us flag
Also, you seem to come from mathematical background, most people here I don't think will be able to understand euclidean locallity or hyberbolic planes terms you mention :/
J. Doe avatar
at flag
(did some update related to the comment)
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.