NTRU: ประวัติ การออกแบบ และความปลอดภัย

NTRU ถูกคิดค้นโดย Hoffstein, Pipher และ Silverman ในปี 1996 ทำให้เป็นหนึ่งในระบบกุญแจสาธารณะหลังยุคควอนตัมที่เก่าแก่ที่สุดซึ่งยังถือว่าปลอดภัย ต่างจาก RSA และ ECC ซึ่งอาศัยความยากเชิงทฤษฎีจำนวน ความมั่นคงปลอดภัยของ NTRU ตั้งอยู่บนความยากในการค้นหาเวกเตอร์สั้นในแลตทิซเฉพาะที่สร้างจากริงพหุนาม NTRU ถูกนำไปทำเป็นผลิตภัณฑ์เชิงพาณิชย์และใช้งานในผลิตภัณฑ์ด้านความปลอดภัยหลายรายการ ก่อนที่การเข้ารหัสลับหลังยุคควอนตัมจะกลายเป็นกระแสหลัก

NTRU ทำงานในริงพหุนามแบบตัดทอน Z[X]/(X^N - 1) โดย N เป็นจำนวนเฉพาะ พหุนามในริงนี้มีดีกรีไม่เกิน N-1 และการคูณจะวนรอบ (คอนโวลูชัน) การเลือกริงและโครงสร้างของพหุนามที่มีสัมประสิทธิ์ขนาดเล็กเป็นหัวใจสำคัญของทั้งประสิทธิภาพและคุณสมบัติด้านความมั่นคงปลอดภัยของ NTRU

การสร้างกุญแจจะเลือกพหุนามขนาดเล็กสองตัวคือ f และ g ซึ่งมีสัมประสิทธิ์อยู่ใน {-1, 0, 1} พหุนาม f ต้องมีอินเวอร์สได้ทั้งเมื่อมอดุโล p (จำนวนเฉพาะขนาดเล็ก โดยทั่วไปคือ 3) และ q (จำนวนเฉพาะขนาดใหญ่กว่า โดยทั่วไปคือ 2048) กุญแจสาธารณะคือ h = f_q^{-1} * g mod q โดย f_q คืออินเวอร์สของ f มอดุโล q กุญแจส่วนตัวคือคู่ (f, g)

ในการเข้ารหัสพหุนามข้อความ m ที่มีสัมประสิทธิ์ขนาดเล็ก ผู้ส่งจะเลือกพหุนามพรางขนาดเล็กแบบสุ่ม r แล้วคำนวณ c = r * h + m mod q ข้อความเข้ารหัส c เป็นพหุนามในริงเดียวกัน r แบบสุ่มจะป้องกันไม่ให้การเข้ารหัสข้อความเดียวกันสองครั้งดูเหมือนกันทุกประการ และทำให้เกิดความมั่นคงปลอดภัยเชิงความหมาย

การถอดรหัสจะคำนวณ a = f * c mod q โดยเลือกสัมประสิทธิ์ให้อยู่ในช่วง (-q/2, q/2] จากนั้น a mod p จะกู้คืน f_p * m mod p และการคูณด้วย fp = f^{-1} mod p จะให้ค่า m โครงสร้างความผิดพลาดขนาดเล็กช่วยให้สัมประสิทธิ์ของ f * c มีขนาดเล็กพอที่การดำเนินการ mod q และ mod p จะทำงานสัมพันธ์กันอย่างถูกต้อง และกู้คืนข้อความได้โดยไม่เกิดความล้มเหลวจากสัญญาณรบกวน

NTRU สมัยใหม่มีตระกูลพารามิเตอร์ที่กำหนดมาตรฐานไว้สองตระกูล ได้แก่ NTRU-HPS (Hoffstein-Pipher-Silverman) และ NTRU-HRSS (Hulsing-Rijneveld-Schanck-Schwabe) NTRU-HPS ใช้พหุนามข้อความแบบไตรภาค ขณะที่ NTRU-HRSS ใช้การเข้ารหัสแบบสุ่มเพื่อให้อัตราความล้มเหลวในการถอดรหัสดีขึ้น ทั้งสองแบบเป็นผู้เข้ารอบสุดท้ายของการแข่งขัน NIST PQC รอบที่ 3 โดยมีชุดพารามิเตอร์ที่มุ่งเป้าความมั่นคงปลอดภัยระดับ 128, 192 และ 256 บิต

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

NTRU ได้รับการคุ้มครองด้วยสิทธิบัตรจำนวนมากโดย NTRU Cryptosystems Inc. (ต่อมาคือ Security Innovation) สิทธิบัตรดั้งเดิมยื่นในปี 1996 และ 1998 การคุ้มครองด้วยสิทธิบัตรนี้ขัดขวางการนำไปใช้อย่างแพร่หลายและการพัฒนาสิ่งใช้งานแบบโอเพนซอร์สเป็นเวลาถึงสองทศวรรษ สิทธิบัตรหลักของ NTRU หมดอายุประมาณปี 2017 หลังจากนั้นสิ่งใช้งานแบบเปิดก็แพร่หลาย และ NTRU ก็เข้าร่วมการแข่งขันกำหนดมาตรฐาน NIST PQC

NTRU เป็นผู้เข้ารอบสุดท้ายในรอบที่ 3 ของการแข่งขัน NIST PQC ร่วมกับ Kyber, Classic McEliece และ SABER ในที่สุด NIST เลือก Kyber (ML-KEM) เป็นมาตรฐาน KEM หลัก โดยอ้างถึงการวิเคราะห์ความมั่นคงปลอดภัยที่ง่ายกว่าและการออกแบบที่สะอาดกว่า NTRU ไม่ได้ถูกกำหนดเป็นมาตรฐาน แต่ยังคงเป็นทางเลือกที่ใช้งานได้ และการวิเคราะห์ NTRU ก็มีส่วนช่วยให้เข้าใจความมั่นคงปลอดภัยของแลตทิซมากขึ้น

NTRUPrime ซึ่งพัฒนาโดย Bernstein, Chuengsatiansup, Lange และ van Vredendaal จงใจนำโครงสร้างริง X^N - 1 ออก แล้วแทนที่ด้วย X^N - X - 1 ซึ่งเป็นพหุนามดีกรีจำนวนเฉพาะ การทำเช่นนี้กำจัดจุดอ่อนที่อาจเกิดจากโครงสร้างริงแบบวัฏจักร ซึ่งนักวิเคราะห์การเข้ารหัสบางคนเชื่อว่าอาจถูกโจมตีได้ NTRUPrime ยังเป็นผู้สมัครทางเลือกของ NIST PQC ด้วย

NTRU มีมาก่อนโครงร่างที่อาศัย LWE และไม่มีการลดรูปความยากในกรณีเลวร้ายที่สุดอย่างเป็นทางการเหมือนการลดรูป LWE ของ Regev อย่างไรก็ตาม NTRU สร้างกุญแจได้เร็วกว่าและมีขนาดข้อความเข้ารหัสเล็กกว่าโครงร่าง LWE หลายแบบที่มีระดับความมั่นคงปลอดภัยเทียบเท่ากัน ข้อแลกเปลี่ยนคือมีรากฐานด้านความมั่นคงปลอดภัยที่เป็นทางการน้อยกว่า โดยอาศัยประสบการณ์การวิเคราะห์การเข้ารหัสตลอดหลายทศวรรษแทนการพิสูจน์ด้วยการลดรูป

ใน NTRU กุญแจสาธารณะได้มาจากอะไร

NTRU เป็นระบบเข้ารหัสลับบนแลตทิซรุ่นบุกเบิกที่อาศัยเลขคณิตของริงพหุนาม การสร้างกุญแจใช้พหุนามขนาดเล็ก f และ g โดยมีกุญแจสาธารณะ h = f^{-1}*g mod q การเข้ารหัสใช้การพรางแบบสุ่ม ส่วนการถอดรหัสอาศัยโครงสร้างสัมประสิทธิ์ขนาดเล็กของ f NTRU ไม่มีการลดรูปจากกรณีเลวร้ายที่สุดอย่างเป็นทางการ แต่ผ่านการวิเคราะห์การเข้ารหัสมาหลายทศวรรษ สิทธิบัตรของ NTRU หมดอายุในปี 2017 และ NTRU เป็นผู้เข้ารอบสุดท้ายของ NIST PQC รอบที่ 3