Concrete Security for Entity Recognition: The Jane Doe Protocol (Full Paper)

Entity recognition does not ask whether the message is from some entity X, just whether a message is from the same entity as a previous message. This turns out to be very useful for low-end devices. Motivated by an attack against a protocol presented at SAC 2003, the current paper proposes a new protocol -the "Jane Doe Protocol" - and provides a formal proof of its concrete security. The protocol neither employs asymmetric cryptography, nor a trusted third party, nor any key pre-distribution. It is suitable for light-weight cryptographic devices such as sensor network motes and RFID tags.