PMNS revisited for consistent redundancy and equality test

Fangan Yssouf Dosso; Alexandre Berzati; Nadia El Mrabet; Julien Proy

Paper 2023/1231

PMNS revisited for consistent redundancy and equality test

Fangan Yssouf Dosso, SAS laboratory, École des Mines de Saint-Étienne, Gardanne, France

Alexandre Berzati, Thales DIS, Meyreuil, France

Nadia El Mrabet, SAS laboratory, École des Mines de Saint-Étienne, Gardanne, France

Julien Proy, Thales DIS, Meyreuil, France

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, γ, ρ, E)$ , where $p$ , $n$ , $γ$ and $ρ$ are positive non-zero integers and $E \in Z_{n} [X]$ is a monic polynomial such that $E (γ) \equiv 0 (\mod 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 by 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Modular arithmetic Polynomial modular number system Internal reduction Euclidean lattices Redundancy Equality test
Contact author(s): fanganyssouf dosso @ emse fr
alexandre berzati @ thalesgroup com
nadia el-mrabet @ emse fr
julien proy @ thalesgroup com
History: 2023-09-01: revised; 2023-08-14: received; See all versions
Short URL: https://ia.cr/2023/1231
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1231,
      author = {Fangan Yssouf Dosso and Alexandre Berzati and Nadia El Mrabet and Julien Proy},
      title = {{PMNS} revisited for consistent redundancy and equality test},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1231},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1231}
}