Abstract
Existing protocols for private set intersection are based on homomorphic public-key encryption and the technique of representing sets as polynomials in the cryptographic model. Based on the ideas of these protocols and the two-dimensional verifiable secret sharing scheme, we propose a protocol for private set intersection in the information-theoretic model. By representing the sets as polynomials, the set intersection problem is converted into the task of computing the common roots of the polynomials. By sharing the coefficients of the polynomials among parties, the common roots can be computed out using the shares. As long as more than 2n/3 parties are semi-honest, our protocol correctly computes the intersection of n sets, and reveals no other information than what is implied by the intersection and the secrets sets controlled by the active adversary. This is the first specific protocol for private set intersection in the information-theoretic model as far as we know.
Supported by National Natural Science Foundation of China under Grant NO.90304007 and the National Grand Fundamental Research 973 Program of China under Grant NO.2004CB318004.
Chapter PDF
Similar content being viewed by others
References
Beaver, D.: Efficient Multiparty Protocols Using Circuit Randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992)
Beerliová-Trubíniová, Z., Hirt, M.: Efficient Multi-Party Computation with Dispute Control. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 305–328. Springer, Heidelberg (2006)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation. In: 20th Annual Symposium on the Theory of Computing (STOC’88), pp. 1–10. ACM Press, New York (1988)
Freedman, M.J., Nissim, K., Pinkas, B.: Efficient Private Matching and Set Intersection. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg (2004)
Goldreich, O., Micali, S., Wigderson, A.: How to Play Any Mental Game — A Completeness Theorem for Protocols with Honest Majority. In: 19th ACM Symposium on the Theory of Computing (STOC’87), pp. 218–229. ACM Press, New York (1987)
Hirt, M., Maurer, U., Przydatek, B.: Efficient Secure Multi-Party Computation. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 143–161. Springer, Heidelberg (2000)
Kissner, L., Song, D.: Privacy-Preserving Set Operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005)
Kissner, L., Song, D.: Private and Threshold Set-Intersection. Technical Report CMU-CS-05-113, Carnegie Mellon University (2005)
Shamir, A.: How to Share a Secret. Communications of the ACM 22, 612–613 (1977)
Yao, A.C.: Protocols for Secure Computations. In: 23rd IEEE Symposium on Foundations of Computer Science (FOCS’82), pp. 160–164. IEEE Computer Society Press, Los Alamitos (1982)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Li, R., Wu, C. (2007). An Unconditionally Secure Protocol for Multi-Party Set Intersection . In: Katz, J., Yung, M. (eds) Applied Cryptography and Network Security. ACNS 2007. Lecture Notes in Computer Science, vol 4521. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72738-5_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-72738-5_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72737-8
Online ISBN: 978-3-540-72738-5
eBook Packages: Computer ScienceComputer Science (R0)