(57)【要約】【課題】秘密分散法における分散情報の最適な割り当ての決定を行う。【解決手段】秘密分散法の複数割り当て法において、与えられた一般アクセス構造に対する最適な複数割り当て写像を整数計画法を用いて求めることにより、従来法に比べ小さい符号化レートでの一般アクセス構造を実現する。【選択図】    図１
2004336577.tif 000002
【特許請求の範囲】
【請求項１】
分散情報を配布するディーラ端末が、その分散情報を秘密情報から生成し、各ユーザー端末に割り当て、秘密情報の復元の際には管理端末がユーザー端末から分散情報を収集して秘密情報を復元する秘密分散管理システムにおいて、任意に与えられたアクセス構造を実現するために各ユーザー端末にしきい値秘密分散法の分散情報を複数割り当てる最適な写像を、整数計画法により求めることを特徴とした最適割り当て決定方法。
【請求項２】
2004336577.tif 000106
【請求項３】
請求項１における秘密分散法の最適割り当て決定方法により、アクセス構造が不完全にしか与えられていない場合でも最適な割り当て決定を行うことを特徴とした最適割り当て決定方法。
【請求項４】
請求項１における秘密分散法の最適割り当て決定方法により、ランプ型秘密分散法の任意に与えられたアクセス構造に対しても最適な割り当て決定を行う方法。
【請求項５】
請求項１の秘密分散法の最適割り当て決定方法を実行するコンピュータプログラム。
【請求項６】
請求項２の秘密分散法のアクセス構造更新方法を実行するコンピュータプログラム。
【請求項７】
請求項３の秘密分散法の最適割り当て決定方法を実行するコンピュータプログラム。
【請求項８】
請求項４の秘密分散法の最適割り当て決定方法を実行するコンピュータプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、秘密情報を複数の装置に分散して管理する秘密分散システム及びプログラムに関する。
【０００２】
【従来の技術】
従来、暗号に使用する鍵など重要度の高い秘密情報の管理法として、情報を複数の分散情報に分けて管理するという秘密分散管理方式が知られている。この秘密分散管理方式として（ｋ，  ｎ）しきい値秘密分散法やそれを一般化した一般アクセス構造をもつ秘密分散法がある。以下ではまず（ｋ，  ｎ）しきい値秘密分散法について説明し、次に一般アクセス構造をもつ秘密分散法の場合について記述する。
【０００３】
2004336577.tif 000003
【０００４】
2004336577.tif 000004
2004336577.tif 000005
【０００５】
2004336577.tif 000006
【０００６】
2004336577.tif 000007
【０００７】
2004336577.tif 000008
【０００８】
2004336577.tif 000009
【０００９】
2004336577.tif 000010
2004336577.tif 000011
【００１０】
2004336577.tif 000012
【００１１】
2004336577.tif 000013
【００１２】
既存の手法としては、ｍｏｎｏｔｏｎｅ  ｃｉｒｃｕｉｔ  ｃｏｎｓｔｒｕｃｔｉｏｎ  や、その拡張であるｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｃｏｎｓｔｒｕｃｔｉｏｎ  、他にｃｕｍｕｌａｔｉｖｅ  ｍａｐ  などが知られている。ｍｏｎｏｔｏｎｅ  ｃｉｒｃｕｉｔ  ｃｏｎｓｔｒｕｃｔｉｏｎ  は任意に与えられたアクセス構造を実現するために、複数の（ｍ，ｍ）しきい値秘密分散法の分散情報を組み合わせて符号化する手法であるが、符号化レートが悪い。
【００１３】
一方、符号レートを小さくするためにｍｏｎｏｔｏｎｅ  ｃｉｒｃｕｉｔ  ｃｏｎｓｔｒｕｃｔｉｏｎ  を拡張したもので、符号化手法が既知のいくつかの秘密分散法を組み合わせて新しい秘密分散法を構成する手法であるｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｃｏｎｓｔｒｕｃｔｉｏｎ  が提案されており、いくつかのアクセス構造に対して最適な符号化手法を与えることが知られているが、任意に与えられたアクセス構造に対して自動的な符号化を行う事が出来ない。
【００１４】
別のアプローチとして、ディーラ端末が１つのユーザー端末に複数の分散情報を配布することで秘密分散法を構成する複数割り当て法は、単純な構成法で一般のアクセス構造をもつ秘密分散法が容易に構成できる。以下では、複数割り当て法について記述する。
【００１５】
2004336577.tif 000014
【００１６】
2004336577.tif 000015
【００１７】
2004336577.tif 000016
【００１８】
この複数割り当て法によるアクセス構造の実現法の一つであるｃｕｍｕｌａｔｉｖｅ  ｍａｐが、「伊藤，斎藤，西関，  ”一般的なアクセス構造を実現する秘密共有法，”電子情報通信学会論文誌，  ｖｏｌ．  Ｊ７１−Ａ，  ｎｏ．  ８，  ｐｐ．  １５９２−１５９８，  １９８８．」（以下、文献１  と呼ぶ）に述べられている。
【００１９】
2004336577.tif 000017
【００２０】
2004336577.tif 000018
【００２１】
2004336577.tif 000019
2004336577.tif 000020
【００２２】
2004336577.tif 000021
【００２３】
2004336577.tif 000022
【００２４】
2004336577.tif 000023
【００２５】
2004336577.tif 000024
2004336577.tif 000025
【００２６】
2004336577.tif 000026
【００２７】
2004336577.tif 000027
【００２８】
2004336577.tif 000028
【００２９】
2004336577.tif 000029
【００３０】
2004336577.tif 000030
2004336577.tif 000031
【００３１】
2004336577.tif 000032
【００３２】
ここまで論じて来た秘密分散法は有資格集合族と禁止集合族に対する秘密分散法であったが、秘密情報を部分的に漏らす集合族を定義することで符号化レートをより小さくする手法が「山本，  ”（ｋ；  Ｌ；  ｎ）しきい値秘密分散システム，”電子通信学会論文誌，ｖｏｌ．  Ｊ６８−Ａ，  ｎｏ．  ９，  ｐｐ．  ９４５−９５２，  １９８５．」（以下、文献２  と呼ぶ）及び「Ｇ．  Ｒ．  Ｂｌａｋｌｅｙ  ａｎｄ  Ｃ．  Ｍｅａｄｏｗｓ，  “Ｓｅｃｕｒｉｔｙ  ｏｆ  ｒａｍｐ  ｓｃｈｅｍｅｓ，”  ｉｎ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ’８４，ＬＮＣＳ  １９６，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ｐｐ．  ２４２−２６９，  １９８５．」で提案されており、ランプ型秘密分散法と呼ばれる。
【００３３】
ランプ型秘密分散法への複数割り当て写像の適用を考えると、ｃｕｍｕｌａｔｉｖｅ  ｍａｐは完全な秘密分散法に対する構成法であり、ランプ型への適用は考えられていない。
【００３４】
2004336577.tif 000033
【００３５】
2004336577.tif 000034
2004336577.tif 000035
【００３６】
2004336577.tif 000036
【００３７】
2004336577.tif 000037
【００３８】
2004336577.tif 000038
【００３９】
2004336577.tif 000039
【００４０】
2004336577.tif 000040
【００４１】
2004336577.tif 000041
【００４２】
2004336577.tif 000042
【００４３】
2004336577.tif 000043
【００４４】
2004336577.tif 000044
【００４５】
2004336577.tif 000045
【００４６】
2004336577.tif 000046
【００４７】
一般のアクセス構造に対するランプ型秘密分散法の構成方法は文献３以外には「Ｋ．  Ｓｒｉｎａｔｈａｎ，  Ｎ．  Ｔ．  Ｒａｊａｎ，  ａｎｄ  Ｃ．  Ｐ．  Ｒａｎｇａｎ，  “Ｎｏｎ−ｐｅｒｆｅｃｔ  ｓｅｃｒｅｔ  ｓｈａｒｉｎｇ  ｏｖｅｒ  ｇｅｎｅｒａｌ  ａｃｃｅｓｓ  ｓｔｒｕｃｔｕｒｅｓ，”  ｉｎ  Ｐｒｏｇｒｅｓｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＩＮＤＯＣＲＹＰＴ’０２，  ＬＮＣＳ  ２５５１，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ｐｐ．  ４０９−４２１，  ２００２．」（以下、文献４と呼ぶ）しか知られていない。文献４の方法は線型演算による構成法で、非常に複雑である。
【００４８】
【発明が解決しようとする課題】
任意に与えられたアクセス構造の構成法として、さまざまな手法が提案されているが、それぞれ、（１）符号化効率が悪い。（２）自動的な符号化が出来ない。といった欠点をもつ。
【００４９】
2004336577.tif 000047
【００５０】
（４）全ての部分集合に対して、アクセス構造が決定されていなければならない。
【００５１】
2004336577.tif 000048
【００５２】
【課題を解決するための手段】
前述の課題を解決するために、本発明は次の手段を提供する。
【００５３】
（１）分散情報を配布するディーラ端末が、その分散情報を秘密情報から生成し、各ユーザー端末に割り当て、秘密情報の復元の際には管理端末がユーザー端末から分散情報を収集して秘密情報を復元する秘密分散管理システムにおいて、任意に与えられたアクセス構造を実現するために各ユーザー端末にしきい値秘密分散法の分散情報を複数割り当てる最適な写像を、整数計画法により求めることを特徴とした最適割り当て決定方法。
【００５４】
2004336577.tif 000049
【００５５】
（３）上記（１）における秘密分散法の最適割り当て決定方法により、アクセス構造が不完全にしか与えられていない場合でも最適な割り当て決定を行うことを特徴とし
た最適割り当て決定方法。
【００５６】
（４）上記（１）における秘密分散法の最適割り当て決定方法により、ランプ型秘密分散法の任意に与えられたアクセス構造に対しても最適な割り当て決定を行う方法。
【００５７】
（５）上記（１）の秘密分散法の最適割り当て決定方法を実行するコンピュータプログラム。
【００５８】
（６）上記（２）の秘密分散法のアクセス構造更新方法を実行するコンピュータプログラム。
【００５９】
（７）上記（３）の秘密分散法の最適割り当て決定方法を実行するコンピュータプログラム。
【００６０】
（８）上記（４）の秘密分散法の最適割り当て決定方法を実行するコンピュータプログラム。
【００６１】
【発明の実施の形態】
2004336577.tif 000050
【００６２】
2004336577.tif 000051
【００６３】
2004336577.tif 000052
【００６４】
2004336577.tif 000053
【００６５】
2004336577.tif 000054
【００６６】
2004336577.tif 000055
【００６７】
2004336577.tif 000056
【００６８】
2004336577.tif 000057
【００６９】
2004336577.tif 000058
【００７０】
2004336577.tif 000059
【００７１】
2004336577.tif 000060
【００７２】
2004336577.tif 000061
【００７３】
2004336577.tif 000062
【００７４】
2004336577.tif 000063
2004336577.tif 000064
【００７５】
2004336577.tif 000065
【００７６】
2004336577.tif 000066
【００７７】
2004336577.tif 000067
2004336577.tif 000068
【００７８】
2004336577.tif 000069
【００７９】
2004336577.tif 000070
【００８０】
2004336577.tif 000071
【００８１】
2004336577.tif 000072
【００８２】
2004336577.tif 000073
2004336577.tif 000074
【００８３】
2004336577.tif 000075
【００８４】
2004336577.tif 000076
【００８５】
2004336577.tif 000077
【００８６】
2004336577.tif 000078
【００８７】
2004336577.tif 000079
【００８８】
2004336577.tif 000080
【００８９】
2004336577.tif 000081
【００９０】
さらに、アクセス構造がグラフで書き表される秘密分散法が理想的であるための必要十分条件は、アクセス構造が式（３３）でｔ  ＝  ２  と書ける（つまりアクセス構造が完全ｔ  部グラフで書ける）ことであることが「Ｃ．  Ｂｌｕｎｄｏ，  Ａ．  Ｄ．  Ｓａｎｔｉｓ，  Ｄ．  Ｒ．  Ｓｔｉｏｎｓｏｎ，  ａｎｄ  Ｕ．  Ｖａｃｃａｒｏ，  “Ｇｒａｐｈ  ｄｅｃｏｍｐｏｓｉｔｉｏｎｓ  ａｎｄ  ｓｅｃｒｅｔ  ｓｈａｒｉｎｇ  ｓｃｈｅｍｅｓ，”  Ｊ．  ｏｆ  ｃｒｙｐｔｏｌｏｇｙ，ｖｏｌ．  ８，  ｐｐ．  ３９−６４，１９９５．」で知られている。
【００９１】
2004336577.tif 000082
【００９２】
2004336577.tif 000083
【００９３】
2004336577.tif 000084
2004336577.tif 000085
【００９４】
2004336577.tif 000086
【００９５】
2004336577.tif 000087
【００９６】
このように整数計画法を用いれば、式（９）が満たされていない場合でも新しいアクセス構造に更新できる。
【００９７】
2004336577.tif 000088
【００９８】
2004336577.tif 000089
2004336577.tif 000090
【００９９】
2004336577.tif 000091
【０１００】
2004336577.tif 000092
【０１０１】
次に、００５０段落の課題について、アクセス構造が十分に与えられなかった場合でも最適な複数割り当て写像を構成する方法について述べる。
【０１０２】
2004336577.tif 000093
【０１０３】
このようにして得られた複数割り当て写像が式（１０）を満たす中で最も小さい符号化レートを与えることは明らかである。
【０１０４】
2004336577.tif 000094
【０１０５】
2004336577.tif 000095
【０１０６】
2004336577.tif 000096
【０１０７】
2004336577.tif 000097
【０１０８】
2004336577.tif 000098
【０１０９】
2004336577.tif 000099
【０１１０】
2004336577.tif 000100
【０１１１】
2004336577.tif 000101
2004336577.tif 000102
【０１１２】
2004336577.tif 000103
【０１１３】
2004336577.tif 000104
【０１１４】
【発明の効果】
以上から、本発明の採用により、複数割り当て写像の構成に整数計画法を用いると、従来知られていたｃｕｍｕｌａｔｉｖｅ  ｍａｐ  および改良ｃｕｍｕｌａｔｉｖｅ  ｍａｐ  より小さい符号化レートで秘密分散法が実現できる。
【０１１５】
さらに既に知られているｃｕｍｕｌａｔｉｖｅ  ｍａｐ  のいくつかの拡張が、本発明方式でも可能であり、ランプ型秘密分散法における複数割り当て写像への適用も可能である。
【図面の簡単な説明】
【図１】2004336577.tif 000105
【図１】
2004336577.tif 000107