รากฐาน Learning With Errors (LWE)

การเรียนรู้ที่มีข้อผิดพลาด (LWE) โดย Regev (2005): เมื่อกำหนดสมการเชิงเส้นที่มีสัญญาณรบกวนจำนวนมากบน Z_q ให้ค้นหาเวกเตอร์ลับ s สัญญาณรบกวน e มีขนาดเล็กแต่ทำให้การกำจัดแบบเกาส์ใช้ไม่ได้ หากไม่มีสัญญาณรบกวน ระบบจะแก้ได้ง่าย แต่เมื่อมีสัญญาณรบกวนแม้เพียงเล็กน้อย ระบบจะยากต่อการคำนวณ

คีย์ลับ s ∈ Z_q^n ผู้โจมตีได้รับตัวอย่าง (a_i, b_i) โดยที่ a_i ∈ Z_q^n เป็นค่าสุ่ม และ b_i = + e_i mod q โดย e_i เป็นสัญญาณรบกวนขนาดเล็กจากการแจกแจง χ (เช่น การแจกแจงแบบเกาส์เซียนที่มี σ = √n) ภารกิจคือค้นหา s จากตัวอย่างจำนวนมากเชิงพหุนาม

หากไม่มีสัญญาณรบกวน: b_i = mod q การกำจัดแบบเกาส์จะกู้คืน s ได้ในเวลา O(n^3) เมื่อมีสัญญาณรบกวน: สมการที่ผิดเพียงสมการเดียวก็ทำให้การกำจัดเสียหาย สัญญาณรบกวนมีขนาดเล็กพอให้ถอดรหัสได้เมื่อใช้กุญแจ แต่มีขนาดใหญ่พอที่จะป้องกันการวิเคราะห์รหัสลับ

Regev พิสูจน์ว่า LWE ลดรูปเป็นปัญหาแลตทิซในกรณีเลวร้ายที่สุด (SIVP, GapSVP) ด้วยการลดรูปเชิงควอนตัม ซึ่งหมายความว่า หากทำลาย LWE ได้ ก็จะสามารถแก้ปัญหาแลตทิซยากได้หลายชนิด — แต่ยังไม่มีอัลกอริทึมควอนตัมที่ทราบว่าสามารถเร่งความเร็วสำหรับปัญหาแลตทิซได้ LWE จึงมีความปลอดภัยหลังยุคควอนตัม

RLWE แทนที่ Z_q^n ด้วยวงแหวน Z_q[x]/(f(x)) สำหรับพหุนามไซโคลโตมิก f ตัวอย่าง RLWE หนึ่งตัวอย่างเข้ารหัสสมการจำนวน n สมการ จึงมีประสิทธิภาพมากกว่ามาก RLWE เป็นพื้นฐานของ Kyber (KEM), Dilithium (ลายเซ็น) และรูปแบบ HE อย่าง BFV/BGV/CKKS

ความปลอดภัยขึ้นอยู่กับ: n (มิติ โดยทั่วไปคือ 512-2048), q (มอดูลัส 1024-2^60), σ (ส่วนเบี่ยงเบนมาตรฐานของสัญญาณรบกวน) ค่า n ที่มากขึ้นและอัตราส่วน σ/q ที่เล็กลงทำให้ปัญหายากขึ้น มาตรฐานหลังยุคควอนตัมของ NIST ใช้ n=256 (มิติของโมดูล) พร้อมโมดูล k ชุด (k=2,3,4)

กุญแจสาธารณะ: (A, b=As+e) เข้ารหัสบิต m: เลือก r แบบสุ่ม แล้วคำนวณข้อความเข้ารหัส (u=A^T r, v = b^T r + m*q/2) ถอดรหัส: v - s^T u = e^T r + m*q/2 ≈ m*q/2 ปัดเป็น m ที่ใกล้ที่สุด สัญญาณรบกวน e ช่วยซ่อน m ในข้อความเข้ารหัสระหว่างการเข้ารหัส

LWE แบบตัดสินใจ: แยกแยะ (a, As+e) จาก (a, u) โดยที่ u เป็นค่าสุ่มแบบสม่ำเสมอ ไม่สามารถแยกแยะได้ในเชิงคำนวณ หากสมมติว่า LWE เป็นปัญหายาก นี่คือพื้นฐานของความปลอดภัยเชิงความหมาย — ข้อความเข้ารหัสจะดูเหมือนสัญญาณรบกวนแบบสุ่มสำหรับผู้โจมตีที่ไม่มีกุญแจลับ

การโจมตีที่ดีที่สุดเท่าที่ทราบ: การลดรูปแลตทิซ BKZ (Block Korkine-Zolotarev) ความซับซ้อน: แบบกึ่งเอ็กซ์โพเนนเชียลแต่ไม่ใช่พหุนาม BKZ-β ต้องใช้การดำเนินการ 2^{0.292β} ครั้ง สำหรับ LWE-512: ความปลอดภัยประมาณ 128 บิตเมื่อโจมตีด้วย BKZ ยังไม่มีการเร่งความเร็วด้วยควอนตัมที่ทราบสำหรับ BKZ

LWE แบบโมดูล (ใช้ใน Kyber) คือ RLWE บนโมดูลที่มีอันดับ k ให้ความยืดหยุ่น: k=2 สำหรับความปลอดภัย 512 บิต, k=3 สำหรับ 768 บิต และ k=4 สำหรับ 1024 บิต ความปลอดภัยและประสิทธิภาพเพิ่มขึ้นตาม k NIST เลือก Kyber (เปลี่ยนชื่อเป็น ML-KEM) เป็นมาตรฐาน PQC

ความปลอดภัยของ RSA/ECC มีพื้นฐานจากการแยกตัวประกอบจำนวนเต็มและลอการิทึมไม่ต่อเนื่อง (เสี่ยงต่อควอนตัมผ่าน Shor) ความปลอดภัยของ LWE มีพื้นฐานจากปัญหาแลตทิซในกรณีเลวร้ายที่สุด (ยังไม่มีการเร่งความเร็วด้วยควอนตัมที่ทราบ) ขนาดกุญแจ: กุญแจ LWE ประมาณ 1 KB เทียบกับ RSA-2048 ขนาด 256 ไบต์ LWE มีขนาดใหญ่กว่าแต่ปลอดภัยต่อควอนตัม

เหตุใด LWE จึงยังแก้ได้ยากแม้จะมีตัวอย่างจำนวนมาก

LWE: ค้นหา s ลับจากสมการเชิงเส้นที่มีสัญญาณรบกวน ซึ่งยากต่อควอนตัม RLWE ใช้วงแหวนพหุนามเพื่อเพิ่มประสิทธิภาพ เป็นพื้นฐานของ Kyber, Dilithium และรูปแบบ HE ถัดไป: รูปแบบ HE อย่าง BGV และ BFV สำหรับการดำเนินการกับจำนวนเต็ม