# Efficient KDM-CCA Secure Public-Key Encryption via Auxiliary-Input Authenticated Encryption

Authors: Shuai Han; Shengli Liu; Lin Lyu
Journal: Security and Communication Networks
 (2017)

---

## Abstract

KDM[F]-CCA security of public-key encryption (PKE) ensures the privacy of key-dependent messages f(sk) which are closely related to the secret key sk, where f∈F, even if the adversary is allowed to make decryption queries. In this paper, we study the design of KDM-CCA secure PKE. To this end, we develop a new primitive namedAuxiliary-Input Authenticated Encryption (AIAE). ForAIAE, we introduce two related-key attack (RKA) security notions, includingIND-RKA andweak-INT-RKA. We present a generic construction ofAIAE from tag-based hash proof system (HPS) and one-time secure authenticated encryption (AE) and give an instantiation ofAIAE under the Decisional Diffie-Hellman (DDH) assumption. UsingAIAE as an essential building block, we give two constructions of efficient KDM-CCA secure PKE based on the DDH and the Decisional Composite Residuosity (DCR) assumptions. Specifically, (i) our first PKE construction is the first one achieving KDM[Faff]-CCA security for the set of affine functions and compactness of ciphertexts simultaneously. (ii) Our second PKE construction is the first one achieving KDM[Fpolyd]-CCA security for the set of polynomial functions and almost compactness of ciphertexts simultaneously. Our PKE constructions are very efficient; in particular, they are pairing-free and NIZK-free.


---

## Body

## 1. Introduction

For public-key encryption (PKE) schemes, Chosen-Ciphertext Attack (CCA) security is the de facto security notion. In the CCA security model, the adversary sees the public key and gets challenge ciphertexts, which are encryptions of messages of its choices. It is also allowed to make decryption queries and obtain the decrypted messages for ciphertexts (but not the challenge ciphertexts) of its choices. CCA security considers whether the challenge ciphertexts can protect the security of messages. Observe that the adversary does not know the secret keys; thus it is not able to submit messages that are closely related to the secret keys. Thus, there is a corner that is not covered by CCA security, that is, the security of messages which are closely dependent on the secret keys. It was Goldwasser and Micali [1] who first pointed out this problem. In 2002, the security of such key-dependent messages (KDM) was formalized by Black et al. [2]. Up to now, KDM-security has found many applications, such as anonymous credential systems [3] and hard disk encryption [4].KDM[F]-security means KDM-security for a set F of functions. Loosely speaking, in the n-KDM[F]-security model, the adversary obtains public keys (pk1,…,pkn) of n users and has access to an encryption oracle. Each time, the adversary submits a function f in the function set F, the encryption oracle will encrypt f(sk1,…,skn) or a dummy message (say 0) and output the challenge ciphertext to the adversary. The n-KDM[F]-CPA security stipulates that the adversary cannot distinguish the two cases, and the n-KDM[F]-CCA security demands the indistinguishability of the two cases even if the adversary is also allowed to make decryption queries. KDM-CCA is obviously stronger than KDM-CPA security notion. Moreover, the KDM-security is stronger when the function set F is larger.KDM
[
F
]
-CPA Security. In 2008, Boneh et al. (BHHO) [4] proposed the first KDM[Faff]-CPA secure PKE construction for the affine function set Faff, from the Decisional Diffie-Hellman (DDH) assumption. Soon after, the BHHO scheme was generalized by Brakerski and Goldwasser [5], who presented KDM[Faff]-CPA secure PKE constructions under the Quadratic Residuosity (QR) assumption or the Decisional Composite Residuosity (DCR) assumption. However, these schemes suffer from incompact ciphertext, which contains O(λ) group elements (λ denotes the security parameter throughout the paper).Applebaum et al. [6] proved that a variant of the Regev scheme [7] is KDM[Faff]-CPA secure and enjoys compact ciphertexts, that is, encompassing only O(1) group elements.Brakerski et al. [8] provided a KDM[Fpolyd]-CPA secure PKE scheme for the polynomial function set Fpolyd, which contains all polynomials whose degrees are at most d. The drawback of the scheme is incompact ciphertext, which contains O(λd+1) group elements.Barak et al. [9] presented a KDM-CPA secure PKE for the set of Boolean circuits whose sizes are a priori bounded, which is a very large function set. Nevertheless, their scheme is neither practical nor flexible.In 2011, Malkin et al. [10] proposed the first efficient KDM[Fpolyd]-CPA secure PKE. The ciphertext of their PKE construction is almost compact and consists of only O(d) group elements.KDM
[
F
]
-CCA Security. The first approach to KDM-CCA security was proposed by Camenisch, Chandran, and Shoup (CCS) [11]. The CCS approach follows the Naor-Yung paradigm [12], and the building blocks are a PKE scheme with CCA security, a PKE scheme with KDM-CPA security, and a noninteractive zero-knowledge (NIZK) proof system which proves that the two PKE schemes encrypt the same message.The Groth-Sahai proofs [13] are the only practical NIZK. To obtain efficient KDM-CCA secure PKE, we have to employ an efficient PKE scheme with KDM-CPA security and the Groth-Sahai proofs if we follow the CCS approach [11]. Unfortunately, the existing efficient PKE schemes with KDM-CPA security, like [6, 10], are not compatible with the Groth-Sahai proofs, since the underlying groups of their schemes are not pairing-friendly ones.Galindo et al. [14] proposed a KDM-CCA secure PKE scheme from the Matrix Decisional Diffie-Hellman assumption. Their scheme enjoys compact ciphertexts, but the KDM-CCA security of their scheme is constrained (more precisely, in their KDM-CCA security model, the adversary is only allowed to have access to the encryption oracle for a number of times linear in the secret key’s size).In order to achieve both KDM-CCA security and efficiency for PKE, Hofheinz [15] developed another approach, making use of a novel primitive named “lossy algebraic filter.” The PKE scheme proposed by Hofheinz enjoys the security of KDM[Fcirc]-CCA and the compactness of ciphertexts simultaneously, but the function set Fcirc is made up of constant functions and selection functions f(sk1,…,skn)=ski.In fact, it is a challenging job to enlarge the KDM-CCA function setF while keeping the efficiency of the PKE scheme. Recently, Lu et al. [16] designed the first PKE achieving both KDM[Faff]-CCA security and compact ciphertexts. Their construction is referred to as the LLJ scheme in this paper. The essential building block in their scheme is “authenticated encryption” (AE¯). The so-called INT-Faff-RKA security of AE¯ turns out to be critical to the KDM[Faff]-CCA security of the LLJ scheme. Unfortunately, their security reduction of the INT-Faff-RKA security of AE¯ to the underlying DDH assumption is flawed. Roughly speaking, the problem of their security reduction is that there is no efficient way for the DDH adversary to convert the forgery provided by the INT-Faff-RKA adversary to a decision bit for solving the DDH problem, since it has no trapdoor. See our conference version [17] for details. The failure of AE¯’s INT-Faff-RKA security reduction directly affects the validity of LLJ’s KDM[Faff]-CCA security proof.To construct efficient KDM[Fpolyd]-CCA secure PKE schemes, the CCS approach [11] is the unique way, to the best of our knowledge. However, the only efficient KDM[Fpolyd]-CPA secure PKE [10] is incompatible with the Groth-Sahai NIZK proofs [13]; thus the CCS approach must adopt a general inefficient NIZK.Our Contribution. In this work, we focus on the design of efficient PKE schemes possessing KDM[Faff]-CCA security and KDM[Fpolyd]-CCA security, respectively.(i)
We develop a new primitive named“Auxiliary-Input Authenticated Encryption” (AIAE). We introduce new related-key attack (RKA) security notions for it, calledIND-F′-RKA andweak-INT-F′-RKA.
(a)
We show a general paradigm for constructing such anAIAE from a one-time secure AE and atag-based hash proof system (HPS) that is universal2, extracting, and key-homomorphic.(b)
We present an instantiation of tag-based HPS under the DDH assumption. Following our paradigm, we immediately obtain a DDH-basedAIAE for the set of restricted affine functions.(ii)
UsingAIAE as an essential building block, we design the first PKE scheme enjoying KDM[Faff]-CCA security and compactness of ciphertexts simultaneously. Specifically, the ciphertext of our scheme contains only O(1) group elements.(iii)
Furthermore, we design the first PKE scheme enjoying KDM[Fpolyd]-CCA security and almost compactness of ciphertexts simultaneously. More precisely, the number of group elements contained in a ciphertext is independent of the security parameter λ.In Table1, we list the existing PKE schemes which either achieve KDM-CCA security or are KDM-secure for the set Fpolyd of polynomial functions.Table 1
Comparison among PKE schemes achieving either KDM-CCA security or security against the setFpolyd of polynomial functions. Here, we denote by λ the security parameter and by Fcirc, Faff, and Fpolyd the set of selection functions, the set of affine functions, and the set of polynomial functions of bounded degree d, respectively. “CCA” indicates that the scheme is KDM-CCA secure. By the symbol “?”, we mean that the security proof is not rigorous. G, ZN2, ZN3, ZNs, and ZN- are the underlying groups, where s≥1.
Scheme
Set
CCA?
Free of pairing?
The size of ciphertext
Assumption
BHHO08 [4] + CCS09 [11]
F
a
f
f
√
—
(
6
λ
+
13
)
|
G
|
DDH
BGK11 [8]
F
p
o
l
y
d
—
√
(
λ
d
+
1
)
|
G
|
DDH or LWE
MTY11 [10]
F
p
o
l
y
d
—
√
(
d
+
2
)
|
Z
N
s
|
DCR
Hof13 [15]
F
c
i
r
c
√
—
6
|
Z
N
3
| + 49|G|
DDH & DCR
LLJ15 [16]
F
a
f
f
?
√
3
|
Z
N
2
| + 3|ZNs| + |ZN-|
DDH & DCR
Our scheme in Section4
F
a
f
f
√
√
9
|
Z
N
2
| + 9|ZNs| + 2|ZN-|
DDH & DCR
Our scheme in Section5
F
p
o
l
y
d
√
√
9
|
Z
N
2
| + (8d9+1)|ZNs| + 2|ZN-|
DDH & DCROverview of Our Construction. In the construction of our KDM-CCA secure PKE schemes, we adopt a key encapsulation mechanism (KEM) + data encapsulation mechanism (DEM) approach [18] and employ three building blocks:KEM, E, andAIAE, as shown in Figure 1.(i)
KEM and E share the same pair of public and secret keys.(ii)
A keyk is encapsulated byKEM.Encrypt, and an encapsulationkem.c is generated byKEM.Encrypt along the way.(iii)
The messagem is encrypted by E.Encrypt, and the resulting E-ciphertext is E.c.(iv)
The keyk generated byKEM is used byAIAE.Encrypt to encrypt E.c with auxiliary input ai≔kem.c, and the resultingAIAE-ciphertext isaiae.c.(v)
The ciphertext of our PKE scheme is (kem.c,aiae.c).Figure 1
Our approach of PKE construction.Following this approach, we design KDM[Faff]-CCA and KDM[Fpolyd]-CCA secure PKE schemes, respectively, by constructing specific building blocks.Differences to Conference Version. This paper constitutes an extended full version of [17]. The new results in this paper are as follows.(i)
In contrast to presenting a concrete construction ofAIAE in the conference paper, we give a general paradigm for constructingAIAE from a one-time secure authenticated encryption (AE) and atag-based hash proof system (HPS) in this paper.
(a)
In Section3.2, we show that the resultingAIAE is IND-RKA secure and weak-INT-RKA secure, as long as the underlying tag-based HPS is universal2, extracting, and key-homomorphic.(b)
In Section3.3, we give an instantiation of tag-based HPS based on the DDH assumption. Following our paradigm, we obtain a DDH-basedAIAE scheme in Section 3.4.We view the specificAIAE proposed in the conference paper as an instantiation of the general paradigm presented in this paper.(ii)
In this paper, we provide the full proofs of the theorems regarding the KDM[Faff]-CCA security and KDM[Fpolyd]-CCA security of our PKEs. Compared with the conference paper, we add the proofs of Lemmas 16, 18, 25, 26, and 29, and the proof of indistinguishability between Hybrids  2 and 3 in Section 5.3.


## 2. Preliminaries

Throughout this paper, denote byλ∈N the security parameter. y←$Y means choosing an element y from set Y uniformly. y←$A(x;r) means executing algorithm A with input x and randomness r and assigning output to y. We sometimes abbreviate this to y←$A(x). “PPT” is short for probabilistic polynomial-time. For integers n<m, we denote [n]≔{1,2,…,n} and [n,m]≔{n,n+1,…,m}. For a security notion YY and a primitive XX, the advantage of a PPT adversary A is typically denoted by AdvXX,AYY(λ) and we denote AdvXXYY(λ)≔maxPPTAAdvXX,AYY(λ). Letnegl(·) denote an unspecified negligible function.Games. We will use games in our security definitions and proofs. Typically, a gameG begins with aninitialize procedure and ends with afinalize procedure. In the game, there might be other procedures Proc1,…,Procn which perform as oracles. All procedures are presented with pseudocode, all sets are initialized as empty sets, and all variables are initialized as empty strings. In the execution of a gameG with an adversary A, firstly A callsinitialize and obtains its output; then A makes arbitrary oracle queries to Proci according to their specifications and obtains their outputs; finally A callsfinalize. In the end of the execution, iffinalize outputs b, then we write this as GA⇒b. The statement a=Gb means that, in gameG, a is computed as b or a equals b.


### 2.1. Public-Key Encryption

There are four PPT algorithmsPKE=(ParGen,KeyGen,Encrypt,Decrypt) in a public-key encryption (PKE) scheme:(i)
ParGen(1λ) outputs a public parameterpars. We assume thatpars implicitly defines a secret key space SK and a message space M.(ii)
KeyGen(pars) takespars as input and outputs a public keypk and a secret keysk.(iii)
Encrypt(pk,m) takespk and a message m∈M as input and outputs a ciphertextpke.c.(iv)
Decrypt(sk,pke.c) takessk and a ciphertextpke.c as input and outputs either a message m or a symbol ⊥ indicating the failure of the decryption.We requirePKE to have perfect correctness; that is, for all possible pars←$ParGen(1λ) and all m∈M, we have (1)Pr⁡pk,sk⟵$KeyGenpars:Decryptsk,Encryptpk,m=m=1.Definition 1 (KDM[F]-CCA security).
Letn∈N and let F denote a set of functions from (SK)n to M. A schemePKE is n-KDM[F]-CCA secure, if for any PPT adversary A, we have AdvPKE,Akdm-cca(λ)≔Prn-KDMF-CCAA⇒1-1/2≤negl(λ), where n-KDM[F]-CCA is the security game shown in Figure 2.Figure 2
n-KDM[F]-CCA security game.


### 2.2. Authenticated Encryption

There are three PPT algorithmsAE=(AE.ParGen,AE.Encrypt,AE.Decrypt) in an authenticated encryption (AE) scheme:(i)
AE.ParGen(1λ) generates a system parameter parsAE. We require parsAE to be an implicit input to other algorithms and assume that parsAE implicitly defines a key space KAE and a message space M.(ii)
AE.Encrypt(k,m) takes a key k∈KAE and a message m∈M as input and outputs a ciphertextae.c.(iii)
AE.Decrypt(k,ae.c) takes a key k∈KAE and a ciphertext ae.c as input and outputs a message m∈M or a symbol ⊥.We requireAE to have perfect correctness; that is, for all possible parsAE←$AE.ParGen(1λ), all keys k∈KAE, and all m∈M, (2)Pr⁡AE.Decryptk,AE.Encryptk,m=m=1.Definition 2 (one-time security).
A schemeAE is one-time secure (OT-secure), that is, IND-OT and INT-OT secure, if for any PPT A, both AdvAE,Aind-ot(λ)≔PrIND-OTA⇒1-1/2≤negl(λ) and AdvAE,Aint-ot(λ)≔Pr[INT-OTA⇒1]≤negl(λ), whereIND-OT andINT-OT are the security games presented in Figure 3.Figure 3
IND-OT (a) andINT-OT (b) security games.
(a)
(b)


### 2.3. Key Encapsulation Mechanism

There are three PPT algorithmsKEM=(KEM.KeyGen,KEM.Encrypt,KEM.Decrypt) in a key encapsulation mechanism (KEM):(i)
KEM.KeyGen(1λ) generates a public keypk and a secret keysk.(ii)
KEM.Encrypt(pk) takes pk as input and outputs a key k together with a ciphertextkem.c.(iii)
KEM.Decrypt(sk,kem.c) takes sk and a ciphertextkem.c as input and outputs either a key k or a symbol ⊥.We requireKEM to have perfect correctness; that is, for all possible (pk,sk)←$KEM.KeyGen(1λ), we have (3)Pr⁡k,kem.c⟵$KEM.Encryptpk:KEM.Decryptsk,kem.c=k=1.


### 2.4. Tag-Based Hash Proof System: Universal2, Extracting, and Key-Homomorphism

Tag-based hash proof system (HPS) was first defined in [19]. The definition is similar to extended HPS [20], but the universal2 property is slightly different.Definition 3 (tag-based hash proof system).
A tag-based hash proof systemTHPS=(THPS.Setup,THPS.Pub,THPS.Priv) is comprised of three PPT algorithms: (i)
THPS.Setup(1λ) outputs a parameterized instance parsTHPS, which implicitly defines (K,C,V,T, HK,PK,Λ(·),μ), where K,C,V,T,HK,PK are all finite sets with V⊆C, Λ(·):C×T→K is a set of hash functions indexed by hk∈HK, and μ:HK→PK is a function. We assume that μ is efficiently computable, and there are PPT algorithms sampling hk←$HK uniformly, sampling C←$C uniformly, sampling C←$V uniformly with a witness w, and checking membership in C.(ii)
THPS.Pub(pk,C,w,t) takes a projection key pk=μ(hk)∈PK, an element C∈V with a witness w, and a tag t∈T as input and outputs a hash value K=Λhk(C,t)∈K.(iii)
THPS.Priv(hk,C,t) takes a hashing key hk∈HK, an element C∈C, and a tag t∈T as input and outputs a hash value K=Λhk(C,t)∈K without knowing a witness.
We requireTHPS to beprojective; that is, for all parsTHPS←$THPS.Setup(1λ), all hk∈HK and pk=μ(hk)∈PK, all C∈V with all witnesses w and all t∈T, it holds that (4)THPS.Pubpk,C,w,t=ΛhkC,t=THPS.Privhk,C,t.Tag-based HPS is associated with a subset membership problem. Informally speaking, it asks to distinguish the uniform distribution overV from the uniform distribution over C∖V.Definition 4 (SMP).
The Subset Membership Problem (SMP) related toTHPS is hard, if for any PPT adversary A, one has (5)AdvTHPS,Asmpλ≔PrAparsTHPS,C=1-PrAparsTHPS,C′=1≤neglλ,where parsTHPS←$THPS.Setup(1λ), C←$V, and C′←$C∖V.Definition 5 (universal2).
T
H
P
S is called (strongly) universal2, if for all possible parsTHPS←$THPS.Setup(1λ), all pk∈PK, all C∈C, all C′∈C∖V, all t,t′∈T with t≠t′, and all K,K′∈K, it holds that(6)Pr⁡ΛhkC′,t′=K′∣μhk=pk,ΛhkC,t=K=1K,where the probability is over hk←$HK.The key difference between tag-based HPS and extended HPS lies in the definition of theuniversal2 property [19]. Extended HPS requires (6) to hold for (C,t)≠(C′,t′), while tag-based HPS requires (6) to hold only for t≠t′. Hence, any (universal2) extended HPS is also a (universal2) tag-based HPS, but not vice versa. Tag-based HPS is essentially a weaker variant of extended HPS and admits more efficient constructions.Dodis et al. [21] defined an extracting property for extended HPS, which requires the hash value Λhk(C,t) to be uniformly distributed over K for any C∈C and t∈T, as long as hk is randomly chosen from HK. Besides, Xagawa [22] considered a key-homomorphic property for extended HPS, which stipulates that Λhk+Δ(C,t)=Λhk(C,t)·ΛΔ(C,t) holds for any hk,Δ∈HK, C∈C, and t∈T. Here we adapt these notions to tag-based HPS.Definition 6 (extracting).
T
H
P
S is called extracting, if for all parsTHPS←$THPS.Setup(1λ), all C∈C, all t∈T, and all K∈K, it holds that (7)Pr⁡ΛhkC,t=K=1K,where hk←$HK.Definition 7 (key-homomorphism).
T
H
P
S is calledkey-homomorphic, if for all parsTHPS←$THPS.Setup(1λ), which defines (K,C,V,T,HK,PK,Λ(·),μ), one has the following: (i)
Both(HK,+) and (K,·) are groups.(ii)
For allC∈C and all t∈T, the mapping Λ(·)(C,t):HK→K is a group homomorphism. That is, for all hk,b∈HK and all a∈Z, it holds that Λa·hk+b(C,t)=(Λhk(C,t))a·Λb(C,t).


### 2.5. DCR, DDH, DL, and IVd Assumptions

Suppose thatGenN(1λ) is a PPT algorithm generating (p,q,N,N¯), where p, q are safe primes of λ-bit, N=pq, and N¯=2N+1 is a prime. We define the following:(i)
QRN¯≔{a2modN¯∣a∈ZN¯}.ThenQRN¯ is a cyclic group of order N. For s∈N and T=1+N, we define(i)
QRNs≔{a2modNs∣a∈ZNs∗},(ii)
SCRNs≔{a2Ns-1modNs∣a∈ZNs∗},(iii)
RUNs≔{TrmodNs∣r∈[Ns-1]}.ThenSCRNs is a cyclic group of order ϕ(N)/4, and QRNs=SCRNs⊗RUNs, where ⊗ represents the internal direct product.Damgård and Jurik [23] showed that the discrete logarithm dlogT(u)∈[Ns-1] of an element u∈RUNs can be efficiently computed from u and N. Observe that ZNs∗=Z2⊗Z2′⊗SCRNs⊗RUNs; thus for any v=v(Z2)·v(Z2′)·v(SCRNs)·Tx∈ZNs∗, we have vϕ(N)=Tx·ϕ(N)∈RUNs and(8)dlogTvϕNϕNmodNs-1=x.Definition 8 (DCR assumption).
The Decisional Composite Residuosity (DCR) assumption holds forGenN and QRNs, if for any PPT A, it holds that(9)AdvGenN,Adcrλ≔Pr⁡AN,u=1-Pr⁡AN,v=1≤neglλ,where (p,q,N,N¯)←$GenN(1λ), u←$QRNs, and v←$SCRNs.The Interactive Vector (IVd) assumption is implied by the DCR assumption, as shown in [5]. Here we recall the IVd assumption according to [16].Definition 9 (IVd assumption).
TheIVd assumption holds for GenN and QRNs, if for any PPT A, it holds that(10)AdvGenN,Aivdλ≔Pr⁡AChalIVdbN,g1,…,gd=b-12≤neglλ,where (p,q,N,N¯)←$GenN(1λ), g1,…,gd←$SCRNs, b←${0,1}, and A is allowed to query the oracle ChalIVdb(·) adaptively. Each time, A can submit (δ1,…,δd) to the oracle, and ChalIVdb(δ1,…,δd) selects r←$[⌊N/4⌋] randomly: if b=0, the oracle outputs (g1r,…,gdr) to A; otherwise it outputs (g1rTδ1,…,gdrTδd) to A, where T=1+N.Definition 10 (DDH assumption).
The DDH assumption holds forGenN and QRN¯, if for any PPT A, it holds that(11)AdvGenN,Addhλ≔Pr⁡AN,p,q,g1,g2,g1x,g2x=1-Pr⁡AN,p,q,g1,g2,g1x,g2y=1≤neglλ,where (p,q,N,N¯)←$GenN(1λ), g1,g2←$QRN¯, x,y←$ZN∖{0}.Definition 11 (DL assumption).
The Discrete Logarithm (DL) assumption holds forGenN and SCRNs, if for any PPT A, it holds that(12)AdvGenN,Adlλ≔Pr⁡AN,p,q,g,gx=x≤neglλ,where (p,q,N,N¯)←$GenN(1λ), g←$SCRNs, x←$[ϕ(N)/4].


### 2.6. Collision-Resistant Hashing

Definition 12 (collision-resistant hashing).
LetH={H:X→Y} be a set of hash functions. H is said to becollision-resistant, if for any PPT A, one has(13)AdvH,Acrλ≔Pr⁡H⟵$H,x,x′⟵$AH:x≠x′∧Hx=Hx′≤neglλ.


## 2.1. Public-Key Encryption

There are four PPT algorithmsPKE=(ParGen,KeyGen,Encrypt,Decrypt) in a public-key encryption (PKE) scheme:(i)
ParGen(1λ) outputs a public parameterpars. We assume thatpars implicitly defines a secret key space SK and a message space M.(ii)
KeyGen(pars) takespars as input and outputs a public keypk and a secret keysk.(iii)
Encrypt(pk,m) takespk and a message m∈M as input and outputs a ciphertextpke.c.(iv)
Decrypt(sk,pke.c) takessk and a ciphertextpke.c as input and outputs either a message m or a symbol ⊥ indicating the failure of the decryption.We requirePKE to have perfect correctness; that is, for all possible pars←$ParGen(1λ) and all m∈M, we have (1)Pr⁡pk,sk⟵$KeyGenpars:Decryptsk,Encryptpk,m=m=1.Definition 1 (KDM[F]-CCA security).
Letn∈N and let F denote a set of functions from (SK)n to M. A schemePKE is n-KDM[F]-CCA secure, if for any PPT adversary A, we have AdvPKE,Akdm-cca(λ)≔Prn-KDMF-CCAA⇒1-1/2≤negl(λ), where n-KDM[F]-CCA is the security game shown in Figure 2.Figure 2
n-KDM[F]-CCA security game.


## 2.2. Authenticated Encryption

There are three PPT algorithmsAE=(AE.ParGen,AE.Encrypt,AE.Decrypt) in an authenticated encryption (AE) scheme:(i)
AE.ParGen(1λ) generates a system parameter parsAE. We require parsAE to be an implicit input to other algorithms and assume that parsAE implicitly defines a key space KAE and a message space M.(ii)
AE.Encrypt(k,m) takes a key k∈KAE and a message m∈M as input and outputs a ciphertextae.c.(iii)
AE.Decrypt(k,ae.c) takes a key k∈KAE and a ciphertext ae.c as input and outputs a message m∈M or a symbol ⊥.We requireAE to have perfect correctness; that is, for all possible parsAE←$AE.ParGen(1λ), all keys k∈KAE, and all m∈M, (2)Pr⁡AE.Decryptk,AE.Encryptk,m=m=1.Definition 2 (one-time security).
A schemeAE is one-time secure (OT-secure), that is, IND-OT and INT-OT secure, if for any PPT A, both AdvAE,Aind-ot(λ)≔PrIND-OTA⇒1-1/2≤negl(λ) and AdvAE,Aint-ot(λ)≔Pr[INT-OTA⇒1]≤negl(λ), whereIND-OT andINT-OT are the security games presented in Figure 3.Figure 3
IND-OT (a) andINT-OT (b) security games.
(a)
(b)


## 2.3. Key Encapsulation Mechanism

There are three PPT algorithmsKEM=(KEM.KeyGen,KEM.Encrypt,KEM.Decrypt) in a key encapsulation mechanism (KEM):(i)
KEM.KeyGen(1λ) generates a public keypk and a secret keysk.(ii)
KEM.Encrypt(pk) takes pk as input and outputs a key k together with a ciphertextkem.c.(iii)
KEM.Decrypt(sk,kem.c) takes sk and a ciphertextkem.c as input and outputs either a key k or a symbol ⊥.We requireKEM to have perfect correctness; that is, for all possible (pk,sk)←$KEM.KeyGen(1λ), we have (3)Pr⁡k,kem.c⟵$KEM.Encryptpk:KEM.Decryptsk,kem.c=k=1.


## 2.4. Tag-Based Hash Proof System: Universal2, Extracting, and Key-Homomorphism

Tag-based hash proof system (HPS) was first defined in [19]. The definition is similar to extended HPS [20], but the universal2 property is slightly different.Definition 3 (tag-based hash proof system).
A tag-based hash proof systemTHPS=(THPS.Setup,THPS.Pub,THPS.Priv) is comprised of three PPT algorithms: (i)
THPS.Setup(1λ) outputs a parameterized instance parsTHPS, which implicitly defines (K,C,V,T, HK,PK,Λ(·),μ), where K,C,V,T,HK,PK are all finite sets with V⊆C, Λ(·):C×T→K is a set of hash functions indexed by hk∈HK, and μ:HK→PK is a function. We assume that μ is efficiently computable, and there are PPT algorithms sampling hk←$HK uniformly, sampling C←$C uniformly, sampling C←$V uniformly with a witness w, and checking membership in C.(ii)
THPS.Pub(pk,C,w,t) takes a projection key pk=μ(hk)∈PK, an element C∈V with a witness w, and a tag t∈T as input and outputs a hash value K=Λhk(C,t)∈K.(iii)
THPS.Priv(hk,C,t) takes a hashing key hk∈HK, an element C∈C, and a tag t∈T as input and outputs a hash value K=Λhk(C,t)∈K without knowing a witness.
We requireTHPS to beprojective; that is, for all parsTHPS←$THPS.Setup(1λ), all hk∈HK and pk=μ(hk)∈PK, all C∈V with all witnesses w and all t∈T, it holds that (4)THPS.Pubpk,C,w,t=ΛhkC,t=THPS.Privhk,C,t.Tag-based HPS is associated with a subset membership problem. Informally speaking, it asks to distinguish the uniform distribution overV from the uniform distribution over C∖V.Definition 4 (SMP).
The Subset Membership Problem (SMP) related toTHPS is hard, if for any PPT adversary A, one has (5)AdvTHPS,Asmpλ≔PrAparsTHPS,C=1-PrAparsTHPS,C′=1≤neglλ,where parsTHPS←$THPS.Setup(1λ), C←$V, and C′←$C∖V.Definition 5 (universal2).
T
H
P
S is called (strongly) universal2, if for all possible parsTHPS←$THPS.Setup(1λ), all pk∈PK, all C∈C, all C′∈C∖V, all t,t′∈T with t≠t′, and all K,K′∈K, it holds that(6)Pr⁡ΛhkC′,t′=K′∣μhk=pk,ΛhkC,t=K=1K,where the probability is over hk←$HK.The key difference between tag-based HPS and extended HPS lies in the definition of theuniversal2 property [19]. Extended HPS requires (6) to hold for (C,t)≠(C′,t′), while tag-based HPS requires (6) to hold only for t≠t′. Hence, any (universal2) extended HPS is also a (universal2) tag-based HPS, but not vice versa. Tag-based HPS is essentially a weaker variant of extended HPS and admits more efficient constructions.Dodis et al. [21] defined an extracting property for extended HPS, which requires the hash value Λhk(C,t) to be uniformly distributed over K for any C∈C and t∈T, as long as hk is randomly chosen from HK. Besides, Xagawa [22] considered a key-homomorphic property for extended HPS, which stipulates that Λhk+Δ(C,t)=Λhk(C,t)·ΛΔ(C,t) holds for any hk,Δ∈HK, C∈C, and t∈T. Here we adapt these notions to tag-based HPS.Definition 6 (extracting).
T
H
P
S is called extracting, if for all parsTHPS←$THPS.Setup(1λ), all C∈C, all t∈T, and all K∈K, it holds that (7)Pr⁡ΛhkC,t=K=1K,where hk←$HK.Definition 7 (key-homomorphism).
T
H
P
S is calledkey-homomorphic, if for all parsTHPS←$THPS.Setup(1λ), which defines (K,C,V,T,HK,PK,Λ(·),μ), one has the following: (i)
Both(HK,+) and (K,·) are groups.(ii)
For allC∈C and all t∈T, the mapping Λ(·)(C,t):HK→K is a group homomorphism. That is, for all hk,b∈HK and all a∈Z, it holds that Λa·hk+b(C,t)=(Λhk(C,t))a·Λb(C,t).


## 2.5. DCR, DDH, DL, and IVd Assumptions

Suppose thatGenN(1λ) is a PPT algorithm generating (p,q,N,N¯), where p, q are safe primes of λ-bit, N=pq, and N¯=2N+1 is a prime. We define the following:(i)
QRN¯≔{a2modN¯∣a∈ZN¯}.ThenQRN¯ is a cyclic group of order N. For s∈N and T=1+N, we define(i)
QRNs≔{a2modNs∣a∈ZNs∗},(ii)
SCRNs≔{a2Ns-1modNs∣a∈ZNs∗},(iii)
RUNs≔{TrmodNs∣r∈[Ns-1]}.ThenSCRNs is a cyclic group of order ϕ(N)/4, and QRNs=SCRNs⊗RUNs, where ⊗ represents the internal direct product.Damgård and Jurik [23] showed that the discrete logarithm dlogT(u)∈[Ns-1] of an element u∈RUNs can be efficiently computed from u and N. Observe that ZNs∗=Z2⊗Z2′⊗SCRNs⊗RUNs; thus for any v=v(Z2)·v(Z2′)·v(SCRNs)·Tx∈ZNs∗, we have vϕ(N)=Tx·ϕ(N)∈RUNs and(8)dlogTvϕNϕNmodNs-1=x.Definition 8 (DCR assumption).
The Decisional Composite Residuosity (DCR) assumption holds forGenN and QRNs, if for any PPT A, it holds that(9)AdvGenN,Adcrλ≔Pr⁡AN,u=1-Pr⁡AN,v=1≤neglλ,where (p,q,N,N¯)←$GenN(1λ), u←$QRNs, and v←$SCRNs.The Interactive Vector (IVd) assumption is implied by the DCR assumption, as shown in [5]. Here we recall the IVd assumption according to [16].Definition 9 (IVd assumption).
TheIVd assumption holds for GenN and QRNs, if for any PPT A, it holds that(10)AdvGenN,Aivdλ≔Pr⁡AChalIVdbN,g1,…,gd=b-12≤neglλ,where (p,q,N,N¯)←$GenN(1λ), g1,…,gd←$SCRNs, b←${0,1}, and A is allowed to query the oracle ChalIVdb(·) adaptively. Each time, A can submit (δ1,…,δd) to the oracle, and ChalIVdb(δ1,…,δd) selects r←$[⌊N/4⌋] randomly: if b=0, the oracle outputs (g1r,…,gdr) to A; otherwise it outputs (g1rTδ1,…,gdrTδd) to A, where T=1+N.Definition 10 (DDH assumption).
The DDH assumption holds forGenN and QRN¯, if for any PPT A, it holds that(11)AdvGenN,Addhλ≔Pr⁡AN,p,q,g1,g2,g1x,g2x=1-Pr⁡AN,p,q,g1,g2,g1x,g2y=1≤neglλ,where (p,q,N,N¯)←$GenN(1λ), g1,g2←$QRN¯, x,y←$ZN∖{0}.Definition 11 (DL assumption).
The Discrete Logarithm (DL) assumption holds forGenN and SCRNs, if for any PPT A, it holds that(12)AdvGenN,Adlλ≔Pr⁡AN,p,q,g,gx=x≤neglλ,where (p,q,N,N¯)←$GenN(1λ), g←$SCRNs, x←$[ϕ(N)/4].


## 2.6. Collision-Resistant Hashing

Definition 12 (collision-resistant hashing).
LetH={H:X→Y} be a set of hash functions. H is said to becollision-resistant, if for any PPT A, one has(13)AdvH,Acrλ≔Pr⁡H⟵$H,x,x′⟵$AH:x≠x′∧Hx=Hx′≤neglλ.


## 3. Auxiliary-Input Authenticated Encryption

Our PKE constructions in Sections4 and 5 will resort to a new primitiveAIAE. To serve the KDM-CCA security of our PKE construction in Figure 1, ourAIAE should satisfy the following properties.(i)
AIAE must take an auxiliary inputai in both the encryption and decryption algorithms.(ii)
AIAE must have IND-F-RKA security and weak-INT-F-RKA security. Compared to the INT-F-RKA security proposed in [16], the weak-INT-F-RKA security imposes a special rule to determine whether the adversary’s forgery is successful or not.In the following, we present the syntax ofAIAE and define itsIND-F-RKA Security andWeak-INT-F-RKA Security. We also show a general paradigm of AIAE from tag-based HPS and give an instantiation of AIAE under the DDH assumption.


### 3.1. Auxiliary-Input Authenticated Encryption

Definition 13 (AIAE).
There are three PPT algorithmsAIAE=(AIAE.ParGen,AIAE.Encrypt,AIAE.Decrypt) in an AIAE scheme: (i)
The parameter generation algorithmAIAE.ParGen(1λ) generates a system parameter parsAIAE. We require parsAIAE to be an implicit input to other algorithms and assume that parsAIAE implicitly defines a key space KAIAE, a message space M, and an auxiliary-input space AI.(ii)
The encryption algorithmAIAE.Encrypt(k,m,ai) takes a key k∈KAIAE, a message m∈M, and an auxiliary input ai∈AI as input and outputs a ciphertext aiae.c.(iii)
The decryption algorithmAIAE.Decrypt(k,aiae.c,ai) takes a key k∈KAIAE, a ciphertext aiae.c, and an auxiliary input ai∈AI as input and outputs a message m∈M or a symbol ⊥.
We requireAIAE to have perfect correctness; that is, for all possible parsAIAE←$AIAE.ParGen(1λ), all keys k∈KAIAE, all messages m∈M, and all auxiliary-inputs ai∈AI, (14)Pr⁡AIAE.Decryptk,AIAE.Encryptk,m,ai,ai=m=1.In fact, AIAE is a generalization of traditional AE, and traditional AE can be viewed as AIAE withAI=∅.Definition 14 (RKA security).
Denote byF a set of functions from KAIAE to KAIAE. A scheme AIAE is IND-F-RKA secure and weak-INT-F-RKA secure, if for any PPT A, (15)AdvAIAE,Aind-rkaλ≔Pr⁡IND-F-RKAA⟹1-12≤neglλ,AdvAIAE,Aweak-int-rkaλ≔Prweak-INT-F-RKAA⟹1≤neglλ,whereIND-F-RKA andweak-INT-F-RKA are the security games presented in Figure 4.Figure 4
IND-F-RKA (a) andweak-INT-F-RKA (b) security games. We note that, in theweak-INT-F-RKA game, there is a special rule (as shown in the shadow) of outputting 0 infinalize.
(a)
(b)


### 3.2. Generic Construction of AIAE from Tag-Based HPS and OT-Secure AE

Our construction of AIAE needs the following ingredients.(i)
A tag-based hash proof systemTHPS=(THPS.Setup,THPS.Pub,THPS.Priv), where the hash value space is K, the tag space is T, and the hashing key space is HK.(ii)
A (traditional) authenticated encryption schemeAE=(AE.ParGen,AE.Encrypt,AE.Decrypt), where the message space is M and the key space is K.(iii)
A set of hash functionsH={H:{0,1}∗→T}.We present our AIAE constructionAIAE=(AIAE.ParGen,AIAE.Encrypt,AIAE.Decrypt) in Figure 5, whose key space is KAIAE≔HK, message space is M, and auxiliary-input space is AI≔{0,1}∗.Figure 5
Generic construction ofAIAE from THPS and AE.By the perfect correctness ofAE, it is routine to check that AIAE has perfect correctness.Theorem 15.
If (i)THPS is universal2, extracting, key-homomorphic and has a hard subset membership problem, (ii) AE is one-time secure, and (iii) H is collision-resistant, then the schemeAIAE in Figure 5 is IND-Fraff-RKA and weak-INT-Fraff-RKA secure. Here Fraff≔{fa,b:hk∈HK↦a·hk+b∈HK∣a∈Z|K|∗,b∈HK} is the set of restricted affine functions.Proof of Theorem15 (IND-
F
r
a
f
f
-RKA Security). Denote by A a PPT adversary who is against the IND-Fraff-RKA security and queriesencrypt oracle for at most Qe times. We show the IND-Fraff-RKA security through a series of games. For an event E, we denote by Prj[E], Prj′[E], and Prj′′[E] the probability of E occurring in games Gj, Gj′, and Gj′′, respectively.Game
G
1. It is the originalIND-Fraff-RKA game. Denote the event β′=β bySucc. According to the definition, AdvAIAE,Aind-rka(λ)=|Pr1[Succ]-1/2|.As for thelth (l∈[Qe])encrypt query (ml,0,ml,1,ail,fl), where fl=〈al,bl〉∈Fraff, the challenger prepares the challenge ciphertext as follows:(i)
pickCl←$V together with witness wl,(ii)
computetl≔H(Cl,ail)∈T,(iii)
computeκl≔Λal·hk+bl(Cl,tl)∈K,(iv)
invokeχl←$AE.Encrypt(κl,ml,β),and it outputs the challenge ciphertext〈Cl,χl〉 to A.Game
G
1
,
j
,
j
∈
[
Q
e
+
1
]. It is identical to G1, except that, for the first j-1 times ofencrypt queries, that is, l∈[j-1], the challenger chooses κl←$K randomly for the AE scheme.ClearlyG1,1 is identical to G1; thus Pr1[Succ]=Pr1,1[Succ].Game
G
1
,
j
′
,
j
∈
[
Q
e
]. It is identical to G1,j, except that, for the jthencrypt query, the challenger samples Cj←$C∖V uniformly.The difference betweenG1,j and G1,j′ lies in the distribution of Cj. In game G1,j, Cj is uniformly chosen from V; in game G1,j′, Cj is uniformly chosen from C∖V. Any difference between G1,j and G1,j′ results in a PPT adversary solving the subset membership problem related toTHPS; thus we have that |Pr1,j[Succ]-Pr1,j′[Succ]|≤AdvTHPSsmp(λ).Game
G
1
,
j
′
′
,
j
∈
[
Q
e
]. It is identical to G1,j′, except that, for the jthencrypt query, the challenger chooses κj←$K randomly.Lemma 16.
For allj∈[Qe], Pr1,j′[Succ]=Pr1,j′′[Succ].Proof.
For gameG1,j′ and game G1,j′′, the difference between them lies in the computation of κj in the jthencrypt query. In G1,j′, κj is properly computed, while in G1,j′′, it is chosen from K uniformly.
We analyze the information about the keyhk that is used in game G1,j′.(i)
For thelth (l∈[j-1]) query,encrypt does not usehk at all since κl is randomly chosen from K.(ii)
For thelth (l∈[j+1,Qe]) query,encrypt can use pk=μ(hk) to compute κl:(16)κl=Λal·hk+blCl,tl:Cl⟵$Vwithwitnesswl=ΛhkCl,tlal·ΛblCl,tl:via  key-homomorphism=THPS.Pubpk,Cl,wl,tlal·ΛblCl,tl:via  projective  property.(iii)
For thejth query,encrypt uses Λhk(Cj,tj) to compute κj:(17)κj=Λaj·hk+bjCj,tj:Cj⟵$C∖V=ΛhkCj,tjaj·ΛbjCj,tj:via  key-homomorphism.
SinceCj∈C∖V, by the universal2 property ofTHPS, Λhk(Cj,tj) is uniformly distributed over K conditioned on pk=μ(hk). Then as long as aj∈Z|K|∗, κj=(Λhk(Cj,tj))aj·Λbj(Cj,tj) is also randomly distributed over K. Consequently, G1,j′ is essentially the same as G1,j′′, and Pr1,j′[Succ]=Pr1,j′′[Succ].Now, we show that gameG1,j′′ is computationally indistinguishable from game G1,j+1, j∈[Qe]. Note that the divergence between G1,j′′ and G1,j+1 lies in the distribution of Cj in the jthencrypt query. In game G1,j′′, Cj is uniformly chosen from C∖V; in game G1,j+1, Cj is uniformly chosen from V. Any difference between these two games results in a PPT adversary solving the subset membership problem related toTHPS; thus we have that |Pr1,j′′[Succ]-Pr1,j+1[Succ]|≤AdvTHPSsmp(λ).Game
G
2. It is identical to G1,Qe+1, except that when answeringencrypt queries, the challenger invokes χl←$AE.Encrypt(κl,0|ml,0|).In gameG1,Qe+1, the challenger computes χl←$AE.Encrypt(κl,ml,β); in game G2, the challenger computes χl←$AE.Encrypt(κl,0|ml,0|). Since each κl is chosen from K uniformly at random, l∈[Qe], by a standard hybrid argument, any difference between G1,Qe+1 and G2 results in a PPT adversary against the IND-OT security of AE, so that |Pr1,Qe+1[Succ]-Pr2[Succ]|≤Qe·AdvAEind-ot(λ).Finally, in gameG2, since the challenge ciphertexts are encryptions of 0|ml,0|, hence β is perfectly hidden to A. So Pr2[Succ]=1/2.Summing up, we proved the IND-Fraff-RKA security.This completes the proof of Theorem15 (IND-Fraff-RKA security).Proof of Theorem15 (Weak-INT-
F
r
a
f
f
-RKA Security). Denote by A a PPT adversary who is against the weak-INT-Fraff-RKA security and queriesencrypt oracle for at most Qe times. Similarly, the proof goes through a series of games, which are defined analogously, just like those games of the previous proof.Game
G
0. It is the originalweak-INT-Fraff-RKA game.As for thelth (l∈[Qe])encrypt query (ml,ail,fl), the challenger computes the challenge ciphertext 〈Cl,χl〉 in similar steps as the previous proof and outputs 〈Cl,χl〉 to A. Moreover, the challenger will put (ail,fl,〈Cl,χl〉) to a set QENC, put (ail,fl) to a set QAI-F, and put (Cl,ail,tl) to a set QTAG. In the end, the adversary outputs a forgery (ai∗,f∗,〈C∗,χ∗〉), where f∗=〈a∗,b∗〉, and the challenger invokes thefinalize procedure as follows:(i)
If(ai∗,f∗,〈C∗,χ∗〉)∈QENC, output 0.(ii)
If∃(ail,fl)∈QAI-F such that ail=ai∗ but fl≠f∗, output 0.(iii)
IfC∗∉C, output 0.(iv)
Computet∗≔H(C∗,ai∗)∈T and κ∗≔Λa∗·hk+b∗(C∗,t∗)∈K.Output(AE.Decrypt(κ∗,χ∗)≠⊥).Denote the event thatfinalize outputs 1 byForge. According to the definition, AdvAIAE,Aweak-int-rka(λ)=Pr0[Forge].Game
G
1. It is identical to G0, except that the following rule is added to the procedurefinalize by the challenger:(i)
If∃(Cl,ail,tl)∈QTAG such that tl=t∗ but (Cl,ail)≠(C∗,ai∗), output 0.Sincetl=H(Cl,ail) and t∗=H(C∗,ai∗), any difference between G0 and G1 implies a hash collision of H. So |Pr0[Forge]-Pr1[Forge]|≤AdvHcr(λ).Game
G
1
,
j
,
j
∈
[
Q
e
+
1
]. It is identical to G1, except that, for the first j-1 times ofencrypt queries, that is, l∈[j-1], the challenger chooses κl←$K uniformly for theAE scheme.ClearlyG1,1 is identical to G1; thus Pr1[Forge]=Pr1,1[Forge].Game
G
1
,
j
′
,
j
∈
[
Q
e
]. It is identical to G1,j, except that, for the jthencrypt query, the challenger samples Cj←$C∖V uniformly.The difference betweenG1,j and G1,j′ lies in the distribution of Cj. In game G1,j, Cj is uniformly chosen from V; in game G1,j′, Cj is uniformly chosen from C∖V. Any difference between these two games results in a PPT adversary solving the subset membership problem related toTHPS. We emphasize that the PPT adversary (simulator) is able to check the occurrence ofForge in an efficient way, because the keyhk can be chosen by the simulator itself. Consequently, the difference between G1,j and G1,j′ can be reduced to the subset membership problem smoothly.Lemma 17.
For allj∈[Qe], |Pr1,j[Forge]-Pr1,j′[Forge]|≤AdvTHPSsmp(λ).Proof.
To bound the difference betweenG1,j and G1,j′, we build an efficient adversary B solving the subset membership problem. Given (parsTHPS,C), where parsTHPS←$THPS.Setup(1λ), B aims to distinguish C←$V from C←$C∖V.
B simulates G1,j or G1,j′ for A. Firstly, B invokes parsAE←$AE.ParGen(1λ), picks H←$H randomly, and sends parsAIAE≔(parsTHPS,parsAE,H) to A. Next, B chooses hk←$HK.
As for thelth (l∈[Qe])encrypt query (ml,ail,fl), where fl=〈al,bl〉∈Fraff, B prepares the challenge ciphertext 〈Cl,χl〉 in the following way. (i)
Ifl∈[j-1], B computes 〈Cl,χl〉 just like that in both G1,j and G1,j′. That is, B chooses Cl←$V with witness wl, chooses κl←$K randomly, and invokes χl←$AE.Encrypt(κl,ml).(ii)
Ifl∈[j+1,Qe], B computes 〈Cl,χl〉 just like that in both G1,j and G1,j′. That is, B chooses Cl←$V with witness wl, computes tl≔H(Cl,ail) and κl≔Λal·hk+bl(Cl,tl), and invokes χl←$AE.Encrypt(κl,ml).(iii)
Ifl=j, B embeds its own challenge C to Cj, that is, Cj≔C. Then it computes tj≔H(Cj,aij), κj≔Λaj·hk+bj(Cj,tj), and invokes χj←$AE.Encrypt(κj,mj).
B outputs the challenge ciphertext 〈Cl,χl〉 to A. Moreover, B puts (ail,fl,〈Cl,χl〉) to QENC, (ail,fl) to QAI-F, and (Cl,ail,tl) to QTAG.
Obviously,B simulates G1,j in the case of C←$V and simulates G1,j′ in the case of C←$C∖V.
Finally,A sends a forgery (ai∗,f∗,〈C∗,χ∗〉) to B, with f∗=〈a∗,b∗〉∈Fraff. Then B decides whetherfinalize outputs 1 or not with the help ofhk. (i)
If(ai∗,f∗,〈C∗,χ∗〉)∈QENC, B outputs 0 (to its own challenger).(ii)
If∃(ail,fl)∈QAI-F such that ail=ai∗ but fl≠f∗, B outputs 0.(iii)
IfC∗∉C, B outputs 0.(iv)
B computes t∗≔H(C∗,ai∗)∈T.(v)
If∃(Cl,ail,tl)∈QTAG such that tl=t∗ but (Cl,ail)≠(C∗,ai∗), B outputs 0.(vi)
B computes κ∗≔Λa∗·hk+b∗(C∗,t∗)∈K and outputs (AE.Decrypt(κ∗,χ∗)≠⊥).
With the help ofhk, B is able to perfectly simulatefinalize, just like that in both G1,j and G1,j′. Moreover, B outputs 1 to its own challenger if and only if the eventForge occurs.
As a result, we have that|Pr1,j[Forge]-Pr1,j′[Forge]|≤AdvTHPS,Bsmp(λ).Game
G
1
,
j
′
′
,
j
∈
[
Q
e
]. It is identical to G1,j′, except that, for the jthencrypt query, the challenger chooses κj←$K randomly.Lemma 18.
For allj∈[Qe], Pr1,j′[Forge]≤Pr1,j′′[Forge]+AdvAEint-ot(λ).Proof.
For gameG1,j′ and game G1,j′′, the difference between them lies in the computation of κj in the jthencrypt query. In G1,j′, κj is properly computed; in G1,j′′, κj is chosen from K uniformly.
We consider the information about the keyhk that is used in G1,j′.(i)
For thelth (l∈[j-1]) query,encrypt does not usehk at all since κl is randomly chosen from K.(ii)
For thelth (l∈[j+1,Qe]) query, similar to the proof of Lemma 16,encrypt can use pk=μ(sk) to compute κl.(iii)
For thejth query, similar to the proof of Lemma 16,encrypt uses Λhk(Cj,tj) to compute κj:(18)κj=Λaj·hk+bjCj,tj:Cj⟵$C∖V=ΛhkCj,tjaj·ΛbjCj,tj:via  key-homomorphism.(iv)
Thefinalize procedure, which defines the eventForge, uses Λhk(C∗,t∗) to compute κ∗:(19)κ∗=Λa∗·hk+b∗C∗,t∗=ΛhkC∗,t∗a∗·Λb∗C∗,t∗:via  key-homomorphism.
We divide the eventForge into the following two subevents:
(i) Subevent:
F
o
r
g
e
∧
t
j
≠
t
∗. Let us first consider the event tj≠t∗. We show that (20)Pr1,j′tj≠t∗=Pr1,j′′tj≠t∗.By the fact that Cj∈C∖V and by the universal2 property ofTHPS, Λhk(Cj,tj) is uniformly distributed over K conditioned on pk=μ(hk). Then as long as aj∈Z|K|∗, κj=(Λhk(Cj,tj))aj·Λbj(Cj,tj) is also randomly distributed over K. Hence, G1,j′ is the same as G1,j′′ before A queriesfinalize, and consequently, tj≠t∗ occurs with the same probability in G1,j′ and G1,j′′.
Next we consider the eventForge conditioned on tj≠t∗. We show that(21)Pr1,j′Forge∣tj≠t∗=Pr1,j′′Forge∣tj≠t∗.Since tj≠t∗ and Cj∈C∖V, by the universal2 property ofTHPS, Λhk(Cj,tj) is uniformly distributed over K conditioned on pk=μ(hk) and Λhk(C∗,t∗). With a similar argument, κj is also randomly distributed over K. Hence, G1,j′ is the same as G1,j′′ when tj≠t∗, and consequently, the probability thatForge occurs in G1,j′ and G1,j′′ conditioned on tj≠t∗ is the same.
In conclusion, we have that(22)Pr1,j′Forge∧tj≠t∗=Pr1,j′′Forge∧tj≠t∗≤Pr1,j′′Forge.
(ii) Subevent:
F
o
r
g
e
∧
t
j
=
t
∗. By the new rule added in game G1,Forge and tj=t∗ will imply (Cj,aij)=(C∗,ai∗). In addition,Forge and aij=ai∗ will imply that fj=f∗, due to the special rule in theweak-INT-Fraff-RKA game (see Figure 4). Then it is straightforward to check that Λhk(Cj,tj)=Λhk(C∗,t∗) and (23)κj=ΛhkCj,tjaj·ΛbjCj,tj=ΛhkC∗,t∗a∗·Λb∗C∗,t∗=κ∗.Since Cj∈C∖V, by the universal2 property ofTHPS, Λhk(Cj,tj) (=Λhk(C∗,t∗)) is uniformly distributed over K conditioned on pk=μ(hk). Then as long as aj (which equals a∗) ∈Z|K|∗, κj (which equals κ∗) is also randomly distributed over K. Also in this subevent, (ai∗,f∗,C∗)=(aij,fj,Cj) implies χ∗≠χj; thus the probability of AE.Decrypt(κ∗,χ∗)≠⊥ is bounded by AdvAEint-ot(λ). So we have the following claim. We present the full description of the reduction in Appendix A.
Claim  19. One has Pr1,j′[Forge∧tj=t∗]≤AdvAEint-ot(λ).
Combining the above two subevents together, Lemma18 follows.Now, we show that gameG1,j′′ is computationally indistinguishable from game G1,j+1, j∈[Qe]. Note that the divergence between G1,j′′ and G1,j+1 lies in the distribution of Cj in the jthencrypt query. In game G1,j′′, Cj is uniformly chosen from C∖V; in game G1,j+1, Cj is uniformly chosen from V. Similar to Lemma 17, any difference between these two games results in a PPT adversary solving the subset membership problem related toTHPS; thus we have that |Pr1,j′′[Forge]-Pr1,j+1[Forge]|≤AdvTHPSsmp(λ).Finally, in gameG1,Qe+1, note that the challenger does not usehk to compute κl at all; thushk is uniformly random to A. Consequently, in thefinalize procedure, we have(24)κ∗=ΛhkC∗,t∗a∗·Λb∗C∗,t∗.By the extracting property ofTHPS, Λhk(C∗,t∗) is uniformly random over K. Therefore, as long as a∗∈Z|K|∗, κ∗ is uniformly random over K as well. Hence, the probability of AE.Decrypt(κ∗,χ∗)≠⊥ is bounded by AdvAEint-ot(λ), and we have Pr1,Qe+1[Forge]≤AdvAEint-ot(λ).In all, we proved the weak-INT-Fraff-RKA security.This completes the proof of Theorem15 (weak-INT-Fraff-RKA security).Remark 20.
We emphasize that the special rule in theweak-INT-F-RKA game (cf. Figure 4) plays an essential role in proving Lemma 18. Below is the reason.
Without this special rule, the adversary is allowed to submitf∗ (=〈a∗,b∗〉) which is different from fj (=〈aj,bj〉), even if ai∗=aij holds. In this case, we cannot expect to employ the INT-OT security of the underlyingAE scheme to show that the second subevent (Forge∧tj=t∗) occurs with only a negligible probability. To demonstrate the problem clearly, suppose that the adversary A submits fj=〈aj,bj〉 in the jthencrypt query and submits f∗=〈a∗,b∗〉=〈aj,bj+Δ〉 in thefinalize procedure, where Δ is a constant. Then we have(25)κ∗=ΛhkCj,tjaj·Λbj+ΔCj,tj=ΛhkCj,tjaj·ΛbjCj,tj·ΛΔCj,tj=κj·ΛΔCj,tj,where the second equality follows from the key-homomorphism ofTHPS. Thus, κ∗andκjare closely related but may not be equal; in particular, the quotient κ∗/κj (=ΛΔ(Cj,tj)) is a constant.
Consequently, it is hard for us to show that the subeventForge∧tj=t∗ occurs with a negligible probability. The reason is as follows. To show that it is infeasible for any PPT adversary A, who obtains χj←$AE.Encrypt(κj,mj) in the jthencrypt query, to generate anAE-ciphertext χ∗ satisfying AE.Decrypt(κ∗,χ∗) (=AE.Decrypt(κj·ΛΔ(Cj,tj),χ∗)) ≠⊥, it seems that INT-RKA security ofAE is required to some extent. We definitely cannot require INT-RKA security for the underlyingAE scheme, since we are constructing (weak) INT-RKA secure (AI)AE schemeAIAE. As a result, it is hard to prove Lemma 18 without our special rule in theweak-INT-F-RKA game.


### 3.3. Tag-Based HPS from the DDH Assumption

Qin et al. [19] gave a construction of tag-based HPS from the d-LIN assumption. Here we construct a key-homomorphic THPSDDH under the DDH assumption in Figure 6. With a routine check, the projective property of THPSDDH follows.Figure 6
Construction ofTHPSDDH.Theorem 21.
T
H
P
S
D
D
H in Figure 6 is universal2, extracting, and key-homomorphic. Moreover, the subset membership problem related to THPSDDH is hard under the DDH assumption forGenN and QRN¯.Proof of Theorem21.
U
n
i
v
e
r
s
a
l
2. Suppose that C=(g1w1,g2w2)∈C, C′=(g1w1′,g2w2′)∈C∖V, and t,t′∈T with t≠t′. For hk=(k1,k2,k3,k4)←$(ZN)4, we analyze the distribution of Λhk(C′,t′) conditioned on pk=μ(hk) and Λhk(C,t).
Denoted≔dlogg1g2∈ZN. Firstly pk=μ(hk)=(g1k1g2k2,g1k3g2k4)=(g1k1+dk2,g1k3+dk4), which may leak the values of k1+dk2 and k3+dk4.
Next(26)ΛhkC,t=g1w1k1+k3t·g2w2k2+k4t=g1w1k1+w2dk2+t·w1k3+w2dk4︷≜X,which may further leak the value of X.
Similarly,(27)ΛhkC′,t′=g1w1′k1+k3t′·g2w2′k2+k4t′=g1w1′k1+w2′dk2+t′·w1′k3+w2′dk4︷≜Y.By the fact that C′=(g1w1′,g2w2′)∉V, we have w1′≠w2′. Then as long as t≠t′, Y is independent of k1+dk2, k3+dk4, and X, and consequently, Y is uniformly distributed over ZN.
Therefore, conditioned onpk=μ(hk) and Λhk(C,t), Λhk(C′,t′) (=g1Y) is randomly distributed over K=QRN¯.
Extracting. Suppose that C=(g1w1,g2w2)∈C and t∈T. For hk=(k1,k2,k3,k4)←$(ZN)4, we analyze the distribution of Λhk(C,t).
By (26), Λhk(C,t)=g1X with X=(w1k1+w2dk2)+t·(w1k3+w2dk4). Since C=(g1w1,g2w2)∈C, we have (w1,w2)≠(0,0). Then when (k1,k2,k3,k4) is randomly chosen from (ZN)4, X is uniformly distributed over ZN. Consequently, Λhk(C,t) is randomly distributed over K=QRN¯.
Key-Homomorphism. For all hk=(k1,k2,k3,k4)∈(ZN)4, all a∈Z, all b=(b1,b2,b3,b4)∈(ZN)4, all C=(c1,c2)∈C, and all t∈T, we have a·hk+b=a·(k1,k2,k3,k4)+(b1,b2,b3,b4)=(ak1+b1,ak2+b2,ak3+b3,ak4+b4). Then it follows that(28)Λa·hk+bC,t=c1ak1+b1+ak3+b3t·c2ak2+b2+ak4+b4t=c1k1+k3tc2k2+k4ta·c1b1+b3tc2b2+b4t=ΛhkC,ta·ΛbC,t.
Subset Membership Problem. The subset membership problem related to THPSDDH requires that (parsTHPS=(N,p,q,N¯,g1,g2),C=(g1w,g2w)) is computationally indistinguishable from (parsTHPS=(N,p,q,N¯,g1,g2),C′=(g1w1,g2w2)), where C←$V and C′←$C∖V. It trivially holds under the DDH assumption forGenN and QRN¯.


### 3.4. Instantiation: AIAEDDH from DDH-Based THPSDDH and OT-Secure AE

When plugging theTHPSDDH (cf. Figure 6) into the paradigm in Figure 5, we immediately obtain an AIAE scheme AIAEDDH under the DDH assumption, as shown in Figure 7. The key space is KAIAE=(ZN)4.Figure 7
Construction ofAIAEDDH from AE and THPSDDH.By combining Theorem15 with Theorem 21, we have the following corollary regarding the RKA security of AIAEDDH.Corollary 22.
If (i) the DDH assumption holds forGenN and QRN¯, (ii)AE is one-time secure, and (iii) H is collision-resistant, then the scheme AIAEDDH in Figure 7 is IND-Fraff-RKA and weak-INT-Fraff-RKA secure. Here Fraff≔{fa,b:(k1,k2,k3,k4)∈(ZN)4↦(ak1+b1,ak2+b2,ak3+b3,ak4+b4)∈(ZN)4∣a∈ZN∗,b=(b1,b2,b3,b4)∈(ZN)4}.Remark 23.
OurAIAEDDH enjoys the following property: κ=c1k1+k3t·c2k2+k4t will be randomly distributed over QRN¯, as long as any element kj in k=(k1,k2,k3,k4) is uniformly chosen. As a result, the one-time security ofAE will guarantee that AIAE.Decrypt(k,aiae.c,ai)=⊥ holds for any (aiae.c,ai) except with probability AdvAEint-ot(λ)≤AdvAIAEDDHweak-int-rka(λ). This fact will be used in the security proof of the PKE schemes presented in Sections 4 and 5.


## 3.1. Auxiliary-Input Authenticated Encryption

Definition 13 (AIAE).
There are three PPT algorithmsAIAE=(AIAE.ParGen,AIAE.Encrypt,AIAE.Decrypt) in an AIAE scheme: (i)
The parameter generation algorithmAIAE.ParGen(1λ) generates a system parameter parsAIAE. We require parsAIAE to be an implicit input to other algorithms and assume that parsAIAE implicitly defines a key space KAIAE, a message space M, and an auxiliary-input space AI.(ii)
The encryption algorithmAIAE.Encrypt(k,m,ai) takes a key k∈KAIAE, a message m∈M, and an auxiliary input ai∈AI as input and outputs a ciphertext aiae.c.(iii)
The decryption algorithmAIAE.Decrypt(k,aiae.c,ai) takes a key k∈KAIAE, a ciphertext aiae.c, and an auxiliary input ai∈AI as input and outputs a message m∈M or a symbol ⊥.
We requireAIAE to have perfect correctness; that is, for all possible parsAIAE←$AIAE.ParGen(1λ), all keys k∈KAIAE, all messages m∈M, and all auxiliary-inputs ai∈AI, (14)Pr⁡AIAE.Decryptk,AIAE.Encryptk,m,ai,ai=m=1.In fact, AIAE is a generalization of traditional AE, and traditional AE can be viewed as AIAE withAI=∅.Definition 14 (RKA security).
Denote byF a set of functions from KAIAE to KAIAE. A scheme AIAE is IND-F-RKA secure and weak-INT-F-RKA secure, if for any PPT A, (15)AdvAIAE,Aind-rkaλ≔Pr⁡IND-F-RKAA⟹1-12≤neglλ,AdvAIAE,Aweak-int-rkaλ≔Prweak-INT-F-RKAA⟹1≤neglλ,whereIND-F-RKA andweak-INT-F-RKA are the security games presented in Figure 4.Figure 4
IND-F-RKA (a) andweak-INT-F-RKA (b) security games. We note that, in theweak-INT-F-RKA game, there is a special rule (as shown in the shadow) of outputting 0 infinalize.
(a)
(b)


## 3.2. Generic Construction of AIAE from Tag-Based HPS and OT-Secure AE

Our construction of AIAE needs the following ingredients.(i)
A tag-based hash proof systemTHPS=(THPS.Setup,THPS.Pub,THPS.Priv), where the hash value space is K, the tag space is T, and the hashing key space is HK.(ii)
A (traditional) authenticated encryption schemeAE=(AE.ParGen,AE.Encrypt,AE.Decrypt), where the message space is M and the key space is K.(iii)
A set of hash functionsH={H:{0,1}∗→T}.We present our AIAE constructionAIAE=(AIAE.ParGen,AIAE.Encrypt,AIAE.Decrypt) in Figure 5, whose key space is KAIAE≔HK, message space is M, and auxiliary-input space is AI≔{0,1}∗.Figure 5
Generic construction ofAIAE from THPS and AE.By the perfect correctness ofAE, it is routine to check that AIAE has perfect correctness.Theorem 15.
If (i)THPS is universal2, extracting, key-homomorphic and has a hard subset membership problem, (ii) AE is one-time secure, and (iii) H is collision-resistant, then the schemeAIAE in Figure 5 is IND-Fraff-RKA and weak-INT-Fraff-RKA secure. Here Fraff≔{fa,b:hk∈HK↦a·hk+b∈HK∣a∈Z|K|∗,b∈HK} is the set of restricted affine functions.Proof of Theorem15 (IND-
F
r
a
f
f
-RKA Security). Denote by A a PPT adversary who is against the IND-Fraff-RKA security and queriesencrypt oracle for at most Qe times. We show the IND-Fraff-RKA security through a series of games. For an event E, we denote by Prj[E], Prj′[E], and Prj′′[E] the probability of E occurring in games Gj, Gj′, and Gj′′, respectively.Game
G
1. It is the originalIND-Fraff-RKA game. Denote the event β′=β bySucc. According to the definition, AdvAIAE,Aind-rka(λ)=|Pr1[Succ]-1/2|.As for thelth (l∈[Qe])encrypt query (ml,0,ml,1,ail,fl), where fl=〈al,bl〉∈Fraff, the challenger prepares the challenge ciphertext as follows:(i)
pickCl←$V together with witness wl,(ii)
computetl≔H(Cl,ail)∈T,(iii)
computeκl≔Λal·hk+bl(Cl,tl)∈K,(iv)
invokeχl←$AE.Encrypt(κl,ml,β),and it outputs the challenge ciphertext〈Cl,χl〉 to A.Game
G
1
,
j
,
j
∈
[
Q
e
+
1
]. It is identical to G1, except that, for the first j-1 times ofencrypt queries, that is, l∈[j-1], the challenger chooses κl←$K randomly for the AE scheme.ClearlyG1,1 is identical to G1; thus Pr1[Succ]=Pr1,1[Succ].Game
G
1
,
j
′
,
j
∈
[
Q
e
]. It is identical to G1,j, except that, for the jthencrypt query, the challenger samples Cj←$C∖V uniformly.The difference betweenG1,j and G1,j′ lies in the distribution of Cj. In game G1,j, Cj is uniformly chosen from V; in game G1,j′, Cj is uniformly chosen from C∖V. Any difference between G1,j and G1,j′ results in a PPT adversary solving the subset membership problem related toTHPS; thus we have that |Pr1,j[Succ]-Pr1,j′[Succ]|≤AdvTHPSsmp(λ).Game
G
1
,
j
′
′
,
j
∈
[
Q
e
]. It is identical to G1,j′, except that, for the jthencrypt query, the challenger chooses κj←$K randomly.Lemma 16.
For allj∈[Qe], Pr1,j′[Succ]=Pr1,j′′[Succ].Proof.
For gameG1,j′ and game G1,j′′, the difference between them lies in the computation of κj in the jthencrypt query. In G1,j′, κj is properly computed, while in G1,j′′, it is chosen from K uniformly.
We analyze the information about the keyhk that is used in game G1,j′.(i)
For thelth (l∈[j-1]) query,encrypt does not usehk at all since κl is randomly chosen from K.(ii)
For thelth (l∈[j+1,Qe]) query,encrypt can use pk=μ(hk) to compute κl:(16)κl=Λal·hk+blCl,tl:Cl⟵$Vwithwitnesswl=ΛhkCl,tlal·ΛblCl,tl:via  key-homomorphism=THPS.Pubpk,Cl,wl,tlal·ΛblCl,tl:via  projective  property.(iii)
For thejth query,encrypt uses Λhk(Cj,tj) to compute κj:(17)κj=Λaj·hk+bjCj,tj:Cj⟵$C∖V=ΛhkCj,tjaj·ΛbjCj,tj:via  key-homomorphism.
SinceCj∈C∖V, by the universal2 property ofTHPS, Λhk(Cj,tj) is uniformly distributed over K conditioned on pk=μ(hk). Then as long as aj∈Z|K|∗, κj=(Λhk(Cj,tj))aj·Λbj(Cj,tj) is also randomly distributed over K. Consequently, G1,j′ is essentially the same as G1,j′′, and Pr1,j′[Succ]=Pr1,j′′[Succ].Now, we show that gameG1,j′′ is computationally indistinguishable from game G1,j+1, j∈[Qe]. Note that the divergence between G1,j′′ and G1,j+1 lies in the distribution of Cj in the jthencrypt query. In game G1,j′′, Cj is uniformly chosen from C∖V; in game G1,j+1, Cj is uniformly chosen from V. Any difference between these two games results in a PPT adversary solving the subset membership problem related toTHPS; thus we have that |Pr1,j′′[Succ]-Pr1,j+1[Succ]|≤AdvTHPSsmp(λ).Game
G
2. It is identical to G1,Qe+1, except that when answeringencrypt queries, the challenger invokes χl←$AE.Encrypt(κl,0|ml,0|).In gameG1,Qe+1, the challenger computes χl←$AE.Encrypt(κl,ml,β); in game G2, the challenger computes χl←$AE.Encrypt(κl,0|ml,0|). Since each κl is chosen from K uniformly at random, l∈[Qe], by a standard hybrid argument, any difference between G1,Qe+1 and G2 results in a PPT adversary against the IND-OT security of AE, so that |Pr1,Qe+1[Succ]-Pr2[Succ]|≤Qe·AdvAEind-ot(λ).Finally, in gameG2, since the challenge ciphertexts are encryptions of 0|ml,0|, hence β is perfectly hidden to A. So Pr2[Succ]=1/2.Summing up, we proved the IND-Fraff-RKA security.This completes the proof of Theorem15 (IND-Fraff-RKA security).Proof of Theorem15 (Weak-INT-
F
r
a
f
f
-RKA Security). Denote by A a PPT adversary who is against the weak-INT-Fraff-RKA security and queriesencrypt oracle for at most Qe times. Similarly, the proof goes through a series of games, which are defined analogously, just like those games of the previous proof.Game
G
0. It is the originalweak-INT-Fraff-RKA game.As for thelth (l∈[Qe])encrypt query (ml,ail,fl), the challenger computes the challenge ciphertext 〈Cl,χl〉 in similar steps as the previous proof and outputs 〈Cl,χl〉 to A. Moreover, the challenger will put (ail,fl,〈Cl,χl〉) to a set QENC, put (ail,fl) to a set QAI-F, and put (Cl,ail,tl) to a set QTAG. In the end, the adversary outputs a forgery (ai∗,f∗,〈C∗,χ∗〉), where f∗=〈a∗,b∗〉, and the challenger invokes thefinalize procedure as follows:(i)
If(ai∗,f∗,〈C∗,χ∗〉)∈QENC, output 0.(ii)
If∃(ail,fl)∈QAI-F such that ail=ai∗ but fl≠f∗, output 0.(iii)
IfC∗∉C, output 0.(iv)
Computet∗≔H(C∗,ai∗)∈T and κ∗≔Λa∗·hk+b∗(C∗,t∗)∈K.Output(AE.Decrypt(κ∗,χ∗)≠⊥).Denote the event thatfinalize outputs 1 byForge. According to the definition, AdvAIAE,Aweak-int-rka(λ)=Pr0[Forge].Game
G
1. It is identical to G0, except that the following rule is added to the procedurefinalize by the challenger:(i)
If∃(Cl,ail,tl)∈QTAG such that tl=t∗ but (Cl,ail)≠(C∗,ai∗), output 0.Sincetl=H(Cl,ail) and t∗=H(C∗,ai∗), any difference between G0 and G1 implies a hash collision of H. So |Pr0[Forge]-Pr1[Forge]|≤AdvHcr(λ).Game
G
1
,
j
,
j
∈
[
Q
e
+
1
]. It is identical to G1, except that, for the first j-1 times ofencrypt queries, that is, l∈[j-1], the challenger chooses κl←$K uniformly for theAE scheme.ClearlyG1,1 is identical to G1; thus Pr1[Forge]=Pr1,1[Forge].Game
G
1
,
j
′
,
j
∈
[
Q
e
]. It is identical to G1,j, except that, for the jthencrypt query, the challenger samples Cj←$C∖V uniformly.The difference betweenG1,j and G1,j′ lies in the distribution of Cj. In game G1,j, Cj is uniformly chosen from V; in game G1,j′, Cj is uniformly chosen from C∖V. Any difference between these two games results in a PPT adversary solving the subset membership problem related toTHPS. We emphasize that the PPT adversary (simulator) is able to check the occurrence ofForge in an efficient way, because the keyhk can be chosen by the simulator itself. Consequently, the difference between G1,j and G1,j′ can be reduced to the subset membership problem smoothly.Lemma 17.
For allj∈[Qe], |Pr1,j[Forge]-Pr1,j′[Forge]|≤AdvTHPSsmp(λ).Proof.
To bound the difference betweenG1,j and G1,j′, we build an efficient adversary B solving the subset membership problem. Given (parsTHPS,C), where parsTHPS←$THPS.Setup(1λ), B aims to distinguish C←$V from C←$C∖V.
B simulates G1,j or G1,j′ for A. Firstly, B invokes parsAE←$AE.ParGen(1λ), picks H←$H randomly, and sends parsAIAE≔(parsTHPS,parsAE,H) to A. Next, B chooses hk←$HK.
As for thelth (l∈[Qe])encrypt query (ml,ail,fl), where fl=〈al,bl〉∈Fraff, B prepares the challenge ciphertext 〈Cl,χl〉 in the following way. (i)
Ifl∈[j-1], B computes 〈Cl,χl〉 just like that in both G1,j and G1,j′. That is, B chooses Cl←$V with witness wl, chooses κl←$K randomly, and invokes χl←$AE.Encrypt(κl,ml).(ii)
Ifl∈[j+1,Qe], B computes 〈Cl,χl〉 just like that in both G1,j and G1,j′. That is, B chooses Cl←$V with witness wl, computes tl≔H(Cl,ail) and κl≔Λal·hk+bl(Cl,tl), and invokes χl←$AE.Encrypt(κl,ml).(iii)
Ifl=j, B embeds its own challenge C to Cj, that is, Cj≔C. Then it computes tj≔H(Cj,aij), κj≔Λaj·hk+bj(Cj,tj), and invokes χj←$AE.Encrypt(κj,mj).
B outputs the challenge ciphertext 〈Cl,χl〉 to A. Moreover, B puts (ail,fl,〈Cl,χl〉) to QENC, (ail,fl) to QAI-F, and (Cl,ail,tl) to QTAG.
Obviously,B simulates G1,j in the case of C←$V and simulates G1,j′ in the case of C←$C∖V.
Finally,A sends a forgery (ai∗,f∗,〈C∗,χ∗〉) to B, with f∗=〈a∗,b∗〉∈Fraff. Then B decides whetherfinalize outputs 1 or not with the help ofhk. (i)
If(ai∗,f∗,〈C∗,χ∗〉)∈QENC, B outputs 0 (to its own challenger).(ii)
If∃(ail,fl)∈QAI-F such that ail=ai∗ but fl≠f∗, B outputs 0.(iii)
IfC∗∉C, B outputs 0.(iv)
B computes t∗≔H(C∗,ai∗)∈T.(v)
If∃(Cl,ail,tl)∈QTAG such that tl=t∗ but (Cl,ail)≠(C∗,ai∗), B outputs 0.(vi)
B computes κ∗≔Λa∗·hk+b∗(C∗,t∗)∈K and outputs (AE.Decrypt(κ∗,χ∗)≠⊥).
With the help ofhk, B is able to perfectly simulatefinalize, just like that in both G1,j and G1,j′. Moreover, B outputs 1 to its own challenger if and only if the eventForge occurs.
As a result, we have that|Pr1,j[Forge]-Pr1,j′[Forge]|≤AdvTHPS,Bsmp(λ).Game
G
1
,
j
′
′
,
j
∈
[
Q
e
]. It is identical to G1,j′, except that, for the jthencrypt query, the challenger chooses κj←$K randomly.Lemma 18.
For allj∈[Qe], Pr1,j′[Forge]≤Pr1,j′′[Forge]+AdvAEint-ot(λ).Proof.
For gameG1,j′ and game G1,j′′, the difference between them lies in the computation of κj in the jthencrypt query. In G1,j′, κj is properly computed; in G1,j′′, κj is chosen from K uniformly.
We consider the information about the keyhk that is used in G1,j′.(i)
For thelth (l∈[j-1]) query,encrypt does not usehk at all since κl is randomly chosen from K.(ii)
For thelth (l∈[j+1,Qe]) query, similar to the proof of Lemma 16,encrypt can use pk=μ(sk) to compute κl.(iii)
For thejth query, similar to the proof of Lemma 16,encrypt uses Λhk(Cj,tj) to compute κj:(18)κj=Λaj·hk+bjCj,tj:Cj⟵$C∖V=ΛhkCj,tjaj·ΛbjCj,tj:via  key-homomorphism.(iv)
Thefinalize procedure, which defines the eventForge, uses Λhk(C∗,t∗) to compute κ∗:(19)κ∗=Λa∗·hk+b∗C∗,t∗=ΛhkC∗,t∗a∗·Λb∗C∗,t∗:via  key-homomorphism.
We divide the eventForge into the following two subevents:
(i) Subevent:
F
o
r
g
e
∧
t
j
≠
t
∗. Let us first consider the event tj≠t∗. We show that (20)Pr1,j′tj≠t∗=Pr1,j′′tj≠t∗.By the fact that Cj∈C∖V and by the universal2 property ofTHPS, Λhk(Cj,tj) is uniformly distributed over K conditioned on pk=μ(hk). Then as long as aj∈Z|K|∗, κj=(Λhk(Cj,tj))aj·Λbj(Cj,tj) is also randomly distributed over K. Hence, G1,j′ is the same as G1,j′′ before A queriesfinalize, and consequently, tj≠t∗ occurs with the same probability in G1,j′ and G1,j′′.
Next we consider the eventForge conditioned on tj≠t∗. We show that(21)Pr1,j′Forge∣tj≠t∗=Pr1,j′′Forge∣tj≠t∗.Since tj≠t∗ and Cj∈C∖V, by the universal2 property ofTHPS, Λhk(Cj,tj) is uniformly distributed over K conditioned on pk=μ(hk) and Λhk(C∗,t∗). With a similar argument, κj is also randomly distributed over K. Hence, G1,j′ is the same as G1,j′′ when tj≠t∗, and consequently, the probability thatForge occurs in G1,j′ and G1,j′′ conditioned on tj≠t∗ is the same.
In conclusion, we have that(22)Pr1,j′Forge∧tj≠t∗=Pr1,j′′Forge∧tj≠t∗≤Pr1,j′′Forge.
(ii) Subevent:
F
o
r
g
e
∧
t
j
=
t
∗. By the new rule added in game G1,Forge and tj=t∗ will imply (Cj,aij)=(C∗,ai∗). In addition,Forge and aij=ai∗ will imply that fj=f∗, due to the special rule in theweak-INT-Fraff-RKA game (see Figure 4). Then it is straightforward to check that Λhk(Cj,tj)=Λhk(C∗,t∗) and (23)κj=ΛhkCj,tjaj·ΛbjCj,tj=ΛhkC∗,t∗a∗·Λb∗C∗,t∗=κ∗.Since Cj∈C∖V, by the universal2 property ofTHPS, Λhk(Cj,tj) (=Λhk(C∗,t∗)) is uniformly distributed over K conditioned on pk=μ(hk). Then as long as aj (which equals a∗) ∈Z|K|∗, κj (which equals κ∗) is also randomly distributed over K. Also in this subevent, (ai∗,f∗,C∗)=(aij,fj,Cj) implies χ∗≠χj; thus the probability of AE.Decrypt(κ∗,χ∗)≠⊥ is bounded by AdvAEint-ot(λ). So we have the following claim. We present the full description of the reduction in Appendix A.
Claim  19. One has Pr1,j′[Forge∧tj=t∗]≤AdvAEint-ot(λ).
Combining the above two subevents together, Lemma18 follows.Now, we show that gameG1,j′′ is computationally indistinguishable from game G1,j+1, j∈[Qe]. Note that the divergence between G1,j′′ and G1,j+1 lies in the distribution of Cj in the jthencrypt query. In game G1,j′′, Cj is uniformly chosen from C∖V; in game G1,j+1, Cj is uniformly chosen from V. Similar to Lemma 17, any difference between these two games results in a PPT adversary solving the subset membership problem related toTHPS; thus we have that |Pr1,j′′[Forge]-Pr1,j+1[Forge]|≤AdvTHPSsmp(λ).Finally, in gameG1,Qe+1, note that the challenger does not usehk to compute κl at all; thushk is uniformly random to A. Consequently, in thefinalize procedure, we have(24)κ∗=ΛhkC∗,t∗a∗·Λb∗C∗,t∗.By the extracting property ofTHPS, Λhk(C∗,t∗) is uniformly random over K. Therefore, as long as a∗∈Z|K|∗, κ∗ is uniformly random over K as well. Hence, the probability of AE.Decrypt(κ∗,χ∗)≠⊥ is bounded by AdvAEint-ot(λ), and we have Pr1,Qe+1[Forge]≤AdvAEint-ot(λ).In all, we proved the weak-INT-Fraff-RKA security.This completes the proof of Theorem15 (weak-INT-Fraff-RKA security).Remark 20.
We emphasize that the special rule in theweak-INT-F-RKA game (cf. Figure 4) plays an essential role in proving Lemma 18. Below is the reason.
Without this special rule, the adversary is allowed to submitf∗ (=〈a∗,b∗〉) which is different from fj (=〈aj,bj〉), even if ai∗=aij holds. In this case, we cannot expect to employ the INT-OT security of the underlyingAE scheme to show that the second subevent (Forge∧tj=t∗) occurs with only a negligible probability. To demonstrate the problem clearly, suppose that the adversary A submits fj=〈aj,bj〉 in the jthencrypt query and submits f∗=〈a∗,b∗〉=〈aj,bj+Δ〉 in thefinalize procedure, where Δ is a constant. Then we have(25)κ∗=ΛhkCj,tjaj·Λbj+ΔCj,tj=ΛhkCj,tjaj·ΛbjCj,tj·ΛΔCj,tj=κj·ΛΔCj,tj,where the second equality follows from the key-homomorphism ofTHPS. Thus, κ∗andκjare closely related but may not be equal; in particular, the quotient κ∗/κj (=ΛΔ(Cj,tj)) is a constant.
Consequently, it is hard for us to show that the subeventForge∧tj=t∗ occurs with a negligible probability. The reason is as follows. To show that it is infeasible for any PPT adversary A, who obtains χj←$AE.Encrypt(κj,mj) in the jthencrypt query, to generate anAE-ciphertext χ∗ satisfying AE.Decrypt(κ∗,χ∗) (=AE.Decrypt(κj·ΛΔ(Cj,tj),χ∗)) ≠⊥, it seems that INT-RKA security ofAE is required to some extent. We definitely cannot require INT-RKA security for the underlyingAE scheme, since we are constructing (weak) INT-RKA secure (AI)AE schemeAIAE. As a result, it is hard to prove Lemma 18 without our special rule in theweak-INT-F-RKA game.


## 3.3. Tag-Based HPS from the DDH Assumption

Qin et al. [19] gave a construction of tag-based HPS from the d-LIN assumption. Here we construct a key-homomorphic THPSDDH under the DDH assumption in Figure 6. With a routine check, the projective property of THPSDDH follows.Figure 6
Construction ofTHPSDDH.Theorem 21.
T
H
P
S
D
D
H in Figure 6 is universal2, extracting, and key-homomorphic. Moreover, the subset membership problem related to THPSDDH is hard under the DDH assumption forGenN and QRN¯.Proof of Theorem21.
U
n
i
v
e
r
s
a
l
2. Suppose that C=(g1w1,g2w2)∈C, C′=(g1w1′,g2w2′)∈C∖V, and t,t′∈T with t≠t′. For hk=(k1,k2,k3,k4)←$(ZN)4, we analyze the distribution of Λhk(C′,t′) conditioned on pk=μ(hk) and Λhk(C,t).
Denoted≔dlogg1g2∈ZN. Firstly pk=μ(hk)=(g1k1g2k2,g1k3g2k4)=(g1k1+dk2,g1k3+dk4), which may leak the values of k1+dk2 and k3+dk4.
Next(26)ΛhkC,t=g1w1k1+k3t·g2w2k2+k4t=g1w1k1+w2dk2+t·w1k3+w2dk4︷≜X,which may further leak the value of X.
Similarly,(27)ΛhkC′,t′=g1w1′k1+k3t′·g2w2′k2+k4t′=g1w1′k1+w2′dk2+t′·w1′k3+w2′dk4︷≜Y.By the fact that C′=(g1w1′,g2w2′)∉V, we have w1′≠w2′. Then as long as t≠t′, Y is independent of k1+dk2, k3+dk4, and X, and consequently, Y is uniformly distributed over ZN.
Therefore, conditioned onpk=μ(hk) and Λhk(C,t), Λhk(C′,t′) (=g1Y) is randomly distributed over K=QRN¯.
Extracting. Suppose that C=(g1w1,g2w2)∈C and t∈T. For hk=(k1,k2,k3,k4)←$(ZN)4, we analyze the distribution of Λhk(C,t).
By (26), Λhk(C,t)=g1X with X=(w1k1+w2dk2)+t·(w1k3+w2dk4). Since C=(g1w1,g2w2)∈C, we have (w1,w2)≠(0,0). Then when (k1,k2,k3,k4) is randomly chosen from (ZN)4, X is uniformly distributed over ZN. Consequently, Λhk(C,t) is randomly distributed over K=QRN¯.
Key-Homomorphism. For all hk=(k1,k2,k3,k4)∈(ZN)4, all a∈Z, all b=(b1,b2,b3,b4)∈(ZN)4, all C=(c1,c2)∈C, and all t∈T, we have a·hk+b=a·(k1,k2,k3,k4)+(b1,b2,b3,b4)=(ak1+b1,ak2+b2,ak3+b3,ak4+b4). Then it follows that(28)Λa·hk+bC,t=c1ak1+b1+ak3+b3t·c2ak2+b2+ak4+b4t=c1k1+k3tc2k2+k4ta·c1b1+b3tc2b2+b4t=ΛhkC,ta·ΛbC,t.
Subset Membership Problem. The subset membership problem related to THPSDDH requires that (parsTHPS=(N,p,q,N¯,g1,g2),C=(g1w,g2w)) is computationally indistinguishable from (parsTHPS=(N,p,q,N¯,g1,g2),C′=(g1w1,g2w2)), where C←$V and C′←$C∖V. It trivially holds under the DDH assumption forGenN and QRN¯.


## 3.4. Instantiation: AIAEDDH from DDH-Based THPSDDH and OT-Secure AE

When plugging theTHPSDDH (cf. Figure 6) into the paradigm in Figure 5, we immediately obtain an AIAE scheme AIAEDDH under the DDH assumption, as shown in Figure 7. The key space is KAIAE=(ZN)4.Figure 7
Construction ofAIAEDDH from AE and THPSDDH.By combining Theorem15 with Theorem 21, we have the following corollary regarding the RKA security of AIAEDDH.Corollary 22.
If (i) the DDH assumption holds forGenN and QRN¯, (ii)AE is one-time secure, and (iii) H is collision-resistant, then the scheme AIAEDDH in Figure 7 is IND-Fraff-RKA and weak-INT-Fraff-RKA secure. Here Fraff≔{fa,b:(k1,k2,k3,k4)∈(ZN)4↦(ak1+b1,ak2+b2,ak3+b3,ak4+b4)∈(ZN)4∣a∈ZN∗,b=(b1,b2,b3,b4)∈(ZN)4}.Remark 23.
OurAIAEDDH enjoys the following property: κ=c1k1+k3t·c2k2+k4t will be randomly distributed over QRN¯, as long as any element kj in k=(k1,k2,k3,k4) is uniformly chosen. As a result, the one-time security ofAE will guarantee that AIAE.Decrypt(k,aiae.c,ai)=⊥ holds for any (aiae.c,ai) except with probability AdvAEint-ot(λ)≤AdvAIAEDDHweak-int-rka(λ). This fact will be used in the security proof of the PKE schemes presented in Sections 4 and 5.


## 4. PKE withn-KDMFaff⁡-CCA Security

Denote byAIAEDDH=(AIAE.ParGen,AIAE.Encrypt,AIAE.Decrypt) the DDH-based AIAE scheme in Figure 7, where the key space is (ZN)4. We need two other building blocks, following the approach in Figure 1.KEM: to be compatible with this AIAEDDH, we have to design aKEM encapsulating a key tuple (k1,k2,k3,k4)∈(ZN)4.E: to support the set Faff of affine functions, we have to construct a special public-key encryption E, so that after a computationally indistinguishable change, E.Encrypt can serve as an entropy filter for the affine function set.The proposed PKE schemePKE=(ParGen,KeyGen,Encrypt,Decrypt) is presented in Figure 8, in which the shadowed parts highlight algorithms ofKEM and E.Figure 8
Construction ofPKE from AIAEDDH. The shadowed parts highlight algorithms ofKEM and E. Here p, q in parsAIAE are not provided in parsAIAE′, since they are not used in AIAE.Encrypt and AIAE.Decrypt of AIAEDDH.The correctness ofPKE is guaranteed by the correctness of AIAEDDH, E, andKEM.Theorem 24.
If (i) the DCR assumption holds forGenN and QRNs, (ii) AIAEDDH is IND-Fraff-RKA and weak-INT-Fraff-RKA secure, and (iii) the DL assumption holds forGenN and SCRNs, then the proposed schemePKE in Figure 8 is n-KDM[Faff]-CCA secure.Proof of Theorem24. Denote by A a PPT adversary who is against the n-KDM[Faff]-CCA security, queryingencrypt oracle for at most Qe times anddecrypt oracle for at most Qd times. The theorem is proved through a series of games. A rough description of differences between adjacent games is summarized in Table 2.Table 2
Brief description of the security proof of Theorem24.
Changes between adjacent games
Assumptions
G0
The originaln-KDM-CCA security game.
—
G1
decrypt: reject if 〈ai,aiae.c〉=〈ail,aiae.cl〉 for some l∈[Qe].
G
0
≈
s
G
1
G2
initialize: sample secret keys with (xi,1,yi,1,…,xi,4,yi,4):=(x1,y1,…,x4,y4)+(x¯i,1,y¯i,1,…,x¯i,4,y¯i,4).
G
1
=
G
2
G
3
encrypt
(
f
l
,
i
l
): use the secret keys to run KEM.Encrypt and E.Encrypt.
G
2
=
G
3
G
4
encrypt
(
f
l
,
i
l
): when encrypt oracle encrypts affine function of secret keys, E.c is computed with (u~l,j)j∈8:=(g1r~l,1Tδ1,…,g5r~l,4Tδ8) instead of (g1r~l,1,…,g5r~l,4).encrypt does not use (xj,yj)j=14modN any more if (δj)j∈[8] is carefully chosen.
G
3
≈
c
G
4 by IV5
G
5
encrypt
(
f
l
,
i
l
): kem.ct (=ai) of KEM.Encrypt is computed with (ul,j)j∈[5]:=((gjr∗Tαj)rl)j∈[5] instead of (gjrl)j∈[5]. Now KEM.Encrypt encapsulates four keys (kl,j-rl⋅(αjxi,j+αj+1yi,j))j=14modN but (kl,j)j=14 is the key used in AIAE.Encrypt.
G
4
≈
c
G
5 by IV5
G
6
encrypt
(
f
l
,
i
l
): sample kl,j≔rlkj∗+sl,j for j∈[4].Now KEM.Encrypt encapsulates four keys(rl(kj∗-αjxj-αj+1yj)-rl(αjx-i,j+αj+1y-i,j)+sl,j)j=14 but (rlkj∗+sl,j)j=14 is the key used in AIAE.Encrypt.
G
5
=
G
6
G
7
decrypt: use ϕ(N) and secret keys to answer decryption queries.
G
6
=
G
7
G8
decrypt: add an additional rejection rule. Reject ifBad′:=(∃uj∉SCRN2) or Bad~:=(∀uj∈SCRN2)∧(∃u~j∉SCRNs) happens.Bad′ and Bad~ can be detected by using ϕ(N). Now only the (modϕ(N)/4) part of secret keys and ϕ(N) are used in decrypt.The randomness of (αjxj+αj+1yj)j=14modN perfectly hides (k1∗,…,k4∗) in encrypt, thus (k1∗,…,k4∗) is uniform.(rlkj∗+sl,j)j=14 is the key used in AIAE.Encrypt.Bad′ may lead to a fresh successful forgery for AIAEDDH.
G
7
=
G
8 if neither Bad′ nor Bad~ happens.Pr[Bad′]=negl due to weak INT-Fraff-RKA security of AIAEDDH
G
9
initialize: sample an independent random tuple (k-1∗,…,k-4∗).encrypt(fl,il): use (rlk-j∗+sl,j)j=14 in AIAE.Encrypt.
G
8
=
G
9 to the adversary
G
10
encrypt: encrypt zeros instead of the affine function of secret keys. Bad~ happens with negligible probability, since t≠g1mmodN in decrypt. Adversary A wins with probability 1/2.
G
9
≈
c
G
10 by IND-Fraff-RKA security of AIAEDDH.Pr[Bad~]=neglIn the proof,G1-G2 deals with the n-user case; G3-G4 is used to eliminate the utilization of the (modN) part of (xj,yj)j=14 in theencrypt oracle; the aim of G5-G6 is to use (xj,yj)j=14modN to hide a base key k∗=(k1∗,…,k4∗) of AIAEDDH in theencrypt oracle; G7-G8 is used to eliminate the utilization of (xj,yj)j=14modN in thedecrypt oracle; in G9-G10, the IND-Fraff-RKA security of AIAEDDH leads to the n-KDM[Faff]-CCA security, because k∗=(k1∗,…,k4∗) now is concealed by (xj,yj)j=14modN perfectly.Game
G
0. It is the n-KDM[Faff]-CCA game. Denote the event β′=β bySucc. According to the definition, AdvPKE,Akdm-cca(λ)=|Pr0[Succ]-1/2|.For theith user, i∈[n], let pki=(hi,1,…,hi,4) and ski=(xi,1,yi,1,…,xi,4,yi,4) denote the corresponding public key and secret key, respectively.Game
G
1. It is identical to G0, except the way of answering thedecrypt query (〈ai,aiae.c〉,i∈[n]). More precisely, the challenger outputs ⊥ if 〈ai,aiae.c〉=〈ail,aiae.cl〉 for some l∈[Qe], where 〈ail,aiae.cl〉 is the challenge ciphertext of the lthencrypt oracle query (fl,il).Case  1
(
〈
a
i
,
a
i
a
e
.
c
〉
,
i
)
=
(
〈
a
i
l
,
a
i
a
e
.
c
l
〉
,
i
l
).decrypt will output ⊥ in G0 since (〈ail,aiae.cl〉,il)∈QENC is prohibited bydecrypt.Case  2 (〈ai,aiae.c〉=〈ail,aiae.cl〉 but i≠il). We show that, in G0,decrypt will output ⊥, due to el,1ul,1xi,1ul,2yi,1∉RUN2, with overwhelming probability. Recall that ul,1=g1rl, ul,2=g2rl, el,1=hil,1rlTkl,1, so (29)el,1ul,1xi,1ul,2yi,1=hil,1rlTkl,1·g1rlxi,1g2rlyi,1=hil,1hi,1-1rlTkl,1modN2,where hil,1 and hi,1 are parts of public keys of ilth user and ith user, respectively, and are uniformly random over SCRNs. So hil,1hi,1-1≠1; hence el,1ul,1xi,1ul,2yi,1∉RUN2, except with negligible probability 2-Ω(λ).ThusG0 and G1 are the same except with probability at most Qd·2-Ω(λ) according to the union bound, and |Pr0[Succ]-Pr1[Succ]|≤Qd·2-Ω(λ).Game
G
2. It is identical to G1, except the way the challenger samples the secret keys ski=(xi,1,yi,1,…,xi,4,yi,4), i∈[n]. In game G2, the challenger first chooses (x1,y1,…,x4,y4) and (x¯i,1,y¯i,1,…,x¯i,4,y¯i,4) randomly from [⌊N2/4⌋]; next it computes (xi,1,yi,1,…,xi,4,yi,4)≔(x1,y1,…,x4,y4)+(x¯i,1,y¯i,1,…,x¯i,4,y¯i,4)mod⌊N2/4⌋ for i∈[n].Obviously, the secret keysski=(xi,1,yi,1,…,xi,4,yi,4) are uniformly distributed. Hence G2 is identical to G1, and Pr1[Succ]=Pr2[Succ].Game
G
3. It is identical to G2, except the way the challenger responds to the lth (l∈[Qe])encrypt query (fl,il). In game G3, instead of using the public key pkil=(hil,1,…,hil,4), the challenger uses the secret key skil=(xil,1,yil,1,…,xil,4,yil,4) to prepare (el,1,…,el,4) and e~l in the following way:(i)
(30)el,1,…,el,4≔ul,1-xil,1ul,2-yil,1Tkl,1,…,ul,4-xil,4ul,5-yil,4Tkl,4modN2,(ii)
(31)e~l≔u~l,1-xil,1u~l,2-yil,1u~l,3-xil,2u~l,4-yil,2u~l,5-xil,3u~l,6-yil,3u~l,7-xil,4u~l,8-yil,4TmβmodNs.Note that forj∈[4],(32)el,j=G2hil,jrlTkl,j=gj-xil,jgj+1-yil,jrlTkl,j=G3ul,j-xil,jul,j+1-yil,jTkl,jmodN2,e~l=G2hil,1r~l,1⋯hil,4r~l,4Tmβ=g1-xil,1g2-yil,1r~l,1⋯g4-xil,4g5-yil,4r~l,4Tmβ=G3u~l,1-xil,1u~l,2-yil,1⋯u~l,7-xil,4u~l,8-yil,4TmβmodNs.Thus, G3 is the same as G2, and Pr2[Succ]=Pr3[Succ].Game
G
4. It is identical to G3, except the way the challenger responds to the lth (l∈[Qe])encrypt query (fl,il). In game G4, in the case of β=1, (u~l,1,…,u~l,8) and e~l are computed without the use of (x1,y1,…,x4,y4)modN:(i)
(33)u~l,1,…,u~l,8≔g1r~l,1T∑i=1nai,1,g2r~l,1T∑i=1nbi,1,g2r~l,2T∑i=1nai,2,g3r~l,2T∑i=1nbi,2,g3r~l,3T∑i=1nai,3,g4r~l,3T∑i=1nbi,3,g4r~l,4T∑i=1nai,4,g5r~l,4T∑i=1nbi,4modNs,(ii)
(34)e~l≔hil,1r~l,1⋯hil,4r~l,4T∑i=1n∑j=14ai,jx¯i,j-x¯il,j+bi,jy¯i,j-y¯il,j+cmodNs,where fl=({ai,1,bi,1,…,ai,4,bi,4}i∈[n],c)∈Faff.Note that(35)e~l=G4∏j=14hil,jr~l,j·T∑i=1n∑j=14ai,jx¯i,j-x¯il,j+bi,jy¯i,j-y¯il,j+c=∏j=14hil,jr~l,j·T∑i=1n∑j=14ai,jxi,j-xil,j+bi,jyi,j-yil,j+c=∏j=14gj-xil,jgj+1-yil,jr~l,j·Tm1-∑i=1n∑j=14ai,jxil,j+bi,jyil,j=∏j=14gjr~l,jT∑i=1nai,j-xil,jgj+1r~l,jT∑i=1nbi,j-yil,j·Tm1=u~l,1-xil,1u~l,2-yil,1⋯u~l,7-xil,4u~l,8-yil,4Tm1modNs,where the third equality follows from m1=∑i=1n‍(ai,1xi,1+bi,1yi,1+⋯+ai,4xi,4+bi,4yi,4)+c.We analyze the difference betweenG3 and G4 via the following lemma.Lemma 25.
One hasPr3Succ-Pr4Succ≤AdvGenNiv5(λ).Proof.
According to the last line of (35), the way that e~l is computed from (u~l,1,…,u~l,8) is the same in G3 and G4. Therefore the only divergence between G3 and G4 lies in (u~l,1,…,u~l,8).
We show that any difference betweenG3 and G4 results in a PPT adversary B1 solving the IV5 problem. B1 is provided with (N,g1,…,g5) and has access to its ChalIV5b oracle. B1 simulates game G3 or game G4 for A. Firstly, B1 preparespars and generates (pki,ski), i∈[n], as in G3 and G4. As for the lth (l∈[Qe])encrypt query (fl,il) from A, where fl=({ai,1,bi,1,…,ai,4,bi,4}i∈[n],c)∈Faff, B1 proceeds as follows: it queries its own ChalIV5b oracle with (∑i=1n‍ai,1,∑i=1n‍bi,1,∗,∗,∗), (∗,∑i=1n‍ai,2,∑i=1n‍bi,2,∗,∗), (∗,∗,∑i=1n‍ai,3,∑i=1n‍bi,3,∗), (∗,∗,∗,∑i=1n‍ai,4,∑i=1n‍bi,4), where the symbol “∗” denotes dummy messages. Then B1 obtains its challenges (u~l,1,u~l,2,∗~,∗~,∗~), (∗~,u~l,3,u~l,4,∗~,∗~), (∗~,∗~,u~l,5,u~l,6,∗~), (∗~,∗~,∗~,u~l,7,u~l,8) and neglects “∗~” terms. According to the definition of ChalIV5b oracle, (u~l,1,…,u~l,8) is one of the following:
Case  1
(
b
=
0
). (g1r~l,1,g2r~l,1,g2r~l,2,g3r~l,2,g3r~l,3,g4r~l,3,g4r~l,4,g5r~l,4).
Case  2
(
b
=
1
). (g1r~l,1T∑i=1n‍ai,1,g2r~l,1T∑i=1n‍bi,1,g2r~l,2T∑i=1n‍ai,2, g3r~l,2T∑i=1n‍bi,2,g3r~l,3T∑i=1n‍ai,3,g4r~l,3T∑i=1n‍bi,3,g4r~l,4T∑i=1n‍ai,4, g5r~l,4T∑i=1n‍bi,4).
NextB1 uses the obtained (u~l,1,…,u~l,8) and the secret keys to compute e~l via (35) for A. In the meantime, B1 can also simulatedecrypt for A since it knows the secret keys. Finally, B1 outputs 1 if the event Succ occurs.
In Case1, B1 simulates game G3 perfectly for A; in Case 2, B1 simulates game G4 perfectly for A. Any difference between Pr3[Succ] and Pr4[Succ] results in B1’s advantage over the IV5 problem. Thus Lemma 25 follows.Game
G
5. It is identical to G4, except for the following differences. In theinitialize procedure of game G5, the challenger picks r∗←$[⌊N/4⌋] and α1,…,α5←$ZN randomly. As for the lth (l∈[Qe])encrypt query (fl,il), the challenger computes (ul,1,…,ul,5) as follows:(i)
(ul,1,…,ul,5)≔((g1r∗Tα1)rl,…,(g5r∗Tα5)rl)  modN2.The only difference betweenG4 and G5 is the distribution of (ul,1,…,ul,5). In game G4, (ul,1,…,ul,5)=(g1rl,…,g5rl)modN2, while in game G5, (ul,1,…,ul,5)=((g1r∗Tα1)rl,…,(g5r∗Tα5)rl)modN2. Just like Lemma 25, any difference between G4 and G5 results in a PPT adversary solving IV5 problem by invoking A. Therefore, |Pr4[Succ]-Pr5[Succ]|≤AdvGenNiv5(λ).Game
G
6. It is identical to G5, except for the following differences. In theinitialize procedure of game G6, the challenger picks k∗=(k1∗,k2∗,k3∗,k4∗) randomly. As for the lth (l∈[Qe])encrypt query (fl,il), the challenger computes kl=(kl,1,kl,2,kl,3,kl,4) and (el,1,…,el,4) in a different way:(i)
Picksl=(sl,1,sl,2,sl,3,sl,4)←$(ZN)4 and rl←$[⌊N/4⌋] randomly, and compute kl=(kl,1,kl,2,kl,3,kl,4)≔(rlk1∗+sl,1,…,rlk4∗+sl,4).(ii)
(36)el,1,…,el,4≔hil,1r∗rlTrl·k1∗-α1xil,1-α2yil,1+sl,1,…,hil,4r∗rlTrl·k4∗-α4xil,4-α5yil,4+sl,4.Clearlykl is uniformly random over (ZN)4, just like that in game G5. In the meantime, for j∈[4], we have(37)el,j=G5ul,j-xil,jul,j+1-yil,jTkl,j=gjr∗Tαj-rl·xil,jgj+1r∗Tαj+1-rl·yil,jTkl,j=gj-xil,jgj+1-yil,jr∗rlTkl,j-rl·αjxil,j+αj+1yil,j=G6hil,jr∗rlTrl·kj∗-αjxil,j-αj+1yil,j+sl,jmodN2.Thus, G6 is the same as G5, and Pr5[Succ]=Pr6[Succ].Game
G
7. It is identical to G6, except the way the challenger answers thedecrypt oracle queries (〈ai,aiae.c〉,i∈[n]). In game G7, it uses ski=(xi,1,yi,1,…,xi,4,yi,4) and ϕ(N)=(p-1)(q-1) to decrypt 〈ai,aiae.c〉, where ai=(u1,…,u5,e1,…,e4). More precisely, it computes k=(k1,…,k4) and m in the following way:(i)
(38)α1′,…,α5′≔dlogTu1ϕNϕN,…,dlogTu5ϕNϕNmodN,γ1′,…,γ4′≔dlogTe1ϕNϕN,…,dlogTe4ϕNϕNmodN,k=k1,…,k4≔α1′xi,1+α2′yi,1+γ1′,…,α4′xi,4+α5′yi,4+γ4′modN,(ii)
(39)E.c=u~1,…,u~8,e~,t/⊥⟵AIAE.Decryptk,aiae.c,ai,(iii)
(40)α~1,…,α~8≔dlogTu~1ϕNϕN,…,dlogTu~8ϕNϕNmodNs-1,γ~≔dlogTe~ϕNϕNmodNs-1,m≔α~1xi,1+α~2yi,1+α~3xi,2+α~4yi,2+α~5xi,3+α~6yi,3+α~7xi,4+α~8yi,4+γ~modNs-1.According to (8), for j∈[4], we have that(41)kj=G6dlogTejujxi,juj+1yi,j=dlogTejujxi,juj+1yi,jϕNϕNmodN=dlogTujϕN·xi,jϕN+dlogTuj+1ϕN·yi,jϕN+dlogTejϕNϕN=G7dlogTujϕNϕN︸αj′·xi,j+dlogTuj+1ϕNϕN︸αj+1′·yi,j+dlogTejϕNϕN︸γj′,m=G6dlogTe~u~1xi,1u~2yi,1u~3xi,2u~4yi,2u~5xi,3u~6yi,3u~7xi,4u~8yi,4modNs-1=G7dlogTu~1ϕNϕN︸α~1·xi,1+⋯+dlogTu~8ϕNϕN︸α~8·yi,4+dlogTe~ϕNϕN︸γ~.Hence G7 is essentially the same as G6, and Pr6[Succ]=Pr7[Succ].Game
G
8. It is identical to G7, except the way of answering thedecrypt oracle queries (〈ai,aiae.c〉, i∈[n]). More precisely, a rejection rule is added indecrypt:(i)
Ifα1′≠0∨⋯∨α5′≠0∨α~1≠0∨⋯∨α~8≠0, output ⊥.Denote byBad the event that A ever queries thedecrypt oracle with (〈ai,aiae.c〉,i∈[n]), satisfying(42)e1u1xi,1u2yi,1,…,e4u4xi,4u5yi,4∈RUN2∧AIAE.Decryptk,aiae.c,ai≠⊥(43)∧e~u~1xi,1u~2yi,1u~3xi,2u~4yi,2u~5xi,3u~6yi,3u~7xi,4u~8yi,4∈RUNs∧t=g1mmodN(44)∧α1′≠0∨⋯∨α5′≠0∨α~1≠0∨⋯∨α~8≠0.Obviously,G8 is identical to G7 unless Bad occurs. Thus, |Pr7[Succ]-Pr8[Succ]|≤Pr8[Bad].To show the computational indistinguishability ofG7 and G8, we must prove that Pr8[Bad] is negligible. To this end, Bad is divided into two subevents:(i)
Bad′: A ever queries thedecrypt oracle with (〈ai,aiae.c〉,i∈[n]), satisfying(45)Conditions42,43∧α1′≠0∨⋯∨α5′≠0.(ii)
Bad~: A ever queries thedecrypt oracle with (〈ai,aiae.c〉,i∈[n]), satisfying(46)Conditions42,43∧α1′=⋯=α5′=0∧α~1≠0∨⋯∨α~8≠0.Obviously, Pr8[Bad]≤Pr8[Bad′]+Pr8[Bad~]. We will defer the analysis of Pr8[Bad~] to subsequent games. Through the following lemma, we provide the analysis of Pr8[Bad′].Lemma 26.
One hasPr8[Bad′]≤2Qd·AdvAIAEDDHweak-int-rka(λ).Proof. Indecrypt of game G8, the challenger will reply ⊥ to A unless α1′=⋯=α5′=0 and α~1=⋯=α~8=0. Consequently, the (modϕ(N)/4) part of ski, that is, (xi,1,yi,1,…,xi,4,yi,4)modϕ(N)/4, i∈[n], and the value of ϕ(N), is enough for answeringdecrypt queries. In particular, the values of (x1,y1,…,x4,y4)modN are not necessary indecrypt.B
a
d
′ is further divided into the following two subevents:(i)
Bad′-1: A ever queries thedecrypt oracle with (〈ai,aiae.c〉,i∈[n]), satisfying(47)Conditions42,43∧α1′≠0∨⋯∨α5′≠0∧∃j∈4,αj′αj≠αj+1′αj+1modN.(ii)
Bad′-2: A ever queries thedecrypt oracle with (〈ai,aiae.c〉,i∈[n]), satisfying(48)Conditions42,43∧α1′≠0∨⋯∨α5′≠0∧α1′α1=⋯=α5′α5modN.Recall that (α1,…,α5) are chosen ininitialize.We will consider the two subevents in gameG8 separately via the following two claims.Claim 27.
One hasPr8[Bad′-1]≤Qd·AdvAIAEDDHweak-int-rka(λ).Proof.
In gameG8, the values of (x1,y1,…,x4,y4)modN are not needed indecrypt, and the computation of tl=g1mβmodN inencrypt only makes use of (x1,y1,…,x4,y4)modϕ(N)/4. Thus the only information about (x1,y1,…,x4,y4)modN leaked to A is through the computation of (el,1,…,el,4) inencrypt, which may leak the values of (α1x1+α2y1), (α2x2+α3y2), (α3x3+α4y3), (α4x4+α5y4)modN: for j∈[4],(49)el,j=hil,jr∗rlTrl·kj∗-αjxil,j-αj+1yil,j+sl,jmodN2=hil,jr∗rlTrl·kj∗-αjxj-αj+1yj︸≜k^j-αjx¯il,j-αj+1y¯il,j+sl,jmodN2.
IfBad′-1 occurs, for concreteness, say that α1′/α1≠α2′/α2modN, then (50)k1=α1′xi,1+α2′yi,1+γ1′=α1′x1+α2′y1+α1′x¯i,1+α2′y¯i,1+γ1′modN,where k1 is independent of (α1x1+α2y1)modN, thus uniformly distributed over ZN from A’s view. By Remark 23, for k=(k1,k2,k3,k4) where k1←$ZN, the probability of AIAE.Decrypt(k,aiae.c,ai)≠⊥ is upper bounded by AdvAIAEDDHweak-int-rka(λ).
ThenPr8[Bad′-1]≤Qd·AdvAIAEDDHweak-int-rka(λ) by a union bound.Claim 28.
One hasPr8[Bad′-2]≤Qd·AdvAIAEDDHweak-int-rka(λ).Proof.
Similar to the discussion in the proof for the previous claim, in gameG8, the only information about (x1,y1,…,x4,y4)modN and k∗=(k1∗,k2∗,k3∗,k4∗) involved is throughencrypt, which uses the value of k^1≔(k1∗-α1x1-α2y1), k^2≔(k2∗-α2x2-α3y2), k^3≔(k3∗-α3x3-α4y3), k^4≔(k4∗-α4x4-α5y4)modN via computing (el,1,…,el,4) (see (49)) and also uses kl=rl·(k1∗,k2∗,k3∗,k4∗)+(sl,1,…,sl,4) as the encryption key ofAIAE.Encrypt.
Note that because of the randomness of(x1,y1,…,x4,y4)modN, (k^1,k^2,k^3,k^4) are uniformly distributed and independent of (k1∗,k2∗,k3∗,k4∗). Therefore it is possible to construct an algorithm to simulatedecrypt andencrypt of game G8 without k∗=(k1∗,k2∗,k3∗,k4∗) and (x1,y1,…,x4,y4)modN. The algorithm can also simulateAIAE.Encrypt as long as it has access to a weak-INT-Fraff-RKA encryption oracle of the AIAEDDH scheme.
More precisely, we construct a PPT adversaryB2(parsAIAE), which has access to EncryptAIAE oracle, against the weak-INT-Fraff-RKA security of the AIAEDDH scheme, where parsAIAE=(N,p,q,…). B2 does not choose k∗=(k1∗,k2∗,k3∗,k4∗) ininitialize any more, and it implicitly sets k∗ to be the encryption key used by its weak-INT-Fraff-RKA challenger. B2 does not choose (x1,y1,…,x4,y4)modN either, and instead, it chooses k^=(k^1,k^2,k^3,k^4) uniformly from (ZN)4. B2 picks (x1,y1,…,x4,y4)modϕ(N)/4 and (x¯i,1,y¯i,1,…,x¯i,4,y¯i,4)∈[⌊N2/4⌋], i∈[n], randomly. To simulateencrypt, B2 can use (x¯il,j,y¯il,j,k^j)j=14 to compute (el,j)j=14 via (49) and use (x¯i,j,y¯i,j)j=14, i∈[n], to compute e~l. Note that B2 is able to compute tl=g1mβmodN, even if β=1, because it knows the (modϕ(N)/4) part of ski, that is, (xj,yj)j=14modϕ(N)/4 and (x¯i,j,y¯i,j)j=14modϕ(N)/4, i∈[n]. Then B2 submits (E.cl,ail,〈rl,sl=(sl,1,…,sl,4)〉) to its own EncryptAIAE oracle and obtains aiae.cl. The final ciphertext is 〈ail,aiae.cl〉. According to the weak-INT-Fraff-RKA security game, the EncryptAIAE oracle will encrypt E.cl with the auxiliary input ail under the transformed key kl=rl·k∗+sl; that is, the EncryptAIAE oracle behaves as AIAE.Encrypt(kl,E.cl,ail). Thus B2’s simulation ofencrypt is identical to G8. Fordecrypt, B2 answers decryption queries with the (modϕ(N)/4) part of all the secret keys and ϕ(N)=(p-1)(q-1), just like G8.
Suppose thatA ever queries thedecrypt oracle with (〈ai,aiae.c〉,i∈[n]), such that Bad′-2 occurs. For concreteness, say that r≔α1′/α1=⋯=α5′/α5≠0modN, then for j∈[4],(51)kj=αj′xi,j+αj+1′yi,j+γj′=r·αjxi,j+αj+1yi,j+γj′modN=r·kj∗-r·kj∗-αjxi,j-αj+1yi,j+γj′modN=r·kj∗-r·kj∗-αjxj-αj+1yj︸=k^j-αjx¯i,j-αj+1y¯i,j+γj′modN=r·kj∗-r·k^j-αjx¯i,j-αj+1y¯i,j+γj′︸≜sj=r·kj∗+sjmodN.Thus k=(k1,…,k4)=r·k∗+s, where s≔(s1,…,s4). B2 can compute 〈r,s=(s1,…,s4)〉 as above using (x¯i,j,y¯i,j,k^j)j=14 and outputs (ai,〈r,s〉,aiae.c) to its weak-INT-Fraff-RKA challenger as a forgery. We analyze the success probability of B2 as follows.(i)
Firstly, a valid decryption query fromA satisfies 〈ai,aiae.c〉≠〈ail,aiae.cl〉 for all l∈[Qe]; thus (ai,〈r,s〉,aiae.c)≠(ail,〈rl,sl〉,aiae.cl) will hold for all l∈[Qe]; that is, B2 always outputs a fresh forgery.(ii)
Secondly, ifai=ail for some l∈[Qe], then it is easy to have that α1′=α1·rl,…,α5′=α5·rl and thus r=rl. Furthermore for j∈[4], it clearly holds that γj′=rl·(k^j-αjx¯i,j-αj+1y¯i,j)+sl,j (cf. (49)); thus sj=-r·(k^j-αjx¯i,j-αj+1y¯i,j)+γj′=sl,j and s=sl. That is, if ai=ail for some l∈[Qe], then it holds that 〈r,s〉=〈rl,sl〉. Obviously it satisfies the special rule required for the weak-INT-Fraff-RKA security.(iii)
Finally, ifBad′-2 occurs in this decryption query, then AIAE.Decrypt(k,aiae.c,ai)≠⊥, where k=r·k∗+s, will imply that B2’s forgery is successful.
By a union bound, we have thatPr8[Bad′-2]≤Qd·AdvAIAEDDH,B2weak-int-rka(λ).In conclusion, Lemma26 follows from the above two claims.This completes the proof of Lemma26.Game
G
9. It is identical to G8, except for the following differences. In theinitialize procedure of game G9, the challenger picks an independent k¯∗=(k¯1∗,k¯2∗,k¯3∗,k¯4∗)←$(ZN)4 besides k∗=(k1∗,k2∗,k3∗,k4∗). As for the lth (l∈[Qe])encrypt oracle query (fl,il), the challenger employs a different key for AIAEDDH in the computation of aiae.cl:(i)
k¯l≔(rlk¯1∗+sl,1,…,rlk¯4∗+sl,4);(ii)
aiae.cl←$AIAE.Encrypt(k¯l,E.cl,ail).We stress that the challenger still employsk∗=(k1∗,k2∗,k3∗,k4∗) in the computation of (el,1,…,el,4).InG8, the only place that involves the value of (x1,y1,…,x4,y4)modN is in the computation of (el,1,…,el,4) in theencrypt oracle. Specifically, for j∈[4],(52)el,j=hil,jr∗rlTrl·kj∗-αjxil,j-αj+1yil,j+sl,jmodN2=hil,jr∗rlTrl·kj∗-αjxj-αj+1yj-αjx¯il,j-αj+1y¯il,j+sl,jmodN2.Note that the computation of tl=g1mβmodN in theencrypt oracle only involves (x1,y1,…,x4,y4)modϕ(N)/4. Moreover, observe that neither k∗=(k1∗,k2∗,k3∗,k4∗) nor (x1,y1,…,x4,y4)modN is used indecrypt. Hence, k∗=(k1∗,k2∗,k3∗,k4∗) is perfectly hidden by (x1,y1,…,x4,y4)modN.Therefore, the challenger could always employ anotherk¯∗=(k¯1∗,…,k¯4∗) in the computation of k¯l and utilize k¯l in the AIAEDDH’s encryption in theencrypt oracle, as in G9.Then gameG8 and game G9 are essentially the same from A’s view, so Pr8[Succ]=Pr9[Succ] and Pr8[Bad~]=Pr9[Bad~].Game
G
10. It is identical to G9, except the way the challenger answers the lth (l∈[Qe])encrypt oracle query (fl,il). More precisely, in game G10, the challenger computes aiae.cl in the following way:(i)
aiae.cl←$AIAE.Encrypt(k¯l,0λM,ail).Observe that, inG9 and G10, k¯∗ is employed only in the AIAEDDH encryption, where it uses k¯l=rl·k¯∗+sl as the encryption key with sl=(sl,1,…,sl,4). Any difference between G9 and G10 results in a PPT adversary against the IND-Fraff-RKA security of the AIAEDDH scheme. Therefore, |Pr9[Succ]-Pr10[Succ]|≤AdvAIAEDDHind-rka(λ) and |Pr9[Bad~]-Pr10[Bad~]|≤AdvAIAEDDHind-rka(λ).Finally inG10, the challenger always computes the AIAEDDH encryption of 0λM in theencrypt oracle, so β is perfectly hidden from A’s view. Thus, Pr10[Succ]=1/2.To complete the proof of Theorem24, we only need to prove the following lemma.Lemma 29.
One hasPr10[Bad~]≤(Qd+1)·2-Ω(λ)+AdvGenNdl(λ).Proof. In G10, neitherdecrypt norencrypt uses the values of (x1,y1,…,x4,y4)modϕ(N)/4. The only information leaked about them lies in the public keys pki, i∈[n], which reveal the values of (w1x1+w2y1), (w2x2+w3y2), (w3x3+w4y3), (w4x4+w5y4)modϕ(N)/4, where we denote wj≔dlogggjmodϕ(N)/4 for some base g∈SCRNs, j∈[5].B
a
d
~ is further divided into the following disjoint two subevents:(i)
Bad~-1: A ever queries thedecrypt oracle with (〈ai,aiae.c〉,i∈[n]), satisfying(53)Conditions42,43∧α1′=⋯=α5′=0∧α~1≠0∨⋯∨α~8≠0∧α~1w1≠α~2w2∨α~3w2≠α~4w3∨α~5w3≠α~6w4∨α~7w4≠α~8w5.(ii)
Bad~-2: A ever queries thedecrypt oracle with (〈ai,aiae.c〉,i∈[n]), satisfying(54)Conditions42,43∧α1′=⋯=α5′=0∧α~1≠0∨⋯∨α~8≠0∧α~1w1=α~2w2∧α~3w2=α~4w3∧α~5w3=α~6w4∧α~7w4=α~8w5.We will analyze the two subevents in gameG10 separately via the following two claims.Claim 30.
One hasPr10[Bad~-1]≤Qd·2-Ω(λ).Proof.
IfBad~-1 occurs, for concreteness, say that α~1/w1≠α~2/w2, then (55)g1m=g1α~1xi,1+α~2yi,1+⋯=g1α~1x1+α~2y1+α~1x¯i,1+α~2y¯i,1+⋯modϕN/4modN,and (α~1x1+α~2y1)modϕ(N)/4 is independent of (w1x1+w2y1)modϕ(N)/4. Thus g1m is uniformly distributed over SCRNs from A’s view, and t=g1mmodN will not hold except with negligible probability 2-Ω(λ).
Then according to a union bound,Pr10[Bad~-1]≤Qd·2-Ω(λ).Claim 31.
One hasPr10[Bad~-2]≤AdvGenNdl(λ)+2-Ω(λ).Proof.
In gameG10, if Bad~-2 occurs, then we can construct a PPT adversary B3(N,p,q,g,h) to compute the discrete logarithm of h based on g, where g,h∈SCRNs. With (N,p,q,g,h), B3 simulatesinitialize as follows. B3 picks zj, zj′ uniformly from [ϕ(N)/4] and sets gj≔gzjhzj′ for j∈[5]. Then gj is uniformly distributed over SCRNs. Next, B3 samples secret keys and computes public keys just the same way asinitialize in G10. Since B3 knows all the secret keys together with ϕ(N)=(p-1)(q-1), B3 can perfectly simulatesencrypt anddecrypt the same way as G10 does. Furthermore, zj′ is hidden by zj perfectly from A’ view. If we denote w≔dlogghmodϕ(N)/4, then for j∈[5], wj=dlogggj=zj+wzj′modϕ(N)/4.
IfBad~-2 occurs indecrypt, for concreteness, say that α~1/w1=α~2/w2≠0modϕ(N)/4, that is, g1α~2=g2α~1≠1, then B3 can compute w by solving the equation w1α~2=w2α~1modϕ(N)/4, or equivalently, (56)z1α~2+wz1′α~2=z2α~1+wz2′α~1modϕN4.Since zj′ is hidden from the point of view of A, (z1′α~2-z2′α~1)modϕ(N)/4 is multiplicative invertible except with negligible probability 2-Ω(λ). Thus B3 will succeed in computing the discrete logarithm of h based on g and output w=(z1′α~2-z2′α~1)-1·(z2α~1-z1α~2)modϕ(N)/4 to its challenger. Clearly, we have Pr10[Bad~-2]≤AdvGenN,B3dl(λ)+2-Ω(λ).In conclusion, Lemma29 follows from the above two claims.This completes the proof of Lemma29.In all, we proved then-KDM[Faff]-CCA security.This completes the proof of Theorem24.


## 5. PKE withn-KDM[Fpolyd]-CCA Security

### 5.1. The Basic Idea

We extend the construction ofn-KDM[Faff]-CCA secure PKE to that of n-KDM[Fpolyd]-CCA secure PKE. We allow adversaries to submit polynomial function in Fpolyd in the form ofmodular arithmetic circuit (MAC) [10], which is a polynomial-sized circuit computing f∈Fpolyd. We stress that there is no a priori bound on the size of modular arithmetic circuits. The only requirement is that the degree d of the polynomials is a priori bounded. We still follow the approach in Figure 1 in our PKE construction. Indeed, we use the same AIAEDDH andKEM as those in the previous n-KDM[Faff]-CCA secure PKE in Figure 8. We only need to construct a new E to serve as an entropy filter for the polynomial function set. Moreover, the new E should employ the same pair of public and secret keys withKEM. That is, we have ski=(xi,1,yi,1,…,xi,4,yi,4) and pki=(hi,1,…,hi,4) with hi,1=g1-xi,1g2-yi,1,…,hi,4=g4-xi,4g5-yi,4modNs, for i∈[n].


### 5.2. Reducing Polynomials of 8n Variables to Polynomials of 8 Variables

How to Reduce 8n-Variable Polynomial
f
l. In the n-KDM[Fpolyd]-CCA security game, the adversary is allowed to query theencrypt oracle with (fl,il∈[n]) for l∈[Qe]. Note that the function fl is a polynomial in the n secret keys (xi,j,yi,j)i∈[n],j∈[4]; thus fl has 8n variables and is of degree at most d. The bad news is that fl contains as many as 8n+d8n=Θ(d8n) monomial functions. Note that this number can be exponentially large.The good news is that we found an efficient way to greatly reduce the number of monomials fromΘ(d8n) to Θ(d8). In particular, the polynomial fl((xi,j,yi,j)i∈[n],j∈[4]) can always be changed to a polynomial fl′((xil,j,yil,j)j∈[4]) of 8 variables, consisting of at most 8+d8=Θ(d8) monomial functions. Now this number is polynomial in λ.The efficient method for reducing the8n-variable polynomial fl is as follows. In theinitialize procedure, ski could be computed as xi,j≔xj+x¯i,j and yi,j≔yj+y¯i,jmod⌊N2/4⌋ for i∈[n] and j∈[4]. By using (x¯i,j,y¯i,j)i∈[n],j∈[4], (xi,j,yi,j)i∈[n],j∈[4] could be represented as shifts of (xil,j,yil,j)j∈[4]; that is, (57)xi,j=xil,j+x¯i,j-x¯il,j,yi,j=yil,j+y¯i,j-y¯il,j.Consequently, fl in 8n variables (xi,j,yi,j)i∈[n],j∈[4] can be reduced to fl′ in 8 variables (xil,j,yil,j)j∈[4]; that is,(58)flxi,j,yi,ji∈n,j∈4=flxil,j+x¯i,j-x¯il,j︸xi,j,yil,j+y¯i,j-y¯il,j︸yi,ji∈n,j∈4=fl′xil,j,yil,jj∈4=∑0≤c1+⋯+c8≤dac1,…,c8·xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8.The degree of the resulting polynomial fl′ is still upper bounded by d. Moreover, the coefficients a(c1,…,c8) of fl′ are completely determined by the shifts (x¯i,j,y¯i,j)i∈[n],j∈[4].How to Determine Coefficients
a
(
c
1
,
…
,
c
8
)
for
f
l
′
Efficiently with Only
(
x
¯
i
,
j
,
y
¯
i
,
j
)
i
∈
[
n
]
,
j
∈
[
4
]. In order to compute the coefficients a(c1,…,c8) of fl′, we can repeat the following procedure:(i)
Choose(xil,j,yil,j)j∈[4] uniformly.(ii)
Feed modular arithmetic circuit (which functions asfl) with (xil,j+x¯i,j-x¯il,j,yil,j+y¯i,j-y¯il,j)i∈[n],j∈[4] as input. We stress that (x¯i,j,y¯i,j)i∈[n],j∈[4] are always the ones chosen ininitialize.(iii)
Record the output of the circuit.Repeating the above procedure about8+d8=Θ(d8) times, all the coefficients a(c1,…,c8) can be extracted through solving a linear system of equations:(59)flxil,j+x¯i,j-x¯il,j,yil,j+y¯i,j-y¯il,ji∈n,j∈4=∑0≤c1+⋯+c8≤dac1,…,c8·xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8.The overall time complexity for computing the coefficients a(c1,…,c8) is polynomial in λ.


### 5.3. How to DesignE: A Warmup

To illustrate the ideas behind our construction, we take a simple case as consideration: constructE for a concrete type of monomial function; that is,(60)fl′xil,j,yil,jj∈4=a·xil,1yil,1xil,2yil,2xil,3yil,3xil,4yil,4.Algorithms E.Encrypt and E.Decrypt are shown in Figure 9.Figure 9
E designed for a concrete type of monomial functions a⋅xil,1yil,1xil,2yil,2xil,3yil,3xil,4yil,4.Security Proof. Now we sketch the proof of KDM-CCA security for this concrete type of monomial functions, that is, a·xil,1yil,1xil,2yil,2xil,3yil,3xil,4yil,4. The proof is similar to that for Theorem 24 (cf. Table 2). The only difference lies in games G3-G4, which are related to the building block E. Next, we will replace G3-G4 with the following hybrids (i.e., Hybrid  1–Hybrid  3), as shown in Figure 10. Concretely, the E.Encrypt part ofencrypt is changed in a computationally indistinguishable way, so that it can serve as an entropy filter for this concrete monomial function, reserving the entropy of (x1,y1,…,x4,y4)modN.Figure 10
Security proof ofE.Encrypt as an entropy filter for concrete monomials a⋅xil,1yil,1xil,2yil,2xil,3yil,3xil,4yil,4.Suppose that the adversary submits(fl,il∈[n]) to theencrypt oracle. Our purpose is to eliminate the use of (xj,yj)j=14modN in the computation of E.Encrypt(pkil,fl((xi,j,yi,j)i∈[n],j∈[4])), so the entropy of (xj,yj)j=14modN is reserved.Hybrid  0. In theinitialize procedure, the secret keys are computed as xi,j≔xj+x¯i,j and yi,j≔yj+y¯i,jmod⌊N2/4⌋ for i∈[n], j∈[4]. This hybrid is identical to G2 in the proof of Theorem 24.Hybrid  1. Using (x¯i,j,y¯i,j)i∈[n],j∈[4], reduce (fl,il∈[n]) to (fl′,il∈[n]), and calculate the coefficient a of fl′, such that(61)fl′xil,j,yil,jj∈4=a·xil,1yil,1xil,2yil,2xil,3yil,3xil,4yil,4.Hybrid  2. Implement E.Encrypt using skil=(xil,j,yil,j)j∈[4]. This hybrid corresponds to G3 in the proof of Theorem 24.(i)
InvokeE.Encrypt to set uptable.(ii)
InvokeE.Decrypt to compute v^0,…,v^8 fromtable.(iii)
Employv^8 rather than v~8 in the computation of e~, that is, e~≔v^8·Tfl′((xil,j,yil,j)j∈[4])modNs, and compute t≔g1fl′((xil,j,yil,j)j∈[4])modN.Clearly,v^0,…,v^8 computed via E.Decrypt are the same as v~0,…,v~8 computed via E.Encrypt. Therefore, this is just a conceptual change.Hybrid  3. This hybrid corresponds to G4 in the proof of Theorem 24.(i)
table is computed similarly as that in E.Encrypt, except for a small difference. More precisely, intable, the entry located in row 1 and column 1 is now computed as u^1,1=(u~1,1Ta)·v~0 rather than u^1,1=u~1,1·v~0. By the IV5 assumption, this difference is computationally undetectable (see Appendix B for a formal analysis).(ii)
InvokeE.Decrypt to compute v^0,…,v^8 fromtable.(iii)
Computee~≔v^8·Tfl′((xil,j,yil,j)j∈[4])modNs, and t≔g1fl′((xil,j,yil,j)j∈[4])modN.Through a routine calculation, we havev^0=v~0,v^1=v~1·T-axil,1,v^2=v~2·T-axil,1yil,1,…,v^8=v~8·T-axil,1yil,1⋯xil,4yil,4=v~8·T-fl′((xil,j,yil,j)j∈[4]); hence e~=v^8·Tfl′((xil,j,yil,j)j∈[4])=v~8.Consequently, Hybrid  3 can be implemented in an equivalent way.Hybrid  3 (Equivalent Form). (i)table is computed similarly as that in E.Encrypt, except for a small difference. More precisely, the entry located in row 1 and column 1 intable is now computed as u^1,1=(u~1,1Ta)·v~0 rather than u^1,1=u~1,1·v~0.(ii) Computee~≔v~8modNs, and t≔g1fl′((xil,j,yil,j)j∈[4])modϕ(N)/4modN.Now(x1,y1,…,x4,y4)modN is not used in E.Encrypt any more.After these computationally indistinguishable changes, theE.Encrypt part of theencrypt oracle reserves the entropy of (x1,y1,…,x4,y4)modN.Similarly, we can change thedecrypt oracle in a computationally indistinguishable way, so that (xj,yj)j=14modN is not involved at all. More precisely,decrypt uses only the (modϕ(N)/4) part of secret key and ϕ(N). This change corresponds to G7-G8 in the proof of Theorem 24. Loosely speaking, ϕ(N) is used to ensure that all entries intable are elements in SCRNs. If this is not the case,decrypt rejects immediately. Consequently, thedecrypt oracle leaks nothing about (x1,y1,…,x4,y4)modN. We can also show the computational indistinguishability of this change, through a similar analysis as that of Pr⁡[Bad] in the proof of Theorem 24.


### 5.4. The GeneralE Designed for Fpolyd

In Section5.3, we presented the construction of E for a concrete type of monomial functions. Generally, a polynomial function fl′ of degree d might contain as many as 8+d8=Θ(d8) monomials. In order to construct a general E for the set Fpolyd of polynomial functions, we must handle all types of monomial functions. To this end, we generate a table for each type of nonconstant monomial and associate it with a v~, which is named as atitle. Algorithms E.Encrypt and E.Decrypt are shown in Figure 11.Figure 11
(a)E.Encrypt (left) and E.Decrypt (right) of E designed for Fpolyd; (b)TableGen, which generates table(c) together with a title v~(c); (c)CalculateV, which calculates a title v^(c) from table(c) using secret key.
(a)
(b)
(c)Neglecting the coefficients of monomials, there are8+d8-1 types of nonconstant monomial functions whose degrees are at most d. For each nonconstant monomial type xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8, we can associate it with a degree tuple c=(c1,…,c8). Let S denote the set of all such degree tuples, that is, S≔{c=c1,…,c8∣1≤c1+⋯+c8≤d}.For each degree tuplec=(c1,…,c8)∈S, which corresponds to the monomial xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8, we generate table(c) and v~(c) by invoking the algorithmTableGen shown in Figure 11. Finally in e~, Tm is hidden by the product of all the titles.Meanwhile, with the help of the secret keysk=(x1,y1,…,x4,y4), we can recover v^(c)=v~(c) from table(c) by invoking the algorithmCalculateV in Figure 11. Thus, the titles (v~(c))c∈S could always be extracted from (table(c))c∈S one by one, and finally m is recovered.Security Proof. We sketch the proof of KDM[Fpolyd]-CCA security for the set of polynomial functions. The proof is also similar to that for Theorem 24 (cf. Table 2). The only difference lies in games G3-G4. Next, we will replace G3-G4 with the following hybrids (Hybrid  1–Hybrid  3). Specifically, the E.Encrypt part ofencrypt is changed in a computationally indistinguishable way, so that it can serve as an entropy filter for polynomial functions of degree at most d, reserving the entropy of (x1,y1,…,x4,y4)modN.Suppose that the adversary submits(fl,il∈[n]) to theencrypt oracle. Our purpose is to eliminate the use of (xj,yj)j=14modN in the computation of E.Encrypt(pkil,fl((xi,j,yi,j)i∈[n],j∈[4])), so the entropy of (xj,yj)j=14modN is reserved.Hybrid  0. In theinitialize procedure, the secret keys are computed as xi,j≔xj+x¯i,j and yi,j≔yj+y¯i,jmod⌊N2/4⌋ for i∈[n], j∈[4]. This hybrid is identical to G2 in the proof of Theorem 24.Hybrid  1. Using (x¯i,j,y¯i,j)i∈[n],j∈[4], reduce (fl,il∈[n]) to (fl′,il∈[n]), and compute the coefficients a(c1,…,c8) of fl′, as discussed in Section 5.2. Then(62)fl′xil,j,yil,jj∈4=∑c1,…,c8∈Sac1,…,c8·xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8+δ,where δ is the constant term a(0,…,0) of fl′.Hybrid  2. Implement E.Encrypt using skil=(xil,j,yil,j)j∈[4]. This hybrid corresponds to G3 in the proof of Theorem 24.(i)
For eachc=(c1,…,c8)∈S
(1)
invoke(table(c),v~(c))←$TableGen(pkil,c),(2)
invokev^(c)←CalculateV(skil,table(c),c).(ii)
Employ(v^(c))c∈S rather than (v~(c))c∈S in the computation of e~, that is, e~≔∏c∈S‍v^(c)·Tfl′((xil,j,yil,j)j∈[4])modNs, and compute t≔g1fl′((xil,j,yil,j)j∈[4])modN.Clearly, for eachc=(c1,…,c8)∈S, v^(c) computed viaCalculateV is the same as v~(c) computed viaTableGen. Therefore, this change is just conceptual.Hybrid  3. This hybrid corresponds to G4 in the proof of Theorem 24.(i)
For eachc=(c1,…,c8)∈S
(1)
table(c) is computed by (table(c),v~(c))←$TableGen(pkil,c), except for a small difference; more precisely, in table(c), the entry located in row 1 and column j≔min{i∣1≤i≤8,ci≠0} is now computed as u^1,j=(u~1,jTa(c1,…,c8))·v~0 rather than u^1,j=u~1,j·v~0; by the IV5 assumption, this difference is computationally undetectable,(2)
extractv^(c) from the (modified) table(c) by invoking v^(c)←CalculateV(skil,table(c),c).(ii)
Computee~≔∏c∈S‍v^(c)·Tfl′((xil,j,yil,j)j∈[4])modNs, and t≔g1fl′((xil,j,yil,j)j∈[4])modN.Through a routine calculation, for eachc=(c1,…,c8)∈S, we have (63)v^c=v~c·T-ac1,…,c8xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8.Hence,(64)e~=∏c∈Sv^c·Tfl′xil,j,yil,jj∈4=∏c∈Sv~c·∏c∈ST-ac1,…,c8xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8·Tfl′xil,j,yil,jj∈4=∏c∈Sv~c·Tδ.Consequently, Hybrid  3 can be implemented in an equivalent way.Hybrid  3 (Equivalent Form). (i) For each c=(c1,…,c8)∈Stable(c) is computed by (table(c),v~(c))←$TableGen(pkil,c), except for a small difference. More precisely, in table(c), the entry located in row 1 and column j≔min{i∣1≤i≤8,ci≠0} is now computed as u^1,j=(u~1,jTa(c1,…,c8))·v~0 rather than u^1,j=u~1,j·v~0.(ii) Computee~≔∏c∈S‍v~(c)·TδmodNs, and t≔g1fl′((xil,j,yil,j)j∈4)modϕ(N)/4modN.Now(x1,y1,…,x4,y4)modN is not used in E.Encrypt any more.After these computationally indistinguishable changes, theE.Encrypt part of theencrypt oracle reserves the entropy of (x1,y1,…,x4,y4)modN.With a similar argument as that in Section5.3, we can change thedecrypt oracle in a computationally indistinguishable way, so that (xj,yj)j=14modN is not employed at all.


## 5.1. The Basic Idea

We extend the construction ofn-KDM[Faff]-CCA secure PKE to that of n-KDM[Fpolyd]-CCA secure PKE. We allow adversaries to submit polynomial function in Fpolyd in the form ofmodular arithmetic circuit (MAC) [10], which is a polynomial-sized circuit computing f∈Fpolyd. We stress that there is no a priori bound on the size of modular arithmetic circuits. The only requirement is that the degree d of the polynomials is a priori bounded. We still follow the approach in Figure 1 in our PKE construction. Indeed, we use the same AIAEDDH andKEM as those in the previous n-KDM[Faff]-CCA secure PKE in Figure 8. We only need to construct a new E to serve as an entropy filter for the polynomial function set. Moreover, the new E should employ the same pair of public and secret keys withKEM. That is, we have ski=(xi,1,yi,1,…,xi,4,yi,4) and pki=(hi,1,…,hi,4) with hi,1=g1-xi,1g2-yi,1,…,hi,4=g4-xi,4g5-yi,4modNs, for i∈[n].


## 5.2. Reducing Polynomials of 8n Variables to Polynomials of 8 Variables

How to Reduce 8n-Variable Polynomial
f
l. In the n-KDM[Fpolyd]-CCA security game, the adversary is allowed to query theencrypt oracle with (fl,il∈[n]) for l∈[Qe]. Note that the function fl is a polynomial in the n secret keys (xi,j,yi,j)i∈[n],j∈[4]; thus fl has 8n variables and is of degree at most d. The bad news is that fl contains as many as 8n+d8n=Θ(d8n) monomial functions. Note that this number can be exponentially large.The good news is that we found an efficient way to greatly reduce the number of monomials fromΘ(d8n) to Θ(d8). In particular, the polynomial fl((xi,j,yi,j)i∈[n],j∈[4]) can always be changed to a polynomial fl′((xil,j,yil,j)j∈[4]) of 8 variables, consisting of at most 8+d8=Θ(d8) monomial functions. Now this number is polynomial in λ.The efficient method for reducing the8n-variable polynomial fl is as follows. In theinitialize procedure, ski could be computed as xi,j≔xj+x¯i,j and yi,j≔yj+y¯i,jmod⌊N2/4⌋ for i∈[n] and j∈[4]. By using (x¯i,j,y¯i,j)i∈[n],j∈[4], (xi,j,yi,j)i∈[n],j∈[4] could be represented as shifts of (xil,j,yil,j)j∈[4]; that is, (57)xi,j=xil,j+x¯i,j-x¯il,j,yi,j=yil,j+y¯i,j-y¯il,j.Consequently, fl in 8n variables (xi,j,yi,j)i∈[n],j∈[4] can be reduced to fl′ in 8 variables (xil,j,yil,j)j∈[4]; that is,(58)flxi,j,yi,ji∈n,j∈4=flxil,j+x¯i,j-x¯il,j︸xi,j,yil,j+y¯i,j-y¯il,j︸yi,ji∈n,j∈4=fl′xil,j,yil,jj∈4=∑0≤c1+⋯+c8≤dac1,…,c8·xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8.The degree of the resulting polynomial fl′ is still upper bounded by d. Moreover, the coefficients a(c1,…,c8) of fl′ are completely determined by the shifts (x¯i,j,y¯i,j)i∈[n],j∈[4].How to Determine Coefficients
a
(
c
1
,
…
,
c
8
)
for
f
l
′
Efficiently with Only
(
x
¯
i
,
j
,
y
¯
i
,
j
)
i
∈
[
n
]
,
j
∈
[
4
]. In order to compute the coefficients a(c1,…,c8) of fl′, we can repeat the following procedure:(i)
Choose(xil,j,yil,j)j∈[4] uniformly.(ii)
Feed modular arithmetic circuit (which functions asfl) with (xil,j+x¯i,j-x¯il,j,yil,j+y¯i,j-y¯il,j)i∈[n],j∈[4] as input. We stress that (x¯i,j,y¯i,j)i∈[n],j∈[4] are always the ones chosen ininitialize.(iii)
Record the output of the circuit.Repeating the above procedure about8+d8=Θ(d8) times, all the coefficients a(c1,…,c8) can be extracted through solving a linear system of equations:(59)flxil,j+x¯i,j-x¯il,j,yil,j+y¯i,j-y¯il,ji∈n,j∈4=∑0≤c1+⋯+c8≤dac1,…,c8·xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8.The overall time complexity for computing the coefficients a(c1,…,c8) is polynomial in λ.


## 5.3. How to DesignE: A Warmup

To illustrate the ideas behind our construction, we take a simple case as consideration: constructE for a concrete type of monomial function; that is,(60)fl′xil,j,yil,jj∈4=a·xil,1yil,1xil,2yil,2xil,3yil,3xil,4yil,4.Algorithms E.Encrypt and E.Decrypt are shown in Figure 9.Figure 9
E designed for a concrete type of monomial functions a⋅xil,1yil,1xil,2yil,2xil,3yil,3xil,4yil,4.Security Proof. Now we sketch the proof of KDM-CCA security for this concrete type of monomial functions, that is, a·xil,1yil,1xil,2yil,2xil,3yil,3xil,4yil,4. The proof is similar to that for Theorem 24 (cf. Table 2). The only difference lies in games G3-G4, which are related to the building block E. Next, we will replace G3-G4 with the following hybrids (i.e., Hybrid  1–Hybrid  3), as shown in Figure 10. Concretely, the E.Encrypt part ofencrypt is changed in a computationally indistinguishable way, so that it can serve as an entropy filter for this concrete monomial function, reserving the entropy of (x1,y1,…,x4,y4)modN.Figure 10
Security proof ofE.Encrypt as an entropy filter for concrete monomials a⋅xil,1yil,1xil,2yil,2xil,3yil,3xil,4yil,4.Suppose that the adversary submits(fl,il∈[n]) to theencrypt oracle. Our purpose is to eliminate the use of (xj,yj)j=14modN in the computation of E.Encrypt(pkil,fl((xi,j,yi,j)i∈[n],j∈[4])), so the entropy of (xj,yj)j=14modN is reserved.Hybrid  0. In theinitialize procedure, the secret keys are computed as xi,j≔xj+x¯i,j and yi,j≔yj+y¯i,jmod⌊N2/4⌋ for i∈[n], j∈[4]. This hybrid is identical to G2 in the proof of Theorem 24.Hybrid  1. Using (x¯i,j,y¯i,j)i∈[n],j∈[4], reduce (fl,il∈[n]) to (fl′,il∈[n]), and calculate the coefficient a of fl′, such that(61)fl′xil,j,yil,jj∈4=a·xil,1yil,1xil,2yil,2xil,3yil,3xil,4yil,4.Hybrid  2. Implement E.Encrypt using skil=(xil,j,yil,j)j∈[4]. This hybrid corresponds to G3 in the proof of Theorem 24.(i)
InvokeE.Encrypt to set uptable.(ii)
InvokeE.Decrypt to compute v^0,…,v^8 fromtable.(iii)
Employv^8 rather than v~8 in the computation of e~, that is, e~≔v^8·Tfl′((xil,j,yil,j)j∈[4])modNs, and compute t≔g1fl′((xil,j,yil,j)j∈[4])modN.Clearly,v^0,…,v^8 computed via E.Decrypt are the same as v~0,…,v~8 computed via E.Encrypt. Therefore, this is just a conceptual change.Hybrid  3. This hybrid corresponds to G4 in the proof of Theorem 24.(i)
table is computed similarly as that in E.Encrypt, except for a small difference. More precisely, intable, the entry located in row 1 and column 1 is now computed as u^1,1=(u~1,1Ta)·v~0 rather than u^1,1=u~1,1·v~0. By the IV5 assumption, this difference is computationally undetectable (see Appendix B for a formal analysis).(ii)
InvokeE.Decrypt to compute v^0,…,v^8 fromtable.(iii)
Computee~≔v^8·Tfl′((xil,j,yil,j)j∈[4])modNs, and t≔g1fl′((xil,j,yil,j)j∈[4])modN.Through a routine calculation, we havev^0=v~0,v^1=v~1·T-axil,1,v^2=v~2·T-axil,1yil,1,…,v^8=v~8·T-axil,1yil,1⋯xil,4yil,4=v~8·T-fl′((xil,j,yil,j)j∈[4]); hence e~=v^8·Tfl′((xil,j,yil,j)j∈[4])=v~8.Consequently, Hybrid  3 can be implemented in an equivalent way.Hybrid  3 (Equivalent Form). (i)table is computed similarly as that in E.Encrypt, except for a small difference. More precisely, the entry located in row 1 and column 1 intable is now computed as u^1,1=(u~1,1Ta)·v~0 rather than u^1,1=u~1,1·v~0.(ii) Computee~≔v~8modNs, and t≔g1fl′((xil,j,yil,j)j∈[4])modϕ(N)/4modN.Now(x1,y1,…,x4,y4)modN is not used in E.Encrypt any more.After these computationally indistinguishable changes, theE.Encrypt part of theencrypt oracle reserves the entropy of (x1,y1,…,x4,y4)modN.Similarly, we can change thedecrypt oracle in a computationally indistinguishable way, so that (xj,yj)j=14modN is not involved at all. More precisely,decrypt uses only the (modϕ(N)/4) part of secret key and ϕ(N). This change corresponds to G7-G8 in the proof of Theorem 24. Loosely speaking, ϕ(N) is used to ensure that all entries intable are elements in SCRNs. If this is not the case,decrypt rejects immediately. Consequently, thedecrypt oracle leaks nothing about (x1,y1,…,x4,y4)modN. We can also show the computational indistinguishability of this change, through a similar analysis as that of Pr⁡[Bad] in the proof of Theorem 24.


## 5.4. The GeneralE Designed for Fpolyd

In Section5.3, we presented the construction of E for a concrete type of monomial functions. Generally, a polynomial function fl′ of degree d might contain as many as 8+d8=Θ(d8) monomials. In order to construct a general E for the set Fpolyd of polynomial functions, we must handle all types of monomial functions. To this end, we generate a table for each type of nonconstant monomial and associate it with a v~, which is named as atitle. Algorithms E.Encrypt and E.Decrypt are shown in Figure 11.Figure 11
(a)E.Encrypt (left) and E.Decrypt (right) of E designed for Fpolyd; (b)TableGen, which generates table(c) together with a title v~(c); (c)CalculateV, which calculates a title v^(c) from table(c) using secret key.
(a)
(b)
(c)Neglecting the coefficients of monomials, there are8+d8-1 types of nonconstant monomial functions whose degrees are at most d. For each nonconstant monomial type xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8, we can associate it with a degree tuple c=(c1,…,c8). Let S denote the set of all such degree tuples, that is, S≔{c=c1,…,c8∣1≤c1+⋯+c8≤d}.For each degree tuplec=(c1,…,c8)∈S, which corresponds to the monomial xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8, we generate table(c) and v~(c) by invoking the algorithmTableGen shown in Figure 11. Finally in e~, Tm is hidden by the product of all the titles.Meanwhile, with the help of the secret keysk=(x1,y1,…,x4,y4), we can recover v^(c)=v~(c) from table(c) by invoking the algorithmCalculateV in Figure 11. Thus, the titles (v~(c))c∈S could always be extracted from (table(c))c∈S one by one, and finally m is recovered.Security Proof. We sketch the proof of KDM[Fpolyd]-CCA security for the set of polynomial functions. The proof is also similar to that for Theorem 24 (cf. Table 2). The only difference lies in games G3-G4. Next, we will replace G3-G4 with the following hybrids (Hybrid  1–Hybrid  3). Specifically, the E.Encrypt part ofencrypt is changed in a computationally indistinguishable way, so that it can serve as an entropy filter for polynomial functions of degree at most d, reserving the entropy of (x1,y1,…,x4,y4)modN.Suppose that the adversary submits(fl,il∈[n]) to theencrypt oracle. Our purpose is to eliminate the use of (xj,yj)j=14modN in the computation of E.Encrypt(pkil,fl((xi,j,yi,j)i∈[n],j∈[4])), so the entropy of (xj,yj)j=14modN is reserved.Hybrid  0. In theinitialize procedure, the secret keys are computed as xi,j≔xj+x¯i,j and yi,j≔yj+y¯i,jmod⌊N2/4⌋ for i∈[n], j∈[4]. This hybrid is identical to G2 in the proof of Theorem 24.Hybrid  1. Using (x¯i,j,y¯i,j)i∈[n],j∈[4], reduce (fl,il∈[n]) to (fl′,il∈[n]), and compute the coefficients a(c1,…,c8) of fl′, as discussed in Section 5.2. Then(62)fl′xil,j,yil,jj∈4=∑c1,…,c8∈Sac1,…,c8·xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8+δ,where δ is the constant term a(0,…,0) of fl′.Hybrid  2. Implement E.Encrypt using skil=(xil,j,yil,j)j∈[4]. This hybrid corresponds to G3 in the proof of Theorem 24.(i)
For eachc=(c1,…,c8)∈S
(1)
invoke(table(c),v~(c))←$TableGen(pkil,c),(2)
invokev^(c)←CalculateV(skil,table(c),c).(ii)
Employ(v^(c))c∈S rather than (v~(c))c∈S in the computation of e~, that is, e~≔∏c∈S‍v^(c)·Tfl′((xil,j,yil,j)j∈[4])modNs, and compute t≔g1fl′((xil,j,yil,j)j∈[4])modN.Clearly, for eachc=(c1,…,c8)∈S, v^(c) computed viaCalculateV is the same as v~(c) computed viaTableGen. Therefore, this change is just conceptual.Hybrid  3. This hybrid corresponds to G4 in the proof of Theorem 24.(i)
For eachc=(c1,…,c8)∈S
(1)
table(c) is computed by (table(c),v~(c))←$TableGen(pkil,c), except for a small difference; more precisely, in table(c), the entry located in row 1 and column j≔min{i∣1≤i≤8,ci≠0} is now computed as u^1,j=(u~1,jTa(c1,…,c8))·v~0 rather than u^1,j=u~1,j·v~0; by the IV5 assumption, this difference is computationally undetectable,(2)
extractv^(c) from the (modified) table(c) by invoking v^(c)←CalculateV(skil,table(c),c).(ii)
Computee~≔∏c∈S‍v^(c)·Tfl′((xil,j,yil,j)j∈[4])modNs, and t≔g1fl′((xil,j,yil,j)j∈[4])modN.Through a routine calculation, for eachc=(c1,…,c8)∈S, we have (63)v^c=v~c·T-ac1,…,c8xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8.Hence,(64)e~=∏c∈Sv^c·Tfl′xil,j,yil,jj∈4=∏c∈Sv~c·∏c∈ST-ac1,…,c8xil,1c1yil,1c2xil,2c3yil,2c4xil,3c5yil,3c6xil,4c7yil,4c8·Tfl′xil,j,yil,jj∈4=∏c∈Sv~c·Tδ.Consequently, Hybrid  3 can be implemented in an equivalent way.Hybrid  3 (Equivalent Form). (i) For each c=(c1,…,c8)∈Stable(c) is computed by (table(c),v~(c))←$TableGen(pkil,c), except for a small difference. More precisely, in table(c), the entry located in row 1 and column j≔min{i∣1≤i≤8,ci≠0} is now computed as u^1,j=(u~1,jTa(c1,…,c8))·v~0 rather than u^1,j=u~1,j·v~0.(ii) Computee~≔∏c∈S‍v~(c)·TδmodNs, and t≔g1fl′((xil,j,yil,j)j∈4)modϕ(N)/4modN.Now(x1,y1,…,x4,y4)modN is not used in E.Encrypt any more.After these computationally indistinguishable changes, theE.Encrypt part of theencrypt oracle reserves the entropy of (x1,y1,…,x4,y4)modN.With a similar argument as that in Section5.3, we can change thedecrypt oracle in a computationally indistinguishable way, so that (xj,yj)j=14modN is not employed at all.



---

*Source: 2148534-2017-12-11.xml*