Схема обязательств

Криптографическая схема

Схема обязательств — это криптографический примитив , который позволяет брать на себя обязательство по выбранному значению (или выбранному утверждению), сохраняя его скрытым от других, с возможностью раскрыть принятое значение позже. ^[1] Схемы обязательств разработаны таким образом, что сторона не может изменить значение или утверждение после того, как она приняла на себя обязательство: то есть схемы обязательств являются обязательными . Схемы обязательств имеют важные приложения в ряде криптографических протоколов, включая безопасное подбрасывание монеты, доказательства с нулевым разглашением и безопасные вычисления .

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

Взаимодействие в схеме обязательств происходит в два этапа:

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

В приведенной выше метафоре фаза обязательства — отправитель кладет сообщение в коробку и запирает ее. Фаза раскрытия — отправитель дает ключ получателю, который использует его, чтобы открыть коробку и проверить ее содержимое. Запертая коробка — это обязательство, а ключ — доказательство.

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

Концепция схем обязательств, возможно, была впервые формализована Жилем Брассаром , Дэвидом Шомом и Клодом Крепо в 1988 году ^[2] как часть различных протоколов с нулевым разглашением для NP , основанных на различных типах схем обязательств. ^{[3] [4]} Но эта концепция использовалась и до этого, не будучи формально рассмотренной. ^{[5] [6]} Понятие обязательств впервые появилось в работах Мануэля Блюма ^[7] , Шимона Эвена [ ^8] и Ади Шамира и др. ^[9] Терминология, по-видимому, была создана Блюмом ^[6], хотя схемы обязательств можно взаимозаменяемо называть схемами битовых обязательств — иногда зарезервированными для особого случая, когда зафиксированное значение равно биту . До этого рассматривалось обязательство через односторонние хэш-функции, например, как часть, скажем, подписи Лампорта , оригинальной одноразовой однобитовой схемы подписи.

Приложения

Подбрасывание монеты

Предположим, что Алиса и Боб хотят разрешить спор с помощью подбрасывания монеты . Если они физически находятся в одном месте, типичная процедура может быть такой:

1. Алиса «вызывает» подбрасывание монеты,
2. Боб подбрасывает монетку,
3. Если ответ Алисы правильный, она выигрывает, в противном случае выигрывает Боб.

Если Алиса и Боб не находятся в одном и том же месте, возникает проблема. Как только Алиса «вызвала» подбрасывание монеты, Боб может оговорить «результаты» подбрасывания, которые будут наиболее желательными для него. Аналогично, если Алиса не объявляет свой «вызов» Бобу, после того, как Боб подбрасывает монету и объявляет результат, Алиса может сообщить, что она назвала тот результат, который наиболее желателен для нее. Алиса и Боб могут использовать обязательства в процедуре, которая позволит обоим доверять результату:

1. Алиса «выбирает» подбрасывание монеты, но только сообщает Бобу о своей готовности сделать ставку,
2. Боб подбрасывает монетку и сообщает результат,
3. Элис раскрывает, к чему она стремилась,
4. Боб проверяет, соответствует ли звонок Алисы ее обязательству,
5. Если ответ Алисы совпадает с результатом подсчета монеты, который сообщил Боб, Алиса выигрывает.

Чтобы Боб мог исказить результаты в свою пользу, он должен быть в состоянии понять вызов, скрытый в обязательстве Алисы. Если схема обязательств хороша, Боб не может исказить результаты. Аналогично, Алиса не может повлиять на результат, если она не может изменить значение, которое она обязуется.

Реальное применение этой проблемы существует, когда люди (часто в СМИ) обязуются принять решение или дать ответ в «запечатанном конверте», который затем вскрывается позже. «Давайте выясним, так ли ответил кандидат», например, в игровом шоу, может служить моделью этой системы.

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

Одним из конкретных мотивирующих примеров является использование схем обязательств в доказательствах с нулевым разглашением . Обязательства используются в доказательствах с нулевым разглашением для двух основных целей: во-первых, чтобы позволить доказывающему участвовать в доказательствах «вырезать и выбрать», где проверяющему будет предоставлен выбор того, что изучать, и доказывающий раскроет только то, что соответствует выбору проверяющего. Схемы обязательств позволяют доказывающему заранее указать всю информацию и раскрыть только то, что должно быть раскрыто позже в доказательстве. ^[10] Во-вторых, обязательства также используются в доказательствах с нулевым разглашением проверяющим, который часто заранее указывает свой выбор в обязательстве. Это позволяет составлять доказательства с нулевым разглашением параллельно, не раскрывая дополнительную информацию доказывающему. ^[11]

Схемы подписи

Схема подписи Лампорта — это система цифровой подписи , которая основана на поддержании двух наборов секретных пакетов данных , публикации проверяемых хэшей пакетов данных, а затем выборочном раскрытии частичных секретных пакетов данных способом, который соответствует конкретно подписываемым данным. Таким образом, предварительное публичное обязательство по секретным значениям становится важнейшей частью функционирования системы.

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

Проверяемый обмен секретами

Другое важное применение обязательств — проверяемое разделение секрета , критически важный строительный блок безопасных многосторонних вычислений . В схеме разделения секрета каждая из нескольких сторон получает «доли» значения, которое должно быть скрыто от всех. Если достаточно сторон соберется вместе, их доли могут быть использованы для восстановления секрета, но даже злонамеренная группа недостаточного размера не должна ничего узнать. Разделение секрета лежит в основе многих протоколов для безопасных вычислений : чтобы безопасно вычислить функцию некоторых общих входных данных, вместо этого манипулируют секретными долями. Однако, если доли должны быть сгенерированы злонамеренными сторонами, может быть важно, чтобы эти доли могли быть проверены на корректность. В проверяемой схеме разделения секрета распределение секрета сопровождается обязательствами по отдельным долям. Обязательства не раскрывают ничего, что могло бы помочь нечестной группе, но доли позволяют каждой отдельной стороне проверить, являются ли их доли правильными. ^[12]

Определение безопасности

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

Если обязательство C по отношению к значению x вычисляется как C:=Commit(x,open) , где open — случайность, используемая для вычисления обязательства, то CheckReveal (C,x,open) сводится к простой проверке уравнения C=Commit (x,open) .

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

Вычислительная привязка

Пусть open выбирается из набора размера , т. е. его можно представить в виде строки из k бит, и пусть будет соответствующей схемой обязательств. Поскольку размер k определяет безопасность схемы обязательств, он называется параметром безопасности . ${\displaystyle 2^{k}}$ ${\displaystyle {\text{Commit}}_{k}}$

Тогда для всех неравномерных вероятностных полиномиальных алгоритмов , которые выводят и увеличивающейся длины k , вероятность того, что и является пренебрежимо малой функцией от k . ${\displaystyle x,x'}$ ${\displaystyle open,open'}$ ${\displaystyle x\neq x'}$ ${\displaystyle {\text{Commit}}_{k}(x,open)={\text{Commit}}_{k}(x',open')}$

Это форма асимптотического анализа . Также можно сформулировать то же самое требование, используя конкретную безопасность : Схема обязательств Commit является безопасной, если для всех алгоритмов, которые выполняются за время t и выводят вероятность того, что и не превышает . ${\displaystyle (t,\epsilon )}$ ${\displaystyle x,x',open,open'}$ ${\displaystyle x\neq x'}$ ${\displaystyle {\text{Commit}}(x,open)={\text{Commit}}(x',open')}$ ${\displaystyle \epsilon }$

Идеальное, статистическое и вычислительное сокрытие

Пусть будет равномерным распределением по начальным значениям параметра безопасности k . Схема обязательств является соответственно совершенным, статистическим или вычислительно скрытым, если для всех вероятностных ансамблей и равны, статистически близки или вычислительно неразличимы . ${\displaystyle U_{k}}$ ${\displaystyle 2^{k}}$ ${\displaystyle x\neq x'}$ ${\displaystyle \{{\text{Commit}}_{k}(x,U_{k})\}_{k\in \mathbb {N} }}$ ${\displaystyle \{{\text{Commit}}_{k}(x',U_{k})\}_{k\in \mathbb {N} }}$

Невозможность создания универсально скомпонованных схем обязательств

Невозможно реализовать схемы обязательств в рамках универсальной компоновки (UC). Причина в том, что обязательство UC должно быть извлекаемым , как показано Канетти и Фишлином ^[13] и объяснено ниже.

Идеальная функциональность обязательства, обозначенная здесь как F , работает примерно следующим образом. Коммиттер C отправляет значение m в F , который сохраняет его и отправляет «квитанцию» получателю R. Позже C отправляет «открыть» в F , который отправляет m в R.

Теперь предположим, что у нас есть протокол π , реализующий эту функциональность. Предположим, что коммиттер C поврежден. В фреймворке UC это по сути означает, что C теперь контролируется средой, которая пытается отличить выполнение протокола от идеального процесса. Рассмотрим среду, которая выбирает сообщение m , а затем говорит C действовать так, как предписано π , как если бы она приняла обязательство m . Обратите внимание, что для реализации F получатель должен после получения обязательства вывести сообщение «квитанция». После того, как среда видит это сообщение, она говорит C открыть обязательство.

Протокол безопасен только в том случае, если этот сценарий неотличим от идеального случая, когда функциональность взаимодействует с симулятором S. Здесь S контролирует C. В частности, всякий раз, когда R выводит «квитанцию», F должен сделать то же самое. Единственный способ сделать это — сказать S C отправить значение в F. Однако следует отметить, что к этому моменту m не известно S. Следовательно, когда обязательство открывается во время выполнения протокола, маловероятно, что F откроется в m , если только S не сможет извлечь m из сообщений, полученных из среды, до того, как R выведет квитанцию.

Однако протокол, который извлекаем в этом смысле, не может быть статистически скрытым. Предположим, что такой симулятор S существует. Теперь рассмотрим среду, которая вместо того, чтобы портить C , портит R. Кроме того, она запускает копию S. Сообщения , полученные от C , подаются в S , а ответы от S пересылаются в C.

Среда изначально говорит C принять сообщение m . В какой-то момент взаимодействия S примет значение m′ . Это сообщение передается R , который выводит m′ . Обратите внимание, что по предположению мы имеем m' = m с высокой вероятностью. Теперь в идеальном процессе симулятор должен придумать m . Но это невозможно, потому что в этот момент обязательство еще не открыто, поэтому единственное сообщение, которое R может получить в идеальном процессе, — это сообщение «получение». Таким образом, у нас есть противоречие.

Строительство

Схема обязательств может быть либо совершенно обязательной (Алиса не может изменить свое обязательство после того, как она его приняла, даже если у нее неограниченные вычислительные ресурсы); либо совершенно скрывающей (Боб не может узнать обязательство без того, чтобы Алиса его не раскрыла, даже если у него неограниченные вычислительные ресурсы); либо сформулированной как зависящая от экземпляра схема обязательств, которая либо скрывает, либо связывает в зависимости от решения другой проблемы. ^{[14] [15]} Схема обязательств не может быть одновременно и совершенно скрывающей, и совершенно связывающей.

Обязательство по битам в модели случайного оракула

Схемы бит-коммитинга тривиально построить в модели случайного оракула . ​​Учитывая хэш-функцию H с выходом 3k бит , для фиксации k -битного сообщения m Алиса генерирует случайную k- битную строку R и отправляет Бобу H( R || m ). Вероятность того, что существуют любые R′ , m′ , где m′ ≠ m такие, что H( R′ || m′ ) = H( R || m ), составляет ≈ 2 ^{− k} , но для проверки любой догадки о сообщении m Бобу потребуется сделать 2k ⁽ для неправильной догадки) или 2k ^{-1 (} в среднем, для правильной догадки) запросов к случайному оракулу. ^[16] Отметим, что более ранние схемы, основанные на хэш-функциях, по сути, можно рассматривать как схемы, основанные на идеализации этих хэш-функций как случайного оракула.

Бит-обязательство из любой односторонней перестановки

Можно создать схему бит-обязательства из любой односторонней функции , которая является инъективной . Схема основана на том факте, что каждая односторонняя функция может быть модифицирована (через теорему Голдрайха-Левина ) так, чтобы обладать вычислительно жестким предикатом (сохраняя при этом свойство инъективности).

Пусть f будет инъективной односторонней функцией, а h — хардкорным предикатом. Тогда для фиксации бита b Алиса выбирает случайный вход x и отправляет тройку

${\displaystyle (h,f(x),b\oplus h(x))}$

Бобу, где обозначает XOR, т. е . побитовое сложение по модулю 2. Чтобы раскоммитить, Алиса просто отправляет x Бобу. Боб проверяет, вычисляя f ( x ) и сравнивая с зафиксированным значением. Эта схема является скрывающей, потому что для того, чтобы Боб восстановил b, он должен восстановить h ( x ). Поскольку h является вычислительно сложным предикатом, восстановление h ( x ) из f ( x ) с вероятностью, большей половины, так же сложно, как и инвертирование f . Совершенное связывание следует из того факта, что f инъективно, и, таким образом, f ( x ) имеет ровно один прообраз. ${\displaystyle \oplus }$

Бит-коммитмент от псевдослучайного генератора

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

В 1991 году Мони Наор показал, как создать схему бит-коммита из криптографически безопасного генератора псевдослучайных чисел . ^[17] Конструкция выглядит следующим образом. Если G — псевдослучайный генератор, такой, что G преобразует n бит в 3 n бит, то если Алиса хочет передать бит b :

• Боб выбирает случайный 3 n -битный вектор R и отправляет R Алисе.
• Алиса выбирает случайный n- битный вектор Y и вычисляет 3 n- битный вектор G ( Y ).
• Если b = 1, Алиса отправляет G ( Y ) Бобу, в противном случае она отправляет побитовое исключающее ИЛИ G ( Y ) и R Бобу.

Чтобы отменить фиксацию, Алиса отправляет Y Бобу, который затем может проверить, получил ли он изначально G ( Y ) или G ( Y ) R . ${\displaystyle \oplus }$

Эта схема статистически связывающая, что означает, что даже если Алиса вычислительно неограничена, она не может обмануть с вероятностью, большей, чем 2 ^{− n} . Чтобы Алиса обманула, ей нужно найти Y' , такой, что G ( Y' ) = G ( Y ) R . Если бы она могла найти такое значение, она могла бы декоммитировать, отправив правду и Y , или отправить противоположный ответ и Y' . Однако G ( Y ) и G ( Y' ) могут производить только 2 ⁿ возможных значений каждый (то есть 2 ^{2 n} ), в то время как R выбирается из 2 ^{3 n} значений. Она не выбирает R , поэтому существует вероятность 2 ^{2 n} /2 ^{3 n} = 2 ^{− n} , что Y' удовлетворяет уравнению, необходимому для обмана. ${\displaystyle \oplus }$

Свойство сокрытия следует из стандартного сокращения: если Боб может сказать , приняла ли Алиса ноль или единицу, он также может отличить выход псевдослучайного генератора G от истинно случайного, что противоречит криптографической безопасности G.

Идеально связывающая схема, основанная на задаче дискретного логарифма и не только

Алиса выбирает кольцо простого порядка p с мультипликативным генератором g .

Алиса случайным образом выбирает секретное значение x от 0 до p  − 1 для фиксации и вычисляет c = g ^x и публикует c . Задача дискретного логарифма диктует, что из c вычислительно невозможно вычислить x , поэтому при этом предположении Боб не может вычислить x . С другой стороны, Алиса не может вычислить a x ′ <> x , так что g ^{x ′} = c , поэтому схема является обязательной.

Эта схема не идеально скрывает, так как кто-то может обнаружить обязательство, если ему удастся решить задачу дискретного логарифма . Фактически, эта схема вообще не скрывает по отношению к стандартной игре в сокрытие, где противник не должен иметь возможности угадать, какое из двух выбранных им сообщений было передано — аналогично игре IND-CPA . Одним из следствий этого является то, что если пространство возможных значений x невелико, то злоумышленник может просто попробовать их все, и обязательство не будет скрыто.

Лучшим примером схемы идеально связывающего обязательства является тот, где обязательство представляет собой шифрование x в соответствии с семантически безопасной схемой шифрования с открытым ключом с идеальной полнотой, а декоммитирование представляет собой строку случайных битов, используемых для шифрования x . Примером схемы теоретически скрывающего информацию обязательства является схема обязательства Педерсена, ^[18] которая вычислительно связывает в соответствии с предположением дискретного логарифма. ^[19] В дополнение к схеме выше, она использует другой генератор h простой группы и случайное число r . Обязательство устанавливается . ^[20] ${\displaystyle c=g^{x}h^{r}}$

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

Идеально скрываемая схема обязательств, основанная на RSA

Алиса выбирает так, что , где и — большие секретные простые числа. Кроме того, она выбирает простое число, такое что и . Затем Алиса вычисляет публичное число как элемент максимального порядка в группе. ^[22] Наконец, Алиса подтверждает свой секрет , сначала генерируя случайное число из , а затем вычисляя . ${\displaystyle N}$ ${\displaystyle N=p\cdot q}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle e}$ ${\displaystyle e>N^{2}}$ ${\displaystyle gcd(e,\phi (N^{2}))=1}$ ${\displaystyle g_{m}}$ ${\displaystyle \mathbb {Z} _{N^{2}}^{*}}$ ${\displaystyle m}$ ${\displaystyle r}$ ${\displaystyle \mathbb {Z} _{N^{2}}^{*}}$ ${\displaystyle c=m^{e}g_{m}^{r}}$

Безопасность вышеуказанного обязательства основана на сложности проблемы RSA и имеет идеальное сокрытие и вычислительную привязку. ^[23]

Аддитивные и мультипликативные гомоморфные свойства обязательств

Схема обязательств Педерсена вводит интересное гомоморфное свойство, которое позволяет выполнять сложение между двумя обязательствами. Более конкретно, учитывая два сообщения и и случайность и , соответственно, можно сгенерировать новое обязательство, такое что: . Формально: ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$ ${\displaystyle r_{1}}$ ${\displaystyle r_{2}}$ ${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}+m_{2},r_{1}+r_{2})}$

${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=g^{m_{1}}h^{r_{1}}\cdot g^{m_{2}}h^{r_{2}}=g^{m_{1}+m_{2}}h^{r_{1}+r_{2}}=C(m_{1}+m_{2},r_{1}+r_{2})}$

Чтобы раскрыть вышеуказанное обязательство Педерсена для нового сообщения , необходимо добавить случайность и . ${\displaystyle m_{1}+m_{2}}$ ${\displaystyle r_{1}}$ ${\displaystyle r_{2}}$

Аналогично, упомянутое выше обязательство на основе RSA имеет гомоморфное свойство относительно операции умножения. При наличии двух сообщений и со случайностью и , соответственно, можно вычислить: . Формально: . ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$ ${\displaystyle r_{1}}$ ${\displaystyle r_{2}}$ ${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}\cdot m_{2},r_{1}+r_{2})}$ ${\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=m_{1}^{e}g_{m}^{r_{1}}\cdot m_{2}^{e}g_{m}^{r_{2}}=(m_{1}\cdot m_{2})^{e}g_{m}^{r_{1}+r_{2}}=C(m_{1}\cdot m_{2},r_{1}+r_{2})}$

Чтобы открыть вышеуказанное обязательство для нового сообщения , необходимо добавить случайность и . Это вновь созданное обязательство распространяется аналогично новому обязательству для . ${\displaystyle m_{1}\cdot m_{2}}$ ${\displaystyle r_{1}}$ ${\displaystyle r_{2}}$ ${\displaystyle m_{1}\cdot m_{2}}$

Частичное раскрытие

Некоторые схемы обязательств позволяют предоставить доказательство только части обязательственного значения. В этих схемах секретное значение представляет собой вектор многих индивидуально разделяемых значений. ${\displaystyle X}$

${\displaystyle X=(x_{1},x_{2},...,x_{n})}$

Обязательство вычисляется из в фазе подтверждения. Обычно, в фазе раскрытия, доказывающий раскрывает все и некоторые дополнительные данные доказательства (например, в простом битовом обязательстве). Вместо этого доказывающий может раскрыть любое отдельное значение из вектора и создать эффективное доказательство того, что это подлинный элемент th исходного вектора, который создал обязательство . Доказательство не требует никаких значений, кроме как быть раскрытыми, и невозможно создать действительные доказательства, которые раскрывают другие значения для любого из , кроме истинного. ^[24] ${\displaystyle C}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle i}$ ${\displaystyle C}$ ${\displaystyle X}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}}$

Вектор хеширования

Вектор хеширования является наивной векторной схемой частичного раскрытия обязательств, основанной на бит-обязательстве. Значения выбираются случайным образом. Отдельные обязательства создаются путем хеширования . Общее обязательство вычисляется как ${\displaystyle m_{1},m_{2},...m_{n}}$ ${\displaystyle y_{1}=H(x_{1}||m_{1}),y_{2}=H(x_{2}||m_{2}),...}$

${\displaystyle C=H(y_{1}||y_{2}||...||y_{n})}$

Чтобы доказать один элемент вектора , доказывающий раскрывает значения ${\displaystyle X}$

${\displaystyle (i,y_{1},y_{2},...,y_{i-1},x_{i},m_{i},y_{i+1},...,y_{n})}$

Проверяющий может вычислить из и , а затем может проверить, что хэш всех значений является обязательством . К сожалению, доказательство находится в размере и времени проверки. С другой стороны, если есть набор всех значений, то обязательство находится в размере, а доказательство находится в размере и времени проверки. В любом случае, обязательство или доказательство масштабируется с , что не является оптимальным. ${\displaystyle y_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle m_{i}}$ ${\displaystyle y}$ ${\displaystyle C}$ ${\displaystyle O(n)}$ ${\displaystyle C}$ ${\displaystyle y}$ ${\displaystyle O(n)}$ ${\displaystyle O(1)}$ ${\displaystyle O(n)}$

дерево Меркла

Распространенным примером практической схемы частичного раскрытия является дерево Меркла , в котором создается двоичное хэш-дерево из элементов . Эта схема создает обязательства, которые имеют размер, и доказательства, которые имеют размер и время проверки. Корневой хэш дерева является обязательством . Чтобы доказать, что раскрытое является частью исходного дерева, только значения хэша из дерева, по одному с каждого уровня, должны быть раскрыты в качестве доказательства. Проверяющий может проследить путь от заявленного листового узла до корня, хэшируя родственные узлы на каждом уровне и в конечном итоге достигая значения корневого узла, которое должно быть равно . ^[25] ${\displaystyle X}$ ${\displaystyle O(1)}$ ${\displaystyle O(\log _{2}{n})}$ ${\displaystyle C}$ ${\displaystyle x_{i}}$ ${\displaystyle \log _{2}{n}}$ ${\displaystyle C}$

Обязательства КЗГ

Обязательство Кейт-Заверуча-Голдберг использует криптографию на основе пар для построения схемы частичного раскрытия с размерами обязательств, размерами доказательств и временем проверки доказательств. Другими словами, по мере того, как , количество значений в , увеличивается, обязательства и доказательства не становятся больше, и доказательства не требуют дополнительных усилий для проверки. ${\displaystyle O(1)}$ ${\displaystyle n}$ ${\displaystyle X}$

Обязательство KZG требует предопределенного набора параметров для создания пары и доверенного элемента-ловушки. Например, можно использовать пару Тейта . Предположим, что — аддитивные группы, а — мультипликативная группа пары. Другими словами, пара — это отображение . Пусть — элемент-ловушка (если — простой порядок и ), и пусть и — генераторы и соответственно. В рамках настройки параметров мы предполагаем, что и — известные и общие значения для произвольного числа положительных целочисленных значений , в то время как само значение-ловушка отбрасывается и никому не известно. ${\displaystyle \mathbb {G} _{1},\mathbb {G} _{2}}$ ${\displaystyle \mathbb {G} _{T}}$ ${\displaystyle e:\mathbb {G} _{1}\times \mathbb {G} _{2}\rightarrow \mathbb {G} _{T}}$ ${\displaystyle t\in \mathbb {F} _{p}}$ ${\displaystyle p}$ ${\displaystyle \mathbb {G} _{1}}$ ${\displaystyle \mathbb {G} _{2}}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle \mathbb {G} _{1}}$ ${\displaystyle \mathbb {G} _{2}}$ ${\displaystyle G\cdot t^{i}}$ ${\displaystyle H\cdot t^{i}}$ ${\displaystyle i}$ ${\displaystyle t}$

Совершить

Обязательство KZG переформулирует вектор значений, которые должны быть приняты, как полином. Сначала мы вычисляем полином таким образом, что для всех значений в нашем векторе. Интерполяция Лагранжа позволяет нам вычислить этот полином ${\displaystyle p(i)=x_{i}}$ ${\displaystyle x_{i}}$

${\displaystyle p(x)=\sum _{i=0}^{n-1}x_{i}\prod _{0\leq j<n,j\neq i}{\frac {x-j}{i-j}}}$

В этой формулировке полином теперь кодирует вектор, где . Пусть будут коэффициентами , такими, что . Обязательство вычисляется как ${\displaystyle p(0)=x_{0},p(1)=x_{1},...}$ ${\displaystyle p_{0},p_{1},...,p_{n-1}}$ ${\displaystyle p}$ ${\textstyle p(x)=\sum _{i=0}^{n-1}p_{i}x^{i}}$

${\displaystyle C=\sum _{i=0}^{n-1}p_{i}Gt^{i}}$

Это вычисляется просто как скалярное произведение между предопределенными значениями и коэффициентами полинома . Поскольку является аддитивной группой с ассоциативностью и коммутативностью, равно просто , поскольку все сложения и умножения с могут быть распределены вне оценки. Поскольку значение ловушки неизвестно, обязательство по сути является полиномом, оцененным по числу, неизвестному никому, с результатом, замаскированным в непрозрачный элемент . ${\displaystyle G\cdot t^{i}}$ ${\displaystyle p_{i}}$ ${\displaystyle \mathbb {G} _{1}}$ ${\displaystyle C}$ ${\displaystyle G\cdot p(t)}$ ${\displaystyle G}$ ${\displaystyle t}$ ${\displaystyle C}$ ${\displaystyle \mathbb {G} _{1}}$

Раскрывать

Доказательство KZG должно продемонстрировать, что выявленные данные являются подлинным значением, когда было вычислено. Пусть , выявленное значение, которое мы должны доказать. Поскольку вектор был переформулирован в многочлен, нам действительно нужно доказать, что многочлен , будучи оцененным в , принимает значение . Проще говоря, нам просто нужно доказать, что . Мы сделаем это, продемонстрировав, что вычитание из дает корень в . Определим многочлен как ${\displaystyle x_{i}}$ ${\displaystyle C}$ ${\displaystyle y=x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle p}$ ${\displaystyle i}$ ${\displaystyle y}$ ${\displaystyle p(i)=y}$ ${\displaystyle y}$ ${\displaystyle p}$ ${\displaystyle i}$ ${\displaystyle q}$

${\displaystyle q(x)={\frac {p(x)-y}{x-i}}}$

Этот многочлен сам по себе является доказательством того, что , поскольку если существует, то делится на , то есть имеет корень в , поэтому (или, другими словами, ). Доказательство KZG покажет, что существует и обладает этим свойством. ${\displaystyle p(i)=y}$ ${\displaystyle q}$ ${\displaystyle p(x)-y}$ ${\displaystyle x-i}$ ${\displaystyle i}$ ${\displaystyle p(i)-y=0}$ ${\displaystyle p(i)=y}$ ${\displaystyle q}$

Доказывающая программа вычисляет посредством указанного выше полиномиального деления, а затем вычисляет значение доказательства KZG. ${\displaystyle q}$ ${\displaystyle \pi }$

${\displaystyle \pi =\sum _{i=0}^{n-1}q_{i}Gt^{i}}$

Это равно , как и выше. Другими словами, значение доказательства — это многочлен, снова оцененный при значении ловушки , скрытом в генераторе . ${\displaystyle G\cdot q(t)}$ ${\displaystyle q}$ ${\displaystyle t}$ ${\displaystyle G}$ ${\displaystyle \mathbb {G} _{1}}$

Это вычисление возможно только в том случае, если указанные выше многочлены делятся нацело, поскольку в этом случае частное является многочленом, а не рациональной функцией . Из-за конструкции ловушки невозможно оценить рациональную функцию при значении ловушки, можно оценить многочлен только с помощью линейных комбинаций предварительно вычисленных известных констант . Вот почему невозможно создать доказательство для неверного значения . ${\displaystyle q}$ ${\displaystyle G\cdot t^{i}}$ ${\displaystyle x_{i}}$

Проверять

Для проверки доказательства используется билинейная карта спаривания , чтобы показать, что значение доказательства суммирует действительный многочлен , который демонстрирует желаемое свойство, которое состоит в том, что было разделено нацело на . Проверочное вычисление проверяет равенство ${\displaystyle \pi }$ ${\displaystyle q}$ ${\displaystyle p(x)-y}$ ${\displaystyle x-i}$

${\displaystyle e(\pi ,H\cdot t-H\cdot i)\ {\stackrel {?}{=}}\ e(C-G\cdot y,H)}$

где — билинейная функция отображения, как указано выше. — предварительно вычисленная константа, вычисляется на основе . ${\displaystyle e}$ ${\displaystyle H\cdot t}$ ${\displaystyle H\cdot i}$ ${\displaystyle i}$

Переписав вычисление в группе сопряжения , заменив в и и позволив быть вспомогательной функцией для подъема в группу сопряжения, проверка доказательства становится более ясной. ${\displaystyle \mathbb {G} _{T}}$ ${\displaystyle \pi =q(t)\cdot G}$ ${\displaystyle C=p(t)\cdot G}$ ${\displaystyle \tau (x)=e(G,H)^{x}}$

${\displaystyle e(\pi ,H\cdot t-H\cdot i)=e(C-G\cdot y,H)}$

${\displaystyle e(G\cdot q(t),H\cdot t-H\cdot i)=e(G\cdot p(t)-G\cdot y,H)}$

${\displaystyle e(G\cdot q(t),H\cdot (t-i))=e(G\cdot (p(t)-y),H)}$

${\displaystyle e(G,H)^{q(t)\cdot (t-i)}=e(G,H)^{p(t)-y}}$

${\displaystyle \tau (q(t)\cdot (t-i))=\tau (p(t)-y)}$

Предполагая, что билинейное отображение построено корректно, это демонстрирует, что , без того, чтобы валидатор знал, что такое или . Валидатор может быть в этом уверен, потому что если , то многочлены оцениваются с одинаковым выходом в значении ловушки . Это демонстрирует, что многочлены идентичны, потому что, если параметры были построены корректно, значение ловушки никому не известно, а это означает, что проектирование многочлена, имеющего определенное значение в ловушке, невозможно (согласно лемме Шварца–Циппеля ). Если теперь проверено, что является истинным, то проверено, что существует, поэтому должно быть полиномиально делимым на , поэтому из-за теоремы о факторах . Это доказывает, что значение th принятого вектора должно быть равно , поскольку это выход оценки принятого многочлена в . ${\displaystyle q(x)(x-i)=p(x)-y}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle \tau (q(t)\cdot (t-i))=\tau (p(t)-y)}$ ${\displaystyle x=t}$ ${\displaystyle q(x)(x-i)=p(x)-y}$ ${\displaystyle q}$ ${\displaystyle p(x)-y}$ ${\displaystyle (x-i)}$ ${\displaystyle p(i)-y=0}$ ${\displaystyle i}$ ${\displaystyle y}$ ${\displaystyle i}$

Почему используется билинейное сопряжение отображений

Полезность спаривания билинейного отображения заключается в том, чтобы позволить умножению на происходить безопасно. Эти значения действительно лежат в , где деление предполагается вычислительно сложным. Например, может быть эллиптической кривой над конечным полем, как это принято в криптографии на эллиптических кривых . Тогда предположение о делении называется проблемой дискретного логарифма эллиптической кривой ^{[ сломанный якорь ]} , и это предположение также является тем, что защищает значение ловушки от вычисления, делая его также основой обязательств KZG. В этом случае мы хотим проверить , . Это невозможно сделать без спаривания, потому что со значениями на кривой и мы не можем вычислить . Это нарушило бы вычислительное предположение Диффи-Хеллмана , основополагающее предположение в криптографии на эллиптических кривых . Вместо этого мы используем спаривание, чтобы обойти эту проблему. по-прежнему умножается на , чтобы получить , но другая сторона умножения выполняется в парной группе , поэтому . Мы вычисляем , что из-за билинейности отображения равно . В этой выходной группе у нас все еще есть проблема дискретного логарифма , поэтому, даже если мы знаем это значение и , мы не можем извлечь показатель степени , предотвращая любое противоречие с дискретным логарифмом ранее. Это значение можно сравнить с , и если мы сможем заключить, что , даже не зная, чему равно фактическое значение , не говоря уже о . ${\displaystyle q(x)}$ ${\displaystyle x-i}$ ${\displaystyle \mathbb {G} _{1}}$ ${\displaystyle \mathbb {G} _{1}}$ ${\displaystyle q(x)(x-i)=p(x)-y}$ ${\displaystyle G\cdot q(x)}$ ${\displaystyle G\cdot (x-i)}$ ${\displaystyle G\cdot (q(x)(x-i))}$ ${\displaystyle q(x)}$ ${\displaystyle G}$ ${\displaystyle G\cdot q(x)}$ ${\displaystyle \mathbb {G} _{2}}$ ${\displaystyle H\cdot (t-i)}$ ${\displaystyle e(G\cdot q(t),H\cdot (t-i))}$ ${\displaystyle e(G,H)^{q(t)\cdot (t-i)}}$ ${\displaystyle \mathbb {G} _{T}}$ ${\displaystyle e(G,H)}$ ${\displaystyle q(t)\cdot (t-i)}$ ${\displaystyle e(G\cdot (p(t)-y),H)=e(G,H)^{p(t)-y}}$ ${\displaystyle e(G,H)^{q(t)\cdot (t-i)}=e(G,H)^{p(t)-y}}$ ${\displaystyle q(t)\cdot (t-i)=p(t)-y}$ ${\displaystyle t}$ ${\displaystyle q(t)(t-i)}$

Кроме того, обязательство KZG может быть расширено для доказательства значений любых произвольных значений (не только одного значения), при этом размер доказательства остается , но время проверки доказательства масштабируется с . Доказательство то же самое, но вместо вычитания константы мы вычитаем многочлен, который вызывает множественные корни, во всех местах, которые мы хотим доказать, и вместо деления на мы делим на для тех же мест. ^[26] ${\displaystyle k}$ ${\displaystyle X}$ ${\displaystyle O(1)}$ ${\displaystyle O(k)}$ ${\displaystyle y}$ ${\displaystyle x-i}$ ${\textstyle \prod _{i}x-i}$

Квантовое битовое обязательство

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

Однако это невозможно, как показал Доминик Майерс в 1996 году (см. ^[27] для оригинального доказательства). Любой такой протокол можно свести к протоколу, в котором система находится в одном из двух чистых состояний после фазы принятия, в зависимости от бита, который Алиса хочет принять. Если протокол является безусловно скрывающим, то Алиса может унитарно преобразовать эти состояния друг в друга, используя свойства разложения Шмидта , эффективно побеждая свойство связывания.

Одно тонкое предположение доказательства заключается в том, что фаза фиксации должна быть завершена в какой-то момент времени. Это оставляет место для протоколов, которые требуют непрерывного потока информации до тех пор, пока бит не будет раскрыт или протокол не будет отменен, в этом случае он больше не будет обязательным. ^[28] В более общем плане доказательство Майерса применимо только к протоколам, которые используют квантовую физику , но не специальную теорию относительности . Кент показал, что существуют безусловно безопасные протоколы для фиксации битов, которые используют принцип специальной теории относительности, утверждающий, что информация не может распространяться быстрее света. ^[29]

Обязательства, основанные на физических неклонируемых функциях

Физические неклонируемые функции (PUF) полагаются на использование физического ключа с внутренней случайностью, который трудно клонировать или эмулировать. Электронные, оптические и другие типы PUF ^[30] широко обсуждались в литературе в связи с их потенциальными криптографическими применениями, включая схемы обязательств. ^{[31] [32]}

Смотрите также

• Незаметная передача
• Аккумулятор (криптография)
• Вечеринка по подписанию ключей
• Сеть доверия
• Zerocoin
• Анаграммы — использовались натурфилософами XVII века для установления приоритета открытия, не раскрывая его другим.

Ссылки

1. Одед Голдрайх (2001). Основы криптографии : Том 1, Основные инструменты. Cambridge University Press. ISBN  0-521-79172-3 . ^{: 224}
2. Жиль Брассар, Дэвид Шом и Клод Крепо, Доказательства минимального раскрытия знаний , Журнал компьютерных и системных наук, т. 37, стр. 156–189, 1988.
3. Голдрайх, Одед; Микали, Сильвио; Вигдерсон, Ави (1991). «Доказательства, которые не дают ничего, кроме своей достоверности». Журнал ACM . 38 (3): 690–728. CiteSeerX 10.1.1.420.1478 . doi : 10.1145/116825.116852 . S2CID  2389804. 
4. Рассел Импальяццо, Моти Юнг: Прямые вычисления с минимальными знаниями. CRYPTO 1987: 40-51
5. Наор, Мони (1991). «Обязательство бита с использованием псевдослучайности». Журнал криптологии . 4 (2): 151–158. doi : 10.1007/BF00196774 . S2CID  15002247.
6. Claude Crépeau, Commitment , Cryptography and Quantum Information Lab, McGill University School of Computer Science , дата обращения 11 апреля 2008 г.
7. Мануэль Блюм, Подбрасывание монеты по телефону , Труды CRYPTO 1981, стр. 11–15, 1981, перепечатано в SIGACT News т. 15, стр. 23–27, 1983, Школа компьютерных наук Карнеги-Меллона .
8. Шимон Эвен. Протокол подписания контрактов. В Аллен Гершо , ред., Достижения в криптографии (труды CRYPTO '82), стр. 148–153, Санта-Барбара, Калифорния, США, 1982.
9. A. Shamir, RL Rivest и L. Adleman, " Mental Poker " . В David A. Klarner , ed., The Mathematical Gardner ( ISBN 978-1-4684-6686-7 ), стр. 37–43. Wadsworth, Belmont, Калифорния, 1981. 
10. Одед Голдрайх , Сильвио Микали и Ави Вигдерсон , Доказательства, которые не дают ничего, кроме своей валидности, или все языки в NP имеют системы доказательств с нулевым разглашением, Журнал ACM , 38: 3, стр. 690–728, 1991
11. Одед Голдрайх и Хьюго Кравчик , О составе систем с доказательством нулевого разглашения , SIAM Journal on Computing , 25: 1, стр. 169–192, 1996
12. Дженнаро; Росарио; Рабин, Майкл О.; Рабин, Тал. «Упрощенные VSS и ускоренные многосторонние вычисления с приложениями к пороговой криптографии». Труды семнадцатого ежегодного симпозиума ACM по принципам распределенных вычислений . 1998, июнь.
13. Канетти Р. и Фишлин М. Универсально компонуемые обязательства.
14. Шиен Хин Онг и Салил Вадхан (1990). Совершенное нулевое знание в постоянном раунде, In Proc. STOC, стр. 482–493, цитируется в Шиен Хин Онг и Салил Вадхан (2008). Эквивалентность между нулевым знанием и обязательствами, Теория криптографии.
15. Тошия Ито, Иджи Ота, Хироки Шизуя (1997). Криптографический примитив, зависящий от языка, в J. Cryptol., 10(1):37-49, цитируется в Shien Hin Ong and Salil Vadhan (2008). Эквивалентность между нулевым разглашением и обязательствами, Теория криптографии.
16. Вагнер, Дэвид (2006), Midterm Solution, стр. 2 , получено 26 октября 2015 г.
17. "Цитаты: Bit Commitment using Pseudorandom Generators - Naor (ResearchIndex)" . Citeseer.ist.psu.edu . Получено 2014-06-07 .
18. Педерсен, Торбен Прайдс (1992). «Неинтерактивное и информационно-теоретическое безопасное проверяемое разделение секрета». Достижения в криптологии – CRYPTO '91 . Конспект лекций по информатике. Том 576. Берлин, Гейдельберг: Springer Berlin Heidelberg. С. 129–140. doi :10.1007/3-540-46766-1_9. ISBN 978-3-540-55188-1.
19. Метере, Роберто; Донг, Чанъюй (2017). «Автоматизированный криптографический анализ схемы обязательств Педерсена». Международная конференция по математическим методам, моделям и архитектурам для безопасности компьютерных сетей . Springer. С. 275–287.
20. Tang, Chunming; Pei, Dingyi; Liu, Zhuojun; He, Yong (16 августа 2004 г.). "Pedersen: Non-interactive and information-theoretic secure verifible secret sharing" (PDF) . Архив Cryptology ePrint . Advances in Cryptology CRYPTO 1991 Springer. Архивировано из оригинала (PDF) 11 августа 2017 г. . Получено 2 февраля 2019 г. .
21. Мони Наор, Рафаил Островский, Рамаратнам Венкатесан, Моти Юнг: Совершенные аргументы с нулевым разглашением для NP с использованием любой односторонней перестановки. J. Cryptology 11(2): 87–108 (1998)[1]
22. Менезес, Альфред Дж.; Ван Оршот, Пол К.; Ванстоун, Скотт А. (2018). Справочник по прикладной криптографии . CRC press.
23. Mouris, Dimitris; Tsoutsos, Nektarios Georgios (26 января 2022 г.). «Маскарад: проверяемая многопартийная агрегация с безопасными мультипликативными обязательствами» (PDF) . Архив Cryptology ePrint .
24. Каталано, Дарио; Фиоре, Дарио (2013). «Векторные обязательства и их применение». Криптография с открытым ключом – PKC 2013. Конспект лекций по информатике. Том 7778. Springer Berlin Heidelberg. С. 55–72. doi :10.1007/978-3-642-36362-7_5. ISBN 978-3-642-36362-7. Каталано, Дарио; Фиоре, Дарио (2013). "Векторные обязательства и их применение" (PDF) . Международная ассоциация криптологических исследований .
25. Беккер, Георг (18 июля 2008 г.). «Схемы подписей Меркла, деревья Меркла и их криптоанализ» (PDF) . Рурский университет в Бохуме. п. 16. Архивировано из оригинала (PDF) 22 декабря 2014 г. Проверено 20 ноября 2013 г.
26. Кейт, Аникет; Заверуча, Грегори; Голдберг, Ян (2010). "Constant-size commitments to polynomials and their applications" (PDF) . Международная конференция по теории и применению криптологии и информационной безопасности .
27. Брассар, Крепо, Майерс, Сальвайль: краткий обзор невозможности квантового битового обязательства
28. А. Кент: Безопасное классическое битовое обязательство с использованием каналов связи фиксированной емкости
29. Кент, А. (1999). «Безусловно безопасное обязательство по битам». Phys. Rev. Lett . 83 (7): 1447–1450. arXiv : quant-ph/9810068 . Bibcode :1999PhRvL..83.1447K. doi :10.1103/PhysRevLett.83.1447. S2CID  8823466.
30. МакГрат, Томас; Багчи, Ибрагим Э.; Ван, Чжимин М.; Рёдиг, Утц; Янг, Роберт Дж. (2019-02-12). "Таксономия PUF". Applied Physics Reviews . 6 (1): 011303. Bibcode : 2019ApPRv...6a1303M. doi : 10.1063/1.5079407 .
31. Рюрмайр, Ульрих; ван Дейк, Мартен (2013-04-01). «О практическом использовании физических неклонируемых функций в протоколах забывчивой передачи и битовых обязательств». Журнал криптографической инженерии . 3 (1): 17–28. doi :10.1007/s13389-013-0052-8. hdl : 1721.1/103985 . ISSN  2190-8516. S2CID  15713318.
32. Николопулос, Георгиос М. (2019-09-30). «Оптическая схема для криптографических обязательств с физическими неклонируемыми ключами». Optics Express . 27 (20): 29367–29379. arXiv : 1909.13094 . Bibcode : 2019OExpr..2729367N. doi : 10.1364/OE.27.029367. ISSN  1094-4087. PMID  31684673. S2CID  203593129.

Внешние ссылки

• Обязательство квантового бита на arxiv.org
• Кейт-Заверуча-Голдберг (KZG) Полиномиальные обязательства постоянного размера - Алин Томеску
• Полиномиальные обязательства Кейт