การพิสูจน์ความปลอดภัยและการลดรูปในโครงสร้างแลตทิซ

บทพิสูจน์ความปลอดภัยของโครงร่างการเข้ารหัสลับคือข้อโต้แย้งทางคณิตศาสตร์อย่างเป็นทางการที่แสดงว่า การทำลายโครงร่างดังกล่าวย่อมหมายถึงการแก้ปัญหายากที่อยู่เบื้องหลังได้ บทพิสูจน์ไม่ได้รับประกันความปลอดภัยอย่างสมบูรณ์ แต่แสดงให้เห็นว่าผู้โจมตีที่มีประสิทธิภาพซึ่งโจมตีโครงร่างได้ สามารถถูกแปลงให้เป็นตัวแก้ปัญหายากที่มีประสิทธิภาพได้ หากปัญหายากนั้นไม่สามารถคำนวณได้ในทางปฏิบัติ โครงร่างก็จะปลอดภัย

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

การลดรูปของ Regev ไม่แน่นสนิท: ตัวประกอบพหุนามในการลดรูปทำให้ระดับความปลอดภัยที่บทพิสูจน์รับรองอ่อนกว่าการโจมตีที่ดีที่สุดซึ่งเป็นที่รู้จักอยู่บ้าง ในการเลือกพารามิเตอร์สำหรับใช้งานจริง นักวิทยาการเข้ารหัสลับจะใช้ความปลอดภัยเชิงรูปธรรมที่ได้จากการโจมตีที่ดีที่สุดซึ่งเป็นที่รู้จักผ่านตัวประเมินแลตทิซ แทนขอบเขตจากการลดรูปเชิงทฤษฎี เนื่องจากการลดรูปนั้นอนุรักษนิยม

โครงร่างการเข้ารหัสลับที่อาศัย LWE ได้รับการพิสูจน์ว่ามีความปลอดภัยแบบ IND-CPA (แยกแยะไม่ได้ภายใต้การโจมตีด้วยข้อความต้นฉบับที่เลือก) ผ่านข้อโต้แย้งแบบไฮบริด บทพิสูจน์แสดงว่า ตัวแยกแยะ IND-CPA ย่อมทำให้เกิดตัวแยกแยะ LWE ในไฮบริดขั้นแรก ข้อความเข้ารหัสจริงจะถูกแทนที่ด้วยสตริงสุ่มที่กระจายสม่ำเสมอ และความแยกแยะไม่ได้เป็นผลจากสมมติฐาน LWE วิธีนี้ให้บทพิสูจน์ความปลอดภัยที่ชัดเจนสำหรับการเข้ารหัสแบบแลตทิซพื้นฐาน

ความปลอดภัยแบบ IND-CPA ไม่เพียงพอสำหรับกลไกการห่อหุ้มกุญแจที่ใช้ใน TLS แต่ต้องมีความปลอดภัยแบบ IND-CCA2 (การโจมตีด้วยข้อความเข้ารหัสที่เลือก) การแปลง Fujisaki-Okamoto (FO) แปลงโครงร่างแบบ IND-CPA ใด ๆ ให้เป็น KEM แบบ IND-CCA2 ในแบบจำลองออราเคิลสุ่ม (ROM) ML-KEM ใช้การแปลง FO ในรูปแบบหนึ่งกับการเข้ารหัสที่มี Module-LWE เป็นพื้นฐาน เพื่อให้มีความปลอดภัยแบบ CCA2 ที่จำเป็นต่อการนำไปใช้งานจริง

แบบจำลองออราเคิลสุ่ม (ROM) จำลองฟังก์ชันแฮชให้เป็นฟังก์ชันสุ่มอย่างแท้จริง บทพิสูจน์ความปลอดภัยจำนวนมาก รวมถึงบทพิสูจน์ของการแปลง FO จำเป็นต้องใช้ ROM ในทางปฏิบัติ ฟังก์ชันแฮชอย่าง SHA-3 ไม่ใช่ออราเคิลสุ่มอย่างแท้จริง ดังนั้นบทพิสูจน์ใน ROM จึงไม่ได้รับประกันความปลอดภัยในแบบจำลองมาตรฐาน อย่างไรก็ตาม บทพิสูจน์ใน ROM ได้รับการยอมรับอย่างกว้างขวางในชุมชนการเข้ารหัสลับว่าเป็นหลักฐานที่หนักแน่นของความปลอดภัย

บทพิสูจน์ในแบบจำลองมาตรฐานไม่ตั้งสมมติฐานเชิงอุดมคติเกี่ยวกับฟังก์ชันแฮช และแข็งแกร่งกว่าบทพิสูจน์ใน ROM อย่างเคร่งครัด โครงร่างแบบแลตทิซที่ใช้งานจริงส่วนใหญ่ใช้บทพิสูจน์ใน ROM เนื่องจากบทพิสูจน์ CCA2 ในแบบจำลองมาตรฐานสำหรับ KEM ที่อาศัยแลตทิซมีความซับซ้อนกว่ามาก และให้พารามิเตอร์เชิงรูปธรรมที่ด้อยกว่า NIST ยอมรับบทพิสูจน์ใน ROM สำหรับ ML-KEM โดยเห็นว่าเพียงพอสำหรับระดับความปลอดภัยที่ตั้งเป้าไว้

บทพิสูจน์ความปลอดภัยของ ML-KEM ดำเนินไปเป็นสองขั้นตอน ขั้นแรก แสดงให้เห็นว่าการเข้ารหัสที่มี Module-LWE เป็นพื้นฐานมีความปลอดภัยแบบ IND-CPA ภายใต้สมมติฐาน M-LWE ขั้นที่สอง การแปลง Fujisaki-Okamoto (โดยเฉพาะการแปลง T และ U ที่ใช้ใน Kyber) ยกระดับความปลอดภัยนี้เป็น IND-CCA2 ในออราเคิลสุ่มแบบควอนตัม (QROM) ซึ่งรองรับผู้โจมตีที่สอบถามออราเคิลสุ่มในสถานะซ้อนทับ

ตัวประเมินแลตทิซของ Albrecht, Player และ Scott เป็นเครื่องมือมาตรฐานสำหรับคำนวณความปลอดภัยเชิงรูปธรรมของโครงร่างที่อาศัย LWE เครื่องมือนี้จำลองต้นทุนของการโจมตีแลตทิซที่ดีที่สุดซึ่งเป็นที่รู้จัก (BKZ ร่วมกับการทำซีฟหรือการแจกแจง) และแสดงผลความปลอดภัยโดยประมาณเป็นบิตสำหรับพารามิเตอร์ที่กำหนด (n, q, sigma) เครื่องมือนี้ได้รับการปรับปรุงอย่างสม่ำเสมอเมื่อมีการเผยแพร่อัลกอริทึมและแบบจำลองต้นทุนฮาร์ดแวร์ใหม่ ๆ

อัลกอริทึม Block Korkine-Zolotarev (BKZ) เป็นอัลกอริทึมลดรูปแลตทิซที่ใช้งานได้จริงดีที่สุด BKZ ที่มีขนาดบล็อก beta สามารถค้นหาเวกเตอร์สั้นได้ โดยมีความซับซ้อนประมาณ 2^{0.292*beta} การดำเนินการเกตเมื่อใช้อัลกอริทึมทำซีฟที่ดีที่สุด สำหรับ ML-KEM-768 ความปลอดภัยแบบคลาสสิกที่ประเมินได้อยู่ที่ประมาณ 180 บิต และความปลอดภัยแบบควอนตัมอยู่ที่ประมาณ 164 บิต ซึ่งสูงกว่าเป้าหมาย 192 บิตอย่างมาก

บทพิสูจน์ความปลอดภัยเชิงเส้นกำกับแสดงว่าโครงร่างปลอดภัยเมื่อพารามิเตอร์มีขนาดใหญ่เพียงพอ แต่ไม่ได้ระบุว่า “เพียงพอ” ในทางปฏิบัติหมายถึงขนาดเท่าใด การวิเคราะห์ความปลอดภัยเชิงรูปธรรมช่วยเติมช่องว่างนี้ด้วยการประเมินต้นทุนจริงของการโจมตีที่ดีที่สุดสำหรับพารามิเตอร์ที่เลือก การจัดทำมาตรฐานหลังยุคควอนตัมพึ่งพาการวิเคราะห์ความปลอดภัยเชิงรูปธรรมอย่างมาก โดยเลือกพารามิเตอร์ให้ต้านทานการโจมตีจากฮาร์ดแวร์ควอนตัมที่คาดว่าจะมีในช่วงเวลา 30 ปี

การแปลงใดใช้เพื่อยกระดับการเข้ารหัสแบบ IND-CPA ที่อาศัยแลตทิซให้มีความปลอดภัยแบบ IND-CCA2 ใน ML-KEM

บทพิสูจน์ความปลอดภัยของโครงร่างแบบแลตทิซลดความปลอดภัยของโครงร่างลงเป็นความยากของ LWE หรือ SVP การลดรูปของ Regev รับประกันว่า LWE ยากอย่างน้อยเท่ากับปัญหาแลตทิซในกรณีเลวร้ายที่สุด การแปลง Fujisaki-Okamoto ยกระดับ IND-CPA เป็น IND-CCA2 ใน ROM ความปลอดภัยเชิงรูปธรรมประเมินด้วยตัวประเมินแลตทิซโดยใช้แบบจำลองความซับซ้อนของ BKZ ช่องว่างด้านความแน่นของการลดรูปทำให้พารามิเตอร์ในทางปฏิบัติต้องอาศัยค่าประเมินต้นทุนการโจมตี มากกว่าขอบเขตจากการลดรูปเพียงอย่างเดียว