Paper 2020/1102

PQC: R-Propping of Public-Key Cryptosystems Using Polynomials over Non-commutative Algebraic Extension Rings

Pedro Hecht, University of Buenos Aires, Argentina
Abstract

Post-quantum cryptography (PQC) is a trend that has a deserved NIST status, and which aims to be resistant to quantum computers attacks like Shor and Grover algorithms. In this paper, we propose a method for designing post-quantum provable IND-CPA/IND-CCA2 public key cryptosystems based on polynomials over a non-commutative algebraic extension ring. The key ideas of our proposal is that (a) for a given non-commutative ring of rank-3 tensors, we can define polynomials and take them as the underlying work structure (b) we replace all numeric field arithmetic with GF(2^8) field operations. By doing so, it is easy to implement R-propped Diffie-Helman-like key exchange protocol and consequently ElGamal-like cryptosystems. Here R stands for Rijndael as we work over the AES field. This approach yields secure post-quantum protocols since the resulting multiplicative monoid is immune against quantum algorithms and resist classical linearization attacks like Tsaban’s Algebraic Span or Roman’kov. The protocols have been proved to be semantically secure. Finally, we present numerical examples of the proposed R-Propped protocols.

Note: Corrected source code

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Post-quantum cryptography finite fields rings combinatorial group theory R-propping public-key cryptography non-commutative cryptography AES.
Contact author(s)
phecht @ dc uba ar
History
2022-07-04: last of 2 revisions
2020-09-15: received
See all versions
Short URL
https://ia.cr/2020/1102
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1102,
      author = {Pedro Hecht},
      title = {PQC: R-Propping of Public-Key Cryptosystems Using Polynomials over Non-commutative Algebraic Extension Rings},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1102},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1102}},
      url = {https://eprint.iacr.org/2020/1102}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.