시각적 비밀 분산과 가법 방식

시각 비밀 공유(Naor와 Shamir, 1994)는 이미지를 n개의 투명 필름으로 나눕니다. k개의 투명 필름을 겹치면 비밀 이미지가 나타나지만, 그보다 적은 수를 겹치면 아무것도 드러나지 않습니다. 계산 능력이 무한한 공격자에게도 마찬가지입니다.

비밀 이미지의 각 픽셀은 2x2 블록으로 확장됩니다. 검은색 픽셀의 경우 두 공유 조각에 서로 보완되는 패턴을 배정하므로 겹치면 전체가 검은색이 됩니다. 흰색 픽셀의 경우 두 공유 조각에 같은 패턴을 배정하므로 겹치면 검은색이 50%인 회색으로 보입니다. 눈은 이 차이를 인식합니다.

비트 문자열의 경우 다음과 같이 비밀값 S를 공유합니다. 무작위 R_1, R_2, ..., R_{n-1}을 생성하고 R_n = S XOR R_1 XOR ... XOR R_{n-1}로 설정합니다. n개의 공유 조각을 모두 XOR하면 S가 됩니다. n-1개 공유 조각 중 어떤 부분집합도 균등한 무작위 값이므로 S에 관한 정보를 전혀 드러내지 않습니다.

XOR 기반 가법 공유는 n-of-n 방식이므로 모든 공유 조각이 필요합니다. Shamir SSS는 k-of-n 방식이므로 임의의 k개 공유 조각을 사용할 수 있습니다. 가법 공유는 더 단순하고 빠르며, Shamir는 임의의 임계값을 처리합니다. MPC 프로토콜은 산술 연산에 가법 공유를 사용하는 경우가 많습니다.

정수 비밀값의 경우 S를 S = s_1 + s_2 + ... + s_n (mod p)로 공유합니다. 각 s_i는 Z_p의 무작위 원소입니다. 공유된 두 값 A와 B를 더할 때는 각 참여자가 자신의 공유 조각을 로컬에서 더해 (a_i + b_i) mod p를 계산합니다. 덧셈에는 통신이 필요하지 않습니다.

공유된 비밀값을 곱하려면 참여자 간 상호작용이 필요합니다. 고전적인 Beaver 삼중항 방식에서는 공유된 무작위 값 (a, b, c=ab)을 미리 계산합니다. x*y를 계산할 때 (x-a)와 (y-b)를 모든 참여자에게 공개합니다. 이 값들은 x와 y에 관한 정보를 전혀 드러내지 않으며, 그다음 삼중항을 사용해 x*y를 계산합니다.

선형 비밀 공유 방식(LSSS)은 모든 단조 접근 구조를 구현합니다. Shamir는 LSSS입니다. LSSS는 속성 기반 암호화(ABE)와 다중 기관 접근 제어 시스템을 구성하는 기본 요소입니다.

Packed Shamir는 하나의 다항식에 여러 비밀값을 공유합니다. k개의 비밀값을 차수 (n-k) 다항식의 계수로 부호화합니다. 여러 값을 동시에 공유해야 하는 MPC 프로토콜에서 통신 비용을 상각할 수 있습니다.

기본 공유 방식은 악의적인 공유 조각 보유자가 유효하지 않은 공유 조각을 제출하는 것을 막지 못합니다. 검증 가능한 비밀 공유(VSS)는 커밋값을 추가하고, 견고한 비밀 공유는 오류 정정을 추가하므로 잘못된 공유 조각이 t개 있어도 복원에 성공할 수 있습니다.

시각 암호: 인쇄 문서 인증, 안전한 투표용지. 가법 공유: SPDZ MPC, 연합 학습의 안전한 집계(Google). 임계값 방식: 하드웨어 지갑 시드 백업, 기업 키 관리.

(k,n) 램프 방식은 보안성이 더 낮습니다. k-d개보다 적은 공유 조각은 부분적인 정보(d단계의 비밀성)를 드러냅니다. 부분 공유 조각에 완전한 비밀성이 필요하지 않지만 저장 효율이 중요한 경우에 사용됩니다. Shamir보다 더 짧은 공유 조각을 사용할 수 있습니다.

시각 암호는 이미지를 투명 필름으로 나누고, 가법 공유는 n-of-n 방식에 XOR를 사용하며, Shamir는 k-of-n을 처리합니다. MPC는 곱셈에 Beaver 삼중항과 함께 가법 공유를 사용합니다. 다음 주제: 임계값 서명과 실제 활용