<?xml version="1.0" encoding="UTF-8"?><lom xmlns="http://ltsc.ieee.org/xsd/LOM" xmlns:lomfr="http://www.lom-fr.fr/xsd/LOMFR" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://ltsc.ieee.org/xsd/LOM http://www.lom-fr.fr/xsd/lomfrv1.0/std/lomfr.xsd">
<general>
<identifier>
<catalog>Canal-U_Ocms</catalog>
<entry>32937</entry>
</identifier>
<title><string language="fre"><![CDATA[4.4. Attack against subcodes of GRS codes]]></string></title>
<language>ENG</language>
<description>
<string language="fre"><![CDATA[In this session, we will
talk about using subcodes of a Generalized Reed–Solomon code
for the McEliece Cryptosystem. Recall that to avoid the
attack of Sidelnikov and Shestakov, Berger and
Loidreau proposed to replace Generalized Reed–Solomon
codes by some random subcodes of small codimension.
However, this attack has been broken by Wieschebrink in 2006
using square code considerations. The idea of the
attack is very simple.
The public key is a subcode
of large dimension, otherwise a generic attack could be applied. And we also know the
error-correcting capacity of the Generalized Reed–Solomon code. With high probability, the
square of this subcode is again a Generalized
Reed–Solomon code of maximal dimension. Thus, we just need to apply
Sidelnikov and Shestakov to retrieve the code locator
and the column multiplier. And thus, we have an efficient
decoding algorithm for the Generalized Reed–Solomon
code, which is also a decoding algorithm for the chosen subcode. We correct up to t errors. But what happens if the
square code is the whole space? Then, a similar attack could
be applied but to a shortened code. Recall the definition
of a shortened code. First of all, some notations. The process of
deleting columns from a parity-check matrix of a linear code
is known as shortening. In other words, the
shortened code, at the J-locations, is the set of codewords that
have a zero in the J-locations restricted to the coordinates
indexed by the relative complement of J. In a simple way, suppose
that we have a generator matrix and we have the identity at the
beginning of its first J-columns. Then, a basis of the
shortened code can be easily
obtained by extracting the
components that we indicate in the figure, that is by extracting
these columns of the generator matrix. Generalized Reed–Solomon
codes behave specially with the shortening operation.
Since we have that the shortened of a Generalized
Reed–Solomon code is again a Generalized Reed–Solomon code. To simplify the proof, we
will just shortened the first position, but the generalization to
other positions is straightforward. So, let G be a matrix of a
Generalized Reed–Solomon code of dimension k
associated to the pair (a,b). We labelled its rows by 
g1, g2, … , gk. We apply Gauss elimination to
get a matrix of the following form. Then, this sub-matrix is
a generator matrix for the shortened code at the first position.]]></string></description>
<keyword><string language="fre"><![CDATA[algèbre linéaire]]></string></keyword><keyword><string language="fre"><![CDATA[chiffrement à clé publique]]></string></keyword><keyword><string language="fre"><![CDATA[cryptage des données]]></string></keyword><keyword><string language="fre"><![CDATA[cryptographie]]></string></keyword><keyword><string language="fre"><![CDATA[code correcteur]]></string></keyword><keyword><string language="fre"><![CDATA[algorithmes]]></string></keyword><keyword><string language="fre"><![CDATA[GRS code]]></string></keyword>
<lomfr:documentType>
<lomfr:source>LOMFRv1.0</lomfr:source>
<lomfr:value>image en mouvement</lomfr:value>
</lomfr:documentType>
</general><lifeCycle>
<contribute>
<role>
<source>LOMv1.0</source>
<value>author</value>
</role>
<entity><![CDATA[BEGIN:VCARD
VERSION:3.0
CLASS:PUBLIC
REV:2021-07-06 18:02:49
FN:Irene MARQUEZ-CORBELLA
N:MARQUEZ-CORBELLA;Irene;;;
URL;TYPE=work:https://www.canal-u.tv/auteurs/marquez_corbella_irene
ROLE:author
TZ:+0200
END:VCARD
]]></entity>
<date><dateTime>2015-05-05</dateTime></date>
</contribute>
<contribute>
<role>
<source>LOMv1.0</source>
<value>author</value>
</role>
<entity><![CDATA[BEGIN:VCARD
VERSION:3.0
CLASS:PUBLIC
REV:2021-07-06 18:02:49
FN:Nicolas SENDRIER
N:SENDRIER;Nicolas;;;
URL;TYPE=work:https://www.canal-u.tv/auteurs/sendrier_nicolas
ROLE:author
TZ:+0200
END:VCARD
]]></entity>
<date><dateTime>2015-05-05</dateTime></date>
</contribute>
<contribute>
<role>
<source>LOMv1.0</source>
<value>author</value>
</role>
<entity><![CDATA[BEGIN:VCARD
VERSION:3.0
CLASS:PUBLIC
REV:2021-07-06 18:02:49
FN:Matthieu FINIASZ
N:FINIASZ;Matthieu;;;
URL;TYPE=work:https://www.canal-u.tv/auteurs/finiasz_matthieu
ROLE:author
TZ:+0200
END:VCARD
]]></entity>
<date><dateTime>2015-05-05</dateTime></date>
</contribute>
</lifeCycle>
<metaMetadata>
<metadataSchema>LOMv1.0</metadataSchema>
<metadataSchema>LOMFRv1.0</metadataSchema>
</metaMetadata>
<technical>
<format>video/mp4</format>
<location><![CDATA[https://www.canal-u.tv/video/inria/4_4_attack_against_subcodes_of_grs_codes.32937]]></location>
<location><![CDATA[https://streaming-canal-u.fmsh.fr/vod/media/canalu/videos/fuscia/4.4.attack.against.subcodes.of.grs.codes_32937/c015im.w4.s4.mov]]></location>
<size>99866431</size>
<duration><duration>PT0H3M57S</duration></duration>
</technical>
<educational>
<learningResourceType>
<source>LOMv1.0</source>
<value>lecture</value>
</learningResourceType>
<context>
<source>LOMv1.0</source>
<value>master</value>
</context>
<context>
<source>LOMv1.0</source>
<value>doctorat</value>
</context>
</educational>
<rights>
<cost>
<source>LOMv1.0</source>
<value>no</value>
</cost>
<copyrightAndOtherRestrictions>
<source>LOMv1.0</source>
<value>no</value>
</copyrightAndOtherRestrictions>
<description>
<string language="fre"><![CDATA[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.]]></string>
</description>
</rights>
<relation>
<kind>
<source>LOMv1.0</source>
<value>ispartof</value>
</kind>
<resource>
<identifier>
<catalog>URI</catalog>
<entry>https://www.canal-u.tv/producteurs/inria/cours_en_ligne/code_based_cryptography/4_key_attacks</entry>
</identifier>
<description>
<string language="fre"><![CDATA[4: Key Attacks]]></string>
</description>
</resource>
</relation>
<classification>
<purpose>
<source>LOMv1.0</source>
<value>discipline</value>
</purpose>
<taxonPath>
<source>
<string language="fre"><![CDATA[Universités Numériques Thématiques 2009 http://www.universites-numeriques.fr]]></string>
</source>
<taxon>
<id/>
<entry>
<string language="fre"/>
</entry>
</taxon>
</taxonPath>
</classification>
<classification>
<purpose>
<source>LOMv1.0</source>
<value>discipline</value>
</purpose>
<taxonPath>
<source>
<string language="fre">CDD 22e éd.</string>
<string language="eng">DDC 22nd ed.</string>
</source>
<taxon>
<id>518</id>
<entry>
<string language="fre"><![CDATA[Analyse numérique]]></string>
</entry>
</taxon>
</taxonPath>
<taxonPath>
<source>
<string language="fre">CDD 22e éd.</string>
<string language="eng">DDC 22nd ed.</string>
</source>
<taxon>
<id>003.54</id>
<entry>
<string language="fre"><![CDATA[Théorie de l'information]]></string>
</entry>
</taxon>
</taxonPath>
<taxonPath>
<source>
<string language="fre">CDD 22e éd.</string>
<string language="eng">DDC 22nd ed.</string>
</source>
<taxon>
<id>005.7</id>
<entry>
<string language="fre"><![CDATA[données dans les systèmes informatiques]]></string>
</entry>
</taxon>
</taxonPath>
<taxonPath>
<source>
<string language="fre">CDD 22e éd.</string>
<string language="eng">DDC 22nd ed.</string>
</source>
<taxon>
<id>652.8</id>
<entry>
<string language="fre"><![CDATA[cryptographie]]></string>
</entry>
</taxon>
</taxonPath>
<taxonPath>
<source>
<string language="fre">CDD 22e éd.</string>
<string language="eng">DDC 22nd ed.</string>
</source>
<taxon>
<id>510</id>
<entry>
<string language="fre"><![CDATA[Mathématiques]]></string>
</entry>
</taxon>
</taxonPath>
</classification> </lom>