Table of contents

  • This session has been presented March 21, 2008.

Description

  • Speaker

    Benoit Chevallier-Mames - DCSSI

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

  • Random lattices that are modules over the ring of integers

    • May 22, 2026 (13:45 - 15:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Nihar Gargava - Institut de Mathématiques d'Orsay

    We investigate the average number of lattice points within a ball where the lattice is chosen at random from the set of unit determinant ideal or modules lattices of some cyclotomic number field. The goal is to consider the space of such lattice as a probabilistic space and then study the distribution of lattice point counts. This is inspired by the connections of this problem to lattice-based[…]

    • Cryptography

  • Schéma de signature à clé publique : Frobénius-UOV

    • May 29, 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Gilles Macario-Rat - Orange

    L'exposé présente un schéma de signature à clé publique post-quantique inspiré du schéma UOV et introduisant un nouvel outil : les formes de Frobénius. L'accent est mis sur le rôle et les propriétés des formes de Frobénius dans ce nouveau schéma : la simplicité de description, la facilité de mise en oeuvre et le gain inédit sur les tailles de signature et de clé qui bat RSA-2048 au niveau de[…]

  • Yoyo tricks with a BEANIE

    • June 05, 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Speaker : Xavier Bonnetain - Inria

    TBD

    • Cryptography

    • Symmetrical primitive

Show previous sessions
Page top