ML-DSA (FIPS 204) 및 SLH-DSA (FIPS 205)

FIPS 204로 표준화된 ML-DSA(Module-Lattice-based Digital Signature Algorithm)는 CRYSTALS-Dilithium에서 파생되었습니다. Dilithium은 Ducas, Kiltz, Lepoint, Lyubashevsky, Schwabe, Seiler, Stehle이 설계했으며 2017년에 NIST에 제출했습니다. 이 방식은 Module-LWE에 적용한 Fiat-Shamir 중단 프레임워크를 사용하여, 강력한 보안 증명을 갖춘 실용적인 서명 방식을 만듭니다.

고전적인 Fiat-Shamir 변환은 상호작용형 식별 프로토콜을 서명으로 변환합니다. 격자 방식에 이를 직접 적용하면 응답 벡터를 통해 비밀 키 정보가 누출됩니다. Lyubashevsky가 제안한 "중단 포함" 기법은 거부 표본 추출을 추가합니다. 서명자는 응답이 정보를 드러내는지 확인하고, 그런 경우 중단한 뒤 다시 시도합니다. 이 과정에서는 서명에 약간의 추가 비용이 발생하지만 보안을 위해 필수적입니다.

서명할 때 ML-DSA는 균등 분포에서 마스킹 벡터 y를 추출하고, 커밋값 w = Ay를 계산한 다음, (message, w)를 해시하여 도전 다항식 c를 얻고, 응답 z = y + cs를 계산합니다. 거부 표본 추출을 통해 z가 s에 관한 정보를 드러내는지 확인합니다. 검사를 통과하면 서명은 (c, z)와 효율적인 검증을 위한 보조 정보로 구성됩니다. 통과하지 못하면 과정을 반복합니다.

ML-DSA는 세 가지 매개변수 집합을 정의합니다. ML-DSA-44는 NIST 보안 수준 2(약 128비트), ML-DSA-65는 수준 3(약 192비트), ML-DSA-87은 수준 5(약 256비트)입니다. 숫자는 이 방식에서 사용하는 모듈의 랭크를 나타냅니다. 공개 키 크기는 각각 1312, 1952, 2592바이트입니다. ML-DSA-65의 서명 크기는 3293바이트로, 128비트 보안의 Ed25519가 64바이트인 것과 비교됩니다.

ECDSA 또는 EdDSA와 비교했을 때 ML-DSA의 가장 큰 단점은 서명 크기입니다. ML-DSA-65의 서명은 3293바이트인 반면 Ed25519의 서명은 64바이트입니다. TLS 인증서 체인이나 코드 서명처럼 많은 서명을 전송하는 프로토콜에서는 대역폭 사용량이 증가합니다. 그러나 ML-DSA의 서명과 검증은 매우 빠르므로(ECDSA와 비슷하거나 더 빠름) 주된 절충점은 통신 비용입니다.

FIPS 205로 표준화된 SLH-DSA(Stateless Hash-Based Digital Signature Algorithm)는 SPHINCS+에서 파생되었습니다. 격자 방식과 달리 SLH-DSA의 보안은 기반 해시 함수(SHA-256 또는 SHAKE-256)의 충돌 저항성과 제2 원상 저항성에만 의존합니다. 따라서 SLH-DSA는 매우 보수적인 방식이며, 격자 가정이 깨지더라도 보안을 유지합니다.

SLH-DSA는 WOTS+(Winternitz One-Time Signature)를 기반으로 합니다. WOTS+는 개인 키가 무작위 문자열의 집합이고 각 문자열을 반복해서 해시하여 공개 키를 얻는 해시 기반 방식입니다. 서명할 때는 메시지 비트에 따라 부분적으로 해시합니다. WOTS+는 한 키 쌍에서 안전하게 한 번만 사용할 수 있으며, 두 번 사용하면 정보가 누출됩니다. SLH-DSA는 트리를 통해 WOTS+ 위에 여러 번 사용할 수 있는 서명 기능을 구축합니다.

SLH-DSA는 머클 트리로 이루어진 트리인 하이퍼트리를 사용합니다. 각 잎은 하나의 WOTS+ 인스턴스의 공개 키입니다. 루트는 SLH-DSA 공개 키입니다. 하나의 서명은 메시지에 대한 WOTS+ 서명과 잎에서 루트까지의 인증 경로로 구성됩니다. 하이퍼트리 구조에서는 서로 다른 WOTS+ 잎을 사용하여 하나의 키 쌍으로 여러 번 서명할 수 있습니다.

SLH-DSA에는 해시 함수(SHA-256 또는 SHAKE-256), 보안 수준(128s/128f, 192s/192f, 256s/256f), 최적화(s = 작은 서명, f = 빠른 서명 생성)를 조합한 12개의 매개변수 집합이 있습니다. 128f 변형은 서명이 7856바이트이고 서명 생성이 빠릅니다. 128s도 7856바이트이지만 더 느립니다. 모든 변형은 ML-DSA보다 훨씬 크지만 가장 강력한 보안 가정을 사용합니다.

성능과 대역폭이 중요하고 격자 가정을 신뢰할 수 있다면 ML-DSA를 선호합니다. 해시 함수의 보안만 신뢰할 수 있는 매우 보수적인 배포 환경이나 잠재적인 격자 방식의 붕괴에 대비해야 하는 경우에는 SLH-DSA를 선호합니다. 드물게 서명하지만 최대한의 보증이 필요한 인증 기관과 정부 시스템은 SLH-DSA를 선호할 수 있으며, 자주 서명하는 TLS 서버는 ML-DSA를 선호할 수 있습니다.

FN-DSA(FIPS 206, FALCON 기반)는 NTRU 격자와 가우시안 샘플링을 사용하여 ML-DSA보다 더 짧은 서명을 제공합니다(128비트 보안 수준에서 FALCON-512의 서명 크기는 897바이트). 그러나 FALCON은 가우시안 샘플러에서 발생하는 부채널 공격을 방지하려면 신중한 일정 시간 구현이 필요합니다. FIPS 206은 FIPS 203~205 이후에 표준화될 예정이며, 리소스가 제한된 환경을 위한 고성능 선택지를 제공할 것입니다.

SLH-DSA가 ML-DSA보다 갖는 주요 보안상의 장점은 무엇입니까?

ML-DSA(FIPS 204)는 Module-LWE에서 중단을 포함한 Fiat-Shamir 방식을 사용하며, 3KB 서명으로 빠른 서명을 제공합니다(192비트 보안 수준). SLH-DSA(FIPS 205)는 해시 기반 Merkle 트리(WOTS+)를 사용하고 해시 함수의 보안성에만 의존하며, 서명 크기는 7~50KB입니다. ML-DSA는 성능이 중요한 응용 분야에 적합하고, SLH-DSA는 최대한 보수적인 보안이 필요한 경우에 적합합니다. FN-DSA(FALCON, FIPS 206)는 더 작은 서명을 제공하는 격자 기반 선택지를 추가할 예정입니다.