Description
The Polynomial Modular Number System (PMNS) is an integer number system that aims to speed up arithmetic operations modulo a prime number p. This system is defined by a tuple (p, n, g, r, E), where p, n, g and r are positive integers, and E is a polynomial with integer coefficients, having g as a root modulo p.
Arithmetic operations in PMNS rely heavily on Euclidean lattices. Modular reduction in this system is done using a lattice of zeros L (here, the set of polynomials in Z[X], with degrees smaller than n, having g as a root modulo p).
Many works have shown that the PMNS can be an efficient alternative to the classical representation for modular arithmetic and cryptographic size integers.
In this presentation, we first present the PMNS and its arithmetic. Next, we introduce new properties of the lattice L, regarding a Montgomery-like coefficient reduction method. Then, we study the redundancy in the PMNS and explain how to choose the parameters for the desired redundancy in the system. Finally, we show how to use some properties of Euclidean lattices for efficient modular arithmetic and equality test within the PMNS.
Reference: F. Y. Dosso, A. Berzati, N. El Mrabet, and J. Proy. PMNS revisited for consistent redundancy and equality test. Cryptology ePrint Archive, Paper 2023/1231, (\url{https://eprint.iacr.org/2023/1231})
Infos pratiques
Prochains exposés
-
Predicting Module-Lattice Reduction
Orateur : Paola de Perthuis - CWI
Is module-lattice reduction better than unstructured lattice reduction? This question was highlighted as `Q8' in the Kyber NIST standardization submission (Avanzi et al., 2021), as potentially affecting the concrete security of Kyber and other module-lattice-based schemes. Foundational works on module-lattice reduction (Lee, Pellet-Mary, Stehlé, and Wallet, ASIACRYPT 2019; Mukherjee and Stephens[…]-
Cryptography
-
-
Séminaire C2 à INRIA Paris
Emmanuel Thomé et Pierrick Gaudry Rachelle Heim Boissier Épiphane Nouetowa Dung Bui Plus d'infos sur https://seminaire-c2.inria.fr/ -
Attacking the Supersingular Isogeny Problem: From the Delfs–Galbraith algorithm to oriented graphs
Orateur : Arthur Herlédan Le Merdy - COSIC, KU Leuven
The threat of quantum computers motivates the introduction of new hard problems for cryptography.One promising candidate is the Isogeny problem: given two elliptic curves, compute a “nice’’ map between them, called an isogeny.In this talk, we study classical attacks on this problem, specialised to supersingular elliptic curves, on which the security of current isogeny-based cryptography relies. In[…]-
Cryptography
-