Afuzzy extractor can extract an almost uniformrandom string from a noisy source with enough entropy such as biometric data.To reproduce an identical key from repeated readings of biometric data,the fuzzy extractor gen...Afuzzy extractor can extract an almost uniformrandom string from a noisy source with enough entropy such as biometric data.To reproduce an identical key from repeated readings of biometric data,the fuzzy extractor generates a helper data and a random string from biometric data and uses the helper data to reproduce the random string from the second reading.In 2013,Fuller et al.proposed a computational fuzzy extractor based on the learning with errors problem.Their construction,however,can tolerate a sub-linear fraction of errors and has an inefficient decoding algorithm,which causes the reproducing time to increase significantly.In 2016,Canetti et al.proposed a fuzzy extractor with inputs from low-entropy distributions based on a strong primitive,which is called digital locker.However,their construction necessitates an excessive amount of storage space for the helper data,which is stored in authentication server.Based on these observations,we propose a new efficient computational fuzzy extractorwith small size of helper data.Our scheme supports reusability and robustness,which are security notions that must be satisfied in order to use a fuzzy extractor as a secure authentication method in real life.Also,it conceals no information about the biometric data and thanks to the new decoding algorithm can tolerate linear errors.Based on the non-uniform learning with errors problem,we present a formal security proof for the proposed fuzzy extractor.Furthermore,we analyze the performance of our fuzzy extractor scheme and provide parameter sets that meet the security requirements.As a result of our implementation and analysis,we show that our scheme outperforms previous fuzzy extractor schemes in terms of the efficiency of the generation and reproduction algorithms,as well as the size of helper data.展开更多
The existing solutions to keyword search in the cloud can be divided into two categories： searching on exact keywords and searching on error-tolerant keywords. An error-tolerant keyword search scheme permits to make ...The existing solutions to keyword search in the cloud can be divided into two categories： searching on exact keywords and searching on error-tolerant keywords. An error-tolerant keyword search scheme permits to make searches on encrypted data with only an approximation of some keyword. The scheme is suitable to the case where users＇ searching input might not exactly match those pre-set keywords. In this paper, we first present a general framework for searching on error-tolerant keywords. Then we propose a concrete scheme, based on a fuzzy extractor, which is proved secure against an adaptive adversary under well-defined security definition. The scheme is suitable for all similarity metrics including Hamming distance, edit distance, and set difference. It does not require the user to construct or store anything in advance, other than the key used to calculate the trapdoor of keywords and the key to encrypt data documents. Thus, our scheme tremendously eases the users＇ burden. What is more, our scheme is able to transform the servers＇ searching for error-tolerant keywords on ciphertexts to the searching for exact keywords on plaintexts. The server can use any existing approaches of exact keywords search to search plaintexts on an index table.展开更多
基金supported by Institute of Information&communications Technology Planning&Evaluation(IITP)grant funded by the Korea government(MSIT)(No.2022-0-00518,Blockchain privacy preserving techniques based on data encryption).
文摘Afuzzy extractor can extract an almost uniformrandom string from a noisy source with enough entropy such as biometric data.To reproduce an identical key from repeated readings of biometric data,the fuzzy extractor generates a helper data and a random string from biometric data and uses the helper data to reproduce the random string from the second reading.In 2013,Fuller et al.proposed a computational fuzzy extractor based on the learning with errors problem.Their construction,however,can tolerate a sub-linear fraction of errors and has an inefficient decoding algorithm,which causes the reproducing time to increase significantly.In 2016,Canetti et al.proposed a fuzzy extractor with inputs from low-entropy distributions based on a strong primitive,which is called digital locker.However,their construction necessitates an excessive amount of storage space for the helper data,which is stored in authentication server.Based on these observations,we propose a new efficient computational fuzzy extractorwith small size of helper data.Our scheme supports reusability and robustness,which are security notions that must be satisfied in order to use a fuzzy extractor as a secure authentication method in real life.Also,it conceals no information about the biometric data and thanks to the new decoding algorithm can tolerate linear errors.Based on the non-uniform learning with errors problem,we present a formal security proof for the proposed fuzzy extractor.Furthermore,we analyze the performance of our fuzzy extractor scheme and provide parameter sets that meet the security requirements.As a result of our implementation and analysis,we show that our scheme outperforms previous fuzzy extractor schemes in terms of the efficiency of the generation and reproduction algorithms,as well as the size of helper data.
基金supported by the National Natural Science Foundation of China under Grant Nos.61272436,61003232 and 61272404the Natural Science Foundation of Guangdong Province of China under Grant No.10351806001000000
文摘The existing solutions to keyword search in the cloud can be divided into two categories： searching on exact keywords and searching on error-tolerant keywords. An error-tolerant keyword search scheme permits to make searches on encrypted data with only an approximation of some keyword. The scheme is suitable to the case where users＇ searching input might not exactly match those pre-set keywords. In this paper, we first present a general framework for searching on error-tolerant keywords. Then we propose a concrete scheme, based on a fuzzy extractor, which is proved secure against an adaptive adversary under well-defined security definition. The scheme is suitable for all similarity metrics including Hamming distance, edit distance, and set difference. It does not require the user to construct or store anything in advance, other than the key used to calculate the trapdoor of keywords and the key to encrypt data documents. Thus, our scheme tremendously eases the users＇ burden. What is more, our scheme is able to transform the servers＇ searching for error-tolerant keywords on ciphertexts to the searching for exact keywords on plaintexts. The server can use any existing approaches of exact keywords search to search plaintexts on an index table.
