기술 요약: TALUS – 1라운드 온라인 서명을 지원하는 임계값 ML-DSA

1. 문제 정의

ML-DSA(FIPS 204 기반, CRYSTALS-Dilithium 기반)를 임계값(threshold) 설정에서 배포하는 것은 고유한 비선형 반올림 단계로 인해 미해결 과제로 남아 있었습니다. 가산 동형성(additive homomorphism)에 의존하는 고전적인 임계값 서명(예: Schnorr/ECDSA를 위한 FROST)과 달리, ML-DSA는 서명 힌트가 범위를 벗어나지 않도록 보조 잔차(residual) $r_0 - cs_2$를 확인해야 합니다. 임계값 설정에서 비밀키 성분 $s_2$는 여러 당사자 간에 공유됩니다. $r_0$ 확인을 처리하기 위해 기존 방식들은 다음과 같은 요구사항을 가졌습니다:

1. 고비용 MPC: $cs_2$를 온라인에서 평가하기 위한 다자간 계산(MPC).
2. 신뢰할 수 있는 코디네이터: TEE(신뢰 실행 환경) 또는 단일 신뢰 당사자에 $s_2$를 보유.
3. 노이즈 플러딩(Noise Flooding): 체크를 마스킹하기 위해 파라미터를 저하시킴.

이러한 방법들은 온라인 지연 시간을 증가시키거나(다중 라운드), 신뢰 모델을 제한하거나, 보안 파라미터를 저하시킵니다. 나아가, 근본적인 "격자 임계값 딜레마(Lattice Threshold Trilemma)"가 존재합니다: 논스(nonce) 공간으로부터의 어떠한 군 동형 사상(group homomorphism)도 은닉성(hiding)과 결합성(binding)을 동시에 만족할 수 없으므로, 이산 로그 설정에서 사용되는 표준 동형 약속(homomorphic commitment) 방식은 사용할 수 없습니다.

2. 방법론 및 핵심 혁신

TALUS(Threshold Agile Lattice Unified Signatures)는 $r_0$ 확인 과정을 온라인 서명 단계에서 분리하고, 새로운 대수적 프레임워크를 통해 분산 약속 문제를 해결함으로써 이러한 장벽을 극복합니다.

2.1 경계 클리어런스 조건 (Boundary Clearance Condition, BCC)

본 논문은 ML-DSA 약속 공간의 기하학적 특성을 식별했습니다. 서명 과정은 잔차 $r_0 = \text{LowBits}(Ay)$를 포함합니다. 비밀값에 의존하는 시프트(shift) $cs_2$는 $r_0$가 모듈러 경계($\pm \gamma_2$)에 근접할 때만 경계 교차를 일으킬 수 있습니다.

• 관찰: 모든 $r_0$의 계수가 경계로부터 $\beta = \tau\eta$보다 더 멀리 떨어져 있다면(여기서 $\tau$는 챌린지 가중치, $\eta$는 비밀값 상한), 시프트 $cs_2$는 경계를 넘을 수 없습니다.
• 함의: 이 경계 클리어런스 조건(BCC) 하에서, 약속의 고차 부분($w_1$)은 $s_2$에 의해 변하지 않으며, 힌트 $h$는 전적으로 공개된 값들($r = Az - ct_1 \cdot 2^d$ 및 $w_1$)로부터 계산 가능해집니다.
• 확률: BCC는 논스 시도당 확률 $p_{BCC} \approx 31.7\%$로 성립합니다.
• 전략: TALUS는 BCC를 만족하는 논스를 생성하기 위해 **오프라인 전처리(offline preprocessing)**를 수행합니다. 이는 온라인 단계 이전에 "나쁜" 논스를 필터링하여, 서명 중에 $cs_2$를 계산하거나 $r_0$를 확인할 필요를 제거합니다.

2.2 캐리 제거 프레임워크 (Carry Elimination Framework, CEF)

BCC가 있더라도, 당사자들은 분산된 방식으로 약속 해시 입력인 $w_1 = \text{HighBits}(Ay)$를 계산해야 합니다. $\text{HighBits}$는 군 동형 사상이 아니기 때문에, 개별적인 가산 논스 조각들을 합산하면 "캐리(carry)"가 발생하며, 이는 전체 논스를 재구성하지 않고도 해결되어야 합니다.

• 핵심 항등식: 본 논문은 모듈러 항등식 $\alpha^{-1} \equiv -16 \pmod q$ (여기서 $\alpha = 2\gamma_2$)를 활용합니다.
• 프로토콜:
  • TALUS-TEE: 신뢰할 수 있는 코디네이터(TEE 내)가 총합 논스를 보유하고 $w_1$을 직접 계산합니다. 서명자들은 $s_1$의 조각들을 보유합니다.
  • TALUS-MPC: 당사자들은 **캐리 안전 비교 프로토콜(CSCP)**을 사용하여 마스킹된 가산 논스 조각들의 분해(decomposition)를 브로드캐스트합니다. 비버 트리플(Beaver triples)과 접두사 트리 비교 회로를 사용하여, 당사자들은 단일 캐리 비트 $c$와 FIPS 보정 비트 $\delta$를 계산합니다. 이를 통해 코디네이터는 논스의 개별 로우 비트(low-bits)를 학습하지 않고도 정확한 $w_1$을 재구성할 수 있습니다.
• 효율성: $T=2$인 경우, 이는 분산 비교 함수(DCF)로 퇴화하여 통신량을 크게 줄입니다. $T \ge 3$인 경우, $O(\log N)$의 오프라인 라운드가 필요하지만 온라인 단계에는 영향을 주지 않습니다.

3. 프로토콜 인스턴스화

본 논문은 두 가지 배포 프로필을 제시합니다.

TALUS-TEE (신뢰 실행 환경)

• 모델: 코디네이터가 TEE 내부에서 $s_2$와 $t_0$를 보유합니다. 서명자들은 $s_1$의 조각들을 보유합니다.
• 과정: TEE는 BCC를 준수하는 논스를 찾기 위해 오프라인 전처리를 수행합니다. TEE는 $w_1$을 브로드캐스트합니다. 서명자들은 $z_i = y_i + c \cdot s_{1,i}$로 응답합니다. TEE는 서명을 조립합니다.
• 신뢰: 준-정직(semi-honest) TEE 코디네이터가 필요하며, 서명자는 악의적일 수 있습니다(식별 가능한 중단(Identifiable Abort) 지원).
• 제약: 정직한 과반수 요구사항이 없습니다 ($N \ge T$).

TALUS-MPC (완전 분산형)

• 모델: 완전 분산형이며, 어떤 당사자도 $s_2$나 총합 논스를 보유하지 않습니다.
• 과정: 당사자들은 오프라인 전처리 단계에서 CEF를 통해 $w_1$을 공동으로 계산합니다. 온라인 서명은 TEE와 동일하게 1라운드로 진행됩니다.
• 신뢰: 식별 가능한 중단(IA)을 포함한 악의적 보안을 제공하며, $T \ge 2$인 경우 적용됩니다.
• 제약: $T \ge 3$인 경우, 러싱 공격자(rushing adversary)가 논스의 로우 비트를 학습하는 것을 방지하기 위해 정직한 과반수($N \ge 2T - 1$)가 필요합니다 ("불성실한 과반수 장벽"). $T=2$인 경우, 정직한 과반수가 필요하지 않습니다.

4. 주요 기여

1. 격자 임계값 딜레마(Lattice Threshold Trilemma): 격자 논스 공간으로부터의 어떠한 군 동형 사상도 은닉성과 결합성을 동시에 가질 수 없다는 증명을 제시했습니다. 이는 캐리 해결이 단순한 프로토콜의 부산물이 아니라 수학적 필연성임을 입증합니다.
2. 경계 클리어란스 조건 (BCC): $r_0$ 체크를 약 $31.7\%$의 논스에 대해 우회할 수 있음을 공식적으로 증명하여, 온라인 단계에서 $s_2$ 계산을 제거할 수 있게 했습니다.
3. 캐리 제거 프레임워크 (CEF): 논스 $y$를 재구성하지 않고도 $\text{HighBits}(Ay)$를 계산하는 분산 프로토콜을 제안하며, ML-DSA의 특정 모듈러 산술 특성을 활용합니다.
4. 1라운드 온라인 서명: 두 변형 모두 온라인 서명을 위한 단일 브로드캐스트 라운드를 달성하여, 2~3라운드가 필요한 기존의 FIPS 호환 제안들(예: Mithril, Quorus)보다 뛰어난 성능을 보입니다.
5. 구현: 모든 세 가지 FIPS 204 보안 레벨(ML-DSA-44, 65, 87)에 대한 Rust 참조 구현을 제공합니다.

5. 결과 및 성능

• 성공률: 성공적인 서명당 기대되는 전처리 시도 횟수는 약 $3.15$입니다 ($31.7%$의 BCC 통과율 때문).
• 지연 시간 (ML-DSA-65, $T=3$):
  • TALUS-TEE: 온라인 서명에 0.29 ms가 소요되며, 오프라인 준비를 포함한 상쇄(amortized) 총 시간은 1.52 ms입니다.
  • TALUS-MPC: 온라인 서명에 0.68 ms가 소요되며, 상쇄 총 시간은 4.09 ms입니다.
  • 비교: TALUS-TEE는 온라인 지연 시간 측면에서 Mithril(3.6 ms)보다 2.4배 빠릅니다. TALUS-MPC는 Mithril과 경쟁 가능한 수준이지만, Mithril의 3라운드 대신 1라운드만으로 이를 달성합니다.
• 통신량:
  • T=2: 오프라인 비용은 배치당 약 5 KB (DCF)입니다.
  • T $\ge$ 3: 오프라인 비용은 배치당 약 350 KB (CarryCompare에 의해 결정됨)입니다.
  • 온라인: $T$와 $N$에 독립적이며, 서명자당 약 3.6 KB로 일정합니다.
• 네트워크 지연: GCP에서의 분산 실험 결과, 엔드 투 엔드 지연 시간은 네트워크 RTT에 선형적으로 비례하며(예: US-Europe 간 약 350 ms), 이는 1라운드의 이점을 확인시켜 줍니다.

6. 의의 및 주장

본 논문은 TALUS가 다음을 동시에 달 achieve하는 최초의 임계값 ML-DSA 구조라고 주장합니다:

1. 전체 FIPS 204 호환성: 수정되지 않은 표준 검증기에 의해 서명이 검증될 수 있습니다.
2. 임의의 임계값: 특정 정직한 과반수 제약 조건 하에 $1 \le T \le N$인 모든 $T$-of-$N$을 지원합니다.
3. 1라운드 온라인 서명: 단일 당사자 서명과 일치하는 지연 시간을 달성하여, 다중 라운드를 요구하는 이전 연구들보다 유의미한 개선을 이루었습니다.

저자들은 "캐리 비용(carry cost)"이 격자 설정의 고유한 대수적 대가이지만, TALUS는 이를 완전히 오프라인 단계로 이동시켜 이 비용을 최소화한다고 강조합니다. 본 연구는 FIPS 204 호환성이 임계값 설정에서 반드시 성능 저하를 수반할 필요는 없음을 보여줍니다.

참고 (암호 분석): 본 논문은 G. Niot의 암호 분석(2026-07-09 자)을 인정하는 노트를 포함하고 있습니다. 해당 공격은 TALUS-MPC의 약속 체계가 은닉적이지 않음($Ax$로부터$x$를 복구 가능)을 확인하였으며,$s_2$체크의 제거가 통계적 누출을 유발함을 확인했습니다. 저자들은 이러한 점들을 인정하고,$As_{1,i}$의 은닉성 및 비밀 유지를 위한$s_2$ 체크의 중복성에 대한 특정 주장을 철회하며, 진정으로 은닉성을 갖춘 약속을 사용하는 수정된 구조를 준비 중이라고 밝혔습니다. 또한 TALUS-TEE는 이러한 약속 공격의 영향을 받지 않는다고 명시했습니다.