💻 computer science

Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits

تقدم هذه الورقة مفهوم التقييم الموجز والمنسي للموتور (OTE) المبني على فرضية (LWE) القياسية، والذي يعمل كأداة أساسية لتحقيق التقييم الموجز والآمن تكيفياً للدوال الإيجازية، وتجزئة الباب الخلفي لجميع الدوائر، وغيرها من الأوليات التشفيرية المثلى.

المؤلفون الأصليون: Damiano Abram, Giulio Malavolta, Lawrence Roy

نُشر 2026-04-21

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Damiano Abram, Giulio Malavolta, Lawrence Roy

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك تحاول حل لغز ضخم مع صديق لك، لكنكما في غرفتين مختلفتين ولا يمكنكما سوى إرسال ملاحظة قصيرة واحدة لبعضكما البعض في نفس الوقت. تريد الوصول إلى نتيجة معقدة بناءً على معلوماتكما المشتركة، ولكنك لا تريد الكشف عن قطع معلوماتك السرية للطرف الآخر.

تقدم هذه الورقة البحثية طريقة جديدة وعالية الكفاءة للقيام بذلك بالضبط، ثم توضح كيف يمكن لهذه الحيلة أن تفتح عالماً جديداً بالكامل من الحوسبة الآمنة.

إليك تفصيل ذلك بأسلوب مبسط:

1. المشكلة الجوهرية: لغز "التنسور" (Tensor)

تخيل أن أليس لديها قائمة ضخمة من الأرقام (متجه - vector) وبوب لديه قائمة سرية أصغر. يريدان حساب "حاصل الضرب التنسوري" (Tensor Product).

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

2. الخدعة السحرية: "التقييم التنسوري الخفي" (OTE)

يسمون هذه الأداة الجديدة "التقييم التنسوري الموجز والخفي" (Succinct Oblivious Tensor Evaluation).

خفي (Oblivious): لا تعرف أليس أرقام بوب السرية، ولا يعرف بوب أرقام أليس.
موجز (Succinct): الرسائل صغيرة جداً، بغض النظر عن حجم البيانات الأصلية.
السر المكنون: استخدموا مفهوماً رياضياً يسمى LWE (التعلم مع الأخطاء). تخيل هذا كـ "قفل صاخب". يمكنك قفل رسالة داخل صندوق، لكن الصندوق مهتز قليلاً (صاخب). فقط الشخص الذي يملك المفتاح الصحيح يمكنه هز الصندوق بالقدر المناسب لسماع الرسالة بداخله، بينما لا يسمع أي شخص آخر سوى الضجيج. اكتشف المؤلفون كيفية جعل هذه الأقفال الصاخبة تعمل معاً في سلسلة بحيث يلغي الضجيج بعضه البعض تماماً في النهاية، ليكشف عن الإجابة.

3. المكاسب الكبرى: ماذا يمكننا أن نفعل الآن؟

بمجرد بناء آلة "الملاحظة الصغيرة" هذه، استخدموها لبناء عدة أدوات قوية أخرى:

أ. "فتح الأقفال الشامل" (Trapdoor Hash)

الطريقة القديمة: للتحقق مما إذا كان مفتاح معين يفتح قفلاً معيلاً، يتعين عليك عادةً إرسال المخطط الكامل للقفل إلى حامله.
الطريقة الجديدة: باستخدام أداتهم الجديدة، يمكن لحامل القفل إرسال "بصمة" (hash) صغيرة للقفل. يمكن لحامل المفتاح بعد ذلك إثبات امتلاكه للمفتاح الصحيح دون الكشف عن المفتاح نفسه أو المخطط الكامل. وهذا يعمل مع أي دالة، حتى البرامج الحاسوبية المعقدة، وليس فقط العمليات الرياضية البسيطة.

ب. "الوصفة السرية" (Homomorphic Secret Sharing)

السيناريو: تريد أليس وبوب طهي وجبة معاً (حساب دالة) باستخدام مكوناتهما السرية الخاصة.
الطريقة القديمة: كان عليهما إرسال قوائم ضخمة من المكونات ذهاباً وإياباً.
الطريقة الجديدة: يمكنهما إرسال ملاحظات مشفرة صغيرة. عندما يدمجان ملاحظاتهما، يحصلان على الطبق النهائي (النتيجة) دون أن يرى أي منهما مكونات الآخر. هذا هو "تقاسم الأسرار المتماثل" (Homomorphic Secret Sharing)، وهو يعمل الآن مع أي وصفة، وليس فقط الوصفات البسيطة.

ج. "درع الخصوصية التكيفي" (Laconic Function Evaluation)

المشكلة: في العديد من الأنظمة الآمنة، يجب عليك تحديد ما تريد حسابه قبل بدء المحادثة. إذا غيرت رأيك لاحقاً، فعليك البدء من جديد.
الحل: ابتكر المؤلفون نظاماً آمناً تكيفياً (Adaptively Secure). هذا يعني أن "المهاجم" يمكنه الانتظار، ورؤية الإعداد العام، ومن ثم اختيار ما سيهاجمه. يظل النظام آمناً حتى في هذا السيناريو الصعب.
ميزة "المعدل-1" (Rate-1): لقد حققوا "المعدل-1"، وهو الحد النظري للكفاءة. هذا يعني أن كمية البيانات التي ترسلونها هي تقريباً نفس حجم الإجابة التي تحصلون عليها. لا يوجد هدر في المساحة.

4. لماذا هذا مهم؟

قبل هذه الورقة البحثية، إذا كنت تريد إجراء حسابات معقدة وخاصة بين شخصين بأقل قدر من الاتصالات، كان عليك إما:

إرسال كميات ضخمة من البيانات (بطيء).
الوثوق بافتراض رياضي قوي وغير مثبت (مخاطرة).
القيام بعمليات رياضية بسيطة فقط (محدود).

تقول هذه الورقة: "يمكننا إجراء اتصالات معقدة وخاصة وثنائية الاتجاه برسائل صغيرة، ويمكننا إثبات سلامتها باستخدام رياضيات قياسية ومعروفة جيداً."

ملخص التشبيه

تخيل أنك وصديقك تحاولان حساب التكلفة الإجمالية لقائمة تسوق ضخمة (قائمة أليس) مدمجة مع رمز خصم سري (قائمة بوب).

قبل: كان عليكما إرسال قائمة التسوق المكونة من 500 صفحة وكتاب الرموز المكون من 50 صفحة عبر البريد لبعضكما البعض.
بعد: يكتب كل منكما جملة واحدة على بطاقة بريدية. ترسلانها في وقت واحد. يقرأ كل منكما البطاقات، ويجري القليل من الحسابات في ذهنه، وفجأة يعرف كلاكما السعر النهائي. لم يرَ أي منكما قائمة الآخر أو كتاب الرموز، وكانت البطاقات البريدية صغيرة جداً.

لم يكتفِ المؤلفون بإيجاد طريقة أفضل لإرسال البطاقات البريدية؛ بل بنوا آلة تجعل هذه البطاقات البريدية تعمل لأي عملية حسابية سرية، مما يمهد الطريق لتأمين إنترنت أسرع وأكثر خصوصية وكفاءة.

إليك ملخص تقني مفصل للورقة البحثية بعنوان "تقييم الموتر الموجز والمنفصل (Succinct Oblivious Tensor Evaluation) وتطبيقاته: تقييم الدوال اللاتونية (Laconic Function Evaluation) آمن تكيّفيًا والهاش ذو الباب الخلفي (Trapdoor Hashing) لجميع الدوائر" من إعداد Abram وMalavolta وRoy.

1. بيان المشكلة

تتناول الورقة مشكلة تقييم الموتر المنفصل غير التفاعلي (NI-OTE). في هذا السيناريو، يمتلك طرفان، أليس (الهاشر/Hasher) وبوب (المُشفّر/Encoder)، المتجهات $x \in \mathbb{Z}_q^m$ و $y \in \mathbb{Z}_q^\ell$ على التوالي. يرغبون في تبادل جولة واحدة متزامنة من الرسائل لحساب تقاسم سري جمعي لضرب الموتر $x \otimes y$ محليًا (أي $v + w = x \otimes y$ ) دون الكشف عن مدخلاتهما الخاصة لبعضهما البعض.

التحدي الجوهري:
الهدف الأساسي هو كفاءة الاتصال. بديهيًا، يتطلب تحديد ضرب الموتر اتصالًا يتناسب مع حجم المدخلات ( $m \cdot \ell$ ). يهدف المؤلفون إلى بناء بروتوكول يكون فيه تعقيد الاتصال موجزًا (succinct)، وتحديدًا لوغاريتميًا في بُعد المدخل الأكبر ( $m$ )، مع الحفاظ على الأمان بناءً على الافتراضات التشفيرية القياسية (LWE - التعلم مع الأخطاء).

علاوة على ذلك، تسعى هذه الورقة إلى الاستفيد من هذا النموذج الأولي لحل مشكلات مفتوحة في تقييم الدوال اللاتونية (LFE) والهاش ذو الباب الخلفي (TDH)، وتحديدًا تحقيق:

الأمان التكيفي (Adaptive Security): الأمان ضد الخصوم الذين يختارون المدخلات بعد رؤية المعلمات العامة.
المعدل-1 (Rate-1): حجم الاتصال يتناسب مع حجم المدخل/المخرج بالإضافة إلى حمل إضافي صغير، بدلًا من التضخم متعدد الحدود.
دعم جميع الدوائر: التوسع إلى ما وراء الدوال الخطية أو فئات الدوائر المقيدة (مثل $\mathsf{NC}^1$ ).

2. المنهجية والنهج التقني

يعتمد نهج المؤلفين على تسلسل هرمي من النماذج التشفيرية الأولية، بدءًا من بناء OTE جديد وتطورًا إلى ترميزات شبكية (lattice encodings) ومخططات تقييم الدوال.

أ. بناء NI-OTE نصف الموجز (Half-Succinct)

يتم بناء الـ OTE عبر مرحلتين:

NI-OTE نصف الموجز:
- الإعداد (Setup): توليد مصفوفة عشوائية $A \in \mathbb{Z}_q^{n \times m}$ ومصفوفة $B$ .
- الهاش (أليس): تحسب الملخص $d = A \cdot x$ .
- التشفير (بوب): يحسب مصفوفة $C$ تتضمن $A^\top$ ، ومصفوفة عشوائية $S$ ، وضجيجًا (noise)، والمدخل $y$ .
- التقييم: تحسب أليس $v = C^\top x$ ويحسب بوب $w = -S^\top d$ . المجموع $v+w$ يعطي $x \otimes y$ بالإضافة إلى ضجيج صغير.
- القصور: في هذه النسخة الأولية، يعتمد حجم رسالة بوب على $m$ (طول $x$ ).
الارتقاء إلى NI-OTE موجز بالكامل (Fully-Succinct):
- لجعل رسالة بوب موجزة، يستخدم المؤلفون استراتيجية ضغط تكرارية.
- العشوائية الزائفة (Pseudorandomness): بدلًا من أخذ عينات من مصفوفة عشوائية كبيرة $S$ ، يقومون بتوليد $S$ بشكل عشوائي زائف باستخدام عينات LWE المستمدة من متجه سري أصغر $s$ .
- التكرار (Recursion): يتم تطبيق البروتوكول بشكل تكراري. تقوم أليس بعمل هاش لمجموعات (blocks) من مدخلاتها $x$ لإنتاج ملخصات. بوب يشفر "العشوائية" المستخدمة في الخطوة السابقة.
- الرؤية الجوهرية: من خلال استخدام مصفوفات ثنائية وخصائص LWE محددة، يظل حجم متجه العشوائية $s$ ثابتًا عبر مستويات التكرار، بينما يتقلص حجم الملخص. يسمح هذا للبروتوكول بضغط مدخلات أليس إلى حجم لوغاريتمي دون أن يؤدي ذلك إلى تضخم رسالة بوب.

ب. الترميزات الشبكية التكيفية (Adaptive Lattice Encodings)

الابتكار التقني الحاسم هو تقديم الترميزات الشبكية التكيفية، والتي تتغلب على قيود ترميزات BGG+ القياسية (Boneh et al., 2014).

المشكلة في BGG+: الترميزات الشبكية القياسية آمنة فقط في الإعداد الانتقائي (حيث يكون المدخل ثابتًا قبل المفتاح العام). إذا تم اختيار المدخل تكيّفيًا (بعد رؤية المفتاح العام)، توجد هجمات لاستعادة المفتاح السري.
الحل: يقترح المؤلفون تنسيق ترميز جديد:
$c^\top = s^\top A + r^\top (x^\top \otimes G) + e^\top$
هنا، $s$ هو مفتاح التشفير و $r$ هو مفتاح المصادقة.
الخصائص الهومومورفية (Homomorphic Properties): يوضحون كيفية إجراء العمليات الخطية وعمليات الضرب بين الترميزات ذات المفاتيح المرتبطة (على سبيل المثال، ضرب ترميز بمفاتيح $(s, r)$ وترمز آخر بمفاتيح $(r, t)$ ينتج ترميزًا بمفاتيح $(s, t)$ ).
الضغط: يقدمون تقنية ضغط باستخدام OTE الموجز لضغط هذه الترميزات التكيفية، مما يسمح للحجم بالتوسع لوغاريتميًا مع طول المدخل مع الحفاظ على الأمان التكيفي.

ج. الهاش ذو الباب الخلفي العكسي (Reverse Trapdoor Hashing - TDH)

يبني المؤلفون Reverse TDH حيث يمتلك الهاشر دالة $f$ ويمتلك المُشفّر مدخلًا $x$ .

الآلية: يرسل الهاشر ملخصًا لـ $f$ . يرسل المُشفّر ترميزًا لـ $x$ . يقومان محليًا بحساب التقاسم السري لـ $f(x)$ .
الابتكار: من خلال الجمع بين MOLE الموجز (Matrix Oblivious Linear Evaluation، المشتق من OTE) والترميزات الشبكية التكيفية، يحققون مخططًا يعتمد فيه حجم مفتاح الترميز فقط على وصف الدالة $f$ (وهو مستقل عن حجم المدخل $m$ )، ويكون الملخص بحجم ثابت.

د. LFE بمعدل-1 (Rate-1 Adaptive LFE)

أخيرًا، يبنون مخطط تقييم الدوال اللاتونية (LFE).

الهيكل: يرسل الهاشر هاش لـ $f$ . يرسل المُشفّر ترميزًا لـ $x$ . يستعيد الهاشر $f(x)$ .
التقنية: يقومون بتفكيك الدالة $f$ إلى سلسلة من برامج $\mathsf{RMS}$ (Restricted Multiplication Straightline) الضحلة. يستخدمون Reverse TDH الموجز للمدخلات (حيث يعرف المُشفّر المدخل لتوليد المفتاح، لكن الهاش يكون موجزًا) لتقييم هذه الطبقات بشكل تكراري.
الخصوصية: لضمان عدم تعلم الهاشر لـ $x$ أثناء العملية التكرارية، يستخدمون تشفير FHE من نوع GSW لتشفير $x$ وتقييم الدالة هومومورفيًا، مما يزيل الـ one-time pad في النهاية.

3. المساهمات الرئيسية

NI-OTE موجز من LWE القياسي:
- أول بناء لـ OTE غير تفاعلي بتعقيد اتصال لوغاريتمي في بُعد المدخل، بناءً فقط على افتراض LWE القياسي.
- يحقق معدلات اتصال مثالية (Rate-1/2 للـ batched OT).
الترميزات الشبكية التكيفية:
- تقدم مخطط ترميز جديد يكون آمنًا ضد الهجمات التكيفية تحت افتراض LWE القياسي، متجاوزًا الحاجة إلى افتراض "LWE التكيفي" (الذي كان يُفترض سابقًا أنه موجود ولكن أثبت المؤلفون خطأه).
- تقدم مثالاً مضادًا لافتراض Adaptive LWE الخاص بـ Quach وWee وWichs (FOCS 2018).
أول LFE بمعدل-1 آمن تكيّفيًا:
- بناء أول مخطط LFE يكون في آن واحد آمنًا تكيّفيًا وبمعدل-1 (الاتصال $\approx m + \ell + D \cdot \text{poly}(\lambda)$ ).
- الأعمال السابقة حققت إما الأمان التكيفي (بمعدلات سيئة) أو المعدل-1 (بافتراضات أمنية ضعيفة).
الهاش ذو الباب الخلفي الشامل (Universal TDH):
- بناء TDH لكل الدوال (وبرامج RAM) بحجم مفتاح ترميز خطي في حجم وصف الدالة $|f|$ ومستقل عن حجم المدخل.
- تحسين العمل السابق الذي كان مقتصرًا على الدوال الخطية أو يتطلب CRS غير موجز.
التقاسم السري الهومومرفي الموجز (Succinct HSS):
- توفير مخطط HSS بمفتاح عام لجميع الدوال بتعقيد اتصال لوغاريتمي في المدخل الطويل، مما يحسن المخططات السابقة المقتصرة على $\mathsf{NC}^1$ أو ذات الاتصال متعدد الحدود.

4. النتائج والأداء

تعقيد الاتصال:
- NI-OTE: $O(\ell \cdot \text{poly}(\lambda) + \text{poly}(\lambda, \log m))$ .
- LFE: $m + \ell + D \cdot \text{poly}(\lambda, \log m, \log \ell, \log D)$ .
- TDH: حجم مفتاح الترميز $|f| \cdot \text{poly}(\lambda, \log m)$ .
الأمان: جميع النتائج مثبتة تحت افتراض LWE القياسي. لا تتطلب النتائج الرئيسية أي افتراضات غير قياسية (مثل Circular LWE أو Adaptive LWE)، رغم ذكر Circular LWE لتحسين بعض المعلمات.
المعدل (Rate): تحقق مخططات LFE وOT معدل Rate-1 (أو Rate-1/2 للـ batched OT)، وهو مثالي تقاربيًا.

5. الأهمية

تمثل هذه الورقة تقدمًا كبيرًا في مجال التشفير الموجز والحوسبة الآمنة:

كسر الحاجز التكيفي: تحل مشكلة مفتوحة طويلة الأمد تتمثل في بناء LFE وTDH آمن تكيّفيًا من افتراضات قياسية. المثال المضاد لـ Adaptive LWE يوضح المشهد لافتراضات الشبكة، ويظهر أن المعلمات "المتفائلة" السابقة كانت غير آمنة.
المثالية (Optimality): معدلات الاتصال التي تم تحقيقها مثالية. على سبيل المثال، في LFE، لا يمكن أن يكون الاتصال أصغر من حجم المدخل زائد حجم المخرج؛ وهذا العمل يحقق ذلك بالضبط بالإضافة إلى حمل إضافي صغير يعتمد على العمق.
نموذج أولي جديد (OTE): يعد الـ Succinct NI-OTE لبنة بناء جديدة وقوية تتيح تقييمًا آمنًا وفعالًا لضرب الموترات، وهي عمليات أساسية للعديد من البروتوكولات التشفيرية (مثل Private Set Intersection، وSecure Multi-party Computation).
الآثار العملية: القدرة على تقييم دوال عشوائية باتصال موجز وأمان تكيّفي تفتح الأبواب أمام بروتوكولات أكثر كفاءة للحوسبة السحابية، والبلوكشين، وتحليل البيانات الآمن، خاصة عندما تكون المدخلات كبيرة والدوال معقدة.

باختًا، توحد هذه الورقة عدة أهداف تشفيرية متباينة (الإيجاز، التكيفية، والشمولية) تحت إطار واحد قوي يعتمد على LWE القياسي، باستخدام تقنيات مبتكرة في الترميز الشبكي والضغط التكراري.