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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
entropoidentropic
Contact author(s)
danilog @ ntnu no
History
2021-07-01: received
Short URL
https://ia.cr/2021/896
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/896,
      author = {Danilo Gligoroski},
      title = {Rebuttal to claims in Section 2.1 of the ePrint report 2021/583 "Entropoid-based cryptography is group exponentiation in disguise"},
      howpublished = {Cryptology ePrint Archive, Paper 2021/896},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/896}},
      url = {https://eprint.iacr.org/2021/896}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.