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.

Leave a Reply

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

× seven = fourteen