Paper 2023/1231 Original: eprint.iacr.org/2023/1231 ↗

Redundancy and equality test in the PMNS, application to Elliptic Curve Diffie–Hellman

Abstract

The Polynomial Modular Number System (PMNS) is a non-positional number system for modular arithmetic. A PMNS is defined by a tuple $(p, n, \gamma, \rho, E)$, where $p$, $n$, $\gamma$ and $\rho$ are positive non-zero integers and $E\in\mathbb{Z}_{n}[X]$ is a monic polynomial such that $E(\gamma) \equiv 0 \pmod p$. The PMNS is a redundant number system. This redundancy property has already been used to randomise the data during the Elliptic Curve Scalar Multiplication (ECSM). In this paper, we refine the results on redundancy and propose several new results on PMNS. More precisely, we study a generalisation of the Montgomery-like internal reduction method proposed Negre and Plantard, along with some improvements on parameter bounds for smaller memory cost to represent elements in this system. We also show how to perform equality test in the PMNS. This open problem has been a limitation for the use of PMNS in cryptography. Finally, as an application, we show the use of the Elliptic Curve Diffie Hellman key agreement protocol with PMNS, without needing another number system. We also provide SageMath and C implementations. We make some comparisons with the OpenSSL library.