Untraceable RFID tags via insubvertible encryption

ABSTRACT

We introduce a new cryptographic primitive, called insubvertible encryption, that produces ciphertexts which can be randomized without the need of any key material. Unlike plain universal re-encryption schemes, insubvertible encryption prevents against adversarial exploitation of hidden channels, by including certificates proving that the ciphertext can only be decrypted by authorized parties.The scheme can be applied to RFID tags, providing strong protection against tracing. This enables post-sale applications of manufacturer-issued RFID tags while preserving the privacy of consumers. The functionality required of the RFID tags is minimal, namely that they be re-writable (many-writable). No cryptographic capabilities are required of the tags themselves, as the readers perform all necessary computations.

REFERENCES

• 1: G. Avoine. Privacy issues in RFID banknote protection schemes. In The Sixth International Conference on Smart Card Research and Advanced Applications -- CARDIS, pp. 33--48, 2004. IFIP, Kluwer Academic Publishers.
• 2: G. Avoine. Security and privacy in rfid systems. http://lasecwww.epfl.ch/~gavoine/rfid/, Last Access: May 2005.
• 3: G. Avoine and P. Oechslin. RFID traceability: A multilayer problem. In Financial Cryptography -- FC'05, LNCS of Springer-Verlag. 2005.
• 4: L. Ballard, M. Green, B. de Medeiros, and F. Monrose. Correlation-resistant storage. Johns Hopkins University, Computer Science Department Technical Report # TR-SP-BGMM-050705, http://spar.isi.jhu.edu/~mgreen/correlation.pdf, 2005.
• 5: P. S. L. M. Barreto, B. Lynn, and M. Scott. Constructing elliptic curves with prescribed embedding degrees. In Proc. of Security in Communication Networks (SCN'02), number 2576 in LNCS, pp. 263--273. Springer-Verlag, 2002.
• 6: P. S. L. M. Barreto and M. Naehrig. Pairing-friendly elliptic curves of prime order. Technical Report 2005/133, International Association for Cryptologic Research, 2005.
• 7: Mihir Bellare , Alexandra Boldyreva , Anand Desai , David Pointcheval, Key-Privacy in Public-Key Encryption, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.566-582, December 09-13, 2001
• 8: D. Boneh, X. Boyean, and H. Shacham. Short group signatures. In Advances in Cryptology -- CRYPTO '04, vol. 3152 of LNCS, pp. 41--55, 2004. Full version available at http://crypto.stanford.edu/~dabo/papers/groupsigs.pdf.
• 9: Dan Boneh , Matthew Franklin, Identity-Based Encryption from the Weil Pairing, SIAM Journal on Computing, v.32 n.3, p.586-615, 2003 [doi>10.1137/S0097539701398521]
• 10: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Journal of Cryptology, v.17 n.4, p.297-319, September 2004 [doi>10.1007/s00145-004-0314-9]
• 11: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 12: J. Camenisch and A. Lysyanskaya. Signature Schemes and Anonymous Credentials from Bilinear Maps. In Advances in Cryptology --- CRYPTO 2004. Springer Verlag, 2004.
• 13: R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. Technical Report 2000/067, Cryptology ePrint Archive, International Association for Cryptology, http://eprint.iacr.org/2000/067, 2000.
• 14: R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001
• 15: Steven D. Galbraith , Keith Harrison , David Soldera, Implementing the Tate Pairing, Proceedings of the 5th International Symposium on Algorithmic Number Theory, p.324-337, July 07-12, 2002
• 16: S. D. Galbraith and V. Rotger. Easy decision Diffie-Hellman groups. Journal of Computation and Mathematics, 7:201--218, 2004.
• 17: P. Golle, M. Jakobsson, A. Juels, and P. Syverson. Universal re-encryption for mixnets. In Proc. of the 2004 RSA Conference, 2004.
• 18: Dirk Henrici , Paul Müller, Hash-based Enhancement of Location Privacy for Radio-Frequency Identification Devices using Varying Identifiers, Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications Workshops, p.149, March 14-17, 2004
• 19: Antoine Joux, A One Round Protocol for Tripartite Diffie-Hellman, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.385-394, July 02-07, 2000
• 20: A. Juels and R. Pappu. Squealing euros: Privacy protection in RFID-enabled banknotes. In Financial Cryptography -- FC'03, vol. 2742 of LNCS, pp. 103--121, Springer-Verlag, 2003.
• 21: Ari Juels , Ronald L. Rivest , Michael Szydlo, The blocker tag: selective blocking of RFID tags for consumer privacy, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948126]
• 22: Anna Lysyanskaya , Ronald L. Rivest , Amit Sahai , Stefan Wolf, Pseudonym Systems, Proceedings of the 6th Annual International Workshop on Selected Areas in Cryptography, p.184-199, August 09-10, 1999
• 23: A. Miyaji, M. Nakabayashi, and S. Takano. New explicit conditions of elliptic curves for FR-reduction. IEICE Transactions on Fundamentals, E84-A(5):1234--1243, 2001.
• 24: David Molnar , David Wagner, Privacy and security in library RFID: issues, practices, and architectures, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030112]
• 25: V. I. Nechaev. Complexity of a determinate algorithm for the discrete logarithm. Mathematical Notes, 55:165--172, 1994.
• 26: D. Page, N. Smart, and F. Vercauteren. A comparison of MNT curves and supersingular curves. Cryptology ePrint Archive: Report 2004/165, 2004. http://eprint.iacr.org/2004/165/.
• 27: Birgit Pfitzmann , Michael Waidner, Composition and integrity preservation of secure reactive systems, Proceedings of the 7th ACM conference on Computer and communications security, p.245-254, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352639]
• 28: J. Saito, J.-C. Ryou, and K. Sakurai. Enhancing privacy of universal re-encryption scheme for RFID tags. In Embedded and Ubiquitous Computing -- EUC 2004, vol. 3207 of LNCS, pp. 879--890, Springer-Verlag, 2004.
• 29: M. Scott. MIRACL library. Indigo Software. http://indigo.ie/~scott/#download.
• 30: M. Scott. Authenticated ID-based key exchange and remote log-in with simple token and PIN number. Technical Report 2002/164, International Association for Cryptologic Research, 2002.
• 31: V. Shoup. Lower bounds for discrete logarithms and related problems. In Advances in Cryptology: Proceedings of Eurocrypt'97, LNCS, pp. 256--266. Springer-Verlag, 1997. Revised version: http://www.shoup.net/papers/.
• 32: S. Spiekermann and O. Berthold. Maintaining privacy in RFID enabled environments -- proposal for a disable-model. In The First Workshop on Security and Privacy, Conference on Pervasive Computing, Vienna, Austria, April 2004.
• 33: Eric R. Verheul, Evidence that XTR Is More Secure than Supersingular Elliptic Curve Cryptosystems, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.195-210, May 06-10, 2001
• 34: Eric R. Verheul, Evidence that XTR Is More Secure than Supersingular Elliptic Curve Cryptosystems, Journal of Cryptology, v.17 n.4, p.277-296, September 2004 [doi>10.1007/s00145-004-0313-x]
• 35: S. Weis, S. Sarma, R. Rivest, and D. Engels. Security and privacy aspects of low-cost radio frequency identification systems. In International Conference on Security in Pervasive Computing -- SPC 2003, vol. 2802 of LNCS, pp. 454--469, Springer-Verlag, 2003.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Security

Keywords:
RFID privacy, bilinear maps, universal re-encryption