| 1 |
1
소셜 네트워크 서비스(SNS) 상에 있는 제1 및 제2 노드들 간의 공통 노드를 비공개적으로 검출하는 공통 노드 검출 서버에서 수행되는 공통 노드 검출 방법에 있어서,(a) 상기 제2 노드의 블룸 필터를 통해 상기 제1 노드에 이웃한 적어도 하나의 이웃 노드를 필터링하여 적어도 하나의 후보 공통 노드를 결정하는 단계; 및(b) 상기 적어도 하나의 후보 공통 노드의 블룸 필터를 통해 상기 제2 노드를 필터링하여 상기 적어도 하나의 후보 공통 노드 중 상기 공통 노드를 최종적으로 결정하는 단계를 포함하고,상기 제1 및 제2 노드들의 블룸 필터 및 상기 제1 노드에 이웃한 적어도 하나의 이웃 노드의 블룸 필터는 동일한 필터 에러 확률을 가지고,상기 필터 에러 확률은 하기 수학식 1을 통해 계산되는 것을 특징으로 하는 공통 노드 검출 방법
|
| 2 |
2
삭제
|
| 3 |
3
제1항에 있어서, 상기 제1 및 제2 노드들의 블룸 필터는외부의 무차별 대입 공격(Brute-Force Attack) 상황에서 상기 필터 에러 확률에 따라 거짓 이웃 노드를 통과시키는 것을 특징으로 하는 공통 노드 검출 방법
|
| 4 |
4
제1항에 있어서, 상기 제1 및 제2 노드들의 블룸 필터 및 상기 제1 노드에 이웃한 적어도 하나의 이웃 노드의 블룸 필터는적어도 하나의 해쉬 함수(Hash Function)를 기초로 형성된 해쉬 테이블을 통해 구현되는 것을 특징으로 공통 노드 검출 방법
|
| 5 |
5
제4항에 있어서, 상기 제1 및 제2 노드들의 블룸 필터 및 상기 제1 노드에 이웃한 적어도 하나의 이웃 노드의 블룸 필터의 사이즈는상기 해쉬 함수의 수, 이웃 노드들의 집합 및 상기 필터 에러 확률을 기초로 결정되는 것을 특징으로 공통 노드 검출 방법
|
| 6 |
6
제1항에 있어서,상기 (a) 단계 전에 상기 소셜 네트워크 서비스의 환경을 기초로 프라이버시 보호 기능과 공통 노드 검출의 정확성 간의 트레이드-오프를 수행하여 상기 블룸 필터의 필터 에러 확률을 결정하는 단계를 더 포함하는 것을 특징으로 하는 공통 노드 검출 방법
|
| 7 |
7
제1항에 있어서, 상기 제1 및 제2 노드들의 블룸 필터 및 상기 제1 노드에 이웃한 적어도 하나의 이웃 노드의 블룸 필터 각각은서로 이웃하는 노드에 대한 정보를 비공개적으로 저장하는 것을 특징으로 하는 공통 노드 검출 방법
|
| 8 |
8
제1항에 있어서, 상기 (a) 단계는상기 제1 또는 제2 노드의 블룸 필터에 적어도 하나의 거짓 이웃 노드를 추가하는 단계를 포함하는 것을 특징으로 하는 공통 노드 검출 방법
|
| 9 |
9
제1항에 있어서, 상기 (a) 단계는상기 제1 및 제2 노드들 중 상대적으로 차수(Degree)가 작은 제1 노드에 이웃한 적어도 하나의 이웃 노드 각각을 상대적으로 차수가 큰 제2 노드의 블룸 필터를 통해 필터링하는 단계를 포함하는 것을 특징으로 하는 공통 노드 검출 방법
|
| 10 |
10
제1항에 있어서,상기 (a) 단계 전에 기 설정된 필터 에러 확률이 존재하면 가변하는 블룸 필터의 사이즈에 따른 임시 필터 에러 확률을 상기 필터 에러 확률과 비교하여, 상기 필터 에러 확률에 적합한 블룸 필터의 사이즈를 결정하는 단계를 더 포함하는 것을 특징으로 하는 공통 노드 검출 방법
|
| 11 |
11
제10항에 있어서, 상기 필터 에러 확률에 적합한 블룸 필터의 사이즈를 결정하는 단계는상기 필터 에러 확률이 상기 임시 필터 에러 확률보다 크면 상기 블룸 필터의 사이즈를 낮추고, 상기 필터 에러 확률이 상기 임시 필터 에러 확률보다 작으면 상기 블룸 필터의 사이즈를 높이는 단계를 포함하는 것을 특징으로 하는 공통 노드 검출 방법
|
| 12 |
12
제11항에 있어서, 상기 필터 에러 확률에 적합한 블룸 필터의 사이즈를 결정하는 단계는상기 필터 에러 확률과 상기 임시 필터 에러 확률을 비교하여 조정된 블룸 필터의 사이즈를 기초로 임시 필터 에러 확률을 다시 산출하고, 상기 필터 에러 확률과 상기 다시 산출된 임시 필터 에러 확률을 비교하여 상기 블룸 필터의 사이즈를 조정하는 과정을 반복하는 단계를 포함하는 것을 특징으로 하는 공통 노드 검출 방법
|
| 13 |
13
소셜 네트워크 서비스(SNS) 상에 있는 제1 및 제2 노드들 간의 공통 노드를 비공개적으로 검출하기 위하여 상기 제2 노드의 블룸 필터를 통해 상기 제1 노드에 이웃한 적어도 하나의 이웃 노드를 필터링하여 적어도 하나의 후보 공통 노드를 결정하는 후보 공통 노드 결정부; 및상기 적어도 하나의 후보 공통 노드의 블룸 필터를 통해 상기 제2 노드를 필터링하여 상기 적어도 하나의 후보 공통 노드 중 상기 공통 노드를 최종적으로 결정하는 공통 노드 결정부를 포함하고,상기 제1 및 제2 노드들의 블룸 필터 및 상기 제1 노드에 이웃한 적어도 하나의 이웃 노드의 블룸 필터는 동일한 필터 에러 확률을 가지고,상기 필터 에러 확률은 하기 수학식 1을 통해 계산되는 것을 특징으로 하는 공통 노드 검출 서버
|
| 14 |
14
제13항에 있어서,상기 소셜 네트워크 서비스의 환경을 기초로 프라이버시 보호 기능과 공통 노드 검출의 정확성 간의 트레이프-오프를 수행하여 상기 블룸 필터의 필터 에러 확률을 결정하는 필터 에러 확률 결정부를 더 포함하는 것을 특징으로 하는 공통 노드 검출 서버
|
| 15 |
15
제13항에 있어서,기 설정된 필터 에러 확률이 존재하면 가변하는 블룸 필터의 사이즈에 따른 임시 필터 에러 확률을 상기 필터 에러 확률과 비교하여, 상기 필터 에러 확률에 적합한 블룸 필터의 사이즈를 결정하는 블룸 필터 사이즈 결정부를 더 포함하는 것을 특징으로 하는 공통 노드 검출 서버
|
