| 1 |
1
하나 이상의 프로세서들, 및상기 하나 이상의 프로세서들에 의해 실행되는 하나 이상의 프로그램들을 저장하는 메모리를 구비한 컴퓨팅 장치에서 수행되는 방법으로서,제1 사용자의 비밀키를 이용하여 제1 평문을 암호화한 제1 암호문 및 제2 사용자의 비밀키를 이용하여 제2 평문을 암호화한 제2 암호문을 획득하는 단계;상기 제1 사용자에 의해 이용되는 제1 클라이언트 장치 및 제2 사용자에 의해 이용되는 제2 클라이언트 장치로 상기 제1 사용자의 식별 정보 및 상기 제2 사용자의 식별 정보를 제공하는 단계;상기 제1 클라이언트 장치로부터 상기 제1 사용자의 식별 정보, 상기 제2 사용자의 식별 정보 및 상기 제1 사용자의 비밀키를 이용하여 생성된 제1 비교키 엘리먼트를 수신하고, 상기 제2 클라이언트 장치로부터 상기 제1 사용자의 식별 정보, 상기 제2 사용자의 식별 정보 및 상기 제2 사용자의 비밀키를 이용하여 생성된 제2 비교키 엘리먼트를 수신하는 단계; 및상기 제1 비교키 엘리먼트 및 상기 제2 비교키 엘리먼트를 포함하는 비교키를 이용하여 상기 제1 암호문 및 상기 제2 암호문을 암호화된 상태에서 비교하고, 상기 비교 결과에 기초하여 상기 제1 평문 및 상기 제2 평문 사이의 대소를 판단하는 단계를 포함하는, 방법
|
| 2 |
2
청구항 1에 있어서,상기 제1 비교키 엘리먼트는, 상기 제1 사용자의 식별 정보 및 상기 제2 사용자의 식별 정보에 대해 해시 함수(hash function)를 적용한 결과 값과 상기 제1 사용자의 비밀키를 이용하여 생성되고,상기 제2 비교키 엘리먼트는, 상기 제1 사용자의 식별 정보 및 상기 제2 사용자의 식별 정보에 대해 상기 해시 함수를 적용한 결과 값과 상기 제2 사용자의 비밀키를 이용하여 생성되는, 방법
|
| 3 |
3
청구항 2에 있어서,상기 제1 비교키 엘리먼트는, 아래의 수학식 1[수학식 1] (이때, K0는 상기 제1 비교키 엘리먼트, IDj는 상기 제1 사용자의 식별 정보, IDk는 상기 제2 사용자의 식별 정보, sj는 상기 제1 사용자의 비밀키, 는 를 만족하는 해시 함수, 는 위수가 소수 p인 덧셈 군)을 이용하여 생성되고,상기 제2 비교키 엘리먼트는, 아래의 수학식 2[수학식 2] (이때, K1은 상기 제2 비교키 엘리먼트, sk는 상기 제2 사용자의 비밀키)를 이용하여 생성되는, 방법
|
| 4 |
4
청구항 1에 있어서,상기 제1 암호문은, 상기 제1 평문의 각 비트 값에 대한 프리픽스(prefix) 비트 열 및 상기 제1 사용자의 비밀키를 이용하여 상기 제1 평문을 비트 단위로 암호화하여 생성되고,상기 제2 암호문은, 상기 제2 평문의 각 비트 값에 대한 프리픽스 비트 열 및 상기 제2 사용자의 비밀키를 이용하여 상기 제2 평문을 비트 단위로 암호화하여 생성되는, 방법
|
| 5 |
5
청구항 4에 있어서,상기 제1 암호문은, 아래의 수학식 3 내지 5[수학식 3][수학식 4][수학식 5](이때, 는 상기 1 암호문, m은 인 상기 제1 평문, 는 상기 제1 평문의 i 번째 비트 값, 는 상기 제1 평문의 i 번째 비트 값에 대한 프리픽스 비트 열, 는 상기 제1 사용자의 비밀키, H는 를 만족하는 해시 함수, 는 위수가 소수 p인 덧셈 군)을 이용하여 생성되고,상기 제2 암호문은, 아래의 수학식 6 내지 8[수학식 6][수학식 7][수학식 8](이때, 는 상기 제2 암호문, m'은 인 상기 제2 평문, 는 상기 제2 평문의 i 번째 비트 값, 는 상기 제2 평문의 i 번째 비트 값에 대한 프리픽스 비트 열, 는 상기 제2 사용자의 비밀키)을 이용하여 생성되는, 방법
|
| 6 |
6
청구항 5에 있어서,상기 판단하는 단계는, 와 (이때, e는 를 만족하는 겹선형(bilinear) 함수, 는 위수가 소수 p인 덧셈 군, 는 위수가 소수 p인 곱셈 군, K0는 상기 제1 비교키 엘리먼트, K1은 상기 제2 비교키 엘리먼트)가 일치하지 않는 i의 최소 값 i*가 존재하는지 여부를 판단하는 단계; 및상기 최소 값 i*이 존재하고, 와 가 일치하는 경우, 상기 제1 평문이 상기 제2 평문보다 작은 것으로 판단하고, 와 가 일치하지 않거나 상기 최소 값 i*이 존재하지 않는 경우, 상기 제1 평문이 상기 제2 평문보다 크거나 같은 것으로 판단하는 단계를 포함하는, 방법
|
| 7 |
7
하나 이상의 프로세서;메모리; 및하나 이상의 프로그램을 포함하는 장치로서,상기 하나 이상의 프로그램은 상기 메모리에 저장되고 상기 하나 이상의 프로세서에 의해 실행되도록 구성되며,상기 프로그램은,제1 사용자의 비밀키를 이용하여 제1 평문을 암호화한 제1 암호문 및 제2 사용자의 비밀키를 이용하여 제2 평문을 암호화한 제2 암호문을 획득하는 단계;상기 제1 사용자에 의해 이용되는 제1 클라이언트 장치 및 제2 사용자에 의해 이용되는 제2 클라이언트 장치로 상기 제1 사용자의 식별 정보 및 상기 제2 사용자의 식별 정보를 제공하는 단계;상기 제1 클라이언트 장치로부터 상기 제1 사용자의 식별 정보, 상기 제2 사용자의 식별 정보 및 상기 제1 사용자의 비밀키를 이용하여 생성된 제1 비교키 엘리먼트를 수신하고, 상기 제2 클라이언트 장치로부터 상기 제1 사용자의 식별 정보, 상기 제2 사용자의 식별 정보 및 상기 제2 사용자의 비밀키를 이용하여 생성된 제2 비교키 엘리먼트를 수신하는 단계; 및상기 제1 비교키 엘리먼트 및 상기 제2 비교키 엘리먼트를 포함하는 비교키를 이용하여 상기 제1 암호문 및 상기 제2 암호문을 암호화된 상태에서 비교하고, 상기 비교 결과에 기초하여 상기 제1 평문 및 상기 제2 평문 사이의 대소를 판단하는 단계를 실행하기 위한 명령어들을 포함하는, 장치
|
| 8 |
8
청구항 7에 있어서,상기 제1 비교키 엘리먼트는, 상기 제1 사용자의 식별 정보 및 상기 제2 사용자의 식별 정보에 대해 해시 함수(hash function)를 적용한 결과 값과 상기 제1 사용자의 비밀키를 이용하여 생성되고,상기 제2 비교키 엘리먼트는, 상기 제1 사용자의 식별 정보 및 상기 제2 사용자의 식별 정보에 대해 상기 해시 함수를 적용한 결과 값과 상기 제2 사용자의 비밀키를 이용하여 생성되는, 장치
|
| 9 |
9
청구항 8에 있어서,상기 제1 비교키 엘리먼트는, 아래의 수학식 1[수학식 1] (이때, K0는 상기 제1 비교키 엘리먼트, IDj는 상기 제1 사용자의 식별 정보, IDk는 상기 제2 사용자의 식별 정보, sj는 상기 제1 사용자의 비밀키, 는 를 만족하는 해시 함수, 는 위수가 소수 p인 덧셈 군)을 이용하여 생성되고,상기 제2 비교키 엘리먼트는, 아래의 수학식 2[수학식 2] (이때, K1은 상기 제2 비교키 엘리먼트, sk는 상기 제2 사용자의 비밀키)를 이용하여 생성되는, 장치
|
| 10 |
10
청구항 7에 있어서,상기 제1 암호문은, 상기 제1 평문의 각 비트 값에 대한 프리픽스(prefix) 비트 열 및 상기 제1 사용자의 비밀키를 이용하여 상기 제1 평문을 비트 단위로 암호화하여 생성되고,상기 제2 암호문은, 상기 제2 평문의 각 비트 값에 대한 프리픽스 비트 열 및 상기 제2 사용자의 비밀키를 이용하여 상기 제2 평문을 비트 단위로 암호화하여 생성되는, 장치
|
| 11 |
11
청구항 10에 있어서,상기 제1 암호문은, 아래의 수학식 3 내지 5[수학식 3][수학식 4][수학식 5](이때, 는 상기 1 암호문, m은 인 상기 제1 평문, 는 상기 제1 평문의 i 번째 비트 값, 는 상기 제1 평문의 i 번째 비트 값에 대한 프리픽스 비트 열, 는 상기 제1 사용자의 비밀키, H는 를 만족하는 해시 함수, 는 위수가 소수 p인 덧셈 군)을 이용하여 생성되고,상기 제2 암호문은, 아래의 수학식 6 내지 8[수학식 6][수학식 7][수학식 8](이때, 는 상기 제2 암호문, m'은 인 상기 제2 평문, 는 상기 제2 평문의 i 번째 비트 값, 는 상기 제2 평문의 i 번째 비트 값에 대한 프리픽스 비트 열, 는 상기 제2 사용자의 비밀키)을 이용하여 생성되는, 장치
|
| 12 |
12
청구항 11에 있어서,상기 판단하는 단계는, 와 (이때, e는 를 만족하는 겹선형(bilinear) 함수, 는 위수가 소수 p인 덧셈 군, 는 위수가 소수 p인 곱셈 군, K0는 상기 제1 비교키 엘리먼트, K1은 상기 제2 비교키 엘리먼트)가 일치하지 않는 i의 최소 값 i*가 존재하는지 여부를 판단하는 단계; 및상기 최소 값 i*이 존재하고, 와 가 일치하는 경우, 상기 제1 평문이 상기 제2 평문보다 작은 것으로 판단하고, 와 가 일치하지 않거나 상기 최소 값 i*이 존재하지 않는 경우, 상기 제1 평문이 상기 제2 평문보다 크거나 같은 것으로 판단하는 단계를 포함하는, 장치
|
