선행 지식

• Lagrange 보간법

1. 개요

**Shamir's Secret Sharing (SSS)**은 1979년 Adi Shamir가 고안한 암호화 알고리즘으로, 하나의 비밀을 여러 조각으로 나누어 분산 저장하는 방식이다.

이 알고리즘의 핵심은 $(k, n)$ 임계값 체계이다:

• $n$ (Total Shares): 비밀을 나눈 전체 조각의 개수
• $k$ (Threshold): 비밀을 복원하기 위해 필요한 최소 조각의 개수

주요 특징:

• $k$개 이상의 조각이 모이면 원래의 비밀 $S$를 완벽하게 복원할 수 있다
• $k-1$개 이하의 조각으로는 비밀에 대한 어떠한 정보도 얻을 수 없다

2. 기본 개념

• SSS는 라그랑주 보간법을 기초로 한다. 기하학적 원리는 다음과 같다

  

• 2개의 점은 하나의 직선(1차 함수)을 유일하게 결정한다

  

• 3개의 점은 하나의 포물선(2차 함수)을 유일하게 결정한다

• $k$개의 점은 $k-1$차 다항식을 유일하게 결정한다

2.1 비밀 분산

비밀 $S$를 정수로 변환한 후, 이를 $k-1$차 다항식의 상수항(y절편)으로 설정한다.

1. 다항식 생성:

$$ f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_{k-1}x^{k-1} $$

• $a_0 = S$ (평문)
• 나머지 계수 $a_1, \ldots, a_{k-1}$은 무작위로 선택된 숫자이다

2. 조각 생성:

$x = 1, 2, \ldots, n$을 대입하여 $n$개의 좌표 점 $(x, f(x))$를 계산한다. 각 점이 참여자들에게 나눠줄 조각이 된다.

2.2 비밀 복원

$k$개 이상의 점 $(x_i, y_i)$를 모으면, 라그랑주 보간법을 통해 원본 다항식 $f(x)$를 재구성할 수 있다.

라그랑주 기저 다항식 $\ell_j(x)$를 이용한 복원 공식:

$$ f(x) = \sum_{j=0}^{k-1} y_j \ell_j(x) $$

여기서 라그랑주 기저 다항식은: