=Paper=
{{Paper
|id=Vol-2638/paper2
|storemode=property
|title=Computationally secure threshold secret sharing scheme with minimal redundancy
|pdfUrl=https://ceur-ws.org/Vol-2638/paper2.pdf
|volume=Vol-2638
|authors=Mikhail Babenko,Andrei Tchernykh,Elena Golimblevskaia,Nguyen Viet Hung,Vijay Chaurasiya
|dblpUrl=https://dblp.org/rec/conf/iccs-de/BabenkoTGHC20
}}
==Computationally secure threshold secret sharing scheme with minimal redundancy==
https://ceur-ws.org/Vol-2638/paper2.pdf
Computationally secure threshold secret sharing scheme with
minimal redundancy
M Babenko1, A Tchernykh2,3,4, E Golimblevskaia1, Nguyen Viet Hung5 and
V K Chaurasiya5
1
North-Caucasus Federal University, Stavropol, Russia
2
CICESE Research Center, Ensenada, BC, Mรฉxico
3
South Ural State University, Chelyabinsk, Russia
4
Ivannikov Institute for System Programming, Moscow, Russia
5
LeQuyDon Technical University, Hanoi, Vietnam
6
Indian Institute of Information Technology, Allahabad, India
E-mail: chernykh@cicese.mx
Abstract. 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.
1. Introduction
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) > โ/2$
.0) p&2. = ฮฑ leads to increasing the complexity of the
Copyright ยฉ 2020 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).
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.
2. RNS and its properties
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 |QU V (1)
๐ด ร ๐ต = N|๐" ร ๐" |QR , . . . , |๐T ร ๐T |QU V (2)
The equalities (1) and (2) show the parallel nature of RNS, free from bitwise transfers. In addition,
the numbers ๐X and ๐X have much smaller number of digits than the original numbers ๐ด and ๐ต.
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:
๐ = [โTX0"]๐X2" ]Q ๐X ๐ฅX [ (3)
_ `
where ๐X = ๐/๐X , ]๐X2" ]Q is the multiplicative inversion of ๐X modulo ๐X for ๐ = 1, . . . , ๐.
_
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:
๐ = ๐T ๐T2" ๐T2$ . . . ๐$ ๐" + ๐T2" ๐T2$ ๐T2e . . . ๐$ ๐" +. . . +๐$ ๐" + ๐" ,
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" V๐T2",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 (3) are divided by ๐, then we obtain the
relation
]`_rR ]
p
๐o = ` = qโTX0"
s_
Q_
๐ฅX q (4)
"
where the operation | โ |" means discarding the integer part of the number and the numbers
]`_rR ]
s_
๐X = , ๐ = 1,2, โฆ , ๐ (5)
Q_
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๐ (6)
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
p2" p
`
< ]โTX0" ๐wv ๐ฅX ]" โค ` (7)
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
"
0 โค ]โTX0"N๐X โ ๐wv V๐ฅX ]" < ` (8)
]`_rR ] ${ ]`_rR ]s 2}${ ]`_rR ]s } }${ ]`_rR]s }
_ _ s _ s
Since ๐X โ ๐wv =
s_
โ _
= _
, then
Q_ ${ โQ _ ${ โQ _
}${ ]`_rR ]s }
_ s
โTX0"N๐X โ ๐wv V๐ฅX = โTX0" _
๐ฅX . (9)
${ โQ _
Considering ๐ฅX โค ๐X โ 1, the left side of equality (9) satisfies the inequality:
}${ ]`_rR ]s } }${ ]`_rR ]s }
_ s " _ s
โTX0" _
๐ฅX โค ${ โขโTX0" [2โฌ ]๐X2" ]Q [ โ โTX0" _
โข (10)
${ โQ_ _ Q Q_
_
It follows from (8) and (10) that ๐ satisfies the inequality:
}${ ]`_rR ]s }
_ s
2โฌ โค ๐ โขโTX0" [2โฌ ]๐X2" ]Q [ โ โTX0" _
โข โค โSQ + ๐ โTX0"(๐X โ 1). (11)
_ Q Q_
_
where ๐๐ = โTX0" ๐X .
Denoting ๐ = โTX0"(๐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.
3. Minimally redundant code and its properties
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:
๐ = โT2" 2"
X0" ๐X ]๐X โ
๐ฅX ]Q + ๐T โ
๐ผ(๐), (12)
_
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:
๐ผโ(๐) ๐๐ ๐ผโ(๐) < ๐"
๐ผ(๐) = โข (13)
๐ผโ(๐) โ ๐T ๐๐ ๐ผโ(๐) โฅ ๐T โ ๐" โ ๐ + 2
โ "
where ๐ผโ(๐) = q[`U [ โโ
โT2"
X0" [Q [ โ
]๐X2" โ
๐ฅX ]Q q .
U Q _ Q _
U U 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 (14)
We consider four cases:
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.
Using (12) we can reduce the computational complexity of the data decoding algorithm.
4. Modification of the secret sharing scheme
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
๐ <๐ฝโ๐โ
๐ (15)
On the other hand, ๐ = |๐ฬ
|โ so that we can uniquely decode data if
๐<๐ (16)
Multiplying inequality (16) by ๐ and adding to (15), we have
(๐ + 1) โ
๐ < ๐ฝ (17)
Hence,
โข
๐< (18)
ลพลธ"
Since ๐ must satisfy two conditions (16) and (18), therefore:
โข
๐ < min ๐, ลพลธ"ยก (19)
We consider two cases:
โข
Case 1: ๐ < , then ๐ < ๐ and redundancy is equal to
ลพลธ"
ยคยฅยฆยง โU
_ยจR Q_ ยคยฅยฆยง โU
_ยจR Q_ ยคยฅยฆยง (ลพลธ")ลธยคยฅยฆยง โU
_ยจยฉยชR Q_
๐
โ > =1+ (20)
ยคยฅยฆยง โ ยคยฅยฆยง โยฉ
_ยจR Q_ 2ยคยฅยฆยง (ลพลธ") ยคยฅยฆยง โยฉ
_ยจR Q_ 2ยคยฅยฆยง (ลพลธ")
โข โข
Case 2: ๐ โฅ ลพลธ", then ๐ < ลพลธ"
ยคยฅยฆ โU Q
ยง _ยจR _ ยคยฅยฆยง โU
_ยจR Q_ ยคยฅยฆยง (ลพลธ")ลธยคยฅยฆยง โU
_ยจยฉยชR Q_
๐
โ ยคยฅยฆ โข2ยคยฅยฆ = =1+ (21)
ยง (ลพลธ")
ยง ยคยฅยฆยง โยฉ
_ยจR Q_ 2ยคยฅยฆยง (ลพลธ") ยคยฅยฆยง โยฉ
_ยจ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:
๐ โ
๐ โค ๐ฝ โค (๐ + 1)๐ (22)
Dividing (22) by ๐, we get:
โข
๐ โคโ โค๐+1 (23)
โข
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:
Condition 1: ฮฒ > โ/2$
.0) ๐T2X (determines that the proposed scheme is a threshold)
โข
Condition 2: ๐ < $ and gcd(๐, ๐ฝ) = 1.
โข
Condition 3: ๐ = ยซโยฌ.
Condition 4. 2ยฎ2" < ๐" < ๐$ < โฏ < ๐T is the minimum redundant modular code.
In contrast to the Asmuth-Bloom scheme [14], the proposed scheme provides data security with
minimum redundancy.
5. Properties of the proposed scheme
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 ๐ยฒ โค โโบ2$ X0) ๐T2X . Consequently, the
โ " " "
probability to compute ๐ with the known ๐ , satisfies the equality ๐๐(๐ผ) โค ยธ โค Q < $ยปrR
ยท ยบ Urยฉยช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 ยฉยชR , where ๐(๐ฅ) is Euler function.
ยผ(โข)2$
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โบ (24)
ร ร ร
Since the number of numbers that are non-coprime to ๐ฝ and smaller ๐ฝ is, on the one hand, equal to
โข
โยพโยฒ ยซ ยฌ, on the other hand, substituting ๐ฝ โ ๐(๐ฝ) in (24), we find that the number of numbers non-
pร
โข
coprime to ๐ฝ and less than $ is less then:
"
$
N๐ฝ โ ๐(๐ฝ)V + 2โบ (25)
โข
Therefore, the number of numbers coprime to ๐ฝ and less than is greater than or equal to:
$
โข " " ยผ(โข)2$ยฉยชR
$
โ $
N๐ฝ โ ๐(๐ฝ)V + 2โบ ยก = $ ๐(๐ฝ) โ 2โบ = $
(26)
$
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 ๐ด
1
[Pr ๐ด ๐ทN๐ถ (") , ๐ (") Vยก = 1ยก โ Pr ๐ด ๐ทN๐ถ ($) , ๐ ($) Vยก = 1ยก[ < ,
๐๐๐๐ฆ(๐, ๐)
where ๐๐๐๐ฆ(๐, ๐) is the some polynomial over the amount of possible shares.
Theorem 2. The proposed scheme is computationally secure if ๐ โค 4.
Proof. To prove the computational security of proposed scheme, we use the auxiliary inequality.
โ ๐, ๐, ๐ โ ๐
: |๐ โ ๐| โค |๐ โ ๐| + |๐ โ ๐| (27)
Let = Pr ๐ด ๐ทN๐ถ (") , ๐ (") Vยก = 1ยก, ๐ = Pr ๐ด ๐ทN๐ถ ($) , ๐ ($) Vยก = 1ยก, ๐ = PrN๐ทN๐ถ (") , ๐ (") V = 1V .
We have:
[Pr A DNC(") , S(") Vยก = 1ยก โ Pr A DNC($) , S($) Vยก = 1ยก[
โค [Pr A DNC(") , S(") Vยก = 1ยก โ PrNDNC(") , S(") V = 1V[ (28)
+ [Pr A DNC($) , S($) Vยก = 1ยก โ PrNDNC(") , S(") V = 1V[
where PrN๐ทN๐ถ (") , ๐ (") 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 โTX0" ๐X , then the probability is
(") (")
โโบX0" ๐X 1
Pr A DNC ,S Vยก = 1ยก โค T = T ,
โX0" ๐X โX0โบลธ" ๐X
($) ($)
โโบX0" ๐X 1
Pr A DNC ,S Vยก = 1ยก โค T = T ,
โX0" ๐X โX0โบลธ" ๐X
1
PrNDNC (") , S (") V = 1V = .
โโบX0" ๐X
From Condition 4 and k โฅ 4, it follows that p"/ < โ/.0" p. < 2/ p"/ and p"&2/ < โ&.0/ลธ" p. <
2&2/ p"&2/ .
" " " " " "
Therefore, $ยฉ Qยฉ < โยฉ < Qยฉ and $Urยฉ QUrยฉ < โU Q
< QUrยฉ .
R _ยจR Q_ R R _ยจยฉยชR _ R
Let us estimate terms of (28):
" " " "
[Pr A DNC (") , S (") Vยก = 1ยก โ PrNDNC (") , S (") V = 1V[ < max รQUrยฉ โ $ยฉ Qยฉ , Qยฉ โ $Urยฉ QUrยฉ ร (29)
R R R R
" " " "
[Pr A DNC ($) , S ($) Vยก = 1ยก โ PrNDNC (") , S (") V = 1V[ < max รQUrยฉ โ $ยฉ Qยฉ , Qยฉ โ $Urยฉ QUrยฉ ร .
R R R R
By substituting (29) in (28), we obtain:
[Pr ๐ด ๐ทN๐ถ (") , ๐ (") Vยก = 1ยก โ Pr ๐ด ๐ทN๐ถ ($) , ๐ ($) Vยก = 1ยก[ (30)
1 1 1 1
< 2 โ max โข T2โบ โ โบ โบ , โบ โ T2โบ T2โบ ร .
๐" 2 ๐" ๐" 2 ๐"
It means that the proposed scheme satisfies the formal definition of computational security.
The theorem is proven.
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 (31)
_ _
Since for all โ [1, โฆ , ๐] gcd(Q, ๐X ) = 1, there exist ๐๐๐๐"ร , ๐๐๐๐$ร , Qโฒ such that the following
equations are satisfied:
(") ($)
๐X = ]๐ ($) + Qโฒ โ
๐๐๐๐$ร ]Q , ๐X = ]๐ (") + Qโฒ โ
๐๐๐๐"ร ]Q . (32)
_ _
From (31) and (32), it follows that to unambiguously map (๐ (") , ๐ถ (") ) and (๐ ($) , ๐ถ ($) ) , ๐ is
required. Since ๐ is not known, our scheme is computationally secure.
6. Conclusion
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.
Acknowledgments
This work was supported by a grant from the Russian Science Foundation Grant No. 19-71-10033.
References
[1] ลขiplea F L and Drฤgan C C 2014 A necessary and sufficient condition for the asymptotic
idealness of the GRS threshold secret sharing scheme Inf. Process. Lett. 114 299โ303
[2] Drฤgan C C and Tiplea F L 2018 On the asymptotic idealness of the Asmuth-Bloom threshold
secret sharing scheme Inf. Sci. (Ny). 463โ464 75โ85
[3] Muhammad Y I, Kaiiali M, Habbal A, Wazan A S and Sani Ilyasu A 2016 A secure data
outsourcing scheme based on Asmuth-Bloom secret sharing Enterp. Inf. Syst. 10 1001โ1023
[4] Tchernykh A, Babenko M, Chervyakov N, Miranda-Lรณpez V, Kuchukov V, Cortรฉs-Mendoza J
M, Deryabin M, Kucherov N, Radchenko G and Avetisyan A 2018 AC-RRNS: Anti-
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
Applications IEEE Trans. Comput. Cโ32 398โ402
[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,
Rivera-Rodriguez R, Radchenko G and Du Z 2020 Scalable Data Storage Design for Non-
Stationary IoT Environment with Adaptive Security and Reliability IEEE Internet Things J.
[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
J M 2019 AR-RRNS: Configurable reliable distributed data storage systems for Internet of
Things to ensure security Futur. Gener. Comput. Syst. 92 1080โ1092
[11] Chervyakov N I, Molahosseini A S, Lyakhov P A, Babenko M G and Deryabin M A 2017
Residue-to-binary conversion for general moduli sets based on approximate Chinese
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
Method for Comparing Modular Numbers and its Application to the Division of Numbers in
Residue Number Systems* Cybern. Syst. Anal. 50 977โ984
[13] Chernyavsky A F, Kolyada A A 2009 Scaling Method and Algorithm in the Minimum
Redundant Modular Counting System Reports of the NAS of Belarus 53 29โ37
[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 Bi-
objective 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-
Rodriguez R, Radchenko G, Barrios-Hernandez C J, Castro H and Drozdov A Y 2020 Multi-
objective Configuration of a Secured Distributed Cloud Data Storage Communications in
Computer and Information Science 1087 pp 78โ93
[22] Miranda-Lรณpez V, Tchernykh A, Cortรฉs-Mendoza J M, Babenko M, Radchenko G,
Nesmachnow S and Du Z 2018 Experimental Analysis of Secret Sharing Schemes for Cloud
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
G and Borodulin K 2019 Configurable cost-quality optimization of cloud-based VoIP J.
Parallel Distrib. Comput. 133 319โ336