Wiki du cours

Rédacteur: Charlotte Baumgart

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).

• Amplitude des bonnes observables ([1] Section 6.3)
• Cardinalité de l'ensemble des bonnes observables ([1] Section 6.4)

Rappel [تحرير]

On dit que l'observable \((s_1,s_2, b)\) est dans \(\mathcal{V}\) si les quatre conditions suivantes sont satisfaites :

• \(s_1 q \geq W\)
• \(\{s_1 q\}_W\leq \frac{W}{m}\)
• Soit \(C= s_2 -s_1 \alpha +\frac{\alpha}{q}\{s_1 q\}_W\), alors \(C=tW+\delta\) pour un certain \(t\) et un certain \(\mid\delta\mid<1\)
• \( \mid \sum_{k=1}^{m} exp(\frac{2i\pi b_k s_1}{W}) \mid \geq\frac{1}{2}\) avec \(b_1,...b_m\) des éléments distincts tels que \(h(b_k)=b \quad\forall b_k\) (\(m\) l'ordre de h.)

Amplitude des bonnes observables [تحرير]

But : on veut qu'une bonne observable ait une probabilité suffisante d'arriver.

Soit \((s_1,s_2,b)\) une observable de \(\mathcal{V}\). On a vu que la probabilité de cette observable est donnée par

\(\sigma(s_1,s_2,b)= \mid\frac{1}{qW} \sum exp(\frac{2i\pi}{W}(r_1s_1+r_2s_2))\mid^2\),

la somme parcourant tous les \(r_1, r_2\) tels que \(f(r_1,r_2)=b\).

On sait que \(f(r_1,r_2)=b\) si et seulement si \(h(r_1 +\alpha r_2)=b\) (car \(f\) a une structure linéaire cachée). Par périodicité de \(f\), il existe des valeurs distinctes \(b_1, ..., b_m\), telles que \(h(b_k)=b \quad \forall k.\)

On peut réécrire notre probabilité comme \(\mid\frac{1}{q^2W^2}\sum_{k=1}^{m} \sum exp(\frac{2i\pi(r_1s_1+r_2s_2)}{W})\mid^2\), la somme (intérieure) parcourant les \(r_1, r_2\) tels que \(r_1\equiv b_k-\alpha r_2\) mod \(q\).

Comme \(1\leq r_1<q\), pour \(r_2\) donné, on a \(r_1=b_k-\alpha r_2-q\left \lfloor{\frac{b_k-\alpha r_2}{q}}\right \rfloor\). En remplaçant, on trouve \(\frac{1}{q^2W^2} \mid \sum_{k=1}^{m}exp(\frac{2i\pi b_ks_1}{W}) \sum_{r_2=0}^{q-1}exp(\frac{2i\pi}{W} (r_2s_2-\alpha s_1r_2)-s_1 q \left \lfloor{\frac{b_k-\alpha r_2}{q}}\right \rfloor )\mid\), qu'il nous reste à borner.

Fixons \(k\) et regardons la somme intérieure. On peut la réécrire \(\sum_{r_2=0}^{q-1} exp (\frac{2i\pi}{W}r_2(s_2-\alpha s_1+\frac{\alpha}{q}\{s_1 q\}_W )) exp(-\frac{2i\pi}{W}(\frac{\alpha r_2}{q}+\left\lfloor{\frac{b_k-\alpha r_2}{q}}\right\rfloor)\{s_1 q\}_W ) \)
Par la condition (3), et parce que \(\frac{r_2}{W}<\frac{q}{W}<\frac{1}{m}\), l'argument de la première exponentielle est toujours inférieur à \(\frac{2i\pi}{m}\). De plus, par les propriétés de la partie entière, on a (pour la deuxième exponentielle):

 \( \mid \frac{\alpha r_2}{q}+\left\lfloor{\frac{b_k - \alpha r_2}{q} }\right\rfloor\mid\leq \left\lfloor{\frac{b_k}{q} }\right\rfloor+1\leq 1 \).

Comme \(\{s_1 q\}_W\leq\frac{W}{m}\), on déduit que la valeur absolue de l'argument de la deuxième exponentielle est inférieure à \(\frac{2i\pi}{m}\), et donc l'argument total est inférieur à \(\frac{4i\pi}{m}\).

Le lemme 7 nous donne que la somme est toujours inférieure à \((1-O(\frac{1}{m^2}))q\). De plus, elle est aussi inférieure à \(q\) (puisqu'on somme moins de \(q\) termes inférieurs à 1). On obtient que \(\sigma(s_1,s_2,b)= \frac{1}{W^2}\mid \sum_{k=1}^{m} (1-\epsilon_k)exp(\frac{2i\pi b_k s_1}{W})\mid^2 \) avec \(0\leq\epsilon_k\leq O(\frac{1}{m^2}) \forall k\).

La condition (4) conclut : une bonne observable a bien probabilité d'ordre supérieur à \(\frac{1}{W}\).

Cardinalité de l'ensemble des bonnes observables [تحرير]

But : on veut montrer que \(\mid \mathcal{V}\mid >\frac{W^2}{n^{O(1)}}\) Pour tout \(s_1\), il existe \(s_2\) satisfaisant la condition (3). En effet, il suffit de choisir \(s_2\) l'entier le plus proche de \(-\alpha s_1 +\frac{\alpha }{q}\{s_1\}_W\). On va borner par en-dessous le nombre de \(s_1\) satisfaisant les conditions (2) et (4), et montrer que le nombre de \(s_1\) ne satisfaisant pas la condition (1) est négligeable : au niveau des probabilités, leur présence ou absence ne change rien.

Posons \(x=q s_1\) mod \(W\) et \(c_k =b_k q^{-1}\) mod \(W\) (\(q^{-1}\) existe, car \(W\) et \(q\) sont premiers entre eux). On peut réécrire les conditions (2) et (4) :
(2) : \(0\leq x \leq \frac{W}{m}\)
(4) : \(\mid \sum_{k=1}^{m}exp(\frac{2i\pi c_k x}{W}) \mid \geq \frac{1}{2}\)
Par le lemme 5, le nombre de \(x\) satisfaisant ces deux conditions est supérieur à \( \frac{W}{m^3} \). Le nombre de \(s_1\) entiers ne satisfaisant pas la condition (1) (\(s_1q\geq W\)) est directement maximisé par \(\frac{W}{q}\). Par hypothèse, \(m\) est maximisé par \(log(q)^{O(1)}\), donc \(m^3\leq log(q)^{3O(1)}\) et \(\frac{W}{m^3} -\frac{W}{q}\geq (\frac{q-log(q)^{O(1)}}{q})\frac{W}{m^3} = (1-\frac{log(q)^{O(1)}}{q})\frac{W}{m^3}\), or \(\frac{log(q)^{O(1)}}{q}\) est très petit pour \(q\) suffisamment grand.
Le nombre total de paires \((s_1,s_2)\) satisfaisant les quatre conditions est alors de l'ordre de \(\frac{W}{m^3}\), et donc supérieur à \( \frac{W}{n^{O(1)}} \).
Comme on a q valeurs possibles pour \(b\), et par définition de \(W=q n^{O(1)}\) on a en fait \(\mid\mathcal{V}\mid >\frac{W^2}{n^{O(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