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

서지정보

· 발행기관 : 한국정보처리학회
· 수록지 정보 : 정보처리학회논문지. 컴퓨터 및 통신시스템 / 10권 / 9호 / 243 ~ 250페이지
· 저자명 : 김형진, 장재우

초록

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

영어초록

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

참고자료

· 없음