จะพิสูจน์การลดลงจากการตัดสินใจเลือก LWE ได้อย่างไร

ฉันยังใหม่กับการเข้ารหัสและพยายามเข้าใจแนวคิดของ LWE (การเรียนรู้จากข้อผิดพลาด) อย่างเป็นทางการ ฉันจะระบุความเข้าใจของฉันเกี่ยวกับคำจำกัดความซึ่งอาจไม่ถูกต้อง

คำจำกัดความตามความเข้าใจของฉัน

อนุญาต $R$ เป็นวงแหวนการสับเปลี่ยนหน่วยที่มีจำกัดซึ่งมีความน่าจะเป็น $\mu$ (ของใคร $\sigma$-พีชคณิตไม่ต่อเนื่อง) $R$ กล่าวเพื่อตอบสนองความ สมมติฐาน LWE ของการค้นหาในกรณีที่เลวร้ายที่สุด ถ้าสำหรับพหุนามทั้งหมด $n$ และอัลกอริธึมสุ่มพหุนาม-เวลาทั้งหมด $S$, แผนที่ \begin{สมการ} m\mapsto \min_{s\in R^m} p(m,s)\text{,} \end{สมการ} ที่ไหน \begin{สมการ} p(m,s) = \Pr\{(A,e)\in R^{m\times n(m)} \times R^{n(m)}: S (-sA+e,A)= s\}\ข้อความ{,} \end{สมการ} เป็นเรื่องเล็กน้อย ในสมการข้างต้น $A$ สุ่มตัวอย่างจากความน่าจะเป็นแบบเดียวกัน และ $e$ สุ่มตัวอย่างจากความน่าจะเป็นของผลิตภัณฑ์ $\mu^{n(ม)}$.

$R$ กล่าวเพื่อตอบสนองความ การตัดสินใจในกรณีที่เลวร้ายที่สุด สมมติฐาน LWE ถ้าสำหรับพหุนามทั้งหมด $n$ และอัลกอริธึมสุ่มพหุนาม-เวลาทั้งหมด $D$, แผนที่ \begin{สมการ} m\mapsto \min_{s\in R^m} |p_1(m,s)-p_2(m)|\text{,} \end{สมการ} ที่ไหน \begin{สมการ} \begin{แยก} p_1(m,s) &= \Pr\{(A,e)\in R^{m\times n(m)}\times R^{n(m)}: D (-sA+e,A) =1\},\ p_2(m) &= \Pr\{(b,A)\in R^{n(m)}\times R^{m\times n(m)}\times: D (b,A)=1\ }\ข้อความ{,} \end{แยก} \end{สมการ} เป็นเรื่องเล็กน้อย ในสมการข้างต้น $A$ และ $ข$ มีการสุ่มตัวอย่างจากความน่าจะเป็นแบบเดียวกัน และ $e$ สุ่มตัวอย่างจากความน่าจะเป็นของผลิตภัณฑ์ $\mu^{n(ม)}$.

คำถาม

ฉันพิสูจน์แล้วว่าหาก $R$ เป็นเขตข้อมูลจำกัดที่มีความน่าจะเป็น $\mu$ (ของใคร $\sigma$-พีชคณิตไม่ต่อเนื่อง) และถ้า $R$ เป็นไปตามสมมติฐานการค้นหา LWE กรณีที่เลวร้ายที่สุด $R$ ยังเป็นไปตามข้อสันนิษฐาน LWE ของการตัดสินใจในกรณีที่เลวร้ายที่สุด แต่จะพิสูจน์การสนทนาได้อย่างไร? วรรณกรรมทั้งหมดที่ฉันเคยเห็นบอกเพียงว่ามันเป็นเรื่องเล็กน้อย แต่ฉันไม่สามารถพิสูจน์ได้ ให้ชัดเจนยิ่งขึ้น ฉันต้องการหลักฐานของข้อความต่อไปนี้:

ถ้า $R$ เป็นวงแหวนการสับเปลี่ยนหน่วยจำกัดที่มีความน่าจะเป็น $\mu$ (ของใคร $\sigma$-พีชคณิตไม่ต่อเนื่อง) และถ้า $R$ เป็นไปตามข้อสันนิษฐาน LWE ของการตัดสินใจในกรณีที่เลวร้ายที่สุด $R$ ยังเป็นไปตามสมมติฐานการค้นหา LWE กรณีที่แย่ที่สุด

ความพยายามของฉัน

สมมติว่า $R$ เป็นไปตามข้อสันนิษฐาน LWE ของการตัดสินใจในกรณีที่เลวร้ายที่สุด อนุญาต $n$ เป็นพหุนามและปล่อยให้ $S$ เป็นอัลกอริทึมแบบสุ่มเวลาพหุนาม (ซึ่งอินพุตเป็นองค์ประกอบใน $R^{n(m)}\times R^{m\times n(m)}$ และผลลัพธ์ของใครเป็นองค์ประกอบใน $R^m$). เราต้องแสดงแผนที่นั้น \begin{สมการ} m\mapsto \min_{s\in R^m} p(m,s)\text{,} \end{สมการ} ที่ไหน $p(m,s)$ กำหนดไว้ข้างต้นเล็กน้อย ได้รับอินพุต $(b,A)\in R^{n(m)}\times R^{m\times n(m)}$ ที่ไหน $b=-sA+e$, $S$ จะกลับมาคาดเดา $g\in R^m$ ที่อาจหรือไม่เท่ากับก็ได้ $s$. สามารถคำนวณได้ $b+gA$ และแสดงโดย $e'$. ถ้า $g=s$, แล้ว $e'=e$. ถ้า $ก\neq ส$, แล้ว $e'=e$ อาจจะถือหรือไม่ถือก็ได้ฉันไม่รู้ว่าจะทำอย่างไรตอนนี้