التشفير القائم على الشبكة

التشفير القائم على الشبكات هو مصطلح عام يُطلق على بنى التشفير الأساسية التي تتضمن الشبكات ، سواء في البنية نفسها أو في برهان الأمان. تدعم هذه البنى معايير مهمة في التشفير ما بعد الكمومي . ^{[ 1 ]} على عكس أنظمة المفتاح العام الأكثر شيوعًا وشهرة، مثل RSA و Diffie-Hellman وأنظمة تشفير المنحنيات الإهليلجية - والتي يُمكن نظريًا اختراقها باستخدام خوارزمية شور على حاسوب كمومي - تبدو بعض البنى القائمة على الشبكات مقاومة للهجمات من قِبل الحواسيب الكلاسيكية والكمومية على حد سواء. علاوة على ذلك، تُعتبر العديد من هذه البنى آمنة بافتراض عدم إمكانية حل بعض مسائل الشبكات الحسابية المدروسة جيدًا بكفاءة.

في عام 2024، أعلن المعهد الوطني للمعايير والتكنولوجيا (NIST) عن معيار التوقيع الرقمي القائم على الشبكة المعيارية للتشفير ما بعد الكمي. ^{[ 2 ]}

في عام 1996، قدّم ميكلوس أيتائي أول بنية تشفيرية قائمة على الشبكات، والتي يمكن أن يستند أمانها إلى صعوبة مسائل الشبكات المدروسة جيدًا، ^{[ 3 ]} وأظهرت سينثيا دورك أن مسألة شبكة معينة في الحالة المتوسطة، والمعروفة باسم حلول الأعداد الصحيحة القصيرة (SIS)، لا تقل صعوبة عن حل مسألة شبكة في أسوأ الحالات . ^{[ 4 ]} ثم عرضت دالة تجزئة تشفيرية يكون أمانها مكافئًا للصعوبة الحسابية لـ SIS.

في عام 1998، قدم جيفري هوفستين وجيل بايفر وجوزيف هـ. سيلفرمان نظام تشفير بالمفتاح العام قائم على الشبكة ، يُعرف باسم NTRU . ^{[ 5 ]} ومع ذلك، من غير المعروف أن نظامهم صعب على الأقل مثل حل مشكلة الشبكة في أسوأ الحالات.

قدّم أوديد ريغيف في عام 2005 أول نظام تشفير بالمفتاح العام قائم على الشبكة، والذي تم إثبات أمانه في ظل افتراضات صعوبة الحالات القصوى، ^{[ 6 ]} إلى جانب مشكلة التعلم مع الأخطاء (LWE). ومنذ ذلك الحين، ركزت العديد من الدراسات اللاحقة على تحسين برهان أمان ريغيف ^{[ 7 ] [ 8 ]} وتحسين كفاءة النظام الأصلي. ^{[ 9 ] [ 10 ] [ 11 ] [ 12 ]} كما تم تخصيص المزيد من الجهود لبناء عناصر تشفيرية أساسية إضافية استنادًا إلى مشكلة التعلم مع الأخطاء والمسائل ذات الصلة. على سبيل المثال، في عام 2009، قدّم كريغ جينتري أول نظام تشفير متماثل تمامًا ، والذي كان قائمًا على مشكلة الشبكة. ^{[ 13 ]}

في الجبر الخطي ، الشبكة${\displaystyle L\subset \mathbb {R} ^{n}}$هي مجموعة جميع التراكيب الخطية الصحيحة للمتجهات من أساس${\displaystyle \{\mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\}}$ل${\displaystyle \mathbb {R} ^{n}}$. بعبارة أخرى، ${\displaystyle L={\Big \{}\sum a_{i}\mathbf {b} _{i}:a_{i}\in \mathbb {Z} {\Big \}}.}$ على سبيل المثال،${\displaystyle \mathbb {Z} ^{n}}$هي شبكة، يتم توليدها بواسطة الأساس القياسي لـ${\displaystyle \mathbb {R} ^{n}}$الأهم من ذلك، أن أساس الشبكة ليس فريدًا. على سبيل المثال، المتجهات${\displaystyle (3,1,4)}$،${\displaystyle (1,5,9)}$، و${\displaystyle (2,-1,0)}$تشكيل أساس بديل لـ${\displaystyle \mathbb {Z} ^{3}}$.

تُعدّ مسألة أقصر متجه (SVP أو أحيانًا GapSVP) أهمّ مسألة حسابية قائمة على الشبكات ، وهي مسألة تتطلب إيجاد أقصر طول إقليدي تقريبي لمتجه شبكي غير صفري. ويُعتقد أن حلّ هذه المسألة بكفاءة أمرٌ صعب، حتى مع استخدام عوامل تقريبية متعددة الحدود.${\displaystyle n}$وحتى باستخدام حاسوب كمومي. من المعروف أن العديد من البنى التشفيرية القائمة على الشبكات (وإن لم تكن جميعها) آمنة إذا كانت مسألة القيمة القصوى (SVP) صعبة بالفعل في هذا النظام.

يعرض هذا القسم مخططات مختارة تعتمد على الشبكة، مصنفة حسب العناصر الأولية.

تُبشّر البنى التشفيرية القائمة على الشبكات بآفاق واعدة في مجال التشفير ما بعد الكمومي باستخدام المفتاح العام . ^{[ 38 ]} في الواقع، تتمثل الأشكال البديلة الرئيسية للتشفير باستخدام المفتاح العام في مخططات تعتمد على صعوبة التحليل إلى عوامل أولية والمسائل ذات الصلة ، ومخططات أخرى تعتمد على صعوبة اللوغاريتم المتقطع والمسائل ذات الصلة . مع ذلك، من المعروف أن كلاً من التحليل إلى عوامل أولية ومسألة اللوغاريتم المتقطع قابلة للحل في وقت متعدد الحدود على الحاسوب الكمومي . ^{[ 39 ]} علاوة على ذلك، تميل خوارزميات التحليل إلى إنتاج خوارزميات للوغاريتم المتقطع، والعكس صحيح. وهذا بدوره يحفز دراسة البنى القائمة على افتراضات بديلة، مثل صعوبة مسائل الشبكات.

من المعروف أن العديد من أنظمة التشفير القائمة على الشبكات آمنة بافتراض صعوبة أسوأ الحالات لبعض مسائل الشبكات. ^{[ 3 ] [ 6 ] [ 7 ]} أي، إذا وُجدت خوارزمية قادرة على كسر نظام التشفير بكفاءة باحتمالية غير مهملة، فإنه توجد خوارزمية فعالة لحل مسألة شبكة معينة على أي مُدخل. مع ذلك، بالنسبة للتركيبات العملية القائمة على الشبكات (مثل الأنظمة القائمة على NTRU وحتى الأنظمة القائمة على LWE ذات المعاملات الفعالة)، لا توجد ضمانات أمنية ذات دلالة قائمة على الاختزال.

تُسمى تقييمات مستويات الأمان التي توفرها حجج الاختزال من المسائل الصعبة - استنادًا إلى أحجام المعلمات الموصى بها، والتقديرات القياسية للتعقيد الحسابي للمسائل الصعبة، والفحص التفصيلي لخطوات الاختزال - بالأمان الملموس ، وأحيانًا بالأمان القابل للإثبات الموجه نحو التطبيق العملي . ^{[ 40 ]} وقد وجد بعض الباحثين الذين درسوا الأمان الملموس لأنظمة التشفير القائمة على الشبكات أن نتائج الأمان القابل للإثبات لهذه الأنظمة لا توفر أي أمان ملموس ذي معنى للقيم العملية للمعلمات. ^{[ 41 ]}

بالنسبة للعديد من العناصر الأساسية للتشفير، فإن البنى المعروفة الوحيدة تعتمد على الشبكات أو الكائنات ذات الصلة الوثيقة بها. وتشمل هذه العناصر التشفير المتماثل تمامًا ، ^{[ 13 ]} والتشويش غير القابل للتمييز ، ^{[ 42 ]} والخرائط الخطية المتعددة للتشفير ، والتشفير الوظيفي . ^{[ 42 ]}

• مشاكل الشبكة
• التعلم من الأخطاء
• التشفير المتماثل
• التشفير ما بعد الكمي
• التعلم الحلقي مع الأخطاء
• التعلم الحلقي مع تبادل مفاتيح الأخطاء

• جولدرايش، عوديد؛ جولدفاسر، شافي؛ هاليفي، شاي (1997). "أنظمة التشفير بالمفتاح العام من مسائل اختزال الشبكة". كريبتو 97: وقائع المؤتمر الدولي السنوي السابع عشر لعلم التشفير حول التطورات في علم التشفير . لندن، المملكة المتحدة: سبرينغر-فيرلاغ. ص 112-131 . doi : 10.1007/BFb0052231 . ISBN  978-3-540-63384-6.
• ريجيف، أوديد (2006). "التشفير القائم على الشبكة". التطورات في علم التشفير (CRYPTO) . سبرينغر-فيرلاغ. ص 131-141 . doi : 10.1007/11818175_8 . ISBN  978-3-540-37432-9.

• عرض توضيحي لـ Dilithium في Excel - مثال على التنفيذ والتوضيح في Excel (بدون وحدات ماكرو) بواسطة Tim Wambach.