Перевод Кольцевые подписи (Часть 1): протокол идентичности Шнорра

Тема в разделе "Статьи", создана пользователем Mr. Pickles, 11 май 2019.

  1. Mr. Pickles

    Команда форума Модератор Редактор

    Регистрация:
    11 сен 2017
    Сообщения:
    429
    Симпатии:
    154
    Интерактивные схемы доказательства с нулевым раскрытием конфиденциальных данных

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

    У доказывающей стороны есть пара ключей (x, P), где x является приватным ключом, а P является публичным ключом. P транслируется публично, в то время как x остаётся известным только доказывающей стороне.

    Когда мы имеем дело с подписями, особенно в случае с подписями семейства Шнорра, наше обязательство строится путём выбора случайного значения нонса r с его последующей шифровкой для создания R. В частности, процесс шифрования работает путём выполнения R=r*G (mod n), где G является некоторой указанной точкой-генератором на эллиптической кривой. Допуск дискретного логарифма позволяет нам безопасно выдать R всему остальному миру, поскольку вычисление r только при известном R неосуществимо.

    Проблема состоит в некоторой случайно выбираемой скалярной величине, которая выбирается верифицирующей стороной. Мы называем её e. Верифицирующая сторона отправляет обратно доказывающей стороне e после получения от неё R.

    Наконец, после получения запроса от верифицирующей стороны доказывающая сторона берёт x, e и r и использует их как входы для функции подписи: s = r+e*x. Это и есть ответ.

    В этот момент верифицирующая сторона может проверить действительность ответа, отправив P, R, s, e (все они являются публичными параметрами) в качестве входных данных в алгоритм верификации. Алгоритм сначала берёт значение подписи, затем умножает его на точку-генератор G. После вычисления значения sG верифицирующая сторона переходит к другой стороне уравнения и вычисляет R + e*P. Если обе стороны соответствуют друг другу, верифицирующая сторона понимает, что доказывающей стороне на самом деле известен дискретный логарифм, равно как и то, что они владеют приватным ключом x и имеют право подписывать сообщение.

    2.png

    Далее мы станем называть доказывающую сторону Пегги (английское имя начинается с латинской P), а верифицирующую сторону Виктором. Даже несмотря на то, что Пегги использует r (простой текстовый нонс) и x (приватный ключ) при вычислении подписи, Виктор не сможет независимо восстановить эти переменные. В данном случае хорошей аналогией будет попытка восстановления изначальных ингредиентов пирога (яиц, молока и муки) после того, как они будут замешаны в тесто. Виктор видит только зашифрованные значения R и P (которые Пегги включила при публичной трансляции транзакции) и включает их в уравнение. Тем не менее он математически убеждён в аутентичности подписи, поскольку единственным человеком, который мог бы сбалансировать это уравнение, является тот, кто владеет секретными значениями x и r.

    Теперь, если бы Пегги смогла определить, какое значение e Виктор собирался взять заранее, она смогла бы обмануть протокол и подделать [как кажется] действительную подпись, НЕ ЗНАЯ x, и вот как она бы это сделала:

    3.png
    1. Пегги берёт случайное значение s, при этом ей на самом деле неважно, каким оно будет. Это значение s станет просто фасадом в её попытке обмануть верифицирующую сторону.
    2. Пегги известно, что в процессе верификации Виктор возьмёт подпись и умножит её на G, чтобы увидеть, сбалансировано или нет уравнение (формула снизу слева на приведённом выше графике). Поэтому она берёт своё случайное значение s, которое было получено ею на первом этапе, и умножает его на G.
    3. Имея sG, Пегги переходит к вычислению R, используя формулу, показанную справа снизу. Она может сделать это, поскольку: a) e было заранее опубликовано Виктором; b) P является публичным ключом, который может видеть каждый; c) sG было только что вычислено на втором этапе.
    4. Пегги отправляет значения (R, s) Виктору для верификации.
    Бедняга Виктор включит подпись Пегги в алгоритм верификации, и он на выходе даст ответ TRUE (ДЕЙСТВИТЕЛЬНА). Теперь, если Виктор увидит, что значения r и x попадают в конструкцию s = r + x*e, он сможет обнаружить подделку. К сожалению, если мы дадим Виктору эти секретные значения, мы потеряем всю ценность подписи, то есть отсутствие необходимости у Пегги раскрывать всему миру свой секретный приватный ключ.

    Также следует отметить, что в вышеприведённом описании, если бы у Пегги не было предварительного доступа к e, она не смогла бы вычислить R и обмануть Виктора. Почему? Да потому что протокол Шнорра, в первую очередь, буквально требует у Пегги дать обязательства по значению R (выбрав нонс r, а затем вычислив R = r*G) ПЕРЕД тем, как она получит запрос Виктора e. В мошенническом уравнении R = sG — e*P мы используем e в качестве ВВОДНОЙ переменной. Вполне разумно, что мы не можем использовать в качестве вводных данных что-то, что нам пока неизвестно, помимо случайного угадывания, какое значение e может задать Виктор заранее, и вычисления R таким вот образом. Но при используемых массовых параметрах мы можем утверждать, что шансы на то, что подобное произойдёт, настолько астрономически малы, что их можно просто игнорировать.

    Поэтому, если уравнение будет сбалансировано, мы можем утверждать одно из двух: либо Пегги известен секретный ключ x, либо Виктор упустил из внимания, что Пегги было известно значение e заранее, и позволил ей таким образом подделать подпись. Тем не менее, так как Виктор является единственным человеком, который пытается вывести это уравнение, ему будет известно, ошибся он или нет, а это означает, что мы приходим к единственному выводу — Пегги на самом деле был известен приватный ключ, и она честно создала подпись.

    Неинтерактивные варианты

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

    Во-вторых, интерактивные схемы нельзя верифицировать публично, что опять же является серьёзным препятствием для системы, построенной на основе блокчейна. Интерактивная модель работает только в том случае, если обе стороны-участники процесса готовы продемонстрировать друг другу доказательство. Тут также необходимо помнить о том, что если Пегги узнает значение e, выбранное Виктором, до реализации схемы, она сможет подделать действительную подпись, не зная приватного ключа. Но что будет, если появится ещё один проверяющий (назовём её Кэрол) и захочет самостоятельно проверить подпись Пегги? Кэрол не сможет сказать, имел или нет место сговор между Пегги и Виктором при последней проверке. Единственным способом проверить это для Кэрол и обличить Пегги является принуждение Пегги повторно пройти проверку, используя другое значение e, которое будет выбрано Кэрол. Таким образом, Пегги не сможет повторить этот трюк с появлением новых верификаторов.

    И вот тут в игру вступают неинтерактивные доказательства. Используя технику, известную как эвристический метод Фиата-Шамира, мы можем преобразовать любое интерактивное доказательство знания в неинтерактивное доказательство, где не будет этапов обмена обязательством\запросом, а будет просто осуществлён переход к построению подписи, то есть необходимость во взаимодействии с верифицирующей стороной не появится вплоть до этапа валидации. Кроме того, мы получаем второе свойство публичной верификации, когда Пегги может выдать единственную подпись, которой будет достаточно для любого проверяющего.

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

    4.png
    Задача верифицирующей стороны выполняется хеш-функцией

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

    5.png
    Произвольный перенос входов хеш-функции
    Хеш-функция даёт нам некую форму собственного временного упорядочивания. Чтобы вычислить выход хеша H(X), нам необходимо выбрать значение X до того, как мы сможем оценить H(X), то есть, если мы хотим найти e = H(5), то нам придётся выбрать значение 5 до того, как будет найдена e. Эта концепция применима к нашему протоколу и дает возможность получить необходимые нам свойства.

    В случае с неинтерактивным протоколом Шнорра вместо значения e, предоставляемого верифицирующей стороной, мы переназначаем e = H(R). Следует отметить, что в нашем новом определении мы гарантируем, что значение R будет определено до того, как будет выбрано значение e, так как хеш чего бы то ни было не может быть оценен до того, как это что-то станет известным.

    В случае с интерактивным протоколом Шнорра существуют определённые угрозы безопасности, которые нельзя использовать при применении неинтерактивной модели. Мы ранее убедились в том, что Виктор, выбирающий случайное значение e, может определить, известен Пегги дискретный логарифм или нет. Но это будет действительно так при допуске идеальной безопасности. Что если Пегги имеет доступ к аппаратному обеспечению Виктора, генерирующему случайный нонс? Или же, что если RNG Виктора не генерирует действительно случайные числа, и Пегги может заранее угадать, какое значение e будет выдано? Если дело будет обстоять так, то Пегги сможет подделать подпись, не зная приватного ключа. Виктор не узнает, что его «взломали», и будет интерпретировать недействительную подпись как действительную.

    Мы устраняем возможность таких атак из области социальной инженерии (допуская, что хеш-функция является безопасной), просто удаляя верифицирующую сторону из процесса. Построение подписи остаётся исключительно делом Пегги, и Пегги не может обмануть саму себя. Даже если она определит значение R и вычислит хеш до формирования подписи, само её обязательство по значению R будет означать, что временное упорядочение состоялось. Пегги просто не сможет получить значение e до вычисления R, если только она сначала не возьмёт какое-либо значение e, а потом задним числом случайно угадает его прообраз, что противоречит нашему определению безопасной хеш-функции.

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

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

    Источник: Ring Signatures (Part 1): Schnorr Identity Protocol

    Перевод:
    Mr. Pickles (@v1docq47)
    Редактирование:
    Agent LvM (@LvMi4)
    Коррекция:
    Kukima (@Kukima)
     
    #1 Mr. Pickles, 11 май 2019
    Последнее редактирование: 6 июн 2019
    TheFuzzStone нравится это.
  • О нас

    Наш сайт является одним из уникальных мест, где русскоязычное сообщество Monero может свободно общаться на темы, связанные с этой криптовалютой. Мы стараемся публиковать полезные мануалы и статьи (как собственные, так и переводы с английского) о криптовалюте Monero. Если вы хорошо владеете английским (или можете писать собственные статьи/мануалы) и хотите помочь в переводах и общем развитии Monero для русскоязычной аудитории - свяжитесь с одним из администраторов.