郑娜娜， 马昌社

(华南师范大学计算机学院， 广州 510631)

无线射频识别(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)在无线信道中需要进行大量的通信；……