Abstract: We revisit a public key scheme presented by Shamir in 1994 (and
simultaneously by Naccache in 1992) and examine its applicability for general-purpose
RFID tags in the supply chain. Using a combination of new and established spacesaving
methods, we present a full-edged public key identification scheme, which is secure
yet highly efficient. The 1024-bit scheme fits completely (including RAM) into 4682
gate equivalents and has a mean current consumption of
14.2 uA. The main novelty in our implementation is the replacement of the long pseudo-random
sequence, originally stored on 260 bytes of EEPROM, by a reversible stream cipher
using less than 300 bits of RAM. We show how our scheme offers tag-to-reader and
reader-to-tag authentication and how it can be fit into the existing RFID supply
chain infrastructure.