Cryptology ePrint Archive: Report 2020/1102

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

Pedro Hecht

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.

Category / Keywords: cryptographic protocols / Post-quantum cryptography, finite fields, rings, combinatorial group theory, R-propping, public-key cryptography, non-commutative cryptography, AES.

Date: received 12 Sep 2020, last revised 15 Sep 2020

Contact author: qubit101 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200915:212609 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]