When designing and using distributed storage systems with cloud technology, the security issues become crucial. One of the promising mechanisms is the computationally secure threshold secret sharing scheme. We propose a computationally secure secret sharing scheme based on the minimally redundant modular code. It reduces the computational complexity of data encoding and decoding and reduce data redundancy. We show that it is computationally secure and provides data redundancy equivalent to the redundancy of the Rabin system. We demonstrate that the minimally redundant modular code does not satisfy the criterion of compactness of a sequence, but it can be used as an asymptotically ideal secret sharing scheme.
The cloud technologies require users to take into account the increased risks of data security and reliability. To reduce the likelihood of theft, loss or distortion of data stored in clouds, two mechanisms can be used: secret sharing schemes and hash functions. Residue Number System (RNS) as the basis for the design of distributed storage systems combines these two mechanisms into one, since RNS on the one hand is a secret sharing scheme, and, on the other hand, it has properties of error detection and correction.
Secret sharing schemes on RNS provide the same level of security as schemes built on Lagrange interpolation, however, have higher redundancy. To solve this problem, compact sequences as RNS moduli that satisfy the condition p" < p$ < ⋯ < p& < 2p& are proposed [1].
Compact sequences highlight a class of asymptotically ideal Asmuth-Bloom secret sharing schemes [2, 3], which ensure a high level of data reliability and security. But this approach is not applicable in practice for storing big data, since data redundancy is higher than data replication and symmetric encryption.
AC-RRNS [4] modification of the Asmuth-Bloom scheme uses compact sequences to reduce data redundancy while ensuring computational security. However, using a prime number ) as a key satisfying the condition: β = ∏. 0 " p. > p) > ∏./02)$ p&2 . = α leads to increasing the complexity of the / encoding and decoding algorithm from linear-logarithmic to quadratic. It does not allow its efficient use.
An alternative solution to the problem is to use minimally redundant modular code, which, on the one hand, satisfies the criteria of compactness of a sequence, and, on the other hand, reduces the computational complexity of encoding and decoding while maintaining reliability and security at the same level.
The rest of the paper is structured as follows. Section 2 discusses the properties of RNS. Section 3 describes RNS-based minimally redundant code. Section 4 discusses our secret sharing scheme modification. Section 5 explores the security issues of the proposed scheme. Section 6 concludes the paper.
RNS is a non-positional number system that allows splitting long numbers into a series of independent digits of small length, speeding up the calculations and organizing their parallelism. The main advantage of RNS is the ability to perform addition and multiplication operations fast compared to all other number systems. It causes a great interest in RNS in those areas in which large amounts of computation are required.
RNS is defined by a system of mutually prime moduli β = {p", p$, … , p&}. The positive number X in the RNS for these moduli is represented as a tuple of numbers X = (x", x$, … , x&), where x. = |X|=. = X mod p. [5] for i = 1,2, … , n. Such a representation of the number X is unique, if 0 ≤ X < P, where P = ∏.&0 " p. , and is called the RNS range.
The operations of addition, subtraction and multiplication in the RNS for the numbers A = (a", a$, … , a&) and B = (b", b$, … , b&) are determined by the formulas: ± = N|" ± "|QR, . . . , |T ± T|QUV × = N|" × "|QR, . . . , |T × T|QUV
The equalities (
In modern technology, one of the most popular properties of algorithms is their parallelism. This fact is due to the development of many parallel systems, from multiprocessor clusters to embedded systems for special purposes.
The most common way to reconstruct the positional value of a number based on its residual representation is the Chinese Remainder Theorem (CRT), the classical form of which we will designate as CRTc.
Let the number be given in the form (", $, … , T) in the CRT by moduli (", $, … , T). Then:
(
Q_
This method is computationally complex, since it leads to calculations that fall outside the range of , and its implementation requires the operation of calculating the residue of the division by a large number of , which greatly complicates the calculation scheme. The calculation of the residue of the division in any computer system is traditionally one of the most expensive operations. The implementation of this operation on the FPGA leads to a significant increase in the hardware costs of the algorithm and an increase in the delay in operation.
One approach to get rid of calculating the residue of dividing by the RNS range is an approach using a Mixed-Radix System (MRS) [6-8]. By MRS with moduli ", $, … , T we mean a system in which the integer is represented as:
= TT2 "T2 $. . . $" + T2 "T2 $T2 e. . . $"+. . . +$" + ", where f are the numbers 0,1, … , f2 ". MRS numbers f can be found by the formulas. " = " "; $ = ($ − ")"$ $ …. e = N(e − ")"e − $V$e e T = N. . . N(T − ")"T − $V$T−. . . −T2 "VT2 ",T T
The constants Xf are multiplicative inverse elements for X modulo f for all 1 ≤ ≤ ≤ , i.e. Xf ∙ X = 1 f for 1 ≤ ≤ , and can be calculated, for example, using the Euclidean algorithm.
The main advantage of MRS is the transition to the use of low-bit operations. Most operands for addition and multiplication operations are numbers whose bit capacity is equal to the capacity of the moduli, which allows constructing simpler schemes than when using CRT. In addition, the considered method can be presented in parallel form [9]. However, a decrease in the capacity of operands leads to an increase in the number of operations, including operations for calculating the residue of the division, which leads to an overall decrease in the operating time of the algorithm.
Next, we consider a modification of the Chinese remainder theorem using fractional quantities,
which we will denote CRTd [10-12]. If both parts of formula (
Q_ X =
Q_ ]`_r R]s_ , = 1,2, … , are constants of RNS and can be calculated in advance. In this case, the value of each sum will be in the range [0,1), which gives enough information to evaluate the sign and value of the number represented in the RNS.
Such a transition allows replacing the exact number with its fractional characteristic, making it possible to control the accuracy of the presentation depending on the available resources and the task. The value o can be considered as a positional characteristic of the number , while the number can be found by the formula
= o
However, in the case of machine calculations, we can use only limited accuracy, which requires rounding or discarding the least significant bits of the fraction. Let us estimate the number of bits that make it possible to uniquely determine the fractional characteristic of the number . Let wv be a finite fraction containing bits that coincide with the first bits of the number X for all = 1,2, … , . In other words wv = ⌊X⌋$r { , where the operation means rounding the number down. The approximate value of the number o will not be more accurate, since X ≥ wv. The exact value of can be restored by multiplying o by , discarding the fractional part with rounding up. Let us estimate the required calculation accuracy , at which the value o reconstructed using wv will not lead to errors when restoring the exact value of . For this, the relation shows the uniqueness of the positional characteristic o for different numbers of RNS. The transformation of expression (7) using formula (4) leads to the inequality p 2 " `
p < ]∑XT0 " wvX]" ≤ `
" 0 ≤ ]∑XT0 "NX − wvVX]" < ` (4) (5) (6) (7) (8) Since X − wv = ]`_r R]s
Q_ _ − ${ ]`_r R]s 2 }${ ]`_r R] } _ s_ s_ = ${ ∙Q_ }${ ]`_r R] }
s_ s_, then ${ ∙Q_
T T ∑X0 "NX − wvVX = ∑X0 " }${ ]`_r R]s_}s_ X.
${ ∙Q_
T ∑X0 " }${ ]`_r R]s_}s_ X ≤ { ∑X0 " [2]X2 "] [ " T ${ ∙Q_ $ Q_ Q_ T − ∑X0 " }${ ]`_r R] }
s_ s_ Q_
2 ≤ ∑XT0 " [2]X2 "]Q_ [Q_
T − ∑X0 " }${ ]`_r R] }
s_ s_ Q_ ≤ −SQ + ∑XT0 "(X − 1).
(9) (10) (11) (12) (13) (14)
T where = ∑X0 " X.
T
Denoting = ∑X0 "(X − 1), from formula (11) we get that when choosing equal to = ⌈log$( ∙ − )⌉, the resulting estimate is the estimate refinement obtained in [12], where = ⌈log$( ∙ )⌉. Using the approximate method allows getting away from calculating the residue of the division by the RNS range, by increasing the dimension of the coefficients. An alternative solution is to use minimally redundant code, which imposes additional restrictions on the moduli, but at the same time reduces the complexity of decoding.
In the following, we assume that the RNS moduli are ordered in increasing order " < $ < ⋯ < T. The number can be restored using the properties of the modular code, according to the following formula:
= ∑XT02"" X]X2 " ⋅ X]Q_ + T ⋅ (), where for any ∈ [1, − 1]: X = T/X, and () is an interval characteristic that is determined using the following Theorem 1.
Theorem 1 [13]. If the RNS moduli satisfy the condition T ≥ 2" + − 2, then the interval characteristic () is calculated using the following formula: () =
() () < " () − T () ≥ T − " − + 2 where () = q[U[ −⋅ ∑XT02"" [ " [ ⋅ ]X2 " ⋅ X]Q_q .
`U QU Q_ QU QU
As shown in Chernyavsky & Kolyada, 2009 [13], for RNS moduli to be minimally redundant modular code, it is necessary and sufficient that
T = 2" + + |T − |$ + 2
Case 1, T and are even numbers, T = 2" + + 2, Case 2, T and are odd numbers, T = 2" + + 2, Case 3, T is even number and is odd number, T = 2" + + 3, Case 4, T is odd number and is even number, T = 2" + + 3.
Considering four cases, we can conclude that if T > 2", then the minimally redundant code does not satisfy the compactness criterion.
To formalize the proposed scheme, we use the following notations. ∈ is a secret, ", $, … , T are prime numbers (RNS moduli set), with properties of the minimum redundant modular code, where Q = ", $, … , is secret key and X is prime numbers and compact sequence, i.e. " < $ < ⋯ < < 2".
We perform a masking transformation that translates to ̅ = + ⋅ , where is a random number and ̅ < ∏X0 " X. To calculate the chunks, we get X = |̅|Q_.
It follows from the condition ̅ < ∏X0 " X = that + ⋅ < , which means that < − ⋅ . Let be bounded above ≤ . We have < − ⋅ < ( + 1) ⋅ < < "
< min , "¡
⋅ ≤ ≤ ( + 1)
≤ ≤ + 1 From (23), it follows that the value = «¬. Since, from the point of view of safety, satisfies the condition ≥ 1, then < /2. Therefore, the scheme parameters must satisfy the following conditions:
On the other hand, = |̅| so that we can uniquely decode data if
Case 1: < , then < and redundancy is equal to "
≈ ¤¥¦¤§¥∏¦§_U¨R Q_ > ¤¥¦§ ∏¤_©¥¨¦R§Q∏_2_U¨¤R¥Q¦§_(") = 1 + ¤ ¥¤¥¦¦§§(∏_©"¨)RQ¤_¥2¦§¤¥∏¦§_U¨(©ªR"Q)_ Case 2: ≥ , then < " " ¤¥¦§ ∏_U¨R Q_ ¤¥¦§ ∏_U¨R Q_ ¤¥¦§(")¤¥¦§ ∏_U¨©ªR Q_ ≈ ¤¥¦§ 2 ¤¥¦§(") = ¤¥¦§ ∏_©¨R Q_ 2 ¤¥¦§(") = 1 + ¤¥¦§ ∏_©¨R Q_ 2 ¤¥¦§(")
From (20) and (21), it follows that the secret sharing scheme has optimal redundancy (21). If the condition ≥ is fulfilled, then ( + 1) ≥ . On the other hand, from (15) ⋅ ≤ follows, " therefore satisfies the condition: (15) (16) (17) (18) (19) (20) (21) (22) (23) and gcd(, ) = 1.
Condition 2: < $ Condition 1: β > ∏./02)$ T2 X (determines that the proposed scheme is a threshold) Condition 3: = «¬.
In contrast to the Asmuth-Bloom scheme [14], the proposed scheme provides data security with minimum redundancy.
In this section, we examine the security parameters of the proposed scheme. Condition 4 states that RRNS moduli set is a minimum redundant modular code. Hence, each user has approximately the same amount of information about the original data. Now, we show that proposed scheme minimizes the probability of access to data by collusion of adversaries. To this end, we prove the following statements, corollary, and theorem.
Statement 1. In proposed (, ) secret sharing scheme, if an adversary coalition knows less than secret shares and secret key , then the probability obtaining the secret is less than 1/2(®2 ").
Proof. For the set ⊂ {1,2, … , } with the cardinality less than , we can compute the value ∗ that satisfies the equality ∗ = ||`±, where ² = ∏X∈² X. Therefore, can be represented as: = ∗ + ² ⋅ , where integer ∈ [0, ⌊/²⌋]. Each value of corresponds the value of µ∗ calculated by the following formula: µ∗ = |∗ + ² ⋅ |Q¶.
Taking into account Condition 1, ² satisfies the condition ² ≤ ∏X02)$ T2 X. Consequently, the probability to compute with the known ∗, satisfies the equality () ≤ ·¹¸"±º ≤ QUr"©ªR < $»"r R
Statement 2. In the proposed (, ) scheme, probability to obtain the secret based on known or more secret shares without secret key is less than ¼()2$ $©ªR, where () is Euler function.
Proof. Knowing or more secret shares using the Chinese remainder theorem, we can restore the value of ̅. In order to calculate from ̅ it is necessary to sort out the whole set of possible values of . Since from Condition 2 gcd(, ) = 1 and < $, then represented in RNS by the moduli ", $, … , should not contain a single residue from the division equal to zero. Let us consider the values of the form ¾, the smallest of the numbers which in the representation of the moduli contains ≤ different zero values at the positions = {", $, … , Á}, respectively, then the number of numbers containing at the positions {", $, … , Á} zeros and is «$p¬. Therefore, the number of $ non-coprime to numbers is ∑¾∈² «$p¬. Considering that the cardinality of the set is 2, then ∑¾∈² «$p¬ < ∑¾∈² $p = $" ∑¾∈² p − 2 < $" ∑¾∈² «p¬ + 2 coprime to and less than is less then:
$
Since the number of numbers that are non-coprime to and smaller is, on the one hand, equal to ∑¾∈² «p¬, on the other hand, substituting − () in (24), we find that the number of numbers non"$ N − ()V + 2 Therefore, the number of numbers coprime to and less than is greater than or equal to: $ $ − $" N − ()V + 2¡ = $" () − 2 = ¼()2 $©ªR $ (24) (25) Hence, the probability to obtain is less than ¼()2$ $©ªR.
Now, we show the computational security of the proposed scheme. The concept of computational security is based on the following idea: information cannot be effectively restored if there is no complete information. Therefore, the scheme is computationally secure, if the adversary knows the secrets ("), ($) and incomplete sets of shares ("), ($), but cannot map N("), (")V and N($), ($)V unambiguously.
Computational security for secret sharing schemes can be defined in more strong way [15]. It is based on the polynomial indistinguishability concept [16-23]. For any probability distribution (, ), a secret sharing scheme is computationally secure if, for any pair of secrets ("), ($) and incomplete subsets of shares (") and ($), the distributions N("), (")V and N("), (")V are polynomial indistinguishable, i.e. for any probabilistic algorithm [Pr N("), (")V¡ = 1¡ − Pr N($), ($)V¡ = 1¡[ < 1
, (, ) where (, ) is the some polynomial over the amount of possible shares.
Theorem 2. The proposed scheme is computationally secure if ≤ 4.
∀ , , ∈ : | − | ≤ | − | + | − |
Let = Pr N("), (")V¡ = 1¡, = Pr N($), ($)V¡ = 1¡, = PrNN("), (")V = 1V . We have: (27) (28) [Pr A DNC("), S(")V¡ = 1¡ − Pr A DNC($), S($)V¡ = 1¡[ ≤ [Pr A DNC("), S(")V¡ = 1¡ − PrNDNC("), S(")V = 1V[
+ [Pr A DNC($), S($)V¡ = 1¡ − PrNDNC("), S(")V = 1V[ where PrNN("), (")V = 1V is the probability of obtaining the secret using the first shares.
Since the number of desired outcomes is less than or equal to ∏X0 " X and the total number of all outcomes is ∏XT0 " X, then the probability is
Pr A DNC("), S(")V¡ = 1¡ ≤ Pr A DNC($), S($)V¡ = 1¡ ≤
PrNDNC("), S(")V = 1V = ∏X0 " X ∏XT0 " X ∏X0 " X ∏XT0 " X = = 1 1
, ∏XT0 " X
, ∏XT0 " X 1
.
∏X0 " X
QR
Therefore, $©"QR© < ∏_©¨"R Q_ < "© and $Ur ©"QRUr © < ∏_U¨©"ªR Q_ < QRU"r ©.
From Condition 4 and k ≥ 4, it follows that p"/ < ∏. 0 " p. < 2/ p"/ and p"&2 / < ∏.&0 /" p. < / 2&2 / p"&2 / . " " " " [Pr A DNC("), S(")V¡ = 1¡ − PrNDNC("), S(")V = 1V[ < max ÍQRUr © − $©QR© , QR© − $Ur ©QRUr ©Î (29) " " " " [Pr A DNC($), S($)V¡ = 1¡ − PrNDNC("), S(")V = 1V[ < max ÍQRUr © − $©QR© , QR© − $Ur ©QRUr ©Î .
[Pr N("), (")V¡ = 1¡ − Pr N($), ($)V¡ = 1¡[ (30) 1 1 1 1 < 2 ∙ max "T2 − 2" , " − 2T2 "T2 Ï .
Theorem 2 has a significant practical importance. It states that the adversary cannot obtain any information from an incomplete set of shares.
Let (("), (")) and (($), ($)) satisfy the following assertions for all ∈ [1, … , ]: X(") = ](") + Q ⋅ "]Q_, X($) = ]($) + ⋅ $]Q_
Since for all ∈ [1, … , ] gcd(Q, X) = 1, there exist "Ð, $Ð, Q′ such that the following equations are satisfied:
X(") = ]($) + Q′ ⋅ $Ð]Q_, X($) = ](") + Q′ ⋅ "Ð]Q_.
From (31) and (32), it follows that to unambiguously map (("), (")) and (($), ($)) , is required. Since is not known, our scheme is computationally secure.
We propose and analyze computationally secure threshold secret sharing schemes based on the minimally redundant modular code. We show that a minimally redundant modular code does not possess the compact sequence property. We study the selection of circuit parameters to minimize redundancy while ensuring data security. We demonstrate that a scheme has minimal redundancy if it satisfies Conditions 2 and 3.
We prove the security property of the proposed modification of the secret sharing scheme. The probability of a secret being obtained by an attacker is provided, as well as we prove the computational security of this scheme. This information shows a possible level of security that allows working out a more detailed strategy for protecting data in cloud storages when applying this modification.
In the future work, we plan to study the applicability of the proposed scheme in different areas: homomorphic data encryption; efficient implementation of data encoding and decoding algorithms using artificial neural networks and minimally redundant modular code; generating moduli with the property of minimally redundant modular code; implementing safe and reliable storage systems for processing and transmitting data in cloud computing; building devices of low-power devices for use in the design of smart Internet of things, etc.
This work was supported by a grant from the Russian Science Foundation Grant No. 19-71-10033. (31) (32) [4] Tchernykh A, Babenko M, Chervyakov N, Miranda-López V, Kuchukov V, Cortés-Mendoza J
collusion secured data sharing scheme for cloud storage Int. J. Approx.Reason. 102 60–73 [5] Barsi F and Maestrini P 1973 Error Correcting Properties of Redundant Residue Number
Systems IEEE Trans. Comput. C–22 307–315 [6] Huang 1983 A Fully Parallel Mixed-Radix Conversion Algorithm for Residue Number
[7] Gbolagade K A and Cotofana S D 2009 An O(n) Residue Number System to Mixed Radix Conversion technique 2009 IEEE International Symposium on Circuits and Systems (IEEE) pp 521–524 [8] Tchernykh A, Babenko M, Chervyakov N, Miranda-Lopez V, Avetisyan A, Drozdov A Y,
[9] Sung-Ming Yen, Seungjoo Kim, Seongan Lim and Sang-Jae Moon 2003 RSA speedup with chinese remainder theorem immune against hardware fault cryptanalysis IEEE Trans.
Comput. 52 461–472 [10] Chervyakov N, Babenko M, Tchernykh A, Kucherov N, Miranda-López V and Cortés-Mendoza
[11] Chervyakov N I, Molahosseini A S, Lyakhov P A, Babenko M G and Deryabin M A 2017
remainder theorem Int. J. Comput. Math. 94 1833–1849 [12] Chervyakov N I, Babenko M G, Lyakhov P A and Lavrinenko I N 2014 An Approximate
[13] Chernyavsky A F, Kolyada A A 2009 Scaling Method and Algorithm in the Minimum
[14] Asmuth C and Bloom J 1983 A modular approach to key safeguarding IEEE Trans. Inf. Theory 29 208–210 [15] Krawczyk H 1993 Secret Sharing Made Short Proceedings in the 13th Annual International
Cryptology Conference, 93 136-146 [16] Quisquater M, Preneel B, Vandewalle J 2002 On the security of the threshold scheme based on the Chinese remainder theorem Proceedings in the International Workshop on Public Key Cryptography 199-210. [17] Babenko M, Tchernykh A, Chervyakov N, Kuchukov V, Miranda-López V, Rivera-Rodriguez R, Du Z and Talbi E-G 2019 Positional Characteristics for Efficient Number Comparison over the Homomorphic Encryption Program. Comput. Softw. 45 532–543 [18] Tchernykh A, Miranda-López V, Babenko M, Armenta-Cano F, Radchenko G, Drozdov A Y and Avetisyan A 2019 Performance evaluation of secret sharing schemes with data recovery in secured and reliable heterogeneous multi-cloud storage Cluster Comput. 22 1173–1185 [19] Tchernykh A, Schwiegelsohn U, Talbi E and Babenko M 2019 Towards understanding uncertainty in cloud computing with risks of confidentiality, integrity, and availability J.
Comput. Sci. 36 100581 [20] Lopez-Falcon E C, Miranda-López V, Tchernykh A, Babenko M and Avetisyan A 2019 Biobjective Analysis of an Adaptive Secure Data Storage in a Multi-cloud Communications in Computer and Information Science 979 pp 307–321 [21] García-Hernández L E, Tchernykh A, Miranda-López V, Babenko M, Avetisyan A, Rivera
Computer and Information Science 1087 pp 78–93 [22] Miranda-López V, Tchernykh A, Cortés-Mendoza J M, Babenko M, Radchenko G,
Storage Based on RNS Communications in Computer and Information Science 796 pp 370– 383 [23] Tchernykh A, Cortés-Mendoza J M, Bychkov I, Feoktistov A, Didelot L, Bouvry P, Radchenko
Parallel Distrib. Comput. 133 319–336