2. Инкрементальное шифрование Вводные замечания

Будем говорить, что инкрементальное шифрование является стойким относительно некоторой операции модификации, если (для данной последовательности шифртекстовЕ₁,...,E_tнад соответствующими открытыми даннымиD_i,i=1,...,tи при инкрементальном получении каждой последовательностиЕ_i, из предыдущих шифртекстовE_i-1) извлечение какой-либо информации об оригинальном документеD₁, также как и его измененных версияхD₂,..,D_t(за исключением того факта, чтоD_iполучено посредством применения этой операции модификации к открытым даннымD_i-1)не возможно. Аналогично, рассмотрим любые две последовательностиА=(А₁,...,А_t) иВ=(В₁,...,B_t) так, чтоA₁,B₁^l, где- используемый алфавит. ДанныеА_i(отн.,В_i) получены заменой единственного символа вA_i-1(отн.,В_i-1). Тогда, не должны быть различимы последовательность шифртекстов, полученных посредством применения инкрементального алгоритмаIпри обработке «командой создания» блока данныхA₁и соответствующих «команд замены» в последовательностиА, от последовательности шифртекстов, полученных посредством применения инкрементального алгоритмаIпри обработке «команды создания» блока данныхВ₁и соответствующих «команд замены» данныхВ.

Схемы инкрементального шифрования

Предлагаемые решения используют стойкую схему вероятностного шифрования E[GM] (см. также приложение). Предположим, чтоЕможет использоваться для шифрования символов изи пар (i,), гдеиi- целое число не большее, чем длина блоков данных в системе. При использованииЕсначала будет описан алгоритм, который шифрует версии блоков данных, в которых осуществляется операции замены. Далее будем рассматривать операцию замены одного символа. Шифрованные версии состоят из двух последовательностей шифртекстов, обозначаемыхЕ₁иЕ₂. Первая последовательностьЕ₁является результатом блочного шифрования некоторого файлаD=D[1]...D[l], в то время как втораяЕ₂, шифрует последовательность изменений, обозначаемуюM=М[1]...M[t] , посредством которых текущий документ был получен изD. Тогда инкрементальный алгоритм шифрования заключается в конкатенации шифртекста модифицированного документа сЕ₂. Каждыеlшагов алгоритм восстанавливает модифицированные данные и заново шифрует их, используя блочное шифрование и, таким образом, формирует новую последовательность шифртекстовЕ₁(одновременно устанавливаяЕ₂в нулевую последовательность). Сложность этого алгоритма составляет два блочных шифрования на каждое изменение. Важным моментом является то, что конвейерная обработка является достаточно ресурсозатратной.

Теперь предположим, что нам позволено сохранять промежуточные результаты работы в некоторой безопасной памяти («невидимой противником»). В этом случае, как только длина Е₂достигнетl, мы можем начать подготовку новых шифртекстов для данных, обозначаемыхD', которые получаютсяDприменением первыхlизменений вМ. Для этого необходимо выполнить все требуемые вычисления наряду со следующимиlизменениями, в то время какМувеличивается до размера 2l. Таким образом, мы имеем шифртекст, обозначаемыйЕ'данныхD'(конечно, теперь текущие данные другие). При заменеЕ₁наЕ'и при исключении первыхlизменений вМмы получаем зашифрованную форму текущего документа. Следует подчеркнуть, что в такой модели вычислений все эти операции могут выполняться за константное временя. Наконец необходимо отметить, что алгоритм работает впериодах, каждый состоящий изlизменений. В каждом периоде, алгоритм модифицирует шифртекст для сравнения с изменениями, выполненными в предыдущем периоде.

Выше мы предположили, что пользователь может хранить промежуточные результаты (которые требуют памяти размером О(l)) в локальной памяти, невидимой противником. Это предположение нереалистично в некоторых сценариях и несовместимо с вышеприведенными определениями для схем инкрементального шифрования. Далее мы используем вышеупомянутые идеи без этого предположения (идеи берутся из [GO,O], см. предыдущую главу). Для этого нам необходимо шифровать данные, используя три последовательности, обозначаемыеЕ₁,Е₂иЕ₃. Первые две последовательностиЕ₁иЕ₂, является точно такими же, как определенные выше. Их достаточно для дешифрования данных. Дополнительная последовательностьЕ₃– является «шифрованием рабочей области» и обозначается какW=W[1]...W[2l].

Далее мы опишем операции, выполняемые в одном периоде. В нашем описании, мы не упоминаем явно операции шифрования, и, таким образом, всякий раз, когда мы говорим, что мы устанавливаем элемент последовательности W, это должно означать, что соответствующий шифртекст получен и сохранен.

Сначала, мы устанавливаем элементы последовательности Wследующим образом:W[i]:=(i+D[i]) дляilиW[i]:=M[i-l] дляl+1i2l. Здесь мы предполагаем, что записи изменений имеют форму (i,), гдеi– номер ячейки памяти исимвол, который размещен в этой ячейке. Затем, мы сортируем пары изWпо их левым элементам в соответствии с так называемымиключами сортировкитак, что, если два ключа сортировки равны, тогда соответствующие пары хранятся упорядоченными. Определяющим является то, что сортировка выполняется посредством использования эффективной сети сортировки такой, например, как сеть сортировки Батчера [BGG]. Следует подчеркнуть, что всякий раз, когда две пары сравниваются и переставляются (или нет), тогда они заново шифруются посредствомЕ(так что противник не может «понять» были ли они переставлены или нет). Это гарантирует то, что вся процедура сортировки не дает никакой информация противнику. Как только сортировка завершена, алгоритм просматриваетWдля нахождения всех мест нахождения элементов с одним и тем же ключом сортировки и сохраняет последнее (которое является новым), в большом фиктивном значении (l+1,...). Теперь, мы посредством ключа сортировки заново сортируем пары изWи получаем последовательность, в которой первыеlэлементов содержат модифицированный документD'. В заключение, мы устанавливаемЕ₁для хранения в ней зашифрованного блока данныхD'и исключаем первыеlэлементов последовательностиЕ₂.

При использовании AKS-сети сортировки [BGG] вышеприведенная реализация инкрементального алгоритма шифрования требуетO(llogl) шагов (в то время как, если мы используем сеть Батчера, то получаем сумму изО(l)+(llоg₂l) шагов). Эти шаги могут быть распределены равномерно средиlопераций модификации, обеспечивающих желаемую сложность.

Как было упомянуто выше, каждый из рассматриваемых алгоритмов можно адаптировать для реализации схемы инкрементального шифрования для операций вставки/удаления (единственного символа), которая является эффективной в строгом смысле. Для этого длина открытых данных устанавливается в некоторых предопределенных пределах (например, между l/2 и 2l). А именно, схема инкрементального шифрования состоит из трех последовательностейЕ₁,Е₂иЕ₃, гдеЕ₁иЕ₂– определены выше, аЕ₃- шифрование рабочей области для некоторого забывающего моделирующего устройства (см. предыдущую главу). Также как и как выше, алгоритм работает в периодах, состоящих изlизменений каждый. В каждом периоде, инкрементальный алгоритм выполняетlизменений предыдущего периода. Это делается посредством моделированияRAM-программы, которая содержит структуру данных, обеспечивающую эффективное выполнение операций вставки/удаления, например, 2-3-дерево.