Anonymous Authentication Schemewith Decentralized Multi-authorities
Hiroaki Anada

Seiko Arita

Department of Information Security
University of Nagasaki
Nagasaki, Japan
Email: anada@sun.ac.jp

Graduate School of Information Security
Institute of Information Security
Yokohama, Japan
Email: arita@iisec.ac.jp

Abstract—We propose an anonymous authentication schemewith a feature that more than one authorities such as license
issuers or product providers can admit a single entity by issuing
secret keys, and then the entity is able to prove that is has
those secret keys associated to its identity, without a central
authority. First, we provide the syntax and the security definitionof an anonymous authentication scheme with such decentralized
multi-authorities. Next, we give a construction of an anonymous
authentication scheme in the discrete logarithm setting by using
the Okamoto identification scheme and the Pedersen commitment
scheme as building blocks. Then we prove that, under the discrete
logarithm assumption, our scheme possesses the proving abilityof knowing secret keys associated to the single identity, theanonymity, and the security against concurrent attacks of causing
misauthentication. The algorithm of our scheme does not needcostly pairing computation, and hence our scheme is suitable fordevices with less computational resource.

I. I NTRODUCTION
Authentication is a process of determining whether someone
or something is in fact the one which has been beforehand
admitted by an authority. Currently, logging into a service ona website needs inputting a pair of ID and a password, andonce the pair matches with a string on a database the process
successfully ends. The succeeded entity goes into the next
process of getting permission to do something on the service.
The recent growth of the internet of things and related
big data analysis makes protecting privacy more important,and hence the framework of ID and a password should be
replaced by an anonymous authentication mechanism. Anotherdirection is a multi-factor authentication scheme for moresecurity to prevent misauthentication. In the scheme an entity
is granted access only after successfully presenting several
separate pieces of evidence. Actually the multi-factor authentication of using both a laptop PC and a smartphone is getting
popular.
In this paper, we propose an anonymous authentication
scheme with a feature that various authorities such as license
issuers or product providers can admit a person or a thing
without a central authority. For example, a person identified bya string like a social security number or a passport ID number
is authorized by several organizations of tax, hospital, job
opportunity, immigration control, etc. Those organizations are
independent and issue authorization evidence separately. Herethe need of authorization by decentralized multi-authorities

978-1-5090-6517-2/17/$31.00 ©2017 IEEE

arises. Note here that we must care the privacy problem
because if the kind of number like the social security number
is once revealed, then his records of activities are linked andanalysed for serious purpose like job interview or unexpectedsales marketing. In those situation, our anonymous authentication scheme with decentralized multi-authorities is useful.
A. Related Works, our Contribution and Construction
Anonymous credential systems (AC for short) share thesame spirit with our proposal. Sadiah et al. [15] proposed AC
for proving possession of credentials that satisfy a monotone
formula given to both a prover and a verifier. Camenisch etal. [7] proposed AC for multi-authorities with the universal
composability. Attribute-based identification schemes (ABIDfor short) [2] also shares the spirit. ABID usually possesses
collusion resistance, anonymity and attribute-privacy as well
as security against impersonation. The proposed protocols inthese works basically use pairing computations.
Our scheme, however, does not pursue collusion resistance,
but instead, pursues less computational amount. Actually thealgorithm of our scheme does not need costly pairing computation, and it is suitable for IoT devices with less computational
resource.
The building blocks of our scheme are the Okamoto identification scheme [13] and the Pedersen commitment scheme [14],both of which are in the discrete logarithm setting, At a highlevel, the perfect witness-indistinguishability [10], [13] and theproof-of-knowledge property [5] of the Okamoto identification
scheme as well as the perfectly hiding property of the Pedersen
commitment scheme yield the security against concurrent
attacks causing misauthentication [6] and the anonymity. On
the other hand, the computationally binding property yields
that the authorized person or the thing is actually a single
one.
B. Organization of the Paper
In Section II, we prepare the needed notations and notions.
In Section III, we provide the syntax and security definitionsof our anonymous authentication scheme with decentralized
multi-authorities. In Section IV, we construct a concrete
scheme in the discrete logarithm setting. In Section V, We

discuss some supplemental aspects. In Section VI, we conclude our work.
II. P RELIMINARIESLet 𝜆 denote the security parameter. For a positive integer𝑛 let ℤ𝑛>0 denote the set of positive integers less than orequal to 𝑛. Let 𝑎 ∈𝑅 Space(1𝜆 ) denote a uniform random
sampling of an element 𝑎 from a sample space parametrizedby 1𝜆 . For a set 𝑆 let ∣𝑆∣ denote the number of elements of𝑆. and for a string 𝑠 let ∣𝑠∣ denote the bit-length of 𝑠. For
two events 𝐴 and 𝐵, let Pr[𝐴 : 𝐵] denote the conditional
probability that, on condition that 𝐴 occurs, 𝐵 occurs. The
expression 𝑎 =? 𝑏 returns a value 1 (T RUE) when 𝑎 = 𝑏,
and otherwise, 0 (FALSE). When an algorithm 𝒜 with input
𝑎 outputs 𝑧, we denote it as 𝑧 ← 𝒜(𝑎), or, because of
space limitation, 𝒜(𝑎) → 𝑧. When 𝒜 with input 𝑎 and ℬ
with input 𝑏 interact with each other and ℬ outputs 𝑧, we
denote it as 𝑧 ← ⟨𝒜(𝑎), ℬ(𝑏)⟩. When 𝒜 has oracle-accessto 𝒪, we denote it as 𝒜𝒪 . When 𝒜 has concurrent oracle𝑛
access to 𝑛 oracles 𝒪1 , . . . , 𝒪𝑛 , we denote it as 𝒜𝒪𝑖 ∣𝑖=1 .
Here “concurrent” means that 𝒜 accesses oracles in arbitrarily
interleaved order of messages.
A. Discrete Logarithm Assumption [13]Let 𝔾 denote a cyclic group of a prime order 𝑝 where∣𝑝∣ = 𝜆, and let 𝑔 denote a generator. Let Grp denote a
PPT algorithm which, on input 1𝜆 , returns a set of publicparameters params := (𝑝, 𝔾, 𝑔). The discrete logarithm
assumption [13] states that, for any PPT algorithm 𝒮, theadvantage of 𝒮 over Grp, which is defined as follows, is anegligible function of 𝜆.
𝜆
Advdl
Grp,𝒮 (𝜆) := Pr[params ← Grp(1 ), 𝛾 ∈𝑅 ℤ𝑝 ,𝛾 ∗ ← 𝒮(params, 𝑔, 𝑔 𝛾 ) : 𝛾 = 𝛾 ∗ ].
Here the probability is taken over the random tape of Grp,
the uniform random sampling of 𝛾 and the random tape of 𝒮.
B. Okamoto Identification Scheme [13]The Okamoto identification scheme [13] is an identification
scheme in the discrete logarithm setting. It is an interactive
proof system whose protocol is a Σ-protocol [8]. Let paramsbe (𝑝, 𝔾, 𝑔) where 𝑝 is a prime of bit-length 𝜆, 𝔾 is a cyclic
group of order 𝑝 and 𝑔 is a base of 𝔾. Choose 𝛼 ∈𝑅 ℤ𝑝 andcomputes ℎ := 𝑔 𝛼 . Choose 𝑤1 , 𝑤2 ∈𝑅 ℤ𝑝 and computes
𝑋 = 𝑔 𝑤1 ℎ𝑤2 .

(1)Set 𝑥 := (𝑔, ℎ, 𝑋) and 𝑤 := (𝑤1 , 𝑤2 ). The prover 𝒫 takes as
input (𝑥, 𝑤) and the verifier 𝒱 takes as input 𝑥. 𝒫 chooses
𝜇1 , 𝜇2 ∈𝑅 ℤ𝑝 and computes a group element 𝐴 := 𝑔 𝜇1 ℎ𝜇2
called a commitment message. 𝒫 sends 𝐴 to 𝒱. Then 𝒱
chooses an exponent 𝑐 ∈𝑅 ℤ𝑝 called a challenge message.
𝒱 sends 𝑐 to 𝒫. Then, 𝒫 computes a pair of exponent values𝜂1 := 𝜇1 +𝑐𝑤1 , 𝜂2 := 𝜇2 +𝑐𝑤2 called a response messages. 𝒫
sends (𝜂1 , 𝜂2 ) to 𝒱. Finally, 𝒱 checks whether the following
equality holds to return acc (“accept”) or rej (“reject”).
𝑔 𝜂1 ℎ𝜂2 = 𝐴𝑋 𝑐 .

(2)

There are two features. One is that the Okamoto identification
scheme is perfectly witness-indistinguishable [10], [13]. The
verifier 𝒱 gets no information through the protocol which
witness 𝑤 = (𝑤1 , 𝑤2 ) satisfying the equation (1) was actuallyused among 𝑝 solutions. The other is that the Okamoto identification scheme is a proof of knowledge system [5], [6]. For any
PPT prover 𝒫 ∗ whose probability of being accepted is nonnegligible, there exist a PPT algorithm 𝒦 called a knowledge
extractor which returns a solution of the equation (1). The
knowledge extractor 𝒦 of the Okamoto identification scheme(and, generally, of the Σ-protocol) is constructed by therewinding technique [6] to yield the special-soundness. Hence,
we denote the Okamoto identification scheme as OkamWIPoK,
which will be a building block of our anonymous authentication scheme.
C. Pedersen Commitment Scheme [14]The Pedersen commitment scheme [14] PedCom is a commitment scheme in the discrete logarithm setting. Let paramsbe (𝑝, 𝔾, 𝑔) where 𝑝 is a prime of bit-length 𝜆, 𝔾 is a cyclic
group of order 𝑝 and 𝑔 is a base of 𝔾. Choose 𝛼 ∈𝑅 ℤ𝑝 andcomputes ℎ := 𝑔 𝛼 . In the commitment phase, Alice, who isgoing to commit to an exponent value 𝜏 , chooses 𝑤 ∈𝑅 ℤ𝑝
and compute 𝑋 = 𝑔 𝜏 ℎ𝑤 . The commitment value is 𝑋. Alicesends 𝑋 to Bob. In the reveal phase, Alice sends (𝜏, 𝑤) to Bob
and Bob checks whether 𝑋 is equal to 𝑔 𝜏 ℎ𝑤 or not. There are
two features. One is that PedCom is perfectly hiding. Bobgets no information about the exponent expression of 𝑋 tothe base (𝑔, ℎ). The other is that PedCom is computationallybinding. If (a PPT algorithm) Alice reveals in a different way(𝜏 ′ , 𝑤′ ) ∕= (𝜏, 𝑤) with non-negligible probability, then a PPT
algorithm 𝒮 that solves the discrete logarithm problem with
non-negligible probability is constructed by employing Aliceas a subroutine. PedCom will be a building block of ouranonymous authentication scheme.
III. S YNTAX AND S ECURITY D EFINITIONIn this section, we provide the syntax and the security
definition of an anonymous authentication scheme with decentralized multi-authorities, a-auth.
A. Syntax
a-auth consists of five PPT algorithms, (Setup,
AuthKey, PrivKey, 𝒫, 𝒱).
Setup(1𝜆 ) → params. This PPT algorithm is needed only
for generating a set of values of public parameters params(that includes, for example, group-operation description). On
input the security parameter 1𝜆 , it generates the values ofpublic parameters and returns them as params. In the casethat an already known set of values is available (for example,
NIST FIPS 186-4 [12]), params can be set as those values.
AuthKey(params, 𝑙) → (PK𝑙 , MSK𝑙 ). This PPT algorithm
is executed by an authority indexed by a positive integer 𝑙,
who issues a private key for a prover. On input the publicparameter values params and the index 𝑙, it generates the 𝑙-th
maser public key PK𝑙 of the authority and the corresponding

𝑙-th master secret key MSK𝑙 of the authority. It returns(PK𝑙 , MSK𝑙 ).
PrivKey(params, PK𝑙 , MSK𝑙 , 𝜏 ) → sk𝜏,𝑙 . This PPT algorithm is executed by an authority who has the 𝑙-th master secretkey MSK𝑙 . On input the public parameter values params, the𝑙-th pair of the public and the master secret keys (PK𝑙 , MSK𝑙 )and a private identity string 𝜏 of a prover, it generates theprivate secret key sk𝜏,𝑙 of a prover. It returns sk𝜏,𝑙 .
⟨𝒫(params, (PK𝑙 , sk𝜏,𝑙 )𝑙∈𝑆 ), 𝒱(params, (PK𝑙 )𝑙∈𝑆 )⟩→acc/rej. These two interactive PPT algorithms are executedby a prover who is to be authenticated, and by a verifier
who confirms that the prover certainly knows the secret keys
issued by authorities, respectively. The prover is identified
by a private string 𝜏 . Let 𝑆 denote a subset of the set of all
indices at which the prover is issued her private secret keys
by authorities: 𝑆 := {𝑙 ∈ ℤ; sk𝜏,𝑙 has been issued }. The
prover algorithm 𝒫 and the verifier algorithm 𝒱 are given
as input the public parameter values params and the publickeys (PK𝑙 )𝑙∈𝑆 . In addition, 𝒫 is given as input the private
secret keys indexed by 𝑙 ∈ 𝑆, (sk𝜏,𝑙 )𝑙∈𝑆 . In the interaction,
after at most polynomially many (in 𝜆) moves of messages
between 𝒫 and 𝒱, 𝒱 returns acc or rej.
B. Security Definition
For an anonymous authentication scheme with decentralized
multi-authorities, a-auth, we define two security notions;security against misauthentication and anonymity property.
1) Anonymity: For defining the anonymity of a-auth,we consider the following experiment on a-auth and an
adversary 𝒜.
𝜆Expranonym
a-auth,𝒜 (1 , poly(⋅))

params ← Setup(1𝜆 ), 𝑛𝑎 ∈𝑅 ℤ>0
For 1 ≤ 𝑙 ≤ 𝑛𝑎 : (PK𝑙 , MSK𝑙 ) ← AuthKey(params, 𝑙)poly(𝜆)𝜏0 , 𝜏1 ∈𝑅 {0, 1}𝜆For 1 ≤ 𝑙 ≤ 𝑛𝑎 :sk𝜏0 ,𝑙 ← PrivKey(params, PK𝑙 , MSK𝑙 , 𝜏0 )sk𝜏1 ,𝑙 ← PrivKey(params, PK𝑙 , MSK𝑙 , 𝜏1 )𝑏 ∈𝑅 {0, 1}, 𝑏∗ ←𝑎𝑎⟨𝒫(params, (PK𝑙 , sk𝜏𝑏 ,𝑙 )𝑛𝑙=1), 𝒜(params, (PK𝑙 )𝑛𝑙=1)⟩
If 𝑏 = 𝑏∗ , then Return Win, else Return Lose

The advantage of an adversary 𝒜 over an authentication
scheme a-auth in the experiment of anonymity is defined asdefanonym𝜆follows: Advanonym
a-auth,𝒜 (𝜆) = Pr[Expra-auth,𝒜 (1 , poly(⋅)) =Win]. An authentication scheme a-auth is called to possess anonymity if, for any PPT algorithm 𝒜, the advantage
Advanonym
a-auth,𝒜 (𝜆) is negligible in 𝜆.
2) Concurrent Attack of Misauthentication: For defining
the security of a-auth against misauthentication, we consider
concurrent attacks in the sense that an adversary 𝒜 interacts
with provers in arbitrarily interleaved order of messages in thelearning phase. After the phase, 𝒜 tries to cause misauthen-tication. For a formal treatment we consider the following
experiment of a concurrent attack of misauthentication.
𝜆Exprmisauth-ca
a-auth,𝒜 (1 , poly(⋅))

params ← Setup(1𝜆 ), 𝑛𝑎 , 𝑛𝑝 ∈𝑅 ℤ>0
For 1 ≤ 𝑙 ≤ 𝑛𝑎 : (PK𝑙 , MSK𝑙 ) ← AuthKey(params, 𝑙)poly(𝜆)For 1 ≤ 𝑚 ≤ 𝑛𝑝 : 𝜏𝑚 ∈𝑅 {0, 1}𝜆 ,For 1 ≤ 𝑙 ≤ 𝑛𝑎 :sk𝜏𝑚 ,𝑙 ← PrivKey(params, PK𝑙 , MSK𝑙 , 𝜏𝑚 )
𝑛𝑎

𝑛𝑝

𝑎
)
st ← 𝒜𝒫(params,(PK𝑙 ,sk𝜏𝑚 ,𝑙 )𝑙=1 )∣𝑚=1 (params, (PK𝑙 )𝑛𝑙=1
𝑛𝑎𝑑 ← ⟨𝒜(st), 𝒱(params, (PK𝑙 )𝑙=1 )⟩If 𝑑 = acc, then Return Win, else Return LoseIn the above experiment, 𝒜 does concurrent oracle accesses to𝑎𝒫(params, (PK𝑙 , sk𝜏𝑚 ,𝑙 )𝑛𝑙=1), 𝑚 = 1, . . . , 𝑛𝑝 , as the learning
phase. Then, as the next phase, 𝒜 interacts with 𝒱. In theinteraction 𝒜 generates a set of indices 𝑆 which determines
public keys {PK𝑙 ; 𝑙 ∈ 𝑆}. Under the set of public keys 𝒜 tries
to cause misauthentication.
The advantage of an adversary 𝒜 over an authentication
scheme a-auth in the experiment is defined as follows:defmisauth-ca 𝜆Advmisauth-ca
a-auth,𝒜 (𝜆) = Pr[Expra-auth,𝒜 (1 , poly(⋅)) = Win].
An authentication scheme a-auth is called secure against concurrent attacks of misauthentication if, for any PPT algorithm
𝒜, the advantage Advmisauth-ca
a-auth,𝒜 (𝜆) is negligible in 𝜆.
IV. O UR C ONSTRUCTION
In this section, we construct a concrete anonymous authentication scheme with decentralized multi-authorities, a-auth =(Setup, AuthKey, PrivKey, 𝒫, 𝒱). Then we prove that
our a-auth possesses anonymity and that our a-auth issecure against concurrent attacks of misauthentication, bothunder the discrete logarithm assumption on the group generation algorithm, Grp.
A. Scheme
The five algorithms are constructed as follows (see Fig. 1).
Setup(1𝜆 ) → params. On input the security parameter 1𝜆 ,this PPT algorithm runs Grp(1𝜆 ) to generates a prime 𝑝, a
cyclic group 𝔾 of order 𝑝 and a base 𝑔0 of 𝔾. Besides, itchooses an exponent 𝛼0 ∈𝑅 ℤ𝑝 and computes ℎ0 := 𝑔0𝛼0 . It
returns params := (𝑝, 𝔾, 𝑔0 , ℎ0 ).
AuthKey(params, 𝑙) → (PK𝑙 , MSK𝑙 ). On input params
and the index 𝑙, this PPT algorithm chooses a base 𝑔𝑙 ∈𝑅 𝔾
and an exponent 𝛼𝑙 ∈𝑅 ℤ𝑝 and computes ℎ𝑙 := 𝑔𝑙𝛼𝑙 . Then itchooses two exponents 𝜏𝑙∗ , 𝑤𝑙∗ ∈𝑅 ℤ𝑝 and computes 𝑋𝑙 :=𝜏 ∗ 𝑤∗
𝑔𝑙 𝑙 ℎ𝑙 𝑙 . It sets PK𝑙 := (𝑔𝑙 , ℎ𝑙 , 𝑋𝑙 ), MSK𝑙 := (𝛼𝑙 , 𝜏𝑙∗ , 𝑤𝑙∗ ). It
returns (PK𝑙 , MSK𝑙 ).
PrivKey(params, PK𝑙 , MSK𝑙 , 𝜏 ) → sk𝜏,𝑙 . On input
params, PK𝑙 , MSK𝑙 and a private identity string 𝜏 of a prover,this PPT algorithm computes 𝑤𝜏,𝑙 := 𝑤𝑙∗ +(𝜏𝑙∗ −𝜏 )/𝛼𝑙 and setssk𝜏,𝑙 := (𝜏, 𝑤𝜏,𝑙 ). It returns sk𝜏,𝑙 . Note here that the following
equality holds.
𝜏 ∗ 𝑤∗𝑤

𝑋𝑙 = 𝑔𝑙 𝑙 ℎ𝑙 𝑙 = 𝑔𝑙𝜏 ℎ𝑙 𝜏,𝑙 .

(3)

⟨𝒫(params, (PK𝑙 , sk𝜏,𝑙 )𝑙∈𝑆 ), 𝒱(params, (PK𝑙 )𝑙∈𝑆 )⟩→acc/rej. On the common input params and (PK𝑙 )𝑙∈𝑆
and the private input (sk𝜏,𝑙 )𝑙∈𝑆 , 𝒫 chooses an exponent
𝑤𝜏,0 ∈𝑅 ℤ𝑝 and computes the Perdersen commitment𝑤
𝑋0 := 𝑔0𝜏 ℎ0 𝜏,0 to 𝜏 . Then, for each 𝑙 ∈ 𝑆, 𝒫 chooses
two exponents 𝜇𝑙 , 𝜈𝑙 ∈𝑅 ℤ𝑝 and computes the commitment
message 𝐴𝑙 := 𝑔𝑙𝜇𝑙 ℎ𝜈𝑙 𝑙 of the Σ-protocol of OkamWIPoK.
Besides, 𝒫 chooses an exponent 𝜈0,𝑙 ∈𝑅 ℤ𝑝 and computes𝜈the commitment message 𝐴0,𝑙 := 𝑔0𝜇𝑙 ℎ00,𝑙 of OkamWIPoK.
𝒫 sends 𝑋0 and (𝐴𝑙 , 𝐴0,𝑙 )𝑙∈𝑆 to 𝒱.
Receiving the Pedersen commitment 𝑋0 and all the commitment messages (𝐴𝑙 , 𝐴0,𝑙 )𝑙∈𝑆 of OkamWIPoK, 𝒱 on input params and (PK𝑙 )𝑙∈𝑆 chooses a challenge message𝑐 ∈𝑅 C HA S P(1𝜆 ) of the Σ-protocol of OkamWIPoK. HereC HA S P(1𝜆 ) is ℤ𝑝 . 𝒱 sends 𝑐 to 𝒫.
Receiving the challenge message 𝑐, 𝒫 computes the response messages of the Σ-protocol of OkamWIPoK as 𝜂𝑙 :=𝜇𝑙 + 𝑐𝜏 , 𝜃𝑙 := 𝜈𝑙 + 𝑐𝑤𝜏,𝑙 and 𝜃0,𝑙 := 𝜈0,𝑙 + 𝑐𝑤𝜏,0 . 𝒫 sends(𝜂𝑙 , 𝜃𝑙 , 𝜃0,𝑙 )𝑙∈𝑆 to 𝒱.
Receiving the response messages (𝜂𝑙 , 𝜃𝑙 , 𝜃0,𝑙 )𝑙∈𝑆 of
OkamWIPoK, 𝒱 checks the following equations of the Σprotocol of OkamWIPoK: For 𝑙 ∈ 𝑆, 𝑔𝑙𝜂𝑙 ℎ𝜃𝑙 𝑙 =? 𝐴𝑙 𝑋𝑙𝑐 and𝜃𝑔0𝜂𝑙 ℎ00,𝑙 =? 𝐴0,𝑙 𝑋0𝑐 . If all the equations hold, then 𝒱 returns
acc, and otherwise, rej.
The correctness holds for our a-auth. That is, for any given
positive polynomial poly(𝜆),Pr[params ← Setup(1𝜆 ); 𝑛𝑎 ∈𝑅 ℤpoly>0 (𝜆);As Δ𝑐 ∕= 0 except the case of probability 1/𝑝, 𝒦 sets for each𝑙 𝜏ˆ𝑙 := Δ𝜂𝑙 /Δ𝑐, 𝑤ˆ𝑙 := Δ𝜃𝑙 /Δ𝑐 and 𝑤ˆ0,𝑙 := Δ𝜃0,𝑙 /Δ𝑐. Thenthe following equalities hold.
{
𝑋𝑙 = 𝑔𝑙𝜏ˆ𝑙 ℎ𝑙𝑤ˆ𝑙 ,𝑙 ∈ 𝑆.
(8)𝑤ˆ
𝑋0 = 𝑔0𝜏ˆ𝑙 ℎ0 0,𝑙 ,Thus, 𝒦 is able to compute the tuple (𝜏ˆ𝑙 , 𝑤ˆ𝑙 , 𝑤ˆ0,𝑙 )𝑙∈𝑆 thatsatisfies the equation (8).
Claim 1. The equality

For 𝑙 = 1 to 𝑛𝑎 (PK𝑙 , MSK𝑙 ) ← AuthKey(params, 𝑙);𝜏 ∈𝑅 {0, 1}𝜆 ;For 𝑙 = 1 to 𝑛𝑎 sk𝜏,𝑙 ← PrivKey(params, PK𝑙 , MSK𝑙 , 𝜏 );𝑎
𝑆 := ℤ𝑛>0:
acc ← ⟨𝒫(params, (PK𝑙 , sk𝜏,𝑙 )𝑙∈𝑆 ), 𝒱(params, (PK𝑙 )𝑙∈𝑆 )⟩]
= 1.
(4)

B. Security
1) Proofs of Knowledge of Common Prefix:
Theorem 1 (PoK of Common String). Suppose that ∣𝑆∣ ≥2. Then, our authentication scheme a-auth is a proof ofknowledge system for generating proofs of the knowledge of
witnesses that share a common string 𝜏 under the discrete logarithm assumption on Grp. More precisely, given params and(PK𝑙 )𝑙∈𝑆 and for any PPT prover 𝒫 ∗ whose probability of being accepted is 𝑝acc , there exist a PPT knowledge extractor 𝒦
and a PPT algorithm 𝒮 on Grp where 𝒦(params, (PK𝑙 )𝑙∈𝑆 )returns a tuple (ˆ𝜏 , (𝑤ˆ𝑙 , 𝑤ˆ0,𝑙 )𝑙∈𝑆 ) ∈ (ℤ𝑝 )2∣𝑆∣+1 that satisfies
the following equations:{
𝑋𝑙 = 𝑔𝑙𝜏ˆ ℎ𝑙𝑤ˆ𝑙 ,𝑙 ∈ 𝑆,(5)𝑤ˆ
𝑋0 = 𝑔0𝜏ˆ ℎ0 0,𝑙 .
with the probability at least()2
1− Advdl𝑝acc −
Grp,𝒮 (𝜆).
𝑝Proof. Using a PPT prover 𝒫 ∗ as a subroutine, we construct a PPT knowledge extractor 𝒦 as follows (in accordance with the standard argument [6]). 𝒦 is given as
input (params, (PK𝑙 )𝑙∈𝑆 ). 𝒦 gives (params, (PK𝑙 )𝑙∈𝑆 ) to𝒫 ∗ and receives from 𝒫 ∗ a tuple of commitment messages(𝐴𝑙 , 𝐴0,𝑙 )𝑙∈𝑆 and copies and keeps the inner state st of 𝒫 ∗ .
𝒦 chooses two challenge messages 𝑐 and 𝑐′ uniformly at
random from C HA S P(𝜆) = ℤ𝑝 . Here 𝑐 = 𝑐′ holds withprobability 1/𝑝. 𝒦 sends 𝑐 to 𝒫 ∗ (st) and receives the response
messages (𝜂𝑙 , 𝜃𝑙 , 𝜃0,𝑙 )𝑙∈𝑆 . 𝒦 also sends 𝑐′ to 𝒫 ∗ (st) and′)𝑙∈𝑆 . Suppose here
receives the response messages (𝜂𝑙′ , 𝜃𝑙′ , 𝜃0,𝑙that all the messages are accepting conversation. For each𝑙 ∈ 𝑆, 𝒦 computes the differences: Δ𝜂𝑙 := 𝜂𝑙 − 𝜂𝑙′ , Δ𝜃𝑙 :=′, Δ𝑐 := 𝑐 − 𝑐′ . After cancelling the𝜃𝑙 − 𝜃𝑙′ , Δ𝜃0,𝑙 := 𝜃0,𝑙 − 𝜃0,𝑙commitment messages the following equalities hold.
{𝑙
𝑔𝑙Δ𝜂𝑙 ℎΔ𝜃= 𝑋𝑙Δ𝑐 ,𝑙𝑙 ∈ 𝑆.
(7)Δ𝜂𝑙 Δ𝜃0,𝑙= 𝑋0Δ𝑐 ,𝑔 0 ℎ0∃ˆ𝜏 ∈ ℤ𝑝 s.t. [∀𝑙 ∈ 𝑆, 𝜏ˆ𝑙 = 𝜏ˆ](9)holds except the case of probability at most Advdl
Grp,𝒮 (𝜆).
Proof of Claim 1. Name the event that there exists at leasta pair (𝑙1 , 𝑙2 ) at which 𝜏ˆ𝑙1 ∕= 𝜏ˆ𝑙2 as D L PAIR. A solver 𝒮of the discrete logarithm problem on Grp is constructed,
as follows. Given an instance (𝑔, ℎ), 𝒮 sets 𝑔0 := 𝑔 andℎ0 := ℎ. 𝒮 executes Setup, AuthKey, PrivKey honestly
as in the correctness formula (4). Then, 𝒮 interacts with𝒫 ∗ (params, (PK𝑙 )𝑙∈𝑆 ) as a verifier, and obtains all the above
messages (as in the proof of the theorem).
We are in the case that ∣𝑆∣ ≥ 2. Hence, if 𝜏ˆ𝑙1 ∕= 𝜏ˆ𝑙2
in (8) for some 𝑙1 , 𝑙2 ∈ 𝑆, 𝑙1 ∕= 𝑙2 , then 𝒮 obtains two
different expressions of the Pedersen commitment 𝑋0 to thebase (𝑔0 , ℎ0 ). Therefore 𝒮 computes the discrete log of ℎ to
ˆ 1 − 𝑤0,𝑙
ˆ 2 ). The
the base 𝑔 as log𝑔 (ℎ) = −(𝜏ˆ𝑙1 − 𝜏ˆ𝑙2 )/(𝑤0,𝑙probability of this event is Pr[D L PAIR], which is less than orequal to Advdl
Grp,𝒮 (𝜆) by the definition.
Now we evaluate the probability in the theorem. Using Reset
Lemma [6] (Lemma 3.1), the following inequality holds.
√
𝑝acc ≤ (1/𝑝) + Pr[𝒦 returns (𝜏ˆ𝑙 , 𝑤ˆ𝑙 , 𝑤ˆ0,𝑙 )𝑙∈𝑆 ](10)
By the above Claim 1, the following equality holds.
Pr[𝒦 returns (𝜏ˆ𝑙 , 𝑤ˆ𝑙 , 𝑤ˆ0,𝑙 )𝑙∈𝑆 ] − Advdl
Grp,𝒮 (𝜆)≤ Pr[𝒦 returns (ˆ𝜏 , (𝑤ˆ𝑙 , 𝑤ˆ0,𝑙 )𝑙∈𝑆 )].

(6)

Combining (10) and (11), the evaluation (6) follows.

(11)Setup(1𝜆 )(𝑝, 𝔾, 𝑔0 ) ← Grp(1𝜆 )𝛼0 ∈𝑅 ℤ𝑝 , ℎ0 := 𝑔0𝛼
params := (𝑝, 𝔾, 𝑔0 , ℎ0 )Return params
AuthKey(params, 𝑙)𝑔𝑙 ∈𝑅 𝔾, 𝛼𝑙 ∈𝑅 ℤ𝑝 , ℎ𝑙 := 𝑔𝑙𝛼𝑙𝜏 ∗ 𝑤∗
𝜏𝑙∗ , 𝑤𝑙∗ ∈𝑅 ℤ𝑝 , 𝑋𝑙 := 𝑔𝑙 𝑙 ℎ𝑙 𝑙
PK𝑙 := (𝑔𝑙 , ℎ𝑙 , 𝑋𝑙 )MSK𝑙 := (𝛼𝑙 , 𝜏𝑙∗ , 𝑤𝑙∗ )Return (PK𝑙 , MSK𝑙 )𝒫(params, (PK𝑙 , sk𝜏,𝑙 )𝑙∈𝑆 )𝑤
𝑤𝜏,0 ∈𝑅 ℤ𝑝 , 𝑋0 := 𝑔0𝜏 ℎ0 𝜏,0For 𝑙 ∈ 𝑆 :𝜇𝑙 , 𝜈𝑙 ∈𝑅 ℤ𝑝 , 𝐴𝑙 := 𝑔𝑙𝜇𝑙 ℎ𝜈𝑙 𝑙𝜈𝜈0,𝑙 ∈𝑅 ℤ𝑝 , 𝐴0,𝑙 := 𝑔0𝜇𝑙 ℎ00,𝑙

For 𝑙 ∈ 𝑆 :𝜂𝑙 := 𝜇𝑙 + 𝑐𝜏, 𝜃𝑙 := 𝜈𝑙 + 𝑐𝑤𝜏,𝑙𝜃0,𝑙 := 𝜈0,𝑙 + 𝑐𝑤𝜏,0𝒱(params, (PK𝑙 )𝑙∈𝑆 )𝑋0 , (𝐴𝑙 , 𝐴0,𝑙 )𝑙∈𝑆−→

𝑐 ∈𝑅 C HA S P(1𝜆 )𝑐←−(𝜂𝑙 , 𝜃𝑙 , 𝜃0,𝑙 )𝑙∈𝑆−→

For 𝑙 ∈ 𝑆 :𝑔𝑙𝜂𝑙 ℎ𝜃𝑙 𝑙 =? 𝐴𝑙 𝑋𝑙𝑐
𝜃𝑔0𝜂𝑙 ℎ00,𝑙 =? 𝐴0,𝑙 𝑋0𝑐
If all eqs. hold, Return acc
otherwise Return rej

PrivKey(params, PK𝑙 , MSK𝑙 , 𝜏 )𝑤𝜏,𝑙 := 𝑤𝑙∗ + (𝜏𝑙∗ − 𝜏 )/𝛼𝑙sk𝜏,𝑙 := (𝜏, 𝑤𝜏,𝑙 ), Return sk𝜏,𝑙Fig. 1. Anonymous authentication scheme with decentralized multi-authorities a-auth2) Anonymity:
Theorem 2 (Perfect Anonymity). Our authentication scheme
a-auth possesses perfect anonymity. More precisely, for any
unbounded algorithm 𝒜, the following inequality holds.
Advanonym
a-auth,𝒜 (𝜆) = 0.
Proof (sketch). This is the direct consequence of two facts;
one is that the Okamoto identification scheme [13] is perfectly witness indistinguishable; the other is that the Pedersen
commitment scheme [14] is perfectly hiding.
3) Security against Concurrent Attack of Misauthentication:𝑎) instead of private secret
Using the values (𝜏 ∗ , (𝑤𝑙∗ )𝑛𝑙=1
𝑛𝑎 𝑛𝑝
keys ((sk𝜏𝑚 ,𝑙 )𝑙=1 )𝑚=1 that are not generated, 𝒮 simulates
𝑛𝑝
𝑎
)∣𝑚=1
perfectly in the replies to𝒫(params, (PK𝑙 , sk𝜏𝑚 ,𝑙 )𝑛𝑙=1
the concurrent oracle access by 𝒜. This can be done becauseof the perfect anonymity of a-auth (Theorem 2); 𝒜 learns
no information about the exponent expression (3) of 𝑋𝑙 to thebase (𝑔𝑙 , ℎ𝑙 ), 𝑙 = 1, . . . , 𝑛𝑎 . 𝒮 copies and keeps the inner state
st of 𝒜. After the concurrent oracle access, 𝒜 interacts with𝑎) simulated by 𝒮. 𝒮 rewinds
a verifier 𝒱(params, (PK𝑙 )𝑛𝑙=1
𝒜(st) to obtain the equalities that is the same as (8) (in the
proof of Theorem 1). Therefore, there exists at least one 𝑙 at
which the following equalities hold.
∗

Theorem 3 (Security under Concurrent Attacks of Causing
Misauthentication). Our authentication scheme a-auth issecure against concurrent attacks of causing misauthentication under the discrete logarithm assumption on Grp. Moreprecisely, given a positive polynomial poly(⋅) and for any PPT
algorithm 𝒜 in the experiment of the concurrent attack, there
exists a PPT algorithm 𝒮 on Grp that satisfies the following
inequality.
√
1
1
misauth-ca(12)Adva-auth,𝒜 (𝜆) ≤ + Advdl
Grp,𝒮 (𝜆) + .
𝑝𝑝
Proof (sketch). Using a PPT algorithm 𝒜 as a subroutine,
we construct a PPT solver 𝒮 of the discrete logarithm
problem on Grp as follows. Given an instance (𝑔, ℎ), 𝒮
runs Setup(1𝜆 ) and chooses 𝑛𝑎 , 𝑛𝑝 as in the experiment𝜆Exprmisauth-ca
a-auth,𝒜 (1 , poly(⋅)). 𝒮 sets 𝑔0 := 𝑔 and ℎ0 := ℎ.
Instead of honestly running AuthKey and PrivKey, 𝒮
randomizes 𝑔 and ℎ to obtain 𝑔𝑙 and ℎ𝑙 for 𝑙 = 1, . . . , 𝑛𝑎 ,as follows. For each 𝑙 = 1, . . . , 𝑛𝑎 , 𝒮 chooses 𝛽𝑙 , 𝛾𝑙 ∈𝑅 ℤ𝑝
and computes 𝑔𝑙 := 𝑔 𝛽𝑙 , ℎ𝑙 := ℎ𝛾𝑙 . Further, 𝒮 chooses asingle 𝜏 ∗ ∈𝑅 ℤ𝑝 . Then for each 𝑙 = 1, . . . , 𝑛𝑎 , 𝒮 chooses∗ 𝑤∗𝑤𝑙∗ ∈𝑅 ℤ𝑝 and computes 𝑋𝑙 := 𝑔𝑙𝜏 ℎ𝑙 𝑙 . The public key PK𝑙is (𝑔𝑙 , ℎ𝑙 , 𝑋𝑙 ).

𝑤∗

𝑋𝑙 = 𝑔𝑙𝜏 ℎ𝑙 𝑙 = 𝑔𝑙𝜏ˆ𝑙 ℎ𝑙𝑤ˆ𝑙 .

(13)

Since 𝒜 learns no information about the exponent expression,(𝜏 ∗ , 𝑤𝑙∗ ) ∕= (𝜏ˆ𝑙 , 𝑤ˆ𝑙 ) holds without the probability at most
1/𝑝. Thus, 𝒮 is able to compute the discrete logarithm as
log𝑔𝑙 (ℎ𝑙 ) = −(𝜏 ∗ − 𝜏ˆ𝑙 )/(𝑤𝑙∗ − 𝑤ˆ𝑙 ) and hence, log𝑔 (ℎ) =−(𝛽𝑙 /𝛾𝑙 )(𝜏 ∗ − 𝜏ˆ𝑙 )/(𝑤𝑙∗ − 𝑤ˆ𝑙 ), without the probability at
most 1/𝑝. The probability evaluation (12) follows from Reset
Lemma [6] (Lemma 3.1).
V. D ISCUSSION
In this section, we discuss the security proof of Theorem 3,
a generalization of our proof system to monotone predicates,
and the drawback of vulnerability against collusion attacks.
A. Security Proof Revisited
Roughly speaking, the two properties, the witnessindistinguishability (WI) and the proof-of-knowledge property(PoK), yield the security against concurrent attacks (see [6]).
Our a-auth has WI and PoK, and therefore the concurrent
security follows.

B. Generalization to any Monotone Predicates
Our a-auth in this paper is for proving the knowledge ofthe exponents which satisfy all the public equations. By using
the OR-proof [9], a-auth is used for proving the knowledgeof the exponents which satisfy at least one of the public
equations. The critical change in the protocol of a-auth isto divide the challenge message 𝑐 into 𝑐 = 𝑐1 ⊕ 𝑐2 , where
one of 𝑐1 and 𝑐2 is chosen at random. By using an extended
division technique [3], [4], a-auth is generalized to a systemfor proving the knowledge of witnesses that satisfy any given
monotone predicate.
C. Collusion Attacks
Our a-auth has a drawback that a-auth is not secureagainst collusion attacks. That is, if two secret keys sk𝜏1 ,𝑙 =(𝜏1 , 𝑤𝜏1 ,𝑙 ) and sk𝜏2 ,𝑙 = (𝜏2 , 𝑤𝜏2 ,𝑙 ) issued by a single 𝑙th authority are collected, then the core component 𝛼𝑙 of
the master secret key MSK𝑙 is computed as 𝛼𝑙 = −(𝜏1 −𝜏2 )/(𝑤𝜏1 ,𝑙 − 𝑤𝜏2 ,𝑙 ). To avoid the vulnerability, there are two
possible countermeasures by real operations. One is for theauthority to update the core component 𝛼𝑙 , and reissue theprivate secret keys to provers. The other is to make a premisethat collecting private identity strings {𝜏𝑚 } causes somecritical issue like in the case as the social security numbers in
USA.
VI. C ONCLUSION
We proposed an anonymous authentication scheme a-authwith a feature that various authorities can admit a person or athing without a central authority. The building blocks of ourscheme are the Okamoto identification scheme OkamWIPoK
and the Pedersen commitment scheme PedCom. The witnessindistinguishability and the proof-of-knowledge property of
OkamWIPoK and the perfect hiding property of PedCom gave
the anonymity and concurrent security of a-auth. On theother hand, the binding property of PedCom enabled to prove
the knowledge of witnesses that share a common identity
string. a-auth does not need costly pairing computation,and hence our scheme is suitable for IoT devices with lesscomputational resource.
It is expected that we can exit the drawback of vulnerability
against collusion attacks by employing (and paying the costof) the pairing technique of the Groth-Sahai non-interactive
witness-indistinguishable proof system [11] and commitments
to group elements [1]. We leave the construction as our future
work.
ACKNOWLEDGMENT
This work is partially supported by kakenhi Grant-in-Aid
for Scientific Research (C) JP15K00029 from Japan Society
for the Promotion of Science.

R EFERENCES[1] M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, and M. Ohkubo,“Structure-preserving signatures and commitments to group elements,”
in Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology
Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings,
2010, pp. 209–236. [Online]. Available: http://dx.doi.org/10.1007/
978-3-642-14623-7 12[2] H. Anada, S. Arita, S. Handa, and Y. Iwabuchi, “Attribute-based
identification: Definitions and efficient constructions,” in Information
Security and Privacy - 18th Australasian Conference, ACISP 2013,
Brisbane, Australia, July 1-3, 2013. Proceedings, 2013, pp. 168–186.
[Online]. Available: http://dx.doi.org/10.1007/978-3-642-39059-3 12[3] H. Anada, S. Arita, and K. Sakurai, “Attribute-based signatures without
pairings via the fiat-shamir paradigm,” in ASIAPKC2014, ser. ACMASIAPKC, vol. 2. ACM, 2014, pp. 49–58.
[4] ——, “Proofs of knowledge on monotone predicates and its application
to attribute-based identifications and signatures,” IACR Cryptology
ePrint Archive, vol. 2016, p. 483, 2016. [Online]. Available:
http://eprint.iacr.org/2016/483[5] M. Bellare and O. Goldreich, “On defining proofs of knowledge,” inAdvances in Cryptology - CRYPTO ’92, 12th Annual International
Cryptology Conference, Santa Barbara, California, USA, August
16-20, 1992, Proceedings, 1992, pp. 390–420. [Online]. Available:
http://dx.doi.org/10.1007/3-540-48071-4 28[6] M. Bellare and A. Palacio, “GQ and Schnorr identification schemes:
Proofs of security against impersonation under active and concurrent
attacks,” in Advances in Cryptology - CRYPTO 2002, 22nd Annual
International Cryptology Conference, Santa Barbara, California, USA,
August 18-22, 2002, Proceedings, 2002, pp. 162–177. [Online].
Available: http://dx.doi.org/10.1007/3-540-45708-9 11[7] J. Camenisch, M. Dubovitskaya, K. Haralambiev, and M. Kohlweiss,“Composable and modular anonymous credentials: Definitions andpractical constructions,” in Advances in Cryptology - ASIACRYPT 2015
- 21st International Conf. on the Theory and Application of Cryptology
and Information Security, Auckland, New Zealand, November 29 December 3, 2015, Proceedings, Part II, 2015, pp. 262–288. [Online].
Available: http://dx.doi.org/10.1007/978-3-662-48800-3 11[8] R. Cramer, “Modular designs of secure, yet practical cyptographic
protocols,” Ph.D. dissertation, University of Amsterdam, Amsterdam,
the Netherlands, 1996.
[9] R. Cramer, I. Damgård, and B. Schoenmakers, “Proofs of partial knowledge and simplified design of witness hiding protocols,” in CRYPTO ’94.
Springer-Verlag, 1994, pp. 174–187.
[10] U. Feige and A. Shamir, “Witness indistinguishable and witness
hiding protocols,” in Proceedings of the 22nd Annual ACM
Symposium on Theory of Computing, May 13-17, 1990, Baltimore,
Maryland, USA, 1990, pp. 416–426. [Online]. Available: http://doi.acm.org/10.1145/100216.100272[11] J. Groth and A. Sahai, “Efficient non-interactive proof systems forbilinear groups,” in Proceedings of the Theory and Applications of
Cryptographic Techniques 27th Annual International Conference on
Advances in Cryptology, ser. EUROCRYPT’08. Berlin, Heidelberg:
Springer-Verlag, 2008, pp. 415–432. [Online]. Available: http://dl.acm.
org/citation.cfm?id=1788414.1788438[12] National Institute of Standards and Technology, “Federal information
processing standard (fips) 186-4, digital signature standard (dss),” 2013,
http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf.
[13] T. Okamoto, “Provably secure and practical identification schemes
and corresponding signature schemes,” in Advances in Cryptology CRYPTO ’92, 12th Annual International Cryptology Conference, Santa
Barbara, California, USA, August 16-20, 1992, Proceedings, 1992, pp.
31–53. [Online]. Available: http://dx.doi.org/10.1007/3-540-48071-4 3[14] T. P. Pedersen, “Non-interactive and information-theoretic secure
verifiable secret sharing,” in Advances in Cryptology - CRYPTO ’91,
11th Annual International Cryptology Conference, Santa Barbara,
California, USA, August 11-15, 1991, Proceedings, 1991, pp. 129–140.
[Online]. Available: http://dx.doi.org/10.1007/3-540-46766-1 9[15] S. Sadiah, T. Nakanishi, and N. Funabiki, “Anonymous credential
system with efficient proofs for monotone formulas on attributes,” inAdvances in Information and Computer Security - 10th International
Workshop on Security, IWSEC 2015, Nara, Japan, August 2628, 2015, Proceedings, 2015, pp. 262–278. [Online]. Available:
http://dx.doi.org/10.1007/978-3-319-22425-1 16