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