消息认证是密码学和信息安全领域中一个最基础也是最重要的研究问题之一。其目的是，发送方Alice将消息$M$发送给接收方Bob，并通过交互(或者非交互)的方式使得Bob能够确认消息$M$是来自Alice的。要达到这个目的，Alice和Bob首先要共享一个密钥$K$。为了确保协议的安全性，首先要考虑敌手模型，即敌手具有什么样的计算能力，能够发起什么形式的攻击。通常采用的敌手模型是敌手可以发起中间人攻击。即敌手可以冒充Alice(Bob)发送任何消息给Bob(Alice)。除此之外，敌手还可以插入、篡改和删除Alice和Bob之间的消息。

在经典消息认证模型中，Alice和Bob之间的通信信道是无噪声的^{[1, 2]}。然而，在无噪声的认证模型中，由于每一次认证都会降低密钥的熵，故而提高了敌手攻击成功的概率。文献^[2]证明了使用相同密钥认证$l$个消息后，敌手攻击成功概率的下界是$2 - H(K)/(l + 1)$。这说明当 $l$增大时，攻击成功的概率将会很快增加到1。噪声是通信中常见的物理现象。在安全领域，噪声却带来了诸多好处。文献^[3]在窃听信道模型下利用噪声实现了合法用户间的密钥共享，同时使窃听者得不到任何关于密钥的信息。文献^[4]将这一结果推广到了广播信道模型。从此，噪声信道下的密钥分配问题得到了理论和工业界的广泛研究^{[5, 6, 7, 8, 9]}，但在噪声信道下的消息认证的相关工作却鲜有进展。如何实现信息安全下的多项式次的消息认证是一个值得关注的问题。

本文将考察在噪声信道下的消息认证。文献^[10]提到了利用噪声信道获得的相关性实现(无噪声)公共信道的消息认证。该问题可归类为信源模型^[11]的消息认证。文献^[12]首次提出了窃听信道的消息认证：Alice和Bob共享一个密钥，当Alice发送$X\$时，合法接收者Bob通过主信道${W_1}:X \to Y$收到Y，窃听者通过窃听信道 ${W_2}:X \to Z$收到Z。当不等式 $I(X;Y) > I(X;Z)$成立时，文献^[12]构造出一个能够多次进行消息认证的认证协议，并且认证次数的增加对敌手攻击成功的概率的影响是可以忽略的。而文献^[2]的结论说明上述结果在无噪声信道下是不可能的。相关的研究工作还包括文献^[13]提出的在MIMO衰落信道下的认证问题，该协议假设Alice和Bob之间没有共享密钥，并且假设攻击者只发起冒充攻击。该协议在文献^[14]中得到了进一步的研究。

本文考察如下认证框架：Alice首先通过无噪声信道将消息$M$发送给Bob，接着利用安全密钥生成一个认证标签，再将认证标签转化为码字 ${X^n}$，最后通过窃听信道模型将码字传输给Bob。本文定义了固定标签率下的安全认证信道容量，并证明该认证信道容量等于 $H(X|Z)$。这也进一步证明了文献^[15]提出的协议在本文的认证模型中是可达容量的。

一条输入字母表为X，输出字母表为Y的信道称为离散无记忆信道(discrete memoryless channel, DMC)当且仅当这个信道可以有随机矩阵 $W = {\{ W(y|x)\} _{x \in X,y \in Y}}$ $W(|x)$是指当输入为x时，在信道输出端的输出分布情况，即 $W(y|x) = {P_{Y|X}}(y|x)$。当输入为序列 ${x^n} = {x_1}{x_2} \cdots {x_n}$，输出为 ${y^n} = {y_1}{y_2} \cdots {y_n}$时，有：

${P_{{Y^n}|{X^n}}}({y^n}|{x^n}) = \prod\limits_{i = 1}^n {{P_{Y|X}}} (y_i^{}|{x_i}) = \prod\limits_{i = 1}^n {W({y_i}|{x_i})} $

定义 1 把输入相同的两个离散无记忆信道 ${W_1}:X \to Y$， ${W_2}:X \to Y$称为窃听信道模型。其中，W₁为主信道；W₂为窃听信道。

如图 1所示，考虑两个离散无记忆信道${W_1}:X \to Y$， ${W_2}:X \to Z$。Alice和Bob共享一个对称密钥$K$，其中$K$是从一个有限集 $ [\kern-0.15em[ {\rm K} ]\kern-0.15em] $中均匀的随机产生。他们由信道W₁相连，当Alice传输 $X \in [\kern-0.15em[ X ]\kern-0.15em] $时，Bob以概率 ${P_{Y|X}} = {W_1}(Y|X)$接收到 $Y \in [\kern-0.15em[ Y ]\kern-0.15em] $(其中，对任意随机变量R， $ [\kern-0.15em[ R ]\kern-0.15em] $定义为R的事件域)。同时，X将在窃听信道W₂上传输。窃听者Oscar收到的信道输出变量为 $Z \in [\kern-0.15em[ Z ]\kern-0.15em] $，其概率分布满足 ${P_{Z|X}} = {W_2}(Z|X)$。Alice的目标是传输消息$M$的同时并对消息进行认证。为此，定义认证模型为：记 $ [\kern-0.15em[ M ]\kern-0.15em] $为消息域，Alice将传输并认证消息 $M \in [\kern-0.15em[ M ]\kern-0.15em] $。

图1

图1系统模型

1) Alice通过无噪声信道发送消息$M$给Bob；

2) Alice利用哈希函数 $h: [\kern-0.15em[ M ]\kern-0.15em] \times [\kern-0.15em[ {\rm K} ]\kern-0.15em] \to [\kern-0.15em[ T ]\kern-0.15em] $产生一个标签 $T = {h_K}(M)$；然后利用有密钥的编码函数 ${f_K}: [\kern-0.15em[ T ]\kern-0.15em] \to { [\kern-0.15em[ X ]\kern-0.15em] ^n}$产生认证码 ${X^n} = {f_K}(T)$；最后在窃听信道 $({W_1},{W_2})$上发送认证码 ${X^n}$。

3) Bob从无噪声信道接收到消息 $M'$，同时从信道W₁接收到失真的认证码 ${Y^n}$。Bob计算 $T' = {h_K}(M')$，并通过带密钥的函数 ${{\mathop{\rm g}\nolimits} _K}:T \times {Y^n} \to \{ 0,1\} $认证 $(T',{Y^n})$。如果函数 ${{\mathop{\rm g}\nolimits} _K}$的输出是1，则接受消息 $M'$；否则，拒绝。

把满足上述模型的协议称为一个认证协议(记为 $\Pi $)，如果生成的认证码为 ${X^n}$，即认证码的长度为n，用 ${\Pi _n}$表示 $\Pi $。

协议 $\Pi $的目的是认证消息$M$。一个认证失败包含有两种可能性：完备性错误或者敌手攻击，其中，完备性错误是指没有敌手存在时发生了错误。在本文的模型中，从Alice到Oscar有一条DMC信道相连。Oscar可以插入和修改在无噪声信道的传输消息。假设从Oscar到Bob的信道是无噪声的，且敌手具有无限的计算能力。本文希望在敌手Oscar多次通过窃听信道W₂得到认证的观察值并且多次动态地修改无噪声信道的消息的前提下，Oscar还是不能伪造一个可通过认证的消息。这里“多次”的上界是认证码长度的任意多项式。形式化地，Oscar可发起两类攻击。

1) 假设Alice已经认证了消息 ${M_1},{M_2}, \cdots ,{M_{i - 1}}$。为了认证消息 ${M_i}$，Alice在无噪声信道上发送消息 ${M_i}$，并且在信道 $({W_1},{W_2})$上发送认证码 $X_i^n$。Oscar可以观察到 ${M_i}$并可以将其篡改为 ${M_i}^\prime $。还可以观察到信道 ${W_2}$的输出 $Z_i^n$。Bob可以接收到无噪声信道的消息 ${M_i}^\prime $和信道 ${W_1}$的输出 ${b_i}: = {{\mathop{\rm g}\nolimits} _k}({T'_i},{M_i}^\prime )$，这里 ${T'_i} = {h_{\rm{k}}}({M_i}^\prime )$。当 ${b_i} = 1$并且 ${M_i}^\prime \ne {M_i}$时，攻击成功。其中， ${M_i}^\prime $的选取是基于Oscar的随机源R，消息 ${M_i}^\prime $和前 $i - 1$阶段收集到的信息： $\{ ({M_j},Z_j^n)\} _{j = 1}^{i - 1}$；以及在第一型攻击下的判定比特 $\{ {b_j}^\prime \} $和在第二型攻击下的判定比特 $\{ {\hat b_j}\} $。

如果 ${M_t}^\prime = {M_t}$(即不发起攻击)， ${b_t} = 1$是(几乎)可以确定的，因此可以将其从 $\{ {b_j}^\prime \} $中去掉。

2) Osca可以自适应地通过无噪声信道发送给Bob任何消息 ${M_t} \in [\kern-0.15em[ M ]\kern-0.15em] $和 $\hat Y_t^n \in { [\kern-0.15em[ Y ]\kern-0.15em] ^n}$。Oscar将会学习到Bob的判定比特 ${\hat b_i}: = {{\mathop{\rm g}\nolimits} _k}({\hat T_t},{\hat Y^n})$，其中， ${\hat T_t} = {h_{\rm{k}}}({\hat M_t})$。如果 ${\hat b_i} = 1$，则攻击成功。这里 $({\hat M_t},\hat Y_t^n)$的计算是基于Oscar的随机源R和前 $i - 1$阶段收集到的信息 $\{ ({M_j},Z_j^n)\} _{j = 1}^{i - 1}$、 $\{ {b_j}^\prime \} $和 $\{ {\hat b_j}\} $。

在引入敌手模型后，开始形式化定义认证。认证的性质由完备性和认证性组成。完备性指敌手不存在时，Bob应当以很高的概率接受消息$M$为合法的消息；认证性指在敌手存在的前提下，认证失败的可能性应该很小，其中，认证失败是指接受了敌手篡改过的消息。

定义 2 称一个函数 $f: \to $是可忽略的当且仅当对任意多项式函数 ${\mathop{\rm Ploy}\nolimits} : \to $，存在一个自然数 ${N_0}$，当 $n \ge {N_0}$时，有：

${\mathop{\rm f}\nolimits} (n) \le \frac{1}{{{\mathop{\rm Ploy}\nolimits} (n)}}$

定义 3 给定一个窃听信道模型${W_1}:X \to Y$，${W_2}:X \to Y$，称协议 $\Pi $是认证安全的当且仅当 $\Pi $满足下列条件：1) 完备性：如果敌手不存在，那么Bob将以指数(对于n)小的概率拒绝合法的消息$M$；2) 强安全性：记VIEW(Oscar)为窃听者Oscar的观察值，那么，互信息 $I(T;{\mathop{\rm VIEW}\nolimits} (Oscar))$是可忽略的(对于n)；3) 认证性：如果第二型攻击的次数不超过多项式(对于n)，那么敌手攻击成功的概率 $\Pr ({\rm{succ}})$是可忽略的(对于n)。

完备性说明合法消息有很高的概率通过认证；强安全性说明认证过程中的认证标签不会向敌手泄露；认证性说明敌手不能伪造一个消息并通过认证。

限制第二型攻击次数是不可避免的，这是因为敌手Oscar可以持续地选择同一个消息$M$并选择所有可能的 ${Y^n}$，并通过无噪声信道发送给Bob。由于 ${\left[\kern-0.15em\left[ Y \right]\kern-0.15em\right]^n}$是有限集，Oscar总能够选中某些 ${Y^n}$使得攻击成功。限定第二型攻击的次数不超过多项式的原因是，每一次攻击都涉及接收方Bob，而要求Bob的复杂度超过多项式是不实际的。另外，由于第一型攻击的次数等于Alice发送消息的次数，故第一型攻击自然的被限定在多项式内。

考虑到在窃听信道上通信是比较昂贵的资源，因此，希望尽可能少地利用这一昂贵的资源。针对有效性分析，定义了两类有效性测度。

第一类测度称为标签率，其定义是：

${\ell _{{\rm{auth}}}} = \log |M|log|T|$ 即消息源长度与标签长度的比值。

第二类测度称为标签的信道编码率，定义为：

${\ell _{{\rm{chan}}}} = \frac{1}{n}\log |T|$ 即标签长度和编码长度的比值。

事实上， ${\ell _{{\rm{auth}}}}$和 ${\ell _{{\rm{chan}}}}$都涉及信道的使用效率。一方面，对于固定的 ${\ell _{{\rm{chan}}}}$，更大的 ${\ell _{{\rm{auth}}}}$意味着同样的消息源具有更小的标签长度，因此，会更少使用窃听信道 $({W_1},{W_2})$。另一方面，对于固定的 ${\ell _{{\rm{auth}}}}$，更大的 ${\ell _{{\rm{chan}}}}$意味着同样的n，可以在信道上传输更长的标签，因此，消息源的长度也随之更长。也就是说，增加 ${\ell _{{\rm{auth}}}}$和 ${\ell _{{\rm{chan}}}}$的值都能够提高信道的使用率。本文协议主要关注如何提高 ${\ell _{{\rm{chan}}}}$的值，这是传统密码学解决的问题。

在窃听信道下安全认证信道容量的定义如下：

定义 4 给定一个窃听信道模型${W_1}:X \to Y$，${W_1}:X \to Y$。对于任何以 ${\ell _{{\rm{auth}}}}$的标签率认证安全的协议 $\Pi $，可达的最大信道率 ${\ell _{{\rm{chan}}}}$称为以标签率为 ${\ell _{{\rm{auth}}}}$的安全认证信道容量，简记为 ${C_{{\rm{chan}}}}({\ell _{{\rm{auth}}}})$。

先引用一个重要的定理，该定理是构造一个可达安全认证容量的认证协议的基础。

定理 1^[15] 记 $X,Y,Z$分别为 $ [\kern-0.15em[ X ]\kern-0.15em] , [\kern-0.15em[ Y ]\kern-0.15em] , [\kern-0.15em[ Z ]\kern-0.15em] $上的随机变量，且 ${P_{Y|X}} = {W_1}$， ${P_{Z|X}} = {W_2}$为两个DMC。有一个类P使得X的概率分布 ${P_X} = P$，且对于任意 $x \in [\kern-0.15em[ X ]\kern-0.15em] $，有 $P(x) > 0$。若存在 $\tau > 0$，使得 $I(X;Y) > $ $I(X;Z) + \tau $，那么，对于任意正整数I,J满足条件：

$\begin{array}{c} 0 \le \frac{1}{n}\log J \le H(X|Y) + \tau \\ 0 \le \frac{1}{n}\log I \le I(X;Y) - I(X;Z) - \tau \end{array}$ 则存在不相交的子集簇 ${C_{ij}} \subset T_P^n$( $i \in [I]$, $j \in [J]$)，使得对于足够大的n，有下列3个性质成立：

1) 对于每一个j，子集 ${C_{j}} \buildrel \Delta \over = { \cup _i}{C_{ij}}$是信道 ${W_1}$上一个信道编码 $({f_j},{g_j})$的码本，并且该信道编码的平均解码错误率是指数(对于n)小的。其中， ${f_j}$将消息m映射到 ${C_{j}}$的第m个码字。

2) 记J为 $[J]$上的随机变量，I为 $[I]$上的随机变量， ${\hat Z^n}$为输入 ${\hat X^n} \leftarrow {C_{IJ}}$时信道 ${W_2}$的输出。如果联合分布 ${P_{IJ}} = {P_J}I$ ，那么，存在 ${\beta _2} > 0$，使得 $I(I,J;{\hat Z^n}) \le {2^{ - n{\beta _2}}}$(该结果不依赖于 ${P_J}$)。

3) 对于 $[J]$上的任意随机变量J， $[I]$上的任意随机变量I，记 ${\hat Z^n}$为输入 ${\hat X^n} \leftarrow {C_{IJ}}$时信道 ${W_2}$的输出。假设 $[J]$上的任意随机变量 $J'$使得 $J' \ne J$，且满足下列条件：

① $SD({P_{J'J}};{P_{J'J|I}}) \le {\delta _1}$；

② $J' \to IJ \to {\hat X^n} \to {\hat Y^n}$形成Markov链；

③ 对任意 $j',j$，有：

${P_{J'J}}(j',j) \le \frac{{{2^{{n^\omega }}}}}{{J(J - 1)}} + d(j',j)$ 且函数 $d(,)$满足不等式：

${P_{J'J}}(j',j) \le \frac{{{2^{{n^\omega }}}}}{{J(J - 1)}} + d(j',j)$

那么，对于足够大的n，有：

$P({\hat Y^n} \in {T_{{{[W]}_\varepsilon }}}({{\bf{C}}_{IJ'}})) \le {2^{ - n\omega }} + {\delta _1} + {\delta _2}$ 式中， $\omega $是开区间(0,1)上的常数。

文献^[15]所构造的安全认证协议描述如下。

记${W_1}:X \to Y$，${W_2}:X \to Y$为窃听信道模型。假设 $I(X;Y) > I(X;Z) + \tau $，其中 $\tau $为大于0的常数。X的概率分布 $\tau $为类P，并且对任意的 $x \in X$有 $P(x) > 0$。记 $T_P^n$上的子集簇 ${C_{ij}}\;(i = 1,2, \cdots ,I;\;$ $j = 1,2, \cdots ,J)$是通过定理1得到的。令 ${K_1} = \{ 1,2, \cdots ,I\} $， $h: [\kern-0.15em[ M ]\kern-0.15em] \times [\kern-0.15em[ {K_0} ]\kern-0.15em] \to [\kern-0.15em[ T ]\kern-0.15em] $是一个 $\varepsilon {\rm{ - ASU}}$哈希函数^[15]，其中，集合 $ [\kern-0.15em[ {K_0} ]\kern-0.15em] $是密钥空间， $ [\kern-0.15em[ T ]\kern-0.15em] \subseteq \{ 1,2, \cdots ,J\} $。Alice和Bob预先共享了对称密钥 $({K_0},{K_1}) \in [\kern-0.15em[ {K_0} ]\kern-0.15em] \times [\kern-0.15em[ {K_1} ]\kern-0.15em] $。如果Alice要传输消息 $M \in [\kern-0.15em[ M ]\kern-0.15em] $给Bob，那么，执行下列步骤：

1) Alice计算 $T = {h_{{K_0}}}(M)$，并且从 ${C_{{K_1}T}}$中随机地选出一个码字 ${X^n}$。Alice再将消息$M$通过无噪声(无认证的)信道传给Bob。消息$M$经过Oscar后，Bob收到$M'$。最后，Alice通过信道 $({W_1},{W_2})$传输 ${X^n}$。Oscar通过 ${W_2}$收到 ${Z^n}$，Bob通过 ${W_1}$收到 ${Y^n}$。

2) 获得 $M'$和 ${Y^n}$后，Bob计算 $T' = {h_{{K_0}}}(M')$。如果 ${\mathop{\rm g}\nolimits} ({Y^n}) \in {C_{{K_1}T'}}$，Bob接受 $M'$；否则，拒绝。

在定理1中， ${f_j}$将消息 $l$编码成码本 ${C_{j}}$中的第 $l$个码字， ${g_j}({Y^n})$将 ${Y^n}$解码成 $ \bot $或者 ${C_{j}}$中码字的编号。由于编号和码字是一一对应的，因此，在本文的构造中，g_j(Yⁿ)被定义为将Yⁿ解码 $ \bot $或者 ${C_{j}}$中码字。

定理 2 对于上述认证协议，存在一个恰当的参数输入，使得对任意的 ${\ell _{{\rm{auth}}}}$，以及任意的 $\delta \in (0,H(X|Z))$，有 ${\ell _{{\rm{chan}}}} = H(X|Z) - \delta $。

证明：该定理证明类似于文献^[15]的定理3，这里将其略去。

定理 3 给定窃听信道模型${W_1}:X \to Y$，${W_2}:X \to Y$。对于任何以 ${\ell _{{\rm{auth}}}}$的标签率认证安全的协议 $\Pi $，有 ${\ell _{{\rm{chan}}}} \le H(X|Z)$。

证明：由强安全性可知:

$H(T) = H(T|{Z^n}) + I(T;{Z^n}) \le $

$\begin{array}{c} H(T|{Z^n}) + I(T;{\rm{View}}({\rm{Oscar}})) \le \\ H({X^n}|{Z^n}) + {\varepsilon _n} \le nH(X|Z) + {\varepsilon _n} \end{array}$
式中，第1个不等式成立的原因是 ${Z^n} \in {\mathop{\rm VIEW}\nolimits} (Oscar)$；第2个不等式成立是因为T可以由Xⁿ完全确定；第3个不等式成立是因为Xⁿ和Zⁿ是独立同分布且窃听信道是离散无记忆的。

故有：

$\,\;{\ell _{{\rm{chan}}}} \le H(X|Z)$
证毕。

定理 4 给定窃听信道模型${W_1}:X \to Y$，${W_2}:X \to Y$。对于任意 ${\ell _{{\rm{auth}}}}$，认证信道容量为 ${C_{{\rm{chan}}}}({\ell _{{\rm{auth}}}}) = H(X|Z)$。

证明：由定理2和定理3可以得出结论。

Alice在一个无噪声信道的辅助下，利用窃听信道${W_1}:X \to Y$，${W_2}:X \to Y$来认证消息$M$，其中，Alice和Bob事先共享一个对称密钥。在这个认证框架下，Alice利用无噪声信道来传输要认证的消息$M$，然后在窃听信道上传输认证标签$T$所对应的码字。证明了本文考虑的认证模型下的安全认证容量为 $H(X|Z)$。文献^[15]提出了一个高效的消息认证协议，本文的结果说明了该协议是可以达到认证容量的。将来的工作会探究怎样构造出一个计算有效的协议？