Многопоточный вычислительно-конфиденциальный поиск информации с постоянной скоростью связи

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 01:54, 24 декабря 2015.
Multi-query CPIR
Multi-query Computationally-Private Information Retrieval with Constant Communication Rate.PNG
Авторы Jens Groth[@: 1],
Aggelos Kiayias[@: 2],
and Helger Lipmaa[@: 3][@: 4]
Опубликован 2010 г.
Сайт Homepage of Jens Groth
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

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

Введение

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

Предпосылки

Конфиденциальный информационный поиск был представлен в [2]. Кушилевитц и Островский [3] показали, что возможно создать ВКИП-протoкол с сублинейными связями. Кашин, Микали и Стадлер [4] представили первый ВКИП-протокол для извлечения одного бита из базы данных, где сложность связи была полилогарифмична размеру базы данных. На сегодняшний день лучшим однопоточным ВКИП-протоколом был предложен Гентри, Рамзаном [5] и Лимпа [6] и он позволяет получать -битную запись из базы данных.

Возвращаясь к нашей проблеме, есть 3 тривиальных решения -поточного ВКИП. Первый вариант - это параллельное исполнение нескольких однопоточных ВКИПов. В случае повторения ВКИПов Гентри и Рамзана [5] мы получим связь , где - параметр безопасности, определяющий длину модуля RSA. Как мы увидим далее, это не является оптимальным решением.

Второй вариант - использовать однопоточный ВКИП-протокол для длдя получения одного -битного сегмента из -элементной базы данных. Как показывает наша нижняя граница, это решение дает асимптотически оптимальную связь при использовании ВКИПа Гентри и Рамзана, но, к сожалению, увеличивает вычислительную нагрузку на сервер до , что для многих значений и неполиномиальным относительно параметра безопасности.

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

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

Наш вклад

Мы разрабатываем вычислительно эффективный многопоточный ВКИП-проткол на двух сообщениях с битами связи, где -параметр безопасности, определяющий длину модуля RSA. Серверные вычисления определяются группами операций, где в обоих случаях постоянная в большая-достаточно мала. Конфиденциальность клиента основана на предположении о -неизвестности [4][5]. В нашей конструкции мы используем многопоточный вариант однопоточного ВКИПа Гентри и Рамзана [5], который работает с ограниченным набором параметров . Мы представляем редукцию, показывающую, что любой многопоточный ВКИП-протокол, работающий с фискированным набором параметров, можно использовать как основу для создания оптимального по связи ВКИП-проткоола для любого набора параметров.

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

Трудности и методы

Известные методы удовлетворяют оптимальным по связи ВКИП в кайних случаях, где число запросов очень мало или велико. Если сервер может переслать базу данных целиком пользователю, что даст сложность связи бит. Если мы можем использовать однопоточный ВКИП Гентри и Рамзана раз параллельно и получим сложность связи бит. Мы заинтересованы в нахождении эффективного по связи ВКИП-протокола для случая .когда лежит между экстремумами. Действительно, если , то скачивание базы данных целиком ценой бит будет субоптимальным и при простое повторение протокола Гентри и Рамзана будет иметь аддитивные затраты в бит, что сделает этот вариант субоптимальным выбором.

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

Чтобы устранить увеличение фактора до мы будем кодировать базу данных таким образом, что она может быть разделена на более мелкие фрагменты, которые будут обрабатываться ограниченными многопоточными ВКИП-протоколами. Одна из частей такого кодирования - разделение базы данных на блоки, к которым можно обратиться раздельно. С меньшими блоками нам нужны меньшие простые числа в ВКИПе Гентри и Рамзана для определения конкретной записи и это хорошо для сложности связи. Чтобы равномерно распределить запросы по блокам, мы предоставили пользователю возможность выбрать случайную перестановку базы данных. Чтобы сохранить сублинейную сложность связи, клиент сначала задает начальное значение для генератора псевдослучайных чисел на сервере, на основании результата которого можно сгенерировать полную перестановку.

Другую часть нашего кодирования лучше пояснить на примере. Допустим, у нас есть база данных с 4 однобитовыми записями, и пользователь хочет получить 2 записи. Мы можем закодировать базу данных в 6 записей по 2 бита для каждой возможной пары запросов: . Такое кодирование увеличит размер базы и записей в ней, но уменьшит число запросов клиента. Если система кодирования запросов простыми числами позволяет извлекать несколько бит за раз, это улучшит пропускную способность за счет сокращения числа запросов. Батч-коды [7] направлены на схожие проблемы, однако, как показано в секции по связанным работам, ни один из этих кодов не подходит для нашей схемы.

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

Содержание статьи

В Разделе 2 мы представим необходимые подготовительные сведения. В Разделе 3 мы доказываем нижнюю границу для сложности связи многопоточных ВКИП(даже когда конфиденциальность не требуется). В Разделе 4 мы строим базовый ограниченный многопоточный протокол ВКИП на основе работы Рамзана и Гентри [5]. В Разделе 5 мы разрабатываем новый многопоточный протокол для любых значений параметров.

Базовые сведения

ЗАМЕЧАНИЕ.

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

МНОГОПОТОЧНЫЙ ВКИП.

Рассмотрим базу данных с записями . Неформально, многопоточный ВКИП-протокол - это протокол, позволяющий извлечь различных записей из базы данных без разглашения, какие записи были извлечены. Формально, многопоточный ВКИП-протокол состоит из двух интерактивных машин Тьюринга с полиномиальным временем и , называемых соответственно клиент и сервер. Обе стороны получают на входе параметр безопасности в унарном виде и дополнительные параметры . Сервер получает на входе n элементов . Клиент получает на входе набо m различных индексов (отметим, что поскольку нас интересует минимальная связь при ограниченном m, мы можем предположить, что все m индексов различны). Клиент и сервер взаимодействуют, и в итоге клиент получает на выходе или спецсимвол ошибки . является многопоточным ВКИМ-протоколом если он удовлетворяет стандартной достоверности и свойствам конфидженциальности, определенным ниже. Интуитивно, достоверность означает, что в случае честного клиента и честного сервера клиент всегда получает верные элементы . Конфиденциальность определяется свойством неразличимости: получая на входе 2 кортежа выбранные злоумышленником, сервер не должен определить, какой из двух кортежей на самом деле использует клиент.


TemplateDifinitionIcon.svg Определение «Определение 1 - Абсолютная достоверность»
Многопоточный ВКИП-протокол обладает свойством абсолютной достоверности, если для , где получим , тогда .
TemplateDifinitionIcon.svg Определение «Определение - Вычислительная конфиденциальность»
Многопоточный ВКИП-протокол обладает свойством вычислительной конфиденциальности, если для всех неоднородных противников за полиномиальное время имеем

Где

Нижняя граница связи (m, n, l)-ВКИП

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

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

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

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

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

TemplateLemmaIcon.svg Лемма «Лемма 1»
Зададим . Пусть :. Зададим , где функция выдает наименьший лексикографический элемент из множества строк А. Множество

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

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

Очевидно, что и что любые входные данные удовлетворяют . Покажем, что - обманное множество. Пусть / Заметим, что должно быть , поэтому есть хотя бы одна точка, в которой не совпадает с . Без ограничения общности, скажем . Из этого следует, что так как .


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


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

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

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

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


Ограниченный многопоточный ВКИП

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

В этом разделе мы представим построение такого блока, который мы называем ограниченный многопоточный ВКИП, на основе однопоточного ВИКПа Гентри и Рамзана [5] и их наблюдении, что его можно использовать для многопоточных запросов. Безопасность ограниченного многопоточного ВКИПа основывается на предположении о неизвестности [4]. Это протокол с двумя сообщениями, и мы опишем его тремя алгоритмами (Запрос, Ответ, Извлечение) которые генерируют соответственно запрос клиента, ответ сервера и разрешают клиенту извлечь запись из этого ответа.

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

TemplateDifinitionIcon.svg Определение «Определение 3 - Предположение о выборе подгруппы»
Существует некоторое такое, что все вероятностные алгоритмы , выполяемые за полиномиальное время:

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

В качестве примера выберем в качестве модуля RSA длины , где и и - большие случайные положительные целые числа, и выберем как случайный элемент из с порядком для некоторого НОД. Гентри и Рамзан показали[5], что если . Когда генерирует набор , где , то предположение из опр. 3 сводится к варианту предположения о неизвестности [прим. 1]:

, где выдает и как описано выше, и выдает -битный RSA-модуль . Чтобы избежать атак методом факторизации по Копперсмиту при известном большом сомножителе , параметр должен быть выбран соответствующим образом. В частности, когда известен большой сомножитель более чем , то становится возможным факторизовать N (Копперсмит, [9][10], также см.[11] и связанные с ними обсуждения в [5]) нам следует выбрать .

Действительно, при таком выборе получим , что меньше, чем пока .

Имея , мы можем построить -ВКИП протокол с двумя сообщениями, следующий из протокола Гентри и Рамзана. Этот ограниченный протокол работает для параметров? удовлетворяющих :

Запрос Пусть - простые числа, полученные из . Пусть - наименьшие степени простых чисел , большие , то есть, . Пусть - индексы, отличные от индексов элементов, которые запрашивает клиент. Пусть и прогоним . Посылаем на сервер, сохраняем для дальнейших нужд.
Ответ Имеется база данных из -битовых элементов , используем Китайскую теорему об остатках для вычисления для и отправим клиенту.
Извлечение Для каждого , вычисляим и и найдем таким образом, что . На выходе получим

Видно, что процедура запроса требует проведение операций дискретного логарифмирования в циклических группах для , где порядок каждой подгруппы равен . При условии, что являются степенями простых , извлечение потребует шагов при использовании методов Giant-Step Baby-Step, когда пользователь вычисляет -е аналогично алгоритму Похлига-Хелмана [3] Вычисления сервера сводятся к одной операции экспоненциирования бит как в работе [5]

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

.

Используя ограничения из примера Гентри и Рамзана, основанные на RSA-моделях, мы можем использовать , который генерирует первые простых чисел, больших . Мы можем использовать следующие грубые ограничения на простые числа для . Поэтому для мы можем использовать многопоточный ВКИП-протокол во всех случаях, когда выполняется .

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

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


Рассуждения Вспомним, что, согласно Утв. 1, , таким образом, ограниченный протокол имеет связь . Может показаться, что мы не получаем никакого прироста при параллельном повторении протокола Гентри-Рамзана, имеющего связь для некоторого параметра безопасности . Однако, прирост на самом деле значительный, особенно при .

Для примера, рассмотрим случай . Тогда повторение протокола Гентри-Рамзана дает нам многопоточный протокол со связью . Теперь предположим, что и . Число бит в записи . С другой стороны, при использовании ограниченного многопоточного протокола и, следовательно, получаем протокол со связью . Таким образом для больших значений рассматриваемый протокол будет лучше повторения протокола Гентри-Рамзана раз.

Идеально корректный многопоточный ВКИП, оптимальный по связи

Наше сведение произвольного многопоточного ВКИП к ограниченному многопоточному ВКИП будет использовать ограниченный протокол из [5], описанный выше, и генератор псевдослучайных чисел (ГПЧ). Мы рассмотрим 4 варианта преобразований в зависимости от параметров . Мы изучим эти варианты преобразований и подразделах ниже. Наиболее трудный случай возникает при большом , которое при этом не достаточно велико для того, чтобы отправить БД целиком пользователю. Мы начнем с рассмотрения более простых случаев.

Многопоточный (m, n, l)-ВКИП для постоянных n/m

При пересылка БД целиком клиенту является асимптотически оптимальной. Для определенности, мы выберем предельное значение в записи , равное 9, и тогда будем отправлять всю БД клиенту при . Очевидно, получим ВКИП-протокол с 1 сообщением с идеальной корректностью и конфиденциальностью и оптимальной связью бит. В таком случае, сервер не выполняет никаких вычислений кроме тех, что необходимы для передачи БД.

Многопоточный(m, n, l)-ВКИП для маленьких m

Теперь представим простое расширение для ограниченного многопоточного ВКИП-протокола, являющегося оптимальным по связи при и . Мы проделаем это разбиением -битных записей на меньшие блоки размера . Это даст нам баз данных, содержащих -битные строки. Воспользуемся ограниченным многопоточным ВКИП-протоколом для извлечения записей в каждой из этих БД. Для этого мы должны выбрать параметр таким образом, чтобы он подходил под ограничение параметров протокола.

1. Пусть

2. Сервер делит на баз данных , где все есть -битные строки и есть конкатенация

3. Клиент и сервер применяют ограниченных ВКИП протоколов параллельно для

4. Клиент вычисляет конкатенацией результатов огарниченных ВКИП-протоколов для каждого индекса.

5. Клиент получает

Этот протокол выполняется за тоже число раундов, что и ограниченный ВКИП-протокол. Если на нужна только одна копия ограниченного протокола, так что получим сложзность связи бит. Если , мы получим сложность

при условии

Последнее условие выполняется для достаточно больших , потому что и , что влечет

,

асимптотически, что в свою очередь влечет

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

TemplateLemmaIcon.svg Лемма «Лемма 2.»
Многопоточный ВКИП-протокол, описанный выше, является корректным и конфиденциальным при при предположении, что лежащий в его основе протокол удовлетворяет этим условиям. Более того, если ограниченный ВКИП-протокол обладает идеальной корректностью, то и ВКИП-протокол выше обладает этим свойством.


Доказательство Выбирая мы добиваемся

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

,

где последнее неравентсов выполняется для значений


Многопоточный -ВКИП для больших значений и Многопоточный   ( m , n , l ) {\displaystyle ~(m,n,l)} -ВКИП для больших значений   m {\displaystyle ~m} и   l ≤ log 2 ⁡ ( n / m ) {\displaystyle ~l\leq \log {2}(n/m)}

Теперь рассмотрим случай, когда . Пусть есть два параметра, которые определим ниже. Разделим БД на блоков размера и к каждому из таких блоков мы применим ограниченный многопоточный ВКИП-протокол. Заметим, что при равномерном распределении запросов пользователя нам нужно извлечь в среднем лишь записей из каждого блока.

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

Вспомним, что ограниченный многопоточный ВКИП-алгоритм позволяет нам извлечь записей из каждого блока при условии, что (следует из опр. 1)

Когда мало, например, , нам нужно бит для извлечения

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

TemplateLemmaIcon.svg Лемма «Лемма 3.»
Пусть и пусть - непересекающиеся наборы со свойством . Для любого , где , существует семейство наборов таких, что:
  1. для каждого найдется какой-либо

Доказательство Пусть - разбиение А на при . Каждый может быть покрыт поднаборами размера из . Следовательно, мы можем покрыть А числом наборов .

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


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

  • Мы хотим, чтобы было достаточно велико для того, чтобы была мала вероятность попадания более чем записей в один блок.
  • Мы ограничены неравенством для использования ограниченного многопоточного ВКИП-протокола.
  • Наконец, мы хотим, чтобы было полиномиально по с тем, чтобы закодированная БД содержэала элементов и, следовательно, она обрабатывается за полиномиальное время по k.

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

Для выполнения последнего условия выберем и , что дает нам

Если при этом , мы получим и сервер будет работать за полиномиальное время. Отметим на будущее, что в то же время

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

1 Установим и и

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

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

4 Клиент отправляет на сервер и сервер переставляет индексы согласно

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

6 Клиент и сервер запускают ограниченный многопоточный ВКИП-протокол над закодированными блоками из записей для получения битных строк. Это отвечает извлечению до записей из каждого из оригинальных блоков.

7 Клиент декодирует результат и обращает перестановку записей, получая на выходе .

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

Касательно сложности связи, сначала вычислим её при

так, что . Мы отправляем стартовое значение для ГПП длины и запускаем ВКИП-протокол раз, получая общую связь вида

,

где мы применили неравенство

Далее рассмотрим случай . Получим сложность связи:

.

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

TemplateLemmaIcon.svg Лемма «Лемма 4»
ВКИП-протокол для корректен и защищен. Он обладает идеальной корректностью, если ограниченный многопоточный ВКИП-протокол обладает этим свойством.

Доказательство Протокол обладает свойством идеальной корректности, если ограниченный ВКИП-протокол идеально корректен. Нам необходимо проверить, что ограниченный протокол действительно можно применить, то есть для достаточно больших k имеем

.

Чтобы удостоверится в том, что это выполняется, покажем, что , так как

,

что следует из и (для достаточно больших k). Выбирая d в протоколе получим

, где второе неравенство следует из (для достаточно больших k).


Выбором параметров мы гарантируем, что ограниченный многопототочный ВКИП сложности связи k бит можно использовать на каждом блоке размера . Злоумышленника, с вероятностью взламывающего защиту протокола, можно заменить на злоумышленника, ограниченный многопоточный ВКИП-протокол с вероятностью , исключая маловероятный случай прорыва защиты из-за плохого результата ГПП. Аналогично гибридный аргумент показывает, что многопоточный протокол корректен. Когда начальное значение ГПП плохое, мы приходим к незащищенному, но идеально корректному ВКИП. Следовательно, если ограниченный многопоточный ВКИП обладает идеальной корректностью, то ей обладает и наш протокол.

Многопоточный ВКИП для Многопоточный ВКИП для   l > l o g 2 ( n / m ) {\displaystyle ~l>log2(n/m)}

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

Резюме: оптимальный по связи многопоточный ВКИП-протокол

Объединяя эти 4 протокола, оптимальный по связи многопоточный ВКИП:

1 Если отправляем всю БД клиенту.

2 Иначе если используем протокол из 5.2 со сложностью связи

3 Иначе если используем протокол из 5.3 со сложностью связи

4 Иначе если используем протокол из 5.4 со сложностью связи

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

TemplateTheoremIcon.svg Теорема Теорема 3
ВКИП-протокол, приведенный выше, корректен и защищен. Он обладает идеальной корректностью, если ограниченный многопоточный ВКИП-протокол обладает ею.
Доказательство
Без доказательства


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

Некоторые цензоры сделали полезные комментарии по этой статье. Мы хотели бы особо поблагодарить анонимного рецензента из ICALP 2009 за долгий и проницательный обзор. Первый автор был поддержан грантом номер EP/G013829/1 от Engineering and Physical Sciences Research Council, так же частично подержан грантом от NSF 0447808,0831304,0831306. Третий автор был поддержан грантом №8058 от Estonian Science Foundation и European Union через European Regional Development Fund.

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

  1. University College London, UK, E-mail: j.groth@ucl.ac.uk
  2. Department of Informatics, University of Athens, Greece , E-mail: aggelos@di.uoa.gr
  3. Cybernetica AS, Estonia, E-mail: lipmaa@research.cyber.ee
  4. Tallinn University, Estonia

Примечание

  1. Строго говоря, Гентри и Рамзан доказали это только для случая, когда простое число. Однако, доказательство не изменится для болеее общего случая, когда составное число

Литература

  1. Naor, M., Pinkas, B.: Oblivious Transfer and Polynomial Evaluation. In: Proceedings of the Thirty-First Annual ACM Symposium on the Theory of Computing, Atlanta, Georgia, USA, May 1–4, pp. 245–254. ACM Press, New York (1999)
  2. Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private Information Retrieval. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, October 23–25, pp. 41–50. IEEE, Los Alamitos (1995)
  3. 3,0 3,1 >Kushilevitz, E., Ostrovsky, R.: Replication is Not Needed: Single Database, Computationally-Private Information Retrieval. In: 38th Annual Symposium on Foundations of Computer Science, Miami Beach, Florida, October 20–22, pp. 364– 373. IEEE Computer Society, Los Alamitos (1997)
  4. 4,0 4,1 4,2 Cachin, C., Micali, S., Stadler, M.: Computational Private Information Retrieval with Polylogarithmic Communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
  5. 5,00 5,01 5,02 5,03 5,04 5,05 5,06 5,07 5,08 5,09 5,10 Gentry, C., Ramzan, Z.: Single-Database Private Information Retrieval with Constant Communication Rate. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 803–815. Springer, Heidelberg (2005)
  6. Lipmaa, H.: An Oblivious Transfer Protocol with Log-Squared Communication. In: Zhou, J., L ́opez, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 314–328. Springer, Heidelberg (2005)
  7. 7,0 7,1 Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Batch codes and their applications. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on the Theory of Computing, Chicago, IL, USA, June 13–16, pp. 262–271. ACM Press, New York (2004)
  8. 8,0 8,1 Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)
  9. Pohlig, S., Hellman, M.: An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance. IEEE Transactions on Information The- ory 24, 106–110 (1978)
  10. Coppersmith, D.: Finding a Small Root of a Univariate Modular Equation. In: Maurer [11], pp. 155–165
  11. Bl ̈omer, J., May, A.: A Tool Kit for Finding Small Roots of Bivariate Polynomi- als over the Integers. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 251–267. Springer, Heidelberg (2005)

Оригинал статьи

<doc>http://gir.bmstu.ru/data/ksbp_data/pdf/EUROCRYPT/EC%202011.00022_Two-Output%20Secure%20Computation%20with%20Malicious%20Adversaries.pdf</doc>