<?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>32899</entry>
</identifier>
<title><string language="fre"><![CDATA[3.8. Becker, Joux, May, and Meurer Algorithm]]></string></title>
<language>ENG</language>
<description>
<string language="fre"><![CDATA[Now in session 8, we will
present yet another evolution of information set decoding. Before presenting this
improvement, we will first improve the Birthday Decoding
algorithm what I call a Further Improvement of Birthday Decoding. I will consider the
two following lists. The difference between
those two lists and those we had before is the + ? that you
can find in the weight of the errors e1 and e2. Those lists depend on
another parameter ?. What is the meaning
of that parameter? Well, the idea is the
following: if you add two words of weight w/2 and length n, you expect that you obtain a sum of weight w-(w²/2n). That is, in fact, that
you expect that those two words have w²/4n
non-zero positions in common. Now, if we shift things a little bit and if we
choose ? such that ? = (w/2+?)²/n, then two words of weight (w/2) + ? and length n are expected
to have ? non-zero positions in common and a sum of
weight w which is the target weight of our
syndrome decoding problem. Note that in addition
to the above property with a non-zero value
of ?, (w,w/2)*(n-w,?) different ways to write a
word of weight w, a word e, as a sum of two
error patterns e1 and e2 of weight (w/2)+?, that is, the
number of representation will increase. All of this together
allows us to give that claim. If we choose 2^r and ? as described here, then any
solution e to our problem is represented in the
intersection of the two sets above with the probability 1/2. And if we do that and
implement the Birthday Decoding with those two lists, the
workfactor will simplify, if I may say, into the following formula which is true up to
a polynomial factor. And, I'm not going to
explain why it is a polynomial factor now and rather
than a constant factor. Improving Birthday
Decoding has an impact on the May, Meurer and Thomae
algorithm we have just seen. Instead of the formula we
have here, in green, that is true up to a constant
factor, by using the Further Improved Birthday Decoding,
we could obtain this formula which is better for any
value of the parameter, which is true up to a polynomial factor. This idea and this
improvement is the embryo of the next improvement of
information set decoding. This improvement is due to
Becker, Joux, May and Meurer. And the idea is to let ?, that is the increase in the
weight of the half error patterns. We let ? grow beyond the optimal value
that is much beyond w²/4n. If we do that and the
workfactor of the Birthday Decoding becomes this formula with L equal to the list size and
2^r is the number of representative which is
given by the formula here. We may also write the
formula in the following form introducing the value ? which is the probability that
is described on the slide.]]></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[algorithmes]]></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:2022-04-04 16:50:57
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:2022-04-04 16:50:57
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:2022-04-04 16:50:57
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/3_8_becker_joux_may_and_meurer_algorithm.32899]]></location>
<location><![CDATA[https://streaming-canal-u.fmsh.fr/vod/media/canalu/videos/fuscia/3.8.becker.joux.may.and.meurer.algorithm_32899/c015im.w3.s8.mov]]></location>
<size>241595788</size>
<duration><duration>PT0H8M33S</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/3_message_attacks_isd</entry>
</identifier>
<description>
<string language="fre"><![CDATA[3: Message Attacks (ISD)]]></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>