Processing of private data on public computer networks

Computing systems have gone from mainframes to personal computers, and are now making their way back from personal computers to mainframes.

Massively offered services for everyone to perform computing on high-performance computers, implemented in the form of cloud and other systems, from companies providing similar services in public networks.

However, the use of public computer networks carries the risks for their customers:

• Leaks of private data during processing on an external device or in the process of data transfer;
• The possibility of distortions in the obtained results of calculations on an external device or in the process of data transmission. At the same time, even repeated repetition of calculations with the same source data will not allow detecting the presence of these distortions if they are systemic and not random.

We will not consider issues of leakage of private data or distortions in the results caused in the process of data transfer, leaving this topic to classical cryptography to ensure a closed communication channel of the required degree of reliability.

Let us consider the question when the external computer itself can be compromised, and it is possible for it to analyze private data during processing, and distort the results of calculations, and try to solve the problem, which we formulate as follows:

• It is required to provide a mechanism for processing private data on an external computing device, which, while preserving the possibilities of using standard algorithms, would make it impossible (that is, quite complex) to reveal the values ​​of private data, and also would allow to detect and correct possible distortions in the results of calculations made by chance or systemically.
• Since, undoubtedly, some additional processing of tasks and results is required, on the consumer’s side, it is desirable that the complexity (price, time) of such processing be significantly less than the complexity (price, time) of solving the main problem - otherwise the consumer has no point in performing calculations on external public networks.
• Also, of course, the total number of calculations given to an external computer can increase, since any introduction of redundancy into the original data, either to exclude their unambiguous definition, or to control their accuracy, will undoubtedly require processing more information. However, since external computing capacities can be increased only at the expense of greater payment by the consumer, a reasonable increase in cost should not be a decisive factor when choosing an algorithm for data protection mechanism.

Terms and designations

Denote by the formula f (x) = f0? formulation of the problem of solving a mathematical equation.

As a starting point for the reasoning, we choose the problem of solving a system of linear equations.

Denote by the formula (x0 + ex): f (x0 + ex) = f0 acceptance as the solution of the problem of the value (x0 + ex), where

• x0 is the true solution to the problem
• ex - the distortion added to the true solution of the problem.

Formulation of the problem

It is required to find the transformation of the problem Ek and the transformation of the found solution Dk, such that

• Ek: f (x) = f0? -> g (y) = g0?
• (y0 + ey): g (y0 + ey) = g0
• Dk: (y0 + ey) -> (x0 + ex)
• (x0 + ex): f (x0 + ex) = f0

Where

• f: R-> R and
• g: C-> C

At the same time, the economic / temporal / or other benefit from performing the calculations on an external computer should remain

price (f (x) = f0? -> g (y) = g0?) + price ((y0 + ey) -> (x0 + ex)) << price (f (x) = f0?)

Solving a system of linear equations

Consider the problem of solving a system of linear equations ax = b, where

• a and b - source data - matrices with elements from the R field
• x - required data - matrix with elements from the R field

Remarks:

• The solution is a set that is a linear combination of the vectors of the fundamental solution system.
• For simplicity, we assume that the sizes of all elements of the matrix equation are consistent with each other.
• We assume that the complexity of calculating the inverse matrix to an arbitrary matrix on the local computer is much greater than the complexity of multiplying or adding two matrices.
• Also note that the set of matrices with elements from the R field with multiplication and addition operations is an associative ring with zero divisors.

Linear transformations of a system of linear equations

• ax = b -> Uax = Ub -> a'x '= b' | a '= Ua, b' = Ub, x = x '
• ax = b -> aV / Vx = b -> a'x '= b' | a '= aV, b' = b, x = Vx '
• ax = b -> a (xz) = b-az -> a'x '= b' | a '= a, b' = b-az, x = x '+ z

Algorithm of protection of computation of the problem of solving a system of linear equations

1. Form reversible matrices U and V and vector z from random variables
2. Calculated on the local computer a '= UaV, b' = U (b-az)
3. We transfer the problem of solving the equation a'x '= b' to the external computer.
4. Using the obtained solution of the equation a'x '= b', we calculate on the local calculator x = Vx '+ z
5. Verification of the truth of the found solution can be performed by explicitly substituting the found solution into the formula of the system of linear equations ax = b

')

Linear programming task

Linear programming is a mathematical discipline dedicated to the theory and methods of solving extremal problems on sets of an n-dimensional vector space defined by systems of linear equations and inequalities.

Linear programming is a special case of convex programming, which in turn is a special case of mathematical programming. At the same time, it is the basis of several methods for solving problems of integer and non-linear programming. One of the generalizations of linear programming is fractional linear programming.

Many properties of linear programming problems can also be interpreted as properties of polyhedra and thus formulate and prove them geometrically.



Consider the linear programming problem ax <= b && cx-> max, where

• a and b - source data - matrix and vector with elements from the R field
• c - source data - a vector with elements from the R field
• x - required data - vector with elements from the R field

Algorithm for the protection of computations solving linear programming problems

1. We form a reversible matrix V and a vector z from random variables
2. Calculated on the local computer a '= aV, c' = cV, b '= b-az
3. We transfer the problem of solving the equation a'x '<= b' && c'x '-> max to the external computer.
4. Using the obtained solution of the linear programming problem a'x '<= b' && c'x '-> max, we calculate on the local computer x = Vx' + z

Remarks:

• The formulas ax = b -> UaV / V (xz) = U (b-az) -> a'x '= b' | a '= UaV, b' = U (b-az), x = Vx '+ z
• Reversible matrices can be obtained from the identity matrix by elementary transformations of rows or columns.

Abstract computer

According to the theory of algorithms, modern technical devices, when solving data processing problems, can be represented as a finite abstract calculator that completely simulates a calculation on any technical device.

Models of such abstract calculators have been proposed by Turing, Markov and others.

We will use the entry y = x * F to denote the operation of these calculators on the initial data x by the algorithm F where y is the desired data.

Sequential application of several algorithms (program) F1, ..., Fn in data processing will be denoted as y = x * F1 * ... * Fn

The theory of algorithms tells us that any algorithm (or composition of algorithms) has equivalent algorithms, which means that you can create an algorithm to “reduce” the number of program steps or an algorithm to obfuscate a program to complicate the analysis of a program code using a program entry F1 * ... * Fn as raw data for processing.

Public abstract calculator

Formulation of the problem:

Suppose you want to perform calculations y = x * F over the source data x by the algorithm F where y is the desired data.

Remarks:

• When sending a job to an external computer, we give the source data x and the F algorithm to this computer, receiving the desired data y
• At the same time, it is obvious that there exist algorithms with the properties x = x * E * U and y = y * V * D for any valid x and y. Examples of such algorithms are known from cryptography tasks and problems of recovering corrupted data (error correcting codes)
• So any task of the form y = x * F can be replaced by a task of the form y = x * E * U * F * V * D = (x * E) * (U * F * V) * D = (x * E ) * G * D, where G = U * F * V

Algorithm for the protection of computing on a public computer

1. Take arbitrary algorithms that have the properties x = x * E * U and y = y * V * D for any valid x and y, and such that the algorithms E and D are not too costly to calculate on the local computer.
2. We compose the algorithm G = U * F * V and using the algorithm of “reducing” the number of calculations or the algorithm “obfukatsii” we transform it to the program G 'using a local calculator.
3. Calculate on the local computer x '= x * E
4. Let us perform the task y '= x' * G 'on the external computer, reporting program G' to the external computer x 'as the initial data and receiving the value y' in response.
5. Calculate on the local computer y = y '* D

Remarks:

• Using algorithms E and D, obtained from the theories of cryptography and recovery of corrupted data will ensure the protection of private data transmitted to an external computer or received from an external computer, as well as to detect the facts of distortion of the results of data processing on an external computer.

Literature

• Kudryavtsev V.V., Aleshin S.V., Podkolzin A.S. An Introduction to Automata Theory. M .: Science, 1985.
• Maltsev A. I. Algorithms and computable functions. M .: Science, 1986.
• McWilms FJ, Sloan NJ. The theory of error correction codes. M .: Communication, 1979
• Markov A. A. Introduction to coding theory. M .: Science, 1982
• Karmanov V.G. Mathematical programming. M .: Science, 2000.
• Turchin V.F. REFAL programming language. Internet project www.refal.net
• Ivan Kochurkin @KvanTTT Mathematical expressions in .NET (parsing, differentiation, simplification, fractions, compilation). Internet publication habrahabr.ru/post/150043
• @JediPhilosopher How the computer itself improved its code, or we program the programming process. Internet publication habrahabr.ru/post/265195

Contacts

• Project's Internet address: github.com/dprotopopov/cc