Перевод Кольцевые подписи (Часть 2): Обзор AOS

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

  1. Mr. Pickles

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

    Регистрация:
    11 сен 2017
    Сообщения:
    721
    Симпатии:
    222
    Идея кольцевых AOS-подписей работает следующим образом: каждый участник группы представлен независимой подписью Шнорра, соответствующей уникальному публичному ключу участника. Затем эти подписи объединяются в связный объект. Как работает эта связная структура? Ну, мы поправляем уравнение Шнорра, но совсем немного, добавляя префикс вызова. Всё выглядит практически так же, как и в случае со стандартной подписью Шнорра, за исключением того, что вместо использования каждым участником собственного Ri для вычисления e = H(m||R), подписант использует значение Ri участника, идущего перед ним в индексе:

    1.png
    Предпосылки

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

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

    И вот тут в игру вступают кольцевые подписи. Боб может создать подпись специальной формы, которая убедит любого верификатора в том, что он является сотрудником АНБ, но при этом не раскроет его личности. Свободное описание выглядит примерно следующим образом: Боб создаёт свою подпись и выпускает её вместе с n ложных подписей, которые он также подделывает сам. Например, Боб может взять публичные ключи других 19 сотрудников АНБ из директории и выдать 20 подписей: 1 свою и 19 фальшивых от лица своих коллег. Невероятной особенностью данной схемы является то, что реальную подпись Боба нельзя отличить от ложных. Проверяющий сможет сказать, что 1 из 20 участников группы является действительным создателем подписи, но не сможет расшифровать, кто именно.

    Построение

    В нашем примере ниже представим, что публичными ключами, которые Боб использует в качестве ложных, являются {PA, PC, PD}, принадлежащие Элис, Кэрол и Дейву, соответственно. Публичный ключ Боба PB также будет включён в список.

    Когда всё будет сделано, получится всего 4 подписи, по одной, соответствующей каждому публичному ключу в списке. Эти подписи могут быть разделены на две группы: поддельные и действительные. Под действительной мы понимаем подпись, созданную со знанием приватного ключа: s = r + e*x. Только подпись Боба будет действительной, поскольку xB является единственным приватным ключом, к которому у него есть доступ. Порядок операций при создании кольцевой подписи варьируется в зависимости от классификации, под которую она попадает.

    Давайте начнём процедуру. Первое, что делает Боб, он выбирает для себя случайный нонс rB. Он зашифровывает rB путём вычисления RB = rB*G. В случае с нормальной подписью Шнорра Боб закончил бы создание подписи вычислением eB = H(m||RB), а затем запустил бы sB = rB + eB*xB. Но в случае с кольцевыми подписями протокол диктует необходимость в использовании некоторых «данных заполнения» (filler data), которые растягивают подпись Боба. Как, возможно, вы уже догадались, этими «данными заполнения» являются подделанные подписи Кэрол, Дейва и Элис. Эти ложные подписи никак не влияют на изначальную способность подписанта создавать действительную подпись, но они обеспечивают сохранение анонимности, так как действительная подпись криптографически неотличима от ложных, что позволяет её создателю «затеряться в толпе».

    2.png

    Помните, как в Части 1 я описал, как доказывающая сторона могла бы убедить верификатора в том, что поддельная подпись является аутентичной, если бы она смогла заполучить вызов верификатора заранее? Это в значительной степени именно то, что мы делаем с ложными подписями. Вместо того чтобы сначала вычислить r и R для ложных подписей, мы предварительно заполучаем значение e, берём любое случайное значение s, а затем возвращаем значение R, которое выглядит действительным с точки зрения проверяющего, но не было создано с использованием приватного ключа.

    Вы можете задаться вопросом, как мы получаем e до R? Не препятствует ли этому хеш?

    Ну, в этом и состоит поправка в протоколе AOS. Ведь вместо того чтобы каждый участник использовал собственное значение R при вычислении e = H(m||R), подписант использует значение R участника, который предшествует ему в индексе. Боб уже создал своё R на первом этапе, поэтому в индексе Кэрол будет использоваться именно это значение для вычисления eC.

    3.png
    Почему на графике выше поставлен знак вопроса? Когда мы создаём подделку, мы видим только точку R на публичной кривой, но не соответствующую ей скалярную величину r. Существует некоторая r, где r = r*G, но мы не можем восстановить её из-за допуска дискретного логарифмирования.

    Теперь, когда мы вычислили eC, нам необходимо сгенерировать значение sC для Кэрол. У Боба нет доступа к приватному ключу Кэрол, поэтому создание действительной подписи sC = rC + eC*xC выпадает из общей картины. Вместо этого нам необходимо выбрать случайное число для sC, а затем просто вернуть RC, чтобы сбалансировать уравнение. Алгебраическое доказательство, стоящее за этим математическим решением, выглядит следующим образом:

    4.png

    Таким образом, чтобы Боб мог подделать RC для Кэрол, ему необходимы:
    • случайное значение sC;
    • eC (вызов);
    • PC (публичный ключ Кэрол).
    У него есть всё это, поэтому он может смело начинать!

    Мы можем продолжить эту итерацию для остальных ложных участников. Боб может подделать часть Дейва eD = H(RC||m), опять же, используя значение RC предыдущего участника кольца, для которого мы только что нашли решение (Кэрол). Затем он выберет случайное значение sD. После этого, используя наше изменённое уравнение, Боб вернёт RD = sD*G – eD*PD. Это будет продолжаться до тех пор, пока этот цикл не пройдут все участники группы и всё снова не замкнётся на Бобе.

    5.png

    Когда мы вернёмся к Бобу, нам будет необходимо решить eB = H(RA||m)... и тут мы отметим нечто новое. На последнем этапе выбирается значение sB для Боба, чтобы окончательно замкнуть кольцо. Но в случае с Бобом процедура будет отличаться. С Кэрол, Элис и Дейвом для s мы выбираем любое случайное значение и просто возвращаем R, чтобы сбалансировать уравнение. Это работало, поскольку R и s были «неограниченными», то есть отсутствовал фактор непредвиденных обстоятельств (не было дискретного логарифмирования), связывающий эти значения.

    6.png
    Замки означают «обязательные» элементы. Выберите любое случайное значение s и вы легко вычислите R.

    В ситуации с Бобом разница состоит в том, что мы более не сталкиваемся со сценарием, при котором как R, так и s являются неограниченными. Не ограничено только значение s, поскольку на первом этапе протокола нами уже было выбрано значение RB для Боба! Это означает, что Боб не может взять любое случайное значение sB и вернуть RB, чтобы всё сбалансировать. Скорее, его значение sB должно быть определённым — дискретный логарифм RB. Но пытаться найти решение для r, имея только заданное значение R, это всё равно что пытаться восстановить приватный ключ, зная только публичный ключ, а это... невозможно!

    7.png

    Как видите, нет ничего подобного. Если RB уже является обязательным значением, то нам нужно вполне определённое значение sB, чтобы уравнение было сбалансировано. И когда мы включаем последнюю часть уравнения, e*P, это определённое значение sB можно будет сгенерировать только в том случае, если человеку известны сразу как скрытый нонс r, так и приватный ключ x.

    8.png

    Если Бобу известны эти секретные элементы r и s, он сможет создать определённое значение sB для Элис и сбалансировать уравнение, замкнув тем самым кольцо и «вернувшись» к самому себе. Как будет видно в процессе валидации ниже, верификатор, проводящий вычисления, не сможет выделить аутентичную подпись среди её поддельных частей. Тем не менее, если все подписи симметрично аутентифицируются, то это означает, что кому-то в группе известен приватный ключ, и он имел право на составление подписи.

    Публикация

    Нами были вычислены 3 значения для каждого члена кольца: R, e и s. Подписи для каждого участника публикуются в виде последовательности (s1, e1)..., в которую R может и не входить, так как это значение будет вычислено с клиентской стороны верификатором.

    Боб опубликует полную подпись в виде кольца (sA, sB, sC, sD, eA, eB, eC, eD)... всего 8 32-байтовых значений. Однако из-за особенности связывания Бобу будет необходимо опубликовать только одно случайно выбранное значение e из группы. Это позволяет нам сэкономить место и сокращает количество 32-байтовых значений до 5. Допуская, что Боб случайным образом выберет значение Дейва eD, опубликованная подпись будет выглядеть как (sA, sB, sC, sD, eD).

    Валидация

    Проверяющий получает последовательность (sA, sB, sC, sD, eD) и «раскручивает» кольцо, проверяя подписи одну за одной, начиная с участника, указанного в индексе, значение e которого было включено (в нашем примере это Дейв). Используя значения sD и eD, вычисляется значение RD Дейва: RD = sD*G – eD*PD.

    Теперь мы можем использовать это значение RD в качестве вводного для получения значения eA = H(m||RD) Элис. При наличии вычисленного значения eA мы снова можем выполнить RA = sA*G – eA*PA, чтобы вывести значение R Элис, и итерационно повторяем этот цикл для всех остальных участников группы. Когда мы, наконец, доходим до последнего участника, Кэрол, мы решаем для него уравнение RC = sC*G – eC*PC. Затем мы используем это значение RC в качестве вводного в функции eD = H(m||RC) и сравниваем результат со значением eD, которое было включено в оригинальную последовательность (sA, sB, sC, sD, eD). Если эти значения соответствуют друг-другу, то подпись успешно проходит валидацию! И это является для проверяющего доказательством того, что один из индексов создал подпись, используя приватный ключ, иначе бы значения eD не совпадали.

    9.png

    Хеш-функции хамелеоны

    Перейдём к другому примеру. Предположим, Энди создаёт кольцевую подпись. В своё кольцо он включает 3 других участников: Билли, Кэтрин и Дена.

    Как уже было описано нами ранее, при построении кольца Энди должен вычислить вызов e для каждого участника как ei = H(Ri-1). И поскольку нам известно, что R = sG – eP, эта формула также может быть переписана как e = H(m||s*G – ei-1*P).

    Для простоты я запишу это последнее уравнение e = H(m||s*G – ei-1*P) как:

    9_1.png

    «c» легко вычисляется для каждого участника кольца, кроме его создателя. Почему? Потому что при вычислении c = H(m||sG – eP) для индекса Энди значение «e» Дена не было создано. Это проблема «курицы и яйца»; Энди не может решить хеш-функцию, включающую в себя элемент, который пока ему не известен.

    Более того, нам необходимо сделать так, чтобы казалось, что значение «c» Энди было выведено из значения Дена, несмотря на тот факт, что мы не используем ничего, взятого у Дена, чтобы сгенерировать значение R Энди. В противном случае проверяющий сможет выделить его в качестве создателя группы.

    Может показаться, что невозможно решить эту задачу, но есть обходной путь. Решение предполагает использование ассоциативных свойств точек эллиптической кривой с целью реорганизации нашего уравнения Шнорра и «перемотки времени» в процессе путём небольшого изменения различных компонентов хеш-функции после того, как мы узнаем критическую информацию (то есть значение e Дена) на последующих этапах протокола. Такое гармоничное решение позволяет нам замкнуть кольцо и скрыть личность создателя. Чтобы понять общую идею, стоящую за концепцией, рассмотрим следующий пример:

    Допустим, что H(100) = ad5736

    H(100) «упорядочено по времени», то есть вводное значение не может быть изменено после того, как комбинация будет вычислена. Если кто-то изменит 100 на 101 после этого, верификатор просто поймёт, что оригинальное вводное значение было искажено, поскольку оно больше не будет хешироваться с тем же выходящим значением.

    Но что, если мы хешируем уравнение с множеством переменных, как это показано в примере ниже?

    10.png

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


    Процесс

    Так как R = rG, а rG = sG – eP, мы можем использовать ассоциативные свойства точек эллиптической кривой, чтобы переписать наше уравнение следующим образом:

    11.png

    Сфокусируемся на двух последних уравнениях. Поскольку Энди известно значение «r», то ему также известно и значение R, и он может хешировать R, чтобы «мельком взглянуть» на ответ... Энди фактически может увидеть ответ к Уравнению №1, несмотря на то, что ему ещё не известно значение Дена. И только позже, ближе к концу протокола, он откроет это значение, после того как будут созданы ложные подписи для Билли и Кэтрин.


    Когда Энди, наконец, вычислит значение «e» Дена, всё, что ему будет необходимо сделать — вбросить значение s для Дена и замкнуть цикл. Но тут есть одна уловка: если Энди возьмёт случайное значение s, как он делал это в случае с Билли и Кэтрин, то значение «c», найденное при помощи Уравнения №1, НЕ БУДЕТ соответствовать тому же значению «e», полученному при помощи Уравнения №3. Это бы означало, что индекс Дена не «закольцуется» на Энди, указав на Энди как на создателя кольца.

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

    12.png

    Прелесть состоит в том, что любой проверяющий кольца не сможет выяснить, был ли индекс любого из участников (Энди, Билли, Кэтрин или Дена) создан способом, при котором r и x были известны, что позволяет создателю увидеть «c» заранее и построить определённое значение s, которое бы сбалансировало уравнение, или же r и x были неизвестны, и значение c было вычислено просто как c = H(m||sG – eP).


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

    Заключение

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

    Следует отметить, что описанные нами схемы несовместимы с настройками блокчейна, поскольку в них отсутствует связываемость. В случае с AOS Боб может накопить случайные публичные ключи и построить кольцо, чтобы отправить анонимное сообщение. В денежном протоколе, таком как Bitcoin, сообщение представляет собой транзакцию, позволяющую отправить определённые UTXO, поэтому в данном случае императивом является то, что Боб не должен быть в состоянии отправить одно и то же сообщение дважды разными кольцами и дважды потратить одни и те же средства. Во второй части этой серии мы коснёмся согласованных подписей, таких как LSAG и MLSAG (в настоящее время используются Monero), которые обладают такими свойствами связываемости.

    Источник: Ring Signatures (Part 2): AOS Rings

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

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