(57)【要約】【課題】２つ以上の証明式集合に適用でき、一般的なペアリング積で表現された証明式を証明の対象とし、効率的に証明する。【解決手段】証明装置は、証明式の定数と定数のペアリングのすべてを、定数と変数のペアリングに変換した変換式を生成することで、変換式集合を生成する。Ｗｎが１またはｇのときのみ成り立つペアリング積の等式と、Ｗ１，…，ＷＮのいずれか１つがｇであり他がすべて１のときには成り立つペアリング積の等式を、スイッチャー式とする。すべての変換式集合について、Ｗｎ＝ｇのときにはＹｉ＝Ｂｉでのみ成り立ち、Ｗｎ＝１のときにはＹｉ＝１でのみ成り立つペアリング積の等式を、変換変数式として生成する。証拠を保有する集合側の変数には証拠と元の定数を割り当て、証拠を保有しない集合側の変数にはペアリングの結果が１となる値を割り当て、ＧＳ証明を行う。検証装置は、この結果を確認する。【選択図】図１
2014164285.tif 000002
【特許請求の範囲】
【請求項１】
群の要素同士のペアリングの積で構成された証明の対象となる式を証明式、１つ以上の証明式を含む証明式の集合を証明式集合と呼ぶこととし、
Ｎ個の証明式集合のうち少なくとも１つの証明式集合に含まれるすべての証明式を成り立たせる変数の情報を証明装置が保有していることを、検証装置に対して証明する証明システムであって、
式内の値であって前記証明装置も前記検証装置も保有している値を定数、式内の値であって前記検証装置に対して秘匿された値を変数と呼ぶこととし、Ｎは２以上の整数、ｎとｍは１以上Ｎ以下の整数、Ｗｎはｎ番目の証明式集合に対応した群の要素の変数、ｇは群の要素であって１以外の定数、ｉは対応関係を示す番号とし、
前記証明装置は、
すべての証明式集合に含まれるすべての証明式に含まれるすべての定数の情報である証明対象情報を取得する証明対象取得部と、
いずれか１つの証明式集合であるｍ番目の証明式集合に含まれるすべての証明式を成り立たせる変数の情報である証拠を取得する証拠取得部と、
ｎ＝１，…，Ｎのすべてに対して、ｎ番目の証明式集合に含まれるすべての証明式について、定数と定数のペアリングのすべてを、定数と変数のペアリングに変換した変換式を生成することで、ｎ番目の変換式集合を生成する変換部と、
ｎ＝１，…，ＮについてＷｎが１またはｇのときのみ成り立つペアリング積の等式と、Ｗ１，…，ＷＮのいずれか１つがｇであり他がすべて１のときには成り立つペアリング積の等式とを、スイッチャー式として生成するスイッチャー生成部と、
ｎ＝１，…，Ｎのすべてに対して、ｎ番目の変換式集合の中で、前記変換部で定数Ｂｉから変換された変数Ｙｉごとに、Ｗｎ＝ｇのときにはＹｉ＝Ｂｉでのみ成り立ち、Ｗｎ＝１のときにはＹｉ＝１でのみ成り立つペアリング積の等式を、変換変数式として生成し、この変換変数式の集合をｎ番目の変換変数式集合とする変換変数式生成部と、
前記スイッチャー式にＷｍ＝ｇ、ｎ≠ｍのＷｎにはＷｎ＝１を割り当て、ｍ番目の変換式集合に含まれるすべての変換式の変数とｍ番目の変換変数式集合に含まれるすべての変換変数式の変数に、前記証拠から得られる値とＹｉ＝Ｂｉを割り当て、ｍ番目以外のすべての変換式集合に含まれるすべての変換式のすべての変数とｍ番目以外のすべての変換変数式集合に含まれるすべての変換変数式の変数にペアリングの結果が１となる値を割り当て、すべてのスイッチャー式、すべての変換式、すべての変換変数式に対してそれぞれＧＳ証明を行うＧＳ証明実行部と、
すべての前記スイッチャー式、すべての前記変換式集合、すべての前記変換変数式集合、および前記ＧＳ証明のすべての結果の情報を出力する証明出力部と
を備え、
前記検証装置は、
すべての証明式集合に含まれるすべての証明式に含まれるすべての定数の情報である証明対象情報を取得する検証対象取得部と、
前記証明装置が出力したすべての前記スイッチャー式、すべての前記変換式集合、すべての前記変換変数式集合、前記ＧＳ証明のすべての結果の情報を取得する証明入力部と、
すべての前記スイッチャー式、すべての前記変換式、すべての前記変換変数式に対する前記ＧＳ証明の結果を確認するＧＳ証明確認部と、
すべての前記スイッチャー式、すべての前記変換式、すべての前記変換変数式が、前記証明対象情報に対応していることを確認する対象確認部と
を備える
証明システム。
【請求項２】
請求項１記載の証明システムであって、
ｅは群の要素同士のペアリングとし、
前記スイッチャー式は、
ｅ（Ｗ１，Ｗ１／ｇ）＝１，…，ｅ（ＷＮ，ＷＮ／ｇ）＝１と
【数８】
2014164285.tif 000010
であり、
前記変換変数式は、
ｅ（Ｂｉ，Ｗ）＝ｅ（Ｙｉ，ｇ）
である
ことを特徴とする証明システム。
【請求項３】
請求項１または２記載の証明システムであって、
群Ｇ，ＧＴを素数位数ｑの群、ｅは群Ｇの要素同士を群ＧＴの要素に写像するペアリング、Ａａ，Ｂｆ，Ｃｆは群Ｇの要素である定数、Ｕａ，Ｖｂ，Ｘｃは群Ｇの要素である変数、ｄｂｃは０以上ｑ−１以下の整数である定数、ａ，ｂ，ｃ，ｆは対応関係を示すための番号とし、
前記証明式は、
【数９】
2014164285.tif 000011
または、この式の項を移項することで表現できる式であり、
前記変換部は、前記証明式のＢｆもしくはＣｆ、または移項後の表現でのＢｆに対応する定数もしくはＣｆに対応する定数を、前記定数Ｂｉまたは前記定数Ｂｊとして、変数に変換する
ことを特徴とする証明システム。
【請求項４】
群の要素同士のペアリングの積で構成された証明の対象となる式を証明式、１つ以上の証明式を含む証明式の集合を証明式集合と呼ぶこととし、
Ｎ個の証明式集合のうち少なくとも１つの証明式集合に含まれるすべての証明式を成り立たせる変数の情報を保有していることを、検証装置に対して証明する証明装置であって、
式内の値であって前記証明装置も前記検証装置も保有している値を定数、式内の値であって前記検証装置に対して秘匿された値を変数と呼ぶこととし、Ｎは２以上の整数、ｎとｍは１以上Ｎ以下の整数、Ｗｎはｎ番目の証明式集合に対応した群の要素の変数、ｇは群の要素であって１以外の定数、ｉは対応関係を示す番号とし、
すべての証明式集合に含まれるすべての証明式に含まれるすべての定数の情報である証明対象情報を取得する証明対象取得部と、
いずれか１つの証明式集合であるｍ番目の証明式集合に含まれるすべての証明式を成り立たせる変数の情報である証拠を取得する証拠取得部と、
ｎ＝１，…，Ｎのすべてに対して、ｎ番目の証明式集合に含まれるすべての証明式について、定数と定数のペアリングのすべてを、定数と変数のペアリングに変換した変換式を生成することで、ｎ番目の変換式集合を生成する変換部と、
ｎ＝１，…，ＮについてＷｎが１またはｇのときのみ成り立つペアリング積の等式と、Ｗ１，…，ＷＮのいずれか１つがｇであり他がすべて１のときには成り立つペアリング積の等式とを、スイッチャー式として生成するスイッチャー生成部と、
ｎ＝１，…，Ｎのすべてに対して、ｎ番目の変換式集合の中で、前記変換部で定数Ｂｉから変換された変数Ｙｉごとに、Ｗｎ＝ｇのときにはＹｉ＝Ｂｉでのみ成り立ち、Ｗｎ＝１のときにはＹｉ＝１でのみ成り立つペアリング積の等式を、変換変数式として生成し、この変換変数式の集合をｎ番目の変換変数式集合とする変換変数式生成部と、
前記スイッチャー式にＷｍ＝ｇ、ｎ≠ｍのＷｎにはＷｎ＝１を割り当て、ｍ番目の変換式集合に含まれるすべての変換式の変数とｍ番目の変換変数式集合に含まれるすべての変換変数式の変数に、前記証拠から得られる値とＹｉ＝Ｂｉを割り当て、ｍ番目以外のすべての変換式集合に含まれるすべての変換式のすべての変数とｍ番目以外のすべての変換変数式集合に含まれるすべての変換変数式の変数にペアリングの結果が１となる値を割り当て、すべてのスイッチャー式、すべての変換式、すべての変換変数式に対してそれぞれＧＳ証明を行うＧＳ証明実行部と、
すべての前記スイッチャー式、すべての前記変換式集合、すべての前記変換変数式集合、および前記ＧＳ証明のすべての結果の情報を出力する証明出力部と
を備える証明装置。
【請求項５】
群の要素同士のペアリングの積で構成された証明の対象となる式を証明式、１つ以上の証明式を含む証明式の集合を証明式集合と呼ぶこととし、
Ｎ個の証明式集合のうち少なくとも１つの証明式集合に含まれるすべての証明式を成り立たせる変数の情報を証明装置が保有していることを検証する検証装置であって、
式内の値であって前記証明装置も前記検証装置も保有している値を定数、式内の値であって前記検証装置に対して秘匿された値を変数と呼ぶこととし、Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｗｎはｎ番目の証明式集合に対応した群の要素の変数、ｇは群の要素であって１以外の定数、ｉは対応関係を示す番号とし、
ｎ番目の証明式集合に含まれるすべての証明式について、定数と定数のペアリングのすべてを、定数と変数のペアリングに変換した変換式を生成することで、証明式集合ごとに生成された集合をｎ番目の変換式集合とし、
ｎ＝１，…，ＮについてＷｎが１またはｇのときのみ成り立つペアリング積の等式と、Ｗ１，…，ＷＮのいずれか１つがｇであり他がすべて１のときには成り立つペアリング積の等式とをスイッチャー式とし、
ｎ番目の変換式集合の中で、定数Ｂｉから変換された変数Ｙｉごとに生成された、Ｗｎ＝ｇのときにはＹｉ＝Ｂｉでのみ成り立ち、Ｗｎ＝１のときにはＹｉ＝１でのみ成り立つペアリング積の等式を変換変数式、この変換変数式の集合をｎ番目の変換変数式集合とし、
すべての証明式集合に含まれるすべての証明式に含まれるすべての定数の情報である証明対象情報を取得する検証対象取得部と、
前記証明装置が出力したすべての前記スイッチャー式、すべての前記変換式集合、すべての前記変換変数式集合の情報、およびすべての前記スイッチャー式、すべての前記変換式、すべての前記変換変数式に対するＧＳ証明のすべての結果の情報を取得する証明入力部と、
前記ＧＳ証明のすべての結果を確認するＧＳ証明確認部と、
すべての前記スイッチャー式、すべての前記変換式、すべての前記変換変数式が、前記証明対象情報に対応していることを確認する対象確認部と、
を備える検証装置。
【請求項６】
群の要素同士のペアリングの積で構成された証明の対象となる式を証明式、１つ以上の証明式を含む証明式の集合を証明式集合と呼ぶこととし、
Ｎ個の証明式集合のうち少なくとも１つの証明式集合に含まれるすべての証明式を成り立たせる変数の情報を証明装置が保有していることを、検証装置に対して証明する証明方法であって、
式内の値であって前記証明装置も前記検証装置も保有している値を定数、式内の値であって前記検証装置に対して秘匿された値を変数と呼ぶこととし、Ｎは２以上の整数、ｎとｍは１以上Ｎ以下の整数、Ｗｎはｎ番目の証明式集合に対応した群の要素の変数、ｇは群の要素であって１以外の定数、ｉは対応関係を示す番号とし、
前記証明装置が、すべての証明式集合に含まれるすべての証明式に含まれるすべての定数の情報である証明対象情報を取得する証明対象取得ステップと、
前記証明装置が、いずれか１つの証明式集合であるｍ番目の証明式集合に含まれるすべての証明式を成り立たせる変数の情報である証拠を取得する証拠取得ステップと、
前記証明装置が、ｎ＝１，…，Ｎのすべてに対して、ｎ番目の証明式集合に含まれるすべての証明式について、定数と定数のペアリングのすべてを、定数と変数のペアリングに変換した変換式を生成することで、ｎ番目の変換式集合を生成する変換ステップと、
前記証明装置が、ｎ＝１，…，ＮについてＷｎが１またはｇのときのみ成り立つペアリング積の等式と、Ｗ１，…，ＷＮのいずれか１つがｇであり他がすべて１のときには成り立つペアリング積の等式とを、スイッチャー式として生成するスイッチャー生成ステップと、
前記証明装置が、ｎ＝１，…，Ｎのすべてに対して、ｎ番目の変換式集合の中で、前記変換部で定数Ｂｉから変換された変数Ｙｉごとに、Ｗｎ＝ｇのときにはＹｉ＝Ｂｉでのみ成り立ち、Ｗｎ＝１のときにはＹｉ＝１でのみ成り立つペアリング積の等式を、変換変数式として生成し、この変換変数式の集合をｎ番目の変換変数式集合とする変換変数式生成ステップと、
前記証明装置が、前記スイッチャー式にＷｍ＝ｇ、ｎ≠ｍのＷｎにはＷｎ＝１を割り当て、ｍ番目の変換式集合に含まれるすべての変換式の変数とｍ番目の変換変数式集合に含まれるすべての変換変数式の変数に、前記証拠から得られる値とＹｉ＝Ｂｉを割り当て、ｍ番目以外のすべての変換式集合に含まれるすべての変換式のすべての変数とｍ番目以外のすべての変換変数式集合に含まれるすべての変換変数式の変数にペアリングの結果が１となる値を割り当て、すべてのスイッチャー式、すべての変換式、すべての変換変数式に対してそれぞれＧＳ証明を行うＧＳ証明実行ステップと、
前記証明装置が、すべての前記スイッチャー式、すべての前記変換式集合、すべての前記変換変数式集合、および前記ＧＳ証明のすべての結果の情報を出力する証明出力ステップと、
前記検証装置が、すべての証明式集合に含まれるすべての証明式に含まれるすべての定数の情報である証明対象情報を取得する検証対象取得ステップと、
前記検証装置が、前記証明装置が出力したすべての前記スイッチャー式、すべての前記変換式集合、すべての前記変換変数式集合、前記ＧＳ証明のすべての結果の情報を取得する証明入力ステップと、
前記検証装置が、すべての前記スイッチャー式、すべての前記変換式、すべての前記変換変数式に対する前記ＧＳ証明の結果を確認するＧＳ証明確認ステップと、
前記検証装置が、すべての前記スイッチャー式、すべての前記変換式、すべての前記変換変数式が、前記証明対象情報に対応していることを確認する対象確認ステップと、
を有する証明方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２つ以上の証明式集合のうち少なくとも１つの証明式集合に含まれるすべての証明式を成り立たせる変数の値を証明装置が保有していることを、検証装置に対して証明する証明システム、証明装置、検証装置、証明方法に関する。
【背景技術】
【０００２】
群Ｇの要素同士のペアリングの積で構成された証明の対象となる式を証明式、１つ以上の証明式を含む証明式の集合を証明式集合と呼ぶこととする。そして、任意のペアリング積の等式について、その式を満たす値を知っていることを、その値を公開せずに非対話的に証明する手法として、Groth-Sahai非対話証明（以下、「ＧＳ証明」という。）が知られている（非特許文献１）。また、２つの証明式集合のうち少なくとも１つの証明式集合に含まれるすべての証明式を成り立たせる変数の値を証明装置が保有していることを、ＧＳ証明を用いて証明する方法として、非特許文献２，３の方法が知られている。
【０００３】
ｅは群Ｇの要素同士のペアリング、Ｗ０，Ｗ１，Ｗ，Ｕ，Ｖ，Ｘは群Ｇの要素の変数、ｇは群Ｇの要素であって１以外の定数、Ａは群Ｇの要素の定数とする。非特許文献２の方法は、
ｅ（ｇ，ｇＷ０Ｗ１）＝１
をスイッチャー式として採用し、ペアリングを含む式を追加することで証明する方法である。非特許文献３の方法は、証明する対象を
ｅ（Ａ，Ｕ）ｅ（Ｖ，Ｘ）＝１  と  ｅ（Ａ，Ｘ）＝ｅ（ｇ，ｇ）
の形に限定して、
ｅ（Ｗ，Ｗ／ｇ）＝１
をスイッチャー式として採用し、ペアリングを含む式を追加することで証明する方法である。
【０００４】
なお、証明式や証明式集合の具体例としては、非特許文献４のような署名がある。非特許文献４の署名は、
【数１】
2014164285.tif 000003
という２つのペアリングの積で構成された式からなる。また、これらの式の中のそれぞれの値は、公開鍵から計算できる定数または検証装置には秘匿された秘密鍵から計算できる変数である。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Jens Groth and Amit Sahai, “Ecient non-interactive proof systems for bilinear groups”, In EUROCRYPT 2008, pages 415-432, 2008.
【非特許文献２】Jens Groth, “Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures”, Asiacrypt 2006, Springer-Verlag, 2006.
【非特許文献３】Jan Camenisch, Nishanth Chandran and Victor Shoup, “A Public Key Encryption Scheme Secure against Key Dependent Chosen Plaintext and Adaptive Chosen Ciphertext Attacks”, Eurocrypt 2009, Springer-Verlag, 2009.
【非特許文献４】Masayuki Abe, Kristiyan Haralambiev and Miyako Ohkubo, “Signing on Elements in Bilinear Groups for Modular Protocol Design”, IACR e-print 2010/133 ［平成２５年１月３０日検索］、インターネット<URL: http://eprint.iacr.org/2010/133>.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献２の方法は、追加する変数とペアリングを含む式の数が多く、証明の効率が悪いという課題がある。また、非特許文献３の方法は、証明式が特定の形式に分解できていることが必要であり、利用の用途が限定されるという課題がある。さらに、非特許文献２，３の方法は２つの証明式集合を前提としていて、３つ以上の証明式集合のいずれか１つの証明式集合に含まれるすべての証明式を成り立たせる変数の値を証明装置が保有していることを、ＧＳ証明を用いて証明することはできない。
【０００７】
本発明は、２つの証明式集合に限定することなく、２つ以上の証明式集合に適用でき（２つの場合も適用できるが、２つよりも多い場合にも適用でき）、一般的なペアリング積で表現された証明式を証明の対象とし、効率的に証明できる技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本明細書では、群Ｇの要素同士のペアリングの積で構成された証明の対象となる式を証明式、１つ以上の証明式を含む証明式の集合を証明式集合と呼ぶこととする。本発明の証明システムは、２つ以上の証明式集合のうち少なくとも１つの証明式集合に含まれるすべての証明式を成り立たせる変数の情報を証明装置が保有していることを、検証装置に対して証明する。また、式内の値であって証明装置も検証装置も保有している値を定数、式内の値であって検証装置に対して秘匿された値を変数と呼ぶこととする。Ｎは２以上の整数、ｎとｍは１以上Ｎ以下の整数、Ｗｎはｎ番目の証明式集合に対応した群Ｇの要素の変数、ｇは群Ｇの要素であって１以外の定数、ｉは対応関係を示す番号とする。証明装置は、証明対象取得部、証拠取得部、変換部、スイッチャー生成部、変換変数式生成部、ＧＳ証明実行部、証明出力部を備える。検証装置は、検証対象取得部、証明入力部、ＧＳ証明確認部、対象確認部を備える。証明対象取得部は、すべての証明式集合に含まれるすべての証明式に含まれるすべての定数の情報である証明対象情報を取得する。証拠取得部は、いずれか１つの証明式集合であるｍ番目の証明式集合に含まれるすべての証明式を成り立たせる変数の情報である証拠を取得する。変換部は、ｎ＝１，…，Ｎのすべてに対して、ｎ番目の証明式集合に含まれるすべての証明式について、定数と定数のペアリングのすべてを、定数と変数のペアリングに変換した変換式を生成することで、ｎ番目の変換式集合を生成する。スイッチャー生成部は、ｎ＝１，…，ＮについてＷｎが１またはｇのときのみ成り立つペアリング積の等式と、Ｗ１，…，ＷＮのいずれか１つがｇであり他がすべて１のときには成り立つペアリング積の等式を、スイッチャー式として生成する。変換変数式生成部は、ｎ＝１，…，Ｎのすべてに対して、ｎ番目の変換式集合の中で、変換部で定数Ｂｉから変換された変数Ｙｉごとに、Ｗｎ＝ｇのときにはＹｉ＝Ｂｉでのみ成り立ち、Ｗｎ＝１のときにはＹｉ＝１でのみ成り立つペアリング積の等式を、変換変数式として生成し、この変換変数式の集合をｎ番目の変換変数式集合とする。ＧＳ証明実行部は、スイッチャー式にＷｍ＝ｇ、ｎ≠ｍのＷｎにはＷｎ＝１を割り当て、ｍ番目の変換式集合に含まれるすべての変換式の変数とｍ番目の変換変数式集合に含まれるすべての変換変数式の変数に、証拠から得られる値とＹｉ＝Ｂｉを割り当て、ｍ番目以外のすべての変換式集合に含まれるすべての変換式のすべての変数とｍ番目以外のすべての変換変数式集合に含まれるすべての変換変数式の変数にペアリングの結果が１となる値を割り当て、すべてのスイッチャー式、すべての変換式、すべての変換変数式に対してそれぞれＧＳ証明を行う。証明出力部は、すべてのスイッチャー式、すべての変換式集合、すべての変換変数式集合、およびＧＳ証明のすべての結果の情報を出力する。検証対象取得部は、すべての証明式集合に含まれるすべての証明式に含まれるすべての定数の情報である証明対象情報を取得する。証明入力部は、証明装置が出力したすべてのスイッチャー式、すべての変換式集合、すべての変換変数式集合、ＧＳ証明のすべての結果の情報を取得する。ＧＳ証明確認部は、すべてのスイッチャー式、すべての変換式、すべての変換変数式に対するＧＳ証明の結果を確認する。対象確認部は、すべてのスイッチャー式、すべての変換式、すべての変換変数式が、証明対象情報に対応していることを確認する。
【発明の効果】
【０００９】
本発明の証明システムでは、２つ以上の証明式集合に適用でき、ペアリングの積で表現された証明式の形の制限はない。また、本発明の証明システムによれば、証明式中の定数と定数のペアリングに対してのみ変換の処理を行い、定数から変数への変換ごとに１つの変換変数式（ペアリングを含む式）を追加するだけである。したがって、証明式中のすべてのペアリングに対して変換の処理を行うことを前提としている非特許文献２の方法よりも、追加しなければならないペアリングを含む式の数を少なくできる。
【図面の簡単な説明】
【００１０】
【図１】本発明の証明システムの構成例を示す図。
【図２】証明装置の処理フローの例を示す図。
【図３】検証装置の処理フローの例を示す図。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１２】
以下では、群Ｇの要素同士のペアリングの積で構成された証明の対象となる式を証明式、１つ以上の証明式を含む証明式の集合を証明式集合と呼ぶこととする。本発明の証明システムは、２つ以上の証明式集合のうち少なくとも１つの証明式集合に含まれるすべての証明式を成り立たせる変数の情報を証明装置が保有していることを、検証装置に対して証明する。また、明細書中で「定数」とは数式内の値であって証明装置も検証装置も保有している値（既知の値）を示しており、「変数」とは数式内の値であって検証装置に対して秘匿された値を示している。さらに、群Ｇ，ＧＴを素数位数ｑの群、ｅは群Ｇの要素同士を群ＧＴの要素に写像するペアリング、Ｎは２以上の整数、ｎとｍは１以上Ｎ以下の整数、Ｗｎはｎ番目の証明式集合に対応した群Ｇの要素の変数、ｇは群Ｇの要素であって１以外の定数、ｉは対応関係を示す番号とする。なお、ｇ１，ｇ２を群Ｇの要素であって１以外の定数、α，βを０以上ｑ−１以下の整数とするときに、ペアリングｅは、ｅ（ｇ１，ｇ２）≠１、ｅ（ｇ１α，ｇ２β）＝ｅ（ｇ１，ｇ２）αβとなる性質を持つ写像である。
【００１３】
また、Ａａ，Ｂｆ，Ｃｆは群Ｇの要素である定数、Ｕａ，Ｖｂ，Ｘｃは群Ｇの要素である変数、ｄｂｃは０以上ｑ−１以下の整数である定数、ａ，ｂ，ｃ，ｆは対応関係を示すための番号とすると、証明式は、一般的に
【数２】
2014164285.tif 000004
または、この式の項を移項すること（両辺に同じ項を乗算すること、または両辺を同じ項で除算すること）で表現できる式である。つまり、ペアリングの積で表現されたすべての式は、移項によって整理すれば式（１）の形に変形できる。そこで、以下での一般化した説明では、式（１）を用いて説明する。
【００１４】
このようなペアリングの積で表現される式は、例えば非特許文献４に示した署名で用いられている。そして、１つの署名は、ペアリングの積で表現された１つ以上の式（非特許文献４の場合は２つの式）で構成され、すべての式を満たすことを確認することで署名の検証が行われる。つまり、署名の中の１つの式が本明細書中の証明式に相当し、署名が証明式集合に相当する。そして、上述の「２つ以上の証明式集合のうち少なくとも１つの証明式集合に含まれるすべての証明式を成り立たせる変数の値を証明装置が保有していることを、検証装置に対して証明する。」を署名に当てはめてみると、「２つ以上の署名のうち少なくとも１つの正当な署名を証明装置が保有していることを、検証装置に対して証明する。」という意味である。ただし、本発明は、署名に限定することなく適用できるものであり、一般的な表現として証明式や証明式集合という表現を用いている。
【００１５】
＜証明システムの構成と処理＞
図１に本発明の証明システムの構成例を示す。また、図２に証明装置の処理フローの例、図３に検証装置の処理フローの例を示す。証明システムは、少なくとも証明装置１００と検証装置２００を備える。図１では証明装置１００と検証装置２００はネットワーク９００で接続されているが、証明装置１００と検証装置２００との情報の受け渡しは、ネットワーク９００経由に限定する必要はなく、記録媒体などによって情報の受け渡しを行ってもよい。
【００１６】
証明装置１００は、証明対象取得部１１０、証拠取得部１２０、変換部１３０、スイッチャー生成部１４０、変換変数式生成部１５０、ＧＳ証明実行部１６０、証明出力部１７０、記録部１９０を備える。検証装置２００は、検証対象取得部２１０、証明入力部２２０、ＧＳ証明確認部２３０、対象確認部２４０、記録部２９０を備える。
【００１７】
証明対象取得部１１０は、すべての証明式集合に含まれるすべての証明式に含まれるすべての定数の情報である証明対象情報を取得し、記録部１９０に記録する（Ｓ１１０）。証明式の形はあらかじめ定めておいてもよいし、ステップＳ１１０の処理の中で取得してもよい。また、「定数の情報」とは、定数の値そのものであっても、あらかじめ定めた方法で計算するために必要な値でもよい。例えば、ステップＳ１１０では、公開鍵などの情報を取得する。なお、本明細書では、「取得」とは、外部から得るだけではなく、証明装置１００が生成することも含む意味で用いている。「集合」とは、まとまりを表わす程度の意味であって、証明式集合とは１つ以上の証明式のまとまりという意味である。また、証明式集合の一方を第１証明式集合、他方を第２証明式集合と呼ぶことにする。
【００１８】
証拠取得部１２０は、いずれか１つの証明式集合であるｍ番目の証明式集合に含まれるすべての証明式を成り立たせる変数の情報である証拠を取得し、記録部１９０に記録する（Ｓ１２０）。「変数の情報」とは、変数の値そのものであっても、あらかじめ定めた方法で計算するために必要な値でもよい。例えば、ステップＳ１２０では、秘密鍵などの情報を取得する。また、証明装置１００が署名を生成する装置の場合は、証明装置１００が証拠を生成することも含んでいる。
【００１９】
変換部１３０は、ｎ＝１，…，Ｎのすべてに対して、ｎ番目の証明式集合に含まれるすべての証明式について、定数と定数のペアリングのすべてを、定数と変数のペアリングに変換した変換式を生成することで、ｎ番目の変換式集合を生成し、記録部１９０に記録する（Ｓ１３０）。式（１）の場合であれば、ＢｆもしくはＣｆを変数Ｙｆに変換することを意味する。また、移項によって式が変形された場合でも、移項後の表現でのＢｆに対応する定数もしくはＣｆに対応する定数を、変数Ｙｆに変換することを意味する。例えば、
【数３】
2014164285.tif 000005
のように変換する。つまり、変換式では、定数と定数のペアリングが存在しない。以下の説明のために、第１証明式集合の証明式において、変数に変換した定数をＢｉとし、変換後の変数をＹｉとする。また、第２証明式集合の証明式において、変数に変換した定数をＢｊとし、変換後の変数をＹｊとする。つまり、変換部１３０は、証明式のＢｆもしくはＣｆ、または移項後の表現でのＢｆに対応する定数もしくはＣｆに対応する定数を、定数Ｂｉまたは定数Ｂｊとして、変数に変換する。なお、第１証明式集合に対応した変換式集合を第１変換式集合、第２証明式集合に対応した変換式集合を第２変換式集合と呼ぶことにする。また、ｉとｊは対応関係を示す番号であって、第１変換式集合の中で定数から変数に変換された数だけ番号ｉの数は存在し、第２変換式集合の中で定数から変数に変換された数だけ番号ｊの数は存在する。さらに、「集合を生成する」とは、１つ以上の式を何らかの方法でまとまりとして扱えるようにすることを意味しており、同じ集合に属する式を同じテーブルに記録することや、関連付けるための番号を付与することなどを含んでいるが、これらに限定するものではない。
【００２０】
スイッチャー生成部１４０は、スイッチャー式を、ｎ＝１，…，ＮについてＷｎが１またはｇのときのみ成り立つペアリング積の等式と、Ｗ１，…，ＷＮのいずれか１つがｇであり他がすべて１のときには成り立つペアリング積の等式とし、記録部１９０に記録する（Ｓ１４０）。例えば、
ｅ（Ｗ１，Ｗ１／ｇ）＝１，…，ｅ（ＷＮ，ＷＮ／ｇ）＝１        （３）
のＮ個の等式と
【数４】
2014164285.tif 000006
をスイッチャー式とすればよいし、
ｅ（ｇ／Ｗ１，Ｗ１）＝１，…，ｅ（ｇ／ＷＮ，ＷＮ）＝１        （５）
のＮ個の等式と
【数５】
2014164285.tif 000007
をスイッチャー式にしてもよい。
【００２１】
変換変数式生成部１５０は、ｎ＝１，…，Ｎのすべてに対して次の処理を行う。ｎ番目の変換式集合について、変換部１３０で定数Ｂｉから変換された変数Ｙｉごとに、Ｗｎ＝ｇのときにはＹｉ＝Ｂｉでのみ成り立ち、Ｗｎ＝１のときにはＹｉ＝１でのみ成り立つペアリング積の等式を変換変数式として生成し、この変換変数式の集合をｎ番目の変換変数式集合とする（Ｓ１５０）。例えば、
ｅ（Ｂｉ，Ｗｎ）＝ｅ（Ｙｉ，ｇ）        （７）
のように変換変数式を生成すればよいし、
ｅ（Ｂｉ，Ｗｎ）ｅ（Ｙｉ，ｇ−１）＝１        （８）
のように変換変数式を生成してもよい。
【００２２】
ＧＳ証明実行部１６０は、次の処理を行う。スイッチャー式にＷｍ＝ｇ、ｎ≠ｍのＷｎにはＷｎ＝１を割り当て、ｍ番目の変換式集合に含まれるすべての変換式の変数とｍ番目の変換変数式集合に含まれるすべての変換変数式の変数に、証拠から得られる値とＹｉ＝Ｂｉを割り当てる。つまり、証明式でも変数だった変数には証拠から得られる値を割り当て、変換部１３０によって定数から変数に変換された変数にはＹｉ＝Ｂｉを割り当てる。そして、ｍ番目以外のすべての変換式集合に含まれるすべての変換式のすべての変数と、ｍ番目以外のすべての変換変数式集合に含まれるすべての変換変数式の変数にペアリングの結果が１となる値を割り当てる。そして、変数に値が割り当てられたすべてのスイッチャー式、すべての変換式、すべての変換変数式に対してそれぞれＧＳ証明（Groth-Sahai非対話証明）を行う（Ｓ１６０）。なお、「変数にペアリングの結果が１となる値を割り当てる」とは、定数と変数のペアリングの場合には変数の値を１にし、変数と変数のペアリングの場合には少なくとも一方の変数の値を１にすることを意味する。このようにすれば、ペアリングの結果が１となる。
【００２３】
例えば、式（２）が変換式、式（３），（４）がスイッチャー式、式（７）が変換変数式のときについて説明すると、以下のようになる。スイッチャー式ｅ（Ｗｍ，Ｗｍ／ｇ）＝１は、
ｅ（ｇ，ｇ／ｇ）＝１
となり、成り立つ。ｎ≠ｍのときのスイッチャー式ｅ（Ｗｎ，Ｗｎ／ｇ）＝１は、
ｅ（１，１／ｇ）＝１
となり、成り立つ。また、式（４）は、
ｅ（ｇ，ｇ／ｇ）＝１
となるので成り立つ。ｍ番目の変換式集合の変換式は、
【数６】
2014164285.tif 000008
のＵａ，Ｖｂ，Ｘｃに証拠から得られる値を代入した式となり、成り立つ。ｍ番目の変換変数式集合の変換変数式は、
ｅ（Ｂｉ，ｇ）＝ｅ（Ｙｉ，ｇ）
となるので成り立つ。また、ｍ番目以外のすべての変換式集合の変換式は、
【数７】
2014164285.tif 000009
となる。この式では、すべてのペアリングで一方の要素が“１”なので、すべてのペアリングの結果が１となる。よって、右辺も左辺も１となり、成り立つ。ｍ番目以外のすべての変換変数式集合の変換変数式は、
ｅ（Ｂｉ，１）＝ｅ（１，ｇ）
となり、やはり右辺も左辺も１となるので成り立つ。
【００２４】
つまり、ｍが１〜Ｎのいずれの値であったとしても、変数を割り当てたすべてのスイッチャー式、すべての変換式、すべての変換変数式は成り立つ。そして、これらの等式に対してＧＳ証明を行うので、すべての式が成り立っていることを証明できる。
【００２５】
証明出力部１７０は、すべてのスイッチャー式、すべての変換式集合、すべての変換変数式集合、およびＧＳ証明のすべての結果の情報を出力する（Ｓ１７０）。具体的には、ネットワーク９００を介して検証装置２００に送信してもよいし、可搬タイプの記録媒体に記録してもよい。
【００２６】
次に検証装置２００の処理について説明する。検証対象取得部２１０は、すべての証明式集合に含まれるすべての証明式に含まれるすべての定数の情報である証明対象情報を取得し、記録部２９０に記録する（Ｓ２１０）。この処理は、証明装置１００の証明対象取得部１１０の処理と同じである。
【００２７】
証明入力部２２０は、証明装置１００が出力したすべてのスイッチャー式、すべての変換式集合、すべての変換変数式集合、ＧＳ証明のすべての結果の情報を取得する（Ｓ２２０）。取得の方法は、ネットワーク９００を介してでもよいし、記録媒体を介してでもよい。
【００２８】
ＧＳ証明確認部２３０は、すべてのスイッチャー式、すべての変換式、すべての変換変数式に対するＧＳ証明の結果を確認する（Ｓ２３０）。この確認によって、すべての式が成り立っていることは確認できる。
【００２９】
対象確認部２４０は、すべてのスイッチャー式、すべての変換式、すべての変換変数式が、証明対象情報に対応していることを確認する（Ｓ２４０）。変換変数式集合を確認することで、変換式の変数の中で、証明式でも変数の変数と変換部１３０で定数から変数に変換された変数とを区別できる。そして、変換式集合を確認することで、変換式集合と変換変数式集合が、証明式集合に対応していることが確認できる。
【００３０】
本発明の証明システムは、このような処理を行うので、検証装置２００では、証明装置１００がどの証明式集合に対する証拠を保有しているのか分からないようにしながら、証明装置１００が少なくとも１つの証明式集合に対する証拠を保有していることを証明できる。このような手法を用いれば、例えば署名システムのセキュリティ強化も可能である。また、２つの証明式集合に限定するのではなく、２つ以上の任意の数の証明集合に対しても適用できることで、本発明の応用範囲が広がる。例えば、あるグループ内の１人からの署名を受け取った人は、だれから受け取ったかを明らかにすることなく、少なくともグループ内の誰かから署名を受け取ったことを証明できるようになる。さらに、本発明の証明システムでは、ペアリングの積で表現された証明式の形の制限はない。また、本発明の証明システムによれば、証明式中の定数と定数のペアリングに対してのみ変換の処理を行い、定数から変数への変換ごとに１つの変換変数式（ペアリングを含む式）を追加するだけである。したがって、証明式中のすべてのペアリングに対して変換の処理を行うことを前提としている非特許文献２の方法よりも、追加しなければならないペアリングを含む式の数を少なくできる。
【００３１】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００３２】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００３３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００３４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００３５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００３６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００３７】
本発明は、署名システムのセキュリティ強化や署名を応用したシステムなどに利用できる。
【符号の説明】
【００３８】
１００  証明装置                        １１０  証明対象取得部
１２０  証拠取得部                      １３０  変換部
１４０  スイッチャー生成部              １５０  変換変数式生成部
１６０  ＧＳ証明実行部                  １７０  証明出力部
１９０、２９０  記録部                  ２００  検証装置
２１０  検証対象取得部                  ２２０  証明入力部
２３０  ＧＳ証明確認部                  ２４０  対象確認部
９００  ネットワーク
【図１】
2014164285.tif 000012
【図２】
2014164285.tif 000013
【図３】
2014164285.tif 000014