40 IFT6170 Claude Crépeau

IFT6170 Devoir 4

à rendre au début du cours le mercredi 3 décembre 1997

Partage de secret [6 points]

Soit un code Reed-Solomon sur F_{q} ayant des paramètres [N = q − 1, K, N − K + 1]. On suppose que ses mots de code sont définis de façon standard

c = (c_{0} c_{1} ... c_{N−1}) = (F (1), F (α), ..., F (α^{N−1}))

pour les polynômes F sur F_{q} de degré < K. Supposons qu’Alice dispose d’un secret s ∈ F_{q}. Elle peut choisir un polynôme aléatoire

F (x) = s + f_{1}x + f_{2}x^{2} + ⋯ + f_{K−1}x^{K−1}

tel que F (0) = s, où chaque f_{i} est sélectionné au hasard dans F_{q}. Soit P_{0}, P_{1}, ..., P_{N−1} des personnes distinctes à qui Alice va distribuer des “ombres” de son secret: Alice donne c_{i} à P_{i}. Soit Φ ⊆ {0, 1, ..., N − 1}.

• Montrez que si |Φ| < K alors I(s; {(i, c_{i}) : i ∈ Φ}) = 0. C’est à dire que tout ensemble de personnes de taille inférieure à K n’a aucune information sur s.

• Montrez que si |Φ| ≥ K alors H(s | {(i, c_{i}) : i ∈ Φ}) = 0. C’est à dire que tout ensemble de personnes de taille au moins K peut déterminer s.

• Supposons que toutes les personnes se rencontrent et échangent leurs c_{i}. Considérons qu’un certain nombre t d’entre eux soit menteur et révèlent au contraire c̃_{i} ≠ c_{i}. Donnez une relation entre N, K et t qui donne les situations où l’on sera capable d’identifier les menteurs et de récupérer quand même le secret s. Comment peut-on identifier les menteurs efficacement?

Justesen généralisés [6 points]

Considérez sur F_{2} les codes C_{α,β} = {[u, αu, βu] : u ∈ F_{2^{m}}} pour α, β ∈ F_{2^{m}} − 0.

• Montrez qu’il existe parmis les codes C_{α,β} des codes de paramètres [3m, m, 3γm] pour γ ≥ h^{−1} (\frac{2}{3}) ≈ 0.1739523.

• Montrez qu’une construction semblable à celle de Justesen nous permet de construire à partir des codes C_{α,β} des codes sur F_{2} ayant des paramètres [N, RN, δN] pour N = 3m2^{m}, 0 ≤ R ≤ \frac{1}{3} et δ ≥ (1 − 3R)h^{−1} (\frac{2}{3}).

• Montrez qu’une construction semblable à la précédente nous permet de construire pour chaque entier a des codes sur F_{2} ayant des paramètres [N, RN, δN] pour N = am2^{m}, 0 ≤ R ≤ \frac{1}{a} et δ ≥ (1 − aR)h^{−1} (\frac{a−1}{a}).

• Tracez ces droites sur un graphique et montrez qu’elles forment un ensemble de tangentes à la courbe de Zyablov.

Codes réversibles [4 points]

Un code C ⊆ F_{q} est réversible si c_{0}c_{1} … c_{n−1} ∈ C implique c_{n−1}c_{n−2} … c_{0} ∈ C également. Montrez qu’un code cyclique C = ⟨g⟩ est réversible si et seulement si g(α) = 0 implique toujours g(α^{−1}) = 0. Montrez qu’un code cyclique C est réversible si et seulement si −1 est une puissance de q modulo n.