1 |
1
하나 이상의 프로세서들, 및상기 하나 이상의 프로세서들에 의해 실행되는 하나 이상의 프로그램들을 저장하는 메모리를 구비한 컴퓨팅 장치에서 수행되는 방법으로서,키 생성 장치로부터 사용자 암호키를 획득하는 단계;기 설정된 이진 트리 내에서 루트 노드로부터 암호화할 데이터에 대응되는 리프 노드까지의 경로 상에 있는 복수의 노드를 포함하는 노드 집합을 생성하는 단계; 상기 사용자 암호키, 상기 암호화할 데이터에 대한 라벨(label) 및 상기 노드 집합에 기초하여 상기 암호화할 데이터에 대한 암호문을 생성하는 단계를 포함하고,상기 암호문을 생성하는 단계는,상기 라벨에 대한 해시 값을 생성하는 단계; 상기 복수의 노드 각각의 식별 정보에 대한 의사 난수(pseudo-random number)를 생성하는 단계; 및상기 해시 값, 상기 의사 난수, 상기 복수의 노드 각각의 상기 이진 트리 내 깊이(depth) 및 상기 사용자 암호키에 기초하여 상기 암호문을 생성하는 단계를 포함하고,상기 암호문은, 상기 복수의 노드 각각에 대한 의사 난수를 상기 해시 값의 지수로 이용하여 산출된 복수의 암호문 원소를 포함하는, 방법
|
2 |
2
삭제
|
3 |
3
삭제
|
4 |
4
청구항 1에 있어서,상기 사용자 암호키는, 아래의 수학식 1[수학식 1](이때, 는 사용자 인덱스, 는 사용자 i에 대한 사용자 암호키, 는 의 원소, 및 는 각각 임의의 정수, p는 소수(prime number))을 만족하고,상기 의사 난수를 생성하는 단계는, 아래의 수학식 2[수학식 2](이때, 는 상기 복수의 노드 중 j(이때, j는 인 정수, 은 상기 이진 트리의 깊이) 번째 노드, 는 에 할당된 노드 식별 정보, 는 에 대한 의사 난수)를 이용하여 상기 복수의 노드 각각에 대한 의사 난수를 생성하는, 방법
|
5 |
5
청구항 4에 있어서,상기 암호문을 생성하는 단계는, 아래의 수학식 3[수학식 3](이때, 는 상기 암호문, 는 상기 복수의 노드 중 j번째 노드의 상기 이진 트리 내 깊이, T는 상기 라벨, 는 상기 해시 값)을 이용하여 상기 암호문을 생성하는, 방법
|
6 |
6
하나 이상의 프로세서들, 및상기 하나 이상의 프로세서들에 의해 실행되는 하나 이상의 프로그램들을 저장하는 메모리를 구비한 컴퓨팅 장치에서 수행되는 방법으로서,복수의 사용자 각각에 대한 사용자 암호키 및 마스터 비밀키를 생성하는 단계;상기 생성된 사용자 암호키를 상기 복수의 사용자 각각의 클라이언트 장치로 제공하는 단계;질의 장치로부터 복수의 범위 질의 벡터를 포함하는 질의 벡터 집합을 수신하는 단계;기 설정된 이진 트리, 상기 질의 벡터 집합 및 상기 마스터 비밀키를 이용하여 상기 질의 벡터 집합에 대한 토큰을 생성하는 단계; 및상기 생성된 토큰을 상기 질의 장치로 제공하는 단계를 포함하는, 방법
|
7 |
7
청구항 6에 있어서,상기 토큰을 생성하는 단계는, 상기 이진 트리로부터 상기 복수의 범위 질의 벡터 각각에 대한 커버 노드 집합을 생성하는 단계;상기 커버 노드 집합 각각에 포함된 하나 이상의 노드 각각의 식별 정보에 대한 의사 난수(pseudo-random number)를 생성하는 단계; 및상기 하나 이상의 노드 각각의 상기 이진 트리 내 깊이(depth), 상기 의사 난수 및 상기 마스터 비밀키를 이용하여 상기 복수의 범위 질의 벡터 각각에 대한 부분 토큰을 생성하는 단계를 포함하고,상기 질의 벡터 집합에 대한 토큰은 상기 복수의 범위 질의 벡터 각각에 대한 부분 토큰을 포함하는, 방법
|
8 |
8
청구항 7에 있어서,상기 사용자 암호키는 아래의 수학식 1[수학식 1](이때, 는 사용자 인덱스, 는 사용자 i에 대한 사용자 암호키, 는 의 원소, 및 는 각각 임의의 정수, p는 소수(prime number))을 만족하고,상기 의사 난수를 생성하는 단계는, 아래의 수학식 2[수학식 2](이때, 는 상기 하나 이상의 노드 중 j(이때, j는 인 정수, 은 상기 커버 노드 집합에 포함된 노드의 개수) 번째 노드, 는 에 할당된 노드 식별 정보, 는 에 대한 의사 난수)를 이용하여 상기 의사 난수를 생성하는, 방법
|
9 |
9
청구항 8에 있어서,상기 마스터 비밀키를 생성하는 단계는 아래의 수학식 3[수학식 3](이때, MK는 상기 마스터 비밀키, n은 상기 복수의 사용자의 총수, 는 위수가 p인 순환군(cyclic group) 의 원소)을 이용하여 상기 마스터 비밀키를 생성하고,상기 부분 토큰을 생성하는 단계는, 아래의 수학식 4[수학식 4](이때, 는 범위 질의 벡터 에 대한 부분 토큰, 는 상기 하나 이상의 노드 중 j번째 노드의 상기 이진 트리 내 깊이, 는 상기 순환군 의 생성원, 는 및 을 만족하는 임의의 정수, , 및 는 각각 를 만족하는 임의의 정수)를 이용하여 상기 부분 토큰을 생성하는, 방법
|
10 |
10
하나 이상의 프로세서들, 및상기 하나 이상의 프로세서들에 의해 실행되는 하나 이상의 프로그램들을 저장하는 메모리를 구비한 컴퓨팅 장치에서 수행되는 방법으로서,복수의 범위 질의 벡터를 포함하는 질의 벡터 집합을 생성하는 단계;키 생성 장치로부터 상기 질의 벡터 집합에 대한 토큰을 획득하는 단계; 및상이한 복수의 사용자의 사용자 암호키를 이용하여 암호화된 복수의 데이터 각각에 대한 암호문, 상기 복수의 데이터에 대한 라벨(label) 및 상기 토큰을 이용하여, 상기 복수의 데이터를 포함하는 데이터 집합과 상기 질의 벡터 집합 사이의 매칭 여부를 판단하는 단계를 포함하는, 방법
|
11 |
11
청구항 10에 있어서,상기 복수의 데이터 각각에 대한 암호문은, 상기 라벨에 대한 해시 값, 상기 복수의 데이터 각각에 대하여 기 설정된 이진 트리로부터 생성된 노드 집합에 포함된 복수의 노드 각각의 식별 정보에 대한 의사 난수, 상기 복수의 노드 각각의 상기 이진 트리 내 깊이 및 상기 사용자 암호키에 기초하여 생성되고,상기 토큰은, 상기 복수의 범위 질의 벡터 각각에 대하여 상기 이진 트리로부터 생성된 커버 노드 집합에 포함된 하나 이상의 노드 각각의 식별 정보에 대한 의사 난수, 상기 하나 이상의 노드 각각의 상기 이진 트리 내 깊이 및 마스터 비밀키에 기초하여 생성된 상기 복수의 범위 질의 벡터 각각에 대한 부분 토큰을 포함하는, 방법
|
12 |
12
청구항 11에 있어서,상기 사용자 암호키는 아래의 수학식 1[수학식 1](는 사용자 인덱스, 는 사용자 i에 대한 사용자 암호키, 는 의 원소, 및 는 각각 임의의 정수, p는 소수(prime number))을 만족하고,상기 의사 난수는, 아래의 수학식 2[수학식 2](이때,는 상기 복수의 노드 중 j(이때, j는 인 정수, 은 상기 이진 트리의 깊이) 번째 노드 또는 상기 하나 이상의 노드 중 j(이때, j는 인 정수, 은 상기 커버 노드 집합에 포함된 노드의 개수) 번째 노드, 는 에 할당된 노드 식별 정보, 는 에 대한 의사 난수)를 이용하여 생성되는, 방법
|
13 |
13
청구항 12에 있어서,상기 마스터 비밀키는 아래의 수학식 3[수학식 3](이때, MK는 상기 마스터 비밀키, n은 상기 복수의 사용자의 수, 는 위수가 p인 순환군(cyclic group) 의 원소)을 만족하고,상기 암호문은, 아래의 수학식 4[수학식 4](이때, 는 상기 암호문, 는 상기 복수의 노드 중 j번째 노드의 상기 이진 트리 내 깊이, T는 상기 라벨, 는 상기 해시 값)를 만족하고,상기 부분 토큰은, 아래의 수학식 5[수학식 5](이때, 는 범위 질의 벡터 에 대한 부분 토큰, 는 상기 하나 이상의 노드 중 j번째 노드의 상기 이진 트리 내 깊이, 는 상기 순환군 의 생성원, 는 및 을 만족하는 임의의 정수, , 및 는 각각 를 만족하는 임의의 정수)를 만족하는, 방법
|
14 |
14
청구항 13에 있어서,상기 판단하는 단계는, 상기 복수의 데이터 각각에 대한 암호문을 포함하는 암호문 집합과 상기 질의 벡터 집합에 대한 토큰을 이용하여 임의의 j에 대해 만들 수 있는 각 조합 (이때, , )에 대해 아래의 수학식 6 및 7을 만족하는지 여부를 판단하고, [수학식 6][수학식 7](이때, e는 를 만족하는 겹선형 함수(bilinear map), , 및 는 위수(order)가 소수 p인 순환군(cyclic group))상기 수학식 6 및 7을 만족하는 조합이 존재하는 경우, 상기 질의 벡터 집합과 상기 데이터 집합이 매칭되는 것으로 판단하는, 방법
|
15 |
15
하나 이상의 프로세서;메모리; 및하나 이상의 프로그램을 포함하는 장치로서,상기 하나 이상의 프로그램은 상기 메모리에 저장되고 상기 하나 이상의 프로세서에 의해 실행되도록 구성되며,상기 프로그램은,키 생성 장치로부터 사용자 암호키를 획득하는 단계;기 설정된 이진 트리 내에서 루트 노드로부터 암호화할 데이터에 대응되는 리프 노드까지의 경로 상에 있는 복수의 노드를 포함하는 노드 집합을 생성하는 단계; 및상기 사용자 암호키, 상기 암호화할 데이터에 대한 라벨(label) 및 상기 노드 집합에 기초하여 상기 암호화할 데이터에 대한 암호문을 생성하는 단계를 실행하기 위한 명령어들을 포함하고,상기 암호문을 생성하는 단계는,상기 라벨에 대한 해시 값을 생성하는 단계; 상기 복수의 노드 각각의 식별 정보에 대한 의사 난수(pseudo-random number)를 생성하는 단계; 및상기 해시 값, 상기 의사 난수, 상기 복수의 노드 각각의 상기 이진 트리 내 깊이(depth) 및 상기 사용자 암호키에 기초하여 상기 암호문을 생성하는 단계를 포함하고,상기 암호문은, 상기 복수의 노드 각각에 대한 의사 난수를 상기 해시 값의 지수로 이용하여 산출된 복수의 암호문 원소를 포함하는, 장치
|
16 |
16
삭제
|
17 |
17
삭제
|
18 |
18
청구항 15에 있어서,상기 사용자 암호키는, 아래의 수학식 1[수학식 1](이때, 는 사용자 인덱스, 는 사용자 i에 대한 사용자 암호키, 는 의 원소, 및 는 각각 임의의 정수, p는 소수(prime number))을 만족하고,상기 의사 난수를 생성하는 단계는, 아래의 수학식 2[수학식 2](이때, 는 상기 복수의 노드 중 j(이때, j는 인 정수, 은 상기 이진 트리의 깊이) 번째 노드, 는 에 할당된 노드 식별 정보, 는 에 대한 의사 난수)를 이용하여 상기 복수의 노드 각각에 대한 의사 난수를 생성하는, 장치
|
19 |
19
청구항 18에 있어서,상기 암호문을 생성하는 단계는, 아래의 수학식 3[수학식 3](이때, 는 상기 암호문, 는 상기 복수의 노드 중 j번째 노드의 상기 이진 트리 내 깊이, T는 상기 라벨, 는 상기 해시 값)을 이용하여 상기 암호문을 생성하는, 장치
|
20 |
20
하나 이상의 프로세서;메모리; 및하나 이상의 프로그램을 포함하는 장치로서,상기 하나 이상의 프로그램은 상기 메모리에 저장되고 상기 하나 이상의 프로세서에 의해 실행되도록 구성되며,상기 프로그램은,복수의 사용자 각각에 대한 사용자 암호키 및 마스터 비밀키를 생성하는 단계;상기 생성된 사용자 암호키를 상기 복수의 사용자 각각의 클라이언트 장치로 제공하는 단계;질의 장치로부터 복수의 범위 질의 벡터를 포함하는 질의 벡터 집합을 수신하는 단계;기 설정된 이진 트리, 상기 질의 벡터 집합 및 상기 마스터 비밀키를 이용하여 상기 질의 벡터 집합에 대한 토큰을 생성하는 단계; 및상기 생성된 토큰을 상기 질의 장치로 제공하는 단계를 실행하기 위한 명령어들을 포함하는, 장치
|
21 |
21
청구항 20에 있어서,상기 토큰을 생성하는 단계는, 상기 이진 트리로부터 상기 복수의 범위 질의 벡터 각각에 대한 커버 노드 집합을 생성하는 단계;상기 커버 노드 집합 각각에 포함된 하나 이상의 노드 각각의 식별 정보에 대한 의사 난수(pseudo-random number)를 생성하는 단계; 및상기 하나 이상의 노드 각각의 상기 이진 트리 내 깊이(depth), 상기 의사 난수 및 상기 마스터 비밀키를 이용하여 상기 복수의 범위 질의 벡터 각각에 대한 부분 토큰을 생성하는 단계를 포함하고,상기 질의 벡터 집합에 대한 토큰은 상기 복수의 범위 질의 벡터 각각에 대한 부분 토큰을 포함하는, 장치
|
22 |
22
청구항 21에 있어서,상기 사용자 암호키는 아래의 수학식 1[수학식 1](이때, 는 사용자 인덱스, 는 사용자 i에 대한 사용자 암호키, 는 의 원소, 및 는 각각 임의의 정수, p는 소수(prime number))을 만족하고,상기 의사 난수를 생성하는 단계는, 아래의 수학식 2[수학식 2](이때, 는 상기 하나 이상의 노드 중 j(이때, j는 인 정수, 은 상기 커버 노드 집합에 포함된 노드의 개수) 번째 노드, 는 에 할당된 노드 식별 정보, 는 에 대한 의사 난수)를 이용하여 상기 의사 난수를 생성하는, 장치
|
23 |
23
청구항 22에 있어서,상기 마스터 비밀키를 생성하는 단계는 아래의 수학식 3[수학식 3](이때, MK는 상기 마스터 비밀키, n은 상기 복수의 사용자의 총수, 는 위수가 p인 순환군(cyclic group) 의 원소)을 이용하여 상기 마스터 비밀키를 생성하고,상기 부분 토큰을 생성하는 단계는, 아래의 수학식 4[수학식 4](이때, 는 범위 질의 벡터 에 대한 부분 토큰, 는 상기 하나 이상의 노드 중 j번째 노드의 상기 이진 트리 내 깊이, 는 상기 순환군 의 생성원, 는 및 을 만족하는 임의의 정수, , 및 는 각각 를 만족하는 임의의 정수)를 이용하여 상기 부분 토큰을 생성하는, 장치
|
24 |
24
하나 이상의 프로세서;메모리; 및하나 이상의 프로그램을 포함하는 장치로서,상기 하나 이상의 프로그램은 상기 메모리에 저장되고 상기 하나 이상의 프로세서에 의해 실행되도록 구성되며,상기 프로그램은,복수의 범위 질의 벡터를 포함하는 질의 벡터 집합을 생성하는 단계;키 생성 장치로부터 상기 질의 벡터 집합에 대한 토큰을 획득하는 단계; 및상이한 사용자 암호키를 이용하여 암호화된 복수의 데이터 각각에 대한 암호문, 상기 복수의 데이터에 대한 라벨(label) 및 상기 토큰을 이용하여, 상기 복수의 데이터를 포함하는 데이터 집합과 상기 질의 벡터 집합 사이의 매칭 여부를 판단하는 단계를 실행하기 위한 명령어들을 포함하는, 장치
|
25 |
25
청구항 24에 있어서,상기 복수의 데이터 각각에 대한 암호문은, 상기 라벨에 대한 해시 값, 상기 복수의 데이터 각각에 대하여 기 설정된 이진 트리로부터 생성된 노드 집합에 포함된 복수의 노드 각각의 식별 정보에 대한 의사 난수, 상기 복수의 노드 각각의 상기 이진 트리 내 깊이 및 상기 사용자 암호키에 기초하여 생성되고,상기 토큰은, 상기 복수의 범위 질의 벡터 각각에 대하여 상기 이진 트리로부터 생성된 커버 노드 집합에 포함된 하나 이상의 노드 각각의 식별 정보에 대한 의사 난수, 상기 하나 이상의 노드 각각의 상기 이진 트리 내 깊이 및 마스터 비밀키에 기초하여 생성된 상기 복수의 범위 질의 벡터 각각에 대한 부분 토큰을 포함하는, 장치
|
26 |
26
청구항 25에 있어서,상기 사용자 암호키는 아래의 수학식 1[수학식 1](는 사용자 인덱스, 는 사용자 i에 대한 사용자 암호키, 는 의 원소, 및 는 각각 임의의 정수, p는 소수(prime number))을 만족하고,상기 의사 난수는, 아래의 수학식 2[수학식 2](이때,는 상기 복수의 노드 중 j(이때, j는 인 정수, 은 상기 이진 트리의 깊이) 번째 노드 또는 상기 하나 이상의 노드 중 j(이때, j는 인 정수, 은 상기 커버 노드 집합에 포함된 노드의 개수) 번째 노드, 는 에 할당된 노드 식별 정보, 는 에 대한 의사 난수)를 이용하여 생성되는, 장치
|
27 |
27
청구항 26에 있어서,상기 마스터 비밀키는 아래의 수학식 3[수학식 3](이때, MK는 상기 마스터 비밀키, n은 상기 복수의 사용자의 수, 는 위수가 p인 순환군(cyclic group) 의 원소)을 만족하고,상기 암호문은, 아래의 수학식 4[수학식 4](이때, 는 상기 암호문, 는 상기 복수의 노드 중 j번째 노드의 상기 이진 트리 내 깊이, T는 상기 라벨, 는 상기 해시 값)를 만족하고,상기 부분 토큰은, 아래의 수학식 5[수학식 5](이때, 는 범위 질의 벡터 에 대한 부분 토큰, 는 상기 하나 이상의 노드 중 j번째 노드의 상기 이진 트리 내 깊이, 는 상기 순환군 의 생성원, 는 및 을 만족하는 임의의 정수, , 및 는 각각 를 만족하는 임의의 정수)를 만족하는, 장치
|
28 |
28
청구항 27에 있어서,상기 판단하는 단계는, 상기 복수의 데이터 각각에 대한 암호문을 포함하는 암호문 집합과 상기 질의 벡터 집합에 대한 토큰을 이용하여 임의의 j에 대해 만들 수 있는 각 조합 (이때, , )에 대해 아래의 수학식 6 및 7을 만족하는지 여부를 판단하고, [수학식 6][수학식 7](이때, e는 를 만족하는 겹선형 함수(bilinear map), , 및 는 위수(order)가 소수 p인 순환군(cyclic group))상기 수학식 6 및 7을 만족하는 조합이 존재하는 경우, 상기 질의 벡터 집합과 상기 데이터 집합이 매칭되는 것으로 판단하는, 장치
|