Оптимальная верификация операций над динамическими множествами

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:04, 20 декабря 2015.
Optimal Verification of Operations on Dynamic Sets
Optimal Verification of Operations on Dynamic Sets.png
Авторы Charalampos Papamanthou[@: 1],
Roberto Tamassia[@: 2] and
Nikos Triandopoulos[@: 3]
Опубликован 2011 г.
Перевели Denis Yakunchikov
Год перевода 2015 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Мы изучаем составление протоколов для верификации операций на рядах, так называемую проблему криптографической проверки правильности операций над множествами из внешних источников, произведенных не доверенным сервером над динамическимb множествами, которые являются частью (и обновляются им) доверенного источника. Мы представляем новую информация о структурах, которые позволяют любому объекту публично верифицировать доказательство правильности примитивного набора операций, таких как пересечение, объединение, подмножество и разностью. Наши протоколы основаны на расширении свойств безопасности сумматоров биленейного отображения и на примитивах, которые называются суммирующие деревья. Протоколы достигают оптимальной верификации и сложности доказательства (то есть, только пропорциональные размер параметров запроса и ответ), также как и оптимальной сложности обновления (то есть, константа), при этом не привлекая никакого дополнительного пространства. Доказательство конструкции также эффективно, так как добавляет логарифмическую нагрузку к вычислению ответа на запрос операций множеств. Существующие схемы влекут за собой высокие коммуникации, которые включают в себя эффективную проверку поиска по ключевым словам и запросы к базам данных. Безопасность нащего протокола основана на биленейном q-сильном продположении Диффи — Хеллмана.

Введение

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

В этой статье мы изучаем верификацию операций внешних источников над обычными рядами и рассматриваем следующую проблему. Если предположить, что динамическое множество из m множеств удаленно хранится на не доверенном сервере, и мы хотим публично верифицировать операции над этими множествами, такими, как пересечение, объединение или разность. Например, для пересечения запросов из t множеств с индексами мы хотим создать методы, которые позволяют каждому клиенту криптографически проверить правильность полученного ответа . Более того, мы хотим, чтобы верификация любой операции над множествами была чувствительна, что означает, что результирующая сложность зависит лишь от (описания и результата) операции, но не от размеров данных множеств. То есть, если - размер ответа, то тогда мы хотим, чтобы стоимость верификации была пропорциональна и независима от или  ; отметим, что на деле она должна быть как минимум пропорциональна , чтобы верифицировать любой такой ответ на запрос. Применение включает в себя поиск по ключевым словам и запросы к базам данных, которые сокращаются до операций над множествами.

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

Желая получить одновременно публично верифицируемые и динамические решения, мы изучаем верификацию операций над множествами посредством модели подлинных структур данных (ADS). Типичный вид этой модели, обычно называемый трехсторонней моделью [6] , включает в себя протоколы, выполняемые тремя действующими лицами. Доверенная сторона, называемая источником, обладает структурой данных (в нашем случае, множество), копии которой, вместе в какой-либо криптографической информацией, находятся на одной или более не доверенной стороне, называемой серверами. Соответственно, клиенты делают структурные запросы к серверам и могут подтвердить правильность полученных ответов, основываясь лишь на знании публичной информации, которая включает в себя публичный ключ и дайджест, созданный источником (например, хеш дерева Меркла). Обновления данных производятся источником и соответственно распространяются серверами. Виды этой модели включают в себя: (i) двусторонний вариант (например, [7] ), в котором на источнике хранится только небольшая структура (то есть, только дайджест) и источник выполняет и обновления/запросы, и верификацию - эта модель сопоставима протоколу проверяемых вычислений; (ii) - модель проверки памяти [8] , где чтение/запись операций в массив ячеек памяти верифицируется - однако, отсутствие понятия доказательства вычислений в проверке памяти (сервер представляется лишь как устройство хранения), так же как и функция публичной проверки подлинности структур данных, делают эти две модели абсолютно различными.

Достижение верификации, чувствительной к операциям. В этой работе мы разрабатываем структуры данных с проверкой подлинности для верификации операций над множествами в операционно-чувствительном смысле, когда сложность подтверждения и верификации зависит только от описания и результата операции и не зависит от размера рассматриваемых множеств. Это свойство идентично свойству супер-эффективной верификации, которая изучалась в сертификации алгоритмов [9] и сертификации структур данных [10] [11], которое достигается так же, как и протокол проверяемых вычислений [1] [2] [3], где ответ может быть верифицирован со сложностью, ассимптотически меньше, чем сложность создания. Вопрос о том, достижимо ли вышеупомянутое оптимальное свойство для операций над множествами (при линейной памяти), стал главной проблемой в [12]. Мы решаем эту проблему с положительным результатом.

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

Мы достигаем оптимальной верификации за счет отклонения от указанных выше подходов следующим образом. Сначала мы уменьшаем проблему верификации операций над рядами до проблемы верификации законности некоторых более примитивных отношений на множествах, так называемых, принадлежностей множеств и непересекающихся множеств. Далее для каждого примитивного отношения мы используем соответствующий криптографический примитив, чтобы оптимально верифицировать его подлинность. В частности, мы используем аккумулятор билинейного отображения, чтобы оптимально верифицировать составляющую подмножества (Леммы 1 и 4), при помощи [13] . Далее мы используем расширенный алгоритм Евклида для полиномов (Лемма 5) в комбинации с доказательствами содержания подмножеств, чтобы получить оптимальный тест верификации для непересекающихся множеств. Суть нашего способа в том, что непересекающиеся множества могут быть представлены взаимно неделимыми многочленами, и при этом существуют другие полиномы, такие, что попарная их сумма равно единице - этот сет мы будем использовать в доказательстве. Передача и обработка этих полиномов непомерно огромна по объему и по времени и не приводит к верификации, чувствительной к операциям. Билинейные свойства, тем не менее, позволяют нам сжать их коэффициенты в экспоненту и использовать их, чтобы вычислять внутренние результаты. Вот почему более простой концептуально аккумулятор RSA [14] даст математическое решение, а аккумулятор билинейного отображения [15] необходим для достижения желаемой сложности

Мы формально описываем наши протоколы, используя структурную схему аутентификации данных или ADS схему (Определение 1). Схема ADS состоит из алгоритмов , что означает: (i) генерирование ключа системы; (ii) при получении простой структуры данных D, setup инициализирует структуру аутентифицированных данных auth(D); (iii) имея доступ к секретному ключу, update вычисляет дайджест auth(D); (iv) не имея секретного ключа, refresh обновляет auth(D); (v) запрос вычисляет криптографические проверки для ответов для структур запросов q; (vi) процесс верификации проверки и ответа и получение либо подтверждение, либо отказа. Отметим, что ни query, ни verify не имеют доступа к секретному ключу, таким образом, обеспечиваются моделирование вычисления извне и публичная верификация. ADS схема должна удовлетворять определенной корректности и свойствами защиты (Определения 2 и 3). Отметим, что протоколы двусторонней и трехсторонней моделей могут быть реализованы с помощью схемы ADS.

Наш основной результат, Теорема 1, представляет первую ADS схему, которая достигает оптимальной верификации операций над множествами: пересечения, объединения, подмножества и разности множеств, а также оптимальных обновлений на основном наборе множеств. При помощи билинейного расширения q-сильного предположения Диффи — Хеллмана доказано, что наша схема является безопасной [16] .

Таблица 1. Ассимптотический доступ и групповые сложности различных схем ADS для запросов с пересечением на множествах с в наборе из m множеств с размером ответа . Здесь M - сумма размеров всех множеств и - константа. Также, все размеры пересеченных или обновленных множеств равны означает размеры проверки, и "CR" означает "сопротивление столкновению".

setup update, refresh query verify, предположение
[12][17] Generic CR
[18] Strong RSA
[19] Discrete Log
наша работа Bilinear q-Strong DH

Модель сложности. Чтобы явно измерить сложность различных алгоритмов в отношении числа примитивных криптографических операций, не считая зависимость параметра безопасности, мы приняли модель сложности, которая используется при проверке памяти [8][20], которая неявно использовалась в литературе по ADS. Сложность доступа алгоритма определяется числом обращений к памяти, осуществляемых во время его исполнения к аутентифицированной структуре данных, которая хранится в виде индексированной памяти из n элементов. Например, дерево Меркла [21] имеет сложность обновления доступа , так как алгоритм обновления должен прочесть и записать ячеек памяти аутентифицированной структуры данных, где одна ячейка хранит ровно одно хеш-значение. Групповая сложность набора данных (например, доказательство или групповая сложность ADS) определяется, как число элементарных объектов данных (например, хеш-значения или элементы в ), из которых состоит этот набор. Отметим, что, хотя доступ и групповая сложность соответственно зависят от сложности по времени и емкости, предыдущее в принципе меньше последнего. Это происходит потому, что сложность по времени и емкости включает в себя число бит и и всегда существуют функции параметра безопасности, которые, в свою очередь, всегда равны . Следовательно, сложность по времени и емкости всегда равна , в то время, как сложность доступа и групповая сложность могут быть равны . Наконец, каждый раз, когда это ясно понятно из контекста, мы пренебрегаем понятиями "доступ" и "группа".

Связанные работы. Подавляющее большинство аутентифицированных структур данных включает в себя использование криптографического хеширования [22][8][23][24][12][25][26] или другие примитивы [27][28][13], чтобы иерархически проводить вычислять один или более дайджестов над внешними данными. Большинство из этих схем включают в себя стоимость верификации, которая пропорциональна времени, затраченному на создание ответа на запрос, поэтому они не чувствительны к операциям. и чувствительные к операциям решения для верификации различных (например, поиск диапазона) запросов представлены в [22][10].

Несмотря на тот факт, что проблемы приватности для операций над множествами широко изучались в криптографической литературе (например, [29][30]), существующие работы по измерению целостности операций над множествами приводятся в основном в литературе по базам данных. В [12] рассматривается важность создания схемы, чувствительной к операциям. В [18], возможно, самой близкой к нашей работе, пересечение множеств, объединение и разность аутентифицируются с линейными затратами. Аналогичные оценки представлены в работе [17]. В [19] используется другой подход: чтобы достичь чувствительности к операциям, необходимы дорогая предварительная подготовка и экспоненциальная емкость (ответы на все возможные запросы подписаны). Наконец, связанные с нашей работой доказательства, оба для RSA[31] и аккумуляторов билинейных отображений[32][33]. Сравнение нашей работы с существующими схемами представлено в Таблице 1.

Подготовка

Обозначим параметр безопасности и незначительную функцию.

Аккумулятор билинейных отображений. Пусть - циклическая мультипликативная группа с простым порядком , порожденная элементом . Пусть также - циклическая мультипликативная группа того же порядка , что существует пара со следующими свойствами: (i) Билинейность: для всех и ; (ii) Невырожденность: ; (iii) Исчислимость: Для всех эффективно исчислимо. Мы называем кортежем парных билинейных параметров, полученных из вероятностного полиномиального алгоритма, который принимает на вход .

При этом аккумулятор билинейных отображений [15] является эффективным способом предоставления коротких доказательств членства элементов, которые принадлежат множеству. Пусть произвольно выбранное значение, которое является потайным местом в схеме. Примитивный аккумулятор накапливает элементы в , выводя значение, которое является элементом в . Для множества элементов в накопленное значение определяется как:

[34]

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

(1)

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

TemplateDifinitionIcon.svg Определение «Предположение 1 (Билинейное q-сильное предположение Диффи-Хеллмана)»
Пусть - параметр безопасности и - кортеж билинейных парных параметров. Взяв элементы , для некоторых , выбранных случайно из , где , никакой вероятностный алгоритм с полиномиальным временем не может произвести пару , за исключением незначительной вероятности .

Далее мы доказываем безопасность подмножеств свидетелей, обобщая доказательство из [15] . Подмножество свидетелей также рассматривается (независимо от нашей работы, но без доказательства) в [35].

TemplateTheoremIcon.svg Теорема Лемма 1(Принадлежность подмножеств)
Пусть - параметр безопасности и - кортеж билинейных парных параметров. Взяв элементы , для некоторых , выбранных случайно из и множество элементов в при , предполагается, что существует вероятностный алгоритм с полиномиальным временем, который находит и W, такие, что и . Тогда существует вероятностный алгоритм с полиномиальным временем, который опровергает билинейное q-сильное предположение Диффи-Хеллмана.
Доказательство
Предположим, что существует вероятностный алгоритм с полиномиальным временем, который вычисляет множество , и поддельный свидетель W. Пусть и для некоторых . Это означает, что

.

Отметим, что не делит . Следовательно, существует полиномиальное (вычисляемое за полиномиальное время) степени и константа , такое, что . Таким образом, имеем

.

Таким образом, этот алгоритм может опровергнуть билинейное q-сильное предположение Диффи-Хеллмана.


Инструменты для полиномиального вычисления. Наши решения используют (по модулю ) полиномиальные вычисления. Далее мы представляем два результата, которые широко используются в нашей технике, способствующей достижению желаемой сложности. Первый результат полиномиальной интерполяции получен при помощи алгоритма FFT [36] , который вычисляет DFN в конечном поле (например, ) для произвольного и представляющий операций над полем. Отметим, что -ый корень объединения не обязательно должен существовать в , чтобы данный алгоритм работал.

TemplateTheoremIcon.svg Теорема Лемма 2(Полиномиальная интерполяция с FFT[36])
Пусть - полином степени . Коэффициенты полинома могут быть сравнены со сложностью при .
Доказательство
Без доказательства.


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

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

Алгоритм : Алгоритм берет случайное . Если , тогда алгоритм принимает, в противном случае - отвергает.

TemplateTheoremIcon.svg Теорема Лемма 3(Верификация полиномиальных коэффициентов)
Пусть и . Алгоритм имеет сложность . Также, если , тогда - коэффициенты полинома с вероятностью .
Доказательство
Без доказательства.


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

TemplateDifinitionIcon.svg Определение «Определение 1 (Схема ADS)»
Пусть D - любая структура данных, которая поддерживает запросы q и обновления u. Пусть auth(D) обозначает полученную структуру аутентифицированных данных, и d - дайджест, то есть, описание D постоянного размера. Схема ADS состоит из следующих шести вероятностных алгоритмов с полиномиальным временем:
  1.  : на вход подается параметр k, на выходе получаем секретный ключ sk и публичный ключ pk;
  2.  : на вход подается (пустая) структура данных и секретный и публичный ключи, далее вычисляется структура аутентифицированных данных и ее дайджест  ;
  3.  : на вход подается обновление u для структуры данных , структура аутентифицированных данных , дайджест и секретный и публичный ключи, на выходе получаем обновленную структуру аутентифицированных данных , обновленный дайджест и некоторую информацию upd;
  4.  : на вход подается обновление u для структуры данных , структура аутентифицированных данных , дайджест , информация upd (из update) и публичный ключ, на выходе получаем обновленную структуру данных , обновленную структуру аутентифицированных данных и обновленный дайджест  ;
  5.  : на вход подается запрос q над структурой данных , структура аутентифицированных данных и публичный ключ, на выходе получаем ответ на запрос и проверку ;
  6.  : на вход подается запрос q, ответ , проверка , дайджест и публичный ключ, на выходе получаем accept или reject.

Пусть - алгоритм, который решает, является ли правильным ответом на запрос q для структуры данных . Есть два свойства, которым должна удовлетворять схема ADS, это правильность и безопасность.

TemplateDifinitionIcon.svg Определение «Определение 2 (Правильность)»
Пусть - схема ADS . Мы говорим, что схема ADS правильна, если , полученных из алгоритма genkey, , полученных из одного вызова setup и полиномиальным количеством вызовов refresh, где , для всех запросов q и для всех , полученных из , с небольшой вероятностью каждый раз, когда алгоритм возвращает accept, алгоритм возвращает то же самое.
TemplateDifinitionIcon.svg Определение «Определение 3 (Безопасность)»
Пусть - схема ADS , k - параметр безопасности, - незначительная функция и . Пусть также Adv - вероятностный полиномиальный противник, который имеет только pk. Противник имеет неограниченный доступ ко всем алгоритмам , за исключением setup и update. Противник выбирает начальное состояние структуры данных и вычисляет с помощью доступа оракула к алгоритму setup. Далее, для Adv выполняет обновление для структуры данных и вычисляет с помощью доступа оракула к алгоритму update. Наконец, противник выбирает индекс и вычисляет запрос q, ответ и проверку . Мы говорим, что схема ADS безопасна, если , полученных из алгоритма genkey, и для любого вероятностного полиномиального противника Adv справедливо:

(2)

Построение и алгоритмы

В этом разделе мы представляем схему ADS для верификации операций над множествами. Лежащая в основе структура данных, для которой мы разрабатываем схему ADS, называется набором множеств и может быть представлена, как обобщение структуры данных с инвертированным индексом [37].

Набор множеств. Набор множеств - структура данных, состоящая из m множеств , каждое из которых содержит элементы из . Мы предполагаем, что - множество неотрицательных цифр в интервале , где p - k-битное простое число, m - число множеств в нашем наборе размера , k - параметр безопасности, и s - потайное место в схеме (см. алгоритм genkey). Множество не содержит одинаковых элементов, хотя элемент может встретиться несколько раз. Каждое множество сортируется и необходимое суммарное пространство равно , где M - сумма размеров множеств.

Мы можем рассмотреть набор множеств, как инвертированные индексы. С этой точки зрения, элементы - это указатели на документы, и каждый набор соответствует элементу в словаре, содержащем указатели на документы, где встречается элемент . В этом случае, m - это число проиндексированных элементов, которое обычно равно сотням тысяч, а M, являющееся числом проиндексированных документов, равно миллиардам. Таким образом, общие термины "элементы" и "множества" могут быть заменены более конкретными "документы" и "элементы".

Операции, которые можно выполнять над наборами множеств, состоят из обновлений и запросов. Обновление - это либо добавление элемента в множество, либо удаление его из множества. Обновление множества размера n требует времени. Для простоты мы предполагаем, что количество множеств m не изменяется при обновлении. Запрос - это одна из стандартных операций над множествами: (i) Пересечение: при данных возвращаемое значение  ; (ii) Объединение: при данных возвращаемое значение  ; (iii) Подмножество: при данных i и j возвращаемое значение положительное, если , и отрицательное, если наоборот; (iv) Разность: при данных i и j возвращаемое значение . В остальной части статьи мы называем размер ответа на операцию запроса, то есть равна размеру I, U или D. Для операции подмножества .

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

Алгоритмы схемы

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

Алгоритм  : Выбираются билинейные парные параметры , и выбирается случайный элемент . Далее используется функция . Функция выдает битовое описание элементов , в соответствии с некоторым каноническим представлением . Наконец, алгоритм выводит и pk=\{h(\cdot),p,\mathbb{G},\mathcal{G},e,\mathit{g},g\} , где вектор g содержит значения:

где . Алгоритм имеет сложность .

Алгоритм  : Пусть - начальная структура данных, то есть представляет собой наборы . Структура аутентифицированных данных строится следующим образом. Сначала для каждого набора вычисляется его аккумулированное значение (см. Раздел 2). Далее алгоритм выбирает константу . Пусть T - дерево с уровнями и m листьями, пронумерованными 1,2,...,m, где m - число множеств нашего набора множеств структур данных. Так как T - дерево с постоянной высотой, степень каждого его внутреннего узла равна . Такое дерево мы называем аккумулированным, которое впервые появилось (в соответствии с различной криптографией) в [13]. Для каждого узла дерева алгоритм рекурсивно вычисляет дайджест для следующим образом. Если - лист, относящийся ко множеству , где , алгоритм задается  ; здесь возрастание значения до экспоненты при константе производится также индексом аккумуляции i множества . Если узел не лист, тогда

(3)

где обозначает множество потомков узла . Алгоритм выводит все множества как структуру данных , все аккумулированные значения для , дерево T и все дайджесты для всех как структуру аутентифицированных данных . Наконец, алгоритм задает , где r - корень T, то есть - дайджест структуры аутентифицированных данных (определенных так же, как дерево Меркла). Сложность доступа алгоритма - (для обратного обхода T и вычисления ), где . Групповая сложность также равна , так как алгоритм хранит один дайджест для узла T, T имеет узлов, и существует M элементов во множествах.

Алгоритм  : Рассмотрим обновление "вставить элемент во множество " (отметим, что такой же алгоритм использовался для удаления элементов). Пусть - лист T, принадлежащий множеству . Пусть - путь в T от узла до корня дерева, где . Алгоритм сначала задает . Далее алгоритм задает

для (4)

где - текущий дайджест , и - обновленный дайджест . Все эти только что вычисленные значения (то есть, новые дайджесты) сортируются алгоритмом. Далее алгоритм выводит новые дайджесты , вместе с путем в обновленному множеству к корню дерева, как часть информации в upd. Информация upd также включает в себя и . Алгоритм также задает , то есть обновленный дайджест корня T. Наконец, новая структура аутентифицированных данных вычисляется следующим образом: для входа алгоритма - текущей структуры аутентифицированных данных значения заменяются новыми значениями , и полученная структура данных включается в вывод алгоритма. Число операций пропорционально , хотя сложность алгоритма равна .

Алгоритм  : Рассмотрим обновление "вставить элемент во множество ". Пусть - лист T, принадлежащий множеству . Пусть - путь в T от узла до корня дерева. Используя информацию upd, алгоритм задает , то есть он обновляет дайджесты, которые относятся к обновленному пути. Наконец, он выводит обновленный набор множеств , обновленные дайджесты (вместе с теми, которые принадлежат к узлам, которые не обновлялись), как и (содержащиеся в upd), как . Алгоритм имеет сложность , так как число операций равно .

Подлинность значений аккумуляции

Мы уже описали структуру аутентифицированных данных , которую будет использовать наша схема ADS для верификации операций над множествами. В общем и целом, составляет множество из значений аккумуляций , одно для каждого множества , и множество из дайджестов , по одному для каждого внутреннего узла v дерева аккумуляции T. Наше доказательство и протоколы верификации для операций над множествами (описанные в Разделе 3.3) пользуются деревом аккумуляции , и, следовательно, требуется, чтобы можно было проверить подлинность каждого такого значения. Дерево T делает это с помощью коротких доказательств корректности для каждого значения , хранящихся в листе i дерева T, а дайджест </math> дайджестов - в корне дерева. Далее мы представляем детали, относящиеся к доказательству аутентифицированности .

Доказательство корректности значения аккумуляции - множество доказательств аккумуляции билинейного отображения (см. Раздел 2). В частности, устанавливается, как упорядоченная последовательность , где - пара дайджестов узла и доказательство, которое аутентифицирует , объект , на пути , определенное листом , в котором содержится значение аккумуляции math>~ acc(S_i) </math> и корень дерева T. определяется, как , где

(5)

Отметим, что - доказательство для подмножество из одного элемента, назовем, (вспомним ). Пара имеет групповую сложность и может быть построен при использовании полиномиальной интерполяции со сложностью из Леммы 2, и, так как имеет сложность . Так как состоит из таких пар, мы заключаем, что доказательство значения аккумуляции может быть построено со сложностью и имеет групповую сложность . Следующие алгоритмы и используются для формального определения конструкции и соответственно верификации таких доказательств корректности. Аналогичные методы описывались в [13].

Алгоритм  : Пусть - путь в дереве T от узла до корня T. Алгоритм вычисляет , принимая , где и - из уравнения (5) и Леммы 2. Наконец, алгоритм задает .

Алгоритм  : Пусть есть доказательство , где . Алгоритм выводит , если одно из следующих утверждений верно: (i)  ; или (ii) для некоторого  ; или (iii) . В противном случае, алгоритм выводит .

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

TemplateTheoremIcon.svg Теорема Лемма 4
Алгоритм имеет сложность и выводит доказательство групповой сложности . Более того, алгоритм имеет сложность доступа . Наконец, для любого доказательства, выбранного противником, , если , тогда с вероятностью .
Доказательство
Без доказательства.


Запросы и верификация

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

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

Запрос пересечения. Пусть . Мы выражаем корректность операции с помощью следующих двух условий:

Условие подмножества: (6) Условие завершенности: (7)

Условие законченности в выражении (7) обязательно, так как множество должно содержать все общие элементы. Для пересечения и для каждого множества , мы определяем полином степени

(8)

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

TemplateTheoremIcon.svg Теорема Лемма 5
Множество - пересечение множеств тогда и только тогда, когда существуют полиномы , такие, что , где - определены в равенстве (8). Более того, полиномы могут быть вычислены со сложностью .
Доказательство
Без доказательства.

Используя Леммы 2 и 5, мы составили рациональные доказательства для обоих условий из уравнение (6) и (7). Доказательства напрямую используются для определения алгоритмов query и verify нашей ADS схемы для запросов пересечения.

Доказательство условия подмножества. Для каждого множества вычисляется условие подмножества со сложностью из Леммы 2(Вспомним, что W_{I,j} </math> является доказательством того, что является подмножеством ). Таким образом, общая сложность для вычисления всех t доказательств равна , где .

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

Алгоритм (Пересечение): Запрос q состоит из t индексов , запрашивающих пересечение I, состоящее из . Пусть . Тогда и доказательство состоит из следующих частей.

  1. Коэффициенты полинома , который ассоциируется с пересечением . Они вычисляются со сложностью (Лемма 2) и имеют групповую сложность .
  2. Значения аккумуляции , которые ассоциируются со множествами и их доказательствами корректности . Они вычисляются с помощью алгоритма с общей сложностью и имеют общую групповую сложность (Лемма 4).
  3. Принадлежность множеству , которая ассоциируется со множествами и пересечением I. Она вычисляется со сложностью и имеет общую групповую сложность (Лемма 2).
  4. Доказательство завершенности ассоциируется с полиномами из Леммы 5. Они вычисляются со сложностью и имеют групповую сложность (Лемма 5).

Алгоритм (Пересечение): Подтверждение результата запроса пересечения включает в себя следующие шаги.

  1. Во-первых, алгоритм использует коэффициенты и ответ на вход алгоритма , чтобы подтвердить годность . Если certify выведет reject, алгоритм также выведет reject. Этот шаг имеет сложность (Лемма 3).
  2. Алгоритм использует доказательство , чтобы верифицировать корректность , запуская алгоритм . Если для некоторых j функция выведет reject, алгоритм также выведет reject. Этот шаг имеет сложность (Лемма 4).
  3. Далее алгоритм проверяет состояние подмножества:

(9)

Если для некоторых j "падает", алгоритм выводит reject. Этот шаг имеет сложность .

  1. Наконец, алгоритм проверяет условие завершенности:

(10)

Если приведенная выше проверка завершенности "падает", то алгоритм выводит reject. Или, если это соотношение выполняется, алгоритм выводит accept, то есть, он принимает как корректное пересечение. Этот шаг имеет сложность .

Отметим, что для выражения (10) , когда все доказательства подмножества равны , все доказательства завершенности равны и все множества значений аккумуляции вычислены честно, . Это необходимое условие для доказательства корректности нашей ADS схемы, как написано в Определении 2. Мы продолжаем описание алгоритмов query и verify для запроса объединения.

Запрос объединения. Пусть .Мы выражаем правильность операции объединения с помощью следующих двух условий:

Условие членства: (11) Условие надмножества: (12)

Условие надмножества в выражении (12) необходимо, так как множество U не должно исключать элементы множеств . Мы формально определяем алгоритмы query и verify нашей ADS схемы для запросов объединения.

Алгоритм (Объединение): Запрос q запрашивает объединение U из t множеств . Пусть . Тогда и доказательство состоит из следующий частей.

  1. Коэффициенты полинома ассоциируются с объединением .
  2. Значения аккумуляции , которые ассоциируются со множествами и их доказательствами корректности , получаются из .
  3. Доказательство членства (см. выражение (1)), которая доказывает, что принадлежит некоторому множеству и которая вычисляется с общей сложностью и имеет общую групповую сложность (Лемма 2) .
  4. Принадлежность подмножеству , которая ассоциируется со множествами и объединением U и доказывает, что U - надмножество . Вычисляется со сложностью и имеет групповую сложность (Лемма 3).

Алгоритм (Объединение): Подтверждение результата запроса объединения включает в себя следующие шаги.

  1. Во-первых, алгоритм использует коэффициенты и ответ на вход алгоритма , чтобы подтвердить годность .
  2. Алгоритм использует доказательство , чтобы верифицировать корректность , запуская алгоритм . Если для некоторых j функция выведет reject, алгоритм также выведет reject.
  3. Далее алгоритм проверяет, принадлежит ли каждый элемент объединения некоторому множеству (сложность ). Это происходит путем проверки, что выражение  ; в противном случае алгоритм выводит reject.
  4. Наконец, алгоритм проверяет, что все множества являются подмножествами объединения, проверяя следующие условия:

Если приведенная выше проверка "падает", то алгоритм выводит reject, в противном случае - accept, то есть U принимается за корректное объединение.

Запрос на подмножество и разность. Для запроса подмножества (положительного или отрицательного) мы используем свойство . Для запроса разности множеств мы используем свойство:

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

TemplateTheoremIcon.svg Теорема Теорема 1
Рассмотрим набор из множеств и пусть . Для операции запроса для множеств пусть - это сумма размеров множеств и - размер ответа. Тогда существует ADS схема для структуры данных набора множеств со следующими свойствами:# корректируется и становится безопасной в соответствии с Определениями 2 и 3 и билинейным q-сильным предположением Дифле-Хелмана; # Сложность алгоритма доступа (i) genkey -  ; (ii) setup -  ; (iii) update - - ввод информации upd групповой сложности  ; (iv) refresh -  ; # Для всех запросов q (пересечение/объединение/подмножество/разность), создающих доказательство с помощью алгоритма query имеет сложность доступа , алгоритм verify имеет сложность доступа , и доказательство имеет сложность  ; # Групповая сложность структуры аутентифицированных данных -
Доказательство
Без доказательства.


Безопасность, протоколы и применения

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

Набросок доказательства безопасности. Мы предоставляем некоторые ключевые элементы безопасности протоколов верификации, уделяя внимание запросами пересечения множеств. Доказательства безопасности других операций над множествами похожи. Пусть - набор множеств, структура данных состоит из множеств и пусть наша ADS схема . Пусть - параметр безопасности и пусть . Противнику доступен публичный ключ pk, , и неограниченный доступ ко всем алгоритмам , за исключением setup и update, к которым он имеет только доступ оракула. Противник изначально выводит структуру аутентифицированных данных и дайджест , через который оракул вызывает алгоритм setup. Далее противник выбирает полиномиальное число обновлений (например, вставка элемента в множество ) и выводит структуру данных , структуру аутентифицированных данных и дайджест , через который оракул вызывает update. Далее он выбирает множество индексов , все между 1 и m и выводит доказательство и ответ , который отвергается check как некорректный. Пусть ответ состоит из d элементов. Доказательство содержит (i) некоторые коэффициенты  ; (ii) некоторые значения аккумуляции с некоторыми доказательствами корректности  ; (iii) некоторые доказательства подмножеств с некоторыми доказательствами завершенности .

Предположим, что verify принимает. Тогда: (i) из Леммы 3 - коэффициенты полинома , за исключением незначительной вероятности; (ii) из Леммы 4 - значения - значения аккумуляции множеств , за исключением незначительной вероятности; (iii) из Леммы 1 - значения - подмножества доказательств для множества , то есть , за исключением незначительной вероятности; (iv) однако, не являются взаимно простыми , так как некорректно и не может содержать все элементы пересечения. Таким образом, полиномы (выражение 8) имеют хотя бы один общий коэффициент, скажем, и для некоторых полиномов (вычисляемых за полиномиальное время), для всех . При верификации выражения (10), получаем:

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

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

Протоколы. Как говорилось во введении, наша ADS схема может использоваться протоколом верификации в трехсторонней модели [6]. Здесь, доверенный объект, называемый источником, владеет набором множеств структур данных , но хочет передать ответ на запрос доверенным (который можно верифицировать) способом. Источник запускает genkey и setup выводят структуру аутентифицированных данных вместе с дайджестом . Источник далее подписывает дайджест и отсылает и их подписи некоторым не доверенным лицам, называемым серверами. На входе - запрос структуры данных query q (например, запрос пересечения), посланная клиентами, серверы используют и , чтобы вычислить подтверждения при помощи алгоритма query, и далее они возвращают клиентам и подпись с ответом на q. Клиенты могут верифицировать эти проверки при помощи алгоритма verify (так как у них есть доступ к подписи , они могут верифицировать, что подлинно). Когда структура данных обновляется, источник использует алгоритм update, чтобы создать новый дайджест , чтобы использовать его для следующей верификации, пока серверы обновляют структуру аутентифицированных данных с помощью refresh.

Добавим, что наша ADS схема может также быть использована для неинтерактивного протокола верификации в двусторонней модели [7] . В этом случае источник и клиент совпадают, то есть клиент производит и обновления, и запросы, и необходимо хранить только постоянное состояние, то есть дайджест структуры аутентифицированных данных. Когда клиент выполняет update, он получает верифицированную структуру аутентифицированных данных постоянного размера, которая используется для локального выполнения update и для вычисления нового локального состояния, то есть нового дайджеста. Неинтерактивный двусторонний протокол, который используется в ADS схеме для структуры данных D, сравним с последними протоколами для вычисления верификации [1][2][3] для функциональностей структуры данных D, например, вычисление пересечения, объединения и т.д. Из-за ограничений по размеру, мы откладываем детальное описание этих протоколов для полной версии нашей статьи.

Применения. Во-первых, наша схема может быть использована для верификации запросов по поиску по ключевым словам, реализованному с помощью структуры данных с инвертированными индексами [37] : каждый элемент словаря относится ко множеству из нашего набора множеств структур данных, которые содержат все документы в этом словаре. Обычный текстовый запрос для элементов и возвращает те документы, которые включены в оба множества, то есть это их пересечение. Более того, полученный аутентифицированный инвертированный индекс тоже может быть обновлен. Однако, иногда при поиске по ключевым словам (например, во входящих сообщения почты) желательно ввести "второе" измерение: Например, запрос может быть "вывести сообщения, которые содержат и и которые были получены во время между и ". Мы называем такой вариант датирующимся поиском по ключевым словам. Одним из решений для верификации таких запросов может быть введение меток времени в документы (например, в каждое сообщение) после того, как клиент проведет фильтрацию на локальном уровне и, используя нашу схему, верифицирует пересечение множеств, которые относятся к и . Однако, такой подход не чувствителен к операциям: Пересечение может быть больше, чем вывод множества после локальной фильтрации, что делает решение неэффективным. Чтобы преодолеть эту неэффективность, мы можем использовать структуру данных в виде сегментного дерева [38]. При верифицировании таким образом запросы при датирующемся поиске по словам производятся со сложностью , где r - общее число меток времени. Для этого способа необходимо построение бинарного дерева T из набора сообщений, посланных между конкретными метками времени, что означает, что каждый внутренний узел является объединением сообщений, хранящихся в его потомках. Наконец, наш метод может использоваться для верификации запросов equi-join для реляционных таблиц, которые сводятся к операциям пересечения множеств.

Заключение

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

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

Благодарности. Эта работы была поддержана Американским национальным научным фондом грантами CNS–1012060 и CNS–1012798, стипендией Канеллакиса, Центром геометрический вычислений Брауновского университета, RISCS центром Бостонского университета и NetApp. Авторы благодарят Майкла Т. Гудрича за полезные обсуждения. Взгляды этой статьи не обязательно отражают взгляды спонсоров.

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

  1. Brown University, Providence RI, USA
  2. RSA Laboratories, Cambridge MA, USA
  3. Boston University, Boston MA, USA

Литература

  1. 1,0 1,1 1,2 1,3 B. Applebaum, Y. Ishai, and E. Kushilevitz. From secrecy to soundness: Efficient verification via secure computation. In Int. Colloquium on Automata, Languages and Programming (ICALP), pp. 152–163, 2010.
  2. 2,0 2,1 2,2 2,3 K.-M. Chung, Y. Kalai, and S. Vadhan. Improved delegation of computation using fully homomorphic encryption. In Int. Cryptology Conference (CRYPTO), pp. 483–501, 2010.
  3. 3,0 3,1 3,2 3,3 R. Gennaro, C. Gentry, and B. Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In Int. Cryptology Conference (CRYPTO), pp. 465–482, 2010.
  4. K.-M. Chung, Y. Kalai, F.-H. Liu, and R. Raz. Memory delegation. In Int. Cryptology Conference (CRYPTO), 2011.
  5. S. Benabbas, R. Gennaro, and Y. Vahlis. Verifiable delegation of computation over large datasets. In Int. Cryptology Conference (CRYPTO), 2011.
  6. 6,0 6,1 6,2 R. Tamassia. Authenticated data structures. In European Symp. on Algorithms (ESA), pp. 2–5, 2003.
  7. 7,0 7,1 7,2 C. Papamanthou and R. Tamassia. Time and space efficient algorithms for two-party authenticated data structures. In Int. Conference on Information and Communications Security (ICICS), pp. 1–15, 2007.
  8. 8,0 8,1 8,2 M. Blum, W. S. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the correctness of memories. Algorithmica, 12(2/3):225–244, 1994.
  9. 9,0 9,1 D. Kratsch, R. M. McConnell, K. Mehlhorn, and J. P. Spinrad. Certifying algorithms for recognizing interval graphs and permutation graphs. In Symposium on Discrete Algorithms (SODA), pp. 158–167, 2003.
  10. 10,0 10,1 M. T. Goodrich, R. Tamassia, and N. Triandopoulos. Super-efficient verification of dynamic outsourced databases. In RSA, Cryptographers’ Track (CT-RSA), pp. 407–424, 2008.
  11. R. Tamassia and N. Triandopoulos. Certification and authentication of data structures. In Alberto Mendelzon Workshop on Foundations of Data Management, 2010.
  12. 12,0 12,1 12,2 12,3 C. Martel, G. Nuckolls, P. Devanbu, M. Gertz, A. Kwong, and S. G. Stubblebine. A general model for authenticated data structures. Algorithmica, 39(1):21–41, 2004.
  13. 13,0 13,1 13,2 13,3 C. Papamanthou, R. Tamassia, and N. Triandopoulos. Authenticated hash tables. In Int. Conference on Computer and Communications Security (CCS), pp. 437–448, 2008.
  14. M. Bellare and D. Micciancio. A new paradigm for collision-free hashing: Incrementality at reduced cost. In Advances in Cryptology (EUROCRYPT), pp. 163–192, 1997.
  15. 15,0 15,1 15,2 L. Nguyen. Accumulators from bilinear pairings and applications. In RSA, Cryptographers’ Track (CT-RSA), pp. 275-292, 2005.
  16. 16,0 16,1 D. Boneh and X. Boyen. Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptology, 21(2):149–177, 2008.
  17. 17,0 17,1 Y. Yang, D. Papadias, S. Papadopoulos, and P. Kalnis. Authenticated join processing in outsourced databases. In Int. Conf. on Management of Data (SIGMOD), pp. 5–18, 2009.
  18. 18,0 18,1 R. Morselli, S. Bhattacharjee, J. Katz, and P. J. Keleher. Trust-preserving set operations. In Int. Conference on Computer Communications (INFOCOM), 2004.
  19. 19,0 19,1 H. Pang and K.-L. Tan. Authenticating query results in edge computing. In Int. Conference on Data Engineering (ICDE), pp. 560–571, 2004.
  20. C. Dwork, M. Naor, G. N. Rothblum, and V. Vaikuntanathan. How efficient can memory checking be? In Theoretical Cryptography Conference (TCC), pp. 503–520, 2009.
  21. R. C. Merkle. A certified digital signature. In Int. Cryptology Conference (CRYPTO), pp. 218–238, 1989.
  22. 22,0 22,1 M. J. Atallah, Y. Cho, and A. Kundu. Efficient data authentication in an environment of untrusted third-party distributors. In Int. Conference on Data Engineering (ICDE), pp. 696– 704, 2008.
  23. M. T. Goodrich, R. Tamassia, and A. Schwerin. Implementation of an authenticated dictionary with skip lists and commutative hashing. In DARPA Information Survivability Conference and Exposition II (DISCEX II), pp. 68–82, 2001.
  24. M. T. Goodrich, R. Tamassia, and N. Triandopoulos. Efficient authenticated data structures for graph connectivity and geometric search problems. Algorithmica, 60(3):505–552, 2011.
  25. M. Naor and K. Nissim. Certificate revocation and certificate update. In USENIX Security Symposium, pp. 217–228, 1998.
  26. M. L. Yiu, Y. Lin and K. Mouratidis. Efficient verification of shortest path search via authenticated hints. In Int. Conference on Data Engineering (ICDE), pp. 237–248, 2010.
  27. M. T. Goodrich, R. Tamassia, and J. Hasic. An efficient dynamic and distributed cryptographic accumulator. In Information Security Conference (ISC), pp. 372–388, 2002.
  28. C. Papamanthou and R. Tamassia. Cryptography for efficiency: Authenticated data structures based on lattices and parallel online memory checking. Cryptology ePrint Archive, Report 2011/102, 2011. http://eprint.iacr.org/.
  29. D. Boneh and B. Waters. Conjunctive, subset, and range queries on encrypted data. In Theoretical Cryptography Conference (TCC), pp. 535–554, 2007.
  30. M. J. Freedman, K. Nissim, and B. Pinkas. Efficient private matching and set intersection. In Advances in Cryptology (EUROCRYPT), pp. 1–19, 2004.
  31. J. Li, N. Li, and R. Xue. Universal accumulators with efficient nonmembership proofs. In Applied Cryptography and Network Security (ACNS), pp. 253–269, 2007.
  32. M. H. Au, P. P. Tsang, W. Susilo, and Y. Mu. Dynamic universal accumulators for DDH groups and their application to attribute-based anonymous credential systems. In RSA, Cryptographers’ Track (CT-RSA), pp. 295–308, 2009.
  33. I. Damg°ard and N. Triandopoulos. Supporting non-membership proofs with bilinear-map accumulators. Cryptology ePrint Archive, Report 2008/538, 2008. http://eprint.iacr.org/.
  34. Y. Minsky, A. Trachtenberg, and R. Zippel. Set reconciliation with nearly optimal communication complexity. IEEE Transactions on Information Theory, 49(9):2213–2218, 2003.
  35. S. Canard and A. Gouget. Multiple denominations in e-cash with compact transaction data. In Financial Cryptography (FC), pp. 82–97, 2010.
  36. 36,0 36,1 F. P. Preparata and D. V. Sarwate. Computational complexity of Fourier transforms over finite fields. Mathematics of Computation, 31(139):pp. 740–751, 1977.
  37. 37,0 37,1 R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley Publishing Company, Reading, Mass., 1999.
  38. F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer- Verlag, New York, NY, 1985.
  39. C. Papamanthou, R. Tamassia, and N. Triandopoulos. Optimal authenticated data structures with multilinear forms. In Int. Conference on Pairing-Based Cryptography (PAIRING), pp. 246–264, 2010.