2.3.Компоненты алгоритма 2.3.1.Используемые криптопримитивы
Основой для функционирования схемы SSE является криптосистема с закрытым ключом, которая состоит из трех алгоритмов:  . Алгоритм  генерирует секретный ключ на основе некоторого параметра безопасности. Алгоритм  с помощью секретного ключа шифрует документ. В свою очередь алгоритм  расшифровывает полученное зашифрованное сообщение с помощью закрытого ключа. Выбор  является частным вопросом реализации, однако рекомендуется выбирать схему, которая соответствует нотации безопасности CPA-secure [24].
Кроме в SSE применяются псевдо случайные функции  . Каждая из этих функций принимает на вход битовую строку и возвращает определенную битовую последовательность некоторой длины:  . Псевдо-случайные функции используются в схеме в процессе шифрования индекса файловой коллекции.
2.3.2.Секретный ключ
Секретный ключ в схеме SSE представляет собой совокупность четырех элементов: три произвольные строки  и секретный ключ  . Ключ является криптографическим ключом, генерируемым с помощью алгоритма из набора  . используется для шифрования оригинальной файловой коллекции клиента, генерации токенов  и  и расшифровки полученных документов. Ключи используются для шифрования отдельных записей индекса, хранимого на сервере.
2.3.3.Зашифрованный индекс
Зашифрованный индекс – это структура, которая позволяет серверу производить поиск по хранящимся на нем документам в зашифрованном виде, не зная, что они представляют собой. Зашифрованный индекс основан на инвертированном индексе [4], который представляет собой структуру данных, где каждому отдельному слову ставится в соответствие документы, в которых оно содержится. В схеме SSE зашифрованный индекс представляет собой совокупность четырех структур данных: поисковый массив, поисковая таблица, массив удаления и таблица удаления.
Поисковый массив и поисковая таблица используются для выполнения операции поиска по ключевому слову в зашифрованных данных. Массив удаления и таблица удаления используются для поддержки операций добавления и удаления файлов в зашифрованную коллекцию. Поисковый массив и массив удаления хранят элементы, каждый из которых представляет собой пару соответствия слово – файл. Таким образом, в этих двух структурах данных образуются парные узлы – ячейка в поисковом массиве и ячейка в массиве удаления, которые содержат данные об одной и той же паре слово-файл.
2.4.Работа алгоритма 2.4.1.Построение зашифрованного индекса
Построение зашифрованного индекса состоит из создания и заполнения каждого из его четырех элементов: поисковый массив, поисковая таблица, массив удаления и таблица удаления.
Построение поискового массива 
В основе поискового массива лежит обратный индекс, вычисляемый предварительно. Для каждого слова  , где  – множество слов, содержащихся в файловой коллекции, создается список узлов  . Узлы представляют собой список файлов, содержащих слово  . Каждый узел, в свою очередь, представляет собой пару файл-слово и записывается в ячейку , выбранную случайным образом. Каждый узел хранит следующую информацию:
где  – уникальный идентификатор файла ,  – адрес следующего узла  в поисковом массиве , а  – генератор случайных чисел от ключа  и слова . В случае, если  является последним элементом списка ,  .
Построение поисковой таблицы 
Каждый список узлов имеет соответствующую запись в поисковой таблице :
где  – генератор случайных чисел от ключа  и слова ,  – адрес первого узла списка в ,  - адрес соответствующего парного узла в массиве удаления  , а  – генератор случайных чисел от ключа  и слова . Таким образом, хранит ссылку на первый элемент списка , а первый элемент, в свою очередь, содержит адрес на следующий элемент. Таким образом, прочитав запись в поисковой таблице, обладая ключами , и , можно получить доступ ко всем узлам .
Построение массива удаления
Также как и поисковый массив , массив удаления состоит из элементов, представляющих собой соответствие файл-слово. Отличие заключается в том, что список узлов файл-слово строится для каждого файла. Иными словами, для каждого файла  строится список узлов  , где  – число уникальных неповторяющихся слов в файле . Каждый узел  содержит в себе следующую информацию:
 ,
где  – адрес следующего узла  в ,  – адрес предыдущего узла  в ,  – адрес следующего узла в ,  – адрес парного узла в ,  – адрес узла в , предшествующего парному узлу в ,  – адрес узла в , следующего после парного узла в , – генератор случайных чисел от ключа и слова ,  – генератор случайных чисел от ключа и слова .
Построение таблицы удаления
Каждый список узлов имеет соответствующую запись в таблице удаления  :
Аналогично поисковой таблице , хранит ссылку на первый элемент списка , а первый элемент, в свою очередь, содержит адрес на следующий элемент. Таким образом, получив запись в таблице удаления, обладая ключами , и , можно прочитать все узлы списка .
Запись свободных ячеек
Когда запись данных о содержании файлов завершена, в зашифрованный индекс добавляется незашифрованная информация об оставшихся пустых элементах поискового и массива удаления. Данные свободные ячейки в дальнейшем используются для записи данных о добавленных файлах. Кроме того, после удаления файла ячейки, ранее занятые данными о нем, освобождаются и становятся доступными для записи новых данных.
Данные о свободных ячейках заносятся в и . В заносится незашифрованный список  , каждый элемент которого содержит информацию о следующей ячейке в списке и об адресе в парного свободного узла:
В заносятся данные о первом элементе списка свободных ячеек  :
После того, как элементы зашифрованного массива сформированы, оставшиеся свободные ячейки и заполняются случайными строками. Вместе с вышеописанными действиями с помощью шифруются оригинальные файлы.
2.4.2.Поиск по ключевому слову
Когда клиент хочет отправить поисковый запрос со словом , он формирует поисковый токен  . Поисковый токен состоит из трех элементов:  . Затем токен отправляется серверу.
Сервер получает , разделяет его на  . С помощью  в поисковой таблице находится запись о слове . Если такой не обнаружено, то сервер возвращает пустой список, что означает, что искомого слова нет в коллекции. Далее, вычисляя  , сервер получает номер первой ячейки списка узлов для слова в поисковом массиве. Обращаясь к искомой ячейке, сервер прочитывает из нее идентификатор файла, и идет к следующей ячейке, повторяя до тех пор, пока не дойдет до конца списка узлов . Отдельную запись ячейки поискового массива сервер расшифровывает, вычисляя  , где  – зашифрованная запись поискового массива.
2.4.3.Добавление файла в коллекцию
Генерация токена для добавления
Для добавления файла , который содержит множество уникальных слов  , в коллекцию зашифрованных файлов пользователь генерирует токен для добавления . Токен для добавления файла содержит следующие данные:
где  и  – генераторы случайных чисел от ключей и и файла , а  содержит информацию об -м уникальном слове в (Номер формулы).
где  ,  и  – генераторы случайных чисел от ключей , и и слова  ,  – уникальный идентификатор добавляемого файла и – генераторы случайных чисел от ключа и добавляемого файла .
После генерации токена клиент шифрует добавляемый файл и отправляет его серверу вместе с .
Добавление файла
Получив токен для добавления, сервер разделяет его на составляющие:
Далее для каждого  сервер производит следующие действия:
С помощью поисковой таблицы вычисляет парный узел ( и  ) для первого свободного элемент в поисковом массиве :
Обновляет ссылку в поисковой таблице на следующий свободный узел:
Находит ссылку на  для слова :
Записывает новый элемент в , соответствующий слову и добавляемому файлу :
Обновляет поисковую таблицу:
Обновляет парный узел :
Обновляет парный узел нового записанного элемента:
Если  , то обновляет таблицу удаления:
Далее сервер добавляет зашифрованный файл в коллекцию файлов, хранимую на сервере.
2.4.4.Удаление файла из коллекции
Генерация токена для удаления
Для удаления файла из коллекции файлов, хранимой на сервере, пользователь генерирует токен для удаления :
где , и – генераторы случайных чисел на основе удаляемого файла и ключей , и , а  – уникальный идентификатор файла .
Удаление файла
Получив токен для удаления, сервер разделяет его на составляющие:
Далее сервер ищет первый элемент списка :
Далее для каждого сервер производит следующие действия:
Расшифровывает элемент :
Удаляет , присваивая случайную строку элементу  .
Находит адрес первого свободного узла :
Обновляет поисковую таблицу :
Делает ячейку парного узла свободной:
 – узел, предшествующий парному узлу . Сервер обновляет указатель узла на следующий элемент в :
 – узел, следующий за парным узлом . Сервер обновляет указатель узла на предыдущий элемент в :
Присваивает 
Далее сервер удаляет из своего хранилища зашифрованный файл, который соответствует  , полученному из токена, и удаляет из .
|
