International Journal of Computer, Consumer and Control (IJ3C), Vol. 4, No.2 (2015)
A Data Integrity Scheme Based on Homomorphic Hash Function
for Multi-source Network Coding
Niu Shu-fen, Wang Cai-fen and Cao Su-zhen
Abstract
The integrity scheme for a single source based
on homomorphic signature cannot handle a combined
message's signature from multiple sources with
different private keys. The main reason is that the
signature schemes will not hold the homomorphism if
the unique secret key is replaced by distinct private
keys. This also means the forwarding nodes could
not generate a valid signature for a combined
message without knowing the source keys.
In this paper, taking advantage of vector Merge
algorithm and homomorphic hash function, we
propose an efficient data integrity scheme for
multi-source securing network coding against
pollution attacks. Firstly, each source node
computes raw massage's hash values and uses a
secure mechanism to sign the hash values, and then
appends the hash values and its signatures to each
message sending to forwarding nodes and sink
nodes. The forwarder can verify the integrity of
network coded data from different source nodes
without knowing the sources private keys and
generate the hash for the combined messages. The
security of the scheme relies on the Discrete
Logarithm problem and Co-Diffie-Hellman problem.
Keywords:
Multi-source network coding, Data
integrity, Aggregate Signatures, Homomorphic Hash
Function
1. Introduction
Network coding was first introduced in [1] as
an alternative to the traditional routing networks, and
it has been shown to improve the capacity and
achieve the optimal throughput in network [2],[3].
Furthermore, network coding can reduce the amount
of transmissions in wireless networks[4],[5].
However, network coding may face potential
pollution attack threats; if some routers in the
network are malicious and forward invalid
combinations of received packets, then these invalid
packets get mixed with valid packets downstream and
quickly pollute the whole network. Prior works for
intermediate nodes verifying the validity of incoming
vectors are based on one of two primitives:
(collision-resistant) homomorphic hash functions
[8][10] or homomorphic signature
schemes[11][12][13]. In both cases, the
homomorphic properties are used such that the
signature (or hashing) operation on a linear
combination of vectors results in a corresponding
homomorphic combination of signatures (or hash
values).
For multi-source networks using network
coding, signature scheme is considerably harder than
the single source problem. In this systems, packets
originating from multiple different sources are
encoded together, and the homomorphic signature
schemes will not hold the homomorphism if the
unique secret key is replaced by distinct private keys,
which means that the forwarding nodes could not
generate a valid homomorphic signature for a
combined message without knowing the source keys.
The remainder of this paper is organized as
follows. In Section 2, we briefly discuss related work,
and we discuss the novelty and contributions of this
paper in Section 3. Then we introduce complexity
assumptions and cryptographic primitives used in our
approach in Section 4. The detailed design and
security analysis of our scheme are presented in
Section 5 and 6. Finally, we evaluate the performance
of the proposed scheme in Section 7,and conclude
this paper in Section 8.
2. Related Work
Krohn [10] first presented a homomorphic
hashing scheme, which allows a verifier to verify the
integrity of rateless erase codes. This approach was
extended by Gkantsidis and Rodriguez (denotes as
GR’s scheme)[15] for securing the file distribution
systems built on top of network coding technique.
However, one drawback of GR’s scheme is that it
needs an extra secure channel to broadcast the source
hashes to all the forwarders.
Charles (denotes as CJL’s scheme)[12] defined
another similar model based on homomorphic
signature scheme over elliptic curves. However, the
pair-based operations used by CJL’s scheme are
much slower than the modular exponentiation
operations adopted in GR’s schemes.
E-mail:
{sfniu76,wangcf, suzcao}nwnu.edu.cn
)
College of Computer Science and Engineering,Northwest Normal
University Northwest Normal University,
Lanzhou,
P.R.C