On the possibility of provably secure obfuscating programs.

Authors

Varnovskij N.P., Zakharov V.A.

Abstract

By obfuscation we mean any efficient semantic-preserving transformation of computer programs aimed at bringing a program into such a form, which impedes the understanding of its algorithm and data structures or prevents the extracting of some valuable information from the plaintext of a program. The main difficulty in designing an effective program obfuscator is to guarantee security, i.e. to prove that no algorithm can break a software protection in reasonable time. All obfuscation techniques and tools developed so far rely on the informal concept of security and therefore can't be regarded as provably secure. In this paper we (1) introduce for the first time a formal information-theoretic definition of obfuscation security, (2) present a new obfuscation technique which takes advantage of cryptographic primitives (one-way functions, hard-core predicates), and (3) demonstrate, taking a conventional password identification scheme as a case study, how to prove security of the obfuscating transformations.

Text of article

Keywords

program transformation, obfuscation, security, mutual information, one-way function

Edition

Proceedings of the Andrei Ershov 5th International Conference «Prespectives of System Informatics» (PSI'03) , 9-12 July 2003, Novosibirsk, 2003, Lecture Notes in Computer Science, место издания Springer, том 2890, pp. 91-102.

Research Group

Theoretical Computer Science

All publications during 2003

All publications