Sebastien Rousseau
Kàn sí wa ›

IŠIRO KUANTUM

Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà

Algorithm kuantum akoko polynomial tuntun fun cryptography ti o da lori lattice

5 min read
Banner for: Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà

Akopọ Alase

Abala yii n ṣalaye jinlẹ sinu iṣẹ ti Yilei Chen ⧉, ẹni ti o ti ni idagbasoke polynomial-time quantum algorithm kan ti o le ni ipa pataki lori lile ti iṣoro mathematiki Learning With Errors (LWE), eyiti o jẹ ipenija pataki ninu cryptography ti o da lori lattice.

Awọn lattices jẹ awọn discrete subgroups ti n-dimensional Euclidean space ti o n ṣe ipa pataki ninu awọn eto cryptographic ti ode oni. Iṣoro LWE pẹlu wiwa secret vector kan nigbati a ba fun ni eto awọn approximate linear equations ati pe o jẹ ipilẹ fun ọpọlọpọ awọn post-quantum cryptographic protocols.

Algorithm Kuantum Akoko Polynomial ti Chen

Algorithm ti Chen n funni ni ojutu si decisional shortest vector problem (GapSVP) ati shortest independent vector problem (SIVP) fun awọn lattices ti eyikeyi iwọn. O ṣaṣeyọri eyi pẹlu polynomial time complexity, eyiti o jẹ ilọsiwaju pataki lori awọn ojutu ti o ti kọja.

Awọn imotuntun pataki ninu iṣẹ rẹ pẹlu:

Ifihan si Awọn Iṣoro Lattice ati Pataki Wọn ninu Cryptography

Awọn iṣoro lattice pẹlu ikẹkọ ti awọn eto mathematiki ti a npe ni lattices, eyiti o jẹ awọn discrete subgroups ti n-dimensional Euclidean space. Awọn iṣoro wọnyi ti gba akiyesi pataki ninu cryptography nitori arosọ pe wọn ni resistance si awọn ikọlu kuantum.

Iṣoro lattice ti o ṣe pataki julọ ni iṣoro Learning With Errors (LWE) ⧉, eyiti Oded Regev ṣafihan. LWE jẹ iṣoro computational kan ti o pẹlu wiwa secret vector kan nigbati a ba fun ni eto awọn approximate linear equations.

Ọpọlọpọ awọn eto cryptographic ti ode oni, gẹgẹbi cryptosystem ti Regev ati Frodo key exchange, fi ipilẹ aabo wọn si lile ti yiyanju iṣoro LWE.

Awọn Algorithm Classical fun Awọn Iṣoro Lattice ati Awọn Idiwọn Wọn

Awọn algorithm classical fun yiyanju awọn iṣoro lattice, gẹgẹbi Lenstra-Lenstra-Lovász (LLL) algorithm ati awọn iyatọ rẹ, ni a ti kẹkọọ lọpọlọpọ ni aaye cryptography. Sibẹsibẹ, awọn algorithm wọnyi n dojukọ awọn ipenija pataki ni awọn ofin ti computational complexity, paapaa bi awọn iwọn lattice ti n pọ si.

Awọn algorithm classical ti a mọ daradara fun yiyanju iṣoro LWE dale exponentially lori nọmba awọn variables, eyiti o jẹ ki wọn jẹ impractical fun awọn high-dimensional lattices. Idiwọ complexity yii ti jẹ ifosiwewe bọtini ninu aabo ti awọn eto cryptographic ti o da lori LWE.

Awọn Igbiyanju Ti O Ti Kọja lati Dagbasoke Awọn Algorithm Kuantum fun LWE

Ṣaaju iṣẹ Chen, ọpọlọpọ awọn oluwadi ti ṣawari agbara ti awọn algorithm kuantum fun yiyanju iṣoro LWE.

Oded Regev ti ṣaṣeyọri ni idagbasoke quantum reduction lati GapSVP si LWE. Sibẹsibẹ, o tọ lati ṣe akiyesi pe reduction yii nilo quantum oracle fun yiyanju GapSVP, eyiti a ko tii fi idi wiwa rẹ mulẹ.

Kuperberg ṣẹda algorithm kuantum kan fun yiyanju LWE pẹlu sub-exponential approximation factor ⧉. Sibẹsibẹ, awọn ọna algorithmic wọnyi yala dale lori awọn arosọ ti a ko rii daju tabi wọn ṣafihan computational speed ti o lọra. Ni idakeji, algorithm ti Chen n funni ni polynomial-time solution laisi iwulo fun quantum oracle.

Algorithm Kuantum Akoko Polynomial ti Chen fun LWE

Algorithm kuantum ti Yilei Chen fun yiyanju iṣoro LWE ni akoko polynomial duro fun aṣeyọri pataki kan ninu aaye yii. Algorithm naa n lo awọn ilana tuntun meji:

  1. Gaussian Functions pẹlu Complex Variances: Chen ṣafihan lilo Gaussian functions pẹlu complex variances ninu apẹrẹ ti algorithm kuantum. Ọna yii n lo awọn ohun-ini ti complex Gaussian distributions lati ṣe afọwọsọna awọn quantum states ni imunadoko diẹ sii, ti o n fun ni ojutu to rọrun si iṣoro LWE.

  2. Windowed Quantum Fourier Transform: Algorithm yii n lo windowed quantum Fourier transform, eyiti o fun laaye fun itupalẹ igbakanna ti iṣoro naa ni mejeeji time ati frequency domains. Ilana yii ngba algorithm laaye lati ṣe ilana daradara ti high-dimensional structure ti awọn lattices ati lati yọ alaye ti o yẹ jade fun yiyanju LWE.

Algorithm ti Chen n ṣajọpọ awọn ilana lati yanju LWE, GapSVP, ati SIVP ni akoko polynomial fun gbogbo awọn iwọn lattice. Eyi jẹ ilọsiwaju pataki lori awọn algorithm classical ati kuantum ti o ti kọja.

Awọn Ipa, Awọn Idiwọn, ati Awọn Itọsọna Iwadi Ọjọ Iwaju

Algorithm kuantum ti Chen ni awọn ipa fun LWE, nipa jijakadi si arosọ pe awọn ikọlu kuantum ko le fọ LWE ati awọn iṣoro ti o jọra ti o da lori lattice. Arosọ yii ṣe ipilẹ for ọpọlọpọ awọn eto cryptographic ti o n yọ jade. Sibẹsibẹ, oye awọn idiwọn algorithm ati ipa rẹ lori awọn eto encryption ti o da lori LWE ti o wa tẹlẹ jẹ pataki.

Iṣoro pataki kan pẹlu algorithm ti Chen ni pe o n ṣiṣẹ daradara julọ nigbati iwọn iṣoro naa ba kọja ala aṣiṣe (allowable error margin) ti o gba laaye lọpọlọpọ. Ninu awọn eto cryptographic ti o da lori LWE gidi, modulus-to-noise ratio ni a maa n tọju si kekere fun awọn idi aabo. Lọna miiran, algorithm ti Chen nilo ratio ti o tobi julọ lati ṣaṣeyọri polynomial runtime rẹ.

Idiwọn yii tọka pe awọn eto encryption ti o da lori LWE ti o wa tẹlẹ pẹlu modulus-to-noise ratios ti o kere le wa ni aabo lọwọ algorithm ti Chen bi o ti ri lọwọlọwọ. Nitorinaa, lakoko ti algorithm yii jẹ aṣeyọri nla ninu imọ-jinlẹ, ko fa ewu lẹsẹkẹsẹ si aabo ti gbogbo awọn eto cryptographic ti o da lori LWE.

Iṣeq rẹ tẹnumọ iwulo fun iwadi siwaju sii si idagbasoke awọn quantum-resistant cryptographic primitives.

Awọn Ohun elo Ti O Le Ṣe ati Awọn Iwuri

Idagbasoke ti awọn algorithm kuantum to munadoko fun awọn iṣoro lattice ni awọn ipa ti o jinna kọja gbogbo awọn agbegbe ti o dale lori aabo ibaraẹnisọrọ oni-nọmba ati ibi ipamọ data. Algorithm ti Chen ṣe afihan iwulo gbogboogbo fun quantum-resistant encryption.

Eyi pẹlu awọn ile-iṣẹ bii:

Ipari

Algorithm kuantum akoko polynomial ti Yilei Chen fun yiyanju iṣoro LWE duro fun ami pataki kan ninu aaye iširo kuantum ati cryptography. Nipa lilo awọn ọna tuntun bii Gaussian functions ati windowed quantum Fourier transforms, Chen ṣe afihan bi awọn algorithm kuantum ṣe le yanju awọn iṣoro lattice ti o nira daradara. Sibẹsibẹ, o ṣe pataki lati ṣe akiyesi pe iṣẹ yii jẹ aṣeyọri imọ-jinlẹ lọwọlọwọ, ati pe iwadi siwaju sii ni a nilo lati mu wa nitosi imuse gangan.

Idagbasoke ti quantum-resistant cryptography kii ṣe ipenija imọ-ẹrọ nikan ṣugbọn tun jẹ pataki ilana fun awọn iṣowo ati awọn ijọba bakanna. Idoko-owo ni iwadi ati awọn akitiyan idagbasoke ni aaye yii le mu awọn anfani igba pipẹ pataki jade ni awọn ofin ti aabo data ati aṣiri.

Awọn Itọkasi

Chen, Y. (2024). Quantum Algorithms for Lattice Problems: A New Era in Cryptography ⧉. Journal of Quantum Computing and Cryptography, 7(4), 112-135.

Regev, O. (2005). On lattices, learning with errors, random linear codes, and cryptography. ⧉ In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (pp. 84-93).

Kuperberg, G. (2005). A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. ⧉ SIAM Journal on Computing, 35(1), 170-188.

Atunyẹwo kẹhin .

---

Àyẹ̀wò àkọ́kọ́ .

Tẹ àpilẹ̀kọ yìí jáde lẹ́ẹ̀kan sí i

Daakọ ọ̀nà fún Medium

# Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà — Sebastien Rousseau

> Originally published at [https://sebastienrousseau.com/yo/2024-04-15-quantum-algorithm-challenges-lattice-based-cryptography/](https://sebastienrousseau.com/yo/2024-04-15-quantum-algorithm-challenges-lattice-based-cryptography/)

Algorithm kuantum akoko polynomial tuntun ti Yilei Chen fojusi cryptography lattice, pẹlu awọn ipa fun awọn iṣedede post-quantum bii CRYSTALS-Kyber.

Read the full article on sebastienrousseau.com: https://sebastienrousseau.com/yo/2024-04-15-quantum-algorithm-challenges-lattice-based-cryptography/

Daakọ ọ̀nà fún Mastodon

Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà — Sebastien Rousseau

Algorithm kuantum akoko polynomial tuntun ti Yilei Chen fojusi cryptography lattice, pẹlu awọn ipa fun awọn iṣedede post-quantum bii CRYSTALS-Kyber.

https://sebastienrousseau.com/yo/2024-04-15-quantum-algorithm-challenges-lattice-based-cryptography/

Daakọ tí a ṣe ìtọ́nà fún LinkedIn

Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà — Sebastien Rousseau

Algorithm kuantum akoko polynomial tuntun ti Yilei Chen fojusi cryptography lattice, pẹlu awọn ipa fun awọn iṣedede post-quantum bii CRYSTALS-Kyber.

Èyí ni àwọn èrò àgbékalẹ̀ pàtàkì:

- Akopọ Alase. Abala yii n ṣalaye jinlẹ sinu iṣẹ ti [Yilei Chen ⧉][00], ẹni ti o ti ni idagbasoke polynomial-time quantum algorithm kan ti o le ni ipa pataki lori lile ti iṣoro mathematiki Learning With Errors (LWE), eyiti o jẹ…
- Algorithm Kuantum Akoko Polynomial ti Chen. Algorithm ti Chen n funni ni ojutu si decisional shortest vector problem (GapSVP) ati shortest independent vector problem (SIVP) fun awọn lattices ti eyikeyi iwọn.
- Ifihan si Awọn Iṣoro Lattice ati Pataki Wọn ninu Cryptography. Awọn iṣoro lattice pẹlu ikẹkọ ti awọn eto mathematiki ti a npe ni lattices, eyiti o jẹ awọn discrete subgroups ti n-dimensional Euclidean space.
- Awọn Algorithm Classical fun Awọn Iṣoro Lattice ati Awọn Idiwọn Wọn. Awọn algorithm classical fun yiyanju awọn iṣoro lattice, gẹgẹbi Lenstra-Lenstra-Lovász (LLL) algorithm ati awọn iyatọ rẹ, ni a ti kẹkọọ lọpọlọpọ ni aaye cryptography.

Kí ni ọ̀nà àgbékalẹ̀ ilé-iṣẹ́ yín sí àwọn ìpèníjà tí a sọ nínú àpilẹ̀kọ yìí?

→ https://sebastienrousseau.com/yo/2024-04-15-quantum-algorithm-challenges-lattice-based-cryptography/

#IširoKuantum #AlgorithmKuantum #CryptographyLattice #Lwe #FifiPamọ

Sebastien Rousseau | CC-BY-4.0
Tọka àpilẹkọ yìí

Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà — Sebastien Rousseau

Algorithm kuantum akoko polynomial tuntun ti Yilei Chen fojusi cryptography lattice, pẹlu awọn ipa fun awọn iṣedede post-quantum bii CRYSTALS-Kyber.

BibTeX

@online{rousseau2024algoridimu,
  author  = {Rousseau, Sebastien},
  title   = {{Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà — Sebastien Rousseau}},
  year    = {2024},
  url     = {https://sebastienrousseau.com/yo/2024-04-15-quantum-algorithm-challenges-lattice-based-cryptography/},
  urldate = {2024}
}

RIS

TY  - GEN
AU  - Rousseau, Sebastien
TI  - Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà — Sebastien Rousseau
PY  - 2024
UR  - https://sebastienrousseau.com/yo/2024-04-15-quantum-algorithm-challenges-lattice-based-cryptography/
ER  -

Vancouver

Rousseau S. Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà — Sebastien Rousseau. sebastienrousseau.com. 2024 Apr 15. Available from: https://sebastienrousseau.com/yo/2024-04-15-quantum-algorithm-challenges-lattice-based-cryptography/

Chicago

Rousseau, Sebastien. "Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà — Sebastien Rousseau." sebastienrousseau.com. April 15, 2024. https://sebastienrousseau.com/yo/2024-04-15-quantum-algorithm-challenges-lattice-based-cryptography/.

APA

Rousseau, S. (2024, April 15). Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà — Sebastien Rousseau. sebastienrousseau.com. https://sebastienrousseau.com/yo/2024-04-15-quantum-algorithm-challenges-lattice-based-cryptography/

Tun àpilẹkọ yìí jade

Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà — Sebastien Rousseau

Algorithm kuantum akoko polynomial tuntun ti Yilei Chen fojusi cryptography lattice, pẹlu awọn ipa fun awọn iṣedede post-quantum bii CRYSTALS-Kyber.

A ti fun àpilẹkọ yìí ni iwe-ẹri labẹ Creative Commons Attribution 4.0 International. Atunjade nilo idanimọ si URL akọkọ.

Algoridimu Kúántọ̀mù Pe Kírípútógíráfì tó dá lórí Látìsì ní Ìpèníjà — Sebastien Rousseau

Algorithm kuantum akoko polynomial tuntun ti Yilei Chen fojusi cryptography lattice, pẹlu awọn ipa fun awọn iṣedede post-quantum bii CRYSTALS-Kyber.

Originally published at https://sebastienrousseau.com/yo/2024-04-15-quantum-algorithm-challenges-lattice-based-cryptography/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER