耐量子コンピュータ性をもつディジタル署名方式
【課題】従来の方式は、耐量子コンピュータ性がなく、量子コンピュータが出現すると多項式時間で解読されてしまうと予想されている。この発明の目的は、安全性をＮＰ完全問題の１つである高次多変数連立代数方程式の解法に依存する方式を採用することにより、耐量子コンピュータ性を持つディジタル署名方式を提案することにある。
【解決手段】有限体Ｆｑ上のｍ個の任意の要素ｋｉ（ｉ＝１，．．，ｍ）と、Ｆｑ上の四元数環Ｈ上の互いに非可換となるｍ個の要素Ａｉ（ｉ＝１，．．，ｍ）を係数とする四元数環上の暗号化関数Ｆ（Ｘ）を利用者Ａ（署名者）の公開鍵として、利用者Ａ（署名者）が署名作成時毎に作成する補助暗号化関数Ｔ（Ｘ）と暗号化関数Ｆ（Ｘ）とメッセージＥを用いて、ディジタル署名Ｓを生成し、利用者Ｂ（検証者）にＳとＥを送信し、利用者Ｂ（検証者）は受信したＳとＥと公開鍵Ｆ（Ｘ）と公開情報ｑ，ｄ，ｒ，ｍを用いてＳが利用者Ａの署名であることを検証する。
【解決手段】有限体Ｆｑ上のｍ個の任意の要素ｋｉ（ｉ＝１，．．，ｍ）と、Ｆｑ上の四元数環Ｈ上の互いに非可換となるｍ個の要素Ａｉ（ｉ＝１，．．，ｍ）を係数とする四元数環上の暗号化関数Ｆ（Ｘ）を利用者Ａ（署名者）の公開鍵として、利用者Ａ（署名者）が署名作成時毎に作成する補助暗号化関数Ｔ（Ｘ）と暗号化関数Ｆ（Ｘ）とメッセージＥを用いて、ディジタル署名Ｓを生成し、利用者Ｂ（検証者）にＳとＥを送信し、利用者Ｂ（検証者）は受信したＳとＥと公開鍵Ｆ（Ｘ）と公開情報ｑ，ｄ，ｒ，ｍを用いてＳが利用者Ａの署名であることを検証する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は電子文書の正当性を確認するディジタル署名方式に関し、特に安全性が高く、耐量子コンピュータ性をもつディジタル署名方式に関するものである。
【背景技術】
【０００２】
「ディジタル署名」とは，送られてきたデータの送信元が間違いないか，伝送経路上でデータが改ざんされていないかを確認するための技術である。従来提案されているディジタル署名方式の代表例として岡本方式やＦｉａｔ−Ｓｈａｍｉｒ方式（Ｆｉａｔ，Ａ．ａｎｄ Ｓｈａｍｉｒ，Ａ：“Ｈｏｗ ｔｏ ｐｒｏｖｅ ｙｏｕｒｓｅｌｆ：ｐｒａｃｔｉｃａｌ ｓｏｌｕｔｉｏｎｓ ｔｏ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ａｎｄ ｓｉｇｎａｔｕｒｅ ｐｒｏｂｌｅｍｓ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｃｒｙｐｔｏ８６，Ｓａｎｔａ Ｂａｒｂａｒａ，Ａｕｇｕｓｔ１９８６，ｐｐ．１８−１−１８−７）がある。
【０００３】
岡本方式の署名方式は、以下の通りである。署名者Ａは素数ｐ，ｑ（ｑはｐ−１の因数の１つ）と乱数ｒ（２以上ｐ−１以下）とからｒｑｍｏｄ ｐを計算し、１となるｑを２つ見つけてｇ１，ｇ２とし、これらと乱数ｓ１，ｓ２とからｖ＝ｇ１−ｓ１・ｇ２−ｓ２ｍｏｄ ｐを計算し、ｐ，ｑ，ｇ１，ｇ２，ｔ，ｖ（ｔは安全性の度合いを示すパラメータ）を公開し、ｓ１，ｓ２を自分の秘密鍵とする。Ａは文書Ｍに対する署名を行うには、乱数ｒ１，ｒ２を発生し、ｘ＝ｇ１ｒ１・ｇ２ｒ２ｍｏｄ ｐを計算し、ハッシュ関数演算器でｅ＝ｈ（ｘ，Ｍ）を計算し、秘密鍵ｓ１，ｓ２を用い、ｙ１＝ｒ１＋ｅ・ｓ１ｍｏｄｑ、ｙ２＝ｒ２＋ｅ・ｓ２ｍｏｄ ｑを計算し、署名（ｅ，ｙ１，ｙ２）とＭを検証者Ｂへ送る。Ｂはｗ＝ｇ１ｙ１・ｇ２ｙ２・ｖｅｍｏｄ ｐを計算し、ｗ＝ｘかを判定し、成立すれば合格とする。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許公開平６−５９６２６ ディジタル署名方式 日本電信電話株式会社 岡本 龍明 特許出願平４−２１５８０９
【発明の概要】
【発明が解決しようとする課題】
【０００５】
Ｆｉａｔ−Ｓｈａｍｉｒ方式の安全性は、法の合成数の素因数分解の困難さに依存する。岡本方式の安全性は、法の合成数の素因数分解の困難さに依存すること、及び乗法群上の離散対数問題の計算量上の困難さに依存することであり、量子コンピュータが出現するといずれの問題も多項式時間で解読可能と予想されている。
【０００６】
このように岡本方式やＦｉａｔ−Ｓｈａｍｉｒ方式は、耐量子コンピュータ性がなく、量子コンピュータが出現すると多項式時間で解読されてしまうと予想されている。この発明の目的は、安全性をＮＰ完全問題の１つである高次多変数連立代数方程式の解法に依存する方式を採用することにより、耐量子コンピュータ性を持つディジタル署名方式を提案することにある。
【課題を解決するための手段】
【０００７】
信頼のおける第３者機関であるシステムセンタは３以上の素数ｑおよび３つの整数ｄ，ｒ，ｍを選び公開する。利用者Ａ（署名者）は、システム加入時に、秘密鍵［ｋｉ，Ａｉ（ｉ＝１，．．，ｍ）］を選ぶ。ここで、ｋｉ（ｉ＝１，．．，ｍ）を有限体Ｆｑ上のｍ個の任意の要素として、Ａｉ（ｉ＝１，．．，ｍ）をＦｑ上の四元数環Ｈ上の互いに非可換となるｍ個の要素とする。１つの要素ＡｉはＦｑ上の４つの要素から成り立っている四元数である。利用者Ａは公開されている４つのシステムパラメータ［ｑ，ｄ，ｒ，ｍ］と秘密鍵［ｋｉ，Ａｉ（ｉ＝１，．．，ｍ）］から、公開鍵である四元数環上の暗号化関数Ｆ（Ｘ）を以下のように生成する。
【０００８】
【数１】
【０００９】
利用者ＡはＦ（Ｘ）を展開して、展開式の係数ｆｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｆｊｅ０ｅ１ｅ２ｅ３｝を利用者Ａの公開鍵として、利用者Ａの識別情報ＩＤと対にしてシステムセンタに送る（図２）。ｆｊｅ０ｅ１ｅ２ｅ３は以下のような形をしている。四元数Ｆ（Ｘ）の要素表現形式を（ｆ０，ｆ１，ｆ２，ｆ３）とすると、
【００１０】
【数２】
【００１１】
ここで、１＋ｒ＋…＋ｒｄ＝ｓとして、
ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｆｊを与える式の右辺の項数ｎは、
ｎ＝４Ｈｓ＝３＋ｓＣ３＝（ｓ＋３）（ｓ＋２）（ｓ＋１）／６
となる。
【００１２】
利用者Ａが利用者Ｂに署名Ｓを以下のように送る。
利用者Ａは、すべてのＡｉ（ｉ＝１，．．，ｍ）と非可換な四元数環Ｈの任意の要素Ｒを選ぶ。
利用者Ａは、送信するメッセージＥ＝（Ｅ０，Ｅ１，Ｅ２，Ｅ３）∈Ｈから、ｇ＝Ｅ０＋Ｅ１＋Ｅ２＋Ｅ３を生成する。
利用者Ａは自分の秘密鍵［ｋｉ，Ａｉ（ｉ＝１，．．，ｍ）］と選んだ要素Ｒを用いて、Ｆｑ上の四元数環上の補助暗号化関数Ｔ（Ｘ）を以下のように生成する。
【００１３】
【数３】
【００１４】
利用者ＡはＴ（Ｘ）を展開して、展開式の係数ｔｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｔｊｅ０ｅ１ｅ２ｅ３｝を求める。
ｔｊｅ０ｅ１ｅ２ｅ３は以下のような形をしている。
四元数Ｔ（Ｘ）の要素表現形式を（ｔ０，ｔ１，ｔ２，ｔ３）とすると
【００１５】
【数４】
【００１６】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｔｊを与える式の右辺の項数ｎは、
ｎ＝４Ｈｓ＝３＋ｓＣ３＝（ｓ＋３）（ｓ＋２）（ｓ＋１）／６
となる。
【００１７】
利用者ＡはメッセージＥと署名Ｓ＝［｛ｔｊｅ０ｅ１ｅ２ｅ３｝，Ｒ］を利用者Ｂに送る（図３の上段）。
【００１８】
利用者Ｂはシステムセンタの公開鍵管理簿から入手した利用者Ａの公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝と利用者Ａから送られてきたメッセージＥと署名Ｓから以下の手順で検証する。
まず、メッセージＥ＝（Ｅ０，Ｅ１，Ｅ２，Ｅ３）∈Ｈから、ｇ＝Ｅ０＋Ｅ１＋Ｅ２＋Ｅ３を生成する。
【００１９】
次に、利用者ＢはＦ（ＲｇＥ）≠Ｔ（ＲＥ）であることを確認する。
利用者Ｂは｛ｆｊｅ０ｅ１ｅ２ｅ３｝からＦ（ＲｇＥ）の要素表現形式（ｆ’０，ｆ’１，ｆ’２，ｆ’３）を求める。
ＲｇＥ＝（ｂ０，ｂ１，ｂ２，ｂ３）とおくと、
【００２０】
【数５】
【００２１】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｆ’ｊを与える式の右辺の項数ｎは、
ｎ＝４Ｈｓ＝３＋ｓＣ３＝（ｓ＋３）（ｓ＋２）（ｓ＋１）／６
となる。
【００２２】
同様にして、利用者Ｂは｛ｔｊｅ０ｅ１ｅ２ｅ３｝からＴ（ＲＥ）の要素表現形式（ｔ’０，ｔ’１，ｔ’２，ｔ’３）を求める。
ＲＥ＝（ｃ０，ｃ１，ｃ２，ｃ３）とおくと
【００２３】
【数６】
【００２４】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｔ’ｊを与える式の右辺の項数ｎは、
ｎ＝４Ｈｓ＝３＋ｓＣ３＝（ｓ＋３）（ｓ＋２）（ｓ＋１）／６
となる。
【００２５】
利用者Ｂは
Ｔ（ＲＥ）＝（ｔ’０，ｔ’１，ｔ’２，ｔ’３）≠（ｆ’０，ｆ’１，ｆ’２，ｆ’３）＝Ｆ（ＲｇＥ）
を確認する。等しければ送られてきたＳは利用者Ａの署名でないと判定する（図３下段）。
【００２６】
利用者Ｂは、任意の整数ｐを選び、以下のように
Ｆ（Ｒｇ＋ｐ）＝Ｔ（Ｒｐ＋１）
を確認する。
【００２７】
利用者Ｂは｛ｆｊｅ０ｅ１ｅ２ｅ３｝からＦ（Ｒｇ＋ｐ）の要素表現形式（ｆ’’０，ｆ’’１，ｆ’’２，ｆ’’３）を求める。
Ｒｇ＋ｐ＝（ｂ０，ｂ１，ｂ２，ｂ３）とおいて、
【００２８】
【数７】
【００２９】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｆ”ｊを与える式の右辺の項数ｎは、
ｎ＝４Ｈｓ＝３＋ｓＣ３＝（ｓ＋３）（ｓ＋２）（ｓ＋１）／６
となる。
【００３０】
同様にして、利用者ＢはＴ（Ｒｐ＋１）の要素表現形式（ｔ’’０，ｔ’’１，ｔ’’２，ｔ’’３）を求める。
Ｒｐ＋１＝（ｃ０，ｃ１，ｃ２，ｃ３）とおくと、
【００３１】
【数８】
【００３２】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｔ”ｊを与える式の右辺の項数ｎは、
ｎ＝４Ｈｓ＝３＋ｓＣ３＝（ｓ＋３）（ｓ＋２）（ｓ＋１）／６
となる。
【００３３】
利用者Ｂは
Ｆ（Ｒｐ＋ｇ）＝（ｔ’’０，ｔ’’１，ｔ’’２，ｔ’’３）＝（ｆ’’０，ｆ’’１，ｆ’’２，ｆ’’３）＝Ｔ（Ｒｐ＋１）
を確認する。その結果が一致するかどうかを検証し、その検証に合格すればＳは利用者Ａの正当な署名文書と判定することにより署名文書の正当性を確認する（図４）。
【００３４】
［００１０］で公開される集合｛ｆｊｅ０ｅ１ｅ２ｅ３｝の値から秘密鍵［ｋｉ，Ａｉ（ｉ＝１，．．，ｍ）］を求めることが高次元多変数連立代数方程式の解法に帰結される。この解法問題はＮＰ完全問題の一つである。
【００３５】
ところで、岡本方式の安全性は、法の合成数の素因数分解の困難さや素数を法とする離散対数問題の困難さに依存する。
【００３６】
一方、本発明方式の安全性は、有限体Ｆｑ上の高次多変数連立代数方程式の解法の困難さに依存する。次数を大きくし、変数の数を多くすることにより、耐量子コンピュータ性をもつディジタル署名方式である。
【発明の効果】
【００３７】
岡本方式やＦｉａｔ−Ｓｈａｍｉｒ方式の安全性は、法の合成数の素因数分解の困難さや素数を法とする離散対数問題の困難さに依存するので、量子コンピュータが出現すると、多項式時間で解読可能となる恐れがある。
【００３８】
一方、本発明においては、有限体Ｆｑ上の高次多変数連立代数方程式の解法の困難さに依存するディジタル署名方式が、高次多変数連立代数方程式の解法がＮＰ完全問題の１つとなるので、量子コンピュータに耐えうるディジタル署名方式を提供できる。
【００３９】
従ってこの発明によれば安全性を高く保持するものとなる。
【００４０】
なお、本発明は、上記において説明した実施形態に限定されるものではなく、その主旨を逸脱しない範囲において種々変更可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【図面の簡単な説明】
【００４１】
【図１】本発明の一実施の形態による署名方式のブロック図である。
【図２】同実施の形態による署名方式における利用者Ａの署名処理手順のブロック図である。
【図３】同実施の形態による署名方式における利用者Ｂの検証処理手順１のブロック図である。
【図４】同実施の形態による署名方式における利用者Ｂの検証処理手順２のブロック図である。
【符号の説明】
【００４２】
１００…システムセンタ装置
２００…利用者Ａ（署名者）端末
３００…利用者Ｂ（検証者）端末
４００…安全でない通信路
１１０…システムセンタ公開鍵管理簿
２０１、２０２，２０６、３０３…乱数発生器
２０３…記憶装置
２０４…公開鍵生成装器
２０５…署名生成器
３０１，３０４，３０５…検証器
３０２，３０６…比較器
【発明を実施するための形態】
【００４３】
請求項１の発明の一実施例について説明する。
【実施例】
【００４４】
図１にこの発明の全体構成を示す。ディジタル署名を作成する利用者Ａ（署名者）装置２００と、署名を検証する利用者Ｂ（検証者）装置３００とが安全でない通信路４００を介して結合されているとする。
【００４５】
まず、システムに加入した利用者Ａは、システム加入時に、システムセンタ１００からシステムパラメータｑ，ｄ，ｒ，ｍを入手して、署名者装置２００にて基本的に一度だけ行う初期情報設定段階において、図２に示す乱数発生器２０１，２０２を用いて、秘密鍵［ｋｉ，Ａｉ（ｉ＝１，．．，ｍ）］と、公開鍵生成器２０４を用いて公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝を生成し、秘密鍵［ｋｉ，Ａｉ（ｉ＝１，．．，ｍ）］と公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝を記憶装置２０３に入力し、公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝を利用者Ａの識別情報ＩＤと対にして、システムセンタ１００の公開鍵管理簿１１０に登録する。
【００４６】
次に、利用者Ａが文書Ｅに対するディジタル署名を作成する手順について説明する。署名作成者である利用者Ａは、署名者装置２００で署名作成を行う。図３にその処理手順を示す。
利用者Ａは乱数発生器２０６を用いて四元数である乱数Ｒを生成し、記憶装置２０３に入力し、当該文書Ｅ，当該乱数Ｒを入力として署名生成器２０５を用いて｛ｔｊｅ０ｅ１ｅ２ｅ３｝を計算し、［｛ｔｊｅ０ｅ１ｅ２ｅ３｝，Ｒ］を文書Ｅに対するディジタル署名Ｓとして、ＳとＥを記憶装置２０３に入力し、検証者である利用者ＢにＳとＥを送信する。
【００４７】
次に、検証者である利用者Ｂが検証者装置３００を用いて、署名作成者である利用者Ａの署名者装置２００から送信された文書Ｅと当該文書Ｅに対するディジタル署名［｛ｔｊｅ０ｅ１ｅ２ｅ３｝，Ｒ］を検証する手順について説明する。図３，図４に署名検証手順を示す。
【００４８】
まず、Ｔ（ＲＥ）≠Ｆ（ＲｇＥ）を確認する。検証者である利用者Ｂは検証器３０１を用いて、受信した四元数である文書Ｅから、その４つの要素の和ｇを計算し、システムセンタの公開鍵管理簿から入手した利用者Ａの公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝と受信したＲとＥと計算したｇからＲｇＥを計算して、Ｆ（ＲｇＥ）＝（ｆ’０，ｆ’１，ｆ’２，ｆ’３）を生成して、比較器３０２に入力する。一方、検証器３０１を用いて、受信したＲ，ＥからＲＥを計算し、受信した｛ｔｊｅ０ｅ１ｅ２ｅ３｝とＲＥからＴ（ＲＥ）＝（ｔ’０，ｔ’１，ｔ’２，ｔ’３）を生成して、比較器３０２に入力する。比較器３０２を用いて、（ｆ’０，ｆ’１，ｆ’２，ｆ’３）と（ｔ’０，ｔ’１，ｔ’２，ｔ’３）が等しいか異なるかを検証する。利用者Ｂは等しいときはＳは利用者Ａの署名ではないと出力する。異なるときは検証器３０４を用いて、図４に示すように検証する。
【００４９】
検証者である利用者Ｂは乱数発生器３０３を用いて、整数である乱数ｐを生成し、検証器３０４に入力する。
【００５０】
検証者である利用者Ｂは検証器３０４にてＲｇ＋ｐを計算し、Ｒｇ＋ｐと公開鍵管理簿から入手した利用者Ａの公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝からＦ（Ｒｇ＋ｐ）＝（ｆ’’０，ｆ’’１，ｆ’’２，ｆ’’３）を計算し比較器３０６に入力する。
【００５１】
検証者である利用者Ｂは検証器３０５にてＲｐ＋１を計算し、Ｒｐ＋１と受信した｛ｔｊｅ０ｅ１ｅ２ｅ３｝からＴ（Ｒｐ＋１）＝（ｔ’’０，ｔ’’１，ｔ’’２，ｔ’’３）を計算し比較器３０６に入力する。
【００５２】
検証者である利用者Ｂは比較器３０６を用いて、（ｆ’’０，ｆ’’１，ｆ’’２，ｆ’’３）と（ｔ’’０，ｔ’’１，ｔ’’２，ｔ’’３）が等しいか異なるかを検証する。等しいときはＳは利用者Ａの署名であると出力する。異なるときはＳは利用者Ａの署名ではないと出力する。
【００５３】
なお、本発明は、上記において説明した実施形態に限定されるものではなく、その主旨を逸脱しない範囲において種々変更可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【産業上の利用可能性】
【００５４】
この発明は電子文書の正当性を確認するディジタル署名方式に関し、特に安全性が高く、耐量子コンピュータ性をもつディジタル署名方式を提案するものである。
【技術分野】
【０００１】
この発明は電子文書の正当性を確認するディジタル署名方式に関し、特に安全性が高く、耐量子コンピュータ性をもつディジタル署名方式に関するものである。
【背景技術】
【０００２】
「ディジタル署名」とは，送られてきたデータの送信元が間違いないか，伝送経路上でデータが改ざんされていないかを確認するための技術である。従来提案されているディジタル署名方式の代表例として岡本方式やＦｉａｔ−Ｓｈａｍｉｒ方式（Ｆｉａｔ，Ａ．ａｎｄ Ｓｈａｍｉｒ，Ａ：“Ｈｏｗ ｔｏ ｐｒｏｖｅ ｙｏｕｒｓｅｌｆ：ｐｒａｃｔｉｃａｌ ｓｏｌｕｔｉｏｎｓ ｔｏ ｉｄｅｎｔｉｆｉｃａｔｉｏｎ ａｎｄ ｓｉｇｎａｔｕｒｅ ｐｒｏｂｌｅｍｓ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｃｒｙｐｔｏ８６，Ｓａｎｔａ Ｂａｒｂａｒａ，Ａｕｇｕｓｔ１９８６，ｐｐ．１８−１−１８−７）がある。
【０００３】
岡本方式の署名方式は、以下の通りである。署名者Ａは素数ｐ，ｑ（ｑはｐ−１の因数の１つ）と乱数ｒ（２以上ｐ−１以下）とからｒｑｍｏｄ ｐを計算し、１となるｑを２つ見つけてｇ１，ｇ２とし、これらと乱数ｓ１，ｓ２とからｖ＝ｇ１−ｓ１・ｇ２−ｓ２ｍｏｄ ｐを計算し、ｐ，ｑ，ｇ１，ｇ２，ｔ，ｖ（ｔは安全性の度合いを示すパラメータ）を公開し、ｓ１，ｓ２を自分の秘密鍵とする。Ａは文書Ｍに対する署名を行うには、乱数ｒ１，ｒ２を発生し、ｘ＝ｇ１ｒ１・ｇ２ｒ２ｍｏｄ ｐを計算し、ハッシュ関数演算器でｅ＝ｈ（ｘ，Ｍ）を計算し、秘密鍵ｓ１，ｓ２を用い、ｙ１＝ｒ１＋ｅ・ｓ１ｍｏｄｑ、ｙ２＝ｒ２＋ｅ・ｓ２ｍｏｄ ｑを計算し、署名（ｅ，ｙ１，ｙ２）とＭを検証者Ｂへ送る。Ｂはｗ＝ｇ１ｙ１・ｇ２ｙ２・ｖｅｍｏｄ ｐを計算し、ｗ＝ｘかを判定し、成立すれば合格とする。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許公開平６−５９６２６ ディジタル署名方式 日本電信電話株式会社 岡本 龍明 特許出願平４−２１５８０９
【発明の概要】
【発明が解決しようとする課題】
【０００５】
Ｆｉａｔ−Ｓｈａｍｉｒ方式の安全性は、法の合成数の素因数分解の困難さに依存する。岡本方式の安全性は、法の合成数の素因数分解の困難さに依存すること、及び乗法群上の離散対数問題の計算量上の困難さに依存することであり、量子コンピュータが出現するといずれの問題も多項式時間で解読可能と予想されている。
【０００６】
このように岡本方式やＦｉａｔ−Ｓｈａｍｉｒ方式は、耐量子コンピュータ性がなく、量子コンピュータが出現すると多項式時間で解読されてしまうと予想されている。この発明の目的は、安全性をＮＰ完全問題の１つである高次多変数連立代数方程式の解法に依存する方式を採用することにより、耐量子コンピュータ性を持つディジタル署名方式を提案することにある。
【課題を解決するための手段】
【０００７】
信頼のおける第３者機関であるシステムセンタは３以上の素数ｑおよび３つの整数ｄ，ｒ，ｍを選び公開する。利用者Ａ（署名者）は、システム加入時に、秘密鍵［ｋｉ，Ａｉ（ｉ＝１，．．，ｍ）］を選ぶ。ここで、ｋｉ（ｉ＝１，．．，ｍ）を有限体Ｆｑ上のｍ個の任意の要素として、Ａｉ（ｉ＝１，．．，ｍ）をＦｑ上の四元数環Ｈ上の互いに非可換となるｍ個の要素とする。１つの要素ＡｉはＦｑ上の４つの要素から成り立っている四元数である。利用者Ａは公開されている４つのシステムパラメータ［ｑ，ｄ，ｒ，ｍ］と秘密鍵［ｋｉ，Ａｉ（ｉ＝１，．．，ｍ）］から、公開鍵である四元数環上の暗号化関数Ｆ（Ｘ）を以下のように生成する。
【０００８】
【数１】
【０００９】
利用者ＡはＦ（Ｘ）を展開して、展開式の係数ｆｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｆｊｅ０ｅ１ｅ２ｅ３｝を利用者Ａの公開鍵として、利用者Ａの識別情報ＩＤと対にしてシステムセンタに送る（図２）。ｆｊｅ０ｅ１ｅ２ｅ３は以下のような形をしている。四元数Ｆ（Ｘ）の要素表現形式を（ｆ０，ｆ１，ｆ２，ｆ３）とすると、
【００１０】
【数２】
【００１１】
ここで、１＋ｒ＋…＋ｒｄ＝ｓとして、
ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｆｊを与える式の右辺の項数ｎは、
ｎ＝４Ｈｓ＝３＋ｓＣ３＝（ｓ＋３）（ｓ＋２）（ｓ＋１）／６
となる。
【００１２】
利用者Ａが利用者Ｂに署名Ｓを以下のように送る。
利用者Ａは、すべてのＡｉ（ｉ＝１，．．，ｍ）と非可換な四元数環Ｈの任意の要素Ｒを選ぶ。
利用者Ａは、送信するメッセージＥ＝（Ｅ０，Ｅ１，Ｅ２，Ｅ３）∈Ｈから、ｇ＝Ｅ０＋Ｅ１＋Ｅ２＋Ｅ３を生成する。
利用者Ａは自分の秘密鍵［ｋｉ，Ａｉ（ｉ＝１，．．，ｍ）］と選んだ要素Ｒを用いて、Ｆｑ上の四元数環上の補助暗号化関数Ｔ（Ｘ）を以下のように生成する。
【００１３】
【数３】
【００１４】
利用者ＡはＴ（Ｘ）を展開して、展開式の係数ｔｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｔｊｅ０ｅ１ｅ２ｅ３｝を求める。
ｔｊｅ０ｅ１ｅ２ｅ３は以下のような形をしている。
四元数Ｔ（Ｘ）の要素表現形式を（ｔ０，ｔ１，ｔ２，ｔ３）とすると
【００１５】
【数４】
【００１６】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｔｊを与える式の右辺の項数ｎは、
ｎ＝４Ｈｓ＝３＋ｓＣ３＝（ｓ＋３）（ｓ＋２）（ｓ＋１）／６
となる。
【００１７】
利用者ＡはメッセージＥと署名Ｓ＝［｛ｔｊｅ０ｅ１ｅ２ｅ３｝，Ｒ］を利用者Ｂに送る（図３の上段）。
【００１８】
利用者Ｂはシステムセンタの公開鍵管理簿から入手した利用者Ａの公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝と利用者Ａから送られてきたメッセージＥと署名Ｓから以下の手順で検証する。
まず、メッセージＥ＝（Ｅ０，Ｅ１，Ｅ２，Ｅ３）∈Ｈから、ｇ＝Ｅ０＋Ｅ１＋Ｅ２＋Ｅ３を生成する。
【００１９】
次に、利用者ＢはＦ（ＲｇＥ）≠Ｔ（ＲＥ）であることを確認する。
利用者Ｂは｛ｆｊｅ０ｅ１ｅ２ｅ３｝からＦ（ＲｇＥ）の要素表現形式（ｆ’０，ｆ’１，ｆ’２，ｆ’３）を求める。
ＲｇＥ＝（ｂ０，ｂ１，ｂ２，ｂ３）とおくと、
【００２０】
【数５】
【００２１】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｆ’ｊを与える式の右辺の項数ｎは、
ｎ＝４Ｈｓ＝３＋ｓＣ３＝（ｓ＋３）（ｓ＋２）（ｓ＋１）／６
となる。
【００２２】
同様にして、利用者Ｂは｛ｔｊｅ０ｅ１ｅ２ｅ３｝からＴ（ＲＥ）の要素表現形式（ｔ’０，ｔ’１，ｔ’２，ｔ’３）を求める。
ＲＥ＝（ｃ０，ｃ１，ｃ２，ｃ３）とおくと
【００２３】
【数６】
【００２４】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｔ’ｊを与える式の右辺の項数ｎは、
ｎ＝４Ｈｓ＝３＋ｓＣ３＝（ｓ＋３）（ｓ＋２）（ｓ＋１）／６
となる。
【００２５】
利用者Ｂは
Ｔ（ＲＥ）＝（ｔ’０，ｔ’１，ｔ’２，ｔ’３）≠（ｆ’０，ｆ’１，ｆ’２，ｆ’３）＝Ｆ（ＲｇＥ）
を確認する。等しければ送られてきたＳは利用者Ａの署名でないと判定する（図３下段）。
【００２６】
利用者Ｂは、任意の整数ｐを選び、以下のように
Ｆ（Ｒｇ＋ｐ）＝Ｔ（Ｒｐ＋１）
を確認する。
【００２７】
利用者Ｂは｛ｆｊｅ０ｅ１ｅ２ｅ３｝からＦ（Ｒｇ＋ｐ）の要素表現形式（ｆ’’０，ｆ’’１，ｆ’’２，ｆ’’３）を求める。
Ｒｇ＋ｐ＝（ｂ０，ｂ１，ｂ２，ｂ３）とおいて、
【００２８】
【数７】
【００２９】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｆ”ｊを与える式の右辺の項数ｎは、
ｎ＝４Ｈｓ＝３＋ｓＣ３＝（ｓ＋３）（ｓ＋２）（ｓ＋１）／６
となる。
【００３０】
同様にして、利用者ＢはＴ（Ｒｐ＋１）の要素表現形式（ｔ’’０，ｔ’’１，ｔ’’２，ｔ’’３）を求める。
Ｒｐ＋１＝（ｃ０，ｃ１，ｃ２，ｃ３）とおくと、
【００３１】
【数８】
【００３２】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｔ”ｊを与える式の右辺の項数ｎは、
ｎ＝４Ｈｓ＝３＋ｓＣ３＝（ｓ＋３）（ｓ＋２）（ｓ＋１）／６
となる。
【００３３】
利用者Ｂは
Ｆ（Ｒｐ＋ｇ）＝（ｔ’’０，ｔ’’１，ｔ’’２，ｔ’’３）＝（ｆ’’０，ｆ’’１，ｆ’’２，ｆ’’３）＝Ｔ（Ｒｐ＋１）
を確認する。その結果が一致するかどうかを検証し、その検証に合格すればＳは利用者Ａの正当な署名文書と判定することにより署名文書の正当性を確認する（図４）。
【００３４】
［００１０］で公開される集合｛ｆｊｅ０ｅ１ｅ２ｅ３｝の値から秘密鍵［ｋｉ，Ａｉ（ｉ＝１，．．，ｍ）］を求めることが高次元多変数連立代数方程式の解法に帰結される。この解法問題はＮＰ完全問題の一つである。
【００３５】
ところで、岡本方式の安全性は、法の合成数の素因数分解の困難さや素数を法とする離散対数問題の困難さに依存する。
【００３６】
一方、本発明方式の安全性は、有限体Ｆｑ上の高次多変数連立代数方程式の解法の困難さに依存する。次数を大きくし、変数の数を多くすることにより、耐量子コンピュータ性をもつディジタル署名方式である。
【発明の効果】
【００３７】
岡本方式やＦｉａｔ−Ｓｈａｍｉｒ方式の安全性は、法の合成数の素因数分解の困難さや素数を法とする離散対数問題の困難さに依存するので、量子コンピュータが出現すると、多項式時間で解読可能となる恐れがある。
【００３８】
一方、本発明においては、有限体Ｆｑ上の高次多変数連立代数方程式の解法の困難さに依存するディジタル署名方式が、高次多変数連立代数方程式の解法がＮＰ完全問題の１つとなるので、量子コンピュータに耐えうるディジタル署名方式を提供できる。
【００３９】
従ってこの発明によれば安全性を高く保持するものとなる。
【００４０】
なお、本発明は、上記において説明した実施形態に限定されるものではなく、その主旨を逸脱しない範囲において種々変更可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【図面の簡単な説明】
【００４１】
【図１】本発明の一実施の形態による署名方式のブロック図である。
【図２】同実施の形態による署名方式における利用者Ａの署名処理手順のブロック図である。
【図３】同実施の形態による署名方式における利用者Ｂの検証処理手順１のブロック図である。
【図４】同実施の形態による署名方式における利用者Ｂの検証処理手順２のブロック図である。
【符号の説明】
【００４２】
１００…システムセンタ装置
２００…利用者Ａ（署名者）端末
３００…利用者Ｂ（検証者）端末
４００…安全でない通信路
１１０…システムセンタ公開鍵管理簿
２０１、２０２，２０６、３０３…乱数発生器
２０３…記憶装置
２０４…公開鍵生成装器
２０５…署名生成器
３０１，３０４，３０５…検証器
３０２，３０６…比較器
【発明を実施するための形態】
【００４３】
請求項１の発明の一実施例について説明する。
【実施例】
【００４４】
図１にこの発明の全体構成を示す。ディジタル署名を作成する利用者Ａ（署名者）装置２００と、署名を検証する利用者Ｂ（検証者）装置３００とが安全でない通信路４００を介して結合されているとする。
【００４５】
まず、システムに加入した利用者Ａは、システム加入時に、システムセンタ１００からシステムパラメータｑ，ｄ，ｒ，ｍを入手して、署名者装置２００にて基本的に一度だけ行う初期情報設定段階において、図２に示す乱数発生器２０１，２０２を用いて、秘密鍵［ｋｉ，Ａｉ（ｉ＝１，．．，ｍ）］と、公開鍵生成器２０４を用いて公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝を生成し、秘密鍵［ｋｉ，Ａｉ（ｉ＝１，．．，ｍ）］と公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝を記憶装置２０３に入力し、公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝を利用者Ａの識別情報ＩＤと対にして、システムセンタ１００の公開鍵管理簿１１０に登録する。
【００４６】
次に、利用者Ａが文書Ｅに対するディジタル署名を作成する手順について説明する。署名作成者である利用者Ａは、署名者装置２００で署名作成を行う。図３にその処理手順を示す。
利用者Ａは乱数発生器２０６を用いて四元数である乱数Ｒを生成し、記憶装置２０３に入力し、当該文書Ｅ，当該乱数Ｒを入力として署名生成器２０５を用いて｛ｔｊｅ０ｅ１ｅ２ｅ３｝を計算し、［｛ｔｊｅ０ｅ１ｅ２ｅ３｝，Ｒ］を文書Ｅに対するディジタル署名Ｓとして、ＳとＥを記憶装置２０３に入力し、検証者である利用者ＢにＳとＥを送信する。
【００４７】
次に、検証者である利用者Ｂが検証者装置３００を用いて、署名作成者である利用者Ａの署名者装置２００から送信された文書Ｅと当該文書Ｅに対するディジタル署名［｛ｔｊｅ０ｅ１ｅ２ｅ３｝，Ｒ］を検証する手順について説明する。図３，図４に署名検証手順を示す。
【００４８】
まず、Ｔ（ＲＥ）≠Ｆ（ＲｇＥ）を確認する。検証者である利用者Ｂは検証器３０１を用いて、受信した四元数である文書Ｅから、その４つの要素の和ｇを計算し、システムセンタの公開鍵管理簿から入手した利用者Ａの公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝と受信したＲとＥと計算したｇからＲｇＥを計算して、Ｆ（ＲｇＥ）＝（ｆ’０，ｆ’１，ｆ’２，ｆ’３）を生成して、比較器３０２に入力する。一方、検証器３０１を用いて、受信したＲ，ＥからＲＥを計算し、受信した｛ｔｊｅ０ｅ１ｅ２ｅ３｝とＲＥからＴ（ＲＥ）＝（ｔ’０，ｔ’１，ｔ’２，ｔ’３）を生成して、比較器３０２に入力する。比較器３０２を用いて、（ｆ’０，ｆ’１，ｆ’２，ｆ’３）と（ｔ’０，ｔ’１，ｔ’２，ｔ’３）が等しいか異なるかを検証する。利用者Ｂは等しいときはＳは利用者Ａの署名ではないと出力する。異なるときは検証器３０４を用いて、図４に示すように検証する。
【００４９】
検証者である利用者Ｂは乱数発生器３０３を用いて、整数である乱数ｐを生成し、検証器３０４に入力する。
【００５０】
検証者である利用者Ｂは検証器３０４にてＲｇ＋ｐを計算し、Ｒｇ＋ｐと公開鍵管理簿から入手した利用者Ａの公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝からＦ（Ｒｇ＋ｐ）＝（ｆ’’０，ｆ’’１，ｆ’’２，ｆ’’３）を計算し比較器３０６に入力する。
【００５１】
検証者である利用者Ｂは検証器３０５にてＲｐ＋１を計算し、Ｒｐ＋１と受信した｛ｔｊｅ０ｅ１ｅ２ｅ３｝からＴ（Ｒｐ＋１）＝（ｔ’’０，ｔ’’１，ｔ’’２，ｔ’’３）を計算し比較器３０６に入力する。
【００５２】
検証者である利用者Ｂは比較器３０６を用いて、（ｆ’’０，ｆ’’１，ｆ’’２，ｆ’’３）と（ｔ’’０，ｔ’’１，ｔ’’２，ｔ’’３）が等しいか異なるかを検証する。等しいときはＳは利用者Ａの署名であると出力する。異なるときはＳは利用者Ａの署名ではないと出力する。
【００５３】
なお、本発明は、上記において説明した実施形態に限定されるものではなく、その主旨を逸脱しない範囲において種々変更可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【産業上の利用可能性】
【００５４】
この発明は電子文書の正当性を確認するディジタル署名方式に関し、特に安全性が高く、耐量子コンピュータ性をもつディジタル署名方式を提案するものである。
【特許請求の範囲】
【請求項１】
電子的に作成したディジタル文書の正当性及び承認者を確認するためのディジタル署名を実現する方式であって、システム加入時に利用者Ａ（署名者）は、秘密鍵［ｋｉ，Ａｉ（ｉ＝１，…，ｍ）］を生成し、その秘密鍵より、公開情報である整数ｑ，ｄ，ｒ，ｍを用いて、公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝を生成し、上記署名者の識別情報ＩＤと上記公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝を対としてシステムセンタの公開鍵管理簿に登録し、署名作成処理段階において、文書Ｅに対して署名を作成したい利用者Ａ（署名者）は、乱数Ｒを生成し、それと上記ｑ，ｄ，ｒ，ｍとＥより、｛ｔｊｅ０ｅ１ｅ２ｅ３｝を生成し、上記［｛ｔｊｅ０ｅ１ｅ２ｅ３｝，Ｒ］の組を上記文書Ｅに対する署名Ｓとして、文書ＥをＳと共に利用者Ｂ（検証者）に送信し、上記署名Ｓと文書Ｅを受信した利用者Ｂ（検証者）は、上記利用者Ａ（署名者）の識別情報ＩＤに基づき上記システムセンタの公開鍵管理簿より上記公開情報ｑ，ｄ，ｒ，ｍ及び上記公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝を検索し、これらｑ，ｄ，ｒ，ｍ，｛ｆｊｅ０ｅ１ｅ２ｅ３｝と上記受信したＳとＥより、暗号化関数Ｆ（Ｘ）にＲｇＥを入力して求めた（ｆ’０，ｆ’１，ｆ’２，ｆ’３）と補助暗号化関数Ｔ（Ｘ）にＲＥを入力して求めた（ｔ’０，ｔ’１，ｔ’２，ｔ’３）が等しくないことを検証し、暗号化関数Ｆ（Ｘ）にＲｇ＋ｐを入力して求めた（ｆ’’０，ｆ’’１，ｆ’’２，ｆ’’３）と補助暗号化関数Ｔ（Ｘ）にＲｐ＋１を入力して求めた（ｔ’’０，ｔ’’１，ｔ’’２，ｔ’’３）が等しいことを検証し，合格すれば正当な署名文書と判定することにより署名文書の正当性を確認することを特徴とするディジタル署名方式。
【請求項１】
電子的に作成したディジタル文書の正当性及び承認者を確認するためのディジタル署名を実現する方式であって、システム加入時に利用者Ａ（署名者）は、秘密鍵［ｋｉ，Ａｉ（ｉ＝１，…，ｍ）］を生成し、その秘密鍵より、公開情報である整数ｑ，ｄ，ｒ，ｍを用いて、公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝を生成し、上記署名者の識別情報ＩＤと上記公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝を対としてシステムセンタの公開鍵管理簿に登録し、署名作成処理段階において、文書Ｅに対して署名を作成したい利用者Ａ（署名者）は、乱数Ｒを生成し、それと上記ｑ，ｄ，ｒ，ｍとＥより、｛ｔｊｅ０ｅ１ｅ２ｅ３｝を生成し、上記［｛ｔｊｅ０ｅ１ｅ２ｅ３｝，Ｒ］の組を上記文書Ｅに対する署名Ｓとして、文書ＥをＳと共に利用者Ｂ（検証者）に送信し、上記署名Ｓと文書Ｅを受信した利用者Ｂ（検証者）は、上記利用者Ａ（署名者）の識別情報ＩＤに基づき上記システムセンタの公開鍵管理簿より上記公開情報ｑ，ｄ，ｒ，ｍ及び上記公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝を検索し、これらｑ，ｄ，ｒ，ｍ，｛ｆｊｅ０ｅ１ｅ２ｅ３｝と上記受信したＳとＥより、暗号化関数Ｆ（Ｘ）にＲｇＥを入力して求めた（ｆ’０，ｆ’１，ｆ’２，ｆ’３）と補助暗号化関数Ｔ（Ｘ）にＲＥを入力して求めた（ｔ’０，ｔ’１，ｔ’２，ｔ’３）が等しくないことを検証し、暗号化関数Ｆ（Ｘ）にＲｇ＋ｐを入力して求めた（ｆ’’０，ｆ’’１，ｆ’’２，ｆ’’３）と補助暗号化関数Ｔ（Ｘ）にＲｐ＋１を入力して求めた（ｔ’’０，ｔ’’１，ｔ’’２，ｔ’’３）が等しいことを検証し，合格すれば正当な署名文書と判定することにより署名文書の正当性を確認することを特徴とするディジタル署名方式。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１２−１０３６５５（Ｐ２０１２−１０３６５５Ａ）
【公開日】平成２４年５月３１日（２０１２．５．３１）
【国際特許分類】
【出願番号】特願２０１０−２６８８０６（Ｐ２０１０−２６８８０６）
【出願日】平成２２年１１月１３日（２０１０．１１．１３）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成２２年６月１７日 インターネットアドレス「ｈｔｔｐ：／／ｗｗｗ．ｉａｃｒ．ｏｒｇ／」に発表
【出願人】（５１０３１８０５５）
【Ｆターム（参考）】
【公開日】平成２４年５月３１日（２０１２．５．３１）
【国際特許分類】
【出願日】平成２２年１１月１３日（２０１０．１１．１３）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成２２年６月１７日 インターネットアドレス「ｈｔｔｐ：／／ｗｗｗ．ｉａｃｒ．ｏｒｇ／」に発表
【出願人】（５１０３１８０５５）
【Ｆターム（参考）】
[ Back to top ]