ใช่ ด้วยเหตุผลทั่วไป
กล่าวคือ $a$ กลับด้านได้คือ:
- ตรวจสอบได้โดยสาธารณะและ
- เกิดขึ้นด้วยความน่าจะเป็นที่ไม่สำคัญ $p$ (มากกว่าการเลือกเครื่องแบบของ $a$), ดู นี้เพื่อดูรายละเอียด.
เมื่อไรก็ตามที่คุณมีเงื่อนไขเช่นนี้ คุณสามารถให้ฝ่ายตรงข้ามที่เป็นสมมุติฐานตรวจสอบก่อนว่าเงื่อนไขนั้นเป็นจริงหรือไม่ และหากไม่เป็นเช่นนั้น ให้ "เดา" คำตอบแบบสุ่ม
สิ่งนี้จะลดความได้เปรียบด้วยปัจจัยที่ทวีคูณ $p$แต่เนื่องจากสิ่งนี้ไม่มีนัยสำคัญ จึงไม่สำคัญ (สำหรับแนวคิดด้านความปลอดภัยอย่างน้อยที่สุด)
นี่คือคำอธิบายที่ชัดเจนซึ่งให้ไว้ในกระดาษของ Steinfield และ Stehle ที่คุณเชื่อมโยงไว้ แต่ก็ไม่มีส่วนเกี่ยวข้องกับ "ปัญหาพื้นฐาน" ที่พวกเขากำลังทำงานด้วยการเป็น RLWE ด้วยความลับแบบเดียวกัน และถือเป็นเรื่องทั่วไปที่ฉันกล่าวถึงข้างต้น
เป็นอิสระจากข้างต้นนี่คือ อีกด้วย แรงจูงใจสำหรับการลดกรณีเลวร้ายที่สุดถึงกรณีเฉลี่ยในการเข้ารหัสขัดแตะ
บ่อยครั้งที่มีผู้สมัครที่ "ชัดเจน" สำหรับปัญหาหนักๆ (เช่น แฟคตอริ่ง หรือ BDD/CVP สำหรับแลตทิซ) แต่การตรึงการแจกแจงกรณีเฉลี่ยที่แม่นยำเพื่อใช้อาจไม่ชัดเจน
การลดกรณีที่เลวร้ายที่สุดถึงกรณีเฉลี่ยแสดงว่าการกระจายกรณีเฉลี่ยจำนวนหนึ่งสำหรับปัญหา LWE ไม่ได้ "ไม่ดีทางโครงสร้าง" ตัวอย่างเช่น:
- ชุดยูนิฟอร์ม $a$,ยูนิฟอร์ม $s$เสียน $e$ (ของส่วนเบี่ยงเบนมาตรฐาน $\geq \Omega(\sqrt{n})$มีขนาดใหญ่กว่าที่คนส่วนใหญ่ใช้ในทางปฏิบัติ)
- ชุดยูนิฟอร์ม $a$, $s$ ที่เป็นไปตามการกระจายของ $e$
เมื่อเราทราบเครื่องแบบนั้นแล้ว $a$ เป็นการกระจาย "ที่ถูกต้อง" ในการทำงาน เราสามารถกำหนดเงื่อนไข "ขนาดใหญ่" (ความหมายที่เกิดขึ้นด้วยความน่าจะเป็นที่ไม่สำคัญ) ได้อย่างอิสระตามที่เราต้องการ $a$รวมถึงว่ามันกลับด้านได้ (หรือมีพิกัดแรก $1$หรือมี $\sum_i a_i \equiv 0 \bmod q$ สำหรับพหุนามขนาดใหญ่ $คิว$หรือโดยพื้นฐานแล้ว อะไรก็ตาม). โปรดทราบว่านี่เป็นเรื่องจริงเท่านั้น โดยไม่แสดงอาการ แม้ว่า --- การลดกรณีที่เลวร้ายที่สุดถึงกรณีเฉลี่ยจะไม่มีประโยชน์อย่างยิ่งในการทำให้ LWE เป็นพาราเมตริกอย่างเป็นรูปธรรม เนื่องจากเราสามารถปรับพารามิเตอร์ให้เล็กลงได้โดยการเข้ารหัส LWE โดยตรง