# CCA Secure Public Key Encryption against After-the-Fact Leakage without NIZK Proofs

Authors: Yi Zhao; Kaitai Liang; Bo Yang; Liqun Chen
Journal: Security and Communication Networks
 (2019)

---

## Abstract

In leakage resilient cryptography, there is a seemingly inherent restraint on the ability of the adversary that it cannot get access to the leakage oracle after the challenge. Recently, a series of works made a breakthrough to consider a postchallenge leakage. They presented achievable public key encryption (PKE) schemes which are semantically secure against after-the-fact leakage in the split-state model. This model puts a more acceptable constraint on adversary’s ability that the adversary cannot query the leakage of secret states as a whole but the functions of several parts separately instead of prechallenge query only. To obtain security against chosen ciphertext attack (CCA) for PKE schemes against after-the-fact leakage attack (AFL), existing works followed the paradigm of “double encryption” which needs noninteractive zero knowledge (NIZK) proofs in the encryption algorithm. We present an alternative way to achieve AFL-CCA security via lossy trapdoor functions (LTFs) without NIZK proofs. First, we formalize the definition of LTFs secure against AFL (AFLR-LTFs) and all-but-one variants (ABO). Then, we show how to realize this primitive in the split-state model. This primitive can be used to construct AFLR-CCA secure PKE scheme in the same way as the method of “CCA from LTFs” in traditional sense.


---

## Body

## 1. Introduction

In the past two decades, physical attacks which are capable of getting access to partial information of the secret state have become a serious threat to the security of cryptographic algorithms in practice. These attacks have moved far beyond the scope of traditional cryptography with an inherent assumption that no information of the secret key is leaked. Up till now, the branch of cryptography to treat this issue is highly motivated, which is called leakage resilient cryptography.The first step to address leakage resilience systematically is formalizing the leakage attack in the traditional security notion. There are already several models in the existing works which describe leakage in different ways. Akavia et al. [1] modeled the leakage as the bounded output of an arbitrary function of secret states (bounded/relative leakage). Naor and Segev [2] presented an alternative description to allow leakage without length restriction. They measured the leakage by the induced decrease of the minimum entropy of the secret (noisy leakage). Under these formulations, some leakage resilient primitives are successfully designed, including signature schemes [3–5] and key agreement protocol [6, 7].However, in the area of public key encryption (PKE), there is an inherent restriction in the security notion. Semantic security is always defined to be the indistinguishability of the challenge ciphertext issued by an adversary in a game with a challenger answering different types of queries from the adversary. The full-fledged definition for leakage resilience allows the adversary to query the leakage oracle after the challenge. This means an adversary could design its leakage function via the information of challenge ciphertext. For instance, in the bounded leakage model, an adversary could encode the challenge and decryption algorithm together to recover the whole message via leakage queries if its length is shorter than the bound. Most existing works, such as [1, 2, 8–10], beg this technical difficulty with a weaker security definition, which only admits prechallenge leakage queries. But in practice, after-the-fact leakage is really feasible because many cryptographic devices are portable so that the attack can be launched at any time.Halevi and Lin [11] made an effort to treat after-the-fact leakage (AFL) directly. As classic semantic security is impossible under postleakage attack, they choose to put another limitation instead of ignoring it. They require that the adversary can only get access to different parts of the secret via leakage independently, not as a whole. This “split-state” leakage was also defined and applied in the setting “computation leaks only” [12]. This restriction is meaningful because it is feasible to store secret fractions in different locations. They introduced the notion of “entropy leakage” to capture after-the-fact leakage. This concept states that the leakage should not be used to obtain more information than itself. This is an essential property for a postchallenge leakage. They showed that constructions from the hash proof system like that in [2] meet the requirement of security against entropy leakage. And they gave the first after-the-fact leakage resilient (AFLR) encryption scheme secure against chosen plaintext attack (CPA) by combining two instances of entropy leakage resilient schemes. Then, Li et al. presented identity-based encryption secure against postchallenge leakage attack [13]. Yang and Li considered this problem for the key exchange protocol [14].Since security against chosen ciphertext attack (CCA) is a well-accepted standard for encryption schemes, some subsequent works aimed to achieve this goal against AFL. Zhang et al. [15] followed the classic Naor–Yung paradigm [16] to give a construction with simulation sound noninteractive zero knowledge (NIZK) proof. Chakraborty et al. [17] presented a more efficient construction with true simulation extractable NIZK proof. Fujisaki et al. [18] considered the multichallenge setting as well as the leakage from randomness. There are indeed more techniques to obtain traditional CCA security, but few existing works secure against AFL attacks have been proposed.Lossy trapdoor functions: besides double encryption paradigm [16] and hash proof system [19], there is another approach to achieve CCA security, via a powerful primitive called lossy trapdoor functions (LTFs). Since its appearance [20], this primitive has been widely applied in many areas. The CCA secure encryption schemes based on LTFs get rid of the burden from NIZK proofs so that it is more efficient than those which need NIZK proofs. Also, LTFs have brilliant properties to extract statistical entropy from computational indistinguishability between two working modes. So LTFs have its nature to play an important role in leakage resilient cryptography. Some prior works already tried this way. Qin et al. [8] designed an invariant called the lossy filter to replace the universal-2 part in HPS-based schemes and achieved better leakage rate. More directly, Qin et al. [21] attempted to construct LR-LTFs, but their result can only be proven secure in a weaker model in which the adversary can get access to entire public key after leakage queries. Chen et al. proposed an advanced version of lossy function with its application in leakage resilience [22].


### 1.1. Our Contribution

In this work, we demonstrate that AFLR-LTFs and ABO invariants can be constructed in the split-state model and then can achieve AFLR-CCA security without NIZK proofs either. First, we formulate the notion of AFL secure LTFs. Then, we realize this primitive from AFL CPA secure PKE schemes. To overcome the technical difficulty that most randomness extractors and the underlying PKE schemes do not have homomorphic property which is essential for this use, we refine a AFLR randomness extractor from the BHHO PKE scheme [21, 23] with this property. Thus, with an AFLR-LTF and an AFL-ABO-LTF, we can follow the approach in [20] to achieve CCA security. Furthermore, our construction is easy to be used to construct chameleon AFL-ABO-LTFs [24] for a more efficient CCA secure realization.


### 1.2. Organization

The remaining part of this paper is organized as follows: the basic definitions and tools we need is shown in Section2. In Section 3, we build a step stone before arriving to the final step: a two-source extractor in the 2 split-state model. Then, we present AFLR-LTFs in Section 4 and an AFLR PKE scheme based on them in Section 5, respectively. The final scheme is interpreted in a black box manner from AFLR-LTFs. The security of the final scheme can be reduced to the security of AFLR-LTFs.


## 1.1. Our Contribution

In this work, we demonstrate that AFLR-LTFs and ABO invariants can be constructed in the split-state model and then can achieve AFLR-CCA security without NIZK proofs either. First, we formulate the notion of AFL secure LTFs. Then, we realize this primitive from AFL CPA secure PKE schemes. To overcome the technical difficulty that most randomness extractors and the underlying PKE schemes do not have homomorphic property which is essential for this use, we refine a AFLR randomness extractor from the BHHO PKE scheme [21, 23] with this property. Thus, with an AFLR-LTF and an AFL-ABO-LTF, we can follow the approach in [20] to achieve CCA security. Furthermore, our construction is easy to be used to construct chameleon AFL-ABO-LTFs [24] for a more efficient CCA secure realization.


## 1.2. Organization

The remaining part of this paper is organized as follows: the basic definitions and tools we need is shown in Section2. In Section 3, we build a step stone before arriving to the final step: a two-source extractor in the 2 split-state model. Then, we present AFLR-LTFs in Section 4 and an AFLR PKE scheme based on them in Section 5, respectively. The final scheme is interpreted in a black box manner from AFLR-LTFs. The security of the final scheme can be reduced to the security of AFLR-LTFs.


## 2. Preliminaries

### 2.1. ABO Lossy Trapdoor Functions

A collection of LTFs is a collection of publicly computable functions which are indexed by a set of public keys. Every public key is associated with a branch which is used to generate the key. There are two kinds of public keys. Functions indexed by one kind are injective, while functions indexed by the other have a smaller size of image than that of domain. We called the branch according to the former “injective branch” and the other “lossy branch.” “Lossy” means the image of the function working on these branches loses part of the information of the preimage. We use a generalized notion to incorporate exponential lossy branches. Let Bn denote a collection of branch sets and Bn∗ denote the corresponding collection of lossy branch sets. We recall the definition of ABO-LTFs [20] below. If Bn contains two elements only, it is just the standard LTF.Definition 1.
A collection ofn,k ABO-LTFs is composed of 3 probabilistic polynomial time (PPT) algorithms:Gabo: take λ∈ℕ and b∗∈Bλ as input and output s,td,Bλ∗, where s is a function index, td is its trapdoor, and Bλ∗ is the set of lossy branches that b∗∈Bλ∗.Fabo and Fabo−1: for any b∈Bλ/Bλ∗, Fabos,b,⋅ computes an injective function fs,b⋅ over the domain 0,1n and Fabo−1s,b,⋅ computes fs,b−1⋅. For any b∈Bλ∗, Fabos,b,⋅ computes a function fs,b⋅ over the domain 0,1n whose image size is at most 2k.
There are two security requirements for ABO-LTFs. Index indistinguishability: the ensembles⟵Gaboλ,b0∗ and s⟵Gaboλ,b1∗ are computationally indistinguishable. Lossy branch hidden: any PPT adversary A which takes s,b as input, where s,td,B∗⟵Gaboλ,b∗ has only a negligible probability to find a b′ such that b′≠b and b′∈B∗. And even b∈B∗, and the adversary could not find one either.


### 2.2. Randomness Extractor

#### 2.2.1. One Source

Definition 2.
A randomized algorithmExt1:K⟶0,1ν is a μ,ε extractor if for all X,Z that is distributed on K and H˜∞XZ≥μ, Z,S,Ext1X;S=Z,S,Uνs, where Uν is a uniform distribution over 0,1ν and S is called seed which is the coin of Ext1.
The parameters of the concrete extractor used need to satisfy the condition thatν≤μ−2log1/ε−1. Generally, pair-wise independent hash functions are used to realize extractors.


#### 2.2.2. Two Source

Definition 3.
A two-source extractor does not rely on random seeds but extracts randomness from two independent sources. A randomized algorithmExt2:K2⟶0,1ν is a μ,ε extractor if for all K1,K2,Z where K1andK2 are distributed on K and have minimum entropy μ conditioned on Z, Z,ExtK1,K2=Z,Uνs.


### 2.3. AFLR-CPA Secure PKE

#### 2.3.1. Entropy Leakage Resilient PKE

The definition of entropy leakage resilience stresses that the leakage after challenge cannot be amplified. This fact is captured by a simulator, which interacts with the adversary in an indistinguishable manner to the real setting. Formally, we first set some parameters:k is the minimum entropy that the message source M has, lpost denotes the leakage after challenge, and δ is an overhead parameter which comes from the statistical distance that the extractor deviates from uniform distribution.Definition 4.
A PKE schemeΠ is entropy leakage resilient if there exists a simulator Sim such that, for every PPT adversary A, the following two conditions hold:(1)
Mreal,ViewAΠ=cMsim,ViewASim(2)
H˜∞MsimViewASim≥k−lpost−δ


#### 2.3.2. After-the-Fact Leakage Resilience

Semantic security against AFL is defined by a game between a challenger and an adversary just the same as normal CPA game, except that the adversary is allowed to issue leakage query before and after challenge. The semantic security requires that the adversary can still not win with nonnegligible advantage in this setting. The CCA security is define analogously.An AFLR-CPA-secured PKE scheme in the 2 split-state model can be constructed via combination of two instances of an entropy leakage resilient PKE scheme and a two-source extractor. Specifically, given two entropy leakage resilient PKE schemesΠ1=Gen1,Enc1,Dec1 and Π2=Gen2,Enc2,Dec2, a semantic secure scheme against a posthallenge leakage can be defined as Gen=Gen1,Gen2,Encm;r1,r2=c1=Enc1r1,c2=Enc2r2,Ext2r1,r2⊕m=c,Decc=c⊕Ext2Dec1c1,Dec2c2. The security proof for this construction is in [11].


### 2.4. Homomorphism

A function is called homomorphism if the operation between elements in the domain preserves its structured functionality between elements in the range. For instance, let “+” denote the operation in the domain, “⋅” denote the operation in the range, and f:A⟶B be the function. The property can be represented as fx+y=fx⋅fy, which can induce fax=fxa.


### 2.5. DDH Assumption

Given a cyclic groupG with order q which is a big prime number, fandh are random elements in G and then f,h,fr,hr and f,h,fr,hr′ are computationally indistinguishable for randomly chosen r and r′. Following a hybrid argument, this result can be extended to vector situation: g,f1r,…,flr,h1r,…,hlr and g,f1r,…,flr,h1r′,…,hlr′ are computationally indistinguishable for randomly chosen r and r′.


### 2.6. 2 Split-State Model

This model is introduced in [11] to incorporate postchallenge leakage resilience. This model puts one more restriction than the ordinary security model against leakage attack that an adversary cannot issue leakage queries on the whole secret state but two separate parts. This means, instead of a leakage function f on sk, the adversary can only issue queries f1 on sk1 and f2 on sk2.


### 2.7. Notations

Throughout this paper, we build our concrete construction on quadratic residue subgroup of the cyclic group with orderN2. So we present all the parameter settings here. Let G denote a group of order N2 where N is a Blum integer, Gr the subgroup of G∗ with order p−1q−1/4, n the security parameter, λ the length of leakage, and set l=2+λ+2log1/ε/logN−3 for some negligible ε.Note that DDH assumption also holds inGr.Also, we define the multiple computation and exponential computation of a vector asxy=x1,…,xny1,…,yn=x1y1,…,xnyn and xr=x1,…,xnr=x1r,…,xnr.


## 2.1. ABO Lossy Trapdoor Functions

A collection of LTFs is a collection of publicly computable functions which are indexed by a set of public keys. Every public key is associated with a branch which is used to generate the key. There are two kinds of public keys. Functions indexed by one kind are injective, while functions indexed by the other have a smaller size of image than that of domain. We called the branch according to the former “injective branch” and the other “lossy branch.” “Lossy” means the image of the function working on these branches loses part of the information of the preimage. We use a generalized notion to incorporate exponential lossy branches. Let Bn denote a collection of branch sets and Bn∗ denote the corresponding collection of lossy branch sets. We recall the definition of ABO-LTFs [20] below. If Bn contains two elements only, it is just the standard LTF.Definition 1.
A collection ofn,k ABO-LTFs is composed of 3 probabilistic polynomial time (PPT) algorithms:Gabo: take λ∈ℕ and b∗∈Bλ as input and output s,td,Bλ∗, where s is a function index, td is its trapdoor, and Bλ∗ is the set of lossy branches that b∗∈Bλ∗.Fabo and Fabo−1: for any b∈Bλ/Bλ∗, Fabos,b,⋅ computes an injective function fs,b⋅ over the domain 0,1n and Fabo−1s,b,⋅ computes fs,b−1⋅. For any b∈Bλ∗, Fabos,b,⋅ computes a function fs,b⋅ over the domain 0,1n whose image size is at most 2k.
There are two security requirements for ABO-LTFs. Index indistinguishability: the ensembles⟵Gaboλ,b0∗ and s⟵Gaboλ,b1∗ are computationally indistinguishable. Lossy branch hidden: any PPT adversary A which takes s,b as input, where s,td,B∗⟵Gaboλ,b∗ has only a negligible probability to find a b′ such that b′≠b and b′∈B∗. And even b∈B∗, and the adversary could not find one either.


## 2.2. Randomness Extractor

### 2.2.1. One Source

Definition 2.
A randomized algorithmExt1:K⟶0,1ν is a μ,ε extractor if for all X,Z that is distributed on K and H˜∞XZ≥μ, Z,S,Ext1X;S=Z,S,Uνs, where Uν is a uniform distribution over 0,1ν and S is called seed which is the coin of Ext1.
The parameters of the concrete extractor used need to satisfy the condition thatν≤μ−2log1/ε−1. Generally, pair-wise independent hash functions are used to realize extractors.


### 2.2.2. Two Source

Definition 3.
A two-source extractor does not rely on random seeds but extracts randomness from two independent sources. A randomized algorithmExt2:K2⟶0,1ν is a μ,ε extractor if for all K1,K2,Z where K1andK2 are distributed on K and have minimum entropy μ conditioned on Z, Z,ExtK1,K2=Z,Uνs.


## 2.2.1. One Source

Definition 2.
A randomized algorithmExt1:K⟶0,1ν is a μ,ε extractor if for all X,Z that is distributed on K and H˜∞XZ≥μ, Z,S,Ext1X;S=Z,S,Uνs, where Uν is a uniform distribution over 0,1ν and S is called seed which is the coin of Ext1.
The parameters of the concrete extractor used need to satisfy the condition thatν≤μ−2log1/ε−1. Generally, pair-wise independent hash functions are used to realize extractors.


## 2.2.2. Two Source

Definition 3.
A two-source extractor does not rely on random seeds but extracts randomness from two independent sources. A randomized algorithmExt2:K2⟶0,1ν is a μ,ε extractor if for all K1,K2,Z where K1andK2 are distributed on K and have minimum entropy μ conditioned on Z, Z,ExtK1,K2=Z,Uνs.


## 2.3. AFLR-CPA Secure PKE

### 2.3.1. Entropy Leakage Resilient PKE

The definition of entropy leakage resilience stresses that the leakage after challenge cannot be amplified. This fact is captured by a simulator, which interacts with the adversary in an indistinguishable manner to the real setting. Formally, we first set some parameters:k is the minimum entropy that the message source M has, lpost denotes the leakage after challenge, and δ is an overhead parameter which comes from the statistical distance that the extractor deviates from uniform distribution.Definition 4.
A PKE schemeΠ is entropy leakage resilient if there exists a simulator Sim such that, for every PPT adversary A, the following two conditions hold:(1)
Mreal,ViewAΠ=cMsim,ViewASim(2)
H˜∞MsimViewASim≥k−lpost−δ


### 2.3.2. After-the-Fact Leakage Resilience

Semantic security against AFL is defined by a game between a challenger and an adversary just the same as normal CPA game, except that the adversary is allowed to issue leakage query before and after challenge. The semantic security requires that the adversary can still not win with nonnegligible advantage in this setting. The CCA security is define analogously.An AFLR-CPA-secured PKE scheme in the 2 split-state model can be constructed via combination of two instances of an entropy leakage resilient PKE scheme and a two-source extractor. Specifically, given two entropy leakage resilient PKE schemesΠ1=Gen1,Enc1,Dec1 and Π2=Gen2,Enc2,Dec2, a semantic secure scheme against a posthallenge leakage can be defined as Gen=Gen1,Gen2,Encm;r1,r2=c1=Enc1r1,c2=Enc2r2,Ext2r1,r2⊕m=c,Decc=c⊕Ext2Dec1c1,Dec2c2. The security proof for this construction is in [11].


## 2.3.1. Entropy Leakage Resilient PKE

The definition of entropy leakage resilience stresses that the leakage after challenge cannot be amplified. This fact is captured by a simulator, which interacts with the adversary in an indistinguishable manner to the real setting. Formally, we first set some parameters:k is the minimum entropy that the message source M has, lpost denotes the leakage after challenge, and δ is an overhead parameter which comes from the statistical distance that the extractor deviates from uniform distribution.Definition 4.
A PKE schemeΠ is entropy leakage resilient if there exists a simulator Sim such that, for every PPT adversary A, the following two conditions hold:(1)
Mreal,ViewAΠ=cMsim,ViewASim(2)
H˜∞MsimViewASim≥k−lpost−δ


## 2.3.2. After-the-Fact Leakage Resilience

Semantic security against AFL is defined by a game between a challenger and an adversary just the same as normal CPA game, except that the adversary is allowed to issue leakage query before and after challenge. The semantic security requires that the adversary can still not win with nonnegligible advantage in this setting. The CCA security is define analogously.An AFLR-CPA-secured PKE scheme in the 2 split-state model can be constructed via combination of two instances of an entropy leakage resilient PKE scheme and a two-source extractor. Specifically, given two entropy leakage resilient PKE schemesΠ1=Gen1,Enc1,Dec1 and Π2=Gen2,Enc2,Dec2, a semantic secure scheme against a posthallenge leakage can be defined as Gen=Gen1,Gen2,Encm;r1,r2=c1=Enc1r1,c2=Enc2r2,Ext2r1,r2⊕m=c,Decc=c⊕Ext2Dec1c1,Dec2c2. The security proof for this construction is in [11].


## 2.4. Homomorphism

A function is called homomorphism if the operation between elements in the domain preserves its structured functionality between elements in the range. For instance, let “+” denote the operation in the domain, “⋅” denote the operation in the range, and f:A⟶B be the function. The property can be represented as fx+y=fx⋅fy, which can induce fax=fxa.


## 2.5. DDH Assumption

Given a cyclic groupG with order q which is a big prime number, fandh are random elements in G and then f,h,fr,hr and f,h,fr,hr′ are computationally indistinguishable for randomly chosen r and r′. Following a hybrid argument, this result can be extended to vector situation: g,f1r,…,flr,h1r,…,hlr and g,f1r,…,flr,h1r′,…,hlr′ are computationally indistinguishable for randomly chosen r and r′.


## 2.6. 2 Split-State Model

This model is introduced in [11] to incorporate postchallenge leakage resilience. This model puts one more restriction than the ordinary security model against leakage attack that an adversary cannot issue leakage queries on the whole secret state but two separate parts. This means, instead of a leakage function f on sk, the adversary can only issue queries f1 on sk1 and f2 on sk2.


## 2.7. Notations

Throughout this paper, we build our concrete construction on quadratic residue subgroup of the cyclic group with orderN2. So we present all the parameter settings here. Let G denote a group of order N2 where N is a Blum integer, Gr the subgroup of G∗ with order p−1q−1/4, n the security parameter, λ the length of leakage, and set l=2+λ+2log1/ε/logN−3 for some negligible ε.Note that DDH assumption also holds inGr.Also, we define the multiple computation and exponential computation of a vector asxy=x1,…,xny1,…,yn=x1y1,…,xnyn and xr=x1,…,xnr=x1r,…,xnr.


## 3. Homomorphic and Leakage Resilient Randomness Extraction

In general, the keyed randomness extractor in leakage resilient setting is initiated with universal hash functions which do not incorporate homomorphic property. However, it is quite vital in our scheme. So we refine an extractor from a variant of BHHO scheme [21] which meets our requirement and leads to a construction of homomorphic two-source extractor.


### 3.1. One-Source Leakage Resilient Extractor

An extractor can be constructed as follows with abovementioned parameters:Gen: choose f1,f2,…,fl∈Gr. The evaluation key is set to be pk=N,f1,f2,…,fl.Ext: for any x=x1,x2,…,xl sampled from source ℤN−1/4, choose r∈ℤN−1/4, compute public random seed u1=f1r,u2=f2r,…,ul=flr, and f=∏i=1lfixi. Then, the extracted randomness is Extx;r=∏i=1luixi.Following [21], R is distributed negligibly close to uniform even subject to λ bits leakage and published f.Homomorphic property: we observe thatExtx;ra=Extx;ar. So this extractor has homomorphic random seed.


### 3.2. Two Sources in 2 Split-State Model

Given the same parameters as above, we can present our publicly computable two-source extractor in 2 split-state model.Gen: choose f1,f2,…,fl,h1,h2,…,hl∈Gr. The evaluation key is set to be pk=N,f1,f2,…,fl,h1,h2,…,hl.Ext2: for any x=x1,x2,…,xl and y=y1,y2,…,yl sampled from source ℤN−1/4, choose r∈ℤN−1/4, compute public random seed u1=f1r,u2=f2r,…,ul=flr, v1=h1r,v2=h2r,…,vl=hlr, and f=∏i=1lfixi and h=∏i=1lhiyi. Then, the extracted randomness is Ext2x,y=∏i=1luixiviyi.Theorem 1.
The construction above is alogN−3−λ,ε two-source extractor against λ bits leakage under DDH assumption.Proof.
We prove this theorem via hybrid argument through games between a challenger and an adversary as follows:Game0: the game proceeds as the real game. The challenger choosespk=N,f1,f2,…,fl,h1,h2,…,hl and responds queries from the adversary as the algorithm.Game1: in this game, the only change is that challenger computes the public random seed with two randomnessr and r′, which is u1=f1r,u2=f2r,…,ul=flr, v1=h1r′,v2=h2r′,…,vl=hlr′ and f=∏i=1lfixi and h=∏i=1lhiyi.Lemma 1.
The view of adversary is indistinguishable between Game0 and Game1 assuming DDH problem is hard.
Given a DDH instanceg1,g2,A=g1r,z, the challenger can simulate the game by letting f1=g1x1,f2=g1x2,…,fl=g1xl and h1=g2y1,h2=g2y2,…,hl=g2yl where x1,…,xl,y1,…yl are chosen randomly. In the challenge query, the challenger computes the public randomness as u1=Ax1,u2=Ax2,…,ul=Axl, v1=zy1,v2=zy2,…,vl=zyl. The challenger can answer leakage queries because it chooses secret key itself.
If the adversary can tell which game he is playing with nonnegligible advantage, then we can conclude thatz=g2r, which breaks the DDH assumption.Lemma 2.
The output is distributed negligibly close to uniform.
In Game1, the output can be seen as the multiplication of two-independent leakage resilient one-source extractors in the 2 split-state model. Forl=2+λ+2log1/ε/logN−3 where ε is negligible, the output is the multiplication of two variables which are both distributed ε close to uniform. Thus, it is at least distributed ε close to uniform itself.
Combing lemma 1 and lemma 2, the construction above is a two-source extractor againstλ bits leakage under DDH assumption in the 2 split-state model.


## 3.1. One-Source Leakage Resilient Extractor

An extractor can be constructed as follows with abovementioned parameters:Gen: choose f1,f2,…,fl∈Gr. The evaluation key is set to be pk=N,f1,f2,…,fl.Ext: for any x=x1,x2,…,xl sampled from source ℤN−1/4, choose r∈ℤN−1/4, compute public random seed u1=f1r,u2=f2r,…,ul=flr, and f=∏i=1lfixi. Then, the extracted randomness is Extx;r=∏i=1luixi.Following [21], R is distributed negligibly close to uniform even subject to λ bits leakage and published f.Homomorphic property: we observe thatExtx;ra=Extx;ar. So this extractor has homomorphic random seed.


## 3.2. Two Sources in 2 Split-State Model

Given the same parameters as above, we can present our publicly computable two-source extractor in 2 split-state model.Gen: choose f1,f2,…,fl,h1,h2,…,hl∈Gr. The evaluation key is set to be pk=N,f1,f2,…,fl,h1,h2,…,hl.Ext2: for any x=x1,x2,…,xl and y=y1,y2,…,yl sampled from source ℤN−1/4, choose r∈ℤN−1/4, compute public random seed u1=f1r,u2=f2r,…,ul=flr, v1=h1r,v2=h2r,…,vl=hlr, and f=∏i=1lfixi and h=∏i=1lhiyi. Then, the extracted randomness is Ext2x,y=∏i=1luixiviyi.Theorem 1.
The construction above is alogN−3−λ,ε two-source extractor against λ bits leakage under DDH assumption.Proof.
We prove this theorem via hybrid argument through games between a challenger and an adversary as follows:Game0: the game proceeds as the real game. The challenger choosespk=N,f1,f2,…,fl,h1,h2,…,hl and responds queries from the adversary as the algorithm.Game1: in this game, the only change is that challenger computes the public random seed with two randomnessr and r′, which is u1=f1r,u2=f2r,…,ul=flr, v1=h1r′,v2=h2r′,…,vl=hlr′ and f=∏i=1lfixi and h=∏i=1lhiyi.Lemma 1.
The view of adversary is indistinguishable between Game0 and Game1 assuming DDH problem is hard.
Given a DDH instanceg1,g2,A=g1r,z, the challenger can simulate the game by letting f1=g1x1,f2=g1x2,…,fl=g1xl and h1=g2y1,h2=g2y2,…,hl=g2yl where x1,…,xl,y1,…yl are chosen randomly. In the challenge query, the challenger computes the public randomness as u1=Ax1,u2=Ax2,…,ul=Axl, v1=zy1,v2=zy2,…,vl=zyl. The challenger can answer leakage queries because it chooses secret key itself.
If the adversary can tell which game he is playing with nonnegligible advantage, then we can conclude thatz=g2r, which breaks the DDH assumption.Lemma 2.
The output is distributed negligibly close to uniform.
In Game1, the output can be seen as the multiplication of two-independent leakage resilient one-source extractors in the 2 split-state model. Forl=2+λ+2log1/ε/logN−3 where ε is negligible, the output is the multiplication of two variables which are both distributed ε close to uniform. Thus, it is at least distributed ε close to uniform itself.
Combing lemma 1 and lemma 2, the construction above is a two-source extractor againstλ bits leakage under DDH assumption in the 2 split-state model.


## 4. AFLR-LTFs in 2 Split-State Model

In this section, we formulate the notion of AFLR-LTFs in the 2 split-state model and give concrete constructions of its own and ABO variants.


### 4.1. Definition

In this model, the secret is divided into 2 parts for storage and leakage attack can only get access to each part independently but not a function of whole state as before. This restriction provides the possibility to achieve AFL resilience.Definition 5.
A collection of 2 split-state ABO-LTFs are composed of specified algorithms as follows:Gabo: the generated trapdoor td is divided into two parts td1,td2, as well as the index s=s1,s2. The lossy branch set Bλ∗ is the same as before.Fabo−1: the inversion algorithm consists of two subroutines inv1 and inv2 which take two parts of the secret as input, respectively. And a combing subroutine f−1 takes as input the output of the two subroutines and outputs the preimage.
The security notion requires that index indistinguishability and lossy branch hidden hold even subject to leakage attack. Note that this requirement is just the same as AFLR PKE because the adversary could issue leakage queries to check the lossy branch after it sees the index.


### 4.2. A Homomorphic AFLR PKE Scheme in 2 Split-State Model

Homomorphism is essential to the underlying PKE schemes for LTFs and CCA security [25]. However, the generic construction in [11] does not incorporate this property. But [11] indicated that variants of hash proof system-based schemes are entropy leakage resilient. So we use the extractors mentioned in Section 3. We start from a basic scheme in [21] which is a variant of the BHHO scheme (and thus hash proof system-based scheme) and then construct the scheme we need via this one.The basic scheme is as follows:Gen: choose x1,x2,…,xl∈ℤN−1/4, f1,f2,…,fl∈Gr. Let f=∏i=1lfixi. The public key is set to be pk=N,f1,f2,…,fl,f, and the secret key is sk=x1,x2,…,xl.Enc: given the message m∈ℤN−1/4, Choose r∈ℤN−1/4 and compute c1=u1=f1r,u2=f2r,…,ul=flr,c2=fr1+Nm.Dec: given c=c1,c2. Compute K=∏i=1luixi and m=logc2/K.The construction is as follows:Given two instances of the basic entropy leakage schemeGen1,Enc1,Dec1 and Gen2,Enc2,Dec2, we define an AFLR PKE scheme in the 2 split-state model as follows:GEN: it includes two subroutines of Gen1,Gen2. The outputs are a public key pair pk=pk1,pk2 and a secret key pair sk=sk1,sk2.ENC: given a message m, it chooses randomness x1,x2,r as the input of two subroutines Enc1,Enc2 (we use the same randomness r in both encryption algorithm), and the ciphertext is computed as C=C1,C2,C3=c11,c21,c12,c22,Ext2x1,x21+Nm.DEC: m=logC3/Ext2Dec1C1,Dec2C2.Note: discrete logarithm in this case can be easily computed.Homomorphic property:ENCam;r=ENCam;ar.Theorem 2.
The construction above is a CPA secure scheme against1−O1sk bits prechallenge leakage and λ bits postchallenge leakage under DDH assumption in the 2 split-state model.Proof.
LetA denote the adversary. We prove the theorem via a sequence of hybrid experiments as follows.Game0: the challenger and the adversary proceed as the normal game. The challenger chooses the secret to generate public key and respond leakage queries.Game1: the only difference from Game0 happens in the challenge phase. The challenger chooses two independent randomnessr1,r2 for Enc1,Enc2 instead of the same one for both.Game2: in this game, the challenger generates half of public key by itself and runs the simulator of one-entropy leakage resilient instance to get the rest. In detail, the challenger executeGen to generate x1,x2,…,xl∈ℤN−1/4, pk1=f=∏i=1lfixi,f1,f2,…,fl and runs a simulator of another instance of the basic scheme to receive pk2=h,h1,h2,…,hl∈Gr. The public key is N,f1,f2,…,fl,h1,h2,…,hl,f,h. When the adversary issues a leakage query leak1,leak2, the challenger forward leak2 to the simulator and receives the answer. The answer can be merged with the output of leak1 which can be calculated by itself. In the challenge phase, the challenger chooses x2 and sends it to simulator to get ciphertext c12,c22. Then, it computes the challenge ciphertext by C=C1,C2,C3=c11,c21,c12,c22,Ext2x1,x21+Nm. When the adversary issues a postchallenge leakage query, the challenger handles like the way in the prechallenge phase.Game3: the challenger interacts withA via two entropy leakage resilient simulators. In this game, all the leakage queries are forwarded to simulators. The challenger computes Ext2x1,x21+Nm itself but receives the rest part of ciphertext from simulators.Lemma 3.
The views ofA in Game0 and Game1 are indistinguishable under DDH assumption.
This lemma is the same as Theorem 1.Lemma 4.
The views ofA in Game1 and Game2 are indistinguishable following Defintion 4.Lemma 5.
The views ofA in Game2 and Game3 are indistinguishable following Defintion 4.
The above two lemmas hold assuming the property of simulator.Lemma 6.
In Game3, the challenge ciphertext has distribution negligible close to uniform distribution against1−O1sk bits prechallenge leakage and λ bits postchallenge leakage.
This can be concluded by the property of the two-source extractor.


### 4.3. AFLR-LTFS

Following [25], AFLR-ABO-LTFS can be constructed as follows given a homomorphic AFLR-CPA secure encryption scheme GEN,ENC,DEC which we present above.PP: choose a branchb as the lossy branch and then run GEN and ENCb=C. The public key is pk,C, and the secret key is sk (we do not put b here because the security is not guaranteed with leaked b, and it can actually be obtained by decrypting C).Evaluationf: for any input x, choose an evaluation branch b′, fx=C/ENCb′x=ENCb−b′x. Output fx,b′.Inversionf−1: decrypt C to get b and then compute f−1=DECfx/b−b′.Security analysis: our construction achieves pre- and postchallenge leakage resilience more than [25]. Due to the use of AFLR encryption scheme as the building block, we can handle leakage query before and after challenge, which makes the proof similar to the one in [25]. So we omit the details here.Indistinguishability: adversary cannot tell the computation is lossy or not with nonnegligible advantage because the branch is encrypted with the AFLR encryption scheme. If the branch set consists only two elements 0 and 1, this construction can lead to a standard AFLR-LTF which will be used to achieve CCA security later. If the branch set contains many branches, the lossy one is also hidden from adversary.Lossiness: the output has entropy at mostlogN−2. So the lossiness is at least logN−logN−2=2. These results can be extended if we use Na as a module for the basic encryption scheme.


## 4.1. Definition

In this model, the secret is divided into 2 parts for storage and leakage attack can only get access to each part independently but not a function of whole state as before. This restriction provides the possibility to achieve AFL resilience.Definition 5.
A collection of 2 split-state ABO-LTFs are composed of specified algorithms as follows:Gabo: the generated trapdoor td is divided into two parts td1,td2, as well as the index s=s1,s2. The lossy branch set Bλ∗ is the same as before.Fabo−1: the inversion algorithm consists of two subroutines inv1 and inv2 which take two parts of the secret as input, respectively. And a combing subroutine f−1 takes as input the output of the two subroutines and outputs the preimage.
The security notion requires that index indistinguishability and lossy branch hidden hold even subject to leakage attack. Note that this requirement is just the same as AFLR PKE because the adversary could issue leakage queries to check the lossy branch after it sees the index.


## 4.2. A Homomorphic AFLR PKE Scheme in 2 Split-State Model

Homomorphism is essential to the underlying PKE schemes for LTFs and CCA security [25]. However, the generic construction in [11] does not incorporate this property. But [11] indicated that variants of hash proof system-based schemes are entropy leakage resilient. So we use the extractors mentioned in Section 3. We start from a basic scheme in [21] which is a variant of the BHHO scheme (and thus hash proof system-based scheme) and then construct the scheme we need via this one.The basic scheme is as follows:Gen: choose x1,x2,…,xl∈ℤN−1/4, f1,f2,…,fl∈Gr. Let f=∏i=1lfixi. The public key is set to be pk=N,f1,f2,…,fl,f, and the secret key is sk=x1,x2,…,xl.Enc: given the message m∈ℤN−1/4, Choose r∈ℤN−1/4 and compute c1=u1=f1r,u2=f2r,…,ul=flr,c2=fr1+Nm.Dec: given c=c1,c2. Compute K=∏i=1luixi and m=logc2/K.The construction is as follows:Given two instances of the basic entropy leakage schemeGen1,Enc1,Dec1 and Gen2,Enc2,Dec2, we define an AFLR PKE scheme in the 2 split-state model as follows:GEN: it includes two subroutines of Gen1,Gen2. The outputs are a public key pair pk=pk1,pk2 and a secret key pair sk=sk1,sk2.ENC: given a message m, it chooses randomness x1,x2,r as the input of two subroutines Enc1,Enc2 (we use the same randomness r in both encryption algorithm), and the ciphertext is computed as C=C1,C2,C3=c11,c21,c12,c22,Ext2x1,x21+Nm.DEC: m=logC3/Ext2Dec1C1,Dec2C2.Note: discrete logarithm in this case can be easily computed.Homomorphic property:ENCam;r=ENCam;ar.Theorem 2.
The construction above is a CPA secure scheme against1−O1sk bits prechallenge leakage and λ bits postchallenge leakage under DDH assumption in the 2 split-state model.Proof.
LetA denote the adversary. We prove the theorem via a sequence of hybrid experiments as follows.Game0: the challenger and the adversary proceed as the normal game. The challenger chooses the secret to generate public key and respond leakage queries.Game1: the only difference from Game0 happens in the challenge phase. The challenger chooses two independent randomnessr1,r2 for Enc1,Enc2 instead of the same one for both.Game2: in this game, the challenger generates half of public key by itself and runs the simulator of one-entropy leakage resilient instance to get the rest. In detail, the challenger executeGen to generate x1,x2,…,xl∈ℤN−1/4, pk1=f=∏i=1lfixi,f1,f2,…,fl and runs a simulator of another instance of the basic scheme to receive pk2=h,h1,h2,…,hl∈Gr. The public key is N,f1,f2,…,fl,h1,h2,…,hl,f,h. When the adversary issues a leakage query leak1,leak2, the challenger forward leak2 to the simulator and receives the answer. The answer can be merged with the output of leak1 which can be calculated by itself. In the challenge phase, the challenger chooses x2 and sends it to simulator to get ciphertext c12,c22. Then, it computes the challenge ciphertext by C=C1,C2,C3=c11,c21,c12,c22,Ext2x1,x21+Nm. When the adversary issues a postchallenge leakage query, the challenger handles like the way in the prechallenge phase.Game3: the challenger interacts withA via two entropy leakage resilient simulators. In this game, all the leakage queries are forwarded to simulators. The challenger computes Ext2x1,x21+Nm itself but receives the rest part of ciphertext from simulators.Lemma 3.
The views ofA in Game0 and Game1 are indistinguishable under DDH assumption.
This lemma is the same as Theorem 1.Lemma 4.
The views ofA in Game1 and Game2 are indistinguishable following Defintion 4.Lemma 5.
The views ofA in Game2 and Game3 are indistinguishable following Defintion 4.
The above two lemmas hold assuming the property of simulator.Lemma 6.
In Game3, the challenge ciphertext has distribution negligible close to uniform distribution against1−O1sk bits prechallenge leakage and λ bits postchallenge leakage.
This can be concluded by the property of the two-source extractor.


## 4.3. AFLR-LTFS

Following [25], AFLR-ABO-LTFS can be constructed as follows given a homomorphic AFLR-CPA secure encryption scheme GEN,ENC,DEC which we present above.PP: choose a branchb as the lossy branch and then run GEN and ENCb=C. The public key is pk,C, and the secret key is sk (we do not put b here because the security is not guaranteed with leaked b, and it can actually be obtained by decrypting C).Evaluationf: for any input x, choose an evaluation branch b′, fx=C/ENCb′x=ENCb−b′x. Output fx,b′.Inversionf−1: decrypt C to get b and then compute f−1=DECfx/b−b′.Security analysis: our construction achieves pre- and postchallenge leakage resilience more than [25]. Due to the use of AFLR encryption scheme as the building block, we can handle leakage query before and after challenge, which makes the proof similar to the one in [25]. So we omit the details here.Indistinguishability: adversary cannot tell the computation is lossy or not with nonnegligible advantage because the branch is encrypted with the AFLR encryption scheme. If the branch set consists only two elements 0 and 1, this construction can lead to a standard AFLR-LTF which will be used to achieve CCA security later. If the branch set contains many branches, the lossy one is also hidden from adversary.Lossiness: the output has entropy at mostlogN−2. So the lossiness is at least logN−logN−2=2. These results can be extended if we use Na as a module for the basic encryption scheme.


## 5. Constructions of AFLR-CCA Secure PKE

AFLR-CCA security can be obtained in a classic way with a standard AFLR-LTF, an AFLR-ABO-LTF, and an unforgeable one-time signature scheme. But we prefer another approach via chameleon AFLR-ABO-LTFs. Chameleon ABO-LTFs are introduced in [24] which can avoid using one-time signature. In this variant of LTFs, the lossy set is denoted as a line rather than points to incorporate exponential lossy branches. So we give the construction of chameleon AFLR-ABO-LTFs first.


### 5.1. Chameleon AFLR-ABO-LTFs

PP: choosed,e,j∈ℤN−1/4 and then run GEN and ENCd=D, ENCe=E, and ENCj=J. The public key is pk,D,E,J, and the secret key is skCH.
EvaluationfCH: for any input x, choose an evaluation branch xd,xe, fCHx=DxdExeJx=ENCdxd+exe+jx. Output fCHx,xd,xe.
InversionfCH−1: decrypt D,E,J to get d,e,j and then compute fCH−1=DECfCHx/dxd+exe+j.The lossy branches are all pairsxd,xe that satisfy the condition dxd+exe+j=0.


### 5.2. AFLR-CCA Secure PKE Scheme

We can build our AFLR-CCA secure encryption schemeG,E,D by combining standard AFLR-LTFs and chameleon AFLR-ABO-LTFs as [24].G: first generate public parameters for LTF and chameleon ABO-LTF with an AFLR-CPA secure PKE scheme Gen,Enc,Dec. Let H be a universal hash function and h a collision-resistant hash function. The public key is pk,pkCH,H,h,A=Enc1,D=Encd,E=Ence,J=Encj where d,e,j are randomly chosen and independently encrypted. Thus, the standard LTF fx=Ax and chameleon AFLR-ABO-LTF fCHx;xd,xe=DxdExeJx are well defined. The secret key is sk,skCH.E: for a message m, choose a randomness x, evaluation branch b randomly, and compute C=c0=Hx⊕m,c1=fx,c2=fCHx;b,hc0,c1,b.D: given a ciphertext C=c0,c1,c2,b, compute x=f−1c1 and check whether c2=fCHx;b,hc0,c1. If the output is not ⊥, then output m=c0⊕Hx.Theorem 3.
Given AFLR-LTFs and chameleon AFLR-ABO-LTFs, the construction above is an AFLR-CCA secure PKE scheme in the 2 split-state model againstλ bits after-the-fact leakage.Proof sketch:.
the case without leakage attack are proven secure in [24]. The proof goes with a sequence of indistinguishable games between challenger and adversary. The first step is to reject all the decryption queries with lossy computation by chameleon ABO-LTF. Then, change the working mode of LTF to be lossy and the decryption queries can be responded by chameleon LTF on injective branches. Finally, CCA security is achieved statistically with appropriate parameter.
As the underlying AFLR primitives we propose in Sections4 and 5.1 can handle leakage queries in both pre- and postchallenge phase, we can preserve AFLR security if we use these primitives instead of ones in ordinary case naturally. Readers can check every step and see the proof strategy above can still work with additional leakage attack.


## 5.1. Chameleon AFLR-ABO-LTFs

PP: choosed,e,j∈ℤN−1/4 and then run GEN and ENCd=D, ENCe=E, and ENCj=J. The public key is pk,D,E,J, and the secret key is skCH.
EvaluationfCH: for any input x, choose an evaluation branch xd,xe, fCHx=DxdExeJx=ENCdxd+exe+jx. Output fCHx,xd,xe.
InversionfCH−1: decrypt D,E,J to get d,e,j and then compute fCH−1=DECfCHx/dxd+exe+j.The lossy branches are all pairsxd,xe that satisfy the condition dxd+exe+j=0.


## 5.2. AFLR-CCA Secure PKE Scheme

We can build our AFLR-CCA secure encryption schemeG,E,D by combining standard AFLR-LTFs and chameleon AFLR-ABO-LTFs as [24].G: first generate public parameters for LTF and chameleon ABO-LTF with an AFLR-CPA secure PKE scheme Gen,Enc,Dec. Let H be a universal hash function and h a collision-resistant hash function. The public key is pk,pkCH,H,h,A=Enc1,D=Encd,E=Ence,J=Encj where d,e,j are randomly chosen and independently encrypted. Thus, the standard LTF fx=Ax and chameleon AFLR-ABO-LTF fCHx;xd,xe=DxdExeJx are well defined. The secret key is sk,skCH.E: for a message m, choose a randomness x, evaluation branch b randomly, and compute C=c0=Hx⊕m,c1=fx,c2=fCHx;b,hc0,c1,b.D: given a ciphertext C=c0,c1,c2,b, compute x=f−1c1 and check whether c2=fCHx;b,hc0,c1. If the output is not ⊥, then output m=c0⊕Hx.Theorem 3.
Given AFLR-LTFs and chameleon AFLR-ABO-LTFs, the construction above is an AFLR-CCA secure PKE scheme in the 2 split-state model againstλ bits after-the-fact leakage.Proof sketch:.
the case without leakage attack are proven secure in [24]. The proof goes with a sequence of indistinguishable games between challenger and adversary. The first step is to reject all the decryption queries with lossy computation by chameleon ABO-LTF. Then, change the working mode of LTF to be lossy and the decryption queries can be responded by chameleon LTF on injective branches. Finally, CCA security is achieved statistically with appropriate parameter.
As the underlying AFLR primitives we propose in Sections4 and 5.1 can handle leakage queries in both pre- and postchallenge phase, we can preserve AFLR security if we use these primitives instead of ones in ordinary case naturally. Readers can check every step and see the proof strategy above can still work with additional leakage attack.


## 6. Efficiency in Practice

The generic constructions in previous works [15, 17] need NIZK system to prove the language that two encryptions contain the same plaintext. In practice, NIZK proofs secure in standard model concerns the Groth–Sahai system [26] which suffers from heavy burden of computations via bilinear mappings. Specifically, proving a commitment of exponential which is only a step stone for proving equal plaintext requires 4 group elements and verified by 9 pairing operations. The cost of NIZK for same plaintext may be dozens of group elements and pairing operations. That is why existing works did not even give concrete construction for NIZK-based solutions. This situation is just like “two-key” generic construction in [16] which is convincing but not practical until [19] appeared. Our construction comes from a leakage resilient extension of [19] and achieves CCA security against postleakage without NIZK just like Cramer and Shoup [19] did in classic environment.Specifically, the evaluation key in our scheme can be processed in precomputation and the encryption algorithm works by8l exponential computations. If we want to achieve 80 bit security (ε=2−80) with 1024 bit N, l=2+λ+160/7 against λ bit leakage. If we want to encrypt longer plaintext, we can use larger modulus like Na,a>2.We implement our scheme to evaluate its efficiency, which is based on JPBC 2.0.0 library (http://gas.dia.unisa.it/projects/jpbc/index.html#.VTDrLSOl_Cw) and coding language Java. We select type A1 pairings are constructed on the curve y2=x3+x over the field ℤN for some Blum integer N. The following experiments are based on Dell laptop (Windows 7 operation system with Intel(R) Core(TM) i5-2450M CPU 2.50 GHz, 4.00 GB RAM, and 500 G disk storage). The time cost in real-world experiment for one encryption is 0.042 s with 1024 bit N.


## 7. Conclusion and Future Direction

Our work removes the use of zero knowledge proofs which is not efficient in the construction of AFLR-CCA secure PKE encryption schemes via the approach of lossy trapdoor functions. We also present instances of AFLR-LTF and its variants. An interesting open problem is finding more efficient PKE schemes with both homomorphic property and leakage resilience.



---

*Source: 8357241-2019-10-31.xml*