Инкрементальные алгоритмы
Зафиксируем базовое криптографическое преобразованиеT (например, цифровая подпись документа с некоторым ключом). Каждой элементарной операции модификации текста (например, вставки) будет соответствовать инкрементальный алгоритм I. На вход этого алгоритма подаются: исходный файл, значения преобразования T на нем, описание операций модификации и, возможно, соответствующие ключи или другие параметры. Это позволяет вычислить значение T для результирующего файла. Основная проблема здесь заключается в проектировании схем обработки файлов, с включенными в них эффективными инкрементальными алгоритмами. Предположим, что имеется подпись sстар
для файла Dстар и файл D¢стар, измененный посредством вставки в файл Dстар
некоторых данных. Необходимо получить новую цифровую подпись путем подписывания строки, состоящей из sстар и описания операций модификации над документом Dстар. Это схема называется схемой, зависящей от истории. Могут иметься приложения, когда такие действия могут применяться. В большинстве же случаев это не желательно, так как когда делается большое количество изменений, то затраты на верификацию подписи (а эти затраты пропорциональны числу изменений) резко увеличиваются. В связи с этим размеры подписи растут со временем. Чтобы избежать таких затрат необходимо использовать схемы, свободные от истории или HF-схемы. Все нижеприведенные схемы являются схемами, свободными от истории.
