خصم محدود حسابيًا

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

للمقارنة، لنأخذ خوارزمية الفرز السريع ^كمثال . في أسوأ الأحوال، تُجري هذه الخوارزمية O( n² ) من المقارنات، إلا أن هذا نادر الحدوث. في أغلب الأحيان، تُجري خوارزمية الفرز السريع O( n log n ) من المقارنات، بل وتتفوق على الخوارزميات الأخرى التي تضمن أداءً مماثلاً. لنفترض أن مهاجمًا يرغب في إجبار خوارزمية الفرز السريع على إجراء O( n² ) ^من المقارنات. عندها سيتعين عليه البحث في جميع التباديل الممكنة (n !) لسلسلة الإدخال، واختبار الخوارزمية على كل تبديل حتى يجد التبديل الذي يُبطئ الخوارزمية بشكل ملحوظ. ولكن بما أن هذا سيستغرق O( n ! ) من الوقت، فمن الواضح أنه من غير العملي للمهاجم القيام بذلك. وبالمثل، من غير المعقول افتراض أن مهاجمًا لنظام التشفير وفك التشفير سيكون قادرًا على اختبار كل نمط خطأ على حدة للعثور على النمط الأكثر فعالية.    

يمكن وصف نموذج الضوضاء العشوائي بأنه نموذج ضوضاء "بسيط". بمعنى آخر، يفتقر إلى القدرة على التكيف مع التهديدات "الذكية". حتى لو كان المهاجم محدود القدرات، فمن الممكن أن يتمكن من التغلب على النموذج العشوائي ببعض الحيل. لا يملك النموذج العشوائي وسيلة فعالة لمواجهة هذا النوع من الهجمات، وبالتالي فهو غير مناسب للتعامل مع التهديدات "الذكية" التي يُفضل وجود دفاعات ضدها.

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

بما أن أي خصم محدود حسابيًا يستطيع في زمن قدره O( n ) قلب قطعة نقدية لكل بت، فمن البديهي أن أي نظام تشفير وفك تشفير قادر على مواجهة هذا الخصم يجب أن يعمل أيضًا في نموذج الضوضاء العشوائية. أما العكس فليس بهذه البساطة؛ ومع ذلك، يمكن إثبات أن أي نظام يعمل في نموذج الضوضاء العشوائية يمكنه أيضًا التشفير وفك التشفير بكفاءة ضد خصم محدود حسابيًا، وذلك بتكلفة إضافية متعددة الحدود في n فقط . ^{[ 1 ]} وقد صمم ديك ليبتون الطريقة التالية لتحقيق ذلك، وهي مأخوذة من: ^{[ 1 ]}

يترك${\displaystyle E()}$كن مشفرًا لنموذج الضوضاء العشوائية و${\displaystyle D()}$ليكن لدينا مُفكِّك بسيط لنفس البيانات، يعمل كلٌّ منهما في وقت متعدد الحدود. علاوة على ذلك، ليكن كلٌّ من المُرسِل والمُستقبِل يشتركان في دالة تبديل عشوائية.${\displaystyle \pi }$ونمط عشوائي${\displaystyle R}$.

للترميز: 1. ليكن${\displaystyle X=E(M)}$.

2. ليكن${\displaystyle Y=\pi (X)\oplus R}$.

3. الإرسال${\displaystyle Y}$

ثم لفك التشفير: 1. الاستقبال${\displaystyle Y'}$حساب${\displaystyle Z=\pi ^{-1}(Y'\oplus R)}$.

2. احسب${\displaystyle M=D(Z)}$.

على غرار مقارنة الفرز السريع المذكورة أعلاه، إذا أرادت القناة القيام بشيء ذكي، فيجب عليها أولاً اختبار جميع التباديل. ومع ذلك، فإن هذا غير عملي بالنسبة لخصم محدود القدرات الحسابية، لذا فإن أقصى ما يمكنها فعله هو إنشاء نمط خطأ عشوائي.${\displaystyle N}$ولكن بعد ذلك:

${\displaystyle Z=\pi ^{-1}(Y'\oplus R)=\pi ^{-1}(Y\oplus N\oplus R),}$

منذ${\displaystyle Y'=Y\oplus N}$بحسب التعريف.

${\displaystyle =\pi ^{-1}(Y\oplus R)\oplus N'}$، أين${\displaystyle N'=\pi ^{-1}(N),}$

بما أن أي تبديل يكون خطيًا بالنسبة لعملية XOR،

${\displaystyle =X\oplus N',}$

وفقًا لتعريف${\displaystyle Y}$فوق.

منذ${\displaystyle \pi }$عشوائي،${\displaystyle N'}$إنها مجرد ضوضاء عشوائية، ويمكننا استخدام جهاز فك التشفير البسيط لفك تشفير الرسالة المستلمة والعودة إليها.${\displaystyle M}$.