CRYSTALS-Dilithium 및 Falcon 서명

RSA와 ECDSA 서명은 쇼어 알고리즘으로 해독됩니다. 다음 분야에서는 포스트양자 서명으로 대체해야 합니다. TLS 인증서, 코드 서명, 이메일 서명(S/MIME, PGP), 소프트웨어 업데이트 인증입니다. NIST는 두 가지 격자 기반 방식인 ML-DSA와 FN-DSA를 표준화했습니다.

딜리시움은 Module-LWE와 Module-SIS(Short Integer Solution)의 어려움에 기반합니다. 보안 증명은 QROM(양자 무작위 오라클 모델)에서 이루어집니다. 세 가지 변형은 딜리시움2(약 128비트), 딜리시움3(약 192비트), 딜리시움5(약 256비트)입니다. 구조가 단순하며 서명 경로에 거부 샘플링이 없습니다.

개인키는 비밀 행렬 s1, s2입니다. 공개키는 t = As1 + s2입니다. 서명할 때 무작위 y를 샘플링하고 w = Ay를 계산합니다. w1 = HighBits(w)일 때 챌린지 c = H(mu || w1)을 계산합니다. z = y + cs1을 계산한 뒤 ||z|| 또는 ||r0||가 너무 크면 거부하고 다시 시도합니다. 출력은 (z, c, hint)입니다.

(z, c, hint)를 검증하려면 ||z||가 작은지 확인하고 w' = Az - ct를 계산합니다. hint를 사용하여 w1을 복원한 다음 c == H(mu || w1)인지 확인합니다. hint는 MakeHint()에서 얻는 소수의 비트입니다. z가 s1을 유출하지 않도록 거부하며, 보안 논증은 "중단 후 균일" 논증입니다.

ML-DSA-65(딜리시움3, 192비트 보안)의 공개키는 1952바이트, 개인키는 4000바이트, 서명은 3293바이트입니다. ECDSA-P256과 비교하면 공개키는 64바이트이고 서명은 64바이트입니다. 딜리시움은 서명 크기가 약 40~50배 크지만 양자 컴퓨터에 안전합니다.

팔콘은 NTRU 격자에 기반하며 NTRU 격자에서 가우시안 샘플러를 사용합니다. 서명은 딜리시움보다 훨씬 작지만, 서명하려면 부동소수점 가우시안 샘플러가 필요합니다. 따라서 상수 시간으로 구현하기가 더 어렵고 보안 코드를 작성하는 일도 더 복잡합니다.

Falcon-512(128비트 보안)의 공개키는 897바이트, 서명은 666바이트로 딜리시움보다 훨씬 작습니다. 대신 팔콘은 안전하게 구현하기가 더 어렵습니다. 가우시안 샘플링이 타이밍 공격에 취약하기 때문입니다. 대역폭이 제한된 환경에 적합하지만 신중한 구현이 필요합니다.

SPHINCS+는 해시 기반 서명 방식으로, 구조적 대수 가정을 사용하지 않는 보수적인 선택입니다. 보안은 해시 함수의 보안성에만 의존합니다. 서명 크기는 약 8~50KB로 크고 서명 속도는 느립니다. 장기적인 신뢰가 중요하고 성능이 부차적인 환경에서 사용됩니다.

ML-DSA(딜리시움)는 범용 방식으로 구현이 단순하며 TLS 인증서와 코드 서명에 적합합니다. FN-DSA(팔콘)는 IoT와 LPWAN처럼 대역폭이 제한된 환경에 적합합니다. SLH-DSA(SPHINCS+)는 매우 보수적인 방식으로, 장기간 사용하는 루트(CA 오프라인 키, 소프트웨어 신뢰 루트)에 적합합니다.

딜리시움은 거부 샘플링으로 인해 분기 타이밍이 유출될 수 있으므로 상수 시간 비교를 사용해야 합니다. 팔콘은 가우시안 샘플러가 부동소수점을 사용하므로 FP 결정성을 보장해야 합니다. 두 방식 모두 다항식 연산에서 부채널이 발생하지 않도록 해야 합니다. NIST 제출 패키지의 참조 구현을 사용해야 합니다.

NIST FIPS 204는 ML-DSA(딜리시움), NIST FIPS 205는 SLH-DSA(SPHINCS+), NIST FIPS 206은 FN-DSA(팔콘)를 규정합니다. 세 표준은 모두 2024년 8월에 발표되었습니다. 라이브러리로는 OpenSSL 3.x, BoringSSL, liboqs(Open Quantum Safe 프로젝트)가 세 가지를 모두 구현합니다.

딜리시움에 비해 팔콘의 가장 큰 장점은 무엇인가요?

ML-DSA(딜리시움)는 격자 기반이고 단순하며 서명 크기는 약 3KB입니다. FN-DSA(팔콘)는 NTRU 기반이고 서명 크기는 약 700바이트이지만 구현이 복잡합니다. SLH-DSA(SPHINCS+)는 해시 기반이고 보수적이지만 크기가 큽니다. 세 방식 모두 FIPS 204/205/206으로 표준화되었습니다. 다음으로 하이브리드 접근 방식을 사용한 PQC 전환을 살펴봅니다.