Homomorphic signatures for network coding: Difference between revisions

Revision as of 06:06, 21 November 2021

Revision as of 18:33, 10 January 2022

Line 10:

: <math>y(e) = \sum_{f:\mathrm{out}(f)=v}(m_e(f)y(f))</math>

where <math>m_e(f) \in \mathbb{F}_p</math>. We consider the source as having <math>k</math> input edges carrying the <math>k</math> vectors <math>w_i</math>. By [[Mathematical induction|induction]], one has that the vector <math>y(e)</math> on any edge is a linear combination <math>y(e) = \sum_{1 \le i \le k}(g_i(e)v_i)</math> and is a vector in <math>V</math> . The k-dimensional vector <math>g(e) = (g_1(e), \ldots , g_k(e))</math> is simply the first ''k'' coordinates of the vector <math>y(e)</math>. We call the [[Matrix (mathematics)|matrix]] whose rows are the vectors <math>g(e_1), \ldots , g(e_k)</math>, where <math>e_i</math> are the incoming edges for a vertex <math>t \in T</math>, the global encoding matrix for <math>t</math> and denote it as <math>G_t</math>. In practice the encoding vectors are chosen at random so the matrix <math>G_t</math> is invertible with high probability. Thus, any receiver, on receiving <math>y_1, \ldots , y_k</math> can find <math>w_1,\ldots ,w_k</math> by solving

: <math>\begin{bmatrix} y'\\ y_2' \\ \vdots \\ y_k' \end{bmatrix} = G_t \begin{bmatrix} w_1\\ w_2 \\ \vdots \\ w_k \end{bmatrix}</math>

where the <math>y_i'</math> are the vectors formed by removing the first <math>k</math> coordinates of the vector <math>y_i</math>.