(57)【要約】      （修正有）【課題】線形準同型な構造保存署名を生成および検証する暗号学的装置および方法を提供する。【解決手段】ベクトル(M1,…,Mn)∈＾Gnに対する線形準同型署名σの生成は、プロセッサにおいて、署名鍵sk＝{χi,γi,δi}i=1nを使って、z＝Πi=1nMi-χi、r＝Πi=1nMi-γi、u＝Πi=1nMi-δiを計算することによって、署名要素(z,r,u)を計算し、前記署名要素(z,r,u)を含む署名σを出力することによる。署名の検証は、プロセッサにおいて、(M1,…,Mn)≠(1＾G,…,1＾G)であることおよび(z,r,u)が等式1GT＝e(gz,z)・e(gr,r)・Πi=1ne(gi,Mi)、1GT＝e(hz,z)・e(h,u)・Πi=1ne(hi,Mi)を満たすことを検証することによってなされる。完全に展開された方式およびコンテキスト隠蔽型の方式も提供される。【選択図】図２
2014157354.tif 000002
【特許請求の範囲】
【請求項１】
ベクトル
【数１２４】
2014157354.tif 000126
に対する線形準同型署名σを生成する方法であって、＾付きのGは第一の群を表わし、当該方法は、装置において：
・計算手段によって、署名鍵sk＝{χi,γi,δi}i=1nを使って、
【数１２５】
2014157354.tif 000127
を計算することによって、署名要素(z,r,u)を計算する段階と；
・前記計算手段によって、前記署名要素(z,r,u)を含む署名σを出力する段階とを含む、
方法。
【請求項２】
前記署名鍵はさらに、要素
【数１２６】
2014157354.tif 000128
を含み、当該方法はさらに：
・前記計算手段によって、ランダムな要素
【数１２７】
2014157354.tif 000129
を選ぶ段階と；
・前記計算手段によって、さらなる署名要素v＝hρを計算する段階とを含み、hは第二の群の要素であり；
zの前記計算はさらに、grθによる乗算を含み、rの前記計算はさらにgz-θによる乗算を含み、uの前記計算はさらに
【数１２８】
2014157354.tif 000130
による乗算を含み、ここで、αrは整数であり、h、grおよびgzは前記第二の群の要素であり；
前記署名はさらに、前記署名要素vを含み；
前記第一の群および前記第二の群は同じである、
請求項１記載の方法。
【請求項３】
ベクトル
【数１２９】
2014157354.tif 000131
に対する署名要素(z,r,u)を含む線形準同型署名σを検証する方法であって、＾付きのGは第一の群を表わし、当該方法は、装置において：
・計算手段によって、
【数１３０】
2014157354.tif 000132
であることおよび(z,r,u)が第一の等式
【数１３１】
2014157354.tif 000133
および第二の等式
【数１３２】
2014157354.tif 000134
を満たすことを検証する段階であって、e(・,・)は対称かつ可換なペアリングを表わし、h、hz、hi、gr、giおよびgzは第二の群の要素である、段階と；
・前記計算手段によって、前記検証が成功の場合に前記署名が成功裏に検証されたと判定し、それ以外の場合に前記署名が成功裏に検証されなかったと判定する段階とを含む、
方法。
【請求項４】
前記第二の等式はさらに項
【数１３３】
2014157354.tif 000135
を含み、ここで、HG(τ)はハッシュ関数を表わし、τは署名されたベクトルが存する部分空間の識別子を表わす、請求項３記載の方法。
【請求項５】
ベクトル
【数１３４】
2014157354.tif 000136
に対する線形準同型署名σを生成する装置であって、＾付きのGは第一の群を表わし、当該装置はプロセッサを有し、該プロセッサは：
・署名鍵sk＝{χi,γi,δi}i=1nを使って、
【数１３５】
2014157354.tif 000137
を計算することによって、署名要素(z,r,u)を計算する段階と；
・前記署名要素(z,r,u)を含む署名σを出力する段階とを実行するよう構成されている、
装置。
【請求項６】
前記署名鍵はさらに、要素
【数１３６】
2014157354.tif 000138
を含み、前記プロセッサはさらに：
・ランダムな要素
【数１３７】
2014157354.tif 000139
を選ぶ段階と；
・さらなる署名要素v＝hρを計算する段階とを実行するよう構成されており、ここで、hは第二の群の要素であり；
zの前記計算はさらに、grθによる乗算を含み、rの前記計算はさらにgz-θによる乗算を含み、uの前記計算はさらに
【数１３８】
2014157354.tif 000140
による乗算を含み、ここで、αrは整数であり、h、grおよびgzは前記第二の群の要素であり；
前記署名はさらに、前記署名要素vを含み；
前記第一の群および前記第二の群は同じである、
請求項５記載の装置。
【請求項７】
ベクトル
【数１３９】
2014157354.tif 000141
に対する署名要素(z,r,u)を含む線形準同型署名σを検証する装置であって、＾付きのGは第一の群を表わし、当該装置はプロセッサを有し、該プロセッサは：
・
【数１４０】
2014157354.tif 000142
であることおよび(z,r,u)が第一の等式
【数１４１】
2014157354.tif 000143
および第二の等式
【数１４２】
2014157354.tif 000144
を満たすことを検証するよう構成されており、ここで、e(・,・)は対称かつ可換なペアリングを表わし、h、hz、hi、gr、giおよびgzは第二の群の要素であり；
前記プロセッサはさらに、前記検証が成功の場合に前記署名が成功裏に検証されたと判定し、それ以外の場合に前記署名が成功裏に検証されなかったと判定するよう構成されている、
装置。
【請求項８】
前記第二の等式はさらに項
【数１４３】
2014157354.tif 000145
を含み、ここで、HG(τ)はハッシュ関数を表わし、τは署名されたベクトルが存する部分空間の識別子を表わす、請求項７記載の装置。
【請求項９】
ベクトル
【数１４４】
2014157354.tif 000146
に対する線形準同型署名σを生成する装置であって、＾付きのGは第一の群を表わし、当該装置はプロセッサを有し、該プロセッサは：
署名鍵
【数１４５】
2014157354.tif 000147
を使って、
【数１４６】
2014157354.tif 000148
を計算することによって、署名要素(z,r,u,v)を計算するよう構成されており、
ここで、hzは第二の群の元であり、αrは整数であり、HG(τ)はハッシュ関数を表わし、τは署名されたベクトルが存する部分空間の識別子を表わし、
前記プロセッサはさらに：
z、rおよびuへのコミットメントをそれぞれ生成し；
z、rおよびuへの前記コミットメントを使って、z、rおよびuが所定の検証アルゴリズムを満たすことの証明を生成し；
署名要素vと、z、rおよびuへの前記コミットメントと、前記証明とを含む署名σを出力するよう構成されている、
装置。
【請求項１０】
ベクトル
【数１４７】
2014157354.tif 000149
に対する線形準同型署名σを検証する装置であって、＾付きのGは第一の群を表わし、前記線形準同型署名σは第一の署名要素v、それぞれさらなる署名要素z、rおよびuへのコミットメント
【数１４８】
2014157354.tif 000150
およびz、rおよびuが所定の検証アルゴリズムを満たすことの証明
【数１４９】
2014157354.tif 000151
を含み、前記コミットメントはベクトル
【数１５０】
2014157354.tif 000152
を使って生成されたものであり、当該装置はプロセッサを有し、該プロセッサは、
【数１５１】
2014157354.tif 000153
であることおよび検証
【数１５２】
2014157354.tif 000154
を検証するよう構成されており、
ここで、E(・,・)は座標ごとのペアリングを表わし、h、hz、hi、gr、giおよびgzは第二の群の要素であり；
前記プロセッサはさらに：
前記検証が成功の場合に前記署名が成功裏に検証されたと判定し、それ以外の場合に前記署名が成功裏に検証されなかったと判定するよう構成されている、
装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概括的には暗号に、詳細には線形準同型な、構造を保存する署名に関する。
【背景技術】
【０００２】
本節は、下記で記述および／または特許請求される本発明の様々な側面に関係しうる技術のさまざまな側面を読者に紹介することを意図したものである。この議論は読者に、本発明のさまざまな側面についてのよりよい理解を容易にするための背景情報を与える助けとなるものと思われる。よって、これらの陳述は従来技術の自認としてではなくそのような観点で読まれるべきであることは理解しておくべきである。
【０００３】
線形準同型署名は暗号の分野でよく知られている。定義は非特許文献１に与えられている。
【０００４】
線形準同型署名の他の例は特許文献１、非特許文献１〜８において得られる。
【０００５】
標準的な想定のもとで標準的なモデルにおいて安全であると証明されている諸方式のうち、最も効率のよい方式は非特許文献９のもののようである。
【０００６】
その構築は加法群
【数１】
2014157354.tif 000003
上で準同型である。すなわち、基礎になる巡回群はG＝Zpであり〔本稿では、誤解のない限りこのような簡略書体を使うことがある〕、署名されるメッセージはファイル識別子τ∈{0,1}LおよびZpnのベクトルからなる。この方式は、素数位数pの群
【数２】
2014157354.tif 000004
の間で定義される双線形写像
【数３】
2014157354.tif 000005
を利用する。
【０００７】
〔鍵生成〕Keygen(λ,n)：セキュリティ・パラメータλ∈Nおよび署名されるベクトルの次元を表わす整数n∈poly(λ)を与えられて、素数位数p＞2λの双線形群
【数４】
2014157354.tif 000006
を選ぶ。何らかのL∈poly(λ)について、
【数５】
2014157354.tif 000007
を選ぶ。これらの要素(u0,u1,…,uL)∈GL+1は、任意のLビット・ストリングm＝m[1]…m[L]∈{0,1}Lがハッシュ値
【数６】
2014157354.tif 000008
をもつような数論的ハッシュ関数HG：{0,1}L→Gを実装するために使われる。i＝1からnについて
【数７】
2014157354.tif 000009
を選ぶ。最後に、識別子空間
【数８】
2014157354.tif 000010
を定義する。秘密鍵はsk:＝αであり、公開鍵は
【数９】
2014157354.tif 000011
からなる。
【０００８】
〔署名〕
【数１０】
2014157354.tif 000012
ベクトル→v＝(v1,…,vn)∈Zpn、ファイル識別子τ:＝{0,1}Lおよび秘密鍵sk＝α∈Zpを与えられて、
【数１１】
2014157354.tif 000013
を選ぶ。次いで、署名
【数１２】
2014157354.tif 000014
を、
【数１３】
2014157354.tif 000015
として計算する。
【０００９】
〔署名導出〕
【数１４】
2014157354.tif 000016
pk、ファイル識別子τおよびl個のタプル(βi,σ(i))を与えられて、i＝1からl〔エル〕について、各σ(i)をσ(i)＝(σi,1,σi,2,si)とパースする。
【００１０】
【数１５】
2014157354.tif 000017
を選ぶ。次いで、(σ1,σ2,s)を計算し、出力する。ここで、
【数１６】
2014157354.tif 000018
〔検証〕
【数１７】
2014157354.tif 000019
pk、署名σ＝(σ1,σ2,s)およびメッセージ(τ,→y)、（ここで、τ∈{0,1}Lであり→y＝(y1,…,yn)∈(Zp)n）を与えられて、
【数１８】
2014157354.tif 000020
である場合には
【数１９】
2014157354.tif 000021
を返す。そうでない場合には、
【数２０】
2014157354.tif 000022
のときかつそのときのみ1を返す。
【００１１】
この構築において、すべて0のベクトル→0〔本稿では便宜上、ベクトルの上に付ける矢印をこのように書くことがある〕に対する署名は許されないことが理解されるであろう。これは制約にはならない。というのも、線形準同型署名のあらゆる応用において、適切な長さの単位ベクトル(0,…,1,…,0)が署名されるベクトルにアペンドされるからである。
【００１２】
Attrapadungらの下記論文では、上記の方式は、ディフィー・ヘルマン仮定の変形のもとで偽造不能であると証明された。この仮定は、ランダムに選んだa,b∈Zpについて
【数２１】
2014157354.tif 000023
が与えられ、
【数２２】
2014157354.tif 000024
が位数pの巡回双線形群である場合、gabを計算できる確率的多項式時間（PPT:  Probabilistic  Polynomial  Time）アルゴリズムはないことを述べるものである。上記のバージョンでは、この方式は完全にコンテキスト隠蔽型ではない（すなわち、導出される署名は統計的にもとの署名と独立ではない）。Attrapadungらは、署名長を増すという代償を払って完全にコンテキスト隠蔽型にするよう上記の方式をどのように修正するかを示した（非特許文献１０）。
【００１３】
従来技術の線形準同型署名は、各ベクトルの座標が(Zp,＋)のような群に属するベクトル空間についてのみ存在する。その場合は離散対数を計算するのがたやすい。よって、座標が、有限位数pの離散対数困難な群Gに存するベクトル
【数２３】
2014157354.tif 000025
を扱うことのできる方式をもつことが望まれていることが理解されるであろう。一つの主要な困難は、そのような群では、通例、複数のベクトル
【数２４】
2014157354.tif 000026
が線形従属であるかどうかを判断するのが難しいということである。一般に、n＞2については、それを行なう唯一の既知の方法は、Zp内のすべての座標の離散対数を計算することである。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】米国特許第7743253号明細書、2010年6月22日発行。D.-X.Charles,  K.Jain,  K.Lauter。ネットワーク符号化のためのデジタル署名。
【非特許文献】
【００１５】
【非特許文献１】D.Boneh,  D.Freeman,  J.Katz,  B.Waters、"Signaling  a  Linear  Subspace:  Signature  Schemes  for  Network  Coding",  PKC'09,  Lecture  Notes  in  Computer  Science  5443,  pp.68-87,  2009
【非特許文献２】R.Gennaro,  J.Katz,  H.Krawczyk,  T.Rabin,  "Secure  Network  Coding  over  the  Integers",  PKC'10,  Lecture  Notes  in  Computer  Science,  vol.6056,  pp.142-160,  2010
【非特許文献３】N.Attrapadung,  B.Libert,  "Homomorphic  Network  Coding  Signatures  in  the  Standard  Model",  PKC'11,  Lecture  Notes  in  Computer  Science,  vol.6571,  pp.17-34,  2011
【非特許文献４】D.Boneh,  D.Freeman,  "Linearly  Homomorphic  Signatures  over  Binary  Fields  and  New  Tools  for  Lattice-Based  Signatures",  PKC'11,  Lecture  Notes  in  Computer  Science,  vol.6571,  pp.1-16,  2011
【非特許文献５】D.Boneh,  D.Freeman,  "Homomorphic  Signatures  for  Polynomial  Functions",  Eurocrypt'11,  Lecture  Notes  in  Computer  Science,  vol.6632,  pp.149-168,  2011
【非特許文献６】D.Freeman,  "Improved  security  for  linearly  homomorphic  signatures:  A  generic  framework",  PKC'12,  Lecture  Notes  in  Computer  Science,  vol.7293,  pp.697-714,  2012
【非特許文献７】D.Catalano,  D.Fiore,  B.Warinschi,  "Adaptive  Pseudo-free  Groups  and  Applications",  Eurocrypt'11,  Lecture  Notes  in  Computer  Science,  vol.6632,  pp.207-223,  2011
【非特許文献８】D.Catalano,  D.Fiore,  B.Warinschi,  "Efficient  Network  Coding  Signatures  in  the  Standard  Model",  PKC'12,  Lecture  Notes  in  Computer  Science,  vol.7293,  pp.680-696,  2012
【非特許文献９】N.Attrapadung,  B.Libert,  T.Peters、"Computing  on  Authenticated  Data:  New  Privacy  Definitions  and  Constructions"、Asiacrypt'12,  Lecture  Notes  in  Computer  Science  vol.7658,  pp.367-385,  2012
【非特許文献１０】N.Attrapadung,  B.Libert,  T.Peters、"Efficient  Completely  Context-Hiding  Quotable  Signatures  and  Linearly  Homomorphic  Signatures",  PKC'13,  LNCS  7778,  pp.386-404,  2013
【非特許文献１１】M.Abe,  K.Haralambiev,  M.Ohkubo、"Signing  on  Elements  in  Bilinear  Groups  for  Modular  Protocol  Design"、Cryptology  ePrint  Archive:  Report  2010/133,2010
【非特許文献１２】M.Abe,  G.Fuchsbauer,  J.Groth,  K.Haralambiev,  M.Ohkubo,  "Structure-Preserving  Signatures  and  Commitments  to  Group  Elements",  Crypto'10,  LEcture  Notes  in  Computer  Science,  vol.6223,  pp.209-236,  2010
【非特許文献１３】B.Waters、"Efficient  Identity-Based  Encryption  without  Random  Oracles,  "Eurocrypt'05,  Lecture  Notes  in  Computer  Science,  vol.3498,  pp.114-127,  2005
【非特許文献１４】J.Groth,  A.Sahai,  Efficient  non-interactive  proof  systems  for  bilinear  groups,  Eurocrypt  '08,  Lecture  Notes  in  Computer  Science,  vol.4965,  pp.415-432,  2008
【非特許文献１５】M.Belenkiy,  J.Camenisch,  M.Chase,  M.Kohlweiss,  A.Lysyanskaya,  H.Shacham、"Randomizable  Proofsand  Delegatable  Anonymous  Credentials",  Crypto'09,  Lecture  Notes  in  Computer  Science,  vol.5677,  pp.108-125,  2009
【発明の概要】
【発明が解決しようとする課題】
【００１６】
よって、メッセージが特殊な代数構造をもつ要素であることができる線形準同型署名方式、すなわち「構造を保存する」署名方式をもつことが望まれていることが理解されるであろう。本発明はそのような方式を提供する。
【課題を解決するための手段】
【００１７】
第一の側面では、本発明は、ベクトル
【数２５】
2014157354.tif 000027
に対する線形準同型署名σを生成する方法に向けられる。ここで、＾付きのGは第一の群を表わす。装置のプロセッサが、署名鍵sk＝{χi,γi,δi}i=1nを使って、
【数２６】
2014157354.tif 000028
を計算することによって、署名要素(z,r,u)を計算し、前記署名要素(z,r,u)を含む署名σを出力する。
【００１８】
ある好ましい実施形態では、前記署名鍵はさらに、要素
【数２７】
2014157354.tif 000029
を含み、前記プロセッサはさらにランダムな要素
【数２８】
2014157354.tif 000030
を選び；さらなる署名要素v＝hρを計算し、ここで、hは第二の群の要素であり；zの前記計算はさらに、grθによる乗算を含み、rの前記計算はさらにgz-θによる乗算を含み、uの前記計算はさらに
【数２９】
2014157354.tif 000031
による乗算を含み、ここで、αrは整数であり、h、grおよびgzは前記第二の群の要素であり；前記署名はさらに、前記署名要素vを含み；前記第一の群および前記第二の群は同じである。
【００１９】
第二の側面では、本発明は、ベクトル
【数３０】
2014157354.tif 000032
に対する署名要素(z,r,u)を含む線形準同型署名σを検証する方法に向けられる。ここで、＾付きのGは第一の群を表わす。装置のプロセッサが、
【数３１】
2014157354.tif 000033
であることおよび(z,r,u)が第一の等式
【数３２】
2014157354.tif 000034
および第二の等式
【数３３】
2014157354.tif 000035
を満たすことを検証し、ここで、e(・,・)は対称かつ可換なペアリングを表わし、h、hz、hi、gr、giおよびgzは第二の群の要素であり；前記プロセッサはさらに、前記検証が成功の場合に前記署名が成功裏に検証されたと判定し、それ以外の場合に前記署名が成功裏に検証されなかったと判定する。
【００２０】
第一の実施形態では、前記第二の等式はさらに項
【数３４】
2014157354.tif 000036
を含む。ここで、HG(τ)はハッシュ関数を表わし、τは署名されたベクトルが存する部分空間の識別子を表わす。
【００２１】
第三の側面では、本発明は、ベクトル
【数３５】
2014157354.tif 000037
に対する線形準同型署名σを生成する装置に向けられる。ここで、＾付きのGは第一の群を表わす。当該装置はプロセッサを有する。該プロセッサは、署名鍵sk＝{χi,γi,δi}i=1nを使って、
【数３６】
2014157354.tif 000038
を計算することによって、署名要素(z,r,u)を計算し、前記署名要素(z,r,u)を含む署名σを出力するよう構成されている。
【００２２】
第一の実施形態では、前記署名鍵はさらに、要素
【数３７】
2014157354.tif 000039
を含み、前記プロセッサはさらに：ランダムな要素
【数３８】
2014157354.tif 000040
を選び；さらなる署名要素v＝hρを計算するよう構成されており、ここで、hは第二の群の要素であり；zの前記計算はさらに、grθによる乗算を含み、rの前記計算はさらにgz-θによる乗算を含み、uの前記計算はさらに
【数３９】
2014157354.tif 000041
による乗算を含み、ここで、αrは整数であり、h、grおよびgzは前記第二の群の要素であり；前記署名はさらに、前記署名要素vを含み；前記第一の群および前記第二の群は同じである。
【００２３】
第四の側面では、本発明は、ベクトル
【数４０】
2014157354.tif 000042
に対する署名要素(z,r,u)を含む線形準同型署名σを検証する装置に向けられる。ここで、＾付きのGは第一の群を表わす。当該装置はプロセッサを有する。該プロセッサは、
【数４１】
2014157354.tif 000043
であることおよび(z,r,u)が第一の等式
【数４２】
2014157354.tif 000044
および第二の等式
【数４３】
2014157354.tif 000045
を満たすことを検証するよう構成されており、ここで、e(・,・)は対称かつ可換なペアリングを表わし、h、hz、hi、gr、giおよびgzは第二の群の要素であり；前記プロセッサはさらに、前記検証が成功の場合に前記署名が成功裏に検証されたと判定し、それ以外の場合に前記署名が成功裏に検証されなかったと判定するよう構成されている。
【００２４】
第一の実施形態では、前記第二の等式はさらに項
【数４４】
2014157354.tif 000046
を含む。ここで、HG(τ)はハッシュ関数を表わし、τは署名されたベクトルが存する部分空間の識別子を表わす。
【００２５】
第五の側面では、本発明は、ベクトル
【数４５】
2014157354.tif 000047
に対する線形準同型署名σを生成する装置に向けられる。ここで、＾付きのGは第一の群を表わす。当該装置はプロセッサを有する。該プロセッサは、署名鍵
【数４６】
2014157354.tif 000048
を使って、
【数４７】
2014157354.tif 000049
を計算することによって、署名要素(z,r,u,v)を計算するよう構成されており、ここで、hzは第二の群の元であり、αrは整数であり、HG(τ)はハッシュ関数を表わし、τは署名されたベクトルが存する部分空間の識別子を表わし、前記プロセッサはさらに、z、rおよびuへのコミットメントをそれぞれ生成し；z、rおよびuへの前記コミットメントを使って、z、rおよびuが所定の検証アルゴリズムを満たすことの証明を生成し；署名要素vと、z、rおよびuへの前記コミットメントと、前記証明とを含む署名σを出力するよう構成されている。
【００２６】
第六の側面では、本発明は、ベクトル
【数４８】
2014157354.tif 000050
に対する線形準同型署名σを検証する装置に向けられる。ここで、＾付きのGは第一の群を表わし、前記線形準同型署名σは第一の署名要素v、それぞれさらなる署名要素z、rおよびuへのコミットメント
【数４９】
2014157354.tif 000051
およびz、rおよびuが所定の検証アルゴリズムを満たすことの証明
【数５０】
2014157354.tif 000052
を含み、前記コミットメントはベクトル
【数５１】
2014157354.tif 000053
を使って生成されたものである。当該装置は、プロセッサを有する。該プロセッサは、
【数５２】
2014157354.tif 000054
であることおよび検証
【数５３】
2014157354.tif 000055
を検証するよう構成されており、ここで、E(・,・)は座標ごとの（coordinate-wise）ペアリングを表わし、h、hz、hi、gr、giおよびgzは第二の群の要素であり；前記プロセッサはさらに、前記検証が成功の場合に前記署名が成功裏に検証されたと判定し、それ以外の場合に前記署名が成功裏に検証されなかったと判定するよう構成されている。
【図面の簡単な説明】
【００２７】
本発明の好ましい特徴についてこれから限定しない例として、付属の図面を参照して述べる。
【図１】本発明のある好ましい実施形態に基づく、構造を保存する線形準同型署名システムを示す図である。
【図２】本発明のある好ましい実施形態に基づく、コンテキスト隠蔽型の、線形準同型な、構造を保存する署名を生成および検証する方法を示す図である。
【発明を実施するための形態】
【００２８】
本発明の構造を保存する線形準同型署名方式は非特許文献１１および非特許文献１２（説明については第一の文書のAppendix  C参照）で提案された構造を保存する署名方式の修正に基づいている。前記方式は準同型ではないし、準同型であることが意図されてもいなかったことは理解されるであろう。前記方式は単に所与の公開鍵に関して一つのメッセージに署名することを許容するものである。
【００２９】
そこで、（
【数５４】
2014157354.tif 000056
のn−1個の線形独立なベクトルによって張られる）ただ一つの線形部分空間が所与の鍵ペア(sk;pk)を使って署名される限り、離散対数困難な群上で、線形準同型な署名方式を得るよう第一の修正がなされる。この第一の方式は、次のように記述できる。以下の記法において、ppは素数位数p＞2λの群
【数５５】
2014157354.tif 000057
からなる一組の公開パラメータ（public  parameter）を表わす。ここで、λ∈Nはセキュリティ・パラメータであり、それらの群の上で、効率的に計算可能な双線形マップ
【数５６】
2014157354.tif 000058
が定義される。
【００３０】
図１は、本発明のある好ましい実施形態に基づく、準同型署名を生成する暗号学的署名装置１００および準同型署名の検証のための暗号学的署名装置２００を示している。装置１００、２００はそれぞれ、通信のために構成された少なくとも一つのインターフェース・ユニット１１０、２１０と、少なくとも一つの処理器（「プロセッサ」）１２０、２２０と、アキュムレータおよび仲介計算結果のようなデータを記憶するよう構成された少なくとも一つのメモリ１３０、２３０とを有する。この図は、CD-ROMまたはDVDのような第一および第二のコンピュータ・プログラム・プロダクト（非一時的な記憶媒体）１４０、２４０が記憶された命令を有しており、該命令はプロセッサ１２０、２２０によって実行されたときにそれぞれ本発明に基づいて署名の生成および検証を行なうことを示している。
【００３１】
ワンタイム方式
Keygen(pp,n)〔鍵生成〕：ppおよび署名されるべき部分空間の次元n∈Nを与えられて、生成子
【数５７】
2014157354.tif 000059
を選ぶ。i＝1ないしnについて、
【数５８】
2014157354.tif 000060
を選ぶ。次いで、それぞれのi∈{1,…,n}について、
【数５９】
2014157354.tif 000061
を計算する。公開鍵は
【数６０】
2014157354.tif 000062
として、秘密鍵は
【数６１】
2014157354.tif 000063
として定義される。
【００３２】
Sign(sk,τ,(M1,…,Mn))〔署名〕：sk＝{χi,γi,δi}i=1nを使って識別子τ＝εに関連付けられたベクトル
【数６２】
2014157354.tif 000064
に署名するために次式を計算する。
【００３３】
【数６３】
2014157354.tif 000065
署名は次のようになる。
【００３４】
【数６４】
2014157354.tif 000066
〔署名導出〕
【数６５】
2014157354.tif 000067
pk、ファイル識別子τおよびl個のタプル(ωi,σ(i))を与えられて、i＝1ないしl〔エル〕について、各署名σ(i)を
【数６６】
2014157354.tif 000068
としてパースする。
【００３５】
【数６７】
2014157354.tif 000069
を計算し、σ＝(z,r,u)を返す。
【００３６】
Verify(sk,σ,τ,(M1,…,Mn))〔検証〕：署名
【数６８】
2014157354.tif 000070
、ベクトル(M1,…,Mn)およびファイル識別子τ＝εが与えられて、
【数６９】
2014157354.tif 000071
であり、かつ(z,r,u)が等式
【数７０】
2014157354.tif 000072
を満たす場合にかつその場合にのみ1を返す。
【００３７】
高々n−1個の線形独立なベクトル
【数７１】
2014157354.tif 000073
についての署名を得る敵は、同時二重ペアリング（SDP:  Simultaneous  Double  Paring）仮定が成り立つ限り、ベクトル
【数７２】
2014157354.tif 000074
に対する署名を偽造することができないことが証明できる。Abe,  Haralambiev  and  Ohkuboによる論文で記述されているSDP仮定は、
【数７３】
2014157354.tif 000075
において、要素のタプル
【数７４】
2014157354.tif 000076
が与えられて、
【数７５】
2014157354.tif 000077
となるような非自明なタプル
【数７６】
2014157354.tif 000078
を見出すものである。
【００３８】
完全に展開した方式
上記のワンタイム方式は、任意の数の線形部分空間に署名することを許容する線形構築に拡張できる。これを行なうために、
【数７７】
2014157354.tif 000079
となる双線形群
【数７８】
2014157354.tif 000080
の構成が必要とされる。換言すれば、双線形マップe:G×G→GTは、対称かつ可換であるべきなので、その引数の両方を同じ群G内にもつ必要がある。
【００３９】
この構築では、各ファイル識別子τは、何らかのL∈poly(λ)について、Lビット・ストリングからなる。各署名のu成分はワンタイム方式の署名の、ファイル識別子τ上でのウォーターズ（Waters）署名
【数７９】
2014157354.tif 000081
との総合と見ることができる（非特許文献１３参照）。本方式では、そのようなウォーターズ署名が、署名ランダム化手段θ∈Zpのためのサポートとして使われる。
【００４０】
Keygen(pp,n)〔鍵生成〕：ppおよび署名されるべき部分空間の次元n∈Nを与えられて、下記のステップを実行する：
１．
【数８０】
2014157354.tif 000082
を選ぶ。
【００４１】
【数８１】
2014157354.tif 000083
を定義する。
２．i＝1ないしnについて、
【数８２】
2014157354.tif 000084
を選び、
【数８３】
2014157354.tif 000085
を計算する。
３．τ＝τ[1]…τ[L]∈{0,1}Lを
【数８４】
2014157354.tif 000086
にマッピングするハッシュ関数HG：{0,1}L→Gを定義するランダムなベクトル
【数８５】
2014157354.tif 000087
を選ぶ。
【００４２】
公開鍵は
【数８６】
2014157354.tif 000088
からなり、秘密鍵は
【数８７】
2014157354.tif 000089
である。
【００４３】
Sign(sk,τ,(M1,…,Mn))〔署名〕：
【数８８】
2014157354.tif 000090
を使ってファイル識別子τに関してベクトル(M1,…,Mn)∈Gnに署名するために、
【数８９】
2014157354.tif 000091
を選び、
【数９０】
2014157354.tif 000092
を計算する。署名はσ＝(z,r,u,v)∈G4となる。
【００４４】
【数９１】
2014157354.tif 000093
〔署名導出〕
pk、ファイル識別子τおよびl個のタプル(ωi,σ(i))を与えられて、i＝1からl〔エル〕について、各署名σ(i)をσ(i)＝(zi,ri,ui,vi)∈G4とパースする。次いで、
【数９２】
2014157354.tif 000094
を選び、
【数９３】
2014157354.tif 000095
を計算し、σ＝(z,r,u,v)を返す。
【００４５】
Verify(pk,σ,τ,(M1,……,Mn))〔検証〕：署名σ＝(z,r,u,v)∈G4、ファイル識別子τおよびベクトル(M1,……,Mn)を与えられて、
【数９４】
2014157354.tif 000096
ときかつそのときのみ、1を返す。
【００４６】
上記のワンタイム方式がこの完全に展開した方式の、各署名においてθ＝ρ＝0とした特殊な場合であることは理解されるであろう。
【００４７】
コンテキスト隠蔽型の方式
上記の完全に展開した方式が完全なコンテキスト隠蔽型セキュリティを提供するのでないことは理解されるであろう。署名導出演算が、秘密鍵を知ることなく基礎になっているθを再ランダム化することができないからである。いくつかの応用では、計算量が制限されない観察者の目でも、導出された署名ともとの署名がリンクできないことを保証することが望ましいことがある。
【００４８】
このため、好ましい実施形態は、完全にコンテキスト隠蔽型であることが証明できる方式である。この方式は、上記の完全に展開した方式を修正することによって得られる。本質的には、署名者はまず上記の完全に展開した方式のように署名σ＝(z,r,u,v)を計算する。要素(z,r,u)は公に再ランダム化されることはできないので、署名者は単にそれらの要素をGroth-Sahaiコミットメント内に現われるようにし（非特許文献１４参照）、コミットされた値が検証の式を満たすことの非対話的な証明を加える。Groth-Sahai証明の完璧なランダム化可能性属性（非特許文献１５において示されている）は、導出された署名が新規に生成された署名として配布されることを保証する。
【００４９】
以下の記述では、やはり、双線形マップe:G×G→GT
が対称的であること、すなわち
【数９５】
2014157354.tif 000097
であることが要求される。以下の記法では、座標ごとのペアリング
【数９６】
2014157354.tif 000098
は、任意の要素h∈Gおよび任意のベクトル→g＝(g1,g2,g3)について、
【数９７】
2014157354.tif 000099
となるよう定義される。
【００５０】
図２は、以下の方式のSign〔署名〕、SignDerive〔署名導出〕およびVerify〔検証〕を示している。
【００５１】
Keygen(pp,n)〔鍵生成〕：ppおよび署名されるべき部分空間の次元n∈Nを与えられて、下記のステップを実行する：
１．
【数９８】
2014157354.tif 000100
を選ぶ。
【００５２】
【数９９】
2014157354.tif 000101
を定義する。
２．それぞれのi＝{1,…,n}について、
【数１００】
2014157354.tif 000102
を選び、
【数１０１】
2014157354.tif 000103
を計算する。
３．
【数１０２】
2014157354.tif 000104
を選び、ベクトル
【数１０３】
2014157354.tif 000105
を定義することによって、Groth-Sahai共通参照ストリングを選ぶ。
【００５３】
公開鍵は
【数１０４】
2014157354.tif 000106
からなり、秘密鍵は
【数１０５】
2014157354.tif 000107
である。
【００５４】
Sign(sk,τ,(M1,…,Mn))〔署名〕：
【数１０６】
2014157354.tif 000108
を使ってファイル識別子τに関してベクトル(M1,…,Mn)∈Gnに署名するために、下記を実行する。
１．
【数１０７】
2014157354.tif 000109
を選び（S1）、
【数１０８】
2014157354.tif 000110
を計算する。
２．諸ベクトル
【数１０９】
2014157354.tif 000111
を使って、それぞれz,r,uへのコミットメント
【数１１０】
2014157354.tif 000112
を計算する（S2）。これらのコミットメントのランダム性を使って、(z,r,u)が上記完全に展開した方式の検証の式、すなわち
【数１１１】
2014157354.tif 000113
を満たすという証明
【数１１２】
2014157354.tif 000114
を生成する。これらの証明は、
【数１１３】
2014157354.tif 000115
として得られ、検証の式
【数１１４】
2014157354.tif 000116
を満たす。署名は
【数１１５】
2014157354.tif 000117
となる。
【００５５】
〔署名導出〕
【数１１６】
2014157354.tif 000118
pk、ファイル識別子τおよびl個のタプル(ωi,σ(i))を与えられて、i＝1からl〔エル〕について、各署名σ(i)を
【数１１７】
2014157354.tif 000119
の形のタプルとしてパースする。
【００５６】
【数１１８】
2014157354.tif 000120
を選び、
【数１１９】
2014157354.tif 000121
を計算する。
【００５７】
次いで、上記コミットメントおよび証明を再ランダム化し（S3）、
【数１２０】
2014157354.tif 000122
を返す。
【００５８】
Verify(pk,σ,τ,(M1,……,Mn))〔検証〕：ペア(τ,(M1,……,Mn))および標榜される署名σを与えられて、署名を
【数１２１】
2014157354.tif 000123
としてパースする。次いで、
【数１２２】
2014157354.tif 000124
であり、かつSign〔署名〕検証が満たされる（S4）、すなわち
【数１２３】
2014157354.tif 000125
であるときかつそのときのみ、1を返す（S5）。
【００５９】
上記の方式の偽造不可能性は決定線形（Decision  Linear）仮定のもとで証明できる。この仮定は、略式にいうと、次元3の群要素の三つのベクトルが線形従属であるか否かを決定することは現実的には不可能であることをいうものである。さらに、上記の方式は、無条件でコンテキスト隠蔽型である。
【００６０】
本発明の利点は、署名者が、群要素からなるベクトルに、その離散対数を知ることなく署名することを許容できるということである。たとえば、上記の署名方式は、署名者が、必ずしも基礎になる平文を知ることなく、暗号文に署名することを可能にする。
【００６１】
本発明の方式が、暗号化されたデータセットをクラウド・コンピューティング・サービスにおいてアウトソーシングするために使われることができることは理解されるであろう。さらに、線形準同型署名は、匿名の推薦システムにおける正しい総合（aggregation）の証明のはたらきをもすることができる。
【００６２】
本明細書および（適切な場合には）請求項および図面において開示される各特徴は、独立して、あるいは任意の適切な組み合わせにおいて与えられてもよい。ハードウェアで実装されるとして記述される特徴は、ソフトウェアで実装されてもよく、逆にソフトウェアで実装されるとして記述される特徴は、ハードウェアで実装されてもよい。請求項に参照符号があったとしても単に例示するものであって、請求項の範囲に対する限定効果はもたない。
【図１】
2014157354.tif 000155
【図２】
2014157354.tif 000156
【外国語明細書】
2014157354000001.pdf