NIST PQC 공모전: 절차와 기준

NIST는 양자 컴퓨터가 초래하는 위협에 직접 대응하여 2016년에 Post-Quantum Cryptography(PQC) 표준화 프로젝트를 시작했습니다. Shor 알고리즘은 충분히 큰 양자 컴퓨터에서 RSA와 타원 곡선 암호를 다항 시간 안에 깨뜨릴 수 있습니다. NIST는 암호 인프라를 전환하는 데 수십 년이 걸린다는 점을 인식하고, 양자 컴퓨터가 즉각적인 위협이 되기 훨씬 전에 이 과정을 시작했습니다.

NIST는 2016년 12월에 제출 요청을 발표했고, 2017년 11월까지 완전한 제출물 82건을 받았습니다. 초기 검토 후 69건이 1라운드 후보로 채택되었습니다. 제출물은 격자 문제, 해시 함수, 코드 기반 암호, 아이소제니 기반 암호, 다변량 다항식 등 폭넓은 수학적 가정을 바탕으로 했습니다. 모든 가능성을 하나에만 걸지 않도록 가정의 다양성을 확보하는 것이 핵심 목표였습니다.

1라운드 동안 NIST와 더 넓은 암호학계는 69개 후보 모두를 집중적으로 분석했습니다. 평가 기준에는 보안(고전 및 양자 공격에 대한 저항성), 성능(키와 암호문 크기, 계산 속도), 유연성(서로 다른 보안 수준을 위한 매개변수 집합), 구현의 단순성이 포함되었습니다. 2019년 1월까지 26개 후보가 2라운드로 진출했습니다.

2라운드의 26개 후보는 더 심층적인 암호 분석과 성능 측정을 거쳤습니다. 이 라운드에서는 다변량 방식인 Rainbow와 아이소제니 기반 방식인 SIKE를 비롯한 여러 방식이 깨지거나 약화되었습니다. 다만 SIKE는 3라운드에서야 깨졌습니다. 2020년 7월까지 15개 후보가 3라운드로 진출했으며, 7개 최종 후보와 8개 대체 후보로 구성되었습니다.

3라운드의 최종 후보 7개는 KEM인 Kyber, NTRU, SABER와 서명 방식인 Dilithium, FALCON, Rainbow, SPHINCS+였습니다. 대체 후보였던 SIKE는 2022년에 극적으로 깨졌습니다. NIST는 깔끔한 설계, 강력한 보안 증명, 뛰어난 성능을 바탕으로 KEM 표준화 대상으로 Kyber를 선택했습니다. 서명 방식으로는 Dilithium, FALCON, SPHINCS+를 선택했습니다.

NIST는 향후 획기적인 발전에 대비하기 위해 서로 다른 수학적 문제에 기반한 알고리즘을 의도적으로 선택했습니다. ML-KEM과 ML-DSA는 모듈 LWE(격자)에 의존합니다. FALCON은 NTRU 격자와 가우시안 표본 추출에 의존합니다. SLH-DSA는 해시 함수의 보안에만 의존합니다. 만약 격자에 대한 획기적인 공격이 등장하더라도 SLH-DSA는 안전하게 남아 표준화된 암호 체계에 알고리즘 다양성을 제공합니다.

2022년 NIST는 격자 기반 방식 외에도 더 다양한 서명 방식을 확보하기 위해 추가 서명 후보를 특별히 모집하는 네 번째 라운드를 시작했습니다. 후보에는 다변수 및 코드 기반 가정에 기반한 MAYO, CROSS, UOV 등이 포함되었습니다. 이 과정은 처음 선정된 세 가지 표준(FIPS 203, 204, 205)을 최종 확정하는 작업과 동시에 진행되었습니다.

NIST는 2024년 8월 최종 PQC 표준을 발표했습니다. FIPS 203( Kyber 기반 ML-KEM), FIPS 204(Dilithium 기반 ML-DSA), FIPS 205(SPHINCS+ 기반 SLH-DSA)입니다. FIPS 206(FALCON 기반 FN-DSA)도 뒤이어 발표될 예정입니다. 이제 이 표준들은 US 연방 기관이 반드시 고려해야 하는 사항이 되었으며, ISO, ETSI, IETF를 통해 전 세계 표준에도 영향을 미치고 있습니다.

IETF는 PQC를 프로토콜에 빠르게 통합했습니다. 2024년에는 TLS 1.3, SSH, X.509 인증서에서 ML-KEM을 사용하기 위한 RFC 초안이 작성되고 있었습니다. Cloudflare, Google, Amazon은 TLS 스택에 ML-KEM을 배포할 계획을 발표했습니다. Apple은 ML-KEM을 사용해 래칫 기반 양자 이후 순방향 비밀성을 제공하는 iMessage용 PQ3를 발표했고, 10억 대가 넘는 기기에 배포했습니다.

NIST PQC 경쟁은 개방적이고 협력적인 암호 표준화가 효과적으로 작동한다는 사실을 보여 주었습니다. 이 과정에서 높은 평가를 받던 여러 방식(GeMSS, SIKE, Rainbow)이 깨졌으며, 이를 통해 광범위한 공개 암호 분석의 중요성이 입증되었습니다. 또한 이 경쟁은 효율적인 하드웨어 구현과 공개 소스 라이브러리(liboqs, PQClean)의 개발을 촉진하여 도입을 앞당겼습니다.

양자 이후 표준화는 아직 완료되지 않았습니다. NIST는 다양한 서명을 확보하기 위해 추가 서명 방식을 계속 평가하고 있습니다. X9 금융 표준 기관은 은행 업무를 위한 PQC 표준을 개발하고 있습니다. ETSI와 ISO는 NIST FIPS와 표준을 조정하고 있습니다. 의료(HIPAA의 영향), 국방(NSA CNSA 2.0 제품군), 통신(5G/6G를 위한 3GPP) 등 특정 분야를 위한 전환 지침도 개발되고 있습니다.

NIST PQC 경쟁에서 최초 제출작 중 몇 개의 후보가 2라운드로 진출했습니까?

NIST는 2016년에 PQC 표준화 프로젝트를 시작했고, 완성된 제출작 69개를 접수했습니다. 세 차례의 평가 라운드를 거치며 보안, 성능, 다양성을 기준으로 후보군을 좁혔습니다. 최종 선정작은 Kyber(ML-KEM, FIPS 203), Dilithium(ML-DSA, FIPS 204), SPHINCS+(SLH-DSA, FIPS 205), FALCON(FN-DSA, FIPS 206)이었습니다. 이 경쟁은 공개 암호 분석의 유효성을 입증했으며, 현재 TLS, SSH, 메시징 프로토콜에 통합되고 있는 널리 도입된 표준을 만들어 냈습니다.