Русская Википедия:Searchable Encryption

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шифрование с возможностью поиска (Шаблон:Lang-en или SE) — класс криптографических алгоритмов шифрования, в которых существует возможность осуществлять поиск по зашифрованным данным (файлам, записям базы данных и т. д.). Областью применения является предоставление приватности данных, хранимых на недоверенном удалённом ресурсе[1].

В общем случае, в основе такого шифрования могут лежать как симметричные, так и асимметричные шифры. Однако, так как практические задачи предполагают шифрование большого количества данных, чаще встречается использование симметричного шифрования с поиском (соответственно, Шаблон:Lang-en или сокращённо SSE). Большинство асимметричных подходов основаны на шифровании по открытому ключу с поиском по ключевым словам (Шаблон:Lang-en, сокращённо PEKS)[1].

История

Идея поиска по шифротексту стала актуальна на фоне введения облачных хранилищ данных. Данные пользователей хранятся на удалённых ресурсах, которые могут быть недоверенными (или «полудоверенными», Шаблон:Lang-en[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].

Базовая идея

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

Пусть пользователь Алиса хочет зашифровать документ из слов <math display="inline">W_1, W_2, ..., W_l</math>. Её цель — произвести обратимую операцию XOR над каждым из слов с каким-то секретным значением[5].

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

  • псевдослучайная функция F с ключами <math display="inline">k_i</math>, необходимая для расширения элементов последовательности S до длины слов (возвращает m-битные значения)
  • псевдослучайная функция f с ключом <math display="inline">k'</math>, для генерации ключей <math display="inline">k_i</math>

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

  1. Сначала Алиса генерирует последовательность <math display="inline">S_1, S_2, ..., S_l</math>.
  2. Чтобы зашифровать очередное слово <math display="inline">W_i</math> длины n бит, расположенное на позиции i, генерируется <math display="inline">S_i</math> длины n-m бит.
  3. Вычисляется <math display="inline">T_i</math> как конкатенация <math display="inline">S_i</math> и <math display="inline">F_{k_i}(S_i)</math>
    <math display="inline">T_i = <S_i, F_{k_i}(S_i)></math>.
  4. Результатом шифрования будет <math display="inline">C_i = W_i + T_i</math>.

При этом последовательность ключей <math display="inline">k_i</math> может быть выбрана разными способами (например, использовать один и тот же ключ или какой-то набор ключей)[5].

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

Пусть зашифрованный документ Алисы хранится у Боба. Алиса хочет отыскать слово W, поэтому отправляет его вместе с набором ключей <math display="inline">k_i</math> к таким позициям i, где может находиться W. Тогда Боб проверяет, представима ли сумма по модулю очередного шифрослова с образцом в виде[5]:

<math display="inline">C_i + W = <s,F_{k_i}(s)></math>

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

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

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

Чтобы повысить гибкость поиска и приватность шифрованных данных можно использовать дополнительный генератор для ключей с отдельным ключом для него. Тогда <math display="inline">k_i = f_{k'}(W_i)</math> для каждого слова, и вместо раскрытия группы ключей, Алиса будет прикладывать к поисковому запросу только необходимый[5].

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

Чтобы Боб не получал доступ к открытым данным, их следует предварительно шифровать. То есть предварительно следует получить прешифрованный документ из <math display="inline">X_1, X_2, ..., X_l</math>, где <math display="inline">X_i = E_{k^s}(W_i)</math>. Стоит отметить, что шифрование E не должно зависеть от позиции слова (одинаковые слова в разных частях документа породят одинаковый шифротекст)[5].

Для поиска, Алиса отправляет Бобу зашифрованное слово <math display="inline">X=E_{k^s}(W)</math> и ключ к нему <math display="inline">k_i = f_{k'}(X_i)</math>. Боб сможет осуществить поиск, не имея доступа к открытому тексту[5].

Однако в этой схеме проявляется новый недостаток. Из одного только шифротекста Алиса не сможет получить исходный текст, если она не знает, что там было. То есть ей необходимо знать <math display="inline">E(W_i)</math> (или, хотя бы, последние m бит) чтобы из <math display="inline">C_i</math> восстановить <math display="inline">W_i</math>[5].

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

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

  1. Над словом <math display="inline">W_i</math> выполняется пре-шифрация: <math display="inline">X_i=E_{k^s}(W_i)</math>.
  2. <math display="inline">X_i</math> делится на две части — <math display="inline">L_i</math> длины n-m бит и <math display="inline">R_i</math> длины m бит.
  3. Из <math display="inline">L_i</math> генерируется ключ <math display="inline">k_i=f_{k'}(L_i)</math>.
  4. Генератором G с ключом k генерируется (n-m)-битный член последовательности <math display="inline">S_i</math>.
  5. <math display="inline">S_i</math> расширяется до n-битного <math display="inline">T_i=<S_i,F_{k_i}(S_i)></math>.
  6. Наконец шифротекст вычисляется как <math display="inline">C_i=T_i+X_i</math>.

Поиск на стороне Боба происходит как описано ранее, используя <math display="inline">(X,k_i)</math>[5].

В этой схеме Алиса (или кто-либо ещё) может расшифровать данные, имея ключи <math display="inline">k,k'</math> и <math display="inline">k^s</math> и зная положение слова i. Для этого[5]:

  1. Алиса получает при помощи зерна k элемент <math display="inline">S_i</math>.
  2. <math display="inline">L_i</math> считается сложением по модулю 2 старших n-m бит <math display="inline">C_i</math> c <math display="inline">S_i</math>.
  3. Восстанавливается <math display="inline">T_i=<S_i,F_{k_i}(S_i)></math>.
  4. Исходный текст находится как <math display="inline">W_i=E^{-1}_{k^s}(C_i+T_i)</math>.

Применение

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

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

Примечания

Шаблон:Примечания

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 1,2 1,3 1,4 1,5 1,6 Шаблон:Статья
  2. ↑ Шаблон:Книга
  3. ↑ Шаблон:Статья
  4. ↑ 4,0 4,1 4,2 Шаблон:Статья
  5. ↑ 5,00 5,01 5,02 5,03 5,04 5,05 5,06 5,07 5,08 5,09 5,10 5,11 5,12 5,13 5,14 5,15 5,16 5,17 5,18 Шаблон:Статья
  6. ↑ 6,0 6,1 Шаблон:Статья
  7. ↑ 7,0 7,1 7,2 Шаблон:Статья
  8. ↑ Шаблон:Статья
  9. ↑ Шаблон:Статья
  10. ↑ 10,0 10,1 Шаблон:Статья
  11. ↑ 11,0 11,1 Шаблон:Статья
  12. ↑ Шаблон:Статья
  13. ↑ Шаблон:Статья
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Searchable_Encryption&oldid=8803280