Efficient zero-knowledge identification schemes which respect privacy

ABSTRACT

At first glance, privacy and zero-knowledgeness seem to be similar properties. A scheme is private when no information is revealed on the prover and in a zero-knowledge scheme, communications should not leak provers' secrets.

Until recently, privacy threats were only partially formalized and some zero-knowledge (ZK) schemes have been proposed so far to ensure privacy. We here explain why the intended goal is not reached. Following the privacy model proposed by Vaudenay at Asiacrypt 2007, we reconsider the analysis of these schemes. We firstly propose a framework which enables to transform some generic ZK scheme into private scheme. We then apply as a relevant example this framework to the GPS scheme. This leads to efficient implementations of zero-knowledge identification schemes which respect privacy. Their security and their privacy are based on the problem of the Short Exponent Decisional Diffie-Hellman problem.

REFERENCES

• 1: G. Avoine, E. Dysli, and P. Oechslin. Reducing time complexity in RFID systems. In SAC, pages 291--306. Springer, 2005.
• 2: L. Batina, N. Mentens, K. Sakiyama, B. Preneel, and I. Verbauwhede. Low-cost elliptic curve cryptography for wireless sensor networks. In ESAS, pages 6--17. Springer, 2006.
• 3: Mihir Bellare , Adriana Palacio, GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.162-177, August 18-22, 2002
• 4: U. Feige , A. Fiat , A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, v.1 n.2, p.77-94, Aug. 1988 [doi>10.1007/BF02351717]
• 5: M. Feldhofer, S. Dominikus, and J. Wolkerstorfer. Strong authentication for RFID systems using the AES algorithm. In CHES, pages 357--370. Springer, 2004.
• 6: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 7: T. E. Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In IEEE Transactions on Information Theory, volume 31, pages 469--472, 1985.
• 8: Marc Girault, An identity-based identification scheme based on discrete logarithms modulo a composite number, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.481-486, February 1991, Aarhus, Denmark
• 9: M. Girault, G. Poupard, and J. Stern. On the fly authentication and signature schemes based on groups of unknown order. J. Cryptology, 19(4):463--487, 2006.
• 10: S. Goldwasser and S. Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270--299, 1984.
• 11: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 12: Louis C. Guillou , Jean-Jacques Quisquater, A "Paradoxical" Indentity-Based Signature Scheme Resulting from Zero-Knowledge, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.216-231, August 21-25, 1988
• 13: I. S. ISO/IEC. ISO 14443--3: Identification cards -- Contactless Integrated Circuit(s) Cards -- Proximity Cards. Part 3: Initialization and Anticollision. ISO, 2001.
• 14: Markus Jakobsson , David Pointcheval, Mutual Authentication for Low-Power Mobile Devices, Proceedings of the 5th International Conference on Financial Cryptography, p.178-195, February 19-22, 2002
• 15: M. Jakobsson and D. Pointcheval. Mutual authentication for low-power mobile devices. http://www.informatics.indiana.edu/markus/papers/mutual.pdf, 2001.
• 16: M. Jakobsson, K. Sako, and R. Impagliazzo. Designated verifier proofs and their applications. In EUROCRYPT, pages 143--154, 1996.
• 17: A. Juels and S. A. Weis. Authenticating pervasive devices with human protocols. In CRYPTO, pages 293--308. Springer, 2005.
• 18: Ari Juels , Stephen A. Weis, Defining Strong Privacy for RFID, Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications Workshops, p.342-347, March 19-23, 2007 [doi>10.1109/PERCOMW.2007.37]
• 19: T. Koshiba and K. Kurosawa. Short exponent Diffie-Hellman problems. In PKC, pages 173--186. Springer, 2004.
• 20: F. Laguillaumie and D. Vergnaud. Designated verifier signatures: Anonymity and efficient construction from any bilinear map. In SCN, pages 105--119. Springer, 2004.
• 21: Tri Van Le , Mike Burmester , Breno de Medeiros, Universally composable and forward-secure RFID authentication and authenticated key exchange, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore [doi>10.1145/1229285.1229319]
• 22: H. Lipmaa, G. Wang, and F. Bao. Designated verifier signature schemes: Attacks, new security notions and a new construction. In ICALP, pages 459--471. Springer, 2005.
• 23: Machine Readable Travel Documents. Development of a logical data structure -- LDS for optional capacity expansion technologies. Version 1.7. International Civil Aviation Organization., 2004.
• 24: Machine Readable Travel Documents. PKI for machine readable travel documents offering ICC read-only access. Version 1.1. International Civil Aviation Organization., 2004.
• 25: M. McLoone and M. J. B. Robshaw. Public key cryptography and RFID tags. In CT-RSA, pages 372--384, 2007.
• 26: Silvio Micali , Adi Shamir, An Improvement of the Fiat-Shamir Identification and Signature Scheme, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.244-247, August 21-25, 1988
• 27: 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]
• 28: J. Monnerat, S. Vaudenay, and M. Vuagnoux. About machine-readable travel documents. RFID Security, 2007.
• 29: Miyako Ohkubo , Koutarou Suzuki , Shingo Kinoshita, RFID privacy issues and technical challenges, Communications of the ACM, v.48 n.9, September 2005 [doi>10.1145/1081992.1082022]
• 30: Tatsuaki Okamoto, Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.31-53, August 16-20, 1992
• 31: H. Ong , C. P. Schnorr, Fast signature generation with a Fiat Shamir—like scheme, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.432-440, February 1991, Aarhus, Denmark
• 32: D. Pointcheval. A new identification scheme based on the perceptrons problem. In EUROCRYPT, pages 319--328, 1995.
• 33: J.-J. Quisquater and L. Guillou. The new Guillou-Quisquater Scheme. In Proceedings of the RSA 2000 conference, 2000.
• 34: R. L. Rivest. On the notion of pseudo-free groups. In TCC, pages 505--521. Springer, 2004.
• 35: S. Saeednia, S. Kremer, and O. Markowitch. An efficient strong designated verifier signature scheme. In ICISC, pages 40--54. Springer, 2003.
• 36: Claus-Peter Schnorr, Efficient Identification and Signatures for Smart Cards, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.239-252, August 20-24, 1989
• 37: Adi Shamir, An Efficient Identification Scheme Based on Permuted Kernels (Extended Abstract), Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.606-609, August 20-24, 1989
• 38: R. Steinfeld, L. Bull, H. Wang, and J. Pieprzyk. Universal designated-verifier signatures. In ASIACRYPT, pages 523--542. Springer, 2003.
• 39: Jacques Stern, An alternative to the Fiat-Shamir protocol, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.173-180, November 1990, Houthalen, Belgium
• 40: Jacques Stern, A new identification scheme based on syndrome decoding, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.13-21, January 1994, Santa Barbara, California, United States
• 41: Jacques Stern, Designing Identification Schemes with Keys of Short Size, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.164-173, August 21-25, 1994
• 42: P. C. van Oorschot and M. J. Wiener. On Diffie-Hellman key agreement with short exponents. In EUROCRYPT, pages 332--343, 1996.
• 43: S. Vaudenay. On privacy models for RFID. In ASIACRYPT, pages 68--87, 2007.
• 44: P. Véron. Improved identification schemes based on error-correcting codes. 8(1):57--69, 1996.
• 45: S. A. Weis, S. E. Sarma, R. L. Rivest, and D. W. Engels. Security and privacy aspects of low-cost radio frequency identification systems. In Security in Pervasive Computing, pages 201--212. Springer, 2003.
• 46: Duncan S. Wong , Agnes Hui Chan, Efficient and Mutually Authenticated Key Exchange for Low Power Computing Devices, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.272-289, December 09-13, 2001
• 47: D. S. Wong and A. H. Chan. Efficient and mutually authenticated key exchange for low power computing devices. http://www.cs.cityu.edu.hk/~duncan/papers/01wongetal_csake.ps, 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional 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:
Security

Keywords:
identification, privacy, zero-knowledge