<?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>32871</entry>
</identifier>
<title><string language="fre"><![CDATA[3.2. Combinatorial Solutions: Exhaustive Search and Birthday Decoding]]></string></title>
<language>ENG</language>
<description>
<string language="fre"><![CDATA[In this session, I will
detail two combinatorial solutions to the decoding problem. The first one is
the Exhaustive Search. To find our w columns,
we will simply enumerate all the tuples j1 to
jw and check whether the corresponding column
plus the syndrome is equal to zero modulo 2. In detail
here is how we will do. We have w loops enumerating the indices from j1 to jw, and in the innermost loop,
we add the w columns plus the syndrome and
either we test the value of the syndrome or we store it
depending on what is our need. The cost of this
algorithm is at most w(n,w) column additions plus a
certain number of tests. In practice, the cost
for the test is negligible and we will just ignore
that term, and we have this cost for the algorithm. But we can do better. Instead, we may keep
track of partial sums. In the first loop, line 1,
we add the syndrome to the first column. In the
second loop, we add the first partial sum to the second column. We obtain a second partial
sum and so on until, in the inner loop, we add the
previous partial sum to the last column. If we do
this, since each line i is executed (n,i)
times, we have a total of column additions
which is given here. And this cost is
dominated by (n,w), when w is not too large. So, the
total cost for the Exhaustive Search is (n,w) column operations. And for that cost, we obtain
all the solutions to our problem. We can do better with
the Birthday Decoding. In this algorithm, we
split the matrix into two equal parts and we will
enumerate all solutions by enumerating those two
lists using error pattern of weight w/2. If the
intersection of those two lists is not empty, then we have
a solution to our problem.
Here is the algorithm. We first enumerate all
errors of weight w/2, compute the syndrome and store each of the computed values. This
will cost (n/2,w/2), that is the size of the first list. At this point, we may check the intersection of the
two lists, L1 and L2. This last part of the
algorithm will cost (L1 * L2)/2 to the size of the syndrome. Coming back to the
Birthday Decoding slide, the cost of the above
enumeration will be given by the
formula here with binomial
coefficient which can also be written as 2L + (L²/2^(n-k)) where L is the size common to the two lists. To measure the exact
complexity of this algorithm, we have to take into account
that an error pattern of weight w splits evenly between the
two halves of the matrix with a probability P which
may be smaller than one.]]></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:2021-07-06 18:02:27
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:27
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:27
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_2_combinatorial_solutions_exhaustive_search_and_birthday_decoding.32871]]></location>
<location><![CDATA[https://streaming-canal-u.fmsh.fr/vod/media/canalu/videos/fuscia/3.2.combinatorial.solutions.exhaustive.search.and.birthday.decoding_32871/c015im.w3.s2.mov]]></location>
<size>138168873</size>
<duration><duration>PT0H5M17S</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>