A Generic Construction of Homomorphic MAC for Multi-
File Transmission in Network Coding
Jinyong Chang
1,2
and Rui Xue
1
1
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences,
Beijing 100093, China
2
Department of Mathematics, Changzhi University, Changzhi 046011, China
Email: {changjinyong, xuerui}@iie.ac.cn
Abstract—Homomorphic message authentication codes (MAC)
have been proposed to thwart pollution attacks in network
coding. The existing schemes mainly are based on the vector
inner product or trace function over finite fields. Recently,
Wang and Hu presented a generic construction of homomorphic
MAC scheme based on linear mapping over finite fields which
is an excellent abstract of the vector inner product and the trace
function. However, their construction can only be used for
single-file transmission. In this paper, we convert their scheme
into a new one that supports multi-file transmission. Moreover,
our scheme needs shorter key when one wants to achieve the
same security as that of Wang et al.
Index Terms—Homomorphic MAC, network coding, pollution
attacks, linear mapping
I. INTRODUCTION
Network coding provides a new data transmission
paradigm, in which intermediate nodes are allowed to
mix/code packets rather than just forward them. This
technique is proven capable of achieving maximized
throughtput [1], enhanced robustness, and lower energy
consumption [2] for communication networks. However,
the information-mixing nature of network coding also
renders it more susceptible to pollution attacks than the
traditional store-and-forward paradigm.
The existing techniques for combating data pollution in
network coding include some information-theoretic
approaches [3] and cryptographic approaches [4], which
can also be divided into public key setting, such as
homomorphic hash, homomorphic signature [5], and
symmetric key setting, such as homomorphic MAC [6]
(See [7] for further discussion). However, researchers
prefer the schemes based on symmetric key, which are
considered to be computationally efficient and hence of
more practical meaning for network coding.
In recent years, several works was proposed by
Agrawal and Boneh [6]. In particular, they essentially use
the inner product between two vectors over the (n+m)-
Manuscript received October 26, 2014; revised January 24, 2015.
This work was supported by National Natural Science Foundation of
China under Grant No. 61472414, 61170280, 61402471, the Strategic
Priority Research Program of Chinese Academy of Sciences under
Grant No. XDA06010701, the Foundation of Institute of Information
Engineering for Cryptography.
Corresponding author email: changjinyong@iie.ac.cn.
dimension linear space
F
nm
q
, in which one is the basis
vector to be authenticated and another one is the key, to
construct their homomorphic MAC and the resulting tag
is a single element of
F
q
, which means that any adversary
may break the MAC by randomly guessing a value in
F
q
as the tag. However, just as Agrawal et al. said in [6],
usually, the predetermined parameter
q
is typically set as
8
2 256.
Hence, this security level may not be sufficient.
Two “trivial” methods are suggested to enhance the
security. One is simply to increase
q
, i.e. the size of the
underlying field, which may cause additional
computational and communication overheads, and
another one is computing multiple MACs per vector,
which may need longer keys [6].
To solve the above problem, Cheng and Jiang [8]
employed the trace function over finite fields to construct
a homomorphic MAC achieving a reliable security
1/
l
q
,
where
l
is a proper parameter chosen according to the
different requirement of security, neither increasing the
size of the field nor employing longer keys.
In fact, from the algebra point of view, both the inner-
product operation and the trace function can be viewed as
special cases of the linear mapping over finite fields.
More recently, Wang and Hu [9] proposed a
generic/universal construction of homomorphic MAC
based on the linear mapping. Therefore, all existing
schemes based on inner-product or trace function are
essentially special cases of their scheme. Moreover, their
construction not only achieves the functionality of
authentication but also has greater flexibility and
effectiveness for multi-tag cases. In particular, based on
their linear mapping-technique, Wang and Hu analyzed
the MAC scheme used in the transmission protocol
RIPPLE [10, 11] and shortened the length of its keys.
Revisiting the excellent construction in [9], we find
that their scheme only considered the single-file
distribution (i.e. the packets (or vectors) transmitted
among the nodes must belong to one file (or linear
space)). However, in this situation, the corresponding
homomorphic MAC scheme is susceptible to repetitive
attacks [12].
In this paper, inspired by the technique proposed in [6],
we convert the construction of Wang and Hu into a new
one which supports multi-file transmission and hence
of Communications Vol. 10, No. 1, January 2015
43
©2015 Engineering and Technology Publishing
doi:10.12720/jcm.10.1.43-47