(57)【要約】【課題】線形準同型署名からコミットメントを生成および検証する暗号学的装置および方法を提供する。【解決手段】装置（１００）のプロセッサ（１２０）が、ベクトルm、準同型署名方式の公開検証鍵およびタグを受領し；署名空間内の署名σを選び；準同型署名方式の検証アルゴリズムを走らせることによってコミットメントcを生成し；コミットメントcを検証アルゴリズムから帰結する中間的な値として出力することによって、暗号学的なコミットメントを生成する。【選択図】図２
2014158265.tif 000002
【特許請求の範囲】
【請求項１】
頑健な暗号学的コミットメントを生成する方法であって、当該方法は、装置のプロセッサにおける下記の段階、すなわち：
・処理手段によって、ベクトル→mと、署名が存する空間に関連付けられた準同型署名方式の公開検証鍵と、タグとを受領する段階と；
・前記処理手段によって、署名が存する前記空間内のある要素σを選ぶ段階と；
・前記処理手段によって、前記ベクトル→m、前記公開検証鍵、前記タグおよび前記要素σを使ってコミットメントcを生成する段階と；
・出力手段によって、前記コミットメントcを出力する段階とを含んでおり、
前記コミットメントcは、前記ベクトル→m、前記公開検証鍵、前記タグおよび前記要素σに対する前記準同型署名方式の検証アルゴリズムにおいて使用される線形関数Fを評価することによって生成される、
方法。
【請求項２】
前記コミットメントcのサイズは前記ベクトル→mのサイズとは独立である、請求項１記載の方法。
【請求項３】
前記ベクトル→mは、双線形マップG×G→GTが効率的に計算可能な群Gの要素を含む、請求項１記載の方法。
【請求項４】
前記ベクトル→mの次元は2以上である、請求項１記載の方法。
【請求項５】
前記コミットメントcは零知識証明を使って開封の知識を証明することを許容する、請求項１記載の方法。
【請求項６】
前記コミットメントcは、前記検証アルゴリズムから帰結する中間的な値として生成される、請求項１記載の方法。
【請求項７】
頑健な暗号学的コミットメントを生成する装置であって、当該装置は：
・ベクトル→m、署名が存する空間に関連付けられた準同型署名方式の公開検証鍵およびタグを受領し；
・コミットメントcを出力するよう構成された
インターフェース手段と；
・署名が存する前記空間内のある要素σを選び；
・前記ベクトル→m、前記公開検証鍵、前記タグおよび前記要素σを使って前記コミットメントcを生成するよう構成された
処理手段とを有しており、
前記処理手段は、前記コミットメントcを、前記ベクトル→m、前記公開検証鍵、前記タグおよび前記要素σに対する前記準同型署名方式の検証アルゴリズムにおいて使用される線形関数Fを評価することによって生成するよう構成されている、
装置。
【請求項８】
前記コミットメントcのサイズは前記ベクトル→mのサイズとは独立である、請求項７記載の装置。
【請求項９】
前記ベクトル→mは、双線形マップG×G→GTが効率的に計算可能な群Gの要素を含む、請求項７記載の装置。
【請求項１０】
前記ベクトル→mの次元が2以上である、請求項７記載の装置。
【請求項１１】
前記コミットメントcは零知識証明を使って開封の知識を証明することを許容する、請求項７記載の装置。
【請求項１２】
前記コミットメントcは、前記検証アルゴリズムから帰結する中間的な値として生成される、請求項７記載の装置。
【請求項１３】
命令を記憶している非一時的なコンピュータ・プログラム・プロダクトであって、前記命令は、プロセッサによって実行されたときに、請求項１ないし６のうちいずれか一項記載の方法を実行する、コンピュータ・プログラム・プロダクト。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概括的には暗号に、詳細には線形準同型署名からの頑健な（non-malleable）コミットメントに関する。
【背景技術】
【０００２】
本節は、下記で記述および／または特許請求される本発明の様々な側面に関係しうる技術のさまざまな側面を読者に紹介することを意図したものである。この議論は読者に、本発明のさまざまな側面についてのよりよい理解を容易にするための背景情報を与える助けとなるものと思われる。よって、これらの陳述は従来技術の自認としてではなくそのような観点で読まれるべきであることは理解しておくべきである。
【０００３】
いわゆるコミットメント方式は、封印された封筒のデジタル等価物であるということができる。封筒の中にあるものが何であれ、それは封筒が開かれるまで秘密のままである。同時に、ひとたび封筒が閉じられたら、送り手は内容について気を変えることはできない。このように、コミットメント方式の目標は、送り手が、将来の何らかの時点で明かされるまで変更できないメッセージを定義することを強制するものである。
【０００４】
コミットメント方式は非対話的であってもよい。つまり、いわゆるコミットメント・フェーズおよび開封フェーズの両方が送り手から受け手への単一のメッセージからなる。別の言い方をすると、受け手は、メッセージを受け取る以外には、送り手といかなる仕方でも対話する必要がない。
【０００５】
落とし戸コミットメント（trapdoor  commitment）は、完全に隠蔽する（すなわち、制限のない敵に対してでも隠蔽属性が保たれる）コミットメントであり、tkが束縛属性（binding  property）を破ってコミットメントを任意の値に開くことを可能にする。しかしながら、これは落とし戸なしには実現不可能なままのはずである。本発明の記述の際に見られるように、落とし戸コミットメントは、フェイクコム（FakeCom）およびフェイクオープン（FakeOpen）と呼ばれる二つの追加的なアルゴリズムを使う。
【０００６】
シミュレーション健全な落とし戸コミットメント（SSTC:  simulation-sound  trapdoor  commitment）では、各コミットメントはタグでラベル付けされる。定義は、非特許文献１において与えられている。この定義は、たとえ敵がいくつかのタグtag1、……、tagqについての、可能性としては相異なるメッセージに対するコミットメントの多義使用（equivocation）を見ることが許容されたとしても、その敵は新たなタグ
【数１】
2014158265.tif 000003
について束縛属性を破ることはできないということを要求する。
【０００７】
コミットメント方式のもう一つの望ましい属性は、敵が、正直なプレーヤーのメッセージに相関しているメッセージにコミットすることができないというものである。開封に関して独立という概念は、敵がそのコミットメントを開いて示すことのできるメッセージは、正直な送り手のコミットメントが開かれる仕方とは独立であるべきであるというものである。非特許文献２、非特許文献３参照。
【０００８】
コミットメントのために、素数位数p＞2λの群
【数２】
2014158265.tif 000004
を考える。ここで、λはセキュリティ・パラメータであり、この群の上で離散対数問題は困難であると考えられる。さらに、効率的に計算可能な双線形マップ（ペアリングとしても知られる）が想定される：
【数３】
2014158265.tif 000005
つまり、任意のg,h∈Gおよび任意のa,b∈Zについて、e(ga,hb)＝e(g,h)abとなる。さらに、
【数４】
2014158265.tif 000006
これらの群において、次の困難さの想定に頼ることができる。
・計算ディフィー・ヘルマン問題（Computational  Diffie-Hellman  Problem）（CDH）；
・決定線形問題（Decision  Linear  Problem）（DLIN）――非特許文献４参照。
・同時二重ペアリング問題（Simultaneous  Double  Pairing  problem）（SDP）。この想定は、群GにおけるDLIN想定によって含意される。――非特許文献５参照。
【０００９】
従来技術は、敵が自分自身のコミットメントを出力する前に一つの正直に生成されたコミットメントしか与えられないという意味で再使用可能でない非対話的な頑健なコミットメントのいくつかの構築を含んでいる。たとえば非特許文献６、特許文献１、非特許文献７参照。
【００１０】
再使用可能な頑健なコミットメントの概念はダムゴルドおよびグロート（非特許文献８）によって提案された。再使用可能な頑健なコミットメントは、シミュレーション健全な落とし戸コミットメント（非特許文献９、非特許文献１参照）およびマルチ落とし戸コミットメント（非特許文献１０参照）から構築できる。
【００１１】
マッケンジーおよびヤンはその論文において、効率的なΣプロトコルを認める署名方式からのSSTCの構築を与えた。当技術分野において知られているように、Σプロトコルは、証明者と検証者の間の三手の対話的プロトコルである。実際、藤崎（非特許文献１１）によって記されるように、非対話的なシミュレーション健全なまたはマルチ落とし戸（非特許文献１０参照）コミットメントのすべての既知の構築は、効率的なΣプロトコルが署名の知識を証明することを許容する署名方式の上に立脚している。
【００１２】
その考え方は、メッセージmへのコミットを、mをタグ上での署名σ＝Sig(sk,tag)の知識を証明するためのΣプロトコルのチャレンジとして使うことによって行なうというものである。コミットメントは、メッセージtag上の有効な署名σの知識の証明をシミュレートすることによって得られるΣプロトコル転記（transcript）(a,m,z)の第一のメッセージaによって与えられる。このコミットメントはその後、zを明かすことによって開かれる。Σプロトコルの特別な健全性によって、送り手が実際にtag上の有効な署名を知っているのでない限り、一つのメッセージmへの所与のコミットメントaを開くことができるだけである。
【００１３】
単純だが、上記の構築は、コミットされたベクトルの個々の座標についての陳述を送り手が効率的に証明できるままにしたい場合、ベクトルへのコミットに容易には拡張されない。さらに、Σプロトコルに基づく方法は、群要素のベクトルにコミットすることを可能にしない：この目的に向けては、チャレンジが群要素のベクトルであるΣプロトコルを必要とする。非特許文献１１において、藤崎は暗号化方式に基づくSSTCシステムの代替的な構築を与えた。しかしながら、この構築は、コミットメント・フェーズの間に送り手と受け手との間に数ラウンドの対話が必要とされるので、対話的である。
【００１４】
群要素への非対話的なコミットメントはたとえば非特許文献１２、１３、１４、１５において記述された。
【００１５】
しかしながら、これらの方式はみな準同型であり、よって改変できる〔頑健ではない〕。今日まで、メッセージおよび開封が群要素のみからなる、唯一知られている非対話的な頑健なコミットメント方式はフィシュリン（非特許文献１６）によって記述されたものである。しかしながら、これらの構築は、ユニバーサルな構成可能性（universal  composability）を達成するため、長さを短縮するものであることはできない（すなわち、コミットメントはメッセージより短いことはできない）（非特許文献１７、１８参照）。そして、ユニバーサルに構成可能なコミットメントは抽出可能（extractable）でなければならない（すなわち、落とし戸情報がコミットメントに含まれるメッセージを回復することを可能にするべきである）ことが知られている。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】米国特許第6301664号明細書（G.DiCrescenzo,  Y.Ishai.,  R.Ostrovsky、"Method  and  System  for  Non-Malleable  and  Non-Interactive  Cryptographic  Commitment  in  a  Network"、2001）
【非特許文献】
【００１７】
【非特許文献１】P.MacKenzie,  K.Yang、"On  Simulation-Sound  Trapdoor  Commitments",  Eurocrypt  '04,  Lecture  Notes  in  Computer  Science,  vol.3027、pp.382-400、2004
【非特許文献２】G.DiCrescenzo,  Y.Ishai,  R.Ostrovsky、"Non-Interactive  and  Non-Malleable  Commitment"、STOC  '98,  pp.141-150,  1998
【非特許文献３】R.Gennaro  and  S.Micali、"Independent  Zero-Knowledge  Sets"、ICALP  '06,  Lecture  Notes  in  Computer  Science,  vol.4052,  pp.34-45,  2006
【非特許文献４】D.Boneh,  X.Boyen,  H.Shacham、"Short  Group  Signatures"、Crypto  '04,  Lecture  Notes  in  Computer  Science,  vol.3152,  pp.41-55,  Springer,  2004
【非特許文献５】M.Abe,  K.Haralambiev,  M.Ohkubo、"Signing  on  Elements  in  Bilinear  Groups  for  Modular  Protocol  Design"、Cryptology  ePrint  Archive:  Report  2010/133,2010
【非特許文献６】G.DiCrescenzo,  Y.Ishai,  R.Ostrovsky、"Non-Interactive  and  Non-Malleable  Commitment"、STOC  '98、pp.141-150、1998
【非特許文献７】G.DiCrescenzo,  J.Katz,  R.Ostrovsky,  A.Smith、"Efficient  and  Non-interactive  Non-malleable  Commitment"、Eurocrypt  '01,  Lecture  Notes  in  Computer  Science,  vol.2045,  pp.40-59,  2001
【非特許文献８】I.Damgord,  J.Groth、"Non-interactive  and  reusable  non-malleable  commitment  schemes"、STOC  '03,  pp.426-437,  2003
【非特許文献９】J.Garay,  P.MacKenzie,  K.Yang、"Strengthening  Zero-Knowledge  Protocols  Using  Signatures"、Eurocrypt  '03,  Lecture  Notes  in  Computer  Science,  vol.2656,  pp.177-194,  2003
【非特許文献１０】R.GEnnaro、"Multi-Trapdoor  Commitments  and  Their  Applications  to  Proofs  of  KNowledge  Secure  Under  Concurrent  Man-in-the-Middle  Attacks"、Crypto  '04,  Lecture  Notes  in  Computer  Science,  vol.3152,  pp.220-236,  2004
【非特許文献１１】E.Fujisaki、"New  Constructions  of  Efficient  Simulation-Sound  Commitments  Using  Encryption  and  Their  Applications"、CT-RSA  '12,  Lecture  Notes  in  Computer  Science,  vol.7178,  pp.136-155,  2012
【非特許文献１２】J.Groth、"Simulation-Sound  NIZK  Proofs  for  a  Practical  Language  and  Constant  Size  Group  Signatures"、Asiacrypt  '06,  Lecture  Notes  in  Computer  Science,  vol.4284,  pp.444-459,  Springer,  2006
【非特許文献１３】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
【非特許文献１４】J.Cathalo,  B.Libert,  M.Yung,  Group  Encryption:  Non-Interactive  Realization  in  the  Standard  Model,  Asiacrypt  '09,  Lecture  Notes  in  Computer  Science,  vol.5912,  pp.179-196,  2009
【非特許文献１５】G.Groth,  Homomorphic  trapdoor  commitments  to  group  elements,  Cryptology  ePrint  Archive:  Report  2009/007.  2009
【非特許文献１６】M.Fischlin,  B.Libert,  M.Manulis,  Non-interactive  and  Re-usable  Universally  Composable  String  Commitments  with  Adaptive  Security,  Asiacrypt  '11,  Lecture  Notes  in  Computer  Science,  vol.7073,  pp.468-485,  2011
【非特許文献１７】R.Canetti,  Universally  Composable  Security:  A  New  Paradigm  for  Cryptographic  Protocols,  FOCS  '01,  pp.136-145,  2001
【非特許文献１８】R.Canetti,  M.Fischlin,  Universally  Composable  Commitments,  Crypto  '01,  Lecture  Notes  in  Computer  Science,  vol.2139,  pp.19-40,  2001
【非特許文献１９】M.Abe,  K.Haralambiev,  M.Ohkubo、Group  to  Group  Commitments  Do  Not  Shrink、Eurocrypt  '12,  Lecture  Notes  in  Computer  Science,  vol.  7237,  pp.301-317,  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
【非特許文献２１】Y.Dodis,  V.Shoup,  S.Walfish、"Efficient  Constructions  of  Composable  Commitments  and  Zero-Knowledge  Proofs",  Crypto  '08,  Lecture  Notes  in  Computer  Science,  vol.5157,  pp.21-38,  2008
【非特許文献２２】R.Nishimaki,  E.Fujisaki,  K.Tanaka,  "A  Multi-trapdoor  Commitment  Scheme  from  the  RSA  Assumption",  ACISP  2010,  Lecture  Notes  in  Computer  Science,  vol.6168,  pp.182-199,  2010
【発明の概要】
【発明が解決しようとする課題】
【００１８】
このように、個々のベクトル座標{mi}i=1nについての属性を効率的に証明できることを保持しつつ、ベクトル→m＝(m1,……,mn)に対する非対話的な頑健な落とし戸コミットメントのモジュラーな（modular）構築を提供するコミットメント方式をもつことが望まれていることが理解されるであろう〔→mはベクトルを表わす→付きのm〕。これは、ベクトル→mのハッシュ値にコミットすることからなる自明な解決策を排除する。また、かかる方式は、群要素に、その離散対数を知ることなくコミットすることを可能にすることも望まれる。換言すれば、コミットされるべきメッセージは群要素の諸ベクトル
【数５】
2014158265.tif 000007
からなるべきであり、ここで、G〔本稿では、誤解のない限りこのような簡略書体を使うことがある〕は双線形マップe:G×G→GTが効率的に計算可能な群である。コミットメント方式は、好ましくは、コミットメント・ストリングcomが、一時にいくつの群要素(M1,……,Mn)がコミットされるかに関わりなく、一定のサイズをもつようにも設計されるべきである。最後に、開封も好ましくはG内の要素からなるべきであり、それによりコミットされた群要素がある種の属性を満たすことの効率的な非対話的な証明を（非特許文献１３の技法を使って）生成することが可能になる。本発明は、そのようなコミットメント方式を提供する。
【課題を解決するための手段】
【００１９】
第一の側面では、本発明は、頑健な暗号学的コミットメントを生成する方法に向けられる。装置のプロセッサがベクトルと、署名が存する空間に関連付けられた準同型署名方式の公開検証鍵と、タグとを受領し；署名が存する空間内のある要素を選び、前記ベクトル、前記公開検証鍵、前記タグおよび前記要素を使ってコミットメントを生成し；前記コミットメントを出力する。前記コミットメントは、前記ベクトル→m〔本稿では便宜上、上に→を付けたmをこのように書くことがある〕、前記公開検証鍵、前記タグおよび前記要素σに対する前記準同型署名方式の検証アルゴリズムにおいて使用される線形関数Fを評価することによって生成される。
【００２０】
第一の実施形態では、前記コミットメントのサイズは前記ベクトルのサイズとは独立である。
【００２１】
第二の実施形態では、前記ベクトルは、双線形マップG×G→GTが効率的に計算可能な群Gの要素を含む。
【００２２】
第三の実施形態では、前記ベクトルの次元は2以上である。
【００２３】
第四の実施形態では、前記コミットメントは零知識証明を使って開封の知識を証明することを許容する。
【００２４】
第五の実施形態では、前記コミットメントは、検証アルゴリズムから帰結する中間的な値として生成される。
【００２５】
第二の側面では、本発明は、頑健な暗号学的コミットメントを生成する装置に向けられる。本装置は、ベクトル、署名が存する空間に関連付けられた準同型署名方式の公開検証鍵およびタグを受領し；コミットメントを出力するよう構成された少なくとも一つのインターフェースを有する。本装置はさらに、署名が存する空間内のある要素を選び；前記ベクトル、前記公開検証鍵、前記タグおよび前記要素を使って前記コミットメントを生成するよう構成されたプロセッサを有する。前記プロセッサは、前記コミットメントを、前記ベクトル→m、前記公開検証鍵、前記タグおよび前記要素σに対する前記準同型署名方式の検証アルゴリズムにおいて使用される線形関数Fを評価することによって生成する。
【００２６】
第一の実施形態では、前記コミットメントのサイズは前記ベクトルのサイズとは独立である。
【００２７】
第二の実施形態では、前記ベクトルは、双線形マップG×G→GTが効率的に計算可能な群Gの要素を含む。
【００２８】
第二の実施形態では、前記ベクトルの次元は2以上である。
【００２９】
第三の実施形態では、前記コミットメントは零知識証明を使って開封の知識を証明することを許容する。
【００３０】
第四の実施形態では、前記コミットメントは、検証アルゴリズムから帰結する中間的な値として生成される。
【００３１】
第三の側面では、本発明は、命令を記憶している非一時的なコンピュータ・プログラム・プロダクトに向けられる。前記命令は、プロセッサによって実行されたときに、前記第一の側面の任意の実施形態の方法を実行する。
【図面の簡単な説明】
【００３２】
本発明の好ましい特徴についてこれから限定しない例として、付属の図面を参照して述べる。
【図１】本発明のある好ましい実施形態に基づく、コミットメントを生成するための暗号学的装置およびコミットメントの検証のための暗号学的装置を示す図である。
【図２】本発明のある好ましい実施形態に基づく、コミットメントを生成する方法およびコミットメントの開封を検証する方法を示す図である。
【発明を実施するための形態】
【００３３】
本発明の一つの主要な発想は、ある種のゆるやかな条件のもとで、線形準同型の構造を保存する署名は、群要素のベクトルに対する、長さを短縮する、頑健な、構造を保存するコミットメントを含意するということに基づく。結果として、本発明は、長さを短縮する、頑健な、構造を保存する落とし戸コミットメントを提供する。本方式は厳密に構造を保存するものではないことを注意しておく（つまり、コミットメント・ストリングは非特許文献１９の用語のとおりにメッセージと同じ群に存するのではない）。むしろ、本方式は、コミットメント・ストリングがGではなくGTに存するので、厳密でない意味において構造を保存する（しかし、前記論文において示されているように、厳密に構造を保存するコミットメントは長さを短縮するものであることはできない）。それでも、開封はG内の要素のみからなり、これにより、コミットされた群の要素がある種の属性を満たすことの、効率的な非対話的な証明を生成することが可能となる。
【００３４】
本発明の方式は、まず、群の要素に対するシミュレーション健全な落とし戸コミットメント（SSTC）を構築することによって得られる（非特許文献９、１参照）。
【００３５】
SSTC方式は、Garay、MacKenzieおよびYangによって非特許文献９において、ユニバーサルに構成可能な零知識証明を構築するためのツールとして、最初に提案された（非特許文献１７参照）。MacKenzieおよびYangはその後、非特許文献１において、再使用可能な頑健なコミットメントの定義の意味において開封に関して頑健性を提供するのに十分な簡略化されたセキュリティ定義を与えた（非特許文献８参照）。
【００３６】
まず、任意の、一定サイズの、線形準同型な、構造を保存する署名は必ず以下のテンプレートに準拠することを注意しておく。
【００３７】
Keygen(pp,n)〔鍵生成〕：双線形マップを用いた群(G,GT)の記述を含む公開パラメータ（public  parameters）ppおよび署名されるべき部分空間の次元n∈Nを与えられて、定数nz、nv、m∈Nを選ぶ。このうち、nzおよびnvは署名の長さを決定し、mは検証アルゴリズムにおける式の数である。次いで、群Gにおいて要素
【数６】
2014158265.tif 000008
を選ぶ。公開鍵（public  key）は
【数７】
2014158265.tif 000009
であり、秘密鍵は特定の基底に関する公開鍵要素の表現に関係する情報を含んでいる。
【００３８】
Sign(sk,τ,(M1,……,Mn))〔署名〕：タプル
【数８】
2014158265.tif 000010
を出力する。
【００３９】
SignDerive(pk,τ,{(ωi,σ(i))}i=1l)〔署名導出〕：i＝1からl〔エル〕について、各署名σ(i)を
【数９】
2014158265.tif 000011
とパースして、次いで
【数１０】
2014158265.tif 000012
を計算し、可能性としては再ランダム化ステップ後に、
【数１１】
2014158265.tif 000013
を出力する。
【００４０】
Verify(pk,σ,τ,(M1,……,Mn))〔検証〕：署名σ
【数１２】
2014158265.tif 000014
ベクトル(M1,……,Mn)およびタグτを与えられて、
【数１３】
2014158265.tif 000015
であれば0を返し、そうでなければ：
１．各j∈{1,……,m}およびv∈{1,……,nv}について、群要素として、タグτの一対一のエンコードTj,v∈Gを計算する。（この条件を、衝突耐性のある決定論的エンコードをもつようゆるめることが可能である。ここで、簡単のため単射が想定される。）
１．j＝1からmについて、次式を計算する
【数１４】
2014158265.tif 000016
２．各j∈{1,……,m}について、
【数１５】
2014158265.tif 000017
であるときかつそのときのみ、1を返す。
【００４１】
以下の記述では、線形準同型の、構造を保存する署名は、各ファイル識別子（すなわち「タグ」）について、任意の自明でないベクトル
【数１６】
2014158265.tif 000018
が有効な署名をもつ場合に、「正則（regular）」である。
【００４２】
図１は、本発明のある好ましい実施形態に基づく、コミットメントを生成する暗号学的装置１００およびコミットメントの検証のための暗号学的装置２００を示している。装置１００、２００はそれぞれ、通信のために構成された少なくとも一つのインターフェース・ユニット１１０、２１０と、少なくとも一つの処理器（「プロセッサ」）１２０、２２０と、アキュムレータおよび仲介計算結果のようなデータを記憶するよう構成された少なくとも一つのメモリ１３０、２３０とを有する。図１は、CD-ROMまたはDVDのような第一および第二のコンピュータ・プログラム・プロダクト（非一時的な記憶媒体）１４０、２４０が記憶された命令を有しており、該命令はプロセッサ１２０、２２０によって実行されたときにそれぞれ本発明に基づいてコミットメントの生成および検証を行なうことを示している。
【００４３】
構造を保存する、シミュレーション健全な落とし戸コミットメントの構築
ΠSPS＝(Keygen,Sign,SignDerive,Verify)が線形準同型な構造を保存する署名（SPS:  structure-preserving  signature）であれば、構造を保存する、シミュレーション健全な落とし戸コミットメント（SSTC）は次のように構築されうる。
【００４４】
SSTC.Setup(λ,n)：コミットされるベクトルの所望される次元n∈Nを与えられて、線形準同型SPS方式のための公開パラメータppを選ぶ。次いで、ΠSPS.Keygen(pp,n)を実行して、いくつかの定数nz,nv,mおよび秘密鍵skについて、
【数１７】
2014158265.tif 000019
を得る。コミットメント鍵はpk＝pkであり、落とし戸tkはskからなる。公開鍵は、定数nzおよびnvについて署名空間
【数１８】
2014158265.tif 000020
を定義することを注意しておく。
【００４５】
SSTC.Com(pk,tag,(M1,……,Mn))：タグtag＝τに関してベクトル(M1,……,Mn)∈Gnにコミットし、署名空間において
【数１９】
2014158265.tif 000021
を選ぶ。次いで、Verify(pk,σ,τ,(M1,……,Mn))のステップ１および２を実行する。すなわち、
【数２０】
2014158265.tif 000022
を計算する。ここで、{Tj,v}j,vは群要素の集合としてtag＝τの単射エンコードをなす。コミットメント・ストリングは、com＝(c1,……,cm)によって与えられ、一方、コミットメント解除（de-commitment）は
【数２１】
2014158265.tif 000023
からなる。
【００４６】
SSTC.FakeCom(pk,tk,tag)：
【数２２】
2014158265.tif 000024
を用いてSSTC.Comと同様に進む。
【００４７】
【数２３】
2014158265.tif 000025
が結果として得られる対を表わすものとすると、アルゴリズムは
【数２４】
2014158265.tif 000026
およびauxを出力する。auxはtag＝τについて対
【数２５】
2014158265.tif 000027
からなる。
【００４８】
【数２６】
2014158265.tif 000028
パースする。まずtag＝τについて
【数２７】
2014158265.tif 000029
上で線形準同型署名を生成する。すなわち、落とし戸tk＝skを使って、
【数２８】
2014158265.tif 000030
を計算する。
【００４９】
σ′は有効な署名であり、
【数２９】
2014158265.tif 000031
ので、フェイク開封アルゴリズムは
【数３０】
2014158265.tif 000032
を走らせることができる。構築により、
【数３１】
2014158265.tif 000033
はtag＝τに関してベクトル(M1,……,Mn)への有効なコミットメント解除である。
【００５０】
SSTC.Verify(pk,tag,(M1,……,Mn),com,dec)：コミットメントを
【数３２】
2014158265.tif 000034
として、開封decを
【数３３】
2014158265.tif 000035
としてパースする。これらが適正にパースされなければ、0を返す。次いで、tag＝τの一対一のエンコード{Tj,v}j,vを計算する。
【００５１】
【数３４】
2014158265.tif 000036
が成り立てば1を返し、そうでなければ0を返す。
【００５２】
線形準同型署名からのSSTC
このセクションは、先の構造を保存する構築の一般化を提供する。目標は、線形準同型署名からベクトルに対するシミュレーション健全な（よって頑健な）コミットメントを構築することである。SSTCを構築するための従来技術の方式は、コミットされるベクトルの知識を効率的に証明することの実現可能性を保持しつつベクトルにコミットすることを直接許容しないことを注意しておくべきである。この方法は、図２に示されている。
【００５３】
Π＝(Keygen,Sign,SignDeriv,Verify)は何らかの大きな素数p＞2λ
について
【数３５】
2014158265.tif 000037
上での線形準同型署名であるとする。Πは何らかの
【数３６】
2014158265.tif 000038
について、それぞれ公開位数pkおよびpの群G1およびG2を使うものとする。各署名σがG1に存することも想定される。検証アルゴリズムは標榜される（purported）署名σ∈G1、ファイル識別子τおよびベクトル→mを入力として受ける。この検証アルゴリズムは
【数３７】
2014158265.tif 000039
のときかつこのときのみ1を返す。ここで、Fは群G2上の範囲を取りある種の線形属性を満たする関数である。つまり、Keygenによって生成される各pkおよび各τについて、
【数３８】
2014158265.tif 000040
であることが要求される。結果として、
【数３９】
2014158265.tif 000041
となる。
【００５４】
このテンプレートは、公開位数の群における方式のみを捉えており、よって、強RSA仮定に基づく構築はカバーされないことを注意しておく。その理由は、整数上で作業するとき、メッセージおよび署名成分は各準同型演算において増大しうるが、そのため偽の開封を本来のコミットメント解除から識別不能にすることがより難しくなるのである。
【００５５】
SSTC.Setup(λ,n)：コミットされるベクトルの所望される次元n∈Nを与えられて、線形準同型署名について公開パラメータppを選ぶ。次いで、鍵生成アルゴリズムΠSPS.Keygen(pp,n)を走らせて、公開鍵pkおよび秘密鍵skを得る。コミットメント鍵はpk＝pkであり、落とし戸tkはskからなる。
【００５６】
SSTC.Com(pk,tag,→m)：tagに関してベクトル
【数４０】
2014158265.tif 000042
にコミットし、署名空間における要素
【数４１】
2014158265.tif 000043
を選ぶ（S1）。検証の式
【数４２】
2014158265.tif 000044
の左辺の要素としてFを評価することによって
【数４３】
2014158265.tif 000045
を計算し（S2）、出力する（S3）。コミットメント・ストリングはcom＝cであり、コミットメント解除はdec＝σである。
【００５７】
SSTC.FakeCom(pk,tk,tag)：SSTC.Comと同様に、ただしランダムに選んだベクトル
【数４４】
2014158265.tif 000046
を使って進む。
【００５８】
【数４５】
2014158265.tif 000047
が結果として得られるコミットメント／コミットメント解除対を表わすとすると、アルゴリズムは
【数４６】
2014158265.tif 000048
と設定する。
【００５９】
【数４７】
2014158265.tif 000049
【数４８】
2014158265.tif 000050
これはまずtag＝τについて座標ごとの差
【数４９】
2014158265.tif 000051
に対する線形準同型署名を生成する。つまり、落とし戸tk＝skを使って、
【数５０】
2014158265.tif 000052
を計算する。最後に、
【数５１】
2014158265.tif 000053
【数５２】
2014158265.tif 000054
コミットメントcomをc∈G2として、開封decをσ∈G1としてパースする（S4）。これらが適正にパースされない場合には、0を返す（S5）。それ以外の場合には、
【数５３】
2014158265.tif 000055
の場合には1を返し、そうでない場合には0を返す（S6）。
【００６０】
Attrapadungらの線形準同型方式（非特許文献２０参照）は、群G1は演算(・,・,＋)についての群である積
【数５４】
2014158265.tif 000056
であり、
【数５５】
2014158265.tif 000057
であるテンプレートの特定の事例化として見ることができる。本方式では、このように、G1およびG2はそれぞれ位数p3およびpをもつ。線形関数Fについては、次のように事例化できる。
【００６１】
【数５６】
2014158265.tif 000058
結果として、計算ディフィー／ヘルマン（CDH）仮定に基づく、ベクトルに対する新しい非対話的な、シミュレーション健全な落とし戸コミットメントが得られる。
【００６２】
この方式は、項vsおよびsを除去して
【数５７】
2014158265.tif 000059
となるようにすることによって最適化されることができる。
【００６３】
実際、項(vs,s)∈G×Zpは根底にある署名方式では必要であるものの、これらは結果として得られるコミットメントにおいては消去できる。
【００６４】
最適化は、CDH仮定に依拠し、ベクトルにコミットすることを許容する次のようなSSTC方式を生じさせる。CDH仮定に基づく従来技術の頑健なコミットメントは――暗黙的または明示的に――二つの論文において記述されているが、それらをモジュラーな仕方でどのようにしてベクトルにコミットするよう拡張するかは明らかではなかったことを注意しておく（非特許文献２１、２２参照）。
【００６５】
SSTC.Setup(λ,n)：コミットされるベクトルの所望される次元n∈Nを与えられて、素数位数p＞2λの双線形群(G,GT)を選ぶ。何らかのL∈poly(λ)について
【数５８】
2014158265.tif 000060
を選ぶ。これらの要素u0,…,uL∈GL+1は、任意のLビット・ストリングτ＝τ[1]…τ[L]∈{0,1}Lがハッシュ値
【数５９】
2014158265.tif 000061
にマッピングされるような数論的ハッシュ関数HG：{0,1}L→Gを実装するために使われる。次いで、i＝1からnについて
【数６０】
2014158265.tif 000062
が選ばれ、識別子空間
【数６１】
2014158265.tif 000063
が定義される。落とし戸はtk＝αであり、公開鍵は
【数６２】
2014158265.tif 000064
からなる。
【００６６】
SSTC.Com(pk,tag,→m)：tagに関してベクトル→m＝(m1,…,mn)∈Zpnにコミットし、署名空間内の要素
【数６３】
2014158265.tif 000065
を選び、
【数６４】
2014158265.tif 000066
を計算する。
【００６７】
コミットメント・ストリングcom＝c∈GTおよびコミットメント解除dec＝(σ1,σ2)∈G2を返す。
【００６８】
SSTC.FakeCom(pk,tk,tag)：SSTC.Comと同様に、ただしランダムに選んだベクトル
【数６５】
2014158265.tif 000067
を使って進む。
【００６９】
【数６６】
2014158265.tif 000068
が結果として得られるコミットメント／コミットメント解除対を表わすとすると、アルゴリズムは
【数６７】
2014158265.tif 000069
と設定する。
【００７０】
【数６８】
2014158265.tif 000070
【数６９】
2014158265.tif 000071
これはまずタグtagについて差
【数７０】
2014158265.tif 000072
に対する線形準同型署名(σ′1,σ′2)∈G2を生成する。つまり、tk＝αを使って、
【数７１】
2014158265.tif 000073
を計算する。これは次式を満たす。
【００７１】
【数７２】
2014158265.tif 000074
最後に、
【数７３】
2014158265.tif 000075
を計算し、
【数７４】
2014158265.tif 000076
を返す。
【００７２】
SSTC.Verify(pk,tag,→m,com,dec)：コミットメントcomをc∈GTとして、開封decを(σ1,σ2)∈G2としてパースする。これらが適正にパースされない場合には、0を返す。それ以外の場合には、(σ1,σ2)が
【数７５】
2014158265.tif 000077
を満たす場合には1を返し、そうでない場合には0を返す。
【００７３】
さらなるSSTC方式を提示する前に、下記で基礎になる線形準同型な構造を保存する署名方式について述べておく。
【００７４】
Keygen(pp,n)：セキュリティ・パラメータλおよび署名されるべき部分空間の次元n∈Nが与えられて、素数位数p＞2λの双線形群(G,GT)を選び、下記のステップを実行する。
１．
【数７６】
2014158265.tif 000078
を選び、
【数７７】
2014158265.tif 000079
と定義する。
２．各i∈{i,…,n}について、
【数７８】
2014158265.tif 000080
を選び、
【数７９】
2014158265.tif 000081
を計算する。
３．τ＝τ[1]…τ[L]∈{0,1}Lを
【数８０】
2014158265.tif 000082
にマッピングするハッシュ関数HG：{0,1}L→Gを定義するランダムなベクトル
【数８１】
2014158265.tif 000083
を選ぶ。
【００７５】
公開鍵は
【数８２】
2014158265.tif 000084
からなり、秘密鍵は
【数８３】
2014158265.tif 000085
である。
【００７６】
Sign(sk,τ,(M1,…,Mn))：
【数８４】
2014158265.tif 000086
を使ってファイル識別子τに関してベクトル(M1,…,Mn)∈Gnに署名するために、
【数８５】
2014158265.tif 000087
を選び、
【数８６】
2014158265.tif 000088
を計算する。
【００７７】
署名はσ＝(z,r,u,v)∈G4となる。
【００７８】
【数８７】
2014158265.tif 000089
pk、ファイル識別子τおよびl個のタプル(ωi,σ(i))を与えられて、i＝1からl〔エル〕について、各署名σ(i)をσ(i)＝(zi,ri,ui,vi)∈G4とパースする。次いで、
【数８８】
2014158265.tif 000090
を選び、
【数８９】
2014158265.tif 000091
を計算し、σ＝(z,r,u,v)を返す。
【００７９】
Verify(pk,σ,τ,(M1,……,Mn))〔検証〕：署名σ＝(z,r,u,v)∈G4、ファイル識別子τおよびベクトル(M1,……,Mn)を与えられて、
【数９０】
2014158265.tif 000092
ときかつそのときのみ、1を返す。
【００８０】
線形準同型な、構造を保存する署名からのSSTC
構造を保存するシミュレーション健全な落とし戸コミットメントの構築を線形準同型な署名に適用することによって特に有利な実施形態が得られる。これについて下記で述べる。
【００８１】
基礎になる準同型署名と同様に、結果として得られるSSTC（これは構造を保存する）のセキュリティは、同時二重ペアリング（SDP）問題の困難さに依拠する。
【００８２】
SSTC.Setup(λ,n)：コミットされるベクトルの所望される次元n∈Nを与えられて、素数位数p＞2λの双線形群(G,GT)を選ぶ。次いで、
１．
【数９１】
2014158265.tif 000093
を選ぶ。
２．
【数９２】
2014158265.tif 000094
を定義する。
３．各i∈{i,…,n}について、
【数９３】
2014158265.tif 000095
を選び、
【数９４】
2014158265.tif 000096
を計算する。
４．τ＝τ[1]…τ[L]∈{0,1}Lを
【数９５】
2014158265.tif 000097
にマッピングするハッシュ関数HG：{0,1}L→Gを定義するランダムなベクトル
【数９６】
2014158265.tif 000098
を選ぶ。
【００８３】
公開鍵は
【数９７】
2014158265.tif 000099
からなり、落とし戸は
【数９８】
2014158265.tif 000100
である。
【００８４】
SSTC.Com(pk,tag,(M1,……,Mn))：ベクトル(M1,…,Mn)∈Gnにタコミットするために、
【数９９】
2014158265.tif 000101
を選び、
【数１００】
2014158265.tif 000102
を計算する。
【００８５】
次いで、com＝(c1,c2)∈GT2およびdec＝(z,r,u,v)∈G4を返す。
【００８６】
SSTC.FakeCom(pk,tk,tag)：
【数１０１】
2014158265.tif 000103
を選び、
【数１０２】
2014158265.tif 000104
を計算する。
【００８７】
次いで、
【数１０３】
2014158265.tif 000105
を返す。
【００８８】
【数１０４】
2014158265.tif 000106
下記で述べる基礎になる線形準同型SPSを使ってベクトル
【数１０５】
2014158265.tif 000107
に対する線形準同型署名(z',r',u',v')を生成する。次いで、
【数１０６】
2014158265.tif 000108
を生成する。
【００８９】
【数１０７】
2014158265.tif 000109
を返す。これは次式を満たす。
【００９０】
【数１０８】
2014158265.tif 000110
SSTC.Verify(pk,tag,(M1,…,Mn),com,dec)：コミットメントcomを(c1,c2)∈GT2として、開封decを(z,r,u,v)∈G4としてパースする。これらが適正にパースされない場合には、0を返す。それ以外の場合には、(z,r,u,v)が
【数１０９】
2014158265.tif 000111
を満たす場合には1を返し、そうでない場合には0を返す。
【００９１】
当業者は、ベクトルに対して機能する本発明の方式がスカラーに対しても機能することを理解するであろう（その場合、次元nは1に等しい）。このように、次元nは任意の正の整数1,2,3,……であることができる。
【００９２】
本発明の方式が、上述した所望される特徴をもつコミットメント方式を提供できることが理解されるであろう。
【００９３】
本明細書および（適切な場合には）請求項および図面において開示される各特徴は、独立して、あるいは任意の適切な組み合わせにおいて与えられてもよい。ハードウェアで実装されるとして記述される特徴は、ソフトウェアで実装されてもよく、逆にソフトウェアで実装されるとして記述される特徴は、ハードウェアで実装されてもよい。請求項に参照符号があったとしても単に例示するものであって、請求項の範囲に対する限定効果はもたない。
【図１】
2014158265.tif 000112
【図２】
2014158265.tif 000113
【外国語明細書】
2014158265000001.pdf