Высокоэффективных универсально-составных обязательств, основанных на DDH предположении

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 12:35, 15 декабря 2015.
Highly-Efficient Universally-Composable Commitments Based on the DDH Assumption
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Yehuda Lindell[@: 1]
Опубликован 2010 г.
Сайт Yehuda Lindell's Homepage
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация Универсальная передача, так же известная как UC безопасность, обеспечивает очень прочные гарантии безопасности для протоколов, которые работают в сложных реальных условиях. В частности, безопасность гарантирована, когда протокол работает одновременно множество раз с другими безопасными и небезопасными протоколами. Передающие схемы являются главной частью многих криптографических конструкций, тем самым имею большое значение в построении UC-безопасных протоколов. В этой статье мы построим высокоэффективные UC-безопасные передатчики от стандартного DDH допущения, струнная модель послужит опорной. Наш передатчик не является интерактивным, имеет общую справочную строку с элементами группы, и имеет сложность возведения в степень для привязки к элементу группы (точнее, эффективная стоимость заключается в том, что 3 возведения в степень имеется для каждой пары передачи – не передачи). Мы представляем конструкцию, которая является безопасной при статических противниках, и создадим другую конструкцию, которая является безопасной в присутствии адаптивных противников, при чем создание эффективной модели второго типа обойдется нам в дополнительные возведения в степень.

Введение

История. Универсальная эффективная составная передача. Современные криптографические протоколы работают в сложных условиях. Много различных безопасных и небезопасных протоколов выполняются одновременно, а некоторые протоколы могут быть разработаны специально для атаки других [13]. Классические определения безопасности, которые предполагают одиночные решения по угрозам, не могут гарантировать безопасность в современном мире. Универсальная передача определяет рамки, которые реально могут гарантировать безопасность, даже если протокол обрабатывается одновременно со множеством других, в том числе и небезопасных или смешанными. Более конкретно, UC-безопасный протокол ведет себя как идеальный исполнитель, где сторона, которой доверяют все, выполняет вычисления для других, вне зависимости от того, какие еще протоколы обрабатываются в данный момент.

UC-каркасные модели на много лучше работают в условиях реального времени и современного мира, чем классические, основанные на определениях. Таким образом, можно ожидать, что данная работа заинтересует практиков, реализующих передатчики, и в скором времени ее идеи притворятся в жизнь. Для демонстрации нам потребуются всего два примера: семейство СИГМА ключевых протоколов обмена, которые являются частью IKE (стандартизированного протокола обмена ключами в Интернет) и протокол HMQV, для которого была доказана безопасность в рамках UC-[5, 15]. Тем не менее, в UC-безопасности вызывает интерес так же и обмен ключами из прикладной криптографической области. (Подчеркнем, что это, в отличие от недавнего роста интереса к реализации общих и специфических протоколов для безопасного двух сторон и многопартийных вычислений; [17, 2, 23, 20, 19] в качестве примеров). Есть целый ряд причин для этого. Мы считаем, что одной из основных причин является отсутствие эффективных примитивов UC-безопасности, исключение составляют UC-безопасность без переводов [22]. Учитывая такое положение дел, очень трудно построить эффективные UC-безопасные протоколы, которые могут быть хорошо выполнены.

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

Схемы передатчиков, которые основаны на UC-ограничениях, впервые представленных Канетти и Фишлином, показаны в [4]. Они также показали, что невозможно построить передачи UC в простой модели, и, таким образом, следует, что требуются некие общие принципы построения. Схемы передачи [4] имеют свойство, что необходимо совершить ассиметричных битовых операций. Вскоре после этого, Дэмг'ард и Нильсен [9] представили передачи UC с тем свойством, что возведений в степень являются достаточными для трансформаций на всей строке (которые могут быть отображены в группе элемента). Это значительное улучшение. Тем не менее, строительство Дэмг'ард-Нильсена имеет несколько недостатков. Во-первых, она требует некую общую опору, линейно растет с увеличением числа сторон в системе; в частности, один элемент группы необходим для каждой партии. Это существенное препятствие для реализации, так как это означает, что это не возможно для публикации одной общей опорной строки, которая затем может быть использована для произвольных сторон, желающих запустить протокол. Во-вторых, сооружения Дэмг'ард-Нильсена базируются на N-сводимости и р-подгруппы предположений. Они станут более, чем предположениями RSA и DDH. Кроме того, N-сводимое предположение, поскольку его поведение в [21] страдает от значительных вычислительных накладных расходов, зависит от вычислений. Это связано с тем, что возведение в степень по модулю размером 1536 - необходимость для обеспечения достаточной безопасности - приводит возведения в степень по модулю число длиной 3072 бита. В отличие от этого, основные дискретные возведения в степень могут работать в эллиптических кривых размера 224 или 256 бит значительно быстрее. В криптографических протоколах, где многие передачи UC необходимы (см ниже пример), это может быть существенным препятствием.

Наши результаты. Мы представляем концептуально простой и эффективный протокол для UC-безопасности передач в общей опорной модели, которая основана на предположении DDH. Наш протокол требует регулярная группа возведения в степень и имеет общую справочную строку с ) группы элементов для любого количества участников. Кроме того, у нас есть вариант обеспечения безопасности в присутствии адаптивных противников, который приносит лишь незначительные дополнительные затраты. Сравнение наших результатов со построением Дэмг'ард-Нильсена, которое является самым известным, дает следующие:

- Предположения: Мы полагаемся на стандартное DDH предположение, в то время Дэмг'ард-Нильсен полагается на N-повторимость или п-подгруппа предположений. - Общая справочная строка (CRS): Наша общая ссылка на строку содержит описание дискретной группы журнала, его порядок и 7 элементов группы, и может быть использован любым количеством сторон. Таким образом, один CRS может быть опубликован для публичного использования. В противоположность этому, Дэмг'ард-Нильсену нужен CRS с одной (или кольцами) группой элементов каждой партии в системе. - Эффективность: Наш протокол имеет неинтерактивную фазу передач с помощью всего 5 возведений в степень для вычисленных коммиттера. Фаза декомпозиции является интерактивной и требует, чтобы вычислить 21 возведение в степень обеих сторон.

Использование оптимизации для вычисления мульти-возведения в степень вида общая стоимость в обеих фазах регулярной DDh возведения в степень. В отличие Дамгарда-Нильсена, здесь есть интерактивный этап передач с 10 крупными возведениями в степень упругости и неинтерактивной фазы декомпозиции, требующей 4 возведения. 1 Основа эксперимента. Мы считаем, что наша схема передачи примерно в 25-30 раз быстрее схемы Дамгарда-Нильсена. (Эта оценка основывается не на реализации схем, а на сравнении времени, необходимого для вычисления 14 возведений в степень с модулем N размера 2048 бит против эллиптических кривых "возведения в степень" над полем размер 256 бит , используя библиотеку Crypto ++ [25]. При использовании модуля N размера 1536 бит по сравнению с кривой над полем размер 224 битов, наша схема примерно в 20 раз быстрее.)

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

Пример - UC нулевое знание с сигма-протоколов. Так как наша эффективность повышена по сравнению с предыдущими работами конкретно, а не асимптотически, мы хотим продемонстрировать свою значимость в реализации. Мы делаем это с учетом ветвления нашего повышения эффективности на конструкциях эффективных UC-защищенных протоколов с нулевым знанием. Многие, если не большинство, полезные эффективные протоколы с нулевым знанием основаны на протоколах Sigma [8]. В случае автономного преобразования, из протоколов Сигма с нулевым знанием и с нулевым знанием доказательств, знания являются высокоэффективными, требуя только несколько дополнительных возведений в степень; [10, раздел 6.5]. К сожалению, такой эффективный аналог не известен для достижения UC нулевого знания из протоколов Sigma. Скорее всего, это необходимо повторить для Сигма протокола L раз, чтобы достичь ошибку устойчивости Кроме того, 3 UC-допущения необходимы для каждого повторения (но только два открыты); [12] и [16] для описания трансформации. Установка L = 40 в течение разумного времени ошибки, мы имеем, что 120 UC передач необходимы для трансформации. Предполагая, 47 миллисекунд для нашей схемы и 1,35 секунд для Дамгарда-Нильсена (на основе оценок с использованием Crypto ++ библиотеки), мы получем, что дополнительные накладные расходы в результате передач UC 5,6 секунд для нашего протокола против 162 секунд для Damg˚ard-Nielsen (разница на самом деле даже больше, так как 40 из 120 передач не открыты, см Сноска 1). Мы пришли к выводу, что реализация протокола улучшения эффективности, полученной с использованием нашего нового протокола передач UC, может быть окончательной.

Предварительные выборы и определения

2 м определением универсальной передачи [3] является определение безопасности, которое гласит, что к исполнению автономного протокола в специальной настройке причастны машины среды, в дополнение к честным партиям и противникам. Как и в классическом определении безопасного вычисления, идеальные и реальные модели считаются таковыми, если доверенная сторона осуществляет вычисления в модели идеального и реального протокола работы в реальной модели. Среда адаптивно выбирает входы для честных лиц, взаимодействует с оппонентом на протяжении вычислений, и получает выходные значения. Безопасность формулируется из требования существования идеальной модели тренажера так, что ни среда не может различать случая, когда работает с реальным противником в реальной модели и когда работает с идеальной моделью тренажера в идеальной модели. Рассматривая чуть более подробно, обозначим через выход окружающей среды с входным z после идеального завершения с идеальным противником (симулятором) и функциональном , с параметром безопасности n.Мы будем рассматривать только черный ящик тренажера и поэтому мы обозначим симулятор в смысле, что он работает с противником с целью атаковать реальный протокол. Кроме того, мы обозначим через выход среды с входным z после реального исполнения протокола π с противником с параметром безопасности n.Наши протоколы занесены в общий справочник строки (CRS) модели. Формально это означает, что протокол π выполняется в гибридной модели, где стороны имеют доступ к идеальной функциональности , что выбирает CRS в соответствии с установленным распределением и передает его какой-либо партии, которая обращается с такой просьбой. Обозначим ошибки π в такой модели по гибридной функции Неофициально, протокол π UC реализует функциональность в гибридной модели если существует вероятностная полиномиального симулятора такая, что для каждого неравномерного вероятностного полинома времени среды и каждой вероятностной полиномиальной состязательности , считает, что Важность этого определения является теоремой композиции и утверждает, что любой протокол, который универсально компонуем, является безопасным, когда работает одновременно со многими другими произвольными протоколами; [3] для определения и деталей.

Передачи UC. Мульти-передача - идеальная функциональность Fmcom такая, что функциональные возможности, которые мы UC реализовали в этой статье, формально определяется на рисунке 1.

Рисунок 1 (функциональность) . происходит следующим образом. Она работает с партиями , параметр , и противник :

- Фаза фиксации: При получении сообщения совершить ( отправка,sid, SSID, , , ) от , где х ∈ , записать Кортеж (SSID,, , ) и отправить сообщения (получение, sid, SSID, , ), чтобы и . Игнорируя любые будущие сообщения с тем же SSID от к .

– Этап выявления: После получения сообщения раскрыть (sid, SSID) из , если кортеж (SSID, , , ) был ранее записан, а затем отправить сообщение (раскрыть, sid, SSID, , , ) для и . В противном случае, игнорировать. Идеальная функциональная приверженность. По техническим причинам, длина совершенного значение х равно Она определяется таким образом, потому что наша приверженность включает шифрование x вместе с SID идентификаторами сессий, SSID и идентичностей сторон (I, J). Теперь, шифрование, которое мы используем для одного элемента группы, стало длины n, и поэтому общая длина x, sid, SSID, I, J должна быть n. Поэтому мы определим каждый идентификатор и идентичность, чтобы они были размера ; это означает, что каждый исходит из суперполиномиального домена, что достаточно, чтобы обеспечить уникальность идентификаторов сеанса и сторон. Таким образом, принимая x объема имеем, что строка (x, sid, SSID, I, J) имеет длину n.

Эффективные Передачи UC

Протокол идея и Обзор. Прежде, чем описывать идею нашей конструкции, напомним, что UC-безопасная передача должна быть как извлекаемые (это означает, что тренажер может извлечь значение, что повреждены партии, обязан) и двусмысленные (это означает, что модель может генерировать передачи, которые могут быть открыты в любом значении), без тренажера перемотки противника. Кроме того, противник не должен быть в состоянии генерировать передачи, связанные с переданными данными честных лиц. Таким образом, передача должно быть по существу не податлива. Наш протокол находится в общей опорной строке (CRS) модели; это оправдано тем, что передачи UC не могут быть достигнуты в простой модели [4]. Высокий уровень идея нашей конструкции состоит в следующем. Коммиттер использует строку с помощью шифрования с CCA2-безопасной схемой шифрования ECCA, используя общественный ключ PK1, который содержится в общей опорной строке (CRS). Заметим, что это допускает извлечение, потому что при моделировании протокола, в модели CRS, симулятору разрешено выбирать сам CRS. Таким образом, можно выбрать открытый ключ, что будет известен всем, и соответствующий секретный ключ дешифрования. Это позволяет ему расшифровать и получить зафиксированное значение. Далее, для того, чтобы декомпозицией явно не удалось выявить значение и случайность, используемую для шифрования, шифрование совершенно обязательно, и поэтому не представляется возможным исключить его. Таким образом, для того, чтобы провести декомпозицию, коммитер вместо этого посылает зафиксированное значение, а затем доказывает, в нулевым знанием, что это действительно правильное значение. На первый взгляд, это подход может показаться бесполезным, потому что в UC установке кажется, что передачи UC построить проще, чем нулевое значение. Тем не менее, мы видим, что доказательство не должно быть развернутым протоколом нулевого знания полного UC, и, в частности, нет необходимости отвлекать свидетеля от доказательства. Скорее всего, только подразумевается, что мы должны имитировать без перемотки. Это связано с тем, что извлечение совершенного значения уже имело место на стадии фиксации, и это доказательство нужно только для того, чтобы поврежденные стороны декомпозировались в то же значение, в которое должны были. Конечно, способность симулятора увиливать связана с его способностью запускать симулятор нулевых знаний и, по сути, лгать о стоимости совершенных с. Доказательство того, что мы используем его, базируется на протоколе Sigma, и мы делаем это с нулевым знанием (без перемотки), имея проверяющий первый коммит его вызова, а затем запускаем протокол Sigma с проверяющий декомпозицией. Для того, чтобы иметь симулятор прямой линии, мы делаем эту передачу от проверяющего шифрование вызова под другим открытым ключом PK2 в CRS. Как и ранее, при моделировании симулятора можно выбрать открытый ключ, так что он знает соответствующий секретный ключ, что позволяет ему извлекать вызов от проверяющего. После того, как он добыл вызов, он может запустить симулятор для протокола Sigma, который идеально подходит. Хотя это кажется интуитивно привлекательным, это проблематично, поскольку устойчивость этой трансформации из протокола Сигма доказательства с нулевыми знаниями может быть доказана только, если передача прекрасно прячется. Мы решили, что это может быть эффективно с помощью двойной режим криптосистемы введенную в [22, 2], хотя мы должны изучить только простую версию. Такие криптосистемы имеет регулярный алгоритм генерации ключей и альтернативный, который и обладает свойством представления себя как обычного публичного ключа шифрования, когда схемы регулярного ключа генерируется, но прекрасно скрывают зашифрованное значение, пока генерируется альтернативный ключ. Кроме того, регулярные и альтернативные ключи неразличимы. Как мы увидим в доказательстве, этого достаточно для обоснованнования, поскольку в точке, где устойчивость необходима, мы больше не должны быть в состоянии извлечь вызов верификатора и, таким образом, заменить ключ в общей опорной колонне с помощью альтернативной. Обратите внимание, что регулярный ключ для используется в исполнении реального протокола, и способность генерировать альтернативный ключ используется в доказательстве безопасности. (Отметим также, что мы не можем использовать этот метод для фактической UC приверженности, потому что мы должны одновременно извлекать и увиливать.) Возможно, приведенный выше тезис вытекает из следующего шаблона для передач UC:

Протокол 1 (шаблон UC-передачи). Общие строка ссылка: (pk1, pk2 ), где pk1 является открытым ключом из CCA2-безопасной схемы шифрования, и pk2 является открытым ключом из двухрежимной криптосистемы, как описано выше. Фиксировании фаза: 1. .Коммитер обязуется доставить х путем шифрования его под pk1 и отправки зашифрованного текста к ресиверу (например, он шифрует x при помощи случайного значения r). (На самом деле, х шифруется вместе с уникальным идентификатором сессии и идентичностей сторон, но мы игнорируем эти подробности здесь.)

Фаза декомпозиции: 1. Коммитер посылает х к ресиверу (не раскрывая r) 2. Пусть обозначим (α , ε, г) сообщение протокола Sigma для доказательства того, что с является шифрованием х (с помощью свидетеля r).

Получатель отправляет ε;

Коммитер отправляет α

Приемник декомпозиции к ε, отправив ε и г'

Коммиттер проверяет, что ε;и если да, вычисляет ответ z для протокола Sigma, основанный на (а,ε), где (ε) - выходы приемника х, как декомпозированного значения, если и только если (α, ε, г) является принятым Сигма-протоколом стенограммы.

Прежде чем приступить, мы объясним, почему значение х стремится к а с помощью шифрования под схемой шифрования, которая безопасна под адаптивных выборкой зашифрованных атак (CCA2 безопасный).В частности, мы уже обсуждали, почему некоторые понятия непластичности необходимы, но CCA2-безопасности сильнее, чем NM-CPA 2. На самом деле, наша конструкция двойного шифрования точно такая же, как неоднозначные приверженности, используемые в [11]. Для того, чтобы понять, почему мы все-таки должны обеспечить CCA2 безопасность, напомним, что симулятор должен уметь избегать определенные случаи. В частности, в моделировании идеальной модели, симулятор получает целенаправленные команда, которые не содержат никакой информации о полной стоимости. Тем не менее, в реальном мире, противник получает шифрование фактического полного значения. Таким образом, всякий раз, когда он получает квитанцию передач, симулятор шифрует 0 и передает его в реальном мире противникам. Позже, когда приверженность открывается и имитатор узнает, что это было до величины х, то мошенничество в протоколе Sigma открывается и "доказывает", что шифрование 0 был фактическим шифрованием х. Для того, чтобы доказать, что шифрование 0 (как тренажер делает) и шифрование х (как честный участник делает) не имеет никакой разницы, необходимо уменьшить безопасность схемы шифрования. В таком упрощении, противник нападает на схему шифрования и имитирует выполнение передачи UC, так что, если он получил шифры от 0, то результат должен быть таким же, как в идеальной модели, и если он получил шифры реальных значений х, то результат должен быть так же, как при реальном исполнении с честным лицам и реальным противником. Чтобы быть более точным, это сокращение осуществляется путем запуска тренажер для схемы передач UC и использования вызова шифрования, полученного в игре, а не шифрования передач симулятора, генерируемых самостоятельно. Конечно, в этом сокращении симулятор не выбрает открытый ключ CCA2-безопасности, чтобы разместить в CRS, а помещает открытый ключ, который он получает в рамках шифрования в отличительный игре. Однако, как мы уже говорили, симулятор должен быть в состоянии извлечь зафиксированные значения, сгенерированные противником путем дешифрования, в то время как мы проводим это сокращение. Это подводит нас к сути проблемы, которая заключается в том, что он может нести только эту расшифровку, потому что он знает секретный ключ, и поэтому он не может расшифровать при доказательстве сокращение. Эта проблема решается с помощью CCA2-безопасного шифрования, потому что в настоящее время в отличительный игре противнику разрешается просить расшифровку шифртекстов, и поэтому тренажер может расшифровать передачи от противника, как это и требуется

Эффективные реализации. Остается сказать, что все элементы протокола могут быть эффективно реализованы. Во-первых, мы используем Крамера-Шоап (CS) схему шифрования [7] как CCA2-безопасной схемы шифрования. Эта схема определяется следующим образом:

- генерация ключей CS: Пусть (G, q, g1, g2) такое, что G является группой порядка q и g1, g2 - два различных генератора. Выберите x1, x2, y1, y2, Z ∈ R наугад и вычисляемое и . Открытый ключ (G, q, g1, g2, c, d, h) и секретный ключ (x1, x2, y1, y2, z).

- Шифрование CS: Пусть m ∈ G. Затем, для того, чтобы зашифровать m, нужно выбрать случайный r∈ R в , вычисляемого ,ω = Н, где Н устойчивые Хэш-функции, . Зашифрованный текст представляет собой .

- Расшифровки CS: вычислить ω = Н. Если , то выход .

Ключевое наблюдение, которое мы делаем для того, чтобы проверить, что зашифрованный текст является допустимым шифрованием из сообщения m, то достаточно доказать, что существует такое значение r ∈ , таких, что , , и .

Кроме того, поскольку ω может быть вычислена публично от открытого ключа и зашифрованного текста, все значения для г являются открытыми исключениями. Таким образом, мы имеем, что для того, чтобы доказать, что зашифрованный текст шифрует некоторое заданное значение м, нам просто нужно запустить доказательство того, что 4 значения имеют один и тот же дискретный журнал по отношению к их соответствующим основаниям. Высокоэффективные протоколы Sigma существуют для решения этой задачи (это то же самое, как доказать, что кортеж имеет вид Диффи-Хеллмана). Таким образом, CCA2-безопасной схемы шифрования вместе с необходимым доказательством может быть реализован очень эффективно. Остается показать, как двойная модель схемы шифрования может быть эффективно реализована. Для этого мы должны иметь возможность построить фальшивый открытый ключ, который неотличим от нормального, так что если шифрование осуществляется в этом разделе, то зашифрованное значение совершенно скрыто. Такой схемы шифрования могут быть построены в двойной стоимости Эль Гамаля следующим образом:

- Двойная регулярная генерация ключа: Пусть (G, q, g1, g2), как показано выше. Выберите р ∈ R и вычислите и . Открытый ключ (G, q, g1, g2, h1, h2), и частный ключ ρ.

- Двойное поколение альтернативного ключа: Как и выше, за исключением того, что выбрать ρ1, ρ2 ∈ R с ρ1 ̸= ρ2 и вычислить и .

- Двойное шифрование: Для шифрования m ∈ G, выберите случайное R, S ∈ и вычислите и . Зашифрованный с = (u, v).

- Двойная расшифровка: Для расшифровки (u, v) вычислить .

Для того, чтобы увидеть, что эта схема имеет желаемые свойства, заметим, что для расшифровки работ, как и в Эль-Гамале, альтернативные ключи, неотличимые от реальных по предположению DDH, и шифрование при альтернативном ключе прекрасно скрывается, так как при ρ1 ̸= ρ2 значения и и V являются независимыми. Наивно полагать, что стоимость шифрования составляет 4 возведения в степень. Однако, используя метод одновременных нескольких возведений в степень в [18, гл. 14.6], мы получаем, что и и v может быть вычислено в эквивалентной стоимости возведения в степень каждого. Таким образом, стоимость возведения в степень.

Фактический Протокол

Полная спецификация нашей схемы передач появляется в Протоколе 2. Доказательство проводится в фазе декомпозиции на основе протокола Sigma для кортежей Диффи-Хеллмана. Что касается полноты этого доказательства заметим, что если является честным, то , , и

ПРОТОКОЛ 2 (UC-безопасный протокол передачи).

Общие строки ссылки:(G, q, g1, g2, c, d, h, h1, h2), где G представляет собой группу порядка q с образующими g1, g2, и c, d , h ∈ R G случайными элементами G, и , для случайного р ∈ R Zq. (Заметим, что (G, q, g1, g2, c, d, h) является открытым ключом Крамера-Шоап, и (G, q, g1, g2, h1, h2) является регулярным открытым ключом двухрежимной схемы шифрования.) Пусть G (у) - отображение строки у ∈ G, и предположим, что также эффективно вычислимо.

Фаза совершения: По входу (совершить, sid, SSID,, ,x), где х ∈ и SID, SSID ∈ , партия работает следующим образом:

1. вычисляет m = G (х, sid, SSID, , ,x). (Личности I, J могут быть отображены в и так в целом (х, sid, SSID, I, J) является n-битовая строка).

2. выбирает случайное r ∈ R Zq, вычисляет , ω = H (, , е) и , где Н столкновение устойчивых хеш-функций (формально, ключ для хэш-функции может появиться в CRS, мы игнорируем это для простоты).

3. множества С = (, , е, v), и посылает (SID, SSID, C) в Pj.

4. магазины (SID, SSID, ,, С) и выходы (квитанция, sid, SSID, , ). игнорирует любые более поздние сообщения с тем же (SID, SSID) из .

Фаза декомпозиции:

1. По входу (раскрыть, sid, SSID, , ), партия посылает (SID, SSID, х) к

2. вычисляет m = G (х, sid, SSID, I, J)

3. Доказательство совершенной стоимости: оказывается что m является зашифрованным значением. Это эквивалентно доказательству, что существует значение r, что ,, и . Доказательство проводится следующим образом:

посылает (SID , SSID, с') для , где с' = (, (ε)) является приверженностью к случайному вызову ε ∈ R и R, S ∈ R Zq.

вычисляет α = , β =, γ = и δ = , и передает (SID, SSID, α, β, γ, δ) для .

посылает декомпозицию (SID, SSID, R, S, ε) на вызов, чтобы .

проверяет, что с' = (, (ε)). Если нет, прерывает операцию. В противном случае, вычисляет Z = S + εr и посылает (SID, SSID, z) в .

выходы (раскрыть, sid, SSID, , , х), если и только если ,, и

Бетон эффективность: Стоимость протокола в ряде возведения в степень (все остальные операции незначительны) выглядит следующим образом:

1. вычисляет 5 возведений в степень для того, чтобы генерировать приверженности, и 8 возведений в степень в фазе декомпозиции(обратите внимание, что 4 из этих возведений в степень делаются в целях проверки вызов Е из , а с уже вычислена на этапе фиксации, и только одно возведение в степень необходимо для d).

2. вычисляет 0 возведений в степень в фиксации фазы и 13 возведений в степень в фазе декомпозиции. В целом, стороны вычисляют 26 возведений в степень. Заметим, что может сделать все предварительные обработки, но 6 из его возведений в степень. Это потому, что он может вычислить прежде чем m таким образом ω известно. После (х, SID, SSID, , ) дается и тем самым m могут быть вычислены, просто необходимо, чтобы вычислить до завершения приверженности и до конца первого сообщения на этапе декомпозиции. Наконец, он должен совершить более 4 возведений в степень, чтобы проверить е отправленных . Аналогично, предварительно обрабатывает 4 его возведения в степень при генерации. Мы пришли к выводу, что протокол требует 26 возведений в степень в целом, но с использованием предварительной обработки коммиттером нужно вычислить только 6 возведений в степень, и необходимо вычислить только 9 возведений в степень. Кроме того, расчеты и необходимые для вычислений и проверки шифрования, могут быть вычислены по стоимости возведений в степень каждого, используя оптимизацию [18, п. 14.6]. Таким образом, количество возведений в степень может быть эффективно снижено до .

Теорема 1 Если предположить, что предположение DDH имеет в группе G, протокол 2 UC-надежно реализует функциональность в -гибридной модели, в наличие статических противников.

Доказательство: Интуиция за доказательства безопасности уже появляется в разделе 3.1.Поэтому мы перейдем непосредственно к описанию симулятора и доказательства безопасности.

Тренажер S:

-Шаг инициализации: S выбирает открытый ключ / секретный-ключ для Крамера Шоап криптосистемы; пусть (G, q, g1; g2; с; d; h) с открытым ключом Кроме того, S выбирает случайное и вычисляет и S устанавливает CRS может быть (G; q; g1; g2; c; d; h; h1; h2).

- Моделирование связи с Z: Каждая входная стоимость, которую получает S от Z написан на входной ленте А (как если оно прибывает из Z) и наоборот.

- Имитируя фиксацию на этапе, когда коммиттер поврежден и приемник честно: при получении (sid;SSID; c) как он намерен отправить от до , имитатором S использует свои знания Крамер-Shoup секретный ключ для расшифровки c. Пусть m = G(х; sid';SSID'; i'; j') будет результат. Если (sid';SSID'; i'; j') = (идентификатор,sid,SSID; i; j) или дешифрации недействительным, тогда S отправляет манекен обязательств (совершения; sid;SSID;; ; 0) в . Иначе, он посылает (фиксации; sid;SSID;; ; х) в .

- Имитируя снимает выделение стадии, когда поврежден и является честный: S управляет честный стратегии с контрольным . Если бы вывод (выявить;sid;SSID;;; х), то S посылает (раскрыть;sid;SSID; ;) в . В противном случае, он ничего не делает.

- Моделирование стадии фиксации при является честным и поврежден: после получения (приемники; SID;SSID;;) от , симулятор S, вычисляет шифрование Крамера-Шоапа с 0, и (SID; SSID; c) к А, как он ожидает получать от . Моделируя стадию, когда честен и поврежден:после получения (показывают; sid; ssid; ;; x) от , S работает правильно.

1. S руки (sid; ssid; x) к A, поскольку это ожидает получать от .

2 S получает c′ от A и использует его знание дискретной регистрации h1; h2 (в CRS), чтобы расшифровывать c′ от G(e) и получает е.

3 Пусть C = (u1; Уu; e; v) быть как подсчитало S в стадии совершения..S выбирает случайный z ∈R Zq и вычисляет

В противном случае, (это должно происходит потому, что при регулярном открытого ключа двойного шифрования схема использует шифрование от S до A. Моделирование в случаях, что как и являются честными проста. Это связано с тем, что когда обе стороны честны, тренажер может выбрать значение e себя и генерировать действительное доказательство для любого требуемого значения . Анализ моделирования: обозначающий протокол 2 к π и напоминая о том, что он работает в -гибридная модель, мы должны доказать, что для любого и каждого Z,

Мы докажем это через серию гибридных игр. Игра гибрид hyb-game1: в этой игре, идеальная функциональность дает симулятор значение х стремится к честным вместе с обычным (квитанцию; sid; SSID; ;) сообщения. работает точно так же, как S, за исключением что при моделировании стадии фиксации при является честным и поврежден, он вычисляет с как шифровки m = G (х;sid; SSID; i, j) в качестве честного будет

В противном случае, он ведет себя точно так же как и в симуляции. Для того, чтобы показать, это выход Z в hyb-game1 неотличима от ее выхода в идеале, нам нужно уменьшить разницу в безопасности схеме шифрования. Однако, S и должны расшифровать в моделировании фиксации этапе, когда коммиттер поврежден и честно (см. тренажера описание). S и можно проводить эту расшифровку, потому что они знают секретный ключ Крамера-Shoup . Но, это означает, что безопасность не может быть сведена к этой схеме. Мы решаем эту проблему, используя тот факт, что Крамер-Shoup схема шифрования CCA2- надежная. Таким образом, S и можно расшифровать, используя их расшифровки оракула. Мы используем LR-формулировку CCA2-безопасности. В такой формулировке немного случайностей и противник можете задать шифрование для многих задач. Каждый запрос состоит из пары (m0;m1) и противник получает обратно шифрования (всегда с одной b). Задача противника-угадать бит b. И конечно, учитывая, что это CCA2 игры, противник может задать для расшифровки любой зашифрованный текст, который не был получен в качестве шифрования одной из пары. Формально, мы построим CCA2 противника атакующий Крамера-Шоап Схема строится следующим образом.

Пусть (G, q, g1; g2; с; d; h) будет открытым ключом для . Противник выбирает p∈R Zq, вычисляет и , и устанавливает системой координат в (G; q; g1; g2; c; d; h; h1; h2). Затем имитирует выполнение в но со следующими отличиями:

1. Всякий раз, когда честный совершает до значения х, а S шифрование 0 (или шифрования х), создает шифрование в зашифрованный текст, задавая для шифрования вызов пары (0, G (X; sdi; SSID, i, j)). Зашифрованный С получала обратно отправляется в качестве обязательства. (Обратите внимание, что знает, потому что х он работает Z и так знает, входы передаются в честных лиц).

2. Всякий раз, когда повреждены посылает значение обязательств (SID; SSID C) и симулятор необходим для расшифровки C, запрашивает его расшифровки оракула с с. Если С был получен в зашифрованного вызова, то симулятор отправляет манекен приверженность (совершить; sid; SSID; ; ; 0) до , как в случае, (SID '; SSID "; i'; j') ̸= (SID; SSID; i; j) в симуляции. Так как с было получено, как зашифрованный текстом вызов, это действительно имеет что (SID'; SSID'; i', j ') = (SID; SSID; i, j) и это то же самое.

3. Наконец, выходы все выходы Z. Теперь, если b = 0 в CCA2 игры, то все обязательства С, порожденная когда правильно должны быть 0. Таким образом, моделирование в точности, как S а выход именно, что из . (Заметим, что все другие инструкции выполняются идентично S.) В противоположность этому, если b = 1, полученные правильные значения х, и поэтому моделирование так же, как . Таким образом, выход из именно, что из Мы пришли к выводу что схема шифрования Крамера-Шоап является CCA2-безопасный.

Гибридная игра HYB-Game2: В этой игре, симулятор работает точно так Точно так же, как , за исключением того, при моделировании фазы когда Пи является честным и поврежден, он вычисляет сообщения (a;b;c; d) И в доказательство будет именно как честный . Это может сделать это потому что обязательство c посланный в фазе обязательства к правильному значению m = G (x; sid; ssid; i; j)и таким образом, это может означать честную программу автоматического доказательства. Распределение выхода этой игры идентична HYB-Game1 моделирования доказательства из фазы. Это доказательство основано на стандартном протоколе, что Sigma кортеж Диффи-Хеллмана, и это просто, чтобы убедиться, что эти распределение идентичны. Мы заключаем, что

В завершение доказательства: Остается показать, что на выходе Z после из в модель ничем не отличается от его выхода после HYB-Game2 игры. Во-первых, заметим, что приверженность и сообщения в случае честного коммиттера идентичны в обоих HYB-game2 и выполнены в режиме реального протокола в модели . Таким образом, с той лишь разницей что между выходом Z в обоих случаях может быть связано с значением х преобразователя и честно говоря приемник из поврежденного отправителя . Это связано с тем, что в Hyb-game2, значение х на выходе честного это значение послано после расшифровки зашифрованного текста, связанного в стадии фиксации при помощи секретного ключа Крамера-Шоап.

В отличие от этого, в значение выхода x то честный участник, который направляется в первую ступень этап ( пока доказательство проходит). Эти значения могут быть разными только если сможет убедить честный выход x В фазы, хотя зашифрованное значение C отправлено в обязательства фазы не m = G(х; sid; SSID; i; j). Таким образом, это различие уменьшает до разумности доказательства в фазе. Напомним, что специальным свойство Сигма протокола, в случае что C не является шифрование m = G(х; sid; SSID; i;j), для каждого первого сообщения ( a;b ; c; d) есть только одно e, для которого существует убедительного ответа z. Напрашивается вывод, что, поскольку шифрование e семантически надежности, не сможет обмануть в Сигма-протоколе. Однако это требует сокращение и такое сокращение не могут быть выполнены, потому что противник не “показывает” нам, преуспеет ли это в доказательстве, пока мы не расшифруем . Таким образом,нельзя уменьшить способность противника к сокрытию, "(в таком сокращение, нельзя показать "вместе с хаотичностью, используемой, чтобы зашифровывать). Тем не менее, это возможно, чтобы заменить значения ; , где и со значениями и , ∈R Zq. В таком случае, как мы обсуждали, шифрование идеально скрывает значение e. Кроме того, должен когда-либо расшифровывать c′ здесь (симулятор, который не расшифровывает в hyb-game2 эти символы). Таким образом нет никакой проблемы, заменяющей ; Наконец, вспомните что альтернативный ключ h1; h2 неотличим от регулярного.Таким образом, определяя hyb-game3, чтобы совпасть с hyb-game2 за исключением того, что ключи h1; h2 отличаются, как описано, и разрешение = (кроме снова, для как h1; h2 выбраны).

Мы теперь готовы завершить доказательство. Так как шифрование c′ отлично скрывает проблему e, вероятно, что успешно доказывает неправильное заявление на стадии самое большее . Таким образом, стоимость отправленных в имеет такое же значение, что и выход по честным , за исключением с ничтожно малой вероятностью. Единственная разница заключается в том, что в hyb-game3 альтернатива с открытым ключом для двойного режима криптосистемы используется регулярно в гибридных криптосхемах. Напоминая о том, что эти ключи являются вычислительно неразличимы, мы заключаем, что:

=

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

Адаптивные противники со стираниями

Фон и схема решения.

В настройках адаптивных повреждений, противник может повредить партии на протяжении всего вычисления. По повреждениям, он получает локальное состояние сторон,в том числе он использует случайности и так далее. В модели с подчистками, протокол может поручить , чтобы стереть некоторые из его состояния (например, старые ключи), и в таком случае противник не получает стертое состояние после коррупции. Повреждения точно моделирует реалистичные настройки, где стороны могут быть "взломаны"во время вычислений. Таким образом, желательно, чтобы протоколы, в этой модели были безопасными. Эта модель представляет значительные трудности при доказательстве безопасности. В частности,заметим, что протокол 2 не является безопасным в присутствии адаптивных противников,даже с подчистками, потому что коммиттером должны хранить случайности R которые используются для того, чтобы запустить схему . Теперь, в нашей модели,симулятор совершает 0, даже тогда, когда обязательство действительно х. Однако, в реальном мире, противник получает r и х такие, что является шифрование с помощью х случайности r. При моделировании, например случайность может никогда не производиться из с является шифрование 0, а не х (там не существуют r', которые могут объяснить как шифровки х ̸= 0). Обеспечения адаптивной безопасности. Наш протокол может быть модифицирован так, что он достигает адаптивной безопасности с стираний, при небольших дополнительных затратах. Интересно, единственное необходимые модификации являются изменением в заказе операций . Обязательство Педерсена. Чтобы видеть это, вспомните что проблема с достижением адаптивной безопасности - то, что судья не может стереть r перед представлением и передать фазу, потому что тогда это не будет в состоянии быть доказательством в фазе

Однако, это возможно для сторон для выполнения большинства доказательств уже в фазе фиксации, прежде чем послать шифротекст (фактически,зашифрованный текст) текст ведет себя двусмысленно ,приемник управляет протоколом нулевого знания, прежде чем судья, посылает последнее сообщение z. Кроме того, судья передает первое сообщение протокола вместо того, чтобы послать его в правдивом виде. (Таким образом, приемник посылает приверженность ; лицо, совершившее отправляет приверженность ; приемник раскрывает ; наконец, коммиттер готовит Z e без отправки.) После этой преамбулы, коммитер стирает все ее случайности, кроме, что необходимо для снятия выделения в первом сообщении с нулевым знанием протокола, и только потом раскрывает c. Это завершает фазы фиксации . К снятию выделения фазы просто состоит из коммиттер отправки (a,b,c,d) и сообщение Z (который уже готов), и приемник проверяет что(a,b,c,d) представляет собой прием стенограмма. Таким образом, это вовсе не влияет на сокрытие первоначального обязательства в схеме. Кроме того,судья стирает все секретное прежде, чем послать c, и в особенности стирает случайные записи, используемые, чтобы произвести c. Таким образом, адаптивные искажения не дают никакой разницы ,потому что коммиттером не имеет секретного состояния и сразу с отправляется, и выявляет информацию перед отправкой . В действительности, для того, чтобы достичь этого свойства, все сообщения, отправленные до того не зависят от х, мы должны прикрепить к первому сообщению доказательства, используя совершенно скрываемую схему. Кроме того, она должна быть адаптивно безопасной в том, что злоумышленник, можете открыть его на все, что он хочет. К счастью, это может быть легко достигаться с помощью обязательств Педерсен C(х)= со значением h, что проявляется в CRS.3 Обратите внимание, что с учетом дискретного журнала h можно привести к любому нужному значению. В частности, совершить путем вычисления с= путь известен. Теперь, учитывая х мы хотим найти r такое, что с==*. При условии что h= это означает, что мы должны найти r, что =, или что то же самое r, что а = г + pх mod q . Таким образом, просто взять r = a - px mod q ). Заметим,что, все выше скаазанное он вводит дополнительные трудности, поскольку обоснованность протокола Sigma теперь опирается на твердость нахождения дискретного логарифма h. Это требует дополнительного сокращения; см доказательство для деталей.См протокол 3 для контура модифицированного протокола. ПРОТОКОЛ (шаблон -обязательство для адаптивного безопасности) Общие ссылки строка: (; , G, q, g; h), где является открытый ключ из CCA2-безопасной схемы шифрования, является открытым ключом из двойного криптографического режима и (G, q, g; h) параметры для схемы Педерсена. Передать фазы:

1. Коммитер вычисляет приверженность к x как , и отправляет в Педерсен приверженность C до приемника, используя (g;h)

2. Управляющий посылает; его приверженность первому сообщению из доказательства.

3. Коммитер отправляет доказательству Педерсен приверженность первого сообщения вычисленное из зашифрованного текста .

4. Приемник decommits к e, отправим в r.

5. Коммиттера проверяет , и вычисляет отвечает для протокола Sigma, основанный на (а e).

6. Коммиттера теперь стирает r случайности, используемый для генерации обязательств Педерсен, и наконец, посылает его в decommitment к приемнику.

Фаза decommitment:

1. Коммитер отправляет х, ( a; z), используемого для создания Педерсен приверженности.

2. Выходы приемника х, в докозательстве Педерсен приверженностью является принятие Сигма-протокола стенограммы.

Адаптивный протокол

Схема адаптивной безопасности подчисток проявляется в Протоколе 4. ПРОТОКОЛ 4 (UC-Secure Обязательство {Адаптивная стираний) Общие ссылки строки: (G, q, g1; g2; с; d; h; h1; h2; h), где все параметры такие, как в протоколе 2, и (G, q, g1, h) параметры для Педерсен обязательства.

После ввода (допустить, sid,ssid,,,x) где x ∈ и sid,ssid ∈ тогда работает следующим образом:

1. вычисляет m=G(x,sid,ssid,i,j) где i,j могут быть сопоставлены к а так в целом (х; sid; SSID; i; j) представляет собой N-битовую строку.

2. выбирает случайный r ∈ R Zq, вычисляет , , w = H(u1; u2; e) и и, где H хэш функция (формально, ключ для хэш-функция может появиться в CRS; мы игнорируем это для простоты). комплекты C = (u1; u2; u; v).

3. выбирает k ∈ R Zq вычисляет и посылает к

4. посылает с'=() к где е ∈ R и R,S ∈ R Zq

5. вычисляет ,, и и вычисляет Педерсен приверженность = где ∈ R Zq . посылает к

6. посылает (R,S,e) к

7. проверяет, что с'=() Если нет, то прерывает. В Противном Случае, вычисляет z=s+er.

8. стирает r и s, (х,a,b,c,d,,z). отправляет ( ; c) на .

9. проверяет, что = . Если да, то он хранит (sid, SSID; ; ;c ; e ;) и выходы (получения; sid;SSID; ; ). игнорирует любые последующие обязательства сообщения с тем же (sid; SSID) из .

Стадия декомпозиции:

1. После ввода (раскрыть; sid;SSID; ; ), отправляет (х; a; b; c; d; ; Z) с .

2. множеств m = G(х; sid; SSID; i; j) и выходы (раскрыть; sid;SSID;;; х) если и только если

= , ,,,

Мы используем эти обязательства чтобы совершить элементы группы в G. Тем не менее, ввод обязательство Педерсона в Zq, а не G. Одно решение этого состоит в том, чтобы разбить элементы на части и отдельно передают каждую часть. Мы используем другое решение, которое является для расчета С(m)=, где H-стойкие хеш-функции. Обязательство может быть открыто для любого значения.Разница лишь в том, что свойство связывания зависят теперь и от жесткости проблемы дискретного логарифма (как в стандартном случае) так и в столкновениях. По соглашению, в Протоколе 4, все сообщения отправляются вместе с (SID; SSID).

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

Доказательство безопасности

Теорема 2 Если предположить, что предположение DDH имеет в группе G, протокол 4 UC-надежно реализует функциональность в -гибридной модели, в наличии адаптивных противников с подчистками. Доказательство: Доказательство безопасности очень похоже на статический случай, с добавлением о том, как иметь дело с адаптивными коррупциями.

Заметим, что мы следуем конвенции где только часть сообщения не видел противник . Таким образом, когда честный посылает сообщение к функциональности , противник знает, какой тип послания есть, и кто является получателем. Из-за недостатка места и расширенных тезисов, мы наметим основное различие между доказательства здесь, и доказательства в статическом случае. Главное наблюдение состоит в том что, если при совершении файл поврежден и этап закончен, тогда информация никакой значимого не имела и была отдана даром. Это связано с использованием доказательства Педерсена и тем фактом, что тренажер сможет открыть их в любой момент по пожеланию, выбирая h так, как он знает ее дискретные логарифмы. Кроме того, если совершеные участником поврежденные фазы закончены, то случайность используется для генерации шифрования Крамера-Шоап и Сигма протокол, доказывающий что сообщения уже удалены. Таким образом, если тренажер запускает Сигма-протокол симулятор через доказательство делает заявление на основе полученного значения, и это будет выглядеть точно . В связи с этим моделирование и доказательство в этом случае адаптивных повреждений очень похожи на случай статических искажений. Однако, есть одно основное различие что касается последнего шага, где мы должны доказать обоснованность доказательства, предоставленного сторонами . .В частности, мы должны утверждать, что сторона может доказать неверное утверждение о незначительной вероятности. Для того, чтобы доказать это, мы сначала заменим двойной режим на ключ с альтернативной, как в статистическом доказательстве случая коррупции Тем не менее, это еще не достаточно, потому что противник может быть в состоянии доказать неправильное требование, разбив вычислительное связывание доказательств Педерсена (напомним, что последнее сообщение от доказывания decommitted только после решения задачи раскрывается) . Несмотря на это, мы используем тот факт, что способность к двум различным значениям эквивалентно найти дискретный логарифм H. Поэтому мы докажем обоснованность следующим образом. Предположим, что существует среда Z, противник А, а вход r до Z такая, что для бесконечно многих х, Удается доказать неверное заявление с непренебрежимо малой вероятностью. В этом случае удастся доказать неверное заявление, с которым нельзя пренебречь вероятность также в hyb-game3. (Отметим, что можно обнаружить это событие потому что мы можем расшифровать шифрованием Крамера-Shoup и посмотреть, какое значение было на самом деле зашифровано.) Итак, пусть (G; q; g1;h) будут параметры доказательства Педерсена . Противник пытаясь сломить в схеме получает параметры и работает следующим образом.

Он выбирает все значения в общей справочной строке как s (основанный на (G; q; g1)) и потом имитирует hyb-game3 эксперимент под управлением входного сигнала Z с Z и A. Если A доказывает неверное утверждение, то все выполненные операции( в том числеZ) повторяются, посылает другой (R', S'; e'). Отметим, что поскольку в этой точке открытого ключа для двухрежимной криптосистемы является альтернативной, и вернувший знает дискретные логарифмы , то может эффективно найти (R'; S'; e'), что с'=() хотя с' был первоначально порожден . (Для того, чтобы сделать это, также нужно знать дискретные журналы и G по отношению к G1, но это значение может быть выбрано таким образом. Смотрите объяснение конкретного двойного криптографического режима в конце раздела 3.1, с тем чтобы посмотреть, нужно решить уравнение, затем продолжает выполнение до точки, где А стенограммы. Видимо, по доказательству Педерсена может быть только один ответ e если заявление неверно e'. В этом случае подражали нашла дискретный журнал h и остановок. В противном случае, неоднократно перематывает до тех пор, пока не примет стенограммы. Это дает ожидаемое время противнику ; можно просто усечь время противнику на выполнения действия.Замечу, что хотя мы работаем в рамках UC, разрешена перемотка в сокращении, потому что это не имеет ничего общего с моделированием, и мы сокращаем разницу между hyb-гибрид game3 и твердости нахождения дискретных логарифмов в h.

Благодарности

Мы благодарим Канетти и Бенни Пинкас за полезные обсуждения.

Контакты авторов материала

  1. Department of Computer Science Bar-Ilang University, Israel, E-mail: lindell@cs.biu.ac.il

Примечание

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

Литература

  1. М. Bellare и П. Rogaway." Введение в современную Криптографию", Глава 7 (конспектов), 2007.
  2. . А. Бен-Давид, Н. Нисана и В. Пинькас. "Системы защищенной мульти- вычислений". стр. 257-266, 2008.
  3. Р. Канетти." Универсально комбинировать безопасности: новая парадигма для криптографических протоколов", стр. 136-145, 2001. Полная версия доступна в http://eprint.iacr.org/2000/067.
  4. Р. Канетти и Бенни Пинкас. "Универсально составляющие обязательства". В КРИПТО 2001, Спрингер (дискретный 2139), на страницах 19-40, 2001.