2022 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW)

Formalising Linked-Data based Veriﬁable Credentials for Selective Disclosure
Dan Yamamoto

Yuji Suga

Kazue Sako

Internet Initiative Japan Inc.
Tokyo, Japan
dan@iij.ad.jp

Internet Initiative Japan Inc.
Tokyo, Japansuga@iij.ad.jp

Waseda University
Tokyo, Japankazuesako@aoni.waseda.jp

1. Introduction

the vaccination dates. The user can present the credential
in a way that discloses only the vaccination dates, but not
the name, and it can still be veriﬁed.
Typically, veriﬁable credentials are implemented using
JSON (JavaScript Object Notation) [8] and applying thedigital signature on JSON objects. An example is touse JSON Web Signature (JWS) and JSON Web Token(JWT) [38]. To achieve the selective disclosure property
using anonymous credentials, we need the messages to besigned by a special digital signature scheme that is notin the scope of JSON Web Signatures. Therefore, several
alternative designs or “ﬂavours” of veriﬁable credentials
have been proposed [25], depending on the message structure and the digital signature scheme applied.
Among those different ﬂavours of veriﬁable credentials, there are some that use JSON-LD [26] to adopt
the concept of Linked Data [3]. By adopting JSON-LD,
we can interpret JSON objects according to the publicly
available JSON-LD context, which enhances the semantic interoperability of veriﬁable credentials. However, thecurrent design that uses JSON-LD can offer a selective
disclosure property in a limited manner.

Current identity management systems are centralised,as there is a central authority who has all the attributes of
all the users. On the contrary, the design being discussed
at World Wide Web Consortium (W3C) based on Decentralised IDentiﬁer (DID) [39] and Veriﬁable Credentials(VCs) [40] is gaining attention, as users are in charge ofstoring their own attributes and can control which of their
attributes are to be presented to whom.
In a nutshell, the users are issued with veriﬁable
credentials, which certify the user’s set of attributes bya digital signature of the issuer. A veriﬁable credential
can be issued not only to a natural person or legal entity
but also to any subject. The adoption of standardised data
structures for veriﬁable credentials has been seen in many
practical applications, such as COVID-19 vaccination certiﬁcates [18] and the IATA Travel Pass [23].
What is attractive in this design is that we can combine
anonymous credentials [11], [12], [15] and users canpresent veriﬁable credentials in a selective way. That is,
the user can select a portion of the attributes and prove thatthey are certiﬁed by the issuer, without disclosing further
information on the credentials, such as the signature orother remaining set of attributes. This property is called
selective disclosure. For example, in vaccination credentials, a local government might have issued a certiﬁcatewith a set of attributes, such as the name of the user andContribution. In this paper, we propose the ﬁrst veriﬁable
JSON-LD-based credentials that can perform selective
disclosure that are free from the restrictions of previous
schemes. We also propose a novel use of combining
multiple certiﬁcates issued by independent issuers, whichstill allows users to perform selective disclosure on theset of credentials. We further propose a formal deﬁnitionon the security and privacy of such selective disclosure
schemes and prove the property of the proposed scheme.
Our scheme has been implemented as open source andprovides a Web-based application that generates a veriﬁable presentation for any given selection of attributes.
Performance evaluation is also provided in the paper.
We strongly believe in the potential of applying theconcept of Linked Data to veriﬁable credentials. For example, as shown in Figure 1, user John Smith, identiﬁedby the identiﬁer A, has a veriﬁable credential issued by
the issuer I, which asserts that he works for the company
identiﬁed by an identiﬁer B, such as the Legal Entity
Identiﬁer (LEI) [24]. Furthermore, this company has averiﬁable credential issued by the issuer J that claims
that the company is named ABC Inc. and has received theTop 100 award. John can combine these two credentials
and claim that he works for a company that received theTop 100 award without disclosing his name, the name

Abstract—In this paper, we propose a formal deﬁnition for
Linked-Data based veriﬁable credential to enable secure
selective disclosure among one or multiple veriﬁable credentials a user has. Previous schemes considered using a single
veriﬁable credential and could not hide the user’s identifying
information when performing selective disclosure. We propose the ﬁrst Linked-Data based veriﬁable credentials thatcan perform selective disclosure free from the restrictions
the previous scheme had, and prove its property. We also
discuss a novel use of combining multiple certiﬁcates issued
by independent issuers to still allow users to perform selective
disclosure on the set of credentials. Our scheme has been
implemented as an open source Web-based application thatgenerates a veriﬁable presentation for a given selection of
attributes. The performance evaluation is also provided in
the paper.
Index Terms—anonymous credentials, veriﬁable credentials,
zero-knowledge proof© 2022, Dan Yamamoto. Under license to IEEE.
DOI 10.1109/EuroS&PW55150.2022.00013

52 


 
 

 

  

 

 

"

dentials based on graph signatures are discussed in [21],[33], [42]. When encoding a graph in the input of adigital signature, Nakanishi et al. [33] use a pairing-based
accumulator to achieve proof sizes and veriﬁcation times
that do not depend on the number of points or edges
in the graph. However, it is not obvious how to convert
Linked Data, the subject of this paper, into general graphinformation handled by these graph signatures or how to
selectively link graphs signed by multiple issuers.

  

!  !

 

  



 

 


"


 

!  !

  



Related standardisation efforts. There are three standardisation efforts at W3C related to our work. The ﬁrst
is Veriﬁable Credentials Data Model speciﬁcation [40],which describes a core data model, concepts and syntaxes
of veriﬁable credentials. The speciﬁcation is maintainedby the Veriﬁable Credentials Working Group. It does notstandardise on any single proof mechanism, but insteadrefers to the second speciﬁcation effort, Data Integrity.
The speciﬁcation of Data Integrity [30], which wasformerly called Linked Data Proofs, is currently published as a Draft Community Group Report by the W3C
Credentials Community Group. It provides speciﬁcations
to ensure the authenticity and integrity of Linked Data
documents, including Linked-Data based veriﬁable credentials. Data Integrity speciﬁcation only provides highlevel algorithms. Hence, we additionally require a speciﬁccanonicalisation algorithm, message digest algorithm, andproof algorithm to be used to obtain the intended result.
These are considered in the third effort, LDP-BBS+ speciﬁcation.
The LDP-BBS+ speciﬁcation [31] is also a Draft Community Group Report by the W3C Credentials Community
Group. It deﬁnes speciﬁc algorithms to create, verify andderive proofs for BBS+ Signatures [1], [9], [12] with theData Integrity speciﬁcation. The construction proposed in
our work extends LDP-BBS+ to overcome its limitation
and realise the aforementioned use case. While our work
has not yet been on any standardisation roadmap, we hadsome discussions with the editors of the speciﬁcations.
Our work can be regarded as a candidate for an additional
suite in conformance with Data Integrity.
Furthermore, we believe that this work can also be integrated into OpenID Connect for Self-Sovereign Identity
speciﬁcations [28], [43], [44] discussed in the OpenID
Foundation and the Decentralized Identity Foundation(DIF), as well as DIDcomm [16] discussed in DIF.
As for other ongoing standardisation activities related
to anonymous credentials, Privacy Pass protocol [17] enables a user to obtain a blindly signed anonymous token
from an issuer. The issuer issues anonymous tokens when
the user passed some test, for example, CAPTCHAs, andthe veriﬁer uses the token for authorisation. This protocol
is currently being standardised by the Internet Engineering Task Force (IETF) as Internet-Draft of Privacy Pass
Issuance Protocol [13], using the blind RSA signaturescheme [14] in publicly veriﬁable anonymous tokens. In
contrast to our work, the scheme intends a different use
case where the token is used once, and not multi-use as
in our case. It is also unclear if other attributes of theuser need to be veriﬁed besides passing a test, nor if theproperty of selective disclosure will be in need.

#

   

Figure 1. Example of Linked-Data based veriﬁable credentialsof the company, or any other identiﬁers included in thecredentials.
Note that credential 1, identiﬁed by the identiﬁer I/1
in the ﬁgure, is classiﬁed as a bound credential because
the credential is bound to the user secret key and no one
can show the credential without such secret key. On thecontrary, credential 2, identiﬁed by the identiﬁer J/2, iscalled an unbound credential because there are no user
secret keys bound to the credential and anyone can use
it as a public signed document. This is an interesting
example of combining bound and unbound credentials to
augment attribute presentations of the user. By collecting
public unbound credentials from governments, companies,
etc., and linking them to private bound credentials, users
can attest to various attributes of themselves which could
not have been done with bound credentials alone, as well
as claims that include the attributes of others. To ourknowledge, this type of selective disclosure use case has
not been discussed in previous work, and this would open
up new possibilities for veriﬁable credentials.
We note that Fig. 1 exempliﬁes a graph where thearrows are labelled with informal properties such as
issuer and name for simplicity, while in practice we
can use standardised properties such as https://www.w3.
org/2018/credentials#issuer from [40] and de facto standard ones such as http://schema.org/name from [36] toenhance semantic interoperability among distinct issuers.
Related work. The BBS+ signature is an extension of theBoneh, Boyen and Shacham (BBS) group signature [5] foranonymous credentials. It is capable of signing sequencesof messages and has the features of generating signatures
while hiding some messages and efﬁciently constructing
discrete-logarithm-based zero-knowledge proofs for eachmessage. It uses bilinear pairings, and security is shown
under the q -SDH (Strong Difﬁe-Hellman) assumption.
Signatures with similar characteristics exist, such as the
Pointcheval-Sanders (PS) signature [34] and the Sanders
redactable signature [35], but their security is reduced toa less general assumption than the q -SDH assumption.
Most conventional anonymous credentials treat attributes as simple sequences or sets of values. For example, [4], [10]–[12], [35] deals with a sequence of attributevalues (m ) , and [20] represents attribute values as a set{m } . For more complex data structures, anonymous cre-53

2. Preliminaries 

2.1. NotationFor a ≤ b ∈ Z, [a, b] denotes the set{x ∈ Z : a ≤ x ≤ b}. We write [1, n] as [n]. If I ∈Z, denote the sequence (x1 , . . . , xI ) by (xi )i∈[I]or (xi )Ii=1 , and (xi,1 , . . . , xi,J )i∈[I] to denote thesequence ((x1,1 , . . . , x1,J ), . . . , (xI,1 , . . . , xI,J )). Probabilistic Polynomial Time is abbreviated as PPT. Let a ←f(x) or f(x) → a denote that the PPT algorithm f withx as input is executed and the output is a. We write
a, b ← f(x), g(y) or f(x), g(y) → a, b to indicatethat the PPT algorithms f and g run interactively withx and y as input, respectively, and their outputs are aand b. We write a ← f(x, y, . . . ; Ooracle1 , Ooracle2 , . . .) toindicate the operation of a PPT algorithm f with inputs
x, y, . . . and access to oracles Ooracle1 , Ooracle2 , . . . and let
a be the output. We omit the system parameter prm thatis entered into the algorithm if it is clear from the context.

 







              

 
    

Figure 2. The roles and information ﬂows related to veriﬁable credentials.

regular car while hiding their name and address or to showthat a person is over 20 years old without revealing theirdate of birth. In addition, the unlinkability of the credential
is considered so that the user’s actions cannot be tracked
between issuers, veriﬁers, or even between issuers andveriﬁers.
Veriﬁable credentials can be represented as JSONLD [26] document, which has the aspect of Linked Data,
linking data to data to form a “web of data” 1 . The
veriﬁable credential described as JSON-LD enables scalable and interoperable data deﬁnition and also facilitateslinking among multiple veriﬁable credentials.
The LDP-BBS+ [31] scheme has been proposed as ascheme that takes advantage of the features of anonymous
credentials and Linked Data. This scheme applies the
BBS+ signature [1], [9], [12] to veriﬁable credentials
based on JSON-LD to allow selective disclosure of attributes. In recent years, the community has been working
on standard speciﬁcations and test implementations of thismethod, as it requires less preparation than conventional
methods, has a simple structure, and is easy to implement. However, there are some limitations in the scopeof anonymisation and zero-knowledge proofs other thanselective disclosure cannot be handled. In addition, there
is a lack of features to take advantage of the characteristics of Linked Data, such as conﬁdentiality of identiﬁers
contained in credentials and selective disclosure of links
between multiple credentials.

2.2. Veriﬁable Credentials
A veriﬁable credential is a set of attributes of a subject
digitally signed by an issuer. For example, a veriﬁable
credential could serve as a vaccination certiﬁcate for a userthat is signed by the authority, e.g. a local government,that includes a set of attributes like user’s name, address,
date of birth, vaccination status together with dates ofvaccinations and the names of each vaccine manufacturer.
The World Wide Web Consortium (W3C), in its Veriﬁable Credentials Working Group, deﬁnes the ecosystem of Veriﬁable Credentials consisting of the following
roles [40]: issuer, subject, holder, veriﬁer, and veriﬁed dataregistry, as depicted in Fig. 2.
The issuer issues a veriﬁable credential containing a
set of claims on a Subject, and transfers it to a Holder, whois typically the subject themselves. The holder stores theveriﬁable credential received, and storage is often called
an identity wallet. For simplicity, we use the term “User”
to represent both a holder and a subject.
In response to a request from the veriﬁer, the holder
retrieves one or more stored veriﬁable credentials fromthe identity wallet, extracts only the necessary attributes,
and presents them to the veriﬁer in a data set calleda veriﬁable presentation. The veriﬁer uses the issuer’s
public key to verify that the credentials contained in theveriﬁable presentation are indeed those of the issuer. In
this process, the issuer’s identiﬁer and public key areexchanged through a veriﬁable data registry.
For the implementation of veriﬁable credentials, several methods have been proposed, including those thatenhance user privacy by applying anonymous credentials
and those that have features as Linked Data that facilitate
linking between multiple data and assigning clear meanings to data.
The veriﬁable credential is based on the work of
the anonymous credential [11], [12], [15] and privacyenhancing attribute-based credential [10], providing a privacy enhancement mechanism that uses zero-knowledge
proofs in addition to digital signatures. For example, it
can be used to show that a person is qualiﬁed to drive a

2.3. Anonymous Credentials
In this paper, we basically follow the (game-based
security) deﬁnition of multi-use2 anonymous credential(AC) from [35] with slight modiﬁcations. We modify thedeﬁnitions to enable simultaneous presentations of multiple credentials and for proofs of equivalence of attributes,
as in the simulation-based security deﬁnitions of privacyenhancing attribute-based credential system [10]. Contrary
to the previous deﬁnitions based on interactive proofs, ourdeﬁnitions are based on non-interactive proofs to suit for
applications in concrete data exchange protocols such as
OpenID Connect and DIDComm.
Deﬁnition 1. An anonymous credential system AC consists of the following PPT algorithms:
1. W3C Speciﬁcation [40] also includes JWT-based veriﬁable credentials as well as those based on JSON-LD.
2. We require our ACs to support multiple unlinkable showing ofcredentials, rather than single-use showing such as U-Prove based on
Brand’s signature scheme [7] and anonymous credentials light [2].

54prmGen(1λ , L) → prm: Given a security parameter 1λand an upper bound L for the number of attributes,
it outputs public parameters prm.
ikGen(prm) → (isk, ipk): Given public parameters prm, it
outputs an issuer’s secret key isk and public key ipk.
sign(isk, (m ) ) → σ : Given an issuer secret key isk andattribute values (m ) to be signed, it outputs a signature σ .
A tuple (ipk, (m ) , σ, b = 0) consisting of a public
key ipk corresponding to isk, attribute values (m ) , asignature σ , and an unbound indicator b = 0 is called
unbound credential.
sigVf(ipk, (m ) , σ) → b: Given an issuer’s public key
ipk, attribute values (m ) , and a signature σ , it outputs
1 (accept) or 0 (reject).
uskGen(prm) → usk: It takes prm as input and outputs auser’s secret key usk.
obtain(usk, ipk, (m ) ), issue(isk, (m ) ) → σ, : It
is an interactive protocol run by a user and an issuer,
where the user runs obtain with its secret key usk,
the issuer’s public key ipk, and attribute values (m )
to be signed, whereas the issuer runs issue with its
secret key isk and (m ) . If the protocol is successful,the user gets the signature σ and the issuer gets .
Otherwise, both parties get ⊥.
We name the issued (ipk, (m ) , σ, b = 1) as boundcredential.
show(usk, (ipki , (mi, ) , σi , Di , bi )i , E, m) → π : Given
one or more pairs of credentials (ipki , (mi, ) , σi , bi )and reveal indices Di , a user’s secret key usk, indices
E to specify the target of the equivalence proof, andnonce m ∈ {0, 1}∗ , it outputs a proof π .
Di , is an index to specify the (mi, ) to be presented
to the veriﬁer from the entire attribute value (mi, ) .
E = {E1 , E2 , . . .} is the set of E ⊆ [I] × [L], which
instructs us to prove that (i, ), (i ,  ) ∈ EE thenmi, = mi, without hiding the actual value. Here,(i, ) ∈ E ∈ E implies  ∈/ Di .
If there exists a pair (i, ), (i ,  ) ∈ E ∈ E such thatmi, = mi , , the algorithm show outputs ⊥ since inthis case E contains inappropriate indices.
verify((ipki , (mi, ) , bi )i , E, m, π) → b: Given more than
one triple of an issuer’s public key ipki , revealed attribute values (mi, ) , and an indicator bi of bound /unbound, as well as indices E to specify the target of
equivalence proof, nonce m ∈ {0, 1}∗ , and the proof π ,it outputs 1 (accept) or 0 (reject).
When  ∈ Di (subject to disclosure), mi, = mi, , andwhen  ∈/ Di (subject not to disclosure), mi, = ⊥using the non-disclosure symbol ⊥ ∈/ M.

LiExpcorr
AC (λ, I, K, L, (ki , Li , (mi, )=1 , Di , bi )i∈[I] , E, m)
λ1:

prm ← prmGen(1 , L); usk ← uskGen(prm)2:for k ∈ [K] : (iskk , ipkk ) ← ikGen(prm)3:

for i ∈ [I] :4:

if bi : σi , b1,i 

5:else : σi ← sign(iskki , (mi, ) ); b1,i ← sigVf(ipkki , (mi, ) , σi )6:

for mi, ∈ (mi, ) :← obtain(usk, ipkki , (mi, ) ), issue(iskki , (mi, ) )





7:

if  ∈ Di : mi, ← mi, else : mi, ← ⊥8:

π ← show(usk, (ipkki , (mi, ) , σi , Di , bi )i∈[I] , E, m)

9:b2 ← verify((ipki , (mi, ) , bi )i∈[I] , E, m, π)

10:return b1,1 ∧ · · · ∧ b1,I ∧ b2

Figure 3. Correctness game for anonymous credentials
Lii
Li ≤ L, (mi, )L=1 ⊆ M , Di ⊆ [Li ], bi ∈ {0, 1}, E
such that mi, = mi, holds for any (i, ), (i ,  ) ∈ E
for all E ∈ E , m ∈ {0, 1}∗ , we say that AC is correct.

The security notions of an anonymous credential here
are not novel; they are slightly modiﬁed versions of thedeﬁnitions in [35]. The differences between ours and [35]are that we adopt a static corruption model for the brevityof the analysis, we add oracles to model the issuance ofunbound credentials, and we allow users and adversaries
to present multiple credentials at the same time.
Fig. 4 shows the deﬁnitions of oracles to be used in the
security deﬁnitions of anonymous credentials. The Oobtiss
is an oracle that allows an honest issuer and an honest user
u to issue and obtain a signature σ for attribute values(m ) . Signature σ is assigned an identiﬁer cid and isrecorded in CREDu (a wallet of credentials issued to theuser u) with the public key ipk∗ of the issuer, the attributevalue (m ) , and a bound/unbound ﬂag b. Oiss is an oracle
that causes an honest issuer to issue a bound signatureassociated with the adversary for the attribute values(m ) . Osign is an oracle that causes an honest issuer toissue an unbound signature for the attribute values (m ) .
Oobt and Oobt are oracles that allow an honest user u
to obtain bound and unbound signatures, respectively. As
in Oobtiss , the signature and other information is recorded
in CREDu , which is associated with the user u. Oshow isan oracle that causes an honest user u to present theircredentials. It speciﬁes one or more credentials issued
to u by Oobtiss , Oobt and Oobt by the identiﬁer cidi ,and performs selective disclosure based on reveal indices
Di and proof of equivalence based on the equivalenceindex E using the nonce m. Information on the disclosed
credentials is recorded in PRES with the nonce.
We deﬁne the unforgeability of anonymous credentials
as follows.

Correctness requires that if all I credentials with at
most L attributes each are correctly issued to a user by
K honest issuers, then any presentation, with selective
disclosure and proof of equivalence indicated by Di andE , correctly computed by the user from those credentials
will be accepted by the veriﬁer. The formal deﬁnition is
as follows.

Deﬁnition 3 (Unforgeability).
We say that AC is unufforgeable if Pr ExpAC (λ, L, A) = 1 is negligible for any
λ ∈ N, L ≥ 1 and adversary of the PPT A, where ExpufAC
is deﬁned in Fig. 5.

With an unforgeable anonymous credential, for ahonest issuer with (isk∗ , ipk∗ ) and a group of honest
users with ((usk∗u )u∈[U ] ), the adversary cannot make aforgery ((ipki , (m )∈Di , Di , bi )i∈[I ∗ ] , E ∗ , m∗ , π ∗ ) that is
accepted by the veriﬁer (b∗1 ). Here, the forgery must be

Deﬁnition 2 (correctness). We deﬁne the game
Expcorr
as in Fig. 3. If it always holds thatAC
Li
Expcorr
AC (λ, I, K, L, (ki , Li , (mi, )=1 , Di , bi )i∈[I] , E, m) =1 for any λ ∈ N, I ≥ 1, K ≥ 1, L ≥ 1, ki ∈ [K] (i ∈ [I]),55

ExpufAC (λ, L, A)

Oobtiss (u, (m ) , b)
2:

∗
∗
∗
if b : σ, · ← obtain(usku , ipk , (m ) ), issue(isk , (m ) )
∗else : σ ← sign(isk , (m ) )3:

if σ = ⊥ : return ⊥1:∗

cid ←$ {0, 1} ; CREDu [cid] ← (ipk , (m ) , σ, b)5:

return cid

Oiss ((m ) )2:
3:

if b = ⊥ :2:

ATTR ← ATTR ∪ {(m ) }
σ, · ←3:

1:∗

obtain(usku , ipk, (m ) ), A2:

if σ = ⊥ : return ⊥3:

CREDu [cid] ← (ipk, (m ) , σ, 1)

∗

∗

∗



∗

∗

∗

b2 ← [((ipki , (mi, ) , bi )i∈[I ∗ ] , E , m ) ∈/ PRES]σ ← sign(isk , (m ) )∗6:

b3 ← [ipk ∈ {ipki }i∈[I ∗ ] ]; b4 ←ATTR ← ATTR ∪ {(m ) }7:

for i ∈ {i ∈ [I ] : ipki = ipk } :return σ

8:9:if sigVf(ipk, (m ) , σ) = 0 :2:

return ⊥3:

CREDu [cid]3:

for mi, ∈ (mi, ) :

∗



∗

∗

∗

∗

∗

∗

∗

∗

∗

∗



b4 ← b4 ∧ [∀(m ) ∈ ATTR. (mi∗ , ) ⊆ (m ) ]∗∗∗∗return b1 ∧ b2 ∧ b3 ∧ b4

Expan
AC (λ, L, A)← (ipk, (m ) , σ, 0)b ←$ {0, 1}; prm ← prmGen(1 , L)2:

for u ∈ [U ] : usku ← uskGen(prm)3:((u0 , cid0,i , D0,i )i∈[I ∗ ] , (u1 , cid1,i , D1,i )i∈[I ∗ ] , E , m )

5:
6:



if  ∈ Di : mi, ← mi, else : mi, ← ⊥

7:



λ

1:

4:

(ipki , (mi, ) , σi , bi ) ← CREDu [cidi ]∗← A(prm, ipk ; Oobtiss , Oiss , Osign , Oobt , Oobt , Oshow )for i ∈ [I] :





5:

2:

4:

((ipki , (mi, ) , bi )i∈[I ∗ ] , E , m , π )b1 ← verify((ipki , (mi, ) , bi )i∈[I ∗ ] , E , m , π )Oshow (u, (cidi , Di )i∈[I] , E, m)
1:

3:

∗

4:

Oobt (u, cid, ipk, (m ) , σ)Oobt (u, cid, ipk, (m ) )
1:

1:

∗

for u ∈ [U ] : usku ← uskGen(prm)∗Osign ((m ) )∗·, b ← A, issue(isk , (m ) )

∗prm ← prmGen(1 , L); (isk , ipk ) ← ikGen(prm)

2:

∗

4:

1:

λ

1:

∗

∗

∗

∗

∗

∗

∗

∗

∗

← A(prm; Oobt , Oobt , Oshow )∗for i ∈ [I ] :
∗

∗

∗

∗

∗

(ipk0,i , (m0,i, ) , σ0,i , b0,i ) ← CREDu∗ [cid0,i ]
0
∗
∗
∗
∗
∗
(ipk1,i , (m1,i, ) , σ1,i , b1,i ) ← CREDu∗ [cid1,i ]
1∗∗∗
if (ipk0,i , (m0,i, )∈D∗ , b0,i )i∈[I ∗ ]0,i5:

if ∃(i, ), (i ,  ) ∈ E ∈ E. [m(i,) = m(i , ) ] : return ⊥6:

if ∃(i, ) ∈ E ∈ E. [ ∈ Di ] : return ⊥7:

π ← show(usku , (ipki , (mi, ) , σi , Di , bi )i∈[I] , E, m)

8:π ← show(usku∗ , (ipkb,i , (mb,i, ) , σb,i , Db,i , bb,i )i∈[I ∗ ] , E , m )8:

if π = ⊥ : return ⊥9:if π = ⊥ : return 0

9:PRES ← PRES ∪ {((ipki , (mi, ) , bi )i∈[I] , E, m)}

10:b ← A(π ; Oobt , Oobt , Oshow ); return (b = b)10:

return π∗∗∗= (ipk1,i , (m1,i, )∈D∗ , b1,i )i∈[I ∗ ] : return 0

∗



∗

∗

∗

∗

∗

∗

∗

∗

b

∗

∗

∗

1,i

∗

∗

Figure 5. Unforgeability and anonymity of anonymous credentials

Figure 4. Oracles to be used in the security deﬁnitions of anonymous
credentials

graph [37] as Linked Data. Note that veriﬁable credentials
based on JSON-LD can be uniquely deserialised to RDF
graphs according to the standardised algorithm [27]. An
RDF graph is a representation of a labelled directed graphas a set of triples. Speciﬁcally, for a message set M, theset of three terms called subject, predicate, and object(s, p, o) ∈ M3 is called an RDF triple, and the set of RDF
triples G ⊂ M3 is called an RDF graph. For simplicity,
we assume that each term is an element of M and ignore
the difference between IRIs and literals, and we do notdeal with blank nodes.
The two credentials shown in Figure 1 are examples of
RDF graphs. For example, credential 1 can be represented
as the RDF graph G1 shown below.

nontrivial, that is, the forgery must not have been created by a Oshow oracle (b∗2 ), and must contain at least
one credential issued by an honest issuer (b∗3 ). Furthermore, forgeries based on those honest credentials mustnot be derivable from the credentials obtained by theadversary via the Oiss or Osign oracles (b∗4 ). We say that(m ) ⊆ (m ) if m = ⊥ ⇒ m = m is valid for all .
We deﬁne the anonymity of anonymous credentials as
follows:
Deﬁnition 4 (Anonymity). We say that AC is anonymous
if Pr[Expan
AC (λ, L, A) = 1] is negligible for any λ ∈ N,
L ≥ 1 and PPT adversary A, where Expan
AC is deﬁned inFig. 5.
The above deﬁnition means that any PPT adversary
cannot extract any knowledge from the proof π ∗ that helps
identify who presents π ∗ and which credentials are used
to construct π ∗ , except to the extent that it is trivially
identiﬁed from the revealed attributes and the issuers’
public keys.
For example, we can construct an anonymous credential scheme with the above notions of unforgeability andanonymity, based on BBS + signatures [1], [9], [12] with
the Fiat-Shamir heuristic [19], which is proven secure
under the q -SDH assumption in the random oracle model.

G1 = {(si , pi , oi ) : 1 ≤ i ≤ 4}, where(s1 , p1 , o1 ) = (I/1, issuer, I)),(s2 , p2 , o2 ) = (I/1, credentialSubject, A),(s3 , p3 , o3 ) = (A, name, John Smith),(s4 , p4 , o4 ) = (A, worksFor, B)

Hereinafter, we refer to RDF graphs and RDF triples
simply as graphs and triples if it does not cause misunderstanding.
We use a canonicalisation algorithm canon, a deterministic algorithm that converts a graph G ={(sj , pj , oj )}j∈J , an unordered set of triples, into the = (sj , pj , oj )j∈[|G|] . Since we assumed
ordered set G
that the RDF graphs in this paper do not contain blanknodes, canonicalisation is trivially possible. For example,
serialising each element s, p, o ∈ M by any appropriate
serialisation rule and sorting them in lexicographic order is

3. Linked-Data based Veriﬁable Credentials
3.1. RDF Graph
In this paper, we follow [26] and refer to a set of
documents, each containing a representation of an RDF

56

sufﬁcient.3 For the above example of G1 , its canonicalised
form is obtained as follows:

ikGen(prm) → (isk, ipk): Given public parameters prm, it
outputs an issuer’s secret key isk and public key ipk.
sign(isk, G) → σ : Given an issuer secret key isk and agraph G to be signed, it outputs a signature σ .
A tuple (ipk, G, σ, b = 0) consisting of a public key
ipk corresponding to isk, a graph G, a signature σ ,and an unbound indicator b = 0 is called an unboundcredential.
sigVf(ipk, G, σ) → b: Given an issuer’s public key ipk, agraph G, and a signature σ , it outputs 1 (accept) or 0
(reject).
uskGen(prm) → usk: It takes prm as input and outputs auser’s secret key usk.
obtain(usk, ipk, G), issue(isk, G) → σ, : It is an interactive protocol run by a user and an issuer, where
the user runs obtain with its secret key usk, the issuer’s
public key ipk and a graph G to be signed, while theissuer runs issue with its secret key isk and G. If the
protocol is successful, the user gets the signature σ andthe issuer gets . Otherwise, both parties get ⊥.
We name the issued (ipk, G, σ, b = 1) as bound credential.
show(usk, (ipki , Gi , σi , ϕi , bi )i , m) → π : Given one ormore pairs of credentials (ipki , Gi , σi , bi ) and reveal
functions ϕi , a user’s secret key usk, and nonce m ∈{0, 1}∗ , it outputs a proof π for the derived graphs(ϕi (Gi ))i .
It outputs ⊥ if (ϕi )i is an incorrect set of reveal
functions.
verify((ipki , Gi , bi )i , m, π) → b: Given more than one
triple of an issuer’s public key ipki , a derived graphGi , and an indicator bi of bound / unbound, as well as
nonce m ∈ {0, 1}∗ and the proof π , it outputs 1 (accept)
or 0 (reject).

canon(G1 ) = ((A, name, John Smith),(A, worksFor, B),(I/1, credentialSubject, A),(I/1, issuer, I))

3.2. Reveal Function
Our veriﬁable credentials based on Linked Data allow
users to selectively disclose their RDF graphs. Specifically, we introduce the following reveal function ϕ toexpress the operation of deriving a partially hidden graphG from an RDF graph G as G = ϕ(G).
Let ϕ be a function that assigns the RDF triple(s, p, o) ∈ M3 to the empty set ∅ or (s , p , o ) withzero or more terms replaced by mask X ∈ X , wheres ∈ {s} ∪ X , p ∈ {p} ∪ X , o ∈ {o} ∪ X . Here,
X = {X1 , X2 , . . .} is a set of masks that is used tohide the labels of the vertices and arcs on the graph,
which satisﬁes X ∩ M = ∅. If the same mask appears inseveral places in the revealed graph G , this means that the
attribute values are originally equal and their equivalenceis later shown by the user in a zero-knowledge proof.
We say that G  G if for any (s , p , o ) ∈ G there
exists some (s, p, o) ∈ G such that s ∈ {s} ∪ X , p ∈{p} ∪ X , and o ∈ {o} ∪ X hold.
A reveal function is called incorrect if it attempts
to show the equivalence of non-equivalent values. Morestrictly, for a given ϕi , ϕi ∈ (ϕi )i , for any tj ∈ M andxj ∈ M ∪ X (1 ≤ j ≤ 6) such that ϕi ((t1 , t2 , t3 )) =(x1 , x2 , x3 ) and ϕi ((t4 , t5 , t6 )) = (x4 , x5 , x6 ), if both
tj = tj  and xj = xj  hold for some 1 ≤ j, j  ≤ 6, thenwe say that (ϕi )i is an incorrect set of reveal functions.
For example, for credential 1 in Figure 1, the following
reveal function ϕ1 speciﬁes that the vertices I/1 and A
are to be masked by X1 and X2 , respectively, and thatthe arc name with value John Smith will be deleted.

Since the correctness of LDVC is almost the sameas the correctness of an anonymous credential, the exact
deﬁnition is omitted.

3.4. Security
We deﬁne the unforgeability and anonymity of LDVC
based on the corresponding notions of anonymous credentials by replacing a sequence (m ) of attributes in ananonymous credential with an RDF graph G.
With the oracle deﬁnitions in Fig. 6, the unforgeability
and anonymity of LDVC are deﬁned as follows:ϕ1 ((I/1, issuer, I)) := (X1 , issuer, I),
ϕ1 ((I/1, credentialSubject, A)):= (X1 , credentialSubject, X2 ),ϕ1 ((A, name, John Smith)) := ∅,ϕ1 ((A, worksFor, B)) := (X2 , worksFor, B)

For an RDF graph G, we denote the set{ϕ((s, p, o))}(s,p,o)∈G by ϕ(G). For a sequence = (si , pi , oi )i of RDF triples, we denote the sequenceG(ϕ((si , pi , oi ))i = (ϕ((s1 , p1 , o1 )), ϕ((s2 , p2 , o2 )), . . .) as
 .
ϕ(G)

Deﬁnition 6 (Unforgeability).
We saythat LDVC is unufforgeable if Pr ExpLDVC (λ, L, A) = 1 is negligible forany λ ∈ N, L ≥ 1, and PPT adversary A, where Expuf
LDVC
is deﬁned in Fig. 7.
Deﬁnition 7 (Anonymity and weak anonymity). We
say that LDVC is anonymous and weakly anonymous ifwan
Pr[Expan
LDVC (λ, L, A) = 1] and Pr[ExpLDVC (λ, L, A) = 1]
are negligible for any λ ∈ N, L ≥ 1 and PPT adversary A,
where the experiments are deﬁned in Fig. 7, respectively.

3.3. Syntax
Deﬁnition 5. A Linked-Data based veriﬁable credential
system LDVC consists of the following PPT algorithms:
prmGen(1λ , L) → prm: Given a security parameter 1λand an upper bound L for the number of arcs in a graph,
it outputs public parameters prm.

Although the unforgeability and anonymity of LDVC
are obtained as straightforward extensions of the anonymous credential, we additionally deﬁne the notion of
weak anonymity for LDVC. Informally speaking, (full)anonymity ensures that no PPT adversary can identify the

3. For canonicalisation of RDF graphs with blank nodes, there exist
several proposed methods including [29] and [22].

57Oobtiss (u, G, b)
1:

if b :Expuf
LDVC (λ, L, A)∗∗∗
σ, · ← obtain(usku , ipk , G), issue(isk , G)
∗2:else : σ ← sign(isk , G)3:

if σ = ⊥ : return ⊥4:

cid ←$ {0, 1} ; CREDu [cid] ← (ipk , G, σ, b)5:

return cid

1:
2:
3:

∗

∗

4:

Oiss (G)Osign (G)
∗

5:
∗

1:

·, b ← A, issue(isk , G)

1:

σ ← sign(isk , G)6:2:

if b = ⊥ :2:

ATTR ← ATTR ∪ {G}7:

3:

return σ

8:3:ATTR ← ATTR ∪ {G}Oobt (u, cid, ipk, G, σ)Oobt (u, cid, ipk, G)
1:

σ, · ←1:∗

obtain(usku , ipk, G), A2:
3:

if σ = ⊥ : return ⊥9:

if sigVf(ipk, G, σ) = 0 :2:

return ⊥3:

CREDu [cid]CREDu [cid] ← (ipk, G, σ, 1)
if (ϕi )i∈[I] is incorrect : return ⊥2:

for i ∈ [I] :

3:

∗

∗

∗
for u ∈ [U ] : usku ← uskGen(prm)∗∗((ipki , Gi , bi )i∈[I ∗ ] , m , π )∗← A(prm, ipk ; Oobtiss , Oiss , Osign , Oshow )∗∗∗
b1 ← verify((ipki , Gi , bi )i∈[I ∗ ] , m , π )∗∗b2 ← [((ipki , Gi , bi )i∈[I ∗ ] , m ) ∈/ PRES]∗∗∗b3 ← [ipk ∈ {ipki }i∈[I ∗ ] ]; b4 ←∗∗∗for i ∈ {i ∈ [I ] : ipki = ipk } :∗∗
b4 ← b4 ∧ [∀G ∈ ATTR. Gi∗  G]∗∗∗∗
return b1 ∧ b2 ∧ b3 ∧ b4

wan
Expan
LDVC (λ, L, A) ExpLDVC (λ, L, A)← (ipk, G, σ, 0)Oshow (u, (cidi , ϕi )i∈[I] , m)1:

λprm ← prmGen(1 , L); (isk , ipk ) ← ikGen(prm)b ←$ {0, 1}; prm ← prmGen(1 , L)2:

for u ∈ [U ] : usku ← uskGen(prm)3:((u0 , cid0,i , ϕ0,i )i∈[I ∗ ] , (u1 , cid1,i , ϕ1,i )i∈[I ∗ ] , m )4:for i ∈ [I ] :5:(ipki , Gi , σi , bi ) ← CREDu [cidi ]; Gi ← ϕi (Gi )∗4:π ← show(usku , (ipki , Gi , σi , ϕi , bi )i∈[I] , m)

6:5:if π = ⊥ : return ⊥7:

6:

PRES ← PRES ∪ {((ipki , Gi , bi )i∈[I] , m)}7:

return π8:Figure 6. Oracles to be used in the security deﬁnitions of LDVC

9:
10:
11:

∗

user presenting the proof π or learn anything about theuser, except to the extent that it is trivially learnt from therevealed graphs and the issuers’ public keys required toverify the proof. Regarding weak anonymity, we further
extend this ”trivially learnt” information; an adversary in
the weak anonymity setting is able to additionally learn
the sizes and canonicalised forms of the graphs at the timeof issuance as well as the revealed graphs and the issuers’
public keys.

λ

1:

∗

∗

∗

∗

∗

∗

∗

← A(prm; Oobt , Oobt , Oshow )

∗

∗

∗

∗

∗

∗

∗

(ipk0,i , G0,i , σ0,i , b0,i ) ← CREDu∗ [cid0,i ]

0
∗
∗
∗
∗
∗
(ipk1,i , G1,i , σ1,i , b1,i ) ← CREDu∗ [cid1,i ]
1
∗
∗
∗
∗
if (ipk0,i , ϕ0,i (G0,i ), b0,i )i∈[I ∗ ]∗∗∗∗= (ipk1,i , ϕ1,i (G1,i ), b1,i )i∈[I ∗ ] : return 0∗∗∗∗
if (ipk0,i , ϕ0,i (canon(G0,i )), |G∗
0,i |, b0,i )i∈[I ∗ ]∗∗∗∗= (ipk1,i , ϕ1,i (canon(G1,i )), |G1,i |, b∗1,i )i∈[I ∗ ] : return 0
∗
∗
∗
∗
∗
∗
∗
∗
π ← show(usku∗ , (ipkb,i , Gb,i , σb,i , ϕb,i , bb,i )i∈[I ∗ ] , m )b∗if π = ⊥ : return 0∗∗∗b ← A(π ; Oobt , Oobt , Oshow ); return (b = b)

Figure 7. Unforgeability and anonymity of LDVC. Highlighted parts are
only evaluated in the weak anonymity game.

can combine multiple RDF graphs while hiding the URIs
in the graphs, enabling the use cases shown in Figure 1.
Note that the selectively disclosed graph, passed fromthe user to the veriﬁer, can be different from the originalissued graph by the issuer, that is, some of the triples in
the graph might be removed or some of the terms in the
triples might be replaced by masks. These redactions candiffer the result of canonicalisation, that is, the order of thecanonicalised RDF triples by the veriﬁer can be different
from that of the issuer, leading to veriﬁcation failure. To
address this problem, in our construction, we let the user
calculate a map ψ between (m̃ ) at veriﬁcation (verify)and (m ) at issuance (sign or issue), which is delivered
to the veriﬁer so that the veriﬁer can reproduce the same
attribute order as at the time of issuance.
Figure 8 shows our LDVC construction LDVCAC using
AC as its building block.
 =ﬂatten is a function that takes a sequence G((s1 , p1 , o1 ), (s2 , p2 , o2 ), . . .) of triples as input to obtaina ﬂat sequence (m ) = (s1 , p1 , o1 , s2 , p2 , o2 , . . .).
mapGen is a function that takes sequences (xi )Ii=1 and(yj )Jj=1 as input to output a map ψ : [I] → [J] such thatxi = yψ(i) is satisﬁed.
reorder uses ψ to reconstruct a sequence (yj )Jj=1 from(xi )Ii=1 , where the missing elements are ﬁlled with theempty set ∅.
Masks X1 , X2 , . . . speciﬁed by ϕ are used in thecomputation of the equivalence proof indices E . The attribute values assigned to the same mask are shown to beequivalent by a zero-knowledge proof of AC.

4. Construction of Linked-Data based Veriﬁable Credential
4.1. Construction
Now we construct our LDVC from an anonymous
credential system. Our construction can be seen as anextension of the LDP-BBS+ scheme [31]. The original
LDP-BBS + scheme uses the Universal RDF Dataset
Canonicalisation Algorithm 2015 (URDNA2015) [29] toconvert an RDF graph into a canonicalised (ordered) listof RDF triples, and then generates and veriﬁes a BBS+
signature taking each RDF triple as input attribute. As
a result, zero-knowledge proofs in the scheme can only
be performed for each triple, so that selective disclosure,range proofs, and any other ZKPs for individual values(i.e., ID, name, date of birth, etc.) cannot be realised.
However, in our construction, RDF triples are further
decomposed into RDF terms, that is, subject, predicate,and object, which are regarded as attributes for generating
and verifying signatures. This enables zero-knowledge
proofs, such as selective disclosure, range proofs, andproof of equivalent attributes for individual values rather
than triples. In particular, using the proof of equality, we

58

prmGen(1λ , L)1:

ikGen(prm)λreturn prm ← AC.prmGen(1 , 3L)

sign(isk, G)

1:

uskGen(prm)return (isk, ipk) ← AC.ikGen(prm)sigVf(ipk, G, σ)1:

return usk ← AC.uskGen(prm)obtain(usk, ipk, G), issue(isk, G)

1:(m ) ← ﬂatten(canon(G))

1:(m ) ← ﬂatten(canon(G))

obtain(usk, ipk, G)2:

σ ← AC.sign(isk, (m ) )2:

b ← AC.sigVf(ipk, (m ) , σ)(m ) ← ﬂatten(canon(G))(m ) ← ﬂatten(canon(G))

3:return σ

3:

return b

σ ← AC.obtain(usk, ipk, (m ) )AC.issue(isk, (m ) ) → b

return σ

return b

verify((ipki , Gi , bi )i∈[I] , m, π)show(usk, (ipki , Gi , σi , ϕi , bi )i∈[I] , m)1:(π̃, (ψi , Ji )i∈[I] ) ← π

2:(mi, ) ← ﬂatten(canon(Gi )); Ji ← |Gi |2:

for i ∈ [I] :3:(m̃i, ) ← ﬂatten(ϕi (canon(Gi )))3:

for m̃i, ∈ (m̃i, ) :(m̃i, ) ← ﬂatten(reorder(canon(Gi ), ψi , Ji ))4:4:(mi, ) ← (m̃i, )
for m̃i, ∈ (m̃i, ) :1:

for i ∈ [I] :5:

if m̃i, ∈ X : Eq[m̃i, ] ← Eq[m̃i, ] ∪ {(i, )}5:

6:elseif m̃i, = ⊥ : Di ← Di ∪ {}6:

ψi ← mapGen(canon(ϕi (Gi )), ϕi (canon(Gi )))7:8:

E ← {Eq[X] : X ∈ X }9:m̃ ← (((m̃i, ) , ψi , Ji )i∈[I] , E, m)

10:π̃ ← AC.show(usk, (ipki , (mi, ) , σi , Di , bi )i∈[I] , E, m̃)11:

if π̃ = ⊥ : return ⊥12:

return π ← (π̃, (ψi , Ji )i∈[I] )

2:
3:

8:

4:

if m̃i, ∈ X :

Eq[m̃i, ] ← Eq[m̃i, ] ∪ {(i, )}; mi, ← ⊥E ← {Eq[X] : X ∈ X }9:m̃ ← (((m̃i, ) , ψi , Ji )i∈[I] , E, m)

10:

return b ← AC.verify((ipki , (mi, ) , bi )i∈[I] , E, m̃, π̃)

mapGen((xi )Ii=1 , (yj )Jj=1 ) :for j ∈ [|G|]
if G[j] = ∅ :else :



7:


ﬂatten(G)1:issue(isk, G)

1:(m3(j−1)+1 , m3(j−1)+2 , m3(j−1)+3 ) ← (⊥, ⊥, ⊥)
(m3(j−1)+1 , m3(j−1)+2 , m3(j−1)+3 ) ← G[j]2:3:reorder((xi )Ii=1 , ψ, J)

for (i, j) ∈ [I] × [J] :if xi = yj : ψ(i) ← j
return ψ1:

for j ∈ [J] : yj ← ∅2:for i ∈ [I] : yψ(i) ← xi

3:

return (yj )j=1

J

return (m )∈[3|G|]

Figure 8. Generic construction LDVCAC of Linked-Data based Veriﬁable Credential

With the processing added to line 13 in Oshow , the tuple (ipki , (mi, ) , σi , bi ) will be overwritten with the values recorded in AC.CREDu [cidi ]. Note that ipki , σi , andbi are the same in both AC.CREDu [cid] and CREDu [cid].
Furthermore, we see that (mi, ) is also generated as(mi, ) = ﬂatten(canon(G)) in the lines 1 of Oobtiss ,which is completely the same as the way in Oshow . Therefore, these additional operations will not affect the game’s
output.
Although we introduce a variable mi, on the line 15
of Oshow , this does not affect the game output.
In lines 16 and 17 of Oshow , we let the oracle return⊥ when E satisﬁes certain conditions, but note that these
conditions can never be true if (ϕi )i∈[I] are correct reveal
functions. Since the validity of (ϕi )i∈[I] is guaranteed on
the line 1 of Oshow , these additional processes do not affect
the game output.
From the above, we have Pr[G0 (λ, L, A) = 1] =Pr[G1 (λ, L, A) = 1].

Eq is a dictionary-like data structure that maps a mask
X ∈ X to a set of (i, )’s, each of which corresponds to
an attribute mi, and these mi, ’s are masked by X in
the derived graph G . For example, if we have Eq[X1 ] ={(1, 2), (2, 3)} then both m1,2 in G1 and m2,3 in G2 havethe mask X1 as their values. Note that {Eq[X] : X ∈X } = {Eq[X1 ], Eq[X2 ], . . .}, where each Eq[Xi ] is a setof (i, )’s masked by Xi ’s.

4.2. Security
Theorem 1. LDVCAC is unforgeable if AC is unforgeable.
Proof. Assume that we have a PPT adversary A against
the unforgeability of LDVCAC . We will construct an adversary B that exploits A to break the unforgeability of
AC. Since we assume AC to be unforgeable, showing thefollowing relation is sufﬁcient to conclude this proof.




uf
Pr Expuf
(λ,
L,
A)
=
1
≤
Pr
Exp
(λ,
L,
B)
=
1
LDVCAC
AC(1)

Game G2 . We replace the game output with four∗∗∗∗
additional variables
b∗∗
b∗∗
1 , 
2 , b3 , and b4 . We will ∗∗∗bi implies
bi , from which we haveshow that
Pr[G1 (λ, L, A) = 1] ≤ Pr[G2 (λ, L, A) = 1].
We can see that b∗1 and b∗3 are equivalent to b∗∗
1 and∗∗b3 , respectively.
Next, we show that b∗2 = 1 implies b∗∗
2 = 1. Assume∗∗∗∗∗
b2 = 0, namely, ((ipk∗i , (m∗i, ) , bi )i∈[I ∗ ] , E , m̃ ) ∈AC.PRES. Then ((m̃∗i, ) )i∈[I ∗ ] in m̃∗ should have been
computed as (m̃∗i, ) ← ﬂatten(ϕi (canon(Gi ))) in line 5of Oshow . On the other hand, from the line 7 of G2 , we∗∗also have (m̃∗i, ) = ﬂatten(reorder(canon(G∗i ), ψi , Ji )),To show how to construct B that meets Eq. (1), we deﬁneconsecutive games described in Figure 11.
Game G0 . The initial game G0 (λ, L, A) is equivalent to
Expuf
LDVCAC (λ, L, A). Therefore, we have the following.

Pr Expuf
LDVCAC (λ, L, A) = 1 = Pr[G0 (λ, L, A) = 1]
Game G1 . We introduce three variables AC.CREDu ,AC.ATTR, and AC.PRES to record some values during
the processing of Oobtiss , Oiss , Osign , and Oshow .

59

∗
∗
= ψ1,iandGame G3 . Here we can see that both ψ0,i∗∗∗
J0,i = J1,i hold for any i ∈ [I ] because of the checking
in line 7 of the game. Note that this guarantee holds
in the weak anonymity game, which implies the reason
why we cannot prove (full) anonymity using the same
argument here. In addition, we can also check that Eb̄∗and m̃∗b̄ are the same as their counterparts related to b.
To sum up, we can omit b and b̄ from these values
without affecting the output of the game, which resultsin Pr[G2 (λ, L, A) = 1] = Pr[G3 (λ, L, A) = 1].

so that we can say ﬂatten(ϕi (canon(Gi )))=∗∗ﬂatten(reorder(canon(G∗
),
ψ
,
J
))
.
Here,
by
the
i
i
i
deﬁnition of ﬂatten, we have ϕi (canon(Gi )) =∗∗reorder(canon(G∗Furthermore, from thei ), ψi , Ji ).
deﬁnitions of ϕi , canon, and reorder, we haveϕi (Gi ) = G∗i . Immediately after adding the tuple∗∗∗((ipk∗i , (m∗i, ) , bi )i∈[I ∗ ] , E , m̃ ) to AC.PRES on line 20
of Oshow , PRES should get ((ipk∗i , ϕi (Gi ), b∗i )i∈[I ∗ ] , m∗ )in line 23. Since ϕi (Gi ) = G∗i holds here, we can saythat b∗2 = 0 and b∗2 = 1 ⇒ b∗∗
2 = 1 as desired.
We can also show that b∗4 = 1 implies b∗∗=4
1. Assume b∗∗
=
0
.
Then
there
exist
some
4
i∗ ∈ [I ∗ ] and some (m ) ∈ AC.ATTR such that∗(m∗i∗ , ) ⊆ (m ) . For each (mi∗ , ) and (m ) , there∗∗∗
exist G∗
=
{(
m̃
,
m̃
,
m̃
∗
∗
∗
i
i ,j
i ,j+1i∗ ,j+2 )}j and G ={(mj , mj+1 , mj+2 )}j ∈ ATTR, respectively. We can∗check G∗i∗  G, which implies b4 = 0 as desired.

Game G4 . With the loop starting from line 31, the tuples(ipk∗b ,i , (m∗b ,i, ) , σb∗ ,i , b∗b ,i ) will be overwritten with thevalues recorded in AC.CREDu∗b [cid∗b ,i ] for b ∈ {0, 1}.
Similarly to the proof of Theorem 1, these additional
operations do not affect the output of the game. Hence,
Pr[G3 (λ, L, A) = 1] = Pr[G4 (λ, L, A) = 1] holds.
Adversary B . Figure 14 shows the description of theadversary B and its experiment Expan
AC (λ, L, B). We
can see that the output of Expan
AC (λ, L, B) is equivalently generated to the output of G4 . Hence, we havePr[G4 (λ, L, A) = 1] = Pr[Expan
AC (λ, L, B) = 1]
allthis  together,wehavePuttingan
Pr Expwan
LDVCAC (λ, L, A) = 1 ≤ Pr[ExpAC (λ, L, B) = 1].
Since the right-hand side is negligible by assumption, theleft-hand side is also negligible.

Adversary B . Figure 12 shows the description of theadversary B and its experiment Expuf
AC (λ, L, B). We(λ,L,B) is equivacan see that the output of Expuf
AC
lently generated to the outputofG.
Hence,
2 we havePr[G2 (λ, L, A) = 1] = Pr Expuf
(λ,
L,
B)
=
1
AC
all
this  together,wehavePuttinguf.
Pr Expuf
(λ,
L,
A)
=
1
≤
Pr
Exp
(λ,
L,
B)
=
1
LDVCACAC
Since the right-hand side is negligible by assumption, theleft-hand side is also negligible.

4.3. Impact of Weak Anonymity in Practice

Theorem 2. LDVCAC is weakly anonymous if AC isanonymous.

Our construction leaks the size and the canonicalised
form of the original graph, due to J and ψ in the proof
π , respectively. Weak anonymity guarantees that nothing
further will be leaked by our construction.
The leaked size of the graph helps adversaries guess
which credential is included in the presented proof. For
example, assume that a user has two credentials that
include G1 and G2 , respectively, where |G1 | = |G2 | andG1 ∩ G2 = ∅. If the user shows one of these credentials
that partially discloses an intersection G1 ∩ G2 , anyone
can determine which credential is presented by the leaked
size |Gi |, even though the disclosed attributes G1 ∩ G2
themselves do not leak any information to identify theoriginal credential. A simple workaround is to add dummy
RDF triples to each graph when issuing credentials so thatall graphs are the same size.
Similarly, the leaked canonicalised form of the originalgraph can also be exploited to identify the credentials
included in the presentation. Furthermore, in some speciﬁc situations, an adversary can even guess unrevealed
attribute values from revealed attributes with a leaked
canonicalised form. For example, let us assume that auser has the issued credential, including an RDF graph
G, which is canonicalised to get the following orderedset:

Proof. Assume that we have a PPT adversary A against
the weak anonymity of LDVCAC . We will construct anadversary B that exploits A to break the anonymity of AC.
Since we assume AC is anonymous, showing the following
relation is sufﬁcient to conclude this proof:an
Pr Expwan
LDVCAC (λ, L, A) = 1 ≤ Pr[ExpAC (λ, L, B) = 1]
(2)
To show how to construct B that meets Eq. (2), we deﬁneconsecutive games described in Figure 13.
Game G0 . The initial game G0 (λ, L, A) is equivalent to
ExpwanLDVCAC (λ, L, A). Therefore, we have the following.

Pr Expwan
LDVCAC (λ, L, A) = 1 = Pr[G0 (λ, L, A) = 1]
Game G1 . We introduce a variable AC.CREDu to record
the credentials that the honest user obtains through Oobt
and Oobt. Similarly to the proof of Theorem 1, we havePr[G0 (λ, L, A) = 1] = Pr[G1 (λ, L, A) = 1].

canon(G1 ) = ((John, children, Albert)),(John, children, Alice),(John, children, Allie))Game G2 . We deﬁne b̄ = 1 ⊕ b, as the inverse of bit∗∗b, and additional variables (m∗b̄,i, ) , Jb̄,i, (m̃∗b̄,i, ) , Db̄,i,∗∗∗ψb̄,i , Eb̄ and m̃b̄ in the similar fashion as the ones indexed
by b. These additional variables do not affect the outputof the game, so that we have Pr[G1 (λ, L, A) = 1] =Pr[G2 (λ, L, A) = 1].

Even if the user selectively discloses only the ﬁrst
and third triples of canon(G1 ), anyone can easily
guess that the unrevealed second triple must be like60

(John, children, Al...), because the canonicalisation algorithm used here is just a simple sorting based on
lexicographic order.
We can prevent this type of attack by using random
permutation to shufﬂe the order of a canonicalised orderedset. This random permutation is contained in the credentialthat is to be shared between the issuer and the user,
while the user does not have to show the permutation
to the veriﬁer because it can be implicitly embedded in
the map ψ . However, such a workaround cannot preventan adversary from guessing which credential is used in
the presentation. Therefore, we cannot yet have a fully
anonymous LDVC scheme at the moment.
We leave it as an open problem to make a full anonymous construction of LDVC instead of the above ad hoc
workarounds.



















  

 







 

   

Figure 9. Processing time of sign / sigVf







5. Performance Evaluation






We extended MATTR’s open source implementation [32] of the LDP-BBS+ scheme [31] to provide a
prototype4 and a demo application5 running in a Web
browser, implemented in TypeScript, WebAssembly andRust.
The anonymous credential scheme we used as a building block is the same as LDP-BBS +, that is, the BBS+
signature scheme [1], [9] used with the BLS 12-381
curve [6], where the size of the private key, public key,signature σ and the non-interactive zero-knowledge proofπ̃ are 32 bytes, 96 bytes, 112 bytes and 368 + 32n bytes(where n is the number of undisclosed RDF terms), respectively. We ran the above prototype on Google Chromewith an Intel i7-10750H @ 2.60GHz (6 cores, 12 threads)
and 32GB RAM and measured its performance.
Figure 9 shows the processing time of sign and sigVf
for the number of RDF terms contained in the Linked Data
to be signed, where “sign (AC)” and “sigVf (AC)” indicate
only the time for the anonymous credential computation,that is, BBS + signature generation and veriﬁcation. Similarly, the processing times of show and verify for thenumber of unrevealed RDF terms during the veriﬁable
presentation are shown in Figure 10. Here, the numberof revealed terms is ﬁxed at 30 in all cases because thedominant factor is the number of unrevealed terms rather
than revealed terms.
It can be seen that most of the processing time isspent on the underlying anonymous credential, that is, theBBS + signature scheme. The processing time increases
in proportion to the number of RDF terms, since both
our construction and the underlying BBS+ scheme do not
use any accumulator in order to implement the proof ofequality that is necessary to link multiple data in the zeroknowledge fashion in our proposed use case. When around
200 out of 230 RDF terms are unrevealed, the processing
time required for signing, signature veriﬁcation, showing,
and its veriﬁcation can all be performed within one second, which shows that a user using Google Chrome takes
at most one second to selectively disclose 50 attributes
from the Linked-Data based veriﬁable credentials with
about 60 attributes in total.
















              

Figure 10. Processing time of show / verify

Note that the issuance of bound credentials, that is,issue and obtain, has not yet been implemented and shouldbe treated as future work.

6. Conclusion and Future WorkIn this paper, we present a construction of LinkedData based veriﬁable credentials, introduce its security
model handling RDF graphs, and prove the security andprivacy of our construction using the model. Additionally,
we implement a prototype and a demo application to evaluate the practicality of our construction. Our performance
evaluation shows that a user using Google Chrome takes
at most one second to selectively disclose 50 attributes
from the Linked-Data based veriﬁable credentials with 60
attributes in total.
Our current construction satisﬁes a weaker notion ofanonymity. Fully anonymous constructions are currently
declared to be an open problem. Future work also includes adding features such as revocation, delegation,
range proofs, pseudonyms, and anonymous issuer [4]to our model and conﬁguration. As with existing graphsignatures [33], [42] and redactable signatures [35], it isalso desirable to achieve constant proof sizes and veriﬁcation times independent of the number of attributes.
Furthermore, in this paper, we have processed Linked
Data in a procedural way using canon, reorder and otherutility functions. However, it is worth considering a more
algebraic and/or order-agnostic approach, such as the set
commitment scheme in [20] or the Monipoly scheme [41],for the sake of constructing fully anonymous schemes.

References

4. https://github.com/zkp-ld/jsonld-signatures-bbs
5. https://playground.zkp-ld.org/

[1]

61

M. H. Au, W. Susilo, and Y. Mu, “Constant-size dynamic k-TAA,”in SCN 06, ser. LNCS, R. D. Prisco and M. Yung, Eds., vol. 4116.

[22] A. Hogan, “Canonical forms for isomorphic and equivalent RDF
graphs: algorithms for leaning and labelling blank nodes,” ACM
Transactions on the Web (TWEB), vol. 11, no. 4, pp. 1–62, 2017.
[23] IATA(International Air Transport Association). IATA travel passinitiative. [Online]. Available: https://www.iata.org/en/programs/
passenger/travel-pass/[24] ISO Central Secretary, “Financial services ̶ legal entity identiﬁer (LEI) ̶ part 1: Assignment,” International Organization forStandardization, Geneva, CH, Standard ISO/IEC TR 17442-1:2020,2020.
[25] Kaliya Young. Veriﬁable credentials ﬂavors explained.
[Online]. Available: https://www.lfph.io/wp-content/uploads/2021/
02/Veriﬁable-Credentials-Flavors-Explained.pdf[26] G. Kellogg, D. Longley, and P.-A. Champin. (2020, Jul.) JSON-LD
1.1. W3C. [Online]. Available: https://www.w3.org/TR/json-ld11/[27] ——. (2020, Jul.) JSON-LD 1.1 processing algorithms and API.
W3C. [Online]. Available: https://www.w3.org/TR/json-ld11-api/[28] T. Lodderstedt and K. Yasuda. (2021, Dec.) OpenID
Connect
forveriﬁablecredential
issuance.
Workin progress. [Online]. Available: https://openid.net/specs/
openid-connect-4-veriﬁable-credential-issuance-1 0.html[29] D. Longley. (2021) RDF dataset canonicalization. W3C Credentials
Community Group. Work in progress. [Online]. Available:
https://json-ld.github.io/rdf-dataset-canonicalization/spec/[30] D. Longley and M. Sporny. (2022, Mar.) Data integrity 1.0.
W3C Credentials Community Group. Work in progress. [Online].
Available: https://w3c-ccg.github.io/data-integrity-spec/[31] T. Looker and O. Steele. (2021) BBS+ signatures 2020.
W3C Credentials Community Group. [Online]. Available: https://w3c-ccg.github.io/ldp-bbs2020/[32] MATTR Limited. jsonld-signatures-bbs. [Online]. Available:
https://github.com/mattrglobal/jsonld-signatures-bbs[33] T. Nakanishi, H. Yoshino, T. Murakami, and G.-V. Policharla, “Efﬁcient zero-knowledge proofs of graph signature for connectivity
and isolation using bilinear-map accumulator,” in Proceedings ofthe 7th ACM Workshop on ASIA Public-Key Cryptography, 2020,
pp. 9–18.
[34] D. Pointcheval and O. Sanders, “Reassessing security of randomizable signatures,” in CT-RSA 2018, ser. LNCS, N. P. Smart, Ed.,
vol. 10808. Springer, Heidelberg, Apr. 2018, pp. 319–338.
[35] O. Sanders, “Efﬁcient redactable signature and application toanonymous credentials,” in PKC 2020, Part II, ser. LNCS, A. Kiayias, M. Kohlweiss, P. Wallden, and V. Zikas, Eds., vol. 12111.
Springer, Heidelberg, May 2020, pp. 628–656.
[36] Schema.org. [Online]. Available: https://schema.org[37] G. Schreiber and Y. Raimond. (2014, Jun.) RDF 1.1
primer. W3C. [Online]. Available: https://www.w3.org/TR/2014/
NOTE-rdf11-primer-20140624/[38] Y. Sheffer, D. Hardt, and M. Jones, “JSON Web Token Best Current
Practices,” RFC 8725, Feb. 2020.
[39] M. Sporny, D. Longley, M. Sabadello, D. Reed, O. Steele, and
C. Allen. (2021, Aug.) Decentralized identiﬁers (dids) v1.0. W3C.
[Online]. Available: https://www.w3.org/TR/did-core/[40] M. Sporny, G. Noble, D. Longley, D. Burnett, B. Zundel,
and K. D. Hartog. (2022, Mar.) Veriﬁable credentials data
model 1.1. W3C. [Online]. Available: https://www.w3.org/TR/
2022/REC-vc-data-model-20220303/[41] S.-Y. Tan and T. Groß, “MoniPoly - an expressive q -SDHbased anonymous attribute-based credential system,” in ASIACRYPT 2020, Part III, ser. LNCS, S. Moriai and H. Wang, Eds.,
vol. 12493. Springer, Heidelberg, Dec. 2020, pp. 498–526.
[42] S.-Y. Tan, I. Sfyrakis, and T. Gross, “A q-SDH-based graphsignature scheme on full-domain messages with efﬁcient protocols,” Cryptology ePrint Archive, Report 2020/1403, 2020, https://eprint.iacr.org/2020/1403.
[43] O. Terbu, T. Lodderstedt, K. Yasuda, A. Lemmon, and T. Looker.
(2022, Jan.) OpenID Connect for veriﬁable presentations.
Work in progress. [Online]. Available: https://openid.net/specs/
openid-connect-4-veriﬁable-presentations-1 0-ID1.html[44] K. Yasuda and M. B. Jones. (2022, Jan.) Self-issued OpenID
provider v2. Work in progress. [Online]. Available: https://openid.net/specs/openid-connect-self-issued-v2-1 0-ID1.html

Springer, Heidelberg, Sep. 2006, pp. 111–125.
[2]

F. Baldimtsi and A. Lysyanskaya, “Anonymous credentials light,”
in ACM CCS 2013, A.-R. Sadeghi, V. D. Gligor, and M. Yung,
Eds. ACM Press, Nov. 2013, pp. 1087–1098.

[3]

C. Bizer, T. Heath, and T. Berners-Lee, “Linked data: The story sofar,” in Semantic services, interoperability and web applications:emerging concepts. IGI global, 2011, pp. 205–227.

[4]

J. Bobolz, F. Eidens, S. Krenn, S. Ramacher, and K. Samelin,“Issuer-hiding attribute-based credentials,” in Cryptology and Network Security, M. Conti, M. Stevens, and S. Krenn, Eds. Cham:
Springer International Publishing, 2021, pp. 158–178.

[5]

D. Boneh, X. Boyen, and H. Shacham, “Short group signatures,” in
CRYPTO 2004, ser. LNCS, M. Franklin, Ed., vol. 3152. Springer,
Heidelberg, Aug. 2004, pp. 41–55.

[6]

S. Bowe. (2017) BLS12-381: New zk-SNARK elliptic curve
construction. [Online]. Available: https://electriccoin.co/blog/
new-snark-curve[7]

S. Brands, Rethinking public key infrastructures and digital certiﬁcates: building in privacy. MIT Press, 2000.

[8]

T. Bray, “The JavaScript Object Notation (JSON) Data Interchange
Format,” RFC 8259, Dec. 2017.

[9]

J. Camenisch, M. Drijvers, and A. Lehmann, “Anonymous attestation using the strong difﬁe hellman assumption revisited,” inInternational Conference on Trust and Trustworthy Computing.
Springer, 2016, pp. 1–20.

[10] J. Camenisch, S. Krenn, A. Lehmann, G. L. Mikkelsen, G. Neven,and M. Ø. Pedersen, “Formal treatment of privacy-enhancing credential systems,” in SAC 2015, ser. LNCS, O. Dunkelman and
L. Keliher, Eds., vol. 9566. Springer, Heidelberg, Aug. 2016,
pp. 3–24.
[11] J. Camenisch and A. Lysyanskaya, “A signature scheme with
efﬁcient protocols,” in SCN 02, ser. LNCS, S. Cimato, C. Galdi,
and G. Persiano, Eds., vol. 2576. Springer, Heidelberg, Sep. 2003,
pp. 268–289.
[12] ——, “Signature schemes and anonymous credentials from bilinear
maps,” in CRYPTO 2004, ser. LNCS, M. Franklin, Ed., vol. 3152.
Springer, Heidelberg, Aug. 2004, pp. 56–72.
[13] S. Celi, A. Davidson, A. Faz-Hernández, S. Valdez, andC. Wood. (2022, Apr.) Privacy pass issuance protocol (draft-ietfprivacypass-protocol-04). Work in progress. [Online]. Available:
https://datatracker.ietf.org/doc/draft-ietf-privacypass-protocol/[14] D. Chaum, “Blind signatures for untraceable payments,” in
CRYPTO’82, D. Chaum, R. L. Rivest, and A. T. Sherman, Eds.
Plenum Press, New York, USA, 1982, pp. 199–203.
[15] ——, “Security without identiﬁcation: Transaction systems to makebig brother obsolete,” Communications of the Association for Computing Machinery, vol. 28, no. 10, pp. 1030–1044, 1985.
[16] S. Curren, T. Looker, and O. Terbu. (2022) DIDComm messaging.
Work in progress. [Online]. Available: https://identity.foundation/
didcomm-messaging/spec/[17] A. Davidson, I. Goldberg, N. Sullivan, G. Tankersley, and F. Valsorda, “Privacy pass: Bypassing internet challenges anonymously,”
PoPETs, vol. 2018, no. 3, pp. 164–180, Jul. 2018.
[18] European Union. Eu digital covid certiﬁcate. [Online]. Available:
https://ec.europa.eu/info/live-work-travel-eu/coronavirus-response/
safe-covid-19-vaccines-europeans/eu-digital-covid-certiﬁcate en[19] A. Fiat and A. Shamir, “How to prove yourself: Practical solutions
to identiﬁcation and signature problems,” in CRYPTO’86, ser.
LNCS, A. M. Odlyzko, Ed., vol. 263. Springer, Heidelberg, Aug.
1987, pp. 186–194.
[20] G. Fuchsbauer, C. Hanser, and D. Slamanig, “Structure-preserving
signatures on equivalence classes and constant-size anonymous
credentials,” Journal of Cryptology, vol. 32, no. 2, pp. 498–546,
Apr. 2019.
[21] T. Groß, “Signatures and efﬁcient proofs on committed graphs
and NP-statements,” in FC 2015, ser. LNCS, R. Böhme andT. Okamoto, Eds., vol. 8975. Springer, Heidelberg, Jan. 2015,
pp. 293–314.

62

G0 , G 1 , G 2

Oshow (u, (cidi , ϕi )i∈[I] , m)
λ1:prm ← AC.prmGen(1 , 3L)2:(isk , ipk ) ← AC.ikGen(prm)3:for u ∈ [U ] : usku ← AC.uskGen(prm)

4:

5:
6:

∗

∗

∗
∗
∗
∗
∗
((ipki , Gi , bi )i∈[I ∗ ] , m , π )∗← A(prm, ipk ; Oobtiss , Oiss , Osign , Oshow )∗∗∗∗(π̃ , (ψi , Ji )i∈[I ∗ ] ) ← π∗

for i ∈ [I ] :
∗

7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

∗

∗

∗

1:

if (ϕi )i∈[I] is incorrect : return ⊥2:

for i ∈ [I] :3:(ipki , Gi , σi , bi ) ← CREDu [cidi ]; Gi ← ϕi (Gi )4:(mi, ) ← ﬂatten(canon(Gi )); Ji ← |Gi |5:(m̃i, ) ← ﬂatten(ϕi (canon(Gi )))6:

for m̃i, ∈ (m̃i, ) :if m̃i, ∈ X : Eq[m̃i, ] ← Eq[m̃i, ] ∪ {(i, )}7:∗(m̃i, ) ← ﬂatten(reorder(canon(Gi ), ψi , Ji ))

8:

∗
∗
(mi, ) ← (m̃i, )
∗∗for m̃i, ∈ (m̃i, ) :∗if m̃i, ∈ X :∗∗Eq[m̃i, ] ← Eq[m̃i, ] ∪ {(i, )};
∗

9:
10:

∗

mi, ← ⊥elseif m̃i, = ⊥ : Di ← Di ∪ {}ψi ← mapGen(canon(ϕi (Gi )), ϕi (canon(Gi )))E ← {Eq[X] : X ∈ X }11:m̃ ← (((m̃i, ) , ψi , Ji )i∈[I] , E, m)

12:

for i ∈ [I] :

(1,2)

13:

(ipki , (mi, ) , σi , bi ) ← AC.CREDu [cidi ]

∗
∗
∗
∗
∗
m̃ ← (((m̃i, ) , ψi , Ji )i∈[I ∗ ] , E , m )
∗
∗
∗
∗
∗
∗
∗
b1 ← AC.verify((ipki , (mi, ) , bi )i∈[I ∗ ] , E , m̃ , π̃ )14:

for mi, ∈ (mi, ) :

∗
∗
∗
∗
∗
∗ (2)
b∗∗
1 ← AC.verify((ipki , (mi, ) , bi )i∈[I ∗ ] , E , m̃ , π̃ )
∗
∗
∗
∗
∗
b2 ← [((ipki , Gi , bi )i∈[I ∗ ] , m ) ∈/ PRES]
(2)
∗
∗
∗
∗
∗
b∗∗
←
[((ipk
,
(m
)
,
b
)
,
E
, m̃∗ ) ∈/ AC.PRES]

i∈[I
]
2
i
i,
i
∗
∗
∗
∗
b3 ← [ipk ∈ {ipki }i∈[I ∗ ] ]; b4 ←
(2)
∗
∗
∗∗
b∗∗
3 ← [ipk ∈ {ipki }i∈[I ∗ ] ]; b4 ←∗∗∗∗for i ∈ {i ∈ [I ] : ipki = ipk } :∗∗∗
b4 ← b4 ∧ [∀G ∈ ATTR. Gi∗  G]

16:E

← {Eq[X] : X ∈ X }

∗

(2)
∗∗
∗
b∗∗
4 ← b4 ∧ [∀(m ) ∈ AC.ATTR. (mi∗ , ) ⊆ (m ) ]
(0,1)

23:

∗
∗
∗
return b∗
1 ∧ b2 ∧ b 3 ∧ b4

24:

∗∗
∗∗
∗∗ (2)
return b∗∗
1 ∧ b 2 ∧ b3 ∧ b 4

Oobtiss (u, G, b)

if  ∈ Di : mi, ← mi, else : mi, ← ⊥

15:

17:



(m ) ← ﬂatten(canon(G))

2:if b : σ, · ← AC.obtain(usku , ipk , (m ) ),

∗

∗

∗

AC.issue(isk , (m ) )
∗if ∃(i, ), (i ,  ) ∈ E ∈ E. [m(i,) = m(i , ) ] : return ⊥if ∃(i, ) ∈ E ∈ E. [ ∈ Di ] : return ⊥∗18:π̃ ← AC.show(usku , (ipki , (mi, ) , σi , Di , bi )i∈[I] , E, m̃)19:

if π̃ = ⊥ : return ⊥20:

AC.PRES ← AC.PRES ∪ {((ipki , (mi, ) , bi )i∈[I] , E, m̃)}21:

π ← (π̃, (ψi , Ji )i∈[I] )22:

if π = ⊥ : return ⊥23:

PRES ← PRES ∪ {((ipki , Gi , bi )i∈[I] , m)}24:

return π

Osign (G)1:(m ) ← ﬂatten(canon(G))

1:(m ) ← ﬂatten(canon(G))

2:·, b ← A, AC.issue(isk , (m ) )

2:σ ← AC.sign(isk , (m ) )3:

if b = ⊥ :3:

ATTR ← ATTR ∪ {G}4:

AC.ATTR ← AC.ATTR ∪ {(m ) }5:

return σ∗

4:

ATTR ← ATTR ∪ {G}4:if σ = ⊥ : return ⊥5:

AC.ATTR ← AC.ATTR ∪ {(m ) }5:

cid ←$ {0, 1} ; CREDu [cid] ← (ipk , G, σ, b)∗6:AC.CREDu [cid] ← (ipk , (m ) , σ, b)

7:

return cid

(1,2)



else : σ ← AC.sign(isk , (m ) )

∗

(1,2)

(1,2)

3:

∗

(1,2)



Oiss (G)

1:

(1,2)

(1,2)

(1,2)

∗

(1,2)

Figure 11. Unforgeability games of LDVCAC . Highlighted codes with superscript i ∈ {0, 1, 2} are evaluated only in game Gi .

63

(1,2)

ExpufAC (λ, 3L, B)
prm ← AC.prmGen(1 , 3L)2:(isk , ipk ) ← AC.ikGen(prm)3:for u ∈ [U ] : usku ← AC.uskGen(prm)

4:

∗

∗

∗

∗
∗
∗
∗
∗
∗
((ipki , (mi, ) , bi )i∈[I ∗ ] , E , m̃ , π̃ )← B(prm, ipk∗ ; OAC.obtiss , OAC.iss , OAC.sign , OAC.show )
∗
∗ ∗
∗
∗
1: ((ipki , Gi , bi )i∈[I ∗ ] , m , π )∗← A(prm, ipk ; Oobtiss , Oiss , Osign , Oshow )

2:
3:
4:

8:
9: E
10:
11:
5:
6:
7:
8:
9:
10:

∗

for i ∈ [I] :3:(ipki , Gi , σi , bi ) ← CREDu [cidi ]; Gi ← ϕi (Gi )4:(mi, ) ← ﬂatten(canon(Gi )); Ji ← |Gi |5:(m̃i, ) ← ﬂatten(ϕi (canon(Gi )))6:

for m̃i, ∈ (m̃i, ) :if m̃i, ∈ X : Eq[m̃i, ] ← Eq[m̃i, ] ∪ {(i, )}elseif m̃i, = ⊥ : Di ← Di ∪ {}ψi ← mapGen(canon(ϕi (Gi )), ϕi (canon(Gi )))10:E ← {Eq[X] : X ∈ X }11:m̃ ← (((m̃i, ) , ψi , Ji )i∈[I] , E, m)

12:π̃ ← OAC.show (u, (cidi , Di )i∈[I] , E, m)
1:

∗
∗
∗
Eq[m̃i, ] ← Eq[m̃i, ] ∪ {(i, )}; mi, ← ⊥← {Eq[X] : X ∈ X }∗∗∗∗m̃ ← (((m̃i, ) , ψi , Ji )i∈[I ∗ ] , E ∗ , m∗ )
∗
∗
∗
∗
∗
∗
return ((ipki , (mi, ) , bi )i∈[I ∗ ] , E , m̃ , π̃ )Oobtiss (u, G, b)/ given to A by B

1:(m ) ← ﬂatten(canon(G))

2:cid ← OAC.obtiss (u, (m ) , b)σ, ·4: cid ←$ {0, 1}∗

7:

if ∃(i, ) ∈ E ∈ E. [ ∈ Di ] : return ⊥∗π̃ ← AC.show(usku , (ipki , (mi, ) , σi , Di , bi )i∈[I] , E, m̃)

8:

if π̃ = ⊥ : return ⊥9:
AC.PRES ← AC.PRES ∪ {((ipki , (mi, ) , bi )i∈[I] , E, m̃)}10:

return π̃

13:π ← (π̃, (ψi , Ji )i∈[I] )14:

if π = ⊥ : return ⊥15:

PRES ← PRES ∪ {((ipki , Gi , bi )i∈[I] , m)}16:

return π/ given to A by B(m ) ← ﬂatten(canon(G))

2:OAC.iss ((m ) )
·, b

2:

if b = ⊥ :4:←/ given to B

1:(m ) ← ﬂatten(canon(G))

2:σ ← OAC.sign ((m ) )AC.ATTR ← AC.ATTR ∪ {(m ) }if b = ⊥ :ATTR ← ATTR ∪ {G}2:

AC.ATTR ← AC.ATTR ∪ {(m ) }3:

return σ

4:

return σ∗

Figure 12. Adversary B against the unforgeability of LDVCAC .

64∗
σ ← AC.sign(isk , (m ) )ATTR ← ATTR ∪ {G}CREDu [cid] ← (ipk , G, σ, b); return cid/ given to B

1:

3:

6: return cid
3:/ given to A by B

Osign (G)∗A, AC.issue(isk , (m ) )

1:
3:
3:

∗
5: AC.CREDu [cid] ← (ipk , (m ) , σ, b)if  ∈ Di : mi, ← mi, else : mi, ← ⊥ if ∃(i, ), (i ,  ) ∈ E ∈ E. [m(i,) = m   ] : return ⊥(i , )

1:←

3: if σ = ⊥ : return ⊥for mi, ∈ (mi, ) :6:

Oiss (G)/ given to B

(ipki , (mi, ) , σi , bi ) ← AC.CREDu [cidi ]

3:

5:

∗
∗
AC.obtain(usku , ipk , (m ) ),∗AC.issue(isk , (m ) )∗else : σ ← AC.sign(isk , (m ) )1: if b :/ given to B

for i ∈ [I] :

2:

4:

∗∗
∗
∗
∗
∗
∗
∗
b1 ← AC.verify((ipki , (mi, ) , bi )i∈[I ∗ ] , E , m̃ , π̃ )
∗∗
∗
∗
∗
∗
∗
b2 ← [((ipki , (mi, ) , bi )i∈[I ∗ ] , E , m̃ ) ∈/ AC.PRES]
∗∗
∗
∗
∗∗
b3 ← [ipk ∈ {ipki }i∈[I ∗ ] ]; b4 ←∗∗∗∗for i ∈ {i ∈ [I ] : ipki = ipk } :∗∗∗∗∗
b4 ← b4 ∧ [∀(m ) ∈ AC.ATTR. (mi∗ , ) ⊆ (m ) ]
∗∗
∗∗
∗∗
∗∗
return b1 ∧ b2 ∧ b3 ∧ b4

2:

2:

9:

∗
∗
(mi, ) ← (m̃i, )
∗∗for m̃i, ∈ (m̃i, ) :∗if m̃i, ∈ X :7:

if (ϕi )i∈[I] is incorrect : return ⊥

8:

∗
∗
∗
(π̃ , (ψi , Ji )i∈[I ∗ ] ) ← π∗
for i ∈ [I ] :∗∗∗(m̃i, ) ← ﬂatten(reorder(canon(Gi ), ψi , Ji∗ ))

6:

1:

7:

∗

5:

/ given to A by B

Oshow (u, (cidi , ϕi )i∈[I] , m)
λ1:

G0 , G1 , G2 , G3Expan
AC (λ, 3L, B)

λ1:b ←$ {0, 1}; prm ← AC.prmGen(1 , 3L)2:

for u ∈ [U ] : usku ← AC.uskGen(prm)3:((u0 , cid0,i , ϕ0,i )i∈[I ∗ ] , (u1 , cid1,i , ϕ1,i )i∈[I ∗ ] , m )

4:
5:
6:
7:

8:

∗

∗

∗

∗

∗

∗

∗

∗

← A(prm; Oobt , Oobt , Oshow )

∗

∗

∗

∗

11:

for m̃b,i, ∈ (m̃b,i, ) :

∗

∗

∗

∗

∗

5:

6:

∗

∗

8:
9:

∗

(m̃∗
) ← ﬂatten(ϕ∗(canon(G∗)))
b̄,i, 
b̄,i
b̄,i

19:

for m̃∗∈ (m̃∗) :b̄,i,
b̄,i, 

12:(2,3,4)13:(2,3,4)14:(2,3,4)∗∗
elseif m̃∗= ⊥ : Db̄,i← Db̄,i∪ {}b̄,i,

(2,3,4)

17:

22:
23:

∗
∗
∗
∗
if (ψ0,i, J1,i)i : return 0, J0,i)i = (ψ1,i

24:

∗
∗
else : (ψi∗ , Ji∗ ) ← (ψ0,i, J0,i
)

18:
19:

(3,4)

20:

(3,4)

21:

∗

∗
∗
∗
(u1 , cid1,i , D1,i )i∈[I ∗ ] , E ∗ , m̃∗ )25:

Eb ← {Eq[X] : X ∈ X }26:

Eb̄∗ ← {Eq[X] : X ∈ X }27:

m̃b ← (((m̃b,i, ) , ψb,i , Jb,i )i∈[I ∗ ] , Eb , m )

28:

∗
∗
← (((m̃∗) , ψb̄,i, Jb̄,i)i∈[I ∗ ] , Eb̄∗ , m∗ )m̃∗b̄b̄,i, 

29:∗∗
if (E0∗ , m̃∗0 ) = (E1 , m̃1 ) : return 030:

else : (E ∗ , m̃∗ ) ← (E0∗ , m̃∗0)31:

for i ∈ [I ∗ ] :∗∗(2,3,4)
∗

∗

4:

∗

5:

for i ∈ [I ] :
∗

∗

∗

∗

∗

(ipk0,i , (m0,i, ) , σ0,i , b0,i ) ← AC.CREDu∗ [cid0,i ]

(4)

8:

0
(4)
∗
∗
∗
(ipk∗
[cid∗
1,i , (m1,i, ) , σ1,i , b1,i ) ← AC.CREDu∗
1,i ]
1

9:

(4)
∗
∗
∗ , b0,i )i∈[I ∗ ]if (ipk∗
0,i , (m0,i, )∈D0,i

10:b ← B(π̃ ∗ ; OAC.obt , OAC.obt , OAC.show )(2,3,4)

6:

(3,4)

7:

(3,4)

(4)

∗
∗
∗
∗
(ipk∗
0,i , (m0,i, ) , σ0,i , b0,i ) ← AC.CREDu∗ [cid0,i ]∗∗= (ipk∗1,i , (m1,i, )∈D ∗ , b1,i )i∈[I ∗ ] : return 0

if π̃ = ⊥ : return 0

37:

∗
∗
π ∗ ← (π̃ ∗ , (ψb,i, Jb,i)i∈[I ∗ ] )∗return (b = b)if σ = ⊥ : return ⊥4:

CREDu [cid] ← (ipk, G, σ, 1)

5:AC.CREDu [cid] ← (ipk, (m ) , σ, 1)(1,2,3,4)

OAC.obt (u, cid, ipk, (m ) )2:

if AC.sigVf(ipk, (m ) , σ) = 0 : return ⊥3:

CREDu [cid] ← (ipk, G, σ, 0)

4:AC.CREDu [cid] ← (ipk, (m ) , σ, 0)/ given to B

1:

σ, ·

2:

∗
AC.obtain(usku , ipk, (m ) ), A
if σ = ⊥ : return ⊥3:

AC.CREDu [cid] ← (ipk, (m ) , σ, 1)←

CREDu [cid] ← (ipk, G, σ, 1)Oobt (u, cid, ipk, G, σ)Oobt (u, cid, ipk, G, σ)(m ) ← ﬂatten(canon(G))∗

return (b = b)(m ) ← ﬂatten(canon(G))

3:

1:

∗

∗

2:

(m ) ← ﬂatten(canon(G))

3:

b

1:

Oobt (u, cid, ipk, G)
2:

π

2:

Oobt (u, cid, ipk, G)∗∗
σ, · ← AC.obtain(usku , ipk, (m ) ), A∗∗∗← (π̃ , (ψi , Ji )i∈[I ∗ ] )∗← A(π ; Oobt , O  , Oshow )obt∗return b

1:

3:
11:

(0,1,2)(3,4)π ← (π̃ , (ψi∗ , Ji∗ )i∈[I ∗ ] )∗∗b ← A(π ; Oobt , Oobt , Oshow );

∗

(4)

1,i
∗
∗
∗
∗
∗
∗
∗
π̃ ← AC.show(usku∗ , (ipkb,i , (mb,i, ) , σb,i , Db,i , bb,i )i∈[I ∗ ] ,b∗∗ (0,1,2) ∗∗(3,4)
Eb , m̃b
E , m̃
)
∗

36:

1:

∗

0
∗
∗
∗
∗
∗
(ipk1,i , (m1,i, ) , σ1,i , b1,i ) ← AC.CREDu∗ [cid1,i ]
1∗∗∗
if (ipk0,i , (m0,i, )∈D∗ , b0,i )i∈[I ∗ ]
0,i
∗
∗
∗
= (ipk1,i , (m1,i, )∈D∗ , b1,i )i∈[I ∗ ] : return 01,i∗∗π̃ ← AC.show(usku∗ ,
b
∗
∗
∗
∗
∗
∗
∗
(ipkb,i , (mb,i, ) , σb,i , Db,i , bb,i )i∈[I ∗ ] , E , m̃ )

∗

∗

∗
∗
∗
∗
else : (ψi , Ji ) ← (ψ0,i , J0,i )∗E  ← {Eq[X] : X ∈ X }
b
∗
∗
∗
∗
∗
m̃  ← (((m̃ ) , ψ  , J  )i∈[I ∗ ] , E  , m∗ )bb ,i, 
b ,i
b ,i
b
∗
∗
∗
∗
if (E0 , m̃0 ) = (E1 , m̃1 ) : return 0∗∗∗∗else : (E , m̃ ) ← (E0 , m̃0 )∗∗∗return ((u0 , cid0,i , D0,i )i∈[I ∗ ] ,16:(2,3,4)(2,3,4)∗ψb̄,i← mapGen(canon(ϕ∗(G∗)), ϕ∗(canon(G∗
)))
b̄,i
b̄,i
b̄,i
b̄,i

∗

∗

∗
∗
∗
∗
if (ψ0,i , J0,i )i = (ψ1,i , J1,i )i : return 015:

if m̃∗∈ X : Eq[m̃∗] ← Eq[m̃∗] ∪ {(i, )}b̄,i,
b̄,i,
b̄,i,

21:∗∗∗
for m̃ ∈ (m̃ ) :b ,i,
b ,i, ∗∗∗
if m̃ ∈ X : Eq[m̃ ] ← Eq[m̃ ] ∪ {(i, )}b ,i,
b ,i,
b ,i,
∗∗∗elseif m̃ = ⊥ : D 
← D 
∪ {}
b ,i,
b ,i
b ,i
∗
∗
∗
∗
∗
ψ 
← mapGen(canon(ϕ  (G  )), ϕ  (canon(G  )))
b ,i
b ,i
b ,i
b ,i
b ,i

11:

18:

20:

10:

(2,3,4)∗(m∗) ← ﬂatten(canon(G∗)); Jb̄,i← |G∗|b̄,i, 
b̄,i
b̄,i

∗

return 0for b ∈ {0, 1} :∗for i ∈ [I ] :
∗
∗
∗
∗
(m 
) ← ﬂatten(canon(G  )); J ← |G  |b ,i, 
b ,i
b ,i
b ,i
∗
∗
∗
(m̃ 
) ← ﬂatten(ϕ  (canon(G  )))b ,i, 
b ,i
b ,i

7:

(2,3,4)b̄ ← b ⊕ 1

for i ∈ [I ∗ ] :

39:

4:

ψb,i ← mapGen(canon(ϕb,i (Gb,i )), ϕb,i (canon(Gb,i )))

16:

38:

3:

∗

∗

∗

← A(prm; Oobt , O  , Oshow )obt∗
for i ∈ [I ] :∗∗∗∗(ipk0,i , G0,i , σ0,i , b∗0,i ) ← CREDu∗ [cid0,i ]
0
∗
∗
∗
∗
(ipk1,i , G1,i , σ1,i , b1,i ) ← CREDu∗ [cid∗
1,i ]
1
∗
∗
∗
∗
if (ipk0,i , ϕ0,i (canon(G0,i )), |G∗
0,i |, b0,i )i∈[I ∗ ]∗∗∗∗= (ipk1,i , ϕ1,i (canon(G1,i )), |G1,i |, b∗1,i )i∈[I ∗ ] :2:∗elseif m̃b,i, = ⊥ : Db,i ← Db,i ∪ {}

∗

∗

∗
∗
∗
∗
∗
∗
∗
((u0 , cid0,i , ϕ0,i )i∈[I ∗ ] , (u1 , cid1,i , ϕ1,i )i∈[I ∗ ] , m )

1:

∗

∗

15:

∗

← B(prm; OAC.obt , OAC.obt , OAC.show )

∗

∗

13:

35:

∗

if m̃b,i, ∈ X : Eq[m̃b,i, ] ← Eq[m̃b,i, ] ∪ {(i, )}

12:

34:

((u0 , cid0,i , D0,i )i∈[I ∗ ] , (u1 , cid1,i , D1,i )i∈[I ∗ ] , E , m̃ )∗(m̃b,i, ) ← ﬂatten(ϕb,i (canon(Gb,i )))

33:

3:

∗

for i ∈ [I ] :

10:

32:

for u ∈ [U ] : usku ← AC.uskGen(prm)

∗
∗
∗
∗
∗
(ipk0,i , G0,i , σ0,i , b0,i ) ← CREDu∗ [cid0,i ]
0
∗
∗
∗
∗
∗
(ipk1,i , G1,i , σ1,i , b1,i ) ← CREDu∗ [cid1,i ]
1
∗
∗
∗
∗
∗
if (ipk0,i , ϕ0,i (canon(G0,i )), |G0,i |, b0,i )i∈[I ∗ ]
∗
∗
∗
∗
∗
= (ipk1,i , ϕ1,i (canon(G1,i )), |G1,i |, b1,i )i∈[I ∗ ] : return 0∗(mb,i, ) ← ﬂatten(canon(Gb,i )); Jb,i ← |Gb,i |17:b ←$ {0, 1}; prm ← AC.prmGen(1 , 3L)

2:

for i ∈ [I ] :

9:

14:

λ

1:

1:

(m ) ← ﬂatten(canon(G))

2:OAC.obt (u, cid, ipk, (m ) , σ)

(1,2,3,4)

3:/ given to B

1:

if AC.sigVf(ipk, (m ) , σ) = 0 : return ⊥2:

AC.CREDu [cid] ← (ipk, (m ) , σ, 0)

CREDu [cid] ← (ipk, G, σ, 0)Figure 14. Adversary B against the anonymity of LDVCAC . The description of Oshow is same as Fig. 12 and omitted here.

Figure 13. Weak anonymity games of LDVC. Highlighted codes withsuperscript i are evaluated only in game Gi . The description of Oshow
is same as Fig. 11 and omitted here.

65