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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Схема обязательств»  -  новости  · газеты  · книги  · ученый  · JSTOR ( октябрь 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

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

Приложения [ править ]

Подбрасывание монет [ править ]

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

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

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

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

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

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

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

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

Схемы подписи [ править ]

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

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

Поддающийся проверке секретный обмен [ править ]

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

Определение безопасности [ править ]

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

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

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

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

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

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

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

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

Позвольте быть равномерным распределением по значениям открытия для параметра безопасности k . Схема обязательства соответственно совершенная, статистическая или вычислительное скрытие, если для всех тех вероятностей ансамблей и равны, статистически близка , или вычислительно неразличим .${\ displaystyle U_ {k}}$${\ displaystyle 2 ^ {k}}$${\ Displaystyle х \ 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 , работает примерно следующим образом. Коммиттер С посылает значение т к F , который сохраняет его и посылает «получение» для приемника R . Позже, C посылает «открыто» к F , который посылает м к R .

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

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

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

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

Строительство [ править ]

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

Бит-обязательство в случайной модели оракула [ править ]

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

Битовая фиксация от любой односторонней перестановки [ править ]

Можно создать схему битовой фиксации из любой односторонней функции, которая является инъективной. Схема основана на том факте, что каждая односторонняя функция может быть модифицирована (с помощью теоремы Голдрейха-Левина ), чтобы обладать вычислительно жестким предикатом (при сохранении инъективного свойства). Пусть 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 инъективен и, следовательно,${\displaystyle \oplus }$f ( x ) имеет ровно один прообраз.

Битовая фиксация от псевдослучайного генератора [ править ]

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

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

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

Для decommit Алиса посылает 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} ), в то время как${\displaystyle \oplus }$ R выбирается из 2 ^{3 n} значений. Она не выбирает R , поэтому существует вероятность 2 ^{2 n} / 2 ^{3 n} = 2 ^{- n,} что Y ', удовлетворяющий уравнению, необходимому для обмана, будет существовать.

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

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

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

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

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

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

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

Квантовые битовые обязательства [ править ]

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

• Приверженность квантовым битам на arxiv.org