(57)【特許請求の範囲】
【請求項１】
ＢＷｎｌをｎ本の紐からなる組紐群の長さｌの語の集合とし、
【数３】
0003935767.tif 000013
不定元ｖ，ｚの負巾も許す多項式の集合の成す環を表す。）を組紐の閉包として表された向き付けられた絡み目のＨＯＭＦＬＹ多項式（組紐の閉包のＨＯＭＦＬＹ多項式Ｐは準同型性、つまりＰ（ａ＃ｂ）＝Ｐ（ａ）・Ｐ（ｂ）を満たす。（ただし、ａ＃ｂは組紐の連結和を表す。））とし、Ｈ：｛０，１｝＊→｛０，１｝ｋ（ｋはセキュリティパラメータを表す。）をハッシュ関数として、
署名装置の鍵生成部が、ｘｉ∈ＢＷｎｌ（ｉ＝１，・・・，ｋ）をランダムに選び、秘密鍵として秘密に保持し、
【数４】
0003935767.tif 000014
を公開鍵として公開する手順と、
署名装置の要素ｒ生成部が、ｒｉ∈ＢＷｎｌ（ｉ＝１，・・・，ｋ）をランダムに選ぶ手順と、
署名装置の署名生成部が、（ｅ１，・・・，ｅｋ）＝Ｈ（Ｐ（ｒ１），・・・，Ｐ（ｒｋ），ｍ）を計算し、
【数５】
0003935767.tif 000015
ｍに対する署名（Ｐ（ｒ１），・・・，Ｐ（ｒｋ），ｚ１，・・・，ｚｋ）を出力する手順と、
を有することを特徴とする準同型一方向性関数を用いた署名方法。
【請求項２】
署名検証装置の署名受信手段が、請求項１に記載の準同型一方向関数を用いた署名方法により生成されたメッセージｍに対する署名（Ｐ（ｒ１），・・・，Ｐ（ｒｋ），ｚ１，・・・，ｚｋ）とメッセージｍを受け取る手順と、
署名検証装置の署名検証部が、（ｅ１，・・・，ｅｋ）＝Ｈ（Ｐ（ｒ１），・・・，Ｐ（ｒｋ），ｍ）を計算し、
【数６】
0003935767.tif 000016
が成立すれば正当な署名と判定し、そうでなければ不正な署名と判定する手順と、
を有することを特徴とする準同型一方向関数を用いた署名方法により生成された署名の署名検証方法。
【請求項３】
ＢＷｎｌをｎ本の紐からなる組紐群の長さｌの語の集合とし、
【数９】
0003935767.tif 000017
を組紐の閉包として表された向き付けられた絡み目のＨＯＭＦＬＹ多項式（組紐の閉包のＨＯＭＦＬＹ多項式Ｐは準同型性、つまりＰ（ａ＃ｂ）＝Ｐ（ａ）・Ｐ（ｂ）を満たす。（ただし、ａ＃ｂは組紐の連結和を表す。））とし、Ｈ：｛０，１｝＊→｛０，１｝ｋ（ｋはセキュリティパラメータを表す。）をハッシュ関数とし、
ｘｉ∈ＢＷｎｌ（ｉ＝１，・・・，ｋ）をランダムに選び、秘密鍵として秘密に保持し、
【数１０】
0003935767.tif 000018
を公開鍵として公開する鍵生成部と、
ｒｉ∈ＢＷｎｌ（ｉ＝１，・・・，ｋ）をランダムに選ぶ要素ｒ生成部と、
（ｅ１，・・・，ｅｋ）＝Ｈ（Ｐ（ｒ１），・・・，Ｐ（ｒｋ），ｍ）を計算し、
【数１１】
0003935767.tif 000019
ｍに対する署名（Ｐ（ｒ１），・・・，Ｐ（ｒｋ），ｚ１，・・・，ｚｋ）を出力する署名生成部と、
を備えたことを特徴とする準同型一方向性関数を用いた署名装置。
【請求項４】
請求項３に記載の準同型一方向関数を用いた署名装置により生成されたメッセージｍに対する署名（Ｐ（ｒ１），・・・，Ｐ（ｒｋ），ｚ１，・・・，ｚｋ）とメッセージｍを受け取る署名受信手段と、
（ｅ１，・・・，ｅｋ）＝Ｈ（Ｐ（ｒ１），・・・，Ｐ（ｒｋ），ｍ）を計算し、
【数１２】
0003935767.tif 000020
が成立すれば正当な署名と判定し、そうでなければ不正な署名と判定する署名検証部と、
を備えたことを特徴とする準同型一方向関数を用いた署名装置により生成された署名の署名検証装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報通信技術の応用技術に関するものであり、準同型一方向性関数を用いて電子署名を実現する署名方法、装置及び署名検証方法、装置に関する。
【０００２】
【従来の技術】
従来の電子署名方法の代表的な例として、以下のようなものである。
ＲＳＡ問題にもとづいたものとしては、以下のような"M.Bellare and P.Rogaway, The Exact Security of Digital Signatures, Proc.of Eurocrypt '96, 1996."がある。
ｋをセキュリティパラメータとし、Ｈ：[0,1]*→[0,1]2kをハッシュ関数とする。
１.鍵生成
ｋビットの素数ｐ,ｑをランダムに選び、ｎ＝ｐｑ,λ(n)＝LCM(ｐ−1,ｑ−1)を計算し、
【数１３】
0003935767.tif 000002
ｄ＝ｅ-1 modλ(n)を秘密鍵として秘密に保持する。ｎ,ｅを公開鍵として公開する。
２．署名生成
メッセージｍに対して以下のように署名を生成する。
ｈ＝Ｈ(m)を計算し、メッセージｍに対する署名ｓ＝ｈd modｎを出力する。
３．署名検証
メッセージｍに対する署名ｓを以下のように検証する。
ｓemodｎ＝Ｈ(m)が成立すれば正当な署名と判定し、そうでなければ不正な署名と判定する。
ここで、ｓemodｎ＝（ｈd）emodｎ＝ｈなので、正しく生成された署名は検証をパスする。
【０００３】
離散対数問題にもとづいたものとしては、以下のような"D.Pointcheval and J.Stern,Security Proofs for Signature Schemes, Proc.of Eurocrypt '96, 1996."がある。
ｋをセキュリティパラメータとし、Ｈ：[0,1]*→[0,1]kをハッシュ関数とする。
１.鍵生成
ｋビットの素数ｐをランダムに選び、
【数１４】
0003935767.tif 000003
ｘを秘密鍵として秘密に保持する。ｐ,ｇ,Ｘ＝ｇxを、公開鍵として公開する。
２.署名生成
メッセージｍに対して以下のように署名を生成する。
【数１５】
0003935767.tif 000004
ｅ＝Ｈ(ｇrmod p, m)を計算し、ｙ＝ｒ＋ｅｘ mod p-1とし、メッセージｍに対する署名（ｅ,ｙ）を出力する。
３.署名検証
メッセージｍに対する署名（ｅ,ｙ）を以下のように検証する。
ｅ＝Ｈ(ｇyＸ-emod p, m)が成立すれば正当な署名と判定し、そうでなけければ不正な署名と判定する。
ここでｇyＸ-emod p＝ｇr+ex（ｇx）-emod p＝ｇrなので、正しく生成された署名は検証をパスする。
【０００４】
【発明が解決しようとする課題】
従来の電子署名方法においては素因数分解問題、離散対数問題などの数論的問題に基礎をおいたものしかなく、量子計算機が実現し、これらの問題が解かれてしまうと、破られてしまうという問題点があった。
【０００５】
【課題を解決するための手段】
本発明では、数論的問題にもとづかない、一般的な準同型一方向性関数を用いて電子署名を構成することにより、量子計算機が実現しても破られない電子署名方法、装置及びその検証方法、装置を実現する。
【０００６】
【発明の実施の形態】
図１に本発明の準同型一方向性関数を用いた署名方法及び検証方法が適用される署名生成装置と署名検証装置の構成図を示す。
署名生成装置は、ハッシュ関数Ｈおよび準同型一方向性関数（ｆ：Ａ→Ｂ）を保持し、秘密鍵と公開鍵を生成する鍵生成部と、メッセージｍに対する署名を生成する署名生成部と、Ａのランダムな要素ｒ生成部とを備える。
署名検証装置は、公開鍵とハッシュ関数Ｈを保持し、署名検証部においてメッセージｍとｍに対する署名を受け取り検証する。
【０００７】
（実施例１）
本発明の実施例１について図２を参照して説明する。
ｆ：Ａ→Ｂを準同型一方向性関数、つまりｆ（ａ・ｂ）＝ｆ（ａ）・ｆ（ｂ）を満たし、関数ｆは容易に計算できるが逆関数ｆ-1を計算するのは困難であるとする。
ｋをセキュリティパラメータとし、Ｈ：｛０,１｝*→｛０,１｝kをハッシュ関数とする。
１．鍵生成
ｘi∈Ａ（ｉ＝１,・・・,ｋ）をランダムに選び、秘密鍵として秘密に保持する。Ｘi＝ｆ（ｘi）∈Ｂ（ｉ＝１,・・・,ｋ）を公開鍵として公開する。
２．署名生成
メッセージｍに対して以下のように署名を生成する。
ｒi∈Ａ（ｉ＝１,・・・,ｋ）をランダムに選び、（ｅ1,・・・,ｅk）＝Ｈ（ｆ（ｒ1）,・・・,ｆ（ｒk）,ｍ）を計算し(S1)、
【数１６】
0003935767.tif 000005
メッセージｍに対する署名（ｆ（ｒ1）,・・・,ｆ（ｒk）,ｙ1,・・・,ｙk）を出力する(S2)。
３.署名検証
メッセージｍに対する署名（ｆ（ｒ1）,・・・,ｆ（ｒk）,ｙ1,・・・,ｙk）を以下のように検証する。
（ｅ1,・・・,ｅk）＝Ｈ（ｆ（ｒ1）,・・・,ｆ（ｒk）,ｍ）を計算し(S2)、
【数１７】
0003935767.tif 000006
が成立すれば正当な署名と判定し、そうでなければ不正な署名と判定する(S3)。ここで、準同型性により
【数１８】
0003935767.tif 000007
正しく生成された署名は検証をパスする。
【０００８】
（実施例２）
本発明の実施例２を図３を参照して説明する。
実施例２は、実施例１で構成された署名において、準同型一方向性関数としてＨＯＭＦＬＹ（ホンフリー）多項式Ｐを用いたものである。
ＢＷnlをｎ本の紐からなる組紐群の長さｌの語の集合とし、
【数１９】
0003935767.tif 000008
を（組紐の閉包を取って得られる）向き付けられた絡み目のＨＯＭＦＬＹ多項式（実際にはLaurent多項式）とする。
組紐の閉包のＨＯＭＦＬＹ多項式Ｐは準同型性、つまりＰ（ａ＃ｂ）＝Ｐ（ａ）・Ｐ（ｂ）を満たす（ただし、ａ＃ｂは組紐の連結和を表す。）。
また、組紐の閉包のＨＯＭＦＬＹ多項式Ｐは、"H.R.Morton and H.B.Short,Calculating the 2-Variable Polynomial for Knots Presented as Closed Braids, Journal of Algorithms 11, pp.117-131,1990."の方法によりＯ（ｎ!ｌ3）＋Ｏ（ｎ!ｎ4ｌ2）時間で計算することができる。一方、ＨＯＭＦＬＹ多項式の逆Ｐ-1を計算する方法は知られておらず、ＢＷnlの総当たりにより逆Ｐ-1を計算するにはＯ（ｎl）時間かかる。よって、ｎを固定すると、組紐の閉包のＨＯＭＦＬＹ多項式Ｐは多項式時間で計算でき、逆Ｐ-1の計算は指数時間かかるので、Ｐは一方向性関数である。
【０００９】
ｋをセキュリティパラメータとし、Ｈ：｛０,１｝*→｛０,１｝kをハッシュ関数とする。
１．鍵生成
ｘi∈ＢＷnl（ｉ＝１,・・・,ｋ）をランダムに選び、秘密鍵として秘密に保持する。
【数２０】
0003935767.tif 000009
を公開鍵として公開する。
２.署名生成
メッセージｍに対して以下のように署名を生成する。
ｒi∈ＢＷnl（ｉ＝１,・・・,ｋ）をランダムに選び、（ｅ1,・・・,ｅk）＝Ｈ（Ｐ（ｒ1）,・・・,Ｐ（ｒk）,ｍ）を計算し(S1)、
【数２１】
0003935767.tif 000010
ｙiを（組紐のMarkov移動を適用して）ランダム化したものをｚiとし、メッセージｍに対する署名（Ｐ（ｒ1）,・・・,Ｐ（ｒk）,ｚ1,・・・,ｚk）を出力する(S2)。
３．署名検証
メッセージｍに対する署名（Ｐ（ｒ1）,・・・,Ｐ（ｒk）,ｚ1,・・・,ｚk）を以下のように検証する。
（ｅ1,・・・,ｅk）＝Ｈ（Ｐ（ｒ1）,・・・,Ｐ（ｒk）,ｍ）を計算し(S2)、
【数２２】
0003935767.tif 000011
が成立すれば正当な署名と判定し、そうでなければ不正な署名と判定する(S3)。
ここで、準同型性とMarkov移動がＨＯＭＦＬＹ多項式を変えないことにより
【数２３】
0003935767.tif 000012
なので、正しく生成された署名は検証をパスする。
【００１０】
（実施例３）
本発明の実施例３について図４を参照して説明する。
ｆ：Ａ→Ｂを準同型一方向性関数、つまりｆ（ａ・ｂ）＝ｆ（ａ）・ｆ（ｂ）を満たし、関数ｆは容易に計算できるが逆関数ｆ-1を計算するのは困難であるとする。
ｋをセキュリティパラメータとし、Ｈ：｛０,１｝*→｛０,１｝kをハッシュ関数とする。
１．鍵生成
ｘ∈Ａをランダムに選び、秘密鍵として秘密に保持する。Ｘ＝ｆ（ｘ）∈Ｂを、公開鍵として公開する。
２．署名生成
メッセージｍに対して以下のように署名を生成する。
ｒ∈Ａをランダムに選び、ｅ＝Ｈ（ｆ（ｒ）,ｍ）を計算し(S1)、ｙ＝ｒ・ｘeとし、メッセージｍに対する署名（ｅ,ｙ）を出力する(S2)。
３.署名検証
メッセージｍに対する署名（ｅ,ｙ）を以下のように検証する。
ｆ（ｙ）、Ｘ-eを計算し(S2)、
ｅ＝Ｈ（ｆ（ｙ）・Ｘ-e,ｍ）が成立すれば正当な署名と判定し、そうでなければ不正な署名と判定する(S3)。
ここで、準同型性によりｆ（ｙ）・Ｘ-e＝ｆ（ｒ・ｘe）・ｆ（ｘ）-e＝ｆ（ｒ）なので、正しく生成された署名は検証をパスする。
【００１１】
【発明の効果】
従来の電子署名方法においては素因数分解問題、離散対数問題、などの数論的問題に基礎をおいたものしかなく、量子計算機が実現しこれらの問題が解かれてしまうと、破られてしまうという問題点があった。
本発明では、数論的問題にもとづかない、一般的な準同型一方向性関数を用いて電子署名を構成することにより、量子計算機が実現しても破られない電子署名方法を実現する。
【図面の簡単な説明】
【図１】本発明が適用される署名生成装置と署名検証装置の構成図。
【図２】本発明の実施例１の鍵生成、署名生成、署名検証の手順を説明するための図。
【図３】本発明の実施例２の鍵生成、署名生成、署名検証の手順を説明するための図。
【図４】本発明の実施例３の鍵生成、署名生成、署名検証の手順を説明するための図。
【図１】
0003935767.tif 000021
【図２】
0003935767.tif 000022
【図３】
0003935767.tif 000023
【図４】
0003935767.tif 000024