Non-commutitive and nonassociative algebraic structures in cryptography

Question

Are there any cryptographic algorithms or primitives that have been developed and studied that make use of non-commutative or non-associative algebraic structures such as quaternion integers or octonion integers? It seems to me that many of these structures can preserve the things that make them useful to cryptography (the trapdoor nature of multiplication for example) while removing some of the tools used to attack it (symmetries exploited in commutativity and associativity).

There are several structures that are non-commutative and non-associative that have many features of unique factorization domains, such as Hurwitz quaternions and the 'Cayley' integers studied by Conway and Smith; It wouldn't surprise me to learn there are other structures that have similar properties that are close enough to the integers we're familiar with yet with broken symmetries that make them more resistant to cryptanalytic attacks.

The most obvious utility I can think of is using quaternion or octonion based unique factorization domains in RSA, but many cryptographic systems that use objects like integers I can see being extended to alternative structures. The downside I can see is that some hidden congruence relations that could be exploited don't exist in the integers. Are there cryptosystems that use such alternatives to the integers?

Answer 1

A self-distributive algebra is an algebra $(X,*)$ that satisfies the identity $x*(y*z)=(x*y)*(x*z)$. There are several cryptosystems that use self-distributive algebras as platforms and these cryptosystems should be thought of as non-associative versions of the more well-known non-abelian group based cryptosystems (such as the Anshel-Anshel-Goldfeld and Ko-Lee key exchanges). Since the current quantum algorithms have nothing to do with self-distributivity, I would suspect that cryptosystems based on self-distributive algebras would be no less secure against quantum attacks than they are against classical attacks.

Cryptosystem 1: This paper by Kalka and Teicher presents a self-distributive algebra based key exchange which is a modifification the Anshel-Anshel-Goldfeld key exchange for groups.

Cryptosystem 2: In this paper, Patrick Dehornoy proposed an authentication protocol which (with some modification) could use any self-distributive algebra as a platform.

Cryptosystem 3: The Ko-Lee key exchange for non-abelian groups extends to a self-distributive algebra based key exchange. Define terms $t_{n}$ for $n\geq 1$ by letting $$t_{1}(x,y)=y,t_{2}(x,y)=x,t_{n+2}(x,y)=t_{n+1}(x,y)*t_{n}(x,y).$$ Then $x*(y*z)=t_{n+1}(x,y)*(t_{n}(x,y)*z)$ for all $x,y,z$ and $n\geq 1$. Consider the following key exchange.

A self-distributive structure $(X,*)$ and an element $x\in X$ are public.

1. Alice selects some $a\in X$ and $n\geq 1$ and sends $r_{1}=t_{n+1}(a,x),r_{2}=t_{n}(a,x)$ to Bob.

2. Bob selects some $b\in X$ and sends $s=x*b$ to Alice.

Let $K=a*(x*b)$.

3. Alice computes $K$ using the fact that $K=a*s$.

4. Bob computes $K$ using the fact that $K=r_{1}*(r_{2}*b)$.

Now these cryptosystems just need a suitable self-distributive algebra as a platform.

Platform type 1: racks and quandles. Racks and quandles are among the most well-known self-distributive algebras. Racks and quandles arise from groups, so I would consider these cryptosystems a part of non-abelian group based cryptography instead of non-associative cryptography.

Platform type 2: Shifted conjugacy on braids. Braid based cryptography does not appear to be secure and Dehornoy's authentication scheme for shifted conjugacy has been attacked in this paper.

Platform type 3: Algebras of elementary embeddings. These are the algebras which I have been working on, and there is currently no one else studying these structures. The algebras of elementary embeddings are self-distributive structures that arise from the rank-into-rank cardinals at the top of the large cardinal hierarchy. It is too early to comment whether these algebras of elementary embeddings could be made into secure cryptosystems.

Note: The action of braid groups on quandles could be used to greatly improve the security and efficiency of braid group based cryptosystems.

Answer 2

People have proposed schemes for building cryptographic hash functions using $SL_2$ (a non-commutative group over matrices). See, e.g., "Hashing with SL2", http://www.cerias.purdue.edu/apps/reports_and_papers/view/1114.

That said, standard cryptographic hash functions work just fine, so there's not a clear advantage to using this approach in practice, as far as we can tell.

Answer 3

Late answer, but: there are a number of such algebraic structures used to instantiate LWE and NTRU.

LWE in non-commutative algebras: https://eprint.iacr.org/2019/680

LWE in non-commutative group rings: https://eprint.iacr.org/2016/1169

NTRU from the octonions: https://ieeexplore.ieee.org/document/5623536

NTRU in quaternion algebras: https://link.springer.com/article/10.1007/s10623-017-0451-4 and https://www.semanticscholar.org/paper/Isecure-Qtru%3A-Quaternionic-Version-of-the-Ntru-Malekian-Zakerolhosseini/a65e7d99fbf0297ffb0a2f68496bb24778a5b4f3?p2df