Solving the "Millionaire Problem" - Interpretation of Privacy Comparison and Efficient Algorithms

text

Privacy comparison refers to obtaining the magnitude relationship between the two parties without revealing the specific values ​​of the two parties. The millionaire problem first originated from Yao Zhizhi: There are two millionaires who want to compare who is richer, but they don’t want to disclose how much money they have. How can they compare without a trusted third party? This question was raised in the 1980s by Yao Qizhi, the first and only Turing Award winner in China. He is the first person in computer science and education in China, and opened a new door for modern cryptography.

In the previous article "Elegant Job Hunting—Privacy Comparison Algorithm Example", the application scenarios of privacy comparison and how to implement it have been introduced through job hunting cases. This article mainly introduces a privacy comparison protocol with relatively high efficiency at present.

This protocol is a sub-protocol proposed in [1] CrypTFlow2: Practical 2-Party SecureInference, and based on this protocol, the DRelu activation function is applied to the neural network.

--Related technologies--

The protocol is mainly constructed using two technologies of Boolean secret sharing and oblivious transmission:

▲ inadvertent transmission

Oblivious transfer (OT, Oblivious Transfer) means that the data sender has n data, the data receiver receives one of the data, and the data receiver cannot obtain other data, and the data sender does not know the details of the data that the receiver chooses to receive. Which one is it. An implementation scheme has been introduced in the previous article "Privacy Computing Technology Based on Secure Multi-Party Computation (MPC) (1)", so this article will not repeat it.

▲ Boolean secret sharing

In secure multi-party computing, secret sharing will be used to split the data and share it out. Each party gets the corresponding fragment of each data, and the calculation logic for the original data will be converted to the calculation of the fragments. After the entire calculation logic is completed, Then aggregate and restore the calculation results of the fragments to obtain the calculation results of the original data.

Boolean secret sharing refers to splitting a Boolean value b into two fragments b0 and b1, and bringing the two fragments together to restore the original data b.

Fragment generation: Randomly generate a Boolean value b0, and perform XOR with b to calculate b1=b0⊕b

 b=b0⊕b1

Shard Restore: Execute XOR operation on two shards

      a=a0⊕a1，b=b0⊕b1

      a⊕b=(a0⊕b0)⊕(a1⊕b1)

XOR operation: Boolean secret sharing satisfies the homomorphic property in the XOR operation, and performing the XOR operation on the fragments locally and then restoring it is equivalent to the XOR operation on the original data

AND operation: Boolean secret sharing does not satisfy the homomorphic property for AND operations, and uses oblivious transfer technology to achieve safe AND operations:

Alice holds fragments a0 and b0, Bob holds fragments a1 and b1, through the AND operation, Alice obtains c0, Bob obtains c1, c0⊕c1=(a0⊕a1)∧(b0⊕b1), and the security of both fragments is guaranteed ;

*Alice, as the sender of oblivious transmission, randomly generates a Boolean value r as c0, and generates the input of oblivious transmission as shown below:

*Bob, as the recipient of inadvertent transmission, splices his fragments a1 and b1 into a1||b1 as an option for inadvertent transmission to obtain data r⊕((a0⊕a1)∧(b0⊕b1)) as c1;

It can be verified that c0⊕c1= r⊕r⊕((a0⊕a1)∧(b0⊕b1))=(a0⊕a1)∧(b0⊕b1);

The essence is to list all the possibilities of the AND operation, and after adding random items, the other party chooses the confused calculation result according to its own data.

--Implementation Ideas--

▲ Plaintext comparison

First of all, regardless of the privacy of comparison operations, how do two numbers compare in normal circumstances:

a=123，b=5879，a=>[0,1,2,3]，b=>[5,8,7,9]

*Align the two numbers into a digital array of the same length, if the length is not enough, add 0 in front

*Compare the numbers in the two arrays sequentially. If the numbers in the corresponding digits are equal, continue to compare the next digit until one digit is unequal. The comparison result of the earliest unequal digit is the comparison result of the two data. If If all digits are equal, the two numbers are equal. The whole process can be summarized as the following formula:

Both X and Y are data of length n, 1{X

X=x0||x1||x2||...||x(n-1), Y=y0||y1||y2||...||y(n-1), xi, yi means The i-th data after splitting

1{X

1{X1

     ...

1{X(n-1)

Xi=xi||...||x(n-1), Yi=yi||...||y(n-1), used to represent the data after removing the first i-1 bits

▲ Insecure privacy comparison

If you want to convert the above comparison scheme into a private comparison, the easiest way to think of it is to make the comparison of the two smallest comparison units private, which has been introduced in the previous article "Elegant Job Hunting—Privacy Comparison Algorithm Example": The comparison of two smallest comparison units can be done through the oblivious transfer protocol. This indeed guarantees the security of a single minimum comparison unit, but for some cases, some situations of data will be exposed:

a=1230 b=1231, for the comparison of these two numbers, if b is the recipient of ot, that is, the acquirer of the data comparison result of the smallest comparison unit, and the comparison is performed according to the above scheme, two additional information will be leaked:

1) When the first few digits are the same: b will know that the first three digits of a are 123;

2) The data of the two smallest units is the data at both ends of the smallest unit range: b will know that the last digit of a is 0;

▲ Eliminate insecurity

text

In the privacy comparison protocol in this paper, the whole comparison idea is consistent with the insecure privacy comparison above, but this protocol introduces secret sharing technology, and the sender confuses the previous one for each data when the comparison result is obtained through the inadvertent transfer protocol. Random items, so that neither party will obtain the comparison result of the minimum comparison unit data, but the fragments of the comparison result, and use the fragments to recursively compare according to the plaintext comparison process. After all the minimum comparison units are compared, the comparison The resulting fragments are restored to obtain comparison results for the entire data.

Since the comparison results of the smallest unit are all fragments, the recursive calculation result will not be restored until the comparison is completed, thus avoiding the information leakage caused by obtaining the comparison result of the smallest comparison unit.

--Agreement process--

Alice has data x, Bob has data y, the binary length of the data is l, the binary length of the minimum comparison unit is m, the number of the minimum comparison units divided is q=l/m, and the decimal maximum value of the minimum comparison unit is M= 2^m-1

1) The two parties divide the data separately: x=x0||...||x(q-1), y=y0||...||y(q-1)

2) For all the smallest comparison units xi(0<=i_0，*Alice prepares data as sender of oblivious transfers: random boolean generation

sij=_0 ⊕ 1{xi

      tij=_0 ⊕ 1{xi=j}

_0, as the boolean sharing fragments of whether xi is less than or equal to yi, respectively, for 0<=j<=M, the input of two inadvertent transfer instances are respectively set as:

*Bob uses yi as input to execute two instances of inadvertent transfer respectively, and obtains the fragments of the two comparison results:1

1 and_0，For example, when m is 2, Alice's first minimum comparison unit x0=2, Bob's first minimum comparison unit y0=1, Alice randomly generates

_0, and generate two oblivious inputs as follows:

_1=0⊕_0，_1=0⊕_0

Bob uses y0 as an option for both oblivious transfers, obtaining:

3) After the comparison of all the minimum comparison units is completed, both parties have obtained the Boolean shared fragments of whether the corresponding minimum comparison units are less than or equal to each other, and then can follow the plaintext comparison process and use fragment recursion to calculate the fragments of the final comparison result.

For the XOR operation of fragments, it is only necessary to perform XOR of fragments locally. For the AND operation of fragments, it is necessary to inadvertently transfer the fragments of the calculated results according to the scheme introduced above.

In the recursion process, there are mainly two places that need to perform AND operations:

1{x0||x1 = y0||y1 } ∧ 1{x2 < y2 }

When all previous comparison units are equal and the next one needs to be compared:

1{x0||x1 = y0||y1} = 1{x0 = y0 } ∧ 1{x1 = y1 }

When computing whether all preceding comparison units are equal:

--Summarize--

For the comparison of a single element, the OT instance of the operation cannot be optimized through OT expansion, because recursive calculations are required, and there are dependencies before and after. For the comparison of batch elements, the efficiency can be optimized through OT expansion in the vertical direction for OT instances with the same position and operation.

About the Author

About the Author

text

references

references