Предлагаемые решения используют стойкую схему вероятностного шифрования 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'
(конечно, теперь текущие данные другие).