Searchable Encryption

Шифрование с возможностью поиска (англ. 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)
один пишущий/много читающих (S/M)
много пишущих/один читающий (M/S)
много пишущих/много читающих (M/M)

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

В обзорной статье 2016 года^[1] приводятся статистика наличия исследований в различных классах 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 года и является разновидностью симметричного шифрования с поиском^[5]. Он работает за линейное от размеров шифруемых данных время и использует фундаментальные криптографические примитивы, что делает его удобным для рассмотрения^[5].

Базовая идея[править | править код]

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

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

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

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

Алгоритм шифрования^[5]:

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

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

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

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

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

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

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

Скрытие ключей[править | править код]

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

Скрытие открытого текста[править | править код]

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

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

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

Окончательный вариант[править | править код]

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

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

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

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

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

Применение[править | править код]

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

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

Примечания[править | править код]

↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ Christoph Bösch, Pieter Hartel, Willem Jonker, Andreas Peter. A Survey of Provably Secure Searchable Encryption (Undefined) // ACM Computing Surveys. — 2014/08. — Т. 47, вып. 2. — С. 1–51. — ISSN 0360-0300. — doi:10.1145/2636328. Архивировано 12 августа 2017 года.
↑ Oded Goldreich. Foundations of Cryptography: Volume 2, Basic Applications. — Cambridge University Press, 2009-09-17. — 452 с. — ISBN 9781107393974. Архивировано 25 декабря 2017 года.
↑ Md Iftekhar Salam, Wei-Chuen Yau, Ji-Jian Chin, Swee-Huay Heng, Huo-Chong Ling. Implementation of searchable symmetric encryption for privacy-preserving keyword search on cloud storage // Human-centric Computing and Information Sciences. — 2015-07-17. — Т. 5. — С. 19. — ISSN 2192-1962. — doi:10.1186/s13673-015-0039-9.
↑ ¹ ² ³ Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano. Public Key Encryption with Keyword Search (англ.) // Advances in Cryptology - EUROCRYPT 2004. — Springer, Berlin, Heidelberg, 2004-05-02. — P. 506–522. — ISBN 9783540219354, 9783540246763. — doi:10.1007/978-3-540-24676-3_30. Архивировано 22 декабря 2017 года.
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² ¹³ ¹⁴ ¹⁵ ¹⁶ ¹⁷ ¹⁸ ¹⁹ Dawn Xiaoding Song, D. Wagner, A. Perrig. Practical techniques for searches on encrypted data // Proceeding 2000 IEEE Symposium on Security and Privacy. S P 2000. — 2000. — С. 44–55. — doi:10.1109/secpri.2000.848445. Архивировано 19 октября 2016 года.
↑ ¹ ² Eu-Jin Goh. Secure Indexes. — 2003. — № 216. Архивировано 24 декабря 2017 года.
↑ ¹ ² ³ Reza Curtmola, Juan Garay, Seny Kamara, Rafail Ostrovsky. Searchable symmetric encryption: Improved definitions and efficient constructions (англ.) // Journal of Computer Security. — 2011-01-01. — Vol. 19, iss. 5. — P. 895–934. — ISSN 0926-227X. — doi:10.3233/jcs-2011-0426.
↑ Seny Kamara, Charalampos Papamanthou, Tom Roeder. Dynamic Searchable Symmetric Encryption // Proceedings of the 2012 ACM Conference on Computer and Communications Security. — New York, NY, USA: ACM, 2012. — С. 965–976. — ISBN 9781450316514. — doi:10.1145/2382196.2382298.
↑ David Cash, Stanislaw Jarecki, Charanjit Jutla, Hugo Krawczyk, Marcel-Cătălin Roşu. Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries (англ.) // Advances in Cryptology – CRYPTO 2013. — Springer, Berlin, Heidelberg, 2013. — P. 353–373. — ISBN 9783642400407, 9783642400414. — doi:10.1007/978-3-642-40041-4_20. Архивировано 22 декабря 2017 года.
↑ ¹ ² Emily Shen, Elaine Shi, Brent Waters. Predicate Privacy in Encryption Systems (англ.) // Theory of Cryptography. — Springer, Berlin, Heidelberg, 2009-03-15. — P. 457–473. — ISBN 9783642004568, 9783642004575. — doi:10.1007/978-3-642-00457-5_27. Архивировано 24 декабря 2017 года.
↑ ¹ ² Raphael Bost. ∑OφOς: Forward Secure Searchable Encryption // Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. — New York, NY, USA: ACM, 2016. — С. 1143–1154. — ISBN 9781450341394. — doi:10.1145/2976749.2978303.
↑ Muhammad Naveed. The Fallacy of Composition of Oblivious RAM and Searchable Encryption. — 2015. — № 668. Архивировано 22 декабря 2017 года.
↑ Mihir Bellare, Alexandra Boldyreva, Adam O'Neill. Deterministic and Efficiently Searchable Encryption. — 2006. — № 186. Архивировано 23 декабря 2017 года.

[:3-1] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ Christoph Bösch, Pieter Hartel, Willem Jonker, Andreas Peter. A Survey of Provably Secure Searchable Encryption (Undefined) // ACM Computing Surveys. — 2014/08. — Т. 47, вып. 2. — С. 1–51. — ISSN 0360-0300. — doi:10.1145/2636328. Архивировано 12 августа 2017 года.

[2] Oded Goldreich. Foundations of Cryptography: Volume 2, Basic Applications. — Cambridge University Press, 2009-09-17. — 452 с. — ISBN 9781107393974. Архивировано 25 декабря 2017 года.

[3] Md Iftekhar Salam, Wei-Chuen Yau, Ji-Jian Chin, Swee-Huay Heng, Huo-Chong Ling. Implementation of searchable symmetric encryption for privacy-preserving keyword search on cloud storage // Human-centric Computing and Information Sciences. — 2015-07-17. — Т. 5. — С. 19. — ISSN 2192-1962. — doi:10.1186/s13673-015-0039-9.

[:0-4] ¹ ² ³ Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano. Public Key Encryption with Keyword Search (англ.) // Advances in Cryptology - EUROCRYPT 2004. — Springer, Berlin, Heidelberg, 2004-05-02. — P. 506–522. — ISBN 9783540219354, 9783540246763. — doi:10.1007/978-3-540-24676-3_30. Архивировано 22 декабря 2017 года.

[:1-5] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² ¹³ ¹⁴ ¹⁵ ¹⁶ ¹⁷ ¹⁸ ¹⁹ Dawn Xiaoding Song, D. Wagner, A. Perrig. Practical techniques for searches on encrypted data // Proceeding 2000 IEEE Symposium on Security and Privacy. S P 2000. — 2000. — С. 44–55. — doi:10.1109/secpri.2000.848445. Архивировано 19 октября 2016 года.

[:4-6] ¹ ² Eu-Jin Goh. Secure Indexes. — 2003. — № 216. Архивировано 24 декабря 2017 года.

[:2-7] ¹ ² ³ Reza Curtmola, Juan Garay, Seny Kamara, Rafail Ostrovsky. Searchable symmetric encryption: Improved definitions and efficient constructions (англ.) // Journal of Computer Security. — 2011-01-01. — Vol. 19, iss. 5. — P. 895–934. — ISSN 0926-227X. — doi:10.3233/jcs-2011-0426.

[8] Seny Kamara, Charalampos Papamanthou, Tom Roeder. Dynamic Searchable Symmetric Encryption // Proceedings of the 2012 ACM Conference on Computer and Communications Security. — New York, NY, USA: ACM, 2012. — С. 965–976. — ISBN 9781450316514. — doi:10.1145/2382196.2382298.

[9] David Cash, Stanislaw Jarecki, Charanjit Jutla, Hugo Krawczyk, Marcel-Cătălin Roşu. Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries (англ.) // Advances in Cryptology – CRYPTO 2013. — Springer, Berlin, Heidelberg, 2013. — P. 353–373. — ISBN 9783642400407, 9783642400414. — doi:10.1007/978-3-642-40041-4_20. Архивировано 22 декабря 2017 года.

[:5-10] ¹ ² Emily Shen, Elaine Shi, Brent Waters. Predicate Privacy in Encryption Systems (англ.) // Theory of Cryptography. — Springer, Berlin, Heidelberg, 2009-03-15. — P. 457–473. — ISBN 9783642004568, 9783642004575. — doi:10.1007/978-3-642-00457-5_27. Архивировано 24 декабря 2017 года.

[:6-11] ¹ ² Raphael Bost. ∑OφOς: Forward Secure Searchable Encryption // Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. — New York, NY, USA: ACM, 2016. — С. 1143–1154. — ISBN 9781450341394. — doi:10.1145/2976749.2978303.

[12] Muhammad Naveed. The Fallacy of Composition of Oblivious RAM and Searchable Encryption. — 2015. — № 668. Архивировано 22 декабря 2017 года.

[13] Mihir Bellare, Alexandra Boldyreva, Adam O'Neill. Deterministic and Efficiently Searchable Encryption. — 2006. — № 186. Архивировано 23 декабря 2017 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]