Схемы инкрементального шифрования
Предлагаемые решения используют стойкую схему вероятностного шифрования E [GM] (см. также приложение). Предположим, что Е может использоваться для шифрования символов из S
и пар (i,d), где dÎS и i - целое число не большее, чем длина блоков данных в системе. При использовании Е
сначала будет описан алгоритм, который шифрует версии блоков данных, в которых осуществляется операции замены. Далее будем рассматривать операцию замены одного символа. Шифрованные версии состоят из двух последовательностей шифртекстов, обозначаемых Е1
и Е2. Первая последовательность Е1
является результатом блочного шифрования некоторого файла D=D[1]...D[l], в то время как вторая Е2, шифрует последовательность изменений, обозначаемую M=М[1]...M[t] , посредством которых текущий документ был получен из D. Тогда инкрементальный алгоритм шифрования заключается в конкатенации шифртекста модифицированного документа с Е2. Каждые l шагов алгоритм восстанавливает модифицированные данные и заново шифрует их, используя блочное шифрование и, таким образом, формирует новую последовательность шифртекстов Е1
(одновременно устанавливая Е2
в нулевую последовательность). Сложность этого алгоритма составляет два блочных шифрования на каждое изменение. Важным моментом является то, что конвейерная обработка является достаточно ресурсозатратной.
Теперь предположим, что нам позволено сохранять промежуточные результаты работы в некоторой безопасной памяти («невидимой противником»). В этом случае, как только длина Е2
достигнет l, мы можем начать подготовку новых шифртекстов для данных, обозначаемых D', которые получаются D применением первых l изменений в М. Для этого необходимо выполнить все требуемые вычисления наряду со следующими l
изменениями, в то время как М
увеличивается до размера 2l. Таким образом, мы имеем шифртекст, обозначаемый Е' данных D'
(конечно, теперь текущие данные другие).
При замене Е1 на Е'
и при исключении первых l
изменений в М мы получаем зашифрованную форму текущего документа. Следует подчеркнуть, что в такой модели вычислений все эти операции могут выполняться за константное временя. Наконец необходимо отметить, что алгоритм работает в периодах, каждый состоящий из l
изменений. В каждом периоде, алгоритм модифицирует шифртекст для сравнения с изменениями, выполненными в предыдущем периоде.
Выше мы предположили, что пользователь может хранить промежуточные результаты (которые требуют памяти размером О(l)) в локальной памяти, невидимой противником. Это предположение нереалистично в некоторых сценариях и несовместимо с вышеприведенными определениями для схем инкрементального шифрования. Далее мы используем вышеупомянутые идеи без этого предположения (идеи берутся из [GO,O], см. предыдущую главу). Для этого нам необходимо шифровать данные, используя три последовательности, обозначаемые Е1,Е2 и Е3. Первые две последовательности Е1
и Е2, является точно такими же, как определенные выше. Их достаточно для дешифрования данных. Дополнительная последовательность Е3
– является «шифрованием рабочей области» и обозначается как W=W[1]...W[2l].
Далее мы опишем операции, выполняемые в одном периоде. В нашем описании, мы не упоминаем явно операции шифрования, и, таким образом, всякий раз, когда мы говорим, что мы устанавливаем элемент последовательности W, это должно означать, что соответствующий шифртекст получен и сохранен.
Сначала, мы устанавливаем элементы последовательности W следующим образом: W[i]:=(i+D[i]) для i£l и W[i]:=M[i-l] для l+1£i£2l. Здесь мы предполагаем, что записи изменений имеют форму (i,d), где i – номер ячейки памяти и d
символ, который размещен в этой ячейке. Затем, мы сортируем пары из W по их левым элементам в соответствии с так называемыми ключами сортировки
так, что, если два ключа сортировки равны, тогда соответствующие пары хранятся упорядоченными.
Определяющим является то, что сортировка выполняется посредством использования эффективной сети сортировки такой, например, как сеть сортировки Батчера [BGG]. Следует подчеркнуть, что всякий раз, когда две пары сравниваются и переставляются (или нет), тогда они заново шифруются посредством Е
(так что противник не может «понять» были ли они переставлены или нет). Это гарантирует то, что вся процедура сортировки не дает никакой информация противнику. Как только сортировка завершена, алгоритм просматривает W для нахождения всех мест нахождения элементов с одним и тем же ключом сортировки и сохраняет последнее (которое является новым), в большом фиктивном значении (l+1,...). Теперь, мы посредством ключа сортировки заново сортируем пары из W и получаем последовательность, в которой первые l
элементов содержат модифицированный документ D'. В заключение, мы устанавливаем Е1 для хранения в ней зашифрованного блока данных D' и исключаем первые l элементов последовательности Е2.
При использовании AKS-сети сортировки [BGG] вышеприведенная реализация инкрементального алгоритма шифрования требует O(llog l) шагов (в то время как, если мы используем сеть Батчера, то получаем сумму из О(l)+(llоg2l) шагов). Эти шаги могут быть распределены равномерно среди l операций модификации, обеспечивающих желаемую сложность.
Как было упомянуто выше, каждый из рассматриваемых алгоритмов можно адаптировать для реализации схемы инкрементального шифрования для операций вставки/удаления (единственного символа), которая является эффективной в строгом смысле. Для этого длина открытых данных устанавливается в некоторых предопределенных пределах (например, между l/2 и 2l). А именно, схема инкрементального шифрования состоит из трех последовательностей Е1, Е2 и Е3, где Е1 и Е2 – определены выше, а Е3 - шифрование рабочей области для некоторого забывающего моделирующего устройства (см. предыдущую главу).Также как и как выше, алгоритм работает в периодах, состоящих из l изменений каждый. В каждом периоде, инкрементальный алгоритм выполняет l
изменений предыдущего периода. Это делается посредством моделирования RAM-программы, которая содержит структуру данных, обеспечивающую эффективное выполнение операций вставки/удаления, например, 2-3-дерево.
