(57)【特許請求の範囲】
【請求項１】
可換群Ｇの元ｙ、ｇ1、・・・・、ｇmが位数ｎの有限部分群要素を形成し、または、Ｇ自身が位数ｎの有限可換群である時、部分群要素ｙ、ｇ1、・・・・、ｇmおよび整数ｋ1、・・・・、ｋmの入力に対し、群演算に関して
ｙ＝Πmi=1ｇiki
の真理値を出力する多基底離散対数検証方法において、
最短ベクトル近似装置が、
ｎと互いに素な整数Ｌoに関して
Ｌ1＝Ｌ0ｋ1ｍｏｄｎ
Ｌ2＝Ｌ0ｋ2ｍｏｄｎ
・
・
・
Ｌm＝Ｌ0ｋmｍｏｄｎ
なるＬ0、Ｌ1、・・・・、Ｌmの内のノルムの小さいものを求める最短ベクトル近似過程と、
逆元器が、上記元ｙの逆元ｇ0を求める逆元生成過程と、
多基底べき乗積演算装置が、上記求められたＬ0、Ｌ1、・・・・、Ｌmの内のノルムの小さいものと、上記ｇ1、・・・・、ｇmと、上記逆元ｇ0と、を用いて、Πmi=0ｇiLiを求める多基底べき乗積演算過程と、
単位元判定器が、ｅをＧの単位元とし、ｅ＝Πmi=0ｇiLiの真理値を出力する単位元判定過程とを、有することを特徴とする多基底離散対数検証方法。
【請求項２】
請求項１に記載される多基底離散対数検証方法において、
上記最短ベクトル近似過程は、整数Ｌ0、Ｌ1、・・・・、Ｌmを最短ベクトル問題の解または近似解を求める方法によって求める過程であることを特徴とする多基底離散対数検証方法。
【請求項３】
請求項１に記載される多基底離散対数検証方法において、
上記最短ベクトル近似過程は、整数Ｌ0、Ｌ1、・・・・、ＬmをＬＬＬ法によって求める過程であることを特徴とする多基底離散対数検証方法。
【請求項４】
請求項１に記載される多基底離散対数検証方法において、
上記最短ベクトル近似過程は、整数Ｌ0、Ｌ1、・・・・、Ｌmを拡張ユークリッド互除法に基づく方法によって求める過程であることを特徴とする多基底離散対数検証方法。
【請求項５】
可換群Ｇの元ｙ、ｇ1、・・・・・、ｇmが位数ｎの有限部分群要素を形成し、または、Ｇ自身が位数ｎの有限可換群である時、部分群要素ｙ、ｇ1、・・・・、ｇmおよび整数ｋ1、・・・・、ｋmの入力に対し、群演算に関して
ｙ＝Πmi=1ｇiki
の真理値を出力するコンピュータを主要な構成部材として構成される多基底離散対数検証装置において、
部分群要素ｙ、ｇ1、・・・・、ｇmおよび整数ｋ1、・・・・、ｋmが入力され、整数ｋ0、・・・・・、ｋmおよび群の位数ｎよりベクトル（１、ｋ1、ｋ2・・・・、ｋm）、（０、ｎ、０、・・・・、０）、・・・・・・、（０、０、・・・・、０、ｎ）を生成する制御装置を具備し、
制御装置を介して出力される部分群要素ｙを入力してこれにより駆動され、ｙの逆元ｇ0を生成出力する逆元器を具備し、
制御装置により生成されるベクトルを入力してこれにより駆動され、最短ベクトル或いはその近似解（Ｌ0、Ｌ1、・・・・、Ｌm）を生成出力する最短ベクトル近似装置を具備し、
制御装置を介して出力される部分群要素ｇ1、・・・・、ｇmおよび逆元器から出力される逆元ｇ0を入力してこれらにより駆動され、Πmi=0ｇiLiを演算出力する多基底べき乗積演算装置を具備し、
多基底べき乗積演算装置から出力されるΠmi=0ｇiLiを入力してこの真偽を判定出力する単位元判定器を具備することを特徴とする多基底離散対数検証装置。
【請求項６】
請求項５に記載される多基底離散対数検証装置において、
最短ベクトル近似装置はＬＬＬ法或は拡張ユークリッド互除法に基づく方法を実行する装置より成るものであることを特徴とする多基底離散対数検証装置。
【請求項７】
可換群Ｇの元ｙ、ｇ1、・・・・・、ｇmが位数ｎの有限部分群要素を形成し、または、Ｇ自身が位数ｎの有限可換群であるとき、部分群要素ｙ、ｇ1、・・・・、ｇmおよび整数ｋ1、・・・・、ｋmの入力に対し、群演算に関して
ｙ＝Πmi=1ｇiki
の真理値を出力するコンピュータを主要な構成部材として構成される多基底離散対数検証装置のコンピュータに対して、
制御装置が入力された整数ｋ0、・・・・・・、ｋmおよび群の位数ｎよりベクトル（１、ｋ1、ｋ2・・・・、ｋm）、（０、ｎ、０、・・・・、０）、・・・・・・、（０、０、・・・・、０、ｎ）を生成すべき指令をし、
逆元器が制御装置を介し出力される部分群要素ｙを入力してｙの逆元ｇ0を生成すべき指令をし、
最短ベクトル近似装置が制御装置により生成されるベクトルを入力して最短ベクトル或いはその近似解（Ｌ0、Ｌ1、・・・・、Ｌm）を生成すべき指令をし、
多基底べき乗積演算装置が制御装置を介して出力される部分群要素ｇ1、・・・・、ｇmおよび逆元器から出力される逆元ｇ0を入力してΠmi=0ｇiLiを演算すべき指令をし、
単位元判定器が多基底べき乗積演算装置から出力されるΠmi=0ｇiLiを入力してこの真、偽を判定すべき指令をすることを特徴とする多基底離散対数検証プログラム。
【請求項８】
可換群Ｇの元ｙ、ｇ1、・・・・・、ｇmが位数ｎの有限部分群要素を形成し、または、Ｇ自身が位数ｎの有限可換群である時、部分群要素ｙ、ｇ1、・・・・、ｇmおよび整数ｋ1、・・・・、ｋmの入力に対し、群演算に関して
ｙ＝Πmi=1ｇiki
の真理値を出力するコンピュータを主要な構成部材として構成される多基底離散対数検証装置のコンピュータに対して、
制御装置が入力された整数ｋ0、・・・・・・、ｋmおよび群の位数ｎよりベクトル（１、ｋ1、ｋ2・・・・、ｋm）、（０、ｎ、０、・・・・、０）、・・・・・・、（０、０、・・・・、０、ｎ）を生成すべき指令をし、
逆元器が制御装置を介し出力される部分群要素ｙを入力してｙの逆元ｇ0を生成すべき指令をし、
最短ベクトル近似装置が制御装置により生成されるベクトルを入力して最短ベクトル或いはその近似解（Ｌ0、Ｌ1、・・・・、Ｌm）を生成すべき指令をし、
多基底べき乗積演算装置が制御装置を介して出力される部分群要素ｇ1、・・・・、ｇmおよび逆元器２から出力される逆元ｇ0を入力してΠmi=0ｇiLiを演算すべき指令をし、
単位元判定器が多基底べき乗積演算装置から出力されるΠmi=0ｇiLiを入力してこの真、偽を判定すべき指令をする多基底離散対数検証プログラムを記憶したことを特徴とするプログラム記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、多基底離散対数検証方法、この方法を実施する装置、プログラムおよびプログラムを記憶した記憶媒体に関し、特に、情報セキュリティ技術において使用される群上のべき乗を容易に実行することができる多基底離散対数検証方法、この方法を実施する装置、プログラムおよびプログラムを記憶した記憶媒体に関する。
【０００２】
【従来の技術】
近年、インターネットの如き情報伝送技術が発達し、公衆電話回線を介して情報を伝送がなされている。公衆電話回線は誰でも利用することができるものであるところから、中継される情報が盗聴、改ざんされる恐れに曝されている。盗聴の如き悪意のある行為に対抗するは情報伝送に際してセキュリティ技術を適用することが有効である。
情報セキュリティ技術の内の公開鍵暗号を用いた暗号、署名、認証、ゼロ知識証明プロトコルその他、様々な場面において多基底の群のべき乗演算による検証がよく用いられる。例えば、ElGamal署名方式、Schnorr認証方式においては
ｙ＝ｇ1k1ｇ2k2
が成立するか否かにより署名、相手認証に関する検証を行う。従来、この目的の為にはｇ1k1ｇ2k2を計算してから、それがｙと等しいか否かを検査することが行われてきた。
【０００３】
【発明が解決しようとする課題】
以上の
ｇ1k1ｇ2k2
なる値、或は、より一般にｇ1k1ｇ2k2・・・・ｇmkm
なる値は、HANDB00K of APPLIED CRYPTOGRAPHY（ISBN O-8493-8523-7）のp.618 14.88 Algorithm Simultaneous multiple exponentiationに記述されている方法によって計算される。この時、必要な演算コストは、｜ｘ｜をｘの絶対値として└ｌｏｇ2 ｍａｘ（｜ｋ1｜、・・・・、｜ｋm｜）┘回の群演算の平均コストに比例する（なお、└ｘ┘は、ｘ以下の最大整数を意味する）。従って、└ｌｏｇ2 ｍａｘ（｜ｋ1｜、・・・・、｜ｋm｜）┘が大きい場合、この演算コストが無視することができず、署名および相手認証に或いはより一般の情報セキュリティアプリケーションに関する検証装置の演算コスト削減を阻んでいた。
【０００４】
この発明は、上述の問題を解消した多基底離散対数検証方法、この方法を実施する装置、プログラムおよびプログラムを記憶した記憶媒体を提供するものである。
【０００５】
【課題を解決するための手段】
請求項１：可換群Ｇの元ｙ、ｇ1、・・・、ｇm が位数ｎの有限部分群要素を形成し、またはＧ自身が位数ｎの有限可換群であるとき、部分群要素ｙ、ｇ1、・・・、ｇm および整数ｋ1 、・・・・・、ｋm の入力に対して、群演算に関してｙ＝Πmi=1 ｇiki の真理値を出力する多基底離散対数検証方法において、ｎと互いに素な整数Ｌo に関して
Ｌ1＝Ｌ0ｋ1 ｍｏｄ ｎ
Ｌ2＝Ｌ0ｋ2 ｍｏｄ ｎ
・
・
・
Ｌm＝Ｌ0ｋm ｍｏｄ ｎ
なるＬ0 、Ｌ1 、・・・・、Ｌm の内のノルムの小さいものを使用し、ｅをＧの単位元とし、ｇ0をｙの逆元としてｅ＝Πmi=0ｇiLiの真理値を出力する多基底離散対数検証方法を構成した。
【０００６】
そして、請求項２：請求項１に記載される多基底離散対数検証方法において、整数Ｌ0 、Ｌ1 、・・・・、Ｌm を最短ベクトル問題の解または近似解を求める方法によって求める多基底離散対数検証方法を構成した。
また、請求項３：請求項１に記載される多基底離散対数検証方法において、整数Ｌ0 、Ｌ1 、・・・・、Ｌm をＬＬＬ法によって求める多基底離散対数検証方法を構成した。
更に、請求項４：請求項１に記載される多基底離散対数検証方法において、整数Ｌ0 、Ｌ1 、・・・・、Ｌm を拡張ユークリッド互除法に基づく方法によって求める多基底離散対数検証方法を構成した。
【０００７】
ここで、請求項５：可換群Ｇの元ｙ、ｇ1、・・・・・、ｇm が位数ｎの有限部分群要素を形成し、または、Ｇ自身が位数ｎの有限可換群である時、部分群要素ｙ、ｇ1、・・・・、ｇm および整数ｋ1 、・・・・、ｋm の入力に対し、群演算に関して
ｙ＝Πmi=1 ｇiki
の真理値を出力するコンピュータを主要な構成部材として構成される多基底離散対数検証検証装置において、部分群要素ｙ、ｇ1、・・・・、ｇm および整数ｋ1 、・・・・、ｋm が入力され、整数ｋ0、・・・・・・、ｋm および群の位数ｎよりベクトル（１、ｋ1、ｋ2・・・・、ｋm）、（０、ｎ、０、・・・・、０）、・・・・・・、（０、０、・・・・・、０、ｎ）を生成する制御装置１を具備し、制御装置１を介して出力される部分群要素ｙを入力してこれにより駆動され、ｙの逆元ｇ0 を生成出力する逆元器２を具備し、制御装置１により生成されるベクトルを入力してこれにより駆動され、最短ベクトル或いはその近似解（Ｌ0、Ｌ1、・・・・、ｋm ）を生成出力する最短ベクトル近似装置３を具備し、制御装置１を介して出力される部分群要素ｇ1、・・・・・、ｇm および逆元器２から出力される逆元ｇ0 を入力してこれらにより駆動され、Πmi=0 ｇiLiを演算出力する多基底べき乗積演算装置４を具備し、多基底べき乗積演算装置４から出力されるΠmi=0ｇiLi を入力してこの真、偽を判定出力する単位元判定器５を具備する多基底離散対数検証装置を構成した。
【０００８】
そして、請求項６：請求項５に記載される多基底離散対数検証装置において、最短ベクトル近似装置３はＬＬＬ法或は拡張ユークリッド互除法に基づく方法を実行する装置より成るものである多基底離散対数検証装置を構成した。
また、請求項７：可換群Ｇの元ｙ、ｇ1、・・・・・、ｇm が位数ｎの有限部分群要素を形成し、または、Ｇ自身が位数ｎの有限可換群であるとき、部分群要素ｙ、ｇ1、・・・・、ｇm および整数ｋ1 、・・・・、ｋm の入力に対し、群演算に関して
ｙ＝Πmi=1 ｇiki
の真理値を出力するコンピュータを主要な構成部材として構成される多基底離散対数検証装置のコンピュータに対して、制御装置１が入力された整数ｋ0、・・・・・・、ｋm および群の位数ｎよりベクトル（１、ｋ1、ｋ2・・・・、ｋm）、（０、ｎ、０、・・・・、０）、・・・・・・、（０、０、・・・・、０、ｎ）を生成すべき指令をし、逆元器２が制御装置１を介し出力される部分群要素ｙを入力してｙの逆元ｇ0 を生成すべき指令をし、最短ベクトル近似装置３が制御装置１により生成されるベクトルを入力して最短ベクトル或いはその近似解（Ｌ0、Ｌ1、・・・・、ｋm ）を生成すべき指令をし、多基底べき乗積演算装置４が制御装置１を介して出力される部分群要素ｇ1、・・・・、ｇm および逆元器２から出力される逆元ｇ0 を入力してΠmi=0ｇiLi を演算すべき指令をし、単位元判定器５が多基底べき乗積演算装置４から出力されるΠmi=0 ｇiLiを入力してこの真、偽を判定すべき指令をする多基底離散対数検証プログラムを構成した。
【０００９】
更に、請求項８：可換群Ｇの元ｙ、ｇ1、・・・・・、ｇm が位数ｎの有限部分群要素を形成し、または、Ｇ自身が位数ｎの有限可換群であるとき、部分群要素ｙ、ｇ1、・・・・、ｇm および整数ｋ1 、・・・・、ｋm の入力に対し、群演算に関して
ｙ＝Πmi=1 ｇiki
の真理値を出力するコンピュータを主要な構成部材として構成される多基底離散対数検証装置のコンピュータに対して、制御装置１が入力された整数ｋ0、・・・・・・、ｋm および群の位数ｎよりベクトル（１、ｋ1、ｋ2・・・・、ｋm）、（０、ｎ、０、・・・・、０）、・・・・・・、（０、０、・・・・、０、ｎ）を生成すべき指令をし、逆元器２が制御装置１を介し出力される部分群要素ｙを入力してｙの逆元ｇ0 を生成すべき指令をし、最短ベクトル近似装置３が制御装置１により生成されるベクトルを入力して最短ベクトル或いはその近似解（Ｌ0、Ｌ1、・・・・、ｋm ）を生成すべき指令をし、多基底べき乗積演算装置４が制御装置１を介して出力される部分群要素ｇ1、・・・・、ｇm および逆元器２から出力される逆元ｇ0 を入力してΠmi=0 ｇiLiを演算すべき指令をし、単位元判定器５が多基底べき乗積演算装置４から出力されるΠmi=0 ｇiLiを入力してこの真、偽を判定すべき指令をする多基底離散対数検証プログラムを記憶したプログラム記憶媒体を構成した。
【００１０】
【発明の実施の形態】
（命題：ｙ＝Πmi=1 ｇikiと等価な論理式）
一般に、位数ｎの群Ｇ上の元ｇに関して、ｅを群Ｇの単位元とすれば、
gn =ｅ
が成立する。従って、２個の整数ｋ、Ｌに関して
Ｌ=ｋ＋ｃｎ≡ｋ ｍｏｄ ｎ、  但し、c：整数
が成立するなら、
ｇL=ｇk+cn＝ｇk
が成立する。ｎと互いに素なＬoに関しては常に
Ｌ0Ｌ0-1≡１ ｍｏｄ ｎ
なる整数Ｌ0-1が存在しており、従ってｙ、ｇ1 、・・・・・・、ｇm が位数ｎの可換群上の元であるならＬoをｎと互いに素として、
Ｌ1＝Ｌ0ｋ1 ｍｏｄ ｎ
Ｌ2＝Ｌ0ｋ2 ｍｏｄ ｎ
・
・
・
Ｌm＝Ｌ0ｋm ｍｏｄ ｎ
なるＬ0 、Ｌ1 、・・・・・・、Ｌm およびｙの逆元ｇ0 に関して、
命題：ｙ＝ｇ1k1 ・・・・・・ｇmkmと、
命題：ｅ＝ｇ0L0ｇ1L1・・・・・・ｇmLm          式（１）
とは同値となる。式（1）の右辺の値を計算するのにも、先のHANDB00K of APPLIED CRYPTOGRAPHY（ISBN O-8493-8523-7）のp61814.88 Algorithm Simultanecous multiple exponentiation に記述されている方法によって行うことができる。従って、この演算の平均コストは└ｌｏｇ2 ｍａｘ（｜Ｌ0｜、・・・・、｜Ｌm｜）┘回の群演算の平均コストに比例する。ここで、└ｌｏｇ2 ｍａｘ（｜Ｌ0｜、・・・・、｜Ｌm｜）┘が└ｌｏｇ2 ｍａｘ（｜ｋ1｜、・・・・、｜ｋm｜）┘より充分に小さい場合、式（１）の変形により演算コストを削減することになる。この要件を満足する整数Ｌ0 、Ｌ1 、・・・・・・、Ｌm を縮小されたべきと呼ぶことにする。また、元の命題：ｙ＝Πmi=1ｇikiは、ｋ0 ＝１とすれば
ｅ＝Πmi=0 ｇiki
と、式（１）の型にいつでも変形することができる。この場合、ｋ0 、ｋ1、・・・・・、ｋmは
0003886384.tif 000002
を満足するので、縮小されたべきではない。ｋ0 、ｋ1、・・・・、ｋmは元のべきと呼ぶ。
【００１１】
『最短ベクトル近似問題について』
縮小されたべきＬ0 、Ｌ1 、・・・・、Ｌm が求まるなら、以上の通りにして、多基底の離散対数の検証において平均演算コストを削減することができる。以下、これについて説明する。
縮小されたべきのベクトル表現（Ｌ0 、Ｌ1 、・・・・、Ｌm ）は元のべきのベクトル表現（ｋ0 、ｋ1、・・・・、ｋm）と
0003886384.tif 000003
なる関係にある筈である。従って、ｃ0 ＝Ｌ0 とすれば、或る整数列ｃ1、ｃ2・・・・、ｃm が存在して、
0003886384.tif 000004
が成立する筈である。即ち、縮小されたべきのベクトル（Ｌ0、Ｌ1、Ｌ2、・・・、Ｌm）は（ｍ＋１）個の線形独立なベクトル（ｋ0、ｋ1、ｋ2・・・、ｋm）、（０、ｎ、０、・・・・、０）、・・・・・・、（０、０、・・・・、０、ｎ）の整数係数線形結合によって記述することができる。この整数係数線形結合によって記述されるベクトルの内のＬ∞ノルム、即ち、ｍａｘ（Ｌ0、Ｌ1、Ｌ2、・・・・、Ｌm）を最小とするベクトル（Ｌ0、Ｌ1、Ｌ2、・・・・、Ｌm）を求めることができれば、このＬ0、Ｌ1、Ｌ2 、・・・・、Ｌmをもって縮小されたべきとすることができる。また、縮小されたべきは必ずしもＬ∞ノルムを最小としなくてもよい。例えば、Ｌ2 ノルム、即ち、√（Σmi=0Ｌi2）を最小とするＬ0 、Ｌ1 、Ｌ2 、・・・・、Ｌm をもって、縮小されたべきとしても良い。この様に、ベクトルの整数係数線形結合の内で、何らかのノルムが最小となるベクトルを探索する問題は最短ベクトル問題といわれ、その解を求める様々方法が提案されている。
ところで、縮小されたべきを求めるには、何らかのノルムが最小であるベクトルを求める必要はない。即ち、例えば、√（Σmi=0Ｌi2）が√（Σmi=0ｋi2）よリ充分に小さいＬ0 、Ｌ1 、Ｌ2 、・・・・、Ｌm をもって縮小されたべきとしても良く、この何らかのノルムが充分小さくなるベクトルを探索する問題は最短ベクトル近似問題といわれ.その解を求める様々な方法も提案されている。
【００１２】
『ＬＬＬ法について』
A Course in Computational Algebraic Number Theory（ISBN 3-540-55640-0）のp.84〜ｐ.108 2.6 Lattice Reduction Algorithms およびApplications of the LLL Algorithm には、ＬＬＬ法を含む最短ベクトル近似問題を解く種々の方法が記述されている。これらの方法は複数のベクトルｖ1、ｖ2、・・・・、ｖn の入力に対して、整数係数線形結合ｋ1ｖ1 、ｋ2ｖ2 、・・・・・・、ｋnｖnで表現することができる値の内のノルムの小さいものを演算出力することができるものである。
【００１３】
『拡張ユークリッド互除法を使用する方法について』
最短ベクトル近似問題を解く方法として、ＬＬＬ法の他に拡張ユークリッド互除法を使用する方法がある。拡張ユークリッド互除法を使用した以下の方法でｓ〜√（ｎ）とする方法がある。
0003886384.tif 000005
縮小べき出力手続１はランダムなｋ1 に対し高い確率で（｜Ｌ0｜、｜Ｌ1｜）〜（ｎ／ｓ、ｓ）なるＬ0、Ｌ1を出力する。
この方法は、例えば、２基底の場合に次の様に拡張することができる。
0003886384.tif 000006
この方法はビット演算量量ｌｏｇ2 ｎの自乗に比例する方法であり、一般にＬＬＬ法より高速であるが、最短ベクトル近似問題の近似度はＬＬＬ法と比較して悪い。一般のｍに関しても縮小べき出力手続１をｍ回呼ぶことによって縮小されたべきを得ることができる。
【００１４】
この発明の実施の形態を図１の実施例を参照して具体的に説明する。
図１は多基底の一般的な群の離散対数検証命題
ｙ＝Πmi=1 ｇiki
の真理値を出力する多基底離散対数検証装置の実施例を説明する図である。図１において、１は制御装置、２は逆元器、３は最短ベクトル近似装置、４は多基底べき乗積演算装置、５は単位元判定器であり、これらはコンピュータを主要な構成部材として構成される。
制御装置１は入力される整数ｋ0、・・・・・、ｋm および群の位数ｎより、ベクトル（１、ｋ1、ｋ2・・・・、ｋm）、（０、ｎ、０、・・・・、０）、・・・・・・、（０、０、・・・・、０、ｎ）を生成し、最短ベクトル近似装置３に入力してこの最短ベクトル近似装置３を駆動する。更に、逆元器２に入力群要素ｙを入力してこの逆元器２を駆動する。
【００１５】
最短ベクトル近似装置３は最短ベクトル或いはその近似解（Ｌ0、Ｌ1、・・・・、ｋm ）を出力してこれを多基底べき乗積演算装置４に入力する。更に、逆元器２はｙの逆元ｇ0 を出力してこれを多基底べき乗積演算装置４に入力すると共に、制御装置１は入力群要素ｇ1、ｇ2、・・・・・、ｇmを多基底べき乗積演算装置４に入力し、これら入力により多基底べき乗積演算装置４を駆動する。
多基底べき乗積演算装置４はΠmi=0 ｇiLiを出力してこれを単位元判定器５に入力し、これを駆動する。
単位元判定器５は入力であるΠmi=0 ｇiLiが単位元であれば真を出力し、単位元でなければ偽を出力する。
図２は多基底離散対数検証装置の動作フローチャートである。
【００１６】
【発明の効果】
以上の通りであって、この発明によれば、多基底の一般化された離散対数の検証命題：ｙ＝Πmi=1 ｇikiの真理値を出力する演算において、必要な群演算の演算コストをＬＬＬ法を使用した場合はｍ／（ｍ＋１）に削減することができ、拡張ユークリッド互除法を使用した場合は（２m −１）／２m に削減することができる。これを数値的に具体的に示すと、汎用されているElGama1署名、或はSchnorr認証方式のｍ＝２の場合、演算コストがＬＬＬ法なら２／３に削減することができ、拡張ユークリッド互除法なら３／４に削減することができる。
【図面の簡単な説明】
【図１】実施例を説明する図。
【図２】実施例の動作フローチャート。
【符号の説明】
１  制御装置                      ２  逆元器
３  最短ベクトル近似装置          ４  多基底べき乗積演算装置
５  単位元判定器
【図１】
0003886384.tif 000007
【図２】
0003886384.tif 000008