IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3

No. 3

54–66 (Oct. 2010)

Regular Paper

An Identifiable Yet Unlinkable Authentication System
in Multi-service Environment
Toru Nakamura,†1 Shunsuke Inenaga,†2Daisuke Ikeda,†2 Kensuke Baba†3
and Hiroto Yasuura†2
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, weak-unlinkability,
and memory eﬃciency. The proposed system is the first system which satisfies
all the properties. In the proposed system, transactions of a user within a single service can be linked (personalization), while transactions of a user among
distinct services can not be linked (weak-unlinkability). The proposed system
can be used with smart cards since the amount of memory required by thesystem does not depend on the number of services. First, this paper formalizes
the property of weak-unlinkability, which has not been formalized in the literatures. Next, this paper extends an identification scheme with a pseudorandomfunction in order to realize an authentication system which satisfies all the requirements. This extension can be done with any identification scheme andany pseudorandom function. Finally, this paper proposes an implementation
with the Schnorr identification scheme and a collision-free hash function as an
example of the proposed system.

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 user name (pseudonym) and a password of multiple services. Hencemuch attention is recently paid to authentication systems which enable users to
use multiple services after they register only once at a registration manager. For
example, credit card systems and single-sign-on systems such as Microsoft’s .NET
†1 Graduate School of Information Science and Electrical Engineering, Kyushu University†2 Faculty of Information Science and Electrical Engineering, Kyushu University†3 Research and Development Division, Kyushu University Library

54

Passport 1) , Shibboleth 2) , and OpenID 3) , have been popular. In this paper, sucha system is called an authentication system in multi-service environment.
The multi-service environment raises a new problem on privacy of users, thatis, the daily activity of a user can be revealed by gathering information about
his/her usage of 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 ﬁles and trace actions ofa user from his/her transactions. Service logs of a user in a service provider canbe associated with those in other service providers if a pseudonym of the user isused among multiple service providers. In fact, credit card systems and typicalsingle-sign-on systems are 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. For example, it
is technically viable that purchase information of credit cards in a supermarket
is shared with other companies or is sold to another company without asking
the customer. A typical single-sign-on system enables a third party to gather
information about user behaviour over multiple web sites without user consent
more easily than using “Web Bugs” 4) . Web Bugs are invisible third party images
added to a web page so that the third party receives notice of the page viewing
event.
In order to solve the problem, authentication systems should have the property that it is diﬃcult to determine whether two transactions in distinct service
providers are related to the same user or not (weak-unlinkability). There are someauthentication systems which satisfy weak-unlinkability, such as Janus 5) , anonymous credentials 6) , and authentication systems based on group signatures 7) .
Authentication systems which satisfy weak-unlinkability can be classiﬁed according to the degree of unlinkability as follows.
• Transactions of a user can be linked within a service, while transactions of auser among 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, withoutc 2010 Information Processing Society of Japan

55

An Identifiable Yet Unlinkable Authentication System in Multi-service Environment

identiﬁcation of each user, the purpose of service logs previously described cannot
be achieved. Therefore, the system with the latter property cannot be applied to“personalized services”, which customize and provide the contents according to auser’s proﬁle 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.
A appropriate strategy to realize weak-unlinkability depends on the way how
a user maintains pairs pseudonym and a password. We consider the way thata user maintains the pairs. There are two ways on how to maintain pairs, thatis, (1) doing by himself and (2) delegating the maintenance of the pairs to atrusted third party, such as a registration manager. We focus on the case (1) inthis paper. In the case (1), some trusted devices, such as PCs and smart cards,
are usually used for storing the pairs. A straightforward solution that satisﬁes
both weak-unlinkability and personalization is that each user stores the tableof the pairs of a pseudonym and a password for all service providers. In thissolution, the amount of memory required by the system is proportional to thenumber of service providers. This solution would be an eﬃcient solution to realize
weak-unlinkability for systems with PCs as they have enough amount of memory.
However, in this paper we are interested in situations where the portability ofdevice of a user is indispensable, such as the use of ATM machines. Hence weconsider a smart card as a device of a user. Since smart cards have much lessmemory than PCs, the above straightforward solution is unsuitable for smart
cards when the number of service providers is considerably large. For example,
VISA, which is a company that oﬀers credit card services, provides the assuranceof acceptance at more than 30 million Merchant outlets in 2009 8) . In anotherinstance, the number of web sites which support OpenID is about 50 thousandin July 2009 9) . Therefore, it is important for any authentication system withsmart cards to require as little amount of memory as possible in order to store
pseudonyms and passwords (memory eﬃciency).
In practical systems, the entities who try to impersonate a legitimate user are
not only eavesdroppers but also malicious service providers. Therefore, authen-

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3tication systems should have the property that an adversary cannot impersonate
a legitimate user even if the adversary is a service provider (impersonation resistance against insiders).
The requirements for an authentication system considered in this paper are thefollowing.
• Personalization: service providers can identify each user.
• Weak-unlinkability: it is diﬃcult to determine whether two transactions
among distinct service providers are the same user’s or not.
• Memory eﬃciency: the amount of memory for pseudonyms and passwords
does not depend 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.
We propose an extension of an identiﬁcation scheme 10) to realize the ﬁrst
authentication system which satisﬁes all the requirements previously described.
Identiﬁcation schemes consist of a key-generating algorithm and an interactive
identiﬁcation protocol. Identiﬁcation schemes are required that a prover is always able to convince a veriﬁer who the prover is, whereas any adversary cannot
impersonate the prover even after getting interactions between the prover andthe veriﬁer. We note that there is no authentication system satisﬁes all of therequirements as far as we know. The overview of our extended identiﬁcation
protocol is as follows.
• First, a user generates a pair of a pseudonym and a secret-key for each service
provider from the service ID corresponding to the service which the user
wants to use by pseudorandom functions 11) .
• Next, the user and the service provider follow an identiﬁcation protocol.
The main idea of our scheme is shown in Fig. 1.
In order to evaluate our identiﬁcation scheme, we deﬁne some properties, whichcorrespond to the above requirements concerning authentication systems, basedon the computational theory. We also prove that our identiﬁcation scheme satisﬁes all the properties. To our knowledge, the deﬁnition of weak-unlinkability
has not been formalized based on the computational theory, hence we introduce
the ﬁrst formalization of weak-unlinkability. The deﬁnition of impersonation resistance in this paper is based on the formalization of security of identiﬁcation

54–66 (Oct. 2010)

c 2010 Information Processing Society of Japan

56

An Identifiable Yet Unlinkable Authentication System in Multi-service Environment

Fig. 1 Illustrations of our scheme and a straightforward solution.

schemes shown by Goldreich 10) .
We brieﬂy describe some existing authentication systems that realize memory
eﬃciency. Gabber, et al. 5) proposed an authentication system, named Janus. In
the Janus system, a user generates a pair of a pseudonym and a password foreach service provider from his/her secret and the corresponding service ID witha cryptographic function. Hence the amount of memory does not depend on thenumber of service providers. The Janus system satisﬁes personarization, weakunlinkability, and memory eﬃciency. However, the property of impersonation
resistance was not much treated in this paper. Juang 12) and Hwang and Shiau 13)
proposed authentication systems in multi-service environment with smart cards
which satisfy memory eﬃciency. However, these systems cannot achieve weakunlinkability. Liao and Wang 14) proposed the anonymous authentication system
in multi-service environment with smart cards which have memory eﬃciency andweak-unlinkability. However, service providers cannot identify each user in thesystem. Similarly, in anonymous credential systems 6) and in the systems basedon group signatures 7) , service providers cannot identify each user.
Next, we brieﬂy describe privacy-oriented single-sign-on systems. Some single-

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3

sign-on systems such as OpenID.ee 15) can treat pseudonyms of users in order torealize weak-unlinkability. The Security Assertion Markup Language (SAML) 16) ,which is a framework of single-sign on system, includes aspects of privacy protection due to the usage of pseudonyms. Hence some implementations of SAML
also can be treat pseudonyms of users. However, these implementations are basedon a proxy server which has a table of triads of a user ID, a service ID and apseudonym in order to convert a user ID to a pseudonym for a service provider.
Our authentication system is superior to these single-sign-on systems since oursystem needs not to additional proxy servers.
This paper is organized as follows. In Section 2 we recall the deﬁnition ofidentiﬁcation schemes 10) and introduce its slight modiﬁcation. In Section 3 weconsider an extension of identiﬁcation schemes to the case where there are multiple service providers. We also formalize the property of weak-unlinkability.
Section 4 shows our proposed identiﬁcation scheme which satisﬁes impersonation
resistance, unlinkability, memory eﬃciency, and personalization. Section 5 describes an example of implementation of our authentication system based on the
Schnorr identiﬁcation scheme 17) .
2. Identiﬁcation Scheme
In this paper, we show an extension of an identiﬁcation scheme which realizes anauthentication system which satisﬁes all the requirements, that is, impersonation
resistance against insiders, personalization, weak-unlinkability, and memory eﬃciency. In this section, we ﬁrst show the deﬁnition of identiﬁcation schemes 10) .
Next, we discuss the extension of the deﬁnition of identiﬁcation schemes basedon an equality of protocols.
2.1 Deﬁnitions
An interactive Turing machine (ITM) is a multi-tape Turing machine withread-only input tapes, a read-and-write work tape, a write-only output tape, apair of communication tapes, and a read-and-write switch tape consisting of asingle 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 com-

54–66 (Oct. 2010)

c 2010 Information Processing Society of Japan

57

An Identifiable Yet Unlinkable Authentication System in Multi-service Environment

munication 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 other tapes are called an auxiliary input tape. A joint computation of twolinked ITMs is a sequence of pairs of the local conﬁgurations (that is, the state,
the contents of the tapes, and the positions of the heads) of the ITMs, where
the conﬁguration of one ITM is not modiﬁed when the conﬁguration of the other
ITM is modiﬁed, which is realized by the switch tape (if the content of the switch
tape is 0, the conﬁguration of the one ITM is modiﬁed, and otherwise that of
the another one is modiﬁed). 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 A, B a joint computation of ITMs A and B, and by A(y), B(z)(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, we sometimes call a Turing machine A an “algorithm” A,
and a joint computation A, B 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 byp(n) denotes any polynomial of n ∈ N.
We show the deﬁnition of identiﬁcation schemes. An identiﬁcation scheme
consists of a probabilistic algorithm and a protocol. Identiﬁcation schemes are
required that an entity (prover) is always able to convince another entity (veriﬁer), whereas any adversary cannot fool the veriﬁer into believing that he/sheis the prover. Furthermore, any adversary cannot impersonate the prover evenafter receiving polynomially many proofs of identity from the prover.
Deﬁnition 1 An identiﬁcation scheme is a pair of a probabilistic polynomialtime algorithm I and a protocol P, V of two probabilistic polynomial-time ITMs
such that• Viability: for any n ∈ N, any α ∈ {0, 1}n , and any s ∈ {0, 1}n ,Pr[P(s), V(α, Is (α)) = 1] = 1,
• Impersonation resistance against insiders: for any pair (B  , B  ) of probabilistic polynomial-time ITMs, any suﬃciently large n ∈ N, any α ∈ {0, 1}n , andany z,IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3

No. 3

1
,
p(n)
where S is a random variable uniformly distributed over {0, 1}n and T is arandom variable describing a sequence of outputs P(S), B (z)(α, IS (α)) in
polynomially many trials.
Then, the string s is called a secret-key, the string α is called a pseudonym,
the algorithm I is called a verifying-key generating algorithm, the output of I iscalled a verifying-key, and the protocol P, V is called an identiﬁcation protocol.
2.2 Extension Based on Equality of Protocols
In this section, we extend the identiﬁcation scheme by an equality of protocols.
We also prove that the extended identiﬁcation schemes satisﬁes viability andimpersonation resistance.
For any protocol A, B and any input x, there exists a protocol A , B   suchthat
A, B(x) = A (x), B  (x).
In addition, there exists a protocol A , B   such that
A (x), B  (x) = A (x), B  .
Lemma 1 For any identiﬁcation protocol P, V, any n ∈ N, any α ∈ {0, 1}n ,and any s ∈ {0, 1}n , there exists a protocol P  , V   such that
P(s), V(α, Is (α)) = P  (s, α), V  (Is (α)).
For instance, the protocol P  , V   in the previous lemma can be constructedfrom P, V as follows:( 1 ) P  is an ITM which reads α on the auxiliary input tape, writes α in thewrite-only communication tape, and then behaves in the same manner asP.
( 2 ) V  is a modiﬁcation of V, which reads α on the read-only communication
tape instead of reading α on the common input tape.
The identiﬁcation protocol P  , V   is called the extended identiﬁcation protocol
w.r.t. P, V.
Lemma 2 If (I, P, V) is an identiﬁcation scheme and P  , V   is the extended identiﬁcation protocol w.r.t. P, V, the extended identiﬁcation scheme(I, P  , V  ) satisﬁes the following property: for any pair (B  , B  ) of probabilistic
polynomial-time ITMs, any suﬃciently large n ∈ N, any α ∈ {0, 1}n , and any z,

54–66 (Oct. 2010)

Pr[B  (z, T ), V(α, IS (α)) = 1] <c 2010 Information Processing Society of Japan

58

An Identifiable Yet Unlinkable Authentication System in Multi-service Environment

1
,
p(n)
where S is a random variable uniformly distributed over {0, 1}n and T is a randomvariable describing a sequence of outputs P  (S), B  (z)(α, IS (α)) in polynomiallymany trials.
proof: Assuming that there exists a pair (C  , C  ) of probabilistic polynomial-time
ITMs such that for some α ∈ {0, 1}n , some z  , and some polynomial q(n) of n,1
Pr[C  (z  , T  , α), V  (IS  (α )) = 1] ≥,q(n)where S  is a random variable uniformly distributed over {0, 1}n and T  is a random variable describing a sequence of outputs P  (S, α), C  (z)(IS (α)) in polynomially many trials. We can construct a pair (D , D ) of probabilistic polynomialtime ITMs such that
( 1 ) D is a modiﬁcation of C  , which reads α on the read-only communication
tape instead of reading α,( 2 ) D is an ITM which skips writing α on the write-only communication tape,and then behaves in the same manner as C  .
Then the distribution of the random variable T  , which describes a sequence of
outputs P  (S), D (z)(IS (α)) in polynomially many trials, equals the distribution of T  . According to (1) and (2), the pair of D and D satisﬁes the following
property:
1
Pr[D (z  , T  ), V(α, IS  (α )) = 1] ≥.
q(n)This is contradictory to Deﬁnition 1.
2
The next theorem follows from Lemma 1 and Lemma 2.
Theorem 1 If (I, P, V) is an identiﬁcation scheme and P  , V   is the extended identiﬁcation protocol w.r.t. P, V, the extended identiﬁcation scheme(I, P  , V  ) satisﬁes the following property:• Viability: for any n ∈ N, any α ∈ {0, 1}n , and any s ∈ {0, 1}n ,Pr[P  (s, α), V  (Is (α)) = 1] = 1,
• Impersonation resistance against insiders: for any pair (B  , B  ) of probabilistic polynomial-time ITMs, any suﬃciently large n ∈ N, any α ∈ {0, 1}n , andany z,

1,p(n)where S is a random variable uniformly distributed over {0, 1}n and T is arandom variable describing a sequence of outputs P  (S), B  (z)(α, IS (α)) in
polynomially many trials.

Pr[B  (z, T, α), V  (IS (α)) = 1] <IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3

No. 3

Pr[B  (z, T ), V  (IS (α)) = 1] <3. Extension of Identiﬁcation Scheme for Multi-Service Environment and Weak-unlinkability
In this section, we deﬁne identiﬁcation schemes in multi-service environmentby extending Deﬁnition 1. The key is the use of a set of functions that map
strings to strings. We also formalize the property of weak-unlinkability.
3.1 Extension of Identiﬁcation Scheme for Multi-Service Environment
In order to describe identiﬁcation schemes in multi-service environment, we
introduce user IDs and service IDs. A user ID and a service ID are n-bit strings
corresponding uniquely to users and service providers, respectively. We consider
a set of functions that map strings which indicate service IDs to strings whichindicate pseudonyms or secret-keys. For ease of explanation, we consider only
length-preserving functions. Let F and G be multi-sets of functions mapping
n-bit strings to n-bit strings and |F | = |G| = 2n . The sets F and G are indexedby n-bit strings. We denote that F = {fx : {0, 1}n → {0, 1}n }x∈{0,1}n and
G = {gy : {0, 1}n → {0, 1}n }y∈{0,1}n . Here the indice x and y indicate user
IDs. The preimages of functions belonging to F and G indicate a set of service
IDs. The mapping of functions belonging to F indicates a set of secret-keys andthat of functions belonging to G indicates a set of pseudonyms. That is, for any
user ID a and any service ID b, fa (b) and ga (b) denote the secret-key and thepseudonym corresponding to the pair (a, b), respectively.
Then, we deﬁne identiﬁcation schemes in multi-service environment, which isa quadruplet of a verifying-key generating algorithm I, an identiﬁcation protocol
P, V and multi-sets F and G of functions. An identiﬁcation scheme in multiservice environment is constructed by replacing a secret-key s and a pseudonym
α in Deﬁnition 1 with fa (b) and ga (b), respectively. An identiﬁcation scheme inmulti-service environment clearly satisﬁes the property of viability in Deﬁnition 1.

54–66 (Oct. 2010)

c 2010 Information Processing Society of Japan

59

An Identifiable Yet Unlinkable Authentication System in Multi-service Environment

3.2 Weak-unlinkability
We deﬁne the property concerning privacy protection, which is called weakunlinkability. Informally, this property means that it is diﬃcult for any adversaries to determine whether two pseudonyms (and verifying-keys) for distinct
service IDs are generated from the same user ID or not. We deﬁne this property
as follows:
Deﬁnition 2 An identiﬁcation scheme in multi-service environment(I, P, V, F, G) has weak-unlinkability if for any probabilistic polynomial-timealgorithm A, any suﬃciently large n ∈ N, and any b = b ∈ {0, 1}n ,1Pr[A(gU (b), gU (b )) = 1] − Pr[A(gU (b), gW (b ))] = 1| <p(n)and| Pr[A(IfU (b) (gU (b)), IfU (b ) (gU (b ))) = 1]
1,
− Pr[A(IfU (b) (gU (b)), IfW (b ) (gW (b ))) = 1]| <p(n)where U and W are random variables independently and uniformly distributed
over {0, 1}n .
We note that not all identiﬁcation schemes in multi-service environment satisfy
weak-unlinkability. We show an example of “linkable” schemes below.
Example 1 We consider an identiﬁcation scheme in multi-service environment where the same secret-key and pseudonym are used for all the service
providers. That is, we assume that for any a ∈ {0, 1}n and any b, b ∈ {0, 1}n ,fa (b) = fa (b ) and ga (b) = ga (b ) where a indicates a user ID and b, b indicate
distinct service IDs. In this scheme, it is trivial whether two pseudonyms for distinct service providers are related to the same user. If an algorithm A outputs 1
when the ﬁrst input equals to the second input, and outputs 0 otherwise, then it
holds that Pr[A (gU (b), gU (b )) = 1] = 1 and Pr[A (gU (b), gW (b )) = 1] < 1/p(n).
Hence this scheme does not have weak-unlinkability.
4. Identiﬁcation Scheme Achieving Impersonation Resistance, Unlinkability, Memory Eﬃciency, and Personalization
In this section, we modify an identiﬁcation scheme in multi-service environment
which realizes an authentication system which satisﬁes impersonation resistance

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3

against insiders, weak-unlinkability, memory eﬃciency on auxiliary input tape,and personalization by using pseudorandom functions 11) . In the authentication
system, a user behaves according to the one ITM in the protocol of the modiﬁed
identiﬁcation scheme and a service provider behaves according to the other ITM.
4.1 Proposed Scheme
We explain the overview of our proposed scheme. Assume that each user stores
two functions 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 identiﬁcation protocol. In order to evaluate ourscheme, we further modify the deﬁnition of identiﬁcation schemes.
4.1.1 Re-extended Identiﬁcation Scheme
For any function f , let f  be the description of an algorithm which on an input
x returns f (x). Then we assume any Turing machine can execute the algorithm
which compute f if the machine is given the description f . If P, V is an
identiﬁcation protocol and P  , V   is the extended identiﬁcation protocol w.r.t.
P, V, the re-extended identiﬁcation protocol P  , V   w.r.t. P, V is constructed
as follows:• P  is an ITM which ﬁrst reads fa  and ga  on the auxiliary input tape.
After reading b on the common input tape, P  computes fa (b) and ga (b).
Next, P  reads fa (b) and ga (b) instead of reading the auxiliary input s, α ofP  , and then behaves in the same manner as P  .
A re-extended identiﬁcation scheme is a quadruplet of a verifying-key generating algorithm I, a re-extended identiﬁcation protocol P  , V  , and sets offunctions F and G. Our identiﬁcation scheme is the re-extended identiﬁcation
scheme where F and G are pseudorandom functions. In what follows, we provethat our identiﬁcation scheme satisﬁes impersonation resistance against insiders,weak-unlinkability, memory eﬃciency on auxiliary input tape, and personalization.
4.1.2 Pseudorandom Functions
A pseudorandom function is a multi-set of functions that map strings to stringsand cannot be distinguished from a truly random function.
An oracle machine is a Turing machine with an additional tape, called the

54–66 (Oct. 2010)

c 2010 Information Processing Society of Japan

60

An Identifiable Yet Unlinkable Authentication System in Multi-service Environment

oracle tape, and two special states, called oracle invocation and oracle appeared.
For conﬁgurations with states diﬀerent from oracle invocation, the next conﬁguration is deﬁned as usual. Let γ be a conﬁguration in which the state is oracle
invocation, the oracle is a function f , and the contents of the oracle tape is q.
Then the conﬁguration 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.
Deﬁnition 3 A multi-set F = {fx : {0, 1}n → {0, 1}n }x∈{0,1}n is called apseudorandom function, if for any probabilistic polynomial-time oracle machine
M , and any suﬃciently large n ∈ N,
1
| Pr[MfU (1n ) = 1] − Pr[MH (1n ) = 1]| <,p(n)where U is a random variable uniformly distributed over {0, 1}n and H is arandom variable uniformly distributed over all functions from {0, 1}n to {0, 1}n .
The following three lemmas are used to prove the impersonation resistanceand weak-unlinkability of our identiﬁcation scheme. The next lemma follows
from Deﬁnition 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 ,1| Pr[A(fU (b), x) = 1] − Pr[A(W, x) = 1]| <p(n)where U and W are random variables independently and uniformly distributed
over {0, 1}n .
proof: By Deﬁnition 3, the oracle reply which is given by the random variable
H distributed over all functions on any query is obviously a random variableuniformly distributed over {0, 1}n . Assuming for contrary that there exists a
probabilistic polynomial-time algorithm A such that for some x ∈ {0, 1}n andsome polynomial q(n) of n,1.
| Pr[A (fU (b ), x ) = 1] − Pr[A (W, x ) = 1]| ≥q(n)Let M be a probabilistic polynomial-time oracle machine which receives theoracle reply fU (b ) on a query b and then invokes A on inputs fU (b ) and x .

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3

Then we have that1,q(n)which contradicts Deﬁnition 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 ,1| Pr[A(B(fU (b), x)) = 1] − Pr[A(B(W, x)) = 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 B, C of probabilistic
polynomial-time ITMs, and any x ∈ {0, 1}n ,| Pr[MfU (1n ) = 1] − Pr[MH (1n ) = 1]| ≥| Pr[A(B(fU (b), x), C(gU (b), 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 prove that our proposed scheme using pseudorandom functions as F and G satisﬁes impersonation resistance against insiders.
First, we prove that the identiﬁcation scheme in multi-service environment withpseudorandom functions has impersonation resistance against insiders.
Theorem 2 If F and G are pseudorandom functions, for any identiﬁcation
scheme in multi-service environment (I, P, V, F, G), any pair (B  , B  ) of probabilistic polynomial-time ITMs, any suﬃciently large n ∈ N, any b ∈ {0, 1}n , andany z,
1,
Pr[B  (z, T  ), V(gU (b), IfU (b) (gU (b))) = 1] <p(n)where U is a random variable uniformly distributed over {0, 1}n and T  is

54–66 (Oct. 2010)− Pr[A(B(W, x), C(X, y)) = 1]| <c 2010 Information Processing Society of Japan

61

An Identifiable Yet Unlinkable Authentication System in Multi-service Environment

a random variable describing a sequence of outputs P(fU (b)), B  (z)(gU (b),IfU (b) (gU (b))) in polynomially many trials.
proof: For any probabilistic algorithm A, there exists a deterministic algorithmA that outputs A (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-timealgorithm A and any b ∈ {0, 1}n ,| Pr[A(P(fU (b)), B  (gU (b), IfU (b) (gU (b)))) = 1]
1,
− Pr[A(P(W ), B  (gU (b), IW (gU (b))) = 1]| <p(n)where U and W are random variables uniformly and independently distributed
over {0, 1}n . Therefore, it holds that
| Pr[B  (z, T ), V(gU (b), IfU (b) (gU (b))) = 1]
1,
− Pr[B  (z, T  ), V(gU (b), IW (gU (b))) = 1]| <p(n)where T and T  are a sequence of outputs P(fU (b)), B  (z)(gU (b), IfU (b) (gU (b)))
and that of outputs P(W ), B  (z)(gU (b), IW (gU (b))) in polynomially many trials. By the deﬁnition of impersonation resistance against insiders in Deﬁnition 1,
1
Pr[B  (z, T ), V(gU (b), IW (gU (b))) = 1] <
,
p(n)
hence
1
Pr[B  (z, T  ), V(gU (b), IfU (b) (gU (b))) = 1] <.
p(n)2
In the case where the common tape includes b in addition, it can be provedthat the scheme has impersonation resistance against insiders.
The next theorem follows from Theorem 1 and Theorem 2.
Theorem 3 If F and G are pseudorandom functions, then any re-extended
identiﬁcation scheme (I, P  , V  , F, G) satisﬁes the following properties:• Viability: for any n ∈ N, any a ∈ {0, 1}n and any b ∈ {0, 1}n ,Pr[P  (fa , ga ), V  (b, Ifa (b) (ga (b))) = 1] = 1,
• Impersonation resistance against insiders: for any pair (B  , B  ) of probabilistic polynomial-time ITMs, any suﬃciently large n ∈ N, any b ∈ {0, 1}n andany z,IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3

No. 3

1
,
p(n)
where U is a random variable uniformly distributed over {0, 1}n and T 
is a random variable describing a sequence of outputs P  (fa , ga ),B  (z)(b, IfU (b) (gU (b))) in polynomially many trials.
4.3 Evaluation of Weak-unlinkability
In this section, we prove that our proposed identiﬁcation schemes satisﬁes weakunlinkability.
Theorem 4 If F and G are pseudorandom functions, then any re-extended
identiﬁcation scheme (I, P  , V  , F, G) has weak-unlinkability.
proof: By Lemma 3,
1| Pr[A(gU (b), gU (b )) = 1] − Pr[A(gU (b), X) = 1]| <
(1)
p(n)
and
1
| Pr[A(gU (b), gW (b )) = 1] − Pr[A(gU (b), Y ) = 1]| <
,
(2)
p(n)
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
1| Pr[A(gU (b), X) = 1] − Pr[A(gU (b), Y ) = 1]| <
.
(3)
p(n)
By Inequalities (1), (2), and (3),1
| Pr[A(gU (b), gU (b )) = 1] − Pr[A(gU (b), gW (b ))] = 1| <
.
(4)
p(n)
In a similar way, by Lemma 4,| Pr[A(IfU (b) (gU (b)), IfU (b ) (gU (b ))) = 1]
1
(5)
− Pr[A(IfU (b) (gU (b)), IX (Y )) = 1]| <p(n)and| Pr[A(IfU (b) (gU (b)), IfW (b ) (gW (b ))) = 1]
1,
(6)
− Pr[A(IfU (b) (gU (b)), IZ (Q)) = 1]| <p(n)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

54–66 (Oct. 2010)

Pr[B  (z, T  ), V  (b, IfU (b) (gU (b))) = 1] <c 2010 Information Processing Society of Japan

62

An Identifiable Yet Unlinkable Authentication System in Multi-service Environment

follow the same distribution, hence| Pr[A(IfU (b) (gU (b)), IX (Y )) = 1]
− Pr[A(IfU (b) (gU (b)), IZ (Q)) = 1]| <

1
.
p(n)

(7)

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

1
.
p(n)

2
4.4 Memory Eﬃciency on Auxiliary Input Tape
In our authentication system, a user behaves according to the one ITM P 
in a re-extending identiﬁcation scheme. Assuming that smart cards are used
for authentication in our system, the auxiliary input tape of P  of our proposed identiﬁcation scheme corresponds to the memory of each smart card in
our authentication system. The memory eﬃciency on auxiliary input tape ofidentiﬁcation schemes is deﬁned as follows:
Deﬁnition 4 A re-extended identiﬁcation scheme (I, P  , V  , F, G) has
memory-eﬃciency on auxiliary input tape if the length of the auxiliary input
tape of P  is independent of the number of service providers.
In a precise sense, the length of a service ID logarithmically depends on thenumber of service providers. However, the length of a service ID can be regarded
as a constant since the size of a set of service IDs is generally much larger than
the number of service providers. (In fact, all people in the world can even beindexed by only 40 bit strings.)
Hence the algorithms which compute fa and ga do not depend on the numberof service providers and the length of a service ID is independent of the numberof service providers. Therefore, we have the following theorem.
Theorem 5 If the length of a service ID is a constant number, any reextended identiﬁcation scheme has memory eﬃciency on auxiliary input tape.
4.5 Personalization
Informally, a re-extended identiﬁcation scheme has personalization if the probability that a pseudonym or a secret-key of a user for a service provider equals to
those of a distinct user for the same service provider is negligible. Personalization

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3

is deﬁned as follows:
Deﬁnition 5 A re-extended identiﬁcation scheme (I, P  , V  , F, G) has personalization, if for any suﬃciently large n ∈ N and any b ∈ {0, 1}n ,1
1
Pr[fU (b) = fW (b)] <and Pr[gU (b) = gW (b)] <
p(n)
p(n)
where U and W are uniformly and independently distributed over {0, 1}n .
We show an example of identiﬁcation schemes which has weak-unlinkability,
but does not have personalization below.
Example 2 In addition to the assumptions in Example 1, we assume eachuser has a unique pseudonym and a unique secret-key for all service providers.
That is, for any a = a ∈ {0, 1}n and any b ∈ {0, 1}n , fa (b) = fa (b) andga (b) = ga (b). In this case, Pr[fU (b) = fW (b)] = 0 and Pr[gU (b) = gW (b)] = 0.
Therefore, this scheme has personalization, and does not have weak-unlinkability.
If F and G are pseudorandom functions, the scheme clearly has personalization
because of the property of pseudorandom functions.
Theorem 6 If F and G are pseudorandom functions, then any re-extended
identiﬁcation scheme (I, P  , V  , F, G) has personalization.
5. An Example of Implementation
In this section, we show an example of implementation of the authentication system which satisﬁes impersonation resistance against insiders, weakunlinkability, memory eﬃciency on auxiliary input tape, and personalization.
The implementation is based on the re-extended identiﬁcation scheme which consists of the Schnorr identiﬁcation scheme 17) and a cryptographic hash function
instead of pseudorandom functions. We then estimate an overhead with respect
to the run time of our scheme and memory eﬃciency with respect to the transistor
count.
5.1 The Schnorr Identiﬁcation Scheme
As an example of identiﬁcation schemes, we introduce the scheme proposed by
Schnorr 17) . The scheme is a three-move identiﬁcation scheme based on the discrete logarithm problem. Bellare and Paracio 18) showed that the scheme is secureon the assumption that the one more inversion problem for discrete logarithm ishard in terms of an interactive computation.

54–66 (Oct. 2010)

c 2010 Information Processing Society of Japan

63

An Identifiable Yet Unlinkable Authentication System in Multi-service Environment

Fig. 2 The Schnorr identification scheme.

The verifying-key generating algorithm in the Schnorr identiﬁcation 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 of a subgroup of Z∗p of order q, and X is g s mod p. In oursystem, (p, q, g) is regarded as common parameters and (p, q, g) can be computed
independently of X. Hence the verifying-key generating algorithm can be divided
into the algorithm C, which outputs (p, q, g) on input 1k , and the algorithm I  ,which outputs X on input s.
The Schnorr identiﬁcation protocol is shown as follows.
( 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.
The Schnorr identiﬁcation protocol is shown in Fig. 2.
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 } be the set of user IDs. A user ui is associated with his/her user
ID ai , and if i = j, then ai = aj . Each service provider is labelled by his/her

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3service ID, which is the public identiﬁer. Let {b1 , b2 , . . . , bm } be the set of theservice IDs. A service provider sj is associated with his service ID bj , and ifi = j, then bi = bj .
We use a cryptographic hash function (for example, SHA-1 19) and
AURORA 20) ) in place of pseudorandom functions. A cryptographic hash function has (1) one-wayness and (2) collision resistance. One-wayness is the property
that for a hash function h and a hash value y, it is hard to ﬁnd any message x suchthat y = h(x). Collision-resistance is the property that it is hard to ﬁnd two different messages x1 and x2 such that h(x1 ) = h(x2 ). More concretely, h(0 a b)
and h(1 a b) are used as fa (b) and ga (b) in the system respectively, where
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 the algorithm 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 } chosenrandomly and (p, q, g) to ui .
• Registration of Services: When a new service provider sj requests to joinin the system, M sends bj ∈ {0, 1}k − {b1 , b2 , . . . bi−1 } chosen randomly and(p, q, g) to sj . Then M computes pairs (h(0 ai bj ), h(1 ai bj )) for alli, and sends pairs (h(1 ai bj ), g h(0ai bj ) mod p) for all i to sj .
Next, we show the identiﬁcation protocol as follows.
( 1 ) ui sends an authentication query to sj .
( 2 ) sj sends bj to ui .
( 3 ) ui computes a pair (h(0 ai bj ), h(1 ai bj )) and sends h(1 ai bj )to sj .
( 4 ) sj speciﬁes the corresponding g h(0ai bj ) mod p from h(1 ai bj ).
( 5 ) ui and sj follow the Schnorr identiﬁcation scheme.
The Schnorr identiﬁcation protocol is shown in Fig. 3.
5.3 Discussion
A straightforward solution realizing weak-unlinkability can be achieve by storing a user’s secret-keys and pseudonyms which are randomly chosen. In the

54–66 (Oct. 2010)

c 2010 Information Processing Society of Japan

64

An Identifiable Yet Unlinkable Authentication System in Multi-service Environment

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

Fig. 4 Estimation of transistor count.

straightforward solution, the amount of memory which a user needs is proportional to the number of services. While in our scheme, the amount of memory
does not depend on the number of services in exchange for two more hash computations than the straightforward solution. However, the computational timeof a hash function is almost much faster than that of an identiﬁcation protocol.
Hence we don’t have to consider the additional time.
Let ta (b) = h(0 a b) and ta (b) = h(1 a b). Assuming that the sets{ta }a∈{0,1}n and {ta }a∈{0,1}n are pseudorandom functions, the implementationof our authentication system satisﬁes impersonation resistance against insiders,weak-unlinkability, memory eﬃciency, and personalization.
We assume that both a pseudonym and a secret-key are 256 bit strings and thehash algorithm is AURORA-256 20) , which is a candidate for a new cryptographic
hash algorithm (SHA-3). We assume that a gate in the circuit of AURORA256 consists of 6 transistors and 1 bit memory cell consists of 1 transistor. A
speed-oriented implementation of AURORA-256 needs 35,016 gates 21) . Hence
we can estimate that the transistor count of a speed-oriented implementationof AURORA-256 is less than that of a table of 420 pairs of a pseudonym anda secret-key. The estimation is shown in Fig. 4. Our authentication system is

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3

more space eﬃcient than the straightforward solution if the number of service
providers is more than 420. We note that the transistor count of an area-oriented
implementation of AURORA is about one-quarter of that of the speed-oriented
implementation.
We describe the resistance of our system against a brute force attack. Herewe consider the following brute force attack: An adversary randomly chooses
a candidate of a user ID from the search space of user IDs. Then the adversary generates a pair of a pseudonym and a secret-key for a particular service
provider using the user ID and a cryptographic hash function. After that, theadversary repeatedly tries to authenticate with the service provider until the service provider accepts this try. In our system, we assume that the number of valid
user IDs (the number of users) is much less than the entire space of user IDs. In
this way we can prevent the brute force attack. For example, if the length of auser ID is 256 bit and the number of users is 1 million (about 220 ), the probability
that a valid user ID is chosen randomly is 1/2236 . The longer the length of user
IDs is, the smaller the probability that a valid user ID is chosen gets. Hence if
the length of user IDs is suﬃciently long, our system prevents such an attack
practically.

54–66 (Oct. 2010)

c 2010 Information Processing Society of Japan

65

An Identifiable Yet Unlinkable Authentication System in Multi-service Environment

6. Conclusions
In this paper we proposed an authentication system in multi-service environment which satisﬁes impersonation resistance, weak-unlinkability, memory efﬁciency, and personalization. Due to the use of pseudorandom functions, thememory requirement for each smart card is independent of the number of services. This is a remarkable advantage when a massive number of services utilize
the system. We showed an example of our system based on the Schnorr identiﬁcation scheme in which pseudorandom functions are replaced with collision-freehash functions.
Our future work includes implementing our system with smart cards and a PC
in order to measure the execution time and to compare it with that of otherrelated authentication systems.
References
1) Microsoft’s .NET Passport: http://www.passport.net/.
2) Shibboleth: http://shibboleth.internet2.edu/.
3) OpenID: http://openid.net/.
4) Alsaid, A. and Martin, D.: Detecting Web Bugs with Bugnosis: Privacy Advocacy
through Education, Privacy Enhancing Technologies (PET2003 ), LNCS, Vol.2482,
pp.27–31, Springer-Verlag (2003).
5) Gabber, E., Gibbons, P.B., Matias, Y. and Mayer, A.: How to Make Personalized
Web Browsing Simple, Secure, and Anonymous, Financial Cryptography, LNCS,
Vol.1318, pp.17–31, Springer-Verlag (1997).
6) Camenisch, J. and Lysyanskaya, A.: An Eﬃcient System for Non-transferable
Anonymous Credentials with Optional Anonymity Revocation, Advances in
Cryptology—EUROCRYPT 2001, LNCS, Vol.2045, pp.93–118, Springer-Verlag(2001).
7) Chaum, D. and van Heyst, E.: Group Signatures, Advances in Cryptology—
EUROCRYPT 1991, LNCS, Vol.547, pp.257–270, Springer-Verlag (1991).
8) VISA Corporate: http://corporate.visa.com/ media/visa-corporate-overview.pdf.
9) OpenIDeas, the JanRain Blog, July 1, 2009: http://blog.janrain.com/
2009 07 01 archive.html.
10) Goldreich, O.: Foundations of Cryptography, Cambridge University (2001).
11) Goldreich, O., Goldwasser, S. and Micali, S.: How to construct random functions,
J. ACM (JACM ), Vol.33, No.4, pp.792–807 (1986).
12) Juang, W.-S.: Eﬃcient multi-server password authenticated key agreement us-

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3

ing smart cards, IEEE Transactions on Consumer Electronics, Vol.50, pp.251–255(2004).
13) Hwang, R.-J. and Shiau, S.-H.: Provably Eﬃcient Authenticated Key Agreement
Protocol for Multi-Servers, Comput. J., Vol.50, pp.602–615 (2007).
14) Liao, Y.-P. and Wang, S.-S.: A secure dynamic ID based remote user authentication scheme for multi-server environment, Computer standards and interfaces,
Vol.31, No.1, pp.24–29 (2009).
15) OpenID.ee: https://openid.ee/en/.
16) SAML XML. org.: http://saml.xml.org/.
17) Schnorr, C.P.: Eﬃcient signature generation by smart cards, Journal of Cryptology,
Vol.4, No.3, pp.161–174, Springer New York (1991).
18) Bellare, M. and Palacio, A.: GQ and Schnorr Identiﬁcation Schemes: Proofs ofSecurity against Impersonation under Active and Concurrent Attacks, Advances in
Cryptology—CRYPTO 2002, LNCS, Springer-Verlag (2002).
19) National Institute of Standards and Technology (NIST): FIPS-180-2: Secure Hash
Standard, http://www.itl.nist.gov/ﬁpspubs/.
20) Iwata, T., Shibutani, K., Shirai, T., Moriai, S. and Akishita, T.: Aurora: A cryptographic hash algorithm family, Submission to NIST (2008).
21) AURORA: http://www.sony.net/Products/cryptography/aurora/?j-short=aurora.

54–66 (Oct. 2010)(Received February 4, 2010)(Revised March 28, 2010)(Accepted April 30, 2010)
Toru Nakamura is a Ph.D. candidate at Graduate School ofInformation Science and Electrical Engineering, Kyushu University. He received his B.E. and M.E. degrees in Computer Sciencefrom Kyushu University. His current research focuses on the security and privacy of authentication. He is a student member of
IPSJ and IEEE.

c 2010 Information Processing Society of Japan

66

An Identifiable Yet Unlinkable Authentication System in Multi-service Environment

Shunsuke Inenaga is an associate professor of Institute forAdvanced Study, Kyushu University, and is a research associate
professor of Graduate School of Information Science and Electrical Engineering, Kyushu University. He received his B.E. from
Kyushu Institute of Technology in 2000, and his M.S. and Ph.D.
in Science from Kyushu University in 2002 and 2003, respectively.
He became a research associate professor of Kyushu University in
2006, and an associate professor of Institute for Advanced Study, Kyushu University in 2009. His current research interests include stringology, algorithms anddata structures, and design and modeling of social information infrastructure.
He is a member of IPSJ and EATCS.
Daisuke Ikeda is an associate professor in Department of Informatics, Graduate School of Information Science and ElectricalEngineering, Kyushu University. He received his B.S., M.S. and
Ph.D. from Kyushu University in 1994, 1996, and 2004, respectively. He became an associate professor in Kyushu University in
2004. His current interests include data/text/Web mining, digital library, and academic communication infrastructure. He is amember of IPSJ, ACM, and EATCS.

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3

Kensuke Baba is an associate professor of Research and Development Division, Kyushu University Library. He received his
B.S. and M.S. degrees and his Ph.D. in Science from Kyushu University in 1996, 1998, and 2002, respectively. His current interests
include algorithms for string processing and formal analysis of security. He is a member of IEEE, EATCS, and IPSJ.

Hiroto Yasuura is a Executive Vice President of Kyushu University. He is also a professor of Department of Computer Science
and Communication Engineering, Graduate School of Information
Science and Electrical Engineering, and a member of System LSI
Research Center in Kyushu University. Prof. Yasuura received
his B.E., M.E. and Ph.D. degrees in computer science from Kyoto
University, Kyoto, Japan, in 1976, 1978, and 1983 respectively. He
was an associate professor in Kyoto University and moved to Kyushu University
in 1991.

54–66 (Oct. 2010)

c 2010 Information Processing Society of Japan