Constructions Of Lossy Trapdoor Function And Reduce Of The Keys

Diffie and Hellman [15] proposed the one way trapdoor function in1976. And one way trapdoor function is publicly accepted as the cryptography prim-itive for constructing lots of primitives like PSRG[23], zero knowledge proof[23] and somatic security schemes. But we know that sematic security is not enough. Nowadays security against adaptive chosen ciphertext attack (CCA)[24] is widely accepted as the right notion of security for public key encryption. It is simple to construct semantie security scheme based on one way trapdoor function while not so simple to construct CCA security scheme. Actually con-structions of CCA scheme nowadays base on noninteractive zero knowledge proof which is complex. Moreover not all the complexity assumption can be used to construct one way trapdoor function. There are only known con-structions based on factoring assumption and discrete logarithm assumptions. It is unknown how to construct one way trapdoor function based on lattice assumptions.Chris Peikert and Brent Waters [31] proposed a new conception-Lossy trapdoor functions-in cryptography in2008. Lossy trapdoor functions(LTF) can be constructed from more complexity assumptions, especially lattice as-sumptions, and can be used to construct classic one way trapdoor functions. Lossy trapdoor functions imply lots of primitives such as collision-resistant hash functions, and oblivious transfer [31], chosen cipliertext secure public-key encryption [31], deterministic public-key encryption [5], OAEP-based public-key encryption [26], public-key encryption for protecting against bad random- ness [3], security against selective opening attacks [2], and non-interactive universally-composable string commitments [30]. A collection of lossy trap-door functions consists of two families of functions. Functions in the first family are injective and can be inverted using a trapdoor, while functions in the second are lossy, meaning that the size of their image is significantly smaller than the size of their domain.Chris Peikert and Brent Waters[31] proposed two constructions based on DDH assumption and Learn with Erro (LWE) assumption. But the two con-structions are not efficient as the function index’s size is about O(λ2). The function index is usually public keys in scheme. Freeman etc.[29] proposed more constructions of lossy trapdoor functions based on quadratic residuosity assumption, composite residuosity assumption and k-linear assumption. In the construction based on k-linear assumption. they define a computation of ma-trix on the exponent. But this construction is also not efficient as the function index and trapdoor’s size is O(λ2). Xavier Boyen etc.[8] shrink the function index of Peikert’s DDH construction from O(λ2) to O(λ) utilize common ref-erence string (CRS) and paring. The security of the reduced scheme based on the decisional bilinear Diffie Hellman assumption as the decisional Diffie Hellman assumption doesn’t hold on bilinear group.All the constructions above based on discrete logarithm related assump-tion are not efficient. This paper consider how to construct more efficient LTF with small function index and trapdoors. This paper have the following three main contributions:Firstly, we propose a new construction of LTF based on decisional linear Diffie Hellman (DLDH) assumption which is a generalization of Peikert and Waters’method and we reduce the size of the function index utilize pairing and CRS. Although Freeman etc.[29] have proposed a general construction of LTF based on DLDH, their construction’s function index is large and can not be reduced. Our construction’s function index can be reduced from O(λ2) to O(λ). The formal description is given in Chapter3.Secondly,In Chapter4, we general the conception of Hash Proof System add the bilinear map in the system and get Bilinear Hash Proof System. We propose the general construction of LTF in the CRS model based on Bilinear Hash Proof System with function index and trapdoor about (?)(λ).Thirdly, In Chapter5, we propose a new construction of LTF based on DDH-like assumption which is proposed by Ronald Cramer etc.[10]. While standard DDH is based on encoding elements of Fq’in the exponent’of el-ements in the group, they put in the exponent elements of the finite fields Rf=Fq[X]/(f) where f can be any degree d irreducible polynomial. We also propose DLDH-like assumption and prove that it is a weaker assumption than DDH-like and DLDH and propose a new construction of LTF based on DLDH-like assumption. Our constructions of this Chapter is much efficient than all the known constructions based discrete logarithm related assumptions, with only O(λ) number of function index and trapdoorsAnd at last we compare the efficiency and complexity of these construc-tions.