TD CRYPTOGRAPHIE BASÉE SUR LES CODES
Correction :
1. Supposons que pour communiquer une permutation ou un vecteur aléatoire, le Prouveur
envoie simplement une graine α de 100 bits permettant au Vérifieur de générer cette
permutation aléatoire à l’aide d’un générateur de pseudo-aléa.
On envoie toujours 3 × 160 bits pour c1 , c2 et c3 et 2 bits pour b.
Puis dans le premier cas on envoie α + k bits, dans le deuxième cas 2n bits et enfin dans le
al
troisième cas 2α bits. Soit en moyenne :
3α + 2n + k 2n + k
3 × 160 + 2 + = 482 + α + bits.
3 3
2. On a 482 + α + 2n+k
3 bits pour le schéma de Véron contre 482 + α + n bits pour Stern.
nti
Comme k < n, le protocole de Véron permet un coût de communication plus faible pour
un même niveau de sécurité.
3. On pourrait envoyer dans le cas b = 1 : φ−1 n
n,t (σ(e)) de ` = blog2 t c bits (< n) mais en
contrepartie le Vérifieur devra reconstruire σ(e) à partir de φ−1
n,t (σ(e)).
4. • Stratégie (a). Se préparer à répondre aux challenges b = 0 ou b = 1.
u← $
Fk2 , σ← $
Sn , e0 ←
$
Fn2 de poids de Hamming t,
c1 ← h(σ), c2 ← h(σ(uG)), c3 ← h(σ(uG ⊕ e0 )).
de
Pour b = 0, il divulgue σ et u au vérifieur V.
Pour b = 1, il divulgue σ(uG) et σ(e0 ) au vérifieur V.
Par contre, il ne peut pas répondre si b = 2.
• Stratégie (b). Se préparer à répondre aux challenges b = 0 ou b = 2.
u← $
Fk2 , σ← $
Sn , c1 ← h(σ), c2 ← h(σ(uG)), c3 ← h(σ(uG ⊕ c)).
Pour b = 0, il divulgue σ et u au vérifieur V.
Pour b = 2, il divulgue σ et u au vérifieur V.
nfi
Par contre, il ne peut pas répondre si b = 1.
• Stratégie (c). Se préparer à répondre aux challenges b = 1 ou b = 2.
u← $
Fk2 , σ←$
Sn , e0 ←
$
Fn2 de poids de Hamming t,
c1 ← h(σ), c2 ← h(σ(uG ⊕ c ⊕ e0 ))), c3 ← h(σ(uG ⊕ c)).
0 0
Pour b = 1, il divulgue σ(uG ⊕ c ⊕ e ) et σ(e ) au vérifieur V.
Pour b = 2, il divulgue σ et u au vérifieur V.
Par contre, il ne peut pas répondre si b = 0. L’IDENTIFICATION
Co
5. Le Prouveur malicieux peut suivre la stratégie (b) ou (c) pour les tirages dont les indices
sont divisibles par 3 (tirages 3-6-9-12-...) et pourra ainsi répondre aux challenges b = 2.
Pour les autres tirages, il suit la stratégie (a) et pourra ainsi répondre aux challenges b = 0
ou b = 1.
31/49
