Searchable Encryption

Шифрование с возможностью поиска (англ. Searchable Encryption) — класс криптографических алгоритмов шифрования, в которых существует возможность осуществлять поиск по зашифрованным данным (файлам, записям базы данных и т.д.). Областью применения является предоставление приватности данных, хранимых на недоверенном удалённом ресурсе.

В общем случае, в основе такого шифрования могут лежать как симметричные, так и асимметричные шифры. Однако, так как практические задачи предполагают шифрование большого количества данных, чаще встречается использование симметричного шифрования с поиском (соответственно, англ. Searchable Symmetric Encryption или сокращённо SSE). Большинство асимметричных подходов основаны на шифровании по открытому ключу с поиском по ключевым словам (англ. Public Key Encryption with Keyword Search, сокращённо PEKS).

История

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

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

Первая работа в направлении поиска по шифрованным данным была изложена в 2000-м году Dawn Xiaodong Song, David Wagner и Adrian Perrig. Их алгоритм предполагал поиск по шифротексту с точным совпадением.

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

В статье Eu-Jin Goh 2003-го года впервые был предложен поиск по шифрованному индексу, который предполагал поиск точного совпадения. А в 2009-ом в статье Emily Shen, Elaine Shi и Brent Waters - приватный предикативный поиск.

В направлении PEKS первый результат представлен в статье 2004-го за авторством Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky и Giuseppe Persiano.

Изначально, при проверке новых алгоритмов на защищённость, проверялись только общие требования к криптографическим системам. Определения криптостойкости для SE, учитывающие особенности возможных новых видов утечек, были даны в статье 2006-го года от Reza Curtmola, Juan Garay, Seny Kamara и Rafail Ostrovsky.

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

Описание принципа

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

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

Классификация

SE основана на наличии клиент-серверной архитектуры. Как следствие, различные подходы к созданию алгоритмов могут различаться по количеству клиентов, имеющих доступ к данным. Могут быть один или несколько клиентов с правом размещать данные на сервере (записывающие), и один или несколько клиентов с правом производить поиск (читающие). Таким образом, выделяются 4 класса алгоритмов:

• один пишущий/один читающий (S/S)
• один пишущий/много читающих (S/M)
• много пишущих/один читающий (M/S)
• много пишущих/много читающих (M/M)

К классу S/S относятся, в большей степени, алгоритмы симметричного шифрования, так как хозяин информации будет хранить у себя единственный ключ. Алгоритмы класса M/S предполагают наличие множества клиентов, шифрующих данные для единственного получателя. Так, например, устроена система шифрованной электронной почты. Стоит отметить, что алгоритмы этого класса можно тривиальным образом превратить в S/S алгоритмы, если читающий клиент не будет распространять открытый ключ.

В обзорной статье 2016-го года приводятся статистика наличия исследований в различных классах SE:

Исследования в области SE

Архитектура	S/S	S/M	M/S	M/M
точное совпадение	✓	✓	✓	✓
конъюнкция	✓	-	✓	✓
сравнение	-	-	✓	-
поднабор	(✓)	-	✓	-
диапозон	(✓)	-	✓	-
wildcard	-	-	✓	-
fuzzy	✓	-	-	-
Количество схем	28	2	19	9
Количество реализаций	6	1	0	2
Временной промежуток	2000–2013	2009–2011	2004–2011	2007–2008

Пример (алгоритм SWP00)

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

Базовая идея

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

Пусть пользователь Алиса хочет зашифровать документ из слов ${\textstyle W_{1},W_{2},...,W_{l}}$. Её цель - произвести обратимую операцию XOR над каждым из слов с каким-то секретным значением.

Для этого ей понадобятся:

• псевдослучайный генератор G с зерном k, используется для создания последовательности S, и k является частью её секретного ключа

• псевдослучайная функция F с ключами ${\textstyle k_{i}}$, необходимая для расширения элементов последовательности S до длинны слов (возвращает m-битные значения)

• псевдослучайная функция f с ключом ${\textstyle k'}$, для генерации ключей ${\textstyle k_{i}}$

• псевдослучайная перестановка E с ключом ${\textstyle k_{s}}$, для прешифрования

Алгоритм шифрования:

1. Сначала Алиса генерирует последовательность ${\textstyle S_{1},S_{2},...,S_{l}}$.
2. Чтобы зашифровать очередное слово ${\textstyle W_{i}}$ длинны n бит, расположенное на позиции i, генерируется ${\textstyle S_{i}}$ длинны n-m бит.
3. Вычисляется ${\textstyle T_{i}}$ как конкатенация ${\textstyle S_{i}}$ и ${\textstyle F_{k_{i}}(S_{i})}$
   ${\textstyle T_{i}=<S_{i},F_{k_{i}}(S_{i})>}$.
4. Результатом шифрования будет ${\textstyle C_{i}=W_{i}+T_{i}}$.

При этом последовательность ключей ${\textstyle k_{i}}$ может быть выбрана разными способами (например, использовать один и тот же ключ или какой-то набор ключей).

Так построенная схема позволяет проводить поиск по шифротексту следующим образом:

Пусть зашифрованный документ Алисы хранится у Боба. Алиса хочет отыскать слово W, поэтому отправляет его вместе с набором ключей ${\textstyle k_{i}}$ к таким позициям i, где может находиться W. Тогда Боб проверяет, представима ли сумма по модулю очередного шифрослова с образцом в виде:

${\textstyle C_{i}+W=<s,F_{k_{i}}(s)>}$

Если такое условие выполняется, то Алисе возвращается подтверждение совпадения и позиция i. Если же для какой-то из позиций ключ не передавался, то Боб ничего не узнаёт об этом слове.

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

Скрытие ключей

Чтобы повысить гибкость поиска и приватность шифрованных данных можно использовать дополнительный генератор для ключей с отдельным ключом для него. Тогда ${\textstyle k_{i}=f_{k'}(W_{i})}$ для каждого слова, и вместо раскрытия группы ключей, Алиса будет прикладывать к поисковому запросу только необходимый.

Скрытие открытого текста

Чтобы Боб не получал доступ к открытым данным, их следует предварительно шифровать. То есть предварительно следует получить прешифрованный документ из ${\textstyle X_{1},X_{2},...,X_{l}}$, где ${\textstyle X_{i}=E_{k^{s}}(W_{i})}$. Стоит отметить, что шифрование E не должно зависеть от позиции слова (одинаковые слова в разных частях документа породят одинаковый шифротекст).

Для поиска, Алиса отправляет Бобу зашифрованное слово ${\textstyle X=E_{k^{s}}(W)}$ и ключ к нему ${\textstyle k_{i}=f_{k'}(X_{i})}$. Боб сможет осуществить поиск, не имея доступа к открытому тексту.

Однако в этой схеме проявляется новый недостаток. Из одного только шифротекста Алиса не сможет получить исходный текст, если она не знает, что там было. То есть ей необходимо знать ${\textstyle E(W_{i})}$ (или, хотя бы, последние m бит) чтобы из ${\textstyle C_{i}}$ восстановить ${\textstyle W_{i}}$.

Окончательный вариант

Конечная форма алгоритма Сонг-Вагнера-Перрига выглядит следующим образом:

1. Над словом ${\textstyle W_{i}}$ выполняется пре-шифрация: ${\textstyle X_{i}=E_{k^{s}}(W_{i})}$.
2. ${\textstyle X_{i}}$ делится на две части - ${\textstyle L_{i}}$ длинны n-m бит и ${\textstyle R_{i}}$ длинны m бит.
3. Из ${\textstyle L_{i}}$ генерируется ключ ${\textstyle k_{i}=f_{k'}(L_{i})}$.
4. Генератором G с ключом k генерируется (n-m)-битный член последовательности ${\textstyle S_{i}}$.
5. ${\textstyle S_{i}}$ расширяется до n-битного ${\textstyle T_{i}=<S_{i},F_{k_{i}}(S_{i})>}$.
6. Наконец шифротекст вычисляется как ${\textstyle C_{i}=T_{i}+X_{i}}$.

Поиск на стороне Боба происходит как описано ранее, используя ${\textstyle (X,k_{i})}$.

В этой схеме Алиса (или кто-либо ещё) может расшифровать данные, имея ключи ${\textstyle k,k'}$ и ${\textstyle k^{s}}$ и зная положение слова i. Для этого:

1. Алиса получает при помощи зерна k элемент ${\textstyle S_{i}}$.
2. ${\textstyle L_{i}}$ считается сложением по модулю 2 старших n-m бит ${\textstyle C_{i}}$ c ${\textstyle S_{i}}$.
3. Восстанавливается ${\textstyle T_{i}=<S_{i},F_{k_{i}}(S_{i})>}$.
4. Исходный текст находится как ${\textstyle W_{i}=E_{k^{s}}^{-1}(C_{i}+T_{i})}$.

Применение

До закрытия Google Desktop предполагалось, что он будет ярким примером использования SSE.

Однако на текущий момент реализации алгоритмов (например, открытая реализация OpenSSE) имеют скорее исследовательский, а не практический характер [1].