비밀 공유

[섬네일|upright=1.3|[시각 암호 방식의 한 예시: 두 개의 구성 이미지(문자 A와 B를 보여줌)가 합쳐지면 비밀 문자 S가 드러난다. 비밀은 단일 구성 요소만으로는 결정될 수 없다.]]
**비밀 공유**(secret sharing) 또는 **비밀 분할**(secret splitting)은 그룹 구성원들 사이에 비밀을 분산시키는 방법을 의미한다. 개별 구성원은 비밀에 대한 어떠한 이해할 수 있는 정보도 보유하지 않지만, 충분한 수의 구성원들이 자신들의 '지분'을 결합할 때 비밀이 재구성될 수 있다. 안전하지 않은 비밀 공유는 공격자가 각 지분으로 더 많은 정보를 얻을 수 있도록 허용하지만, 안전한 비밀 공유는 '전부 아니면 전무'(여기서 '전부'는 필요한 지분 수를 의미)이다.

한 가지 유형의 비밀 공유 체계에는 한 명의 딜러와 n명의 플레이어가 있다. 딜러는 플레이어들에게 비밀의 지분을 제공하지만, 특정 조건이 충족될 때만 플레이어들은 자신들의 지분으로부터 비밀을 재구성할 수 있다. 딜러는 t개(임계값) 이상의 플레이어 그룹이 함께 비밀을 재구성할 수 있도록 각 플레이어에게 지분을 제공하지만, t개 미만의 플레이어 그룹은 재구성할 수 없다. 이러한 시스템을 -임계값 체계(때로는 -임계값 체계로 표기되기도 함)라고 한다.

비밀 공유는 아디 샤미르와 조지 블레이클리에 의해 1979년에 각각 독립적으로 발명되었다.

## 중요성

비밀 공유 체계는 매우 민감하고 중요한 정보를 저장하는 데 이상적이다. 예시로는 암호화 키, 미사일 발사 코드, 숫자계좌 등이 있다. 이러한 정보들은 노출될 경우 치명적일 수 있으므로 매우 기밀하게 유지되어야 하지만, 또한 손실되지 않도록 하는 것도 중요하다. 기존의 암호화 방법은 높은 수준의 기밀성과 신뢰성을 동시에 달성하는 데 적합하지 않다. 이는 암호화 키를 저장할 때 최대의 기밀성을 위해 키의 단일 사본을 한 곳에 보관할 것인지, 아니면 더 큰 신뢰성을 위해 여러 사본을 다른 위치에 보관할 것인지 선택해야 하기 때문이다. 여러 사본을 저장하여 키의 신뢰성을 높이는 것은 추가적인 공격 벡터를 생성하여 기밀성을 낮춘다. 즉, 사본이 잘못된 사람의 손에 들어갈 기회가 더 많아지는 것이다. 비밀 공유 체계는 이 문제를 해결하며, 임의로 높은 수준의 기밀성과 신뢰성을 달성할 수 있도록 한다.

비밀 공유는 또한 비밀의 배포자가 그룹을 '집합적으로' 신뢰할 수 있도록 한다. 전통적으로 비밀을 보관을 위해 그룹에 맡기는 것은 배포자가 그룹의 모든 구성원을 완전히 신뢰해야 할 것을 요구한다. 비밀 공유 체계는 모든 구성원을 항상 신뢰할 수 없더라도 배포자가 비밀을 그룹에 안전하게 저장할 수 있도록 한다. 배신자의 수가 비밀을 재구성하는 데 필요한 임계값보다 많지 않는 한 비밀은 안전하다.

비밀 공유 체계는 클라우드 컴퓨팅 환경에서 중요하다. 따라서 키는 임계값 비밀 공유 메커니즘을 통해 여러 서버에 분산될 수 있다. 키는 필요할 때 재구성된다.

비밀 공유는 또한 센서 네트워크에서도 제안되었다. 센서 네트워크에서는 링크가 도청될 가능성이 있으므로, 데이터를 지분으로 보내 도청자의 작업을 어렵게 만든다. 이러한 환경에서의 보안은 지분 구성 방식을 지속적으로 변경하여 더욱 강화될 수 있다.

## "보안" 대 "비보안" 비밀 공유
보안 비밀 공유 체계는 t개 미만의 지분을 가진 사람이 0개의 지분을 가진 사람보다 비밀에 대해 더 많은 정보를 얻지 못하도록 지분을 분배한다.

예를 들어, 비밀 문구 "password"를 "pa––––––", "––ss––––", "––––wo––", "––––––rd"로 나누는 비밀 공유 체계를 고려해 보자. 0개의 지분을 가진 사람은 암호가 여덟 글자로 구성되어 있다는 것만 알며, 따라서 268 = 2080억 가지 가능한 조합 중에서 암호를 추측해야 한다. 그러나 한 개의 지분을 가진 사람은 266 = 3억 8백만 가지 조합 중에서 여섯 글자만 추측하면 되며, 더 많은 사람들이 공모할수록 이러한 방식이 이어진다. 결과적으로 이 시스템은 "보안" 비밀 공유 체계가 아니다. 왜냐하면 t개 미만의 비밀 지분을 가진 플레이어가 필요한 모든 지분을 먼저 얻지 않고도 내부 비밀을 얻는 문제를 줄일 수 있기 때문이다.

대조적으로, X가 공유될 비밀이고 Pi가 공개 비대칭 암호화 키이며 Qi가 해당 개인 키인 비밀 공유 체계를 고려해 보자. 각 플레이어 J에게는 }가 제공된다. 이 체계에서 개인 키 1을 가진 플레이어는 가장 바깥쪽 암호화 계층을 제거할 수 있고, 키 1과 2를 가진 플레이어는 첫 번째와 두 번째 계층을 제거할 수 있으며, 이러한 방식이 이어진다. N개 미만의 키를 가진 플레이어는 해당 개인 키가 없는 공개 키 암호화된 덩어리를 먼저 해독하지 않고는 비밀 X에 완전히 도달할 수 없다. 이는 현재 계산적으로 불가능하다고 여겨지는 문제이다. 또한 N개의 모든 개인 키를 가진 사용자는 모든 외부 계층을 해독하여 비밀 X를 얻을 수 있으므로 이 시스템은 보안 비밀 배포 시스템임을 알 수 있다.

## 한계
일부 비밀 공유 체계는 정보 이론적으로 안전하다고 하며 그렇게 증명될 수 있는 반면, 다른 체계는 무조건적인 보안을 포기하고 효율성을 개선하는 대신 다른 일반적인 암호화 기본 요소만큼 안전하다고 간주될 만큼의 보안을 유지한다. 예를 들어, 각 지분이 현재 가능한 어떤 적도 저지하기에 충분하다고 간주되므로 비밀을 각각 128비트의 엔트로피를 가진 지분으로 보호할 수 있으며, 평균 크기 2127의 무차별 대입 공격이 필요하다.

모든 무조건적으로 안전한 비밀 공유 체계에 공통적으로 다음과 같은 한계가 있다:
* 비밀의 각 지분은 비밀 자체보다 최소한 커야 한다. 이 결과는 정보 이론에 기반하지만, 직관적으로 이해할 수 있다. 개의 지분이 주어졌을 때, 비밀에 대한 어떠한 정보도 결정될 수 없다. 따라서 마지막 지분은 비밀 자체만큼의 정보를 포함해야 한다. 이 한계에 대한 해결책으로 비밀을 공유하기 전에 먼저 압축하는 경우가 있지만, 많은 비밀(예: 키)은 고품질 무작위 데이터처럼 보여 압축하기 어렵기 때문에 종종 불가능하다.
* 모든 비밀 공유 체계는 지분을 구성하는 데 무작위 비트를 사용한다. t개의 지분 임계값을 가진 1비트 비밀을 분배하려면 개의 무작위 비트가 필요하다. b비트의 비밀을 분배하려면 비트의 엔트로피가 필요하다.

## 사소한 비밀 공유
참고: n은 '플레이어'의 총 수이며, 그들 사이에 지분이 분배되고, t는 비밀을 공개하는 데 필요한 최소 플레이어 수이다.

### t = 1
t = 1 비밀 공유는 사소하다. 비밀은 단순히 모든 n명의 참가자에게 분배될 수 있다.

### t = n
모든 지분이 비밀을 복구하는 데 필요한 경우 인 여러  비밀 공유 체계가 있다:

# 비밀을 임의 길이의 이진수 s로 인코딩한다. 각 플레이어 i(총 플레이어 수보다 하나 적음)에 대해 s와 동일한 길이의 무작위 이진수 pi를 제공한다. 지분이 없는 플레이어에게는 로 계산된 지분을 제공한다. 여기서 ⊕는 비트 배타적 논리합을 나타낸다. 비밀은 모든 플레이어의 숫자(pi, 1 ≤ i ≤ n)의 비트 단위 배타적 논리합이다.
# 대신, (1)은 모든 군에서 이진 연산을 사용하여 수행될 수 있다. 예를 들어, 232를 법으로 하는 덧셈을 가진 정수들의 순환군을 취하는데, 이는 이진 오버플로를 버린 채 정의된 덧셈을 가진 32비트 정수에 해당한다. 비밀 s는 M개의 32비트 정수 벡터로 분할될 수 있으며, 이를 vsecret라고 부른다. 그러면 명의 플레이어 각각은 균일 확률 분포에서 독립적으로 추출된 M개의 32비트 정수 벡터를 받으며, 플레이어 i는 vi를 받는다. 나머지 플레이어는 vn = vsecret − v1 − v2 − ... − vn−1를 받는다. 비밀 벡터는 모든 플레이어의 벡터를 합하여 복구될 수 있다.

### 1 < t < n
어려움은 여전히 안전하면서도 모든 n개의 지분을 요구하지 않는 체계를 만드는 데 있다.

공간 효율성이 문제가 되지 않을 때, 사소한  체계는 단순히 각 부분집합에 대해 체계를 적용함으로써 플레이어의 원하는 부분집합에 비밀을 공개하는 데 사용될 수 있다. 예를 들어, 앨리스, 밥, 캐럴 세 명의 플레이어 중 두 명에게 비밀 s를 공개하려면, s에 대해 세 가지(\binom{3}{2}) 다른  비밀 지분을 생성하여 앨리스와 밥, 앨리스와 캐럴, 밥과 캐럴에게 세 가지 두 지분 세트를 제공한다.

### {1, 2, ..., n}의 원하는 부분집합에 속하는 t
예를 들어, 회사의 이사회가 비밀 공식을 보호하고 싶다고 상상해 보자. 회사 사장은 필요할 때 공식을 열람할 수 있어야 하지만, 비상시에는 12명의 이사회 구성원 중 3명이라도 함께 비밀 공식을 해제할 수 있어야 한다. 이를 달성하는 한 가지 방법은 이고 인 비밀 공유 체계를 사용하는 것으로, 사장에게 3개의 지분을 주고 각 이사회 구성원에게 1개의 지분을 준다.

## 효율적인 비밀 공유
사소한 접근 방식은 부분집합의 수가 증가함에 따라 빠르게 비실용적이 된다. 예를 들어, 100명의 플레이어 중 50명에게 비밀을 공개하려면 \binom{100}{50} \approx 1.009\times 10^{29}개의 체계를 생성해야 하고 각 플레이어는 각 체계에 대해 \binom{99}{49} \approx 5.04\times 10^{28}개의 고유한 지분 세트를 유지해야 한다. 최악의 경우, 증가율은 기하급수적이다. 이는 플레이어 임계값으로 비밀을 효율적으로 공유할 수 있는 체계를 찾는 데 박차를 가했다.

### 샤미르의 체계

이 체계에서는 n개의 지분 중 t개를 사용하여 비밀을 복구할 수 있다. 이 시스템은 t개의 점이 모두 다항식 위에 놓이는, 차의 고유한 다항식을 구성할 수 있다는 아이디어에 의존한다. 직선을 정의하는 데 두 점이 필요하고, 이차 곡선을 완전히 정의하는 데 세 점이 필요하며, 삼차 곡선을 정의하는 데 네 점이 필요하다. 즉, 차 다항식을 정의하는 데 t개의 점이 필요하다. 이 방법은 비밀을 첫 번째 계수로 하고 나머지 계수는 무작위로 선택하여 차 다항식을 만드는 것이다. 다음으로 곡선 위에 n개의 점을 찾아 각 플레이어에게 하나씩 준다. n명의 플레이어 중 최소 t명이 자신들의 점을 공개하면, 그 점들에 차 다항식을 맞추기에 충분한 정보가 있으며, 첫 번째 계수가 비밀이 된다.

### 블레이클리의 체계
같은 평면에 있는 두 개의 평행하지 않은 선은 정확히 한 점에서 교차한다. 공간에 있는 세 개의 평행하지 않은 평면은 정확히 한 점에서 교차한다. 더 일반적으로, n개의 평행하지 않은 -차원 초평면은 특정 점에서 교차한다. 비밀은 교점의 단일 좌표로 인코딩될 수 있다. 비밀이 모든 좌표를 사용하여 인코딩되면, 비록 그것들이 무작위일지라도, 내부자(하나 이상의 -차원 초평면을 소유한 사람)는 그의 평면에 있어야 한다는 것을 알기 때문에 비밀에 대한 정보를 얻게 된다. 내부자가 외부자보다 비밀에 대해 더 많은 지식을 얻을 수 있다면, 시스템은 더 이상 정보 이론적 보안을 갖지 않는다. n개의 좌표 중 하나만 사용된다면, 내부자는 외부자보다 더 많은 것을 알지 못한다(즉, 2차원 시스템의 경우 비밀이 x축에 있어야 한다는 것). 각 플레이어에게 초평면을 정의하기에 충분한 정보가 주어지며, 비밀은 평면들의 교점을 계산한 다음 해당 교점의 지정된 좌표를 취하여 복구된다.





블레이클리의 체계는 샤미르의 체계보다 공간 효율성이 떨어진다. 샤미르의 지분은 각각 원래 비밀만큼 크기만 한 반면, 블레이클리의 지분은 t배 더 크다(t는 임계 플레이어 수). 블레이클리의 체계는 어떤 평면을 지분으로 사용할 수 있는지에 대한 제약을 추가하여 더 강화될 수 있다. 그 결과 체계는 샤미르의 다항식 시스템과 동등하다.

### 중국인의 나머지 정리 사용

중국인의 나머지 정리는 비밀 공유에서도 사용될 수 있다. 이는 S 라는 조건 하에, k개의 서로소 정수 m_1, m_2, ..., m_k에 대해 modulo k에서 숫자 S를 고유하게 결정하는 방법을 제공하기 때문이다. 중국인의 나머지 정리를 사용하는 두 가지 비밀 공유 체계인 미그노트(Mignotte)와 애스무스-블룸(Asmuth-Bloom) 체계가 있다. 이들은 임계값 비밀 공유 체계로, 지분은 정수 m_i를 modulo로 줄여서 생성되며, 비밀은 중국인의 나머지 정리를 사용하여 합동 시스템을 푸는 방식으로 복구된다.

## 사전 예방적 비밀 공유

플레이어들이 자신들의 지분을 안전하지 않은 컴퓨터 서버에 저장한다면, 공격자가 침입하여 지분을 훔칠 수 있다. 비밀을 변경하는 것이 실용적이지 않은 경우, 손상되지 않은(샤미르 방식의) 지분을 갱신할 수 있다. 딜러는 상수 항이 0인 새로운 무작위 다항식을 생성하고, 각 남아있는 플레이어에 대해 새로운 순서쌍을 계산하는데, 이때 이전 순서쌍과 새로운 순서쌍의 x-좌표는 동일하다. 각 플레이어는 이전 y-좌표와 새로운 y-좌표를 서로 더하고 그 결과를 비밀의 새로운 y-좌표로 유지한다.

공격자가 축적한 모든 업데이트되지 않은 지분은 쓸모 없게 된다. 공격자는 임계값에 도달할 만큼 충분한 다른 업데이트되지 않은 지분을 찾을 수 있는 경우에만 비밀을 복구할 수 있다. 플레이어들이 이전 지분을 삭제했기 때문에 이러한 상황은 발생하지 않아야 한다. 또한 공격자는 업데이트 파일에 무작위 정보만 포함되어 있기 때문에 업데이트 파일에서 원래 비밀에 대한 어떠한 정보도 복구할 수 없다.

딜러는 업데이트를 배포하면서 임계값을 변경할 수 있지만, 만료된 지분을 보관하는 플레이어들에 대해 항상 경계해야 한다.

## 검증 가능한 비밀 공유

플레이어는 다른 지분에 접근하기 위해 자신의 지분에 대해 거짓말을 할 수 있다. 검증 가능한 비밀 공유(VSS) 체계는 플레이어가 합리적인 오류 확률 범위 내에서 다른 플레이어가 자신의 지분 내용에 대해 거짓말을 하지 않는다는 것을 확신할 수 있도록 한다. 이러한 체계는 일반적으로 계산될 수 없으며, 플레이어들은 어떤 개인이 무엇이 더해지고 곱해지는지 정확히 알지 못하는 상태에서 집단적으로 숫자를 더하고 곱해야 한다. 탈 라빈과 마이클 벤-오르는 "적응형" 공격자가 공개된 정보에 따라 실시간으로 전략을 변경할 수 있더라도, 딜러 또는 임계값 수의 3분의 1에 해당하는 플레이어의 부정행위를 탐지할 수 있는 다자간 컴퓨팅(MPC) 시스템을 고안했다.

## 계산적으로 안전한 비밀 공유

무조건적으로 안전한 비밀 공유 체계의 단점은 지분의 저장 및 전송에 비밀 크기 곱하기 지분 수에 해당하는 저장 및 대역폭 자원이 필요하다는 것이다. 만약 비밀의 크기가 1GB이고 지분 수가 10개라면, 주주들은 10GB의 데이터를 저장해야 한다. 무조건적인 보안 요구 사항을 포기하면서 비밀 공유 체계의 효율성을 크게 높이기 위한 대체 기술들이 제안되었다.

이러한 기술 중 하나인 '단축된 비밀 공유'는 라빈의 정보 분산 알고리즘(IDA)과 샤미르의 비밀 공유를 결합한다. 데이터는 먼저 대칭 암호화 알고리즘을 사용하여 무작위로 생성된 키로 암호화된다. 다음으로 이 데이터는 라빈의 IDA를 사용하여 N개의 조각으로 분할된다. 이 IDA는 비밀 공유 체계와 유사하게 임계값으로 구성되지만, 비밀 공유 체계와는 달리 결과 데이터의 크기는 (조각 수 / 임계값)만큼 증가한다. 예를 들어, 임계값이 10이고 IDA로 생성된 조각 수가 15개라면, 모든 조각의 총 크기는 원래 입력 크기의 (15/10) 또는 1.5배가 된다. 이 경우, 이 체계는 샤미르 체계를 데이터에 직접 적용한 것보다 10배 더 효율적이다. 단축된 비밀 공유의 마지막 단계는 샤미르 비밀 공유를 사용하여 무작위로 생성된 대칭 키(일반적으로 16-32바이트 정도)의 지분을 생성하고, 각 주주에게 하나의 지분과 하나의 조각을 제공하는 것이다.

AONT-RS로 알려진 관련 접근 방식은 IDA에 대한 전처리 단계로 데이터에 전부 아니면 전무 변환을 적용한다. 전부 아니면 전무 변환은 임계값 미만의 어떤 수의 지분도 데이터를 해독하기에 불충분하다는 것을 보장한다.

## 다중 비밀 및 공간 효율적인 (일괄) 비밀 공유
정보 이론적으로 안전한 k-of-n 비밀 공유 체계는 n개의 지분을 생성하며, 각 지분의 크기는 비밀 자체의 크기 이상이므로 필요한 총 저장 공간은 비밀보다 최소 n배 더 커진다. 매튜 K. 프랭클린과 모티 융이 설계한 다중 비밀 공유에서는 다항식의 여러 점이 비밀을 호스팅한다. 이 방법은 코딩에서 다자간 계산에 이르는 수많은 응용 분야에서 유용하게 사용되었다. 아비쉑 파라흐와 수바시 카크가 고안한 공간 효율적인 비밀 공유에서는 각 지분의 크기가 비밀을 로 나눈 것과 거의 같다.

이 체계는 반복된 다항식 보간을 활용하며, 웹 및 센서 네트워크에서의 안전한 정보 분산에 잠재적인 응용 가능성이 있다. 이 방법은 유한 필드에서 다항식의 근을 포함하는 데이터 분할에 기반한다. 관련 공간 효율적인 비밀 공유 체계의 일부 취약점은 나중에 지적되었다. 그들은 보간법에 기반한 체계가 분산될 k개의 비밀이 본질적으로 차 미만의 다항식에서 생성될 때  체계를 구현하는 데 사용될 수 없으며, 공유될 모든 비밀이 동일한 경우 등에는 작동하지 않는다는 것을 보여준다.

## 다른 용도 및 응용 분야
비밀 공유 체계는 여러 서버에 걸쳐 비밀을 보호하고 여러 서버 오류에도 불구하고 복구될 수 있도록 한다. 딜러는 여러 개의 개별 참가자 역할을 하여 참가자들 사이에 지분을 분배할 수 있다. 각 지분은 다른 서버에 저장될 수 있지만, 딜러는 최소 t개의 지분을 복구할 수 있는 한 여러 서버가 고장나더라도 비밀을 복구할 수 있다. 그러나 한 서버에 침입한 크래커는 각 서버에 t개 미만의 지분이 저장되어 있는 한 비밀을 알 수 없다.

이는 워싱턴 대학교의 바니시 컴퓨터 프로젝트의 주요 개념 중 하나로, 임의의 키가 데이터를 암호화하는 데 사용되고, 키는 P2P 네트워크의 여러 노드에 비밀로 분산된다. 메시지를 해독하려면 네트워크의 최소 t개 노드에 접근할 수 있어야 한다. 이 특정 프로젝트의 원리는 네트워크의 비밀 공유 노드 수가 시간이 지남에 따라 자연스럽게 감소하여 비밀이 결국 사라지도록 하는 것이다. 그러나 네트워크는 시빌 공격에 취약하여 바니시를 안전하지 않게 만든다.

어떤 시점에서든 콘텐츠를 해독할 만큼 충분한 정보를 가진 모든 주주는 X의 사본을 가져와 저장할 수 있다. 결과적으로, 바니시와 같은 도구 및 기술이 일정 시간 후에 자체 시스템 내에서 데이터를 복구 불가능하게 만들 수 있지만, 악의적인 사용자가 데이터를 본 이상 데이터의 삭제를 강제할 수는 없다. 이는 디지털 권리 관리의 주요 난제 중 하나이다.

딜러는 원래 비밀을 복구하는 데 필요한 t개의 지분을 모두 단일 수신자에게 보낼 수 있다. 공격자는 비밀을 복구하기 위해 모든 t개의 지분을 가로채야 하는데, 이는 단일 파일을 가로채는 것보다 훨씬 어려운 작업이다. 특히 지분이 다른 매체(예: 일부는 인터넷을 통해, 일부는 CD로 우편 발송)를 사용하여 전송될 경우 더욱 그렇다.

큰 비밀의 경우, 비밀을 암호화한 다음 비밀 공유를 사용하여 키를 분배하는 것이 더 효율적일 수 있다.

비밀 공유는 보안 다자간 계산을 위한 여러 프로토콜에서 중요한 기본 요소이다.
비밀 공유는 시스템에서 사용자 인증에도 사용될 수 있다.

## 같이 보기

## 각주

## 외부 링크
* 우분투 맨페이지: gfshare – GF(2<sup>8</sup>)에서 샤미르 비밀 공유 설명
* 샤미르와 블레이클리 체계 설명
* PGP (및 기타?) 암호 문구 복구에 비밀 공유 사용 특허 
* 비밀 공유 체계에 대한 참고문헌
* 
* 

분류:암호학