  Radio Frequency Identification (RFID) is a key technology used in many
applications. In the past decades, plenty of secure and privacy-preserving RFID
tag/mutual authentication protocols as well as formal frameworks for evaluating
them have been proposed. However, we notice that a property, namely proof of
possession (PoP), has not been rigorously studied till now, despite it has
significant value in many RFID applications. For example, in RFID-enabled
supply chains, PoP helps prevent dis-honest parties from publishing information
about products/tags that they actually have never processed.
  We propose the first formal framework for RFID tag/mutual authentication with
PoP after correcting deficiencies of some existing RFID formal frameworks. We
provide a generic construction to transform an RFID tag/mutual authentication
protocol to one that supports PoP using a cryptographic hash function, a
pseudorandom function (PRF) and a signature scheme. We prove that the
constructed protocol is secure and privacy-preserving under our framework if
all the building blocks possess desired security properties. Finally, we show
an RFID mutual authentication protocol with PoP. Arming tag/mutual
authentication protocols with PoP is an important step to strengthen
RFID-enabled systems as it bridges the security gap between physical layer and
data layer, and reduces the misuses of RFID-related data.
