Earticle

초록

영어

In this paper, we deal with a method to securely process a query to a database outsourced to a remote server. In particular we are interested in a wildcard query in which a database query statement contains a wildcard character. Moreover, we consider a setting where users’ data are very sensitive (e.g., medical information) so that they should be handled very carefully in the light of security. To this end, we use a fully homomorphic encryption scheme as a baseline encryption. Together with this encryption scheme, our basic idea to the wildcard query problem is to segment an input string as Τ- gram and to represent the Τ- gram into the correspnong polynomial Q Τ(x) . Later a user sends a wildcard pattern including p , then the server evaluate the polynomial as Q Τ(p) , and so if the evaluation result is equal to 0, then it implies that the string involves the pattern p as a substring. All computations are performed on encryptions so that we can guarantee that it is as secure as the baseline encryption scheme applied to the protocol. Finally our construction only requires multiplicative depth O (log2k) where k is the maximum length of strings.

한국어

본 논문에서는 사용자가 원격 서버에 데이터베이스를 아웃소싱 (Outsourcing)한 후, 안전하게 쿼리 (Query)하는 기법에 대한 것으로 특히 쿼리문 (Query Statement)이 와일드카드 문자 (Wildcard Character)를 포함한 쿼리를 안전하게 처리하는 방법을 다룬다. 이러한 안전한 와일드카드 쿼리 문제 를 해결하기 위하여 서버의 데이터베이스에 저장할 문자열을 길이 Τ의 부분문자열로 분할하여 Τ- gram 을 만들고 이것을 다항식으로 확장하는 방식을 핵심 아이디어로 한다. 좀 더 구체적으로, 서버에 저장하는 문자열을 Τ- gram 의 다항식 Q Τ(x)로 표현한 후 와일드카드 쿼리의 조건문에 포함 된 문자열 p를 근 (Root)으로 다항식의 값을 계산하여 결과가 Q Τ(p) = 0 이면 주어진 문자열이 와일 드카드 패턴에 있는 문자열 p를 포함하는 것으로 판단한다. 데이터베이스에 저장된 데이터가 매우 민감한 경우를 고려하여 기반암호기법으로 암호화된 상태에서 산술연산을 지원하는 완전동형암호 (Fully Homomorphic Encryption)를 사용한다. 동형암호의 특성을 활용하여 모든 연산을 암호화된 상 태에서 수행할 수 있어 기반암호기법에서 제공하는 수준의 안전성을 보장할 수 있고, 프로토콜 수행 을 위한 Multiplicative Depth가 기껏해야 O (log2 k) 로서 효율적이다, 여기서 k 는 저장된 문자열의 길이이다.

목차

요약
 Abstract
 1. 서론
  1.1 기여하는 내용
  1.2 제안하는 기법의 핵심 아이디어
  1.3 선행 연구
 2. 정의 및 배경지식
  2.1 표기
  2.2 동형암호
  2.3 Level을 갖는 동형암호 (Leveled FHE)
  2.4 암호문상의 동일성검증 회로 (Equality Test Circuit)
  2.5 시스템 모델
  2.6 안전성 정의
 3. 제안하는 기법
  3.1 배경 지식 및 준비 작업
  3.2 제안하는 기법의 구체적 내용
  3.3 안전성 및 효율성 분석
 4. 결론
 References

키워드

저자

• 김명선 [ Myungsun Kim | Department of Information Security, The University of Suwon ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  보안공학연구논문지 [Journal of Security Engineering]

• 간기

  계간

• pISSN

  1738-7531

• 수록기간

  2005~2017

• 십진분류

  KDC 505 DDC 605