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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:57, 27 сентября 2015.
Two-Output Secure Computation with Malicious Adversaries
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Abhi Shelat[@: 1] and
Chih-Hao Shen[@: 2]
Опубликован 2010 г.
Сайт Department of Computer Science
Перевели Egor Zorin
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

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


Ключевые слова: Неразличимость свидетелей, искаженные схемы Яо, схемы подписей.

Введение

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

Существует два хорошо известных метода для достижения этого преобразования: проверка и доказательство или отсечение и выбор. Метод проверки и доказательства, предложенный Голдрейхом, Микали и Вингерсоном в работе [5] требует лишь общих предположений относительно доказательств с нулевым разглашением.

Однако такой подход требует сложных NP преобразований, которые никогда ранее не были реализованы. С другой стороны, эффективные преобразования, основанные на методе отсечения и выбора были недавно предложены Линделлом и Пинкасом [1] и реализованы Пинкасом и соавт. в работе[6]. Общая идея в данном методе состоит в подготовке нескольких копий схемы для для последующей оценки. Случайно выбранный набор схем (так называемых контрольных схем) затем раскрывается, чтобы показать, что они были созданы правильно. Наконец, закрытые схемы (так называемые оценочные схемы) оцениваются и большая часть результатов берется в качестве конечной выходных данных. Этот подход имеет ограниченную сложность, включающую в себя как коммуникационные, так и вычислительные затраты.

Отправной точкой для нашей работы является метод с отсечением и выбором. Вопрос, которому уделяем основное внимание заключается в понимании основных ограничений (в отношении эффективности) для данного метода. Этот метод не требует NP преобразований, однако, он сталкивается с другими проблемами эффективности, вытекающими из новых проблем безопасности при оценке e из s копий для схемы. В данной статье, мы обратимся к нескольким из этих вопросов: (1) обеспечение согласованности входных данных, (2) обработка функций с двумя выводами, (3) предотвращение селективных атак, и (4) определение оптимального количества схем. Более того, мы определяем различные свойства, которые позволяют найти эффективные решение этих вопросов. В некоторых случаях оказывается достаточно использования протоколов с нераздичимыми свидетелями. Таким образом, в случае согласованности входных данных, мы можем использовать чрезвычайно эффективный протокол, до тех пор пока существуют функции без сцепки и при минимальном свойстве пластичности (это возможно при стандартных алгебраических вычислениях). Также мы продемонстрируем преимущества нашего подхода как для асимптотического анализа сложности, так и для экспериментальной реализации. Приведем теперь обзор наших достижений.

Согласованность входных данных для генератора

Согласно методу с отсечением и выбором, необходимо отправить по e копии своих искаженных данных в качестве входа для . Так как схемы искаженны, может сжульничать, послав различные входы для e копий искаженной схемы. Для некоторых функций, существуют несложные пути для , чтобы извлечь информацию о входных данных для (§3 в работе[1]). Таким образом, протокол должен гарантировать, чтобы все e копии для являлись согласованными.

Предыдущие работы. Пусть определяет размеры для входов и , и пусть будет статистическим параметром безопасности для метода отсечения и выбора. Мохасель и Франклин в работе[7] предложили схему проверки равенство, имеющию сложность вычислений и коммуникаций порядка . Позже Вудруф[8] предложил подход с расширенными границами, чтобы ограничить возможность мошенничества со стороны . Асимптотическая сложность равна , однако, на практике, необходимое количество констант для построения графиков намного больше. Линделл и Пинкас[1] разработали подход на основе схемы отсечения и выбора, который использует моделирующую защиту от вредоносных игроков. Этот подход требует рассчета обязательств, и их распределения между участниками. Хотя эти обязательства могут быть реализованы с помощью примитивов, таких как устойчивые хеш-функции столкновений, коммуникационная сложность по прежнему имеет место. Джареки и Шматиков в работе[2] представили подход, основанный на методе с проверкой и доказательством. Хотя в их протоколе создается только одна схема, требуются сотни сложных криптографических операций на цикл, в то время как подходы, основанные на методе отсечения и выбора требуют таких операций только для входных циклов.Нильсен и Орланди а работе[9] предлагают подход с циклами как в конструкторе Lego. Хотя он также основан на методе отсечения и выбора, использование техники выравнивания возволяет ограничиться только одной копией входных ключей для для всех e копий искаженной цепи. Однако подобно подходу Джареки и Шматикова, каждый цикл требует нескольких групповых элементов, что приводит как к вычислительным, так и к коммуникационным затратам. Линделл и Пинкас предложили технику псевдослучайного синтезатора Дифи-Хелмана в в работе[3]; их подход основывается на поиске эффективных доказательств с нулевым разглашением для специально выбранного предположения о сложности, что подразумевает сложность порядка .

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

Функции с двумя выходами

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


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

Как описано в работе[1], случай с двумя выходами может быть сведен к случаю с одним выходом следующим образом: (1) случайным образом выбирает в качестве дополнительных входов, (2) первоначальная функция преобразуется в , где является шифровкой для , а это MAC код для сообщения , и (3) посылает обратно для , который затем может проверить подлинность выхода .Тем не менее, это преобразование увеличивает размер входа для с до бит. Как следствие, сложность проверки согласованности входа также увеличивается. Второй недостаток состоит в том, что схема должна быть также изменена, чтобы включить в себя дополнительные цепочки для вычисления шифровки и MAC функции. Хотя метод в работе[10] может быть использован для реализации алгоритма XOR «без затрат», MAC функция по-прежнему требует около дополнительный цепочек. Так как все s копий схемы должны быть изменены, это приводит к дополнительным связям для цепочек шифрования. Действительно, для простых функций, размер этих преобразований превышает размер самой исходной схемы.

Киразом и Шоенмакерсом в работе[11] была представлена справедливый двусторонний вычислительный протокол, в котором также встает аналогичный вопрос о двух выходных функциях. В их подходе, связан с искаженными выходами . Далее показывает два выходных ключа для каждого из его выходных каналов, а находит одну цепь , согласующуюся с "большинством выходов для ". Индекс затем демонстрируется . Тем не менее, информирование индексе большинства схем может привести к утечке информации о входах . Обращаем ваше внимание на наличие неопубликованной работа Кираза[12], в которой данная проблема решена без уменьшения общей производительности. В частности, в новых подходах основные вычислительные затраты связаны с OR-доказательством размера , а коммуникационные связаны с выходными ключами , где порядок затрат примерно равен . Их техника хорошо соотноситься с нашим подходом, но у нас нет экспериментальных данных, чтобы сделать точные сравнения.


Наш подход к функциям с двумя выходами. Мы представляем метод оценки функции с двумя выходами, без добавления цепочек XOR к исходной схеме для . Для того, чтобы мог выбрать один выход, согласующийся с большинством, аналогично схеме Кираза и Шоенмакерса[11], мы однократно добавляем дополнительные биты для входного ключа , преобразуя функцию в , где . С помощью этого дополнительного случайного вклада c со стороны , может сделать большинство операций по оценке выхода , не зная настоящего выхода для . Далее, должен доказать достоверность оценки выхода , предоставленной для . Здесь наша идея состоит в том, что в -й выходной цепочке для -го искаженного контура изменяется на или вместо 0 или 1, где будет являться подписью для сообщения , подписанного ключом . Другими словами, искаженный контур выдает выходной бит для , подпись для этого бита, индекс , и индекс контура . Таким образом, после оценки, передает значение и доказывает знание подписей для всех битов при условии, что индексы для всех подписей действительны и одинаковы (среди индексов для оценки). Это же доказательство использовалось для групповых элементов . Тем не менее, мы покажем, что доказательства неразличимости свидетелей оказывается достаточно, что в свою очередь снижает сложность вычислений. Кроме того, с помощью техники Камениша, Шабони и Шелата для доказательства[13], мы можем уменьшить сложность до групповых элементов.

Проблема селективной ошибки

Другая проблема при создании искаженных схем происходит во время фазы неосознанной передачи (OT), когда получает входные ключи для схем. Вредоносный может атаковать протокол с селективной ошибкой, где ключи, используемые для построения искаженного контура могут быть не теми, что были использованы при ОТ передаче, в следствие чего вход для может быть выведен по реакции на ОТ передачу. Например, для обмана может использовать , чтобы построить искаженный контур, но использовать в соответствующей OT передаче, где . В результате, если бит на входной бит для равен 1, то он получит после ОТ передачи и не сможет правильно оценить искаженныц контур. Напротив, если входной бит равен 0, тогда получает из OT передачи и совершает оценку без каких-либо проблем. Поэтому может вывести вход . Этот проблема отмечена как Мохасселем и Франклином в работе[7], так и Киразом и Шоенмакерсом в работе[14].


Аналогичные работы. Линделл и Пинкас в работе[1] заменяют все входные биты для дополнительными входными битами . Эти новые обрабатываются совместно алгоритмом XOR, а результат используется в качестве входа для исходной схемы. Такой подход делает вероятность того, что совершит селективную ошибку независимой от его входа. Такой подход, тем не менее, увеличивает количество входных битов для с до . Вудруфф позже отметил, что использование интеллектуальных систем кодирования может уменьшить сложность до величины . Стоит отметить, что Линделл, Пинкас и Смарт в работе[15] реализовали метод, описанный в работе[1], и эмпирически подтвердили наличие дополнительных затрат от этого шага. В частности, 16-битная схема сравнения, изначально требующая пятнадцати 3-в-1 цепочек и одной 2-в-1 цепочку, будет увеличена до схемы с несколькими тысячами цепочками после увеличения числа входов. Ввиду того, что число входов определяет число OT операций, подход, сводящий число дополнительных входов минимум оказывается предпочтительнее. На деле мы покажем, что увеличение количества входов и числа цепочек в схеме не является необходимым для решения данной проблемы. Независимо от нашей работы, Линделл и Пинкас[3] предложили решить эту проблему с помощью ОТ операций отсечения и выбора. Это новое решение действительно обеспечивает значительное улучшение по отношению к работе[1] и обладает примерно такой же сложностью, как и наше решение. Кроме того, оба подхода могут быть построены на эффективных OT передачах, предложенных Наором и Пинкасом в работе[16] или Пейкертом, Вайкунтанатом и Вотерсом в работе[17]. Тем не менее, особенности использования последних ОТ операций в[3] требует двух независимо выбранных строки, в то время как наше решение требует только одной.


Наш подход к селективной ошибке. Вдохновленные идеей неосознанной передачи, предложенной Кирацом и Шоенмакерсом[14], мы решаем проблему селективной ошибки за счет того, что отправитель ( в протоколе Яо) доказывает правильность осуществления OT операций, показывая каким образом был сделан выбор при передаче. Как правило, это нарушит безопасность отправителя в OT передаче. Однако в схеме с отсечением и выбором, отправитель изначально открывает много схем, так что ключи, используемые в качестве входа для OT передачи не являются секретом. Таким образом, идея состоит в том, что отправитель может доказать правильность выполнения OT передачи для всех открытых схем, просто показав случайные метки, используемые им в OT передаче. Подчеркнем, что не каждая OT передача может быть здесь использована. Подходящей передачей будет та, обязательным свойством которой является невозможность для отправителя мошенника показать метки, отличающиеся от реально использовавшихся от реально использованых. Неудобство в данном случае заключается в том, что для имитации вредоносного P2 мы должны использовать сложный протокол проверки меток, чтобы выбрать, какие из схем открыть. Следовательно, не может открыть схемы для , пока протокол проверки не закончится; и к тому же ОТ передача должна быть сделана до проверки меток, чтобы гарантировать надлежащее отсечение. Таким образом, порядок операций для протокола имеет решающее значение для безопасности. Эффективное решение проблемы Диффи-Хеллмана представлено в разделе 2.3.

Оптимальная стратегия отсечения и выбора

Мы обнаружили, что большинство протоколов отсечения и выбора открывают из копий искаженных схем, чтобы уменьшить вероятность успешного обмана со стороны . Мы покажем, что открытие из является более эффективным, чем из . В частности, когда используется s схем, наша стратегия приводит к уровню безопасности в отличие от величины из работы[1] и из работы[3]. Хотя разница с последним значением не превышает 1%, мы покажем оптимальные значения параметров для метода отсечения и выбора в приложении, тем самым демонстрируя пределы для данного метода.

Сравнение коммуникационной сложности

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

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

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

  • Джареки и Шматиков[2]: Для каждой цепочки, количество вычисляемых элементов составляет не менее 100, включая искаженные значения для входов, дважды зашифрованные записи и доказательство с нулевым разглашением (ZK) для правильности цепочек. Более того, для каждого входа или выхода требуется ZK доказательство для конъюнкции/дизъюнкции. Каждое из ZK доказательств требует определенного числя групповых элементов. Наконец, данный протокол предполагает наличие сложной задачи принятия решений в рамках RSA групп; таким образом каждый групповой элемент будет иметь размер .
  • Кираз[12]: Этот подход использует метод проверки соответствия, размер которого для проверки согласованности входов для составляет . Решение проблемы селективной атаки осуществляется при помощи OT операции как и в нашем подходе. Более того, для работы с функциями с двумя выходами, добавляется n дополнительных битов ко входу , обязательных для всех ключей на выходе , которые включающих в себя порядка вычислений и OR-доказательство с нулевым разглашением размера .
  • Линделл и Пинкас[1]: Каждая из искаженных цепочек требует пространства для четырех дважды зашифрованных записей. Таким образом, анализ коммуникаций выглядит следующим образом: (1) s копии основной схемы требуют цепочек; (2) каждый из входных бит для требует простых вычислений для проверки согласованности; (3) все входные биты для требуют ОТ операций в количестве . Кроме того, определение функции с двумя выходами на основе MAC вычислений добавляет цепочек к каждой из копий схемы и ко входу . Таким образом, общие коммуникационные затраты составят
Таблица 1. Асимптотический анализ различных вычислений безопасности при наличии двух участников
коммуникационные затраты

основная схема вход для вход для для двух выходов
JS[2] OT's
K[12] OT's
LP07[1] OT's
LP10[3] OT's
наш подход OT's

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

Элементы построения

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

Проверка согласованности данных для входа генератора

Схема с отсечением и выбором для составления протоколов Яо гарантирует, что предоставляет согласованные значения для каждой копии оценочных схем. Напомним, что существует e схем, которые необходимо вычислить. Таким образом, для каждой входной последовательности должен передать все e ключи, соответствующие входному биту равному 0 или 1. Подробно известно[7][14][8][1], что при некоторых обстоятельствах, может получать информацию о входах , если способен представить различные входные значения для e копий этой входной последовательности. Основная идея нашего решения основана на использовании функций без сцепок[прим. 4], определяемых следующим образом:

TemplateDifinitionIcon.svg Определение «Определение 1 (Функции без сцепок, согласно работе[18]

Триплет алгоритмов называется не имеющим сцепки, если выполнены следующие условия:

  1. Легкость оценки: Как алгоритм выбора индекса , так и алгоритм подбора домена имеют вероятностный характер, в то время как оценочный алгоритм является детерминированным.
  2. Идентичность распределения областей: Пусть будет обозначать выход для алгоритма при входных значениях . Для любого в границах , случайные величины и будут распределены одинаково.
  3. Трудность формирования сцепок: Для любого неоднородного вероятностного алгоритма , любого многочлена и любого достаточно большого n должно быть справедливо

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

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

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

TemplateDifinitionIcon.svg Определение «Определение 2 (изменяемые функции без сцепок)»

Набор алгоритмов является изменяемым, если выполнены следующие условия

  1. Подмножество функций без сцепок: являются функциями без сцепок, а диапазонами для и будут группы, обозначаемые как и , соответственно.
  2. Равномерное определение домена: Для любого из диапазона , случайные величины и будут равномерны в , и мы обозначим их как для простоты.
  3. Изменяемость: Запускается для , для любого из диапазона и любых и вычисляется

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

Функции с двумя выходами

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

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

Алгоритм 1. Доказательство достоверности выходов .

Как правило, доказательства OR будет достаточно чтобы подствердить, что подпись принадлежит одной из оценочных схем. Тем не менее, OR доказательство размера для каждого бита из битного выхода приведет к доказательству с нулевым разглашением размера . Поэтому мы изменяем технику из работы[13], чтобы уменьшить размер доказательств до . Пусть будут индексами для всех оценочных схем. Идея для состоит в отправке подписей для каждого элемента в , обозначенного как . Перепроверив эти подписи, может выполнять каждое OR доказательства при постоянных связях. В частности, после оценки, выбирает одну оценочную схему, например -ю, результат которой соответствует большинству из всех оценочных схем. Пусть будет выходом для -й схемы . Напомним, что имеет как значение так и подпись для , определяемую как , в соответствии со способом построения искаженных схем. Чтобы доказать подлинность значения , передает к , скрывает подписи и , и доказывает знание « для некоторых ». Другими словами, должен доказать знание и для и . Полное доказательство показано в алгоритме 1. За счет свойства достоверности схем подписей доказывает знание подписи и тем самым подлинность .

В одной из реализаций нашего протокола может быть использована краткая схема подписей Боне-Бойена [2], который кратко описана ниже. Схема Боне-Бойена требует q-SDH (Сильного Диффи-Хельмановского) прежположения[прим. 5] билинейных карт[прим. 6]. Основываясь на этих двух объектах, схема Боне-Бойена включает в себя набор таких эффективных алгоритмов , что

  1. генерирует такую пару ключей , что и , где является группой порядка это генератор для , а .
  2. подписывает сообщение с ключом подписью .
  3. проверяет подпись ключом путем вычисления . Если результат равен , выводит значение valid, в противном случае, выводит invalid.

Осуществление неосознанной передачи

Алгоритм 2. Неосозная передача для получения входного ключа для [3]

Понятие неосознанной передачи (OT), введенное Рабином в работе[19], а также расширенное Эвеном, Голдрейхом и Лемпелом в работе [5] и Брассардом, Шепо и Робертом в работе[20] работает следующим образом: существует отправитель сообщения и получатель с параметром выбора . Получатель старается таким образом получить от отправителя, чтобы (1) отправитель не узнал ничего о выборе получателя и (2) получатель знал только и ничего о каких-либо других сообщениях для . Кираз и Шоенмакер в работе[14] ввели другое понятие ОТ передаци, называемое обязывающей OT передачей, в которой получатель также получает идеально скрытые и вычислительно-связывающие обязательства для отправителя входного сообщения, а отправитель получает в качестве выхода значение, чтобы раскрыть обязательства. На практике, Кираз и Шоенмакер ввели это понятие специально для использования в оценочных схемах Яо. Мы согласны с идеей, лежащей в основе их рассуждений.

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

TemplateTheoremIcon.svg Теорема Теорема 1[17]
Если предположение Диффи-Хеллмана выполняется в группе , то существует протокол, который надежно вычисляет передачу
Доказательство
Без доказательства.

Алгоритм 2 схематично доказывает теорему 1. Этот алгоритм является простой модификацией ОТ протоколов, разработанных Пейкертом, Вайкунтанатом и Вотерсом[17] и позже Линделл и Пинкасом[3]. Мы просто добавили ZK доказательство на промежуточных шагах. Безопасность получателя достигается за счет предположения Диффи-Хеллмана и того факта, что ZK доказательство не зависит от входа получателя. С другой стороны, безопасность отправителя получается из равномерности распределения и по , с учетом равномерного выбора и , и при идеальном верификаторе для ZK доказательства. Как описано в работе[15], операции неосознанной передачи можно осуществить так, чтобы все входные ключи n (по одному для каждого бита) с копиями схемы будут передаваться за один раз.

Основной алгоритм

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

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

Индивидуальные входы: имеет исходный вход и дополтельные случайные входы , а <mathP_2</math> имеет вход .

Индивидуальные выходы: выводит , а выводит

  1. запускает алгоритм выбора индекса и отправляет к .
  2. OT передача для входов : За всех и , выбирает случайную пару -битовых строк , связаных с -м входом цепочек для -й схемы. Обе стороны далее осуществляют ОT передачу параллельно. На -м этапе
    (а) использует вход , а использует входы .
    (b) получает ключи открытия для всех векторов, в то время как получает вектор на свой выбор и обязательства по обеим векторам, то есть и
  3. Построение искаженной схемы: запускает алгоритм генерации ключей для создания пары ключей для подписи , далее запускается алгоритм отбора доменов для создания элементов домена , для и , . Далее создает независимых копий искаженных схем для , обозначеных как . В дополнение к схеме построения Яо, схема также удовлетворяет следующим условиям:
    (a) связано со значениями из -й входной цепочки для , где извлекается из групповых элементов , то есть
    (b) , выбранное в шаге 2, связывается со значением из -й входной цепочки для .
    (c) связывается бит значением из -й входной цепочки для .
  4. Для , , , посылает схемы и обязательства для , обозначаемые как к .
  5. Отсечение и выбор: и реализуют алгоритм подбрасывания монеты для создания случайной последовательности, с помощью которой они согласовывают набор контрольных схем. Пусть будет итоговым набором, то есть и . Для всех посылает к схемы вместе со значениями для , и случайные ключи, связанные с каждой последовательностью . проверяет следующее:
    (a) Открыты ли значения из шага 2 для .
    (b) Открыты ли значение из шага 4 для c
    (с) Является ли искаженной версией для правильно построеной . В частности,
    - связано со значением из -й входной цепочки для  ;
    - связано с бит значением из -й входной цепочки для  ;
    - , где является подписью совместно с бит значением из -й входной цепочки для  ;
    - таблица истинности для каждой булевой цепочки корректно преобразовывается в дважды зашифрованные входы для соответствующих искаженных цепочек.
    Если любая из выше описанных проверок не выполняется, останавливается.
  6. Проверка согласованности для входов : Пусть и будут индексами для оценочных циклов. посылает свои значения оценочных цепочек к . Пусть будут в данном случае итоговыми результатами. Далее, доказывает согласованность своих взодных битов, отправляя к , который затем проверяет справедливость , для останавливается, если какая-либо из проверок не выполняется. В противном случае .
  7. Оценка цепочки: Для всех , теперь обладает векторами ключей (из шага 6) для входов и (из шага 2) для входов . Таким образом способен сделать оценку схемы и получить выходы для и выходы для , где . Пусть и будут n выходными битами для и соответственно. Далее выбирает такие индексы , что и будут появляться в векторах и более раз, соответственно. посылает к и берет в качестве конечного результата. Если не существует таких , тогда останавливается.
  8. Проверка выходов : Чтобы подтвердить подлинность без открытия , создает новую пару ключей для подписи . Далее подписывает индексы для всех оценочных схем и передает результаты к . В частности, передает открытый ключ и вектор подписей , где . Подписи проверяются , проверяя справедливость , для всех . Далее, доказывает при неразличимости свидетелей знание таких (подписи, подписанной ключом ) и (подписи, подписанной с ), что и эквивалентны для . останавливается, если доказательство не действительно; в противном случае берет в качестве конечного выхода.
TemplateTheoremIcon.svg Теорема Теорема 2
Пусть задана функция . При заданных безопасном протоколе неосознанной передачи, идеально скрытой схеме, схеме с обязательствами, функциях без сцепок, и псевдослучайных функциях, основной протокол надежно вычисляет .
Доказательство
Мы опустили стандартное определение для «надежного вычисления » на основе моделирования. Грубо говоря, это определение требует моделирования для проведения оценки и для генераторов, способных генерировать шифровки, при наличии доступа либо к оценщику либо к генератору (соответственно). В данном случае имеет место неразличимость от шифровок, созданных при реальном взаимодействии между опасным генератором и честным оценщиком или честным генератором и опасным оценщиком. (В случае, когда обе стороны опасны также требуется моделирование, но оно тривиально). Доказательство теоремы 2 опускается в данной статье.


Экспериментальные результаты

Ниже мы хотим показать практическую выгоду от использования нашего протокола. Наша реализация принимает булеву схему, созданную честным компилятором, в качестве входных данных. Функция шифрования, используемая для построения искаженные цепочек определяется как , где и обозначает младшие разряды бит из . Здесь SHA-256 моделируется как псевдослучайная функция. Целью для SHA-256 является осуществление справедливого сравнения, аналогично работе[6].

Следуя Пинкас и соавт.[6], мы устанавливаем уровень безопасности и параметр безопасности (длина ключа) в 128-бит. В первом эксперименте, и имеют 32-битные входы и , соответственно. Они вычисляют такую , что после безопасных вычислений, получает , а получает в качестве результата сравнения и . В описанных цепочек мы применяем в первом эксперименте для нашего подхода к функциям с двумя выходами. Во втором эксперименте, имеет 128-битный блок сообщений, в то время, как имеет 128-битный ключ шифрования. Они хотят надежно вычислить AES шифрование, и только получает текст шифровки. Мы провели наши эксперименты на двух компьютерах: медленном и быстром, где медленный работает на OS X 10.5 с процессором Intel Core 2 Duo 2,8 ГГц и 2 ГБ RAM, а быстрый имеет СentOS с Intel Xeon Quad Core E5506 2,13 ГГц и 8 ГБ RAM. Мкдленный уступает компьютеру, испольванному в работе[6] (Intel Core 2 Duo 3,0 ГГц, 4 Гб RAM), и быстрый максимально близок по параметрам.

Таблица 2 показывает наилучшие результаты из[6]. Заметим, что используемая в[6] техника сокращения строк позволяет даже не-XOR цепочкам сэкономить до 25% вычислительных затрат. Будущая версия нашего протокола сможет также уменьшить затраты на 25%, так как эта техника применима в нем.

Таблица 2. Производительность по сравнению с работой[6]

Число цепочек Время (с) Итого
основные доп. Non-XOR Преком. ОТ расч. Время (с) Кбайты
531 2,250 278 117 16 39 172 140,265
У нас (медленный) 531 6 237 35 15 21 71 5,513
У нас (быстрый) 531 6 237 27 11 15 53 5,513
33,880 12,080 11,490 483 34 361 878 406,010
У нас (медленный) 33,880 0 11,286 138 58 69 265 190,122
У нас (быстрый) 33,880 0 11,286 98 44 50 192 190,122
Таблица 3. Время работы (в секундах) двух экспериментов на медленном компьютере

Сумма (с) Сумма (с)
Прекомпозиция 35.4 0.0 35.4 137.7 0.0 137.7
ОТ передача 7.9 6.7 14.6 31.9 26.3 58.2
Выбор и отсечение 0.0 14.7 14.7 0.0 44.4 44.4
Проверка входа 0.0 3.0 3.0 0.0 10.0 10.0
Оценка 0.0 3.4 3.4 0.0 14.1 14.1
Для двух входов 0.1 0.0 0.1 0.0 0.0 0.0
Итого (с) 43.4 27.8 71.2 169.6 94.8 264.4
Рис. 3. (a) Коммуникационные затраты на эксперимента 1 поэтапно для нашего подхода, при заданном статистическом параметре безопасности s=125 и параметре безопасности k =128. (b) Размер схемы и затраты на связи по сравнению с работой[6] (которая также обеспечивает ограниченность вероятности обмана значением ).

Наша реализация включает в себя по программе для и . Для экономии времени, мы написали другую программу, которая объединяет эти две и использует выход одной в качестве входа для второй и и наоборот. Временные затраты увеличиваются на основных стадиях и показаны в таблице 3. Приведенные данные получены как среднее для 5 запусков.

Рис. 4. (a) Коммуникационные затраты на эксперимента 2 поэтапно для нашего подхода, при заданном статистическом параметре безопасности s=125 и параметре безопасности k =128

Тестирование нашего решения реализовано при помощи PBC (Криптография на основе сопряжений) библиотеки[21]. Компоненты нашего протокола, в том числе функции без сцепок, проверка входной согласованности генератора, а также проверка достоверности выходов генератора, построены на эллиптической кривой в поле для 80-битного . Мы сделали на системном уровне изменения для функции выбора случайных битов PBC библиотеки (в основном для кэширования файлов и устранения ненужных системных расчетов).

В таблице 4 перечислены результаты для работы с функциями с двумя выходами, для MAC подхода и нашего. MAC подход требует дополнительных 16,384 (), не-XOR цепочек для AES схем, в то время как оригинальная AES схема имеет 11 286 не-XOR цепочек. Так как количество не-XOR цепочек увеличивается почти в два раза в MAC подходе, их схема построения и оценки требует времени, примерно в два раза больше, чем у нас. Более того, MAC-подход имеет в два раза больше входных битов, чем наш подход, что удваивает время для упорядочивания входов для .

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

MAC подход Наш подход
Сумма (с) Сумма (с)
Прекомпозиция 498.9 0.0 498.9 294.1 0.0 294.1
ОТ передача 32.0 26.3 58.3 31.9 26.2 58.1
Выбор и отсечение 0.0 158.6 158.6 0.0 185.3 185.3
Проверка входа 0.0 50.6 50.6 0.0 24.4 24.4
Оценка 0.0 50.6 50.6 0.0 24.4 24.4
Для двух входов 0.0 0.0 0.0 0.7 0.6 1.3
Итого (с) 530.9 275.9 806.8 326.7 256.3 583.0

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

  1. University of Virginia, Charlottesville, VA 22904, E-mail: shelat@virginia.edu
  2. University of Virginia, Charlottesville, VA 22904, E-mail: shench@virginia.edu

Примечание

  1. Подробное описание этого протокола можно найти в работах Линделла и Пинкаса
  2. Грубо говоря, пара функций не имеет сцепки, если они (1) легко оцениваются, (2) одинаково распределены в диапазоне, и (3) трудно найти сцепку. Сцепкой называется пара элементов, один из домена , а другой из , которые сопоставляются одному и тому же элементу диапазона.
  3. Здесь и являются сокращениями для и .
  4. Хорошо известно, что функции без сцепок существуют как при дискретном логарифме, так и при интегральном распределении.
  5. q-SDF предположение в группе из простых чисел порядка утверждает, что для заданных , невозможно вывести пару , в которой
  6. Пусть и это две группы простых чисел порядка . справедливо, если (1) для любых и (2) для любого генератора, при , и (3) для любых легко вычислить значение .

Литература

  1. 1,00 1,01 1,02 1,03 1,04 1,05 1,06 1,07 1,08 1,09 1,10 1,11 1,12 Lindell, Y., Pinkas, B.: An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007)
  2. 2,0 2,1 2,2 2,3 2,4 Jarecki, S., Shmatikov, V.: Efficient Two-Party Secure Computation on Commit- ted Inputs. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 97–114. Springer, Heidelberg (2007)
  3. 3,0 3,1 3,2 3,3 3,4 3,5 3,6 3,7 3,8 3,9 Lindell, Y., Pinkas, B.: Secure Two-Party Computation Via Cut-and-Choose Obliv- ious Transfer. Crypto ePrint Archive (2010), http://eprint.iacr.org/2010/284
  4. Yao, A.: Protocols for Secure Computations. In: 23rd Annual Symposium on Foun- dations of Computer Science, pp. 160–164. IEEE Computer Society, Los Alamitos (1982)
  5. Goldreich, O., Micali, S., Wigderson, A.: How to Play ANY Mental Game. In: 19th Annual ACM Symposium on Theory of Computing, pp. 218–229. ACM, New York (1987)
  6. 6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 Pinkas, B., Schneider, T., Smart, N., Williams, S.: Secure Two-Party Computation Is Practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 250–267. Springer, Heidelberg (2009)
  7. 7,0 7,1 7,2 7,3 Mohassel, P., Franklin, M.: Efficiency Tradeoffs for Malicious Two-Party Compu- tation. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 458–473. Springer, Heidelberg (2006)
  8. 8,0 8,1 Woodruff, D.: Revisiting the Efficiency of Malicious Two-Party Computation. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 79–96. Springer, Heidelberg (2007)
  9. Nielsen, J., Orlandi, C.: LEGO for Two-Party Secure Computation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 368–386. Springer, Heidelberg (2009)
  10. Kolesnikov, V., Schneider, T.: Improved Garbled Circuit: Free XOR Gates and Ap- plications. In: Aceto, L., Damg ̊ard, I., Goldberg, L., Halld ́orsson, M., Ing ́olfsd ́ottir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 486–498. Springer, Heidelberg (2008)
  11. 11,0 11,1 Kiraz, M., Schoenmakers, B.: An Efficient Protocol for Fair Secure Two-Party Computation. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 88–105. Springer, Heidelberg (2008)
  12. 12,0 12,1 12,2 Kiraz, M.: Secure and Fair Two-Party Computation. Ph.D. thesis, Technische Universiteit Eindhoven (2008)
  13. 13,0 13,1 Camenisch, J., Chaabouni, R., Shelat, A.: Efficient Protocols for Set Membership and Range Proofs. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 234–252. Springer, Heidelberg (2008)
  14. 14,0 14,1 14,2 14,3 Kiraz, M., Schoenmakers, B.: A Protocol Issue for The Malicious Case of Yao’s Garbled Circuit Construction. In: 27th Symposium on Information Theory in the Benelux, pp. 283–290 (2006)
  15. 15,0 15,1 Lindell, Y., Pinkas, B., Smart, N.: Implementing Two-Party Computation Efficiently with Security Against Malicious Adversaries. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 2–20. Springer, Heidelberg (2008)
  16. Naor, M., Pinkas, B.: Oblivious transfer with adaptive queries. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, p. 791. Springer, Heidelberg (1999)
  17. 17,0 17,1 17,2 Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and com- posable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008)
  18. Goldreich, O., Kahan, A.: How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. Journal of Cryptology 9, 167–189 (1996)
  19. Rabin, M.: How to Exchange Secrets by Oblivious Transfer. Tech. Rep. TR-81, Harvard Aiken Computation Laboratory (1981)
  20. Brassard, G., Cr ́epeau, C., Robert, J.M.: All-or-Nothing Disclosure of Secrets. In: Odlyzko, A. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 234–238. Springer, Heidelberg (1987)
  21. Pairing-Based Cryptography Library (2006), http://crypto.stanford.edu/pbc/