| 1 |
1
제1 클라우드와, 상기 제1 클라우드와 독립(non-colluding)되는 제2 클라우드를 구축하는 단계;원본 데이터베이스에 저장되는 데이터를 암호화 한 암호화 데이터베이스와, 상기 암호화와 연관되어 생성되는 암호화 공개키를, 상기 제1 클라우드에 유지하는 단계;상기 암호화 공개키에 대응하는 복호화 비밀키를, 상기 제2 클라우드에 유지하는 단계;상기 암호화 공개키를 배포 받은 사용자 단말에서, kNN(k Nearest Neighbor) 질의가 발생되는 경우,상기 제1 클라우드에서, GSPE 프로토콜을 기반으로, 상기 kNN 질의의 지점에 관한 복수의 데이터 E(a)를, 상기 암호화 데이터베이스에서 탐색하여, 상기 제2 클라우드로 전송하는 단계;상기 제2 클라우드에서, 상기 복호화 비밀키를 통해, 상기 복수의 데이터 E(a) 각각을, 복수의 데이터 E'(a)로 복호화하고, 상기 복수의 데이터 E'(a)를 각각 포함하는 노드 그룹을 생성하는 단계;상기 제1 클라우드에서, 정해진 순서에 따라 상기 제2 클라우드로부터 노드 그룹을 수신하고, 상기 노드 그룹에 저장된 데이터 E'(a) 및 상기 데이터 E(a)를 이용한 SM 프로토콜을 기반으로, 상기 제1 클라우드와 상기 제2 클라우드 간의 다자간 계산(SMC, Secure Multiparty Computation)을 수행하는 단계; 및상기 다자간 계산의 수행에 따라, 상기 암호화 데이터베이스로부터 상기 kNN 질의에 대한 결과 데이터를 도출하여 상기 사용자 단말로 제공하는 단계를 포함하는 가블드 회로(GARBLED CIRCUIT) 기반 k-NN 질의 처리 방법
|
| 2 |
2
제1항에 있어서,상기 원본 데이터베이스에 저장된 데이터를, 다수의 속성(attribute) 및 차원(column)으로 분할하여, kd 트리를 구성하는 단계; 및상기 kd 트리를 암호화 한 암호화 kd 트리를, 상기 제1 클라우드에 유지하는 단계;를 더 포함하고,상기 결과 데이터를 도출하여 상기 사용자 단말로 제공하는 단계는,선정된 암호화 연산 프로토콜을 기반으로, 상기 암호화 kd 트리에 근거한, 상기 암호화 데이터베이스 상에서의 상기 kNN 질의를 처리하는 단계를 포함하는 k-NN 질의 처리 방법
|
| 3 |
3
제2항에 있어서,상기 결과 데이터를 도출하여 상기 사용자 단말로 제공하는 단계는,ESSED(Enhanced Secure Squared Euclidean Distance) 프로토콜, GSCMP(Garbled Circuit based Secure Compare) 프로토콜, 및 GSPE(Garbled Circuit based Secure Point Enclosure) 프로토콜 중 어느 하나를, 상기 암호화 연산 프로토콜로 선정하는 단계를 더 포함하는 k-NN 질의 처리 방법
|
| 4 |
4
제2항에 있어서,상기 암호화 연산 프로토콜로서, ESSED 프로토콜이 선정되면,상기 결과 데이터를 도출하여 상기 사용자 단말로 제공하는 단계는,상기 암호화 kd 트리 내 임의의 데이터 쌍에 대한 차원별 거리의 합산을, 2차원 상에서 수행하여, 상기 결과 데이터의 도출을 위한 암호화 데이터 기반 연산 횟수를 감소시키는 단계를 더 포함하는 k-NN 질의 처리 방법
|
| 5 |
5
제2항에 있어서,상기 암호화 연산 프로토콜로서, GSCMP 프로토콜이 선정되면,상기 결과 데이터를 도출하여 상기 사용자 단말로 제공하는 단계는,상기 제1 클라우드와 상기 제2 클라우드 사이에서 난수를 교환하여, 상기 암호화 kd 트리 내 임의의 데이터 쌍에 대한 크기 비교에 따라 반환되는 데이터의 값을 결정하는 단계를 더 포함하는 k-NN 질의 처리 방법
|
| 6 |
6
제2항에 있어서,상기 암호화 연산 프로토콜로서, GSPE 프로토콜이 선정되면,상기 결과 데이터를 도출하여 상기 사용자 단말로 제공하는 단계는,상기 암호화 kd 트리 내 m 차원의 데이터 E(p)가, 상기 kNN 질의와 연관된 질의 영역에 포함되면, 상기 GSPE 프로토콜에 의한 수행 결과로서 'E(1)'을 반환하는 단계; 및상기 데이터 E(p)가, 상기 질의 영역에 포함되지 않으면, 상기 GSPE 프로토콜에 의한 수행 결과로서 'E(0)'을 반환하는 단계를 더 포함하는 k-NN 질의 처리 방법
|
| 7 |
7
삭제
|
| 8 |
8
제1항에 있어서,상기 원본 데이터베이스에 저장된 데이터를, 다수의 속성 및 차원으로 분할하여, kd 트리를 구성하는 단계를 더 포함하고,상기 결과 데이터가 복수로 도출되는 경우,상기 결과 데이터를 도출하여 상기 사용자 단말로 제공하는 단계는,상기 kd 트리 내에서, 상기 복수의 결과 데이터 중 상기 kNN 질의와의 거리가 가까운 순서대로, 정해진 개수의 결과 데이터를 선별하여, 상기 사용자 단말로 제공하는 단계를 포함하는 k-NN 질의 처리 방법
|
| 9 |
9
제1항에 있어서,상기 원본 데이터베이스에 저장된 데이터를, 다수의 속성 및 차원으로 분할하여, kd 트리를 구성하는 단계; 및상기 kd 트리 내에서, 상기 kNN 질의를 기준으로, 상기 결과 데이터와의 거리 보다, 짧은 거리를 갖는 데이터가 존재하는지를 확인하여, 상기 결과 데이터를 검증하는 단계를 더 포함하는 k-NN 질의 처리 방법
|
| 10 |
10
제1항에 있어서,상기 결과 데이터를 도출하여 상기 사용자 단말로 제공하는 단계는,상기 제1 클라우드에서, 암호화 연산 프로토콜을 수행하여 탐색한 노드를 상기 제2 클라우드로 전달하는 제1 단계;상기 제2 클라우드에서, 상기 복호화 비밀키로 상기 노드로부터 획득한 데이터에 대해 암호화 연산 프로토콜을 수행한 결과를 상기 제1 클라우드로 전달하는 제2 단계; 및상기 kNN 질의에 대한 결과가 도출될 때까지, 상기 제1 및 제2 단계를 반복하여, 상기 kNN 질의를 처리하는 단계를 포함하는 k-NN 질의 처리 방법
|
