Paper 2021/896

Rebuttal to claims in Section 2.1 of the ePrint report 2021/583 "Entropoid-based cryptography is group exponentiation in disguise"

Danilo Gligoroski

Abstract

In the recent ePrint report 2021/583 titled "Entropoid-based cryptography is group exponentiation in disguise" Lorenz Panny gave a cryptanalysis of the entropoid based instances proposed in our eprint report 2021/469. We acknowledge the correctness of his claims for the concrete instances described in our original report 2021/469. However, we find that claims for the general applicability of his attack on the general Entropoid framework are misleading. Namely, based on the Theorem 1 in his report, which claims that for every entropic quasigroup $(G, *)$, there exists an Abelian group $(G, \cdot)$, commuting automorphisms $\sigma$, $\tau$ of $(G, \cdot)$, and an element $c \in G$, such that $x * y = \sigma(x) \cdot \tau(y) \cdot c$ the author infers that \emph{"all instantiations of the entropoid framework should be breakable in polynomial time on a quantum computer."} There are two misleading parts in these claim: \textbf{1.} It is implicitly assumed that all instantiations of the entropoid framework would define entropic quasigroups - thus fall within the range of algebraic objects addressed by Theorem 1. \emph{We will show a construction of entropic groupoids that are not quasigroups}; \textbf{2.} It is implicitly assumed that finding the group $(G, \cdot)$, the commuting automorphisms $\sigma$ and $\tau$ and the constant $c$ \emph{would be easy for every given entropic operation} $*$ and its underlying groupoid $(G, *)$. However, the provable existence of a mathematical object \emph{does not guarantee an easy finding} of that object. Treating the original entropic operation $* := *_1$ as a one-dimensional entropic operation, we construct multidimensional entropic operations $* := *_m$, for $m\geq 2$ and we show that newly constructed operations do not have the properties of $* = *_1$ that led to the recovery of the automorphism $\sigma$, the commutative operation $\cdot$ and the linear isomorphism $\iota$ and its inverse $\iota^{-1}$. We give proof-of-concept implementations in SageMath 9.2 for the new multidimensional entropic operations $* := *_m$ defined over several basic operations $* := *_1$ and we show how the non-associative and non-commutative exponentiation works for the key exchange and digital signature schemes originally proposed in report 2021/469.