التمويه الذي لا يمكن تمييزه

في علم التشفير ، يُعدّ التمويه غير القابل للتمييز (يُختصر بـ IO أو iO ) نوعًا من أنواع تمويه البرمجيات ، ويتميز بخاصية أساسية هي أن تمويه أي برنامجين يُحسبان نفس الدالة الرياضية ينتج عنه برنامجان لا يمكن التمييز بينهما. بعبارة أخرى، يُخفي هذا النوع من التمويه آلية تنفيذ البرنامج مع السماح للمستخدمين بتشغيله. ^{[ 1 ]} أما من الناحية الرسمية، فيُحقق iO خاصية أن تمويه دائرتين من نفس الحجم تُنفذان نفس الدالة يكون غير قابل للتمييز حسابيًا . ^{[ 2 ]}

يتمتع التمويه غير القابل للتمييز بعدة خصائص نظرية مثيرة للاهتمام. أولًا، يُعدّ التمويه غير القابل للتمييز "أفضل تمويه ممكن" (بمعنى أن أي سرّ يتعلق ببرنامج ما، يمكن إخفاؤه بأي مُموّه، يمكن إخفاؤه أيضًا بواسطة التمويه غير القابل للتمييز). ثانيًا، يمكن استخدام التمويه غير القابل للتمييز لبناء جميع أنواع الخوارزميات التشفيرية تقريبًا ، بما في ذلك الخوارزميات الشائعة مثل التشفير بالمفتاح العام، والخوارزميات الأكثر تعقيدًا مثل التشفير القابل للإنكار والتشفير الوظيفي (وهي أنواع من التشفير لم يكن أحد يعرف كيفية بنائها سابقًا ^{[ 3 ]} )، باستثناء عائلات دوال التجزئة المقاومة للتصادم . لهذا السبب، يُشار إليه باسم "التشفير الكامل". أخيرًا، على عكس العديد من أنواع التشفير الأخرى، يستمر التمويه غير القابل للتمييز في الوجود حتى لو كان P=NP (على الرغم من أنه سيتعين بناؤه بشكل مختلف في هذه الحالة)، مع أن هذا لا يعني بالضرورة أن التمويه غير القابل للتمييز موجود بشكل مطلق.

على الرغم من أن فكرة التمويه البرمجي التشفيري موجودة منذ عام 1996، إلا أن تم اقتراح تمويه عدم التمييز لأول مرة من قبل باراك وآخرون (2001)، الذين أثبتوا وجوده في حالة P=NP. أما في حالة P≠NP (وهي أصعب، ولكنها أيضًا أكثر ترجيحًا ^{[ 2 ]} )، فقد كان التقدم أبطأ: إذ اقترح غارغ وآخرون (2013) ^{[ 4 ]} بناءً لتمويه عدم التمييز قائمًا على افتراض صعوبة حسابية يتعلق بالخرائط متعددة الخطية ، ولكن تم دحض هذا الافتراض لاحقًا. أما البناء القائم على "افتراضات راسخة" (افتراضات الصعوبة التي درسها علماء التشفير جيدًا، وبالتالي يُفترض على نطاق واسع أنها آمنة) فقد انتظر حتى جاين ولين وساهي (2020). (ومع ذلك، فإن أحد هذه الافتراضات المستخدمة في اقتراح 2020 ليس آمنًا ضد الحواسيب الكمومية ).

إن تقنيات التمويه المعروفة حاليًا والتي لا تسمح بالتمييز بين الإشارات بعيدة كل البعد عن التطبيق العملي. وذلك وفقًا لدراسة نُشرت عام 2017.حتى إخفاء وظيفة اللعبة التي تُخرج الربط المنطقي لمدخلاتها من نوع البيانات المنطقية البالغ عددها 32 ينتج برنامجًا بحجم يقارب 12 جيجابايت .

يترك${\displaystyle {\mathcal {iO}}}$ليكن خوارزمية احتمالية موحدة ذات زمن متعدد الحدود . إذن${\displaystyle {\mathcal {iO}}}$يُطلق عليه اسم مُشوش عدم التمييز إذا وفقط إذا استوفى كلا العبارتين التاليتين: ^{[ 5 ] [ 6 ] [ 7 ]}

• الاكتمال أو الوظائف : لأي دائرة منطقية C ذات طول إدخال n وإدخال${\displaystyle x\in \{0,1\}^{n}}$لدينا$${\displaystyle \Pr[C'(x)=C(x):C'\leftarrow {\mathcal {iO}}(C)]=1.}$$
• عدم التمييز : لكل زوج من الدوائر${\displaystyle C_{0},C_{1}}$التوزيعات ذات الحجم نفسه k والتي تُنفذ نفس الوظائف${\displaystyle \{{\mathcal {iO}}(C_{0})\}}$و${\displaystyle \{{\mathcal {iO}}(C_{1})\}}$لا يمكن التمييز بينهما حسابيًا. بعبارة أخرى، بالنسبة لأي خصم احتمالي متعدد الحدود A ، توجد دالة مهملة${\displaystyle \varepsilon (k)}$( أي ، دالة تنمو في النهاية بشكل أبطأ من${\displaystyle 1/p(k)}$لأي متعددة حدود p بحيث، لكل زوج من الدوائر${\displaystyle C_{0},C_{1}}$لدينا وحدات من نفس الحجم k تُنفذ نفس الوظائف.$${\displaystyle |\Pr[A({\mathcal {iO}}(C_{0}))=1]-\Pr[A({\mathcal {iO}}(C_{1}))=1]|\leq \varepsilon (k).}$$

في عام ٢٠٠١، اقترح باراك وآخرون، مُبينين استحالة التمويه الصندوقي الأسود ، فكرة مُموِّه عدم التمييز، وقاموا ببناء نموذج غير فعال منه. ^{[ ٨ ] [ ٧ ] [ ٢ ]} على الرغم من أن هذه الفكرة بدت ضعيفة نسبيًا، فقد أظهر غولدواسير وروثبلوم (٢٠٠٧) أن مُموِّه عدم التمييز الفعال سيكون أفضل مُموِّه ممكن، وأن أي مُموِّه أفضل ممكن سيكون مُموِّه عدم تمييز. ^{[ ٨ ] [ ٩ ]} (مع ذلك، بالنسبة للمُموِّهات غير الفعالة ، لا يوجد مُموِّه أفضل ممكن إلا إذا انهار التسلسل الهرمي متعدد الحدود إلى المستوى الثاني. ^{[ ٩ ]} )

تم إنشاء تطبيق برمجي مفتوح المصدر لمرشح iO في عام 2015. ^{[ 10 ]}

من المفيد تقسيم مسألة وجود iO باستخدام "العوالم الخمسة" لراسل إمباغليازو ، ^{[ 13 ]} وهي خمس حالات افتراضية مختلفة حول تعقيد الحالة المتوسطة : ^{[ 6 ]}

• Algorithmica : في هذه الحالة P = NP ، ولكن iO موجود.
• Heuristica : في هذه الحالة، تكون مشاكل NP سهلة في المتوسط؛ iO غير موجود.
• Pessiland : في هذه الحالة، BPP ≠ NP، لكن الدوال أحادية الاتجاه غير موجودة؛ ونتيجة لذلك، فإن iO غير موجود.
• Minicrypt : في هذه الحالة، توجد وظائف أحادية الاتجاه ، ولكن التشفير الآمن بالمفتاح العام غير موجود؛ iO غير موجود (لأن الإنشاءات الصريحة للتشفير بالمفتاح العام من iO والوظائف أحادية الاتجاه معروفة).
• هوس التشفير : في هذه الحالة، يوجد تشفير المفتاح العام الآمن ، لكن iO غير موجود.
• Obfustopia : ^{[ 14 ] [ 15 ]} في هذه الحالة، يُعتقد أن iO موجود.

يمكن استخدام مُخفيات عدم التمييز، إن وُجدت، في نطاق واسع من التطبيقات التشفيرية ، لدرجة أنها تُوصف بأنها "محور مركزي" للتشفير، ^{[ 1 ] [ 3 ]} و"جوهرة تاج التشفير"، ^{[ 3 ]} أو "كاملة تشفيرياً". ^{[ 2 ]} وبالتحديد، يمكن استخدام مُخفي عدم التمييز (مع افتراض إضافي بوجود دوال أحادية الاتجاه ^{[ 2 ]} ) لبناء الأنواع التالية من التشفير:

• إخفاء عدم التمييز للبرامج في نموذج ذاكرة الوصول العشوائي ^{[ 5 ]} ولآلات تورينج ^{[ 16 ] [ 17 ]}
• التشفير الآمن بالمفتاح العام IND-CCA ^{[ 18 ]}
• التوقيعات الرقمية القصيرة ^{[ 18 ]}
• مخططات تغليف المفاتيح الآمنة IND-CCA ^{[ 18 ]}
• البراهين غير التفاعلية ذات المعرفة الصفرية تمامًا والحجج غير التفاعلية الموجزة ^{[ 18 ]}
• بروتوكولات المعرفة الصفرية المتزامنة ذات عدد الجولات الثابت ^{[ 5 ]}
• الخرائط متعددة الخطية ذات الدرجات متعددة الحدود المحدودة ^{[ 5 ]}
• دوال المصيدة الحقنية ^{[ 18 ]}
• التشفير المتماثل بالكامل ^{[ 5 ]}
• تشفير الشهود ^{[ 5 ] [ 2 ]}
• التشفير الوظيفي ^{[ 2 ]}
• مشاركة الأسرار لأي لغة NP رتيبة ^{[ 5 ]}
• التحويل شبه الصادق غير الواعي ^{[ 18 ]}
• التشفير القابل للإنكار (سواء كان قابلاً للإنكار من قبل المرسل أو قابلاً للإنكار بالكامل) ^{[ 18 ] [ 5 ] [ 2 ]}
• تبادل المفاتيح متعدد الأطراف وغير التفاعلي ^{[ 5 ]}
• ذاكرة الوصول العشوائي المشوشة الموجزة الآمنة تكيفيًا ^{[ 5 ]}
• الدوال غير القابلة للحل ^{[ 5 ]}
• التشفير القائم على الهوية ^{[ 5 ]}
• التشفير القائم على السمات ^{[ 5 ]}
• النقل غير الواعي ^{[ 2 ]}
• تتبع الخونة ^{[ 2 ]}
• مخططات التشفير المتدرجة ^{[ 2 ]}

بالإضافة إلى ذلك، إذا وُجدت دوال الإدخال/الإخراج والدوال أحادية الاتجاه، فإن المسائل في فئة تعقيد PPAD تُعتبر صعبة بشكل مؤكد. ^{[ 5 ] [ 19 ]}

ومع ذلك، لا يمكن استخدام التمويه غير القابل للتمييز لبناء كل بروتوكول تشفير ممكن: على سبيل المثال، لا يمكن لأي بنية صندوق أسود تحويل مُموِّه غير قابل للتمييز إلى عائلة دوال تجزئة مقاومة للتصادم ، حتى مع تبديل الباب الخلفي ، إلا مع خسارة أسية في الأمان. ^{[ 20 ]}

• التمويه بالصندوق الأسود ، وهو شكل أقوى من التمويه ثبت استحالته
• مبدأ كيركوفس – مبدأ تشفير ينص على أن كل شيء باستثناء المفتاح يمكن أن يكون معلومة عامة