FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG

이 논문은 기존 ML-DSA 구현체와 호환되는 표준 서명을 생성하면서도 조건부 최소 엔트로피 보장을 통해 서명자 비노출을 달성하는 최초의 임계값 ML-DSA(FIPS 204) 체계를 제안하며, Shamir 비선형 DKG 와 쌍별 PRF 마스크 기술을 통해 이를 실현합니다.

핵심

🏛️ 비유: "보안 금고와 5 명의 경비원"

상상해 보세요. 거대한 **보안 금고 (디지털 자산)**가 있습니다. 이 금고의 비밀번호는 매우 강력하지만, 한 사람이 비밀번호를 모두 알고 있으면 그 사람이 도둑이 되거나 실수로 비밀번호를 잃어버릴 때 모든 것이 위험해집니다.

그래서 우리는 **5 명의 경비원 (N=5)**을 고용하고, 비밀번호를 **3 명 이상 (T=3)**이 모여야만 열 수 있도록 설정합니다. 이를 **'임계값 서명 (Threshold Signature)'**이라고 합니다.

하지만 문제는 **새로운 종류의 금고 (양자 내성 암호, ML-DSA)**가 등장하면서 기존 방식으로는 3 명 이상이 모였을 때 금고 문을 여는 과정이 너무 복잡해지거나, 문이 열리지 않는 경우가 생긴다는 것입니다.

이 논문은 **이 문제를 해결하는 새로운 열쇠 (프로토콜)**를 개발했습니다.

---

🔑 핵심 기술 1: "함께 만든 비밀 열쇠 (Shamir Nonce DKG)"

기존 방식에서는 3 명의 경비원이 각자 가진 열쇠 조각을 합칠 때, 수학적으로 계산하는 과정에서 오차가 발생하거나 누군가 열쇠를 훔쳐볼 수 있는 위험이 있었습니다.

이 논문은 "비밀 열쇠 (Nonce)"를 만들 때부터 5 명이 함께 참여하는 방식을 도입했습니다.

• 비유: 5 명의 경비원이 각자 종이에 숫자를 적어 상자에 넣습니다. 그리고 상자를 섞어서 3 명이 뽑아 숫자를 더하면, 그 결과가 완벽한 비밀 열쇠가 됩니다.
• 장점: 만약 2 명의 경비원만 도둑질하더라도, 나머지 3 명의 숫자 조합을 알 수 없기 때문에 비밀 열쇠는 절대 노출되지 않습니다. 마치 **한 번만 쓰면 사라지는 일회용 패드 (One-time Pad)**처럼 안전합니다.
• 결과: 기존 방식보다 훨씬 안전하면서도, 금고 문을 여는 속도가 빠릅니다.

🛡️ 핵심 기술 2: "서로 상쇄되는 가짜 흔적 (Pairwise-Canceling Masks)"

경비원들이 금고 문을 열 때, 서로의 동작을 숨기기 위해 **가짜 흔적 (마스크)**을 남깁니다. 하지만 이 가짜 흔적들이 합쳐지면 서로 사라져야 (상쇄) 진짜 열쇠만 남습니다.

• 비유: 3 명의 경비원이 금고 앞에 서 있습니다. 각자 "왼쪽을 봐"라는 신호를 보내지만, 실제로는 "오른쪽"을 보고 있습니다. 그런데 3 명이 합치면, "왼쪽"과 "오른쪽" 신호가 서로 상쇄되어 사라지고, 결국 "열쇠를 돌린다"는 진짜 명령만 남습니다.
• 효과: 도둑이 경비원들의 대화를 엿듣더라도, 진짜 열쇠가 어디에 있는지 알 수 없습니다.

⏱️ 핵심 기술 3: "세 가지 운영 모드 (Deployment Profiles)"

이 기술은 상황에 따라 세 가지 방식으로 작동할 수 있습니다.

1. P1 (신뢰할 수 있는 관리자 모드):
   • 비유: 신뢰할 수 있는 **보안관 (TEE/HSM)**이 있습니다. 경비원들은 보안관에게만 비밀 조각을 주고, 보안관이 합쳐서 문을 엽니다.
   • 특징: 가장 빠르고 효율적입니다. (약 5.8 초)
2. P2 (완전 분산 모드):
   • 비유: 아무도 신뢰하지 않습니다. 모든 경비원이 서로 대화하며 수학적 연산을 통해 문을 엽니다.
   • 특징: 가장 안전하지만, 조금 더 시간이 걸립니다. (약 21.5 초)
3. P3+ (반비동기 모드):
   • 비유: 경비원들이 미리 준비해 둔 열쇠 조각을 가지고 있습니다. 금고 문이 열릴 때만 짧은 시간 내에 반응하면 됩니다.
   • 특징: 사람이 직접 확인해야 하는 상황 (예: 은행 이체 승인) 에 가장 적합합니다. (약 22 초)

---

🌟 이 기술이 왜 중요한가요?

1. 표준 호환성 (FIPS 204): 이 기술로 만든 서명은 기존에 사용하던 모든 시스템에서 아무런 수정 없이 바로 인식됩니다. 마치 새로운 열쇠를 썼는데도 기존 금고 구멍에 완벽하게 들어가는 것과 같습니다.
2. 안전한 규모 확장: 과거에는 경비원이 32 명 이상일 때 서명이 불가능하거나 매우 느렸습니다. 하지만 이 기술은 32 명, 45 명까지도 빠르고 안전하게 처리할 수 있습니다.
3. 양자 컴퓨터 대비: 미래의 양자 컴퓨터가 현재의 암호를 뚫더라도, 이 새로운 방식은 안전합니다.

📝 요약

이 논문은 "여러 사람이 함께 디지털 서명을 할 때, 속임수 없이, 빠르고, 표준에 맞게, 그리고 양자 컴퓨터 시대에도 안전하게" 할 수 있는 방법을 찾아냈습니다.

• 기존의 문제: 여러 명이 합치면 계산이 복잡해지고, 보안이 약해지거나, 표준과 맞지 않음.
• 이 논문의 해결책: "함께 만든 비밀 열쇠"와 "서로 상쇄되는 가짜 흔적"을 이용해, 어떤 상황에서도 (3 명~45 명까지) 안전하고 빠른 서명을 가능하게 함.

이 기술은 향후 암호화폐 지갑, 기업 보안, 국가 인증 시스템 등에서 핵심적인 역할을 할 것으로 기대됩니다.

기술 요약

1. 문제 제기 (Motivation: The Threshold Gap)

• 양자 컴퓨팅 위협: 현재 공개키 암호체계의 붕괴 위험에 대응하여 NIST 는 ML-DSA (CRYSTALS-Dilithium 기반) 를 FIPS 204 표준으로 채택했습니다.
• 임계값 서명의 필요성: 금융 시스템, 분산 인증 기관 (CA), 암호화폐 지갑 등에서 비밀키를 여러 서버에 분산하여 보호하고, 다수의 합의를 통해 서명하는 기능이 필수적입니다.
• 기존 기술의 한계:
  • ECDSA/Schnorr: 효율적인 임계값 프로토콜이 잘 정립되어 있음.
  • ML-DSA (격자 기반): 'Fiat-Shamir with Aborts' 패러다임으로 인해 서명 생성 시 '거부 샘플링 (Rejection Sampling)'이 필요하여 임계값 환경에서 복잡도가 급증함.
  • 기존 ML-DSA 임계값 솔루션의 결함:
    • Short-coefficient LSSS: 임계값이 작을 때만 (T ≤ 6) 표준 서명 크기를 유지 가능. T 가 커지면 라그랑주 계수가 모듈로 q 를 초과하여 표준 호환성이 깨짐.
    • Noise Flooding: 임의의 임계값을 지원하지만 서명 크기가 17KB 로 커져 FIPS 204 형식과 호환되지 않음.
    • Ringtail 등: 서명 형식이 표준과 달라 기존 검증기를 사용할 수 없음.
• 결론: T ∈ [9, 32] 범위의 실용적인 임계값 설정 (예: 16-of-32) 에서 표준 서명 크기, 높은 성공률, FIPS 204 호환성을 동시에 만족하는 솔루션이 부재했습니다.

2. 주요 방법론 (Methodology)

이 논문은 두 가지 핵심 기술을 결합하여 위 문제를 해결합니다.

A. Shamir Nonce DKG (주요 기술)

• 개념: 서명에 사용되는 비선형 (Nonce, $y$) 을 장기간 비밀키 ($s_1$) 와 동일한 구조 (Shamir 분할) 로 생성합니다.
• 작동 원리:
  • 각 참여자는 차수 $T-1$인 Shamir 다항식을 생성하여 비선형 공유 ($y_i$) 를 만듭니다.
  • 각 참여자는 $z_i = y_i + c \cdot s_{1,i}$를 계산합니다. (라그랑주 계수 $\lambda_i$를 미리 곱하지 않음).
  • 합산기 (Combiner) 가 $z = \sum \lambda_i z_i = y + c \cdot s_1$을 재구성합니다.
• 장점:
  • 통계적 프라이버시: 공격자가 $T-1$개의 평가점만 관찰하더라도, honest party 의 비선형 공유는 조건부 최소 엔트로피 (Conditional Min-Entropy) 가 비밀키 엔트로피의 5 배 이상 유지됩니다. 이는 계산적 가정 없이 통계적으로 보장됩니다.
  • 임계값 최적화: Coordinator 기반 프로파일 (P1, P3+) 에서는 $|S| \ge T$ (정확한 임계값) 만으로 프라이버시가 보장되며, 기존 방식이 요구하던 $|S| \ge T+1$ (두 명의 honest party 필요) 조건을 제거했습니다.

B. Pairwise-Canceling Masks (보조 기술)

• 목적: 격자 기반 임계값 서명에서 발생하는 고유한 3 가지 문제 해결:
  1. Commitment Binding: 비선형 공유에 대한 약속 값 ($W_i$) 은 공개되지 않아야 함.
  2. r0-Check: $cs_2$ 값이 노출되면 비밀키가 유출될 수 있음.
  3. Response Aggregation: 개별 응답을 합산할 때 프라이버시를 유지해야 함.
• 해결책: ECDSA 에서 영감을 얻은 쌍별 상쇄 마스크 (Pairwise-canceling masks) 를 격자 환경에 적용하여, $W_i$와 $r_0$-check 공유 ($V_i$) 를 숨기면서도 합산 시 정확성을 유지합니다.

C. Irwin-Hall 분포 분석 및 보안 증명

• 문제: 임계값 서명에서 집계된 비선형은 Uniform 분포가 아닌 Irwin-Hall 분포를 따릅니다. 이는 기존 보안 증명 (EUF-CMA) 에 영향을 줄 수 있습니다.
• 해결: 기존 'Raccoon' 스타일의 보수적인 분석 (Rényi 발산) 은 $T$가 커질수록 보안 손실이 급격히 커져 무의미해졌습니다.
• 혁신: 직접 이동 불변성 (Direct Shift-Invariance) 분석을 도입하여, Irwin-Hall 분포가 가져오는 보안 손실이 매우 작음을 증명했습니다.
  • $|S| \le 17$일 때 세션당 보안 손실: < 0.007 비트
  • $|S| \le 33$일 때 세션당 보안 손실: < 0.013 비트
  • 이는 기존 연구의 확장성 격차를 완전히 해소합니다.

3. 배포 프로파일 (Deployment Profiles)

논문은 세 가지 다른 신뢰 가정 하에 작동하는 프로파일을 정의하고, 각각에 대해 완전한 UC (Universal Composability) 보안을 증명했습니다.

프로파일	특징	신뢰 가정	라운드 수	성능 (3-of-5 기준)
P1 (TEE-Assisted)	TEE/HSM 코디네이터가 $r_0$-검사를 수행	TEE 무결성 (하드웨어 신뢰)	3 온라인 + 1 오프라인	5.8 ms (가장 빠름)
P2 (Fully Distributed)	완전 분산 MPC (SPDZ + edaBits) 사용	신뢰할 수 있는 코디네이터 없음	5 온라인	21.5 ms
P3+ (Semi-Async 2PC)	2PC 기반, 서명자는 오프라인에서 비선형 미리 계산	2 개의 계산 파티 중 1 개만 정직하면 됨	2 논리 라운드	22.1 ms (반동기 지원)

• P3+ 의 혁신: 인간 개입이 필요한 승인 시나리오 (Human-in-the-loop) 에 적합하며, 서명자가 여러 라운드를 동기화할 필요 없이 시간 창 내에서 응답할 수 있어 네트워크 지연에 강합니다.

4. 실험 결과 및 성능 (Results)

• 구현: Rust 로 구현되었으며, ML-DSA-65 (NIST Security Level 3) 를 대상으로 테스트되었습니다.
• 성능:
  • 지연 시간: P1 과 P3+ 는 32-of-45 임계값에서도 100ms 미만의 지연 시간을 유지합니다.
  • 성공률: 단일 서명자 ML-DSA 의 기대 성공률 (약 20-25%) 과 유사하거나 더 높은 **21-45%**의 성공률을 기록했습니다. (Irwin-Hall 분포가 0 근처에 더 집중되어 거부 샘플링 통과율이 높아짐).
  • 확장성: 2-of-3 에서 32-of-45 까지 확장 가능하며, P3+ 는 128 개의 참여자까지 3 초 이내로 동작합니다.
• 호환성: 생성된 서명은 FIPS 204 표준과 완전히 호환되어 수정되지 않은 검증기로 검증 가능합니다.

5. 기여 및 의의 (Significance)

1. 첫 번째 FIPS 204 호환 임계값 솔루션: 임의의 임계값을 지원하면서도 표준 3.3KB 서명 크기를 유지하는 유일한 솔루션입니다.
2. 통계적 프라이버시 보장: 계산적 가정이 아닌 Shamir 다항식의 구조적 속성을 통해 비선형 공유의 프라이버시를 통계적으로 보장합니다.
3. 확장성 문제 해결: Irwin-Hall 분포로 인한 보안 손실이 미미함을 수학적으로 증명하여, 대규모 임계값 설정에서도 실용적인 보안을 제공합니다.
4. 실용적 배포: TEE 기반, 완전 분산 MPC, 반동기 2PC 등 다양한 신뢰 모델과 환경에 맞춰 최적화된 프로파일을 제공합니다.
5. 미래 지향성: 양자 내성 암호 (PQC) 시대의 분산 키 관리, 암호화폐 지갑, 분산 CA 등 다양한 분야에서 표준 임계값 서명 인프라의 기반이 될 것으로 기대됩니다.

결론

이 논문은 ML-DSA 의 임계값 구현에 있어 존재하던 "표준 호환성 vs 임계값 유연성"이라는 딜레마를 해결했습니다. Shamir Nonce DKG 와 정교한 보안 분석을 통해, FIPS 204 표준을 준수하면서도 임의의 임계값을 지원하고 통계적으로 안전한 실용적인 임계값 서명 체계를 최초로 제시했다는 점에서 암호학 및 보안 분야에서 중요한 이정표가 됩니다.