Anonymous Authentication Systems Based on Private Information Retrieval
Toru Nakamura Shunsuke Inenaga Daisuke Ikeda Kensuke Baba Hiroto Yasuura
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 baba@ait.kyushu-u.ac.jp

Abstract
This paper focuses on authentication with three types ofentities: a user who sends an authentication request, anauthentication-server who receives and verifies the request,
and a database who supplies the authentication-server withinformation for verifying the request. This paper presents
novel authentication protocols that satisfy the following important properties: (1) secure against replay attacks, (2)the database(s) cannot identify which user is authenticatingand (3) the authentication-server cannot identify to whichuser a given authentication-request corresponds. Firstly,
we show a protocol with a single database which satisfies Properties (1) and (2). Secondly, we show a protocol
with multiple databases which satisfies Properties (1), (2)and (3). A key idea of our authentication protocols is touse private information retrieval (PIR) [Chor et al. J. ACM,
1998].

1system only once even in a multi-service environment, andsince the risk of leakage of user-related information from anauthentication-server is reduced.
This paper presents novel authentication protocols thatsatisfy the following important properties: (1) secureagainst replay-attacks, (2) the database(s) cannot identify which user is authenticating (anonymity against the
database(s)), and (3) the authentication-server cannot identify to which user a given authentication-request corresponds (anonymity against the authentication-server).
Firstly, we show a protocol with a single database which
satisfies Properties (1) and (2). Secondly, we show a protocol with multiple databases which satisfies Properties (1),(2) and (3).
A key idea of our authentication protocols is to use theprivate information retrieval (PIR) [8] technologies. Using the PIR technologies, a client (the authentication-serverin our context) can retrieve a data string from a database
without the index of the data string being revealed to the
database.

Introduction
Related Work

Identity management technologies are getting more andmore essential in our life. In particular, authentication plays
an important role to prevent impersonation attacks. In themeantime, much attention has been paid to protecting users’
privacy on identity management systems [10]. Indeed, due
to increase of data storage available and progress of data
mining technologies, it is becoming easier for adversaries toanalyze user’s actions or preferences from e.g., the service
logs related to the user.
In this paper, we focus on authentication with three typesof entities: a user who sends an authentication request, anauthentication-server who receives and verifies the request,
and a database who supplies the authentication-server withinformation for verifying the request. These types of systems are recently becoming more and more popular (e.g.,the OpenID system [1] which is a kind of single-sign-on
system), since each user needs to register him/her in the

It should be noted that there already exist authentication protocols based on PIR. Bringer et al. [3, 4] proposed
biometric authentication protocols based on PIR. However,
unfortunately their protocols do not satisfy Properties (1)and (3).
It is known that authentication protocols based on anonymous credentials [6] or group signatures [7] also satisfy
Properties (2) and (3). A merit of these protocols is that theauthentication-server does not need to communicate withthe manager (the database in our context) when verifying
a given authentication request. However, a revocation of agroup member in these schemes is known to be difficult due
to the anonymity. Still, it is easy to revoke a user in oursimple password-based authentication protocols.
Liao et al. [12] proposed a password-based anonymous
authentication protocol. In this protocol, the authentication-

server needs to secretly store some information to verify
a given authentication request. On the other hand, in our
protocols the authentication-server does not need to store
such information.

2

PIR Based Authentication

In this section we propose a simple authentication protocol that is based on private information retrieval (PIR). The
simple protocol has properties that

• Correctness: If z = pi , then the probability that theuser Ui is rejected by the authentication-server S is
negligible.
• Soundness: If z = pi , then the probability that the user
Ui is accepted by authentication-server S is negligible.
• Anonymity against Database: It is hard for the
database D to compute any information about the identifier i from any information that D obtains in the authentication protocol.

• the authentication-server does not need not to store a
set of passwords of users, and2.2• the database cannot identify which user is authenticating with the authentication-server.

In this subsection, we construct a simple authentication
protocol based on the single-database PIR [11]. We show
a formal definition of a single-database PIR protocol basedon the formulation in [5].
Let n be the number of data stored in the database. Let
r , q , s , a be any non-negative integers. Let m > 2n be
the length of a password pi . Let poly(·) denote any polynomial.

2.1

Security Requirements

We consider an authentication protocol which consists ofthe three following types of entities:• Users: A user Ui is assigned a unique identifier i ∈def[n] = {1, 2, ..., n} and has a password pi ∈ {0, 1}m .
• Authentication-Server: An authentication-server S
verifies whether or not an entity who has sent an authentication request with identifier i is truly user Ui .
• Databases: A database D stores a set P{p1 , p2 , ..., pn } of passwords of users.

=

only

with

Definition 1 A single-database PIR for consists of the following three functions:• Query function Q : [n] × {0, 1}r → {0, 1}q ×{0, 1}s ;• Answer function A : ({0, 1}m )n × {0, 1}q →{0, 1}a ;• Reconstruction function R : [n]×{0, 1}q ×{0, 1}s ×{0, 1}a → {0, 1}m .

Throughout this paper, we assume that• each user can communicate
authentication-server,

Simple Authentication Protocol Based on PIRthe• the authentication-server can communicate with bothusers and databases,• each database can communicate only with theauthentication-server,• the password of each user is shared by the user and a
database, and• the authentication-server have no passwords.
Although this paper only considers protocols with a single authentication-server, it is rather straightforward to apply our protocols to multiple service environments.
In what follows, we regard each user Ui , theauthentication-server S, and a database D as interactive algorithms. A user Ui takes a pair of an identifier i and apassword candidate z as input, and a database D takes P as
auxiliary input.
It is important for an authentication protocol to satisfy
the following requirements:

For integer i and string r of length r , let Q1 (i, r ) denotes the first element q of the output (q, s) = Q(i, r).
These functions satisfy the following requirements:• For any set X = {xi | 1 ≤ i ≤ n, xi ∈ {0, 1}m } andany i ∈ [n],Pr[R(i, Q(i, r), A(X, Q1 (i, r))) = xi ]1>1−poly(log n + q + s + a )(1)

where the probability is taken over uniformly chosenr ∈ {0, 1}r .
• For any i, j ∈ [n], any probabilistic polynomial-timealgorithm B, and sufficiently large w,| Pr[B(1w , Q1 (i, r)) = 1]
− Pr[B(1w , Q1 (j, r )) = 1]| <1,poly(w)where the probabilities are taken over uniformly andindependently chosen r, r ∈ {0, 1}r and random
coins of B.

Below we show a simple authentication protocol basedon PIR (see also Figure 1).
1. Ui sends a pair of an identifier i and a password candidate z to S as an authentication request.
2. S chooses r randomly and computes (q, s) ← Q(i, r).
S sends q to D.
3. D computes a ← A(P, q) and sends a to S.
4. S computes pi ← R(i, (q, s), a) and compares pi andz. If z = pi , then S outputs 1, otherwise, S outputs 0.

We remark that the simple authentication protocol basedon PIR has two disadvantages: One is that the password
candidate z is transmitted in the communication channelin Step 1. Hence an adversary can impersonate the user
Ui if z = pi is eavesdropped by the adversary. This cannot be solved by simply encrypting or hashing the password candidate, since an adversary can impersonate the user
by repeating the previous communication transcript to theauthentication-server (replay attacks). The other is that theauthentication-server S can obtain password pi in Step 4.
This contributes to an increased risk of leakage of user’s
passwords.
In the following sections, we will show authentication
protocols that solve the above difficulties.

3

Authentication Protocol Preventing Replay
Attacks

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

3.1

Figure 1. Simple authentication protocol
based on PIR.

Theorem 1 The simple authentication protocol based on
PIR satisfies correctness and soundness.
proof: Due to Inequality (1) of Definition 1, the probability
that S does not receive password pi from the database D isnegligible. Now assume S has successfully received pi . Ifz = pi , then the probability that Ui is rejected by S is negligible. If z = pi , then the probability that Ui is accepted by
S is negligible. Therefore, the simple authentication protocol based on PIR has correctness and soundness.
2
Theorem 2 The simple authentication protocol based on
PIR satisfies anonymity against database.
proof: Note that q = Q1 (i, r) is all the information related
to i that D can obtain in the above protocol. By Definition 1,
it is hard for any polynomial-time algorithms to computeany information about i from q. Hence the protocol has
anonymity against database.
2

Password Protection and Security against
Replay-Attack

In addition to the requirements introduced in the previous section, we consider the two following requirements.
• Password Protection : it is hard for the authenticationserver S to compute the user’s password pi from any
information that S obtains in the authentication protocol.
• Security against Replay-attacks: it is hard for any adversary who can obtain transcripts of previous communication between Ui and S to be accepted by S.

3.2

Challenge-Response Authentication Protocol

Our protocol is based on a challenge-response authentication protocol like CRAM-MD5 [2], which uses a cryptographic hash function. We assume that there exists an ideal
hash function such that• it is hard to guess the input from an output (onewayness),• it is hard to find two inputs that hash to the same output(collision resistance), and• it is hard to distinguish whether an outputs from thehash function or from true random function (pseudorandomness).

Readers are referred to e.g. [9] for formal definitions of theabove properties.
Let H : {0, 1}∗ → {0, 1}m be an ideal hash function.
We denote a concatenation of any strings a and b by a  b.
We can construct a challenge-response authentication
protocol with a single-server PIR and an ideal hash function, as follows (see also Figure 2).
1. Ui sends an identifier i to S.
2. S chooses r, r randomly and independently, and computes (q, s) ← Q(i, r). S sends (q, r ) to D.
3. For every 1 ≤ j ≤ n, D computes pj ← H(pj r ), and let P  = {p1 , p2 , ..., pn }. D computes a ←A(P  , q), and sends a to S.
4.

S computes pi ← R(i, r, (q, s), a) = H(pi  r ).
sends r to Ui .

S

5. Ui computes z  ← H(z  r ), where z is a password
candidate, and sends z  to S.
6. If z  = pi , then S outputs 1, otherwise, S outputs 0.

(Anonymity against Database) In the above protocol,
database D obtains {q, r } such that q = Q1 (i, r). Sincer is random value, r clearly includes no information abouti. By Definition 1, it is hard for any polynomial-time algorithms to compute any information about i from q. Thus the
protocol has anonymity against database.
(Password Protection) The authentication-server S obtains{i, a, pi , z  } such that pi = H(pi  r ) and z  = H(z r ). The value i is independent of both pi and z. Since
q = Q1 (i, r) and H is a one-way hash function, it is hard tocompute pi from a = A(P  , q). Due to the one-wayness offunction H, the probability that S succeeds in computing pi(or z) from pi (or z  ) is negligible. Therefore the protocol
has the property of password protection.
(Security against Replay-attacks) Transcripts of a previous
communication between Ui and S is {i, r , z  }. The probability that any adversary succeeds in computing z fromz  is negligible, since H has one-wayness and pseudorandomness. Similarly, it is hard for any adversary to compute H(z  r ) from H(z  r ) with a fresh random
value r with r = r . Therefore, the protocol has security against replay-attack.
2

4

Authentication
ProtocolAnonymous
against Authentication-Server

In this section, we propose an authentication protocol
based on PIR in which a user does not have to send his
identifier to the authentication-server. Hence can neither theauthentication-server or the databases identify which usercorresponds to a given authentication-request.

4.1
Figure 2. Challenge-Response Authentication
Protocol Based on PIR.

Theorem 3 The challenge-response authentication protocol based on PIR satisfies correctness, soundness,anonymity against database, password protection, and security against replay-attack.
proof: (Correctness and soundness) Due to Inequality (1)of Definition 1, the probability that S does not receive password pi from the database D is negligible. Now assume
S has successfully received pi . If z = pi , then clearlyH(z  r ) = H(pi  r ). Hence, if z = pi , then the probability that Ui is rejected by S is negligible, and if z = pi ,then the probability that Ui is accepted by S is negligible.

Anonymity against Authentication-Server

In addition to the four requirements shown in the previous sections, we consider the following requirement.
• Anonymity against Authentication-Server : It is hardfor the authentication-server S to compute any information about the identifier i from any information that
S obtains in the authentication protocol.

4.2

PIR with Reconstruction Function Not Taking
Identifier as Input

In the single-database PIR of Definition 1, the reconstruction function takes an index of a data string as an input
to reconstruct the corresponding data string. In this section, we use an information theoretical PIR protocol of [8]in which the reconstruction function does not take as input
an index of a data string. In the information theoretical PIR,
there are k database-servers which have the same copies ofthe database.

Definition 2 An information theoretical k-database PIR
without identifiers in reconstruction consists of the following three functions:

1. Ui chooses r randomly. For every 1 ≤ d ≤ k, Ui
computes qd ← Qd (i, r) and qd ← E(pk, qd ) as anauthentication request. Ui sends (q1 , ..., qk ) to S.

• k Query function Q1 , ..., Qk : [n] × {0, 1}r →{0, 1}q ;2. S chooses r randomly. For every 1 ≤ e ≤ k, S sends(qe , r ) to De .

• Answer function A : ({0, 1}m )n × {0, 1}q →{0, 1}a ;• Reconstruction function R : ({0, 1}a )k → {0, 1}m .
These functions satisfy the following requirements:

3. De computes qe ← T (sk, qe ). For every 1 ≤ j ≤ n,
De computes pj ← H(pj  r ), and let P  ={p1 , p2 , ..., pn }. De computes ae ← A(P  , qe ) andsends ae to S.
4. S computes pi ← R(a1 , ..., an ) = H(pi  r ). S
sends r to Ui .

• For any set X = {xi | 1 ≤ i ≤ n, xi ∈ {0, 1}m } andany i ∈ [n],5. Ui computes z  ← H(z  r ), where z is a password
candidate, and sends z  to S.

R(A(X, Q1 (i, r)), . . . , A(X, Qk (i, r))) = xi .

6. If z  = pi , then S outputs 1, otherwise, S outputs 0.

• For any i, j ∈ [n], any t ∈ [k], and for any q ∈ {0, 1}q
Pr[Qt (i, r)) = q] = Pr[Qt (j, r )) = q],
where the probabilities are taken over uniformly andindependently chosen r, r ∈ {0, 1}r .
• For any i, j ∈ [n] and for any x ∈ {0, 1}m ,Pr[R(A(X, Q1 (i, r)), . . . , A(X, Qk (i, r))) = x]
= Pr[R(A(X, Q1 (j, r)), . . . , A(X, Qk (j, r))) = x],where the probabilities are taken over uniformly andindependently chosen r, r ∈ {0, 1}r .

4.3

Authentication Protocol Anonymous against
Authentication-Server

The key idea of our authentication protocol is to use apublic key encryption scheme. A public key encryption
scheme consists of a triple of algorithms, key generation
algorithm K, encryption algorithm E, and decryption algorithm T , satisfies following properties:• For any α ∈ {0, 1}∗ , T (sk, E(pk, α)) = α, where(pk, sk) ← K(1y ) (y is a security parameter),• Semantic secure [9] (we omit a formal definition ofthis property).
In our protocol, we assume that a pair (pk, sk) is precomputed, and all users have obtained pk, and a manager
has stored sk secretly.
Our authentication protocol which realizes anonymity
against the authentication-server is as follows (see also Figure 3).

Figure 3. PIR-Based Authentication Protocol
Anonymous against Authentication-Server.

Theorem 4 The proposed protocol satisfies correctness,soundness, password protection, security against replayattacks, anonymity against databases, and anonymity
against authentication-server.
proof: (Correctness and Soundness) Since we use a public
key encryption scheme, every database De can obtain qe . It
follows from Definition 2 that S can obtain pi . It is clearthat H(z  r ) = H(pi  r ) if z = pi . Hence, if z = pi ,then Ui is accepted by S, and if z = pi , then Ui is rejectedby S. Therefore, the protocol has correctness and soundness.
(Password Protection and Security against Replay-attacks)
These can be shown similarly to Theorem 3 of Section 3.2.
(Anonymity against Database-Servers) In the proposed protocol, each De obtains {qe , r } such that qe = Qe (i, r).

Since r is a random value, r contains no information about i.
By Definition 2, it is impossible for any polynomial-time algorithms to compute any information about i from qe . Thus
the protocol has privacy protection.
(Anonymity against Authentication-Server) What S obtains
in the proposed protocol is {(q1 , ..., qk ), (a1 , ..., ak ), pi , z  }.
S can obtain no information about i from (q1 , ..., qk ) since
the public encryption scheme is semantic secure. Also, S
can also obtain no information about i from (a1 , ..., ak )by Definition 2. The value i is independent from piand z  . Therefore the protocol has anonymity against
authentication-servers.
2

5

Conclusions and Future WorkIn this paper, we proposed novel authentication protocols. Firstly, we showed a protocol with a single databasewhich satisfies correctness, soundness, anonymity against
database, password protection, and security against replayattacks. Secondly, we showed a protocol with multiple
databases which satisfies anonymity against authenticationserver in addition to the previous properties. The key idea
is to employ PIR in the core of authentication protocols.
The authentication protocol proposed in Section 4 isbased on an information theoretical PIR in which an identifier is not given as an input of the reconstruction function. However, the assumption that the multiple databases
are mutually independent but yet share the same set of passwords, may be impractical. Hence our future work includes surveying or developing single-server PIR without
identifiers in reconstruction. We will evaluate the computational complexity and the communication complexity ofthese proposed protocols.

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] RFC2195. http://tools.ietf.org/html/rfc2195.
[3] J. Bringer, H. Chabanne, M. Izabachéne, D. Pointcheval,
Q. Tang, and S. Zimmer. An application of the GoldwasserMicali cryptosystem to biometric authentication. In Information Security and Privacy, 12th Australasian Conference, ACISP 2007, volume 4586 of LNCS, pages 96–106.
Springer-Verlag, 2007.
[4] J. Bringer, H. Chabanne, D. Pointcheval, and Q. Tang. Extended private information retrieval and its application inbiometrics authentications. In Cryptology and Network Security, 6th International Conference, CANS 2007, volume
4856 of LNCS, pages 175–193. Springer-Verlag, 2007.

[5] C. Cachin, S. Micali, and M. Stadler. Computationally private information retrieval with polylogarithmic communication. In Advances in Cryptology - EUROCRYPT ’99, volume
1592 of LNCS, pages 402–414. Springer-Verlag, 1999.
[6] J. Camenisch and A. Lysyanskaya. An efficient system
for non-transferable anonymous credentials with optional
anonymity revocation. In Advances in Cryptology - EUROCRYPT 2001, volume 2045 of LNCS, pages 93–118.
Springer-Verlog, 2001.
[7] D. Chaum and E. van Heyst. Group signatures. In Advancesin Cryptology - EUROCRYPT 1991, volume 547 of LNCS,
pages 257–270. Springer-Verlag, 1991.
[8] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private
information retrieval. Jornal of the ACM, 45:965–982, 1998.
[9] O. Goldreich. Foundations of Cryptography. Cambridge
University, 2001.
[10] M. Hansen, A. Schwartz, and A. Cooper. Privacy-enhancing
identity management. IEEE Security and Privacy, 3:38–45,
2008.
[11] E. Kushilevitz and R. Ostrovsky. Replication is not needed:
Single database, computationally-private information retrieval. In Proceedings of the 38th Annual Symposium on
Foundations of Computer Science, pages 364–373, 1997.
[12] Y.-P. Liao and S.-S. Wang. A secure dynamic ID based remote user authentication scheme for multi-server environment. Computer standards and interfaces, 31(1):24–29,
2009.