Abstract. 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. Verification of digital signatures of computation results ensures detection of any unauthoried changes to the source code of the program.

Keywords: addition machine, digital signature, verifiable computing, homomorphic cryptography.