A Provably Secure and Unlinkable Authentication System with Smart Cards
Toru Nakamura, Shunsuke Inenaga, Daisuke Ikeda, Kensuke Baba, Hiroto Yasuura · Kyushu University Institutional Repository (QIR) (Kyushu University) · 2008
Abstract. This paper proposes an identification scheme realizing an authentica-tion system with smart cards. The proposed scheme satisfies the following prop-erties simultaneously: security, unlinkability in multi-service environment and memory efficiency, although a system which satisfies only two of these prop-erties 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 pseudoran-dom functions. We then give a formal definition of unlinkability in multi-service environment, and prove that our scheme is secure, unlinkable and memory effi-cient. Key words: identification, authentication, unlinkability, smart card 1