画像の秘密共有化
２００６ MI ０８９ 久留島自翔
指導教員：小藤俊幸
１ はじめに現代の情報社会では様々な情報がディジタル化されていて，コンピュータで処理・保存されている．しかし，それらはコンピュータの故障などの原因から損失するかのうせいがある．そのため USB や CD-ROM などの予備記憶装置にバックアップを保存しておく必要がある．しかし，昨今そのバックアップを紛失したり，パソコンが不正アクセスされたりすることで，情報が漏洩している．問題なのはその中には企業の重要書類や企画のデザイン，役所の住民票などのような個人情報といった見ず知らずの第３者に見られたくない，見られてはいけない情報があるということだ．そうならないために情報を見られないようにパスワードなどのロックをかけたり，暗号化の処理を行っている．しかし，これらは特定の方法をしようすることで解読することができるという欠点がある．そこでできたのがシークレット・シェアリング（Secret sharing）である．シークレット・シェアリングは情報を分けて共同保有することで，情報の漏洩を防ぐ技術である．シークレット・シェアリングは分けた情報の１つが漏洩しても情報を復元できないという特性と，情報が１つくらい欠けても復元が可能であるという特性がある．この論文ではそのシークレット・シェアリングについて論じたい．
２ シークレット・シェアリング
冒頭でも述べたとおり，シークレット・シェアリングは秘密情報を他人には見られないようにする技術の一つである．
この章ではシークレット・シェアリングの基本的な仕組みを理解していきたい[1]．
p を素数とし，s ∈ Fp を秘密にしておきたい数字とする．
クレジットカードの番号やキャッシュカードの暗証番号などをイメージしておけばいいだろう．この番号を何人かで“共同”して保管することを考える．まずs０, s１ ∈ Fp を適当に選んで，Fp 上の２次多項式を作る．さらに，c1, c2, ... をFp の相異なる元として，d1 =f(c1), d2 = f(c2), ...を計算します．得られた対(c1, d1), (c2, d2),... をシェア(share) と呼び，秘密を共有する人たちに一つずつ渡しておく．受け取った人たちは，自分のシェアを他人には知られないように保管する．
※ここで言うシェアは，いわゆるマーケットシェア（市場占有率）のシェアではなく，株式，株券のたぐいを指す．

保持しているシェアを提示しさえすれば，s ∈ Fpを復元することができる．実際，(ci, di), (cj , dj), (ck, dk) を（異なる）３人のシェアとすると，di = f(ci), dj = f(cj), dk = f(ck) から，のようなs0, s1, s に関する連立一次方程式が得られる．左辺の行列はci, cj ,ck が相異なるとき，正則（逆行列をもつこと）となり，s0, s1, s（特にs）が一意に定まる．なお，多項式の次数を大きくすれば，s の復元に必要な「３人」をもっと多くの人数に変えることができる．
※「正則⇔ (行列式) ≠ 0」は一般の体で成り立つ(行列式)≠ 0 であることは，行列式(determinant) を実際に計算してみると分かる．ci → a, cj → b, ck → c とおきかえて，次のように入力してみよう．このような形の行列の行列式は，ファンデルモンド(Vandermonde,1735–1796) の行列式と呼ばれている．
(%i1) A:matrix([1,a,a^2],[1,b,b^2],[1,c,c^2]);(%i2) determinant(A);(%i3) factor(%);
次に実際に数値をあてた例題を Maxima（今回の論文では Maxima-5.27.0 を使用した）を用いて解いてみる．
（例題）p = 257 とし，s = 99 を秘密にしたい数字とする．s0= 239, s1 = 228 に取り，f(x) = 239 + 228x +99x2 とする．
例えば，c1 = 72 とするとき，d1 = f(c1) の値を，次のように計算する．
(%i1) p:257;(%i2) f:239+228*x+99*x^2;(%i3) mod(subst(x=72,f),p);
結果として，d1 = 194となる．同様にc2 = 89, c3 = 56, c4 =240, c5 = 143 に対して，di = f(ci) を計算すると，d2 = 43, d3= 165, d4 = 45, d5 = 9 となるので，シェア(72, 194), (89,43), (56, 165), (240, 45), (143, 9) を一つずつ５人に分配する．
一例として，シェア(89, 43), (56, 165), (143, 9) からs = 99を復元することを考えよう．対応する(2) の方程式をガウスの消去法で解けばよい．特に，s は階段化して得られる最後の式から直ちに求められる．次の計算例では，A0 を(2) の（Maxima流ではない）通常の拡大係数行列としている．
(%i4) modulus:p;(%i5)A0:radcan(matrix([1,89,89^2,43],[1,56,56^2,165],[1,143,143^2,9]));(%i6) A1:radcan(matrix(A0[1],A0[2]-A0[1],A0[3]-A0[1]));(%i7)A2:radcan(matrix(A1[1],A1[2],A1[3]+(54/33)*A1[2]));(%i8) s:mod(radcan(-68/72),p);

図１：Secret Sharing
秘密の共有者が（少なくとも）３人集まって，自分自身が３ 画像のシークレット。シェアリング
前章ではシークレット・シェアリングの基本的なことについて述べたので，この章ではこの論文の題目にもなっている画像のシークレット・シェアリングについて述べたい．
今回は白黒の二値画像（白黒画像のように色が２色しかない画像）をサンプル画像として使用して 2 人にシェアした場合の画像のシークレット・シェアリングをする[2]．
画像のシークレット・シェアリングをする手順としては，まず，1 ピクセルを 4 ピクセル分の正方形に置き換える．次に 2 つの分散画像に分割する．元々が黒だったピクセルの場合は図 2.1 のようにそれぞれ左端と右端を互い違いに黒くして，重ねたときに黒い部分が重ならないようにする．右を黒くするか左を黒くするかはランダムで決める．また元々が白だったピクセルの場合は図 2.2 のようにそれぞれ右端と左端の同じ側を黒くして，2 つを重ねた時に黒い部分が重なるようにする．なお，ここでは見やすくする
ため灰色で表示する．

これを先ほど述べた手順でシークレット・シェアリングをして，2 つに分けると次の図 3.2 と図 3.3 のように分割する
前，どんな画像であったかわからない 2 つの画像が出来上がる．

図 3.2

図 3.3
しかし，実際にこの 2 つの画像を OHP シートのような透明なシートに印刷して，それらを重ね合わせてみると，図3.4 のようになる．

図 2.1 黒の場合
図 3.4
図 3.4 を見てみると，元々は「南山」という文字が書かれていた画像であることがわかる．このようにして画像を見たいときには今のように保持している画像を提示して，重ね合わせることで元々の画像を見ることができるということがわかった．

図 2.2 白の場合（右端を黒くする場合）
このようにして今述べた手順に従って，図 3.1 の画像サンプルを実際にシークレット・シェアリングの処理を行ってみる．

４．おわりに今回の論文で，シークレット・シェアリングによって画像を分けてそれを秘密にすることができた．今回は画像を二つ（二人分）に分けたが，実際に行われているシークレッ
ト・シェアリングの場合は，始めに述べたとおり，画像だけではなく様々な情報があり，共有する人数はもっと多くなるし，情報を暗号化した上でシークレット・シェアリングをする．なので今度はそういった処理も行った上でシークレッ
ト・シェアリングをしたい．
５．参考文献[1]小藤俊幸，情報システム数理実習資料，2011．
[2]S.Cimate,C.-N.Yang(ed.),”Visual Cryptography
and Secret Image Sharing”,CRC Press,Boca
Raton,2012.

図 3.1