암호화된 데이터에 대한 프라이버시를 보존하는 k-means 클러스터링 기법
Privacy-Preserving k-means Clustering of Encrypted Data
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
k-means 클러스터링 알고리즘은 주어진 데이터를 비슷한 k개의 그룹으로 묶어서 시장 세분화나 의료연구 등의다양한 분야에서 활용되고 있다. 본 논문에서는 다수의 사용자 데이터를 노출하지 않고 암호화하여 외부 서버에 저장하는 환경에서 프라이버시를 보존하는 클러스터링 알고리즘을 제안한다. 분산된 서버에 평문으로 저장된 데이터를다자간 계산프로토콜을 기반으로 수행된 기존 클러스터링 알고리즘 연구와 비교했을 때 제안하는 기법은 모든 데이터를 안전하게 암호문으로 저장할 수 있다는 뚜렷한 장점이 있다. 데이터 간의 거리를 측정하고 비교하기 위해서 덧셈과 곱셈 연산이 가능한 완전동형암호로 데이터를 암호화한다. 프로토콜 수행과정에서 사용자 데이터의 안전성을분석하고 통신량과 연산량을 다른 연구들과 비교한다.
Abstract
The k-means clustering algorithm groups input data with the number of groups represented by variable k. In fact, thisalgorithm is particularly useful in market segmentation and medical research, suggesting its wide applicability. In this paper,we propose a privacy-preserving clustering algorithm that is appropriate for outsourced encrypted data, while exposing noinformation about the input data itself. Notably, our proposed model facilitates encryption of all data, which is a largeadvantage over existing privacy-preserving clustering algorithms which rely on multi-party computation over plaintext datastored on several servers. Our approach compares homomorphically encrypted ciphertexts to measure the distance betweeninput data. Finally, we theoretically prove that our scheme guarantees the security of input data during computation, and alsoevaluate our communication and computation complexity in detail.
참고문헌 (21)
- S. Dolnicar, "Using cluster analysis for market segmentation - typical misconceptions, established methodological weaknesses and some recommendations for improvement", Australasian Journal of Market Research, 11(2), pp.5~12 (2003)
- M.N. Tuma, "A survey of the challenges and pitfalls of cluster analysis application in market segmentation", International Journal of Market Research, 53(3), pp.391~414 (2011)
- M. GJ, "Cluster analysis and related techniques in medical research", Statistical Methods in Medical Research, 1(1), pp.27~48 (1992)
- R. Paul, "Clustering medical data to predict the likelihood of diseases", Proceedings of 2010 Fifth International Conference on Digital Information Management, pp.44~49 (2010)
- P. Bunn, "Secure two-party k-means clustering", Proceedings of the 14th ACM conference on Computer and communications security, pp.486~497 (2007)
- G. Jagannathanand, "Privacy-preserving distributed kmeans clustering over arbitrarily partitioned data", Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pp.593~599 (2005)
- S. Jha, "Privacy Preserving Clustering", European Symposium on Research in Computer Security, LNCS, 3679, pp.397~417 (2005)
- Unsupervised Machine Learning on Encrypted Data, "A. Jaschke", IACR ePrint, ~, pp.Report 2018-411 (2018)
- V. Nikolaenko, "Privacy-Preserving Ridge Regression on Hundreds of Millions of Records", Proceedings of 2013 IEEE Symposium on Security and Privacy, pp.334~348 (2013)
- A.C. Yao, "How to generate and exchange secrets", Proceedings of 27th Annual Symposium on Foundations of Computer Science, pp.162~167 (1986)
- Y. Lindell, "A Proof of Security of Yao’s Protocol for Two-Party Computation", Journal of Cryptology, 22(2), pp.161~188 (2009)
- Z. Brakerski, "(Leveled) fully homomorphic encryption without bootstrapping", ACM Transactions on Computation Theory, 6(13) (2014)
- "HElib"[URL]
- I. Chillotti, "Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds", Advances in Cryptology, ASIACRYPT 2016, LNCS, 10031, pp.3~33 (2016)
- C. Gentry, "Homomorphic Encryption from Learning with Errors: Conceptually –Simpler, Asymptotically-Faster, Attribute-Based", Advances in Cryptology, CRYPTO '13. LNCS, 8042, pp.75~92 (2013)
- "TFHE:Fast Fully Homomorphic Encryption over the Torus"[URL]
- B.K. Samanthula, "k-Nearest Neighbor Classification over Semantically Secure Encrypted Relational Data", IEEE Transactions on Knowledge and Data Engineering, 27(5), pp.1261~1273 (2015)
- H. Narumanchi, "Performance Analysis of Sorting of FHE Data: Integer-Wise Comparison vs Bit-Wise Comparison", Proceedings of 2017 IEEE 31st International Conference on Advanced Information Networking and Applications, pp.902~908 (2017)
- J. MacQueen, "Some Methods for classification and Analysis of Multivariate Observations", Proceedings of Fifth Berkeley Symposium on Mathematical Statistics and Probability, pp.281~297 (1967)
- Multi-Key FHE from LWE, Revisited, "C. Peikert", IACR, ~, pp.IACR ePrint 2016-196 (2016)
- V. Lyubashevsky, "On Ideal Lattices and Learning with Errors over Rings", Advances in Cryptology, EUROCRYPT 2010, LNCS, 6110, pp.1~23 (2010)