Vector Dominance with Threshold Searchable Encryption (VDTSE) for the Internet of Things

1  Introduction

The Internet of Things (IoT) [1] provides safe and controllable real-time online monitoring, positioning, and other service functions. As an important IoT application in the medical field, the Internet of Medical Things (IoMT) can realize efficient and inexpensive healthcare and enhance patient comfort. However, the data involved in continuous monitoring can be massive, and the devices used to collect the data are resource-constrained. As a result, the data is often stored in the cloud, which may seriously violate patient privacy during data collection, storage, and computation. Suspecting the infringement of their healthcare privacy, patients may become reluctant to participate or encrypt their medical data before uploading it to service providers. This raises another question: how to perform a user search about this encrypted private data. In this context, Searchable Encryption (SE) is desirable as a prominent encryption tool for privacy-preserving IoMT [2,3].

1.1 Motivation

Consider a specific example of privacy-preserving diabetes screening (see Fig. 1) in IoMT. In this example, a nurse tries to screen out diabetics from Personal Health Records (PHRs). However, PHRs contain private information, and the patient is unwilling to share them with anyone. Therefore, the patient in this example encrypts the medical record X→ (random blood glucose = 4, fasting blood glucose = 3, 2-h post-load glucose = 5, glycated hemoglobin = 4) and the personal information M before uploading them to the service provider. In this case, the nurse sends a search request (Δ→, t) (random blood glucose = 3, fasting blood glucose = 2, 2-h post-load glucose = 3, glycated hemoglobin = 5, t = 2 (1≤t≤4)) to the service provider using a handheld Personal Digital Assistant (PDA). When the service provider detects number(X→≻Δ→)≥t (X→≻Δ→ means that X→ dominates Δ→ [4]), it will send the encrypted M to the nurse. In this process, the service provider has no prior knowledge of X→ and M.

Figure 1: Privacy-preserving diabetes screening

For the application above, it is necessary to solve number(X→≻Δ→)≥t in SE. It is very helpful when we need to compare multiple attributes while counting the number of matches. We call the proposed scheme Vector Dominance [4] with Threshold Searchable Encryption (VDTSE). The vector dominance with threshold problem determines whether the number of components in vectors X→=(X1,…,Xn) and Δ→=(Δ1,…,Δn) (Xi>Δi, i∈[1,n]) reaches a certain threshold t.

Therefore, the proposed VDTSE scheme is favorable for threshold comparison queries in a public-key SE system. When number (X→≻Δ→)≥t holds, the encrypted M will be sent to the requester. Besides, our algorithm can solve the problem of existing SE schemes by controlling the threshold t, which is adaptive and can support additional functionalities such as range queries (t = 0) or similarity searches (Xi=Δi).

1.2 Our Contribution

The main contributions of this study are outlined below:

• We design a VDTSE scheme supporting comparable attributes that can function for the (t, n)-threshold policy. Although existing schemes [5–8] also support this feature, they are restricted to AND-gates (or (t, t)-threshold). We implement the threshold using a Lagrangian polynomial technique.

• The VDTSE scheme has a shorter trapdoor that makes it more suitable for data storage on mobile devices (such as PDAs). To achieve this, we solve it using our technique modified in Hidden Vector Encryption (HVE) [7], which makes the trapdoor size linear.

• We prove the security, flexibility, and effectiveness of the proposed scheme through theoretical comparison with other schemes. Finally, the experiment shows that the trapdoor size of our method is much smaller than that of other similar SE schemes.

1.3 Outline

The rest of this paper is structured as below. Section 2 describes the related work of VDTSE. Section 3 contains the preliminaries, while Section 4 presents the scheme construction. Section 5 discusses the security proof for our scheme, Section 6 describes the performance of the proposed scheme, and Section 7 concludes the article and suggests possible future work.

2  Related Work

Song et al. popularized the SE scheme [9] that enabled a user to generate both ciphertexts and trapdoors under a symmetric system, so service providers could perform a match search on encrypted information. Under the symmetric system, SE was further improved in [10–12]. In 2004, Boneh et al. [13] considered the first asymmetric SE scheme, Public-key Encryption with Keyword Search (PEKS). The initial public-key SE schemes, however, were limited to test keyword equality. Among these developments, comparative searches received little attention.

To address the aforementioned issue, Boneh et al. [5] created a searchable public-key system called HVE in 2007, which allowed for conjunctive range queries over encrypted data. That same year, Shi et al. [6] proposed a multi-dimensional range SE scheme. However, the aforementioned methods were inefficient and disadvantageous from an operational standpoint. As a result, Park [7] proposed a novel HVE that was effective in prime-order groups significantly smaller than the composite-order groups on the identical level. Later, Park et al. [8] realized a more effective HVE scheme. Although the schemes above supported the AND gate of attribute comparison, they could not apply to arbitrary threshold gates. Fortunately, Sun et al. [14] extended the technique by combining HVE and predicate encryption (PE) for the inner product (called IPE) to achieve threshold comparison queries.

In addition to these references, other scholars addressed the threshold comparison. In 2007, Bethencourt et al. [15] presented a threshold comparison scheme to realize numeric ranges search. In 2018, Attrapadung et al. [16] developed a numeric comparison scheme under the Attribute-Based Encryption (ABE) system. In 2017, Xue et al. [17] constructed a comparable ABE scheme that was more efficient. Although these schemes [15–17] were under the public key system, they could not protect the privacy of X→.

To the best of our knowledge, the only scheme that supported the threshold comparison was [14], but their ciphertext and private key size increased quadratically, posing potential challenges in resource-constrained IoT devices. Therefore, we need to design a more efficient SE scheme.

3  Preliminaries

3.1 Bilinear Maps

Assume g is a generator in G, while G and GT are two multiplicative cyclic groups whose order is prime p. e:G×G→GT is a function with these attributes:

1. Bilinear. We have e(uc,vd)=e(u,v)cd, where u,v∈G, c,d∈Zp.

2. Nondegenerate. e(g,g)≠1.

3. Computable. e is a computable map algorithm.

Therefore, we state that e is a bilinear pairing map within G. It is worth noting that e(,) is symmetric because e(gc,gd)=e(g,g)cd=e(gd,gc).

3.2 Complexity Assumptions

Decisional Bilinear Diffie-Hellman (DBDH) Assumption. The following describes the DBDH problem: Provided (g,ga,gb,gc,Z)∈G4×GT, identify Z=e(g,g)abc or Z is random in GT.

Augmented Decision Linear (ADLIN) Assumption. Provided (g,gz1,gz2,gz22,gz2/z1,gz22z3,gz4,Z) ∈G8, find Z=gz1(z3+z4) or Z is random in G.

Definition 1. The {DBDH, ADLIN} assumption holds in G when the advantage of any polynomial time algorithm in dealing with the {DBDH, ADLIN} problem is negligible.

3.3 Security Model

Our scheme is characterized by a chosen plaintext security, and ciphertext CT offers no information about the vector X→ and the message M, which is proved in a security proof that relies on the difficulty of DBDH and ADLIN. The following games are played between an adversary 𝒜 and a challenger 𝒞. Besides, U and ℓ are given to 𝒜, where U is the attribute universal set and ℓ is the length of vector.

• Initialization (Init). 𝒜 commits X→0∗, X→1∗∈Σℓ/U to 𝒞.

• Setup. 𝒞 runs the KeyGen algorithm to get a public key PK and a secret key SK, offers PK to 𝒜.

• Query Phase 1. 𝒜 performs a series of trapdoor queries adaptively. To any trapdoor TΔ→i from queried vectors Δ→1,…,Δ→qη∈(Σ)ℓ/U and thresholds t1,…,tqη, there is a restriction of fΔ→i,ti(X→0∗)=fΔ→i,ti(X→1∗) for all i=1,…,qη. 𝒞 uses trapdoors TKΔ→i,ti←Trapdoor(SK,Δ→i,ti) to respond to 𝒜.

• Challenge. 𝒜 offers M0,M1∈ℳ. If fΔ→i,ti(X→0∗)=fΔ→i,ti(X→1∗)=1, then M0=M1. 𝒞 responds CT∗ ← PEKS(PK,X→β∗,Mβ) to 𝒜, where β∈{0,1}.

• Query Phase 2. 𝒜 makes other trapdoor queries adaptively for vectors Δ→qn+1,…,Δ→qTK and thresholds tqn+1,…,tqTK. The restrictions are the same as those in Query Phase 1 and Challenge.

• Guess. 𝒜 guesses β′. 𝒜 wins the game when β′=β, where β′∈{0,1}.

We define Adv𝒜VDTSE=|Pr[β′=β]−1/2| as the advantage that 𝒜 has in breaking the VDTSE scheme.

Definition 2. If the advantage Adv𝒜VDTSE is negligible, the VDTSE scheme is selectively secure.

4  Construction

4.1 A Novel Encoding

This section presents the techniques for solving number(X→≻Δ→)≥t in the form of a novel encoding. We set a universal set U={1,2,…,|U|}. Every bit xj of a |Δ→|×|U|-dimension vector x→ converted from vector X→ is chosen from {0,1} following Eq. (1). In a similar way, every bit σj of another |Δ→|×|U|-dimension vector σ→ transformed from vector Δ→ is selected from {1,∗} according to Eq. (2).

x(i−1)×|U|+j={1,Xi<j,0,otherwise,(1)

where 1≤j≤|U|, 1≤i≤|X→|.

σ(i−1)×|U|+j={1,Δi=j,∗,otherwise,(2)

where 1≤j≤|U|, 1≤i≤|Δ→|.

When the VDTSE scheme is used in multi-user scenarios, a trusted private service provider needs to be added to receive trapdoors from users and then send the trapdoors to an untrusted public service provider. Therefore, only single-user scenarios are considered in this paper.

Applying the example of privacy-preserving diabetes screening in the Introduction, set X→=(X1, X2, X3, X4)=(4, 3, 5, 4), Δ→=(Δ1,Δ2,Δ3,Δ4)=(3,2,3,5), t = 2, ℓ=|X→|×|U|=20, where U={1, 2, 3, 4, 5} and |X→|=|Δ→|=4. Two 20-dimension vectors x→ and σ→ are transformed from X→ and Δ→ following Eqs. (1) and (2), respectively.

For X→, the 20-dimension vector x→ is represented by

For Δ→, the 20-dimension vector σ→ is represented by

Since there are 3 (>t) equal corresponding bits of x→ and σ→ excluding * bits, number(X→≻Δ→)≥t holds. The detailed scheme is as follows.

4.2 Scheme

• KeyGen(k, ℓ, U). The KeyGen algorithm uses a security parameter k = 1024 bit and a type-A elliptic curve that has as input a 160-bit group order, a vector length ℓ, a universe U, and a random generator g ∈ G to generate our scheme parameters. It selects random exponents y1,v1,…,vℓ, t1,…,tℓ∈Zp as well as random elements α, (h1, u1, w1) ,…, (hℓ, uℓ, wℓ)∈G. It defines g1=gα, Y1=gy1, Vi=gvi, Ti=gti for i=1,…,ℓ. Furthermore, it establishes Ω=e(g1,Y1) ∈ GT. The public key PK and the secret key SK are

PK=(g,Y1,(h1,u1,w1,V1,T1),…,(hℓ,uℓ,wℓ,Vℓ,Tℓ),Ω)∈G5ℓ+2×GT,SK=(α,g1=gα,y1,v1,…,vℓ,t1,…,tℓ)∈Zp2ℓ+2×G.

• PEKS(PK, X→). With PK and vector X→=(X1,…,Xℓ/U) as input, this algorithm initially converts X→ into x→=(x1,…,xℓ) based on Eq. (1). It chooses two random parameters s1, s2∈Zp, then uses them to encrypt message M∈GT and vector x→ for generating ciphertext:

CT=(Y1s1,gs2,(h1u1x1)s1V1s2,…,(hℓuℓxℓ)s1Vℓs2,w1s1T1s2,…,wℓs1Tℓs2,Ωs1M)∈G2ℓ+2×GT.

This encryption algorithm ensures the confidentiality of M and x→. Their integrity can be recognized by the Message Authentication Code (MAC), public key-based Homomorphic Linear Authentication (HLA), Hash-based Message Authentication Code (HMAC), etc.

• Trapdoor(SK, Δ→, t). This algorithm uses SK and vector Δ→=(Δ1,…,ΔJ,…,Δℓ/U) as input, then chooses at random a t-1 degree polynomial q(x) where q(0)=α. It first transforms Δ→ into σ→ = (σ1,…,σℓ) ∈ (Σ∗)ℓ based on Eq. (2). To generate a trapdoor Tσ→ for i∈S(σ→), where S(σ→) is the set of all indexes i that satisfies σi≠∗, it computes Tσ→ as

Tσ→=(σ∗,∀i∈S(σ→):{gq(J)(hiuiσi)rJwiηJ,Y1rJ,Y1ηJ,Y1−(virJ+tiηJ),Viy1ZJ,Y1ZJ,(hiuiσi)ZJ}J=1ℓ/U)∈G7(ℓ/U),i=(J−1)U+ΔJ.

• Test (CT,Tσ→). Let CT = (C1, C2, C3,1, …, C3,i, …, C3,ℓ, C4,1, …, C4,i, …, C4,ℓ, C5) and Tσ→=(K1,J,K2,J,K3,J,K4,J,K5,J,K6,J,K7,J) for 1≤J≤ℓ/U. The Test algorithm computes the following:

Step 1.

e(K7,J,C1)⋅e(K5,J,C2)e(K6,J,C3,i)=e((hiuiσi)ZJ,Y1s1)⋅e(Viy1ZJ,gs2)e((hiuixi)s1Vis2,Y1ZJ)=e(ui,g)y1s1ZJ(σi−xi)=1, when σi=xi.

Step 2.

When number(xi=σi)≥t holds except for * bits, chooses t elements of S satisfying xi=σi. So we have

C5/∏i∈S[e(C1,K1,J)e(C3,i,K2,J)⋅e(C4,i,K3,J)⋅e(C2,K4,J)]AJ→M,

where AJ is the Lagrange coefficient for i and S: AJ(x)=∏j∈S,j≠i[(x−j)/(i−j)].

5  Security Proof

5.1 Overview

If the DBDH and ADLIN assumptions are met, the VDTSE scheme is selectively secure. The adversary chooses two vectors x→0∗=(x0,1∗,…,x0,ℓ∗) and x→1∗=(x1,1∗,…,x1,ℓ∗)∈Σℓ that are transformed from vectors X→0∗,X→1∗ at the beginning of this security game. We assume that A={1,2,…,|A|}, where A is the set of indexes i that satisfies A={i∈{1,…,ℓ}∣x0,i∗≠x1,i∗}. We continue to choose random elements (R3,1,…,R3,∣A∣, R4,1,…,R4,∣A∣) from G and R5 from GT. We assume the following games:

Game0:CT0=(C1,C2,C3,1,…,C3,∣A∣,C3,∣A∣+1,…,C3,ℓ,C4,1,…,C4,∣A∣,C4,∣A∣+1,…,C4,ℓ,C5),

Game1:CT1=(C1,C2,C3,1,…,C3,∣A∣,C3,∣A∣+1,…,C3,ℓ,C4,1,…,C4,∣A∣,C4,∣A∣+1,…,C4,ℓ,R5),

Game2,1:CT2,1=(C1,C2,R3,1,…,C3,∣A∣,C3,∣A∣+1,…,C3,ℓ,R4,1,…,C4,∣A∣,C4,∣A∣+1,…,C4,ℓ,R5),

⋮,

Game2,∣A∣:CT2,∣A∣=(C1,C2,R3,1,…,R3,∣A∣,C3,∣A∣+1,…,C3,ℓ,R4,1,…,R4,∣A∣,C4,∣A∣+1,…,C4,ℓ,R5).

When the adversary sends M0,M1, the challenger provides the ciphertext about (x→β∗,Mβ) to the adversary, where β∈{0,1}. If the adversary guesses β correctly, he will win the game. Game0 is the real security game that is given to the adversary. In this game, C3,1,…,C3,ℓ,C4,1,…,C4,ℓ are the ciphertext about x→β∗, and C5 is the ciphertext about Mβ. CT2,∣A∣ is the challenge ciphertext of Game2,∣A∣, which reveals nothing about the attributes associated with A or message Mβ. We show this in the following games, which are all computationally indistinguishable.

5.2 Type of Trapdoor Queries

In our model (the selective security), the adversary performs trapdoor queries for any vector Δ→=(Δ1, …,ΔJ,…,Δℓ/U) and a threshold t transformed to vector σ→=(σ1,…,σℓ)∈(Σ∗)ℓ and t, under the constraint that fΔ→,t(X→0∗)=fΔ→,t(X→1∗) (i.e., fσ→,t(x→0∗)=fσ→,t(x→1∗)). We assume S is the set of i for which σi is not a wildcard. We divide the queries into two types:

• Type 1. [number(X0,J>ΔJ)≥t]∧[number(X1,J>ΔJ)≥t] (i.e., [number(σi=x0,i∗)≥t]∧ [number (σi=x1,i∗)≥t]). If the challenge message meets M0=M1, this type of query can be performed.

• Type 2. [number(X0,J>ΔJ<t]∧[number(X1,J>ΔJ)<t] (i.e., [number(σi=x0,i∗)<t]∧ [number(σi) =x1,i∗)<t].

Case 1. Type 1 does not match. Additionally, there is an index i∈S∩A for which σi≠xβ,i∗.

Case 2. Type 1 and Case 1 fail to hold, and there exist i∈S∩A for which σi=xβ,i∗, while there exists j∈S for which σi≠xβ,i∗.

5.3 Proof of Lemmas

Lemma 1. Suppose that the DBDH assumption holds. In other words, the distinct difference in the advantage of 𝒜 who is an adversary of any polynomial time in Game0 and Game1 is negligible.

Proof. Suppose 𝒜 has a non-negligible difference about the advantage of G. If Z=e(g,g)abc holds for a random instance (g,ga,gb,gc,Z), ℬ returns 1, otherwise, ℬ returns 0. ℬ communicates with 𝒜 in the following ways:

• Init. At the start of the game, 𝒜 produces two vectors X→0∗,X→1∗ that have been converted to x→0∗,x→1∗∈Σℓ. ℬ internally changes β∈{0,1}.

• Setup. ℬ selects exponents at random γ, y1,v1,…,vℓ, t1,…, tℓ, θ1,…,θℓ, ϕ1,…,ϕℓ, λ1,…,λℓ\break∈Zp. It sets Y1=gy1, hi=gθi(gb)−ϕi⋅xβ,i∗,ui=(gb)ϕi,wi=gλi,Vi=gvi,Ti=gti. Besides, ℬ establishes Ω = e(g1,Y1) =e(ga, gb)y1e(g, g)γy1. Take note that g1=gabgγ, and this is secret to ℬ. 𝒜 is handed the public key PK=(g, Y1, (h1, u1, w1, V1, T1),…,(hℓ, uℓ, wℓ, Vℓ, Tℓ), Ω).

• Query Phase 1. 𝒜 triggers the trapdoor queries. Assume 𝒜 searches for Δ→ that has been changed to σ→=(σ1,…,σℓ)∈(Σ∗)ℓ. Let S={i|σi≠∗}, where * is a wildcard. The queries of 𝒜 are divided into the following two types.

Type 1. 𝒜 sends a Type 1 query, and ℬ answers an arbitrary guess. The query above shows that M0=M1, and ℬ provides the message’s encryption. Since in this circumstance the two games, Game0 and Game1, are identical, there ought to be no difference in 𝒜’s advantage.

Type 2. These two scenarios imply that there exists at least one index j∈S that satisfies σj≠xβ,j∗. ℬ initially defines the three sets, Γ, Γ′, S, as follows: Γ={i∣σi=xβ,i∗}, Γ′ is any set such that Γ⊆Γ′⊆S and |Γ′|=t−1, and S=Γ′∪{0}. Following that, ℬ specifies the trapdoor KJ, where J=(i−ΔJ)/U+1. ℬ selects a random t-1 degree polynomial q(x) by randomly selecting its value for the t-1 points and having q(0)=ab+γ.

If i∈Γ′, ℬ chooses a random rJ,ηJ∈Zp,q(J)=τJ.

K1,J=gq(J)(hiuiσi)rJwiηJ=(g)τJ+θi+λiηJ(gb)rJ(σi−xβ, i∗)ϕi,

K2,J=Y1rJ=(g)y1rJ,

K3,J=Y1ηJ=(g)y1ηJ,

K4,J=Y1−(rJvi+ηJti)=(g)−y1(rJvi+ηJti),

K5,J=Viy1ZJ=(g)y1viZJ,

K6,J=Y1ZJ=(g)y1ZJ,

K7,J=(hiuiσi)ZJ=((g)θi(gb)(σi−xβ,i∗)ϕi)ZJ

If i∈S−Γ′:σi−xβ,i∗≠0, q(J)=Σi∈Γ′q(J)ΔJ+q(0)Δ0,rJ=(r~J−a/[(σi−xβ,i∗)ϕi])Δ0.

K1,J=gq(J)(hiuiσi)rJwiηJ=gΣi∈Γ′q(J)ΔJ+q(0)Δ0((g)θi(gb)(σi−xβ,i∗)ϕi)rJ(gλi)ηJ

=(g)Σi∈Γ′q(J)ΔJg(ab+γ)Δ0((g)θi(gb)(σi−xβ,i∗)ϕi)(r~J−a/[(σi−xβ,i∗)ϕi])Δ0(gλi)ηJ

=(g)Σi∈Γ′q(J)ΔJ+γΔ0gabΔ0(g)θir~JΔ0(ga)(θi/[(σi−xβ,i∗)ϕj])Δ0(gb)(σi−xβ,i∗)ϕir~JΔ0(g−abΔ0)(gλi)ηJ

=(g)Σi∈Γ′q(J)ΔJ+γΔ0+θir~JΔ0+λiηJ(ga)(θi/[(σi−xβ,i∗)ϕj])Δ0(gb)(σi−xβ,i∗)ϕir~JΔ0,

K2,J=Y1rJ=(gy1)(r~J−a/[(σi−xβ,i∗)ϕi])Δ0=(g)y1r~JΔ0(ga)−(y1Δ0)/[(σi−xβ,i∗)ϕi],

K3,J=Y1ηJ=(g)y1ηJ,

K4,J=Y1−(rJvi+ηJti)=(gy1)−((r~J−a/[(σi−xβ,i∗)ϕi])Δ0vi+ηJti)=(g)−y1(r~JΔ0vi+ηJti)(ga)(y1Δ0vi)/(σi−xβ,i∗)ϕi,

K5,J=Viy1ZJ=(g)y1viZJ,

K6,J=Y1ZJ=(g)y1ZJ,

K7,J=(hiuiσi)ZJ=((g)θi(gb)(σi−xβ,i∗)ϕi)ZJ=(g)θiZJ(gb)(σi−xβ,i∗)ϕiZJ.

• Challenge. 𝒜 sends M0 and M1 to ℬ. If M0=M1, ℬ finishes the game and guesses β′∈{0,1}. Otherwise, ℬ chooses s1,s2∈Zp randomly and generates the challenge ciphertext CT∗, where s1=c.

C1∗=Y1s1=(gy1)c=(gc)y1,

C2∗=gs2=(g)s2,

C3,1∗=(h1u1xβ,1∗)s1V1s2=((g)θ1(gb)(xβ,1∗−xβ,1∗)ϕ1)cgv1s2=(gc)θ1(gv1)s2,…,

C3,i∗=(hiuixβ,i∗)s1Vis2=(gc)θi(g)vis2,…,

C3,ℓ∗=(hℓuℓxβ,ℓ∗)s1Vℓs2=(gc)θℓ(g)vℓs2,

C4,1∗=w1s1T1s2=(gλ1)c(gt1)s2=(gc)λ1(g)t1s2,…,

C4,i∗=wis1Tis2=(gc)λi(g)tis2,…,

C4,ℓ∗=wℓs1Tℓs2=(gc)λℓ(g)tℓs2,

C5∗=e(g1,Y1)s1Mβ=e(gab+γ,gy1)cMβ=Ze(gc,g)y1γMβ,

where Z=e(g,g)abc.

• Query Phase 2. 𝒜 carries on issuing questions that were not asked in Query Phase 1. ℬ reacts the same way as previously.

• Guess. For the challenge ciphertext, 𝒜 provides a guess β′∈{0,1}. If β′=β, ℬ returns 1, else ℬ returns 0.

ℬ’s advantage in solving the DBDH problem is related to 𝒜’s advantage of distinguishing Game0 and Game1. Allow Game1 = Game2, 0, and the following lemma is true for j=0,1,…,|A|−1.

Lemma 2. Suppose that the ADLIN assumption is true. In other words, the difference in the advantage of 𝒜 in Game2, j and Game2, j + 1 is negligible for every polynomial time adversary 𝒜.

Proof. Consider 𝒜 with a non-negligible difference ε about its advantage between Game2, j and Game2, j + 1. We hope to create an algorithm in which ℬ employs 𝒜’s ability to work out the ADLIN issue in G. Given (g,gz1,gz2,gz22,gz2/z1,gz22z3,gz4,Z)∈G8, ℬ outputs 1 when Z=gz1(z3+z4), otherwise ℬ generates 0. ℬ communicates with 𝒜 using the subsequent process: