Homomorphic signatures for network coding

Last updated July 24, 2023

Network coding has been shown to optimally use bandwidth in a network, maximizing information flow but the scheme is very inherently vulnerable to pollution attacks by malicious nodes in the network. A node injecting garbage can quickly affect many receivers. The pollution of network packets spreads quickly since the output of (even an) honest node is corrupted if at least one of the incoming packets is corrupted.

An attacker can easily corrupt a packet even if it is encrypted by either forging the signature or by producing a collision under the hash function. This will give an attacker access to the packets and the ability to corrupt them. Denis Charles, Kamal Jain and Kristin Lauter designed a new homomorphic encryption signature scheme for use with network coding to prevent pollution attacks.^[1]

The homomorphic property of the signatures allows nodes to sign any linear combination of the incoming packets without contacting the signing authority. In this scheme it is computationally infeasible for a node to sign a linear combination of the packets without disclosing what linear combination was used in the generation of the packet. Furthermore, we can prove that the signature scheme is secure under well known cryptographic assumptions of the hardness of the discrete logarithm problem and the computational Elliptic curve Diffie–Hellman.

Network coding

Let $G=(V,E)$ be a directed graph where $V$ is a set, whose elements are called vertices or nodes, and $E$ is a set of ordered pairs of vertices, called arcs, directed edges, or arrows. A source $s\in V$ wants to transmit a file $D$ to a set $T\subseteq V$ of the vertices. One chooses a vector space $W/\mathbb {F} _{p}$ (say of dimension $d$ ), where $p$ is a prime, and views the data to be transmitted as a bunch of vectors $w_{1},\ldots ,w_{k}\in W$ . The source then creates the augmented vectors $v_{1},\ldots ,v_{k}$ by setting $v_{i}=(0,\ldots ,0,1,\ldots ,0,w_{i_{1}},\ldots ,w{i_{d}})$ where $w_{i_{j}}$ is the $j$ -th coordinate of the vector $w_{i}$ . There are $(i-1)$ zeros before the first '1' appears in $v_{i}$ . One can assume without loss of generality that the vectors $v_{i}$ are linearly independent. We denote the linear subspace (of $\mathbb {F} _{p}^{k+d}$ ) spanned by these vectors by $V$ . Each outgoing edge $e\in E$ computes a linear combination, $y(e)$ , of the vectors entering the vertex $v=in(e)$ where the edge originates, that is to say

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

where $m_{e}(f)\in \mathbb {F} _{p}$ . We consider the source as having $k$ input edges carrying the $k$ vectors $w_{i}$ . By induction, one has that the vector $y(e)$ on any edge is a linear combination $y(e)=\sum _{1\leq i\leq k}(g_{i}(e)v_{i})$ and is a vector in $V$ . The k-dimensional vector $g(e)=(g_{1}(e),\ldots ,g_{k}(e))$ is simply the first k coordinates of the vector $y(e)$ . We call the matrix whose rows are the vectors $g(e_{1}),\ldots ,g(e_{k})$ , where $e_{i}$ are the incoming edges for a vertex $t\in T$ , the global encoding matrix for $t$ and denote it as $G_{t}$ . In practice the encoding vectors are chosen at random so the matrix $G_{t}$ is invertible with high probability. Thus, any receiver, on receiving $y_{1},\ldots ,y_{k}$ can find $w_{1},\ldots ,w_{k}$ by solving

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

where the $y_{i}'$ are the vectors formed by removing the first $k$ coordinates of the vector $y_{i}$ .

Decoding at the receiver

Each receiver, $t\in T$ , gets $k$ vectors $y_{1},\ldots ,y_{k}$ which are random linear combinations of the $v_{i}$ ’s. In fact, if

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

then

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

Thus we can invert the linear transformation to find the $v_{i}$ ’s with high probability.

History

Krohn, Freedman and Mazieres proposed a theory^[2] in 2004 that if we have a hash function $H:V\longrightarrow G$ such that:

$H$ is collision resistant – it is hard to find $x$ and $y$ such that $H(x)=H(y)$ ;
$H$ is a homomorphism – $H(x+y)=H(x)+H(y)$ .

Then server can securely distribute $H(v_{i})$ to each receiver, and to check if

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

we can check whether

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

The problem with this method is that the server needs to transfer secure information to each of the receivers. The hash functions $H$ needs to be transmitted to all the nodes in the network through a separate secure channel. $H$ is expensive to compute and secure transmission of $H$ is not economical either.

Advantages of homomorphic signatures

Establishes authentication in addition to detecting pollution.
No need for distributing secure hash digests.
Smaller bit lengths in general will suffice. Signatures of length 180 bits have as much security as 1024 bit RSA signatures.
Public information does not change for subsequent file transmission.

Signature scheme

The homomorphic property of the signatures allows nodes to sign any linear combination of the incoming packets without contacting the signing authority.

Elliptic curves cryptography over a finite field

Elliptic curve cryptography over a finite field is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields.

Let $\mathbb {F} _{q}$ be a finite field such that $q$ is not a power of 2 or 3. Then an elliptic curve $E$ over $\mathbb {F} _{q}$ is a curve given by an equation of the form

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

where $a,b\in \mathbb {F} _{q}$ such that $4a^{3}+27b^{2}\not =0$

Let $K\supseteq \mathbb {F} _{q}$ , then,

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

forms an abelian group with O as identity. The group operations can be performed efficiently.

Weil pairing

Weil pairing is a construction of roots of unity by means of functions on an elliptic curve $E$ , in such a way as to constitute a pairing (bilinear form, though with multiplicative notation) on the torsion subgroup of $E$ . Let $E/\mathbb {F} _{q}$ be an elliptic curve and let $\mathbb {\bar {F}} _{q}$ be an algebraic closure of $\mathbb {F} _{q}$ . If $m$ is an integer, relatively prime to the characteristic of the field $\mathbb {F} _{q}$ , then the group of $m$ -torsion points, $E[m]={P\in E(\mathbb {\bar {F}} _{q}):mP=O}$ .

If $E/\mathbb {F} _{q}$ is an elliptic curve and $\gcd(m,q)=1$ then

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

There is a map $e_{m}:E[m]*E[m]\rightarrow \mu _{m}(\mathbb {F} _{q})$ such that:

(Bilinear) $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)$ .
(Non-degenerate) $e_{m}(P,Q)=1$ for all P implies that $Q=O$ .
(Alternating) $e_{m}(P,P)=1$ .

Also, $e_{m}$ can be computed efficiently.^[3]

Homomorphic signatures

Let $p$ be a prime and $q$ a prime power. Let $V/\mathbb {F} _{p}$ be a vector space of dimension $D$ and $E/\mathbb {F} _{q}$ be an elliptic curve such that $P_{1},\ldots ,P_{D}\in E[p]$ . Define $h:V\longrightarrow E[p]$ as follows: $h(u_{1},\ldots ,u_{D})=\sum _{1\leq i\leq D}(u_{i}P_{i})$ . The function $h$ is an arbitrary homomorphism from $V$ to $E[p]$ .

The server chooses $s_{1},\ldots ,s_{D}$ secretly in $\mathbb {F} _{p}$ and publishes a point $Q$ of p-torsion such that $e_{p}(P_{i},Q)\not =1$ and also publishes $(P_{i},s_{i}Q)$ for $1\leq i\leq D$ . The signature of the vector $v=u_{1},\ldots ,u_{D}$ is $\sigma (v)=\sum _{1\leq i\leq D}(u_{i}s_{i}P_{i})$ Note: This signature is homomorphic since the computation of h is a homomorphism.

Signature verification

Given $v=u_{1},\ldots ,u_{D}$ and its signature $\sigma$ , verify that

{\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}}

The verification crucially uses the bilinearity of the Weil-pairing.

System setup

The server computes $\sigma (v_{i})$ for each $1\leq i\leq k$ . Transmits $v_{i},\sigma (v_{i})$ . At each edge $e$ while computing $y(e)=\sum _{f\in E:\mathrm {out} (f)=\mathrm {in} (e)}(m_{e}(f)y(f))$ also compute $\sigma (y(e))=\sum _{f\in E:\mathrm {out} (f)=\mathrm {in} (e)}(m_{e}(f)\sigma (y(f)))$ on the elliptic curve $E$ .

The signature is a point on the elliptic curve with coordinates in $\mathbb {F} _{q}$ . Thus the size of the signature is $2\log q$ bits (which is some constant times $log(p)$ bits, depending on the relative size of $p$ and $q$ ), and this is the transmission overhead. The computation of the signature $h(e)$ at each vertex requires $O(d_{in}\log p\log ^{1+\epsilon }q)$ bit operations, where $d_{in}$ is the in-degree of the vertex $in(e)$ . The verification of a signature requires $O((d+k)\log ^{2+\epsilon }q)$ bit operations.

Proof of security

Attacker can produce a collision under the hash function.

If given $(P_{1},\ldots ,P_{r})$ points in $E[p]$ find $a=(a_{1},\ldots ,a_{r})\in \mathbb {F} _{p}^{r}$ and $b=(b_{1},\ldots ,b_{r})\in \mathbb {F} _{p}^{r}$

such that $a\not =b$ and

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

Proposition: There is a polynomial time reduction from discrete log on the cyclic group of order $p$ on elliptic curves to Hash-Collision.

If $r=2$ , then we get $xP+yQ=uP+vQ$ . Thus $(x-u)P+(y-v)Q=0$ . We claim that $x\not =u$ and $y\not =v$ . Suppose that $x=u$ , then we would have $(y-v)Q=0$ , but $Q$ is a point of order $p$ (a prime) thus $y-u\equiv 0{\bmod {p}}$ . In other words $y=v$ in $\mathbb {F} _{p}$ . This contradicts the assumption that $(x,y)$ and $(u,v)$ are distinct pairs in $\mathbb {F} _{2}$ . Thus we have that $Q=-(x-u)(y-v)^{-1}P$ , where the inverse is taken as modulo $p$ .

If we have r > 2 then we can do one of two things. Either we can take $P_{1}=P$ and $P_{2}=Q$ as before and set $P_{i}=O$ for $i$ > 2 (in this case the proof reduces to the case when $r=2$ ), or we can take $P_{1}=r_{1}P$ and $P_{i}=r_{i}Q$ where $r_{i}$ are chosen at random from $\mathbb {F} _{p}$ . We get one equation in one unknown (the discrete log of $Q$ ). It is quite possible that the equation we get does not involve the unknown. However, this happens with very small probability as we argue next. Suppose the algorithm for Hash-Collision gave us that

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

Then as long as $\sum _{2\leq i\leq r}b_{i}r_{i}\not \equiv 0{\bmod {p}}$ , we can solve for the discrete log of Q. But the $r_{i}$ ’s are unknown to the oracle for Hash-Collision and so we can interchange the order in which this process occurs. In other words, given $b_{i}$ , for $2\leq i\leq r$ , not all zero, what is the probability that the $r_{i}$ ’s we chose satisfies $\sum _{2\leq i\leq r}(b_{i}r_{i})=0$ ? It is clear that the latter probability is $1 \over p$ . Thus with high probability we can solve for the discrete log of $Q$ .

We have shown that producing hash collisions in this scheme is difficult. The other method by which an adversary can foil our system is by forging a signature. This scheme for the signature is essentially the Aggregate Signature version of the Boneh-Lynn-Shacham signature scheme.^[4] Here it is shown that forging a signature is at least as hard as solving the elliptic curve Diffie–Hellman problem. The only known way to solve this problem on elliptic curves is via computing discrete-logs. Thus forging a signature is at least as hard as solving the computational co-Diffie–Hellman on elliptic curves and probably as hard as computing discrete-logs.

Related Research Articles

In mathematics, the tensor product $of two vector spaces V and W is a vector space to which is associated a bilinear map that maps a pair to an element of denoted$

In mathematics, the $L p$ spaces are function spaces defined using a natural generalization of the $p$ -norm for finite-dimensional vector spaces. They are sometimes called Lebesgue spaces, named after Henri Lebesgue, although according to the Bourbaki group they were first introduced by Frigyes Riesz.

In mathematical analysis, Hölder's inequality, named after Otto Hölder, is a fundamental inequality between integrals and an indispensable tool for the study of $L p$ spaces.

In mathematics, a linear form is a linear map from a vector space to its field of scalars.

In vector calculus, Green's theorem relates a line integral around a simple closed curve $C$ to a double integral over the plane region $D$ bounded by $C$ . It is the two-dimensional special case of Stokes' theorem.

Vapnik–Chervonenkis theory was developed during 1960–1990 by Vladimir Vapnik and Alexey Chervonenkis. The theory is a form of computational learning theory, which attempts to explain the learning process from a statistical point of view.

In differential geometry, the Atiyah–Singer index theorem, proved by Michael Atiyah and Isadore Singer (1963), states that for an elliptic differential operator on a compact manifold, the analytical index is equal to the topological index. It includes many other theorems, such as the Chern–Gauss–Bonnet theorem and Riemann–Roch theorem, as special cases, and has applications to theoretical physics.

In functional analysis and related areas of mathematics, locally convex topological vector spaces (LCTVS) or locally convex spaces are examples of topological vector spaces (TVS) that generalize normed spaces. They can be defined as topological vector spaces whose topology is generated by translations of balanced, absorbent, convex sets. Alternatively they can be defined as a vector space with a family of seminorms, and a topology can be defined in terms of that family. Although in general such spaces are not necessarily normable, the existence of a convex local base for the zero vector is strong enough for the Hahn–Banach theorem to hold, yielding a sufficiently rich theory of continuous linear functionals.

Multi-index notation is a mathematical notation that simplifies formulas used in multivariable calculus, partial differential equations and the theory of distributions, by generalising the concept of an integer index to an ordered tuple of indices.

In abstract algebra and multilinear algebra, a multilinear form on a vector space $over a field is a map$

In mathematics, a norm is a function from a real or complex vector space to the non-negative real numbers that behaves in certain ways like the distance from the origin: it commutes with scaling, obeys a form of the triangle inequality, and is zero only at the origin. In particular, the Euclidean distance in a Euclidean space is defined by a norm on the associated Euclidean vector space, called the Euclidean norm, the 2-norm, or, sometimes, the magnitude of the vector. This norm can be defined as the square root of the inner product of a vector with itself.

Reed–Muller codes are error-correcting codes that are used in wireless communications applications, particularly in deep-space communication. Moreover, the proposed 5G standard relies on the closely related polar codes for error correction in the control channel. Due to their favorable theoretical and mathematical properties, Reed–Muller codes have also been extensively studied in theoretical computer science.

Hidden Fields Equations (HFE), also known as HFE trapdoor function, is a public key cryptosystem which was introduced at Eurocrypt in 1996 and proposed by (in French)Jacques Patarin following the idea of the Matsumoto and Imai system. It is based on polynomials over finite fields $of different size to disguise the relationship between the private key and public key. HFE is in fact a family which consists of basic HFE and combinatorial versions of HFE. The HFE family of cryptosystems is based on the hardness of the problem of finding solutions to a system of multivariate quadratic equations (the so-called MQ problem) since it uses private affine transformations to hide the extension field and the private polynomials. Hidden Field Equations also have been used to construct digital signature schemes, e.g. Quartz and Sflash.$

In mathematics, a Witt vector is an infinite sequence of elements of a commutative ring. Ernst Witt showed how to put a ring structure on the set of Witt vectors, in such a way that the ring of Witt vectors $over the finite field of order is isomorphic to, the ring of -adic integers . They have a highly non-intuitive structure upon first glance because their additive and multiplicative structure depends on an infinite set of recursive formulas which do not behave like addition and multiplication formulas for standard p-adic integers.$

In mathematics, the Grothendieck inequality states that there is a universal constant $with the following property. If M ij is an n \times n matrix with$

An important aspect in the study of elliptic curves is devising effective ways of counting points on the curve. There have been several approaches to do so, and the algorithms devised have proved to be useful tools in the study of various fields such as number theory, and more recently in cryptography and Digital Signature Authentication. While in number theory they have important consequences in the solving of Diophantine equations, with respect to cryptography, they enable us to make effective use of the difficulty of the discrete logarithm problem (DLP) for the group $, of elliptic curves over a finite field, where q = p k and p is a prime. The DLP, as it has come to be known, is a widely used approach to public key cryptography, and the difficulty in solving this problem determines the level of security of the cryptosystem. This article covers algorithms to count points on elliptic curves over fields of large characteristic, in particular p > 3. For curves over fields of small characteristic more efficient algorithms based on p -adic methods exist.$

A sum-of-squares optimization program is an optimization problem with a linear cost function and a particular type of constraint on the decision variables. These constraints are of the form that when the decision variables are used as coefficients in certain polynomials, those polynomials should have the polynomial SOS property. When fixing the maximum degree of the polynomials involved, sum-of-squares optimization is also known as the Lasserre hierarchy of relaxations in semidefinite programming.

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

In mathematics, calculus on Euclidean space is a generalization of calculus of functions in one or several variables to calculus of functions on Euclidean space $as well as a finite-dimensional real vector space. This calculus is also known as advanced calculus, especially in the United States. It is similar to multivariable calculus but is somehow more sophisticated in that it uses linear algebra more extensively and covers some concepts from differential geometry such as differential forms and Stokes' formula in terms of differential forms. This extensive use of linear algebra also allows a natural generalization of multivariable calculus to calculus on Banach spaces or topological vector spaces.$

The finite promise games are a collection of mathematical games developed by American mathematician Harvey Friedman in 2009 which are used to develop a family of fast-growing functions $, and . The greedy clique sequence is a graph theory concept, also developed by Friedman in 2010, which are used to develop fast-growing functions, and .$

References

↑ "Signatures for Network Coding". 2006. CiteSeerX 10.1.1.60.4738 . Archived from the original on 2021-11-20.{{cite journal}}: Cite journal requires |journal= (help)
↑ Krohn, Maxwell N.; Freedman, Michael J; Mazières, David (2004). "On-the-fly verification of rateless erasure codes for efficient content distribution" (PDF). IEEE Symposium on Security and Privacy, 2004. Proceedings. 2004. Berkeley, California, USA. pp. 226–240. doi:10.1109/SECPRI.2004.1301326. ISBN 0-7695-2136-3. ISSN 1081-6011. S2CID 6976686 . Retrieved 17 November 2022.
↑ Eisentraeger, Kirsten; Lauter, Kristin; Montgomery, Peter L. (2004). "Improved Weil and Tate pairings for elliptic and hyperelliptic curves": 169–183. arXiv: math/0311391 . Bibcode:2003math.....11391E. CiteSeerX 10.1.1.88.8848 .{{cite journal}}: Cite journal requires |journal= (help)
↑ Boneh, Dan; Lynn, Ben; Shacham, Hovav (2001). "Short Signatures from the Weil Pairing" (PDF). Advances in Cryptology — ASIACRYPT 2001. Lecture Notes in Computer Science. Vol. 2248. pp. 514–532. doi:10.1007/3-540-45682-1_30. ISBN 978-3-540-45682-7 . Retrieved 17 November 2022.

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] "Signatures for Network Coding". 2006. CiteSeerX 10.1.1.60.4738 . Archived from the original on 2021-11-20.{{cite journal}}: Cite journal requires |journal= (help)

[2] Krohn, Maxwell N.; Freedman, Michael J; Mazières, David (2004). "On-the-fly verification of rateless erasure codes for efficient content distribution" (PDF). IEEE Symposium on Security and Privacy, 2004. Proceedings. 2004. Berkeley, California, USA. pp. 226–240. doi:10.1109/SECPRI.2004.1301326. ISBN 0-7695-2136-3. ISSN 1081-6011. S2CID 6976686 . Retrieved 17 November 2022.

[3] Eisentraeger, Kirsten; Lauter, Kristin; Montgomery, Peter L. (2004). "Improved Weil and Tate pairings for elliptic and hyperelliptic curves": 169–183. arXiv: math/0311391 . Bibcode:2003math.....11391E. CiteSeerX 10.1.1.88.8848 .{{cite journal}}: Cite journal requires |journal= (help)

[4] Boneh, Dan; Lynn, Ben; Shacham, Hovav (2001). "Short Signatures from the Weil Pairing" (PDF). Advances in Cryptology — ASIACRYPT 2001. Lecture Notes in Computer Science. Vol. 2248. pp. 514–532. doi:10.1007/3-540-45682-1_30. ISBN 978-3-540-45682-7 . Retrieved 17 November 2022.

[1]

[2]

[3]

[4]