Lightweight Grouping-Proof for Post-Quantum RFID Security

A grouping-proof protocol aims to generate an evidence that two or more RFID (Radio Frequency Identification) tags in a group are coexistent, which has been widely deployed in practical scenarios, such as healthcare, supply-chain management, and so on. However, existing grouping-proof protocols have many issues in security and efficiency, either incompatible with EPCglobal Class-1 Generation-2 (C1G2) standard, or vulnerable to different attacks. In this paper, we propose a lightweight grouping-proof protocol which only utilizes bitwise operations (AND, XOR) and 128-bit pseudorandom number generator (PRNG). 2-round interactions between the reader and the tags allow them to cooperate on fast authentication in parallel mode where the reader broadcasts its round messages rather than hang on for the prior tag and then fabricate apposite output for the next tag consecutively. Our design enables the reader to aggregate the first round proofs (to bind the membership of tags in the same group) generated by the tags to an authenticator of constant size (independent of the number of tags) that can then be used by the tags to generate the second round proofs (and that will be validated by the verifier). Formal security (i.e., PPT adversary cannot counterfeit valid grouping-proof that can be accepted by any verifier) of the proposed protocol relies on the hardness of the learning parity with noise (LPN) problem, which can resist against quantum computing attacks. Other appealing features (e.g., robustness, anonymity, etc.) are also inspected. Performance evaluation shows its applicability to C1G2 RFID.