Utafiti huu unatoa kikomo cha chini cha kihisabati kisichotegemea uigaji kwa uwezekano kwamba algoriti ya quantum ya Ekerå–Håstad inaweza kutatua tatizo la logarithmu fupi ya diskriti (short discrete logarithm problem, short DLP) katika utekelezaji mmoja tu wa quantum, na pia unaweka kikomo cha juu kwa gharama ya ukokotoaji inayohitajika kuchakata matokeo hayo kwa njia ya klasiki. Matokeo makuu yanaonyesha kwamba, kwa uchaguzi unaofaa wa vigezo na post-processing ya klasiki, kikomo cha chini cha kinadharia cha mafanikio ya kurejesha logarithmu fupi \(d\) katika utekelezaji mmoja kinaweza kuinuliwa hadi kiwango cha \(1-10^{-10}\). Uwezekano huu mkubwa wa mafanikio haupatikani hasa kwa kuongeza ukubwa wa sehemu ya quantum, bali kwa kutumia mbinu za meet-in-the-middle au random-walk zenye mahitaji madogo ya kumbukumbu katika uchakataji wa klasiki wa jozi \((j,k)\) inayotoka kwenye kipimo cha quantum kwa kutumia tatizo la lattice. Matokeo yanahusu saketi za quantum za kihisabati na kimantiki; viwango vya makosa vya vifaa halisi vya quantum na mzigo wa quantum error correction havijajumuishwa.

Mchango muhimu wa utafiti ni kubadilisha tabia ya mafanikio ambayo hapo awali ilichunguzwa kwa uigaji na mipaka thabiti ya uwezekano na uchangamano. Algoriti inalenga thamani fupi \(d\) katika uhusiano \(x=g^d\) ndani ya kundi la mzunguko lenye order isiyojulikana. Katika sehemu ya quantum, matokeo mawili ya Fourier sampling, \(j\) na \(k\), yanazalishwa; katika sehemu ya klasiki, thamani hizi huchakatwa kupitia tatizo la lattice la vipimo viwili ili kupata \(d\).

Kuna mabadilishano ya gharama yaliyo wazi kati ya vigezo. \(\Delta\) inapoongezwa, idadi ya operesheni za kundi zinazohitaji kutathminiwa kwenye kompyuta ya quantum inaweza kupungua; kwa upande mwingine, eneo la utafutaji wa klasiki na gharama ya post-processing huongezeka. Katika mfano wa FF-DH wenye safe prime ya biti 2048, utafiti unaonyesha kupungua kutoka operesheni 672 za kundi la quantum kwa \(\Delta=0\) hadi operesheni 572 kwa kuchagua \(\Delta=50\). Majaribio ya utekelezaji ya mwandishi yanaeleza kuwa upungufu huu wa takriban %15 unaweza kufikiwa huku post-processing ya klasiki ikiendelea kuwa ya kutekelezeka kwa vigezo vilivyochaguliwa.

Tatizo la logarithmu fupi ya diskriti ni nini?

Katika short DLP inayochunguzwa, generator \(g\) wa kundi la mzunguko lenye order \(r\) na thamani

\[ x=g^d \]

hutolewa. Lengo ni kukokotoa logarithmu fupi ya diskriti \(d\) chini ya sharti \(d\ll r\). Sifa muhimu ya utafiti huu ni kwamba order ya kundi \(r\) si lazima ijulikane.

\(m\) huchukuliwa kuwa kikomo cha juu cha urefu wa biti wa \(d\), hivyo

\[ d<2^m \]

hutumika. Makala pia hufafanua kigezo

\[ \ell=m-\Delta \]

. \(\Delta\) ina jukumu kuu katika mabadilishano kati ya gharama ya sehemu ya quantum na utafutaji wa klasiki unaofuata.

Mbinu ya Ekerå–Håstad inatofautianaje na algoriti ya Shor?

Algoriti ya awali ya Shor ya logarithmu ya diskriti hushughulikia logarithmu za diskriti za jumla katika makundi ya mzunguko yenye order inayojulikana, ilhali mbinu ya Ekerå–Håstad inayochunguzwa hapa inalenga logarithmu fupi wakati order ya kundi haijulikani.

Utafiti unaeleza kuwa sifa hii ina umuhimu wa cryptoanalysis, hasa kwa mifumo ya finite-field Diffie–Hellman inayotumia exponents fupi katika makundi ya safe-prime na kwa kupunguza tatizo la factoring ya integers katika RSA hadi short DLP.

Algoriti ya quantum huunda hali gani?

Algoriti kwanza huunda superposition sawia juu ya thamani \(a\) na \(b\), na katika work register hukokotoa

\[ g^a x^{-b}=g^{a-bd} \]

. Hali kabla ya QFT hutolewa katika chanzo kama:

\[ \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 . \]

Kisha quantum Fourier transforms (QFT) za ukubwa \(2^{m+\ell}\) na \(2^\ell\) hutumika kwa control registers mbili za kwanza. Control registers zinapopimwa, thamani \(j\) na \(k\) hupatikana.

Kielelezo 1 mwishoni mwa makala kinaonyesha saketi hii moja kwa moja: control register ya kwanza hushughulikia uzalishaji wa \(g^a\), control register ya pili hubeba sehemu ya \(x^{-b}\), na work register huunganisha hizo kwa operesheni ya kundi. Kila control register ina QFT na kipimo.

Kwa nini mpangilio wa pili wa saketi ni muhimu?

Kielelezo 2 kinapanga upya operesheni ileile ya kihisabati na kuonyesha kwamba \(j\) inaweza kukokotolewa kwanza, kisha \(k\) ikakokotolewa huku \(j\) ikiwa tayari inajulikana. Mpangilio huu hupunguza hitaji la kushikilia control registers zote mbili kwa wakati mmoja.

Kulingana na chanzo, katika mpangilio wa kawaida ukubwa wa jumla wa control registers mbili ni \(m+2\ell\) qubit, lakini kwa kupanga upya operesheni eneo la udhibiti linalohitajika kwa wakati mmoja linaweza kupunguzwa hadi \(m+\ell\) qubit. Makala pia inaeleza kwamba kwa semi-classical QFT na kurejeleza control qubit, kazi ya control registers mbili inaweza kufanywa na control qubit moja inayotumiwa tena; uboreshaji huu si sehemu kuu ya uchambuzi, bali umewekwa kama dokezo kuhusu utekelezaji wa saketi.

Gharama kuu katika sehemu ya quantum ni nini?

Katika utafiti, sehemu inayotawala gharama ya quantum huchukuliwa kuwa operesheni mbili za exponentiation. Idadi ya operesheni za kundi zinazopaswa kutathminiwa katika utekelezaji mmoja ni

\[ m+2\ell \]

na kwa kuwa \(\ell=m-\Delta\):

\[ m+2\ell=3m-2\Delta. \]

Kwa hiyo, kwa \(\Delta=0\), gharama iko katika kiwango cha operesheni \(3m\) za kundi. Kuongeza \(\Delta\) hupunguza idadi ya operesheni za quantum, lakini kama inavyoonekana baadaye, huongeza gharama ya utafutaji wa klasiki.

Vipimo vya \(j\) na \(k\) hubebaje taarifa kuhusu logarithmu?

Kwa jozi inayopatikana kutokana na kipimo, utafiti hufafanua

\[ \alpha_d=\alpha(j,k) =\{dj+2^mk\}_{2^{m+\ell}} \]

na pembe inayolingana

\[ \theta_d= \frac{2\pi\alpha_d}{2^{m+\ell}} \]

. Hapa \(\{u\}_n\) inamaanisha thamani ya \(u\) iliyopunguzwa modulo \(n\) hadi katika interval iliyowekwa katikati.

Sehemu muhimu ya uthibitisho ni kuonyesha kuwa \(j\) huchaguliwa kwa usambazaji sawia kutoka kwa integers katika

\[ [0,2^{m+\ell}) \]

. Katika utekelezaji wa saketi, \(j\) inaweza kukokotolewa kwanza; kisha \(k\) hupimwa kulingana na usambazaji wa uwezekano wa quantum uliowekwa chini ya \(j\) hiyo.

Jozi ya \(\tau\)-good ni nini?

Ili post-processing ya klasiki ifanye kazi kwa mafanikio, mwandishi hutumia ufafanuzi ufuatao. Jozi \((j,k)\)

\[ \left| \{dj+2^mk\}_{2^{m+\ell}} \right| \leq 2^{m+\tau} \]

ikitimiza sharti hili inaitwa \(\tau\)-good. Hapa

\[ \tau\in[0,\ell]\cap\mathbb Z. \]

\(\tau\) inapoongezwa, eneo la matokeo ya vipimo yanayokubalika kama “mazuri” hupanuka na hivyo uwezekano wa kupata kipimo chenye mafanikio huongezeka; kwa upande mwingine, eneo ambalo utafutaji wa lattice wa klasiki lazima ushughulikie pia linaweza kuongezeka.

Ni kikomo gani kinathibitishwa kwa uwezekano wa jozi ya \(\tau\)-good?

Lemma 1 inaweka kikomo cha chini kwa uwezekano kwamba \(k\) iliyopimwa kwa \(j\) isiyobadilika itaunda jozi ya \(\tau\)-good:

\[ P_{\tau\text{-good}} \geq 1-\psi'(2^\tau) \]

na kwa kutumia kikomo cha juu kwa trigamma function:

\[ P_{\tau\text{-good}} > 1- \frac{1}{2^\tau} - \frac{1}{2\cdot2^{2\tau}} - \frac{1}{6\cdot2^{3\tau}}. \]

Hii si asilimia ya mafanikio ya majaribio. Ni kikomo cha chini cha kiuchanganuzi kinachotokana na usambazaji wa uwezekano wa kihisabati wa algoriti ya quantum.

Kwa nini lattice iko katikati ya post-processing ya klasiki?

Kwa \(j\) iliyopimwa, utafiti huunda lattice ya vipimo viwili

\[ L^\tau(j) = \langle (j,2^\tau), (2^{m+\ell},0) \rangle \]

.

Jozi \((j,k)\) ikiwa \(\tau\)-good, vector inayojulikana

\[ v= (\{-2^mk\}_{2^{m+\ell}},0) \]

na vector isiyojulikana inayobeba \(d\)

\[ u= (dj+2^{m+\ell}z,2^\tau d) \]

huwa karibu. Katika utafiti ukaribu huu

\[ \|u-v\|<2^{m+\tau}\sqrt 2 \]

unawekewa kikomo.

Kwa hiyo tatizo hubadilika kuwa kutafuta vector inayofaa ya \(L^\tau(j)\) ndani ya radius fulani kuzunguka \(v\).

Lattice ya \(t\)-balanced ina maana gani?

Ikiwa \(\lambda_1\) ni norm ya vector fupi zaidi isiyo sifuri ya lattice, utafiti hutumia sharti

\[ \lambda_1\geq2^{m-t} \]

na lattice \(L^\tau(j)\) inayolitimiza huitwa \(t\)-balanced.

Kulingana na Lemma 2, uwezekano wa lattice kutokuwa \(t\)-balanced ni si zaidi ya

\[ 2^{\Delta-2(t-1)-\tau} \]

, hivyo uwezekano wa kuwa \(t\)-balanced una kikomo cha chini

\[ P_{\mathrm{balanced}} \geq 1-2^{\Delta-2(t-1)-\tau} \]

; maeneo ya vigezo ambapo usemi unaweza kuwa hasi yanawekewa sifuri katika theorem kuu.

Kikomo kikuu cha uwezekano wa mafanikio

Theorem 1 na Theorem 2 huunganisha uwezekano wa jozi ya \(\tau\)-good na lattice ya \(t\)-balanced. Hivyo kikomo cha chini cha mafanikio ya kurejesha logarithmu fupi ndani ya kikomo cha gharama ya klasiki kilicholengwa ni

\[ 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) \]

.

Hii ndiyo formula muhimu zaidi katika utafiti: inaonyesha moja kwa moja kihisabati uhusiano kati ya kuongeza uwezekano wa mafanikio na kupanua eneo la post-processing ya klasiki.

Suluhisho la kwanza la klasiki: meet-in-the-middle

Mbinu ya kwanza ya post-processing ni utafutaji wa deterministi wa meet-in-the-middle unaopanua baby-step giant-step ya Shanks hadi vipimo viwili.

Utafiti kwanza hukokotoa msingi wa lattice uliopunguzwa kwa Lagrange \((s_1,s_2)\). Kwa algoriti ya Babai nearest-plane, hupatikana nukta ya lattice \(o\) iliyo karibu na vector inayojulikana \(v\). Utafutaji kisha hupunguzwa hadi eneo lenye mipaka la vipimo viwili kuzunguka \(o\).

Kwa Theorem 1,

\[ N= 2^{\Delta+\tau+1} + 2^{\tau+t+2} + 2 \]

hufafanuliwa. Kwa constant chanya integer \(c\), kwa sharti kwamba baadhi ya group elements zimekokotolewa mapema, idadi ya operesheni za kundi zinazohitajika ni si zaidi ya

\[ 2^3c\sqrt N = 8c\sqrt N \]

.

Idadi ya integers zinazohitaji kuhifadhiwa katika lookup table ni si zaidi ya

\[ \frac{8\sqrt N}{c}+3 \]

. Kuongeza \(c\) hupunguza matumizi ya kumbukumbu lakini huongeza kazi katika awamu ya pili ya utafutaji, hivyo kutengeneza mabadilishano ya muda-kumbukumbu.

Suluhisho la pili la klasiki: random walk na Gaudry–Schost

Katika meet-in-the-middle, kumbukumbu inaweza kuwa kizuizi kikuu kwa vigezo vikubwa. Kwa hiyo utafiti unatoa suluhisho la pili: kubadilisha utafutaji wa lattice kuwa short DLP ya vipimo viwili na kutumia algoriti ya Gaudry–Schost pamoja na maboresho ya Galbraith–Ruprai.

Mbinu hii hutumia random-walk ya uwezekano badala ya lookup table kubwa ya deterministi na hupunguza mahitaji ya kumbukumbu hadi \(O(1)\) group element.

Kwa Theorem 2,

\[ N= 2^{\Delta+\tau+4} + 2^{\tau+t+5} + 5 \]

, na katika idealized model idadi inayotarajiwa ya operesheni za kundi katika hali bora, wastani na mbaya zaidi inawekewa kikomo cha juu na

\[ \left(\frac{4}{3}+o(1)\right)\sqrt{\pi N} \]

.

Hapa matokeo ni uchangamano unaotarajiwa na yanategemea idealized model ya uchanganuzi wa Gaudry–Schost; hayapaswi kutafsiriwa kama muda kamili wa utekelezaji wa deterministi.

Vigezo \(\Delta\), \(\tau\) na \(t\) hubadilisha nini?

Uwezekano wa mafanikio unaweza kuongezwa kwa kiwango gani?

Jedwali 1 la utafiti linaonyesha wazi jinsi mzigo wa kazi ya klasiki na kikomo cha chini cha mafanikio kilichothibitishwa hubadilika kwa \(\Delta=0\):

Thamani hizi si viwango vya mafanikio vilivyopimwa kwa majaribio. Ni mchanganyiko uliochaguliwa wa mipaka ya chini na ya juu ya kihisabati iliyohakikishwa inayotokana na Theorem 1.

Ni nini hutokea \(\Delta\) inapoongezeka?

Jedwali 1 na Jedwali 2 vikichunguzwa pamoja, mwelekeo mkuu ni wazi: wakati uwezekano uleule wa mafanikio unalengwa, gharama ya classical enumeration huongezeka sana kadiri \(\Delta\) inavyoongezeka.

Kwa mfano, kwa kikomo cha chini cha mafanikio \(1-10^{-10}\):

Kwa hiyo kuongeza \(\Delta\) kila mara ili kupunguza gharama ya quantum si uboreshaji wa bure. Ukokotoaji wa quantum unapungua, lakini ukokotoaji wa klasiki na, ikiwa meet-in-the-middle inatumika, mahitaji ya kumbukumbu huongezeka haraka.

Idadi ya operesheni za quantum hubadilikaje katika mifano ya FF-DH?

Jedwali 3 la utafiti hutumia idadi ya operesheni za kundi la quantum za algoriti ya Ekerå–Håstad kama

\[ o_{\mathrm{EH}}=3m-2\Delta \]

. Katika mfano wa safe-prime wa biti 2048 na exponent fupi ya \(m=224\) biti, chanzo kinatoa:

Mfano wa \(\Delta=50\) unamaanisha kupungua kutoka operesheni 672 hadi 572 za kundi la quantum. Kwa tathmini ya utafiti wenyewe, hii ni kupungua kwa takriban %15 kwa operesheni za kundi la quantum. Kwa upande mwingine, kikomo cha juu cha kazi ya klasiki huongezeka kutoka 22,1 hadi 33,6 katika kipimo cha \(\log_2\).

Mwandishi anaripoti kwamba katika majaribio ya awali ya utekelezaji ulioboreshwa na wa sambamba, kwa \(\Delta=50\) na lengo la angalau %99 mafanikio, kufanya post-processing kwenye kompyuta ya kawaida kwa ujumla hakukuwa tatizo. Hii ni taarifa ya uzoefu wa utekelezaji na imeripotiwa kando na theorem ya kihisabati.

Utafiti unasemaje kuhusu RSA?

Utafiti unachunguza pia matumizi ya mfumo huohuo wa uchambuzi wa mafanikio kwa RSA kupitia kupunguza tatizo la factoring ya integers hadi short DLP. Hata hivyo, kuna sharti la ziada: \(g\) iliyochaguliwa kwa nasibu lazima iwe na order kubwa vya kutosha.

Kwa RSA, Jedwali 4 huzingatia kipengele hiki cha ziada cha kupunguza uwezekano kwa \(f(\Delta)\). Kwa mfano, kwa \(\Delta=20\), chanzo hutumia

\[ f(20)\geq0{,}999867 \]

. Katika familia hiyo hiyo ya vigezo:

Jedwali hili halimaanishi kwamba ufunguo wa RSA unaweza kuvunjwa kwenye kompyuta ya quantum ya sasa kwa idadi hii ya operesheni. Utafiti hapa unachanganua uwezekano wa mafanikio ya algoriti na gharama ya classical enumeration; physical qubit, error correction, gate error na muda halisi wa utekelezaji kwa ujumla havimo kwenye hesabu.

Kwa nini matokeo ya asymptotic ni muhimu?

Corollary 1 inaonyesha kwamba kadiri ukubwa wa tatizo \(m\) unavyoelekea infinity, \(\Delta\), \(\tau\) na \(t\) vinaweza kuchaguliwa kutegemea \(m\) ili kikomo cha chini cha uwezekano wa mafanikio kikaribie 1 huku uchangamano wa classical enumeration ukibaki ndani ya

\[ O(\mathrm{poly}(m)) \]

.

Kwa mfano, utafiti unaeleza kwamba kuweka \(\Delta\) na \(t\) kuwa constants na kuchagua

\[ \tau=\log_2 f(m) \]

kunaweza kutoa matokeo haya kwa \(f(m)\) inayofaa ambayo ni super-constant lakini polynomially bounded.

Matokeo yanayoungwa mkono na utafiti

• Mipaka thabiti ya chini isiyotegemea simulation inaweza kupatikana kwa uwezekano wa mafanikio ya single-run ya algoriti ya Ekerå–Håstad short DLP.
• Kwa vigezo vinavyofaa vya classical post-processing, kikomo cha chini cha uwezekano wa mafanikio kinaweza kuongezwa hadi \(1-10^{-10}\).
• Utafutaji wa meet-in-the-middle hutoa uharakishaji wa deterministi kwa tatizo la lattice enumeration lenye mipaka.
• Mbinu ya random-walk inayotegemea Gaudry–Schost inaweza kupunguza hitaji la kumbukumbu la tatizo hilo hilo hadi \(O(1)\) group element.
• Kuongeza \(\Delta\) hupunguza operesheni za kundi za quantum zinazohitajika lakini huongeza gharama ya classical post-processing.
• Uchambuzi unatumika moja kwa moja kwa safe-prime FF-DH yenye exponents fupi na kwa RSA kupitia short DLP reduction.
• Vigezo vikipimwa kulingana na ukubwa wa tatizo, kikomo cha chini cha mafanikio kinaweza kukaribia 1 asymptotically huku classical post-processing ikibaki katika polynomial time.

Matokeo ambayo utafiti hauthibitishi

• Utafiti haufanyi jaribio la kuvunja RSA au FF-DH kwenye kompyuta halisi ya quantum.
• Uwezekano wa mafanikio wa kinadharia si uwezekano kwamba hardware halisi ya quantum haitafanya kosa.
• Uchambuzi haukokotoi mzigo wa quantum error correction au gharama ya physical qubit.
• Idadi ya operesheni za kundi haiwezi kulinganishwa moja kwa moja na sekunde, quantum gates au idadi ya physical qubit.
• Uchangamano uliotolewa kwa random-walk ni uchangamano unaotarajiwa katika idealized model.
• Kuongeza \(\Delta\) hakupunguzi gharama zote; muda wa klasiki na/au gharama ya kumbukumbu huongezeka.
• Katika matumizi ya RSA, sharti la ziada la order la short DLP reduction na kipengele chake cha kupunguza mafanikio haviwezi kupuuzwa.

Mbinu na Matokeo ya Utafiti

Muundo wa utafiti

Huu si utafiti wa majaribio ya hardware ya quantum, bali uchambuzi wa kihisabati wa uwezekano wa mafanikio na uchangamano katika cryptography ya kinadharia na algoriti za quantum. Lengo kuu ni kubadilisha makadirio ya awali ya mafanikio yaliyotegemea simulation na mipaka ya chini iliyothibitishwa.

Uchambuzi una hatua kuu nne:

1. Usambazaji wa vipimo \((j,k)\) wa algoriti ya quantum unachanganuliwa.
2. Uwezekano kwamba \((j,k)\) ni \(\tau\)-good unawekewa kikomo cha chini.
3. Uwezekano kwamba lattice \(L^\tau(j)\) ni \(t\)-balanced unawekewa kikomo cha chini.
4. Haya yakitokea, gharama ya classical enumeration inayorejesha \(d\) inawekewa kikomo cha juu.

Jukumu la Lemma 1

Lemma 1 inachanganua uwezekano kwamba \(k\) iliyopimwa kwa \(j\) fulani itaangukia eneo sahihi la phase. Katika uthibitisho, tails chanya na hasi za usambazaji wa uwezekano zinawekewa mipaka ya juu tofauti. Mipaka ya trigonometria na trigamma function hutumiwa kudhibiti jumla ya uwezekano wa tail.

Matokeo:

\[ P_{\tau\text{-good}} > 1- 2^{-\tau} - \frac{1}{2}2^{-2\tau} - \frac{1}{6}2^{-3\tau}. \]

Jukumu la Lemma 2

Sehemu ya pili ya uwezekano hutoka kwenye geometry ya lattice. Kwa kuwa vector fupi zaidi isiyo sifuri ikiwa fupi mno huifanya enumeration kuwa ngumu kudhibiti, sharti la \(t\)-balanced hutumiwa.

Kutoka kwenye uhusiano wa eneo la msingi la lattice

\[ \lambda_1\lambda_2^\perp = 2^{m+\ell+\tau} \]

na usambazaji sawia wa \(j\), hupatikana

\[ P(L^\tau(j)\text{ balanced değil}) \leq 2^{\Delta-2(t-1)-\tau} \]

.

Meet-in-the-middle enumeration inawekewaje mipaka?

Kwa kutumia msingi uliopunguzwa kwa Lagrange na matokeo ya Babai nearest-plane, utafutaji hupunguzwa hadi eneo la indices lenye mipaka kwa indices mbili \(m_1\) na \(m_2\). Utafiti huweka mipaka kwa ukubwa wa eneo hili kwa \(B_1\) na \(B_2\).

Generalization ya vipimo viwili ya mbinu ya Shanks hugawanya utafutaji mara mbili badala ya kukagua wagombea wote \((2B_1+1)(2B_2+1)\) mmoja mmoja. Sehemu ya kwanza huandikwa kwenye lookup table, sehemu ya pili hutafuta matches kwenye jedwali.

Muundo huu ndio msingi wa uharakishaji wa meet-in-the-middle unaotoa utegemezi wa takriban square root kwa idadi ya wagombea.

Suluhisho la random-walk huondoa kizuizi gani?

Katika meet-in-the-middle, lookup table inapokua, kumbukumbu huwa bottleneck. Utafiti kwa hiyo huandika tena tatizo la enumeration kama short DLP ya vipimo viwili:

\[ g_1^{i_1}g_2^{i_2}=x' \]

.

Tatizo hili likitatuliwa kwa algoriti ya Gaudry–Schost na uboreshaji wa Galbraith–Ruprai, lookup table kubwa haihitajiki. Hivyo matumizi ya kumbukumbu yanaweza kushuka asymptotically hadi \(O(1)\) group element.

Ujumbe mkuu wa Jedwali 1 na Jedwali 2

Jedwali 1 na 2 yanaonyesha jinsi kikomo cha chini cha mafanikio na kikomo cha juu cha classical enumeration hubadilika \(\Delta\), \(\tau\) na \(t\) zinapobadilika. Mwelekeo unaojitokeza zaidi ni kwamba, \(\Delta\) inapoongezwa, kazi ya klasiki inayohitajika kufikia kiwango kilekile cha mafanikio huongezeka haraka.

Kwa mfano, kwa kikomo cha chini cha mafanikio cha %99, thamani ya “Work” ni si zaidi ya 8,6 kwa \(\Delta=0\), lakini ni 32,1 kwa \(\Delta=50\), 57,1 kwa \(\Delta=100\), na 72,1 kwa \(\Delta=130\). “Work” si idadi ya moja kwa moja ya operesheni; ni uwakilishi wa \(\log_2\) wa kikomo cha juu cha operesheni za kundi kilichofafanuliwa kwenye chanzo.

Ujumbe mkuu wa Jedwali 3

Jedwali la FF-DH linaonyesha mabadilishano ya gharama ya quantum na klasiki kwa kutumia vigezo vya kriptografia halisi. Linaonyesha urefu wa exponents fupi kwa makundi ya safe-prime ya biti 2048, 3072, 4096, 6144 na 8192, na kulinganisha idadi ya operesheni za kundi la quantum za Ekerå–Håstad na mbinu ya Shor iliyorekebishwa.

Kwa mfano, kwa safe-prime ya biti 4096 na exponent fupi ya \(m=304\) biti:

• \(\Delta=0\): operesheni 912 za kundi la quantum, advantage 9,0.
• \(\Delta=50\): operesheni 812 za kundi la quantum, advantage 10,0.
• \(\Delta=70\): operesheni 772 za kundi la quantum, advantage 10,5.

Lakini kuongezeka kwa advantage hii lazima kutathminiwe pamoja na kuongezeka kwa gharama ya classical post-processing.

Ujumbe mkuu wa Jedwali 4

Jedwali la RSA halizingatii tu kikomo cha mafanikio cha short DLP, bali pia uwezekano kwamba group element iliyochaguliwa katika RSA reduction haina order kubwa vya kutosha. Kwa hiyo, tofauti na jedwali la FF-DH, kuna kipengele cha ziada cha kupunguza \(f(\Delta)\).

Utafiti unaeleza kwamba \(f(\Delta)\) hukaribia 1 \(\Delta\) inapoongezeka, lakini gharama ya ukokotoaji ya njia ya analytic lower bound huongezeka haraka pamoja na \(\Delta\). Kwa sababu hiyo, si thamani zote za malengo ya juu sana ya mafanikio zimeorodheshwa.

Je, algoriti zilijaribiwa kwa vitendo?

Mwandishi anaripoti kwamba alitekeleza Algorithm 1 na Algorithm 2 za post-processing na kuthibitisha, kwa kuchakata matokeo yaliyoigizwa ya algoriti ya quantum, kwamba zinafanya kazi kama inavyotarajiwa.

Pia imeelezwa kuwa majaribio ya awali ya utekelezaji ulioboreshwa na sambamba kwa \(\Delta=50\), huku lengo la mafanikio likiwa angalau %99, yalionyesha kwamba post-processing kwenye kompyuta ya kawaida kwa ujumla haikuwa tatizo. Utafiti unaeleza wazi kwamba kazi ya uboreshaji na uparaleli zaidi bado inaendelea.

Ujumbe wa kisayansi wa Kielelezo 1 na Kielelezo 2

Kielelezo 1 kinaonyesha control register ya kwanza yenye \(m+\ell\) qubit, ya pili yenye \(\ell\) qubit, operesheni za kundi zinazodhibitiwa za \(g^a\) na \(x^{-b}\), blocks za QFT na vipimo vya \(j,k\) katika saketi moja.

Kielelezo 2 kinapanga upya saketi sawa kihisabati kwa muda. QFT na kipimo cha control register ya kwanza huwekwa mara moja baada ya operesheni ya \(g^a\), na control register ya pili huandaliwa baadaye. Kwa hivyo kukokotoa \(j\) kwanza na kupata \(k\) baadaye ikitegemea \(j\) kunalingana na muundo uliotumiwa katika uchanganuzi wa uwezekano wa Lemma 1.

Matokeo makuu ya kiasi

Nguvu kuu za utafiti

• Kuunga mkono tabia ya mafanikio ya single-run iliyokadiriwa hapo awali kwa simulation kwa mipaka ya chini ya kiuchanganuzi.
• Kutathmini gharama ya quantum na classical post-processing ndani ya familia moja ya vigezo.
• Kutoa kikomo cha juu wazi kwa classical enumeration pamoja na uwezekano wa mafanikio.
• Kutoa mbinu mbili za post-processing: deterministi yenye mabadilishano ya muda-kumbukumbu na probabilistic yenye kumbukumbu ndogo.
• Kutoa majedwali tofauti ya vigezo kwa FF-DH na RSA reduction.
• Algoriti za post-processing zimejaribiwa kwa utekelezaji kwenye matokeo ya quantum yaliyosimuliwa.

Vikwazo vikuu vya utafiti

• Uchambuzi mkuu wa kihisabati hudhani kompyuta ya quantum inaendesha algoriti kama ilivyofafanuliwa kihisabati bila computational errors.
• Mzigo wa kimwili na wa ukokotoaji wa quantum error correction haujajumuishwa.
• Uchambuzi umewekewa mipaka kwa logical quantum circuits na logical costs.
• Uchambuzi wa short DLP hutumia sharti la \(r\geq2^{m+\ell}+(2^\ell-1)d\); katika RSA sharti hili linahitaji kipengele cha ziada cha uwezekano.
• Kiasi cha kazi kwa mbinu ya Gaudry–Schost ni thamani inayotarajiwa katika idealized model.
• Kwa \(\Delta\) kubwa, mahitaji ya kumbukumbu ya meet-in-the-middle post-processing yanaweza kuzuia utekelezekaji wa vitendo.
• Matokeo ya utekelezaji wa post-processing ulioboreshwa na sambamba ni ya awali, na mwandishi anasema uboreshaji zaidi bado unaendelea.

Maelezo ya Chanzo na Mbinu

Jina kamili la kazi asili: On the success probability of the quantum algorithm for the short DLP

Mwandishi: Martin Ekerå.

Idadi ya waandishi: Mmoja.

Co-first author/equal contribution: Haitumiki; kazi ina mwandishi mmoja.

Mwandishi wa mawasiliano: Chanzo hakitumii alama maalum ya “corresponding author”. Barua pepe ya mawasiliano ya Martin Ekerå imetolewa.

Affiliations: KTH Royal Institute of Technology, Stockholm, Sweden; Swedish NCSA, Swedish Armed Forces, Stockholm, Sweden.

Jarida: IACR Communications in Cryptology.

Volume / issue: 3 / 1.

ISSN: 3006-5496.

Urefu: kurasa 32.

DOI: 10.62056/an2isgsfg

Kiungo rasmi cha uchapishaji: https://doi.org/10.62056/an2isgsfg

Mchapishaji / shirika la uchapishaji: International Association for Cryptologic Research (IACR).

Aina ya chanzo: Makala ya utafiti iliyopitiwa na wataalamu.

Hali ya peer review: Kazi imechapishwa katika jarida lililopitiwa na wataalamu. IACR Communications in Cryptology ni jarida lenye peer review kamili, na sera rasmi ya jarida inaeleza matumizi ya double-blind peer review.

Tarehe ya kuwasilishwa: 2 Februari 2026.

Tarehe ya kukubaliwa: 23 Aprili 2026.

Tarehe ya kuchapishwa: 4 Mei 2026.

Uhusiano na preprint: Matoleo ya awali ya kazi yalichapishwa chini ya arXiv:2309.01754. Rekodi ya arXiv inaunganisha na uchapishaji wa mwisho wa jarida na DOI 10.62056/an2isgsfg. Maelezo ya kisayansi katika makala hii ya Verianla yanategemea toleo lililochapishwa la kurasa 32 lililopakiwa na mtumiaji.

Leseni: Creative Commons Attribution 4.0 (CC BY 4.0). Hakimiliki inabaki kwa mwandishi/waandishi.

Ufadhili na msaada: Utafiti unaeleza kwamba ufadhili na msaada ulitolewa na Swedish NCSA; Swedish NCSA iko ndani ya Swedish Armed Forces. Ukokotoaji ulifanywa pia kwa rasilimali za KTH PDC chini ya National Academic Infrastructure for Supercomputing in Sweden (NAISS), iliyofadhiliwa kwa sehemu na Swedish Research Council grant agreement no. 2022-06725.

Shukrani: Mwandishi anamshukuru Johan Håstad kwa maoni na ushauri, na Joel Gärtner kwa kuonyesha tatizo katika Lemma 3 katika toleo la kwanza la preprint.

Maelezo ya data na programu: Utafiti hautegemei experimental dataset. Mwandishi anaripoti kuwa alitekeleza post-processing algorithms na kuzithibitisha kwa matokeo ya algoriti ya quantum yaliyosimuliwa. Makala inarejelea utekelezaji unaopatikana lakini ambao haujaoptimishwa wa Algorithm 1 na repository ya programu ya Quaspy kwa simulator.

Mgongano wa maslahi: Hakuna sehemu tofauti ya conflict-of-interest iliyotambuliwa katika kazi iliyopakiwa.

Michango ya mwandishi: Kazi ina mwandishi mmoja na hakuna taarifa tofauti ya CRediT iliyotolewa.

Mbinu kuu: Kuweka mipaka ya kiuchanganuzi kwa usambazaji wa vipimo wa Ekerå–Håstad short DLP quantum algorithm; uchambuzi wa lattice ya vipimo viwili; Lagrange reduction na Babai nearest-plane; meet-in-the-middle enumeration; reduction hadi short DLP ya vipimo viwili na uchambuzi wa Gaudry–Schost/Galbraith–Ruprai random-walk.

Kikomo cha maudhui ya kisayansi: Mechanisms za algoriti, formula, majedwali ya namba, matokeo ya FF-DH na RSA, observations za utekelezaji na limitations katika makala hii ya Verianla zinategemea kazi iliyopakiwa. Vyanzo vya nje vilitumika tu kuthibitisha bibliografia ya utambulisho wa kazi, tarehe ya uchapishaji, hali ya jarida, DOI, leseni na uhusiano wa preprint-uchapishaji; hakuna finding mpya ya kisayansi kutoka nje ya PDF iliyoongezwa.

Kikomo muhimu zaidi cha tafsiri: Uwezekano wa mafanikio na mipaka ya gharama ya utafiti inahusu logical quantum algorithm. Makosa ya hardware ya kimwili, quantum error correction na gharama za ziada za physical resources hazimo katika uchambuzi huu.