Как стать автором
Обновить

Доказательство с нулевым разглашением

Чулан
Доказательство с нулевым разглашением (знанием) (Zero-knowledge proof) представляет собой криптографический протокол, позволяющий одной из сторон (проверяющему, стороне B) убедиться в том, что вторая сторона (доказывающая, сторона A) знает какое-либо утверждение, при этом проверяющий не получает никакой другой информации о самом утверждении. Другими словами, А доказывает знание секрета, не разглашая самого секрета.

Использовать доказательства с нулевым знанием для доказательства идентичности было впервые предложено Уриелем Файгом, Амосом Фиатом и Ади Шамиром. В данном случае пользователь доказывает знание своего закрытого ключа, который в данном случае выступает в роли секрета, не раскрывая его. Таким образом, он доказывает свою идентичность.

Читать дальше →
Всего голосов 40: ↑37 и ↓3 +34
Просмотры 13K
Комментарии 30

«Что такое доказательство?»: взгляд из теоретической информатики

Блог компании Образовательные проекты JetBrains Алгоритмы *Математика *
Теоретическая информатика — одно из направлений обучения на кафедре Математических и информационные технологий Академического университета. Нас часто спрашивают, чем занимается теоретическая информатика. Теоретическая информатика — активно развивающееся научное направление, включающее в себя как фундаментальные области: алгоритмы, сложность вычислений, криптография, теория информации, теория кодирования, алгоритмическая теория игр, так и более прикладные: искусственный интеллект, машинное обучение, семантика языков программирования, верификация, автоматическое доказательство теорем и многое другое. Эту статью мы посвятим обзору лишь небольшого сюжета, а именно расскажем о необычных подходах к понятию доказательства, которые рассматривает теоретическая информатика.



Чтобы объяснить, о какого рода доказательствах пойдет речь, рассмотрим пример: есть компьютерная программа, авторы которой утверждают, что программа делает что-то определенное (конкретные примеры будут чуть позже). Программу можно запустить и получить ответ. А как можно удостовериться, что программа делает то, что должна делать? Хорошо бы, если кроме ответа программа выдавала бы доказательство того, что этот ответ правильный.

Рассмотрим более конкретный пример: мы хотим иметь программу, которая в двудольном графе находит паросочетание максимального размера вместе с доказательством его максимальности.



Напомним, что граф называется двудольным, если его вершины можно покрасить в два цвета так, что ребра графа соединяют вершины разных цветов. Паросочетанием в графе называется такое множество ребер, что никакие два из них не имеют общего конца. Множество вершин графа называется покрывающим, если каждое ребро графа имеет как минимум один конец в этом множестве. Теорема Кенига гласит, что в двудольном графе размер максимального паросочетания совпадает с размером минимального покрывающего множества. Таким образом, чтобы доказать, что паросочетание является максимальным, можно предъявить, покрывающее множество, размер которого совпадает с размером данного паросочетания. Действительно, это покрывающее множество будет минимальным, поскольку каждое покрывающее множество обязано покрыть хотя бы один конец каждого ребра этого паросочетания. Например, в графе на рисунке паросочетание (M1, G3), (M2, G2), (M4,G1) будет максимальным, поскольку есть покрывающее множество размера 3, которое состоит из G2, G3 и M4. Отметим, что проверить такое доказательство гораздо проще, чем вычислять максимальное паросочетание: достаточно проверить, что размер паросочетания совпадает с размером покрывающего множества и проверить, что все ребра покрыты.

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



Как можно доказать правильность результата? Если система совместна, то доказательством совместности может стать решение этой системы (нетрудно доказать, что если у такой системы есть решение, то есть и рациональное решение, т.е. его можно записать). А как доказать, что система несовместна? Оказывается, что это сделать можно с помощью леммы Фаркаша, которая утверждает, что если система нестрогих линейных неравенств несовместна, то можно сложить эти неравенства с неотрицательными коэффициентами и получить противоречивое неравенство 0≥1. Например, система на рисунке несовместна, и если сложить первое уравнение с коэффициентом 1, второе с коэффициентом 2, а третье с коэффициентом 1, то получится 0≥1. Доказательством несовместности будет как раз набор неотрицательных коэффициентов.

В этой статье мы поговорим о том, нужны ли доказательства, или проверка доказательства всегда не проще, чем самостоятельное решение задачи. (В примере про максимальное паросочетание мы не доказали, что не существует алгоритма, решающего задачу за то же время, сколько занимает проверка доказательства.) Если мы не ограничиваем размер доказательства, то окажется, что доказательства нужны, а если будем требовать, чтобы доказательства были короткими, то вопрос о нужности доказательств эквивалентен важнейшему открытому вопросу о равенстве классов P и NP. Потом мы поговорим об интерактивных доказательствах (доказательства в диалоге). Обсудим криптографические доказательства, которые не разглашают лишнюю информацию, кроме верности доказываемого утверждения. И закончим обсуждением вероятностно проверяемых доказательств и знаменитой PCP-теоремы, которая используется для доказательства трудности приближения оптимизационных задач.

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

Читать дальше →
Всего голосов 49: ↑46 и ↓3 +43
Просмотры 22K
Комментарии 11

Анонимные криптовалюты: почему Эдвард Сноуден поддерживает концепцию доказательства с нулевым разглашением

Блог компании Binary District Информационная безопасность *Финансы в IT
Перевод


Перевела – Мария Агеева, Binary District

6 февраля на блокчейн-митапе Zero knowledge proof protocols генеральный директор ZCash Зуко Уилкокс и основатель Ergo Platform Александр Чепурной обсудят основные принципы работы протокола с нулевым разглашением, а также специфику ZCash, Bitcoin, Ethereum и других криптовалют.

Читать дальше →
Всего голосов 15: ↑12 и ↓3 +9
Просмотры 17K
Комментарии 9

Как победить гроссмейстера, не умея играть в шахматы. Про злоупотребление доказательства с нулевым знанием

Информационная безопасность *Криптография *Научно-популярное
Из песочницы

Статья про злоупотребления доказательства с нулевым знанием. Описаны такие темы, как "проблема гроссмейстера", "обман, выполненный мафией", "обман, выполненный террористами" и предложены решения этих проблем.

Читать далее
Всего голосов 31: ↑28 и ↓3 +25
Просмотры 10K
Комментарии 23

Молчание — золото: доказательство существования Гамильтонова цикла в графе

Криптография *Алгоритмы *
Из песочницы

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

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

Read more
Всего голосов 26: ↑23 и ↓3 +20
Просмотры 5K
Комментарии 13

Как связаны аутентификация и теория относительности? Учёные ищут способы защиты ATM за гранью физики

Блог компании DataLine Информационная безопасность *Криптография *Занимательные задачки Научно-популярное

В ноябре Nature опубликовал работу учёных Женевского университета (UNIGE) и канадского Университета Макгилла, которые решили заменить привычную систему PIN-кодов на более безопасную. В поисках сверхнадежной аутентификации исследователи предложили пересмотреть фактор владения и опираться на метод математического доказательства с нулевым разглашением в связке со специальной теорией относительности. 

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

Читать далее
Всего голосов 17: ↑17 и ↓0 +17
Просмотры 5.8K
Комментарии 15

Доказательство с нулевым разглашением (ZKP) — дорожная карта блокчейна

Децентрализованные сети *Информационная безопасность *Криптография *Распределённые системы *
Recovery mode

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

Доказательство с нулевым разглашением было впервые определено в статье 1985 года "The Knowledge Complexity of Interactive Proof Systems", написанной Шафи Голдвассером и Сильвио Микали. В этой статье авторы показывают, что аттестующий может убедить проверяющего в истинности определенного утверждения о точке данных, не раскрывая никакой дополнительной информации об этих данных.

Zero-Knowledge Proof может быть интерактивным, когда доказывающий убеждает конкретного проверяющего, но должен повторять этот процесс для каждого проверяющего, или неинтерактивным, когда доказывающий создает доказательство, которое может быть проверено любым человеком, использующим то же доказательство. Существует несколько реализаций доказательства нулевого знания, включая zk-SNARKS, zk-STARKS, PLONK и Bulletproofs, каждая из которых имеет свой размер доказательства транзакции, доказательство доказательства, время проверки и многое другое, работая с различными механизмами в своих системах.

Читать далее
Всего голосов 11: ↑6 и ↓5 +1
Просмотры 2.1K
Комментарии 3