ما هي مشكلة الشبكة الصلبة؟ خيط 🧵

تعتمد التشفير القائم على الشبكة على تحد مركزي: إيجاد حل متجه قصير s لنظام من المعادلات الخطية بترديد عدد صحيح q (عادة قوة أولية أو أولية). تسمى هذه مشكلة SIS (حل الأعداد الصحيحة القصيرة)، بسيطة في شكلها لكنها تعتبر صعبة ضد الهجمات الكمومية/الكلاسيكية.

هناك نسختان رئيسيتان: الشكل غير المتجانس المستخدم كدالة أحادية الاتجاه f_A(s) = A * s mod q في مخططات الالتزام، حيث نحل A * s = t (mod q) معطى A والهدف t...

... ومشكلة SIS المتجانسة، التي تطلب إيجاد s قصير بحيث A * s = 0 (mod q) لمصفوفة عشوائية A.

نظام الالتزام مضمون أن يكون ملزما بسبب صلابة نظام SIS. إذا كان A * s = t = A * s'، فإن A * (s - s') = 0، مما يعني أن إيجاد s' مختلف يحل مشكلة SIS المتجانسة الصلبة.

قصر ال s (المعيار الصغير) أمر أساسي. بدون حدود s، تكون الحلول تافهة باستخدام الجبر الخطي الكلاسيكي. هذا القيد المعياري يدعم الطبيعة الصعبة في حل نظام المعلومات الاستراتيجية، حتى ضد الحواسيب الكمومية.

ربطت نتيجة أجتاي عام 1996 صلابة مشكلة SIS بحل مشاكل الشبكة الأسوأ حالا، مما شكل أساسا لافتراضات التشفير ما بعد الكم.

تمكن مشكلة SIS من الضغط من متجه سري كبير s (بعد M) إلى التزام أقصر t. المصفوفة A لها أبعاد N x M، حيث يرتبط N عادة بمعامل الأمان، مما يجعلها جذابة لبراهين المعرفة الصفرية التي تتطلب إيجازا.

مجتمعة، من السهل ذكر SIS لكنه صعب للغاية في الحل، ويلعب دورا أساسيا في الالتزامات، وإثبات المعرفة الصفرية، وأمن ما بعد الكمومي الأوسع.