論文翻訳: Compact Multi-Signatures for Smaller Blockchains

2019年10月15日 2018年の論文 #マルチ署名

Dan Boneh ¹ , Manu Drijvers ^2,3 , and Gregory Neven ²
¹ Stanford University
dabo@cs.stanford.edu
² IBM Research – Zurich
{mdr,nev}@zurich.ibm.com
³ ETH Zurich

Abstract

我々は新しい機能性を提供する新しいマルチ署名スキームを構築する。我々のスキームは Bitcoin ブロックチェーンのサイズを削減するように設計されているがマルチ署名が必要な多くの設定で役立つだろう。すべての構築は署名圧縮と公開鍵集約の両方を備えている。従って、多くの当事者が共通のメッセージ $m$ に署名したことを検証するために、検証者は短いマルチ署名、公開鍵の短い集約、およびメッセージ $m$ のみを必要とする。我々は Schnorr 署名と BLS 署名から派生した新しい構造を提供する。我々の構築は単純な公開鍵モデルに基づいているため、ユーザは秘密鍵の知識や所有を証明する必要はない。

さらに、我々は最初の短い accountable-subgroup マルチ署名 (ASM) スキームを構築する。ASM スキームでは $n$ 個の当事者の任意の部分集合 $S$ があるメッセージ $m$ に対する署名を生成でき、その有効な署名からはどの部分集合が署名したかが分かる (従って部分集合 $S$ は $m$ に署名する責任 (accountable) がある)。我々は $S$ の記述において署名サイズがたった $O(k)$ ビットとなる最初の ASDM スキームを構築した。ここで $k$ はセキュリティパラメータである。同様に、集約公開鍵は $n$ とは独立した $O(k)$ ビットのみである。署名プロセスは対話的ではない。我々の ASM スキームは非常に実用的で、任意の (多項サイズ) $t$ と $s$ に対して $t$ -of- $n$ マルチシグビットコインアドレスから資金を支払うために必要なデータの圧縮に適している。

Abstract
1 導入
2 予備知識
3 ペアリングによる鍵集約を有するマルチ署名
4 Accountable-Subgroup マルチ署名
5 A Scheme from Discrete Logarithms
1. 5.1 離散対数スキームの説明
2. 5.2 セキュリティ証明
6 所有の証明を有するスキーム
参照
A 所有の証明を有するスキームのセキュリティ証明
1. A.1 $\mathcal{MSP\mathcal{-}pop}$ と $\mathcal{AMSP\mathcal{-}pop}$ に対するセキュリティ証明
2. A.2 $\mathcal{ASM\mathcal{-}pop}$ に対するセキュリティ証明
翻訳抄

1 導入

それぞれが署名スキームのための鍵ペアを個別に生成する $n$ 個の当事者について考える。その後に全ての $n$ 当事者たちは同一のメッセージ $m$ に署名しようと考えている。マルチ署名スキーム [28, 38] は $n$ 人の署名者たちが $m$ 上で短い署名 $\sigma$ を共同で生成できるプロトコルであり、 $\sigma$ により $n$ 人の全てが $m$ に署名したことを検証者に納得させる。具体的には、検証アルゴリズムの入力は $n$ 個の公開鍵、メッセージ $m$ およびマルチ署名 $\sigma$ として与えられ、アルゴリズムは $\sigma$ を受け入れるか拒否する。マルチ署名 $\sigma$ は短くなければならない; その長さは署名者数 $n$ には依存しない。次のセクションではこの概念をより正確に定義する。ここでそのようなスキーム [38] に対する標準的なセキュリティモデルも示す。安全なマルチ署名は Schnorr 署名 ([9] など)、BSL 署名 ([10] など) およびセクション 1.5 で詳述するような多くのスキームから構築されてる。

集約署名スキーム [12] と呼ばれるより一般的な概念では、 $n$ 当事者たちがそれぞれ異なるメッセージに署名するが、それらの署名は全て単一の短い署名 $\sigma$ に集約することができる。前述と同様にこの短い署名は全ての署名者が指定されたメッセージに署名したことを検証者に納得させる。

Bitcoin への適用. マルチ署名と集約署名を使用して Bitcoin ブロックチェーン [40] のサイズを縮小することができる。最近の研究では Maxwell, Poelstra, Seurin and Wuille [35] はマルチ署名を使用して Bitcoin Multisig アドレスに関連づけられたトランザクションデータを縮小することを提案している。概念的に Multisig アドレスとは $n$ 個の公開鍵 $pk_1,\ldots,pk_n$ と、しきい値と呼ばれるある数値 $t \in \{1,\ldots,n\}$ のハッシュである (詳細は [2, 35] 参照)。これらのアドレスに関連づけられた資金を送金するためには、 $n$ 個全ての公開鍵 $pk_1,\ldots,pk_n$ に続いて、それらのうち $t$ 個の公開鍵による有効な署名を含むトランザクションを作成し、そのトランザクションをブロックチェーンに書き込む。署名されるメッセージは $t$ 個の署名全てで同じ、つまりトランザクションデータに対してである。

実際には、多くの場合 Multisig アドレスは $t=n$ を使用するため、このアドレスから資金を送金するには $n$ 個全ての署名を必要とする。この場合、 $n$ 個の署名全てをマルチ署名スキームを使用して単一の短い署名に圧縮することができる。これによりトランザクション全体のサイズが縮小されブロックチェーンに書き込まれるデータの量が削減される。このアプローチでは全ての $t$ -size の部分集合を列挙することによって、 $\binom{n}{t}$ が小さければ、 $t \lt n$ で機能するようにすることができる [35, Section 5.2]。マルチ署名を使用してマルチ入力トランザクションを圧縮することもできるが、単純化のため Multisig アドレスにのみ焦点を当てる。

依然として我々は $n$ 個の公開鍵をブロックチェーンに書き込む必要があるため、署名を圧縮してもそれほど節約はできないことに注意。幸いなことにこれに対する解決策も存在する。Maxwell ら [35] は Bellare and Neven [9] の研究に基づいて公開鍵集約もサポートする Schnorr ベースのマルチ署名スキームを構築している。つまり、検証者は $n$ 個すべての公開鍵の明示的なリストの代わりに、短い集約公開鍵のみを必要とする。このアプローチでは $n$ -of- $n$ Multisig アドレスは単純に短い集約公開鍵のハッシュであり、支払いトランザクションでブロックチェーンに書き込まれるデータは単一の短い集約公開鍵、単一の短い圧縮された署名、そしてメッセージである。このデータは $n$ 個の署名者全員がトランザクションに署名したことを検証者に確信させるのには十分である。これはブロックチェーンに書き込まれるデータの量を $1/n$ に縮小する。

Maxwell らはこのプリミティブを公開鍵集約によるマルチ署名スキームと呼んでいる。彼らの署名プロトコルは署名者間の 2 ラウンドの通信を必要とし、もう一つの ([8] で導入された) 離散対数仮定を想定してスキームのセキュリティを証明している。しかし、最近の研究 [21] ではセキュリティの証明にギャップがありこの仮定の下ではセキュリティを証明できないことが示されている。彼らのスキームが別の仮定の下で、または一般的な群モデルで安全であると証明できるかどうかは現在のところ未解決問題である。

セクション 5 では Maxwell らによるスキームの修正を示し、標準の離散対数仮定の下で安全であることを証明している。我々の $\mathcal{MSDL}$ スキームはオリジナルのスキームの全ての利点を保持し、特に、同じ鍵集約技術を使用しているが、署名プロトコルに 1 ラウンドを追加している。

1.1 ペアリングを使用したより良い構築

我々の主な結果は [35] の Schnorr 署名スキームを BLS 署名 [13] に置き換えることで遙かに改善できることを示している。結果のスキームは Bitcoin に非常に良く適合しているが、マルチ署名が必要とされているケースでも非常に便利である。

新しい構成を説明するためにまず BLS 署名スキームとその集約メカニズムを簡単に確認する。スキームに必要なものは (1) 素数位数 $q$ の群 $\mathbb{G}_1$ , $\mathbb{G}_2$ , $\mathbb{G}_t$ において効率的に計算可能な非縮退ペアリング $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_t$ 、ここで $g_1$ と $g_2$ をそれぞれ $\mathbb{G}_1$ と $\mathbb{G}_2$ の生成元とする。および (2) ハッシュ関数 ${\sf H}_0: \mathcal{M} \to \mathbb{G}_1$ である。これで BLS 署名スキームは以下のように機能する:

鍵生成: $sk \overset{s}{\leftarrow} \mathbb{Z}_q$ をランダムに選択し $(pk,sk)$ を出力する。ここで $pk \leftarrow g_2^{sk} \in \mathbb{G}_2$ である。
${\rm Sign}(sk,m): \sigma \leftarrow {\sf H}_0(m)^{sk} \in \mathbb{G}_1$ を出力する。
${\rm Verify}(pk,m,\sigma):$ もし $e(\sigma,g_2) \overset{?}{=} e({\sf H}_0(m),pk)$ であれば "accept" を出力し、そうでなければ "reject" を出力する。

この署名スキームはシンプルな署名集約手続きをサポートしている。 $i=1,\ldots,n$ に対して三値 $(pk_i,m_i,\sigma_i)$ が与えられたとき $\begin{equation} \sigma \leftarrow \sigma_1 \cdots \sigma_n \in \mathbb{G}_1 \label{aggregated_signature} \end{equation}$ を計算することで誰でも署名 $\sigma_1,\ldots,\sigma_n \in \mathbb{G}_1$ を確信性のある短い集約署名 $\sigma$ に集約することができる。この集約署名 $\sigma \in \mathbb{G}_1$ を検証するためには: $\begin{equation} e(\sigma,g_2) = e({\sf H}_0(m_1),pk1) \cdots e({\sf H}_0(m_n), pk_n) \label{verify_aggregated_signature} \end{equation}$ を検証する。検証には $i=1,\ldots,n$ に対する全ての $(pk_i,m_i)$ が必要であることに注意。もし署名されている全てのメッセージが同一 ( $m_1=\ldots=m_n$ ) であれば検証関係 ( $\ref{verify_aggregated_signature}$ ) は 2 つのペアリングのみを必要とするより単純な検証に削減される: $\begin{equation} e(\sigma,g_2) \overset{?}{=} e\left({\sf H}_0(m_1), pk_1 \cdots pk_n \right) \label{single_m_aggsig} \end{equation}$ さらに、検証者は短い公開鍵 $apk := pk_1 \cdots pk_n \in \mathbb{G}_2$ のみを与えられれば良い。

不正公開鍵攻撃 (rogue public-key attack). ( $\ref{aggregated_signature}$ ) の単純な署名集約方法はそれ自体では安全ではないため拡張する必要がある。理由を理解するために以下の不正公開鍵攻撃について検討する: 攻撃者は不正な公開鍵 $pk_2 := g_2^\alpha \cdot (pk_1)^{-1} \in \mathbb{G}_2$ を登録する。ここで $pk_1 \in \mathbb{G}_2$ は正常なユーザ Bob の公開鍵であり、 $\alpha \overset{\rm S}{\leftarrow} \mathbb{Z}_q$ は攻撃者によって選ばれたものである。攻撃者は集約署名 $\sigma := {\sf H}_0(m)^\alpha$ を提示することにより攻撃者自身と Bob の両者があるメッセージ $m \in \mathcal{M}$ に署名したと主張することができる。つまりこの署名は以下のように $pk_1$ による署名と $pk_2$ による署名とを集約したものとして検証される。 $e(\sigma,g_2) = e({\sf H}_0(m)^\alpha,g_2) = e({\sf H}_0(m),g_2^\alpha) = e({\sf H}_0(m), pk_1 \cdot pk_2)$ 従ってこの $\sigma$ は ( $\ref{single_m_aggsig}$ ) の条件を満たしており、Bob がメッセージ $m$ に署名していないにもかかわらず、事実上攻撃者は Bob を $m$ にコミットさせることができる。

防衛策. 不正公開鍵攻撃に対して 2 つの標準的な防衛方法がある:

全てのユーザに対して対応する秘密鍵の知識または所有権を証明するよう要求する [10, 32, 47]。ただしこれは [7, 47] で論議されているように実際に実施するには難しく、[35] で述べられているように暗号通貨への適用にはうまく適合しない。
集約されるメッセージが明確であることを要求する [12, 7]。つまり検証者は明確でないメッセージの集約署名を拒否する。これは不正鍵攻撃を防ぐのに十分である。さらに、署名前に全てのメッセージに常に公開鍵を付加することによってメッセージの明確性を強化できる。ただし、全てのメッセージが区別されるようになっているため、共通メッセージ $m$ の署名を集約する場合 ( $\ref{single_m_aggsig}$ ) のように公開鍵集約を利用できない。

1.2 ペアリングに基づく結果

セクション 3 では、欠点なしに前述の両防衛策の全ての利点を得る、不正公開鍵攻撃に対する異なる防衛策を提案する。特に、マルチ署名スキームは公開鍵の集約と ( $\ref{single_m_aggsig}$ ) のような高速な検証をサポートしている。さらにこのスキームはプレーンな公開鍵モデルで安全であるため、ユーザは秘密鍵の知識や所有権を証明する必要がない。このスキームには 2 つの追加の有用な特性がある:

このスキームは複数の署名集合を 1 つずつ検証するよりも高速にバッチとして検証できるバッチ検証をサポートしている。
セクション 3.3 では異なるメッセージに複数のマルチ署名がある場合 ( $\ref{aggregated_signature}$ ) を使用して全てのマルチ署名を単一の短い署名に集約できることを示す。これは多くのトランザクションに渡って署名を集約しブロックチェーン上のデータをさらに圧縮するために利用できる。

我々の構築は [9] と [35] で開発されたアプローチに基づいており、Schnorr マルチ署名を不正公開鍵攻撃から保護する。

BLS ベースのマルチ署名スキーム $\mathcal{MSP}$ は Schnorr マルチ署名よりも遙かに扱いやすい。Schnorr を振り返ると集約は署名時にのみ行われ、署名者間のマルチラウンドプロトコルが必要である。我々の新しいスキームでは、全ての署名が作成され署名者が利用できなくなった後でも単純な乗算で集約を公開することができる。具体的に Bitcoin のコンテキストでは、Multisig アドレスの背後に居る全ての署名者が、全ての署名を一つの署名に集約する単一の当事者に署名を送信できることを意味する。インタラクションは不要であり当事者全員が同時にオンラインである必要はない。さらに、異なるトランザクションのマルチ署名をさらに単一の集約署名に圧縮してさらにスペースを節約する集約マルチ署名スキーム $\mathcal{AMSP}$ について説明する。

Accountable-Subgroup マルチ署名. 当事者のそれぞれが独立した署名鍵ペアを生成する $n$ 個の参加者について再検討する。ASM により $n$ 当事者たちの部分集合 $S$ が共同でメッセージ $m$ に署名できるため、有効な署名は署名を生成した部分集合 $S$ に関係する; 従って $S$ は $m$ に署名する責任がある。ASM の検証者は入力として $n$ 当事者全てを表す (集約) ASM 公開鍵、集合 $S \subseteq \{1,\ldots,n\}$ 、集合 $S$ によって生成されたマルチ署名、そしてメッセージ $m$ をを与えられる。その署名を受け入れるか拒否する。セキュリティは署名者 $S' \not\supseteq S$ の集合が、 $S$ によって生成されたかのように受け入れられる署名を発行できないことを保証する必要がある。我々はセクション 4 で ASM とそれらのセキュリティ特性について正確に定義する。この概念は過去に Micali ら [38] によって研究された。

任意のセキュアな署名スキームは愚直な ASM を提供する。つまり、全ての当事者が独立して署名鍵ペアを生成し、メッセージ $m$ に対する集合 $S$ による署名は $S$ のメンバーによる全ての署名の単純な連結である。セキュリティパラメータ $\kappa$ に対してこの愚直な ASM の公開鍵サイズは $O(n\times\kappa)$ ビットであり、署名サイズは $O(|S|\times\kappa)$ ビットである。

我々の $\mathcal{ASM}$ スキームでの署名サイズは、集合 $S$ の記述の背後に $O(\kappa)$ ビットのみであり、公開鍵が $n$ に依存せず $O(\kappa)$ のみとなる最初の ASM である。具体的には、マルチ署名は $S$ の記述と合わせた 2 つの群元のみであり、公開鍵は単一の群元である。署名プロトコルは非インタラクションだが、最初の鍵生成にはすべての $n$ 署名者間で単純な 1 ラウンドのプロトコルを必要とする。

これがどのように使用できるかを確認するには Bitcoin の $n$ -of $n$ Multisig アドレスを再考しよう。公開鍵集約を用いたマルチ署名は、このアドレスから資金を支払う際にブロックチェーンに書き込まれるデータ量を (現在の Bitcoin で行われている $O(\kappa\times n)$ ビットとは対照的に) $O(\kappa)$ ビットのみに削減することを既に見て来た。課題は $t\lt n$ となる $t$ -of- $n$ Multisig アドレスに対して同様のことを行うことである。我々の ASM は完全なソリューションを提供する; ブロックチェーンに書き込まれる唯一の情報は、 $S$ の記述に加えて 1 つは公開鍵用で 2 つが署名用である追加の 3 つの群元である。 $\binom{n}{t}$ が指数関数である場合でも同様である。これは現在 Bitcoin が採用している愚直な線形サイズ ASM スキームより遙かに優れている。

1.3 所有の証明

最後に、セクション 6 で我々は全てのユーザが自分の秘密鍵の所有の証明 (proof of possession) (PoP) を提供する必要のある設定に我々の全てのスキーム、BLS ベースと Schnorr ベースの両方を適用できることを確認する。所有の証明は個々の公開鍵のサイズを大きくするが、個々の鍵サイズがそれほど重要でないアプリケーションも存在する。例えば Bitcoin の Multisig アドレスはブロックチェーンに集約公開鍵を保存する必要があるだけだが、個々の公開鍵は署名者のみに関係し、チェーン外に保持するか、一度検証した後は破棄できる。他のアプリケーションは、鍵が一度検証されその後の任意の組み合わせで使用できる署名ノードの静的な集合、多かれ少なかれ、を含むことができる。

PoP の変種は主なスキームに対していくつかの利点を提供する。例えば公開鍵の積またはハッシュを (multi-exponentiation ではなく) 集約公開鍵として単純に使用し、基礎となるセキュリティの前提に対してより厳密なセキュリティ証明を持つ。

1.4 効率比較

Table 1 はこの構成によって Bitcoin ブロックチェーンのサイズがどの程度削減されるかを示している。ペアリングベースのスキーム $\mathcal{AMSP}$ と離散対数ベースのスキーム $\mathcal{MSDL}$ の両方は、現実的なパラメータを想定して、現在展開されているソリューションと比較して Bitcoin ブロック内の全てのトランザクションを承認するために必要なスペースは 20% 未満であった。表からはすぐには読み取れないが、accountable-subgroup マルチ署名スキーム $\mathcal{ASM}$ は $\binom{n}{t}$ が非常に大きい時に $t$ -of- $n$ 署名に対して最も有用である。具体的には 50-out-of-100 マルチシグウォレットに対して現在展開されている Bitcoin ソリューションには $\mathcal{ASM}$ スキームの 30 倍のスペースが必要となる。それ以外のスキームは [35, セクション 5.2] で概説されているように Merkle tree [37] を使用したしきい値署名をサポートしている。この方法は、例えば 50-of-100 しきい値スキームでは実行不可能である。

**Table 1**. 全てが $n$ -out-of- $n$ マルチシグウォレットからの、それぞれ $inp$ 入力を持った $tx$ 個のトランザクションを含んでいる Bitcoin ブロックチェーン内のブロックを承認するために必要なスペースの比較。ここで $|\mathbb{G}|$ は群のある元を表すために必要なスペースを示している。4 番目の列は、Bitcoin, ${\sf MuSig}$ , $\mathcal{MSDL}$ スキーム ( $|\mathbb{G}|$ =32B, $|\mathbb{Z}_q|$ =32B) に secp256k1 [18] を使用し、ペアリングベースの $\mathcal{MSP}$ , $\mathcal{AMSP}$ , $\mathcal{ASM}$ スキーム ( $|\mathbb{G}_1|$ =32B, $|\mathbb{G}_2|$ =48B, $|\mathbb{Z}_q|$ =32B) に BLS381 [6] を使用してサンプルパラメータ ( $tx=1500$ , $inp=3$ , $n=3$ ) を選択することによって得られた Bitcoin ブロックの具体的なバイト数を表している。右端の列では、"linear" は $t$ -of- $n$ しきい値が $n$ と $t$ で線形となる鍵と署名サイズでサポートされることを示しており、"small" はサポートが $\binom{n}{t}$ が小さい場合に制限されることを、そして "any" は任意の (多項式サイズ) $t$ と $n$ のサポートをそれぞれ示している。
	連結した公開鍵サイズ	連結した署名サイズ	トータルサイズ (kB)	しきい値サポート
Bitcoin	$tx \cdot inp \cdot n \cdot \|\mathbb{G}\|$	$tx \cdot inp \cdot n \cdot 2 \cdot \|\mathbb{Z}_q\|$	1296	linear
${\sf MuSig}$ ([35])	$tx \cdot inp \cdot \|\mathbb{G}\|$	$tx \cdot (\|\mathbb{G}\|+\|\mathbb{Z}_q\|)$	240	small
$\mathcal{MSDL}$ (セクション5)	$tx \cdot inp \cdot \|\mathbb{G}\|$	$tx \cdot (\|\mathbb{G}\|+\|\mathbb{Z}_q\|)$	240	small
$\mathcal{MSP}$ (セクション3.1)	$tx \cdot inp \cdot \|\mathbb{G}_2\|$	$tx \cdot \|\mathbb{G}_1\|$	360	small
$\mathcal{AMSP}$ (セクション3.3)	$tx \cdot inp \cdot \|\mathbb{G}_2\|$	$\|\mathbb{G}_1\|$	216	small
$\mathcal{ASP}$ (セクション4)	$tx \cdot inp \cdot \|\mathbb{G}_2\|$	$tx \cdot inp \cdot (\|\mathbb{G}_1\| + \|\mathbb{G}_2\|)$	864	any

マルチ署名は RSA [28, 42, 45, 29]、離散対数 [25, 31, 26, 27, 19, 43, 16, 38, 17, 9, 3, 4, 34, 35]、ペアリング [10, 32, 47, 11, 30] および格子 (lattice) [5] に基づいて広く研究されている。不正公開鍵攻撃に対する防衛策は離散対数とペアリング [27, 39, 38, 12, 9, 7, 47] に基づくマルチ署名スキームのコンテキストで常に主な関心事であり、離散対数ベースのマルチ署名システムに複雑度が追加された主要な理由である。集約署名 [12, 24, 1] は異なるメッセージ上の異なる署名者を共に圧縮するル署名と密接に関連する概念である。連続集約署名 (sequential aggregate signature) [33, 32, 41, 14, 23] は署名者が代わる代わる自身の署名を集約に追加する変種である。署名圧縮に加えて公開鍵集約の概念は [35] とこの研究に至るまでプレーンな公開鍵モデルでは明示的に議論されていない。この概念によりマルチ署名の検証に必要なデータの合計長が大幅に削減される。

2 予備知識

2.1 双線形群

入力としてセキュリティパラメータ $\kappa$ を取り、乗法群 $(g,\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_t,e,g_1,g_2)$ の詳細を出力する双線形群生成元を $\mathcal{g}$ とする。ここで $\mathbb{G}_1$ , $\mathbb{G}_2$ および $\mathbb{G}_t$ は素数位数 $q$ を持つ群であり、 $e$ は効率的な非縮退双線形写像 $e:\mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_t$ 、また $g_1$ と $g_2$ はそれぞれ群 $\mathbb{G}_1$ と $\mathbb{G}_2$ の生成元である。

2.2 計算問題

定義 1 (離散対数問題) . 素数位数 $q$ の群 $\mathbb{G}=\langle g \rangle$ に対し敵対者 $\mathcal{A}$ の ${\sf Adv}_{\mathbb{G}}^{\rm dl}$ を ${\rm Pr}\left[ y = g^x: y \overset{s}{\leftarrow} \mathbb{G}, x \overset{s}{\leftarrow} \mathcal{A}(y) \right]$ と定義する。ここでこの確率は $\mathcal{A}$ のランダム選択と $y$ のランダム選択を取る。もし $\mathcal{A}$ が離散対数問題を最大時間 $\tau$ で実行し ${\sf Adv}_{\mathbb{G}}^{\rm dl} \ge \epsilon$ であれば、 $\mathcal{A}$ は離散対数問題を $(\tau,\epsilon)$ -break する。もしそのような敵対者が存在しないのであれば離散対数は $(\tau,\epsilon)$ -困難である。

定義 2 (Computational co-Diffie-Hellman 問題) . 素数位数 $q$ を持つ群 $\mathbb{G}_1=\langle g_1 \rangle$ 、 $\mathbb{G}_2=\langle g_2 \rangle$ に対し敵対者 $\mathcal{A}$ の ${\sf Adv}_{\mathbb{G}_1,\mathbb{G}_2}^{\sf co\mbox{-}CDH}$ を ${\rm Pr}\left[y=g_1^{\alpha\beta} : (\alpha,\beta) \overset{s}{\leftarrow}\mathbb{Z}_q^2, y \leftarrow \mathcal{A}(g_1^\alpha,g_1^\beta,g_2^\beta)\right]$ と定義する。ここでこの確率は $\mathcal{A}$ のランダム選択と $(\alpha,\beta)$ のランダム選択を取る。もし $\mathcal{A}$ が ${\sf co\mbox{-}CDH}$ 問題を最大時間 $\tau$ で実行し ${\sf Adv}_{\mathbb{G}_1,\mathbb{G}_2}^{\sf co\mbox{-}CDH} \ge \epsilon$ であれば、 $\mathcal{A}$ は ${\sf co\mbox{-}CDH}$ 問題を $(\tau,\epsilon)$ -break する。もしそのような敵対者が存在しないのであれば ${\sf co\mbox{-}CDH}$ は $(\tau,\epsilon)$ -困難である。

定義 3 (Computational \(\varphi)-co-Diffie-Hellman 問題) . 素数位数 $q$ を持つ群 $\mathbb{G}_1=\langle g_1 \rangle$ 、 $\mathbb{G}_2=\langle g_2 \rangle$ に対し、入力 $g_2^\alpha \in \mathbb{G}_2$ を取り $g_1^\alpha \in \mathbb{G}_1$ を返すオラクルを $\mathcal{O}^\varphi(\cdot)$ とする。敵対者 $\mathcal{A}$ の ${\sf Adv}_{\mathbb{G}_1,\mathbb{G}_2}^{\sf \varphi\mbox{-}co\mbox{-}CDH}$ を ${\rm Pr}\left[y=g_1^{\alpha\beta} : (\alpha,\beta) \overset{s}{\leftarrow}\mathbb{Z}_q^2, y \leftarrow \mathcal{A}^{\mathcal{O}^\varphi(\cdot)}(g_1^\alpha,g_1^\beta,g_2^\beta)\right]$ と定義する。ここでこの確率は $\mathcal{A}$ のランダム選択と $(\alpha,\beta)$ のランダム選択を取る。もし $\mathcal{A}$ が ${\sf \varphi\mbox{-}co\mbox{-}CDH}$ 問題を最大時間 $\tau$ で実行し ${\sf Adv}_{\mathbb{G}_1,\mathbb{G}_2}^{\sf \varphi\mbox{-}co\mbox{-}CDH} \ge \epsilon$ であれば、 $\mathcal{A}$ は ${\sf \varphi\mbox{-}co\mbox{-}CDH}$ 問題を $(\tau,\epsilon)$ -break する。もしそのような敵対者が存在しないのであれば ${\sf \varphi\mbox{-}co\mbox{-}CDH}$ は $(\tau,\epsilon)$ -困難である。

2.3 一般化された分岐補題

Pointcheval and Stern [46] の分岐補題 (forking lemma) はランダムオラクルモデルの Schnorr 署名 [46] に基づくスキームのセキュリティを証明するために一般的に使用されている。彼らの補題はより広い分類に適用するために後に一般化されている [9, 3]。Bagherzandi, Cheon and Jaracki [3] によるバージョンをここで反復する。

入力 $in$ でランダムオラクル ${\sf H}:\{0,1\}^* \to \mathbb{Z}_q$ と相互作用するアルゴリズムを $\mathcal{A}$ とする。 $f=(\rho,h_1,\ldots,h_{q_{\sf H}})$ を $\mathcal{A}$ の実行に含まれるランダム性とする。ここで $\rho$ は $\mathcal{A}$ のランダムテープ (確率的チューリングマシンにおけるランダムビットの刻印されたテープ)、 $h_i$ は $\mathcal{A}$ の ${\sf H}$ に対する $i$ 番目のクエリーの応答、そして $q_{\sf H}$ はランダムオラクルクエリーの最大数である。そのようなベクトル $f$ の全てを $\Omega$ とし $f |_i = (\rho,h_1,\ldots,h_{i-1})$ とする。もしペア $(J,\{out_j\}_{j\in J})$ を出力すれば、我々は $\mathcal{A}$ の入力 $in$ とランダム性 $f$ での実行 ( $\mathcal{A}(in,f)$ と示す) を成功と見なす。ここで $J$ は $\{1,\ldots,q_H\}$ の空ではない部分集合の多重集合 (multi-set) であり、 $\{out_j\}_{j\in J}$ はサイド出力 (?) の多重集合である。 $J=\emptyset$ を出力したとき $\mathcal{A}$ は失敗したという。 $\mathcal{A}(in,f)$ が新鮮なランダム性 $f \overset{s}{\leftarrow} \Omega$ と入力ジェネレータ ${\sf IG}$ によって生成された入力 $in \overset{s}{\leftarrow} {\sf IG}$ に対して成功する確率を $\epsilon$ とする。

与えられた入力 $in$ に対して、一般化された分岐アルゴリズム $\mathcal{GF_A}$ は以下のように定義される:

\mathcal{GF_A}(in)

f=(\rho,h_1,\ldots,h_{q_H}) \overset{s}{\leftarrow} \Omega

(J, \{out_j\}_{j\in J}) \leftarrow \mathcal{A}(in,f)

J = \emptyset

then output fail
Let

J = \{j_1,\ldots,j_n\}

such that

j_1 \le \ldots \le j_n

For

i = 1, \ldots, n

succ_i \leftarrow 0

;

k_i \leftarrow 0

;

k_{\rm max} \leftarrow 8nq_H/\epsilon\cdot \ln(8n/\epsilon)

Repeat until

succ_i = 1

k_i \gt k_{\rm max}

f'' \overset{s}{\leftarrow} \Omega

such that

f'|_{j_i} = f|_{j_i}

Let

f'' = (\rho, h_1, \ldots, h_{j_i-1}, h''_{j_i}, \ldots, h''_{q_H})

(J'', \{out''_j\}_{j \in J''} \leftarrow \mathcal{A}(in,f'')

h''_{j_i} \neq h_{j_i}

and

J'' \neq \emptyset

and

j_i \in J''

then

out'_{j_i} \leftarrow out''_{j_i}

;

succ_i \leftarrow 1

succ_i = 1

for all

i = 1, \ldots, n

Then output

(J, \{out_j\}_{j \in J}, \{out'_j\}_{j \in J})

else output fail

fail を出力しなければ $\mathcal{GF_A}$ は成功すると言う。Bagherzandi らは分岐アルゴリズムの次の補題を証明した。

補題 1 (一般化された分岐補題 [3]) . ${\sf IG}$ をランダム化アルゴリズム、 $\mathcal{A}$ を、確率 $\epsilon$ で成功する最大 $q_H$ のランダムオラクルクエリーの作成を時間 $\tau$ で実行するランダム化アルゴリズムとする。 $q \gt 8nq_H/\epsilon$ の場合、 $\mathcal{GF_A}(in)$ は最大で $\tau \cdot 8n^2q_H/\epsilon \cdot \ln(8n/\epsilon)$ で実行され、少なくとも $\epsilon/8$ の確率で成功する。ここで確率は $in \overset{s}{\leftarrow} {\sf IG}$ の選択と $\mathcal{GF_A}$ のコインを超えている。

2.4 マルチ署名と集約マルチ署名

我々は Bellare and Neven [9] に従いマルチ署名スキームをアルゴリズム ${\sf Pg}$ , ${\sf Kg}$ , ${\sf Sign}$ , ${\sf KAg}$ および ${\sf Vf}$ として定義する。信頼済み当事者はシステムパラメータ $par \leftarrow {\sf Pg}$ を生成する。それぞれの署名者は鍵ペア $(pk,sk) \overset{s}{\leftarrow} {\sf Kg}(par)$ を生成し、署名者はそれぞれインタラクティブなアルゴリズム ${\sf Sign}(par,\mathcal{PK},sk,m)$ を呼び出すことでメッセージ $m$ に集合的に証明することができる。ここで $\mathcal{PK}$ は署名者の公開鍵の集合、 $sk$ は署名者の個別の秘密鍵である。プロトコルの最後に各署名者は署名 $\sigma$ を出力する。公開鍵集合 $\mathcal{PK}$ を入力に取るアルゴリズム ${\sf KAg}$ は単一の集約公開鍵 $apk$ を出力する。検証者は署名が無効か有効かをそれぞれ示す 0 または 1 を出力する ${\sf Vf}(par,apk,m,\sigma)$ を実行することで、集約公開鍵 $apk$ の下でメッセージ $m$ 上の署名 $\sigma$ の有効性を検証することができる。

マルチ署名スキームは完全性を満たしている必要がある。つまり任意の $n$ に対して、任意の $i=1,\ldots,n$ で $(pk_i,sk_i) \leftarrow {\sf Kg}(par)$ を持っており、任意のメッセージ $m$ に対して全ての署名者に ${\sf Sign}(par, sk_i, m)$ を入力した場合、各署名者は ${\sf Vf}(par, {\sf KAg}(par,\{pk_i\}_{i=1}^n), m, \sigma) = 1$ となるような署名 $\sigma$ を出力するだろう。次に、マルチ署名スキームは偽造不可能性を満たす必要がある。マルチ署名スキーム $\mathcal{AMS} = ({\sf Pg}, {\sf Kg}, {\sf Sign}, {\sf KAg}, {\sf Vf})$ の偽造不可能性は 3 段階のゲームで定義される。

Setup. 挑戦者はパラメータ $par \leftarrow {\sf Pg}$ とチャレンジ鍵ペア $(pk^*,sk^*) \overset{s}{\leftarrow} {\sf Kg}(par)$ を生成する。公開鍵 $\mathcal{A}(par,pk^*)$ で攻撃者を実行する。

Signature queries. $\mathcal{A}$ は $pk^* \in \mathcal{PK}$ を持つ任意の署名者公開鍵集合 $\mathcal{PK}$ に対して任意のメッセージ $m$ 上に署名クエリーを行うことができる。これは、署名プロトコルでメッセージ $m$ に署名するために $\mathcal{PK}$ の他の署名者と対話する正直な署名者をシミュレートするオラクル $\mathcal{O}^{{\sf Sign}(par,\cdot,sk^*,\cdot)}$ にアクセスできることを意味する。 $\mathcal{A}$ はこのようなクエリーをいくつでも同時に作成できることに注意。

Output. 最後に、攻撃者は偽造マルチ署名 $\sigma$ 、メッセージ $m$ および公開鍵集合 $\mathcal{PK}$ を出力する。 $pk^* \in \mathcal{PK}$ で $\mathcal{A}$ が $m^*$ に対する署名クエリーを行わず ${\sf Vf}(par, {\sf KAg}(par, \mathcal{PK}), m, \sigma) = 1$ の場合、攻撃者が勝利する。

定義 4 . $\tau$ 時間で実行され、 $q_{\rm S}$ 個の署名クエリーを作成し、 $q_{\rm H}$ 個のランダムオラクルクエリーを作成し、少なくとも $\epsilon$ の確率で上記のゲームに勝つ場合、 $\mathcal{A}$ はマルチ署名スキーム $\mathcal{AMS} = ({\sf Pg},{\sf Kg},{\sf Sign},{\sf Vf},{\sf SAg},{\sf AVf})$ に対して $(\tau,q_{\rm S},q_{\rm H},\epsilon)$ -偽造者であると言う。 $\mathcal{AMS}$ は $(\tau,q_{\rm S},q_{\rm H},\epsilon)$ -偽造者がいない場合 $(\tau,q_{\rm S},q_{\rm H},\epsilon)$ -偽造不可能である。

2.5 集約マルチ署名

我々は集約署名とマルチ署名の概念を組み合わせて集約マルチ署名を導入し、複数のマルチ署名を 1 つに集約できるようにした。より正確には、2 つのアルゴリズムを使用してマルチ署名の定義を拡張する。 ${\sf SAg}$ はタプルの集合を入力とし、それぞれのタプルは集約公開鍵 $apk$ 、メッセージ $m$ およびマルチ署名 $\sigma$ を含んでおり、単一の集約マルチ署名 $\Sigma$ を出力する。 ${\sf AVf}$ はタプルの集合を入力に取り、それぞれのタプルは集約公開鍵 $apk$ 、メッセージ $m$ および集約マルチ署名 $\Sigma$ を含んでおり、それぞれ集約マルチ署名が無効か有効かを示す 0 または 1 を出力する。どのようなマルチ署名スキームであっても、 $\Sigma \leftarrow (\sigma_1,\ldots,\sigma_n)$ を出力するための ${\sf SAg}(par,\{apk_i,m_i,\sigma_i\})$ と、全ての個々のマルチ署名が有効であれば 1 を出力する ${\sf AVf}(par,\{apk_i,m_i\},(\sigma_1,\ldots,\sigma_n))$ を実装することによって、簡単な方法で集約マルチ署名スキームに転換できることに注意。しかし、目標は $\Sigma$ を個々のマルチ署名の連結より遙かに小さく、理想的には固定サイズにすることである。

集約マルチ署名のセキュリティはマルチ署名のセキュリティに非常に似ている。まず集約マルチ署名は完全性を満たす必要がある。つまり、1) 任意の $n$ に対して $i=1,\ldots,n$ の $(pk_i,sk_i) \leftarrow {\sf Kg}(par)$ を持ち、任意のメッセージ $m$ に対して全ての署名者に ${\sf Sign}(par, sk_i, m)$ を入力すると ${\sf Vf}(par, {\sf KAg}(par, \{pk_i\}_{i=1}^n), m, \sigma) = 1$ となるようなある署名 $\sigma$ を出力する。2) 全ての要素が ${\sf Vf}(par, apk_i, m_i, \sigma_i) = 1$ となるようなマルチ署名集合 $\{(apk_i, m_i, \sigma_i)\}$ に対して、集約マルチ署名も有効 ${\sf AVf}(par, \{apk_i, m_i\}, {\sf SAg}(par, \{(apk_i, m_i, \sigma_i)\})) = 1$ となる。次に、集約マルチ署名は偽造不可能性を満たす必要がある。集約マルチ署名スキーム $\mathcal{AMS} = ({\sf Pg}, {\sf Kg}, {\sf Sign}, {\sf KAg}, {\sf Vf}, {\sf SAg}, {\sf AVf})$ の偽造不可能性は 3 段階のゲームによって定義される。セットアップステージと署名クエリーステージはマルチ署名偽造不可能性ゲームと同じである。出力ステージは以下のように変更される:

Output. 最後に、攻撃者は偽造マルチ署名 $\sigma$ 、集約公開鍵とメッセージのペア $\{apk_i,m_i\}$ 、公開鍵集合 $\mathcal{PK}$ およびメッセージ $m^*$ を出力することによって停止する。 $pk^* \in \mathcal{PK}$ で $\mathcal{A}$ が $m^*$ に対する署名クエリーを行わず、 ${\sf AVf}(par, \{(apk_i, m_i)\} \cup \{({\sf KAg}(par, \mathcal{PK}), m^*)\}, \Sigma) = 1$ の場合、攻撃者が勝利する。

定義 5 . $\tau$ 時間で実行され、 $q_{\rm S}$ 個の署名クエリーを作成し、 $q_{\rm H}$ 個のランダムオラクルクエリーを作成し、少なくとも $\epsilon$ の確率で上記のゲームに勝つ場合、 $\mathcal{A}$ は集約マルチ署名スキーム $\mathcal{AMS} = ({\sf Pg}, {\sf Kg}, {\sf Sign}, {\sf Vf}, {\sf SAg}, {\sf AVf})$ に対して $(\tau, q_{\rm S}, q_{\rm H}, \epsilon)$ -偽造者であると言う。 $\mathcal{AMS}$ は $(\tau, q_{\rm S}, q_{\rm H}, \epsilon)$ -偽造者がいない場合 $(\tau, q_{\rm S}, q_{\rm H}, \epsilon)$ -偽造不可能である。

3 ペアリングによる鍵集約を有するマルチ署名

我々はまず公開鍵集約をサポートするペアリングベースの新しいマルチ署名スキームを提示する。双線形群は 2 つの群のうち 1 つがよりコンパクトな表現を有するという意味で典型的には非対称である。以下のペアリングベースのスキームは公開鍵と署名が異なる群に属する必要がある。標準の署名では 1 つの公開鍵を使用して多くのメッセージに署名するため、署名にはよりコンパクトな群を使用することが理にかなっている。しかしながら、以下のスキームでは署名と公開鍵の両方の集約が可能になるためもはやこれは真ではなく、最適な群の選択は具体的な適用状況に強く依存する可能性がある。以下では $\mathbb{G}_1$ に署名を配置し $\mathbb{G}_2$ に公開鍵を配置するスキームについて説明するが、これら 2 つの群のどちらがよりコンパクトな表現を持つかについては公開しておく。効率的なハッシュ関数が群のいずれかにマッピングされている [49, 22, 15] ことに注意。

3.1 ペアリングベースのスキームの説明

公開鍵集約 $\mathcal{MSP}$ を使用した我々のペアリングベースのマルチ署名は BLS 署名スキーム [13] から構築される。このスキームはプレーン公開鍵モデルでセキュアであり、ハッシュ関数 ${\sf H}_0:\{0,1\}^* \to \mathbb{G}_2$ と ${\sf H}_1: \{0,1\}^* \to \mathbb{Z}_q$ を想定している。

パラメータ生成. ${\sf Pg}(\kappa)$ は双線形群 $(q, \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t, e, g_1, g_2) \leftarrow \mathcal{G}(\kappa)$ を設定し $par \leftarrow (q, \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t, e, g_1, g_2)$ を出力する。

鍵生成. 鍵生成アルゴリズム ${\sf Kg}(par)$ は $sk \overset{S}{\leftarrow} \mathbb{Z}_q$ を選択し、 $pk \leftarrow g_2^{sk}$ を計算して $(pk, sk)$ を出力する。

鍵集約. ${\sf KAg}(\{pk_1, \ldots, pk_n\})$ は $apk \leftarrow \prod_{i=1}^n pk_i^{{\sf H}_1(pk_i, \{pk_1, \ldots, pk_n\})}$ を出力する。

署名. 署名は単一ラウンドのプロトコルである。 ${\sf Sign}(par, \{pk_1, \ldots, pk_n\}, sk_i, m)$ は $s_i \leftarrow {\sf H}_0(m)^{a_i \cdot sk_k}$ を計算する。ここで $a_i \leftarrow {\sf H}_1(pk_i, \{pk_1, \ldots, pk_n\})$ である。最終的な署名を $\sigma \leftarrow \prod_{j=1}^n s_j$ として計算する特定の結合者に $s_i$ を送信する。この特定の結合者は署名者のいずれかや外部の当事者でも構わない。

マルチ署名検証. ${\sf Vf}(par, apk, m, \sigma)$ は $e(\sigma, g_2^{-1}) \cdot e({\sf H}_0(m), apk) \overset{?}{=} 1_{\mathbb{G}_t}$ の場合に 1 を出力する。

バッチ検証. $b$ 個のマルチ署名は 1 つずつ検証するよりもバッチとして検証した方が高速である点に注意。この方法を理解するために $i=1, \ldots, b$ に対して三値 $(m_i, \sigma_i, apk_i)$ が与えられたと仮定する。ここで $apk_i$ は $m_i$ 上のマルチ署名 $\sigma_i$ を検証するために使用する集約公開鍵である。もし全てのメッセージ $m_1, \ldots, m_b$ の性質が異なっていれば、( $\ref{aggregated_signature}$ ) のように署名集約を使用してこれら全ての三値をバッチとして検証することができる:

集約署名 $\tilde{\sigma} = \sigma_1 \cdots \sigma_b \in \mathbb{G}_1$ を計算する。
もし $e(\tilde{\sigma}, g_2) \overset{?}{=} e({\sf H}_0(m_1), apk_1) \cdots e({\sf H}_0(m_b), apk_b)$ であれば全ての $b$ 個全てのマルチ署名三値を有効として受け入れる。

このように、 $b$ 個のマルチ署名を検証するには $2b$ のペアリングではなく $b+1$ のペアリングのみが必要である。この簡単なバッチ手続きはメッセージ $m_1, \ldots, m_b$ 全てが異なっている時にのみ使用することができる。もしいくつかのメッセージが繰り返されていれば、バッチ検証は最初にランダムな指数 $\rho_1, \ldots, \rho_b \overset{S}{\leftarrow} \{1, \ldots, 2^\kappa\}$ を選択することで行うことができる。ここで $\kappa$ はセキュリティパラメータであり、 $\tilde{\sigma} = \sigma_1^{\rho_1} \cdots \sigma_b^{\rho_b} \in \mathbb{G}_2$ を計算して $e(\tilde{\sigma}, g_2) \overset{?}{=} e({\sf H}_0(m_1), apk_1^{\rho_1}) \cdots e({\sf H}_0(m_b), apk_b^{\rho_b})$ を検証する。もちろん、右側のペアリングは繰り返されるメッセージに対して結合できる。

3.2 セキュリティ証明

定理 1. $\mathcal{MSP}$ は (定義 4 で定義されたように) ランダムオラクルモデルの Computational co-Diffie-Hellman 問題に基づく偽造不可能なマルチ署名スキームである。より正確には、 $\mathcal{MSP}$ は $q \gt 8q_{\rm H} / \epsilon$ かつ ${\sf co\mbox{-}CDH}$ が $((\tau + q_{\rm H} \tau_{{\rm exp}_1} + q_{\rm S} (\tau_{{\rm exp}_2^l} + \tau_{{\rm exp}_1}) + \tau_{{\rm exp}_2^l}) \cdot 8_{q_{\rm H}}^2 / \epsilon \cdot \ln(8q_{\rm H} / \epsilon), \epsilon / (8q_{\rm H}))$ -困難であれば $(\tau, q_{\rm S}, q_{\rm H}, \epsilon)$ -偽造不可能である。ここで $l$ は単一のマルチ署名に含まれる署名者の最大数、 $\tau_{{\rm exp}_1}$ と $\tau_{{\rm exp}_2}$ はそれぞれ $\mathbb{G}_1$ と $\mathbb{G}_2$ のべき乗の計算に必要な時間を示し、 $\tau_{{\rm exp}_1^i}$ と $\tau_{{\rm exp}_2^i}$ はそれぞれ $\mathbb{G}_1$ と $\mathbb{G}_2$ での $i$ -multiexponentiations の計算に必要な時間を示している。

Proof. (原文参照)

3.3 マルチ署名の集約

集約されたマルチ署名のメッセージが異なるのであれば $\mathcal{MSP}$ スキームのマルチ署名をさらに乗算してさらに集約することができる。メッセージが異なることを保証する最も簡単な方法は、署名されるメッセージに集約公開鍵を含めることである。これは集約マルチ署名スキーム $\mathcal{AMSP}$ をここで定義する方法である。つまり $\mathcal{AMSP}$ と $\mathcal{MSP}$ は ${\sf Pg}$ , ${\sf Kg}$ および ${\sf KAg}$ アルゴリズムを共有するが、 $\mathcal{AMSP}$ は署名されたメッセージに $apk$ を含む ${\sf Sign}$ と ${\sf Vf}$ アルゴリズムをわずかに変更し、署名を集約し集約署名を検証するための追加のアルゴリズム ${\sf SAg}$ と ${\sf AVf}$ がそれぞれ存在する。

署名. ${\sf Sign}(par, \mathcal{PK}, sk_i, m)$ は $s_i \leftarrow {\sf H}_0(apk, m)^{a_i \cdot sk_i}$ を計算する。ここで $apk \leftarrow {\sf KAg}(par, \mathcal{PK})$ と $a_i \leftarrow {\sf H}_1(pk_i, \{pk_1, \ldots, pk_n\})$ である。指定された結合者は全ての署名 $s_i$ を収集し最終的な署名 $\sigma \leftarrow \prod_{j=1}^n s_j$ を計算する。

マルチ署名検証. ${\sf Vf}(par, apk, m, \sigma)$ は $e(\sigma, g_2^{-1}) \cdot e({\sf H}_0(apk, m), apk) \overset{?}{=} 1_{\mathbb{G}_t}$ の場合にのみ 1 を出力する。

署名アルゴリズム. ${\sf SAg}(par, \{(apk_i, m_i, \sigma_i)\}_{i=1}^n)$ は $\Sigma \leftarrow \prod_{i=1}^n \sigma_i$ を出力する。

集約署名検証. ${\sf AVf}(\{(apk_i, m_i)\}_{i=1}^n, \Sigma)$ は $e(\Sigma, g_2^{-1}) \cdot \prod_{i=1}^n e({\sf H}_{i=1}^n e({\sf H}_0(apk_i, m_i), apk_i) \overset{?}{=} 1_{\mathbb{G}_t}$ の場合にのみ 1 を出力する。

セキュリティ証明は $\mathcal{MSP}$ の証明とほとんど同じだが $\mathbb{G}_1$ と $\mathbb{G}_2$ の間に同型 (isomorphism) $\varphi$ が必要となる。従って我々はより強い ${\sf \varphi\mbox{-}co\mbox{-}CDH}$ 仮定の下でセキュリティを証明する。これは ${\sf co\mbox{-}CDH}$ と同じだが、敵対者にこの同型をオラクルとして提供する。

定理 2. ランダムオラクルモデルにおいて Computational $\varphi$ -co-Diffie-Hellman 問題の下で $\mathcal{AMSP}$ はセキュアな集約マルチ署名スキームである。より正確には $q \gt 8 q_{\rm H} / \epsilon$ であり、Computational $\varphi$ -co-Diffie-Hellman 問題が $(\tau + q_{\rm H} \tau_{{\rm exp}_1} + q_{\rm S} (\tau_{{\rm exp}_2^l} + \tau_{{\rm exp}_1}) + \tau_{{\rm exp}_2^l} + \tau_{{\rm exp}_1^n}) \cdot 8 q_{\rm H}^2 / \epsilon \cdot \ln(8 q_{\rm H} / \epsilon), \epsilon / (8 q_{\rm H}))$ -困難であれば、 $\mathcal{AMSP}$ は $(\tau, q_{\rm S}, q_{\rm H}, \epsilon)$ -偽造不可能である。ここで $l$ は単一のマルチ署名に関与する署名者の最大数、 $n$ は偽造に集約されたマルチ署名の量、 $\tau_{{\rm exp}_1}$ と $\tau_{{\rm exp}_2}$ はそれぞれ $\mathbb{G}_1$ と $\mathbb{G}_2$ のべき乗を研鑽する為に必要な時間を示し、 $\tau_{{\rm exp}_1^i}$ と $\tau_{{\rm exp}_2^i}$ はそれぞれ $\mathbb{G}_1$ と $\mathbb{G}_2$ の $i$ -multiexponentiations を計算するために必要な時間を示す。

Proof. $\mathcal{AMSP}$ マルチ署名スキームに対して $(\tau, q_{\rm S}, q_{\rm H}, \epsilon)$ 偽造者 $\mathcal{F}$ が存在すると仮定する。我々は定理 1 の証明と全く同じように $\mathcal{A}$ を作成する。ただし、 $\mathcal{F}$ は単純な署名偽造者ではなく集約マルチ署名の偽造署名出力する。つまり、 $\mathcal{F}$ は集約マルチ署名 $\Sigma$ 、集約公開鍵とメッセージのペア $\{(apk_1,m_1),\ldots,(apk_n,m_n)\}$ 、公開鍵の集合 $\mathcal{PK}$ およびメッセージ $m^*$ を出力する。 $apk^* \leftarrow {\sf KAg}(par, \mathcal{PK})$ とする。もし $\mathcal{A}$ が $k$ 番目の ${\sf H}_0$ クエリーは ${\sf H}_0(apk^*, m^*)$ であると正しく推測した場合、 $e(\Sigma, g_2^{-1}) \cdot e(A, apk^*) \cdot \prod_{i=1}^n e({\sf H}_0(apk_i, m_i), apk_i) = 1_{\mathbb{G}_t}$ となる。 $\mathcal{A}$ は ${\sf H}_0(apk_i, m_i) = g_1^{r_i}$ であるような全ての $(api_i, m_i)$ に対して $r_i$ を検索する。これは $\sigma \leftarrow \Sigma \cdot \prod_{i=1}^n \mathcal{O}^\varphi(apk_i^{-r_i})$ を計算するため $e(\sigma, g_2) = e(y, apk^*)$ である。ここで $\mathcal{A}$ が $\mathcal{MSP}$ 偽造を抽出したことに注意。つまり残りの削減は定理 1 の証明と全く同じである。従って削減の成功確率は同じであり、実行時間は $\sigma$ を計算するために必要な余計なステップによってのみ増加する。これには $\tau_{{\rm exp}_1^n}$ がかかる。

4 Accountable-Subgroup マルチ署名

Micali, Ohta and Reyzin [38] は署名者集合 $\mathcal{PK}$ の任意の部分集合 $S$ が、部分集合内の署名者たちの公開鍵に対して検証できる有効なマルチ署名を生成することができるマルチ署名スキームとして、accountable-subgroup マルチ署名スキームを定義した。ASM スキームを $\mathcal{PK}$ 上の任意のアクセス構造と組み合わせて、部分集合 $S$ が $\mathcal{PK}$ に変わって署名する権限を持つかを判断することができる。例えば $|S| \ge t$ が必要であるとすれば ASM スキームをしきい値署名スキームの形に変換する。これにより、署名は参加した署名者の集合も認証する。

ASM スキームの検証には $\min(|\mathcal{PK}|, |S| \times \lceil \log_2 |\mathcal{PK}| \rfloor)$ ビットを使用する群 $\mathcal{PK}$ 内のインデックスによって記述できる署名者集合 $S$ の記述が明らかに必要である。 $S$ の説明とは別に $|S|$ や $|\mathcal{PK}|$ に依存するサイズのデータ項目を必要としない最初の ASM スキームを説明する。検証はコンパクトな集約公開鍵と署名に基づいて実行される。集約公開鍵は個々の署名者の公開鍵から誰でも計算できるが、 $\mathcal{PK}$ の全てのメンバーが、それぞれの署名者が群固有のメンバーシップ鍵を取得した後に、群 $\mathcal{PK}$ に対するメッセージに署名する必要がある 1 回限りの群セットアップを必要とする。

4.1 ASM スキームの定義

ASM スキーム [38] のオリジナルの構文とセキュリティ定義を採用して公開鍵集約とインタラクティブな群セットアップ手順をサポートする。

ASM スキームはアルゴリズム ${\sf Pg}$ , ${\sf Kg}$ , ${\sf GSetup}$ , ${\sf Sign}$ , ${\sf KAg}$ および ${\sf Vf}$ で構成されている。共通のシステムパラメータは $par \overset{S}{\leftarrow} {\sf Pg}$ で生成される。それぞれの署名者は鍵ペア $(pk, sk) \overset{S}{\leftarrow} {\sf Kg}(par)$ を生成する。署名者 $\mathcal{PK} = \{pk_1, \ldots, pk_n\}$ のグループに参加するために、メンバーシップ鍵 $mk$ を得るために $\mathcal{PK}$ の各署名者はインタラクティブなアルゴリズム ${\sf GSetup}(sk, \mathcal{PK})$ を実行する。我々は $\mathcal{PK}$ のそれぞれの署名者に公に計算可能なインデックス $i \in \{1, \ldots, |\mathcal{PK}|\}$ 、例えばソート済み $\mathcal{PK}$ リストの $pk$ のインデックスなどが割り当てられていると想定する。 $\mathcal{PK}$ の任意の署名者サブグループ $S \subseteq \{1, \ldots, |\mathcal{PK}|\}$ は、それぞれがインタラクティブアルゴリズム ${\sf Sign} (par, \mathcal{PK}, S, sk, mk, m)$ を呼び出すことによってメッセージ $m$ に集約的に署名することができる。ここで $mk$ は署名 $\sigma$ を得るための、この署名者グループの署名者のメンバーシップ鍵である。この鍵集約アルゴリズムは、署名者 $\mathcal{PK}$ グループの公開鍵を入力すると集約公開鍵 $apk$ を出力する。署名 $\sigma$ は 0 または 1 を出力する ${\sf Vf}(par, apk, S, m, \sigma)$ を実行することによって検証される。

正確性には、全ての $n \gt 0$ 、全ての $S \subseteq \{1, \ldots, n\}$ および全ての $m \in \{0,1\}^*$ に対して、 $par \overset{S}{\leftarrow} {\sf Pg}$ 、 $(pk_i, sk_i) \overset{S}{\leftarrow} {\sf Kg}(par)$ 、 $mk_i \overset{S}{\leftarrow} {\sf GSetup}(sk_i, \{pk_1, \ldots, pk_n\})$ および $\sigma \overset{S}{\leftarrow} {\sf Sign}(par, \{pk_1, \ldots, pk_n\}, S, sk_i, mk_i, m)$ のとき、確率 1 で ${\sf Vf}(para, apk, S, m, \sigma) = 1$ となることを必要とする。ここで、 ${\sf Sign}$ は $S$ のメンバーによってのみ実行されるが、 ${\sf GSetup}$ は全ての署名者 $1, \ldots, n$ によって実行される。

セキュリティ. 偽造不可能性は以下のゲームで説明される。

Setup. 挑戦者は $par \leftarrow {\sf Pg}$ と $(pk^*, sk^*) \overset{S}{\leftarrow} {\sf Kg}(par)$ を生成し、攻撃者は $\mathcal{A}(par, pk^*)$ を実行する。

Group Setup. 攻撃者は公開鍵 $\mathcal{PK}$ の任意の集合に対してグループセットアッププロトコル ${\sf GSetup}(sk^*, \mathcal{PK})$ を実行できるため、 $pk^* \in \mathcal{PK}$ であり、挑戦者は標的署名者 $pk^*$ の役割を行う。挑戦者は結果のメンバーシップ鍵 $mk_{\mathcal{PK}}^*$ を保存するが $\mathcal{A}$ には渡さない。

Signature queries. 攻撃者は、任意のメッセージ $m$ 、任意の署名者グループ $\mathcal{PK}$ 、 $mk_{\mathcal{PK}}^*$ の定義されている $pk^* \in \mathcal{PK}$ 、および任意の $S \subseteq \{1, \ldots, |\mathcal{PK}|\}$ に対して、任意で多数同時の署名プロトコルに関与することもできる。ここで $i$ は $\mathcal{PK}$ での $pk^*$ のインデックスである。挑戦者は ${\sf Sign}(par, \mathcal{PK}, S, sk^*, mk^*, m)$ を実行して $i$ 番目の署名者の役割を果たし、結果の署名 $\sigma$ を $\mathcal{A}$ に渡す。

Output. 攻撃者は、公開鍵集合 $\mathcal{PK}$ 、集合 $S \subseteq \{1, \ldots, |\mathcal{PK}|\}$ 、メッセージ $m$ 、および ASM 署名 $\sigma$ を出力する。もし ${\sf Vf}(par, apk, S, m, \sigma) = 1$ であればゲームに勝利する。ここで $apk \leftarrow {\sf KAg}(\mathcal{PK})$ , および $pk^* \in \mathcal{PK}$ , $i$ は $\mathcal{PK}$ での $pk^*$ のインデックスであり $i \in S$ である。そして $\mathcal{A}$ は署名クエリーの一部として $m$ を送信していない。

定義 6 . 時間 $\tau$ で実行し、 $q_{\rm G}$ 個のグループセットアップクエリー、 $q_{\rm S}$ 個の署名クエリー、 $q_{\rm H}$ 個のランダムオラクルクエリーを作成し、少なくとも $\epsilon$ の確率で上記のゲームに勝利する場合、 $\mathcal{A}$ は accountable-subgroup マルチ署名スキーム ASM に対して $(\tau, q_{\rm G}, q_{\rm S}, q_{\rm H}, \epsilon)$ -偽造者であると言う。 $(\tau, q_{\rm G}, q_{\rm S}, q_{\rm H}, \epsilon)$ -偽造者が存在しない場合 $\mathcal{ASM}$ は $(\tau, q_{\rm G}, q_{\rm S}, q_{\rm H}, \epsilon)$ -偽造不可能である。

4.2 我々の ASM スキーム

我々の ASM スキームにおける鍵生成と鍵集約は前のセクションの集約可能なマルチ署名スキームと同じである。我々は $\mathcal{PK}$ の $i$ 番目の署名者が $(apk,i)$ 上のマルチ署名である "メンバーシップ鍵" を持つように、グループセットアップ中に全ての署名者が集約公開鍵と全ての署名者のインデックスのマルチ署名に貢献できるようにすることで ASM スキームを構築する。上位レベルでは accountable-subgroup マルチ署名は個々の署名者の署名、それらのメンバーシップ鍵、サブグループ $S$ の集約公開鍵で構成される。サブグループ $S$ がメッセージに署名したかを検証するためには、その署名が、サブグループの集約公開鍵がメッセージと $S$ に対応するメンバーシップ鍵に署名した有効な集約署名であることを確認する。

このスキームはハッシュ関数 ${\sf H}_0: \{0,1\}^* \to \mathbb{G}_1$ 、 ${\sf H}_1: \{0,1\}^* \to \mathbb{Z}_q$ 、および ${\sf H}_2: \{0,1\}^* \to \mathbb{G}_1$ を使用する。パラメータ生成、鍵生成、および鍵集約はセクション 3 の集約マルチ署名スキームと同じである。

グループセットアップ. ${\sf GSetup}(sk_i, \mathcal{PK} = \{pk_1, \ldots, pk_n\})$ では $pk_i \in \mathcal{PK}$ であり $i$ が $\mathcal{PK}$ での $pk_i$ のインデックスであることを確認する。署名者 $i$ は集約公開鍵 $apk \leftarrow {\sf KAg}(\mathcal{PK})$ と $a_i \leftarrow {\sf H}_1(pk_i, \mathcal{PK})$ を計算する。そして署名者 $j$ に $\mu_{j,i} = {\sf H}_2(apk, j)^{a_i \cdot sk_i}$ を送信するか、または単にそれらの値を発行する。 $j \neq i$ である他の全ての署名者から $\mu_{i,j}$ を受け取った後、 $\mu_{i,i} \leftarrow {\sf H}_2(apk, i)^{a_i \cdot sk_i}$ を計算し、メンバーシップ鍵 $mk_i \leftarrow \prod_{j=1}^n \mu_{i,j}$ を返す。全ての署名者が正直に動作する場合 $e(g_1, mk_i) = e(apk, {\sf H}_2(apk, i))$ となることに注意。言い換えると、この $mk_i$ はセクション 3.1 のスキームで定義されているように、全ての $n$ 個の当事者によるメッセージ ${\sf H}_2(apk, i)$ 上の有効なマルチ署名である。

署名. ${\sf Sign}(par, \mathcal{PK}, S, sk_i, mk_i, m)$ は $apk \leftarrow {\sf KAg}(\mathcal{PK})$ と $s_i \leftarrow {\sf H}_0(apk, m)^{sk_i} \cdot mk_i$ を計算し指定された結合者 ( $S$ のメンバーまたは外部の当事者の 1 つ) に $(sk_i, s_i)$ を送信する。結合者は $pk \leftarrow \prod_{j \in S} pk_j, \ \ s \leftarrow \prod_{j \in S} s_j$ を計算し、マルチ署名 $\sigma := (pk, s)$ を出力する。集合 $S$ はプロトコルの開始時に固定している必要はなく、部分的な署名が収集されるときに決定できることに注意。

検証. ${\sf Vf}(par, apk, S, m, \sigma)$ は $\sigma$ を $(pk, s)$ として解析し $e({\sf H}_0(apk, m), pk) \cdot e\left( \prod_{j \in S} {\sf H}_2(apk, j), apk \right) \overset{?}{=} e(s, g_2)$ かつ $S$ が署名によって認証された集合であれば 1 を出力する。

提示した ASM スキームは正確性を満たしている。当事者たちがグループセットアップと署名プロトコルを正直に実行する場合、 $pk = g_2^{\sum_{i \in S} sk_i}$ 、 $apk = g_2^{\sum_{i=1,\ldots,n}a_i \cdot pk_i}$ 、および $s = {\sf H}_0(apk, m)^{\sum_{i \in S}sk_i} \cdot \prod_{i \in S} {\sf H}_2(apk, i)^{\sum_{j \in 1,\ldots,n} a_j \cdot sk_j}$ となり、それらは検証に渡される: $\begin{eqnarray*} e(s, g_2) & = & e\left( {\sf H}_0(apk, m)^{\sum_{i \in S} sk_i} \cdot \prod_{i \in S} {\sf H}_2(apk, i)^{\sum_{j \in 1,\ldots,n} a_j \cdot sk_j}, g_2 \right) \\ & = & e\left( {\sf H}_0(apk, m), pk \right) \cdot e\left( \prod_{i \in S} {\sf H}_2(apk, i), g_2^{\sum_{j \in 1,\ldots,n} a_j \cdot sk_j} \right) \\ & = & e\left( {\sf H}_0(apk, m), pk \right) \cdot e\left( \prod_{i \in S} {\sf H}_2(apk, i), apk \right) \end{eqnarray*}$

4.3 我々の ASM スキームのセキュリティ

定理 3. 我々の ASM スキームはランダムオラクルモデルにおける Computational $\varphi$ -co-Diffie-Hellman 問題の困難さの下では偽造不可能である。より正確には、 $q \gt 8 q_{\rm H} / \epsilon$ かつ $\varphi\mbox{-}{\sf co\mbox{-}CDH}$ が $(\tau + q_{\rm H} \cdot \max(\tau_{{\rm exp}_2^1}, \tau_{{\rm exp}_1^2}) + q_{\rm G} \cdot (l - 1) \tau_{{\rm exp}_1} + q_{\rm S} \cdot (\tau_{{\rm exp}_2^1} + \tau_{{\rm exp}_1}) + 2 \tau_{\rm pair} + \tau_{{\rm exp}_1^3}) \cdot 8 q_{\rm H}^2 / ((1 - (q_{\rm S} + q_{\rm H}) / q) \cdot \epsilon) \cdot \ln(8 q_{\rm H} / ((1 - (q_{\rm S} + q_{\rm H}) / q) \cdot \epsilon)), (1-(q_{\rm S} + q_{\rm H}) / q) \cdot \epsilon / (8 q_{\rm H}))$ -困難であれば、ランダムオラクルモデルにおいて $(\tau, q_{\rm S}, q_{\rm H}, \epsilon)$ -偽造不可能である。ここで $l$ は任意のグループセットアップに関与する署名者の最大数であり、 $\tau_{{\rm exp}_1}$ と $\tau_{{\rm exp}_2}$ はそれぞれ $\mathbb{G}_1$ と $\mathbb{G}_2$ のべき乗計算に必要な時間を示し、 $\tau_{{\rm exp}_1^i}$ と $\tau_{{\rm exp}_2}^i$ はそれぞれ $\mathbb{G}_1$ と $\mathbb{G}_2$ の $i$ -multiexponentiations の計算に必要な時間を示す。 $\tau_{\rm pair}$ はペアリング操作の計算に必要な時間を示す。

Proof. (原文参照)

5 A Scheme from Discrete Logarithms

我々のペアリングベースのスキームの基本的な鍵集約技術は Maxwell ら [35] によるものである。彼らは同様の鍵集約技術を使用し Bellare-Naven のスキーム [9] に関する署名プロトコルで 1 ラウンドのインタラクションを削減した Schnorr ベースのマルチ署名スキームを提示した。しかし残念ながら署名プロトコルのシミュレーションに問題があったため後にセキュリティの証拠に欠陥があることが分かった [21]。以下では Bellare-Neven の予備ラウンドハッシュと組み合わせることにより Maxwell らの通常の (つまりペアリングに向いていない) 曲線に対する鍵集約技術を回復する。結果として得られるスキームは Maxwell らのオリジナルのスキームと同じスペースを削減するが、離散対数仮定の困難さの下で確実に安全である。我々の研究とは独立して、Maxell ら [36] は我々がここで提示するのと同じプロトコルを使用して彼らの研究を修正している。

5.1 離散対数スキームの説明

我々の離散対数ベースのマルチ署名スキーム $\mathcal{MSDL}$ はハッシュ関数 ${\sf H}_0,{\sf H}_1,{\sf H}_2:\{0,1\}^* \to \mathbb{Z}_q$ を使用する。これらはドメイン分離 (domain separation) を使用して単一のハッシュ関数から具現化できる。

パラメータ生成. ${\sf Pg}(\kappa)$ は生成元 $g$ で位数 $q$ の群 $\mathbb{G}$ を設定する。ここで $q$ は $\kappa$ -ビットの素数であり、 $par \leftarrow (\mathbb{G}, g, q)$ を出力する。

鍵生成. 鍵生成アルゴリズム ${\sf Kg}(par)$ では $sk \overset{S}{\leftarrow} \mathbb{Z}_q$ を選択し $pk \leftarrow g^{sk}$ を計算して $(pk,sk)$ を出力する。

鍵集約. ${\sf KAg}(\{pk_1,\ldots,pk_n\})$ は $apk \leftarrow \prod_{i=1}^n pk_i^{{\sf H}_1(pk_i,\ldots,pk_n\})}$ を出力する。

署名. 署名はインタラクションを伴う 3 ラウンドのプロトコルである。入力 ${\sf Sign}(par, \{pk_1, \ldots, pk_n\}, sk, m)$ で署名者 $i$ は以下のように動作する。

ラウンド 1. $r_i \overset{S}{\leftarrow} \mathbb{Z}_q$ を選択し $R_i \leftarrow g^{r_i}$ を計算する。 $t_i \leftarrow {\sf H}_2(R_i)$ とする。 $pk_1,\ldots,pk_n$ に対応する他の全ての署名者に $t_i$ を送信し、他の全ての署名者 $j \neq i$ から $t_i$ を受信するまで待機する。
ラウンド 2. $pk_1,\ldots,pk_n$ に対応する他の全ての署名者に $R_i$ を送信し、他の全ての署名者 $j \neq i$ からの $R_j$ を受信するまで待機する。全ての $j=1,\ldots,n$ に対して $t_j = {\sf H}_2(R_j)$ を確認する。
ラウンド 3. $apk \leftarrow {\sf KAg}(\{pk_1,\ldots,pk_n\})$ を計算し $a_i \leftarrow {\sf H}_1(pk_i, \{pk_1, \ldots, pk_n\})$ とする。複数のメッセージが同じ署名者の集合で署名されている場合、 $apk$ と $a_i$ は再計算しなくても保存できることに注意。

$\bar{R} \leftarrow \prod_{i=1}^n R_j$ と $c \leftarrow (\bar{R},apk,m)$ を計算する。 $s_i \leftarrow r_i + c \cdot sk_i \cdot a_i \bmod q$ を計算する。他の全ての署名者に $s_i$ を送信し、他の全ての署名者 $j \neq i$ から $s_j$ を受信するまで待機する。 $s \leftarrow \sum_{j=1}^n s_j$ を計算し $\sigma \leftarrow (\bar{R},s)$ を最終的な署名として出力する。

検証. ${\sf Vf}(par, apk, m, \sigma)$ は $\sigma$ を $(\bar{R},s) \in \mathbb{G} \times \mathbb{Z}_q$ として解析し、 $c \leftarrow {\sf H}_0(\bar{R},apk,m)$ を計算して、もし $g^s \cdot apk^{-c} \overset{?}{=} \bar{R}$ であれば 1 を出力する。

このスキームはより効率的なバッチ検証を可能に為る。これにより検証者は $n$ 2-multi-exponentiations の代わりに $3n$ -multi-exponentiations で $n$ 個の署名の正当性を確認することができる。 $n$ 個の署名 $\{(apk_i,m_i,(\bar{R}_i,s_i))\}_{i=1}^n$ のリスト内の全ての署名が有効であることを検証するには $c_i \leftarrow {\sf H}_1(\bar{R},apk_i,m_i)$ を計算し $i=1,\ldots,n$ に対して $\alpha_i \overset{S}{\leftarrow} \mathbb{Z}_q$ を選択し、そしてもし $\prod_{i=1}^n g^{\alpha_i s_i} apk_i^{-\alpha_i c_i} \bar{R}_i^{-\alpha_i} \overset{S}{=} 1_\mathbb{G}$ であれば受け入れる。

5.2 セキュリティ証明

セキュリティ証明は分岐補題を 2 回適用する [35] のそれに従う: ランダムオラクルクエリー ${\sf H}_0(\bar{R},apk,m)$ で分岐することにより、 $apk$ の離散対数 $w$ を抽出できる 2 つの偽造を取得し、そして再度クエリー ${\sf H}_1(pk_i,\{pk_1,\ldots,pk_n\})$ で分岐することにより標的の公開鍵の離散対数を抽出できる 2 つのそのようなペア $(apk,w)$ と $(apk',w')$ を取得する。

定理 4. $\mathcal{MSDL}$ はランダムオラクルモデルにおいて離散対数問題が困難であれば (定義 4 で定義したように) 偽造不可能なマルチ署名スキームである。より正確には、 $q \gt 8 q_{\rm H} / \epsilon$ かつ離散対数が $((\tau + 4lq_{\rm T} \cdot \tau_{\rm exp} + O(lq_{\rm T})) \cdot 512 q_{\rm T}^2 / (\epsilon - \delta) \cdot \ln^2(64 / (\epsilon - \delta)), (\epsilon - \delta) / 64)$ -困難であれば $\mathcal{MSDL}$ はランダムオラクルモデルにおいて $(\tau,q_{\rm S},q_{\rm H},\epsilon)$ -偽造不可能である。ここで $l$ は単一のマルチ署名に含まれる署名者の最大数、 $q_{\rm T} = q_{\rm H} + q_{\rm S} + 1$ 、 $\delta = 4lq_{\rm T}^2/q$ 、および $\tau_{\rm exp}$ は $\mathbb{G}$ のべき乗の計算に必要な時間である。

Proof. (原文参照)

6 所有の証明を有するスキーム

Ristenpart and Yilek [47] によって最初に観察されたように、マルチ署名での不正鍵攻撃は署名者が自身の公開鍵にいわゆる所有の証明 (proof of possession) (PoP) を追加することによって防ぐことができる。特に Boldyreva の [10, 13] と Lu ら [32] のマルチ署名の場合にこれが当てはまることを示している。我々は Maxwell らの鍵集約 [35] ではなく、PoP を検証した後に、より簡単な鍵集約を生成する PoP を使用しても我々の全てのスキームが強化できることを示す。これは集約鍵が個々の鍵の単純な積であるようなものである。

PoP を使用するスキームの主な欠点はもちろん公開鍵サイズの増加である。しかしながら、個々の公開鍵のサイズは問題にはならない場合もある。例えば主体の Multisig アドレスは、全ての署名者が集約公開鍵を知っており合意している限り、原則として全ての署名者の個々の公開鍵を明らかにする必要はない。署名者たちは Multisig ウォレットが作成されたときにお互いの PoP を交換し検証することによって集約鍵に対する信頼を構築でき、集約鍵は外部世界にのみ宣伝する。(Blockchain のような) 分散台帳において、署名者は比較的小さく静的なノードの集合である場合があり、その公開鍵は一度検証された後、任意の組み合わせで集約される。

我々のスキームの PoP 変種は検討する価値のあるいくつかの利点がある。つまり集約公開鍵は、アクティブな署名者の集合が頻繁に変更される場合に関連する multi-exponentiation とは対照的に、個々の鍵の単純な乗算および/またはハッシュである。また、それらのセキュリティ証明は (第一層) 分岐を回避し、セキュリティの大幅な削減をもたらし、従って具体的なセキュリティが考慮される状況でより短い鍵と署名のサイズをもたらす。

以下では元のスキームとそれらのセキュリティに対する PoP 変種の違いを要約しているだけである。セキュリティの証明は補足資料に記載されている。

6.1 PoP を有するペアリングベースのスキーム

$\mathcal{MSP}\mbox{-}\mathcal{pop}$ と $\mathcal{AMSP}\mbox{-}\mathcal{pop}$ はそれぞれ $\mathcal{MSP}$ と $\mathcal{ASMP}$ スキームの PoP 変種である。事実、 $\mathcal{MSP}\mbox{-}\mathcal{pop}$ は [47, 10] で知られるが完全を期すためにここで振り返る。スキームは追加のハッシュ関数 ${\sf H}_1:\{0,1\}^* \to \mathbb{G}_1$ を使用する。これはドメイン分割を使用して ${\sf H}_0$ から構築できるだろう。鍵生成は $y \leftarrow g_2^{sk}$ と所有の証明 $\pi \leftarrow {\sf H}_1(y)^x$ を計算し $sk \leftarrow (y,\pi)$ を設定するという点で異なる。鍵 $\{(y_1,\pi_1),\ldots,(y_n,\pi_n)\}$ を集約するために、最初に $i = 1, \ldots, n$ に対して $e({\sf H}_1(y_i), y_i) \overset{?}{=} e(\pi_i, g_2)$ を確認する。その場合、 ${\sf KAg}$ は $apk \leftarrow \prod_{i=1}^n y_i$ を出力し、そうでなければ $\perp$ を出力する。

$\mathcal{MSP}\mbox{-}\mathcal{pop}$ の署名プロトコルにより、秘密鍵 $sk_i$ を持つ署名者たちはその部分署名を $s_i \leftarrow {\sf H}_0(m)^{sk_i}$ として計算でき、 $\mathcal{AMSP}\mbox{-}\mathcal{pop}$ では $s_i \leftarrow {\sf H}_0(apk, m)^{sk_i}$ として計算する。その他の署名結合、集約および検証は $\mathcal{MSP}$ と $\mathcal{AMSP}$ と同じである。

定理 5 . ランダムオラクルモデルにおいて $\mathcal{MSP}\mbox{-}\mathcal{pop}$ と $\mathcal{AMSP}\mbox{-}\mathcal{pop}$ はそれぞれ ${\sf co\mbox{-}CDH}$ および $\varphi-{\sf co\mbox{-}CDH}$ 困難性の下で偽造不可能なマルチ署名と集約マルチ署名スキームである。正確には、 ${\sf co\mbox{-}CDH}$ が $(\tau + (q_{\rm H} + 2 q_{\rm S} + l + 3) \tau_{{\rm exp}_1} + l \cdot \tau_{\rm pair} + O(l(q_{\rm H} + q_{\rm S} + 1)), \epsilon/(q_{\rm H} + q_{\rm S} + 1))$ -困難であれば、ランダムオラクルモデルにおいて $\mathcal{MSP}\mbox{-}\mathcal{pop}$ は $(\tau,q_{\rm S}, q_{\rm H}, \epsilon)$ -偽造不可能である。ここで $l$ は単一のマルチ署名に含まれる署名者の最大値、 $\tau_{{\rm exp}_1}$ はペアリングを計算するために必要な時間である。もし $\varphi-{\sf co\mbox{-}CDH}$ が $(\tau + (q_{\rm H} + 2 q_{\rm S} + l + 3) \tau_{{\rm exp}_1} + \tau_{{\rm exp}_1^n} + l \cdot \tau_{\rm pair} + O(l(q_{\rm H} + q_{\rm S} + 1)), \epsilon / (q_{\rm H} + q_{\rm S} + 1))$ -困難であれば、ランダムオラクルモデルにおいて $\mathcal{AMSP}\mbox{-}\mathcal{pop}$ は $(\tau, q_{\rm S}, q_{\rm H}, \epsilon)$ -偽造不可能である。ここで $\tau_{{\rm exp}_1^n}$ は $\mathbb{G}_1$ で n-multiexponentiation を計算するために必要な時間である。

6.2 PoP を有する Accountable-Subgroup のスキーム

$\mathcal{ASM}\mbox{-}\mathcal{pop}$ での鍵生成、PoP を使用した我々の ASM は上記の $\mathcal{MSP}\mbox{-}\mathcal{pop}$ や $\mathcal{AMSP}\mbox{-}\mathcal{pop}$ と同じである。鍵集約は鍵の集合 $\mathcal{PK} \leftarrow \{(y_1, \pi_1), \ldots, (y_n, \pi_n)\}$ が積 $Y \leftarrow \prod_{i=1}^n y_i$ だけではなく全ての公開鍵のハッシュ $h \leftarrow {\sf H}_3(\mathcal{PK})$ も含んでいると言う点でわずかに異なる。ここで ${\sf H}_3:\{0, 1\}^* \to \mathbb{Z}_q$ は別のハッシュ関数である。集約公開鍵はペア $apk \leftarrow (Y, h)$ で与えられる。このハッシュを含める理由は、 ${\sf H}_2(apk, i)$ への応答をシミュレートするときに、 $i$ が、 $apk$ が集約公開鍵である集合 $\mathcal{PK}$ での対象署名者のインデックスかどうかを知ることができなければならないためである。

グループセットアップ ${\sf GSetup}(sk_i, \mathcal{PI} = \{pk_i, \ldots, pk_n\})$ は $apk = (Y, h) \leftarrow {\sf KAg}(par, \mathcal{PK})$ を計算し、署名者 $j$ に $\mu_{j,i} = {\sf H}_2(apk, j)^{sk_i}$ を送信する。他の全ての署名者 $j \neq i$ から $\mu_{i,j}$ を受け取った後、署名者 $i$ は $\mu_{i,i} \leftarrow {\sf H}_2(apk, i)^{sk_i}$ と計算し、メンバーシップ鍵 $mk_i \leftarrow \prod_{j=1}^n \mu_{i,j}$ を出力する。もし全ての署名者が正直に動作するなら $e(g_1, mk_i) = e(Y, {\sf H}_2(apk, i))$ となる。

公開鍵の積 $pk \leftarrow \prod_{j \in S} pk_j$ が $y \leftarrow \prod_{j \in S} y_j$ に置き換えられることを除いて、署名と検証は $\mathcal{ASM}$ と同じである。

定理 6 . 我々の $\mathcal{ASM\mathcal{-}pop}$ スキームはランダムオラクルモデルにおける Computational $\varphi$ -co-Diffie-Hellman 問題の困難性の下で偽造不可能である。正確には、もし $\varphi{\sf \mbox{-}co\mbox{-}CDH}$ が $(\tau + (q_{\rm H} + q_{\rm G}(l - 1) + q_{\rm S} + 1) \cdot \tau_{{\rm exp}_1} + (2l + 2) \cdot \tau_{\rm pair} + \tau_{{\rm exp}_1^{l+2}}, \epsilon / q_{\rm H} - q_{\rm H} (q_{\rm S} + q_{\rm H}) / q)$ -困難であれば、ランダムオラクルモデルにおいて $(\tau, q_{\rm S}, q_{\rm H}, \epsilon)$ -偽造不可能である。ここで $l$ は任意のグループセットアップに関与する署名者の最大数、 $\tau_{{\rm exp}_1}$ と $\tau_{{\rm exp}_1^l}$ はそれぞれ $\mathbb{G}_1$ のべき乗と $i$ -multiexponentiation の計算に必要な時間を示し、 $\tau_{\rm pair}$ はペアリング操作の計算に必要な時間を示している。

6.3 PoP を有する離散対数からのスキーム

Drijvers ら [21] は $\mathcal{GD\mbox{-}CoSi}$ スキームを提示した。これは不正鍵攻撃から保護するために double-generator Okamoto 署名 [44] と所有の証明を持つ非ペアリング曲線とを組み合わせる。Okamoto 署名を使用すると Bellare-Neven [9] の署名プロトコルでのハッシュの余分なラウンドを回避するが、 $\mathbb{Z}_q$ の追加の元により署名サイズが増加する。あるいは、 $\mathcal{MSDL}$ の PoP 変種である、余分なハッシュラウンドを使用する我々の $\mathcal{MSDL\mbox{-}pop}$ スキームを検討することができる。

$\mathcal{MSDL\mbox{-}pop}$ の鍵ペアを生成するために、署名者は $sk \overset{S}{\leftarrow} \mathbb{Z}_q$ を選択し、 $y \leftarrow g^{sk}$ を計算し、 ${\sf H}_1$ をハッシュ関数として使用して $y$ 上の Schnorr 署名 [48] である所有の証明を追加する。つまり $r \overset{S}{\leftarrow} \mathbb{Z}_q$ を選択し $t \leftarrow g^r$ , $c \leftarrow {\sf H}_1(t, y)$ および $s \leftarrow r + c \cdot sk \bmod q$ を計算する。公開鍵は $pk \leftarrow (y, c, s)$ である。

鍵 $\{(y_1, c_1, s_1), \cdot, (y_n, c_n, s_n)\}$ を集約するために全ての $i = 1, \ldots, n$ に対して最初に $c_i \overset{?}{=} {\sf H}_1(g^s y_i^{-c_i}, y_i)$ を確認する。そうであれば集約公開鍵は $apk \leftarrow \prod_{i=1}^n y_i$ であり、そうでなければ $\perp$ を返す。署名プロトコルは第三ラウンドの署名者が $s_i \leftarrow r_i + c \cdot sk_i \bmod q$ を計算することを除いて $\mathcal{MSDL}$ とほとんど同じである。

$\mathcal{MSDL\mbox{-}pop}$ はランダムオラクルモデルにおける離散対数仮定の下でセキュアである。この証明は $\mathcal{DG\mbox{-}CoSi}$ [21] と同じであるため省略する。

参照

Ahn, J.H., Green, M., Hohenberger, S.: Synchronized aggregate signatures: new definitions, constructions and applications. In: Al-Shaer, E., Keromytis, A.D., Shmatikov, V. (eds.) ACM CCS 10: 17th Conference on Computer and Communications Security. pp. 473–484. ACM Press, Chicago, Illinois, USA (Oct 4–8, 2010)
Andresen, G.: $m$ -of- $n$ standard transactions. Bitcoin improvement proposal (BIP) 0011 (2011)
Bagherzandi, A., Cheon, J.H., Jarecki, S.: Multisignatures secure under the discrete logarithm assumption and a generalized forking lemma. In: Ning, P., Syverson, P.F., Jha, S. (eds.) ACM CCS 08: 15th Conference on Computer and Communications Security. pp. 449–458. ACM Press, Alexandria, Virginia, USA (Oct 27–31, 2008)
Bagherzandi, A., Jarecki, S.: Multisignatures using proofs of secret key possession, as secure as the Diffie-Hellman problem. In: Ostrovsky, R., Prisco, R.D., Visconti, I. (eds.) SCN 08: 6th International Conference on Security in Communication Networks. Lecture Notes in Computer Science, vol. 5229, pp. 218–235. Springer, Heidelberg, Germany, Amalfi, Italy (Sep 10–12, 2008)
Bansarkhani, R.E., Sturm, J.: An efficient lattice-based multisignature scheme with applications to bitcoins. In: Foresti, S., Persiano, G. (eds.) CANS 16: 15th International Conference on Cryptology and Network Security. Lecture Notes in Computer Science, vol. 10052, pp. 140–155. Springer, Heidelberg, Germany, Milan, Italy (Nov 14–16, 2016)
Barreto, P.S.L.M., Lynn, B., Scott, M.: On the selection of pairing-friendly groups. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003: 10th Annual International Workshop on Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 3006, pp. 17–25. Springer, Heidelberg, Germany, Ottawa, Ontario, Canada (Aug 14–15, 2004)
Bellare, M., Namprempre, C., Neven, G.: Unrestricted aggregate signatures. In: Arge, L., Cachin, C., Jurdzinski, T., Tarlecki, A. (eds.) ICALP 2007: 34th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 4596, pp. 411–422. Springer, Heidelberg, Germany, Wroclaw, Poland (Jul 9–13, 2007)
Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The one-more-RSAinversion problems and the security of Chaum’s blind signature scheme. Journal of Cryptology 16(3), 185–215 (Jun 2003)
Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: Juels, A., Wright, R.N., Vimercati, S. (eds.) ACM CCS 06: 13th Conference on Computer and Communications Security. pp. 390–399. ACM Press, Alexandria, Virginia, USA (Oct 30 – Nov 3, 2006)
Boldyreva, A.: Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme. In: Desmedt, Y. (ed.) PKC 2003: 6th International Workshop on Theory and Practice in Public Key Cryptography. Lecture Notes in Computer Science, vol. 2567, pp. 31–46. Springer, Heidelberg, Germany, Miami, FL, USA (Jan 6–8, 2003)
Boldyreva, A., Gentry, C., O’Neill, A., Yum, D.H.: Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing. In: Ning, P., di Vimercati, S.D.C., Syverson, P.F. (eds.) ACM CCS 07: 14th Conference on Computer and Communications Security. pp. 276–285. ACM Press, Alexandria, Virginia, USA (Oct 28–31, 2007)
Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) Advances in Cryptology – EUROCRYPT 2003. Lecture Notes in Computer Science, vol. 2656, pp. 416–432. Springer, Heidelberg, Germany, Warsaw, Poland (May 4–8, 2003)
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd, C. (ed.) Advances in Cryptology – ASIACRYPT 2001. Lecture Notes in Computer Science, vol. 2248, pp. 514–532. Springer, Heidelberg, Germany, Gold Coast, Australia (Dec 9–13, 2001)
Brogle, K., Goldberg, S., Reyzin, L.: Sequential aggregate signatures with lazy verification from trapdoor permutations - (extended abstract). In: Wang, X., Sako, K. (eds.) Advances in Cryptology – ASIACRYPT 2012. Lecture Notes in Computer Science, vol. 7658, pp. 644–662. Springer, Heidelberg, Germany, Beijing, China (Dec 2–6, 2012)
Budroni, A., Pintore, F.: Efficient hash maps to $\mathbb{G}_2$ on BLS curves. Cryptology ePrint Archive, Report 2017/419 (2017), http://eprint.iacr.org/2017/419
Burmester, M., Desmedt, Y., Doi, H., Mambo, M., Okamoto, E., Tada, M., Yoshifuji, Y.: A structured ElGamal-type multisignature scheme. In: Imai, H., Zheng, Y. (eds.) PKC 2000: 3rd International Workshop on Theory and Practice in Public Key Cryptography. Lecture Notes in Computer Science, vol. 1751, pp. 466–483. Springer, Heidelberg, Germany, Melbourne, Victoria, Australia (Jan 18–20, 2000)
Castelluccia, C., Jarecki, S., Kim, J., Tsudik, G.: A robust multisignatures scheme with applications to acknowledgment aggregation. In: Blundo, C., Cimato, S. (eds.) SCN 04: 4th International Conference on Security in Communication Networks. Lecture Notes in Computer Science, vol. 3352, pp. 193–207. Springer, Heidelberg, Germany, Amalfi, Italy (Sep 8–10, 2005)
Certicom Research: Sec 2: Recommended elliptic curve domain parameters. Tech. rep., Certicom Research (2010)
Chang, C.C., Leu, J.J., Huang, P.C., Lee, W.B.: A scheme for obtaining a message from the digital multisignature. In: Imai, H., Zheng, Y. (eds.) PKC’98: 1st International Workshop on Theory and Practice in Public Key Cryptography. Lecture Notes in Computer Science, vol. 1431, pp. 154–163. Springer, Heidelberg, Germany, Pacifico Yokohama, Japan (Feb 5–6, 1998)
Coron, J.S., Naccache, D.: Boneh et al.’s k-element aggregate extraction assumption is equivalent to the Diffie-Hellman assumption. In: Laih, C.S. (ed.) Advances in Cryptology – ASIACRYPT 2003. Lecture Notes in Computer Science, vol. 2894, pp. 392–397. Springer, Heidelberg, Germany, Taipei, Taiwan (Nov 30 – Dec 4, 2003)
Drijvers, M., EdalatNejad, K., Ford, B., Neven, G.: Okamoto beats Schnorr: On the provable security of multi-signatures. Cryptology ePrint Archive, Report 2018/417 (2018), https://eprint.iacr.org/2018/417
Fuentes-Casta˜neda, L., Knapp, E., Rodr´ıguez-Henr´ıquez, F.: Faster hashing to ð2. In: Miri, A., Vaudenay, S. (eds.) SAC 2011: 18th Annual International Workshop on Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 7118, pp. 412–430. Springer, Heidelberg, Germany, Toronto, Ontario, Canada (Aug 11–12, 2012)
Gentry, C., O’Neill, A., Reyzin, L.: A unified framework for trapdoor-permutationbased sequential aggregate signatures. In: Abdalla, M., Dahab, R. (eds.) PKC 2018: 21st International Conference on Theory and Practice of Public Key Cryptography, Part II. Lecture Notes in Computer Science, vol. 10770, pp. 34–57. Springer, Heidelberg, Germany, Rio de Janeiro, Brazil (Mar 25–29, 2018)
Gentry, C., Ramzan, Z.: Identity-based aggregate signatures. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006: 9th International Conference on Theory and Practice of Public Key Cryptography. Lecture Notes in Computer Science, vol. 3958, pp. 257–273. Springer, Heidelberg, Germany, New York, NY, USA (Apr 24–26, 2006)
Hardjono, T., Zheng, Y.: A practical digital multisignature scheme based on discrete logarithms. In: Seberry, J., Zheng, Y. (eds.) Advances in Cryptology – AUSCRYPT’92. Lecture Notes in Computer Science, vol. 718, pp. 122–132. Springer, Heidelberg, Germany, Gold Coast, Queensland, Australia (Dec 13–16, 1993)
Harn, L.: Group-oriented $(t,n)$ threshold digital signature scheme and digital multisignature. IEE Proceedings-Computers and Digital Techniques 141(5), 307–313 (1994)
Horster, P., Michels, M., Petersen, H.: Meta-multisignature schemes based on the discrete logarithm problem. In: Information Securitythe Next Decade. pp. 128–142. Springer (1995)
Itakura, K., Nakamura, K.: A public-key cryptosystem suitable for digital multisignatures. Tech. rep., NEC Research and Development (1983)
Komano, Y., Ohta, K., Shimbo, A., Kawamura, S.: Formal security model of multisignatures. In: Katsikas, S.K., Lopez, J., Backes, M., Gritzalis, S., Preneel, B. (eds.) ISC 2006: 9th International Conference on Information Security. Lecture Notes in Computer Science, vol. 4176, pp. 146–160. Springer, Heidelberg, Germany, Samos Island, Greece (Aug 30 – Sep 2, 2006)
Le, D.P., Bonnecaze, A., Gabillon, A.: Multisignatures as secure as the DiffieHellman problem in the plain public-key model. In: Shacham, H., Waters, B. (eds.) PAIRING 2009: 3rd International Conference on Pairing-based Cryptography. Lecture Notes in Computer Science, vol. 5671, pp. 35–51. Springer, Heidelberg, Germany, Palo Alto, CA, USA (Aug 12–14, 2009)
Li, C.M., Hwang, T., Lee, N.Y.: Threshold-multisignature schemes where suspected forgery implies traceability of adversarial shareholders. In: Santis, A.D. (ed.) Advances in Cryptology – EUROCRYPT’94. Lecture Notes in Computer Science, vol. 950, pp. 194–204. Springer, Heidelberg, Germany, Perugia, Italy (May 9–12, 1995)
Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., Waters, B.: Sequential aggregate signatures and multisignatures without random oracles. In: Vaudenay, S. (ed.) Advances in Cryptology – EUROCRYPT 2006. Lecture Notes in Computer Science, vol. 4004, pp. 465–485. Springer, Heidelberg, Germany, St. Petersburg, Russia (May 28 – Jun 1, 2006)
Lysyanskaya, A., Micali, S., Reyzin, L., Shacham, H.: Sequential aggregate signatures from trapdoor permutations. In: Cachin, C., Camenisch, J. (eds.) Advances in Cryptology – EUROCRYPT 2004. Lecture Notes in Computer Science, vol. 3027, pp. 74–90. Springer, Heidelberg, Germany, Interlaken, Switzerland (May 2–6, 2004)
Ma, C., Weng, J., Li, Y., Deng, R.: Efficient discrete logarithm based multisignature scheme in the plain public key model. Designs, Codes and Cryptography 54(2), 121–133 (2010)
Maxwell, G., Poelstra, A., Seurin, Y., Wuille, P.: Simple schnorr multi-signatures with applications to bitcoin. Cryptology ePrint Archive, Report 2018/068 (2018), https://eprint.iacr.org/2018/068/20180118:124757
Maxwell, G., Poelstra, A., Seurin, Y., Wuille, P.: Simple schnorr multi-signatures with applications to bitcoin. Cryptology ePrint Archive, Report 2018/068 (2018), https://eprint.iacr.org/2018/068/20180520:191909
Merkle, R.C.: A digital signature based on a conventional encryption function. In: Pomerance, C. (ed.) Advances in Cryptology – CRYPTO’87. Lecture Notes in Computer Science, vol. 293, pp. 369–378. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 16–20, 1988)
Micali, S., Ohta, K., Reyzin, L.: Accountable-subgroup multisignatures: Extended abstract. In: ACM CCS 01: 8th Conference on Computer and Communications Security. pp. 245–254. ACM Press, Philadelphia, PA, USA (Nov 5–8, 2001)
Michels, M., Horster, P.: On the risk of disruption in several multiparty signature schemes. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 334–345. Springer (1996)
Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2008), http://bitcoin.org/bitcoin.pdf
Neven, G.: Efficient sequential aggregate signed data. In: Smart, N.P. (ed.) Advances in Cryptology – EUROCRYPT 2008. Lecture Notes in Computer Science, vol. 4965, pp. 52–69. Springer, Heidelberg, Germany, Istanbul, Turkey (Apr 13–17, 2008)
Ohta, K., Okamoto, T.: A digital multisignature scheme based on the Fiat-Shamir scheme. In: Imai, H., Rivest, R.L., Matsumoto, T. (eds.) Advances in Cryptology – ASIACRYPT’91. Lecture Notes in Computer Science, vol. 739, pp. 139–148. Springer, Heidelberg, Germany, Fujiyoshida, Japan (Nov 11–14, 1993)
Ohta, K., Okamoto, T.: Multi-signature schemes secure against active insider attacks. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 82(1), 21–31 (1999)
Okamoto, T.: Provably secure and practical identification schemes and corresponding signature schemes. In: Brickell, E.F. (ed.) Advances in Cryptology – CRYPTO’92. Lecture Notes in Computer Science, vol. 740, pp. 31–53. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 16–20, 1993)
Park, S., Park, S., Kim, K., Won, D.: Two efficient RSA multisignature schemes. In: Han, Y., Okamoto, T., Qing, S. (eds.) ICICS 97: 1st International Conference on Information and Communication Security. Lecture Notes in Computer Science, vol. 1334, pp. 217–222. Springer, Heidelberg, Germany, Beijing, China (Nov 11–14, 1997)
Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. Journal of Cryptology 13(3), 361–396 (2000)
Ristenpart, T., Yilek, S.: The power of proofs-of-possession: Securing multiparty signatures against rogue-key attacks. In: Naor, M. (ed.) Advances in Cryptology – EUROCRYPT 2007. Lecture Notes in Computer Science, vol. 4515, pp. 228–245. Springer, Heidelberg, Germany, Barcelona, Spain (May 20–24, 2007)
Schnorr, C.P.: Efficient signature generation by smart cards. Journal of Cryptology 4(3), 161–174 (1991)
Scott, M., Benger, N., Charlemagne, M., Perez, L.J.D., Kachisa, E.J.: Fast hashing to $g_2$ on pairing-friendly curves. In: Shacham, H., Waters, B. (eds.) PAIRING 2009: 3rd International Conference on Pairing-based Cryptography. Lecture Notes in Computer Science, vol. 5671, pp. 102–113. Springer, Heidelberg, Germany, Palo Alto, CA, USA (Aug 12–14, 2009)

A 所有の証明を有するスキームのセキュリティ証明

A.1 $\mathcal{MSP\mathcal{-}pop}$ と $\mathcal{AMSP\mathcal{-}pop}$ に対するセキュリティ証明

(原文参照)

A.2 $\mathcal{ASM\mathcal{-}pop}$ に対するセキュリティ証明