アキュムレータ（暗号化）

暗号学において、アキュムレータは一方向のメンバーシップハッシュ関数です。これにより、ユーザーは、集合の個々のメンバーを明らかにすることなく、潜在的な候補が特定の集合のメンバーであることを証明できます。この概念は、1993年にジョシュ・ベナローとマイケル・デ・マーレによって正式に導入されました。 ^{[1] [2]}

文献ではいくつかの正式な定義が提案されている。このセクションでは、提案者別に概ね時系列順にリストする。^[2]

ベナローとデ・マーレは、一方向ハッシュ関数を次の3つの性質を満たす関数の族として定義している。^{[1] [2]}${\displaystyle h_{\ell }:X_{\ell }\times Y_{\ell }\to Z_{\ell }}$

1. すべての に対して、 の時間で計算できます。(ここで、「poly」記号は、指定されていないが固定された多項式を表します。)${\displaystyle \ell \in \mathbb {Z} ,x\in X_{\ell },y\in Y_{\ell }}$${\displaystyle h_{\ell}(x,y)}$${\displaystyle {\text{poly}}(\ell,|x|,|y|)}$
2. 十分に大きい に対して、入力 をマップし、無視できる確率を超える値を見つける確率多項式時間アルゴリズムは存在しません。${\displaystyle \ell}$${\displaystyle \ell \in \mathbb {Z} ,(x,y)\in X_{\ell }\times Y_{\ell },y'\in Y_{\ell }}$${\displaystyle x'\in X_{\ell}}$${\displaystyle h_{\ell}(x,y)=h_{\ell}(x',y')}$
3. すべての に対して、 が成り立ちます。(この性質を満たす関数は準可換 と呼ばれます。)${\displaystyle \ell \in \mathbb {Z} ,x\in X_{\ell },y_{1},y_{2}\in Y_{\ell }}$${\displaystyle h(h(x,y_{1}),y_{2})=h(h(x,y_{2}),y_{1})}$

(最初の 2 つの特性により、暗号ハッシュ関数の通常の定義が復元されます。)

このような関数から、集合の「累積ハッシュ」と開始値を と定義します。結果は、準可換であるため、要素の順序に依存しません。 ^{[1] [2]}${\displaystyle \{y_{1},\dots ,y_{m}\}}$${\displaystyle x}$${\displaystyle z}$${\displaystyle h(h(\cdots h(h(x,y_{1}),y_{2}),\dots ,y_{m-1}),y_{m})}$${\displaystyle y_{1},y_{2},...,y_{n}}$${\displaystyle h}$

が暗号システムの一部のユーザーに属している場合、誰でも累積値を計算できます。また、 のユーザーはの部分累積値を計算できます。次に、ユーザーはを認証するために、ペアを他の任意の部分に提供できます。 ${\displaystyle y_{1},y_{2},...,y_{n}}$${\displaystyle z.}$${\displaystyle y_{i}}$${\displaystyle z_{i}}$${\displaystyle (y_{1},...,y_{i-1},y_{i+1},...,y_{n})}$${\displaystyle h(z_{i},y_{i})=z.}$${\displaystyle i-}$${\displaystyle (z_{i},y_{i})}$${\displaystyle y_{i}}$

準可換ハッシュ関数の基本的な機能は定義からすぐにはわかりません。これを修正するために、バリッチとフィッツマンは、以下のコンポーネントで構成されるアキュムレータスキームの概念という、もう少し一般的な定義を定義しました。 ^{[2] [3]}

1. Gen: 2 つのパラメータ(それぞれセキュリティ パラメータと安全に蓄積できる値の数)を受け取り、適切なキーを返す確率アルゴリズム。${\displaystyle \lambda ,N}$${\displaystyle k}$
2. Eval: キーと累積セットを受け取り、累積値と補助情報を返す確率アルゴリズム。Eval はに対して決定論的である必要があると主張します。${\displaystyle k}$${\displaystyle Y:=\{y_{1},\dots ,y_{N'}\}}$${\displaystyle N'\leq N}$${\displaystyle z}$${\displaystyle aux}$${\displaystyle z}$
3. Wit: キー、値、何らかの集合の累積値、および何らかの補助情報を受け取り、証拠または特殊記号を返す確率アルゴリズム。 の場合、Wit は証拠を返し、それ以外の場合は Wit は を返すことを主張します。${\displaystyle k}$${\displaystyle y}$${\displaystyle z}$${\displaystyle Y}$${\displaystyle aux}$${\displaystyle w}$${\displaystyle \bot }$${\displaystyle y\in L}$${\displaystyle \bot }$
4. Ver:キー、値、証跡、累積値を受け取り、Yes/No 値を返す決定論的アルゴリズム。 がタプルで Wit を実行して生成され、 が何らかの で Eval を実行して生成され、 が任意に選択され、 がGen を実行して選択された場合、 Ver は常に Yes を返すことを要求します。${\displaystyle k}$${\displaystyle y}$${\displaystyle w}$${\displaystyle z}$${\displaystyle w}$${\displaystyle (k,y,z,aux)}$${\displaystyle z,aux}$${\displaystyle k,L}$${\displaystyle L}$${\displaystyle k}$

上記の手法を使用すると、任意の準可換ハッシュ関数からアキュムレータスキームを定義できることは比較的簡単にわかります。^[2]

多くのアプリケーションでは、累積値のセットが何度も変更されることが観察されます。素朴に言えば、毎回アキュムレータの計算を完全にやり直すことができますが、これは非効率的である可能性があります。特に、セットが非常に大きく、変更が非常に小さい場合はそうです。この直感を形式化するために、CamenishとLysyanskayaは、通常のアキュムレータスキームの4つのコンポーネントに加えて、さらに3つのコンポーネントで構成される動的アキュムレータスキームを定義しました。 ^{[2] [4]}

1. Add: キー、累積値、累積する別の値を取り込み、新しい累積値と補助情報を返す (おそらく確率的な) アルゴリズム。が何らかのセット を累積することによって生成された場合、 はセット を累積することによって生成されたかのようになることを主張します。${\displaystyle k}$${\displaystyle z}$${\displaystyle y}$${\displaystyle z'}$${\displaystyle aux}$${\displaystyle z}$${\displaystyle L}$${\displaystyle z'}$${\displaystyle L\cup \{y\}}$
2. Del: キー、累積値、累積する別の値を受け取り、新しい累積値と補助情報を返す (おそらく確率的な) アルゴリズム。が何らかのセットを累積することによって生成された場合、 はセットを累積することによって生成されたかのようになることを主張します。${\displaystyle k}$${\displaystyle z}$${\displaystyle y}$${\displaystyle z'}$${\displaystyle aux}$${\displaystyle z}$${\displaystyle L}$${\displaystyle z'}$${\displaystyle L\backslash \{y\}}$
3. Upd: キー、値、証人、累積値、補助情報を受け取り、新しい証人を返す決定論的アルゴリズム。が Gen によって生成され、セット の一部であり、のメンバーであることの証人であり、 がの累積値であり、Add または Del を実行することによって生成された場合、 は新しいセットのメンバーであることの証人になります。${\displaystyle k}$${\displaystyle y}$${\displaystyle w}$${\displaystyle z}$${\displaystyle aux}$${\displaystyle w'}$${\displaystyle k}$${\displaystyle y}$${\displaystyle L}$${\displaystyle w}$${\displaystyle y}$${\displaystyle L}$${\displaystyle z}$${\displaystyle L}$${\displaystyle aux}$${\displaystyle w'}$${\displaystyle y}$

FazioとNicolosiは、Add、Del、UpdはEvalとWitを再実行することでシミュレートできるため、この定義では根本的に新しい機能は追加されないと指摘している。^[2]

一例として、大きな素数の乗算があげられる。これは暗号アキュムレータである。なぜなら、合成数を因数分解するには（少なくとも推測によれば）超多項式の時間がかかるが、素数を整数に割ってそれが因数の 1 つであるかどうかをチェックしたり因数分解したりするには、ほんの少しの時間（多項式のサイズ）しかかからないからである。新しいメンバーは、それぞれ数を乗算するか因数分解することで因数集合に追加または減算することができる。このシステムでは、単一の共有素数を蓄積した 2 つのアキュムレータは、素数の事前知識がなくても（そうでなければ、アキュムレータの素因数分解を行って発見する必要がある）、GCD を計算することで簡単に素数を発見できる。^[要出典]

より実用的なアキュムレータは準可換ハッシュ関数を使用するため、アキュムレータのサイズはメンバーの数に応じて増加しません。たとえば、Benaloh と de Mare は、RSAにヒントを得た暗号アキュムレータを提案しています。これは、ある合成数 に対する準可換関数です。彼らは、 を固定整数 (つまり、2 つの安全な素数の積)として選択することを推奨しています。 ^[1] Barić と Pfitzmann は、 が素数で最大 に制限される変形を提案しました(この定数は に非常に近いですが、 の素因数分解に関する情報を漏らしません)。^{[2] [3]}${\displaystyle h(x,y):=x^{y}{\pmod {n}}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle y}$${\displaystyle n/4}$${\displaystyle \phi (n)}$${\displaystyle n}$

デビッド・ナカチェは1993年に、すべての定数に対して準可換性があることを観察し、以前のRSAに触発された暗号アキュムレータを一般化しました。ナカチェはまた、ディクソン多項式が次数で準可換性があることを指摘しましたが、この関数族が一方向であるかどうかは不明です。^[1]${\displaystyle e_{n,c}(x,y):=x^{y}c^{y-1}{\pmod {n}}}$${\displaystyle c,n}$

1996 年、ニーバーグはランダムオラクルモデルにおいて情報理論的に安全であることが証明できるアキュムレータを構築しました。安全に蓄積できる項目の数の上限とセキュリティパラメータを選択し、定数を の整数倍( と書けるように)として定義し、暗号的に安全なハッシュ関数とします。キーをランダムな ビットのビット文字列として選択します。次に、ニーバーグの方式を使用して蓄積するには、準可換ハッシュ関数 を使用します。ここで、 はビット単位の and演算であり、 は入力を長さ の ビットのビット文字列のシーケンスとして解釈し、すべて 0 のビット文字列を 1 つの 0 に、その他のビット文字列を 1 つに置き換えて、結果を出力する関数です。^{[2] [5]}${\displaystyle N=2^{d}}$${\displaystyle \lambda }$${\displaystyle \ell :\approx {\frac {e}{\log _{2}(e)}}\lambda N\log _{2}(N)}$${\displaystyle d}$${\displaystyle \ell =rd}$${\displaystyle H:\{0,1\}^{*}\to \{0,1\}^{\ell }}$${\displaystyle k}$${\displaystyle r}$${\displaystyle h(x,y):=x\odot \alpha _{r}(H(y))}$${\displaystyle \odot }$${\displaystyle \alpha _{r}:\{0,1\}^{\ell }\to \{0,1\}^{r}}$${\displaystyle d}$${\displaystyle r}$

ハーバーとストルネッタは1990年に、アキュムレータを使って暗号連鎖を通じて文書にタイムスタンプを付けることができることを示しました。（この概念は、現代の暗号ブロックチェーンの概念を先取りしたものです。）^{[1] [2] [6]}ベナローとデ・マーレは1991年に、時間をラウンドに離散化することに基づく代替方式を提案しました。^{[1] [7]}

Benaloh と de Mare は、アキュムレータを使用すると、大人数のグループが後でお互いを認識できることを示しました (Fazio と Nicolosi はこれを「ID エスクロー」状況と呼んでいます)。各人が自分のアイデンティティを表す を選択し、グループが集合的に公開アキュムレータと秘密 を選択します。次に、グループはハッシュ関数と、秘密と公開アキュムレータに関するグループのすべてのアイデンティティの累積ハッシュを公開または保存します。同時に、グループの各メンバーは、自分のアイデンティティ値と、メンバー以外のグループのすべてのアイデンティティの累積ハッシュの両方を保持します。(大人数のグループがお互いを信頼していない場合、または RSA に触発されたアキュムレータの場合のようにアキュムレータに暗号化トラップドアがある場合は、セキュアなマルチパーティ計算によって累積ハッシュを計算できます。) 主張されたメンバーが実際にグループに属していたことを後で検証するには、自分のアイデンティティと個人の累積ハッシュ (またはそのゼロ知識証明) を提示します。主張されたメンバーのアイデンティティを蓄積し、それをグループ全体の蓄積されたハッシュと照合することで、誰でもグループのメンバーを検証することができます。^{[1] [2]}動的アキュムレータ方式では、後からメンバーを追加したり削除したりすることも簡単です。^{[2] [4]}${\displaystyle y}$${\displaystyle h}$${\displaystyle x}$${\displaystyle x}$${\displaystyle y}$

暗号アキュムレータは、他の暗号的に安全なデータ構造を構築するためにも使用できます。

• バリッチとフィッツマンは、圧縮特性を利用することで、一定のスペースのみでフェイルストップ署名を構築できることを示している。^{[2] [3]}
• Goodrichらは、サイズを意識せず、効率的で動的な認証辞書を構築した（これにより、信頼できないディレクトリがメンバーシップクエリに対して暗号的に検証可能な回答を返すことができる）。^{[2] [8]}
• パパマントゥらは暗号的に安全なハッシュテーブルを構築し、その機能はリモートで保存しても認証できるようになった。^[9]

このコンセプトは、ビットコインにゼロコインを追加したことで新たな関心を集めている。ゼロコインは、暗号アキュムレータを使用してビットコインブロックチェーン内の追跡可能なリンクを排除し、取引を匿名かつよりプライベートなものにする。^{[10] [11] [12]}より具体的には、ゼロコインを鋳造（作成）するには、コインと、秘密のランダム値を持つシリアル番号への暗号コミットメントを公開する（正しいフォーマットであればすべてのユーザーが受け入れる）。ゼロコインを使う（取り戻す）には、ゼロコインのシリアル番号と、要求されたシリアル番号に関連する公開されたコミットメントを知っているという非対話型のゼロ知識証明を公開し、コインを要求（NIZKPが有効であり、シリアル番号が以前に登場していない限りすべてのユーザーが受け入れる）。^{[10] [11] Zerocoinの最初の提案以来、} Zerocashプロトコルに引き継がれ、現在はビットコインのコードベースに基づいたデジタル通貨であるZcashに開発されています。 ^{[13] [14]}

• 暗号化
• ゼロ知識証明