ネットワークコーディングのための準同型署名

ネットワーク コーディングは、ネットワークの帯域幅を最適に使用して情報フローを最大化することが示されていますが、この方式は本質的に、ネットワーク内の悪意のあるノードによる汚染攻撃に対して非常に脆弱です。ガベージを挿入するノードは、多くの受信者にすぐに影響を与える可能性があります。受信パケットの少なくとも 1 つが破損している場合、(正直なノードであっても) 出力が破損するため、ネットワーク パケットの汚染は急速に広がります。

攻撃者は、署名を偽造するかハッシュ関数で衝突を発生させることで、たとえ暗号化されていたとしても、簡単にパケットを破壊できます。これにより、攻撃者はパケットにアクセスし、それを破壊することができます。Denis Charles、Kamal Jain、Kristin Lauterは、汚染攻撃を防ぐためにネットワークコーディングで使用する新しい準同型暗号化署名スキームを設計しました。 ^[1]

署名の準同型性により、ノードは署名機関に問い合わせることなく、受信パケットの任意の線形結合に署名できます。この方式では、パケットの生成に使用された線形結合を開示せずにノードがパケットの線形結合に署名することは計算上不可能です。さらに、離散対数問題の困難性と計算楕円曲線 Diffie-Hellman のよく知られた暗号仮定の下で、署名方式が安全であることを証明できます。

を有向グラフとします。ここでは集合で、その要素は頂点またはノードと呼ばれ、 はアーク、有向エッジ、または矢印と呼ばれる頂点の順序付きペアの集合です。ソースは、頂点の集合にファイルを送信したいと考えています。ベクトル空間(次元 とします) を選択します。ここで は素数であり、送信されるデータをベクトルの束と見なします。次に、ソースはを設定することによって拡張ベクトルを作成します。ここで はベクトル の - 番目の座標です。で最初の「1」が現れる前はゼロです。一般性を失うことなく、ベクトルが線形独立 であると仮定できます。これらのベクトルによって張られる( の)線形部分空間を で表します。各出力エッジは、エッジの起点である頂点に入るベクトルの線形結合 を計算します。つまり、 ${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle E}$${\displaystyle s\in V}$${\displaystyle D}$${\displaystyle T\subseteq V}$ ${\displaystyle W/\mathbb {F} _{p}}$${\displaystyle d}$${\displaystyle p}$${\displaystyle w_{1},\ldots ,w_{k}\in W}$${\displaystyle v_{1},\ldots ,v_{k}}$${\displaystyle v_{i}=(0,\ldots ,0,1,\ldots ,0,w_{i_{1}},\ldots ,w{i_{d}})}$${\displaystyle w_{i_{j}}}$${\displaystyle j}$${\displaystyle w_{i}}$${\displaystyle (i-1)}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle \mathbb {F} _{p}^{k+d}}$${\displaystyle V}$${\displaystyle e\in E}$${\displaystyle y(e)}$${\displaystyle v=in(e)}$

${\displaystyle y(e)=\sum _{f:\mathrm {out} (f)=v}(m_{e}(f)y(f))}$

ここで です。ソースはベクトル を運ぶ入力エッジを持つとします。帰納法により、任意のエッジ上のベクトルは線形結合であり、 のベクトルであることがわかります。k 次元ベクトルは、ベクトル の最初のk座標です。行がベクトルである行列(ここでは頂点 の入力エッジ) を のグローバル符号化行列と呼び、 と表記します。実際には、符号化ベクトルはランダムに選択されるため、行列は高い確率で逆行列になります。したがって、受信側は、受信時に次を解くことで 見つけることができます。${\displaystyle m_{e}(f)\in \mathbb {F} _{p}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle w_{i}}$${\displaystyle y(e)}$${\displaystyle y(e)=\sum _{1\leq i\leq k}(g_{i}(e)v_{i})}$${\displaystyle V}$${\displaystyle g(e)=(g_{1}(e),\ldots ,g_{k}(e))}$${\displaystyle y(e)}$${\displaystyle g(e_{1}),\ldots ,g(e_{k})}$${\displaystyle e_{i}}$${\displaystyle t\in T}$${\displaystyle t}$${\displaystyle G_{t}}$${\displaystyle G_{t}}$${\displaystyle y_{1},\ldots ,y_{k}}$${\displaystyle w_{1},\ldots ,w_{k}}$

${\displaystyle {\begin{bmatrix}y'\\y_{2}'\\\vdots \\y_{k}'\end{bmatrix}}=G_{t}{\begin{bmatrix}w_{1}\\w_{2}\\\vdots \\w_{k}\end{bmatrix}}}$

ここで、 はベクトルの最初の座標を削除することによって形成されるベクトルです。 ${\displaystyle y_{i}'}$${\displaystyle k}$${\displaystyle y_{i}}$

各受信者は、のランダムな線形結合であるベクトルを受け取ります。実際、 ${\displaystyle t\in T}$${\displaystyle k}$${\displaystyle y_{1},\ldots ,y_{k}}$${\displaystyle v_{i}}$

${\displaystyle y_{i}=(\alpha _{i_{1}},\ldots ,\alpha _{i_{k}},a_{i_{1}},\ldots ,a_{i_{d}})}$

それから

${\displaystyle y_{i}=\sum _{1\leq j\leq k}(\alpha _{ij}v_{j}).}$

したがって、線形変換を逆にすると、 を高い確率で見つけることができます。 ${\displaystyle v_{i}}$

クローン、フリードマン、マジエールは2004年に次のようなハッシュ関数が存在するという 理論^[2]を提唱した。 ${\displaystyle H:V\longrightarrow G}$

• ${\displaystyle H}$衝突耐性があり、見つけるのが難しく、次のようなものになります。${\displaystyle x}$${\displaystyle y}$${\displaystyle H(x)=H(y)}$
• ${\displaystyle H}$は準同型です– 。${\displaystyle H(x+y)=H(x)+H(y)}$

その後、サーバーは各受信者に安全に配信し、 ${\displaystyle H(v_{i})}$

${\displaystyle y=\sum _{1\leq i\leq k}(\alpha _{i}v_{i})}$

確認できるのは

${\displaystyle H(y)=\sum _{1\leq i\leq k}(\alpha _{i}H(v_{i}))}$

この方法の問題点は、サーバーが各受信者に安全な情報を転送する必要があることです。ハッシュ関数は、別の安全なチャネルを介してネットワーク内のすべてのノードに送信する必要があります。計算にはコストがかかり、安全な送信も経済的ではありません。 ${\displaystyle H}$${\displaystyle H}$${\displaystyle H}$

1. 汚染の検出に加えて認証を確立します。
2. 安全なハッシュダイジェストを配布する必要はありません。
3. 一般的には、より短いビット長で十分です。長さ 180 ビットの署名は、1024 ビットの RSA 署名と同等のセキュリティを備えています。
4. 公開情報は、その後のファイル送信では変更されません。

署名の準同型性により、ノードは署名機関に連絡することなく、受信パケットの任意の線形結合に署名できます。

有限体上の楕円曲線暗号は、有限体上の楕円曲線の代数構造に基づいた公開鍵暗号へのアプローチです。

が2の累乗でも3の累乗でもない有限体であるとする。すると、上の楕円曲線は次の式の曲線となる。 ${\displaystyle \mathbb {F} _{q}}$${\displaystyle q}$${\displaystyle E}$${\displaystyle \mathbb {F} _{q}}$

${\displaystyle y^{2}=x^{3}+ax+b,\,}$

ここで、${\displaystyle a,b\in \mathbb {F} _{q}}$${\displaystyle 4a^{3}+27b^{2}\not =0}$

それでは、 ${\displaystyle K\supseteq \mathbb {F} _{q}}$

${\displaystyle E(K)=\{(x,y)|y^{2}=x^{3}+ax+b\}\bigcup \{O\}}$

O を単位元とするアーベル群を形成します。群演算を効率的に実行できます。

ヴェイユのペアリングは、楕円曲線上の関数による単位根の構築であり、の捩れ部分群上のペアリング(双線型形式、ただし乗法表記)を構成するような方法です。を楕円曲線とし、を の代数閉包とします。が整数で、体 の特性と互いに素である場合、 -捩れ点 の群 が成り立ちます。 ${\displaystyle E}$${\displaystyle E}$${\displaystyle E/\mathbb {F} _{q}}$${\displaystyle \mathbb {\bar {F}} _{q}}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle m}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle m}$${\displaystyle E[m]={P\in E(\mathbb {\bar {F}} _{q}):mP=O}}$

が楕円曲線である場合、 ${\displaystyle E/\mathbb {F} _{q}}$${\displaystyle \gcd(m,q)=1}$

${\displaystyle E[m]\cong (\mathbb {Z} /m\mathbb {Z} )*(\mathbb {Z} /m\mathbb {Z} )}$

次のようなマップがあります: ${\displaystyle e_{m}:E[m]*E[m]\rightarrow \mu _{m}(\mathbb {F} _{q})}$

1. (双線形) 。${\displaystyle e_{m}(P+R,Q)=e_{m}(P,Q)e_{m}(R,Q){\text{ and }}e_{m}(P,Q+R)=e_{m}(P,Q)e_{m}(P,R)}$
2. (非退化)すべてのPに対して は、 を意味します。${\displaystyle e_{m}(P,Q)=1}$${\displaystyle Q=O}$
3. (交互に) 。${\displaystyle e_{m}(P,P)=1}$

また、効率的に計算することができる。^[3]${\displaystyle e_{m}}$

を素数、を素数べき乗とします。 を次元のベクトル空間、となる楕円曲線とします。を次のように定義します。 関数はからへの任意の準同型です。 ${\displaystyle p}$${\displaystyle q}$${\displaystyle V/\mathbb {F} _{p}}$${\displaystyle D}$${\displaystyle E/\mathbb {F} _{q}}$${\displaystyle P_{1},\ldots ,P_{D}\in E[p]}$${\displaystyle h:V\longrightarrow E[p]}$${\displaystyle h(u_{1},\ldots ,u_{D})=\sum _{1\leq i\leq D}(u_{i}P_{i})}$${\displaystyle h}$${\displaystyle V}$${\displaystyle E[p]}$

サーバーはで秘密にを選択し、となる p-ねじれ点を公開し、 についても を公開します。ベクトルの署名は、 注: h の計算は準同型なので、この署名は準同型です。 ${\displaystyle s_{1},\ldots ,s_{D}}$${\displaystyle \mathbb {F} _{p}}$${\displaystyle Q}$${\displaystyle e_{p}(P_{i},Q)\not =1}$${\displaystyle (P_{i},s_{i}Q)}$${\displaystyle 1\leq i\leq D}$${\displaystyle v=u_{1},\ldots ,u_{D}}$${\displaystyle \sigma (v)=\sum _{1\leq i\leq D}(u_{i}s_{i}P_{i})}$

およびその署名が与えられている場合、 ${\displaystyle v=u_{1},\ldots ,u_{D}}$${\displaystyle \sigma }$

${\displaystyle {\begin{aligned}e_{p}(\sigma ,Q)&=e_{p}\left(\sum _{1\leq i\leq D}(u_{i}s_{i}P_{i}),Q\right)\\&=\prod _{i}e_{p}(u_{i}s_{i}P_{i},Q)\\&=\prod _{i}e_{p}(u_{i}P_{i},s_{i}Q)\end{aligned}}}$

検証では、Weil ペアリングの双線形性が重要な役割を果たします。

サーバーは各 について を計算します。 を送信します。計算中 に各エッジで 楕円曲線 の 計算も行います 。 ${\displaystyle \sigma (v_{i})}$${\displaystyle 1\leq i\leq k}$${\displaystyle v_{i},\sigma (v_{i})}$${\displaystyle e}$${\displaystyle y(e)=\sum _{f\in E:\mathrm {out} (f)=\mathrm {in} (e)}(m_{e}(f)y(f))}$${\displaystyle \sigma (y(e))=\sum _{f\in E:\mathrm {out} (f)=\mathrm {in} (e)}(m_{e}(f)\sigma (y(f)))}$${\displaystyle E}$

署名は、座標が にある楕円曲線上の点です。したがって、署名のサイズはビット (これはとの相対的なサイズに応じて、ビットの定数倍になります) であり、これが転送オーバーヘッドです。各頂点での署名の計算にはビット操作が必要です。ここで、 は頂点 の入次数です。署名の検証にはビット操作が必要です。 ${\displaystyle \mathbb {F} _{q}}$${\displaystyle 2\log q}$${\displaystyle log(p)}$${\displaystyle p}$${\displaystyle q}$${\displaystyle h(e)}$${\displaystyle O(d_{in}\log p\log ^{1+\epsilon }q)}$${\displaystyle d_{in}}$${\displaystyle in(e)}$${\displaystyle O((d+k)\log ^{2+\epsilon }q)}$

攻撃者はハッシュ関数の下で衝突を発生させることができます。

与えられたポイントが見つかっ た場合${\displaystyle (P_{1},\ldots ,P_{r})}$${\displaystyle E[p]}$${\displaystyle a=(a_{1},\ldots ,a_{r})\in \mathbb {F} _{p}^{r}}$${\displaystyle b=(b_{1},\ldots ,b_{r})\in \mathbb {F} _{p}^{r}}$

そして、 ${\displaystyle a\not =b}$

${\displaystyle \sum _{1\leq i\leq r}(a_{i}P_{i})=\sum _{1\leq j\leq r}(b_{j}P_{j}).}$

命題: 楕円曲線上の順序の巡回群上の離散対数からハッシュ衝突へ の多項式時間短縮が存在します。${\displaystyle p}$

の場合、 が得られます。したがってとなります。 および であると主張します。と仮定すると が得られますが、 は順序の点(素数) であるため となります。言い換えるとではとなります。これはと がで異なるペアであるという仮定と矛盾します。したがって が得られます。ここで、逆数は を法として取られます。 ${\displaystyle r=2}$${\displaystyle xP+yQ=uP+vQ}$${\displaystyle (x-u)P+(y-v)Q=0}$${\displaystyle x\not =u}$${\displaystyle y\not =v}$${\displaystyle x=u}$${\displaystyle (y-v)Q=0}$${\displaystyle Q}$${\displaystyle p}$${\displaystyle y-u\equiv 0{\bmod {p}}}$${\displaystyle y=v}$${\displaystyle \mathbb {F} _{p}}$${\displaystyle (x,y)}$${\displaystyle (u,v)}$${\displaystyle \mathbb {F} _{2}}$${\displaystyle Q=-(x-u)(y-v)^{-1}P}$${\displaystyle p}$

r > 2 の場合、2 つの方法のいずれかを実行できます。前と同じようにとを取り、 を > 2と設定するか(この場合、証明は の場合に帰着します)、と を取ります ( はからランダムに選択されます)。1 つの未知数 ( の離散対数) に対して 1 つの方程式が得られます。得られた方程式に未知数が含まれない可能性は十分にあります。ただし、次に説明するように、これは非常に低い確率で発生します。ハッシュ衝突のアルゴリズムによって次の式が得られたと仮定します。 ${\displaystyle P_{1}=P}$${\displaystyle P_{2}=Q}$${\displaystyle P_{i}=O}$${\displaystyle i}$${\displaystyle r=2}$${\displaystyle P_{1}=r_{1}P}$${\displaystyle P_{i}=r_{i}Q}$${\displaystyle r_{i}}$${\displaystyle \mathbb {F} _{p}}$${\displaystyle Q}$

${\displaystyle ar_{1}P+\sum _{2\leq i\leq r}(b_{i}r_{i}Q)=0.}$

すると、 である限り、Q の離散対数を解くことができます。しかし、はハッシュ衝突の神託には未知なので、このプロセスが発生する順序を入れ替えることができます。言い換えると、 、に対して がすべてゼロではない場合、選択した が を満たす確率はどれくらいでしょうか。後者の確率は であることは明らかです。したがって、 の離散対数を高い確率で解くことができます。 ${\displaystyle \sum _{2\leq i\leq r}b_{i}r_{i}\not \equiv 0{\bmod {p}}}$${\displaystyle r_{i}}$${\displaystyle b_{i}}$${\displaystyle 2\leq i\leq r}$${\displaystyle r_{i}}$${\displaystyle \sum _{2\leq i\leq r}(b_{i}r_{i})=0}$${\displaystyle 1 \over p}$${\displaystyle Q}$

この方式ではハッシュ衝突を起こすのが難しいことが分かりました。敵対者がこのシステムを破るもう一つの方法は、署名を偽造することです。この署名方式は、本質的には Boneh-Lynn-Shacham 署名方式の集約署名バージョンです。^{[4]ここでは、署名の偽造は少なくとも}楕円曲線の Diffie-Hellman問題を解くのと同じくらい難しいことが示されています。楕円曲線上でこの問題を解決する唯一の既知の方法は、離散対数を計算することです。したがって、署名の偽造は少なくとも楕円曲線上の計算的 co-Diffie-Hellman 問題を解くのと同じくらい難しく、おそらく離散対数を計算するのと同じくらい難しいでしょう。

• ネットワークコーディング
• 準同型暗号
• 楕円曲線暗号
• ワイルペアリング
• 楕円曲線ディフィー・ヘルマン
• 楕円曲線デジタル署名アルゴリズム
• デジタル署名アルゴリズム

1. ライブネットワークコーディングP2Pシステムの包括的なビュー
2. ネットワークコーディングのための署名（プレゼンテーション）CISS 2006、プリンストン
3. バッファロー大学コーディング理論講義ノート – アトリ・ルドラ博士