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

ネットワークコーディングは、ネットワーク内の帯域幅を最適に利用し、情報フローを最大化することが実証されていますが、ネットワーク内の悪意のあるノードによる汚染攻撃に対して非常に脆弱です。ゴミデータを注入するノードは、多くの受信者に急速に影響を及ぼす可能性があります。受信パケットのうち少なくとも1つが破損すると、（たとえ）正直なノードの出力も破損するため、ネットワークパケットの汚染は急速に広がります。

攻撃者は、署名を偽造するかハッシュ関数の下で衝突を発生させることによって、暗号化されているパケットであっても簡単に改ざんできます。これにより、攻撃者はパケットにアクセスし、改ざんできるようになります。Denis Charles、Kamal Jain、Kristin Lauterは、汚染攻撃を防ぐためにネットワークコーディングで使用する新しい準同型暗号化署名方式を設計しました。^{[ 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)}$最初の「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))}$

どこ${\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}$k次元ベクトル${\displaystyle g(e)=(g_{1}(e),\ldots ,g_{k}(e))}$これは単にベクトルの最初のk 個の座標です${\displaystyle y(e)}$行がベクトルである行列を、${\displaystyle g(e_{1}),\ldots ,g(e_{k})}$、 どこ${\displaystyle e_{i}}$頂点への入力エッジは$t ∈ 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}}$。

各受信機、$t ∈ T$、取得する${\displaystyle k}$ベクトル$\displaystyle y_{1},\ldots ,y_{k}}$これらは、${\displaystyle v_{i}}$'s。実際、もし

${\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}}$高い確率で。

クローン、フリードマン、マジェールは²⁰⁰⁴年に、ハッシュ関数が ^あれば${\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. 公開情報は、その後のファイル送信によって変更されることはありません。

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

サーバーは計算します${\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 つの方法のいずれかを実行できます。${\displaystyle P_{1}=P}$そして${\displaystyle P_{2}=Q}$以前と同じように設定して${\displaystyle P_{i}=O}$のために${\displaystyle i}$> 2 (この場合、証明は次のケースに帰着します)${\displaystyle r=2}$）または、${\displaystyle P_{1}=r_{1}P}$そして${\displaystyle P_{i}=r_{i}Q}$どこ${\displaystyle r_{i}}$ランダムに選ばれる${\displaystyle \mathbb {F} _{p}}$1 つの未知数 (離散対数) を含む 1 つの方程式が得られます。${\displaystyle Q}$) 得られた方程式に未知数が含まれていない可能性は十分にあります。しかし、次に述べるように、これは非常に低い確率でしか起こりません。ハッシュ衝突アルゴリズムが次のような結果を出したとしましょう。

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

そして、${\displaystyle \sum _{2\leq i\leq r}b_{i}r_{i}\not \equiv 0{\bmod {p}}}$離散的な Q の対数を解くことができます。しかし、${\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}$。

この方式ではハッシュ衝突を生成することが難しいことを示しました。攻撃者がシステムを妨害できるもう1つの方法は、署名を偽造することです。この署名方式は、基本的にBoneh-Lynn-Shacham署名方式の集約署名バージョンです。^{[ 4 ]}ここでは、署名の偽造は楕円曲線Diffie-Hellman問題を解くのと少なくとも同程度に難しいことが示されています。楕円曲線上でこの問題を解決する既知の方法は、離散対数を計算することだけです。したがって、署名の偽造は、楕円曲線上の計算的co-Diffie-Hellman問題を解くのと少なくとも同程度に難しく、おそらく離散対数を計算するのと同程度に難しいです。

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

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