[I486S]
暗号プロトコル理論
藤 英一郎 北陸先端科学技術大学院大学 2018年5月1日 藤 英一郎 (JAIST)基本情報
: I486S
暗号プロトコル理論
I
URL:https://www.jaist.ac.jp/~fujisaki/i486S 開催日時 火曜日 (Tuesdays) 5 時限 17:10 – 18:50 予定 4/17, 4/24, 5/1, 5/15, 5/22, 5/29, 6/5, 6/19, 6/26, 7/3, 7/10, 7/17, 7/24, 7/31 教室：知識２棟２階遠隔教育ルーム 教科書：指定なし
参考文献
R. Cramer, I. Damgaard, and J. Nielsen: Secure Multiparty Computation and Secret Sharing, Cambridge University Press (ISBN 9781107043053). R. Cramer, I. Damgaard, J. Nielsen: Multiparty computation, Introduction. Ben-Or, S. Goldwasser and A. Wigderson: Completeness Theorems for Non-Cyptographic Fault-Tolerant Distributed Computation, in STOC88, pp. 1–10.
R. Cramer, I. Damgaard and U. Maurer: General Secure Multi-party Computation from any Linear Secret-Sharing Scheme, in
EUROCRYPT2000, pp 316–334.
R. Cramer, I. Damgaard and Y. Ishai: Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation, in TCC2005, pp 342–362.
A. Yao: Protocols for secure computations, in FOCS82, pp 160–164. Y. Lindell and B. Pinkas: A Proof of Security of Yao’s Protocol for
Two-Party Computation, Journal of Cryptology, volume 22(2), pp.161–188, 2009.
本日の講義の内容
1 Shamir 秘密分散
2 Reed-Solomon 符号
3 Shamir SSの足し算と掛け算
Shamir
秘密分散
(Shamir SS)
Shamir秘密分散SS = (Share, Recon, Γt+1,n)
Share(s):
a0:= s の条件のもと K 係数のランダムな t 次多項式 f (X ) =∑ti =0aiXiを選ぶ。
f (X )←R K [X ] such that deg(f ) = t, and a0= s.
[s] = (f (α1), . . . , f (αn)) を出力する。αi ∈ K は予め定められた互異な る値。 Recon(SQ) (SQ ={f (αi)|i ∈ Q s.t. Q ∈ Γt+1,n}): sを出力。 s =∑ i∈Q λi ,Qf (αi) where λi ,Q = ∏ j∈Q\{i} ( αj αj − αi ) . Reconstruction vector (λ1,Q, . . . , λ#Q,Q)は、SQのみで決定することに注意 （(α1, . . . , αn)はシステムのパラメータで予め決まっているとする）。 藤 英一郎 (JAIST)
Shamir
秘密分散は線型
f , g ∈ K[X ] (deg(f ), deg(g) ≤ t)に対して次のことは明らか。 線型性 [αf (0) + βg (0)] = α[f (0)] + β[g (0)] where α, β∈ K. f (X ) = a0+ a1X + . . . atXt および g (X ) = b0+ b1X + . . . btXt とする。h(X )≜ αf (X ) + βg(X ) と定義すると、deg(h)≤ tで、 [h(0)] = (h(α1), . . . , h(αn)) = (αf (α1) + βg (α1), . . . , αf (αn) + βg (αn)) = α[f (0)] + β[g (0)]
本日の講義の内容
1 Shamir 秘密分散 2 Reed-Solomon 符号 3 Shamir SSの足し算と掛け算 4 付録 藤 英一郎 (JAIST)Reed-Solomon
符号
(n, t + 1)-線型符号とは、n 次元ベクトル空間のt + 1 次元部分空間であ る。K =Fq（元の個数がq個の有限体）とする。α1, . . . , αn∈ K (αi ̸= αj for i ̸= j) とする。 Reed-Solomon (RS) 符号 f ∈ K[X ], deg(f ) ≤ t となる多項式から作られる次の符号語 (f (α1), . . . , f (αn)) の全体からなる集合を、(n, t + 1)-Reed-Solomon 符号と言う。 i.e., CRS ={(f (α1), . . . , f (αn))| f ∈ K[X ] s.t. deg(f ) ≤ t}. (n, t + 1)-RS 符号は(n, t + 1)-線型符号
線型符号
線型符号のこと 線型符号Cは、ベクトル空間の部分ベクトル空間であるので、 c, c′∈ C, a, b ∈ K =⇒ ac + bc′∈ C. つまり、符号語の線形和は符号語。 任意の相異なる符号語c, c′ と（ハミング）重みτ以下の任意の（エラー）ベクト ルe, e′ に対して、必ず c + e̸= c′+ e′ なら、τ個誤り訂正可能(τ -error correcting)という。 線型符号の最小距離dは、非零の最小の符号語のハミング重みに等しい 線型符号誤り訂正可能（最大）数は、τ < d 2 の最大値. v ∈ Knのハミング重み : wH(v )≜ # of {vi ̸= 0 for v = (v1, . . . , vn)}. v とw間のハミング距離: dH(v , w )≜ wH(v− w). 符号の最小距離: 二つの符号間のハミング距離の最小値. d = min{dH(c, c′)| ∀c, c′∈ C s.t. c ̸= c′} 藤 英一郎 (JAIST)RS-
符号
Theorem 1 (n, t + 1)-Reed-Solomon 符号の最小距離はn− t（＝(n, t + 1)-線型符号 の最小距離の上界）。ここから誤り訂正可能最大数はτ < n−t2 なるτの最 大値。 Proof. RS 符号語が f = (f (α1), . . . , f (αn)) であることを頭に入れ、 非零の符号 f∈ CRS ⇐⇒ f (x) = 0 の零点が t 個以下 何故ならば、deg(f )≤ t より t + 1 点以上の零点があると f ≡ 0. よって、 f (x ) = 0 の零点が t 個以下 ⇐⇒ wH(f )≥ n − t これから、最小距離 d = n− t が導かれる。さらに、wH(e) < n− t なる e が、e ̸∈ CRSということは、 ∀c, c′∈ CRS,∀e, e′(w H(e), wH(e′) < n− t) =⇒ c + e̸= c′+ e′.
RS-
符号の復号
符号語f = (f (α1), . . . , f (αn)) where deg(f )≤ t and n ≥ 3t + 1. エラー付きf = (yˆ 1, . . . , yn) = f + e where WH(e)≤ t
Goal: ˆf からf に復号する Welch/Berlekamp Algorithm
Q(X , Y )≜ f0(X )− f1(X )Y
Q(αi, yi) = 0 for i = 1, . . . , n
deg(f0)≤ 2t and deg(f1)≤ t
f1(0) = 1
となるf0(X ), f1(X )を求め、f (X ) = f0f1(X )(X )として出力。
WH(e)≤ tかつ、n≥ 3t + 1ならこのようなf0, f1は存在し、さらに
f (X ) = f0f1(X )(X )を満たす。
RS-
符号の復号（その
1.5
）
f
0, f
1の存在証明
yi = f (αi) + ei で、ei ̸= 0は高々t個なので、f0, f1は次のように存在す る。B ={i | ei ̸= 0}とおく。 定義より、#B≤ t. k(X ) = ∏ i∈B(X − αi) ∏ i∈B(−αi) とおく。 f0(X ) = k(X )f (X ), f1(X ) = k(X ) とおくと、f1(0) = 1, deg(f0)≤ 2t, deg(f1)≤ t. さらに、i = 1, . . . , n に 対して、 Q(αi, yi) = f0(αi)− f1(αi)yi = k(αi) ( f (αi)− yi ) = 0. よって、f0, f1は存在。
RS-
符号の復号（その２）
f0(X ) = a0+ a1X + . . . + a2tX2t f1(X ) = 1 + b1X + . . . + btXt Q(αi, yi) = f0(αi)− f1(αi)yi= 0 for i = 1, . . . , nから、以下の未知変数3t + 1の連立一 次方程式を解く。 0 .. . .. . .. . 0 = 1 α1 · · · α2t1 −y1 −y1α1 · · · −y1αt1
.. . ... ... ... ... ... ... ... ... .. . ... ... ... ... ... ... ... ... .. . ... ... ... ... ... ... ... ... 1 αn · · · α2tn −y1 −ynαn · · · −ynαtn
a0 .. . a2t 1 b1 .. . bt 藤 英一郎 (JAIST)
RS-
符号の復号（その３）
ˆ Q(X ) = Q(X , f (X ))と定義する。すると deg( ˆQ)≤ 2t. WH(e)≤ tより、yi = f (αi)となる点が少なくともn− t個ある。 よって、n− t 個の(αi)で、Q(αˆ i) = 0. n≥ 3t + 1より、deg( ˆQ)≤ 2t < n − t. よって、 deg( ˆQ)≡ 0. よって、 f0(X )− f1(X )f (X )≡ 0. よって、 f (X ) = f0(X ) f1(X ) .
本日の講義の内容
1 Shamir 秘密分散 2 Reed-Solomon 符号 3 Shamir SSの足し算と掛け算 4 付録 藤 英一郎 (JAIST)Shamir SS
の足し算（復習）
[a], [b]: a, b ∈ KがP1, . . . , Pn 間でシェアされた状態 addition [a] + [b] = [a + b] f , g をそれぞれa, bをシェアする時のt次多項式とする。f0 = a, g0 = b で、 f (X ) = f0+ f1X + . . . + ftXt, and g (X ) = g0+ g1X + . . . + gtXt. h(X ) = f (X ) + g (X )と置くと、h(0) = a + bとdeg(h) = tより [a + b] = (h(α1), . . . , h(αn)) h(αi) = f (αi) + g (αi)であるから、各Piがローカルに自分のシェアを足 し算すれば、[a + b]と言う状態になる。
Shamir SS
の掛け算（試み）
[a]t, [b]t: a, b∈ KがP1, . . . , Pn間で(t + 1, n)秘密分散でシェアされた状態 multiplication [a]t· [b]t= [ab]2t ただし、[a]· [b]は、各Pi がローカルに自分のシェアを掛け合わせた状態を意味する。 [a]t は、t + 1個のシェアからaが復元できることを意味する。 f , g をそれぞれa, bをシェアする時のt次多項式とする。f0= a, g0= bで、 f (X ) = f0+ f1X + . . . + ftXt, and g (X ) = g0+ g1X + . . . + gtXt. h(X ) = f (X )g (X )と置くと、h(0) = abとdeg(h) = 2tより [ab]2t = (f (α1)g (α1), . . . , f (αn)g (αn)) よって、P1, . . . , Pn間でabをシェアした状態になるが、2t + 1個のシェアが集まらない とabが復元できない。 藤 英一郎 (JAIST)Shamir SS
の掛け算（アイデア）
multiplication Lagrangeと線型性により [ab] = [h(0)] = [ n ∑ i =1 λi ,nh(αi)] = n ∑ i =1 λi ,n[h(αi)] (λ1,n, . . . , λn,n)は{α1, . . . , αn}のみから決まる。 h(X ) = f (X )g (X )であるから、h(αi) = f (αi)g (αi).よって、[a], [b]の状態から、[ab] を作るには各Piがローカルにf (αi)g (αi)を計算した後、その値を(t + 1, n)-線型秘密分 散で[f (αi)g (αi)]という状態を作り出せば良い。後は線型性から[ab]の状態に持って いく。
Shamir SS
の掛け算（まとめ）
Input: [a], [b]. Output: [ab]. [a], [b]というa, bがそれぞれP1, . . . , , Pn間でシェアされる（初期 状態） 各Piがci = aibi をローカルに計算 各Piがci をP1, . . . , Pn間で線型秘密分散。[c1], . . . , [cn]の状態にな る。Pi は、c1,i, . . . , ci ,i, . . . , cn,i を、[c1], . . . , [cn]の自分のシェアと して持つ。 i = 1, . . . , nに対して、λi ,n= ∏ j̸=i αjα−αi i を計算する。 各Piがdi = ∑ j =1λj ,ncj ,iを計算する。 [ab] = (d1, . . . , dn)なので、[ab]の状態になる。 藤 英一郎 (JAIST)本日の講義の内容
1 Shamir 秘密分散
2 Reed-Solomon 符号
3 Shamir SSの足し算と掛け算
秘密分散
(Secret Sharing)
SS = (Share, Recon, Γt+1,n)とは次のスペックを満たすもの。 Shareは秘密s∈ K（Kは体）を入力に取り、n個のshareからなるベクトル [s]≜ (s1, . . . , sn)を出力する確率的アルゴリズム Share : s∈ K 7→ [s] = (s1, . . . , sn)∈ Kn Γt+1,n≜ {Q ⊂ {1, . . . , n} | #Q ≥ t + 1}（閾値型アクセス構造） Reconは、[s]のt個以上の要素を含む部分集合SQ ={si|i ∈ Q}（Q∈ Γt+1,n）を 入力に取り、秘密sを復元する確定的アルゴリズム 上記SS = (Share, Recon, Γt+1,n)が秘密分散とは、次の条件を満たすものである。(Perfect Reconstructability)全てのs∈ K, [s] ← Share(s), Q ∈ Γt+1,nとなるSQ
に対して、Recon(SQ) = s.
(Perfect Privacy)全てのs∈ K, [s] ← Share(s), T ̸∈ Γt+1,nとなるSTに対して、
H(s) = H(s|ST)。すなわち、確率変数sとSTは独立。
線型秘密分散
(Linear Secret Sharing)
上記SS = (Share, Recon, Γt+1,n)が線型秘密分散とは、次の条件を満たす
ものである。
Linearlity
SSが秘密分散かつ、
(Linearlity) 全てのs, s′, a, b∈ K, [s] ← Share(s), [s′]← Share(s′)に
対して、 [as + bs′] = a[s] + b[s′] が成り立つ。ここで、a[s]≜ (a · s1, . . . , a· sn), [s] + [s′]≜ (s1+ s1′, . . . , sn+ sn′)と定義。 線型であるということは、P1, . . . , Pn間で秘密s, s′をシェア状態[s],[s′]であるとき、各 Pi がローカルに手元でasi+ bsi′を計算して（a, bは既知）新たにシェアされる (as1+ bs1′, . . . , asn+ bsn′)が秘密as + bs′をシェアした状態[a· s + b · s′]になることを意 味する。
