Wiki du cours

Rédacteur: Samuel Monnier

A traiter [تحرير]

Le but des sujets 35 et 36 est de montrer comment il est possible de reconstruire les coefficients linéaires cachés d'une fonction en temps polynomial (la preuve du Théorème 1 de [1], contenue dans la Section 6).

• L'expérience quantique, bonnes observables ([1] Section 6.1).
• Comment utiliser une bonne observable pour trouver la structure linéaire cachée ([1] Section 6.2).

Rappel [تحرير]

On rappelle que l'on a une fonction \( f(x,y) = h(x + \alpha y) \) avec \( h \) un homomorphisme de \( \mathbb{Z} \) dans \( \mathbb{Z}_q \). Le but est de trouver la "structure linéaire cachée" de \( f \), c'est-à-dire \( \alpha \). On suppose que \( q \) est un nombre de \( n \) bits (\( n \sim \log q \)), que l'ordre de \( h \) est au plus \( m = n^d \) pour une constante \( d \) et que le plus petit premier divisant \( q \) est supérieur à \( m \).

L'expérience quantique [تحرير]

On énumère les nombres premiers par ordre croissant, et on construit le produit \( W \) de tous les nombres premiers ne divisant pas \( q \), jusqu'à ce que \( W \) dépasse \( \max(2q, mq) \).

On rappelle que la transformée de Fourier discrète d'ordre \( W \) a pour éléments de matrice

\( (F_W)_{x,y} = \frac{1}{\sqrt{W}} \exp \frac{2 \pi i x y}{W} \)

pour \( 0 \leq x, y < W \). Il est possible de calculer cette transformée de Fourier en un temps polynomial (en la taille en bit \( \log W \) de \( W \)), comme expliqué au Sujet 33.

L'expérience quantique procède comme suit. L'espace des états est formés de qubits groupés en trois registres. Les deux premiers registres permettent chacun de stocker un élément de \( \mathbb{Z}_q \), alors que le troisième permet de stocker un élément du groupe \( S \) dans lequel \( h \) prend valeurs.

1. Le premier pas consiste à construire une superposition de tous les couples \( (r_1, r_2) \in \mathbb{Z}_q \times \mathbb{Z}_q \) possibles, pour obtenir un état

\( \sum_{r_1, r_2 \in \mathbb{Z}_q} | r_1, r_2, 0 \rangle \).

Ceci est effectué en appliquant à l'état \( |0, 0, 0 \rangle \) une porte \( R \) du sujet Sujet 33 à chaque qbit des deux premier registres.

2. On passe l'état quantique dans une porte calculant \( f \) et stockant le résultat dans le troisième registre pour obtenir l'état

\( \sum_{r_1, r_2 \in \mathbb{Z}_q} | r_1, r_2, f(r_1, r_2) \rangle \).

3. On applique la transformation the Fourier (modulo \( W \)) décrite plus haut sur les deux premiers registres et on obtient

\( \sum_{r_1, r_2, s_1, s_2 \in \mathbb{Z}_q} \exp \left (2\pi i \frac{r_1*s_1 + r_2*s_2}{W} \right) | s_1, s_2, f(r_1, r_2) \rangle \).

4. On mesure l'état, ce qui le projette sur une composante \( | s_1, s_2, b \rangle \) avec une probabilité

\( \frac{1}{q^2W^2} \left| \sum \exp 2\pi i \frac{r_1*s_1 + r_2*s_2}{W} \right|^2 \)

où la somme est sur tous les \( r_1, r_2 \in \mathbb{Z}_q \) tels que \( f(r_1, r_2) = b \).

Bonnes observables [تحرير]

On décrit maintenant l'ensemble \( \mathcal{V} \) des "bonnes observables" (voir Sujet 34), c'est-à-dire l'ensemble des valeurs \( (s_1, s_2, b) \) telles que si l'état \( | s_1, s_2, b \rangle \) est obtenu lors de la mesure, alors on arrive à calculer \( \alpha \) (ou tout au moins à simplifier le problème, voir plus loin).

On note \( \{ x \}_W \) le résidu de \( x \) modulo \( W \). Dans les relations suivantes, on représente librement \( s_1, s_2 \in \mathbb{Z}_q \) par les entiers correspondants entre \( 0 \) et \( q \). Les bonnes observables doivent satisfaire les propriétés suivantes:

1. \( s_1 q \geq W \);
2. \( \{ s_1 q \}_W \leq W/m \);
3. \( s_2 - s_1 \alpha + \frac{\alpha}{q} \{ s_1 q \}_W = tW + \delta \) pour un entier \( t \) et \( |\delta| < 1 \);
4. \( \left | \sum_{k=1}^m \exp 2\pi i \frac{b_k s_1}{W} \right | \geq \frac{1}{2} \), où les \( \{ b_k \} \) sont les \( m \) éléments distincts de \( \mathbb{Z}_q \) tels que \( h(b_k) = b \).

Notons que seules les conditions 1 et 3 sont nécessaire pour le calcul de \( \alpha \) ci-dessous. Les conditions 2 et 4 ne sont là que pour faciliter la dérivation des bornes sur l'amplitudes et la cardinalité des états dans \( \mathcal{V} \), expliquées dans le Sujet 36. Effectivement, ceci veut dire que si l'on obtient un état hors de \( \mathcal{V} \) mais satisfaisant tout de même les conditions 1 et 3, on sera quand même capable de retrouver \( \alpha \) (ou de simplifier le problème, cf. ci-dessous).

Calcul de la structure linéaire cachée étant donné une bonne observable [تحرير]

On remarque que l'on peut écrire \( s_1 q = vW + u \) avec \( 0 \leq u < W \) et

\( v = \frac{s_1 q - \{ s_1 q \}_W}{W} \).

Notons \( || x || \) pour la partie fractionelle de \( x \in \mathbb{Q} \). En divisant l'égalité de la condition 3 ci-dessus par \( W \) on obtient

\( \left| \left| \frac{s_2}{W} - \alpha \frac{v}{q} \right| \right| < \frac{1}{W} \)

Soit \( s \) l'entier tel que la fraction \( \frac{s}{q} \) approxime au mieux \( \frac{s_2}{W} \). On a donc

\( \left|\frac{s}{q} - \frac{s_2}{W} \right| < \frac{1}{2q} \)

Mais comme \( W > 2q \) les deux inégalités précédentes impliquent que

\( \left| \left| \frac{s}{q} - \alpha \frac{v}{q} \right| \right| = 0 \)

ou en d'autre termes \( s - \alpha v = 0 \) modulo \( q \). La condition 1 nous assure de plus que \( v \geq 1 \). Si \( v \) ne divise pas \( q \), une simple division modulaire permet de déterminer \( \alpha = s/v \).

Si \( v \) divise \( q \), on ne peut pas trouver \( \alpha \) directement. \( \alpha \) est néanmoins déterminé modulo \( z := q/{\rm gcd}(q, v) \), ce qui permet de simplifier le problème et remplace effectivement \( q \) par \( q/z \). Les détails sont expliqués à la fin de la Section 6.2 de [1].

Références [تحرير]

[1] Dan Boneh, Richard J. Lipton, Quantum cryptanalysis of hidden linear functions
[2] Peter W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer