양자컴퓨터 시대의 디지털 서명 경쟁,
NIST 3라운드 진출 9개 알고리즘
NIST가 추가 디지털 서명을 다시 선발하는 이유
양자컴퓨터가 충분히 발전하면 오늘날 널리 사용되는 공개키 암호의 상당 부분이 영향을 받을 수 있다. 특히 디지털 서명은 웹 브라우징, 소프트웨어 업데이트, 전자문서, 인증서, DNS 보안 등 다양한 시스템에서 신원과 데이터의 무결성을 증명하는 핵심 기술이다.
미국 국립표준기술연구소(NIST)는 이러한 변화에 대비하기 위해 2016년부터 포스트양자암호(PQC) 표준화 절차를 진행해 왔다. 이미 NIST는 격자 기반 디지털 서명인 ML-DSA와 해시 기반 디지털 서명인 SLH-DSA 등을 표준화했지만, 특정 수학적 가정에 대한 의존도를 낮추고 더 다양한 성능 특성을 확보하기 위해 추가 후보군을 검토하고 있다.
2026년 5월 발표된 NIST IR 8610은 추가 디지털 서명 표준화 절차의 2라운드 결과를 담은 보고서다. NIST는 2라운드에 진입한 14개 후보 중 FAEST, HAWK, MAYO, MQOM, QR-UOV, SDitH, SNOVA, SQIsign, UOV 등 9개를 3라운드 후보로 선정했다.
이번 발표는 최종 표준 선정이 아니다. 9개 알고리즘이 추가 분석과 공개 검토를 받을 자격을 얻었다는 의미에 가깝다.
50개 제출안에서 9개 후보까지
추가 디지털 서명 절차는 기존 표준을 보완할 수 있는 알고리즘을 찾기 위해 시작됐다. NIST는 특히 다음과 같은 방향을 중요하게 봤다.
•기존 표준과 다른 비격자 기반 보안 가정을 제공할 것
•짧은 서명이나 빠른 검증 등 뚜렷한 성능상 이점을 가질 것
•다양한 하드웨어와 소프트웨어 환경에서 구현 가능할 것
•보안 분석과 실제 배포를 뒷받침할 만큼 설계가 성숙할 것
2023년 6월까지 총 50개의 제출안이 접수됐고, 이 가운데 40개가 1라운드 후보로 받아들여졌다. 이후 1년 이상에 걸친 검토를 통해 14개가 2라운드에 진입했다. 2라운드는 2024년 10월 24일 시작해 2026년 5월 14일까지 진행됐다.
NIST는 무엇을 기준으로 평가했나
NIST의 평가 기준은 크게 보안, 비용과 성능, 알고리즘 및 구현 특성의 세 가지로 나뉜다. 중요도 역시 대체로 이 순서를 따른다.
1. 보안
가장 중요한 기준은 위조 저항성이다. 디지털 서명은 공격자가 메시지를 선택해 서명을 관찰한 뒤에도 새로운 유효 서명을 만들어낼 수 없어야 한다. NIST는 최소한 EUF-CMA라는 선택 메시지 공격에 대한 존재적 위조 불가능성을 요구했고, 더 강한 보안 정의인 SUF-CMA도 바람직한 특성으로 보았다.
평가 과정에서는 제출팀의 보안 증명뿐 아니라 외부 연구자들이 제시한 암호분석 결과도 함께 검토됐다. 2라운드 동안 일부 후보는 새로운 공격을 받았고, 특히 다변수 암호 계열에서는 제안된 파라미터의 보안 수준이 크게 조정된 경우가 있었다.
2. 비용과 성능
보안만 충분하다고 표준이 되는 것은 아니다. 공개키, 개인키, 서명 크기와 함께 키 생성, 서명, 검증에 필요한 연산량을 고려해야 한다. 메모리 사용량과 하드웨어 구현 시 필요한 회로 규모도 평가 대상이다.
2라운드에서는 MPC-in-the-Head 계열을 중심으로 성능이 크게 개선됐다. TCitH와 VOLEitH 같은 새로운 기법이 적용되면서 서명 크기가 줄고 서명 및 검증 속도가 빨라졌다. SQIsign 역시 구조를 바꿔 서명 속도와 검증 속도를 향상시켰고, LESS는 정규형을 활용해 서명 크기를 줄였다.
3. 알고리즘과 구현 특성
NIST는 다양한 플랫폼에서 효율적으로 동작하고, 병렬화나 명령어 확장을 활용할 수 있는 알고리즘을 선호한다. 설계가 단순할수록 보안 분석과 구현, 표준 채택이 수월하다는 점도 중요하다.
부채널 공격에 대한 저항성도 계속 검토됐다. 2라운드에서 보고된 부채널 분석 결과만으로 후보가 즉시 탈락한 사례는 없었지만, 3라운드에서는 상수 시간 구현과 부채널 방어가 중요한 과제가 될 전망이다.
3라운드에 진출한 9개 알고리즘
NIST는 14개 2라운드 후보 중 다음 9개를 3라운드로 올렸다.
HAWK: Falcon의 대안이 될 수 있을까
HAWK는 격자 기반 해시-앤드-사인 방식의 디지털 서명이다. Falcon과 비슷한 면이 있지만, HAWK는 부동소수점 연산에 의존하지 않고 정수 연산만으로 구현할 수 있다는 점이 특징이다.
NIST 보고서에 따르면 HAWK의 보안 카테고리 1 서명 크기는 555바이트로, Falcon이나 ML-DSA보다 작다. 부동소수점 장치가 부족한 임베디드 환경이나 제한된 하드웨어에서 구현이 비교적 수월할 수 있다는 점도 장점이다.
다만 HAWK의 기반이 되는 모듈 격자 문제와 관련한 보안 가정은 더 폭넓은 분석이 필요하다. NIST는 특히 특정 순환체 구조에서 해당 문제의 난도가 충분히 유지되는지 추가 검토해야 한다고 봤다.
FAEST: AES에서 출발한 포스트양자 서명
FAEST는 VOLE-in-the-Head라는 영지식 증명 프레임워크를 활용하고, AES와 같은 대칭키 암호를 중심으로 구성된다. 공개키 암호의 새로운 수학적 구조보다는 비교적 잘 연구된 대칭키 원시함수에 보안을 의존하려는 접근이다.
2라운드에서 FAEST는 성능을 개선하고 양자 랜덤 오라클 모델에서의 보안 증명을 보완했다. 물리적 구현에 대한 부채널 및 결함 주입 공격 연구도 있었지만, NIST는 이것이 기본적인 암호학적 보안을 무너뜨리는 결과는 아니라고 평가했다.
FAEST가 선정된 배경에는 MPC-in-the-Head 후보 가운데 경쟁력 있는 성능과 함께, 비교적 보수적인 보안 기반을 제공한다는 점이 있었다.
MQOM과 SDitH: MPC-in-the-Head 계열의 대표 후보
MQOM은 유한체 위의 무작위 이차방정식 시스템을 푸는 문제를 기반으로 한다. 2라운드 버전은 TCitH 계열 기법을 적용해 서명 크기를 줄였으며, 3개 보안 수준 모두에서 MPC-in-the-Head 후보 중 공개키와 서명의 합산 크기가 가장 작았다.
반면 MQOM은 보안 증명, 특히 양자 공격자를 고려한 모델에서 추가 정교화가 필요하다. 성능이 매우 좋더라도 증명의 완성도와 설계 변경의 안정성이 함께 검증돼야 한다는 의미다.
SDitH는 랜덤 선형 코드에 대한 신드롬 복호 문제를 기반으로 한다. 이 문제는 오랫동안 연구돼 온 만큼 보안 가정이 비교적 보수적이라는 평가를 받았다. 다만 다른 MPC 계열 후보보다 연산 비용이 높을 수 있어, 보안성과 성능 사이의 균형이 핵심 과제로 남아 있다.
SQIsign: 가장 작은 키와 서명을 노리는 후보
SQIsign은 아이소제니 기반 구조를 사용하는 서명 방식이다. NIST는 2라운드 후보 가운데 SQIsign이 공개키와 서명을 합친 크기가 가장 작다고 평가했다. 보안 카테고리 1에서 서명 크기는 148바이트까지 줄었다.
2라운드 동안 SQIsign은 내부 구조를 크게 개선했다. 그 결과 서명 속도는 약 20배, 검증 속도는 약 6배 향상됐다. 다만 서명 절차가 수학적으로 복잡하고 완전한 상수 시간 구현이 어렵다는 문제가 있다. 부분적인 부채널 정보가 공격에 활용될 가능성도 계속 연구해야 한다.
SQIsign은 매우 작은 서명이라는 독보적인 장점을 제공하지만, 비교적 새로운 보안 가정과 구현 난도가 다음 라운드의 주요 검증 대상이다.
UOV, MAYO, QR-UOV, SNOVA: 다변수 암호의 재도전
다변수 암호 계열은 작은 서명과 빠른 검증을 제공할 수 있지만, 공개키가 커지는 경우가 많다. 이번 2라운드에서도 여러 다변수 후보가 새로운 공격을 받았다. 그럼에도 NIST는 네 후보 가운데 UOV, MAYO, QR-UOV, SNOVA를 모두 3라운드에 남겼다.
UOV는 1990년대부터 연구된 대표적인 다변수 서명 구조다. 보안 카테고리 1에서 서명 크기를 96바이트까지 줄일 수 있고 검증도 빠르지만, 확장된 공개키가 200킬로바이트를 넘을 수 있어 범용 표준보다는 특정 애플리케이션에 적합할 가능성이 있다.
MAYO는 UOV 구조를 변형해 공개키 크기를 줄인 방식이다. 다변수 후보 중 공개키 크기가 작은 편이고 서명과 검증 효율도 유지한다. 다만 일부 카테고리 1 파라미터는 웨지 공격의 영향을 크게 받았기 때문에, 파라미터 선택을 다시 검토해야 한다.
QR-UOV는 몫환을 사용해 UOV보다 공개키를 약 15~50% 줄인다. 2라운드 동안 웨지 공격에 상대적으로 잘 견디는 특성을 보였고, 서명과 검증 속도도 1라운드보다 크게 개선됐다. NIST는 이러한 보안 프로파일과 성능 개선을 긍정적으로 평가했다.
SNOVA는 네 다변수 후보 중 공개키 크기를 가장 공격적으로 줄이는 구조를 갖는다. 일부 파라미터에서는 Falcon보다 공개키와 서명이 모두 작을 수 있다. 그러나 1·2라운드에서 여러 공격을 받았고, 제안된 파라미터 상당수가 영향을 받았다. NIST는 SNOVA의 가능성을 인정하면서도 아직 설계가 안정된 단계는 아니며, 표준화까지는 더 긴 평가 시간이 필요하다고 명시했다.
왜 CROSS와 LESS는 탈락했나
2라운드에서 탈락한 두 후보는 CROSS와 LESS다. 탈락은 해당 알고리즘이 즉시 안전하지 않다는 단정이라기보다, 기존 표준 및 남은 후보와 비교했을 때 표준화 후보로 계속 검토할 만큼 차별적 이점과 성숙도가 충분하지 않았다는 뜻이다.
CROSS는 작은 공개키를 제공하지만 서명이 매우 크다. 성능 특성은 SLH-DSA와 비슷한데, CROSS가 의존하는 보안 문제는 SLH-DSA의 기반 문제보다 연구 역사가 짧다. 2라운드 중 공격으로 파라미터를 수정한 점까지 고려해 NIST는 성능상의 이점이 보안 불확실성을 상쇄할 만큼 크지 않다고 판단했다.
LESS는 작은 서명이 장점이지만 공개키가 매우 크고 키 생성, 서명, 검증이 CROSS보다 느리다. 2라운드에서 공격이 제시되면서 보안에 대한 이해도 추가로 흔들렸다. 결국 작은 서명이라는 장점만으로는 3라운드 진출을 정당화하기 어려웠다.
NIST 보고서는 3라운드에 선정되지 않은 알고리즘은 더 이상 NIST 표준화를 위한 후보로 고려하지 않는다고 명시한다.
이번 결과가 보여주는 세 가지 흐름
첫째, 보안 가정의 다양성이 중요해졌다
기존 표준이 격자와 해시에 크게 의존하는 상황에서 NIST는 단일 수학적 가정에 모든 미래 보안을 걸지 않으려 한다. MPC-in-the-Head, 다변수, 아이소제니 기반 후보가 함께 남은 것은 알고리즘 포트폴리오를 다변화하려는 방향을 보여준다.
둘째, 파라미터 선택이 알고리즘 설계만큼 중요하다
UOV 계열 사례에서 확인되듯 같은 기본 구조라도 파라미터에 따라 공격의 영향이 크게 달라질 수 있다. 따라서 “이 알고리즘은 안전하다”라는 표현만으로는 부족하다. 어떤 파라미터 세트를 사용하고, 그 파라미터가 어떤 공격 모델에서 어느 정도의 보안 여유를 갖는지까지 확인해야 한다.
셋째, 최종 표준화까지는 여전히 긴 검증이 필요하다
NIST는 3라운드 후보에게 사양과 소스 코드의 오류 및 문제를 수정할 기회를 부여했다. 2026년 8월 14일까지 업데이트된 제출 패키지를 받도록 했으며, 향후에는 공개 암호분석, 최적화된 소프트웨어 구현, 제한된 플랫폼에서의 적합성, 하드웨어 구현 성능을 추가로 검토할 계획이다.
NIST는 2027년 상반기에 다음 PQC 표준화 회의를 개최할 계획이라고 밝혔다. 따라서 이번 9개 후보 발표는 결승선이 아니라, 실제 표준화 가능성을 가르는 더욱 집중적인 검증 단계의 시작이다.
마무리: 가장 빠른 알고리즘보다 오래 검증된 알고리즘이 중요하다
NIST의 2라운드 결과는 포스트양자 디지털 서명 경쟁이 단순한 속도와 크기 비교가 아니라는 점을 보여준다. 짧은 서명, 작은 공개키, 빠른 검증은 분명 중요하지만, 새로운 공격이 등장했을 때 얼마나 빠르게 보안 수준을 재평가할 수 있는지, 보안 증명이 얼마나 성숙했는지, 실제 구현에서 부채널 공격을 막을 수 있는지도 같은 비중으로 중요하다.
현재 3라운드 후보 가운데 특정 알고리즘이 최종 표준으로 확정됐다고 볼 수는 없다. HAWK와 SQIsign은 독특한 성능상 이점을, FAEST·MQOM·SDitH는 MPC-in-the-Head 계열의 서로 다른 보안과 성능 조합을, UOV·MAYO·QR-UOV·SNOVA는 짧은 서명과 다변수 기반의 다양성을 제공한다.
앞으로의 핵심 질문은 세 가지다. 새로운 공격에도 살아남는가, 실제 시스템에서 구현 가능한가, 그리고 기존 표준과 비교해 추가 표준으로 채택할 충분한 이유가 있는가다. NIST의 이번 보고서는 이 질문에 답하기 위한 다음 검증 라운드의 출발점이다.
