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

In my research on the generalizations of Laver tables, I found that the endomorphic Laver tables could be used as platforms for several cryptosystems. I am currently the only one looking at endomorphic Laver table based cryptosystems, and it is unclear whether endomorphic Laver table based cryptosystems are secure or not. I am therefore giving this post to invite researchers to evaluate the security of endomorphic Laver table based cryptosystems and to give them some basic information about such cryptosystems. While these posts will give some information that will allow a basic cryptanalysis of endomorphic Laver table based cryptosystems, one would definitely need to read my paper generalizations of Laver tables for a thorough understanding of the algebras involved in these cryptosystems. One should also read the chapter Elementary Embeddings and Algebra in the Handbook of Set Theory (Chapter 11) and Chapters 10-13 in Dehornoy’s book Braids and Self-Distributivity for the an outline of the development of the classical Laver tables before I started my work in 2015.

If you are interested in evaluating the security of endomorphic Laver table based cryptosystems, then please post a comment to this post or send me an e-mail or otherwise contact me.

As a general principle, the non-abelian group based cryptosystems extend to self-distributive algebra based cryptosystems. In particular, the Ko-Lee key exchange, Anshel-Anshel-Goldfeld key exchange, and conjugacy based authentication system, which are some of the most important non-abelian group based cryptosystems, extend from group based cryptosystems to self-distributive algebra based cryptosystems, and the endomorphic Laver tables seem to be good platforms for these self-distributive algebra based cryptosystems.

It seems like endomorphic Laver tables based cryptosystems would even remain secure even against adversaries who have access to quantum computers. I do not believe that quantum computers pose any more of a threat to these cryptosystems than classical computers would since none of the techniques for constructing quantum algorithms (besides Grover’s algorithm which works in general) seem applicable to anything remotely related endomorphic Laver tables. Unless there is a fairly obvious attack, I do not foresee that we will be able to mathematically prove that there is an polynomial time classical or quantum algorithm that breaks these cryptosystems. Nevertheless, I am concerned that these cryptosystems may be susceptible to heuristic attacks.

I have only been able to efficiently compute the endomorphic Laver table operations for two months now (see my previous post for more information about the difficulties in computing the endomorphic Laver table operations and how it was overcome), so these algebras and cryptosystems are fairly unknown.

Endomorphic algebras

An LD-system is an algebra $(X,*)$ that satisfies the self-distributivity identity $x*(y*z)=(x*y)*(x*z)$. LD-systems arise naturally in set theory and in the theory of knots and braids. One can generalize the notion of self-distributivity to algebras with multiple operations, operations of higher arity, and algebras where only some of the fundamental operations are self-distributive.

Suppose that $(X,E,F)$ is an algebraic structure where each $f\in E$ has arity $n_{f}+1$. If $f\in E,a_{1},\dots,a_{n_{f}}\in X$, then define the mapping $L_{f,a_{1},\dots,a_{n_{f}}}$ by letting $L_{f,a_{1},\dots,a_{n_{f}}}(x)=f(a_{1},\dots,a_{n_{f}},x)$. Then we say that $(X,E,F)$ is a partially endomorphic algebra if the mapping $L_{f,a_{1},\dots,a_{n_{f}}}$ is an endomorphism of $(X,E,F)$ whenever $f\in E,a_{1},\dots,a_{n_{f}}\in X$. If $F=\emptyset$, then we shall call $(X,E,F)$ an endomorphic algebra (and we may write $(X,E)$ to denote the endomorphic algebra $(X,E,\emptyset)$). If $(X,t)$ is an endomorphic algebra and $t$ is an $n+1$-ary operation, then we shall call $(X,t)$ an $n+1$-ary self-distributive algebra. The partially endomorphic algebras are the universal algebraic analogues of the LD-systems.

If $(X,E)$ is an endomorphic algebra, then let
$$\Gamma(X,E)=(\bigcup_{f\in E}\{f\}\times X^{n_{f}},*)$$
where the operation $*$ is defined by
$$(f,x_{1},\dots,x_{n_{f}})*(g,y_{1},\dots,y_{n_{g}})=(g,f(x_{1},\dots,x_{n_{f}},y_{1}),\dots,f(x_{1},\dots,x_{n_{f}},y_{n_{g}})).$$
Then $\Gamma(X,E)$ is an LD-system.

Endomorphic algebra based cryptosystems

The Ko-Lee key exchange for semigroups

The following key exchange is a simplified version of the Ko-Lee key exchange for semigroups.

The simplified Ko-Lee key exchange: A semigroup $(X,\circ)$ along with an element $x\in X$ are public.

  1. Alice selects an element $a\in X$ and sends $r=a\circ x$ to Bob.
  2. Bob selects an element $b\in X$ and sends $s=x\circ b$ to Alice.
  3. Let $K=a\circ x\circ b$.

  4. Alice computes $K$ using the fact that $K=a\circ s$.
  5. Bob computes $K$ using the fact that $K=r\circ b$.

An eavesdropper listening in to the communications between Alice and Bob cannot compute $K$. The full-fledged Ko-Lee key exchange would not work for Laver-like algebras since the associative operation on Laver-like algebras has very little commutativity.

The Anshel-Anshel-Goldfeld key exchange for self-distributivity

In this paper, Kalka and Teicher have extended the Anshel-Anshel-Goldfeld key exchange to LD-systems. The following key exchange extends this cryptosystem by Kalka and Teicher to partially endomorphic algebras.

The Anshel-Anshel-Goldfeld key exchange for endomorphic algebras: An partially endomorphic algebra $(X,E,F)$ along with $x_{1},\dots,x_{m},y_{1},\dots,y_{n}\in X$ are public. Let
$$A=\langle x_{1},\dots,x_{m}\rangle,B=\langle y_{1},\dots,y_{n}\rangle.$$

  1. Alice selects some $a\in A$ along with some term $t$ such that $t(x_{1},\dots,x_{m})=a$. Alice selects an
    $f\in E$ along with a tuple $\mathbf{a}=(a_{1},\dots,a_{n_{f}})\in X^{n_{f}}$. Alice then sends $$u_{1}=f(\mathbf{a},y_{1}),\dots,u_{n}=f(\mathbf{a},y_{n}),p_{0}=f(\mathbf{a},a)$$
    to Bob.
  2. Bob selects some $g\in E$ along with $\mathbf{b}=(b_{1},\dots,b_{n_{g}})\in B^{n_{g}}$ and terms
    $t_{1},\dots,t_{n_{g}}$ such that
    $$b_{1}=t_{1}(y_{1},\dots,y_{n}),\dots,b_{n_{g}}=t_{n_{g}}(y_{1},\dots,y_{n}).$$
    Bob then sends the elements $v_{1}=g(\mathbf{b},x_{1}),\dots,v_{m}=g(\mathbf{b},x_{m})$ to Alice.
  3. Let $K=f(\mathbf{a},g(\mathbf{b},a))$.

  4. Alice computes $K$. Alice is able to compute $K$ since Alice knows $f,\mathbf{a}$ and since
    $$g(\mathbf{b},a)=g(\mathbf{b},t(x_{1},\dots,x_{m}))=t(g(\mathbf{b},x_{1}),\dots,g(\mathbf{b},x_{m}))
    =t(v_{1},\dots,v_{m}).$$
  5. Bob computes $K$. Bob is able to compute $K$ since

    $$K=f(\mathbf{a},g(\mathbf{b},a))=f(\mathbf{a},g(b_{1},\dots,b_{n_{g}},a))$$

    $$=g(f(\mathbf{a},b_{1}),\dots,f(\mathbf{a},b_{n_{g}}),f(\mathbf{a},a))$$

    $$=g(f(\mathbf{a},t_{1}(y_{1},\dots,y_{n})),\dots,f(\mathbf{a},t_{n_{g}}(y_{1},\dots,y_{n})),p_{0})$$

    $$=g(t_{1}(f(\mathbf{a},y_{1}),\dots,f(\mathbf{a},y_{n})),\dots,t_{n_{g}}(f(\mathbf{a},y_{1}),\dots,f(\mathbf{a},y_{n})),p_{0})$$

    $$=g(t_{1}(u_{1},\dots,u_{n}),\dots,t_{n_{g}}(u_{1},\dots,u_{n}),p_{0}).$$

  6. No third party will be able to compute the common key $K$.

Laver tables

The classical Laver table $A_{n}$ is the unique algebraic structure $(\{1,\dots,2^{n}\},*_{n})$ that satisfies the self-distributivity identity $x*_{n}(y*_{n}z)=(x*_{n}y)*_{n}(x*_{n}z)$ and where $x*_{n}1=x+1\,\mod 2^{n}$ for $x\in A_{n}$. The operation $*_{n}$ can easily be computed from a 2.5 MB file of precomputed data as long as $n\leq 48$. We believe that it is feasible with current technology to compute $*_{n}$ when $n\leq 96$ though. The classical Laver tables alone are unsuitable as platforms for self-distributive algebra based cryptosystems (the classical Laver tables will offer at most 96 bits of security and in practice such cryptosystems based on the classical Laver tables are effortlessly and instantly broken). The multigenic Laver tables are not suitable as platforms for such cryptosystems either since elements in multigenic Laver tables can easily be factored.

If $(X,*)$ is an LD-system, then a subset $L\subseteq X$ is said to be a left-ideal if $x*y\in L$ whenever $y\in L$. An element $x\in X$ is said to be a left-identity if $x*y=y$ whenever $y\in X$. Let $\mathrm{Li}(X)$ denote the set of all left-identities in the set $(X,*)$. We say that an LD-system $(X,*)$ is Laver-like if

  1. $\mathrm{Li}(X)$ is a left-ideal in $X$, and
  2. Whenever $x_{n}\in X$ for all natural numbers $n$, there is some $N$ such that $x_{0}*\dots*x_{N}\in\mathrm{Li}(X)$ (here the implied parentheses are grouped on the left. i.e. $x*y*z=(x*y)*z$. ).

For example, the classical Laver tables $A_{n}$ are always Laver-like.

If $(X,*)$ is an LD-system, then define the Fibonacci terms $t_{n}$ for $n\geq 1$ by letting $t_{1}(x,y)=y,t_{2}(x,y)=x$ and $t_{n+2}(x,y)=t_{n+1}(x,y)*t_{n}(x,y)$. If $(X,*)$ is a Laver-like LD-system, then define an operation $\circ$ on $X\setminus\mathrm{Li}(X)$ by letting $x\circ y=t_{n+1}(x,y)$ whenever $t_{n}(x,y)\in\mathrm{Li}(X)$ (the operation $\circ$ does not depend on the choice of $n$). The operation $\circ$ is associative and hence suitable for the Ko-Lee key exchange. The operation $\circ$ also satisfies the identity $(x\circ y)*z=x*(y*z)$.

A partially endomorphic algebra $(X,E,F)$ is said to be Laver-like if the hull $\Gamma(X,E)$ is Laver-like. Any Laver-like algebra may be used to induce a partially endomorphic Laver table, but for simplicity, we shall only define the functional endomorphic Laver tables induced by the endomorphic algebras with only one fundamental operation.

Suppose now that $(X,t^{\bullet})$ is a $n+1$-ary Laver-like algebra. Let $\Diamond(X,t^{\bullet})$ be the algebra with underlying set consisting of all functions $\mathfrak{l}:\{1,\dots,n\}^{*}\rightarrow X\cup\{\#\}$ such that

  1. $\mathfrak{l}(\varepsilon)\in X$.
  2. If $\mathfrak{l}(\mathbf{x})\in\#$, then $\mathfrak{l}(i\mathbf{x})\in\#$ for all $i\in\{1,\dots,n\}$.
  3. If $\mathfrak{l}(\mathbf{x})\in X$, then either $\mathfrak{l}(i\mathbf{x})\in X$ for all $i\in\{1,\dots,n\}$ or
    $\mathfrak{l}(i\mathbf{x})=\#$ for all $i\in\{1,\dots,n\}$.
  4. If $\mathfrak{l}(i\mathbf{x})\in X$ for all $i\in\{1,\dots,n\}$, then $(\mathfrak{l}(1\mathbf{x}),\dots,\mathfrak{l}(n\mathbf{x}))\not\in \mathbf{Li}(\Gamma((X,t^{\bullet})))$.
  5. If $\mathfrak{l}(\mathbf{x})\in X$, and $\mathfrak{l}(i\mathbf{x})\in X$ for all $i\in\{1,\dots,n\}$, then
    there is some $x\in X$ where $t(\mathfrak{l}(1\mathbf{x}),\dots,\mathfrak{l}(n\mathbf{x}),x)=\mathfrak{l}(\mathbf{x})$.
  6. $\mathfrak{l}(\mathbf{x})\in X$ for only finitely many strings $\mathbf{x}\in\{1,\dots,n\}^{*}$.

If $\mathfrak{l}_{1},\dots,\mathfrak{l}_{n}\in\Diamond(X,t)$ and $(\mathfrak{l}_{1}(\varepsilon),\dots,\mathfrak{l}_{n}(\varepsilon))\not\in\Gamma((X,t^{\bullet}))$, then define $t_{x}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})\in\Diamond(X,t^{\bullet})$ by $t(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})(\varepsilon)=t^{\bullet}(\mathfrak{l}_{1}(\varepsilon),\dots,\mathfrak{l}_{n}(\varepsilon),x)$ and where $t(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})(\mathbf{x}i)=\mathfrak{l}_{i}(\mathbf{x})$.

Now define an operation $t^{\sharp}:\Diamond(X,t^{\bullet})^{n+1}\rightarrow\Diamond(X,t^{\bullet})$ by letting

  1. $t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l})=\mathfrak{l}$ whenever
    $(\mathfrak{l}_{1}(\varepsilon),\dots,\mathfrak{l}_{n}(\varepsilon))\in\mathrm{Li}(\Gamma(X,t^{\bullet}))$,
  2. otherwise, if $\mathfrak{l}(i)=\#$ for $1\leq i\leq n$, then define
    $t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l})=t_{\mathfrak{l}(\varepsilon)}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})$,
  3. otherwise if $\mathfrak{l}=t(\mathfrak{u}_{1},\dots,\mathfrak{u}_{n})$, then
    $$t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l})$$

    $$=t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},t_{x}(\mathfrak{u}_{1},\dots,\mathfrak{u}_{n}))$$

    $$=t^{\sharp}(t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{u}_{1}),\dots,t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{u}_{n}),t_{x}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})).$$

Then the algebra $(\Diamond(X,t^{\bullet}),t^{\sharp})$ is an $n+1$-ary self-distributive algebra which we shall refer to as a functional endomorphic Laver table. Every functional endomorphic Laver table is a Laver-like endomorphic algebra. If one has an efficient algorithm for computing $\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l}$, then one also has a reasonably efficient algorithm for computing $t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l})$.

The Ko-Lee key exchange for endomorphic Laver tables

One could apply the Ko-Lee key exchange to the operation $\circ$ in $\Gamma(\Diamond(X,t^{\bullet}),t^{\sharp})$. However, since we are only able to compute $t^{\bullet}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l})(\mathbf{x})$ instead of the entire function $t^{\bullet}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l})$, we will need to modify the Ko-Lee key exchange so that the endomorphic Laver tables can be used as a platform for this cryptosystem. The self-distributive Anshel-Anshel-Goldfeld key exchange can be modified in the same way.

The Ko-Lee key exchange for endomorphic Laver tables: Suppose that $(X,t^{\bullet})$ is an $n+1$-ary Laver-like algebra. Then in this key exchange algorithms for computing $\mathfrak{l}_{1},\dots,\mathfrak{l}_{n}\in\Diamond(X,t^{\bullet})$ are public.

  1. Alice selects secret algorithms for computing $\mathfrak{u}_{1},\dots,\mathfrak{u}_{n}\in\Diamond(X,t^{\bullet})$. Let
    $(\mathfrak{j}_{1},\dots,\mathfrak{j}_{n})=(\mathfrak{u}_{1},\dots,\mathfrak{u}_{n})\circ(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})$. Then Alice has secret algorithms for computing $\mathfrak{j}_{1},\dots,\mathfrak{j}_{n}$.
  2. Bob selects secret algorithms for computing $\mathfrak{v}_{1},\dots,\mathfrak{v}_{n}\in\Diamond(X,t^{\bullet})$. Let
    $(\mathfrak{k}_{1},\dots,\mathfrak{k}_{n})=(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})\circ(\mathfrak{v}_{1},\dots,\mathfrak{v}_{n})$. Bob has secret algorithms for computing $\mathfrak{k}_{1},\dots,\mathfrak{k}_{n}$.

    Let
    $$(\mathfrak{w}_{1},\dots,\mathfrak{w}_{n})$$
    $$(\mathfrak{u}_{1},\dots,\mathfrak{u}_{n})\circ(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})\circ(\mathfrak{v}_{1},\dots,\mathfrak{v}_{n}).$$

  3. Let $i\in\{1,\dots,n\},\mathbf{x}\in\{1,\dots,n\}^{*}$, and let $K=\mathfrak{w}_{i}(\mathbf{x})$.

  4. Alice computes $K$. Bob will not reveal the algorithms for computing $\mathfrak{k}_{1},\dots,\mathfrak{k}_{n}$ since Bob’s algorithms for computing $\mathfrak{k}_{1},\dots,\mathfrak{k}_{n}$ depend on his algorithms for computing $\mathfrak{v}_{1},\dots,\mathfrak{v}_{n}$. However, upon request from Alice, Bob will send specific values of the form $\mathfrak{k}_{j}(\mathbf{y})$ to Alice. Alice will be able to compute $K$ using her algorithms for computing $\mathfrak{u}_{1},\dots,\mathfrak{u}_{n}$ and using the values $\mathfrak{k}_{j}(\mathbf{y})$ sent from Bob. In general, Alice will need to ask Bob for the values of $\mathfrak{k}_{j}(\mathbf{y})$ several times.
  5. Bob computes $K$ in a similar manner. Alice will not reveal algorithms for computing $\mathfrak{j}_{1},\dots,\mathfrak{j}_{n}$ either. However, Alice will reveal specific values of the form $\mathfrak{j}_{j}(\mathbf{y})$ to Bob. Bob will therefore compute $K$ using his secret algorithms for computing $\mathfrak{v}_{1},\dots,\mathfrak{v}_{n}$ along with values of the form $\mathfrak{j}_{j}(\mathbf{y})$ sent by Alice.

Remark: The common key $K$ may only have a couple of bits of entropy so the common key $K$ could be found by an eavesdropping party by guessing the most common possibilities. The most obvious way to mitigate this problem is to perform the above key exchange multiple times in order to obtain a large enough key. Another probably more efficient way to mitigate this problem is to use $(\mathfrak{w}_{i}(\mathbf{x}_{0}),\dots,\mathfrak{w}_{i}(\mathbf{x}_{r}))$ as the common key instead where $(\mathbf{x}_{0},\dots,\mathbf{x}_{r})$ is an enumeration of the suffixes of $\mathbf{x}$.

To be continued

In the second post, I will give a detailed analysis of the Ko-Lee key exchange for endomorphic Laver tables. Furthermore, at the same time, I will release an online JavaScript program for analyzing the Ko-Lee key exchange for endomorphic Laver tables.

Endomorphic Laver tables can be computed efficiently

The partially endomorphic Laver tables are the generalizations of the notion of the classical Laver table to algebraic structures which may have an arbitrary number of fundamental operations each of arbitrary arity and where only some of the fundamental operations are required to be self-distributive. While the endomorphic Laver tables have much richer combinatorial structure than is found in the corresponding classical Laver tables and multigenic Laver tables, we are still able to somewhat efficiently compute information about the output of the fundamental operations on endomorphic Laver tables. In fact, as I have mentioned before, you may compute in endomorphic Laver tables here and here.

Since we are able to compute the endomorphic Laver tables, it is plausible that the endomorphic Laver tables could be used as platforms for cryptosystems which are secure against classical attacks and even quantum attacks, but much more research still needs to be done on this topic.

The definition of Laver-like partially endomorphic algebras and partially endomorphic Laver tables

The definition of the partially endomorphic Laver tables is somewhat complicated. For simplicity, we shall only define the well-founded partially endomorphic Laver tables induced from known partially endomorphic Laver-like algebras.

Suppose that $X$ is a set and $E,F$ are sets of operations on $X$. Suppose that each $\mathfrak{g}\in F$ has arity $n_{\mathfrak{g}}$ and each $f\in E$ has arity $n_{f}+1$. If $f\in E,a_{1},…,a_{n_{f}}\in X$ then let $L_{f,a_{1},…,a_{n_{f}}}:X\rightarrow X$ be the mapping defined by $L_{f,a_{1},…,a_{n_{f}}}(x)=f(a_{1},…,a_{n_{f}},x)$. Then we say that $(X,E,F)$ is an endomorphic algebra if each mapping $L_{f,a_{1},…,a_{n_{f}}}$ is an endomorphism of $(X,E,F)$. In other words, the partially endomorphic algebras are precisely the algebras where one has the notion of an inner endomorphism. If $F=\emptyset$ and $(X,E,F)$ is a partially endomorphic algebra, then we say that $(X,E)$ is an endomorphic algebra. We say that an algebra $(X,*)$ is an LD-system (or left-distributive algebra) if $(X,*)$ satisfies the identity $x*(y*z)=(x*y)*(x*z)$.

Suppose that $(X,*)$ is a left-distributive algebra. Then we say that a subset $L\subseteq X$ is a left-ideal if $x*y\in L$ whenever $y\in L$. We say that an element $x\in X$ is a left-identity if $x*y=y$ for all $y\in X$. Let $\mathrm{Li}(X)$ denote the set of all left-identities in $X$. A left-distributive algebra $(X,*)$ is said to be Laver-like if $\mathrm{Li}(X)$ is a left-ideal and whenever $x_{n}\in X$ for all $n\in\omega$ there is some $N$ where $x_{0}*…*x_{N}\in\mathrm{Li}(X)$.

If $(X,*)$ is Laver-like, then define $\preceq$ to be the smallest partial ordering on $X$ where $x\preceq x*y$ whenever $x\in X\setminus\mathrm{Li}(X)$. Then $(X,\preceq)$ is a dual well-founded partially ordered set and the dual well-foundedness of $(X,\preceq)$ is necessary for all inductive proofs involving the generalizations of Laver tables.

If $(X,E)$ is an endomorphic algebra, then define the hull $\Gamma(X,E)$ of $(X,E)$ to be the algebra with underlying set
$\bigcup_{f\in E}\{f\}\times X^{n_{f}}$ and binary operation $*$ defined by
$$(f,x_{1},…,x_{n_{f}})*(g,y_{1},…,y_{n_{g}})$$
$$=(g,f(x_{1},…,x_{n_{f}},y_{1}),…,f(x_{1},…,x_{n_{f}},y_{n_{g}})).$$ Then the hull $\Gamma(X,E)$ of an endomorphic algebra is always a left-distributive algebra. We say that a partially endomorphic algebra $(X,E,F)$ is Laver-like if $\Gamma(X,E)$ is Laver-like.

Suppose that $\mathcal{V}=(V,(f^{\mathcal{V}})_{f\in E},(\mathfrak{g}^{\mathcal{V}})_{\mathfrak{g}\in F})$ is a Laver-like partially endomorphic algebra. Suppose furthemore that $X$ is a set of variables and $v_{x}\in V$ for all $x\in X$. For each $x\in X$ and $f\in E$, let $f_{x}$ be an $n_{f}$-ary function symbol. Let $\mathcal{G}=\{f_{x}\mid f\in E,x\in X\}\cup F$. Let $\mathbf{T}_{\mathcal{G}}[X]$ be the set of all terms in the language $\mathcal{G}$ with variables in $X$. Let $L$ be the subset of $\mathbf{T}_{\mathcal{G}}[X]$ and let $\phi:L\rightarrow V$ be the mappings defined by induction on the complexity of the term $\ell\in\mathbf{T}_{\mathcal{G}}[X]$ according to the following rules:

  1. $X\subseteq L$ and $\phi(x)=v_{x}$ for each $x\in X$.
  2. If $\mathfrak{g}\in F$ and $\ell_{1},…,\ell_{n_{\mathfrak{g}}}\in L$, then $\mathfrak{g}(\ell_{1},…,\ell_{n_{\mathfrak{g}}})\in L$ and
    $\phi(\mathfrak{g}(\ell_{1},…,\ell_{n_{\mathfrak{g}}}))=\mathfrak{g}(\phi(\ell_{1}),…,\phi(\ell_{n_{\mathfrak{g}}}))$.
  3. if $f\in E,x\in X$ and $\ell_{1},…,\ell_{n_{f}}\in L$, then $f_{x}(\ell_{1},…,\ell_{n_{f}})\in L$ if and only if
    $$(f,\phi(\ell_{1}),…,\phi(\ell_{n_{f}}))\not\in\mathrm{Li}(\Gamma(V,(f^{\mathcal{V}})_{f\in E})).$$
    If $f_{x}(\ell_{1},…,\ell_{n_{f}})\in L$, then
    $$\phi(f_{x}(\ell_{1},…,\ell_{n_{f}}))=f^{\mathcal{V}}(\phi(\ell_{1}),…,\phi(\ell_{n_{f}}),v_{x})).$$

For each $f\in E$, define an operation $f^{\sharp}$ on $L$ by
$f^{\sharp}(\ell_{1},…,\ell_{n},\ell)=\ell$ whenever $f_{x}(\ell_{1},…,\ell_{n})\in L$ and if
$f_{x}(\ell_{1},…,\ell_{n})\not\in L$ then

  1. $f^{\sharp}(\ell_{1},…,\ell_{n},x)=f_{x}(\ell_{1},…,\ell_{n})$
  2. $f^{\sharp}(\ell_{1},…,\ell_{n},\mathfrak{g}(u_{1},…,u_{n_{g}}))
    =\mathfrak{g}(f^{\sharp}(\ell_{1},…,\ell_{n},u_{1}),…,f^{\sharp}(\ell_{1},…,\ell_{n},u_{n_{g}})),$
  3. $f^{\sharp}(\ell_{1},…,\ell_{n},g_{x}(u_{1},…,u_{n_{g}}))
    =g^{\sharp}(f^{\sharp}(\ell_{1},…,\ell_{n_{g}},u_{1}),…,f^{\sharp}(\ell_{1},…,\ell_{n_{g}},u_{n_{g}}),f_{x}(\ell_{1},…,\ell_{n_{g}})).$

Then we shall write $\mathbf{L}((v_{x})_{x\in X},\mathcal{V})$ for the algebra $(L,(f^{\sharp})_{f\in E},F)$. The algebra $(L,(f^{\sharp})_{f\in E},F)$ is a Laver-like partially endomorphic algebra.

Endomorphic Laver tables are usually infinite

The classical Laver tables and multigenic Laver tables are always locally finite. Furthermore, every Laver-like LD-system is locally finite. In particular, the quotient algebra of elementary embeddings $\mathcal{E}_{\lambda}/\equiv^{\gamma}$ is always locally finite. On the other hand, the partially endomorphic Laver tables with at least one fundamental operation of arity at least 3 that we have looked at are all infinite. Since the endomorphic Laver tables that we have looked at are all infinite, it is unclear as to how these endomorphic Laver tables could arise naturally from the algebras of rank-into-rank embeddings.

Endomorphic Laver tables are abundant

There are many ways to construct $N$-ary operations $t:A_{n}^{N}\rightarrow A_{n}$ with $x*t(x_{1},…,x_{N})=t(x*x_{1},\ldots,x*x_{N})$. If $t$ satisfies the identity $x*t(x_{1},…,x_{N})=t(x*x_{1},\ldots,x*x_{N})$, then define a mapping $T:A_{n}^{N+1}\rightarrow A_{n}$ by letting $T(x_{1},…,x_{N},x)=t(x_{1},…,x_{N})*x$. Then $(X,T)$ is a Laver-like $N+1$-ary algebra.

Every term $t$ in the language of LD-systems satisfies the identity $x*t(x_{1},…,x_{N})=t(x*x_{1},\ldots,x*x_{N})$.

Let $(x)_{r}$ be the unique natural number such that $1\leq(x)_{r}\leq r$ and $(x)_{r}=x\mod\,r$. Then define a mapping $\pi_{n,m}:A_{n}\rightarrow A_{m}$ by $\pi_{n,m}(x)=(x)_{2^{m}}$ whenever $n\geq m$. If $x,y\in A_{n}$, then say that $x\leq^{L}y$ if $x=y$ or if $m$ is the least natural number with $\pi_{n,m}(x)\neq\pi_{n,m}(y)$, then $\pi_{n,m}(x)<\pi_{n,m}(y).$ Then $\leq^{L}$ is a linear ordering with $y\leq^{L}z\rightarrow x*y\leq^{L}x*z$ whenever $x,y,z\in A_{n}$. Define an operation $T_{k,r}:A_{n}^{r}\rightarrow A_{n}$ by letting $T_{k,r}(x_{1},...,x_{r})=x_{\sigma(k)}$ where $\sigma$ is a permutation of $\{1,...,r\}$ with $x_{\sigma(1)}\leq^{L}...\leq^{L}x_{\sigma(n)}$. Then $A_{n}$ satisfies the identity $x*T_{k,r}(x_{1},...,x_{r})=T_{k,r}(x*x_{1},...,x*x_{r})$ as well. There are more complex techniques for constructing mappings $t:A_{n}^{N}\rightarrow A_{n}$ that satisfy the identity $x*t(x_{1},...,x_{N})=t(x*x_{1},\ldots,x*x_{N})$.

At least exponential growth in output length

Let $e$ be a variable. Let $\ell_{1}=e$. Let $\mathcal{V}=(A_{n},t^{\mathcal{V}})$ where $t^{\mathcal{V}}$ is the operation defined by $t^{\mathcal{V}}(x,y,z)=y*z$. Let $L=\mathbf{L}((1)_{r\in\{e\}},\mathcal{V})$. For $1\leq i<2^{n}$, let $\ell_{i+1}=t(\ell_{i},\ell_{i})$. Then the term $\ell_{i}$ has $2^{i-1}$ instances of the variable $e$ and by induction one can show that in $L$, we have $t^{\sharp}(\ell_{r},\ell_{r},\ell_{s})=\ell_{r*_{n}s}$. Such large output is typical for endomorphic Laver table operations. Therefore the output of an endomorphic Laver table operation is often too large to be stored completely by a computer. Some computer experiments suggest that the output size of the endomorphic Laver table operations may be super-exponential.

The trick to computing endomorphic Laver tables

In one sense, the endomorphic Laver table operations are not efficiently computable since our output grows at least exponentially, but we are able to find a sense in which the endomorphic Laver table operations are efficiently computable. The first idea to computing endomorphic Laver tables is not to compute the entire term $t^{\sharp}(\ell_{1},…,\ell_{n},\ell)$ but to recursively compute just a piece of information from the term $t^{\sharp}(\ell_{1},…,\ell_{n},\ell)$ or an approximation of the term $t^{\sharp}(\ell_{1},…,\ell_{n},\ell)$. We shall see that these approximations of the term $t^{\sharp}(\ell_{1},…,\ell_{n},\ell)$ are analogous to how floating point numbers approximate the real numbers. The second idea is to use the original endomorphic Laver-like algebra to extract the necessary information about the terms.

For simplicity of notation, assume that $(X,t^{\bullet})$ is an $n+1$-ary Laver-like algebra.

Let $\Diamond(X,t^{\bullet})$ be the set of all functions $\mathfrak{l}:\{1,…,n\}^{*}\rightarrow X\cup\{\#\}$ that satisfy the following conditions:

  1. $\mathfrak{l}(\varepsilon)\in X$.
  2. If $\mathfrak{l}(\mathbf{x})=\#$, then $\mathfrak{l}(i\mathbf{x})=\#$ for $1\leq i\leq n$.
  3. If $\mathfrak{l}(\mathbf{x})\in X$, then either $\mathfrak{l}(i\mathbf{x})\in X$ for $1\leq i\leq n$ or
    $\mathfrak{l}(i\mathbf{x})=\#$ for $1\leq i\leq n$.
  4. If $\mathfrak{l}(i\mathbf{x})\in X$ for $1\leq i\leq n$, then
    $(\mathfrak{l}(1\mathbf{x}),…,\mathfrak{l}(n\mathbf{x}))\not\in\mathrm{Li}(\Gamma(X,t^{\bullet}))$.
  5. If $\mathfrak{l}(i\mathbf{x})\in X$ for $1\leq i\leq n$, then there is some $x\in X$ where
    $t^{\bullet}(\mathfrak{l}(1\mathbf{x}),…,\mathfrak{l}(n\mathbf{x}),x)=\mathfrak{l}(\mathbf{x})$.
  6. $\mathfrak{l}(\mathbf{x})\in X$ for only finitely many $\mathbf{x}\in X$.

Now if $\mathfrak{l}_{1},…,\mathfrak{l}_{n}\in\Diamond(X,t^{\bullet})^{n}$ and
$(\mathfrak{l}_{1}(\varepsilon),…,\mathfrak{l}_{n}(\varepsilon))\not\in\mathrm{Li}(\Gamma(X,t^{\bullet}))$, and
$x\in X$, then define $t_{x}(\mathfrak{l}_{1},…,\mathfrak{l}_{n}):\{1,…,n\}^{*}\rightarrow X\cup\{\#\}$ by letting
$t_{x}(\mathfrak{l}_{1},…,\mathfrak{l}_{n})(\varepsilon)=t^{\bullet}(\mathfrak{l}_{1}(\varepsilon),…,\mathfrak{l}_{n}(\varepsilon),x)$ and where $t_{x}(\mathfrak{l}_{1},…,\mathfrak{l}_{n})(\mathbf{x}i)=\mathfrak{l}_{i}(\mathbf{x})$ whenever $i\mathbf{x}\in\{1,…,n\}^{*}$.

Then there is a unique operation $t^{\sharp}:\Diamond(X,t^{\bullet})^{n+1}\rightarrow\Diamond(X,t^{\bullet})$ such that

  1. $t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})=\mathfrak{l}$ whenever
    $(\mathfrak{l}_{1}(\varepsilon),…,\mathfrak{l}_{n}(\varepsilon))\in\mathrm{Li}(\Gamma(X,t^{\bullet}))$,
  2. Otherwise, if $\mathfrak{l}(i)=\#$ for $1\leq i\leq n$, then
    $t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})=t_{\mathfrak{l}(\varepsilon)}(\mathfrak{l}_{1},…,\mathfrak{l}_{n})$, and
  3. $$t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},t^{\sharp}(\mathfrak{u}_{1},…,\mathfrak{u}_{n},\mathfrak{u}))$$
    $$=t^{\sharp}(t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{u}_{1}),…,
    t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{u}_{n}),t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{u})).$$

Then the algebra $\Diamond(X,t^{\bullet})$ is isomorphic to a quotient of the endomorphic Laver table $\mathbf{L}((x)_{x\in X},(X,t^{\bullet}))$ by a very small congruence. Furthermore, it is easy to embed any desired endomorphic Laver table into an algebra of the form $\Diamond(X,t^{\bullet})$. Instead of computing the entire output $t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})$, one could just compute $t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})(\mathbf{x})$ for some string $\mathbf{x}$.

Endomorphic Laver tables can be computed quickly

Suppose that $(X,t^{\bullet})$ is an $r+1$-ary Laver-like algebra. By our experiments, we have concluded that if $f(x_{1},…,x_{r})$ is a term whose only function symbol is $t^{\sharp}$, then in $\Diamond(X,t^{\bullet})$, the value of
$f(\mathfrak{l}_{1},…,\mathfrak{l}_{r})(\mathbf{x})$ is usually computable in a few seconds as long as $|\mathbf{x}|<500$ or so in the language JavaScript on a web browser. When $\mathbf{x}$ gets to long, I usually run out of memory or the computation fails from too deep recursion errors.

A limitless source of combinatorial complexity.

While the classical Laver tables and multigenic Laver tables collectively can be thought of as an unlimited source of combinatorial complexity, since every classical Laver table and multigenic Laver table is locally finite, each classical Laver table and multigenic Laver table must only have a limited amount of combinatorial complexity. However, each endomorphic Laver table seems to contain an unlimited amount of combinatorial complexity and there does not appear to be a formula for computing $t^{\bullet}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})(\mathbf{x})$ even for endomorphic Laver tables originally obtained from $A_{5}$. The output of an endomorphic Laver table operation is usually unpredictable, but among the complexity of the output of the endomorphic Laver tables, there is some order amidst the complexity. The output of endomorphic Laver table operations seem to exhibit a sort of periodicity which is similar to the periodicity found in the classical and multigenic Laver tables.

Possible applications to public key cryptography

The endomorphic Laver tables incorporate the following attributes which are necessary for public key cryptography.

  1. The classical Laver tables are combinatorially complicated since they may be used to produce recursive functions which grow faster than the Ackermann function. The multigenic Laver tables are even more complicated. However, the combinatorial richness of the classical Laver tables and multigenic Laver tables is surpassed by the combinatorial complexity that arises from the endomorphic Laver tables.
  2. While the endomorphic Laver tables are combinatorially intricate, the endomorphic Laver tables still retain much algebraic structure. In other words, there is order to the chaos that arises from endomorphic Laver tables.
  3. The endomorphic Laver tables are fairly easy to compute.
  4. The endomorphic Laver tables currently have nothing to do with linear algebra, fourier transforms, or anything of that sort. This is an advantage since quantum algorithms tend to rely on these techniques that have nothing to do with Laver tables. Therefore since quantum algorithms do not seem to help with calculating anything related to Laver tables, endomorphic Laver tables may be useful in post-quantum cryptography (post-quantum cryptography refers to the study of public key cryptosystems that resist attacks from parties that have access to quantum computers).

I will put up a post soon about the various endomorphic Laver tables based cryptosystems along with a preliminary analysis of one of those cryptosystems. It is currently unclear as to whether endomorphic Laver table based cryptosystems are secure and much more investigation on endomorphic Laver tables is necessary before I can gain any confidence about the security of endomorphic Laver table based cryptosystems.