Novokshonov A. Methods for controlling integrity of delegated computations

The dissertation is devoted to the problem of verifying correctness of computations performed by a remote device that is not trusted by the user. A system of algorithms for checking integrity of computations has been developed for a limited class of functions over integers of arbitrary length. A new additively homomorphic authentication scheme for integer data of arbitrary length is constructed, which allows controlling the process of performing addition and subtraction operations on them. A new application of the addition machine model of computation is developed for the industry of controlling computation integrity. Practically important conditions for checking integrity of conditional statements and general loops are formulated and proved. Algorithms for checking integrity of computations are constructed for a variant of the addition machine model of computation with integer registers of arbitrary length. Using developed algorithms, a prototype of the software system for controlling integrity of computations is implemented.