Вычислительная неотличимость

В вычислительной сложности и криптографии два семейства распределений неотличимы в вычислительном отношении, если ни один эффективный алгоритм не может определить разницу между ними, кроме как с незначительной вероятностью.

Формальное определение

Позволять $\scriptstyle \{D_{n}\}_{n\in \mathbb {N} }$ и $\scriptstyle \{E_{n}\}_{n\in \mathbb {N} }$ быть двумя ансамблями распределения , индексированными параметром безопасности n (который обычно относится к длине входных данных); мы говорим, что они вычислительно неотличимы, если для любого неоднородного вероятностного с полиномиальным временем алгоритма A следующая величина является пренебрежимо малой функцией от n :

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

обозначенный $D_{n}\approx E_{n}$. Другими словами, поведение каждого эффективного алгоритма A существенно не меняется при задании выборок в соответствии с n _или En в _D пределе как $n\to \infty$. Другая интерпретация вычислительной неотличимости заключается в том, что алгоритмы с полиномиальным временем, активно пытающиеся различить два ансамбля, не могут этого сделать: любой такой алгоритм будет работать лишь незначительно лучше, чем если бы кто-то просто догадывался.

Связанные понятия

Неявным в определении является условие, что алгоритм, $A$, должен принять решение на основе одной выборки из одного из распределений. Можно представить себе ситуацию, в которой алгоритм, пытающийся различать два распределения, может получить доступ к такому количеству выборок, сколько ему необходимо. Следовательно, два ансамбля, которые не могут быть различены с помощью алгоритмов с полиномиальным временем, рассматривающих несколько выборок, считаются неотличимыми с помощью выборки с полиномиальным временем . Если алгоритм с полиномиальным временем может генерировать выборки за полиномиальное время или имеет доступ к случайному оракулу , который генерирует для него выборки, то неотличимость с помощью выборки с полиномиальным временем эквивалентна вычислительной неотличимости.

Внешние ссылки

• Иегуда Линделл . Введение в криптографию
• Дональд Бивер, Сильвио Микали и Филип Рогауэй , Круглая сложность безопасных протоколов (расширенное резюме), 1990, стр. 503–513.
• Шафи Гольдвассер и Сильвио Микали . Вероятностное шифрование. JCSS, 28(2):270–299, 1984 г.
• Одед Гольдрейх . Основы криптографии: Том 2 – Основные приложения. Издательство Кембриджского университета, 2004.
• Джонатан Кац , Иегуда Линделл , «Введение в современную криптографию: принципы и протоколы», Chapman & Hall/CRC, 2007 г.

Эта статья включает в себя материал из вычислительно неотличимого материала PlanetMath , который доступен под лицензией Creative Commons Attribution/Share-Alike License .