양자 후 암호

양자 후 암호(Post-Quantum Cryptography) 또는 의역하여 양자내성암호는 양자 컴퓨터를 이용한 공격에 다항 시간내에 뚫리지 않을것으로 기대되는 암호이다. 기존의 암호는 크게 인수분해, 이산로그, 타원곡선 이산로그 문제 셋 중 하나에 기반하여 설계되었는데, 이는 양자컴퓨터를 이용한 알고리즘인 쇼어 알고리즘에 뚫리게 된다.

필요성

양자컴퓨터가 실용화 될 경우 양자컴퓨팅 환경에 적합한 통신기술로서 양자 키 분배(Quantum Key Distribution, QKD)와 양자 후 암호가 존재한다. 이 중 QKD는 키 교환 과정의 안전함을 제고하는 것이며, 앞서 언급한 인수분해 및 이산로그 문제를 이용하여 설계한 암호들이 쇼어 알고리즘에 의해 비교적 짧은 시간에 암호화가 깨질 수 있는 문제에 대한 해결책은 되지 않는다. 英 NCSC가 모든 정부기관과 군사 분야에서 QKD사용을 보증하지 않고 양자컴퓨터 위협의 최적 대안은 PQC라고 발표한 바 있다.

현재까지 알려진 실험실 차원의 양자 컴퓨터로 실제 암호 알고리즘을 깨뜨릴 수는 없지만[3], 암호학자들은 새로운 암호 알고리즘의 필요성에 공감하고 연구를 진행하고 있다. 이러한 연구는 2006년 PQCrypto 컨퍼런스를 통해 학계와 산업계에서 큰 관심을 받게 되었으며, 최근에는 ETSI(European Telecommunications Standards Institute) 및 Institute for Quantum Computing에서 주최한 Quantum Safe Cryptography와 같은 여러 워크샵을 통해 더 많은 관심을 받게 되었다.

양자 컴퓨터가 공개키 암호 알고리즘에 가하는 위협과 대조적으로, 대부분의 최신 대칭키 암호 알고리즘 또는 해시 함수는 양자 컴퓨터의 공격에 대해 상대적으로 안전한 것으로 간주된다. 그로버(Grover)의 알고리즘은 대칭키 암호 알고리즘에 대한 공격 속도를 높이기는 하지만 키의 크기를 두 배로 늘리면 이러한 공격을 효과적으로 차단할 수 있다고 알려져 있다.[8] 따라서 양자 컴퓨터에 내성을 갖는 대칭키 암호는 현재의 대칭키 암호와 크게 다르지 않아도 될 것으로 판단된다.

알고리즘

현재 양자내성암호 연구는 아래의 여섯 가지 상이한 수학적 난제 또는 접근 방법으로 진행되고 있다.

• 격자기반 암호 LWE(Learning with errors), Ring-LWE 등을 기반으로 하는 암호 알고리즘과 Ring-LWE 키교환 및 Ring-LWE 전자서명, 구 버전의 NTRU 또는 GGH 암호 알고리즘과 새로운 버전의 NTRU 또는 BLISS 전자서명 등이 격자기반 암호에 속한다. 지난 수년 동안 NTRU와 같은 암호 알고리즘을 공격하는 다양한 시도가 있었으나 성공한 사례는 없었다. 유럽연합 집행위원회(European Commission)가 후원하는 양자내성암호 연구 그룹(Post Quantum Cryptography Study Group)은 표준화를 위해 NTRU 알고리즘보다 Stehle-Steinfeld가 개선한 NTRU를 사용할 것을 권고했다. 연구에 따르면 NTRU는 다른 격자 기반 알고리즘보다 더 안전하다고 판단되는데, 특허에 묶여있었기 때문에 개선안을 권고한 것으로 보인다.   
• 다변수 다항식 기반 암호 다변수 다항식의 해를 구하기 어렵다는 것을 기반으로 하는 Rainbow(Unbalanced Oil and Vinegar)와 같은 암호 알고리즘이 여기에 속한다. 그동안 암호 알고리즘 개발의 시도가 수차례 있었으나 실패했었고, Rainbow 전자서명이 양자내성을 갖는 스킴으로서 성공을 거두었다.
• 해쉬 기반 암호 Lamport 서명, Merkle 서명 알고리즘, XMSS, SPHINCS, 및 WOTS와 같은 암호 알고리즘이 여기에 속하는데, 일회 또는 수회로 서명 가능한 횟수가 제한된다. 해시 기반의 전자서명은 1970년대 후반 Ron Merkle에 의해 발명되었으며 이후로도 RSA 및 DSA와 같은 대수적 전자서명 기법으로서 연구되어왔다. 해시기반 공개키 서명의 경우 개인키를 사용하여 서명할 수 있는 서명의 갯수에 제한이 있다는 것이 중요한 문제로 지적되어 왔으며, 양자내성암호의 기반문제로 주목을 받기 전까지는 관심을 받지 못하고 있었다. 1989년 Moni Naor와 Moti Yung은 UOWHF 해싱 알고리즘과 그를 이용한 서명(Naor-Yung 체계)을 설계하였는데, 이 서명 방법은 트랩도어 속성이 필요하지 않은 첫 번째 서명이다.
• 부호(코드)기반 암호 McEliece, Niederreiter 암호 알고리즘과 Courtois, Finiasz, Sendrier 서명 알고리즘이 오류 정정부호에 의존하는 알고리즘에 속한다. 랜덤한 Goppa 코드를 사용하는 기존 McEliece 전자서명은 40년 이상 엄밀한 공격에도 공격되지 않았다. 그러나 키의 크기를 줄이기 위한 여러 가지 변형이 McEliece 체계의 안전성을 침해하였다. 유럽 위원회가 후원하는 양자내성암호 Study Group은 McEliece 공개키 암호 알고리즘을 양자내성암호의 장기적인 후보로 추천했다.
• 초특이 타원곡선 아이소제니 암호 이 암호 시스템은 초특이 타원 곡선과 초특이 아이소제니 그래프의 특성을 활용하여 현재 광범위하게 사용되고 있는 Diffie-Hellman 및 타원 곡선 Diffie-Hellman 키교환 방법을 양자컴퓨터에 내성을 갖는 Diffie-Hellman 키교환 방법으로 변경한 것이다. 기존 Diffie-Hellman 구현과 매우 유사하게 작동하기 때문에 정부의 대규모 감시를 방지하고 장기적인 비밀키 유출을 방지하는 데 모두 중요한 것으로 간주되는 순방향 비밀성을 제공한다. 2012년 중국 국가 핵심 연구소(Chinese State Key Lab)와 Xidian University의 연구원 Sun, Tian 및 Wang은 De Feo, Jao 및 Plut의 작업을 확장하여 통합 서비스 네트워크를 위한 초특이 타원 곡선 아이소제니 기반 양자내성 전자서명을 개발했다.
• 대칭키 암호의 양자 내성 충분히 큰 크기의 암호키를 사용한다면 AES 및 SNOW 3G와 같은 기존의 대칭키 암호 알고리즘은 이미 양자 컴퓨터의 공격에 내성을 갖는다. 또한 Kerberos 및 3GPP 모바일 네트워크 인증 구조와 같이 대칭키 암호를 사용하는 키관리 시스템 및 프로토콜도 양자 컴퓨터의 공격에 대해 본질적으로 안전하다. 이미 세계적으로 널리 배포되어 있다는 점을 감안할 때 일부 연구자들은 오늘날 양자내성암호를 구현하는 효율적인 방법으로 Kerberos와 같은 대칭키 관리의 확장된 사용을 권장하기도 한다.

안전성 환원문제

암호학에서 암호 알고리즘의 안전성 증명은 이미 알려진 수학적 난제와 그 알고리즘을 해독하는 것의 어려움이 동등하다는 것을 증명하는 방법이 일반적인데, 이를 ‘안전성 환원(security reduction)’이라고 부른다. 현재 양자내성암호의 안전성 증명에 사용되는 안전성 환원은 다음과 같다.

• 격자기반 암호 - Ring-LWE 전자서명 안전성 증명의 하한선으로서 일부 버전의 Ring-LWE 문제를 NP-hard 문제인 격자에서의 최단 벡터 문제(shortest-vector problem; SVP)로 환원한다. Güneysu, Lyubashevsky 및 Pöppelmann의 논문에 정의된 Lyubashevsky의 Ring-LWE 전자서명 변형은 증명 가능한 안전성 환원이 존재한다. GLYPH 서명 체계는 Güneysu, Lyubashevsky, Pöppelmann(GLP) 서명의 변형이다. 또 다른 Ring-LWE 전자서명으로 Ring-TESLA가 있는데, 이는 LWR(Learning with Rounding)이라고 하는 LWE의 변형이 있는데, 이는 “향상된 속도 및 대역폭”을 제공한다. LWE가 하위 비트를 숨기기 위해 작은 오류를 추가하는 것을 활용하는 반면, LWR은 같은 목적으로 반올림을 활용한다.
• 격자기반 암호 – NTRU, BLISS NTRU 암호 알고리즘과 BLISS 전자서명의 안전성은 격자의 ‘가장 가까운 벡터 문제(Closest Vector Problem; CVP)’와 관련이 있다고 믿어진다. CVP 역시 NP-hard 문제로 알려져 있다. 유럽연합 집행위원회가 후원하는 양자내성암호 연구그룹은 안전성 증명이 가능한 NTRU의 Stehle-Steinfeld 변종을 기존의 NTRU 알고리즘 대신 사용할 것을 권고했다.
• 다변수 다항식 기반 암호 – Unbalanced Oil and Vinegar Unbalanced Oil and Vinegar 전자서명 알고리즘은 유한체에서 다변수 다항식의 해를 구하기 어렵다는 것을 안전성의 기반으로 하는 암호 알고리즘이다. Bulygin, Petzoldt 및 Buchmann은 일반적인 다변수 이차 UOV 시스템을 NP-Hard Multivariate Quadratic Equation Solving 문제로 환원할 수 있음을 보였다.
• 해쉬 기반 암호 – Merkle 전자서명 2005년 Luis Garcia는 Merkle Hash Tree 전자서명의 안전성이 기본 해시 함수의 안전성으로 환원될 수 있음을 증명했다. Garcia는 논문에서 단방향 해시 함수가 존재하는 경우 Merkle Hash Tree 서명이 안전하다는 것을 증명했다. 따라서 수학적 난제에 대한 안전성 환원이 입증된 해시 함수를 사용하면 Merkle 트리 전자서명의 안전성이 증명될 수 있다.
• 부호 기반 암호 – McEliece McEliece 암호 알고리즘은 NP-hard문제로 알려진 SDP(Syndrome Decoding Problem)으로 안전성 환원이 가능하다.
• 부호 기반 암호 – RLCE 2016년 Wang은 McEliece 방식을 기반으로 하는 랜덤 선형 코드 암호 알고리즘 RLCE를 제안했다. RLCE는 기본 선형 코드 생성기 행렬에 임의의 열을 삽입하여 Reed-Solomon 코드와 같은 선형 코드를 사용하여 구성할 수 있다.
• 초특이 타원 곡선 아이소제니 암호 보안성은 같은 수의 점을 가진 두 개의 초특이 곡선 사이에 아이소제니를 구성하는 문제와 관련이 있다. 이 문제와 관련된 NP-hard 문제는 없으나, 안전성에 대한 가장 최근의 조사에서 Delfs와 Galbraith이 어렵다는 것을 설명한 바 있다.

안전성 논란 해프닝

2022년 한국의 일부 언론에서 ‘국내 연구진이 양자내성암호의 주요 기반 문제인 선형 잡음 문제를 효과적으로 공략할 수 있는 양자 알고리즘이 개발’되었다고 보도한 바 있는데, 해당 기사는 격자(Lattice) 기반 암호 알고리즘의 주요 기반문제인 LWE(Learning With Error)나 LWR(Learning With Rounding)과 논문에서 해결하였다고 주장하는 선형잡음문제(Noisy Linear Problem)를 구분하지 못한데서 발생한 해프닝으로 아직까지 격자기반 양자내성암호를 해독할 수 있다는 연구결과는 존재하지 않는다.

표준화 동향

미 NSA(National Security Agency)는 2015.8월 양자내성암호의 필요성을 밝히고 2016년부터 NIST를 통해 양자내성 알고리즘 표준공모전을 진행 중이다. 이 공모전은 2020년 3라운드째의 심사 Archived 2021년 9월 25일 - 웨이백 머신를 진행 중이며, 한국에서 제언한 시스템은 2라운드까지는 진출하였으나 3라운드에서는 탈락하였다. 3라운드 심사 목록은 다음과 같다.

공개키 암호 알고리즘

• Classic McEliece
• CRYSTALS-KYBER
• NTRU
• SABER

전자서명 알고리즘

• CRYSTALS-DILITHIUM
• FALCON
• Rainbow