データ圧縮装置、および、これに利用されるパラメータ設定装置
【課題】 拡大次数ｎが一般の正整数であれば、制限なく利用できるようなデータ圧縮装置、および、これに利用されるパラメータ設定装置を提供する。
【解決手段】 拡大次数を素数の組で示すために素因数分解した、素因数分解結果を入力するとともに、外部から有限体の標数と圧縮するデータとを入力し、有限体の標数と拡大次数とで規定され、圧縮するデータが含まれる代数的トーラスに、素因数分解結果の素数のべき指数に依存する次元を持つ入力アフィン空間を加えて、素因数分解結果の素数のべき指数に依存する次元を持つ出力アフィン空間へ写像する関数、テーブル、または関数とテーブルとの組へ、圧縮したいデータ、及び入力アフィン空間に属する補助入力データを供給して取得される結果データを圧縮データとして外部へ出力するデータ圧縮部２４とを備えた。
【解決手段】 拡大次数を素数の組で示すために素因数分解した、素因数分解結果を入力するとともに、外部から有限体の標数と圧縮するデータとを入力し、有限体の標数と拡大次数とで規定され、圧縮するデータが含まれる代数的トーラスに、素因数分解結果の素数のべき指数に依存する次元を持つ入力アフィン空間を加えて、素因数分解結果の素数のべき指数に依存する次元を持つ出力アフィン空間へ写像する関数、テーブル、または関数とテーブルとの組へ、圧縮したいデータ、及び入力アフィン空間に属する補助入力データを供給して取得される結果データを圧縮データとして外部へ出力するデータ圧縮部２４とを備えた。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は離散対数問題に依った暗号系のデータ圧縮に関する。
【背景技術】
【０００２】
ネットワークの利便性の向上や、ハードディスク装置や、不揮発性メモリなどの技術進歩により、ますますデジタルデータの流通が盛んになってきており、これに伴って、デジタルデータを安全に流通させるために、暗号技術や署名技術もより重要になってきている。
【０００３】
暗号技術や署名技術の一つのカテゴリとして、例えばＥｌＧａｍａｌ暗号／署名のような有限群上の離散対数問題に依った暗号／署名方式がある。しかしながら、この有限群上の離散対数問題に依った暗号／署名方式は、鍵、暗号文、署名などが長く、このことが利便性を損ねている大きな要因の１つであった。
【０００４】
有限群上の離散対数問題に依った暗号／署名方式では、有限群としては有限体の部分群が用いられるものが多い。このような方式のとき、部分群の元の個数は有限体の大きさに比べるとかなり小さい場合がある。もし、有限体の要素より少ないｂｉｔ数で部分群を効率よく表現できるとすると、それは鍵長や暗号文長、署名長を圧縮できることにつながる。
【０００５】
ＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇは、離散対数問題に依った暗号系に用いられる鍵と暗号文、離散対数問題に依った署名方式で生成される署名を代数的トーラスを用いることで圧縮する方法を開示している（非特許文献1参照）。以下では、有限体の標数ｑ、拡大次数ｎとし説明する。非特許文献１では、圧縮関数ρと伸長関数ψを構成し、ｎが２個以下の素数の巾の積である場合について圧縮率ｒ＝ｎ／φ（ｎ）を達成した。ここで圧縮率ｒは鍵等のビット長が圧縮により１／ｒ倍になることと定義される。φはオイラー関数である。
【０００６】
ｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらは、非特許文献１の方法を改良し、ｎが相異なる素数の積である場合について、圧縮率として漸近的にｎ／φ（ｎ）を達成する圧縮方法を開示している（非特許文献２参照）。ここでｎ／φ（ｎ）は、ｎが小さい素因数を多く含む場合に大きい値を取ることが知られている。
【非特許文献１】Ｋ．Ｒｕｂｉｎ ａｎｄ Ａ． Ｓｉｌｖｅｒｂｅｒｇ， Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ． Ｃｒｙｐｔｏ’０３， ＬＮＣＳ ２７２９， ３４９−３６５
【非特許文献２】Ｍ． ｖａｎ Ｄｉｊｋ ａｎｄ Ｄ． Ｗｏｏｄｒｕｆｆ，Ａｓｙｍｐｔｏｔｉｃａｌｌｙ Ｏｐｔｉｍａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ｆｏｒ Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｔｏｇｒａｐｈｙ． Ｃｒｙｐｔｏ’０４， ＬＮＣＳ３１５２， １５７−１７８
【発明の開示】
【発明が解決しようとする課題】
【０００７】
有限体の部分群上の離散対数問題に依った暗号／署名におけるデータ圧縮法として、有限体の拡大次数ｎが一般の正整数であれば、利用に制限がなく利用価値が高い。
【０００８】
しかしながら、上記非特許文献１に開示される圧縮技術は、ｎの条件によって圧縮率ｒが大きな値を取らないため、限定的にしか利用できないという問題があった。なお、この方法を用いた場合の圧縮率ｒの上限は３である。
【０００９】
また、上記非特許文献２に開示される圧縮技術は、大きな圧縮率ｒを取るｎの個数が少ないためにｎの選択に大きな制約を受けるから利用がし難かったという問題があった。
【００１０】
そこで、本発明は、有限体の部分群上の離散対数問題に依った暗号／署名におけるデータ圧縮法として、有限体の拡大次数ｎが一般の正整数であれば、制限なく利用できるよう好適なデータ圧縮装置、および、これに利用されるパラメータ設定装置を提供する。
【課題を解決するための手段】
【００１１】
本発明は、離散対数問題に依った暗号化方式または署名方式に係るデータを圧縮するデータ圧縮装置であって、有限体の拡大次数の入力を受け、この拡大次数を素数の組で示すために素因数分解し、素因数分解結果を出力する素因数分解手段と、前記素因数分解手段で出力された前記素因数分解結果を入力するとともに、外部から有限体の標数と圧縮するデータとを入力し、有限体の標数と拡大次数とで規定され、前記圧縮するデータが含まれる代数的トーラスに、前記素因数分解結果の素数のべき指数に依存する次元を持つ入力アフィン空間を加えて、前記素因数分解結果の素数のべき指数に依存する次元を持つ出力アフィン空間へ写像する関数、テーブル、または関数とテーブルとの組へ、前記圧縮したいデータ、及び前記入力アフィン空間に属する補助入力データを供給して取得される結果データを圧縮データとして外部へ出力する圧縮手段とを備えた。
【００１２】
また、本発明は、離散対数問題に依った暗号化方式または署名方式に係るデータを圧縮するデータ圧縮装置であって、有限体の拡大次数の入力を受け、この拡大次数ｎを示す素数の組で出力するとともに、各素数のべきの積が２個以下の素数のべきの積で表されるか否かを判定し、判定結果を出力する判定手段と、前記拡大次数を示す素数の組を入力するとともに、外部から有限体の標数と圧縮するデータとを入力し、有限体の標数と拡大次数とで規定され、前記圧縮するデータが含まれる代数的トーラスに、前記拡大次数を示す素数の組の素数のべき指数に依存する次元を持つ入力アフィン空間を加えて、前記拡大次数を示す素数の組の素数のべき指数に依存する次元を持つ出力アフィン空間へ写像する関数、テーブル、または関数とテーブルとの組へ、前記圧縮したいデータ、及び前記入力アフィン空間に属する補助入力データを供給して取得される結果データを圧縮データとして外部へ出力する第１圧縮手段と、前記判定手段の判定結果を入力し、これが否であるときに、前記判定手段から入力された前記拡大次数を示す素数の組と、外部から入力された有限体の標数と圧縮するデータとを前記第１圧縮手段へ出力する切替手段とを備えた。
【００１３】
また、本発明は、離散対数問題に依った暗号化方式または署名方式に係るデータを圧縮するデータ圧縮装置へ与える拡大次数を決定するパラメータ設定装置であって、外部から入力される前記暗号化方式または署名方式のセキュリティ強度を、外部から入力される有限体の標数のビット長で除し、この結果を最小となる拡大次数と決定する最小拡大次数決定手段と、圧縮後のビット長を決定するオイラー関数を設定し、該オイラー関数の単調増加区間ごとにグループ化し、前記最小拡大次数決定手段で決定された拡大次数が属するグループを判定する判定手段と、前記判定手段で判定されたグループの一つ上のグループの下限値を求めて、該判定されたグループの閾値と設定する閾値設定手段と、該判定されたグループの下限値から前記閾値設定手段で設定した閾値までの間を、前記オイラー関数が最小となる拡大次数を探索する探索手段とを備えた。
【発明の効果】
【００１４】
本発明によれば、有限体の部分群上の離散対数問題に依った暗号／署名におけるデータ圧縮において、有限体の拡大次数ｎが一般の正整数であれば、制限なく利用できるようになった。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施の形態を詳細に説明する。
【００１６】
図１は、本実施の形態のデータ圧縮部を含むコンピュータ装置の機能ブロックの一例を示している。
【００１７】
コンピュータ装置１は、暗号／署名部１１、データ圧縮部１２、記憶部１３、及び通信部１４を備える。暗号／署名部１１は、有限群上の離散対数問題に依存した暗号方式または署名方式で暗号化または署名を実現するものであって、例えば、ＥｌＧａｍａｌ暗号を実現する機能を備えたものである。
【００１８】
データ圧縮部１２は、暗号／署名部１１によって生成された暗号文、署名文、鍵、等の各データ（以後、データαと称す）のうち、圧縮したいデータαを圧縮するものであり、入力として、データαと、パラメータとして、有限体の標数ｑと拡大次数ｎとを入力し、値の組で示される圧縮データａ→＝（ｖ１，ｖ２，・・・）を出力する。データ圧縮部１２の詳細は、後述する。
【００１９】
記憶部１３は、圧縮データａ→を記憶するものである。通信部１４は、圧縮データａ→を他のコンピュータ装置へ送るものである。なお、暗号／署名部１１、記憶部１３、通信部１４は、必ずしもコンピュータ装置１内に備える必要はないため、点線で示している。また、記憶部１３と通信部１４は、必ずしも必要なものではなく、圧縮されたデータａ→を、後にコンピュータ装置１内で利用する用途に用いる場合には、記憶部１３があれば良く、また、圧縮されたデータａ→を他の装置へ送信する用途に用いる場合には、通信部１４があれば良い。
【００２０】
次に、データ圧縮部１２内の機能ブロックを図２を用いて説明する。
【００２１】
データ圧縮部１２は、ｎ判定部２１、切替部２２、第１圧縮部２３、及び第２圧縮部２４を備える。
【００２２】
まず、ｎ判定部２１は、入力された拡大次数ｎが２個以下の素数のべきの積（１は除く）で表すことができるか否かを判定するものである。図３は、ｎ判定部２１の例を２つ示している。図３（ａ）において、ｎ判定部２１は、素因数分解部２１１と方式判定部２１２とを備えている。素因数分解部２１１は、入力されたｎを素因数分解し、分解された、各べき乗数付きの各素数（ｐ１ｅ１，・・・，ｐｋｅｋ）を出力する。出力された結果は、切替部２２へ供給されるとともに、方式判定部２１２へ供給される。方式判定部２１２は、供給された素因数分解の結果が、２個以下のｐｉｅｉであれば、“０”を出力し、２個以下のｐｉｅｉでなければ、“１”を出力する。この出力は、切替部２２へ供給される。
【００２３】
また、ｎ判定部２１は、別の例として図３（ｂ）のように構成してしても良い。これは、同図からも明らかなように、素因数分解部２１１に代え、各数ｎと、それらの素因数分解で得られる各素数（ｐ１ｅ１，・・・，ｐｋｅｋ）の結果とを予め対応付けて格納した素因数テーブル２１３を備え、入力されるｎに対応するべき乗付き素数の積、即ち数ｎを素因数分解した各素数（ｐ１ｅ１，・・・，ｐｋｅｋ）の組を出力するようしている。
【００２４】
次に、切替部２２は、入力された有限体の標数ｑ、拡大次数ｎを素因数分解した各素因数（ｐ１ｅ１，・・・，ｐｋｅｋ）、及び、データαを、第１圧縮部２３、または第２圧縮部２４へ供給するものである。切替部２２は、ｎ判定部２１からの判定結果が０の場合には第１圧縮部２３へ、１の場合には第２圧縮部２４に切り替え、これにより、ｑ、（ｐ１ｅ１，・・・，ｐｋｅｋ）、αはいずれかに供給される。なお、特に記載しなかったが、各素因数（ｐ１ｅ１，・・・，ｐｋｅｋ）のもとの値ｎも供給しても良い。
【００２５】
次に、第１圧縮部２３は、図４の、公知のＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇの圧縮方式を実装したものである。ＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇは、離散対数問題に依った暗号系に用いられる鍵と暗号文、離散対数問題に依った署名方式で生成される署名を、圧縮関数ρと伸長関数ψとを利用した代数的トーラスを用いることで圧縮している。
【００２６】
ここで、圧縮関数ρと伸長関数ψの構成の例を示す。ｎ＝６の場合には、次のように構成される。この構成方法では、ｑは９で割った余りが２または５となる素数でなければならない。まず、ｘ＝ζ３は１の原始３乗根とする。ｙ＝ζ３＋ζ３−１は１の原始９乗根と原始９乗根の逆数を足したものとする。関数ｆをｆ（ｖ１，ｖ２）＝１−ｖ１２−ｖ２２＋ｖ１ｖ２と定義する。また、圧縮後のデータをａ→と表すこととする。
【００２７】
圧縮後のデータがａ→＝（ｖ１，ｖ２）と入力されると、伸長関数ψは、
【数１】
【００２８】
と構成される。
【００２９】
一方、圧縮したいデータαが入力されるとα＝α１＋α２ｘと分解し、さらに（１＋α１）／α＝ｕ１＋ｕ２ｙ＋ｕ３（ｙ２−２）よりｕ１，ｕ２，ｕ３を得る。このｕ１，ｕ２，ｕ３を用いると、圧縮関数ρは、ρ（α）＝（ｕ２／ｕ１，ｕ３／ｕ１）＝ａ→と構成される。
【００３０】
次に、第２圧縮部２４は、公知のｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらのデータ圧縮方式を改良した本実施の形態による圧縮方式を実装したものであって、切替部２２から有限体の標数ｑと拡大次数ｎ＝ｐ１ｅ１・・・ｐｋｅｋ（但し、３個以上の素数のべきの積で表すことができる）とデータαとを入力とし、データαを、補助入力データａ’→を利用し圧縮して圧縮データａ→を出力する。
【００３１】
ここで、本実施の形態の圧縮方式の説明の前に、まずｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの圧縮方式について、簡単に説明する。ｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの圧縮方式は、ｎが相異なる素数の積である場合について、圧縮率として漸近的にｎ／φ（ｎ）を達成している。ここでｎ／φ（ｎ）は、ｎが小さい素因数を多く含む場合に大きい値を取ることが知られている。
【００３２】
図５は、ｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの圧縮方式を示したものである。同図は、圧縮したいデータαと、素数の二乗を持たない、素因数分解されたｎ＝ｐ１ｐ２・・・ｐｋと、ｑとを入力し、データαを写像して圧縮されたデータａ→を出力することを示している。なお、ｐ１，ｐ２，・・・，ｐｋは、ｎの素因数であり、またｎは相異なる素数の積でなければならないからｎ＝ｐ１ｐ２・・・ｐｋである。
【００３３】
ｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの圧縮法では以下のような写像を構成する。
【数２】
【００３４】
この写像はテーブルまたは関数で実現される。関数を用いる為には、
【数３】
【００３５】
という円分多項式の関係式の左辺が互いに素でなければならない。テーブルで実現する場
合には、ｉが２からｋ−１までの数であるとしてｐｉ＋２・・・ｐｋを割り切る全てのｄと
ｐｉ＋２・・・ｐｋを割り切る全ての（ｄと異なる）ｅに対して、
【数４】
【００３６】
なる最小のＵｉをＵｉとする。テーブルのエントリ数Ｕｉを最小とするｑを選択する。
【００３７】
一方、本実施の形態のデータ圧縮方式は、このｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの圧縮方式に、以下の数学的事実１に基づいて改良を加えたものである。
【００３８】
（数学的事実１・・・始め）
円分多項式の性質：ｐを素数、ｂを正整数として、ｐがｂを割り切るときΦｂｐ（ｘ）＝Φｂ（ｘｑ）が成り立つ。この性質を利用して代数的トーラスＴｎ（Ｆｑ）を決める円分多項式Φｎ（ｑ）を、次式のように、その次数がｎの素因数の積である円分多項式へ変形した。
【数５】
【００３９】
ここで、ｎの素因数分解をｎ＝ｐ１ｅ１ｐ２ｅ２・・・ｐｋｅｋとする。
【００４０】
この性質を用いて、ｎが相異なる素数の積であるか否かに依らずにｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの方法が使えるように改良を加えた。具体的には、本発明の圧縮方法において写像を実現するテーブルまたは関数の構成方法が、ｎを素因数分解した際の素数の巾指数に依存している。
【００４１】
（数学的事実１・・・終わり）
以上を踏まえた上、改良した本実施の形態の圧縮方式を図６に示す。同図は、圧縮したいデータαと、正整数ｑと、ｎを素数のべき指数に依存していることがわかるように素因数分解した、ｐ１ｅ１ｐ２ｅ２・・・ｐｋｅｋとを入力し、データαを写像して圧縮されたデータａ→を出力することを示している。元の値ｎも入力してもよい。より詳しくは、有限体の標数ｑと拡大次数ｎとで規定されるものであって、圧縮したいデータが含まれる代数的トーラスＴｎ（Ｆｑ）に、ｎを素因数分解した際の素数のべき指数に依存する次元を持つ入力アフィン空間を加えて、ｎを素因数分解した際の素数の巾指数に依存する次元を持つ出力アフィン空間へ写像する写像方式を取得し、この写像方式に、圧縮したいデータαと補助入力データａ’→との組を与えて計算し、計算結果を圧縮データａ→として出力するようにしている。
【００４２】
上記取得される写像方式は、以下の写像を実現するものである。
【数６】
【００４３】
ここでｐ１，ｐ２，・・・，ｐｋは、１）で素因数分解されたｎの素因数である。
【００４４】
上記取得される写像方式を第２圧縮部２４へ実装するには、１）この写像を関数で実現する方法と、２）この写像をテーブルで実現する方法と、３）この写像を代数的トーラス間の写像を実現するテーブルと圧縮関数ρと伸長関数ψとを組み合わせて実現する方法とが考えられる。
【００４５】
まず、１）（式１）の写像を関数で実現する方法について説明する。
【００４６】
（式１）の写像を関数を用いて構成するには、代数的トーラス間の写像を実現する関数σと圧縮関数ρと伸長関数ψとを組み合わせる方法がある。代数的トーラス間の写像を実現する関数σとは、代数的トーラスＴｎ（Ｆｑ）に、ｎの素因数の積を次数として持つ代数的トーラスを加えて、ｎの素因数のうち２個以下の積を次数として持つ代数的トーラスへ写像する以下の関数σである。
【数７】
【００４７】
このとき代数的トーラスが定義される有限体の拡大次数は、ｎを素因数分解した際の素数のべき指数に依存する。
【００４８】
関数σは、代数的トーラスＴｎ（Ｆｑ），Ｔｐ１ｐ２・・・ｐｉ（Ｆｑｎ／ｐ１ｐ２・・・ｐｉ+１），ｉ＝２，・・・，ｋ−１を決める円分多項式Φｎ（ｑ），Φｐ１ｐ２・・・ｐｉ（ｑｎ／ｐ１ｐ２・・・ｐｉ＋１），ｉ＝２，・・・，ｋ−１が互いに素であるときに限り構成できる。
【００４９】
そのようなｑが設定されているとすると関数σは、
【数８】
【００５０】
と構成される。ここでα，α２，・・・αｋ−１は、それぞれ代数的トーラスＴｎ（Ｆｑ），Ｔｐ１ｐ２・・・ｐｉ（Ｆｑｎ／ｐ１ｐ２・・・ｐｉ＋１），ｉ＝２，・・・，ｋ−１の要素である。
【００５１】
ｄ０，ｄ２，・・・，ｄｋ−１は、ｄ０Φｎ（ｑ）＋ｄ２Φｐ１ｐ２（ｑｎ／ｐ１・・・ｐ３）＋・・・＋ｄｋ−１Φｐ１ｐ２・・・ｐｋ−１（ｑｎ／ｐ１・・・ｐｋ）＝１から決定される。βは、Ｔｐ１ｐ２（Ｆｑｎ／ｐ１ｐ２）の要素となっている。また、逆関数は、次のようになっている。
【数９】
【００５２】
（式１）の写像を関数ζとして実現するには、次のような手順で行われる。
【００５３】
まず、圧縮したいデータαを含む、有限体の標数ｑ、拡大次数ｎで定まる代数的トーラスＴｎ（Ｆｑ）に加えられる、入力アフィン空間Ａψ（ｐ１ｐ２）ｎ／ｐ１ｐ２−ψ（ｎ）（Ｆｑ）の少なくとも一部を伸長関数ψによって、トーラスに変換する。更に、変換後のトーラスをσ−１を用いてトーラスの積へ変換する。変換結果のうち、不要な部分を
【数１０】
【００５４】
を用いてアフィンへ戻す。これらの操作を繰り返すことによって、代数的トーラスと入力アフィン空間とは、（式２）の左辺で示されるトーラスの積のみで表される。そして、（式２）の関数σを用いて、トーラスの積を有理な１つのトーラスＴｐ１ｐ２（Ｆｑｎ／ｐ１ｐ２）へ変換する。このトーラスＴｐ１ｐ２（Ｆｑｎ／ｐ１ｐ２）を圧縮関数ρを用いて、出力アフィン空間へ変換する。以上の手順は、σｉにおいても同様の手順で実現できるので、（式２）の関数ζの右辺の写像先を得ることとなる。以上のようにして関数ζを構成することができる。
【００５５】
第２圧縮部２４は、以上の手順によって、圧縮時に都度、関数ζを生成するように実装し実現しても良いし、また、標数ｑ、拡大次数ｎの多数の組み合わせによって、関数ζを多数生成してそれらを対応付けて格納しておき、入力される標数ｑと拡大次数ｎとから、格納される関数ζを検索して取得するように実装し実現しても良い。
【００５６】
以上で示した関数ζで圧縮データａ→を得るには、圧縮したいデータαの他に、補助入力データａ’→が必要である。入力アフィン空間Ａψ（ｐ１ｐ２）ｎ／ｐ１ｐ２−ψ（ｎ）（Ｆｑ）から、圧縮に必要な補助入力データａ’→を元として含む入力アフィン空間の次元ｌζ（ｎ）は、ψ（ｐ１ｐ２）ｎ／ｐ１ｐ２−ψ（ｎ）となる。従って、補助入力データａ’→は、Ｆｑの元がｌζ（ｎ）個だけ並んだものとなるから、Ｆｑの元からｌζ（ｎ）個分の元を適宜決定すればよい。これは、第２圧縮部２４内で決定しても良いし、外部から与えられるようにしても良い。
【００５７】
そして、第２圧縮部２４は、関数ζへ、圧縮したいデータαと、決定された補助入力データａ’→とを与え、計算することにより、圧縮データa→＝（ｖ１，ｖ２，・・・）を得て、これを出力する。
【００５８】
以上のようにして、第２圧縮部２４は、（式１）の写像を関数ζを用いて実現することができる。
【００５９】
ここで、（式１）の写像に対し、ｎ=ｐ１ｅ１ｐ２ｅ２ｐ３ｅ３の場合の操作を一例にとって具体例を説明する。
【００６０】
（式１）の左辺は、代数トーラスＴｎ（Ｆｑ）へ入力アフィン空間上の補助入力データ（a’→）を加えたものであるが、この入力アフィン空間上の補助入力データ（a’→）は、ｎ=ｐ１ｅ１ｐ２ｅ２ｐ３ｅ３とすると、以下の式で表される入力アフィン空間の元となる。
【数１１】
【００６１】
これを伸長関数ψを用いて、代数的トーラス上のデータへと伸長し、ψ（a’→）=α’とすると、α’は、次式となる。
【数１２】
【００６２】
すると、（式１）の左辺は、次のような代数的トーラスとして表現できる。
【数１３】
【００６３】
これは、すなわち代数的トーラスの元の組を、
【数１４】
【００６４】
の代数的トーラスの元へと写像することに相当する（これをα”とする）。これを圧縮関数ρを用いて、アフィン空間上のデータへと圧縮する。圧縮後の圧縮データは、ρ（α’’）=（a→）となる。（a→）は圧縮されたαと伸長に必要な符号からなる。
【００６５】
圧縮されたアフィン空間上のデータは、
【数１５】
【００６６】
で表される出力アフィン空間の元となる。これは、（式１）の右辺を、ｎ=ｐ１ｅ１ｐ２ｅ２ｐ３ｅ３とした場合に等しい。以上をまとめると、 ζ（α, a’→）=ρ（σ（α, ψ（a’→） ））= a→となり、この右辺は圧縮関数ρと伸長関数ψとを用いて計算できるから、圧縮データa→が計算できる。
【００６７】
次に、上記２）（式１）の写像をテーブルで実現する方法について説明する。
【００６８】
これは上記で説明した１）（式１）の写像を関数で実現する方法の上記関数ζのそれぞれへ様々なデータαと様々な補助入力データａ’→とを与えた結果得られる様々な圧縮データa→とを対応付けて格納したテーブルを備えるようにすれば、標数ｑと拡大次数ｎとデータαと補助入力データａ’→とで、テーブルを検索することによって、圧縮データａ→を得ることが可能である。但し、膨大な量のテーブルを構成する必要になり大型化は避けられない。
【００６９】
従って、テーブルを用いる方法としては、上記３）（式１）の写像を代数的トーラス間の写像を実現するテーブルと圧縮関数ρと伸長関数ψとを組み合わせる方法が現実的であり、以下に、この方法について説明する。なお、上記説明によれば、代数的トーラス間の写像は関数σに相当するが、以下の方法は、この関数σそのものをテーブルとして構成するのではなく、関数σを、テーブルと関数とを用いて構成するものである。
【００７０】
まず、説明を簡単にするために、ｎ’=ｐ１ｐ２・・・ｐｋ，q’=ｑｎ/ｎ’， ｍｉ=ｐ１ｐ２・・・ｐｉと置くと、関数σの式は次のように表すことができる。
【数１６】
【００７１】
また、
【数１７】
【００７２】
の円分多項式の関係式が成り立っているので、この円分多項式に対応した、代数的トーラスの関係式を用いると、図７のようになる。この図において、双方向の矢印で示した２箇所の計算ができれば、関数σが構成できる。ここで、
【数１８】
【００７３】
の写像を構成するには、具体的に次の計算を行う。なお、ｋ＝３のときには左辺と右辺は等しくなるため、写像を考える必要はないので、ｋ＞３について説明する。
【００７４】
まず、次の写像を関数として計算する。
【数１９】
【００７５】
この計算は、右辺の巡回群の位数を用いて、上記で説明した関数σ-1の関数と同様の方法で行う。すなわち、入力されたデータに関して、出力データが属する巡回群の位数から決まる指数でべき乗したデータの組を作る。
【００７６】
ここで、Ｕｉは、ｐｉ+２・・・ｐｋを割り切る全てのｄ≠ｅに対して、
【数２０】
【００７７】
なる最小のＵｉである。
【００７８】
また、
【数２１】
【００７９】
と定める。
【００８０】
（式３）の関数を計算した結果として得られたＧｕｉ上のデータを、更に小さな巡回群上のデータの組に写像する。この写像は、
【数２２】
【００８１】
として、表すことができるが、この写像全体をテーブル（このテーブルを以下、写像テーブルと称す）を用いて実現する。写像テーブルの構成法は後述する。
【００８２】
ここで、
【数２３】
【００８３】
と定める。（式４）より、
【数２４】
【００８４】
上のデータが得られたので、以下の写像が関数によって計算できる。
【数２５】
【００８５】
この写像間の関数の計算は、（式１）を関数で実現する方法で説明した関数σ-1の計算法と同様の方法で行う。
【００８６】
以上の操作によって、図７の双方向の矢印で示した２箇所の計算のうちの左側の計算が実現できる。以上の説明は、図８のようにまとめられる。
【００８７】
次に、図７の双方向の矢印で示した２箇所の計算のうちの左側の計算と、写像した後のデータは圧縮したいデータαとを合わせると、図７に示す、恒等式の右辺にある代数的トーラス上のデータの組に等しい。従って、今まで行ってきた逆の手順、即ち、（式５）→（式４）→（式３）の手順によって、図７の双方向の矢印で示した２箇所の計算のうちの右側の計算を行うことができる。従って、図７の双方向の矢印で示した２箇所の計算ができるので、関数σが、関数とテーブル（写像テーブル）とによって実現できるようになった。なお、以上の計算の流れを図にすると図９のようになる。
【００８８】
次に、（式４）の写像に対応する写像テーブルの構成方法について簡単に説明する。図１０は、写像テーブルの構成を説明した図である。
【００８９】
Ｇｕｉの生成元ｇとＧｚｍｉｄの生成元ｇｄを選び、ｇｊに対応するｇｄｊｄの組が一意に定まるようにｊ＝１，・・・，Ｕｉに関して作成する。例えば、ｊｄはｊをｚｍｉｄで割った余りとする。写像テーブルは、Ｕｉ個のエントリを備え、各エントリは、番地１・・・番地Ｕｉで識別される。そして、大きな巡回群の要素γ１・・・γＵｉと番地１・・・Ｕｉという対応付けをしておく。また、各エントリ内は小さな巡回群の要素としてｇｄｊｄをｄ個ずつ記憶する。なお、ｄは、ｐｉ＋２・・・ｐｋを割り切る全ての数を取るものである。
【００９０】
以上のことから、写像テーブルは、一つのエントリの長さを、ｄ｜ｐｉ＋２・・・ｐｋとなるｄの個数×各要素の長さで、このエントリをＵｉ個備えた記憶容量で構成される。
【００９１】
この写像テーブルは、大きい巡回群の要素γが入力されると、その要素γに対応する番地にエントリされる小さな巡回群の要素の組を出力する。
【００９２】
以上詳細に説明した本実施の形態によれば、特に第２圧縮部２４を備えたから、有限体の部分群上の離散対数問題に依った暗号／署名におけるデータ圧縮において、有限体の拡大次数ｎが一般の正整数であれば、制限なく利用できるようになった。
【００９３】
なお、本実施の形態では、第１圧縮部２３と第２圧縮部２４との併用で構成したが、第１圧縮部２３を無くし、全ての圧縮を第２圧縮部２４で行っても良い。この場合の構成は、図１１のような機能ブロックとなる。
【００９４】
また、（式１）の写像を関数で実現する方法で第２圧縮部２４に実装すれば、余計なメモリなどが不要になり、小型化が実現できる。
【００９５】
また、（式１）の写像をテーブルで実現する方法で第２圧縮部２４に実装すれば、大型化は避けられないが、非常に高速にデータを圧縮できる。
【００９６】
また、（式１）の写像を代数的トーラス間の写像を実現するテーブルと圧縮関数ρと伸長関数ψとを組み合わせる方法で第２圧縮部２４に実装すれば、代数的トーラス間を高速に写像できるようになり、圧縮を高速化できる。
【００９７】
次に、上記で説明した本実施の形態のデータ圧縮部１２に与えられる標数ｑ、拡大次数ｎは、最適な値であれば効率的な圧縮が実現される。そこで、セキュリティ強度Ｓ（＝ｎｌｏｇｑ）とｑのビット数Ｂ（＝ｌｏｇｑ）を入力とし、最適な標数ｑ、拡大次数ｎ出力するパラメータ設定部の実現方法について、説明する。
【００９８】
図１２は、パラメータ設定部３１の機能ブロックを示したものである。パラメータ設定部３１は、入力部３２と、ｎ決定部３３と、ｑ決定部３４と、パラメータ出力部３５とを備える。
【００９９】
入力部３２は、外部からユーザの指示などによって与えられたセキュリティ強度Ｓ（＝ｎｌｏｇｑ）とｑのビット数Ｂ（＝ｌｏｇｑ）との入力を受けるものである。
【０１００】
ｎ決定部３３は、入力部から、セキュリティ強度Ｓ（＝ｎｌｏｇｑ）とｑのビット数Ｂとを受けて、後述する所定の方法によって、最適なｎを求めるものである。
【０１０１】
ｑ決定部３４は、ｎ決定部３３で求められたｎ及び、実現される圧縮方式に基づいて、後述する方法によって、最適なｑを求めるものである。
【０１０２】
パラメータ出力部３５は、求められた最適なｎ及びｑをデータ圧縮部１２へ供給するものである。
【０１０３】
次にｎ決定部３３について詳細に説明する。ｎ決定部３３では、セキュリティ強度Ｓ（＝ｎｌｏｇｑ）とｑのビット長から、与えられたセキュリティ強度を満たし圧縮後のビット数が最も小さくなるｎを選ぶ。圧縮前にｎｌｏｇｑビットであったデータは、圧縮率ｎ／φ（ｎ）で圧縮すると圧縮後のビット数φ（ｎ）ｌｏｇｑビットとなる。ｑのビット長ｌｏｇｑを与えると、圧縮後のビット数を決めているのはオイラー関数φ（ｎ）である。次に示すオイラー関数の下限の性質を用いると、ｎを探索する範囲を適切に設定して、不必要な探索を行わず効率的に探索できる。
【０１０４】
オイラー関数の下限の性質とは、ｎｋを小さい方から数えてｋ番目までの素数を全て掛け合わせた数とすると、ｎｋからｎｋ＋１に到達するまでの間オイラー関数の下限は単調に増加し、ｎｋ＋１で急激に減少するというものである。
【０１０５】
ｎ決定部３３は、図１３にｎの決定法全体の処理の流れを示すが、大別すると以下のステップで動作する。
【０１０６】
１）セキュリティ強度と有限体の標数ｑのビット長Ｂからｎの最小値を決定するステップ
２）ｎの最小値が属する数のグループを判定するステップ
３）閾値を作成するステップ
４）オイラー関数の下限の性質を用いて、オイラー関数が最小となるｎを探索するステップ。
【０１０７】
上記１）のステップでは、ｎの最小値としてＳ／Ｂを計算する。結果をｎｍｉｎ＝Ｓ／Ｂとして記憶する。
【０１０８】
上記２）のステップでは、ｎｍｉｎが属するグループのｋを求める。圧縮後のビット数を決定するオイラー関数の下限はｎの関数である。ｎｋからｎｋ＋１に到達するまでの間オイラー関数の下限は単調に増加し、この範囲にある数を第ｋグループの数と呼ぶ。
【０１０９】
上記３）のステップでは、第ｋグループにおけるｎｋ＋１での下限と等しい下限を持つｎｘを求める（図１４参照）。
【０１１０】
上記４）のステップでは、オイラー関数の下限の性質を用いて、オイラー関数が最小となるｎを探索する
この探索においては、ｎｍｉｎがｎｘ以下である場合（図１５参照）、まず初期値の設定を行う。ｍｉｎにはオイラー関数の最小値を格納する。初期値はｍｉｎ＝φ（ｎｍｉｎ）とする。ｎの探索はｎｍｉｎから始める。探索している位置をｎｔｅｍｐで表し、その初期値をｎｔｅｍｐ＝ｎｍｉｎとする。オイラー関数の最小値を更新したときのｎｔｅｍｐの値をｎとして記憶する。初期値はｎ＝ｎｍｉｎとする。
【０１１１】
ｎｔｅｍｐでのオイラー関数の下限がｍｉｎより小さい期間、探索を繰り返す。
【０１１２】
探索は、圧縮後のビット数が最も小さくなるｎを探す。ｎｔｅｍｐとしてｎｍｉｎから値を１つずつ増やしｎｔｅｍｐにおけるオイラー関数の値がｍｉｎよりも小さいとき、その値をｍｉｎへ上書きし、そのときのｎｔｅｍｐをｎとして記憶する。
【０１１３】
一方、ｎｍｉｎがｎｘよりも大きい場合（図１６参照）、その値ｎｍｉｎからｎｋ＋１に到達するまでのオイラ−関数は必ずｎｋ＋１でのオイラー関数よりも大きくなる。よってｎ＝ｎk＋１とする。
【０１１４】
これにより、最良のｎが求まる。
【０１１５】
次に、ｑ決定部３４におけるｑの決定法は、ｎと圧縮方法をどのように実現するかに依る。まずｑはＢビットでなければならない。
【０１１６】
本実施の形態の圧縮法において写像を実現するテーブル（または関数）は、代数的トーラス間のテーブル（または関数）とＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇの圧縮関数ρと伸長関数ψで構成される。まず、ＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇの圧縮関数ρと伸長関数ψを構成するために以下の条件が課せられる。上記で示したＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇの圧縮法でｎ＝６の場合の例では、ｑは９で割った余りが２または５となる素数でなければならない。代数的トーラス間の関数を用いる為には、
【数２６】
【０１１７】
という円分多項式の関係式の左辺が互いに素でなければならない。代数的トーラス間のテーブルを用いる場合、テーブルのサイズはＵｉで決定される。Ｕｉは、ｎとｑとで定まる。
【０１１８】
具体的には、ｉが２からｋ−１までの数であるとしてｐｉ＋２・・・ｐｋを割り切る全てのｄと、ｐｉ＋２・・・ｐｋを割り切る全てのｄ≠ｅに対して、
【数２７】
【０１１９】
なる最小のＵｉをＵｉとする。ここで、ｎの素因数分解をｎ=ｐ１ｅ１ｐ２ｅ２・・・ｐｋｅｋとした。よって、テーブルのエントリ数Ｕ＝ΣｉＵｉを最小とするｑを選択する。
【０１２０】
以上のようにして、パラメータｎ，ｑを決定することにより、最適なパラメータｎ，ｑを決定できる。
【図面の簡単な説明】
【０１２１】
【図１】本実施の形態のデータ圧縮部を含むコンピュータ装置の機能ブロックの一例を示す図。
【図２】データ圧縮部１２内の機能ブロックを示す図。
【図３】ｎ判定部２１の例を示す図。
【図４】ＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇの圧縮方式を示す図。
【図５】ｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの圧縮方式を示す図。
【図６】本実施の形態の圧縮方式を示す図。
【図７】円分多項式に対応した、代数的トーラスの関係式を用いた場合の図。
【図８】これまでの説明を纏めた図。
【図９】これまでの計算の流れを示した図。
【図１０】写像テーブルの構成を説明した図
【図１１】全ての圧縮を第２圧縮部２４で行う構成の、データ圧縮部の機能ブロックを示す図。
【図１２】パラメータ設定部３１の機能ブロックを示す図。
【図１３】ｎの決定法全体の処理の流れを示す図。
【図１４】オイラー関数を示したグラフ。
【図１５】オイラー関数を示したグラフ。
【図１６】オイラー関数を示したグラフ。
【符号の説明】
【０１２２】
１・・・コンピュータ装置１
１１・・・暗号／署名部
１２・・・データ圧縮部
１３・・・記憶部
１４・・・通信部
２１・・・ｎ判定部
２２・・・切替部
２３・・・第１圧縮部
２４・・・第２圧縮部
３１・・・パラメータ設定部
３２・・・入力部
３３・・・ｎ決定部
３４・・・ｑ決定部
３５・・・パラメータ出力部
２１１・・・素因数分解部
２１２・・・方式判定部
２１３・・・素因数テーブル
【技術分野】
【０００１】
本発明は離散対数問題に依った暗号系のデータ圧縮に関する。
【背景技術】
【０００２】
ネットワークの利便性の向上や、ハードディスク装置や、不揮発性メモリなどの技術進歩により、ますますデジタルデータの流通が盛んになってきており、これに伴って、デジタルデータを安全に流通させるために、暗号技術や署名技術もより重要になってきている。
【０００３】
暗号技術や署名技術の一つのカテゴリとして、例えばＥｌＧａｍａｌ暗号／署名のような有限群上の離散対数問題に依った暗号／署名方式がある。しかしながら、この有限群上の離散対数問題に依った暗号／署名方式は、鍵、暗号文、署名などが長く、このことが利便性を損ねている大きな要因の１つであった。
【０００４】
有限群上の離散対数問題に依った暗号／署名方式では、有限群としては有限体の部分群が用いられるものが多い。このような方式のとき、部分群の元の個数は有限体の大きさに比べるとかなり小さい場合がある。もし、有限体の要素より少ないｂｉｔ数で部分群を効率よく表現できるとすると、それは鍵長や暗号文長、署名長を圧縮できることにつながる。
【０００５】
ＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇは、離散対数問題に依った暗号系に用いられる鍵と暗号文、離散対数問題に依った署名方式で生成される署名を代数的トーラスを用いることで圧縮する方法を開示している（非特許文献1参照）。以下では、有限体の標数ｑ、拡大次数ｎとし説明する。非特許文献１では、圧縮関数ρと伸長関数ψを構成し、ｎが２個以下の素数の巾の積である場合について圧縮率ｒ＝ｎ／φ（ｎ）を達成した。ここで圧縮率ｒは鍵等のビット長が圧縮により１／ｒ倍になることと定義される。φはオイラー関数である。
【０００６】
ｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらは、非特許文献１の方法を改良し、ｎが相異なる素数の積である場合について、圧縮率として漸近的にｎ／φ（ｎ）を達成する圧縮方法を開示している（非特許文献２参照）。ここでｎ／φ（ｎ）は、ｎが小さい素因数を多く含む場合に大きい値を取ることが知られている。
【非特許文献１】Ｋ．Ｒｕｂｉｎ ａｎｄ Ａ． Ｓｉｌｖｅｒｂｅｒｇ， Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ． Ｃｒｙｐｔｏ’０３， ＬＮＣＳ ２７２９， ３４９−３６５
【非特許文献２】Ｍ． ｖａｎ Ｄｉｊｋ ａｎｄ Ｄ． Ｗｏｏｄｒｕｆｆ，Ａｓｙｍｐｔｏｔｉｃａｌｌｙ Ｏｐｔｉｍａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ｆｏｒ Ｔｏｒｕｓ−Ｂａｓｅｄ Ｃｒｙｔｏｇｒａｐｈｙ． Ｃｒｙｐｔｏ’０４， ＬＮＣＳ３１５２， １５７−１７８
【発明の開示】
【発明が解決しようとする課題】
【０００７】
有限体の部分群上の離散対数問題に依った暗号／署名におけるデータ圧縮法として、有限体の拡大次数ｎが一般の正整数であれば、利用に制限がなく利用価値が高い。
【０００８】
しかしながら、上記非特許文献１に開示される圧縮技術は、ｎの条件によって圧縮率ｒが大きな値を取らないため、限定的にしか利用できないという問題があった。なお、この方法を用いた場合の圧縮率ｒの上限は３である。
【０００９】
また、上記非特許文献２に開示される圧縮技術は、大きな圧縮率ｒを取るｎの個数が少ないためにｎの選択に大きな制約を受けるから利用がし難かったという問題があった。
【００１０】
そこで、本発明は、有限体の部分群上の離散対数問題に依った暗号／署名におけるデータ圧縮法として、有限体の拡大次数ｎが一般の正整数であれば、制限なく利用できるよう好適なデータ圧縮装置、および、これに利用されるパラメータ設定装置を提供する。
【課題を解決するための手段】
【００１１】
本発明は、離散対数問題に依った暗号化方式または署名方式に係るデータを圧縮するデータ圧縮装置であって、有限体の拡大次数の入力を受け、この拡大次数を素数の組で示すために素因数分解し、素因数分解結果を出力する素因数分解手段と、前記素因数分解手段で出力された前記素因数分解結果を入力するとともに、外部から有限体の標数と圧縮するデータとを入力し、有限体の標数と拡大次数とで規定され、前記圧縮するデータが含まれる代数的トーラスに、前記素因数分解結果の素数のべき指数に依存する次元を持つ入力アフィン空間を加えて、前記素因数分解結果の素数のべき指数に依存する次元を持つ出力アフィン空間へ写像する関数、テーブル、または関数とテーブルとの組へ、前記圧縮したいデータ、及び前記入力アフィン空間に属する補助入力データを供給して取得される結果データを圧縮データとして外部へ出力する圧縮手段とを備えた。
【００１２】
また、本発明は、離散対数問題に依った暗号化方式または署名方式に係るデータを圧縮するデータ圧縮装置であって、有限体の拡大次数の入力を受け、この拡大次数ｎを示す素数の組で出力するとともに、各素数のべきの積が２個以下の素数のべきの積で表されるか否かを判定し、判定結果を出力する判定手段と、前記拡大次数を示す素数の組を入力するとともに、外部から有限体の標数と圧縮するデータとを入力し、有限体の標数と拡大次数とで規定され、前記圧縮するデータが含まれる代数的トーラスに、前記拡大次数を示す素数の組の素数のべき指数に依存する次元を持つ入力アフィン空間を加えて、前記拡大次数を示す素数の組の素数のべき指数に依存する次元を持つ出力アフィン空間へ写像する関数、テーブル、または関数とテーブルとの組へ、前記圧縮したいデータ、及び前記入力アフィン空間に属する補助入力データを供給して取得される結果データを圧縮データとして外部へ出力する第１圧縮手段と、前記判定手段の判定結果を入力し、これが否であるときに、前記判定手段から入力された前記拡大次数を示す素数の組と、外部から入力された有限体の標数と圧縮するデータとを前記第１圧縮手段へ出力する切替手段とを備えた。
【００１３】
また、本発明は、離散対数問題に依った暗号化方式または署名方式に係るデータを圧縮するデータ圧縮装置へ与える拡大次数を決定するパラメータ設定装置であって、外部から入力される前記暗号化方式または署名方式のセキュリティ強度を、外部から入力される有限体の標数のビット長で除し、この結果を最小となる拡大次数と決定する最小拡大次数決定手段と、圧縮後のビット長を決定するオイラー関数を設定し、該オイラー関数の単調増加区間ごとにグループ化し、前記最小拡大次数決定手段で決定された拡大次数が属するグループを判定する判定手段と、前記判定手段で判定されたグループの一つ上のグループの下限値を求めて、該判定されたグループの閾値と設定する閾値設定手段と、該判定されたグループの下限値から前記閾値設定手段で設定した閾値までの間を、前記オイラー関数が最小となる拡大次数を探索する探索手段とを備えた。
【発明の効果】
【００１４】
本発明によれば、有限体の部分群上の離散対数問題に依った暗号／署名におけるデータ圧縮において、有限体の拡大次数ｎが一般の正整数であれば、制限なく利用できるようになった。
【発明を実施するための最良の形態】
【００１５】
以下、本発明の実施の形態を詳細に説明する。
【００１６】
図１は、本実施の形態のデータ圧縮部を含むコンピュータ装置の機能ブロックの一例を示している。
【００１７】
コンピュータ装置１は、暗号／署名部１１、データ圧縮部１２、記憶部１３、及び通信部１４を備える。暗号／署名部１１は、有限群上の離散対数問題に依存した暗号方式または署名方式で暗号化または署名を実現するものであって、例えば、ＥｌＧａｍａｌ暗号を実現する機能を備えたものである。
【００１８】
データ圧縮部１２は、暗号／署名部１１によって生成された暗号文、署名文、鍵、等の各データ（以後、データαと称す）のうち、圧縮したいデータαを圧縮するものであり、入力として、データαと、パラメータとして、有限体の標数ｑと拡大次数ｎとを入力し、値の組で示される圧縮データａ→＝（ｖ１，ｖ２，・・・）を出力する。データ圧縮部１２の詳細は、後述する。
【００１９】
記憶部１３は、圧縮データａ→を記憶するものである。通信部１４は、圧縮データａ→を他のコンピュータ装置へ送るものである。なお、暗号／署名部１１、記憶部１３、通信部１４は、必ずしもコンピュータ装置１内に備える必要はないため、点線で示している。また、記憶部１３と通信部１４は、必ずしも必要なものではなく、圧縮されたデータａ→を、後にコンピュータ装置１内で利用する用途に用いる場合には、記憶部１３があれば良く、また、圧縮されたデータａ→を他の装置へ送信する用途に用いる場合には、通信部１４があれば良い。
【００２０】
次に、データ圧縮部１２内の機能ブロックを図２を用いて説明する。
【００２１】
データ圧縮部１２は、ｎ判定部２１、切替部２２、第１圧縮部２３、及び第２圧縮部２４を備える。
【００２２】
まず、ｎ判定部２１は、入力された拡大次数ｎが２個以下の素数のべきの積（１は除く）で表すことができるか否かを判定するものである。図３は、ｎ判定部２１の例を２つ示している。図３（ａ）において、ｎ判定部２１は、素因数分解部２１１と方式判定部２１２とを備えている。素因数分解部２１１は、入力されたｎを素因数分解し、分解された、各べき乗数付きの各素数（ｐ１ｅ１，・・・，ｐｋｅｋ）を出力する。出力された結果は、切替部２２へ供給されるとともに、方式判定部２１２へ供給される。方式判定部２１２は、供給された素因数分解の結果が、２個以下のｐｉｅｉであれば、“０”を出力し、２個以下のｐｉｅｉでなければ、“１”を出力する。この出力は、切替部２２へ供給される。
【００２３】
また、ｎ判定部２１は、別の例として図３（ｂ）のように構成してしても良い。これは、同図からも明らかなように、素因数分解部２１１に代え、各数ｎと、それらの素因数分解で得られる各素数（ｐ１ｅ１，・・・，ｐｋｅｋ）の結果とを予め対応付けて格納した素因数テーブル２１３を備え、入力されるｎに対応するべき乗付き素数の積、即ち数ｎを素因数分解した各素数（ｐ１ｅ１，・・・，ｐｋｅｋ）の組を出力するようしている。
【００２４】
次に、切替部２２は、入力された有限体の標数ｑ、拡大次数ｎを素因数分解した各素因数（ｐ１ｅ１，・・・，ｐｋｅｋ）、及び、データαを、第１圧縮部２３、または第２圧縮部２４へ供給するものである。切替部２２は、ｎ判定部２１からの判定結果が０の場合には第１圧縮部２３へ、１の場合には第２圧縮部２４に切り替え、これにより、ｑ、（ｐ１ｅ１，・・・，ｐｋｅｋ）、αはいずれかに供給される。なお、特に記載しなかったが、各素因数（ｐ１ｅ１，・・・，ｐｋｅｋ）のもとの値ｎも供給しても良い。
【００２５】
次に、第１圧縮部２３は、図４の、公知のＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇの圧縮方式を実装したものである。ＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇは、離散対数問題に依った暗号系に用いられる鍵と暗号文、離散対数問題に依った署名方式で生成される署名を、圧縮関数ρと伸長関数ψとを利用した代数的トーラスを用いることで圧縮している。
【００２６】
ここで、圧縮関数ρと伸長関数ψの構成の例を示す。ｎ＝６の場合には、次のように構成される。この構成方法では、ｑは９で割った余りが２または５となる素数でなければならない。まず、ｘ＝ζ３は１の原始３乗根とする。ｙ＝ζ３＋ζ３−１は１の原始９乗根と原始９乗根の逆数を足したものとする。関数ｆをｆ（ｖ１，ｖ２）＝１−ｖ１２−ｖ２２＋ｖ１ｖ２と定義する。また、圧縮後のデータをａ→と表すこととする。
【００２７】
圧縮後のデータがａ→＝（ｖ１，ｖ２）と入力されると、伸長関数ψは、
【数１】
【００２８】
と構成される。
【００２９】
一方、圧縮したいデータαが入力されるとα＝α１＋α２ｘと分解し、さらに（１＋α１）／α＝ｕ１＋ｕ２ｙ＋ｕ３（ｙ２−２）よりｕ１，ｕ２，ｕ３を得る。このｕ１，ｕ２，ｕ３を用いると、圧縮関数ρは、ρ（α）＝（ｕ２／ｕ１，ｕ３／ｕ１）＝ａ→と構成される。
【００３０】
次に、第２圧縮部２４は、公知のｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらのデータ圧縮方式を改良した本実施の形態による圧縮方式を実装したものであって、切替部２２から有限体の標数ｑと拡大次数ｎ＝ｐ１ｅ１・・・ｐｋｅｋ（但し、３個以上の素数のべきの積で表すことができる）とデータαとを入力とし、データαを、補助入力データａ’→を利用し圧縮して圧縮データａ→を出力する。
【００３１】
ここで、本実施の形態の圧縮方式の説明の前に、まずｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの圧縮方式について、簡単に説明する。ｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの圧縮方式は、ｎが相異なる素数の積である場合について、圧縮率として漸近的にｎ／φ（ｎ）を達成している。ここでｎ／φ（ｎ）は、ｎが小さい素因数を多く含む場合に大きい値を取ることが知られている。
【００３２】
図５は、ｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの圧縮方式を示したものである。同図は、圧縮したいデータαと、素数の二乗を持たない、素因数分解されたｎ＝ｐ１ｐ２・・・ｐｋと、ｑとを入力し、データαを写像して圧縮されたデータａ→を出力することを示している。なお、ｐ１，ｐ２，・・・，ｐｋは、ｎの素因数であり、またｎは相異なる素数の積でなければならないからｎ＝ｐ１ｐ２・・・ｐｋである。
【００３３】
ｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの圧縮法では以下のような写像を構成する。
【数２】
【００３４】
この写像はテーブルまたは関数で実現される。関数を用いる為には、
【数３】
【００３５】
という円分多項式の関係式の左辺が互いに素でなければならない。テーブルで実現する場
合には、ｉが２からｋ−１までの数であるとしてｐｉ＋２・・・ｐｋを割り切る全てのｄと
ｐｉ＋２・・・ｐｋを割り切る全ての（ｄと異なる）ｅに対して、
【数４】
【００３６】
なる最小のＵｉをＵｉとする。テーブルのエントリ数Ｕｉを最小とするｑを選択する。
【００３７】
一方、本実施の形態のデータ圧縮方式は、このｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの圧縮方式に、以下の数学的事実１に基づいて改良を加えたものである。
【００３８】
（数学的事実１・・・始め）
円分多項式の性質：ｐを素数、ｂを正整数として、ｐがｂを割り切るときΦｂｐ（ｘ）＝Φｂ（ｘｑ）が成り立つ。この性質を利用して代数的トーラスＴｎ（Ｆｑ）を決める円分多項式Φｎ（ｑ）を、次式のように、その次数がｎの素因数の積である円分多項式へ変形した。
【数５】
【００３９】
ここで、ｎの素因数分解をｎ＝ｐ１ｅ１ｐ２ｅ２・・・ｐｋｅｋとする。
【００４０】
この性質を用いて、ｎが相異なる素数の積であるか否かに依らずにｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの方法が使えるように改良を加えた。具体的には、本発明の圧縮方法において写像を実現するテーブルまたは関数の構成方法が、ｎを素因数分解した際の素数の巾指数に依存している。
【００４１】
（数学的事実１・・・終わり）
以上を踏まえた上、改良した本実施の形態の圧縮方式を図６に示す。同図は、圧縮したいデータαと、正整数ｑと、ｎを素数のべき指数に依存していることがわかるように素因数分解した、ｐ１ｅ１ｐ２ｅ２・・・ｐｋｅｋとを入力し、データαを写像して圧縮されたデータａ→を出力することを示している。元の値ｎも入力してもよい。より詳しくは、有限体の標数ｑと拡大次数ｎとで規定されるものであって、圧縮したいデータが含まれる代数的トーラスＴｎ（Ｆｑ）に、ｎを素因数分解した際の素数のべき指数に依存する次元を持つ入力アフィン空間を加えて、ｎを素因数分解した際の素数の巾指数に依存する次元を持つ出力アフィン空間へ写像する写像方式を取得し、この写像方式に、圧縮したいデータαと補助入力データａ’→との組を与えて計算し、計算結果を圧縮データａ→として出力するようにしている。
【００４２】
上記取得される写像方式は、以下の写像を実現するものである。
【数６】
【００４３】
ここでｐ１，ｐ２，・・・，ｐｋは、１）で素因数分解されたｎの素因数である。
【００４４】
上記取得される写像方式を第２圧縮部２４へ実装するには、１）この写像を関数で実現する方法と、２）この写像をテーブルで実現する方法と、３）この写像を代数的トーラス間の写像を実現するテーブルと圧縮関数ρと伸長関数ψとを組み合わせて実現する方法とが考えられる。
【００４５】
まず、１）（式１）の写像を関数で実現する方法について説明する。
【００４６】
（式１）の写像を関数を用いて構成するには、代数的トーラス間の写像を実現する関数σと圧縮関数ρと伸長関数ψとを組み合わせる方法がある。代数的トーラス間の写像を実現する関数σとは、代数的トーラスＴｎ（Ｆｑ）に、ｎの素因数の積を次数として持つ代数的トーラスを加えて、ｎの素因数のうち２個以下の積を次数として持つ代数的トーラスへ写像する以下の関数σである。
【数７】
【００４７】
このとき代数的トーラスが定義される有限体の拡大次数は、ｎを素因数分解した際の素数のべき指数に依存する。
【００４８】
関数σは、代数的トーラスＴｎ（Ｆｑ），Ｔｐ１ｐ２・・・ｐｉ（Ｆｑｎ／ｐ１ｐ２・・・ｐｉ+１），ｉ＝２，・・・，ｋ−１を決める円分多項式Φｎ（ｑ），Φｐ１ｐ２・・・ｐｉ（ｑｎ／ｐ１ｐ２・・・ｐｉ＋１），ｉ＝２，・・・，ｋ−１が互いに素であるときに限り構成できる。
【００４９】
そのようなｑが設定されているとすると関数σは、
【数８】
【００５０】
と構成される。ここでα，α２，・・・αｋ−１は、それぞれ代数的トーラスＴｎ（Ｆｑ），Ｔｐ１ｐ２・・・ｐｉ（Ｆｑｎ／ｐ１ｐ２・・・ｐｉ＋１），ｉ＝２，・・・，ｋ−１の要素である。
【００５１】
ｄ０，ｄ２，・・・，ｄｋ−１は、ｄ０Φｎ（ｑ）＋ｄ２Φｐ１ｐ２（ｑｎ／ｐ１・・・ｐ３）＋・・・＋ｄｋ−１Φｐ１ｐ２・・・ｐｋ−１（ｑｎ／ｐ１・・・ｐｋ）＝１から決定される。βは、Ｔｐ１ｐ２（Ｆｑｎ／ｐ１ｐ２）の要素となっている。また、逆関数は、次のようになっている。
【数９】
【００５２】
（式１）の写像を関数ζとして実現するには、次のような手順で行われる。
【００５３】
まず、圧縮したいデータαを含む、有限体の標数ｑ、拡大次数ｎで定まる代数的トーラスＴｎ（Ｆｑ）に加えられる、入力アフィン空間Ａψ（ｐ１ｐ２）ｎ／ｐ１ｐ２−ψ（ｎ）（Ｆｑ）の少なくとも一部を伸長関数ψによって、トーラスに変換する。更に、変換後のトーラスをσ−１を用いてトーラスの積へ変換する。変換結果のうち、不要な部分を
【数１０】
【００５４】
を用いてアフィンへ戻す。これらの操作を繰り返すことによって、代数的トーラスと入力アフィン空間とは、（式２）の左辺で示されるトーラスの積のみで表される。そして、（式２）の関数σを用いて、トーラスの積を有理な１つのトーラスＴｐ１ｐ２（Ｆｑｎ／ｐ１ｐ２）へ変換する。このトーラスＴｐ１ｐ２（Ｆｑｎ／ｐ１ｐ２）を圧縮関数ρを用いて、出力アフィン空間へ変換する。以上の手順は、σｉにおいても同様の手順で実現できるので、（式２）の関数ζの右辺の写像先を得ることとなる。以上のようにして関数ζを構成することができる。
【００５５】
第２圧縮部２４は、以上の手順によって、圧縮時に都度、関数ζを生成するように実装し実現しても良いし、また、標数ｑ、拡大次数ｎの多数の組み合わせによって、関数ζを多数生成してそれらを対応付けて格納しておき、入力される標数ｑと拡大次数ｎとから、格納される関数ζを検索して取得するように実装し実現しても良い。
【００５６】
以上で示した関数ζで圧縮データａ→を得るには、圧縮したいデータαの他に、補助入力データａ’→が必要である。入力アフィン空間Ａψ（ｐ１ｐ２）ｎ／ｐ１ｐ２−ψ（ｎ）（Ｆｑ）から、圧縮に必要な補助入力データａ’→を元として含む入力アフィン空間の次元ｌζ（ｎ）は、ψ（ｐ１ｐ２）ｎ／ｐ１ｐ２−ψ（ｎ）となる。従って、補助入力データａ’→は、Ｆｑの元がｌζ（ｎ）個だけ並んだものとなるから、Ｆｑの元からｌζ（ｎ）個分の元を適宜決定すればよい。これは、第２圧縮部２４内で決定しても良いし、外部から与えられるようにしても良い。
【００５７】
そして、第２圧縮部２４は、関数ζへ、圧縮したいデータαと、決定された補助入力データａ’→とを与え、計算することにより、圧縮データa→＝（ｖ１，ｖ２，・・・）を得て、これを出力する。
【００５８】
以上のようにして、第２圧縮部２４は、（式１）の写像を関数ζを用いて実現することができる。
【００５９】
ここで、（式１）の写像に対し、ｎ=ｐ１ｅ１ｐ２ｅ２ｐ３ｅ３の場合の操作を一例にとって具体例を説明する。
【００６０】
（式１）の左辺は、代数トーラスＴｎ（Ｆｑ）へ入力アフィン空間上の補助入力データ（a’→）を加えたものであるが、この入力アフィン空間上の補助入力データ（a’→）は、ｎ=ｐ１ｅ１ｐ２ｅ２ｐ３ｅ３とすると、以下の式で表される入力アフィン空間の元となる。
【数１１】
【００６１】
これを伸長関数ψを用いて、代数的トーラス上のデータへと伸長し、ψ（a’→）=α’とすると、α’は、次式となる。
【数１２】
【００６２】
すると、（式１）の左辺は、次のような代数的トーラスとして表現できる。
【数１３】
【００６３】
これは、すなわち代数的トーラスの元の組を、
【数１４】
【００６４】
の代数的トーラスの元へと写像することに相当する（これをα”とする）。これを圧縮関数ρを用いて、アフィン空間上のデータへと圧縮する。圧縮後の圧縮データは、ρ（α’’）=（a→）となる。（a→）は圧縮されたαと伸長に必要な符号からなる。
【００６５】
圧縮されたアフィン空間上のデータは、
【数１５】
【００６６】
で表される出力アフィン空間の元となる。これは、（式１）の右辺を、ｎ=ｐ１ｅ１ｐ２ｅ２ｐ３ｅ３とした場合に等しい。以上をまとめると、 ζ（α, a’→）=ρ（σ（α, ψ（a’→） ））= a→となり、この右辺は圧縮関数ρと伸長関数ψとを用いて計算できるから、圧縮データa→が計算できる。
【００６７】
次に、上記２）（式１）の写像をテーブルで実現する方法について説明する。
【００６８】
これは上記で説明した１）（式１）の写像を関数で実現する方法の上記関数ζのそれぞれへ様々なデータαと様々な補助入力データａ’→とを与えた結果得られる様々な圧縮データa→とを対応付けて格納したテーブルを備えるようにすれば、標数ｑと拡大次数ｎとデータαと補助入力データａ’→とで、テーブルを検索することによって、圧縮データａ→を得ることが可能である。但し、膨大な量のテーブルを構成する必要になり大型化は避けられない。
【００６９】
従って、テーブルを用いる方法としては、上記３）（式１）の写像を代数的トーラス間の写像を実現するテーブルと圧縮関数ρと伸長関数ψとを組み合わせる方法が現実的であり、以下に、この方法について説明する。なお、上記説明によれば、代数的トーラス間の写像は関数σに相当するが、以下の方法は、この関数σそのものをテーブルとして構成するのではなく、関数σを、テーブルと関数とを用いて構成するものである。
【００７０】
まず、説明を簡単にするために、ｎ’=ｐ１ｐ２・・・ｐｋ，q’=ｑｎ/ｎ’， ｍｉ=ｐ１ｐ２・・・ｐｉと置くと、関数σの式は次のように表すことができる。
【数１６】
【００７１】
また、
【数１７】
【００７２】
の円分多項式の関係式が成り立っているので、この円分多項式に対応した、代数的トーラスの関係式を用いると、図７のようになる。この図において、双方向の矢印で示した２箇所の計算ができれば、関数σが構成できる。ここで、
【数１８】
【００７３】
の写像を構成するには、具体的に次の計算を行う。なお、ｋ＝３のときには左辺と右辺は等しくなるため、写像を考える必要はないので、ｋ＞３について説明する。
【００７４】
まず、次の写像を関数として計算する。
【数１９】
【００７５】
この計算は、右辺の巡回群の位数を用いて、上記で説明した関数σ-1の関数と同様の方法で行う。すなわち、入力されたデータに関して、出力データが属する巡回群の位数から決まる指数でべき乗したデータの組を作る。
【００７６】
ここで、Ｕｉは、ｐｉ+２・・・ｐｋを割り切る全てのｄ≠ｅに対して、
【数２０】
【００７７】
なる最小のＵｉである。
【００７８】
また、
【数２１】
【００７９】
と定める。
【００８０】
（式３）の関数を計算した結果として得られたＧｕｉ上のデータを、更に小さな巡回群上のデータの組に写像する。この写像は、
【数２２】
【００８１】
として、表すことができるが、この写像全体をテーブル（このテーブルを以下、写像テーブルと称す）を用いて実現する。写像テーブルの構成法は後述する。
【００８２】
ここで、
【数２３】
【００８３】
と定める。（式４）より、
【数２４】
【００８４】
上のデータが得られたので、以下の写像が関数によって計算できる。
【数２５】
【００８５】
この写像間の関数の計算は、（式１）を関数で実現する方法で説明した関数σ-1の計算法と同様の方法で行う。
【００８６】
以上の操作によって、図７の双方向の矢印で示した２箇所の計算のうちの左側の計算が実現できる。以上の説明は、図８のようにまとめられる。
【００８７】
次に、図７の双方向の矢印で示した２箇所の計算のうちの左側の計算と、写像した後のデータは圧縮したいデータαとを合わせると、図７に示す、恒等式の右辺にある代数的トーラス上のデータの組に等しい。従って、今まで行ってきた逆の手順、即ち、（式５）→（式４）→（式３）の手順によって、図７の双方向の矢印で示した２箇所の計算のうちの右側の計算を行うことができる。従って、図７の双方向の矢印で示した２箇所の計算ができるので、関数σが、関数とテーブル（写像テーブル）とによって実現できるようになった。なお、以上の計算の流れを図にすると図９のようになる。
【００８８】
次に、（式４）の写像に対応する写像テーブルの構成方法について簡単に説明する。図１０は、写像テーブルの構成を説明した図である。
【００８９】
Ｇｕｉの生成元ｇとＧｚｍｉｄの生成元ｇｄを選び、ｇｊに対応するｇｄｊｄの組が一意に定まるようにｊ＝１，・・・，Ｕｉに関して作成する。例えば、ｊｄはｊをｚｍｉｄで割った余りとする。写像テーブルは、Ｕｉ個のエントリを備え、各エントリは、番地１・・・番地Ｕｉで識別される。そして、大きな巡回群の要素γ１・・・γＵｉと番地１・・・Ｕｉという対応付けをしておく。また、各エントリ内は小さな巡回群の要素としてｇｄｊｄをｄ個ずつ記憶する。なお、ｄは、ｐｉ＋２・・・ｐｋを割り切る全ての数を取るものである。
【００９０】
以上のことから、写像テーブルは、一つのエントリの長さを、ｄ｜ｐｉ＋２・・・ｐｋとなるｄの個数×各要素の長さで、このエントリをＵｉ個備えた記憶容量で構成される。
【００９１】
この写像テーブルは、大きい巡回群の要素γが入力されると、その要素γに対応する番地にエントリされる小さな巡回群の要素の組を出力する。
【００９２】
以上詳細に説明した本実施の形態によれば、特に第２圧縮部２４を備えたから、有限体の部分群上の離散対数問題に依った暗号／署名におけるデータ圧縮において、有限体の拡大次数ｎが一般の正整数であれば、制限なく利用できるようになった。
【００９３】
なお、本実施の形態では、第１圧縮部２３と第２圧縮部２４との併用で構成したが、第１圧縮部２３を無くし、全ての圧縮を第２圧縮部２４で行っても良い。この場合の構成は、図１１のような機能ブロックとなる。
【００９４】
また、（式１）の写像を関数で実現する方法で第２圧縮部２４に実装すれば、余計なメモリなどが不要になり、小型化が実現できる。
【００９５】
また、（式１）の写像をテーブルで実現する方法で第２圧縮部２４に実装すれば、大型化は避けられないが、非常に高速にデータを圧縮できる。
【００９６】
また、（式１）の写像を代数的トーラス間の写像を実現するテーブルと圧縮関数ρと伸長関数ψとを組み合わせる方法で第２圧縮部２４に実装すれば、代数的トーラス間を高速に写像できるようになり、圧縮を高速化できる。
【００９７】
次に、上記で説明した本実施の形態のデータ圧縮部１２に与えられる標数ｑ、拡大次数ｎは、最適な値であれば効率的な圧縮が実現される。そこで、セキュリティ強度Ｓ（＝ｎｌｏｇｑ）とｑのビット数Ｂ（＝ｌｏｇｑ）を入力とし、最適な標数ｑ、拡大次数ｎ出力するパラメータ設定部の実現方法について、説明する。
【００９８】
図１２は、パラメータ設定部３１の機能ブロックを示したものである。パラメータ設定部３１は、入力部３２と、ｎ決定部３３と、ｑ決定部３４と、パラメータ出力部３５とを備える。
【００９９】
入力部３２は、外部からユーザの指示などによって与えられたセキュリティ強度Ｓ（＝ｎｌｏｇｑ）とｑのビット数Ｂ（＝ｌｏｇｑ）との入力を受けるものである。
【０１００】
ｎ決定部３３は、入力部から、セキュリティ強度Ｓ（＝ｎｌｏｇｑ）とｑのビット数Ｂとを受けて、後述する所定の方法によって、最適なｎを求めるものである。
【０１０１】
ｑ決定部３４は、ｎ決定部３３で求められたｎ及び、実現される圧縮方式に基づいて、後述する方法によって、最適なｑを求めるものである。
【０１０２】
パラメータ出力部３５は、求められた最適なｎ及びｑをデータ圧縮部１２へ供給するものである。
【０１０３】
次にｎ決定部３３について詳細に説明する。ｎ決定部３３では、セキュリティ強度Ｓ（＝ｎｌｏｇｑ）とｑのビット長から、与えられたセキュリティ強度を満たし圧縮後のビット数が最も小さくなるｎを選ぶ。圧縮前にｎｌｏｇｑビットであったデータは、圧縮率ｎ／φ（ｎ）で圧縮すると圧縮後のビット数φ（ｎ）ｌｏｇｑビットとなる。ｑのビット長ｌｏｇｑを与えると、圧縮後のビット数を決めているのはオイラー関数φ（ｎ）である。次に示すオイラー関数の下限の性質を用いると、ｎを探索する範囲を適切に設定して、不必要な探索を行わず効率的に探索できる。
【０１０４】
オイラー関数の下限の性質とは、ｎｋを小さい方から数えてｋ番目までの素数を全て掛け合わせた数とすると、ｎｋからｎｋ＋１に到達するまでの間オイラー関数の下限は単調に増加し、ｎｋ＋１で急激に減少するというものである。
【０１０５】
ｎ決定部３３は、図１３にｎの決定法全体の処理の流れを示すが、大別すると以下のステップで動作する。
【０１０６】
１）セキュリティ強度と有限体の標数ｑのビット長Ｂからｎの最小値を決定するステップ
２）ｎの最小値が属する数のグループを判定するステップ
３）閾値を作成するステップ
４）オイラー関数の下限の性質を用いて、オイラー関数が最小となるｎを探索するステップ。
【０１０７】
上記１）のステップでは、ｎの最小値としてＳ／Ｂを計算する。結果をｎｍｉｎ＝Ｓ／Ｂとして記憶する。
【０１０８】
上記２）のステップでは、ｎｍｉｎが属するグループのｋを求める。圧縮後のビット数を決定するオイラー関数の下限はｎの関数である。ｎｋからｎｋ＋１に到達するまでの間オイラー関数の下限は単調に増加し、この範囲にある数を第ｋグループの数と呼ぶ。
【０１０９】
上記３）のステップでは、第ｋグループにおけるｎｋ＋１での下限と等しい下限を持つｎｘを求める（図１４参照）。
【０１１０】
上記４）のステップでは、オイラー関数の下限の性質を用いて、オイラー関数が最小となるｎを探索する
この探索においては、ｎｍｉｎがｎｘ以下である場合（図１５参照）、まず初期値の設定を行う。ｍｉｎにはオイラー関数の最小値を格納する。初期値はｍｉｎ＝φ（ｎｍｉｎ）とする。ｎの探索はｎｍｉｎから始める。探索している位置をｎｔｅｍｐで表し、その初期値をｎｔｅｍｐ＝ｎｍｉｎとする。オイラー関数の最小値を更新したときのｎｔｅｍｐの値をｎとして記憶する。初期値はｎ＝ｎｍｉｎとする。
【０１１１】
ｎｔｅｍｐでのオイラー関数の下限がｍｉｎより小さい期間、探索を繰り返す。
【０１１２】
探索は、圧縮後のビット数が最も小さくなるｎを探す。ｎｔｅｍｐとしてｎｍｉｎから値を１つずつ増やしｎｔｅｍｐにおけるオイラー関数の値がｍｉｎよりも小さいとき、その値をｍｉｎへ上書きし、そのときのｎｔｅｍｐをｎとして記憶する。
【０１１３】
一方、ｎｍｉｎがｎｘよりも大きい場合（図１６参照）、その値ｎｍｉｎからｎｋ＋１に到達するまでのオイラ−関数は必ずｎｋ＋１でのオイラー関数よりも大きくなる。よってｎ＝ｎk＋１とする。
【０１１４】
これにより、最良のｎが求まる。
【０１１５】
次に、ｑ決定部３４におけるｑの決定法は、ｎと圧縮方法をどのように実現するかに依る。まずｑはＢビットでなければならない。
【０１１６】
本実施の形態の圧縮法において写像を実現するテーブル（または関数）は、代数的トーラス間のテーブル（または関数）とＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇの圧縮関数ρと伸長関数ψで構成される。まず、ＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇの圧縮関数ρと伸長関数ψを構成するために以下の条件が課せられる。上記で示したＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇの圧縮法でｎ＝６の場合の例では、ｑは９で割った余りが２または５となる素数でなければならない。代数的トーラス間の関数を用いる為には、
【数２６】
【０１１７】
という円分多項式の関係式の左辺が互いに素でなければならない。代数的トーラス間のテーブルを用いる場合、テーブルのサイズはＵｉで決定される。Ｕｉは、ｎとｑとで定まる。
【０１１８】
具体的には、ｉが２からｋ−１までの数であるとしてｐｉ＋２・・・ｐｋを割り切る全てのｄと、ｐｉ＋２・・・ｐｋを割り切る全てのｄ≠ｅに対して、
【数２７】
【０１１９】
なる最小のＵｉをＵｉとする。ここで、ｎの素因数分解をｎ=ｐ１ｅ１ｐ２ｅ２・・・ｐｋｅｋとした。よって、テーブルのエントリ数Ｕ＝ΣｉＵｉを最小とするｑを選択する。
【０１２０】
以上のようにして、パラメータｎ，ｑを決定することにより、最適なパラメータｎ，ｑを決定できる。
【図面の簡単な説明】
【０１２１】
【図１】本実施の形態のデータ圧縮部を含むコンピュータ装置の機能ブロックの一例を示す図。
【図２】データ圧縮部１２内の機能ブロックを示す図。
【図３】ｎ判定部２１の例を示す図。
【図４】ＲｕｂｉｎとＳｉｌｖｅｒｂｅｒｇの圧縮方式を示す図。
【図５】ｖａｎ ＤｉｊｋとＷｏｏｄｒｕｆｆらの圧縮方式を示す図。
【図６】本実施の形態の圧縮方式を示す図。
【図７】円分多項式に対応した、代数的トーラスの関係式を用いた場合の図。
【図８】これまでの説明を纏めた図。
【図９】これまでの計算の流れを示した図。
【図１０】写像テーブルの構成を説明した図
【図１１】全ての圧縮を第２圧縮部２４で行う構成の、データ圧縮部の機能ブロックを示す図。
【図１２】パラメータ設定部３１の機能ブロックを示す図。
【図１３】ｎの決定法全体の処理の流れを示す図。
【図１４】オイラー関数を示したグラフ。
【図１５】オイラー関数を示したグラフ。
【図１６】オイラー関数を示したグラフ。
【符号の説明】
【０１２２】
１・・・コンピュータ装置１
１１・・・暗号／署名部
１２・・・データ圧縮部
１３・・・記憶部
１４・・・通信部
２１・・・ｎ判定部
２２・・・切替部
２３・・・第１圧縮部
２４・・・第２圧縮部
３１・・・パラメータ設定部
３２・・・入力部
３３・・・ｎ決定部
３４・・・ｑ決定部
３５・・・パラメータ出力部
２１１・・・素因数分解部
２１２・・・方式判定部
２１３・・・素因数テーブル
【特許請求の範囲】
【請求項１】
離散対数問題に依った暗号化方式または署名方式に係るデータを圧縮するデータ圧縮装置であって、
有限体の拡大次数の入力を受け、この拡大次数を素数の組で示すために素因数分解し、素因数分解結果を出力する素因数分解手段と、
前記素因数分解手段で出力された前記素因数分解結果を入力するとともに、外部から有限体の標数と圧縮するデータとを入力し、有限体の標数と拡大次数とで規定され、前記圧縮するデータが含まれる代数的トーラスに、前記素因数分解結果の素数のべき指数に依存する次元を持つ入力アフィン空間を加えて、前記素因数分解結果の素数のべき指数に依存する次元を持つ出力アフィン空間へ写像する関数、テーブル、または関数とテーブルとの組へ、前記圧縮したいデータ、及び前記入力アフィン空間に属する補助入力データを供給して取得される結果データを圧縮データとして外部へ出力する圧縮手段とを備えたことを特徴とするデータ圧縮装置。
【請求項２】
離散対数問題に依った暗号化方式または署名方式に係るデータを圧縮するデータ圧縮装置であって、
有限体の拡大次数の入力を受け、この拡大次数ｎを示す素数の組で出力するとともに、各素数のべきの積が２個以下の素数のべきの積で表されるか否かを判定し、判定結果を出力する判定手段と、
前記拡大次数を示す素数の組を入力するとともに、外部から有限体の標数と圧縮するデータとを入力し、有限体の標数と拡大次数とで規定され、前記圧縮するデータが含まれる代数的トーラスに、前記拡大次数を示す素数の組の素数のべき指数に依存する次元を持つ入力アフィン空間を加えて、前記拡大次数を示す素数の組の素数のべき指数に依存する次元を持つ出力アフィン空間へ写像する関数、テーブル、または関数とテーブルとの組へ、前記圧縮したいデータ、及び前記入力アフィン空間に属する補助入力データを供給して取得される結果データを圧縮データとして外部へ出力する第１圧縮手段と、
前記判定手段の判定結果を入力し、これが否であるときに、前記判定手段から入力された前記拡大次数を示す素数の組と、外部から入力された有限体の標数と圧縮するデータとを前記第１圧縮手段へ出力する切替手段とを備えたことを特徴とするデータ圧縮装置。
【請求項３】
更に、前記拡大次数を示す素数の組を入力するとともに、外部から有限体の標数と圧縮するデータとを入力し、規定の圧縮関数へ、前記圧縮するデータを供給して取得される結果データを圧縮データとして外部へ出力する第２圧縮手段を備え、
前記切替手段は、前記判定手段の判定結果を入力し、これが否でないときに、前記判定手段から入力された前記拡大次数を示す素数の組と、外部から入力された有限体の標数と圧縮するデータとを前記第２圧縮手段へ出力するようにしたことを特徴とする請求項２に記載のデータ圧縮装置。
【請求項４】
前記判定手段は、
有限体の拡大次数の入力を受け、この拡大次数を素因数分解し、素数の組で出力する素因数分解手段と、
前記素因数分解手段から出力された素数の組が、各素数のべきの積が２個以下の素数のべきの積で表されるか否かを判定し、判定結果を出力する方式判定手段とを備えたことを特徴とする請求項２、または請求項３に記載のデータ圧縮装置。
【請求項５】
前記判定手段は、
予め有限体の拡大次数とこの拡大次数を素因数分解した素数の組とを対応付け記憶しておき、有限体の拡大次数の入力を受けると、対応する素数の組を出力する素因数テーブル手段と、
前記素因数テーブル手段から出力された素数の組が、各素数のべきの積が２個以下の素数のべきの積で表されるか否かを判定し、判定結果を出力する方式判定手段とを備えたことを特徴とする請求項２、または請求項３に記載のデータ圧縮装置。
【請求項６】
離散対数問題に依った暗号化方式または署名方式に係るデータを圧縮するデータ圧縮装置へ与える拡大次数を決定するパラメータ設定装置であって、
外部から入力される前記暗号化方式または署名方式のセキュリティ強度を、外部から入力される有限体の標数のビット長で除し、この結果を最小となる拡大次数と決定する最小拡大次数決定手段と、
圧縮後のビット長を決定するオイラー関数を設定し、該オイラー関数の単調増加区間ごとにグループ化し、前記最小拡大次数決定手段で決定された拡大次数が属するグループを判定する判定手段と、
前記判定手段で判定されたグループの一つ上のグループの下限値を求めて、該判定されたグループの閾値と設定する閾値設定手段と、
該判定されたグループの下限値から前記閾値設定手段で設定した閾値までの間を、前記オイラー関数が最小となる拡大次数を探索する探索手段とを備えたことを特徴とするパラメータ設定装置。
【請求項１】
離散対数問題に依った暗号化方式または署名方式に係るデータを圧縮するデータ圧縮装置であって、
有限体の拡大次数の入力を受け、この拡大次数を素数の組で示すために素因数分解し、素因数分解結果を出力する素因数分解手段と、
前記素因数分解手段で出力された前記素因数分解結果を入力するとともに、外部から有限体の標数と圧縮するデータとを入力し、有限体の標数と拡大次数とで規定され、前記圧縮するデータが含まれる代数的トーラスに、前記素因数分解結果の素数のべき指数に依存する次元を持つ入力アフィン空間を加えて、前記素因数分解結果の素数のべき指数に依存する次元を持つ出力アフィン空間へ写像する関数、テーブル、または関数とテーブルとの組へ、前記圧縮したいデータ、及び前記入力アフィン空間に属する補助入力データを供給して取得される結果データを圧縮データとして外部へ出力する圧縮手段とを備えたことを特徴とするデータ圧縮装置。
【請求項２】
離散対数問題に依った暗号化方式または署名方式に係るデータを圧縮するデータ圧縮装置であって、
有限体の拡大次数の入力を受け、この拡大次数ｎを示す素数の組で出力するとともに、各素数のべきの積が２個以下の素数のべきの積で表されるか否かを判定し、判定結果を出力する判定手段と、
前記拡大次数を示す素数の組を入力するとともに、外部から有限体の標数と圧縮するデータとを入力し、有限体の標数と拡大次数とで規定され、前記圧縮するデータが含まれる代数的トーラスに、前記拡大次数を示す素数の組の素数のべき指数に依存する次元を持つ入力アフィン空間を加えて、前記拡大次数を示す素数の組の素数のべき指数に依存する次元を持つ出力アフィン空間へ写像する関数、テーブル、または関数とテーブルとの組へ、前記圧縮したいデータ、及び前記入力アフィン空間に属する補助入力データを供給して取得される結果データを圧縮データとして外部へ出力する第１圧縮手段と、
前記判定手段の判定結果を入力し、これが否であるときに、前記判定手段から入力された前記拡大次数を示す素数の組と、外部から入力された有限体の標数と圧縮するデータとを前記第１圧縮手段へ出力する切替手段とを備えたことを特徴とするデータ圧縮装置。
【請求項３】
更に、前記拡大次数を示す素数の組を入力するとともに、外部から有限体の標数と圧縮するデータとを入力し、規定の圧縮関数へ、前記圧縮するデータを供給して取得される結果データを圧縮データとして外部へ出力する第２圧縮手段を備え、
前記切替手段は、前記判定手段の判定結果を入力し、これが否でないときに、前記判定手段から入力された前記拡大次数を示す素数の組と、外部から入力された有限体の標数と圧縮するデータとを前記第２圧縮手段へ出力するようにしたことを特徴とする請求項２に記載のデータ圧縮装置。
【請求項４】
前記判定手段は、
有限体の拡大次数の入力を受け、この拡大次数を素因数分解し、素数の組で出力する素因数分解手段と、
前記素因数分解手段から出力された素数の組が、各素数のべきの積が２個以下の素数のべきの積で表されるか否かを判定し、判定結果を出力する方式判定手段とを備えたことを特徴とする請求項２、または請求項３に記載のデータ圧縮装置。
【請求項５】
前記判定手段は、
予め有限体の拡大次数とこの拡大次数を素因数分解した素数の組とを対応付け記憶しておき、有限体の拡大次数の入力を受けると、対応する素数の組を出力する素因数テーブル手段と、
前記素因数テーブル手段から出力された素数の組が、各素数のべきの積が２個以下の素数のべきの積で表されるか否かを判定し、判定結果を出力する方式判定手段とを備えたことを特徴とする請求項２、または請求項３に記載のデータ圧縮装置。
【請求項６】
離散対数問題に依った暗号化方式または署名方式に係るデータを圧縮するデータ圧縮装置へ与える拡大次数を決定するパラメータ設定装置であって、
外部から入力される前記暗号化方式または署名方式のセキュリティ強度を、外部から入力される有限体の標数のビット長で除し、この結果を最小となる拡大次数と決定する最小拡大次数決定手段と、
圧縮後のビット長を決定するオイラー関数を設定し、該オイラー関数の単調増加区間ごとにグループ化し、前記最小拡大次数決定手段で決定された拡大次数が属するグループを判定する判定手段と、
前記判定手段で判定されたグループの一つ上のグループの下限値を求めて、該判定されたグループの閾値と設定する閾値設定手段と、
該判定されたグループの下限値から前記閾値設定手段で設定した閾値までの間を、前記オイラー関数が最小となる拡大次数を探索する探索手段とを備えたことを特徴とするパラメータ設定装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２００７−１８７９７８（Ｐ２００７−１８７９７８Ａ）
【公開日】平成１９年７月２６日（２００７．７．２６）
【国際特許分類】
【出願番号】特願２００６−７２７７（Ｐ２００６−７２７７）
【出願日】平成１８年１月１６日（２００６．１．１６）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成１９年７月２６日（２００７．７．２６）
【国際特許分類】
【出願日】平成１８年１月１６日（２００６．１．１６）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]