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. 2 2.1
RNS homomorphic ciphers and their properties
Method of conversion from positional number system to RNS 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]: ai2i + ai+12i+1 pj = |·|p+j , 0 ≤ i ≤ k, i.e. αi ≡ k X ai2i p+j i=0 + pj where ki = |Pi−1|pi – for all i from 1 to n are the constants of the system, xi – digits in the RNS representation.
pi 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 where αi – is the least non negative residue |pj |, α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]. 2.2
Method of conversion from RNS to positional number system 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 (x1, x2, . . . , xn), where xi – is the least non negative residue, from division by modules from RNS moduli set (p1, p2, . . . , pn), with the following expression n where P = Q pi, pi – RNS moduli set, Pi−1 – multiplicative inversion of Pi with respect to pi, and Pi = pPi .
i=1 If we divide (2) by the constant P , then we obtain an approximate value
X = n X P i=1 pi
Pi−1 xi
P X P
n = X i=1
Pi−1 pi pi xi 1 = n X kixi i=1 1 (1) (2) (3)
It is worth to note that RNS moduli set has the form p1 = 2a − c and p2 = 2a + c, where c is impair, and SQ = 2a+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 2aa++11 = 2 , the size of coefficients is asymptotically twice smaller than in methods that allow to a→∞ compute X with lower complexity than CRT, nCRT and aCRT.
Algorithm for error detection, localization and correction for moduli set of the form n2l − 3, 2l − 1, 2l + 1, 2l + 3o 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 2l − 3, 2l − 1, 2l + 1, 2l + 3 for cloud computing.
1. Calculate the value of X, using moduli set 2l − 1, 2l + 1 : SQ23 = 2l − 1 + 2l + 1 = 2l+1. Constants of 1 1 Diagonal function: k2 = − 2l−1 2 l + 1 = 2l + 1, k3 = − 2l+1 2 l + 1 = 2l − 1.
D23 (X) = |k2x2 + k3x3|2 l + 1 = 2l (x2 + x3) + x2 − x3 l2+1 .
X = 22l − 9 D14 (X) + 2l + 3 x1 2l − 3 x4 2l+1 Using the equation from the paper [Moh16], we find the value X.
As the gcd 2l − 1, 2l+1 = 1, Eqn. (10) can be written as |X − x2|2l−1 6= 0. 2l+1X − 2l+1x2 2l−1 6= 0.
As the 2l 2l−1 = 1 Eqn. (11) can be written as 22l − 9 D14 (X) + 2l + 3 x1 + 2l − 3 x4 − 2l+1x2 2l−1 6= 0. s2 = |8D14 (X) − 4x1 + 2x4 + 2x2|2l−1 6= 0.
As the gcd 2l + 1, 2l+1 = 1, Eqn. (
As the 2l 2l+1 = −1 Eqn. (
|X − x4|2l+3 6= 0.
As the gcd 2l + 3, 2l+1 = 1, Eqn. (
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 x1, then
As the gcd 2l − 3, 2l+1 = 1, then the condition Eqn. (7) is equivalent to:
2l+1X − 2l+1x1 2l−3 6= 0.
(7)
(8)
(9)
(10)
(11)
(12)
(
Using the Eqn. (9), (12), (
Example 1. Let X = 92 → (
1. If error vector is E → (1, 0, 0, 0), then X0 → (
Compute diagonal function values:
D23 (X0) = |16(2 + 7) + 2 − 7|32 = |16 − 5|32 = 11.
Because n = 4, then r3 = 24+1+1 = 3, consequently:
3
D14 (X0) = |11(16(2 + 16) + 2 − 16)|32 = |11 · 18|32 = 6.
s1 = |8 · 11 + 4 · 2 + 2 · 7 − 6 · 2|13 = 7, since 7 6= 0, it follows that s1 = 1. s2 = |8 · 6 − 4 · 2 + 2 · 16 + 2 · 2|15 = 1. s3 = |8 · 6 − 2 · 2 + 4 · 16 − 2 · 7|17 = 9, since 9 6= 0, it follows that s3 = 1. s4 = |8 · 11 − 2 · 2 − 4 · 7 + 6 · 16|19 = 0.
Since s1 = s2 = s3 = 1 and s4 = 0, then the case 3 of Table 1, and therefore an error occurred in the x1, therefore, the true value of X is reduced using the Eqn. (5).
X =
D14 (X0) = |11(16(1 + 16) + 1 − 16)|32 = 11.
s1 = |8 · 28 + 4 · 3 + 2 · 7 − 6 · 1|13 = 10, since 10 6= 0, it follows that s1 = 1. s2 = |8 · 11 − 4 · 1 + 2 · 16 + 2 · 3|15 = 1 since 2 6= 0, it follows that s2 = 1. s3 = |8 · 11 − 2 · 1 + 4 · 16 − 2 · 7|17 = 0. s4 = |8 · 28 − 2 · 3 − 4 · 7 + 6 · 16|19 = 1.
Since s1 = s2 = s4 = 1 and s3 = 0, then the case 4 of Table 1, and therefore an error occurred in the x2, therefore, the true value of X is reduced using the Eqn. (6).
X =
True value: X = 92.
3. If error vector is E → (0, 0, 1, 0), then we obtain X0 = X + E → (
Compute diagonal function values:
D23 (X0) = |16(2 + 8) + 2 − 8|32 = |32 − 6|32 = 26.
True value: X = 92.
4. If error vector is E → (0, 0, 0, 1), then we obtain X0 = X + E → (
Compute diagonal function values:
s1 = |8 · 11 + 4 · 2 + 2 · 7 − 6 · 1|13 = 0. s2 = |8 · 16 − 4 · 1 + 2 · 17 + 2 · 2|15 = 12 since 12 6= 0, it follows that s2 = 1. s3 = |8 · 16 − 2 · 1 + 4 · 17 − 2 · 7|17 = 10 since 10 6= 0, it follows that s3 = 1. s4 = |8 · 11 − 2 · 2 − 4 · 7 + 6 · 17|19 = 6 since 6 6= 0, it follows that s4 = 1.
Since s2 = s3 = s4 = 1 and s1 = 0, then the case 2 of Table 1, and therefore an error occurred in the x4, therefore, the true value of X is reduced using the Eqn. (5).
X =
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´exico), 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. [DIP93]
Mahadevan Gomathisankaran, Akhilesh Tyagi, and Kamesh Namuduri. HORNS: A homomorphic encryption scheme for cloud computing using residue number system. In Information Sciences and Systems (CISS), 2011 45th Annual Conference on, pages 1–5. IEEE, 2011.
Evgeny Ivashko and Alexander Golovin. Partition algorithm for association rules mining in BOINC– based enterprise desktop grid. In International Conference on Parallel Computing Technologies, pages 268–272. Springer, 2015. [KPT+13] Dzmitry Kliazovich, Johnatan E Pecero, Andrei Tchernykh, Pascal Bouvry, Samee U Khan, and Albert Y Zomaya. CA-DAG: communication-aware directed acyclic graphs for modeling cloud computing applications. In Cloud Computing (CLOUD), 2013 IEEE Sixth International Conference on, pages 277–284. IEEE, 2013. [KPT+16] Dzmitry Kliazovich, Johnatan E Pecero, Andrei Tchernykh, Pascal Bouvry, Samee U Khan, and Albert Y Zomaya. CA-DAG: modeling communication-aware applications for scheduling in cloud computing. Journal of Grid Computing, 14(1):23–39, 2016. [SJJT86]