Additive Secret Sharing Scheme

概要

シャミアの秘密分散法と並ぶ秘密分散手法の一つ

秘密情報 $ xを$ x = x_1 + x_2 + ... + x_nなるシェア$ x_iに分散する

SPDZが$ Additive ~ Secret ~ Sharing ~ Schemeを用いたフレームワークの代表例

詳細

$ i番目のパーティ$ P_iは$ xのシェア$ x_iをもつ

$ xは$ n個のシェア全てを集めなければ$ xを復元できない

$ x,$ yのシェアについて以下が成り立つ

$ x + y = \sum_i x_i + \sum_i y_i = \sum_i (x_i + y_i)

各パーティは手元で$ \langle x \rangle + \langle y \rangleを計算することで$ x+yのシェア$ \langle x+y \rangleを得る

$ \alpha a = \alpha \sum_i x_i = \sum_i \alpha x_i ($ \alphaは任意定数 )

各パーティは手元で$ \alpha \langle x \rangleを計算することで$ \alpha xのシェア$ \langle \alpha x \rangleを得る

$ SPDZでは乗算に$ Beaver's ~ Trickを利用

$ \langle x \rangleと$ \langle y \rangleから$ \langle z \rangle = \langle xy \rangleを作りたい

$ c = abなる定数$ a, b, cのシェア$ \langle a \rangle , \langle b \rangle , \langle c \rangle を用意する

$ a, b, cは$ x,$ yに非依存

どのパーティも$ a, b, cの値は知らない

$ P_iは$ x_i - a_iと$ y_i - b_iを計算しブロードキャストする

$ x_i, y_i, a_i, b_iそれぞれの値は送信者である$ P_i以外は誰も分からないので安全

各パーティはブロードキャストされた値を元に手元で$ x-a, y-bを復元できる

$ x-a = \sum_i (x_i - a_i)

$ y-b = \sum_i (y_i - b_i)

$ P_iは$ z_i = c_i + (x-a)b_i + (y-b)a_iとして$ \langle z \rangleを得る

ある一つのパーティが$ x-aと$ y-bの積を自分のシェアに加える

ここでは仮に$ P_1がその役だとする

$ z_1 = c_1 + (x-a)b_1 + (y-b)a_1 + (x-a)(y-b)

$ \sum_i z_i = c + (x-a)b + (y-b)a + (x-a)(y-b) = xy

前処理を行うことで$ SPDZは効率的な乗算を実現

前処理 : 乱数$ a, b, cを生成し, それらのシェアを分配

参考文献

Web

What is SPDZ?

Bristol Cryptography Brog

スライド

Multi Party Computation: From Theory to Practice

Nigel P. Smart

Multi-Party Computation Part 1

Claudio Orlandi

An Introduction to Secure Multi-Party Computation

Giuseppe D'Alconzo