User:20-BuchinskayaAV

From CryptoWiki
Jump to: navigation, search

Contents

Постановка задачи защиты информации (Security challenge)

Акроним zk-SNARK расшифровывается как «лаконичный неинтерактивный аргумент знания с нулевым знанием» и относится к доказательной конструкции, в которой можно доказать владение определенной информацией, например, секретный ключ, без раскрытия этой информации и без какого-либо взаимодействия между проверяющим и проверяющим.

Этот эффективный вариант доказательства знания с нулевым разглашением мы неформально опишем с помощью примера. Предположим, Алиса хочет доказать Бобу утверждение «Я (Алиса) обладаю 30 биткойнами». Простой способ сделать это для Алисы - указать 30 монет на цепочке блоков и для каждого из них подписать сообщение (например, «привет, мир»), используя секретный ключ, который контролирует эту монету. К сожалению, этот метод передает знания Бобу, показывая какие монеты принадлежат Алисе. В примере, если использовать доказательство с нулевым знанием, то это позволит Алисе достичь той же цели, не раскрывая никакой информации Бобу (кроме того факта, что она знает некоторые секретные ключи, которые контролируют 30 монет). Важно, что такие доказательства могут быть получены для любого утверждения. Утверждение может быть проверено на истинность с помощью эффективного вычисления, включающего вспомогательные входы, такие как люки и пароли (такие операторы называются «операторы NP»).

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

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

Обязательные свойства

Важно, что zk-SNARK должен обладать тремя свойствами:

1.Полнота: если утверждение действительно верно, то испытатель убедит в этом верификатора с любой наперед заданной точностью.

2.Корректность: если утверждение неверно, то любой, даже «нечестный», испытатель не сможет убедить верификатора за исключением пренебрежимо малой вероятности.

3.Нулевое разглашение: если утверждение верно, то любой, даже «нечестный», верификатор не узнает ничего кроме самого факта, что утверждение верно.

Связь с NIZK

Zk-SNARK связан со знакомым криптографическим примитивом: неинтерактивные доказательства с нулевым знанием знаний NIZK. И zk-SNARK, и NIZK требуют одноразовой доверительной настройки открытых параметров (ключей проверки и проверки для zk-SNARK и общей справочной строки для NIZKs). Оба обеспечивают одинаковые гарантии полноты, доказательства знания и нулевого знания. Разница заключается в гарантиях эффективности. В NIZK продолжительность доказательства и время проверки зависят от проверяемого языка NP. Например, для языка выполнимости схемы длина и время проверки в [GOS06b, GOS06a] являются линейными по размеру схемы. И наоборот, в zk-SNARK длина доказательства зависит только от параметра безопасности, а время проверки зависит только от размера экземпляра (и параметра безопасности), но не от размера канала или свидетеля. Таким образом, zk-SNARK можно рассматривать как «краткие NIZK», имеющие короткие доказательства и быстрое время проверки. Краткость сопровождается оговоркой: известные конструкции zk-SNARK основаны на более строгих предположениях, чем NIZK.


Вернуться к оглавлению

Теоретические основы решения задачи (Theoretical issues)

Первоначально неинтерактивное нулевое знание определялось только как единая система доказательства теорем. В такой системе для каждого доказательства требуется своя свежая общая ссылочная строка. Обычно общая ссылочная строка не является случайной строкой. Например, он может состоять из случайно выбранных групповых элементов, которые используют все стороны протокола. Хотя элементы группы являются случайными, ссылочная строка не является таковой, поскольку она содержит определенную структуру (например, элементы группы), которая отличается от случайности. Впоследствии Фейдж, Лапидот и Шамир представили много-теоремные доказательства с нулевым знанием как более универсальное понятие для неинтерактивных доказательств с нулевым знанием.

Условия, которые необходимы для zk-SNARK, описываются математическим языком следующим образом:

1. Полнота: для любого общего входа 5aa.png и полинома p(•),

6aa.png.

2. Корректность: для любого общего входа 7aa.png и любой интерактивной машины Тьюринга P' и полинома p(•),

Vtoroy.png.

3. Нулевое разглашение: для любого 5aa.png существует вероятностный полиномиальный алгоритм M, такой что

Tretiy.png.


Основные понятия

В этом разделе представлены основные понятия zk-SNARK и их математическое обоснование.

Гомоморфное скрытие

Роль этой части наиболее заметна в доказательствах.

Гомоморфным скрытием функции E(x) числа x является функцией, удовлетворяющей следующим свойствам:

  • Для большинства х зная E(x) трудно найти х.
  • Разные входы приводят к разным выходам, ​​поэтому, если x ≠ y, то E(x) ≠ E(y).
  • Если кто-то знает E(x) и E(y), он может сгенерировать гомоморфное скрытие арифметических выражений в x и y. Например, они могут вычислить E(x+y) из E(x) и E(y).

Теперь давайте рассмотрим пример того, как создаются сокрытия. На самом деле мы не можем построить их для обычных целых чисел с регулярным сложением, но нам нужно взглянуть на конечные группы: Пусть n будет некоторым целым числом. Когда мы пишем A mod n для целого числа A, мы имеем ввиду взять остаток от A после деления на n. Мы можем использовать операцию mod n, чтобы определить операцию сложения для чисел {0,…, n − 1}: мы делаем регулярное сложение, но затем применяем (mod n) к результату, чтобы получить число в диапазоне {0, …, n − 1}. Иногда мы пишем (mod n) справа, чтобы уточнить, что мы используем этот тип дополнения. Мы называем множество элементов {0, …, n − 1} вместе с операцией сложения группой Группа.JPG.

Основные криптографические конструкции и их стойкость (Cryptographic primitives and/or protocols)

Безопасность zk-SNARK основана на предположениях об уровне экспоненты и вариантах предположений Диффи-Хеллмана в билинейных группах [Gro10, BB04, Gen04]. В то время как предположения об уровне экспоненты довольно сильны, есть свидетельства того, что такие предположения могут быть присущи для построения zk-SNARK [GW11, BCCT12].

Menezes A.J., van Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography [1]

Stinson D.R. Cryptography: Theory and Practice [2]

Van Tilborg H.C.A., Jajodia S. (Eds.) Encyclopedia of Cryptography and Security [3]

Mao W. Modern Cryptography: Theory and Practice (2003) [4]

См. также другие источники по списку: [5]

Практические применения криптографических конструкций, особенности их реализации (Practical issues)

Zcash - это первое широко распространенное применение zk-SNARKs, новой формы криптографии с нулевым знанием. Строгая гарантия конфиденциальности Zcash вытекает из того факта, что экранированные транзакции в Zcash могут быть полностью зашифрованы на блокчейне, но все же могут быть проверены как действительные в соответствии с согласованными правилами сети, используя доказательства zk-SNARK. Если бы кто-то имел доступ к секретной случайности, используемой для генерации этих параметров, он мог бы создавать ложные доказательства, которые выглядели бы достоверными для верификатора. Для Zcash это означало бы, что злоумышленники могут создавать поддельные монеты. Чтобы этого не происходило, Zcash генерировал публичные параметры посредством сложной многопартийной церемонии.

Создание экранированных транзакций в Zcash - это еще один пример из множества возможных применений zk-SNARK. Теоретически, вы можете использовать zk-SNARK для проверки любого отношения, не раскрывая входные данные или утечки информации. Генерация доказательств для сложных функций все еще слишком сложна в вычислительном отношении, чтобы быть практичной для многих приложений, но команда Zcash расширяет границы для оптимизации zk-SNARK и уже открывает новые возможности с более эффективными реализациями.

В биткойнах транзакции проверяются путем связывания адреса отправителя, адреса получателя и входных и выходных значений в общедоступной цепочке блоков. Zcash использует zk-SNARK, чтобы доказать, что условия для действительной транзакции были выполнены, не раскрывая никакой важной информации об задействованных адресах или значениях. Отправитель экранированной транзакции создает доказательство, показывающее, что с высокой вероятностью: входные значения суммируются с выходными значениями для каждой экранированной передачи. Отправитель доказывает, что у него есть ключи личных расходов во входных заметках, что дает им право тратить. Закрытые ключи расходов входных заметок криптографически связаны с сигнатурой всей транзакции таким образом, что транзакция не может быть изменена стороной, которая не знает этих закрытых ключей. Биткойн отслеживает неизрасходованные транзакции (UTXO), чтобы определить, какие транзакции можно потратить. В Zcash экранированный эквивалент UTXO называется «обязательством», а расходование обязательства подразумевает выявление «аннулирующего». Узлы Zcash хранят списки всех обязательств, которые были созданы, и всех аннулирующих элементов, которые были обнаружены. Обязательства и аннулирующие элементы хранятся в виде хэшей, чтобы избежать раскрытия какой-либо информации об обязательствах или о том, какие аннулирующие элементы относятся к каким обязательствам.

Имеется возможность создавать полноценную цифровую валюту на основе бухгалтерских книг с надежными гарантиями конфиденциальности.Чтобы обеспечить нулевую конфиденциальность в Zcash, функция, определяющая действительность транзакции в соответствии с согласованными правилами сети, должна возвращать ответ о том, действительна транзакция или нет, не раскрывая какую-либо информацию, по которой она выполняла вычисления. Это делается путем кодирования некоторых согласованных правил сети в zk-SNARK. На высоком уровне zk-SNARKs сначала превращают то, что вы хотите доказать, в эквивалентную форму о знании решения некоторых алгебраических уравнений.

В настоящее время Zcash-реализация zk-SNARK может быть добавлена к любому существующему решению распределенной бухгалтерской книги в качестве уровня безопасности с нулевым знанием для случаев использования на предприятии.

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

Существует три опубликованные реализации zk-SNARK: (i) Parno et al. [PGHR13] представляет реализацию zk-SNARK для программ, не имеющих зависимостей от данных; (ii) Бен-Сассон и соавт. [BCG + 13] представляет реализацию zk-SNARK для произвольных программ (с зависимостями данных); и (iii) Ben-Sasson et al. [BCTV14] представляет реализацию zk-SNARK, которая поддерживает программы, которые изменяют свой собственный код (например, для генерации кода во время выполнения); их реализация также снижает затраты на программы большего размера и позволяет использовать универсальные пары ключей. Каждая из вышеперечисленных работ также достигает zk-SNARK для удовлетворения арифметической схемы в качестве трамплина к их соответствующим усилиям более высокого уровня.

Глоссарий (Glossary)

Ниже приведены примеры оформления ссылок на термины и определения, содержащиеся в глоссарии. Все термины и определения должны содержать ссылки на источники, из которых они заимствованы. Источники должны быть перечислены в библиографическом указателе к вашему разделу

и т.д.

Библиографический указатель (Bibliography)

Перейти к списку литературы или базе данных публикаций по разделу "Наименование вашего раздела".

Вернуться к оглавлению

Бучинская А.В., 2020 год