[논문]암호화된 데이터베이스에서 인덱스 검색 시스템 구현

신승수; 한군희

doi:10.5762/kais.2010.11.5.1653

암호화된 데이터베이스에서 인덱스 검색 시스템 구현
The Implementation of the Index Search System in a Encrypted Data-base 원문보기

한국산학기술학회논문지 = Journal of the Korea Academia-Industrial cooperation Society, v.11 no.5, 2010년, pp.1653 - 1660

초록
AI-Helper

데이터베이스에 저장된 고객 정보들에 대한 유출 사례가 빈번히 발생하고 있다. 악의적인 목적을 갖고 있는 내부 관리자나 외부 공격자로부터 정보를 막기 위해서는 정보를 암호화하여 DB에 저장하는 것이 가장 효율적인 방법 중 하나이다. 암호화를 해 놓고선 DB에 저장만 하여놓고 다른 어떤 활용도 할 수 없다면 차라리 파기하는 편이 나을 것이다. 암호화된 DB 검색시스템이 다양하게 발전하고 있고 여러 분야에서 활용되고 있다. 본 논문에서는 모바일 디바이스에서 신뢰할 수 없는 서버에게 사용자의 정보를 노출하지 않고 암호화된 문서를 검색할 수 있는 스킴을 구현하고 비교분석을 하였다. 구현 결과를 대칭키 기반의 DES, AES, ARIA별로 검색시간을 비교 분석하였다.

Abstract ▼ AI-Helper

The user information stored in database have been leaked frequently. To protect information against malevolent manager on the inside or outside aggressor, it is one of the most efficient way to encrypt information and store to database. It is better to destruct information than not to use encrypted information stored in database. The encrypted database search system is developed variously, and used widely in many fields. In this paper, we implemented the scheme that can search encrypted document without exposing user's information to the untrusted server in mobile device. We compared and analyzed the result embodied with DES, AES, and ARIA based on symmetric key by searching time.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 문에서는 모바일 디바이스에서 사용자의 정보를 노출하지 않고 암호화된 문서를 검색할 수 있는 스킴을 구현하고 실험을 하였다.
Song et al.이 제안한 문서전체 검색 스킴은 데이터의 기밀성을 만족하면서 검색 기능을 지원하는 방법으로 비신뢰적인 서버에게 어떠한 정보도 노출시키지 않는 암호화 기법을 사용하는 것에 관한 시발적인 논문이다. 이것은 증명 가능한 안전성을 제공하며 제한된 검색, 은닉 검색, 질의 분리 기술을 가능하게 한다.

가설 설정

본 구현에서는 각 문서 당 1~3개의 키워드를 포함한다고 가정하였다. 구현에 사용된 전체 키워드 수는 32개, 전체 문서 수는 100개이다.

제안 방법

검색단계 중에서 세 가지 암호모듈을 사용하여 복호화한 과정을 문서 용량별로 효율성을 비교하였다. 각 암호 모듈의 복호화 시간을 비교하기 위해 검색단계에서 각 문서를 수신하고, 복호화하는 시간만을 측정한다. 이때, 사용자가 문서를 요청하고 서버로부터 문서를 수신하는 과정은 복호화 분석시간에 포함하지 않았다.
검색단계 중에서 세 가지 암호모듈을 사용하여 복호화한 과정을 문서 용량별로 효율성을 비교하였다. 각 암호 모듈의 복호화 시간을 비교하기 위해 검색단계에서 각 문서를 수신하고, 복호화하는 시간만을 측정한다.
세 암호 모듈은 암호화에 비해 복호화가 10~20ms정도 시간이 지연되었으며, ARIA의 복호화 시간이 가장 효율적이었다. 검색시간은 사용자가 키워드를 입력하고 문서목록을 수신하는데 걸리는 시간을 측정하였으며, 모바일 디바이스의 특성에 따라 클라이언트를 무선 암호통신으로 구축하였다. 무선 암호통신은 송·수신하는 파일이 커질수록 오류를 제어하는 시간이 길어지고 검색시간이 달라진다.
본 실험에서 암·복호화는 사용자가 문서를 저장하고 문서를 수신하는 과정에서 암·복호화 연산시간만을 각각 파일에 대해 적용하여 실험한 측정값들 중에 다수의 비슷한 시간을 추출하여 평균값을 측정하였다. 검색시간은 여러 사용자를 등록하여 각 사용자에 대하여 파일을 분산시키고, 로그인한 사용자가 키워드를 이용해 검색하고자 할 때, 서버의 데이터베이스에 저장된 모든 사용자들의 문서의 수를 다르게 하였다. 검색시간은 사용자가 키워드를 입력하고 서버로부터 검색된 암호문서의 목록을 수신하는 과정까지 포함한다.
따라서 본 논문에서는 AES, DES, ARIA와 같은 암호모듈을 8비트의 경량화된 시스템에 맞게 구현하고 각각에 대한 암·복호화에 대한 시간 분석과, 검색시간을 측정한다.
먼저, 문서를 암호화하기 위해서 각 문서들은 대칭키 기반 DES-ECB-64, AES-ECB-128와 ARIA-ECB- 128을 이용하여 암호화하였다.
본 논문에서 구현한 암호화된 데이터베이스 검색기법은 서버, 사용자와 같이 두 개체로 나누어져 있으며, 사용자는 모바일 디바이스를 사용하는 모델이다. 그러나 모바일 디바이스는 일반적인 컴퓨터에 비해 제한적인 8비트의 경량화된 시스템이다.
본 실험에서 암·복호화는 사용자가 문서를 저장하고 문서를 수신하는 과정에서 암·복호화 연산시간만을 각각 파일에 대해 적용하여 실험한 측정값들 중에 다수의 비슷한 시간을 추출하여 평균값을 측정하였다.
사용자가 세 모듈을 사용해 암호화된 문서들을 각각 10개, 50개, 100개씩 저장하고, 서버로부터 암호화된 문서를 검색한 시간을 비교하였다. 검색시간은 사용자가 키워드를 입력하고 서버로부터 문서의 목록을 수신하는 과정과 오류제어를 모두 포함한다.
암호화된 DB에서 대칭키 기반 검색 기법의 효율적인 구현을 DES, AES, ARIA 암호모듈을 적용한 저장단계 및 검색단계를 비교분석하였다.
인덱스 기반의 암호화된 데이터베이스 검색 시스템을 암호모듈 DES, AES, ARIA별로 암호화 속도, 복호화 속도, 검색 속도의 효율성을 비교 분석하기 위해서 데이터베이스를 구축하고, 100개의 문서와 32개의 키워드를 만들었다. 구현 방법은 등록 단계, 로그인 단계, 문서 저장 단계, 문서 검색 단계로 나누어진다.
저장단계 중에서 DES, AES, ARIA 암호 모듈을 사용하여 암호화하는 과정을 문서의 용량별로 효율성을 비교하였다. 각 암호모듈의 암호화 시간을 비교하기 위해 저장단계에서 각 문서를 암호화하는 시간만을 측정하며, 사용자가 서버로 파일을 송신하는 과정은 암호화 분석시간에 포함하지 않았다.

대상 데이터

본 구현에서는 각 문서 당 1~3개의 키워드를 포함한다고 가정하였다. 구현에 사용된 전체 키워드 수는 32개, 전체 문서 수는 100개이다. 표 2는 인덱스 기반의 암호화된 데이터베이스에서 검색 기법을 구현하기 위한 구현 환경이다.

성능/효과

1) 사용자가 ‘암호’라는 키워드를 검색하면, 키워드 목록을 비교하여 8자리의 비트열 00100000를 얻을 수 있다.
저장단계에서는 문서를 송·수신을 제외하고 각 암호 모듈을 적용하여 문서를 암호화하는데 걸린 시간만을 측정하여 암호 모듈의 암호화 시간을 분석했다. 분석 결과 ARIA의 암호화 시간이 가장 효율적이었다. 그러나 경량화된 모바일 디바이스에서는 모바일 디바이스의 환경과 구조에 따라 다소 차이가 있을 수 있다.
분석 결과는 표 5에서처럼 저장된 문서가 10개일 때 약 4ms, 50개일 때 약 6ms, 100개일 때 약 8ms가 걸리는 것으로 나타났다. 암호모듈은 검색 시간에 영향을 주지 않으며, 데이터베이스에 저장된 문서 수가 많을수록 검색 시간이 더 걸린다.
반면에, ARIA는 약 130ms가 증가하여 암호화된 DB 검색 기법의 검색단계에서 가장 효율적이다.세 모듈을 분석한 결과 DES, AES, ARIA 암호모듈은 암호화보다 복호화의 속도가 약 10~20ms 떨어졌다.
검색단계에서는 서버와 사용자의 문서 송·수신을 제외하고 사용자가 문서를 수신하여 문서를 복호화하는 시간만을 측정하였다. 세 암호 모듈은 암호화에 비해 복호화가 10~20ms정도 시간이 지연되었으며, ARIA의 복호화 시간이 가장 효율적이었다. 검색시간은 사용자가 키워드를 입력하고 문서목록을 수신하는데 걸리는 시간을 측정하였으며, 모바일 디바이스의 특성에 따라 클라이언트를 무선 암호통신으로 구축하였다.
1kb의 문서에서는 세 모듈의 속도가 비슷하였고, 50kb 이상의 문서에서는 ARIA의 암호화 속도가 가장 효율적이었다. 표 3은 크기별 각각 5번 실행한 결과를 세 모듈별로 분석한 결과로서, DES는 문서 크기가 50kb당 약 250ms가 증가하였고, AES는 약 400ms가 증가하였다. 반면에, ARIA는 약 120ms가 증가하여 암호화된 DB 검색 기법의 저장단계에서 가장 효율적이다.
1kb의 문서에서는 세 모듈의 속도가 비슷하였고, 50kb 이상의 문서에서는 ARIA의 암호화 속도가 가장 효율적이었다. 표 4는 크기별 각각 5번 실행한 결과를 세 모듈별로 분석한 것으로서, DES는 문서 크기가 50kb당 약 260ms가 증가하였고, AES는 약 430ms가 증가하였다. 반면에, ARIA는 약 130ms가 증가하여 암호화된 DB 검색 기법의 검색단계에서 가장 효율적이다.

후속연구

이것은 증명 가능한 안전성을 제공하며 제한된 검색, 은닉 검색, 질의 분리 기술을 가능하게 한다. 이러한 특징들은 향후 연구되어지는 암호화된 검색 시스템의 안전성에 관한 기술을 제공해 준다. 검색 시 서버가 문서 전체를 계산하는 양과 검색한 문서를 복호화 할 때 사용자의 계산 양이 많이 필요하기 때문에 문서의 주요 키워드들을 뽑아 만든 인덱스나 키워드 필드를 사용하는 것이 훨씬 효율적이다[8, 10].

질의응답

핵심어	질문	논문에서 추출한 답변
	D. Song et al.이 제안한 문서전체 검색 스킴이란?	Song et al.이 제안한 문서전체 검색 스킴은 데이터의 기밀성을 만족하면서 검색 기능을 지원하는 방법으로 비신뢰적인 서버에게 어떠한 정보도 노출시키지 않는 암호화 기법을 사용하는 것에 관한 시발적인 논문이다. 이것은 증명 가능한 안전성을 제공하며 제한된 검색, 은닉 검색, 질의 분리 기술을 가능하게 한다.
	Song 기법의 문제점은?	Song 기법에서는 문서의 양과 키워드의 수에 따라 데이터베이스의 저장 공간이 크게 증가하게 되는 문제점이 있다. 이를 보완하고자, Goh가 블룸필터(Bloom Filter)를 사용하는 검색 기법을 제안하였고, Chang은 서버에 사용자의 정보를 노출시키지 않으면서 서버로부터 저장된 데이터를 검색할 수 있는 모바일환경의 검색 기법을 제안하였다.
	D. Song et al.이 제안한 문서전체 검색 스킴의 특징은?	이 제안한 문서전체 검색 스킴은 데이터의 기밀성을 만족하면서 검색 기능을 지원하는 방법으로 비신뢰적인 서버에게 어떠한 정보도 노출시키지 않는 암호화 기법을 사용하는 것에 관한 시발적인 논문이다. 이것은 증명 가능한 안전성을 제공하며 제한된 검색, 은닉 검색, 질의 분리 기술을 가능하게 한다. 이러한 특징들은 향후 연구되어지는 암호화된 검색 시스템의 안전성에 관한 기술을 제공해 준다.

참고문헌 (10)

Byunghee Lee, yunho Lee, Seokhyang Cho, Seungjoo Kim, Dongho Won, "A Study on the Keyword Search on Encrypted Data using Symmetric Key Encryption," 한국정보보호학회 정보보호학술대회논문집, 2006.
민관겸용 블록 암호 ARIA 알고리즘 명세서, 2004.
김선영, 서재우, 이필중, "검색 가능 암호 기술의 연구 동향", 한국정보보호학회, 2009.
D. Song, D. Wagner, and A. Perrig, "Practical techniques for searches on encrypted data," In Proceedings of IEEE Symposium on Security and Privacy, pp. 44-55. IEEE, May 2000.
Y. C. Chang and M. Mitzenmacher, "Privacy preserving keyword seaches on remote encrypted data," Cryptology ePrint Archive, Report 2004/051, Feb 2004.
P. Golle, J. Staddon, B. Waters, "Secure Conjunctive Keyword Search over Encrypted Data," Proc. of the 2004 Applied Cryptography and Network Security Conference, 2004.
이동훈, "계층적 그룹 DB에서 암호화 기법을 이용한 효율적인 검색 시스템의 설계 및 구현", 정보통신산업진흥원, 2006.
노건태, 정익래, 이동훈, 변진욱, "암호화된 데이터에서의 연산 기술 분류 및 최근 동향 연구", 한국정보과학회 학술발표논문집, 2008.
조상록,"하나로텔.옥션 개인정보 유출사건, 집단분쟁 조정 개시", http://www.itdaily.kr/news/articleView.html?idxno16119 , IT데일리, 2008.
정미경, 송희정, 신승수, 한군희, "암호화된 DB에서 대칭키 기반 검색기법 구현", 한국산학기술학회 춘계학술대회발표논문, 2009.

저자의 다른 논문 :

표제어: 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

연합인증