Циклический коэффициент сложности доказуемого разделения секретной информации между несколькими лицами: статистический случай

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:08, 30 ноября 2015.
The Round Complexity of Verifiable Secret Sharing: The Statistical Case
Multi-query Computationally-Private Information Retrieval with Constant Communication Rate.PNG
Авторы Ranjit Kumaresan, Arpita Patra, and C. Pandu Rangan
Опубликован Dept. of Computer Science University of Maryland 2 Dept. of Computer Science IIT Madras
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал
Аннотация.. Мы рассматриваем циклический коэффициент сложности базовой криптографической задачи: доказуемое разделение секретной информации между несколькими лицами (ДРСИНЛ). Хорошо изученное элементарное действие обеспечивает хороший «контрольный пример» для понимания того, что из себя в целом представляет округлённый коэффициент сложности; более того, ДРСИНЛ важно само по себе как центральное элементарное звено, например, для злоумышленного соглашения или протокола конфиденциального вычисления.Округлённый коэффициент сложности идеального ДРСИНЛ был выведен Геннаро и др. (STOC 2001) и Фитци и др. (TCC 2006). В результате неожиданно для всех Патра и др. (Crypto 2009) недавно показал, что предыдущие предельные значения больше не применяются, если допускается незначительная возможность ошибки. Мы решили оставить открытыми ключевые вопросы их работы и в частности безошибочно определить округлённый коэффициент статистического ДРСИНЛ с оптимальной предельной величиной. Пусть n обозначает количество команд, большинство t которых умышленные. Их работа показывает, что дважды округлённое статистическое ДРСИНЛ невозможно при . Мы показываем, что трижды округлённое статистическое ДРСИНЛ возможно, если . Мы также предлагаем четырежды округлённый протокол при .

Введение

Округлённый коэффициент сложности криптографических протоколов является основной мерой измерения их эффективности и стал предметом внимательного изучения. В данной работе нас интересует понимание округлённого коэффициента сложности ДРСИНЛ[1]. Здесь существует распространитель, который распределяет секретную информацию среди группы команд , большая часть которых (возможно включая и распространителя) может быть умышленной. Требования (грубо говоря) таковы, что если распространитель подлинный, то никакой информации о тайне распространителя для умышленных команд math>t \, \! </math> не будет выявлено к концу фазы распределения; тем не менее, к концу фазы распределения даже поддельный распространитель окончательно связан с некоей величиной, которая будет выявлена подлинными командами в фазе реконструкции. К тому же если распространитель является подлинным, эта присвоенная величина должна быть идентична исходному вводу распространителя.

Мы фокусируемся на информационно-теоретическом ДРСИНЛ, в котором требования безопасности должны выполняться даже когда умышленные команды обладают неограниченно вычислительной мощностью. Здесь могут быть рассмотрены две различные возможности: или требования безопасности выполняются идеально (например, всегда), или требования безопасности выполняются статистически, но возможно могут быть нарушены незначительной вероятностью. При рассмотрении широковещательных каналов, идеальное ДРСИНЛ возможно только в том случае, если [2] [3] в то время, как статистическое ДРСИНЛ возможно вплоть до параметров [4].

Округлённый коэффициент сложности идеального ДРСИНЛ подробно изучается. В случае оптимального параметра (например, ) Геннаро и др. [5] показал 3 цикла необходимых и достаточных для идеального ДРСИНЛ и предложил 4-цикловый протокол для задачи. 3-цикловый протокол ДРСИНЛ Геннаро и др. требует обмена информацией, увеличивающейся в геометрической прогрессии в количестве систем воспроизведения, но Фитци и др. [6] позже продемонстрировал, что возможен 3-цикловый эффективный протокол. Кац и др. [7] показал, что идеальное ДРСИНЛ могло бы быть достигнуто с помощью оптимального циклического коэффициента сложности и в то же время оптимального использования широковещательных каналов.

3-цикличная сниженная граница Геннаро и др. в общем, также предполагалось применять в случае статистического ДРСИНЛ. Поэтому было удивительно, когда Патра и др. [8] недавно показали, что статистическое ДРСИНЛ могло быть реализовано в двух циклах для . Протокол Патра и др. не применяется, когда, и поиск минимально цикличного протокола для оптимального параметра безопасности в их работе остаётся открытым. С другой стороны работа Патра и др. доказывает, что 2-цикличное статистическое ДРСИНЛ невозможно для , которое конечно также применяется для наших условий.

Наши результаты и условия работы. В этой работе мы анализируем цикличный коэффициент сложности статистического ДРСИНЛ с оптимальным параметром . Мы показываем, что 3-цикличное статистическое ДРСИНЛ возможно для любого t < n/2. Мы также даём эффективный 4-цикличный протокол для .

Модель и определения

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

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

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

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

TemplateDifinitionIcon.svg Определение «Определение - Определение 1»
. Двухфазовый протокол для команд , где отличающийся распространитель содержит исходный ввод , является -статистическим протоколом ДРСИНЛ допускающим умышленные команды , если для каждого нарушителя контролирующего большинство команд применяются следующие условия:

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

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

  1. В конце фазы распределения совместное представление подлинных команд определяет величину как для каждой подлинной .
  2. Если во время выполнения распространитель является подлинным, тогда .
На заметку: Наше определение статистического ДРСИНЛ ослабляет требование правильности/обязательности, но не требование безопасности. Это определение прежде было рассмотрено в литературе и является определением, которое достигают наши протоколы.

Мульти-контрольный протокол информационной проверки

Наши протоколы опираются на то, что известно как (под)протокол проверки информации (ППИ/ICP), термин, впервые представленный Ребином и Бен-Ором [4]. Традиционное определение ППИ [4] [9] включает в себя распространителя , промежуточным целым числом (INT) и устройством верификации . В исходной фазе распространитель передаёт секретную величину целому числу и некоторую контрольную информацию (которая ничего не говорит о ) – . Позднее получает от целого числа наряду с «доказательством» того, что действительно является величиной, первоначально полученной целым числом от .


Базовое определение ППИ включает в себя только одно устройство верификации; Патра и др. [10] [11] расширяет это определение, чтобы позволить каждой команде в сети действовать в качестве устройства верификации. Определяя ППИ таким образом (например, допуская множественные устройства верификации) будет полезным, когда мы используем объект исследования с неизвестными свойствами в наших ДРСИНЛ протоколах. Формально ППИ состоит из трёх уровней Distr, AuthVal и RevealVal:

  • Distr(D, INT, ) вводится , используя ввод некоей величины . Алгоритм создаёт некоторую идентификационную информацию (которая включает само ), которая передана INT, также как некоторая контрольная информация передаётся каждому устройству верификации.
  • AuthVal(D, INT, ) вводится INT после получения идентификационной информации от . Информация, которой обладает INT после этой стадии, называется IC-подпись и обозначается ICSIG(D, INT, s).
  • RevealVal(D, INT, ) является подпротоколом, в котором все сообщения широковещательные. Основанный на широковещательных сообщениях, ICSIG(D, INT, s) либо принимается, либо отвергается всеми подлинными верификационными устройствами (с большой вероятностью).

ППИ должен отвечать следующим требованиям:

  1. Правильность 1: Если и INT подлинные, тогда каждое подлинное устройство верификации принимает ICSIG(D, INT, s) во время RevealVal.
  2. Правильность 2: Если INT подлинный, то в конце AuthVal INT обладает ICSIG(D, INT, s), который будет принят в RevealVal каждым подлинным устройством верификации, кроме вероятности .
  3. Правильность 3: Если подлинное, тогда во время RevealVal с вероятностью как минимум ICSIG(D, INT, s) будет получено повреждённым INT как и отвергнуто каждым подлинным устройством верификации.
  4. Секретность: Если и INT подлинные, тогда до конца AuthVal нарушитель не будет обладать никакой информацией о s.

Протокол ППИ

Здесь мы представляем упрощённую версию протокола ППИ (от Патра и др. [10] [11] ), допускающий умышленных операций, так что Distr требует один цикл, а AuthVal и RevealVal требуют два цикла каждый. Мы опускаем доказательства ввиду уменьшения места.

Distr(D, INT, s):

Цикл 1:
1. отправляет INT следующее:
  • (a) Случайное многочленное в степени , делённое на , при . Пусть INT получит многочленное при (сноска: если INT подлинный, то ).
  • (b) Случайное многочленное в степени , делённое на . Пусть INT получит как многочленное в степени .
2. частно отправляет каждому устройству верификации следующее:
  • , где случайно (все различны), и .

AuthVal(D, INT, s):

Цикл 1: INT выбирает случайное и транслирует , где .
Цикл 2: проверяет для . Если D находит какое-либо несоответствие, он транслирует .

Многочленное (когда D не транслирует в цикле 2 AuthVal) или (транслируетcя D в цикле 2 AuthVal), которыми обладает INT, обозначается ICSIG(D, INT, s).

RevealVal(D, INT, s) Цикл 1: INT транслирует ICSIG(D, INT, s) (например, секретную информацию D, содержимую в ICSIG(D, INT, s) в качестве или ). Цикл 2: Устройство верификации транслирует Принять, если одно есть одно из следующих условий. (В противном случае транслирует Отказать.)

  1. и .
  2. и есть одно из следующего.
    1. ИЛИ
    2. (B(x) была транслирована INT во время AuthVal).

Локальные вычисления (Для каждого устройства верификации): если хотя бы устройства верификации транслировали Принять во время цикла 2 RevealVal, тогда принять ICSIG(D, INT, s) и выдать или (в зависимости от того, является ли ICSIG(D, INT, s) или ). Иначе отказать ICSIG(D, INT, s).

В наших протоколах мы используем Authval(1) или AuthVal(2) для обозначения соответственно первого и второго циклов AuthVal. Соответственно RevealVal(1) и RevealVal(2) используются для RevealVal. Под мы подразумеваем выполнение , за которым следует . Чтобы представить всё яснее, мы иногда используем вместо . Также в случае выполнения мы говорим, что X конфликтует с Y, если X должен транслировать поправочную информацию . В заключение мы говорим является последовательным для », если есть следующее:

3-цикловое статистическое ДРСИНЛ с максимальной отказоустойчивостью

В данной главе мы представляем 3-цикловый статистический протокол ДРСИНЛ с максимальной отказоустойчивостью. Хотя сложность протокола возрастает в геометрической прогрессии в отношении количества команд, протокол доказывает оптимальность сниженной границы [8]. Мы также показываем эффективный 4-цикловый протокол ДРСИНЛ в разделе 5.

В нашем 3-цикловом протоколе ДРСИНЛ распространитель добавочно распределяет секретную информацию на ресурсы. Проще говоря, каждый из ресурсов отвечает подклассу размером в . Затем распространитель проводит подпротокол типа «ДРСИНЛ», чтобы разделить среди систем воспроизведения в подклассе размером t. В фазе реконструкции ресурсы, отвечающие за каждый подкласс, реконструируются первыми. Эти ресурсы в свою очередь используются для реконструкции оригинальной секретной информации s.

Мы начинаем с описания подпрограммы, которую называем У-ДРСИНЛ (U-VSS).

U-VSS

Цель подпрограммы U-VSS функциональности типа «ДРСИНЛ» для подкласса (при ) системы воспроизведения . В частности мы хотим, чтобы правильность и работоспособность определяли VSS. Тем не менее требование секретности должно быть полностью соблюдено только, когда все системы воспроизведения в являются подлинными.


Неформально 3-цикловый протокол U-VSS может быть описан следующим способом:

  • В цикле 1, D отправляет секретную информацию всем системам воспроизведения в . Системы воспроизведения в случайно обмениваются «пустышками».
  • В цикле 2, каждая система воспроизведения в устанавливает подлинность его ресурса (через AuthVal). В дополнение он также транслирует секретную информацию, скрытую случайными «пустышками», полученными от других систем воспроизведения в . Системы воспроизведения в U также устанавливают подлинность «пустышек», полученных друг от друга.
  • В цикле 3, D устраняет конфликтующие широковещательные рассылки (если необходимо, с помощью путём транслирования s всем системам воспроизведения).

К сожалению, протокол U-VSS, описанный выше, не гарантирует блокирования, как такого, потому что системы воспроизведения в могут (претендуют) иметь конфликты относительно случайных «пустышек», таким образом, обладая функцией выявления различных случайных «пустышек» в фазе реконструкции. Чтобы это увидеть, рассмотрим ситуацию, когда , а . Без потери общности пусть . В цикле 3 может (претендует) быть неудачным (например, если провалена проверка AuthVal(2)) в установлении подлинности случайной «пустышки» (отправленной к ). Это может привести к трансляции и . Сходным образом P3 может (претендует) неудачным с в отношении . Заметим, что другие системы воспроизведения не обладают никакой информацией о и . В данном случае системы воспроизведения не могут различить (до конца фазы распределения) 3 следующие случая:

  1. (D и не являются подлинными.) транслировало неверную информацию об установлении подлинности для (поэтому создание относительно неудачно) и претендует на неудачу относительно трансляции , связанной с .
  2. (D и не являются подлинными.) транслировало неверную информацию об установлении подлинности для (поэтому создание относительно неудачно) и претендует на неудачу относительно трансляции , связанной с .
  3. ( и не являются подлинными.) Оба претендуют на неудачу относительно трансляций друг друга, связанных со случайными «пустышками» и .

Заметим, что в данном случае (3) подлинное D не может обнаружить никакой неудачи до конца второго цикла. (сноска: если мы допускаем ещё один цикл, тогда случай (3) может быть решён следующим образом. Когда каждая система воспроизведения транслирует «коррекционную» величину на случайную «пустышку», В будет транслировать секретную информацию s в четвёртом цикле. С этой модификацией блокировка может быть легко достигнута). В случаях (1) и (2) неподлинное большинство . Таким образом неподлинное D может становиться на стороны выявления или в фазе реконструкции. В зависимости от того, чью систему воспроизведения она поддерживает, могут быть реконструированы различные секреты. Заметим, что системы воспроизведения в могут быть неспособны сообщить является ли подлинным или и чью версию секретной информации они должны вывести. Тем не менее, в процессах, где нет нерешённых взаимных конфликтов U-VSS достигает желаемых характеристик VSS. Оглядываясь назад, на случай , , мы приводим наше определение взаимного конфликта к общему случаю:

TemplateDifinitionIcon.svg Определение «Определение - Определение 2»
Говорится, что взаимный конфликт возможен в осуществлении U-VSS, если
  1. Некоторые транслировали для ; и
  2. также транслировал и
  3. не транслирует в цикле 3 фазы распределения.

Для начала мы хотим, чтобы наш протокол U-VSS отвечал следующим нестрогим критериям: Если нет взаимного конфликта в исполнении U-VSS, то:

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

Протокол для U-VSS

Мы представляем протокол для протокола U-VSS, который отвечает вышеуказанным требованиям.

Вводы: Пусть обозначает ряд средств воспроизведения и пусть является распределителем с вводом . Пусть является целью подгруппы при

Фаза распределения:

Цикл 1:

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

Для каждой пары из подгруппы команда берёт случайную величину и осуществляет для каждого . Пусть принимает от как .

Цикл 2: Каждое транслирует и для каждого

Цикл 3:

  1. Если для какого-либо или , тогда D транслирует s.
  2. Если конфликтует с , тогда он транслирует

Локальные вычисления: D отвергается, если для некоторых , или , тогда D не транслировали s.

Фаза реконструкции: Если D транслировало s в цикле 3 фазы распределения, тогда каждая система воспроизведения устанавливает и выводит s и заканчивает.

Если существует взаимный конфликт, тогда каждая система воспроизведения (в ) выводит , и фаза реконструкции заканчивается. Иначе,

  1. Каждое выполняет , и каждый выполняет .
  2. D транслирует секретную информацию s.

Локальные вычисления: Конструировать GOOD следующим образом: Включить в GOOD для , если

  1. успешен в выявлении .
  2. Для каждого , который не конфликтует с , успешен в выявлении .
  3. Для каждого , выявленном в предыдущем шаге, выполняется .
  4. Если был успешно выявлен , выполняется .

Вычисли следующим образом:

  1. Если GOOD пустой, тогда , где s является трансляцией D в шаге 2.
  2. Иначе возьми любой и присвой .

Выведи .

Доказательства

Мы показываем, что протокол U-VSS, представленный ранее, отвечает необходимым требованиям сквозь серии требований.

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

TemplateTheoremIcon.svg Теорема Требование 1
. Если все системы воспроизведения в подлинные, никакой информация о s, выявленная для систем воспроизведения в конце фазы распределения.
Доказательство
Легко увидеть, что подлинное D никогда не отвергает в фазе распределения.


TemplateTheoremIcon.svg Теорема Требование 2.
Если нет взаимного конфликта, то величина, разделённая подлинным D, скажем s, реконструируется с высокой вероятностью.
Доказательство
Так как только величины, выполняемые , реконструируются, необходимо оспорить тот факт, что в GOOD содержится неподлинный , только если он выявляет . Это легко показано, так как если D подлинное, из-за Корректности 3, каждое успешное выявление равно s.


TemplateTheoremIcon.svg Теорема Требование 3.
Если D не отвергается, то для всех подлинных для некоторых .
Доказательство
Предположим, что системы воспроизведения получают ресурсы и при . Тогда в цикле 2 не равно . Поэтому D должно транслировать s, иначе будет отвергнут. Следовательно, каждый устанавливает (смотри Локальные вычисления).


Следующее требование может быть легко подтверждено.

TemplateTheoremIcon.svg Теорема Требование 4.
Доказательство
Если D не отвергнуто и не транслирует s в фазе распределения, то с большой вероятностью все подлинные системы воспроизведения в U содержатся в GOOD.


TemplateTheoremIcon.svg Теорема Требование 5.
Если нет взаимного конфликта, то существует величина , так что D фиксируется для в конце фазы распределения. Это реконструируется в конце фазы распределения.
Доказательство
Когда D подлинное, требование следует из Требования 2. Предположим, что D неподлинное. Если D отвергается в фазе распределения, тогда требование заведомо выполняется. В следующем мы предполагаем, что D не отвергается. Так как D неподлинное, и содержит системы воспроизведения , существует неподлинный . Из Требования 3 мы имеем, что все подлинные системы воспроизведения получили одинаковый ресурс (ресурс ) от D. Теперь мы показываем, что если нет взаимного конфликта, то реконструируется.


Идея в том, чтобы показать, что любой содержится в GOOD только, если он выявляет как. Это может доказать требование, т.к. все подлинные системы воспроизведения уже содержатся в GOOD (следует из Требования 4).

Ради достижения противоречия предположим, что успешно выявил . Мы рассмотрим два случая:

Случай 1: не конфликтует с .

Из-за Корректности 3 высока вероятность того, что может успешно выявить только как . Так как использовало , чтобы вычислить , он показывает, что для .

В таком случае, отсюда следует, что не будет включено в GOOD.

Случай 2: не конфликтует с .

Из Корректности 2 высока вероятность того, что успешно выявил , который он получил. Так как D не отвергается . Заметим, что условие не будет отвечать .

В таком случае, отсюда следует, что не будет включено в GOOD.

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

Конструирование статистической VSS для t < n/2 из U-VSS

В предыдущей главе мы видели, как U-VSS даёт нам желаемые качества VSS, когда нет взаимного конфликта. В данной главе мы разовьём технологии, чтобы справиться в выполнениями, в которых существует взаимный конфликт. Давайте сначала рассмотрим случай. Есть небольшой фокус, который мы можем использовать, чтобы добиться связывания: Сначала рассмотрим ситуацию, когда взаимный конфликт возникает, когда хотя бы 2 команды повреждены. Т.к. и t = 2, все системы воспроизведения в подлинные. (Это не случай наивысшего n, и в этом случае сложность усиливается.) Т.к. конфликтующие могли бы соответственно выявить свои многочлены (при ), выявления для системы U зафиксированы. Т.к. и подлинные, «контрольные точки» тоже фиксированы! Ключевой вывод таков, что подлинные не будут способны верно определить подлинные «контрольные точки» для подлинного D (Случай 3). Если D подлинное, тогда хотя бы один из выявленных многочленов не будет постоянным для любой подлинной «контрольной точки», кроме тех, вероятность которых незначительна. Итак, одно из выявлений не будет Принято.

Для общих , когда мы высчитываем взаимный конфликт в выполнении U-VSS? все системы воспроизведения в не являются обязательно подлинными. Вместо присваивания «контрольной точки» каждому средству воспроизведения мы присваиваем «контрольную точку» каждой подгруппе размера с помощью U-VSS протокола. В качестве дополнения, чтобы избежать проблем, вызванных взаимными конфликтами, чтобы создать подтверждающие точки в фазе реконструкции, используются только те выполнения U-VSS, в которых нет взаимного конфликта. Скрытой причиной использования U-VSS для распределения «контрольных точек» является тот факт, что сейчас проверка Корректности производится открыто (например, неподдельные системы воспроизведения больше не могут бесконтрольно транслировать Принять или Отказать, чтобы принудительно задавать желаемый вывод). U-VSS выполнения без взаимного конфликта гарантируют согласие среди выявленных контрольных точек. В результате становится ясно, какие многочлены будут действительно подходящими. Могут быть два конфликтующих многочлена, каждый из которых отвечает всем контрольным точкам. Тем не менее, в конце фазы распределения вывод проверки Корректности фиксирован! Если два конфликтующих многочлена проходят тест Корректности, то реконструируется. Заметим, что это не вредит качеству фиксации VSS, т.к. вне зависимости от реконструированной фиксируется в конце фазы распределения. (Мы предполагаем, что представляет неопределённый элемент в F). Также неподлинные системы воспроизведения возможно могли бы выявить неверные многочлены в фазе реконструкции. Мы доказываем, что наш статистический протокол VSS устойчив к такому враждебному поведению.

3-цикловый протокол для VSS

Вводы: Пусть определяет ряд систем воспроизведения и пусть является распространителем с вводом s. Пусть .

Фаза распределения: D дополнительно распределяет s в , где является случайным субъектом для . Следующие выполнения U-VSS идут параллельно:

  1. Повторить все подгруппы размером t: Выполнить .
  2. Для каждого средства воспроизведения подгруппы D берёт «контрольные точки» и отправляет это (чтобы проверить выявление многочленов каждым ). Выполнить для всех и для каждой подгруппы размера t.

Локальные вычисления: D отвергается, если существует хотя бы одно из следующего:

  1. D отвергается в некотором выполнении .
  2. D отвергается в некотором выполнении .

Фаза реконструкции: Пусть транслируемая . Пусть

Отсутствуют взаимные конфликты выполнения

Фаза реконструкции состоит из двух следующих циклов:

Цикл 1: Повторить все и каждый Выполнить реконструкцию фазы и (для каждого ). Цикл 2: Выявления, начатые в цикле 1, завершаются в этом цикле. Также D транслирует для каждого .

Локальные вычисления: Пусть транслировала и взаимно конфликтовала с некоторыми в фазе распределения}

Все системы воспроизведения реконструируют , если для любого :

  1. Существует система воспроизведения с и в соответствии с для всех  ; И
  2. Существует система воспроизведения с и в соответствии с для всех .

Если не реконструирована, то для каждого следующим образом создаётся : Включить в , если:

  1. содержится в GOOD, отвечающей выполнению .
  2. находится в соответствии с для всех . (где являются внутренними переменными в , отвечающей при ). Пусть .

Вычислить (что есть фиксация D ) следующим образом: Для установить как одно из транслируемых D во время цикла 3 фазы распределения.

Для взять любой и установить . Если пустой, то , где является трансляцией D в цикле 2 фазы реконструкции.

Реконструировать секрет D как .

Доказательство верности 3-циклового VSS

Теперь мы доказали, что 3-цикловый VSS отвечает всем качествам, требуемым от статистического протокола VSS. Пусть .

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

TemplateLemmaIcon.svg Лемма «Лемма 1.»
(Секретность) Протокол 3-циклового VSS отвечает идеальной секретности.


TemplateLemmaIcon.svg Лемма «Лемма 2.»
(Корректность) Протокол 3-циклового VSS отвечает качеству правильности .


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

Единственная возможность для быть реконструированным существует тогда, когда есть две взаимно конфликтующие системы воспроизведения (при math> S_m \not\in \mathcal {B}\, \! </math> ), так что существуют в соответствии с (соответственно) для всех и . Т.к. D является подлинным хотя бы один из должен быть неподлинным (иначе они не будут конфликтовать в случайных «пустышках» и транслировать свои многочлены).

Ключевой момент здесь – это хотя бы одна система, скажем , которая содержит только подлинные члены. Так как все члены подлинные, нет взаимно конфликтующей пары . В результате . Из-за Требования 1 никакая информация о не выявляется. Верные величины , распределенные D, также выявляются в фазе реконструкции соответствующих протоколов U-VSS (следует из Требования 2). Итак, если неподлинная система воспроизведения, скажем способно отвергнуть подлинное D, выявляя , то он должен быть сочтён (следует из доказательства Корректности 3). Это происходит с незначительной вероятностью.

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

TemplateTheoremIcon.svg Теорема Требование 6
Если повреждённое D не отвергается, то для каждого хотя бы одна подлинная система воспроизведения с большой вероятностью содержится в .
Доказательство
Доказательство. Сначала давайте зафиксируем . Из-за Требования 5 (качество фиксации для U-VSS) мы имеем, что для каждого кортежа , подлинной (всеми подлинными) системой(ами) воспроизведения в содержится определённый кортеж. В сущности это вынуждает каждое подтверждение контрольной точки действовать, как если бы им обладала подлинная система воспроизведении. Теперь из доказательства Корректности 2 для ППИ (сноска: доказательство идентично, т.к. в обоих случаях мы имеем дело в неподлинным D и подлинным посредником. В обоих случаях распространитель был неудачен с , где s является секретом распространителя.) каждая подлинная система воспроизведения в находится в соответствии с «контрольными точками» в с высокой вероятностью . Предположим, что есть подлинные системы воспроизведения в . Из вышеупомянутых суждений требование может быть ошибочным для данной , только если оно ошибочно для каждой подлинной системы воспроизведения в . Это происходит с максимальной вероятностью (сноска: мы использовали факт того, что повреждённая способность D становиться причиной ошибки для конкретных подлинных систем воспроизведения не зависит от его способности становиться причиной ошибки для различных подлинных систем воспроизведения. Это верно, потому что D может стать причиной ошибки для подлинного только считая (следует из доказательства Корректности 2). Различная подлинная система воспроизведения выбирает независимое от ). Отсюда следует, что наше суждение оправдано.). Так как есть типа , вероятность того, что требование будет ошибочным для любого , ограничивается . Суммируя все k, мы видим, что D может стать причиной требования стать ошибочным для любого с максимальной вероятностью . Таким образом требование выполняется.


TemplateLemmaIcon.svg Лемма «Лемма 3.»
(Фиксация) Протокол Протокол 3-циклового VSS отвечает фиксированному качеству .


Доказательство. Для подлинного D лемма следует из Леммы 2. Далее мы полагаем, что D является неподлинным. Сначала мы показываем, что вне зависимости от того, реконструировано ли , оно фиксируется в конце фазы распределения. Заметим, что многочлены в взяты из фазы распределения. Также «контрольные точки» для этих многочленов фиксированы в конце фазы распределения (из-за фиксированного качества U-VSS, доказанного в Требовании 5). Следовательно, решение о том, реконструировать ли , фиксировано в конце фазы распределения. Так как (из-за нашего предположения). Мы достигаем фиксации, даже когда реконструировано.

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

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

Случай 1: не транслирует в цикле 3 фазы распределения.

Исходя из Корректности 3, может с большой вероятностью выявить только как . Так как вычислил , он (с большой вероятностью) содержит . Следовательно, в данном случае не будет включён в .

Случай 2: не транслировал в цикле 3 фазы распределения.

Исходя из Корректности 2, с большой вероятностью происходит, что выявил как случайную «пустышку», которую он использовал для вычисления . Т.к. , и т.к. D не отвергается, мы имеем . Следовательно, в данном случае не будет включён в .

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

Теорема следует из Лемм 1, 2 и 3.

TemplateLemmaIcon.svg Лемма «Теорема 1.»
Существует 3-цикловый статистический протокол VSS, принимающий умышленные команды


Эффективный 4-цикловый статистический VSS с оптимальной отказоустойчивостью

Сейчас мы разрабатываем статистический VSS со сложностью многочленного обмена информацией при 4 циклах распределение, 2-циклах реконструкции . В протоколе D отбирает случайный симметричный многочленный с двумя переменными такой, как и отправляет к . В конце фазы распределения если D не отвергается, то каждый подлинный содержит степень многочленного fi(x) такого, как для каждой пары команд . Это значит, что если D не отвергается, то многочлены подлинных команд определяют симметричный многочленный с двумя переменными. Более того, в протоколе использованием качеств гарантировано, что ни один повреждённый не будет способен обнаружить в фазе реконструкции. Следовательно, независимо от того, подлинное или повреждённое ли D, реконструкция будет осуществлена. Чтобы достичь всех качеств VSS, D передаёт отдельным командам, и параллельно каждая отдельная команда передаёт каждой другой команде. Протокол каким-то образом стимулируется протоколом VSS [9]. Т.к. ППИ, предложенный в [9], использует один цикл Distr, 3 цикла в AuthVal и 2 цикла в RevealVal, VSS [9] использует максимально 11 циклов в фазе распределения.

Протокол

Вводы: Распространитель имеет секретную информацию s. Пусть D будет распространителем и пусть будет симметричным многочленом с двумя переменными степени t в каждой перменной. Пусть .

Фаза распределения

Цикл 1: Пусть будет определена как . Пусть для каждого . Выполнить и . Пусть соответствующие полученные величины будут и . Цикл 2:

  1. транслирует и .
  2. D транслирует и .
  3. Если получит , который не является многочленом степени , то выполнит для всех j.

Цикл 3:

  1. Если D конфликтует с , или или , то D транслирует и выполняет и для всех k.
  2. Если конфликтует с , или , или , или или , то выполняет и .
  3. Если конфликтует с D, то он выполняет для всех .

Цикл 4: Соответствующие выполнения завершаются в данном цикле.

Локальные вычисления: D отвергается, если для какого-либо не выполняется хотя бы одно из следующих условий:

  1. находится в многочлене степени t.
  2. Все выявления были успешными (например, хотя бы t + 1 вводов были транслированы).

Фаза реконструкции: Каждый выполняет (если уже не выполнил) для всех .

Локальные вычисления: Пусть , если D транслировало . Создать Rec следующим образом:

  1. , если . В этом случае, определить .
  2. , если он успешно выполнил для всех j , и они находятся в многочлене степени t.

Удалить из Rec, если

  1. успешно выявил и для некоторых .
  2. успешно выявил и .
  3. Если некоторые не конфликтовали с и .

Реконструировать симметричный многочлен с двумя переменными степени t из Вывести

Доказательства

Заметим, что в нашем 4-цикловом протоколе VSS, GGB качества Корректности 1, Корректности 2, Корректности 3 в силе одновременно выполнить и . Также, когда D является подлинным, Секретность в силе одновременно выполнить и .

Следующая лемма доказана с помощью стандартных суждений.

TemplateLemmaIcon.svg Лемма «Лемма 4.»
(Секретность) Протокол 4-цикловой VSS отвечает идеальной секретности.


TemplateTheoremIcon.svg Теорема Требование 7
Если D не отвергается и является подлинным, то для каждого .
Доказательство
Если , то , а т.к. D не отвергается, требование выполняется. Теперь пусть . Вспомним, что , потому что D конфликтовало с (относительно некоторой величины ИЛИ потому что или . В результате D выявляет (Цикл 3 Шаг 1). Вспомним, что . Следовательно, его выявления успешны. Теперь рассмотрим два случая. В первом, если не конфликтовало с D, то D придётся выявлять верную величину (следует из Корректности 3), например, . Т.к. , мы имеем . Следовательно, для подлинного , мы имеем . Если , то D отвергается (смотри Локальные вычисления). Следовательно, .


TemplateTheoremIcon.svg Теорема Требование 8.
Если D не отвергается, и является подлинным, то
Доказательство
Если , то во время реконструкции. Подлинный успешно выявляет для всех j. Теперь мы покажем, что ни одно из правил, которые удаляют из Rec, не обращаются к подлинному .


  1. Исходя из Требования 8, мы имеем, что для каждого
  2. Т.к. выявленное равно (исходя из Корректности 3),
  3. Если не конфликтовал с , то подлинный будет успешным в выявлении «пустышки» (исходя из Корректности 2). Следовательно, }}
TemplateTheoremIcon.svg Теорема Требование 9.
Если D не отвергается, то для каждого подлинного .
Доказательство

Вспомним, что когда Когда оба находятся в U, то требование следует непосредственно. Теперь предположим, что Для подлинных если , то и . Следовательно, могли бы успешно выявить соответственно (исходя из Корректности 2). Т.к. мы полагаем, что D не отвергается, требование также следует в этом случае.

В заключение рассмотрим случай, когда только один из содержится в U. Пусть . Если , то могло бы быть удалено из Rec. Но исходя из Требования 8, мы имеем подлинный . Следовательно, требование должно быть выполнено.


Вспомним, что есть хотя бы t + 1 подлинные средства воспроизведения, и исходя из Требования 8, все они содержатся в Rec. Исходя из Требования 9, ресурсы этих подлинных средств воспроизведения постоянны. Теперь легко увидеть следующее требование:

TemplateLemmaIcon.svg Лемма «Требование 10.»
Если D не отвергается, то все подлинные команды находятся в соответствии с уникальным симметричным многочленом с двумя неизвестными степени t, скажем .


TemplateTheoremIcon.svg Теорема Требование 11.
Если D не отвергается, а , то находится в соответствии с .
Доказательство

Исходя из Требования 7, для каждого находится в соответствии с ресурсами подлинных средств воспроизведения. Это значит, что находится в соответствии с .

Теперь пусть . Т.к. , мы имеем для каждого (иначе удаляется из Rec). Следовательно, если не находится в соответствии с , то должно быть выполнено для некоторых подлинных . Если или , то могли бы выявить соответственно . Т.к. D не отвергнуто, мы имеем . Для остальной части доказательства мы полагаем и .

Если не конфликтовало с , то выявляет . Если также вынужден конфликтовать с , то мог бы выявить . Т.к. D не было отвергнуто, мы имеем . С другой стороны, если не пришлось конфликтовать с , то пришлось бы выявлять (следует из Корректности 3). Т.к. является подлинным, то . Если , то . Т.к. , это показывает, что . Следовательно, находится в соответствии с .


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

TemplateTheoremIcon.svg Теорема Требование 12.
Если D не отвергается, то будет реконструирован в фазе реконструкции. Более того, это фиксировано в конце фазы распределения.
Доказательство
Легко увидеть, что подлинное D никогда не отвергается. С учётом этого следующие две леммы следуют напрямую из Требования 12, а теорема следует из Лемм 4, 5 и 6.


TemplateLemmaIcon.svg Лемма «Лемма 5.»
(Корректность) Протокол 4-циклового VSS отвечает качеству корректности .


TemplateLemmaIcon.svg Лемма «Лемма 6.»
(Чёткая фиксация) Протокол 4-циклового VSS отвечает качеству чёткой фиксации .


TemplateLemmaIcon.svg Лемма «Теорема 2.»
Существует эффективный статистический VSS протокол с 4 циклами распределения и 2 циклами реконструкции (2t + 1, t).


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

Мы благодарим Джонатана Каца за плодотворное сотрудничество на ранних стадиях этого исследования.

Литература

  1. B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults. In 26th Annual Symposium on Foundations of Computer Science (FOCS), pages 383–395. IEEE, 1985
  2. M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for noncryptographic fault-tolerant distributed computation. In 20th Annual ACM Symposium on Theory of Computing (STOC), pages 1–10. ACM Press, 1988.
  3. D. Dolev, C. Dwork, O. Waarts, and M. Yung. Perfectly secure message transmission. Journal of the ACM, 40(1):17–47, 1993.
  4. 4,0 4,1 4,2 Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In 21st Annual ACM Symposium on Theory of Computing (STOC), pages 73–85. ACM Press, 1989.
  5. Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, and Tal Rabin. The round complexity of verifiable secret sharing and secure multicast. In 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 580–589. ACM Press, 2001.
  6. . Matthias Fitzi, Juan A. Garay, Shyamnath Gollakota, C. Pandu Rangan, and K. Srinathan. Round-optimal and efficient verifiable secret sharing. In 3rd Theory of Cryptography Conference — TCC 2006, volume 3876 of LNCS, pages 329–342. Springer, 2006.
  7. . J. Katz, C.-Y. Koo, and R. Kumaresan. Improving the round complexity of VSS in point-to-point networks. Information and Computation, 207(8):889–899, 2009.
  8. A. Patra, A. Choudhary, T. Rabin, and C.P. Rangan. The round complexity of verifiable secret sharing revisited. In Advances in Cryptology — Crypto 2009, volume 5677 of LNCS, pages 487–504. Springer, 2009.
  9. 9,0 9,1 9,2 9,3 Ronald Cramer, Ivan Damg˚ard, Stefan Dziembowski, Martin Hirt, and Tal Rabin. Efficient multiparty computations secure against an adaptive adversary. In Jacques Stern, editor, Advances in Cryptology — Eurocrypt ’99, volume 1592 of LNCS, pages 311–326. Springer, 1999.
  10. 10,0 10,1 Arpita Patra, Ashish Choudhary, and C. Pandu Rangan. Simple and efficient asynchronous byzantine agreement with optimal resilience. In Srikanta Tirthapura and Lorenzo Alvisi, editors, PODC, pages 92–101. ACM, 2009.
  11. 11,0 11,1 Arpita Patra, Ashish Choudhary, and C. Pandu Rangan. Round efficient unconditionally secure multiparty computation protocol. In Dipanwita Roy Chowdhury, Vincent Rijmen, and Abhijit Das, editors, INDOCRYPT, volume 5365 of Lecture Notes in Computer Science, pages 185–199. Springer, 2008.