(57)【要約】  署名としての安全性を保ったまま文字列の文字位置の交換を安全に実現することを目的とする。署名鍵ｓｋを用いて、Ｎ個（Ｎは２以上の整数）の文字を含むメッセージｍについて第１署名σを生成する署名生成装置（１０２）と、１以上Ｎ−１以下の整数であるパラメータｊを取得し、パラメータｊと第１署名σと署名鍵ｓｋとは異なる準同型鍵ｈｋとを用いて、メッセージｍにおけるパラメータｊ番目の文字とｊ＋１番目の文字とが入れ替わった改変メッセージの第２署名σ’を生成する準同型演算装置（１０３）とを備える。
2017061017.tif 000002
【特許請求の範囲】
【請求項１】
署名鍵を用いて、Ｎ個（Ｎは２以上の整数）の文字を含むメッセージについて第１署名を生成する署名生成装置と、
前記第１署名と前記署名鍵とは異なる準同型鍵とを用いて、前記メッセージにおいて位置が異なる２つの文字が入れ替わった改変メッセージの第２署名を生成する準同型演算装置と
を備える暗号システム。
【請求項２】
前記暗号システムは、さらに、
双対ペアリングベクトル空間の基底Ｂ０＊，・・・，ＢＮ＊であって基底Ｂ０＊，・・・，ＢＮ＊のうちＢ２＊以降の基底がＮ−１個の変換行列Ｗ１，・・・，ＷＮ−１を用いて生成された基底Ｂ０＊，・・・，ＢＮ＊を用いて、前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合を含む前記署名鍵を生成する鍵生成装置を備え、
前記署名生成装置は、
前記署名鍵に含まれる前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合と前記メッセージとを用いて、双対ペアリングベクトル空間の元であって前記メッセージに含まれる各文字を含む元の組σ１，・・・，σＮを生成し、生成した前記元の組σ１，・・・，σＮを含む前記第１署名を生成する請求項１に記載の暗号システム。
【請求項３】
前記準同型演算装置は、
パラメータを取得し、前記パラメータと前記第１署名と前記準同型鍵とを用いて、前記メッセージの前記パラメータの値であるｊ番目（ｊは１以上Ｎ−１以下の整数）の文字とｊ＋１番目の文字とが入れ替わった前記改変メッセージの前記第２署名を生成する請求項２に記載の暗号システム。
【請求項４】
前記鍵生成装置は、
前記変換行列Ｗ１，・・・，ＷＮ−１と前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合とを含む前記準同型鍵を生成し、
前記準同型演算装置は、
前記準同型鍵に含まれる前記変換行列Ｗ１，・・・，ＷＮ−１のうち前記パラメータの値であるｊ番目の変換行列Ｗｊを用いて前記第１署名に含まれる前記元の組σ１，・・・，σＮにおいて前記パラメータの値であるｊ番目のσｊとｊ＋１番目のσｊ＋１とを入れ替え、σｊとσｊ＋１とが入れ替わった入替署名を生成し、前記入替署名を用いて前記第２署名を生成する請求項３に記載の暗号システム。
【請求項５】
前記準同型演算装置は、
前記準同型鍵に含まれる前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合を用いて、双対ペアリングベクトル空間から元τ０，・・・，τＮを生成し、前記入替署名と前記元τ０，・・・，τＮとの積を用いて、前記第２署名を生成する請求項４に記載の暗号システム。
【請求項６】
前記鍵生成装置は、さらに、
双対ペアリングベクトル空間の基底Ｂ０，・・・，ＢＮの部分集合を含む検証鍵を生成し、
前記暗号システムは、さらに、
前記第２署名を検証署名として取得し、前記検証鍵を用いて、前記検証署名を検証する署名検証装置を備える請求項２から５のいずれか１項に記載の暗号システム。
【請求項７】
前記署名検証装置は、
前記第１署名を前記検証署名として取得し、前記検証鍵を用いて、前記検証署名を検証する請求項６に記載の暗号システム。
【請求項８】
前記署名検証装置は、
前記検証鍵に含まれる前記基底Ｂ０，・・・，ＢＮを用いて双対ペアリングベクトル空間の元ｃ０，・・・，ｃＮを生成し、前記元ｃ０，・・・，ｃＮと前記検証署名とのペアリング演算を実行し、ペアリング演算の演算結果に基づいて前記検証署名を検証する請求項６または７に記載の暗号システム。
【請求項９】
署名生成装置が、署名鍵を用いて、Ｎ個（Ｎは２以上の整数）の文字を含むメッセージについて第１署名を生成し、
準同型演算装置が、前記第１署名と前記署名鍵とは異なる準同型鍵とを用いて、前記メッセージにおいて位置が異なる２つの文字が入れ替わった改変メッセージの第２署名を生成する準同型署名方法。
【請求項１０】
署名鍵を用いて、Ｎ個（Ｎは２以上の整数）の文字を含むメッセージについて第１署名を生成する署名生成処理と、
前記第１署名と前記署名鍵とは異なる準同型鍵とを用いて、前記メッセージにおいて位置が異なる２つの文字が入れ替わった改変メッセージの第２署名を生成する準同型演算処理と
をコンピュータに実行させる準同型署名プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号システム、準同型署名方法及び準同型署名プログラムに関する。
【背景技術】
【０００２】
電子署名は、署名者が秘密鍵を用いてメッセージの署名を作成し、検証者が検証鍵を用いて署名とメッセージの組を検証することによって、メッセージに対する改ざんが行われていないことを保証する技術である。メッセージに対する全ての改ざんを検知するために、通常の電子署名では、メッセージに対して署名が生成されると、少しでもメッセージに改変が加えられた場合正しいメッセージであると検証されることは無い。よって署名を作成したメッセージにはいかなる編集も行うことができない。【０００３】
一方、準同型署名とは、署名が作成されたメッセージに対して、一定の範囲で改変することが可能な、すなわち改変されたメッセージに対する署名を元のメッセージの署名から生成可能な方式のことを指す。メッセージに対して可能な改変の種類によってさまざまな準同型署名方式が提案されている。例えば、メッセージをベクトルとみなした場合に、複数のベクトルの署名から、それらのベクトルの線型和へと改変することが可能な方式について特許文献１および非特許文献１において記されている。また非特許文献２においては、メッセージを集合とみなした場合に、その部分集合へと改変することが可能な方式や、メッセージを文字列とみなした場合に、その部分文字列へと改変することが可能な方式について記されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１４−１５８２６５号公報
【非特許文献】
【０００５】
【非特許文献１】Ｂ．ＬＩＢＥＲＴ  ，  Ｍ．ＪＯＹＥ，  Ｍ．ＹＵＮＧ  「Ｌｉｎｅａｒｌｙ  ｈｏｍｏｍｏｒｐｈｉｃ  ｓｔｒｕｃｔｕｒｅ−ｐｒｅｓｅｒｖｉｎｇ  ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  ｔｈｅｉｒ  ａｐｐｌｉｃａｔｉｏｎｓ」  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ  ２０１３、ＬＮＣＳ  ８０４３、２８９−３０７ページ、２０１３年
【非特許文献２】Ｎ．  ＡＴＴＲＡＰＡＤＵＮＧ，  Ｂ．  ＬＩＢＥＲＴ，  Ｔ．ＰＥＴＥＲＳ  「Ｃｏｍｐｕｔｉｎｇ  ｏｎ  Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｄａｔａ  ：  Ｎｅｗ  Ｐｒｉｖａｃｙ  Ｄｅｆｉｎｉｔｉｏｎｓ  ａｎｄ  Ｃｏｎｓｔｒｕｃｔｉｏｎｓ」Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＡＳＩＡＣＲＹＰＴ  ２０１２、ＬＮＣＳ  ７６５８、３６７−３８５ページ、２０１２年
【発明の概要】
【発明が解決しようとする課題】
【０００６】
準同型署名においては、メッセージに対する可能な改変の種類が多くなることが、多彩な応用を生み出すうえで必要となる。従来の準同型署名のいずれにおいても、改変の種類として文字列の文字位置の交換を実現する方式は存在しない。これは、既存の方式において用いられている数学的な構造と改変方法では、文字列の文字位置交換を署名としての安全性を保ったまま実現する事が困難であったためである。すなわち、従来の準同型署名では、改変の種類として文字列の文字位置の交換を実現することはできないという課題があった。【０００７】
この発明は、これまでの方式とは異なる数学的構造を用いることによって、署名としての安全性を保ったまま文字列の文字位置の交換を安全に実現することが可能な準同型署名方式の実現を目的とする。
【課題を解決するための手段】
【０００８】
この発明に係る暗号システムは、
署名鍵を用いて、Ｎ個（Ｎは２以上の整数）の文字を含むメッセージについて第１署名を生成する署名生成装置と、
前記第１署名と前記署名鍵とは異なる準同型鍵とを用いて、前記メッセージにおいて位置が異なる２つの文字が入れ替わった改変メッセージの第２署名を生成する準同型演算装置とを備える。
【発明の効果】
【０００９】
この発明に係る暗号システムによれば、署名と準同型鍵とを用いて、メッセージにおいて位置が異なる２つの文字が入れ替わった改変メッセージの第２署名を生成することができるので、署名としての安全性を保ったまま文字の文字位置の交換を実現する準同型署名方式を提供することができるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】実施の形態１に係る暗号システム１００のシステム構成図。
【図２】実施の形態１に係る鍵生成装置１０１の構成を示す図。
【図３】実施の形態１に係る署名生成装置１０２の構成を示す図。
【図４】実施の形態１に係る準同型演算装置１０３の構成を示す図。
【図５】実施の形態１に係る署名検証装置１０４の構成を示す図。
【図６】実施の形態１に係る暗号システム１００の準同型署名処理Ｓ１００及び準同型署名方法５００の流れを示すフロー図。
【図７】実施の形態１に係る鍵生成処理Ｓ１０１の処理の流れを示すフロー図。
【図８】実施の形態１に係る鍵生成アルゴリズムの実行処理である鍵生成アルゴリズム実行処理（ステップＳ１１２）のフロー図。
【図９】実施の形態１に係る鍵生成アルゴリズムの実行処理である鍵生成アルゴリズム実行処理（ステップＳ１１２）のフロー図。
【図１０】実施の形態１に係る署名生成処理Ｓ１０２の処理の流れを示すフロー図。
【図１１】実施の形態１に係る署名生成アルゴリズムの実行処理である署名生成アルゴリズム実行処理（ステップＳ１２２）のフロー図。
【図１２】実施の形態１に係る準同型演算処理Ｓ１０３の処理の流れを示すフロー図。
【図１３】実施の形態１に係る準同型演算アルゴリズムの実行処理である準同型演算アルゴリズム実行処理（ステップＳ１３２）のフロー図。
【図１４】実施の形態１に係る署名検証処理Ｓ１０４の処理の流れを示すフロー図。
【図１５】実施の形態１に係る署名検証アルゴリズムの実行処理である署名検証アルゴリズム実行処理（ステップＳ１４２）のフロー図。
【図１６】実施の形態１の変形例に係る鍵生成装置１０１の構成を示す図。
【図１７】実施の形態１の変形例に係る署名生成装置１０２の構成を示す図。
【図１８】実施の形態１の変形例に係る準同型演算装置１０３の構成を示す図。
【図１９】実施の形態１の変形例に係る署名検証装置１０４の構成を示す図。
【発明を実施するための形態】
【００１１】
まず、実施の形態の説明における記法について、以下に説明する。
（１）ｙ←Ａは、Ａがランダムな変数または分布であるとき、Ａの分布に従いＡからｙを一様ランダムに選択したこと、すなわちｙがＡ上の一様乱数であることを表す。
（２）ｙ：＝ｚは、ｙがｚにより定義された集合であること、またはｚが変数ｙに代入されたことを表す。
（３）Ｆｑは、位数ｑの有限体を示す。
（４）下記の数１は、有限体Ｆｑにおけるベクトル表示を表す。
【数１】
2017061017.tif 000003
（５）ＸＴは、行列Ｘの転置行列を表す。
（６）Ｂ：＝（ｂ１，・・・，ｂＮ），Ｂ＊：＝（ｂ１＊，・・・，ｂＮ＊）は、ベクトルｂ１，・・・，ｂＮおよびｂ１＊，・・・，ｂＮ＊からなる基底Ｂ、Ｂ＊をあらわす。
（７）下記の数２は、基底ＢおよびＢ＊上の元の係数ベクトルによる表記を表す。
【数２】
2017061017.tif 000004
（８）下記の数３は、有限体Ｆｑ上のＮ次元ベクトル空間Ｖを示す。
【数３】
2017061017.tif 000005
（９）下記の数４は、空間Ｖの標準基底Ａ：＝（ａ１，・・・，ａＮ）のａｉを表す。
【数４】
2017061017.tif 000006
（１０）下記の数５は、空間Ｖにおけるペアリングの定義を示す。
【数５】
2017061017.tif 000007
【００１２】
次に、実施の形態の説明における数学的概念について、以下に説明する。
まず、対称双線型ペアリング群について説明する。
対称双線型ペアリング群（ｑ，Ｇ，ＧＴ，ｇ、ｅ）は、素数ｑと、素数ｑを位数ｑとした加法巡回群Ｇと、位数ｑの乗法巡回群ＧＴと、ｇ≠０∈Ｇと、多項式時間で計算可能な非退化双線型ペアリングｅ：Ｇ×Ｇ→ＧＴとの組である。非退化双線型ペアリングは、ｅ（ｓｇ、ｔｇ）＝ｅ（ｇ，ｇ）ｓｔであり、ｅ（ｇ，ｇ）≠１である。
【００１３】
次に、双対ペアリングベクトル空間について説明する。
双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は対称双線型ペアリング群（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の直積によって構成することができる。双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、素数ｑ、数３に示すＦｑ上のＮ次元ベクトル空間Ｖ、位数ｑの乗法巡回群ＧＴ、空間Ｖの標準基底Ａ：＝（ａ１，・・・，ａＮ）、ペアリングｅの組である。ａｉは、数４に示すとおりである。
【００１４】
空間Ｖにおけるペアリングは、数５によって定義される。これは、非退化双線型である。つまり、ｅ（ｓｘ，ｔｙ）＝ｅ（ｘ，ｙ）ｓｔであり、全てのｙ∈Ｖに対してｅ（ｘ，ｙ）＝１の場合、ｘ＝０である。また、全てのｉとｊに対して、ｅ（ａｉ，ａｊ）＝ｅ（ｇ，ｇ）δｉ，ｊである。ここでｉ＝ｊであれば、δｉ，ｊであり、ｉ≠ｊであれば、δｉ，ｊ＝０である。また、ｅ（ｇ，ｇ）≠１∈ＧＴである。
【００１５】
なお、本実施の形態では、上述した対称双線型ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。なお、非対称双線型ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を非対称双線型ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することができる。
【００１６】
実施の形態１．
＊＊＊構成の説明＊＊＊
図１は、本実施の形態に係る暗号システム１００のシステム構成図である。
図１に示すように、暗号システム１００は、鍵生成装置１０１、署名生成装置１０２、準同型演算装置１０３、署名検証装置１０４を備える。
まず、図１を用いて、暗号システム１００の各装置の機能の概要について説明する。
【００１７】
鍵生成装置１０１は、鍵生成パラメータ（１ｋ，Ｎ）を取得し、鍵生成アルゴリズムを実行し、検証鍵ｖｋと署名鍵ｓｋと準同型鍵ｈｋとを生成する。
ここで、暗号システム１００における方式の安全性を保つために、署名鍵ｓｋは署名の生成の実行を許可されたユーザあるいは装置にのみに渡される。また、準同型鍵ｈｋは準同型演算の実行を許可されたユーザあるいは装置にのみに渡される。署名鍵ｓｋと準同型鍵ｈｋとは、上記以外の許可されていないユーザあるいは装置に対しては秘匿される秘密鍵である。検証鍵ｖｋは公開鍵である。
【００１８】
署名生成装置１０２は、鍵生成装置１０１から署名鍵ｓｋを取得し、入力装置からメッセージｍを取得する。署名生成装置１０２は、取得した署名鍵ｓｋ及びメッセージｍとに基づいて、署名生成アルゴリズムを実行して、第１署名σを出力する。
【００１９】
準同型演算装置１０３は、鍵生成装置１０１から準同型鍵ｈｋを取得し、署名生成装置１０２から第１署名σを取得し、入力装置からパラメータｊを取得する。準同型演算装置１０３は、取得した準同型鍵ｈｋと、第１署名σと、パラメータｊとに基づいて、準同型演算アルゴリズムを実行して第２署名σ’を出力する。第２署名σ’は、準同型演算アルゴリズムを実行した後の署名であり、演算後署名ともいう。
【００２０】
署名検証装置１０４は、鍵生成装置１０１から検証鍵ｖｋを取得すると共に検証署名ｖσを取得し、署名検証アルゴリズムを実行して検証署名ｖσの検証結果ｒを出力する。ここで、検証署名ｖσは、第１署名σあるいは第２署名σ’である。
【００２１】
＜鍵生成装置１０１の構成＞
図２は、本実施の形態に係る鍵生成装置１０１の構成を示す図である。
鍵生成装置１０１は、鍵生成パラメータ受信部３０１と、鍵生成部３０２と、鍵送信部３０３とを有する。
鍵生成装置１０１は、コンピュータである。鍵生成装置１０１における鍵生成パラメータ受信部３０１と、鍵生成部３０２と、鍵送信部３０３との機能を、鍵生成装置１０１の「部」の機能ともいう。鍵生成装置１０１の「部」の機能は、ソフトウェアで実現される。鍵生成装置１０１は、プロセッサ９０１ａ、記憶装置９０２ａ、入力装置９０３ａ、出力装置９０４ａといったハードウェアを備える。
【００２２】
＜署名生成装置１０２の構成＞
図３は、本実施の形態に係る署名生成装置１０２の構成を示す図である。
署名生成装置１０２は、署名鍵受信部３０４と、メッセージ受信部３０５と、署名生成部３０６と、署名送信部３０７とを有する。
署名生成装置１０２は、コンピュータである。署名生成装置１０２における署名鍵受信部３０４と、メッセージ受信部３０５と、署名生成部３０６と、署名送信部３０７との機能を、署名生成装置１０２の「部」の機能ともいう。署名生成装置１０２の「部」の機能は、ソフトウェアで実現される。署名生成装置１０２は、プロセッサ９０１ｂ、記憶装置９０２ｂ、入力装置９０３ｂ、出力装置９０４ｂといったハードウェアを備える。
【００２３】
＜準同型演算装置１０３の構成＞
図４は、本実施の形態に係る準同型演算装置１０３の構成を示す図である。
準同型演算装置１０３は、準同型鍵受信部３０８と、パラメータ受信部３０９と、署名受信部３１０と、準同型演算部３１１と、第２署名送信部３１２とを有する。
準同型演算装置１０３は、コンピュータである。準同型演算装置１０３における準同型鍵受信部３０８と、パラメータ受信部３０９と、署名受信部３１０と、準同型演算部３１１と、第２署名送信部３１２との機能を、準同型演算装置１０３の「部」の機能ともいう。準同型演算装置１０３の「部」の機能は、ソフトウェアで実現される。準同型演算装置１０３は、プロセッサ９０１ｃ、記憶装置９０２ｃ、入力装置９０３ｃ、出力装置９０４ｃといったハードウェアを備える。
【００２４】
＜署名検証装置１０４の構成＞
図５は、本実施の形態に係る署名検証装置１０４の構成を示す図である。
署名検証装置１０４は、検証鍵受信部３１３と、署名受信部３１４と、署名検証部３１５と、検証結果送信部３１６とを有する。
署名検証装置１０４は、コンピュータである。署名検証装置１０４における検証鍵受信部３１３と、署名受信部３１４と、署名検証部３１５と、検証結果送信部３１６との機能を、署名検証装置１０４の「部」の機能ともいう。署名検証装置１０４の「部」の機能は、ソフトウェアで実現される。署名検証装置１０４は、プロセッサ９０１ｄ、記憶装置９０２ｄ、入力装置９０３ｄ、出力装置９０４ｄといったハードウェアを備える。
【００２５】
ここで、図２から図５を用いて、暗号システム１００が備える各装置のハードウェアについて説明する。以下の説明では、プロセッサ９０１ａ，９０１ｂ，９０１ｃ，９０１ｄを総称してプロセッサ９０１として説明する。記憶装置９０２、入力装置９０３、出力装置９０４についても同様とする。また、鍵生成装置１０１と署名生成装置１０２と準同型演算装置１０３と署名検証装置１０４との各装置を、暗号システム１００の各装置ともいう。
暗号システム１００の各装置は、プロセッサ９０１、記憶装置９０２、入力装置９０３、出力装置９０４といったハードウェアを備える。プロセッサ９０１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００２６】
プロセッサ９０１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ・Ｃｉｒｃｕｉｔ）である。プロセッサ９０１は、具体的には、ＣＰＵ（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ）である。
【００２７】
記憶装置９０２は、補助記憶装置及びメモリを含む。補助記憶装置は、具体的には、ＲＯＭ（Ｒｅａｄ・Ｏｎｌｙ・Ｍｅｍｏｒｙ）、フラッシュメモリ、又は、ＨＤＤ（Ｈａｒｄ・Ｄｉｓｋ・Ｄｒｉｖｅ）である。メモリは、具体的には、ＲＡＭ（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）である。
【００２８】
入力装置９０３の具体例としては、マウス、キーボード、又は、タッチパネルがある。
出力装置９０４の具体例としては、ディスプレイがある。ディスプレイは、具体的には、ＬＣＤ（Ｌｉｑｕｉｄ・Ｃｒｙｓｔａｌ・Ｄｉｓｐｌａｙ）である。
【００２９】
暗号システム１００の各装置は、通信装置を備えていてもよい。通信装置は、データを受信するレシーバ及びデータを送信するトランスミッタを含む。通信装置は、具体的には、通信チップ又はＮＩＣ（Ｎｅｔｗｏｒｋ・Ｉｎｔｅｒｆａｃｅ・Ｃａｒｄ）である。入力装置９０３及び出力装置９０４として、通信装置を用いてもよい。
【００３０】
補助記憶装置には、「部」の機能を実現するプログラムが記憶されている。このプログラムは、メモリにロードされ、プロセッサ９０１に読み込まれ、プロセッサ９０１によって実行される。補助記憶装置には、ＯＳ（Ｏｐｅｒａｔｉｎｇ・Ｓｙｓｔｅｍ）も記憶されている。ＯＳの少なくとも一部がメモリにロードされ、プロセッサ９０１はＯＳを実行しながら、「部」の機能を実現するプログラムを実行する。
【００３１】
暗号システム１００の各装置は、１つのプロセッサ９０１のみを備えていてもよいし、複数のプロセッサ９０１を備えていてもよい。複数のプロセッサ９０１が「部」の機能を実現するプログラムを連携して実行してもよい。
【００３２】
「部」の処理の結果を示す情報、データ、信号値、及び、変数値は、補助記憶装置、メモリ、又は、プロセッサ９０１内のレジスタ又はキャッシュメモリに記憶される。
【００３３】
「部」の機能を実現するプログラムは、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｃ）等の可搬記録媒体に記憶されてもよい。
なお、準同型署名プログラム５１０は、暗号システム１００の各装置の「部」として説明している機能を実現するプログラムである。また、準同型署名プログラムプロダクトと称されるものは、「部」として説明している機能を実現するプログラムが記録された記憶媒体及び記憶装置であり、見た目の形式に関わらず、コンピュータ読み取り可能なプログラムをロードしているものである。
【００３４】
＊＊＊動作の説明＊＊＊
＜暗号システム１００の準同型署名処理Ｓ１００及び準同型署名方法５００＞
図６は、本実施の形態に係る暗号システム１００の準同型署名処理Ｓ１００及び準同型署名方法５００の流れを示すフロー図である。
【００３５】
鍵生成処理Ｓ１０１において、鍵生成装置１０１は、入力装置９０３ａにより鍵生成パラメータ（１ｋ，Ｎ）を取得し、検証鍵ｖｋと署名鍵ｓｋと準同型鍵ｈｋとを生成する。
署名生成処理Ｓ１０２において、署名生成装置１０２は、入力装置９０３ｂにより署名鍵ｓｋとＮ個の文字を含むメッセージｍとを取得し、メッセージｍの第１署名σを生成する。
準同型演算処理Ｓ１０３において、準同型演算装置１０３は、入力装置９０３ｃによりパラメータｊと第１署名σと署名鍵ｓｋとは異なる準同型鍵ｈｋとを取得する。準同型演算装置１０３は、パラメータｊと第１署名σと準同型鍵ｈｋと用いて、メッセージｍのｊ番目の文字とｊ＋１番目の文字とが入れ替わった改変メッセージの第２署名σ’を生成する。
署名検証処理Ｓ１０４において、署名検証装置１０４は、入力装置９０３ｄにより検証鍵ｖｋと第１署名σあるいは第２署名σ’である検証署名ｖσとを取得し、検証署名ｖσを検証し、検証結果ｒを出力する。
【００３６】
＜鍵生成装置１０１の動作＞
図７は、本実施の形態に係る鍵生成処理Ｓ１０１の処理の流れを示すフロー図である。
ステップＳ１１１において、鍵生成パラメータ受信部３０１は、キーボードあるいは通信装置などの入力装置９０３ａを用いて鍵生成パラメータ（１ｋ，Ｎ）を受信する。ｋは、生成される鍵の強度を示すセキュリティパラメータである。鍵生成パラメータ受信部３０１は、受信した鍵生成パラメータ（１ｋ，Ｎ）を記憶装置９０２ａに書き込む。ステップＳ１１１は鍵生成パラメータ受信処理である。
ステップＳ１１２において、鍵生成部３０２は、記憶装置９０２ａに書き込まれた鍵生成パラメータ（１ｋ，Ｎ）に基づいて、鍵生成アルゴリズムを実行する。鍵生成部３０２は、鍵生成アルゴリズムを実行し、検証鍵ｖｋと署名鍵ｓｋと準同型鍵ｈｋとを生成する。鍵生成部３０２は、生成した検証鍵ｖｋと署名鍵ｓｋと準同型鍵ｈｋとを記憶装置９０２ａに書き込む。ステップＳ１１２は鍵生成アルゴリズム実行処理である。
ステップＳ１１３において、鍵送信部３０３は、通信装置などの出力装置９０４ａを用いて、検証鍵ｖｋを公開し、署名鍵ｓｋを署名生成装置１０２に送信し、準同型鍵ｈｋを準同型演算装置１０３に送信する。鍵生成装置１０１は、署名鍵ｓｋを署名生成装置１０２に安全な通信路を用いて送信し、準同型鍵ｈｋを準同型演算装置１０３に安全な通信路を用いて送信する。ステップＳ１１３は鍵送信処理ともいう。
【００３７】
図８及び図９は、本実施の形態に係る鍵生成アルゴリズムの実行処理である鍵生成アルゴリズム実行処理（ステップＳ１１２）のフロー図である。
ここで、鍵生成パラメータ受信部３０１が受信した鍵生成パラメータ（１ｋ、Ｎ）は、生成される鍵の強度を示すセキュリティパラメータｋと、署名を生成するメッセージの文字列長を表す自然数Ｎとからなる。
【００３８】
ステップＳ４０１において、鍵生成部３０２は、セキュリティパラメータｋに基づき、対称双線型ペアリング群のパラメータＰ０として、位数ｑと、位数ｑの加法巡回群Ｇ及び乗法巡回群ＧＴと、加法巡回群Ｇの生成元ｇと、ペアリングｅとを決定する。ここで、位数ｑ、群Ｇ、群ＧＴと生成元ｇは、ペアリングに適したＢＮ曲線などの楕円曲線を生成する既存のアルゴリズムよって生成される。ペアリングｅは、ｏｐｔｉｍａｌ  ａｔｅペアリングなどの既存のペアリング演算アルゴリズムを選択することで決定される。
【００３９】
ステップＳ４０２において、鍵生成部３０２は、対称双線型ペアリング群のパラメータＰ０に基づき、双対ペアリングベクトル空間のパラメータＰ１を決定する。パラメータＰ１は、位数ｑ、５次元ベクトル空間Ｖ０、７次元ベクトル空間Ｖ１、位数ｑの乗法巡回群ＧＴ、Ｖ０の標準基底Ａ０、Ｖ１の標準基底Ａ１、ペアリングｅの組である。鍵生成部３０２は、パラメータＰ１を対称双線型ペアリング群の直積とその上のペアリングとして決定する。
ステップＳ４０３において、鍵生成部３０２は、乱数ψを生成する。
【００４０】
ステップＳ４０４において、鍵生成部３０２は、行列式が０でないＦｑ上のランダム行列であるＸ０とＸ１を生成する。Ｘ０の大きさは、５×５、Ｘ１の大きさは７×７である。
ステップＳ４０５において、鍵生成部３０２は、（γ０ｉ，ｊ）：＝ψ・（Ｘ０Ｔ）−１と（γ１ｉ，ｊ）：＝ψ・（Ｘ１Ｔ）−１とを生成する。
ステップＳ４０６において、鍵生成部３０２は、標準基底Ａ０から基底Ｂ０を生成し、標準基底Ａ１から基底Ｂ１を生成する。
ステップＳ４０７において、鍵生成部３０２は、（γ０ｉ，ｊ）に基づき標準基底Ａ０から基底Ｂ０＊を生成し、（γ１ｉ，ｊ）に基づき標準基底Ａ１から基底Ｂ１＊を生成する。
ステップＳ４０４からステップＳ４０７において、Ｘ０と基底Ｂ０と基底Ｂ０＊を求める式においてはｉは１から５の整数であり、Ｘ１と基底Ｂ１と基底Ｂ１＊を求める式においてはｉは１から７の整数である。
【００４１】
ステップＳ４０８において、鍵生成部３０２は、ｇＴ：＝ｅ（ｇ，ｇ）ψを生成する。
ステップＳ４０９において、鍵生成部３０２は、行列式が０でないＦｑ上のランダム行列をＮ−１個の変換行列Ｗ１，・・・，ＷＮ−１として生成する。生成される変換行列Ｗ１，・・・，ＷＮ−１の大きさは７×７である。ステップＳ４０９において、Ｗｉのｉは１からＮ−１の整数である。
【００４２】
ステップＳ４１０において、鍵生成部３０２は、基底Ｂ１と基底Ｂ１＊と変換行列Ｗ１，・・・，ＷＮ−１とに基づき、基底Ｂ２，Ｂ３，・・・，ＢＮと基底Ｂ２＊，Ｂ３＊，・・・，ＢＮ＊を生成する。
以上のように、鍵生成部３０２は、双対ペアリングベクトル空間の基底Ｂ０，・・・，ＢＮと基底Ｂ０＊，・・・，ＢＮ＊とを生成する。基底Ｂ０，・・・，ＢＮでは、Ｂ２以降の基底がＮ−１個の変換行列Ｗ１，・・・，ＷＮ−１を用いて生成される。また、基底Ｂ０＊，・・・，ＢＮ＊では、Ｂ２＊以降の基底がＮ−１個の変換行列Ｗ１，・・・，ＷＮ−１を用いて生成される。
ステップＳ４１０において、ｉは１からＮ−１の整数であり、ｊは１から７の整数である。
【００４３】
ステップＳ４１１において、鍵生成部３０２は、基底Ｂ０，・・・，ＢＮから部分基底Ｂ０＾，・・・，ＢＮ＾を設定する。
ステップＳ４１２において、鍵生成部３０２は、基底Ｂ０＊，・・・，ＢＮ＊から部分基底Ｂ０＾＊，・・・，ＢＮ＾＊を設定する。
ステップＳ４１１及びステップＳ４１２において、ｉは１からＮの整数である。
【００４４】
ステップＳ４１３において、鍵生成部３０２は、双対ペアリングベクトル空間の基底Ｂ０，・・・，ＢＮの部分集合を含む検証鍵ｖｋを生成する。具体的には、鍵生成部３０２は、対称双線型ペアリング群のパラメータＰ０、双対ペアリングベクトル空間のパラメータＰ１、基底Ｂ０，・・・，ＢＮの各基底の部分集合Ｂ＾、基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合Ｂ＾＊を含む検証鍵ｖｋを生成する。
また、鍵生成部３０２は、基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合を含む署名鍵ｓｋを生成する。具体的には、鍵生成部３０２は、ｂ１０＊と検証鍵ｖｋとを含む署名鍵ｓｋを生成する。
また、鍵生成部３０２は、変換行列Ｗ１，・・・，ＷＮ−１と基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合とを含む準同型鍵ｈｋ＝｛ｈｋ１，・・・，ｈｋＮ−１｝を設定する。具体的には、鍵生成部３０２は、変換行列Ｗ１，・・・，ＷＮ−１と検証鍵ｖｋとを含む準同型鍵ｈｋ＝｛ｈｋ１，・・・，ｈｋＮ−１｝を生成する。
【００４５】
以上のように、鍵生成部３０２は、セキュリティパラメータｋと署名を生成するメッセージの文字列長を表す自然数Ｎの組からなる鍵生成パラメータを入力とする。鍵生成部３０２は、対称双線型ペアリング群のパラメータを生成し、双対ペアリングベクトル空間のパラメータを生成し、ランダム行列の組を生成し、ランダム行列の組から双対ペアリングベクトル空間の基底の組を生成する。そして、鍵生成部３０２は、ランダム行列の組と双対ペアリング空間の基底の組の部分集合と双線型ペアリング群のパラメータと双対ペアリングベクトル空間のパラメータからなる検証鍵ｖｋと、双対ペアリング空間の基底の要素と検証鍵ｖｋからなる署名鍵ｓｋと、ランダム行列の組と検証鍵ｖｋからなる準同型鍵ｈｋを構成する。
【００４６】
＜署名生成装置１０２の動作＞
図１０は、本実施の形態に係る署名生成処理Ｓ１０２の処理の流れを示すフロー図である。
ステップＳ１２１において、署名鍵受信部３０４は、通信装置などの入力装置９０３ｂを用いて署名鍵ｓｋを受信する。メッセージ受信部３０５は、キーボードあるいは通信装置などの入力装置９０３ｂを用いてメッセージｍを受信する。署名鍵ｓｋとメッセージｍとは、記憶装置９０２ｂに書き込まれる。ステップＳ１２１は署名鍵受信処理及びメッセージ受信処理である。
ステップＳ１２２において、署名生成部３０６は、記憶装置９０２ｂに書き込まれた署名鍵ｓｋとメッセージｍとに基づいて、署名生成アルゴリズムを実行し第１署名σを生成する。署名生成部３０６は、生成した第１署名σを記憶装置９０２ｂに書き込む。ステップＳ１２２は署名生成アルゴリズム実行処理である。
ステップＳ１２３において、署名送信部３０７は、記憶装置９０２ｂに書き込まれた第１署名σを通信装置などの出力装置９０４ｂを用いて、準同型演算装置１０３あるいは署名検証装置１０４に送信する。署名検証装置１０４に送信する場合は、署名送信部３０７は、第１署名σを検証の対象となる検証署名ｖσとして署名検証装置１０４に送信する。ステップＳ１２３は署名送信処理である。
【００４７】
図１１は、本実施の形態に係る署名生成アルゴリズムの実行処理である署名生成アルゴリズム実行処理（ステップＳ１２２）のフロー図である。
ここで、署名生成部３０６は、署名鍵受信部３０４が受信した署名鍵ｓｋと、メッセージ受信部３０５が受信したメッセージｍとを署名生成アルゴリズム実行処理に入力する。メッセージｍは、Ｆｑ上の長さＮのベクトルからなる。
【００４８】
ステップＳ４１４において、署名生成部３０６は、乱数δ０，・・・，δＮと、乱数η０と、乱数η１，１，・・・，η１，Ｎと、乱数η２，１，・・・，η２，Ｎと、乱数θ１，・・・，θＮとを生成する。
【００４９】
ステップＳ４１５において、署名生成部３０６は、双対ペアリングベクトル空間上の元σ０，・・・，σＮを、ステップＳ４１４において生成した乱数と基底Ｂ０＊，・・・，ＢＮ＊とを用いて生成する。署名生成部３０６は、署名鍵ｓｋに含まれる基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合とメッセージｍ（ｍ１，・・・，ｍＮ）とを用いて、双対ペアリングベクトル空間の元であってメッセージｍに含まれる各文字ｍｉを含む元の組σ０，σ１，・・・，σＮを生成する。
ステップＳ４１６において、署名生成部３０６は、生成した元の組σ０，σ１，・・・，σＮを含む第１署名σを生成する。ここでは、署名生成部３０６は、メッセージｍ１，・・・，ｍＮと生成した元の組σ０，σ１，・・・，σＮとを含む第１署名σを生成して出力する。
【００５０】
＜準同型演算装置１０３の動作＞
図１２は、本実施の形態に係る準同型演算処理Ｓ１０３の処理の流れを示すフロー図である。
準同型演算装置１０３の準同型演算処理Ｓ１０３は、第１署名σと署名鍵ｓｋとは異なる準同型鍵ｈｋとを用いて、メッセージｍにおいて位置が異なる２つの文字が入れ替わった改変メッセージの第２署名σ’を生成する。
ステップＳ１３１において、準同型鍵受信部３０８は、通信装置などの入力装置９０３ｃを用いて準同型鍵ｈｋを受信する。パラメータ受信部３０９は、キーボードあるいは通信装置などの入力装置９０３ｃを用いてパラメータｊを受信する。署名受信部３１０は、通信装置などの入力装置９０３ｃを用いて、第１署名σを受信する。準同型鍵受信部３０８が受信した準同型鍵ｈｋとパラメータ受信部３０９が受信したパラメータｊと署名受信部３１０が受信した第１署名σとは、記憶装置９０２ｃに書き込まれる。ステップＳ１３１は準同型鍵受信処理、パラメータ受信処理及び署名受信処理である。
ステップＳ１３２において、準同型演算部３１１は、記憶装置９０２ｃに書き込まれた準同型鍵ｈｋとパラメータｊと第１署名σとに基づいて、準同型演算アルゴリズムを実行する。準同型演算部３１１は、準同型演算アルゴリズムを実行し、第２署名σ’を生成する。準同型演算部３１１は、生成した第２署名σ’を記憶装置９０２ｃに書き込む。ステップＳ１３２は準同型演算アルゴリズム実行処理である。
ステップＳ１３３において、第２署名送信部３１２は、記憶装置９０２ｃに書き込まれた第２署名σ’を通信装置などの出力装置９０４ｃを用いて、署名検証装置１０４に送信する。このとき、第２署名送信部３１２は、第２署名σ’を検証の対象となる検証署名ｖσとして署名検証装置１０４に送信する。あるいは、さらにメッセージｍの文字位置を入れ替える場合には、第２署名送信部３１２は、第２署名送信部３１２を含む準同型演算装置１０３に第２署名σ’を再度送信する。ステップＳ１３３は第２署名送信処理である。
【００５１】
図１３は、本実施の形態に係る準同型演算アルゴリズムの実行処理である準同型演算アルゴリズム実行処理（ステップＳ１３２）のフロー図である。
ここで、準同型演算部３１１は、準同型鍵受信部３０８が受信した準同型鍵ｈｋとパラメータ受信部３０９が受信したパラメータｊと署名受信部３１０が受信した第１署名σを準同型演算アルゴリズム実行処理に入力する。パラメータｊは１以上かつＮ−１以下の整数である。パラメータｊは、メッセージｍ（ｍ１，・・・，ｍＮ）において、Ｊ番目のｍｊとＪ＋１番目のｍｊ＋１とを入れ替えることを意味する。すなわち、パラメータｊは、一つ右の文字と文字位置を交換する文字の位置を表す整数である。
【００５２】
ステップＳ４１７において、準同型演算部３１１は、第１署名σの要素σｊとσｊ＋１、及び準同型鍵ｈｋに含まれるＷｊを用いて、σｊ＾とσｊ＋１＾とを生成する。準同型演算部３１１は、準同型鍵ｈｋに含まれる変換行列Ｗ１，・・・，ＷＮ−１のうちパラメータｊの値であるｊ番目の変換行列Ｗｊを用いて第１署名σに含まれる元の組σ１，・・・，σＮにおいてｊ番目のσｊとｊ＋１番目のσｊ＋１とを入れ替える。このように準同型演算部３１１がσｊ＾とσｊ＋１＾とを生成することにより、メッセージｍのｊ番目の文字に対して付けられた第１署名σの要素と、メッセージｍのｊ＋１番目の文字に対して付けられた第１署名σの要素とを入れ替えることで文字の位置の入れ替えを実現している。ここで、第１署名σにおいてσｊとσｊ＋１とが入れ替わったものを入替署名ｃσともいう。
【００５３】
ステップＳ４１８において、準同型演算部３１１は、乱数δ’０，・・・，δ’Ｎと、乱数η’０と、乱数η’１，１，・・・，η’１，Ｎと、乱数η’２，１，・・・，η’２，Ｎと、乱数θ’１，・・・，θ’Ｎとを生成する。
【００５４】
ステップＳ４１９において、準同型演算部３１１は、準同型鍵ｈｋに含まれる基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合を用いて、双対ペアリングベクトル空間から元τ０，・・・，τＮを生成する。準同型演算部３１１は、基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合とメッセージｍ（ｍ１，・・・，ｍＮ）とを用いて、メッセージｍに含まれる各文字ｍｉから各元τ０，・・・，τＮを生成する。
【００５５】
ステップＳ４２０において、準同型演算部３１１は、入替署名ｃσ（σ０，・・・，σｊ−１，σｊ＾，σｊ＋１＾，σｊ＋２，・・・，σＮ）と、双対ペアリングベクトル空間の元τ（τ０，・・・，τＮ）との積を用いて、双対ペアリングベクトル空間の元σ０’，・・・σＮ’を生成する。準同型演算部３１１は、入替署名ｃσ（σ０，・・・，σｊ−１，σｊ＾，σｊ＋１＾，σｊ＋２，・・・，σＮ）と、ｊ番目の元とｊ＋１番目の元とを入れ替えた元（τ０，・・・，τｊ−１，τｊ＋１，τｊ，τｊ＋２，・・・，τＮ）との積を用いて、元σ０’，・・・σＮ’を生成する。
【００５６】
ステップＳ４２１において、準同型演算部３１１は、生成した元σ０’，・・・σＮ’を含む第２署名σ’を生成する。ここでは、準同型演算部３１１は、ｊ番目の文字とｊ＋１番目の文字とを入れ替えた改変メッセージｍ１，・・・，ｍｊ−１，ｍｊ＋１，ｍｊ，ｍｊ＋２，・・・，ｍＮと、生成した元σ０’，・・・σＮ’とを含む第２署名σ’を生成して出力する。すなわち、準同型演算部３１１は、入替署名ｃσと元τとを用いて第２署名σ’を生成する。
【００５７】
＜署名検証装置１０４の動作＞
図１４は、本実施の形態に係る署名検証処理Ｓ１０４の処理の流れを示すフロー図である。
署名検証処理Ｓ１０４では、署名検証装置１０４は、第２署名σ’を検証署名ｖσとして取得し、検証鍵ｖｋを用いて、検証署名ｖσを検証する。あるいは、署名検証装置１０４は、第１署名σを検証署名ｖσとして取得し、検証鍵ｖｋを用いて、検証署名ｖσを検証する。
ステップＳ１４１において、検証鍵受信部３１３は、通信装置などの入力装置９０３ｄを用いて、検証鍵ｖｋを受信する。署名受信部３１４は、通信装置などの入力装置９０３ｄを用いて検証署名ｖσを受信する。検証鍵ｖｋと検証署名ｖσとは、記憶装置９０２ｄに書き込まれる。検証署名ｖσは、第１署名σあるいは第２署名σ’であるが、どちらの署名であっても同様の署名検証処理Ｓ１０４で検証することができる。ここでは、検証署名ｖσが第１署名σであるものとして説明する。ステップＳ１４１は検証鍵受信処理及び署名受信処理である。
ステップＳ１４２において、署名検証部３１５は、記憶装置９０２ｄに書き込まれた検証鍵ｖｋと検証署名ｖσとに基づいて、署名検証アルゴリズムを実行し検証結果ｒとして０または１を出力する。０または１の検証結果ｒは、記憶装置９０２ｄに書き込まれる。ステップＳ１４２は、署名検証アルゴリズム実行処理である。
ステップＳ１４３において、検証結果送信部３１６は、記憶装置９０２ｄに書き込まれた検証結果ｒを通信装置あるいは表示装置などの出力装置９０４ｄを用いて出力する。ステップＳ１４３は、検証結果送信処理である。
【００５８】
図１５は、本実施の形態に係る署名検証アルゴリズムの実行処理である署名検証アルゴリズム実行処理（ステップＳ１４２）のフロー図である。
ここで、署名検証部３１５は、検証鍵受信部３１３が受信した検証鍵ｖｋと署名受信部３１４が受信した検証署名ｖσを署名検証アルゴリズムに入力する。
【００５９】
ステップＳ４２２において、署名検証部３１５は、乱数λと、乱数ωと、乱数φ０，・・・，φＮとを生成する。
ステップＳ４２３において、署名検証部３１５は、検証鍵ｖｋに含まれる基底Ｂ０，・・・，ＢＮを用いて双対ペアリングベクトル空間の元ｃ０，・・・，ｃＮを生成する。ステップＳ４２３において、ｉは１からＮの整数である。
【００６０】
ステップＳ４２４において、署名検証部３１５は、検証署名ｖσの要素σ０，・・・，σＮと元ｃ０，・・・，ｃＮからζを生成する。署名検証部３１５は、元ｃ０，・・・，ｃＮと検証署名ｖσとのペアリング演算を実行し、ペアリング演算の演算結果ζを生成する。
【００６１】
ステップＳ４２５において、署名検証部３１５は、乱数λと生成元ｇＴからζ’を生成する。
ステップＳ４２６において、署名検証部３１５は、ペアリング演算の演算結果ζと、乱数λと元ｇＴから生成されたζ’とに基づいて、検証署名ｖσを検証する。署名検証部３１５は、ζとζ’を比較し、等しい場合は検証結果ｒとして１を出力し、それ以外の場合は検証結果ｒとして０を出力する。
【００６２】
以上で、本実施の形態に係る暗号システム１００の準同型署名処理Ｓ１００及び準同型署名方法５００についての説明を終わる。
【００６３】
＊＊＊本実施の形態の効果の説明＊＊＊
以上のように、本実施の形態に係る暗号システムによれば、これまでの方式とは異なる数学的構造を用いることによって文字列の文字位置の交換を安全に実現することができる。
また、本実施の形態に係る暗号システムによれば、改変を施すものと改変可能な範囲を専用の準同型鍵によって制御することができる。
【００６４】
＊＊＊他の構成＊＊＊
本実施の形態では、暗号システム１００の各装置の機能がソフトウェアで実現されるが、変形例として、暗号システム１００の各装置の機能がハードウェアで実現されてもよい。
この本実施の形態の変形例について、図１６から図１９を用いて説明する。
【００６５】
図１６は、本実施の形態の変形例に係る鍵生成装置１０１の構成を示す図である。
図１７は、本実施の形態の変形例に係る署名生成装置１０２の構成を示す図である。
図１８は、本実施の形態の変形例に係る準同型演算装置１０３の構成を示す図である。
図１９は、本実施の形態の変形例に係る署名検証装置１０４の構成を示す図である。
【００６６】
図１６に示すように、鍵生成装置１０１は、処理回路９０９ａ、入力装置９０３ａ、出力装置９０４ａといったハードウェアを備える。
図１７に示すように、署名生成装置１０２は、処理回路９０９ｂ、入力装置９０３ｂ、出力装置９０４ｂといったハードウェアを備える。
図１８に示すように、準同型演算装置１０３は、処理回路９０９ｃ、入力装置９０３ｃ、出力装置９０４ｃといったハードウェアを備える。
図１９に示すように、署名検証装置１０４は、処理回路９０９ｄ、入力装置９０３ｄ、出力装置９０４ｄといったハードウェアを備える。
以下の説明では、処理回路９０９ａ，９０９ｂ，９０９ｃ，９０９ｄを総称して処理回路９０９として説明する。入力装置９０３、出力装置９０４についても同様とする。
【００６７】
処理回路９０９は、前述した「部」の機能を実現する専用の電子回路である。処理回路９０９は、具体的には、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ・Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ・Ｓｐｅｃｉｆｉｃ・Ｉｎｔｅｇｒａｔｅｄ・Ｃｉｒｃｕｉｔ）、又は、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ・Ｇａｔｅ・Ａｒｒａｙ）である。
【００６８】
「部」の機能は、１つの処理回路９０９で実現されてもよいし、複数の処理回路９０９に分散して実現されてもよい。
【００６９】
別の変形例として、暗号システム１００の各装置の機能がソフトウェアとハードウェアとの組み合わせで実現されてもよい。即ち、暗号システム１００の各装置の一部の機能が専用のハードウェアで実現され、残りの機能がソフトウェアで実現されてもよい。
【００７０】
プロセッサ９０１、記憶装置９０２、及び、処理回路９０９を、総称して「プロセッシングサーキットリ」という。つまり、暗号システム１００の各装置の構成が図２から図５及び図１６から図１９のいずれに示した構成であっても、「部」の機能は、プロセッシングサーキットリにより実現される。
【００７１】
「部」を「工程」又は「手順」又は「処理」に読み替えてもよい。また、「部」の機能をファームウェアで実現してもよい。
【００７２】
また、本実施の形態では、暗号システム１００は、鍵生成装置１０１、署名生成装置１０２、準同型演算装置１０３、署名検証装置１０４を備え、各装置が１つのコンピュータである場合について説明した。しかし、例えば、鍵生成装置１０１と署名生成装置１０２とが１つのコンピュータであってもよい。また、署名生成装置１０２と準同型演算装置１０３とが１つのコンピュータであってもよい。また、全ての装置が１つのコンピュータで実現されていても構わない。
【００７３】
また、本実施の形態では、第１署名σ及び第２署名σ’は、メッセージを含む形態であったが、メッセージに対して第１署名σあるいは第２署名σ’を添付する構成でもよい。
以上、本発明の実施の形態について説明したが、この実施の形態を部分的に実施しても構わない。具体的には、この実施の形態の説明において「部」として説明するもののうち、いずれか１つのみを採用してもよいし、いくつかの任意の組み合わせを採用してもよい。なお、本発明は、この実施の形態に限定されるものではなく、必要に応じて種々の変更が可能である。
【符号の説明】
【００７４】
１００  暗号システム、１０１  鍵生成装置、１０２  署名生成装置、１０３  準同型演算装置、１０４  署名検証装置、３０１  鍵生成パラメータ受信部、３０２  鍵生成部、３０３  鍵送信部、３０４  署名鍵受信部、３０５  メッセージ受信部、３０６  署名生成部、３０７  署名送信部、３０８  準同型鍵受信部、３０９  パラメータ受信部、３１０  署名受信部、３１１  準同型演算部、３１２  第２署名送信部、３１３  検証鍵受信部、３１４  署名受信部、３１５  署名検証部、３１６  検証結果送信部、５００  準同型署名方法、５１０  準同型署名プログラム、９０１，９０１ａ，９０１ｂ，９０１ｃ，９０１ｄ  プロセッサ、９０２，９０２ａ，９０２ｂ，９０２ｃ，９０２ｄ  記憶装置、９０３，９０３ａ，９０３ｂ，９０３ｃ，９０３ｄ  入力装置、９０４，９０４ａ，９０４ｂ，９０４ｃ，９０４ｄ  出力装置、９０９，９０９ａ，９０９ｂ，９０９ｃ，９０９ｄ  処理回路、Ｓ１００  準同型署名処理、Ｓ１０１  鍵生成処理、Ｓ１０２  署名生成処理、Ｓ１０３  準同型演算処理、Ｓ１０４  署名検証処理、ｓｋ  署名鍵、ｈｋ  準同型鍵、ｖｋ  検証鍵、σ  第１署名、σ’  第２署名、ｃσ  入替署名、ｒ  検証結果、ｍ  メッセージ、ｖσ  検証署名。
【図１】
2017061017.tif 000008
【図２】
2017061017.tif 000009
【図３】
2017061017.tif 000010
【図４】
2017061017.tif 000011
【図５】
2017061017.tif 000012
【図６】
2017061017.tif 000013
【図７】
2017061017.tif 000014
【図８】
2017061017.tif 000015
【図９】
2017061017.tif 000016
【図１０】
2017061017.tif 000017
【図１１】
2017061017.tif 000018
【図１２】
2017061017.tif 000019
【図１３】
2017061017.tif 000020
【図１４】
2017061017.tif 000021
【図１５】
2017061017.tif 000022
【図１６】
2017061017.tif 000023
【図１７】
2017061017.tif 000024
【図１８】
2017061017.tif 000025
【図１９】
2017061017.tif 000026
【手続補正書】
【提出日】平成29年8月29日(2017.8.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
双対ペアリングベクトル空間の基底Ｂ０＊，・・・，ＢＮ＊（Ｎは２以上の整数）であって基底Ｂ０＊，・・・，ＢＮ＊のうちＢ２＊以降の基底がＮ−１個の変換行列Ｗ１，・・・，ＷＮ−１を用いて生成された基底Ｂ０＊，・・・，ＢＮ＊を用いて、前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合を含む署名鍵を生成する鍵生成装置と、
前記署名鍵を用いて、Ｎ個の文字を含むメッセージについて第１署名を生成する署名生成装置であって、前記署名鍵に含まれる前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合と前記メッセージとを用いて、双対ペアリングベクトル空間の元であって前記メッセージに含まれる各文字を含む元の組σ１，・・・，σＮを生成し、生成した前記元の組σ１，・・・，σＮを含む前記第１署名を生成する署名生成装置と、
前記第１署名と前記署名鍵とは異なる準同型鍵とを用いて、前記メッセージにおいて位置が異なる２つの文字が入れ替わった改変メッセージの第２署名を生成する準同型演算装置であって、パラメータを取得し、前記パラメータと前記第１署名と前記準同型鍵とを用いて、前記メッセージの前記パラメータの値であるｊ番目（ｊは１以上Ｎ−１以下の整数）の文字とｊ＋１番目の文字とが入れ替わった前記改変メッセージの前記第２署名を生成する準同型演算装置と
を備え、
前記鍵生成装置は、
前記変換行列Ｗ１，・・・，ＷＮ−１と前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合とを含む前記準同型鍵を生成し、
前記準同型演算装置は、
前記準同型鍵に含まれる前記変換行列Ｗ１，・・・，ＷＮ−１のうち前記パラメータの値であるｊ番目の変換行列Ｗｊを用いて前記第１署名に含まれる前記元の組σ１，・・・，σＮにおいて前記パラメータの値であるｊ番目のσｊとｊ＋１番目のσｊ＋１とを入れ替え、σｊとσｊ＋１とが入れ替わった入替署名を生成し、前記入替署名を用いて前記第２署名を生成する暗号システム。
【請求項２】
前記準同型演算装置は、
前記準同型鍵に含まれる前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合を用いて、双対ペアリングベクトル空間から元τ０，・・・，τＮを生成し、前記入替署名と前記元τ０，・・・，τＮとの積を用いて、前記第２署名を生成する請求項１に記載の暗号システム。
【請求項３】
前記鍵生成装置は、さらに、
双対ペアリングベクトル空間の基底Ｂ０，・・・，ＢＮの部分集合を含む検証鍵を生成し、
前記暗号システムは、さらに、
前記第２署名を検証署名として取得し、前記検証鍵を用いて、前記検証署名を検証する署名検証装置を備える請求項１または２に記載の暗号システム。
【請求項４】
前記署名検証装置は、
前記第１署名を前記検証署名として取得し、前記検証鍵を用いて、前記検証署名を検証する請求項３に記載の暗号システム。
【請求項５】
前記署名検証装置は、
前記検証鍵に含まれる前記基底Ｂ０，・・・，ＢＮを用いて双対ペアリングベクトル空間の元ｃ０，・・・，ｃＮを生成し、前記元ｃ０，・・・，ｃＮと前記検証署名とのペアリング演算を実行し、ペアリング演算の演算結果に基づいて前記検証署名を検証する請求項３または４に記載の暗号システム。
【請求項６】
鍵生成装置が、双対ペアリングベクトル空間の基底Ｂ０＊，・・・，ＢＮ＊（Ｎは２以上の整数）であって基底Ｂ０＊，・・・，ＢＮ＊のうちＢ２＊以降の基底がＮ−１個の変換行列Ｗ１，・・・，ＷＮ−１を用いて生成された基底Ｂ０＊，・・・，ＢＮ＊を用いて、前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合を含む署名鍵を生成し、
署名生成装置が、前記署名鍵に含まれる前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合と、Ｎ個の文字を含むメッセージとを用いて、双対ペアリングベクトル空間の元であって前記メッセージに含まれる各文字を含む元の組σ１，・・・，σＮを生成し、生成した前記元の組σ１，・・・，σＮを含む第１署名であって前記メッセージについての第１署名を生成し、
準同型演算装置が、パラメータを取得し、前記パラメータと前記第１署名と前記署名鍵とは異なる準同型鍵とを用いて、前記メッセージの前記パラメータの値であるｊ番目（ｊは１以上Ｎ−１以下の整数）の文字とｊ＋１番目の文字とが入れ替わった改変メッセージの第２署名を生成し、
前記鍵生成装置が、前記変換行列Ｗ１，・・・，ＷＮ−１と前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合とを含む前記準同型鍵を生成し、
前記準同型演算装置が、前記準同型鍵に含まれる前記変換行列Ｗ１，・・・，ＷＮ−１のうち前記パラメータの値であるｊ番目の変換行列Ｗｊを用いて前記第１署名に含まれる前記元の組σ１，・・・，σＮにおいて前記パラメータの値であるｊ番目のσｊとｊ＋１番目のσｊ＋１とを入れ替え、σｊとσｊ＋１とが入れ替わった入替署名を生成し、前記入替署名を用いて前記第２署名を生成する準同型署名方法。
【請求項７】
双対ペアリングベクトル空間の基底Ｂ０＊，・・・，ＢＮ＊（Ｎは２以上の整数）であって基底Ｂ０＊，・・・，ＢＮ＊のうちＢ２＊以降の基底がＮ−１個の変換行列Ｗ１，・・・，ＷＮ−１を用いて生成された基底Ｂ０＊，・・・，ＢＮ＊を用いて、前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合を含む署名鍵を生成する鍵生成処理と、
前記署名鍵に含まれる前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合と、Ｎ個の文字を含むメッセージとを用いて、双対ペアリングベクトル空間の元であって前記メッセージに含まれる各文字を含む元の組σ１，・・・，σＮを生成し、生成した前記元の組σ１，・・・，σＮを含む第１署名であって前記メッセージについての第１署名を生成する署名生成処理と、
パラメータを取得し、前記パラメータと前記第１署名と前記署名鍵とは異なる準同型鍵とを用いて、前記メッセージの前記パラメータの値であるｊ番目（ｊは１以上Ｎ−１以下の整数）の文字とｊ＋１番目の文字とが入れ替わった改変メッセージの第２署名を生成する準同型演算処理と
をコンピュータに実行させる準同型署名プログラムであって、
前記鍵生成処理は、前記変換行列Ｗ１，・・・，ＷＮ−１と前記基底Ｂ０＊，・・・，ＢＮ＊の各基底の部分集合とを含む前記準同型鍵を生成し、
前記準同型演算処理は、前記準同型鍵に含まれる前記変換行列Ｗ１，・・・，ＷＮ−１のうち前記パラメータの値であるｊ番目の変換行列Ｗｊを用いて前記第１署名に含まれる前記元の組σ１，・・・，σＮにおいて前記パラメータの値であるｊ番目のσｊとｊ＋１番目のσｊ＋１とを入れ替え、σｊとσｊ＋１とが入れ替わった入替署名を生成し、前記入替署名を用いて前記第２署名を生成する準同型署名プログラム。
【国際調査報告】
2017061017.tif 000027
2017061017.tif 000028
2017061017.tif 000029
2017061017.tif 000030