Description
On construit trois systèmes de cryptographie basés sur le problème NP-complet du sac à dos. Les constructions standard cachent des instances faciles du problème du sac à dos et ont été cassées. Les systèmes présentés ici sont plus surs car ils cachent des instances quelconques ( éventuellement difficiles ). On donnera des résultats de complexité ( taille de la clé, temps d'encodage et de décodage...) et des résultats expérimentaux. Des résultats de sécurité théorique sont également donnés. Une réduction probabiliste polynômiale montre qu'il est aussi difficile de trouver la clé que de factoriser un produit de deux nombres premiers. La densité du sac à dos peut être choisie arbitrairement proche de 1, évitant les attaques par faible densité. Enfin, les attaques heuristiques par LLL ne sont pas opératoires car la clé publique est aussi sure qu'une clé aléatoire relativement à ce type d'attaques.
Next sessions
-
Computational assumptions in the quantum world
Speaker : Alex Bredariol Grilo - LIP6 (CNRS / Sorbonne Université)
QKD is a landmark of how quantum resources allow us to implement cryptographicfunctionalities with a level of security that is not achievable only with classical resources.However, key agreement is not sufficient to implement all functionalities of interest, and it iswell-known that they cannot be implemented with perfect security, even if we have accessto quantum resources. Thus, computational[…]-
Cryptography
-
-
Polytopes in the Fiat-Shamir with Aborts Paradigm
Speaker : Hugo Beguinet - ENS Paris / Thales
The Fiat-Shamir with Aborts paradigm (FSwA) uses rejection sampling to remove a secret’s dependency on a given source distribution. Recent results revealed that unlike the uniform distribution in the hypercube, both the continuous Gaussian and the uniform distribution within the hypersphere minimise the rejection rate and the size of the proof of knowledge. However, in practice both these[…]-
Cryptography
-
Asymmetric primitive
-
Mode and protocol
-
-
Post-quantum Group-based Cryptography
Speaker : Delaram Kahrobaei - The City University of New York