METHODS AND SYSTEMS FOR ADDITION, MULTIPLICATION, SUBTRACTION, AND DIVISION OF RATIONAL NUMBERS ENCODED IN THE DOMAIN OF FAREY RATIONALS FOR MPC SYSTEMS

Abstract

Disclosed are methods and systems to provide encoding and decoding using of p-adic arithmetic, and inverse p-adic arithmetic, in the domain of Farey rationals that is induced by a ring isomorphism, such that said encoded integers preserve inverses, and additive and multiplicative homomorphic properties. This encoding permits MPC systems to perform arithmetic more efficiently and accurately, particularly for division.

Claims

1. A method for Multi-Party Computation (MPC) 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 first rational number x.sub.0/y.sub.0 into a first encoded integer corresponding to said first rational number x.sub.0/y.sub.0 as an encode function of p-adic arithmetic in said domain of Farey rationals that is induced by a ring isomorphism performed on said first rational number x.sub.0/y.sub.0, such that said first encoded integer preserves inverses, and additive and multiplicative homomorphic properties; sending by said first data server computing device said first encoded integer to a third data server computing device; encoding by a second data server computing device a second rational number x.sub.1/y.sub.1 into a second encoded integer corresponding to said second rational number x.sub.1/y.sub.1 as said encode function of p-adic arithmetic in said domain of Farey rationals that is induced by a ring isomorphism performed on said second rational number x.sub.1/y.sub.1, such that said second encoded integer preserves inverses, and additive and multiplicative homomorphic properties; sending by said second first data server computing device said second encoded integer to said third data server computing device; computing by said third data server computing device an arithmetic function as part of said MPC system with said first encoded integer and said second encoded integer to obtain a result encoded integer; sending by said third data server computing device said result encoded integer to a fourth data server computing device; and decoding by said fourth data server computing device said result encoded integer into a result rational number x.sub.1/y.sub.1 corresponding to said result encoded integer as a decode inverse function of p-adic arithmetic in said domain of Farey rationals performed on said result encoded integer.

2. The method of claim 1 wherein said arithmetic function is addition performed according to the MPC system functions.

3. The method of claim 1 wherein said arithmetic function is subtraction performed according to the MPC system functions.

4. The method of claim 1 wherein said arithmetic function is division performed by inverting said second encoded integer and multiplying according to the MPC system functions by said first encoded integer to obtain said result encoded integer of said 1.sup.st encoded integer divided by said second encoded integer.

5. An Farey rational encoding system for Multi-Party Computation (MPC) on a Multi-Party Computation (MPC) system of rational data encoded in a domain of Farey rationals, the Farey rational encoding system comprising: a first data server computing system that encodes a first rational number x.sub.0/y.sub.0 into a first encoded integer corresponding to said first rational number x.sub.0/y.sub.0 as an encode function of p-adic arithmetic in said domain of Farey rationals that is induced by a ring isomorphism performed on said first rational number x.sub.0/y.sub.0, such that said first encoded integer preserves inverses, and additive and multiplicative homomorphic properties and sends said first encoded integer to a third data server computing device; a second data server computing device that encodes a second rational number x.sub.1/y.sub.1 into a second encoded integer corresponding to said second rational number x.sub.1/y.sub.1 as said encode function of p-adic arithmetic in said domain of Farey rationals that is induced by a ring isomorphism performed on said second rational number x.sub.1/y.sub.1, such that said second encoded integer preserves inverses, and additive and multiplicative homomorphic properties and sends said second encoded integer to said third data server computing device; said third data server computing device that computes an arithmetic function as part of said MPC system with said first encoded integer and said second encoded integer to obtain a result encoded integer and sends said result encoded integer to a fourth data server computing device; and said fourth data server computing device that decodes said result encoded integer into a result rational number x.sub.r/y.sub.r corresponding to said result encoded integer as a decode inverse function of p-adic arithmetic in said domain of Farey rationals performed on said result encoded integer.

6. The Farey rational encoding system of claim 5 wherein said arithmetic function is addition performed according to the MPC system functions.

7. The Farey rational encoding system of claim 5 wherein said arithmetic function is subtraction performed according to the MPC system functions.

8. The Farey rational encoding system of claim 5 wherein said arithmetic function is division performed by inverting said second encoded integer and multiplying according to the MPC system functions by said first encoded integer to obtain said result encoded integer of said 1.sup.st encoded integer divided by said second encoded integer.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0010] In the drawings,

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

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

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0013] Secure computation has become a necessity in the modern world. Its applications are widespread: from allowing medical researchers to compute statistics over private patient data without violating HIPAA (Health Insurance Portability and Accountability Act) to helping large companies like Meta and Google avoid GDPR (General Data Protection Regulation) fines. A ubiquitous and popular choice for secure computation is Multi-Party Computation (MPC). Most MPC protocols work over finite fields or rings, which means that encoding techniques are required to map rational-valued data into the algebraic structure being used. The various embodiments herein leverage an encoding technique introduced in U.S. patent application Ser. No. 18/535,875, filed Dec. 11, 2023, entitled Methods and Systems for P-Adic Encoding and Decoding of Rational Data for FHE Systems, and are presented herein as Mercury-a family of protocols for addition, multiplication, subtraction, and division of rational numbers. Notably, the output of an embodiment's division protocol is exact (i.e., it does not use iterative methods). The protocols of the various embodiments offer significant improvements in both round complexity and communication complexity when compared with prior art, and are secure for a dishonest minority of semi-honest parties. To reiterate, the encoding technique of the various embodiments' protocols are based on is composable, so it can be paired with any MPC protocol over a prime-order field.

1 INTRODUCTION

[0014] Secure computation is a tool which allows functions of private data to be evaluated without revealing those data. One such tool is homomorphic encryption (HE), which allows, e.g., a data owner to encrypt their data and outsource computations on those data. More specifically, anyone can compute reasonable functions of the encrypted data and never learn more about the data than what the output of the function reveals. However, most HE schemes are prohibitively slow, especially when computing products. Further, most HE schemes, with the exception of CKKS (Cheon, Kim, Kim, and Song), do not support division. The CKKS scheme can perform division by approximating the inverse function with a Taylor polynomial T(x)x.sup.1 and then computing c.sub.0/c.sub.1c.sub.0T(c.sub.1), for ciphertexts c.sub.0, c.sub.1.

[0015] Another well-studied form of secure computation is Multi-Party Computation (MPC). In the classic setting, n mutually distrusting parties P.sub.i possess private data d.sub.i and wish to jointly compute a function F(d.sub.1, . . . , d.sub.n) without revealing d.sub.i to P.sub.j for ij. Much work has been done extending these results, developing new tools for MPC, and implementing these tools in the real world. Many of these protocols rely on secret sharing. In secret sharing, each P.sub.i is provided masked pieces (called shares) of private data (henceforth, secrets). These shares are chosen such that only authorized sets of parties can determine a secret if they pool their shares. The parties use their shares to perform computations on the secrets by communicating (e.g., sending/receiving shares, creating and sending new shares, etc.) with one another as needed. A common primitive for secret sharing is Shamir's scheme, which is based on polynomial interpolation over a finite field. An advantage of the Shamir scheme is that it is additively homomorphic so that shares of two secrets can be added locally to give a sharing of the sum of those secrets. Additively homomorphic secret sharing is also used by the well-known MP-SPDZ framework.

[0016] Most MPC protocols are defined over finite rings or fields such as /n or GF (2.sup.l), and as such require real data (often in the form of fixed-point or floating-point numbers) to be encoded as elements of the ring (field). Further, since the goal is evaluating certain functions (e.g., polynomials) over secret shared values, the encoding method must be homomorphic with respect to the operations which compose the function (e.g., addition and multiplication). Some works encode a fixed-point or floating-point number a with precision f as the integer a.Math.2.sup.f. Other approaches work with floating-point numbers by separately encoding the sign, exponent, and significand, along with an extra bit that is set to 0 if, and only if, the number is 0.

[0017] The various embodiments differ significantly from all of these approaches. Instead of choosing a set of fixed-point numbers and designing the protocols around them, the various embodiments start with a set of rationals (with bounded numerators and denominators) which can be constructed to contain a desired set of fixed-point numbers. This set of rationals, paired with an encoding that is homomorphic with respect to both addition and multiplication, forms the basis of the protocols of the various embodiments. The range of the encoding may be any ring/field of the form /n. This means that, for the most part, the protocols of the various embodiments are obtained by simply attaching the encoder to existing protocols. The exception is division which relies heavily on the structure of the aforementioned set of rationals.

[0018] The protocols of the various embodiments require only a constant number of rounds and have communication complexity O(tn), where n is the number of parties and t1 is a bound on the number of corrupted parties. The protocols of the various embodiments are also generic, by which it is meant that the protocols do not depend on the underlying primitive being used. For example, even though the description of the various embodiments presented herein use Shamir's scheme as the example foundation, the protocols of the various embodiments for rational arithmetic could easily be translated to use additive secret sharing (e.g., implemented with MP-SPDZ). Moreover, the encoding technique on which the protocols of the various embodiments are based is composable, meaning that the encoding works with any MPC protocol based on secret sharing over a prime-order field.

2 PRELIMINARIES

2.1 Notation

[0019] For a positive integer a, /a denotes the ring of integers modulo a. In case a is prime, we write a. The elements of /a will be represented by integers 0, 1, . . . , a1. For a ring R, R[x] will denote the ring of polynomials with coefficients in R. 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). All circuits we consider are arithmetic over a field .sub.a, and have fan-in 2.

[0020] Shamir's scheme. Here is a brief overview of Shamir Secret Sharing (SSS), and the notation used therein. Suppose we have n parties and wish for any set of tn parties to be able to reconstruct a secret by pooling their shares. This is called t-out-of-n threshold scheme. One creates Shamir shares of a secret s.sub.p by generating a random polynomial f(x).sub.p[x] of degree at most t1 whose constant term is s (i.e., f(0)=s and whose remaining coefficients are chosen uniformly from .sub.p. Shares of s are the field elements f(i), iF.sub.p\{0}. We assume the i.sup.th party receives the share f(i). We use [x].sub.i to denote the i.sup.th party's share of x.sub.p, and [x] to denote a sharing of x among all parties. Then, for example, [x]+[y] will mean each party adds their share of x to their share of y, and c[x] will mean each party multiplies their share of x by c. Any collection of t parties can pool their shares [s] and reconstruct the polynomial f using Lagrange interpolation, thereby obtaining the secret s=f(0).

2.1 Framework

[0021] As mentioned above, we use t-out-of-n SSS over .sub.p for all protocols. The various embodiment's protocols are built on the basic Shamir addition, and the multiplication introduced by Gennaro, Rabin and Rabin, which is itself an optimization of the multiplication described by Ben-Or, Goldwasser and Wigderson. To ensure the multiplication protocol works, the various embodiments require t1<n/2. The various embodiments also tolerate up to t1 semi-honest (honest-but-curious) adversaries. The communication complexity of a protocol is measured by the number of field elements sent by all parties throughout the protocol. When comparing with protocols that measure communication complexity in bits, the embodiments simply multiply its communication complexities by log.sub.2(p).

3 PROTOCOLS FOR RATIONAL NUMBERS

[0022] A family of efficient MPC protocols for performing computations with rational numbers is proposed herein. These protocols are obtained by pairing an encoder that maps certain rational numbers to integers with the familiar SSS protocols for addition, multiplication, and computing modular inverses. The protocols for computing the sum and product of shared fixed-point numbers remain unchanged from the analogous SSS primitives, except that rational operands are encoded to field elements before any protocols are executed. Division is an amalgam of existing protocols and relies on the fact that the various embodiments' mapping for encoding rational numbers to integers is induced by a ring homomorphism, and therefore preserves inverses; likewise is true for the decode mapping. Further elaboration is given below.

3.1 Encoding Rationals

[0023] The various embodiments use the encoding map introduced in U.S. patent application Ser. No. 18/535,875, filed Dec. 11, 2023, entitled Methods and Systems for P-Adic Encoding and Decoding of Rational Data for FHE Systems, which maps a subset of rationals, whose denominators are co-prime with a prime p, into .sub.p using p-adic encoding and decoding supported by p-adic number theory. This map is defined by encode(x/y)=xy.sup.1 mod p, and has as its domain the Farey rationals:

[00002]$N_{}:=\left\{x/y:.Math.x.Math.N,0<yN,\gcd \left(x,y\right)=1,\gcd \left(p,y\right)=1\right\},$

where N=N(p):={square root over ((p1)/2)}. encode is induced by a ring isomorphism, so both it and its inverse decode are additively and multiplicatively homomorphic as long as the composition of operands in .sub.N remains in .sub.N

[00003]$\left(e.g.,\mathrm{encode}\left(\frac{x_0}{y_0}+\frac{x_1}{y_1}\right)=\mathrm{encode}\left(\frac{x_0}{y_0}\right)+\mathrm{encode}\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}_{}\right).$

decode can be computed efficiently using a slight modification of the Extended Euclidean Algorithm. We summarize important properties of encode, decode, and .sub.N with the following lemma.

[0024] Lemma 1. Let p be a prime, N=N (p), and encode, decode be the encode and decode maps, respectively. [0025] (i) If x/y.sub.N, then x/y.sub.N. [0026] (ii) If x/y.sub.N is nonzero, then y/x.sub.N. [0027] (iii) .sub.N is not closed under addition and multiplication. [0028] (iv) [N, N].Math..sub.N. Moreover, if [0, N], then encode()=. [0029] (v) encode and decode are homomorphic with regard to addition and multiplication as long as the composition of operands in .sub.N remains in .sub.N.

[0030] Proof. (i)-(iv) are obvious.

[0031] For (v), the mapping H.sub.p.sub.r: .sub.N.fwdarw..sub.p.sub.r and its inverse are defined as:

[00004]$H_{p^r}\left(\frac{x}{y}\right)={\mathrm{xy}}^{-1}\mathrm{mod}{p}^r,$$H_{p^r}^{-1}\left(h\right)=\mathrm{MEEA}\left(p^r,h\right).$

[0032] The H-mapping is injective and, therefore, gives a unique representation of each element of .sub.N in .sub.p.sub.r. The inverse of H.sub.p.sub.r is well-defined.

[0033] For all x/y.sub.N and hH.sub.p.sub.r(.sub.N).Math..sub.p.sub.r,

[00005]$\begin{array}{cc}{H}_{p^r}^{-1}\left(H_{p^r}\left(x/y\right)\right)=x/y,& \left(i\right)\end{array}$$\begin{array}{cc}{H}_{p^r}\left(H_{p^r}^{-1}\left(h\right)\right)=h,& \left(\mathrm{ii}\right)\end{array}$$\begin{array}{cc}\mathrm{If}a,a^{}\mathrm{and}{a}^{}=a\left(\mathrm{mod}{p}^r\right),\mathrm{then}{H}_{p^r}^{-1}\left(a\right)=H_{p^r}^{-1}\left(a^{}\right)& \left(\mathrm{iii}\right)\end{array}$

[0034] The mappings H.sub.p.sub.r and H.sub.p.sub.r.sup.1 are homomorphic with respect to addition and multiplication in the following sense.

[00006]$\begin{array}{cc}\mathrm{For}\mathrm{all}u,u^{}{N}_{},H_{p^r}\left(u\right).Math.H_{p^r}\left(u^{}\right)=H_{p^r}\left(u.Math.u^{}\right)\mathrm{mod}{p}^r\mathrm{and}& \left(i\right)\end{array}$$H_{p^r}\left(u\right)+H_{p^r}\left(u^{}\right)=H_{p^r}\left(u+u^{}\right)\mathrm{mod}{p}^r.$$\begin{array}{cc}\mathrm{If}h,h^{}{}_{p^r}\mathrm{and}{H}_{p^r}^{-1}\left(h\right).Math.H_{p^r}^{-1}\left(h^{}\right),H_{p^r}^{-1}\left(h\right)+H_{p^r}^{-1}\left(h^{}\right)N_{},\mathrm{then}& \left(\mathrm{ii}\right)\end{array}$$H_{p^r}^{-1}\left(h.Math.h^{}\right)=H_{p^r}^{-1}\left(h\right).Math.H_{p^r}^{-1}\left(h^{}\right)\mathrm{and}{H}_{p^r}^{-1}\left(h+h^{}\right)=H_{p^r}^{-1}\left(h\right)+H_{p^r}^{-1}\left(h^{}\right)$

[0035] Proof. (i) Let a/b, c/d.sub.N. By definition of the Farey rationals, a, b, c, d are co-prime with p. That H.sub.p.sub.r is homomorphic with respect to addition and multiplication follows from the properties of congruences:

[00007]${\mathrm{ac}\left(\mathrm{bd}\right)}^{-1}=\left({\mathrm{ab}}^{-1}\right)\left({\mathrm{cd}}^{-1}\right)\mathrm{mod}{p}^r\mathrm{and}$$\left(\mathrm{ad}+\mathrm{bc}\right){\left(\mathrm{bd}\right)}^{-1}=\left({\mathrm{ab}}^{-1}+{\mathrm{cd}}^{-1}\right)\mathrm{mod}{p}^r$ [0036] (ii) Invoking the homomorphic property of H.sub.p.sub.r, from H.sub.p.sub.r.sup.1(h).Math.H.sub.p.sub.r.sup.1(h), H.sub.p.sub.r.sup.1(h)+H.sub.p.sub.r.sup.1(h).sub.N we obtain h.Math.h, h+hH.sub.p.sub.r (.sub.N). By proposition 1(ii), H.sub.p.sub.r(H.sub.p.sub.r.sup.1(h.Math.h))=h.Math.h and H.sub.p.sub.r (H.sub.p.sub.r.sup.1(h+h))=h+h. The result follows from the injectivity of H.sub.p.sub.r.

PIE: A Rational Encoder/Decoder

[0037] The encoding/decoding map introduced in U.S. patent application Ser. No. 18/535,875, is given as a PIE (p-adic encoding) rational encoder and decoder as described in more detail below.

[0038] Let g be a positive integer, N={square root over ((g1)/2)}, and make .sub.N the input space. We define encoding and decoding as follows: [0039] PIE.Encode(x/y). For x/yF.sub.N output H.sub.g(x/y) [0040] PIE.Decode(z). For z.sub.g, output H.sub.g.sup.1(z)

[0041] For all m, m.sub.N such that m.Math.m.sub.N,

[00008]$\mathrm{PIE}.\mathrm{Decode}\left(\left[\mathrm{PIE}.\mathrm{Encode}\left(m\right).Math.\mathrm{PIE}.\mathrm{Encode}\left(m^{}\right)\mathrm{mod}g\right]\right)=m.Math.m^{}$

and m, m.sub.N such that m+m.sub.N

[00009]$\mathrm{PIE}.\mathrm{Decode}\left(\left[\mathrm{PIE}.\mathrm{Encode}\left(m\right)+\mathrm{PIE}.\mathrm{Encode}\left(m^{}\right)\mathrm{mod}g\right]\right)=m+m^{}$

[0042] Further, let p be a multivariate polynomial with coefficients in . For all m.sub.0, . . . , m.sub.k.sub.N such that p(m.sub.0, . . . , m.sub.k).sub.N,

[00010]$\mathrm{PIE}.\mathrm{Decode}\left(g,p\left(\mathrm{PIE}.\mathrm{Encode}\left(g,m_0\right),.Math.,\mathrm{PIE}.\mathrm{Encode}\left(g,m_k\right)\right)\mathrm{mod}g\right)=p\left(m_0,.Math.,m_k\right).$

[0043] For the encoding (and decoding) to yield the correct result when used in an MPC scheme, one must ensure that if two or more elements from .sub.N are combined using additions and/or multiplications then any intermediates and the final output must not lie outside the set .sub.N. For this reason, we will define the (rational) message space to be the following subset of .sub.N:

[00011]$M_{}=\left\{x/y{N}_{}:0.Math.x.Math.M,1yM\right\}$

[0044] The main idea behind choosing a subset of .sub.N as the set of messages is that when elements from .sub.M are combined, the resulting element can be in .sub.N. Ensuring the output lands in .sub.N induces a bound on the number of computations that can be performed, and determines the choice of parameters involved therein. At this point, one might wonder whether we need to do something similar with the range .sub.g of the encoder to make sure that overflow modulo g does not occur during computations. The answer is no. This is because proposition 3(iii) along with the above message space restriction imply that overflow modulo g does not affect decoding.

[0045] The choice of M depends jointly on the rational data one must encode, and the circuits one must evaluate over those data. We elaborate this in the following section.

Choosing the Message Space .sub.M.

[0046] We will describe an arithmetic circuit in terms of the multivariate polynomial it computes. To this end, recall that the .sub.1-norm of a polynomial is simply the sum of the absolute values of its coefficients.

[0047] Polynomials with which PIE is compatible. Let .sub.d,t denote the set of polynomials in [x.sub.1, x.sub.2, . . . ] with total degree at most d and .sub.1-norm at most t, whose coefficients have absolute value at least 1. For example, .sub.d,t contains polynomials of the form:

[00012]$p\left(x_1,.Math.,x_k\right)=\underset{d_1+.Math.+d_{k}d}{.Math.}\underset{=1}{\overset{I}{.Math.}}{c}_{}{x}_1^{d_1}{x}_1^{d_2}.Math.x_k^{d_k},$

where each |c.sub.|1, and .sub.|c.sub.|t.

[0048] The following establishes an upper bound on the output of a polynomial in .sub.d,t when all inputs are from .sub.M.

[0049] If x.sub.1/y.sub.1, . . . , x.sub.k/y.sub.k .sub.M, p.sub.d,t is k-variate, and p(x.sub.1/y.sub.1, . . . , x.sub.k/y.sub.k)=x/y, then:

|x|t.Math.M.sup.dt and |y|M.sup.dt

[0050] Proof. Note that .sub.d,t can be written as, p=.sub.ic.sub.ip.sub.i, where .sub.i|c.sub.i|t, each |c.sub.i|1, and each p.sub.i is a monomial of degree at most d.

[0051] Let p=.sub.i=1.sup.lc.sub.ip.sub.i.

[0052] Since deg(p.sub.i)d, the evaluation p.sub.i(x.sub.1/y.sub.1, . . . , x.sub.k/y.sub.k) is a fraction of the form:

[00013]$\frac{a_i}{b_i}=\frac{x_{i_1}{x}_{i_2}.Math.x_{i_{}}}{y_{i_1}{y}_{i_2}.Math.y_{i_{}}},\mathrm{for}\mathrm{some}d\mathrm{and}\left\{i_1,.Math.,i_{}\right\}.Math.\left\{1,.Math.,k\right\}.$

[0053] As each x.sub.i/y.sub.i.sub.M, we have |a.sub.i|, |b.sub.i|M.sup.d.

[0054] Since x/y=.sub.i=1.sup.lc.sub.i.Math.a.sub.i/b.sub.i, there are nonzero integers a and B such that:

[00014]$x=\left(c_1{a}_1\right)b_2{b}_3.Math.b_I+b_1\left(c_2{a}_2\right)b_3.Math.b_I+b_1{b}_2.Math.b_{I-1}\left(c_I{a}_I\right)$$\mathrm{and}y=b_1{b}_2.Math.b_I.$

[0055] It follows from |c.sub.i|t and the above bound on |a.sub.i|, |b.sub.i| that:

[00015]$.Math.x.Math.\underset{i=1}{\overset{I}{.Math.}}.Math.c_i.Math.{\left(M^d\right)}^{I}t.Math.M^{\mathrm{dI}}\mathrm{and}.Math.y.Math.M^{\mathrm{dI}}.$

[0056] The proof is completed by observing that |c.sub.i|1, for all i, implies It.

[0057] A sufficient condition for compatibility of PIE with polynomials in .sub.d,t as described above:

[00016]$\mathrm{PIE}.\mathrm{Decode}\left(g,p\left(\mathrm{PIE}.\mathrm{Encode}\left(g,m_0\right),.Math.,\mathrm{PIE}\mathrm{Enode}\left(g,m_k\right)\right)\mathrm{mod}g\right)={\mathrm{pm}}_0,.Math.,m_k)\mathrm{is}$$M{\left(\frac{N}{t}\right)}^{\frac{1}{\mathrm{dt}}},\mathrm{equivalently}d\frac{\log \left(N\right)-\log \left(t\right)}{t\log \left(M\right)}.$

[0058] Proof. Suppose M is chosen according to the above equation, and let p.sub.d,t be k-variate. According to the above descriptions, if m.Math..sub.M.sup.k and p(m)=x/y, then:

[00017]$.Math.x.Math.t.Math.M^{\mathrm{dt}}t.Math.{\left({\left(N/t\right)}^{\frac{1}{\mathrm{dt}}}\right)}^{\mathrm{dt}}=N,\mathrm{and}$$.Math.y.Math.M^{\mathrm{dt}}\left({\left(N/t\right)}^{\frac{1}{\mathrm{dt}}}\right)=N/tN.$

[0059] Clearly gcd(g, y)=1, since y is a factor of the product of the denominators in m. Thus p(m).sub.N, and the proof is completed.

3.2 Building Blocks

[0060] SSS primitives will be the algorithms/protocols Share, Recon, Add, ScalarMult, and Mult. Respectively, these create shares of a secret value s.sub.p, reconstruct a secret value given enough shares [s], compute the shares of the sum of two secrets without revealing either, compute shares of the product of a secret value and a known value without revealing the secret value, and compute shares of the product of two secrets without revealing either. Note that Recon, Add, and ScalarMult are all performed locally. By performed locally it is meant that the parties use their shares to execute the protocol without communicating with each other. For example, for Recon a party (or the dealer, if one exists) in possession of at least t shares reconstructs the secret using polynomial interpolation. sOutput([s]) is used to mean that each of a set of t1 parties sends their share of s to another party, which subsequently computes s=Recon([s]) and sends s to the other n1 parties. The Gennaro, Rabin and Rabin multiplication protocol is described below.

[00018]$\left[xy\right]\mathrm{Mult}\left(\left[x\right],\left[y\right]\right)$ [0061] 1. For i=1, . . . , n, the i.sup.th party P.sub.i computes .sub.i=[x].sub.i.Math.[y].sub.i; [0062] 2. for i=1, . . . , 2t1, P.sub.i computes [.sub.i]Share(.sub.i) (One could use any set of 2t1 parties for this step); [0063] 3. once each party P.sub.1, . . . , P.sub.n has received 2t1 shares, each party P.sub.i locally computes [xy].sub.i using Lagrange interpolation on the received shares; [0064] 4. output [xy].

[0065] Two additional protocols, RandInt and Inv, are required for the rational division protocol of the various embodiments. These protocols allow all parties to obtain shares of a random ring element and compute shares of the multiplicative inverse of a ring element, respectively.

TABLE-US-00001 [r] RandInt( ) 1. Each of a set of t parties select a uniformly random r.sub.i .sub.p, i = 1,..., t; 2. each of the t parties do [r.sub.i] Share(r.sub.i), and send the j.sup.th share to P.sub.j; 3. [r] Add([r.sub.1],..., [r.sub.t]); 4. return [r]. [x.sup.1] Inv([x]) 1. [r] RandInt( ); 2. [rx] Mult([r], [x]); 3. rx = Output([rx]); 4. abort and restart if rx = 0, otherwise continue; 5. each party locally computes (rx).sup.1 = x.sup.1r.sup.1 mod p; 6. each party does [x.sup.1] = ScalarMult(x.sup.1r.sup.1, [r]); 7. return [x.sup.1].

TABLE-US-00002 TABLE 1 Total communication complexity (measured in field elements) of SSS building block protocols. Protocol Rounds Comm. Complexity Share 1 n 1 Recon 0 0 Output 2 (n 1) + (t 1) Add 0 0 Mult 1 (2t 1)(n 1) ScalarMult 0 0 RandInt 1 t(n 1) Inv 4 t(3n 2) 1

[0066] Note that Share has communication complexity n (initial sharing of a secret), unless one party is sharing with the remaining parties, in which case it has communication complexity n1. The latter is the only one relevant to our protocols.

3.3 Rational Addition, Multiplication, Subtraction, and Division

[0067] Addition and multiplication are obtained by simply pairing the encoder encode with Add and Mult. To represent shares of the encoding of x/y.sub.N, we write [encode(x/y)]. We first present the four protocols, and then list their complexities in table 2. For all protocols, we use the field .sub.p, and

[00019]$\frac{x_o}{y_0},\frac{x_1}{y_1}{}_N$

such that:

[00020]$\frac{x_0}{y_0}\frac{x_1}{y_1},\frac{x_0}{y_0}.Math.\frac{x_1}{y_1},\frac{x_0}{y_0}\frac{x_1}{y_1}{}_N.$

Let t.sub.0=encode(x.sub.0/y.sub.0) and t.sub.1=encode(x.sub.1/y.sub.1).

[0068] Remark 1. We use the prefix Hg for our protocols because it is the chemical symbol for Mercury in the Periodic Table of Elements.

TABLE-US-00003 [encode(x.sub.0/y.sub.0 + x.sub.1/y.sub.1)] = HgAdd([encode(x.sub.0/y.sub.0)], [encode(x.sub.1/y.sub.1)]) 1. [t.sub.0 + t.sub.1] = Add([t.sub.0], [t.sub.1]); 2. return [t.sub.0 + t.sub.1] = [encode(x.sub.0/y.sub.0 + x.sub.1/y.sub.1)]. [encode(x.sub.0x.sub.1/y.sub.0y.sub.1)] = HgMult([encode(x.sub.0/y.sub.0)], [encode(x.sub.1/y.sub.1)]) 1. [t.sub.0t.sub.1] Mult([t.sub.0], [t.sub.1]); 2. return [t.sub.0t.sub.1] =[encode(x.sub.0x.sub.1/y.sub.0y.sub.1)]. [encode(x.sub.0/y.sub.0 x.sub.1/y.sub.1)] = HgSubtr([encode(x.sub.0/y.sub.0)], [encode(x.sub.1/y.sub.1)]) 1. All parties compute encode(1) = 1.sub.field .sub.p; 2. all parties compute [t.sub.1] = ScalarMult(1.sub.field, [t.sub.1]); 3. [t.sub.0 t.sub.1] = HgAdd([t.sub.0], [t.sub.1]); 4. return [t.sub.0 t.sub.1] =[encode(x.sub.0/y.sub.0 x.sub.1/y.sub.1)]. [encode(x.sub.0y.sub.1/y.sub.0x.sub.1)] = HgDiv([encode(x.sub.0/y.sub.0)], [encode(x.sub.1/y.sub.1)]) 1. [t.sub.1.sup.1] Inv([t.sub.1]); 2. [t.sub.0t.sub.1.sup.1] HgMult([t.sub.0], [t.sub.1.sup.1]); 3. return [t.sub.0t.sub.1.sup.1] =[encode(x.sub.0y.sub.1/y.sub.0x.sub.1)].

TABLE-US-00004 TABLE 2 Total communication complexity (measured in field elements) of rational addition, multiplication, subtraction, and division protocols. Mercury Protocol Rounds Comm. Complexity HgAdd 0 0 HgMult 1 (2t 1)(n 1) HgSubtr 0 0 HgDiv 5 t(5n 4) n

[0069] Remark 2. ScalarMult can be turned into HgScalarMult by simply encoding a public element .sub.N, and then computing [encode()s]=ScalarMult (encode(), [s]). Note that HgScalarMult also serves as a division by public divisor protocol-simply replace 0 by 1/.

4 WHICH RATIONAL NUMBERS CAN WE USE?

[0070] The various embodiments' protocols use the aforementioned Farey rationals. As mentioned in lemma 1 above, .sub.N is closed under additive inverses and under multiplicative inverses, but it is not closed under addition and multiplication. This means that a suitable subset of .sub.N must be chosen as the set of rational inputs. In particular, we must include fractions with small numerators and denominators so that adding/multiplying these fractions yields fractions that remain in .sub.N. Following closely the analysis of previously mentioned U.S. patent application Ser. No. 18/535,875, filed Dec. 11, 2023, entitled Methods and Systems for P-Adic Encoding and Decoding of Rational Data for FHE Systems, this set will be chosen as:

[00021]${X,Y}_{}:=\left\{x/y{N}_{}|X,Y\left[0,N\right],.Math.x.Math.X,0<yY\right\}.$

4.1 Compatibility with Fixed-Point Numbers

[0071] We now highlight the various embodiments' (partial) compatibility with fixed-point arithmetic. Further, many previous works designed their protocols with fixed-point arithmetic in mind. So, to facilitate comparison with prior art, we briefly discuss conditions under which .sub.N contains a set of fixed-point numbers.

[0072] Fixed-point numbers. These are rational numbers represented as a list of digits split by a radix point, and are defined by an integer (represented in a particular base b) in a given range along with a fixed scaling factor f. For example, we can represent decimal numbers with integral part in the range (, ) and up to f decimal places after the radix point as a.Math.10.sup.f=a/10.sup.f, a(, ). We will represent a set of fixed point numbers with a tuple of the form (b, , f), where b is the base, (, ) is range of the integer part, and up to f base-b digits are allowed after the radix point. The set of Farey rationals .sub.N contains the fixed-point numbers given by (b, , f) as long as:

[00022]$\begin{array}{cc}N\max \left\{b^{+f+1}-1,b^f-1\right\}.& \mathrm{Eq}.1\end{array}$

[0073] Of course, N should be sufficiently large to ensure that adding/multiplying the fixed-point numbers does not cause overflow. While .sub.N can be made to contain a set of fixed-point numbers with precision f, addition and multiplication of Farey rationals does not quite coincide with addition and multiplication of fixed-point numbers. This is because the fixed-point representation requires the precision to remain f after each operation (this necessitates a truncation protocol), while .sub.N allows the precision to increase until overflow occurs and the output of a computation is no longer correct. However, this disparity mostly vanishes if the system running the protocols only allows precision f, because the extra bits that would be removed via a truncation protocol are removed by the system itself.

[0074] We will use the fact that .sub.N contains certain fixed-point numbers in Section 6 where we compare embodiments' protocols with prior work.

4.2 Compatible Circuits

[0075] Again borrowing from previously mentioned U.S. patent application Ser. No. 18/535,875, filed Dec. 11, 2023, entitled Methods and Systems for P-Adic Encoding and Decoding of Rational Data for FHE Systems, for positive integers d, t we define (d, t)-permitted (arithmetic) circuits over to be those that compute a polynomial p[x.sub.1, x.sub.2, . . . ] such that: (i) p has .sub.1 norm at most t, (ii) total degree at most d, and (iii) coefficients with absolute value greater than or equal to 1. Note that nonzero polynomials p[x.sub.1, x.sub.2, . . . ] with p.sub.1 and deg (p)d satisfy (iii). Let C.sub.d,t be the set of (d, t)-permitted circuits, and .sub.d,t be the set of polynomials the circuits compute. The following lemma 2 is further described in U.S. patent application Ser. No. 18/535,875 at Proposition 7.

[0076] Lemma 2. Let C.sub.d,t with inputs from .sub.X,Y.Math..sub.N. If x/y is the output of C, then |x|tX.sup.dY.sup.d(t1) and |y|Y.sup.dt.

[0077] Proof. This is a slight modification of the proof of U.S. patent application Ser. No. 18/535,875 at Proposition 7. The bounds given in lemma 2 allow us to determine the (d, t)-permitted circuits with output fractions in .sub.N given inputs from .sub.X,Y. Intuitively, the bound on x is larger than the bound on y because the numerator grows faster than the denominator when fractions are summed versus when they are multiplied. For example, (a/b)(c/d)=(ad/bc)/bd versus (a/b)(c/d)=ac/bd. Some space is wasted if, for example, one chooses X=Y, because then the numerator bound becomes the limiting factor for ensuring the output of a permitted circuit remains in .sub.N. For fixed d and t, this can be avoided by judiciously choosing X to be smaller than Y. In particular, X and Y should satisfy log.sub.2(t)/d+log.sub.2(X)=log.sub.2(Y). Of course this is not possible for many applications, so typically the numerator bound will remain the limiting factor for depth of compatible circuits.

[0078] For example, suppose p is a prime such that N={square root over ((p1)/2)} is 1024 bits, and let X=2.sup.32, Y=2.sup.14. According to Lemma 2, we can only evaluate circuits in C.sup.d,t with inputs in .sub.X,Y if t(2.sup.32).sup.d(2.sup.14).sup.d(t1)2.sup.1024 or, equivalently, if log.sub.2(t)+18d+14dt1024. Notice how the numerator bound from Lemma 2 is the only one needed to determine d and t. The following table shows some choices for d and t.

TABLE-US-00005 TABLE 3 Possible values of d (total degree of polynomial computed by permitted circuit) and t ( .sub.1 norm of polynomial computed by permitted circuit) for fractions with numerators bounded in absolute value by 2.sup.32 and denominators bounded by 2.sup.14. |num| 2.sup.32, denom = 2.sup.14 d 1 2 3 4 5 10 t 71 35 22 16 13 6

[0079] This is not particularly useful, as many applications require thousands or even millions of additions to be performed on shared values. However, for many applications one is likely to work with decimal numbers with a small number of significant digits; e.g., fractions with denominators a power of 10 between 7 bits and 17 bits. In such cases, we can significantly improve the bounds on d and t. In general, if the fractional data all have the same denominator, then Lemma 2 yields the following corollary.

[0080] Corollary 1. Let C.sub.d,t with inputs from .sub.N whose denominators are all some power of integer base b>0, say B=b.sup.e, and whose numerators are bounded in absolute value by X. If x/y is the output of C, then |x|t(XB).sup.d and yB.sup.d.

[0081] Rehashing the above example (X=2.sup.32 and N 1024 bits) with B=2.sup.14 we get t(2.sup.322.sup.14).sup.d2.sup.1024.Math.log.sub.2(t)102446d and (2.sup.14).sup.d2.sup.1024.Math.d73. The bound on d is in fact even smaller: since the .sub.1 norm of a polynomial in .sub.d,t is at least 1, log.sub.2(t)0.Math.102446d0.Math.22d. This yields the following table.

TABLE-US-00006 TABLE 4 Possible values of d (total degree of polynomial computed by permitted circuit) and t ( .sub.1 norm of polynomial computed by permitted circuit) for fractions with numerators bounded in absolute value by 2.sup.32 and denominators bounded by 2.sup.14. |num| 2.sup.32, denom = 2.sup.14 d 1 2 10 15 20 22 t 2.sup.978 2.sup.932 2.sup.564 2.sup.334 2.sup.104 2.sup.12

[0082] So if we restrict inputs to have the same denominators, we can perform an enormous number of additions and a reasonable number of multiplications before the output lands outside of .sub.N. We can do even better though.

[0083] Degree-constant circuits. Each gate of an arithmetic circuit computes a polynomial over (some of) the inputs. We define a degree-constant (arithmetic) circuit to be one in which every gate computes a polynomial whose monomial summands all have the same degree; e.g., a dot product. The goal of introducing these circuits is to ensure that whenever two fractions are summed, they already have a common denominator.

[0084] Corollary 2. Let C.sub.d,t be degree-constant with inputs from .sub.N whose denominators are all B=b.sup.e and whose numerators are bounded in absolute value by X>0. If x/y is the output of C, then |x|tX.sup.d and yB.sup.d.

[0085] Proof. This follows easily from the fact that whenever two terms are added during the evaluation of a degree-constant circuit, they already have a common denominator which is a power of B.

[0086] Again, using a 1024 bit N, X=2.sup.32, and B=2.sup.14, we get the inequalities log.sub.2(t)102432d and d32, yielding the following table.

TABLE-US-00007 TABLE 5 Possible values of d (total degree of polynomial computed by a permitted circuit) and t ( .sub.1 norm of polynomial computed by permitted circuit) for degree- constant C .sub.d, t taking inputs from F.sub.N with numerators bounded in absolute value by 2.sup.32 and denominators all equal to 2.sup.14. |num| 2.sup.32, denom = 2.sup.14 d 1 2 10 15 25 31 t 2.sup.992 2.sup.960 2.sup.704 2.sup.544 2.sup.384 2.sup.32

[0087] Incorporating division. Once we allow divisions, the bounds given in Corollary 1 and Corollary 2 no longer apply, since the numerator of the divisor becomes a factor of denominator of the quotient. This means we should perform any necessary divisions as late as possible relative to other operations.

5 OPTIMIZATIONS

[0088] The complexity of HgMult and HgDiv can be reduced by executing parts of the protocols asynchronously in an offline phase. This allows certain parts of the protocols to be executed before the desired computation, thereby reducing the online complexity. The complexity of the offline phase depends on chosen primitives, existence of a trusted dealer, etc. Henceforth, we emphasize the online round complexity and the online communication complexity.

[0089] We utilize two ubiquitous tools for optimization: Beaver triples (introduced in [3]) for more efficient multiplication, and Pseudo-Random Secret Sharing (PRSS, [11]) to generate random field elements sans interaction.

[0090] In PRSS, the parties agree on a pseudo-random function (PRF) .Math.(.Math.) and a common input a. They then use pre-distributed keys r.sub.A (one for each set A of nt parties) to locally compute shares of a random field element s using Replicated Secret Sharing (see for details). The use of PRSS reduces the online round and communication complexity of RandInt from 1 and t(n1) to 0 and 0, respectively. Further, we assume that the PRF, common input, and keys are agreed upon and distributed during a set-up phase, whence using PRSS makes the offline round and communication complexity of RandInt both 0.

[0091] Beaver triples are 3-tuples of shares ([a], [b], [c]) satisfying ab=c, and can be generated asynchronously in the offline phase using PRSS and Mult. These triples can be used to multiply secrets without interaction. In particular, shares [xy] can be obtained from [x] and [y] using only Add, ScalarMult, Recon, Output, and one Beaver triple ([a], [b], [c]):

[00023]$\left[xy\right]=\left(x+a\right)\left[y\right]-\left(y+b\right)\left[a\right]+\left[c\right].$

[0092] Used triples must be discarded, else information is leaked. This means that a sufficiently-large reservoir of Beaver triples should be maintained to allow the desired functions to be computed.

[0093] These optimizations reduce the online complexities of HgMult and HgDiv, and leave the complexities of HgSubtr and HgAdd the same. Table 6 below summarizes the improvements.

TABLE-US-00008 TABLE 6 Optimized round and communication complexities for our protocols. Note that the nonzero offline communication complexities come from Mult during Beaver triple generation. Online Offline Protocol Rounds Rounds Online Comm. Offline Comm. HgAdd 0 0 0 0 HgMult 0 0 0 (2t 1)(n 1) HgSubtr 0 0 0 0 HgDiv 2 2 (t 1) + (n 1) 2(2t 1)(n 1)

[0094] We use the complexities listed in table 6 for the comparisons in section 6. Henceforth, rounds will mean online rounds+offline rounds, and total communication will mean online communication+offline communication.

6 COMPARISON WITH PRIOR WORK

[0095] Catrina and Saxena introduced semi-honest secure protocols for fixed-point multiplication and divisiontheir division is based on (the iterative) Goldschmidt's method. A variant of their protocol is used by MP-SPDZ for fixed-point division. Catrina subsequently improved the round and communication complexities. To measure the complexities of their protocols, they use the set of fixed-point numbers given by (2, 2f, f); i.e., the set of rationals a.Math.2.sup.f with a[2.sup.2f, 2.sup.2f). Their fixed-point encoding technique requires a field .sub.q with q>2.sup.2f+, a statistical security parameter. For our protocols, we use the same field .sub.q, whence our set of rationals is .sub.N with N=N(q); specifically log.sub.2(N)f+/2. Table 7 shows that for reasonable values of n and t (e.g., n=3, t=2), our protocols far outperform those of Catrina's subsequent improvements.

TABLE-US-00009 TABLE 7 Complexity comparison between our work and that of [7] Both the online and offline communication complexity are measured in elements of g sent among all parties throughout a protocol. n and t are the number of parties and the threshold, resp., is the number of iterations of Goldschmidt's method, and f is the fixed-point precision. Protocol Rounds Online Comm. Offline Comm. Mercury Multiplication 0 0 (2t 1)(n 1) Division 3 (t 1) + 2(2t 1)(n 1) (n 1) [7] Multiplication 1 1 f Division 9 + 10f + 2 16f + 4f

[0096] For example, the authors suggest f=32 and =5, which results in a 14 round division with online communication complexity 320 field elements. Taking n=3 and t=2, our division requires 2 rounds, and has online communication complexity 3 field elements. There is, however, a bit more subtlety to this comparison. As mentioned in Section 4.1, operations on fixed-point numbers require a truncation, and the protocols of Catrina et al. use truncation. Consequently, there is no limit to how many times they can multiply/divide two fixed-point numbers. However, there is a number of multiplications, say, that will render their outputs of little use because so many bits have been truncated. Our limitation, on the other hand, is overflow: computations over .sub.N are only meaningful if all intermediate outputs and the final output are in .sub.N. We can address this in two ways: (i) only take inputs from the subset .sub.X,Y.Math..sub.N defined in section 4, for X, Y sufficiently smaller than N, or (ii) use a larger field than Catrina. As long as we don't choose too large a field, (ii) will preserve our complexity advantage.

[0097] Another interesting solution, albeit only for integer division, was proposed by Veugen and Abspoel. They propose three division variations: public divisor, private divisor (only one party knows the divisor), and secret divisor (hidden from all parties). Their protocols are implemented using MP-SPDZ with three parties, and runtimes along with communication complexities (in MB) for dividing a k-bit integer by a k/2-bit integer are provided. Even though our division protocol uses rationals in general, comparison makes sense because .sub.N contains the integers [N, N] (see lemma 1). For comparison, we use n=3 and t=2, and use the smallest prime field .sub.p allowed by Veugen and Abspoel:

[00024]${\log }_2\left(p\right)4\max \left\{{\log }_2\left(\mathrm{dividend}\right),{\log }_2\left(\mathrm{divisor}\right)\right\}+40$

[0098] For example, this means that for a 64 bit dividend and 32 bit divisor, we have log.sub.2(p)=296 and N=N(p)148 bits.

[0099] The reader should take the comparison in table 8 with a grain of salt since our numbers were estimated and not obtained from implementation.

TABLE-US-00010 TABLE 8 Total communication complexity in megabytes (MB) of our division protocol (applied to integers) vs. the (secret divisor) integer division protocol of Veugen and Abspoel. The communication complexities for our work were estimated using table 7. dividend bits 8 16 32 64 divisor bits 4 8 16 32 Mercury 0.001 MB 0.0015 MB 0.0024 MB 0.0042 MB [20] (semi-honest 8.6 MB 32.6 MB 121.0 MB 492.7 MB security)

[0100] The last comparison we shall show is against Pika. Pika uses Function Secret Sharing to construct a three-party protocol (one party is used only to generate correlated randomness) for computing functions such as reciprocal, sigmoid, and square root. The protocol Pika takes as inputs (binary) fixed-point numbers x with precision f, such that x.Math.2.sup.f(2.sup.k1, 2.sup.k1], and creates shares in the ring , where 2 k. For comparison, we choose N=N(p)=2.sup.k1 (meaning we share secrets over .sub.p with p2.sup.2k). This guarantees that .sub.N contains the fixed-point numbers used by Pika regardless of the chosen precision f. As with the preceding comparisons, we again take n=3 and t=2.

[0101] Using the same parameter values for (semi-honest secure) Pika as the author, we found that that total communication complexity for securely computing the reciprocal with k=16 and =32 was 8524 bits over three rounds (one offline). In contrast, we can compute the reciprocal of an element of .sub.2.sub.15 in three rounds (one offline) with communication complexity 9 log.sub.2(p)18 k=288 bits.

7 CONCLUSIONS

[0102] Conclusion. This work uses Shamir Secret Sharing with a minority of semi-honest adversaries, but Mercury is flexible in the sense that it can be easily realized over other primitives with better security assumptions; e.g. additive secret sharing la MP-SPDZ along with a majority of malicious adversaries. Mercury provides an efficient low round and communication complexity solution to exact computation over rational numbers using MPC. A cost of exactness, though, is that our protocols are not intrinsically compatible with fixed-point arithmetic. Instead of truncating after every operation to not exceed the chosen fixed-point precision, we allow the precision to grow until overflow occurs. This means that we may need to work over a larger field .sub.p than prior art, but our communication and round complexity are sufficiently low as to make using a slightly larger field not problematic.

Hardware Implementation for an Embodiment (FIG. 1)

[0103] 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 110 to 3.sup.rd data server computing device 106. A 2.sup.nd data server computing device 104 is also connected over an electronic network/bus connection 112 to the 3.sup.rd data server computing device 106. The third data server computing device 106 is further connected over an electronic network/bus connection 114 to the 4.sup.th data server computing device 108.

[0104] In the embodiment shown in FIG. 1, the 1.sup.st data server computing device 102 acts as the source of the 1.sup.st encoded integer 110 and the 1.sup.st data server computing device 102 sends the 1.sup.st encoded integer 110 over the network/bus connection 110 to the 3.sup.rd data server computing device 106. The 2.sup.nd data server computing device 104 acts as the source of the 2.sup.nd encoded integer 112 and the 2.sup.nd data server computing device 104 sends the 2.sup.nd encoded integer 112 over the network/bus connection 112 to the 3.sup.rd data server computing device 106.

[0105] The 3.sup.rd data server computing device 106, in compliance with the MPC system 116, performs an arithmetic operation (addition, subtraction, multiplication, and/or division) with the 1.sup.st encoded integer 110 and the 2.sup.nd encoded integer 112. The 3.sup.rd data server computing device 106 then sends the result encoded integer 114 over the network/bus connection 114 to the 4.sup.th data server computing device 108. The 4.sup.th data server computing device 108 then decodes the result encoded integer 114.

[0106] The 1.sup.st encoded integer 110 and the 2.sup.nd encoded integer 112 starts at the source computing device as one or more rational numbers (e.g., of the form x/y). An embodiment at the 1.sup.st data server computing device 102 and the 2.sup.nd data server computing device 104 encodes the rational numbers into corresponding 1.sup.st encoded integer 110 and the 2.sup.nd encoded integer 112, respectively as a function of p-adic arithmetic performed on the rational numbers.

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

[0108] Further, as shown in FIG. 1, the data server computing devices 102-108 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-108. Additionally, data server computing devices 102-108 may actually be the same physical computing device communicating over an internal bus connection with itself.

[0109] Various embodiments may implement the network/bus communications channel 110-114 using any communications channel 110-114 capable of transferring electronic data between the data server computing devices 102-108. For instance, the network/bus communication connection 110-114 may be an Internet connection routed over one or more different communications channels. Likewise, the network/bus communication connection 110-114 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 110-114 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.

[0110] The T various embodiments may provide the control and management functions detailed herein via an application operating on the data server computing devices 102-108. The data server computing devices 102-108 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-108 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)

[0111] FIG. 2 is a flow chart 200 of operations for an embodiment. At process 210, the 1.sup.st data server computing device 202 encodes a 1.sup.st rational number (e.g., x.sub.0/y.sub.0) into a 1.sup.st corresponding encoded integer using p-adic arithmetic that provides the inverse and homomorphic preserving aspects of the p-adic generated integers. At process 212, the 1.sup.st data server computing device 202 sends 1.sup.st encoded integer to the 3.sup.rd data server computing device 206. At process 214, the 2.sup.nd data server computing device 204 encodes a 2.sup.nd rational number (e.g., x.sub.1/y.sub.1) into a 2.sup.nd corresponding encoded integer using p-adic arithmetic that provides the inverse and homomorphic preserving aspects of the p-adic generated integers. At process 216, the 1.sup.st data server computing device 202 sends 1.sup.st encoded integer to the 3.sup.rd data server computing device 206. At process 218, the 3.sup.rd data server computing device 205, in accord with the MPC system, computes an arithmetic function with the 1.sup.st encoded integer and 2.sup.nd encoded integer in to obtain at least one result encoded integer. The potential arithmetic functions are one or more of addition, subtraction, multiplication, and division. At process 220, the 3.sup.rd data server computing device 206 sends the result encoded integer to the 4.sup.th data server computing device 208. At process 222, the 4.sup.th data server computing device decodes the result encoded integer into a corresponding result rational number (e.g., x.sub.r/y.sub.r) using inverse p-adic arithmetic. The MPC system running on the data server computing devices 202-208 should be of the same type.

[0112] 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 the 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.

[0113] 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.