Paper 2023/318

A Transformation for Lifting Discrete Logarithm Based Cryptography to Post-Quantum Cryptography

Danilo Gligoroski, Department of Information Security and Communication Technologies, Norwegian University of Science and Technology - NTNU
Abstract

We construct algebraic structures where rising to the non-associative power indices is no longer tied with the Discrete Logarithm Problem but with a problem that has been analysed in the last two decades and does not have a quantum polynomial algorithm that solves it. The problem is called Exponential Congruences Problem. By this, \emph{we disprove} the claims presented in the ePrint report 2021/583 titled "Entropoids: Groups in Disguise" by Lorenz Panny that \emph{"all instantiations of the entropoid framework should be breakable in polynomial time on a quantum computer."} Additionally, we construct an Arithmetic for power indices and propose generic recipe guidelines that we call "Entropic-Lift" for transforming some of the existing classical cryptographic schemes that depend on the hardness of Discrete Logarithm Problem to post-quantum cryptographic schemes that will base their security on the hardness of the Exponential Congruences Problem. As concrete examples, we show how to transform the classical Diffie-Hellman key exchange, DSA and Schnorr signature schemes. We also post one open problem: From the perspective of provable security, specifically from the standpoint of security of post-quantum cryptographic schemes, to precisely formalize and analyze the potentials and limits of the Entropic-Lift transformation.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Post-Quantum CryptographyEntropoid-based CryptographyEntropic-Lift
Contact author(s)
DANILOG @ ntnu no
History
2023-03-03: approved
2023-03-03: received
See all versions
Short URL
https://ia.cr/2023/318
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/318,
      author = {Danilo Gligoroski},
      title = {A Transformation for Lifting Discrete Logarithm Based Cryptography to Post-Quantum Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2023/318},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/318}},
      url = {https://eprint.iacr.org/2023/318}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.