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

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

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

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

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

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

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

Концепция схем обязательств была, пожалуй, впервые формализована Жилем Брассаром , Дэвидом Чаумом и Клодом Крепо в 1988 году. как часть различных протоколов с нулевым разглашением для NP , основанных на различных типах схем обязательств. Но до этого понятие использовалось без формального рассмотрения. Понятие обязательств впервые появилось в работах Мануэля Блюма . Шимон Эвен , и Ади Шамир и др. Терминологию, по-видимому, придумал Блюм. хотя схемы фиксации можно взаимозаменяемо называть схемами фиксации битов — иногда они зарезервированы для особого случая, когда зафиксированное значение равно биту . Ранее фиксация с помощью односторонних хэш-функций рассматривалась, например, как часть, скажем, подписи Лэмпорта , исходной схемы одноразовой однобитовой подписи.

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Идеальная функциональность обязательства, обозначенная здесь F , работает примерно следующим образом. Коммиттер C отправляет значение m в F , что получателю R. сохраняет его и отправляет «квитанцию » Позже C отправляет команду «open» 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 может получить в идеальном процессе, — это сообщение «получения». Таким образом, мы имеем противоречие.

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

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

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

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

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

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

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

$(h,f(x),b\oplus h(x))$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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})$

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

Аналогичным образом, упомянутое выше обязательство на основе RSA обладает гомоморфным свойством по отношению к операции умножения. Учитывая два сообщения $m_{1}$ и $m_{2}$ со случайностью $r_{1}$ и $r_{2}$соответственно, можно вычислить: $C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}\cdot m_{2},r_{1}+r_{2})$. Формально: $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})$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Совершить

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

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

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

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

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

Раскрывать

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

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

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

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

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

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

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

Проверять

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

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

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

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

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

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

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

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

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

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

показывать

Почему используется спаривание билинейных карт

The utility of the bilinear map pairing is to allow the multiplication of $q(x)$ by $x-i$ to happen securely. These values truly lie in $\mathbb {G} _{1}$, where division is assumed to be computationally hard. For example, $\mathbb {G} _{1}$ might be an elliptic curve over a finite field, as is common in elliptic-curve cryptography. Then, the division assumption is called the elliptic curve discrete logarithm problem, and this assumption is also what guards the trapdoor value from being computed, making it also a foundation of KZG commitments. In that case, we want to check if $q(x)(x-i)=p(x)-y$. This cannot be done without a pairing, because with values on the curve of $G\cdot q(x)$ and $G\cdot (x-i)$, we cannot compute $G\cdot (q(x)(x-i))$. That would violate the computational Diffie–Hellman assumption, a foundational assumption in elliptic-curve cryptography. We instead use a pairing to sidestep this problem. $q(x)$ is still multiplied by $G$ to get $G\cdot q(x)$, but the other side of the multiplication is done in the paired group $\mathbb {G} _{2}$, so, $H\cdot (t-i)$. We compute $e(G\cdot q(t),H\cdot (t-i))$, which, due to the bilinearity of the map, is equal to $e(G,H)^{q(t)\cdot (t-i)}$. In this output group $\mathbb {G} _{T}$ we still have the discrete logarithm problem, so even though we know that value and $e(G,H)$, we cannot extract the exponent $q(t)\cdot (t-i)$, preventing any contradiction with discrete logarithm earlier. This value can be compared to $e(G\cdot (p(t)-y),H)=e(G,H)^{p(t)-y}$ though, and if $e(G,H)^{q(t)\cdot (t-i)}=e(G,H)^{p(t)-y}$ we are able to conclude that $q(t)\cdot (t-i)=p(t)-y$, without ever knowing what the actual value of $t$ is, let alone $q(t)(t-i)$.

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

Обязательство квантового бита

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

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

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

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

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

См. также

• Не обращающий внимания трансфер
• Аккумулятор (криптография)
• Сторона, подписывающая ключ
• Сеть доверия
• Зерокойн
• Анаграммы - использовались натурфилософами 17-го века, чтобы установить приоритет открытия, не раскрывая его другим.

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

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