A Provably Secure and Unlinkable Authentication System with Smart Cards

This paper proposes an identification scheme realizing an authentication system with smart cards. The proposed scheme satisfies the following properties simultaneously: security, unlinkability in multi-service environment and memory efficiency, although a system which satisfies only two of these properties can be constructed with trivial extensions of existing systems. However, to the best of our knowledge, there has not existed a system that satisfies all of these properties. Unlinkability in multi-service environment is a property of privacy protection such that user’s actions or preferences are not linked by the adversary by analyzing logs from distinct service providers. We first present an identification scheme for multi-service environment, which utilizes pseudorandom functions. We then give a formal definition of unlinkability in multi-service environment, and prove that our scheme is secure, unlinkable and memory efficient.