Description
The Naccache-Stern (NS) knapsack cryptosystem is a little-known public-key encryption scheme, despite (or because of) its original design. In this scheme, the ciphertext is obtained by multiplying the public-keys indexed by the message bits modulo a prime p. The cleartext is then recovered by factoring the ciphertext raised to a secret power modulo p.<br/> NS encryption requires a multiplication per two plaintext bits on the average, while decryption is roughly as costly as an RSA decryption. However, NS features a bandwidth sublinear in log(p), namely log(p)/log(log(p)).<br/> This presentation presents new NS variants allowing to reach bandwidths linear in log(p). The price to pay for reaching a linear bandwidth is a public-key of size log3(p)/log(log(p)). Beyond their mathematical interest, these modifications can possibly make the NS knapsack cryptosystem more practical and attractive. The presentation will be held in French, and will be self-included as much as possible.<br/> This is a joint work with David Naccache (U. Paris II, ENS) and Jacques Stern (ENS) .
Next sessions
-
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
Speaker : 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
-