[논문]클라우드 컴퓨팅에서 프라이버시 보호를 지원하는 데이터 필터링 기반 병렬 영역 질의 처리 알고리즘

김형진; 장재우

doi:10.3745/ktccs.2021.10.9.243

클라우드 컴퓨팅에서 프라이버시 보호를 지원하는 데이터 필터링 기반 병렬 영역 질의 처리 알고리즘
Privacy-Preserving Parallel Range Query Processing Algorithm Based on Data Filtering in Cloud Computing 원문보기

정보처리학회논문지. KIPS transactions on computer and communication systems 컴퓨터 및 통신 시스템, v.10 no.9, 2021년, pp.243 - 250

김형진 (전북대학교 컴퓨터공학부) , 장재우 (전북대학교 IT정보공학과)

초록
AI-Helper

최근 클라우드 컴퓨팅이 발전함에 따라 데이터베이스 아웃소싱에 대한 관심이 증가하고 있다. 그러나 데이터베이스를 아웃소싱하는 경우, 데이터 소유자의 정보가 내부 및 외부 공격자에게 노출되는 문제점을 지닌다. 따라서 본 논문에서는 프라이버시 보호를 지원하는 병렬 영역 질의처리 알고리즘을 제안한다. 제안하는 알고리즘은 Paillier 암호화 시스템을 사용하여 데이터 보호, 질의 보호, 접근 패턴 보호를 지원한다. 또한 기존 알고리즘에서 영역 겹침을 확인하는 프로토콜(SRO)의 연산 비용을 줄이기 위해 garbled 서킷(circuit) 을 통해 SRO 프로토콜의 효율성을 향상시킨다. 제안하는 병렬 영역질의 처리 알고리즘은 크게 2단계로 구성된다. 이는 kd-트리를 병렬적으로 탐색하고 질의를 포함하는 단말 노드의 데이터를 안전하게 추출하는 병렬 kd-트리 탐색 단계와 다수의 thread를 통해 질의 영역에 포함된 데이터를 병렬 탐색하는 병렬 데이터 탐색 단계로 구성된다. 한편, 제안하는 알고리즘은 암호화 연산 프로토콜과 인덱스 탐색의 병렬화를 통해 우수한 질의 처리 성능을 제공한다. 제안하는 병렬 영역 질의 처리 알고리즘은 thread 수에 비례하여 성능이 향상됨을 알 수 있고 10 thread 상에서 기존 기법은 38초, 제안하는 기법은 11초로 약 3.4배의 성능 향상이 있음을 보인다.

Abstract ▼ AI-Helper

Recently, with the development of cloud computing, interest in database outsourcing is increasing. However, when the database is outsourced, there is a problem in that the information of the data owner is exposed to internal and external attackers. Therefore, in this paper, we propose a parallel range query processing algorithm that supports privacy protection. The proposed algorithm uses the Paillier encryption system to support data protection, query protection, and access pattern protection. To reduce the operation cost of a checking protocol (SRO) for overlapping regions in the existing algorithm, the efficiency of the SRO protocol is improved through a garbled circuit. The proposed parallel range query processing algorithm is largely composed of two steps. It consists of a parallel kd-tree search step that searches the kd-tree in parallel and safely extracts the data of the leaf node including the query, and a parallel data search step through multiple threads for retrieving the data included in the query area. On the other hand, the proposed algorithm provides high query processing performance through parallelization of secure protocols and index search. We show that the performance of the proposed parallel range query processing algorithm increases in proportion to the number of threads and the proposed algorithm shows performance improvement by about 5 times compared with the existing algorithm.

주제어

표/그림 (7)

표 Table 1. Equation Notation
표 Table 2. Comparison of Related Works
그림 Fig. 1. Overall System Architecture
표 Table 3. Experimental Parameter
그림 Fig. 2. Performance Evaluation According to the Change in the Number of Data
그림 Fig. 3. Performance Evaluation According to the Change in the Number of Threads
그림 Fig 4. Performance Evaluation According to the Change in Key Size (512 and 1024)

참고문헌 (21)

B. Hayes, "Cloud computing," pp.9-11, 2008.
C. Bing, "Atos, IT provider for winter olympics, hacked months before opening ceremony cyberattack," 2018. [Internet], https://www.cyberscoop.com/atos-olympics-hackolympic-destroyer-malware-peyongchang/.
김재광, "개인정보보호법에 관한 새로운 법적 문제," 강원법학, Vol.36, pp.95-120, 2012.

상세보기
W. Wu, Wei, X. Ming, P. Udaya, and L. Bin, "Efficient privacy-preserving frequent itemset query over semantically secure encrypted cloud database," World Wide Web, Vol.24, No.2, pp.607-629, 2021.

상세보기
W. Wu, P. Udaya, L. Jian, and X. Ming, "Privacy preserving k-nearest neighbor classification over encrypted database in outsourced cloud environments," World Wide Web, Vol.22, No.1, pp.101-123. 2019.

상세보기
H. Dai, J. Yan, Y. Geng, H. Haiping, and Y. Xun, "A privacy-preserving multi-keyword ranked search over encrypted data in hybrid clouds," IEEE Access, Vol.8, pp.4895-4907, 2019.
C. S. H. Eom, C. C. Lee, W. Lee, and C. K. Leung, "Effective privacy preserving data publishing by vectorization," Information Sciences, Vol.527, pp.311-328, 2020.

상세보기
S. Belguith, N. Kaaniche, M. Laurent, A. Jemai, and R. Attia, "Accountable privacy preserving attribute based framework for authenticated encrypted access in clouds," Journal of Parallel and Distributed Computing, Vol.135, pp.1-20, 2020.

상세보기
L. Xu, C. Y. Weng, L. P. Yuan, M. E. Wu, R. Tso, and H. M. Sun, "A shareable keyword search over encrypted data in cloud computing," The Journal of Supercomputing, Vol.74, No.3, pp.1001-1023, 2018.

상세보기
B. U. Pagel, H. W. Six, H. Toben, and P. Widmayer, "Towards an analysis of range query performance in spatial data structures," Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of Database Systems, pp.214-221, 1993.
P. Wang and C. V. Ravishankar, "Secure and efficient range queries on outsourced databases using R-trees," In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp.314-325, 2013.
B. Wang, Y. Hou, M. Li, H. Wang, and H. Li, "Maple: Scalable multi-dimensional range search over encrypted cloud data with tree-based index," ACM symposium on Information, Computer and Communications Security, pp.111-122, 2014.
H. I. Kim, S. T. Hong, and J. W. Chang. "Hilbert curve-based cryptographic transformation scheme for spatial query processing on outsourced private data," Data & Knowledge Engineering, Vol.104, pp.32-44, 2016.

상세보기
H. J. Kim, H. I. Kim, J. W. Chang, "Secure Range Query Processing Algorithm on Outsourced Database Environment," The Journal of Korean Institute of Next Generation Computing, Vol.12, No.4, 2016, pp.71-88.
P. Paillier, "Public-key cryptosystems based on composite degree residuosity classes," In International Conference on the Theory and Applications of Cryptographic Techniques, pp.223-238, 1999.
Y. Watanabe, J. Shikata, and H. Imai, "Equivalence between semantic security and indistinguishability against chosen ciphertext attacks," International Workshop on Public Key Cryptography, Springer, Berlin, Heidelberg, 2003.
B. K. Samanthula, Y. Elmehdwi, and W. Jiang, "K-nearest neighbor classification over semantically secure encrypted relational data," IEEE Transactions on Knowledge and Data Engineering, Vol.27, No.5, pp.1261-1273, 2014.

상세보기
C. M. Schneider, A. A. Moreira, J. S. Andrade, S. Havlin, and H. J. Herrmann, "Mitigation of malicious attacks on networks," Proceedings of the National Academy of Sciences, Vol.108, No.10, pp.3838-3841, 2011.
R. Cramer and I. B. Damgard, "Secure multiparty computation," Cambridge University Press, 2015.
A. C. Yao, "How to Generate and Exchange Secrets," In 27th Annual Symposium on Foundations of Computer Science, IEEE pp.162-167, 1986.
"GMP ≪Arithmetic without limitations≫" The GNU Multiple Precision Arithmetic Library [Internet], https://gmplib.org/

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증