Out of $N = s^3$ total points we pick a starting point $p$ and an end point $q$
with
$$p=(p_1, p_2)$$
$$q=(q_1,q_2)$$
$$p_1,q_1 \in [0,s)$$
$$p_2,q_2 \in [0,s^2)$$
We want to find a path in between them.
For doing so we have two kinds of progression:
- A trivial one by just walking forward: $$f((e_1,e_2)) = ((e_1+1 \bmod s),e_2)$$
- And an advanced one by jumping from one point $(e_1,e_2)$ to another $(e'_1,e'_2)$.
This connection is encrypted ( $E$ ) with a symmetric, format preserving block cipher (similar to AES but with bigger block size) with domain $[0,t-1]$ with $t = s^{3+a}$ with $0>a<1$ (*) ($t$ is related to the block size in most cases. For AES $t$ would be $2^{128}$)
They are connected if: $$E(e_1+e_2\cdot s) + E(e'_1+e'_2\cdot s) = t-1$$ Given a random point $(r_1,r_2)$ we can use the decryption ( $D$ ) to find it's connection with: $$D(t-1-E(r_1+r_2\cdot s)) = v \in [0,t-1]$$ Iff $v<s^3$ it's a valid connection and we can decode it to the related point $(r'_1,r'_2)$
This has a property of $\frac{\textstyle s^3}{\textstyle s^{3+a}} = s^{-a}$. So in mean it will take $s^a$ forward steps to find a valid connection. As we can only take $s-1$ steps forward $a$ has a more limited upper bound than in (*) to avoid dead ends. $a \approx 0.8$ seems to be good choice for target $s$-size.
To find a connection in between points $p$ and $q$ we 'just' need to start exploring from both sides and jump to points $ {p^i}',{q^j}'$ with equal second value ${p_2^i}' ={q_2^j}'$. Similar to Giant-Step this should take in mean $\approx \sqrt{s^2} = s$ jumps. (Update edit) According to this a more accurate value is $\sqrt{\pi}\cdot s$ total jumps.
Combined with the mean number of trials to find a valid jump location ( $s^a$ ) an adversary would need to calculate in mean $\approx s^a\cdot \sqrt{\pi} \cdot s = \sqrt{\pi} \cdot s^{1+a}$ block cipher (encryption and decryption). This is much smaller than the normal effort for breaking a $t=s^{3+a}$-Bit Block-Cipher.
(we assume a suitable $a$ has been chosen without any dead ends and the adversary has access to all run time variables including the block cipher keys)
Q1 Is this approximation for the number of block cipher calculations correct? Can it done faster?
Q2 As single bit have big impact for block cipher security is there a more accurate calculation for the mean count of block cipher encryption required to find a connection in between $p$ and $q$?
Q3 On https://www.keylength.com/en/1/ there is some overview about the security of different values. Would this kind of encryption described here similar to a $\log_2(\sqrt{\pi}s^{1+a})$-bit keylength symmetric block cipher encryption? If not what else?
The main Question would be if a 192-bit block size is good enough for this. According to the approximation above (and $a=0.8$) it would take in mean $\approx 2^{92}$ block cipher calculations to break it. If this is equal to a 92-symmetric block cipher this would not be considered as secure anymore in near future $\approx$ year $2030$ (according to the link above). $\rightarrow $Update: AES-192 won't work out. It only supports a block size of 128 bits. Changed it to a block cipher similar to AES but with a block size of 192. E.g. Rijndael (or is there any more common?)
($a$ can be tweaked but this will not gain much more than a factor of $\approx 16$ else chance for dead ends gets too high)
Main Q2: Can we introduce multiple (3) different Block Cipher without big impact on security?
(could als be part of a new thread)
Instead of a single advanced way of progression we can now jump from one point to up to two different points. Given a point $(e_1,e_2)$ the kind of progression depends if $e_2 \bmod 3$ is $0,1$ or $2$.
$$[i]_3 \rightarrow [j]_3: D_j(t-1 - E_i(e_1+e_2\cdot s)) \text{ with } i,j\in{0,1,2}$$
$E_k,D_k$ means we encrypt, decrypt with the $k$-th Block-Cipher. To use $E_i$ the value $e_2$ need to hold $e_2 \bmod 3= i$. After using decryption $D_j$ the resulting value not only need to be $<s^3$ the resulting point $(e_1','e_2')$ also need to hold $e_2' \bmod 3 = j$.
This reduces the chances for a single connection but also increases chances for any connection.
MQ2 Does this have any significant impact on security?
This path encryption is related to a slightly modified/simplified version of an answer in here. I would like to be more certain about the security of this.
