Shamir's Secret Sharing과 Lagrange Interpolation

Secret Sharing

비밀 데이터를 여러 조각으로 "나누어" 분산 저장하는 작업이며, 유사시 여러 조각들을 취합하여 비밀 데이터를 복구한다. 단, 비밀 데이터를 n 등분하여 조각을 만들면, 각 조각에 비밀 데이터의 직접적인 정보가 담기게 되므로 바람직하지 않다. 비밀 데이터에 대한 어떤 정보도 담고 있지 않은 n 개의 조각을 만들 수 있을까? 여러 가지 설루션이 있지만 Shamir's Secret Sharing만 참고하면 된다.

Threshold Secret Sharing

n개의 조각 중에 일부를 분실하여도 비밀 데이터를 복구할 수 있도록 구성된 프로토콜이다. 하지만 이런 Threshold 기능은 공격자가 n 개 조각 중에 일부만 취득하여도 비밀데이터를 복구할 수 있으므로, 공격자에게도 득이 된다. 따라서 프로토콜마다 몇 개의 조각을 모아야 비밀 데이터를 복구할 수 있도록 할지를 의미 있게 정해야 한다.

전체 n개 조각중 t개를 모아야 복구가 가능하다는 의미에서 "t-out-of-n threshold Secret sharing"이라는 표현을 많이 사용한다. 단, 논문마다 복구 가능한 최소 조각 수를 t+1로 표기하기도 한다.

---

Shamir's Secret Sharing

논문: Shamir, Adi, How to share a secret, Communications of the ACM, 1979
Shamir의 Secret Sharing은 Threshold Secret Sharing 기능을 지원한다. 비전공자가 봐도 이해할만한 수준의 간단한 수학으로 강력한 Zero-knowledge Secret Sharing을 구성했다.
핵심 원리: t차 다항식을 유일하게 확정하려면 t+1개의 점이 필요하다.(t차 다항식은 t+1개의 계수로 이루어져 있기 때문)

split

• 소유자의 비밀 값을 key라 할 때, 상수항이 Key가 되며, 다른 모든 계수가 난수인 t차 다항식 f(x)를 구성한다.
• f(x)를 지나는 서로 다른 n개의 점을 share로 정의한다. (각 Player에게 분배)

reconstruct

• 각 Player에게서 최소 t+1개 이상의 Share을 받아온다.
• 각 Shares로 f(x)를 복구한 후, f(0)을 계산하여 key를 복구한다. (라그랑주 보간법)

굳이 어렵게?

굳이 어렵게 Shamir 방식으로 Split 하는 이유는 서론에서 언급한 것과 같이, 조각(share)에서 비밀 key의 어떠한 정보도 얻지 못하도록 하기 위함이다. 나의 조각을 보관하는 Player는 단지 "보관소" 역할만 수행하면 되는데 굳이 key에 대한 정보를 갖게 할 필요가 없다. 또는 나의 비밀 키가 상당히 가치가 있는 것이라면 "보관소" 또한 잠재적인 공격자가 될 수 있으므로 Shamir 스타일의 Split이 유용하다.
정보이론적으로, 공격자가 t개 미만의 조각을 획득하더라도 비밀 Key의 한 비트의 정보도 얻을 수 없다. 오로지 t개 이상의 조각을 모은 사람만이 Key 정보를 얻을 수 있다. 이러한 성질은 Access Control 응용에 잘 어울린다. 예를 들어 3명의 이사들에게 승인을 받아야 열람할 수 있는 비밀문서가 있다고 가정해보자. 이사 2명의 승인을 받은 직원 A는 비밀문서의 한 글자도 읽을 수 없지만, 3명의 승인을 받으면 전부 열람할 수 있다.

구현 고려사항

t와 n 값 설정

비밀 데이터를 몇 조각(n)으로 나눌 것인지, 몇 조각(t)을 모아야 복구가 가능하게 할지 사전에 정해야 한다.
t와 n은 client와 모든 Player가 사전에 공유해야 한다.

Secure Channel

Clinet는 조각을 Player에게 전송 시 Secure Channel로 전송해야 한다. 조각을 모으면 비밀 데이터를 복구할 수 있으므로 도청 공격자에 대한 대비를 위함이다.

Application Overview

Shamir Secret Sharing을 그대로 구현하여 사용하기에는 부족한 점들이 많다. 보다 유용한 응용을 위해서 다음과 같은 키워드의 연구들을 고려해볼 만하다. Dealerless SS, Verifiable SS, SS with Zero-knowledge, SS for MPC 등등...