샤미르 비밀 분산 (Shamir's Secret Sharing, SSS)

샤미르 비밀 분산(Shamir's Secret Sharing, SSS)은 비밀 하나를 n개의 조각(share)으로 나눠, 그중 t개 이상이 모이면 원래 비밀을 복원하고 t개 미만으로는 비밀에 대한 정보를 전혀 얻을 수 없도록 하는 방식입니다. 1979년 아디 샤미르(Adi Shamir)가 논문 「How to Share a Secret」에서 제안했습니다.

자세히 알아보기

원리는 '점 t개가 있으면 t−1차 다항식이 하나로 정해진다'는 사실입니다. 유한체 위에서 상수항이 비밀 s인 t−1차 다항식 f(x) = s + a₁x + … + a_{t−1}x^t−1을 무작위 계수로 만들고, 조각으로 (1, f(1)), (2, f(2)), …, (n, f(n))을 나눠 줍니다. t개의 조각이 모이면 라그랑주 보간으로 f(0) = s를 계산합니다. t−1개 이하의 조각으로는 모든 가능한 비밀 값이 똑같이 그럴듯하므로, 계산 능력과 무관한 정보 이론적 안전성을 갖습니다.

기본 SSS에는 한계가 있습니다. ① 조각을 나눠 준 사람이 엉터리 조각을 줘도 확인할 수 없습니다. 이를 보완한 것이 펠트먼(Feldman), 페더슨(Pedersen)의 검증 가능한 비밀 분산(VSS)입니다. ② 복원할 때 비밀 전체가 한 기기에 모이므로, 그 순간 그 기기가 해킹되면 비밀 전체가 노출됩니다. 키를 한 번도 모으지 않고 서명하려면 임계값 서명이나 MPC를 써야 합니다. ③ 무작위 계수는 반드시 암호학적으로 안전한 난수여야 합니다.

블록체인·암호화폐에서는

SatoshiLabs의 SLIP-0039 표준은 SSS로 지갑 시드를 여러 개의 니모닉 조각으로 나누며, Trezor 하드웨어 지갑은 이를 'Shamir 백업'으로 제공합니다. 예를 들어 3개 중 2개 조각만 있으면 복구되도록 구성해 집과 금고 등 서로 다른 장소에 보관할 수 있습니다. 24단어 니모닉을 단순히 8단어씩 셋으로 자르는 것은 SSS가 아니며, 조각 하나만으로도 남은 경우의 수가 크게 줄어 위험합니다. 임계값 서명과 MPC 지갑의 키 생성 단계에서도 SSS가 기본 부품으로 쓰입니다.

쉽게 말하면

금고 비밀번호를 여러 사람에게 나눠 맡기되, 정해진 인원 이상이 모이면 비밀번호를 알아낼 수 있고 그보다 적으면 아무것도 알 수 없게 만드는 방법입니다.

예시

11을 법으로 하는 체에서 비밀 s = 7, t = 2, f(x) = 7 + 3x로 정하면 조각은 (1, 10), (2, 2), (3, 5)입니다. (1, 10)과 (2, 2)로 직선을 다시 구하면 기울기 3, 절편 7이 나와 비밀 7이 복원됩니다.