An open invitation to evaluate endomorphic Laver table based cryptosystems-Part II

In this post, I will give an analysis of the Ko-Lee key exchange for the functionally endomorphic Laver tables (the Ko-Lee key exchange for functional endomorphic Laver tables is simpler to analyze than the distributive version of the Anshel-Anshel-Goldfeld key exchange). In the next post, I will simply link a JavaScript program here on this site which will allow one to analyze the Ko-Lee key exchange for functional endomorphic Laver tables. We will leave an analysis of the more complex but probably more secure distributive version of the Anshel-Anshel-Goldfeld key exchange for functional endomorphic Laver tables for a later post (we believe that the distributive Anshel-Anshel-Goldfeld key exchange would be more secure for the functional endomorphic Laver tables).

Critical points

Suppose that $(X,*)$ is a Laver-like algebra. Then if $x,y\in X$, then define $\mathrm{crit}(x)\leq\mathrm{crit}(y)$ if $x^{n}*y\in\mathrm{Li}(X)$ for some $n$. We say that $\mathrm{crit}(x)=\mathrm{crit}(y)$ if $\mathrm{crit}(x)\leq\mathrm{crit}(y)$ and $\mathrm{crit}(y)\leq\mathrm{crit}(x)$. We shall call $\mathrm{crit}(x)$ the critical point of the element $x$. Let $\mathrm{crit}[X]=\{\mathrm{crit}(x)|x\in X\}$. Then $\mathrm{crit}[X]$ is a linearly ordered set.

If $\alpha\in\mathrm{crit}[X]$, then there is some $r\in X$ with $\mathrm{crit}(r)=\alpha$ and $r*r\in\mathrm{Li}(X)$. Suppose now that $\alpha\in\mathrm{crit}[X],\mathrm{crit}(r)=\alpha,r*r=\mathrm{Li}(X)$. Then define a congruence $\equiv^{\alpha}$ on $X$ by letting $x\equiv^{\alpha}y$ if and only if $r*x=r*y$. Then the congruence $\equiv^{\alpha}$ does not depend on the choice of $\alpha$. The congruence $\equiv^{\alpha}$ is the smallest congruence on $X$ such that if $\mathrm{crit}(x)\geq\alpha$, then $y\in\mathrm{Li}(X)$ for some $y$ with $y\equiv^{\alpha}x$. If $x\in X$, then define the mapping $x^{\sharp}:\mathrm{crit}[X]\rightarrow\mathrm{crit}[X]$ by letting $x^{\sharp}(\mathrm{crit}(y))=\mathrm{crit}(x*y)$. The mapping $x^{\sharp}$ is monotone; if $\alpha\leq\beta$, then $x^{\sharp}(\alpha)\leq x^{\sharp}(\beta)$. Suppose that $(X,E,F)$ is a Laver-like endomorphic algebra. Then suppose that $\alpha\in\mathrm{crit}(\Gamma(X,E))$. Then define the congruence $\equiv^{\alpha}$ on $(X,E,F)$ by letting $x\equiv^{\alpha}y$ if and only if $f(x_{1},…,x_{n_{f}},x)=f(x_{1},…,x_{n_{f}},y)$ where $x_{1},…,x_{n_{f}}\in X$ and $\mathrm{crit}(f,x_{1},…,x_{n_{f}})=\alpha$ and $(f,x_{1},…,x_{n_{f}})*(f,x_{1},…,x_{n_{f}})\in\mathrm{Li}(\Gamma(X,E))$.

In the Laver-like LD-systems which we have looked at which are suitable for cryptographic purposes, $\mathrm{crit}[X]$ tends to be rather small (for cryptographic purposes, $X$ should have at least about 9 critical points, but the largest classical Laver table ever computed $A_{48}$ has 49 critical points).

$\mathbf{Proposition}:$

  1. If $y\equiv^{\alpha}z$, then $x*y\equiv^{x^{\sharp}(\alpha)}x*z$ and $x\circ y\equiv^{x^{\sharp}(\alpha)}x\circ z$.
  2. Suppose that $X$ is a Laver-like LD-system and $x\in X$. Let $\alpha$ be the least critical point such that $x^{\sharp}(\alpha)=\max(\mathrm{crit}[X])$. Then if $y\equiv^{\alpha}z$, then $x*y=x*z$ and $x\circ y=x\circ z.$

Therefore if $\mathbf{y}\in X/\equiv^{\alpha}$ is the equivalence class of $y\in X$, then define $x*\mathbf{y}$ to be the equivalence class of $x*y$ in the quotient algebra $X/\equiv^{x^{\sharp}(\alpha)}$ and define $x\circ\mathbf{y}$ to be the equivalence class of $x\circ\mathbf{y}$ in $X/\equiv^{x^{\sharp}(\alpha)}$.

$\mathbf{Proposition}$ Suppose that $(X,t^{\bullet})$ is an $n+1$-ary Laver-like LD-system. Suppose that $\mathfrak{u}_{1},…,\mathfrak{u}_{n},\mathfrak{v}_{1},…,\mathfrak{v}_{n}\in\Diamond(X,t^{\bullet})$. Then $\mathrm{crit}(\mathfrak{u}_{1},…,\mathfrak{u}_{n})\leq\mathrm{crit}(\mathfrak{v}_{1},…,\mathfrak{v}_{n})$ in $\Gamma(\Diamond(X,t^{\bullet}))$ if and only if $\mathrm{crit}(\mathfrak{u}_{1}(\varepsilon),…,\mathfrak{u}_{n}(\varepsilon))\leq\mathrm{crit}(\mathfrak{v}_{1}(\varepsilon),…,\mathfrak{v}_{1}(\varepsilon))$.

We may therefore define $\mathrm{crit}(\mathfrak{u}_{1},…,\mathfrak{u}_{n})=\mathrm{crit}(\mathfrak{u}_{1}(\varepsilon),…,\mathfrak{u}_{1}(\varepsilon))$.

$\mathbf{Proposition}$ Suppose that $(X,t^{\bullet})$ is an $n+1$-ary Laver-like LD-system and $\alpha\in\mathrm{crit}(\Gamma(X,t^{\bullet}))=\mathrm{crit}(\Gamma(\Diamond(X,t^{\bullet})))$. Then $(\Diamond(X,t^{\bullet}))/\equiv^{\alpha}\simeq\Diamond((X,t^{\bullet})/\equiv^{\alpha})$. In particular, define a mapping $\phi:\Diamond(X,t^{\bullet})\rightarrow\Diamond((X,t^{\bullet})/\equiv^{\alpha})$ as follows. Let $\mathfrak{l}\in\Diamond(X,t^{\bullet})$. Let $\mathbf{BAD}_{\mathfrak{l}}$ be the set of all strings $i\mathbf{x}\in\{1,…,n\}^{*}$ with $\mathrm{crit}(1\mathbf{x},…,n\mathbf{x})\geq\alpha$. Let $\mathbf{GOOD}_{\mathfrak{l}}$ be the set of all strings in $\{1,…,n\}^{*}$ which are not in $\mathbf{BAD}_{\mathfrak{l}}$ nor have suffixes in $\mathbf{BAD}_{\mathfrak{l}}$. Then $\phi(\mathfrak{l})(\mathbf{x})=\mathfrak{l}(\mathbf{x})/\equiv^{\alpha}$ whenever $\mathbf{x}\in\mathbf{GOOD}_{\mathfrak{l}}$ and $\phi(\mathfrak{l})(\mathbf{x})=\#$ otherwise. Then $\phi$ is a homomorphism whose kernel is $\equiv^{\alpha}$.

Analysis of the Ko-Lee key exchange for Laver-like LD-systems.

The security of the Ko-Lee key exchange for Laver-like LD-systems depends on the difficulty of the following problem.

Problem A for $(a,x,b)$ in $X$: Suppose that $X$ is a Laver-like algebra. Suppose that $a,x,b\in X,r=a\circ x,s=x\circ b$. Let $\alpha$ be the least ordinal such that $a^{\sharp}(\alpha)=\max(\mathrm{crit}[X])$ and let $\beta$ be the least ordinal such that $r^{\sharp}(\beta)=\max(\mathrm{crit}[X])$.

INPUT: $x,r,s,\alpha,\beta$ are known.

OBJECTIVE: Find $a’$ such that $r=a’\circ x$ (Problem A-1) or find $\mathbf{b}\in X/\equiv^{\beta}$ such that $x\circ\mathbf{b}\equiv^{\alpha}s$ (Problem A-2).

Note: In the above problem, we assume that $\alpha$ is known since $X$ usually has a limited number of critical points and $\alpha$ can either be solved or there are a limited number of possibilities for $\alpha$.

We take note that problem A is asymmetric in the roles of $a$ and $b$. In particular, Problem A-2 seems to be an easier problem than problem A-1 since $X/\equiv^{\beta}$ is simpler than $X$.

Constructing endomorphic Laver tables

Suppose that $(X,*)$ is a Laver-like LD-system. If $t:X^{n}\rightarrow X$ is a mapping that satisfies the identity $x*t(x_{1},…,x_{n})=t(x*x_{1},…,x*x_{n})$, then define an operation $T:X^{n+1}\rightarrow X$ by letting $T(x_{1},…,x_{n},x)=t(x_{1},…,x_{n})*x$. Then the algebra $(X,T)$ is a Laver-like endomorphic algebra.

$\mathbf{Proposition:}$ Suppose that $(X,*)$ is a Laver-like LD-system and $t:X^{n}\rightarrow X$ is a mapping that satisfies the identity $x*t(x_{1},…,x_{n})=t(x*x_{1},…,x*x_{n})$. Then define $T:X^{n+1}\rightarrow X$ by letting $T(x_{1},…,x_{n},x)=t(x_{1},…,x_{n})*x$. Then
$\mathrm{crit}(T,x_{1},…,x_{n})\leq\mathrm{crit}(T,y_{1},…,y_{n})$ in $\Gamma(X,T)$ if and only if
$\mathrm{crit}(t(x_{1},…,x_{n}))\leq\mathrm{crit}(t(y_{1},…,y_{n}))$ in $(X,*)$.

By the above Proposition, we will hold to the convention that $\mathrm{crit}(T,x_{1},…,x_{n})=\mathrm{crit}(t(x_{1},…,x_{n}))$.

If $x>0$, then define $(x)_{r}$ to be the unique integer with $1\leq(x)_{r}\leq r$ and where $(x)_{r}=x\mod\,r$. If $n\geq m$, then define a mapping $\pi_{n,m}:A_{n}\rightarrow A_{m}$ by letting $\pi_{n,m}(x)=(x)_{2^{m}}$. Define a linear ordering $\leq^{L}_{n}$ on the classical Laver table $A_{n}$ by induction on $n$ by letting $x<^{L}_{n+1}y$ if and only if $\pi_{n+1,n}(x)<^{L}_{n}\pi_{n+1,n}(y)$ or $\pi_{n+1,n}(x)=\pi_{n+1,n}(y),x < y$. For simplicity, we shall simply write $\leq^{L}$ for $\leq^{L}_{n}$. Then $y\leq^{L}z\rightarrow x*_{n}y\leq^{L}x*_{n}z$.

Suppose that $\mathbf{S}$ is a function such that

  1. if $n$ is a natural number and $x_{1},…,x_{r}\in A_{n}$, then $\mathbf{S}(n;x_{1},…,x_{r})\in\{0,1\}$, and
  2. if $x_{1},…,x_{r}\in A_{m},y_{1},…,y_{r}\in A_{n}$ and there is an isomorphism $\iota:\langle x_{1},…,x_{r}\rangle\rightarrow\langle y_{1},…,y_{r}\rangle$ with $\iota(x_{1})=y_{1},…,\iota(x_{r})=y_{r}$ and which preserves $\leq^{L}$, then $\mathbf{S}(m,x_{1},…,x_{r})=\mathbf{S}(n,y_{1},…,y_{r})$.

Then define a mapping $\mathbf{S}_{n}:A_{n}^{r}\rightarrow A_{n}$ for all $n$ by induction on $n$. Suppose that $\mathbf{S}_{n}$ has been defined already and suppose that $x_{1},…,x_{r}\in A_{n+1}$. Then let $v=\mathbf{S}_{n}(\pi_{n+1,n}(x_{1}),…,\pi_{n+1,n}(x_{r}))$. If $|\{v,v+2^{n}\}\cap\langle x_{1},…,x_{r}\rangle|=1$, then let $\mathbf{S}_{n+1}(x_{1},…,x_{r})$ be the unique element in $\{v,v+2^{n}\}\cap\langle x_{1},…,x_{r}\rangle$. If $|\{v,v+2^{n}\}\cap\langle x_{1},…,x_{r}\rangle|=2$, then let $\mathbf{S}_{n}(x_{1},…,x_{r})=v+2^{n}\cdot\mathbf{S}(n;x_{1},…,x_{r})$.

Then for all $n$, the operation $\mathbf{S}_{n}$ satisfies the identity $x*_{n}\mathbf{S}_{n}(x_{1},…,x_{r})=\mathbf{S}_{n}(x*_{n}x_{1},…,x*_{n}x_{r})$.

Analysis of the Ko-Lee key exchange for functional endomorphic Laver tables.

For our analysis of the Ko-Lee key exchange for functional endomorphic Laver tables, assume that $t:A_{n}^{2}\rightarrow A_{n}$ is a mapping that satisfies the identity $x*_{n}t(y,z)=t(x*_{n}y,x*_{n}z)$ and $T^{\bullet}:A_{n}^{3}\rightarrow A_{n}$ is defined by $T^{\bullet}(x,y,z)=t(x,y)*z$.

In the classical Laver table $A_{n}$, we have $\mathrm{crit}(x)\leq\mathrm{crit}(y)$ if and only if $\gcd(x,2^{n})\leq\gcd(y,2^{n})$. Therefore, for the classical Laver table $A_{n}$, we define $\mathrm{crit}(x)=\log_{2}(\gcd(x,2^{n}))$. In the classical Laver table $A_{n}$, we have $x\equiv^{m}y$ if and only if $x=y\mod 2^{m}$. If $x\in A_{n}$, then let $o_{n}(x)$ be the least natural number $m$ such that $x*_{n}2^{m}=2^{n}$. In other words, $o_{n}(x)$ is the least critical point $\alpha\in\mathrm{crit}[A_{n}]$ where in $A_{n}$, we have $x^{\sharp}(\alpha)=\max(\mathrm{crit}[A_{n}])$.

Let $\mathfrak{u}_{1},\mathfrak{u}_{2},\mathfrak{l}_{1},\mathfrak{l}_{2},\mathfrak{v}_{1},\mathfrak{v}_{2}\in\Diamond(X,T^{\bullet})$. Then in order for problem A for $(\mathfrak{u}_{1},\mathfrak{u}_{2}),(\mathfrak{l}_{1},\mathfrak{l}_{2}),(\mathfrak{v}_{1},\mathfrak{v}_{2})$ to be difficult, one needs for $o_{n}(t(\mathfrak{u}_{1}(\varepsilon),\mathfrak{u}_{2}(\varepsilon))\circ_{n}t(\mathfrak{l}_{1}(\varepsilon),\mathfrak{l}_{2}(\varepsilon)))$ to be as large as possible. We therefore recommend for $o_{n}(t(\mathfrak{u}_{1}(\varepsilon),\mathfrak{u}_{2}(\varepsilon))\circ_{n}t(\mathfrak{l}_{1}(\varepsilon),\mathfrak{l}_{2}(\varepsilon)))\geq 4$ for the functional endomorphic Laver table based Ko-Lee key exchange to be secure. Unfortunately, $o_{n}(x\circ y)$ is usually very small $\leq 4$ except for highly specialized values of$ x,y$. If $x,y\in A_{n}$, then $o_{n}(x\circ_{n}y)\leq\min(o_{n}(x),o_{n}(y))$, so $o_{n}(x\circ_{n}y)$ is typically very small.

The following function shows that $o_{n}(x)$ is usually small (usually 2 or 4).

Function:The following function maps $n$ to the number of elements $x\in A_{20}$ with $o_{20}(x)=n$.
[0→1,1→20,2→555085,3→ 107010,4→ 316545,5→ 55,6→ 37235,7→ 7255,8→ 21230,9→ 24, 10→2193, 11→462, 12→1191, 13→12, 14→144, 15→41, 16→58, 17→4, 18→8, 19→2, 20→1 ]
Increasing $n$ past $10$ in $A_{n}$ will probably not increase the security of functional endomorphic Laver table based cryptosystems.

While $\{o_{n+1}(x),o_{n+1}(x)+2^{n}\}\subseteq\{o_{n}(x),o_{n}(x)+2^{n}\}$, and $o_{n+1}(x+2^{n})=o_{n}(x)$, the following data indicates that for $n\geq 10$ increasing $n$ has little effect on $o_{n}(x)$ since it is very rare for $o_{n+1}(x)=o_{n}(x)+1$ as $n$ gets large.

The n-th entry in the following data list is the probability (from a sample size of 100000) that $o_{n}(x)-o_{n}((x)_{2^{n-1}})=1$ for $x\in A_{n}$.
[1→0.5004, 2→ 0.50211, 3→ 0.5006, 4→ 0.37539, 5→ 0.37352, 6→ 0.25163, 7→ 0.18058, 8→ 0.11521, 9→ 0.0929, 10→ 0.05558, 11→ 0.0364, 12→ 0.02191, 13→ 0.01572, 14→ 0.00878, 15→ 0.00513, 16→ 0.00324, 17→ 0.00242, 18→ 0.00124, 19→ 0.00072, 20→ 0.00043, 21→ 0.00041, 22→
0.0002, 23→ 0.00012, 24→ 2.e-05, 25→ 4.e-05, 26→ 1.e-05, 27→ 2.e-05, 28→ 0., 29→ 0., 30→ 0., 31→ 0., 32→ 0., 33→ 0., 34→ 0., 35→ 0., 36→ 0., 37→ 0., 38→ 0., 39→ 0., 40→ 0., 41→ 0., 42→ 0., 43→ 0., 44→ 0., 45→ 0., 46→ 0., 47→ 0., 48→ 0. ]

While one can show that $o_{n}(1)\rightarrow\infty$ using large cardinals, there is no known proof in ZFC that $o_{n}(1)\rightarrow\infty$ and it is known that if $o_{n}(1)\rightarrow\infty$, then $o_{n}(1)$ must diverge very slowly.

Increases $n$ past about 10 or so does not seem to increase the security of the functional endomorphic Laver table based cryptosystems. If $n$ is much larger than $10$, and if $f$ is a $k$-ary term in $\Diamond(X,T^{\bullet})$ and $\mathfrak{l}_{1},…,\mathfrak{l}_{k}\in\Diamond(X,T^{\bullet})$, then $f(\mathfrak{l}_{1},…,\mathfrak{l}_{k})(\mathbf{x})$ is either very close to $2^{n}$, very close to $1$, or very close to $\mathfrak{l}_{i}(\mathbf{y})$ for some string $\mathbf{y}$. Said differently, increasing the size of $n$ past about 10 or so does not seem to make problem A (or any other cryptographic problem) much harder to solve.

Leave a Reply

Your email address will not be published. Required fields are marked *

three + = seven