Mix and match: a new approach to secure multiparty computation

Details Mix and match: a new approach to secure multiparty computation Mix and match: a new approach to secure multiparty computation

2000-03-13

2004-08-03

Barrón, Gilberto (Department: 2132)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S163000, C713S169000, C713S180000, C380S030000, C380S047000, C380S283000, C380S285000, C463S029000, C717S126000

Reexamination Certificate

active

06772339

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to methods for performing secure multiparty computations.
BACKGROUND OF THE INVENTION
Secure multiparty computation is the process whereby a collection of n participants compute a function ƒ on secret input values such that only the final result of the computation is made known to the participants. A. C. Yao is generally credited with innovating the notion of secure multiparty computation, offering as an example the well-known Yao's Millionaires' Problem. See Yao, A. C., “Protocols for Secure Computations”, 23
rd
Annual Symposium on Foundations of Computer Science, pp. 160-64, 1982. In a two-party setting, the millionaires' problem is that of enabling two entities to determine which is wealthier, without either being able to learn any additional information about the other's fortune. For example, suppose that Alice has A million dollars and Bob has B million dollars. The goal is to securely compute the function ƒ(A, B), where ƒ(A, B) is defined as=0 if A=B, 1 if A>B, and 2 if B>A.
All of the known methods for secure multiparty computation rely on the use of a circuit to simulate the particular function ƒ of interest. The circuit is generally viewed as being composed of two logical connectors, an XOR gate (binary addition) and an AND gate (binary multiplication), which together allow for the realization of any boolean function. These methods for secure multiparty computation simulate the function of interest by evaluating the circuit on a gate-by-gate basis. To simulate an XOR gate using these methods, participants can perform local addition on their respective shares. To simulate an AND gate, however, the computation must be distributed, a procedure that in the computational model generally involves a round of verifiable secret sharing (VSS). However, the circuits used in these approaches typically will contain many AND gates and, thus, the VSS associated with each AND gate can become computationally demanding. The known approaches therefore often yield rather impractical algorithms. Recent efforts have led to some efficiency improvements. See R. Gennaro, M. Rabin, and T. Rabin, “Simplified VSS and Fast-track Multiparty Computations with Applications to Threshold Cryptography”, Proceedings of 1998 ACM Symposium on Principles of Distributed Computing, pp. 25-34, 1997. Even with these improvements, however, the computational costs for problems of interest remain high, and the impact on real-world applications has been negligible.
SUMMARY OF THE INVENTION
The above-identified problems are solved and a technical advance is achieved in the art by providing an innovative method for secure multiparty computation which dispenses with the need for extensive use of VSS. An exemplary method for secure multiparty computation includes: generating a data set based on a function to be computed, the data set comprising pairs of first data and second data; for each pair of first data and second data, encrypting the first data and the second data; randomly mixing pairs of the encrypted first data and second data; comparing encrypted input data with the encrypted first data to detect a match; and selecting encrypted second data corresponding to the detected match.
In accordance with one embodiment of the present invention, n participants to a secure multiparty computation agree upon a function ƒ to be computed and a representation of that function as a circuit with at least one gate. For each gate in the circuit, the participants generate a logical table. A logical table includes all possible input and output values for the gate to which it pertains based on the function ƒ. The participants then preferably encode the input and output values in each logical table, and pass each table through a mix network. The mix network generates a blinded table for each encoded logical table. A blinded table is similar to its corresponding encoded logical table except that now the rows of the table are randomly permuted and the input and output values in each row are individually encrypted using a public key y. The process of generating blinded tables is referred to herein as “the mixing process.”
After the initial mixing process, the participants engage in “the matching process.” In this regard, the participants exchange encoded and encrypted versions of their secret inputs. These inputs are encrypted using the same public key y as used during the mixing process. The participants then jointly compute the function ƒ using the secret inputs and the representative circuit. To simulate a gate in the circuit, the participants compare the encrypted inputs to the gate with each encrypted input value in the blinded table until a match is detected. In the case where the circuit is a multi-layer circuit, the encrypted inputs to the gate are either the secret inputs provided by the participants (in the case where the gate resides in the first layer of the circuit) or the outputs of an upstream gate (in the case where the gate resides in either the output layer or some intermediate layer of the circuit). When a match is detected, the corresponding output value in the matched row is taken to be the output of the gate.
The foregoing is referred to herein as the “mix and match” method of secure multiparty computation. As will be understood, the mix and match method is performed in an identical manner for every gate in the circuit, irrespective of the layer in which it resides or the function being computed, until the output of the last gate is identified. The output of the last gate can then be decoded and decrypted using a shared secret key x to obtain the output of the function ƒ.
Compared with previous approaches to secure multiparty computation, the mix and match method of the present invention is conceptually simpler, and, in many cases, is more computationally efficient as well. In addition, the method is provably secure relative to the Decision Diffie-Hellman problem, with robustness against a static malicious adversary corrupting fewer than one-half of the players.
Other and further aspects of the present invention will become apparent during the course of the following description and by reference to the attached drawings.


REFERENCES:
patent: 3800281 (1974-03-01), Devore et al.
patent: 5481717 (1996-01-01), Gaboury
patent: 6149522 (2000-11-01), Alcorn et al.
patent: 6396928 (2002-05-01), Zheng
A. Juels and M. Jakobsson, “Millimix: Mixing in Small Batches,” DIMACS Tech. Report 99-33, Jun. 1999.
Jakobsson, M., “Flash Mixing”, Proceedings of 1999 ACM Symposium on Principles of Distributed Computing, pp. 83-89, 1999.
R. Gennaro, M. Rabin, and T. Rabin, “Simplified VSS and Fast-track Multiparty Computations with Applications to Threshold Cryptography”, Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, pp. 101-111, 1998.
Schnoor, C. P., “Efficient Signature Generation by Smart Cards”, Journal of Cryptology, 4:161-174, 1991.
El Gamal, T., “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms”, IEEE Transactions on Information Theory, vol. IT-31, No. 4, pp. 469-472, Jul. 1985.
Yao, A.C., “Protocols for Secure Computations”, 23rdAnnual Symposium on Foundations of Computer Science, pp. 160-164, 1982.

Affiliated with

Also associated with

Rating

Mix and match: a new approach to secure multiparty computation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Mix and match: a new approach to secure multiparty computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mix and match: a new approach to secure multiparty computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3280781