Construction and Implementation of a Privacy-Preserving Identity-Based Encryption Architecture ()

David Bissessar^{}, Carlisle Adams^{}

School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada.

**DOI: **10.4236/jis.2023.144018
PDF
HTML XML
150
Downloads
709
Views
Citations

School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada.

A
recent proposal by Adams integrates the digital credentials (DC) technology of
Brands with the identity-based encryption (IBE) technology of Boneh and
Franklin to create an IBE scheme that demonstrably enhances privacy for users.
We refer to this scheme as a privacy-preserving identity-based encryption (PP-IBE)
construction. In this paper, we discuss the concrete implementation
considerations for PP-IBE and provide a detailed instantiation (based on *q*-torsion groups in supersingular
elliptic curves) that may be useful both for proof-of-concept purposes and for
pedagogical purposes.

Keywords

Identity-Based Encryption (IBE), Digital Credentials (DC), Privacy, Pairing-Based Cryptography, Supersingular Elliptic Curve, *q*-Torsion Group

Share and Cite:

Bissessar, D. and Adams, C. (2023) Construction and Implementation of a Privacy-Preserving Identity-Based Encryption Architecture. *Journal of Information Security*, **14**, 304-329. doi: 10.4236/jis.2023.144018.

1. Introduction

This paper describes, in some details, the considerations involved in implementing the Privacy-Preserving Identity-Based Encryption (PP-IBE) scheme presented by Adams [1] [2] . In 2001, Boneh and Franklin proposed the first efficient construction of Identity-Based Encryption (IBE) [3] [4] , but their construction has a system authority, the Private Key Generator (PKG), that computes all user private keys; the PKG can therefore decrypt all ciphertexts in the environment. Subsequent constructions to reduce the trust in the PKG have relied on unrealistic assumptions (see [1] ) and have not been described and implemented using easy-to-analyze numerical values.

The recently introduced proposal by Adams [1] [2] incorporates pseudonyms into the IBE process. This ensures that the PKG no longer needs to be fully trusted (in particular, the PKG is successfully able to learn any given user’s private key with probability as small as the user wishes). Adams’ proposal is based on the IBE scheme designed by Boneh and Franklin (BF-IBE) [3] [4] but also uses the Digital Credentials (DC) technology of Brands [5] [6] for identity and pseudonym credentials.

The integrated protocol combines pairing-based cryptography (in the IBE portions) with discrete-log-based cryptography (in the DC portions); thus, parameter values must be carefully chosen to provide a consistent security level throughout the PP-IBE architecture.

This present paper provides the first concrete construction and numeric example (produced by our SageMath [7] software implementation^{1}) of the complete Adams proposal. Our construction uses a *q*-torsion group (a cyclic subgroup of order *q*) of a supersingular elliptic curve over *F _{p}*, where

Section 1 of this paper presents an overview of PP-IBE. Section 2 provides a brief introductory background on BF-IBE, DC, PP-IBE, and the mathematical concepts supporting the proposed construction. Section 3 describes the construction itself. Section 4 presents a detailed numerical example using relatively small, easy-to-verify numbers. Section 5 provides some discussion, including suggested parameters for 128-bit security and enhancements for an admissible encoding of user identities. Section 6 presents performance measurements for the 128-bit secure version, and Section 7 concludes the paper.

1.1. Protocol Overview

Whereas the protocol of BF-IBE includes steps for entity setup, encryption, key extraction, and decryption, PP-IBE introduces a sequence of identity and pseudonym credential steps into the workflow. To obtain the keying material used for decryption from the PKG, Alice must redeem a valid identity/pseudonym credential. Identity and pseudonym credentials are obtained through interaction with a community of Intermediate Certification Authorities (ICAs) who each verify Alice’s identity or the derivation of a pseudonym and issue a Brands digital credential. In the key extraction protocol, the PKG returns initial keying material which can be finalized (“un-blinded”) only by Alice using random data produced during pseudonym creation. The overall flow, from encryption, through pseudonymization, to key extraction, and finally to decryption, is shown in Figure 1.

1.2. Protocol Steps

Setup: First, as a precursor to protocol execution, all participants undergo a SETUP phase. The required public primitives and parameters for PP-IBE, BF-IBE, and DC are initialized into the environment.

Following the environment setup, each of the scenario participants is set up. Thus, individual participants (Alice and Bob) and the service providers (*ICA _{i}*,

Figure 1. PP-IBE employs a five-step protocol. (1) System parameters are established for all participants. (2) Bob encrypts a message and sends it to Alice. (3) Alice engages with a community of Intermediate Certification Authorities (ICAs) which grant her identity and pseudonym credentials. (4) To obtain a decryption key, Alice presents a pseudonym credential to the PKG which validates it and provides her with initial keying material. (5) After finalizing her decryption key, Alice decrypts her message.

*ICA _{j}*,

Encrypt: Bob encrypts a message for Alice as in BF-IBE. Given an identity string for Alice (say, alice@gmail.com) and only public functions and data, Bob encrypts a message for Alice and sends her the resulting ciphertext.

Get Identity/Pseudonym Credentials: To decrypt the message received from Bob, Alice requires a decryption key. This key is calculated by Alice using keying material provided by the PKG and using a set of random values which she chooses and stores during pseudonym creation (each random value is shared with only a single ICA). Figure 1 shows an identity credential being issued by *ICA _{i}* followed by consecutive steps with

Extract: Alice presents a pseudonym credential to query the private key generator (PKG) which conducts a verification protocol. On successful verification, the PKG calculates keying material specific to messages encrypted for Alice. This keying material cannot be used directly to decrypt the ciphertext sent by Bob. Rather, Alice must finalize (“unblind”) the keying material into her decryption key by applying the random values accumulated during the pseudonym creation steps.

Decrypt: After finalization of her private key, Alice uses it to decrypt the ciphertext received from Bob. Decryption proceeds as specified in BF-IBE.

2. Background

This section introduces some of the background mathematical concepts used in PP-IBE, as well as the BF-IBE, DC, and PP-IBE algorithms themselves.

2.1. Fundamental Principles

Elliptic Curves. An elliptic curve over a finite field *E*/*F _{p}* can be seen as the set of
$\left(x,y\right)$ points with
$x,y\in {F}_{p}$ which satisfy an equation of the form

The set of points in the curve *E*(*F _{p}*) includes a distinguished point, the point at infinity
$\mathcal{O}$ , and forms a group under addition. The number of points on a curve #

Background on supersingular elliptic curves can be found in [8] . Given a prime base *b*, an integer exponent *e** *³ 1, and *t* in a range, such that
$\left|t\right|\le 2\sqrt{p}$ , a supersingular curve *E*(*F _{p}*) over a field

Each point on a curve also has an order, a scalar *r*, the number of times that point must be added to itself to give
$\mathcal{O}$ : the order of a point *o*(*P*) = *r*, so that
$r\ast P=\mathcal{O}$ for
$P\in E\left({F}_{p}\right)$ . The *r*-torsion subgroup of a curve *E*(*F _{p}*)[

In this paper, curves are used in the context of bilinear maps (“pairings”). A taxonomy of pairing-friendly curves (including FMT curves, GMV curves, Freeman curves, Cyclotomic families, Sporadic families, Scott-Barreto families, Supersingular curves, Cocks-Pinch curves, MNT curves, and DEM curves) is presented in [11] .

The construction given in this paper uses a supersingular curve of the form
${y}^{2}={x}^{3}+1$ over *F*(*p*), with prime
$p\equiv 2\left(\mathrm{mod}3\right)$ . This follows the construction in BF-IBE and lends itself well to the requirements of PP-IBE where a point *p*_{1} must be paired with itself. Other curves are also possible, including other supersingular curves and MNT curves.

Bilinear Maps. A bilinear map is a function
$\stackrel{^}{e}:{G}_{0}\times {G}_{1}\to {G}_{T}$ where *G*_{0}, *G*_{1} and *G** _{T}* have order

The embedding degree of elliptic curve *E*(*F _{p}*) with respect to the order

Distortion Maps. As we shall see, in its derivation of *ξ*, PP-IBE requires that the two inputs to the pairing be from the same cyclic group *G*_{1}. The Weil pairing produces the degenerate result 1 when the inputs *P* and *Q* are linearly dependent. The Tate pairing also has this property when *k** *> 1. One technique for working around this issue is to use a supersingular curve, *E*, with a distortion map *φ*. The distortion map projects points from the base curve onto the curve on the extension field, in a manner that the points are no longer linearly dependent, and so the result of the Weil pairing is non-degenerate [3] [9] [12] . When distortion map functionality is required, supersingular curves are not the only choice. MNT curves and their trace map may also be used [14] . We selected the supersingular curve for pedagogical reasons, as a natural progression from BF-IBE and PP-IBE.

2.2. Boneh-Franklin Identity-Based Encryption

In 2001, Boneh and Franklin published the first Identity-based Encryption scheme [3] . Their scheme is defined in terms of bilinear maps. BF-IBE features four protocols.

Setup: The environment is initialized with public parameters *q* prime, groups *G*_{1} and *G** _{T}* of order

Encrypt: Message
$M\in {\left\{0,1\right\}}^{n}$ is encrypted to ciphertext (*u*, *v*, *w*) using Alice’s public identity string
$I{D}_{i}\in {\left\{0,1\right\}}^{n}$ as follows.

1) Map the identity string to point ${I}_{A}={H}_{1}\left(I{D}_{i}\right)$ .

2) Apply the pairing $\mu =\stackrel{^}{e}\left({I}_{A},T\right)$ .

3) Select random $\sigma \in {\left\{0,1\right\}}^{n}$ .

4) Set exponent *r* to
${H}_{2}\left(\sigma \left|\right|M\right)$ .

5) Compute $z={\mu}^{r}$ .

6) Compute ciphertext $\left(u,v,w\right)=\left(rG,\sigma \oplus {H}_{3}\left(z\right),M\oplus {H}_{4}\left(\sigma \right)\right)$ .

Extract: To decrypt a message the recipient must present their
$I{D}_{i}$ to a Private Key Generator (PKG). The algorithm first maps the string to a group point
${I}_{A}={H}_{1}\left(I{D}_{i}\right)$ and then multiplies the point by the master private key to produce the decryption key
${K}_{A}=t{I}_{A}$ . The decryption key *K _{A}* is returned to the caller.

Decrypt: The decryption algorithm applies the private key *K _{A}* to ciphertext (

1) Compute $z=\stackrel{^}{e}\left({K}_{A},u\right)$ .

2) Compute $\sigma =v\oplus {H}_{3}\left(z\right)$ .

3) $M=w\oplus {H}_{4}\left(\sigma \right)$ .

4) Verify that *u* == *rG*: if these are equal, return *M*; if they are not equal, the ciphertext is rejected.

Boneh and Franklin define an adaptive chosen ciphertext notion of security IND-ID-CCA applicable to identity-based encryption, and three different variations of their protocol.

2.3. Digital Credentials

Brands Digital Credentials [5] [6] may be described in terms of three protocols: “setup”, “issue” and “show”.

Setup: During setup, the environment is initialized with
$p,q,{g}_{0}$ , where *p* is a large prime *q* is the prime order of a multiplicative subgroup of
${Z}_{p}^{*}$ , and *g*_{0} is a generator of this *q*-order subgroup. Issuers of Digital Credentials are each initialized with a private key
$\left({y}_{1},{y}_{2},\cdots ,{y}_{m},{x}_{0}\right)$ where
${y}_{1},{y}_{2},\cdots ,{y}_{m},{x}_{0}\in {Z}_{q}$ and a public key
$\left({g}_{1},{g}_{2},\cdots ,{g}_{m},{h}_{0}\right)$ , where
${g}_{i}={g}_{0}^{{y}_{i}}$ for *i* in [1, *m*] and
${h}_{0}={g}_{0}^{{x}_{0}}$ .

Issue: The issue protocol proceeds between an individual, Alice, and a credential issuer, say Bob, as follows.

1) Alice selects
$\alpha \underset{R}{\leftarrow}{Z}_{q}$ and calculates
$h={\left({g}_{1}^{{x}_{1}}{g}_{2}^{{x}_{2}}\cdots {g}_{m}^{{x}_{m}}{h}_{0}\right)}^{\alpha}\mathrm{mod}p$ using Bob’s public key and her attributes
$\left({x}_{1},{x}_{2},\cdots ,{x}_{m}\right)$ . Alice retains *h* as the first part of the credential.

2) Bob selects ${w}_{0}\underset{R}{\leftarrow}{Z}_{q}$ and calculates ${a}_{0}={g}_{0}^{{w}_{0}}\mathrm{mod}p$ which he sends to Alice.

3) Alice selects $\beta ,\gamma \underset{R}{\leftarrow}{Z}_{q}$ and calculates the second credential component ${{c}^{\prime}}_{0}=H\left(h|{h}_{2}\right)$ where ${h}_{2}={g}_{0}^{\beta}\left({\left({g}_{1}^{{x}_{1}}{g}_{2}^{{x}_{2}}\cdots {g}_{m}^{{x}_{m}}{h}_{0}\right)}^{\gamma}\right){a}_{0}\mathrm{mod}p$ . She sends a blinded version ${c}_{0}=\left({{c}^{\prime}}_{0}-\beta \right)\mathrm{mod}q$ to Bob for his signature.

4) Bob creates receives *c*_{0} and creates signature material
${r}_{0}=\left({w}_{0}-{c}_{0}\right)/({x}_{0}+{x}_{1}\ast {y}_{1}+{x}_{2}\ast {y}_{2}+\cdots +{x}_{m}\ast {y}_{m})\mathrm{mod}q$ and sends this *r*_{0} to Alice.

5) Alice evaluates an issuance verification relation, confirming that
${g}_{0}^{{c}_{0}}{\left({g}_{1}^{{x}_{1}}{g}_{2}^{{x}_{2}}\cdots {g}_{m}^{{x}_{m}}{h}_{0}\right)}^{{r}_{0}}\mathrm{mod}p$ is equal to *a*_{0}. If valid, she finalizes Bob’s signature to obtain
${{r}^{\prime}}_{0}=\left({r}_{0}+\gamma \right)/\alpha \mathrm{mod}q$ and stores the issued credential
$\left(h,{{c}^{\prime}}_{0},{{r}^{\prime}}_{0}\right)$ for later use in the showing protocol.

Show: Alice shows selected contents of her credential to verifier Victor as follows.

1) Alice sends the credential $\left(h,{{c}^{\prime}}_{0},{{r}^{\prime}}_{0}\right)$ to Victor.

2) Victor confirms the credential is valid by evaluating a verification relation, confirming that
${{c}^{\prime}}_{0}$ is equal to
$H\left(h|{g}_{0}^{{{c}^{\prime}}_{0}}{h}^{{{r}^{\prime}}_{0}}\mathrm{mod}p\right)$ *.** *

3) If the verification relation passes, Alice and Victor engage in a proof of knowledge protocol (a verification of a Boolean predicate on Alice’s credential attributes). Brands describes a variety of predicates in which Alice reveals the value of a required attribute and proves knowledge of the remaining attributes in the credential [5] [6] . One such predicate will be presented in the construction section of this document.

4) Following successful proof of knowledge, Victor provides Alice with a service or access to a resource. In the PP-IBE protocol, after integrity verification and proof of knowledge, the ICA in the role of verifier grants a pseudonym credential.

Brands [6] presents variations of the protocols including a version based on the RSA problem. This paper restricts itself to the protocol as described on the discrete logarithm problem [5] [6] . Brands digital credentials are used by Adams to sign and certify identity and pseudonym credentials. The nomenclature in our construction uses *p**'* and *q**'* for *p* and *q* above for integration with BF-IBE (which itself uses a *p* and *q*).

2.4. Privacy-Preserving Identity-Based Encryption

In [1] [2] , Adams proposes PP-IBE, an approach to reduce the amount of trust that must be placed in the PKG. PP-IBE uses digital credentials as both identity certificates and pseudonyms, and proposes a community of ICAs who certify these credentials. In this paper, we focus on the “augmented scheme” of PP-IBE in which Alice interacts with a community of ICAs to obtain a final pseudonym credential that is exchanged for keying material with the PKG.

Setup: The setup protocol of PP-IBE combines the setup activities of BF-IBE and DC, without introducing additional global (*i.e*., publicly accessible) data. Thus PP-IBE requires, for BF-IBE, a curve
${E}_{\rho}\left(a,b\right)$ with generator point *G* which generates the group *G*_{1}, and a bilinear map
$\stackrel{^}{e}:{G}_{1}\times {G}_{1}\to {G}_{T}$ . For DC, PP-IBE requires primes *p'* and *q'*, and *g*_{0}, a generator of the *q**'*-order subgroup of
${Z}_{{p}^{\prime}}^{*}$ .

Encrypt: Encryption proceeds as defined by BF IBE, thus using ${I}_{A}={H}_{1}$ (id_string) and $\mu =\stackrel{^}{e}\left({I}_{A},T\right)$ , producing ciphertext $\left(u,v,w\right)$ which is sent to Alice. Alice requires the help of a community of ICAs and a PKG to decrypt the ciphertext.

Identity Credential Issuance. Alice obtains an identity credential from *ICA _{i}* as follows. 1) Alice sends her id_string to

Pseudonym Credential Issuance. Alice may choose to pseudonymize the identity credential issued by *ICA _{i}*. To do this, Alice selects another Intermediate Certification Authority, say

$att{r}_{j}={\left({a}_{1},{a}_{2}\right)}_{j}=\left({a}_{{1}_{j}},{a}_{{2}_{j}}\right)=\left({\xi}_{j},id\left(IC{A}_{j}\right)\right)$ .

Alice may now choose to pseudonymize further: she can present *cred _{j}*,

Key Extraction. In PP-IBE, key extraction is in two parts. First Alice provides a credential on a pseudonymized point *p _{k}*

Decryption. After having successfully created *K _{A}*, Alice can decrypt ciphertext
$\left(u,v,w\right)$ as per the BF-IBE algorithm.

Note that in [1] [2] , PP-IBE uses two attributes within the credential (one for *ξ* and one for the id of the issuing ICA). However, in an actual implementation, the output of the pairing function (either the Weil or Tate pairing) will be a polynomial in the extension field *p ^{k}*. For the supersingular curves on which we base our construction below,

3. Construction

3.1. PP-IBE Group Parameters

The parameter selection consists of finding a tuple of primes (*q*, *p*, *q'*, *p'*). These values determine the main group sizes used in our construction PP-IBE. Parameter *q* sets the size of *G*_{1}; in our construction *G*_{1} is *q*-torsion group of the base elliptic curve. Parameter *p** *creates *F _{p}*, the prime field upon which the base elliptic curve is defined. Parameter

The parameter selection algorithm is as follows:

1) Select *q* a prime.

2) Find *p* prime such that *q* | *p** *+ 1, *q*^{2} ∤ *p** *+ 1 and *p* º 2 mod 3.

3) Set *q**'* to *p*.

4) Find *p**'* prime such that *q**'* | *p**'* - 1.

5) Return (*q*, *p*, *q'*, *p'*).

3.2. Definition of Mathematical Objects

Given parameters (*q*, *p*, *q'*, *p'*) initialize the required mathematical objects:

1) Let *p* define the prime field *F _{p}*.

2) Set base curve $E\left({F}_{p}\right):{y}^{2}={x}^{3}+1$ .

3) Set *G*_{1} to be the torsion group *E*(*F _{p}*)[

4) Extension field ${F}_{{p}^{2}}$ , curve on extension field $E\left({F}_{{p}^{2}}\right):{y}^{2}={x}^{3}+1$ , and corresponding torsion group $E\left({F}_{{p}^{2}}\right)\left[q\right]$ are created.

5) Set ${{G}^{\prime}}_{1}$ to be $E\left({F}_{{p}^{2}}\right)\left[q\right]$ .

6) Set ${Z}_{{q}^{\prime}}^{\text{*}}$ , ${Z}_{{p}^{\prime}}$ , ${Z}_{{p}^{\prime}}^{\text{*}}\left[{q}^{\prime}\right]$ .

7) Return ( $E\left({F}_{p}\right)\left[q\right],E\left({F}_{p}\right),E\left({F}_{{p}^{2}}\right),{Z}_{{q}^{\prime}}^{*},{Z}_{{p}^{\prime}}$ ).

The base curve
$E\left({F}_{p}\right):{y}^{2}={x}^{3}+1$ where *p* = 2 mod 3 has the following properties. It is a supersingular curve of order #*E*(*F _{p}*) =

3.3. Construction of PP-IBE

The parameters (*q*, *p*, *q'*, *p'*) and mathematical objects (
$E\left({F}_{p}\right)\left[q\right]$ ,
$E\left({F}_{p}\right)$ ,
$E\left({F}_{{p}^{2}}\right)$ ,
${Z}_{{q}^{\prime}}^{*}$ ,
${Z}_{{p}^{\prime}}^{*}\left[{q}^{\prime}\right]$ ,
${Z}_{{p}^{\prime}}$ ) are used to initialize the components of PP-IBE as follows:

1) Set *G*_{1} to
$E\left({F}_{p}\right)\left[q\right]$ .

2) Set $f:E\left({F}_{p}\right)\left[q\right]\times E\left({F}_{p}\right)\left[q\right]\to E\left({F}_{{p}^{2}}\right)$ to the Weil (or Tate) pairing.

3) Define
$\stackrel{^}{e}\left(p,q\right)\triangleq f\left(p,\phi \left(q\right)\right)$ where *φ* is the distortion map of *E*(*F _{p}*).

4) Set *m*, the number of attributes for digital credentials, to be 3.

5) Set ${Z}_{{q}^{\prime}}^{*}$ to be the field from which digital credential attributes and exponents are drawn.

6) Set ${Z}_{{p}^{\prime}}^{*}$ to be the base field of digital credentials.

7) Set *G* and
${G}_{{H}_{1}}$ to be elements of *G*_{1}.

8) Set *g*_{0} to be a generator of
${Z}_{{p}^{\prime}}^{*}\left[{q}^{\prime}\right]$ .

3.4. Hash Functions

Function
${H}_{1}:{\left\{0,1\right\}}^{*}\to {G}_{1}^{*}$ is implemented using
${G}_{{H}_{1}}$ , a generator of *G*_{1}, which is multiplied by the SHA256 hash of the input string (this product is reduced modulo *q*). Function
${H}_{2}:{\left\{0,1\right\}}^{n}\times {\left\{0,1\right\}}^{n}\to {Z}_{q}^{*}$ takes the hash of the input strings, reduces it modulo *q* − 1 and adds one to the result. Function
${H}_{3}:{G}_{T}\to {\left\{0,1\right\}}^{n}$ has the polynomial representation of the arguments and extracts the *n* least significant bits. Function
${H}_{4}:{\left\{0,1\right\}}^{n}\to {\left\{0,1\right\}}^{n}$ hashes the input string and extracts the *n* least significant bits.

3.5. Other Considerations

Use of Distortion Map. In PP-IBE, the identity token
${\xi}_{{p}_{i}}=\stackrel{^}{e}\left({p}_{i},{p}_{i}\right)$ requires that point
${p}_{i}\in {G}_{1}$ be paired with itself. The Weil pairing *f*(*P*,*Q*) returns the degenerate result 1 when the inputs are linearly dependent, which is precisely the case in determining
${\xi}_{{p}_{i}}$ . The problem is addressed by using the distortion map to implement a modified pairing function
$\stackrel{^}{e}\left(p,q\right)=f\left(p,\phi \left(q\right)\right)$ where *f* is a pairing such as the Weil or Tate pairing. The distortion map is defined as

$\phi \left(x,y\right)=\left(\zeta x,y\right)$ where
$\zeta \in {F}_{{p}^{2}}$ and
${\zeta}^{3}=1$ . This map
$\phi :\left({F}_{p}\right)\to E\left({F}_{{p}^{2}}\right)$ translates a point in *E*(*F _{p}*) to a linearly independent point in
$E\left({F}_{{p}^{2}}\right)$ , which allows the pairing to be applied returning non-degenerate results.

Three-Base Credential. The modified pairing function uses the Weil or Tate pairing and returns
$\xi \in {F}_{{p}^{2}}$ , a degree-one polynomial with two coefficients *F _{p}*. Since

Choice of the Curve. A supersingular curve was chosen for two main reasons. First, the distortion map permits the pairing of *p* with itself. Second, this curve follows the construction given in [3] ; our worked example thus complements [3] and contributes to its body of knowledge. Note that by choosing this curve, we also benefit from the BDH generator and security proofs given in [3] .

Security Impact. From the perspective of elliptic curves and bilinear pairings, we refer to the discussion in [3] . The MOV reduction [9] can be applied to such supersingular curves as we have chosen for our construction. Thus as pointed out in [3] , care must be taken to choose parameters such that the discrete log *G*_{1} = *E*(*F _{p}*)[

Issue_on_Point(). We introduce a function issue_on_point() which takes a point in *G*_{1} and a scalar and can be used for issuing both credentials and pseudonyms. Identity credentials and pseudonym credentials are both issued based on some
${\xi}_{i}$ derived from a source point in *G*_{1}. The elegance of the algorithm allows one to be expressed in terms of the other. An “issue_on_point” algorithm has been implemented, which accepts a point and a scalar (as well as the other DC-required arguments) to produce a credential on the point resulting from the multiplication of the point and the scalar received as arguments. This protocol is called both by identity issuance and pseudonym issuance logic. If an identity credential is to be issued, the scalar has the value one and multiplication leaves the point unchanged. If a pseudonym credential is to be issued, the scalar is the *s _{i}* value selected by Alice to create the pseudonym. See Figure 2 for an illustration of the steps involved in credential issuance.

4. Worked Example

The following demonstrates the augmented flow from [1] on sample parameters describing an elliptic curve of the form
$E\left({F}_{p}\right):{y}^{2}={x}^{3}+1$ where *p* = 2 mod 3. The numbers are based on output generated by the SageMath [7] implementation of PP-IBE^{2}.

4.1. System Parameter Generation

Group Parameters: First, group parameters are selected. We seek *p*, *q*, *q**'*, *p**'* all prime with
$q|p+\text{1}$ and
${q}^{\text{2}}\text{\hspace{0.05em}}\nmid \text{\hspace{0.05em}}p+\text{1}$ , *p* = 2 mod 3, *p* ≠ 3 mod 4, *q**'* = *p*, and
${q}^{\prime}|{p}^{\prime}-\text{1}$ . Our worked example (a “toy” example with deliberately small numbers for readability and easy verifiability) uses *q* = 47, *p* = 281, *q'* = 281, and *p'* = 563.

Let *q* = 47, for a torsion group *G*_{1} of size 47. Parameters *o*, *p*, *q**'* and *p**'* follow from this choice. Our construction uses a supersingular curve of the form
$E\left({F}_{p}\right):{y}^{2}={x}^{3}+1$ , where *p* = 2 mod 3, which has order
$o=\#E\left({F}_{p}\right)=p+1$ . We require *p* prime such that
$q|p+\text{1}$ and
${q}^{\text{2}}\text{\hspace{0.05em}}\nmid \text{\hspace{0.05em}}p+\text{1}$ . For the worked example, we select *p* = 281, so that our base curve is *E*/*F*_{281}:
${y}^{2}={x}^{3}+1$ with *G*_{1} = *E*(*F*_{281}) [47],

Figure 2. In the pseudonym service Alice submits credential *cred _{i}*, point

the set of points in *E** *(*F*_{281}) with order 47, along with
$\mathcal{O}$ . The order of the base curve *o* = #*E** *(*F _{p}*) = 282 is divisible by

Credential Parameters: As per our construction, the output of the pairing function will be an element in the extension field
${F}_{{p}^{2}}$ , a polynomial of degree one with coefficients in *F _{p}*. We carry the coefficients as attributes in the digital credential. The

Generators: Select generator *G** *= (1, 132) for IBE and *g*_{0} = 3 for digital credentials.

4.2. Key Generation

The ICAs are each initialized with their DC key pairs in which private key
${K}_{priv}=({y}_{1},{y}_{2},{y}_{3},{x}_{0})$ which are random values in
${Z}_{{q}^{\prime}}$ and public key
${K}_{pub}=\left({g}_{1},{g}_{2},{g}_{3},{h}_{0}\right)$ where
${g}_{i}={g}_{0}^{{y}_{i}}\mathrm{mod}{p}^{\prime}$ and
${h}_{0}={g}_{0}^{{x}_{0}}\mathrm{mod}{p}^{\prime}$ . The PKG is initialized with a BF-IBE key pair in which the master secret key is a random scalar in *Z _{q}*, say

4.3. Encryption

Encryption proceeds according to BF-IBE. Here, ciphertext
$\left(u,v,w\right)$ is created for *M* = “*abc*” (msg_bits: “011000010110001001100011”, of length *n** *= 24) using Alice’s identity string “alice@gmail.com”.

First *u* is calculated. Alice’s identity string is first mapped to point
${I}_{A}\in {\mathbb{G}}_{1}=$ *H*_{1} (“alice@gmail.com”) = (34, 33). Next the identity point *I _{A}* is paired with the master public key
$\mu =\stackrel{^}{e}\left({I}_{A},T\right)$ . Recall that
$\stackrel{^}{e}\left({p}_{1},{p}_{2}\right)=f\left({p}_{1},\phi \left({p}_{2}\right)\right)$ where
$\phi \left(x,y\right)=\left(\zeta x,y\right)$ ,
$\zeta =68b+106$ ,

Table 1. Service provider key pairs.

an arbitrary symbolic variable to be used in polynomials in
${F}_{{p}^{2}}$ . Using the Weil pairing,
$\mu =\text{weil\_pairing}\left({I}_{A},\phi \left(T\right)\right)=\text{weil\_pairing}\left(\left(34,33\right),\phi \left(252,202\right)\right)$
$=\text{weil\_pairing}(\left(34,33\right),\left(276b+17,202\right))=216b+147$ . Let *σ* = “100101000111100011000010”, and *r* = *H*_{2}_{ }(*σ*, msg_bits) = 43, then
$u=r\ast G=$
$43\ast \left(1,132\right)=\left(263,167\right)$ .

The second component of the ciphertext, *v*, is calculated as follows. Calculate
$z={\mu}^{r}={\left(216b+147\right)}^{43}=21b+60$ (where exponentiation is reduced modulo the Conway polynomial [15] [16] *b*^{2} + 280*b* + 3) and let *h*3*z* = *H*_{3}(*z*, *n*) = 001100110011011000110001; then component *v* = sigma xor h3z* *= 101001110100111011110011.

The last component of the ciphertext is *w** *= msg_bits Å *H*_{4}(*σ*). Assuming *H*_{4}(*σ*) = 011001100011010001100010, then *w* = 011000010110001001100011 Å 011001100011010001100010 = 000001110101011000000001.

The ciphertext of *M* = “*abc*” encrypted using Alice’s identity string “alice@gmail.com” is (*u*,*v*,*w*) = ((263, 167), 101001110100111011110011, 000001110101011000000001).

4.4. Identity Credentials

PP-IBE uses interactions between Alice and ICAs to certify her identity and pseudonym as precursors to interacting with the PKG to obtain the decryption keys.

Alice engages with *ICA _{i}* to obtain a digital credential
$\left(h,{{c}^{\prime}}_{0},{{r}^{\prime}}_{0}\right)$ certifying her identity. For this worked example, we choose the following values at random: (

As her next step Alice calculates
${{c}^{\prime}}_{0}=H\left(h|{h}_{2}\right)$ with input a committed random from the ICA. *ICA _{i}* selects random

To calculate
${{r}^{\prime}}_{0}$ , Alice initiates by sending
${c}_{0}={{c}^{\prime}}_{0}-\beta \mathrm{mod}{q}^{\prime}$ = 204 – 6 mod 281 = 198 to *ICA _{i}*. The ICA calculates
${r}_{0}=\left({w}_{0}-{c}_{0}\right)/({x}_{0}+{x}_{1}\ast {y}_{1}+{x}_{2}\ast {y}_{2}+{x}_{3}$
$\ast {y}_{3})\mathrm{mod}{q}^{\prime}$ = ((8 - 198)/(3 + 211 * 5 + 13 * 9 + 27 * 7) mod 281 = 128 and returns it to Alice. Alice checks the integrity of the components using the verification relation:
${g}_{0}^{{c}_{0}}{\left({g}_{1}^{{x}_{1}}{g}_{2}^{{x}_{2}}{g}_{3}^{{x}_{3}}{h}_{0}\right)}^{{r}_{0}}\mathrm{mod}{p}^{\prime}=={a}_{0}$ . In this case both

4.5. Pseudonym Credentials

As in the augmented scheme example from [1] , identity credential *cred _{i}* is used as an input in obtaining pseudonym credential

In general, to issue a pseudonym credential, the ICA conducts a verification of the previous credential and the proposed pseudonym, and then issues a new credential on the pseudonym.

*ICA _{j}* Issuance of Pseudonym Credential. Alice presents her identity credential

Alice sends *cred _{i}* = (256, 204, 245),

Verification of *cred _{i}* consists of three checks: the integrity check, the proof of knowledge, and the coefficients check. The integrity of

The next step is the proof of knowledge. For this example, let’s assume random values *w** *= 6 and *c** *= 7. *ICA _{j}* creates a random challenge

In the final verification step, *ICA _{j}* verifies that

After this successful verification of *cred _{i}*,

Next *ICA _{j}* selects random

*ICA _{k}* Issuance of Pseudonym Credential. Alice uses pseudonym credential

The proof of knowledge follows the verification relation. *ICA _{k}* creates a random challenge, say

For the last verification step, *ICA _{k}* performs a pairing and confirms that the coefficients of
${\xi}_{j}=\stackrel{^}{e}\left({p}_{j},{p}_{j}\right)=\stackrel{^}{e}\left(\left(199,158\right),\left(199,158\right)\right)=151b+29$ correspond to (

Once *cred _{j}* has been verified,

Credential
$cre{d}_{k}=\left(h,{{c}^{\prime}}_{0},{{r}^{\prime}}_{0}\right)$ is calculated as follows. First, Alice calculates and retains
$h={\left({g}_{1}^{{x}_{1}}{g}_{2}^{{x}_{2}}{g}_{3}^{{x}_{3}}{h}_{0}\right)}^{\alpha}\mathrm{mod}{p}_{1}$ = ((68^{190})(441^{197})(49^{42})(508))^{7} mod 563 = 92. Alice sends *p _{j}* = (199, 158) and

4.6. Key Extraction

Alice sends credential *cred _{k}* = (92, 240, 234) and pseudonymous point

The PKG’s next step in checking *cred _{k}* is the proof of knowledge. Proof of knowledge proceeds with the PKG generating random value

Once *cred _{k}* has been verified, the PKG creates the keying material by multiplying the pseudonymous point

4.7. Finalization and Decryption

To finalize her decryption key, Alice applies the scalars she retained during pseudonym creation to the keying material received from the PKG to obtain *K _{A}* = ((

First, she computes
$z=\stackrel{^}{e}\left({K}_{A},u\right)=\stackrel{^}{e}\left(\left(111,206\right),\left(263,167\right)\right)=21b+60$ . Then she derives *σ* = *v* ♁ *H*_{3}(*z*) = 101001110100111011110011 Å *H*_{3}(21*b* + 60) = 101001110100111011110011 Å 001100110011011000110001 = 100101000111100011000010. Using *σ*, she calculates the plaintext *M* = *w* Å *H*_{4}(*σ*)) = 000001110101011000000001 Å 011001100011010001100010 = 011000010110001001100011. Alice confirms the verification relation: *u* == *r* * *G* = 43 * (1, 132) which is equal to *u* = (263, 167), the first component in the ciphertext, so the ciphertext is confirmed to be valid. Encryption returns the string value of *M*, which is “*abc*”.

5. Discussion

The worked example of section 4 demonstrates small numbers for ease of calculation and for the sake of communication. This section discusses how to obtain parameters with more realistic security levels. BF-IBE specifies that an admissible mapping is required to achieve IND-ID-CCA security; this section also describes how the current implementation should be extended to achieve this.

5.1. Parameter Generation

The worked example uses small numbers for the sake of illustration. In an IBE deployment, the group parameters must be selected so that identity attacks on *G*_{1} and forgery attacks on the digital credential are cryptographically hard. The parameter generation algorithm described in Section 5 can be modified to set target security sizes for *F _{p}* and
${Z}_{{p}^{\prime}}$ . For 128-bit security, we would seek |

Table 2. Parameters for 128 bit security.

The required constraints hold on the above parameters. All numbers are prime, and all required relationships hold, namely that *q* | *p* + 1, *p* º 2 mod 3, *p* ≠ 3 mod 4, *q*^{2} ∤ *p*+1, and *q**'* | *p**'* – 1.

We also note that other (*i.e*., non-supersingular) elliptic curves may be used to obtain a security level of 128 bits (or higher) with a smaller value of *p*. For example, BLS12-381 and BLS12-440 curves have an embedding degree of *k** *= 12, allowing a significant reduction in the size of *p* (which, of course, would lead to a corresponding increase in the efficiency of computations involving *p*); see [18] . However, these so-called *Type 3* curves use an asymmetric pairing (
$\stackrel{^}{e}:{G}_{0}\times {G}_{1}\to {G}_{T}$ ), rather than a symmetric pairing (
$\stackrel{^}{e}:{G}_{1}\times {G}_{1}\to {G}_{T}$ ), which would then require a modification to how pairings are used for pseudonym construction in PP-IBE.

5.2. IBE Topics

Security Model. Boneh and Franklin [3] [4] define IND-ID-CCA, a form of chosen ciphertext security applicable to IBE schemes. IND-ID-CCA defines adaptive security in which the attacker attempts to demonstrate an advantage at decrypting a ciphertext for a chosen identity. The Attacker is given a choice of which identity to attack, the option of knowing the decryption keys for a set of independent identities, and oracle access to the private key extraction algorithm and to the decryption algorithm.

Construction:* *Boneh and Franklin present a construction based on *p* º 2 mod 3 with its accompanying distortion map. Our example proceeds with such a curve and is, as such, complimentary material for researchers in the area.

Distribution of Trust:* *A large amount of trust is placed in the PKG in an IBE deployment. All users obtain their decryption keys from the PKG using their public identity string. The PKG is thus able to derive private keys for all users. Adams’ architectural approach wipes out this complete knowledge, displacing it across the community of ICAs instead. The initial ICA provides a verification of ownership of the identity string (for example, using a challenge and response email pattern). The subsequent ICA issues a pseudonym credential on the trust of the previous ICA’s identity proofing mechanisms. Thus, the full trust that had previously been placed in the PKG is now spread out across the service providers:

· At the beginning of this chain of trust, the first ICA issues an identity credential, verifying Alice’s ownership of the identity string, and then maps that string to a point (using a map-to-point function *H*_{1}(.) or its stronger “admissible encoding” counterpart *L*(.); see below).

· The subsequent ICAs in the chain each issue a pseudonym on the basis of their trust in the integrity and processes of the peers that precede them in the chain, the strength of the signatures, and the quality of the map-to-point function.

Admissible Encoding:* *Of the variations presented in [3] [4] , only *FullIdent**’* is IND-ID-CCA secure. The algorithms for *FullIdent* and* **FullIdent**’* are identical, differing only differ only in terms of the definition of *H*_{1}(.). *FullIdent**’ *tightens requirements on the mapping, such that the distribution is provably uniformly random. In *FullIdent**'*, *p*_{1} = *H*_{1}(id_string) is replaced with
${p}_{1}=L\left({{H}^{\prime}}_{1}\left(id\_string\right)\right)$ where
${{H}^{\prime}}_{1}(.)$ is uniform string hashing and *L*(.) is uniform point mapping. This is referred to as an “admissible encoding”. The *H*_{1} used in this implementation conforms to FullIdent requirements but has not (yet) been verified against FullIdent’ requirements.

6. Performance

This section presents performance measures for the scenario of Figure 1 using the 128-bit security parameters presented in section 5.1.

The computing environment consists of SageMath version 9.6, installed on Ubuntu 20.04.5 LTS within the Windows Subsystem for Linux (GNU/Linux 5.10.16.3-microsoft-standard-WSL2 x86_64) on a Windows 10 Pro computer equipped with an IntelCore i7-1185G7, 3.00 GHz processor with 16.0 GB of RAM.

Table 3 presents performance measurements at 4 levels of drill-down: a) total demo execution time, b) time spent on initialization vs. protocol execution, c) breakdown by workflow step and, within each step, the breakdown per algorithm, d) within selected algorithms, a view at the primitive operations used. Full drill-down is shown for the issuance of credj, but is omitted from other steps for the sake of brevity.

The total time to run the demo is made up of two parts: initialization time, and protocol execution time. The actual protocol runs in 1.68 seconds. The full demo runs in 20 seconds, however data structure initialization accounts for 92% of this time, requiring over 18 seconds. Note that this initialization is a one-time pre-deployment cost to instantiate objects using prime moduli and curve parameters; once these are established, the PP-IBE system can be run for a set of users for an indefinite amount of time at sub-second speeds for each protocol step.

Figure 3 presents the relationship of protocol execution to system initialization and shows the execution times and proportions of the main steps in the scenario depicted in Figure 1.

Comparative Examination of Workflow Steps. When evaluated with the 128-bit security parameters, each protocol step exhibits sub-second performance. The three credential issuance steps are comparable, requiring between 304 and 462 ms. Also comparable are the encryption and decryption steps, requiring between 132 and 162 ms. These costs are dominated by the cost of the pairing. The issuance of *cred _{j}* requires 2 pairing calculations, whereas the issuance of

Primitive Usage. The PP-IBE protocol combines elliptic curve operations, pairings, and modular exponentiations. Figure 4 shows the breakdown of Step

Table 3. Performance measurements at 128 bit security.

Figure 3. Protocol execution (Setup, Encrypt, Credential Certifications, Key Extraction and Decrypt) takes approximately 1.68 seconds. Initialization activities for group and curve data structures require 18.7 seconds. Each protocol step exhibits sub-second performance. The encrypt and decrypt steps have comparable performance, as do the three credential issuance steps.

Figure 4. Looking at Step 3.2, the cost of pairing operations dominatesissuance of *cred _{j}*. The total cost of this step is 461.8 ms; 85% of that time is spent in pairings.

3.2, the interactive protocol between Alice and *ICA _{J}* for the issuance of

The total cost of step 3.2, the issuance of c*red _{j}*, is made up of four parts. Alice’s calculation of the pseudonym

7. Conclusions

In a Boneh-Franklin Identity Based Encryption (BF-IBE) [3] [4] , the Private Key Generator has significant power, with the ability to derive the decryption keys of the community of users. The community must trust, therefore, that this PKG will not be malicious.

The recently-introduced Privacy Preserving Identity-based Encryption (“PP-IBE”) [1] [2] removes this complete knowledge of the PKG, and distributes it across the PKG and a community of Intermediate Certification Authorities (ICA) who grant identity and pseudonym credentials. In PP-IBE, the generation of decryption keys becomes a collaborative responsibility between the ciphertext recipient and the PKG.

This paper provides an elaboration of the recent privacy preserving IBE proposed by Adams. We offer a construction and a worked example based on torsion groups within supersingular elliptic curves over *F _{p}* in which

Appendix—Notation

NOTES

^{1}PP-IBE SageMath implementation: [ada22] Integrated example 2 mod 3 v08.sage.

^{2}Ibid.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

[1] |
Adams, C. (2022) Improving User Privacy in Identity-Based Encryption Environments. Cryptography, 6, Article No. 55. https://doi.org/10.3390/cryptography6040055 |

[2] |
Adams, C. (2022) Security Analysis of a Privacy-Preserving Identity-Based Encryption Architecture. Journal of Information Security, 13, 323-336. https://doi.org/10.4236/jis.2022.134018 |

[3] |
Boneh, D. and Franklin, M. (2001) Identity-Abased Encryption from the Weil Pairing. In: Kilian, J., Ed., Advances in Cryptology—CRYPTO 2001. CRYPTO 2001. Lecture Notes in Computer Science, Vol. 2139, Springer, Berlin, 213-229. https://doi.org/10.1007/3-540-44647-8_13 |

[4] |
Boneh, D. and Franklin, M. (2003) Identity-Based Encryption from the Weil Pairing. SIAM Journal on Computing, 32, 586-615. https://doi.org/10.1137/S0097539701398521 |

[5] |
Brands, S. (2002) A Technical Overview of Digital Credentials. https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=9c2f1b143a9f07e8644aa72d57168638b7f469f4 |

[6] |
Brands, S. (2000) Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy. MIT Press, Cambridge. https://doi.org/10.7551/mitpress/5931.001.0001 |

[7] |
SageMath (Free Opensource Mathematics Software System). https://www.sagemath.org/ |

[8] |
Silverman, J.H. (2009) The Arithmetic of Elliptic Curves. In: Graduate Texts in Mathematics, Vol. 106, Springer, New York. https://doi.org/10.1007/978-0-387-09494-6 |

[9] |
Menezes, A., Vanstone, S. and Okamoto, T. (1991) Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. Proceedings of the 23rd annual ACM symposium on Theory of Computing, New Orleans, 5-8 May 1991, 80-89. https://doi.org/10.1145/103418.103434 |

[10] |
Galbraith, S.D., Paterson, K.G. and Smart, N.P. (2008) Pairings for Cryptographers. Discrete Applied Mathematics, 156, 3113-3121. https://doi.org/10.1016/j.dam.2007.12.010 |

[11] |
Freeman, D., Scott, M. and Teske, E. (2010) A Taxonomy of Pairing-Friendly Elliptic Curves. Journal of Cryptology, 23, 224-280. https://doi.org/10.1007/s00145-009-9048-z |

[12] | Lynn, B. (2007) On the Implementation of Pairing-Based Cryptosystems. Stanford University, Stanford. |

[13] |
Miller, V.S. (2004) The Weil Pairing, and Its Efficient Calculation. Journal of Cryptology, 17, 235-261. https://doi.org/10.1007/s00145-004-0315-8 |

[14] |
Page, D., Smart, N.P. and Vercauteren, F. (2006) A Comparison of MNT Curves and Supersingular Curves. Applicable Algebra in Engineering, Communication and Computing, 17, 379-392. https://doi.org/10.1007/s00200-006-0017-6 |

[15] |
Heath, L.S. and Loehr, N.A. (2004) New Algorithms for Generating Conway Polynomials over Finite Fields. Journal of Symbolic Computation, 38, 1003-1024. https://doi.org/10.1016/j.jsc.2004.03.002 |

[16] |
Lübeck, F. (2023) Standard Generators of Finite Fields and Their Cyclic Subgroups. Journal of Symbolic Computation, 117, 51-67. https://doi.org/10.1016/j.jsc.2022.11.001 |

[17] | Barker, E., Barker, W., Burr, W., Polk, W. and Smid, M. (2007) NIST Special Publication 800-57. NIST Special Publication 800-57. National Institute of Standards and Technology, Gaithersburg, 1-142. |

[18] | Kumar, M. and Chand, S. (2022) Pairing-Friendly Elliptic Curves: Revisited Taxonomy, Attacks and Security Concern. ArXiv Preprint ArXiv: 2212.01855. |

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2024 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.