In this paper, we propose approaches to constructing reliable schemes using the Residue Number System (RNS) for the BOINC volunteer computing systems. We show that application of RNS to homomorphic ciphers allows to build completely homomorphic information security system that not only ensure security but possibility to process encrypted data without its decryption. We present an algorithm for localizing and correcting errors for moduli of a special type.
BOINC type systems allows obtaining significant functional and economic advantages [BCT + 17, IG15, SJJT86]. On the other hand, volunteer computing systems require special attention to security, since, they lead to risks of confidentiality, integrity and correctness of the obtained results [ASS + 14, TBC + 17]. Homomorphic ciphers are used to ensure the security of information [CBT + 17, Gen10]. Users can send information to BOINC servers that is not the result of the requested calculations [TSTB16]. For instance, they could send results with an error or a set of random bits [KPT + 13].
Here, we consider two main problems: uncompleted tasks, and deliberately distorting results.
1. The problem of an uncompleted task. After the data for processing is sent to one of the participants, he could not be able to return results, due to software failures, participant's refusal, natural cataclysm, etc [TSAT15].
The BOINC systems try to solve this problem by setting a deadline for participant task execution.
2. The problem of deliberately distorting results by users can lead to the failure of all computations performed by other participants, and need for recalculations, which could requires significant additional time. The BOINC system solves this problem by using at least 5 replicas (by default) [IG15,TPBS14]. In each project, this value can be either increased or decreased. The result, adopted by the quorum of client programs, is considered to be correct or incorrect. Incorrect answers are usually rejected [KPT + 16].
To protect the system from the information distortion, we propose to apply RNS for detection and correction of errors. RNS improves performance, reliability, security, since, computations are not performed over original large numbers, but over small projections of large numbers [QPV02,SJJT86].
Operations on projections can be executed in parallel and independently. Encryption schemes constructed by using RNS allow building asymptotically optimal security systems, both from a practical and theoretical point of view [GTN11].
Homomorphic encryption can be naturally used in cloud computing. RNS creates several pieces of data, and operations over individual pieces are homomorphic with respect to: addition, subtraction and multiplication.
These properties of RNS can be used to develop a homomorphic encryption function. In homomorphic encryption schemes, we consider two types of security: data security and moduli security.
In the volunteer computing systems like BOINC, when we use redundant RNS to ensure the reliability of information, the probability of distortion of one or several projections of the result is high.
In order to provide verification of the result, we propose a model, in which the Boing server does not trust any user. We develop a simplified mechanism of result verification with a given probability of the correctness.
There exist several methods for conversion between positional number system and RNS. Methods based on the principle of sequential summation of bit modular products are not efficient [Gen10].
To convert the numbers from positional number system to RNS, we propose to use the method of recursive doubling, the parallel summation of bit modular products described in the following way [CBD + 16, CBKG15]:
where α i -is the least non negative residue |p j |, α i ∈ {0, 1} in case of binary number system. For a further parallelization this method uses the associativity of addition. The details of this parallel method is described in [Gen10].
For an efficient implementation of decryption algorithms we use the approximate method from [CBD + 16]. The idea of the approximate method of comparison of modular numbers is based on a quotient from division of the value of a number by the dynamic range of RNS, Chinese reminder theorem (CRT), which relates the positional number X with its representation with residues (x 1 , x 2 , . . . , x n ), where x i -is the least non negative residue, from division by modules from RNS moduli set (p 1 , p 2 , . . . , p n ), with the following expression
where P = n i=1 p i , p i -RNS moduli set, P −1 i -multiplicative inversion of P i with respect to p i , and P i = P pi . If we divide (2) by the constant P , then we obtain an approximate value
where
-for all i from 1 to n are the constants of the system, x i -digits in the RNS representation. The value of each sum is in the interval [0, 1). The final result of the sum is defined after the summation and is the fractional part of the sum. The fractional part also can be represented as X mod 1, because X = X +X mod 1. The number of digits in the fractional part is defined by the maximum possible difference between adjacent numbers [CBD + 16].
Here, we briefly review the concept of diagonal function [DIP93]. First, for a given moduli set {p 1 , p 2 , . . . , p n },
where the moduli m i are mutually prime, we define a parameter "Sum of Quotients (SQ)", where SQ = n i=1 P i , for all P i = P/p i . Then, we also define constants ki = − 1 pi SQ for i = 1, 2, . . . , n. The diagonal function corresponding to a given number X with residues (x 1 , x 2 , . . . , x n ) is defined as:
Note that D (X) is a monotonic function. Two numbers X and Y can be compared based on the D (X) and D (Y ) values. However, if they are equal, we need to compare the coordinates (residues corresponding to modulus) of X with respect to Y in order to determine whether X > Y or X = Y or X < Y . Pirlo and Impedovo [PI13] have observed that diagonal function does not support RNS to binary conversion. Mohan [Moh16] shows that it is possible to perform RNS to binary conversion using diagonal function by equations:
It is worth to note that RNS moduli set has the form p 1 = 2 a − c and p 2 = 2 a + c, where c is impair, and SQ = 2 a+1 . Considering that SQ is a power of 2, to convert a number from RNS to binary number system it is not necessary to compute residues from division by large numbers used in methods such as CRT and nCRT.
Since lim a→∞ 2a+1 a+1 = 2 , the size of coefficients is asymptotically twice smaller than in methods that allow to compute X with lower complexity than CRT, nCRT and aCRT.
3 Algorithm for error detection, localization and correction for moduli set of the form
Taking into account the works on constructing a reliable, secure and distributed storage system in the clouds with erasure codes, Byzantine protocol etc. with parameters (2, 4), we develop the error correction code with a moduli set of a special form that allows to detect and correct errors using error syndrome. We can extend the applicability of the error detection, localization and correction with error syndrome using moduli set of the form 2 l − 3, 2 l − 1, 2 l + 1, 2 l + 3 for cloud computing.
1. Calculate the value of X, using moduli set 2 l − 1, 2 l + 1 : SQ 23 = 2 l − 1 + 2 l + 1 = 2 l+1 . Constants of Diagonal function:
Using the equation from the paper [Moh16], we find the value X.
2. Calculate the value of X, using moduli set {2 l − 3, 2 l + 3}: SQ 14 = 2 l − 3 + 2 l + 3 = 2 L+1 . Constants of Diagonal function:
l + 1. Then, the diagonal function value is:
, if n -even. Using the equation from the work [8], we find the value of X.
The use of error correction codes in the RNS with the given parameters can detect two or correct one error. We study the data obtained from the cloud using the Eqn. ( 5) and (6) we find the error syndrome.
1. If an error occurs in x 1 , then
As the gcd 2 l − 3, 2 l+1 = 1, then the condition Eqn. ( 7) is equivalent to:
Substitute Eqn. (5) in Eqn. (8), then
As the 2 l 2 l −3 = 3 Eqn. (8) can be written as
As the gcd 2 l − 1, 2 l+1 = 1, Eqn. (10) can be written as
Substitute Eqn. (6) in Eqn. (8), then
As the 2 l 2 l −1 = 1 Eqn. ( 11) can be written as
3. If an error occurs in x 3 , then
As the gcd 2 l + 1, 2 l+1 = 1, Eqn. (13) can be written as
Substitute Eqn. (6) in Eqn. ( 14), then
As the 2 l 2 l +1 = −1 Eqn. ( 15) can be written as
4. If an error occurs in x 4 , then
As the gcd 2 l + 3, 2 l+1 = 1, Eqn. (17) can be written as
Substitute Eqn. (5) in Eqn. (18), then
Using the Eqn. ( 9), ( 12), ( 16) and (20) calculate the value of the error syndromes s 1 , s 2 , s 3 , s 4 . If s i = 0, we assume that s i = 1, for all i = (1, 4) . Using Table 1, you can calculate the position of error. After excluding error true value can be restored Example 1. Let X = 92 → (1, 2, 7, 16), RNS is defined by moduli set 2 4 − 3, 2 4 − 1, 2 4 + 1, 2 4 + 3 .
1. If error vector is E → (1, 0, 0, 0), then X → (2, 2, 7, 16). If the error vector is given by: E → (1, 0, 0, 0), then X = X + E → (2, 2, 7, 16).
Compute diagonal function values:
Because n = 4, then r 3 = 2 4+1 +1 3 = 3, consequently:
Compute error syndrome value:
Since s 1 = s 2 = s 3 = 1 and s 4 = 0, then the case 3 of Table 1, and therefore an error occurred in the x 1 , therefore, the true value of X is reduced using the Eqn. (5).
(2 8 − 1)
True value: X = 92. 2. If error vector is E → (0, 1, 0, 0), then we obtain X = X + E → (1, 3, 7, 16).
Compute diagonal function values:
Because n = 4, then r 3 = 2 4+1 +1 3 = 11, consequently:
Compute error syndrome value:
Since s 1 = s 2 = s 4 = 1 and s 3 = 0, then the case 4 of Table 1, and therefore an error occurred in the x 2 , therefore, the true value of X is reduced using the Eqn. (6).
(2 8 − 9)
True value: X = 92. 3. If error vector is E → (0, 0, 1, 0), then we obtain X = X + E → (1, 2, 8, 16).
Compute diagonal function values:
Because n = 4, then r 3 = 2 4+1 +1 3 = 11, consequently:
Compute error syndrome value:
Since s 1 = s 3 = s 4 = 1 and s 2 = 0, then the case 5 of Table 1, and therefore an error occurred in the x 3 , therefore, the true value of X is reduced using the Eqn. (6).
True value: X = 92. 4. If error vector is E → (0, 0, 0, 1), then we obtain X = X + E → (1, 2, 7, 17).
Compute diagonal function values:
Because n = 4, then r 3 = 2 4+1 +1 3 = 11, consequently:
Compute error syndrome value:
Since s 2 = s 3 = s 4 = 1 and s 1 = 0, then the case 2 of Table 1, and therefore an error occurred in the x 4 , therefore, the true value of X is reduced using the Eqn. (5).
(2 8 − 1) • 11 + (2 4 + 1) • 2 + (2 4 − 1) • 7 2 5 = 92.
True value: X = 92. Analyzing the values of error syndromes from the Table 1 we can note that in order to determine which parts should be used to obtain a true value it is sufficient to know either the syndromes {s 1 , s 4 } or {s 2 , s 3 } . In terms of computational complexity of computing {s 1 , s 4 } are better. Thus using {s 1 , s 4 }, we determine which parts should be taken to obtain the true value. The results are shown in the Table 2. Its worth noting that in Table 2 in case 4 to control the result of computations it is required to use the value of hash function MD5, which ensure the correctness of the data with probability 2 −32 .
In this paper, we propose approaches to construct reliable schemes for BOINC type volunteer computing systems using Residue Number System, and a scheme for controlling computations. We show how an application of RNS allows to build completely homomorphic information security systems. We present a new algorithm for localizing and correcting errors for moduli of a special type.
Acknowledgment. The work is partially supported by CONACYT (Consejo Nacional de Ciencia y Tecnología, México), grant No. 178415. Part of the work was supported State task No. 2.6035.2017 and Russian Federation President Grant SP-1215.2016.5. We gratefully acknowledge Evgeny Ivashko for valuable discussions and comments.