METHODS AND SYSTEMS FOR SECURE ARITHMETIC EQUALITY AND COMPARISON USING QUADRATIC RESIDUES

Abstract

Disclosed are methods and system for providing secure arithmetic equality and comparison using probabilistic rounding in the domain of Farey rationals with quadratic residues for a Multi-Party Computation (MPC) system. Embodiments securely provide for evaluation of encoded rational numbers for arithmetic equality equal to zero or not, probabilistic modulo of two rational numbers, probabilistic modulo of a rational number by a public value of two, a test for whether a rational number is greater-than-zero for quadratic residues and a general greater-than-zero test for a rational number which are quadratic non-residues.

Claims

1. A method for Multi-Party Computation (MPC) arithmetic comparison on a Multi-Party Computation (MPC) system of rational data encoded in a domain of Farey rationals, the method comprising: encoding by a first data server computing device a rational number into an encoded integer corresponding to said rational number as an encode function in said domain of Farey rationals; sending by said first data server computing device said encoded integer to a second data server computing device; computing by said second data server computing device an arithmetic comparison that has an arithmetic comparison result as a function of a FuzzyRound operation, quadratic residues, and said encoded integer; and sending by said second data server computing device said result encoded integer to a third data server computing device for use in additional computations and logic.

2. The method of claim 1 wherein said arithmetic comparison is an arithmetic equality as a function of said FuzzyRound operation, said quadratic residues, and said encoded integer such that said arithmetic comparison result is 0 when said encoded integer represents a 0 value for said rational number and a 1 when said encoded integer represents a non-zero value for said rational number.

3. The method of claim 1 wherein said arithmetic comparison is said rational number modulo a second rational number and further comprising: encoding by said first data server computing device a second rational number into a second encoded integer corresponding to said second rational number as an encode function in said domain of Farey rationals; sending by said first data server computing device said second encoded integer to said second data server computing device; and wherein said computing by said second data server computing device of said arithmetic comparison said arithmetic comparison result is said rational number modulo said second rational number as a function of a FuzzyRound operation, quadratic residues, said encoded integer, and said second encoded integer.

4. The method of claim 1 wherein said arithmetic comparison is said rational number modulo public modulus 2 as a function of said FuzzyRound operation, said quadratic residues, said encoded integer and said public modulus 2.

5. The method of claim 1 wherein said arithmetic comparison is a greater-than-zero test for said quadratic residues as a function of said FuzzyRound operation, said quadratic residues, and said encoded integer.

6. The method of claim 1 wherein said arithmetic comparison is a general greater-than-zero test for said encoded integer as a function of said FuzzyRound operation, said quadratic residues, and said encoded integer and said encoded integer is quadratic non-residue.

7. The method of claim 1 wherein said FuzzyRound operation is a probabilistic rounding protocol for rational numbers in said domain of Farey rationals.

8. The method of claim 1 wherein said rational data is comprised of a fixed-point integer representation of fractional data.

9. An arithmetic comparison system that operates as part of a Multi-Party Computation (MPC) system, the arithmetic comparison system comprising: a first data server computing device that encodes a rational number into an encoded integer corresponding to said rational number as an encode function in said domain of Farey rationals and sends said encoded integer to a second data server computing device; and said second server computing device that computes an arithmetic comparison that has an arithmetic comparison result as a function of a FuzzyRound operation, quadratic residues, and said encoded integer and sends said result encoded integer to a third data server computing device for use in additional computations and logic.

10. The arithmetic comparison system of claim 9 wherein said arithmetic comparison is an arithmetic equality as a function of said FuzzyRound operation, said quadratic residues, and said encoded integer such that said arithmetic comparison result is 0 when said encoded integer represents a 0 value for said rational number and a 1 when said encoded integer represents a non-zero value for said rational number.

11. The arithmetic comparison system of claim 9: wherein said arithmetic comparison is said rational number modulo a second rational number; wherein said first data server further encodes a second rational number into a second encoded integer corresponding to said second rational number as an encode function in said domain of Farey rationals and sends said second encoded integer to said second data server computing device; and wherein said second data server computing device computes said arithmetic comparison of said arithmetic comparison result is said rational number modulo said second rational number as a function of a FuzzyRound operation, quadratic residues, said encoded integer, and said second encoded integer.

12. The arithmetic comparison system of claim 9 wherein said arithmetic comparison is said rational number modulo public modulus 2 as a function of said FuzzyRound operation, said quadratic residues, said encoded integer and said public modulus 2.

13. The arithmetic comparison system of claim 9 wherein said arithmetic comparison is a greater-than-zero test for said quadratic residues as a function of said FuzzyRound operation, said quadratic residues, and said encoded integer.

14. The arithmetic comparison system of claim 9 wherein said arithmetic comparison is a general greater-than-zero test for said encoded integer as a function of said FuzzyRound operation, said quadratic residues, and said encoded integer and said encoded integer is quadratic non-residue.

15. The arithmetic comparison system of claim 9 wherein said FuzzyRound operation is a probabilistic rounding protocol for rational numbers in said domain of Farey rationals.

16. The arithmetic comparison system of claim 9 wherein said rational data is comprised of a fixed-point integer representation of fractional data.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0012] In the drawings,

[0013] FIG. 1 is a block diagram of the hardware implementation for an embodiment.

[0014] FIG. 2 is a flow chart of operations for an embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0015] In multi-party computation, the problem of efficiently and securely comparing two shared secrets has been the focus of volumes of research. Of particular interest has been the problem of finding protocols that play well with so-called arithmetic protocols. This is because arithmetic operations (+, ) are more frequent than Boolean operations in most applications, and are much more efficient than their Boolean counterparts. However, all of the proposed comparison protocols work by enabling Boolean circuits within the arithmetic domain and rely on the binary representations (e.g. two-complement representation) of their inputs. In this work, we present the first (to our knowledge) arithmetic equality and comparison protocols for secret sharing-based multi-party computation which do not depend on the binary representation of their inputs. Instead, they use a novel probabilistic truncation protocol, and a quadratic residue test protocol introduced by Nishide and Ohta. Our protocols require very few invocations of core operations like multiplication and reconstruction, and the number of these invocations is independent of input size. For example, in its online phase our equality protocol requires only four multiplications and three reconstructions. In practice this means that increasing the input size only requires the size of the field to increase. Moreover, all of our protocols are constant-round when realized by a particular secret-sharing scheme such as Shamir's.

1 Introduction

[0016] In 1982, researchers introduced the millionaires' problem. In this well-known problem Alice and Bob are two millionaires who are trying to determine which of them is wealthier without revealing their wealth. Through this problem and its solution researchers formally introduced secure computation. Secure computation allows the evaluation of functions on private data without revealing those data. A common technique for secure computation, and the focus of this patent application disclosure, is Multi-Party Computation (MPC). In MPC, n distrusting parties (n2) each with data d.sub.1, . . . , d.sub.n want to evaluate a function F(d.sub.1, . . . , d.sub.n) on their data without revealing any information about the data other than the output of the function.

[0017] Multiple of these works depend on secret sharing for their protocols and their subsequent implementations. Secret sharing appeared a few years ahead of secure computation, it was introduced independently by Shamir and Blakley in 1979. Traditionally, in secret sharing each of n parties P.sub.i receives a piece (share) of the private data (secret) being shared. Each of these shares being indistinguishable from a random value. Any authorized set of parties must have the ability to reconstruct the secret while unauthorized sets of parties should not be able to learn any information about the secret. When applied to secure computation the authorized sets can perform operations on the secrets and reconstruct them through communications with one another (e.g., sending/receiving shares, creating and sending new shares, etc.). Shamir introduced a technique to share secrets using polynomial interpolation over finite fields. Another well-known technique to share secrets is Additive Secret Sharing, which relies on the fact that a sum of a fixed element and uniformly random element in a finite field is indistinguishable from uniformly random.

[0018] There have been volumes of follow-up work aimed at improving the performance of protocols that securely compare (< or =) secret-shared values. Many of these use so-called garbled circuits and evaluate comparisons as Boolean circuits. While garbled circuit-based solutions can be very efficient in evaluating secure comparisons, they tend to be much less efficient for arithmetic operations (i.e. operations on integers). In contrast, MPC realized over a large ring or field suffers from the opposite problem: arithmetic operations are very efficient, but comparisons are very inefficient. A secure equal-to-zero protocol which works over finite fields has been introduced, but it suffered from the constraint of requiring the field to have small characteristic. Researchers finally made comparisons practical over large prime-order fields by introducing a constant-round bit-decomposition protocol for converting a sharing of a.sub.p to sharings of the bits of a viewed as elements of .sub.p. Their protocol enabled equality and comparison of integers (field elements) to be performed bitwise. Despite impressive progress in efficiency, equality and comparison protocols (specifically comparison) which do not rely on the binary representation of the inputs have been elusive.

1.1 Our Contributions

[0019] We introduce two novel arithmetic protocols for securely computing equal-to-zero and greater-than-zero with constant invocations of core protocols like multiplication. These protocols heavily rely on two other protocols. One is a quadratic residue test that securely computes the Legendre symbol of a shared integer. The other is a novel protocol for probabilistic rounding of Farey rationals. The latter enables equal-to-zero by leveraging patterns of quadratic residues, and enables greater-than-zero via two mod reduction protocols. Of course, the equal-to-zero and greater-than-zero protocols trivially enable comparison of two nonzero values; just subtract the values and run the protocol on their difference.

Organization.

[0020] Section 2 introduces notation, linear secret sharing schemes, and our notion of security via the so-called arithmetic black box model.

[0021] In Section 3, we introduce the Farey rationals, discuss some relevant prior work which used them, and present the quadratic residue test protocol which enables our comparison protocols.

[0022] Section 4 presents our first new protocolFuzzyRoundand proves some important results about correctness and security.

[0023] Section 5 introduces the equal-to-zero protocol, proves its correctness, and then shows that the quadratic residue pattern required by the protocol occurs in all sufficiently large primes. It finishes with a discussion of parameters.

[0024] Section 6 begins by introducing the mod reduction protocols used by the greater than-zero protocol, and then presents and proves the correctness of the protocol. Like the preceding section, it ends with a discussion of parameters.

[0025] The security of our protocols is proved in Section 7. The heavy lifting is done by lemma 3 in section 4.

[0026] Section 8 provides some example field sizes that allow our protocols to work with various inputs, and then briefly discusses fixed-point numbers and how our protocols are compatible with fixed-point arithmetic.

[0027] Section 9 uses 2-out-of-3 Shamir Secret Sharing along with specific core protocols to estimate the online round and communication complexities of our protocols.

2 Preliminaries

[0028] Notation. For a positive integer m, /m denotes the ring of integers modulo m. In case m is prime, we write .sub.m. The elements of /m will be represented by integers 0, 1, . . . , m1. We use yA(x) to denote that a randomized algorithm A on input x outputs y. If A is deterministic, we simply write y=A(x). We use rS to mean that r is selected uniformly at random from the set S. If a protocol has no argument, e.g. ( ), then the protocol takes no inputs. always denotes a statistical security parameter.

[0029] Linear Secret Sharing Schemes (LSSS). A sharing of x.sub.p among n parties will be denoted [x]=([x].sub.1, [x].sub.2, . . . , [x].sub.n), so that the i.sup.th party receives the share [x].sub.i. [x][y], [x].Math.[y] mean that each party adds/subtracts or multiplies their share of x with their share of y. Execution of LSSS protocols can be separated into the synchronous online phase, i.e. the operations which must be performed during the protocol, and the asynchronous offline phase. The offline phase is reserved for tasks that can be performed before the inputs to a particular functionor even the function itselfare known. E.g., generating correlated randomness.

[0030] Arithmetic Black Box. In spite of using LSSS for our protocols, we do not specify which LSSS. Instead we use the Arithmetic Black Box (ABB) model introduced by Damgrd and Nielson. Under this model, the parties all have access to a functionality .sub.ABB that allows parties share and reconstruct secrets (Recon), multiply shared secrets (Mult), and perform local operations (addition of shared values, and addition and multiplication of a secret value and a public value). We further assume the parties have access to functionalities that generate: a uniformly random element of .sub.p, a uniformly random bit viewed as an element of .sub.p, and a uniformly random integer in [0, 2.sup.k).Math..sub.p. We denote these protocols by RandInt( ), RandBit( ), and RandInt(k), respectively. We further assume that all randomness needed for a protocol is generated in the offline phase. With this in mind, the complexity of a protocol will be measured in number of invocations of Mult, Recon, and functionalities for generating randomness.

2.1 Security

[0031] All of our protocols are constructed via clever compositions of Mult, Recon, local operations, and protocols for generating randomness. This means that as long as values which are revealed during a protocol do not leak any information, the protocol inherits the security of .sub.ABB and the randomness functionalities. This allows our protocols to achieve active security (security against malicious adversaries) by simply assuming all functionalities are realized using actively secure framework (e.g. Verifiable Secret Sharing) which ensures the core protocols are actively secure, and then invoking Canetti's composition theorem which roughly states that a composition of secure protocols yields a secure protocol.

3 Building Blocks

[0032] Here we review and summarize the prior work on which our protocols rely. As discussed in the introduction, our protocols heavily rely on prior works that use the Farey rationals along with a protocol for securely computing the Legendre symbol of a shared integer. This section first introduces the Farey rationals and the encoder used to map them into a finite field along with some of their important properties, and then presents the protocol for computing the Legendre symbol.

3.1 Farey Rationals

[0033] The Farey rationals (Also commonly called the Farey fractions, and related to the Farey sequence.) have been used in the context of rational approximations of irrational numbers, error-free computation, and the rational reconstruction problem. The latter asks when is it possible to recover an unknown fraction a/b given a modulus m which is co-prime to b and the value ab.sup.1 mod m. They are defined as the set

[00002]${}_N:=\left\{x/y:.Math.x.Math.N,0<yN,\gcd \left(x,y\right)=1,\gcd \left(p,y\right)=1\right\},$ [0034] where N=N(p):={square root over ((p1)/2)}, and are simply the set of reduced fractions with numerator and denominator both bounded in absolute value by N. Note that there may be many primes p which yield the same set of Farey rationals. The following lemma collects some important properties of .sub.N.

[0035] Lemma 1. Let p be a prime and N=N(p). [0036] (i) If x/yN, then x/y.sub.N. [0037] (ii) If x/y.sub.N is nonzero, then y/x.sub.N. [0038] (iii) [N, N].Math..sub.N. [0039] (iv) .sub.N is not closed under addition and multiplication.

[0040] Proof. (i) x/y.sub.N implies |x|=|x|N, so x/y.sub.N. (ii) Let x/y.sub.N be nonzero. Then x0 and |x|, yN, so y/x.sub.N. (iii) If x[N, N] then clearly x=x/1.sub.N. (iv) Since .sub.N is simply a set of rationals, it is not closed under the usual +,. E.g. N.sub.N, but N+N=2N.Math..sub.N.

3.2 A Somewhat Homomorphic Encoding

[0041] Harmon et al defined a rational encoder for homomorphic encryption based on the aforementioned rational reconstruction problem. Their encoding maps elements of .sub.N(p) to the finite field .sub.p, and is defined by enc(x/y)=xy.sup.1 mod p. The decoding dec can be computed efficiently using a slight modification of the Extended Euclidean Algorithm. enc is somewhat homomorphic in the sense that it is homomorphic with respect to +, as long as the composition of operands remains in .sub.N

[00003]$(E.g.,\mathrm{enc}\left(\frac{x_0}{y_0}+\frac{x_1}{y_1}\right)=\mathrm{enc}\left(\frac{x_0}{y_0}\right)+\mathrm{enc}\left(\frac{x_1}{y_1}\right)\mathrm{iff}\frac{x_0}{y_0},\frac{x_1}{y_1},\frac{x_0}{y_0}+\frac{x_1}{y_1}{}_N.$

We summarize important properties of enc with the following lemma.

[0042] Lemma 2. Let p be a prime, N=N(p), and enc, dec be the encode and decode maps, respectively. [0043] (i) If z[N, N], then enc(z)=z. [0044] (ii) enc is somewhat homomorphic w.r.t. addition and multiplication of Farey rationals. In particular, if *{+,} and A, B, A*B.sub.N, then

[00004]$\mathrm{dec}\left(\mathrm{enc}\left(A\right)*\mathrm{enc}\left(B\right)\right)=A*B.$

[0045] Proof. (i) Let z[N, N]. By definition, enc(z)=z.sub.p. Of course, enc(z) is a field element, and so depends on the representatives chosen for .sub.p. E.g., if we use {0, 1, . . . , p1}, then enc(1)=1 and enc(1)=p1.

3.3 Protocols for Arithmetic Over the Farey Rationals

[0046] We briefly review the protocols for addition, subtraction, multiplication, and division of Farey rationals using SSS or AddSS introduced by Harmon and Delavignette in previous work. Their family of protocols, which they call Mercury, is defined over the Farey Rationals via the aforementioned somewhat homomorphic encoding, allowing it to leverage existing protocols defined over .sub.p. The Mercury division, in particular, relies on the fact that .sub.N is closed under reciprocals lemma 1(ii). This property allows to be performed very efficiently as multiplication with a reciprocal. All of the Mercury protocols are distinguished by the prefix Hg. However, ignoring the encoder, addition, subtraction, and multiplication are identical to their counterparts realized by .sub.ABB, so we choose to only include the prefix for division. I.e., division is denoted by HgDiv.

[0047] The addition and subtraction protocols can be performed locally, and the multiplication is identical to Mult. HgDiv requires two invocations of Mult, one invocation of Recon, and one invocation of RandInt( ).

[0048] All of these protocols are constrained by the fact that .sub.N is not closed under +,. This means that in practice they must take the domain of secrets to be a subset .Math..sub.N that is chosen so that any desired compositions of elements of remain in F.sub.N. The choice of depends on the secrets, and the functions that must be computed on the shared secrets. We will elaborate later on how should be chosen.

3.4 A Quadratic Residue Test Protocol

[0049] It requires a prime secret sharing modulus which is congruent to 3 modulo 4, and outputs the Legendre symbol of a, which is defined as

[00005]$\begin{array}{cc}\left(\frac{a}{p}\right):=\{\begin{array}{cc}1,& \mathrm{if}a\mathrm{is}a\mathrm{quatratic}\mathrm{residue}\mathrm{modulo}p\\ -1,& \mathrm{if}a\mathrm{is}a\mathrm{quatratic}\mathrm{non}-\mathrm{residue}\mathrm{modulo}p\\ 0,& \mathrm{if}a=0\end{array}& \mathrm{Eq}.1\end{array}$

[0050] Protocol 1: Secure quadratic residue test.

TABLE-US-00001 Inputs. Shares of nonzero a .sub.p. [00006]$\left[\left(\frac{a}{p}\right)\right]\mathrm{Legendre}\left(\left[a\right]\right).$ 1.[b] RandBit( ) 2.[s] = 2[b] 1; 3.[r] RandInt( ); 4.[r.sup.2] = Mult([r], [r]); 5.[sr.sup.2] = Mult([s], [r.sup.2]); 6.[sr.sup.2a] = Mult([sr.sup.2], [a]); 7.sr.sup.2a = Recon([[ar.sup.2a]);// if sr.sup.2a = 0, the parties restart from Step 4. 8.[00007]$s^{}=\left(\frac{s{r}^{2}a}{p}\right);$ 9.[00008]$\left[\left(\frac{a}{p}\right)\right]=s^{}\left[s\right];$ 10.[00009]$\mathrm{return}\left[\left(\frac{a}{p}\right)\right].$ Invocations.Online: 1 Mult, 1 Recon. Offline: 2 Mult, 1 RandBit( ), 1 RandInt( ).

4 FuzzyRound: A Probabilistic Rounding Protocol

[0051] This protocol is the fundamental component of our equality and comparison protocols. FuzzyRound approximates a/b.sub.N by c/B.sup.k.sub.N for some positive integer base B and nonnegative integer k. The example below illustrates the idea of the protocol by performing the truncation on un-shared values.

[0052] Example 1. Given a/10.sup.8=314159265/10.sup.8=3.14159265, suppose we want to truncate to four decimal places of precision. On un-shared values, the protocol proceeds as follows: [0053] (i) Secret to be truncated: 3.14159265; [0054] (ii) Scale secret by 10.sup.8/10.sup.4=10.sup.4: 31415.9265; [0055] (iii) Generate random integer masks r, s: say r=537914 and s=7116; [0056] (iv) Add r+10.sup.4s to the scaled secret: 31415.9265+537914.7116=569330.6381; [0057] (v) Round down to the nearest integer: 569330.6381=569330; [0058] (vi) Subtract r from the rounded value: 569330537914=31416; [0059] (vii) Scale result by 10.sup.4: 31416.Math.10.sup.4=3.1416.

[0060] This yields 31416/10.sup.4314159265/10.sup.8, as desired. Notice that 314159265//10.sup.831416//10.sup.4=9265/10.sup.8<10.sup.4/10.sup.8=1/10.sup.4.

[0061] We assume that at the start of the protocol each party has: B, k, and shares of enc(a/b). For notational simplicity, we will write [a/b] instead of [enc(a/b)].

[0062] Protocol 2: Secure probabilistic rounding of Farey rationals.

TABLE-US-00002 Inputs.The fraction x/y .sub.N to be rounded and its encoding enc(x/y) .sub.p. An integer base B, a precision k, and a security parameter . [00010]$\mathrm{Constraints}.2^{}\underset{x}{\max }\left\{.Math.x.Math.\right\}{B}^k\mathrm{and}{2}^{}N{2}^{}+2^{}\underset{y}{\max }\left\{.Math.y.Math.\right\}+\underset{y}{\max }\left\{.Math.y.Math.\right\}.$ [z/B.sup.k] FuzzyRound([x/y], B, k, ). 1.[r] RandInt( ) and [r] RandInt(); 2.[xB.sup.k/y] = B.sup.k .Math. [x/y] and = [r/2.sup.] = 1/2.sup. .Math. [r]; 3.[xB.sup.k/y + r + r/2.sup.] = [xB.sup.k/y] + [r] + [r/2.sup.]; 4.enc(xB.sup.k/y + r + r/2.sup.) = Recon[xB.sup.k/y + r + r/2.sup.]); 5.xB.sup.k/y + r + r/2.sup. = dec(enc(xB.sup.k/y + r + r/2.sup.)); 6.compute [xB.sup.k/y] + b + r = xB.sup.k /y + r + r/2.sup.; // Note that b {0,1} 7.[xB.sup.k/y + b] = enc(xB.sup.k/y + b + r ) [r]; 8.[xB.sup.k/y .Math. B.sup.k + bB.sup.k] = B.sup.k .Math. [xB.sup.k/y + b]; 9.return[z/B.sup.k] = [xB.sup.k/y .Math. B.sup.k + bB.sup.k]. Invocations.Online: 1 Recon. Offline: 1 RandInt( ), 1 RandInt().

[0063] The constraint +log.sub.2(B)k is required for the proof of security, and N++2.sup.+ ensures that computations do not overflow .sub.N during the execution of FuzzyRound.

[0064] Observe that FuzzyRound probabilistically rounds up or down, depending on the values of r, x/y, B.sup.k, and . In particular, it rounds down whenever xB.sup.k/y+r/2.sup. remains between xB.sup.k/y and xB.sup.k/y. Proposition 1 provides details.

[0065] Proposition 1. Let frac=xB.sup.k/yxB.sup.k/y0, 1) be the fractional part of xB.sup.k/y. Then FuzzyRound [0066] (i) rounds down with probability 1frac, and [0067] (ii) and rounds up with probability frac.

[0068] Proof. Recall that b{0, 1} the bit from step (6) of FuzzyRound protocol. Clearly FuzzyRound rounds down if and only if

[00011]$\begin{array}{cc}.Math.\frac{{\mathrm{xB}}^k}{y}.Math.\frac{{\mathrm{xB}}^k}{y}+\frac{r^{}}{2^{}}<.Math.\frac{{\mathrm{xB}}^k}{y}.Math.,& \mathrm{Eq}.2\end{array}$ [0069] and Equation 2 holds precisely when b=0. Note that if y divides xB.sup.k, then Pr(b=0)=1 and frac=0. Suppose yxB.sup.k, whence xB.sup.k/yxB.sup.k/y. Then Equation 2 implies

[00012]$\begin{array}{c}0\frac{x{B}^k}{y}-.Math.\frac{x{B}^k}{y}.Math.+\frac{r^{}}{2^{}}<.Math.\frac{x{B}^k}{y}.Math.-.Math.\frac{x{B}^k}{y}.Math.\\ 0+\frac{r^{}}{2^{}}<1\\ 0r^{}<2^{}\left(1-\right).\end{array}$

Since r is selected from the uniform distribution over [0, 2.sup.), it follows that Pr(b=0)=2.sup.(1frac)/2.sup.=1frac and Pr(b=1)=1Pr(b=0)=frac. This completes the proof.

4.1 Correctness and Security

[0070] Proposition 2 (Correctness). The truncation protocol FuzzyRound is correct in the sense that, for input x/y and output z/B.sup.k=xB.sup.k/y/B.sup.k+b/B.sup.k,

[00013]$.Math.\frac{x}{y}-\frac{z}{B^k}.Math.<\frac{1}{B^k}$

Moreover, if x=0, then z=0.

[0071] Proof. For b{0,1}

[00014]$.Math.\frac{x}{y}-\left(\frac{.Math.\frac{x{B}^k}{y}.Math.}{B^k}+\frac{}{B^k}\right).Math.=.Math.\frac{x}{y}-\frac{.Math.\frac{x{B}^k}{y}.Math.}{B^k}-\frac{}{B^k}.Math..Math.\frac{y{B}^k}{y{B}^k}=.Math.{\mathrm{xB}}^k-y.Math.\frac{x{B}^k}{y}.Math.-y.Math..Math.\frac{1}{y{B}^k}=.Math.\left({\mathrm{xB}}^k\mathrm{mod}y\right)-y.Math..Math.\frac{1}{y{B}^k}<y.Math.\frac{1}{y{B}^k}=\frac{1}{B^k}$

[0072] If x=0, then the bit b in step 6 of FuzzyRound is 0. It follows that z=0. This completes the proof.

[0073] We next prove a lemma which will allow us to show that FuzzyRound is secure. The formal security will be discussed later along with the security of the rest of our protocols.

[0074] Lemma 3. Let x/y.sub.N and B, k be integers. Further, let r[0, ), and r[0, 2.sup.). If .sub.secret is the distribution of the random variable S=xB.sup.k/y+r+r/2.sup. and is the distribution of the random variable R=r+r/2.sup., then the statistical distance between and .sub.secret is negligible in .

[0075] Proof. We start by showing that D is uniform over its range. It suffices to show that the random variable 2.sup.R=2.sup.(r+r/2.sup.)=r2.sup.+r is uniform. If r.sub.02.sup.+r.sub.0=r.sub.12.sup.+r.sub.1, then (r.sub.0r.sub.1)2.sup.=r.sub.1r.sub.0. Since 0|r.sub.1r.sub.0|<2.sup., r.sub.0=r.sub.1 and r.sub.0=r.sub.1. This means the distribution of 2.sup.R is uniform, whence the distribution of R is also uniform. That is, since |range(2.sup.R)|=|range(R)| and range(2.sup.R)=[0, ), Pr(R=i)=1/|range(R)|=1/.

[0076] Notice that S=xB.sup.k/y+r+r/2.sup. is simply the random variable obtained by shifting the distribution of R by xB.sup.k/y to the left if x<0 and to the right if x>0. Without loss of generality, suppose x>0. With this shift in mind, we split range(R)range(S)=[0, xB.sup.k/y+) into three subintervals: [0, xB.sup.k/y), [xB.sup.k/y, ), and [, xB.sup.k/y+). It is clear that

[00015]$\begin{array}{cc}\left(i\right)& i[0,{\mathrm{xB}}^k/y)\mathrm{Pr}\left(R=i\right)=1/2^{+}\mathrm{and}\mathrm{Pr}\left(S=i\right)=0,\\ \left(\mathrm{ii}\right)& i[x{B}^k/y,2^{+})\mathrm{Pr}\left(R=i\right)=Pr\left(S=i\right),\mathrm{and}\\ \left(\mathrm{iii}\right)& i[2^{+},{\mathrm{xB}}^k/y+2^{+})\mathrm{Pr}\left(R=i\right)=0\mathrm{and}\mathrm{Pr}\left(S=i\right)=1/2^{+}.\end{array}$

[0077] We now show that the statistical distance between R and S is bounded by a negligible function of the statistical security parameter .

[00016]$2\left(R,S\right)=\underset{i\mathrm{range}\left(R\right).Math.\mathrm{range}\left(S\right)}{.Math.}.Math.\mathrm{Pr}\left(R=i\right)-Pr\left(S=i\right).Math.=\frac{2x{B}^k/y}{2^{+}}\frac{2.Math.2^{}}{2^{+}y},\mathrm{since}+{\log }_2\left(B\right)k=\frac{2}{2^{}y}$

So

[00017]$\left(R,S\right)<\frac{1}{2^{}y},$

which is negligible in , as desired.

[0078] Even though this is not the focus of this work, we note that pairing FuzzyRound with the Mercury protocols yields efficient fixed-point protocols for +, .Math., , and . The resulting division protocol, in particular, is better than state-of-the-art protocols in terms of both round and communication complexity.

5 Arithmetic Equality

[0079] With a well-chosen prime modulus, we can use FuzzyRound along with properties of quadratic residues to build a protocol which outputs 1 if its input is zero, and 0 otherwise.

[0080] Proposition 3. Let a.sub.N be an integer such that a.sup.2+1<N and f=FuzzyRound ([a.sup.2/a.sup.2+1], 2, 1, ) is defined, then

[00018]$\begin{array}{cc}f=\{\begin{array}{cc}0& \mathrm{if}a=0\\ 1/2\mathrm{or}1,& \mathrm{if}a0\end{array}& \mathrm{Eq}.3\end{array}$

[0081] Proof. Let =a.sup.2/(a.sup.2+1). If a=0, then =0, and Proposition 2 implies that f=0. Suppose a0. In this case, <1. Again, by Proposition 2, <f<. Combining these two inequalities yields 0<f<3/2. The result follows since f must be a multiple of .

[0082] For a prime p, recall that an integer a is a quadratic residue modulo p (qr) if and only if there is an integer b such that a=b.sup.2 mod p. If no such integer exists, we say a is a quadratic non-residue modulo p (qnr). With this in mind, we may now introduce the equal-to-zero protocol.

[0083] Protocol 3: Secure equal-to-zero.

TABLE-US-00003 Inputs. Shares of (the encoding of) an integer a .sub.N, an integer , and a security parameter . Constraints.a needs to be small enough relative to N so that a.sup.2 + 1 < N and FuzzyRound([a.sup.2/a.sup.2 + 1], 2, 1, ) is defined, and is qr and + 1, + 2 are qnr. [a =.sup.? 0] EQZ([a], , ) 1. [a.sup.2] = Mult([a], [a]); 2. [a.sup.2 + 1] = [a.sup.2] + 1; 3. [d] = HgDiv([a.sup.2], [a.sup.2 + 1]); 4. [f] FuzzyRound([d], 2, 1, ); 5. [s] = 2[f] + ; 6. [ ] = Legendre([s]); 7. [ ] = ([ ] + 1)/2; 8. return [ ] = [a =.sup.? 0]. Invocations. Online: 4 Mult, 3 Recon. Offline: 2 Mult, 2 RandInt( ), 1 RandBit ( ), 1 RandInt( ), 1 Randint().

[0084] Theorem 1. The equal-to-zero protocol EQZ is correct.

[0085] Proof. First notice that by Proposition 3, f=0 if a=0, and f= or 1 if a0. So then s= if a=0 and s=+1 or +2 if a0. Since is qr and +1, +2 are qnr, =1 if a=0 and =1 if a0. Consequently, z=1 if a=0 and z=0 if a0, as desired.

[0086] We now pivot to the question of finding a suitable for EQZ. A well-studied question in number theory regards patterns of quadratic residues modulo a given prime. In particular, one may fix a pattern, e.g. (qr, qnr, qnr), and ask how many .sub.p satisfy: is qr, and +1, +2 are qnr. Note that the pattern should not wrap around p. We will consider the case where p=3 mod 4 and the pattern is (qr, qnr, qnr). With minor changes, EQZ also works when the pattern is (qr, qnr, qnr). First, we collect a few well-known properties of quadratic residues and the Legendre symbol

[00019]$\left(\frac{.Math.}{p}\right).$

[0087] Lemma 4. Let p=3 mod 4 be prime,

[00020]$\left(x\right)=\frac{x}{p},$

and f.sub.p[x]. [0088] (i) For all x, y.sub.p, (xy)=(x)(y). [0089] (ii)

[00021]${.Math.}_{x=0}^{p-1}\left(x+c\right)=0$ for all c.sub.p. [0090] (iii) If f(x)=f(x) for all x.sub.p, then

[00022]${.Math.}_{x=0}^{p-1}\left(f\left(x\right)\right)=-1.$ [0091] (iv) If f is quadratic and monic with nonzero discriminant, then

[00023]${.Math.}_{x=0}^{p-1}\left(f\left(x\right)\right)=-1.$

[0092] We now show that almost all primescertainly the ones large enough to be of use for EQZhave a pattern of the form (qr, qnr, qnr).

[0093] Proposition 4. If p=3 mod 4 is prime, then the number N(p) of a.sub.p such that (a, a+1, a+2) is (qr, qnr, qnr) satisfies N(p)(p3)/8.

[0094] Proof. Again, let

[00024]$\left(x\right)=\left(\frac{x}{p}\right).$

Put .sub.i=(a+i), i=0, 1, 2.

[0095] Suppose (a, a+1, a+2) is (qr, qnr, qnr). Notice that in this implies .sub.0=1 and .sub.1=.sub.2=1. Define q(a):=(1+(a))(1(a+1))(1(a+2)), and observe that

[00025]$\begin{array}{cc}q\left(a\right)=\{\begin{array}{cc}8,& \mathrm{if}\left(a,a+1,a+2\right)\mathrm{is}\left(\mathrm{qr},\mathrm{qnr},\mathrm{qnr}\right)\\ 0,& \mathrm{otherwise}\end{array}& \mathrm{Eq}.4\end{array}$

[0096] So the number of a.sub.p which yield the pattern is

[00026]$N\left(p\right)=1/8{.Math.}_{a=0}^{p-3}q\left(a\right).$

The sum only goes to p3 because the pattern cannot wrap around p by definition. Now, multiply out q(a) and use Lemma 4(i) to get

[0097] See Section A at the end of this detailed disclosure for proof of Lemma 4.

[00027]$\begin{array}{cc}1+\left(a\right)-\left(a+1\right)-\left(a+2\right)-\left(a^2+a\right)-\left(a^2+2a\right)+\left(a^2+3a+2\right)+\left(a\left(a+1\right)\left(a+2\right)\right).& \mathrm{Eq}.5\end{array}$

[0098] Now we apply Lemma 4 to the sum of Equation 5 over a=0, 1, . . . , p3 to obtain a closed form for

[00028]$N\left(p\right)={.Math.}_{a=0}^{p-3}q\left(a\right).$${.Math.}_{a=0}^{p-3}1=p-3.$${.Math.}_{a=0}^{p-3}\left(a\right)={.Math.}_{a=0}^{p-1}\left(a\right)-\left(p-2\right)-\left(p-1\right)=1+\left(2\right).$${.Math.}_{a=0}^{p-3}\left(a+1\right)={.Math.}_{a=0}^{p-1}\left(a+1\right)-\left(p-1\right)-\left(p\right)=1.$${.Math.}_{a=0}^{p-3}\left(a+2\right)={.Math.}_{a=0}^{p-1}\left(a+2\right)-\left(p\right)-\left(p+1\right)=-1.$${.Math.}_{a=0}^{p-3}\left(a^2+a\right)={.Math.}_{a=0}^{p-1}\left(a^2+a\right)-\left(p^2-3p+2\right)-\left(p^2-p\right)=-1-\left(2\right).$${.Math.}_{a=0}^{p-3}\left(a^2+2a\right)={.Math.}_{a=0}^{p-1}\left(a^2+2a\right)-\left(p^2-2p\right)-\left(p^2-1\right)=0.$${.Math.}_{a=0}^{p-3}\left(a^2+3a+2\right)={.Math.}_{a=0}^{p-1}\left(a^2+3a+2\right)-\left(p^2-p\right)-\left(p^2+p\right)=-1.$

[0099] The last term requires an easy substitution. First, we see that

[00029]${.Math.}_{a=0}^{p-3}\left(a\left(a+1\right)\left(a+2\right)\right)={.Math.}_{a=0}^{p-1}\left(a\left(a+1\right)\left(a+2\right)\right)-\left(\left(p-2\right)\left(p-1\right)p\right)-\left(\left(p-1\right)p\left(p+1\right)\right)={.Math.}_{a=0}^{p-1}\left(a\left(a+1\right)\left(a+2\right)\right).$

Now replacing a by b1, we see the latter sum is equivalent to

[00030]${.Math.}_{b=0}^{p-1}\left(\left(b-1\right)b\left(b+1\right)\right).$

Lemma 4(iii) then implies that

[00031]${.Math.}_{b=0}^{p-1}\left(\left(b-1\right)b\left(b+1\right)\right)=0.$

[0100] Putting the above computations together yields

[00032]$N\left(p\right)=1/8{.Math.}_{a=0}^{p-3}q\left(a\right)=\left(p+2\left(2\right)-1\right)/8.$

Since (2)=1, it follows that N(p)(p3)/8, completing the proof.

[0101] Corollary 1. Let p=3 mod 4 be prime. If p11, then there is at least one a.sub.p such that (, +1, +2) is (qr, qnr, qnr).

[0102] The takeaway is that for any sufficiently large prime p, one can find an such that (, +1, +2) is (qr, qnr, qnr). For arbitrary primes, we suspect that a small which yields the pattern can be found because of the apparent randomness of the distribution of quadratic residues. This remains speculation, however. Fortunately, we can provide specific primes which work. Consider, for example, the Mersenne primes 2.sup.1271 and 2.sup.6071. For both primes, taking =4 yields the desired pattern: (4, 5, 6) is (qr, qnr, qnr).

5.1 EQZ Parameters

[0103] How large does the prime modulus need to be for EQZ to work with integers a of a fixed bit-size? The only relevant constraint is that FuzzyRound([a.sup.2/(a.sup.2+1)], 2, 1, ) needs to be defined. In particular, using the constraints listed in Protocol 5 with

[00033]$a_{\max }=\underset{a}{\max }\left\{.Math.a.Math.\right\}\mathrm{and}={\log }_2\left(a_{\max }^2\right)+2$

we obtain

[00034]$\begin{array}{cc}{2}^{-}N4a_{\max }^2+4a_{\max }^2\left(a_{\max }^2+1\right)+\left(a_{\max }^2+1\right)=4a_{\max }^4+9a_{\max }^2+1& \mathrm{Eq}.6\end{array}$

[0104] If |a.sub.max|=2.sup.1, then taking log.sub.2(N)=4++3 suffices. This results in a prime modulus of size log.sub.2(p)8+2+7.

6 Arithmetic Comparison

[0105] Before introducing the comparison protocol, we introduce two new protocols on which it relies.

6.1 Mod Reduction Protocols

[0106] Here we present two new protocols for computing mod reductions. The first is a probabilistic mod reduction which takes as inputs secret-shared integers a, b. The second is a mod 2 protocol, which computes a mod 2 for an integer input a.

[0107] Probabilistic mod reduction. Using FuzzyRound, we introduce a new protocol which computes a mod b for shared integers a, b.sub.N. It is probabilistic in the sense that its output lies in either (b, 0] or [0, b). Recall that for integers a, b with b>0,

[00035]$\begin{array}{cc}a\mathrm{mod}b=a-b.Math.\frac{a}{b}.Math.[0,b)& \mathrm{Eq}.7\end{array}$

[0108] If we use FuzzyRound on [a/b] with precision k=0, then the output is either a/b or a/b, depending on the value of the fractional part of a/b. Using Equation 7, we then get:

[00036]$\begin{array}{cc}\left[a\right]-Mult\left(\left[b\right],\mathrm{FuzzyRoun}d\left(\left[a/b\right],B,0,\right)\right)=\left[a\mathrm{mod}b\right]\mathrm{or}\left[\left(a\mathrm{mod}b\right)-b\right].& \mathrm{Eq}.8\end{array}$

[0109] From Equation 8, we get the following protocol.

[0110] Protocol 4: Secure probabilistic a modulo b.

TABLE-US-00004 Inputs. Shares of (encodings of) integers a, b .sub.N, and a security parameter . Constraints. a, b need to be small enough relative to N so that FuzzyRound([a/ b], B, 0, ) is defined. [f] FuzzyMod([a], [b], ) 1. [a/b] = Div([a], [b]); 2. [f] = FuzzyRound([a/b], B, 0, );// The value of B is irrelevant here 3. [m] = [a] Mult([b], [f]); 4. return [m]. Invocations. Online: 3 Mult, 2 Recon. Offline: 1 RandInt( ), 1 RandInt( ), 1 RandInt().

[0111] Mod 2 protocol. This protocol relies on the fact that FuzzyMod can be modified to accept a public modulus. The modification is defined by

[00037]$\begin{array}{cc}FuzzyMo{d}_{pub}\left(\left[a\right],b,\right)=\left[a\right]-\left(b.Math.\mathrm{FuzzyRound}\left(\left[a\right]/b,B,0,\right)\right).& \mathrm{Eq}.9\end{array}$

[0112] The division and multiplication in steps 1 and 3 of FuzzyMod are replaced by division by a public value and multiplication by a public value. Since the latter two operations can be performed locally, FuzzyMod.sub.pub only requires one invocation of FuzzyRoundone Mult, and RandInt(), RandInt(). Notice that if we take b=2, the fact that FuzzyMod.sub.pub and FuzzyMod have the same range implies:

[00038]$\begin{array}{cc}FuzzyMo{d}_{pub}\left(\left[a\right],2,\right)=\{\begin{array}{cc}1,& \mathrm{if}a\mathrm{is}\mathrm{odd}\\ 0,& \mathrm{if}a\mathrm{is}\mathrm{even}\end{array}& \mathrm{Eq}.10\end{array}$

[0113] Thus, to compute a mod 2, we simply need to use Equation 10 and then square the result.

[0114] Protocol 5: Secure a mod 2.

TABLE-US-00005 Inputs. Shares of (encodings of) integer a .sub.N, and a security parameter . Constraints. a needs to be small enough relative to N so that FuzzyRound([a/2], B, 0, ) is defined. [f] Mod2([a], ) 1. [f] = FuzzyMod.sub.pub([a], 2, ); 2. [b] = Mult([f], [f]); 3. return [b] = [a mod 2]. Invocations. Online: 1 Mult, 1 Recon. Offline: 1 RandInt( ), 1 RandInt().

6.2 the Comparison Protocol

[0115] We first introduce a restricted version of the protocol that requires the input to be a quadratic residue, then generalize so that the input may be a residue or a non-residue.

[0116] Protocol 6: Greater-than-zero test for quadratic residues.

TABLE-US-00006 Inputs.Shares of an integer a .sub.N, and a security parameter . [00039]$\mathrm{Constraints}.a0,p=3\mathrm{mod}4,p=7\mathrm{mod}8,\left(\frac{a}{p}\right)=1,\mathrm{and}{\left(2a\right)}^2+1<N\mathrm{small}$ enough so that FuzzyMod([(2a 1).sup.2], [(2a).sup.2 + 1], ) is defined. [(a >.sup.? 0)] QResGTZ([a], ). 1.[] = 2[a]; 2.[.sup.2] = Mult([], []); 3.compute [2] = 2[], [.sup.2 + 1] = [.sup.2] + 1, and [( 1).sup.2] = [.sup.2 + 1] [2]; 4.[f] FuzzyMod([( 1).sup.2], [.sup.2 + 1], ); 5.[ ] = Legendre([f]); 6.[b] = (1 [ ])/2; 7.[m] = [f] + Mult([b], [.sup.2 + 1]); 8.[s] = Mod2([m]); 9.return [s] = [(a >.sup.? 0)]. Invocations.Online: 7 Mult, 4 Recon. Offline: 2 Mult, 1 RandBit( ), 2 RandInt( ), 2 RandInt( ), 2 RandInt().

[0117] Theorem 2 (Correctness of Quadratic Residue Comparison). The restricted comparison protocol QResGTZ is correct.

[0118] Proof. Suppose the secret-sharing modulus p is prime, and that p=3 mod 4 and p=7 mod 8. First observe that >0.Math.(1).sup.2 mod(.sup.2+1)=(1).sup.2 and <0.Math.(1).sup.2 mod(.sup.2+1)=2. From Equation 8 and the fact that 2<.sup.2+1, we obtain:

[00040]$\begin{array}{cc}f=FuzzyMod\left(\left[{\left(-1\right)}^2\right],\left[{}^2+1\right],\right)=\{\begin{array}{cc}\begin{array}{c}{\left(-1\right)}^2\\ -2\\ 2\\ -{\left(-1\right)}^2\end{array}& \begin{array}{c}\mathrm{if}>0\\ \mathrm{if}<0\end{array}\end{array}& \mathrm{Eq}.11\end{array}$

[0119] Notice that 2 and (1).sup.2 are incorrect outputs in the sense that they are of the form (x mod y)y instead of x mod y.

[0120] Since p=7 mod 8 and p=3 mod 4, 2 is a quadratic residue mod p, and for any integer z such that pz only one of z and z is a quadratic residue mod p. Since a was chosen to be a quadratic residue mod p and 2 is also a quadratic residue, 2 is a quadratic non-residue. Further, (1).sup.2 is clearly a quadratic residue, so (1).sup.2 is a quadratic non-residue. Let

[00041]$=\left(\frac{f}{p}\right).b=\left(1-\right)/2$

is a bit which is set to 1 if f is a quadratic non-residue mod p, and 0 otherwise. This bit allows us to correct the output of FuzzyMod if necessary i.e. convert ((1).sup.2 mod .sup.2+1)(.sup.2+1) to (1).sup.2 mod .sup.2+1. It follows that

[00042]$\begin{array}{cc}m=f+b\left({}^2+1\right)=\{\begin{array}{cc}{\left(-1\right)}^2,& \mathrm{if}>0\\ 2,& \mathrm{if}<0\end{array}& \mathrm{Eq}.12\end{array}$

[0121] =2a is even, so (1).sup.2 is odd. Consequently, (>.sup.?0)=m mod 2. The result follows since a and have the same sign.

[0122] QResGTZ can be generalized to accept inputs which are quadratic non-residues with the addition of a few simple steps.

[0123] Protocol 7: General greater-than-zero test.

TABLE-US-00007 Inputs.Shares of an integer a .sub.N, and a security parameter . [00043]$\mathrm{Constraints}.a0,p=3\mathrm{mod}4,p=7\mathrm{mod}8,\left(\frac{a}{p}\right)=1,\mathrm{and}{\left(2a\right)}^2+1<N\mathrm{small}$ enough so that FuzzyMod([(2a 1).sup.2], [(2a).sup.2 + 1], ) is defined. [(a >.sup.? 0)] GTZ([a], ). 1.[l] = Legendre([a]); 2.[a] = Mult([l], [a]); 3.[b] = QResGTZ([a], ); 4.[s] = 2[b] 1; 5.[b] = (1 + Mult([s], [l]))/2; 6.return [b] = [(a >.sup.? 0)]. Invocations.Online: 10 Mult, 5 Recon. Offline: 4 Mult, 2 RandBit( ), 3 RandInt( ), 2 RandInt( ), 2 RandInt(o).

[0124] Corollary 2 (Correctness of GTZ). The comparison protocol GTZ is correct.

[0125] Proof. Since the secret-sharing prime is congruent to 3 modulo 4, the product

[00044]$a^{}=a.Math.\left(\frac{a}{p}\right),$

where pa, is always a nonzero quadratic residue modulo p. b=QResGTZ([a], ) is 1 if a>0 and 0 if a<0. This is the output we want if a and a have the same signi.e. if

[00045]$\left(\frac{a}{p}\right)=1.$

However, if

[00046]$\left(\frac{a}{p}\right)=-1,$

then a and a have opposite signs. First note that s=2b1 is 1 when a>0 and 1 when a<0.

[0126] Case 1:

[00047]$l=\left(\frac{a}{p}\right)=1.$

b=(1+s)/2=b=(a>.sup.?0). Since a, a have the same sign, b=(a>.sup.?0).

[0127] Case 2:

[00048]$l=\left(\frac{a}{p}\right)=-1.$

b=(1s)/2=1b=1(a>.sup.?0). Since a, a have opposite signs, b=(a>0).

[0128] This completes the proof.

[0129] As with EQZ, one may ask how to find primes which enable GTZnamely, primes which are congruent to 3 modulo 4 and 7 modulo 8. This turns out to be quite easy. In fact, the Mersenne primes 2.sup.1271 and 2.sup.6071 from section 5 both work.

6.3 GTZ Parameters

[0130] The only relevant constraint is that FuzzyMod([(2a1).sup.2], ((2a).sup.2+1), ) must be defined, which means that FuzzyRound([(2a1).sup.2/((2a).sup.2+1)], B, 0, ) must be defined. Let

[00049]$a_{\max }=\underset{a}{\max }\left\{.Math.a.Math.\right\}.$

Taking =log.sub.2((2a.sub.max1).sup.2) we obtain

[00050]$\begin{array}{cc}{2}^{-}N{\left(2a_{\max }-1\right)}^2+{\left(2a_{\max }-1\right)}^2\left({\left(2a_{\max }\right)}^2+1\right)+\left({\left(2a_{\max }\right)}^2+1\right)& \mathrm{Eq}.13\end{array}$

If a.sub.max=2.sup.1, then 2.sup.N=2.sup.4+5 satisfies Equation 13. This results in a prime modulus of size log.sub.2(p)8+2+11.

7 Security of FuzzyRound, EQZ, and GTZ

[0131] As discussed in section 2.1, our protocols inherit the security of the functionalities they use .sub.ABB and those for generating randomnessas long as any values revealed during the protocols is statistically indistinguishable from random. For example, in both HgDiv and Legendre, a value of the form randomsecret is revealed. This does not reveal any information about the secret, if s.sub.p is fixed and r.sub.p, then rs is uniformly random in .sub.p. Consequently, HgDiv and Legendre inherit the security of the functionalities.

[0132] The only other time a value is revealed that could leak information about a secret is in step 4 of FuzzyRound where an additively-masked secret is revealed. However, by lemma 3 the statistical distance between the distribution of the revealed value and the uniform distribution over the range of the revealed value is negligible in the security parameter . This result, along with Canetti's composition theorem, implies that FuzzyRound, EQZ, and GTZ are as secure as the functionalities they use.

8 Field Size and Rational Secrets

[0133] Use the derived parameters, we show what size of prime modulus is required for various sizes of inputs to EQZ and GTZ. We also show, as promised in section 3.3, how to select the subset .Math. in order to ensure correctness of protocols. Specifically, choosing to be a set of fixed-point numbers of various sizes and precisions will be discussed.

8.1 how Large does .sub.p Need to Be?

[0134] Recall that both EQZ and GTZ take as input integers in .sub.N. Moreover, since [N, N] is the set of all integers in .sub.N, the integer inputs must be chosen small enough so that computations (e.g. step 2 in Protocol 6) do not overflow .sub.N. In table 1, we use the parameters provided in sections 5.1 and 6.3 to estimate the size of prime modulus required for EQZ and GTZ to work with integers of various bit sizes and values of the security parameter .

TABLE-US-00008 TABLE 1 Approximate values for log.sub.2(p), where p is the secret sharing modulus, for inputs with absolute value up to 2.sup. 1 for various values of and the security parameter . E.g. GTZ with 32-bit integer inputs and = 40 requires a field .sub.p with log.sub.2(p) 347. = 30 = 40 Input Size EQZ GTZ EQZ GTZ 8 131 135 151 155 16 195 199 215 219 32 323 327 343 347 64 579 583 599 603

8.2 Rational Secrets: Fixed-Point Numbers

[0135] Fixed-point numbers are rational numbers represented as a list of digits split by a radix point, and are defined by an integer in a given range represented in some base b along with a fixed scaling factor f (called the precision). In particular, we can represent binary fixed-point numbers with integral part in the range (2.sup.l+1, 2.sup.l+1) and up to f decimal places after the radix point as a.Math.2.sup.f=a/2.sup.f, a(2.sup.l+f+1, 2.sup.l+f+1). This set will be denoted by FX.sub.l,f, the (1+f)-bit binary fixed-point numbers with f-bit bit precision.

[0136] Observe that, .sub.NFX.sub.l,f as long as N2.sup.l+f+11. It follows easily that the Mercury protocols paired with FuzzyRound yield protocols for multiplication and division of fixed-point numbers. The online cost for fixed-point multiplication is 1 Mult and 1 Recon. For fixed-point division, it is 2 Mult and 2 Recon. It turns out that using the field sizes given in table 1 is sufficiently large to enable these fixed-point operations. In particular, parameters which allow EQZ and GTZ to work with -bit integer inputs also allow fixed-point multiplication and division over FX.sub.l,f as long as 1+f=.

9 Complexities with Shamir Secret Sharing

[0137] Suppose the underlying LSSS is Shamir's (t+1)-out-of-n secret-sharing scheme with an honest majority of semi-honest parties. Henceforth, n denotes the number of parties, and t+1 the reconstruction threshold: any t+1 parties can obtain the secret, but any t or fewer can learn nothing about the secret.

[0138] We assume that the reconstruct protocol Recon reveals a secret s as follows: any t+1 parties send their share of s to every other party so each party has at least t+1 shares, then each party reconstructs s locally. Recon requires 1 online round and has online communication complexity (t+1)(n1) field elements. Mult is realized by the the protocol of Gennaro et al. This version of Mult takes 1 online round, has communication complexity (2t+1)(n1) field elements, and requires t<n/2.

[0139] An Optimization. The aforementioned multiplication in Shamir's scheme requires the parties to multiply their shares locally, increasing the number of shares required for reconstruction from t+1 to 2t+1. They then perform 1 round of communication to reduce the reconstruction threshold back to t+1. In the case that a protocol requires a multiplication followed immediately by a reconstruction, which requires 2 online rounds, we can reduce the complexity to 1 online round at the cost of slightly increasing the communication complexity. This is done by performing the local multiplication, and then reconstructing with 2t+1 parties instead of t+1. The communication complexity increases from (t+1)(n1) to (2t+1)(n1). This optimization makes the online round complexities of Legendre and HgDiv to 1 and 2, respectively. Consequently, the online rounds required for EQZ and GTZ using Shamir's scheme are 5 and 11, respectively.

[0140] Using the communication complexities of above protocols, we obtain the communication complexities of EQZ and GTZ.

TABLE-US-00009 TABLE 2 Online communication (measured in field elements sent by all parties) for the equality and comparison protocols. Protocol Shamir's Scheme Online Comm. EQZ (9t + 5)(n 1) GTZ (22t + 12)(n 1)

[0141] The complexities listed in table 2 do not paint a complete picture of the online communication complexities of EQZ and GTZ. In particular, we must combine the field sizes listed in table 1 with the communication complexities in table 2. Table 3 does exactly this, and lists the communication complexities of EQZ and GTZ in kilobytes (KB). For us, 1 kilobyte is 1000 bytes. To convert to 1 KB=1024 B, multiply the communication complexities in Table 3 by 1000/10240.98.

TABLE-US-00010 TABLE 3 Estimated online communication in KB between all parties during EQZ and GTZ using 2-out-of-3 Shamir secret sharing and security parameter = 40. Input Size (bits) 8 16 32 64 EQZ 0.528 0.753 1.201 2.097 GTZ 1.318 1.862 2.950 5.126

[0142] In general, using honest-majority Shamir's scheme with passive adversaries both EQZ and GTZ have online communication complexity O(tn log.sub.2(p)) bits. Of course, this could change depending on the protocols chosen to realize Mult and Recon.

10 Conclusion and Future Work

[0143] Conclusions. We have presented three novel arithmetic protocols intended for multi-party computation from secret-sharing: FuzzyRound, EQZ, and GTZ. FuzzyRound is a probabilistic rounding protocol that approximates a secret Farey rational x/y by z/B.sup.k, where B and k are public values which can be chosen to suit the desired application. The remaining two protocols, EQZ and GTZ, use FuzzyRound along with a quadratic residue test protocol to, respectively, securely test whether an integer is equal to zero or positive. Notably, EQZ and GTZ do not depend on the binary representation of their inputs.

A: Proof of Lemma 4

[0144] Proof. Clearly every element of .sub.p is qr or qnr. It is well-known that .sub.p contains (p+1)/2 qr and (p1)/2 qnr. Moreover, since p=3 mod 4, if a.sub.p is nonzero, then one of a, a is qr and the other is qnr. Equivalently, (x)=(x). [0145] (i) This follows immediately from properties of congruences. [0146] (ii) x+x+c is a bijection from .sub.p to .sub.p, so

[00051]${.Math.}_{x=1}^p\left(x+c\right)={.Math.}_{x=1}^p\left(x\right)={.Math.}_{x=1}^{\left(p-1\right)/2}\left(x\right)+\left(-x\right)=0.$ [0147] (iii)

[00052]${.Math.}_{x=1}^p\left(f\left(x\right)\right)={.Math.}_{x=1}^{\left(p-1\right)/2}\left(f\left(x\right)\right)+\left(f\left(-x\right)\right)={.Math.}_{x=1}^{\left(p-1\right)/2}\left(f\left(x\right)\right)+\left(-f\left(x\right)\right)=0.$ [0148] (iv) Say f(x)=x.sup.2+bx+c=4.sup.1((2x+b).sup.2(b.sup.24c)). If the discriminant b.sup.24c0, then we can rewrite f as f(x)=4.sup.1(X.sup.2D) where D is nonzero. Since 4.sup.1=(2.sup.1).sup.2 is always qr,

[00053]${.Math.}_{x=1}^p\left(f\left(x\right)\right)={.Math.}_{x=1}^p\left(X^2-D\right).$ Now, consider the equation

[00054]$\begin{array}{cc}{Y}^2=X^2-D,\mathrm{where}X,Y{}_p.& \mathrm{Eq}.14\end{array}$

[0149] This is equivalent to (XY)(X+Y)=D. Now, the mapping (X, Y)(u=XY, v=X+Y) is given by the matrix

[00055]$M=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right].$

Since p2, det(M)=20, which means the mapping is bijective. Consequently, the number of solutions (X, Y) of Equation 14 is the same as the number of solutions (u, v) of uv=D. For each u0, there is only one v such that uv=D, whence Equation 14 has exactly p1 solutions. On the other hand, for a fixed X, the number of solutions (X, Y) of Equation 14 is: 0 if X.sup.2D is qnr, 1 if X.sup.2D=0, and 2 if X.sup.2D a qr. So the number of solutions for a fixed Y is given succinctly as 1+(X.sup.2D). This implies that the number of solutions of Equation 14 is

[00056]${.Math.}_{x=1}^p\left(1+\left(X^2-D\right)\right).$

But because the aforementioned mapping is a bijection each solution of Equation 14 corresponds to a solution of uv=D. Consequently,

[00057]$p-1={.Math.}_{x=1}^p\left(1+\left(X^2-D\right)\right),$

which implies

[00058]${.Math.}_{x=1}^p\left(X^2-D\right)=-1.$

Hardware Implementation for an Embodiment (FIG. 1)

[0150] FIG. 1 is a block diagram 100 of the hardware implementation for an embodiment. A 1.sup.st data server computing device 102 is connected over an electronic network/bus connection 108 to a 2.sup.nd data server computing device 104. The 2nd data server computing device 104 is further connected over an electronic network/bus connection 110 to a 3.sup.rd data server computing device 106. Each of the data server computing devices are running the Multi-Party Computation (MPC) system 112.

[0151] In the embodiment shown in FIG. 1, the 1.sup.st data server computing device 102 acts as the source of the encoded integer(s) 108 and the 1.sup.st data server computing device 102 sends the encoded integer(s) 108 over the network/bus connection 108 to the 2.sup.nd data server computing device 104. For the use of the arithmetic comparison of the encoded initial rational number by a second rational, the 1.sup.st data server computing device 102, encodes the second rational number into a second encoded integer and sends the second rational number 108 to the 2.sup.nd data server computing device 104.

[0152] The encoded integer(s) 108 start at the 1.sup.st data server computing device as rational numbers, which may be in fixed-point format. An embodiment at the 1.sup.st data server computing device 102 encodes the rational numbers into the corresponding encoded integer(s) 108 as a function of in the domain of Farey rationals.

[0153] Generally, communications, including concealed/encrypted communications, are bi-directional and may be connected between any of the data server computing devices 102-106, such that data server computing devices 102-106 may change roles as is necessary to accommodate the transfer of data back and forth between the data server computing devices 102-106. Additionally, while the data server computing devices 102-106 are depicted as separate devices in FIG. 1, the functionality of the data server computing devices 102-106 may be shared on a single computing system/device or among two or more computing devices.

[0154] Further, as shown in FIG. 1, the data server computing devices 102-106 appear to be laptop computers, but any computing device or system may be satisfactory. Generally, any computing device capable of communication over any form of electronic network or bus communication platform may be one or more of the data server computing devices 102-106. Additionally, data server computing devices 102-106 may actually be the same physical computing device communicating over an internal bus connection with itself.

[0155] Various embodiments may implement the network/bus communications channel 108-110 using any communications channel 108-110 capable of transferring electronic data between the data server computing devices 102-106. For instance, the network/bus communication connection 108-110 may be an Internet connection routed over one or more different communications channels. Likewise, the network/bus communication connection 108-110 may be an internal communications bus of a computing device, or even the internal bus of a processing or memory storage Integrated Circuit (IC) chip, such as a memory chip or a Central Processing Unit (CPU) chip. The network/bus communication channel 108-110 may utilize any medium capable of transmitting electronic data communications, including, but not limited to: wired communications, wireless electro-magnetic communications, fiber-optic cable communications, light/laser communications, sonic/sound communications, etc., and any combination thereof of the various communication channels.

[0156] The various embodiments may provide the control and management functions detailed herein via an application operating on the data server computing devices 102-106. The data server computing devices 102-106 may each be a computer or computer system, or any other electronic devices capable of performing the communications and computations of an embodiment. The data server computing devices 102-108 may include, but are not limited to: a general-purpose computer, a laptop/portable computer, a tablet device, a smart phone, an industrial control computer, a data storage system controller, a CPU, a Graphical Processing Unit (GPU), an Application Specific Integrated Circuit (ASIC), and/or a Field Programmable Gate Array (FPGA). Notably, the data server computing devices 102-106 may be the storage controller of a data storage media (e.g., the controller for a hard disk drive). Embodiments may be provided as a computer program product which may include a computer-readable, or machine-readable, medium having stored thereon instructions which may be used to program/operate a computer (or other electronic devices) or computer system to perform a process or processes in accordance with the various embodiments. The computer-readable medium may include, but is not limited to, hard disk drives, floppy diskettes, optical disks, Compact Disc Read-Only Memories (CD-ROMs), Digital Versatile Disc ROMS (DVD-ROMs), Universal Serial Bus (USB) memory sticks, magneto-optical disks, ROMs, random access memories (RAMs), Erasable Programmable ROMs (EPROMs), Electrically Erasable Programmable ROMs (EEPROMs), magnetic optical cards, flash memory, or other types of media/machine-readable medium suitable for storing electronic instructions. The computer program instructions may reside and operate on a single computer/electronic device or various portions may be spread over multiple computers/devices that comprise a computer system. Moreover, embodiments may also be downloaded as a computer program product, wherein the program may be transferred from a remote computer to a requesting computer by way of data signals embodied in a carrier wave or other propagation medium via a communication link (e.g., a modem or network connection, including both wired/cabled and wireless connections).

Operational Flow Chart for an Embodiment (FIG. 2)

[0157] FIG. 2 is a flow chart 200 of operations for an embodiment. At process 208, the 1.sup.st data server computing device 202 encodes one or more rational numbers into corresponding encoded integers in the domain of Farey rationals. At process 210, the 1.sup.st data server computing device 202 sends the encoded integers to the 2nd data server computing device 204. At process 212, the 2.sup.nd data server computing device 204, computes an arithmetic comparison result as of function of FuzzyRound operation, quadratic residues, and the encoded integers. Embodiments securely provide for evaluation of encoded rational numbers for arithmetic equality equal to zero or not, probabilistic modulo of two rational numbers, probabilistic modulo of a rational number by a public value of two, a test for whether a rational number is greater-than-zero for quadratic residues and a general greater-than-zero test for a rational number which are quadratic non-residues.

[0158] At process 214, the 2.sup.nd data server computing device 204 sends the arithmetic comparison result to the 3.sup.rd data server computing device 206. At process 216, the 3.sup.rd data server computing device uses the arithmetic comparison result in additional computation and logic.

[0159] Additionally, while the flow charts and flow chart details described above with respect to FIG. 2 describe a methodology that may be embodied as a method or process, another embodiment may be recognized as a computer system, and/or as an intermediary computing device that stores and/or performs homomorphic operations of encrypted data by implementing the processes described above with respect to the flow chart and flow chart details of FIG. 2. Further, in describing the computing system, and/or any intermediary computing system, one, or more, individual processes described above for the methodology may be broken down and represented as a subsystem of the overall encryption computer system. A subsystem of the computer system, in whole or in part, may be assigned to a particular hardware implemented system, such as a dedicated Application Specific Integrated Circuit (ASIC) or Field Programmable Gate Array (FPGA). One or more subsystems, in whole or in part, may alternatively be implemented as software or firmware instructions defining the operation of a computer system with specific regard to the one or more subsystems implemented as software or firmware instructions. The software or firmware instructions may cause the Central Processing Unit, memory, and/or other systems of a computer system to operate in particular accordance with the particular one or more subsystems designated features.

[0160] The foregoing description of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and other modifications and variations may be possible in light of the above teachings. The embodiments were chosen and described in order to best explain the principles of the invention and its practical application to thereby enable others skilled in the art to best utilize the invention in various embodiments and various modifications as are suited to the particular use contemplated.