Shamir 비밀 분산: 다항식 수학

Shamir 비밀 공유(1979)는 유한체 위의 무작위 (k-1)차 다항식에서 비밀을 y절편(f(0))으로 인코딩합니다. 임의의 k개 점은 다항식을 유일하게 결정하며(라그랑주 보간), k개보다 적은 점으로는 아무것도 알아낼 수 없습니다.

n명의 당사자 사이에서 임계값 k로 비밀 S를 공유하려면 S와 n보다 큰 소수 p를 선택합니다. 무작위 계수 a_1, ..., a_{k-1}를 선택합니다. f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p)로 정의합니다. 당사자 i는 공유 조각 (i, f(i))를 받습니다.

비밀 S=7, p=17, k=2(선형 다항식)입니다. a_1=3을 선택합니다. f(x)=7+3x mod 17입니다. 공유 조각: (1,10), (2,13), (3,16). 임의의 두 점으로 직선을 결정할 수 있습니다. f(0)=7입니다. 점 하나만으로는 가능한 직선이 무한히 많으므로 S에 대한 정보가 전혀 없습니다.

k개의 점 (x_1,y_1),...,(x_k,y_k)가 주어졌을 때 라그랑주 보간법을 사용해 f(0)을 복원합니다: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. 모든 산술 연산은 모듈러 방식으로 수행됩니다. 부동소수점 연산 없이 유한체에서 정확하게 복원합니다.

from functools import reduce def lagrange(shares, p): xs = [s[0] for s in shares] ys = [s[1] for s in shares] result = 0 for i, (xi, yi) in enumerate(shares): num = reduce(lambda a,b: a*b%p, [(-xj)%p for j,xj in enumerate(xs) if j!=i], 1) den = reduce(lambda a,b: a*b%p, [(xi-xj)%p for j,xj in enumerate(xs) if j!=i], 1) result = (result + yi * num * pow(den, p-2, p)) % p return result

k-1개의 공유 조각이 주어졌을 때, 가능한 모든 비밀값 S에 대해 이 k-1개의 점을 지나는 차수 k-1의 다항식은 정확히 하나씩 존재합니다. 따라서 k-1개의 공유 조각을 알고 있어도 [0, p-1]의 모든 S 값은 동일한 확률을 가지므로 정보가 전혀 공개되지 않습니다.

p는 비밀값과 n보다 커야 합니다. 일반적으로 128비트 비밀값에는 p = 2^127-1(메르센 소수)을 선택합니다. 이렇게 하면 모든 공유 조각이 128비트 안에 들어가고 연산도 효율적입니다. 또는 512비트 비밀값에는 p=2^521-1을 사용할 수 있습니다.

기본 SSS에는 공유 조각의 무결성을 보장하는 기능이 없습니다. 악의적인 공유 조각 보유자가 잘못된 공유 조각을 제출하면 비밀값이 잘못 복원될 수 있습니다. Feldman VSS(검증 가능한 비밀 공유)는 g^{a_i} mod p에 대한 커밋값을 공개하므로 다항식을 공개하지 않고도 공유 조각을 검증할 수 있습니다.

공유 조각은 주기적으로 새로 만들 수 있습니다. 같은 비밀값 S를 사용해 새 다항식을 생성하고 새로운 공유 조각을 다시 분배하면 기존 공유 조각은 무효가 됩니다. 공격자가 갱신 후 공유 조각 보유자를 침해하더라도 쓸모없는 기존 공유 조각만 얻게 됩니다. 장기간 운영되는 키 관리 시스템에서 사용됩니다.

ssss(Linux 명령줄 도구), python-secret-sharing, hashicorp/vault는 봉인 메커니즘에 SSS를 사용하며, Trezor 하드웨어 지갑은 지갑 시드 백업에 SSS를 사용합니다(SLIP-39). 모두 큰 소수체에서 작동합니다.

SSS에서는 신뢰할 수 있는 분배자가 공유 조각을 생성하고 분배해야 합니다(분배자는 비밀값을 알고 있습니다). 분배자를 두지 않는 상황에서는 DKG가 필요합니다. 복원 과정에서는 k개의 공유 조각을 가진 사람이 비밀값을 알게 되지만, MPC 또는 임계값 서명을 사용하면 이러한 문제를 없앨 수 있습니다.

Shamir의 SSS는 비밀값을 다항식의 y절편으로 부호화합니다. 라그랑주 보간으로 k개의 공유 조각에서 비밀값을 복원합니다. k개보다 적은 공유 조각에 대해서는 정보 이론적으로 완전한 보안을 제공합니다. 다음 주제: 시각 비밀 공유와 가법 비밀 공유