KpqC 최종 4종 정리｜AIMer·HAETAE·NTRU+·SMAUG-T는 각각 무엇인가

PQC 얘기를 하면 거의 다 NIST 쪽으로 흘러갑니다. ML-KEM, ML-DSA, FIPS 203. 그런데 한국에도 따로 골라 놓은 양자내성암호 알고리즘이 네 개 있습니다. AIMer, HAETAE, NTRU+, SMAUG-T입니다.

이름만 들으면 뭐가 뭔지 감이 안 옵니다. 서명인지 KEM인지, 격자인지 아닌지, NIST 표준이랑 무슨 관계인지. 최종 규격서가 2026년 1월에 공개됐는데 한국어로 정리된 글은 거의 없더라고요. 그래서 공식 문서를 직접 열어 보고 정리했습니다. ML-KEM이 결국 KEM이라는 이야기를 먼저 보고 오시면 훨씬 편합니다.

KpqC가 뭔지부터

양자내성암호연구단(KpqC 연구단)이 2021년에 발족했고, 여기서 연 공모전이 KpqC 공모전입니다. 일정은 이렇게 흘러갔습니다.

• Round 1 — 2022년 11월 ~ 2023년 11월. 2023년 12월 7일에 2라운드 진출 8종 발표(서명 AIMer·HAETAE·MQ-Sign·NCC-Sign, KEM NTRU+·PALOMA·REDOG·SMAUG+TiGER 병합).
• Round 2 — 2024년 4월 ~ 2024년 11월. 2025년 1월 16일에 최종 4종 발표.
• 최종 규격서 공개 — 연구단 페이지 기준 2026년 1월 30일. 문서 자체 날짜는 AIMer·NTRU+가 1월 30일, HAETAE·SMAUG-T가 2월 4일입니다.

규격서마다 SHA-256 무결성 해시가 표지에 박혀 있습니다. 사내에서 문서를 돌려 볼 일이 있으면 이 값으로 대조해 두는 게 좋습니다.

중요한 단서 하나 — 아직 국가표준은 아닙니다

이 부분을 먼저 못 박고 갑니다. 연구단이 공개한 소개 글에는 앞으로 "KpqC 알고리즘의 국가표준화 추진을 지원"하겠다고 적혀 있습니다. 추진을 지원하겠다는 말이지, 이미 국가표준이 됐다는 말이 아닙니다.

그러니까 "KpqC 4종 = 국내 표준"이라고 말하면 지금은 틀립니다. 공모전을 통해 선정된 국내 개발 알고리즘이고, 표준화는 진행할 일로 남아 있는 상태입니다. 제안서나 내부 보고서에 쓸 때 이 한 줄 차이가 꽤 큽니다.

같은 맥락에서 하나 더. 연구단은 이 4종을 "순수 국내 기술로 개발된" 알고리즘이라고 소개합니다. 다만 규격서의 저자 목록을 보면 HAETAE에는 프랑스 ANSSI, 독일 보훔 루르대, 룩셈부르크대, Intel 소속 공동저자가 들어가 있습니다. 국내 주도로 만들어진 건 맞지만 문서상으로는 국제 공동 작업의 성격도 함께 있다고 보는 쪽이 정확합니다.

서명 2종

AIMer — 이 중에 격자가 아닌 유일한 하나

네 개 중 성격이 가장 다릅니다. AIMer는 격자 문제에 기대지 않습니다. 대신 MPC-in-the-Head라는 영지식증명 방식(BN++ 계열)과 AIM2라는 대칭키 프리미티브를 조합해서 만듭니다. 서명이란 게 결국 "내가 이 일방향 함수의 입력값을 안다"는 걸 증명하는 일인데, 그 증명을 대칭암호 위에서만 굴리는 구조입니다.

그래서 문서가 이렇게 적어 놨습니다. "AIMer의 보안은 오직 기반 대칭 프리미티브의 보안에만 의존한다." 격자 가정이 흔들리는 날이 와도 이쪽은 따로 서 있다는 뜻이라, 한 바구니에 다 담지 않는다는 관점에서 값이 있습니다.

대가도 분명합니다. 규격서의 한계 항목에 "표준화된 격자 기반 방식에 비해 서명 크기가 상대적으로 크다"고 직접 적혀 있어요. 대신 키는 아주 작습니다. 공개키가 (iv, ct) 두 값뿐이라 L1에서 32바이트 수준입니다. 인증서를 자주 주고받는 PKI 환경에 유리하다고 문서도 그 점을 장점으로 듭니다.

파라미터는 보안수준 L1/L3/L5마다 f(빠른 쪽)와 s(작은 쪽) 두 갈래로 총 6종입니다. 문서의 서명 크기 공식 |σ| = (5 + (log₂N + ℓ + 5)·τ)·λ 비트에 Table 4 값을 넣어 계산하면 AIMer-128s가 약 4.1KB, AIMer-128f가 약 5.9KB, AIMer-256s가 약 17KB 정도 나옵니다. ML-DSA나 HAETAE와 비교하면 확실히 큰 편이고, 이게 곧 속도와 크기를 골라 쓸 수 있는 구조이기도 합니다.

HAETAE — Dilithium을 더 작게 만든 쪽

HAETAE는 격자 기반 서명입니다. NIST가 고른 Dilithium(ML-DSA)과 같은 Fiat-Shamir with Aborts 계열인데, 설계 선택을 바꿔서 크기를 줄였습니다. 핵심은 y를 초구(hyperball) 위 균등분포에서 뽑고 이중모드(bimodal)를 쓰는 부분입니다.

결과가 숫자로 나옵니다. 규격서 Table 3 기준입니다.

• HAETAE-120 (레벨 2) — 검증키 992B, 서명 1,474B / Dilithium-2는 1,312B, 2,420B
• HAETAE-180 (레벨 3) — 검증키 1,472B, 서명 2,349B / Dilithium-3은 1,952B, 3,293B
• HAETAE-260 (레벨 5) — 검증키 2,080B, 서명 2,948B / Dilithium-5는 2,592B, 4,595B

문서 표현으로 서명은 29~39%, 검증키는 20~25% 작습니다. 설계 목표도 명확히 적혀 있어요. 서명이 TCP·UDP 데이터그램 하나에 들어가게 하는 것. 패킷 하나를 넘기느냐 마느냐가 성능을 가르는 환경을 노린 겁니다.

Falcon과의 비교도 문서가 먼저 꺼냅니다. Falcon은 크기는 작지만 가우시안 샘플링 때문에 구현과 부채널 대응이 까다로운데, HAETAE의 거부 단계는 유클리드 노름 계산뿐이고 서명 전체를 고정소수점 연산으로 구현할 수 있다고 주장합니다.

KEM 2종

NTRU+ — NTRU 계열을 NTT 친화적으로

NTRU는 1998년에 나온 오래된 격자 암호입니다. 오래됐다는 건 그만큼 오래 두들겨 맞고도 살아남았다는 뜻이라 그 자체로 자산인데, 실무적으로는 불편한 구석이 있었습니다. 모듈러스를 적당히 두면 최악의 경우 오류 확률을 충분히 낮추기 어렵고, 메시지 샘플링이 복잡하고, 속도가 다른 격자 방식보다 느렸습니다.

NTRU+는 그 세 가지를 겨냥합니다. ACWC2와 FO 변환을 이어 붙이고, SOTP라는 인코딩 방식을 새로 써서 일반 비트열 공간에서 임의 분포로 뽑은 메시지를 그대로 쓸 수 있게 했습니다. 상수시간 구현에서 거부 샘플링이 골치였던 문제가 여기서 풀립니다. 복호화 때 재암호화를 하지 않는 구조라 복호화도 더 빠릅니다.

파라미터는 NTRU+768 / 864 / 1152 세 종이고 모듈러스 q는 전부 3457입니다. 규격서 Table 7 기준으로 NTRU+768은 공개키·암호문이 각각 1,152B이고 고전 기준 156비트 보안입니다. Kyber와 견주면 대역폭은 조금 더 크지만(Kyber가 압축을 쓰니까요) 키생성·캡슐화·복호캡슐화 속도는 C 최적화와 AVX2 양쪽에서 더 빠르다고 적혀 있습니다.

SMAUG-T — 암호문이 가장 작은 쪽

1라운드의 SMAUG와 TiGER가 합쳐져서 나온 알고리즘입니다. MLWE와 MLWR을 같이 쓰고, 비밀값을 희소(sparse)하게 뽑는 SMAUG 방식을 따릅니다. MLWR 쪽을 암호화에 쓰면 log q / log p 만큼 암호문이 줄어든다는 게 설계의 출발점이에요.

그래서 문서가 내세우는 지점이 크기입니다. Kyber 대비 암호문 최대 14%, 공개키 최대 19% 작고, 캡슐화는 상수시간 C 구현에서 최대 60%, AVX2에서 최대 70% 빠르다고 적혀 있습니다. 규격서 Table 3 기준 SMAUG-T Mode 1은 공개키 672B·암호문 672B, Mode 3은 1,088B·992B, Mode 5는 1,440B·1,376B입니다.

파라미터 하나가 더 있습니다. TiMER인데, 메시지 공간을 줄이고 오류 정정(error reconciliation)을 써서 크기와 복호 실패 확률을 더 낮춘 IoT용 세트입니다. 공개키 672B에 암호문 608B로, 네 세트 중 암호문이 가장 작습니다. 대역폭이 진짜 아쉬운 장비를 다루고 있다면 여기부터 보면 됩니다.

한 장으로 정리

알고리즘	용도	기반	한 줄 특징
AIMer	서명	대칭 프리미티브 + MPCitH	격자 아님. 키는 아주 작고 서명은 큼
HAETAE	서명	MLWE / MSIS (격자)	Dilithium보다 서명 29~39% 작음
NTRU+	KEM	NTRU / RLWE (격자)	NTT 친화 링, Kyber보다 빠름
SMAUG-T	KEM	MLWE / MLWR (격자)	암호문이 작음, IoT용 TiMER 세트

보시면 네 개 중 셋이 격자입니다. NIST가 고른 ML-KEM·ML-DSA도 격자죠. 격자 하나에 얼마나 몰려 있는지를 생각하면 AIMer의 자리가 왜 따로 의미가 있는지 보입니다.

그래서 실무에서 뭘 하면 되나

솔직하게 적겠습니다. 국내 규제나 인증 기준에서 NIST 표준과 KpqC 중 어느 쪽이 요구되는지는 이 글에서 단정하지 않겠습니다. 확인된 1차 출처 없이 쓸 수 있는 내용이 아니고, 앞서 적었듯 KpqC의 국가표준화는 아직 추진 대상입니다.

대신 지금 해 둘 수 있는 일은 분명합니다.

• 암호 인벤토리부터. 어디서 RSA·ECC를 쓰고 있는지 모르면 어느 표준을 고르든 못 옮깁니다. 2035년 일정을 읽는 법에서 다룬 것과 같은 이야기입니다.
• 알고리즘을 갈아끼울 수 있게 설계. NIST냐 KpqC냐가 나중에 정해져도 버틸 수 있으면 지금 결정을 미뤄도 됩니다. 키를 어디에 두고 누가 꺼내 쓰는지 정리해 두는 게 출발점이라 HSM과 KMS의 역할 구분이 여기서 또 걸립니다.
• KpqC는 후보로 올려 두기. 특히 국내 공공·국방 쪽 요구가 걸릴 가능성이 있는 조직이라면, 규격서와 구현 패키지가 전부 공개돼 있으니 지금 읽어 두는 비용이 싸요.

출처

이 글의 사실관계는 2026년 9월 24일에 아래 1차 출처에서 직접 확인했습니다.

• 양자내성암호연구단 KpqC Algorithms 페이지 및 AIMer·HAETAE·NTRU+·SMAUG-T 최종 규격서 PDF — kpqc.or.kr
• KpqC Competition Round 1 / Round 2 결과 페이지 — kpqc.or.kr
• 연구단 소개(목적) 페이지 — kpqc.or.kr

알고리즘 크기와 성능 수치는 각 규격서의 표에 적힌 값이고, AIMer 서명 크기는 규격서의 공식에 Table 4 파라미터를 대입해 계산한 근삿값입니다. 저는 이 알고리즘들을 직접 운영 환경에 넣어 본 적은 없습니다. 문서에 적힌 내용을 정리한 글이니 구현할 때는 규격서와 참조 코드를 다시 확인하세요.