Field of the Invention

The present invention relates to the field of cyber security. More particularly, the invention relates to a system and method for performing CRT-based multiplicatively homomorphic secret-sharing with Perfect Information-Theoretic (PIT) security.

Background of the Invention

Secret sharing and secure multiparty computation are essential in securing data and computations. Perfect information-theoretic (PIT) secure multiparty computation is preferred over computational security. A computationally secure, fully homomorphic system has the advantage that it can perform secure computation on a single server (in general, honest but curious; see, e.g., [10]). A homomorphism is a map between two algebraic structures of the same type (e.g. groups, rings) that preserves the operation of the structures [4], The equation /(% ® y) = /(%) ® f(y), where ' @ ' and ' ® ' are binary operations, characterizes a homomorphic operation. It is also possible that f is a homomorphism involving two binary operations. A partial homomorphism may be defined only on a certain subset, and is required to satisfy the property above for x,y in the subset, such that x @ y is also in the subset. See also [16],

On the other hand, the computation-based solution is (j) based on an unproven candidate for a one-way function, (jj) is required to protect an encryption/decryption key, and (iti) has no redundancy as the server can erase the entire data. Thus, the distributed PIT-secure multiparty computation is employed in many scenarios.

There is a growing need for cloudifying storage and computing. Users of cloud services want to be sure that their sensitive data is not exposed to the service provider (i.e., convert and/or migrate data and application programs in order to make use of cloud computing). Cloud computing allows companies to focus on their primary objective while cloud providers handle the storage and computing infrastructure.

Secure migration of data and computation to the cloud is of one of the following types:

• Fully Homomorphic Encryption (FHE), e.g., [9]; also, a partially computationally secure distributed version of FHE, e.g., [15],

• Partially Homomorphic Secret Sharing Schemes (typically with respect to addition), e.g., [1, 7, 11],

• Secure Multiparty Computation with communication between the participants, e.g., [12],

FHE, where data is encrypted to hide its content, suffers from some serious drawbacks:

• Encryption is done using a key that needs to be stored.

• Encryptions are mainly based on the (unproven) hardness of (one-way) computing problems. Those problems are assumed to imply the need for a bruteforce search for the encryption keys. Unfortunately, the most popular functions, DH (based on Discrete Log) and RSA (based on Integer Factorization), can be broken using Shor's algorithm, designed for emerging quantum computing. Furthermore, the recently proposed (by NIST) post-quantum functions are also not proven to be hard for (quantum) computers to solve.

• Encryption may be very time-consuming, for example, calculating powers on numbers done in RSA or performing multiple cycles of mathematical functions and hashes.

The other approaches, besides encryption, are distributed Secret Sharing (SS) and distributed Secure Multiparty Computations (SMC or SMPC) based on PIT-security proofs. These methods are based on mathematical proofs that ensure the secret data is secure as long as the adversary does not have a sufficient number of shares defined by a threshold to recover the secret.

The first secret-sharing schemes were presented by Shamir [7] and Blakley [11], Later, many schemes were presented, including schemes based on the Chinese Remainder Theorem (CRT - the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime (no two divisors share a common factor other than 1), e.g., Asmuth-Bloom's scheme [1] and Mignotte's scheme [2], The above schemes are designed to respect a threshold of t out of n shares to reconstruct the secret, where t < n shares are sufficient to reconstruct the secret. Such a scheme is a threshold scheme.

Some of the above schemes are partially homomorphic, and others are non- homomorphic.

Efficient versions, where the communication overhead (which is originally quadratic in the number of participants) is dramatically reduced, are of great interest. Therefore, it is desired to extend the communication-less addition homomorphism of the original secret sharing schemes presented in [7], to be a homomorphism of both addition and multiplication. This allows performing communication-less distributed secure multiparty computations.

Secret Sharing Schemes are typically defined by two parameters, n and t. Here, n is the number of participants, and t is the reconstruction threshold. For simplicity, we take [n] = {1,2, ..., n} as the set of all participants. The parameter t is the minimum number of participants to reconstruct the secret. The secret is a bit string or belongs to the ring of integers modulo some M and will be denoted by S. An important notion is that of access structure. An access structure [18] is a collection of sets of participants; these are the authorized sets that should be capable of reconstructing the secret data S. The access structure is denoted by c/Z.

In the sequel, the possible secrets belong to some domain S. The secret is distributed according to some probability measure 2) on S. Given a secret S, the shared part of the secret given, by the dealer D, to each participant i is denoted by S[. The domain to which belongs is denoted by S _t .

Definition 1

A Perfect Secret Sharing Scheme [19] is a secret sharing scheme, satisfying the following two conditions:

• Correctness: Any qualified set of participants can reconstruct the secret.

• Perfect Privacy: No unqualified set of participants can get any information about the secret. More formally:

For every set P G <A and S' G £ where S? G Sj,j G G c [n],:

Secret Sharing Schemes may be more flexible. Ramp Secret Sharing Schemes, to be defined momentarily, have two thresholds, t and s, where s < t — 1 (see [17]). The additional parameter s is a secrecy bound. This bound is the maximum number of participants who cannot learn any information about the secret by cooperating. Thus, for a set of participants P, there are three ranges in ramp SSS:

1. |G| < s: No information leak at all.

2. s < |G| < t: Might be a partial information leak.

3. |G | > t: Full reconstruction.

Definition 2

A Ramp Secret Sharing Scheme [17] is a scheme that uses a secrecy bound s that should satisfy the following two conditions:

Correctness: Any qualified set of participants can reconstruct the secret. • Perfect Ramp Privacy: For every set of participants P, \P\ < s, given a secret S with distribution 2), the secret distribution stays the same, meaning the probability of the secret being equal to a specific element S' E S stays the same even when knowing the shared secret data held by the participants of P. Namely:

For every have: p[

Thus, a perfect SSS is a ramp SSS with s = t — 1.

Therefore, in a ramp SSS:

1. 1 < s < t < n.

2. We may have s < t — 2.

3. It is possible that a set of participants smaller than t can reconstruct the data in ramp SSS.

4. It is possible that a set of participants larger than s cannot learn anything about the data.

In some schemes, participants work with several moduli. A participant may hold several shares of parts of a secret, each with respect to a different modulus. The various moduli used by the participants are denoted by m _lt m ₂ , m _r . When writing expressions such as m _i+ j, we understand that i + j is taken modulo r.

Conventional SMPC is not sufficiently secured since it requires communication between parties. Using encryption schemes is also problematic, since it requires key that may be stolen and

It is therefore an object of the present invention to provide a system and method for performing CRT-based multiplicatively homomorphic secret-sharing with Perfect Information-Theoretic (PIT) security, while reducing the communication overhead. It is another object of the present invention to provide a system and method for performing CRT-based multiplicatively homomorphic secret-sharing with Perfect Information-Theoretic (PIT) security, with homomorphism of both addition and multiplication.

It is a further object of the present invention to provide a system and method for performing CRT-based multiplicatively homomorphic secret-sharing with Perfect Information-Theoretic (PIT) security, while performing communication-less distributed secure multiparty computations.

Other objects and advantages of the invention will become apparent as the description proceeds.

Summary of the Invention

A method for performing CRT-based homomorphic secret-sharing with Perfect Information-Theoretic (PIT) security, comprising: a) determining a secret S and a number of participants n, each being a computerized device or a server; b) performing, using a computerized device comprising at least one processor, a secret distribution phase by: b.l) determining a general moduli set and a specific moduli set for each participant; b.2) calculating a general multiplicative modulo M _n as a product of all moduli; b.3) selecting a plurality of n — 1 random numbers and assigning the selected random number to each participant; b.4) calculating a modified secret S _mix being the product of the secret and the plurality of random numbers, under the multiplicative modulo; b.5) sending to each participant an adapted secret S _mix . being the modified secret after passing his corresponding modulo; b.6) to each participant, assigning modified random numbers being the random numbers, after passing the moduli of the participants corresponding to the random numbers; c) performing using the computerized device, a secret reconstruction phase by: d) reconstructing the modified secret S _mix by applying a CRT operator to all adapted secrets, using the multiplicative modulo; e) reconstructing each random number by applying a CRT operator to all modified random numbers, using the multiplicative modulo; f) calculating the inverse of each reconstructed random number; and g) reconstructing the secret by multiplying modified secret S _mix by the inverses of all reconstructed random numbers.

A method for performing CRT-based multiplicatively homomorphic secret-sharing with Perfect Information-Theoretic (PIT) security, comprising: a) determining a plurality of secrets (S',S”, ... ) and a number of participants n, , each being a computerized device or a server; b) calculating, using a computerized device comprising at least one processor, the product S* of the secrets; c) performing, by the computerized device, a secret distribution phase by: c.l) determining a general moduli set and a specific moduli set for each participant; c.2) calculating a multiplicative modulo M _n of all moduli; c.3) selecting a plurality of random numbers; c.4) for each secret, calculating a modified secret S' _mix ,S" _mix ,... being the multiplicative modulo of the product of the secret and the plurality of random numbers; c.5) sending to each participant an adapted secret S' _mix . , S" _mix . being the modified secret after passing his corresponding modulo; c.6) to each participant, assigning modified random numbers being the random numbers, after passing the moduli of the participants corresponding to the random numbers; d) performing, by the computerized device, a multiplication phase by: d.l) for each participant, multiplying all adapted secrets S' _mi . S" mi ■ ■ d.2) for each participant, multiplying all his adapted random numbers r\, r' ₂ r' _s ; r" _r , r" ₂ , . , r” _s ; e) performing, by the computerized device, a secret reconstruction phase by: f) reconstructing a blinded secret S* _mix by applying a CRT operator to all blinded secrets S* _mix ., each being the product of modified secrets that correspond to each participant, using the multiplicative modulo; g) reconstructing blinded random r*i by applying a CRT operator to all blinded randoms r*, each being the product of modified secrets that correspond to each participant, using the multiplicative modulo; h) calculating the inverse of the blinded random number r*,; and i) reconstructing the product of secrets by multiplying the blinded secret by the inverse of the blinded random number.

Multiplications may be applied to a simple multiplicative homomorphic SSS.

A method for performing CRT-based additively homomorphic secret-sharing with Perfect Information-Theoretic (PIT) security, comprising: a) determining a plurality of secrets (S',S", ... ) and a number of participants n, , each being a computerized device or a server; b) performing, using a computerized device comprising at least one processor, a secret distribution phase by: b.l) determining a modulo for each participant; b.2) calculating a multiplicative modulo M _n of all moduli; b.3) selecting a plurality of random numbers; b.4) for each secret, calculating a modified secret S' _mix ,S" _miX ,... being the multiplicative modulo of the product of the secret and the plurality of random numbers; b.5) sending to each participant an adapted secret S' _mix . , S" _mix . being the modified secret after passing his corresponding modulo; b.6) to each participant, assigning modified random numbers being the random numbers after passing the moduli of the participants corresponding to the random numbers; c) performing, by the computerized device, an addition phase by: c.l) assigning a plurality of random numbers r _1; ..., r _s to each addend; c.2) allowing each participant i to calculate S' _Tlix . + S^ _ix . without changing the random numbers; d) performing, by the computerized device, a secret reconstruction phase by: e) reconstructing a blinded secret S* _mix by applying a CRT operator to all blinded secrets S* _mix ., each being the product of modified secrets that correspond to each participant, using the multiplicative modulo; f) reconstructing blinded random r* _; by applying a CRT operator to all blinded randoms r*, each being the product of modified secrets that correspond to each participant, using the multiplicative modulo; g) calculating the inverse of the blinded random number r*; and h) reconstructing the sum of secrets by multiplying the blinded secret by the inverse of the blinded random number.

The method may further comprise the step of: a) calculating (S'_mix • S*mix + S"_mix • S**mix) • S ^@ mix + (S'_mix • S ^# mix + S"_mix • S ^## mix) • S ^@@ mix, where S' and S" are the real secrets, and all the remaining secrets are blinding secrets. b) selecting equal random numbers for: b.l) S'_mix • S*mix and S"_mix • S**mix; b.2) S'_mix • S ^# mix and S"_mix • S ^## mix; b.3) (S'_mix • S*mix + S"_mix • S**mix) • S ^@ mix and (S'_mix • S ^# mix + S"_mix •

S ^## mix) • S ^@@ mix, such that S* • S ^@ + S ^# • S ^@@ = 1 and S** • S ^@ + S ^## • S ^@@ = 1 and S** are randomly chosen, such that S ^# = — c) reconstructing S' + S" as = S' • (S* • S ^@ + S ^# • S ^@@ ) + S" • (S** • m _t < m ₂ < ••• < m _n may be the co-primes that the modulus operations are performed on the participants' side, thereby obtaining perfectly secured calculations.

Leakage may be avoided by choosing random numbers such that during each addition, the addends have the same random numbers. Additions may be applied to a simple additive SSS or to a ramp additive homomorphic SSS.

Additions and multiplications may be applied to logic and arithmetic circuits, for calculating logical and arithmetical functions.

Whenever additions cannot be performed with no communication, multiplicative and additive participants may be chosen.

Participants of the same type may not be familiar with each other.

A streaming model may be implemented that requires all participants to be honest and can still be curious.

Whenever functions are known, the random numbers for each function may be calculated in advance by an arithmetic circuit.

Additions of blinded secrets may be performed by: a) to each participant i, assigning: a.l) pre-addition dockers, one for each addend; a.2) an addition docker, for performing the addition; b) calculating, by a first pre-addition docker having parameters S^, S@ _ix , r ^# ,and r* , a first pre-addition result: ■ s; _nix (mod(m _i ')), r' • r ^# • r*(mod(m _i+1 )) c) calculating, by a second pre-addition docker having parameters Smix’ S®®, ^r## ,and r**, a second pre-addition result: (S" _ix ■ S^ _ix + the first docker has no knowledge about the parameters of the second docker, and vice versa; d) receiving the results by the addition docker; p l erforming by the addition docker, ^f the addition • St 1L 11/ _j (.✓ _Y V + S 1® I LL.-A^i •

Brief Description of the Drawings

The above and other characteristics and advantages of the invention will be better understood through the following illustrative and non-limitative detailed description of preferred embodiments thereof, with reference to the appended drawings, wherein:

Figs. 1-3 illustrate an example of distributing and reconstructing a secret, in case of a simple Secret Sharing Scheme (SSS);

Figs. 4-6 illustrate an example of distributing and reconstructing a secret, in case of a multiplicative (SSS);

Fig. 7 illustrates an example of an arithmetic circuit; and

Fig. 8 illustrates another implementation of additions of blinded secrets by each participant i using addition dockers.

Detailed Description of the Invention

The present invention provides a system and method for performing CRT-based multiplicatively homomorphic secret-sharing with Perfect Information-Theoretic (PIT) security, while reducing the communication overhead. The method allows performing CRT-based multiplicatively homomorphic secret-sharing with Perfect Information-Theoretic (PIT) security, with homomorphism of both addition and multiplication, to perform communication-less distributed secure multiparty computations. The new CRT-based secret sharing scheme with supports homomorphic multiplications and additions. This allows calculating functions on the secret data while keeping the data safe and performing computations without communication between the participants. In order to better understand the new proposed method, some of the known SSS homomorphic methods will be reviewed:

Simple additive SSS

This scheme has a threshold of t = n, namely it is an n out of n scheme. Let be the additive group on which the calculations are being made. This scheme has two phases:

• Distribution phase:

The dealer D selects uniformly random elements S ₁ ,S ₂ , ... ,S _n-1 E 1 _M . D then computes S _n = S — $i- Finally, D gives to participant i for 1 < i < n.

• Reconstruction phase:

Let P c [n] be a set of participants gathered to reconstruct the secret. The participants compute the secret S by summing all their secret shares. RF is the reconstruction function.

Here, 1 denotes "none".

This scheme is also additive homomorphic. In fact, let S' and S" be secrets and S[ and S" the respective shares of participant i. Clearly,

Each participant i can calculate S- + S” and send the sum to the user. Therefore, the scheme is an additive homomorphic scheme.

Simple multiplicative homomorphic SSS

This scheme is very similar to the Simple additive SSS, but in this case, the product of the shared values gives the secret. Secrets to be 0 should not be allowed. More generally, any non-invertible elements of Thus, secrets belong to the multiplicative group TL _M * of TL _M . The shared secrets given are also from TL _M * and the share of participant n is S _n = S • (LlETi ¹ S’;) ^-1 -

This scheme is also multiplicative homomorphic due to the commutativity of 1 _M * .

Ramp additive homomorphic SSS

This scheme is based on the above-mentioned ideas of Asmuth-Bloom's SSS [1], It has a threshold of t = n, with a security factor of s. The secrets and the calculations are all in 1 _M .

This scheme has two phases:

A distribution phase:

D chooses a set of pairwise prime integers m ₁ < m ₂ < ••• < m _n and uses their product All participants know all mi's. D randomly chooses s elements computes

Then D computes and distributes the vector

St = (S _mix (mod _m .), r ₁ (mod _m.+ J, ..., r _s (rnod _m.+s )) as the shared part of each participant i.

A reconstruction phase:

Let P be a set of participants gathered to reconstruct the secret. If P = [n], the set knows S_mix and all r/s modulo each of the mi's, and can therefore find them by CRT: r _s = CRT(S _{l s} , ...,S _{n s} ).

Here, CRT denotes the function computing an element of by its residues modulo the mi's. Then they are able to compute S = S_mix — ^r j-

If \P | < s, they get no information [5], This scheme is also additive homomorphic. In fact, let S' and S" be secrets. Let r[, ..., Ts be the random elements drawn for S' and rf, ..., r” those drawn for S". (the mi's are fixed once and for all) Let S'_mlx and S"_mlx be the corresponding blinded secrets. Each participant i has the secret shares of each blinded secret and blinding randoms:

We have:

Each participant can calculate S' _mir . + S'' _mir . and r,'. + r,'.' for each 1 < / < s and send them to the user. Using CRT, the user then computes S' + S". Thus, the scheme is an additive homomorphic scheme.

The method for performing CRT-based multiplicatively homomorphic secret-sharing provided by the present invention is similar to the ramp additive SSS, but uses multiplications instead of additions. As in the simple multiplicative SSS, the secrets and random elements are restricted to Z^.

The distribution phase:

The mi's and the r^'s are as in the ramp additive SSS, except that the rj's need to lie in ZM- D computes S_mix = S • fli=i ^r i< and then distributes the shared set of each participant 1 < i < n:

S, = (S_mix(mod_ m _i '),r ₁ (mod_ m _i+1 ), ... ,r _s (mod_ m _i+s )).

The reconstruction phase:

The reconstruction is as in the ramp additive SSS, except for the final calculation: S = S_mix • nf=i ^r i ^-1 - For providing proofs, several basic properties of will play an important role. In particular, Z^ is the direct product of the groups Z^, 1 < i < n. Also, all groups who have a generator, have the property that any element of a group can be obtained from each element by applying the group operation [20], The following lemma is well known (in much more generality).

Lemma 1

Let G be a finite multiplicative group. Given two elements g _1; g ₂ e G, chosen uniformly randomly from G, the product g _t g ₂ is also uniformly distributed. Moreover, if one of the elements is chosen uniformly randomly, and the other according to any distribution 2), the product is still uniformly distributed.

Correctness

Theorem 1

For P = [n], the reconstruction phase above always returns the secret.

Proof: Participant 1 knows S_mix modulo m ₁₇ participant 2 - modulo m ₂ , and so forth. When all participants cooperate, S_mix is known modulo all m/s, and by CRT, we can find S_mix e Z _M itself. Similarly, each Fj is known modulo all m/s: participant 1 knows it modulo rrij ₊₁ , participant 2 - modulo rrij ₊₂ , and so forth. Once this information is obtained, the inverses Fj ^-1 , is found and compute S by the definition of S_mix:

Therefore, the Scheme is Multiplicatively Homomorphic

Theorem 2

The ramp multiplicative scheme is multiplicatively homomorphic. Proof. The proposed multiplicative scheme is multiplicatively homomorphic. In fact, let S' and S" be secrets. Let r], ..., rs be the random elements drawn for S' and r^' , ... , r" those drawn for S". Each participant i has the secret shares of each blinded secret and blinding randoms:

We have:

Each participant can calculate S' _mi . • S" _miXj and r-. • r-.' for each 1 < j < s and send them to the user. Using CRT, the user then computes:

S'mix • S"mix, r] • r]', ... , r' • r^', then finding the inverses:

(ri • ri')’ ¹ . Ol - r")- ¹ , and finally computing S' • S".

Thus, the proposed scheme is multiplicatively homomorphic.

The proposed scheme satisfies the security requirements, as will be shown below:

Theorem 3

In the ramp multiplicative scheme, no set P of participants of size up to s can get any information by cooperation between them. In particular, if s = n — 1 then the scheme is perfect.

The following exemplary proof will be for the case s = 1. The full proof for the general case is detailed in Appendix B below.

It may be assumed that P = {1}. If the secret is S we have to show that, for each S' e <S, if P[S = S'] = p (according to the distribution 2)), then the conditional probability of the event S = S', given the information participant 1 has, according to the proposed scheme, is still p.

The domain of S mix Its size is I^M I = <p(M) = n"=i <p(mi), where cp is Euler's totient function.

For arbitrary fixed have

P [ L ^r i 1 = x] J = <p(M) and, by using Lemma 1,

It is assumed that the data that participant 1 has is r _t = x ₀ (mod m ₂ ) and S mix = y ₀ (mod m-J for some specific x ₀ ,y ₀ . The last two probabilities do change when the participant's data is known. Yet, the conditional probability of the secret S being equal to S' does not change, namely that:

P[S = S'l^ = x ₀ (mod m ₂ ), S mix = y ₀ (mod m _t )] = p. (Eq. 1)

Indeed, by using Bayes' theorem:

P[S = S' |r _t = x ₀ (mod_ m ₂ ), S_mix = y ₀ (mod_m ₁ )]

The event in the fraction numerator on the right-hand side is that r _t assumes a specific value modulo mi and a specific value modulo m ₂ . In contrast, its value modulo all other mj's is arbitrary (as long as it is invertible). Hence the numerator is l/cpCm-J • l/(p(m ₂ ). Since the same holds for any instead of S', the denominator assumes by the law of total probability the same value. This proves Eq. 1.

Addition expansion of the proposed multiplicative method

In order to perform addition in the proposed scheme, it is required that the randoms' of each addend (monomial) will have equal randoms, for simplicity in case of sum of two secrets: S_mix' = S' • r _t • ... • r _s ,

S_mix" = S" • r _t • ... • r _s .

When performing the addition, each participant i calculates S^ _ix + S" _ix and does not change the randoms.

The user then finds (S' _Tlix + S" _ix ) and r _1; ..., r _s using CRT. Finally, since:

S_mix' + S_mix" = (S' + S") • r _t • ... • r _s =>

S' + S" = (S_mix' + S_mix") • (r _t • ... • r _s ) ^-1

The user can calculate S' + S''.

Performing fully homomorphic operations on secret data is equivalent to being able to calculate any polynomial function on secret data. Trying to perform addition in a method where the secrets are being summed with each other lead to the following problem:

Taking the simple scenario of s = 1, summing up two secrets S' and S". The shares parts participant i has are S'mix(mod_ mi), S"mix(mod_ mi), r'(mod_ m _i+1 ) and r"(mod_ m _i+1 ). Participant i knows some additional information allowing the addition, namely that r' = r''.

Therefore the participant can calculate: thereby revealing the ratio among the two secrets under the participant's modulo of

S ^u mi .x*

In order to eliminate such an information leakage, the difference between the ranges of M _n and m, is exploited. The following computation is used:

(S'_mix • S*mix + S"_mix • S**mix) • S ^@ mix + (S'_mix • S ^# mix + S"_mix

• S ^## mix) • S ^@@ mix.

Where S' and S" are the real secrets, and all the other "secrets" are for blinding. We require that the randoms of the following couples are equal: 1. S'_mix • S*mix and S"_mix • S**mix, namely that r' • r* = r" • r**, meaning r* is randomly chosen, while r** is determined accordingly.

2. S'_mix • S ^# mix and S"_mix • S ^## mix, namely that r' • r ^# = r" • r ^## meaning r ^# is randomly chosen, while r ^## is determined accordingly.

3. (S'_mix • S*mix + S"_mix • S**mix) • S ^@ mix and

(S'_mix • S ^# mix + S"_mix • S ^## mix) • S ^@@ mix, namely that, r* • r ^@ = r ^# • r ^@@ or equally r** • r ^@ = r ^## • r ^@@ , meaning r ^@ is randomly chosen, while r ^@@ is determined accordingly.

We further restrict these randomly chosen values to obey the following equations:

S* • S ^@ + S ^# • S ^@@ = 1, (1)

S** • S ^@ + S ^## • S ^@@ = 1. (2)

Namely, S* and S** can be randomly chosen, such that S ^# and S ^## =

Let S = S' + S". We need to show that each participant i is able to find S_mix modulo mi and the r corresponding to S modulo m _i+1 . Indeed, the participants can calculate:

(S'_mix • S*mix + S"_mix • S**mix) • S ^@ mix + (S'_mix • S ^# mix + S"_mix • S ^## mix) • S ^@@ mix

= S_mix = S • 2 • r' • r* • r ^@ , modulo mj, and also 2 • r' • r* • r ^@ = r modulo m _i+1 . Finally, when reconstructing both S_mix and r modulo M _n we can get the desired result S = S' + S".

Examining the knowledge of a participant, consisting of:

S'_mix(mod_ mi), S"_mix(mod_mi), S*mix(mod_mi), S**mix(mod_ mj), S ^# mix(mod_ mj), S ^## mix(mod_ mj), S ^@ mix(mod_ mj), S ^@@ mix(mod_ mj), r'(mod_ rrii ₊₁ ), r"(mod_ rrii ₊₁ ), r*(mod_ rrii ₊₁ ), r**(mod_ rrii ₊₁ ), r ^# (mod_ m _i+1 ), r ^## (mod_ m _i+1 ), r ^@ (mod_ m _i+1 ), r ^@@ (mod_ m _i+1 ).

We conclude that the participant does not know the value of any r in (mod_ mi), moreover, the ratio information leakage of the previous scheme is eliminated, as the following equations demonstrate. Trying to get information from all the equalities of couples mentioned before:

„ S'_mix-S*mix . . „*

1. - S»_mix-S"mix is uniformly ¹ random in Z _M ^M n . . . .. . has no imp K hcation on ratio leakage. has no implication on ratio leakage.

Addition under the limitation of calculations with a threshold

As defined in the proposed scheme, mi < m ₂ < ••• < m _n are the co-primes that the modulus operations are performed on the participants' side. Therefore, when the calculations are done under the limit of m ₁₇ all results and intermediate results are elements of Z^. This limitation ensures that all the calculations are perfectly secured by the security analysis described above.

Unbounded calculations

In this case, the security analysis should deal with different scenarios. If, for example, a calculation or an intermediate calculation of S res is not from Z^, then there is a modulo m, such that mi|S _{res m} , meaning that the participant with the m, modulo used for S mix can know the equivalence class of the real secretl: S = S + k • m,, Elk.

Since all the randoms are from 1 _M * , they do not change the effect of zero divisors. Arithmetic circuit extension

By parsing the equation in advance, it is possible to calculate all the randoms needed for any given function. It can be ensured that each addend's randoms are equal for each addition operation in the function. To achieve that and avoid leakage, the following steps are performed:

1. For each addition, fix the addition using the method described in the addition expansion of our original scheme.

2. Choose randoms such that for each addition have addends with the same randoms.

Byzantine fault tolerance

It is possible to make the proposed scheme a threshold scheme with threshold t < n, as explained above. Therefore, it is possible to create a byzantine fault tolerance algorithm for the proposed scheme, based on [13] and [14], The most trivial way is to transform the proposed scheme to a threshold scheme with t < n using redundancy [6], Then during the reconstruction phase, check all results reconstructed from sets of a sufficient amount of participants ( |P| > t). After reconstructing the results, take the result from the majority of the sets (if there is no majority, then there were more adversaries than we can handle), see, e.g., [13] and the references therein for more efficient schemes.

Examples:

Figs. 1-3 illustrate an example of distributing and reconstructing a secret in case of a simple Secret Sharing Scheme (SSS).

Fig. 1 illustrate a setup phase, where the number of participants is n = 3 the number of participants that cannot reveal the secret when establishing coalition is s = 2, the modulo each participant is m ₁ = 5, m ₂ = 7, and m ₃ = 11 , respectively. The multiplicative modulo M _n of all moduli is therefore M _n = 5 ■ 7 ■ 11 = 385 . The secret to be shared is S' = 12. The selected n — 1 random numbers assigned to each participant are = 36, r ₂ = 67. Therefore, the modified secret S _mix is given by S _mix = [(12 • 36 • 67)] ₃₈₅ = 69.

Fig. 2 illustrates the distribution phase:

Participant 1 receives the values:

Participant 2 receives the values:

Participant 3 receives the values:

Fig. 3 illustrates the reconstruction phase by applying CRT: ri = CRT[r ₁₃ , r _{l r} r ₁₂ ] _Mn = 36 r ₂ = CRT[r ₂₂ , r _{2 3} , r _{2 1} ]M _n = 67

Then the inverse of and r ₂ is calculated by:

And the secret is reconstructed by:

Figs. 4-6 illustrate an example of distributing and reconstructing a secret in case of a multiplicative (SSS). Fig. 4 illustrates the setup phase for multiplication of secrets.

The secrets are S' = 12 and S" = 17. The selected n — 1 random numbers assigned to each participant are r' = 36, r" = 52. Therefore, the modified secrets S' _mix and S" _mix are given by S' _mix = [(12 • 36)] ₃₈₅ = 47 and S" _mix = [(17 • 52)] ₃₈₅ = 114. The product of the secrets is S* = S' . S" = 17 . 12 = 204

Fig. 5A-5B illustrate the distribution phase for multiplication of secrets, during which the values of: are calculated.

Fig. 5C-5F illustrate the multiplication of secrets, during which the values of: participant 1

S' _m iil _i l 2 ’ S"m ifLiL 2 = 3 and r' ₂ " r" ₂ =2 for participant 2 r participant 3 are calculated.

Fig. 6 illustrates the reconstruction phase, during which the values of: participant 1

S* _m ix ₂ ^ar| d ^r *2 f° ^r participant 2

S* _miX3 and r* ₃ for participant 3 are calculated.

Then, the values 353 and r* = CRT[r* ₃ , r\, r* ₃ ] _Mn = 332

[r* ¹ 1 = 138

L -< 385 are calculated.

Finally, is reconstructed by:

Fig. 7 illustrates an example of an arithmetic circuit.

Streaming Model

Assuming that there are n participants and for simplicity s = 1, the inner algorithm running for each participant will be explained. The described algorithm runs after the secrets have been distributed safely by the original scheme and under the constraint that each of the pre-addition inner components is not familiar with the other component secrets. In order to perform addition we have the real secrets S' and S", we also have the blinding secrets S ^@ , s ^@@ , S ^# , S ^## , S* and S**, such that S# = S ^## = S* = S** = 1 and S ^@ = —s ^@@ . All secrets are distributed using the original distribution algorithm, yet we also require that:

For each participant there will be three components (can be dockers, for example), that are connected for communication, but do not share memory. The components perform the following operations:

1. The first component holds S'_mix, S ^@ mix, S ^# mix, S*mix modulo mi, and also r', r ^@ , r ^# , r* modulo m _i+1 .

The component computes (S'_mix • S ^# mix + S@mix) • S*mix(mod mi), and r' • r ^# • r*(mod_mi + 1).

Finally sending the results from the previous computations to the third component.

2. The second component holds S"_mlx, S ^@@ mix, S ^## mix, S**mix modulo mi, and also r", r ^@@ , r**, r** modulo m _i+1 . The component computes (S" _mix . S ^## mix + S®®mix') . S**mix(mod_m _i ), and r" • r ^## • r** (mod_mi + 1).

Finally sending the results from the previous computations to the third component.

3. The third component receives (S’ _mix . S ^# mix + S®mix) . S*mix(mod_m.i) and (S" mix . S ^## mix + S®®mix) . S ^mixfmod-mi) and calculates:

(S' mix . S ^# mix + S®mix) . S*mix + (S"_mj% • S ^## mix + S®®mix') . S**mix.

The component also receive r' • r ^# • r*(mod_mi + 1) and r" . r ^## . r**(mod_mi + 1) and validate that they are equal.

All the relevant data for the computation has been transferred to the addition component, in such a way that disable any recover of the original secrets and calculations performed in the pre-addition components.

Fig. 8 illustrates an example of additions of blinded secrets by each participant i using the streaming model. Each participant comprises pre-addition dockers (software platforms to create, deploy and manage virtualized application containers on a common operating system), one for each addend, and an addition docker, for performing the addition.

The blinded secrets to be added are • S* - _r + S®-„') • S* _ix and (S", _r . S*^ _r + and the corresponding randoms are r’ • r ^# • r* and r" • r ^## • r** , respectively.

The first docker comprises the parameters S ₇ ' _nix , S® _ix , r ^# ,and r* and calculates a first pre-addition result: r' • r ^# • r* (mod(m _i+1 )')

The second docker comprises the parameters S^ _ix , S®®, r ^## ,and r** and calculates a second pre-addition result: r" • r ^## • r** (mod(m _i+1 )') T1

The first docker has no knowledge about the parameters of the second docker, and vice versa.

The results are forwarded to the addition docker, which performs the addition where r' . r ^# . r* = r" . ^## . r**

In more general terms, the invention is directed to a method for performing CRTbased homomorphic secret-sharing with Perfect Information-Theoretic (PIT) security, comprising: a) determining a secret S and a number of participants n, each being a computerized device or a server; b) performing, using a computerized device comprising at least one processor, a secret distribution phase by: b.l) determining a general moduli set and a specific moduli set for each participant; b.2) calculating a general multiplicative modulo M _n as a product of all moduli; b.3) selecting a plurality of n — 1 random numbers and assigning the selected random number to each participant; b.4) calculating a modified secret S _mix being the product of said secret and said plurality of random numbers, under the multiplicative modulo; b.5) sending to each participant an adapted secret S _mix . being said modified secret after passing his corresponding modulo; b.6) to each participant, assigning modified random numbers being said random numbers, after passing the moduli of the participants corresponding to said random numbers; c) performing using said computerized device, a secret reconstruction phase by: d) reconstructing said modified secret S _mix by applying a CRT operator to all adapted secrets, using said multiplicative modulo; e) reconstructing each random number by applying a CRT operator to all modified random numbers, using said multiplicative modulo; f) calculating the inverse of each reconstructed random number; and g) reconstructing the secret by multiplying modified secret S _mix by the inverses of all reconstructed random numbers.

The invention is also directed to a method for performing CRT-based multiplicatively homomorphic secret-sharing with Perfect Information-Theoretic (PIT) security, comprising: a) determining a plurality of secrets (S',S”, ... ) and a number of participants n, , each being a computerized device or a server; b) calculating, using a computerized device comprising at least one processor, the product S* of said secrets; c) performing, by said computerized device, a secret distribution phase by: c.l) determining a general moduli set and a specific moduli set for each participant; c.2) calculating a multiplicative modulo M _n of all moduli; c.3) selecting a plurality of random numbers; c.4) for each secret, calculating a modified secret S' _ir ,S" _ir ,... being the multiplicative modulo of the product of said secret and said plurality of random numbers; c.5) sending to each participant an adapted secret S' _mix , S" _mix . being said modified secret after passing his corresponding modulo; c.6) to each participant, assigning modified random numbers being said random numbers, after passing the moduli of the participants corresponding to said random numbers; d) performing, by said computerized device, a multiplication phase by: d.l) for each participant, multiplying all adapted secrets S' _mi . S" mi ■ [t ■ d.2) for each participant, multiplying all his adapted random numbers r\, r' ₂ r' _s ; r" _r , r" ₂ , . , r” _s ; e) performing, by said computerized device, a secret reconstruction phase by: f) reconstructing a blinded secret S* _mix by applying a CRT operator to all blinded secrets S* _mix ., each being the product of modified secrets that correspond to each participant, using said multiplicative modulo; g) reconstructing blinded random r*i by applying a CRT operator to all blinded randoms r*, each being the product of modified secrets that correspond to each participant, using said multiplicative modulo; h) calculating the inverse of the blinded random number r*i; and i) reconstructing the product of secrets by multiplying said blinded secret by the inverse of the blinded random number.

The invention is also directed to a method for performing CRT-based additively homomorphic secret-sharing with Perfect Information-Theoretic (PIT) security, comprising: a) determining a plurality of secrets (S',S”, ... ) and a number of participants n, , each being a computerized device or a server; b) performing, using a computerized device comprising at least one processor, a secret distribution phase by: b.l) determining a modulo for each participant; b.2) calculating a multiplicative modulo M _n of all moduli; b.3) selecting a plurality of random numbers; b.4) for each secret, calculating a modified secret S' _ir ,S" _ir being the multiplicative modulo of the product of said secret and said plurality of random numbers; b.5) sending to each participant an adapted secret S' _mix . , S" _mix . being said modified secret after passing his corresponding modulo; b.6) to each participant, assigning modified random numbers being said random numbers after passing the moduli of the participants corresponding to said random numbers; c) performing, by said computerized device, an addition phase by: c.l) assigning a plurality of random numbers r _1; ..., r _s to each addend; c.2) allowing each participant i to calculate S^ _ix + S^ _ix . without changing said random numbers; d) performing, by said computerized device, a secret reconstruction phase by: e) reconstructing a blinded secret S* _mix by applying a CRT operator to all blinded secrets S* _mix ., each being the product of modified secrets that correspond to each participant, using said multiplicative modulo; f) reconstructing blinded random r* _; by applying a CRT operator to all blinded randoms r*, each being the product of modified secrets that correspond to each participant, using said multiplicative modulo; g) calculating the inverse of the blinded random number r*; and h) reconstructing the sum of secrets by multiplying said blinded secret by the inverse of the blinded random number. The above examples and description have of course been provided only for the purpose of illustrations, and are not intended to limit the invention in any way. As will be appreciated by the skilled person, the invention can be carried out in a great variety of ways, employing more than one technique from those described above, all without exceeding the scope of the invention.

Appendix A

Multiplicative Homomorphism Expanded Proof

The proposed multiplicative scheme is multiplicative homomorphic. In fact, let S' and S" be secrets. Let rj, ..., rs be the random elements drawn for S' and r£', ... , rs' those drawn for S". Each participant i has the secret shares of each blinded secret and blinding randoms:

We have:

Each participant can calculate S' _miXj • S" _mi . and r-. • r-.' for each 1 < j < s and send them to the user. Using CRT, the user then computes: then finding the inverses:

OK)- ¹ . W - r;')- ¹ , and finally computing S' • S".

Thus, the scheme is a multiplicative homomorphic scheme.

Appendix B

Theorem 3

In the ramp multiplicative scheme, no set P of participants of size up to s can get any information by cooperating. In particular, if s = n — 1 then the scheme is perfect. Proof: It suffices to show that any set P = {i _1; ..., i _s },l < i _t < ••• < i _s < n, of s participants cannot gather any information by cooperating.

Let S be the secret. We have to show that, for each S' G <S, if P[S = S'] = p (according to the distribution 2)), then the conditional probability of the event S = S', given the information the set P has according to the proposed scheme, is still p.

For arbitrary fixed have i and, by Lemma 1,

The probabilities of r _1; ... , r _s and S mix being equal to Xp ... , x' and y', respectively, do change knowing the information held by the set P. However, we claim that the conditional probability of the secret S being equal to S' does not change:

P[S = S'|r! = xi(mod_ m _ii+1 ), ..., r _t = xi(mod_ m _is+1 ), r _s = Xs(mod_ m _ii+s ), ..., r _s = x^(mod_ m _is+s ),

S mix = y'(mod_ m^), ..., S mix = y'(mod_ m _is ) ] = p.

(Eq. 5)

Denote the knowledge of the set with, r _s = Xg(mod_ m _ii+s ), ..., r _s = x;(mod_ m _is+s ),

S mix

By Bayes' theorem: It is known that s < n and therefore, it is known that each modulo equivalence of m,., VI < j < s does not appear n times for different randoms. Therefore, the event in the numerator is,

P[ri = xi(mod_ m _ii+1 ), ..., 11 = xi(mod_ m _is+1 ),

... r _s = Xg(mod_ m _ii+s ), ..., r _s = x;(mod_ m _is+s ), S_mix = y'(mod_ m^), ..., S_mix = y'(mod_ m _is )|S = S']

= P[r _t = xi(mod_ m _il+1 ), ..., ri = xi(mod_ m _is+1 ), meaning r _t assumes specific values modulo m^, m _ii+1 , ..., m _is+1 , r ₂ assumes specific values modulo m _i2 , m _ii+2 , ..., m _is+2 and r _s assumes specific values modulo m _is , m _ii+s , ... , m _is+s , while r _1; ... , r _s values modulo all other mj's is arbitrary (as long as they are invertible). Hence the numerator is:

Product of fractions of the type l/c|>(m _i )

When anything is not known, each of these is to power s. The information all s cooperating participants have gives q pieces of information mod m _i7 where q is the number of cooperating participants among i — s, i — s + 1, ... , i. Hence the probability should

Since the same holds for any S" G instead of S', the denominator assumes by the law of total probability the same value. This proves Eq. 5. The choice of s = n — 1 yields perfect privacy, meaning the scheme is a perfect secret sharing scheme according to Definition 1 as VP g Jl, there is no information leak.

References

[1] C. Asmuth, J. Bloom, A modular approach to key safeguarding, IEEE Transactions on Information Theory (Volume: 29, Issue: 2, March 1983) 208 - 210.

[2] Maurice Mignotte, How to Share a Secret, EUROCRYPT 1982. Lecture Notes in Computer Science, Springer (Volume 149, 1983) 371-375.

[3] Dor Bitan, Shlomi Dolev, Optimal-round preprocessing-MPC of polynomials over non-zero inputs via distributed random matrix. Wireless Netw (2022).

[4] Stanley Burris, H.P. Sankappanavar, A Course in Universal Algebra (2012).

[5] Oguzhan Ersoy, Thomas Brochmann Pedersen, Emin Anarim, Homomorphic extensions of CRT-based secret sharing, Discrete Applied Mathematics (Volume 285, 15 October 2020) 317-329.

[6] Yildirim, Ismail Fatih, SecurePL: A compiler and toolbox for practical and easy secure multiparty computation, Master Thesis Sabanci University (2008).

[7] Adi Shamir, How to share a secret, Communications of the ACM (Volume 22, Issue 11, 01 November 1979), 612-613.

[8] Leslie G. Valiant, Why is Boolean complexity theory difficult?, Proceedings of the London Mathematical Society Symposium on Boolean function complexity (1992), 84-94.

[9] Craig Gentry, Fully homomorphic encryption using ideal lattices, Proceedings of the forty-first annual ACM symposium on Theory of computing (May 2009), 169-178.

[10] Shlomi Dolev and Arseni Kalma, Verifiable Computing Using Computation Fingerprints Within FHE. NCA 2021: 1-9.

[11] George Robert Blakey, Safeguarding cryptographic keys, Federal Information Processing Standard Conference Proceedings, 48 (1979), 313-317. [12] Michael Ben-Or, Shafi Goldwasser, Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing (January 1988), 1- 10.

[13] Oded Goldreich, Dana Ron, Madhu Sudan, Chinese Remaindering with Errors, IEEE Transactions on Information Theory (Volume: 46, Issue: 4, July 2000), 1330 - 1338.

[14] Asaf Cohen, Shlomi Dolev, Nir Tzachar, Efficient and Universal Corruption Resilient Fountain Codes, IEEE Transactions on Communications (Volume: 61, Issue: 10, October 2013), 4058 - 4066.

[15] Shlomi Dolev, Stav Doolman, Blindly Follow: SITS CRT and FHE for DCLSMPC of DUFSM (Extended Abstract), CSCML 2021, 487-496.

[16] Abbas Acar, Hidayet Aksu, A. Selcuk Uluagac, Mauro Conti, A Survey on Homomorphic Encryption Schemes: Theory and Implementation, ACM Computing Surveys (Volume: 51, Issue: 4, July 2019), 1-35.

[17] Ryutaroh Matsumoto, Paul Zhang, Quantum strongly secure ramp secret sharing, Quantum Inf Process 14 (2015), 715-729.

[18] Renato M. Capocelli, Adele De Santis, Luisa Gargano, Ugo Vaccaro, On the size of shares for secret sharing schemes, Journal of Cryptology 6 (1993), 157- 167.

[19] Ernest F. Brickell, Some Ideal Secret Sharing Schemes, Lecture Notes in Computer Science (Volume: 434, 1989) 468-475.

[20] Horace Edgar Rose, A Course on Finite Groups, Springer London (2010).