An Identifiable Yet Unlinkable Authentication Systemwith Smart Cards for Multiple Services
Toru Nakamura1 , Shunsuke Inenaga1 , Daisuke Ikeda1 ,Kensuke Baba2 , and Hiroto Yasuura1
1

Graduate School/Faculty of Information Science and Electrical Engineering,
Kyushu University
Moto’oka 744, Nishi-ku, Fukuoka, 819-0395, Japan{toru, inenaga, yasuura}@c.csce.kyushu-u.ac.jp
daisuke@inf.kyushu-u.ac.jp
2
Research and Development Division, Kyushu University Library
10-1, Hakozaki 6, Higashi-ku, Fukuoka, 812-8581, Japanbaba@lib.kyushu-u.ac.jp

Abstract. The purpose of this paper is to realize an authentication system which
satisfies four requirements for security, privacy protection, and usability, that is,impersonation resistance against insiders, personalization, unlinkability in multiservice environment, and memory efficiency. The proposed system is the first system which satisfies all the properties. In the proposed system, transactions of auser within a single service can be linked (personalization), while transactions ofa user among distinct services can not be linked (unlinkability in multi-service environment). The proposed system can be used with smart cards since the amountof memory required by the system does not depend on the number of services.
First, this paper formalizes the property of unlinkability in multi-service environment, which has not been formalized in the literatures. Next, this paper extends
an identification scheme with a pseudorandom function in order to realize an authentication system which satisfies all the requirements. This extension can bedone with any identification scheme and any pseudorandom function. Finally,
this paper shows an implementation with the Schnorr identification scheme and acollision-free hash function as an example of the proposed systems.

1 Introduction
With the increase of the number of services which a user would like to use, it is becoming more and more tedious for the user to establish and manage pairs of a username (pseudonym) and a password of multiple services. Hence much attention is recently paid to authentication systems which enable users to use multiple services after
they register at a registration manager only once. For example, single-sign-on systems,
such as Shibboleth [2], OpenID [1], and so on, have been popular. In this paper, such asystem is called an authentication system in multi-service environment.
The multi-service environment raises a new problem on privacy of users, that is, thedaily activity of a user can be revealed from information in multiple service providers.
Service providers usually maintain service logs of the transactions for the purpose ofthe detection of abuse, audit, and diagnosis of problems, and they can collect their log
files and trace actions of a user from his/her transactions. This can be done if the same
pseudonym is associated with the same user and is used for multiple service providers.
In fact, a typical single-sign-on system is based on such an implementation, hence much
more information in various service providers can be collected due to leakages of theservice logs or illegal coalitions among multiple service providers. In order to solve theproblem, authentication systems should have the property that it is difficult to determine
whether multiple transactions in distinct service providers are related to the same user ornot (unlinkability in multi-service environment). There are some authentication systems
which satisfy unlinkability in multi-service environment, such as Janus [6], anonymous
credentials [4], and authentication systems based on group signatures [5].
Authentication systems which satisfy unlinkability in multi-service environment
can be classified according to the degree of unlinkability as follows.
– Transactions of a user can be linked within a service, while transactions of a useramong distinct services. can not be linked.
– Transactions of a user can not be linked even within a service.
From the viewpoint of privacy protection, the systems with the latter property are superior to those with the former property. However, on the practical side, the systems
with the latter property have some disadvantages. Indeed, without identification of eachuser, the purpose of service logs previously described cannot be achieved. Therefore,
the system with the latter property cannot be applied to “personalized services”, whichcustomize and provide the contents according to a user’s profile and preference. Examples of personalized services are personalized news and recommendation services.
In the systems with the former property, service providers can identify each user (Personalizasion), hence they can maintain the service logs of their users and personalized
service can be treated. In this paper, we focus on the systems with the former property.
Next, we consider how to maintain pairs of a pseudonym and a password. There
are two ways on how to maintain pairs, that is, (1) doing by himself and (2) delegating
the maintenance of the pairs to a trusted third party, such as a registration manager.
We focus on the case (1) in this paper. In the case (1), some trusted devices, such as
PCs and smart cards, are usually used for storing the pairs. A straightforward solutionthat satisfies both unlinkability in multi-service environment and personalization is thateach user stores the table of the pairs of a pseudonym and a password for all service
providers. In this solution, the amount of memory required by the system is proportional
to the number of service providers. This solution would be efficient for systems with
PCs as they have enough amount of memory. However, in this paper we are interested
in situations where the portability of device of a user is indispensable, such as the use of
ATM machines. Hence we consider a smart card as a device of a user. Notice that, sincesmart cards have much less memory than PCs, the above straightforward solution is
unsuitable for smart cards when the number of service providers is considerably large.
Therefore, it is important for any authentication system with smart cards to requireas little amount of memory as possible in order to store pseudonyms and passwords(Memory efficiency)
The requirements for an authentication system considered in this paper are the following:– Personalization: service providers can identify each user.
– Unlinkability in multi-service environment: it is difficult to determine whether two
transactions among distinct service providers are the same user’s or not.
– Memory efficiency: the amount of memory for pseudonyms and passwords does notdepend on the number of service providers.
– Impersonation resistance against insiders: even if an adversary is a service provider,
the adversary cannot impersonate a legitimate user.
In practical systems, the entities who try to impersonate a legitimate user are not only
eavesdroppers but also malicious service providers. Therefore, authentication systems
should have the property that an adversary cannot impersonate a legitimate user even if
the adversary is a service provider.
We propose the first authentication system which satisfies all the requirements previously described. We note that there is no authentication system satisfies all of therequirements as far as we know. We show an extension of an identification scheme [7],which includes a key generating algorithm and an identification protocol, and the purpose of the extension is to realize the authentication system. The overview of our extended identification protocol is as follows:– First, a user generates a pair of a pseudonym and a secret-key for each service
provider from the corresponding service ID with pseudorandom functions [8].
– Next, the user and the service provider follow an identification protocol.
In order to evaluate our extended identification scheme, we define the above requirements based on the computational theory and we prove that our extended identification
scheme satisfies all the requirements. To our knowledge, the definition of unlinkability
in multi-service environment has not been formalized based on the computational theory, hence we show the first formalization of unlinkability in multi-service environment.
The definition of impersonation resistance in this paper is based on the formalization of
security of identification schemes in [7].
Related Work
Gabber et al. [6] proposed an authentication system, named Janus. In the Janus system,
a user generates a pair of a pseudonym and a password for each service provider from
his/her secret and the corresponding service ID with a cryptographic function. Hencethe amount of memory does not depend on the number of service providers. The Janus
system satisfies personarization, unlinkability in multi-service environment, and memory efficiency. However, the property of impersonation resistance was not much treatedin [6]. Both Juang [10] and Hwang & Shiau [9] proposed authentication systems in
multi-service environment with smart cards which satisfy memory efficiency. However, these systems cannot achieve unlinkability in multi-service environment. Liao andWang [11] proposed the anonymous authentication system in multi-service environment
with smart cards which have both memory efficiency and unlinkability in multi-service
environment. However, service providers cannot identify each user in the system. Similarly, in anonymous credential systems [4] and in the systems based on group signatures [5], service providers cannot identify each user.

Organization
This paper is organized as follows. In Section 2 we recall the definition of identification
schemes [7] and introduce its slight modification. In Section 3 we consider an extensionof identification schemes to the case where there are multiple service providers. We also
formalize the property of unlinkability in multi-service environment. Section 4 shows
our proposed identification scheme which satisfies impersonation resistance, unlinkability, memory efficiency, and personalization. Section 5 describes an example of implementation of our authentication system based on the Schnorr identification scheme [12].
Section 6 concludes the paper.

2

Identification Scheme

In this paper, we show an extension of an identification scheme which realizes anauthentication system which satisfies all the requirements, that is, impersonation resistance against insiders, personalization, unlinkability in multi-service environment,
and memory efficiency. In this section, we first show the definition of identification
schemes [7]. Next, we discuss the extension of the definition of identification schemes
based on the equality of the outputs of protocols.
2.1 Definitions
An interactive Turing machine (ITM) is a multi-tape Turing machine with read-only input tapes, a read-and-write work tape, a write-only output tape, a pair of communication
tapes, and a read-and-write switch tape consisting of a single cell. One communication
tape is read-only and the other is write-only.
Two ITMs A and B are said to be linked if– an input tape of A coincides with an input of B,– the read-only communication tape of A coincides with the write-only communication tape of B, and vice versa, and– the switch tape of A coincides with that of B.
The shared input tape is called the common input tape of the two ITMs, while the othertapes are called an auxiliary input tape. A joint computation of two linked ITMs is asequence of pairs of the local configurations (that is, the state, the contents of the tapes,
and the positions of the heads) of the ITMs, where the configuration of one ITM is not
modified when the configuration of the other ITM is modified, which is realized by theswitch tape (if the content of the switch tape is 0, the configuration of the one ITM
is modified, and otherwise that of the another one is modified). The output of a joint
computation is the content of the output tape of one of the ITMs.
The output of a Turing machine A on an input x is denoted by A(x). We denote
by hA, Bi a joint computation of ITMs A and B, and by hA(y), B(z)i(x) its output
on a common input x, an auxiliary input y for A, and an auxiliary input z for B. We
sometimes omit the brackets if the input tapes are blank. In the rest of this paper, wesometimes call a Turing machine A an “algorithm” A, and a joint computation hA, Bi a“protocol”. If A is a probabilistic algorithm, Ar (x) denotes the output of A on an input
x and random coins r. We denote by p(n) denotes any polynomial of n ∈ N.

Definition 1. An identification scheme is a pair of a probabilistic polynomial-time algorithm I and a protocol hP, Vi of two probabilistic polynomial-time ITMs such that:– Viability: For any n ∈ N, any α ∈ {0, 1}n , and any s ∈ {0, 1}n ,Pr[hP(s), Vi(α, Is (α)) = 1] = 1.
– Impersonation resistance against insiders: For any pair (B 0 , B 00 ) of probabilistic
polynomial-time ITMs, any sufficiently large n ∈ N, any α ∈ {0, 1}n , and any z,
Pr[hB00 (z, T ), Vi(α, IS (α)) = 1] <

1
,
p(n)

where S is a random variable uniformly distributed over {0, 1}n and T is a randomvariable describing the output of B 0 (z) after interacting with P(S), on common
input (α, IS (α)), for polynomially many times.
Then, the string s is called a secret-key, the string α is called a pseudonym, thealgorithm I is called a verifying-key generating algorithm, the output of I is called averifying-key, and the protocol hP, Vi is called an identification protocol.
2.2

Extension Based on Equality of Output of Protocols

In this section, we extend the identification scheme by the equality of the outputs ofprotocols. We also show the extended identification schemes which satisfies viability
and impersonation resistance.
For any protocol hA, Bi and any input x, it is easy to see that there exists a protocol
hA0 , B0 i such that
hA, Bi(x) = hA0 (x), B 0 (x)i.
In addition, it is easy to see that there exists a protocol hA00 , B 00 i such thathA0 (x), B0 (x)i = hA00 (x), B 00 i.
The next lemma follows from the above arguments.
Lemma 1. For any identification protocol hP, Vi, any n ∈ N, any α ∈ {0, 1}n , andany s ∈ {0, 1}n , there exists a protocol hP 0 , V 0 i such thathP(s), Vi(α, Is (α)) = hP 0 (s, α), V 0 i(Is (α)).
For instance, the protocol hP 0 , V 0 i can be constructed as follows:
1. P 0 is an ITM which reads α on the auxiliary input tape, writes α in the write-onlycommunication tape, and then behaves in the same manner as P.
2. V 0 is a modification of V, which reads α on the read-only communication tapeinstead of reading α on the common input tape.
The modified version of identification protocol hP 0 , V 0 i is called the extended identification protocol w.r.t. hP, Vi.

Lemma 2. If (I, hP, Vi) is an identification scheme and hP 0 , V 0 i is the extended identification protocol w.r.t. hP, Vi, the extended identification scheme (I, hP 0 , V 0 i) satisfies
the following property: for any pair (B0 , B00 ) of probabilistic polynomial-time ITMs,
any sufficiently large n ∈ N, any α ∈ {0, 1}n , and any z,
Pr[hB00 (z, T, α), V 0 i(IS (α)) = 1] <

1
,
p(n)

where S is a random variable uniformly distributed over {0, 1}n and T is a randomvariable describing the output of B0 (z) after interacting with P 0 (S, α), on common
input (IS (α)), for polynomially times.
Proof. Assuming that there exists a pair (C 0 , C 00 ) of probabilistic polynomial-time ITMs
such that for some α0 ∈ {0, 1}n , some z 0 , and some polynomial q(n) of n,
Pr[hC 00 (z 0 , T 0 , α), V 0 i(IS 0 (α0 )) = 1] ≥

1
,
q(n)

where S 0 is a random variable uniformly distributed over {0, 1}n and T 0 is a randomvariable describing the output of C 0 (z 0 ) after interacting with P 0 (S 0 , α0 ) on the common
input (IS 0 (α0 )) for polynomially times. We can construct a pair (D0 , D00 ) of probabilistic polynomial-time ITMs such that:
1. D0 is a modification of C 0 , which reads α on the read-only communication tapeinstead of reading α.
2. D00 is an ITM which skips writing α on the write-only communication tape, andthen behaves in the same manner as C 00 .
Then the distribution of the random variable T 00 , which describes the output of D0 after
interacting with P(S 0 ), equals the distribution of T 0 . According to previous 1 and 2, thepair of D0 and D00 satisfies the following property:
1
Pr[hD00 (z 0 , T 0 ), Vi(α, IS 0 (α0 )) = 1] ≥
.
q(n)
2

This is contradictory to Definition 1.
The next theorem follows from Lemma 1 and Lemma 2:

Theorem 1. If (I, hP, Vi) is an identification scheme and hP 0 , V 0 i is the extended
identification protocol w.r.t. hP, Vi, the extended identification scheme (I, hP 0 , V 0 i)
satisfies the following property:– Viability: for any n ∈ N, any α ∈ {0, 1}n , and any s ∈ {0, 1}n ,Pr[hP 0 (s, α), V 0 i(Is (α)) = 1] = 1.
– Impersonation resistance against insiders: for any pair (B 0 , B 00 ) of probabilistic
polynomial-time ITMs, any sufficiently large n ∈ N, any α ∈ {0, 1}n , and any z,
Pr[hB00 (z, T ), V 0 i(IS (α)) = 1] <

1
,
p(n)

where S is a random variable uniformly distributed over {0, 1}n and T is a randomvariable describing the output of B0 (z) after interacting with P 0 (S, α) on common
input IS (α), for polynomially many times.

3

Extension of Identification Scheme for Multi-Service
Environment and Unlinkability in Multi-Service Environment

In this section, we define identification schemes in multi-service environment by extending identification schemes of Definition 1. The key is the use of a set of functions
that map strings to strings. We also formalize the property of unlinkability in multiservice environment.
3.1

Extension of Identification Scheme for Multi-Service Environment

In order to describe identification schemes in multi-service environment, we introduce
user IDs and service IDs, which are n-bit strings corresponding uniquely to users andservice providers, respectively. We consider a set of functions that map strings whichindicate service IDs to strings which indicate pseudonyms or secret-keys. For ease of
explanation, we consider only length-preserving functions. Let F be a set of functions
that map n-bit strings to n-bit strings, that is, F = {fx : {0, 1}n → {0, 1}n }x∈{0,1}n ,where x ∈ {0, 1}n indicates a user ID.
Let F and G be sets of functions mapping n-bit strings to n-bit strings. For any user
ID a and any service ID b, fa (b) and ga (b) denote the secret-key and the pseudonym
corresponding to the pair (a, b), respectively.
Then, we define identification schemes in multi-service environment, which is aquadruplet of a verifying-key generating algorithm I, an identification protocol hP, Vi,sets F , and G of functions. An identification scheme in multi-service environment isconstructed by replacing a secret-key s and a pseudonym α in Definition 1 with fa (b)and ga (b), respectively. An identification scheme in multi-service environment clearlysatisfies the property of viability in Definition 1.
3.2

Unlinkability in Multi-Service Environment

We define the property concerning privacy protection, which is called unlinkability inmulti-service environment. Informally, this property means that it is difficult for any
adversaries to determine whether two pseudonyms (and secret-keys) for distinct service
IDs are generated from the same user ID or not. We define this property as follows:
Definition 2. An identification scheme in multi-service environment (I, hP, Vi, F, G)
has unlinkability in multi-service environment if for any probabilistic polynomial-timealgorithm A, any sufficiently large n ∈ N, and any b 6= b0 ∈ {0, 1}n ,Pr[A(gU (b), gU (b0 )) = 1] − Pr[A(gU (b), gW (b0 ))] = 1| <

1
p(n)

and
| Pr[A(IfU (b) (gU (b)), IfU (b0 ) (gU (b0 ))) = 1]
− Pr[A(IfU (b) (gU (b)), IfW (b0 ) (gW (b0 ))) = 1]| <

1
,
p(n)

where U and W are random variables independently and uniformly distributed over{0, 1}n .

As an example of “linkable” schemes, we consider an identification scheme inmulti-service environment in which the same secret-key and pseudonym (we assume
they are unique for each user ID) are used for all the service providers. That is, we
assume that for any a, fa and ga are functions which output the same string on any
input b, that is, for any a ∈ {0, 1}n and any b, b0 ∈ {0, 1}n , fa (b) = fa (b0 ) andga (b) = ga (b0 ). In this scheme, it is trivial to check whether or not two pseudonyms
for distinct service providers are related to the same user. If an algorithm A0 outputs
1 if the first input equals the second input, and outputs 0 otherwise, it then holds that
Pr[A0 (gU (b), gU (b0 )) = 1] = 1 and Pr[A0 (gU (b), gW (b0 )) = 1] < 1/p(n). Hence thisscheme does not have unlinkability in multi-service environment.

4

Identification Scheme Achieving Impersonation Resistance,
Unlinkability, Memory Efficiency, and Personalization

In this section, we propose an identification scheme in multi-service environment which
satisfies impersonation resistance against insiders, unlinkability in multi-service environment, memory efficiency on auxiliary input tape, and personalization by using an
identification scheme and pseudorandom functions [8].
4.1

Proposed Scheme

We explain the overview of our proposed scheme. Assume that each user stores twofunctions to generate his/her pseudonyms and secret-key. First, after receiving a service
ID, a user generates the pair of the pseudonym and the secret-key with the service ID
and his/her functions. Next, the user and the corresponding service provider follow an
identification protocol. In order to evaluate our scheme, we further modify the definitionof identification schemes.
Extension of Identification Scheme for Construction of Our Scheme For any function f , let hf i be the description of an algorithm which on an input x returns f (x), andwe assume any Turing machine can execute the algorithm which compute f if the machine is given the description hf i. If hP, Vi is an identification protocol and hP 0 , V 0 i isthe extended identification protocol w.r.t. hP, Vi, the re-extended identification protocol
hP 00 , V 0 i w.r.t. hP, Vi is constructed as follows:– P 00 is an ITM which first reads hfa i and hga i on the auxiliary input tape. Afterreading b on the common input tape, P 00 computes fa (b) and ga (b). Next, P 00 readsfa (b) and ga (b) instead of reading the auxiliary input s, α of P 0 , and then behavesin the same manner as P 0 .
Our proposed scheme is a quadruplet of a verifying-key generating algorithm I,
a re-extended identification protocol hP 00 , V 0 i, pseudorandom functions F , and G. In
what follows, we show that our identification scheme satisfies impersonation resistanceagainst insiders, unlinkability in multi-service environment, memory efficiency on auxiliary input tape, and personalization.

Pseudorandom Functions A pseudorandom function, which is a multi-set of functions
that map strings to strings, cannot be distinguished from a truly random function.
An oracle machine is a Turing machine with an additional tape, called the oracle
tape, and two special states, called oracle invocation and oracle appeared. For configurations with states different from oracle invocation, the next configuration is definedas usual. Let γ be a configuration in which the state is oracle invocation, the oracle is afunction f , and the contents of the oracle tape is q. Then the configuration following γ
is identical to γ, except that the state is oracle appeared, and the content of the oracle
tape is f (q). For any oracle machine M and function f , let Mf denote the output of M
when given access to the oracle f . The string q is called M’s query and f (q) is called
the oracle reply.
Definition 3. A multi-set F = {fx : {0, 1}n → {0, 1}n }x∈{0,1}n is called a pseudorandom function, if for any probabilistic polynomial-time oracle machine M , and any
sufficiently large n ∈ N,
| Pr[MfU (1n ) = 1] − Pr[MH (1n ) = 1]| <

1
,
p(n)

where U is a random variable uniformly distributed over {0, 1}n and H is a randomvariable uniformly distributed over all functions from {0, 1}n to {0, 1}n .
The following three lemmas are used to prove the impersonation resistance and unlinkability in multi-service environment of our identification scheme. The next lemma
follows from Definition 3.
Lemma 3. For any pseudorandom functions F , any b ∈ {0, 1}n , any probabilistic
polynomial-time algorithm A, and any x ∈ {0, 1}n ,| Pr[A(fU (b), x) = 1] − Pr[A(W, x) = 1]| <1p(n)where U and W are random variables independently and uniformly distributed over{0, 1}n .
Proof. According to Definition 3, the oracle reply which is given by the random variable H distributed over all functions on any query is obviously a random variable uniformly distributed over {0, 1}n . Assuming for contrary that there exists a probabilistic
polynomial-time algorithm A0 such that for some x0 ∈ {0, 1}n and some polynomial
q(n) of n,1| Pr[A0 (fU (b0 ), x0 ) = 1] − Pr[A0 (W, x0 ) = 1]| ≥.
q(n)Let M0 be a probabilistic polynomial-time oracle machine which receives the oracle
reply fU (b0 ) on a query b0 and then invokes A0 on inputs fU (b0 ) and x0 . Then we havethat1,
| Pr[M0fU (1n ) = 1] − Pr[M0H (1n ) = 1]| ≥q(n)which contradicts Definition 3 of pseudorandom functions.

2The following lemma can be shown similarly to Lemma 3.
Lemma 4. For any pseudorandom function F , any b ∈ {0, 1}n , any probabilistic
polynomial-time algorithm A, B, and any x ∈ {0, 1}n ,| Pr[A(B(fU (b), x)) = 1] − Pr[A(B(W, x)) = 1]| <

1
,
p(n)

where U and W are random variables independently and uniformly distributed over{0, 1}n .
The following lemma can be shown similarly to Lemma 4 since any joint computation can be simulated by a probabilistic polynomial-time algorithm.
Lemma 5. For any pseudorandom functions F and G, any b ∈ {0, 1}n , any probabilistic polynomial-time algorithm A, any protocol hB, Ci of probabilistic polynomial-time
ITMs, and any x ∈ {0, 1}n ,| Pr[A(hB(fU (b), x), Ci(gU (b), y)) = 1]
− Pr[A(hB(W, x), Ci(X, y)) = 1]| <

1
,
p(n)

where U , W , and X are random variables independently and uniformly distributed
over {0, 1}n .
4.2

Evaluation of Impersonation ResistanceIn this section, we show that our proposed scheme in multi-service environment using
pseudorandom functions as F and G satisfies impersonation resistance against insiders.
First, we prove that an identification scheme in multi-service environment withpseudorandom functions has impersonation resistance against insiders.
Theorem 2. For any identification scheme in multi-service environment (I, hP, Vi,
F, G) such that F and G are pseudorandom functions, any pair (B 0 , B 00 ) of probabilistic polynomial-time ITMs, any sufficiently large n ∈ N, any b ∈ {0, 1}n , and anyz,1
Pr[hB00 (z, T 0 ), Vi(gU (b), IfU (b) (gU (b))) = 1] <,p(n)where U is a random variable uniformly distributed over {0, 1}n and T 0 is a randomvariable describing the output of B 0 (z) after interacting with P(fU (b)), on common
input (gU (b), IfU (b) (gU (b))), for polynomially many times.
Proof. For any probabilistic algorithm A , there exists a deterministic algorithm A0
that outputs A0 (r, x) = Ar (x) on input x and random coins r. According to Lemma 4
and Lemma 5, it holds that for any probabilistic polynomial-time algorithm A and anyb ∈ {0, 1}n ,| Pr[A(hP(fU (b)), B 0 i(gU (b), IfU (b) (gU (b)))) = 1]
− Pr[A(hP(W ), B0 i(gU (b), IW (gU (b))) = 1]| <

1
,
p(n)

where U and W are random variables uniformly and independently distributed over{0, 1}n . Therefore, it holds that
| Pr[hB 00 (z, T 0 ), Vi(gU (b), IfU (b) (gU (b))) = 1]
− Pr[hB00 (z, T ), V i(gU (b), IW (gU (b))) = 1]| <

1
,
p(n)

where T = hP(W ), B0 i(gU (b), IW (gU (b))) and T 0 = hP(fU (b)), B0 i(gU (b), IfU (b) (gU (b))).
According to the definition of impersonation resistance against insiders in Definition 1,
Pr[hB00 (z, T ), V i(gU (b), IW (gU (b))) = 1] <

1
,
p(n)

hence
Pr[hB00 (z, T 0 ), V i(gU (b), IfU (b) (gU (b))) = 1] <

1
.
p(n)
2

In the case where the common tape includes b in addition, it is can be proven that thescheme has impersonation resistance against insiders. The next theorem follows from
Theorem 1 and Theorem 2:
Theorem 3. If a pair (I, hP, Vi) is an identification scheme, then our proposed identification scheme, which is a quadruplet of I, re-extended identification protocol hP 00 , V 0 i
w.r.t. hP, Vi and pseudorandom functions F , and G, satisfies the following properties:– Viability: for any n ∈ N, any a ∈ {0, 1}n and any b ∈ {0, 1}n ,Pr[hP 0 (hfa i, hga i), V 0 i(b, Ifa (b) (ga (b))) = 1] = 1.
– Impersonation resistance against insiders: for any pair (B 0 , B 00 ) of probabilistic
polynomial-time ITMs, any sufficiently large n ∈ N, any b ∈ {0, 1}n and any z,
Pr[hB00 (z, T 0 ), V 0 i(b, IfU (b) (gU (b))) = 1] <

1
,
p(n)

where U is a random variable uniformly distributed over {0, 1}n and T 0 is a random variable describing the output of B0 (z) after interacting with P 0 (hfU i, hgU i),on common input b and IfU (b) (gU (b)) , for polynomially many times.
4.3

Evaluation of Unlinkability in Multi-Service Environment

In this section, we prove that our proposed identification schemes satisfies unlinkability
in multi-service environment.
Theorem 4. Our proposed identification scheme (I, hP 00 , V 0 i, F, G) has unlinkability
in multi-service environment.

Proof. According to Lemma 3,| Pr[A(gU (b), gU (b0 )) = 1] − Pr[A(gU (b), X) = 1]| <

1
p(n)

(1)

| Pr[A(gU (b), gW (b0 )) = 1] − Pr[A(gU (b), Y ) = 1]| <

1
,
p(n)

(2)

and

where U , W , X, and Y are random variables independently and uniformly distributed
over {0, 1}n . X and Y follow the same distribution, hence| Pr[A(gU (b), X) = 1] − Pr[A(gU (b), Y ) = 1]| <

1
.
p(n)

(3)

According to Inequalities (1), (2), and (3),| Pr[A(gU (b), gU (b0 )) = 1] − Pr[A(gU (b), gW (b0 ))] = 1| <

1
.
p(n)

(4)

In a similar way, according to Lemma 4,| Pr[A(IfU (b) (gU (b)), IfU (b0 ) (gU (b0 ))) = 1]
− Pr[A(IfU (b) (gU (b)), IX (Y )) = 1]| <

1
p(n)

(5)

1
,
p(n)

(6)

and
| Pr[A(IfU (b) (gU (b)), IfW (b0 ) (gW (b0 ))) = 1]
− Pr[A(IfU (b) (gU (b)), IZ (Q)) = 1]| <where U , W , X, Y , Z and Q are random variables independently and uniformly distributed over {0, 1}n . X and Z follow the same distribution and Y and Q follow thesame distribution, hence| Pr[A(IfU (b) (gU (b)), IX (Y )) = 1]
− Pr[A(IfU (b) (gU (b)), IZ (Q)) = 1]| <

1
.
p(n)

(7)

According to Inequalities (5), (6), and (7),| Pr[A(IfU (b) (gU (b)), IfU (b0 ) (gU (b0 ))) = 1]
− Pr[A(IfU (b) (gU (b)), IfW (b0 ) (gW (b0 ))) = 1]| <

1
.
p(n)
2

4.4 Memory Efficiency on Auxiliary Input Tape
The auxiliary input tape of P 00 of our proposed identification scheme corresponds tothe memory of each smart card of our authentication system. The memory efficiency on
auxiliary input tape of identification schemes is defined as follows:
Definition 4. An identification scheme in multi-service environment (I, hP, Vi, F, G)
has memory-efficiency on auxiliary input tape if the length of the auxiliary input tapeof P is independent of the number of service providers.
There exist algorithms such that they compute fa and ga and the length of theirdescriptions is independent of the number of service providers. Therefore, we have thefollowing theorem:
Theorem 5. Our proposed identification scheme (I, hP 00 , V 0 i, F, G) has memory-efficiency
on auxiliary input tape.
4.5

Personalization

The property of personalization is defined as follows:
Definition 5. An identification scheme in multi-service environment (I, hP, Vi, F, G)
has personalization, if for any sufficiently large n ∈ N and any b ∈ {0, 1}n ,Pr[fU (b) = fW (b)] <1
1
and Pr[gU (b) = gW (b)] <
p(n)
p(n)

where U and W are uniformly and independently distributed over {0, 1}n .
If F and G are pseudorandom functions, the scheme clearly has personalization
because of the property of pseudorandom functions.
Theorem 6. Our proposed identification scheme (I, hP 00 , V 0 i, F, G) has personalization.

5

An Example of Implementation

In this section, we show an example of implementation of our authentication system.
The implementation is based on the Schnorr identification scheme [12], and uses acollision-free hash function instead of pseudorandom functions. We then estimate an
overhead with respect to the run time of our scheme.
5.1

The Schnorr Identification Scheme

As an example of identification schemes, we introduce the scheme proposed by Schnorr [12].
The scheme is a three-move identification scheme based on the discrete logarithm problem. Bellare and Paracio [3] showed that the scheme is secure on the assumption thatthe one more inversion problem for discrete logarithm is hard in terms of an interactive
computation.
The verifying-key generating algorithm in the Schnorr identification scheme outputs(p, q, g, X) on input s ∈ {0, 1}k for a security parameter k ∈ N, where p is a prime
number such that 2k−1 ≤ p < 2k , q is a prime divisor of p − 1, g is a generator ofa subgroup of Z∗p of order q, and X is g s mod p. In our system, (p, q, g) is regarded
as common parameters and (p, q, g) can be computed independently of X. Hence theverifying-key generating algorithm can be divided into the algorithm C, which outputs(p, q, g) on input 1k , and the algorithm I 0 , which outputs X on input s.
The Schnorr identification protocol is shown as follows and in Fig.1.
1. P chooses y ∈ Zq randomly, computes g y mod p, and send the result as Y to V;
2. V chooses c ∈ Zq randomly and sends c to P;
3. P computes y + cs mod q and sends the result as z to V;
4. V outputs 1 if g z = Y X c (mod p), and 0 otherwise.

Setting

Identification( p, q, g ) ← C (1 )s ←{0,1}
X ← g mod p
$

k

$

k

V (X )

P(s)

y
Y

←Z
← g mod p
$

q

y

s

z ← y + cs mod q

αY
,

$

c

c ← Ζqz

If g z YX cthen d 1=←
else d ← 0

Fig. 1. The Schnorr identification scheme.

5.2

The Implementation of Our Authentication System

Let {u1 , u2 , . . . , u` } be the set of users and {s1 , s2 , . . . , sm } the set of service providers.
Each user secretly stores his/her user ID in his/her smart card. Let {a1 , a2 , . . . , a` } bethe set of user IDs. A user ui is associated with his/her user ID ai , and if i 6= j, thenai 6= aj . Each service provider is labelled by his/her service ID, which is the public
identifier. Let {b1 , b2 , . . . , bm } be the set of the service IDs. A service provider sj is
associated with his service ID bj , and if i 6= j, then bi 6= bj .
We use a collision-free hash function in place of pseudorandom functions. Moreconcretely, h(0 k a k b) and h(1 k a k b) are used as fa (b) and ga (b) in the system respectively, where h denotes a collision-free hash function and k denotes concatenation.
In our authentication system, there is a manager M , which sets up several parameters. First, we show the preparation procedure which is operated by M .

– Startup: M chooses a security parameter k ∈ N, and computes (p, q, g) with thealgorithm C.
– Registration of Users: When a new user ui requests to join in the system, M issues
a smart card which stores ai ∈ {0, 1}k − {a1 , a2 , . . . ai−1 } chosen randomly and(p, q, g) to ui .
– Registration of Services: When a new service provider sj requests to join in thesystem, M sends bj ∈ {0, 1}k − {b1 , b2 , . . . bi−1 } chosen randomly and (p, q, g)
to sj . Then M computes pairs (h(0 k ai k bj ), h(1 k ai k bj )) for all i, and sends
pairs (h(1 k ai k bj ), g h(0kai kbj ) mod p) for all i to sj .
Next, we show the identification protocol as follows and in Fig. 2.
1. ui sends an authentication query to sj .
2. sj sends bj to ui .
3. ui computes a pair (h(0 k ai k bj ), h(1 k ai k bj )) and sends h(1 k ai k bj ) to sj .
4. sj specifies the corresponding g h(0kai kbj ) mod p from h(1 k ai k bj ).
5. ui and sj follow the Schnorr identification scheme.

Setting$( p, q, g ) ← C (1 )FOR (1 ≤ i ≤ m)
FOR (1 ≤ j ≤ l)s ← h(0 || a || b )α ← h(1 || a || b )X ← g mod p
I (α ) = X
ENDFORENDFORk

Identification
P(a )
query
s ← h(0 || a || b )b
α ← h(1 || a || b )
i

i

j

y

i

j

Y

i

j

i

j

←Z
← g mod p
$

q

y

s

s

z ← y + cx mod q

V (b )
i

j

αY
,

c
z

I s (α ) → X$

c ← Ζq=←else d ← 0

If g z YX cthen d 1

Fig. 2. Our identification scheme based on the Schnorr identification scheme.

5.3

Discussion

A naive scheme realizing unlinkability in multi-service environment can be achieve by
storing a user’s secret-keys and pseudonyms, which are randomly chosen, in a table.
In the naive scheme, the amount of memory which a user needs is proportional to thenumber of services. Using our scheme, the amount of memory does not depend on thenumber of services, however, two more hash computations are required compared to thenaive scheme. Let ta (b) = h(0 k a k b) and t0a (b) = h(1 k a k b). Assuming that thesets {ta }a∈{0,1}n and {t0a }a∈{0,1}n are pseudorandom functions, the implementationof our authentication system satisfies impersonation resistance against insiders, unlinkability in multi-service environment, memory efficiency, and personalization.

6

Conclusions

In this paper we proposed an authentication system in multi-service environment which
satisfies impersonation resistance, unlinkability in multi-service environment, memory
efficiency, and personalization. Due to the use of pseudorandom functions, the memory requirement for each smart card is independent of the number of services. Thisis a remarkable advantage when a massive number of services utilize the system. We
showed an example of our system based on the Schnorr identification scheme, in which
pseudorandom functions are replaced with collision-free hash functions.
Our future work includes the following:– Implementing our system with smart cards and a PC in order to measure the execution time and to compare it with that of other related authentication systems.
– A comparison of the circuit size of our implementation with a hash function andthat of a naive method using a table of pairs of a pseudonym and secret-key . We
conjecture that as the number of service providers increase, our system will become
more memory efficient than the naive method.

Acknowledgements
This work was in part supported by CREST-DVLSI of JST. We are grateful for theirsupport.

References
1. OpenID. http://openid.net/
2. Shibboleth. http://shibboleth.internet2.edu/
3. Bellare, M., Palacio, A.: GQ and schnorr identification schemes: Proofs of security against
impersonation under active and concurrent attacks. In: Advances in Cryptology - CRYPTO
2002. LNCS, Springer-Verlog (2002)
4. Camenisch, J., Lysyanskaya, A.: An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: Advances in Cryptology - EUROCRYPT
2001. LNCS, vol. 2045, pp. 93–118. Springer-Verlag (2001)
5. Chaum, D., van Heyst, E.: Group signatures. In: Advances in Cryptology - EUROCRYPT
1991. LNCS, vol. 547, pp. 257–270. Springer-Verlag (1991)
6. Gabber, E., Information, C., Gibbons, P.B., Matias, Y., Mayer, A.: How to make personalized
web browsing simple, secure, and anonymous. In: Financial Cryptography. LNCS, vol. 1318,
pp. 17–31. Springer-Verlag (1997)
7. Goldreich, O.: Foundations of Cryptography. Cambridge University (2001)
8. Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. Journal of theACM (JACM) 33(4), 792–807 (1986)
9. Hwang, R.J., Shiau, S.H.: Provably efficient authenticated key agreement protocol for multiservers. The Computer Journal 50, 602–615 (2007)
10. Juang, W.S.: Efficient multi-server password authenticated key agreement using smart cards.
IEEE Transactions on Consumer Electronics 50, 251–255 (2004)
11. Liao, Y.P., Wang, S.S.: A secure dynamic ID based remote user authentication scheme formulti-server environment. Computer standards and interfaces 31(1), 24–29 (2009)12. Schnorr, C.P.: Efficient signature generation by smart cards. In: Journal of Cryptology. vol. 4,
pp. 161–174. Springer New York (1991)