Многопоточные вычисления для редукции модуля без битовой декомпозиции и обобщение битовой декомпозиции

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:06, 30 ноября 2015.
Multiparty Computation for Modulo Reduction without Bit-Decomposition and a Generalization to Bit-Decomposition
Finding Second Preimages of Short Messages for.png
Авторы Chao Ning [@: 1]
Qiuliang Xu [@: 2]
Опубликован 2010 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал


Аннотация Побитовое разложение, предложенное Дамгардом и др. является мощным средством для вычисления с несколькими участниками (МРС). При заданном общем секрете а, участникам можно вычислить общие значения бит а за определённое число циклов. С помощью побитового разложения, протоколов с непрерывным значением цикла можно построить различные МРС задачи. Однако, побитовое разложение довольно ресурсоёмко, так что построение протоколов для МРС задач без принятия во внимания также и побитового разложения – бесполезно. При вычислении с несколькими участниками есть один насущный вопрос – будет ли решена задача сокращения по модулю за определённое значение циклов без побитового разложения.
В данной работе мы предлагаем протокол (открытый) сокращения по модулю без использования побитового разложения. Этот протокол оперирует при сложности непрерывного цикла и сложности линейного вычисления. Более того, покажем также обобщённый протокол побитового разложения, который может, за непрерывный цикл, преобразовывать общий секрет а в общие цифровые значения а, а также общие значения бит для каждого числа. Числа могут быть представлены по основанию для любого
Ключевые слова: Вычисление с несколькими участниками, Непрерывные циклы, сокращение по модулю, обобщение побитового разложения.

Введение

Безопасное вычисление с несколькими участниками (МРС) реализует вычисление функции , когда входы для есть секретные значения каждого различного участника. После выполнения МРС протокола, участники получают только предопределённые выходные значение и ничто другое, т.о. гарантируется конфиденциальность их входом. Хотя обобщенные решения для МРС уже существуют [1][2], эффективность этих протоколов довольно не высока. Поэтому мы сфокусировались на создании эффективных протоколов для определённых функций. Точнее говоря, нас интересует целочисленная арифметика применительно к теории информации [3].

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

Для установления взаимосвязи арифметических схем и Булевых схем, Дамгард и др. [4]предложили новый протокол, называемый битовым разложением, который преобразовывает общий разделяемый секрет в разделяемые биты . Этот протокол очень полезен как в теории, так и на практике. Однако, протокол битового разложения относительно ресурсоёмкий касательно сложностей цикла и вычисления. Т.о. работа по созданию протоколов (с постоянными циклами) для МРС задач без битового разложения не только будет значимой, но и реализуемой. Недавно, в [3] Нишид и др. создали более эффективные протоколы по сравнению с предыдущими, в которых проверка интервала и проверка эквивалентности разделённых секретов были без реализации битового разложения. Однако, всё же оставался вопрос – можно ли решить задачу сокращения по модулю без выполнения битового разложения [8]. В данной работе показан линейный протокол для (открытой) задачи сокращения по модулю без выполнения битового разложения. Более того, протокол битового разложения [4] может только разбить общий секрет а на общие биты . Однако, в особенности на практике, часто необходимо иметь общие цифровые значения а. Здесь они могут быть по основанию для любого . К примеру, в действительности, целые значения (практически всегда) представляются как цифровые значения по основанию . Т.о., МРС протоколы реализуемые на практике могут зачастую требовать цифровые значения по основанию для секретных разделяемых целых значений. Давайте запишем и другие примеры. Если целые значения используются для времени и даты, то требуются цифровые значения по основанию . Т.е. для соответствия этим требованиям, мы предлагаем в данной работе обобщение битового разложения.

Наш вклад

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

Открытую задачу сокращения по модулю можно обобщить как:

где и

В существующих протоколах открытого сокращения по модулю [4][8], присутствует битовое разделение, приводящее к сложности вычисления. Более того, в наихудшем случае, сложность вычисления данного протокола может возрасти до . В частности, существующий протокол сокращения по модулю использует протокол битового разложения для уменьшения «размеров» задачи, и т.о. применяется до нетривиальных сравнений, для того чтобы определить конечный результат. Это фактически «полный перебор». Если битовая длина входов по сравнению с протоколом относительно большая, например, зачастую это , общая сложность увеличиться до . Т.о. эффективность протокола может быть очень мала. Для решения этой проблемы, предлагается протокол, который достигает сложности непрерывного цикла и сложности линейных вычислений, для открытого сокращения по модулю без использования битового разложения. К тому же, мы также представим расширенный протокол который может выводить общие биты по модулю , т.е. .

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

Для примера, покажем следующее. Возьмём бинарное число

Если задаётся для протокола битового разложения в качестве входа, то выходом будет

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

</math>

что значительно отличается от выхода битового разложения.

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

Также, очень рекомендуется заинтересованным читателям просмотреть [9], что является полной версией данной работы. Многие детали в данной работе опущены для экономии места.

Схожие работы

Задача битового разложения является основной в МРС и была практично решена Алгешеймером и др. в [10]. Однако, это решение не было для непрерывных циклов и может оперировать только значениями, которые заметно меньше . Дамгард и др. предложили первое решения с непрерывными циклами (полными) для задачи битового разложения в [4]. Это продвинутая работа основывается на схемах разделения линейного секрета [1][11]. Независимо, Шоенмейкер и Тилс [12] решили данную задачу битового разделения для вычислений с несколькими участниками основанных на (Пайлеровских) пороговых гомоморфических криптосистемах [13][14]. Что удивительно, Нишид и Охта представили также решения, осуществляющие проверку интервала и эквивалентности разделяемых секретов без битового разложения [3]. Их методики были нововведением и довольно значительно нам помогли. Недавно, Тофт показал новый способ, который может уменьшить вычислительную сложность битового разложения до практически линейной [5]. Хотя мы не нацеливались на «практически» линейное свойство протоколов, некоторые методики представленные в этой работе оказались для нам очень полезными. В последующей работе Рейстад и Тофт представили линейный протокол битового разложения [15]. Однако, безопасность их протокола не идеальна.

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

Начальные сведения

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

Обозначения и Определения

Вычисление с несколькими участниками рассмотренное в данной работе основывается на схемах разделения линейного секрета, таких как схема Шамира [17]. Как упоминалось ранее обозначим соответствующее поле как , где это простое значение с бинарной длинной .

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

Как и в [3], запишем , где есть Булева проверка, это значит, что и тогда и только тогда, когда верно. К примеру, используем для обозначения выхода протокола сравнения, т.е. тогда и только тогда, когда выполняется .

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

Определим . Очевидно, длинна , когда закодирован по основанию . Отметим, что т.к .

Для любого разделение секрета определяется как . Используем для обозначения побитового разделения .

Используем для обозначения разделения зависимого от цифровых значений. За обозначим разделение i-ого цифрового значения по основанию для с .

Побитовое цифровое разделение , обозначенное как , определяется следующим образом:

где обозначает побитовое разделение i-ого цифрового значения по основанию для . Отметим, что имеет бит.

Иногда если можно вывести из контекста, то есть возможность записать (или ) как (или ) для простоты.

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

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

Для заданного , необходим протокол выявляющий , который обозначается

Запишем команду , где и это означает следующее:

если , то есть ; в противном случае, есть .

Назовём эту команду – командой выбора условия. Когда все переменные в этой команде открытые, этот «выбор» непременно реализуется. Когда переменные разделены или разделены побитно, это также реализуемо. В частности, команду

можно реализовать с помощью установки

на которую потратиться 1 цикл и 1 умножение; а команду

можно реализовать следующей процедурой:


For in parallel:

Отметим, что вышеуказанная процедура применяет цикл, вызовов умножения.

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

Известные примитивы

Теперь просто представим несколько существующих примитивов, которые являются важными составными частями для данной работы. Все эти примитивы показаны в [4].

  • Протокол случайного бита (Random-Bit). Протокол случайного бита является наиболее основным примитивом, который может генерировать разделяемый равномерный случайный бит неизвестный никому из участников. В контексте разделения линейного секрета, рассматриваемого в случае данной работы, он выполняется за цикла и умножения.
  • Условный протокол с зависимостью от битов (Bitwise-LessThen). Для заданных двух зависимых от битов разделяемых входа и Bitwise-LessThen протокол может вычислить разделение бита . Отметим, что используя метод из [5], этот протокол можно реализовать за циклов и умножений. Заметим также, что выполняется для , что часто происходит на практике. Т.о. для простоты, будем рассматривать сложность протокола относительно циклов и умножений.
  • Сложение с зависимостью от битов (Bitwise-Addition). Для заданных двух зависимых от битов разделяемых входа и Bitwise-Addition протокол выводит . Важно то, что протокол будет реализовываться для при выполнении над целыми числами, а не (только) . Этот протокол на который уходит циклов и умножений, является наиболее ресурсоёмким протоколом побитового разложения [4]. Мы не будем использовать данный примитив в нашей работе, а воспользуемся Вычитанием с зависимостью от битов (Bitwise-Subtraction) вместо него. Однако, асимптотическая сложность нашего Bitwise-Subtraction протокола будет той же что и для Bitwise-Addition т.к. они оба включают в себя протокол генерации префикса, который требует умножений. Покажем Bitwise-Subtraction чуть позже.

Простое представление наших новых примитивов

В данном разделе мы покажем в простой форме новые примитивы реализуемые в данной работе. Мы только рассмотрим входные и выходные значения данных протоколов, и прокомментируем их. Все эти новые примитивы будут детально описаны в Разделе 6.

  • Bitwise-Subtraction. Протокол Bitwise-Subtraction принимает два разделяемых зависимых от битов значения и и выводит . Этот протокол фактически впервые был предложен в [5] и пересмотрен (в другом более общем виде) в данной работе. В наших протоколах, необходимо лишь уменьшенная версия (Bitwise-Subtraction) для которой требуется . И выполнение этого уменьшенного протокола определяется как

на что затрачивается циклов и умножений.

  • BORROWS (Заимствование). Этот протокол используется как подпротокол в Bitwise-Subtraction протоколе указанном выше для вычисления заимствованных битов (также как и в Bitwise-Subtraction* протоколе). Для двух заданных разделений с зависимостью от битов и , этот протокол выводит

где есть разделение заимствованного бита на .

  • Random-Digit-Bit. Для заданного в качестве входа, Random-Digit-Bit протокол выводит

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

  • Digit-Bit-wise-LessThen. Digit-Bit-wise-LessThen протокол принимает два цифровых зависимых от битов разделяемых значения и и выводит

Сложность данного протокола будет циклов и умножений.

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

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

Сложность данного протокола снизиться до цикла и умножения.

При помощи вышеуказанных примитив можно создать протокол сокращения по модулю (Modulo-Reduction) и протокол цифрового битового разложения по основанию m, которые детально будут отдельно рассмотрены в Разделе 4 и Разделе 5.

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

В данном разделе показан (открытый) протокол сокращения по модулю, который реализован без использования побитового разложения. Этот протокол будет с непрерывными циклами и только с умножениями. Проще говоря, наш протокол сокращения по модулю будет в действительности протоколом наименее значимого цифрового значения и может быть обобщён в протокол наименее значимого битового значения (т.е. LSB протокол) из [3]. Напомним, что для целого , разделение наименее значимого цифрового значения по основанию для , будет обозначаться , и при разделении с зависимостью от битов наименее значимого цифрового значения по основанию m для а будет обозначаться как . Протокол описан детально в Протоколе 1.

TemplateDifinitionIcon.svg Определение «Протокол 1. Протокол сокращения по модулю, , для вычисления остатка разделяемого целого значения по модулю открытого целого значения. »


Вход: c
Выход:
Выполнение:

. Заметим, что подразумевает
. Где подразумевает


. (Условный выбор команды)
(Добавление над целыми числами)
.
.




Возвращаем

Правильность: При помощи моделирования процесса сложения по основанию , протокол выражает что является . См. [9] для более подробного описания.

Конфиденциальность: Единственным местом возможной утечки информации может быть (1.а), где используется команда reveal. Однако, выявленное значение, т.е. с, равномерно случайно, т.о. она не предоставляет никакой информации о секрете . Т.о. гарантируется конфиденциальность.

Сложность: Сложность здесь в основном складывается из выполнения подпротоколов. Отметим, что 2 выполнения Bitwise-LessThen и выполнение Digit-Bit-wise-LessThen можно реализовать параллельно. В целом это потребует цикла и

умножений. Напомним, что т.о. сложность взаимосвязи ограничена сверху умножениями.

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

TemplateDifinitionIcon.svg Определение «Протокол 2. Расширенный протокол сокращения по модулю, , для вычисления разделяемого остатка с зависимостью от бит общего целого значения по модулю открытого целого значения. »








Добавлнение над целыми числами.

Включая L(m) умножений








M - уменьшаемое
S - вычитаемое

Возвращаем

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

умножениях.

Обобщение побитового разложения

В данном разделе мы предлагаем наше обобщение побитового разложения, т.е. протокол цифрового побитового разложения по основанию . Детали протокола показаны в Протоколе 3. Основополагающие аспекты этого протокола схожи с протоколом побитового разложения [5].

TemplateDifinitionIcon.svg Определение «Протокол 3 цифрового побитового разложения по основанию - , для преобразования общего секрета в общее цифровое значение с зависимостью от битов









Правильность его детально описана в [9]. Конфиденциальность ясна. Общая сложность данного протокола будет циклов и

умножений. Сложность связности ограничена сверху умножениями т.к .

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

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

Реализация примитивов

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

Вычитание с зависимостью от битов

Здесь описан протокол вычитания с зависимостью от битов. В действительности этот протокол уже представлялся в [5]. Они сократили задачу вычитания с зависимостью от битов до задачи постфиксного сравнения. Пересмотрим задачу вычитания с зависимостью от битов и решим её (очень) простым способом для протокола сложения с зависимостью от битов [4].

Как указывалось в разделе 3, сперва представим сокращённый протокол (вычитания с зависимостью от битов), которому требуется чтобы уменьшаемое было не меньше вычитаемого. В данной работе используется только это сокращённая версия. Общая версия без вышеуказанного упрощения может быть получена с помощью условного протокола с зависимостью от битов. Для более детального обсуждения данного вопроса обращайтесь к [9]. Для заданного протокола BORROWS, который может вычислить разделения заимствованных битов, протокол Bitwise-Subtraction* можно реализовать как показано в Протоколе 4.


TemplateDifinitionIcon.svg Определение «Протокол 4. Упрощённый протокол вычитания с зависимостью от битов, для вычисления зависимых от битов разделений разности между двумя разделёнными значениями с зависимостью от битов. Этому протоколу требуется, чтобы уменьшаемое было не меньше вычитаемого.»








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

Вычисление заимствованных битов

Теперь опишем BORROWS протокол, который может вычислить разделения заимствованных битов. В действительности, наш BORROWS протокол является значительным упрощением CARRIES протокола из [4]. Т.о. здесь мы опишем только то, чем они отличаются. Как и в [4] используем оператор где которая определена с помощью для всех для всех для всех . Следовательно, представляет собой оператор заимствованного распределения, в то время как в [15] это вспомогательный оператор распределения. При вычислении (где выполняется ) с двумя разделяемыми входами с зависимостью от битов

и

для , пусть тогда и только тогда, когда заимствованное значение устанавливается в позицию (т.е. ); тогда и только тогда, когда заимствованное значение распределено в позицию (т.е. ). Можно легко проверить то, что (т.е. i-ый заимствованный бит, что означает необходимость взятия для i-ого бита «» из -ого бита) тогда и только тогда, когда Можно увидеть, в том случае, когда представляет собой заимствованного распределения и в случае, когда это вспомогательный оператор распределения, что правила для (т.е. и для всех ) будут в точности такими же. Это означает, что при вычислении заимствованных битов, когда все получены, оставшаяся процедура нашего BORROWS протокола будет заключаться в (полностью) аналогичных действиях, что и в протоколе CARRIES (из [4]). Т.о. единственная разница заключается в процедуре вычисления , которая кратко описана ниже.

Как и в [4], представляем с битовыми векторами

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

Протокол случайного цифрового бита

Теперь представим протокол случайного цифрового бита для генерации случайного общего цифрового значения по основанию с зависимостью от битов, которое здесь обозначено как . В действительности, есть случайное целое значение удовлетворяющее . Детально он расписан в Протоколе 5.

TemplateDifinitionIcon.svg Определение «Протокол 5. Протокол случайного цифрового бита, , для генерации задачи случайного общего цифрового значения. Цифровое значение будет по основанию для любого  »









Для доказательства правильности обратитесь в [9]. Что касается конфиденциальности, когда этот протокол вынужденно не завершает свою работу, единственной информацией которую можно получить это , что в свою очередь является изначально фактом. Что касается сложности то, когда m не степень , общая сложность одного выполнения этого протокола будет циклов и умножений. Как в [4] используя границу Чернофа, можно увидеть, что этот протокол необходимо повторить параллельно для получения меньшей вероятности отказа, и тогда циклическая сложность будет всё равно , а сложность связности становится равной умножениям.

Протокол Digit-Bit-Wise-LessThan

Протокол Digit-Bit-Wise-LessThan представленный здесь является действительным обобщением Bitwise-LessThen пртокола. Напомним, что когда записывается , где это Булева проверка, получается, что и тогда и только тогда, когда верно. Детали протокола описаны в Протоколе 6.

TemplateDifinitionIcon.svg Определение «Протокол 6. Digit-Bit-Wise-LessThan протокол, , для сравнения двух цифровых разделяемых значений с зависимостью от битов. »
















Правильность показана в [9]. Конфиденциальность следует из использования конфиденциальных подпротоколов. Сложность этого протокола будет заключаться в циклах и (около) умножениях.

Протокол случайных вычисляемых цифровых битов (Random-Solved-Digits-Bits)

Протокол Random-Solved-Digits-Bits является важным примитивом который может генерировать цифровое разделяемое случайное значение с зависимостью от битов неизвестное ни одному участнику. Это есть в действительности обобщение Random-Solved-Bit протокола из [4]. Детально этот протокол представлен в Протоколе 7.

Напомним, что представление зависимое от битов с наиболее значимым цифровым значением по основанию для будет . Предположим, что есть наиболее левая «» в . Тогда для того, чтобы получить допустимую вероятность отказа, битовая длинна наиболее значимого цифрового значения по основанию для должна быть , т.к. допустимый должен быть меньше чем . В нашем протоколе, для простоты, полагаем, что . При этом предположении, можно сгенерировать используя Random-Digit-Bit протокол. Если то можно сгенерировать используя Random-Bit протокол непосредственно.


TemplateDifinitionIcon.svg Определение «Протокол 7. Random-Solved-Digits-Bits протокол, , для объединённой генерации цифрового разделяемого значения с зависимостью от битов, которое равномерно случайно берётся из

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






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

Протокол Digit-Bit-Wise-Subtraction

В данном разделе мы показали детально сокращённую версию, Digit-Bit-Wise-Subtraction*, для которой требуется, чтобы уменьшаемое было не меньше вычитаемого. Общая версия, которую можно реализовать с помощью методов для протокола вычитания с зависимостью от битов и которая не используется в данной работе, а была опущена для простоты.

  • Сокращённый Digit-Bit-Wise-Subtraction. Теперь опишем детально Digit-Bit-Wise-Subtraction* протокол. Этот протокол является новым и самым главным примитивом для нашего протокола цифрового битового разложения по основанию . Детально он представлен в Протоколе 8.


TemplateDifinitionIcon.svg Определение «Протокол 8. Сокращённый Digit-Bit-Wise-Subtraction протокол, , для вычисления разности цифрового битового разложения двух цифровых общих значений зависимых от битов при уменьшаемом большем, чем вычитаемое.»


полагаем, что

























Заметим, что C - публичный.


полагая, что m не степени 2







Правильность детально показана в [9] . Конфиденциальность следует из того, что мы вызываем конфиденциальные подпротоколы. Сложность данного протокола будет циклов и умножений. Связующая сложность будет ограничена сверху умножениями т.к. .

  • Упрощённая версия. Если нет необходимости в , а можно использовать (только) , то получается упрощённая версия вышеуказанного протокола, , при помощи простой замены всех операций после операции (8.а) на следующее:






Отметим, что этот процесс практически не требует никаких затрат ресурсов. Правильность и конфиденциальность доказываются просто. Сложность данного протокола уменьшается до циклов и умножений т.к. ресурсоёмкий Bit-Wise-Subtraction* протокол пропускается.

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

Т.о. используя Bitwise-LessThen протокол в обоих случаях, на что потребуется на больше умножений и больше циклов чем для простого выполнения [5] , получим все . Тогда как и в BORROWS протоколе (или CARRIES протоколе) целевые заимствованные биты (для каждой позиции цифрового значения) можно получить с помощью протокола общего префикса, для которого понадобится циклов и умножений. Т.о. протокол можно реализовать за цикл и за (менее чем) умножений. Напомним, что Тогда для относительно большого , например , где связующая сложность может быть достаточно мала.

Комментарии

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

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

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

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

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

Приложения и дальнейшая работа

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

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

Слова благодарности

Мы хотели бы поблагодарить анонимных авторов за их добросовестные и полезные комментарии.


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

  1. School of Computer Science and Technology, Shandong University, Jinan, 250101, China E-mail: [1]
  2. School of Computer Science and Technology, Shandong University, Jinan, 250101, China E-mail: [2]

Литература

  1. 1,0 1,1 Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness Theorems for Noncryptographic Fault-Tolerant Distributed Computations. In: 20th Annual ACM Symposium on Theory of Computing, pp. 1–10. ACM Press, New York (1988)
  2. Goldreich, O., Micali, S., Wigderson, A.: How to Play Any Mental Game or AComplete Theorem for Protocols with Honest Majority. In: 19th Annual ACM Symposium on Theory of Computing, pp. 218–229. ACM Press, New York (1987)
  3. 3,0 3,1 3,2 3,3 3,4 3,5 3,6 Nishide, T., Ohta, K.: Multiparty Computation for Interval, Equality, and Comparison without Bit-Decomposition Protocol. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 343–360. Springer, Heidelberg (2007)
  4. 4,00 4,01 4,02 4,03 4,04 4,05 4,06 4,07 4,08 4,09 4,10 4,11 4,12 4,13 4,14 4,15 4,16 4,17 Damgard, I.B., Fitzi, M., Kiltz, E., Nielsen, J.B., Toft, T.: Unconditionally Secure Constant-Rounds Multi-Party Computation for Equality, Comparison, Bits and Exponentiation. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp.285–304. Springer, Heidelberg (2006)
  5. 5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 Toft, T.: Constant-Rounds, Almost-Linear Bit-Decomposition of Secret Shared Values. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol. 5473, pp. 357–371. Springer, Heidelberg (2009)
  6. Chandra, A.K., Fortune, S., Lipton, R.J.: Lower Bounds for Constant Depth Circuits for Prefix Problems. In: D.ıaz, J. (ed.) ICALP 1983. LNCS, vol. 154, pp.109–117. Springer, Heidelberg (1983) 500 C. Ning and Q. Xu
  7. Chandra, A.K., Fortune, S., Lipton, R.J.: Unbounded Fan-In Circuits and Associative Functions. In: 15th Annual ACM Symposium on Theory of Computing, pp.52–60. ACM Press, New York (1983)
  8. 8,0 8,1 Toft, T.: Primitives and Applications for Multi-party Computation. PhD thesis, University of Aarhus (2007), http://www.daimi.au.dk/~ttoft/publications/dissertation.pdf
  9. 9,0 9,1 9,2 9,3 9,4 9,5 9,6 9,7 Ning, C., Xu, Q.: Multiparty Computation for Modulo Reduction without Bit-Decomposition and A Generalization to Bit-Decomposition. Cryptology ePrint Archive, Report 2010/266, http://eprint.iacr.org/2010/266
  10. Algesheimer, J., Camenisch, J.L., Shoup, V.: Efficient Computation Modulo AShared Secret with Application to the Generation of Shared Safe-Prime Products.In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 417–432. Springer, Heidelberg(2002)
  11. Gennaro, R., Rabin, M.O., Rabin, T.: Simplified Vss and Fast-Track Multiparty Computations with Applications to Threshold Cryptography. In: 17th ACM Symposium on Principles of Distributed Computing, pp. 101–110. ACM Press, New York (1998)
  12. Schoenmakers, B., Tuyls, P.: Efficient Binary Conversion for Paillier Encrypted Values. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 522–537. Springer, Heidelberg (2006)
  13. Cramer, R., Damg˚ard, I.B., Nielsen, J.B.: Multiparty Computation from Threshold Homomorphic Encryption. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 280–300. Springer, Heidelberg (2001)
  14. Damgard, I.B., Nielsen, J.B.: Universally Composable Efficient Multiparty Computation from Threshold Homomorphic Encryption. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 247–264. Springer, Heidelberg (2003)
  15. 15,0 15,1 15,2 Reistad, T., Toft, T.: Linear, Constant-Rounds Bit-Decomposition. In: Lee, D., Hong, S. (eds.) ICISC 2009. LNCS, vol. 5984, pp. 245–257. Springer, Heidelberg (2010)
  16. Guajardo, J., Mennink, B., Schoenmakers, B.: Modulo Reduction for Paillier Encryptions and Application to Secure Statistical Analysis. In: Sion, R. (ed.) FC 2010. LNCS, vol. 6052, pp. 375–382. Springer, Heidelberg (2010)
  17. Shamir, A.: How to Share A Secret. Communications of the ACM 22(11), 612–613 (1979)