Module-NTRU 기반 PEKS 방법의 설계 및 구현, 그리고 모바일 환경에서의 응용

Ⅰ. 서 론

우리는 2019년 구글의 양자컴퓨터 개발에 대한 발표를 통해 양자컴퓨터 시대가 멀지 않았음을 알 수 있다[1] . 해당 발표에서 구글은 개발 중인 양자컴퓨터가 슈퍼컴퓨터의 성능을 추월한 양자우위를 달성하였음을 주장한다. 구글은 이러한 양자우위에 대한 증거로 양자데이터에 대한 일관된 양자연산과 실시간으로 의사 난수 양자회로의 결과를 샘플링 하는 계산의 결과를 제시한다[1][2]. 현재 가장 계산능력이 뛰어난 슈퍼컴퓨터의 해당 계산 결과는 1만 년이 걸리는 데 비해 발표된 양자컴퓨터는 3분 20초 만에 연산할 수 있음을 보인다. 이러한 양자컴퓨터의 계산 능력 향상으로 인해 앞으로 컴퓨터의 계산능력이 중요한 역할을 하는 많은 분야에서 빠른 발전이 예상되지만, 암호화 알고리즘에 대한 공격 위험 또한 증가할 것이다. 예를 들어 실제 소인수 분해를 빠르게 처리할 수 있는 양자알고리즘인 Shor’s algorithm[3]은 공개키 암호 방식을 쉽게 깰 수 있는 알고리즘이다. 하지만 현재 충분히 큰 수에 대해서 Shor’s algorithm을 적용할 수 있는 양자컴퓨터가 없으므로 소인수 분해를 이용한 RSA와 같은 공개키 기반 암호는 안전하다고 여겨진다. 그러나 양자컴퓨터가 사용된다면 Shor’s algorithm을 이용하여 공개키 기반의 암호는 무력화된다.

양자컴퓨터의 상용화가 점점 다가옴에 따라 생겨나는 보안 위협에 대해 현재 사용되는 암호화 기법들의 안전성 연구가 진행되고 있으며 안전하지 않은 암호화 기법들의 대응책이 연구되고 있다. 양자컴퓨터의 계산 능력으로도 다항 시간 내에 공격을 성공하지 못하도록 하는 암호를 양자내성을 지닌 암호 알고리즘이라 한다. 양자컴퓨터가 다항시간 내에 풀 수 없는 수학적 문제를 이용한 많은 양자내성 암호화 기반 문제 관련 연구가 진행 중이며 [4]-[14], 미국 국립 표준연구소(NIST)[15]의 양자내성 암호에 대한 표준화 작업도 진행 중이다.

본 연구에서는 양자내성 기반 문제인 MNTRU(Module-NTRU)[16] 연구에서 MNTRU를 이용해 설계된 IBE(Identity-Based Encryption) 알고리즘의 각 기능을 이용하여 현재 제안된 기법 중에 양자내성이 없는 암호화 알고리즘인 PEKS(Public-Key Encryption with Keyword Search)를 개선한 방법을 설계한다.

양자내성 기반 문제인 MNTRU를 기반으로 설계된 IBE의 각 기능인 Setup, 키 생성, Extract, 암호화, 복호화 과정을 이용해 본 연구에서 제안하는 PEKS의 각 기능을 설계한다. 설계된 알고리즘은 이메일 송수신 시나리오에 대해 랩톱에서 구현한 후 기존에 제안되었던 PEKS 기법들과 수행 시간 및 보안성 측면에서 비교한다. 측정에 사용된 랩톱의 환경은 MacBook Pro(15inch 2017) 모델 2.9GHz 쿼드코어 intel Core i7이다. 랩톱에서 측정한 결과 중 암호화 시간은 7.378ms, 키워드 검색 테스트 시간은 2.79ms로 측정되었다. 또한 모바일 구현환경인 S20 Ultra+에서 키 생성 수행시간은 126689ms이며 태블릿 환경인 Galaxy tab S7+에서 키 생성 수행시간은 91971.3ms이다. 키 생성은 초기에 한 번만 진행되기 때문에 감내할만한 수준이다. 암호화, 트랩도어 키 생성, 키워드 검색 테스트, 복호화 과정에서는 모바일에서 가장 느린 복호화가 2258.2ms, 태블릿에서 2415.9ms로 측정되었으며 모바일에서 가장 빠른 키워드 검색 테스트가 134.6ms로 태블릿에서 140.7ms로 측정되었다.

본 논문의 나머지 구성은 다음과 같다. 2장에서는 사전 지식에 관해서 설명한다. 3장에서는 관련 연구에 대해 서술한다. 4장에서는 본 연구의 목적에 관해서 서술한다. 5장의 실제 설계된 PEKS에 대해서 설명한다. 6장에서는 랩톱에서 측정된 결과를 바탕으로 기존 제안되었던 PEKS와의 비교를 진행하고 결과를 분석한다. 7장에서는 결론에 관해 설명한다.

Ⅱ. 사전 지식

2.1 PEKS

PEKS[17]-[19] 알고리즘은 암호화된 평문들에 대해서 복호화 과정 없이 특정 키워드를 포함하는 암호문을 찾아낼 수 있는 암호화 기법이다. 해당 기법에서 키워드 검색을 하기 위해 생성되는 키를 트랩도어 키라 한다. 검색을 원하는 키워드를 통해 트랩도어 키를 생성하게 되고 해당키를 통해 암호문에 서의 검색 과정을 수행한다. PEKS의 이메일 전송 시나리오는 그림 1과 같이 송신자(Sender), 수신자(Receiver), 서버(Server)로 구성된다. 송신자와 수신자는 메일을 주고받는 역할을 담당하며 서버는 메일을 저장, 전달하고 저장된 메일에 대한 키워드 검색을 수행하는 역할을 담당한다. 그림 1의 1번 과정에서 수신자는 키 생성 과정을 수행하여 PEKS 공개키(PK)와 PEKS 비밀키(SK)를 생성한 후 2번 과정을 통해 서버로 공개키를 전달한다. 송신자는 3, 4, 5번 과정을 통해 메일을 작성한 후 수신자의 공개키를 서버로부터 받아 메일을 암호화한 후 서버로 해당 암호문을 전송한다. 서버는 송신자로부터 전달받은 암호문을 서버 내에 저장한다. 수신자는 검색을 원하는 키워드를 이용해 6번 과정을 거쳐 트랩도어 키를 생성한 후 서버로 전송한다. 서버는 전달받은 트랩도어 키를 이용해 서버 내에 저장되어있던 암호문을 검색하게 되고 수신자가 검색을 원하는 키워드가 존재하는 암호문을 찾은 후 해당 암호문만을 수신자에게 전달한다. 이 과정에서 수신자는 서버가 트랩도어 키를 이용해 키워드 검색만할 수 있도록 제한하게 되고 서버는 키워드 검색과 암호문 전달 외에는 평문에 대해 어떠한 정보도 알 수 없다. 이를 통해 송신자와 수신자는 메일 내용 유출에 대한 안전성을 보장받으면서 메일을 송수신할 수 있다. 9번 과정을 통해 수신자는 전달받은 암호문에 대해 복호화 과정을 진행한다.

Fig. 1.

PEKS scenario

PEKS는 키 생성, 트랩도어 키 생성, 암호화, 키워드 검색 테스트, 복호화로 이루어진 다섯 단계로 진행된다. 표 1은 다섯 가지 과정의 입력과 출력값을 보여준다. 키 생성 과정에서는 보안 파라미터를 통해 PEKS를 진행하기 위한 공개키와 비밀키를 생성한다. 트랩도어 키 생성 과정에서는 PEKS의 비밀키와 검색을 원하는 키워드를 입력으로 받아 트랩도어 키를 생성한다. 암호화 과정에서는 평문을 PEKS 공개키를 이용해 암호화하여 암호문을 결과값으로 반환한다. 키워드 검색 과정에서는 PEKS 공개키와 암호문, 트랩도어 키를 이용하여 진행하며 결과값으로 키워드가 존재하는지에 대한 검사 결과를 반환한다. 마지막으로 키워드가 존재하는 암호문과 PEKS 비밀키를 이용해 암호문을 복호화한다.

Table 1.

PEKS algorithm process

2.3 IBE

IBE는 사용자의 ID(이메일 주소, 개인 전화번호 등)를 공개키로 이용하는 암호화 방식이다[20] . 기존의 공개키 기반 방식에서는 암호화를 위해 송신자가 전달받은 수신자의 공개키가 상대방의 키가 맞는지 확인할 필요가 있지만 IBE에서는 수신자의 ID를 공개키로 사용하므로 키 검증 과정이 필요 없다.

IBE는 Setup, 키 생성, Extract, 암호화, 복호화로 이루어진 다섯 단계로 진행된다.

Setup 단계에서는 그림 2의 1번 과정과 같이 보안 파라미터 k를 입력으로 받아 IBE_Setup 과정을 진행한다. IBE_Setup 과정의 결과값으로 IBE_MasterKeyGen 과정을 진행하기 위한 파라미터 σ_params를 생성한다.

Fig. 2.

IBE algorithm

키 생성 단계는 그림 2의 2번부터 4번까지의 과정을 통해 진행된다. 앞선 Setup 과정에서 생성된 파라미터 σ_params를 입력값으로 받아 마스터키 생성 과정인 IBE_MasterKeyGen을 거쳐 마스터 공개키(MPK)와 마스터 비밀키(MSK)를 생성한다. 마스터 공개키는 3번째 과정과 같이 CompleteMPK 과정을 거치며 마스터 공개키 데이터(MPKD) 저장형식에 맞춰 저장된다. 4번째 과정과 같이 마스터 비밀키는 CompleteMSK 과정을 거쳐 마스터 비밀키 데이터(MSKD) 저장형식에 맞춰 저장된다. 마스터 비밀키 데이터는 IBE_Extract 과정에서 입력값으로 사용되어 유저의 비밀키를 만들게 되므로 직접 복호화에 관여하지 않는다. 마스터 공개키 데이터는 ID와 함께 평문을 암호화하는데 사용한다.

Extract 과정에서는 그림 2의 5번 과정과 같이 사용자 ID를 이용해 복호화에 사용될 유저의 비밀 키를 만들게 된다. 진행과정에서 유저의 ID 값과 마스터 비밀키를 통해 IBE_Extract 과정을 진행하고 SK_ID라는 유저 개인의 비밀키를 생성한다.

암호화 과정에서는 그림 2의 6번 과정과 같이 입력값으로 평문(Plaintext)과 사용자의 ID 그리고 마스터 공개키를 받는다. 입력값을 이용해 IBE_ Encrypt 암호화 과정을 통해 암호문(Ciphertext)을 반환한다.

복호화 과정에서는 그림 2의 7번 과정과 같이 암호화 과정에서 생성된 암호문과 유저의 비밀키(SK_ID)를 입력으로 받아 IBE_Decrypt 과정을 진행해 평문을 결과로 반환한다. 복호화 과정에서 유저의 비밀키 생성에 사용된 ID와 암호화에 사용된 ID가 같은 값을 가져야 복호화가 성공적으로 진행된다.

Ⅲ. 관련 연구

기존의 PEKS 관련 연구들은 수행 시간과 안전성 측면에서 많은 향상을 보였다. YANG et al. [22]은 기존의 방법들보다 모바일 스마트 단말기기 에서 효율적인 SCF-PEKS 기법을 제안하였다. 실제 기존 기법들보다 수행 시간 측면에서 매우 효율적임을 보였으며 hDH의 보안성을 달성하였다. Baek et al. [23]은 채널이 없는 안전한 PEKS 체계를 제시하였다. 해당 기법에서는 트랩도어가 공개되어 해당 키워드가 포함된 암호문을 얻어도 복호화가 실행 불가능함을 보였으며 BDH의 보안성을 달성하였다. Lu et al. [24]은 개인 정보 보호 키워드검색을 사용하여 향상된 SCF-PEKS 프레임 워크를 제시하였다. 제안된 프레임 워크를 통해 외부 공격자에 대해 암호문과 트랩도어의 안전성을 보였으며 invDBDH의 보안성을 달성하였다.

Hwang et al. [25]은 ElGamal 암호 시스템을 기반으로 한 새로운 SCF-PEKS를 제안하였으며 제안 기법에서 효율성과 보안성 모두 기존 체계보다 향상된 DDH의 보안성을 달성하였다. 앞서 살펴본 기존의 네 가지 PEKS 기법들은 보안성과 효율성에서 많은 향상을 보이나 양자컴퓨터의 계산능력을 이용한 연산이 가능한 미래에는 안전하지 않은 기법들이다.

Ⅳ. 연구 동기

많은 암호화 알고리즘들이 양자컴퓨터의 공격으로부터 안전한 기반문제를 적용하기 위해 연구가 되고 있지만 아직 양자내성 기반문제가 적용되지 못한 암호화 알고리즘들도 존재한다. 그중에서 기존에 제안된 PEKS 기법들은 성능과 보안성 측면에서 많은 향상을 보이고 있지만 양자컴퓨터의 공격으로부터 안전하지 않기 때문에 본 논문에서는 양자내성 기반 문제를 통해 양자컴퓨터의 공격으로부터 안전한 PEKS 알고리즘 설계를 제안한다. 본 연구에서 제안하는 PEKS 설계의 구현을 통해 수행 시간 측정을 진행하고 기존 제안된 PEKS 알고리즘들과 수행 시간 비교를 진행한다. 비교를 통해 제안한 알고리즘이 실제 랩톱, 모바일 및 태블릿 환경에서 사용될 수 있는지 검증한다. 이를 통해 추후 양자컴퓨터의 공격으로부터 안전하게 실제 환경에서의 사용 가능한지 검증한다.

Ⅴ. 제안 PEKS

본 장에서는 앞서 설명한 MNTRU 기반의 PEKS알고리즘 설계에 대하여 설명한다. 본 연구에서는 MNTRU를 기반으로 제안되었던 IBE를 이용해 양자내성을 지닌 PEKS를 제안하고 구현하여 성능을 측정한다.

5.1 MNTRU 기반 PEKS 알고리즘

본 연구에서 제안하는 PEKS 알고리즘은 MNTRU 기반 IBE의 각 과정을 이용하여 설계하며 키 생성, 트랩도어 키 생성, 암호화, 키워드 검색 테스트, 복호화 과정으로 구성 된다.

키 생성 과정은 그림 3과 같이 IBE의 키 생성 과정을 이용해 설계한다. 먼저 1번 과정과 같이 IBE_Setup 과정은 보안 파라미터 k를 입력으로 받아 파라미터 σ_params를 생성한다. 생성된 파라미터를 이용해 2번째 과정인 IBE_KeyGen 과정을 수행한다. IBE_KeyGen 과정을 이용해 생성된 마스터 공개키 (MPK)와 마스터 비밀키(MSK)를 이용해 PEKS과정을 진행하기 위한 PEKS 공개키와 PEKS 비밀키를 생성한다. 마스터 공개키와 마스터 비밀키를 PEKS 과정에 사용하기 위한 데이터 저장 형식으로 바꿔주기 위해 IBE 과정과 마찬가지로 Complete 과정을 수행한다. 마스터 공개키는 IBE_CompleteMPK 과정을 거치며 결과값으로 PEKS 공개키(PEKS_PK)를 생성한다. 마스터 비밀키는 IBE_CompleteMSK 과정을 거쳐 PEKS 비밀키(PEKS_SK) 를 생성한다.

Fig. 3.

Suggested PEKS key-generation

트랩도어 키 생성 과정은 IBE의 Extract 과정을 이용해 설계한다. IBE의 Extract 과정에서 ID 값을 입력하여 진행하지만 그림 4의 PEKS 과정에서는 사용자가 검색을 원하는 키워드를 ID 대신 입력해 IBE_Extract 과정을 진행한다.

Fig. 4.

Suggested PEKS trapdoor key-generation

입력한 키워드(K)를 해시함수를 이용해 연산한 값(K’)으로 변환한다. 본 연구에서는 sha3-512 해시함수를 사용하여 입력된 키워드 값을 정수형의 고정된 길이의 값으로 출력한다. 키워드를 입력한 해시함수의 출력값(K’)과 PEKS의 비밀키(PEKS_SK)를 이용해 IBE_Extract과정을 진행하여 트랩도어 키(TK)를 생성한다.

암호화 과정은 키 생성과정에서 생성된 PEKS 공개키를 이용해 입력된 평문을 암호화하는 과정으로 IBE의 암호화 과정을 이용해 설계한다. 입력된 평문의 문장은 단어 단위로 나뉘어 배열의 각 인덱스에 저장한다. 단어 배열은 암호화 단계에서 각 인덱스의 단어를 따로 암호화해서 인덱스별로 하나씩 암호문을 만든다. 암호화 과정에서 랜덤 값도 생성한다. 입력 문장의 단어 개수가 k개인 그림 5에서 a 배열을 만들기 위해 첫 번째 단어 m₁에 대해서 해시함수를 적용한 후 해시함수 출력값을 길이 512의 배열 (그림 5의 H(m₁)[0]⋯ H(m₁)[511])로 반환한다. b 배열은 랜덤 값 배열인데 a 배열과 같은 길이인 512로 생성한다. 이렇게 생성된 랜덤 값 배열 (b 배열) 의 각 인덱스마다 그림 5의 맨 아래 적힌 과정인 Random (mod 2)의 결과값이 저장된다. Random (mod 2)에서 Random 연산은 균일하게 분포된 값에서 랜덤으로 값을 선택하는 과정이며 (mod 2) 는 선택된 값을 2로 나눈 나머지 (b 배열 각 인덱스의 0 or 1 값)를 구하는 과정이다. 랜덤 값 배열은 단어 하나당 하나씩 할당되는데 그림 5와 같은 상황에서 512의 길이를 가지는 랜덤 값 배열 b가 단어의 개수인 k개 (m₁ ⋯ m_k) 만큼 생성된다.

Fig. 5.

Suggested PEKS generating random values

그림 6의 왼쪽 과정과 같이 복호화를 위한 암호문을 생성하는 과정에서는 k개의 랜덤 값 배열 (그림 5의 r₁ ⋯ r_k) 이 암호화를 위한 키 생성 과정을 통해 암호화키를 생성한다. 단어별 랜덤 값 배열로 생성된 암호화키를 이용해 그림 6의 오른쪽 과정에서 단어 단위 배열의 각 인덱스의 단어마다 암호화를 진행해 복호화를 위한 암호문을 생성한다. 복호화를 위한 암호문은 랜덤 값 배열로 생성된 키를 통해 메시지를 암호화하였기 때문에 올바른 키와 랜덤 값 배열을 이용해 복호화를 진행하게 되면 암호화 과정에서 입력한 메시지를 결과값으로 돌려주는 암호문이 된다.

Fig. 6.

Suggested PEKS generating ciphertext for decryption

그림 7의 왼쪽 과정과 같이 키워드 검색을 위한 암호문 생성과정에서는 앞선 복호화를 위한 암호문 생성과정과는 반대로 단어 단위 배열을 이용한 키 생성 과정을 통해 각 단어를 암호화를 위한 암호화키로 만든다. 해당 암호화 키 배열을 통해 그림 7의 오른쪽 과정에서 입력된 랜덤 값 배열 (그림 5의 r₁ ⋯ r_k) 의 각 인덱스를 암호화하게 되고 해당 암호문을 통해 키워드 검색 과정을 수행한다.

Fig. 7.

Suggested PEKS generating ciphertext for keyword search

키워드 검색을 위한 암호문은 메시지를 이용해 만든 암호화키로 랜덤 값을 암호화하였기 때문에 같은 키워드가 사용된 복호화키를 이용해 복호화를 진행하게 되면 결과값으로 암호화되었던 랜덤 값 (그림 5의 b 배열) 과 모든 인덱스에서 같은 값들이 나온다.

그림 8에서 두 가지 암호문을 만드는 암호화 과정을 확인할 수 있다. 해당 과정은 입력된 문장을 단어 단위로 나눈 배열에 대해 하나의 단어(word W)를 암호화하는 과정이다. 암호문을 생성하기 위해 필요한 랜덤값 배열은 그림 8의 2번째 과정 (그림 5의 Random (mod 2) 과정과 동일) 을 통해 구한 결과값으로 random_value 값을 출력한다. random _value는 그림 5의 과정의 b 배열과 같이 길이가 512인 배열의 각 인덱스에 Random(mod 2) 를 진행한 결과값이 저장된다. 3번째 과정에서 앞서 생성된 랜덤 값과 입력된 단어를 이용해 암호화하는 과정을 진행하기 위해 먼저 단어의 형식을 문자형식 (char형)에서 숫자형식 (long형)으로 변환해주는 convert_chars_to_longs의 과정을 구성한다.

Fig. 8.

Suggested PEKS encrypt

다음으로 4번째 과정과 같이 IBE_Encrypt 과정을 통해 키워드 검색을 위한 암호문 (C₁)이 생성된다. 이 과정에서 IBE_Encrypt에 입력되는 파라미터를 보게 되면 첫 번째 값으로 랜덤 값이 입력되고 두 번째 값으로 입력된 단어가 해시함수(HashFunction)와 형 변환과정을 거친 값 K가 입력된다.

IBE과정에서 IBE_Encrypt 파라미터의 첫 번째 입력값인 평문을 두 번째와 세 번째의 입력값을 이용하여 암호화하기 때문에 PEKS를 위해 설계된 과정을 거치게 되면 두 번째 값으로 입력된 단어와 PEKS 공개키를 이용해 첫 번째 값으로 입력된 랜덤 값을 암호화한다. 5번째 과정은 반대로 첫 번째 입력값에는 단어가 두 번째와 세 번째 입력값에는 랜덤 값과 공개키가 입력되어 입력된 문장의 각 단어가 암호화되는 복호화를 위한 암호문 (C₂) 을 생성한다. 마지막 6번째 과정에서 두 가지 암호문과 랜덤 값 배열이 모두 하나의 암호문 집합 내에 들어가는 것을 확인할 수 있다. 실제 입력된 문장의 모든 단어에 대해서 그림 8의 과정을 반복 진행하고 결과적으로 그림 9에서 볼 수 있듯이 암호문 집합 내에 복호화를 위한 암호문과 키워드 검색을 위한 암호문 결과가 들어간다. 그림 9에서 암호문 C₁과 C₂의 배열은 하나의 문장을 구성하는 k개의 단어에 대해서 각각 암호화한 결과를 인덱스마다 저장한 결과이며 마지막 random_value는 단어별로 생성한 랜덤 배열이다.

Fig. 9.

Ciphertext configuration

키워드 검색 테스트 과정은 트랩도어 키를 이용해 암호문 내에 키워드가 존재하는지 테스트하는 과정으로 IBE_Decrypt 과정을 이용한다. 그림 10은 입력값으로 암호문들의 집합(Ciphertext set S)과 트랩도어 키를 받는다. 그림 10의 1번째 반복과정을 통해 입력받은 암호문 집합 내의 암호문들에 대해 키워드 검색 과정을 수행한다. 2번째 과정을 통해 그림 9와 같은 구성으로 전달된 암호문에서 키워드 검색을 위한 암호문인 C₁과 랜덤값 배열인 random_value를 추출한다.

Fig. 10.

Suggested PEKS keyword search test

3번째 과정의 반복은 키워드 검색을 위한 암호문 배열의 각 인덱스에 대해 트랩도어 키를 이용해 IBE_Decrypt를 진행하기 위한 과정이다. 4번째 과정에서 키워드 검색을 위한 암호문의 IBE_Decrypt 결과값으로 나온 특정 값을 5번째 과정에서 검사한다. 4번째 과정은 트랩도어 키(TK)를 이용해 그림 9의 C₁배열 각 인덱스의 값인 암호문을 IBE_Decrypt(C₁[j], TK)를 통해 복호화한다. IBE_Decrypt(C₁[j], TK)에서 입력값인 C₁[j]는 하나의 암호문 집합 C를 만들 때 입력된 문장의 j번째 단어를 이용해 랜덤값 Rand[j]를 암호화한 암호문이다. 따라서 C₁[j]를 만들 때 사용된 j번째 단어와 트랩도어 키를 만들 때 사용된 키워드가 같다면 복호화의 결과값이 암호화 과정에서 사용된 랜덤값과 같은 값으로 반환된다. 즉, 그림 10의 4번째 과정의 복호화 출력값 (m)은 암호문과 같이 전달된 랜덤값 배열과의 비교에서 j번째 랜덤값과 같은 값을 나타낸다.

키워드 검색 과정에 사용되는 트랩도어 키를 통해서는 평문의 내용이 암호화된 복호화를 위한 암호문 (그림 9의 C₂)을 복호화할 수 없기 때문에 송신자가 전달하고자 하는 평문의 어떠한 내용도 검색 과정을 수행하는 입장에서 절대 알 수 없다. 검색과정을 그 어떤 곳에서 진행한다고 하여도 수신자와 송신자는 암호문의 안전성을 보장 받으며 정보를 송수신할 수 있다.

마지막 과정으로 실제 키워드가 존재하는 암호문들의 집합(Ciphertext set S’)을 전달받은 수신자가 암호문을 복호화하는 과정이며 키워드 검색과 마찬가지로 IBE_Decrypt 과정을 이용한다.

복호화 과정은 복호화를 위한 암호문과 PEKS 비밀키를 이용해 진행한다. 그림 11에서는 한 개의 단어에 대해서 복호화를 진행하는 과정이며 전달된 암호문 내의 단어 수만큼 반복 진행하여 평문 전체를 출력한다. 1번째 과정은 키워드를 포함한 암호문들의 집합 중 하나의 암호문을 불러오는 과정이다. 2번째 과정에서 선택된 암호문의 그림 9와 같은 구성 중 복호화를 위한 암호문 (C₂)과 random_value를 추출한다. 3번째 과정에서 암호문과 같이 전달된 랜덤 값과 PEKS 비밀키를 IBE_Extract 과정의 입력값으로 이용해 복호화를 위한 키를 생성한다. 생성된 복호화 키와 암호문이 입력값으로 쓰이는 IBE_Decrypt 과정을 통해 암호문을 복호화한다. 복호화의 결과값 (K)은 앞선 암호화 과정에서 입력된 평문을 숫자형식으로 바꿔준 값을 출력한다. 출력된 결과값을 처음의 평문과 같은 값으로 만들기 위해 다시 숫자형식(long형)에서 문자형식(char형)으로 바꿔주는 convert_longs_to_chars 과정을 수행하여 평문 (W)을 얻는다. 그림 11의 과정의 3번째부터 5번째까지의 과정을 암호문 내의 단어 수만큼 반복하여 전체 문장을 복호화한다.

Fig. 11.

Suggested PEKS decrypt

5.2 랩톱 구현 및 성능 측정

MNTRU기반으로 설계된 PEKS 알고리즘을 토대로 이메일 전송 시나리오를 구현하였고 테스트 진행 환경은 MacBook Pro (15-inch, 2017) 2.9GHz 쿼드 코어 intel Core i7 CPU이다. 랩톱에서는 PEKS의 다섯 단계에 대해 각각의 수행 시간을 측정하였다.

실제 수행 시간 측정된 결과는 표 2와 같이 측정되었으며 각 과정을 100번 수행하여 평균을 낸 값이다. 키 생성 결과를 보게 되면 4900ms로 측정되었으며 다른 과정보다 작게는 36배에서 크게는 308배 정도 수행시간의 차이를 보이는 것을 알 수 있다. 하지만 키 생성 과정은 초기에 한 번만 진행하면 되기 때문에 충분히 수용할 수 있는 결과다. 나머지 결과를 보게 되면 가장 느린 복호화가 137.7ms 가장 빠른 트랩도어 키 생성이 15.9ms로 측정되었다.

Table 2.

Laptop execution time measurement result

5.3 모바일, 태블릿 구현 및 성능 측정

모바일과 태블릿 환경에서도 시나리오를 구현하여 각 과정의 시간을 측정하였다. 모바일과 태블릿 두 가지 환경에서 각각의 과정에 대해서 수행시간을 측정하며 모바일 환경은 Galaxy S20 Ultra+ (퀄컴 스냅드래곤 865) 이며 태블릿 환경은 Galaxy tab S7+ (퀄컴 스냅드래곤 865+) 로 구성하였다.

모바일에서 진행한 과정의 수행 시간은 표 3과 같이 측정되었다. 랩톱에서의 측정 결과와 마찬가지로 키 생성은 126689ms로 다른 과정과 큰 차이를 보이며 가장 오래 걸리는 것을 볼 수 있지만 한 번만 실행하면 되는 과정이기 때문에 충분히 수용할 수 있는 결과이며 트랩도어 키 생성, 암호화, 키워드 검색, 복호화 과정은 모바일에서 충분히 빠른 성능을 보이며 실제로 사용 가능한 결과임을 알 수 있다.

Table 3.

Mobile execution time measurement result

표 4와 같이 측정된 태블릿에서의 수행시간 측정 결과에서도 모바일에서와 마찬가지로 한 번만 수행하면 되는 키 생성을 제외한 나머지 과정들의 결과는 실제 사용 가능한 성능을 보인다.

Table 4.

Tablet execution time measurement result

Ⅵ. 결과 분석 및 비교

본 연구에서 제시된 PEKS와 기존에 제안된 PEKS들과 비교를 진행하였으며 모든 환경은 2.9GHz의 CPU환경에서 진행하였다. 모든 PEKS는 단어 1개에 대한 암호화 및 키워드 검색 과정에 대해 측정하였으며 그림 12에서 키워드 검색과정과 암호화 과정에 대한 비교를 확인할 수 있다.

Fig. 12.

PEKS performance comparison

기존에 연구된 PEKS 기법들은 다가올 양자내성 시대에는 보안성이 현저하게 떨어질 우려가 있다. 하지만 본 논문에서 제안한 PEKS는 보안성을 극대화하는 방법에 초점을 맞추었기 때문에 양자컴퓨터를 이용한 암호화 기법에 대한 공격이 가능한 미래에도 사용할 수 있는 암호화 기법이다. 그림 12의 왼쪽의 비교 결과를 보게 되면 키워드 검색에서 본 논문에서 설계한 결과인 2.79ms가 [22]의 측정값인 0.033ms와 [25]의 측정값인 0.235 보다는 느리지만 [23], [24]에서 제시한 기법들 보다는 좋은 성능을 보이고 있다. 그림 12의 오른쪽 그래프의 암호화 과정 비교에서는 7.378ms로 [22], [24], [25]의 측정값인 0.177ms, 6.322ms, 0.094ms 보다 느리지만 [23] 보다는 좋은 성능을 보임을 알 수 있다.

표 5에서 기존의 연구들은 양자 내성을 지니지 않지만 본 연구에서 제안한 PEKS는 양자 내성을 지니고 있는 것을 알 수 있다. 기존 [22], [23], [24], [25]의 연구에서 제안한 PEKS의 성능측정 결과에서 충분히 좋은 성능임을 보였음에도 양자컴퓨터가 상용화 된다면 사용할 수 없는 알고리즘들이다. 본 연구에서 제안한 PEKS는 양자컴퓨터의 공격으로부터의 안전성을 바탕으로 기존 연구들이 제시하였던 알고리즘의 성능과 비교하여도 충분히 사용 가능한 성능을 보임을 알 수 있다.

Table 5.

Performance and quantum safe comparison

Ⅶ. 최신연구와의 비교

본 논문에서 제시한 PEKS의 기반 문제인 MNTRU는 NTRU기반 문제의 성능을 향상시킨 이론이다. [19]에서는 NTRU를 기반문제로 한 PEKS의 구현을 통해 양자 내성을 지니면서 성능이 증가된 PEKS 성능 측정 결과를 제시한다. 본 논문에서 제시한 MNTRU기반 PEKS와 [19]에서 제시한 NTRU기반 PEKS의 안전성과 성능 측면에서 비교하고자 한다.

[16]에서 제시한 MNTRU기반 문제는 NTRU기반 문제에서 제한적으로 다뤄진 파라미터에 대해 유연성을 높여 전체적인 효율성을 높인 결과를 제시한다. [19]에서는 80bit security와 192bit security를 가지는 NTRU의 각 안전성을 바탕으로 구현한 PEKS의 각 기능의 성능측정 결과를 제시한다. 본 논문에서 사용한 MNTRU는 147bit security의 안전성을 바탕으로 실험을 진행하였다. 본 실험은 Parallels에서 2.9GHz CPU를 이용한 가상 리눅스 환경을 이용해 진행한다.

실제 실험의 결과는 그림 14에서 확인할 수 있다. 먼저 80bit 안전성을 가진 NTRU 기반 PEKS와의 비교 결과를 보게 되면 암호화 수행시간은 NTRU기반 PEKS가 본 논문에서 제시한 기법의 수행시간보다 절반 정도의 수행시간밖에 걸리지 않는다. 트랩도어 키 생성과 테스트 과정은 본 논문에서 제시한 PEKS와 NTRU기반 PEKS가 비슷한 결과를 보인다. 192bit의 안전성을 가진 NTRU 기반 PEKS와 본 논문에서 제시한 기법의 수행시간 비교결과는 암호화, 트랩도어 키 생성, 키워드 검색 테스트 모두 본 논문에서 제시한 기법이 빠름을 알 수 있다.

Fig. 14.

PEKS performance comparison

본 논문에서 제시한 PEKS는 80bit 안전성의 NTRU기반 PEKS보다 암호화에서는 확연히 느린 결과를 보였지만 나머지 과정은 비슷한 결과를 보인다는 점에서 147bit의 더 뛰어난 안전성을 가지고 있음에도 암호화를 제외하고 비슷한 수준의 성능을 낼 수 있음을 알 수 있다. 192bit 안전성의 NTRU기반 PEKS의 안전성은 본 논문에서 제시한 기법보다 좋다. 만약 80bit보다 크면서 147bit 보다 작은 안전성을 필요로 하는 곳에서 MNTRU는 본 논문에서 적용한 것과 같이 147bit의 안전성을 적용하면서도 성능 또한 충분히 사용가능하도록 설계가 가능하지만 NTRU기반의 PEKS는 이러한 경우에서 사용하기 위해 효율성을 감소시키면서 192bit의 안전성을 적용할 수밖에 없다. MNTRU가 NTRU보다 효율성을 증가시킨 기법이라는 점을 토대로 [19] 에서 제시한 NTRU기반의 PEKS보다 본 논문에서 제시한 기법이 훨씬 효율적으로 사용가능하다는 점을 실험결과를 통해 확인 할 수 있다.

Ⅷ. 결 론

본 논문에서 제시한 PEKS의 보안성은 양자내성을 지니는 것이 확인된 기반 문제인 MNTRU를 토대로 설계하였기 때문에 기존에 제시되었던 PEKS 와는 달리 양자컴퓨터의 공격으로부터 안전하면서 성능 또한 우수한 것을 보였다. 설계 과정에서 MNTRU기반 문제를 이용한 IBE의 각 기능을 통해 PEKS를 설계하였으며 이메일 전송 시나리오를 바탕으로 랩톱과 모바일에서의 구현 테스트를 진행했다. 한번만 실행하면 되는 키 생성을 제외한 나머지 과정의 수행시간이 랩톱에서는 암호화가 71.8ms, 키워드 검색 과정이 28.2ms, 복호화가 137.7ms로 측정되었으며 모바일에서는 암호화 229.6ms, 키워드 검색 과정 134.6ms, 복호화가 2258.2ms로 측정되었다. 태블릿의 수행 결과는 모바일환경과 비슷한 성능으로 측정되었음을 알 수 있다. 해당 실험결과와 기존 PEKS 실험 결과들과의 비교를 통해 실제 환경에서 사용할 수 있는 우수한 성능임을 보였으며 이러한 점들을 통해 제안한 PEKS 알고리즘을 랩톱뿐만 아니라 모바일 및 태블릿 환경에서 양자 컴퓨터의 공격으로부터 안전하게 실생활에 응용할 수 있음을 알 수 있다.

Acknowledgments

본 연구는 서울과학기술대학교 교내 연구비 지원을 받아 수행된 연구임

References

• F. Arute et al., "Quantum supremacyusing a programmable superconducting processor", Nature, Vol. 574, No. 7779, pp. 505–510, Oct. 2019.
• S. Boixo et al., "Characterizingquantum supremacy in near-term devices", Nature Physics, Vol. 14, No. 6, pp. 595–600, Apr. 2018. [https://doi.org/10.1038/s41567-018-0124-x]
• P. W. Shor, "Polynomial-Time Algorithmsfor Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAMReview, Vol. 41, No. 2, pp. 303-332, Jan. 1999. [https://doi.org/10.1137/S0036144598347011]
• J. Porras, J. Baena, and J. Ding, "ZHFE, a New Multivariate Public Key Encryption Scheme", in Post-Quantum Cryptography, Springer International Publishing, pp. 229-245, Oct. 2014. [https://doi.org/10.1007/978-3-319-11659-4_14]
• J. Ding and D. Schmidt, "Rainbow, a New Multivariable Polynomial Signature Scheme", in Applied Cryptography and Network Security, Springer Berlin Heidelberg, pp. 164–175, 2005. [https://doi.org/10.1007/11496137_12]
• R. Misoczki, J. P. Tillich, N. Sendrier, and P. S. L. M. Barreto, "MDPC-McEliece: New McEliece variants fromModerate Density Parity-Check codes", in 2013 IEEE International Symposium on Information Theory, Istanbul, Turkey, Jul. 2013. [https://doi.org/10.1109/ISIT.2013.6620590]
• D. J. Bernstein, T. Lange, and C. Peters, "Wild McEliece", in Selected Areas in Cryptography, Springer Berlin Heidelberg, pp. 143–158, 2011. [https://doi.org/10.1007/978-3-642-19574-7_10]
• D. J. Bernstein, T. Chou, and P. Schwabe, "McBits: Fast Constant-Time Code-Based Cryptography", in Cryptographic Hardware and Embedded Systems – CHES 2013, Springer Berlin Heidelberg, pp. 250–272, Aug. 2013. [https://doi.org/10.1007/978-3-642-40349-1_15]
• D. Stehlé and R. Steinfeld, "Making NTRU as Secure as Worst-Case Problems over Ideal Lattices", in Advances in Cryptology- EUROCRYPT 2011, Springer Berlin Heidelberg, pp. 27–47, Oct. 2011. [https://doi.org/10.1007/978-3-642-20465-4_4]
• J. W. Cooley and J. W. Tukey, "Analgorithm for the machine calculation of complex Fourier series", Mathematicsof Computation, Vol. 19, No. 90, pp. 297–297, May 1965. [https://doi.org/10.1090/S0025-5718-1965-0178586-1]
• L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky, "Lattice Signatures and Bimodal Gaussians", in Advances in Cryptology – CRYPTO 2013, Springer Berlin Heidelberg, pp. 40–56, Aug. 2013. [https://doi.org/10.1007/978-3-642-40041-4_3]
• E. Alkim,L. Ducas, T. Pöppelmann, and P. Schwabe, "Post-quantum key exchange—a new hope", in 25th{USENIX} Security Symposium ({USENIX} Security 16), pp. 327-343, Aug. 2016.
• D. J. Bernstein et al., "SPHINCS:P ractical Stateless Hash-Based Signatures", in Advances in Cryptology-EUROCRYPT 2015, Springer Berlin Heidelberg, pp. 368–397, Apr. 2015. [https://doi.org/10.1007/978-3-662-46800-5_15]
• E. Dahmen, K. Okeya, T. Takagi, and C. Vuillaume, "Digital Signatures Out of Second-Preimage Resistant HashFunctions", in Post-Quantum Cryptography, Springer Berlin Heidelberg, pp. 109–123, Oct. 2008. [https://doi.org/10.1007/978-3-540-88403-3_8]
• Csrc.nist.gov. 2021. Post-Quantum Cryptography | CSRC. [online] Available at: <https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions, >. [accessed: 11 January 2021].
• J. H. Cheon,D. H. Kim, T. C. Kim, and Yongha Son, "A New Trapdoor over Module-NTRU Latticeand its Application to ID-based Encryption", in IACR Cryptol. ePrint Arch, Vol. 19, pp. 1468, 2019.
• D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano, "Public Key Encryption with Keyword Search", inAdvances in Cryptology-EUROCRYPT 2004, Springer Berlin Heidelberg, pp. 506–522, May 2004. [https://doi.org/10.1007/978-3-540-24676-3_30]
• M. Abdalla et al., "Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions", in Advances in Cryptology-CRYPTO 2005, Springer Berlin Heidelberg, pp. 205–222, Aug. 2005. [https://doi.org/10.1007/11535218_13]
• R. Behnia, M. O. Ozmen, and A. A.Yavuz, "Lattice-Based Public Key Searchable Encryption from ExperimentalPerspectives", IEEE Transactions on Dependable and Secure Computing, Vol. 17, No. 6, pp. 1269–1282, Nov. 2020. [https://doi.org/10.1109/TDSC.2018.2867462]
• D. Boneh and M. Franklin, "Identity-Based Encryption from the Weil Pairing", in Advances in Cryptology-CRYPTO 2001, Springer Berlin Heidelberg, pp. 213–229, Aug. 2001. [https://doi.org/10.1007/3-540-44647-8_13]
• A. Menezes, P. C. Oorschot, and S. A. Vanstone, "Handbook Of Applied Cryptography", CRC Press, pp. 321-324, Oct. 1996.
• N. Yang, S. Xu, and Z. Quan, "An Efficient Public Key Searchable Encryption Scheme for Mobile Smart Terminal", IEEE Access, Vol. 8, pp. 77940–77950, Apr. 2020. [https://doi.org/10.1109/ACCESS.2020.2989628]
• J. Baek, R. Safavi-Naini, and W.Susilo, "On the Integration of Public Key Data Encryption and Public KeyEncryption with Keyword Search", in Lecture Notes in Computer Science, SpringerBerlin Heidelberg, pp. 217–232, Sep. 2006. [https://doi.org/10.1007/11836810_16]
• Y. Lu, J. Li, and Y. Zhang, "SCF-PEPCKS: Secure Channel Free Public Key Encryption With Privacy-ConservingKeyword Search", IEEE Access, Vol. 7, pp. 40878–40892, Mar. 2019. [https://doi.org/10.1109/ACCESS.2019.2905554]
• M. S. Hwang, C. C. Lee, and S. T. Hsu, "An ElGamal-like Secure Channel Free Public Key Encryption with Keyword Search Scheme", International Journal of Foundations of Computer Science, Vol. 30, No. 2, pp. 255–273, Feb. 2019. [https://doi.org/10.1142/S0129054119500047]