Learning With Errors: ปัญหาที่ยากต่อการแก้

ปัญหาการเรียนรู้ที่มีความผิดพลาด (LWE) ถูกนำเสนอโดย Oded Regev ในปี 2005 เพื่อเป็นรากฐานของการเข้ารหัสลับหลังยุคควอนตัม เมื่อกำหนดเมทริกซ์สุ่ม A เหนือ Z_q และเวกเตอร์ b = As + e เป้าหมายคือการค้นหาเวกเตอร์ลับ s เวกเตอร์ e คือความผิดพลาดขนาดเล็กที่สุ่มจากการแจกแจงแบบเกาส์เซียนไม่ต่อเนื่อง ทำให้ปัญหานี้แก้ได้ยากในทางคำนวณ

ในปัญหา LWE, A คือเมทริกซ์สุ่มขนาด m x n ที่สุ่มอย่างสม่ำเสมอเหนือ Z_q โดย q เป็นมอดูลัสจำนวนเฉพาะ s เป็นเวกเตอร์มิติ n และ e เป็นเวกเตอร์ความผิดพลาดขนาดเล็ก ซึ่งสมาชิกแต่ละตัวสุ่มมาจากการแจกแจงแบบเกาส์เซียนที่มีช่วงแคบ แม้ผู้โจมตีจะทราบโครงสร้างของ A ก็ยังไม่สามารถใช้ข้อมูลนั้นแยกแยะ b ออกจากเวกเตอร์สุ่มแบบสม่ำเสมอได้

LWE มีการกำหนดรูปแบบมาตรฐานอยู่สองแบบ LWE แบบค้นหาคือการกู้คืนค่าลับ s เมื่อได้รับตัวอย่างจำนวนมาก (A, b) ส่วน LWE แบบตัดสินใจคือการแยกแยะตัวอย่าง (A, As + e) ออกจากคู่สุ่มแบบสม่ำเสมอ (A, u) รูปแบบทั้งสองมีความเทียบเท่ากันในเวลาเชิงพหุนาม กล่าวคือ อัลกอริทึมที่แก้รูปแบบหนึ่งได้สามารถแปลงให้แก้อีกรูปแบบหนึ่งได้

พจน์ความผิดพลาดใน LWE สุ่มมาจากการแจกแจงแบบเกาส์เซียนไม่ต่อเนื่องบนจำนวนเต็ม โดยกำหนดพารามิเตอร์ด้วยส่วนเบี่ยงเบนมาตรฐาน sigma ค่า sigma ที่มีขนาดเล็กทำให้ e มีขนาดสั้นเมื่อเทียบกับ q และทำให้ b ดูเกือบเหมือน As mod q หาก sigma เป็นศูนย์ก็จะไม่มีความผิดพลาด และระบบจะแก้ได้ด้วยการกำจัดแบบเกาส์เซียน ดังนั้นความผิดพลาดจึงเป็นองค์ประกอบสำคัญที่ทำให้ปัญหานี้ยาก

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

ต่างจาก RSA และการเข้ารหัสด้วยเส้นโค้งวงรี ยังไม่มีอัลกอริทึมควอนตัมที่รู้จักซึ่งให้การเร่งความเร็วแบบเลขชี้กำลังต่อ LWE อัลกอริทึมของ Grover ให้การเร่งความเร็วได้มากที่สุดในระดับกำลังสอง และอัลกอริทึมควอนตัมด้านแลตทิซที่ดีที่สุด (รูปแบบต่าง ๆ ของ BKZ) ก็ไม่สามารถทำลาย LWE ได้เมื่อเลือกพารามิเตอร์อย่างเหมาะสม จึงทำให้ LWE เป็นรากฐานที่แข็งแกร่งสำหรับความมั่นคงปลอดภัยหลังยุคควอนตัม

ความมั่นคงปลอดภัยของ LWE ขึ้นอยู่กับพารามิเตอร์สามตัว ได้แก่ มิติ n (ความยาวของค่าลับ) มอดูลัส q และส่วนเบี่ยงเบนมาตรฐานของความผิดพลาด sigma ค่า n ที่ใหญ่ขึ้นและอัตราส่วน q/sigma ที่เล็กลงจะเพิ่มความมั่นคงปลอดภัย สำหรับความมั่นคงปลอดภัยหลังยุคควอนตัมระดับ 128 บิต ค่าที่ใช้โดยทั่วไปคือ n = 1024, q ประมาณ 12289 และ sigma ประมาณ 3.2 เครื่องมือประเมินแลตทิซของ Albrecht และคณะใช้สำหรับประเมินความมั่นคงปลอดภัยในเชิงรูปธรรม

ปัญหาคำตอบจำนวนเต็มสั้น (SIS) เป็นสมมติฐานความยากบนแลตทิซที่เกี่ยวข้องกัน ซึ่งใช้สำหรับลายเซ็น เมื่อกำหนดเมทริกซ์สุ่ม A เหนือ Z_q ให้ค้นหาเวกเตอร์ x ที่ไม่เป็นศูนย์และมีขนาดสั้น ซึ่งเป็นไปตาม Ax = 0 mod q SIS เป็นพื้นฐานของฟังก์ชันแฮชและโครงร่างลายเซ็นในโลกของแลตทิซ และทำงานเสริมกับ LWE ซึ่งเป็นพื้นฐานของการเข้ารหัสและการห่อหุ้มกุญแจ

โครงร่างการเข้ารหัส LWE แบบง่ายทำงานดังนี้ กุญแจสาธารณะคือ (A, b = As + e) และกุญแจลับคือ s ในการเข้ารหัสบิต m ผู้ส่งจะคำนวณ (u, v) = (A^T r, b^T r + m * floor(q/2)) โดยใช้เวกเตอร์ไบนารีสุ่ม r การถอดรหัสจะคำนวณ v - s^T u แล้วปัดค่าเพื่อกู้คืน m โครงร่างนี้มีความมั่นคงปลอดภัยแบบ IND-CPA ภายใต้สมมติฐาน LWE

LWE ทำให้เกิดโครงสร้างการเข้ารหัสลับหลากหลายรูปแบบ นอกเหนือจากการเข้ารหัสพื้นฐาน ซึ่งรวมถึงการเข้ารหัสแบบโฮโมมอร์ฟิกอย่างสมบูรณ์ (FHE) การเข้ารหัสตามเอกลักษณ์ (IBE) การเข้ารหัสตามแอตทริบิวต์ (ABE) และโปรโตคอลแลกเปลี่ยนกุญแจ CRYSTALS-Kyber (ปัจจุบันคือ ML-KEM และกำหนดมาตรฐานเป็น FIPS 203) เป็นโครงร่างที่อาศัย LWE ซึ่งถูกนำไปใช้งานจริงมากที่สุด

การเข้ารหัสลับที่อาศัย LWE กำลังเข้าสู่ระบบที่ใช้งานจริงอยู่แล้ว Google และ Cloudflare ได้ทดลองใช้ TLS โดยใช้ Kyber ในช่วงปี 2018-2020 Chrome และ Firefox เพิ่มการรองรับ ML-KEM-768 ในการจับคู่ TLS แบบผสมในปี 2024 โปรโตคอล Signal เพิ่มชั้นการป้องกันหลังยุคควอนตัม (PQXDH) โดยใช้ ML-KEM-1024 เพื่อรักษาความลับไปข้างหน้า และปกป้องความลับของข้อความระยะยาวจากคอมพิวเตอร์ควอนตัมในอนาคต

ข้อความใดอธิบายหลักประกันด้านความยากของปัญหา LWE ได้ดีที่สุด

LWE เป็นหนึ่งในสมมติฐานความยากหลังยุคควอนตัมที่ได้รับการศึกษามากที่สุด โดยมีการลดรูปจากปัญหาแลตทิซในกรณีเลวร้ายที่สุดที่แข็งแกร่ง พารามิเตอร์สามตัวของ LWE (n, q, sigma) ควบคุมสมดุลระหว่างความมั่นคงปลอดภัยกับประสิทธิภาพ LWE ทนทานต่อการโจมตีด้วยควอนตัมและเป็นพื้นฐานของโครงร่างที่ NIST กำหนดมาตรฐานไว้ การทำความเข้าใจ LWE เป็นประตูสู่การเข้ารหัสลับบนแลตทิซสมัยใหม่ทั้งหมด รวมถึง ML-KEM และ ML-DSA