Алгоритм слепого индексирования

Алгоритм слепого индексирования — подраздел методов шифрования, позволяющих с помощью слепого индекса выполнять поиск по зашифрованным данным (файлам, документам и т. д.), не расшифровывая их.

Слепой индекс (англ. Blind index) — структура данных, которая хранится вместе с набором документов и поддерживает эффективный поиск по ключевым словам. То есть при наличии ключевого слова индекс возвращает указатель на документы, которые содержат это ключевое слово.

Происхождение

Идея индексного «ослепления» пришла Ян-Ченг Чангу и Михаэлю Митценмахеру при исследовании модели Ind-cka. Модель описывает интуитивное предположение, что злоумышленник не может получить никакой информации из индексов, кроме как результаты предыдущих запросов. Суть модели заключается в том, что если есть документ $D$, содержащий $n$ слов, из которых $m$ штук уже знает злоумышленник, а множество оставшихся слов $n-m$ задается $W$. То в этом случае противник не сможет взломать оставшуюся часть документа, хоть и знает все пары индекс-документ и может получить значение односторонней функции с потайным входом всех известных ему слов. Для обеспечения такой безопасности, два зашифрованных документа одинакового размера должны иметь индексы, содержащие одинаковое количество ключевых слов. Чанг и Митценмахер расширили методы модели Ind-cka, создав собственную Ind2-ckamodel. Теперь она более безопасна, может обрабатывать слова переменной длины, но имеет ряд недостатков:

1. Она вычислительно менее эффективна. Когда алгоритм построения индекса z-ind требует $O(n)$ времени, их схема строится $3n+2^{d+1}$, где $2^{d}$ — размер словаря. (Для многих шифров $2^{d}\gg n$)
2. Неспособность обрабатывать произвольные обновления: их схемы используют предварительно построенные словари, где размер и содержание словаря фиксируются, когда словарь и индексы создаются для набора документов. Поскольку трудно предвидеть все возможные слова, которые должны быть проиндексированы, справедливо сказать, что их схемы не могут эффективно обрабатывать произвольные обновления.
3. Относительно большие индексы фиксированного размера: независимо от размера документа, их индексы должны быть длиной $2^{d}$ бит. Для небольших документов их индекс может быть во много раз больше, чем документ.

Общая модель применения

Изначально есть база данных $DB=(M_{1},...,M_{n})$, состоящая из $n$ файлов, некоторые данные $W=(w_{1},...,w_{n})$. Из них извлекаются ключевые слова $w_{j}$ и шифруются под действием ключа $K$ клиента с помощью алгоритма $BuildIndex$. Часто требуется зашифровать и документ, но уже под действием ключа $K'\neq K$. В данном описании алгоритм шифровки документа обозначается $Enc$. Тогда база данных примет вид:

$I=BuildIndex_{K}(DB=(M_{1},...,M_{n}),W=(w_{1},...,w_{n}));C=Enc_{K'}(M_{1},...,M_{n}).$

Общая модель схемы шифрования на основе слепого индекса

Для самого поиска клиент создает функцию одностороннюю функцию с потайным входом $T=Trapdoor_{K}(f)$, где $f$ — предикат для $w_{j}$. Используя $T$ сервер может выполнить поиск по индексу алгоритмом $Search$ и вернуть клиенту те документы, в которых содержится зашифрованное слово.

Безопасность

Любая схема шифрования с возможностью поиска имеет утечку информации, которая делится на 3 группы: метаданных слепого индекса, шаблона поиска и шаблона доступа. Где метаданными слепого индекса называется информация о ключевых словах, содержащихся в слепом индексе. Утечка происходит из сохраненного шифротекста или слепого индекса. Эта информация может включать в себя количество ключевых слов, содержащихся в каждом документе, длину и количество документов. Чтобы уменьшить вероятность утечки и увеличить криптостойкость системы, часто используется подход усеченного слепого индекса. В таком случае индекс урезается до заданного числа битов, и может быть рассмотрен в качестве фильтра Блума. Тогда вместо точного ответа на запрос, содержится ли какое-то слово в файле, клиент будет получать вероятность вхождения слова в файл. Важной особенностью этого фильтра является отсутствие ложноотрицательных срабатываний. Фильтр Блума может утверждать, что элемент является частью набора, когда он не был вставлен, но никогда не сообщит о том, что вставленный элемент отсутствует в наборе.

Но даже в таком случае возможна утечка данных. Поэтому важно знать точную формулу определения безопасной верхней границы объёма информации, которая может безопасно утечь, не раскрывая повторяющиеся открытые тексты: $C=R/2^{-s}$,

где $S=\textstyle \sum _{0}^{n}\displaystyle min(L_{i},K_{i}),$ $n$ — число слепых индексов, $L_{i}$ — длина слепого индекса (в битах), $K_{i}$ — длина ключа (в битах), $R$ — ряд зашифрованных файлов, которые используют эти слепые индексы.

Параметры должны быть подобраны так, чтобы $2\leqslant C<\surd R$. Если $C<2$, то злоумышленник сможет сделать выводы, что некоторые тексты идентичны, что нарушает стандартное понятие безопасной схемы. В противном случае, если $C>\surd R$, то будет случаться слишком много коллизий, что сильно повлияет на производительность алгоритма.

Пример (Acra Searchable Encryption)

В современном мире большинство эффективных схем SE имеют одну общую проблему. У них есть утечка шаблона поиска, который показывает, были ли выполнены 2 поисковых запроса для одного и того же ключевого слова. Подвергая себя дополнительному риску быть вскрытыми статистическим анализом (то есть злоумышленник узнает о ключевых словах открытого текста). Acra Database Security Suite решает эту проблему, используя метод слепого индексирования. Так же для увеличения безопасности алгоритма Acra использует усечение слепого индекса, что приводит ложным срабатываниям и к коллизиям. Тогда вводится AcraServer (расположенный между клиентом и базой данных), фильтрующий нерелеватные записи из ответа, и приложение получает только соответствующие расшифрованные данные.

Ссылки

• Acra Database Security Suite