20-09-2023
Шифрование с возможностью поиска (англ. Searchable Encryption или SE) — класс криптографических алгоритмов шифрования, в которых существует возможность осуществлять поиск по зашифрованным данным (файлам, записям базы данных и т. д.). Областью применения является предоставление приватности данных, хранимых на недоверенном удалённом ресурсе[1].
В общем случае, в основе такого шифрования могут лежать как симметричные, так и асимметричные шифры. Однако, так как практические задачи предполагают шифрование большого количества данных, чаще встречается использование симметричного шифрования с поиском (соответственно, англ. Searchable Symmetric Encryption или сокращённо SSE). Большинство асимметричных подходов основаны на шифровании по открытому ключу с поиском по ключевым словам (англ. Public Key Encryption with Keyword Search, сокращённо PEKS)[1].
Идея поиска по шифротексту стала актуальна на фоне введения облачных хранилищ данных. Данные пользователей хранятся на удалённых ресурсах, которые могут быть недоверенными (или «полудоверенными», англ. semitrusted[1]). Для обеспечения приватности в этом случае, к данным применяется шифрование[2]. Однако, при обычном шифровании для выполнения поиска по этим данным пользователь должен был либо выкачать весь набор данных и расшифровать его, либо же предоставить серверу средства для расшифровки, что противоречит изначальной цели шифрования[3].
Первыми попытками обеспечить приватность пользователя при работе с сервером можно считать работы 1990-х годов по oRAM, когда от сервера скрывался паттерн доступа к памяти при обработке запроса пользователя[4].
Первая работа в направлении поиска по шифрованным данным была изложена в 2000-м году Dawn Xiaodong Song, David Wagner и Adrian Perrig. Их алгоритм предполагал поиск по шифротексту с точным совпадением[5].
В то время, как алгоритм SWP00 строил метод шифрования, где поиск производится по самому шифротексту, большинство дальнейших реализаций предполагают построение зашифрованного индекса[1], поиск по которому занимает меньше времени[6][7], позволяет обновлять данные на сервере (dynamic SSE)[8], или использовать расширенный поиск[9][10]. Платой за это является увеличение размера шифрованных данных и повышение риска утечек.
В статье Eu-Jin Goh 2003-го года[6] впервые был предложен поиск по шифрованному индексу, который предполагал поиск точного совпадения. А в 2009-ом в статье Emily Shen, Elaine Shi и Brent Waters — приватный предикативный поиск[10].
В направлении PEKS первый результат представлен в статье 2004-го за авторством Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky и Giuseppe Persiano[4].
Изначально, при проверке новых алгоритмов на защищённость, проверялись только общие требования к криптографическим системам. Определения криптостойкости для SE, учитывающие особенности возможных новых видов утечек, были даны в статье 2006-го года от Reza Curtmola, Juan Garay, Seny Kamara и Rafail Ostrovsky[7].
Возможность поиска предполагает возможное наличие утечек информации с каждым поисковым запросом[11]. Они могут быть связанны с детерминированностью этапов шифрования, ограничениями входных данных и т. д. В качестве возможного решения рассматривалось использование oRAM для скрытия работы сервера и уменьшения утечек[11], но этот метод также и критиковался[12].
Для удовлетворения потребности в поиске, первым был предложен алгоритм Сонг-Вагнера-Перрига, при котором пользователь делает поисковые запросы на файловый сервер с зашифрованными данными, но при этом не раскрывает ему ни содержимого файлов, ни самого поискового запроса. Шифрование заключается в выполнении обратимой операции (например, XOR) с псевдослучайной последовательностью, а ключом, соответственно, является зерно ГПСП. Такая схема выполняет поиск за линейное от размера шифротекста время, а её надёжность зависит от качества псевдослучайной последовательности и прешифрования[5].
Кроме методов с основой из симметричного шифрования, своё место имеют алгоритмы с использованием открытого ключа. Например, электронные письма могут шифроваться для адресата его открытым ключом. Адресат может пожелать хранить их на удалённом почтовом сервере, но сохранить возможность поиска. Либо, схема может быть рассчитана на то, что из зашифрованного сообщения почтовый сервер сможет понять, что в нём, например, содержится ключевое слово («важно») и составит маршрут или установит приоритет пересылки письма соответствующим образом, но не узнает ничего кроме этого слова[4][13].
SE основана на наличии клиент-серверной архитектуры. Как следствие, различные подходы к созданию алгоритмов могут различаться по количеству клиентов, имеющих доступ к данным. Могут быть один или несколько клиентов с правом размещать данные на сервере (записывающие), и один или несколько клиентов с правом производить поиск (читающие). Таким образом, выделяются 4 класса алгоритмов[1]:
К классу S/S относятся, в большей степени, алгоритмы симметричного шифрования, так как хозяин информации будет хранить у себя единственный ключ. Алгоритмы класса M/S предполагают наличие множества клиентов, шифрующих данные для единственного получателя. Так, например, устроена система шифрованной электронной почты. Стоит отметить, что алгоритмы этого класса можно тривиальным образом превратить в S/S алгоритмы, если читающий клиент не будет распространять открытый ключ[1].
В обзорной статье 2016-го года[1] приводятся статистика наличия исследований в различных классах 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 |
Алгоритм Song-Wagner-Perrig был предложен в статье 2000-го года и является разновидностью симметричного шифрования с поиском[5]. Он работает за линейное от размеров шифруемых данных время и использует фундаментальные криптографические примитивы, что делает его удобным для рассмотрения[5].
Основную идею можно рассмотреть на следующем примере, где обеспечивается только возможность поиска в ущерб некоторой приватности.
Пусть пользователь Алиса хочет зашифровать документ из слов . Её цель — произвести обратимую операцию XOR над каждым из слов с каким-то секретным значением[5].
Для этого ей понадобятся[5]:
Алгоритм шифрования[5]:
При этом последовательность ключей может быть выбрана разными способами (например, использовать один и тот же ключ или какой-то набор ключей)[5].
Так построенная схема позволяет проводить поиск по шифротексту следующим образом[5]:
Пусть зашифрованный документ Алисы хранится у Боба. Алиса хочет отыскать слово W, поэтому отправляет его вместе с набором ключей к таким позициям i, где может находиться W. Тогда Боб проверяет, представима ли сумма по модулю очередного шифрослова с образцом в виде[5]:
Если такое условие выполняется, то Алисе возвращается подтверждение совпадения и позиция i. Если же для какой-то из позиций ключ не передавался, то Боб ничего не узнаёт об этом слове[5].
Такой алгоритм поиска имеет линейную сложность. Недостатками базовой схемы является то, что Боб знает содержимое запроса, и при успешном поиске узнаёт содержимое как самого документа, так и ключей, использованных при шифровании[5].
Чтобы повысить гибкость поиска и приватность шифрованных данных можно использовать дополнительный генератор для ключей с отдельным ключом для него. Тогда для каждого слова, и вместо раскрытия группы ключей, Алиса будет прикладывать к поисковому запросу только необходимый[5].
Чтобы Боб не получал доступ к открытым данным, их следует предварительно шифровать. То есть предварительно следует получить прешифрованный документ из , где . Стоит отметить, что шифрование E не должно зависеть от позиции слова (одинаковые слова в разных частях документа породят одинаковый шифротекст)[5].
Для поиска, Алиса отправляет Бобу зашифрованное слово и ключ к нему . Боб сможет осуществить поиск, не имея доступа к открытому тексту[5].
Однако в этой схеме проявляется новый недостаток. Из одного только шифротекста Алиса не сможет получить исходный текст, если она не знает, что там было. То есть ей необходимо знать (или, хотя бы, последние m бит) чтобы из восстановить [5].
Конечная форма алгоритма Сонг-Вагнера-Перрига выглядит следующим образом[5]:
Поиск на стороне Боба происходит как описано ранее, используя [5].
В этой схеме Алиса (или кто-либо ещё) может расшифровать данные, имея ключи и и зная положение слова i. Для этого[5]:
До закрытия Google Desktop предполагалось, что он будет ярким примером использования SSE[7].
Однако на текущий момент реализации алгоритмов (например, открытая реализация [1].
Searchable Encryption.