Untraceable Tags based on Mild Assumptions

Carlo Blundo, Angelo De Caro, Giuseppe PersianoIACR ePrint 2009 · DOI

TL;DR

This paper introduces a novel construction for untraceable RFID tags that offers strong privacy guarantees even when adversaries can tamper with tags. Their approach is based on a new, "mild" cryptographic assumption, making it more practical and secure than previous methods.

What Problem Does This Paper Address?

Radio Frequency Identification (RFID) technology is becoming ubiquitous for inventory management and supply chains. However, a significant privacy concern arises from the potential for RFID tags to be traced, thereby revealing information about the objects they are attached to and their owners. While encryption can protect stored data, it doesn't inherently prevent tracing. Existing solutions often rely on strong assumptions or are vulnerable to adversaries who can modify tag data. This paper tackles the challenge of creating RFID tags that are untraceable, even in scenarios where an adversary can write to the tag, while using minimal and "mild" cryptographic assumptions.

Methods

The authors propose a new construction for untraceable RFID tags based on a symmetric bilinear setting. Their approach involves a system of algorithms:

  • GenPub: Generates public information, re-randomizing information, and a master secret key.
  • GenKey: Generates public and secret keys for individual users.
  • rEnc: Encrypts messages for storage on a tag, producing a ciphertext.
  • rDec: Decrypts ciphertexts.
  • Randomize: This is a crucial component. It takes a ciphertext and re-randomizes it, producing a new ciphertext that decrypts to the same message but is computationally indistinguishable from a fresh encryption. This process can be performed without knowing the decryption key.

The core of their construction relies on a new cryptographic assumption that is "tautological in the generic group model" and "efficiently falsifiable." This assumption is weaker and more practical than those used in prior work. They also introduce formal definitions for "weak untraceability" (protecting against read-only adversaries) and "strong untraceability" (protecting against adversaries who can also write to tags).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Mild Assumptions for Strong Security: The paper demonstrates that strong untraceability can be achieved with relatively mild cryptographic assumptions, making the system more practical and less reliant on complex or potentially insecure underlying primitives.
  • Re-randomization as a Privacy Primitive: The Randomize procedure is central to achieving untraceability. By re-randomizing ciphertexts, the system obscures the history of a tag's interactions, making it difficult to link different readings together.
  • Distinction Between Weak and Strong Untraceability: The authors clearly define and formalize the difference between protection against passive readers (weak untraceability) and active attackers who can modify tag data (strong untraceability), highlighting the increased challenge of the latter.
  • Symmetric Bilinear Setting: Their construction operates in the symmetric bilinear setting, which is more restrictive and thus more challenging than the asymmetric setting used in some previous works, making their achievement more significant.

Key Results

The paper presents a construction for an untraceable tag system that is:

  • Semantically Secure: Guarantees that an adversary cannot distinguish between encryptions of two different messages.
  • Weakly Untraceable: Protects against adversaries who can only read tags.
  • Strongly Untraceable: Protects against adversaries who can read and write to tags.

The paper also includes experimental results (Table 1 and Table 2) comparing their "Weak" and "Strong" schemes against a prior "InsEnc" scheme. Key findings from the experiments include:

  • Performance: The "Strong" scheme offers competitive performance, with randomization being significantly faster than the "InsEnc" scheme.
  • Size: Their schemes generate slightly larger encrypted messages compared to the "InsEnc" scheme, but this is deemed acceptable given the memory capacity of modern RFID tags.

Limitations and Future Work

  • Strong Untraceability Guarantee: The paper notes that their "Strong" scheme is only weakly untraceable against randomizers. They suggest that a construction guaranteeing untraceability against randomizers, based on mild assumptions, would be a valuable future direction.
  • Randomizer Trust: While their construction aims to be robust, the underlying security of the system still relies on the assumption that randomizers are not malicious.
  • General Construction: The authors mention that their construction of STag is a special case of a more general construction that starts from a randomizable anonymous identity-based encryption scheme. They note that such schemes were not known prior to their work, implying that further research into these underlying primitives could lead to even more advanced tag systems.

Summary updated

BibTeX
@article{blundo2009untraceable,
  author = {Carlo Blundo and Angelo De Caro and Giuseppe Persiano},
  title = {{Untraceable Tags based on Mild Assumptions}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2009},
  doi = {10.1007/978-3-642-11207-2\_14},
}
Figure