عدم القدرة على التمييز الحسابي

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

يترك${\displaystyle \scriptstyle \{D_{n}\}_{n\in \mathbb {N} }}$و${\displaystyle \scriptstyle \{E_{n}\}_{n\in \mathbb {N} }}$لنفترض أن لدينا مجموعتين من التوزيعات مفهرسة بمعامل أمان n (والذي يشير عادةً إلى طول المدخلات)؛ نقول إنهما غير قابلتين للتمييز حسابيًا إذا كانت الكمية التالية دالة مهملة في n لأي خوارزمية احتمالية غير منتظمة ذات وقت متعدد الحدود A :

${\displaystyle \delta (n)=\left|\Pr _{x\gets D_{n}}[A(x)=1]-\Pr _{x\gets E_{n}}[A(x)=1]\right|.}$

يُشار إليه${\displaystyle D_{n}\approx E_{n}}$^{[ 1 ]} بعبارة أخرى، لا يتغير سلوك أي خوارزمية فعالة A بشكل ملحوظ عند إعطائها عينات وفقًا لـ D n _أو E n _في النهاية كما${\displaystyle n\to \infty }$. تفسير آخر لعدم القدرة على التمييز الحسابي هو أن الخوارزميات ذات الوقت متعدد الحدود التي تحاول بنشاط التمييز بين المجموعتين لا تستطيع القيام بذلك: أي أن أي خوارزمية من هذا القبيل لن تؤدي إلا أداءً أفضل بشكل ضئيل مما لو كان المرء يخمن فقط.

يتضمن التعريف ضمناً شرط أن الخوارزمية،${\displaystyle A}$يجب أن يُقرر بناءً على عينة واحدة من أحد التوزيعات. يمكن تصور حالة يستطيع فيها الخوارزمية التي تحاول التمييز بين توزيعين الوصول إلى أي عدد من العينات التي تحتاجها. وبالتالي، تُعتبر مجموعتان لا يمكن التمييز بينهما بواسطة خوارزميات ذات زمن متعدد الحدود عند النظر إلى عينات متعددة غير قابلتين للتمييز بواسطة أخذ العينات في زمن متعدد الحدود . ^{[ 2 ] : 107} إذا كانت الخوارزمية ذات الزمن متعدد الحدود قادرة على توليد عينات في زمن متعدد الحدود، أو لديها إمكانية الوصول إلى مصدر عشوائي لتوليد العينات لها، فإن عدم إمكانية التمييز بواسطة أخذ العينات في زمن متعدد الحدود يُكافئ عدم إمكانية التمييز الحسابي. ^{[ 2 ] : 108}

• يهودا ليندل . مقدمة في علم التشفير
• دونالد بيفر وسيلفيو ميكالي وفيليب روغاواي ، تعقيد الجولات في البروتوكولات الآمنة (ملخص موسع)، 1990، الصفحات  503-513
• شافي غولدواسير وسيلفيو ميكالي . التشفير الاحتمالي. مجلة علوم الحاسوب والأنظمة، 28(2):270–299، 1984
• Oded Goldreich. Foundations of Cryptography: Volume 2 – Basic Applications. Cambridge University Press, 2004.
• Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007

This article incorporates material from computationally indistinguishable on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.