# Password based anonymous authentication with private information retrieval.

1. Introduction

1.1 Background and Motivations

Identity management technologies are getting more and more essential in our life. In particular, authentication plays an important role to prevent impersonation attacks. In the meantime, much attention has been paid to protecting users' privacy on identity management systems [10]. Indeed, due to increase of storage capacity and progress of data mining technologies, it is becoming easier for adversaries to analyze user's actions or preferences from the service logs related to the user.

In this paper, we consider authentication with three types of entities: a user who sends an authentication request, a service provider who receives and verifies the request, and a database who supplies the service provider with information for verifying the request. In particular, an authentication system, in which service providers and a database of identity information are separated, is focused on (for example, the OpenID system [1] which is a kind of single-sign-on system), since each user needs to register him/her in the system only once even in a multi-service environment, and since the risk of leakage of user-related information from a service provider is reduced. However, in most of authentication systems with three types of entities, a database can know who is trying to access to the service provider from his ID or pseudonym. The information who is trying to access may be privacy risk since they can easily analyze user's action or preference from the information.

This paper presents novel authentication protocols that satisfy the following important properties: (1) secure against replay-attacks, (2) the database cannot identify which user is authenticating (anonymity against database). A key idea of our authentication protocols is to use the private information retrieval (PIR) [8, 7, 11, 6] technologies. First, we show a protocol which satisfies Properties (2). Second, we show a protocol which satisfies Properties (1) and (2).

1.2 Private Information Retrieval

PIR technologies contribute for protecting privacy of a client (the service provider in our context) who makes a query to a database. Using a PIR scheme, the client can retrieve an element from the database without the index of the element being revealed to the database. A naive PIR scheme is that a database issues a copy of all elements of the database. The communication complexity of this scheme is O(n) for the number of elements of the database n. Chor et al. [8] proposed some effective solutions with multiple databases, called an information theoretic PIR. For example, if the number of databases k is 2, then the communication complexity of this scheme is O([n.sup.1/3]). Chor et al. [7] introduced the notion of a computational PIR and showed a construction of a computational PIR scheme whose communication complexity is O([n.sup.[epsilon]) for any [epsilon] > 0. Kushilevitz and Ostrovsky [11] proposed a computational PIR scheme which does not need the multiple replicated databases, called a single-database PIR, whose communication complexity is O([n.sup.[epsilon]]) for any [epsilon] > 0.

In order to lead a reader to understand, we show the very simple two-databases PIR scheme [8] as an example of the PIR scheme (although the scheme is not effective from the viewpoint of the communication complexity). Let the elements of database X be a n bit string [x.sub.1] ... [x.sub.n], and each database has the same X. We assume that the client wants to obtain the bit [x.sub.i] from each of two databases. The client selects a random set S [subset or equal to] {1, ..., n}. The client sends S to a database, and if i [not member of] S, then he sends S [union] {i} to the other database, otherwise, he sends S \ {i}. Each of these databases, if receiving the set I, replies a single bit which is the exclusive-or of the bits [X.sub.j] for any j [member of] I. The client exclusive-ors these answers, then the bit is [x.sub.i]. Clearly, none of the databases has obtained any information about the index, since each of databases obtains only a random set.

1.3 Related Work

It should be noted that there already exist authentication protocols based on PIR. Bringer et al. [4, 5] proposed biometric authentication protocols based on PIR. However, unfortunately their protocols do not satisfy Properties (1). Liao et al. [12] proposed a password-based anonymous authentication protocol. In this protocol, the service provider needs to secretly store some information to verify a given authentication request. On the other hand, in our protocols the service provider does not need to store such information.

1.4 Applications

In our authentication scheme a database cannot obtain users' identifiers. Hence our scheme is effective for systems with group authentication or attribute authentication. We show an example of applications. Our authentication scheme can be applied to age-verifying system for sales of cigarette or alcohol. For example, in Japan, as a part of the initiatives to prevent underage smoking, vending machines with an age-verification system based on smart cards were introduced in July 2008 [3]. However, the issuer stores not only personal information of users, but also the dates and locations of the users' cigarette purchases using their cards. Therefore, anxiety to privacy has risen since user's action history can be analyzed easily from such information. Applying our authentication scheme to this system, a user can prove that he is adult, while an issuer cannot obtain any information about the user.

1.5 Organization

In Section 2, we show a formal definition of PIR and introduce a simple PIR based authentication protocol which satisfies Property (2), anonymity against database. In Section 3, we show a PIR based authentication protocol using a challenge-response technique to prevent replay-attacks. The protocol satisfies Properties (1) and (2).

2. Authentication Protocol Anonymous against Database

In this section we propose a simple authentication protocol which is based on the idea of private information retrieval (PIR). The protocol has the following properties:

* the service provider does not need to store the passwords of the users, and

* the database cannot identify which user is authenticating with the service provider.

2.1 Notations

An interactive Turing machine (ITM) [9] is a Turing machine which has a pair of communication tapes in addition to an input tape, an output tape, and a work tape. One communication tape is read-only and the other is write-only. Then, a content on the read-only (also write-only) tape is said to be received (resp., sent) when it is read (resp., written).

A joint computation of two ITMs is a sequence of pairs of the local configurations (that is, the state, the contents of the tapes, and the locations of the heads) of the ITMs in the situation that: the ITMs have a common input tape; the read-only communication tape of one ITM is the write-only tape of the other ITM, and vice versa; and the configuration of one ITM is not modified when the configuration of the other ITM is modified, which is realized by a single bit for each ITM. The output of a joint computation is the output 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 Turing machines A and B, and by (A(y), B(z)) (x) its output on a common input x, a local input y for A, and a local input z for B. We sometimes omit the brackets if the input is empty. In the rest of this paper, we sometimes call a Turing machine A an "algorithm" A . [A.sub.u](x) denotes the output of a probabilistic algorithm A on an input x and random coins u which is always chosen uniformly. In the rest of paper, we sometimes omit the description of the random coins of the probabilistic algorithms. Let m and n be non-negative integers. If X and Y are random variables which are distributed over [{0,1}.sup.m],

Pr[X = Y][??] [summation over (x,y [member of] [{0,1}.sup.m])] Pr[X = x] x Pr[Y = y] x [chi] (x, y),

where [chi] is a predicate such that for any a,b [member of] [{0,1.sup.}m], [chi] (a,b) = 1 if a = b, and [chi](a,b) = 0 otherwise. If A is a probabilistic algorithm and X is a random variable which is distributed over [{0,1}.sup.m] ,

Pr[A(X) = Y][??] [summation over (x,y [member of] [{0,1}.sup.m])] Pr[X = x] x Pr[A(x)= y),

If A is a probabilistic algorithm, and X and Y are random variables which are independently distributed over [{0,1}.sup.m],

Pr[A(X) = Y][??] [summation over (x,y [member of] [{0,1}.sup.m])] Pr[X = x] x Pr[Y = y] x Pr[A(x) = y),

The idea of a joint computation of two ITMs can be extended straightforwardly to that of three ITMs by two pair of communication tapes. We denote by [T.sup.<A(x),B(y),C(z)>.sub.A] the sequence of contents which is written on the input tape and the communication tapes of A in the joint computation <A, B, C> on input x for A, y for B, and z for C. We denote by [T.sup.<A(x),B(y),C(z)>.sub.A] the sequence of contents which is written on the communication tapes between A and B in the joint computation (A, B, C) on input x for A, y for B, and z for C.

2.2 Security Requirements

We consider an authentication model which consists of the following three types of entities.

* User: Let n be the number of the users. Then, a user is denoted by [U.sub.i] for i [member of] [n] [??] {1, 2, ... ,n}. Each user [U.sub.i] is assigned the unique identifier i and has a password [w.sub.i][member of] [{0,1}.sup.m] for a natural number m.

* Service Provider: The service provider S verifies whether the entity who has sent an authentication request with identifier i is truly the user [U.sub.i].

* Database: The database D stores the sequence ([w.sub.t])t[member of][n] [??] ([w.sub.1], [w.sub.2], ..., [w.sub.n]) of the passwords of the users.

Throughout this paper, we assume that

* each user can communicate only with the service provider,

* the service provider can communicate with the users and the database,

* the database can communicate only with the service provider,

* the password of each user is shared by the user and the database, and

* the service provider has no password.

We define an authentication protocol as a joint computation (P, V, M). P takes a pair of an identifier i and a password candidate z [member of] [{0,1}.sup.m] as inputs, and M takes ([w.sub.t])t[member of][n] as an input.

We show the requirements of an authentication protocol in this section. p(k) denotes any polynomial of k.

--Correctness: A probabilistic polynomial-time joint Computation (P, V, M) has correctness if for any i [member of] [n] and any ([W.sub.t])t[member of][n] [member of] [([{0,1}.sup.m]).sup.n],

Pr[<P(i,[w.sub.i]),V,M[([w.sub.t]).sub.t[member of][n]]>=1] > 1/p(mn),

where the probability is taken over random coins of P, V, and M.

--Soundness: A probabilistic polynomial-time joint computation (P, V, M) has soundness if for any i [member of] [n], any [([w.sub.t]).sub.t[member of][n]] [member of] ([{0,1}.sup.m])n, and any z [not equal] [w.sub.i],

Pr[<P(i,z),V,M[([w.sub.t]).sub.t[member of][n]]>=1] < 1/p(mn),

where the probability is taken over random coins of P, V, and M.

--Anonymity against Database: A probabilistic polynomial-time joint computation (P, V, M) has anonymity against database if for any i, j [member of] [n], any [z.sub.1], [z.sub.2] [member of] [{0,1}.sup.m] , any ([w.sub.t]).sub.t[member of][n]] [member of] ([{0,1}.sup.m])n , any probabilistic polynomial-time algorithm B, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the probabilities are taken over the random coins of P, V, M and B.

2.3 Simple Authentication Protocol Based on PIR

In this subsection, we construct a simple authentication protocol based on the single-database PIR [11]. We show a definition of a single-database PIR based on the formulation in [6]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be non-negative integers, respectively.

[FIGURE 1 OMITTED]

Definition 1 A single-database PIR consists of the following three functions:

--a query function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

--an answer function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

--a reconstruction function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For an integer i and a string r of length [l.sub.r], [Que.sub.1](i, r) denotes the first element of Que(i, r). These functions satisfy the following requirements.

--For any [([x.sub.t]).sub.t[member of][n]] [member of] [([{0,1}.sup.m]).sup.n] and any i [member of] [n],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where the probability is taken over random variable R which is uniformly distributed over [{0,1}.sup.[[??].sub.r]].

--For any i,j [member of] [n], any probabilistic polynomial-time algorithmB, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

where the probabilities are taken over random variables [R.sub.1] and [R.sub.2] which are uniformly and independently distributed over [{0,1}.sup.[[??].sub.r]], and random coins of B.

Below we show a simple PIR based authentication protocol (P, V, M) on inputs (i,z) for P and [([w.sub.t]).sub.t[member of][n]] for M (see also Figure 1).

1. P sends a pair (i,z) to V.

2. V chooses r randomly and computes (q,s) [left arrow] Que(i,r). V sends q to M.

3. M computes a [left arrow] Ans([([w.sub.t]).sub.t[member of][n]],q) and sends a to V.

4. V computes [w.sub.i] [left arrow] Rcn(i,(q,s),a) and compares [w.sub.i] and z. If z = [w.sub.i], then V outputs 1, and 0 otherwise.

Theorem 1 The simple PIR based authentication protocol satisfies correctness and soundness.

proof: Clear by the definitions of correctness and soundness and Inequality (1) of Definition 1.

Theorem 2 The simple PIR based authentication protocol satisfies anonymity against database.

proof: Due to the property of the simple PIR based authentication protocol, for any i[member of][n], any z [member of] [{0,1}.sup.m], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We assume, for contrary, that the protocol does not have anonymity against database. By the definition of anonymity against database, there exists a probabilistic polynomial-time algorithm C such that for some i' j' [member of] [n], and some polynomial q(k) of k,

|Pr[C([1.sup.k], [Que.sub.1](i'[R.sub.1])) = 1]

- Pr[C([1.sup.k], [Que.sub.1](j', [R.sub.2]) = 1] |> [1]/[q(k)]

This contradicts to Inequality (2) in Definition 1.

We remark that the simple authentication protocol based on PIR has two disadvantages. One is that the password candidate z is transmitted in the communication channel in Step 1. Hence an adversary can impersonate the user [U.sub.i] if z = [w.sub.i] is eavesdropped by the adversary. This cannot be solved by encrypting or hashing the password candidate, since an adversary can impersonate the user by repeating the previous communication message to the service provider (replay attacks). The other is that the service provider S can obtain password [w.sub.i] in Step 4. This contributes to an increased risk of leakage of user's passwords.

3. Authentication Protocol Preventing Replay Attacks

In this section, we propose an authentication protocol based on PIR which prevents the service provider from obtaining a password, and prevents replay-attacks. We apply the idea of challenge-response to the simple authentication protocol in the previous section.

3.1 Password Protection and Security against Replay Attack

In addition to the requirements introduced in the previous section, we consider the following two requirements.

--Password Protection: A probabilistic polynomial-time joint computation (P, V, M) has password protection if for any i [member of] [n], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the probability is taken over the random coins of P, V, M, and B, and a sequence of random variables [([W.sub.t]).sub.t[member of][n]] each of which is uniformly and independently distributed over [{0,1}.sup.m].

--Security against Replay-attacks: A probabilistic polynomialtime joint computation (P, V, M) has security against replay-attacks if for any i [member of] [n], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the probability is taken over the random coins of P, V, M, and B, and a sequence of random variables [([W.sub.t]).sub.t[member of][n]] each of which is uniformly and independently distributed over [{0,1}.sup.m].

3.2 Challenge-Response Authentication Protocol Based on PIR

The authentication protocol which we propose in this section is based on a challenge-response authentication protocol like CRAMMD5 [2] which uses a cryptographic hash function. We assume that there exists an ideal hash function h : [{0,1}.sup.m] x [{0,1}.sup.m] [right arrow] [{0,1}.sup.m]which has the following properties.

--For any y [member of] [{0,1}.sup.m], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

Pr[B([1.sup.k],h(X,y)) = X] < [1]/[p(k)], (3)

where the probability is taken over a random variable X which is uniformly distributed over [{0,1}.sup.m], and random coins of B.

--For any probabilistic polynomial-time algorithm B, any [c.sub.1], [c.sub.2] [member of] [{0,1}.sup.m] such that [c.sub.1] [not equal to] [c.sub.2], and any sufficiently large k,

Pr[B([1.sup.k],h(X,[c.sub.1])) = h(X,[c.sub.2])] < [1]/[p(k)], (4)

where the probability is taken over a random variable X which is uniformly distributed over [{0,1}.sup.m] , and random coins of B.

We show a simple hash based challenge-response protocol (P, V)on inputs (i,z) for P and [([w.sub.t]).sub.t[member of][n]] for V. The protocol is as follows (see also Figure 2).

[FIGURE 2 OMITTED]

1. P sends i to V.

2. V chooses c [member of] [{0,1}.sup.m] randomly, and sends c to P as a challenge.

3. P computes h(z,c) and sends h(z,c) to V.

4. V computes h([w.sub.i],c), and if h(z,c) = h([w.sub.i],c), then V outputs 1, and 0 otherwise.

We construct PIR based challenge-response authentication protocol (P, V, M) on inputs (i,z) for P and [([w.sub.t]).sub.t[member of][n]] for M with single-database PIR and the previous challenge-response authentication protocol as follows (see also Figure 3).

[FIGURE 3 OMITTED]

1. P sends i to V.

2. V chooses r [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] randomly, and computes (q, s) [left arrow] Que(i, r). V sends (q, c) to M.

3. For each j [member of] [n], M computes h([w.sub.j], c). M computes [alpha] [left arrow] Ans((h[([w.sub.t],c)).sub.t][member of][n]],q), and sends [alpha] to V.

4. V computes h([w.sub.i],c) [left arrow] Rcn(i,(q,s),a).V sends c to P.

5. P computes h(z,c) and sends h(z,c) to V.

6. If h(z,c) = h([w.sub.i],c), then V outputs 1 and 0 otherwise.

Theorem 3 PIR based challenge-response authentication protocol has correctness, soundness, and anonymity against database.

proof: Correctness and soundness are clear. Anonymity against database can be proved in a similar way as the proof of Theorem 2.

Lemma 1 For any probabilistic polynomial-time algorithm B and any sufficiently large k,

Pr[B([1.sup.k],Y,h(X,Y)) = X] < 1/p(k),

where the probability is taken over a random variable X and Y which are uniformly distributed over [{0,1}.sup.m] , and random coins of B.

proof: First, we show a claim that for any y [member of] [{0,1}.sup.m], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

Pr[B([1.sup.k],y,h(X,y)) = X] < 1/p(k), (5)

where X is uniformly distributed over [{0,1}.sup.m]. We assume for contrary of the claim that there exists a probabilistic polynomial-time algorithm C such that for some y' [member of] [{0,1}.sup.m] and some polynomial q(k) of k,

Pr[B([1.sup.k],y',h(X,y')) = X] > 1/q(k), (6)

We derive contradiction by constructing a probabilistic polynomial-time algorithm D which takes [1.sup.k] and [alpha] [member of] [{0,1}.sup.m] as inputs and uses the algorithm C as a subroutine. D proceeds as follows.

1. D invokes C on inputs [1.sup.k], y', and [alpha].

2. D outputs C([1.sup.k], y', [alpha]).

By Inequality (6),

Pr[D([1.sup.k],h(X,y ))= X]

= Pr[C([1.sup.k],y',h(X,y')) = X] > 1/q(k).

This contradicts to Inequality (3), therefore Inequality (5) holds. By Inequality (5),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 4 PIR based challenge-response authentication protocol has password protection.

proof: Due to the property of PIR based challenge-response authentication protocol, for any i [member of] [n], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the probabilities are taken over random variables R and C which are uniformly and independently distributed over [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively, and a sequence of random variables [([w.sub.t]).sub.t[member of][n]] each of which is uniformly and independently distributed over [{0,1}.sup.m]. We assume for contrary that there exists a probabilistic polynomial-time algorithm C such that for some i' [member of] [n] and some polynomial q(k) of k,

Pr[C([1.sup.k],i', C, R,

Ans((h[([W.sub.t],C)).sub.t[member of][i]],[Que.sub.1](i' ,R))) = [W.sub.i']] > 1/q(k). (7)

We can construct a probabilistic polynomial-time algorithm D which takes [1.sup.k], [alpha] [member of] [{0,1}.sup.m], and [beta] [member of] [{0,1}.sup.m] as inputs and uses the algorithm C as a subroutine. D proceeds as follows.

1. D randomly chooses ([([w.sub.t]).sub.t[member of][n]] [member of] [([{0,1}.sup.m]).sup.n].

2. D computes [([w'.sub.t]).sub.t[member of][n]] so that if j [not equal to] i' [member of] [n], [w'.sub.j] = h([w.sub.j], [alpha]), and otherwise j = i', [w'.sub.j] = [beta].

3. D chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] randomly and computes (q,s) [left arrow] Que(i',r).

4. D computes [alpha] [left arrow] Ans([([w'.sub.t]).sub.t[member of][n]],q).

5. D invokes C on inputs [1.sup.k], i' , [alpha], r, [beta] and [alpha].

6. D outputs C([1.sup.k], i' , [alpha], r, [beta] Ans(([([w'.sub.t]).sub.t[member of][n]],q)). By Inequality (7),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This contradicts to Lemma 1.

Lemma 2 For any probabilistic polynomial-time algorithm B and any sufficiently large k,

Pr[B([1.sup.k],[C.sub.1],[C.sub.2],h(X,[C.sub.1])) = h(X,[C.sub.2])] < 1/p(k),

where the probability is taken over random variables X, [C.sub.1] and [C.sub.2] which are uniformly and independently distributed over [{0,1}.sup.m] and random coins of B.

proof: First, we show a claim that for any [c.sub.1], [c.sub.2] [member of] [{0,1}.sup.m] such that [c.sub.1] [not equal to] [c.sub.2], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

Pr[B([1.sup.k],[c.sub.1],[c.sub.2],h(X,[c.sub.1])) = h(X,[c.sub.2])] < 1/p(k), (8)

where X is uniformly distributed over [{0,1}.sup.m]. We assume for contrary of the claim that there exists a probabilistic polynomial-time algorithm C such that for some [c'.sub.1],[c'.sub.2] [member of] [{0,1}.sup.m] such that [c.sub.1] [not equal to] [c.sub.2] and some polynomial q1(k) of k,

Pr[B([1.sup.k],[c'.sub.1],[c'.sub.2],h(X,[c'.sub.1])) = h(X,[c.sub.2])] > 1/[q.sub.1](k). (9)

We derive contradiction by constructing a probabilistic polynomial-time algorithm D which takes [1.sup.k] and a [member of] [{0,1}.sup.m] as inputs and uses the algorithm C as a subroutine. D proceeds as follows.

1. D invokes C on inputs [1.sup.k] and [alpha].

2. D outputs C([1.sup.k], [c'.sub.1],[c'.sub.2], [alpha]). By Inequality (9),

Pr[D([1.sup.k], h(X, [c'.sub.1])) = h(X, [c'.sub.2])]

= Pr[C([1.sup.k], [c'.sub.1],[c'.sub.2],h(X, [c'.sub.1])) = h(X,[c'.sub.2])] > 1/[q.sub.1](k)]

This contradicts to Inequality (4), therefore Inequality (8) holds. By Inequality (8), for some polynomial [q.sub.2](k) of k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 5 PIR based challenge-response authentication protocol has security against replay-attack.

proof: Due to the property of PIR based challenge-response authentication protocol, for any i [member of] [n], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [C.sub.1] is uniformly and independently distributed over [{0,1}.sup.m] and a sequence of random variables [([W.sub.t]).sub.t[member of][n]] each of which is uniformly and independently distributed over [{0,1}.sup.m]. First, we consider any algorithm B which sends i to V in Step 1 of PIR based challenge-response authentication protocol, then receives [c.sub.2] from V in Step 4 and sends the output of B to V in Step 5. Then for any probabilistic polynomial-time algorithm [B.sub.1],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [C.sub.2] is uniformly and independently distributed over [{0,1}.sup.m] . We show a claim that for any i [member of] [n] , any probabilistic polynomial-time algorithm B1 , and any sufficiently large k,

Pr[[B.sub.1]([1.sup.k],i,[C.sub.1],[C.sub.2],h([W.sub.i],[C.sub.1])) = h([W.sub.i],[C.sub.2])] < 1/p(k). (11)

We assume that there exists a probabilistic polynomial-time algorithm C such that for some i [member of] [n] and some polynomial q(k) of k,

Pr[C([1.sup.k], i', [C.sub.1] [C.sub.2], h([W.sub.i'], [C.sub.1])) = h([W.sub.i], [C.sub.2])] > 1/q(k).

This contradicts to Lemma 2, therefore Inequality (11) holds. By Inequality (10), for any B which sends i to V in Step 1,

Pr[(B([1.sup.k], i, [C.sub.1], h([W.sub.i], [C.sub.1])),V,M([([W.sub.t]).sub.t[member of][n]])) = 1] < 1/p(k).

Next, we consider any algorithm B which sends j [member of] [n] such that j [not equal to] i to V in Step 1 of PIR based challenge-response authentication protocol,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [W.sub.j] is uniformly and independently distributed over [{0,1}.sup.m]. Similarly, we can show that

Pr[[B.sub.2]([1.sup.k],i,[C.sub.1],[C.sub.2],h([W.sub.i],[C.sub.1])) = h([W.sub.j],[C.sub.2])] < 1/p(k).

Consequently, PIR based challenge-response authentication protocol has security against replay-attack.

4. Conclusions and Future Work

In this paper, we proposed novel authentication protocols. First, we showed a protocol with a single database which satisfies correctness, soundness, anonymity against database. Second, we showed a protocol which satisfies password protection, and security against replay-attacks in addition to the previous properties. The key idea is to employ PIR in the core of authentication protocols.

Our future work is to construct an authentication protocol which satisfies anonymity against both a database and service providers. Our idea is to apply a publickey encryption scheme and a PIR in which the reconstruction function needs not the index as input to our authentication scheme in this paper. The sketch shows as follows. A user generates a query. The user encrypts the query in order to hide any information about the query to a service provider, and sends the encrypted query to the service provider. The service provider generates a random challenge, and sends the challenge and the received encrypted query to the database. The database decrypts the encrypted query, and computes and sends the service provider an answer in the same way as our protocol in this paper. Finally, the service provider reconstructs the password from the answer without the index.

Received: 29 September 2010, Revised 18 November 2010, Accepted 28 November 2010

5. Acknowledgments

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

References

[1] OpenID. http://openid.net/.

[2] RF[C.sub.2]195. http://tools.ietf.org/html/rf[c.sub.2]195.

[3] Taspo. http://www.taspo.jp/english/index.html.

[4] Bringer, J., Chabanne, H., Izabachene, M., Pointcheval, D., Tang, Q, Zimmer, S. (2007). An application of the Goldwasser-Micali cryptosystem to biometric authentication. In: Information Security and Privacy, 12th Australasian Conference, ACISP 2007, volume 4586 of LNCS, p. 96-106. Springer-Verlag.

[5] Bringer, J., Chabanne, H., Pointcheval, D., Tang, Q. (2007). Extended private information retrieval and its application in biometrics authentications. In: Cryptology and Network Security, 6th International Conference, CANS 2007, volume 4856 of LNCS, p. 175-193. Springer-Verlag.

[6]. Cachin, C., Micali, S., Stadler, M. (1999). Computationally private information retrieval with polylogarithmic communication. In: Advances in Cryptology - EUROCRYPT 99, volume 1592 of LNCS, p. 402-414. Springer- Verlag.

[7] Chor, B., Gilboa, N.(1997). Computationally private information retrieval. In: Annual ACM Symposium on Theory of Computing, p. 304-313. ACM.

[8]. Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M (1998). Private information retrieval. Journal of the ACM, 45. 965-982.

[9] Goldreich, O. (2001). Foundations of Cryptography. Cambridge University.

[10] Hansen, M. Schwartz, A., Cooper, A.(2008). Privacy-enhancing identity management, IEEE Security and Privacy, 3. 38-45.

[11] Kushilevitz, E., Ostrovsky, R. (1997). Replication is not needed: Single database, computationally - private information retrieval. In the 38th Annual Symposium on Foundations of Computer Science, p. 364-373.

[12] Liao, Y.-P., Wang, S.-S (2009). A secure dynamic ID based remote user authentication scheme for multiserver environment. Computer standards and interfaces, 31(1) 24-29.

Author Biographies

Toru Nakamura is a Ph.D. candidate at the Graduate School of Information Science and Electrical Engineering, Kyushu University. He received his B.E. and M.E. degrees in Computer Science from Kyushu University. His current research focuses on the security and privacy of authentication. He is a student member of IPSJ and IEEE.

Shunsuke Inenaga is a research associate professor of Kyushu University. He received his B.E. from Kyushu Institute of Technology in 2000, and his M.S. and Ph.D. from Kyushu University in 2002 and 2003, respectively. He was a pos-doc researcher of JST and of the University of Helsinki, in 2003 and 2004. He became a pos-doc of Kyoto University in 2005, and then a research fellow of JSPS. He became a research associate professor of Kyushu University in 2006. His current research interests include string processing algorithms, and design and modeling of social information infrastructure. He is a member of EATCS.

Daisuke Ikeda is an associate professor in the Department of Informatics, Graduate School of Information Science and Electrical Engineering, 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 a member of IPSJ, ACM, and EATCS.

Kensuke Baba is an associate professor of the 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 the 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.

Toru Nakamura (1), Shunsuke Inenaga (1), Daisuke Ikeda (1), Kensuke Baba (2), Hiroto Yasuura (1) (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, Japan baba@lib.kyushu-u.ac.jp

1.1 Background and Motivations

Identity management technologies are getting more and more essential in our life. In particular, authentication plays an important role to prevent impersonation attacks. In the meantime, much attention has been paid to protecting users' privacy on identity management systems [10]. Indeed, due to increase of storage capacity and progress of data mining technologies, it is becoming easier for adversaries to analyze user's actions or preferences from the service logs related to the user.

In this paper, we consider authentication with three types of entities: a user who sends an authentication request, a service provider who receives and verifies the request, and a database who supplies the service provider with information for verifying the request. In particular, an authentication system, in which service providers and a database of identity information are separated, is focused on (for example, the OpenID system [1] which is a kind of single-sign-on system), since each user needs to register him/her in the system only once even in a multi-service environment, and since the risk of leakage of user-related information from a service provider is reduced. However, in most of authentication systems with three types of entities, a database can know who is trying to access to the service provider from his ID or pseudonym. The information who is trying to access may be privacy risk since they can easily analyze user's action or preference from the information.

This paper presents novel authentication protocols that satisfy the following important properties: (1) secure against replay-attacks, (2) the database cannot identify which user is authenticating (anonymity against database). A key idea of our authentication protocols is to use the private information retrieval (PIR) [8, 7, 11, 6] technologies. First, we show a protocol which satisfies Properties (2). Second, we show a protocol which satisfies Properties (1) and (2).

1.2 Private Information Retrieval

PIR technologies contribute for protecting privacy of a client (the service provider in our context) who makes a query to a database. Using a PIR scheme, the client can retrieve an element from the database without the index of the element being revealed to the database. A naive PIR scheme is that a database issues a copy of all elements of the database. The communication complexity of this scheme is O(n) for the number of elements of the database n. Chor et al. [8] proposed some effective solutions with multiple databases, called an information theoretic PIR. For example, if the number of databases k is 2, then the communication complexity of this scheme is O([n.sup.1/3]). Chor et al. [7] introduced the notion of a computational PIR and showed a construction of a computational PIR scheme whose communication complexity is O([n.sup.[epsilon]) for any [epsilon] > 0. Kushilevitz and Ostrovsky [11] proposed a computational PIR scheme which does not need the multiple replicated databases, called a single-database PIR, whose communication complexity is O([n.sup.[epsilon]]) for any [epsilon] > 0.

In order to lead a reader to understand, we show the very simple two-databases PIR scheme [8] as an example of the PIR scheme (although the scheme is not effective from the viewpoint of the communication complexity). Let the elements of database X be a n bit string [x.sub.1] ... [x.sub.n], and each database has the same X. We assume that the client wants to obtain the bit [x.sub.i] from each of two databases. The client selects a random set S [subset or equal to] {1, ..., n}. The client sends S to a database, and if i [not member of] S, then he sends S [union] {i} to the other database, otherwise, he sends S \ {i}. Each of these databases, if receiving the set I, replies a single bit which is the exclusive-or of the bits [X.sub.j] for any j [member of] I. The client exclusive-ors these answers, then the bit is [x.sub.i]. Clearly, none of the databases has obtained any information about the index, since each of databases obtains only a random set.

1.3 Related Work

It should be noted that there already exist authentication protocols based on PIR. Bringer et al. [4, 5] proposed biometric authentication protocols based on PIR. However, unfortunately their protocols do not satisfy Properties (1). Liao et al. [12] proposed a password-based anonymous authentication protocol. In this protocol, the service provider needs to secretly store some information to verify a given authentication request. On the other hand, in our protocols the service provider does not need to store such information.

1.4 Applications

In our authentication scheme a database cannot obtain users' identifiers. Hence our scheme is effective for systems with group authentication or attribute authentication. We show an example of applications. Our authentication scheme can be applied to age-verifying system for sales of cigarette or alcohol. For example, in Japan, as a part of the initiatives to prevent underage smoking, vending machines with an age-verification system based on smart cards were introduced in July 2008 [3]. However, the issuer stores not only personal information of users, but also the dates and locations of the users' cigarette purchases using their cards. Therefore, anxiety to privacy has risen since user's action history can be analyzed easily from such information. Applying our authentication scheme to this system, a user can prove that he is adult, while an issuer cannot obtain any information about the user.

1.5 Organization

In Section 2, we show a formal definition of PIR and introduce a simple PIR based authentication protocol which satisfies Property (2), anonymity against database. In Section 3, we show a PIR based authentication protocol using a challenge-response technique to prevent replay-attacks. The protocol satisfies Properties (1) and (2).

2. Authentication Protocol Anonymous against Database

In this section we propose a simple authentication protocol which is based on the idea of private information retrieval (PIR). The protocol has the following properties:

* the service provider does not need to store the passwords of the users, and

* the database cannot identify which user is authenticating with the service provider.

2.1 Notations

An interactive Turing machine (ITM) [9] is a Turing machine which has a pair of communication tapes in addition to an input tape, an output tape, and a work tape. One communication tape is read-only and the other is write-only. Then, a content on the read-only (also write-only) tape is said to be received (resp., sent) when it is read (resp., written).

A joint computation of two ITMs is a sequence of pairs of the local configurations (that is, the state, the contents of the tapes, and the locations of the heads) of the ITMs in the situation that: the ITMs have a common input tape; the read-only communication tape of one ITM is the write-only tape of the other ITM, and vice versa; and the configuration of one ITM is not modified when the configuration of the other ITM is modified, which is realized by a single bit for each ITM. The output of a joint computation is the output 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 Turing machines A and B, and by (A(y), B(z)) (x) its output on a common input x, a local input y for A, and a local input z for B. We sometimes omit the brackets if the input is empty. In the rest of this paper, we sometimes call a Turing machine A an "algorithm" A . [A.sub.u](x) denotes the output of a probabilistic algorithm A on an input x and random coins u which is always chosen uniformly. In the rest of paper, we sometimes omit the description of the random coins of the probabilistic algorithms. Let m and n be non-negative integers. If X and Y are random variables which are distributed over [{0,1}.sup.m],

Pr[X = Y][??] [summation over (x,y [member of] [{0,1}.sup.m])] Pr[X = x] x Pr[Y = y] x [chi] (x, y),

where [chi] is a predicate such that for any a,b [member of] [{0,1.sup.}m], [chi] (a,b) = 1 if a = b, and [chi](a,b) = 0 otherwise. If A is a probabilistic algorithm and X is a random variable which is distributed over [{0,1}.sup.m] ,

Pr[A(X) = Y][??] [summation over (x,y [member of] [{0,1}.sup.m])] Pr[X = x] x Pr[A(x)= y),

If A is a probabilistic algorithm, and X and Y are random variables which are independently distributed over [{0,1}.sup.m],

Pr[A(X) = Y][??] [summation over (x,y [member of] [{0,1}.sup.m])] Pr[X = x] x Pr[Y = y] x Pr[A(x) = y),

The idea of a joint computation of two ITMs can be extended straightforwardly to that of three ITMs by two pair of communication tapes. We denote by [T.sup.<A(x),B(y),C(z)>.sub.A] the sequence of contents which is written on the input tape and the communication tapes of A in the joint computation <A, B, C> on input x for A, y for B, and z for C. We denote by [T.sup.<A(x),B(y),C(z)>.sub.A] the sequence of contents which is written on the communication tapes between A and B in the joint computation (A, B, C) on input x for A, y for B, and z for C.

2.2 Security Requirements

We consider an authentication model which consists of the following three types of entities.

* User: Let n be the number of the users. Then, a user is denoted by [U.sub.i] for i [member of] [n] [??] {1, 2, ... ,n}. Each user [U.sub.i] is assigned the unique identifier i and has a password [w.sub.i][member of] [{0,1}.sup.m] for a natural number m.

* Service Provider: The service provider S verifies whether the entity who has sent an authentication request with identifier i is truly the user [U.sub.i].

* Database: The database D stores the sequence ([w.sub.t])t[member of][n] [??] ([w.sub.1], [w.sub.2], ..., [w.sub.n]) of the passwords of the users.

Throughout this paper, we assume that

* each user can communicate only with the service provider,

* the service provider can communicate with the users and the database,

* the database can communicate only with the service provider,

* the password of each user is shared by the user and the database, and

* the service provider has no password.

We define an authentication protocol as a joint computation (P, V, M). P takes a pair of an identifier i and a password candidate z [member of] [{0,1}.sup.m] as inputs, and M takes ([w.sub.t])t[member of][n] as an input.

We show the requirements of an authentication protocol in this section. p(k) denotes any polynomial of k.

--Correctness: A probabilistic polynomial-time joint Computation (P, V, M) has correctness if for any i [member of] [n] and any ([W.sub.t])t[member of][n] [member of] [([{0,1}.sup.m]).sup.n],

Pr[<P(i,[w.sub.i]),V,M[([w.sub.t]).sub.t[member of][n]]>=1] > 1/p(mn),

where the probability is taken over random coins of P, V, and M.

--Soundness: A probabilistic polynomial-time joint computation (P, V, M) has soundness if for any i [member of] [n], any [([w.sub.t]).sub.t[member of][n]] [member of] ([{0,1}.sup.m])n, and any z [not equal] [w.sub.i],

Pr[<P(i,z),V,M[([w.sub.t]).sub.t[member of][n]]>=1] < 1/p(mn),

where the probability is taken over random coins of P, V, and M.

--Anonymity against Database: A probabilistic polynomial-time joint computation (P, V, M) has anonymity against database if for any i, j [member of] [n], any [z.sub.1], [z.sub.2] [member of] [{0,1}.sup.m] , any ([w.sub.t]).sub.t[member of][n]] [member of] ([{0,1}.sup.m])n , any probabilistic polynomial-time algorithm B, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the probabilities are taken over the random coins of P, V, M and B.

2.3 Simple Authentication Protocol Based on PIR

In this subsection, we construct a simple authentication protocol based on the single-database PIR [11]. We show a definition of a single-database PIR based on the formulation in [6]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be non-negative integers, respectively.

[FIGURE 1 OMITTED]

Definition 1 A single-database PIR consists of the following three functions:

--a query function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

--an answer function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

--a reconstruction function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For an integer i and a string r of length [l.sub.r], [Que.sub.1](i, r) denotes the first element of Que(i, r). These functions satisfy the following requirements.

--For any [([x.sub.t]).sub.t[member of][n]] [member of] [([{0,1}.sup.m]).sup.n] and any i [member of] [n],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where the probability is taken over random variable R which is uniformly distributed over [{0,1}.sup.[[??].sub.r]].

--For any i,j [member of] [n], any probabilistic polynomial-time algorithmB, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

where the probabilities are taken over random variables [R.sub.1] and [R.sub.2] which are uniformly and independently distributed over [{0,1}.sup.[[??].sub.r]], and random coins of B.

Below we show a simple PIR based authentication protocol (P, V, M) on inputs (i,z) for P and [([w.sub.t]).sub.t[member of][n]] for M (see also Figure 1).

1. P sends a pair (i,z) to V.

2. V chooses r randomly and computes (q,s) [left arrow] Que(i,r). V sends q to M.

3. M computes a [left arrow] Ans([([w.sub.t]).sub.t[member of][n]],q) and sends a to V.

4. V computes [w.sub.i] [left arrow] Rcn(i,(q,s),a) and compares [w.sub.i] and z. If z = [w.sub.i], then V outputs 1, and 0 otherwise.

Theorem 1 The simple PIR based authentication protocol satisfies correctness and soundness.

proof: Clear by the definitions of correctness and soundness and Inequality (1) of Definition 1.

Theorem 2 The simple PIR based authentication protocol satisfies anonymity against database.

proof: Due to the property of the simple PIR based authentication protocol, for any i[member of][n], any z [member of] [{0,1}.sup.m], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We assume, for contrary, that the protocol does not have anonymity against database. By the definition of anonymity against database, there exists a probabilistic polynomial-time algorithm C such that for some i' j' [member of] [n], and some polynomial q(k) of k,

|Pr[C([1.sup.k], [Que.sub.1](i'[R.sub.1])) = 1]

- Pr[C([1.sup.k], [Que.sub.1](j', [R.sub.2]) = 1] |> [1]/[q(k)]

This contradicts to Inequality (2) in Definition 1.

We remark that the simple authentication protocol based on PIR has two disadvantages. One is that the password candidate z is transmitted in the communication channel in Step 1. Hence an adversary can impersonate the user [U.sub.i] if z = [w.sub.i] is eavesdropped by the adversary. This cannot be solved by encrypting or hashing the password candidate, since an adversary can impersonate the user by repeating the previous communication message to the service provider (replay attacks). The other is that the service provider S can obtain password [w.sub.i] in Step 4. This contributes to an increased risk of leakage of user's passwords.

3. Authentication Protocol Preventing Replay Attacks

In this section, we propose an authentication protocol based on PIR which prevents the service provider from obtaining a password, and prevents replay-attacks. We apply the idea of challenge-response to the simple authentication protocol in the previous section.

3.1 Password Protection and Security against Replay Attack

In addition to the requirements introduced in the previous section, we consider the following two requirements.

--Password Protection: A probabilistic polynomial-time joint computation (P, V, M) has password protection if for any i [member of] [n], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the probability is taken over the random coins of P, V, M, and B, and a sequence of random variables [([W.sub.t]).sub.t[member of][n]] each of which is uniformly and independently distributed over [{0,1}.sup.m].

--Security against Replay-attacks: A probabilistic polynomialtime joint computation (P, V, M) has security against replay-attacks if for any i [member of] [n], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the probability is taken over the random coins of P, V, M, and B, and a sequence of random variables [([W.sub.t]).sub.t[member of][n]] each of which is uniformly and independently distributed over [{0,1}.sup.m].

3.2 Challenge-Response Authentication Protocol Based on PIR

The authentication protocol which we propose in this section is based on a challenge-response authentication protocol like CRAMMD5 [2] which uses a cryptographic hash function. We assume that there exists an ideal hash function h : [{0,1}.sup.m] x [{0,1}.sup.m] [right arrow] [{0,1}.sup.m]which has the following properties.

--For any y [member of] [{0,1}.sup.m], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

Pr[B([1.sup.k],h(X,y)) = X] < [1]/[p(k)], (3)

where the probability is taken over a random variable X which is uniformly distributed over [{0,1}.sup.m], and random coins of B.

--For any probabilistic polynomial-time algorithm B, any [c.sub.1], [c.sub.2] [member of] [{0,1}.sup.m] such that [c.sub.1] [not equal to] [c.sub.2], and any sufficiently large k,

Pr[B([1.sup.k],h(X,[c.sub.1])) = h(X,[c.sub.2])] < [1]/[p(k)], (4)

where the probability is taken over a random variable X which is uniformly distributed over [{0,1}.sup.m] , and random coins of B.

We show a simple hash based challenge-response protocol (P, V)on inputs (i,z) for P and [([w.sub.t]).sub.t[member of][n]] for V. The protocol is as follows (see also Figure 2).

[FIGURE 2 OMITTED]

1. P sends i to V.

2. V chooses c [member of] [{0,1}.sup.m] randomly, and sends c to P as a challenge.

3. P computes h(z,c) and sends h(z,c) to V.

4. V computes h([w.sub.i],c), and if h(z,c) = h([w.sub.i],c), then V outputs 1, and 0 otherwise.

We construct PIR based challenge-response authentication protocol (P, V, M) on inputs (i,z) for P and [([w.sub.t]).sub.t[member of][n]] for M with single-database PIR and the previous challenge-response authentication protocol as follows (see also Figure 3).

[FIGURE 3 OMITTED]

1. P sends i to V.

2. V chooses r [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] randomly, and computes (q, s) [left arrow] Que(i, r). V sends (q, c) to M.

3. For each j [member of] [n], M computes h([w.sub.j], c). M computes [alpha] [left arrow] Ans((h[([w.sub.t],c)).sub.t][member of][n]],q), and sends [alpha] to V.

4. V computes h([w.sub.i],c) [left arrow] Rcn(i,(q,s),a).V sends c to P.

5. P computes h(z,c) and sends h(z,c) to V.

6. If h(z,c) = h([w.sub.i],c), then V outputs 1 and 0 otherwise.

Theorem 3 PIR based challenge-response authentication protocol has correctness, soundness, and anonymity against database.

proof: Correctness and soundness are clear. Anonymity against database can be proved in a similar way as the proof of Theorem 2.

Lemma 1 For any probabilistic polynomial-time algorithm B and any sufficiently large k,

Pr[B([1.sup.k],Y,h(X,Y)) = X] < 1/p(k),

where the probability is taken over a random variable X and Y which are uniformly distributed over [{0,1}.sup.m] , and random coins of B.

proof: First, we show a claim that for any y [member of] [{0,1}.sup.m], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

Pr[B([1.sup.k],y,h(X,y)) = X] < 1/p(k), (5)

where X is uniformly distributed over [{0,1}.sup.m]. We assume for contrary of the claim that there exists a probabilistic polynomial-time algorithm C such that for some y' [member of] [{0,1}.sup.m] and some polynomial q(k) of k,

Pr[B([1.sup.k],y',h(X,y')) = X] > 1/q(k), (6)

We derive contradiction by constructing a probabilistic polynomial-time algorithm D which takes [1.sup.k] and [alpha] [member of] [{0,1}.sup.m] as inputs and uses the algorithm C as a subroutine. D proceeds as follows.

1. D invokes C on inputs [1.sup.k], y', and [alpha].

2. D outputs C([1.sup.k], y', [alpha]).

By Inequality (6),

Pr[D([1.sup.k],h(X,y ))= X]

= Pr[C([1.sup.k],y',h(X,y')) = X] > 1/q(k).

This contradicts to Inequality (3), therefore Inequality (5) holds. By Inequality (5),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 4 PIR based challenge-response authentication protocol has password protection.

proof: Due to the property of PIR based challenge-response authentication protocol, for any i [member of] [n], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the probabilities are taken over random variables R and C which are uniformly and independently distributed over [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively, and a sequence of random variables [([w.sub.t]).sub.t[member of][n]] each of which is uniformly and independently distributed over [{0,1}.sup.m]. We assume for contrary that there exists a probabilistic polynomial-time algorithm C such that for some i' [member of] [n] and some polynomial q(k) of k,

Pr[C([1.sup.k],i', C, R,

Ans((h[([W.sub.t],C)).sub.t[member of][i]],[Que.sub.1](i' ,R))) = [W.sub.i']] > 1/q(k). (7)

We can construct a probabilistic polynomial-time algorithm D which takes [1.sup.k], [alpha] [member of] [{0,1}.sup.m], and [beta] [member of] [{0,1}.sup.m] as inputs and uses the algorithm C as a subroutine. D proceeds as follows.

1. D randomly chooses ([([w.sub.t]).sub.t[member of][n]] [member of] [([{0,1}.sup.m]).sup.n].

2. D computes [([w'.sub.t]).sub.t[member of][n]] so that if j [not equal to] i' [member of] [n], [w'.sub.j] = h([w.sub.j], [alpha]), and otherwise j = i', [w'.sub.j] = [beta].

3. D chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] randomly and computes (q,s) [left arrow] Que(i',r).

4. D computes [alpha] [left arrow] Ans([([w'.sub.t]).sub.t[member of][n]],q).

5. D invokes C on inputs [1.sup.k], i' , [alpha], r, [beta] and [alpha].

6. D outputs C([1.sup.k], i' , [alpha], r, [beta] Ans(([([w'.sub.t]).sub.t[member of][n]],q)). By Inequality (7),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This contradicts to Lemma 1.

Lemma 2 For any probabilistic polynomial-time algorithm B and any sufficiently large k,

Pr[B([1.sup.k],[C.sub.1],[C.sub.2],h(X,[C.sub.1])) = h(X,[C.sub.2])] < 1/p(k),

where the probability is taken over random variables X, [C.sub.1] and [C.sub.2] which are uniformly and independently distributed over [{0,1}.sup.m] and random coins of B.

proof: First, we show a claim that for any [c.sub.1], [c.sub.2] [member of] [{0,1}.sup.m] such that [c.sub.1] [not equal to] [c.sub.2], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

Pr[B([1.sup.k],[c.sub.1],[c.sub.2],h(X,[c.sub.1])) = h(X,[c.sub.2])] < 1/p(k), (8)

where X is uniformly distributed over [{0,1}.sup.m]. We assume for contrary of the claim that there exists a probabilistic polynomial-time algorithm C such that for some [c'.sub.1],[c'.sub.2] [member of] [{0,1}.sup.m] such that [c.sub.1] [not equal to] [c.sub.2] and some polynomial q1(k) of k,

Pr[B([1.sup.k],[c'.sub.1],[c'.sub.2],h(X,[c'.sub.1])) = h(X,[c.sub.2])] > 1/[q.sub.1](k). (9)

We derive contradiction by constructing a probabilistic polynomial-time algorithm D which takes [1.sup.k] and a [member of] [{0,1}.sup.m] as inputs and uses the algorithm C as a subroutine. D proceeds as follows.

1. D invokes C on inputs [1.sup.k] and [alpha].

2. D outputs C([1.sup.k], [c'.sub.1],[c'.sub.2], [alpha]). By Inequality (9),

Pr[D([1.sup.k], h(X, [c'.sub.1])) = h(X, [c'.sub.2])]

= Pr[C([1.sup.k], [c'.sub.1],[c'.sub.2],h(X, [c'.sub.1])) = h(X,[c'.sub.2])] > 1/[q.sub.1](k)]

This contradicts to Inequality (4), therefore Inequality (8) holds. By Inequality (8), for some polynomial [q.sub.2](k) of k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 5 PIR based challenge-response authentication protocol has security against replay-attack.

proof: Due to the property of PIR based challenge-response authentication protocol, for any i [member of] [n], any probabilistic polynomial-time algorithm B, and any sufficiently large k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [C.sub.1] is uniformly and independently distributed over [{0,1}.sup.m] and a sequence of random variables [([W.sub.t]).sub.t[member of][n]] each of which is uniformly and independently distributed over [{0,1}.sup.m]. First, we consider any algorithm B which sends i to V in Step 1 of PIR based challenge-response authentication protocol, then receives [c.sub.2] from V in Step 4 and sends the output of B to V in Step 5. Then for any probabilistic polynomial-time algorithm [B.sub.1],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [C.sub.2] is uniformly and independently distributed over [{0,1}.sup.m] . We show a claim that for any i [member of] [n] , any probabilistic polynomial-time algorithm B1 , and any sufficiently large k,

Pr[[B.sub.1]([1.sup.k],i,[C.sub.1],[C.sub.2],h([W.sub.i],[C.sub.1])) = h([W.sub.i],[C.sub.2])] < 1/p(k). (11)

We assume that there exists a probabilistic polynomial-time algorithm C such that for some i [member of] [n] and some polynomial q(k) of k,

Pr[C([1.sup.k], i', [C.sub.1] [C.sub.2], h([W.sub.i'], [C.sub.1])) = h([W.sub.i], [C.sub.2])] > 1/q(k).

This contradicts to Lemma 2, therefore Inequality (11) holds. By Inequality (10), for any B which sends i to V in Step 1,

Pr[(B([1.sup.k], i, [C.sub.1], h([W.sub.i], [C.sub.1])),V,M([([W.sub.t]).sub.t[member of][n]])) = 1] < 1/p(k).

Next, we consider any algorithm B which sends j [member of] [n] such that j [not equal to] i to V in Step 1 of PIR based challenge-response authentication protocol,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [W.sub.j] is uniformly and independently distributed over [{0,1}.sup.m]. Similarly, we can show that

Pr[[B.sub.2]([1.sup.k],i,[C.sub.1],[C.sub.2],h([W.sub.i],[C.sub.1])) = h([W.sub.j],[C.sub.2])] < 1/p(k).

Consequently, PIR based challenge-response authentication protocol has security against replay-attack.

4. Conclusions and Future Work

In this paper, we proposed novel authentication protocols. First, we showed a protocol with a single database which satisfies correctness, soundness, anonymity against database. Second, we showed a protocol which satisfies password protection, and security against replay-attacks in addition to the previous properties. The key idea is to employ PIR in the core of authentication protocols.

Our future work is to construct an authentication protocol which satisfies anonymity against both a database and service providers. Our idea is to apply a publickey encryption scheme and a PIR in which the reconstruction function needs not the index as input to our authentication scheme in this paper. The sketch shows as follows. A user generates a query. The user encrypts the query in order to hide any information about the query to a service provider, and sends the encrypted query to the service provider. The service provider generates a random challenge, and sends the challenge and the received encrypted query to the database. The database decrypts the encrypted query, and computes and sends the service provider an answer in the same way as our protocol in this paper. Finally, the service provider reconstructs the password from the answer without the index.

Received: 29 September 2010, Revised 18 November 2010, Accepted 28 November 2010

5. Acknowledgments

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

References

[1] OpenID. http://openid.net/.

[2] RF[C.sub.2]195. http://tools.ietf.org/html/rf[c.sub.2]195.

[3] Taspo. http://www.taspo.jp/english/index.html.

[4] Bringer, J., Chabanne, H., Izabachene, M., Pointcheval, D., Tang, Q, Zimmer, S. (2007). An application of the Goldwasser-Micali cryptosystem to biometric authentication. In: Information Security and Privacy, 12th Australasian Conference, ACISP 2007, volume 4586 of LNCS, p. 96-106. Springer-Verlag.

[5] Bringer, J., Chabanne, H., Pointcheval, D., Tang, Q. (2007). Extended private information retrieval and its application in biometrics authentications. In: Cryptology and Network Security, 6th International Conference, CANS 2007, volume 4856 of LNCS, p. 175-193. Springer-Verlag.

[6]. Cachin, C., Micali, S., Stadler, M. (1999). Computationally private information retrieval with polylogarithmic communication. In: Advances in Cryptology - EUROCRYPT 99, volume 1592 of LNCS, p. 402-414. Springer- Verlag.

[7] Chor, B., Gilboa, N.(1997). Computationally private information retrieval. In: Annual ACM Symposium on Theory of Computing, p. 304-313. ACM.

[8]. Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M (1998). Private information retrieval. Journal of the ACM, 45. 965-982.

[9] Goldreich, O. (2001). Foundations of Cryptography. Cambridge University.

[10] Hansen, M. Schwartz, A., Cooper, A.(2008). Privacy-enhancing identity management, IEEE Security and Privacy, 3. 38-45.

[11] Kushilevitz, E., Ostrovsky, R. (1997). Replication is not needed: Single database, computationally - private information retrieval. In the 38th Annual Symposium on Foundations of Computer Science, p. 364-373.

[12] Liao, Y.-P., Wang, S.-S (2009). A secure dynamic ID based remote user authentication scheme for multiserver environment. Computer standards and interfaces, 31(1) 24-29.

Author Biographies

Toru Nakamura is a Ph.D. candidate at the Graduate School of Information Science and Electrical Engineering, Kyushu University. He received his B.E. and M.E. degrees in Computer Science from Kyushu University. His current research focuses on the security and privacy of authentication. He is a student member of IPSJ and IEEE.

Shunsuke Inenaga is a research associate professor of Kyushu University. He received his B.E. from Kyushu Institute of Technology in 2000, and his M.S. and Ph.D. from Kyushu University in 2002 and 2003, respectively. He was a pos-doc researcher of JST and of the University of Helsinki, in 2003 and 2004. He became a pos-doc of Kyoto University in 2005, and then a research fellow of JSPS. He became a research associate professor of Kyushu University in 2006. His current research interests include string processing algorithms, and design and modeling of social information infrastructure. He is a member of EATCS.

Daisuke Ikeda is an associate professor in the Department of Informatics, Graduate School of Information Science and Electrical Engineering, 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 a member of IPSJ, ACM, and EATCS.

Kensuke Baba is an associate professor of the 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 the 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.

Toru Nakamura (1), Shunsuke Inenaga (1), Daisuke Ikeda (1), Kensuke Baba (2), Hiroto Yasuura (1) (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, Japan baba@lib.kyushu-u.ac.jp

Printer friendly Cite/link Email Feedback | |

Author: | Nakamura, Toru; Inenaga, Shunsuke; Ikeda, Daisuke; Baba, Kensuke; Yasuura, Hiroto |
---|---|

Publication: | Journal of Digital Information Management |

Article Type: | Report |

Date: | Apr 1, 2011 |

Words: | 5689 |

Previous Article: | Elementary patterns for converting textual and visual formalisms based on set theory and ORM. |

Next Article: | Taxonomy-based document clustering. |

Topics: |