2
$\begingroup$

Or more general: given two valid random cipher $c_0, c_1$ a function $D$ with

$$D(c_0,c_1) = (a,b,c)$$

should exist but hard to compute (for most cases). The result $(a,b,c)$ represents the path from $c_0$ to $c_1$ underling an encryption $E$: $$E(x_0,y_0,z_0) = c_0$$ $$E(x_1,y_1,z_1) = c_1$$

In this case $$E(x_1,y_1,z_1) = E(x_0+a,y_0+b,z_0+c) = c_1$$

The computation time of $D$ should scale with the distances $d$ to each other $$d(c_0,c_1) = {|a|}^p+{|b|}^p+{|c|}^p]^{\frac{1}{p}} $$ with $p\ge 1$ (other distance measurements possible).

Or more general starting at $c_0$ it should be easy to find $c_1$ if $|a|,|b|,|c|$ are small and hard if they are big values. An additional function $D'$ for finding another valid cipher nearby is also possible.


Let's define the total number of different cipher as $N_c$

Some selection function of choice $S$ selects a subset of those ciphers. This subset need to have size of about: $$N_s \approx 2^{40}$$

Lets name the ciphers of this subset $s$

(This function $S$ receive a single cipher as input and will return true or false. It will take about the same short computation time for each cipher.)


All computation will be done with random cipher values and cipher values computed out of those. Function $E$ won't be part of the program because an attacker has access to all source code and runtime variables.


Use case:

  • every user starts at random valid cipher $s_r$
  • all user have the same set of ciphers (same $S$ as well) or only a small amount of different sets ($<20$)
  • every user want to find nearby $s_n$ of his $s_r$
  • but it should be hard to find the start cipher $s_r'$ of another user (both have interest in this and exchange information)
  • to avoid a center each dimension is cyclic
  • is a path known once it can be checked fast ($< 1$ min)
  • good: subsets of valid cipher $s_i$ share one but not more coordinates

Goal:

The mean computation time of finding $a,b,c$ for two random valid cipher $s_1,s_2$ should be at least $10^9$ or $\approx 2^{33}$ times slower than finding any near $s_n$ related to a given random $s_r$ (small $a,b,c$ for $D(s_r,s_n) = (a,b,c)$)

Finding $s_n$ for given $s_r$ should not take longer than 100h at current standard PC (at 1 CPU core thread).


Problems:

  • tested iterative encryption methodes have no known cycle size and only one dimension (e.g. AES)
  • tested index based encryption methods can be solved with baby-step giant-step algorithm (e.g. discrete logarithm)
  • key related encryption methods can't be used because source code and runtime variables are visible to the user
  • often the decryption problem can be reduced to one dimension
  • finding sweat spot in between to-hard-to-compute for all distant points but possible for near points

Some of these problems can be solved with a bigger bit-length but this will make finding nearby important points impossible.


Examples: (which dont work)

E.g. A elliptic curve for each dimension would need at least a bit length of 100 bit (suggested is 160+). That would result in about $N_c = 2^{300}$ ciphers (3D). With $N_s = 2^{40}$ points of interest that would require about $2^{259}$ operations to find another point of interest nearby a random cipher (way too long). The position of a random cipher (in this case $3$ points in a EC each) could be found in about $2^{50}$ steps.

Assuming there is a cryptographically algorithm similar to AES which can be applied to himself over and over again. But different to AES the cycle would contain all elements of chosen bit length. For about same security as the EC example above each dimension would need at least a bit length of $50$ bit. In 3D that would be $N_c = 2^{150}$ ciphers. Searching nearby point of interest would take about $2^{109}$ steps (way too long). Constructing one random cipher out of another would only take about $2^50$ steps.

To speed up some elements could be skipped. E.g. if only every $2^{30}$ element is a valid member of a cipher. With this only $2^{20}$ for each dim remain. In 3D that would be $2^{60}$ valid ciphers. Inside those valid ciphers it would only take about $2^{19}$ steps to find a nearby point of interest. Combined with the number of steps required to find the next member it would be a total cost of about $2^{49}$ steps. Much less than before but compared to a random point $2^{50}$ still very high.

Would it be better if more points get skipped? Given the small set of interesting points $2^{40}$ a cycle length of $2^{n}$ skipping $2^{b}$ points for next valid cipher member has some limitations:

$$\text{I. faster than finding random cipher: }(n-b)\cdot 3 -40-1+b < n $$ $$\text{II. enough points remain: }(n-b)\cdot 3 > 40+1$$ $$n-20 < b < n-13$$

In mean a total of $2^s$ steps needed to find a nearby interesting point: $$s = 3n-2b-41$$ In mean $2^d$ ciphers with valid members need to be computed to find an interesting point: $$d = s-b$$ And it will be $2^t$ times faster than finding another random interesting point ($2^{50}$ steps): $$t = -2n+2b+41$$

Given this it can only be about $2^{13}$ times faster with the downside every cipher is an interesting point. This will result in straight line placement (in example $b=36, n=50$). For next smaller $b$ every $2^3$ cipher would be such a point (example $b=35$). First adequate would be next value with every $2^6$ cipher is an interesting point (example $b=34$). Given this it would only be about $2^9$ faster than finding a random point. Which would be too less.

-> That means if there is an efficient way to reduce a cipher to its single dimensions it won't work unless there is a faster way to find a nearby point of interest


Do you know any other method which can solve this (goal)?

$\endgroup$

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.