Japan Advanced Institute of Science and Technology
https://dspace.jaist.ac.jp/
Title
An Anonymous Designated Verifier Signature Scheme
with Revocation: How to Protect a Company's
Reputation
Author(s)
Emura, Keita; Miyaji, Atsuko ; Omote, Kazumasa
Citation
Lecture Notes in Computer Science, 6402: 184-198
Issue Date
2010
Type
Journal Article
Text version
author
URL
http://hdl.handle.net/10119/9511
Rights
This is the author-created version of Springer,
Keita Emura, Atsuko Miyaji and Kazumasa Omote,
Lecture Notes in Computer Science, 6402, 2010,
184-198. The original publication is available at
www.springerlink.com,
http://dx.doi.org/10.1007/978-3-642-16280-0_12
Description
Provable Security, 4th International Conference,
ProvSec 2010, Malacca, Malaysia, October 13-15,
2010. Proceedings
Scheme with Revocation: How to Protect a
Company’s Reputation
Keita Emura1, Atsuko Miyaji2, and Kazumasa Omote2
1 Center for Highly Dependable Embedded Systems Technology 2
School of Information Science
Japan Advanced Institute of Science and Technology, 1-1, Asahidai, Nomi, Ishikawa, 923-1292, Japan
{k-emura, miyaji, omote}@jaist.ac.jp
Abstract. There are many cryptographic schemes with anonymity, such
as group signatures. As one important property, anonymity revocation has been introduced. In such schemes, the fact of whether a signer’s
rights have been revoked or not is important additional information. For
example, if a third party knows that there are many revoked members in a company, then the company’s reputation may be damaged in many ways. People may think that there might be many problematic employees
(who have bad behavior-s) in this company, there might be many people who have quit, i.e., the labor environment may not be good, and so on.
To avoid such harmful rumors, in this paper, we propose an Anonymous Designated Verifier Signature (ADVS) scheme with revocation. In ADVS, a designated verifier can only verify a signature anonymously, and a third party cannot identify whether the rights of the signer have been revoked or not. We show two security-enhanced schemes as applications of our scheme: a biometric-based remote authentication scheme, and an identity management scheme.
1
Introduction
Back Ground: There are many cryptographic schemes with anonymity, such
as group signatures [6]. Anonymous schemes are useful to protect a signer’s pri-vacy, and therefore many applications of group signature have been proposed such as the BCPZ (Bringer, Chabanne, Pointcheval, and Zimmer) biometric-based authentication scheme [5], the IMSTY (Isshiki, Mori, Sako, Teranishi, and Yonezawa) identity management scheme [11], and so on. As one important property, anonymity revocation has been introduced [3, 4, 15, 17, 18]. In these revocable group signature schemes, revocation check can be executed by any
entity. Actually, the fact of whether a signer’s rights have been revoked or not
is important additional information. Let a signatory group of a group signature scheme be a company. If a third party knows that there are many revoked mem-bers in this company, then the company’s reputation may be damaged in many ways. For example, someone may think that:
– There might be many problematic employees (who have bad behavior) in this company.
– There might be many people who have quit, i.e., the labor environment may not be good.
In addition, there are possibilities of user privacy exposure, for example: – If the third party knows an employee who left the company three days ago,
and also knows a signer was revoked three days ago, then the signer may be this employee.
Actually, the third party can detect whether a signer was revoked or not by checking whether a value was added to a revocation list RL or not. In this ex-ample, the third party can link signatures made by this employee who has left by executing the revocation check, even if a group signature scheme with backward unlinkability (such as [15, 18]) is used3. This scenario can occur, since (revocable)
group signatures are applied in many applications. As a solution for protecting against damage caused by rumors, we consider to apply a cryptographic primitive with a property that a third party cannot check whether a signer’s rights have already been revoked or not. Someone may think that group signature schemes with Verifier-Local Revocation (VLR) [4, 15, 18] can be applied for this purpose. By hiding a revocation list RL from the third party4, the third party can be
prevented from executing the revocation check. However, there is a problem in this scenario: a revoked user can make a valid group signature which is verified by the third party, since the third party can verify the validity of this signature by using a group public key gpk only (RL is used for the revocation check only). Therefore, VLR group signature schemes are not useful in protecting the com-pany’s reputation. This suggests that it is not enough to restrict the revocation check. As another solution for protecting against damage caused by rumors, we need to apply a cryptographic primitive with properties that not only the third party cannot check whether a signer’s rights have already been revoked or not, but also the third party cannot check whether a signature is valid or not. As a candidate for this purpose, Designated Verifier Signature (DVS) [7, 10, 13, 14, 16, 20–22] is nominated, since a signer can indicate a designated verifier. Especially, strong DVS has been proposed [13, 14] which enables protection of the signer’s anonymity from a third party. However, in the verification phase of strong DVS, a designated verifier verifies a signature with the public key of a signer and the secret key of the designated verifier. This means that these schemes do not pro-vide the signer anonymity from the designated verifier, and this is a difference between DVS and group signatures. In addition, DVS does not have the revo-cation property. To sum up, no previous group signature and DVS schemes can be applied to protect the company’s reputation.
3 Note that backward unlinkability means that even after a signer’s rights are revoked,
signatures made by the signer before the revocation remain anonymous.
4 In VLR schemes, a verifier verifies a group signature by using a group public key
gpk, and checks whether the rights of the signer have been revoked or not by using RL. A signer does not have to obtain RL to sign.
Our Contribution: In this paper, by applying the designated verification
prop-erty of DVS, we propose a way to protect the company’s reputation. By indi-cating a designated verifier, (1) a third party cannot check whether a signature is valid or not, and (2) the third party cannot check whether a signer’s rights have already been revoked or not, and (3) no entity (except the opening man-ager OM, which is defined later) can determine who a signer is. We call this signature primitive Anonymous Designated Verifier Signature (ADVS) scheme with revocation. We compare these functions with other primitives in Table 1.
Table 1. Function Comparisons
Signer Designated Designated Anonymity Verification Revocation Check
DVS [12] no yes no
Strong DVS [13, 14] yes∗ yes no
Revocable Group Signature [3, 4, 15, 17, 18] yes no no
Our ADVS yes yes yes
∗ From a third party only
The property (1) is the same concept as in DVS schemes. The property (2) is a difference between revocable group signatures and our scheme. As a differ-ence between strong DVS and our signer-anonymous DVS scheme, our scheme protects the signer anonymity from the designated verifier (property (3)). We provide formal definitions of ADVS, and prove our scheme along with these def-initions. Our ADVS scheme can be applied to protecting company’s reputation scenario.
Related works: The concept of designated verifier proof was introduced in
Jakobsson, Sako, and Impagliazzo [12] (called JSI scheme), where a specific des-ignated verifier can only verify the validity of proofs made by a prover’s secret key and a verifier’s public key. In the JSI scheme, although any entity can verify the validity of a proof, this entity cannot distinguish whether the proof was made by a prover or not. The designated verifier can make the same proof, and only the prover and the designated verifier know who is the actual prover. The JSI scheme uses the or proof technique [8], namely, the actual signer knows the secret key of the signer or the secret key of the designated verifier. A DVS signature can be achieved [7] by using the ring signature scheme with a two-person group (namely, members are the signer and the designated verifier only). From the viewpoint of a third party, nobody knows who the actual signer is, although the third party can verify the signature. There are DVS schemes such that the va-lidity of a signature can only be verified by a designated verifier by using his/her secret key (e.g., [10, 13, 22]). In these schemes, a third party cannot verify the validity of a signature. Designated revocation check property has been consid-ered in [9]. However, that paper did not define formal security requirements, and there is a flaw whereby a designated verifier can link two signatures by using
his/her secret key. A designated group signature scheme, which enables both signer anonymity and designated verifier property5, has not been proposed yet.
Organization : The paper is organized as follows: Security definitions of ADVS
are presented in Section 3. Our proposed ADVS scheme is described in Section 4. The security proofs are presented in Section 5. Applications of our ADVS scheme to the BCPZ biometric-based authentication scheme [5] and the IMSTY identity management scheme [11] are presented in Section 6.
2
Preliminary
In this section, we show definitions of bilinear groups and complexity assump-tions. Note that x∈RS means x is randomly chosen for a set S.
2.1 Bilinear Groups
Definition 1. (Bilinear Groups) Bilinear groups and a bilinear map are
de-fined as follows:
1. G and GT are cyclic groups of prime order p.
2. g is a generator of G.
3. e is an efficiently computable bilinear map e :G×G → GT with the following
properties.
– Bilinearity : for all u, u0, v, v0∈ G, e(uu0, v) = e(u, v)e(u0, v) and e(u, vv0) =
e(u, v)e(u, v0).
– Non-degeneracy : e(g, g)6= 1GT (1GT is theGT’s unit).
2.2 Complexity Assumptions
Definition 2. (DLIN assumption) [3] The Decision Linear (DLIN) problem
in G is a problem, for input of a tuple (u, v, h, uα, vβ, Z)∈ G6 where α, β∈ Zp
are random values, to decide whether Z = hα+β or not. An algorithmA has
ad-vantage in solving DLIN problem inG if AdvDLIN(A) := |Pr[A(u, v, h, uα, vβ, hα+β) =
0]− Pr[A(u, v, h, uα, vβ, hz) = 0]| ≥ (κ), where hz ∈ G \ {hα+β}. We say that
the DLIN assumption holds in G if no PPT algorithm has an advantage of at
least in solving the DLIN problem in G.
Definition 3. SDH assumption) [2, 3] The q-Strong Diffie-Hellman
(q-SDH) problem inG is a problem, for input of a (q + 1) tuple (g, gγ,· · · , gγq)∈
Gq+1where γ∈ Z
pis a random value, to compute a tuple (x, g1/(γ+x))∈ Zp×G.
An algorithm A has an advantage in solving the q-SDH problem in G if
Pr[A(g, gγ,· · · , gγq
) = (x, g1/(γ+x))] ≥ . We say that the q-SDH assumption
holds in G if no PPT algorithm has an advantage of at least in solving the
q-SDH problem inG.
5 Note that the concept of designated group signature (called ML scheme) proposed
in [16] is different from this concept: the ML scheme enables the verifier anonymity, where designated verifiers are indicated.
3
Definitions of ADVS
In this section, we define ADVS and its security requirements. The ADVS scheme consists of six algorithms, Setup, KeyGenS, KeyGenV, Sign, Verify, and Revoke.
The group public key gpk and the group secret key gsk are obtained by execut-ing Setup(1κ), where κ is the security parameter. A signer public key spk and a signer secret key (which is also called a membership certificate) ssk are obtained by executing KeyGenS(gpk, gsk). A verifier public key vpk and a verifier secret
key vsk are obtained by executing KeyGenV(1κ). For a message M , a designated
signature σ is obtained by executing Sign(gpk, ssk, vpk, M ). σ is verified by ex-ecuting Verify(gpk, vsk, M, σ). If both (1) σ is a valid signature, and (2) σ was made by using vpk (corresponding to vsk), then 1 is output, and 0, otherwise. A designated signature is valid means that (1) a signer has a membership certificate
ssk issued by GM , and (2) the rights of the signer have not been revoked.
Mem-bership revocation is done by executing Revoke(gpk, gsk, ssk, RL), where RL is the revocation list. The Revoke algorithm outputs the updated RL. We assume three entities, the group manager GM , a signer, and a designated verifier, which runs (Setup, KeyGenS, Revoke), Sign, and (KeyGenV, Verify), respectively.
Next, we define the security requirements: Unforgeability, Non-transferability, and Signer anonymity. The DVS scheme is said to be unforgeable if the advan-tage is negligible for any probabilistic polynomial time (PPT) adversary A in the following experiment. In this experiment, A can access the signing oracle
OSign(ssk∗,vpk), where for an input message M , the signing oracle returns a
sig-nature σ made by ssk∗ and designated to vpk, and appends (M, σ) to the set of signatures SigSet. In addition,A can access the verification oracle OVerify(vsk).
For the input of the message/signature pair (M, σ),OVerify(vsk)returns the result
of Verify(gpk, vsk, M, σ). In addition, A can access the corruption oracle Ocorr.
For the input of the identity of signer i,Ocorrreturns sski, and appends i to the
set of corrupted users CU. Note thatA cannot query i∗to the corruption oracle, where i∗ is the target signer (who manages ssk∗). In addition,A can access the revocation oracle Orevoke. For the input of the identity of signer i, Orevoke runs
Revoke(gpk, gsk, sski, RL). Note thatA cannot query i∗ to the revocation
ora-cle. Finally, A outputs (M∗, σ∗)6∈ SigSet. To guarantee that no sski (i∈ CU)
were used to compute (M∗, σ∗), Revoke(gpk, gsk, sski, RL) is executed for all
corrupted users i.
Definition 4. Unforgeability
AdvAUF(κ) = Pr[(gpk, gsk)← Setup(1κ); CU→ ∅; SigSet → ∅; (vpk, vsk) ← KeyGenV(1κ);
(i∗, State)← AOVerify(vsk )(·),Ocorr(·),Orevoke(·)(gpk, vpk);
(spk∗, ssk∗)← KeyGenS(gpk, gsk);
(M∗, σ∗)← AOSign(ssk ∗ ,vpk )(·),OVerify(vsk )(·),Ocorr(·),Orevoke(·)(gpk, spk∗, vpk, State);
∀i ∈ CU, Revoke(gpk, gsk, sski, RL); (M∗, σ∗)6∈ SigSet;
Next, we define Non-transferability. Non-transferability means that a des-ignated verifier cannot produce evidence which convinces a third party that a signature was actually computed by the signer. The ADVS scheme is said to be non-transferable if the advantage is negligible for any PPT adversary A in the following experiment. Intuitively, there exists a simulated signing algorithm Sign0 for which the distribution of (M, Sign(gpk, ssk, vpk, M )) and the distribution of (M, Sign0(gpk, spk, vsk, M )) are indistinguishable.
Definition 5. Non-transferability
AdvANon-Trans(κ) = Pr[(gpk, gsk)← Setup(1κ); (spk, ssk)← KeyGenS(gpk, gsk);
(vpk, vsk)← KeyGenV(1κ); (M∗, State)← A(gpk, spk, ssk, vpk, vsk); µ ∈R{0, 1}; σ0← Sign(gpk, ssk, vpk, M∗); σ1← Sign0(gpk, spk, vsk, M∗); µ0← A(σµ, State); µ = µ0 ] − 1/2
Next, we define Signer anonymity. The ADVS scheme is said to be signer-anonymous if the advantage is negligible for any PPT adversary A in the fol-lowing experiment. Intuitively, Signer anonymity means thatA with vsk cannot determine who the actual signer is. This suggests that even if a malicious desig-nated verifier opens its own secret key vsk, Signer anonymity is still effective.
Definition 6. Signer anonymity
AdvASign-Anon(κ) = Pr[(gpk, gsk)← Setup(1κ); (spk0, ssk0)← KeyGenS(gpk, gsk);
(spk1, ssk1)← KeyGenS(gpk, gsk); (vpk, vsk)← KeyGenV(1κ); (M∗, State)← A(gpk, spk0, ssk0, spk1, ssk1, vpk, vsk) µ∈R{0, 1}; σµ← Sign(gpk, sskµ, vpk, M∗); µ0← A(σµ, State); µ = µ0 ] − 1/2
4
The Proposed Scheme
In this section, we propose an Anonymous Designated Verifier Signature (ADVS) scheme with revocation. Let SP K be a Signature based on a Proof of Knowledge and DSig(sigkey, M ) be a digital signature of a message M under a signing key
sigkey. DSig(sigkey, M ) is verified by using a verification key, verkey. We use DSig(sigkey, M ) to guarantee that GM updates RL. Intuitively, our
construc-tion is as follows: A signer computes an “or proof”, namely, SPK with knowledge of either part-1: an actual signer knows the secret key of the signer (this is the short group signature proposed by Boneh et al. [3]), or part-2: the actual signer knows the secret key of a designated verifier. This construction is needed to achieve Non-transferability. In addition, the signer encrypts a part of the part-1 SPK using the public key of the designated verifier. We improve the revocation algorithm of the Nakanishi-Funabiki group signature [18] to satisfy the property that a third party cannot check whether a signer has already been revoked or not.
Protocol 1. Our ADVS scheme
Setup(1κ): Choose a prime number p, a bilinear group (G, G
T) with order p,
generators g, h, u, v, f ∈R G, and γ ∈R Zp, and compute ω = gγ. Output
gpk = (e, (G, GT), g, h, u, v, f, ω, H, verkey) and gsk = (γ, sigkey), where H
is a cryptographic hash function from{0, 1}∗ toZp.
KeyGenS(gpk, gsk) Choose x ∈R Zp, and compute A = g
1
x+γ. Output spk = ∅
and ssk = (A, x).
KeyGenV(1κ): Choose xv, yv, zv, rv ∈R Zp, and compute hd = gxvyvrv, ud =
gyvrv, v
d = gxvrv, and td = vzv. Output vpk = (hd, ud, vd, td) and vsk =
(xv, yv, zv).
Sign(gpk, ssk, vpk, M ): Choose a, b, α, β, δ ∈R Zp, and compute T1= A· hα+β,
T2 = uα, T3 = vβ, D1 = T1· ha+bd , D2 = uad, D3 = vdb, S1 = fxi+δ, and
S2= tδd. Let τ = αx and λ = βx. Compute SPK as follows:
– Choose rx, rα, rβ, rδ, rτ, rλ, szv, cv ∈RZp. – Compute Rv = vszvt−cd v, Rs,1 = urα, Rs,2 = vrβ, Rs,3 = e(T1, g)rx · e(h, ω)−rα−rβ·e(h, g)−rτ−rλ, R s,4= T2rx·u−rτ, Rs,5= T3rx·v−rλ, Rs,6= frx+rδ, and R s,7= trdδ. Compute c = H(T1, T2, T3, D1, D2, D3, S1, S2, Rv, Rs,1, . . ., Rs,7, M ), cs= c−cv mod p, sx= rx+ csx, sα= rα+ csα, sβ= rβ+ csβ, sδ = rδ+ csδ, sτ = rτ+ csτ , and sλ= rλ+ csλ. – Output σ = (T2, T3, D1, D2, D3, S1, S2, cs, cv, sx, sα, sβ, sδ, sτ, sλ, szv).
Revoke(gpk, gsk, ssk, RL): Let ssk = (A, x). Compute vxand CertA,x= DSig(sigkey, vx).
Output the updated list RL∪ (vx, CertA,x).
Verify(gpk, vsk, M, σ, RL): Output 1 if both the following verification check and
revocation check algorithms output 1, and output 0, otherwise.
Verification check: Compute T10 = D1/(Dx2vD
yv
3 ), R0v = vszvt−cd v, R0s,1=
usαT−cs
2 , R0s,2= vsβT3−cs, R0s,3= e(T10, g)sx·e(h, ω)−sα−sβ·e(h, g)−sτ−sλ(
e(T10,ω) e(g,g) ) cs, R0s,4 = Tsx 2 · u−sτ, R0s,5 = T sx 3 · v−sλ, Rs,60 = gsx+sδS1−cs, and R0s,7 = tsδ d S2−cs. Output 1, if cs+ cv = H(T10, T2, T3, D1, D2, D3, S1, S2, R0v,
R0s,1, . . ., R0s,7, M ) holds, and output 0, otherwise.
Revocation check: For all (vx, Cert
A,x) ∈ RL, verify CertA,x by using
verkey, and check e(S1, td)
?
= e((vx)zvS
2, f ). If there exists a pair (vx, CertA,x)∈
RL, where CertA,x is a valid certificate and the above condition holds,
then output 1. Otherwise, output 0.
Note that e(S1, td) = e(fx+δ, vzv) = e(f, v)zv(x+δ)and e((vx)zvS2, f ) = e(vzvxvzvδ, f ) =
e(v, f )zv(x+δ) hold, and e((vx)zvS
2, f ) can only be computed by the designated
Next, we describe the simulated signing algorithm as follows:
Protocol 2. The simulated signing algorithm
Sign0(gpk, spk, vsk, M ): Choose T2, T3, D1, D2, D3, S1, S2 ∈R G. Compute SPK
as follows:
– Choose sx, sα, sβ, sδ, sτ, sλ, rzv, cs∈RZp.
– Compute Rv = vrzv, Rs,1= usαT2−cs, Rs,2= vsβT3−cs, Rs,3= e(T1, g)sx·
e(h, ω)−sα−sβ · e(h, g)−sτ−sλ(e(T1,ω)
e(g,g) ) cs, R s,4 = T2sx· u−sτ, Rs,5 = T3sx· v−sλ, R s,6 = gsx+sδS1−cs, and Rs,7 = tsdδS−c s 2 . Compute c = H(T1, T2, T3, D1, D2, D3, S1, S2, Rv, Rs,1, . . ., Rs,7, M ), cv= c− csmod p, and szv = rzv + cvzv. – Output σ = (T2, T3, D1, D2, D3, S1, S2, cs, cv, sx, sα, sβ, sδ, sτ, sλ, szv). Obviously, a signature generated by the Sign0 algorithm is a valid signature. Therefore, our ADVS scheme satisfies Non-transferability.
Can RL be publicly opened?: In our scheme, RL is used to execute the
Verify algorithm. Therefore, RL is given to verifiers only. Even if RL is given to a third party, the third party cannot execute the revocation check. However, a different problem occurs. If RL is publicly opened, then the third party can obtain the number of revoked signers. To prevent this, in a natural way, dummy certificates can be used as follows: Let N be the number of group members. Then
GM chooses vi0 ∈R G, where i = 1, 2, . . . , N − |RL|. Note that this procedure
can deal with a dynamic update of RL, namely, dummy certificates are chosen for each revocation. Although the cost of revocation check and updating the list are increased, RL can be opened. However, as with VLR schemes, a signer does not need RL to make a signature. Therefore, practically, we can assume that
RL is given to verifiers only. In this setting, we can prevent a revoked user from
making a valid signature that is verified by the third party, since the third party cannot verify the validity of a signature by using only gpk. However, in VLR schemes, the third party can verify the validity of a signature by using gpk only, since RL is used for the revocation check only. Therefore, VLR group signature schemes are not used (under the assumption that RL is given to verifiers only), since a revoked user could make a valid group signature which could be verified by the third party. This is a superior point of our scheme compared with VLR schemes.
The Open algorithm: The Open algorithm is described as follows: A ←
Open(gpk, gsk, (M, σ)), where A is a signer secret key. Let ξ1 := loguh and
ξ2 := logvh. By adding (ξ1, ξ2) to gsk, GM can compute T1/(T
ξ1 2 T
ξ2
3 ) if T1 is
given. Therefore, the designated verifier needs to send (T10, T2, T3) to GM to
re-quest the Open procedure. If the opening and issuing roles need to be separated, then only the opening key osk = (ξ1, ξ2) is given to the Opening Manager OM .
A designated verifier sends (T10, T2, T3) to OM . If (T10, T2, T3) is included in a
signature computed by the simulated signing algorithm Sign0, then the Open al-gorithm does not work, since (T10, T2, T3) is not a valid ciphertext of a membership
not satisfied from the viewpoint of OM . This suggests OM can reveal not only the identity of a signer, but also information about who the actual signer is.
5
Security Analysis
In this section, we prove that our scheme satisfies security requirements defined in Section 3.
Theorem 1. Our scheme satisfies Unforgeability under the q-SDH assumption.
Proof. Let A be an adversary to break Unforgeability of our scheme. We
con-struct an algorithmB to break the q-SDH problem: Let (g1, g1γ,· · · , g
γq
1 ) be an
instance of q-SDH problem. Let qn be the number of signers (qn≤ q). W.l.o.g.,
we assume that qn= q.B chooses distinct x1, . . . , xq−1 ∈RZp, and sets f (X) :=
∏q−1
i=1(X + xi) :=
∑q−1
i=0αiXi, where α0, . . . , αq−1∈ Zpare the coefficients of the
polynomial f . B chooses θ ∈R Zp, and computes g0 :=
∏q−1 i=0(g γi 1 ) αiθ = gθf (γ) 1 and g00 := ∏qi=1(g1γi)αi−1θ = gθγf (γ) 1 = (g0)γ. Let fi(X) := f (X)/(γ + xi) = ∏q−1 j=1,j6=i(X + xj) := ∑q−2
j=0βiXj, where β0, . . . , βq−2 ∈ Zp are the coefficients
of the polynomial fi. Then Ai =
∏q−2 j=0(g γj 1 )βjθ = g θfi(γ) 1 = (g0)1/(γ+xi) is a
signer public key. B sets g := g0 and ω := g00 = gγ. B chooses h, u, v, f ∈ R G,
xv, yv, zv, rv ∈R Zp, and computes hd = gxvyvrv, ud = gyvrv, vd = gxvrv, and
td = vzv.B gives gpk = (e, (G, GT), g, h, u, v, f, ω, H) and vpk = (hd, ud, vd, td)
to A, where H : {0, 1}∗→ Zp is a random oracle. In addition,B selects a
sign-ing key of DSig sigkey, and opens a correspondsign-ing verification key verkey. For verification queries and signing queries issued byA, B can answer these queries perfectly, sinceB has vsk = (xv, yv, zv), and can execute the simulated signing
algorithm Sign0. For a corruption query i, B returns (Ai, xi) to A. For a
revo-cation query i,B computes vxi and Cert
Ai,xi = DSig(sigkey, v
xi), and outputs updated list RL∪(vxi, Cert
Ai,xi).A outputs (M∗, σ∗). Let σ∗= (T2, T3, D1, D2, D3, S1, S2, cs, cv, sx, sα, sβ, sδ, sτ, sλ, szv).B computes T1= D1/(D xv 2 D yv 3 ),
and can obtain (T1, T2, T3, cs, sα, sβ, sτ, sλ). By using the Forking Lemma [19],B
can obtain (T1, T2, T3, c0s, s0α, s0β, s0τ, s0λ), where cs6= c0s, with non-negligible
prob-ability. By using Lemma 4.4 of [3], we can extract a new SDH tuple ( ˜A, ˜x) as
follows: Let ∆cs := cs− c0s, ∆sα:= sα− s0α, ∆sβ := sβ− s0β, ∆sx := sx− s0x,
∆sτ := s−s0τ, ∆sλ := sλ− s0λ, ˜α := ∆sα/∆cs, ˜β := ∆sβ/∆cs, ˜x := ∆sx/∆cs,
and ˜A := T1· h−˜α− ˜β. Therefore,B can solve q-SDH problem. ut
Theorem 2. Our scheme satisfies Signer anonymity under the DLIN
assump-tion in the random oracle model.
To prove Theorem 2, we apply the BBS short group signature scheme and CPA-full anonymity experiment. For the sake of clarity, we introduce the BBS scheme and the definition of CPA-full anonymity in Appendices A.1 and A.2, respectively.
Proof. Let A be an adversary to break Signer anonymity of our scheme. We
construct an algorithmB to break CPA-full-anonymity of the BBS short group signature scheme with 2-person group as follows: First, the challenger C sends (e, (G, GT), g, ω, H), ssk0, and ssk1toB. B chooses h, u, v, f ∈RG, xv, yv, zv, rv∈R
Zp, and computes hd = gxvyvrv, ud = gyvrv, vd = gxvrv, and td = vzv.B gives
gpk = (e, (G, GT), g, h, u, v, f, ω, H), vpk = (hd, ud, vd, td), vsk = (xv, yv, zv),
ssk0, and ssk1, where H :{0, 1}∗→ Zpis a hash function. In addition,B selects a
signing key of DSig sigkey, and opens a corresponding verification key verkey.A sends M∗toB. B forwards M∗toC, and obtains σ∗= (T1, T2, T3, cs, sx, sα, sβ, sτ, sλ).
B chooses sδ, rzv, cv∈RZp and S1, S2∈RG. B computes Rv = v
rzvt−cv
d , Rs,1=
usαT−cs
2 , Rs,2 = vsβT3−cs, Rs,3= e(T1, g)sx·e(h, ω)−sα−sβ·e(h, g)−sτ−sλ(e(Te(g,g)1,ω))cs,
Rs,4 = T2sx· u−sτ, Rs,5 = T3sx · v−sλ, Rs,6 = gsx+sδS1−cs, and Rs,7 = tsdδS−c
s
2 .
B also computes szv = rzv + cvzv, and sets c := H(T1, T2, T3, D1, D2, D3, S1, S2, Rv, Rs,1, . . ., Rs,7, M∗), where c = cv+ csmod p . B sends the challenge
signature (T2, T3, D1, D2, D3, S1, S2, cs, cv, sx, sα, sβ, sδ, sτ, sλ, szv) to A.
A outputs µ0. Finally,B outputs µ0 as the answer to the anonymity game of the
BBS group signature scheme. Therefore, our scheme satisfies Signer anonymity under the DLIN assumption, since the BBS group signature scheme satisfies anonymity under the DLIN assumption in the random oracle model. ut The following theorem clearly holds, since there exists the simulated signing algorithm Sign0, and OM with a linear encryption secret key (ξ1, ξ2) can reveal
information about who the actual signer is.
Theorem 3. Our scheme satisfies Non-transferability under the DLIN
assump-tion.
6
Applications of our ADVS scheme
In this section, we show the applications of our scheme to a biometric-based re-mote authentication scheme (the BCPZ scheme [5]) and an identity management scheme (the IMSTY scheme [11]).
6.1 Biometric Authentication
The BCPZ scheme [5] is based on the Boneh and Shacham VLR group sig-nature [4]. H is a human user (who authenticates himself/herself to a service provider P by using his/her biometric data b preserved on a plastic card). A sensor client S extracts human user’s biometric trait (e.g., iris is used in the BCPZ scheme), and communicates with P, so that the user will be authenti-cated by P. P executes KeyGenV, and obtains vpk and vsk. A card issuer I
(with a group secret key γ) issues a card to a human user, and (A = gx+γ1 , b) is preserved in the card, where b is biometric data of the user and x = Hash(b). In addition,I generates RL if malicious behavior occurs or a user loses his/her cards. First,P sends the challenge M to S. S gets (A, b) and the fresh biometric
trait b0from a human user (with a card), confirms b0∼ b (which indicates that b0 and b are acquired from the same biometric source), and computes x = Hash(b) and a group signature σ by using a secret x and vpk. P verifies (M, σ), and checks whether the user is a malicious user or not, by using RL. In the (original) BCPZ scheme, a third party (with RL) may think that:
– There might be many malicious behaviors in this company.
– There might be many lost cards, i.e., goods management may deteriorate in this company.
and so on. This is where our ADVS scheme comes into effect. We illustrate a modified BCPZ scheme in Fig.1.
A Human User H (A, b) A Card IssuerI
A SensorS A Service ProviderP (vpk, vsk)
RL
(A, b) (From Card)
b0 ?∼ b, x = Hash(b) Challenge M σ = Sign(gpk, (A, x), vpk, M ) (gpk, gsk) σ Verify(gpk, vsk, M, σ, RL)= 1? b0 (Scanning) Issue
Fig. 1: Modified BCPZ scheme
We assume that RL is given to P only, or that RL is opened with dummy certificates. The service providerP does not have to manage the identity of each user. Users do not have to manage any extra values (e.g., passwords), since they only use their own biometric traits and their cards.
6.2 Identity management
An outsourcing business using group signature has been proposed in [11] (called the IMSTY scheme). In existing systems (which do not apply group signature), authentication servers store the list of identities of users. In group signature set-tings, authentication servers only have to verify users by using the group public key gpk, and do not have to manage the list of identities of users ID-list. There-fore, the risk of leaking user information (i.e., the list of identities of users) can be minimized, and this is the merit of using group signature in identity manage-ment. In the IMSTY scheme, the role of Group Manager GM is separated into three roles: Issuing Manager IM , User-Revocation Manager RM , and Opening Manager OM . IM issues membership certificates for users. When a user requests the service, the user makes a group signature σ, and sends it to Outsourcee who is in charge of providing the service to legitimate users. Outsourcee verifies σ,
provides the service if this signature is valid, and stores σ into the usage log
U Log. After a certain interval, Outsourcee sends U Log to OM who can open
group signatures. OM charges the users who have already used the service. If a user does not pay a fee, then OM announces the identity of this user to RM .
RM updates the revocation list RL when a user wants to leave the group, or
when a user does not pay a fee. ID-list is managed by IM , and it is updated when a new user joins. IM sends ID-list = {(A, x), UserID} to OM, namely Outsourcee does not have to manage ID-list. In the (original) IMSTY scheme, a third party may think that:
– There might be many seceders, i.e., this service may not be interesting. – Signer’s rights have been revoked, maybe, he/she did not pay the service fee.
That is to say, the service fee may be expensive.
and so on. This is where our ADVS scheme comes into effect. GM of our ADVS scheme also can be separated into three roles, since γ (which is used to issue membership certificates) is not used for executing the Revoke algorithm, and the Open algorithm is independent of other procedures. We illustrate a modified IMSTY scheme in Fig.2.
Issuing Manager IM (A, x) γ User Request σ Service Outsourcee vpk, vsk, RL σ = Sign(gpk, (A, x), vpk, M ) Revocation Manager RM Opening Manager OM Verify(gpk, vsk, M, σ, RL)= 1? U Log ={(T10, T2, T3)}, (ξ1, ξ2)
Charge the service fee
sigkey, verkey, x
Open(gpk, (T10, T2, T3), (ξ1, ξ2))
Revoke(gpk, gsk, x, RL)
ID-list ={(A, x), UserID}
Notify x
Fig. 2: Modified IMSTY scheme
We assume that RL is given to Outsourcee only, or that RL is opened with dummy certificates, and all entities know the group public key gpk. In the modi-fied IMSTY scheme, (T10, T2, T3) is stored into U Log, since the signature validity
has already been checked by Outsourcee, and OM needs (T10, T2, T3) only to
ex-ecute the Open procedure. After a certain interval, Outsourcee sends U Log to
OM , and OM charges the users who have already used the service. If a user does
not pay a fee, then OM notifies x of this user to RM . RM updates the revoca-tion list RL, and sends it to Outsourcee, or opens RL with dummy certificates
7
Conclusion
In this paper, we propose an ADVS scheme with revocation. Our ADVS scheme satisfies not only designated verification and Signer anonymity, but also desig-nated revocation check. To the best of our knowledge, our scheme is the first provably secure scheme with designated revocation check. Our scheme can be applied to the protecting company’s reputation scenario. Neither strong DVS nor revocable group signature schemes can be used in this situation. Our ADVS scheme can be directly and easily applied to the BCPZ scheme and the IMSTY scheme. From this fact, our ADVS scheme can be directly and easily applied to many cryptographic schemes based on (revocable) group signatures, when designated property is required.
Acknowledgements
The authors would like to thank anonymous reviewers of ProvSec 2010 for their invaluable comments. The first author Keita Emura is supported by the Center for Highly Dependable Embedded Systems Technology as a Postdoc researcher.
References
1. Mihir Bellare, Daniele Micciancio, and Bogdan Warinschi. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions. In EUROCRYPT, pages 614–629, 2003.
2. Dan Boneh and Xavier Boyen. Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptology, 21(2):149–177, 2008.
3. Dan Boneh, Xavier Boyen, and Hovav Shacham. Short group signatures. In
CRYPTO, pages 41–55, 2004.
4. Dan Boneh and Hovav Shacham. Group signatures with verifier-local revocation. In ACM Conference on Computer and Communications Security, pages 168–177, 2004.
5. Julien Bringer, Herv´e Chabanne, David Pointcheval, and S´ebastien Zimmer. An application of the Boneh and Shacham group signature scheme to biometric au-thentication. In IWSEC, pages 219–230, 2008.
6. David Chaum and Eug`ene van Heyst. Group signatures. In EUROCRYPT, pages 257–265, 1991.
7. Sherman S. M. Chow and Duncan S. Wong. Anonymous identification and designated-verifiers signatures from insecure batch verification. In EuroPKI, pages 203–219, 2007.
8. Ronald Cramer, Ivan Damg˚ard, and Berry Schoenmakers. Proofs of partial knowl-edge and simplified design of witness hiding protocols. In CRYPTO, pages 174–187, 1994.
9. Keita Emura, Atsuko Miyaji, and Kazumasa Omote. A certificate revocable anony-mous authentication scheme with designated verifier. In ARES, pages 769–773, 2009.
10. Xinyi Huang, Willy Susilo, Yi Mu, and Futai Zhang. Short (identity-based) strong designated verifier signature schemes. In ISPEC, pages 214–225, 2006.
11. Toshiyuki Isshiki, Kengo Mori, Kazue Sako, Isamu Teranishi, and Shoko Yonezawa. Using group signatures for identity management and its implementation. In Digital
Identity Management, pages 73–78, 2006.
12. Markus Jakobsson, Kazue Sako, and Russell Impagliazzo. Designated verifier proofs and their applications. In EUROCRYPT, pages 143–154. Springer-Verlag, 1996. LNCS 1070.
13. Fabien Laguillaumie and Damien Vergnaud. Designated verifier signatures: Anonymity and efficient construction from any bilinear map. In SCN, pages 105– 119, 2004.
14. Fabien Laguillaumie and Damien Vergnaud. Multi-designated verifiers signatures: anonymity without encryption. Inf. Process. Lett., 102(2-3):127–132, 2007. 15. Benoit Libert and Damien Vergnaud. Group signatures with verifier-local
revoca-tion and backward unlinkability in the standard model. In CANS, pages 498–517, 2009.
16. Chunbo Ma and Jianhua Li. Adaptable designated group signature. In ICIC (1), pages 1053–1061, 2006.
17. Toru Nakanishi, Hiroki Fujii, Yuta Hira, and Nobuo Funabiki. Revocable group signature schemes with constant costs for signing and verifying. In Public Key
Cryptography, pages 463–480, 2009.
18. Toru Nakanishi and Nobuo Funabiki. A short verifier-local revocation group signa-ture scheme with backward unlinkability. IEICE Transactions, 90-A(9):1793–1802, 2007.
19. David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures. J. Cryptology, 13(3):361–396, 2000.
20. Siamak Fayyaz Shahandashti and Reihaneh Safavi-Naini. Construction of uni-versal designated-verifier signatures and identity-based signatures from standard signatures. In Public Key Cryptography, pages 121–140, 2008.
21. Ron Steinfeld, Huaxiong Wang, and Josef Pieprzyk. Efficient extension of standard schnorr/RSA signatures into universal designated-verifier signatures. In Public Key
Cryptography, pages 86–100, 2004.
22. Yaling Zhang, Jing Zhang, and Yikun Zhang. Multi-signers strong designated verifier signature scheme. In SNPD, pages 324–328, 2008.
Appendix
A.1 BBS Short Group Signature
In this appendix, we introduce the BBS short group signature [3]. Let (G, GT)
be a bilinear group with pairing e :G × G → GT, and P = {U1, . . . , Un} be a
set of participants.
Protocol 3. BBS Short Group Signature [3]
KeyGen(1κ): Choose g, h ∈ G and γ, ξ
1, ξ2 ∈ Zp, and set u = hξ1, v = hξ2, and
ω = gγ. For a user U
i ∈ P, choose xi ∈R Zp, and compute Ai = g
1
xi+γ.
Output the group public key gpk = (e, (G, GT), g, ω, H), the group secret
key gsk = γ, and user secret keys {sski = (xi, Ai)}Ui∈P, where H is a
GSig(gpk, sski, M ): Choose α, β, rx, rα, rβ, rτ, rλ ∈R Zp, and compute T1= Ai· hα+β, T 2= uα, T3= vβ, R1= urα, R2= vrβ, R3= e(T1, g)rx·e(h, ω)−rα−rβ· e(h, g)−rτ−rλ, R 4= T2rxu−rτ, R5= T3rxv−rλ, c = H(M , T1, T2, T3, R1, . . ., R5), sx = rx+ csx, sα = rα+ csα, sβ = rβ + csβ, sτ = rτ + csτ , and sλ= rλ+ csλ. Output σ = (T1, T2, T3, sx, sα, sβ, sτ, sλ). GVer(gpk, σ, M ): Compute R01 = usαT−c 2 , R20 = vsβT3−c, R30 = e(T1, g)sx ·
e(h, ω)−sα−sβ· e(h, g)−sτ−sλ(e(T1,ω)
e(g,g)
)c
, R04= Tsx
2 u−sτ, and R5 = T3sxv−sλ,
and check c= H(M , T? 1, T2, T3, R10, . . ., R05). If checking condition holds,
then output 1, and 0, otherwise.
Open(gpk, gsk, σ, M ): Verify that σ is a valid signature on M to execute Verify(gpk, σ, M ).
Next, compute Ai = T1/(T2ξ1T
ξ2
3 ), and return the signer’s identity i.
A.2 CPA-Anonymity
In this appendix, we introduce the definition of full-anonymity [1]. Note that the BBS short group signature is proven under CPA-full-anonymity, where an adversary cannot issue the Open oracle. Therefore, we introduce this weaker security notion as follows:
Definition 7. CPA-Anonymity
AdvAnonA (κ) = Pr[(gpk, gsk,{sski}Ui∈P)← KeyGen(1
κ); (M∗, i0, i1, State)← A(gpk, {sski}Ui∈P) µ∈R{0, 1}; σµ← GSig(gpk, sskiµ, M ∗); µ0← A(σµ, State); µ = µ0 ] −1 2
The BBS short signature satisfies CPA-full-anonymity under the DLIN assump-tion in the random oracle model (Theorem 5.2 of [3]).
