(Comparison of Lattice-Based Key Exchange Protocols for Quantum Computing Attack)
최락용
안형철
이지은
김성숙
김광조
한국통신학회
[요약] 격자 기반 암호는 양자 컴퓨터를 이용한 공격에도 안전한 포스트 양자 암호(Post Quantum Cryptography, PQC)의 하나로 각광받고 있으며, 함수형 암호, 준동형 암호, 준동형 서명, 난독화 등 다양한 목적으로 연구가 진행 중에 있다. 격자 기반 키 교환 프로토콜은 기존에 사용하고 있는 DH(Diffie-Hellman) 키 교환 프로토콜을 비롯한 정수론 기반의 키 교환 프로토콜을 대체하는 기술로 본 논문에서는 총 7가지의 격자 기반 (인증) 키 교환 프로토콜에 대해 기반 문제, 샘플링 알고리즘, 보안도 및 안전성 분석 기법, 구현 효율성 등을 비교하고 향후 연구를 제시하였다.
링크:
https://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE07274687
이산 대수 문제, 소인수 분해 문제의 어려움에 기반한 키 교환(Key Exchange, KE) 프로토콜 및 인증 키 교환 (Authenticated Key Exchange, AKE) 프로토콜은 Shor 알고리즘에 따라 양자 컴퓨터의 공격에 대단히 취약하다. 따라서 양자컴퓨터의 공격에도 안전한 KE가 필요하다. 포스트 양자 암호(Post-Quantum Cryptography)의 필요성이 제기되고 있으며, 그 중 하나로 격자 기반 KE 프로토콜이 알려져 있다. 또한 인증과정이 추가된 AKE 프로토콜은 기존의 KE 프로토 콜에 비하여 상호간의 인증 정보를 교환하여 중간자 공격 (Man-in-the-Middle Attack)에 안전하다.
본 논문에서 분석한 격자 기반 KE 및 AKE 프로토 콜은 DXL12, BCNS15, NewHope16, Frodo16, ZZD+15, spKEX17, Kyber17의 총 7 가지로 최 근 Ring-LWE 기반 키 교환 프로토콜에 대해 에러 보정 함수의 취약점 또는 격자 상의 특별한 기저를 이용하여 공격하는 논문이 Fluhrer, Gong과 Zhao, Ding 등에 의해 각각 발표된 가운데 각각의 프로토 콜에 대하여 소개하고 기반 문제, 실행시간, 데이터 전송량, 샘플링 알고리즘 등에 대하여 비교한다.
본 논문의 구성은 다음과 같다. Ⅱ장에서 격자 및 LWE 문제에 대한 설명과 KE와 AKE 프로토콜, ROM(Random Oracle Model) 및 QaROM(Quantum accessible Random Oracle Model)에 대하여 간락히 설명한다. 이후 Ⅲ장은 7 가지의 격자 기반 KE 및 AKE 프로토콜 대하여 소개한다. Ⅳ장에서는 앞서 설명한 프로토콜에 대하여 기반 문제, 실행시간, 데이터 전송량, 샘플링 알고리즘, 디지털컴퓨터와 양자 컴퓨터에 대한 보안도에 대하여 비교하고 표로 정리한다. 마지막으로 Ⅴ장에는 향후 격자 기반 키 교환 프로토콜을 활용한 연구과제에 대하여 논의하고 결론을 내린다.
