Ин таҳқиқот барои эҳтимоли он ки алгоритми квантии Ekerå–Håstad масъалаи логарифми дискретии кӯтоҳро (short discrete logarithm problem, short DLP) дар як иҷрои ягонаи квантӣ ҳал кунад, ҳадди поёнии математикии бе такя ба симулятсияро ҳосил намуда, арзиши ҳисоббарории заруриро барои коркарди классикии натиҷаи он аз боло маҳдуд мекунад. Натиҷаи асосӣ ин аст, ки бо интихоби мувофиқи параметрҳо ва post-processing-и классикӣ, ҳадди поёнии назариявии муваффақияти барқарор кардани логарифми кӯтоҳи \(d\) дар як иҷро то сатҳи \(1-10^{-10}\) баланд карда мешавад. Ин эҳтимоли баланди муваффақият на аз калон кардани қисми квантӣ, балки аз истифодаи усулҳои meet-in-the-middle ё random-walk-и камхотира дар коркарди классикии ҷуфти \((j,k)\), ки аз ченкунии квантӣ ба даст меояд, ҳосил мешавад. Натиҷаҳо ба схемаҳои математикиву мантиқии квантӣ дахл доранд; меъёрҳои хатои таҷҳизоти воқеии квантӣ ва сарбории ислоҳи хатои квантӣ ба ҳисоб гирифта нашудаанд.
Саҳми муҳими таҳқиқот иваз кардани рафтори муваффақиятест, ки қаблан бо симулятсияҳо омӯхта шуда буд, бо ҳудудҳои қатъии эҳтимолият ва мураккабӣ. Алгоритм дар гурӯҳи даврие, ки тартибаш номаълум аст, қимати кӯтоҳи \(d\)-ро дар робитаи \(x=g^d\) ҳадаф мегирад. Дар қисми квантӣ ду натиҷаи намунагирии Fourier, яъне \(j\) ва \(k\), ҳосил мешаванд; дар қисми классикӣ бошад, ин қиматҳо тавассути масъалаи шабакаи дученака барои ёфтани \(d\) коркард мешаванд.
Дар байни параметрҳо мубодилаи равшани хароҷот мавҷуд аст. Ҳангоми зиёд кардани \(\Delta\), шумораи амалҳои гурӯҳӣ, ки бояд дар компютери квантӣ арзёбӣ шаванд, метавонад кам шавад; дар иваз, фазои ҷустуҷӯи классикӣ ва арзиши post-processing меафзояд. Дар намунаи FF-DH бо safe prime-и 2048-бит, аз нуқтаи ибтидоии 672 амали гурӯҳии квантӣ барои \(\Delta=0\), бо интихоби \(\Delta=50\) то 572 амали гурӯҳӣ поён рафтан нишон дода мешавад. Озмоишҳои татбиқии муаллиф нишон медиҳанд, ки ин коҳиши тақрибан %15 бо параметрҳои интихобшуда дар ҳоле ба даст меояд, ки post-processing-и классикӣ ҳанӯз амалӣ боқӣ мемонад.
Масъалаи логарифми дискретии кӯтоҳ чист?
Дар short DLP-и баррасишуда, генератори \(g\)-и гурӯҳи даврии дорои тартиби \(r\) ва
\[ x=g^d \]
дода мешаванд. Ҳадаф ҳисоб кардани логарифми дискретии кӯтоҳи \(d\) таҳти шарти \(d\ll r\) аст. Хусусияти муҳими ин таҳқиқот он аст, ки тартиби гурӯҳ \(r\) ҳатман маълум буданаш шарт нест.
\(m\) ҳамчун ҳадди боло барои дарозии битии \(d\) гирифта шуда,
\[ d<2^m \]
қабул мешавад. Мақола ҳамчунин параметри
\[ \ell=m-\Delta \]
-ро муайян мекунад. \(\Delta\) дар мубодилаи байни арзиши қисми квантӣ ва ҷустуҷӯи классикии баъдӣ нақши марказӣ мебозад.
Равиши Ekerå–Håstad аз алгоритми Shor аз кадом ҷиҳат фарқ мекунад?
Алгоритми аслии логарифми дискретии Shor логарифмҳои умумии дискретиро дар гурӯҳҳои даврии дорои тартиби маълум баррасӣ мекунад, дар ҳоле ки равиши Ekerå–Håstad дар ин ҷо логарифмҳои кӯтоҳро ҳангоми номаълум будани тартиби гурӯҳ ҳадаф мегирад.
Таҳқиқот қайд мекунад, ки ин хусусият махсусан барои системаҳои finite-field Diffie–Hellman бо экспонентҳои кӯтоҳ дар гурӯҳҳои safe-prime ва барои коҳиш додани масъалаи факторизатсияи ададҳои бутуни RSA ба short DLP аҳамияти криптоаналитикӣ дорад.
Алгоритми квантӣ кадом ҳолатро месозад?
Алгоритм аввал бар рӯи қиматҳои \(a\) ва \(b\) суперпозицияҳои яксон месозад ва дар регистри корӣ
\[ g^a x^{-b}=g^{a-bd} \]
-ро ҳисоб мекунад. Ҳолати пеш аз QFT дар манбаъ чунин дода шудааст:
\[ \frac{1}{\sqrt{2^{m+2\ell}}} \sum_{a=0}^{2^{m+\ell}-1} \sum_{b=0}^{2^\ell-1} |a,b,g^{a-bd}\rangle . \]
Сипас ба ду регистри идоракунӣ мутаносибан quantum Fourier transform (QFT)-ҳои андозаи \(2^{m+\ell}\) ва \(2^\ell\) татбиқ мешаванд. Пас аз чен кардани регистрҳои идоракунӣ қиматҳои \(j\) ва \(k\) ба даст меоянд.
Шакли 1 дар охири мақола ин схемаро мустақим нишон медиҳад: регистри якуми идоракунӣ сохтани \(g^a\), регистри дуюм ҷузъи \(x^{-b}\), ва регистри корӣ муттаҳид кардани онҳоро бо амали гурӯҳӣ иҷро мекунад. Дар ҳар ду регистри идоракунӣ блокҳои QFT ва ченкунӣ мавҷуданд.
Чаро тарҳи дуюми схема муҳим аст?
Шакли 2 ҳамон амали математикиро аз нав тартиб медиҳад ва нишон медиҳад, ки аввал \(j\), сипас бо маълум будани \(j\), \(k\)-ро ҳисоб кардан мумкин аст. Ин азнавтартибдиҳӣ зарурати ҳамзамон нигоҳ доштани ду регистри идоракуниро кам мекунад.
Мувофиқи манбаъ, дар тарҳи стандартӣ андозаи умумии ду регистри идоракунӣ \(m+2\ell\) qubit аст, аммо бо азнавтартибдиҳии амалҳо фазои идоракунии ҳамзамонро то \(m+\ell\) qubit кам кардан мумкин аст. Мақола инчунин шарҳ медиҳад, ки бо semi-classical QFT ва истифодаи такрории qubit-и идоракунӣ вазифаи ду регистрро бо як qubit-и такроран истифодашаванда иҷро кардан мумкин аст; ин оптимизатсия мавзӯи асосии таҳлил нест ва ҳамчун ёддошти татбиқи схема пешниҳод мешавад.
Арзиши асосӣ дар қисми квантӣ чист?
Дар таҳқиқот ҷузъи бартари арзиши квантӣ ҳамчун ду амали экспоненсиатсия баррасӣ мешавад. Шумораи амалҳои гурӯҳие, ки дар як иҷро бояд арзёбӣ шаванд,
\[ m+2\ell \]
аст ва азбаски \(\ell=m-\Delta\):
\[ m+2\ell=3m-2\Delta. \]
Бинобар ин, барои \(\Delta=0\), арзиш дар миқёси \(3m\) амали гурӯҳӣ аст. Афзоиши \(\Delta\) шумораи амалҳои квантиро кам мекунад, вале чунон ки дар бахшҳои баъдӣ дида мешавад, арзиши ҷустуҷӯи классикиро зиёд мекунад.
Ченкуниҳои \(j\) ва \(k\) чӣ гуна дар бораи логарифм маълумот медиҳанд?
Таҳқиқот барои ҷуфти аз ченкунӣ гирифташуда
\[ \alpha_d=\alpha(j,k) =\{dj+2^mk\}_{2^{m+\ell}} \]
ва кунҷи мувофиқи
\[ \theta_d= \frac{2\pi\alpha_d}{2^{m+\ell}} \]
-ро муайян мекунад. Дар ин ҷо \(\{u\}_n\) қимати \(u\)-ро пас аз кам кардани modulo \(n\) ба интервали марказонидашуда нишон медиҳад.
Яке аз қисмҳои муҳими исбот нишон додани он аст, ки \(j\) аз байни ададҳои бутуни дар
\[ [0,2^{m+\ell}) \]
буда бо тақсимоти яксон интихоб мешавад. Дар татбиқи схема \(j\) метавонад аввал ҳисоб шавад; сипас \(k\) бо шарти додашудаи \(j\), мувофиқи тақсимоти эҳтимолияти квантӣ чен карда мешавад.
Ҷуфти \(\tau\)-good чист?
Барои муваффақ будани post-processing-и классикӣ муаллиф таърифи зеринро истифода мебарад. Агар ҷуфти \((j,k)\) шарти
\[ \left| \{dj+2^mk\}_{2^{m+\ell}} \right| \leq 2^{m+\tau} \]
-ро қонеъ кунад, он \(\tau\)-good номида мешавад. Дар ин ҷо
\[ \tau\in[0,\ell]\cap\mathbb Z. \]
Бо зиёд шудани \(\tau\), минтақаи натиҷаҳои ченкунӣ, ки “хуб” ҳисоб мешаванд, васеъ мегардад ва аз ин рӯ эҳтимоли гирифтани ченкунии муваффақ боло меравад; дар иваз, минтақае, ки ҷустуҷӯи классикии шабака бояд фаро гирад, низ метавонад калон шавад.
Барои эҳтимоли ҷуфти \(\tau\)-good кадом ҳад исбот мешавад?
Lemma 1 барои \(j\)-и собит эҳтимоли он ки \(k\)-и ченшуда ҷуфти \(\tau\)-good созад, аз поён маҳдуд мекунад:
\[ P_{\tau\text{-good}} \geq 1-\psi'(2^\tau) \]
ва бо истифода аз ҳадди боло барои функсияи trigamma:
\[ P_{\tau\text{-good}} > 1- \frac{1}{2^\tau} - \frac{1}{2\cdot2^{2\tau}} - \frac{1}{6\cdot2^{3\tau}}. \]
Ин фоизи муваффақияти таҷрибавӣ нест. Ин ҳадди поёнии аналитикӣ мебошад, ки аз тақсимоти эҳтимолияти математикии алгоритми квантӣ бароварда шудааст.
Чаро шабака дар маркази post-processing-и классикӣ қарор дорад?
Таҳқиқот барои \(j\)-и ченшуда шабакаи дученакаи
\[ L^\tau(j) = \langle (j,2^\tau), (2^{m+\ell},0) \rangle \]
-ро месозад.
Вақте ки ҷуфти \((j,k)\) \(\tau\)-good аст, вектори маълуми
\[ v= (\{-2^mk\}_{2^{m+\ell}},0) \]
ва вектори номаълуми дорои \(d\)
\[ u= (dj+2^{m+\ell}z,2^\tau d) \]
ба ҳам наздик мешаванд. Дар таҳқиқот ин наздикӣ
\[ \|u-v\|<2^{m+\tau}\sqrt 2 \]
чунин маҳдуд карда мешавад.
Аз ин рӯ масъала ба ёфтани вектори мувофиқи \(L^\tau(j)\) дар радиуси муайян атрофи \(v\) табдил меёбад.
Шабакаи \(t\)-balanced чӣ маъно дорад?
Бигзор \(\lambda_1\) нормаи кӯтоҳтарин вектори ғайрисифрии шабака бошад. Таҳқиқот шабакаи \(L^\tau(j)\)-ро, ки шарти
\[ \lambda_1\geq2^{m-t} \]
-ро қонеъ мекунад, \(t\)-balanced меномад.
Мувофиқи Lemma 2 эҳтимоли набудани \(t\)-balanced будани шабака ҳадди аксар
\[ 2^{\Delta-2(t-1)-\tau} \]
аст, бинобар ин барои эҳтимоли \(t\)-balanced будан
\[ P_{\mathrm{balanced}} \geq 1-2^{\Delta-2(t-1)-\tau} \]
ҳадди поён ҳосил мешавад; минтақаҳои параметрие, ки ифода метавонад манфӣ шавад, дар теоремаи асосӣ бо сифр маҳдуд карда мешаванд.
Ҳадди асосии эҳтимоли муваффақият
Theorem 1 ва Theorem 2 эҳтимолҳои ҷуфти \(\tau\)-good ва шабакаи \(t\)-balanced-ро якҷо мекунанд. Ҳамин тавр, ҳадди поёнии муваффақияти барқарор кардани логарифми кӯтоҳ дар доираи арзиши ҳадафшудаи классикӣ чунин дода мешавад:
\[ P_{\mathrm{success}} \geq \max\left( 0, 1- \frac{1}{2^\tau} - \frac{1}{2\cdot2^{2\tau}} - \frac{1}{6\cdot2^{3\tau}} \right) \max\left( 0, 1-2^{\Delta-2(t-1)-\tau} \right) \]
чунин дода мешавад.
Ин формула муҳимтарин натиҷаи таҳқиқот аст: он муносибати байни баланд кардани эҳтимоли муваффақият ва васеъ кардани фазои post-processing-и классикиро мустақиман математикӣ ифода мекунад.
Ҳалли якуми классикӣ: meet-in-the-middle
Усули якуми post-processing ҷустуҷӯи детерминистии meet-in-the-middle аст, ки равиши baby-step giant-step-и Shanks-ро ба ду андоза васеъ мекунад.
Таҳқиқот аввал асоси Lagrange-reduced-и шабака \((s_1,s_2)\)-ро ҳисоб мекунад. Бо алгоритми Babai nearest-plane нуқтаи шабакаи \(o\), ки ба вектори маълуми \(v\) наздик аст, ёфта мешавад. Сипас ҷустуҷӯ ба минтақаи маҳдуди дученака атрофи \(o\) кам карда мешавад.
Барои Theorem 1
\[ N= 2^{\Delta+\tau+1} + 2^{\tau+t+2} + 2 \]
муайян мешавад. Барои собити мусбати бутуни \(c\), ба шарте ки чанд элементи гурӯҳӣ пешакӣ ҳисоб шуда бошанд, шумораи амалҳои гурӯҳии зарурӣ ҳадди аксар
\[ 2^3c\sqrt N = 8c\sqrt N \]
аз боло маҳдуд карда мешавад.
Шумораи ададҳои бутуне, ки бояд дар ҷадвали lookup нигоҳ дошта шаванд, ҳадди аксар
\[ \frac{8\sqrt N}{c}+3 \]
мешавад. Зиёд кардани \(c\) истифодаи хотираро кам мекунад, вале дар марҳилаи дуюми ҷустуҷӯ корро зиёд намуда, мубодилаи вақт-хотира эҷод мекунад.
Ҳалли дуюми классикӣ: random walk ва Gaudry–Schost
Дар равиши meet-in-the-middle барои параметрҳои калон хотира метавонад маҳдудияти асосӣ шавад. Аз ин рӯ таҳқиқот роҳи дуюмро пешниҳод мекунад: табдил додани ҷустуҷӯи шабака ба short DLP-и дученака ва истифодаи алгоритми Gaudry–Schost бо такмилҳои Galbraith–Ruprai.
Ин усул ба ҷойи ҷадвали калони детерминистии lookup равиши эҳтимолии random-walk-ро истифода бурда, талаботи хотираро то сатҳи \(O(1)\) элементи гурӯҳӣ кам мекунад.
Барои Theorem 2
\[ N= 2^{\Delta+\tau+4} + 2^{\tau+t+5} + 5 \]
ва дар модели идеализатсияшуда шумораи интизоршавандаи амалҳои гурӯҳӣ барои ҳолатҳои беҳтарин, миёна ва бадтарин бо
\[ \left(\frac{4}{3}+o(1)\right)\sqrt{\pi N} \]
аз боло маҳдуд карда мешавад.
Ин натиҷа мураккабии интизоршаванда аст ва ба модели идеализатсияшудаи таҳлили Gaudry–Schost такя мекунад; онро ҳамчун вақти мутлақи детерминистии иҷро тафсир кардан дуруст нест.
Verianla Live: Аз ченкунии квантӣ то логарифми кӯтоҳ
Ин раванд қисмҳои квантӣ ва классикии таҳқиқотро бо тартиби воқеии амалҳое, ки дар манбаъ истифода шудаанд, нишон медиҳад. Қадами нави алгоритмӣ ё натиҷаи берун аз манбаъ илова нашудааст.
| Марҳила | Амали муайяншуда дар манбаъ | Нақши илмӣ |
|---|---|---|
| 1. Вуруди short DLP | \(x=g^d\), \(d<2^m\), тартиби гурӯҳ \(r\) метавонад номаълум бошад. | Логарифми кӯтоҳи \(d\), ки бояд барқарор шавад, муайян мегардад. |
| 2. Суперпозицияи квантӣ | Бар рӯи регистрҳои \(a\) ва \(b\) суперпозицияи яксон омода шуда, \(g^{a-bd}\) ҳисоб мешавад. | Маълумоти фазавии вобаста ба логарифми кӯтоҳро ба ҳолати квантӣ рамзгузорӣ мекунад. |
| 3. QFT ва ченкунӣ | Ба регистрҳои идоракунӣ QFT татбиқ мешавад; аввал \(j\), сипас \(k\)-и вобаста ба \(j\) гирифтан мумкин аст. | Ҷуфти ченкунии \((j,k)\)-ро, ки post-processing-и классикӣ истифода мебарад, ҳосил мекунад. |
| 4. Санҷиши \(\tau\)-good | \(|\{dj+2^mk\}_{2^{m+\ell}}|\leq2^{m+\tau}\). | Муайян мекунад, ки ҷуфти ченкунӣ барои барқарор кардани \(d\) дар минтақаи кофӣ мувофиқ аст ё не. |
| 5. Сохтани шабака | Шабакаи \(L^\tau(j)\) сохта ва асоси Lagrange-reduced ҳисоб мешавад. | Масъалаи логарифми кӯтоҳро ба ҷустуҷӯи маҳдуди шабакаи дученака табдил медиҳад. |
| 6. Нуқтаи наздик | Бо усули Babai nearest-plane нуқтаи шабакаи \(o\), ки ба \(v\) наздик аст, муайян мешавад. | Минтақаи шабакаеро, ки бояд ҷустуҷӯ шавад, маҳдуд мекунад. |
| 7A. Meet-in-the-middle | Ҷустуҷӯи умумисозишудаи дученакаи Shanks татбиқ мешавад. | Бо мубодилаи детерминистии вақт-хотира \(d\) ҷустуҷӯ мешавад. |
| 7B. Random walk | Масъала ба short DLP-и дученака табдил ёфта, усули Gaudry–Schost истифода мешавад. | Талаботи калони хотираи ҷадвали lookup-ро то \(O(1)\) элементи гурӯҳӣ кам мекунад. |
| 8. Барқарор кардани логарифм | Аз ҷузъи охирини вектори мувофиқи шабака \(d\) ҳисоб ва бо шарти \(x=g^d\) санҷида мешавад. | Post-processing-и классикӣ анҷом меёбад. |
Параметрҳои \(\Delta\), \(\tau\) ва \(t\) чиро тағйир медиҳанд?
| Параметр | Нақш дар таъриф | Тамоюли асосӣ ҳангоми зиёдшавӣ |
|---|---|---|
| \(\Delta\) | \(\ell=m-\Delta\) | Метавонад амалҳои гурӯҳии квантии зарурии \(3m-2\Delta\)-ро кам кунад; арзиши enumeration-и классикиро меафзояд. |
| \(\tau\) | Паҳноии минтақаи ченкунии \(\tau\)-good-ро муайян мекунад. | Ҳадди поёнии муваффақияти good-pair-ро баланд мекунад; метавонад минтақаи ҷустуҷӯи классикиро васеъ кунад. |
| \(t\) | Шарти шабакаи \(t\)-balanced-ро тавассути \(\lambda_1\geq2^{m-t}\) муайян мекунад. | Миёни эҳтимоли balanced будани шабака ва арзиши enumeration мубодила эҷод мекунад. |
Эҳтимоли муваффақият то чӣ андоза баланд карда мешавад?
Ҷадвали 1 нишон медиҳад, ки барои \(\Delta=0\) чӣ гуна сарбории кори классикӣ ва ҳадди поёнии исботшудаи муваффақият тағйир меёбанд:
| \(\Delta\) | \(\tau\) | \(t\) | Ҳадди поёнии эҳтимоли муваффақият | Ҳадди болоии кор, \(\log_2\) |
|---|---|---|---|---|
| 0 | 4 | 2 | \(\geq0{,}9\) | \(\leq7{,}1\) |
| 0 | 7 | 2 | \(\geq0{,}99\) | \(\leq8{,}6\) |
| 0 | 11 | 1 | \(\geq0{,}999\) | \(\leq10{,}2\) |
| 0 | 21 | 1 | \(\geq1-10^{-6}\) | \(\leq15{,}2\) |
| 0 | 27 | 2 | \(\geq1-10^{-8}\) | \(\leq18{,}6\) |
| 0 | 34 | 2 | \(\geq1-10^{-10}\) | \(\leq22{,}1\) |
Ин қиматҳо нишондиҳандаҳои таҷрибавии мушоҳидашуда нестанд. Онҳо комбинатсияҳои интихобшудаи ҳудудҳои кафолатноки математикии поён ва боло, ки аз Theorem 1 ба даст омадаанд, мебошанд.
Бо зиёд шудани \(\Delta\) чӣ рӯй медиҳад?
Ҷадвалҳои 1 ва 2 якҷоя нишон медиҳанд: ҳангоми нигоҳ доштани як ҳадафи муайяни эҳтимоли муваффақият, бо афзоиши \(\Delta\) арзиши enumeration-и классикӣ ба таври назаррас зиёд мешавад.
Масалан, барои ҳадди поёнии муваффақияти \(1-10^{-10}\):
| \(\Delta\) | \(\tau\) | \(t\) | Ҳадди поёнии муваффақият | Ҳадди болоии кор, \(\log_2\) |
|---|---|---|---|---|
| 0 | 34 | 2 | \(\geq1-10^{-10}\) | \(\leq22{,}1\) |
| 20 | 34 | 12 | \(\geq1-10^{-10}\) | \(\leq30{,}6\) |
| 50 | 34 | 27 | \(\geq1-10^{-10}\) | \(\leq45{,}6\) |
| 80 | 34 | 42 | \(\geq1-10^{-10}\) | \(\leq60{,}6\) |
| 130 | 34 | 67 | \(\geq1-10^{-10}\) | \(\leq85{,}6\) |
Аз ин рӯ, пайваста зиёд кардани \(\Delta\) барои кам кардани арзиши квантӣ оптимизатсияи ройгон нест. Ҳарчанд ҳисобкунии квантӣ кам мешавад, ҳисобкунии классикӣ ва агар meet-in-the-middle истифода шавад, талаботи хотира зуд меафзоянд.
Дар мисолҳои FF-DH шумораи амалҳои квантӣ чӣ гуна тағйир меёбад?
Ҷадвали 3 барои гурӯҳҳои FF-DH-и safe-prime шумораи амалҳои гурӯҳии квантии алгоритми Ekerå–Håstad-ро ҳамчун
\[ o_{\mathrm{EH}}=3m-2\Delta \]
истифода мекунад. Барои safe-prime-и 2048-бит ва экспоненти кӯтоҳи \(m=224\) бит, манбаъ ин қиматҳоро медиҳад:
| \(\Delta\) | \(\tau\) | \(t\) | Ҳадди поёнии муваффақият | Кори классикӣ, \(\log_2\) | Амали гурӯҳии квантӣ |
|---|---|---|---|---|---|
| 0 | 34 | 2 | \(\geq1-10^{-10}\) | \(\leq22{,}1\) | 672 |
| 50 | 10 | 29 | \(\geq0{,}999\) | \(\leq33{,}6\) | 572 |
| 70 | 7 | 37 | \(\geq0{,}99\) | \(\leq42{,}1\) | 532 |
Мисоли \(\Delta=50\) гузариш аз 672 ба 572 амали гурӯҳии квантиро ифода мекунад. Мувофиқи арзёбии худи таҳқиқот, ин тақрибан %15 коҳиши амали гурӯҳии квантӣ аст. Дар иваз, ҳадди болоии кори классикӣ дар миқёси \(\log_2\) аз 22,1 то 33,6 боло меравад.
Муаллиф гузориш медиҳад, ки дар озмоишҳои ибтидоии татбиқи оптимизатсияшуда ва параллелӣ барои \(\Delta=50\) ва ҳадафи ҳадди ақал %99 муваффақият, иҷрои post-processing дар компютери оддӣ одатан мушкил эҷод накардааст. Ин изҳорот мушоҳидаи бар асоси таҷрибаи татбиқӣ буда, аз теоремаи математикии таҳқиқот ҷудо гузориш шудааст.
Таҳқиқот дар бораи RSA чӣ мегӯяд?
Таҳқиқот имкони истифодаи ҳамин чаҳорчӯбаи таҳлили муваффақиятро барои RSA тавассути коҳиш додани масъалаи факторизатсияи ададҳои бутун ба short DLP баррасӣ мекунад. Аммо дар ин ҷо шарти иловагӣ вуҷуд дорад: \(g\)-и тасодуфан интихобшуда бояд тартиби кофӣ калон дошта бошад.
Ҷадвали 4 барои RSA ин омили иловагии коҳиши эҳтимолиятро бо \(f(\Delta)\) ҳисоб мекунад. Масалан, барои \(\Delta=20\) манбаъ омили коҳишро ҳадди ақал
\[ f(20)\geq0{,}999867 \]
мегирад. Дар ҳамин оилаи параметрҳо:
| \(\Delta\) | \(\tau\) | \(t\) | Ҳадди поёнии умумии муваффақият | Кори классикӣ, \(\log_2\) |
|---|---|---|---|---|
| 20 | 4 | 12 | \(\geq0{,}9\) | \(\leq15{,}6\) |
| 20 | 5 | 12 | \(\geq0{,}95\) | \(\leq16{,}1\) |
| 20 | 7 | 12 | \(\geq0{,}99\) | \(\leq17{,}1\) |
| 20 | 11 | 12 | \(\geq0{,}999\) | \(\leq19{,}1\) |
Ин ҷадвал маънои онро надорад, ки калиди RSA дар компютери воқеии квантии имрӯза бо ҳамин миқдор амал шикаста мешавад. Таҳқиқот дар ин ҷо эҳтимоли муваффақияти алгоритмӣ ва арзиши enumeration-и классикиро таҳлил мекунад; qubit-ҳои физикӣ, ислоҳи хато, хатои дарвоза ва вақти умумии воқеии иҷро берун аз ин ҳисобанд.
Чаро натиҷаи асимптотикӣ муҳим аст?
Corollary 1 нишон медиҳад, ки ҳангоми рафтани андозаи масъала \(m\) ба беохир, бо интихоби \(\Delta\), \(\tau\) ва \(t\) вобаста ба \(m\), ҳадди поёнии эҳтимоли муваффақият метавонад ба 1 наздик шавад ва ҳамзамон мураккабии enumeration-и классикӣ дар
\[ O(\mathrm{poly}(m)) \]
нигоҳ дошта шавад.
Масалан, таҳқиқот шарҳ медиҳад, ки агар \(\Delta\) ва \(t\) собит нигоҳ дошта шуда,
\[ \tau=\log_2 f(m) \]
интихоб шавад, барои \(f(m)\)-и мувофиқи super-constant, вале polynomially bounded, ин натиҷа ба даст меояд.
Натиҷаҳое, ки таҳқиқот дастгирӣ мекунад
- Барои эҳтимоли муваффақияти як иҷрои алгоритми Ekerå–Håstad short DLP ҳудудҳои қатъии поёнии бе симулятсия ба даст овардан мумкин аст.
- Бо параметрҳои мувофиқи post-processing-и классикӣ ҳадди поёнии эҳтимоли муваффақият то \(1-10^{-10}\) баланд мешавад.
- Ҷустуҷӯи meet-in-the-middle масъалаи маҳдуди lattice enumeration-ро ба таври детерминистӣ тез мекунад.
- Равиши random-walk-и бар асоси Gaudry–Schost талаботи хотираи ҳамон масъалаи ҷустуҷӯро то \(O(1)\) элементи гурӯҳӣ кам карда метавонад.
- Зиёд кардани \(\Delta\) амалҳои гурӯҳии квантии заруриро кам мекунад, вале арзиши post-processing-и классикиро меафзояд.
- Таҳлил бевосита ба сенарияҳои FF-DH-и safe-prime бо экспонентҳои кӯтоҳ ва ба RSA тавассути short DLP reduction татбиқ мешавад.
- Агар параметрҳо мувофиқи андозаи масъала масштаб шаванд, ҳадди поёнии муваффақият асимптотикӣ ба 1 наздик шуда, post-processing-и классикӣ метавонад дар вақти polynomial боқӣ монад.
Натиҷаҳое, ки таҳқиқот исбот намекунад
- Таҳқиқот дар компютери воқеии квантӣ таҷрибаи шикастани RSA ё FF-DH анҷом намедиҳад.
- Эҳтимоли назариявии муваффақият эҳтимоли бе хато кор кардани таҷҳизоти воқеии квантӣ нест.
- Таҳлил сарбории ислоҳи хатои квантӣ ё арзиши qubit-и физикиро ҳисоб намекунад.
- Шумораи амалҳои гурӯҳиро мустақиман ба сония, шумораи дарвозаҳои квантӣ ё qubit-и физикӣ баробар кардан мумкин нест.
- Мураккабии додаи усули random-walk мураккабии интизоршаванда дар модели идеализатсияшуда аст.
- Зиёд кардани \(\Delta\) ҳамаи хароҷотро кам намекунад; вақти классикӣ ва/ё арзиши хотира зиёд мешавад.
- Дар татбиқи RSA шарти иловагии тартиб барои short DLP reduction ва омили марбут ба коҳиши муваффақиятро сарфи назар кардан мумкин нест.
Усул ва натиҷаҳои таҳқиқот
Тарҳи таҳқиқот
Ин таҳқиқоти таҷрибавии сахтафзори квантӣ нест, балки таҳлили математикии эҳтимоли муваффақият ва мураккабӣ дар соҳаи криптографияи назариявӣ ва алгоритмҳои квантӣ аст. Ҳадафи асосӣ иваз кардани арзёбии қаблии муваффақияти бар асоси симулятсия бо ҳудудҳои поёнии исботшуда мебошад.
Таҳлил дар чор марҳилаи асосӣ пеш меравад:
- Тақсимоти ченкунии \((j,k)\)-и алгоритми квантӣ таҳлил мешавад.
- Эҳтимоли \(\tau\)-good будани \((j,k)\) аз поён маҳдуд карда мешавад.
- Эҳтимоли \(t\)-balanced будани шабакаи \(L^\tau(j)\) аз поён маҳдуд мешавад.
- Вақте ки ҳар ду ҳодиса рӯй медиҳанд, арзиши enumeration-и классикӣ барои барқарор кардани \(d\) аз боло маҳдуд карда мешавад.
Нақши Lemma 1
Lemma 1 барои \(j\)-и муайян эҳтимоли он ки \(k\)-и ченшуда ба минтақаи фазавии мувофиқ афтад, таҳлил мекунад. Дар исбот думҳои мусбат ва манфии тақсимоти эҳтимолият алоҳида аз боло маҳдуд карда мешаванд. Бо ҳудудҳои тригонометрӣ ва функсияи trigamma эҳтимоли умумии дум назорат мешавад.
Натиҷа:
\[ P_{\tau\text{-good}} > 1- 2^{-\tau} - \frac{1}{2}2^{-2\tau} - \frac{1}{6}2^{-3\tau}. \]
Нақши Lemma 2
Ҷузъи дуюми эҳтимолият аз геометрияи шабака меояд. Азбаски хеле кӯтоҳ будани кӯтоҳтарин вектори ғайрисифр назорати минтақаи enumeration-ро душвор мекунад, шарти \(t\)-balanced истифода мешавад.
Аз робитаи майдони фундаменталии шабака
\[ \lambda_1\lambda_2^\perp = 2^{m+\ell+\tau} \]
ва тақсимоти яксони \(j\) истифода шуда,
\[ P(L^\tau(j)\text{ balanced değil}) \leq 2^{\Delta-2(t-1)-\tau} \]
ҳосил мешавад.
Meet-in-the-middle enumeration чӣ гуна маҳдуд мешавад?
Бо истифода аз асоси Lagrange-reduced ва натиҷаи Babai nearest-plane, ҷустуҷӯ ба минтақаи маҳдуди росткунҷаи индекси дученака бо индексҳои \(m_1\) ва \(m_2\) кам карда мешавад. Таҳқиқот андозаҳои ин минтақаро бо \(B_1\) ва \(B_2\) маҳдуд мекунад.
Умумисозии дученакаи усули Shanks ба ҷойи санҷидани ҳамаи \((2B_1+1)(2B_2+1)\) номзадҳо ҷустуҷӯро ба ду қисм ҷудо мекунад. Қисми аввал дар ҷадвали lookup сабт мешавад, қисми дуюм мувофиқатҳоро дар ҷадвал меҷӯяд.
Ин сохтор асоси тезонидани meet-in-the-middle мебошад, ки вобастагиро аз шумораи номзадҳо тақрибан ба решаи квадратӣ табдил медиҳад.
Ҳалли random-walk кадом маҳдудиятро бартараф мекунад?
Дар усули meet-in-the-middle, бо калон шудани ҷадвали lookup хотира ба bottleneck табдил меёбад. Аз ин рӯ таҳқиқот масъалаи enumeration-ро ҳамчун short DLP-и дученакаи
\[ g_1^{i_1}g_2^{i_2}=x' \]
аз нав менависад.
Вақте ки ин масъала бо алгоритми Gaudry–Schost ва такмили Galbraith–Ruprai ҳал мешавад, дигар ҷадвали калони lookup лозим нест. Ҳамин тавр, истифодаи хотира асимптотикӣ то \(O(1)\) элементи гурӯҳӣ поён рафта метавонад.
Паёми асосии Ҷадвалҳои 1 ва 2
Ҷадвалҳои 1 ва 2 нишон медиҳанд, ки бо тағйир ёфтани \(\Delta\), \(\tau\) ва \(t\), ҳадди поёнии муваффақият ва ҳадди болоии enumeration-и классикӣ чӣ гуна тағйир меёбанд. Тамоюли намоён ин аст, ки бо зиёд шудани \(\Delta\), кори классикии зарурӣ барои нигоҳ доштани ҳамон сатҳи муваффақият босуръат меафзояд.
Масалан, барои ҳадди поёнии %99 муваффақият, қимати “Work” барои \(\Delta=0\) ҳадди аксар 8,6 аст, барои \(\Delta=50\) 32,1; барои \(\Delta=100\) 57,1 ва барои \(\Delta=130\) 72,1 дода шудааст. Қиматҳои “Work” шумораи мустақими амалҳо нестанд, балки намоиши \(\log_2\)-и ҳадди болоии амалҳои гурӯҳӣ мебошанд.
Паёми асосии Ҷадвали 3
Ҷадвали FF-DH мубодилаи хароҷоти квантӣ ва классикиро бо параметрҳои воқеии криптографӣ намоён мекунад. Дар ҷадвал барои гурӯҳҳои safe-prime-и 2048, 3072, 4096, 6144 ва 8192 бит дарозии экспонентҳои кӯтоҳ дода шуда, шумораи амалҳои гурӯҳии квантии Ekerå–Håstad бо равиши тағйирёфтаи Shor нисбат дода шудааст.
Масалан, барои safe-prime-и 4096-бит ва экспоненти кӯтоҳи \(m=304\) бит:
- \(\Delta=0\): 912 амали гурӯҳии квантӣ, бартарӣ 9,0.
- \(\Delta=50\): 812 амали гурӯҳии квантӣ, бартарӣ 10,0.
- \(\Delta=70\): 772 амали гурӯҳии квантӣ, бартарӣ 10,5.
Аммо афзоиши ин бартарӣ бояд бо афзоиши арзиши post-processing-и классикӣ якҷо арзёбӣ шавад.
Паёми асосии Ҷадвали 4
Ҷадвали RSA на танҳо ҳадди муваффақияти алгоритми short DLP, балки эҳтимоли он ки элементи гурӯҳии интихобшуда дар RSA reduction тартиби кофӣ калон надошта бошад, низ ба ҳисоб мегирад. Аз ин рӯ, бар хилофи ҷадвали FF-DH, омили иловагии коҳиш \(f(\Delta)\) вуҷуд дорад.
Таҳқиқот қайд мекунад, ки бо зиёд шудани \(\Delta\) ин омил ба 1 наздик мешавад, аммо арзиши ҳисоббарории усули аналитикии ҳадди поён бо \(\Delta\) босуръат меафзояд. Аз ин сабаб, барои ҳадафҳои хеле баланди муваффақият ҳамаи қиматҳо дар ҷадвал оварда нашудаанд.
Оё алгоритмҳо дар амал санҷида шудаанд?
Муаллиф гузориш медиҳад, ки усулҳои post-processing-и Algorithm 1 ва Algorithm 2-ро татбиқ намуда, бо коркарди натиҷаҳои симулятсияшудаи алгоритми квантӣ санҷидааст ва онҳо мувофиқи интизор кор мекунанд.
Ғайр аз ин, гуфта мешавад, ки озмоишҳои ибтидоии татбиқи оптимизатсияшуда ва параллелӣ барои \(\Delta=50\) бо ҳадафи ҳадди ақал %99 муваффақият нишон додаанд, ки post-processing дар компютери оддӣ одатан мушкил нест. Таҳқиқот ҳамчунин равшан мегӯяд, ки корҳои бештар барои оптимизатсия ва параллелсозии татбиқ идома доранд.
Паёми илмии Шаклҳои 1 ва 2
Шакли 1 регистри якуми идоракунии \(m+\ell\) qubit, регистри дуюми \(\ell\) qubit, амалҳои гурӯҳии идорашавандаи \(g^a\) ва \(x^{-b}\), блокҳои QFT ва ченкуниҳои \(j,k\)-ро дар як схема нишон медиҳад.
Шакли 2 схемаи аз ҷиҳати математикӣ эквивалентро аз нигоҳи вақтбандӣ аз нав ташкил мекунад. QFT ва ченкунии регистри якум фавран пас аз амали \(g^a\) ҷойгир мешавад, дар ҳоле ки регистри дуюм дертар омода карда мешавад. Ҳамин тавр, аввал ҳисоб кардани \(j\) ва баъд гирифтани \(k\) вобаста ба \(j\), бо сохтори истифодашуда дар таҳлили эҳтимолии Lemma 1 мутобиқ аст.
Натиҷаҳои асосии миқдорӣ
| Натиҷа | Қимати манбаъ | Ҳадди тафсир |
|---|---|---|
| Ҳадди поёнии асосии single-run-и қаблӣ | \(3/32=9{,}375\%\) | Ҳадди поёне, ки аз таҳлили қаблии Ekerå–Håstad гирифта шудааст. |
| Сатҳи нави назариявии муваффақият | то \(1-10^{-10}\) | Ҳадди поёнии математикӣ бо параметрҳои мувофиқ ва ҳудудҳои ҷустуҷӯи классикӣ. |
| Амали гурӯҳии квантӣ | \(m+2\ell=3m-2\Delta\) | Шумораи амалҳои мантиқии гурӯҳӣ; шумораи дарвозаҳои физикӣ нест. |
| Арзиши meet-in-the-middle | \(\leq8c\sqrt N\) | Таҳти шартҳои Theorem 1 ва ҳисобҳои пешакӣ. |
| Арзиши random-walk | \(\leq(4/3+o(1))\sqrt{\pi N}\) | Арзиши интизоршаванда дар модели идеализатсияшуда. |
| FF-DH 2048-бит, \(\Delta=50\) | 572 амали гурӯҳии квантӣ | Барои \(m=224,\tau=10,t=29\) ва ҳадди поёнии муваффақияти \(\geq0{,}999\) дар Ҷадвали 3. |
| Муқоисаи ибтидоии FF-DH 2048-бит | 672 амали гурӯҳии квантӣ | Параметргузории \(\Delta=0\). |
Ҷиҳатҳои асосии қавии таҳқиқот
- Рафтори single-run-и қаблан бо симулятсия арзёбишударо бо ҳудудҳои поёнии аналитикӣ дастгирӣ мекунад.
- Арзиши квантӣ ва арзиши post-processing-и классикиро дар як оилаи параметрҳо якҷо арзёбӣ мекунад.
- Илова ба эҳтимоли муваффақият, мураккабии enumeration-и классикиро ҳам бо ҳадди боло равшан медиҳад.
- Ду равиши post-processing — детерминистии дорои мубодилаи вақт-хотира ва эҳтимолии камхотира — пешниҳод мекунад.
- Барои FF-DH ва RSA reduction ҷадвалҳои параметрии ҷудогона пешниҳод мекунад.
- Алгоритмҳои post-processing бо натиҷаҳои симулятсияшудаи квантӣ дар амал санҷида шудаанд.
Маҳдудиятҳои асосии таҳқиқот
- Таҳлили асосии математикӣ фарз мекунад, ки компютери квантӣ алгоритмро мувофиқи таърифи математикӣ ва бе хатои ҳисоббарорӣ иҷро мекунад.
- Сарбории физикӣ ва ҳисоббарории ислоҳи хатои квантӣ ба таҳлил дохил карда нашудааст.
- Таҳлил бо схемаҳои мантиқии квантӣ ва арзишҳои мантиқӣ маҳдуд аст.
- Таҳлили short DLP шарти кӯтоҳии \(r\geq2^{m+\ell}+(2^\ell-1)d\)-ро истифода мекунад; дар RSA ин шарт омили иловагии эҳтимолият талаб мекунад.
- Миқдори кори дода барои усули Gaudry–Schost қимати интизоршаванда дар модели идеализатсияшуда аст.
- Барои \(\Delta\)-и калон, талаботи хотираи meet-in-the-middle post-processing метавонад амалишавии воқеиро маҳдуд кунад.
- Натиҷаҳои татбиқи оптимизатсияшуда ва параллелии post-processing ибтидоӣ мебошанд ва муаллиф мегӯяд, ки оптимизатсия идома дорад.
Ёддошти манбаъ ва усул
Номи пурраи кори аслӣ: On the success probability of the quantum algorithm for the short DLP
Муаллиф: Martin Ekerå.
Шумораи муаллифон: Як.
Ҳаммуаллифи аввал/саҳми баробар: Татбиқ намешавад; кор якмуаллифӣ аст.
Муаллифи масъул: Дар манбаъ нишонаи ҷудогонаи “corresponding author” истифода нашудааст. Барои Martin Ekerå почтаи электронӣ дода шудааст.
Аффилиатсияҳо: KTH Royal Institute of Technology, Stockholm, Sweden; Swedish NCSA, Swedish Armed Forces, Stockholm, Sweden.
Маҷалла: IACR Communications in Cryptology.
Ҷилд / шумора: 3 / 1.
ISSN: 3006-5496.
Ҳаҷм: 32 саҳифа.
DOI: 10.62056/an2isgsfg
Пайванди расмии нашр: https://doi.org/10.62056/an2isgsfg
Ношир / ташкилоти нашр: International Association for Cryptologic Research (IACR).
Навъи манбаъ: Мақолаи таҳқиқотии рецензияшуда.
Вазъи рецензия: Дар маҷаллаи peer-reviewed нашр шудааст. IACR Communications in Cryptology маҷаллаи пурра рецензияшаванда буда, сиёсати расмии он double-blind peer review-ро нишон медиҳад.
Санаи ирсол: 2 феврали 2026.
Санаи қабул: 23 апрели 2026.
Санаи нашр: 4 майи 2026.
Робитаи preprint: Версияҳои қаблии кор зери arXiv:2309.01754 нашр шудаанд. Сабти arXiv ба нашри ниҳоии маҷалла ва DOI 10.62056/an2isgsfg пайванд медиҳад. Баёни илмии ин мақолаи Verianla ба версияи нашршудаи 32-саҳифагие, ки корбар бор кардааст, асос ёфтааст.
Литсензия: Creative Commons Attribution 4.0 (CC BY 4.0). Ҳуқуқи муаллиф дар ихтиёри муаллиф(он) мемонад.
Маблағгузорӣ ва дастгирӣ: Дар таҳқиқот гуфта мешавад, ки маблағгузорӣ ва дастгирӣ аз ҷониби Swedish NCSA пешниҳод шудааст; Swedish NCSA дар таркиби Swedish Armed Forces қарор дорад. Ҳисобҳо инчунин бо захираҳои KTH PDC дар доираи National Academic Infrastructure for Supercomputing in Sweden (NAISS), ки қисман аз ҷониби Swedish Research Council grant agreement no. 2022-06725 маблағгузорӣ шудааст, анҷом дода шудаанд.
Сипос: Муаллиф ба Johan Håstad барои шарҳу тавсияҳо ва ба Joel Gärtner барои ҷалби таваҷҷӯҳ ба масъалаи Lemma 3 дар версияи аввали preprint сипос мегӯяд.
Ёддошти дода ва нармафзор: Таҳқиқот ба маҷмӯи додаҳои таҷрибавӣ асос намеёбад. Муаллиф мегӯяд, ки алгоритмҳои post-processing-ро татбиқ карда, бо натиҷаҳои симулятсияшудаи алгоритми квантӣ санҷидааст. Дар мақола ба татбиқи дастрас, вале оптимизатсиянашудаи Algorithm 1 ва ба анбори нармафзории Quaspy барои симулятор истинод шудааст.
Бархӯрди манфиатҳо: Дар кори боршуда бахши алоҳидаи conflict-of-interest ошкор нашудааст.
Саҳми муаллиф: Кор якмуаллифӣ аст ва баёнияи ҷудогонаи CRediT дода нашудааст.
Усули асосӣ: Маҳдудсозии аналитикии тақсимоти ченкунии алгоритми квантии Ekerå–Håstad short DLP; таҳлили шабакаи дученака; Lagrange reduction ва Babai nearest-plane; meet-in-the-middle enumeration; reduction ба short DLP-и дученака ва таҳлили random-walk-и Gaudry–Schost/Galbraith–Ruprai.
Ҳадди мундариҷаи илмӣ: Механизмҳои алгоритмӣ, формулаҳо, ҷадвалҳои ададӣ, натиҷаҳои FF-DH ва RSA, мушоҳидаҳои татбиқӣ ва маҳдудиятҳои ин мақолаи Verianla ба кори манбаи боршуда асос ёфтаанд. Манбаъҳои беруна танҳо барои тасдиқи библиографии шахсияти кор, санаи нашр, мақоми маҷалла, DOI, литсензия ва робитаи preprint-нашр истифода шудаанд; натиҷаи нави илмӣ аз берун аз PDF илова нашудааст.
Муҳимтарин ҳадди тафсир: Эҳтимоли муваффақият ва ҳудудҳои арзиши таҳқиқот ба алгоритми мантиқии квантӣ дахл доранд. Хатоҳои сахтафзори физикӣ, ислоҳи хатои квантӣ ва хароҷоти иловагии захираҳои физикӣ дар ин таҳлил ҷой надоранд.
Шарҳ гузоред
Нишонии почтаи электронии шумо нашр намешавад. Майдонҳои ҳатмӣ бо * нишон дода шудаанд