1.Обзор схем шифрования с возможностью поиска в зашифрованных данных 1.1.Существующие модели поиска по зашифрованным данным 1.1.1.Oblivious RAM
Одним из самых сильных с точки зрения безопасности является подход к поиску в зашифрованных данных с использованием, так называемой, забывчивой памяти (Oblivious RAM, ORAM). Концепция ORAM была предложена в 1996 году в работе Голдриха и Островски [18] и подразумевала собой устройство памяти, которое позволяет считывать и записывать информацию таким образом, что само устройство не знает, в каких областях памяти были произведены операции.
Подобная концепция реализуется с помощью протоколов для чтения и записи. Двусторонний протокол чтения позволяет пользователю получить -й элемент памяти в качестве выходного значения, в то время как входными параметрами являются номер элемента памяти  и секретный ключ. Серверу протокол чтения ничего не возвращает, получая на вход непосредственно саму забывчивую память, т.е. некую область памяти. В свою очередь, протокол записи получает от пользователя номер элемента памяти и значение для записи  , ничего ему не возвращая. Сервер же передает протоколу записи забывчивую память и получает назад ее обновленную версию.
Наличие подобных протоколов позволяет сконструировать решение для поиска по зашифрованным данным. Для этого требуется со стороны сервера наличие двух элементов забывчивой памяти ORAM1 и ORAM2. Первый хранит в себе зашифрованные документы, второй – структуру данных, поддерживающую операцию поиска, например, обратный индекс в зашифрованной форме. Таким образом, процедура поиска сводится к набору обращений к серверу через протокол чтения, а обновление коллекции файлов – через протокол записи.
Безопасность данного подхода определяется непосредственно «забывчивостью» используемых структур. Подобное решение скрывает от сервера практически все, даже доступ к результатам поиска. Однако недостатком использования ORAM является относительная медленность поиска, что накладывает ограничения на размер хранимых коллекций и вычислительные ресурсы.
1.1.2.Searchable symmetric encryption
Searchable symmetric encryption (SSE) – это подход, который с самого начала был ориентирован на проблему взаимодействия клиента с сервером, который не может считаться до конца доверенным. Впервые подход был описан в 2000 году в работе Сонга, Вагнера и Перрига [36]. В общем случае SSE может быть описан в виде следующих четырех процедур: инициализация, генерация поискового запроса, поиск в зашифрованных данных и расшифровка результата. На начальном этапе производится шифрование коллекции документов и генерация секретного ключа. Затем клиент на основе отдельного ключевого слова и секретного ключа формирует поисковый запрос, который передается серверу. Далее в процедуре поиска сервер с помощью поискового запроса и имеющейся коллекции зашифрованных файлов находит вхождения слов в документы коллекции. В качестве результата пользователю возвращаются зашифрованные файлы, которые далее расшифровываются с помощью секретного ключа.
Подход, описанный выше, дает лишь общее представление о функционировании алгоритма. Более подробные описания алгоритмов с используемыми криптопримитивами зависят от конкретной реализации. Однако в общем случае вышеописанный подход позволяет разрабатывать схемы, обеспечивающие соответствие удовлетворительному уровню безопасности и эффективности.
1.1.3.Функциональное шифрование
Формальное определение функционального шифрование было предложено в 2010 году в работе Боней, Сахай и Вотерс [7]. Такая криптосистема поддерживает особые ограниченные секретные ключи, которые позволяют их владельцу узнать лишь значение некоторой функции от зашифрованных данных и ничего более. В качестве примера в оригинальной статье [7] приводится зашифрованная программа, имея ограниченный секретный ключ к которой, можно узнать лишь выходное значение этой программы к конкретным входным данным. Однако еще в 2001 году Боней и Франклином была предложена схема Identity-based encryption (IBE) [8], которая использует вышеописанный принцип. IBE реализует криптосистему с открытым ключом. В рамках данной концепции существует главная пара ключей (master private key, master public key) и набор отдельных секретных ключей, каждый из которых формируется н основе главного закрытого ключа и некоторого идентификатора. С помощью главного открытого ключа сообщения шифруются, а с помощью отдельных секретных ключей вычисляется некоторая функция от идентификатора и зашифрованного сообщения.
Идея использования IBE для поиска по зашифрованным данным была предложена в 2004 году [9]. Эта идея заключается в использовании отдельных ключевых слов, содержащихся в документе, в качестве идентификаторов для секретных ключей. Шифрование производится также на основе ключевого слова в качестве идентификатора. В данном случае удаленный компьютер хранит набор шифров, каждый из которых соответствует отдельному слову в файле. С помощью секретного ключа, выработанного с помощью ключевого слова в качестве идентификатора, сервер может узнать о принадлежности слова отдельному документу.
Недостатком этой схемы является то, что нотация IBE не гарантирует, что шифр скрывает информацию об идентификаторе. Тем не менее, эта проблема решаема путем построения схем шифрования на основе IBE, соответствующих данной задаче. Более серьезным недостатком является медленность работы алгоритма поиска, обусловленная тем, что требуется расшифровать все зашифрованные элементы, соответствующие паре документ – слово. Кроме того, использование криптосистемы с открытым ключом дает возможность удаленному компьютеру самостоятельно сгенерировать шифры с помощью главного открытого ключа и определенного словаря и ждать, пока полученный от пользователя ключ «подойдет» к одному из сгенерированных шифров.
1.1.4.Шифрование, сохраняющее свойства (Property-preserving encryption)
Property-preserving encryption (PPE) - это криптосистема, сохраняющая некоторые свойства оригинального сообщения после шифрования. Примером такой системы является детерминированное шифрование, особенностью которого является генерация определенного шифра для заданных ключа и оригинального сообщения. Таким образом, совпадение шифров свидетельствует о том, что оригинальные зашифрованные сообщения были идентичны. Другим примерами PPE являются шифрование, сохраняющее порядок (Order preserving encryption) [6]. Данная криптосистема позволяет шифровать оригинальные сообщения  и   ), таким образом, что их шифры, соответственно  и  , сохраняют их взаимное расположение:  .
Применительно к поиску по зашифрованным данным PPE на примере детерминированного шифрования используется следующим образом. Удаленный компьютер хранит соответствие между документами коллекции и зашифрованными словами, содержащимися в них. Поисковый запрос приходит на сервер в виде зашифрованного ключевого слова. Далее происходит поиск вхождений ключевого слова по всем документам коллекции на удаленном компьютере.
Недостатком такого подхода является линейное по отношению к размеру коллекции зашифрованных файлов время выполнения. Другими словами, для того чтобы найти все вхождения ключевого слова, требуется проверить все слова из коллекции файлов. Однако это может быть исправлено хранением детерминированных шифров с помощью структур данных, поддерживающих быстрый поиск (binary search tree). Более существенными недостатками этого подхода являются некоторые аспекты безопасности. Детерминированность шифров слов позволяет, с одной стороны, наблюдать вхождений одинаковых слов в документы, а с другой – отслеживать повторяемость в поисковых запросах.
1.1.5.Полностью гомоморфное шифрование
Термин «гомоморфное шифрование» впервые был сформулирован в 1978 Рональдом Ривестом, Леонардом Адлеманом и Майклом Дертузосом и подразумевал шифрование, которое позволяет производить операции над зашифрованными операндами без предварительной расшифровки [31]. В рамках этого термина выделяются частично гомоморфные системы и полностью гомоморфные системы. Первые поддерживают только одну операцию: сложение или умножение. Вторые, в свою очередь, гомоморфны относительно двух операций.
Впервые полностью гомоморфная система была предложена в 2009 году Крейгом Джентри [16]. В своей работе Джентри в качестве одного из возможных применений гомоморфной системы предложил поиск по зашифрованным данным. В общем случае полностью гомоморфное шифрование может быть использовано для решения проблемы удаленных вычислений. Эта проблема может быть сформулирована следующим образом. Пользователь хочет вычислить значение некоторой функции  в точке  , однако его компьютер не позволяет сделать этого, и вычисление  делегируется удаленному компьютеру, который не может считаться до конца доверенным. Таким образом, пользователь отправляет зашифрованное сообщение  , а затем получает значение функции  , расшифровывает его и получает значение . Поиск по зашифрованным данным является частным примером вышеописанной проблемы. В этом случае удаленный компьютер получает зашифрованный поисковый запрос и применяет алгоритм поиска для нахождения документов, содержащих эти слова.
Существенным недостатком такого подхода является линейное по отношению к размеру коллекции зашифрованных файлов время выполнения. Другими словами, для того чтобы найти все вхождения ключевого слова, требуется проверить все зашифрованные файлы.
1.1.6.Сравнение существующих моделей
Основные критерии для сравнения существующих подходов поиска по зашифрованным данным – это безопасность и временная и емкостная эффективность. Под безопасностью в задаче поиска по зашифрованным данным подразумевается, что зашифрованная коллекция файлов не раскрывает серверу информацию об оригинальных данных и что поисковые запросы, посылаемые на сервер, не раскрывают оригинальные ключевые слова.
Самым безопасным среди указанных подходов считается ORAM [24], поскольку он скрывает от сервера всю возможную информацию вплоть до результатов каждого отдельного поиска. PPE, напротив, характеризуется неудовлетворительными показателями, поскольку в его основе лежит детерминированное шифрование, которое позволяет серверу наблюдать за повторяемостью вхождения отдельных слов в документы и запросов. Функциональное шифрование показывает несколько лучшие характеристики, поскольку основано на рандомизированном шифровании и не позволяет отслеживать закономерности в данных и запросах. Но ввиду того, что такой подход использует криптосистему с открытым ключом, он может подвергаться словарным атакам со стороны сервера.
Среди описанных моделей PPE показывает сублинейное время работы алгоритма  , где  – размер коллекции документов, хранимых на сервере. Данный показатель достигается за счет использования специальных структур для хранения отдельных слов (binary search tree). Тем не менее, другие схемы (ORAM, функциональное шифрование, полностью гомоморфное шифрование) показывают линейное время поиска относительно размера коллекции, что связано с необходимостью в процедуре поиска проверять всё содержимое документов. Использование структур вроде обратного индекса в SSE лишает такой необходимости и позволяет свести сложность к линейной относительно  , где  – подмножество коллекции документов , содержащих слово  .
Немаловажным критерием также является практическая применимость той или иной схемы. Так, например, в ряде работ [11, 17, 24] отмечается, что концепция ORAM применима лишь к небольшим коллекциям документов и является скорее теоретической. Также полностью гомоморфное шифрование является в большей степени теоретическим. Таким образом, среди всех перечисленных моделей поиска по зашифрованным данным, многие являются слабо применимыми на практике ввиду низкого уровня безопасности и высоких требований к вычислительным ресурсам. В связи с этим, наиболее предпочтительной моделью видится SSE. Далее будут рассмотрены различные схемы, основанные на этой модели, и проведено их сравнение.
|
