Constant-round privacy preserving multiset union
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Privacy preserving multiset union (PPMU) protocol allows a set of parties, each with a multiset, to collaboratively compute a multiset union {\em secretly}, meaning that any information other than union is not revealed. We propose efficient PPMU protocols, using multiplicative homomorphic cryptosystem. The novelty of our protocol is to directly encrypt a polynomial by representing it by an element of an extension field. The resulting protocols consist of constant rounds and improve communication cost. We also prove the security of our protocol against malicious adversaries, in the random oracle model.
Abstract
Privacy preserving multiset union (PPMU) protocol allows a set of parties, each with a multiset, to collaboratively compute a multiset union {\em secretly}, meaning that any information other than union is not revealed. We propose efficient PPMU protocols, using multiplicative homomorphic cryptosystem. The novelty of our protocol is to directly encrypt a polynomial by representing it by an element of an extension field. The resulting protocols consist of constant rounds and improve communication cost. We also prove the security of our protocol against malicious adversaries, in the random oracle model.
참고문헌 (27)
- B. Applebaum, "Collaborative, privacy-preserving data aggregation at scale", pp.56~74 (2010), Privacy Enhancing Technologies
- F. Boudot, "A fair and effcient solution to the socialist millionaires' problem", Discrete Appl. Math, 111(1), pp.23~36 (2001)
- J. Brickell, "Privacy-preserving graph algorithms in the semi-honest model", ASIACRYPT, pp.236~252 (2005)
- M. Chateauneuf, "Slope packings and coverings, and generic algorithms for the discrete logarithm problem", J. Combin. Des, 11(1), pp.36~50 (2003)
- E. D. Cristofaro, "Practical private set intersection protocols with linear complexity", Financial Cryptography, pp.143~159 (2010)
- D. Dachman-Soled, "Effcient robust private set intersection", ACNS, pp.125~142 (2009)
- Y. Desmedt, "Threshold cryptosystems", CRYPTO, pp.307~315 (1989)
- A. V. Evfimievski, "Limiting privacy breaches in privacy preserving data mining", PODS, pp.211~222 (2003)
- M. J. Freedman, "Effcient private matching and set intersection", EUROCRYPT, pp.1~19 (2004)
- K. B. Frikken, "Privacy-preserving set union", ACNS, pp.237~252 (2007)
- J. Furukawa, "An effcient scheme for proving a shuffle", CRYPTO, pp.368~387 (2001)
- O. Goldreich, "Foundations of Cryptography" (2004), Cambridge University Press
- C. Hazay, "Effcient set operations in the presence of malicious adversaries", Public Key Cryptography, pp.312~331 (2010)
- B. A. Huberman, "Enhancing privacy and trust in elec- tronic communities", ACM Conference on Electronic Commerce, pp.78~86 (1999)
- M. Kantarcioglu, "Privacy-preserving distributed mining of association rules on horizontally partitioned data", IEEE Trans. Knowl. Data Eng, 16(9), pp.1026~1037 (2004)
- L. Kissner, "Privacy-preserving set operations, In Advances in Cryptology", CRYPTO, pp.241~257 (2005)
- Private and threshold set-intersection, "L. Kissner", Carnegie Mellon University, ~, pp.Technical Report CMU-CS-05-113 (2005)
- H. Lipmaa, "Verifiable homomorphic oblivious transfer and private equality test", ASI- ACRYPT, pp.416~433 (2003)
- C. A. Neff, "A verifiable secret shue and its application to e-voting", ACM Conference on Computer and Communications Security, pp.116~125 (2001)
- C. M. O'Keefe, "Privacy-preserving data linkage protocols", WPES, pp.94~102 (2004)
- T. P. Pedersen, "A threshold cryptosystem without a trusted party", EUROCRYPT, pp.522~526 (1991)
- K. Peng, "An effcient and veri able solution to the millionaire problem", ICISC, pp.51~66 (2004)
- J. M. Pollard, "Monte carlo methods for index computation", Math. Comp, 32(143), pp.918~924 (1978)
- Y. Sang, "Privacy preserving set intersection based on bilinear groups", ACSC, pp.47~54 (2008)
- V. Shoup, "Lower bounds for discrete logarithms and related problems", EUROCRYPT, pp.256~266 (1997)
- V. Shoup, "A Computational Introduction to Number Theory and Algebra" (2005), Cambridge Uni-versity Press
- A. C. Yao, "Protocols for secure computations, In Foundations of Computer Science", SFCS '08. 23rd Annual Symposium on, pp.160~164 (1982)