# Canal-U

Mon compte

## 2.2. Security-Reduction Proof

Copier le code pour partager la vidéo :
<div style="position:relative;padding-bottom:56.25%;padding-top:10px;height:0;overflow:hidden;"><iframe src="https://www.canal-u.tv/video/inria/embed.1/2_2_security_reduction_proof.32825?width=100%&amp;height=100%" style="position:absolute;top:0;left:0;width:100%;height: 100%;" width="550" height="306" frameborder="0" allowfullscreen scrolling="no"></iframe></div> Si vous souhaitez partager une séquence, indiquez le début de celle-ci , et copiez le code : h m s
Contacter la chaine
J’aime
Imprimer
partager

### 2.2. Security-Reduction Proof

Welcome to the second session. We will talk about the security-reduction proof. The security of a given cryptographic algorithm is reduced to the security of a known hard problem. To prove that a cryptosystem is secure, we select a problem which we know is hard to solve, and we reduce the problem to the security of the cryptosystem. Since the problem is hard to solve, the cryptosystem is hard to break. A security reduction is a proof that an adversary able to attack the scheme is able to solve some presumably hard computational problem, with a similar effort. For the given parameters n, k, let G be the public-key space, K be the apparent public-key space. In the original McEliece scheme G is the set of all generator matrices of a family of binary Goppa codes of length n and dimension k. K is the set of binary matrices of a size (k x n). A distinguisher is a mapping that takes as input a binary matrix of size (k x n), and returns true if the matrix is distinguishable. We define the following sample space, the set of all matrices of size (k x n) uniformly distributed, and we define the event: the set of binary matrices such that the distinguisher returns true, that is the matrices which are distinguishable.
The advantage of a distinguisher for the subset D, measures how such a distinguisher could be used as a characterization for G; formally, the probability that the event will occur, minus the probability that the   event happens restricted to the subset G. In other words, it is the probability that the distinguisher detects a matrix from G, from a randomly picked up binary matrix. We will denote the running time of a distinguisher by this formula. An algorithm is a (T, ε)-distinguisher for G against K, if it runs in time at most T, and the advantage for G is greater than ε. So, for given parameters n, k and t, we define this, the message space, this, the apparent public key space, and W the error vector space.

•
Label UNT : UNIT
•
Date de réalisation : 5 Mai 2015
Durée du programme : 5 min
Classification Dewey : Analyse numérique, Théorie de l'information, données dans les systèmes informatiques, cryptographie, Mathématiques
•
Catégorie : Vidéocours
Niveau : niveau Master (LMD), niveau Doctorat (LMD), Recherche
Disciplines : Mathématiques, Informatique, Informatique, Mathématiques et informatique
Collections : 2: McEliece Cryptosystem
ficheLom : Voir la fiche LOM
•
Auteur(s) : MARQUEZ-CORBELLA Irene, SENDRIER Nicolas, FINIASZ Matthieu
•
Langue : Anglais
Mots-clés : algèbre linéaire, chiffrement à clé publique, cryptage des données, cryptographie, McEliece, LDPC, MDPC
Conditions d’utilisation / Copyright : 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.

## commentaires

Ajouter un commentaire Lire les commentaires
*Les champs suivis d’un astérisque sont obligatoires.
Aucun commentaire sur cette vidéo pour le moment (les commentaires font l’objet d’une modération)