Русская Википедия:Алгоритм слепого индексирования
Алгоритм слепого индексирования — подраздел методов шифрования, позволяющих с помощью слепого индекса выполнять поиск по зашифрованным данным (файлам, документам и т. д.), не расшифровывая их.
Слепой индекс (Шаблон:Lang-en) — структура данных, которая хранится вместе с набором документов и поддерживает эффективный поиск по ключевым словам. То есть при наличии ключевого слова индекс возвращает указатель на документы, которые содержат это ключевое слово.[1]
Происхождение
Идея индексного «ослепления» пришла Ян-Ченг Чангу и Шаблон:Iw при исследовании модели Ind-cka. Модель описывает интуитивное предположение, что злоумышленник не может получить никакой информации из индексов, кроме как результаты предыдущих запросов. Суть модели заключается в том, что если есть документ <math>D</math>, содержащий <math>n</math> слов, из которых <math>m</math> штук уже знает злоумышленник, а множество оставшихся слов <math>n-m</math> задается <math>W</math>[2]. То в этом случае противник не сможет взломать оставшуюся часть документа, хоть и знает все пары индекс-документ и может получить значение односторонней функции с потайным входом всех известных ему слов. Для обеспечения такой безопасности, два зашифрованных документа одинакового размера должны иметь индексы, содержащие одинаковое количество ключевых слов. Чанг и Митценмахер расширили методы модели Ind-cka, создав собственную Ind2-ckamodel. Теперь она более безопасна, может обрабатывать слова переменной длины, но имеет ряд недостатков:
- Она вычислительно менее эффективна. Когда алгоритм построения индекса z-ind требует <math>O(n)</math> времени, их схема строится <math>3n+2^{d+1}</math>, где <math>2^d</math> — размер словаря. (Для многих шифров <math>2^d\gg n</math>)
- Неспособность обрабатывать произвольные обновления: их схемы используют предварительно построенные словари, где размер и содержание словаря фиксируются, когда словарь и индексы создаются для набора документов. Поскольку трудно предвидеть все возможные слова, которые должны быть проиндексированы, справедливо сказать, что их схемы не могут эффективно обрабатывать произвольные обновления.
- Относительно большие индексы фиксированного размера: независимо от размера документа, их индексы должны быть длиной <math>2^d</math> бит. Для небольших документов их индекс может быть во много раз больше, чем документ.[3]
Общая модель применения
Изначально есть база данных <math>DB = (M_1, ..., M_n)</math>, состоящая из <math>n</math> файлов, некоторые данные <math>W = (w_1,...,w_n)</math>. Из них извлекаются ключевые слова <math>w_j</math> и шифруются под действием ключа <math>K</math> клиента с помощью алгоритма <math>BuildIndex</math>. Часто требуется зашифровать и документ, но уже под действием ключа <math>K'\neq K</math>. В данном описании алгоритм шифровки документа обозначается <math>Enc</math>. Тогда база данных примет вид:
<math>I = BuildIndex_K(DB = (M_1,...,M_n), W = (w_1,...,w_n)); C=Enc_{K'}(M_1,...,M_n).</math>
Для самого поиска клиент создает функцию одностороннюю функцию с потайным входом <math>T = Trapdoor_K(f)</math>, где <math>f</math> — предикат для <math>w_j</math>. Используя <math>T</math> сервер может выполнить поиск по индексу алгоритмом <math>Search</math> и вернуть клиенту те документы, в которых содержится зашифрованное слово[3].
Безопасность
Любая схема шифрования с возможностью поиска имеет утечку информации, которая делится на 3 группы: метаданных слепого индекса, шаблона поиска и шаблона доступа. Где метаданными слепого индекса называется информация о ключевых словах, содержащихся в слепом индексе. Утечка происходит из сохраненного шифротекста или слепого индекса. Эта информация может включать в себя количество ключевых слов, содержащихся в каждом документе, длину и количество документов. Чтобы уменьшить вероятность утечки и увеличить криптостойкость системы, часто используется подход усеченного слепого индекса. В таком случае индекс урезается до заданного числа битов, и может быть рассмотрен в качестве фильтра Блума. Тогда вместо точного ответа на запрос, содержится ли какое-то слово в файле, клиент будет получать вероятность вхождения слова в файл. Важной особенностью этого фильтра является отсутствие ложноотрицательных срабатываний. Фильтр Блума может утверждать, что элемент является частью набора, когда он не был вставлен, но никогда не сообщит о том, что вставленный элемент отсутствует в наборе.
Но даже в таком случае возможна утечка данных. Поэтому важно знать точную формулу определения безопасной верхней границы объёма информации, которая может безопасно утечь, не раскрывая повторяющиеся открытые тексты: <math>C = R / 2^{-s}</math>,
где <math>S = \textstyle \sum_{0}^n \displaystyle min (L_i, K_i),</math> <math>n</math> — число слепых индексов, <math>L_i</math> — длина слепого индекса (в битах), <math>K_i</math> — длина ключа (в битах), <math>R </math> — ряд зашифрованных файлов, которые используют эти слепые индексы.
Параметры должны быть подобраны так, чтобы <math>2\leqslant C < \surd R </math>. Если <math>C < 2 </math>, то злоумышленник сможет сделать выводы, что некоторые тексты идентичны, что нарушает стандартное понятие безопасной схемы. В противном случае, если <math>C>\surd R </math>, то будет случаться слишком много коллизий, что сильно повлияет на производительность алгоритма.[4]
Пример (Acra Searchable Encryption)
В современном мире большинство эффективных схем SE имеют одну общую проблему. У них есть утечка шаблона поиска, который показывает, были ли выполнены 2 поисковых запроса для одного и того же ключевого слова. Подвергая себя дополнительному риску быть вскрытыми статистическим анализом (то есть злоумышленник узнает о ключевых словах открытого текста). Acra Database Security Suite решает эту проблему, используя метод слепого индексирования. Так же для увеличения безопасности алгоритма Acra использует усечение слепого индекса, что приводит ложным срабатываниям и к коллизиям. Тогда вводится AcraServer (расположенный между клиентом и базой данных), фильтрующий нерелеватные записи из ответа, и приложение получает только соответствующие расшифрованные данные.[4]
Примечания
Ссылки
