An Approach to Quantitative Analysis of Resistance of Data Encodings in Tamper-Resistant Software

To protect data in tamper resistant software different types of data encodings can be used. To compare security of different encodings on a quantitative base a measure of resistance of data encodings must be introduced.In this paper a measure of resistance of data encodings is proposed as a measure of uncertainty, i.e. the number of real computations which can correspond to the same observable encoded computation. An adversary observing only operations of encoded computation and its inputs (i.e. all encoded input data) cannot distinguish between any of real computations. Thus the more the number of real computations corresponding to the same encoded computation the more uncertainty and resistance of encoding.It is important to note that such measure characterizes the resistance of encoding to arbitrary attack which uses only information from encoded world.We prove lower bounds of resistance of different types of encodings for some computational schemes and show high security of computations performed in such encodings. Typically such bounds are at least of order 2. This seems large enough because it is impossible to enumerate all potential solutions and the probability to guess right parameters choosing them at random is less than 2