NTRU: التاريخ والتصميم والأمان

ابتكر Hoffstein وPipher وSilverman نظام NTRU عام 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، مع مجموعات معلمات تستهدف أمانًا بمستويات 128 و192 و256 بت.

لا يُعرف أي هجوم بزمن متعدد الحدود ضد NTRU ذي المعلمات المختارة بصورة صحيحة. وتُختزل أفضل الهجمات إلى إيجاد متجه قصير في شبكة NTRU، وهي حالة من مشكلة SVP التقريبية. وتمتلك شبكة NTRU بنية محددة، هي الكتل الدورانية، تجعل مهاجمتها أسهل قليلًا من مهاجمة شبكة عشوائية؛ لذلك تُختار المعلمات مع هامش أمان يراعي هذه البنية.

حظي NTRU بحماية واسعة ببراءات الاختراع من شركة NTRU Cryptosystems Inc.، التي أصبحت لاحقًا Security Innovation. وقد أودعت براءات الاختراع الأصلية عامي 1996 و1998. وأعاقت هذه الحماية انتشار الاعتماد على NTRU وتطبيقاته مفتوحة المصدر طوال عقدين. وانتهت صلاحية براءات NTRU الأساسية نحو عام 2017، وبعد ذلك انتشرت التطبيقات المفتوحة ودخل NTRU منافسة توحيد المعايير الخاصة بـ NIST PQC.

كان NTRU مرشحًا نهائيًا في الجولة الثالثة من مسابقة NIST PQC إلى جانب Kyber وClassic McEliece وSABER. واختارت NIST في النهاية Kyber، المعروف باسم ML-KEM، معيارًا أساسيًا لـ KEM، مستندةً إلى بساطة تحليله الأمني ونظافة تصميمه. ولم يُقنّن NTRU، لكنه لا يزال بديلًا قابلًا للتطبيق، كما أسهم تحليله في فهم أمان الشبكات.

طوّر Bernstein وChuengsatiansup وLange وvan Vredendaal نظام NTRUPrime، فأزال عمدًا بنية الحلقة X^N - 1 واستبدل بها X^N - X - 1، وهو كثير حدود من درجة أولية. ويزيل ذلك نقاط الضعف المحتملة الناتجة عن بنية الحلقة الدورية، التي يعتقد بعض محللي الشفرات أنه يمكن استغلالها. وكان NTRUPrime أيضًا مرشحًا بديلًا في NIST PQC.

ظهر NTRU قبل المخططات القائمة على LWE، ولا يملك اختزالًا رسميًا للصعوبة في الحالة الأسوأ مثل اختزال Regev الخاص بـ LWE. ومع ذلك، فإن NTRU أسرع في توليد المفاتيح، وله أحجام نصوص مشفرة أصغر من كثير من مخططات LWE عند مستويات الأمان المتكافئة. والمقابل هو أساس أمني أقل رسمية، يعتمد على عقود من الخبرة في تحليل الشفرات بدلًا من برهان اختزال.

NTRU نظام تشفير رائد قائم على الشبكات، ويعتمد على حساب كثيرات الحدود في الحلقات. يستخدم توليد المفاتيح كثيرتي الحدود الصغيرتين f وg، مع مفتاح عام h = f^{-1}*g mod q. ويستخدم التشفير تعمية عشوائية، بينما يستغل فك التشفير بنية f ذات المعاملات الصغيرة. ولا يملك NTRU اختزالًا رسميًا من الحالة الأسوأ، لكنه صمد أمام عقود من تحليل الشفرات. وانتهت صلاحية براءات اختراعه عام 2017، وكان مرشحًا نهائيًا في الجولة الثالثة من NIST PQC.