# Tightly Secure Lossy Trapdoor Functions: Constructions and Applications

Authors: Baodong Qin
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Lossy trapdoor functions (LTFs), introduced by Peiker and Waters in STOC’08, are functions that may be working in another injective mode or a lossy mode. Given such a function key, it is impossible to distinguish an injective key from a lossy key for any (probabilistic) polynomial-time adversary. This paper studies lossy trapdoor functions withtight security. First, we give a formal definition for tightly secure LTFs. Loosely speaking, a collection of LTFs is tightly secure if the advantage to distinguish a tuple of injective keys from a tuple of lossy keys does not degrade in the number of function keys. Then, we show that tightly secure LTFs can be used to construct public-key encryption schemes with tight CPA security in a multiuser, multichallenge setting, and with tight CCA security in a multiuser, one-challenge setting. Finally, we present a construction of tightly secure LTFs from the decisional Diffie-Hellman assumption.


---

## Body

## 1. Introduction

In STOC’08, Peikert and Waters [1] introduced the notion of lossy trapdoor functions (LTFs), which have been proven to be a powerful primitive in cryptography. Specifically, LTFs imply many cryptographic primitives, such as (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, correlated-product trapdoor functions [2], and adaptive trapdoor functions [3] and have many “higher level” applications, such as leakage-resilient chosen-ciphertext secure cryptosystems [4–6] and deterministic public-key encryption [7].Informally, an LTF is a function that can work in one of two computationally indistinguishable modes: injective mode and lossy mode. In the injective mode, each function is invertible via a trapdoor. In the lossy mode, each function statistically loses information about its input. Thus, in the security proof (e.g., PKE scheme), the change that a function works in the lossy mode from the injective mode has only a negligible effect on the adversary’s advantage. In addition, once all functions work in the lossy mode, a ciphertext contains nearly no information any more about the encrypted message. Such property can be used to achieve CPA security. LTFs parameterized with a tag are useful in the context of CCA-secure PKE schemes. One such tag-based LTFs are all-but-one lossy trapdoor functions (ABO-LTFs), also proposed in [1]. In ABO-LTFs, all of the tags are injective, except for one tag which is lossy. The lossy tag and the injective tag are (computationally) indistinguishable. There are also many variants of lossy trapdoor functions that are used in diverse scenarios, such as updatable lossy trapdoor functions [4, 5, 8], chameleon ABO-LTFs [9], evasive all-but-many LTFs [10] and all-but-many lossy trapdoor functions [11].Security Proofs by Reductions. Many cryptographic primitives, including lossy trapdoor functions, are designed around computational hardness assumptions (e.g., factoring an integer that is a product of two large primes). The approach to prove security often uses the security reduction technique which aims to convert any efficient algorithm (also called adversary) A that breaks the primitive with probability ϵA to an efficient algorithm B that solves the underlying computational problem with probability ϵB. We say that the security reduction is tight if ϵB≈ϵA. Here, we simply assume that the running times of algorithms A and B are roughly the same. If we consider the explicit relations between the success probabilities, the security reductions often suffer from a nontrivial multiplicative reduction loss L such that only ϵA≤L·ϵB can be guaranteed. A tight security reduction also means that the reduction loss L is a (small) constant.Design of cryptographic primitives with tight security reduction is an important problem since loose reductions imply security loss and large keys are needed to achieve a satisfactory level of security. However, many cryptographic primitives often suffer from loose security reduction, especially in a multiuser (or multichallenge) setting. Taking lossy trapdoor functions as an example, standard security notion for LTFs only considers one-user setting; i.e., the advantage of an adversary is defined to distinguish just one injective key from one lossy key. For multiple users, there will be many LTF keys. However, a generic hybrid security proof usually suffers from a reduction lossL=nu, where nu is the number of users. The issue of loose reduction may result in a significantly practical consequence. As an example, consider a realistic setting that there are 210 users. According to the above discussion, the security level in the multiuser case reduces 210 times than that in the one-user setting. In other words, a secure lossy trapdoor functions may not be secure again in the multiuser setting. LTFs have been used to build many high level cryptographic primitives, e.g., PKE, and the latter usually work in a multiuser setting. Though there are many constructions of lossy trapdoor functions [1, 12, 13], to the best of our knowledge, however, there is no study on lossy trapdoor functions in the multiuser setting.


### 1.1. Our Contribution

In this paper, we initially study lossy trapdoor functions in a multiuser setting and formalize the notion of tightly secure lossy trapdoor functions. A collection of tightly secure LTFs is still a collection of LTFs, except that, in a multiuser setting, the security reduction does not degrade in the number of users. This new notion seems to enhance the security of standard LTFs, but does not change the functionality of LTFs. We show that tightly secure LTFs can be used to construct tightly secure public-key encryption (PKE) against chosen-plaintext attacks (CPA) in the multiuser, multichallenge setting (multichallenge means that each user’s public key may be used to encrypt many challenge messages).We naturally extend tight security from LTFs to ABO-LTFs and propose the notion of tightly secure ABO-LTFs. We show that a collection of tightly secure LTFs with a suitable collection of tightly secure ABO-LTFs can be used to construct tightly secure PKE against adaptive chosen-ciphertext attacks (CCA) in multiuser, one-ciphertext setting. In this application, it requires an additional cryptographic primitive, called strong one-time signature, to be tightly secure. We show that the discrete-log-based strong one-time signature scheme proposed in [14] is tightly secure.Under the decisional Diffie-Hellman (DDH) assumption, we construct a collection of tightly secure LTFs, as well as a collection of tightly secure ABO-LTFs. The tight security of them mainly benefits from the property of random self-reducibility of the underlying assumption.


### 1.2. Related Work: Tightly Secure PKE

Public-key encryption (PKE), as one of the most important cryptographic primitives, often suffers from a loose security reduction. Bellare et al. [15] showed that security of PKE in the simple one-user, one-ciphertext setting implies security in the much more realistic multiuser, multiciphertext setting. However, the generic security reduction suffers from a reduction loss L=nu·qe, where nu is the number of users and qe is the number of challenge ciphertexts.The design of PKE schemes with tight security reduction in multiuser, multiciphertext setting is not easy. One obstacle, as pointed out by Hofheinz and Jager [16], is that the simulator in the CCA security reduction needs to answer all of the adversary’s decryption queries except its own single (many) challenge ciphertext(s). To resolve this dilemma, nearly all of known PKE schemes use either the so-called “proof of well-formedness” [17] or the so-called “all-but-one technique” [18]. Yet both approaches can only guarantee to simulate one or few challenge ciphertexts at a time. To simulate many challenge ciphertexts, a hybrid argument is required. As a result, the security reduction loss grows linearly with the number of challenge ciphertexts. Hofheinz and Jager [16] applied the Naor-Yung paradigm (two tightly IND-CPA-secure PKEs and one tightly secure polynomial-time SS-NIZK) to obtain a generic construction of CCA-secure PKE scheme with tightly security reduction. As an example, they constructed the first PKE scheme with tight CCA security from the DLIN assumption with the usage of pairings. Later, Gay et al. [19] proposed the first tightly CCA-secure pairing-free public-key encryption scheme based on DDH assumption. Recently, Wei et al. [20] presented an improved PKE scheme of [16] with more compact ciphertext size, and Gay et al. [21] presented an improved tightly CCA-secure pairing-free PKE scheme with small ciphertexts and small public keys. Tightly secure all-but-many LTFs (ABM-LTFs) can be used to construct tightly (selective-opening) CCA-secured PKE schemes. However, to date, there are very few candidates of ABM-LTFs with well-tightness [22].


## 1.1. Our Contribution

In this paper, we initially study lossy trapdoor functions in a multiuser setting and formalize the notion of tightly secure lossy trapdoor functions. A collection of tightly secure LTFs is still a collection of LTFs, except that, in a multiuser setting, the security reduction does not degrade in the number of users. This new notion seems to enhance the security of standard LTFs, but does not change the functionality of LTFs. We show that tightly secure LTFs can be used to construct tightly secure public-key encryption (PKE) against chosen-plaintext attacks (CPA) in the multiuser, multichallenge setting (multichallenge means that each user’s public key may be used to encrypt many challenge messages).We naturally extend tight security from LTFs to ABO-LTFs and propose the notion of tightly secure ABO-LTFs. We show that a collection of tightly secure LTFs with a suitable collection of tightly secure ABO-LTFs can be used to construct tightly secure PKE against adaptive chosen-ciphertext attacks (CCA) in multiuser, one-ciphertext setting. In this application, it requires an additional cryptographic primitive, called strong one-time signature, to be tightly secure. We show that the discrete-log-based strong one-time signature scheme proposed in [14] is tightly secure.Under the decisional Diffie-Hellman (DDH) assumption, we construct a collection of tightly secure LTFs, as well as a collection of tightly secure ABO-LTFs. The tight security of them mainly benefits from the property of random self-reducibility of the underlying assumption.


## 1.2. Related Work: Tightly Secure PKE

Public-key encryption (PKE), as one of the most important cryptographic primitives, often suffers from a loose security reduction. Bellare et al. [15] showed that security of PKE in the simple one-user, one-ciphertext setting implies security in the much more realistic multiuser, multiciphertext setting. However, the generic security reduction suffers from a reduction loss L=nu·qe, where nu is the number of users and qe is the number of challenge ciphertexts.The design of PKE schemes with tight security reduction in multiuser, multiciphertext setting is not easy. One obstacle, as pointed out by Hofheinz and Jager [16], is that the simulator in the CCA security reduction needs to answer all of the adversary’s decryption queries except its own single (many) challenge ciphertext(s). To resolve this dilemma, nearly all of known PKE schemes use either the so-called “proof of well-formedness” [17] or the so-called “all-but-one technique” [18]. Yet both approaches can only guarantee to simulate one or few challenge ciphertexts at a time. To simulate many challenge ciphertexts, a hybrid argument is required. As a result, the security reduction loss grows linearly with the number of challenge ciphertexts. Hofheinz and Jager [16] applied the Naor-Yung paradigm (two tightly IND-CPA-secure PKEs and one tightly secure polynomial-time SS-NIZK) to obtain a generic construction of CCA-secure PKE scheme with tightly security reduction. As an example, they constructed the first PKE scheme with tight CCA security from the DLIN assumption with the usage of pairings. Later, Gay et al. [19] proposed the first tightly CCA-secure pairing-free public-key encryption scheme based on DDH assumption. Recently, Wei et al. [20] presented an improved PKE scheme of [16] with more compact ciphertext size, and Gay et al. [21] presented an improved tightly CCA-secure pairing-free PKE scheme with small ciphertexts and small public keys. Tightly secure all-but-many LTFs (ABM-LTFs) can be used to construct tightly (selective-opening) CCA-secured PKE schemes. However, to date, there are very few candidates of ABM-LTFs with well-tightness [22].


## 2. Preliminaries

### 2.1. Notations

IfS is a finite set then |S| denotes its size and s←$S denotes the operation of picking an element s uniformly at random from S. For any n∈N, we denote by [n] the set {1,…,n}. By 1λ, we denote the security parameter. We use PPT for the abbreviation of “ probabilistic polynomial-time”. We denote by z←A(x,y…) the operation of running an algorithm A with inputs (x,y…) and letting z be the output.


### 2.2. Complexity Assumptions

In the following, letG(1λ) be a PPT algorithm that takes as input a security parameter 1λ and outputs a description of group (G,p,g), where G is a group of prime order p and g is a random generator of G. For an arbitrary g1∈G, let logg(g1) denote the discrete logarithm g1 to base g such that g1=glogg(g1). Furthermore, for any generator g∈G, let DDH(G,p)(g) denote the set(1)DDHG,pg=ga,gb,gab:a,b∈Zp.Definition 1 (discrete logarithm assumption).
Letg∈G be a random generator of G and h∈G be a random group element. The discrete logarithm (DL) assumption states that the following advantage:(2)AdvA,Gdlλ≔Pr⁡a←Ag,h:ga=his negligible in λ for every PPT algorithm A.Definition 2 (decisional Diffie-Hellman assumption).
Letg∈G be a random generator of G and U←$DDH(G,p)(g), V←$G3. The decisional Diffie-Hellman (DDH) assumption in group G states that the advantage(3)AdvA,Gddhλ≔Pr⁡Ag,U=1-Pr⁡Ag,V=1is negligible in λ for every PPT algorithm A.Random Self-Reducibility of DDH [15, Lemma 5.1]. The tight security reduction of our LTFs and ABO-LTFs mainly benefit from the self-reducibility property of the DDH problem. Namely, there exists a PPT algorithm Rddh that takes as input the group order p, generator g, (ga,gb,gc)∈G3, and a bit x∈{0,1} and outputs (ga′,gb′,gc′)∈G3 such that we have the following. See Table 1.Table 1 x = 0 x = 1 a ′ = a a ′ is random c = a b  m o d  p b ′ is random b ′ is random c ′ = a ′ b ′ m o d  p c ′ = a ′ b ′  m o d  p  a ′ = a a ′ is random c ≠ a b  m o d  p b ′ is random b ′ is random c ′ is random c ′ is randomPairwise Independent Hash Functions. A family of hash functions H={h:D→R} from domain D to range R is called pairwise independent if, for every distinct x,x′∈D and every y,y′∈R, Pr⁡[h(x)=yandh(x′)=y′]=1/R2.Randomness Extractor [23, Lemma 2.4]. Let X,Y be two random variables such that X∈{0,1}n and H∞X∣Y≤l. Let H be a family of pairwise independent hash functions from {0,1}n to {0,1}k.Ifk≤l-2log⁡(1/ϵ), then H is an average-case strong extractor; i.e., the distribution (Y,h,h(X)) is statistically ϵ-close to the distribution (Y,h,r), where h←$H and r←${0,1}k.Strongly Unforgeable One-Time Signature. A one-time signature schemeOTS consists of three algorithms (OTS.Gen,OTS.Sign, andOTS.Vrf), where (1)OTS.Gen on input a security parameter 1λ outputs a verification key vk and a signing key sigk; (2)OTS.Sign on input a signing key sigk and a message m outputs a signature σ; (3)OTS.Vrf on input a verification key vk, a message m, and a signature outputs either 0 or 1. The correctness guarantees thatOTS.Vrf(vk,m,σ)=1 holds with probability 1, if and only if σ =OTS.Sign(sigk,m). Next, we define the security notion of strong existential unforgeability under a one-time chosen message attack in multiuser setting. It is defined through a game played between a challenger and a PPT adversary A. The challenger first generates independently n pairs of keys (vki,sigki) and gives all vki to the adversary. For each signing key sigki, the adversary can obtain at most one signature σi=OTS.Sign(sigki,mi) on a single message mi chosen by the adversary. Finally, the adversary outputs a pair (m,σ) and is said to succeed if there exists i∈[n] such that OTS.Vrf(vki,m,σ)=1 and (m,σ)≠(mi,σi). We denote by AdvOTS,Asu-cma(λ,n) the adversary’s success probability (advantage). A one-time signature scheme is strongly unforgeable if the adversary has negligible advantage. If the advantage is independent of the number of users, the signature scheme is said to be tightness.By the random self-reducibility of the discrete logarithm problem, we can show the following one-time signature scheme proposed in [14, Fig.4] is tightly secure in multiuser setting, if the schemes share the same group parameters. Let (G,p,g) be a finite group with prime order p and a random generator g. Let H:{0,1}∗→Zp be a collision-resistant hash function. The system parameter is sp=(G,p,g,H). The signature scheme is described as follows.(i)
OTS.Gen(sp): it picks three random exponents sigk=(s0,s1,x)←$Zp3 as the signing key and sets vk=(u0,u1,c)=(gs0,gs1,gx).(ii)
OTS.Sign(sigk,m): for any message m, it chooses a random exponent e←$Zp and computes w=x+e·s0+(H(m)+e)·s1(modp). The signature is σ=(e,w)∈Zp×Zp.(iii)
OTS.Vrf(vk,m,σ): given a message m and a signature (e,w), if gw=c·u0e·u1H(m)+e, then it outputs 1; else it outputs 0.Proof.
Given a challenge discrete logarithm problemh∗=gx∗, our goal is to construct an algorithm B that breaks the discrete-log problem by taking the adversary algorithm A as a subroutine.
Let us denote by(vk1,sigk2),…,(vkn,sigkn) the n key pairs and let (ei,wi) be the signature queried by A on message mi under signing key sigki. Suppose that A finally outputs a valid (forged) signature (e,w) on message m under the verification key vki. By the collision-resistance of hash function H, it is clear that (e,w)≠(ei,wi). Otherwise, m=mi. We first assume that e≠ei. Now, B simulates the game as follows. For each i∈[n], it randomly chooses ei,αi,βi,γi∈Zp and implicitly sets sigki=(s0(i),s1(i),x(i))=(αi-x∗/ei,βi,x∗+γi). It then computes u0(i)=gαi·(h∗)-1/ei, u1(i)=gβi, and c(i)=h∗·gγi and sets vki=(u0(i),u1(i),c(i)). By the randomness of αi, βi, and γi, the verification key vki has the same distribution as the real verification key.
For each signing query on messagemi, B computes wi=γi+ei·αi+(H(mi)+ei)·βi(modp) and sets σi=(ei,wi). B returns the signature σi to A. This signature has the same distribution as the real signature. Finally, A generates a forged signature (m,(e,w)) under the verification key vki. The forged signature satisfies gw=c(i)·(u0(i))e·(u1(i))H(m)+e. Hence (4)gwi-w=u0iei-e·u1iHmi+ei-Hm+e=gαi·h∗-1/eiei-e·gβi·Hmi-Hm+βi·ei-e.So, we have(5)x∗=αi+βi·ei+w-wi+βi·Hmi-Hm·eiei-emodp.
Ife=ei, we must have w≠wi. Similarly, we can construct another algorithm B′ to solve the discrete logarithm problem for the case w≠wi. For any case, the two algorithms B and B′ are independent of the adversary’s point of view. So, we can randomly guess which algorithm we will use to break the discrete logarithm problem using A as the subroutine.
LetF be the even that A forges a valid signature and let E be the even that the collision of H occurs. Denote by ϵdl the probability that B solves the discrete logarithm problem as stated in Definition 1. Denote by ϵcr the probability for any PPT adversary to find a collision of H; that is, ϵcr=Pr⁡[E]=Pr⁡[(x1,x2)←A(H):x1≠x2∧H(x1)=H(x2)]. By the aforementioned analysis, if the event E does not occur, then B solves the discrete-log problem with probability at least 1/2Pr⁡[F∣E¯]. So,(6)Pr⁡F≤PrF∣E¯+Pr⁡E≤2·ϵdl+ϵcr.This shows that the above one-time signature is tightly secure in the multiuser setting.


## 2.1. Notations

IfS is a finite set then |S| denotes its size and s←$S denotes the operation of picking an element s uniformly at random from S. For any n∈N, we denote by [n] the set {1,…,n}. By 1λ, we denote the security parameter. We use PPT for the abbreviation of “ probabilistic polynomial-time”. We denote by z←A(x,y…) the operation of running an algorithm A with inputs (x,y…) and letting z be the output.


## 2.2. Complexity Assumptions

In the following, letG(1λ) be a PPT algorithm that takes as input a security parameter 1λ and outputs a description of group (G,p,g), where G is a group of prime order p and g is a random generator of G. For an arbitrary g1∈G, let logg(g1) denote the discrete logarithm g1 to base g such that g1=glogg(g1). Furthermore, for any generator g∈G, let DDH(G,p)(g) denote the set(1)DDHG,pg=ga,gb,gab:a,b∈Zp.Definition 1 (discrete logarithm assumption).
Letg∈G be a random generator of G and h∈G be a random group element. The discrete logarithm (DL) assumption states that the following advantage:(2)AdvA,Gdlλ≔Pr⁡a←Ag,h:ga=his negligible in λ for every PPT algorithm A.Definition 2 (decisional Diffie-Hellman assumption).
Letg∈G be a random generator of G and U←$DDH(G,p)(g), V←$G3. The decisional Diffie-Hellman (DDH) assumption in group G states that the advantage(3)AdvA,Gddhλ≔Pr⁡Ag,U=1-Pr⁡Ag,V=1is negligible in λ for every PPT algorithm A.Random Self-Reducibility of DDH [15, Lemma 5.1]. The tight security reduction of our LTFs and ABO-LTFs mainly benefit from the self-reducibility property of the DDH problem. Namely, there exists a PPT algorithm Rddh that takes as input the group order p, generator g, (ga,gb,gc)∈G3, and a bit x∈{0,1} and outputs (ga′,gb′,gc′)∈G3 such that we have the following. See Table 1.Table 1 x = 0 x = 1 a ′ = a a ′ is random c = a b  m o d  p b ′ is random b ′ is random c ′ = a ′ b ′ m o d  p c ′ = a ′ b ′  m o d  p  a ′ = a a ′ is random c ≠ a b  m o d  p b ′ is random b ′ is random c ′ is random c ′ is randomPairwise Independent Hash Functions. A family of hash functions H={h:D→R} from domain D to range R is called pairwise independent if, for every distinct x,x′∈D and every y,y′∈R, Pr⁡[h(x)=yandh(x′)=y′]=1/R2.Randomness Extractor [23, Lemma 2.4]. Let X,Y be two random variables such that X∈{0,1}n and H∞X∣Y≤l. Let H be a family of pairwise independent hash functions from {0,1}n to {0,1}k.Ifk≤l-2log⁡(1/ϵ), then H is an average-case strong extractor; i.e., the distribution (Y,h,h(X)) is statistically ϵ-close to the distribution (Y,h,r), where h←$H and r←${0,1}k.Strongly Unforgeable One-Time Signature. A one-time signature schemeOTS consists of three algorithms (OTS.Gen,OTS.Sign, andOTS.Vrf), where (1)OTS.Gen on input a security parameter 1λ outputs a verification key vk and a signing key sigk; (2)OTS.Sign on input a signing key sigk and a message m outputs a signature σ; (3)OTS.Vrf on input a verification key vk, a message m, and a signature outputs either 0 or 1. The correctness guarantees thatOTS.Vrf(vk,m,σ)=1 holds with probability 1, if and only if σ =OTS.Sign(sigk,m). Next, we define the security notion of strong existential unforgeability under a one-time chosen message attack in multiuser setting. It is defined through a game played between a challenger and a PPT adversary A. The challenger first generates independently n pairs of keys (vki,sigki) and gives all vki to the adversary. For each signing key sigki, the adversary can obtain at most one signature σi=OTS.Sign(sigki,mi) on a single message mi chosen by the adversary. Finally, the adversary outputs a pair (m,σ) and is said to succeed if there exists i∈[n] such that OTS.Vrf(vki,m,σ)=1 and (m,σ)≠(mi,σi). We denote by AdvOTS,Asu-cma(λ,n) the adversary’s success probability (advantage). A one-time signature scheme is strongly unforgeable if the adversary has negligible advantage. If the advantage is independent of the number of users, the signature scheme is said to be tightness.By the random self-reducibility of the discrete logarithm problem, we can show the following one-time signature scheme proposed in [14, Fig.4] is tightly secure in multiuser setting, if the schemes share the same group parameters. Let (G,p,g) be a finite group with prime order p and a random generator g. Let H:{0,1}∗→Zp be a collision-resistant hash function. The system parameter is sp=(G,p,g,H). The signature scheme is described as follows.(i)
OTS.Gen(sp): it picks three random exponents sigk=(s0,s1,x)←$Zp3 as the signing key and sets vk=(u0,u1,c)=(gs0,gs1,gx).(ii)
OTS.Sign(sigk,m): for any message m, it chooses a random exponent e←$Zp and computes w=x+e·s0+(H(m)+e)·s1(modp). The signature is σ=(e,w)∈Zp×Zp.(iii)
OTS.Vrf(vk,m,σ): given a message m and a signature (e,w), if gw=c·u0e·u1H(m)+e, then it outputs 1; else it outputs 0.Proof.
Given a challenge discrete logarithm problemh∗=gx∗, our goal is to construct an algorithm B that breaks the discrete-log problem by taking the adversary algorithm A as a subroutine.
Let us denote by(vk1,sigk2),…,(vkn,sigkn) the n key pairs and let (ei,wi) be the signature queried by A on message mi under signing key sigki. Suppose that A finally outputs a valid (forged) signature (e,w) on message m under the verification key vki. By the collision-resistance of hash function H, it is clear that (e,w)≠(ei,wi). Otherwise, m=mi. We first assume that e≠ei. Now, B simulates the game as follows. For each i∈[n], it randomly chooses ei,αi,βi,γi∈Zp and implicitly sets sigki=(s0(i),s1(i),x(i))=(αi-x∗/ei,βi,x∗+γi). It then computes u0(i)=gαi·(h∗)-1/ei, u1(i)=gβi, and c(i)=h∗·gγi and sets vki=(u0(i),u1(i),c(i)). By the randomness of αi, βi, and γi, the verification key vki has the same distribution as the real verification key.
For each signing query on messagemi, B computes wi=γi+ei·αi+(H(mi)+ei)·βi(modp) and sets σi=(ei,wi). B returns the signature σi to A. This signature has the same distribution as the real signature. Finally, A generates a forged signature (m,(e,w)) under the verification key vki. The forged signature satisfies gw=c(i)·(u0(i))e·(u1(i))H(m)+e. Hence (4)gwi-w=u0iei-e·u1iHmi+ei-Hm+e=gαi·h∗-1/eiei-e·gβi·Hmi-Hm+βi·ei-e.So, we have(5)x∗=αi+βi·ei+w-wi+βi·Hmi-Hm·eiei-emodp.
Ife=ei, we must have w≠wi. Similarly, we can construct another algorithm B′ to solve the discrete logarithm problem for the case w≠wi. For any case, the two algorithms B and B′ are independent of the adversary’s point of view. So, we can randomly guess which algorithm we will use to break the discrete logarithm problem using A as the subroutine.
LetF be the even that A forges a valid signature and let E be the even that the collision of H occurs. Denote by ϵdl the probability that B solves the discrete logarithm problem as stated in Definition 1. Denote by ϵcr the probability for any PPT adversary to find a collision of H; that is, ϵcr=Pr⁡[E]=Pr⁡[(x1,x2)←A(H):x1≠x2∧H(x1)=H(x2)]. By the aforementioned analysis, if the event E does not occur, then B solves the discrete-log problem with probability at least 1/2Pr⁡[F∣E¯]. So,(6)Pr⁡F≤PrF∣E¯+Pr⁡E≤2·ϵdl+ϵcr.This shows that the above one-time signature is tightly secure in the multiuser setting.


## 3. Definitions for Tightly Secure LTFs and ABO-LTFs

In the following, unless described otherwise, all quantities are implicitly functions of a security parameterλ∈N. We first recall the standard notions of lossy trapdoor functions and all-but-one lossy trapdoor functions from [1] and then introduce their tight security.


### 3.1. Tightly Secure LTFs

Definition 3 (lossy trapdoor functions).
A collection of(n,l)-lossy trapdoor functions LTF consists of the following (PPT) algorithms: (i)
spltf←LTF.Sys(1λ): this is the system parameter generation algorithm. It takes as input a security parameter λ and outputs the system parameters spltf.(ii)
(ekltf,ikltf)←LTF.IGen(spltf): this is the key generation algorithm. It takes as input the system parameter spltf and outputs an (injective) evaluation key ekltf and an inversion key ikltf.(iii)
(ekltf,⊥)←LTF.LGen(spltf): this is the lossy key generation algorithm. It takes as input the system parameter spltf and outputs an (lossy) evaluation key ekltf and the special symbol ⊥ (indicating that this evaluation key does not have corresponding inversion key).(iv)
y←LTF.Eval(ekltf,x): this is the function evaluation algorithm. It takes as input an evaluation key ekltf and a preimage x∈{0,1}n and outputs an image y.(v)
x←LTF.Inv(ikltf,y): this is the inversion algorithm. It takes as input an inversion key ikltf and an image y and outputs a preimage x∈{0,1}n.
We require thatLTF has the following properties.
Correctness. For all possible spltf←LTF.Sys(1λ), all (ekltf,ikltf)←LTF.IGen(spltf), and all x∈{0,1}n, we have LTF.Inv(ikltf,LTF.Eval(ekltf,x))=x.
Lossiness. For all possible spltf←LTF.Sys(1λ) and all ekltf←LTF.LGen(spltf), we say that LTF is l-lossy, if the image set LTF.Eval(ekltf,Dom) is of size at most 2n-l.
Indistinguishability. For all possible spltf←LTF.Sys(1λ) and for any PPT adversary A, we require that A can not distinguish an injective key from a lossy key with nonnegligible advantage. Namely, the function(7)AdvLTF,Aindλ≔Pr⁡A1λ,spltf,ek0=1-Pr⁡A1λ,spltf,ek1=1is negligible in λ, where (ek0,ik0)←LTF.IGen(spltf) and (ek1,⊥)←LTF.LGen(spltf).Definition 4 (tightly secure LTFs).
We say that a collection of LTFs is tightly secure if, for any PPT adversaryA, the following indistinguishability advantage is negligible and independent of nu, the number of injective or lossy keys.(8)AdvLTF,Anu-indλ≔Pr⁡A1λ,spltfO0·=1-Pr⁡A1λ,spltfO1·=1The above two oracles O0(·) and O1(·) are defined as follows: taking an integer i∈[nu] as input, O0 firstly runs (ekltf,ikltf)←LTF.IGen(spltf) to obtain the i-th injective key eki≔ekltf and returns it to the adversary; O1 firstly runs (ekltf,⊥)←LTF.LGen(spltf) to obtain the i-th lossy key eki≔ekltf and returns it to the adversary. Clearly, the standard indistinguishability is just the case that nu=1.


### 3.2. Tightly Secure ABO-LTFs

In an ABO-LTF collection, each function has an extra input called branch. In the following, we denote byBλ the set of branches.Definition 5 (all-but-one LTFs).
A collection of(n,l)-all-but-one lossy trapdoor functions ABO with branch set Bλ consists of the following (PPT) algorithms: (i)
spabo←ABO.Sys(1λ): this is the system parameter generation algorithm. It takes as input a security parameter λ and outputs the system parameters spabo.(ii)
(ekabo,ikabo)←ABO.Gen(spabo,t∗): this is the key generation algorithm. It takes as input the system parameter spabo and a branch t∗∈Bλ and outputs an evaluation key ekabo and an inversion key ikabo.(iii)
y←ABO.Eval(ekabo,t,x): this is the function evaluation algorithm. It takes as input the evaluation key ekabo, a branch t∈Bλ, and a preimage x∈{0,1}n and outputs an image y.(iv)
x←ABO.Inv(ikabo,t,y): this is the inversion algorithm. It takes as input the inversion key ikabo, a branch b∈Bλ, and an image y and outputs a preimage x∈{0,1}n.
We require thatABO has the following properties.
Correctness. For all spabo←ABO.Sys(1λ), all t∗∈Bλ, and all possible (ekabo,ikabo)←ABO.Gen(spabo,t∗), if t≠t∗, then ABO.Inv(ikabo,t,ABO.Eval(ekabo,t,x))=x holds for all x∈{0,1}n.
Lossiness. If the above t=t∗, then ABO.Eval(ekabo,t∗,·) is of size at most 2r=2n-l. t∗ is usually called lossy branch.
Hidden Lossy Branch. For any PPT adversary A that gives the system parameter spabo←ABO.Sys(1λ) and outputs two branches t0∗,t1∗∈Bλ, the advantage(9)AdvABO,Aindλ≔Pr⁡A1λ,spabo,ek0=1-Pr⁡A1λ,spabo,ek1=1is negligible in λ, where (ek0,ik0)←ABO.Gen(spabo,b0∗) and (ek1,ik1)←ABO.Gen(spabo,b1∗).Definition 6 (tightly secure ABO-LTFs).
We say that a collection of ABO-LTFs is tightly secure if for any PPT adversaryA; the following indistinguishability advantage is negligible and independent of nu, the number of evaluation keys:(10)AdvABO,Aindλ,nu≔Pr⁡A1λ,spaboO0·=1-Pr⁡A1λ,spaboO1·=1.The above oracle Ob(·) (b=0 or b=1) is defined as follows: for i∈[nu], the adversary outputs the i-th pair of branches (t0i,t1i) and is given an evaluation key ekbi, where (ekbi,ikbi)←ABO.Gen(spabo,tbi). Clearly, the hidden lossy branch property of ABO-LTFs is just the case that nu=1.


## 3.1. Tightly Secure LTFs

Definition 3 (lossy trapdoor functions).
A collection of(n,l)-lossy trapdoor functions LTF consists of the following (PPT) algorithms: (i)
spltf←LTF.Sys(1λ): this is the system parameter generation algorithm. It takes as input a security parameter λ and outputs the system parameters spltf.(ii)
(ekltf,ikltf)←LTF.IGen(spltf): this is the key generation algorithm. It takes as input the system parameter spltf and outputs an (injective) evaluation key ekltf and an inversion key ikltf.(iii)
(ekltf,⊥)←LTF.LGen(spltf): this is the lossy key generation algorithm. It takes as input the system parameter spltf and outputs an (lossy) evaluation key ekltf and the special symbol ⊥ (indicating that this evaluation key does not have corresponding inversion key).(iv)
y←LTF.Eval(ekltf,x): this is the function evaluation algorithm. It takes as input an evaluation key ekltf and a preimage x∈{0,1}n and outputs an image y.(v)
x←LTF.Inv(ikltf,y): this is the inversion algorithm. It takes as input an inversion key ikltf and an image y and outputs a preimage x∈{0,1}n.
We require thatLTF has the following properties.
Correctness. For all possible spltf←LTF.Sys(1λ), all (ekltf,ikltf)←LTF.IGen(spltf), and all x∈{0,1}n, we have LTF.Inv(ikltf,LTF.Eval(ekltf,x))=x.
Lossiness. For all possible spltf←LTF.Sys(1λ) and all ekltf←LTF.LGen(spltf), we say that LTF is l-lossy, if the image set LTF.Eval(ekltf,Dom) is of size at most 2n-l.
Indistinguishability. For all possible spltf←LTF.Sys(1λ) and for any PPT adversary A, we require that A can not distinguish an injective key from a lossy key with nonnegligible advantage. Namely, the function(7)AdvLTF,Aindλ≔Pr⁡A1λ,spltf,ek0=1-Pr⁡A1λ,spltf,ek1=1is negligible in λ, where (ek0,ik0)←LTF.IGen(spltf) and (ek1,⊥)←LTF.LGen(spltf).Definition 4 (tightly secure LTFs).
We say that a collection of LTFs is tightly secure if, for any PPT adversaryA, the following indistinguishability advantage is negligible and independent of nu, the number of injective or lossy keys.(8)AdvLTF,Anu-indλ≔Pr⁡A1λ,spltfO0·=1-Pr⁡A1λ,spltfO1·=1The above two oracles O0(·) and O1(·) are defined as follows: taking an integer i∈[nu] as input, O0 firstly runs (ekltf,ikltf)←LTF.IGen(spltf) to obtain the i-th injective key eki≔ekltf and returns it to the adversary; O1 firstly runs (ekltf,⊥)←LTF.LGen(spltf) to obtain the i-th lossy key eki≔ekltf and returns it to the adversary. Clearly, the standard indistinguishability is just the case that nu=1.


## 3.2. Tightly Secure ABO-LTFs

In an ABO-LTF collection, each function has an extra input called branch. In the following, we denote byBλ the set of branches.Definition 5 (all-but-one LTFs).
A collection of(n,l)-all-but-one lossy trapdoor functions ABO with branch set Bλ consists of the following (PPT) algorithms: (i)
spabo←ABO.Sys(1λ): this is the system parameter generation algorithm. It takes as input a security parameter λ and outputs the system parameters spabo.(ii)
(ekabo,ikabo)←ABO.Gen(spabo,t∗): this is the key generation algorithm. It takes as input the system parameter spabo and a branch t∗∈Bλ and outputs an evaluation key ekabo and an inversion key ikabo.(iii)
y←ABO.Eval(ekabo,t,x): this is the function evaluation algorithm. It takes as input the evaluation key ekabo, a branch t∈Bλ, and a preimage x∈{0,1}n and outputs an image y.(iv)
x←ABO.Inv(ikabo,t,y): this is the inversion algorithm. It takes as input the inversion key ikabo, a branch b∈Bλ, and an image y and outputs a preimage x∈{0,1}n.
We require thatABO has the following properties.
Correctness. For all spabo←ABO.Sys(1λ), all t∗∈Bλ, and all possible (ekabo,ikabo)←ABO.Gen(spabo,t∗), if t≠t∗, then ABO.Inv(ikabo,t,ABO.Eval(ekabo,t,x))=x holds for all x∈{0,1}n.
Lossiness. If the above t=t∗, then ABO.Eval(ekabo,t∗,·) is of size at most 2r=2n-l. t∗ is usually called lossy branch.
Hidden Lossy Branch. For any PPT adversary A that gives the system parameter spabo←ABO.Sys(1λ) and outputs two branches t0∗,t1∗∈Bλ, the advantage(9)AdvABO,Aindλ≔Pr⁡A1λ,spabo,ek0=1-Pr⁡A1λ,spabo,ek1=1is negligible in λ, where (ek0,ik0)←ABO.Gen(spabo,b0∗) and (ek1,ik1)←ABO.Gen(spabo,b1∗).Definition 6 (tightly secure ABO-LTFs).
We say that a collection of ABO-LTFs is tightly secure if for any PPT adversaryA; the following indistinguishability advantage is negligible and independent of nu, the number of evaluation keys:(10)AdvABO,Aindλ,nu≔Pr⁡A1λ,spaboO0·=1-Pr⁡A1λ,spaboO1·=1.The above oracle Ob(·) (b=0 or b=1) is defined as follows: for i∈[nu], the adversary outputs the i-th pair of branches (t0i,t1i) and is given an evaluation key ekbi, where (ekbi,ikbi)←ABO.Gen(spabo,tbi). Clearly, the hidden lossy branch property of ABO-LTFs is just the case that nu=1.


## 4. Constructions of Tightly Secure PKE Schemes

### 4.1. Definitions for PKE

Definition 7 (public-key encryption).
A public-key encryption schemePKE with message space M consists of the following PPT algorithms.
s p p k e ← P K E . S y s ( 1 λ ). This is the system parameter generation algorithm. It takes as input a security parameter 1λ and outputs system parameters sppke.
( p k p k e , s k p k e ) ← P K E . G e n ( s p p k e ). This is the key generation algorithm. It takes as input the system parameters sppke and outputs a public key pkpke and a secret key skpke.
c ← P K E . E n c ( p k p k e , m ). This is the message encryption algorithm. It takes as input a public key pkpke and a message m∈M and outputs a ciphertext c.
m/⊥  ←PKE.Dec(skpke,c). This is the decryption algorithm. It takes as input the secret key skpke and a ciphertext c and outputs a message m or a special symbol ⊥ (indicating that c is an invalid ciphertext).
For correctness, we require that, for allsppke←PKE.Sys(1λ), all (pkpke,skpke)←PKE.Gen(sppke), and all m∈M, it always has PKE.Dec(skpke,PKE.Enc(pkpke,m))=m.Security. We recall the security definition of indistinguishability against adaptive chosen-ciphertext attacks (CCA) in multiuser and multichallenge settings from [15, 16]. The following experiment is played between the challenger and an adversary A and is parameterized by integers nu,qe,qd∈N (i.e., the number of users, challenge ciphertexts/encryption queries, and decryption queries).Experiment E x p P K E , A i n d - c c a ( λ , n u , q e , q d ) (1)
Initialization phase: the challenger runs PKE.Sys(1λ) only once to generate the system parameter sppke and runs PKE.Gen(sppke)  nu times to generate nu key pairs (pkpke(i),skpke(i)), i∈[nu]. Then, it tosses a random coin b←$0,1, initializes a list CL≔∅ to an empty list, and defines counters ji≔0 and ji~≔0 for each i∈[nu]. (2)
Query phase: A receives pkpke(1),…,pkpke(nu) as input and may adaptively query the challenger for two types of operations.
(I)
Encryption queries: the adversary submits two messages m0,m1∈M of equal length and an index i∈[nu]. If ji≥qe then the challenger returns ⊥. Otherwise, it returns c=PKE.Enc(pkpke(i),mb), appends (i,c) to CL, and sets ji≔ji+1. (II)
Decryption queries: the adversary submits a ciphertext c and an index i∈[nu]. If (i,c)∈CL or ji~≥qd then the challenger returns ⊥. Otherwise it returns PKE.Dec(skpke(i),c) and sets ji~≔ji~+1. (3)
Guess phase:eventually, the adversary outputs a bit b′ as a guess of b.The advantage ofA in the above experiment is defined as (11)AdvPKE,Aind-ccaλ,nu,qe,qd=Pr⁡b=b′-12.Definition 8 (IND-CCA security).
We say thatA  (tpke,ϵpke) breaks the (nu,qe,qd)-IND-CCA security if A runs in times tpke and AdvPKE,Aind-cca(λ,nu,qe,qd)≥ϵpke(λ). A public-key encryption scheme PKE is (tpke,ϵpke,nu,qe,qd)-IND-CCA-secure if there exists no adversary that (tpke,ϵpke)-breaks the (nu,qe,qd)-IND-CCA security.Definition 9 (IND-CPA security).
In the above experiment, ifqd=0, then we say PKE is (tpke,ϵpke,nu,qe)-IND-CPA-secure.Clearly, if there is only one-user and one-challenger ciphertext, i.e.,nu=1,qe=1, the (1,1,qd)-IND-CCA security in the above sense is exactly the classical definition of IND-CCA security [24], and (1,1)-IND-CPA security is exactly the classical definition of IND-CPA security (or semantic security) [25]. The generic reduction from [15] showed that if A  (tpke,ϵpke)-breaks the (nu,qe,qd)-IND-CCA security, there exists A′  (tpke′,ϵpke′) that breaks the (1,1,qd)-IND-CCA security and tpke′≈tpke, ϵpke′≥ϵpke/(nu·qe). Thus, the security reduction loses (at most) a factor of L=nu·qe. A security reduction is calledtight if the corresponding reduction loss L is constant.


### 4.2. CPA-Secure PKE Scheme

In this section, we propose a generic construction of PKE scheme from LTFs and show its IND-CPA security in the setting that has polynomial number of users and challenge ciphertexts. Our security proof shows that if the underlying LTFs are tightly secure, then so is the PKE scheme.The CPA-secure PKE scheme with message space{0,1}k is given in Box 1. It applies the following components:(i)
A collection of(n,lltf)-lossy trapdoor functions: LTF=(LTF.Sys,LTF.IGen,LTF.LGen,LTF.Eval,LTF.Inv)(ii)
A family of pairwise independent hash functions:H:{0,1}n→{0,1}kBox 1:The CPA-secure PKE scheme.
P K E . S y s ( 1 λ ) : It runs spltf←LTF.Sys(1λ) and returns sppke=spltf. P K E . G e n ( s p p k e ) : It runs (ekltf,ikltf)←LTF.IGen(spltf), and returns pk=ekltf and sk=ikltf. P K E . E n c ( p k , m ): It first chooses x←${0,1}n and h←$H. It then computes y = L T F . E v a l ( e k l t f , x ) ,   π = h ( x ) ⊕ m . Finally, it returns c=(y,h,π). P K E . D e c ( s k ,  c ): First, it parses c as (y,h,π). Then, it computes x=LTF.Inv(ikltf,y). Next, it checks L T F . E v a l ( e k l t f , x ) = y . If not, it returns ⊥. Otherwise, it returns m=hx⊕π.Letϵ≔ϵ(λ)≤2-3λ be a negligible function in λ. We require that the parameters in the above primitives satisfy the condition k≤lltf-2log⁡(1/ϵ).Theorem 10.
Letλ be the security parameter, and let nu,qe≤2λ be integers. Then, the PKE scheme described in Box 1 is (tpke,ϵpke,nu,qe)-IND-CPA-secure, where(12)ϵpke≤AdvLTF,Dindλ,nu+2-λand the runtime of D is roughly the runtime of the IND-CPA experiment with an adversary of runtime tpke. Clearly, if the underlying LTFs are tightly secure, then the obtained PKE is tightly CPA-secure.Outline of Proof. The proof is very simple. First, by the indistinguishability of LTF, we replace all users’ LTF injective evaluation keys with lossy evaluation keys. Now, in the challenge ciphertexts, each function works in lossy mode and thus reveals at most (n-lltf)-bit information of x. Applying h to x, it can extract a random string, which will hide the information of the encrypted message.Proof.
We proceed in a sequence of games. LetA be a fixed adversary that breaks the IND-CPA security of the above PKE scheme in the multiuser setting. Assume that it makes at most qe encryption queries to each user’s encryption oracles. Let wini denote the event that A wins inGamei.
Game 1. This is the original IND-CPA experiment. Roughly speaking, the challenger runs sppke←PKE.Sys(1λ) only once. Then, it runs PKE.Gen(sppke)  nu times to generate nu public/secret key pairs (pk1,sk1),…,(pknu,sknu) and tosses a random coin b∈{0,1}. The adversary A takes these nu public keys as input and may make at most qe queries to each encryption oracle PKE.Enc(pki,·). Every encryption query is of the form (i,m0,m1), where i∈[nu] and m0 and m1 are two equal length messages. The challenger responds with c∗=PKE.Enc(pki,mb). Finally, the adversary outputs a bit b′ as the guess of b. We say that A wins the game if b′=b. So,(13)AdvPKE,Aind-cpaλ,nu,qe=Pr⁡win1-12.
Game 2. This game is identical toGame 1 except that we replace all users’ LTF injective keys with lossy keys. By the indistinguishability property of the LTF collection, it follows that(14)Pr⁡win2-Pr⁡win1≤AdvLTF,Dindλ,nufor some adversary D attacking LTF’s indistinguishability.
The proof is as follows. Given the system parameterspltf of LTF, the simulator sets sppke=spltf and asks the LTF challenger to generation nu LTF keys ekltf(i). The simulator sets pki=ekltf(i) and returns it to the adversary. Once the adversary asks an encryption query (i,m0,m1), the simulator tosses a random coin in advance and computes the challenge ciphertext as inGame 1. Clearly, if all ekltf(i) are generated by the injective key generation algorithm LTF.IGen(spltf), the view of the adversary is exactlyGame 1; otherwise, it is exactlyGame 2. This completes the proof.
Game 3. This game is identical toGame 2, except that we replace h(x) in each challenge ciphertext with a uniformly distributed string r∈{0,1}k. We show that(15)Pr⁡win3-Pr⁡win2≤nuqe·ϵ.The proof is as follows. First, observe that, inGame 2, all y∗=LTF.Eval(ekltf(i),x) in challenge ciphertexts are lossy functions. So the image size of y∗ is at most n-lltf. Since k≤lltf-2log⁡(1/ϵ), by the property of H, it follows that (y∗,h∗,h∗(x)) is statistically ϵ-close to (y∗,h∗,r), where h∗←H and r is uniformly distributed over {0,1}k. Recall that there are at most nuqe challenge ciphertexts. The proof completes. Since ϵ≤2-3λ and nu,qe≤2λ, we further have that(16)Pr⁡win3-Pr⁡win2≤2-λ.Recall that, inGame 3, each challenge message mb is perfectly hidden by the random string r; i.e., π∗=r⊕mb; it follows that(17)Pr⁡win3=12.Taking all together, we get Theorem 10.


### 4.3. CCA-Secure PKE Scheme

Next, we propose a generic construction of PKE scheme from LTFs and ABO-LTFs and show its CCA security in the setting that has polynomial number of users and one-challenge ciphertext. Our security proof shows that if the underlying LTFs and ABO-LTFs are tightly secure, then so is the PKE scheme.The CCA-secure PKE scheme with message space{0,1}k is given in Box 2. It applies the following components:(i)
A collection of(n,lltf)-lossy trapdoor functions: LTF=(LTF.Sys,LTF.IGen,LTF.LGen,LTF.Eval,LTF.Inv)(ii)
A collection of(n,labo)-all-but-one lossy trapdoor functions: ABO=(ABO.Sys,ABO.Gen,ABO.Eval,ABO.Inv) with branch set Bλ={0,1}v(iii)
A family of pairwise independent hash functions:H:{0,1}n→{0,1}k(iv)
A strongly unforgeable one-time signatures scheme:OTS=(OTS.Gen,OTS.Sign,OTS.Vrf).Box 2:The CCA-secure PKE scheme.
P K E . S y s ( 1 λ ) : It runs spltf←LTF.Sys(1λ), spabo←ABO.Sys(1λ) and spots←OTS.Gen(1λ), and then returns sppke=(spltf,spabo). P K E . G e n ( s p p k e ) : It runs (ekltf,ikltf)←LTF.IGen(spltf) and (ekabo,ikabo)←ABO.Gen(spabo,0v) with branch 0v, returns pk=(ekltf,ekabo) and sk=ikltf. P K E . E n c ( p k p k e , m ): It first runs OTS.Gen(1λ) to obtain a one-time signature key pair (vk,sigk). It then chooses x ← $ { 0,1 } n and h←$H, and computes y 1 = L T F . E v a l ( e k l t f , x ) ,   π = h ( x ) ⊕ m , y 2 = A B O . E v a l ( e k a b o , v k , x ) ,   σ = O T S . S i g n ( s i g k , y 1 | | h | | π | | y 2 ) Finally, it returns c=(y1,h,π,y2,σ,vk). P K E . D e c ( s k p k e , c ): It first checks that OTS.Vrf(vk,y1||h||π||y2,σ)=1. If not, it outputs ⊥. It then computes x = L T F . I n v ( i k l t f , y 1 ) and checks LTF.Eval(ekltf,x)=y1 and ABO.Eval(ekabo,vk,x)=y2; if not, it outputs ⊥. Finally, it outputs m=h(x)⊕π.Letϵ≔ϵ(λ)≤2-2λ be a negligible function in λ. We require that (1) the parameters in the above primitives satisfy the condition k≤(lltf+labo-n)-2log⁡(1/ϵ); (2) the branch set Bλ contains the set of signature verification keys.Theorem 11.
Letλ be the security parameter and let nu, qe, qd be integers such that nu≤2λ, qe=1. Then, the PKE scheme described in Box 2 is (tpke,ϵpke,nu,qe=1,qd)-IND-CCA-secure, where(18)ϵpke≤AdvOTS,D1su-cmaλ,nu+AdvABO,D2indλ,nu+AdvLTF,D3indλ,nu+2-λand the runtime of D1, D2, D3 is roughly the runtime of the IND-CCA experiment with an adversary of runtime tpke.Outline of Proof. The proof idea mainly follows [1]. First, by the all-but-one property, we replace each ABO lossy branch with the corresponding verification key of the challenge ciphertext. Since the underlying OTS is strongly unforgeable, all branches in decryption queries would be distinct with the corresponding lossy branch. Thus, all ABO functions in the decryption queries are injective. By this observation, we can replace the decryption key with the ABO inversion key. Next, by the indistinguishability of LTFs, we replace all users’ LTF injective keys with lossy keys. Now, in the challenge ciphertexts, each function works in lossy mode and reveals at most (n-lltf)+(n-labo) bits information of x. So, the application of h guarantees that the ciphertexts of m0 and m1 are indistinguishable.Proof.
We proceed in a sequence of games. LetA be a fixed adversary that breaks the IND-CCA security of the PKE scheme in the multiuser setting. Assume that it makes at mostone encryption query (resp., qd decryption query) to each user’s encryption oracle (resp., decryption oracle). Let wini denote the probability that A wins inGamei.
Game 1. This is the original IND-CCA experiment. Roughly speaking, the challenger first runs sppke←PKE.Sys(1λ) only once. It then runs PKE.Gen(sppke)nu times to generate nu public/secret key pairs (pk1∗,sk1∗),…,(pknu∗,sknu∗) and tosses a random coin b∈{0,1}. The adversary A receives these nu public keys as input and may makeone query to each encryption oracle PKE.Enc(pki∗,·) and qd queries to each decryption oracle PKE.Dec(ski∗,·). Each encryption query is of the form (i,m0,m1) where i∈[nu], and m0 and m1 are two equal length messages, and the challenger responds with ci∗=PKE.Enc(pki∗,mb). Each decryption query is of the form (i,c), where i∈[nu]. The challenger will respond with PKE.Dec(ski∗,c). Finally, the adversary outputs a bit b′ as the guess of b. We say that A wins the game if b′=b. Clearly, the adversary is not allowed to ask for the decryption of the challenge ciphertext; i.e., (i,c)=(i,ci∗). According to the definition of IND-CCA experiment, we have that(19)AdvPKE,Aind-ccaλ,nu,qe,qd=Pr⁡win1-12.Hereafter, we use (i,c=(y1,h,π,y2,σ,vk)) to denote a decryption query, in which the ciphertext c is encrypted under public key pki∗, and denote by (i,ci∗=(y1∗,h∗,π∗,y2∗,σ∗,vk∗)) the challenge ciphertext under user i’s public key.
Game 2. This game is identical toGame 1 except that it rejects all decryption queries (i,c) in which the verification key vk is the same as that of the corresponding challenge ciphertext (i,ci∗) for any i∈[nu]. Recall that A is forbidden to ask for decryption query such that (i,c)=(i,ci∗). So, c≠ci∗. Suppose that there exists some decryption query (i,c), in which vk=vk∗. It must have that (y1,h,π,y2,σ)≠(y1∗,h∗,π∗,y2∗,σ∗). By the strong unforgeability of the underlying one-time signature, we have the following result:(20)Pr⁡win2-Pr⁡win1≤AdvOTS,D1su-cmaλ,nufor some adversary D1 attacking the strong unforgeability of the underlying OTS in the multiuser setting.
The proof is as follows. The simulator asks the OTS challenger to generate the system parameterspots and nu one-time key pairs (vki∗,sigki∗). The simulator will receive the OTS system parameter spots and nu verification keys vki∗. The simulator then generates the other system parameters of the PKE scheme, including (spltf,spabo), and generates nu PKE key pairs (pki∗,ski∗) as inGame 1. The simulator sends the PKE system parameter sppke=(spltf,spabo,spots) and nu PKE public keys pki∗ to the adversary. As the simulator knows all users’ decryption keys, it can answer the adversary’s decryption queries as inGame 1. To answer encryption queries, the simulator tosses a random coin b∈{0,1} in advance. Given (i,m0,m1), the simulator randomly chooses x←{0,1}n and h∗←H and computes y1∗=LTF.Eval(ekltf,x), π∗=h∗(x)⊕mb, and y2∗=OTS.Eval(ekabo,vki∗,x). The simulator sends the message y1∗∥h∗∥π∗∥y2∗ to the OTS challenger to obtain a signature σ∗ which is signed under the corresponding signing key sigki∗. The simulator sends the challenge ciphertext c∗=(y1∗,h∗,π∗,y2∗,σ∗,vk∗=vki∗) to the adversary. Clearly, the view of the adversary in the above simulated environment is the same as that inGame 1. InGame 2, the simulator rejects to answer all decryption queries (i,c=(y1,h,π,y2,σ,vk)) such that vk=vki∗. If such decryption query is not rejected inGame 1, (y1∥h∥π∥y2,σ) must be a valid message-signature pair under the verification key vki∗. The simulator sends it to the OTS challenger as the output of the simulator. This completes the proof.
Game 3. This game is identical toGame 2, except that each ABO function is chosen to have a lossy branch t∗=vk∗. That is, for user i, it first generates an OTS key pair (vk∗,sigk∗)←OTS.Gen(spots) and replaces (ekabo,ikabo)←ABO.Gen(spabo,0v) with (ekabo,ikabo)←ABO.Gen(spabo,vk∗). We show that the adversary’s views inGame 2 andGame 3 are computationally indistinguishable, under the assumption of the hidden lossy branch properties of all ABO-LTF collections. Formally, we have(21)Pr⁡win3-Pr⁡win2≤AdvABO,D2indλ,nuwhere D2 is an adversary attacking the hidden lossy branch properties of the ABO-LTF collection.
The proof is as follows: Given an ABO system parameterspabo, the simulator first generates the remainder PKE system parameters of sppke as inGame 2. It then generates nu OTS key pairs (vki∗,sigki∗) and sends (0v,vki∗) to the ABO challenger to obtain nu ABO evaluation keys ekabo(i). Next, the simulator implements the key generation algorithm to generate the remainder public keys and secret keys as that inGame 2. Since the simulator knows all secret key ski∗ (i.e., the inversion keys ikltf(i) of LTF functions), it can answer the adversary’s decryption queries and encryption queries as that inGame 2. Clearly, if ekabo(i) is generated by ABO.Gen(spabo,0v), the simulated environment is exactlyGame 2; otherwise it is exactlyGame 3. This completes the proof.
Game 4. This game is identical toGame 3 except that we keep all users’ ABO inversion key ikabo(i) and use ikabo(i) to recover the image x in the decryption query (i,c). Recall that, in each decryption query (i,c=(y1,h,π,y2,σ,vk)), if the verification key vk=vki∗, the ciphertext is rejected directly. So, we only need to recover the image x of c for the case that vk≠vki∗. Since LTF.Eval(ekltf(i),·) and ABO.Eval(ekabo(i),vk,·) are both injective, there is a unique x such that(22)y1,y2=LTF.Evalekltfi,x,ABO.Evalekaboi,vk,x.That is,Game 3 uses the LTF inversion key ikltf(i) to recover x, whileGame 4 uses the ABO inversion key ikabo(i) to recover x. Therefore, these two games are conceptionally equivalent; i.e.,(23)Pr⁡win4=Pr⁡win3
Game 5. This game is identical toGame 4 except that we replace all users’ LTF injective evaluation keys with lossy evaluation keys. Assuming the indistinguishability of injective and lossy functions of LTFs, it has that(24)Pr⁡win5-Pr⁡win4≤AdvLTF,D3indλ,nu,for some adversary D3 attacking the indistinguishability of the LTF collections.
The proof is as follows. Given the LTF system parameterspltf, the simulator generates the remainder PKE system parameters sppke as inGame 4. It then asks the LTF challenger to generate nu evaluation keys ekltf(i), which are wehther generated by the injective key generation algorithm LTF.IGen(spltf) or by the lossy key generation algorithm LTF.LGen(spltf) depending on the LTF challenger’s random coin. The simulator generates the remainder public keys for each user as inGame 4; i.e., it first generates nu OTS key pairs (vki,sigki)←OTS.Gen(spots) and then generates (ekabo(i),ikabo(i))←ABO.Gen(spabo,vki). The simulator sets pki∗=(ekltf(i),ekabo(i)) as the public key for user i. Since the simulator knows the PKE public keys and secret keys (i.e., the inversion key of the ABO functions), it can answer the adversary’s encryption queries and decryption queries as inGame 4. Clearly, if all ekltf(i) are injective evaluation keys, the adversary’s view is exactly identical toGame 4; if all ekltf(i) are lossy evaluation keys, the adversary’s view is exactly identical toGame 5. This completes the proof.
Game 6. This game is identical toGame 5 except that we replace h∗(x) with a random string r∈{0,1}k in each challenge ciphertext. We observe that, inGame 5, y1∗=LTF.Eval(ekltf(i),x) and y2∗=ABO.Eval(ekabo(i),vki∗,x) are both lossy functions. So the image size of (y1∗,y2∗) is at most 2n-(lltf+labo). Since k≤(lltf+labo-n)-2log⁡(1/ϵ), by the property of the family of pairwise independent hash functions H, it has that h∗(x) is statistically ϵ-close to uniform even given (y1∗,y2∗). Recall that there are at most nu challenge ciphertexts. Thus,(25)Pr⁡win6-Pr⁡win5≤nu·ϵ≤2-λ.InGame 6, since all r (in challenge ciphertexts) are uniformly distributed over {0,1}k, the adversary has no advantage in this game; i.e.,(26)Pr⁡win6=12.Taking all together, Theorem 11 follows.From One-Challenge Ciphertext to Multichallenge Ciphertexts. As introduced in [15], for multichallenge ciphertexts, a generic (hybrid) security reduction will suffer from a reduction loss qe. According to the above security proof, to achieve tight security, it is better to replace all injective branches with lossy branches simultaneously inGame 3. This requires that all the lossy branches are tightly indistinguishable from the injective branches. However, the ABO-LTFs only have one lossy branch, which is indistinguishable from the other (injective) branches. A good choice is to use all-but-many lossy trapdoor functions that have polynomial number of lossy branches. Though there are some constructions of ABM-LTFs, all of them either have loose security proof or rely on nonstandard assumptions. It is still an open problem to find efficient and tightly secure ABM-LTFs under reasonable assumptions, as pointed out in [11].


## 4.1. Definitions for PKE

Definition 7 (public-key encryption).
A public-key encryption schemePKE with message space M consists of the following PPT algorithms.
s p p k e ← P K E . S y s ( 1 λ ). This is the system parameter generation algorithm. It takes as input a security parameter 1λ and outputs system parameters sppke.
( p k p k e , s k p k e ) ← P K E . G e n ( s p p k e ). This is the key generation algorithm. It takes as input the system parameters sppke and outputs a public key pkpke and a secret key skpke.
c ← P K E . E n c ( p k p k e , m ). This is the message encryption algorithm. It takes as input a public key pkpke and a message m∈M and outputs a ciphertext c.
m/⊥  ←PKE.Dec(skpke,c). This is the decryption algorithm. It takes as input the secret key skpke and a ciphertext c and outputs a message m or a special symbol ⊥ (indicating that c is an invalid ciphertext).
For correctness, we require that, for allsppke←PKE.Sys(1λ), all (pkpke,skpke)←PKE.Gen(sppke), and all m∈M, it always has PKE.Dec(skpke,PKE.Enc(pkpke,m))=m.Security. We recall the security definition of indistinguishability against adaptive chosen-ciphertext attacks (CCA) in multiuser and multichallenge settings from [15, 16]. The following experiment is played between the challenger and an adversary A and is parameterized by integers nu,qe,qd∈N (i.e., the number of users, challenge ciphertexts/encryption queries, and decryption queries).Experiment E x p P K E , A i n d - c c a ( λ , n u , q e , q d ) (1)
Initialization phase: the challenger runs PKE.Sys(1λ) only once to generate the system parameter sppke and runs PKE.Gen(sppke)  nu times to generate nu key pairs (pkpke(i),skpke(i)), i∈[nu]. Then, it tosses a random coin b←$0,1, initializes a list CL≔∅ to an empty list, and defines counters ji≔0 and ji~≔0 for each i∈[nu]. (2)
Query phase: A receives pkpke(1),…,pkpke(nu) as input and may adaptively query the challenger for two types of operations.
(I)
Encryption queries: the adversary submits two messages m0,m1∈M of equal length and an index i∈[nu]. If ji≥qe then the challenger returns ⊥. Otherwise, it returns c=PKE.Enc(pkpke(i),mb), appends (i,c) to CL, and sets ji≔ji+1. (II)
Decryption queries: the adversary submits a ciphertext c and an index i∈[nu]. If (i,c)∈CL or ji~≥qd then the challenger returns ⊥. Otherwise it returns PKE.Dec(skpke(i),c) and sets ji~≔ji~+1. (3)
Guess phase:eventually, the adversary outputs a bit b′ as a guess of b.The advantage ofA in the above experiment is defined as (11)AdvPKE,Aind-ccaλ,nu,qe,qd=Pr⁡b=b′-12.Definition 8 (IND-CCA security).
We say thatA  (tpke,ϵpke) breaks the (nu,qe,qd)-IND-CCA security if A runs in times tpke and AdvPKE,Aind-cca(λ,nu,qe,qd)≥ϵpke(λ). A public-key encryption scheme PKE is (tpke,ϵpke,nu,qe,qd)-IND-CCA-secure if there exists no adversary that (tpke,ϵpke)-breaks the (nu,qe,qd)-IND-CCA security.Definition 9 (IND-CPA security).
In the above experiment, ifqd=0, then we say PKE is (tpke,ϵpke,nu,qe)-IND-CPA-secure.Clearly, if there is only one-user and one-challenger ciphertext, i.e.,nu=1,qe=1, the (1,1,qd)-IND-CCA security in the above sense is exactly the classical definition of IND-CCA security [24], and (1,1)-IND-CPA security is exactly the classical definition of IND-CPA security (or semantic security) [25]. The generic reduction from [15] showed that if A  (tpke,ϵpke)-breaks the (nu,qe,qd)-IND-CCA security, there exists A′  (tpke′,ϵpke′) that breaks the (1,1,qd)-IND-CCA security and tpke′≈tpke, ϵpke′≥ϵpke/(nu·qe). Thus, the security reduction loses (at most) a factor of L=nu·qe. A security reduction is calledtight if the corresponding reduction loss L is constant.


## 4.2. CPA-Secure PKE Scheme

In this section, we propose a generic construction of PKE scheme from LTFs and show its IND-CPA security in the setting that has polynomial number of users and challenge ciphertexts. Our security proof shows that if the underlying LTFs are tightly secure, then so is the PKE scheme.The CPA-secure PKE scheme with message space{0,1}k is given in Box 1. It applies the following components:(i)
A collection of(n,lltf)-lossy trapdoor functions: LTF=(LTF.Sys,LTF.IGen,LTF.LGen,LTF.Eval,LTF.Inv)(ii)
A family of pairwise independent hash functions:H:{0,1}n→{0,1}kBox 1:The CPA-secure PKE scheme.
P K E . S y s ( 1 λ ) : It runs spltf←LTF.Sys(1λ) and returns sppke=spltf. P K E . G e n ( s p p k e ) : It runs (ekltf,ikltf)←LTF.IGen(spltf), and returns pk=ekltf and sk=ikltf. P K E . E n c ( p k , m ): It first chooses x←${0,1}n and h←$H. It then computes y = L T F . E v a l ( e k l t f , x ) ,   π = h ( x ) ⊕ m . Finally, it returns c=(y,h,π). P K E . D e c ( s k ,  c ): First, it parses c as (y,h,π). Then, it computes x=LTF.Inv(ikltf,y). Next, it checks L T F . E v a l ( e k l t f , x ) = y . If not, it returns ⊥. Otherwise, it returns m=hx⊕π.Letϵ≔ϵ(λ)≤2-3λ be a negligible function in λ. We require that the parameters in the above primitives satisfy the condition k≤lltf-2log⁡(1/ϵ).Theorem 10.
Letλ be the security parameter, and let nu,qe≤2λ be integers. Then, the PKE scheme described in Box 1 is (tpke,ϵpke,nu,qe)-IND-CPA-secure, where(12)ϵpke≤AdvLTF,Dindλ,nu+2-λand the runtime of D is roughly the runtime of the IND-CPA experiment with an adversary of runtime tpke. Clearly, if the underlying LTFs are tightly secure, then the obtained PKE is tightly CPA-secure.Outline of Proof. The proof is very simple. First, by the indistinguishability of LTF, we replace all users’ LTF injective evaluation keys with lossy evaluation keys. Now, in the challenge ciphertexts, each function works in lossy mode and thus reveals at most (n-lltf)-bit information of x. Applying h to x, it can extract a random string, which will hide the information of the encrypted message.Proof.
We proceed in a sequence of games. LetA be a fixed adversary that breaks the IND-CPA security of the above PKE scheme in the multiuser setting. Assume that it makes at most qe encryption queries to each user’s encryption oracles. Let wini denote the event that A wins inGamei.
Game 1. This is the original IND-CPA experiment. Roughly speaking, the challenger runs sppke←PKE.Sys(1λ) only once. Then, it runs PKE.Gen(sppke)  nu times to generate nu public/secret key pairs (pk1,sk1),…,(pknu,sknu) and tosses a random coin b∈{0,1}. The adversary A takes these nu public keys as input and may make at most qe queries to each encryption oracle PKE.Enc(pki,·). Every encryption query is of the form (i,m0,m1), where i∈[nu] and m0 and m1 are two equal length messages. The challenger responds with c∗=PKE.Enc(pki,mb). Finally, the adversary outputs a bit b′ as the guess of b. We say that A wins the game if b′=b. So,(13)AdvPKE,Aind-cpaλ,nu,qe=Pr⁡win1-12.
Game 2. This game is identical toGame 1 except that we replace all users’ LTF injective keys with lossy keys. By the indistinguishability property of the LTF collection, it follows that(14)Pr⁡win2-Pr⁡win1≤AdvLTF,Dindλ,nufor some adversary D attacking LTF’s indistinguishability.
The proof is as follows. Given the system parameterspltf of LTF, the simulator sets sppke=spltf and asks the LTF challenger to generation nu LTF keys ekltf(i). The simulator sets pki=ekltf(i) and returns it to the adversary. Once the adversary asks an encryption query (i,m0,m1), the simulator tosses a random coin in advance and computes the challenge ciphertext as inGame 1. Clearly, if all ekltf(i) are generated by the injective key generation algorithm LTF.IGen(spltf), the view of the adversary is exactlyGame 1; otherwise, it is exactlyGame 2. This completes the proof.
Game 3. This game is identical toGame 2, except that we replace h(x) in each challenge ciphertext with a uniformly distributed string r∈{0,1}k. We show that(15)Pr⁡win3-Pr⁡win2≤nuqe·ϵ.The proof is as follows. First, observe that, inGame 2, all y∗=LTF.Eval(ekltf(i),x) in challenge ciphertexts are lossy functions. So the image size of y∗ is at most n-lltf. Since k≤lltf-2log⁡(1/ϵ), by the property of H, it follows that (y∗,h∗,h∗(x)) is statistically ϵ-close to (y∗,h∗,r), where h∗←H and r is uniformly distributed over {0,1}k. Recall that there are at most nuqe challenge ciphertexts. The proof completes. Since ϵ≤2-3λ and nu,qe≤2λ, we further have that(16)Pr⁡win3-Pr⁡win2≤2-λ.Recall that, inGame 3, each challenge message mb is perfectly hidden by the random string r; i.e., π∗=r⊕mb; it follows that(17)Pr⁡win3=12.Taking all together, we get Theorem 10.


## 4.3. CCA-Secure PKE Scheme

Next, we propose a generic construction of PKE scheme from LTFs and ABO-LTFs and show its CCA security in the setting that has polynomial number of users and one-challenge ciphertext. Our security proof shows that if the underlying LTFs and ABO-LTFs are tightly secure, then so is the PKE scheme.The CCA-secure PKE scheme with message space{0,1}k is given in Box 2. It applies the following components:(i)
A collection of(n,lltf)-lossy trapdoor functions: LTF=(LTF.Sys,LTF.IGen,LTF.LGen,LTF.Eval,LTF.Inv)(ii)
A collection of(n,labo)-all-but-one lossy trapdoor functions: ABO=(ABO.Sys,ABO.Gen,ABO.Eval,ABO.Inv) with branch set Bλ={0,1}v(iii)
A family of pairwise independent hash functions:H:{0,1}n→{0,1}k(iv)
A strongly unforgeable one-time signatures scheme:OTS=(OTS.Gen,OTS.Sign,OTS.Vrf).Box 2:The CCA-secure PKE scheme.
P K E . S y s ( 1 λ ) : It runs spltf←LTF.Sys(1λ), spabo←ABO.Sys(1λ) and spots←OTS.Gen(1λ), and then returns sppke=(spltf,spabo). P K E . G e n ( s p p k e ) : It runs (ekltf,ikltf)←LTF.IGen(spltf) and (ekabo,ikabo)←ABO.Gen(spabo,0v) with branch 0v, returns pk=(ekltf,ekabo) and sk=ikltf. P K E . E n c ( p k p k e , m ): It first runs OTS.Gen(1λ) to obtain a one-time signature key pair (vk,sigk). It then chooses x ← $ { 0,1 } n and h←$H, and computes y 1 = L T F . E v a l ( e k l t f , x ) ,   π = h ( x ) ⊕ m , y 2 = A B O . E v a l ( e k a b o , v k , x ) ,   σ = O T S . S i g n ( s i g k , y 1 | | h | | π | | y 2 ) Finally, it returns c=(y1,h,π,y2,σ,vk). P K E . D e c ( s k p k e , c ): It first checks that OTS.Vrf(vk,y1||h||π||y2,σ)=1. If not, it outputs ⊥. It then computes x = L T F . I n v ( i k l t f , y 1 ) and checks LTF.Eval(ekltf,x)=y1 and ABO.Eval(ekabo,vk,x)=y2; if not, it outputs ⊥. Finally, it outputs m=h(x)⊕π.Letϵ≔ϵ(λ)≤2-2λ be a negligible function in λ. We require that (1) the parameters in the above primitives satisfy the condition k≤(lltf+labo-n)-2log⁡(1/ϵ); (2) the branch set Bλ contains the set of signature verification keys.Theorem 11.
Letλ be the security parameter and let nu, qe, qd be integers such that nu≤2λ, qe=1. Then, the PKE scheme described in Box 2 is (tpke,ϵpke,nu,qe=1,qd)-IND-CCA-secure, where(18)ϵpke≤AdvOTS,D1su-cmaλ,nu+AdvABO,D2indλ,nu+AdvLTF,D3indλ,nu+2-λand the runtime of D1, D2, D3 is roughly the runtime of the IND-CCA experiment with an adversary of runtime tpke.Outline of Proof. The proof idea mainly follows [1]. First, by the all-but-one property, we replace each ABO lossy branch with the corresponding verification key of the challenge ciphertext. Since the underlying OTS is strongly unforgeable, all branches in decryption queries would be distinct with the corresponding lossy branch. Thus, all ABO functions in the decryption queries are injective. By this observation, we can replace the decryption key with the ABO inversion key. Next, by the indistinguishability of LTFs, we replace all users’ LTF injective keys with lossy keys. Now, in the challenge ciphertexts, each function works in lossy mode and reveals at most (n-lltf)+(n-labo) bits information of x. So, the application of h guarantees that the ciphertexts of m0 and m1 are indistinguishable.Proof.
We proceed in a sequence of games. LetA be a fixed adversary that breaks the IND-CCA security of the PKE scheme in the multiuser setting. Assume that it makes at mostone encryption query (resp., qd decryption query) to each user’s encryption oracle (resp., decryption oracle). Let wini denote the probability that A wins inGamei.
Game 1. This is the original IND-CCA experiment. Roughly speaking, the challenger first runs sppke←PKE.Sys(1λ) only once. It then runs PKE.Gen(sppke)nu times to generate nu public/secret key pairs (pk1∗,sk1∗),…,(pknu∗,sknu∗) and tosses a random coin b∈{0,1}. The adversary A receives these nu public keys as input and may makeone query to each encryption oracle PKE.Enc(pki∗,·) and qd queries to each decryption oracle PKE.Dec(ski∗,·). Each encryption query is of the form (i,m0,m1) where i∈[nu], and m0 and m1 are two equal length messages, and the challenger responds with ci∗=PKE.Enc(pki∗,mb). Each decryption query is of the form (i,c), where i∈[nu]. The challenger will respond with PKE.Dec(ski∗,c). Finally, the adversary outputs a bit b′ as the guess of b. We say that A wins the game if b′=b. Clearly, the adversary is not allowed to ask for the decryption of the challenge ciphertext; i.e., (i,c)=(i,ci∗). According to the definition of IND-CCA experiment, we have that(19)AdvPKE,Aind-ccaλ,nu,qe,qd=Pr⁡win1-12.Hereafter, we use (i,c=(y1,h,π,y2,σ,vk)) to denote a decryption query, in which the ciphertext c is encrypted under public key pki∗, and denote by (i,ci∗=(y1∗,h∗,π∗,y2∗,σ∗,vk∗)) the challenge ciphertext under user i’s public key.
Game 2. This game is identical toGame 1 except that it rejects all decryption queries (i,c) in which the verification key vk is the same as that of the corresponding challenge ciphertext (i,ci∗) for any i∈[nu]. Recall that A is forbidden to ask for decryption query such that (i,c)=(i,ci∗). So, c≠ci∗. Suppose that there exists some decryption query (i,c), in which vk=vk∗. It must have that (y1,h,π,y2,σ)≠(y1∗,h∗,π∗,y2∗,σ∗). By the strong unforgeability of the underlying one-time signature, we have the following result:(20)Pr⁡win2-Pr⁡win1≤AdvOTS,D1su-cmaλ,nufor some adversary D1 attacking the strong unforgeability of the underlying OTS in the multiuser setting.
The proof is as follows. The simulator asks the OTS challenger to generate the system parameterspots and nu one-time key pairs (vki∗,sigki∗). The simulator will receive the OTS system parameter spots and nu verification keys vki∗. The simulator then generates the other system parameters of the PKE scheme, including (spltf,spabo), and generates nu PKE key pairs (pki∗,ski∗) as inGame 1. The simulator sends the PKE system parameter sppke=(spltf,spabo,spots) and nu PKE public keys pki∗ to the adversary. As the simulator knows all users’ decryption keys, it can answer the adversary’s decryption queries as inGame 1. To answer encryption queries, the simulator tosses a random coin b∈{0,1} in advance. Given (i,m0,m1), the simulator randomly chooses x←{0,1}n and h∗←H and computes y1∗=LTF.Eval(ekltf,x), π∗=h∗(x)⊕mb, and y2∗=OTS.Eval(ekabo,vki∗,x). The simulator sends the message y1∗∥h∗∥π∗∥y2∗ to the OTS challenger to obtain a signature σ∗ which is signed under the corresponding signing key sigki∗. The simulator sends the challenge ciphertext c∗=(y1∗,h∗,π∗,y2∗,σ∗,vk∗=vki∗) to the adversary. Clearly, the view of the adversary in the above simulated environment is the same as that inGame 1. InGame 2, the simulator rejects to answer all decryption queries (i,c=(y1,h,π,y2,σ,vk)) such that vk=vki∗. If such decryption query is not rejected inGame 1, (y1∥h∥π∥y2,σ) must be a valid message-signature pair under the verification key vki∗. The simulator sends it to the OTS challenger as the output of the simulator. This completes the proof.
Game 3. This game is identical toGame 2, except that each ABO function is chosen to have a lossy branch t∗=vk∗. That is, for user i, it first generates an OTS key pair (vk∗,sigk∗)←OTS.Gen(spots) and replaces (ekabo,ikabo)←ABO.Gen(spabo,0v) with (ekabo,ikabo)←ABO.Gen(spabo,vk∗). We show that the adversary’s views inGame 2 andGame 3 are computationally indistinguishable, under the assumption of the hidden lossy branch properties of all ABO-LTF collections. Formally, we have(21)Pr⁡win3-Pr⁡win2≤AdvABO,D2indλ,nuwhere D2 is an adversary attacking the hidden lossy branch properties of the ABO-LTF collection.
The proof is as follows: Given an ABO system parameterspabo, the simulator first generates the remainder PKE system parameters of sppke as inGame 2. It then generates nu OTS key pairs (vki∗,sigki∗) and sends (0v,vki∗) to the ABO challenger to obtain nu ABO evaluation keys ekabo(i). Next, the simulator implements the key generation algorithm to generate the remainder public keys and secret keys as that inGame 2. Since the simulator knows all secret key ski∗ (i.e., the inversion keys ikltf(i) of LTF functions), it can answer the adversary’s decryption queries and encryption queries as that inGame 2. Clearly, if ekabo(i) is generated by ABO.Gen(spabo,0v), the simulated environment is exactlyGame 2; otherwise it is exactlyGame 3. This completes the proof.
Game 4. This game is identical toGame 3 except that we keep all users’ ABO inversion key ikabo(i) and use ikabo(i) to recover the image x in the decryption query (i,c). Recall that, in each decryption query (i,c=(y1,h,π,y2,σ,vk)), if the verification key vk=vki∗, the ciphertext is rejected directly. So, we only need to recover the image x of c for the case that vk≠vki∗. Since LTF.Eval(ekltf(i),·) and ABO.Eval(ekabo(i),vk,·) are both injective, there is a unique x such that(22)y1,y2=LTF.Evalekltfi,x,ABO.Evalekaboi,vk,x.That is,Game 3 uses the LTF inversion key ikltf(i) to recover x, whileGame 4 uses the ABO inversion key ikabo(i) to recover x. Therefore, these two games are conceptionally equivalent; i.e.,(23)Pr⁡win4=Pr⁡win3
Game 5. This game is identical toGame 4 except that we replace all users’ LTF injective evaluation keys with lossy evaluation keys. Assuming the indistinguishability of injective and lossy functions of LTFs, it has that(24)Pr⁡win5-Pr⁡win4≤AdvLTF,D3indλ,nu,for some adversary D3 attacking the indistinguishability of the LTF collections.
The proof is as follows. Given the LTF system parameterspltf, the simulator generates the remainder PKE system parameters sppke as inGame 4. It then asks the LTF challenger to generate nu evaluation keys ekltf(i), which are wehther generated by the injective key generation algorithm LTF.IGen(spltf) or by the lossy key generation algorithm LTF.LGen(spltf) depending on the LTF challenger’s random coin. The simulator generates the remainder public keys for each user as inGame 4; i.e., it first generates nu OTS key pairs (vki,sigki)←OTS.Gen(spots) and then generates (ekabo(i),ikabo(i))←ABO.Gen(spabo,vki). The simulator sets pki∗=(ekltf(i),ekabo(i)) as the public key for user i. Since the simulator knows the PKE public keys and secret keys (i.e., the inversion key of the ABO functions), it can answer the adversary’s encryption queries and decryption queries as inGame 4. Clearly, if all ekltf(i) are injective evaluation keys, the adversary’s view is exactly identical toGame 4; if all ekltf(i) are lossy evaluation keys, the adversary’s view is exactly identical toGame 5. This completes the proof.
Game 6. This game is identical toGame 5 except that we replace h∗(x) with a random string r∈{0,1}k in each challenge ciphertext. We observe that, inGame 5, y1∗=LTF.Eval(ekltf(i),x) and y2∗=ABO.Eval(ekabo(i),vki∗,x) are both lossy functions. So the image size of (y1∗,y2∗) is at most 2n-(lltf+labo). Since k≤(lltf+labo-n)-2log⁡(1/ϵ), by the property of the family of pairwise independent hash functions H, it has that h∗(x) is statistically ϵ-close to uniform even given (y1∗,y2∗). Recall that there are at most nu challenge ciphertexts. Thus,(25)Pr⁡win6-Pr⁡win5≤nu·ϵ≤2-λ.InGame 6, since all r (in challenge ciphertexts) are uniformly distributed over {0,1}k, the adversary has no advantage in this game; i.e.,(26)Pr⁡win6=12.Taking all together, Theorem 11 follows.From One-Challenge Ciphertext to Multichallenge Ciphertexts. As introduced in [15], for multichallenge ciphertexts, a generic (hybrid) security reduction will suffer from a reduction loss qe. According to the above security proof, to achieve tight security, it is better to replace all injective branches with lossy branches simultaneously inGame 3. This requires that all the lossy branches are tightly indistinguishable from the injective branches. However, the ABO-LTFs only have one lossy branch, which is indistinguishable from the other (injective) branches. A good choice is to use all-but-many lossy trapdoor functions that have polynomial number of lossy branches. Though there are some constructions of ABM-LTFs, all of them either have loose security proof or rely on nonstandard assumptions. It is still an open problem to find efficient and tightly secure ABM-LTFs under reasonable assumptions, as pointed out in [11].


## 5. Instantiations under DDH Assumption

The constructions come from Peikert and Waters DDH-based LTFs and ABO-LTFs [1], and our main work is to prove its tightness in the multiuser setting. We first introduce some basic notations and results.


### 5.1. Basic Notations

Let(G,p,g) be a group description outputted by G(1λ). Below, we let r=(r1,…,rn)←$Zpn, s=(s1,…,sn,sn+1)←$Zpn×{1}, and x=(x1,…,xn)∈Zpn be row vectors. Let A=(ai,j)i∈[n],j∈[n+1] and B=(bi,j)i∈[n],j∈[n+1] be n×(n+1) matrices over Zpn×(n+1), and let E=(gi,j)i∈[n],j∈[n+1] be n×(n+1) matrix over Gn×(n+1). We define the following:(i)
r⊗s=rTs=(risj)i∈[n],j∈[n+1]∈Zpn×(n+1) is the outer product of r and s.(ii)
gA=(gai,j)i∈[n],j∈[n+1]∈Gn×(n+1).(iii)
gA+B=gai,j+bi,ji∈[n],j∈[n+1]=gai,j·gbi,ji∈[n],j∈[n+1] is component-wise multiplication of gA and gB.(iv)
Ex=(∏i=1ngi,1xi,…,∏i=1ngi,nxi,∏i=1ngi,n+1xi)∈Gn+1.Prior to describing the construction, we introduce the following lemma that is useful in our security proofs.Lemma 12.
Let(G,p,g) be a group description outputted by G(1λ). For any positive integer L, define matrices El=grl⊗sl∈Gn×(n+1), where rl←$Zpn, sl←$Zpn×1, and 1≤l≤L. Let (G1,…,GL) be L random matrices over Gn×(n+1). Then, for any PPT adversary B, it holds that(27)Pr⁡BE1,…,EL=1-Pr⁡BG1,…,GL=1≤n·AdvA,Gddhλ+nLpwhere A is an algorithm distinguishing the DDH problem over G.Proof.
The proof goes through a sequence of games. In each game,B is given L matrices A1,…,AL∈Gn×(n+1). In Game0, the distribution of (A1,…,AL) is the same as that of (E1,…,EL); i.e., A picks L random vectors r1,…,rL∈Zpn and s1,…,sL∈Zpn×{1} and sets Al=grl⊗sl for 1≤l≤L. In Gamek, all Al are sampled as that in Gamek-1, except that the group elements in the first k rows of Al are with random elements of G. Clearly, in Gamen, (A1,…,AL) has the same distribution as that of (G1,…,GL). Next, we show that the distributions of (A1,…,AL) in any two successive games Gamek-1 and Gamek (1≤k≤n) are computationally indistinguishable under the DDH assumption.
Given a DDH challenge problem(ga,gb,gc)∈G3, A first involves algorithm Rddh(p,g,(ga,gb,gc),1) for L times independently to obtain L tuples (gal,gbl,gcl). Then, A runs algorithm Rddh(p,g,(gal,gbl,gcl),0) for n times independently to obtain n tuples (gal,gbl,j,gcl,j), where j∈[n]. Now, A chooses a random vector rl=(rl,1,…,rl,n)∈Zpn and sets matrix Al as the following form:(28)Al=g1,1⋯g1,ng1,n+1⋮⋱⋮⋮gk-1,1⋯gk-1,ngk-1,n+1gk,1⋯gk,ngk,n+1⋮⋱⋮⋮gn,1⋯gn,ngn,n+1where(29)gi,j=randomgroupelementsifi≤k-1and1≤j≤n+1gcl,jifi=kand1≤j≤ngalifi=kandj=n+1gbl,jrl,iifk+1≤i≤nand1≤j≤ngrl,iifk+1≤i≤nandj=n+1.
Now, we discuss the distributions ofAl for two cases: (1) If (ga,gb,gc)∈G3 is a DDH-tuple, by the property of algorithm Rddh, the n tuples (gal,gbl,j,gcl,j) are also DDH-tuples, and thus Al has the same distribution as that in Gamei-1. (2) If (ga,gb,gc)∈G3 is not a DDH-tuple, it has that c≠abmodp and the L tuples (gal,gbl,gcl) are randomly distributed over G3. Clearly, with probability at least (1-1/p)L≥1-L/p, all cl≠al·blmodp hold. By the property of algorithm Rddh, the n tuples (gal,gbl,j,gcl,j) (j∈[n]) are randomly distributed over G3. So, in this case, Al is distributed as that in Gamek with probability of at least 1-L/p. Therefore, for any 1≤k≤n, we have that(30)Pr⁡BGamek=1-Pr⁡BGamek-1=1≤AdvA,Gddhλ+Lp.The theorem follows directly from the above result.


### 5.2. Tightly Secure LTFs

The collection of LTFsLTF=(LTF.Sys,LTF.IGen,LTF.LGen,LTF.Eval,LTF.Inv) with domain {0,1}n is described in Box 3.Box 3:A collection of LTFs from the DDH assumption.
System Parameter.  spltf←LTF.Sys(1λ): It runs spltf≔(G,p,g)←G(1λ) and returns spltf. Key Generation. e k l t f , i k l t f ← L T F . I G e n s p l t f :  I t  r a n d o m l y  c h o o s e s  t w o  v e c t o r s  r = r 1 , … , r n ← $ Z p n and s = ( s 1 , … , s n , 1 ) ← $ Z p n × { 1 }   A ← $ R k n ( Z p n × n ), and computes E=g(r⊗s)+In×(n+1)∈Gn×(n+1), where I n × ( n + 1 ) ∈ Z p n × ( n + 1 ) is an identity matrix extended by a zero column. It returns ekltf=E and ikltf=s. Lossy Key Generation. ekltf←LTF.LGen(spltf): It randomly chooses two vectors r=(r1,…,rn)←$Zpn and s = ( s 1 , … , s n , 1 ) ← $ Z p n × { 1 }   A ← $ R k n ( Z p n × n ), and computes E=gr⊗s∈Gn×(n+1). It returns ekltf=E. Evaluation.  y←LTF.Eval(ekltf,x): On input x=(x1,…,xn)∈{0,1}n, it computes an image y=Ex∈Gn+1. Inversion.  x←LTF.Inv(ikltf,y): Suppose that y=(y1,…,yn,yn+1). For i∈[n], it computes gi=yi/(yn+1si), and lets xi∈{0,1} be such that gi=gxi. It returns x=(x1,…,xn).Theorem 13.
If the DDH assumption holds inG, then the construction in Box 3 is a collection of lossy trapdoor functions with lossiness n-log⁡p. Particularly, for any PPT adversary A, there exists a DDH distinguisher D of roughly the same complexity as A such that(31)AdvLTF,Aindλ,L≤2n·AdvG,Dddhλ+2nLp.Proof.
We first show its correctness and lossiness and then prove its indistinguishability.
Correctness. If E=g(r⊗s)+In×(n+1) is an injective evaluation key, then, for any string x=(x1,…,xn)∈{0,1}n, it has that(32)Ex=y1,…,yn,yn+1=gx1+s1∑i=1nxiri,…,gxn+sn∑i=1nxiri,g∑i=1nxiri∈Gn×n+1.So, gi=yi/(yn+1si)=gxi and the correctness follows.
Lossiness. If E=gr⊗s is a lossy evaluation key, then, for any string x=(x1,…,xn)∈{0,1}n, it has that(33)y1,…,yn,yn+1=Ex=gs1∑i=1nxiri,…,gsn∑i=1nxiri,g∑i=1nxiri∈Gn×n+1.So, for any fixed lossy evaluation key, the image of LTF.Eval(ekltf,·) is completely determined by yn+1, which has only p possible values. Therefore, the above collection of LTFs is (n-log⁡p)-lossy.
Indistinguishability. By Lemma 12, any L number of lossy evaluation keys (E1,…,EL) is computationally indistinguishable from L random matrices (G1,…,GL). If the diagonal elements of each matrix El multiply g, the results are L injective keys. A random matrix, whose diagonal elements multiply a fixed element g, is still a random matrix. Thus, the L injective keys are computationally indistinguishable from L random matrices, and the computational distance is at most 2n·AdvG,Dddh(λ)+2nL/p.


### 5.3. Tightly Secure ABO-LTFs

The collection of ABO-LTFsABO=(ABO.Sys,ABO.Gen,ABO.Eval,ABO.Inv) with domain {0,1}n is described in Box 4.Box 4:A collection of ABO-LTFs from the DDH assumption.
System Parameter.  spabo←ABO.Sys(1λ): It returns spabo≔(G,p,g)←G(1λ). The branch space is Bλ=Zp. Key Generation.  (ekabo,ikabo)←ABO.Gen(spabo,t∗): For any branch t∗∈Zp, it randomly chooses two vectors r = ( r 1 , … , r n ) ← $ Z p n and s=(s1,…,sn,1)←$Zpn×{1}, and computes E=g(r⊗s)-t∗In×(n+1)∈Gn×(n+1). It returns ekabo=E and ikabo=s. Evaluation.  y←ABO.Eval(ekabo,t,x): On input x=(x1,…,xn)∈{0,1}n and a branch t∈Zp, it computes an image y=(E⋅gtIn×(n+1))x∈Gn+1. Inversion.  x←LTF.Inv(ikabo,t,y): Suppose that y=(y1,…,yn,yn+1) and t≠t∗. For i∈[n], it computes g i = y i / ( y n + 1 s i ), and lets xi∈{0,1} be such that gi=gxi(t-t∗). It returns x=(x1,…,xn).Theorem 14.
If the DDH assumption holds inG, then the construction in Box 4 is a collection of all-but-one lossy trapdoor functions with lossiness n-log⁡p. Particularly, for any PPT adversary A, there exists a DDH distinguisher D of roughly the same complexity as A such that(34)AdvABO,Aindλ,L≤2n·AdvG,Dddhλ+2nLp.Proof.
We first show its correctness and lossiness, and then prove its indistinguishability.
Correctness. If t≠t∗, then E·gtIn×(n+1)=g(r⊗s)+(t-t∗)In×(n+1) is an injective evaluation key. For any string x=(x1,…,xn)∈{0,1}n, it has that (35)E·gtIn×n+1x=y1,…,yn,yn+1=gx1t-t∗+s1∑i=1nxiri,…,gxnt-t∗+sn∑i=1nxiri,g∑i=1nxiri∈Gn×n+1.So, gi=yi/(yn+1si)=gxi(t-t∗) and the correctness follows.
Lossiness. If t=t∗, then E·gtIn×(n+1)=gr⊗s is a lossy evaluation key, which is the same as the lossy evaluation key in previous LTFs. So, the lossiness is (n-log⁡p).
Hidden Lossy Branch. As the discussion on LTFs, for any L tuple of branches (t1,…,tL), the L evaluation keys ekabo(l) generated by ABO.Gen(spabo,tl), are computationally indistinguishable from a tuple of L random matrices (G1,…,GL) with distance at most n·AdvG,Dddh(λ)+nL/p. Therefore, for any two tuples of branches (t1,…,tL) and (t1′,…,tL′), the evaluation keys generated by ABO.Gen(spabo,tl) are computationally indistinguishable from the evaluation keys generated by ABO.Gen(spabo,tl′) with distance 2n·AdvG,Dddh(λ)+2nL/p.


## 5.1. Basic Notations

Let(G,p,g) be a group description outputted by G(1λ). Below, we let r=(r1,…,rn)←$Zpn, s=(s1,…,sn,sn+1)←$Zpn×{1}, and x=(x1,…,xn)∈Zpn be row vectors. Let A=(ai,j)i∈[n],j∈[n+1] and B=(bi,j)i∈[n],j∈[n+1] be n×(n+1) matrices over Zpn×(n+1), and let E=(gi,j)i∈[n],j∈[n+1] be n×(n+1) matrix over Gn×(n+1). We define the following:(i)
r⊗s=rTs=(risj)i∈[n],j∈[n+1]∈Zpn×(n+1) is the outer product of r and s.(ii)
gA=(gai,j)i∈[n],j∈[n+1]∈Gn×(n+1).(iii)
gA+B=gai,j+bi,ji∈[n],j∈[n+1]=gai,j·gbi,ji∈[n],j∈[n+1] is component-wise multiplication of gA and gB.(iv)
Ex=(∏i=1ngi,1xi,…,∏i=1ngi,nxi,∏i=1ngi,n+1xi)∈Gn+1.Prior to describing the construction, we introduce the following lemma that is useful in our security proofs.Lemma 12.
Let(G,p,g) be a group description outputted by G(1λ). For any positive integer L, define matrices El=grl⊗sl∈Gn×(n+1), where rl←$Zpn, sl←$Zpn×1, and 1≤l≤L. Let (G1,…,GL) be L random matrices over Gn×(n+1). Then, for any PPT adversary B, it holds that(27)Pr⁡BE1,…,EL=1-Pr⁡BG1,…,GL=1≤n·AdvA,Gddhλ+nLpwhere A is an algorithm distinguishing the DDH problem over G.Proof.
The proof goes through a sequence of games. In each game,B is given L matrices A1,…,AL∈Gn×(n+1). In Game0, the distribution of (A1,…,AL) is the same as that of (E1,…,EL); i.e., A picks L random vectors r1,…,rL∈Zpn and s1,…,sL∈Zpn×{1} and sets Al=grl⊗sl for 1≤l≤L. In Gamek, all Al are sampled as that in Gamek-1, except that the group elements in the first k rows of Al are with random elements of G. Clearly, in Gamen, (A1,…,AL) has the same distribution as that of (G1,…,GL). Next, we show that the distributions of (A1,…,AL) in any two successive games Gamek-1 and Gamek (1≤k≤n) are computationally indistinguishable under the DDH assumption.
Given a DDH challenge problem(ga,gb,gc)∈G3, A first involves algorithm Rddh(p,g,(ga,gb,gc),1) for L times independently to obtain L tuples (gal,gbl,gcl). Then, A runs algorithm Rddh(p,g,(gal,gbl,gcl),0) for n times independently to obtain n tuples (gal,gbl,j,gcl,j), where j∈[n]. Now, A chooses a random vector rl=(rl,1,…,rl,n)∈Zpn and sets matrix Al as the following form:(28)Al=g1,1⋯g1,ng1,n+1⋮⋱⋮⋮gk-1,1⋯gk-1,ngk-1,n+1gk,1⋯gk,ngk,n+1⋮⋱⋮⋮gn,1⋯gn,ngn,n+1where(29)gi,j=randomgroupelementsifi≤k-1and1≤j≤n+1gcl,jifi=kand1≤j≤ngalifi=kandj=n+1gbl,jrl,iifk+1≤i≤nand1≤j≤ngrl,iifk+1≤i≤nandj=n+1.
Now, we discuss the distributions ofAl for two cases: (1) If (ga,gb,gc)∈G3 is a DDH-tuple, by the property of algorithm Rddh, the n tuples (gal,gbl,j,gcl,j) are also DDH-tuples, and thus Al has the same distribution as that in Gamei-1. (2) If (ga,gb,gc)∈G3 is not a DDH-tuple, it has that c≠abmodp and the L tuples (gal,gbl,gcl) are randomly distributed over G3. Clearly, with probability at least (1-1/p)L≥1-L/p, all cl≠al·blmodp hold. By the property of algorithm Rddh, the n tuples (gal,gbl,j,gcl,j) (j∈[n]) are randomly distributed over G3. So, in this case, Al is distributed as that in Gamek with probability of at least 1-L/p. Therefore, for any 1≤k≤n, we have that(30)Pr⁡BGamek=1-Pr⁡BGamek-1=1≤AdvA,Gddhλ+Lp.The theorem follows directly from the above result.


## 5.2. Tightly Secure LTFs

The collection of LTFsLTF=(LTF.Sys,LTF.IGen,LTF.LGen,LTF.Eval,LTF.Inv) with domain {0,1}n is described in Box 3.Box 3:A collection of LTFs from the DDH assumption.
System Parameter.  spltf←LTF.Sys(1λ): It runs spltf≔(G,p,g)←G(1λ) and returns spltf. Key Generation. e k l t f , i k l t f ← L T F . I G e n s p l t f :  I t  r a n d o m l y  c h o o s e s  t w o  v e c t o r s  r = r 1 , … , r n ← $ Z p n and s = ( s 1 , … , s n , 1 ) ← $ Z p n × { 1 }   A ← $ R k n ( Z p n × n ), and computes E=g(r⊗s)+In×(n+1)∈Gn×(n+1), where I n × ( n + 1 ) ∈ Z p n × ( n + 1 ) is an identity matrix extended by a zero column. It returns ekltf=E and ikltf=s. Lossy Key Generation. ekltf←LTF.LGen(spltf): It randomly chooses two vectors r=(r1,…,rn)←$Zpn and s = ( s 1 , … , s n , 1 ) ← $ Z p n × { 1 }   A ← $ R k n ( Z p n × n ), and computes E=gr⊗s∈Gn×(n+1). It returns ekltf=E. Evaluation.  y←LTF.Eval(ekltf,x): On input x=(x1,…,xn)∈{0,1}n, it computes an image y=Ex∈Gn+1. Inversion.  x←LTF.Inv(ikltf,y): Suppose that y=(y1,…,yn,yn+1). For i∈[n], it computes gi=yi/(yn+1si), and lets xi∈{0,1} be such that gi=gxi. It returns x=(x1,…,xn).Theorem 13.
If the DDH assumption holds inG, then the construction in Box 3 is a collection of lossy trapdoor functions with lossiness n-log⁡p. Particularly, for any PPT adversary A, there exists a DDH distinguisher D of roughly the same complexity as A such that(31)AdvLTF,Aindλ,L≤2n·AdvG,Dddhλ+2nLp.Proof.
We first show its correctness and lossiness and then prove its indistinguishability.
Correctness. If E=g(r⊗s)+In×(n+1) is an injective evaluation key, then, for any string x=(x1,…,xn)∈{0,1}n, it has that(32)Ex=y1,…,yn,yn+1=gx1+s1∑i=1nxiri,…,gxn+sn∑i=1nxiri,g∑i=1nxiri∈Gn×n+1.So, gi=yi/(yn+1si)=gxi and the correctness follows.
Lossiness. If E=gr⊗s is a lossy evaluation key, then, for any string x=(x1,…,xn)∈{0,1}n, it has that(33)y1,…,yn,yn+1=Ex=gs1∑i=1nxiri,…,gsn∑i=1nxiri,g∑i=1nxiri∈Gn×n+1.So, for any fixed lossy evaluation key, the image of LTF.Eval(ekltf,·) is completely determined by yn+1, which has only p possible values. Therefore, the above collection of LTFs is (n-log⁡p)-lossy.
Indistinguishability. By Lemma 12, any L number of lossy evaluation keys (E1,…,EL) is computationally indistinguishable from L random matrices (G1,…,GL). If the diagonal elements of each matrix El multiply g, the results are L injective keys. A random matrix, whose diagonal elements multiply a fixed element g, is still a random matrix. Thus, the L injective keys are computationally indistinguishable from L random matrices, and the computational distance is at most 2n·AdvG,Dddh(λ)+2nL/p.


## 5.3. Tightly Secure ABO-LTFs

The collection of ABO-LTFsABO=(ABO.Sys,ABO.Gen,ABO.Eval,ABO.Inv) with domain {0,1}n is described in Box 4.Box 4:A collection of ABO-LTFs from the DDH assumption.
System Parameter.  spabo←ABO.Sys(1λ): It returns spabo≔(G,p,g)←G(1λ). The branch space is Bλ=Zp. Key Generation.  (ekabo,ikabo)←ABO.Gen(spabo,t∗): For any branch t∗∈Zp, it randomly chooses two vectors r = ( r 1 , … , r n ) ← $ Z p n and s=(s1,…,sn,1)←$Zpn×{1}, and computes E=g(r⊗s)-t∗In×(n+1)∈Gn×(n+1). It returns ekabo=E and ikabo=s. Evaluation.  y←ABO.Eval(ekabo,t,x): On input x=(x1,…,xn)∈{0,1}n and a branch t∈Zp, it computes an image y=(E⋅gtIn×(n+1))x∈Gn+1. Inversion.  x←LTF.Inv(ikabo,t,y): Suppose that y=(y1,…,yn,yn+1) and t≠t∗. For i∈[n], it computes g i = y i / ( y n + 1 s i ), and lets xi∈{0,1} be such that gi=gxi(t-t∗). It returns x=(x1,…,xn).Theorem 14.
If the DDH assumption holds inG, then the construction in Box 4 is a collection of all-but-one lossy trapdoor functions with lossiness n-log⁡p. Particularly, for any PPT adversary A, there exists a DDH distinguisher D of roughly the same complexity as A such that(34)AdvABO,Aindλ,L≤2n·AdvG,Dddhλ+2nLp.Proof.
We first show its correctness and lossiness, and then prove its indistinguishability.
Correctness. If t≠t∗, then E·gtIn×(n+1)=g(r⊗s)+(t-t∗)In×(n+1) is an injective evaluation key. For any string x=(x1,…,xn)∈{0,1}n, it has that (35)E·gtIn×n+1x=y1,…,yn,yn+1=gx1t-t∗+s1∑i=1nxiri,…,gxnt-t∗+sn∑i=1nxiri,g∑i=1nxiri∈Gn×n+1.So, gi=yi/(yn+1si)=gxi(t-t∗) and the correctness follows.
Lossiness. If t=t∗, then E·gtIn×(n+1)=gr⊗s is a lossy evaluation key, which is the same as the lossy evaluation key in previous LTFs. So, the lossiness is (n-log⁡p).
Hidden Lossy Branch. As the discussion on LTFs, for any L tuple of branches (t1,…,tL), the L evaluation keys ekabo(l) generated by ABO.Gen(spabo,tl), are computationally indistinguishable from a tuple of L random matrices (G1,…,GL) with distance at most n·AdvG,Dddh(λ)+nL/p. Therefore, for any two tuples of branches (t1,…,tL) and (t1′,…,tL′), the evaluation keys generated by ABO.Gen(spabo,tl) are computationally indistinguishable from the evaluation keys generated by ABO.Gen(spabo,tl′) with distance 2n·AdvG,Dddh(λ)+2nL/p.



---

*Source: 3636759-2019-01-16.xml*