Paper 2021/469
Entropoid Based Cryptography
Danilo Gligoroski
Abstract
The algebraic structures that are noncommutative and nonassociative known as entropic groupoids that satisfy the "Palintropic" property i.e., $x^{\mathbf{A} \mathbf{B}} = (x^{\mathbf{A}})^{\mathbf{B}} = (x^{\mathbf{B}})^{\mathbf{A}} = x^{\mathbf{B} \mathbf{A}}$ were proposed by Etherington in '40s from the 20th century. Those relations are exactly the DiffieHellman key exchange protocol relations used with groups. The arithmetic for nonassociative power indices known as Logarithmetic was also proposed by Etherington and later developed by others in the 50s70s. However, as far as we know, no one has ever proposed a succinct notation for exponentially large nonassociative power indices that will have the property of fast exponentiation similarly as the fast exponentiation is achieved with ordinary arithmetic via the consecutive rising to the powers of two. In this paper, we define ringoid algebraic structures $(G, \boxplus, *)$ where $(G, \boxplus) $ is an Abelian group and $(G, *)$ is a noncommutative and nonassociative groupoid with an entropic and palintropic subgroupoid which is a quasigroup, and we name those structures as Entropoids. We further define succinct notation for nonassociative bracketing patterns and propose algorithms for fast exponentiation with those patterns. Next, by an analogy with the developed cryptographic theory of discrete logarithm problems, we define several hard problems in Entropoid based cryptography, such as Discrete Entropoid Logarithm Problem (DELP), Computational Entropoid DiffieHellman problem (CEDHP), and Decisional Entropoid DiffieHellman Problem (DEDHP). We post a conjecture that DEDHP is hard in Sylow $q$subquasigroups. Next, we instantiate an entropoid DiffieHellman key exchange protocol. Due to the noncommutativity and nonassociativity, the entropoid based cryptographic primitives are supposed to be resistant to quantum algorithms. At the same time, due to the proposed succinct notation for the power indices, the communication overhead in the entropoid based DiffieHellman key exchange is very low: for 128 bits of security, 64 bytes in total are communicated in both directions, and for 256 bits of security, 128 bytes in total are communicated in both directions. Our final contribution is in proposing two entropoid based digital signature schemes. The schemes are constructed with the FiatShamir transformation of an identification scheme which security relies on a new hardness assumption: computing roots in finite entropoids is hard. If this assumption withstands the time's test, the first proposed signature scheme has excellent properties: for the classical security levels between 128 and 256 bits, the public and private key sizes are between 32 and 64, and the signature sizes are between 64 and 128 bytes. The second signature scheme reduces the finding of the roots in finite entropoids to computing discrete entropoid logarithms. In our opinion, this is a safer but more conservative design, and it pays the price in doubling the key sizes and the signature sizes. We give a proofofconcept implementation in SageMath 9.2 for all proposed algorithms and schemes in an appendix.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 Postquantum cryptographyDiscrete Logarithm ProblemDiffieHellman key exchangeentropicEntropoidEntropoid Based Cryptography
 Contact author(s)
 danilog @ ntnu no
 History
 20210412: received
 Short URL
 https://ia.cr/2021/469
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/469, author = {Danilo Gligoroski}, title = {Entropoid Based Cryptography}, howpublished = {Cryptology ePrint Archive, Paper 2021/469}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/469}}, url = {https://eprint.iacr.org/2021/469} }