Biblio

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.

Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn any linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic circuits, analogously to the role of oblivious transfer (OT) for boolean circuits. A useful extension of OLE is vector OLE (VOLE), allowing the receiver to learn any linear combination of two vectors held by the sender. In several applications of OLE, one can replace a large number of instances of OLE by a smaller number of instances of VOLE. This motivates the goal of amortizing the cost of generating long instances of VOLE. We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency. Our VOLE generators can be used to enhance the efficiency of a host of cryptographic applications. These include secure arithmetic computation and non-interactive zero-knowledge proofs with reusable preprocessing. Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable. Their security can be based on variants of the learning parity with noise (LPN) assumption over large fields that resist known attacks. We provide several constructions that offer tradeoffs between different efficiency measures and the underlying intractability assumptions.