Shamir Secret Sharing

k-of-n 방식은 같은 집합의 유효하고 서로 다른 지분 k개 중 어떤 조합으로도 복구합니다. n−k개 손실을 견디지만 협력하는 k명의 보유자도 비밀을 얻습니다. 예를 들어 3-of-5는 두 개 손실을 견디며 세 개는 아닙니다. 임계값은 가용성과 복구 가능한 집단 크기를 절충합니다. [Adi Shamir — How to Share a Secret (1979)]

비밀 S에 대해 f(x)=S+a1*x+…+a(k−1)*x^(k−1)를 선택합니다. 나머지 계수는 독립적이고 균등한 무작위 체 원소입니다. 지분은 서로 다르고 0이 아닌 x를 가진 (x,f(x))이며 x=0은 S를 바로 드러냅니다. k개 점의 라그랑주 보간으로 f(0)을 구합니다. 같은 점의 사본 두 개는 방정식을 추가하지 않습니다. [Adi Shamir — How to Share a Secret (1979)]

교육용으로만 S=5와 f(x)=5+3*x mod 17을 봅니다. 지분은 (1,8), (2,11), (3,14)입니다. 앞 두 점은 기울기 3과 상수 8−3=5를 주며 세 가지 쌍 모두 5를 복구합니다. (1,8)만 있으면 a=8−S mod 17일 때 0부터 16까지 모든 S와 양립합니다. 작은 체는 지갑 설계가 아닙니다. [Adi Shamir — How to Share a Secret (1979)]

이상적 방식에서는 k개 미만의 완전한 지분이 무한한 계산 능력에도 S의 정보를 주지 않습니다. 올바르게 선택한 독립 계수와 정해진 관측 모델이 전제입니다. 약한 난수, 계수 재사용, 부채널이나 추가 검사 데이터는 따로 분석해야 합니다. 다른 방법으로 추측 가능한 약한 비밀을 분산한다고 강해지지 않습니다. [Adi Shamir — How to Share a Secret (1979)] [SLIP-0039 — Shamir Secret-Sharing for Mnemonic Codes]

복구에는 같은 체, 값 인코딩, 인덱스와 집합 식별이 필요합니다. 소수체 GF(p)는 소수 나눗셈이 아니라 모듈러 역원을 쓰며 GF(256)의 연산은 modulo 256 나머지 연산과 다릅니다. SLIP-39는 구체적인 단어 목록, 메타데이터, 그룹, 암호화와 검사를 추가합니다. Shamir라는 두 프로그램도 지분이 호환되지 않을 수 있습니다. [Adi Shamir — How to Share a Secret (1979)] [SLIP-0039 — Shamir Secret-Sharing for Mnemonic Codes]

기본 보간은 지분 출처나 배포자의 정직성을 인증하지 않습니다. 손상된 점은 부족을 알리는 대신 다른 비밀을 반환할 수 있습니다. 탐지, 오류 정정과 verifiable secret sharing은 별도 가정이 있는 추가 구성입니다. 예를 들어 SLIP-39는 checksum과 digest를 추가하며 모든 Shamir Secret Sharing에 자동으로 포함되는 것은 아닙니다. [SLIP-0039 — Shamir Secret-Sharing for Mnemonic Codes] [NIST — Multi-Party Threshold Cryptography]

일반 복구에서는 전체 S가 한 환경에 나타나 유출될 수 있습니다. Multisig와 달리 Shamir Secret Sharing은 여러 독립적인 온체인 서명 키를 설정하지 않습니다. NIST가 구별하듯 임계값 서명은 추가 MPC 프로토콜로 키를 합치지 않고 지분을 다룰 수 있습니다. 단순히 분할한 뒤 결합하는 것에는 이 성질이 없습니다. [NIST — Multi-Party Threshold Cryptography]

한 계정의 파일 다섯 개는 손실이나 침해 위험을 분리하지 않습니다. 매개변수를 기록하고 신뢰할 수 있는 기기에서 복구를 확인해야 합니다. 같은 S의 새로운 무작위 다항식은 다른 집합을 만들며 이전 지분과 섞으면 안 됩니다. 충분한 이전 집합도 여전히 S를 복구하므로 다시 나누기만 해서는 이미 얻은 지분이나 유출된 비밀을 무효화하지 못합니다. [Adi Shamir — How to Share a Secret (1979)] [Trezor — Multi-share Backup]