On message authentication with a correlated setup

In this note, we study the message authentication problem, where sender Alice, receiver Bob and attacker Oscar are respectively initialized with Xn,Yn,ZnXn,Yn,Zn that are jointly distributed according to PXYZn. The channel between Alice and Bob is noiseless but visible to Oscar. We obtain two results.•We show that a necessary condition for Alice to conduct a secure authentication is I(X;Y|Z)>0I(X;Y|Z)>0. Our main proof technique is to manipulate the Markov chains. If our result is incorrect, then X→Z→YX→Z→Y forms a Markov chain. Thus, PY|Z=PY|ZXPY|Z=PY|ZX. Hence, given Z, X is useless to the verifier. So in view of Bob, Oscar can generate a message as good as Alice.•We prove that the optimal Oscar's success probability in a t  -order secure system is lower bounded by 2−σnH(Y|Z)t+1−1. Our main technique in the proof is to manipulate Markov chains and information theoretical inequalities. For i=0,⋯,ti=0,⋯,t, our strategy is to analyze the attacker who sees i   messages and tries to guess the most possible message as his forgery. The neat lower bound is obtained by averaging these t+1t+1 strategies.

We study the message authentication problem, where sender Alice, receiver Bob and attacker Oscar are respectively initialized with Xn,Yn,ZnXn,Yn,Zn that are jointly distributed according to PXYZn. We show that a necessary condition to do the authentication is I(X;Y|Z)>0I(X;Y|Z)>0. We also prove a lower bound on the optimal Oscar's success probability. Under our result, it is impossible to do secure authentications for Ω(n)Ω(n) times.