WikiDer > Вычислительная неразличимость - Википедия

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

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

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

${ displaystyle delta (n) = left | Pr _ {x получает D_ {n}} [A (x) = 1] - Pr _ {x получает E_ {n}} [A (x) = 1] right |.}$

обозначенный ${ displaystyle D_ {n} приблизительно E_ {n}}$.^[1] Другими словами, каждый эффективный алгоритм А 's поведение существенно не меняется при выдаче образцов в соответствии с D_п или же E_п в пределе как ${ Displaystyle п к infty}$. Другая интерпретация вычислительной неразличимости состоит в том, что алгоритмы с полиномиальным временем, активно пытающиеся различить два ансамбля, не могут этого сделать: любой такой алгоритм будет работать лишь незначительно лучше, чем если бы можно было просто догадываться.

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

Неявным в определении является условие, что алгоритм, ${ displaystyle A}$, должен принять решение на основе единственной выборки из одного из распределений. Можно представить себе ситуацию, в которой алгоритм, пытающийся различать два распределения, может получить доступ к сколь угодно большому количеству образцов. Следовательно, два ансамбля, которые нельзя различить с помощью алгоритмов с полиномиальным временем, просматривающих несколько выборок, считаются неотличимы от выборки за полиномиальное время.^[2]:107 Если алгоритм с полиномиальным временем может генерировать выборки за полиномиальное время или имеет доступ к случайный оракул который генерирует для него выборки, то неотличимость с помощью выборки за полиномиальное время эквивалентна вычислительной неразличимости.^[2]:108

Рекомендации

внешняя ссылка

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

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