Constructions Of Lossy Trapdoor Functions And Applications

Lossy trapdoor function was proposed by Peikert and Waters(STOC 2008).Lossy trap-door function has two kinds of functions.The first type is injective,i.e.,trapdoor functions.The second type is lossy,i.e.,the image size of these functions is smaller than their preim-age size.In addition,LTDF requires functions chosen from the two types are computational indistinguishable.Peikert and Waters also proposed a general definition of lossy trapdoor function:All-But-One(ABO)lossy trapdoor function.ABO lossy trapdoor function is lossy trapdoor function that are parametrized with branches,and there is only one branch is lossy,and others are injective.Peikert and Waters showed that lossy trapdoor function,ABO lossy trapdoor function and a strongly unforgeable one-time signature scheme imply public key encryption scheme against chosen ciphertext attack.All-but-many(ABM)lossy trapdoor function is generalizations of lossy trapdoor func-tion and ABO lossy trapdoor function introduced by Hofheinz(Eurocrypt 2012).ABM lossy trapdoor functions are lossy trapdoor functions that are parametrized with tags.The tag set is divided into two disjoint subsets:injective tag subset and lossy tag subset,where injective tags lead to invertible functions and lossy tags lead to lossy functions.ABM lossy trapdoor functions are more powerful than lossy trapdoor functions.Hofheinz proved that ABM-LTDFs imply selective opening chosen-ciphertext secure public key encryption scheme.Lossy Trapdoor Functions have a number of applications in cryptography such as con-structing collision resistant hash function,chosen plaintext secure and chosen ciphertext se-cure public key encryption,oblivious transfer schem,and so on.Specially,Kakvi and Kiltz(ASIACRYPT 2012)showed that the Full Domain Hash signature scheme(FDH)has a tight security reduction based on the the lossy trapdoor function.However,the security reduction of FDH was non-tight with losing a factor qh before.Kiltz,O'Neill and Smith(CRYPTO 2010)showed that RSA-OAEP is indistinguishability under chosen-plaintext attacks(IND-CPA)in the standard model from the lossiness of RSA trapdoor functions,and before that the security of RSA-OAEP was proved under the random oracle.Existing lossy trapdoor functions were constructed based on decisional Diffie-Hellman(DDH)assumption,learning with errors(LWE)assumptions,quadratic residuosity assump-tion,decisional composite residuosity(DCR)assumption,?-Hiding assumption,and so on.Existing ABM lossy trapdoor functions were constructed based on parings,DCR assump-tion and LWE assumption.In this paper,we propose lossy trapdoor function based on improve RSA trapdoor func-tion,constructions of chameleon All-But-One lossy trapdoor function and identity-based lossy trapdoor function,constructions of All-But-Many lossy trapdoor function,and appli-cations.The results as follows.1.We construct lossy trapdoor functions based on improved RSA lossy trapdoor func-tion.Our construction is under quadratic residuosity assumption.Compared with the traditional RSA lossy trapdoor function,our scheme is not limited by the size of the exponential e(when exponential e<N1/4,RSA trapdoor function is lossy).We con-struct a Full Domain Hash signature scheme based on improved RSA lossy trapdoor function,and we propose a tight security reduction.We also construct a blind signature scheme and we show that the scheme has a tight L-OMF security reduction.2.we construct a generic chameleon ABO lossy trapdoor functions,and our construction is based on ABO lossy trapdoor functions and chameleon hash functions.By the gener-ic construction,we propose a concrete construction based on improved RSA trapdoor function.We correspond the branch of the chameleon ABO lossy trapdoor function to the identity id of identity-based cryptography.We construct a identity-based lossy trapdoor function under the chameleon ABO lossy trapdoor function.Our construction is based on the DBDH-based lossy trapdoor function of Boyen and Waters.At last,we construct a identity-based encryption scheme,and show that it is IND-ID-CPA secure.3.We construct a ABM lossy trapdoor function under decisional RSA subgroup assump-tion.Our scheme is based on Groth's DRSA-based CPA secure public key encryption scheme.ABM lossy trapdoor function needs to meet two main security properties.The first one is indistinguishability,i.e.,it is indistinguishable between a lossy tag and a random tag.In our scheme,tags are constructed under the Groth'CPA-secure PKE scheme.Due to the indistinguishability of Groth' ciphertext,we can substitute the lossy tag for a random tag.The second property is evasiveness,i.e.,it is difficult to compute a lossy tag.We make our scheme to meet this property by using a unforge-ability under chosen message attacks(UF-CMA)secure signature scheme,i.e.,the tag the adversary outputs will be interpreted as a forged signature.We also propose a a generic construction of ABM lossy trapdoor function.Our construction is based on ho-momorphic public key encryption scheme.By the generic construction,we construct a concrete ABM lossy trapdoor function under the DCR assumption.