At this page, you can now plot the graphs of the output of endomorphic Laver tables. As one would expect, the endomorphic Laver tables are much more complex than their corresponding classical Laver tables or multigenic Laver tables. Here is an graph of the outputs of an endomorphic Laver table operation.

# Month: May 2017

## 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).

- 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$.
- 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)}$.

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

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.

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.

$\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

- 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
- 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).

[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 ]

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.

[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.