无线射频识别(Radio Frequency Identification，RFID)技术是一种在开放性环境中自动识别对象的技术，因其成本低廉、部署简易而被广泛地应用于支付系统、供应链管理和产品防伪等领域. RFID技术的广泛应用需要保证系统中标签的低成本，但标签的低成本限制了其计算能力，也为保证阅读器与标签之间的通信隐私安全增加难题. LPN(Learning Parity with Noise)^[1]是计算复杂性领域的一个困难问题，其所涉及的计算只是进行简单的异或操作，对计算量和存储量的要求低，适用于标签这种资源受限的设备.

在RFID研究领域中，大量工作致力于研究轻量级的RFID认证协议，其中一类是基于LPN问题设计的认证协议，包括HB协议^[2]、HB⁺协议^[3]、HB^#协议^[4]、Auth协议^[5]、Auth^#协议^[6]、LPNAP协议^[7]和Auth-Hash协议^[8]等. 上述这类基于LPN问题设计的协议具有结构简单、抗量子攻击和计算复杂度低等优点，但该类协议^[2-8]只提供认证性，不具备隐私安全性.

隐私安全性和识别是RFID系统的2个主要目标^[9]，大多数RFID协议为了保证隐私性而降低识别效率. 阅读器搜索系统中所有的标签来识别单个标签，实现了隐私识别. 但是在大型RFID系统中，对每个标签识别执行线性搜索，尤其是在需要同时识别多个标签的应用中可能是一项繁琐的任务，并且可能导致拒绝服务攻击. 因此，对于一个实用的RFID系统，必须设计更加快速的识别方案.

为了提高识别效率，学者们^[10-13]以树型结构存储标签，将识别效率提高至对数级别，但是这类基于树型结构设计的协议有2个缺点：(1)在无线信道中需要进行大量的通信；(2)一旦某个标签的信息泄露了，就会泄露其他未被破解的标签的信息，无法保证标签的隐私性. 由于树型结构无法保证标签的隐私性，ALOMAIR等^[14]基于hash函数，设计了识别速率达到O(1)的BAJR协议，且保证了隐私安全，但是该协议使用hash函数，使得标签门电路复杂，无法实现低成本. 为了实现标签的低成本，MAMUN等^[15]提出了基于LPN设计且识别效率达到O(1)的MMR协议，并证明该协议能抵抗一般中间人攻击并实现隐私安全. 由于MMR协议用于更新索引的值在上一次认证过程中会作为第二轮响应信息发送给阅读器，攻击者通过比对信息就能将标签的2次行为联系在一起，因此，MMR协议不具备隐私性.

本文借鉴MMR协议的设计思路和SFP(Simple and Forward Private)通用协议^[16]构造的设计方法，提出了具有快速识别的隐私保护认证协议(Fast Identification and Privacy-preserving Authentication Protocol，FIP_Auth)：利用基于LPN问题构造的伪随机数发生器和大型存储设备数据库设计FIP_Auth协议，实现标签的低成本，并达到快速识别和保证隐私性的目的.

1.   预备知识

1.1   符号说明

$\mathbb{Z}_{2}$表示有限域{0, 1}，有限域{0, 1}^*表示任意长度的二进制比特串的集合，对于{0, 1}^*中的元素，有时看成比特串，有时看成向量，具体依上下文而定. $_2^k$表示$\mathbb{Z}_{2}$上的k维线性空间；$\boldsymbol{X} \in \mathbb{Z}_{2}^{l \times n}$是l×n的二进制矩阵，X^T表示X的转置矩阵；$\boldsymbol{x} \in \mathbb{Z}_{2}^{l}$是长度为l的二进制向量，|x|表示x的长度，wt(x)表示x的汉明重量；$\boldsymbol{r} \stackrel{\$}{\leftarrow} \mathbb{Z}_{2}^{2 l}$表示从$\mathbb{Z}_{2}^{2 l}$中均匀抽样出一个二进制向量r；x_↓a表示与向量a相关的x的子向量：对于向量x、a，如果a[i]=0, 则删除x[i], 否则保留x[i] (例：x=(1, 1, 0, 0, 1, 1)，a=(1, 1, 0, 1, 0, 0)，则x_↓a=(1, 1, 0))；Ω表示$\mathbb{Z}_{2}^{2 l}$中汉明重量为l的所有向量的集合；Ber_τ表示参数为τ的贝努利分布(τ∈[0, 1/2]), e←Ber_τⁿ表示从贝努利分布抽样出的n维二进制向量；符号"||"表示2个比特串的连接，也可表示2个向量的连接(例：a=(0, 1, 0, 0)，b=(1, 0, 0, 1)，则a||b=(0, 1, 0, 0, 1, 0, 0, 1))；U_n表示在{0, 1}ⁿ上随机变量的均匀分布.

1.2   困难性问题

定义1^[17]  (LPN问题)假设e←Ber_τⁿ，wt(e)＜τn，噪声参数τ∈[0, 1/2]，x←$\mathbb{Z}_{2}^{2 l}$，R←$\boldsymbol{R} \stackrel{\$}{\leftarrow} \mathbb{Z}_{2}^{2 l \times n}$，给定τ、R以及$\boldsymbol{r}=\boldsymbol{R}^{\mathrm{T}} \cdot \boldsymbol{x} \oplus \boldsymbol{e}$，LPN问题要求找到${\boldsymbol{x}}' \in \mathbb{Z}_{2}^{2 l}$，使得$\mathrm{wt}\left(\boldsymbol{r} \oplus \boldsymbol{R}^{\mathrm{T}} \cdot \boldsymbol{x}^{\prime}\right)＜\tau n$. LPN假设表明：在给定τ、R、r的情况下，攻击者无法在多项式时间内恢复x.

定义2^[18]  一个伪随机数产生器(Pseudorandom Generator，PRG)是一个确定性函数G：{0, 1}^*→{0, 1}^*，需要满足以下2个条件：

(1) 拉伸：存在一个拉伸函数h：$\mathbb{N} \rightarrow \mathbb{N}$，对所有的$n \in \mathbb{N}$, 有h(n)>n, 且对所有的x∈{0, 1}^*，有|G(x)|=h(|x|)；

(2) 伪随机性：集合$\left\{G\left(U_{n}\right)\right\}_{n \in \mathbb{N}}$、$\left\{U_{h(n)}\right\}_{n \in \mathbb{N}}$是计算不可区分的.

当h(n)=n+Ω(n)时，G是线性拉伸的伪随机数产生器(Linear-stretch Pseudorandom Generator，LPRG). 默认G是多项式时间可计算的.

定义3^[2]  (可忽略函数)函数neg(n)如果满足：对于任意常数c>0, 存在足够大的n，使得neg(n)＜n^-c，则称neg(·)是可忽略函数.

1.3   RFID系统

一般地，RFID系统主要由标签、阅读器和后端数据库三部分组成. 标签内存储标签与阅读器认证的信息及保护标签自身隐私的信息，后端数据库存储系统中所有标签的信息. 一般认为标签与阅读器之间的通信是不安全的，阅读器与后端数据库之间的通信是安全的. RFID系统的工作流程如下：

(1) 阅读器通过天线发射无线电载波信号；

(2) 标签进入阅读器的工作范围后，将其内部信息通过天线发送出去；

(3) 阅读器对来自标签的信息进行处理，将结果传到后端数据库；

(4) 后端数据库对接收到的信息进行处理，将结果返回给阅读器.

1.4   认证协议及其安全性

认证协议是指在阅读器和标签之间执行的交互式协议. 标签的拥有者使用标签向阅读器证明自己的身份，阅读器反馈认证结果. 在RFID系统中，阅读器与标签通过无线信道通信，该信道是不安全的，易遭受各种安全攻击，主要有被动攻击、主动攻击、中间人攻击和异步攻击等. 其中，异步攻击指攻击者可以阻断协议通信的进行，使标签和阅读器处于异步状态，并使标签将来的身份验证变得不可能.

此外，由于低成本的标签不具备任何防篡改的能力，攻击者试图通过破解标签来获得其内部状态信息，进而追踪标签之前的通信隐私. 前向隐私指的是攻击者破解了某个标签，但是攻击者不能跟踪该标签未被破解之前的所有通信隐私信息. 准确地说，前向隐私由在RFID系统中有攻击者A参与的前向隐私游戏Game_A来确定，方法如下：先利用前向隐私游戏Game_A来模拟现实的RFID攻击环境，然后根据游戏中2个标签行为的不可区分性来说明2轮通信的RFID认证协议的前向隐私安全.

前向隐私游戏Game_A由2个阶段组成，Game_A中的攻击者A是由算法A₁和算法A₂组成. 第一阶段，算法A₁初始化RFID系统，并且可以随意调用预言机O₁、O₂和O₃，总共调用次数不超过q次，输出2个未被调用过O₃预言机的标签T₀、T₁和状态信息st，将这2个标签作为下一阶段的候选挑战标签. 第二阶段，首先，游戏选取一个随机数$\beta \stackrel{\$}{\longleftarrow}\{0, 1\}$；然后，把T_β给攻击者作为挑战标签，算法A₂可以对T_β随意调用预言机O₁、O₂和O₃来进行查询；最后，算法A₂输出一个随机数β′，若β=β′，则表示攻击者A成功地攻击了RFID系统的前向隐私性.

Game_A中涉及的3个预言机O₁、O₂和O₃定义如下:

(1) Launch(R)：使阅读器产生一个新的会话标识sid和协议中阅读器第一轮产生的消息m₁，该预言机O₁模拟窃听获取第一轮协议的通信消息;

(2) SendTag(sid, m₁, T)：该预言机O₂模拟窃听篡改标签的计算和协议信息，输出第二轮的通信信息m₂;

(3) Reveal(T)：该预言机O₃模拟破解标签，获取标签T的内部信息.

定义4^[16]  (前向隐私性)在前向隐私游戏Game_A中，若不存在任意多项式时间攻击者A在时间t内以ε不可忽略的优势攻击成功，则称该RFID系统是前向隐私安全的.

2.   FIP_Auth协议的设计方案

本节将基于LPN设计的伪随机数产生器G^[19]应用于RFID系统中，并借鉴BAJR协议^[14]在解决协议发生异步攻击的情况下识别效率是O(1)的方法，利用RFID系统中拥有的大型存储设备数据库设计具有快速识别的隐私保护认证协议(FIP_Auth)，该协议的设计方案具体表述如下.

2.1   系统初始化FIP_Init

设N是系统中标签的总数，C是计数器计数的最大值，每个标签T_i存储其初始密钥对(R_i1, x_i1)，G₁与G₂为2个PRG函数，令函数G₁(x)的输出长度为L，L>2l(标签密钥x_i1的长度为2l). 对于每个标签T_i(i=1, 2, …, N)和每一个j(j=1, 2, …, C)，将标签T_i存储的密钥信息x_ij作为伪随机数产生器G₁的输入，计算数据库初始化所需要的索引值I_ij=G₁(x_ij)，I_ij表示第j次识别标签T_i时的索引；将标签T_i存储的密钥信息R_ij作为伪随机数产生器G₂的输入，G₂(R_ij)=x_{i, j+1}||R_{i, j+1}用来更新标签T_i的密钥信息(R_{i, j+1}, x_{i, j+1}). 为了方便，根据计算的所有索引值I_ij建立数据库初始化所需的索引值表(图 1)，其中第i行表示识别标签T_i所需要的索引信息.

图  1  RFID系统的数据库初始化所需的索引值表

Figure  1.  The table of index value required for RFID system database initialization

下载: 全尺寸图片 幻灯片

得到数据库初始化所需的索引值I_ij后，根据该索引值构造RFID系统的数据库. 由于函数G₁的输出长度为L，所以索引值I_ij的长度为L，需要O(2^L)的存储空间来存储数据库初始化所需索引值I_ij.为了节省存储空间，将数据库分为3个逻辑部分M-Ⅰ、M-Ⅱ和M-Ⅲ. 具体构造(图 2)如下: (1)M-Ⅰ只含有1张表，表示为T₁. 取L的高s位(s满足2^s大小的存储是可行的)来构建T₁表，则T₁的高s位相同的索引值存储在M-Ⅱ的同一个小表中，T₁的第i行存储高s位为i-1的所有索引值的低L-s位在M-Ⅱ中的表的位置. (2)M-Ⅱ由若干个小数据表组成，表示为T_2i(i=1, 2, …, 2^s).M-Ⅱ的表的每条记录包含2个域，第1个域是存储索引I_ij的低L-s位，表示为(I_ij)_L-s；第2个域是一对指针(i, j)，其中i表示M-Ⅲ中的第i张表，j表示该表中的第j行.(3)M-Ⅲ由N个大小为C的数据表组成，表示为T_3i(i=1, 2, …, N).T_3i的第i张表存储标签T_i的信息，这张表中的第j行表示标签在第j次识别时的内部状态信息(R_ij, x_ij).

图  2  RFID系统的数据库结构图

Figure  2.  The diagram of the RFID system database structure

下载: 全尺寸图片 幻灯片

FIP_Auth协议的数据库结构与BAJR协议的数据库结构类似，但又有所不同. BAJR协议中总是阅读器与数据库先更新密钥信息，待标签对阅读器认证成功后，标签才进行密钥更新，数据库只需要存储标签当前认证成功后的密钥更新信息并且保存上一次认证通过(即当前进行认证)的密钥信息. 当发生异步攻击时，标签的当前密钥信息是存储在数据库中的，可以通过阅读器的认证. FIP_Auth协议的密钥更新是标签与数据库同时进行，而阅读器不需要密钥更新，因此，FIP_Auth协议的数据库M-Ⅲ需要预先存储标签的C条密钥信息. 当发生异步攻击时，因标签的C条密钥信息已存储在数据库中，标签的信息可以在数据库中找到使得阅读器可以对标签进行认证，达到异步攻击安全. 若某标签认证达到C次，则需要更新数据库M-Ⅲ中该标签未来的C条记录.

2.2   FIP_Auth协议的执行过程

给定安全参数l, $n \in \mathbb{N}$，每个标签T_i存储矩阵${{\boldsymbol{R}}_i} \in \mathbb{Z}_{2}^{l \times n}$和密钥$\boldsymbol{x}_{i} \in \mathbb{Z}_{2}^{2 l}$，R_i和x_i在每次认证时进行更新.将每个标签的密钥x_i作为伪随机数产生器G₁的种子进行计算，计算结果作为建立后端数据库的索引，再以R_i为输入，计算G₂(R_i)，从而更新R_i和x_i.阅读器同样具有计算G₁和G₂的能力，参数τ'=1/4+ τ/2是阅读器验证的阈值，其中τ是贝努利分布Ber_τ的参数. FIP_Auth协议的执行过程(图 3)如下：

图  3  RFID认证协议FIP_Auth的执行过程

Figure  3.  The implementation process of RFID authentication protocol FIP_Auth

下载: 全尺寸图片 幻灯片

(1) 阅读器随机产生长度为2l的挑战向量a，其汉明重量为wt(a)=l，将其发送给标签.

(2) 标签首先判断wt(a)是否等于l，若不等于l，则拒绝，否则标签产生向量e←Ber_τⁿ；然后计算${\boldsymbol{r}} = {\boldsymbol{R}}_i^{\rm{T}} \cdot {\left( {{{\boldsymbol{x}}_i}} \right)_{ \downarrow {\boldsymbol{a}}}} \oplus {\boldsymbol{e}}, {G_1}\left( {{{\boldsymbol{x}}_i}} \right) = {{\boldsymbol{I}}_i}$和${G_2}\left( {{{\bf{R}}_i}} \right) = {\overline {\bf{R}} _i}\left\| {{{\overline {\bf{x}} }_i}} \right.$, 并将(I_i, r)发送给阅读器；最后标签更新密钥x_i=x_i和矩阵R_i=R_i.

(3) 阅读器收到标签发来的信息(I_i, r)，利用索引I_i搜索数据库：由I_i的高s位定位数据库M-Ⅰ的地址，该地址中存储了指向M-Ⅱ中小表的地址指针. 此时会出现3种情况：①指针指向空，说明没有相关标签信息；②指针指向的小表中只有1条记录，此记录的第2个域存储了指向M-Ⅲ中标签T_i信息(R_i, x_i)的地址指针，此时可获取标签T_i信息(R_i, x_i)，并返回给阅读器，阅读器计算$\mathrm{wt}\left(\boldsymbol{r} \oplus \boldsymbol{R}_{i}^{\mathrm{T}} \cdot\left(\boldsymbol{x}_{i}\right)_{\downarrow \boldsymbol{a}}\right)$，如果$\operatorname{wt}\left(\boldsymbol{r} \oplus \boldsymbol{R}_{i}^{\mathrm{T}} \cdot\left(\boldsymbol{x}_{i}\right)_{\downarrow \boldsymbol{a}}\right)>n \cdot \tau^{\prime}$，则本次认证失败，否则认证成功；③指针指向的小表中有多条记录，此时需要将I_i的低(L-s)位与小表中的每条记录的第1个域值进行比较，找到相等值之后即可得到标签T_i信息的存储地址，阅读器得到标签信息，对标签进行认证.

由索引值I_i可知当前是第几次识别标签T_i. M-Ⅲ中除了存储标签T_i的实际信息(R_i, x_i)外，还存储了该信息对应的识别次数j.每次在M-Ⅲ中获取标签信息时，都需要先判断j是否小于等于C. 若j=C，则需要对数据库进行更新操作，更新标签T_i的未来C次识别所需要的密钥信息. 更新操作如下：

首先，计算标签T_i未来所需的C个索引值. 根据当前数据库标签的信息(R_iC, x_iC)，计算G₂(R_{i, k-1})=x_ik||R_ik，索引I_ik=G₁(x_i(k-1))(k=C+1, …, 2C). 然后，取索引I_ik的前s高位，定位数据库M-Ⅰ的地址. 若该地址中存储的地址指针指向空，则在M-Ⅱ中新建一张表，以存储I_ik的低L-s位和指向M-Ⅲ的地址(i, k-C)；若不指向空，则遍历该小表，在小表末尾添加一条记录存储I_ik的低L-s位和指向M-Ⅲ的地址(i, k-C). 此操作之后，原标签T_i存储在M-Ⅲ中的C条记录将被更新的C条记录所覆盖.

2.3   伪随机数产生器的构造

FIP_Auth协议中使用的伪随机数产成器G₁和G₂构造如下：取t、s是大于1的任意正整数，c、k₁是实数. 令m₁=k₁r₁，M_r1是$\mathbb{Z}_{2}$上每行包含1的个数至多为s的m₁×r₁的矩阵，g: $\mathbb{Z}_{2}^{t m_{1} / c} \rightarrow \mathbb{Z}_{2}^{t m_{1}}$是ε-biased产生器^[20]；定义函数G₁，设L是G₁函数输出长度，取k₁=L/(2l(1+t)-tL(1+1/c))，r₁=L/(k₁+tk₁), 则

其中，$\boldsymbol{x} \in \mathbb{Z}_{2}^{2 l}$，x_r1是x的高r₁位，x_t·m1是x高r₁位后的t·m₁位，x_t·m1/c是x的低t·m₁/c位，E(x_t·m1)=(Π_j=1^t(x_t·m1)_t·(i-1)+j)_i=1^m₁，则G₁：$\mathbb{Z}_{2}^{2 l} \rightarrow \mathbb{Z}_{2}^{L}$.

令m₂=k₂r₂，其中k₂是实数.M_r2是$\mathbb{Z}_{2}$上每行包含1的个数至多为s的m₂×r₂的矩阵集合；g: $\mathbb{Z}_{2}^{t m_{2} / c}$→$\mathbb{Z}_{2}^{t m_{2}}$是ε-biased产生器；取k₂=(nc+c)/(nc-tn-2tc-2t)，r₂=(ln+2l)/(k₂+tk₂)，定义函数G₂为：

其中, $\boldsymbol{R} \in \mathbb{Z}_{2}^{l \times n}$，R_r2是R的高r₂位，R_t·m2是R高r₂位后的t·m₂位，R_t·m2/c是R的低t·m₂/c位，E(R_t·m2 = (Π_j=1^t(R_t·m2)_t·(i-1)+j)_i=1^m₂，则G₂：$\mathbb{Z}_{2}^{l \times n} \rightarrow \mathbb{Z}_{2}^{l \times n} \times \mathbb{Z}_{2}^{2 l}$.

3.   协议分析

3.1   安全性分析

异步攻击是阻断FIP_Auth协议的第2轮通信信息. 若攻击者多次阻断第2轮通信，则标签信息更新多次. 因为数据库预先存储了每个标签可能出现的信息，当FIP_Auth协议遭受异步攻击时，阅读器仍能对标签识别认证. 因此，FIP_Auth协议能抗异步攻击.

为了证明FIP_Auth协议具有前向隐私安全，首先证明关于伪随机数产生器G₁和G₂的一个结论：假设G=(G_L, G_R)：$\mathbb{Z}_{2}^{l \times n} \longrightarrow \mathbb{Z}_{2}^{l \times n+2 l}$，这里的G是伪随机数产生器G₂，G_L(·)代表G₂输出的左边部分，G_R(·)代表G₂输出的右边部分. 对于任意的$\boldsymbol{R} \in \mathbb{Z}_{2}^{l \times n}$，|G_L(R)=l×n，|G_R(R)=2l，则对于任意的$\boldsymbol{x} \in \mathbb{Z}_{2}^{2 l}$，有|G₁(x)|=L.

定理1  考察以下2个序列：

这里的$t_{i} \stackrel{\$}{\leftarrow} \mathbb{Z}_{2}^{L}$ (i=1, 2, …, n)，则D₀与D₁是计算不可区分的.

证明  假设D₀与D₁是计算可区分的，则可以构造一个算法B来区分伪随机数产生器G₁的输出分布与均匀分布. 令$y=(\boldsymbol{U}, \boldsymbol{v}) \in \mathbb{Z}_{2}^{l \times n+2 l}$，首先定义序列：

其中, $i=2, \cdots, n ; \boldsymbol{t}_{j} \in \mathbb{Z}_{2}^{L}\;(j=1, 2, \cdots, i-2)$. 然后, 定义以下序列：

假设算法π是能以ε的优势成功区分序列D₀和D₁的多项式时间算法, 构造算法π参与的统计测试实验Ep_πⁱ(y)(y=(U, v))：

(1) 按以上的定义构造Y_i；

(2)b←π(Y_i)；

(3) 输出b.

令p_i=Pr[Ep_πⁱ(y)=1]. 算法B的执行过程如下：(1)接收伪随机数产生器的实验中的安全测试值y=(U, v)；(2)随机选择一个i∈{2, …, n+2}，进行统计测试的实验Ep_πⁱ(y)；(3)计算输出结果为序列D₀的概率Pr[B(y)=1|y=G(R)]和序列D₁的概率Pr[B(y)=1|y=t].根据区分序列D₀与D₁的概率, 得到伪随机数产生器G₁的输出分布与随机分布是计算不可区分的.由于

所以，算法B区分序列D₀与D₁的概率为

则算法B区分伪随机数产生器G₁的输出分布与随机分布的概率至少为ε/(n+1).证毕.

定理2  若G₁和G₂是2个伪随机数产生器，则FIP_Auth协议具有前向隐私安全性.

证明  要证明FIP_Auth协议的前向隐私性，需要证明2个标签行为的不可区分性. 构造2个序列D₀与D₁:

其中，O表示输入为a、R和x且输出为$\boldsymbol{R}^{\mathrm{T}} \cdot \boldsymbol{x}_{\downarrow a} \oplus \boldsymbol{e}$的随机算法，这里e←Ber_τⁿ; $G_{\mathrm{L}}(\cdot) \in \mathbb{Z}_{2}^{l \times n}$、$G_{\mathrm{R}}(\cdot) \in \mathbb{Z}_{2}^{2 l}$分别表示伪随机数产生器G₂输出的左边部分、右边部分；R₁, $\boldsymbol{R}_{2} \in \mathbb{Z}_{2}^{l \times n}$；x₁, $\boldsymbol{x}_{2} \in \mathbb{Z}_{2}^{2 l}$；$\boldsymbol{b}_{i} \stackrel{\$}{\leftarrow} \boldsymbol{\Omega}$；R_i, $\boldsymbol{u}_{i} \stackrel{\$}{\longleftarrow} \mathbb{Z}_{2}^{n}$；t_i, $\boldsymbol{v}_{i} \stackrel{\$}{\longleftarrow} \mathbb{Z}_{2}^{k}$；δ、λ为自然数.

首先，证明序列D₀与D₁是计算不可区分的. 观察以下2个序列：

根据定理1可得D′₀与D′₁是计算不可区分的，证明方法与定理1类似，不再重复.

LPN假设指LPN输出结果$\boldsymbol{R}^{\mathrm{T}} \cdot \boldsymbol{x}_{\downarrow a} \oplus \boldsymbol{e}$的分布与均匀分布是计算不可区分的，则根据LPN假设可得序列

与

是计算不可区分的.

综上，由于D′₀与D′₁是计算不可区分的，D″₀与D″₁是计算不可区分的，所以D₀与D₁是计算不可区分的.

然后, 使用反证法证明FIP_Auth协议的前向隐私安全. 假设FIP_Auth协议不具有前向隐私性，则存在一个能够在多项式时间内以不可忽略的优势ε攻击FIP_Auth协议的前向隐私的攻击者A. 假设攻击者A一共调用了q次预言机，则可以构造一个多项式时间算法ω来区分序列D₀与D₁.

算法ω的执行过程如下：

接收到测试序列(c₁, z₁, w₁, c₂, z₂, w₂, …, c_δ+1, z_δ+1, w_δ+1, d₁, s₁, y₁, d₂, s₂, y₂, …, d_λ+1, s_λ+1, y_λ+1) 后，首先，初始化(n-2)个标签，使用测试序列模拟对标签T₁、T₂的查询. 同时，选择一个随机数β∈{0, 1}，令T_β=T₂，T_1-β=T₁；设置2个计数器k₁和k₂，初始值都设为1. 然后，分2个阶段执行. 在第一阶段，当攻击者A查询SendTag(sid, c_k1, T₁)时，返回z_k1，并设置计数器k₁=k₁+1；当攻击者A查询SendTag(sid, d_k2, T₂)时，返回s_k2，并设置计数器k₂=k₂+1. 在第二阶段，将T_β交给攻击者A，当攻击者A查询Reveal(T_β)时，直接返回d_λ+1, s_λ+1, y_λ+1. 攻击者A输出一个随机数β′，若β=β′，则算法ω输出0, 表示测试序列来自D₀；否则，输出1表示测试序列来自D₁.

接下来分析算法ω的成功优势，分2种情况讨论.

情况1：测试序列来自D₀. 因为算法ω模拟给攻击者A的环境与前向隐私游戏Game_A的攻击环境完全一致，攻击者A能以不可忽略的优势ε攻击FIP_Auth协议的前向隐私，所以算法ω能以不可忽略的优势ε区分序列D₀.

情况2：测试序列来自D₁. 因为D₁序列中的各个元素是相互独立和随机的，攻击者A只得到d_λ+1、s_λ+1、y_λ+1，则无法获得c_i、z_i、w_i、d_i、s_i、y_i的任何有效信息，所以，攻击者A区分标签T₁和T₂的优势是可以忽略不计的.

综上，算法ω区分序列D₀和D₁的优势是不可忽略不计的，与序列本身的计算不可区分相互矛盾，因此，FIP_Auth协议具有前向隐私安全.

定理3  在LPN假设成立的前提条件下，FIP_Auth协议具有主动安全性.

FIP_Auth协议中包含识别部分与认证部分. 认证部分的设计与Auth协议是一致的；识别部分使用了伪随机数产生器G₁和G₂，利用伪随机数产生器G₁的输出作为构建数据库的索引，G₂用来更新标签的密钥信息(R, x).因此，对于FIP_Auth协议的主动安全证明与Auth协议的主动安全证明^[5]是一致的，这里不再重复.

3.2   参数分析

对于FIP_Auth协议在参数的选择上，参数l, $n \in \mathbb{N}$是FIP_Auth协议中标签T_i存储的密钥信息(R_i, x_i)的安全参数，$\boldsymbol{R}_{i} \in \mathbb{Z}_{2}^{l \times n}$，$\boldsymbol{x}_{i} \in \mathbb{Z}_{2}^{2 l}$.τ∈[0, 1/2]是贝努利分布Ber_τ的参数，阅读器验证的阈值τ'∈[nτ, n/2]. 根据Auth协议和Auth^#协议的参数选择，可以适当地选择FIP_Auth协议的相关参数. 设P_FR表示错误拒绝水平，即合法标签被阅读器拒绝的可能性：

P_FA表示错误接受水平，即非法标签被阅读器接受的水平：

由式(1)和式(2)可知，P_FR、P_FA均与密钥参数l的选择无关. 在HB协议与HB⁺协议中，式中的n为协议进行的轮数q.

由文献[3]知，协议每轮通信的安全水平至少为80 bit. FIP_Auth协议中第一轮的通信量最小，长度为2l，所以可以选取l=80, 以保证通信安全. 在贝努利参数τ为0.25和0.125的情况下，Auth协议和Auth^#协议对安全参数l、n分别选取l=80、n=1 164和l=80、n=441. 选取FIP_Auth的参数(表 1)如下:

表  1  FIP_Auth协议的参数集

Table  1.  The parameter sets of the FIP_Auth protocol

参数集	l	n	τ	τ'	PFR	PFA
1	80	1 164	0.250	405	2-45	2-83
2	80	441	0.125	113	2-45	2-83

下载: 导出CSV 

| 显示表格

(1) 参数集1：当协议的安全水平为l=80, n=1 164时，贝努利参数τ为0.25，则阅读器验证的阈值τ′的取值范围为[0.25n, n/2]，从而适当地选取τ'，计算P_FR和P_FA.

(2) 参数集2：当协议的安全水平为l=80, n=441时，贝努利参数τ为0.125，则阅读器验证的阈值τ'的取值范围为[0.125n, n/2]，从而适当地选取τ'，计算P_FR和P_FA.

3.3   4个协议的对比分析

本节主要将FIP_Auth协议与Tree-LSHB+、BAJR、MMR协议的隐私性、安全性、轮数、通信复杂度、标签计算复杂度和密钥大小进行对比.

由结果(表 2)可知：(1)虽然4个协议均考虑了隐私性，但只有FIP_Auth协议与BAJR协议具备隐私性.(2)虽然BAJR协议达到一般中间人安全，而FIP_Auth协议只达到主动安全，但是FIP_Auth协议的通信轮数只需2轮且通信量更低. 而且，BAJR协议执行时，标签需要计算3次哈希函数，使得无法实现标签的低成本且计算复杂度高；FIP_Auth协议执行时，标签只进行异或计算，计算复杂度低且实现了标签低成本.

表  2  4个RFID认证协议的效率与安全比较

Table  2.  The comparison of efficiency and security of 4 RFID authentication protocols

协议	隐私性	安全性	轮数	密钥大小	识别时间	通信量	计算复杂度
Tree-LSHB+	不具备	抗主动攻击	3	2l	O(log NT)	(l×n+n)d+2(l×n)+2n	O(l)
BAJR	具备	抗一般中间人攻击	3	l	O(1)	l+5h(·)	3Thash
MMR	不具备	抗一般中间人攻击	3	l×n	O(1)	4l+l2+3n	O(l)
FIP_Auth	具备	抗主动攻击	2	2l	O(1)	2l+n+L	O(l)
注：Thash是BAJR协议中标签计算1次哈希函数所需要的时间，h(·)表示哈希函数运算输出的长度.

下载: 导出CSV 

| 显示表格

4.   结束语

本文在Auth协议的基础上，借鉴SFP通用构造协议的设计方法，利用基于LPN设计的伪随机数产生器以及RFID系统中原有的大型存储设备数据库，设计具有快速识别的隐私保护认证协议(FIP_Auth). 与Tree-LSHB+、BAJR、MMR协议相比，FIP_Auth协议具有较小的密钥存储、较低的通信量，最重要的是标签的识别速度达到了O(1)，并且保证了协议的隐私安全.

但是，FIP_Auth协议只达到了抗主动攻击，不能抵抗一般中间人攻击. 设计具有与FIP_Auth协议一样的优势并且能抗一般中间人攻击的协议是下一步的研究重点.