In the past, two main approaches for the purpose
of authentication, including information-theoretic authentication
codes and complexity-theoretic message authentication
codes (MACs), were almost independently developed. In this
paper, we consider to construct new MACs, which are both
computationally secure and information-theoretically secure.
Essentially, we propose a new cryptographic primitive, namely,
artificial-noise-aided MACs (ANA-MACs), where artificial noise
is used to interfere with the complexity-theoretic MACs and
quantization is further employed to facilitate packet-based transmission.
With a channel coding formulation of key recovery in
the MACs, the generation of standard authentication tags can
be seen as an encoding process for the ensemble of codes, where
the shared key between Alice and Bob is considered as the input
and the message is used to specify a code from the ensemble
of codes. Then, we show that artificial noise in ANA-MACs can
be well employed to resist the key recovery attack even if the
opponent has an unlimited computing power. Finally, a pragmatic
approach for the analysis of ANA-MACs is provided, and we
show how to balance the three performance metrics, including
the completeness error, the false acceptance probability, and the
conditional equivocation about the key. The analysis can be well
applied to a class of ANA-MACs, where MACs with Rijndael
cipher are employed.