พิจารณาสูตรของ LWE ที่เราได้รับเช่นกัน $(x,S x+e)$ หรือ $(x,u)$ --- ที่ไหน $S$ เป็น $m \คูณ n$ เมทริกซ์ลับ / ซ่อนเร้น $x$ เป็นการสุ่มตัวอย่าง $n \คูณ 1$ เวกเตอร์, $e$ เป็น $m \คูณ 1$ เวกเตอร์ข้อผิดพลาด Gaussian และ $u$ เป็นตัวอย่างสุ่มแบบสม่ำเสมอ --- และบอกให้แยกแยะระหว่างสองกรณีนี้ สิ่งนี้น่าจะยากสำหรับอัลกอริธึมแบบคลาสสิก ตามโพสต์ ที่นี่. เรียกปัญหานี้ว่า "reverse-LWE"
ฉันมีคำถามสองสามข้อเกี่ยวกับการตั้งค่า
เป็นปัญหาที่แตกต่างยากโดยไม่ต้อง $e$?
โปรดทราบว่าในมาตรฐาน LWE เมื่อเราได้รับ $(ก,ก+จ)$ หรือ $(x,u)$และบอกให้แยกความแตกต่างระหว่างทั้งสองกรณี ปัญหาจะง่าย โดยไม่มีข้อผิดพลาด เราแค่แก้ระบบสมการเชิงเส้นเพื่อให้ได้ $n$ รายการของ $s$.
อย่างไรก็ตามที่นี่เราต้องค้นหา $m \คูณ n$ รายการเมทริกซ์ลับของเรา $S$. ฉันไม่เห็นวิธีการทำเช่นนั้นด้วย $m$ สมการ
พิจารณาความแตกต่างของปัญหาที่เราได้รับ $$ \{ (x_1, Sx_1 + e_1), (x_2, Sx_2 + e_2), \ldots, (x_k, Sx_k + e_k)\} ~~\text{or}$$
$$\{ (x_1, u_1), (x_2, u_2), \ldots, (x_k, u_k)\},$$
และบอกให้แยกแยะระหว่างทั้งสองกรณี เรียกปัญหานี้ว่า "ย้อนกลับ LWE ด้วยความลับซ้ำๆ" $k$ มีขนาดใหญ่เป็นพหุนามใน $n$. ปัญหานี้ยากไหม?
โปรดทราบว่าอาร์กิวเมนต์แบบผสม (เช่นเดียวกับที่ใช้ในคำตอบข้อใดข้อหนึ่ง ที่นี่) แสดงว่าปัญหายังคงยากอยู่ นี่คือไฮบริด $H_i$:
$$H_i = \{ (x_1, Sx_1 + e_1), (x_2, Sx_2 + e_2), \ldots, (x_i, Sx_i + e_i), (x_{i+1}, u_{i+1}) \ldots , (x_{k}, u_{k}) \} .$$
จึงมีทางตรงที่จะสรุปได้ว่า ถ้าเราแก้ "reverse LWE ด้วยความลับซ้ำๆ" เราจะสามารถแก้ reverse LWE ได้ เนื่องจากการย้อนกลับ LWE นั้นยาก ปัญหาของเราก็ควรจะยากเช่นกัน
อย่างไรก็ตาม ฉันมีปัญหาในการคาดคะเนข้อเท็จจริงนี้
โปรดทราบว่าหากเราไม่มีคำที่ใช้แสดงข้อผิดพลาด มีวิธีง่ายๆ ในการแยกแยะระหว่างสองกรณี เช่น $k \geq n+1$. โปรดทราบว่าสามารถมีได้เท่านั้น $n$ อิสระเชิงเส้น $x_i$-s. ดังนั้นความแตกต่างเพียงแค่มองหา $n$ แตกต่าง $x_i$-s ในตัวอย่างที่กำหนด ให้บันทึกตำแหน่งเมทริกซ์ $S$ นำเวกเตอร์เหล่านี้ไปหา และสำหรับ $n+1^{\text{th}}$ ตัวอย่างที่แตกต่างกัน ใช้ความเป็นเชิงเส้นเพื่อคำนวณตำแหน่งก่อน $S$ เอาไปตรวจสอบดูว่าตรงกับที่ให้ไปหรือเปล่า
เหตุใดเงื่อนไขข้อผิดพลาดจึงทำให้ตัวแยกความแตกต่างนี้ล้มเหลว แม้จะมีข้อผิดพลาด Gaussian เนื่องจากการพึ่งพาเชิงเส้นก็ไม่ควร $n+1^{\text{th}}$ ตัวอย่างที่แตกต่างกันมีความเข้มข้นเพียงพอกับค่าบางอย่างเพื่อให้ตัวแยกความแตกต่างของฉันประสบความสำเร็จหรือไม่