[논문]버킷인덱스와 블룸필터를 이용한 범위형 의료정보 암호화기법

김창규; 김정태; 유천영; 김지홍

doi:10.6109/jkiice.2011.15.2.371

버킷인덱스와 블룸필터를 이용한 범위형 의료정보 암호화기법
A Mechanism of Medical Data Encryption Method Using Bucket Index and Bloom filter with the range property. 원문보기

한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences, v.15 no.2, 2011년, pp.371 - 381

김창규 (동의대학교 정보통신학과) , 김정태 (목원대학교 전자공학과) , 유천영 (세명대학교 정보통신학부) , 김지홍 (세명대학교 정보통신학부)

초록
AI-Helper

최근 데이터베이스내의 개인정보의 유출이 사회적으로 이슈가 되고 있다. 개인의 민감한 정보를 보호하기 위한 최선의 방법은 데이터 암호화이다. 그러나 데이터를 암호화하면 질의어 처리가 어렵게 된다. 그러므로 데이터베이스를 보호하고 질의어 처리를 효율적으로 하기 위한 많은 방법들이 제안되고 있다. 본 논문에서는 기존의 연구에 대한 방법을 분석하고, 의료정보 데이터베이스내의 범위특성을 가진 데이터를 암호화하기 위한 방안으로서 버킷 방식과 블룸필터 방식을 이용한 복합적인 방법을 제안하였다. 버킷방식만을 적용한 경우에 비하여 본 논문에서 제안한 버킷방식과 블룸필터방식을 융합하여 적용한 경우에는 버킷의 개수를 늘일 수 있고, 이에 따른 사용자 데이터의 분포 노출을 방지할 수 있으며, 결과적으로 검색속도를 높일 수 있음을 알 수 있다.

Abstract ▼ AI-Helper

Recently, there are some social issues that personal sensitive data in database were let out. The best method to protect these personal sensitive data is used by the database encryption method. But the encrypting database makes the query difficult. So, there are a lot of study to protect the database and increase the query efficiency as well. In this paper, we analysed recent research trend to protect the sensitive data and propose the combined method using buckets and the bloom filter for the medical database with range property. Compared to bucket index model, the proposed method can increase bucket index value and protect data distribution exposure. We can estimate that this proposed method can improve searching time and efficiency.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

버킷화 과정에 대한 버킷의 개수와 성능과의 관계를 분석한 논문은 다수 있지만, 버킷의 개수와 보안과의 관계를 정밀하게 분석한 논문은 Hore가 작성한 논문이 유일하다[9]. 논문에서는 버킷 값을 통한 데이터의 누출을 방지하기 위하여, 범위질의어에 대한 최적 버킷화 알고리즘(Query Optimal Bucketization Algorithm)을 제안하였다.
본 논문에서는 버킷방식과 블룸필터 방식을 혼용하여 범위 데이터에 대한 검색방법을 제안하고 검토하였다.

제안 방법

4.1절에서 범위형 데이터에 대한 튜플 암호화와 함께, 버킷인덱스만을 사용한 경우와 4.2절에서 버킷인덱스와 블룸필터를 적용한 경우를 살펴보았다. 버킷 인덱스만 사용하였을 경우에는 버킷의 개수를 증가시키면 성능이 향상되는 반면, 데이터 분포에 대한 노출 현상이 증가된다.
를 최소화하는 알고리즘이다. 결국 버킷별 크기를 가변적으로 구성하여, false positive의 개수를 최소화하는 방법을 제안하였다. 이와 더불어 최적 버킷화 과정을 거친 버킷 구조에 대해 표준편차와 엔트로피를 최대화함으로서, 공격에 강한 알고리즘을 제안하였다.
이와 더불어 최적 버킷화 과정을 거친 버킷 구조에 대해 표준편차와 엔트로피를 최대화함으로서, 공격에 강한 알고리즘을 제안하였다. 그러나 본 논문에서는 버킷화 과정을 거친 결과에 대해 블룸필터에 다시 적용함으로서, 버킷의 분포를 공격자가 알 수 없도록 제안한다.
두 개의 서버 간에는 일종의 장벽이 설치되어 서로 통신할 수 없도록 구성된다. 논문에서는 수평 단편화와 수직 단편화 방법을 적용하여 두 개의 DB 서버로 분리 저장하는 방법을 제안하였다.
일반적으로 암호화된 데이터에 대한 검색을 위하여 버킷인덱스만을 사용하는 경우에는 버킷 인덱스 값으로 암호화된 정보를 개략적으로 짐작할 수 있다는 단점이 있다. 따라서 본 논문에서는 버킷의 개수를 증가시켜 검색성능을 높이고, 데이터 분포노출을 방지하기 위하여 다시 블룸필터를 적용하는 방법을 사용하였다.
일반적으로 암호화된 데이터에 대한 검색을 위하여 버킷인덱스만을 사용하는 경우에는 버킷 인덱스 값으로 암호화된 정보를 개략적으로 짐작할 수 있다는 단점이 있다. 따라서 본 논문에서는 버킷의 개수를 증가시켜 검색성능을 높이고, 데이터 분포노출을 방지하기 위하여 다시 블룸필터를 적용하는 방법을 사용한다.
즉, 버킷의 수를 증가시킨다는 것은 보다 적은 구간단위로 요소들을 묶을 수 있기 때문이다. 따라서 본 논문에서는 이러한 범위형 데이터를 다시 블룸필터에 적용하여, 블룸필터값 만을 저장함으로서, 특정인의 신체 정보가 노출되지 않도록 한다.
복호된 평문데이터로부터, 질의어에 해당되는 적합한 결과들을 추출하여 사용자에게 응답한다.
본 논문에서는 버킷 방식에서의 버킷을 검색어로 사용하기 때문에 블룸필터의 false positive 확률을 적용시키기 위하여, 요소의 개수 n 대신에 버킷의 개수 b를 대입하고, 전개하면 다음 식과 같다.
위의 데이터베이스내의 정보특성에 따라, 본 연구에서는 문자형 데이터인 경우에는 범위형과 문장형을 다루며, 숫자형 데이터인 경우에는 범위형 숫자데이터에 국한하여 의료정보 데이터베이스를 보호하는 방안을 제시한다.
결국 버킷별 크기를 가변적으로 구성하여, false positive의 개수를 최소화하는 방법을 제안하였다. 이와 더불어 최적 버킷화 과정을 거친 버킷 구조에 대해 표준편차와 엔트로피를 최대화함으로서, 공격에 강한 알고리즘을 제안하였다. 그러나 본 논문에서는 버킷화 과정을 거친 결과에 대해 블룸필터에 다시 적용함으로서, 버킷의 분포를 공격자가 알 수 없도록 제안한다.

대상 데이터

본 제안방식을 설명하기 위하여 다음과 같이 범위형 데이터로 구성된 간단한 데이터베이스를 예로 사용하였다. 먼저 범위형 숫자데이터에 해당되는 신장과 체중, 범위형 문자데이터에 해당되는 혈액형은 각각 구간으로 표현되는 버킷으로 분류하고, 이를 블룸필터에 적용한다.

이론/모형

마지막으로 데이터베이스의 암호화와 함께, 이를 보완하기 위한 방법으로 키워드 검색을 위한 블룸필터(bloom filter) 방식을 사용할 수 있다. 블룸필터 방식은 m 비트로 구성된 필터를 사용하며, n개의 키워드 요소에 대하여 k 개의 해쉬 함수 결과에 따라 해당 비트를 “1”로 설정하는 방식이다.

성능/효과

4.1절에서 살펴본 바와 같이 버킷방식의 경우에는 버킷의 개수를 증가시키면 false positive 확률이 낮아질 뿐 아니라, 데이터베이스 서버와 클라이언트간의 통신양이 줄어들고, 클라이언트에서 복호하여야 할데이터 개수가 급격히 줄어들기 때문에 검색성능이 향상됨을 알 수 있다. 일반적으로 암호화된 데이터에 대한 검색을 위하여 버킷인덱스만을 사용하는 경우에는 버킷 인덱스 값으로 암호화된 정보를 개략적으로 짐작할 수 있다는 단점이 있다.
즉, 서버로부터 과도한 암호화된 데이터를 수신하면, 이를 복호하는데, 많은 시간이 소요된다. 결과적으로 본 논문에서 주장하는 바와 같이 버킷에 대한 정보 노출을 방지하기 위하여 블룸필터에 적용하고, 이는 곧 버킷의 개수를 증가시켜서 (2)번 복호화 과정의 속도를 높일 수 있게 된다. 결국 버킷의 수를 l배 증가시키면, 복호화시간은 1/l배로 단축되며, 복호화 성능은 l배로 향상된다.
버킷 값을 이용한 튜플 암호화 방식을 적용하는 경우에는 사용자의 신장 정보에 대한 통계적인 노출을 방지하기 위하여 8등급 데이터(표6)를 사용하는 것보다 대부분 4등급 데이터(표7)를 사용한다. 그러나 버킷 방식에 블룸필터를 적용한 본 논문에서의 제안방식을 사용하는 경우에는 8등급 이상으로 세분화된 버킷 방식을 사용할 수 있다. 왜냐하면 버킷 값을 블룸 필터에 적용함으로서, 사용자의 정보가 노출되지 않으며, 필요한 범위의 false positive를 보장할 수 있기 때문이다.
버킷의 개수가 증가되면, false positive 확률이 낮아질 뿐 아니라, 데이터베이스 서버와 클라이언트간의 통신양이 줄어들고, 클라이언트에서 복호하여야 할 데이터 개수가 급격히 줄어들기 때문에 검색성능이 향상됨을 알 수 있다. 일반적으로 암호화된 데이터에 대한 검색을 위하여 버킷인덱스만을 사용하는 경우에는 버킷 인덱스 값으로 암호화된 정보를 개략적으로 짐작할 수 있다는 단점이 있다.
본 논문에서 살펴본 바와 같이 블룸필터의 크기 m, 해쉬함수의 개수 k, 버킷의 개수 b를 이용하여 false positive 확률을 조절할 수 있다. 버킷의 개수를 2배로 증가시키면, 복호화시간은 2배로 단축시키며, 복호화 성능은 2배로 향상된다.
이와 같은 결과를 통하여, 버킷방식만을 적용한 경우에 비하여 버킷방식과 블룸필터방식을 적용한 경우에는 버킷의 개수를 늘일 수 있고, 이에 따른 사용자 데이터의 분포 노출을 방지할 수 있으며, 결과적으로 검색속도를 높일 수 있음을 알 수 있다.
이를 블룸필터에 적용하여 false positive 확률을 적절히 선택함으로서, 성능과 보안간의 절충점을 찾을 수 있다. 이와 같은 결론은 보안을 중요시 하는 환경에서는 버킷의 개수를 증가시킴과 동시에, 비교적 높은 false positive 확률을 선택하고, 성능을 우선시하는 환경에서는 버킷의 개수를 증가시킴과 동시에 상대적으로 낮은 false positive 확률을 선택할 수 있다.
4장에서는 제안한 방법에 대한 이론적인 분석을 한다. 제안한 방법인 버킷(Bucket) 방식과 블룸필터 방식을 혼합한 적용 방식의 성능이 우수함을 증명한다. 마지막으로 5장에서 결론으로 마무리한다.

후속연구

따라서 본 논문에서는 비교적 간단한 방법으로 버킷 방식을 블룸필터 방식에 이론적으로 적용하였으나, 이러한 이론을 기반으로 범위형 데이터 보안을 위한 방안으로서 적용가능하며, 향상된 데이터베이스 보안에 적용될 수 있을 것으로 판단된다. 향후에는 문장형 데이터를 포함한 블룸 필터를 의료 데이터베이스에 적용하기 위한 연구를 진행할 예정이다.
향후에는 문장형 데이터를 포함한 블룸 필터를 의료 데이터베이스에 적용하기 위한 연구를 진행할 예정이다. 이러한 이론을 기반으로 하여 데이터베이스의 보안기능을 유지하며, 검색성능을 향상시키기 위한 기초연구로서 활용될 수 있을 것으로 기대된다.
따라서 본 논문에서는 비교적 간단한 방법으로 버킷 방식을 블룸필터 방식에 이론적으로 적용하였으나, 이러한 이론을 기반으로 범위형 데이터 보안을 위한 방안으로서 적용가능하며, 향상된 데이터베이스 보안에 적용될 수 있을 것으로 판단된다. 향후에는 문장형 데이터를 포함한 블룸 필터를 의료 데이터베이스에 적용하기 위한 연구를 진행할 예정이다. 이러한 이론을 기반으로 하여 데이터베이스의 보안기능을 유지하며, 검색성능을 향상시키기 위한 기초연구로서 활용될 수 있을 것으로 기대된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	클라이언트 모듈에 있는 메타시스템은 어떤 역할을 하는가?	그림1에서 클라이언트 모듈에 있는 메타시스템이란 사용자의 평문 질의어를 암호화된 DB 서버에서 수행할 수 있도록 질의어를 변환시키는 역할을 한다.
	데이터베이스 암호화 방식은 어떻게 구분되는가?	데이터베이스 암호화 방식으로는 레코드 단위, 튜플 단위, 속성 단위의 암호화 방식으로 구분할 수 있다. 일반적으로 속성단위의 암호화방식은 민감한 데이터만을 암호화할 수 있는 반면에 암호화를 하기 위해 너무 많은 패딩이 필요하다는 단점을 가지고 있다.
	데이터베이스 암호화 방식 중 블록 단위의 암호화 방식의 단점은?	일반적으로 속성단위의 암호화방식은 민감한 데이터만을 암호화할 수 있는 반면에 암호화를 하기 위해 너무 많은 패딩이 필요하다는 단점을 가지고 있다. 반면에 블록단위의 암호화 방식의 경우에는 블록 내에 실제 필요한 데이터는 일부에 해당되기 때문에 DB 서버와 클라이언트 간의 통신트래픽이 증가하고, 클라이언트에서 복호 처리할 데이터양이 크게 증가한다. 튜플 방식의 암호화 방식은 해당 튜플 전체를 복호하고, 다시 필요한 부분만을 선택하여야 한다는 단점이 있기 때문에 버킷 등을 이용한 보완방법이 많이 사용되고 있다.

참고문헌 (10)

Hakan Hacig？m？s, Bala Iyer, and Shrad Mehrotra, "Providing database as a service", In Proc, of the 18th International Conference on Data Engineering, San Jose, California, USA, IEEE Computer Society, pp.21-28., 2002.
Hakan Hacig？m？s, Bala Iyer, Chen Li, and Shrad Mehrotra, "Executing SQL over encrypted data in the database service provider model", In Proc. of the ACM SIGMOD, pp.45-49, 2002.
Ernesto Damiani, S.De Capitani di Vimercati, Sushi Jajordia, "Balancing confidentiality and efficiency in untrusted relational DBMSs", In Jajodia, S., Atluri, V., Eds., Proc. of the 10th ACM Conference on Computer and Communications Security(CCS03), Washington, DC, USA, ACM, pp.12-21, 2003.
Hakan Hacig？m？s, Bala Iyer, and Shrad Mehrotra, "Efficient exeurtion of aggregation queries over encrypted relational databases", In Lee, J., li, J. Wudhang, K., and Lee, D., Eds., Proc. of the 9th International Conference on Database Systems for Advanced Applications, Volume 2973 of Lecture Notes in Computer Science, Jeju Island, Korea, Springer, pp.123-132, 2004.
Aggarwal, Gagan and Bawa, Mayank and Ganesan, Prasanna, "Two can keep a secret: a distributed architecture for secure database services", In Proc. of the Second Biannual Conference on Innovative Data Systems Research (CIDR 2005), Asilomar, CA, pp, 34-42, 2005.
Hakan Hacig？m？s, Bala Iyer, Chen Li, and Shrad Mehrotra, "Executing SQL over encrypted data in the database service provider model", In Proc. of the ACM SIGMOD 2002, Madison, Wisconsin, USA. ACM Press, pp,89-96, 2002.
Rakesh Agrawal, Jerry Kiernan, Ramakrishnan Srikant, Yirong Xu, "Order preserving Encryption for numerical Data", in Weikum, G., Konig, A., and Debloch,s., Eds., Proc. of the ACM SIGMOD 2004, Paris, France. ACM, pp.78-84, 2004.
Andrei Broder, Michael Mitzenmacher, "Network Applications of Bloom Filters:", A Survey. Internet Math. Volume 1, Number 4, pp,89-95, 2003.
Bijit Hore, Sharad Mehrotra, Gene Tsudik, "A Privacy-Preserving Index for Range Queries", Proceeding of the 30th VLDB Conference, Toronto, Canada, pp,103-109, 2004.
Rafael P. Laufer, Pedro B. Velloso, and Otto Carlos M. B. Duarte, "Generalized Bloom Filters, Technical Report", GTA-05-43, COPPE/UFRJ, September, pp.143-150, 2005.

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증