A New Public Key Encryption Scheme Based on the Cubic Pell Curve
Using Encoding Functions
Abderrahmane Nitaj\,^1 and Michel Seck\,^2
\,^{1}Normandie Univ, UNICAEN, CNRS, LMNO, 14000 Caen, France
\,^{2}Ecole Polytechnique de Thies, LTISI, Senegal.
Pages 90-108 | Received 20 October 2024, Accepted 19 December 2024, Published 10 July 2025
Abstract
RSA is a public key encryption scheme introduced by Rivest, Shamir, and Adleman in 1978. Its security relies on the difficulty of factoring an integer N=pq which is the product of two large prime numbers p and q. In 2018, Murru and Saettone proposed a variant of RSA, based on the cubic Pell curve with a modulus of the same form. Recently, Seck and Nitaj extended the scheme of Murru and Saettone to a prime power modulus of the form N=p^rq^s where the ciphertexts C are represented as elements of \mathbb{Z}/N\mathbb{Z}\times \mathbb{Z}/N\mathbb{Z} \times \mathbb{Z}/N\mathbb{Z}, with a size of 3\log_2(N). In addition to the difficulty of factoring composite integers, the security of the scheme of Seck and Nitaj is based on Rabin’s trapdoor one-way function. In this paper, we propose a new variant of the scheme of Seck and Nitaj where the ciphertext size is reduced to a size 2\log_2(N) instead of 3\log_2(N) for a fixed modulus N. This achievement is made possible through the incorporation of encoding and compression functions.
Keywords: Public Key Cryptography, cubic Pell curve, RSA variants, Encoding functions.
MSC numbers: Primary 94A60.
Downloads: Full-text PDF