Ressource en auto-formation : 5.6. An Efficient Provably Secure One-Way Function

In this session, we are going to see how to build an efficient provably secure one-way function from coding theory. As you know, a one-way function is a function which is simple to evaluate and which should be as fast as possible and hard to invert, ideally with good security arguments. There are ma...
cours / présentation - Création : 05-05-2015
Par : Irene MARQUEZ-CORBELLA, Nicolas SENDRIER, Matthieu FINIASZ
Partagez !

Présentation de: 5.6. An Efficient Provably Secure One-Way Function

Informations pratiques sur cette ressource

Langue du document : Anglais
Type : cours / présentation
Niveau : master, doctorat
Durée d'exécution : 5 minutes 21 secondes
Contenu : vidéo
Document : video/mp4
Poids : 135.34 Mo
Droits d'auteur : libre de droits, gratuit
Droits réservés à l'éditeur et aux auteurs. 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.

Description de la ressource en auto-formation

Résumé

In this session, we are going to see how to build an efficient provably secure one-way function from coding theory. As you know, a one-way function is a function which is simple to evaluate and which should be as fast as possible and hard to invert, ideally with good security arguments. There are many applications of one-way functions, especially in symmetric cryptography. For example, for compression functions to build hash functions, expansion functions to build pseudorandom number generators but many more. Unfortunately, one-way functions are hard to build. We know some very fast functions which have very few security arguments and we have some very strong security arguments for functions which are very slow. What we will try to do is to get a fast and secure function. Niederreiter Encryption is a good candidate for one-way function. Any public key encryption scheme is a one-way function with a trapdoor, which is the decryption key. It has very strong security arguments usually a proof of security. But public key encryption is usually very slow, especially if you take construction from numbers theory, you require an expentiation which is expensive to compute. Niederreiter Encryption is much faster than other public key schemes. It simply converts the input into a low weight word. There are many different techniques to do this and then compute its syndrome which is only a few XORs, especially if the weight is very small.  The trapdoor can be easily removed by simply using a random binary matrix which is enough when we don't need to invert this one-way function. And with a few tweaks, it can be made even faster than the usual Niederreiter Encryption. Here, we will give an overview of the one-way function we are building. The parameters are matrix H of 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 simply takes an input x and computes ?(x) and multiplies it by H to obtain a value, a syndrome y. Security of this function: inverting the function requires to solve an instance of syndrome decoding; and efficiency: if ? is fast and w is small, then the function can be very efficient.

"Domaine(s)" et indice(s) Dewey

  • Analyse numérique (518)
  • Théorie de l'information (003.54)
  • données dans les systèmes informatiques (005.7)
  • cryptographie (652.8)
  • Mathématiques (510)

Domaine(s)

Document(s) annexe(s) - 5.6. An Efficient Provably Secure One-Way Function

Partagez !

AUTEUR(S)

  • Irene MARQUEZ-CORBELLA
  • Nicolas SENDRIER
  • Matthieu FINIASZ

DIFFUSION

Cette ressource en auto-formation vous est proposée par :
Canal-U - accédez au site internet
Sur les réseaux sociaux :

EN SAVOIR PLUS

  • Identifiant de la fiche
    32989
  • Identifiant OAI-PMH
    oai:canal-u.fr:32989
  • Schéma de la métadonnée
  • Entrepôt d'origine
    Canal-U

Ressources en auto-formation sur les mêmes thèmes

Présentation de la ressource en auto-formation 5.1. Code-Based Digital Signatures cours / présentation
5.1. Code-Based Digital Signatures
Auteur(s) : MARQUEZ-CORBELLA Irene, SENDRIER Nicolas, FINIASZ Matthieu
Description : Welcome to the last week of this MOOC on code-based cryptography. This week, we will be discussing other cryptographic constructions relying on coding theory. We have seen how to do public key encryption and now we will see other kind of constructions. This first sequence we'll be having a look ...
Présentation de la ressource en auto-formation 5.2. The Courtois-Finiasz-Sendrier (CFS) Construction cours / présentation
5.2. The Courtois-Finiasz-Sendrier (CFS) Construction
Auteur(s) : MARQUEZ-CORBELLA Irene, SENDRIER Nicolas, FINIASZ Matthieu
Description : In this session, I am going to present the Courtois-Finiasz-Sendrier Construction of a code-based digital signature. In the previous session, we have seen that it is impossible to hash a document into decodable syndromes. But it is possible to hash onto the space of all syndromes. The document is ...