(57)【特許請求の範囲】
【請求項１】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数２３】
0005596835.tif 000023
の関係が成り立つ整数、
ｌｏｇは、ネイピア数を底とする対数を示す記号、
ｄｅｇは、多項式の次数を示す記号、
ｇｃｄは、最大公約数を示す記号、
Ｎｆ（ａ＋ｂα）＝（−ｂ）ｄｅｇｆｆ（−ａ／ｂ）はノルム、
λは、Shirokauer指数
であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算装置であって、
多項式選択手段、篩手段、線形代数手段を有し、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算部と、
多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算部とを備え、
前記ＲとＮが、
【数２４】
0005596835.tif 000024
の関係を満足し、
前記多項式選択手段は、ｒ＝１，…，Ｒについて、
【数３６】
0005596835.tif 000025
となる多項式ｆｒ１、ｆｒ２、整数Ｍｒ１、Ｍｒ２を求め、
前記篩手段は、ｒ＝１，…，Ｒとｉ＝１，２のそれぞれに対して、
ノルムの絶対値｜Ｎｆｉ（ａｊ＋ｂｊαｉ）｜が素数の積で表現でき、ｇｃｄ（ａｊ，ｂｊ）＝１である（ａｊ，ｂｊ）をＪ個見つけ、
【数３７】
0005596835.tif 000026
を計算し、
ただし、Ｊは、（ａｊ，ｂｊ）のノルムの素因数分解から得られる式の未知数の個数より大きく、
前記線形代数手段は、ｒ＝１，…，Ｒについて、前記未知数を並べたベクトルの非自明な解を求めてベクトルｘｒ＾とし、
前記群要素計算部は、ｙｊｇｋがＢｉ−ｓｍｏｏｔｈになるようにｊ，ｋを求め、そのｊ，ｋ及びベクトルｘ１＾，…，ｘＲ＾の値を用いて、整数ｘを計算する
ただし、Ｂｉは多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、と素数ｐ１，…，ｐＲに基づいて定められた整数とする
ことを特徴とする離散対数計算装置。
【請求項２】
請求項１記載の離散対数計算装置であって、
すべての前記素数ｐｒは、乗法群（Ｚ／ｐｒＺ）＊についての離散対数の計算で、特殊数体篩法が利用できる素数である
ことを特徴とする離散対数計算装置。
【請求項３】
請求項１または２記載の離散対数計算装置であって、
前記因子基底計算部は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが既知となったときに多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部に記録する
ことを特徴とする離散対数計算装置。
【請求項４】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数２６】
0005596835.tif 000027
の関係が成り立つ整数、
ｌｏｇは、ネイピア数を底とする対数を示す記号、
ｄｅｇは、多項式の次数を示す記号、
ｇｃｄは、最大公約数を示す記号、
Ｎｆ（ａ＋ｂα）＝（−ｂ）ｄｅｇｆｆ（−ａ／ｂ）はノルム、
λは、Shirokauer指数
であり、
多項式選択手段、篩手段、線形代数手段を有し、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算部と、
多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を記録する記録部
を備え、
前記ＲとＮが、
【数２７】
0005596835.tif 000028
の関係を満足し、
前記多項式選択手段は、ｒ＝１，…，Ｒについて、
【数３８】
0005596835.tif 000029
となる多項式ｆｒ１、ｆｒ２、整数Ｍｒ１、Ｍｒ２を求め、
前記篩手段は、ｒ＝１，…，Ｒとｉ＝１，２のそれぞれに対して、
ノルムの絶対値｜Ｎｆｉ（ａｊ＋ｂｊαｉ）｜が素数の積で表現でき、ｇｃｄ（ａｊ，ｂｊ）＝１である（ａｊ，ｂｊ）をＪ個見つけ、
【数３９】
0005596835.tif 000030
を計算し、
ただし、Ｊは、（ａｊ，ｂｊ）のノルムの素因数分解から得られる式の未知数の個数より大きく、
前記線形代数手段は、ｒ＝１，…，Ｒについて、前記未知数を並べたベクトルの非自明な解を求めてベクトルｘｒ＾とする
ことを特徴とする事前計算装置。
【請求項５】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数３０】
0005596835.tif 000031
の関係が成り立つ整数、
ｌｏｇは、ネイピア数を底とする対数を示す記号、
ｄｅｇは、多項式の次数を示す記号、
ｇｃｄは、最大公約数を示す記号、
Ｎｆ（ａ＋ｂα）＝（−ｂ）ｄｅｇｆｆ（−ａ／ｂ）はノルム、
λは、Shirokauer指数
であり、
整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算方法であって、
因子基底計算部が、多項式選択サブステップ、篩サブステップ、線形代数サブステップを実行して、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算ステップと、
群要素計算部が、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算ステップとを有し、
前記ＲとＮが、
【数３１】
0005596835.tif 000032
の関係を満足すし、
前記多項式選択サブステップは、ｒ＝１，…，Ｒについて、
【数４０】
0005596835.tif 000033
となる多項式ｆｒ１、ｆｒ２、整数Ｍｒ１、Ｍｒ２を求め、
前記篩サブステップは、ｒ＝１，…，Ｒとｉ＝１，２のそれぞれに対して、
ノルムの絶対値｜Ｎｆｉ（ａｊ＋ｂｊαｉ）｜が素数の積で表現でき、ｇｃｄ（ａｊ，ｂｊ）＝１である（ａｊ，ｂｊ）をＪ個見つけ、
【数４１】
0005596835.tif 000034
を計算し、
ただし、Ｊは、（ａｊ，ｂｊ）のノルムの素因数分解から得られる式の未知数の個数より大きく、
前記線形代数サブステップは、ｒ＝１，…，Ｒについて、前記未知数を並べたベクトルの非自明な解を求めてベクトルｘｒ＾とし、
前記群要素計算ステップは、ｙｊｇｋがＢｉ−ｓｍｏｏｔｈになるようにｊ，ｋを求め、そのｊ，ｋ及びベクトルｘ１＾，…，ｘＲ＾の値を用いて、整数ｘを計算する
ただし、Ｂｉは多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、と素数ｐ１，…，ｐＲに基づいて定められた整数とする
ことを特徴とする離散対数計算方法。
【請求項６】
請求項５記載の離散対数計算方法であって、
すべての前記素数ｐｒは、乗法群（Ｚ／ｐｒＺ）＊についての離散対数の計算で、特殊数体篩法が利用できる素数である
ことを特徴とする離散対数計算方法。
【請求項７】
請求項５または６記載の離散対数計算方法であって、
前記因子基底計算ステップは、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが既知となったときに多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部に記録する
ことを特徴とする離散対数計算方法。
【請求項８】
ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素、
前記Ｎは、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【数３３】
0005596835.tif 000035
の関係が成り立つ整数、
ｌｏｇは、ネイピア数を底とする対数を示す記号、
ｄｅｇは、多項式の次数を示す記号、
ｇｃｄは、最大公約数を示す記号、
Ｎｆ（ａ＋ｂα）＝（−ｂ）ｄｅｇｆｆ（−ａ／ｂ）はノルム、
λは、Shirokauer指数
であり、
因子基底計算部が、多項式選択サブステップ、篩サブステップ、線形代数サブステップを実行して、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する因子基底計算ステップを有し、
前記ＲとＮが、
【数３４】
0005596835.tif 000036
の関係を満足し、
前記多項式選択サブステップは、ｒ＝１，…，Ｒについて、
【数４２】
0005596835.tif 000037
となる多項式ｆｒ１、ｆｒ２、整数Ｍｒ１、Ｍｒ２を求め、
前記篩サブステップは、ｒ＝１，…，Ｒとｉ＝１，２のそれぞれに対して、
ノルムの絶対値｜Ｎｆｉ（ａｊ＋ｂｊαｉ）｜が素数の積で表現でき、ｇｃｄ（ａｊ，ｂｊ）＝１である（ａｊ，ｂｊ）をＪ個見つけ、
【数４３】
0005596835.tif 000038
を計算し、
ただし、Ｊは、（ａｊ，ｂｊ）のノルムの素因数分解から得られる式の未知数の個数より大きく、
前記線形代数サブステップは、ｒ＝１，…，Ｒについて、前記未知数を並べたベクトルの非自明な解を求めてベクトルｘｒ＾とする
ことを特徴とする事前計算方法。
【請求項９】
請求項１から４のいずれかに記載された装置として、コンピュータを動作させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、落し戸付き離散対数問題の離散対数計算装置、事前計算装置、離散対数計算方法、事前計算方法、プログラムに関する。
【背景技術】
【０００２】
ある群Ｇの要素ｇ、ｙが与えられたときに、ｙ＝ｇｘを満たす整数ｘが存在する場合には整数ｘを計算し、存在しない場合にはその旨を出力する問題を離散対数問題と呼ぶ。ここで、ｘをｇを底とするｙの離散対数と呼ぶ。離散対数問題が困難な群に対し、何かヒントが与えられた場合に離散対数が簡単に計算できるとき、そのヒントを落し戸と呼ぶ。そのようなヒントが構成できるような離散対数問題を落し戸付き離散対数問題と呼ぶ。
【０００３】
群Ｇとして、乗法群（Ｚ／ＮＺ）＊を考える。ただし、Ｎは正の整数である。乗法群（Ｚ／ＮＺ）＊とは、例えば、整数Ｎと互いに素な０以上Ｎ未満の整数の集合である。一般に、整数Ｎが十分に大きい場合には離散対数問題は困難だと考えられている。非特許文献１では、整数Ｎ＝ｐ１ｐ２として、次の条件を満たすものを選び、整数Ｎの素因数分解を落し戸としている。なお、ｐ１とｐ２は素数である。
【０００４】
＜条件１＞
ｉ＝１，２に対し、ｐｉ−１がＢ−ｓｍｏｏｔｈで、ｐｉ−１の２番目に大きな素因子はＢと同程度の大きさである
つまり、整数Ｎの素因数分解が未知の場合は離散対数問題が困難になるようにし、整数Ｎの素因数分解が既知の場合は離散対数問題が容易になるようにした。
【０００５】
ここで、既知の最適な離散対数の解法でも、落し戸がない状態では、まず整数Ｎを素因数分解し、それからその結果を用いて離散対数を計算する方法が最も高速である。＜条件１＞を満たす整数Ｎの場合、Ｂが十分に小さければ最も効率のよい整数Ｎの素因数分解法はｐ−１法であり、計算量はＯ（Ｂ）である。一方、離散対数の計算はPohlig-Hellman法とρ法の組合せが最適であり、計算量はＯ（√Ｂ）である。Ｏ（√Ｂ）の自乗のオーダーとＯ（Ｂ）のオーダーが同じなので、素因数分解の計算量は、離散対数の計算量の自乗のオーダーである。よって、整数Ｂを適切に選べば、素因数分解の計算は困難だが、離散対数の計算は容易になるように調整でき、落し戸付き離散対数問題が構成できる。つまり、落し戸である整数Ｎの素因数分解の結果を知っている場合（例えば、正規なユーザ）は離散対数の計算が容易だが、整数Ｎの素因数分解の結果を知らない場合（例えば、攻撃者）は離散対数の計算が困難になる。例えば、Ｂ＝２４０を選べばよい。なお、乗法群（Ｚ／ＮＺ）＊の離散対数を簡単に構成する具体例として、特許文献１〜３が知られている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００７−００３９４６号公報
【特許文献２】特開２００７−１７１４１１号公報
【特許文献３】特開２００７−１７１４１２号公報
【非特許文献】
【０００７】
【非特許文献１】Kenneth G. Paterson and Sriramkrishnan Srinivasan, “On the Relations Between Non-Interactive Key Distribution, Identity-Based Encryption and Trapdoor Discrete Log Groups”、［平成２１年１０月１３日検索］、インターネット<URL: http://eprint.iacr.org/2007/453.pdf>．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、従来技術では、容易にしたい離散対数の計算量（落し戸ありの場合の計算量）がＯ（√Ｂ）であるのに対し、困難にしたい素因数分解の計算量（落し戸なしの場合の計算量）はＯ（Ｂ）である。また、Ｏ（√Ｂ）２のオーダーとＯ（Ｂ）のオーダーとが等しい。つまり、計算量の比は、自乗の比（Ｏ（√Ｂ）：Ｏ（Ｂ））程度に限られてしまうという課題がある。
【０００９】
本発明は、このような課題に鑑みてなされたものであり、選定された整数Ｎを用いた効率的な離散対数の計算方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の離散対数計算装置は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める。なお、ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素であり、ＮはＲ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）と
【００１１】
【数１】
0005596835.tif 000002
【００１２】
の関係が成り立つ整数である。また、整数Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない、もしくは、ＲとＮが、
【００１３】
【数２】
0005596835.tif 000003
【００１４】
の関係を満足する。そして、本発明の離散対数計算装置は、因子基底計算部と群要素計算部とを備える。因子基底計算部は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算する。群要素計算部は、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する。
【００１５】
本発明の事前計算装置は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが与えられたときに、ｙ＝ｇｘを満たす整数ｘを求めるための中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を求める。本発明の別の離散対数計算装置は、あらかじめ計算された離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する群要素計算部を備える。
【発明の効果】
【００１６】
本発明の離散対数計算装置によれば、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように整数Ｎのサイズと素因数の数Ｒを決めているので、落し戸ありの場合の計算量（離散対数の計算量）と落し戸なしの場合の計算量（素因数分解も行う場合の計算量）の比を大きくできる。また、因子基底計算部と群要素計算部とに分けた構成となっているので、要素ｙが与えられる前でも、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、あらかじめ離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算することができ、効率的である。
【図面の簡単な説明】
【００１７】
【図１】実施例１のパラメータ設定装置の機能構成例を示す図。
【図２】実施例１のパラメータ設定装置の処理フロー例を示す図。
【図３】実施例１変形例１のパラメータ設定装置の機能構成例を示す図。
【図４】実施例１変形例１のパラメータ設定装置の処理フロー例を示す図。
【図５】実施例２の離散対数計算装置の機能構成例を示す図。
【図６】実施例２の離散対数計算装置の処理フロー例を示す図。
【図７】実施例２変形例２の事前計算装置の機能構成例を示す図。
【図８】実施例２変形例２の離散対数計算装置の処理フロー例を示す図。
【図９】実施例２変形例２の事前計算装置の処理フロー例を示す図。
【図１０】実施例２変形例２の離散対数計算装置の処理フロー例を示す図。
【発明を実施するための形態】
【００１８】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１９】
実施例の説明の前に、本発明の理解に必要な内容について説明する。計算量を表す関数としてＬＮ［ｓ，ｃ］（ただし、ｓとｃは実数であり、０≦ｓ≦１）を、
【００２０】
【数３】
0005596835.tif 000004
【００２１】
とおく。なお、ｏ（１）は整数Ｎが無限大の場合に０に近づく適当な関数である。また、
【００２２】
【数４】
0005596835.tif 000005
【００２３】
とし、それぞれのｐｒのサイズは近いものとする。なお、必ずしもｐｒのサイズは近くなくても以下の説明は成り立つが、説明が煩雑になる上、発明の効率もサイズが近い場合の方が良い。仮にｐｒのサイズが異なるとすると、落し戸なしでの計算量は２番目に大きいｐｒもしくはＮのサイズによって決まり、落し戸ありでの離散対数の計算は最も大きなｐｒによって決まる。したがって、以下の説明ではそれぞれのｐｒのサイズは近いものとする。
【００２４】
既知の漸近的に最も高速な素因数分解法である数体篩法による整数Ｎの素因数分解の計算量は、ＬＮ［１／３，（６４／９）１／３］であることが知られている。漸近的にはCoppersmith（Don Coppersmith, “Modifications to the Number Field Sieve,” Journal of Cryptology, vol. 6, num. 3, pp.169-180, 1993.）の改良が知られているが、実用的な効果は薄いと信じられているので実施例では取り扱わない。また、楕円曲線法による素因数分解により因子ｐを見つける計算量は、Ｎのサイズがｐのサイズに比べてそれほど大きくない場合にはＬｐ［１／２，√２］であることが知られている。つまり、楕円曲線法により整数Ｎを素因数分解するためには、
【００２５】
【数５】
0005596835.tif 000006
【００２６】
の計算が必要である。ここで、例えばｏ（１）を無視すれば、
【００２７】
【数６】
0005596835.tif 000007
【００２８】
が成り立つ場合には数体篩法の方が楕円曲線法より整数Ｎを素因数分解するには高速となる。なお、実際にはｏ（１）を無視できない場合や式（１）が成立しない場合にも落し戸付き離散対数問題が構成できるような整数Ｎもあるが、式（１）によって判別すれば、高い確率で数体篩法の方が楕円曲線法よりも高速となるので、整数Ｎを繰り返し設定するパラメータ設定装置の場合には十分に本発明の効果が得られる。したがって、式（１）の条件を用いても実用的には問題ない。
【実施例１】
【００２９】
図１に本発明のパラメータ設定装置の機能構成例を示す。また、図２にパラメータ設定装置の処理フロー例を示す。パラメータ設定装置１００は、条件設定部１３０、素数生成部１１０、整数生成部１２０、記録部１４０を備える。条件設定部１３０は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を決める（Ｓ１３０）。素数生成部１１０は、整数Ｎのサイズと素因数の数Ｒから、Ｒ個の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する（Ｓ１１０）。このときに、前述のように各ｐｒのサイズが近くなるように設定することが望ましい。整数生成部１２０は、素数ｐｒから、整数Ｎを
【００３０】
【数７】
0005596835.tif 000008
【００３１】
のように求め、記録部１４０に記録する（Ｓ１２０）。
【００３２】
本発明のパラメータ設定装置によって選定される整数Ｎの場合、素因数分解の計算量ＰはＬＮ［１／３，（６４／９）１／３］となり、乗法群（Ｚ／ｐｒＺ）＊の離散対数の計算量ＱはＬＮ［１／３，（６４／９Ｒ）１／３］となる。ここで、
【００３３】
【数８】
0005596835.tif 000009
【００３４】
である。したがって、ＰのオーダーとＱのＲ１／３乗のオーダーが等しい。つまり、Ｒを大きくすることで、素因数分解の計算量Ｐのオーダーを離散対数の計算量Ｑのオーダーの自乗よりも大きくできる。なお、漸近的な条件ではいくらでもＲを大きくできるので、計算量の比もいくらでも大きくできる。
【００３５】
［変形例１］
図３に本発明の別のパラメータ設定装置の機能構成例を示す。また、図４にパラメータ設定装置の処理フロー例を示す。パラメータ設定装置１５０は、素数生成部１１５、整数生成部１２０、パラメータ選定部１６０、記録部１９０を備える。素数生成部１１５は、Ｒ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を生成する（Ｓ１１５）。整数生成部１２０は、素数ｐｒから、整数Ｎを
【００３６】
【数９】
0005596835.tif 000010
【００３７】
のように求める（Ｓ１２０）。パラメータ選定部１６０は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるかを確認する（パラメータとしての条件を満たすかを確認する）。そして、条件を満たす場合には当該整数Ｎをパラメータとして選定し、記録部１９０に記録する（Ｓ１６０）。パラメータとしての条件としては、例えば式（１）があるが、この式に限定する必要は無く、効率良く、かつ高い確率で判別できれば良い。そして、条件を満たさない場合にはステップＳ１１５に戻り、素数生成部１１５の素数の生成、整数生成部１２０の整数Ｎの生成、パラメータ選定部１６０の確認を繰り返す。なお、パラメータ設定装置１００は、複数の整数Ｎを生成しておき、その中からパラメータ選定部が条件を満たす整数Ｎを選定してもよい。この場合も、複数の整数Ｎの中に条件を満たす整数が存在しなかった場合には、ステップＳ１１５に戻ればよい。
【００３８】
このような構成なので、本変形例の場合にも、実施例１のパラメータ設定装置と同じ効果が得られる。
【００３９】
［変形例２］
変形例２のパラメータ設定装置１００’、１５０’では、素数生成部１１０’、１１５’が実施例１や実施例１変形例１と異なる。その他の構成部や処理フローは実施例１や実施例１変形例１のパラメータ設定装置１００、１５０と同じである。素数生成部１１０’、１１５’は、乗法群（Ｚ／ｐｒＺ）＊の離散対数の計算で特殊数体篩法が利用できる素数ｐｒを生成する（Ｓ１１０’、Ｓ１１５’）。具体的には、２５２１−１や２６０７−１などを選定すればよい。
【００４０】
このように素数ｐｒを生成すれば、Ｒが十分に大きいときに整数Ｎの素因数分解は、特殊数体篩法ではなく、やはり一般数体篩法が最も高速となる。このような素数ｐｒを用いた整数Ｎの場合、落し戸がある場合の離散対数の計算量Ｑは
【００４１】
【数１０】
0005596835.tif 000011
【００４２】
となる。ここで、
【００４３】
【数１１】
0005596835.tif 000012
【００４４】
である。したがって、ＰのオーダーとＱの（２Ｒ）１／３乗のオーダーが等しい。つまり、実施例１や実施例１変形例１のパラメータ設定装置１００、１５０が選定した整数Ｎよりもさらに計算量の比を大きくできる。
【実施例２】
【００４５】
図５に実施例２の離散対数計算装置の機能構成例を示す。また、図６に離散対数計算装置の処理フロー例を示す。離散対数計算装置２００は、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇ、要素ｙを入力として、ｙ＝ｇｘを満たす整数ｘを求める。なお、ｙとｇは、乗法群（Ｚ／ＮＺ）＊の要素であり、ＮはＲ個（ただし、Ｒは２以上）の素数ｐｒ（ただし、ｒは１からＲの整数）を用いて
【００４６】
【数１２】
0005596835.tif 000013
【００４７】
のように求められた整数である。また、整数Ｎを素因数分解するための計算量は、数体篩法の方が楕円曲線法よりも少ない、もしくは、ＲとＮが、
【００４８】
【数１３】
0005596835.tif 000014
【００４９】
の関係を満足する。離散対数計算装置２００は、因子基底計算部２１０と群要素計算部２５０と記録部２９０とを備える。記録部２９０にあらかじめ上述の整数Ｎ、素数ｐ１，…，ｐＲを記録しておいてもよいし、パラメータ設定装置１００（１００’、１５０、１５０’）も備えておき、必要に応じて整数Ｎ、素数ｐ１，…，ｐＲを設定してもよい。因子基底計算部２１０は、多項式選択手段２２０、篩手段２３０、線形代数手段２４０を有し、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇから、離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部２９０に記録する（Ｓ２１０）。群要素計算部２５０は、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾と要素ｙを用いて整数ｘを計算する（Ｓ２５０）。
【００５０】
次に、ステップＳ２１０とＳ２５０の処理内容について詳細に説明する。整数Ｎとその素因数である素数ｐ１，…，ｐＲが与えられている場合、各ｍｏｄｐｒに対して離散対数を求め、中国人の剰余定理によりｍｏｄＮの離散対数に変換する。具体的には、ｙ（＝ｇｘ  ｍｏｄｐ）とｇが与えられた際の、数体篩法による乗法群（Ｚ／ｐＺ）＊の離散対数ｘ（＝ｌｏｇｇｙ）は、多項式選択処理、篩処理、線形代数処理、個別の離散対数計算の手順で求められる。多項式選択手段２２０が多項式選択処理を行い、篩手段２３０が篩処理を行い、線形代数手段２４０が線形代数処理を行い、群要素計算部２５０が個別の離散対数計算を行う。
【００５１】
次に図６のフロー例に従いながら説明する。ｒを１とし（Ｓ２１１）、１つ目の素数ｐ１についての処理を始める。多項式選択手段２２０は、
【００５２】
【数１４】
0005596835.tif 000015
【００５３】
となる多項式ｆｒ１、ｆｒ２∈Ｚ［Ｘ］、整数Ｍｒ１、Ｍｒ２∈Ｚ／ｐｒＺを求め、記録部２９０に記録する（Ｓ２２０）。多項式ｆｒ１、ｆｒ２は既約で、かつ複素数体Ｃ上の共通根を持ってはならない。また、多項式ｆｒ１、ｆｒ２の次数の和（ｄｅｇｆｒ１＋ｄｅｇｆｒ２）の最適な大きさは素数ｐｒのサイズにより決定される。多くの場合ｆｒ１、ｆｒ２の係数の絶対値が小さい方が、後続の計算が高速となる。なお、多項式ｆｒ１、ｆｒ２の選び方としては、多数の方法が知られており、それらの中から適宜選択すればよい。
【００５４】
ここで、複素数体Ｃ上でｆｒｉ（αｉ）＝０とする。因子基底ｉ＝１，２に対し、
【００５５】
【数１５】
0005596835.tif 000016
【００５６】
と定義する。ここで最適なＢｉはｆｒ１、ｆｒ２とｐｒによって決まる。そして、ノルムを
Ｎｆ（ａ＋ｂα）＝（−ｂ）ｄｅｇｆｆ（−ａ／ｂ）
と定義する。篩手段２３０は、ｉ＝１，２のそれぞれに対して、
【００５７】
【数１６】
0005596835.tif 000017
【００５８】
となる（ａ，ｂ）（ただし、ｇｃｄ（ａ，ｂ）＝１）を多数見つける（Ｓ２３０）。さらに、（ａ，ｂ）に対し、Shirokauer指数λを計算する。Ｋｉ＝Ｑ（αｉ）とし、その整数環ＯＫｉの部分集合Γｉを
【００５９】
【数１７】
0005596835.tif 000018
【００６０】
と定義する。ここで、ｐｒは２以外の素数であり、（ｐｒ−１）／２が素数の場合にはｌ＝（ｐｒ−１）／２とし、（ｐｒ−１）／２が素数でない場合にはｌを素因数分解したすべての因子をそれぞれｌとして処理を行う。このとき、
λｉ：Γｉ→ｌＯＫｉ／ｌ２ＯＫｉ
の像はｄｅｇｆｒｉ個の成分で表現されるので、
【００６１】
【数１８】
0005596835.tif 000019
【００６２】
を計算し、記録部２９０に記録する。その結果（ａｊ，ｂｊ）のノルムの素因数分解から、
【００６３】
【数１９】
0005596835.tif 000020
【００６４】
という式が得られる。ここで、ｘ（ｉ）ｋ∈［０，ｌ）∩Ｚであり、ｘ（ｉ）ｋとｌｏｇｇ（ｑｋ，αｉ−ｔｋ）が未知数である。篩手段２３０は、この未知数の個数より多くの（ａｊ，ｂｊ）を集める。
【００６５】
式（２）の未知数を変数とみなして行列表記すると
Ａｘｒ＾≡０＾  （ｍｏｄｌ）
と書ける。ここで、ｘｒ＾は未知数を並べたベクトル、０＾は零ベクトルである。線形代数手段２４０は、このベクトルｘｒ＾の非自明な解を求め、記録部２９０に記録する（Ｓ２４０）。なお、Ａは疎行列となるので、Gaussの消去法などの一般的な方法ではなく、疎行列専用の高速な解法を利用できる。因子基底計算部２１０は、ｒ＝Ｒかを確認し（Ｓ２１２）、Ｙｅｓの場合には線形代数処理（Ｓ２５０）に進み、Ｎｏの場合にはｒの値を１つ増やした上で（Ｓ２１３）、多項式選択処理（Ｓ２２０）に戻る。ここまでの繰り返し処理（Ｓ２１０）で、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾が記録部２９０に記録されている。これらの情報が、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算の中間情報である。
【００６６】
群要素計算部２５０は、ｙｊｇｋがＢｉ−ｓｍｏｏｔｈになるようにｊ，ｋを求め、そのｊ，ｋ及び線形代数処理（Ｓ２４０）の結果であるベクトルｘ１＾，…，ｘＲ＾の値を用いて、個別の離散対数（ｙに対する離散対数）を計算する（Ｓ２５０）。
【００６７】
離散対数計算装置２００は、数体篩法の方が楕円曲線法よりも素因数分解の計算量が少なくなる整数Ｎを用いているので、落し戸ありの場合の計算量（離散対数の計算量）と落し戸なしの場合の計算量（素因数分解も行う場合の計算量）の比を自乗の比よりも大きくできる。なお、漸近的な条件ではいくらでもＲを大きくできるので、計算量の比もいくらでも大きくできる。
【００６８】
［変形例１］
実施例２で示したように、因子基底計算部２１０の処理（Ｓ２１０）によって、ｙ＝ｇｘを満たす整数ｘを求める離散対数計算の中間情報である多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾が記録部２９０に記録される。ステップＳ２１０の処理は、ｙの値が与えられなくても、整数Ｎ、素数ｐ１，…，ｐＲとｇの値が分かればあらかじめ計算しておくことが可能である。また、ステップＳ２１０の部分の計算量は、
【００６９】
【数２０】
0005596835.tif 000021
【００７０】
であり、ステップＳ２５０の部分の計算量は、
【００７１】
【数２１】
0005596835.tif 000022
【００７２】
しか必要としない。
【００７３】
そこで、変形例１の離散対数計算装置では、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが既知となったとき（落し戸が確定したとき）に、因子基底計算部２１０が多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部２９０に記録する。このように個別の要素ｙが与えられる前に計算量の多い因子基底の離散対数の計算（Ｓ２１０）を行ってしまえば、さらに処理速度を高めることができる。
【００７４】
［変形例２］
図７に実施例２変形例２の事前計算装置の機能構成例、図８に実施例２変形例２の離散対数計算装置の機能構成例を示す。また図９に事前計算装置の処理フロー例、図１０に離散対数計算装置の処理フロー例を示す。本変形例は、離散対数計算装置２００を２つに分けた構成であり、事前計算装置３００は、因子基底計算部２１０と記録部２９０を備えている。離散対数計算装置４００は、群要素計算部２５０と記録部４９０を備えている。因子基底計算部２１０の構成と処理フロー（Ｓ２１０）は実施例２と同じであり、変形例１と同じように、整数Ｎ、素数ｐ１，…，ｐＲ、要素ｇが既知となったとき（落し戸が確定したとき）に、因子基底計算部２１０が多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾を計算し、記録部２９０に記録する。
【００７５】
そして、多項式ｆ１１、ｆ１２，…，ｆＲ１、ｆＲ２、整数Ｍ１１、Ｍ１２，…，ＭＲ１、ＭＲ２、ベクトルｘ１＾，…，ｘＲ＾が離散対数計算装置４００に送信され、記録部４９０に記録される。離散対数計算装置４００の群要素計算部２５０は、要素ｙが入力されると、ｙ＝ｇｘを満たす整数ｘを求める（Ｓ２５０）。この処理も実施例２と同じである。
【００７６】
このような構成であっても、数体篩法の方が楕円曲線法よりも素因数分解の計算量が少なくなる整数Ｎを用いているので、事前計算装置３００および離散対数計算装置４００は、落し戸ありの場合の計算量（離散対数の計算量）と落し戸なしの場合の計算量（素因数分解も行う場合の計算量）の比を自乗の比よりも大きくできる。
【００７７】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００８０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００８３】
本発明は、ＩＤベース暗号などの落し戸付きの離散対数問題を必要とする暗号システムで利用できる。
【符号の説明】
【００８４】
１００、１００’、１５０、１５０’  パラメータ設定装置
１１０、１１０’、１１５、１１５’  素数生成部
１２０  整数生成部                        １３０  条件設定部
１４０、１９０、２９０、４９０  記録部
１６０  パラメータ選定部                  ２００、４００  離散対数計算装置
２１０  因子基底計算部                    ２２０  多項式選択手段
２３０  篩手段                            ２４０  線形代数手段
２５０  群要素計算部                      ３００  事前計算装置
【図１】
0005596835.tif 000039
【図２】
0005596835.tif 000040
【図３】
0005596835.tif 000041
【図４】
0005596835.tif 000042
【図５】
0005596835.tif 000043
【図６】
0005596835.tif 000044
【図７】
0005596835.tif 000045
【図８】
0005596835.tif 000046
【図９】
0005596835.tif 000047
【図１０】
0005596835.tif 000048