Структурированное Шифрование и Управляемое Раскрытие

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:06, 8 января 2016.
Structured Encryption and Controlled Disclosure
SECD.png
Авторы Melissa Chase

Seny Kamara

Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал



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

Введение

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

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

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

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

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

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

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

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

Применение структурированного шифрования

Конфиденциальные запросы к зашифрованным данным.

Основное применение структурированного шифрования заключается в выполнении конфиденциальных запросов к зашифрованных данных. В этом случае клиент шифрует свои (структурированные) данные и в результате получает зашифрованную структуру данных и последовательность шифротекстов . Затем передаются на сервер. Всякий раз, когда клиент хочет запросить данные, он отправляет маркер серверу, который восстанавливает индексы для соответствующих шифротекстов. Использование структурированной схемы шифрования таким способом позволяет клиенту хранить его данные удаленно и одновременно гарантирует конфиденциальность данных на сервере (смысл обрисован в общих чертах выше), эффективное выполнение запросов и извлечение данных. Хотя этот вопрос получил значительное внимание в ряде документов [7] [1] [8] [9] [10] [11] [12] [13], насколько нам известно, он никогда не рассматривался для других видов данных.

Управляемое раскрытие для локальных алгоритмов.

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

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

Другое применение управляемого раскрытия относится к появляющейся области (расположенных в облаке) сервисов обмена данными, таких как Microsoft’s Dallas [14] и Infochimps [15] . Здесь, поставщик "облачной" инфраструктуры действует как брокер между провайдером данных, который хочет продать доступ к большому объему данных, и потребителем данных, который нуждается в доступе к данным. Данные хранятся “в облаке”, и облачный оператор управляет доступом потребителя к данным провайдера. Используя управляемое раскрытие, провайдер может зашифровать свои данные прежде, чем сохранить их в облаке и предоставлять маркеры потребителю в случае необходимости. У такого подхода есть несколько преимуществ: (1) провайдер знает точный объем данных, полученный потребителем; и (2) провайдер может быть уверен, что потребитель может получить доступ только к авторизованным сегментам данных, даже если потребитель и оператор тайно сговариваются.

Очевидно, если алгоритм, выполняемый сервером (или потребителем данных), является "глобальным" в том смысле, что он должен считать все данные, то в этом случае управляемое раскрытие не обеспечивает безопасность. С другой стороны, если алгоритм "локален", в том смысле, что он должен считывать только часть данных, управляемое раскрытие сохраняет конфиденциальность остальных данных. Есть многочисленные алгоритмы, которые демонстрируют этот вид локального поведения, и они широко используются для решения множества различных задач. К примеру, существует множество задач оптимизации, такие как задача коммивояжера или задача о вершинном покрытии. На практике они решаются с использованием алгоритмов локального поиска (например, hill climbing - восхождение на вершину, генетические алгоритмы). Некоторые алгоритмы анализа ссылок для веб-поиска, такие как алгоритм HITS Клейнберга [16] (и связанный алгоритм SALSA [17] ) являются локальными. Наконец, недавняя работа Brautbar и Kearns над алгоритмами “jump and crawl” (“переход и проверка”) [18] мотивирует и предлагает несколько локальных алгоритмов для анализа социальных сетей, включая алгоритмы для поиска вершин с высокой степенью и высоким коэффициентом кластеризации.

Управляемое раскрытие может быть рассмотрено как компромисс между полной безопасностью с одной стороны и эффективностью и функциональностью с другой. В случаях, где вычисление должно быть выполнено с большими объемами данных и "полностью защищено" такие решения как многостороннее вычисление [19] [5] [20] и полностью гомоморфное шифрование [6] являются непомерно дорогими, управляемое раскрытие обеспечивает практическое решение без значительного ущерба для безопасности.

Наши результаты

Выполнение конфиденциальных запросов к зашифрованным данным является важной задачей, которая подкреплена недавней тенденцией относительно "облачного" хранилища. Предоставление клиентам способ шифрования их данных без потери возможности эффективно запрашивать и получать их дает очевидные преимущества клиенту, а также освобождает поставщика "облачной" инфраструктуры от многих юридического формальностей (см. [21] [22] [23] для обсуждения этих проблем). Это обеспечивает механизм, с помощью которого клиенты, работающие в определенных отраслях, могут использовать "облачное" хранилище" (например, чтобы сохранить медицинскую документацию или финансовые документы), сохраняя при этом гибкость.

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

Для устранения этой проблемы нами:

  1. представлено понятие структурированного шифрования, которое обобщает симметричное шифрование с возможностью поиска, основанное на индексе [1] [2] [3] к произвольно-структурированным данным, и предложено новое применение структурированного шифрования (и следовательно SSE) к проблеме управляемого раскрытия.
  2. расширено адаптивное определение безопасности [3] к задаче структурированного шифрования.
  3. представлены конструкции адаптивно-безопасных структурированных схем шифрования множества структур и запросов, включающих:
    1. поисковые запросы в массивах данных. Даны массив данных и пара , необходимо получить значение, сохраненное в строке и столбце . Это используется, например при поисковом запросе для цифрового изображения или извлечении карт.
    2. Поисковые запросы в маркированных данных. Дан ряд маркированных элементов и ключевое слово , необходимо получить элементы, маркированные . Получается знакомая задача шифрования с возможностью поиска. Мы отмечаем, что наша конструкция показывает комбинацию полезных свойств, которых, насколько мы знаем, не достигает ни одна предыдущая схема.
    3. Cоседние запросы в графе. Даны граф и узел , возврат всех узлов, смежных с . Это используется, например, для отображения "списка друзей" пользователя в социальной сети.
    4. Запросы смежности в графе. Даны граф и два узла и , на выходе получается 1, если эти узлы смежные и 0, если нет. Это используется, например, для проверки, являются ли два пользователя "друзьями" в социальной сети.
    В то время как представленные выше конструкции полезны каждая по-своему, цель структурированного шифрования состоит в том, чтобы создать схемы, которые в способны зашифровать сложные структуры и обработать необычные запросы, которые используют сложные структуры данных. Как пример, рассмотрите случай веб-графов (то есть, подграфов сети), которые составлены из страниц и с текстом, и с гиперссылками. Шифрование страниц веб-графа с использованием шифрования с возможностью поиска позволяет осуществлять поиск по ключевым словам только на зашифрованных страницах. Веб-графы, однако, представляют намного более богатую структуру, и мы хотим выполнить более сложные запросы на них. В связи с этим, наша работа призвана показать, как зашифровать веб-графы и что мы именуем маркированными данными графа. В частности, нами:
  4. представлена структурированная схема шифрования маркированных графов, которая обрабатывает фокусируемые запросы подграфа. В общих чертах, для данного поиска по ключевым словам фокусируемый запрос подграфа к веб-графу возвращает подграф, который кодирует достаточную информацию, чтобы привести к хорошему ранжированию страниц для поиска. Эти запросы - основная часть алгоритма Kleinberg’s HITS [16] (и его многих преемников).
    Наша конструкция использует в качестве стандартных блоков некоторые из упомянутых выше схем. Мы подчеркиваем, что не достаточно использовать схемы "как есть", мы показываем новый способ объединить структурированные схемы шифрования простых структур, чтобы создать схемы, которые обрабатывают более сложные данные и более необычные запросы. Подход является общим и может быть адаптирован к другим сложным типам данных.

Связанная работа

Мы уже упоминали работу над забывающими ОЗУ, защищенным двусторонним вычислением и FHE, поэтому ограничим последующее обсуждение шифрованием с возможностью поиска и функциональным шифрованием.

Шифрование с возможностью поиска. Как упомянуто выше, структурированное шифрование - обобщение понятия безопасного индекса, изначально предложенного Goh [1] с целью создания симметричных схем шифрования с возможностью поиска [7] . В [1] Goh дает формальное определение безопасности для безопасных индексов и конструкции, основанной на фильтрах Блума. Это сопровождалось [2] и [3], последнее из которых дает более строгие определения безопасности и более эффективные конструкции. Наши определения безопасности для структурированного шифрования в разделе 4 обобщают определения в [3] для произвольно-структурированных данных. Шифрование с возможностью поиска было также рассмотрено в контексте открытых ключей [10] [9] [8] [24] [13] [25].

Функциональное шифрование. Функциональное шифрование [26] является недавней парадигмой, которая обобщает работу над множеством задач, включая шифрование, основанное на идентификационных данных [27] [28] [27] [28], шифрование основанное на атрибуте [29] [30] [31], и предикатное шифрование [32] [33].

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

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

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

Типы данных. Абстрактный тип данных - набор объектов вместе с рядом операций, определенных на объектах. Для простоты и визуальной ясности мы определяем типы данных так, что для них определена единственная операция, но это определение может быть легко расширено на модель типа данных с несколькими операциями. Формально, тип данных определен множеством и операцией: , где является областью определения операции и – область значений. Множество, oбласть определения и область значений - конечные множества, индексированные параметром безопасности . В этой работе мы предполагаем, что множество - полностью упорядоченный набор и что область значений включает специальный элемент обозначающий отказ.

Определения

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

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

Ассоциативность. Явным свойством некоторых конструкций (например, неадаптивной безопасной конструкция SSE [3] ) является ассоциативность. Интуитивно, схема ассоциативна, если можно связать элемент с элементом данных таким способом, при котором в результате работы запроса возвращается, в дополнение к указателям , строка . Получаем это путем пересматривания пространства сообщений наших алгоритмов шифрования, чтобы получить, в дополнение к структуре данных последовательность пар, которые состоят из конфиденциального элемента данных и полуконфиденциального элемента . Мы иногда обращаемся к последовательностям и как и , соответственно.

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


TemplateDifinitionIcon.svg Определение «Определение 1 (Структурированное шифрование с закрытым ключом). »

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

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

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

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

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

 : детерминированный алгоритм, который получает на вход секретный ключ и шифротекст и выводит сообщение .

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

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

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

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


TemplateDifinitionIcon.svg Определение «Определение 2 (CQA2-безопасность). »

Пусть - ассоциативная структурированная схема шифрования с закрытым ключом для данных типа , поддерживающая операцию:

, для некоторого , и рассматривающая следующие вероятностные эксперименты, где - противник, - средство моделирования и , и - (stateful) алгоритмы утечки:

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

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

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


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


TemplateDifinitionIcon.svg Определение «Определение 3 (Запросы и перекрестные шаблоны). »

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

Структурированное шифрование для базовых структур

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

Поисковые запросы на матрицах

Мы описываем структурированную схему шифрования матричных структурированных данных, которые состоят из матричных указателей в последовательности элементов данных . Здесь, матричный тип множеством и областью поиска , который берет за исходные данные матрицу и пару и выдает . Матричные структурированные данные являются вездесущими и включают любой вид двумерных данных. Рассмотрим, например, случай цифровых изображений, которые могут быть просмотрены как пара , где является матрицей так, что, ячейка в расположении указывает на некоторое , которое кодирует цвет пикселя в расположении в изображении. Наша конструкция, описанная в рисунке 1 ниже, ассоциативна. На высоком уровне шифрование сделано (1) дополнение элементов данных, чтобы сохранить ту же самую длину; (2) в произвольном порядке при перестановке расположения элементов данных, (3) в произвольном порядке перестановка расположения матричных ячеек, используя PRP; и (4) шифрование содержания ячеек (и полуконфиденциальных данных) использование вывода PRF. Цель последних двух шагов непосредственна. Шаги (1) и (2) - то, что позволяет нам скрыть часть схемы доступа, вызывая псевдо-случайную перестановку между и . Запросы поиска обработаны, отправляя переставленное расположение ячейки (которое может быть восстановлено клиентом, так как оно хранит ключ к PRP), и вывод PRF имел обыкновение шифровать содержание (которое может также быть восстановлено, так как клиент хранит ключ к PRF). В Теореме 1 ниже мы показываем, что конструкция выше безопасна против выборочных адаптивных атак.


TemplateTheoremIcon.svg Теорема Теорема 1
Пусть , и псевдо-случайны и защищено CPA , следовательно, матрица -защищена от выборочных адаптивных атак, где и .
Доказательство

Доказательство опущено из-за недостатка места и представлено в [12].


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

  •  : создаются две случайные -битные строки , и ключ . Тогда .
  •  : построим матрицу размером таким образом:
  1. проанализируем при и
  2. выберем псевдослучайную последовательность
  3. простая -битная строка равномерно случайна
  4. для всех ,

определим где , в точке в .

Если , то заменяется случайной строкой соответствующей длины. Пусть последовательность случайной перестановки неких слов так, что они имеют ту же самую длину и перестановку, что и в . Для , пусть . На выходе и .

  •  : На выходе , где и .
  • : проанализируем как ; посчитаем и выведем .
  •  : возвращаем .

Рис. 1. Ассоциативная структурированная схема шифрования матриц

Поисковые запросы на маркированных данных

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

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

  • : два простых случайных - битных ключа ,, и полученный ключ . Установим .
  •  : построим словарь следующим образом:
  1. Проанализируем как и .
  2. Выберем две псевдослучайные последовательности
  3. простая - битная строка равномерно случайная
  4. Для всех таких что , и сохраняем в с поиском ключа .

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

  •  : на выходе .
  •  : проанализируем как и вычислим , где ссылается на значение хранящееся в с поиском ключа . Если не в тогда на выходе и . Иначе проанализируем как и на выходе и .
  •  : на выходе .

Рис. 2. Ассоциативная структурированная схема шифрования маркированных данных.


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

Если , и псевдо-случайны и защищен CPA, то - защищен от адаптивных атак, где и .

Доказательство
Доказательство опущено из-за недостатка места, но показано в [12].


Соседние запросы на графах

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

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

Пусть - ассоциативная структурированная схема шифрования для маркированных данных. Наша схема определяется как:

  • : создаем и выводим .
  •  : распространяем как и и создаем маркированую , связанную с каждым . Установим , где

устанавливает правила в . На выходе .

  •  : посчитаем и получим на выходе .
  •  : на выходе .
  •  : на выходе .

Рис. 3. Структурированная схема шифрования графов, поддерживающих соседние запросы


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

Если -защищен от выборочных адаптивных атак, то - так же защищен от выборочных адаптивных атак.

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

Теорема соответствует схеме. Заметим, что если «Метка» инстанцируется со схемой от Раздела 5.2, то пропускает размер графика, некоторое число элементов данных и длину самого большого элемента данных, в то время как пропускает степень узла и перекрестные шаблоны и запрос.

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

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


Запросы смежности на графах

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

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

  •  : создаем и получаем на выходе .
  •  : строим матрицу таким образом:

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

  •  :посчитаем и получим на выходе .
  •  : на выходе .
  •  : на выходе .

Рис. 4. Структурированная схема шифрования графов, поддерживающих запросы смежности


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

Если матрица защищена от выборочных адаптивных атак, тогда граф (Graph) также защищен от выборочных адаптивных атак.

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


Структурированное шифрование для маркированных графов

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

Фокусируемые запросы подграфа. Один пример сложных запросов на веб-графах - фокусируемые запросы подграфа. Эти запросы - основная часть определенного класса из алгоритмов поисковой системы, который включает оригинальный алгоритм Kleinberg’s HITS [16] и алгоритм SALSA [17]. На высоком уровне они работают следующим образом. Дано ключевое слово , поиск по ключевым словам выполняется по веб-страницам. Это приводит к подмножеству страниц, названных корневым графом. Фокусируемый подграф затем создается путем добавления всех страниц, которые также связаны со страницами в корневом графе. Итеративный алгоритм применяется к фокусируемому подграфу, который возвращает для каждой страницы, значение счетчика, которое определяет количественное отношение относительно ключевого слова . Ключевое свойство этих алгоритмов "анализа ссылки" (и причина их успеха) - то, что они пользуются не только преимуществом информации, предоставленной ключевыми словами, связанными со страницами, но также и неявной информацией, встроенной в структуру графа (то есть, ссылками) веб-графа.

Наш подход.

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

Наша конструкция.

Мы иллюстрируем наш второй подход для случая веб-графов, но отмечаем, что наша конструкция применяется к любым маркированным данным графа. Подробное описание нашей конструкции дано в рисунке 5. Мы отмечаем, конструкция не ассоциативна. Веб-граф будет рассматриваться как кортеж , который состоит из ориентированного графа размера , маркировки по пространству ключевого слова и текстовых страниц . Граф кодирует структуру ссылок веб-графа, и маркировка присваивает ключевые слова каждой странице. Целевая операция берет как исходные данные ориентированный граф размера и ключевое слово и выдает подграф , который состоит из (1) узлов в  ; (2) любых узлов, которые соединяются с узлами в  ; и (3) любых узлов, которые выходят из узлов в .

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

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


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

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

и

.

Доказательство
Доказательство опущено из-за нехватки места, представлено в [12].


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

  •  : создаются три ключа , .
  • :
  1. считаем ,
  2. считаем ,
  3. для ,
    1. считаем ,
    2. считаем ,
  4. Пусть отмечает создание для всех слов в (например, каждое имеет в своем составе маркированные слова) и пусть ,
  5. считаем , где состоит из и ,
  6. на выходе и .
  •  : на выходе .
  •  :
  1. считаем
  2. для всех ,
    1. считаем ,
    2. считаем ,
    3. на выходе .
  •  : возвращаем .

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

Заключения и будущее развитие

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

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

Мы благодарны Кристин Лотер за поддержку на ранних стадий этой работы, Шерману Чоу и Сэтья Локаму за полезных советы относительно шифрования графиков и Сьюзен Хенбергер за идею о полном сравнении с функциональным шифрованием. Мы также благодарны Адаму О'Нилу за полезные советы о функциональном шифровании. Наконец, мы благодарим Эмили Шен и Чарэлэмпоса Пэпамантоу за дополнительные источники.

Ссылки

  1. 1,0 1,1 1,2 1,3 1,4 1,5 E-J. Goh. Secure indexes. Technical Report 2003/216, IACR ePrint Cryptography Archive, 2003.See http://eprint.iacr.org/2003/216. See http://eprint.iacr.org/2003/216.
  2. 2,0 2,1 2,2 2,3 M. Brautbar and M. Kearns. Local algorithms for _nding intersting individuals in large networks.In Innovations in Computer Science (ICS '10), 2010.
  3. 3,0 3,1 3,2 3,3 3,4 3,5 3,6 3,7 3,8 3,9 R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky. Searchable symmetric encryption: Improved de_nitions and e_cient constructions. In ACM Conference on Computer and Communications Security (CCS '06), pages 79{88. ACM, 2006.
  4. O. Goldreich and R. Ostrovsky. Software protection and simulation on oblivious RAMs. Journal of the ACM, 43(3):431{473, 1996.
  5. 5,0 5,1 B. Waters, D. Balfanz, G. Durfee, and D. Smetters. Building an encrypted and searchable auditlog. In Network and Distributed System Security Symposium (NDSS '04). The Internet Society, 2004.
  6. 6,0 6,1 C. Gentry. Fully homomorphic encryption using ideal lattices. In ACM Symposium on Theory of Computing (STOC '09), pages 169{178. ACM Press, 2009.
  7. 7,0 7,1 E. Shi, J. Bethencourt, T. Chan, D. Song, and A. Perrig. Multi-dimensional range query over encrypted data. In IEEE Symposium on Security and Privacy, pages 350{364, Washington, DC, USA, 2007. IEEE Computer Society.
  8. 8,0 8,1 D. Boneh, G. di Crescenzo, R. Ostrovsky, and G. Persiano. Public key encryption with keyword search. In Advances in Cryptology { EUROCRYPT '04, volume 3027 of Lecture Notes in Computer Science, pages 506{522. Springer, 2004.
  9. 9,0 9,1 D. Song, D. Wagner, and A. Perrig. Practical techniques for searching on encrypted data. In IEEE Symposium on Research in Security and Privacy, pages 44{55. IEEE Computer Society, 2000.
  10. 10,0 10,1 M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. M. Lee, G. Neven, P. Paillier, and H. Shi. Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions. In V. Shoup, editor, Advances in Cryptology { CRYPTO '05, volume 3621 of Lecture Notes in Computer Science, pages 205{222. Springer, 2005.
  11. M. Bellare, A. Boldyreva, and A. O'Neill. Deterministic and e_ciently searchable encryption. In A. Menezes, editor, Advances in Cryptology { CRYPTO '07, Lecture Notes in Computer Science, pages 535{552. Springer, 2007.
  12. A. Shamir. Identity-based cryptosystems and signature schemes. In George Robert Blakley andDavid Chaum, editors, Advances in Cryptology { CRYPTO '84, volume 196 of Lecture Notes inComputer Science, pages 47{53. Springer, 1985.
  13. 13,0 13,1 D. Boneh, E. Kushilevitz, R. Ostrovsky, and W. Skeith. Public-key encryption that allows PIR queries. In A. Menezes, editor, Advances in Cryptology { CRYPTO '07, volume 4622 of Lecture Notes in Computer Science, pages 50{67. Springer, 2007.
  14. Micrsoft Corp. Windows azure marketplace. http://www.microsoft.com/windowsazure/marketplace/.
  15. Infochimps. http://www.infochimps.org.
  16. 16,0 16,1 16,2 J. Katz, A. Sahai, and B. Waters. Predicate encryption supporting disjunctions, polynomial equations, and inner products. In Advances in Cryptology - EUROCRYPT 2008, volume 4965 ofLecture Notes in Computer Science, pages 146{162. Springer, 2008.
  17. 17,0 17,1 J. Kleinberg. Authoritative sources in a hyperlinked environment. In Symposium on Discrete Algorithms (SODA '08), pages 668{677. Society for Industrial and Applied Mathematics, 1998.22
  18. X. Boyen and B. Waters. Anonymous hierarchical identity-based encryption (without randomoracles). In Advances in Cryptology - CRYPTO 2006, volume 4117 of Lecture Notes in ComputerScience, pages 290{307. Springer, 2006.
  19. O. Goldreich, S. Micali, and A. Wigderson. How to play ANY mental game. In ACM Symposium on the Theory of Computation (STOC '87), pages 218{229. ACM, 1987.
  20. D. Chaum, C. Cr_epeau, and I. Damgard. Multiparty unconditionally secure protocols. In ACM symposium on Theory of computing (STOC '88), pages 11{19. ACM, 1988.
  21. J. Bardin, J. Callas, S. Chaput, P. Fusco, F. Gilbert, C. Ho_, D. Hurst, S. Kumaraswamy, L. Lynch,S. Matsumoto, B. O'Higgins, J. Pawluk, G. Reese, J. Reich, J. Ritter, J. Spivey, and J. Viega. Security guidance for critical areas of focus in cloud computing. Technical report, Cloud Security Alliance, April 2009.
  22. S. Kamara and K. Lauter. Cryptographic cloud storage. In Workshop on on Real-Life Cryptographic Protocols and Standardization, volume 6054 of Lecture Notes in Computer Science, pages 136{149. Springer, 2010.
  23. E. Shen, E. Shi, and B.Waters. Predicate privacy in encryption systems. In Theory of Cryptography Conference (TCC '09), pages 457{473, Berlin, Heidelberg, 2009. Springer-Verlag.
  24. D. Boneh and B. Waters. Conjunctive, subset, and range queries on encrypted data. In Theory of Cryptography Conference (TCC '07), volume 4392 of Lecture Notes in Computer Science, pages 535{554. Springer, 2007.
  25. D. Boneh, A. Sahai, and B. Waters. Functional encryption: De_nitions and challenges. Technical Report 2010/543, IACR ePrint Cryptography Archive, 2010. See http://eprint.iacr.org/ 2010/543.
  26. [34] C. Soghoian. Caught in the cloud: Privacy, encryption, and government back doors in the web 2.0 era. Journal on Telecommunications and High Technology Law, 8(2), 2010.
  27. 27,0 27,1 Yehuda Lindell and Benny Pinkas. A proof of security of yao's protocol for two-party computation. J. Cryptology, 22(2):161{188, 2009.
  28. 28,0 28,1 D. Boneh and M. Franklin. Identity-based encryption from the weil pairing. In Advances in Cryptology - CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 213{229. Springer-Verlag, 2001.
  29. R. Lempel and S. Moran. SALSA: The stochastic approach for link-structure analysis. ACM Transactions on Information Systems, 19(2):131{160, April 2001.
  30. V. Goyal, O. Pandey, A. Sahai, and B. Waters. Attribute-based encryption for _ne-grained access control of encrypted data. In ACM conference on Computer and communications security (CCS'06), pages 89{98, New York, NY, USA, 2006. ACM.
  31. J. Bethencourt, A. Sahai, and B. Waters. Ciphertext-policy attribute-based encryption. In IEEE Symposium on Security and Privacy, pages 321{334. IEEE Computer Society, 2007.
  32. J. Katz and Y. Lindell. Introduction to Modern Cryptography. Chapman & Hall/CRC, 2008.
  33. A. Sahai and B. Waters. Fuzzy identity-based encryption. In R. Cramer, editor, Advances in Cryptology { EUROCRYPT '05, volume 3494 of Lecture Notes in Computer Science, pages 457{473. Springer, 2005.
  34. Y. Chang and M. Mitzenmacher. Privacy preserving keyword searches on remote encrypted data. In Applied Cryptography and Network Security (ACNS '05), volume 3531 of Lecture Notes in Computer Science, pages 442{455. Springer, 2005.
  35. R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky. Searchable symmetric encryption: Improved de_nitions and e_cient constructions. Journal version (under submission), 2010.