Функция с постоянной партией одновременно неподатлива статической привязке фиксациям и не фиксирована

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:52, 23 ноября 2015.
Constant-Round Concurrent Non-Malleable Statistically Binding Commitments and Decommitments
Constant-Round Concurrent Non-Malleable.png
Авторы Zhenfu Cao and Zongyang Zhang [@: 1] and
Ivan Visconti[@: 2]
Опубликован 2010 г.
Сайт Computer science research laboratory
Перевели Radik Nigamatzyanov
Год перевода 2015 г.
Скачать оригинал

__NUMBEREDHEADINGS__


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


Ключевые слова: Схема фиксаций, статическая привязка, неподатливость.

Введение

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

Хорошо известно, что основные свойства схем фиксаций не могут предотвратить "пластичность" атак, установленных противником среднестатистического человека (man-in-the-middle (MIM)), с помощью вероятностного полиномиального времени (probabilistic polynomial-time (PPT)), который к тому же имеет полный контроль канала связи между разработчиком и приемником. Концепция неподатливости впервые была введена Dolev и др.[1], чтобы обозначить проблемы безопасности в подобных условиях. Грубо говоря, схема фиксаций не является податливой, если нельзя преобразовать обязательство стоимости в обязательство связанной стоимости. Этот вид неподатливости называют неподатливостью относительно обязательства (non-malleability with respect to commitment (NMc, если коротко))[1]. Это определение основано на независимости переданных сообщений, воспроизведенных противником MIM относительно тех сообщений, которые были воспроизведены комитетом. Понятие неподатливости, которое используют Di Crescenzo и др.[2], называют неподатливостью относительно не фиксированности или отверстием (non-malleability with respect to decommitment (NMd, если коротко)), т.е., противник не может построить фиксацию со стороны данной, такой, что видя открытие первоначальной фиксации, он в состоянии правильно открыть свою фиксацию со связанной стоимостью. Это определение предполагает, чтобы вероятность успеха противника MIM находится в ведении автономного симулятора. Последующие NMC определения модифицированы аналогичным образом [3][4][5][6][7][8]. Основанные на моделировании определения намного более полезны, когда схема фиксаций используется в качестве стандартного блока в большем протоколе, так как существование простого симулятора в большой степени является задачей обеспечения безопасности большего протокола.

Интуитивно, кажется, что NMc надежнее, чем NMd. Однако это зависит от тонкости определений. В действительности, подобное не всегда имеет силу, по крайней мере, относительно определений неподатливости в [2][1][3]. В версии журнала [3], авторы [9] представили строгое определение неподатливости w.r.t фиксации, чтобы подразумевать понятие неподатливости w.r.t отверстия.

В некоторых предыдущих решениях обращалось внимание на проектирование статистически скрывающихся схем фиксаций, которыми являются NMd. На основании теоретико-числовых предположений, NMd схемы фиксации были разработаны в [10][3] предположении о существовании общей опорной строки (CRS), которая разделена этими двумя игроками перед выполнением протокола. Таким образом, их схемы не работают в обычной модели (т.е., без установки предположениях). Недавно, Pass and Rosen [4][5] представили несколько другое определение NMd [прим. 1][2][10][3][4][5][3]. Затем они построили схему фиксаций, в соответствии со своим определением NMd , основанным на семействе стойких к коллизиям хэш-функций в простой модели. Их схема - эффективная партия и нуждается лишь в постоянной партии связи. Совсем недавно, на основе работы [11][12], Zhang и др. [13] представили неподатливую схему фиксации в рамках самого слабого предположения, т.е., существование односторонних функций.

Перед работой [8], обычно считалось, что NMd (по сравнению с NMc) является единственным понятием, которое имеет смысл в вычислительном отношении обязательной схеме фиксаций [1]. Тем не менее, Островский и др. [8] утверждают, что путем небольшого ослабления определения NMc[прим. 2][1][3][9], NMc может быть также достигнуто для вычислительно обязательных схем фиксации. Они рассмотрели параллельные нападения MIM, где противник может одновременно участвовать в любом полиномиальном числе уничтожений как приемник и как разработчик. Основываясь на работе [6][7], и используя некоторые методы уже выведенные в [14][15] они дали вычислительное сокрытие и вычислительную обязательную схему фиксаций, которая является и параллельным NMc и параллельным NMd. В полной версии [8], они [16] также дали построение статистически скрывающейся схемы фиксации с постоянной партией, которая является параллельным NMd, и фактически состоит из упрощенного протокола по отношению к приведенному в [8]. Приведенные выше схемы предполагают существование семейства пар перестановок с трудно обнаружимыми зубцами, требуют лишь постоянного количества партий связи и предполагается, что этап фиксированной фазы и нефиксированной фазы, не совпадает во времени.

Для статистически обязательных схем фиксаций, первый NMc был разработан Dolev и др. [1] в предположении существования односторонних функций. Однако схема требует партий, где - параметр безопасности. В модели CRS, Di Crescenzo и др. [10] построили очень эффективные схемы обязательств NMc, основанные на любом открытом ключе криптосистемы, которая неподатлива при атаке с выбором открытого текста в дополнение к любому общему ключу криптосистемы, который обладает неразличимостью при нападении оракула на не зашифрованный CCA-post. Pass и Rosen [4][5] первыми представили схему фиксаций NMc с постоянной партией в простой модели, принимающую существование столкновения стойких хэш-функции. Pass и Rosen [6][7] тогда показали, что схема NMc [4][5] является фактически одним параллельным NMc в соответствии с более сильным, основанным на моделировании, определением [прим. 3][6][7][2]. Доказательства безопасности [4][5][6][7] требуют использования нечерного ящика кодексом противника и кроме того один из [6][7] предполагает, что фаза фиксации и нефиксированная фаза не перекрываются во времени. Lin и др. [12] пересмотрели схему [1] и представили параллельную схему NMc фиксаций, используя только методы черного ящика. Их схема требует полиномиального числа коммуникационных партий и основана на минимальном предположении, т.е., существование односторонних функций. В дополнение к вышеупомянутым результатам, сосредотачивающимся на NMc, единственный из них, который явно требовал схем обязательства NMd, был разработан в [9] в модели CRS.

Перед разъяснением [8], есть одно фольклорное поверье о статистически обязательной схеме фиксаций, состоящая в том, что, если это - NMc тогда, это - NMd. Однако, по крайней мере, это не может быть выведено только из основанных на моделировании определений в [4][5][6][7] в простой модели [прим. 4][8]. Основная проблема состоит в том, что вероятность успеха автономного симулятора зависит от того, насколько он близко к вероятности успеха противника MIM [8]. Напомним, в доказательстве NMc [4][5][6][7], автономный симулятор внутренне моделирует оставленное взаимодействие для противника MIM, передавая поддельную стоимость . Кажется, что этот симулятор не может обработать доказательство NMd, потому что после получения фиксированной стоимости , симулятор застревает, чтобы открыть ложную фиксацию .

Поэтому, достигая одновременно параллельного NMc и NMd в постоянном числе партий и в рамках понятий моделирования, работа [8] достигает самой сильной безопасности для схем фиксаций в простой модели. Однако схема связана только в вычислительном отношении. Когда безопасность приемников представляет большой интерес в некоторых прикладных сценариях, этого может не быть достаточно. Таким образом, остается открытым вопрос относительно того, существует ли статистически обязательная схема фиксаций с постоянной партией, которая является и параллельным NMc и параллельным NMd, в простой модели, в соответствии с более сильным основанным на моделировании определением [6][5][6][7][8].

Наш вклад

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

TemplateTheoremIcon.svg Теорема Теорема 1
Предположим, что существует семейство пар перестановок с трудно обнаружимыми зубцами. Тогда существует статистически обязательная схема фиксаций с постоянной партией, которая является и параллельным NMc и параллельным NMd.
Доказательство
Без доказательств.


На представлении высокого уровня фаза фиксаций нашей схемы почти идентична с этим в [8]. Методы, используемые на этой стадии также одинаковы. Точнее, в дополнение к методу, используемому в [4][5][6][7], здесь также используется метод двух свидетелей Feige [17]. Наш вклад заключается в модификации открытой фазы, чтобы одновременно достигнуть параллельного NMd и статистического обязательного свойства. Мы заимствуем идею [18] в проектировании параллельных доказательств с нулевым раскрытием конфиденциальных сведений, т.е., мы позволяем разработчику предположить частные ценности, зафиксированные приемником в фазе фиксаций, и затем использовать неразличимую от свидетеля систему доказательства, чтобы доказать тщательно разработанное заявление. Таким образом, схема гарантирует, что будет препятствовать, неограниченному открытию фиксации любым противник двумя различными способами. Наша работа может рассматриваться как дополнение к работе [8]. Обе работы решают вопросы неподатливости против одновременных атак среднестатистического человека и достижения того-же-самого-уровня безопасности в простой модели. Основное различие между двумя результатами заключается в том, что работа [8] фокусируется в основном на вычислительных обязательных схемах фиксаций, в то время как наша работа рассматривает их как статистически обязательные. По сравнению с работой [6][7], наша работа также достигает и параллельного NMc и параллельного NMd, тогда как они достигают лишь параллельного NMc. Мы подчеркиваем здесь, что наша схема наследовала ограничение от [6][7][8], т.е., доказательство неподатливости в большой степени полагается при условии, что фиксированная фаза и нефиксированная фаза не накладываются во времени.

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

Мы предполагаем, что читатель знаком с неразличимыми от свидетеля протоколами, нулевыми протоколами знаний и схемами фиксаций. Для получения дополнительной информации читатель может обратиться к [19] для справки.

Параллельная Неподатливость Фиксаций и Не фиксаций

Далее, мы формулируем определение параллельного NMc и параллельного NMd. Как указано в [6][7] мы формализуем понятие неподатливости сравнивая между действиями среднестатистического человека и моделируемым действием. Пусть будет схема фиксаций. Пусть будет параметром безопасности.


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

Пусть случайная величина принимает значения , которую противник зафиксировал в правой итерации. Если правая фиксация перестала работать, или расшифровка его стенограммы (фазы фиксации) равняется расшифровке стенограммы левой итерации, значение установлено в .

Точно так же мы позволяем случайной величине , принимать значения , которые были открыты противником в правой итерации. Если сбои справа фиксирован или нефиксирован, или расшифровка его стенограммы (и фиксированная фаза и нефиксированная фаза) равняются расшифровке стенограммы левой итерации, значение установлено в .

Моделируемое выполнение. В моделируемом выполнении средство моделирования непосредственно взаимодействует с честным получателем в итерациях. Как и в действиях MIM, вектор значения , выбран до взаимодействия, и принимает некоторую предварительную информацию о как часть ее вспомогательного ввода . Сначала выполняет фиксированные фазы с . Как только все фазы фиксаций были завершены, получает вектор значения и пытается дефиксироваться к значениям .

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

TemplateDifinitionIcon.svg Определение «Определение 1 (Параллельная Неподатливость Фиксации со ссылкой на Фиксацию [6][7]

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

TemplateDifinitionIcon.svg Определение «Определение 2 (Параллельная Неподатливость Фиксации со ссылкой на Не Фиксацию)»

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

Схема фиксаций, которая неподатлива согласно Определению 2, либерально неподатлива, а не строго неподатлива [1][3]. Обратите внимание на то, что мы следуем лишь [4][5][8] где неподатливости гарантируется, только если фиксированная фаза и нефиксированная фаза не накладываются во времени.

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

Статистически Фиксированная Параллельная NMc с Постоянной Партией и Параллельный NMd

В этом разделе мы представляем статистически обязательную схему фиксаций с постоянной партией, которая является параллельным NMc и параллельным NMd. Обозначим через SBCom статистически обязательную схему фиксации от любой односторонней функции [20]. Обозначим через SHCom статистически скрываемую схему фиксаций из любой коллекции пар перестановок с трудно обнаружимыми зубцами с эффективно узнаваемым множеством индексов [21]. Обозначим через , основанный на признаке совершенный неподатливый аргумент нулевого знания (NMZKAOK) с постоянной партией для NP [4][5]. Обозначим через статистически неразличимый от свидетеля аргумент знания (WIAOK) с постоянной партией для NP [22][23] [прим. 5][22][21]. Пусть будет в вычислительном отношении неразличимым от свидетеля доказательством знания (WIPOK) с постоянной партией для NP. Пусть будет сильной схемой подписи. Схема фиксации показана на Рис. 1. Обратите внимание на то, что все инструменты, используемые выше, могут быть достигнуты, приняв существование семьи пар перестановок с трудно обнаруживаемыми зубцами.

Наша схема фиксаций является одним вариантом статистического связывания в [8]. Фаза фиксации почти идентична схеме фиксации в [8] за следующим исключением: на Этапе 2, получатель использует статистически скрывающуюся схему фиксации SHCom вместо её статистической привязки. Это также вызывает статистический WIAOK вместо вычислительного WIPOK. Грубо говоря, на Этапе 1, разработчик вырабатывает фиксацию к и доказывает знания открытием . На Этапе 2, получатель генерирует две фиксации к двум секретам , исходя из этого, он доказывает знание любого секрета. Этап 3, до настоящего времени разработчик вырабатывает подпись на транскриптор, и затем получатель проверяет правильность подписи.

Нефиксированная фаза является более сложной и требует более тщательной разработки. Основная трудность заключается в одновременном достижении параллельного NMd и статистических обязательных свойств. Мы вдохновлены работой [18] на параллельных доказательствах нулевого знания. Мы изменяем схему в [8], позволяя разработчику отгадать приватные значения, зафиксированные в фазе фиксации и затем использовать WIPOK, чтобы доказать тщательно разработанный OR операторов. Конструкция использует метод с двумя свидетелями Feige [17] и известный FLS-метод [24]. Грубо говоря, в Этапе 1', разработчик сначала генерирует фиксацию к фиктивной стоимости . После получения , получатель открывает значения , зафиксированные в фазе фиксаций и доказывает знание открытием любой фиксации или . В Этапе 2', судья отправляет зафиксированное значение и выполняет вычислительный WIPOK, чтобы доказать оператору, что или - приверженность , или - приверженность или . В Этапе 3', разработчик доказывает, что - приверженность , или открывает к знание для некоторых . Этап 4', до настоящего времени разработчик вырабатывает подпись на транскриптор, и затем получатель проверяет правильность подписи. Обратите внимание, что FLS-метод используется как на Этапе 2' и Этапе 3'.

Протокол
Параметр безопасности:
Последовательность, которая будет фиксироваться:
Фиксированная фаза:
Этап 1:
Пусть (). Выберем однородное и вычислим . Получаем , .
использует свидетеля и доказывает с помощью (с тегом ) утверждение, что существуют такие значения , что .
Аварийное прекращение работы, если вышеупомянутое доказательство перестало работать.
Этап 2:
Выберем однородное и вычислим , . Получим .
Выберем случайный бит . применяет свидетелей и доказывает использование чтобы найти значения такие что или
Аварийное прекращение работы, если вышеупомянутое доказательство перестало работать.
Этап 3:
Пусть расшифровка стенограммы вышеупомянутой итерации. Вычислим и получим .
Убедимся, что .
Нефиксированная фаза:
Этап 1':
Выберем однородное . Вычислим и получаем .
Получаем .
использует свидетеля и доказывает с помощью (с тегом ) утверждение, что существует значение , что или .
Аварийное прекращение работы, если вышеупомянутое доказательство перестало работать.
Этап 2':
Получаем
использует свидетеля и доказывает использование следующих операторов:
такой что
такой что
Аварийное прекращение работы, если вышеупомянутое доказательство перестало работать.
Этап 3':
использует свидетеля и доказывает с помощью (с тегом ) утверждение, что либо существует ,такое что , либо существуют ,такое что .
Аварийное прекращение работы, если вышеупомянутое доказательство перестало работать.
Этап 4':
Пусть расшифровка стенограммы вышеупомянутой итерации. Вычислим и получим .
Убедимся, что .

Рис 1. Параллельная неподатливая статистически фиксированная схема фиксации .

TemplateTheoremIcon.svg Теорема Теорема 2
Допустим, что SBCom - статистически обязательная схема фиксации, SHCom - статистически скрывающаяся схема фиксации и сильная схема подписи. Предположим, что один из многих параллельных совершенных для , статистическое для и , вычислительное для . Тогда , статистически обязательная схема фиксаций, которая и параллельная и параллельная .
Доказательство

Мы должны доказать, что схема удовлетворяет следующим трем свойствам: вычислительное сокрытие, статистическая привязка, и параллельный NMc и параллельный NMd.

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

Статистическая привязка. Доказательство свойство привязки является более тонким. Мы показываем, что любой вредоносный противник не может нарушить свойство привязки . Интуитивно ясно, если может открыть фиксацию двумя различными способами, то из-за свойства разумности и статистическое свойство привязки SBCom, должен использовать поддельного свидетеля в выполнении в Этапе 2', т.е., свидетеля которому известно, что - приверженность или . Обратите внимание, что единственное место, что может узнать про или до Этапе 1' это в Этапе 2 фиксированной фазе. Так как обе фиксации являются статистически скрытыми и является статистическим WI, узнает или лишь с незначительной вероятностью на Этапе 2. Таким образом, создает фиксацию к значению или только с пренебрежимо малой вероятностью в Этапе 1'. Кроме того, фиксирует используя SBCom. Таким образом, второе утверждение, доказанное в Этапе 2', является ложным (даже для неограниченной машины). Согласно свойству , даже неограниченное не может успешно выполнить доказательство с не незначительной вероятностью в Этапе 2'. Этим достигается противоречие.

Более подробно, предположим для противоречия, что там существует некоторый противник (не обязательно PPT) , который в состоянии нарушить свойство привязки . Мы покажем, как создать алгоритм (не обязательно PPT) , который нарушает свойство привязки SBCom или скрывающееся свойство SHCom или свойство WI . взаимодействует с и следует честной стратегии получателя. Как только нефиксированная фаза закончена, служит извлекающим устройством в Этапе 2' получаем свидетеля . Тогда должно быть верно, что:

(1) SBCom().
(2) SBCom().
(3) SBCom().

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

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

Наконец, мы показываем, что случай 3 происходит с незначительной вероятностью. Предположим обратное, что это происходит с не незначительной вероятностью SBCom (). Тогда мы проектируем алгоритм , который нарушает свойство привязки SHCom. На входе сомнительной фиксации (к значению ), должен решить, какое значение соответствует . проводится точно так же как и со следующими двумя исключениями. Первое исключение это обработка взаимодействия в Этапе 2 с фиксацией. Здесь впервые берет случайный бит , случайную последовательность и универсальную случайную последовательность . Тогда вычисляет SBCom () и наборы . Далее продолжает выполнение Этапа 2 с фиксацией, следуя честной стратегии программы автоматического доказательства , использующую () как свидетеля. Второе исключение заключается в обработке взаимодействия в Этапе 1' с не фиксацией. Здесь в произвольном порядке выбирает немного , отправляет к и затем использует свидетеля , чтобы завершить доказательство . Наконец, если свидетель извлекает удовлетворяющую SBCom (), тогда имеет выводы ; иначе, вывод для случайно выбранных . Поэтому вероятность того, что нарушает свойство привязки SHCom также не является незначительным.

Параллельная неподатливость. Мы должны показать, что схема параллельная NMc и параллельная NMd. Доказательство параллельного NMc почти идентична доказательства в [8]. Примечание NMc касается только фиксированной фазы и как мы обсуждали ранее, фиксированная фаза нашей схемы отклоняется от работы [8] лишь, когда передает фиксацию и воспроизводит WIAOK в Этапе 2. Действительно, в нашей схеме мы используем статистические версии этих инструментов, в то время как протокол [8] имеет потребность лишь в вычислительной версии. Однако, доказательство складывается точно также как и [8]. Здесь мы опускаем детали и откладываем доказательство в полной версии.

Далее, мы показываем, что оно параллельно NMd. Мы покажем, что для каждого среднестатистического человека PPT противника , который участвует в левой части фиксации и в правой части фиксации, существует ожидаемое средство моделирования PPT такое, что для каждого PPT есть различная , и каждая незначительная функция, для каждого значения вектора , где и для каждого , то считается, что

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

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

Как только все фиксированные фазы закончены, получает вектор значения , и должен выполнить нефиксированную фазу внутри с . следует честной стратегии получателя во всех правых фиксациях. Симуляция левой части не фиксации заключается в следующем. В Этапе 1', действует тождественно как честный разработчик за исключением того, что передает вместо (использующий случайность ). В Этапе 2', следует честной стратегии разработчика за исключением того, что это использует "поддельного" свидетеля для открытия приверженности . В Этапе 3', использует поддельного свидетеля для завершения доказательства. следует честной стратегии судьи в Этапе 4'. Наконец, для каждого , если успешно завершил правой части не фиксации, то завершает нефиксированную фазу внешнего решения с честными получателями, открывая фиксацию .


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

Затем, мы доказываем, что распределение сообщений, открытых при взаимодействии с честными разработчиками и честными получателями, неотличимо от распределения сообщений, открытых при взаимодействии с .

Неразличимость моделирования. Сначала мы рассматриваем случай, когда есть только одно левая фиксация и правая фиксация . Представление Уравнения (1) (примечание содержит только значение ), мы определяем последовательность гибридных экспериментов , которые получают и как вспомогательные вводы. Вывод каждого эксперимента - вывод PPT различной на вводе значение и вектора значений , чей элемент определен следующим образом. Если правой не фиксаций завершается успешно, и если расшифровка его стенограммы отличается от левого итерации, то - значение, открытое в правой итерации. Иначе, установлен в . Пусть .

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

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

действует точно также как и за исключением того, что он выполняет средство моделирования в Этапе 3' левой не фиксации. Это следует из совершенного свойства нулевого знания что .

отличается от (HYB3), в котором используется настоящий свидетель (т.е., не фиксации ), чтобы завершить доказательство в Этапе 2' левой не фиксации. Это следует из вычислительного свойства , что незначительно.

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

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

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

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

Наконец мы завершаем Уравнение (1). Это завершает доказательство Теорема 2.

Утверждение 1 В реальной игре не может открыться по-другому.

Доказательство. Предположим, что, с некоторой вероятностью , существует таким образом, что значение открытый в праве не фиксаций отличается от значения фиксировавший в правой фиксаций[прим. 6]. Мы обозначаем фиксацию , взятые на себя в Этапе 2 правой фиксации. Обозначим через бит, таким образом, что использует информацию о не фиксации, соответствующую фиксации , чтобы завершить доказательство в Этапе 2 и Этап 1' правой фиксации. Если успешно завершает правой не фиксации, то мы рассматриваем следующий эксперимент . на вводах и взаимодействует с и работает следующим образом. Мы позволяем передать в левой фазе фиксации. Кроме того, следует честной стратегии разработчика в левой итерации и честной стратегии получателя, в порядке, взаимодействия, кроме не фиксации Этапа 1', отправляет и в произвольном порядке выбирает (С подавляющей вероятностью будут отличаться от выбранной в фазе фиксации. Это важно для доказательства Случая 3 ниже.). После того как правая фиксация закончена, работает как извлекающее устройство в Этапе 3'. Обратите внимание на то, что представления в реальном выполнении и выполнении идентичны. Таким образом, вероятность, которая открывается по-другому в выполнении , также . Согласно свойству извлечения , с вероятностью то, где незначительная функция, , получает свидетеля , и должен произойти один из следующих трех случаев:

1. . ( фиксация, сгенерированное в правой фиксации.)
2. . (, значения, открытые в Этапе 1' правой не фиксации.)
3. .

Пусть , где - вероятность, Случай который происходит (для ). Статистическим обязательным свойством SBCom мы имеем, что должно соответствовать , и таким образом в этом случае не открывается по-другому, поэтому должен быть незначительным. Напомним в правой фиксации, уже создает фиксацию и к двум различным значениям и соответственно и использует знание о не фиксации из для случайного бита в обоих из Этапа 2 и из Этапа 1'. Из статистического свойства сокрытия SHCom и статистического свойства , мы имеем, что по сути идентично , и поэтому и и примерно соответствуют , где - незначительная функция.

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

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

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

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

Поэтому, нарушает один - многие параллельные неподатливости .


Заключительные Примечания

Наш результат поверх предыдущей работы показывает, что там существуют схемы фиксации с постоянными партиями, которые безопасны также против очень мощных противников, пока есть преграда во времени между фиксированной и не фиксированной фазой. Интересный нерешенный вопрос касается возможности достижения схем фиксации, которые остаются безопасными даже без такой преграды. Вопрос интересен даже, не требуя сложности функции с постоянной партией[прим. 7][25][26].

Благодарности. Мы благодарим анонимных рецензентов за их полезные предложения. Работа первых и третьих авторов поддерживается частично Национальной Основой Естествознания Китая под предоставлением № 60773086, № 60972034 и № 60970110. Работа второго автора поддерживалась частично Европейской комиссией через программу ICT EU в соответствии с Контрактом ICT-2007-216646 ECRYPT II, и частично грантом на проведение исследований, полученным от Provincia di Salerno.

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

  1. Department of Computer Science and Engineering, Shanghai Jiao Tong University, P.R.China E-mail: {fzfcao,zongyangzhangg}@sjtu.edu.cn
  2. Dipartimento di Informatica ed Applicazioni, University of Salerno, ITALY E-mail:visconti@dia.unisa.it

Примечание

  1. Более точные определения NMd в [2, 10] не принимают во внимание возможную априорную информацию, которую противник мог бы иметь о фиксации, полученной в левой итерации, в то время как определение в [3-5] это учитывает. Определения в [2, 10, 3] не обеспечивают автономного средства моделирования значения, фиксировавшуюся в левой итерации после того, как фаза фиксации закончена, в то время как определения в [4, 5] это учитывает.
  2. Значения, переданные противником в выполнении MIM, уникально определены для всех алгоритмов в определении NMc, но только для алгоритмов PPT в непринужденном определении. Позже, определение NMc, сформулированное в , может также быть применено в вычислительном отношении обязательной схеме фиксации.
  3. Определение NMd в [6, 7] более сильное, чем в [2]. Первое - основано на неразличимости определения, т.е., там существует автономное средство моделирования PPT, передающее значение, которое в вычислительном отношении неотличимо от значения, переданного противником MIM. Последнее - основано на отношении определения, т.е., автономное средство моделирования, менее вероятно, передаст значение, удовлетворяющее любому полиномиально-разовому вычислимому отношению, чем значение, переданное противником MIM.
  4. В модели CRS нет никакой проблемы. Читатель рецензируется к [8] для получения дополнительной информации.
  5. Основной протокол Blum для Hamiltonicity [22] - только вычислительное нулевое знание с разумной ошибкой 1/2. Кроме того, протокол включает три раунда взаимодействия. При запуске базового протокола полиномиальное число раз параллельно, мы получаем вычислительный WIPOK для Hamiltonicity. Если программа автоматического доказательства использует статистически скрывающуюся схему [21] фиксации в первой партии, то мы получаем статистический WIAOK для Hamiltonicity.
  6. Переданное значение является уникальным и однозначно задается статистически обязательной схемой фиксации SBCom.
  7. Действительно, в этом случае можно было также использовать неподатливый параллельный нулевой параметр знаний и также, когда требуется некоторая эффективность.

Литература

  1. 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 Dolev, D., Dwork, C., Naor, M.: Nonmalleable cryptography. SIAM J. Comput.30(2) (2000) 391-437
  2. 2,0 2,1 2,2 2,3 Crescenzo, G.D., Ishai, Y., Ostrovsky, R.: Non-interactive and non-malleable commitment. In: STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, New York, NY, USA, ACM (1998) 141-150
  3. 3,0 3,1 3,2 3,3 3,4 3,5 3,6 3,7 Fischlin, M., Fischlin, R.: Efficient non-malleable commitment schemes. In Bellare, M., ed.: CRYPTO. Volume 1880 of Lecture Notes in Computer Science., Springer (2000) 413-431
  4. 4,00 4,01 4,02 4,03 4,04 4,05 4,06 4,07 4,08 4,09 4,10 Pass, R., Rosen, A.: New and improved constructions of non-malleable cryptographic protocols. In Gabow, H.N., Fagin, R., eds.: STOC, ACM (2005) 533-542
  5. 5,00 5,01 5,02 5,03 5,04 5,05 5,06 5,07 5,08 5,09 5,10 5,11 Pass, R., Rosen, A.: New and improved constructions of nonmalleable cryptographic protocols. SIAM J. Comput. 38(2) (2008) 702-752
  6. 6,00 6,01 6,02 6,03 6,04 6,05 6,06 6,07 6,08 6,09 6,10 6,11 6,12 6,13 6,14 Pass, R., Rosen, A.: Concurrent non-malleable commitments. In: FOCS, IEEE Computer Society (2005) 563-572
  7. 7,00 7,01 7,02 7,03 7,04 7,05 7,06 7,07 7,08 7,09 7,10 7,11 7,12 7,13 Pass, R., Rosen, A.: Concurrent nonmalleable commitments. SIAM J. Comput.37(6) (2008) 1891-1925
  8. 8,00 8,01 8,02 8,03 8,04 8,05 8,06 8,07 8,08 8,09 8,10 8,11 8,12 8,13 8,14 8,15 8,16 8,17 8,18 8,19 8,20 8,21 Ostrovsky, R., Persiano, G., Visconti, I.: Simulation-based concurrent non-malleable commitments and decommitments. In Reingold, O., ed.: TCC. Volume5444 of Lecture Notes in Computer Science., Springer (2009) 91-108
  9. 9,0 9,1 9,2 Fischlin, M., Fischlin, R.: Efficient non-malleable commitment schemes. J. Cryp- tology 22(4) (2009) 530-571
  10. 10,0 10,1 10,2 Di Crescenzo, G., Katz, J., Ostrovsky, R., Smith, A.: Efficient and non-interactive non-malleable commitment. In Pfitzmann, B., ed.: EUROCRYPT. Volume 2045 of Lecture Notes in Computer Science., Springer (2001) 40-59
  11. Haitner, I., Reingold, O.: Statistically-hiding commitment from any one-way function. In Johnson, D.S., Feige, U., eds.: STOC, ACM (2007) 1-10
  12. 12,0 12,1 Lin, H., Pass, R., Venkitasubramaniam, M.: Concurrent non-malleable commitments from any one-way function. In Canetti, R., ed.: TCC. Volume 4948 of Lecture Notes in Computer Science., Springer (2008) 571-588
  13. Zhang, Z., Cao, Z., Ding, N., Ma, R.: Non-malleable statistically hiding commitment from any one-way function. In Matsui, M., ed.: ASIACRYPT. Volume 5912 of Lecture Notes in Computer Science., Springer (2009) 303-318
  14. Ostrovsky, R., Persiano, G., Visconti, I.: Concurrent non-malleable witness indistinguishability and its applications. Electronic Colloquium on Computational Complexity (ECCC) 13(95) (2006)
  15. Ostrovsky, R., Persiano, G., Visconti, I.: Constant-round concurrent non-malleable zero knowledge in the bare public-key model. In Aceto, L., Damgart, I., Goldberg, L.A., Halldorsson, M.M., Ingolfsdottir, A., Walukiewicz, I., eds.: ICALP (2). Volume 5126 of Lecture Notes in Computer Science., Springer (2008) 548-559
  16. Ostrovsky, R., Persiano, G., Visconti, I.: Concurrent non-malleable commitments and decommitments. Full version, unpublished manuscript (2009)
  17. 17,0 17,1 Feige, U.: Alternative Models for Zero Knowledge Interactive Proofs. PhD thesis, The Weizmann Institute of Science, Rehovot, Israel (1990)
  18. 18,0 18,1 Richardson, R., Kilian, J.: On the concurrent composition of zero-knowledge proofs. In: EUROCRYPT. (1999) 415{431
  19. Goldreich, O.: Foundations of Cryptography Volume II Basic Applications. Cambridge University Press (2004)
  20. Naor, M.: Bit commitment using pseudorandomness. J. Cryptology 4(2) (1991) 151-158
  21. 21,0 21,1 Goldreich, O., Kahan, A.: How to construct constant-round zero-knowledge proof systems for NP. J. Cryptology 9(3) (1996) 167-190
  22. 22,0 22,1 Blum, M.: How to prove a theorem so no one else can claim it. In: Proceedings of the International Congress of Mathematicians. (1986) 1444-1451
  23. Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: STOC, ACM (1990) 416-426
  24. Feige, U., Lapidot, D., Shamir, A.: Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput. 29(1) (1999) 1-28
  25. Barak, B., Prabhakaran, M., Sahai, A.: Concurrent non-malleable zero knowledge. In: FOCS, IEEE Computer Society (2006) 345-354
  26. Ostrovsky, R., Pandey, O., Visconti, I.: Efficiency preserving transformations for concurrent non-malleable zero knowledge. In Micciancio, D., ed.: TCC. Volume 5978 of Lecture Notes in Computer Science., Springer (2010) 535-552