ในการเข้ารหัสลับการเรียนรู้ด้วยข้อผิดพลาด ( LWE ) เป็นปัญหาทางคณิตศาสตร์ที่ใช้กันอย่างแพร่หลายในการสร้างอัลกอริธึมการเข้ารหัสที่ปลอดภัย[ 1 ^{]โดยอิง}จากแนวคิดของการแสดงข้อมูลลับเป็นชุดสมการที่มีข้อผิดพลาด กล่าวอีกนัยหนึ่ง LWE เป็นวิธีซ่อนค่าของข้อมูลลับโดยการเพิ่มสัญญาณรบกวนเข้าไป^{[ 2 ]}ในเชิงเทคนิคมากขึ้น หมายถึงปัญหาการคำนวณของการอนุมานฟังก์ชัน เชิงเส้น α บน วงแหวนจำกัดจากตัวอย่างที่กำหนดซึ่งบางส่วนอาจมีข้อผิดพลาด ปัญหา LWE คาดว่าจะแก้ไขได้ยาก^{[ 1 ]}และด้วยเหตุนี้จึงมีประโยชน์ในการเข้ารหัสลับ ${\displaystyle n}$${\displaystyle f}$${\displaystyle y_{i}=f(\mathbf {x} _{i})}$

กล่าวโดยละเอียด ปัญหา LWE ถูกกำหนดดังนี้ ให้แทนวงแหวนของจำนวนเต็มมอดูลัสและให้ แทนเซตของเวกเตอร์บนมีฟังก์ชันเชิงเส้นที่ไม่ทราบค่า อยู่และอินพุตของปัญหา LWE คือตัวอย่างของคู่โดยที่และซึ่งทำให้ ด้วยความน่าจะเป็นสูงยิ่งไปกว่านั้น การเบี่ยงเบนจากความเท่าเทียมกันเป็นไปตามแบบจำลองสัญญาณรบกวนที่ทราบค่า ปัญหานี้ต้องการหาฟังก์ชันหรือค่าประมาณใกล้เคียงของ ฟังก์ชันนั้น ด้วยความน่าจะเป็นสูง ${\displaystyle \mathbb {Z} _{q}}$${\displaystyle q}$${\displaystyle \mathbb {Z} _{q}^{n}}$${\displaystyle n}$${\displaystyle \mathbb {Z} _{q}}$${\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}$${\displaystyle (\mathbf {x} ,y)}$${\displaystyle \mathbf {x} \in \mathbb {Z} _{q}^{n}}$${\displaystyle y\in \mathbb {Z} _{q}}$${\displaystyle y=f(\mathbf {x} )}$${\displaystyle f}$

ปัญหา LWE ถูกนำเสนอโดยOded Regevในปี 2548 ^{[ 3 ]} (ผู้ซึ่งได้รับรางวัล Gödel Prize ปี 2561 จากผลงานนี้) ซึ่งเป็นการขยายความของ ปัญหา การเรียนรู้ความเท่าเทียมกัน Regev แสดงให้เห็นว่าปัญหา LWE นั้นยากที่จะแก้ไขได้พอๆ กับปัญหาแลตทิซ กรณีที่เลวร้ายที่สุดหลายปัญหา ต่อมา ปัญหา LWE ได้ถูกนำมาใช้เป็นสมมติฐานความยากในการสร้างระบบการเข้ารหัสแบบกุญแจสาธารณะ [ ^{3 ] [ 4 ]}เช่นการแลกเปลี่ยนกุญแจการเรียนรู้แบบวงแหวนที่มีข้อผิดพลาด^โดย Peikert ^{[ 5 ]}

ให้ เป็นกลุ่มการบวกบนจำนวนจริงมอดูลหนึ่งให้เป็นเวกเตอร์คงที่ ให้เป็นการแจกแจงความน่าจะเป็นคงที่บนให้ เป็นการแจกแจงบน ที่ได้มาดังต่อไปนี้ ${\displaystyle \mathbb {T} =\mathbb {R} /\mathbb {Z} }$${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$${\displaystyle \phi }$${\displaystyle \mathbb {T} }$${\displaystyle A_{\mathbf {s} ,\phi }}$${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$

1. เลือกเวกเตอร์จากการกระจายแบบเอกรูปเหนือ,${\displaystyle \mathbf {a} \in \mathbb {Z} _{q}^{n}}$${\displaystyle \mathbb {Z} _{q}^{n}}$
2. เลือกหมายเลขจากชุดข้อมูล${\displaystyle e\in \mathbb {T} }$${\displaystyle \phi }$
3. จงประเมินค่าโดยที่คือผลคูณภายในมาตรฐานในการหารทำในฟิลด์ของจำนวนจริง (หรือในเชิงทางการมากขึ้น การ "หารด้วย" นี้ เป็นสัญลักษณ์แทน การแมปโฮโมมอร์ฟิซึมของกลุ่มไปยัง) และการบวกขั้นสุดท้ายอยู่ใน${\displaystyle t=\langle \mathbf {a} ,\mathbf {s} \rangle /q+e}$${\displaystyle \textstyle \langle \mathbf {a} ,\mathbf {s} \rangle =\sum _{i=1}^{n}a_{i}s_{i}}$${\displaystyle \mathbb {Z} _{q}^{n}}$${\displaystyle q}$${\displaystyle \mathbb {Z} _{q}\longrightarrow \mathbb {T} }$${\displaystyle 1\in \mathbb {Z} _{q}}$${\displaystyle 1/q+\mathbb {Z} \in \mathbb {T} }$${\displaystyle \mathbb {T} }$
4. แสดงผลคู่ดังกล่าวออกมา${\displaystyle (\mathbf {a} ,t)}$

ปัญหาการเรียนรู้ที่มีข้อผิดพลาด คือการหาคำตอบโดยที่สามารถเข้าถึงตัวอย่างที่เลือกได้จำนวนพหุนามจาก ${\displaystyle \mathrm {LWE} _{q,\phi }}$${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$${\displaystyle A_{\mathbf {s} ,\phi }}$

สำหรับทุก ๆให้แทนด้วยฟังก์ชันเกาส์เซียนหนึ่งมิติที่มีค่าเฉลี่ยเป็นศูนย์และความแปรปรวน นั่นคือ ฟังก์ชันความหนาแน่นคือโดยที่และให้เป็นการกระจายบน ที่ได้จากการพิจารณาโมดูลัสหนึ่ง เวอร์ชันของ LWE ที่พิจารณาในผลลัพธ์ส่วนใหญ่จะเป็น${\displaystyle \alpha >0}$${\displaystyle D_{\alpha }}$${\displaystyle \alpha ^{2}/(2\pi )}$${\displaystyle D_{\alpha }(x)=\rho _{\alpha }(x)/\alpha }$${\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}$${\displaystyle \Psi _{\alpha }}$${\displaystyle \mathbb {T} }$${\displaystyle D_{\alpha }}$${\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}$

ปัญหาLWEที่อธิบายไว้ข้างต้นเป็น เวอร์ชัน การค้นหาของปัญหา ใน เวอร์ชัน การตัดสินใจ ( DLWE ) เป้าหมายคือการแยกแยะระหว่างผลคูณภายในที่มีเสียงรบกวนและตัวอย่างสุ่มแบบสม่ำเสมอจาก(ในทางปฏิบัติคือเวอร์ชันแบบไม่ต่อเนื่องบางอย่าง) Regev ^{[ 3 ]}แสดงให้เห็นว่า เวอร์ชัน การตัดสินใจและการค้นหาเทียบเท่ากันเมื่อเป็นจำนวนเฉพาะที่ถูกจำกัดด้วยพหุนามบางตัวใน ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$${\displaystyle q}$${\displaystyle n}$

โดยสัญชาตญาณแล้ว หากเรามีขั้นตอนสำหรับปัญหาการค้นหา ปัญหาการตัดสินใจก็จะสามารถแก้ไขได้ง่ายเช่นกัน เพียงแค่ป้อนตัวอย่างข้อมูลสำหรับปัญหาการตัดสินใจให้กับตัวแก้ปัญหาสำหรับปัญหาการค้นหา กำหนดให้ตัวอย่างที่กำหนดเป็นถ้าตัวแก้ปัญหาให้ผลลัพธ์เป็นผู้สมัครสำหรับทุกให้คำนวณถ้าตัวอย่างมาจากการแจกแจงแบบ LWE ผลลัพธ์ของการคำนวณนี้จะมีการแจกแจงตามแต่ถ้าตัวอย่างเป็นการสุ่มแบบสม่ำเสมอ ปริมาณเหล่านี้ก็จะมีการแจกแจงแบบสม่ำเสมอเช่นกัน ${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }$${\displaystyle \mathbf {s} }$${\displaystyle i}$${\displaystyle \{\langle \mathbf {a} _{i},\mathbf {s} \rangle -\mathbf {b} _{i}\}}$${\displaystyle \chi }$

สำหรับทิศทางตรงกันข้าม เมื่อมีตัวแก้ปัญหาสำหรับปัญหาการตัดสินใจแล้ว เวอร์ชันการค้นหาสามารถแก้ไขได้ดังนี้: กู้คืนพิกัดทีละพิกัด เพื่อให้ได้พิกัดแรกให้เดาค่าและดำเนินการดังต่อไปนี้ เลือกหมายเลขแบบสุ่มอย่างสม่ำเสมอ แปลงตัวอย่างที่กำหนดดังต่อไปนี้ คำนวณส่งตัวอย่างที่แปลงแล้วไปยังตัวแก้ปัญหาการตัดสินใจ ${\displaystyle \mathbf {s} }$${\displaystyle \mathbf {s} _{1}}$${\displaystyle k\in \mathbb {Z} _{q}}$${\displaystyle r\in \mathbb {Z} _{q}}$${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }$${\displaystyle \{(\mathbf {a} _{i}+(r,0,\ldots ,0),\mathbf {b} _{i}+(rk)/q)\}}$

ถ้าการเดาถูกต้อง การแปลงจะนำการกระจายไปสู่ตัวมันเอง และถ้าไม่ถูกต้อง เนื่องจากเป็นจำนวนเฉพาะ การแปลงจะนำไปสู่การกระจายแบบเอกรูป ดังนั้น เมื่อมีตัวแก้ปัญหาการตัดสินใจที่ใช้เวลาแบบพหุนามซึ่งผิดพลาดด้วยความน่าจะเป็นน้อยมาก เนื่องจากถูกจำกัดด้วยพหุนามบางตัวในจึงใช้เวลาเพียงพหุนามในการเดาค่าที่เป็นไปได้ทั้งหมดสำหรับและใช้ตัวแก้ปัญหาเพื่อดูว่าค่าใดถูกต้อง ${\displaystyle k}$${\displaystyle A_{\mathbf {s} ,\chi }}$${\displaystyle q}$${\displaystyle q}$${\displaystyle n}$${\displaystyle k}$

หลังจากได้รับแล้วเราจะทำตามขั้นตอนที่คล้ายคลึงกันสำหรับพิกัดอื่นๆกล่าวคือ เราจะแปลงตัวอย่างของเราในลักษณะเดียวกัน และแปลงตัวอย่างของเราโดยการคำนวณโดยที่อยู่ในพิกัด^{[ 3 ]}${\displaystyle \mathbf {s} _{1}}$${\displaystyle \mathbf {s} _{j}}$${\displaystyle \mathbf {b} _{i}}$${\displaystyle \mathbf {a} _{i}}$${\displaystyle \mathbf {a} _{i}+(0,\ldots ,r,\ldots ,0)}$${\displaystyle r}$${\displaystyle j^{\text{th}}}$

Peikert ^{[ 4 ]}แสดงให้เห็นว่าการลดรูปนี้ ด้วยการดัดแปลงเล็กน้อย ใช้ได้กับทุก ๆที่เป็นผลคูณของจำนวนเฉพาะขนาดเล็กที่แตกต่างกัน (พหุนามใน ) แนวคิดหลักคือ ถ้าสำหรับแต่ละให้เดาและตรวจสอบว่าสอดคล้องกับ หรือ ไม่ จากนั้นใช้ทฤษฎีบทเศษเหลือของจีนเพื่อกู้คืน ${\displaystyle q}$${\displaystyle n}$${\displaystyle q=q_{1}q_{2}\cdots q_{t}}$${\displaystyle q_{\ell }}$${\displaystyle \mathbf {s} _{j}}$${\displaystyle 0\mod q_{\ell }}$${\displaystyle \mathbf {s} _{j}}$

Regev ^{[ 3 ]}แสดงให้เห็นถึงการลดตัวเองแบบสุ่มของ ปัญหา LWEและDLWEสำหรับและ ที่กำหนดโดยพลการ เมื่อกำหนดตัวอย่างจากจะเห็นได้ง่ายว่าเป็นตัวอย่างจาก ${\displaystyle q}$${\displaystyle \chi }$${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}}$${\displaystyle A_{\mathbf {s} ,\chi }}$${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q\}}$${\displaystyle A_{\mathbf {s} +\mathbf {t} ,\chi }}$

ดังนั้น สมมติว่ามีเซตบางเซตที่และสำหรับการแจกแจงโดยที่DLWE นั้นง่าย ${\displaystyle {\mathcal {S}}\subset \mathbb {Z} _{q}^{n}}$${\displaystyle |{\mathcal {S}}|/|\mathbb {Z} _{q}^{n}|=1/\operatorname {poly} (n)}$${\displaystyle A_{\mathbf {s} ',\chi }}$${\displaystyle \mathbf {s} '\leftarrow {\mathcal {S}}}$

จากนั้นก็จะมีตัวแยกแยะบางอย่างซึ่งเมื่อได้รับตัวอย่างแล้วจะสามารถบอกได้ว่าตัวอย่างเหล่านั้นเป็นการสุ่มแบบสม่ำเสมอหรือมาจากถ้าเราต้องการแยกแยะตัวอย่างสุ่มแบบสม่ำเสมอออกจากโดยที่ถูกเลือกแบบสุ่มอย่างสม่ำเสมอจากเราสามารถลองใช้ค่าต่างๆที่สุ่มแบบสม่ำเสมอจากคำนวณและป้อนตัวอย่างเหล่านี้ให้กับเนื่องจากประกอบด้วยสัดส่วนที่มากของด้วยความน่าจะเป็นสูง ถ้าเราเลือกค่าจำนวนพหุนามสำหรับเราจะพบค่าหนึ่งที่ทำให้และจะสามารถแยกแยะตัวอย่างได้สำเร็จ ${\displaystyle {\mathcal {A}}}$${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}}$${\displaystyle A_{\mathbf {s} ',\chi }}$${\displaystyle A_{\mathbf {s} ,\chi }}$${\displaystyle \mathbf {s} }$${\displaystyle \mathbb {Z} _{q}^{n}}$${\displaystyle \mathbf {t} }$${\displaystyle \mathbb {Z} _{q}^{n}}$${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i}+\langle \mathbf {a} _{i},\mathbf {t} \rangle )/q\}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle \mathbb {Z} _{q}^{n}}$${\displaystyle \mathbf {t} }$${\displaystyle \mathbf {s} +\mathbf {t} \in {\mathcal {S}}}$${\displaystyle {\mathcal {A}}}$

ดังนั้น จึงไม่มีสิ่งใดเช่นนั้นเกิดขึ้นได้ ซึ่งหมายความว่าLWEและDLWEนั้น (โดยมีค่าตัวประกอบพหุนาม) ยากเท่ากันในกรณีเฉลี่ยกับกรณีที่เลวร้ายที่สุด ${\displaystyle {\mathcal {S}}}$

สำหรับ แลตทิซ nมิติให้พารามิเตอร์การปรับเรียบแทนค่าที่เล็กที่สุดที่ทำให้ โดยที่คือคู่ของและถูกขยายไปยังเซตโดยการรวมค่าฟังก์ชันที่แต่ละองค์ประกอบในเซต ให้แทนการแจกแจงแบบเกาส์เซียนแบบไม่ต่อเนื่องบนที่มีความกว้างสำหรับแลตทิซและ จำนวนจริงความน่าจะเป็นของแต่ละเป็นสัดส่วนกับ ${\displaystyle L}$${\displaystyle \eta _{\varepsilon }(L)}$${\displaystyle s}$${\displaystyle \rho _{1/s}(L^{*}\setminus \{\mathbf {0} \})\leq \varepsilon }$${\displaystyle L^{*}}$${\displaystyle L}$${\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}$${\displaystyle D_{L,r}}$${\displaystyle L}$${\displaystyle r}$${\displaystyle L}$${\displaystyle r>0}$${\displaystyle x\in L}$${\displaystyle \rho _{r}(x)}$

ปัญหาการสุ่มตัวอย่างแบบเกาส์เซียนแบบไม่ต่อเนื่อง ( DGS) ถูกกำหนดไว้ดังนี้: อินสแตนซ์ของถูกกำหนดโดยแลตทิซมิติและจำนวนเป้าหมายคือการส่งออกตัวอย่างจากRegev แสดงให้เห็นว่ามีการลดรูปจากไปเป็นสำหรับฟังก์ชันใดๆ ${\displaystyle DGS_{\phi }}$${\displaystyle n}$${\displaystyle L}$${\displaystyle r\geq \phi (L)}$${\displaystyle D_{L,r}}$${\displaystyle \operatorname {GapSVP} _{100{\sqrt {n}}\gamma (n)}}$${\displaystyle DGS_{{\sqrt {n}}\gamma (n)/\lambda (L^{*})}}$${\displaystyle \gamma (n)\geq 1}$

จากนั้น Regev แสดงให้เห็นว่ามีอัลกอริธึมควอนตัม ที่มีประสิทธิภาพ สำหรับการเข้าถึงออราเคิลที่กำหนดสำหรับจำนวนเต็มและเช่นนั้นซึ่งหมายถึงความยากของ LWE แม้ว่าการพิสูจน์ข้อความนี้จะใช้ได้กับทุก ๆแต่สำหรับการสร้างระบบเข้ารหัส โมดูลัสจะต้องเป็นพหุนามใน ${\displaystyle DGS_{{\sqrt {2n}}\eta _{\varepsilon }(L)/\alpha }}$${\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}$${\displaystyle q}$${\displaystyle \alpha \in (0,1)}$${\displaystyle \alpha q>2{\sqrt {n}}}$${\displaystyle q}$${\displaystyle q}$${\displaystyle n}$

Peikert พิสูจน์^{[ 4 ]}ว่ามีการลดเวลาพหุนามเชิงความน่าจะเป็นจากปัญหาในกรณีที่เลวร้ายที่สุดไปสู่การแก้ปัญหาโดย ใช้ตัวอย่างสำหรับพารามิเตอร์, , และ${\displaystyle \operatorname {GapSVP} _{\zeta ,\gamma }}$${\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}$${\displaystyle \operatorname {poly} (n)}$${\displaystyle \alpha \in (0,1)}$${\displaystyle \gamma (n)\geq n/(\alpha {\sqrt {\log n}})}$${\displaystyle \zeta (n)\geq \gamma (n)}$${\displaystyle q\geq (\zeta /{\sqrt {n}})\omega {\sqrt {\log n}})}$

ปัญหาLWEถือเป็นปัญหาอเนกประสงค์ที่ใช้ในการสร้างระบบการเข้ารหัสหลายระบบ^{[ 3 ] [ 4 ] [ 6 ] [ 7 ]}ในปี 2548 Regev ^{[ 3 ]}แสดงให้เห็นว่าเวอร์ชันการตัดสินใจของ LWE นั้นยาก โดยถือว่าปัญหาแลตทิซ มีความยากในระดับควอนตัม (สำหรับดังที่กล่าวมาข้างต้น) และด้วย) ในปี 2552 Peikert ^{[ 4 ]}ได้พิสูจน์ผลลัพธ์ที่คล้ายกันโดยถือว่าปัญหาที่เกี่ยวข้องมีความยากในระดับคลาสสิกเท่านั้นข้อเสียของผลลัพธ์ของ Peikert คือมันขึ้นอยู่กับเวอร์ชันที่ไม่เป็นมาตรฐานของปัญหา GapSVP ที่ง่ายกว่า (เมื่อเทียบกับ SIVP) ${\displaystyle \mathrm {GapSVP} _{\gamma }}$${\displaystyle \gamma }$${\displaystyle \mathrm {SIVP} _{t}}$${\displaystyle t=O(n/\alpha )}$${\displaystyle \mathrm {GapSVP} _{\zeta ,\gamma }}$

Regev ^{[ 3 ]}เสนอระบบการเข้ารหัสแบบกุญแจสาธารณะโดยอาศัยความยากของ ปัญหา LWEระบบการเข้ารหัส รวมถึงการพิสูจน์ความปลอดภัยและความถูกต้องนั้นเป็นแบบคลาสสิกโดยสมบูรณ์ ระบบนี้มีลักษณะเฉพาะด้วยและการกระจายความน่าจะเป็นบนการตั้งค่าพารามิเตอร์ที่ใช้ในการพิสูจน์ความถูกต้องและความปลอดภัยคือ ${\displaystyle m,q}$${\displaystyle \chi }$${\displaystyle \mathbb {T} }$

• ${\displaystyle q\geq 2}$โดยปกติจะเป็นจำนวนเฉพาะระหว่างและ${\displaystyle n^{2}}$${\displaystyle 2n^{2}}$
• ${\displaystyle m=(1+\varepsilon )(n+1)\log q}$สำหรับค่าคงที่ใดๆ${\displaystyle \varepsilon }$
• ${\displaystyle \chi =\Psi _{\alpha (n)}}$สำหรับโดยที่คือการแจกแจงความน่าจะเป็นที่ได้จากการสุ่มตัวอย่างตัวแปรปกติที่มีค่าเฉลี่ยและค่าเบี่ยงเบนมาตรฐานและลดผลลัพธ์ลงด้วยโมดูลัส${\displaystyle \alpha (n)\in o(1/{\sqrt {n}}\log n)}$${\displaystyle \Psi _{\beta }}$${\displaystyle 0}$${\displaystyle {\frac {\beta }{\sqrt {2\pi }}}}$${\displaystyle 1}$

ระบบการเข้ารหัสจะถูกกำหนดโดย:

• กุญแจส่วนตัว : กุญแจส่วนตัวถูกเลือกแบบสุ่มอย่างสม่ำเสมอ${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$
• กุญแจสาธารณะ : เลือกเวกเตอร์อย่างสม่ำเสมอและเป็นอิสระ เลือกค่าชดเชยข้อผิดพลาดอย่างอิสระตามเงื่อนไขกุญแจสาธารณะประกอบด้วย${\displaystyle m}$${\displaystyle \mathbf {a} _{1},\ldots ,\mathbf {a} _{m}\in \mathbb {Z} _{q}^{n}}$${\displaystyle e_{1},\ldots ,e_{m}\in \mathbb {T} }$${\displaystyle \chi }$${\displaystyle (\mathbf {a} _{i},b_{i}=\langle \mathbf {a} _{i},\mathbf {s} \rangle /q+e_{i})_{i=1}^{m}}$
• การเข้ารหัส : การเข้ารหัสบิตทำได้โดยการเลือกเซตย่อยแบบสุ่มของ เซตหนึ่ง แล้วกำหนดให้เป็นเซตย่อยถัดไป${\displaystyle x\in \{0,1\}}$${\displaystyle S}$${\displaystyle [m]}$${\displaystyle \operatorname {Enc} (x)}$

${\displaystyle \left(\sum _{i\in S}\mathbf {a} _{i},{\frac {x}{2}}+\sum _{i\in S}b_{i}\right)}$

• การถอดรหัส : การถอดรหัสจะเป็นแบบถ้าอยู่ใกล้กว่าและจะเป็นแบบ ในกรณีอื่น ๆ${\displaystyle (\mathbf {a} ,b)}$${\displaystyle 0}$${\displaystyle b-\langle \mathbf {a} ,\mathbf {s} \rangle /q}$${\displaystyle 0}$${\displaystyle {\frac {1}{2}}}$${\displaystyle 1}$

การพิสูจน์ความถูกต้องมาจากการเลือกพารามิเตอร์และการวิเคราะห์ความน่าจะเป็นบางส่วน การพิสูจน์ความปลอดภัยมาจากการลดรูปเป็นเวอร์ชันการตัดสินใจของLWE : อัลกอริทึมสำหรับการแยกแยะความแตกต่างระหว่างการเข้ารหัส (ด้วยพารามิเตอร์ข้างต้น) ของและสามารถใช้เพื่อแยกแยะความแตกต่างระหว่างและการกระจายแบบสม่ำเสมอเหนือ${\displaystyle 0}$${\displaystyle 1}$${\displaystyle A_{s,\chi }}$${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$

Peikert ^{[ 4 ]}เสนอระบบที่มีความปลอดภัยแม้กระทั่งต่อการโจมตีด้วยข้อความเข้ารหัสที่เลือกไว้

แนวคิดการใช้ LWE และ Ring LWE สำหรับการแลกเปลี่ยนคีย์ได้รับการเสนอและยื่นจดสิทธิบัตรที่มหาวิทยาลัยซินซินเนติในปี 2011 โดย Jintai Ding แนวคิดนี้มาจากคุณสมบัติการสลับที่ของการคูณเมทริกซ์ และข้อผิดพลาดถูกนำมาใช้เพื่อให้เกิดความปลอดภัย เอกสาร^{[ 8 ]}ปรากฏในปี 2012 หลังจากมีการยื่นคำขอจดสิทธิบัตรชั่วคราวในปี 2012

ความปลอดภัยของโปรโตคอลได้รับการพิสูจน์แล้วโดยอาศัยความยากในการแก้ปัญหา LWE ในปี 2014 Peikert ได้นำเสนอแผนการส่งคีย์^{[ 9 ]}โดยใช้แนวคิดพื้นฐานเดียวกันกับของ Ding ซึ่งใช้แนวคิดใหม่ในการส่งสัญญาณ 1 บิตเพิ่มเติมสำหรับการปัดเศษในโครงสร้างของ Ding ด้วย การใช้งาน "ความหวังใหม่" ^{[ 10 ]}ที่เลือกสำหรับการทดลองหลังควอนตัมของ Google ^{[ 11 ]}ใช้แผนการของ Peikert โดยมีการเปลี่ยนแปลงในการกระจายข้อผิดพลาด

โปรโตคอลการระบุตัวตน Feige–Fiat–Shamir เวอร์ชัน RLWE (Ring Learning with Errors) แบบดั้งเดิมถูกสร้างขึ้นและแปลงเป็นลายเซ็นดิจิทัลในปี 2011 โดย Lyubashevsky รายละเอียดของลายเซ็นนี้ได้รับการขยายเพิ่มเติมในปี 2012 โดย Gunesyu, Lyubashevsky และ Popplemann และตีพิมพ์ในบทความเรื่อง "Practical Lattice Based Cryptography – A Signature Scheme for Embedded Systems" บทความเหล่านี้วางรากฐานสำหรับอัลกอริธึมลายเซ็นต่างๆ ในปัจจุบัน ซึ่งบางส่วนอิงโดยตรงจากปัญหาการเรียนรู้แบบมีข้อผิดพลาด (RLWE) และบางส่วนไม่ได้ผูกติดกับปัญหา RLWE ที่ยากเหล่านั้น

• การเข้ารหัสลับหลังควอนตัม
• การเรียนรู้แบบวงแหวนพร้อมข้อผิดพลาด
• การเข้ารหัสแบบอิงโครงสร้างแลตทิซ
• การเรียนรู้แหวนพร้อมข้อผิดพลาด การแลกเปลี่ยนกุญแจ
• ปัญหาการหาคำตอบจำนวนเต็มสั้น (SIS)
• ไคเบอร์