Radio Frequency IDentifiers (RFID) are low-cost pervasive devices used in various settings for identification purposes: although they have originally been introduced to ease the supply chain management, they are already used in many other applications. Some of these applications need secure identification and ad-hoc authentication protocols have to be designed for that purpose. But the intrusion of RFID in the life of end-users might additionally require a higher level of user-privacy. Such security and privacy requirements conflict with the highly constrained environment of RFID systems. Ohkubo, Suzuki, and Kinoshita first proposed an appealing RFID protocol that meets the highest privacy requirements. However, their scheme and its known variants suffer from limitations in terms of computational complexity and provable security which this paper aims to address. We propose a novel forward private authentication scheme built upon less computationally expensive cryptographic ingredients, namely pseudo-random generators and universal hash functions instead of one way hash functions. In contrast with existing schemes, we provide security proofs of our construction in the standard model instead of the random oracle model.

QUAD [1] is a stream cipher whose provable security relies on the hardness of solving systems of multivariate quadratic equations. This paper explores FPGA implementations of this stream cipher and, more specifically, small area ones. The smallest of our implementations of QUAD requires only 85 slices (2961 GE) on a Virtex 4 Xilinx FPGA, which makes it not only the smallest provably secure stream cipher, but also a very good competitor among conventional stream ciphers: this implementation of QUAD's underlying PRNG results in a 68% improvement over the smallest known AES implementation on FPGA [4].