Permissionless Blockchain-Based
Sybil-Resistant Self-Sovereign Identity Utilizing
Attested Execution Secure Processors
Koichi Moriyama†

Akira Otsuka

Institute of Information Security
Yokohama, Japan
moriyama@ai.iisec.ac.jp

Institute of Information Security
Yokohama, Japan
otsuka@iisec.ac.jp

Abstract—The current circumstance that requires people more
online has encouraged us to address digital identity preserving
privacy. There is a momentum of research addressing SelfSovereign Identity (SSI); many research approach blockchain
technology as a foundation. SSI brings natural persons various
benefits such as their owning controls; on the other side, digital
identity systems in the real world require Sybil-resistance tocomply with Anti-Money-Laundering (AML) and other needs.
Our proposal in this paper is to build a secure SSI system
by utilizing permissionless blockchain and Rafael Pass et al.’s
contribution of the formal abstraction of Attested Execution
Secure Processors (AESPs). Our proposal of the AESP-based
SSI architecture and system protocols, ΠGatt , demonstrates thepowerfulness of hardware-assisted security and the formal abstraction of AESPs, fitting into building a proper SSI system thatsatisfies Sybil-resistance. Assuming AESPs and Gatt , the protocols
may eliminate the online distributed committee assumed in otherresearch such as CanDID; thus, ΠGatt allows not to rely on multiparty computation (MPC), and it brings drastic flexibility andefficiency compared with the existing SSI systems.
Index Terms—Permissionless Blockchain, Decentralized Digital
Identity, Sybil-Resistance, Self-Sovereign Identity, and Attested
Execution Secure Processors

I. I NTRODUCTION
Increasing attention to digital identity is a natural trend
in the current Covid-19 circumstances because people face
rapid changes in our lives, requiring much more online than
before, and identifying and verifying who I am has become
fundamental and daily operations under the new normal. SelfSovereign Identity (SSI) is the momentum in academia andthe tech industry. Christoper Allen expressed the history ofdigital identity and the expectation to SSI well in his blog
article in 2016 [1]. Since then, there have been many studies,
researches, and implementations until now [2] [3] [4].
The terminology “Self-Sovereign” inspires many people tothink about how SSI can protect the privacy and resolve
reliance on authorities that may control personal data. Studies
and research on SSI are not limited to technology but also government and human beings. One of those researches addresses
the relationship between SSI and GDPR [5], while there are
already some initiatives on utilizing SSI in Europe [6]. These†Also, belonging to NTT DOCOMO, INC.

情報セキュリティ総合科学第14号2023年2月

trends remind the authors of David Chaum’s approach in1985 to avoid unexpected tracing by someone else like Big
Brother1 by utilizing pseudonyms, digital signatures, and card
computers [7].
If we look at such many of those recent studies, researches,
and implementations, they focus on or are utilizing distributed
ledger and blockchain technology [8] [9]. Some researchers
addressed the necessity of blockchain; however, they still recognize that blockchain technology is a good foundation [10].
All the well-known existing implementations actually utilize
blockchains, such as uPort on Ethereum2 [11], ShoCard3 on
Bitcoin [12], and Sovrin on the Sovrin ledger [13].
Many pieces of research in this domain have addressed
SSI systems architecture. However, surprisingly – to the bestof our knowledge, no study has addressed an opportunity
to utilize hardware-assisted security [14] [15] implemented
within mobile devices that people own for their daily lives.
Several studies and implementations address mobile apps for
SSI systems, but those mobile apps focus on user experiences
and have never addressed security feature perspectives. The
card computer expressed in 1985 was a kind of dream written
as a vision; however, it has become real, and secure processors
are also becoming a norm in such mobile devices as a mandatory requirement today. Why don’t we utilize such capability
for building SSI systems?
This paper proposes a permissionless blockchain-based SSI
systems architecture that utilizes the formal abstraction of
Attested Execution Secure Processors (AESPs) [16] equippedwith mobile devices. Thus, SSI systems will gain more flexibility and efficiency than existing ones.
Contributions– Demonstrate the powerfulness of hardware-assisted security and the formal abstraction of Attested Execution
Secure Processors (AESPs) that fit to build a secure
1 See George Orwell’s novel, “Nineteen Eighty-Four(1984) – Big Brother
Is Watching You,” published in 1948.
2 https://ethereum.org
3 https://www.shocard.com

Copyright © 2022 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective
works, for resale or redistribution to servers or lists, or reuse of any copyrighted
component of this work in other works. DOI 10.1109/Blockchain55522.2022.00012

Self-Sovereign Identity (SSI) system satisfying the Sybilresistance requirement.
– In concrete, propose the AESP-based SSI systems architecture and protocols, ΠGatt , with its construction,
security properties such as Sybil-resistance, and a proof
sketch of the security properties.
– Assuming AESPs and Gatt , the AESP-based SSI systemprotocols ΠGatt eliminates the online distributed committee of trusted nodes assumed in CanDID [17]. Thus, ΠGattallows not to rely on multi-party computation (MPC) that
requires such a trusted party of nodes, and it brings more
flexibility and efficiency than the existing systems.

User (Holder)
IssuerVeri er
VC

DCmaster
DCcontext
node

node

node

DID Commi ee
node

node
node

node

Fig. 1. CanDID – A State-of-the-Art Approach toward Decentralized Digital
Identity

II. BACKGROUND
A. Digital Identity
The importance of “digital identity” is rapidly increasing
under the current circumstance. Many people must feel thatmany things have changed after the pandemic. People would
need to do much more things online than before. Service
providers, companies, and governmental organizations need toprovide services for customers, employees, and citizens online
to deal with the circumstance. Ideas and past efforts on digital
identity are not only for the occasion today, but accumulated
contributions have helped society survive the pandemic.
Researchers and influencers in the tech industry in thisdomain refer to Kim Cameron’s blog article, “The Laws of
Identity” [18]. Beyond the contribution, researchers and the industry have made significant efforts, including standardization
bodies resolving many problems from various perspectives,
such as identity proofing, authentication, and federation.
In digital identity approaches, managing claims and credentials is one of the essential elements of representing who I
am or who you are. Identity is a set of attributes or claims
by definitions, e.g., ISO/IEC 24760-1:2019(en) [19], and acredential represents an identity for use in authentication.
There are also many activities at standardization bodies such as
W3C4 , OpenID Foundation5 , and FIDO Alliance6 . The NIST’s
Digital Identity Guidelines [20] is a set of guidelines that
address various perspectives through its digital identity model.
Digital identity management started from the Isolated User
Identity (SILO) model and got moved to the Federated User
Identity (FED) model by mathematical definition of Md Sadek
Ferdous et al.’s work [21]. The (full) identity representing anatural person is a union of partial identities, each set of claimsconsisting of attribute and value pair. They demonstrated
that digital identity and identity management move from themost straightforward model toward federated models in adecentralized fashion.
B. Decentralized Digital Identity
In the tech industry, several initiatives are addressing decentralized digital identity. Microsoft has been driving an
4 https://www.w3.org
5 https://openid.net/foundation/
6 https://fidoalliance.org

情報セキュリティ総合科学第14号2023年2月

initiative7 and announced ION8 on behalf of the Decentralized
Identity Foundation (DIF)9 in May 2021. The approach utilizes
W3C’s DIDs [22], decentralized systems such as blockchainsand ledgers, and DIF’s standards. There are also many pieces
of research addressing decentralized identity in academia.
The authors would like to focus on modern cryptographic
approaches for preserving privacy because of our motivations.
Thus, we will address Deepak Maram et al.’s work [17] in thissection.
CanDID: It can do decentralized identity with legacy compatibility, Sybil-resistance, and accountability. They identify
remaining problems for building a decentralized identity system, legacy compatibility, Sybil-resistance, and accountability
as entitled. In order to solve the problems, they propose systemprotocols with a trusted committee of nodes-based architecture. Fig. 1 illustrates the overview of CanDID’s approach. In
the figure, VC stands for a Verifiable Credential, and DC stands
for a Derived Credential, DCmaster means a master credential,
and DCcontext means a context-based credential in their work.
The CanDID system protocols provide three APIs for issuing credentials, issuePreCred(), issueMasterCred(), andissueCtxCred(). CanDID supports deduplication of identities
that may ensure the existence of at most one pseudonym witha unique identifier such as Social Security Number (SSN)in the U.S. For this, the master credential, generated byissueMasterCred(), includes a special attribute dedupOver
that is designed to avoid deduplicating their identity by adversaries. This scheme enables the system to issue credentials
uniquely per user and meets Sybil-resistance.
They utilize multi-party computation (MPC) to prevent
committee members from learning unnecessarily private information. They also utilize SNARK proofs for registrationtime screening and other various purposes privacy-preserving.
They successfully demonstrated that the committee-based architecture achieves its goals with some particular purpose
MPC protocols for privacy-preserving deduplication and fuzzy
7 https://www.microsoft.com/en-us/security/business/
identity-access-management/decentralized-identity-blockchain
8 https://identity.foundation/ion/
9 https://identity.foundation

matching for scanning sanction lists to avoid Anti-MoneyLaundering (AML).

Issuer

C. Self-Sovereign Identity (SSI)
Christopher Allen published his blog article entitled “ThePath to Self-Sovereign Identity” in 2016 [1]. It presented
the evolution of digital identity from Phase 1: Centralized
Identity, Phase 2: Federated Identity, Phase 3: User-Centric
Identity through Phase 4: Self-Sovereign Identity, followed byhis definition of SSI with the ten principles:
1) Existence. Users must have an independent existence.
2) Control. Users must control their identities.
3) Access. Users must have access to their own data.
4) Transparency. Systems and algorithms must be transparent.
5) Persistence. Identities must be long-lived.
6) Portability. Information and services about identity
must be transportable.
7) Interoperability. Identities should be as widely usable
as possible.
8) Consent. Users must agree to the use of their identity.
9) Minimalization. Disclosure of claims must be minimized.
10) Protection. The rights of users must be protected.
As David Chaum proposed in 1985, the motivation toward
Self-Sovereign Identity (SSI) described by Christopher Allen
has been encouraging many researchers to create and establish
proper SSI systems preserving privacy from various perspectives [2] [23] [24] [4] [5]. Some research addressed if theten principles express all the principles that may describe theessentials of SSI [9] [25]; however, they have still been treatedas foundational principles.
1) Extended Principles: Some research addressed if theten principles express all principles which may describe theessentials of SSI. Quinten Stokkink et al. proposed to add
another principle Provable [9]. Md Sadek Ferdous et al. tried
to do a comprehensive survey and proposed five taxonomies
and 17 principles under the taxonomies of classes derived fromthe ten principles [4]. Abylay Satybaldy et al. proposed to
add Usability in their SSI evaluation framework, which also
refers to the ten principles as a comprehensive spectrum of
SSI requirements [25].
2) Building Blocks and Blockchain: Many pieces of research addressed how to build SSI systems; essential components [8], design patterns [26], and needs of, how to utilize,
or if it requires blockchain technology [9] [27] [10] [28] [5][29]. Two of these researches concluded that blockchain was
not mandated. However, they still recognize that blockchain
technology is a good foundation to build an SSI system
and indicated that some specific requirements would require
further extra efforts to fill in gaps.
3) SSI Systems with Mobile Devices: There are several
SSI implementations such as uPort and Sovrin [28] [13].
Also, some experimental research and prototypes in the techindustry support governmental agencies’ interests [30] [31].
Through such activities, including W3C’s efforts on verifiable

情報セキュリティ総合科学第14号2023年2月

Veri er
VC

DC

User (Holder)
Veri able data registry (e.g., blockchain)

Fig. 2. Proposed Self-Sovereign Identity Systems in the Tech Industry, Today

credentials and DIDs [32] [22], there has been becoming acommon structure and primary roles involved in exchanging
verifiable credentials among an issuer, a holder (a natural
person), and a verifier.
Fig. 2 illustrates such a proposed SSI solution architecture in
our interpretation. An issuer issues a verifiable credential (VCin the figure) for the holder. To minimize disclosure, they may
have a derived credential (DC in the figure) for presentation.
A verifier may verify with the received derived credential
per a request. Blockchain technology can be a verifiable dataregistry in the proposed structure.
We put a mobile phone next to the user in the figure becausesome SSI implementations provide a mobile app, such as awallet app, for their use with the SSI systems. To the bestof our knowledge, however, such mobile apps never playtheir roles to utilize hardware-assisted security features of themobile device. Kalman C. Torh et al. addressed utilizing users’
mobile devices as a digital identity for each of them [24];however, they have not mentioned opportunities for hardwarebacked attestations.
III. P RELIMINARIES - ATTESTED E XECUTION S ECURE
P ROCESSORS (AESP S )Hardware-assisted security has recently been becoming thenorm for mobile devices. Apple’s iPhone implements Secure
Enclave, a dedicated secure subsystem, and it is isolated
from the apps execution environment on the main processor10 .
Android devices support KeyStore and other security-related
functionality utilizing hardware-assisted implementations, e.g.,
TEE (Trusted Execution Environment), Arm’s TrustZone inparticular. Google recently announced the Android Ready
SE program11 , which will be supporting hardware-backed
security applets for various use cases such as digital keys andidentity credentials. In addition, Microsoft recently announced
Windows 11 with new hardware requirements in which TPM(Trusted Platform Module) 2.0 is mandated12 . There are also
other design choices among implementations in the industry,
10 https://support.apple.com/guide/security/secure-enclave-sec59b0b31ff/

web
11 https://developers.google.com/android/security/android-ready-se
12 https://docs.microsoft.com/en-us/windows/security/
information-protection/tpm/trusted-platform-module-overview

such as Global Platform-supported Secure Elements13 andIntel’s SGX14 , in addition to TrustZone and TPM 2.0.
Among numerous implementations and researches addressing hardware-assisted security including how to realize [14]and how to utilize [33], Rafael Pass et al. uniquely addressed
hardware-assisted security, secure processors, in a formal
fashion [16]. In their words, trusted hardware is commonly
believed to provide a very powerful abstraction for building
secure systems. They approached to formalize the attested
execution abstraction and retrieved the formal modeling ofa broad class of attested execution secure processors Gattfrom the common belief. Also, they successfully demonstrated
an additional observation regarding composable two-party
computation with attested execution processors.
The Formal Modeling of AESPs: GattAccording to their efforts, the attested execution abstraction
enables the following:• A platform equipped with an attested execution processor
can send a program and inputs, denoted (prog, inp), to
its local secure processor. The secure processor executes
the program over the inputs, and compute outp :=prog(inp). The secure processor then signs the tuple(prog, outp) with a secret signing key to obtain a digital
signature σM , which is commonly referred to as an“attestation,” and this entire execution is referred to as
an “attested execution.”• The program’s execution is conducted in a sandboxed
environment (an enclave, in other words), in the sensethat a software adversary and/or a physical adversary
cannot tamper with the execution or inspect data thatlives inside the enclave. This is important for realizing
privacy-preserving applications.
The ideal functionality Gatt captures the core abstractionthat a broad class of AESPs intend to provide. Gatt isparametrized with a signature scheme Σ and also a registry
reg that is meant to capture all the platforms equipped withan AESP. The registry reg is treated a static registry forsimplicity in the research. Gatt consists of the initialization
function to generate a key pair of the manufacturer public key
pkM and secret key skM , public query interface getpk(), andstateful enclave operations of Install() and Resume(), which
realize the anonymous attestation capability. A platform P thatis in the registry reg may invoke those enclave operations15 .
λ• initialization: Σ.KeyGen(1 ) → (pkM , skM ).
• public query interface: getpk() from some P: send pkM
to P.
• local interface – install an enclave: Install() from someP ∈ reg: installing a new enclave with a program prog,
henceforth referred to as the enclave program. Once
13 https://globalplatform.org/resource-publication/
introduction-to-secure-elements/
14 https://www.intel.com/content/www/us/en/architecture-and-technology/
software-guard-extensions.html
15 The notation here is modified from their original paper to adjust thefollowing descriptions in this paper, but the meaning is equivalent.

情報セキュリティ総合科学第14号2023年2月

installed, Gatt generates a fresh enclave identifier eid andreturns it to P.
• local interface – resume an enclave: Resume() fromP ∈ reg: resuming the execution of an existing enclavewith inputs inp. Once resumed, Gatt executes the prog
over the inputs inp, and obtains an output outp. Gattwould then sign the prog together with outp as wellas additional metadata, and return both outp and theresulting anonymous attestation σM to P.
IV. A RCHITECTURE AND P ROTOCOLS P ROPOSALOVERVIEW
We propose architecture and system protocols to build
a flexible, efficient, and secure SSI system by utilizing
the formal abstraction of AESPs along with permissionless
blockchain technology. Also, we would like to propose adesign and construction for realizing a secure SSI to support
Sybil-resistance based on the AESP-based SSI architecture.
A. Architecture
Fig. 3 illustrates overview of the architecture and how thebasic AESP enclave operations of Install() and Resume() areintegrated into the proposed architecture.
Overview of the main ideas are below:• A person may ask authorities such as a governmental
agency, a school, or other service providers to issue averifiable credential consisting of claims and a proof πfor each claim.
• The person may have a mobile device equipped withan AESP, complying with the proposed AESP-based SSI
architecture, needs to set up for making their device asa Self-Sovereign Identity holder. This setup operation
includes a device key pair (pkM , skM ) generation.

Fig. 3. Overview of the Proposal Architecture and the AESP Enclave
Operations of Install() and Resume()

The person may install programs, prog1,...,n , by Install()for enabling the device SSI-operations capable such as
creating derived credentials. For example, a prog isdesigned and implemented for minimizing disclosure of
their original, verifiable credentials, less than 18 years oldin particular.
• Once the installed programs are executed by Resume(),and the AESP digitally signs an output outp to provethat the programs have been executed on the specific
AESP, and signed signature is attached with the output asa proof, σM . Before generating a derived credential, theyshould be allowed to produce a pairwise pseudonym foreach entity E; thus, their identity is to be represented withE
a key pair (pkE
U , skU ). For simplicity, we will describesuch a key pair like (pkU , skU ) in this paper.
• Such verifiable credentials or derived credentials signedby the AESP with each proof are registered to a permissionless blockchain system as a repository.
• Verifiers may utilize the signed credentials with a corresponding proof for each credential to verify if a person
is requesting to subscribe and use services provided by
the verifiers.
In this proposal, the owner of a mobile device equippedwith an AESP is the person who may represent their SelfSovereign Identity. Because of utilizing AESPs, computation
for preserving privacy can securely be executed within adevice. In addition, verifiers may identify if the holder is thesame person or not since the proof is attested by the holder’sdevice equipped with an AESP. It means that MPC requiring acommittee of trusted parties is not required, and permissionless
blockchain can efficiently be utilized for openness.
•

B. Derived Credentials
Because of various needs, the proposed SSI architecture allows people to create programs for issuing derived credentials
to meet different requirements. For example, some service
providers need to verify if customers are not younger than
18 years old but do not need to know their birthday. Someagencies need to verify if applicants are formally registeredas residents in the city but do not need any other claims.
For infinite varieties of needs to utilize derived credentials
for presentation, which allows minimizing disclosure, and theprogrammable architecture allows users to choose appropriate
prog for their needs. Those programs for the proposed SSI
architecture must be public and open source for anyone toverify.
Derived Credentials for Sybil-Resistance: Unlike CanDID,
the AESP-based SSI architecture does not assume generating
the master credential, an interim credential designed to support
the deduplication of identities for satisfying Sybil-resistance.
An AESP is a unique entity capable of secure computation
within a local processor. The equipped AESP may embed an
encrypted link for derived credentials with a natural person by
their key pair (pkU , skU ). Fig. 4 illustrates the relationshipamong real identities I, Symbil-resistant credentials C, andderived credentials some of which are Sybil-resistant.

情報セキュリティ総合科学第14号2023年2月

Programs that require to manage credentials that meet the
Sybil-resistance requirement should implement a function of
injective identification map ψ between Sybil-resistant derived
credentials and C. AESP may install and execute such programs capable of treating ψ securely. The following section
and Fig. 6 will describe the detailed protocol for creating
Sybil-resistant credentials.
V. P ROTOCOLS IN D ETAIL
The proposed SSI architecture defines and provides someprimitive protocols as described in Fig. 5 and Fig. 6. In
our scheme, we assume EUF-CMA (Existential Unforgeability
under Chosen Message Attack) signature scheme Σ and INDCCA (Indistinguishability under Chosen Ciphertext Attack)encryption scheme {Gen, Enc, Dec}. Further, we assume all
AESP-equipped devices share pkM and skM as determinedin the Rafael Pass et al.’s works [16].
Definition 1 (A mobile device equipped with Gatt ). The ideal
formal abstraction of Attested Execution Secure Processors(AESPs) is said to be Gatt , and let assume that every natural
person’s mobile device who needs SSI is equipped with Gatt .
Definition 2 (A secure SSI system protocols). A set of
protocols Π is said to be secure Self-Sovereign Identity (SSI)
system protocols if and only if it satisfies Sybil-resistance,
Unforgebility, Privacy - credential-issuance and verification,and Unlinkability.
Theorem 3 (The AESP-based secure SSI system protocols).
Assuming that natural persons own their mobile devices
equipped with an AESP, Gatt enables the above proposed
protocol Π to realize a set of secure Self-Sovereign Identity(SSI) system protocols ΠGatt for them.
The AESP-based SSI architecture and its protocol ΠGatt
includes the enclave operations of Gatt , such as Install() and
Resume() as well as for set-up, in addition to Π specificprimitives such as for issuing and verifying credentials. As
described in IV-B, the AESP-based SSI architecture and primitive protocols can be extended to adopt various requirements
including Sybil-resistance.
VI. S ECURITY P ROPERTIESWith respect to the CanDID’s contributions [17], we will
follow how CanDID demonstrates their protocols of decentralized identity systems are designed securely as much as
possible. In particular, they define CanDID API; in some of
their definitions, adversaries have unlimited access to the entire

Fig. 4. Sybil-resistant derived credentials and the identification map ψ :cred → CAESP-based Secure Self-Sovereign Identity (SSI) system protocols – ΠGatt
The protocol ΠGatt consists of two classes of primitive functions; one is a class that incorporates Gatt , the ideal abstraction of
Attested Execution Secure Processors (AESPs). The other class is a set of primitive functions for Self-Sovereign Identity (SSI)
working with an AESP. The protocol ΠGatt provides flexibility by allowing a natural person to choose and install programs prog
for various needs.
The followings are ΠGatt generic functions relying on Gatt :λ• Setup(1 ) → (pkM , skM ).
1: Gatt .KeyGen(1λ ); // for generating a key pair.
2: Gatt .getpk().
// for receiving the key pair from some platform P, and sends pkM to P.
•

Install(prog) → eid.
// install a program to enclave.
1: Gatt asserts if P is honest;
2: Gatt generates a nonce eid ∈ {0, 1}λ , stores the program prog, and sends eid to P.

•

Resume(eid, inp) → (outp, σM ).
1: Gatt checks if the program prog associated eid exists, abort if not found;
2: Gatt executes prog and generates output outp;
3: Gatt generates a signature σM by Σ.SigskM (eid, prog, outp), and sends (outp, σM ) to P.

The followings are ΠGatt SSI-featured functions:λE
E• KeyGen(1 ) → (pkU , skU ).
E
1: An AESP generates a user’s key pair (pkE
U , skU ), a pseudonym for each Entity. For simplicity, we omit E in following
descriptions.
•IssueCred(skU , pkU , Stmt) → cred.
1: An AESP requests a legacy authority to issue their verifiable credential;
2: An AESP retrieves a verifiable credential from the authority, and treats {pkU , (claimi )i=1,...,n , π} as cred, where π isa proof for a set of the claims by the authority.

•

IssueDCred (skM , skU , pknew
U , ctx, cred) → derivedCred.
This function, IssueDCred(ctx), is a program prog, which can be vary for different context ctx. To install and execute prog,
1: Gatt .Install(prog) → eid;
2: Gatt .Resume(eid, inp) → (outp, σM ).
Inputs inp of ctx and cred are depend on various context, outputs output are {pknew
U , prog, (claimj )j=1,...,m , σM } asderivedCred, where σM is Σ.SigskM (eid, prog, outp), and prog should be an open-source map satisfying the following
transformation:
prog : {credk }k=1,...,l 7→ {claimj }j=1,...,mFor creating a Sybil-resistant credetial, the program prog should satisfy the construction defined in Fig. 6.

•

VerifyCred(skU , cred) → {true, false}.
User U inputs skU and cred, verifying party V inputs a challenge c, and the public key pkM is a public input. To verify
cred,
1: User U sends (cred, σM ) to V where σ = SigskU (c);2: Verifying party V checks if
VpkM (cred.body, cred.σ) = true ∧ VpkU (c, σM ) = true.
Fig. 5. The Construction of ΠGatt , AESP-based Self-Sovereign Identity (SSI) System Protocols

情報セキュリティ総合科学第14号2023年2月

The Construction for creating Sybil-resistant credentials in ΠGatt
For creating a Sybil-resistant derived credential, the program prog should satisfy the following construction: the program prog treatsb as inputs inp, where ψb is Sybil-resistant pseudonymizer to transform verifiable credentials to a set of claims satisfying(pkU , ψ)
the injective identification map
ψ : cred → C
in encrypted form. We require at least one verifiable credential, say credk , is a Sybil-resistant credential. We embed encrypted links
using IND-CCA encryption algorithm E:
ψb = E. EncpkM (credk )The program prog decrypts ψb to get ψ and checks if ψ(credk ) ∈ C.
The generated derived credential consists of pkU , ψb as prog, claims transformed by the Sybil-resistant pseudonymizer, together
with the attestation signature σM from Gatt as follows:b {claimj }j=1,...,m , σM )derivedCred ← (pkU , ψ,To generate and treat derived credentials that are Sybil-resistant need to satisfy both Definition 5 and the definitions for privacy
at the same time. These requirements contradict each other. However, only the AESP can decrypt and verify links between thederived credential and Sybil-resistant credentials. Thus, we require all derived credentials to embed an encrypted link to one of those
Sybil-resistant credentials in encrypted form.

Fig. 6. The Construction of the program for creating Sybil-resistant credentials in ΠGatt

CanDID API, which they model for conciseness as an oracleO∗ . Also, in their security definitions, the adversaries may∗that models thehave access to an external account oracle Oext
legacy providers called by CanDID. We will reuse the same
oracle models for our AESP-based SSI system protocols ΠGatt .
The protocol ΠGatt aims to satisfy the following security
properties, for each of which adversary may access and try tocorrupt, Sybil-resistance, Unforgebility, Privacy - credentialissuance and verification, and Unlinkability.
A. Sybil-ResistanceAn adversary cannot obtain Sybil-resistant credentials,
which we define as below:
Definition 4 (Sybil-resistant credential). Let I be a set of real
identities and C be a set of credentials. The credentials C issaid to be Sybil-resistant credentials if and only if there exists
a bijective map ϕ : I → C.
In the real world, a national PKI system, e.g., JPKI (described in VIII-A), is an example of authorities that can
provide a unique identifier for creating Sybil-resistant credentials. A master credential in CanDID corresponds to a
Sybil-resistant credential. We assume a single system of Sybilresistant credentials for brevity in this paper.
Definition 5 (Existence). Suppose C be a set of all Sybilresistant credentials. A derived credential cred is said to be
Sybil-resistant with respect to C if and only if, for any P P T(Probabilistic Polynomial-Time) adversary A and security
parameter λ, there exists an identification map ψ : cred → C,"Pr ψ(cred) ∈ C

pkM ,skM ←KeyGen(1λ );∗∗cred←AO ,Oext (pkM );#≥ 1 − negl(λ)

VpkM (cred.body,cred.σ)=true

Informally, this definition captures the infeasibility of an
adversary to obtain a credential that is not in the set of all

情報セキュリティ総合科学第14号2023年2月

Sybil-resistant credentials. Here, the identification map ψ isdefined over all elements in derived credentials such thatψ(cred) ∈ C. Thus, ψ uniquely ‘identifies’ the holders’ real
identity from anonymous derived credentials. In our scheme,
we assume the map ψ is accessed only by the AESP internally.
Thus, the link between derived credentials and the Sybilresistant credentials is hidden; it supports preserving privacy.

B. Unforgeability
An adversary cannot forge the credentials of honest users
or otherwise impersonate them.
Definition 6 (Unforgeability). Let chals denote a set of all
challenges and their responses produced by A in oracle access∗with O∗ and a special oracle Oskthat allows calling any
UGattΠfunctions with the user key parameter set to skU . The
protocol ΠGatt offers unforgeability if, for any stateful P P T
adversary A,
U ,cred)Pr VerifyCred(sk=truepkM ,skM ←KeyGen(1λ );pkU ,skU ←KeyGen(1λ );∗O ∗ ,Oskcred←A,O ∗ext (sk ,pk )U
MUs.t. cred.body∈chals;/ ≤ negl(λ)

The definition captures that it must be infeasible for anadversary to impersonate users, i.e., forge signatures withusers’ keys.

C. Privacy - Credential-Issuance
It is infeasible for an adversary to learn users’ attributes
from observing the derived credential-issuance protocol.

Definition 7 (Credential issuance privacy). The protocol ΠGatt
offers derived credential issue privacy if, for any stateful P P T
adversary A,
pkM ,skM ←KeyGen(1λ );





∗





′

Pr b = b





∗

O ,Oext
10
1(pkM );§ 
pkU ,skU ,{c01 ,...,cl },{c1 ,...,cl }←A0
cred0 ←IssueDCred(skM ,skU ,pkU ,{c01 ,...,cl },prog), 1
cred1 ←IssueDCred(skM ,skU ,pkU ,{c11 ,...,cl },prog) 
c0 ,prog,σ 0 )  − 1,ψwhere cred0 =(pk ,{claim0 }U

j j=1,...,m

M





1
}
as
sets;
}
={claimassert {claim0
j j=1,...,mj j=1,...,m1c1
and cred1 =(pkU ,{claim1j }j=1,...,m ,ψ ,prog,σM );2b←${0,1};∗∗′b ←AO ,Oext (credb )≤ negl(λ)

it implies that Gatt can decrypt ψb to get cred and verify the
relation cred ∈ C unless the signature σM is forged. The
latter probability is negligible given Σ is EUF-CMA signaturescheme.
B. Unforgeability
In ΠGatt based SSI systems, users’ key never leaves theirdevice with an AESP. During the protocols, they use it
only to sign challenges issued as part of VerifyCred(). Thus,
unforgeability of the ΠGatt based SSI systems follows in astraightforward way.
Here, cred has the following form:§

where {cred0k }k=1,...,l is denoted {c01 , ..., c0l } and {cred1k }k=1,...,l is denoted{c11 , ..., c1l } as a set of claims for each {0, 1}.

∗
must be a set of tuples
Queries to O∗ and Osk
U

D. Privacy - Credential-Verification
An adversary can learn about a user no more than theinformation that the user explicitly presents while using theircredentials.
Definition 8 (Credential verification privacy). Given an opensource map prog that maps user data in verifiable credentials
to derived credential claims, any P P T adversary A learns
negligibly more about any given user than the output of prog.
E. Unlinkability
The entities administering the protocol ΠGatt reliant programs cannot collude and link the respective transactions ofany given user.
Definition 9 (Unlinkability across programs). The protocol
ΠGatt offers unlinkability if, for any stateful P P T adversaryA,
pkM ,skM ←KeyGen(1λ );′Pr b = bb {claimj }j=1,...,m , σM ).
(pkU , ψ,∗∗

cred0 ,cred1 ,pkU ,skU ,ctx←AO ,Oext (pkM ); 1
assert VpkU (credb .body,credb .σ)=true for b=0,1; −b←${0,1};
2
crednew ←IssueDCred(skM ,skU ,pkU ,credb );∗∗′b ←AO ,Oext (crednew ,ctx)≤ negl(λ)

VII. A P ROOF S KETCH OF THE S ECURITY P ROPERTIES
Proof Sketch of Theorem 3. We prove that the protocol
ΠGatt defined in Fig. 5 and Fig. 6, which is a set of secureSelf-Sovereign Identity (SSI) system protocols.
A. Sybil-ResistanceFirst, we prove ΠGatt satisfies Definition 5 for Existence. It
is sufficient to prove that every derived credential cred has an
identification map ψ such that ψ(cred) ∈ C. In the protocol
ΠGatt , every cred has the following formb {claimj }j=1,...,m , σM )(pkU , ψ,
where ψb is a ciphertext of a verifiable and Sybil-resistant credential cred encrypted with the public key of Gatt . Therefore,
given
VpkU (cred.body, cred.σ) = true ⇒b {claimj }j=1,...,m , σM = true,
VpkU pkU , ψ,

情報セキュリティ総合科学第14号2023年2月(pkU , {credk }k=1,...,l , prog)b {claimj }j=1,...,m , σM ) where
and the responses are (pkU , ψ,a set of claims {claimj }j=1,...,m is the image of progwith inputs {credk }k=1,...,l . Thus, chals contains all tuples appeared in the oracle access by A of the formb {claimj }j=1,...,m ). For creating new cred such that
(pkU , ψ,
cred.body ∈/ chals, A must forge a signature cred.σ on themessage tuple cred.body. Given the underlying EUF-CMA
signature scheme Σ, this probability is bounded by negl(λ),
that is negligible in the security parameter λ.
C. Privacy - Credential-IssuanceIn our privacy game for privacy - credential-issuance, theadversary chooses a pseudonym of the user who initiates
each query and which providers are used, but otherwise
learns nothing else about users’ identities or attributes during
operations such as credentials issuance.
By Definition 7, the adversary chooses two identities of{0, 1} and observes that derived credentials are created byexecuting IssueDCred() with inputs of claims for each identity
and the program prog with the encrypted identification map
b The adversary tries to access and guess any attributes and/orψ.
values; however, they cannot guess from a derived credential
selected randomly.
Let us explain the reason behind it more. Since two credentials, cred0 and cred1 only differ in ψb0 , ψb1 and related
01signatures, σUand σU. ψb0 and ψb1 are encrypted by the
IND-CCA encryption algorithm E. Probability to distinguishthem is upper-bounded negl(λ). Therefore, we conclude thatthe adversary cannot win the game as it does not learn any
information to distinguish the verifiable credentials.
D. Privacy - Credential-Verification
In our scheme, we assume that all privacy operations for
issuing and treating credentials are executed within an AESP
internally by prog, including IssueDCred() and VerifyCred().
We also expect that only prog will be accepted by bothusers and providers that reach the consensus. Such prog only
leaks required privacy information described as a set of claims{claimj }j=1,...,m . This process are expected to leak any more
information as defined in Definition 8.

E. Unlinkability
As the same as the other privacy game for privacy credential issuance, the adversary needs to try an input but
randomly selected, and a credential cred0 or cred1 in thiscase as defined in Definition 9. It cannot guess any information to distinguish which provider from a credential selected
randomly. Therefore, we conclude that the adversary cannot
win the game for unlinkability in our scheme.
VIII. A PPLICATIONS , L IMITATIONS AND F UTURE
D IRECTIONSThere are many opportunities and applications of this proposal in the real world because of the rapid increase ofsmartphones and other mobile devices equipped with a tamperresistant secure processor in the market.
Permissionless blockchain in this proposal plays a role inbuilding Self-Sovereign Identity (SSI) systems as a foundation.
Like previous research and implementations, it works forverifiable data registries; however, the use is not limited tostoring and retrieving verifiable and derived credentials as aregistry. In addition, combining permissionless blockchain and
AESPs may extend the usage. For instance, secure programsfor creating derived credentials by IssueDCred(), which allows
for a user to choose a program prog depending on different
context ctx, can and should probably be registered andmaintained on the permissionless blockchain. Also, derived
credentials created by the user’s device with an AESP may
represent the person on permissionless blockchain ecosystems,preserving privacy. Because of the recent rapid growth ofblockchain-based business ecosystems, opportunities to utilize
the main idea of this proposal to combine permissionless
blockchain and AESPs are unlimited.
A. Applications
One of the well-known initiatives is mDL, mobile driver’s
license16 . It must be helpful, but people would not always
be happy to show their driver’s license even though it allows
them to choose to show only requested data such as nameand age. The AESP-based SSI architecture and protocols will
enable service providers to create programs that request only
they need to verify; it encourages their users to contact themwithout hesitating to disclose unnecessary information. More
importantly, people on the planet will gain Self-Sovereign
Identity, consisting of the ten principles including existence
and control.
My Number Individual Card and JPKI: An ongoing initiative, driven by the Japanese government, is to enable
JPKI, a part of My Number Individual Card capabilities, on
smartphones. In order to realize a goal to duplicate digital certificates with key pairs, the initiative plans to utilize
Global Platform-supported Secure Elements. The goals of
the initiative and ideas of Self-Sovereign Identity are not
identical; however, there are many analogies between those.
For example, a mobile device may become a digital identity for
16 https://www.aamva.org/Mobile-Drivers-License/

情報セキュリティ総合科学第14号2023年2月

the user once the registration process is completed. Duplicatedcertificates and key pairs are securely stored in the device, andit may work for their identity proofing or verifying claims.
The result of JPKI can also be used to create a Sybil-resistantcredential. Future extensions of real-world identity-related
initiatives toward Self-Sovereign Identity are very expected.
B. Limitations and Future Directions
We have focused on utilizing the abstraction of Attested
Execution Secure Processors (AESPs) together with permissionless blockchain in order to build a secure SSI systemthrough defining the architecture and the system protocols,
ΠGatt . In this section, we would like to describe three problems
that are remaining and will address to solve as our future
works.
1) Addressing Complexity in the Real World: We propose
to incorporate Rafael Pass et al.’s contribution regarding theformal abstraction of Attested Execution Secure Processors(AESPs) [16] to build an SSI system. Also, we have demonstrated our ideas of protocols, security properties, and a
proof sketch of the security properties in an informal fashion;
however, we made some assumptions for brevity, such as asingle system of Sybil-resistant credentials. Further researchis expected to address more complexity existing in the realworld.
2) Potential Vulnerability of Hardware-Assisted Security:
Some readers might be concerned about the vulnerability
residing tamper-resistant secure processors to compromise.
We plan to address defining a treat model to cover such
vulnerability. One of those is the globally shared key pairof pkM and skM , which is possibly an obvious target forcompromise; however, we believe that previous research addressing anonymous attestation may resolve the concern. Ernie
Brickell et al. proposed direct anonymous attestation to address
the problem [34], firstly adopted onto TPM. Further, Christina
Garman et al.’s contributions proposed decentralized direct
anonymous attestation [35].
3) Practice: We have not addressed in detail how to utilize
permissionless blockchain in aligning with the proposed architecture and the system protocols ΠGatt in this paper. Someexisting SSI systems are already deployed utilizing permissionless blockchain, and we plan to design a prototype of
the proposed architecture based on the existing permissionless
blockchain systems [11] [12] [13] such as Ethereum 2.017 .
The further detailed design includes a.) interface between
issuers/verifiers and permissionless blockchain for a natural
person who owns a mobile device equipped with an AESP tocontrol their credentials, b.) Interface for such a natural person
to access programs that can and should be maintained on thepermissionless blockchain, and c.) some applications, such asa scenario where a natural person purchases something with
their wallet on the permissionless blockchain only when a shop
there may verify if the person’s age is over 18 years old, butother private information is not disclosed.
17 https://ethereum.org/en/eth2/

IX. C ONCLUSION
We have demonstrated the powerfulness of hardwareassisted security and the formal abstraction of Attested
Execution Secure Processors (AESPs) over permissionless
blockchain technology. Based on those techniques, we proposed the AESP-based secure Self-Sovereign Identity (SSI)
architecture and system protocols ΠGatt along with security
properties including Sybil-resistance and a proof sketch of the
security properties.
Assuming AESPs and Gatt , the AESP-based SSI systemprotocols ΠGatt eliminates the online distributed committee oftrusted nodes assumed in CanDID; thus, ΠGatt allows not torely on multi-party computation (MPC), and it brings drastic
flexibility and efficiency when compared with the existing
systems. In addition, we described applications, limitations,and our future directions in this work.
ACKNOWLEDGMENT
The authors thank all researchers and contributors for digital
identity and mobile. Also, we very much appreciate all anonymous reviewers’ feedback to improve a draft of this paper; wehave been very encouraged by their comments.
R EFERENCES[1] C. Allen, “The Path to Self-Sovereign Identity,” Apr.
2016. [Online]. Available: http://www.lifewithalacrity.com/2016/04/
the-path-to-self-soverereign-identity.html[2] P. Dunphy and F. A. P. Petitcolas, “A First Look at Identity Management
Schemes on the Blockchain,” IEEE Security & Privacy, vol. 16, no. 4,
pp. 20–29, Jan. 2018.
[3] N. Naik and P. Jenkins, “Self-Sovereign Identity Specifications: GovernYour Identity Through Your Digital Wallet using Blockchain Technology,” 2020 8th IEEE International Conference on Mobile Cloud
Computing, Services, and Engineering (MobileCloud), pp. 90–95, Aug.
2020.
[4] M. S. Ferdous, F. Chowdhury, and M. O. Alassafi, “In Search of SelfSovereign Identity Leveraging Blockchain Technology,” IEEE Access,vol. 7, pp. 103 059–103 079, Aug. 2019.
[5] G. Kondova and J. Erbguth, “Self-sovereign identity on publicblockchains and the GDPR,” Proceedings of the 35th Annual ACM
Symposium on Applied Computing, Mar. 2020.
[6] C. Gomez Munoz, “eIDAS Supported Self-Sovereign Identity,” Tech.
Rep., May 2019. [Online]. Available: https://ec.europa.eu/futurium/en/
system/files/ged/eidas supported ssi may 2019 0.pdf[7] D. Chaum, “Security Without Identification: Transaction Systems to
Make Big Brother Obsolete,” Communications of the ACM, vol. 28,
no. 10, pp. 1030–1044, 1985.
[8] A. Mühle, A. Grüner, T. Gayvoronskaya, and C. Meinel, “A Survey
on Essential Components of a Self-Sovereign Identity,” ArXiv, vol.
abs/1807.06346, Jul. 2018.
[9] Q. Stokkink and J. Pouwelse, “Deployment of a Blockchain-Based SelfSovereign Identity,” in 2018 IEEE International Conference on Internetof Things (iThings) and IEEE Green Computing and Communications(GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData), Jun. 2018, pp. 1336–1342.
[10] D. van Bokkem, R. Hageman, G. Koning, L. Nguyen, and N. Zarin,“Self-Sovereign Identity Solutions: The Necessity of Blockchain Technology,” ArXiv, vol. abs/1904.12816, Apr. 2019.
[11] N. Naik and P. Jenkins, “uPort Open-Source Identity Management System: An Assessment of Self-Sovereign Identity and User-Centric Data
Platform Built on Blockchain,” in 2020 IEEE International Symposium
on Systems Engineering (ISSE), Nov. 2020, pp. 1–7.
[12] S. Nakamoto, “Bitcoin : A Peer-to-Peer Electronic Cash System,” 2008.
[13] P. J. Windley, “Sovrin: An Identity Metasystem for Self-Sovereign
Identity,” Frontiers in Blockchain, vol. 4, Jul. 2021. [Online]. Available:
https://www.frontiersin.org/articles/10.3389/fbloc.2021.626726/full

情報セキュリティ総合科学第14号2023年2月[14] V. Costan, I. Lebedev, and S. Devadas, “Sanctum: Minimal Hardware
Extensions for Strong Software Isolation,” in 25th USENIX Security
Symposium (USENIX Security ’16), Aug. 2016, pp. 857–874.
[15] E. Shi, F. Zhang, R. Pass, S. Devadas, D. Song, and C. Liu,
“Trusted Hardware: Life, the Composable Universe, and Everything(2015 12 15 4 Elaine Shi, et el.),” May 2017. [Online]. Available:
https://www.youtube.com/watch?v=57KnieAVFkY[16] R. Pass, E. Shi, and F. Tramèr, “Formal Abstractions for Attested Execution Secure Processors,” in Advances in Cryptology – EUROCRYPT
2017, vol. LNCS, volume 10210, Apr. 2017, pp. 260–289.
[17] D. Maram, H. Malvai, F. Zhang, N. Jean-Louis, A. Frolov, T. Kell,
T. Lobban, C. Moy, A. Juels, and A. Miller, “CanDID: Can-Do Decentralized Identity with Legacy Compatibility, Sybil-Resistance, andAccountability,” in 2021 IEEE Symposium on Security and Privacy (SP),May 2021, pp. 1348–1366.
[18] K.
Cameron,
“The
Laws
of
Identity,”
May
2005.
[Online]. Available: https://www.identityblog.com/stories/2005/05/13/
TheLawsOfIdentity.pdf[19] ISO/IEC, “ISO/IEC 24760-1:2019(en), IT Security and Privacy —A framework for identity management — Part 1: Terminology andconcepts,” 2019. [Online]. Available: https://www.iso.org/obp/ui/#iso:
std:iso-iec:24760:-1:ed-2:v1:en[20] P. A. Grassi, M. E. Garcia, and J. L. Fenton, “NIST Special Publication
800-63-3 Digital Identity Guidelines,” Jun. 2017. [Online]. Available:
https://pages.nist.gov/800-63-3/[21] M. S. Ferdous, G. Norman, A. Jøsang, and R. Poet, “Mathematical Modelling of Trust Issues in Federated Identity Management,” in IFIPTM
2015: Trust Management IX, Apr. 2015, pp. 13–29.
[22] W3C, “Decentralized Identifiers (DIDs) v1.0,” Aug. 2021. [Online].
Available: https://www.w3.org/TR/did-core/[23] P. Dunphy, L. Garratt, and F. Petitcolas, “Decentralizing Digital Identity:
Open Challenges for Distributed Ledgers,” 2018 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW), pp. 75–78,
Apr. 2018.
[24] K. C. Torh and A. Anderson-Priddy, “Self-Sovereign Digital Identity:
A Paradigm Shift for Identity,” IEEE Security & Privacy, vol. 17, pp.
17–27, May 2019.
[25] A. Satybaldy, M. Nowostawski, and J. Ellingsen, “Self-Sovereign Identity Systems: Evaluation Framework,” in Privacy and Identity Management. Data for Better Living: AI and Privacy, M. Friedewald, M. Önen,
E. Lievens, S. Krenn, and S. Fricker, Eds. Cham: Springer International
Publishing, Mar. 2020, vol. 576, pp. 447–461.
[26] Y. Liu, Q. Lu, H. Paik, and X. Xu, “Design Patterns for Blockchainbased Self-Sovereign Identity,” Proceedings of the European Conference
on Pattern Languages of Programs 2020, May 2020.
[27] A. Grüner, A. Mühle, and C. Meinel, “On the Relevance of Blockchain
in Identity Management,” arXiv:1807.08136 [cs], Jul. 2018, arXiv:
1807.08136. [Online]. Available: http://arxiv.org/abs/1807.08136[28] A.-E. Panait, R. F. Olimid, and A. Stefanescu, “Analysis of uPort Open,an Identity Management Blockchain-Based Solution,” in TrustBus, Sep.
2020.
[29] S. Mahula, E. Tan, and J. Crompvoets, “With blockchain or not?
Opportunities and challenges of self-sovereign identity implementationin public administration: Lessons from the Belgian case,” DG.O2021:
The 22nd Annual International Conference on Digital Government
Research, pp. 495–504, Jun. 2021.
[30] D. Du Seuil, “European Self Sovereign identity framework,”
Jul. 2019, https://ssimeetup.org/understanding-european-self-sovereignidentity-framework-essif-daniel-du-seuil-carlos-pastor-webinar-32/.
[31] A. Boysen, “Decentralized, Self-Sovereign, Consortium: The Future of
Digital Identity in Canada,” in Frontiers in Blockchain, 2021.
[32] W3C, “Verifiable Credentials Data Model 1.1,” Mar. 2022. [Online].
Available: https://www.w3.org/TR/vc-data-model/[33] N. Santos, H. Raj, S. Saroiu, and A. Wolman, “Using ARM trustzone tobuild a trusted language runtime for mobile applications,” in Proceedings of the 19th international conference on Architectural support for
programming languages and operating systems. Salt Lake City Utah
USA: ACM, Feb. 2014, pp. 67–80.
[34] E. Brickell, J. Camenisch, and L. Chen, “Direct anonymous attestation,”in Proceedings of the 11th ACM conference on Computer and communications security - CCS ’04. Washington DC, USA: ACM Press, 2004,
pp. 132–145.
[35] C. Garman, M. Green, and I. Miers, “Decentralized Anonymous Credentials,” IACR Cryptol. ePrint Arch., vol. 2013, Oct. 2013.