視覚的秘密分散と加法的方式

視覚秘密分散（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_1 + s_2 + ... + s_n (mod p) として S を分散します。各 s_i は Z_p のランダムな要素です。2つの共有値 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）や複数機関によるアクセス制御システムの構成要素です。

パックドShamirでは、1つの多項式に複数の秘密を格納します。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トリプルを用いた加法的秘密分散を使用します。次は、閾値署名と実際の利用例について学びます。