CASSANDRA: a probabilistic, efficient, and privacy-preserving solution to compute set intersection
Tóm tắt
Enforcing security often requires the two legitimate parties of a communication to determine if they share a secret, without disclosing information (e.g., the shared secret itself, or just the existence of such a secret) to third parties. In this paper, we propose CASSANDRA, a toolbox composed of three probabilistic protocols that allows two parties, each one having a subset of elements drawn by a pre-determined set, to compute information about the intersection of such two sets. In particular, C-void decides whether the two sets are disjoint; C-size allows to compute how many elements the intersection is composed of; and, C-set returns the identity of the elements of the intersection (if any). These protocols differ, other than in functionality, also in the degree of assurance they can provide and the degree of interactions required by the two parties. The communication cost also differs, but in any case, it is below the cost of competing solution representing the state of the art. These protocols also share some common features: that is, they are completely tunable and specifically suited for devices having constraints on energy, communication, storage, and bandwidth. Examples of these devices are portable devices (e.g., phones) handling satellite communications, or nodes of wireless sensor networks. Thorough analysis and extensive simulations support our findings.
Tài liệu tham khảo
Agrawal, R., Evfimievski, A., Srikant, R.: Information sharing across private databases. In: Proceedings of the 22th ACM SIGMOD International Conference on Management of Data (SIGMOD ’03), pp. 86–97. (2003)
Barbay J., López-Ortiz A., Lu T., Salinger A.: An experimental investigation of set intersection algorithms for text searching. J. Exp. Algorithmics 14, 3.7–3.24 (2009)
Chan, H., Perrig, A., Song, D.X.: Random key predistribution schemes for sensor networks. In: IEEE Symposium on Security and Privacy, p. 197. (2003)
Dachman-Soled, D., Malkin, T., Raykova, M., Yung, M.: Efficient robust private set intersection. In: Proceedings of the 7th International Conference on Applied Cryptography and Network Security, ACNS ’09, pp. 125–142. Springer, Berlin (2009)
De Cristofaro E., Kim J.: Some like it private: sharing confidential information based on oblivious authorization. IEEE Secur. Priv. 8, 18–24 (2010)
Demaine, E.D., López-Ortiz, A., Munro, J.I.: Adaptive set intersections, unions, and differences. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’00), pp. 743–752. (2000)
Di Pietro, R., Mancini, L.V., Mei, A., Panconesi, A., Radhakrishnan, J.: Redoubtable sensor networks. ACM Trans. Inf. Syst. Secur. 11(3), 13:1–13:22 (2008)
Eschenauer, L., Gligor, V.: A key-management scheme for distributed sensor network. In: Proceedings of the 9th ACM Conference on Computer and Communications Security (CCS ’02), pp. 267–282. (2002)
Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: Proceedings of the 23rd Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT ’04), pp. 1–19. (2004)
Håstad J., Wigderson A.: The randomized communication complexity of set disjointness. J. Theory Comput. 3(1), 211–219 (2007)
Hazay, C., Lindell, Y.: Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In: Proceedings of the 5th Conference on Theory of Cryptography, TCC’08, pp. 155–175. Springer, Berlin (2008)
Jarecki, S., Liu, X.: Fast secure computation of set intersection. In: Proceedings of the 7th International Conference on Security and Cryptography for Networks, SCN’10, pp. 418–435. Springer, Berlin (2010)
Kalyanasundaram B., Schnitger G.: The probabilistic communication complexity of set intersection. SIAM J. Discret. Math. 5(4), 545–557 (1992)
Kiayias, A., Mitrofanova, A.: Testing disjointness of private datasets. In: Proceedings of the 9th International Conference on Financial Cryptography and Data Security (FC ’05), pp. 109–124. (2005)
Kissner, L., Song, D.X.: Privacy-preserving set operations. In: Proceedings of the 25th Annual International Cryptology Conference (CRYPTO ’05), pp. 241–257. (2005)
Kurtz T.G., Manber U.: A probabilistic distributed algorithm for set intersection and its analysis. J. Theor. Comput. Sci. 49(2–3), 267–282 (1987)
Kushilevitz E., Nisan N.: Communication Complexity. Cambridge University Press, Cambridge (1997)
Mitzenmacher M., Upfal E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (2005)
Motwani R., Raghavan P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Tsudik, G., Ateniese, G., De Cristofaro, E.: (if) size matters: size-hiding private set intersection. In: The 14th IACR International Conference on Practice and Theory of Public Key Cryptography (PKC) (2011)
Tsudik, G., De Cristofaro, E.: Practical private set intersection protocols with linear complexity. In: Financial Cryptography (2010)
Tsudik, G., De Cristofaro, E., Kim, J.: Linear-complexity private set intersection protocols secure in malicious model. In: The 16th Annual International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt) (2010)
Yao, A.C.-C.: Some complexity questions related to distributive computing. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing (STOC ’79), pp. 209–213. (1979)
Ye Q., Wang H., Pieprzyk J., Zhang X.M.: Unconditionally secure disjointness tests for private datasets. Int. J. Appl. Cryptogr. 1(3), 225–235 (2009)