عدم القدرة على تمييز النص المشفر

بالنسبة لخوارزمية تشفير المفتاح غير المتماثل الاحتمالية ، يُعرَّف عدم التمييز في ظل هجوم النص الصريح المُختار (IND-CPA) باللعبة التالية بين مُهاجم ومُتحدٍّ. بالنسبة للأنظمة القائمة على الأمن الحسابي ، يُنمذج المُهاجم بواسطة آلة تورينغ احتمالية ذات زمن متعدد الحدود ، مما يعني أنه يجب عليه إكمال اللعبة وإخراج تخمين خلال عدد متعدد الحدود من الخطوات الزمنية. في هذا التعريف، يُمثل E ( PK , M ) تشفير الرسالة M باستخدام المفتاح PK .

1. يقوم المُتحدّي بإنشاء زوج من المفاتيح PK و SK بناءً على مُعامل أمان k (مثل حجم المفتاح بالبتات)، وينشر PK للخصم. ويحتفظ المُتحدّي بـ SK .
2. قد يقوم الخصم بتنفيذ عدد محدود من عمليات التشفير أو العمليات الأخرى.
3. في النهاية، يقدم الخصم نصين عاديين مميزين تم اختيارهما M ₀ و M ₁ إلى المتحدي.
4. يختار المتحدي بتًا b ∈ {0, 1} بشكل عشوائي منتظم، ويرسل النص المشفر للتحدي C = E ( PK , M _b ) إلى الخصم.
5. يحق للخصم إجراء أي عدد من العمليات الحسابية أو التشفيرات الإضافية.
6. وأخيراً، يقوم الخصم بإخراج تخمين لقيمة b .

يكون نظام التشفير غير قابل للتمييز في مواجهة هجوم النص الصريح المُختار إذا كان لكل خصم احتمالي ذي وقت متعدد الحدود ميزة ضئيلة للغاية على التخمين العشوائي. ويُقال إن للخصم ميزة ضئيلة للغاية إذا فاز في اللعبة المذكورة أعلاه باحتمالية${\displaystyle \left({\tfrac {1}{2}}\right)\,+\,\epsilon (k)}$، أين${\displaystyle \epsilon (k)}$تُعد وظيفة ضئيلة في معلمات الأمان${\displaystyle k}$أي، لكل دالة متعددة الحدود (غير صفرية) poly() يوجد${\displaystyle k_{0}}$بحيث${\displaystyle |\epsilon (k)|\;<\;\left|{\tfrac {1}{\mathrm {poly(k)} }}\right|}$للجميع${\displaystyle k\;>\;k_{0}}$.

على الرغم من أن الخصم يعرف M ₀ و M ₁ و PK ، فإن الطبيعة الاحتمالية لـ E تعني أن تشفير M _b سيكون واحداً فقط من بين العديد من النصوص المشفرة الصالحة، وبالتالي فإن تشفير M ₀ و M ₁ ومقارنة النصوص المشفرة الناتجة مع النص المشفر للتحدي لا يوفر أي ميزة غير ضئيلة للخصم.

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

لعبة متناظرة بين المحاسبين المستقلين والمحاسبين القانونيين المعتمدين، بصيغة رسمية

تُصوَّر عملية الهجوم باستخدام نص صريح مُختار عادةً على شكل لعبة تشفير . ولاختبار هجوم IND-CPA المتناظر، تُعرَّف اللعبة الموصوفة أعلاه. ^{[ 1 ]} ليكن${\displaystyle {\mathcal {K}}}$أن تكون وظيفة توليد رئيسية،${\displaystyle {\mathcal {E}}}$أن تكون دالة تشفير، و${\displaystyle {\mathcal {D}}}$لتكن دالة فك التشفير.${\displaystyle {\mathcal {S}}{\mathcal {E}}=({\mathcal {K}},{\mathcal {E}},{\mathcal {D}})}$ليكن نظام تشفير متناظر. تُعرَّف لعبة "التخمين" على النحو التالي:

تخمين اللعبة${\displaystyle _{{\mathcal {S}}{\mathcal {E}}}}$

تهيئة الإجراء ${\displaystyle K{\overset {\$}{\leftarrow }}{\mathcal {K}};b{\overset {\$}{\leftarrow }}\left\{0,1\right\}}$إجراء LR${\displaystyle \left(M_{0},M_{1}\right)}$ يعود${\displaystyle C{\overset {\$}{\leftarrow }}{\mathcal {E}}_{K}\left(M_{b}\right)}$إنهاء الإجراء${\displaystyle \left(b'\right)}$ يعود${\displaystyle \left(b==b'\right)}$

يختار الخصم، متى شاء، رسالتين نصيتين عاديتين من اختياره، ويُدخلهما إلى وسيط LR الذي يُعيد نصًا مشفرًا يُشفّر إحدى الرسالتين. وتُحدد ميزة الخصم باحتمالية تخمينه لقيمة b، وهي قيمة تُختار عشوائيًا في بداية اللعبة، وتُحدد الرسالة التي تُشفّر في وسيط LR . لذا، تُعرّف ميزته على النحو التالي: ^{[ 1 ]}$${\displaystyle \operatorname {Adv} _{\mathcal {SE}}^{\mathrm {ind-cpa} }(A)=2\cdot \Pr \left[\mathrm {Guess} _{\mathcal {SE}}^{A}\Rightarrow \mathrm {true} \right]-1}$$

يستخدم تعريف عدم التمييز في ظل هجوم النص المشفر المختار غير التكيفي والتكيفي (IND-CCA1، IND-CCA2) تعريفًا مشابهًا لتعريف IND-CPA. مع ذلك، بالإضافة إلى المفتاح العام (أو وسيط التشفير، في الحالة المتناظرة)، يُمنح المهاجم إمكانية الوصول إلى وسيط فك التشفير الذي يفك تشفير أي نص مشفر بناءً على طلبه، ويعيد النص الأصلي. في التعريف غير التكيفي، يُسمح للمهاجم بالاستعلام من هذا الوسيط فقط حتى يتلقى نص التحدي المشفر. أما في التعريف التكيفي، فيمكن للمهاجم الاستمرار في الاستعلام من وسيط فك التشفير حتى بعد تلقيه نص التحدي المشفر، مع التنبيه إلى أنه لا يجوز له تمرير نص التحدي المشفر لفك التشفير (وإلا لكان التعريف بديهيًا).

1. يقوم المُتحدّي بإنشاء زوج من المفاتيح PK و SK بناءً على مُعامل أمان k (مثل حجم المفتاح بالبتات)، وينشر PK للخصم. ويحتفظ المُتحدّي بـ SK .
2. قد يقوم الخصم بتنفيذ أي عدد من المكالمات إلى وسيط التشفير وفك التشفير بناءً على نصوص مشفرة عشوائية، أو عمليات أخرى.
3. في النهاية، يقدم الخصم نصين عاديين مميزين تم اختيارهما M ₀ و M ₁ إلى المتحدي.
4. يختار المتحدي بتًا b ∈ {0, 1} بشكل عشوائي منتظم، ويرسل النص المشفر "التحدي" C = E ( PK , M _b ) إلى الخصم.
5. يحق للخصم إجراء أي عدد من العمليات الحسابية أو التشفيرات الإضافية.
   1. في الحالة غير التكيفية (IND-CCA1)، قد لا يقوم الخصم بإجراء المزيد من المكالمات إلى وسيط فك التشفير.
   2. في الحالة التكيفية (IND-CCA2)، قد يقوم الخصم بإجراء المزيد من المكالمات إلى وسيط فك التشفير، ولكنه قد لا يقدم النص المشفر للتحدي C.
6. وأخيراً، يقوم الخصم بإخراج تخمين لقيمة b .

تعتبر الخطة آمنة وفقًا لمعيار IND-CCA1/IND-CCA2 إذا لم يكن لدى أي خصم ميزة غير ضئيلة في الفوز باللعبة المذكورة أعلاه.

أحيانًا نحتاج إلى أنظمة تشفير يكون فيها النص المشفر غير قابل للتمييز عن سلسلة عشوائية بالنسبة للخصم. ^{[ 2 ]}

إذا لم يتمكن الخصم من معرفة ما إذا كانت الرسالة موجودة أصلاً، فإن ذلك يمنح الشخص الذي كتب الرسالة إمكانية الإنكار المعقول .

يفضل بعض الأشخاص الذين يقومون بإنشاء روابط اتصال مشفرة جعل محتويات كل حزمة بيانات مشفرة غير قابلة للتمييز عن البيانات العشوائية، وذلك لجعل تحليل حركة البيانات أكثر صعوبة. ^{[ 3 ]}

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

لدعم أنظمة التشفير القابلة للإنكار هذه ، تم تصميم بعض الخوارزميات التشفيرية خصيصًا لجعل رسائل النص المشفر غير قابلة للتمييز عن سلاسل البتات العشوائية. ^{[ 4 ] [ 5 ] [ 6 ]}

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