WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

Доказа́тельство с нулевы́м разглаше́нием (информа́ции) в криптографии (англ. Zero-knowledge proof) — интерактивный криптографический протокол, позволяющий одной из взаимодействующих сторон («The verifier» — проверяющей) убедиться в достоверности какого-либо утверждения (обычно математического), не имея при этом никакой другой информации от второй стороны («The prover» — доказывающей). Причём последнее условие является необходимым, так как обычно доказать, что сторона обладает определёнными сведениями в большинстве случаев тривиально, если она имеет право просто раскрыть информацию. Вся сложность состоит в том, чтобы доказать, что у одной из сторон есть информация, не раскрывая её содержание. Протокол должен учитывать, что доказывающий сможет убедить проверяющего только в случае, если утверждение действительно доказано. В противном случае сделать это будет невозможно, или крайне маловероятно из-за вычислительной сложности.

Под интерактивностью протокола подразумевается непосредственный обмен информацией сторонами^[1]^[2].

Таким образом, рассматриваемый протокол требует наличия интерактивных исходных данных (interactive input) от проверяющего, как правило, в виде задачи или проблемы. Цель легального доказывающего (имеющего доказательство) в этом протоколе — убедить проверяющего в том, что у него есть решение, не выдав при этом даже части «секретного» доказательства («нулевое разглашение»). Цель проверяющего же — это удостовериться в том, что доказывающая сторона «не лжёт»^[2]^[3].

Также были разработаны протоколы доказательства с нулевым разглашением^[4]^[5], для которых не требовалось наличия интерактивных исходных данных, при этом доказательство которых, как правило, опирается на предположение об идеальной криптографической хеш-функции, то есть предполагается, что выход однонаправленной хеш-функции невозможно предсказать, если не известен её вход^[6].

Определение

Доказательство с нулевым разглашением — интерактивный вероятностный протокол, который позволяет доказать, что доказываемое утверждение верно, и Доказывающий знает это доказательство, в то же время не предоставляя никакой информации о самом доказательстве данного утверждения^[7]. Данный криптографический протокол должен обладать тремя свойствами:

Полнота: если утверждение действительно верно, то Доказывающий убедит в этом Проверяющего с любой наперед заданной точностью.
Корректность: если утверждение неверно, то любой, даже «нечестный», Доказывающий не сможет убедить Проверяющего за исключением пренебрежимо малой вероятности.
Нулевое разглашение: если утверждение верно, то любой, даже «нечестный», Проверяющий не узнает ничего кроме самого факта, что утверждение верно^[8].

Доказательства с нулевым разглашением не являются доказательствами в математическом смысле этого термина, потому что есть некоторая небольшая вероятность, что обманом доказывающая сторона сможет убедить Проверяющего в ложном утверждении (ошибка корректности). Иными словами, доказательства с нулевым разглашением — это вероятностные доказательства, а не детерминированные. Тем не менее, есть методы, позволяющие уменьшить ошибку корректности до пренебрежимо малых значений^[9]^[10].

Различные виды нулевого разглашения

Выполнение протокола доказательства с нулевым разглашением приводит к выводу результата Принять/Отклонить и также порождает стенограмму доказательства. Различные варианты нулевого разглашения могут быть определены путём формализации самого понятия и сравнения распространения информации различных моделей с протоколом следующими способами^[11]^[12]:

Идеальный протокол нулевого разглашения — если случайные величины в стенограмме доказательства рассматриваемой модели являются равномерно распределенными и не зависят от общих входных данных^[13]. Хорошей иллюстрацией будет пример Алисы и Боба в пещере.
Статистически нулевое разглашение^[14] означает, что распределение не обязательно такое же, но они по крайней мере статистически близки^[en], при этом статистическая разница есть незначительная функция^[en]^[15].
С вычислительно нулевым разглашением называют такую модель, если не существует на данный момент такого эффективного алгоритма, который смог бы отличить распределение величин от распространения информации в идеальном протоколе^[16].

История развития

В 1986 году в работе Сильвио Микали, Одеда Голдрейха^[en] и Ави Вигдерсона было описано применение доказательств с нулевым разглашением для создания криптографических протоколов, которые должны обеспечивать «честное поведение» сторон, сохраняя при этом конфиденциальность^[17].

Доказательство с нулевым разглашением было придумано и разработано следующими учёными: Шафи Гольдвассер, Сильвио Микали и Чарльзом Реккофом, и опубликовано ими в статье «Знание и сложность интерактивной системы с доказательством»^[18] в 1989 году. Эта работа представила иерархию интерактивных систем с доказательством, основываясь на объёме информации о доказательстве, который необходимо передать от Доказывающего до Проверяющего. Ими так же было предложено первое доказательство конкретно поставленного доказательства с нулевым разглашением — квадратичного вычета по некоторому модулю m^[19]. Впоследствии, дополнив свою работу, они были удостоены первой премии Гёделя в 1993 году^[20].

В дальнейшем криптосистема Гольдвассер — Микали, основанная на рассматриваемом интерактивном протоколе, являющаяся криптографической системой с открытым ключом, разработанная Шафи Гольдвассер и Сильвио Микали в 1982 году, является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических предположениях. Предложенная система была высоко оценена жюри: Гольдовассер и Микали стали лауреатами Премии Тьюринга за 2012 год^[21], за создание криптосистемы с вероятностным шифрованием, отмеченная в номинации как новаторская работа, оказавшая существенное влияние на современную криптографию. Однако, криптосистема является неэффективной, так как порождаемый ею шифротекст может быть в сотни раз длиннее, чем шифруемое сообщение.

Для доказательства свойств стойкости криптосистемы Голдвассер и Микали ввели понятие семантической стойкости^[22]^[23].

Общая структура доказательств с нулевым разглашением

Каждый раунд, или аккредитация доказательства, состоит из трёх этапов. Схематично их можно изобразить следующим образом:

$A\Rightarrow B$ : доказательство (witness)
$A\Leftarrow B$ : вызов (challenge)
$A\Rightarrow B$ : ответ (response)

Сначала A выбирает из заранее определённого непустого множества некоторый элемент, который становится её секретом — закрытым ключом. По этому элементу вычисляется, а затем публикуется открытый ключ. Знание секрета определяет множество вопросов, на которые А всегда сможет дать правильные ответы. Затем A выбирает случайный элемент из множества, по определённым правилам (в зависимости от конкретного алгоритма) вычисляет доказательство и затем отсылает его B. После этого B выбирает из всего множества вопросов один и просит A ответить на него (вызов). В зависимости от вопроса, А посылает B ответ^[24]. Полученной информации B достаточно, чтобы проверить действительно ли А владеет секретом. Раунды можно повторять сколько угодно раз, пока вероятность того, что A «угадывает» ответы, не станет достаточно низкой. Такой подход называется также «разрезать и выбрать» («cut-and-choose»), впервые использованный в криптографии Михаэлем Рабином^[25]^[26].

Примеры

Пещера нулевого разглашения

Впервые данный пример был написан в хорошо известной работе по доказательству с нулевым разглашением «Как объяснить протокол доказательства с нулевым разглашением вашим детям» Жан-Жаком Кискатером (англ.)русск.^[27].

В данном случае Пегги выступает в качестве Доказывающего утверждение, и Виктор — в качестве Проверяющего (в англоязычной литературе обычно используются наименование сторон Peggy от «Prover» и Victor от «Verifier»). Пегги знает магическое слово («ключ»), ввод которого позволяет открыть ей дверь между C и D. Виктор хочет узнать, действительно ли Пегги знает пароль, при этом Пегги не хочет выдавать сам пароль. Пещера имеет круглую форму, как представлено на рисунке. Для того чтобы решить проблему, они поступают следующим способом. Пока Виктор находится в точке А, Пегги идёт к двери, и после того, как она исчезает из виду, Виктор идёт к разветвлению, то есть в точку B, и кричит оттуда: «Пегги нужно выйти справа» или «Пегги нужно выйти слева». Получаем каждый раз вероятность того, что Пегги не знает пароль, равна 50 %. Если же повторить процесс k раз, то вероятность будет ${\frac {1}{2^{k}}}$ . При 20 же повторениях эта вероятность будет порядка 10⁻⁶, что является достаточным для справедливости предположения о том, что Пегги знает ключ^[27].

Если Виктор запишет все происходящее на камеру, то полученная видеозапись не будет являться доказательством для какой-либо другой стороны. Ведь они могли заранее сговориться, откуда будет выходить Пегги. Соответственно, она сможет найти выход, не зная при этом самого ключа. Существует ещё один способ: Виктор просто вырезает все неудачные попытки Пегги. Эти описанные выше действия доказывают, что пример с пещерой удовлетворяет свойствам: полноты, корректности и нулевому разглашению^[28].

Гамильтонов цикл для больших графов

Этот пример был придуман Мануэлем Блюмом и описан в его работе в 1986 году^[29]. Назовём проверяющую сторону Виктор, а доказывающую сторону Пегги. Допустим, Пегги известен гамильтонов цикл в большом графе G. Виктору известен граф G, но он не знает гамильтонова цикла в нём. Пегги хочет доказать Виктору, что она знает гамильтонов цикл, не выдавая при этом ни самого цикла, ни какой-либо информации о нём (возможно Виктор хочет купить информацию об этом гамильтоновом цикле у Пегги, но перед этим желает удостовериться, что Пегги действительно знает его).

Для этого Виктор и Пегги совместно выполняют несколько раундов протокола:

Вначале Пегги создаёт граф H, изоморфный G. Преобразование гамильтонова цикла между изоморфными графами — тривиальная задача, поэтому если Пегги известен гамильтонов цикл в G, то она также знает гамильтонов цикл в порождаемом графе H.
Пегги передаёт граф H Виктору.
Виктор выбирает случайный бит b $\in$ $\in$ {0, 1}.
- Если b = 0, то Виктор просит Пегги доказать изоморфизм G и H, то есть предоставить взаимнооднозначное соответствие вершин этих двух графов. Виктор может проверить, действительно ли G и H изоморфны.
- Если b = 1, то Виктор просит Пегги указать гамильтонов цикл в H. Для задачи изоморфизма графов на данный момент не доказана ни её принадлежность классу $P$ , ни её $NP$ -полнота, поэтому будем здесь считать, что невозможно из гамильтонова цикла в H вычислить гамильтонов цикл в изоморфном G^[29].

В каждом раунде Виктор выбирает новый случайный бит, который неизвестен Пегги, поэтому, чтобы Пегги могла ответить на оба вопроса, нужно чтобы H был в самом деле изоморфен G, и Пегги должна знать гамильтонов цикл в H (а значит также и в G). Поэтому после достаточного числа раундов, Виктор может быть уверен в том, что у Пегги действительно есть знание о гамильтоновом цикле в G. С другой стороны, Пегги не раскрывает никакой информации о гамильтоновом цикле в G. Более того, Виктору сложно будет доказать кому-либо ещё, что он сам или Пегги знают гамильтонов цикл в G^[29].

Предположим, что Пегги неизвестен гамильтонов цикл в G, но она хочет обмануть Виктора. Тогда Пегги необходим неизоморфный G граф G′, в котором она всё-таки знает гамильтонов цикл. В каждом раунде она может передавать Виктору либо H′ — изоморфный G′, либо H — изоморфный G. Если Виктор попросит доказать изоморфизм графов, и ему был передан H, то обман не вскроется. Аналогично, если он просит показать гамильтонов цикл, и ему был передан H′. В таком случае вероятность того, что Пегги всё-таки обманет Виктора после k раундов, равна ${\frac {1}{2^{k}}}$ , что может быть меньше любой заранее заданной величины при достаточном числе раундов^[29].

Предположим, что Виктор не узнал гамильтонов цикл, но хочет доказать Бобу, что Пегги его знает. Если Виктор, например, заснял на видео все раунды протокола, Боб едва ли ему поверит. Боб может предположить, что Виктор и Пегги в сговоре, и в каждом раунде Виктор заранее сообщал Пегги свой выбор случайного бита, чтобы Пегги могла передавать ему H для проверок изоморфизма и H′ для проверок гамильтонова цикла. Таким образом без участия Пегги доказать, что она знает гамильтонов цикл, можно лишь доказав, что во всех раундах протокола выбирались действительно случайные биты^[30].

Применение на практике

Теорема, гласящая, что для любой NP-полной задачи существует доказательство с нулевым разглашением, при этом, если использовать односторонние функции, можно создать корректные криптографические протоколы, была доказана Одедом Голдрейхом^[en], Сильвио Микали и Ави Вигдерсоном^[17]^[31]. То есть, можно доказать любому скептику, что обладаешь доказательством некоей математической теоремы, не раскрывая самого доказательства. Это тоже показывает, как может быть использован данный протокол в практических целях^[11].

Следующим методом, где может быть использовано доказательство с нулевым разглашением, является определением идентичности, при этом закрытый ключ у Пегги является так называемым «показателем идентичности», и, используя рассматриваемый протокол, можно доказать свою идентичность. То есть, можно доказать свою личность без использования различных физических устройств и данных (символов), таких как паспорта, различных снимков человека (сетчатки глаза, пальцев рук, лица и т. д.), а принципиально другим образом^[32]. Однако, он имеет ряд недостатков, которые могут быть применены для обхода защиты. Описанный выше метод был впервые предложен Амосом Фиатом^[en], Ади Шамиром и Уриэлем Фейге^{[источник не указан 1158 дней]} в 1987 году^[33].

Также доказательства с нулевым разглашением могут быть использованы в протоколах конфиденциального вычисления, которые позволяют нескольким участникам убедиться в том, что другая сторона следует протоколу честно^[17].

Злоупотребления

Предложено несколько способов злоупотребления доказательством с нулевым разглашением, которые используют те или иные слабые стороны протокола:

Проблема гроссмейстера

В данном примере некоторая сторона может доказать владение секретом, не обладая им на самом деле или, другими словами, может имитировать то лицо, которому на самом деле принадлежит секрет^[34]. В настоящее время предложен способ решения проблемы Томасом Бетом^[de] и Иво Десмедтом^[en]^[35].

Обман с несколькими личностями

Если сторона сможет создать несколько секретов, то соответственно она также сможет создать «несколько личностей», одну из которых никогда пусть не будет использовать. Такая возможность позволяет, например, совершить преступление и безнаказанно скрыться. Затем, во время совершения преступления, сторона идентифицирует себя никогда не используемой личностью. После преступления личность никогда больше не используется. Таким образом, выследить преступника практически невозможно. Данное злоупотребление обходится, если заранее не допустить возможность создания ещё одного секрета^[36].

Обман, выполненный мафией

Ещё один пример, когда одна сторона выдает себя за другую. Пусть имеется 4 участника: A, B, C, D. Причём B и С сотрудничают между собой («принадлежат одной мафии»). А доказывает свою личность B, а С хочет выдать себя за A перед D. B владеет рестораном, принадлежащим мафии, С — также представитель мафии, D — ювелир. A и D не знают о предстоящем мошенничестве. В момент, когда A готов заплатить за обед и идентифицировать себя перед B, B извещает С о начале мошенничества. Это возможно благодаря наличию радиоканала между ними. В это время С выбирает бриллиант, который хочет купить, и D начинает идентифицировать личность С, который выдает себя за A. С передаёт протокольный вопрос к B, а тот в свою очередь, задаёт его А. Ответ передаётся в обратном порядке. Таким образом А заплатит не только за обед, но и за дорогой бриллиант. Как видно из вышеописанного, существуют определённые требования для подобного мошенничества. Когда А начинает доказывать свою личность перед B, а С — перед D, действия B и С должны быть синхронизированы. Данное злоупотребление тоже разрешимо. Например, если в магазине ювелира будет клетка Фарадея, то «мафиози» не смогут обмениваться сообщениями^[37].

Возможные атаки

Атака на основе подобранного шифротекста

Данная атака осуществима при использовании неинтерактивного метода взаимодействия в протоколе нулевого разглашения.

При использовании такого протокола возникает несколько проблем. Во-первых, нужно решить, как нужно осуществлять взаимодействие, и при этом должны быть сохранены фундаментальные особенности самого протокола: полнота, корректность и «нулевое разглашение». Помимо того, что можно достаточно просто доказать нулевое знание другой стороне, если можно прослушивать канал, то есть столкнуться с проблемой гроссмейстера.

Так вот сама атака заключается в следующем: злоумышленник, используя сложность доказательства обладанием знания, включает «атакующий» шифротекст, подсовывая его в кучу других шифротекстов, которые должны быть расшифрованы. Данная атака называется «playback» атака^[38].

Возможное решение основано на работе Мони Наора^[en] и Моти Юнга^[en], которая заключается в следующем: Доказывающий и Проверяющий шифруют сообщения публичным ключом, это приводит к тому, что описанная выше атака перестает работать^[39].

Атака на мультипротокольную систему нулевого знания

Тида и Ямамото предложили такую реализацию протокола нулевого знания, которая значительно повышает скорость доказательств обладанием нулевым знанием при одновременном доказательстве сразу нескольких утверждений и, как следствие, производительность всей системы в целом^[40]. Ключевой особенностью является ограничение на количество итераций для доказательства. Как было показано в работе К. Пэна^[41], данный алгоритм оказался полностью неустойчивым к следующей атаке. Используя несколько правильно подобранных итераций, злоумышленник может пройти верификацию и нарушить главные положения о протоколе. Причём было показано, что данная атака всегда осуществима на такую систему.

Атака с помощью квантового компьютера

В 2005 году Джоном Ватрусом^[en] было показано, что не все системы с нулевым знанием являются устойчивыми к атакам с помощью квантового компьютера. Однако было доказано, что можно всегда построить такую систему, которая будет устойчива против квантовых атак, в предположении, что существуют квантовые системы с «сокрытием обязательств»^[42].

См. также

Примечания

↑ Goldreich, 2013.
1 2 Шнайер, 2002, pp. 87—92.
↑ Goldwasser, Micali, Rackoff, 1989, pp. 186—189.
↑ Santis, Micali, Persiano, 1988.
↑ Blum, Feldman, Micali, 1988.
↑ Шнайер, 2002, pp. 90—91.
↑ Blum, 1988, p. 1444.
↑ Menezes et al, 1996, pp. 406—408.
↑ Шнайер, 2002, pp. 86—89.
↑ Goldwasser, Micali, Rackoff, 1989, pp. 188—189.
1 2 Шнайер, 2002, pp. 91—92.
↑ Мао, 2005, pp. 683—696.
↑ Мао, 2005, pp. 684—688.
↑ Sahai, Vadhan, 2003.
↑ Мао, 2005, p. 696.
↑ Мао, 2005, pp. 692—696.
1 2 3 Goldreich, Micali, Wigderson, 1986.
↑ Goldwasser, Micali, Rackoff, 1989.
↑ Goldwasser, Micali, Rackoff, 1989, pp. 198—205.
↑ Goldwasser, Micali and Rackoff Receive Gödel Prize in 1993 (неопр.) (недоступная ссылка). ACM Sigact (1993). Архивировано 8 декабря 2015 года.
↑ Goldwasser, Micali Receive ACM Turing Award for Advances in Cryptography (неопр.) (недоступная ссылка). ACM. Проверено 13 марта 2013. Архивировано 16 марта 2013 года.
↑ Goldwasser, Micali, 1982.
↑ Мао, 2005, pp. 524—528.
↑ Мао, 2005, pp. 678—682.
↑ M.O.Rabin. Digital signatures. — Foundations of Secure Computation. — New York: Academic Press, 1978. — С. 155—168. — ISBN 0122103505.
↑ Шнайер, 2002, pp. 87—89.
1 2 Quisquater et al, 1990.
↑ Шнайер, 2002, pp. 87—88.
1 2 3 4 Blum, 1988.
↑ Шнайер, 2002, pp. 89—90.
↑ Goldreich, Micali, Wigderson, 1987.
↑ Шнайер, 2002, p. 92.
↑ Fiat, Shamir, 1987.
↑ Шнайер, 2002, pp. 92—93.
↑ Beth, Desmedt, 1991.
↑ Шнайер, 2002, pp. 93—94.
↑ Шнайер, 2002, p. 93.
↑ Rackoff, Simon, 1992.
↑ Naor, Yung, 1990.
↑ Chida, Yamamoto, 2008.
↑ Peng, 2012.
↑ Watrous, 2006.

Литература

книги и монографии

Мао В. Современная криптография: Теория и практика — М.: Вильямс, 2005. — 768 с. — ISBN 978-5-8459-0847-6
<a href='https://wikidata.org/wiki/Track:Q21704656'></a><a href='https://wikidata.org/wiki/Track:Q21704663'></a><a href='https://wikidata.org/wiki/Track:Q21694521'></a>
Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
Menezes A. J., Oorschot P. v., Vanstone S. A. Chapter 10 // Handbook of Applied Cryptography — CRC Press, 1996. — P. 405–417. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0
<a href='https://wikidata.org/wiki/Track:Q27123086'></a><a href='https://wikidata.org/wiki/Track:Q4723156'></a><a href='https://wikidata.org/wiki/Track:Q15262410'></a><a href='https://wikidata.org/wiki/Track:Q954828'></a><a href='https://wikidata.org/wiki/Track:Q21725116'></a><a href='https://wikidata.org/wiki/Track:Q7437437'></a>
Саломаа А. Криптография с открытым ключом — М.: Мир, 1995. — 318 с. — ISBN 978-5-03-001991-8
<a href='https://wikidata.org/wiki/Track:Q21725147'></a><a href='https://wikidata.org/wiki/Track:Q2440867'></a><a href='https://wikidata.org/wiki/Track:Q21725143'></a>
Goldreich O. A Short Tutorial of Zero-Knowledge // Secure Multi-Party Computation — Amsterdam, Berlin, Tokyo, Washington: IOS Press, 2013. — P. 28–60. — 285 p. — ISBN 978-1-61499-168-7
<a href='https://wikidata.org/wiki/Track:Q21725175'></a><a href='https://wikidata.org/wiki/Track:Q64'></a><a href='https://wikidata.org/wiki/Track:Q61'></a><a href='https://wikidata.org/wiki/Track:Q5972920'></a><a href='https://wikidata.org/wiki/Track:Q727'></a><a href='https://wikidata.org/wiki/Track:Q21725177'></a><a href='https://wikidata.org/wiki/Track:Q253354'></a>

статьи

Goldwasser S., Micali S. Probabilistic encryption & how to play mental poker keeping secret all partial information // STOC'82: Proceedings of the fourteenth annual ACM symposium on Theory of computing — New York, NY, USA: ACM, 1982. — P. 365–377. — ISBN 978-0-89791-070-5 — doi:10.1145/800070.802212
<a href='https://wikidata.org/wiki/Track:Q21714950'></a><a href='https://wikidata.org/wiki/Track:Q93080'></a><a href='https://wikidata.org/wiki/Track:Q11609'></a><a href='https://wikidata.org/wiki/Track:Q21714951'></a>
Blum M. How to Prove a Theorem So No One Else Can Claim It // ICM'86: International Congress of Mathematicians. Berkeley, California, USA, August 3-11, 1986, Proceedings / A. Gleason — Providence: AMS, 1988. — P. 1444–1451. — 1850 p. — ISBN 978-0-8218-0110-9
<a href='https://wikidata.org/wiki/Track:Q18383'></a><a href='https://wikidata.org/wiki/Track:Q92626'></a><a href='https://wikidata.org/wiki/Track:Q465654'></a><a href='https://wikidata.org/wiki/Track:Q504857'></a><a href='https://wikidata.org/wiki/Track:Q21704769'></a><a href='https://wikidata.org/wiki/Track:Q21704768'></a>
Goldreich O., Micali S., Wigderson A. Proofs that Yield Nothing but Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems // FOCS'86: 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986. Proceedings — IEEE Computer Society, 1986. — P. 174–187. — ISBN 978-0-8186-0740-0
<a href='https://wikidata.org/wiki/Track:Q92957'></a><a href='https://wikidata.org/wiki/Track:Q669561'></a><a href='https://wikidata.org/wiki/Track:Q21714556'></a><a href='https://wikidata.org/wiki/Track:Q93080'></a><a href='https://wikidata.org/wiki/Track:Q21714558'></a><a href='https://wikidata.org/wiki/Track:Q253354'></a>
Goldreich O., Micali S., Wigderson A. How to Prove All NP Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design: Extended Abstract // Advances in Cryptology — CRYPTO ’86: 6th Annual International Cryptology Conference, Santa Barbara, California, USA, 1986, Proceedings / A. M. Odlyzko — Springer Berlin Heidelberg, 1987. — P. 171–185. — 490 p. — (Lecture Notes in Computer Science; Vol. 263) — ISBN 978-3-540-18047-0 — ISSN 0302-9743 — doi:10.1007/3-540-47721-7_11
<a href='https://wikidata.org/wiki/Track:Q21587985'></a><a href='https://wikidata.org/wiki/Track:Q21721320'></a><a href='https://wikidata.org/wiki/Track:Q506615'></a><a href='https://wikidata.org/wiki/Track:Q92957'></a><a href='https://wikidata.org/wiki/Track:Q924044'></a><a href='https://wikidata.org/wiki/Track:Q93080'></a><a href='https://wikidata.org/wiki/Track:Q21721313'></a><a href='https://wikidata.org/wiki/Track:Q253354'></a>
Fiat A., Shamir A. How to Prove Yourself: Practical Solutions to Identification and Signature Problems // Advances in Cryptology — CRYPTO ’86: 6th Annual International Cryptology Conference, Santa Barbara, California, USA, 1986, Proceedings / A. M. Odlyzko — Springer Berlin Heidelberg, 1987. — P. 186–194. — 490 p. — (Lecture Notes in Computer Science; Vol. 263) — ISBN 978-3-540-18047-0 — ISSN 0302-9743 — doi:10.1007/3-540-47721-7_12
<a href='https://wikidata.org/wiki/Track:Q506615'></a><a href='https://wikidata.org/wiki/Track:Q21721313'></a><a href='https://wikidata.org/wiki/Track:Q21721403'></a><a href='https://wikidata.org/wiki/Track:Q924044'></a><a href='https://wikidata.org/wiki/Track:Q4747864'></a><a href='https://wikidata.org/wiki/Track:Q320624'></a><a href='https://wikidata.org/wiki/Track:Q21587985'></a>
Desmedt Y. G., Goutier C., Bengio S. Special Uses and Abuses of the Fiat-Shamir Passport Protocol (extended abstract) // Advances in Cryptology — CRYPTO ’87: A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings / C. Pomerance — Berlin: Springer Berlin Heidelberg, 1988. — P. 21–39. — (Lecture Notes in Computer Science; Vol. 293) — ISBN 978-3-540-18796-7 — ISSN 0302-9743 — doi:10.1007/3-540-48184-2_3
<a href='https://wikidata.org/wiki/Track:Q64'></a><a href='https://wikidata.org/wiki/Track:Q924044'></a><a href='https://wikidata.org/wiki/Track:Q16728514'></a><a href='https://wikidata.org/wiki/Track:Q21714631'></a><a href='https://wikidata.org/wiki/Track:Q21714633'></a><a href='https://wikidata.org/wiki/Track:Q21704688'></a><a href='https://wikidata.org/wiki/Track:Q761544'></a><a href='https://wikidata.org/wiki/Track:Q21714635'></a><a href='https://wikidata.org/wiki/Track:Q21587985'></a>
Santis A. D., Micali S., Persiano G. Non-Interactive Zero-Knowledge Proof Systems // Advances in Cryptology — CRYPTO ’87: A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16-20, 1987, Proceedings / C. Pomerance — Berlin: Springer Berlin Heidelberg, 1988. — P. 52–72. — (Lecture Notes in Computer Science; Vol. 293) — ISBN 978-3-540-18796-7 — ISSN 0302-9743 — doi:10.1007/3-540-48184-2_5
<a href='https://wikidata.org/wiki/Track:Q64'></a><a href='https://wikidata.org/wiki/Track:Q924044'></a><a href='https://wikidata.org/wiki/Track:Q21587985'></a><a href='https://wikidata.org/wiki/Track:Q21704685'></a><a href='https://wikidata.org/wiki/Track:Q21704688'></a><a href='https://wikidata.org/wiki/Track:Q761544'></a><a href='https://wikidata.org/wiki/Track:Q93080'></a><a href='https://wikidata.org/wiki/Track:Q21704689'></a><a href='https://wikidata.org/wiki/Track:Q21704686'></a>
Blum M., Feldman P., Micali S. Non-interactive zero-knowledge and its applications // STOC'88: Proceedings of the twentieth annual ACM symposium on Theory of computing — New York City: ACM, 1988. — P. 103–112. — ISBN 978-0-89791-264-8 — doi:10.1145/62212.62222
<a href='https://wikidata.org/wiki/Track:Q21714540'></a><a href='https://wikidata.org/wiki/Track:Q21714499'></a><a href='https://wikidata.org/wiki/Track:Q127992'></a><a href='https://wikidata.org/wiki/Track:Q60'></a><a href='https://wikidata.org/wiki/Track:Q93080'></a><a href='https://wikidata.org/wiki/Track:Q92626'></a><a href='https://wikidata.org/wiki/Track:Q21714544'></a>
Goldwasser S., Micali S., Rackoff C. The knowledge complexity of interactive proof systems // SIAM J. Comput. / M. Sudan — Society for Industrial and Applied Mathematics, 1989. — Vol. 18, Iss. 1. — P. 186–208. — ISSN 0097-5397; 1095-7111 — doi:10.1137/0218012
<a href='https://wikidata.org/wiki/Track:Q11609'></a><a href='https://wikidata.org/wiki/Track:Q7390263'></a><a href='https://wikidata.org/wiki/Track:Q21694644'></a><a href='https://wikidata.org/wiki/Track:Q93149'></a><a href='https://wikidata.org/wiki/Track:Q93080'></a><a href='https://wikidata.org/wiki/Track:Q782100'></a><a href='https://wikidata.org/wiki/Track:Q93097'></a>
Quisquater J., Quisquater M., Quisquater M. et al. How to Explain Zero-Knowledge Protocols to Your Children // Advances in Cryptology — CRYPTO ’89: 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings / G. Brassard — Springer New York, 1990. — P. 628–631. — (Lecture Notes in Computer Science; Vol. 435) — ISBN 978-0-387-97317-3 — ISSN 0302-9743 — doi:10.1007/0-387-34805-0_60
<a href='https://wikidata.org/wiki/Track:Q21694650'></a><a href='https://wikidata.org/wiki/Track:Q21694656'></a><a href='https://wikidata.org/wiki/Track:Q924044'></a><a href='https://wikidata.org/wiki/Track:Q2062294'></a><a href='https://wikidata.org/wiki/Track:Q21694652'></a><a href='https://wikidata.org/wiki/Track:Q92938'></a><a href='https://wikidata.org/wiki/Track:Q21694659'></a><a href='https://wikidata.org/wiki/Track:Q21694658'></a><a href='https://wikidata.org/wiki/Track:Q21694670'></a>
Naor M., Yung M. Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks // STOC'90: Proceedings of the twenty-second annual ACM symposium on Theory of computing — New York City: ACM, 1990. — P. 427–437. — ISBN 978-0-89791-361-4 — doi:10.1145/100216.100273
<a href='https://wikidata.org/wiki/Track:Q6899861'></a><a href='https://wikidata.org/wiki/Track:Q60'></a><a href='https://wikidata.org/wiki/Track:Q127992'></a><a href='https://wikidata.org/wiki/Track:Q6917668'></a><a href='https://wikidata.org/wiki/Track:Q21722728'></a><a href='https://wikidata.org/wiki/Track:Q21722720'></a>
Beth T., Desmedt Y. G. Identification Tokens — or: Solving The Chess Grandmaster Problem // Advances in Cryptology — CRYPTO ’90: 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings / A. J. Menezes, S. A. Vanstone — Springer Berlin Heidelberg, 1991. — P. 169–176. — (Lecture Notes in Computer Science; Vol. 537) — ISBN 978-3-540-54508-8 — ISSN 0302-9743 — doi:10.1007/3-540-38424-3_12
<a href='https://wikidata.org/wiki/Track:Q21704651'></a><a href='https://wikidata.org/wiki/Track:Q2422408'></a><a href='https://wikidata.org/wiki/Track:Q7437437'></a><a href='https://wikidata.org/wiki/Track:Q4723156'></a><a href='https://wikidata.org/wiki/Track:Q924044'></a><a href='https://wikidata.org/wiki/Track:Q16728514'></a><a href='https://wikidata.org/wiki/Track:Q21704652'></a><a href='https://wikidata.org/wiki/Track:Q21587985'></a>
Rackoff C., Simon D. R. Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack // Advances in Cryptology — CRYPTO’91: 11th Annual International Cryptology Conference, Santa Barbara, California, USA, 1991, Proceedings / J. Feigenbaum — Springer Science+Business Media, 1992. — P. 433–444. — 484 p. — (Lecture Notes in Computer Science; Vol. 576) — ISBN 978-3-540-55188-1 — ISSN 0302-9743 — doi:10.1007/3-540-46766-1_35
<a href='https://wikidata.org/wiki/Track:Q176916'></a><a href='https://wikidata.org/wiki/Track:Q21721409'></a><a href='https://wikidata.org/wiki/Track:Q21721408'></a><a href='https://wikidata.org/wiki/Track:Q924044'></a><a href='https://wikidata.org/wiki/Track:Q21721405'></a><a href='https://wikidata.org/wiki/Track:Q4815338'></a><a href='https://wikidata.org/wiki/Track:Q93097'></a>
Bleichenbacher D. Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 // Advances in Cryptology — CRYPTO ’98: 18th Annual International Cryptology Conference Santa Barbara, California, USA August 23–27, 1998 Proceedings / H. Krawczyk — Springer Berlin Heidelberg, 1998. — P. 1–12. — 524 p. — (Lecture Notes in Computer Science; Vol. 1462) — ISBN 978-3-540-64892-5 — ISSN 0302-9743 — doi:10.1007/BFB0055716
<a href='https://wikidata.org/wiki/Track:Q21722638'></a><a href='https://wikidata.org/wiki/Track:Q21587985'></a><a href='https://wikidata.org/wiki/Track:Q924044'></a><a href='https://wikidata.org/wiki/Track:Q21722642'></a><a href='https://wikidata.org/wiki/Track:Q21722636'></a><a href='https://wikidata.org/wiki/Track:Q5216580'></a>
Sahai A., Vadhan S. A complete problem for statistical zero knowledge // J. ACM / V. Vianu — New York City: ACM, 2003. — Vol. 50, Iss. 2. — P. 196–249. — ISSN 0004-5411; 1557-735X; 1535-9921 — doi:10.1145/636865.636868
<a href='https://wikidata.org/wiki/Track:Q7926426'></a><a href='https://wikidata.org/wiki/Track:Q60'></a><a href='https://wikidata.org/wiki/Track:Q21694677'></a><a href='https://wikidata.org/wiki/Track:Q7404539'></a><a href='https://wikidata.org/wiki/Track:Q127992'></a><a href='https://wikidata.org/wiki/Track:Q18631258'></a><a href='https://wikidata.org/wiki/Track:Q1709878'></a>
Watrous J. Zero-Knowledge against Quantum Attacks // STOC'06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing — ACM, 2006. — P. 296–305. — ISBN 978-1-59593-134-4 — doi:10.1137/060670997 — arXiv:quant-ph/0511020
<a href='https://wikidata.org/wiki/Track:Q127992'></a><a href='https://wikidata.org/wiki/Track:Q6263205'></a><a href='https://wikidata.org/wiki/Track:Q21725069'></a><a href='https://wikidata.org/wiki/Track:Q21725078'></a>
Chida K., Yamamoto G. Batch Processing for Proofs of Partial Knowledge and Its Applications // IEICE Trans. Fund. Electron. Comm. Comput. Sci. — 2008. — Vol. E91-A, Iss. 1. — P. 150–159. — ISSN 0916-8508 — doi:10.1093/IETFEC/E91-A.1.150
<a href='https://wikidata.org/wiki/Track:Q21724515'></a><a href='https://wikidata.org/wiki/Track:Q21724669'></a><a href='https://wikidata.org/wiki/Track:Q21724485'></a><a href='https://wikidata.org/wiki/Track:Q15754988'></a>
Peng, K. Attack against a batch zero-knowledge proof system // IET Information Security — IET, 2012. — Vol. 6, Iss. 1. — P. 1–5. — ISSN 1751-8709 — doi:10.1049/IET-IFS.2011.0290
<a href='https://wikidata.org/wiki/Track:Q21725032'></a><a href='https://wikidata.org/wiki/Track:Q21725038'></a><a href='https://wikidata.org/wiki/Track:Q1164410'></a><a href='https://wikidata.org/wiki/Track:Q15754535'></a>

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[_7ba83deaf1c7982c-1] Goldreich, 2013.

[_e8d99bccad48971f-2] 1 2 Шнайер, 2002, pp. 87—92.

[_4cd613949205549f-3] Goldwasser, Micali, Rackoff, 1989, pp. 186—189.

[_fde87505205c39f9-4] Santis, Micali, Persiano, 1988.

[_77790337297ff983-5] Blum, Feldman, Micali, 1988.

[_1b4c02a32f94e9f8-6] Шнайер, 2002, pp. 90—91.

[_70e748f7a356cc5c-7] Blum, 1988, p. 1444.

[_c150274091b8b00b-8] Menezes et al, 1996, pp. 406—408.

[_25c1f36ef69454d0-9] Шнайер, 2002, pp. 86—89.

[_04436fb67faf61e1-10] Goldwasser, Micali, Rackoff, 1989, pp. 188—189.

[_fb02f9e814b88550-11] 1 2 Шнайер, 2002, pp. 91—92.

[_bf730f83cbf55cfc-12] Мао, 2005, pp. 683—696.

[_f743218fb6d4eade-13] Мао, 2005, pp. 684—688.

[_55c1e06485f57962-14] Sahai, Vadhan, 2003.

[_fbcc93d4154f9117-15] Мао, 2005, p. 696.

[_961096b73de7ae56-16] Мао, 2005, pp. 692—696.

[_6d36baaaf89ef669-17] 1 2 3 Goldreich, Micali, Wigderson, 1986.

[_fad192e900503d1a-18] Goldwasser, Micali, Rackoff, 1989.

[_e7a1d55082d96fc9-19] Goldwasser, Micali, Rackoff, 1989, pp. 198—205.

[20] Goldwasser, Micali and Rackoff Receive Gödel Prize in 1993 (неопр.) (недоступная ссылка). ACM Sigact (1993). Архивировано 8 декабря 2015 года.

[21] Goldwasser, Micali Receive ACM Turing Award for Advances in Cryptography (неопр.) (недоступная ссылка). ACM. Проверено 13 марта 2013. Архивировано 16 марта 2013 года.

[_da978d7560b94b87-22] Goldwasser, Micali, 1982.

[_c65faafd7a37332e-23] Мао, 2005, pp. 524—528.

[_137df07be0b2a4c5-24] Мао, 2005, pp. 678—682.

[25] M.O.Rabin. Digital signatures. — Foundations of Secure Computation. — New York: Academic Press, 1978. — С. 155—168. — ISBN 0122103505.

[_e8d99accad489543-26] Шнайер, 2002, pp. 87—89.

[_06e22e6bbee44054-27] 1 2 Quisquater et al, 1990.

[_e8d99accad489542-28] Шнайер, 2002, pp. 87—88.

[_29a163bf1b1dc6db-29] 1 2 3 4 Blum, 1988.

[_9401ac0757b256fb-30] Шнайер, 2002, pp. 89—90.

[_e5310b9f22cd63c4-31] Goldreich, Micali, Wigderson, 1987.

[_7e973e3e4017871a-32] Шнайер, 2002, p. 92.

[_beaac4821697d782-33] Fiat, Shamir, 1987.

[_04ecb33daccf2250-34] Шнайер, 2002, pp. 92—93.

[_727bbe6296c37a12-35] Beth, Desmedt, 1991.

[_3f47c80d17310e98-36] Шнайер, 2002, pp. 93—94.

[_7e973e3e4017871b-37] Шнайер, 2002, p. 93.

[_86fce29ee4cd672c-38] Rackoff, Simon, 1992.

[_0d79f293f3e594d1-39] Naor, Yung, 1990.

[_221592bfda731221-40] Chida, Yamamoto, 2008.

[_8646749f2857b45e-41] Peng, 2012.

[_7891874468c8f5dc-42] Watrous, 2006.