Vidéo pédagogique
Notice
Sous-titrage
Anglais
Langue :
Anglais
Crédits
Irene Marquez-Corbella (Intervention), Nicolas Sendrier (Intervention), Matthieu Finiasz (Intervention)
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
DOI : 10.60527/8jqq-zz89
Citer cette ressource :
Irene Marquez-Corbella, Nicolas Sendrier, Matthieu Finiasz. Inria. (2015, 5 mai). 5.6. An Efficient Provably Secure One-Way Function , in 5: Other cryptographic constructions relying on coding theory. [Vidéo]. Canal-U. https://doi.org/10.60527/8jqq-zz89. (Consultée le 15 mai 2025)
logo Inria
Inria - Institut national de recherche en sciences et technologies du numérique
S'abonner
Contacter

5.6. An Efficient Provably Secure One-Way Function

Réalisation : 5 mai 2015 - Mise en ligne : 21 février 2017
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

In this session, we aregoing to see how to build an efficient provably secureone-way function from coding theory. As you know, a one-wayfunction is a function which is simple to evaluate andwhich should be as fast as possible and hard to invert,ideally with good security arguments. There are manyapplications of one-way functions, especially in symmetriccryptography. For example, for compression functions tobuild hash functions, expansion functions to build pseudorandomnumber generators but many more. Unfortunately, one-wayfunctions are hard to build. We know some very fastfunctions which have very few security arguments and wehave some very strong security arguments forfunctions which are very slow. What we will try to do is toget a fast and secure function. Niederreiter Encryption is agood candidate for one-way function. Any public key encryptionscheme is a one-way function with a trapdoor, whichis the decryption key. It has very strong securityarguments usually a proof of security. But public keyencryption is usually very slow, especially if you takeconstruction from numbers theory, you require an expentiationwhich is expensive to compute. Niederreiter Encryption is muchfaster than other public key schemes. It simply converts theinput into a low weight word. There are many differenttechniques to do this and then compute its syndrome whichis only a few XORs, especially if the weight is very small.  The trapdoor can be easilyremoved by simply using a random binary matrix whichis enough when we don't need to invert this one-way function. And with a few tweaks, itcan be made even faster than the usual Niederreiter Encryption. Here, we will give an overview ofthe one-way function we are building. The parameters are matrix Hof size r*n and the constant weight encoding function φwhich takes l bits and output a word of weight w and length n. The one-way function simplytakes an input x and computes φ(x) and multiplies it byH to obtain a value, a syndrome y. Security ofthis function: inverting the function requires tosolve an instance of syndrome decoding; and efficiency:if φ is fast and w is small, then the functioncan be very efficient.

Intervention
Thème
Disciplines :
Documentation
Support de présentation au format PDF

Dans la même collection

Voir tout

Avec les mêmes intervenants et intervenantes

Sur le même thème