Обязательства постоянного размера для полиномов и их применение

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 00:31, 17 июня 2016.
Creating Constant-Size Commitments to Polynomials and Their Applications
Polynomial-commitments-article-logo.PNG
Авторы Aniket Kate[@: 1],
Gregory M. Zaverucha[@: 2] and
Ian Goldberg[@: 3]
Опубликован 2010 г.
Сайт International Association for Cryptologic Research
Перевели Maxim Nesterov
Год перевода 2015 г.
Скачать оригинал

__NUMBEREDHEADINGS__

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


Доступна расширенная версия этого документа [1]. Это исследование завершено в Университете Ватерлоо.

Введение

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

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

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

Наш вклад. Главным вкладом этой статьи является эффективная схема для создания обязательства для полиномов над группой билинейного спаривания, названной PolyCommitDL, со следующими особенностями. Размер обязательства является константой, одним элементом группы. Пользователь может открыть обязательство таким образом, чтобы получить любую корректную оценку вместе с элементом, названным «свидетель», который позволяет проверяющему подтвердить, что на самом деле оценка в точке полинома . Утверждение основывается на алгебраическом свойстве полиномов , которое заключается в том, что прекрасно делит полином для любых . Свойство сокрытия схемы строится на DL-предположении. Свойство связывания схемы доказывается согласно SDH -предположению [4] ( Strong Diffie-Hellman Problem (аналогично Strong RSA)). Используя технику, похожую на обязательства Педерсена, мы также определяем более сильную схему обязательства PolyCommitPed, которая имеет безоговорочное связывание и вычислительно связана с SDH-предположением.

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

Во-первых, мы применим PolyCommit схемы для протокола проверяемого разделения секрета Фельдмана (VSS ) [7]. Новый VSS протокол требует передачи размера в сравнении с , требуемой в наиболее известных протоколах в литературе (где – число участников) [7][2].

Во-вторых, мы определим и используем PolyCommit схемы для создания слабого типа доказательства с нулевым разглашением (ZKS ) [8]. ZKS – обязательство для набора такого, что пользователь может подтвердить, что или без разглашения дополнительной информации о , даже о . Мы определим множества с почти нулевым разглашением как ZKS, которое не пытается спрятать размер обязываемого множества. Этого достаточно для большинства применений множеств с нулевым разглашением и наша конструкция имеет постоянный размер доказательств (не)принадлежности к множеству в сравнении с наиболее известными конструкциями ZKS , которые требуют неконстантную стоимость связи [9][10]. Мы применим такое же ослабление к элементарным базам данных с нулевым разглашением ( ZK-EDB) и получим также константную стоимость связи.

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

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

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

План. В оставшейся части этого параграфа, мы сравним наши вклады со связанной работой (работа, связанная с каждым применением включена в соответствующий параграф). В §2, мы охватим некоторый предварительный материал и опишем наши криптографические предположения. §3 определяет полиномиальные обязательства и представляет наши вклады. §4 посвященный применениям в то время, как §5 презентует несколько открытых проблем. Из-за ограничения объема все доказательства безопасности включены в расширенную версию [1].

Связанная работа. Похожая на нашу схему хэш-дерево Меркла [12] позволяет создавать обязательство для многих значений в виду одного элемента. Здесь листья бинарного дерева являются сообщениями. Каждый нелистовой узел имеет значение , где и его дети, и – устойчивая к коллизиям хэш-функция. Можно открыть обязательство для отдельного сообщения раскрывая сообщение и выделить путь наверх к корню дерева. Сложность открытия составляет и сравнима с в нашей схеме, где - число всех (листьев) элементов.

Chase и др. [13] вводит обязательство mercurial для построения ZKS , которое в итоге приводит к схемам обязательства для обязывания вектора сообщений [9][10]. Catalano и др. [9], и Libert, и Yung построили вектор схем обязательства под названием trapdoor t-mercurial commitments. Безопасность обоих схем основывается на предположениях, подобных SDH , и их системные параметры имеют размер , как и в нашей схеме. В [9], все сообщения должны быть раскрыты при открытии, в то время как в [10] пользователь может открыть обязательство для отдельного сообщения. Однако в [10] невозможно иметь произвольные индексы для обязываемых сообщений, поскольку каждое из обязываемых сообщений ассоциировано со значением в параметрах системы для . Наша схема не имеет такого ограничения для индексов, обеспечивая большую гибкость.

Другим связанным примитивом является аккумулятор [14], который объединяет большое множество входных элементов в один элементов и может обеспечивать свидетеля как доказательство, что элемент включен в аккумулятор. Далее возможно использовать свидетеля, чтобы доказать (в нулевом разглашении), что элемент включен в аккумулятор. Camenisch и Lysyanskaya [15] расширили понятие для динамических аккумуляторов, которые поддерживают эффективные обновления. Au и др. [16] обнаружили, что спаренный аккумулятор Nguyen [17] является ограниченным аккумулятор, то есть только фиксированное число элементов может быть аккумулированно. Они продолжили использовать ограниченные аккумуляторы для построения компактной e-cash схемы [18]. Однако, аккумулированные элементы в этой схеме не упорядочены, что делает схему неподходящей для аккумулирования полиномов. В то время как наши PolyCommit схемы имеют такие же особенности как нединамический аккумулятор, они имеют дополнительные свойства (сокрытие и пакетные открытие) и являются более общими,поскольку мы можем обязывать полином вместо множества.

Подготовительный этап

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

Мы используем предположение дискретного логарифма (DL ) [12] и t-strong Диффи-Хеллмана (t-SDH ) [4] чтобы доказать безопасность схем PolyCommitDL и PolyCommitPed. Безопасность двух дополнительных параметров схем требует обобщения инверсии предположения t-Диффи-Хеллмана (t-DHI ) [19] [20] и билинейной версии t-SDH и t-BSDH предположений [5].

TemplateDifinitionIcon.svg Определение «Определение 1. Предположение дискретного логарифма (DL).»

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

Mitsunari, Sakai и Kasahara [19] ввели слабое предположение Диффи-Хеллмана, которое было переименовано в t-DHI предположение Boneh и Boyen [20], так как это предположение более сильное, чем предположение Диффи-Хеллмана особенно для больших значений . Смотри анализ безопасности Cheon [21].

t-DHI проблема предусматривает, что на вход подается , на выходе или эквивалентно (см. [22]) . В этом документе мы используем обобщение t-DHI предположение, где должно получить на выходе пару так, что . Мы назвали это предположение t-полиномиальное предположение Диффи-Хеллмана (t-polyDH ). Это предположение было косвенно получено [16][18] чтобы удовлетворить их требованию ограниченного[прим. 1] аккумулятора [17].


TemplateDifinitionIcon.svg Определение «Определение 2. t-полиномиальное предположение Диффи-Хеллмана (t-polyDH).»

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

Boneh и Boyen [4] определяют t-SDH предположение как более сильное предположение, чем t-DHI и имеющее экспоненциально много нетривиальных различных решений, каждой из которых применимо.


TemplateDifinitionIcon.svg Определение «Определение 3. t-полиномиальное предположение Диффи-Хеллмана (t-SDH). »

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

Безопасность расширения пакетного открытия наших схем версии обязательств требует билинейной версии t-SDH и t-BSDH предположения [5].


TemplateDifinitionIcon.svg Определение «Определение 4. t-Билинейное сильное предположение Диффи-Хеллмана (t-BSDH).»

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

Похожее предположение также сделано в [23], но имеет другое решение: , где дополнительный системный параметр.

Полиномиальные обязательства

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

Определение

Схема полиномиального обязательства состоит из шести алгоритмов: Setup, Commit, Open, VerifiPoly, CreateWitness и VerifyEval.

TemplateDifinitionIcon.svg Определение «Определение»

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

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

Open () выдает полином использованный для создания обязательства с информацией .

VerifyPoly () проверяет, что является обязательством для с информацией . Если да, то выдает 1, иначе 0.

CreateWitness () выдает , где - свидетель для оценки полинома в точке и информации .

VerifyEval () проверяет, что на самом деле оценка в точке полиномиального обязательства в . Если да, то выдает 1, иначе 0.

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

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

TemplateDifinitionIcon.svg Определение «Определение 5.»

(Setup, Commit, Open, VerifiPoly, CreateWitness и VerifyEval) являются безопасной схемой полиномиального обязательства, если она удовлетворяет следующими требованиям.

Корректность. Пусть и . Для обязательства , выданного Commit , и всех ,

- выход Open успешно проверяется VerifyPoly , и

- любой выход CreateWitness успешно проверяется VerifyEval .

Связывание полинома. Для всех злоумышленников  :

Связывание оценки. Для всех злоумышленников  :

Сокрытие. Пусть дан и для полинома такого, что для каждого ,

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

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

Конструкция: PolyCommitDL

Теперь мы покажем эффективную конструкцию схемы полиномиального обязательства.

PolyCommitDL основывается на алгебраическом свойстве полиномов  : замечательно делит полином для . В литературе Herzberg и др.[24] используется этот способ для схемы восстановления разделения.

TemplateDifinitionIcon.svg Определение «PolyCommitDL »

Setup () вычисляет две группы и порядка (обеспечивающие -битную безопасность) такие, что существует симметричное билинейное спаривание и для которого справедливо t-SDH предположение. Мы обозначим обобщённое билинейную спаренную группу как . Выберем образующий . Пусть будет , сгенерированный (возможно распределенным) доверенным центром. Setup также создает набор и выдает . не требуется в оставшейся части конструкции.

Commit () вычисляет обязательство для полинома степени или меньше . Для выдает как обязательство для .

Open () выдает обязываемый полином .

VerifyPoly () проверяет, что . Если для алгоритм выдает 1, иначе 0. Заметим, что это работает только когда .

CreateWitness () вычисляет и выдает , где свидетель в способе вычисления похож на выше.

VerifyEval () проверяет, что является оценкой в точке полинома обязываемого с помощью . Если , алгоритм выдает 1, иначе 0.

VerifyEval является корректным, так как

так как

TemplateTheoremIcon.svg Теорема Теорема 1.

PolyCommitDL является безопасной схемой обязательства (определенной в Определении 5) , для которой справедливы DL и t-SDH предположения в .

Доказательство
Доказательство дано в расширенной версии. Доказательство свойства связывания использует t-SDH предположение, в то время как доказательство свойства сокрытия использует DL предположение.


Конструкция: PolyCommitPed

PolyCommitPed также основывается на том же алгебраическом свойстве  : замечательно делит полином для  ; однако используется дополнительный рандомный полином для достижения безоговорочного сокрытия.

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

TemplateDifinitionIcon.svg Определение «PolyCommitPed»

Setup () вычисляет две группы и порядка (обеспечивающие -битную безопасность) такие, что существует симметричное билинейное спаривание  : и для которого справедливо t-SDH предположение. Мы обозначим обобщённое билинейную спаренную группу как . Выберем два образующих . Пусть будет , сгенерированным (возможно распределенным) доверенным центром. Setup также создает набор и выдает . Подобно PolyCommitDL, не требуется в оставшейся части конструкции.

Commit () выбирает степени и вычисляет обязательство для полинома степени или меньше . Для и выдает как обязательство для .

Open () выдает обязываемые полиномы и .

VerifyPoly () проверяет, что . Если для и алгоритм выдает 1, иначе 0. Заметим, что это работает только когда и и .

CreateWitness () вычисляет и и выдает . Здесь свидетель .

VerifyEval () проверяет, что является оценкой в точке полинома обязываемого с помощью . Если , алгоритм выдает 1, иначе 0.

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

TemplateTheoremIcon.svg Теорема Теорема 2.
PolyCommitPed является безопасной схемой обязательства (определенной в Определении 5), для которого справедливо t-SDH предположение в
Доказательство

Доказательство свойства связывания основано на t-SDH предположении, в то время как свойство сокрытия является безоговорочным.


Свойства

Далее мы обсудим некоторые важные свойства PolyCommitDL и PolyCommitPed.

Гомоморфизм. В §3.3 мы рассказали, что PolyCommitDL схема является (дополнительно) гомоморфной по своей природе. В полной версии мы покажем, что PolyCommitPed также является гомоморфным.

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

Trapdoor обязательство. Конструкции являются также схемами trapdoor обязательства, где . Подробности смотри в расширенной версии.

Пакетное открытие. В случае, когда должно быть открыто множество оценок в PolyCommitDL обязательстве, открытие может производиться пакетом для снижения вычислительной и коммуникационной нагрузки как пользователя, так и проверяющего, то есть одновременное открытие множества оценок дешевле, чем открытие каждой из этих оценок индивидуально, используя CreateWitness и VerifyEval. Пусть , есть множество индексов, которые должны быть открыты для обязательства , созданного по типу PolyCommitDL. Свидетель для значений для всех вычисляется как для полинома , где - остаток от деления полинома  ; то есть, , и для , . Мы опишем два алгоритм для пакетного открытия. Алгоритм CreateWitnessBatch () выдает , и алгоритм VerifyEvalBatch () выдает 1, если справедливо , и для всех .

В терминах безопасности, поскольку обязательства сформулированы одинаковым способом, так как алгоритм Commit PolyCommitDL и CreateWitnessBatch раскрывают информации не больше, чем запуск алгоритма CreateWitness PolyCommitDL индивидуально для любого пакета элементов, свойство сокрытия (Теорема 1) справедливо. Для связывания, у злоумышленника не должно быть возможности открыть пакет , содержащий индекс , таким образом, что противоречия со значением приведет к индивидуальному открытию индекса . Формально, мы утверждаем, что пакетное открытие является связанным, если справедливо следующее:

TemplateTheoremIcon.svg Теорема Теорема 3.
Конструкция CreateWitnessBatch, VerifyEvalBatch в §3.4 является связанной, что обеспечивается справедливостью t-BSDH предположения в группе .
Доказательство
Теорема доказана в полной версии.


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

Сильная корректность. VSS схемы требуют дополнительное свойство PolyCommit схемы: невозможность создания обязательства для полинома степени больше чем . Это называется свойством сильной корректности.

Определить сильную корректность для PolyCommit схемы не легко, например, существует много полиномов степени больше чем таких, что и таким образом является тривиально PolyCommitDL обязательством для некоторого полинома степени такого, что . Чтобы избежать этой тривиальности, мы потребуем, чтобы игрок должен убедить игрока , что он знает с помощью следующей игры. создает обязательство для упомянутого полинома степени . говорит индексов . выигрывает, если он сможет произвести , принимаемые алгоритмом VerifyEval и так, что интерполяция (в экспонентах) любых свидетелей создает полином степени . Аналогично для PolyCommitPed. Ссылаемся на расширенную версию статьи для доказательства следующей теоремы.

TemplateTheoremIcon.svg Теорема Теорема 4.
PolyCommitDL и PolyCommitPed имеют свойство сильной корректности если t-polySDH предположение справедливо в .
Доказательство
Ссылаемся на расширенную версию статьи для доказательства теоремы.


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

В дальнейшем, возведение в степень, необходимое при создании обязательства и свидетелей, может быть тривиально распараллелено. Также, поскольку вычисляется как результат степеней (иногда называемое мульти-возведение в степень), мы предлагаем использовать способы быстрого возведения в степень [26] вместо просто реализации. Также возможно предпросчитать и для использования во время проверки.

Применения

В этом параграфе мы расскажем об применениях наших схем обязательств к проверяемому разделению секрета (§4.1), множествам с нулевым разглашением и элементарным базам данных, и выборочное раскрытие подписанных данных и учетных записей (§4.3).

Проверяемое разделение секрета (VSS)

Для целых и таких, что , -схема разделения секрета [27][28] представляет собой метод, используемый дилером чтобы разделить секрет среди множества участников (фаза разделения Sh) таким образом, что в фазе восстановления Rec любое подмножество или больше честных участников может вычислить секрет , но подмножества размера или меньше – не могут. Более того, в разделении секрета узлам может понадобиться процедура проверки корректности значений, с которыми они работают, чтобы предотвратить вредоносное поведение дилера. Чтобы решить эту проблему, Chor и др. [29] ввели проверяемость в разделении секрета, которая привела к концепции проверяемого разделения секрета (VSS).

VSS схемы имеют два требования безопасности: секретность и корректность.

Секретность (VSS-S). -ограниченный злоумышленник, который компрометирует t узлов не может вычислить в течении Sh фазы.

Корректность (VSS-C). Восстановленное значение должно быть равно разделяемому секрету , или каждый честный узел заключает, что дилер является вредоносным, выводя .

При выборе вычислительной сложности, любое вредоносное поведение ловится честными узлами в Sh фазе и VSS-C свойства упрощается: значение восстановления должно быть равно разделяемому секрету.

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

Сильная Корректность (VSS-SC). Злоумышленник, который скомпрометировал узлов не должен иметь больше информации о , кроме той, которая подразумевается открытыми параметрами.

Feldman [7] разработал первый эффективный VSS протокол, который описывает базис всех VSS схем, описанных в литературе. В литературе используется обязательство дискретного логарифма или обязательство Педерсена в Feldman VSS для свойств связывания (корректность) и сокрытия (секретность). Обе эти схемы обязательства тривиально удовлетворяют свойству сильной корректности (VSS-SC) VSS, так как размер обязательства для полинома равен что эквивалентно (так как для оптимальной устойчивости ). Однако, обязательство для полиномов должно транслироваться для всех узлов, которое дает в результате линейный размер передачи для Feldman VSS и для их вариантов, а линейная сложность находится в интервале между сложностью сообщения и битовой сложностью. Наша задача состоит в том, чтобы уменьшить этот интервал, используя любую из PolyCommit схем. Далее, мы применим PolyCommitDL для существующих VSS схем, основанных на полиноме, и уменьшим размер транслируемого сообщения VSS на линейный коэффициент, сделав его равным сложности сообщения. Хотя PolyCommitDL могут быть использованы в любой одномерной схеме, основанной на полиноме, для простоты объяснения мы выбрали Feldman VSS.


Sh Фаза
  1. Чтобы разделить секрет , дилер выбирает случайный полином степени такой, что . Потом дилер начинает передавать .
  2. Для , вычисляет разделённую часть , свидетеля , и отправляет узлу через безопасный и аутентифицированный канал.
  3. После получения от , узел запускает алгоритм VerifyEval() . Если проверка не удалась, начинает передавать обвинительное сообщение в адрес .
  4. Если более чем узлов обвиняют , то дилер очевидно виновен, и его блокируют. Если нет, то для каждой стороны , передает соответствующую разделенную часть и свидетеля такого, что справедливо VerifyEval .
  5. Если любая из раскрытых частей не проходит алгоритм VerifyEval , блокируется и протокол останавливается. Если блокировки нет, каждый узел принимает .
Rec Фаза

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

Алг. 1. eVSS: Эффективная Feldman VSS с использованием PolyCommitDL

Наша эффективная Feldman VSS (eVSS) схема запускает один раз алгоритм Setup ( из PolyCommitDL , который выдает . В дальнейшем, так как мы работаем в синхронной коммуникационной модели, граница устойчивости необходима для VSS против -ограниченного Византийского (слушающего канал) злоумышленника, чтобы обеспечить корректность, так как число честных узлов, доступных в течении Sh и Rec фаз, должно быть, как минимум равно (требуемая граница). В Алг. 1 мы представили eVSS. который использует PolyCommitDL схему в Feldman VSS, В Sh и Rec фазах eVSS схемы методология VSS остается ровно такой же, как и Feldman VSS, за исключением того, что здесь обязательств вида для заменены одним полиномиальным обязательством . В дополнение, вместе с частью , теперь посылает свидетеля узлу . В общем, eVSS протокол требует связи вместо для Feldman VSS. В случае множества обвинений, дилер может использовать функцию пакетного открытия, описанную в §3.4, чтобы получить одного свидетеля для целого пакета. Более того, благодаря гомоморфной природе PolyCommit, eVss схема может быть легко преобразована в протокол распределенной генерации ключа [2].

TemplateTheoremIcon.svg Теорема Теорема 5.
eVSS протокол реализует синхронную VSS схему с VSS-S и VSS-SC свойствами для , обеспеченные справедливостью предположений DL, t-SDH и t-polyDH в
Доказательство

Нам необходимо доказать свойства секретности, корректности и сильной корректности синхронной VSS схемы. Секретность и корректность следуют прямо из Теоремы 1, в то время как Теорема 4 обеспечивает свойство сильной корректности. Секретность обеспечивается тем, что eVSS вычислительно скрыта для -ограниченного противника, и безоговорочно скрыта для -ограниченного противника. Корректность разделения является вычислимой.


PolyCommitDL может быть легко заменена PolyCommitPed в eVSS схеме выше. В этом случае мы достигнем свойства строгой секретности (VSS-SS), благодаря свойству безоговорочного сокрытия (Теорема 2) PolyCommitPed.

«Почти» ZKSs и «почти» ZK-EDBs

Micali и др. [8] дают определение множествам с нулевым разглашением (ZKSs). В основном ZKS разрешает пользователю создавать короткое обязательство для множества значений , такое что он может потом эффективно подтвердить утверждения в виде или в нулевом разделении. Никакой дополнительной информации, связанной с . Возможно, наиболее требовательной особенностью ZKS конструкции является то, что даже не требуется раскрывать верхнюю границу . Тесно связанное понятие элементарных баз данных нулевого разглашения (ZK-EDB) также описывается в [8]. Грубо говоря, EDB представляет собой список пар ключ-значение, а ZK-EDB позволяет пользователю подтверждать, что данное значение связано с данным ключом в отношении короткого обязательства.

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

Причины использования. Множество литературы по ZKSs не рассматривает применения ZKSs [9][13] [30] [10] [31]. В применениях ZKSs (и ZK-EDBs), предложенных в [8] , размер множества (или БД) не является критическим для требующейся безопасности или конфиденциальности применения. Применения даны для улучшения конфиденциальности и контроля доступа в случае, когда записи EDB (элементарной базы данных) содержат важную информацию о людях, например, медицинские записи. В таких случаях, раскрытие ограниченного числа записей в базе данных очевидно, что раскрытие числа записей в базе данных не скажется на конфиденциальности человек, чья информация содержится в базе данных.

Другое использования ZKSs и ZK-EDBs применимо для создания обязательств для баз данных [32]. В этом применении владелец базы данных создает обязательство для базы данных и затем доказывает для каждого запроса, что ответ согласуется с обязательством. Для многих применений содержание обязуемой базы данных должно быть скрыто, но размер может быть раскрыт. Такой пример приводит Buldas и др. [33]. Здесь, ZK-EDBs использованы, чтобы увеличить ответственность центра сертификации для предотвращения от выдачи несогласующихся ответов на запросы о действительности сертификата. Очевидно, сокрытие числа сертификатов не требуется. Следовательно, слабый тип ZKS примитива не прячет размер множества, что достаточно для наиболее практичных применений ZKS. Мы называем ZKS, которая может выдать информацию об размере множества, почти ZKS. Аналогично, почти ZK-EDB – это ZK-EDB, которая может раскрыть информацию об числе записей в ней.

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

SetupZKS выдает SetupZKS . – является верхней границей размера множества, которое должно быть обязано.

CommitZKS() требует . Определим . Выдает Commit() . Пусть будет случайным полиномом степени , выбранным в PolyCommitPed.

QueryZKS() позволяет пользователю создавать доказательство, которое или , или . Вычисляет CreateWitness() .

  1. Если , выдает .
  2. Если , создает и доказательство ZK об разглашении и в . Пусть . Выдает .

VerifyZKS() принимает как .

  1. Если , то . Выдает 1, если VerifyEval .
  2. Если , то . Принимает как .Если и доказательство ZK об разглашении является правильным, выдает 1. Выдает 0, если не проходит проверка.
Алг. 2. Схема почти ZKS, основанная на PolyCommitPed.

Конструкция «Почти» ZKS.

Эта конструкция (Алг. 2) будет использовать PolyCommitPed и позволит нам создавать обязательсво для такое, что . Основная идея заключается в создании обязательства для полинома такого, что для , и для . Наша конструкция полагается на ZK доказательство, которое подтверждает без раскрытия для сохранения конфиденциальности для запросов, когда . Хотя также возможна конструкция, основанная на PolyCommitDL, мы выбрали PolyCommitPed, так как требуемое ZK доказательство проще в это случае. Для удобства мы опишем наши протоколы, предполагая, что ZK доказательство является неинтерактивным, однако, интерактивное ZK доказательство может быть также использовано.

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

Конструкция «Почти» ZK-EDB

Эта конструкция (Алг. 3) использует конструкцию почти ZKS и PolyCommitDL. Пусть, будет списком парк ключ-значение, которые будут определять базу данных ( и являются упорядоченными списками одинаковой длинны такие, что значение соответствует ключу ). Значения могут повторяться, но ключи должны быть уникальными. Мы запишем чтобы обозначить значение, связанное с ключом (если , то ). Идея, лежащая в основе нашей конструкции, заключается в том, чтобы создать обязательства для ключей, используя почти ZKS, и также обязательство для такое, что , используя PolyCommitDL, поскольку этого достаточно для безопасности и это более эффективно. Причина использования почти ZKS заключается в том, что ответы на запросы при не раскрывают никакой дополнительной информации.

SetupEDB () запускает SetupZKS() и выдает .

CommitEDB () устанавливает CommitZKS . Затем интерполирует (или меньше) точек и одну или более случайных точек , чтобы получить полином гарантированно степени . Устанавливает Commit и выдает .

QueryEDB () принимает как .

  1. Если , вычисляет QueryZKS чтобы показать, что и CreateWitness() , чтобы показать, что . Выдает .
  2. Если , мы показываем, что , устанавливаем QueryZKS . Выдает .

VerifyEDB () принимает как и как .

  1. Если , то , выдает , если VerifyZKS и VerifyEval .
  2. Если , то , выдает 1, если VerifyZKS .
Алг. 3. Почти ZK-EDB схема построена с использованием нашей почти ZKS конструкции (Алг. 2) и PolyCommitDL.

Эффективность наших почти ZKS и ZK-EDBs. Размер обязательства является единичным элементом группы для почти ZKS и двумя элементами для почти ZKS-EDB. Доказательство того, что , состоит из двух элементов, в то время как доказательство того, что , состоит из около пяти элементов группы ( при реализации ZK доказательств с использованием стандартного трехшагового ZK протокола, сделанного неинтерактивным с эвристикой Фиата-Шамира). Размер доказательства для нашей почти ZK-EDB конструкции составляет три и около пяти элементов группы (соответственно).

ZK-EDB в литературе с самыми короткими доказательствами основана на конструкции Libert и Yung [10]. Асимптотически, доказательство (не) принадлежности составляет битов, где – параметр безопасности, а – размер параметров системы. Для параметров, приведенных в [10] , размер доказательства составляет 80-200 элементов группы. Вычисление их схемы и нашей практически эквивалентно. Следовательно, использование почти ZK-EDBs вместо ZK-EDBs уменьшает стоимость связи в 16 раз.

Полномочия и выборочное раскрытие подписанных данных

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

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

Поскольку обе PolyCommit схемы сокрыты и связаны и позволяют создавать обязательства для списка сообщений, они могут быть использованы в общей конструкции Steinfeld и др. Вместе с обязательством Трент должны также подписать так, что Боб будет знать только индексы , соответствующие действительным подсообщениям. Новая схема является почти эффективной в плане коммуникации, как и особая схема в [11], которая имеет наименьшую стоимость связи. Последняя, однако, зависит от особых свойств схемы подписи RSA и является безопасной в модели случайного оракула. Использование схемы полиномиального обязательства дает эффективную общую конструкцию. Следовательно, эффективная стандартная модель CES съем является возможной благодаря комбинированию любой из PolyCommit схем с безопасностью схем подписи в стандартной модели.

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

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

Открытые проблемы

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

  1. Какие другие протоколы PolyCommit может улучшить? (Например, может ли PolyCommit уменьшить стоимость связи асинхронных VSS протоколов или проверяемых перемешиваний?)
  2. Мы сфокусировались на стоимости связи, но наши конструкции требуют нетривиальных вычислений. Возможно ли уменьшить также стоимость вычислений?

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

Мы благодарим анонимных обозревателей за многочисленные полезные комментарии и благодарим Benoit Libert за то, что отправил нам черновик [10]. Мы крайне признательны финансовой поддержке NSERC, MITACS и программе David Ceriton Graduate Scholarship.

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

  1. Max Planck Institute for Software Systems (MPI-SWS)
  2. Certicom Research
  3. University of Waterloo

Примечание

  1. Заметим, что мы ограничили до , так как оценки могут быть найдены для полиномов с более высокими степенями за PPT, используя численные теоретические методы (например для , для любого ). На практике .

Литература

  1. 1,0 1,1 A. Kate, G. Zaverucha, and I. Goldberg. Polynomial commitments. Technical report, 2010. CACR 2010-10, Centre for Applied Cryptographic Research, University of Waterloo.
  2. 2,0 2,1 2,2 2,3 T. P. Pedersen. Non-Interactive and Information-Theoretic Secure Verifable Secret Sharing. In Proceedings of CRYPTO'91, pages 129-140. Springer, 1991.
  3. I. Damgard. Commitment schemes and zero-knowledge protocols. In Lectures on Data Security, pages 63-86. Springer, 1999.
  4. 4,0 4,1 4,2 D. Boneh and X. Boyen. Short Signatures Without Random Oracles. In Proceedings of EUROCRYPT'04, pages 56-73. Springer, 2004.
  5. 5,0 5,1 5,2 V. Goyal. Reducing Trust in the PKG in Identity Based Cryptosystems. In Advances in Cryptology|CRYPTO'07, pages 430-447, 2007.
  6. D. Boneh, C. Gentry, and B.Waters. Collusion resistant broadcast encryption with short ciphertexts and private keys. In Proceedings of CRYPTO'05, pages 258-275. Springer, 2005.
  7. 7,0 7,1 7,2 P. Feldman. A Practical Scheme for Non-interactive Veri_able Secret Sharing. In Proceedings of FOCS'87, pages 427-437, 1987.
  8. 8,0 8,1 8,2 8,3 S. Micali, M. Rabin, and J. Kilian. Zero-knowledge sets. In Proceedings of FOCS'03, pages 80-91. IEEE, 2003.
  9. 9,0 9,1 9,2 9,3 9,4 D. Catalano, D. Fiore, and M. Messina. Zero-knowledge sets with short proofs. In Proceedings of EUROCRYPT'08, pages 433-450. Springer, 2008.
  10. 10,0 10,1 10,2 10,3 10,4 10,5 10,6 10,7 B. Libert and M. Yung. Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs. In TCC'10, pages 499-517, 2010.
  11. 11,0 11,1 11,2 R. Steinfeld, L. Bull, and Y. Zheng. Content extraction signatures. In Proceedings of ICISC'01, pages 285-304. Springer, 2002.
  12. 12,0 12,1 A. Menezes, P. Van Oorschot, and S. Vanstone. Handbook of Applied Cryptography. CRC Press, 1st edition, 1997.
  13. 13,0 13,1 M. Chase, A. Healy, A. Lysyanskaya, T. Malkin, and L. Reyzin. Mercurial commitments with applications to zero-knowledge sets. In Proceedings of EUROCRYPT'05, pages 422-439. Springer, 2005.
  14. J.C. Benaloh and M. de Mare. One-way accumulators: A decentralized alternative to digital signatures (extended abstract). In Proceedings of EUROCRYPT'93, pages 274-285. Springer, 1993.
  15. J. Camenisch and A. Lysyanskaya. Dynamic accumulators and application to effcient revocation of anonymous credentials. In Proceedings of CRYPTO'02, pages 61-76. Springer, 2002.
  16. 16,0 16,1 M. H. Au, Q. Wu, W. Susilo, and Y. Mu. Compact E-Cash from Bounded Accumulator. In Proceedings of CT-RSA'07, pages 178-195, 2007.
  17. 17,0 17,1 L. Nguyen. Accumulators from bilinear pairings and applications. In Proceedings of CT-RSA, pages 275-292, 2005.
  18. 18,0 18,1 M.H. Au, W. Susilo, and Y. Mu. Practical anonymous divisible e-cash from bounded accumulators. In Proceedings of FC'08, pages 287-301, 2008.
  19. 19,0 19,1 S. Mitsunari, R. Sakai, and M. Kasahara. A New Traitor Tracing. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E85-A(2):481-484, 2002.
  20. 20,0 20,1 D. Boneh and X. Boyen. Effcient Selective-ID Secure Identity-Based Encryption Without Random Oracles. In Proceedings of EUROCRYPT'04, pages 223-238, 2004.
  21. J.H. Cheon. Security analysis of the strong Diffe-Hellman problem. In Proceedings of EUROCRYPT'06, pages 1-13. Springer, 2006.
  22. D. Boneh, X. Boyen, and E.J. Goh. Hierarchical identity based encryption with constant size ciphertext. In Eurocrypt, volume 3494, pages 440-456. Springer, 2005.
  23. F. Guo, Y. Mu, and Z. Chen. Identity-Based Encryption: How to Decrypt Multiple Ciphertexts Using a Single Decryption Key. In Proceedings of Pairing'07, pages 392-406. Springer, 2007.
  24. A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. Proactive Secret Sharing Or: How to Cope With Perpetual Leakage. In Proceedings of CRYPTO'95, pages 339-352, 1995.
  25. R. Gennaro, M.O. Rabin, and T. Rabin. Simplifed VSS and Fast-Track Multiparty Computations with Applications to Threshold Cryptography. In Proceedings of PODC'98, pages 101-111. ACM Press, 1998.
  26. N. Pippenger. On the evaluation of powers and related problems. In IEEE SFCS(FOCS)'76, pages 258-263, 1976.
  27. A. Shamir. How to Share a Secret. Commun. ACM, 22(11):612-613, 1979.
  28. G.R. Blakley. Safeguarding cryptographic keys. In Proceedings of the National Computer Conference, pages 313-317, 1979.
  29. B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifable Secret Sharing and Achieving Simultaneity in the Presence of Faults (Extended Abstract). In Proceedings of FOCS'85, pages 383-395, 1985.
  30. R. Gennaro and S. Micali. Independent zero-knowledge sets. In Proceedings of ICALP'06, pages 34-45. Springer, 2006.
  31. M. Prabhakaran and R. Xue. Statistically Hiding Sets. In Proceedings of CT-RSA, pages 100-116. Springer, 2009.
  32. R. Ostrovsky, C. Racko_, and A. Smith. E_cient Consistency Proofs for Generalized Queries on a Committed Database. In Proceedings of ICALP'04, pages 1041-1053, 2004.
  33. A. Buldas, P. Laud, and H. Lipmaa. Eliminating Counterevidence with Applications to Accountable Certifcate Management. Journal of Computer Security,10(3):273-296, 2002.
  34. 34,0 34,1 I. Damgard and N. Triandopoulos. Supporting non-membership proofs with bilinear-map accumulators. 2008. Cryptology ePrint Archive: Report 2008/538.
  35. 35,0 35,1 J. Camenisch and M. Stadler. Proof systems for general statements about discrete logarithms. Technical report, 1997. 260, Dept. of Computer Science, ETH Zurich.