1. 전자서명(Digital Signature)이란?

전자서명은 메시지의 무결성(Integrity)과 인증 및 부인방지를 보장하는 암호 메커니즘입니다.

• 무결성: 메시지가 불법적으로 생성/변경되지 않았음을 보장합니다.
• 인증 및 부인방지: 메시지가 특정 서명자에 의해 생성되었음을 보장합니다.

1.1. 전자서명 알고리즘의 3단계

전자서명은 다음 세 가지 기본 프로세스로 구성됩니다:

1. KeyGen: 비밀키(sk)와 검증키(vk, 공개키)를 생성합니다: (sk, vk) <- KeyGen (1^lambda).
2. Sign: 서명자(Alice)는 비밀키(sk)를 이용해 메시지(mu)에 대한 서명(sigma)을 생성합니다: sigma <- Sign(sk, mu).
3. Verify: 검증자(Bob)는 공개된 검증키(vk)를 이용해 서명(sigma)이 메시지(mu)에 대해 유효한지 확인합니다: Verify(vk, mu, sigma) = 0(reject) 또는 1(accept).

1.2. 전자서명의 안전성

전자서명의 안전성은 위조불가능성(Unforgeability)에 중점을 둡니다.

• 공격자의 능력: 공격자는 공개키/검증키만 이용하는 Key Only Attack부터, 공격자가 선택한 메시지에 대한 서명도 이용하는 Chosen-Message Attack까지 다양하게 능력을 발휘할 수 있습니다.
• 공격자의 목표: 비밀키 획득(Total break) 또는 어떤 메시지에 대해 유효한 전자서명을 위조하는 것(Existential forgery)입니다.

2. 격자 기반 전자서명 패러다임

양자 내성 암호(PQC)를 위한 격자 기반 전자서명은 크게 두 가지 설계 패러다임을 따릅니다:

2.1. Fiat-Shamir with Abort (이산로그 서명의 격자 버전)

• 주요 알고리즘: Dilithium (ML-DSA), HAETAE, BLISS, qTESLA.
• 안전성 난제: MLWE (Module LWE) 및 MSIS (Module SIS).
• 서명 원리: 이산로그 기반 서명(예: ECDSA)과 유사하게, 짧은 비밀키 S와 공개키 T(=AS mod q)를 기반으로, 짧은 랜덤 벡터 y를 생성하고 서명 sigma = (z=y+Sc, c)를 만듭니다.
• 핵심 기술: Rejection Sampling (거부 샘플링)을 사용하여 서명 z의 비밀키 S에 대한 의존성을 제거하고, 정보 유출을 막습니다.

2.2. Hash-and-Sign (RSA 서명의 격자 버전)

• 주요 알고리즘: FALCON, NTRUSign.
• 서명 원리: RSA 서명과 유사하며, 짧은 벡터 s를 서명 sigma로 찾습니다.

3. ML-DSA와 HAETAE 상세 비교

ML-DSA (Dilithium)와 HAETAE는 모두 양자 내성 전자서명 알고리즘이며, 탄탄한 안전성 증명이 가능한 Fiat-Shamir with Abort 패러다임을 따릅니다

3.1. HAETAE의 주요 특징

HAETAE는 ML-DSA와 동일한 패러다임을 따르면서도, 서명 및 키 사이즈 측면에서 효율성을 극대화했습니다.

• Bimodal Hyperball Distribution: 서명 z의 중심을 (+or- Sc) 두 개의 모드(Bimodal)로 설정하고, Hyperball 분포를 사용하여 Rejection Sampling을 수행합니다.
• 효율적인 q 사용: 더 작은 q 값을 사용하면서도 mod 2q 연산을 통해 안정성을 유지하고, 결과적으로 ML-DSA보다 더 작은 서명 사이즈를 달성했습니다 (128-bit 보안 기준, Falcon 대비 158%로 Dilithium의 240%보다 작음).