RANDOM NOISE GENERATION FOR MULTIPARTY COMPUTATION

Abstract

Example computer-implemented methods and systems for secure random noise generation are disclosed. One example method includes generating, by a first party, n random first bits and n -bit first strings. The first party generates, based on the n -bit first strings and the n random first bits, n pairs of -bit input messages. The first party receives n pairs of -bit second strings. The first party performs n 1-out-of-2 random oblivious transfers (ROTs) of the n pairs of -bit input messages from the first party to a second party. The first party generates, based on the n -bit first strings, a first random number. The first party performs, based on the first random number, secure multiparty computation (MPC) that involves the first party and the second party.

Claims

1. A computer-implemented method for generating random noise in response to a secure multiparty computation request comprising: generating, by a first party, a quantity of n random first bits; generating, by the first party, a quantity of n -bit first strings, wherein each of the quantity of n -bit first strings is randomly sampled from a set of -bit strings, and the set of -bit strings comprises distinct -bit strings; generating, by the first party and based on the quantity of n -bit first strings and the quantity of n random first bits, a quantity of n pairs of -bit input messages; receiving, by the first party, a quantity of n pairs of -bit second strings; performing, by the first party and in communication with a second party, a quantity of n 1-out-of-2 random oblivious transfers (ROTs) of the quantity of n pairs of -bit input messages from the first party to the second party; generating, by the first party and based on the quantity of n -bit first strings, a first random number, which corresponds to a first share of a random noise value; and performing, by the first party and based on the first random number, secure multiparty computation (MPC) that involves the first party and the second party.

2. The computer-implemented method of claim 1, wherein generating the quantity of n pairs of -bit random input messages comprises: generating the quantity of n pairs of -bit random input messages using s.sub.1,j=(r.sub.j+a.sub.1,j)modulo and s.sub.2,j=(r.sub.j+1a.sub.1,j)modulo , wherein (s.sub.1,j, s.sub.2,j) is a j-th pair of the n pairs of -bit random input messages, r.sub.j is a j-th -bit first string of the n -bit first strings, a.sub.1,j is a j-th random first bit of the n random first bits, and j=1, . . . , n.

3. The computer-implemented method of claim 1, wherein a value of each of the n random first bits is (1) 1 with a probability of 0.5 and (2) 0 with a probability of 0.5.

4. The computer-implemented method of claim 1, wherein generating the first random number comprises generating the first random number using y.sub.1=.sub.j=1.sup.nr.sub.j modulo , wherein y.sub.1 is the first random number and r.sub.j is a j-th -bit first string of the n -bit first strings.

5. The computer-implemented method of claim 1, wherein the first random number follows a binomial distribution with parameters n and p, and wherein p=0.5.

6. The computer-implemented method of claim 1, wherein the first party is a social media entity and the second party is an entity engaging in the secure MPC with the social media entity.

7. The computer-implemented method of claim 1, wherein performing the quantity of n 1-out-of-2 ROTs comprises: generating, by the first party, a quantity of n pairs of -bit third strings according to $T={\left\{\left(t_{1,j},t_{2,j}\right)\right\}}_{j\left\{1,.Math.,n\right\}}={\left\{\left(m_{1,j{s}_{1,j}},m_{2,j{s}_{2,j}}\right)\right\}}_{j\left\{1,.Math.,n\right\}},$ wherein T is the n pairs of -bit third strings, (m.sub.1,j, m.sub.2,j) is a j-th pair of the n pairs of -bit second strings, (s.sub.1,j, s.sub.2,j) is a j-th pair of the n pairs of -bit input messages, and j=1, . . . , n; and sending, by the first party and to the second party, the n pairs of -bit fourth strings.

8. The computer-implemented method of claim 1, wherein performing the secure MPC comprises adding, by the first party, noise corresponding to the first random number to results of the secure MPC.

9. A computer-implemented system comprising: one or more computers; and one or more computer memory devices interoperably coupled with the one or more computers and having tangible, non-transitory, machine-readable media storing one or more instructions that, when executed by the one or more computers, cause the computer-implemented system to perform one or more operations comprising: generating, by a first party, a quantity of n random first bits; generating, by the first party, a quantity of n -bit first strings, wherein each of the quantity of n -bit first strings is randomly sampled from a set of -bit strings, and the set of -bit strings comprises distinct -bit strings; generating, by the first party and based on the quantity of n -bit first strings and the quantity of n random first bits, a quantity of n pairs of -bit input messages; receiving, by the first party, a quantity of n pairs of -bit second strings; receiving, by a second party, a quantity of n selection bits and a quantity of n -bit third strings; performing, by the first party and the second party, a quantity of n 1-out-of-2 random oblivious transfers (ROTs) of the quantity of n pairs of -bit input messages from the first party to the second party; generating, by the first party and based on the quantity of n -bit first strings, a first random number, which corresponds to a first share of a random noise value; generating, by the second party and based on a quantity of n 1-out-of-2 random oblivious transfer (ROT) outputs of the second party, a second random number, which corresponds to a second share of the random noise value; and performing, by the first party and the second party and based on the first random number and the second random number, secure multiparty computation (MPC) that involves the first party and the second party.

10. The computer-implemented system of claim 9, wherein generating the quantity of n pairs of -bit random input messages comprises: generating the quantity of n pairs of -bit random input messages using s.sub.1,j=(r.sub.j+a.sub.1,j)modulo and s.sub.2,j=(r.sub.j+1a.sub.1,j)modulo wherein (s.sub.1,j, s.sub.2,j) is a j-th pair of the n pairs of -bit random input messages, r.sub.j is a j-th -bit first string of the n -bit first strings, a.sub.1,j is a j-th random first bit of the n random first bits, and j=1, . . . , n.

11. The computer-implemented system of claim 9, wherein a value of each of the n random first bits is (1) 1 with a probability of 0.5 and (2) 0 with a probability of 0.5.

12. The computer-implemented system of claim 9, wherein for a j-th 1-out-of-2 random oblivious transfer (ROT), x.sub.j=s.sub.1,j when a.sub.2,j=0, and x.sub.j=s.sub.2,j when a.sub.2,j=1, wherein x.sub.j is a j-th output of the n 1-out-of-2 ROT outputs of the second party, (s.sub.1,j, s.sub.2,j) is a j-th pair of the n pairs of -bit random input messages, a.sub.2,j is a j-th random second bit of the n random selection bits, and j=1, . . . , n.

13. The computer-implemented system of claim 9, wherein generating the first random number comprises generating the first random number using y.sub.1=.sub.j=1.sup.nr.sub.j modulo , wherein y.sub.1 is the first random number and r.sub.j is a j-th -bit first string of the n -bit first strings.

14. The computer-implemented system of claim 9, wherein generating the second random number y.sub.2 comprises generating y.sub.2 using y.sub.2=.sub.j=1.sup.nx.sub.j modulo , wherein y.sub.2 is the second random number and x.sub.j is a j-th output of the n 1-out-of-2 random oblivious transfer (ROT) outputs of the second party.

15. The computer-implemented system of claim 9, wherein the first random number and the second random number follow a binomial distribution with parameters n and p, and wherein p=0.5.

16. The computer-implemented system of claim 9, wherein the first party is a social media entity and the second party is an entity engaging in the secure MPC with the social media entity.

17. The computer-implemented system of claim 9, wherein performing the quantity of n 1-out-of-2 random oblivious transfers (ROTs) comprises generating the quantity of n 1-out-of-2 ROT outputs of the second party {x.sub.j}, and generating the quantity of n 1-out-of-2 ROT outputs of the second party {x.sub.j} comprises: generating, by the first party, a quantity of n pairs of -bit third strings according to $T={\left\{\left(t_{1,j},t_{2,j}\right)\right\}}_{j\left\{1,.Math.,n\right\}}={\left\{\left(m_{1,j{s}_{1,j}},m_{2,j{s}_{2,j}}\right)\right\}}_{j\left\{1,.Math.,n\right\}},$ wherein T is the n pairs of -bit third strings, (m.sub.1,j, m.sub.2,j) is a j-th pair of the n pairs of -bit second strings, (s.sub.1,j, s.sub.2,j) is a j-th pair of the n pairs of -bit input messages, and j=1, . . . , n; sending, by the first party and to the second party, the n pairs of -bit fourth strings; and generating, by the second party, the quantity of n 1-out-of-2 ROT outputs of the second party {x.sub.j} according to x=m.sub.1,jt.sub.1,j when a.sub.2,j=0, and x.sub.j=m.sub.2,jt.sub.2,j, when a.sub.2,j=1, wherein j=1, . . . , n, and a.sub.2,j is a j-th selection bit of the n selection bits received by the second party.

18. The computer-implemented system of claim 9, wherein performing the secure MPC comprises adding, by the first party, noise corresponding to the first random number to results of the secure MPC.

19. A non-transitory computer-readable medium storing one or more instructions executable by a computer system to perform operations comprising: generating, by a first party, a quantity of n random first bits; generating, by the first party, a quantity of n -bit first strings, wherein each of the quantity of n -bit first strings is randomly sampled from a set of -bit strings, and the set of -bit strings comprises 2.sup. distinct -bit strings; generating, by the first party and based on the quantity of n -bit first strings and the quantity of n random first bits, a quantity of n pairs of -bit input messages; receiving, by the first party, a quantity of n pairs of -bit second strings; performing, by the first party and in communication with a second party, a quantity of n 1-out-of-2 random oblivious transfers (ROTs) of the quantity of n pairs of -bit input messages from the first party to the second party; generating, by the first party and based on the quantity of n -bit first strings, a first random number, which corresponds to a first share of a random noise value; and performing, by the first party and based on the first random number, secure multiparty computation (MPC) that involves the first party and the second party.

20. The non-transitory computer-readable medium of claim 19, wherein generating the quantity of n pairs of -bit random input messages comprises: generating the quantity of n pairs of -bit random input messages using s.sub.1,j=(r.sub.j+a.sub.1,j)modulo and s.sub.2,j=(r.sub.j+1a.sub.1,j)modulo , wherein (s.sub.1,j, s.sub.2,j) is a j-th pair of the n pairs of -bit random input messages, r.sub.j is a j-th -bit first string of the n -bit first strings, a.sub.1,j is a j-th random first bit of the n random first bits, and j=1, . . . , n.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0010] FIG. 1 illustrates an example process of generating random numbers for two parties in secure multiparty computation.

[0011] FIG. 2 illustrates an example method of generating secure random numbers for two parties.

[0012] FIG. 3 illustrates an example process of secure random number generation for two parties.

[0013] FIG. 4 is a schematic illustration of example computer systems that can be used to execute implementations of the present disclosure.

[0014] Like reference numbers and designations in the various drawings indicate like elements.

DETAILED DESCRIPTION

[0015] MPC techniques allow parties to jointly evaluate a function with their private inputs without sharing those private inputs with the other parties. There are a number of different MPC techniques that can be used to provide the MPC. Typically, secret sharing is used to provide data privacy. As a simple illustrative example, assume a number of parties working for a company wish to find their average salary without revealing their own salary to any other party. The private data of each participant can be a number representing their salary. Each participant divides their salary into shares, referred to as secret shares. The shares can be random numbers with the constraint being that their sum is equal to the private data, i.e., their salary in this example. For example, if party 1 has an hourly salary of $10 per hour, the shares can be 1, 3, 4, 2, which sum to 10.

[0016] If there are four participants, each participant can divide their salary into four shares. The shares are then divided among the parties. Thus, each party has four shares: one of their shares and one share from each other party. By themselves the shares are meaningless random numbers. Each party then sums the values of their shares and reveals that sum to the other participants. Each party then has four sums, which also provides the sum of all the private data values, in other words, the sum of all the salaries. Knowing the total sum of salaries, the parties can then compute a particular function to operate on the salary information, e.g., divide by four and get the average salary, without the private salary information being revealed for any one party.

[0017] While MPC works to provide protection of private data used as input to the functions of the MPC, for some functions it is possible to infer some private data from the generated results based on the nature of the functions being computed. For example, large data sets can include information about many different users. Even with anonymization (e.g., removing names), it is possible to combine outputs generated from the seemingly anonymous data to identify individualized information. Differential privacy is a technique to reduce the probability of determining individualized private information from the MPC results without changing the outcome of the function being computed. Typically, this is done by introducing noise to individual data based on some distribution so that there is plausible deniability as to its accuracy, so that no individualized determinations can be made. However, because the distribution of the noise is known, it can be compensated for in the aggregate so that a correct final output is generated.

[0018] In a more general example, two entities may wish to compute functions based on large datasets of information. For example, one entity may be a social media entity with a large dataset of information relating to social media content or users. The second entity may be a content sponsor for the social media entity, an academic institution, or other entity. The social media entity needs to maintain the privacy of their dataset such that individualized information, e.g., about a particular user, cannot be obtained by the second entity. Using MPC, and in particular with differential privacy, allows the two entities to perform data analysis as part of evaluating various functions without providing any access to the private data outside of the respective entities and ensuring within the specified degree of differential privacy that the MPC outputs cannot identify any individualized information.

[0019] FIG. 1 illustrates an example process 100 of generating random numbers representing respective shares of a random noise value for two parties in secure multiparty computation. For convenience, process 100 will be described as being performed jointly by a computer system of a first party and a computer system of a second party. Each of the two parties is a participant in the secure multiparty computation, and the two parties jointly compute a function over the two parties' inputs while keeping those inputs private. In some implementations, each party represents a distinct entity or enterprise. The two parties may each include one or more computers, servers, or other computing devices. For example, a first party may correspond to one or more computing devices associated with a first entity and the second party may correspond to one or more computing devices associated with a second entity. An example computer system associated with the first party or the second party is shown in FIG. 4.

[0020] In some implementations, process 100 implements a two-party protocol that is secure against semi-honest adversaries in multiparty computation.

[0021] At 102, a computer system of a first party, for example, a sender of n 1-out-of-2 random oblivious transfers (ROTs), generates the first party's n pairs of input messages {(s.sub.1,j, s.sub.2,j)} for the n 1-out-of-2 ROTs, where j=1, . . . , n. In some implementations, each of the n 1-out-of-2 ROTs enables a second party, for example, a receiver of the n 1-out-of-2 ROTs, to receive, according to a second party's selection bit unknown to the first party, one message out of a corresponding pair of the first party's n pairs of input messages {(s.sub.1,j, s.sub.2,j)}. The first party (i.e., the sender) does not know which message in the corresponding pair of the first party's n pairs of input messages {(s.sub.1,j, s.sub.2,j)} is received by the second party (i.e., the receiver). The second party does not know the other message in the corresponding pair of the first party's n pairs of input messages {(s.sub.1,j, s.sub.2,j)} that the second party does not receive. Furthermore, the first party receives pairs of random strings, with one string in each pair of the random strings also received by the second party, depending on a second party's selection bit unknown to the first party. These random strings received by the two parties are used in the n 1-out-of-2 ROTs to enable the second party to receive one message out of a corresponding pair of the first party's n pairs of input messages {(s.sub.1,j, s.sub.2,j)}, while reducing the number of communication rounds in the n 1-out-of-2 random ROTs, when compared to the number of communication rounds in n 1-out-of-2 oblivious transfers (OTs).

[0022] In some implementations, to generate the first party's input messages, the computer system of the first party generates n random first bits {a.sub.1,j} according to a binomial distribution, where j=1, . . . , n, and a value of each of the n random first bits {a.sub.1,j} is 1 with a probability of 0.5, and 0 with a probability of 0.5. In some cases, generating an n-bit random number allows for an efficient creation of a number that simulates n-Bernoulli trials with probably 0.5. Each bit is selected with a 0.5 probability of being 1 or 0. A share of random noise can then be generated from the n-bit random number. The share of random noise can in turn provide differential privacy of MPC outputs. An example value of n is 64.

[0023] In some implementations, the computer system of the first party also generates n -bit first strings {r.sub.j}, where j=1, . . . , n, and each of the n -bit first strings {r.sub.j} is randomly sampled from a set of -bit strings , and the set of -bit strings forms the space of -bit strings and includes distinct -bit strings. For example, when =2, there are four distinct 2-bit strings, i.e., Z.sub.2.sub.2={00, 01, 10, 11}.

[0024] In some implementations, the computer system of the first party generates the first party's n pairs of input messages {(s.sub.1,j,s.sub.2,j)} for the n 1-out-of-2 ROTs based on the first party generated n random first bits {a.sub.1,j} and the n -bit first strings {r.sub.j}, using Equations 1 and 2 below.

[00001]$\begin{array}{cc}{s}_{1,j}=\left(-r_j+a_{1,j}\right)\mathrm{modulo}{2}^{}& \left(1\right)\end{array}$$\begin{array}{cc}{s}_{2,j}=\left(-r_j+1-a_{1,j}\right)\mathrm{modulo}{2}^{}& \left(2\right)\end{array}$

The modulo operation returns the remainder of a division, after one number is divided by another. For example, a modulo b is the remainder of the division of a by b, where a is the dividend and b is the divisor.

[0025] In some implementations, the computer system of the first party (e.g., the sender of the n 1-out-of-2 ROTs) interacts with a computer system of a second party (e.g., the receiver of the n 1-out-of-2 ROTs) to perform the n 1-out-of-2 ROTs of the first party's n pairs of input messages {(s.sub.1,j, s.sub.2,j)} from the first party to the second party, as described in 104 below. In some cases, the first party and the second party can be semi-honest adversaries in the n 1-out-of-2 ROTs. Two semi-honest adversaries can follow the MPC protocol honestly, but may try to glean as much information from the information they receive from other parties, including through collusion with other parties.

[0026] At 104, the computer system of the second party, while working with the computer system of the first party to perform the n 1-out-of-2 ROTs, generates outputs {x.sub.j} of the second party for the n 1-out-of-2 ROTs, where j=1, . . . , n.

[0027] In some implementations, to jointly perform the n 1-out-of-2 ROTs with the first party in order to generate the outputs of the second party for the n 1-out-of-2 ROTs, the second party receives n selection bits {a.sub.2,j}, where j=1, . . . , n. The n selection bits {a.sub.2,j} can be used by the second party for the n 1-out-of-2 ROTs respectively. Furthermore, the first party receives n pairs of -bit second strings {(m.sub.1,j, m.sub.2,j)}, where j=1, . . . , n. The second party receives n -bit third strings {m.sub.j}, where j=1, . . . , n. When a.sub.2,j=0, m.sub.j=m.sub.1,j; and when a.sub.2,j=1, m=m.sub.2,j; where j=1, . . . , n.

[0028] In some implementations, the first party computes T={(t.sub.1,j, t.sub.2,j)}.sub.j{1, . . . ,n}={(m.sub.1,js.sub.1,j, m.sub.2,js.sub.2,j)}.sub.j{1, . . . ,n}, and then sends T to the second party. The logical operation represents a bit-wise exclusive disjunction operation, also referred to as an exclusive OR operation, XOR. For example, xy is true when the values of x and y are different and false when the values of x and y are the same.

[0029] In some implementations, the second party computes x.sub.j=m.sub.1,jt.sub.1,j, when a.sub.2,j=0; and x.sub.j=m.sub.2,j t.sub.2,j, when a.sub.2,j=1; where j=1, . . . , n.

[0030] At 106, the computer system of the first party generates a first random number y.sub.1 by locally summing up all the elements in {r.sub.j}.sub.j{1, . . . ,n} using Equation 3 below. In some cases, y.sub.1 can be denoted [y.sub.1] to represent a secret share value of a random number y.

y.sub.1=.sub.j=1.sup.nr.sub.j modulo (3)

[0031] The computer system of the second party generates a second random number y.sub.2 by locally summing up all the elements in {x.sub.j}.sub.j{1, . . . ,n} using Equation 4 below. In some cases, y.sub.2 can be denoted [y.sub.2] to represent a secret share value of a random number y, for example, y=[y.sub.1]+[y.sub.2].

y.sub.2=.sub.j=1.sup.nx.sub.j modulo (4)

[0032] In some implementations, the first random number y.sub.1 and the second random number y.sub.2 can then be used by the first party and the second party, respectively, to add noise to MPC results. In particular, y.sub.1 and y.sub.2 may represent secret share values of randomized noise that can be added to MPC results. Normalizing the random noise shares y.sub.1 and y.sub.2 and adding the normalized y.sub.1 and y.sub.2 to the MPC results can provide a statistically defined degree of differential privacy in the generated results so that the probability of determining any individualized data as part of any party's private data is decreased.

[0033] In some implementations, the communication round of process 100 is one, and number of the communication bits of process 100 is 2n. For example, when =2 and n=64, the number of communication bits of process 100 is 256.

[0034] FIG. 2 illustrates an example method 200, e.g., as implemented by respective computer systems of two parties, of generating secure random numbers for the two parties. Method 200 implements process 100 illustrated in FIG. 1.

[0035] In some implementations, components in method 200 can be mapped to components in process 100. For example, steps 1 to 5 in method 200 correspond to the components in 102. Steps 6 to 10 in method 200 correspond to the components in 104. Steps 11 and 12 correspond to the generation of y.sub.1 and y.sub.2 in 106.

[0036] FIG. 3 illustrates an example process 300 of secure random number generation for two parties. For convenience, process 300 will be described as being performed by a computer system of a first party. An example computer system of the first party is shown in FIG. 4.

[0037] At 302, a computer system of a first party generates a quantity of n random first bits.

[0038] At 304, the computer system of the first party generates a quantity of n -bit first strings, where each of the quantity of n -bit first strings is randomly sampled from a set of -bit strings, and the set of -bit strings includes 2.sup. distinct -bit strings.

[0039] At 306, the computer system of the first party generates, based on the quantity of n -bit first strings and the quantity of n random first bits, a quantity of n pairs of -bit input messages.

[0040] At 308, the computer system of the first party receives a quantity of n pairs of -bit second strings.

[0041] At 310, the computer system of the first party performs, in communication with a second party, a quantity of n 1-out-of-2 random oblivious transfers (ROTs) of the quantity of n pairs of -bit input messages from the first party to the second party.

[0042] At 312, the computer system of the first party generates, based on the quantity of n -bit first strings, a first random number, which corresponds to a first share of a random noise value.

[0043] At 314, the computer system of the first party performs, based on the first random number, secure multiparty computation (MPC) that involves the first party and the second party.

[0044] In some implementations, the random noise generated from the secure random noise generation system, for example, random numbers y.sub.1 and y.sub.2 from 106 in FIG. 1, can be added respectively to the outputs of the two parties in the secure multiparty computation. For example, the first party can be a social media entity and the second party can be another entity. MPC may involve one or more datasets of the two parties that wish to compute a function without revealing individualized data form the one or more datasets. Random noise generated from random numbers y.sub.1 and y.sub.2 can be added to provide a particular degree of differential privacy.

[0045] FIG. 4 illustrates a schematic diagram of an example computing system 400. The system 400 can be used for the operations described in association with the implementations described herein. For example, the system 400 may be included in any or all of the server components discussed herein. The system 400 includes a processor 410, a memory 420, a storage device 430, and an input/output device 440. The components 410, 420, 430, and 440 are interconnected using a system bus 450. The processor 410 is capable of processing instructions for execution within the system 400. In some implementations, the processor 410 is a single-threaded processor. The processor 410 is a multi-threaded processor. The processor 410 is capable of processing instructions stored in the memory 420 or on the storage device 430 to display graphical information for a user interface on the input/output device 440.

[0046] The memory 420 stores information within the system 400. In some implementations, the memory 420 is a computer-readable medium. The memory 420 can be a volatile memory unit or a non-volatile memory unit. The storage device 430 is capable of providing mass storage for the system 400. The storage device 430 is a computer-readable medium. The storage device 430 may be a floppy disk device, a hard disk device, an optical disk device, or a tape device. The input/output device 440 provides input/output operations for the system 400. The input/output device 440 includes a keyboard and/or pointing device. The input/output device 440 includes a display unit for displaying graphical user interfaces.

[0047] In addition to the embodiments of the attached claims and the embodiments described above, the following embodiments are also innovative:

[0048] Embodiment 1 is a computer-implemented method comprising: generating, by a first party, a quantity of n random first bits; generating, by the first party, a quantity of n -bit first strings, wherein each of the quantity of n -bit first string is randomly sampled from a set of -bit strings, and the set of -bit strings comprises distinct -bit strings; generating, by the first party and based on the quantity of n -bit first strings and the quantity of n random first bits, a quantity of n pairs of -bit input messages; receiving, by the first party, a quantity of n pairs of -bit second strings; performing, by the first party and in communication with a second party, a quantity of n 1-out-of-2 random oblivious transfers (ROTs) of the quantity of n pairs of -bit input messages from the first party to the second party; generating, by the first party and based on the quantity of n -bit first strings, a first random number, which corresponds to a first share of a random noise value; and performing, by the first party and based on the first random number, secure multiparty computation (MPC) that involves the first party and the second party.

[0049] Embodiment 2 is the method of embodiment 1, wherein generating the quantity of n pairs of -bit random input messages comprises: generating the quantity of n pairs of -bit random input messages comprises: generating the quantity of n pairs of -bit random input messages using s.sub.1,j=(r.sub.j+a.sub.1,j)modulo and s.sub.2,j=(r.sub.j+1a.sub.1,j)modulo , wherein (s.sub.1,j, s.sub.2,j) is a j-th pair of the n pairs of -bit random input messages, r.sub.j is a j-th -bit first string of the n -bit first strings, a.sub.1,j is a j-th random first bit of the n random first bits, and j=1, . . . , n.

[0050] Embodiment 3 is the method of any one of embodiments 1 through 2, wherein a value of each of the n random first bits is (1) 1 with a probability of 0.5 and (2) 0 with a probability of 0.5.

[0051] Embodiment 4 is the method of any one of embodiments 1 through 3, wherein generating the first random number comprises generating the first random number using y.sub.1=.sub.j=1.sup.nr.sub.j modulo , wherein y.sub.1 is the first random number and r.sub.j is a j-th -bit first string of the n -bit first strings.

[0052] Embodiment 5 is the method of any one of embodiments 1 through 4, wherein the first random number follows a binomial distribution with parameters n and p, and wherein p=0.5.

[0053] Embodiment 6 is the method of any one of embodiments 1 through 5, wherein the first party is a social media entity and the second party is an entity engaging in the secure MPC with the social media entity.

[0054] Embodiment 7 is the method of any one of embodiments 1 through 6, wherein performing the quantity of n 1-out-of-2 ROTs comprises: generating, by the first party, a quantity of n pairs of -bit third strings according to

[00002]$T={\left\{\left(t_{1,j},t_{2,j}\right)\right\}}_{j\left\{1,.Math.,n\right\}}={\left\{\left(m_{1,j{s}_{1,j}},m_{2,j{s}_{2,j}}\right)\right\}}_{j\left\{1,.Math.,n\right\}},$

wherein T is the n pairs of -bit third strings, (m.sub.1,j, m.sub.2,j) is a j-th pair of the n pairs of -bit second strings, (s.sub.1,j, s.sub.2,j) is a j-th pair of the n pairs of -bit input messages, and j=1, . . . , n; and sending, by the first party and to the second party, the n pairs of -bit fourth strings.

[0055] Embodiment 8 is the method of any one of embodiments 1 through 7, wherein performing the secure MPC comprises adding, by the first party, noise corresponding to the first random number to results of the secure MPC.

[0056] Embodiment 9 is a computer-implemented system comprising: one or more computers; and one or more computer memory devices interoperably coupled with the one or more computers and having tangible, non-transitory, machine-readable media storing one or more instructions that, when executed by the one or more computers, cause the computer-implemented system to perform one or more operations comprising: generating, by a first party, a quantity of n random first bits; generating, by the first party, a quantity of n -bit first strings, wherein each of the quantity of n -bit first strings is randomly sampled from a set of -bit strings, and the set of -bit strings comprises distinct -bit strings; generating, by the first party and based on the quantity of n -bit first strings and the quantity of n random first bits, a quantity of n pairs of -bit input messages; receiving, by the first party, a quantity of n pairs of -bit second strings; receiving, by a second party, a quantity of n selection bits and a quantity of n -bit third strings; performing, by the first party and the second party, a quantity of n 1-out-of-2 random oblivious transfers (ROTs) of the quantity of n pairs of -bit input messages from the first party to the second party; generating, by the first party and based on the quantity of n -bit first strings, a first random number, which corresponds to a first share of a random noise value; generating, by the second party and based on a quantity of n 1-out-of-2 random oblivious transfer (ROT) outputs of the second party, a second random number, which corresponds to a second share of the random noise value; and performing, by the first party and the second party and based on the first random number and the second random number, secure multiparty computation (MPC) that involves the first party and the second party.

[0057] Embodiment 10 is the computer-implemented system of embodiment 9, wherein generating the quantity of n pairs of -bit random input messages comprises: generating the quantity of n pairs of -bit random input messages using s.sub.1,j=(r.sub.j+a.sub.1,j)modulo and s.sub.2,j=(r+1a.sub.1,j)modulo , wherein (s.sub.1,j, s.sub.2,j) is a j-th pair of the n pairs of -bit random input messages, r.sub.j is a j-th -bit first string of the n -bit first strings, a.sub.1,j is a j-th random first bit of the n random first bits, and j=1, . . . , n.

[0058] Embodiment 11 is the computer-implemented system of any one of embodiments 9 through 10, wherein a value of each of the n random first bits is (1) 1 with a probability of 0.5.

[0059] Embodiment 12 is the computer-implemented system of any one of embodiments 9 through 11, wherein for a j-th 1-out-of-2 random oblivious transfer (ROT), x.sub.j=s.sub.1,j when a.sub.2,j=0, and x.sub.j=s.sub.2,j when a.sub.2,j=1, wherein x.sub.j is a j-th output of the n 1-out-of-2 ROT outputs of the second party, (s.sub.1,j, s.sub.2,j) is a j-th pair of the n pairs of -bit random input messages, a.sub.2,j is a j-th random second bit of the n random selection bits, and j=1, . . . , n.

[0060] Embodiment 13 is the computer-implemented system of any one of embodiments 9 through 12, wherein generating the first random number comprises generating the first random number using y.sub.1=.sub.j=1.sup.nr.sub.j modulo 2, wherein y.sub.1 is the first random number and r.sub.j is a j-th -bit first string of the n -bit first strings.

[0061] Embodiment 14 is the computer-implemented system of any one of embodiments 9 through 13, wherein generating the second random number y.sub.2 comprises generating y.sub.2 using y.sub.2=.sub.j=1.sup.nx.sub.j modulo , wherein y.sub.2 is the second random number and x.sub.j is a j-th output of the n 1-out-of-2 random oblivious transfer (ROT) outputs of the second party.

[0062] Embodiment 15 is the computer-implemented system of any one of embodiments 9 through 14, wherein the first random number and the second random number follow a binomial distribution with parameters n and p, and wherein p=0.5.

[0063] Embodiment 16 is the computer-implemented system of any one of embodiments 9 through 15, wherein the first party is a social media entity and the second party is an entity engaging in the secure MPC with the social media entity.

[0064] Embodiment 17 is the computer-implemented system of any one of embodiments 9 through 16, wherein performing the quantity of n 1-out-of-2 random oblivious transfers (ROTs) comprises generating the quantity of n 1-out-of-2 ROT outputs of the second party {x.sub.j}, and generating the quantity of n 1-out-of-2 ROT outputs of the second party {x.sub.j} comprises: generating, by the first party, a quantity of n pairs of -bit third strings according t

[00003]$T={\left\{\left(t_{1,j},t_{2,j}\right)\right\}}_{j\left\{1,.Math.,n\right\}}={\left\{\left(m_{1,j{s}_{1,j}},m_{2,j{s}_{2,j}}\right)\right\}}_{j\left\{1,.Math.,n\right\}},$

wherein T is the n pairs of -bit third strings, (m.sub.1,j, m.sub.2,j) is a j-th pair of the n pairs of -bit second strings, (s.sub.1,j, s.sub.2,j) is a j-th pair of the n pairs of -bit input messages, and j=1, . . . , n; sending, by the first party and to the second party, the n pairs of -bit fourth strings; and generating, by the second party, the quantity of n 1-out-of-2 ROT outputs of the second party {x.sub.j} according to x=m.sub.1,jt.sub.1,j when a.sub.2,j=0, and x.sub.j=m.sub.2,jt.sub.2,j, when a.sub.2,j=1, wherein j=1, . . . , n, and a.sub.2,j is a j-th selection bit of the n selection bits received by the second party.

[0065] Embodiment 18 is the computer-implemented system of any one of embodiments 9 through 17, wherein performing the secure MPC comprises adding, by the first party, noise corresponding to the first random number to results of the secure MPC.

[0066] Embodiment 19 is a non-transitory computer-readable medium storing one or more instructions executable by a computer system to perform operations including the methods of any one of embodiments 1 to 8.

[0067] Implementations and all of the functional operations described in this specification may be realized in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Implementations may be realized as one or more computer program products (i.e., one or more modules of computer program instructions encoded on a computer readable medium for execution by, or to control the operation of, data processing apparatus). The computer readable medium may be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter effecting a machine-readable propagated signal, or a combination of one or more of them. The term computing system encompasses all apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus may include, in addition to hardware, code that creates an execution environment for the computer program in question (e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or any appropriate combination of one or more thereof). A propagated signal is an artificially generated signal (e.g., a machine-generated electrical, optical, or electromagnetic signal) that is generated to encode information for transmission to suitable receiver apparatus.

[0068] A computer program (also known as a program, software, software application, script, or code) may be written in any appropriate form of programming language, including compiled or interpreted languages, and it may be deployed in any appropriate form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program does not necessarily correspond to a file in a file system. A program may be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub programs, or portions of code). A computer program may be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network.

[0069] The processes and logic flows described in this specification may be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows may also be performed by, and apparatus may also be implemented as, special purpose logic circuitry (e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit)).

[0070] Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any appropriate kind of digital computer. Generally, a processor will receive instructions and data from a read only memory or a random access memory or both. Elements of a computer can include a processor for performing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data (e.g., magnetic, magneto optical disks, or optical disks). However, a computer need not have such devices. Moreover, a computer may be embedded in another device (e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio player, a Global Positioning System (GPS) receiver). Computer readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices (e.g., EPROM, EEPROM, and flash memory devices); magnetic disks (e.g., internal hard disks or removable disks); magneto optical disks; and CD ROM and DVD-ROM disks. The processor and the memory may be supplemented by, or incorporated in, special purpose logic circuitry.

[0071] To provide for interaction with a user, implementations may be realized on a computer having a display device (e.g., a CRT (cathode ray tube), LCD (liquid crystal display) monitor) for displaying information to the user and a keyboard and a pointing device (e.g., a mouse, a trackball, a touch-pad), by which the user may provide input to the computer. Other kinds of devices may be used to provide for interaction with a user as well; for example, feedback provided to the user may be any appropriate form of sensory feedback (e.g., visual feedback, auditory feedback, tactile feedback); and input from the user may be received in any appropriate form, including acoustic, speech, or tactile input.

[0072] Implementations may be realized in a computing system that includes a back end component (e.g., as a data server), a middleware component (e.g., an application server), and/or a front end component (e.g., a client computer having a graphical user interface or a Web browser, through which a user may interact with an implementation), or any appropriate combination of one or more such back end, middleware, or front end components. The components of the system may be interconnected by any appropriate form or medium of digital data communication (e.g., a communication network). Examples of communication networks include a local area network (LAN) and a wide area network (WAN), e.g., the Internet.

[0073] The computing system may include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.

[0074] While this specification contains many specifics, these should not be construed as limitations on the scope of the disclosure or of what may be claimed, but rather as descriptions of features specific to particular implementations. Certain features that are described in this specification in the context of separate implementations may also be implemented in combination in a single implementation. Conversely, various features that are described in the context of a single implementation may also be implemented in multiple implementations separately or in any suitable sub-combination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination may in some cases be excised from the combination, and the claimed combination may be directed to a sub-combination or variation of a sub-combination.

[0075] Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the implementations described above should not be understood as requiring such separation in all implementations, and it should be understood that the described program components and systems may generally be integrated together in a single software product or packaged into multiple software products.

[0076] A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the disclosure. For example, various forms of the flows shown above may be used, with steps re-ordered, added, or removed. Accordingly, other implementations are within the scope of the following claims.