A Post-Quantum Secure Lattice-Based Forward-Secure Identity Based Encryption with Applications to Internet of Things Architecture

기술 요약: 사물인터넷 아키텍처에 적용 가능한 양자 내성 격자 기반 전방향 보안 식별자 기반 암호화

문제 정의
사물인터넷(IoT)의 급격한 확장은 자원이 제한된 이기종 장치들이 방대한 양의 데이터를 교환하는 환경을 조성했습니다. 이러한 환경에서 기밀성을 보장하고 보안 키 관리를 수행하는 것은 매우 까다로운 과제입니다. 전통적인 공개키 기반 구조(PKI)는 인증서 처리에 따른 과도한 오버헤드를 발생시켜 IoT에 부적합합니다. 식별자를 통해 공개키를 유도하는 식별자 기반 암호화(IBE)는 가벼운 대안을 제공하지만, 물리적 IoT 배포 환경에서 흔히 발생하는 부채널 공격 및 키 추출 공격에 취약합니다. 현재의 비밀키가 탈취될 경우, 표준 IBE는 과거의 통신 내용을 보호할 수 없습니다.

나아가, 기존의 전방향 보안 IBE(FS-IBE) 방식은 다음과 같은 이중 과제에 직면해 있습니다:

1. 양자 내성 결여: 고전적 난해성 가정(예: 이산 로그, 정수 인수분해)에 기반한 구성은 양자 공격자에게 취약합니다.
2. 효율성 한계: 기존의 격자 기반(LWE 기반) 전방향 보안 방식은 양자 내성은 갖추었으나, 공공 파라미터, 비밀키 및 암호문 크기가 큽니다. 이러한 비효율성은 제약이 많은 IoT 시스템에 적용하기 어렵게 만듭니다.

방법론
저자들은 Ring Learning With Errors (RLWE) 가정에 기반한 Ring 설정에서 동작하는 새로운 격자 기반 전방향 보안 IBE 방식인 RFS-IBE를 제안합니다. 이 구성은 다음과 같은 여러 암호 기술을 통합합니다:

• Ring-LWE 기반: 아이디얼 격자(특히 링 $R_q = \mathbb{Z}_q[x]/\langle x^n + 1 \rangle$)의 대수적 구조를 활용함으로써, 대규모 행렬을 단일 링 요소로 압축하여 표준 LWE 대비 파라미터 크기를 크게 줄였습니다.
• 최소 커버 메커니즘을 갖춘 이진 트리 구조: 전방향 보안을 달성하기 위해, 시간을 에포크(epoch)로 나누는 이진 트리 구조를 사용합니다. 특정 에포크 $t$에 대해, 비밀키 업데이트 메커니즘은 "최소 커버(minimal cover)" 노드 집합을 활용합니다. 이 집합은 현재 에포크의 리프 노드의 조상들을 포함하되 이전 에포크의 조상들은 제외함으로써, 현재 키가 탈취되더라도 과거 에포크의 키가 드러나지 않도록 보장합니다.
• 트랩도어 위임(Trapdoor Delegation): 본 방식은 마스터 비밀키로부터 전체 설정을 다시 실행하지 않고도 특정 에포크를 위한 비밀키를 유도하기 위해 트랩도어 위임 알고리즘(ringExtBasis, ringRandBasis, ringGenSamplePre)을 사용합니다. 이를 통해 효율적인 에포크별 키 업데이트가 가능합니다.
• Dual Regev 유형 암호화: 기반이 되는 암호화 메커니즘은 링 설정에 맞게 조정된 Dual Regev 암호화의 변형이며, 이는 결정적 RLWE 가정 하에서 CPA 보안을 보장합니다.

주요 기여

1. 최초의 RLWE 기반 FS-IBE: 저자들의 지식 범위 내에서, 본 논문은 이진 트리 구조와 최소 커버 메커니즘, 그리고 아이디얼 격자 상의 트랩도어 위임을 결합한 최초의 RLWE 기반 전방향 보안 IBE(RFS-IBE)를 제시합니다.
2. 정식 보안 분석: 저자들은 RFS-IBE가 결정적 RLWE 가정 하의 랜덤 오라클 모델에서 전방향 보안 선택적 식별자 선택 평문 공격(fs-sID-CPA) 보안을 달성함을 입증하는 정식 보안 증명을 제공합니다. 또한, 표준 변환(예: BCHK 또는 FO 변환)을 사용하여 CCA 보안을 달성할 수 있는 방법도 설명합니다.
3. 효율성 최적화: 표준 LWE 설정이 아닌 링 설정을 사용함으로써, 제안된 방식은 공공 키, 비밀 키 및 암호문 크기를 엄격하게 축소했습니다. 이는 이전의 LWE 기반 구성(특히 Jin 등의 연구)이 가진 효율성 병목 현상을 해결합니다.
4. IoT 응용 사례 연구: 본 논문은 RFS-IBE를 실제 병원 환경의 IoT 아키텍처에 통합하는 사례를 보여줍니다. 이 시나리오에서 백엔드 서버는 개인키 생성기(PKG) 역할을 수행하며, 게이트웨이와 의료 센서는 사용자로 기능합니다. 본 방식은 제약이 많은 장치에서도 충분히 효율적이면서도, 키 추출 공격 및 부채널 누출로부터 과거의 의료 데이터를 보호함을 보여줍니다.

결과 및 성능
본 논문은 Linux 시스템의 Intel Core i5 프로세서 환경에서 Python 3.10을 사용하여 프로토타입 구현을 진행하였으며, Jin 등의 LWE 기반 FS-IBE [10]와 비교하였습니다.

• 크기 감소: 이론적 분석에 따르면, Jin 등의 LWE 기반 방식은 파라미터가 $\Omega(n^2 (\log q)^2 \log N)$의 규모로 증가하는 반면, 제안된 RFS-IBE는 $O(n \cdot \text{polylog}(N))$의 규모로 확장됩니다. 이는 $m$차원 행렬을 단일 링 요소로 압축했기 때문입니다.
• 벤치마킹: 실험 결과, 제안된 방식은 기존 방식에 비해 실행 시간과 메모리 오버헤드를 모두 줄였습니다:
  • KeyGen: 2.74 ms에서 1.82 ms로 단축; 메모리 58.3 KB에서 42.6 KB로 감소.
  • Encrypt: 2.08 ms에서 1.35 ms로 단축; 메모리 49.7 KB에서 37.4 KB로 감소.
  • Decrypt: 1.86 ms에서 1.11 ms로 단축; 메모리 44.2 KB에서 31.8 KB로 감소.

의의 및 주장
저자들은 RFS-IBE가 양자 시대의 IoT 통신을 보안하기 위한 실질적인 솔루션을 제공한다고 주장합니다. 전방향 보안(현재 키가 탈취되어도 과거 데이터를 보호함)과 링 기반 암호 기술의 효율성을 결합함으로써, 본 방식은 IoT 장치의 자원 제약과 보안 수준 사이의 핵심적인 절충안을 해결합니다.

본 논문은 현재의 구성이 fs-sID-CPA 보안을 달성하지만, 추가적인 오버헤드를 통해 적응적 CCA 보안으로 확장 가능하다는 점을 명시하며 마무리합니다. 향후 연구로는 상세한 시스템 레벨 구현 개발과, 대규모 분산 IoT 네트워크를 위한 확장성을 더욱 개선하기 위한 계층적 식별자 기반 암호화(HIBE) 탐색을 제안합니다. 본 연구는 GRAID 프로그램과 ANRF-PMECRG 프로젝트의 지원을 받았습니다.