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 는 저장된 문자열의 길이이다.