  In this paper, we investigate multi-message authentication to combat
adversaries with infinite computational capacity. An authentication framework
over a wiretap channel $(W_1,W_2)$ is proposed to achieve information-theoretic
security with the same key. The proposed framework bridges the two research
areas in physical (PHY) layer security: secure transmission and message
authentication. Specifically, the sender Alice first transmits message $M$ to
the receiver Bob over $(W_1,W_2)$ with an error correction code; then Alice
employs a hash function (i.e., $\varepsilon$-AWU$_2$ hash functions) to
generate a message tag $S$ of message $M$ using key $K$, and encodes $S$ to a
codeword $X^n$ by leveraging an existing strongly secure channel coding with
exponentially small (in code length $n$) average probability of error; finally,
Alice sends $X^n$ over $(W_1,W_2)$ to Bob who authenticates the received
messages. We develop a theorem regarding the requirements/conditions for the
authentication framework to be information-theoretic secure for authenticating
a polynomial number of messages in terms of $n$. Based on this theorem, we
propose an authentication protocol that can guarantee the security
requirements, and prove its authentication rate can approach infinity when $n$
goes to infinity. Furthermore, we design and implement an efficient and
feasible authentication protocol over binary symmetric wiretap channel (BSWC)
by using \emph{Linear Feedback Shifting Register} based (LFSR-based) hash
functions and strong secure polar code. Through extensive experiments, it is
demonstrated that the proposed protocol can achieve low time cost, high
authentication rate, and low authentication error rate.
