Fuzzy Extractor:Constructions And Security Proofs

Uniformly random and precisely reproducible string plays a vital role in cryptography.For example,the secret keys in cryptographic schemes are presumed to be uniformly distributed.At the same time,random strings are always demanded in the algorithms of cryptographic schemes.In real life,random sources outputting such good strings are rare.However,there do exist plenty of imperfect noisy random sources,like biometric information.These sources have enough entropy but they are not uniformly random.Upon different samplings from these source,the sampling results are not identical and suffer from some noises.How to transform the samplings from such imperfect noisy random sources into uniformly random and precisely reproducible strings is just the concern of fuzzy extractor.Fuzzy extractor can distill a uniform string from a noisy random source.When a fuzzy extractor distills a random string R from a source,it will output a public helper string P,which will help R to be precisely reproduced later.In practice,there still exist some problems limiting the usability of fuzzy extractor.Fuzzy extractor does not consider active adversaries.In order to make R precisely reproducible,the public helper string P should be saved carefully.If an active adversary modifies P,then the user may get a wrong R'.With a wrong key R',a cryptographic system may lead to a great loss.Fuzzy extractor can not guarantee the security of multiple extractions from the same noisy random source.Fuzzy extractor can only guarantee the security of one extraction from a noisy source.However,if users can only make one extraction from a noisy random source(for example,biometric information),this may lead to a huge waste of noisy random sources.In order to solve the problems above,robust fuzzy extractor and reusable fuzzy extractor were proposed.Robust fuzzy extractor guarantees that any modification of P will be detected;reusable fuzzy extractor guarantees the security of multiple extractions from one noisy random source.Although many constructions of robust fuzzy extractor and reusable fuzzy extractor were presented,there are still some problems to be solved.(1)The entropy loss of existing robust fuzzy extractors is too big.This may make the extracted random string too short for usage.(2)As far as we know,existing fuzzy extractors are either based on random oracle or non-standard assumption,or only support a sub-linear fraction of errors.There is no reusable fuzzy extractor,which is based on standard assumption and supports a linear fraction of errors.(3)There is no fuzzy extractor considers robustness and reusability simultaneously,needless to say robustly reusable fuzzy extractor in the standard model.(4)With the rapid development of quantum technology,traditional cryptographic schemes from number-theoretic hard problems may not secure any more.The LWE problem is a promising quantum resistant problem.However,the existing LWE-based fuzzy extractor can only tolerate a logarithmic fraction of errors.What,s more,no LWE-based robustly reusable fuzzy extractor exists at all.In this paper,we focus on the problems above and obtain the following results·We proposed a robust fuzzy extractor which can distill a much longer random string.We introduced the notion of computational robust fuzzy extractor by re-laxing information-theoretical security to computational security.We gave a simple construction of computational robust fuzzy extractor based on the hardness of Sub-group Membership Problem and Discrete Logarithm assumption.Thanks to computa-tional security,our construction obtains much longer extracted uniform string than the nearly optimal(information-theoretically)robust fuzzy extractor proposed by Cramer et al.(EUROCRYPT,2008).·We proposed the first reusable fuzzy extractor tolerating a linear fraction of errors from a standard assumption.We constructed a reusable fuzzy extractor tolerating a linear fraction of errors,with security tightly reduced to the Decisional Diffie-Hellman(DDH)assumption in the standard model.Our construction is simple and efficient.Only two group operations and an evaluation of a hash function are added compared with the traditional construction of non-reusable fuzzy extractors.·We proposed the first two generic constructions of robustly reusable fuzzy extractor.We formalized robustly reusable fuzzy extractor(rrFE)whose security notions include both reusability and robustness in the computational setting.We proposed two generic constructions of rrFE.1)We proposed a new primitive called symmetric key encapsulation mechanism(SKEM)and defined the key-shift security for SKEM.With a SKEM,a homomorphic secure sketch,a homomorphic extractor,and a homomorphic lossy algebraic filter as building blocks,we proposed a generic construction of rrFE.By instantiating the underlying building blocks,we obtain the first rrFE based on standard assumptions.Moreover,it supports a linear fraction of errors.2)We proposed another generic construction of rrFE from an auxiliary-input authenti-cated encryption,a family of homomorphic universal hash functions and a homomor-phic secure sketch with linearity property.By instantiating the underlying building blocks,we obtain the first rrFE from the DDH assumption without pairing.Besides,it is efficient and tolerates a linear fraction of errors.·We proposed the first reusable fuzzy extractor tolerating a linear fraction of errors from the LWE assumption and the first robustly reusable fuzzy extractor from the LWE assumption.We proposed a reusable fuzzy extractor from the LWE assumption.Furthermore,we designed a generic paradigm for constructing robustly reusable fuzzy extractor.1)We constructed a reusable fuzzy extractor from the LWE assumption.Our reusable fuzzy extractor provides resilience to a linear fraction of errors.Moreover,our con-struction is simple and efficient and imposes no special requirement on the statistical structure of the multiple readings of the source.2)We proposed another novel generic construction of rrFE from a homomorphic secure sketch with linearity property,a family of homomorphic universal hash functions and a unique-input key-shift secure pseudorandom function.By instantiating the underlying building blocks,we obtain the first rrFE from the LWE assumption.