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