Перевірка делегованих обчислень за допомогою додавальної машини

Abstract

Запропоновано розв'язання проблеми перевірки цілісності арифметичних програм з розгалуженнями і циклами, які виконуються на віддаленому обчислювальному ресурсі. Підхід до розв'язання полягає у заміні арифметичних операцій, таких як множення і ділення, відповідними процедурами додавальної машини (addition machine), введеної Р. Флойдом і Д. Кнутом. Обчислення і послідовність команд підписуються динамічним цифровим підписом, що є гомоморфним за додаванням/відніманням. Для цифрового підпису застосовано модифіковану схему Бенало.

A solution of the integrity verification problem for arithmetic programs with branching and looping statements running on a remote computing resource is proposed. The solution is to replace the arithmetic operations such as multiplication and division by corresponding procedures of the addition machine introduced by R. Floyd and D. Knuth. The order of instructions as well as current meanings of variables are signed by dynamic digital signatures, which are homomorphic with respect to addition and subtraction. A modification of the Benaloh scheme is used for digital signatures implementation.