rcIIes

IIIIIIIeaIII I III IIII IIIRIII I I I I I I III

IIIIIIII

III I IIIIIIIIIIIIIh

私の研究

視覚復号型秘密分散法〜人間の 目 を使って計算する暗号〜

渡邊 曜大（わたなべ ようだい）
公立大学法人会津大学
コンピュータサイエンス部門情報基礎論講座
上級准教授

１．はじめに２つの要求を同時にみたす安全な情報の保管法を近年、計算機やネットワークの普及・発展に伴提供するのが、秘密分散法とよばれる暗号技術でい、さまざまな情報も電子化され、各種電子機す。本稿では、これまで学生と共に取り組んでき器を介して手軽に利用できるようになっていまたこの秘密分散法の一風変わった例である視覚復す。一方でこうした情報には、国家・企業の機密号型秘密分散法の研究について説明したいと思い情報からいわゆる個人情報まで安全に保管されるます。

べき秘密情報も含まれます。ここで漠然と「安全に」という言葉を使いましたが、想定される典型

２．秘密分散法

的なリスクとして紛失と漏洩の２つが挙げられま

秘密分散法とは、以下の２つの条件をみたすよす。電子情報は通常、ハードディスクや光学ディうに秘密情報を暗号化して複数の参加者に分配すスク等の記憶装置・媒体に保管されますが、それる暗号技術のことです。

ら装置・媒体の故障や破損等が原因で情報にアク⑴セスできなくなるのが紛失のリスクです。このリスクを減少させるための単純かつ有効な方法は、資格を有する参加者集合（有資格集合）は秘密情報を完全に復元できるが、⑵

資格のない参加者集合（禁止集合）は秘密情秘密情報のコピーを複数用意し、それらを別々に報に関するいかなる部分情報も得ることができできるだけ相関のない記憶装置・媒体に記録するない。

ことです。しかしもちろん、情報のコピーが複数秘密情報が暗号化され、各参加者に分配される情存在することは、意図せず情報が流出したり盗ま報のことを分散情報と呼びます。

れたりしてしまう漏洩のリスクを増大させること

秘密分散法の典型的な例として、（k, n）‑しきいになります。つまるところ、紛失のリスクを減少値型の秘密分散法が挙げられます。ここで、 k, nさせるためにはコピーの数は多いほど良く、漏洩は条件 k ≦ n をみたす自然数です。この秘密分散のリスクを減少させるためにはコピーの数は少な

法では、 n 人の参加者を想定しています。そしいほど良いということになります。この相反するて、この参加者 n 人のうち k 人以上からなる集合

福島の進路 2016. 1137

私の研究

分散音声１

分散画像１

分散音声１+２

分散画像１+２

分散画像２

分散音声２

図１ （2, 2）‑しきい値型視覚復号型秘密分散法

図２ （2, 2）‑しきい値型聴覚復号型秘密分散法

が有資格集合となり、k−１人以下からなる集合

号は参加者が持ち寄った透明なシートに印刷されが禁止集合となります。すなわち、集まった参加た分散画像を重ね合わせ、現れた画像を人間の目者が k 人以上のときは秘密情報を復元できますが、で判別することにより行われます（図１）。一方、k−１人以下のときは秘密情報に関するいかなる聴覚復号型秘密分散法では、分散情報は音声にな部分情報も漏れません。したがって、n 人の参加ります。復号は参加者が持ち寄った分散音声を同者のうち n−k 人までの分散情報が紛失しても秘時再生し、合成された音声を人間の耳で判別する密情報の復元が可能であり、また、k−１人までことにより行われます（図２）。の分散情報が漏洩しても秘密情報に関するいかなる部分情報も漏れません。（k, n）しきい値型秘密３．複数画像を暗号化する視覚復号型秘密分分散法の具体的な構成法としては、RSA 暗号の散法発明者の一人でもあるアディ・シャミアによる有複数の秘密画像を暗号化することのできる視覚限体上の k−１次多項式を用いる方式が有名です。

復号型秘密分散法について紹介する前に、まず視以上、安全な情報の保管法という観点から秘密分

覚復号型秘密分散法の暗号化の仕組みについて散法について説明してきましたが、この情報の保説明します。そのために、最も簡単な例として、管というのはいわば副産物で、その直接の目的は、（2, 2）しきい値型の視覚復号型秘密分散法につい重要な情報に対して誰がアクセスできるのかを定て考えましょう。この秘密分散法では、秘密画めるアクセス制御の実現にあることを述べておき像は２つの分散画像に暗号化されます（図１左）。

ます。

各分散画像は秘密画像とは相関のない

秘密分散法には、人間の目あるいは耳を使って像ノイズ画と統計的に区別がつかず、したがって秘密画復号（秘密情報の復元）が可能な一風変わったも像に関する一切の情報を漏らしません。一方、透のも在します。前者を視覚復号型秘密分散法、後明なシートに印刷されたこれらの分散画像を重ね者を聴覚復号型秘密分散法とよびます。視覚復号合わせることによって、秘密画像が復元されます

型秘密分散法では、秘密情報（白黒画像）を暗号（図１右）。この２つの分散画像の生成法として、化して生成された分散情報（分散画像）が透明な秘密画像の１画素を分散画像の２画素に暗号化すシートに印刷され、各参加者に分配されます。復る最も単純な方法を取り上げることにします。こ38

福島の進路 2016. 11

私の研究
秘密画像

パターン１

パターン２

分散画像１

分散画像２

分散情報 a

分散情報 b

分散情報 c

分散情報 a+b

分散情報 a+c

分散情報 b+c

分散画像１

分散画像２

図３

視覚復号型秘密分散法の暗号化の方法では、秘密画素が白の場合は図３上段のパターン１もしくはパターン２が、黒の場合は同図下段のパターン１もしくはパターン２がランダム分散情報 a+b+c

図４

参加者が対等でないアクセス構造を実現する
視覚復号型秘密分散法に選ばれ、該当する分散画素が分散画像の対応する位置に配置されます。図から分かるように、秘から成る集合であり、その禁止集合は参加者１人

密画素が白の場合（上段）、分散画素を重ね合わ以下の組み合わせ
, a｝
, b｝
, c｝
｛｛｛

せるとパターン1、２のどちらの場合でも白と黒がそれぞれ１つずつで黒の割合が0.5となりますが、から成る集合（ただし、秘密画素が黒の場合（下段）、重ね合わせると黒空集合）となります。一方、参加者が対等でないが２つで黒の割合が１となります。この黒の割合

簡単な例として、有資格集合がの差によって、分散画像を重ね合わせたときに秘密画像が復元されて見えることになります。

は要素を何も持たない, a, c ｝, a, b, c ｝｛ a, b ｝｛｛から成り、禁止集合がこれまで扱ってきたしきい値型の秘密分散法で, a｝
, b｝
, c｝
, b, c ｝｛｛｛｛

は、参加者は皆対等でした。参加者が必ずしも対から成るアクセス構造を考えることができます。

等とは限らない秘密分散法を扱うためには、アク実際この場合、参加者 a は他の参加者と組むことセス構造という概念を導入すると便利です。ここによって秘密情報を復元できますが、参加者 b,cでアクセス構造とは、⑴ 秘密情報を復元できるのみでは秘密情報を復元できず、参加者 a が参加参加者の組み合わせの集合、および、⑵ 秘密情者 b, c に比べて報に関するいかなる情報も得ることができない参ることが分かります。このアクセス構造を実現す

加者の組み合わせの集合、により定められます。

る視覚復号型秘密分散法は、（2, 2）‑しきい値型の前者の集合を有資格集合、後者を禁止集合と呼び分散情報１を参加者 a に分配し、分散情報２を２ます。例えば、（2, 3）‑しきい値型の秘密分散法のつ用意してそれぞれを参加者 b, c に分配すること

場合、３人の参加者を a、b、c とあらわせば、そによって簡単に構成することができます（図４）。の有資格集合は参加者２人以上の組み合わせ,｛ a, c ｝
, b, c ｝, a, b, c ｝｛ a, b ｝｛｛

偉いアクセス構造になってい最後に、最も一般的なアクセス構造、すなわち、複数の秘密情報をもつアクセス構造を実現する視

福島の進路 2016. 1139

私の研究

分散情報Ｒ

分散情報 R+G

分散情報Ｇ

分散情報 R+B＋＝＋＝分散情報Ｂ

分散情報 G+B

図６

セキュリティ分野以外への応用例：楽しく漢字を学ぶ

視覚復号型秘密分散法の例です。上段は、光の三分散情報 R+G+B

図５

複数の秘密画像を暗号化する視覚復号型
秘密分散法

原色である赤（Red）、緑（Green）、青（Blue）の頭文字を表し、中段・下段は、それらの加法混色
Red + Green = Yellow,
Red + Blue = Magenta,

覚復号型秘密分散法について考えましょう。ただGreen + Blue =し、秘密画像の数だけ各参加者の分散画像を用意

Red + Green + Blue = White,

すればこれを実現できるのは自明なので、各参加により生成された色の頭文字を表しています。

Cyan,者に配布される分散画像は１つのみという制限を課すことにします。つまり同じ分散画像の組み合

４．おわりにわせを変えて重ね合わせるだけで異なる秘密画像

これまで強調しませんでしたが、視覚復号型秘が復元されるようにしたいわけです。実は、この密分散法は、あくまで、数学的にその安全性が証ような最も一般的なアクセス構造を実現する視覚明された暗号技術です。しかし同時に、大学の復号型秘密分散法を構成することは可能で、実際オープンキャンパスや展示会等で年代を問わず来私たちは暗号化関数のみたすべき十分条件を導出場者の方に興味を持っていただけることも多く、することができました。具体的には、各秘密画像

図６のように、セキュリティ分野以外へのに対してそれに対応する暗号化関数が存在して、なその各暗号化関数が、（ i ）対応する秘密画像のアます。

意外応用も考えられるのではないかと期待していクセス構造を実現する視覚復号型秘密分散法を与え、（ii）他の秘密画像に対応する分散情報の復号に干渉しない、という２つの条件をみたすとき、各暗号化関数により出力された分散画素を連結し、それをランダム置換することによって暗号化関数が構成できることを示しました。
図５は、３人から成る参加者集合の空集合を除くすべての部分集合に秘密画像が付与されている40

福島の進路 2016. 11＜プロフィール＞
東京大学大学院理学系研究科修了、博士（理学）。理化学研究所基礎科学特別研究員、会津大学准教授などを経て2016年４月より現職。計算機科学の基礎に関わる分野の研究に従事。日本応用数理学会第３回若手優秀講演賞受賞。