Construction and Implementation of a Privacy-Preserving Identity-Based Encryption Architecture ()
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 implementation1) of the complete Adams proposal. Our construction uses a q-torsion group (a cyclic subgroup of order q) of a supersingular elliptic curve over Fp, where p is a prime congruent to 2 modulo 3.
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 (ICAi,
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.
ICAj, ICAk and PKG) are initialized, granted access to the environment, and instantiated with public keys, private keys, and attributes, as appropriate.
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 ICAi followed by consecutive steps with ICAj and ICAk in which pseudonym credentials are elaborated. Thus, each pseudonym is associated with a random data value; Alice creates and retains these values in local protected storage.
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/Fp can be seen as the set of
points with
which satisfy an equation of the form E:
, where
.
The set of points in the curve E(Fp) includes a distinguished point, the point at infinity
, and forms a group under addition. The number of points on a curve #E(Fp) is called the order of the curve. The Hasse theorem places a bound on the number of points in a curve:
, where
.
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
, a supersingular curve E(Fp) over a field F on prime power p = be is a curve such that its order
, with b | t [9] [10] . The worked example of §4, uses the curve
, which has order 282, with p = b = 281, e = 1 and t = 0. (To keep our example as simple as possible, we want to use a modulus that is a prime, rather than a prime power; thus, e = 1 and therefore p = b. Furthermore, supersingular curves of the form
over Fp are known to have order p + 1, meaning that t = 0. We chose p = 281 as this is a relatively small prime that is not too trivial such as 7 or 13.)
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
: the order of a point o(P) = r, so that
for
. The r-torsion subgroup of a curve E(Fp)[r] is the subset of points in E(Fp) which have order r.
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
over F(p), with prime
. This follows the construction in BF-IBE and lends itself well to the requirements of PP-IBE where a point p1 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
where G0, G1 and GT have order q. We focus on so-called symmetric pairings, where G0 = G1. The mapping is bilinear if
and
,
, and it is non-degenerate if
non-trivial points
,
(the multiplicative identity element in GT). Two common pairing functions are the Weil pairing and the Tate pairing [8] [12] [13] . The worked example in this document was verified with both the Weil and Tate pairings but, for the sake of brevity, only the computations demonstrating the Weil pairing are shown in this paper.
The embedding degree of elliptic curve E(Fp) with respect to the order q of its q-torsion subgroup is the smallest positive integer k such that
(for background, see [8] ). The embedding degree affects security. Curves with a small embedding degree are susceptible to the MOV reduction proposed by Menezes, Vanstone and Okamoto [9] . The MOV reduction allows the discrete log problem to be translated from the elliptic curve setting of G1 to the finite field setting of GT, in which there are faster sub-exponential algorithms to solve it [9] . For this reason, sufficiently large security parameters must be selected when instantiating our construction of PP-IBE (see §3, §5).
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 G1. 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 G1 and GT of order q, bilinear map
, generator
, and hash functions
, where
,
,
, and
. The PKG is given master private key
and master public key T = tG.
Encrypt: Message
is encrypted to ciphertext (u, v, w) using Alice’s public identity string
as follows.
1) Map the identity string to point
.
2) Apply the pairing
.
3) Select random
.
4) Set exponent r to
.
5) Compute
.
6) Compute ciphertext
.
Extract: To decrypt a message the recipient must present their
to a Private Key Generator (PKG). The algorithm first maps the string to a group point
and then multiplies the point by the master private key to produce the decryption key
. The decryption key KA is returned to the caller.
Decrypt: The decryption algorithm applies the private key KA to ciphertext (u, v, w) to obtain plaintext M.
1) Compute
.
2) Compute
.
3)
.
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
, where p is a large prime q is the prime order of a multiplicative subgroup of
, and g0 is a generator of this q-order subgroup. Issuers of Digital Credentials are each initialized with a private key
where
and a public key
, where
for i in [1, m] and
.
Issue: The issue protocol proceeds between an individual, Alice, and a credential issuer, say Bob, as follows.
1) Alice selects
and calculates
using Bob’s public key and her attributes
. Alice retains h as the first part of the credential.
2) Bob selects
and calculates
which he sends to Alice.
3) Alice selects
and calculates the second credential component
where
. She sends a blinded version
to Bob for his signature.
4) Bob creates receives c0 and creates signature material
and sends this r0 to Alice.
5) Alice evaluates an issuance verification relation, confirming that
is equal to a0. If valid, she finalizes Bob’s signature to obtain
and stores the issued credential
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
to Victor.
2) Victor confirms the credential is valid by evaluating a verification relation, confirming that
is equal to
.
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
with generator point G which generates the group G1, and a bilinear map
. For DC, PP-IBE requires primes p' and q', and g0, a generator of the q'-order subgroup of
.
Encrypt: Encryption proceeds as defined by BF IBE, thus using
(id_string) and
, producing ciphertext
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 ICAi as follows. 1) Alice sends her id_string to ICAi who verifies Alice’s ownership. 2) ICAi computes
(id_string) and
. Alice and ICAi engage in the Brands Issuing protocol with
and x2 = the id of ICAi. On successful completion of the issuing protocol, Alice holds
, a signed identity credential enclosing a
certified by a trusted service provider.
Pseudonym Credential Issuance. Alice may choose to pseudonymize the identity credential issued by ICAi. To do this, Alice selects another Intermediate Certification Authority, say ICAj and proceeds as follows. 1) Alice sends credi, pi,
and sj to ICAj. 2) ICAj applies the verification relation to confirm digital integrity of the credential. 3) If the credential passes the integrity check, Alice and ICAj conduct a Brands proof of knowledge on attributes
and
. 4) ICAj verifies provenance, confirming that that
5) Following successful verification of credi, ICAj computes pseudonym point
,
and proceeds with the Brands issuing protocol with
.
Alice may now choose to pseudonymize further: she can present credj, pj, si to another authority (say, ICAk), proving knowledge of attrj. On successful verification, pseudonym pk = sj * pj is created by ICAk, and a new credential, credk, is issued to Alice. Using this process, Alice may create a chain of credentials on pseudonyms of any length she wishes. Note that the random values si, sj, ∙∙∙ are retained by Alice for use in key extraction.
Key Extraction. In PP-IBE, key extraction is in two parts. First Alice provides a credential on a pseudonymized point pk to the PKG. After verifying the credential and Alice’s proof of knowledge of the signed attributes, the PKG creates keying material K = t * pk, where t is the PKG’s master secret key. This initial keying material is sent to Alice who creates the decryption key KA by multiplying this K with the product of the inverses of the scalars used to create pk, thus KA = wK, where
.
Decryption. After having successfully created KA, Alice can decrypt ciphertext
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 pk. For the supersingular curves on which we base our construction below, k = 2 and the pairing output will be a polynomial with two coefficients. Therefore, the credentials in our construction have been modified to contain three attributes (two for the coefficients of the pairing output and one for the id of the issuing ICA).
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 G1; in our construction G1 is q-torsion group of the base elliptic curve. Parameter p creates Fp, the prime field upon which the base elliptic curve is defined. Parameter p' creates
the base field for digital credentials. Parameter q' is the order of the multiplicative subgroup of
; digital credential attributes and other exponents are drawn from
.
The parameter selection algorithm is as follows:
1) Select q a prime.
2) Find p prime such that q | p + 1, q2 ∤ 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 Fp.
2) Set base curve
.
3) Set G1 to be the torsion group E(Fp)[q].
4) Extension field
, curve on extension field
, and corresponding torsion group
are created.
5) Set
to be
.
6) Set
,
,
.
7) Return (
).
The base curve
where p = 2 mod 3 has the following properties. It is a supersingular curve of order #E(Fp) = p + 1. Since q | p + 1, E(Fp) contains a torsion group E(Fp)[q] of order q. The curve E(Fp) also supports a distortion map
where
and
.
3.3. Construction of PP-IBE
The parameters (q, p, q', p') and mathematical objects (
,
,
,
,
,
) are used to initialize the components of PP-IBE as follows:
1) Set G1 to
.
2) Set
to the Weil (or Tate) pairing.
3) Define
where φ is the distortion map of E(Fp).
4) Set m, the number of attributes for digital credentials, to be 3.
5) Set
to be the field from which digital credential attributes and exponents are drawn.
6) Set
to be the base field of digital credentials.
7) Set G and
to be elements of G1.
8) Set g0 to be a generator of
.
3.4. Hash Functions
Function
is implemented using
, a generator of G1, which is multiplied by the SHA256 hash of the input string (this product is reduced modulo q). Function
takes the hash of the input strings, reduces it modulo q − 1 and adds one to the result. Function
has the polynomial representation of the arguments and extracts the n least significant bits. Function
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
requires that point
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
. The problem is addressed by using the distortion map to implement a modified pairing function
where f is a pairing such as the Weil or Tate pairing. The distortion map is defined as
where
and
. This map
translates a point in E(Fp) to a linearly independent point in
, 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
, a degree-one polynomial with two coefficients Fp. Since q' = p, these coefficients may carried as attributes
in the digital credential. There are different approaches to carrying ξ in the credential; however, we found that carrying both coefficients is convenient for calculations in key extraction. Thus, one attribute (and corresponding base) is added to PP-IBE as defined in [1] . Commensurate changes are required to the digital credential setup, issue, and verification protocols.
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 G1 = E(Fp)[q] remains difficult in
. In addition to security in elliptic curves and bilinear maps, we must also consider the difficulty of the traditional discrete log problem due to use of the digital credentials. Parameter sizes are discussed in §5.
Issue_on_Point(). We introduce a function issue_on_point() which takes a point in G1 and a scalar and can be used for issuing both credentials and pseudonyms. Identity credentials and pseudonym credentials are both issued based on some
derived from a source point in G1. 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 si 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
where p = 2 mod 3. The numbers are based on output generated by the SageMath [7] implementation of PP-IBE2.
4.1. System Parameter Generation
Group Parameters: First, group parameters are selected. We seek p, q, q', p' all prime with
and
, p = 2 mod 3, p ≠ 3 mod 4, q' = p, and
. 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 G1 of size 47. Parameters o, p, q' and p' follow from this choice. Our construction uses a supersingular curve of the form
, where p = 2 mod 3, which has order
. We require p prime such that
and
. For the worked example, we select p = 281, so that our base curve is E/F281:
with G1 = E(F281) [47],
Figure 2. In the pseudonym service Alice submits credential credi, point pi, and scalar sj to ICAj. First, credi is verified for data integrity, attribute ownership and point correspondence. After verification, an issuance protocol is conducted to create pseudonym credential credj. The verification and Issuance protocols of Brands are augmented with point verification and derivation steps which use modified pairing
.
the set of points in E (F281) with order 47, along with
. The order of the base curve o = #E (Fp) = 282 is divisible by q = 47. The embedding degree of our worked example is k = 2, the smallest positive integer k such that #G1| #E (Fp)k + 1. In our example,
.
Credential Parameters: As per our construction, the output of the pairing function will be an element in the extension field
, a polynomial of degree one with coefficients in Fp. We carry the coefficients as attributes in the digital credential. The q' of the digital credential parameters must be large enough to accommodate these numbers. We set q' = p = 281. It remains only to find p', the modulus for digital credentials, such that
. For our worked example, we select p' = 563.
Generators: Select generator G = (1, 132) for IBE and g0 = 3 for digital credentials.
4.2. Key Generation
The ICAs are each initialized with their DC key pairs in which private key
which are random values in
and public key
where
and
. The PKG is initialized with a BF-IBE key pair in which the master secret key is a random scalar in Zq, say t = 23, and the public key is calculated as
. Select
(here,
and
). Table 1 presents the key pairs for the service providers of the scenario presented in the augmented scheme of [1] .
4.3. Encryption
Encryption proceeds according to BF-IBE. Here, ciphertext
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
H1 (“alice@gmail.com”) = (34, 33). Next the identity point IA is paired with the master public key
. Recall that
where
,
, f() is either the Tate or Weil pairing, and b is
Table 1. Service provider key pairs.
an arbitrary symbolic variable to be used in polynomials in
. Using the Weil pairing,
. Let σ = “100101000111100011000010”, and r = H2 (σ, msg_bits) = 43, then
.
The second component of the ciphertext, v, is calculated as follows. Calculate
(where exponentiation is reduced modulo the Conway polynomial [15] [16] b2 + 280b + 3) and let h3z = H3(z, n) = 001100110011011000110001; then component v = sigma xor h3z = 101001110100111011110011.
The last component of the ciphertext is w = msg_bits Å H4(σ). Assuming H4(σ) = 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 ICAi to obtain a digital credential
certifying her identity. For this worked example, we choose the following values at random: (α = 12, β = 6, γ = 2, w0 = 8). As a first step, Alice calculates h on her own. She calculates her identity point p1 = H1 ('alice@gmail.com') = IA = (34, 33). Following this, she calculates
,
. Assuming service provider id = 27, Alice has attributes
. Assuming α = 12, she calculates and retains
.
As her next step Alice calculates
with input a committed random from the ICA. ICAi selects random w0 (assume w0 = 8), calculates
, and sends a0 to Alice. Alice uses a0 to calculate
= 36(243211 * 54113 * 49827 * 27)2 * 368 mod 563 = 99. This h2 is combined with h to form
= SHA256(256|99) mod 281 = 204. This
will be the second component in the digital credential.
To calculate
, Alice initiates by sending
= 204 – 6 mod 281 = 198 to ICAi. The ICA calculates
= ((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:
. In this case both a0 and 3198 * ((243211) * (54113) * (49827) * 27)128 mod 563 are equal to 368, so the verification relation holds. Alice finalizes
. Alice stores the finalized credential
for the next step in certifying a pseudonym with ICAj.
4.5. Pseudonym Credentials
As in the augmented scheme example from [1] , identity credential credi is used as an input in obtaining pseudonym credential credj from ICAj, which is then used to obtain another pseudonym credential credk from ICAk.
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.
ICAj Issuance of Pseudonym Credential. Alice presents her identity credential credi in the showing protocol. ICAj verifies this before issuing a pseudonym credential credj.
Alice sends credi = (256, 204, 245), pi = (34, 33) and a scalar sj = 25 to ICAj, as input to the pseudonym service, which will yield a new credential credj = (440, 252, 63) on pseudonym point pj = (199, 158). This process proceeds in two steps: first the submitted credi is verified, after that, the new credj is issued.
Verification of credi consists of three checks: the integrity check, the proof of knowledge, and the coefficients check. The integrity of credi is verified using the digital credentials verification relation. Given credential
verify that
Thus with credi = (256, 204, 245),
= (3204) (256245) mod 563 = 99. This value corresponds to the h2 calculated during the issuing protocol, so
which is equal to
, which satisfies the verification relation.
The next step is the proof of knowledge. For this example, let’s assume random values w = 6 and c = 7. ICAj creates a random challenge c = 7, and sends it to Alice who creates
where the value for
and
are Alice’s attributes for credi. Alice sends
to ICAj who verifies it by confirming the equality of
mod p' = (25630)363 mod 563 = 485 with
= (243211*7)(54113*7)(7627*7)(277) mod 563 = 485; thus proof of knowledge has been confirmed.
In the final verification step, ICAj verifies that credi is on the coefficients of ξi. In this case correspondence is confirmed:
, the coefficients of which correspond to the (x1, x2) received in the proof, above.
After this successful verification of credi, ICAj issues a pseudonym credential to Alice. Let’s assume the random values for the issue protocol to be α = 19, β = 26, γ = 32, w0 = 18. ICAj calculates new point pj = pi * s1 = (34, 33) * 25 = (199, 158) and ξj = ê(pj, pj) = ê((199, 158), (199, 158)) = weil_pairing((199, 158), phi((199, 158))) = weil_pairing((199, 158), (44b + 19, 158)) = 151b + 29. Assuming id(ICAj) = 11, the credential is constructed on attributes (x1 = 29, x2 = 151, x3 = 11). Alice calculates and retains
= ((28929)(326151)(34911)(470))19 mod 563 = 440.
Next ICAj selects random w0=18 and calculates
, which it sends to Alice. Alice calculates
where h = 197 and
= 326((28929)(326151)(34911)(470))32484 mod 563 = 425, thus
. Alice retains this
and calculates
= (252 - 26) mod 281 = 226 which is sent to ICAj. ICAj produces signature data
= (18 - 226)/(13 + 29 * 15 + 151 * 19 + 11 * 17) mod 281 = 41, which is sent to Alice. Alice evaluates the issue-time verification relation, confirming that
= 3226((28929)(326151)(34911)(470))41 mod 563 = 484 equals the expected value of a0 = 484. Alice proceeds to unblind the signature
= (41 + 32)/19 mod 281 = 63 and stores the resulting credential credj = (440, 252, 63).
ICAk Issuance of Pseudonym Credential. Alice uses pseudonym credential credj to obtain another pseudonym credential with ICAk. Alice enters into the “show” protocol, supplying credj = (440, 252, 63), attrj = (x1 = 29, x2 = 151, x3 = 11), pj = (199, 158) and s2 = 17. ICAk first checks the time verification relation for credj:
. Here
= 252, h = 440, and
= 325244063 mod 563 = 425, thus, the hash H(440|425), evaluates, as above, to 252 which is equal to
. The verification relation is satisfied for credj.
The proof of knowledge follows the verification relation. ICAk creates a random challenge, say c = 8, and sends it to Alice who creates
= (37, 29, 151, 11) where c' = c/α + w mod q = 8 /19 + 7 mod 281 = 37 and x1, x2, x3 are the attributes attrj. Alice sends proofj to ICAk who verifies it by confirming that
. Here,
= (44037)381 mod 563 = 99 and
= (28929*8)(326151*8)(34911*8)(4708) mod 563 = 99; thus the proof of knowledge verifies correctly.
For the last verification step, ICAk performs a pairing and confirms that the coefficients of
correspond to (x1 =29, x2 = 151) of credj.
Once credj has been verified, ICAk proceeds to issue pseudonym credential credk to Alice. For the issuance of credk assume values of α = 7, β = 26, γ = 22, w0 = 28 for the random values of the issue protocol.Alice calculates her new point pk = pj * s2 = (199 , 158) * 17 = (99, 179) and ξk = ê(pk, pk) = ê((99, 179), (99, 179)) = weil_pairing ((99 , 179), phi((99, 179))) = weil_pairing((99, 179), (269b + 97, 179)) = 197b + 190. Assuming id(ICAk) = 42, attributes attrk = (x1 = 190, x2 = 197, x3 = 42) are used for issuance of credk.
Credential
is calculated as follows. First, Alice calculates and retains
= ((68190)(441197)(4942)(508))7 mod 563 = 92. Alice sends pj = (199, 158) and s2 = 17 to ICAk, who calculates the same attrk. Next ICAk selects a random w0, say the value 28, and calculates
= 328 mod 563 = 147 and sends this a0 to Alice. Alice calculates
where h = 92 and
= 326(68190 * 441197 * 4942 * 508)22 * 147 mod 563 = 513, so
. Alice retains
and calculates
and sends it to ICAk. Finally, ICAk produces signature data
= ((28 - 214)/(23 + 190 * 25 + 197 * 29 + 42 * 27)) mod 281 = 211, which is sent to Alice. Alice evaluates the issuance-time verification relation, confirming that
= 3214((68190)(441197)(4942)(508))211 mod 563 = 147 which equals a0, as expected. Alice proceeds to unblind the signature
= (211 + 22)/7 mod 281 = 234 and stores the resulting credential credk = (92, 240, 234), along with the attributes and other parameters she used to obtain it.
4.6. Key Extraction
Alice sends credential credk = (92, 240, 234) and pseudonymous point pk = (99, 179) to the PKG with supporting attributes (190, 197, 42). The PKG checks the verification relation:
, with h = 92, and
= 3240 * 92234 mod 563 = 513, thus H(92|513) = SHA256(92|513) mod 281 = 3b11806f98cd81d368137bb211c63561bff95c219fc5b6649501708d0e14693b mod 281 = 240 which indeed equals
, so the verification relation holds.
The PKG’s next step in checking credk is the proof of knowledge. Proof of knowledge proceeds with the PKG generating random value w = 8 and Alice generating proof (c' = (9/7 + 8) mod 281 = 210, x1 = 190, x2 = 197, x3 = 42). The PKG evaluates (hc')a = (92210)271 mod 563 = 201 and confirms that it is equal to
mod 563. Finally, the PKG confirms that the coefficients of
correspond to attributes (x1, x2).
Once credk has been verified, the PKG creates the keying material by multiplying the pseudonymous point pk = (99, 179) with PKG private master key t = 23 to obtain keying material K = t * pk = 23 * (99, 179) = (34, 248). This keying material is sent to Alice.
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 KA = ((s1s2)−1 mod q) * K = ((25 * 17)−1 mod 47) * (34, 248) = 24 * (34, 248) = (111, 206). Alice had received ciphertext
from Bob. She proceeds to decrypt it using the decryption key KA = (111, 206).
First, she computes
. Then she derives σ = v ♁ H3(z) = 101001110100111011110011 Å H3(21b + 60) = 101001110100111011110011 Å 001100110011011000110001 = 100101000111100011000010. Using σ, she calculates the plaintext M = w Å H4(σ)) = 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 G1 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 Fp and
. For 128-bit security, we would seek |q| ³ 254 bits and |p'| ³ 3072 bits [17] . If we want 128 bits of security, we will need p to be at least 1536 bits in length (so that the group size in
is at least 3072 bits long). One possible combination of parameters is shown in Table 2.
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, q2 ∤ 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 (
), rather than a symmetric pairing (
), 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 H1(.) 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 H1(.). FullIdent’ tightens requirements on the mapping, such that the distribution is provably uniformly random. In FullIdent', p1 = H1(id_string) is replaced with
where
is uniform string hashing and L(.) is uniform point mapping. This is referred to as an “admissible encoding”. The H1 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 credj requires 2 pairing calculations, whereas the issuance of credj and credk requires three. Encryption and decryption each require one pairing. The key extraction step also requires a pairing for credential verification. Assuming upfront data structure initialization, key-pair establishment and the selection of generators requires 1.6 ms.
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 credj. 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 ICAJ for the issuance of credj, and provides a view of the usage of the primitive operations and how the costs of these impact protocol performance.
The total cost of step 3.2, the issuance of credj, is made up of four parts. Alice’s calculation of the pseudonym ζj, the ICA verification of credi, the issuance of credj, and Alice’s acceptance of credj. The first three parts each require a pairing calculation, at approximately 130 ms. The modular exponentiations require a fraction of that time. Looking at credential issuance and acceptance in steps 3 and 4, over 20 modular exponentiations are required, at a total of 43.5 ms, these making up only 25% of the total 172.54 ms required.
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 Fp in which p = 2 mod 3, along with their accompanying distortion map. We make extensions to Adams’ algorithms, including a parameter generator, an added digital credential base to support our approach of carrying the Weil or Tate pairing coefficients, and a reuse opportunity between the issuance of identity credentials and pseudonym credentials. We offer a software implementation and a worked numeric example that may be useful to researchers and to students new to this area. We also offer selected discussions into representative-sized parameters for privacy and security properties in an open-world setting.
Appendix—Notation
NOTES
1PP-IBE SageMath implementation: [ada22] Integrated example 2 mod 3 v08.sage.
2Ibid.