# Selective-Opening Security for Public-Key Encryption in the Presence of Parameter Subversion

Authors: Burong Kang; Zhengan Huang; Lei Zhang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

In public-key encryption (PKE), ciphertexts received by a receiver may be possibly correlated and the security of a PKE relies on honestly generated system parameters. Security against selective opening attacks (SOA) for PKE guarantees that even when an attacker has broken into a subset of honestly generated ciphertexts and opened them (i.e., seeing plaintexts and random bits), the unopened ciphertexts remain secure. While security against parameter subversion attacks (PSA) for PKE requires that even when the public system parameters are maliciously generated, a PKE scheme should be secure. In this paper, we initiate the study of PKE secure against both SOA and PSA. To capture SOA and PSA simultaneously, we formulate a new security notion called indistinguishability under selective opening attacks and parameter subversion attacks (IND-SO-PSA). Further, we define the lossy trapdoor function and all-but-many lossy trapdoor function in the presence of PSA (LTF-PSA and ABM-LTF-PSA correspondingly) and propose an instantiation with the efficiently-embeddable group (EG). Applying these new primitives, we construct a PKE scheme that is proven to be IND-SO-PSA secure.


---

## Body

## 1. Introduction

Public-key encryption (PKE) is a fundamental cryptographic primitive to achieve confidential communication from a sender to a receiver [1]. Traditional security requirement of PKE is indistinguishability under chosen plaintext/ciphertext attack (IND-CPA/CCA) security and only considers the single sender case, i.e., the communication is between a single sender and a single receiver. Whereas, many application scenarios, e.g., secure multiparty computation, secret sharing, cloud computing, are often multisender case [1–6]. These scenarios usually require a set of senders to generate their own messages (possibly correlated) encrypted with the same receiver’s public key and may suffer from some special attacks. One of the mostly studied attacks is selective opening attacks (SOA) [7–18], in which an attacker may corrupt a subset of the senders to open their ciphertexts as well as the corresponding random bits used in the encryption algorithm. Under such an attack, the requirement to guarantee the security of the unopened ciphertexts is beyond the capability of traditional IND-CPA/CCA security [14, 15, 19]. SOA security [7] is a commonly secure property to capture the above attack.Commonly, the security of PKE schemes depends on some honestly generated public system parameters, e.g., security parameter, primes, elliptic curves, and common reference string [20–24]. In fact, public system parameters are often specified in some standards [20, 23], e.g., NIST FIPS 186-4 (2013) [25, 26]. It is timesaving for the implementations of PKE systems to use the public system parameters. However, recent research results show that PKE schemes may suffer from parameter subversion attacks (PSA) which allow adversaries to fully control the public system parameters [20, 23, 27–31] and hence compromise the security of the corresponding PKE schemes. For instance, the elliptic curve cryptosystem specified in NIST FIPS 186-4 standard has been analyzed to be insecure due to the malicious manipulation of the elliptic curves [23]. Thus, PKE schemes resistant to PSA should be developed. That is, a PKE scheme should provide usual security with trusted system parameters, but retain as much security as possible when the parameters are maliciously generated.


### 1.1. Related Work

SOA security was originally discussed by Dwork et al. [17] and first formalized by Bellare et al. [7]. In [7], SOA security was further classified into simulation-based SOA security (SIM-SO security) and the indistinguishability-based SOA security (IND-SO security) [7]. The formal requires that there exists a simulator which can compute the same output as the adversary without ever seeing any ciphertext at all. For IND-SO security, it requires that any adversary who is given a vector of ciphertexts and an opened subset of these ciphertexts cannot distinguish the unopened messages from fresh messages which are re-sampled from a message distribution [7]. According to whether a condition of the message distribution for the fresh messages is needed, there are weak IND-SO security where the message distribution is efficiently conditionally re-samplable and full IND-SO security where the message distribution is an arbitrary one [14]. At present, few full IND-SO secure schemes are proposed. In the following, when we mention IND-SO security, it refers to the weak one. In [7], Bellare et al. showed that SIM-SO security is stronger than the weak IND-SO security. Whereas, it is showed that SIM-SO security is significantly harder to achieve [11, 18]. Thus, in this paper, we focus on the IND-SO security.The existing PKE schemes which satisfy IND-SO security are realized based on lossy trapdoor function (LTF) which is firstly studied in [32] and originally motivated to construct PKE schemes secure against CCA attacks. The primal LTFs in [32] are all-but-one LTFs (ABO-LFT) and only suite for the settings in which there is no more than one challenge ciphertext. PKE schemes secure against SOA usually involve multiple challenge ciphertexts. All-but-N LTF (ABN-LTF) [16] allows N challenge ciphertexts. However, N has to be fixed at the construction time. In SOA security, an adversary may observe many ciphertexts (arbitrary number of challenge ciphertexts) and may open arbitrary number of them. All-but-many LTF (ABM-LTF) introduced by Hofheinz [33] could be viewed as a generalization of both ABO-LFT and ABN-LTF and may meet the above requirement.Beside the SOA, PKE schemes also suffer from PSA. Such an attack is initially studied in [20, 21]. In [20], the security notion called indistinguishable encryptions under parameter subversion attacks (IND-PSA) is introduced to capture PSA, which guarantees that even though the public system parameter of a PKE scheme is chosen maliciously, the resulting ciphertext should be indistinguishable [20]. Based on a security tool referred to as an efficient embedding group (EG), a PKE scheme satisfying IND-PSA is proposed as well. Whereas, their scheme was only considered in the single sender case. In other words, the construction of the PKE scheme secure against the PSA in SOA setting is out of their consideration.


### 1.2. Our Contributions

Although there are already some research results for the SOA and PSA, so far, they are only considered separately. Our aim is to construct a PKE scheme secure against both of these attacks simultaneously.To achieve this goal, we formalize a new security notion called indistinguishability under selective opening attacks and parameter subversion attacks (IND-SO-PSA). IND-SO-PSA security captures indistinguishability under parameter subversion attacks, selective opening attacks, and chosen ciphertext attacks. It guarantees that even though the system parameter of the PKE scheme is chosen maliciously and the adversary is allowed to open a subset of the challenge ciphertexts (i.e., seeing the corresponding plaintexts and randomness used during the encryption), the remainder of the plaintexts should be indistinguishable from freshly re-sampled ones.PKE achieving IND-SO security and PKE satisfying IND-PSA are now independently realized based on ABM-LTFs and EGs, respectively. However, the existing ABM-LTFs are only designed for PKE secure against SOA and not applicable for the construction of a PKE scheme secure against PSA. On the contrary, it seems that it is not a trivial task to extend existing EGs to prevent SOA. Therefore, it would be interesting if we can merge these two tools so that the SOA and PSA can be prevented simultaneously. In order to achieve this intention, we define the lossy trapdoor function and all-but-many lossy trapdoor function in the presence of PSA (LTF-PSA and ABM-LTF-PSA correspondingly) and propose an instantiation with the efficiently-embeddable group (EG). With these new primitives and instantiation, we construct a novel PKE scheme that is proven to satisfy the IND-SO-PSA security.


### 1.3. Paper Organization

The rest of this paper is organized as follows. Some preliminaries are given in Section2. The definitions of LTF-PSA and ABM-LTF-PSA primitives and security model of IND-SO-PSA are stated in Section 3. In Section 4, we propose the instantiation of ABM-LTF-PSA from an efficiently-embeddable group family. LTF-PSA can be similarly instantiated. Based on the newly constructed LTF-PSA and ABM-LTF-PSA, we construct a new PKE scheme and prove its security in Section 5 and Section 6, respectively. Section 7 is the conclusion.


## 1.1. Related Work

SOA security was originally discussed by Dwork et al. [17] and first formalized by Bellare et al. [7]. In [7], SOA security was further classified into simulation-based SOA security (SIM-SO security) and the indistinguishability-based SOA security (IND-SO security) [7]. The formal requires that there exists a simulator which can compute the same output as the adversary without ever seeing any ciphertext at all. For IND-SO security, it requires that any adversary who is given a vector of ciphertexts and an opened subset of these ciphertexts cannot distinguish the unopened messages from fresh messages which are re-sampled from a message distribution [7]. According to whether a condition of the message distribution for the fresh messages is needed, there are weak IND-SO security where the message distribution is efficiently conditionally re-samplable and full IND-SO security where the message distribution is an arbitrary one [14]. At present, few full IND-SO secure schemes are proposed. In the following, when we mention IND-SO security, it refers to the weak one. In [7], Bellare et al. showed that SIM-SO security is stronger than the weak IND-SO security. Whereas, it is showed that SIM-SO security is significantly harder to achieve [11, 18]. Thus, in this paper, we focus on the IND-SO security.The existing PKE schemes which satisfy IND-SO security are realized based on lossy trapdoor function (LTF) which is firstly studied in [32] and originally motivated to construct PKE schemes secure against CCA attacks. The primal LTFs in [32] are all-but-one LTFs (ABO-LFT) and only suite for the settings in which there is no more than one challenge ciphertext. PKE schemes secure against SOA usually involve multiple challenge ciphertexts. All-but-N LTF (ABN-LTF) [16] allows N challenge ciphertexts. However, N has to be fixed at the construction time. In SOA security, an adversary may observe many ciphertexts (arbitrary number of challenge ciphertexts) and may open arbitrary number of them. All-but-many LTF (ABM-LTF) introduced by Hofheinz [33] could be viewed as a generalization of both ABO-LFT and ABN-LTF and may meet the above requirement.Beside the SOA, PKE schemes also suffer from PSA. Such an attack is initially studied in [20, 21]. In [20], the security notion called indistinguishable encryptions under parameter subversion attacks (IND-PSA) is introduced to capture PSA, which guarantees that even though the public system parameter of a PKE scheme is chosen maliciously, the resulting ciphertext should be indistinguishable [20]. Based on a security tool referred to as an efficient embedding group (EG), a PKE scheme satisfying IND-PSA is proposed as well. Whereas, their scheme was only considered in the single sender case. In other words, the construction of the PKE scheme secure against the PSA in SOA setting is out of their consideration.


## 1.2. Our Contributions

Although there are already some research results for the SOA and PSA, so far, they are only considered separately. Our aim is to construct a PKE scheme secure against both of these attacks simultaneously.To achieve this goal, we formalize a new security notion called indistinguishability under selective opening attacks and parameter subversion attacks (IND-SO-PSA). IND-SO-PSA security captures indistinguishability under parameter subversion attacks, selective opening attacks, and chosen ciphertext attacks. It guarantees that even though the system parameter of the PKE scheme is chosen maliciously and the adversary is allowed to open a subset of the challenge ciphertexts (i.e., seeing the corresponding plaintexts and randomness used during the encryption), the remainder of the plaintexts should be indistinguishable from freshly re-sampled ones.PKE achieving IND-SO security and PKE satisfying IND-PSA are now independently realized based on ABM-LTFs and EGs, respectively. However, the existing ABM-LTFs are only designed for PKE secure against SOA and not applicable for the construction of a PKE scheme secure against PSA. On the contrary, it seems that it is not a trivial task to extend existing EGs to prevent SOA. Therefore, it would be interesting if we can merge these two tools so that the SOA and PSA can be prevented simultaneously. In order to achieve this intention, we define the lossy trapdoor function and all-but-many lossy trapdoor function in the presence of PSA (LTF-PSA and ABM-LTF-PSA correspondingly) and propose an instantiation with the efficiently-embeddable group (EG). With these new primitives and instantiation, we construct a novel PKE scheme that is proven to satisfy the IND-SO-PSA security.


## 1.3. Paper Organization

The rest of this paper is organized as follows. Some preliminaries are given in Section2. The definitions of LTF-PSA and ABM-LTF-PSA primitives and security model of IND-SO-PSA are stated in Section 3. In Section 4, we propose the instantiation of ABM-LTF-PSA from an efficiently-embeddable group family. LTF-PSA can be similarly instantiated. Based on the newly constructed LTF-PSA and ABM-LTF-PSA, we construct a new PKE scheme and prove its security in Section 5 and Section 6, respectively. Section 7 is the conclusion.


## 2. Preliminary

### 2.1. Notions and Definitions

Throughout this paper, we usek to denote the security parameter. Let X be a finite set and A be an algorithm. We denote by x⟵$X the random selection of an element x from X and by y⟵$Ax1,…;r the running of algorithm A with inputs x1,…;r and output y. If a probabilistic algorithm’s running time is polynomial in k, we call it probabilistic polynomial-time (PPT). For a string α, we denote by α the bit length of α. For a nonnegative integer n, we denote by n the set 1,…,n. Assume x=x1,…,xn is an n-array vector, we denote by xi its ith component and by x its length. Define Xn×n to be an n×n matrix, RankX to be the rank of X, XT to be the transpose of X, and Xi,j is the element of ith row and jth column, 1≤iandj≤n. For two n×n matrixes A and B, let A|B (i.e., an n×2n matrix) be the concatenation of A and B. Let G be an embedding cyclic group generated by generator g with order q. Given an n×n matrix X for Xi,j∈ℤq, the operation Y=gX is defined by computing Yi,j=gXi,j and setting the matrix Y to be Yi,jn×n. For two random variables X and Y over finite set S, their statistical distance is ΔX,Y=1/2∑s∈SPrX=s−PrY=s.Definition 1 (universal hash function).
Letl1=l1k, l2=l2k and l3=l3k. A family of functions UHFs:0,1l1⟶0,1l2 is called universal hash functions with index key s∈0,1l3, if for all X,X′∈0,1l1, with X≠X′, we have PrUHFsX=UHFsX′≤1/l1 over the random choice of function UHFs.Lemma 1 (adapted from [34]).
LetX and Y are random variables such that X∈0,1l1 and the average min-entropy of X given Y is at last k. Let UHFs:0,1l1⟶0,1l2 be a family of universal hash functions, where l2≤k−2log1/ϵ. Let R⟵$0,1l2, and it holds that ΔUHFs,UHFsX,Y,UHFs,R,Y≤ϵ.Definition 2 (pseudorandom function).
Letl2=l2k. A function family PRFsk:0,1l2⟶0,1l with a key space 0,1∗ is called the pseudorandom function if for any PPT adversary A, A’s advantage AdvAPRFk=PrGAPRFk=1−1/2 of winning the security game GAPRFk defined in Figure 1 is negligible.Figure 1
Game-defining PRF security of a function family.Definition 3 (efficiently re-sampling).
Letn=nk and D be a joint distribution over 0,1kn. We say that D is efficiently re-sampling if there is an algorithm ResampD such that, for any ℐ⊆n and any partial vector m′ii∈ℐ∈0,1kℐ, ResampDm′ii∈ℐ samples from the distribution D, conditioned on m′i=mi for all i∈ℐ.


### 2.2. Efficiently-Embeddable Group Family

An efficiently-embeddable group familyEG=EG.P,EG.G,EG.S,EG.E,EG.I consists of following algorithms [20].Parameter generation algorithmEG.P1k inputs the security parameter k and returns a public system parameter π. Group generation algorithm EG.G1k,π inputs k and π and returns a tuple G=G,q,g, where G is a cyclic group of prime order q and g is a generator of G. Sampling algorithm EG.S1k,π,G is used to sample exponents for the group generator. It returns an exponent y∈ℤq. Embedding algorithm EG.E1k,π,G,gy is used to embed group elements into EG.ESk,π, where EG.ESk,π is a finite set called the embedding space [20]. That is, the output σ⟵$EG.E1k,π,G,gy (i.e., an embedding) is in EG.ESk,π. For such a construction, refer to [20] for the details. Inversion algorithm EG.I1k,π,G,σ is a deterministic algorithm which is used to invert the embedding. It returns ψ⟵EG.I1k,π,G,σ in G. This algorithm should satisfy correctness, i.e., PrEG.I1k,π,G,σ=gy≥1−EG.iek, for all π⟵EG.P1k and G⟵EG.G1k,π, where the probability is over y⟵$EG.S1k,π,G and σ⟵$EG.E1k,π,G,gy. The function EG.iek:ℕ⟶ℝ is defined to be the inversion error of EG.As noted in [20], EG=EG.P,EG.G,EG.S,EG.E,EG.I should satisfy the embedding pseudorandomness under parameter subversion attack (EPR-PSA). We review the definition of it below:Definition 4 (embedding pseudorandomness [20]).
EG holds embedding pseudorandomness under parameter subversion attack, if for any PPT adversary A against EG, A’s advantage(1)AdvEG,AEPR−PSAk=PrGEG,AEPR−PSAk=1−12,of winning the security game GEG,AEPR−PSAk defined in Figure 2 is negligible.Figure 2
Games-defining EPR-PSA security with respect toEG.We note that, inGEG,AEPR−PSAk, A may query the INIT oracle for only once with a parameter π∗ chosen by himself. For a randomly-chosen coin b⟵$0,1 chosen by C, A wins the game, if he can distinguish σ∗ is generated by running algorithms EG.S and EG.E, or sampled uniformly from the embedding space EG.ESk,π∗. In other words, A wins the game, if its guess b′ is equal to b.


### 2.3. Public-Key Encryption

LetM be a message space, ℂ be a ciphertext space, ℙK be a public key space, SK be a secret key space, and ℝ be a randomness space. A public-key encryption (PKE) scheme PKE=PKE.P,PKE.Kg,PKE.Enc,PKE.Dec consists of following algorithms.The parameter generation algorithmPKE.P takes as input 1k and returns a public system parameter π. The key generation algorithm PKE.Kg takes as input 1k,π and returns a pair of public key and a secret key pk,sk∈ℙK×SK. The encryption algorithm PKE.Enc takes as input 1k,π,pk,m;r to encrypt a message m∈M under pk, π and randomness r∈ℝ, and outputs a ciphertext c∈ℂ. The decryption algorithm PKE.Dec is a deterministic algorithm. It takes as input 1k,π,sk,c and outputs a message m or an error symbol ⊥ which means the ciphertext is invalid. We require that, for all m∈M and pk,sk∈PK×SK, it holds that PKE.Dec1k,π,sk,PKE.Enc1k,π,pk,m;r=m.The above definition of PKE is suitable for single user (single message) encryption. In this paper, we consider the public-key encryption scheme in selective opening scenarios, i.e., the encryption in multiuser settings (multiple messages). We have to use the notion of vector-valued encryption [1, 35, 36]. That is, for vectors m=mi, r=ri, and c=ci with i∈n, we denote by c⟵$PKE.Enc1k,π,pk,m;r the tuple PKE.Enc1k,π,pk,m1;r1,PKE.Enc1k,π,pk,m2;r2,…,PKE.Enc1k,π,pk,mn;rn, where n is the number of messages. The decryption algorithm is analogous.To capture parameter subversion attacks, Auerbach et al. [20] formulated a new security notion called indistinguishability under parameter subversion attack (IND-PSA). IND-PSA is a different security notion from traditional IND-CCA security and guarantees that the ciphertexts are indistinguishable even when the system parameter is generated maliciously. We introduce the IND-PSA security below.Definition 5 (IND-PSA security [20]).
PKE holds indistinguishability under parameter subversion attack, if for any PPT adversary A against PKE, A’s advantage(2)AdvPKE,AIND−PSAk=PrGPKE,AIND−PSAk=1−12,of winning the security game GPKE,AIND−PSAk defined in Figure 3 is negligible.Figure 3
Game-defining IND-PSA security ofPKE.In gameGPKE,AIND−PSAk, the challenger C will toss a coin to determine a challenge bit b∈0,1. Then, A may query INIT oracle with a system parameter π∗ chosen by himself to initialize a public-private key pair, and the public key pk is returned to A. The ENC oracle may be queried with two challenge plaintexts m0,m1m0=m1 and return the challenge ciphertext c∗ to A. If b=0, c∗ is an encryption for m0; otherwise, it is the encryption for m1. The DEC oracle is not allowed for the challenge ciphertext c∗. We note that the INIT and ENC oracle can be queried for only once. Given the public key and challenge ciphertext, A outputs a guess bit b′. If b′=b, we say A wins the game, and the game will output 1 in this case.The standard IND-CCA security of the public-key encryption scheme also does not generalize the security under selective opening attacks. To capture the security of the public-key encryption scheme under the selective opening attacks, new security notion called indistinguishability against selective opening attacks and chosen ciphertext attack (IND-SO-CCA) is proposed [16]. IND-SO-CCA security guarantees that any adversary cannot distinguish the messages corresponding to the unopened ciphertexts from a freshly re-sampled one according to a re-samplable distribution D conditioned on the opened messages. We introduce the IND-SO-CCA security below.Definition 6 (IND-SO-CCA security [20]).
PKE holds indistinguishability against selective opening attacks and chosen ciphertext attacks (IND-SO-CCA), if for any PPT adversary A against PKE, A’s advantage(3)AdvPKE,AIND−SO−CCAk=PrGPKE,AIND−SO−CCAk=1−12,of winning the security game GPKE,AIND−SO−CCAk defined in Figure 4 is negligible.Figure 4
Game-defining IND-SO-CCA security ofPKE.At the beginning of the gameGPKE,AIND−SO−CCAk, the challenger C firstly tosses a coin to determine a challenge bit b∈0,1. Then, A firstly queries the INIT oracle. C will run the algorithms PKE.P and PKE.Kg to generate the public system parameter π and public-secret key pair pk,sk correspondingly and returns the public key pk to A. A will output a message distribution D as well as a re-sampling algorithm ReSampD to C after adaptively querying the DEC oracle. Subsequently, C uniformly samples a message vector m0 from D and a randomness vector r=rii∈n from a randomness space ℝn. C returns the challenge ciphertext c=cii∈n to A. After receiving c, A adaptively queries the DEC oracle and chooses an arbitrary subset ℐ⊆n to indicate which ciphertexts he wants to open. ℐ is given to C. Notice that any element of the challenge ciphertext c is not allowed for DEC oracle. After receiving ℐ, C will re-sample a message m1⟵$ResampDmℐ conditioned on the mii∈ℐ of m0. C will send mb,mi,rii∈ℐ to A. Finally, A outputs a guess bit b′, if b′=b, we say A wins the game, and the game will output 1 in this case.


### 2.4. Chameleon Hash Function

A chameleon hash functionCHF=CHF.Kg,CHF.Eval,CHF.Equ with domain CHF.Dom consists of the following algorithms. The key generation algorithm CHF.Kg takes as input 1k and outputs a public key pkchf and a trapdoor tdchf. The evaluation algorithm CHF.Evalpkchf,x;R takes as input a public key pkchf, a preimage x∈CHF.Dom, and a randomness R∈ℛchf where ℛchf is the randomness space of CHF and returns an image y=CHF.Evalpkchf,x;R∈CHF.Ran, where CHF.Ran is the range of CHF. The equivocation algorithm CHF.Equtdchf,x,x′;R takes a trapdoor tdchf, R, x, and x′ as input and outputs a randomness R′∈ℛchf such that CHF.Evalpkchf,x;R=CHF.Evalpkchf,x′;R′. We require that, for any x,x′∈CHF.Dom, if R is uniformly distributed, then so is R′∈ℛchf.A secure chameleon hash functionCHF=CHF.Kg,CHF.Eval,CHF.Equ should satisfy the collision resistance property, which is introduced below.Collision Resistance. Given a public key pkchf, it is difficult for any PPT adversary to find x,R,x′,R′ such that CHF.Evalpkchf,x;R=CHF.Evalpkchf,x′;R′ for x≠x′ without tdchf. Formally, for any PPT adversary A, for random pkchf,tdchf⟵$CHF.Kg1k, the advantage AdvCHF,ACOLLk=Prx≠x′∧CHF.Evalpkchf,x;R=CHF.Evalpkchf,x′;R′|x,R,x′,R′⟵A1k,pkchf is negligible.


### 2.5. Lossy Trapdoor Function

A lossy trapdoor functionLTF=LTF.IKg,LTF.LKg,LTF.Eval,LTF.Inv with domain LTF.Dom consists of the following algorithms [16, 32, 33, 37, 38].(i)
LTF.IKg1k: this is the injective key generation algorithm. On input 1k, it outputs an injective evaluation key ek and a inversion key ik for an injective function.(ii)
LTF.LKg1k: this is the lossy key generation algorithm. On input 1k, it outputs a lossy evaluation key lk for a lossy function. In this case, there is no inversion key.(iii)
LTF.Evalek,x: this is the evaluation algorithm. It takes the evaluation key ek and a preimage x∈LTF.Dom as input and returns an image y=LTF.Evalek,x∈LTF.Ran, where LTF.Dom and LTF.Ran denote the domain and the range of LTF, respectively.(iv)
LTF.Invik,y: this is the inversion algorithm. It takes as input the inversion key ik and an image y∈LTF.Ran and outputs x∈LTF.Dom.Moreover, for any LTF, the following property requirements should be satisfied.Correctness. The above LTF algorithm should satisfy correctness, i.e., LTF.Invik,LTF.Evalek,x=x for all ek,ik⟵$LTF.IKg1k, x∈LTF.Dom.Lossiness. A lossy trapdoor function is l-lossy if for all possible lk⟵$LTF.LKg1k, the image set LTF.Evallk,LTF.Dom is of size at most LTF.Dom/2l.Indistinguishability. Let A be any PPT adversary against LTF. LTF holds indistinguishability if A cannot distinguish the injective evaluation key ek from the lossy evaluation key lk, i.e., A’s advantage(4)AdvLTF,AINDk=PrA1k,ek=1−PrA1k,lk=1,is negligible, where ek,ik⟵$LTF.IKg1k and lk⟵$LTF.LKg1k.


### 2.6. All-but-Many Lossy Trapdoor Function

We now recall the definition of all-but-many lossy trapdoor function (ABM-LTF) which is originally introduced by Hofheinz [33]. In the following definition, we keep the same mechanism of tags as in [33]. In other words, each tag of ABM-LTF consists of two parts: the core part which is also called the primary part, and the auxiliary part which is commonly a random string. In addition, we note that we maintain the same definition of tag space introduced in [34]. That is, the tag space of ABM-LTF is divided into three disjoint subsets: a lossy tag set, an injective tag set, and an invalid tag set. We will give the concrete definition of ABM-LTF in the following.An all-but-many lossy trapdoor functionABM.LTF=ABM.Kg,ABM.Eval,ABM.Inv,ABM.LTg with domain ABM.Dom consists of the following algorithms.(i)
ABM.Kg1k: this is a key generation algorithm. On input 1k, it outputs an injective evaluation key ekabm, an inversion key ikabm, and a tag key tkabm. With the evaluation key ekabm, we define a set T=Tp×Ta which is a tag space. We note that the tag space T consists of three disjoint sets: the lossy tags Tlos, the injective tags Tinj, and the invalid tags Tinv. It is easy to find that each of them is a subset of T, i.e., Tlos⊆T, Tinj⊆T and Tinv⊆T. Each tag is defined in the term of t=tp,ta, where tp∈Tp is the core part and ta∈Ta is the auxiliary part.(ii)
ABM.Evalekabm,t,x: this is the evaluation algorithm. It takes the evaluation key ekabm, the tag t, and a preimage x∈ABM.Dom as input and returns y=ABM.Evalekabm,t,x∈ABM.Ran, where ABM.Dom and ABM.Ran denote the domain and the range of ABM.LTF, respectively.(iii)
ABM.Invikabm,t,y: this is the inversion algorithm. It takes an inversion key ikabm, a tag t, and an image y as input and outputs x∈ABM.Dom.(iv)
ABM.LTgtkabm: this is the lossy tag generation algorithm. It takes the tag key tkabm as input and outputs a lossy tag t=tp,ta.Moreover, for any ABM-LTF, the following property requirements should be satisfied.Correctness. ABM.LTF should satisfy correctness, i.e., ABM.InvABM.Evalekabm,t,x,ikabm,t=x for all ekabm,ikabm,tkabm⟵$ABM.Kg1k, tag t∈Tinj, and x∈ABM.Dom. This property is also referred to as invertibility.Lossiness. ABM.LTF is l-lossy if the size of the image set ABM.Evalekabm,t,ABM.Dom is at most ABM.Dom/2l, for all possible ekabm,ikabm,tkabm⟵$ABM.Kg1k and lossy tag t∈Tlos. l is called the lossiness of ABM.LTF.Indistinguishability. Let A be any PPT adversary against ABM.LTF. ABM.LTF holds the indistinguishability between multiple lossy tags and random tags if A’s advantage(5)AdvABM.LTF,AINDk=PrAABM.LTgtkabm,⋅1k,ekabm=1PrAOT⋅1k,ekabm=1,is negligible, where ekabm,tkabm⟵$ABM.Kg1k. The call to oracle ABM.LTgtkabm,⋅ returns a lossy tag, and OT⋅ is a random oracle which returns a uniform and independent tag from T.Evasiveness. This property requires that it is hard to compute noninjective tags for any adversary, even though it has been given multiple lossy tags. Let A be any PPT adversary against ABM.LTF. ABM.LTF holds the evasiveness if A’s advantage(6)AdvABM.LTF,AEVAk=PrAABM.LTgtkabm,⋅,O⋅1k,ekabm∈Tlos∪Tinv,is negligible, where ekabm,tkabm⟵$ABM.Kg1k, and the oracle O⋅ is queried by A with input t which returns the answers “lossy/invalid” and “injective” which indicate the type of t.


## 2.1. Notions and Definitions

Throughout this paper, we usek to denote the security parameter. Let X be a finite set and A be an algorithm. We denote by x⟵$X the random selection of an element x from X and by y⟵$Ax1,…;r the running of algorithm A with inputs x1,…;r and output y. If a probabilistic algorithm’s running time is polynomial in k, we call it probabilistic polynomial-time (PPT). For a string α, we denote by α the bit length of α. For a nonnegative integer n, we denote by n the set 1,…,n. Assume x=x1,…,xn is an n-array vector, we denote by xi its ith component and by x its length. Define Xn×n to be an n×n matrix, RankX to be the rank of X, XT to be the transpose of X, and Xi,j is the element of ith row and jth column, 1≤iandj≤n. For two n×n matrixes A and B, let A|B (i.e., an n×2n matrix) be the concatenation of A and B. Let G be an embedding cyclic group generated by generator g with order q. Given an n×n matrix X for Xi,j∈ℤq, the operation Y=gX is defined by computing Yi,j=gXi,j and setting the matrix Y to be Yi,jn×n. For two random variables X and Y over finite set S, their statistical distance is ΔX,Y=1/2∑s∈SPrX=s−PrY=s.Definition 1 (universal hash function).
Letl1=l1k, l2=l2k and l3=l3k. A family of functions UHFs:0,1l1⟶0,1l2 is called universal hash functions with index key s∈0,1l3, if for all X,X′∈0,1l1, with X≠X′, we have PrUHFsX=UHFsX′≤1/l1 over the random choice of function UHFs.Lemma 1 (adapted from [34]).
LetX and Y are random variables such that X∈0,1l1 and the average min-entropy of X given Y is at last k. Let UHFs:0,1l1⟶0,1l2 be a family of universal hash functions, where l2≤k−2log1/ϵ. Let R⟵$0,1l2, and it holds that ΔUHFs,UHFsX,Y,UHFs,R,Y≤ϵ.Definition 2 (pseudorandom function).
Letl2=l2k. A function family PRFsk:0,1l2⟶0,1l with a key space 0,1∗ is called the pseudorandom function if for any PPT adversary A, A’s advantage AdvAPRFk=PrGAPRFk=1−1/2 of winning the security game GAPRFk defined in Figure 1 is negligible.Figure 1
Game-defining PRF security of a function family.Definition 3 (efficiently re-sampling).
Letn=nk and D be a joint distribution over 0,1kn. We say that D is efficiently re-sampling if there is an algorithm ResampD such that, for any ℐ⊆n and any partial vector m′ii∈ℐ∈0,1kℐ, ResampDm′ii∈ℐ samples from the distribution D, conditioned on m′i=mi for all i∈ℐ.


## 2.2. Efficiently-Embeddable Group Family

An efficiently-embeddable group familyEG=EG.P,EG.G,EG.S,EG.E,EG.I consists of following algorithms [20].Parameter generation algorithmEG.P1k inputs the security parameter k and returns a public system parameter π. Group generation algorithm EG.G1k,π inputs k and π and returns a tuple G=G,q,g, where G is a cyclic group of prime order q and g is a generator of G. Sampling algorithm EG.S1k,π,G is used to sample exponents for the group generator. It returns an exponent y∈ℤq. Embedding algorithm EG.E1k,π,G,gy is used to embed group elements into EG.ESk,π, where EG.ESk,π is a finite set called the embedding space [20]. That is, the output σ⟵$EG.E1k,π,G,gy (i.e., an embedding) is in EG.ESk,π. For such a construction, refer to [20] for the details. Inversion algorithm EG.I1k,π,G,σ is a deterministic algorithm which is used to invert the embedding. It returns ψ⟵EG.I1k,π,G,σ in G. This algorithm should satisfy correctness, i.e., PrEG.I1k,π,G,σ=gy≥1−EG.iek, for all π⟵EG.P1k and G⟵EG.G1k,π, where the probability is over y⟵$EG.S1k,π,G and σ⟵$EG.E1k,π,G,gy. The function EG.iek:ℕ⟶ℝ is defined to be the inversion error of EG.As noted in [20], EG=EG.P,EG.G,EG.S,EG.E,EG.I should satisfy the embedding pseudorandomness under parameter subversion attack (EPR-PSA). We review the definition of it below:Definition 4 (embedding pseudorandomness [20]).
EG holds embedding pseudorandomness under parameter subversion attack, if for any PPT adversary A against EG, A’s advantage(1)AdvEG,AEPR−PSAk=PrGEG,AEPR−PSAk=1−12,of winning the security game GEG,AEPR−PSAk defined in Figure 2 is negligible.Figure 2
Games-defining EPR-PSA security with respect toEG.We note that, inGEG,AEPR−PSAk, A may query the INIT oracle for only once with a parameter π∗ chosen by himself. For a randomly-chosen coin b⟵$0,1 chosen by C, A wins the game, if he can distinguish σ∗ is generated by running algorithms EG.S and EG.E, or sampled uniformly from the embedding space EG.ESk,π∗. In other words, A wins the game, if its guess b′ is equal to b.


## 2.3. Public-Key Encryption

LetM be a message space, ℂ be a ciphertext space, ℙK be a public key space, SK be a secret key space, and ℝ be a randomness space. A public-key encryption (PKE) scheme PKE=PKE.P,PKE.Kg,PKE.Enc,PKE.Dec consists of following algorithms.The parameter generation algorithmPKE.P takes as input 1k and returns a public system parameter π. The key generation algorithm PKE.Kg takes as input 1k,π and returns a pair of public key and a secret key pk,sk∈ℙK×SK. The encryption algorithm PKE.Enc takes as input 1k,π,pk,m;r to encrypt a message m∈M under pk, π and randomness r∈ℝ, and outputs a ciphertext c∈ℂ. The decryption algorithm PKE.Dec is a deterministic algorithm. It takes as input 1k,π,sk,c and outputs a message m or an error symbol ⊥ which means the ciphertext is invalid. We require that, for all m∈M and pk,sk∈PK×SK, it holds that PKE.Dec1k,π,sk,PKE.Enc1k,π,pk,m;r=m.The above definition of PKE is suitable for single user (single message) encryption. In this paper, we consider the public-key encryption scheme in selective opening scenarios, i.e., the encryption in multiuser settings (multiple messages). We have to use the notion of vector-valued encryption [1, 35, 36]. That is, for vectors m=mi, r=ri, and c=ci with i∈n, we denote by c⟵$PKE.Enc1k,π,pk,m;r the tuple PKE.Enc1k,π,pk,m1;r1,PKE.Enc1k,π,pk,m2;r2,…,PKE.Enc1k,π,pk,mn;rn, where n is the number of messages. The decryption algorithm is analogous.To capture parameter subversion attacks, Auerbach et al. [20] formulated a new security notion called indistinguishability under parameter subversion attack (IND-PSA). IND-PSA is a different security notion from traditional IND-CCA security and guarantees that the ciphertexts are indistinguishable even when the system parameter is generated maliciously. We introduce the IND-PSA security below.Definition 5 (IND-PSA security [20]).
PKE holds indistinguishability under parameter subversion attack, if for any PPT adversary A against PKE, A’s advantage(2)AdvPKE,AIND−PSAk=PrGPKE,AIND−PSAk=1−12,of winning the security game GPKE,AIND−PSAk defined in Figure 3 is negligible.Figure 3
Game-defining IND-PSA security ofPKE.In gameGPKE,AIND−PSAk, the challenger C will toss a coin to determine a challenge bit b∈0,1. Then, A may query INIT oracle with a system parameter π∗ chosen by himself to initialize a public-private key pair, and the public key pk is returned to A. The ENC oracle may be queried with two challenge plaintexts m0,m1m0=m1 and return the challenge ciphertext c∗ to A. If b=0, c∗ is an encryption for m0; otherwise, it is the encryption for m1. The DEC oracle is not allowed for the challenge ciphertext c∗. We note that the INIT and ENC oracle can be queried for only once. Given the public key and challenge ciphertext, A outputs a guess bit b′. If b′=b, we say A wins the game, and the game will output 1 in this case.The standard IND-CCA security of the public-key encryption scheme also does not generalize the security under selective opening attacks. To capture the security of the public-key encryption scheme under the selective opening attacks, new security notion called indistinguishability against selective opening attacks and chosen ciphertext attack (IND-SO-CCA) is proposed [16]. IND-SO-CCA security guarantees that any adversary cannot distinguish the messages corresponding to the unopened ciphertexts from a freshly re-sampled one according to a re-samplable distribution D conditioned on the opened messages. We introduce the IND-SO-CCA security below.Definition 6 (IND-SO-CCA security [20]).
PKE holds indistinguishability against selective opening attacks and chosen ciphertext attacks (IND-SO-CCA), if for any PPT adversary A against PKE, A’s advantage(3)AdvPKE,AIND−SO−CCAk=PrGPKE,AIND−SO−CCAk=1−12,of winning the security game GPKE,AIND−SO−CCAk defined in Figure 4 is negligible.Figure 4
Game-defining IND-SO-CCA security ofPKE.At the beginning of the gameGPKE,AIND−SO−CCAk, the challenger C firstly tosses a coin to determine a challenge bit b∈0,1. Then, A firstly queries the INIT oracle. C will run the algorithms PKE.P and PKE.Kg to generate the public system parameter π and public-secret key pair pk,sk correspondingly and returns the public key pk to A. A will output a message distribution D as well as a re-sampling algorithm ReSampD to C after adaptively querying the DEC oracle. Subsequently, C uniformly samples a message vector m0 from D and a randomness vector r=rii∈n from a randomness space ℝn. C returns the challenge ciphertext c=cii∈n to A. After receiving c, A adaptively queries the DEC oracle and chooses an arbitrary subset ℐ⊆n to indicate which ciphertexts he wants to open. ℐ is given to C. Notice that any element of the challenge ciphertext c is not allowed for DEC oracle. After receiving ℐ, C will re-sample a message m1⟵$ResampDmℐ conditioned on the mii∈ℐ of m0. C will send mb,mi,rii∈ℐ to A. Finally, A outputs a guess bit b′, if b′=b, we say A wins the game, and the game will output 1 in this case.


## 2.4. Chameleon Hash Function

A chameleon hash functionCHF=CHF.Kg,CHF.Eval,CHF.Equ with domain CHF.Dom consists of the following algorithms. The key generation algorithm CHF.Kg takes as input 1k and outputs a public key pkchf and a trapdoor tdchf. The evaluation algorithm CHF.Evalpkchf,x;R takes as input a public key pkchf, a preimage x∈CHF.Dom, and a randomness R∈ℛchf where ℛchf is the randomness space of CHF and returns an image y=CHF.Evalpkchf,x;R∈CHF.Ran, where CHF.Ran is the range of CHF. The equivocation algorithm CHF.Equtdchf,x,x′;R takes a trapdoor tdchf, R, x, and x′ as input and outputs a randomness R′∈ℛchf such that CHF.Evalpkchf,x;R=CHF.Evalpkchf,x′;R′. We require that, for any x,x′∈CHF.Dom, if R is uniformly distributed, then so is R′∈ℛchf.A secure chameleon hash functionCHF=CHF.Kg,CHF.Eval,CHF.Equ should satisfy the collision resistance property, which is introduced below.Collision Resistance. Given a public key pkchf, it is difficult for any PPT adversary to find x,R,x′,R′ such that CHF.Evalpkchf,x;R=CHF.Evalpkchf,x′;R′ for x≠x′ without tdchf. Formally, for any PPT adversary A, for random pkchf,tdchf⟵$CHF.Kg1k, the advantage AdvCHF,ACOLLk=Prx≠x′∧CHF.Evalpkchf,x;R=CHF.Evalpkchf,x′;R′|x,R,x′,R′⟵A1k,pkchf is negligible.


## 2.5. Lossy Trapdoor Function

A lossy trapdoor functionLTF=LTF.IKg,LTF.LKg,LTF.Eval,LTF.Inv with domain LTF.Dom consists of the following algorithms [16, 32, 33, 37, 38].(i)
LTF.IKg1k: this is the injective key generation algorithm. On input 1k, it outputs an injective evaluation key ek and a inversion key ik for an injective function.(ii)
LTF.LKg1k: this is the lossy key generation algorithm. On input 1k, it outputs a lossy evaluation key lk for a lossy function. In this case, there is no inversion key.(iii)
LTF.Evalek,x: this is the evaluation algorithm. It takes the evaluation key ek and a preimage x∈LTF.Dom as input and returns an image y=LTF.Evalek,x∈LTF.Ran, where LTF.Dom and LTF.Ran denote the domain and the range of LTF, respectively.(iv)
LTF.Invik,y: this is the inversion algorithm. It takes as input the inversion key ik and an image y∈LTF.Ran and outputs x∈LTF.Dom.Moreover, for any LTF, the following property requirements should be satisfied.Correctness. The above LTF algorithm should satisfy correctness, i.e., LTF.Invik,LTF.Evalek,x=x for all ek,ik⟵$LTF.IKg1k, x∈LTF.Dom.Lossiness. A lossy trapdoor function is l-lossy if for all possible lk⟵$LTF.LKg1k, the image set LTF.Evallk,LTF.Dom is of size at most LTF.Dom/2l.Indistinguishability. Let A be any PPT adversary against LTF. LTF holds indistinguishability if A cannot distinguish the injective evaluation key ek from the lossy evaluation key lk, i.e., A’s advantage(4)AdvLTF,AINDk=PrA1k,ek=1−PrA1k,lk=1,is negligible, where ek,ik⟵$LTF.IKg1k and lk⟵$LTF.LKg1k.


## 2.6. All-but-Many Lossy Trapdoor Function

We now recall the definition of all-but-many lossy trapdoor function (ABM-LTF) which is originally introduced by Hofheinz [33]. In the following definition, we keep the same mechanism of tags as in [33]. In other words, each tag of ABM-LTF consists of two parts: the core part which is also called the primary part, and the auxiliary part which is commonly a random string. In addition, we note that we maintain the same definition of tag space introduced in [34]. That is, the tag space of ABM-LTF is divided into three disjoint subsets: a lossy tag set, an injective tag set, and an invalid tag set. We will give the concrete definition of ABM-LTF in the following.An all-but-many lossy trapdoor functionABM.LTF=ABM.Kg,ABM.Eval,ABM.Inv,ABM.LTg with domain ABM.Dom consists of the following algorithms.(i)
ABM.Kg1k: this is a key generation algorithm. On input 1k, it outputs an injective evaluation key ekabm, an inversion key ikabm, and a tag key tkabm. With the evaluation key ekabm, we define a set T=Tp×Ta which is a tag space. We note that the tag space T consists of three disjoint sets: the lossy tags Tlos, the injective tags Tinj, and the invalid tags Tinv. It is easy to find that each of them is a subset of T, i.e., Tlos⊆T, Tinj⊆T and Tinv⊆T. Each tag is defined in the term of t=tp,ta, where tp∈Tp is the core part and ta∈Ta is the auxiliary part.(ii)
ABM.Evalekabm,t,x: this is the evaluation algorithm. It takes the evaluation key ekabm, the tag t, and a preimage x∈ABM.Dom as input and returns y=ABM.Evalekabm,t,x∈ABM.Ran, where ABM.Dom and ABM.Ran denote the domain and the range of ABM.LTF, respectively.(iii)
ABM.Invikabm,t,y: this is the inversion algorithm. It takes an inversion key ikabm, a tag t, and an image y as input and outputs x∈ABM.Dom.(iv)
ABM.LTgtkabm: this is the lossy tag generation algorithm. It takes the tag key tkabm as input and outputs a lossy tag t=tp,ta.Moreover, for any ABM-LTF, the following property requirements should be satisfied.Correctness. ABM.LTF should satisfy correctness, i.e., ABM.InvABM.Evalekabm,t,x,ikabm,t=x for all ekabm,ikabm,tkabm⟵$ABM.Kg1k, tag t∈Tinj, and x∈ABM.Dom. This property is also referred to as invertibility.Lossiness. ABM.LTF is l-lossy if the size of the image set ABM.Evalekabm,t,ABM.Dom is at most ABM.Dom/2l, for all possible ekabm,ikabm,tkabm⟵$ABM.Kg1k and lossy tag t∈Tlos. l is called the lossiness of ABM.LTF.Indistinguishability. Let A be any PPT adversary against ABM.LTF. ABM.LTF holds the indistinguishability between multiple lossy tags and random tags if A’s advantage(5)AdvABM.LTF,AINDk=PrAABM.LTgtkabm,⋅1k,ekabm=1PrAOT⋅1k,ekabm=1,is negligible, where ekabm,tkabm⟵$ABM.Kg1k. The call to oracle ABM.LTgtkabm,⋅ returns a lossy tag, and OT⋅ is a random oracle which returns a uniform and independent tag from T.Evasiveness. This property requires that it is hard to compute noninjective tags for any adversary, even though it has been given multiple lossy tags. Let A be any PPT adversary against ABM.LTF. ABM.LTF holds the evasiveness if A’s advantage(6)AdvABM.LTF,AEVAk=PrAABM.LTgtkabm,⋅,O⋅1k,ekabm∈Tlos∪Tinv,is negligible, where ekabm,tkabm⟵$ABM.Kg1k, and the oracle O⋅ is queried by A with input t which returns the answers “lossy/invalid” and “injective” which indicate the type of t.


## 3. Definitions of New Primitives and IND-SO-PSA Security

In this section, for both LTF and ABM-LTF, we extend their definitions to the PSA setting. We introduce the primitive of lossy trapdoor function in the presence of PSA (LTF-PSA) and the primitive of all-but-many lossy trapdoor function in the presence of PSA (ABM-LTF-PSA). Further, we introduce the definition of newly-proposed IND-SO-PSA security.


### 3.1. LTF-PSA Primitive

A lossy trapdoor function in the presence of PSALTF′ with domain LTF.Dom′ consists of the algorithms LTF.P′,LTF.IKg′,LTF.LKg′,LTF.EVAL′,LTF.Inv′ specified as follows.(i)
LTF.P′1k: this is the system parameter generation algorithm. On input 1k, it outputs a system parameter π.(ii)
LTF.IKg′1k,π: this is the injective key generation algorithm. On input 1k and π, it outputs an injective evaluation key ek′ and a inversion key ik′ for an injective function.(iii)
LTF.LKg′1k,π: this is the lossy key generation algorithm. On input 1k and π, it outputs a lossy evaluation key lk′ for a lossy function. In this case, there is no inversion key.(iv)
LTF.Eval′ek′,x: this is the evaluation algorithm. It takes the evaluation key ek′ and a preimage x∈LTF.Dom′ as input and returns an image y=LTF.Eval′ek′,x∈LTF.Ran′, where LTF.Dom′ and LTF.Ran′ denote the domain and range of LTF′, respectively.(v)
LTF.Inv′ik′,y: this is the inversion algorithm. It takes as input the inversion key ik′ and an image y∈LTF.Ran′ and outputs x∈LTF.Dom′.In the following, we will give the formal definitions of security requirements forLTF′. The correctness and lossiness are almost the same as that of LTF. In particular, we introduce the notions of indistinguishability under PSA (IND-PSA2) for LTF′.Correctness. The above LTF′ should satisfy correctness, i.e., LTF.Inv′ik′,LTF.Eval′ek′,x=x for all π⟵$LTF.P′1k, ek′,ik′⟵$LTF.IKg′1k,π, and x∈LTF.Dom′.IndistinguishabilityunderPSA. Let A be any PPT adversary against LTF′. LTF′ holds indistinguishability under PSA if A cannot distinguish of the injective evaluation key ek′ from the lossy evaluation key lk′, i.e., A’s advantage(7)AdvLTF′,AIND−PSA2k=PrA1k,ek′=1−PrA1k,lk′=1,is negligible, where ek′,ik′⟵$LTF.LKg′1k,π∗ and lk′⟵$LTF.IKg′1k,π∗, where π∗ is chosen by A rather than from the LTF.P′ algorithm.Lossiness. A lossy trapdoor function is l-lossy if for all possible π⟵$LTF.P′1k and lk′⟵$LTF.LKg′1k,π, the image set LTF.Eval′lk′,LTF.Dom′ is of size at most LTF.Dom′/2l.


### 3.2. ABM-LTF-PSA Primitive

An all-but-many lossy trapdoor function in the presence of PSAABM.LTF′=ABM.P′,ABM.Kg′,ABM.Eval′,ABM.Inv′,ABM.LTg′ with domain ABM.Dom′ consists of the following algorithms:(i)
ABM.P′1k: this is the system parameter generation algorithm. On input 1k, it outputs a system parameter π.(ii)
ABM.Kg′1k,π: on input 1k and π, it outputs an injective evaluation key ekabm′, an inversion key ikabm′, and a tag key tkabm′. We note that it has the tag space T′=Tinj′×Tlos′×Tinv′. Similar to that of ABM.LTF, the term of each tag for ABM.LTF′ is also as t′=tp′,ta′, where tp′∈Tp′ is the core part and ta′∈Ta′ is the auxiliary part.(iii)
ABM.Eval′ekabm′,t′,x′: it takes the evaluation key ekabm′, the tag t′, and a preimage x′∈ABM.Dom′ as input and returns y′∈ABM.Ran′, where ABM.Dom′ and ABM.Ran′ be the domain and range of the ABM.LTF′.(iv)
ABM.Inv′ikabm′,t′,y′: it takes an inversion key ikabm′, a tag t′, and an image y′ as input and outputs x′∈ABM.Dom′.(v)
ABM.LTg′tkabm′: it takes the tag key tkabm′ as input and outputs a lossy tag t′=tp′,ta′.We give the formal definitions of security requirements for the all-but-many lossy trapdoor function in the presence of PSA in the following. The correctness and lossiness are almost the same as that ofABM.LTF. In particular, we introduce the notions of indistinguishability under PSA (IND-PSA3) and evasiveness under PSA (EVA-PSA) for ABM.LTF′.Correctness. ABM.LTF′ should satisfy the correctness. That is, the equation should hold, ABM.Inv′ABM.Eval′ekabm′,t′,x′,ikabm′,t′=x′, for all π⟵$ABM.P′1k, ekabm′,ikabm′,tkabm′⟵$ABM.Kg′1k,π, tag t′∈Tinj′, and x′∈ABM.Dom′. This property is also referred to as invertibility.Lossiness. ABM.LTF′ is l-lossy if the size of the image set ABM.Eval′ekabm′,t′,ABM.Dom′ is at most ABM.Dom′/2l, for all π⟵$ABM.P′1k, ekabm′,ikabm′,tkabm′⟵$ABM.Kg′1k,π, and lossy tag t′∈Tlos′. l is called the lossiness of ABM.LTF′.IndistinguishabilityunderPSA. Let A be any PPT adversary against ABM.LTF′. We say ABM.LTF′ holds the indistinguishability under PSA between multiple lossy tags and random tags if A’s the advantage(8)AdvABM.LTF′,AIND−PSA3k=PrAABM.LTg′tkabm′,⋅1k,ekabm′=1PrAOT′⋅1k,ekabm′=1,is negligible, where ekabm′,tkabm′⟵$ABM.Kg′1k,π∗, π∗ is chosen by A rather than from the ABM.P′ algorithm. The call to oracle ABM.LTg′tkabm′,⋅ returns a lossy tag, and OT′⋅ is a random oracle returns a uniform and independent tag from T′.EvasivenessunderPSA. This property requires that it is hard to compute noninjective tags for any adversary, even though it has been given multiple lossy tags. Let A be any PPT adversary against ABM.LTF′. ABM.LTF′ holds the evasiveness under PSA if A’s advantage(9)AdvABM.LTF′,AEVA−PSAk=PrAABM.LTg′tkabm′,⋅,O⋅1k,ekabm′∈Tlos′∪Tinv′,is negligible, where ekabm′,tkabm′⟵$ABM.Kg′1k,π∗, π∗ is chosen by A itself. The oracle O⋅ is queried by A with input t′ which returns the answers “lossy/invalid” and “injective” which indicate the type of t′.


### 3.3. IND-SO-PSA Security

To capture the security of the public-key encryption scheme under SOA and PSA, we formulate a new security notion called indistinguishability under selective opening attacks and parameter subversion attacks (IND-SO-PSA). IND-SO-PSA security captures indistinguishability under parameter subversion attacks, selective opening attacks, and chosen ciphertext attacks. In other words, it guarantees that even though the system parameter of the PKE scheme is chosen maliciously and the adversary is allowed to open a subset of the challenge ciphertexts (i.e., seeing the corresponding plaintexts and randomness used during the encryption), the remainder of the plaintexts should be indistinguishable from freshly re-sampled ones. In the following, we give the formal definition of IND-SO-PSA security.Definition 7 (IND-SO-PSA security).
LetA be an adversary attacking PKE. We say that PKE holds the indistinguishability under selective opening attacks, parameter subversion attacks, and chosen ciphertext attacks (IND-SO-PSA security), if A’s advantage(10)AdvPKE,AIND−SO−PSAk,=PrGPKE,AIND−SO−PSAk=1−12,of winning the security game GPKE,AIND−SO−PSAk defined in Figure 5 is negligible.Figure 5
Game-defining IND-SO-PSA security ofPKE.At the beginning of the gameGPKE,AIND−SO−PSAk, the challenger C firstly tosses a coin to determine a challenge bit b∈0,1. Then, A firstly queries the INIT oracle with the public system parameter π∗ chosen by himself. C runs the algorithm PKE.Kg to generate public-secret key pair pk,sk. pk is given to the adversary A. A will output a message distribution D as well as a re-sampling algorithm ReSampD after adaptively querying the DEC oracle. Subsequently, C samples uniformly a message vector m0 from D and a randomness vector r=rii∈n from a randomness space ℝn. C returns the challenge ciphertext c=cii∈n to A. After receiving c, A adaptively queries the DEC oracle and chooses an arbitrary subset ℐ⊆n to indicate which ciphertexts he wants to open. ℐ is given to C. Notice that any element of the challenge ciphertext c is not allowed for DEC oracle. After receiving ℐ, C will re-sample a message m1⟵$ResampDmℐ conditioned on the mii∈ℐ of m0. C will send mb,mi,rii∈ℐ to A. Finally, A outputs a guess bit b′, and if b′=b, we say A wins the game, and the game will output 1 in this case.


## 3.1. LTF-PSA Primitive

A lossy trapdoor function in the presence of PSALTF′ with domain LTF.Dom′ consists of the algorithms LTF.P′,LTF.IKg′,LTF.LKg′,LTF.EVAL′,LTF.Inv′ specified as follows.(i)
LTF.P′1k: this is the system parameter generation algorithm. On input 1k, it outputs a system parameter π.(ii)
LTF.IKg′1k,π: this is the injective key generation algorithm. On input 1k and π, it outputs an injective evaluation key ek′ and a inversion key ik′ for an injective function.(iii)
LTF.LKg′1k,π: this is the lossy key generation algorithm. On input 1k and π, it outputs a lossy evaluation key lk′ for a lossy function. In this case, there is no inversion key.(iv)
LTF.Eval′ek′,x: this is the evaluation algorithm. It takes the evaluation key ek′ and a preimage x∈LTF.Dom′ as input and returns an image y=LTF.Eval′ek′,x∈LTF.Ran′, where LTF.Dom′ and LTF.Ran′ denote the domain and range of LTF′, respectively.(v)
LTF.Inv′ik′,y: this is the inversion algorithm. It takes as input the inversion key ik′ and an image y∈LTF.Ran′ and outputs x∈LTF.Dom′.In the following, we will give the formal definitions of security requirements forLTF′. The correctness and lossiness are almost the same as that of LTF. In particular, we introduce the notions of indistinguishability under PSA (IND-PSA2) for LTF′.Correctness. The above LTF′ should satisfy correctness, i.e., LTF.Inv′ik′,LTF.Eval′ek′,x=x for all π⟵$LTF.P′1k, ek′,ik′⟵$LTF.IKg′1k,π, and x∈LTF.Dom′.IndistinguishabilityunderPSA. Let A be any PPT adversary against LTF′. LTF′ holds indistinguishability under PSA if A cannot distinguish of the injective evaluation key ek′ from the lossy evaluation key lk′, i.e., A’s advantage(7)AdvLTF′,AIND−PSA2k=PrA1k,ek′=1−PrA1k,lk′=1,is negligible, where ek′,ik′⟵$LTF.LKg′1k,π∗ and lk′⟵$LTF.IKg′1k,π∗, where π∗ is chosen by A rather than from the LTF.P′ algorithm.Lossiness. A lossy trapdoor function is l-lossy if for all possible π⟵$LTF.P′1k and lk′⟵$LTF.LKg′1k,π, the image set LTF.Eval′lk′,LTF.Dom′ is of size at most LTF.Dom′/2l.


## 3.2. ABM-LTF-PSA Primitive

An all-but-many lossy trapdoor function in the presence of PSAABM.LTF′=ABM.P′,ABM.Kg′,ABM.Eval′,ABM.Inv′,ABM.LTg′ with domain ABM.Dom′ consists of the following algorithms:(i)
ABM.P′1k: this is the system parameter generation algorithm. On input 1k, it outputs a system parameter π.(ii)
ABM.Kg′1k,π: on input 1k and π, it outputs an injective evaluation key ekabm′, an inversion key ikabm′, and a tag key tkabm′. We note that it has the tag space T′=Tinj′×Tlos′×Tinv′. Similar to that of ABM.LTF, the term of each tag for ABM.LTF′ is also as t′=tp′,ta′, where tp′∈Tp′ is the core part and ta′∈Ta′ is the auxiliary part.(iii)
ABM.Eval′ekabm′,t′,x′: it takes the evaluation key ekabm′, the tag t′, and a preimage x′∈ABM.Dom′ as input and returns y′∈ABM.Ran′, where ABM.Dom′ and ABM.Ran′ be the domain and range of the ABM.LTF′.(iv)
ABM.Inv′ikabm′,t′,y′: it takes an inversion key ikabm′, a tag t′, and an image y′ as input and outputs x′∈ABM.Dom′.(v)
ABM.LTg′tkabm′: it takes the tag key tkabm′ as input and outputs a lossy tag t′=tp′,ta′.We give the formal definitions of security requirements for the all-but-many lossy trapdoor function in the presence of PSA in the following. The correctness and lossiness are almost the same as that ofABM.LTF. In particular, we introduce the notions of indistinguishability under PSA (IND-PSA3) and evasiveness under PSA (EVA-PSA) for ABM.LTF′.Correctness. ABM.LTF′ should satisfy the correctness. That is, the equation should hold, ABM.Inv′ABM.Eval′ekabm′,t′,x′,ikabm′,t′=x′, for all π⟵$ABM.P′1k, ekabm′,ikabm′,tkabm′⟵$ABM.Kg′1k,π, tag t′∈Tinj′, and x′∈ABM.Dom′. This property is also referred to as invertibility.Lossiness. ABM.LTF′ is l-lossy if the size of the image set ABM.Eval′ekabm′,t′,ABM.Dom′ is at most ABM.Dom′/2l, for all π⟵$ABM.P′1k, ekabm′,ikabm′,tkabm′⟵$ABM.Kg′1k,π, and lossy tag t′∈Tlos′. l is called the lossiness of ABM.LTF′.IndistinguishabilityunderPSA. Let A be any PPT adversary against ABM.LTF′. We say ABM.LTF′ holds the indistinguishability under PSA between multiple lossy tags and random tags if A’s the advantage(8)AdvABM.LTF′,AIND−PSA3k=PrAABM.LTg′tkabm′,⋅1k,ekabm′=1PrAOT′⋅1k,ekabm′=1,is negligible, where ekabm′,tkabm′⟵$ABM.Kg′1k,π∗, π∗ is chosen by A rather than from the ABM.P′ algorithm. The call to oracle ABM.LTg′tkabm′,⋅ returns a lossy tag, and OT′⋅ is a random oracle returns a uniform and independent tag from T′.EvasivenessunderPSA. This property requires that it is hard to compute noninjective tags for any adversary, even though it has been given multiple lossy tags. Let A be any PPT adversary against ABM.LTF′. ABM.LTF′ holds the evasiveness under PSA if A’s advantage(9)AdvABM.LTF′,AEVA−PSAk=PrAABM.LTg′tkabm′,⋅,O⋅1k,ekabm′∈Tlos′∪Tinv′,is negligible, where ekabm′,tkabm′⟵$ABM.Kg′1k,π∗, π∗ is chosen by A itself. The oracle O⋅ is queried by A with input t′ which returns the answers “lossy/invalid” and “injective” which indicate the type of t′.


## 3.3. IND-SO-PSA Security

To capture the security of the public-key encryption scheme under SOA and PSA, we formulate a new security notion called indistinguishability under selective opening attacks and parameter subversion attacks (IND-SO-PSA). IND-SO-PSA security captures indistinguishability under parameter subversion attacks, selective opening attacks, and chosen ciphertext attacks. In other words, it guarantees that even though the system parameter of the PKE scheme is chosen maliciously and the adversary is allowed to open a subset of the challenge ciphertexts (i.e., seeing the corresponding plaintexts and randomness used during the encryption), the remainder of the plaintexts should be indistinguishable from freshly re-sampled ones. In the following, we give the formal definition of IND-SO-PSA security.Definition 7 (IND-SO-PSA security).
LetA be an adversary attacking PKE. We say that PKE holds the indistinguishability under selective opening attacks, parameter subversion attacks, and chosen ciphertext attacks (IND-SO-PSA security), if A’s advantage(10)AdvPKE,AIND−SO−PSAk,=PrGPKE,AIND−SO−PSAk=1−12,of winning the security game GPKE,AIND−SO−PSAk defined in Figure 5 is negligible.Figure 5
Game-defining IND-SO-PSA security ofPKE.At the beginning of the gameGPKE,AIND−SO−PSAk, the challenger C firstly tosses a coin to determine a challenge bit b∈0,1. Then, A firstly queries the INIT oracle with the public system parameter π∗ chosen by himself. C runs the algorithm PKE.Kg to generate public-secret key pair pk,sk. pk is given to the adversary A. A will output a message distribution D as well as a re-sampling algorithm ReSampD after adaptively querying the DEC oracle. Subsequently, C samples uniformly a message vector m0 from D and a randomness vector r=rii∈n from a randomness space ℝn. C returns the challenge ciphertext c=cii∈n to A. After receiving c, A adaptively queries the DEC oracle and chooses an arbitrary subset ℐ⊆n to indicate which ciphertexts he wants to open. ℐ is given to C. Notice that any element of the challenge ciphertext c is not allowed for DEC oracle. After receiving ℐ, C will re-sample a message m1⟵$ResampDmℐ conditioned on the mii∈ℐ of m0. C will send mb,mi,rii∈ℐ to A. Finally, A outputs a guess bit b′, and if b′=b, we say A wins the game, and the game will output 1 in this case.


## 4. Construction of ABM-LTF-PSA

In this section, based on the embeddable group that was introduced by Auerbach et al. in [20], we construct an ABM-LTF-PSA and prove that it satisfies the IND-PSA3 as well as the EVA-PSA without the random oracle. The formal guarantees that a lossy tag is computationally indistinguishable from a random one, even when the adversary is given access to the lossy tag generation oracle and could choose the system parameter by himself. The latter prevents the adversary who could choose the system parameter by himself from generating lossy tags. We note that ABM-LTF-PSA can be seen as a generic LTF-PSA, which means that it could be used as LTF-PSA. On the contrary, LTF-PSA could be constructed with the same way as the construction of ABM-LTF-PSA. Thus, we will not reconsider the instantiation of LTF-PSA here.


### 4.1. ABM-LTF-PSA from Embeddable Group Family

LetCHF=CHF.Kg,CHF.Eval,CHF.Equ be a chameleon hash function, ℋ1:G⟶0,1∗ be a hash function, and EG=EG.P,EG.G,EG.S,EG.E,EG.I be an embeddable group family (we have recalled in the Section 2.2) [20]. We assume that the multiplication and addition operations hold on EG.ES. In addition, we note that the algorithm EG.E of EG is deterministic as the instantiations of EG in [20]. An ABM-LTF-PSA based on the embeddable group family is a tuple of algorithms ABM.LTF′=ABM.P′,ABM.Kg′,ABM.Eval′,ABM.Inv′,ABM.LTg′ that specified as following.(i)
ABM.P′1k: taking as input the security parameter k, it runs the EG.P1k algorithm of EG to generate a system parameter π.(ii)
ABM.Kg′1k,π: the key generation algorithm does the following steps:(1)
Generate a public keypkchf and the corresponding trapdoor tdchf of the CHF using CHF.Kg. This CHF will be used in the following to compute tags of ABM.LTF’.(2)
Generate an embedding cyclic groupG=G,q,g by running EG.G1k,π.(3)
Letn=nk. Sample αij∈ℤqn×n, βij∈ℤqn×n, and δij∈ℤqn×n by running EG.S1k,π,G for 1≤iandj≤n, and set three matrixes S1=αijn×n, S2=βijn×n, and S3=δijn×n.(4)
Set matrixesA=gαijn×n, B=gβijn×n, and C=gδijn×n for g generated in Step 2.(5)
Computeσij by running EG.E1k,π,G,Aij, θij by running EG.E1k,π,G,Bij, and τij by running EG.E1k,π,G,Cij for 1≤iandj≤n. We have σij,θij,andτij∈EG.ESk,π. Set matrixes E1=σijn×n, E2=θijn×n, and E3=τijn×n.(6)
Select a pseudorandom functionPRF:0,1∗×0,1l2⟶0,1l. Run EG.S1k,π,G to get vector e=e1,e2,…,en∈ℤq1×n. Set vector k=κ1,κ2,…,κn∈0,1∗ as the key of the PRF, where κi=ℋ1gei. Run τij to compute κ′i∈EG.ESk,π and get vector k′=κ′1,κ′2,…,κ′n as the hiding vector of k. We note that k should be kept secret and k′ could be public.(7)
Select an universal hash functionUHFs:0,1l1×0,1l3⟶0,1l2 with key s∈0,1l3. Sample a matrix Hn×n from the embedding space EG.ESk,π, and we use hi to denote the ith row of H.(8)
Set the public evaluation keyekabm′=C,E1,E2,pkchf,k′,s,H,G, private inversion key ikabm′=C,S1,S2,k,s,H,G, and lossy tag generation key tkabm′=E3,k,s,H,tdchf,G.(iii)
Tags: a tag in ABM.LTF′ is defined in the form of t′=tp′,ta′, where ta′∈0,1∗ is an auxiliary part, tp′=D,Rchf∈EG.ESk,πn×n×ℛchf is a primary part, and Rchf∈ℛchf is a randomness for CHF. Set the tag space as T′=EG.ESk,πn×n×ℛchf×0,1∗. With a tag t′=D,Rchf,ta, we compute φ=CHF.Evalpkchf,D,ta′;Rchf∈0,1l1. Let matrix U=DE3−F where F=f1,f2,…,fnT and fi=PRFκi,UHFsφ⋅hi is the ith row of F for 1≤i≤n. We define(11)t′∈Tinj′,RankU=n;Tlos′,U=0;Tinv′,RankU≠nandRankU≠0.We say thatt′ is an injective tag if the rank of matrix U is n, i.e., RankU=n; else, if U=0, we say that t′ is a lossy tag; particularly, if the rank of matrix U is out of the above two cases, i.e., RankU≠n and RankU≠0, we say that t′ is an invalid tag.(iv)
ABM.Eval′ekabm′,t′,x: with a tag t′=D,Rchf,ta′ and the public evaluation key ekabm′=C,E1,E2,pkchf,k′,s,H,G, for a vector of preimage input x=x1,x2,…,xn∈ℤq1×n, the algorithm does the following:(1)
For tagt′, compute φ=CHF.Evalpkchf,D,ta′;Rchf∈0,1l1. With k′, recover the key vector k=κ1,κ2,…,κn of PRF as κi=ℋ1gei, where gei is computed by running EG.I1k,π,G,κ′i.(2)
For matrixesE1=σijn×n and E2=θijn×n, compute gαij and gβij by running EG.I1k,π,G,E1ij and EG.I1k,π,G,E2ij correspondingly. Obtain the matrixes A=gαijn×n and B=gβijn×n, where 1≤iandj≤n. Randomly select μ and υ from ℤq by running EG.S1k,π,G, and compute s1=gμ, s2=gυ, and E=Aμ+Bυ, i.e., Eij=Aijμ+Bijυ=gαijμ+gβijυ. Compute ϖ1 by running EG.E1k,π,G,s1 and ϖ2 by running EG.E1k,π,G,s2, where ϖ1andϖ2∈EG.ESk,π.(3)
Computeτij by running EG.E1k,π,G,Cij to obtain matrix E3=τijn×n for 1≤iandj≤n. Concatenating matrixes E and U to obtain the matrix Mn×2n. That is, M=E|U∈EG.ESk,πn×2n, where U=DE3−F, F=f1,f2,…,fnT, and fi=PRFκi,UHFsφ⋅hi for 1≤i≤n.(4)
Computex¯i by running EG.E1k,π,G,gxi to set a vector x¯=x¯1,x¯2,…,x¯n, where x¯i∈EG.ESk,π,1≤i≤n.(5)
Compute the following equation to get the image vectory∈EG.ESk,π1×2n:(12)y=∑i=1nPRFκi,UHFsφ⋅x¯⋅M.(6)
Outputy,ϖ1,ϖ2.(v)
ABM.Inv′ikabm′,t′,y,ϖ1,ϖ2: given an inversion key ikabm′=C,S1,S2,k,s,H,G, a tag t′=D,Rchf,ta′, ϖ1andϖ2, and image vector y, the algorithm ABM.Inv′ computes x as follows:(1)
Computes1ands2 by running EG.I1k,π,G,ϖ1 and EG.I1k,π,G,ϖ2. Compute E1′=s1S1 and E2′=s2S2, which means that E1′ij=gμαij and E2′ij=gυβij. Obtain the matrix E by computing E=E1′+E2′, that is, Eij=gμαij+gυβij. Compute M=E|U∈EG.ESk,πn×2n as the algorithm ABM.Eval′.(2)
For tagt′=D,Rchf,ta′, it first computes φ=CHF.Evalpkchf,D,ta′;Rchf∈0,1l1.(3)
Withikabm′, it computes the following equation to get x¯:(13)x¯=y⋅M−1∑i=1nPRFκi,UHFsφ,whereM−12n×n is the inverse matrix of M.(4)
Finally, it computes and outputs the vector of preimagex by running EG.I1k,π,x¯.(vi)
ABM.LTg′tkabm′: the lossy tag generation algorithm is given the lossy tag generation key tkabm′. It does the following steps to compute a lossy tag t′=tp′,ta′:(1)
Randomly choose a tagt′˜=D˜,R˜chf,t˜a′∈T′, and then, compute the value φ=CHF.Evalpkchf,D˜,t˜a′,R˜chf.(2)
Solve for an appropriaten×n matrix D∈EG.ESk,πn×n such that the equation DE3=F is valid, where F=f1,f2,…,fnT, fi=PRFκi,UHFsφ⋅hi, for 1≤i≤n.(3)
Compute the valueRchf from the equation Rchf=CHF.Equtdchf,D˜,t˜a′,D,ta′;R˜chf, and output a tag t′=D,Rchf,ta′. It is easy to check that the tag t′ output by this algorithm is indeed a lossy one.Correctness. We note that the correctness of the above ABM-LTF-PSA instantiation holds due to the following equation:(14)E=Aμ+Bυ=s1S1+s2S2=E1′+E2′=E.Lossiness. For any lossy tag t′∈Tlos′ in the above ABM-LTF-PSA instantiation, we note that its lossiness l=log2qn/n2EG.ESk,π. When t′∈Tlos′, the matrix U is equal to 0, i.e., U=0, we have at most n2 possible values of M=E|U∈EG.ESk,πn×2n. Thus, the image set ABM.Eval′ekabm′,t′,ABM.Dom′ has size n2EG.ESk,π. Meanwhile, the size of domain ABM.Dom′ of the ABM.Eval′ is qn because the preimage of ABM.LTF′ is x∈ℤq1×n. According to the definition of lossiness for ABM.LTF′, we could obtain the lossiness of the above construction is l=log2qn/n2EG.ESk,π.


### 4.2. Proofs of Security

Lemma 2.
Letn is polynomial in k and q is exponential in the security parameter k. A matrix X randomly sampled from ℤqn×n will have RankX=n with all but negligible probability in k.Proof.
The probability ofRankX=n is equal to the probability that n columns of X are linearly independent. This means that there are qn−1 possibilities (i.e., the zero vector is removed) for the sample of the first column vector. For the sample of the second column vector, there are qn−q possibilities (i.e., the q vectors linearly dependent on the first vector should be removed). The rest may be deduced by analogy. Thus, the probability of RankX=n is(15)qn−1⋅qn−q⋅qn−q2⋯qn−qn−1qn⋅qn⋯qn=∏i=1n1−1qi=1−1qfunck,where funck is a function satisfying that 0<funck≤n1+1/q+⋯+1/qn. Because q is exponential in k, 1/qfunck is negligible in k. So, we could finally obtain that this probability is overwhelming.Theorem 1 (indistinguishability).
LetEG be an efficiently-embeddable group and CHF be a chameleon hash function. Let ABM.LTF′ be the all-but-many lossy trapdoor function that we built above. For any PPT adversary A with advantage AdvABM.LTF′,AIND−PSA3, there exists adversaries A1 and A2 such that(16)AdvABM.LTF′,AIND−PSA3k⩽2n2+nAdvEG,A1EPR−PSAk+nAdvA2PRFk.Proof.
We proceed with the proof by describing a sequence of games, i.e.,Game 1 to Game 3. Let Si be the event that the output of adversary A is 1 in Gamei. In Game 1, all algorithms work exactly the same as the real scheme. A interacts with ABM.LTg′tkabm′,⋅, and the algorithm outputs lossy tags for adversary A. We emphasis that the system parameter π∗ involved in this game is chosen by A. So, we obtain(17)PrS1=PrAABM.LTg′tkabm′,⋅1k,ekabm′=1.
InGame 2, we modify the way of generating the public evaluation key ekabm′=C,E1,E2,pkchf,k′,s,H,G. Specially, we choose the matrixes E1 and E2 and the vector k′ uniformly at random from EG.ESk,π∗. Since E1, E2, and k′ do not influence the output distribution of ABM.LTg′, by the EPR-PSA assumption of EG, this modification will not be noticed by A. So, for an EPR-PSA adversary A1, we obtain(18)PrS2−PrS1≤2n2+nAdvEG,A1EPR−PSAk.
InGame 3, the proceeding of algorithm ABM.LTg′ is changed. Particularly, in the 2nd step of algorithm ABM.LTg′, we randomly select a matrix F⟵$EG.ESk,π∗n×n instead of computing a matrix F=f1,f2,…,fnT, in which fi=PRFκi,UHFsφ⋅hi with uniformly random φ for 1≤i≤n, as in Game 2. According to the PRF security (defined in Figure 1) of the pseudorandom function, for a PPT adversary A2 against PRF, we could obtain(19)PrS3−PrS2≤nAdvA2PRFk.
On the contrary, inGame 3, the matrix D of tp′ is the solution of equation DE3=Fmodq with random F. If the rank of matrix E3 is n, then D will be random. According to Lemma 2 (same result holds for EG.ESk,πn×n), we indeed have RankE3=n. This means that D is random. Thus, we could obtain result that the primary part tp′=D,Rchf of tag t′ is random. Therefore, all tags generated in Game 3 are random tags. So, we obtain(20)PrS3=PrAOT′⋅1k,ekabm′=1.
Summing up, we find that the advantageAdvABM.LTF′,AIND−PSA3k of adversary A is(21)PrAABM.LTg′tkabm′,⋅1k,ekabm′=1−PrAOT′⋅1k,ekabm′=1≤2n2+nAdvEG,A1EPR−PSAk+nAdvA2PRFk.Theorem 2 (evasiveness).
LetEG be the efficiently-embeddable group and CHF be a chameleon hash function. Let ABM.LTF′ be the all-but-many lossy trapdoor function that we built above. For any PPT adversary A with advantage AdvABM.LTF′,AEVA−PSA, there exist adversaries A1, A2, and A3 such that(22)AdvABM.LTF′,AEVA−PSAk⩽2n2+nAdvEG,A1EPR−PSAk+nAdvA2PRFk+AdvCHF,A3COLLk+negk.Proof.
We proceed with the proof by describing a sequence of games,Game 1 to Game 4. Let Si be the event that the output of adversary A is a lossy or invalid tag in Gamei. We consider the following two types of tags output by A. Specifically, for a tag t′=D∗,Rchf∗,ta′∗,(i)
Type 1: if φ∗=CHF.Evalpkchf,D∗,ta′∗;Rchf∗ is also the chameleon hash output of some previously generated tag, then we refer to t′=D∗,Rchf∗,ta′∗ as a Type 1 tag.(ii)
Type 2: if φ∗=CHF.Evalpkchf,D∗,ta′∗;Rchf∗ is not the chameleon hash output of any previously generated tag, then we refer to t′=D∗,Rchf∗,ta′∗ as a Type 2 tag.
We make an assumption, without loss of generality, thatA obtains n=nk lossy tags by querying the ABM.LTg′tkabm′ oracle. Let ti′i∈n=Di,Rchfi,tai′i∈n denote these lossy tags. Then, A adaptively comes up with n′=n′k tags ti′∗i∈n′=Di∗,Rchfi∗,tai′∗i∈n′ by querying the oracle OT′ and gets answers “invalid” or “injective.”
InGame 1, all algorithms work exactly the same as the real scheme. In particular, we note that the system parameter π∗ involved in this game is chosen by A. So, we have(23)AdvABM.LTF′,AEVA−PSAk=PrS1.
InGame 2, we modify the way of generating the public evaluation key ekabm′=C,E1,E2,pkchf,k′,s,H,G. Specially, we choose the matrixes E1 and E2 and the vector k′ uniformly at random from EG.ESk,π∗. Since E1, E2, and k′ do not influence the output distribution of ABM.LTg′, by the EPR-PSA assumption of EG, this modification will not be noticed by A. So, for an EPR-PSA adversary A1, we obtain(24)PrS2−PrS1≤2n2+nAdvEG,A1EPR−PSAk.
InGame 3, we change the algorithm ABM.LTg′. In particular, in the 2nd step of ABM.LTg′, we randomly select a matrix F⟵$EG.ESk,π∗n×n for any φ, instead of computing a matrix F=f1,f2,…,fnT, in which fi=PRFκi,UHFsφ⋅hi. For all queries ti′∗i∈n′ to the OT′ oracle, we return the answer “injective.” In the following context, we will use the mathematical methods of induction to prove that the distinguishability of Game 2 and Game 3 implies that there is an adversary A2 against the pseudorandom function PRF.(i)
For the base step, supposen′=1 (the case n′=0 is vacuous). In Game 2, OT′ honestly computes U=DE3−F, where F=f1,f2,…,fnT and fi=PRFκi,UHFsφ1∗⋅hi, for 1≤i≤n. Then, it returns the answer “injective.” The distributions of U in Game 2 and Game 3 are correspondingly PRFκj,UHFsφi∗j∈n∪PRFκj,UHFsφ1∗ and Fi⟵$EG.ESk,π∗n×ni∈n∪F⟵$EG.ESkπ∗n×n. Hence, these two distributions are computationally distinguishable, according to the security of PRF, with the probability at most n⋅AdvA2PRFk for a PRF adversary A2. In addition, since for φ1∗ from ti′∗ in Game 3, the matrix F is random, so is the matrix U, and the adversary is always given answers “injective” except with the negligible probability ε. Thus, it holds that PrS3−PrS2≤n⋅AdvA2PRFk+n′⋅ε when n′=1.(ii)
Suppose that the above resultPrS3−PrS2≤n⋅AdvA2PRFk+n′⋅ε holds for η=n′−1≥1. Accordingly, in Game 3, we simply answer “injective” without even looking at the query φi∗.(iii)
Now, we consider the case ofn′. In Game 3, for tags ti′∗i∈η+1, we only focus on the n′th query tag tη+1′∗. In Game 2, we honestly derived the “injective” answers for the previous η queries, and the n′th answer is computed as U=DE3−F. Since PRF in Game 3 is only evaluated on UHFsφi∗i∈n∪UHFsφη+1∗ and since in Game 2 by inductive hypothesis the answers were all “injective,” the inductive hypothesis still holds, i.e., PrS3−PrS2≤n⋅AdvA2PRFk+η+1⋅ε. As a result, for all n′=n′k, we set neg1k=n′⋅ε, and it holds that(25)PrS3−PrS2≤nAdvA2PRFk+neg1k.
We note that tagsti′∗i∈n′ in Game 3 are distributed as random tags.
InGame 4, the trapdoor tdchf′ of chameleon hash function CHF is not available. Each primary part of tag t′ is sampled uniformly at random, i.e., D,Rchf⟵$EG.ESk,π∗n×n×ℛchf. Thus, it holds that PrS4=PrS3. In addition, for any fresh φ, we randomly select a matrix F⟵$EG.ESk,π∗n×n, that is, there is not an adversary that will output Type 2 tags with at most a negligible probability neg2k, so we could get PrS4,2≤neg2k. The Type 1 outputs will break the collision resistance of the chameleon hash function CHF, so we have PrS4,1≤AdvA3COLLk for some adversary A3. Therefore, we could obtain PrS4≤neg2k+AdvCHF,A3COLLk.
Summing up, letnegk=neg1k+neg2k, and we find that the advantage of adversary A is(26)AdvABM.LTF′,AEVA−PSAk⩽2n2+nAdvEG,A1EPR−PSAk+nAdvA2PRFk+AdvCHF,A3COLLk+negk.


## 4.1. ABM-LTF-PSA from Embeddable Group Family

LetCHF=CHF.Kg,CHF.Eval,CHF.Equ be a chameleon hash function, ℋ1:G⟶0,1∗ be a hash function, and EG=EG.P,EG.G,EG.S,EG.E,EG.I be an embeddable group family (we have recalled in the Section 2.2) [20]. We assume that the multiplication and addition operations hold on EG.ES. In addition, we note that the algorithm EG.E of EG is deterministic as the instantiations of EG in [20]. An ABM-LTF-PSA based on the embeddable group family is a tuple of algorithms ABM.LTF′=ABM.P′,ABM.Kg′,ABM.Eval′,ABM.Inv′,ABM.LTg′ that specified as following.(i)
ABM.P′1k: taking as input the security parameter k, it runs the EG.P1k algorithm of EG to generate a system parameter π.(ii)
ABM.Kg′1k,π: the key generation algorithm does the following steps:(1)
Generate a public keypkchf and the corresponding trapdoor tdchf of the CHF using CHF.Kg. This CHF will be used in the following to compute tags of ABM.LTF’.(2)
Generate an embedding cyclic groupG=G,q,g by running EG.G1k,π.(3)
Letn=nk. Sample αij∈ℤqn×n, βij∈ℤqn×n, and δij∈ℤqn×n by running EG.S1k,π,G for 1≤iandj≤n, and set three matrixes S1=αijn×n, S2=βijn×n, and S3=δijn×n.(4)
Set matrixesA=gαijn×n, B=gβijn×n, and C=gδijn×n for g generated in Step 2.(5)
Computeσij by running EG.E1k,π,G,Aij, θij by running EG.E1k,π,G,Bij, and τij by running EG.E1k,π,G,Cij for 1≤iandj≤n. We have σij,θij,andτij∈EG.ESk,π. Set matrixes E1=σijn×n, E2=θijn×n, and E3=τijn×n.(6)
Select a pseudorandom functionPRF:0,1∗×0,1l2⟶0,1l. Run EG.S1k,π,G to get vector e=e1,e2,…,en∈ℤq1×n. Set vector k=κ1,κ2,…,κn∈0,1∗ as the key of the PRF, where κi=ℋ1gei. Run τij to compute κ′i∈EG.ESk,π and get vector k′=κ′1,κ′2,…,κ′n as the hiding vector of k. We note that k should be kept secret and k′ could be public.(7)
Select an universal hash functionUHFs:0,1l1×0,1l3⟶0,1l2 with key s∈0,1l3. Sample a matrix Hn×n from the embedding space EG.ESk,π, and we use hi to denote the ith row of H.(8)
Set the public evaluation keyekabm′=C,E1,E2,pkchf,k′,s,H,G, private inversion key ikabm′=C,S1,S2,k,s,H,G, and lossy tag generation key tkabm′=E3,k,s,H,tdchf,G.(iii)
Tags: a tag in ABM.LTF′ is defined in the form of t′=tp′,ta′, where ta′∈0,1∗ is an auxiliary part, tp′=D,Rchf∈EG.ESk,πn×n×ℛchf is a primary part, and Rchf∈ℛchf is a randomness for CHF. Set the tag space as T′=EG.ESk,πn×n×ℛchf×0,1∗. With a tag t′=D,Rchf,ta, we compute φ=CHF.Evalpkchf,D,ta′;Rchf∈0,1l1. Let matrix U=DE3−F where F=f1,f2,…,fnT and fi=PRFκi,UHFsφ⋅hi is the ith row of F for 1≤i≤n. We define(11)t′∈Tinj′,RankU=n;Tlos′,U=0;Tinv′,RankU≠nandRankU≠0.We say thatt′ is an injective tag if the rank of matrix U is n, i.e., RankU=n; else, if U=0, we say that t′ is a lossy tag; particularly, if the rank of matrix U is out of the above two cases, i.e., RankU≠n and RankU≠0, we say that t′ is an invalid tag.(iv)
ABM.Eval′ekabm′,t′,x: with a tag t′=D,Rchf,ta′ and the public evaluation key ekabm′=C,E1,E2,pkchf,k′,s,H,G, for a vector of preimage input x=x1,x2,…,xn∈ℤq1×n, the algorithm does the following:(1)
For tagt′, compute φ=CHF.Evalpkchf,D,ta′;Rchf∈0,1l1. With k′, recover the key vector k=κ1,κ2,…,κn of PRF as κi=ℋ1gei, where gei is computed by running EG.I1k,π,G,κ′i.(2)
For matrixesE1=σijn×n and E2=θijn×n, compute gαij and gβij by running EG.I1k,π,G,E1ij and EG.I1k,π,G,E2ij correspondingly. Obtain the matrixes A=gαijn×n and B=gβijn×n, where 1≤iandj≤n. Randomly select μ and υ from ℤq by running EG.S1k,π,G, and compute s1=gμ, s2=gυ, and E=Aμ+Bυ, i.e., Eij=Aijμ+Bijυ=gαijμ+gβijυ. Compute ϖ1 by running EG.E1k,π,G,s1 and ϖ2 by running EG.E1k,π,G,s2, where ϖ1andϖ2∈EG.ESk,π.(3)
Computeτij by running EG.E1k,π,G,Cij to obtain matrix E3=τijn×n for 1≤iandj≤n. Concatenating matrixes E and U to obtain the matrix Mn×2n. That is, M=E|U∈EG.ESk,πn×2n, where U=DE3−F, F=f1,f2,…,fnT, and fi=PRFκi,UHFsφ⋅hi for 1≤i≤n.(4)
Computex¯i by running EG.E1k,π,G,gxi to set a vector x¯=x¯1,x¯2,…,x¯n, where x¯i∈EG.ESk,π,1≤i≤n.(5)
Compute the following equation to get the image vectory∈EG.ESk,π1×2n:(12)y=∑i=1nPRFκi,UHFsφ⋅x¯⋅M.(6)
Outputy,ϖ1,ϖ2.(v)
ABM.Inv′ikabm′,t′,y,ϖ1,ϖ2: given an inversion key ikabm′=C,S1,S2,k,s,H,G, a tag t′=D,Rchf,ta′, ϖ1andϖ2, and image vector y, the algorithm ABM.Inv′ computes x as follows:(1)
Computes1ands2 by running EG.I1k,π,G,ϖ1 and EG.I1k,π,G,ϖ2. Compute E1′=s1S1 and E2′=s2S2, which means that E1′ij=gμαij and E2′ij=gυβij. Obtain the matrix E by computing E=E1′+E2′, that is, Eij=gμαij+gυβij. Compute M=E|U∈EG.ESk,πn×2n as the algorithm ABM.Eval′.(2)
For tagt′=D,Rchf,ta′, it first computes φ=CHF.Evalpkchf,D,ta′;Rchf∈0,1l1.(3)
Withikabm′, it computes the following equation to get x¯:(13)x¯=y⋅M−1∑i=1nPRFκi,UHFsφ,whereM−12n×n is the inverse matrix of M.(4)
Finally, it computes and outputs the vector of preimagex by running EG.I1k,π,x¯.(vi)
ABM.LTg′tkabm′: the lossy tag generation algorithm is given the lossy tag generation key tkabm′. It does the following steps to compute a lossy tag t′=tp′,ta′:(1)
Randomly choose a tagt′˜=D˜,R˜chf,t˜a′∈T′, and then, compute the value φ=CHF.Evalpkchf,D˜,t˜a′,R˜chf.(2)
Solve for an appropriaten×n matrix D∈EG.ESk,πn×n such that the equation DE3=F is valid, where F=f1,f2,…,fnT, fi=PRFκi,UHFsφ⋅hi, for 1≤i≤n.(3)
Compute the valueRchf from the equation Rchf=CHF.Equtdchf,D˜,t˜a′,D,ta′;R˜chf, and output a tag t′=D,Rchf,ta′. It is easy to check that the tag t′ output by this algorithm is indeed a lossy one.Correctness. We note that the correctness of the above ABM-LTF-PSA instantiation holds due to the following equation:(14)E=Aμ+Bυ=s1S1+s2S2=E1′+E2′=E.Lossiness. For any lossy tag t′∈Tlos′ in the above ABM-LTF-PSA instantiation, we note that its lossiness l=log2qn/n2EG.ESk,π. When t′∈Tlos′, the matrix U is equal to 0, i.e., U=0, we have at most n2 possible values of M=E|U∈EG.ESk,πn×2n. Thus, the image set ABM.Eval′ekabm′,t′,ABM.Dom′ has size n2EG.ESk,π. Meanwhile, the size of domain ABM.Dom′ of the ABM.Eval′ is qn because the preimage of ABM.LTF′ is x∈ℤq1×n. According to the definition of lossiness for ABM.LTF′, we could obtain the lossiness of the above construction is l=log2qn/n2EG.ESk,π.


## 4.2. Proofs of Security

Lemma 2.
Letn is polynomial in k and q is exponential in the security parameter k. A matrix X randomly sampled from ℤqn×n will have RankX=n with all but negligible probability in k.Proof.
The probability ofRankX=n is equal to the probability that n columns of X are linearly independent. This means that there are qn−1 possibilities (i.e., the zero vector is removed) for the sample of the first column vector. For the sample of the second column vector, there are qn−q possibilities (i.e., the q vectors linearly dependent on the first vector should be removed). The rest may be deduced by analogy. Thus, the probability of RankX=n is(15)qn−1⋅qn−q⋅qn−q2⋯qn−qn−1qn⋅qn⋯qn=∏i=1n1−1qi=1−1qfunck,where funck is a function satisfying that 0<funck≤n1+1/q+⋯+1/qn. Because q is exponential in k, 1/qfunck is negligible in k. So, we could finally obtain that this probability is overwhelming.Theorem 1 (indistinguishability).
LetEG be an efficiently-embeddable group and CHF be a chameleon hash function. Let ABM.LTF′ be the all-but-many lossy trapdoor function that we built above. For any PPT adversary A with advantage AdvABM.LTF′,AIND−PSA3, there exists adversaries A1 and A2 such that(16)AdvABM.LTF′,AIND−PSA3k⩽2n2+nAdvEG,A1EPR−PSAk+nAdvA2PRFk.Proof.
We proceed with the proof by describing a sequence of games, i.e.,Game 1 to Game 3. Let Si be the event that the output of adversary A is 1 in Gamei. In Game 1, all algorithms work exactly the same as the real scheme. A interacts with ABM.LTg′tkabm′,⋅, and the algorithm outputs lossy tags for adversary A. We emphasis that the system parameter π∗ involved in this game is chosen by A. So, we obtain(17)PrS1=PrAABM.LTg′tkabm′,⋅1k,ekabm′=1.
InGame 2, we modify the way of generating the public evaluation key ekabm′=C,E1,E2,pkchf,k′,s,H,G. Specially, we choose the matrixes E1 and E2 and the vector k′ uniformly at random from EG.ESk,π∗. Since E1, E2, and k′ do not influence the output distribution of ABM.LTg′, by the EPR-PSA assumption of EG, this modification will not be noticed by A. So, for an EPR-PSA adversary A1, we obtain(18)PrS2−PrS1≤2n2+nAdvEG,A1EPR−PSAk.
InGame 3, the proceeding of algorithm ABM.LTg′ is changed. Particularly, in the 2nd step of algorithm ABM.LTg′, we randomly select a matrix F⟵$EG.ESk,π∗n×n instead of computing a matrix F=f1,f2,…,fnT, in which fi=PRFκi,UHFsφ⋅hi with uniformly random φ for 1≤i≤n, as in Game 2. According to the PRF security (defined in Figure 1) of the pseudorandom function, for a PPT adversary A2 against PRF, we could obtain(19)PrS3−PrS2≤nAdvA2PRFk.
On the contrary, inGame 3, the matrix D of tp′ is the solution of equation DE3=Fmodq with random F. If the rank of matrix E3 is n, then D will be random. According to Lemma 2 (same result holds for EG.ESk,πn×n), we indeed have RankE3=n. This means that D is random. Thus, we could obtain result that the primary part tp′=D,Rchf of tag t′ is random. Therefore, all tags generated in Game 3 are random tags. So, we obtain(20)PrS3=PrAOT′⋅1k,ekabm′=1.
Summing up, we find that the advantageAdvABM.LTF′,AIND−PSA3k of adversary A is(21)PrAABM.LTg′tkabm′,⋅1k,ekabm′=1−PrAOT′⋅1k,ekabm′=1≤2n2+nAdvEG,A1EPR−PSAk+nAdvA2PRFk.Theorem 2 (evasiveness).
LetEG be the efficiently-embeddable group and CHF be a chameleon hash function. Let ABM.LTF′ be the all-but-many lossy trapdoor function that we built above. For any PPT adversary A with advantage AdvABM.LTF′,AEVA−PSA, there exist adversaries A1, A2, and A3 such that(22)AdvABM.LTF′,AEVA−PSAk⩽2n2+nAdvEG,A1EPR−PSAk+nAdvA2PRFk+AdvCHF,A3COLLk+negk.Proof.
We proceed with the proof by describing a sequence of games,Game 1 to Game 4. Let Si be the event that the output of adversary A is a lossy or invalid tag in Gamei. We consider the following two types of tags output by A. Specifically, for a tag t′=D∗,Rchf∗,ta′∗,(i)
Type 1: if φ∗=CHF.Evalpkchf,D∗,ta′∗;Rchf∗ is also the chameleon hash output of some previously generated tag, then we refer to t′=D∗,Rchf∗,ta′∗ as a Type 1 tag.(ii)
Type 2: if φ∗=CHF.Evalpkchf,D∗,ta′∗;Rchf∗ is not the chameleon hash output of any previously generated tag, then we refer to t′=D∗,Rchf∗,ta′∗ as a Type 2 tag.
We make an assumption, without loss of generality, thatA obtains n=nk lossy tags by querying the ABM.LTg′tkabm′ oracle. Let ti′i∈n=Di,Rchfi,tai′i∈n denote these lossy tags. Then, A adaptively comes up with n′=n′k tags ti′∗i∈n′=Di∗,Rchfi∗,tai′∗i∈n′ by querying the oracle OT′ and gets answers “invalid” or “injective.”
InGame 1, all algorithms work exactly the same as the real scheme. In particular, we note that the system parameter π∗ involved in this game is chosen by A. So, we have(23)AdvABM.LTF′,AEVA−PSAk=PrS1.
InGame 2, we modify the way of generating the public evaluation key ekabm′=C,E1,E2,pkchf,k′,s,H,G. Specially, we choose the matrixes E1 and E2 and the vector k′ uniformly at random from EG.ESk,π∗. Since E1, E2, and k′ do not influence the output distribution of ABM.LTg′, by the EPR-PSA assumption of EG, this modification will not be noticed by A. So, for an EPR-PSA adversary A1, we obtain(24)PrS2−PrS1≤2n2+nAdvEG,A1EPR−PSAk.
InGame 3, we change the algorithm ABM.LTg′. In particular, in the 2nd step of ABM.LTg′, we randomly select a matrix F⟵$EG.ESk,π∗n×n for any φ, instead of computing a matrix F=f1,f2,…,fnT, in which fi=PRFκi,UHFsφ⋅hi. For all queries ti′∗i∈n′ to the OT′ oracle, we return the answer “injective.” In the following context, we will use the mathematical methods of induction to prove that the distinguishability of Game 2 and Game 3 implies that there is an adversary A2 against the pseudorandom function PRF.(i)
For the base step, supposen′=1 (the case n′=0 is vacuous). In Game 2, OT′ honestly computes U=DE3−F, where F=f1,f2,…,fnT and fi=PRFκi,UHFsφ1∗⋅hi, for 1≤i≤n. Then, it returns the answer “injective.” The distributions of U in Game 2 and Game 3 are correspondingly PRFκj,UHFsφi∗j∈n∪PRFκj,UHFsφ1∗ and Fi⟵$EG.ESk,π∗n×ni∈n∪F⟵$EG.ESkπ∗n×n. Hence, these two distributions are computationally distinguishable, according to the security of PRF, with the probability at most n⋅AdvA2PRFk for a PRF adversary A2. In addition, since for φ1∗ from ti′∗ in Game 3, the matrix F is random, so is the matrix U, and the adversary is always given answers “injective” except with the negligible probability ε. Thus, it holds that PrS3−PrS2≤n⋅AdvA2PRFk+n′⋅ε when n′=1.(ii)
Suppose that the above resultPrS3−PrS2≤n⋅AdvA2PRFk+n′⋅ε holds for η=n′−1≥1. Accordingly, in Game 3, we simply answer “injective” without even looking at the query φi∗.(iii)
Now, we consider the case ofn′. In Game 3, for tags ti′∗i∈η+1, we only focus on the n′th query tag tη+1′∗. In Game 2, we honestly derived the “injective” answers for the previous η queries, and the n′th answer is computed as U=DE3−F. Since PRF in Game 3 is only evaluated on UHFsφi∗i∈n∪UHFsφη+1∗ and since in Game 2 by inductive hypothesis the answers were all “injective,” the inductive hypothesis still holds, i.e., PrS3−PrS2≤n⋅AdvA2PRFk+η+1⋅ε. As a result, for all n′=n′k, we set neg1k=n′⋅ε, and it holds that(25)PrS3−PrS2≤nAdvA2PRFk+neg1k.
We note that tagsti′∗i∈n′ in Game 3 are distributed as random tags.
InGame 4, the trapdoor tdchf′ of chameleon hash function CHF is not available. Each primary part of tag t′ is sampled uniformly at random, i.e., D,Rchf⟵$EG.ESk,π∗n×n×ℛchf. Thus, it holds that PrS4=PrS3. In addition, for any fresh φ, we randomly select a matrix F⟵$EG.ESk,π∗n×n, that is, there is not an adversary that will output Type 2 tags with at most a negligible probability neg2k, so we could get PrS4,2≤neg2k. The Type 1 outputs will break the collision resistance of the chameleon hash function CHF, so we have PrS4,1≤AdvA3COLLk for some adversary A3. Therefore, we could obtain PrS4≤neg2k+AdvCHF,A3COLLk.
Summing up, letnegk=neg1k+neg2k, and we find that the advantage of adversary A is(26)AdvABM.LTF′,AEVA−PSAk⩽2n2+nAdvEG,A1EPR−PSAk+nAdvA2PRFk+AdvCHF,A3COLLk+negk.


## 5. Construction of IND-SO-PSA Secure PKE Scheme

Taking the constructions in [32–34, 39] as guidances, we propose an IND-SO-PSA secure PKE scheme with the newly-built ABM-LTF-PSA and LTF-PSA based on an efficiently-embeddable group family. Let ABM.LTF′=ABM.P′,ABM.Kg′,ABM.Eval′,ABM.Inv′,ABM.LTg′ be an all-but-many lossy trapdoor function in the presence of PSA we constructed in Section 4, LTF′=LTF.P′,LTF.IKg′,LTF.LKg′,LTF.Eval′,LTF.Inv′ be a lossy trapdoor function in the presence of PSA, and EG=EG.P,EG.G,EG.S,EG.EE,EG.I be the underlying embeddable group family of ABM.LTF′ and LTF′. Let ℋ2:EG.ESk,π⟶0,1l1 be a hash function and CHF=CHF.Kg,CHF.Eval,CHF.Equ be a chameleon hash function.The schemePKE=PKE.P,PKE.Kg,PKE.Enc,PKE.DEC will be built as follows.(i)
PKE.P1k: taking as input the security parameter k, it runs the EG.P1k algorithm of EG to generate a system parameter π. We note that here π is also used as the system parameter of ABM.LTF′ and LTF′ in this construction.(ii)
PKE.Kg1k,π: the key generation algorithm does the following steps:(1)
Run algorithmABM.Kg′1k,π to get ekabm′,ikabm′,tkabm′. Have the same embeddable group G with generator g and order q and the same public key pkchf of CHF as generated in the step 1 and step 2 of algorithm ABM.Kg′.(2)
Run algorithmLTF.IKg′1k,π to get ek′,ik′. Set the public key as pk=ekabm′,ek′,pkchf and the secret key as sk=ikabm′,ik′. It finally outputs a pair of public and secret keys pk,sk.(iii)
PKE.Encpk,m: with the public key pk=ekabm′,ek′,pkchf and the message m∈0,1l2, the encryption algorithm PKE.Encpk,m does the following:(1)
Randomly select a vectorr=r1,r2,…,rn from ℤq1×n by running EG.S1k,π,G.(2)
Computer¯i by running EG.E1k,π,G,gri for 1≤i≤n, and set vector r¯=r¯1,r¯2,…,r¯n. That is, we have r¯i∈EG.ESk,π.(3)
Randomly select an universal hash functionUHFw:0,1l1×0,1l3⟶0,1l2 with index key w∈0,1l3. Compute Θ=ℋ2r¯, ρ=UHFwΘ⊕m, and y1=LTF.Eval′ek′,r. We note that UHFw is not the same one used in the construction of ABM.LTF′.(4)
Sett′=tp′,ta′ for randomly-sampled tp′=D,Rchf and ta′=UHFw,ρ,r; then, compute φ=CHF.Evalpkchf,D,ta′,y1;Rchf. We note that CHF is the same one used in the construction of ABM.LTF′.(5)
Useφ as the input of the step 3 of the ABM.Eval′ algorithm, and compute y2=ABM.Eval′ekabm′,t′,r. Notice that y2 is a tuple y^,ϖ1,ϖ2 as described in the step 6 of ABM.Eval′. Output the ciphertext C=y1,y2,tp′,UHFw,φ,ρ. Note that the randomness of this encryption algorithm contains w and t′, and all components in t′ are public except r.(iv)
PKE.DecC,sk: after receiving the ciphertext C=y1,y2,tp′,UHFw,φ,ρ, the decryption algorithm does the following:(1)
Run algorithmLTF.Inv′ik′,y1 to obtain the vector r=r1,r2,…,rn.(2)
Run algorithmABM.Eval′ekabm′,t′,r to compute y2′ with the tag t′=tp′,ta′, where tp′=D,Rchf and ta′=UHFw,ρ,r. Check that whether the equation y2′=y2 holds. If not, then return ⊥; otherwise, go to the next step.(3)
Computeφ′=CHF.Evalpkchf,D,ta′,y1;Rchf. If φ=φ′, reject this ciphertext; otherwise, go to the next step.(4)
Computer¯i by running EG.E1k,π,G,gri for 1≤i≤n to obtain vector r¯=r¯1,r¯2,…,r¯n. Compute Θ=ℋ2r¯, and recover the message from m=UHFwΘ⊕ρ.


## 6. Security Analysis

In this section, we analyse the IND-SO-PSA security of our PKE scheme constructed in Section5. In particular, we prove that our scheme can satisfy the IND-SO-PSA security which is defined in Section 3.3. We will give more detailed proofs of security in the following. We note that the proof is processed without random oracle.Theorem 3 (IND-SO-PSA).
LetABM.LTF′ be the newly proposed all-but-many lossy trapdoor function from the embeddable group family scheme we built in Section 4, LTF′ be a lossy trapdoor function in the presence of PSA, and CHF be a chameleon hash function. For any PPT adversary A with advantage AdvPKE,AIND−SO−PSAk, there exist adversaries A1, A2, A3, and A4 such that(27)AdvPKE,AIND−SO−PSAk⩽AdvCHF,A1COLLk+AdvABM.LTF′,A2IND−PSA3k+AdvABM.LTF′,A3EVA−PSAk+AdvLTF′,A4IND−PSA2k+negk.Proof.
We firstly revisit the definition of the IND-SO-PSA security (shown in Figure5). Suppose that we have n challenge ciphertexts, and the ith challenge ciphertext is denoted as Ci=y1i,y2i,tp′i,UHFwi,φi,ρi in which tp′i=Di,Rchfi. We proceed with the proof by describing a sequence of games, Game 1 to Game 6. Let Si be the event that the output of adversary A is 1 in Gamei. In Game 1, all algorithms work exactly the same as the game GPKE,AIND−SO−PSAk. We note that the system parameter π∗ involved in this game is chosen by A, as shown in Figure 5. By the definition of IND-SO-PSA security, we have(28)AdvPKE,AIND−SO−PSAk=PrS1−12.
InGame 2, we note that the decryption queries whose element φi has already existed in one of the challenge ciphertexts were rejected. That is, if adversary A queries decryption oracle with a ciphertext C=y1,y2,tp′,UHFw,φi,ρ in which φi is appeared in some Ci=y1i,y2i,tp′i,UHFwi,φi,ρi, then it will be rejected, or the collision resistant property of CHF will be broken. We note that the only element that is not a part of the inputs of CHF in ciphertext C is y2. Let ta′=UHFw,ρ,r and ta′i=UHFwi,ρi,ri. In the following, we consider three cases:(i)
y2=y2i and y1,tp′,UHFw,ρ=y1i,tp′i,UHFwi,ρi: this is the case that the query ciphertext is precisely the ith challenge ciphertext. Thus, this decryption query should be rejected.(ii)
y2=y2i and y1,tp′,UHFw,ρ≠y1i,tp′i,UHFwi,ρi: to recover the encrypted message, the decryption algorithm has to verify the correctness of the tag of ABM.LTF′ by executing the equivocation algorithm of CHF. This would happen only if the following equation holds: CHF.Evalpkchf,D,ta′,y1;Rchf=CHF.Evalpkchf,Di,ta′i,y1i;Rchfi, which means that there exist a collision of chameleon hash function CHF.(iii)
y2≠y2i: recall that φ=φi is computed by an injective tag. We will consider the following cases. (1) y1=y1i and tp′,UHFw,ρ=tp′i,UHFwi,ρi: the output of this query in step 1 is r. It is obvious that r=ri. Thus, we can get ta′=ta′i. In this case, there is indeed a collision D,ta′,y1;Rchf and Di,ta′i,y1i;Rchfi happening to CHF. (2) y1=y1i and tp′,UHFw,ρ≠tp′i,UHFwi,ρi: similar to the above case, we must have r=ri and ta′=ta′i. Then, the query will be rejected unless a collision happens to CHF. (3) y1≠y1i and tp′,UHFw,ρ=tp′i,UHFwi,ρi: the output of this decryption query in the step 1 is r, and we must have r≠ri, and thus, ta′≠ta′i. Then, the query will be rejected unless an exact collision D,ta′,y1;Rchf and Di,ta′i,y1i;Rchfi happens to CHF. (4) y1≠y1i and tp′,UHFw,ρ≠tp′i,UHFwi,ρi: similar to the above case, we must have r≠ri and ta′≠ta′i. Then, the query will be rejected unless a collision happens.
Therefore,Game 1 to Game 2 behaves the same unless the collision resistancy of the chameleon hashing is broken. Thus, for some adversary A1, it holds that(29)PrS2−PrS1≤AdvCHF,A1COLLk.
InGame 3, we generate the lossy tags by running the ABM.LTg′ for all challenge ciphertexts Ci for i∈n. Note that we allow the decryption query made with lossy tags in which φ≠φi. According to the indistinguishability under PSA of the ABM.LTF′, for some adversary A2, we have(30)PrS3−PrS2≤AdvABM.LTF′,A2IND−PSA3k.
Recall that, inGame 3, we firstly run the algorithm LTF.Inv′ik′,y1 to obtain the vector r. Then, we check that ABM.Eval′ekabm′,t′,r=y2. If it is not, then reject. Now, in Game 4, with ikabm′, we run the algorithm ABM.Inv′ to recover r. Particularly, in the step 3 of ABM.Inv′, the value φ is the one contained in the ciphertext for the decryption query. According to the correctness of ABM.LTF′ and LTF′, Game 4 and Game 3 could have the same result unless the component φ of decryption query belonging to one of the challenge ciphertexts or the queries are made with lossy or invalid tags. We have to consider the previous sitution in Game 3. The latter would happen unless the evasiveness under the PSA property of ABM.LTF′ is broken. Thus, for some adversary A3, we get(31)PrS4−PrS3≤AdvABM.LTF′,A3EVA−PSAk.
InGame 5, a lossy evaluation key is generated for LTF′. So, for some adversary A4, we have(32)PrS5−PrS4≤AdvLTF′,A4IND−PSA2k.
InGame 6, the element ρ of each challenge ciphertext is set as ρ=γ⊕m where γ is selected randomly from 0,1l2. As in Game 5, the y2 elements are computed by ABM.LTF′ with lossy tags for all challenge ciphertexts. Thus, according to Lemma 1, we have(33)PrS6−PrS5≤negk.
InGame 6, since all challenge messages have been padded, the adversary A could get no information about them. The original message vector m0 and conditionally re-sampled message vector m1 come from the same distribution, so PrS6=1/2. Summing up, we could get that AdvPKE,AIND−SO−PSAk⩽AdvCHF,A1COLLk+AdvABM.LTF′,A2IND−PSA3k+AdvABM.LTF′,A3EVA−PSAk+AdvLTF′,A4IND−PSA2\\k+negk.


## 7. Conclusion

In this paper, to capture SOA and PSA simultaneously, we introduce a new security notion called IND-SO-PSA, which captures indistinguishability under parameter subversion attacks, selective opening attacks, and chosen ciphertext attacks. IND-SO-PSA security guarantees that even though the system parameter of the PKE scheme is chosen maliciously and the adversary is allowed to open a subset of the challenge ciphertexts (i.e., seeing the corresponding plaintexts and randomness used during the encryption), the remainder of the plaintexts should be indistinguishable from freshly re-sampled ones. In order to construct IND-SO-PSA secure PKE, we introduce two new primitives (i.e., LTF-PSA and ABM-LTF-PSA) and propose their instantiations with an efficiently-embeddable group family. Then, based on these new primitives, we construct a PKE scheme satisfying the newly-proposed IND-SO-PSA security.



---

*Source: 5895809-2021-10-23.xml*