I2PA: An Efficient ABC for IoT

Abstract

The Internet of Things (IoT) is very attractive because of its promises. However, it brings many challenges, mainly issues about privacy preservation and lightweight cryptography. Many schemes have been designed so far but none of them simultaneously takes into account these aspects. In this paper, we propose an efficient attribute-based credential scheme for IoT devices. We use elliptic curve cryptography without pairing, blind signing, and zero-knowledge proof. Our scheme supports block signing, selective disclosure, and randomization. It provides data minimization and transaction unlinkability. Our construction is efficient since smaller key size can be used, and computing time can be reduced. As a result, it is a suitable solution for IoT devices characterized by three major constraints, namely low-energy power, small storage capacity, and low computing power.

1. Introduction

The Internet has changed our way of living. In fact, it has become an integral part of our life. As a ubiquitous communication platform, it has undergone remarkable development in recent years. The concept of the Internet of Things (IoT) has emerged, and envisages the integration of all real-world objects into the Internet. The evolution of the IoT concept has given rise to other concepts such as IoE (Internet of Everything) or IoV(Internet of Vulnerabilities). Some people even talk about IoP [1] (Internet of People). According to Cisco forecasts [2], there will be 50 billion connected devices by 2020.

In most cases, communications between devices require authentication itself based on authentication factors [3]. Authentication is also based on identification, which makes activities of an entity traceable since each device is directly or indirectly associated with its owner. The current infrastructure is based on centralized architecture, which allows no control of data by their owners; this is a threat to privacy preservation. Security in current infrastructures is guaranteed in most cases by Public Key Infrastructures(PKIs) that can guarantee that messages are not compromised, and only recipients are able to open and read them (integrity, confidentiality, and authenticity are guaranteed). PKIs’ main objective is to guarantee key encryption authenticity. However, they cannot protect users’ privacy and users cannot get a credential on a subset of their attributes without letting the certification authority (CA) see the resulting credential. Moreover, when authenticating to a service provider, users must show their whole credentials instead of just proving their eligibility for that access. We must therefore think to migrate to decentralized and user-centric architecture.

The ultimate challenge can be summarized in this fundamental question: How is it possible to minimize data disclosed about oneself and provide only the bare minimum necessary? Presently, to the best of our knowledge, the most convenient way to protect users’ privacy remains using Anonymous Credentials systems also known as Attribute-Based Credentials (ABCs). ABCs are building blocks for user-centric identity management [4]. With ABCs, it is possible to get a signature on a set of attributes and then use this later to access other services. Seeing the abstractness of some attributes (nationality, age class, occupation, affiliation, profession, etc.), the entire mechanism can remain anonymous and therefore guarantees the privacy of concerned entities. Authentication is carried out by revealing the bare minimum necessary. Better, it is possible, for a set of attributes, to prove their possession instead of revealing their values, from where derives the concept I2PA, meaning “I Prove Possession of Attributes” .

In terms of anonymous credentials, there are two flagship schemes—Idemix of IBM [5] and U-prove of Microsoft [6]. There are many other contributions [7,8,9,10,11,12]; however, as discussed in Section 2, when tackling privacy concerns, none of those schemes is fully adapted in an IoT environment characterized by three major constraints, namely low computing power, very limited storage capacity, and low energy autonomy.

The relevance of our contribution lies in the fact that it offers a good level of security and drastically reduces key size. Credential randomization, selective disclosure, and unlinkability features are very interesting results that contribute in guaranteeing non-traceability. Edwards curves, known as the curves in which cryptographic calculations are faster [13], are privileged. We then win in memory usage, performance in computing time, and bandwidth usage. Analysis presented in Section 7 and performance evaluation conducted in Section 8 show that our scheme is very efficient. Its level of abstractness makes it applicable in any IoT environment.

The rest of this paper is organized as follows. We start by discussing related works in Section 2, review mathematic backgrounds in Section 3, while definitions of some leading concepts are presented in Section 4. Section 5 presents an architecture of ABC systems and in Section 6, our contribution is presented. Section 7 is related to complexity analysis and performance evaluation is presented in Section 8. This paper is ended by a conclusion and perspectives in Section 9.

2. Related Works

Credentials are essential in identity-management systems. They attest that an entity has a certain knowledge, skill, characteristic, etc. [14]. ABCs involve attributes of an entity without including identity information, which allows linking the credential to its owner [14,15,16]. They allow a user to prove properties about herself anonymously [11,15,17]. Even when attributes are hidden, the verifier can still assess the validity of the credential [15]. There are two major families of ABC systems, namely those based on blind signatures (BS) and those based on zero-knowledge proofs (ZKP). In terms of anonymous credential, there are two leading schemes—Idemix of IBM [5] and U-prove of Microsoft [6]. While Idemix’s building block [5] is based on Camenish—Lysyanskaya signature scheme [18] (CL-Signature), U-prove is based on Stefan Brand’s digital signature [19] instead. There are many other contributions including IRMA of Radboud University of Nijmegen [12] (based on Idemix). However, when tackling privacy concerns, none of those schemes is fully adapted in an IoT environment characterized by three major constraints, namely low computing power, very limited storage capacity, and low energy autonomy. In fact, these models are based either on RSA cryptosystems [7] or on pairing-based cryptography [20]. Some of them are based on elliptic curve cryptography (ECC) without pairing (U-prove, for instance) but do not fully take into account some fundamental features relative to privacy preserving. Indeed, the unlinkability feature is not fully taken into account by U-prove, and can only be achieved by using different credentials [16,21,22]. With reference to RSA-based cryptosystems, the major problem remains key size, which will necessarily give rise to problems of storage, performance in computing time, and bandwidth usage. Pairing-based cryptosystems, although considered to be very robust, are not applicable in an IoT context given that they are too greedy in terms of computing time. The relative computation cost of a pairing is approximately 20 times higher than that of the scalar multiplication. The model presented by Gergely et al. [8] is very efficient in a sensor network but does not guarantee anonymity since the verifier has a database of identifiers. Persiano et al. [11] proposed a scheme for multi-show non-transferable credentials. However, authors in [16] shown that this scheme does not support advanced issuance or carry-over attributes, and de-anonymization is partially supported. De Fuentes et al. [14] conducted an assessment of ABCs in smart cities context considering Idemix, U-Prove, and VANET-updated Persiano systems. Their experimental results show that Idemix is the most promising approach both in terms of performance and the set of smart city road traffic services that could adopt it. Dzurenda et al. [23] proposed ecHM12, a new ABC scheme based on EC and HM12 [24] scheme. They assert that their scheme meets all standard requirements on ABC schemes. However, they do not deal with credentials with more than three attributes and the time of their verification protocol depends on the number of revoked users in the system. They also claim that their solution has good impact on bandwidth whereas 12 variables are exchanged between the user and the verifier in the proving protocol. Furthermore, their proving protocol is very greedy in terms of computing time; 19 scalar multiplications and eight additions of points are carried out over the curve. Their revocation process also requires linear time in the number of users. They assume that current servers have high computing power to guarantee usability of their scheme. As a result, this scheme may not be applicable in a system with lots of users and where devices have low computing power. Even if Idemix is the most advanced in terms of implementation, it is subject to improvement given the key size required. Sinha et al. [9] show that at equal security level, an RSA key is at least six times longer than an ECC key. Furthermore, in most cases, operations are faster on ECC than in RSA cryptosystem. Another important point is that in an RSA cryptosystem, when key size is no longer enough to guarantee a secure level, it is recommended to double it, which is not necessarily the case for ECC cryptosystem. Another important contribution [10] is built on top of Idemix. It has been successfully implemented, deployed, and tested. However, criticisms of Idemix remain valid toward it. U-prove, by its generality, can be implemented either based on subgroup or using ECC. However, as mentioned earlier, the unlinkability feature requires additional storage space.

3. Mathematic Background

ECC was presented independently by Koblitz [25] and Miller [26] in the 1980s. Their structure of group and performance in computing time make them a new direction in cryptography [27,28]. ECC has been proven to be one of the best public key cryptosystem (PKC) alternatives for constrained applications [29,30,31]. The following section is a brief description of ECC.

3.1. Definition

An elliptic curve $\mathbf{E}$ over a field $\mathbb{K}$ can be described as a set of $\mathbb{K}\times \mathbb{K}$ satisfying the equation:

$$\mathbf{E}:y^2+a_{1}xy+a_{3}y=x^3+a_2{x}^2+a_{4}x+a_6$$

(1)

where $a_i\in \mathbb{K}$ to which we add a point at infinity $\mathcal{O}$, defined as the intersection of all vertical lines. An additional requirement is that the curve must be “smooth” [3,32]. Depending on the characteristic of $\mathbb{K}$, the equation below can be simplified [3,32]:

• When $char(\mathbb{K})\ne 2,3$ the equation can be simplified to $y^2=x^3+ax+b$, where a, b $\in \mathbb{K}$.
• When $char(\mathbb{K})=2$ and $a_1\ne 0$, the equation can be simplified to $y^2+xy=x^3+a{x}^2+b$, where a, b $\in \mathbb{K}$. This curve is said to be non-supersingular. If $a_1=0$, the equation can be simplified to $y^2+cy=x^3+ax+b$, where a, b, c $\in \mathbb{K}$. This curve is said to be supersingular.
• When $char(\mathbb{K})=3$ and $a_1^2\ne -a_2$ the equation can be simplified to $y^2=x^3+a{x}^2+b$, where a, b $\in \mathbb{K}$. This curve is said to be non-supersingular. If $a_1^2=-a_2$, the equation can be simplified to $y^2=x^3+ax+b,a,b\in \mathbb{K}$. This curve is said to be supersingular.

The “Figure 1” is an illustration of the curve $y^2=x^3-x$ over $\mathbb{R}$.

Theorem 1 (Hasse’s theorem).

Let E be an elliptic curve defined over a finite field $\mathbb{K}$ with q elements, then the result of Hasse states that: $|\#E(\mathbb{K})-q-1|\le 2\sqrt{q}$.

3.2. Edwards’ Curves

Edwards, generalizing an example from Euler and Gauss, introduced an addition law for the curves $x^2+y^2=c^2(1+x^2{y}^2)$ over a non-binary field $\mathbb{K}$. He showed that every elliptic curve over a non-binary field $\mathbb{K}$ can be expressed in the form $x^2+y^2=c^2(1+x^2{y}^2)$ if $\mathbb{K}$ is algebraically closed. Bernstein and Lange [33] generalized the addition law of the curves $x^2+y^2=c^2(1+d{x}^2{y}^2)$. Let $char(\mathbb{K})\ne 2,3$ and let $E(\mathbb{K})$ has a unique point of order 2. Then, E can be written in Edwards form [33,34,35]:

$$E_d:x^2+y^2=1+d{x}^2{y}^2,whered\notin \{0,1\}$$

(2)

Let $P_1(x_1,y_1)$, $P_2(x_2,y_2)$, and $P_3(x_3,y_3)$ be points of the curve such that $P_3=P_1⨁P_2$. The Edwards addition law over $E_d$ is described as follow:

$$(x_3,y_3)=\left(\frac{x_1{y}_2+x_2{y}_1}{1+d{x}_1{x}_2{y}_1{y}_2},\frac{y_1{y}_2-x_1{x}_2}{1-d{x}_1{x}_2{y}_1{y}_2}\right)$$

(3)

This group law is complete, strongly uniform and presents interesting results:

• If d is a non-square in $\mathbb{K}$, the addition law is complete. This ensures that denominators are never zero.
• The addition law is strongly unified, i.e., it can also be used for doubling.
• The point (0,1) is the neutral element.
• The point (0,−1) has order 2.
• The points (±1,0) have order 4.
• The inverse of $(x,y)$ is $(-x,y)$.

In addition, Edwards curve is known to be the fastest among all families of elliptic curves used to implement cryptography.

3.3. Elliptic Curve Discrete Logarithm Problem (ECDLP)

The basic operations of ECC are point scalar computations (also known as scalar multiplication) of the form:

$$Q=k.P=\underset{\mathrm{k}\mathrm{times}}{\underbrace{P+P+\dots +P}}$$

The ECDLP is the problem of retrieving k given P and Q, where P and Q are points of the curve and k is an integer uniformly chosen at random from [1, r−1] (r denotes the order of P). The assumed difficulty of this problem is the basis of security in elliptic curve public key cryptosystems. Point scalar multiplication can be performed efficiently using algorithms such as double-and-add.

4. Definition

The aim of this section is to define some leading terms in this paper, namely attribute, credential, blind signing, and zero-knowledge proof.

4.1. Attribute

An attribute is a characteristic or a qualification of a person. It can either be an identifying or non-identifying property. For example, “full name”, “address”, and “social security number” are identifying attributes. Attributes such as “is a student” and “is a teenager” are non-identifying as they do not uniquely identify a person; such properties can belong to other people as well.

4.2. Credential

A credential is a set of attributes digitally signed by a trusted third party (issuer), i.e., a set of attributes together with the corresponding cryptographic information. A credential is similar to a certificate in terms of content, but they are different in the way they are used. While certificate usage requires showing all its content, a credential can be used by showing some parts and hiding or proving knowledge of others. Credentials are important in identity-management systems. They certify that an entity has certain characteristics, knowledges, skills, etc. One main point is that credentials involve attributes of an entity without including identity information, which allows linking of the credential to its owner. As illustrated in the “Figure 2”, a credential has three main parts: a secret key of its owner, a set of attributes, and a signature of an issuer on that set. A credential includes more information such as expiry date.

4.3. Zero-Knowledge Proofs

Recent decades have witnessed the emergence of several new cryptographic notions. In 1985, Goldwasser, Micali and Rackoff [36] introduced the concept of zero-knowledge interactive proofs that enables an entity, a prover, to convince another entity, a verifier, of the validity of a statement without revealing anything else beyond the assertion of this statement. Zero-knowledge proofs are elegant techniques to limit the amount of information transferred from a prover to a verifier in a cryptographic protocol. The “

Table 1. Schnorr’s proof of knowledge.

” describes Schnorr’s proof of knowledge also known as Schnorr’s Identification protocol. Given a group G of prime order q, in which the discrete logarithm problem (DLP) is hard, and a generator g ($\langle g\rangle =G$), a prover proves to a verifier that he knows a secret value x, uniformly chosen at random from ${\mathbb{Z}}_q^{*}$, corresponding to a public value $h=g^x\in G$.

There is a formal symbolic notation of ZKP as described below:

$$PK\{(\alpha ):h=g^{\alpha }\}$$

4.4. Blind Signing

In many applications involving anonymity, it is often desirable to allow a participant to sign a document without knowing its content; this is known as blind signature. It is typically used in privacy-related protocols where the signer and credential owner are different parties. It can be used in e-cash or a privacy vote.

4.5. Blindness

Let $U_0$ and $U_1$ be two honest users and A be a Probabilistic Polynomial-Time (PPT) adversary which plays the role of the signer engaged in the issuing scheme with $U_0$ and $U_1$ on messages $m_b$ and $m_{1-b}$ where b is chosen uniformly at random from $\{0,1\}$. $U_0$ and $U_1$ output the signatures ${\sigma }_b$ and ${\sigma }_{1-b}$. After that, $(m_b,m_{1-b},{\sigma }_b,{\sigma }_{1-b})$ is sent to A which outputs $b^{\prime }\in \{0,1\}$. For all A, $U_0$, $U_1$, constant c, large n, we have $\mathrm{Pr}[b=b^{\prime }]<n^{-c}$.

5. Architecture

A general architecture of privacy-ABC consists of three main entities—a user (credential owner also known as prover), an issuer (trusted third party or credential signer), and a verifier (services provider or secure resource owner). The issuer issues credentials for users, which can later be used for authentication purposes. Such an architecture may optionally include an entity that takes care of revocation of credentials (revocation authority) and another entity (inspector) that can revoke the anonymity of users. Inspection and revocation are beyond the scope of this paper. Different entities and their relations are illustrated in Figure 3.

The main phases of a privacy-ABC system are described below:

• Set-up: Performed to output system’s parameters.
• Issuance: An interactive protocol between users and issuer. By issuing a credential to a user, the issuer guarantees the correctness of attributes contained in the credential.
• Presentation: An interactive protocol in which a user reveals or proves to a verifier possession of some attributes or claims about attributes. This phase is also known as verification.
• Inspection: Provides conditional anonymity. It enables a trusted party, the so-called inspector, to revoke, in some conditions, anonymity of cheating provers.
• Revocation: Ends the validity of credentials whenever necessary.

At the core of privacy-ABC system, untraceability and unlinkability are the most important privacy-related features. Additional features are also supported [11,16,21,37]; without exhaustivity, we cite:

• Authenticity: feature that guarantees that an ABC cannot be modified.
• Non-transferability: feature that prevents the user from transferring her ABC to another user.
• Minimal information: feature that guarantees that during the verification protocols no other information is revealed to the verifier beyond the disclosed attributes, and the corresponding issuer, etc.
• Multi-show unlinkability: feature that guarantees that different presentations of a given ABC cannot be linked.
• Issuance unlinkability: feature which guarantees that the presentation of an ABC cannot be linked to its issuance.
• Selective disclosure: Allows a user to prove only a subset of attributes to a verifier.
• Carry-over attributes: Enables users to carry over some attributes from an existing ABC into a new one without disclosing them to the issuer.
• Predicate proof: Allows logical operators to be applied on attributes without disclosing them.
• Proof of holdership: A cryptographic evidence for proving ownership of ABC.
• Unforgeability: feature that guarantees that no malicious third party can forge a valid ABC.
• Etc.

6. Contribution

In this section, our scheme is described. We focus on three main phases, namely set-up, issuance, and verification (showing, presentation). We also present a selective disclosure protocol and randomization of credential.

6.1. Set-Up

The set-up is the first algorithm to be run to extract system’s parameters from a security parameter k. This algorithm is described as follows:

• $\{p,q,E({\mathbb{F}}_p),P,P_{pub},\mathcal{H}\}⟵1^k$

where:

• k: a security parameter.
• p: a prime number that defines the field ${\mathbb{F}}_p$.
• E: an elliptic curve defined over ${\mathbb{F}}_p$.
• $P\in E({\mathbb{F}}_p)$: a base point of prime order q.
• $x{\in }_R{\mathbb{F}}_q^{*}$: issuer’s secret key.
• $P_{pub}=x.P$: issuer’s public key.
• $\mathcal{H}$: a hash function defined as follow:

  $$\begin{array}{cc}\hfill \mathcal{H}:& E{({\mathbb{F}}_p)}^2\stackrel{}{\to }{\mathbb{F}}_p^{*}\hfill \\ & (P,Q)\stackrel{\phantom{L^{\infty }(T)}}{\mapsto }\mathcal{H}(P,Q)\hfill \end{array}$$

6.2. Issuance

Once the set-up algorithm is successfully executed, the issuer is ready to issue credentials. When a user wants to be issued a credential, he runs an interactive algorithm with the issuer at the end of which a credential should be issued for him. Issuance unlinkability property should be ensured. The way it is done is that not only the issuer can not store the issued credential, but also, thanks to the blinding mechanism, he may not see the credential’s content while issuing.

6.3. Signature on a Single Message

The issuing protocol on a single message is an interactive protocol of three steps as described below:

• Blinding: The issuer generates a random integer $\overline{k}\in {\mathbb{F}}_q^{*}$, computes the resulting point $\overline{R}=\overline{k}.P$ and sends it to the user. The latter generates random factors $\alpha$ and $\beta$, blinds her document, and sends it to the issuer.
• Singing: The issuer signs the blinded document with his secret key x by computing $\overline{s}\equiv \overline{h}x+\overline{k}(modq)$ and sends the blinded and signed document to the user.
• Unblinding: The user unblinds the blinded and signed document with her blind factors $\alpha$ and $\beta$ without invalidating it.

For convenient notation, proofs of knowledge would be noted $PK$. The corresponding proofs are those mentioned in the so-called protocol. Details of the issuing protocol on a single message are described in “

Table 2. Issuance protocol on a single message.

”.

Theorem 2.

The proposed scheme is fully blind.

Proof. 

From $\overline{s}\equiv \overline{h}x+\overline{k}(\mathrm{mod}q)$, we have $\alpha \equiv hx{(\overline{s}-\overline{k})}^{-1}(\mathrm{mod}q)$. Thus, $\alpha \in {\mathbb{F}}_q^{*}$ is unique. It follows that $\beta \equiv s-\alpha \overline{s}(\mathrm{mod}q)$ is also unique. Thus, there always exist α and β, regardless of $(\overline{R},\overline{h},\overline{s})$ and $(m,R,s)$, such that $(\overline{R},\overline{h},\overline{s})$ and $(m,R,s)$ have the same relation. Therefore, an adversary A outputs a correct value $b^{\prime }$ with probability exactly $\frac{1}{2}$. As a result, the issuing protocol is fully blind. □

Theorem 3.

The proposed scheme is $({ϵ}^{\prime },t^{\prime },q_i,q_h)$-secure in the sense of unforgeability under chosen message attack (UE-CMA) in the random oracle model, assuming that the $(ϵ,t)$-ECDL assumption holds in $\langle P\rangle$, where $t^{\prime }=t+\mathcal{O}(q_i)T$, ${ϵ}^{\prime }=(1-\frac{q_h{q}_i}{q})(1-\frac{1}{q})(\frac{1}{q_h})ϵ$ and $q_i,q_h$ are the number of issue and hashing queries, respectively, the adversary is allowed to perform, while T denotes the time for a scalar multiplication operation.

Proof. 

Assuming that there exists a forger $\mathcal{A}$ that can forge a credential while playing the game of chosen message attack (CMA) [38], we construct an algorithm ${\mathcal{M}}^{\mathcal{A}}$ that uses $\mathcal{A}$ to solve the discrete logarithm problem. Without losing generality, we assume that $q_i{q}_h<q$. The following section is adapted from the proof presented by Joseph K Lui et al. [39].

• Set-up: ${\mathcal{M}}^{\mathcal{A}}$ receives the problem $P_1:(k,p,q,E({\mathbb{F}}_p),P,P_{sec})$ and should find $z\in {\mathbb{F}}_p$ such that $P_{sec}=z.P$. It chooses a hash function $\mathcal{H}$ which behaves like a random oracle, sets $P_{pub}=P_{sec}$ and sends the public parameters $(k,p,q,E({\mathbb{F}}_p),P,P_{pub},\mathcal{H})$ to $\mathcal{A}$ expecting it forges a credential. ${\mathcal{M}}^{\mathcal{A}}$ and $\mathcal{A}$ start playing the game of chosen message attack [38].
• Hashing oracle: ${\mathcal{M}}^{\mathcal{A}}$ starts by initializing an empty database. When $\mathcal{A}$ sends $m_i$ for hashing, ${\mathcal{M}}^{\mathcal{A}}$ checks whether or not that message has already been sent. If so, it picks $h_i$ from the database and returns it as a response to that query, otherwise it picks $h_i{\in }_R{\mathbb{F}}_p^{*}$ , stores the couple $(m_i,h_i)$ in the database and returns $h_i$ as a response to that query.
• Issuing oracle: When $\mathcal{A}$ queries the issuing oracle for the message $m_i$, ${\mathcal{M}}^{\mathcal{A}}$ first checks whether $m_i$ has already been queried for issuance. If so, it aborts and the game is stopped (Event 1) [38], otherwise, it computes $h_i=RO(m_i)$ (where $RO$ denotes the hashing oracle), picks $s_i{\in }_R{\mathbb{F}}_p^{*}$, computes $R_i=s_i.P-h_i.P_{pub}$ and sends $(R_i,s_i)$ to $\mathcal{A}$ as response to its issuing query. As we can see, the algorithm is valid since $s_i.P=h_i.P_{pub}+R_i$.
• Forging step: Finally, $\mathcal{A}$ outputs a forged signature ${\sigma }^{*}=(s^{*},R^{*})$ on message $m^{*}$ with $h^{*}$. It computes $\frac{s^{*}-r^{*}}{h^{*}}$ and extracts z as solution of the DLP.
• Probability analysis: The simulation fails if $\mathcal{A}$ queries the same message for issuance (Event 1). This happens with probability at most $\frac{q_h}{q}$. Hence, the simulation is successful with probability at least ${(1-\frac{q_h}{q})}^{q_i}\ge (1-\frac{q_h{q}_i}{q})$ (provable by recurrence reasoning). The tuple $(m^{*},R^{*},s^{*})$ is a valid credential with probability at least $1-\frac{1}{q}$ [39] and ${\mathcal{M}}^{\mathcal{A}}$ guesses it correctly with probability at least $\frac{1}{q_h}$ [39]. Finally, the overall successful probability is ${ϵ}^{\prime }=(1-\frac{q_h{q}_i}{q})(1-\frac{1}{q})(\frac{1}{q_h})ϵ$ [39]. The time complexity of the algorithm ${\mathcal{M}}^{\mathcal{A}}$ is $t^{\prime }=t+\mathcal{O}(q_i)T$ since the issuing oracle computes at most $2q_{i}T$ scalar multiplications.

□

6.4. Verification

Once the credential is issued, the user can be authenticated by a service provider. As for the issuing protocol, he performs an interactive protocol with the service provider at the end of which an access to the so-called service might be granted or denied. The user must prove knowledge of his secret key. This guarantees unforgeability property. The verification protocol is described in “

Table 3. Verification protocol.

Prover	Public	Verifier
Secret ${\mathit{m}}_{\mathbf{0}}$	$\mathit{k},\mathit{p},\mathit{q},\mathit{P},{\mathit{P}}_{\mathit{pub}},\mathit{E},\mathcal{H}$
Keeps secret $(\overline{R},\overline{s})$
$PK\{(\mu ):P_0=\mu .P\}$	$\stackrel{(R,s),h,PK}{\stackrel{}{\to }}$	$s.P\stackrel{?}{=}h.P_{pub}+R$

”.

6.5. Randomized Version

Many digital services involved in our life emphasize users’ privacy. Blind signature is a well-known technique to address privacy concerns. When a user presents the same signature $(R,s)$ multiple times, he could be traceable; R, s could be stored by the verifier even if this cannot be linked to issuance. The randomized version allows a user to derive a random signature from a valid one without invalidating it. The randomization feature is fundamental because it guarantees multi-show unlinkability. The prover generates a random factor r from which a random signature $(\widehat{R},\widehat{s})$ is derived. The process of randomization is described in “

Table 4. Randomization protocol.

Prover	Public	Verifier
Secret ${\mathit{m}}_{\mathbf{0}}$	$\mathit{k},\mathit{p},\mathit{q},\mathit{P},{\mathit{P}}_{\mathit{pub}},\mathit{E},\mathcal{H}$
$r{\in }_R{\mathbb{F}}_q^{*}$
$\widehat{s}\equiv s+r(modq)$
$\widehat{R}=R+r.P$	$\stackrel{(\widehat{R},\widehat{s}),h,PK}{\stackrel{}{\to }}$	$\widehat{s}.P\stackrel{?}{=}h.P_{pub}+\widehat{R}$

”.

6.6. Signature on a Block of Messages

A credential rarely contains one attribute. In this section, we consider a credential of l attributes $(m_1,\dots ,m_l)$. The issuing protocol on a block of messages is described in “

Table 5. Issuance protocol on a block of messages.

”. The verification protocol remains the same as in Section 6.4.

6.7. Selective Disclosure

The fundamental principle of privacy master is data minimization. Selective disclosure is a way to achieve this. It is the ability of an individual to granularly decide what information to share. In our context, it is a very interesting feature that lets a user decide what attributes to disclose while being authenticated. How a user and verifier agreed on the attributes to disclose is beyond the scope of this paper. After being convinced about hidden and revealed attributes, the verifier grants access to the prover. More concretely, in the selective disclosure protocol, the prover decides to disclose the subset $m_{n+1},m_{n+2},\dots ,m_l$ while $m_0,m_1,\dots ,m_n$ remains secret ($n<l$). The selective disclosure protocol is described in “

Table 6. Selective disclosure protocol.

Prover	Public	Verifier
Secret ${\mathit{m}}_0,{\mathit{m}}_1,\dots ,{\mathit{m}}_{\mathit{n}}$	$\mathit{k},\mathit{p},\mathit{q},\mathit{P},{\mathit{P}}_{\mathit{pub}},\mathit{E},\mathcal{H}$
$PK\{(s,R,{\mu }_0,\dots ,{\mu }_n):$
${\prod }_{i=0}^n\mathcal{H}(P_i,R).P_{pub}=$
${({\prod }_{i=n+1}^l\mathcal{H}(P_i,R))}^{-1}(s.P-R)\wedge$	$\stackrel{(R,s),h,PK}{\stackrel{}{\to }}$	$s.P\stackrel{?}{=}h.P_{pub}+R$
$P_i={\mu }_i.P,0\le i\le n\}$

”.

7. Complexity Analysis

Designing an algorithm is good, but designing an efficient algorithm is better. Let P be a problem, with $M_1$ and $M_2$ two methods to solve P. Answer to the question: which of the methods $M_1$ and $M_2$ is more efficient is not trivial unless one knows their complexity. A complexity is a mathematical approximation to estimate the number of operations and/or memory required for an algorithm to solve a problem. A good algorithm must therefore use as little memory as possible and make the processor work as little as possible. In the remainder of this section, we adopt the following notations:

• $M_s$: Scalar multiplication over EC
• $A_p$: Point adding over EC

This section aims to compare complexities of schemes I2PA, U-prove, and Idemix. While tackling IoT devices, the case of Idemix could be left behind because a basic RSA operation (inversion or elevation to power on large numbers) is more expensive than a well-designed operation on an EC [9,40]. It should be noted that basic arithmetic operations such as addition and multiplication are negligible, in terms of resource consumption, compared to operations in elliptic curves or RSA base operations (power elevation and inversion). Given that Idemix does not provide, as far as we know, an EC-based implementation, we will focus on the memory usage. In the rest of this section, we consider a credential of n$attributes$ to sign and verify. Results presented below are based on [5,6,7,21,41] and simplified schemes presented by Alpár Gergely [42,43].

7.1. Operations over the Curve Comparison

In this first part of comparative study, we focus on U-prove and I2PA schemes regarding operations on the elliptic curve. We do not consider the hash function because its fundamental property is that it should be very easy and quick to compute. We complete the list with the scheme ecHM12 [23] focusing on the verification (proving) protocol, since this scheme does not perform any operation in the curve during the issuance protocol. The comparison results are recorded in “

Table 7. Operations over the curve analysis.

Protocol	U-prove	I2PA	ecHM12
Issuance	$(n+6).M_s+(n+4).A_p$	$(n+6).M_s+2.A_p$	$None$
Verification	$2.M_s+2.A_p$	$2.M_s+1.A_p$	$19.M_s+8.A_p$

”.

“Table 7” shows that U-prove performs more operations in the curve than I2PA what should be the number of attributes to issue and verify. In addition, the issuance is far more expensive in U-prove than in I2PA especially when the number of attributes grows. ecHM12 is by far the greediest, seeing the number of operations required in the proving (verification) protocol. We can safely conclude, without going wrong, that I2PA is more efficient than U-prove in terms of computing time when system parameters are the same.

7.2. Memory Usage Comparison

In this second part of comparative study, we are interested in memory usage. We compare the number of bits in the issuing phase. This choice is justified by the fact that in the verification phase, the verifier has nothing to store. We adopt the following notation:

• T: Total of variables needed in this phase
• P: Total of variables to be stored permanently in this phase

In addition, we assume that all variables of a protocol have the same size and this size is the same as the security level. If in the Idemix scheme we work with 1024 bits, then in I2PA and U-prove we can work with 160 bits expecting the same security level [9]. Results obtained are recorded in “

Table 8. Memory usage analysis.

Protocol	Idemix	U-prove	I2PA
User	T: n + 6	T: n + 9	T: n + 9
	P: n + 4	P: n + 4	P: n + 4
Issuer	T: n + 9	T: 2n + 8	T: 10
	P: n + 4	P: 2n + 6	P: 7

”.

“Table 8” shows that at user side, I2PA and U-prove require around $1024(n+9)$ bits while Idemix requires around $1024(n+6)$ bits. However, at issuer side, I2PA presents interesting results (around 1600 bits which does not dependent on the number of attributes) compared to U-prove and Idemix that require respectively $160(2n+8)$ and $1024(n+9)$. We can also see that if implementation is based on RSA cryptosystem, U-prove presents less interesting results than Idemix. Finally, we can conclude that I2PA is very efficient compared to Idemix and U-prove, the two leaders, in terms of anonymous credentials.

7.3. Feature Comparison

In this last part of comparative study, we focus on the number of key features that need to be carefully considered when tackling privacy concerns in an IoT context. We consider three scenarios for a feature. It can be totally, partially or not at all supported (not provided). The following legend is adopted:

• : Fully supported
• ⊘: Partially supported
• ×: Not supported

The “

Table 9. Features analysis.

Protocol	Idemix	U-prove	I2PA
fully blind signature	⊘	✔	✔
Selective disclosure	✔	✔	✔
Randomization	✔	×	✔
Untraceability	✔	⊘	✔
Unlinkability	✔	✔	✔
Unforgeability	✔	✔	✔
small keys size	×	✔	✔
Bandwidth saving	×	✔	✔
small devices efficiency	×	✔	✔

” is a summary of features comparison.

Idemix issuance is not totally blind because two of the three parts of the resulting credential are known by the issuer. These two elements are A and e of the signature $(A,e,v)$. In addition, this model is not optimal, with low-resource devices and bandwidth optimization. U-prove, meanwhile, does not support the randomization feature. Even if the issuing phase is blind, the issues related to non-traceability are not fully taken into account. Indeed, the triple $(h^{\prime },c^{\prime },r^{\prime })$ where $(c^{\prime },r^{\prime })$ constitutes the signature, if presented several times, may be traceable. The problem can be seen in two angles. First, $h^{\prime }$, constituting the user’s public key, is required in the verification phase. Since the latter only depends on the signed attributes and the secret key of the user, then the probability of having two credentials with the same public key is almost zero. Secondly, lack of randomization may be a problem. To guarantee non-traceability in U-prove, one needs several credentials [21,22]. In our schema, the triple $(h,R,c)$ can become $(h,R^{\prime },c^{\prime })$, where $(R^{\prime },c^{\prime })$ is a random version of $(R,c)$ without invalidating the signature.

8. Performance Evaluation

This section describes measurements obtained for issuance and verification of 100 credentials with 10 fixed attributes. We roughly describe software, hardware, parameters, and curve used in this simulation.

8.1. Hardware Set-up

The hardware set-up used in this experimental evaluation consists of a Raspberry Pi and a smartphone. The Raspberry Pi (Figure 4) is used to deploy both issuers and verifiers. Below are some of its characteristics:

• Model Pi 3 B+
• 1 Go of SDRAM LPDDR2
• A 64-bit quad core processor clocked at 1.4 GHz
• Raspbian operating system.
• Dual Band 2.4 GHz and 5GHz IEEE 802.11. b/g/n/AC Wireless LAN
• Enhanced Ethernet performance over USB 2.0 (maximum throughput of 300 Mbps).

The smartphone (Figure 5) acts as a user. It interacts with issuers to get credentials and with verifiers for verification of credentials purposes. Below are some of its main characteristics:

• model TECNO SPARK KB7j
• RAM 2 GB
• ROM 16 GB
• CPU 2.0 GH*4
• Battery 3500 mAh
• Memory 16 GB

8.2. Software Set-up

The software environment is made up of three major components: issuer, verifier, and user (Figure 6). Issuer and verifier are implemented with Java servers sockets while user is a mobile application developed with Android and Java client socket. We run both issuer and verifier servers on the same device (the Raspberry Pi).

8.3. Curve and Parameters

Edwards’ curves are known to offer better performance among all elliptic curve families [13]. In this experience, we use the curve Curve25519 to implementation schemes I2PA and U-prove (refer to [44] for more details about this curve) with 160 bits key size while Idemix is implemented with 1024 bits key size. We also use extended homogeneous coordinates (EHCs) to speed up operations as recommended by Josefsson et al. [45]. In the EHCs representation, the affine couple $(x,y)$ is represented as $(X:Y:Z:T)$ where $x=\frac{X}{Z}$, $y=\frac{Y}{Z}$ and $xy=\frac{T}{Z}$. The neutral point $(0,1)$ is equivalent to $(0:Z:Z:0)$ for any nonzero Z. Coordinates $(X:Y:Z:T)$ and $(\lambda X:\lambda Y:\lambda Z:\lambda T)$ are equivalent for any nonzero $\lambda$. EHMs avoid inversion operations and, as a result, improve time computation.

8.4. Issuance

Results recorded from issuance are illustrated in the following graphs. In Figure 7 and Figure 8, we illustrate respectively the variation of the duration by simulation and minimum, maximum, and average values.

Figure 7 and Figure 8 show that I2PA and U-prove present similar performance on issuance. Idemix, meanwhile, has very low performance compared to I2PA and U-prove. The time it requires for issuance is at least six times greater than that required by I2PA and U-prove. Considering distribution of time, 50% of simulations have duration higher or equal to the average for I2PA , 49% for U-prove and 51% for Idemix. Finally, we can see, without any risk of being wrong, that I2PA is efficient compared to U-prove and very efficient compared to Idemix. Its curve remains almost below that of U-prove. For 100 simulations, it offers the best performance. The minimum, maximum, and average durations (Figure 7) always remain below the others.

8.5. Verification

As for the issuance, the verification is carried out on 100 credentials of ten fixed attributes. Figure 9 represents the minimum, maximum and average values while Figure 10 represents the variation of duration by simulation.

As for the issuance, Idemix presents less interesting results than I2PA and U-prove, which present very similar performance. Regarding distribution of time, 52% of simulations have duration higher or equal to the average for I2PA, 66% for U-prove and 41% for Idemix. Finally, we can safely conclude that I2PA presents very interesting results compared to U-prove. From the minimum duration to the maximum and the average, it presents best performance.

9. Conclusions

Until recently, authentication without identification was impossible. Anonymous credentials are a suitable way to achieve this. In this paper, we propose an efficient ABC scheme for IoT. We use elliptic curves without pairing, zero knowledge proof, blind signing, selective disclosure, and randomization. Our scheme guarantees anonymity, which is a fundamental aspect for privacy preservation. As stated in Section 3, our scheme is $({ϵ}^{\prime },t^{\prime },q_i,q_h)$-secure in the sense of unforgeability under chosen message attack in the random oracle model. Analysis presented in Section 7 and performance recorded in Section 8 show that our scheme is very suitable for an IoT environment with severely constrained resources. Future work would include performance study, predicate proof over attributes, inspection, and revocation protocols. We would also investigate on how to choose attributes to disclose efficiently in the selective disclosure protocol.