UC-Secure Star DKG for Non-Exportable Key Shares with VSS-Free Enforcement

이 논문은 하드웨어 기반의 비내보내기 키 (NXK) 환경에서 VSS 없이도 UC-보안을 보장하는 'Star DKG' 프로토콜을 제안하며, 이를 위해 KeyBox 기밀성, 고유 구조 검증 (USV), 그리고 gRO-CRP 모델 기반의 Fischlin NIZK 증명을 결합하여 다중 기기 임계 지갑의 1+1-out-of-n 접근 구조를 구현합니다.

핵심

이 논문은 **"비밀 키를 절대 밖으로 내보내지 않으면서, 여러 사람이 함께 암호화 키를 만드는 방법"**에 대한 혁신적인 해결책을 제시합니다.

기존의 방식은 마치 "비밀 번호 조각을 나누어 주고, 각자가 그 조각을 공개해서 합치면 되나요?"라고 확인하는 과정이 필요했습니다. 하지만 이 논문이 다루는 상황은 **"비밀 번호 조각이 금고 (하드웨어) 안에 영원히 갇혀 있어, 절대 밖으로 나올 수 없다"**는 전제입니다.

이 복잡한 기술 내용을 일상적인 비유로 쉽게 설명해 드리겠습니다.

---

🏛️ 1. 배경: 왜 이런 일이 필요한가요?

상황:
우리가 암호화폐 지갑을 만들 때, 해킹을 막기 위해 하나의 비밀번호를 한 사람이 갖지 않고, **중앙 관리자 (서비스)**와 내 스마트폰 (주요 기기), 그리고 백업용 기기가 나누어 갖습니다.

• 규칙: 암호를 풀려면 반드시 '중앙 관리자'가 참여해야 합니다. 하지만 '중앙 관리자' 혼자서는 절대 암호를 풀 수 없습니다. (예: 은행 금고는 금고 관리자 키와 고객 키가 동시에 있어야 열립니다.)

문제점 (기존 방식의 한계):
기존 기술에서는 각자가 가진 비밀 조각을 서로 주고받거나, "내 조각이 진짜 맞아요"라고 증명하기 위해 조각을 밖으로 꺼내야 했습니다.
하지만 요즘은 보안 칩 (TEE/HSM) 같은 '금고' 안에 비밀 조각을 넣어두는 게 대세입니다. 이 금고는 **"비밀 조각을 절대 밖으로 내보내지 않는다"**는 철학을 가집니다.

• 결과: "내 조각이 맞나요?"라고 물어보려고 해도, 금고가 "아니요, 절대 못 꺼내요"라고 대답합니다. 그래서 기존 방식은 작동하지 않습니다.

---

🔑 2. 해결책: "비밀은 금고 안에, 증명서는 밖으로"

이 논문은 **"비밀 조각은 금고 안에 그대로 두되, 그 존재를 증명할 수 있는 '공인된 증명서'"**를 만들어내는 새로운 방법을 고안했습니다.

🌟 핵심 아이디어 1: USV (Unique Structure Verification) - "마법의 증명서"

• 비유: 금고 안에 있는 '비밀 번호'는 절대 밖으로 못 나오지만, 금고 주인은 **"내 금고 안에 있는 숫자가 '5'라는 걸 증명하는 공인된 문서"**를 밖으로 내줄 수 있습니다.
• 어떻게?: 이 증명서 (USV) 를 보면, 금고 안에 있는 숫자가 정확히 무엇인지 알 수 없지만, 그 숫자가 만들어낸 **'공개된 결과물 (예: 특정 숫자의 제곱)'**은 누구나 계산할 수 있습니다.
• 효과: 사람들은 "아, 금고 안에 있는 비밀이 이 결과물을 만들었구나"라고 믿을 수 있게 됩니다. 하지만 그 비밀 숫자 자체는 여전히 금고 안에 갇혀 있습니다.

🌟 핵심 아이디어 2: 직선 추출 (Straight-Line Extraction) - "시간을 되감지 않는 탐정"

• 기존 방식의 문제: 보통 해커나 검증자가 "너가 진짜 그 숫자를 알고 있니?"를 확인하려면, "한 번 다시 해봐"라고 해서 같은 질문을 두 번 던지는 방식 (되감기) 을 썼습니다.
• 새로운 방식: 하지만 금고는 **"한 번만 작동하고 끝나는 일회용"**입니다. 되감기가 불가능합니다.
• 해결: 이 논문은 "한 번의 대화만으로도, 상대방이 진짜 비밀을 알고 있는지 증명할 수 있는" 새로운 수학적 기법 (Fischlin 변환) 을 사용했습니다. 마치 한 번의 대화로 모든 것을 꿰뚫어 보는 '직관적인 탐정' 같은 방식입니다.

---

🚀 3. 실제 작동 원리: "별 모양 (Star) 지갑"

이 기술은 '별 모양 (Star)' 구조의 지갑에 최적화되어 있습니다.

• 중앙 (별의 중심): 서비스 제공자 (반드시 참여해야 함).
• 잎 (별의 끝): 사용자의 기기들 (주요 기기, 복구 기기 등).

작동 과정:

1. 준비: 각 기기 (금고) 는 자신의 비밀 조각을 금고 안에 숨깁니다.
2. 증명: 각 기기는 금고 밖으로 "비밀 조각이 존재하며, 이 공개된 숫자를 만들었다"는 USV 증명서를 보냅니다.
3. 확인: 중앙 서버는 이 증명서들을 모아, "우리가 합치면 하나의 완벽한 공개 키가 만들어지네!"라고 확인합니다.
4. 완료: 모든 기기는 공개 키를 공유하지만, 비밀 조각은 여전히 각자의 금고 안에 안전하게 남아 있습니다.

특징:

• 새 기기 추가: 나중에 새로운 복구 기기를 추가할 때, 기존 기기들이 비밀 조각을 새로 나누어 주지 않아도 됩니다. 대신 "기존의 비밀 조각을 복사해서 새 금고에 넣어줘"라고 요청하면 됩니다. (이때도 비밀 조각은 금고 간에만 암호화된 상태로 이동합니다.)

---

💡 4. 왜 이것이 중요한가요? (일상적인 의미)

1. 보안의 극대화: 해커가 서버를 해킹하거나 사용자의 스마트폰을 훔쳐도, 비밀 키 조각은 금고 (보안 칩) 안에 있기 때문에 절대 탈취할 수 없습니다.
2. 편의성: 사용자는 복잡한 키 관리 없이, 서비스 제공자와 함께 안전하게 자산을 보호할 수 있습니다.
3. 유연성: 기기를 잃어버리거나 새 기기를 사도, 비밀 키를 다시 생성하거나 복잡하게 이동할 필요 없이, 기존 키를 새 금고에 '복사'만 하면 됩니다.

📝 요약

이 논문은 **"비밀은 절대 밖으로 못 꺼내는 금고"**라는 엄격한 규칙 속에서도, 여러 사람이 협력하여 안전한 암호 키를 만들 수 있게 해주는 **새로운 수학적 도구 (USV 증명서)**를 개발했습니다.

기존의 "조각을 주고받으며 확인하는 방식" 대신, **"비밀은 금고 안에 두고, 그 존재만 증명하는 방식"**으로 전환함으로써, 암호화폐 지갑과 같은 민감한 시스템을 훨씬 더 안전하고 유연하게 만들었습니다. 마치 "비밀 번호는 금고 안에 두고, 금고 문이 제대로 잠겼다는 '공인된 도장'만 밖으로 보여주는" 것과 같습니다.

기술 요약

이 논문은 비출력 가능한 키 (Non-Exportable Key, NXK) 환경, 특히 하드웨어 기반 키 격리 모듈 (TEE, HSM 등) 내에서 작동하는 분산 키 생성 (DKG) 프로토콜을 위한 새로운 보안 프레임워크를 제시합니다. 저자 Vipin Singh Sehrawat 는 기존의 검증 가능한 비밀 공유 (VSS) 기반 DKG 가 NXK 환경의 제약 (키의 외부 유출 불가, 상태 연속성으로 인한 재시도/포크링 불가능) 과 충돌하는 문제를 해결하기 위해 VSS-프리 (VSS-Free) 강제 메커니즘을 도입한 UC-보안 Star DKG (SDKG) 를 제안합니다.

다음은 논문의 상세한 기술 요약입니다.

---

1. 문제 정의 (Problem Statement)

• NXK (Non-Exportable Key) 환경의 제약:
  • 최근 MPC(다자간 계산) 지갑 및 규제 준수 요구사항으로 인해, 비밀 키 조각 (Share) 이 하드웨어 (Secure Enclave, TEE, HSM) 내부에 영구적으로 저장되고 외부로 내보내질 수 없는 환경이 필수적이 되었습니다.
  • 기존 DKG 프로토콜은 참여자들이 키 조각을 교환하거나, VSS(Verifiable Secret Sharing) 를 통해 다항식 관계를 검증하기 위해 키 조각이나 그 파생값을 외부로 전송해야 합니다. 이는 NXK 환경의 '비출력 (Non-exportable)' 원칙과 상충됩니다.
• 상태 연속성 (State Continuity) 과 추출의 어려움:
  • UC(Universally Composable) 보안 증명을 위해 일반적으로 사용되는 '재시도 (Rewinding)' 또는 '포크링 (Forking)' lemma 기반의 증인 (Witness) 추출 기법은, 하드웨어가 상태 연속성을 유지하여 (롤백이나 복제가 불가능) 동일한 약속 (Commitment) 에 대해 서로 다른 응답을 생성할 수 없기 때문에 적용할 수 없습니다.
  • 따라서, 키 조각을 외부로 내보내지 않으면서도 프로토콜의 일관성 (Affine Consistency) 과 유일성 (Uniqueness) 을 검증할 수 있는 새로운 메커니즘이 필요합니다.
• 스타 (Star) 액세스 구조의 필요성:
  • 많은 기업용 지갑이나 규제된_custodian_ 환경에서는 특정 서비스 (센터, $P_1$) 가 반드시 서명에 참여해야 하지만, 단독으로 서명할 수는 없는 '1+1-out-of-n' 스타 구조가 필요합니다. 기존 임계값 DKG 는 이러한 역할을 명확히 구분하기 어렵습니다.

2. 방법론 (Methodology)

논문은 다음과 같은 세 가지 핵심 구성 요소를 결합하여 문제를 해결합니다.

A. 고유 구조 검증 (Unique Structure Verification, USV)

• 개념: NXK/KeyBox 경계에서 작동하는 비대화형 공개 검증 가능 인증서 (Certificate) 메커니즘입니다.
• 기능:
  • KeyBox 내부에 숨겨진 스칼라 (비밀 키 조각) 를 외부로 내보내지 않고, 해당 스칼라에 대응하는 공개 군 원소 (Public Group Element) 를 결정론적으로 유도할 수 있는 인증서 $(C, \zeta)$ 를 생성합니다.
  • 검증자는 인증서로부터 공개 원소 $M = mG$ 를 계산할 수 있지만, 스칼라 $m$ 자체는 노출되지 않습니다.
  • 이는 VSS 의 '공개 검증' 기능을 수행하면서도 키 조각의 외부 유출을 방지합니다.

B. 직선 추출 (Straight-Line Extraction) 을 위한 UC-NIZK

• Fischlin 변환 활용: 상태 연속성으로 인해 재시도가 불가능하므로, Fischlin 변환을 기반으로 한 UC-안전한 비대화형 영지식 증명 (NIZK-AoK) 을 사용합니다.
• gRO-CRP 모델: 전역 랜덤 오라클 (Global Random Oracle) 에 컨텍스트 제한 프로그래밍 (Context-Restricted Programmability) 을 도입한 gRO-CRP 모델을 사용합니다. 이는 시뮬레이터가 증명 컨텍스트에서만 오라클 값을 프로그래밍할 수 있게 하여, 직선 추출 (Straight-line extraction) 을 가능하게 합니다.
• 직선 추출: 증명자의 오라클 쿼리 로그를 관찰하여 증인 (Witness) 을 추출할 수 있어, 재시도 없이도 UC 보안을 증명할 수 있습니다.

C. Star DKG (SDKG) 프로토콜

• 구조: $P_1$(센터/서비스) 와 $P_2$(주요 디바이스), $P_3$(복구 디바이스) 로 구성된 1+1-out-of-3 구조를 기본으로 합니다.
• 작동 원리:
  1. 라운드 1: $P_2$ 는 USV 인증서를 생성하여 $P_1$ 에게 전송합니다.
  2. 라운드 2: $P_1$ 은 인증서를 검증하고 자신의 기여분을 USV 및 UC-NIZK(Affine 관계 증명) 를 통해 전송합니다.
  3. 라운드 3: $P_2$ 는 $P_1$ 의 증명을 검증하고 최종 공개 키를 계산하여 브로드캐스트합니다.
  4. 설치: 모든 검증이 완료되면, 각 참여자는 계산된 키 조각을 KeyBox 내부에 설치합니다.
• 역할 기반 등록 (RDR): 프로토콜 완료 후, 추가 복구 디바이스를 기존 '복구 역할'에 등록할 수 있습니다. 이는 키 조각을 재분배 (Resharing) 하지 않고, 기존 디바이스 간의 KeyBox-to-KeyBox sealing 을 통해 새로운 디바이스에 동일한 역할을 복제하는 방식으로 수행됩니다.

3. 주요 기여 (Key Contributions)

1. USV (Unique Structure Verification) 도입:
   • NXK 환경에서 키 조각을 외부로 내보내지 않으면서도, 프로토콜 트랜스크립트에 정의된 공개 구조를 검증할 수 있는 새로운 원시 (Primitive) 를 정의하고 UC 보안을 증명했습니다.
   • 이는 하드웨어 내부의 비밀을 유지하면서 트랜스크립트 기반의 일관성 검증을 가능하게 하는 핵심 기술입니다.
2. VSS-프리 UC-보안 DKG 설계:
   • 기존의 VSS 기반 강제 메커니즘 (Complaint/Opening/Resharing) 을 완전히 제거하고, USV 와 Fischlin 기반 NIZK 를 사용하여 NXK 환경에 적합한 DKG 를 구축했습니다.
   • 상태 연속성 (State Continuity) 제약 하에서도 UC 보안을 보장하는 직선 추출 기법을 적용했습니다.
3. 1+1-out-of-n Star DKG (SDKG) 구현:
   • 필수 서비스와 임의의 디바이스가 함께 서명해야 하는 스타 구조를 지원하며, post-DKG(키 생성 후) 에 추가 디바이스를 등록하는 RDR(Role-based Device Registration) 메커니즘을 제공합니다.
   • 이는 기존 임계값 DKG 와 달리, 특정 역할 (Primary vs Recovery) 을 하드웨어 수준에서 분리하여 관리할 수 있게 합니다.
4. 형식적 보안 증명: DL(이산 로그) 및 DDLEQ(Decisional Diffie-Hellman) 가정 하에, 적응적 손상 (Adaptive Corruption) 과 안전한 삭제 (Secure Erasures) 를 가정하여 UC 보안을 증명했습니다.

4. 결과 및 성능 (Results & Performance)

• 보안성:
  • UC(보편적 구성 가능성) 프레임워크 하에서 표준 UC-DKG 기능의 정제된 버전을 구현함을 증명했습니다.
  • 비인가된 손상 집합에 대한 비밀성,authorized 집합에 의한 키의 유일성 및 일관성을 보장합니다.
• 복잡도:
  • 통신 오버헤드: $O(n \log p)$ 비트 (기초 1+1-out-of-3 실행 시 상수 개수의 증명 객체만 사용).
  • 계산 오버헤드: $O(n \log^{2.585} p)$ 비트 연산 (Karatsuba 모델 기준).
  • 등록 비용: 추가 복구 디바이스 등록 시 통신 $O(\log p)$, 계산 $O(\log^{2.585} p)$ 로 매우 효율적입니다.
• 구체적 크기:
  • 128-bit 보안 수준 (Fischlin 파라미터 고정) 에서 1+1-out-of-3 SDKG 의 기본 트랜스크립트 크기는 약 11~13 KiB입니다.
  • 이는 기존 VSS 기반 프로토콜에 비해 트랜스크립트 크기가 크게 감소하거나, 최소한의 오버헤드로 NXK 제약을 해결함을 보여줍니다.

5. 의의 및 중요성 (Significance)

• 실용적 적용 가능성: 이 연구는 TEE(Trusted Execution Environment) 나 HSM 을 사용하는 실제 MPC 지갑 및 규제 준수 시스템에 바로 적용 가능한 DKG 솔루션을 제공합니다. 특히 '비출력 키'가 필수적인 금융 및 기업 환경에서 핵심적인 역할을 합니다.
• 보안 모델의 진화: 기존 DKG 가 가정했던 '키 조각의 교환'이라는 가정을 버리고, 하드웨어의 비출력 특성을 보안의 핵심 요소로 삼은 새로운 패러다임을 제시했습니다.
• 유연한 확장성: RDR 메커니즘을 통해 디바이스 동적 추가가 가능하며, 키 조각을 재분배하지 않고도 새로운 장치를 안전하게 통합할 수 있어 운영 효율성이 높습니다.
• 이론적 기여: 상태 연속성 제약 하에서의 UC 보안 증명 기법 (직선 추출) 과 USV 같은 새로운 암호학적 원시를 제시하여, 향후 하드웨어 기반 암호학 연구의 기초를 마련했습니다.

결론적으로, 이 논문은 하드웨어 기반 키 격리 환경에서 기존의 DKG 한계를 극복하고, UC 보안을 유지하면서도 효율적이고 확장 가능한 스타 구조 DKG 를 실현한 획기적인 연구입니다.