(57)【特許請求の範囲】
【請求項１】
ｋｂｉｔ（ｋは任意の自然数）の素数位数の巡回群であるＧ１、Ｇ２、ＧＴと、Ｇ１、Ｇ２の生成元であるｇ１、ｇ２と、ＧＴの生成元であるｇＴ＝ｅ（ｇ１，ｇ２）と、非対称ペアリングｅ：Ｇ１×Ｇ２→ＧＴと、ハッシュ関数Ｈ：｛０，１｝＊→｛０，１｝ｋ、Ｈ１：｛０，１｝＊→Ｇ１、Ｈ２：｛０，１｝＊→Ｇ２と、任意に選択されたマスタ秘密鍵
【数４８】
0005651611.tif 000049
から生成された、第１のマスタ公開鍵
【数４９】
0005651611.tif 000050
と、第２のマスタ公開鍵
【数５０】
0005651611.tif 000051
とを公開パラメータとして用い、
ｉ＝１，…，ｍであるｍ個の多項式群
【数５１】
0005651611.tif 000052
であって、
【数５２】
0005651611.tif 000053
を充たす多項式群の係数を用いる鍵交換装置であって、
当該鍵交換装置の識別子である識別子ＩＤＡ（当該鍵交換装置と鍵交換を行う相手側である鍵交換装置の識別子をＩＤＢとする）を鍵生成局に送信する識別子送信部と、
【数５３】
0005651611.tif 000054
として生成された第１の秘密鍵ＤＡ，１と、
【数５４】
0005651611.tif 000055
として生成された第２の秘密鍵ＤＡ，２とを鍵生成局から受信する秘密鍵受信部と、
短期秘密鍵
【数５５】
0005651611.tif 000056
をランダムに選択する短期秘密鍵生成部と、
前記生成された短期秘密鍵ｙＡを用いて、第１の短期公開鍵
【数５６】
0005651611.tif 000057
と、第２の短期公開鍵
【数５７】
0005651611.tif 000058
を計算する短期公開鍵生成部と、
前記識別子ＩＤＡ、前記識別子ＩＤＢ、前記第１の短期公開鍵ＹＡ，１、前記第２の短期公開鍵ＹＡ，２を相手側鍵交換装置に送信し、相手側鍵交換装置から前記識別子ＩＤＡ、前記識別子ＩＤＢ、前記相手側鍵交換装置が生成した第１の短期公開鍵ＹＢ，１、第２の短期公開鍵ＹＢ，２を受信する鍵交換部と、
共有値
【数５８】
0005651611.tif 000059
を計算し、共有鍵
【数５９】
0005651611.tif 000060
を計算する共有鍵生成部と、
を備えることを特徴とする鍵交換装置。
【請求項２】
請求項１に記載の鍵交換装置であって、
前記第１の短期公開鍵ＹＡ，１、前記第２の短期公開鍵ＹＡ，２の底ｇ１、ｇ２に対する離散対数が等しいことを示す非対話ゼロ知識証明πＡを生成する非対話ゼロ知識証明部と、
前記第１の短期公開鍵ＹＢ，１、前記第２の短期公開鍵ＹＢ，２の底ｇ１、ｇ２に対する離散対数が等しいことを示す非対話ゼロ知識証明πＢを検証する非対話ゼロ知識検証部とをさらに備え、
前記鍵交換部は、前記相手側鍵交換装置に前記非対話ゼロ知識証明πＡを送信し、前記相手側鍵交換装置から前記非対話ゼロ知識証明πＢを受信し、
前記共有鍵生成部は、前記非対話ゼロ知識検証部の検証結果が正しい場合に、前記共有鍵を計算すること
を特徴とする鍵交換装置。
【請求項３】
請求項１に記載の鍵交換装置であって、
前記第１の短期公開鍵ＹＢ，１、前記第２の短期公開鍵ＹＢ，２の底ｇ１、ｇ２に対する離散対数が等しいことをペアリングを用いて検証するペアリング短期公開鍵検証部をさらに備え、
前記共有鍵生成部は、前記ペアリング短期公開鍵検証部の検証結果が正しい場合に、前記共有鍵を計算すること
を特徴とする鍵交換装置。
【請求項４】
請求項１から３の何れかに記載の鍵交換装置であって、
前記ｍを３として、
前記多項式群を
【数６０】
0005651611.tif 000061
としたことを特徴とする鍵交換装置。
【請求項５】
請求項１から３の何れかに記載の鍵交換装置であって、
前記ｍを４として、
前記多項式群を
【数６１】
0005651611.tif 000062
としたことを特徴とする鍵交換装置。
【請求項６】
ｉ＝１，…，ｍであるｍ個の多項式群
【数６２】
0005651611.tif 000063
であって、
【数６３】
0005651611.tif 000064
を充たす多項式群の係数を用いる鍵交換システムであって、
前記鍵交換システムは、鍵生成局と、２台以上の鍵交換装置とからなり、
前記鍵生成局は、
ｋｂｉｔ（ｋは任意の自然数）の素数位数の巡回群であるＧ１、Ｇ２、ＧＴと、Ｇ１、Ｇ２の生成元であるｇ１、ｇ２と、ＧＴの生成元であるｇＴ＝ｅ（ｇ１，ｇ２）と、非対称ペアリングｅ：Ｇ１×Ｇ２→ＧＴと、ハッシュ関数Ｈ：｛０，１｝＊→｛０，１｝ｋ、Ｈ１：｛０，１｝＊→Ｇ１、Ｈ２：｛０，１｝＊→Ｇ２とを公開するパラメータ公開部と、
任意にマスタ秘密鍵
【数６４】
0005651611.tif 000065
を選択するマスタ秘密鍵生成部と、
第１のマスタ公開鍵
【数６５】
0005651611.tif 000066
と、第２のマスタ公開鍵
【数６６】
0005651611.tif 000067
とを公開するマスタ公開鍵公開部と、
前記鍵交換装置から識別子ＩＤＡ、または識別子ＩＤＢを受信する識別子受信部と、
前記受信した識別子ＩＤＡ、または識別子ＩＤＢに対して第１、第２の秘密鍵
【数６７】
0005651611.tif 000068
または、第１、第２の秘密鍵
【数６８】
0005651611.tif 000069
を生成する秘密鍵生成部と、
前記生成された第１、第２の秘密鍵を対応する鍵交換装置に送信する秘密鍵送信部とを備え、
前記鍵交換装置は、
当該鍵交換装置の識別子である識別子ＩＤＡ（当該鍵交換装置と鍵交換を行う相手側である鍵交換装置の識別子をＩＤＢとする）を前記鍵生成局に送信する識別子送信部と、
前記第１、第２の秘密鍵を前記鍵生成局から受信する秘密鍵受信部と、
短期秘密鍵
【数６９】
0005651611.tif 000070
をランダムに選択する短期秘密鍵生成部と、
前記生成された短期秘密鍵ｙＡを用いて、第１の短期公開鍵
【数７０】
0005651611.tif 000071
と、第２の短期公開鍵
【数７１】
0005651611.tif 000072
を計算する短期公開鍵生成部と、
前記識別子ＩＤＡ、前記識別子ＩＤＢ、前記第１の短期公開鍵ＹＡ，１、前記第２の短期公開鍵ＹＡ，２を相手側鍵交換装置に送信し、前記相手側鍵交換装置から前記識別子ＩＤＡ、前記識別子ＩＤＢ、前記相手側鍵交換装置が生成した第１の短期公開鍵ＹＢ，１、第２の短期公開鍵ＹＢ，２を受信する鍵交換部と、
共有値
【数７２】
0005651611.tif 000073
を計算し、共有鍵
【数７３】
0005651611.tif 000074
を計算する共有鍵生成部と、
を備えることを特徴とする鍵交換システム。
【請求項７】
請求項６に記載の鍵交換システムであって、
前記鍵交換装置が、
前記第１の短期公開鍵ＹＡ，１、前記第２の短期公開鍵ＹＡ，２の底ｇ１、ｇ２に対する離散対数が等しいことを示す非対話ゼロ知識証明πＡを生成する非対話ゼロ知識証明部と、
前記第１の短期公開鍵ＹＢ，１、前記第２の短期公開鍵ＹＢ，２の底ｇ１、ｇ２に対する離散対数が等しいことを示す非対話ゼロ知識証明πＢを検証する非対話ゼロ知識検証部とをさらに備え、
前記鍵交換部は、前記相手側鍵交換装置に前記非対話ゼロ知識証明πＡを送信し、前記相手側鍵交換装置から前記非対話ゼロ知識証明πＢを受信し、
前記共有鍵生成部は、前記非対話ゼロ知識検証部の検証結果が正しい場合に、前記共有鍵を計算すること
を特徴とする鍵交換システム。
【請求項８】
請求項６に記載の鍵交換システムであって、
前記鍵交換装置が、
前記第１の短期公開鍵ＹＢ，１、前記第２の短期公開鍵ＹＢ，２の底ｇ１、ｇ２に対する離散対数が等しいことをペアリングを用いて検証するペアリング短期公開鍵検証部をさらに備え、
前記共有鍵生成部は、前記ペアリング短期公開鍵検証部の検証結果が正しい場合に、前記共有鍵を計算すること
を特徴とする鍵交換システム。
【請求項９】
ｋｂｉｔ（ｋは任意の自然数）の素数位数の巡回群であるＧ１、Ｇ２、ＧＴと、Ｇ１、Ｇ２の生成元であるｇ１、ｇ２と、ＧＴの生成元であるｇＴ＝ｅ（ｇ１，ｇ２）と、非対称ペアリングｅ：Ｇ１×Ｇ２→ＧＴと、ハッシュ関数Ｈ：｛０，１｝＊→｛０，１｝ｋ、Ｈ１：｛０，１｝＊→Ｇ１、Ｈ２：｛０，１｝＊→Ｇ２と、任意に選択されたマスタ秘密鍵
【数７４】
0005651611.tif 000075
から生成された、第１のマスタ公開鍵
【数７５】
0005651611.tif 000076
と、第２のマスタ公開鍵
【数７６】
0005651611.tif 000077
とを公開パラメータとして用い、
ｉ＝１，…，ｍであるｍ個の多項式群
【数７７】
0005651611.tif 000078
であって、
【数７８】
0005651611.tif 000079
を充たす多項式群の係数を用い、鍵交換装置により実行される鍵交換方法であって、
当該鍵交換装置の識別子である識別子ＩＤＡ（当該鍵交換装置と鍵交換を行う相手側である鍵交換装置の識別子をＩＤＢとする）を鍵生成局に送信する識別子送信ステップと、
【数７９】
0005651611.tif 000080
として生成された第１の秘密鍵ＤＡ，１と、
【数８０】
0005651611.tif 000081
として生成された第２の秘密鍵ＤＡ，２とを鍵生成局から受信する秘密鍵受信ステップと、
短期秘密鍵
【数８１】
0005651611.tif 000082
をランダムに選択する短期秘密鍵生成ステップと、
前記生成された短期秘密鍵ｙＡを用いて、第１の短期公開鍵
【数８２】
0005651611.tif 000083
と、第２の短期公開鍵
【数８３】
0005651611.tif 000084
を計算する短期公開鍵生成ステップと、
前記識別子ＩＤＡ、前記識別子ＩＤＢ、前記第１の短期公開鍵ＹＡ，１、前記第２の短期公開鍵ＹＡ，２を相手側鍵交換装置に送信し、相手側鍵交換装置から前記識別子ＩＤＡ、前記識別子ＩＤＢ、前記相手側鍵交換装置が生成した第１の短期公開鍵ＹＢ，１、第２の短期公開鍵ＹＢ，２を受信する鍵交換ステップと、
共有値
【数８４】
0005651611.tif 000085
を計算し、共有鍵
【数８５】
0005651611.tif 000086
を計算する共有鍵生成ステップと、
を有することを特徴とする鍵交換方法。
【請求項１０】
請求項９に記載の鍵交換方法であって、
前記第１の短期公開鍵ＹＡ，１、前記第２の短期公開鍵ＹＡ，２の底ｇ１、ｇ２に対する離散対数が等しいことを示す非対話ゼロ知識証明πＡを生成する非対話ゼロ知識証明ステップと、
前記第１の短期公開鍵ＹＢ，１、前記第２の短期公開鍵ＹＢ，２の底ｇ１、ｇ２に対する離散対数が等しいことを示す非対話ゼロ知識証明πＢを検証する非対話ゼロ知識検証ステップとをさらに有し、
前記鍵交換ステップにおいて、前記相手側鍵交換装置に前記非対話ゼロ知識証明πＡを送信し、前記相手側鍵交換装置から前記非対話ゼロ知識証明πＢを受信し、
前記共有鍵生成ステップにおいて、前記非対話ゼロ知識検証ステップの検証結果が正しい場合に、前記共有鍵を計算すること
を特徴とする鍵交換方法。
【請求項１１】
請求項９に記載の鍵交換方法であって、
前記第１の短期公開鍵ＹＢ，１、前記第２の短期公開鍵ＹＢ，２の底ｇ１、ｇ２に対する離散対数が等しいことをペアリングを用いて検証するペアリング短期公開鍵検証ステップをさらに有し、
前記共有鍵生成ステップにおいて、前記ペアリング短期公開鍵検証ステップの検証結果が正しい場合に、前記共有鍵を計算すること
を特徴とする鍵交換方法。
【請求項１２】
ｉ＝１，…，ｍであるｍ個の多項式群
【数８６】
0005651611.tif 000087
であって、
【数８７】
0005651611.tif 000088
を充たす多項式群の係数を用い、鍵生成局と鍵交換装置により実行される鍵交換方法であって、
前記鍵生成局は、
ｋｂｉｔ（ｋは任意の自然数）の素数位数の巡回群であるＧ１、Ｇ２、ＧＴと、Ｇ１、Ｇ２の生成元であるｇ１、ｇ２と、ＧＴの生成元であるｇＴ＝ｅ（ｇ１，ｇ２）と、非対称ペアリングｅ：Ｇ１×Ｇ２→ＧＴと、ハッシュ関数Ｈ：｛０，１｝＊→｛０，１｝ｋ、Ｈ１：｛０，１｝＊→Ｇ１、Ｈ２：｛０，１｝＊→Ｇ２とを公開するパラメータ公開ステップと、
任意にマスタ秘密鍵
【数８８】
0005651611.tif 000089
を選択するマスタ秘密鍵生成ステップと、
第１のマスタ公開鍵
【数８９】
0005651611.tif 000090
と、第２のマスタ公開鍵
【数９０】
0005651611.tif 000091
とを公開するマスタ公開鍵公開ステップと、
前記鍵交換装置から識別子ＩＤＡ、または識別子ＩＤＢを受信する識別子受信ステップと、
前記受信した識別子ＩＤＡ、または識別子ＩＤＢに対して第１、第２の秘密鍵
【数９１】
0005651611.tif 000092
または、第１、第２の秘密鍵
【数９２】
0005651611.tif 000093
を生成する秘密鍵生成ステップと、
前記生成された第１、第２の秘密鍵を対応する鍵交換装置に送信する秘密鍵送信ステップとを実行し、
前記鍵交換装置は、
当該鍵交換装置の識別子である識別子ＩＤＡ（当該鍵交換装置と鍵交換を行う相手側である鍵交換装置の識別子をＩＤＢとする）を前記鍵生成局に送信する識別子送信ステップと、
前記第１、第２の秘密鍵を前記鍵生成局から受信する秘密鍵受信ステップと、
短期秘密鍵
【数９３】
0005651611.tif 000094
をランダムに選択する短期秘密鍵生成ステップと、
前記生成された短期秘密鍵ｙＡを用いて、第１の短期公開鍵
【数９４】
0005651611.tif 000095
と、第２の短期公開鍵
【数９５】
0005651611.tif 000096
を計算する短期公開鍵生成ステップと、
前記識別子ＩＤＡ、前記識別子ＩＤＢ、前記第１の短期公開鍵ＹＡ，１、前記第２の短期公開鍵ＹＡ，２を相手側鍵交換装置に送信し、前記相手側鍵交換装置から前記識別子ＩＤＡ、前記識別子ＩＤＢ、前記相手側鍵交換装置が生成した第１の短期公開鍵ＹＢ，１、第２の短期公開鍵ＹＢ，２を受信する鍵交換ステップと、
共有値
【数９６】
0005651611.tif 000097
を計算し、共有鍵
【数９７】
0005651611.tif 000098
を計算する共有鍵生成ステップと、
を実行することを特徴とする鍵交換方法。
【請求項１３】
請求項１２に記載の鍵交換方法であって、
前記鍵交換装置が、
前記第１の短期公開鍵ＹＡ，１、前記第２の短期公開鍵ＹＡ，２の底ｇ１、ｇ２に対する離散対数が等しいことを示す非対話ゼロ知識証明πＡを生成する非対話ゼロ知識証明ステップと、
前記第１の短期公開鍵ＹＢ，１、前記第２の短期公開鍵ＹＢ，２の底ｇ１、ｇ２に対する離散対数が等しいことを示す非対話ゼロ知識証明πＢを検証する非対話ゼロ知識検証ステップとをさらに実行し、
前記鍵交換ステップにおいて、前記相手側鍵交換装置に前記非対話ゼロ知識証明πＡを送信し、前記相手側鍵交換装置から前記非対話ゼロ知識証明πＢを受信し、
前記共有鍵生成ステップにおいて、前記非対話ゼロ知識検証部の検証結果が正しい場合に、前記共有鍵を計算すること
を特徴とする鍵交換方法。
【請求項１４】
請求項１２に記載の鍵交換方法であって、
前記鍵交換装置が、
前記第１の短期公開鍵ＹＢ，１、前記第２の短期公開鍵ＹＢ，２の底ｇ１、ｇ２に対する離散対数が等しいことをペアリングを用いて検証するペアリング短期公開鍵検証ステップをさらに実行し、
前記共有鍵生成ステップにおいて、前記ペアリング短期公開鍵検証ステップの検証結果が正しい場合に、前記共有鍵を計算すること
を特徴とする鍵交換方法。
【請求項１５】
コンピュータを、請求項１から５の何れかに記載の鍵交換装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報セキュリティ技術の応用技術に関するものであり、二者間で共通のセッション鍵を共有する鍵交換装置、鍵交換システム、鍵交換方法、プログラムに関する。
【背景技術】
【０００２】
従来の鍵交換方式として非特許文献１が知られている。非特許文献１の鍵交換方式は長期、および短期の秘密鍵の非自明な全ての漏洩パターンに対して高い安全性を実現している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Atsushi Fujioka, Koutarou Suzuki, Berkant Ustaoglu: EphemeralKey Leakage Resilient and Efficient ID-AKEs That Can Share Identities, Private and Master Keys. Pairing 2010: 187-205
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１の鍵交換方式では、同一群からの生成元を用いて共有鍵が一致するようにシステムを構成している（対称ペアリングを前提としている）ため、非対称ペアリングに対応して、２つの群からの生成元を用いて共有鍵が一致するようにシステムを構成することは出来なかった。一方、非対称ペアリングは対称ペアリングと比較して計算量が小さく、効率が良いことが知られており、非対称ペアリングに対応する鍵交換方式の実現がなされていないことが問題であった。そこで本発明では、非対称ペアリングに対応することにより、従来の鍵交換方式よりも計算量の小さい鍵交換方式を実現する鍵交換装置を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の鍵交換装置は、ｋｂｉｔ（ｋは任意の自然数）の素数位数の巡回群であるＧ１、Ｇ２、ＧＴと、Ｇ１、Ｇ２の生成元であるｇ１、ｇ２と、ＧＴの生成元であるｇＴ＝ｅ（ｇ１，ｇ２）と、非対称ペアリングｅ：Ｇ１×Ｇ２→ＧＴと、ハッシュ関数Ｈ：｛０，１｝＊→｛０，１｝ｋ、Ｈ１：｛０，１｝＊→Ｇ１、Ｈ２：｛０，１｝＊→Ｇ２と、任意に選択されたマスタ秘密鍵
【０００６】
【数１】
0005651611.tif 000002
【０００７】
から生成された、第１のマスタ公開鍵
【０００８】
【数２】
0005651611.tif 000003
【０００９】
と、第２のマスタ公開鍵
【００１０】
【数３】
0005651611.tif 000004
【００１１】
とを公開パラメータとして用いる。また、ｉ＝１，…，ｍであるｍ個の多項式群
【００１２】
【数４】
0005651611.tif 000005
【００１３】
であって、
【００１４】
【数５】
0005651611.tif 000006
【００１５】
を充たす多項式群の係数を用いる。
【００１６】
本発明の鍵交換装置は、識別子送信部と、秘密鍵受信部と、短期秘密鍵生成部と、短期公開鍵生成部と、鍵交換部と、共有鍵生成部とを備える。識別子送信部は、当該鍵交換装置の識別子である識別子ＩＤＡ（当該鍵交換装置と鍵交換を行う相手側である鍵交換装置の識別子をＩＤＢとする）を鍵生成局に送信する。秘密鍵受信部は、
【００１７】
【数６】
0005651611.tif 000007
【００１８】
として生成された第１の秘密鍵ＤＡ，１と、
【００１９】
【数７】
0005651611.tif 000008
【００２０】
として生成された第２の秘密鍵ＤＡ，２とを鍵生成局から受信する。短期秘密鍵生成部は、短期秘密鍵
【００２１】
【数８】
0005651611.tif 000009
【００２２】
をランダムに選択する。短期公開鍵生成部は、生成された短期秘密鍵ｙＡを用いて、第１の短期公開鍵
【００２３】
【数９】
0005651611.tif 000010
【００２４】
と、第２の短期公開鍵
【００２５】
【数１０】
0005651611.tif 000011
【００２６】
を計算する。鍵交換部は、識別子ＩＤＡ、識別子ＩＤＢ、第１の短期公開鍵ＹＡ，１、第２の短期公開鍵ＹＡ，２を相手側鍵交換装置に送信し、相手側鍵交換装置から識別子ＩＤＡ、識別子ＩＤＢ、相手側鍵交換装置が生成した第１の短期公開鍵ＹＢ，１、第２の短期公開鍵ＹＢ，２を受信する。共有鍵生成部は、共有値
【００２７】
【数１１】
0005651611.tif 000012
【００２８】
を計算し、共有鍵
【００２９】
【数１２】
0005651611.tif 000013
【００３０】
を計算する。
【発明の効果】
【００３１】
本発明の鍵交換装置によれば、非対称ペアリングに対応することにより、従来の鍵交換方式よりも計算量の小さい鍵交換方式を実現できる。
【図面の簡単な説明】
【００３２】
【図１】実施例１の鍵交換システムの構成を示すブロック図。
【図２】実施例１の鍵交換システムの動作を示すフローチャート。
【図３】実施例２の鍵交換システムの構成を示すブロック図。
【図４】実施例２の鍵交換システムの動作を示すフローチャート。
【図５】実施例３の鍵交換システムの構成を示すブロック図。
【図６】実施例３の鍵交換システムの動作を示すフローチャート。
【発明を実施するための形態】
【００３３】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００３４】
＜本発明のポイント＞
本発明では、以下のようにして非対称ペアリングには対応していないという問題を解決した。Ｇ１、Ｇ２、ＧＴをｋｂｉｔ（ｋは任意の自然数）の素数位数ｑの巡回群、ｇ１、ｇ２をＧ１、Ｇ２の生成元、ｇＴ＝ｅ（ｇ１，ｇ２）をＧＴの生成元、ｅ：Ｇ１×Ｇ２→ＧＴを非対称ペアリングとする。一方のユーザであるユーザＵＡの長期秘密鍵と短期公開鍵をＧ１、Ｇ２のうちの何れかの元で作り、他方のユーザであるユーザＵＢの長期秘密鍵と短期公開鍵をＧ１、Ｇ２のうち、ユーザＵＡの長期秘密鍵と短期公開鍵の生成に用いた群と異なる群の元で作り、これらの非対称ペアリングの値を共有値とすることにより、非対称ペアリングに基づく方式を構成した。
【実施例１】
【００３５】
図１、図２を参照して、本発明の基本的な構成例である実施例１の鍵交換システム１０について詳細に説明する。図１は本実施例の鍵交換システム１０の構成を示すブロック図である。図２は本実施例の鍵交換システム１０の動作を示すフローチャートである。図１に示すように、本実施例の鍵交換システム１０は、鍵生成局１と、２台以上の鍵交換装置２により構成される。鍵交換装置２はグループに属するユーザ１人につき１台存在するものとする。図１は便宜上、鍵交換装置２を２台（２Ａ、２Ｂ）として図示している。従って、図１の例では少なくともユーザ２名がそれぞれ鍵交換装置（２Ａ、２Ｂ）のいずれかを１台ずつ操作できる状態にあるものとする。図１の例では便宜上、鍵交換装置２を２台としたが、鍵交換装置２はこれに限られず、２台以上であれば何台であってもよい。鍵生成局１は、マスタ秘密鍵生成部１１と、マスタ秘密鍵記憶部１２と、パラメータ公開部１３と、マスタ公開鍵公開部１４と、識別子受信部１５と、秘密鍵生成部１６と、秘密鍵送信部１７とを備える。鍵交換装置２は、識別子送信部２１と、秘密鍵受信部２２と、識別子記憶部２３と、短期秘密鍵生成部２４と、短期公開鍵生成部２５と、鍵交換部２６と、共有鍵生成部２７とを備える。
【００３６】
本実施例の鍵交換システム１０を各装置、各構成部の動作に従って説明する。まず、以下のような、ｍ個の多項式
【００３７】
【数１３】
0005651611.tif 000014
【００３８】
を考える。ここで、ｃｉ，ｊ，ｋ（ｉ＝１，．．．，ｍ，ｊ，ｋ＝０，１）は定数であってもよいし、短期公開鍵、公開鍵、ユーザＩＤ、公開パラメータなどに依存して決まる数でもよい。
【００３９】
【数１４】
0005651611.tif 000015
【００４０】
上記のｍ個の多項式
【００４１】
【数１５】
0005651611.tif 000016
【００４２】
で、
【００４３】
【数１６】
0005651611.tif 000017
【００４４】
であるものを用いて、以下のような認証鍵交換方式
【００４５】
【数１７】
0005651611.tif 000018
【００４６】
を構成する。
【００４７】
Ｇ１、Ｇ２、ＧＴをｋｂｉｔ（ｋは任意の自然数）の素数位数ｑの巡回群、ｇ１、ｇ２をＧ１、Ｇ２の生成元、ｇＴ＝ｅ（ｇ１，ｇ２）をＧＴの生成元、ｅ：Ｇ１×Ｇ２→ＧＴを非対称ペアリングとする。Ｈ：｛０，１｝＊→｛０，１｝ｋとＨ１：｛０，１｝＊→Ｇ１とＨ２：｛０，１｝＊→Ｇ２をハッシュ関数とする。鍵生成局１のパラメータ公開部１３は、Ｇ１、Ｇ２、ＧＴ、ｇ１、ｇ２、ｇＴ、ｅ、Ｈ、Ｈ１、Ｈ２を公開パラメータ５として公開する（Ｓ１３）。このとき、公開パラメータ５は、鍵交換装置２からのアクセスを許可されたサーバの記憶領域などに記憶することなどによって公開される。鍵生成局１のマスタ秘密鍵生成部１１は、マスタ秘密鍵
【００４８】
【数１８】
0005651611.tif 000019
【００４９】
をランダムに選ぶ（Ｓ１１）。マスタ秘密鍵記憶部１２は、マスタ秘密鍵生成部１１が生成したマスタ秘密鍵を記憶する（Ｓ１２）。なお、マスタ秘密鍵記憶部１２は適宜省略することもできるし、一時メモリ、バッファとして実現しても良い。マスタ公開鍵公開部１４は、マスタ秘密鍵記憶部１２に記憶されたマスタ秘密鍵ｚを用いて、第１のマスタ公開鍵
【００５０】
【数１９】
0005651611.tif 000020
【００５１】
と、第２のマスタ公開鍵
【００５２】
【数２０】
0005651611.tif 000021
【００５３】
を公開パラメータ５として公開する（Ｓ１４）。ここで、パラメータ公開部１３が公開したＧ１、Ｇ２、ＧＴ、ｇ１、ｇ２、ｇＴ、ｅ、Ｈ、Ｈ１、Ｈ２は、閲覧に制限がないが、マスタ公開鍵公開部１４が公開する第１のマスタ公開鍵と、第２のマスタ公開鍵については閲覧に制限を設けるものとする。具体的には、第１のマスタ公開鍵と、第２のマスタ公開鍵は、同一のグループ（例えば、会社組織など）に属するユーザ間では閲覧可能であるが、グループに属しないユーザからは閲覧不能であるものとする。
【００５４】
ここで、ｉをグループに属するユーザ数を表す２以上の自然数とし、グループに属するｉ番目のユーザをユーザＵｉと表すこととし、ユーザＵｉの操作する端末を鍵交換装置２ｉと呼ぶ。ユーザＵｉの鍵交換装置２ｉの識別子送信部２１は、識別子ＩＤｉを鍵生成局１に送信する（Ｓ２１）。図１の例は便宜上、鍵交換装置２を２つとした例であるから、鍵交換装置２Ａの識別子送信部２１、および鍵交換装置２Ｂの識別子送信部２１は、鍵生成局１に識別子ＩＤＡ、ＩＤＢを送信する。鍵生成局１の識別子受信部１５は、任意のユーザ（鍵交換装置）Ｕｉから識別子
【００５５】
【数２１】
0005651611.tif 000022
【００５６】
を受信する（Ｓ１５）。図１の例では、鍵生成局１の識別子受信部１５は、鍵交換装置２Ａから識別子ＩＤＡを、鍵交換装置２Ｂから識別子ＩＤＢをそれぞれ受信する。鍵生成局１の秘密鍵生成部１６は、識別子受信部１５が受信した識別子に対して、ハッシュ関数Ｈ１、Ｈ２を用いて
【００５７】
【数２２】
0005651611.tif 000023
【００５８】
と、
【００５９】
【数２３】
0005651611.tif 000024
【００６０】
を計算し、マスタ秘密鍵ｚを用いて第１の秘密鍵
【００６１】
【数２４】
0005651611.tif 000025
【００６２】
と、第２の秘密鍵
【００６３】
【数２５】
0005651611.tif 000026
【００６４】
を生成する（Ｓ１６）。図１の例では、鍵生成局１の秘密鍵生成部１６は、識別子ＩＤＡ、ＩＤＢに対して第１の秘密鍵
【００６５】
【数２６】
0005651611.tif 000027
【００６６】
と、第２の秘密鍵
【００６７】
【数２７】
0005651611.tif 000028
【００６８】
を生成する。次に、鍵生成局１の秘密鍵送信部１７は、第１の秘密鍵Ｄｉ，１と、第２の秘密鍵Ｄｉ，２とを鍵交換装置２ｉに送信する（Ｓ１７）。図１の例では、鍵生成局１の秘密鍵送信部１７は、第１の秘密鍵ＤＡ，１と、第２の秘密鍵ＤＡ，２とを鍵交換装置２Ａに、第１の秘密鍵ＤＢ，１と、第２の秘密鍵ＤＢ，２とを鍵交換装置２Ｂにそれぞれ送信する。次に、ユーザＵｉの鍵交換装置２ｉの秘密鍵受信部２２は、鍵生成局１が送信した第１の秘密鍵Ｄｉ，１と、第２の秘密鍵Ｄｉ，２とを受信する（Ｓ２２）。図１の例では、鍵交換装置２Ａの秘密鍵受信部２２は、鍵生成局１が送信した第１の秘密鍵ＤＡ，１と、第２の秘密鍵ＤＡ，２とを受信し、鍵交換装置２Ｂの秘密鍵受信部２２は、鍵生成局１が送信した第１の秘密鍵ＤＢ，１と、第２の秘密鍵ＤＢ，２とを受信する。
【００６９】
以下、図１の例に従って、鍵交換装置２Ａ、２Ｂ間の認証鍵交換動作、共有鍵Ｋの生成動作について説明する。鍵交換装置２Ａの識別子記憶部２３には、同一のグループに属する全てのユーザの識別子が記憶されている。図１の例では少なくともユーザＵＡ、ユーザＵＢは同一のグループに属しているため、識別子記憶部２３には少なくともユーザＵＡの識別子ＩＤＡ、ユーザＵＢの識別子ＩＤＢが記憶されている。なお、識別子記憶部２３は、必須の構成要素ではない。例えば、鍵交換を行いたい鍵交換装置同士が、お互いに識別子を事前に交換しておくこととすれば、鍵交換装置２は必ずしもグループに属するユーザ全ての識別子を全て記憶しておく必要はないからである。まず、鍵交換装置２Ａの短期秘密鍵生成部２４は、短期秘密鍵
【００７０】
【数２８】
0005651611.tif 000029
【００７１】
をランダムに選ぶ（Ｓ２４）。次に、鍵交換装置２Ａの短期公開鍵生成部２５は、短期秘密鍵ｙＡを用いて、第１の短期公開鍵
【００７２】
【数２９】
0005651611.tif 000030
【００７３】
と、第２の短期公開鍵
【００７４】
【数３０】
0005651611.tif 000031
【００７５】
を計算する（Ｓ２５）。次に、鍵交換装置２Ａの鍵交換部２６は、識別子記憶部２３からＩＤＡ、ＩＤＢを取得し、短期公開鍵生成部２５から第１の短期公開鍵ＹＡ，１、と第２の短期公開鍵ＹＡ，２を取得して、（ＩＤＡ，ＩＤＢ，ＹＡ，１，ＹＡ，２）を鍵交換装置２Ｂに送信する（Ｓ２６ａ）。
【００７６】
鍵交換装置２Ｂの鍵交換部２６は、鍵交換装置２Ａから（ＩＤＡ，ＩＤＢ，ＹＡ，１，ＹＡ，２）を受信する（Ｓ２６ｂ）。そして、鍵交換装置２Ａと同じように、短期秘密鍵生成部２４が、短期秘密鍵
【００７７】
【数３１】
0005651611.tif 000032
【００７８】
をランダムに選ぶ（Ｓ２４）。次に、鍵交換装置２Ｂの短期公開鍵生成部２５は、短期秘密鍵ｙＢを用いて、第１の短期公開鍵
【００７９】
【数３２】
0005651611.tif 000033
【００８０】
と、第２の短期公開鍵
【００８１】
【数３３】
0005651611.tif 000034
【００８２】
を計算する（Ｓ２５）。次に、鍵交換装置２Ｂの鍵交換部２６は、識別子記憶部２３からＩＤＡ、ＩＤＢを取得し、短期公開鍵生成部２５から第１の短期公開鍵ＹＢ，１、と第２の短期公開鍵ＹＢ，２を取得して、（ＩＤＡ，ＩＤＢ，ＹＢ，１，ＹＢ，２）を鍵交換装置２Ａに送信する（Ｓ２６ａ）。鍵交換装置２Ｂの共有鍵生成部２７は、共有値
【００８３】
【数３４】
0005651611.tif 000035
【００８４】
を計算し、共有鍵
【００８５】
【数３５】
0005651611.tif 000036
【００８６】
を計算する（Ｓ２７）。
【００８７】
鍵交換装置２Ａの鍵交換部２６は、（ＩＤＡ，ＩＤＢ，ＹＢ，１，ＹＢ，２）を受信する（Ｓ２６ｂ）。鍵交換装置２Ａの共有鍵生成部２７は、
【００８８】
【数３６】
0005651611.tif 000037
【００８９】
を計算し、共有鍵
【００９０】
【数３７】
0005651611.tif 000038
【００９１】
を計算する（Ｓ２７）。
【００９２】
鍵交換装置２Ａの共有鍵生成部２７が計算した共有値は、
【００９３】
【数３８】
0005651611.tif 000039
【００９４】
となる。一方、鍵交換装置２Ｂの共有鍵生成部２７が計算した共有値は、
【００９５】
【数３９】
0005651611.tif 000040
【００９６】
となり、双方の共有値が一致するため、共有鍵Ｋは一致する。
【００９７】
このように、本実施例の鍵交換システム１０は、鍵生成局１のマスタ公開鍵公開部１４、秘密鍵生成部１６、鍵交換装置２の短期公開鍵生成部２５がそれぞれ２種類（第１、第２）のマスタ公開鍵、秘密鍵、短期公開鍵を、２種類の巡回群Ｇ１、Ｇ２を生成元として生成して、一方のユーザの秘密鍵と短期公開鍵の生成元と、他方のユーザの秘密鍵と短期公開鍵の生成元とを異なる群としておき、さらにこれらを用いて各々の鍵交換装置２の共有鍵生成部２７において生成される共有鍵Ｋを互いに一致させることにより、非対称ペアリングに基づく鍵交換を実現した。
【実施例２】
【００９８】
以下、図３、図４を参照して、実施例１の鍵交換システム１０を拡張した構成例である実施例２の鍵交換システム２０について詳細に説明する。図３は本実施例の鍵交換システム２０の構成を示すブロック図である。図４は本実施例の鍵交換システム２０の動作を示すフローチャートである。図３に示すように、本実施例の鍵交換システム２０は、鍵生成局１と、２台以上の鍵交換装置３により構成される。実施例１と同様に鍵交換装置３はグループに属するユーザ１人につき１台存在するものとする。図３は便宜上、鍵交換装置３を２台（３Ａ、３Ｂ）として図示しているが、鍵交換装置３はこれに限られず、２台以上であれば何台であってもよい。
【００９９】
本実施例の鍵交換システム２０の鍵生成局１は、実施例１における鍵生成局１と全く同じであるため説明を割愛する。本実施例の鍵交換システム２０の鍵交換装置３は、識別子送信部２１と、秘密鍵受信部２２と、識別子記憶部２３と、短期秘密鍵生成部２４と、短期公開鍵生成部２５と、鍵交換部３６と、共有鍵生成部３７と、非対話ゼロ知識証明部３８と、非対話ゼロ知識検証部３９とを備える。実施例１の鍵交換装置２と共通する構成部である識別子送信部２１と、秘密鍵受信部２２と、識別子記憶部２３と、短期秘密鍵生成部２４と、短期公開鍵生成部２５については、実施例１において同一番号を付した各構成部と同じ動作をするため説明を割愛する。
【０１００】
以下、鍵交換部３６、共有鍵生成部３７、非対話ゼロ知識証明部３８、非対話ゼロ知識検証部３９の動作について説明する。鍵交換装置３Ａの非対話ゼロ知識証明部３８は、第１の短期公開鍵ＹＡ，１、第２の短期公開鍵ＹＡ，２の底ｇ１、ｇ２に対する離散対数が等しいことを示す非対話ゼロ知識証明πＡを生成する（Ｓ３８）。鍵交換装置３Ａの鍵交換部３６は、識別子記憶部２３からＩＤＡ、ＩＤＢを取得し、短期公開鍵生成部２５から第１の短期公開鍵ＹＡ，１、と第２の短期公開鍵ＹＡ，２を取得し、非対話ゼロ知識証明部３８から非対話ゼロ知識証明πＡを取得して、（ＩＤＡ，ＩＤＢ，ＹＡ，１，ＹＡ，２、πＡ）を鍵交換装置３Ｂに送信する（Ｓ３６ａ）。鍵交換装置３Ｂの非対話ゼロ知識証明部３８は、第１の短期公開鍵ＹＢ，１、第２の短期公開鍵ＹＢ，２の底ｇ１、ｇ２に対する離散対数が等しいことを示す非対話ゼロ知識証明πＢを生成する（Ｓ３８）。鍵交換装置３Ｂの鍵交換部３６は、識別子記憶部２３からＩＤＡ、ＩＤＢを取得し、短期公開鍵生成部２５から第１の短期公開鍵ＹＢ，１、と第２の短期公開鍵ＹＢ，２を取得し、非対話ゼロ知識証明部３８から非対話ゼロ知識証明πＢを取得して、（ＩＤＡ，ＩＤＢ，ＹＢ，１，ＹＢ，２、πＢ）を鍵交換装置２Ａに送信する（Ｓ３６ａ）。鍵交換装置３Ａの鍵交換部３６は、鍵交換装置３Ｂから（ＩＤＡ，ＩＤＢ，ＹＢ，１，ＹＢ，２、πＢ）を受信する（Ｓ３６ｂ）。鍵交換装置３Ｂの鍵交換部３６は、鍵交換装置３Ａから（ＩＤＡ，ＩＤＢ，ＹＡ，１，ＹＡ，２、πＡ）を受信する（Ｓ３６ｂ）。次に、鍵交換装置３Ａの非対話ゼロ知識検証部３９は、鍵交換装置３Ｂから受信した非対話ゼロ知識証明πＢが正しいかどうかを検証する（Ｓ３９）。同様に、鍵交換装置３Ｂの非対話ゼロ知識検証部３９は、鍵交換装置３Ａから受信した非対話ゼロ知識証明πＡが正しいかどうかを検証する（Ｓ３９）。鍵交換装置３Ａの共有鍵生成部３７は、非対話ゼロ知識証明πＢが正しいと検証された場合に限り（Ｓ３０Ｙ）、共有鍵Ｋを生成する（Ｓ３７）。同様に、鍵交換装置３Ｂの共有鍵生成部３７は、非対話ゼロ知識証明πＡが正しいと検証された場合に限り（Ｓ３０Ｙ）、共有鍵Ｋを生成する（Ｓ３７）。
【０１０１】
このように、本実施例の鍵交換システム２０は、鍵交換装置３が非対話ゼロ知識証明部３８、非対話ゼロ知識検証部３９を備えることにより、実施例１の鍵交換システム１０の効果に加えて、第１、第２の短期公開鍵の離散対数が等しいことを、非対話ゼロ知識証明の検証を通じて検証することができる。
【実施例３】
【０１０２】
以下、図５、図６を参照して、実施例１の鍵交換システム１０を拡張した構成例である実施例３の鍵交換システム３０について詳細に説明する。図５は本実施例の鍵交換システム３０の構成を示すブロック図である。図６は本実施例の鍵交換システム３０の動作を示すフローチャートである。図５に示すように、本実施例の鍵交換システム３０は、鍵生成局１と、２台以上の鍵交換装置４により構成される。実施例１と同様に鍵交換装置４はグループに属するユーザ１人につき１台存在するものとする。図５は便宜上、鍵交換装置４を２台（４Ａ、４Ｂ）として図示しているが、鍵交換装置４はこれに限られず、２台以上であれば何台であってもよい。
【０１０３】
本実施例の鍵交換システム３０の鍵生成局１は、実施例１における鍵生成局１と全く同じであるため説明を割愛する。本実施例の鍵交換システム３０の鍵交換装置４は、識別子送信部２１と、秘密鍵受信部２２と、識別子記憶部２３と、短期秘密鍵生成部２４と、短期公開鍵生成部２５と、鍵交換部４６と、共有鍵生成部４７と、ペアリング短期公開鍵検証部４９とを備える。実施例１の鍵交換装置２と共通する構成部である識別子送信部２１と、秘密鍵受信部２２と、識別子記憶部２３と、短期秘密鍵生成部２４と、短期公開鍵生成部２５については、実施例１において同一番号を付した各構成部と同じ動作をするため説明を割愛する。
【０１０４】
以下、鍵交換部４６、共有鍵生成部４７、ペアリング短期公開鍵検証部４９の動作について説明する。まず、鍵交換装置４Ａの鍵交換部４６は、識別子記憶部２３からＩＤＡ、ＩＤＢを取得し、短期公開鍵生成部２５から第１の短期公開鍵ＹＡ，１、と第２の短期公開鍵ＹＡ，２を取得して、（ＩＤＡ，ＩＤＢ，ＹＡ，１，ＹＡ，２）を鍵交換装置４Ｂに送信する（Ｓ４６ａ）。鍵交換装置４Ｂの鍵交換部４６は、識別子記憶部２３からＩＤＡ、ＩＤＢを取得し、短期公開鍵生成部２５から第１の短期公開鍵ＹＢ，１、と第２の短期公開鍵ＹＢ，２を取得して、（ＩＤＡ，ＩＤＢ，ＹＢ，１，ＹＢ，２）を鍵交換装置２Ａに送信する（Ｓ４６ａ）。鍵交換装置４Ａの鍵交換部４６は、鍵交換装置４Ｂから（ＩＤＡ，ＩＤＢ，ＹＢ，１，ＹＢ，２）を受信する（Ｓ４６ｂ）。鍵交換装置４Ｂの鍵交換部４６は、鍵交換装置４Ａから（ＩＤＡ，ＩＤＢ，ＹＡ，１，ＹＡ，２）を受信する（Ｓ４６ｂ）。
【０１０５】
鍵交換装置４Ｂのペアリング短期公開鍵検証部４９は、以下のようにして短期公開鍵ＹＡ，１、ＹＡ，２の底ｇ１、ｇ２に対する離散対数が等しいことを検証する。鍵交換装置４Ｂのペアリング短期公開鍵検証部４９は、
【０１０６】
【数４０】
0005651611.tif 000041
【０１０７】
と、
【０１０８】
【数４１】
0005651611.tif 000042
【０１０９】
の底ｇ１、ｇ２に対する離散対数が等しいことをペアリングを用いて、
【０１１０】
【数４２】
0005651611.tif 000043
【０１１１】
と検証する（Ｓ４９）。
【０１１２】
短期公開鍵ＹＡ，１、ＹＡ，２の底ｇ１、ｇ２に対する離散対数が等しいと検証された場合に限り（Ｓ４０Ｙ）、鍵交換装置４Ｂの共有鍵生成部４７は、共有鍵Ｋを生成する（Ｓ４７）。
【０１１３】
鍵交換装置４Ａのペアリング短期公開鍵検証部４９は、以下のようにして短期公開鍵ＹＢ，１、ＹＢ，２の底ｇ１、ｇ２に対する離散対数が等しいことを検証する。鍵交換装置４Ａのペアリング短期公開鍵検証部４９は、
【０１１４】
【数４３】
0005651611.tif 000044
【０１１５】
と、
【０１１６】
【数４４】
0005651611.tif 000045
【０１１７】
の底ｇ１、ｇ２に対する離散対数が等しいことをペアリングを用いて、
【０１１８】
【数４５】
0005651611.tif 000046
【０１１９】
と検証する（Ｓ４９）。
【０１２０】
短期公開鍵ＹＢ，１、ＹＢ，２の底ｇ１、ｇ２に対する離散対数が等しいと検証された場合に限り（Ｓ４０Ｙ）、鍵交換装置４Ａの共有鍵生成部４７は、共有鍵Ｋを生成する（Ｓ４７）。
【０１２１】
このように、本実施例の鍵交換システム３０は、鍵交換装置４がペアリング短期公開鍵検証部４９を備えることにより、実施例１の鍵交換システム１０の効果に加えて、第１、第２の短期公開鍵の離散対数が等しいことを、ペアリングを用いて検証することができる。
【０１２２】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１２３】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１２４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１２５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１２７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１２８】
＜付録＞
以下、ｍ＝３、４とした場合の多項式ｐｉ（ｉ＝１，…，ｍ）の実例を簡単に記載する。
【０１２９】
＜ｍ＝３の場合＞
【０１３０】
【数４６】
0005651611.tif 000047
【０１３１】
＜ｍ＝４の場合＞
【０１３２】
【数４７】
0005651611.tif 000048
【図１】
0005651611.tif 000099
【図２】
0005651611.tif 000100
【図３】
0005651611.tif 000101
【図４】
0005651611.tif 000102
【図５】
0005651611.tif 000103
【図６】
0005651611.tif 000104