임계값 ECDSA: 다자간 서명

ECDSA 서명에는 무작위 논스 k, 곡선 점 R = k*G, 서명 s = k^{-1}(h + r*x) mod n을 계산하는 과정이 필요하며, 여기서 x는 개인 키이고 r은 R의 x 좌표입니다. k의 역원을 계산하고 개인 키를 곱해야 하므로 ECDSA는 본질적으로 비선형입니다. 반면 Schnorr 서명에서는 응답이 단순한 선형 결합입니다. 이러한 비선형성 때문에 여러 참여자에게 계산을 분산하는 일이 매우 어려워집니다.

Gennaro와 Goldfeder가 2018년에 제안한 GG18 프로토콜은 신뢰할 수 있는 딜러 없이 안전하게 동작하는 최초의 실용적인 2자 및 임계 ECDSA 구성 방식이었습니다. 핵심 아이디어는 비선형 ECDSA 계산에 필요한 곱셈-덧셈(MtA) 변환을 수행하기 위해 Paillier 동형 암호화를 사용하는 것입니다. GG18은 정적 준정직 공격자에 대한 시뮬레이션 기반 보안을 제공합니다.

Gennaro와 Goldfeder가 2020년에 제안한 GG20은 신뢰할 수 있는 초기 설정 없이 악의적인 공격자에 대한 보안을 증명함으로써 GG18을 개선했습니다. GG20은 각 참여자가 프로토콜을 올바르게 따르는지 확인하기 위해 영지식 증명을 추가했습니다. 이러한 증명은 악의적인 참여자가 논스나 서명을 편향시켜 다른 참여자의 키 공유값에 관한 정보를 추출하지 못하게 합니다. GG20은 많은 운영용 MPC 지갑 구현의 기반이 되었습니다.

CGGMP21(Canetti, Gennaro, Goldfeder, Makriyannis, Peled, 2021)은 현재 가장 앞선 임계 ECDSA 프로토콜입니다. 이 프로토콜은 식별 가능한 중단을 달성합니다. 즉, 악의적인 행동으로 서명 프로토콜이 실패하면 어떤 참여자에게 책임이 있는지 식별할 수 있습니다. 이는 책임 소재가 중요한 기업 환경에 배포할 때 매우 중요합니다. CGGMP21은 tss-lib와 multi-party-sig를 비롯한 널리 사용되는 MPC 라이브러리에 구현되어 있습니다.

임계 ECDSA의 핵심 과제는 비밀 공유값을 공개하지 않고 그 곱을 계산하는 것입니다. MtA(곱셈-덧셈) 변환은 두 참여자의 공유값 a와 b의 곱을 덧셈 공유값으로 변환합니다. 참여자 1은 alpha를, 참여자 2는 beta를 받아 alpha + beta = a*b가 되도록 하는 방식입니다. 이를 위해 Paillier 암호화를 사용합니다. 참여자 1이 a를 암호화하고, 참여자 2가 동형 연산으로 b를 곱한 뒤 무작위성을 더하면, 참여자 1이 그 결과를 복호화하여 덧셈 공유값을 얻습니다.

Paillier 암호화는 덧셈과 평문에 의한 곱셈을 모두 지원하는 부분 동형 암호 방식입니다. 암호화된 Enc(a)가 주어지면 누구나 복호화하지 않고도 알려진 b에 대해 Enc(a*b)를 계산할 수 있습니다. 이 특성 덕분에 MtA 프로토콜을 사용할 수 있습니다. 참여자 1이 Paillier 키 쌍을 생성하고 논스와 개인 키의 공유값인 Enc(k1)과 Enc(x1)을 보냅니다. 참여자 2는 동형 연산을 사용해 k1이나 x1을 알지 못한 채 자신의 기여분을 계산합니다.

임계 ECDSA 서명에는 일반적으로 여러 차례의 통신 라운드가 필요합니다. GG20에서는 사전 처리 단계에서 논스와 무작위 은닉값에 대한 커밋먼트를 계산하며, 이 단계에 2라운드가 필요합니다. 이후 온라인 서명 단계에서 부분 서명을 결합하며 1라운드가 필요합니다. 메시지를 알기 전에 사전 처리를 완료할 수 있으므로 온라인 지연 시간은 단일 라운드로 줄어듭니다. CGGMP21은 이를 더욱 최적화합니다.

식별 가능한 중단이란 임계 서명 프로토콜이 실패했을 때, 예를 들어 어떤 참여자가 잘못된 형식의 메시지를 보내거나 프로토콜을 따르지 않았을 때 정직한 참여자들이 어느 참여자가 잘못된 행동을 했는지 암호학적으로 판별할 수 있다는 뜻입니다. 이를 위해 각 단계에서 계산이 올바르게 수행되었음을 증명하는 영지식 증명이 필요합니다. 식별 가능한 중단이 없다면 악의적인 참여자가 프로토콜 완료를 거부하여 서비스 거부를 일으키면서도 식별되지 않을 수 있습니다.

EdDSA(Ed25519를 사용하는 Schnorr 기반 서명)는 Schnorr 서명이 선형이기 때문에 ECDSA보다 임계 방식으로 구현하기가 훨씬 쉽습니다. 응답 z = r + c*x가 덧셈 공유값의 합이기 때문입니다. Komlo와 Goldberg가 2020년에 제안한 FROST(유연한 라운드 최적화 Schnorr 임계 서명)는 신뢰할 수 있는 초기 설정 없이 2라운드 임계 Schnorr 서명을 수행합니다. FROST는 개인정보 보호 프로토콜과 암호화폐 지갑에 사용하기 위해 IETF(RFC 초안)에서 표준화가 진행 중입니다.

임계 ECDSA는 MtA 프로토콜과 영지식 증명 때문에 단일 참여자 ECDSA보다 계산 비용이 높습니다. GG20의 2자 서명에는 최신 하드웨어에서 약 1~2초가 걸리며, n이 더 큰 임계 방식에서는 쌍별 MtA 실행이 더 많이 필요하므로 시간이 더 오래 걸립니다. CGGMP21의 최적화를 사용하면 이 시간이 수백 밀리초로 줄어듭니다. 서명 지연 시간이 중요한 암호화폐 거래에서는 이러한 성능이 허용할 만하지만 무시할 수 없는 비용입니다.

임계 ECDSA는 기관 금융 분야에서 대규모로 운영되고 있습니다. Fireblocks는 GG20 기반 임계 ECDSA를 사용하여 4조 달러가 넘는 거래량을 보호합니다. Coinbase Prime은 임계 서명 기반 MPC 수탁 서비스를 사용합니다. Qredo와 Copper.co는 기관 자산 관리를 위해 임계 ECDSA를 제공합니다. tss-lib Go 라이브러리(Binance에서 사용)와 multi-party-sig(Coinbase에서 사용)는 주요 오픈 소스 구현입니다.

Paillier 동형 암호화는 임계 ECDSA에서 어떤 역할을 하나요?

임계 ECDSA를 사용하면 t명의 참여자가 어느 한 참여자도 전체 키를 알지 못한 상태에서 서명할 수 있습니다. ECDSA의 비선형 구조에는 Paillier 동형 암호화를 사용하는 MtA 변환이 필요합니다. GG18은 이 접근 방식을 개척했고, GG20은 악의적인 공격자에 대한 보안을 추가했으며, CGGMP21은 식별 가능한 중단을 추가했습니다. EdDSA/Schnorr는 FROST를 사용하면 더 쉽게 임계화할 수 있습니다(2라운드, 신뢰할 수 있는 초기 설정 없음). Fireblocks와 Coinbase의 운영 시스템은 수조 규모의 자산을 보호합니다.