秘密分散法 (Secret Sharing Scheme, SSS) は，秘密情報Sをｎ個の分散情報に分散符号化し，秘密を復号できる集合（有資格集合，qualified set）に属する分散情報が全て集まるとSが復号できるが，秘密情報を復号できない集合（禁止集合，forbidden set）に属する分散情報が集まっても秘密情報は全く洩れない符号化システムである．有資格集合の族と禁止集合の族の対をアクセス構造と呼ぶ．例えば，SSSとして最初に提案された(k,n)しきい値法では， n個の分散情報のうち任意のk個以上から秘密情報を復号できるが，任意のk−1個以下の分散情報からはSに関する情報は情報量的に1ビットも漏洩しないように設計されている．このため，(k,n)しきい値法は分散情報のn−k個以下の破壊およびk−1個以下の盗難の両方に対して安全性を保つことができ，データの保存や通信に有効な符号化法である．さらに，SSSはマルチパーティプロトコルの構成などにおいても重要な役割を果たすことが知られており，情報セキュリティにおける重要な基本技術のひとつとなっている．

一般のSSSでは秘密情報は計算機上で復号される．これに対して，視覚復号型秘密分散法(Visual SSS, VSSS) では秘密情報が画像であり，それを分散画像に分散符号化する．復号は分散画像を重ね合わせるだけで行うことができ，復号に計算機を要しないという特徴をもつ．そのため，VSSSは災害時などでも使用可能な暗号として知られており，また理論的にも興味深い面を有している．本論文では，SSSおよびVSSSの符号化効率や安全性を議論し，新しい構成法を提案する．論文は2部から成り，第1部ではSSSについて，第2部ではVSSSについて扱う．

第1部では始めに，ランプ型SSSの符号化効率について議論する．ランプ型SSSとは有資格集合，禁止集合以外に秘密情報を部分的に漏洩するような集合を許すことで，符号化レートを従来のSSS（ランプ型と区別し，完全SSSと呼ぶ）より小さくし，符号化効率を上げる方式である．また，完全SSSは，部分的に漏洩する集合が存在しないランプ型SSSと考えることができるため，ランプ型SSSの特殊な場合と考えることもできる．本論文では，ランプ型SSSの符号化レートの下限を導出するために，分散情報をsuper-additive, additive, sub-additiveと呼ばれる3種類に分類する．完全SSSにおいてはすべての分散情報がsuper-additive であることが暗黙のうちに仮定されており，この分類はランプ型SSSにおいて初めて必要となる．上記の分類に従うと，sub-additiveな分散情報の符号化レートの下限は他の2種類の分散情報より明らかに大きくなることが示される．また，super-additiveまたはadditiveな分散情報に対し，符号化レートの下限を導出する．

完全SSSでは，SSSはその符号化レートからideal, non-idealの2種類に分類され，それぞれのSSSの特徴が考察されてきた．これに対して本論文ではideal SSSの拡張としてwell-realizedランプ型SSSを新たに定義し，どのようなアクセス構造をもつランプ型SSSがwell-realizedとなり得ないかを考察する．これらの考察は完全SSSにおける，non-ideal SSSの特徴づけの拡張に相当し，ランプ型SSSの符号化効率の評価に関する従来研究のほとんどの結果を特殊な場合として含んでいる．

次にSSSの符号化手法を提案する．従来，(k,n)しきい値SSSは任意のk, nに対し効率よく構成できることが知られている．しかし，一般アクセス構造に対するSSS符号化法は非常に符号化効率の悪いものしか知られていない．例えば，伊藤らによるcumulative mapは一般アクセス構造をもつSSSを構成する簡単な方法であるが，アクセス構造が(k,n)しきい値法に近いと符号化効率が悪くなる．そこで本論文では「複数割り当て法」と呼ばれる一般アクセス構造をもつSSS構成法について考察する．複数割り当て法は，(k,n) しきい値法の分散情報を複数の参加者に割り当てることで，一般アクセス構造をもつSSSを構成する手法の総称であり，cumulative mapは複数割り当て法の一つの実現方法と考えることが出来るが，最適な符号化レートを達成する複数割り当て法の構成法は知られていない．本論文では，整数計画法を用いて最適な複数割り当て法を設計する方法を提案し， cumulative mapによる構成法と比較して符号化レートを大きく改善できることを示す．また，提案手法は容易に実装でき，従来は構成法がほとんど研究されていなかった，ランプ型SSSや不完全なアクセス構造をもつSSSなどの，拡張されたSSSを構成する際にも有効であることを示す．

第2部では，VSSSの構成法や安全性について議論する．まず，古賀らによって提案されたVSSSの代数的構成法を紹介する．この代数的構成法は，カラー画像に対するVSSSに関して極めて効率よく，簡便な構成法を与えるものであったが，白黒画像に対して適用できないという問題点があった．この問題点は桑門らによって解決されたが，彼らはその構成法しか与えておらず，この構成法の効率に関しては言及していない．そこで，本論文ではVSSSの代数的構成法が，白黒濃淡画像を秘密画像とする(n,n)しきい値法のVSSSに対して最適な解を与えることを証明し，実際に最適な符号化手法を示す．この手法により，(n,n)しきい値法の濃淡画像VSSSは極めて簡単に最適なものが構成できる．

次に，複数の画像を秘密画像とするVSSSに関して考察する．従来の複数画像を符号化可能なVSSSは白黒2値画像に対するものしか知られておらず，さらにそのうちいくつかのVSSSの定義では，復号された秘密画像が他の秘密画像に関する情報を洩らしてしまうような場合があった．そこで本論文では，一般アクセス構造に対して画像を複数隠すことのできるVSSSに対して，復号された画像が他の画像に関する情報を全く洩らさないように厳密な定義を与え，そのような定義を満足するVSSSの構成法を与える．このVSSSの定義はカラー濃淡画像を扱うことができ，従来のほとんどのVSSSの定義を特殊な場合として含んでいる．以上のように，本論文ではVSSSの定義，構成法を広範な範囲で与えることに成功している．

本論文は，「General Construction Methods of Secret Sharing Schemes and Visual Secret Sharing Schemes（秘密分散法および視覚復号型秘密分散法の一般的構成法）」と題し，9章と付録から構成されている．暗号技術は情報化社会を支える不可欠な技術であるが，その中で秘密分散法は情報の記録や通信において，破壊および漏洩の両方の脅威に対して安全な符号化法であり，情報セキュリティ技術の重要な研究テーマの一つになっている．本論文では，Part Iで通常の秘密分散法(Secret Sharing Scheme, SSS)に対して，(1)SSSの符号化レートの理論的評価 (2)整数計画法に基づく一般アクセス構造の最適な実現法を取り扱っている．また，Part IIでは，視覚復号型秘密分散法(Visual Secret Sharing Scheme, VSSS)に対して，(3)濃淡画像に対するVSSSの構成法および最適性の評価 (4)複数画像に対するVSSS符号の構成法を取り扱っており，これらに対して新しい知見を与えている．

第1章「Overview of the Thesis」では，SSS全般に対する研究の背景と目的を述べ，従来研究に対する本論文の位置付けを与えている．また，本論文の構成を示している．

第2章「Introduction to Secret Sharing Schemes」では，通常のSSSに関する研究動向を詳細に紹介すると共に，Part Iに対する研究の位置付けを明らかにしている．また，しきい値型SSS，一般アクセス構造，完全SSS，ランプ型SSSなどのSSSに関する基本的な用語の定義を与えている．

第3章は，「Evaluations of Coding Rates in Secret Sharing Schemes」と題し，ランプ型SSSに対する符号化レートを理論的に評価している．分散情報を「優加法的，加法的，劣加法的」の3種類に分類することにより，従来知られているものよりもタイトな符号化レートの下界を，分かりやすい手法で導出している．

第4章は「Constructions of Secret Sharing Schemes Based on Integer Programming」と題し，しきい値型の秘密分散法を用いて一般アクセス構造を効率よく実現する手法を与えている．従来知られていたcumulative map法に比べ，本手法では，整数計画法を用いて最適な多重割り当てを行っているため，従来手法よりかなり効率がよい特長がある．また，提案手法は，ランプ型SSSやアクセス構造が一部未定である不完備なSSSに対しても適用でき，今まで効率よく構成することが困難であった一般アクセス構造を容易に実現できるようにしている．

第5章「Conclusions of Part I」では，Part Iの成果をまとめると共に，SSSに関する今後の研究課題を示している．

第6章「Introduction to Visual Secret Sharing Schemes」では，VSSSに関する詳細な研究動向を紹介すると共に，Part IIで取り扱うVSSSの研究の位置付けを明らかにしている．また， VSSSのシステマティックな構成法である「代数的構成法」を詳細に紹介している．

第7章は「Visual Secret Sharing Schemes for Gray-Scale Images」と題し，濃淡画像に対する代数的構成法を与えると共に，代数的構成法で実現可能な最小の画素拡大率などを導出している．さらに，(n,n)しきい値型の場合，任意のVSSSが代数的構成法で実現可能なことを証明することにより，提案手法を用いれば全ての構成法の中で最適なVSSSを実現できることを示している．

第8章は「Visual Secret Sharing Schemes for Plural Secret Images」と題し，複数の秘密画像を一度に秘密分散する場合を取り扱っている．複数画像を符号化可能な従来のVSSSは，白黒2値画像に対するものしか知られておらず，さらにその幾つかの方式では，復号された秘密画像が他の秘密画像に関する情報を洩らしてしまう欠点があった．これに対して，本論文では，複数の秘密画像を持つVSSSに対して，復号された画像が他の画像に関する情報を全く洩らさないような厳密な定義を与え，その定義を満たすVSSSの構成法を与えている．このVSSSは，白黒画像だけでなく，カラーや濃淡画像も扱うことができ，また，しきい値型だけでなく一般アクセス構造も実現可能である．

第9章「Conclusion of Part II」では，VSSSに関するPart IIの成果をまとめると共に，今後の研究課題を示している．また，付録では，本論文で与えた構成法により作成したVSSSの具体例を，白黒画像，濃淡画像，カラー画像，複数の画像などに対して掲載している．

以上を要するに，本論文は，情報理論および数理工学的手法を用いることにより，理論的に安全性が保証され，かつ効率のよい汎用的なSSSおよびVSSSの構成法を与えており，その成果は，SSSやVSSSの今後の研究や応用において重要な指針を与えている．よって，本論文は，暗号理論の研究に大きく貢献するとともに，数理情報学の進歩に対して寄与するところが大であり，博士（情報理工学）の学位請求論文として合格と認められる．