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

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

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

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

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

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

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

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

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

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

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

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

• Acra Database Security Suite