(57)【要約】【課題】鍵配送方式や公開鍵暗号方式における利便性を保ちつつ、第三者からの攻撃に対する安全性の向上を図る。【解決手段】セキュリティ装置１０から多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）をセキュリティ装置２０に送信し、さらに、セキュリティ装置１０設定の整数組ｓ（ｓ０，ｓ１，ｓ２，…，ｓｎ）を用い、演算手段２ａ、２ｂで演算した多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）＝ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩをセキュリティ装置２０に送信する。一方、セキュリティ装置２０において、セキュリティ装置２０設定の整数組ｔ（ｔ０，ｔ１，ｔ２，…，ｔｎ）を用い、演算手段３ａ、３ｂで演算した多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）＝ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｓ０ｍｏｄＩをセキュリティ装置１０に送信する。そして、共通鍵として、演算手段２ａ、２ｂでｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩを、演算手段３ａ、３ｂでｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩを演算する。【選択図】    図１
2004158951.tif 000002
【特許請求の範囲】
【請求項１】
離散対数問題を利用したセキュリティ装置において、
整数係数の多変数多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した、該多変数多項式の演算を行う第１の演算手段と、
前記第１の演算手段によって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、イデアルであって、該イデアルに対して行われた、整数係数の多変数多項式の任意の変数について任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合、によって剰余演算する第２の演算手段と、
を有することを特徴とするセキュリティ装置。
【請求項２】
共通鍵の配送相手と共用される整数係数の多変数共通多項式の任意の変数に、前記第１の整数組を加算した、該多変数多項式の演算を行う第１の演算手段である第３の演算手段と、
前記第３の演算手段によって行われた演算の結果に対し、前記第１の整数を指数とする指数演算を行い、該演算結果を、前記イデアル集合によって剰余演算する第２の演算手段である第４の演算手段と、
前記第４の演算手段による演算結果である第１の多変数多項式を、前記共通鍵の配送相手に開示する多項式開示手段と、
前記共通鍵の配送相手によって演算された第２の多変数多項式、を取得する多項式取得手段と、
前記多項式取得手段によって取得された前記第２の多変数多項式の任意の変数に、前記第１の整数組を加算した、該多変数多項式の演算を行う第１の演算手段である第５の演算手段と、
前記第５の演算手段によって行われた演算の結果に対し、前記第１の整数を指数とする指数演算を行い、該演算結果を、前記イデアル集合によって剰余演算した結果を、前記共通鍵として出力する第２の演算手段である第６の演算手段と、
を有することを特徴とする請求項１記載のセキュリティ装置。
【請求項３】
通信相手と共用される整数係数の多変数多項式の任意の変数に、前記第１の整数組を加算した、該多変数多項式の演算を行う第１の演算手段である第３の演算手段と、
前記第３の演算手段によって行われた演算の結果に対し、前記第１の整数を指数とする指数演算を行い、該演算結果を、前記イデアル集合によって剰余演算する第２の演算手段である第４の演算手段と、
前記第４の演算手段による演算結果である第１の多変数多項式を、公開鍵として公開する公開鍵公開手段と、
前記通信相手によって演算された第２の多変数多項式と、暗号文とを、取得する暗号文取得手段と、
前記暗号文取得手段によって取得された前記第２の多変数多項式の任意の変数に、前記第１の整数組を加算した、該多変数多項式の演算を行う第１の演算手段である第５の演算手段と、
前記第５の演算手段によって行われた演算の結果に対し、前記第１の整数を指数とする指数演算を行い、該演算結果を、前記イデアル集合によって剰余演算する第２の演算手段である第６の演算手段と、
前記第６の演算手段による演算結果と、前記暗号文と、の排他的論理和を演算する排他的論理和演算手段と、
を有することを特徴とする請求項１記載のセキュリティ装置。
【請求項４】
通信相手によって公開された第１の多変数多項式を、公開鍵として取得する公開鍵取得手段と、
前記公開鍵取得手段によって取得された前記第１の多変数多項式の任意の変数に、前記第１の整数組を加算した、該多変数多項式の演算を行う第１の演算手段である第３の演算手段と、
前記第３の演算手段によって行われた演算の結果に対し、前記第１の整数を指数とする指数演算を行い、該演算結果を、前記イデアル集合によって剰余演算する第２の演算手段である第４の演算手段と、
前記第４の演算手段による演算結果と、通信内容である平文と、の排他的論理和を、暗号文として演算する排他的論理和演算手段と、
前記通信相手と共用される整数係数の多変数共通多項式の任意の変数に、前記第１の整数組を加算した、該多変数多項式の演算を行う第１の演算手段である第５の演算手段と、
前記第５の演算手段によって行われた演算の結果に対し、前記第１の整数を指数とする指数演算を行い、該演算結果を、前記イデアル集合によって剰余演算する第２の演算手段である第６の演算手段と、
前記排他的論理和演算手段によって演算された前記暗号文と、前記第６の演算手段による演算結果である第２の多変数多項式とを開示する暗号文開示手段と、
を有することを特徴とする請求項１記載のセキュリティ装置。
【請求項５】
前記イデアル集合は、
整数係数の多項式がなす環のイデアルであって、δｉを任意の多変数多項式ｇ（ｘ１，ｘ２，…，ｘｎ）に対して多変数多項式ｇ（ｘ１，ｘ２，…，ｘｉ，…，ｘｎ）−ｇ（ｘ１，ｘ２，…，ｘｉ−１，…，ｘｎ）を対応させる作用素とし、ｄｅｇｉｆ（ｘ１，ｘ２，…，ｘｎ）をｆ（ｘ１，ｘ２，…，ｘｎ）のｘｉについての次数とし、（ｐ１，ｐ２，…，ｐｎ）∈Ｎｎとした場合における、｛Σ（ｐ１，ｐ２，…，ｐｎ）（Πｉ＝１ｎδｉｐｉ）ｆ（ｘ１，ｘ２，…，ｘｎ）｝によって生成されるイデアルであること、
を特徴とする請求項１から４の何れかに記載のセキュリティ装置。
【請求項６】
前記第１の演算手段は、
多変数多項式ａ（ｘ１，ｘ２，…，ｘｎ）に対し、前記第１の整数組を（ｓ１，ｓ２，…，ｓｎ）とし、ｐ＝（ｐ１，ｐ２，…，ｐｎ）∈Ｎｎとし、ｓｐ＝ｓ１ｐ１ｓ２ｐ２…ｓｎｐｎとし、ｐ！＝ｐ１！ｐ２！…，ｐｎ！とし、（∂／∂ｘ）ｐ＝（∂／∂ｘ１）ｐ１（∂／∂ｘ２）ｐ２…（∂／∂ｘｎ）ｐｎとした場合における、Σｐｓｐ（１／ｐ！）（∂／∂ｘ）ｐａ（ｘ１，ｘ２，…，ｘｎ）の演算を行う手段である、
ことを特徴とする請求項１から５の何れかに記載のセキュリティ装置。
【請求項７】
離散対数問題を利用したセキュリティ方法において、
第１のセキュリティ装置において行われる、
第２のセキュリティ装置と共用される整数係数の多変数共通多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した、該多変数多項式の演算を行う第１の演算ステップと、
前記第１の演算ステップによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、イデアルであって、該イデアルに対して行われた、整数係数の多変数多項式の任意の変数について任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合によって剰余演算する第２の演算ステップと、
前記第２の演算ステップによる演算結果である第１の多変数多項式を、前記第２のセキュリティ装置に開示する第１の多項式開示ステップと、
前記第２のセキュリティ装置によって演算された第２の多変数多項式、を取得する第１の多項式取得ステップと、
前記第１の多項式取得ステップによって取得された前記第２の多変数多項式の任意の変数に、前記第１の整数組を加算した、該多変数多項式の演算を行う第３の演算ステップと、
前記第３の演算ステップによって行われた演算の結果に対し、前記第１の整数を指数とする指数演算を行い、該演算結果を、前記イデアル集合によって剰余演算した結果を、前記共通鍵として出力する第４の演算ステップと、
前記第２のセキュリティ装置において行われる、
前記多変数共通多項式の任意の変数に、概変数ごとに独立した第２の整数組を加算した、該多変数多項式の演算を行う第５の演算ステップと、
前記第５の演算ステップによって行われた演算の結果に対し、第２の整数を指数とする指数演算を行い、該演算結果を、前記イデアル集合によって剰余演算する第６の演算ステップと、
前記第６の演算ステップによる演算結果である前記第２の多変数多項式を、前記第１のセキュリティ装置に開示する第２の多項式開示ステップと、
前記第１のセキュリティ装置によって演算された前記第１の多変数多項式、を取得する第２の多項式取得ステップと、
前記第２の多項式取得ステップによって取得された前記第１の多変数多項式の任意の変数に、前記第２の整数組を加算した、該多変数多項式の演算を行う第７の演算ステップと、
前記第７の演算ステップによって行われた演算の結果に対し、前記第２の整数を指数とする指数演算を行い、該演算結果を、前記イデアル集合によって剰余演算した結果を、前記共通鍵として出力する第８の演算ステップと、
を有することを特徴とするセキュリティ方法。
【請求項８】
離散対数問題を利用したセキュリティ方法において、
第１のセキュリティ装置において行われる、
第２のセキュリティ装置と共用される整数係数の多変数多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した、該多変数多項式の演算を行う第１の演算ステップと、
前記第１の演算ステップによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、イデアルであって、該イデアルに対して行われた、整数係数の多変数多項式の任意の変数について任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合によって剰余演算する第２の演算ステップと、
前記第２の演算ステップによる演算結果である第１の多変数多項式を、公開鍵として公開する公開鍵公開ステップと、
前記第２のセキュリティ装置において行われる、
公開された前記第１の多変数多項式を取得する公開鍵取得ステップと、
前記公開鍵取得ステップによって取得された前記第１の多変数多項式の任意の変数に、概変数ごとに独立した第２の整数組を加算した、該多変数多項式の演算を行う第３の演算ステップと、
前記第３の演算ステップによって行われた演算の結果に対し、第２の整数を指数とする指数演算を行い、該演算結果を、前記イデアル集合によって剰余演算する第４の演算ステップと、
前記第４の演算ステップによる演算結果と、通信内容である平文と、の排他的論理和を、暗号文として演算する排他的論理和演算ステップと、
前記多変数共通多項式の任意の変数に、前記第２の整数組を加算した、該多変数多項式の演算を行う第５の演算ステップと、
前記第５の演算ステップによって行われた演算の結果に対し、前記第２の整数を指数とする指数演算を行い、該演算結果を、前記イデアル集合によって剰余演算する第２の演算ステップである第６の演算ステップと、
前記排他的論理和演算ステップによって演算された前記暗号文と、前記第６の演算ステップによる演算結果である第２の多変数多項式とを開示する暗号文開示ステップと、
前記第１のセキュリティ装置において行われる、
開示された前記第２の多変数多項式と、前記暗号文とを、取得する暗号文取得ステップと、
前記暗号文取得ステップによって取得された前記第２の多変数多項式の任意の変数に、前記第１の整数組を加算した、該多変数多項式の演算を行う第７の演算ステップと、
前記第７の演算ステップによって行われた演算の結果に対し、前記第１の整数を指数とする指数演算を行い、該演算結果を、前記イデアル集合によって剰余演算する第８の演算ステップと、
前記第８の演算ステップによる演算結果と、前記暗号文と、の排他的論理和を演算する排他的論理和演算ステップと、
を有することを特徴とするセキュリティ方法。
【請求項９】
請求項１から６のいずれかに記載されたセキュリティ装置としてコンピュータを機能させるためのプログラム。
【請求項１０】
請求項９記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、情報の保守に利用されるセキュリティ装置、セキュリティ方法、その機能をコンピュータに実行させるためのセキュリティプログラム及びそれを格納したコンピュータ読み取り可能な記録媒体に関し、特に、離散対数問題を利用したセキュリティ装置、セキュリティ方法、その機能をコンピュータに実行させるためのセキュリティプログラム及びそれを格納したコンピュータ読み取り可能な記録媒体に関する。
【０００２】
【従来の技術】
従来より、離散対数問題を応用したＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式（例えば、非特許文献１参照）及びその応用としての公開鍵暗号方式が提案されている。
まず、この従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式による鍵配送手順について説明する。なお、甲乙間は、安全でない通信回線によって結ばれているものとする。
鍵の配送を行う場合、甲は、まず、擬似乱数生成装置を用いてあるＮ以下の整数ａを定め、このａを通信回線を介して乙に送信する。次に、甲は、擬似乱数生成装置を用いてある整数ｓを定めた後、整数演算装置を用いてｂ＝ａｓｍｏｄＮを計算し、整数ｓを秘密に保ったまま、計算したｂを乙に送信する。
【０００３】
これに対し、乙は、擬似乱数生成装置を用いてある整数ｔを定めた後、整数演算装置を用いてｃ＝ａｔｍｏｄＮを計算し、整数ｓを秘密に保ったまま、計算したｃを甲に送信する。また、乙は、整数演算装置を用い、甲から送信されたｂから、鍵ｋ＝ｂｔｍｏｄＮを求める。
一方、甲は、整数演算装置を用い、乙から送信されたｃから、鍵ｋ＝ｃｓｍｏｄＮを求める。
ここで、乙が求めた鍵ｋは、ｋ＝ｂｔｍｏｄＮ＝ａｓｔｍｏｄＮとなり、甲が求めた鍵ｋ＝ｃｓｍｏｄＮ＝ａｓｔｍｏｄＮと一致することになる。これにより、甲乙間で、共通鍵ｋの配送が行われたことになる。
【０００４】
つぎに、この従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式を応用した公開鍵暗号方式について説明する。以下では、乙から甲へ暗号文を送信し、甲が送られた暗号文を復号するものとする。
この場合、甲は、まず、擬似乱数生成装置を用いてあるＮ以下の整数ａを定め、このａを通信回線を介して乙に送信する。次に、甲は、擬似乱数生成装置を用いてある整数ｓを定めた後、整数演算装置を用いてｂ＝ａｓｍｏｄＮを計算し、整数ｓを秘密に保ったまま、計算したｂを乙に送信する。この整数ｓが秘密鍵として機能し、ｂが公開鍵として機能することになる。
これに対し、乙は、擬似乱数生成装置を用いてある整数ｔを定めた後、整数演算装置を用いてｃ＝ａｔｍｏｄＮを計算し、整数ｓを秘密に保ったまま、計算したｃを甲に送信する。また、乙は、整数演算装置を用い、甲から送信されたｂからｋ＝ｂｔｍｏｄＮを求め、このｋで平文Ｍを暗号化した後、この暗号文と計算したｃとを、甲に送信する。
これを受け取った甲は、整数演算装置を用い、送られたｃからｋ＝ｃｓｍｏｄＮを計算し、このｋを用い、送られた暗号文を復号する。
【０００５】
【非特許文献１】
岡本龍明、山本博資、「現代暗号」ｐｐ．２００〜２０１、１９９７年６月３０日、産業図書株式会社  ＩＳＢＮ４−７８２８−５３５３−Ｘ
【０００６】
【発明が解決しようとする課題】
しかし、従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式及びその応用としての公開鍵暗号方式では、ｂ及びｃの計算に必要な四則演算の回数が、秘密パラメータであるｓ、ｔの大きさに依存して増大してしまう。そのため、秘密パラメータｓ、ｔを大きくした場合、鍵配送時、暗号・復号時における計算量が増大し、実用面での利便性に問題があるという課題がある。
一方、秘密パラメータｓ、ｔの値が十分大きくない場合、高速指数計算法等の攻撃アルゴリズムを用いることにより、第三者が比較的容易にｋを計算できることが知られており、この場合、安全性に問題が生じることとなる。
本発明はこのような点に鑑みてなされたものであり、利用時における利便性を保ちつつ、第三者からの攻撃に対する安全性の向上を図ることが可能なセキュリティ装置を提供することを目的とする。
【０００７】
また、この発明の他の目的は、利用時における利便性を保ちつつ、第三者からの攻撃に対する安全性の向上を図ることが可能なセキュリティ方法を提供することである。
さらに、この発明の他の目的は、利用時における利便性を保ちつつ、第三者からの攻撃に対する安全性の向上を図ることが可能なセキュリティ機能を、コンピュータに実行させるためのセキュリティプログラムを提供することである。
また、この発明の他の目的は、利用時における計算量の増大を抑制することによって利便性を保ちつつ、第三者からの攻撃に対する安全性の向上を図ることが可能なセキュリティ機能を、コンピュータに実行させるためのセキュリティプログラムを格納したコンピュータ読み取り可能な記録媒体を提供することである。
【０００８】
【課題を解決するための手段】
この発明では上記課題を解決するために、セキュリティ装置において、整数係数の多変数多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した該多変数多項式の演算を行い、この演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、イデアルであって、該イデアルに対して行われた、整数係数の多変数多項式の任意の変数について任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合、によって剰余演算する。
【０００９】
ここで、整数係数の多変数多項式の任意の変数に、第１の整数組を加算した該多変数多項式の演算と、この演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を上述のイデアル集合によって剰余演算する演算と、を組み合わせることにより、従来のように単一の離散対数問題のみを用い、例えば鍵配送方式や公開鍵暗号方式を構成していたのに比べ、第三者からの攻撃に対する安全性を向上させることができる。また、この発明では、多変数多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した該多変数多項式の演算を行うため、単一変数多項式に対する同様な演算を行う構成と比べても、その安全性は高い。さらに、上述の剰余演算において上述のイデアル集合を用いることにより、上述の演算の組み合わせが実質的に可能となる。
【００１０】
【発明の実施の形態】
以下、この発明における第１の実施の形態を図面を参照して説明する。
図１は、本形態におけるセキュリティシステム１の概略を説明するための図である。
図１に例示するように、セキュリティシステム１は、セキュリティ装置２、３によって構成されている。この例の場合、セキュリティ装置２、３は、それぞれ、整数係数の多変数多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した、該多変数多項式の演算を行う演算手段２ａ、３ａ、及び演算手段２ａ、３ａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、イデアルであって、該イデアルに対して行われた、整数係数の多変数多項式の任意の変数について任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合、によって剰余演算する演算手段２ｂ、３ｂを有している。
【００１１】
なお、この「イデアル」という用語に関し、例えば、可換環Ｒの部分集合Ｉがイデアルであるとは、任意のｘ，ｙ∈Ｉについてｘ＋ｙ∈Ｉが成り立ち、かつ任意のｘ∈Ｒとｙ∈Ｉについてｘｙ∈Ｉが成り立つことを意味する。また、上述のイデアル集合の具体例としては、例えば、整数係数の多項式がなす環のイデアルであって、δｉを任意の多変数多項式ｇ（ｘ１，ｘ２，…，ｘｎ）に対して多変数多項式ｇ（ｘ１，ｘ２，…，ｘｉ，…，ｘｎ）−ｇ（ｘ１，ｘ２，…，ｘｉ−１，…，ｘｎ）を対応させる作用素とし、ｄｅｇｉｆ（ｘ１，ｘ２，…，ｘｎ）をｆ（ｘ１，ｘ２，…，ｘｎ）のｘｉについての次数とし、（ｐ１，ｐ２，…，ｐｎ）∈Ｎｎとした場合における、｛Σ（ｐ１，ｐ２，…，ｐｎ）（Πｉ＝１ｎδｉｐｉ）ｆ（ｘ１，ｘ２，…，ｘｎ）｝によって生成されるイデアルが挙げられる。また、この例の場合、セキュリティ装置２、３は、図示していないセキュリティ装置２、３で共通の自然数ｎ及び整数係数の多変数多項式ｆ（ｘ１，ｘ２，…，ｘｎ）を生成する手段を有しており、上記｛Σ（ｐ１，ｐ２，…，ｐｎ）（Πｉ＝１ｎδｉｐｉ）ｆ（ｘ１，ｘ２，…，ｘｎ）｝にあるｎ及びｆ（ｘ１，ｘ２，…，ｘｎ）は、この手段によって生成されたものである。なお、「Ｎｎ」とは、ｎ個の自然数の集合を意味する。
【００１２】
本形態におけるセキュリティシステム１において共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）の配送を行う場合、例えば、まず、セキュリティ装置２は、整数係数の多変数多項式である多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を生成し、生成した多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）をセキュリティ装置３に送信する。そして、例えば次に、セキュリティ装置２は、整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を定め、この整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）及び多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を用い、演算手段２ａにおいて、多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、概変数ごとに独立した整数組（ｓ１，ｓ２，…，ｓｎ）を加算した該多変数多項式の演算を行い、この演算の結果に対し、演算手段２ｂにおいて、整数（ｓ０）を指数とする指数演算を行い、該演算結果を、上述したイデアル集合（Ｉ）によって剰余演算する（ｂ（ｘ１，ｘ２，…，ｘｎ）＝ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）。この演算結果である多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）は、例えば、整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）が秘密に保たれた状態で、セキュリティ装置３に送信される。
【００１３】
一方、セキュリティ装置３は、例えば、整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を定め、この整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）、及びセキュリティ装置２から送信された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を用い、演算手段３ａにおいて、多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、概変数ごとに独立した整数組（ｔ１，ｔ２，…，ｔｎ）を加算した該多変数多項式の演算を行い、この演算の結果に対し、演算手段３ｂにおいて、整数（ｔ０）を指数とする指数演算を行い、該演算結果を、上述したイデアル集合（Ｉ）によって剰余演算する（ｃ（ｘ１，ｘ２，…，ｘｎ）＝ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）。この演算結果である多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）は、例えば、整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）が秘密に保たれた状態で、セキュリティ装置２に送信される。
セキュリティ装置３から多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）が送信されたセキュリティ装置２は、例えば、演算手段２ａにおいて、多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、概変数ごとに独立した整数組（ｓ１，ｓ２，…，ｓｎ）を加算した該多変数多項式の演算を行い、この演算の結果に対し、演算手段２ｂにおいて、整数（ｓ０）を指数とする指数演算を行い、該演算結果を、上述したイデアル集合（Ｉ）によって剰余演算し（ｋ（ｘ１，ｘ２，…，ｘｎ）＝ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）、共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）を求める。
【００１４】
一方、セキュリティ装置２から多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）が送信されたセキュリティ装置３は、例えば、演算手段３ａにおいて、多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、概変数ごとに独立した整数組（ｔ１，ｔ２，…，ｔｎ）を加算した該多変数多項式の演算を行い、この演算の結果に対し、演算手段３ｂにおいて、整数（ｔ０）を指数とする指数演算を行い、該演算結果を、上述したイデアル集合（Ｉ）によって剰余演算し（ｋ（ｘ１，ｘ２，…，ｘｎ）＝ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）、共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）を求める。
ここで、上述した演算手段２ａ、３ａにおいて行われる演算（ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）、ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）、ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）、ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ））は、入力される多変数多項式をａ（ｘ１，ｘ２，…，ｘｎ）とし、概変数ごとに独立した第１の整数組を（ｓ１，ｓ２，…，ｓｎ）とし、ｐ＝（ｐ１，ｐ２，…，ｐｎ）∈Ｎｎとし、ｓｐ＝ｓ１ｐ１ｓ２ｐ２…ｓｎｐｎとし、ｐ！＝ｐ１！ｐ２！…，ｐｎ！とし、（∂／∂ｘ）ｐ＝（∂／∂ｘ１）ｐ１（∂／∂ｘ２）ｐ２…（∂／∂ｘｎ）ｐｎとした場合における、Σｐｓｐ（１／ｐ！）（∂／∂ｘ）ｐａ（ｘ１，ｘ２，…，ｘｎ）という一般式を用いて行うことが可能であることが知られている。そして、この例においても、上述の演算手段２ａ、３ａにおける演算は、この一般式によって行うものとする。
【００１５】
この一般式が示す通り、この演算に必要な四則演算の回数は、秘密パラメータ（（ｓ１，ｓ２，…，ｓｎ）や（ｔ１，ｔ２，…，ｔｎ））の大きさに依存しない。したがって、この秘密パラメータの大きさを大きくした場合であっても、鍵配送時において、この演算手段２ａ、３ａにおいて行われる演算に起因した四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式に比べ、大幅に利便性が向上する。
また、この形態では、演算手段２ａ、３ａによって行われる、整数係数の多変数多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した該多変数多項式の演算と、演算手段２ｂ、３ｂによって行われる、第１の整数を指数とする指数演算を行い、該演算結果をイデアル集合によって剰余演算する演算と、を組み合わせることによって離散対数問題を構成し、この離散対数問題を交換することにより、共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）の配送を行うこととしたため、指数演算のみによって構成される離散対数問題によって共通鍵の配送を行っていた従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式に比べ、第三者がこの共通鍵の解読を行うことが困難となり、結果、共通鍵に対する安全性が大幅に向上する。特に、１変数多項式ではなく、多変数多項式の任意の変数に、概変数ごとに独立した整数組を加算する演算によって離散対数問題を生成する本形態の例では、その効果はより大きなものとなる。
【００１６】
次に、本形態の詳細について説明を行う。
図２は、本形態におけるセキュリティシステム１０の全体構成を例示した図である。
図２に例示するように、セキュリティシステム１０は、例えば、離散対数問題を利用し、相互に共通鍵の配送を行うセキュリティ装置２０、３０、及びセキュリティ装置２０、３０相互を通信可能なように接続するネットワーク４０を有しており、このセキュリティ装置２０、３０は、ネットワーク４０を介し、相互に情報のやり取りが可能なように、有線又は無線によって電気的に接続され、或いは接続可能な状態となっている。
セキュリティ装置２０、３０は、例えば、モデム、ＤＳＵ（Ｄｉｇｉｔａｌ  Ｓｅｒｖｉｃｅ  Ｕｎｉｔ）、ＮＣＵ（Ｎｅｔｗｏｒｋ  Ｃｏｎｔｒｏｌ  Ｕｎｉｔ）、ＴＡ（Ｔｅｒｍｉｎａｌ  Ａｄａｐｔｅｒ）等のデータ回線終端装置を具備し、或いは接続されたコンピュータによって構成されている。そして、このセキュリティ装置２０、３０には、所定のメールソフトウェアやＷＷＷブラウザがインストールされており、このメールソフトウェアやＷＷＷブラウザを用いることにより、図示していないメールサーバやＷＷＷサーバを介し、セキュリティ装置２０、３０相互間の通信が可能な構成となっている。
ネットワーク４０は、例えば、インターネット、イントラネット、エクストラネット、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＶＡＮ（Ｖａｌｕｅ  Ａｄｄｅｄ  Ｎｅｔｗｏｒｋ）等であり、その形態について特に制限はない。
なお、図２では、２つのセキュリティ装置２０、３０によってセキュリティシステム１０を構成しているが、セキュリティ装置２０、３０を、これより多く設け、それらのセキュリティ装置相互間で共通鍵の配送を行う構成としてもよい。
【００１７】
図３は、セキュリティ装置２０のハードウェア構成を例示したブロック図である。
図３に例示するように、セキュリティ装置２０は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ：中央処理装置）２１、主記憶装置２２、外部記憶装置２３、入力装置２４、記録媒体読書き装置２５、出力装置２６、通信制御装置２７及びバス２８を有しており、通信制御装置２７を介し、ネットワーク４０と通信可能なように接続され、或いは接続可能なように構成されている。
ＣＰＵ２１は、例えば、制御装置と演算装置を有するＣＩＳＣ（Ｃｏｍｐｌｅｘ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ｃｏｍｐｕｔｅｒ）方式、或いはＲＩＳＣ（Ｒｅｄｕｃｅｄ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ｃｏｍｐｕｔｅｒ）方式の中央処理装置であり、図示していない発信器から供給されるクロック信号に同期し、主記憶装置２２に格納されたオペレーティングシステム、アプリケーションプログラム等の各種プログラムの実行を行い、周辺機器の制御、必要データの呼び出し、呼び出したデータの演算・加工、演算・加工後のデータのメモリへの格納、周辺機器への出力等の各種処理を行う。
【００１８】
主記憶装置２２は、例えば、ＣＰＵ２１が直接データを読み書きできる記憶装置である。主記憶装置２２には、例えば、オペレーティングシステム、アプリケーションプログラム、データ、周辺機器を制御するドライバ等が読み込まれ、ＣＰＵ２１は、この主記憶装置２２に読み込まれたオペレーティングシステム等を実行することにより、一連の処理を行う。主記憶装置２２には、例えば、半導体メモリ等の高速処理可能な記憶素子を用い、この主記憶装置２２内の物理アドレスは、ページング方式、セグメンテーション方式等の方法により、外部記憶装置２３の仮想アドレス空間に対応付けられる。
外部記憶装置２３は、例えば、磁性体が蒸着された薄い円盤を高速回転させ、この磁性体を磁気ヘッドによって磁化することでデータの記録を行うハードディスク装置等である。
入力装置２４は、例えば、キーボードやマウス等の入出力デバイスである。
記録媒体読書き装置２５は、例えば、フレキシブルディスク等への情報の読書き、コンパクト・ディスク等からの情報の読み出し等を行う装置である。
【００１９】
出力装置２６は、例えば、画面表面の蛍光素材に電子ビームを当てることによって映像の表示を行うＣＲＴ（Ｃａｔｈｏｄｅ−ｒａｙ  Ｔｕｂｅ）ディスプレイ、或いは、電圧を加えた際に分子配列が変化する液晶の性質を利用した液晶ディスプレイ等であり、供給されたアナログ信号をもとに、所定の映像の表示を行う。
通信制御装置２７は、例えば、例えば、ＵＳＡＲＴ（Ｕｎｉｖｅｒｓａｌ  Ｓｙｎｃｈｒｏｎｏｕｓ  ａｎｄ  Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｒｅｃｅｉｖｅｒ−Ｔｒａｎｓｍｉｔｔｅｒ）等の汎用同期・非同期送受信回路であり、ネットワーク４０を介したデータ送受信時にデータの直列変換等を行う。
バス２８は、例えば、データバス、アドレスバス、コントロールバス等によって構成され、ＣＰＵ２１、主記憶装置２２、外部記憶装置２３、入力装置２４、記録媒体読書き装置２５、出力装置２６、通信制御装置２７間のデータ、アドレス情報、制御情報の受け渡しを行う。
なお、ここでは説明を省略するが、セキュリティ装置３０も、例えばこのセキュリティ装置２０と同様なハードウェア構成をとるものとする。
【００２０】
図４は、図３に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築されるセキュリティ装置２０の処理機能を例示した機能ブロック図である。
図４に例示するように、この例のセキュリティ装置２０は、共通鍵の配送相手と共用される整数係数の多変数共通多項式を生成する共通多項式生成手段２０ａ、多変数共通多項式を開示する共通多項式開示手段２０ｂ、整数組を生成する整数組生成手段２０ｃ、離散対数問題を構成する多項式の演算を行う多項式演算手段２０ｄ、第１の多変数多項式を、共通鍵の配送相手に開示する多項式開示手段２０ｅ、共通鍵の配送相手によって演算された第２の多変数多項式、を取得する多項式取得手段２０ｆ、共通鍵を算出する共通鍵算出手段２０ｇ、各種情報を記憶する記憶手段２０ｈ、セキュリティ装置２０、３０で共通の自然数、及び整数係数の多変数多項式を生成する共通要素生成手段２０ｊ、及びセキュリティ装置２０全体を制御する制御手段２０ｋを、処理機能として有している。
【００２１】
また、この例では、共通多項式生成手段２０ａは、ＳＨＡ−１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段２０ａａ、及び擬似乱数発生手段２０ａａによって発生させた擬似乱数を用いて所定の整数値を生成し、生成した整数値を係数とする多変数共通多項式を生成する多項式生成手段２０ａｂを有しており、整数組生成手段２０ｃは、ＳＨＡ−１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段２０ｃａ、及び擬似乱数発生手段２０ｃａよって発生させた擬似乱数を用いて、所定の整数値を生成する整数値演算手段２０ｃｂを有している。
【００２２】
さらに、この例の多項式演算手段２０ｄは、共通鍵の配送相手と共用される整数係数の多変数共通多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した、該多変数多項式の演算を行う第３の演算手段である演算手段２０ｄａ、及び演算手段２０ｄａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述したイデアル集合によって剰余演算する第４の演算手段である演算手段２０ｄｂを有しており、この例の多項式演算手段２０ｇは、多項式取得手段２０ｆによって取得された第２の多変数多項式の任意の変数に、第１の整数組を加算した、該多変数多項式の演算を行う第５の演算手段である演算手段２０ｇａ、及び演算手段２０ｇａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述したイデアル集合によって剰余演算した結果を、共通鍵として出力する第６の演算手段である演算手段２０ｇｂを有している。
【００２３】
また、図４に例示するように、共通多項式生成手段２０ａ、共通多項式開示手段２０ｂ、整数組生成手段２０ｃ、多項式演算手段２０ｄ、多項式開示手段２０ｅ、多項式取得手段２０ｆ、共通鍵算出手段２０ｇ、記憶手段２０ｈ、及び共通要素生成手段２０ｊは、制御手段２０ｋとの情報のやり取りが可能なように構成されており、共通多項式開示手段２０ｂ、多項式開示手段２０ｅ、及び多項式取得手段２０ｆは、ネットワーク４０を介した通信が可能なように構成されている。
【００２４】
図５は、図３に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築されるセキュリティ装置３０の処理機能を例示した機能ブロック図である。
図５に例示するように、この例のセキュリティ装置３０は、セキュリティ装置２０によって開示された多変数共通多項式を取得する共通多項式取得手段３０ｂ、整数組を生成する整数組生成手段３０ｃ、離散対数問題を構成する多項式の演算を行う多項式演算手段３０ｄ、第１の多変数多項式を共通鍵の配送相手に開示する多項式開示手段３０ｅ、セキュリティ装置２０によって演算された第２の多変数多項式を取得する多項式取得手段３０ｆ、共通鍵の算出を行う共通鍵算出手段３０ｇ、各種の情報を記憶する記憶手段３０ｈ、セキュリティ装置２０、３０で共通の自然数及び整数係数の多変数多項式を生成する共通要素生成手段３０ｊ、及びセキュリティ装置３０全体を制御する制御手段３０ｋを、処理機能として有している。
また、この例では、整数組生成手段３０ｃは、ＳＨＡ−１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段３０ｃａ、及び擬似乱数発生手段３０ｃａよって発生させた擬似乱数を用いて、所定の整数値を生成する整数値演算手段３０ｃｂを有している。
【００２５】
さらに、この例の多項式演算手段３０ｄは、共通鍵の配送相手と共用される整数係数の多変数共通多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した、該多変数多項式の演算を行う第３の演算手段である演算手段３０ｄａ、及び演算手段３０ｄａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述したイデアル集合によって剰余演算する第４の演算手段である演算手段３０ｄｂを有しており、この例の多項式演算手段３０ｇは、多項式取得手段３０ｆによって取得された第２の多変数多項式の任意の変数に、第１の整数組を加算した、該多変数多項式の演算を行う第５の演算手段である演算手段３０ｇａ、及び演算手段３０ｇａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述したイデアル集合によって剰余演算した結果を、共通鍵として出力する第６の演算手段である演算手段３０ｇｂを有している。
また、図５に例示するように、共通多項式取得手段３０ｂ、整数組生成手段３０ｃ、多項式演算手段３０ｄ、多項式開示手段３０ｅ、多項式取得手段３０ｆ、共通鍵算出手段３０ｇ、記憶手段３０ｈ、及び共通要素生成手段３０ｊは、制御手段３０ｋとの情報のやり取りが可能なように構成されており、共通多項式取得手段３０ｂ、多項式開示手段３０ｅ及び多項式取得手段３０ｆは、ネットワーク４０を介した通信が可能なように構成されている。
次に、本形態におけるセキュリティシステム１０、セキュリティ装置２０、３０の処理動作について説明する。
【００２６】
図６は、本形態におけるセキュリティシステム１０、セキュリティ装置２０、３０の処理動作の一例を説明するためのフローチャートである。なお、このフローチャートにおける実線の矢印は、セキュリティシステム１０全体における一連の処理の流れを例示したものであり、破線の矢印は、セキュリティシステム１０全体における一連の処理の流れと、セキュリティ装置２０、３０それぞれ単体での処理の流れが異なる部分について、セキュリティ装置２０、３０単体での処理の流れを例示したものである。また、ここでは、説明を容易にするため、便宜的に図６のような処理の流れにそって処理動作の説明を行うが、セキュリティ装置２０、３０それぞれが、このフローチャートの流れと異なる順序で処理を行うこととしてもよく、また、セキュリティ装置２０、３０が、平行して、同時にそれぞれの処理を行うこととしてもよい。
【００２７】
以下、このフローチャートに沿って説明を行う。
ステップＳ１：
本ステップでは、セキュリティ装置２０において多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の設定を行う。
多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の設定は、例えば、セキュリティ装置２０の共通多項式生成手段２０ａにおいて行われる。具体的には、例えば、まず、擬似乱数発生手段２０ａａにおいて擬似乱数を発生させ、次に、多項式生成手段２０ａｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、多変数多項式の整数係数を設定し、この整数係数を用いて多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の設定を行う。なお、「ｎ」は、セキュリティ装置２０、３０の共通要素生成手段２０ｊ、３０ｊでそれぞれ生成された共通の自然数である（以下、同様）。
このように設定された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、制御手段２０ｋに送られ、制御手段２０ｋは、送られた多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を、共通多項式開示手段２０ｂ及び記憶手段２０ｈに送る。記憶手段２０ｈに送られた多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、記憶手段２０ｈに記録され、共通多項式開示手段２０ｂに送られた多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、次のステップＳ２の処理に使用される。
【００２８】
ステップＳ２：
本ステップでは、ステップＳ１で設定された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を、セキュリティ装置３０に送信する。
多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の送信は、例えば、セキュリティ装置２０の共通多項式開示手段２０ｂによって行われる。具体的には、例えば、セキュリティ装置２０からセキュリティ装置３０宛の電子メールに、この多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を提示し、或いは、セキュリティ装置３０が閲覧可能なインターネット上のホームページに、この多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報をアップロードすることによって行われる。
このように多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の送信が行われると、次に、ステップＳ３の処理に移る。
【００２９】
ステップＳ３：
本ステップでは、ステップＳ２でセキュリティ装置２０から送信された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）をセキュリティ装置３０において受信する。
多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の受信は、例えば、セキュリティ装置３０の共通多項式取得手段３０ｂにおいて行われる。具体的には、例えば、セキュリティ装置３０が、インターネット上のメールサーバにアクセスし、セキュリティ装置２０から送られたセキュリティ装置３０宛の電子メールを受け取ることにより、または、多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
このように受信された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、制御手段３０ｋに送られ、制御手段３０ｋは、送られた多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を記憶手段３０ｈに送る。記憶手段３０ｈに送られた多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、記憶手段３０ｈに記憶され、次のステップＳ４の処理に移る。
【００３０】
ステップＳ４：
本ステップでは、セキュリティ装置２０において整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）の設定を行う。
整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）の設定は、例えば、セキュリティ装置２０の整数組生成手段２０ｃによって行われる。具体的には、例えば、まず、擬似乱数発生手段２０ｃａにおいて擬似乱数を発生させ、次に、整数値演算手段２０ｃｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、所定の整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を設定する。
設定された整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を特定するための情報は、例えば、制御手段２０ｋに送られ、制御手段２０ｋは、送られた整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を特定するための情報を、多項式演算手段２０ｄ及び記憶手段２０ｈに送る。記憶手段２０ｈに送られた整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を特定するための情報は、例えば、記憶手段２０ｈに記憶され、多項式演算手段２０ｄに送られた整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を特定するための情報は、ステップＳ５の処理に使用される。
【００３１】
ステップＳ５：
本ステップでは、多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の演算を行う。
多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の演算は、例えば、セキュリティ装置２０の多項式演算手段２０ｄにおいて行われる。多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の演算の演算を行う場合、例えば、まず、制御手段２０ｋは、ステップＳ１において記憶手段２０ｈに記憶された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を読み込み、その情報を多項式演算手段２０ｄに送る。この情報が多項式演算手段２０ｄに送られると、例えば、演算手段２０ｄａは、この多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、整数組（ｓ１，ｓ２，…，ｓｎ）を加算した該多変数共通多項式（ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ））の演算を行う。具体的には、例えば、前述した一般式Σｐｓｐ（１／ｐ！）（∂／∂ｘ）ｐａ（ｘ１，ｘ２，…，ｘｎ）（以下、単に「一般式」という。）を用いて行う。
【００３２】
次に、例えば、演算手段２０ｄｂにおいて、この演算手段２０ｄａによって行われた演算の結果に対し、整数ｓ０を指数とする指数演算を行い、該演算結果を、前述したイデアル集合Ｉによって剰余演算する（ｂ（ｘ１，ｘ２，…，ｘｎ）＝ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）。なお、前述のように、このイデアル集合Ｉの生成には、例えば、セキュリティ装置２０、３０で共通する整数係数の多変数多項式ｆ（ｘ１，ｘ２，…，ｘｎ）が使用されるが、この多変数多項式ｆ（ｘ１，ｘ２，…，ｘｎ）は、共通要素生成手段２０ｊにおいて生成されるものである（後述するステップＳ１２の処理においても同様）。また、ここで、このようなイデアル集合Ｉによって剰余演算を行う理由については後述する。
この演算結果である多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、制御手段２０ｋに送られ、制御手段２０ｋは、送られた多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を、多項式開示手段２０ｅに送る。多項式開示手段２０ｅにこの情報が送られると、次に、ステップＳ６の処理に移る。
【００３３】
ステップＳ６：
本ステップでは、演算手段２０ｄｂによって演算された多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を、セキュリティ装置３０に送信する。
多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の送信は、例えば、セキュリティ装置２０の多項式開示手段２０ｅによって行われるが、この際、整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）は開示されず、この整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）をセキュリティ装置２０側で秘密に保った状態で行われる。具体的には、例えば、セキュリティ装置２０からセキュリティ装置３０宛の電子メールに、この多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を、整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を特定するための情報を開示することなく提示し、或いは、セキュリティ装置３０が閲覧可能なインターネット上のホームページに、この多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を、整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を特定するための情報を開示することなくアップロードすることによって行われる。
このように多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の送信が行われると、次に、ステップＳ７の処理に移る。
【００３４】
ステップＳ７：
本ステップでは、ステップＳ６でセキュリティ装置２０から送信された多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）をセキュリティ装置３０において受信する。
多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の受信は、例えば、セキュリティ装置３０の多項式取得手段３０ｆにおいて行われる。具体的には、例えば、セキュリティ装置３０が、インターネット上のメールサーバにアクセスし、セキュリティ装置２０から送られたセキュリティ装置３０宛の電子メールを受け取ることにより、または、多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
このように受信された多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、制御手段３０ｋに送られ、制御手段３０ｋは、送られた多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を記憶手段３０ｈに送る。記憶手段３０ｈに送られた多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、記憶手段３０ｈに記憶され、次のステップＳ８の処理に移る。
【００３５】
ステップＳ８：
本ステップでは、セキュリティ装置３０において整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）の設定を行う。
整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）の設定は、例えば、セキュリティ装置３０の整数組生成手段３０ｃによって行われる。具体的には、例えば、まず、擬似乱数発生手段３０ｃａにおいて擬似乱数を発生させ、次に、整数値演算手段３０ｃｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、所定の整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を設定する。
設定された整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報は、例えば、制御手段３０ｋに送られ、制御手段３０ｋは、送られた整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報を、多項式演算手段３０ｄ及び記憶手段３０ｈに送る。記憶手段３０ｈに送られた整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報は、例えば、記憶手段３０ｈに記憶され、多項式演算手段３０ｄに送られた整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報は、ステップＳ９の処理に使用される。
【００３６】
ステップＳ９：
本ステップでは、多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の演算を行う。
多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の演算は、例えば、セキュリティ装置３０の多項式演算手段３０ｄにおいて行われる。多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の演算の演算を行う場合、例えば、まず、制御手段３０ｋは、ステップＳ３において記憶手段３０ｈに記憶された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を読み込み、その情報を多項式演算手段３０ｄに送る。この情報が多項式演算手段３０ｄに送られると、例えば、演算手段３０ｄａは、この多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、整数組（ｔ１，ｔ２，…，ｔｎ）を加算した該多変数共通多項式（ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ））の演算を行う。この演算は、具体的には、例えば、前述した一般式を用いて行う。
【００３７】
次に、例えば、演算手段３０ｄｂにおいて、この演算手段３０ｄａによって行われた演算の結果に対し、整数ｔ０を指数とする指数演算を行い、該演算結果を、前述したイデアル集合Ｉによって剰余演算する（ｃ（ｘ１，ｘ２，…，ｘｎ）＝ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）。なお、前述のように、このイデアル集合Ｉの生成には、例えば、セキュリティ装置２０、３０で共通する整数係数の多変数多項式ｆ（ｘ１，ｘ２，…，ｘｎ）が使用されるが、この多変数多項式ｆ（ｘ１，ｘ２，…，ｘｎ）は、共通要素生成手段３０ｊにおいて生成されるものである（後述するステップＳ１３の処理においても同様）。また、ここで、このようなイデアル集合Ｉによって剰余演算を行う理由については後述する。
この演算結果である多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、制御手段３０ｋに送られ、制御手段３０ｋは、送られた多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を、多項式開示手段３０ｅに送る。多項式開示手段３０ｅにこの情報が送られると、次に、ステップＳ１０の処理に移る。
【００３８】
ステップＳ１０：
本ステップでは、演算手段３０ｄｂによって演算された多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を、セキュリティ装置２０に送信する。
多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の送信は、例えば、セキュリティ装置３０の多項式開示手段３０ｆによって行われるが、この際、整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）は開示されず、この整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）をセキュリティ装置３０側で秘密に保った状態で行われる。具体的には、例えば、セキュリティ装置３０からセキュリティ装置２０宛の電子メールに、この多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を、整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報を開示することなく提示し、或いは、セキュリティ装置２０が閲覧可能なインターネット上のホームページに、この多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を、整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報を開示することなくアップロードすることによって行われる。
このように多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の送信が行われると、次に、ステップＳ１１の処理に移る。
【００３９】
ステップＳ１１：
本ステップでは、ステップＳ１０でセキュリティ装置３０から送信された多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）をセキュリティ装置２０において受信する。
多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の受信は、例えば、セキュリティ装置２０の多項式取得手段２０ｆにおいて行われる。具体的には、例えば、セキュリティ装置２０が、インターネット上のメールサーバにアクセスし、セキュリティ装置３０から送られたセキュリティ装置２０宛の電子メールを受け取ることにより、または、多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
このように受信された多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、制御手段２０ｋに送られ、制御手段２０ｋは、送られた多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を記憶手段２０ｈに送る。記憶手段２０ｈに送られた多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、記憶手段２０ｈに記憶され、次のステップＳ１２の処理に移る。
【００４０】
ステップＳ１２：
本ステップでは、セキュリティ装置２０において、共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）の算出を行う。
共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）の算出は、例えば、セキュリティ装置２０の共通鍵算出手段２０ｇにおいて行われる。共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）の算出を行う場合、例えば、まず、制御手段２０ｋは、ステップＳ１１において記憶手段２０ｈに記憶された多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を読み込み、その情報を共通鍵算出手段２０ｇに送る。この情報が共通鍵算出手段２０ｇに送られると、例えば、この共通鍵算出手段２０ｇは、演算手段２０ｇａによって、この多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の変数に、整数組（ｓ１，ｓ２，…，ｓｎ）を加算した該多変数多項式の演算（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ））を行い、演算手段２０ｇｂによって、この演算結果に対し、整数ｓ０を指数とする指数演算を行い、該演算結果に対し、前述したイデアル集合によって剰余演算した結果（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０）を共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）として出力する。なお、この場合も、ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）の演算は、例えば、前述した一般式を用いて行う。
【００４１】
ステップＳ１３：
本ステップでは、セキュリティ装置３０において、共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）の算出を行う。
共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）の算出は、例えば、セキュリティ装置３０の共通鍵算出手段３０ｇにおいて行われる。共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）の算出を行う場合、例えば、まず、制御手段３０ｋは、ステップＳ７において記憶手段３０ｈに記憶された多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を読み込み、その情報を共通鍵算出手段３０ｇに送る。この情報が共通鍵算出手段３０ｇに送られると、例えば、この共通鍵算出手段３０ｇは、演算手段３０ｇａによって、この多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の変数に、整数組（ｔ１，ｔ２，…，ｔｎ）を加算した該多変数多項式の演算（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ））を行い、演算手段３０ｇｂによって、この演算結果に対し、整数ｔ０を指数とする指数演算を行い、該演算結果に対し、前述したイデアル集合によって剰余演算した結果（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０）を共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）として出力する。なお、この場合も、ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）の演算は、例えば、前述した一般式を用いて行う。
【００４２】
以上の処理により、セキュリティ装置２０、３０間において共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）の配送が行われたことになるが、次に、このセキュリティ装置２０、３０それぞれで算出された共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）の同一性、及び上述のステップＳ５、Ｓ９、Ｓ１２、Ｓ１３の処理において、前述のイデアル集合Ｉによって剰余演算を行った理由について説明する。
前述のように、イデアル集合Ｉは、イデアルであって、該イデアルに対して行われた、整数係数の多変数多項式の任意の変数について任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなる集合である。この場合、この整数係数の多変数多項式をｇ（ｘ１，ｘ２，…，ｘｎ）、任意の整数組を（ｄ１，ｄ２，…，ｄｎ）とすると、このイデアル集合Ｉ  に対し、ｇ（ｘ１，ｘ２，…，ｘｎ）∈Ｉならばｇ（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）∈Ｉであるという関係が満たされることとなる。
【００４３】
ここで、ｈ（ｘ１，ｘ２，…，ｘｎ）≡ｒ（ｘ１，ｘ２，…，ｘｎ）ｍｏｄＩとする。つまり、ｇ（ｘ１，ｘ２，…，ｘｎ）∈Ｉとｐ（ｘ１，ｘ２，…，ｘｎ）∈Ｚ［ｘ１，ｘ２，…，ｘｎ］が存在して、ｈ（ｘ１，ｘ２，…，ｘｎ）＝ｐ（ｘ１，ｘ２，…，ｘｎ）・ｇ（ｘ１，ｘ２，…，ｘｎ）＋ｒ（ｘ１，ｘ２，…，ｘｎ）と書けるとする。なお、ここで、Ｚ［ｘ１，ｘ２，…，ｘｎ］は、整数係数の多変数多項式全体の集合を表す。この式の両辺について、（ｘ１，ｘ２，…，ｘｎ）を（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）で置き換えると、ｈ（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）＝ｐ（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）・ｇ（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）＋ｒ（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）となるが、上述のように、ｇ（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）∈Ｉが満たされるため、ｈ（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）≡ｒ（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）ｍｏｄＩという関係も成立することになる。すなわち、前述のようなイデアル集合Ｉである限り、ｈ（ｘ１，ｘ２，…，ｘｎ）≡ｒ（ｘ１，ｘ２，…，ｘｎ）ｍｏｄＩという関係が成立すれば、必ず、ｈ（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）≡ｒ（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）ｍｏｄＩという関係も成立することになる。これは、このイデアル集合Ｉの代わりに、このイデアル集合Ｉでない集合で剰余演算を行った場合には、必ずしも成立しない関係である。
さらに、このように、ｈ（ｘ１，ｘ２，…，ｘｎ）≡ｒ（ｘ１，ｘ２，…，ｘｎ）ｍｏｄＩという関係が成立すれば、必ず、ｈ（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）≡ｒ（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）ｍｏｄＩという関係も成立するということが言える場合、任意の整数組（ｄ１，ｄ２，…，ｄｎ）と任意の多変数多項式ｈ（ｘ１，ｘ２，…，ｘｎ）について、Ｉでの剰余演算を行った後に、（ｘ１，ｘ２，…，ｘｎ）を（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）に置き換えた多項式と、（ｘ１，ｘ２，…，ｘｎ）を（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）に置き換えた後に、Ｉでの剰余演算を行った多項式とは同一となることが言える。
【００４４】
そして、任意の整数組（ｄ１，ｄ２，…，ｄｎ）と任意の多変数多項式ｈ（ｘ１，ｘ２，…，ｘｎ）について、Ｉでの剰余演算を行った後に、（ｘ１，ｘ２，…，ｘｎ）を（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）に置き換えた多項式と、（ｘ１，ｘ２，…，ｘｎ）を（ｘ１＋ｄ１，ｘ２＋ｄ２，…，ｘｎ＋ｄｎ）に置き換えた後に、Ｉでの剰余演算を行った多項式とは同一となることが言える場合、例えば、セキュリティ装置２０において、ｂ（ｘ１，ｘ２，…，ｘｎ）を算出するためにＩでの剰余演算を行った後に、セキュリティ装置３０において、ｋ（ｘ１，ｘ２，…，ｘｎ）を算出するために（ｘ１，ｘ２，…，ｘｎ）を（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）に置き換えた多項式の演算結果と、セキュリティ装置３０において、ｃ（ｘ１，ｘ２，…，ｘｎ）を算出するために（ｘ１，ｘ２，…，ｘｎ）を（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）に置き換えた後に、セキュリティ装置３０において、ｋ（ｘ１，ｘ２，…，ｘｎ）を算出するためにＩで剰余演算を行った結果とは等しくなることが言える（交換可能）。これは、（ｓ１，ｓ２，…，ｓｎ）についても同様である。
一方、指数演算に関して交換可能なことは、従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式と同様、明らかである。
以上より、前述したようなイデアル集合Ｉである場合、セキュリティ装置２０、３０それぞれで算出された共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）は同一であることが言える。
【００４５】
このように、この形態の例では、演算手段２０ｄａ、３０ｄａによって、共通鍵の配送相手と共用される整数係数の多変数共通多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した、該多変数多項式の演算を行い（ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）、ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ））、演算手段２０ｄｂ、３０ｄｂによって、演算手段２０ｄａ、３０ｄａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述したイデアル集合によって剰余演算し（ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ、ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）、多項式開示手段２０ｅ、３０ｅによって、演算手段２０ｄｂ、３０ｄｂによる演算結果である第１の多変数多項式（ｂ（ｘ１，ｘ２，…，ｘｎ）、ｃ（ｘ１，ｘ２，…，ｘｎ））を、共通鍵の配送相手に開示する。そして、多項式取得手段２０ｆ、３０ｆにおいて、共通鍵の配送相手によって演算された第２の多変数多項式（ｃ（ｘ１，ｘ２，…，ｘｎ）、ｂ（ｘ１，ｘ２，…，ｘｎ））を取得し、演算手段２０ｇａ、３０ｇａによって、多項式取得手段２０ｆ、３０ｆによって取得された第２の多変数多項式の任意の変数に、第１の整数組をした、該多変数多項式の演算を行い（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）、ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ））、演算手段２０ｇｂ、３０ｇｂによって、演算手段２０ｇａ、３０ｇａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述のイデアル集合によって剰余演算した結果（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ、ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）を、共通鍵として出力することとした。
【００４６】
前述のように、演算手段２０ｄａ、２０ｇａ、３０ｄａ、３０ｇａにおいて行われる演算に必要な四則演算の回数は、秘密パラメータ（（ｓ１，ｓ２，…，ｓｎ）等）の大きさに依存せず、この秘密パラメータの大きさを大きくした場合であっても、鍵配送時において、この演算手段２０ｄａ、２０ｇａ、３０ｄａ、３０ｇａにおいて行われる演算に起因した四則演算の回数が増大することはない。結果、秘密パラメータの大きさに依存して計算量が増大する従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式に比べ、大幅に利便性が向上する。
また、この形態の例では、演算手段２０ｄａ、２０ｇａ、３０ｄａ、３０ｇａによって行われる、整数係数の多変数多項式の任意の変数に、第１の整数組を加算した該多変数多項式の演算と、演算手段２０ｄｂ、２０ｇｂ、３０ｄｂ、３０ｇｂによって行われる、第１の整数を指数とする指数演算を行い、該演算結果を前述のイデアル集合によって剰余演算する演算と、を組み合わせることによって離散対数問題を構成し、この離散対数問題を交換することにより、共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）の配送を行うこととしたため、指数演算のみによって構成される離散対数問題によって共通鍵の配送を行っていた従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式に比べ、第三者がこの共通鍵の解読を行うことが困難となり、結果、共通鍵に対する安全性が大幅に向上する。
【００４７】
さらに、この形態の例では、イデアル集合を、整数係数の多項式がなす環のイデアルであって、δｉを任意の多変数多項式ｇ（ｘ１，ｘ２，…，ｘｎ）に対して多変数多項式ｇ（ｘ１，ｘ２，…，ｘｉ，…，ｘｎ）−ｇ（ｘ１，ｘ２，…，ｘｉ−１，…，ｘｎ）を対応させる作用素とし、ｄｅｇｉｆ（ｘ１，ｘ２，…，ｘｎ）をｆ（ｘ１，ｘ２，…，ｘｎ）のｘｉについての次数とし、（ｐ１，ｐ２，…，ｐｎ）∈Ｎｎとした場合における、｛Σ（ｐ１，ｐ２，…，ｐｎ）（Πｉ＝１ｎδｉｐｉ）ｆ（ｘ１，ｘ２，…，ｘｎ）｝によって生成されるイデアルであることとしたため、前述のように、セキュリティ装置２０、３０のそれぞれで算出された共通鍵ｋ（ｘ１，ｘ２，…，ｘｎ）が同一となり、本形態における鍵配送が実質的に可能となる。
また、この形態の例では、演算手段２０ｄａ、２０ｇａ、３０ｄａ、３０ｇａにおいて、多変数多項式ａ（ｘ１，ｘ２，…，ｘｎ）に対し、第１の整数組を（ｓ１，ｓ２，…，ｓｎ）とし、ｐ＝（ｐ１，ｐ２，…，ｐｎ）∈Ｎｎとし、ｓｐ＝ｓ１ｐ１ｓ２ｐ２…ｓｎｐｎとし、ｐ！＝ｐ１！ｐ２！…，ｐｎ！とし、（∂／∂ｘ）ｐ＝（∂／∂ｘ１）ｐ１（∂／∂ｘ２）ｐ２…（∂／∂ｘｎ）ｐｎとした場合における、Σｐｓｐ（１／ｐ！）（∂／∂ｘ）ｐａ（ｘ１，ｘ２，…，ｘｎ）の演算を行うこととしたため、演算手段２０ｄａ、２０ｇａ、３０ｄａ、３０ｇａにおいて行われる演算に必要な四則演算の回数が、秘密パラメータ（（ｓ１，ｓ２，…，ｓｎ）や（ｔ１，ｔ２，…，ｔｎ））の大きさに依存することはない。したがって、この秘密パラメータの大きさを大きくした場合であっても、鍵配送時において、この演算手段２０ｄａ、２０ｇａ、３０ｄａ、３０ｇａにおいて行われる演算に起因した四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式に比べ、大幅に利便性が向上する。
【００４８】
なお、この発明は上述の実施の形態に限定されるものではない。例えば、この形態の例では、第１の演算手段である演算手段２０ｄａ等において、多変数多項式（ａ（ｘ１，ｘ２，…，ｘｎ）等）の全ての変数に、整数組（（ｓ１，ｓ２，…，ｓｎ）等）を加算した当該多変数多項式の演算を行う場合を例示したが、多変数多項式の一部の変数（例えば、ａ（ｘ１，ｘ２，…，ｘｎ）における（ｘ１，ｘ２，…，ｘｎ）のうちの一部）のみに整数組を加算した当該多変数多項式の演算を行うこととしてもよい。
また、この形態の例では、セキュリティ装置２０で生成した多変数共通多項式を、セキュリティ装置２０からセキュリティ装置３０へ送信する構成としたが、セキュリティ装置３０で生成した多変数共通多項式をセキュリティ装置３０からセキュリティ装置２０へ送信する構成としてもよく、さらに、セキュリティ装置２０、３０双方で、セキュリティ装置２０、３０に共通する多変数共通多項式を生成する構成としてもよい。
【００４９】
さらに、この形態では、コンピュータ上で所定のプログラムを実行させることにより、セキュリティ装置２０、３０を構成することとしたが、これらの処理内容の少なくとも一部を電子回路によってハードウェア的に実現することとしてもよい。
次に、この発明における第２の実施の形態について説明する。
ここでも、まず、本形態の概略について説明を行い、その後、本形態の詳細について説明を行っていく。
【００５０】
図７は、本形態におけるセキュリティシステム１００の概略を説明するための図である。
図７に例示するように、セキュリティシステム１００は、セキュリティ装置１０２、１０３によって構成されており、セキュリティ装置１０３からセキュリティ装置１０２に暗号文Ｃを送信し、セキュリティ装置１０２が、送られた暗号文Ｃを復号するものとする。
この例の場合、セキュリティ装置１０２、１０３は、それぞれ、整数係数の多変数多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した、該多変数多項式の演算を行う演算手段１０２ａ、１０３ａ、及び演算手段１０２ａ、１０３ａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述したイデアル集合によって剰余演算する演算手段１０２ｂ、１０３ｂを有している。
【００５１】
この形態におけるセキュリティシステム１００において、暗号化・復号を行う場合、例えば、まず、セキュリティ装置１０２は、整数係数の多変数多項式である多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を生成し、生成した多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）をセキュリティ装置１０３に送信する。そして、例えば次に、セキュリティ装置１０２は、秘密鍵となる整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を定め、この整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）及び多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を用い、演算手段１０２ａにおいて、多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、整数組（ｓ１，ｓ２，…，ｓｎ）を加算した該多変数多項式の演算を行い、この演算の結果に対し、演算手段１０２ｂにおいて、整数（ｓ０）を指数とする指数演算を行い、該演算結果を、前述したイデアル集合（Ｉ）によって剰余演算する（ｂ（ｘ１，ｘ２，…，ｘｎ）＝ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）。この演算結果である多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）は、例えば、整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）が秘密に保たれた状態で、公開鍵としてセキュリティ装置１０３に送信される。
【００５２】
一方、セキュリティ装置１０３は、例えば、整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を定め、この整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）、及びセキュリティ装置１０２から送信された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を用い、演算手段１０３ａにおいて、多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、整数組（ｔ１，ｔ２，…，ｔｎ）を加算した該多変数多項式の演算を行い、この演算の結果に対し、演算手段１０３ｂにおいて、整数（ｔ０）を指数とする指数演算を行い、該演算結果を、前述したイデアル集合（Ｉ）によって剰余演算する（ｃ（ｘ１，ｘ２，…，ｘｎ）＝ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）。
また、暗号化する平文Ｍが、Ｍ∈［０，１］ｌである場合、セキュリティ装置１０３は、例えば、演算手段１０３ａにおいて、送信された多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、整数組（ｔ１，ｔ２，…，ｔｎ）を加算した該多変数多項式の演算を行い、この演算の結果に対し、演算手段１０３ｂにおいて、整数（ｔ０）を指数とする指数演算を行い、該演算結果を、前述したイデアル集合（Ｉ）によって剰余演算する（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）。その後、この演算結果に対し、ハッシュ関数Ｈ（演算結果の値域が十分大きい集合となることが好ましく、この値域が、例えば、２８０項以上程度の元からなる集合であるものがより好ましい）を作用させ、Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）∈［０，１］ｌを得る。そして、このＨ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）と平文Ｍとの排他的論理和（Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍ）を暗号文として演算する。なお、図７及びこの形態の説明において、「Ａ（＋）Ｂ」は、ＡとＢとの排他的論理和を意味するものとする。
【００５３】
その後、このように演算されたｃ（ｘ１，ｘ２，…，ｘｎ）と、Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍとは、例えば、整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）が秘密に保たれた状態で、暗号文Ｃ＝（ｃ（ｘ１，ｘ２，…，ｘｎ），Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍ）として、セキュリティ装置１０２に送信される。
暗号文Ｃが送信されたセキュリティ装置１０２は、例えば、演算手段１０２ａによって、暗号文Ｃを構成する多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、整数組（ｓ１，ｓ２，…，ｓｎ）を加算した該多変数多項式の演算を行い、この演算の結果に対し、演算手段１０２ｂにおいて、整数（ｓ０）を指数とする指数演算を行い、該演算結果を、前述したイデアル集合（Ｉ）によって剰余演算する（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）。そして、この演算結果に対し、セキュリティ装置１０３で用いたものと同じハッシュ関数Ｈを作用させ、Ｈ（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）∈［０，１］ｌを得る。その後、このように得られたＨ（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）と、暗号文Ｃを構成するＨ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍとの排他的論理和を演算する（Ｈ（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）（＋）Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍ）。ここで、前述した第１の実施の形態の場合と同様、ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩの演算結果と、ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩの演算結果とは同一となっているため、これらに対して同一のハッシュ関数を作用させた結果であるＨ（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）及びＨ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）も同一となっている。そのため、Ｈ（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）（＋）Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍの演算結果はＭとなり、これにより、平文Ｍが復号されたことになる。
【００５４】
ここで、この例では、上述した演算手段１０２ａ、１０３ａにおいて行われる演算（ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）、ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）、ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）、ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ））は、前述した一般式によって行うものとする。そのため、これらの演算に必要な四則演算の回数は、秘密パラメータ（（ｓ１，ｓ２，…，ｓｎ）や（ｔ１，ｔ２，…，ｔｎ））の大きさに依存しない。したがって、この秘密パラメータの大きさを大きくした場合であっても、公開鍵生成時、暗号文生成時、及び復号時において、この演算手段１０２ａ、１０３ａにおいて行われる演算に起因した四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式を応用した公開鍵暗号方式に比べ、大幅に利便性が向上する。
【００５５】
また、この形態では、演算手段１０２ａ、１０３ａによって行われる、整数係数の多変数多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した該多変数多項式の演算と、演算手段１０２ｂ、１０３ｂによって行われる、第１の整数を指数とする指数演算を行い、該演算結果を前述のイデアル集合によって剰余演算する演算と、を組み合わせることによって離散対数問題を構成し、この離散対数問題を用いて暗号化及び復号を行うため、単一の離散対数問題を用いて暗号化及び復号を行っていた従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式を応用した公開鍵暗号方式に比べ、暗号に対する安全性が大幅に向上する。特に、１変数多項式ではなく、多変数多項式の任意の変数に、概変数ごとに独立した整数組を加算する演算によって離散対数問題を生成する本形態の例では、その効果はより大きなものとなる。
【００５６】
次に、本形態の詳細について説明を行う。
図８は、本形態におけるセキュリティシステム１１０の全体構成を例示した図である。
図８に例示するように、セキュリティシステム１１０は、例えば、公開鍵暗号方式によって、平文の暗号化及び復号を行うセキュリティ装置１２０、１３０、及びセキュリティ装置１２０、１３０相互を通信可能なように接続するネットワーク１４０を有しており、このセキュリティ装置１２０、１３０は、ネットワーク１４０を介し、相互に情報のやり取りが可能なように、有線又は無線によって電気的に接続され、或いは接続可能な状態となっている。なお、この全体構成についての詳細は、例えば、第１の実施の形態で説明したものと同様であり、また、セキュリティ装置１２０、１３０のハードウェア構成は、例えば、第１の実施の形態におけるセキュリティ装置２０のハードウェア構成（図３）と同様のものとする。
【００５７】
図９は、図３に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築されるセキュリティ装置１２０の処理機能を例示した機能ブロック図である。
図９に例示するように、この例では、セキュリティ装置１２０は、通信相手であるセキュリティ装置１３０と共用される整数係数の多変数共通多項式を生成する共通多項式生成手段１２０ａ、共通多項式生成手段１２０ａによって生成された多変数共通多項式をセキュリティ装置１３０に開示する共通多項式開示手段１２０ｂ、発生させた乱数を用い、整数組を生成する整数組生成手段１２０ｃ、離散対数問題を構成することとなる多変数多項式を演算する多項式演算手段１２０ｄ、多項式演算手段１２０ｄによって演算された多変数多項式を公開鍵として公開する公開鍵公開手段１２０ｅ、セキュリティ装置１３０によって演算された多変数多項式と暗号文とを取得する暗号文取得手段１２０ｆと、暗号文取得手段１２０ｆによって取得された多変数多項式と暗号文とから、平文を復号する復号手段１２０ｇ、各種情報を記憶する記憶手段１２０ｈ、セキュリティ装置１２０、１３０で共通の自然数、及び整数係数の多変数多項式を生成する共通要素生成手段１２０ｊ、及びセキュリティ装置１２０全体を制御する制御手段１２０ｋを処理機能として有している。
【００５８】
また、この例では、共通多項式生成手段１２０ａは、ＳＨＡ−１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段１２０ａａ、及び擬似乱数発生手段１２０ａａによって発生させた擬似乱数を用いて所定の整数値を生成し、生成した整数値を係数とする多変数共通多項式を生成する多項式生成手段１２０ａｂを有しており、整数組生成手段１２０ｃは、ＳＨＡ−１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段１２０ｃａ、及び擬似乱数発生手段１２０ｃａよって発生させた擬似乱数を用いて、所定の整数値を生成する整数値演算手段１２０ｃｂを有している。
【００５９】
さらに、この例の多項式演算手段１２０ｄは、通信相手と共用される整数係数の多変数多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した、該多変数多項式の演算を行う第３の演算手段である演算手段１２０ｄａ、及び演算手段１２０ｄａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述したイデアル集合によって剰余演算する第４の演算手段である演算手段１２０ｄｂを有している。また、この例の復号手段１２０ｇは、暗号文取得手段１２０ｆによって取得された第２の多変数多項式の任意の変数に、第１の整数組を加算した、該多変数多項式の演算を行う第１の第５の演算手段である演算手段１２０ｇａ、演算手段１２０ｇａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述したイデアル集合によって剰余演算する第６の演算手段である演算手段１２０ｇｂ、セキュリティ装置１３０と共通のハッシュ関数Ｈの演算を行うハッシュ関数演算手段１２０ｇｃ、及び演算手段１２０ｇｂによる演算結果と、暗号文と、の排他的論理和を演算する排他的論理和演算手段１２０ｇｄを有している。
【００６０】
なお、この例では、ハッシュ関数Ｈは、例えば、Ｚ（ｘ１，ｘ２，…，ｘｎ）／Ｉ１→［０，１］ｌの演算を行う関数である。ここで、Ｚ（ｘ１，ｘ２，…，ｘｎ）／Ｉ１とは、整数係数の多変数多項式環Ｚ（ｘ１，ｘ２，…，ｘｎ）とそのイデアルＩ１とが与えられ、ｐ，ｑ∈Ｚ（ｘ１，ｘ２，…，ｘｎ）についてｐ−ｑ∈Ｉ１を満たす場合に、このｐとｑとを同一の類とみなしてＺ（ｘ１，ｘ２，…，ｘｎ）の元を類別し、その類別された類ひとつひとつを新たに元とみなした場合に作られる集合（Ｚ（ｘ１，ｘ２，…，ｘｎ）のＩによる剰余環）を意味する。また、前述のように、ハッシュ関数Ｈは、その演算結果の値域が十分大きい集合となることが望ましいが、このようなハッシュ関数Ｈの構成は、例えば、ブックバーガーのアルゴリズム等を用い、Ｚ（ｘ１，ｘ２，…，ｘｎ）のイデアルＩ１についてグレブナー基底を１つ定め、このグレブナー基底により、Ｚ（ｘ１，ｘ２，…，ｘｎ）／Ｉ１のそれぞれの類において、その類を代表する多項式を定めることによって行う。
【００６１】
また、図９に例示するように、共通多項式生成手段１２０ａ、共通多項式開示手段１２０ｂ、整数組生成手段１２０ｃ、多項式演算手段１２０ｄ、公開鍵公開手段１２０ｅ、暗号文取得手段１２０ｆ、復号手段１２０ｇ、記憶手段１２０ｈ、共通要素生成手段１２０ｊは、制御手段１２０ｋとの情報のやり取りが可能なように構成されており、共通多項式開示手段１２０ｂ、公開鍵公開手段１２０ｅ及び暗号文取得手段１２０ｆは、ネットワーク１４０を介した通信が可能なように構成されている。
【００６２】
図１０は、図３に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築されるセキュリティ装置１３０の処理機能を例示した機能ブロック図である。
図１０に例示するように、この例のセキュリティ装置１３０は、セキュリティ装置１２０によって開示された多変数共通多項式を取得する共通多項式取得手段１３０ｂ、発生させた乱数を用い、整数組を生成する整数組生成手段１３０ｃ、離散対数問題を構成する多変数多項式の演算を行う多項式演算手段１３０ｄ、セキュリティ装置１２０によって公開された多変数多項式を公開鍵として取得する公開鍵取得手段１３０ｅ、公開鍵取得手段１３０ｅによって取得された多変数多項式を用い、通信内容である平文を暗号化する暗号文生成手段１３０ｆ、暗号文生成手段１３０ｆによって生成された暗号文と、多項式演算手段１３０ｄによって生成された多変数多項式とを開示する暗号文開示手段１３０ｇ、各種情報を記憶する記憶手段１３０ｈ、セキュリティ装置１２０、１３０で共通の自然数、及び整数係数の多変数多項式を生成する共通要素生成手段１３０ｊ、及びセキュリティ装置１３０全体を制御する制御手段１３０ｋを有している。
【００６３】
また、この例の整数組生成手段１３０ｃは、ＳＨＡ−１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる擬似乱数発生手段１３０ｃａ、及び擬似乱数発生手段１３０ｃａよって発生させた擬似乱数を用いて、所定の整数値を生成する整数値演算手段１３０ｃｂを有している。
さらに、この例の多項式演算手段１３０ｄは、通信相手と共用される整数係数の多変数共通多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した、該多変数多項式の演算を行う第５の演算手段である演算手段１３０ｄａ、及び演算手段１３０ｄａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述したイデアル集合によって剰余演算する第６の演算手段である演算手段１３０ｄｂを有している。またさらに、この例の暗号文生成手段１３０ｆは、公開鍵取得手段１３０ｅによって取得された第１の多変数多項式の任意の変数に、第１の整数組を加算した、該多変数多項式の演算を行う第３の演算手段である演算手段１３０ｆａ、演算手段１３０ｆａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述したイデアル集合によって剰余演算する第４の演算手段である演算手段１３０ｆｂ、セキュリティ装置１２０と共通のハッシュ関数Ｈの演算を行うハッシュ関数演算手段１３０ｆｃ、及び演算手段１３０ｆｂによる演算結果と通信内容である平文との排他的論理和を暗号文として演算する排他的論理和演算手段１３０ｆｄを有している。
【００６４】
また、図１０に例示するように、共通多項式取得手段１３０ｂ、整数組生成手段１３０ｃ、多項式演算手段１３０ｄ、公開鍵取得手段１３０ｅ、暗号文生成手段１３０ｆ、暗号文開示手段１３０ｇ、記憶手段１３０ｈ、共通要素生成手段１３０ｊは、制御手段１３０ｋとの情報のやり取りが可能なように構成されており、共通多項式取得手段１３０ｂ、公開鍵取得手段１３０ｅ及び暗号文開示手段１３０ｇは、ネットワーク１４０を介した通信が可能なように構成されている。
次に、本形態におけるセキュリティシステム１１０、セキュリティ装置１２０、１３０の処理動作について説明する。
【００６５】
図１１は、本形態におけるセキュリティシステム１１０、セキュリティ装置１２０、１３０の処理動作の一例を説明するためのフローチャートである。このフローチャートにおける実線の矢印は、セキュリティシステム１１０全体における一連の処理の流れを例示したものであり、破線の矢印は、セキュリティシステム１１０全体における一連の処理の流れと、セキュリティ装置１２０、１３０それぞれ単体での処理の流れが異なる部分について、セキュリティ装置１２０、１３０単体での処理の流れを例示したものである。なお、ここでは、説明を容易にするため、便宜的に図１１のような処理の流れにそって処理動作の説明を行うが、セキュリティ装置１２０、１３０それぞれが、このフローチャートの流れと異なる順序で処理を行うこととしてもよく、また、セキュリティ装置１２０、１３０が、平行して、同時にそれぞれの処理を行うこととしてもよい。
以下、このフローチャートに沿って説明を行う。
【００６６】
ステップＳ２０：
本ステップでは、セキュリティ装置１２０において多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の設定を行う。
多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の設定は、例えば、セキュリティ装置１２０の共通多項式生成手段１２０ａにおいて行われる。具体的には、例えば、まず、擬似乱数発生手段１２０ａａにおいて、ＳＨＡ−１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて擬似乱数を発生させ、次に、多項式生成手段１２０ａｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、多変数多項式の整数係数を設定し、この整数係数を用いて多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の設定を行う。なお、「ｎ」は、セキュリティ装置１２０、１３０の共通要素生成手段１２０ｊ、１３０ｊでそれぞれ生成された共通の自然数である（以下、同様）。
【００６７】
このように設定された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、制御手段１２０ｋに送られ、制御手段１２０ｋは、送られた多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を、共通多項式開示手段１２０ｂ及び記憶手段１２０ｈに送る。記憶手段１２０ｈに送られた多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、記憶手段１２０ｈに記録され、共通多項式開示手段１２０ｂに送られた多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、次のステップＳ２１の処理に使用される。
【００６８】
ステップＳ２１：
本ステップでは、ステップＳ２０で設定された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を、セキュリティ装置１３０に送信する。
多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の送信は、例えば、セキュリティ装置１２０の共通多項式開示手段１２０ｂによって行われる。具体的には、例えば、セキュリティ装置１２０からセキュリティ装置１３０宛の電子メールに、この多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を提示し、或いは、セキュリティ装置１３０が閲覧可能なインターネット上のホームページに、この多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報をアップロードすることによって行われる。
このように多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の送信が行われると、次に、ステップＳ２２の処理に移る。
【００６９】
ステップＳ２２：
本ステップでは、ステップＳ２１でセキュリティ装置１２０から送信された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）をセキュリティ装置１３０において受信する。
多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の受信は、例えば、セキュリティ装置１３０の共通多項式取得手段１３０ｂにおいて行われる。具体的には、例えば、セキュリティ装置１３０が、インターネット上のメールサーバにアクセスし、セキュリティ装置１２０から送られたセキュリティ装置１３０宛の電子メールを受け取ることにより、または、多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
このように受信された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、制御手段１３０ｋに送られ、制御手段１３０ｋは、送られた多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を記憶手段１３０ｈに送る。記憶手段１３０ｈに送られた多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、記憶手段１３０ｈに記憶され、次のステップＳ２３の処理に移る。
【００７０】
ステップＳ２３：
本ステップでは、セキュリティ装置１２０において整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）の設定を行う。
整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）の設定は、例えば、セキュリティ装置１２０の整数組生成手段１２０ｃによって行われる。具体的には、例えば、まず、擬似乱数発生手段１２０ｃａにおいて、ＳＨＡ−１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて擬似乱数を発生させ、次に、整数値演算手段１２０ｃｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、所定の整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を設定する。
【００７１】
設定された整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を特定するための情報は、例えば、制御手段１２０ｋに送られ、制御手段１２０ｋは、送られた整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を特定するための情報を、多項式演算手段１２０ｄ及び記憶手段１２０ｈに送る。記憶手段１２０ｈに送られた整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を特定するための情報は、例えば、記憶手段１２０ｈに記憶され、多項式演算手段１２０ｄに送られた整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を特定するための情報は、ステップＳ２４の処理に使用される。
【００７２】
ステップＳ２４：
本ステップでは、多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の演算を行う。
多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の演算は、例えば、セキュリティ装置１２０の多項式演算手段１２０ｄにおいて行われる。多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の演算の演算を行う場合、例えば、まず、制御手段１２０ｋは、ステップＳ２０において記憶手段１２０ｈに記憶された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を読み込み、その情報を多項式演算手段１２０ｄに送る。この情報が多項式演算手段１２０ｄに送られると、例えば、演算手段１２０ｄａは、この多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、整数組（ｓ１，ｓ２，…，ｓｎ）を加算した該多変数共通多項式（ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ））の演算を行う。この演算は、具体的には、例えば、前述した一般式を用いて行う。
【００７３】
次に、例えば、演算手段１２０ｄｂにおいて、この演算手段１２０ｄａによって行われた演算の結果に対し、整数ｓ０を指数とする指数演算を行い、該演算結果を、前述したイデアル集合Ｉによって剰余演算する（ｂ（ｘ１，ｘ２，…，ｘｎ）＝ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）。なお、前述のように、このイデアル集合Ｉの生成には、例えば、セキュリティ装置１２０、１３０で共通する整数係数の多変数多項式ｆ（ｘ１，ｘ２，…，ｘｎ）が使用されるが、この多変数多項式ｆ（ｘ１，ｘ２，…，ｘｎ）は、共通要素生成手段１２０ｊにおいて生成されるものである（後述するステップＳ３２の処理においても同様）。
この演算結果である多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、制御手段１２０ｋに送られ、制御手段１２０ｋは、送られた多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を、公開鍵公開手段１２０ｅに送る。公開鍵公開手段１２０ｅにこの情報が送られると、次に、ステップＳ２５の処理に移る。
【００７４】
ステップＳ２５：
本ステップでは、演算手段１２０ｄｂによって演算された多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を、セキュリティ装置１３０に送信する。
多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の送信は、例えば、セキュリティ装置１２０の公開鍵公開手段１２０ｅによって行われるが、この際、整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）は開示されず、この整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）をセキュリティ装置１２０側で秘密に保った状態で行われる。具体的には、例えば、セキュリティ装置１２０からセキュリティ装置１３０宛の電子メールに、この多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を、整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を特定するための情報を開示することなく提示し、或いは、セキュリティ装置１３０が閲覧可能なインターネット上のホームページに、この多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を、整数組ｓ＝（ｓ０，ｓ１，ｓ２，…，ｓｎ）を特定するための情報を開示することなくアップロードすることによって行われる。
このように多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の送信が行われると、次に、ステップＳ２６の処理に移る。
【００７５】
ステップＳ２６：
本ステップでは、ステップＳ２５でセキュリティ装置１２０から送信された多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）をセキュリティ装置１３０において受信する。
多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の受信は、例えば、セキュリティ装置１３０の公開鍵取得手段１３０ｅにおいて行われる。具体的には、例えば、ステップＳ２２と同様な方法により行われる。
受信された多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、制御手段１３０ｋに送られ、制御手段１３０ｋは、送られた多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を記憶手段１３０ｈに送る。記憶手段１３０ｈに送られた多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、記憶手段１３０ｈに記憶され、次のステップＳ２７の処理に移る。
【００７６】
ステップＳ２７：
本ステップでは、セキュリティ装置１３０において整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）の設定を行う。
整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）の設定は、例えば、セキュリティ装置１３０の整数組生成手段１３０ｃによって行われる。具体的には、例えば、まず、擬似乱数発生手段１３０ｃａにおいて、ＳＨＡ−１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて擬似乱数を発生させ、次に、整数値演算手段１３０ｃｂにおいて、この擬似乱数を所定の桁数に加工し、さらに、所定の値を減算すること等により、所定の整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を設定する。
設定された整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報は、例えば、制御手段１３０ｋに送られ、制御手段１３０ｋは、送られた整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報を、多項式演算手段１３０ｄ及び記憶手段１３０ｈに送る。記憶手段１３０ｈに送られた整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報は、例えば、記憶手段１３０ｈに記憶され、多項式演算手段１３０ｄに送られた整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報は、ステップＳ２８の処理に使用される。
【００７７】
ステップＳ２８：
本ステップでは、多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の演算を行う。
多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の演算は、例えば、セキュリティ装置１３０の多項式演算手段１３０ｄにおいて行われる。多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の演算の演算を行う場合、例えば、まず、制御手段１３０ｋは、ステップＳ２２において記憶手段１３０ｈに記憶された多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を読み込み、その情報を多項式演算手段１３０ｄに送る。この情報が多項式演算手段１３０ｄに送られると、例えば、演算手段１３０ｄａは、この多変数共通多項式ａ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、整数組（ｔ１，ｔ２，…，ｔｎ）を加算した該多変数共通多項式（ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ））の演算を行う。この演算は、具体的には、例えば、前述した一般式を用いて行う。
【００７８】
次に、例えば、演算手段１３０ｄｂにおいて、この演算手段１３０ｄａによって行われた演算の結果に対し、整数ｔ０を指数とする指数演算を行い、該演算結果を、前述したイデアル集合Ｉによって剰余演算する（ｃ（ｘ１，ｘ２，…，ｘｎ）＝ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）。なお、前述のように、このイデアル集合Ｉの生成には、例えば、セキュリティ装置１２０、１３０で共通する整数係数の多変数多項式ｆ（ｘ１，ｘ２，…，ｘｎ）が使用されるが、この多変数多項式ｆ（ｘ１，ｘ２，…，ｘｎ）は、共通要素生成手段１３０ｊにおいて生成されるものである（後述するステップＳ２９の処理においても同様）。
この演算結果である多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、制御手段１３０ｋに送られ、制御手段１３０ｋは、送られた多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報を、記憶手段１３０ｈに送る。記憶手段１３０ｈに送られた多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報は、例えば、記憶手段１３０ｈに記憶され、次のステップＳ２９の処理に移る。
【００７９】
ステップＳ２９：
本ステップでは、暗号文Ｃの演算を行う。
暗号文Ｃの演算は、例えば、セキュリティ装置１３０の暗号文生成手段１３０ｆにおいて行われる。なお、ここでは、平文Ｍ∈［０，１］ｌを暗号化する場合を例にとって説明する。
暗号文Ｃの演算を行う場合、例えばまず、制御手段１３０ｋは、ステップＳ２６において記憶手段１３０ｈに記憶された多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）を特定するための情報、及びステップＳ２６において記憶手段１３０ｈに記憶された整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報を読み込み、これらの情報を暗号文生成手段１３０ｆに送る。これらの情報が送られた暗号文生成手段１３０ｆは、例えば、演算手段１３０ｆａによって、多変数多項式ｂ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、整数組（ｔ１，ｔ２，…，ｔｎ）を加算した該多変数共通多項式（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ））の演算を行う。この演算は、具体的には、例えば、前述した一般式を用いて行う。
【００８０】
次に、例えば、演算手段１３０ｆｂにおいて、この演算手段１３０ｆａによって行われた演算の結果に対し、整数ｔ０を指数とする指数演算を行い、該演算結果を、前述したイデアル集合Ｉによって剰余演算する（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）。
その後、例えば、ハッシュ関数演算手段１３０ｆｃによって、この演算結果に対し、ハッシュ関数Ｈを作用させ（Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）∈［０，１］ｌ）、排他的論理和演算手段１３０ｆｄによって、この演算結果（Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）と平文Ｍとの排他的論理和（Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍ）を暗号文として演算する。
【００８１】
そして、このように演算されたＨ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍと、ステップＳ２８で生成され記憶手段１３０ｈに記憶されている多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）とにより、暗号文Ｃ＝（ｃ（ｘ１，ｘ２，…，ｘｎ），Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍ）を生成する。
生成された暗号文Ｃは、例えば、制御手段１３０ｋに送られ、制御手段１３０ｋは、送られた暗号文Ｃを暗号文開示手段１３０ｇに送る。暗号文Ｃが暗号文開示手段１３０ｇに送られると、次に、ステップＳ３０の処理に移る。
【００８２】
ステップＳ３０：
本ステップでは、暗号文生成手段１３０ｇにおいて生成された暗号文Ｃを、セキュリティ装置１２０に送信する。
暗号文Ｃの送信は、例えば、セキュリティ装置１３０の暗号文開示手段１３０ｇによって行われるが、この際、整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）は開示されず、この整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）をセキュリティ装置１３０側で秘密に保った状態で行われる。具体的には、例えば、セキュリティ装置１３０からセキュリティ装置１２０宛の電子メールに、この暗号文Ｃを特定するための情報を、整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報を開示することなく提示し、或いは、セキュリティ装置１２０が閲覧可能なインターネット上のホームページに、この暗号文Ｃを特定するための情報を、整数組ｔ＝（ｔ０，ｔ１，ｔ２，…，ｔｎ）を特定するための情報を開示することなくアップロードすることによって行われる。
このように暗号文Ｃの送信が行われると、次に、ステップＳ３１の処理に移る。
【００８３】
ステップＳ３１：
本ステップでは、ステップＳ３０でセキュリティ装置１３０から送信された暗号文Ｃをセキュリティ装置１２０において受信する。
暗号文Ｃの受信は、例えば、セキュリティ装置１２０の暗号文取得手段１２０ｆにおいて行われる。具体的には、例えば、セキュリティ装置１２０が、インターネット上のメールサーバにアクセスし、セキュリティ装置１３０から送られたセキュリティ装置１２０宛の電子メールを受け取ることにより、または、暗号文Ｃを特定するための情報がアップロードされたインターネット上のホームページにアクセスすること等により行われる。
このように受信された暗号文Ｃを特定するための情報は、例えば、制御手段１２０ｋに送られ、制御手段１２０ｋは、送られた暗号文Ｃを特定するための情報を復号手段１２０ｇに送り、次のステップＳ３２の処理に移る。
【００８４】
ステップＳ３２：
本ステップでは、セキュリティ装置１２０において、暗号文Ｃの復号を行う。暗号文Ｃの復号は、例えば、セキュリティ装置１２０の復号手段１２０ｇにおいて行われる。
具体的には、例えばまず、復号手段１２０ｇの演算手段１２０ｇａによって、暗号文Ｃ＝（ｃ（ｘ１，ｘ２，…，ｘｎ），Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍ）における多変数多項式ｃ（ｘ１，ｘ２，…，ｘｎ）の任意の変数に、整数組（ｓ１，ｓ２，…，ｓｎ）を加算した該多変数共通多項式（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ））の演算を行う。この演算は、具体的には、例えば、前述した一般式を用いて行う。
次に、例えば、演算手段１２０ｇｂにおいて、この演算手段１２０ｇａによって行われた演算の結果に対し、整数ｓ０を指数とする指数演算を行い、該演算結果を、前述したイデアル集合Ｉによって剰余演算する（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）。そして、この演算結果に対し、ハッシュ関数演算手段１２０ｇｃによって、セキュリティ装置１３０で用いたものと同じハッシュ関数Ｈを作用させ、Ｈ（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）∈［０，１］ｌを得る。その後、排他的論理和演算手段１２０ｇｄにおいて、このように得られたＨ（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）と、暗号文Ｃ＝（ｃ（ｘ１，ｘ２，…，ｘｎ），Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍ）のＨ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍとの排他的論理和を演算する（Ｈ（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）（＋）Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍ）。これにより、前述のように平文Ｍの復号が行われたことになる。
【００８５】
このように、この形態の例では、セキュリティ装置１２０の演算手段１２０ｄａにおいて、通信相手と共用される整数係数の多変数多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した、該多変数多項式の演算を行い（ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ））、演算手段１２０ｄｂにおいて、演算手段１２０ｄａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述のイデアル集合によって剰余演算し（ａ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）、公開鍵公開手段１２０ｅにおいて、演算手段１２０ｄｂによる演算結果である第１の多変数多項式（ｂ（ｘ１，ｘ２，…，ｘｎ））を、公開鍵として公開する。そして、セキュリティ装置１３０の公開鍵取得手段１３０ｅによって、通信相手によって公開された第１の多変数多項式を、公開鍵として取得し、演算手段１３０ｆａにおいて、この第１の多変数多項式の任意の変数に、第１の整数組を加算した、該多変数多項式の演算を行い（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ））、演算手段１３０ｆｂにおいて、この演算結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述のイデアル集合によって剰余演算し（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）、排他的論理和演算手段と１３０ｆｄにおいて、ハッシュ関数Ｈを作用させた  演算手段１３０ｆｂによる演算結果と、通信内容である平文Ｍと、の排他的論理和を、暗号文として演算する（Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍ）。また、演算手段１３０ｄａにおいて、通信相手と共用される整数係数の多変数共通多項式の任意の変数に、第１の整数組を加算した、該多変数多項式の演算を行い（ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ））、演算手段１３０ｄｂにおいて、演算手段１３０ｄａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述のイデアル集合によって剰余演算し（ａ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）、暗号文開示手段１３０ｇにおいて、排他的論理和演算手段１３０ｆｄによって演算された暗号文と、第６の演算手段による演算結果である第２の多変数多項式とを開示する（Ｃ＝（ｃ（ｘ１，ｘ２，…，ｘｎ），Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍ））。開示された第２の多変数多項式と、暗号文とは、セキュリティ装置１２０の暗号文取得手段１２０ｆによって取得され、演算手段１２０ｇａにおいて、暗号文取得手段１２０ｆによって取得された第２の多変数多項式の任意の変数に、第１の整数組を加算した、該多変数多項式の演算を行い（ｃ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ））、演算手段１２０ｇｂにおいて、演算手段１２０ｇａによって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、前述のイデアル集合によって剰余演算し（ｃ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）、排他的論理和演算手段１２０ｇｄにおいて、ハッシュ関数Ｈを作用させた１２０ｇｂ演算手段による演算結果と、暗号文と、の排他的論理���を演算する（Ｈ（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）（＋）Ｈ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）（＋）Ｍ）ことにより、平文Ｍを復号する。そして、前述のように、演算手段１２０ｄａ、１２０ｇａ、１３０ｄａ、１３０ｆａにおいて行われる演算に必要な四則演算の回数は、秘密パラメータ（（ｓ１，ｓ２，…，ｓｎ）等）の大きさに依存せず、この秘密パラメータの大きさを大きくした場合であっても、公開鍵生成時、暗号化時及び復号時において、この演算手段１２０ｄａ、１２０ｇａ、１３０ｄａ、１３０ｆａにおいて行われる演算に起因した四則演算の回数が増大することはない。結果、秘密パラメータの大きさに依存して計算量が増大する従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式を応用した公開鍵暗号方式に比べ、大幅に利便性が向上する。
【００８６】
また、この形態の例では、演算手段１２０ｄａ、１２０ｇａ、１３０ｄａ、１３０ｆａによって行われる、整数係数の多変数多項式の任意の変数に第１の整数組を加算した該多変数多項式の演算と、演算手段１２０ｄｂ、１２０ｇｂ、１３０ｄｂ、１３０ｆｂによって行われる、第１の整数を指数とする指数演算を行い、該演算結果を前述のイデアル集合によって剰余演算する演算と、を組み合わせることによって離散対数問題を構成し、この離散対数問題を用いて、公開鍵生成、暗号化及び復号を行うこととしたため、指数演算のみによって構成される離散対数問題によって、公開鍵生成、暗号化及び復号を行っていた従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式を応用した公開鍵暗号方式に比べ、暗号に対する安全性が大幅に向上する。
【００８７】
さらに、この形態の例では、イデアル集合を、整数係数の多項式がなす環のイデアルであって、δｉを任意の多変数多項式ｇ（ｘ１，ｘ２，…，ｘｎ）に対して多変数多項式ｇ（ｘ１，ｘ２，…，ｘｉ，…，ｘｎ）−ｇ（ｘ１，ｘ２，…，ｘｉ−１，…，ｘｎ）を対応させる作用素とし、ｄｅｇｉｆ（ｘ１，ｘ２，…，ｘｎ）をｆ（ｘ１，ｘ２，…，ｘｎ）のｘｉについての次数とし、（ｐ１，ｐ２，…，ｐｎ）∈Ｎｎとした場合における、｛Σ（ｐ１，ｐ２，…，ｐｎ）（Πｉ＝１ｎδｉｐｉ）ｆ（ｘ１，ｘ２，…，ｘｎ）｝によって生成されるイデアルであることとしたため、前述のように、セキュリティ装置１２０、１３０のそれぞれで算出されたＨ（ｃ（ｘ１＋ｓ１，ｘ２＋ｓ２，…，ｘｎ＋ｓｎ）ｓ０ｍｏｄＩ）とＨ（ｂ（ｘ１＋ｔ１，ｘ２＋ｔ２，…，ｘｎ＋ｔｎ）ｔ０ｍｏｄＩ）との演算結果が同一となり、本形態における暗号文の復号が実質的に可能となる。
【００８８】
また、この形態の例では、演算手段１２０ｄａ、１２０ｇａ、１３０ｄａ、１３０ｆａにおいて、多変数多項式ａ（ｘ１，ｘ２，…，ｘｎ）に対し、第１の整数組を（ｓ１，ｓ２，…，ｓｎ）とし、ｐ＝（ｐ１，ｐ２，…，ｐｎ）∈Ｎｎとし、ｓｐ＝ｓ１ｐ１ｓ２ｐ２…ｓｎｐｎとし、ｐ！＝ｐ１！ｐ２！…，ｐｎ！とし、（∂／∂ｘ）ｐ＝（∂／∂ｘ１）ｐ１（∂／∂ｘ２）ｐ２…（∂／∂ｘｎ）ｐｎとした場合における、Σｐｓｐ（１／ｐ！）（∂／∂ｘ）ｐａ（ｘ１，ｘ２，…，ｘｎ）の演算を行うこととしたため、演算手段１２０ｄａ、１２０ｇａ、１３０ｄａ、１３０ｆａにおいて行われる演算に必要な四則演算の回数が、秘密パラメータ（（ｓ１，ｓ２，…，ｓｎ）や（ｔ１，ｔ２，…，ｔｎ））の大きさに依存することはない。したがって、この秘密パラメータの大きさを大きくした場合であっても、鍵配送時において、この演算手段１２０ｄａ、１２０ｇａ、１３０ｄａ、１３０ｆａにおいて行われる演算に起因した四則演算の回数が増大することはなく、結果、秘密パラメータの大きさに依存して計算量が増大する従来のＤｉｆｆｉｌｅ−Ｈｅｌｌｍａｎ鍵配送方式を応用した公開鍵暗号方式に比べ、大幅に利便性が向上する。
【００８９】
なお、この発明は上述の実施の形態に限定されるものではない。例えば、この形態の例では、第１の演算手段である演算手段１２０ｄａ等において、多変数多項式（ａ（ｘ１，ｘ２，…，ｘｎ）等）の全ての変数に、整数組（（ｓ１，ｓ２，…，ｓｎ）等）を加算した当該多変数多項式の演算を行う場合を例示したが、多変数多項式の一部の変数（例えば、ａ（ｘ１，ｘ２，…，ｘｎ）における（ｘ１，ｘ２，…，ｘｎ）のうちの一部）のみに整数組を加算した当該多変数多項式の演算を行うこととしてもよい。
また、この形態の例では、セキュリティ装置１２０で生成した多変数共通多項式を、セキュリティ装置１２０からセキュリティ装置１３０へ送信する構成としたが、セキュリティ装置１３０で生成した多変数共通多項式をセキュリティ装置１３０からセキュリティ装置１２０へ送信する構成としてもよく、さらに、セキュリティ装置１２０、１３０双方で、セキュリティ装置１２０、１３０に共通する多変数共通多項式を生成する構成としてもよい。
【００９０】
さらに、この形態では、コンピュータ上で所定のプログラムを実行させることにより、セキュリティ装置１２０、１３０を構成することとしたが、これらの処理内容の少なくとも一部を電子回路によってハードウェア的に実現することとしてもよい。
また、第１の実施の形態及び第２の実施の形態で説明した通り、上記の処理機能は、コンピュータによって実現することができる。この場合、セキュリティ装置２、３、２０、３０、１０２、１０３、１２０、１３０が有すべき機能の処理内容はプログラムによって記述され、このプログラムをコンピュータで実行することにより、上記処理機能をコンピュータ上で実現することができる。
【００９１】
また、この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、ＤＶＤ−ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＣＤ−Ｒ（Ｒｅｃｏｒｄａｂｌｅ）／ＲＷ（ＲｅＷｒｉｔａｂｌｅ）等を、光磁気記録媒体として、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｃ）等を用いることができる。
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅｒ）型のサービスによって、上述の処理を実行する構成としてもよい。
なお、上記におけるプログラムとは、電子計算機に対する指令であって、一の結果を得ることができるように組合されたものをいい、その他電子計算機による処理の用に供する情報であってプログラムに準ずるものをも含むものとする。
【００９３】
【発明の効果】
以上説明したようにこの発明では、第１の演算手段によって、整数係数の多変数多項式の任意の変数に、概変数ごとに独立した第１の整数組を加算した、該多変数多項式の演算を行い、第２の演算手段によって、第１の演算手段によって行われた演算の結果に対し、第１の整数を指数とする指数演算を行い、該演算結果を、イデアルであって、該イデアルに対して行われた、整数係数の多変数多項式の任意の変数について任意の整数値だけ加算した該多項式の演算結果が、再び、該イデアルとなるイデアル集合、によって剰余演算することとしたため、例えば鍵配送や暗号文通信時における利便性を保ちつつ、第三者からの攻撃に対する安全性の向上を図ることが可能となる。
【００９４】
特に、この発明では、１変数多項式ではなく、多変数多項式の任意の変数に、概変数ごとに独立した整数組を加算する演算によって離散対数問題を生成することとしたため、第三者からの攻撃に対する安全性をより大きなものとすることができる。
【図面の簡単な説明】
【図１】セキュリティシステムの概略を説明するための図。
【図２】セキュリティシステムの全体構成を例示した図。
【図３】セキュリティ装置のハードウェア構成を例示したブロック図。
【図４】セキュリティ装置の処理機能を例示した機能ブロック図。
【図５】セキュリティ装置の処理機能を例示した機能ブロック図。
【図６】セキュリティシステム、セキュリティ装置の処理動作の一例を説明するためのフローチャート。
【図７】セキュリティシステムの概略を説明するための図。
【図８】セキュリティシステムの全体構成を例示した図。
【図９】セキュリティ装置の処理機能を例示した機能ブロック図。
【図１０】セキュリティ装置の処理機能を例示した機能ブロック図。
【図１１】セキュリティシステム、セキュリティ装置の処理動作の一例を説明するためのフローチャート。
【符号の説明】
１、１０、１００、１１０  セキュリティシステム
２、３、２０、３０、１０２、１０３、１２０、１３０  セキュリティ装置
２ａ、２ｂ、３ａ、３ｂ、２０ｄａ、２０ｄｂ、２０ｇａ、２０ｇｂ、３０ｄａ、３０ｄｂ、３０ｇａ、３０ｇｂ、１０２ａ、１０２ｂ、１０３ａ、１０３ｂ、１２０ｄａ、１２０ｄｂ、１２０ｇａ、１２０ｇｂ、１３０ｄａ、１３０ｄｂ、１３０ｆａ、１３０ｆｂ  演算手段
【図１】
2004158951.tif 000003
【図２】
2004158951.tif 000004
【図３】
2004158951.tif 000005
【図４】
2004158951.tif 000006
【図５】
2004158951.tif 000007
【図６】
2004158951.tif 000008
【図７】
2004158951.tif 000009
【図８】
2004158951.tif 000010
【図９】
2004158951.tif 000011
【図１０】
2004158951.tif 000012
【図１１】
2004158951.tif 000013