Original Title: [Network Security Think Tank] Fuzzy Extractor and Its Application This paper introduces the definition, application and limitation of fuzzy extractor. The limitations of the fuzzy extractor are that it can only extract the entropic information source once, and that the public information is tampered with, which will lead to the generation of the wrong key. Therefore, this paper introduces the reusable robust fuzzy extractor, and gives its definition, construction, and points out its potential application scenarios. Introduction Uniformly distributed random variables are widely used in cryptography. For example, the most important element in a cryptosystem is the key, and the security of a cryptosystem depends on the uniform randomness of the key. In addition, for public key encryption or digital signature schemes, the encryption algorithm or signature algorithm also requires the participation of random numbers to ensure the CPA security or unforgeability of the encryption algorithm. An important question is: how to generate uniformly distributed random bits? A source that generates random bits with a certain entropy is called a Randomness Source. If the string generated by the "random source" is not only "uniformly distributed" in the key space, but also "accurately reproduced". The "random source" can then be used to generate the encryption and decryption keys for the cryptographic algorithm. However, in real life, there are almost no such random sources that are uniformly random and accurately reproduced. In reality, there are many random sources with noise, which have high (minimum) entropy, but are not uniformly random, and each sampling result is similar, but there are some small deviations (noise). For example Human biological information, such as fingerprint, voiceprint, iris, etc.; Noise of electronic components (unclonable function); Quantum information. Can we cryptographically transform these noisy random sources into good random sources that produce random bits that are "uniformly distributed" and "exactly reproduced"? If so, then these random sources can be used by us and provide an endless stream of reproducible random numbers for the cryptosystem. Fuzzy extractor In the past two decades, many cryptographers have devoted themselves to the study of how to use cryptographic techniques to make noisy random sources to generate uniformly random and accurately reproducible strings. Definition of Fuzzy Extractor In 2004, Dodis et al. Proposed the concept of fuzzy extractor to solve this problem. The fuzzy extractor FE = (Gen, Rep) has two algorithms, the generative algorithm and the regenerative algorithm. The extractor is described as follows, see Figure 1. Gen (P,R). Generation algorithm Gen inputs a string w (one sample of a random source of noise) and outputs a string R and a public helper string P; Rep(w',P) R'. Regeneration algorithm input W ' (another sample of a random source of noise) and a public helper string P, a string R' is output. Correctness: The correctness requirement is that if the distance between the two samples w and w 'is close enough, then R' = R, that is, R can be reproduced accurately; Security: The security requirement is that if the random source has enough entropy, then R is uniformly random. Expand the full text The fuzzy extractor construct propose by Dodis et al. Depends on two component, namely an (ordinary, not fuzzy) extractor and a secure sketch. The extractor [13] can convert non-uniform strings into uniform strings, which can be implemented using universal functions, while the secure sketch is dedicated to error correction, which can be implemented using linear error correction codes. Application of Fuzzy Extractor Using the fuzzy extractor, a noisy random source can be transformed into a uniformly random and accurately reproduced string. Fuzzy extractors can be used in cryptosystems. Symmetric key generation Using the fuzzy extractor, the user can extract a random string R and a public helper string P by calling the generation algorithm Gen (w) (P, R) with his own biological information (that is, a noisy random source) as input. This random string R can be used as the key of the cryptosystem to participate in the cryptosystem, and the public help string P is stored without confidentiality. The key R is destroyed as soon as the cryptosystem has run. When the cryptographic system needs the key again for cryptographic operation, the user takes his own biometric information (i.e., noisy random source) and the public helper string P as inputs, and calls the regeneration algorithm Rep (w ', P) R' to reproduce the key R. Therefore, the user does not need to store the key, and the fuzzy extractor can recover the key safely and reliably only by inputting own biological information when the user needs the key each time, thereby solving the problems of key generation and storage. After that, the key R is applied to the symmetric cipher algorithm, and Enc (R, m) can be used to encrypt the plaintext m to obtain the ciphertext C, and Dec (R, C) can be used to decrypt the ciphertext C and recover the plaintext m. This is shown in Figure 2. Key agreement from close secret Two-party key agreement is also possible using the fuzzy extractor technique. Let Alice have a secret message w and Bob have a secret message w'. Where the distances of w and w 'are close. For example Alice and Bob are doing quantum key distribution; Alice and Bob are listening to a noisy radio station at the same time; Alice knows Bob's iris information. Alice can use the fuzzy extractor to act on w to obtain the secure key R and a public helper string P, send P to Bob, and Bob can call the fuzzy extractor regeneration algorithm Rep (w ', P) R to reproduce the key R. Thus, Alice and Bob complete the key agreement. See Figure 3. Application of GPRS in public key cryptosystem Public-key cryptography typically rely on difficult assumptions. Hard assumptions generally require uniformly random strings. Uch as the ElGamal encryption scheme, rely on the "decisional Diffie-Hellman" assumption associated with the discrete logarithm hard problem. The discrete logarithm problem is described as follows: Given a group of size p, p is a large prime, G is the generator of the group, and for a X p chosen uniformly at random, let. Given y, G, computing the discrete logarithm of y is the discrete logarithm problem. For, if X 'is not uniformly distributed, solving the discrete logarithm problem for Z may no longer be difficult. Through the fuzzy extractor, the user can extract a uniformly random X from a noisy random source as the private key of the ElGamal encryption scheme as the public key of the ElGamal encryption scheme. Robust fuzzy extractor The security of fuzzy extractor only considers the passive attack. That is, the public helper string P can be known by the adversary, but P cannot be tampered with by the adversary. If the adversary tampers with P, then the recovery algorithm Rep of the fuzzy extractor is likely to get a wrong output R ′. But in real life, an active adversary may tamper with P. For example, in the key agreement process, an aggressive adversary can intercept P and send a wrong P 'to Bob (see Figure 4). Then Bob's call to the recovery algorithm Rep of the fuzzy extractor is likely to result in a wrong output R '. If R ≠ R ', the key negotiation fails. In order to solve the above problem, Boyen et al. [4] proposed the concept of robust fuzzy extractor in 2005. There are two definitions of security for the robustness of fuzzy extractors, namely, "pre-application" robustness and "post-application" robustness. The robustness before application ensures that the adversary submits a tampered one when he only sees the public help string P, and the recovery algorithm of the fuzzy extractor can only output, and can not produce a wrong one. However, in practical applications, if a user uses R in some cryptographic schemes, some or even all of the information of R will be leaked to the adversary. In this case, "pre-application" robustness no longer applies. " Post-application "robustness" can solve this problem. The post-application robustness guarantees that the adversary can only output the recovery algorithm of the fuzzy extractor when he sees P and R and submits a tampered. Boyen et al. [4] proposed a general method to transform fuzzy extractors into "pre-application" robust fuzzy extractors by using Hash functions. However, in the security proof,thin film distillation, the Hash function is regarded as a random oracle, so the security is based on the Random Oracle model. In 2006, Dodis et al. [7] first constructed a "post-application" robust fuzzy extractor under the standard model. In their construction, inputting a bit string w of length n and min-entropy m, the extractor can extract a uniformly distributed bit string of length l = (2m − n)/3. It can be seen that the extracted random string does not exceed 1/3 of the minimum entropy m. In 2008, K a n u K u R t H I and R e y Z I n C I t e { Kanukurthi 2008 } constructed a "post-application" robust fuzzy extractor, and the length of the extracted random string is longer: l = (2m-n)/2 bits. In 2009, Dodis et al. [9] proved that in the trivial model, if the entropy rate (m/n) of the input w is less than half, then the robustness of the fuzzy extractor is impossible to achieve. In order to solve this problem, Cramer et al. [6] proposed a new cryptographic primitive, algebraic manipulation detection (AMD), in 2008. At the same time, a robust fuzzy extractor is constructed by using AMD codes under the Common Reference String (CRS) model. CRS model means that the Common Reference String is fixed in the hardware, and no one can tamper with the CRS. Their proposed extractor breaks the line that the entropy rate of a random source needs to be greater than half of its length under the trivial model. Nonetheless, the entropy loss of this extractor is enormous. Fuzzy extractor with repeatable extraction Using the fuzzy extractor, the user can extract the secure key from his own biological information for encryption and decryption, and does not need to save the key. After enjoying the above convenience, users may want to extract multiple secure and reliable keys from their biometric information and apply them to different organizations and different scenarios. However A person's biological information is unique and cannot be altered or created; The fuzzy extractor ensures the security of extracting a key from a noisy random source. And the security of drawing multiple different keys from the same random source cannot be guaranteed. In order to solve the above problem, Boyen [3] proposed the concept of reusable fuzzy extractor (Reusable Fuzzy Extractor) in 2004. The reusable fuzzy extractor (Reusable Fuzzy Extractor) allows the production algorithm of the fuzzy extractor, Gen (w) (P, R), to extract Gen multiple times over multiple noisy versions of the random source W. Suppose that w, w1. , wρ is the result of multiple reads of a random source W, then they are statistically correlated. Invoking (P, R) Gen (w), (Pi, Ri) Gen (wi) can get multiple sets of outputs (P, R) { Pi, Ri } _ (I ∈ { 1,wiped film distillation, 2, … ,ρ})。 Let [ρ]: = { 1, 2, … , ρ }, the reusable requirement of the fuzzy extractor is that given { P _ I, R _ I } I ∈ [ρ] and P, R is still pseudorandom. In [3], Boyen proposed two construction schemes for reusable fuzzy extractors and defined "outsider security" and "insider security". Outward security is defined as follows: The adversary dynamically chooses δi and gets Pi, where (Pi, Ri) Gen (w + δi). The final (P, R) { Pi, Ri } I ∈ { 1, 2, … , ρ } should be pseudorandom to the adversary. The definition of inward security is as follows: the adversary not only gets but also sees, where the choice is made by the adversary, and R is required to be pseudo-random to the adversary. It can be seen that inward security is stronger than outward security, but it is also more difficult to achieve. In [3], reusable fuzzy extractors that achieve inward security are built on a "random oracle" model. And the amount of crosstalk δi must be independent of w. In 2017, Apon et al. [2] upgraded the scheme proposed by Fuller et al. [10] to obtain a weak reusable fuzzy extractor whose weak security depends on the LWE assumption. Its security model is similar to the "outward security" in [3], but only requires that the offsets δi submitted by the adversary satisfy dis (δi) ≤ t. But as in the scheme in [10], the error that Apon et al.'s Reusable fuzzy extractor can tolerate is only logarithmic. In 2018, we proposed a reusable fuzzy extractor based on the LWE assumption, and the scheme can tolerate errors at the linear level [14]. In 2016, Canetti et al. [5] proposed a general construction scheme for reusable fuzzy extractors, and an important module used in the general construction is "digital locker". In its security model, for w, w1, … There is no restriction on the dependence of wρ. Therefore, the security model is also the strongest one at present. However, there are only two implementations of "digital locker": one uses Hash function to construct digital locker, and the security of digital locker depends on "random oracle"; the other is based on non-standard DDH variant assumption. In addition, their scheme can only tolerate sub-linear level errors and has structural requirements on the distribution of noise random sources. Then, Alamelou et al. [1] constructed a reusable fuzzy extractor using the technical tool of "digitallocker" proposed by Canetti et al. [5], which is applicable to both Hamming distance and distance between sets. The ability of their scheme to tolerate errors is improved to the linear level. However, they need to subdivide the random source into multiple blocks, each of which is in a character set that is large enough and has enough entropy. In 2018, we [16] proposed a concrete scheme for reusable fuzzy extractors based on the standard DDH hardness assumption. The scheme is based on the standard assumptions of the standard model and can tolerate linear level errors. However, it is required that for any two reading results wi and WJ of the same random source W, the difference wi-wj does not leak too much information about the information source W. From the results w1.. of multiple readings of the same random source W. There are three main directions for the development of reusable fuzzy extractors: (1) wi can be arbitrarily correlated, but the security can only rely on "random oracles" or non-standard assumptions; (2) for any two reading results wi and WJ of the same random source W, the difference wi − WJ does not leak too much information about the information source W; (3) the difference δi (= wi − w) of any two reading results wi and WJ is controlled by the adversary. This is summarized in Figure 7. Table 1 summarizes the specific performance of each scheme. Before 2018, no researcher has proposed the construction of fuzzy extractor under the standard model to meet both robustness and reusability, but we have realized the fuzzy extractor with both for the first time, and the research results were published in the 2018 sub-secret meeting. Our Result: Reusable Robust Fuzzy Extractor In 2018, we defined reusable robust fuzzy extractors and gave a general construction method. Simply speaking, reusable robust fuzzy extractors satisfy both reusability and robustness. The modules used by our general construction method are as follows: Symmetric key encapsulation mechanism (Symmetric Key Encapsulation Mechanism, SKEM for short), whose security requirement is Key-Shift (KS) security; Secure Sketch (SS) with Homogeneity; Extractor (Ext) with homogeneity; Lossy Algebraic Filter (LAF) with Homogeneity. We construct a Key-Shift (KS) -secure SKEM based on the DDH problem, a homomorphic SS using linear error-correcting codes, and a homomorphic Ext using universal hash; A lossy algebraic filter with homogeneity can be constructed based on the DLIN problem [11]. Through such a concrete construction, we obtain the first construction scheme of a fuzzy extractor that is both reusable and robust (reusable robust fuzzy extractor), with the following properties: There is CRS in the scheme, so it is established on the CRS model; Robustness is "post-application" robustness; The scheme can tolerate linear level errors; Reusability and robustness can be achieved under the standard model based on DDH and DLIN assumptions to prove; In the security model, the adversary can control the offset δ _ I to satisfy dis (δ _ I) ≤ DT. Our work was published in AsiaCrypt2018 (see [15] for the eprint version), and the comparison with previous related work is listed in Figure 7 and Table 1. Our specific plan The reusable robust fuzzy extractor rrFE = (rrFE. Init, rrFE. Gen, rrFE. Rep) is constructed as shown in Figure 8 and Figure 9, and the requirements of the components are as follows: Symmetric key encapsulation mechanism (Symmetric Key Encapsulation Mechanism, cbd centrifugal extractor ,cbd crystallization equipment, abbreviated as SKEM) SKEM = (SKem. Init, SKem. Enc, SKem. Dec), whose key space is δκ, The encapsulated key space is κ. Secure Sketch with Homogeneity (SS) SS = (SS. Gen, SS. Rec), the measurement space is, and. Extractor (Ext for short) with homogeneity. A lossy algebraic filter with homogeneity (Lossy Algebraic Filter, LAF for short) LAF = (FGen, FEval, FTag), whose domain is and label space is. Application prospect With the reusable robust fuzzy extractor rrFE = (rrFE. Init, rrFE. Gen, rrFE. Rep), the user can use his own biometric information W as a noisy random source, such as a fingerprint, which the user can obtain via a fingerprint reading device (w1.. ,wj,… , wn), then call the generation algorithm to generate (P1, R1), … ,(Pj,Rj,)… , (Pn, Rn), Rj is used as a private key in different scenarios, such as access control devices, banking systems and smart homes. The operation is as follows (see Figure 9 and Figure 11): CRS generation: CRS is generated by using a rrFE. Init and is solidified in hardware; Key generation: taking the biometric information W as input, the generation algorithm rrFE. Gen (CRS, W) is called to generate a key R and a public helper string P; Use the key and destroy it: The key R participates in the arithmetic operation of the cryptosystem and is destroyed after use. But that public help string P is store (not necessarily secret); Key recovery: when the cryptosystem is used again, the recovery algorithm rrFE. Rep (CRS, P, W ') is invoked with the public helper string P and the (noisy) biometric information W ^' as input. If the output is, the authentication is not passed; otherwise, the output R 'is the recovered key. Destroy after using key R '. From the properties of reusable robust fuzzy extractors, we have that the following holds: The correctness of the fuzzy extractor ensures that Rj can be recovered by reading the fingerprint information and calling the recovery algorithm when the user needs Rj; The reusability of the fuzzy extractor guarantees that every Rj, J ∈ [n] is pseudorandom, and even if some Ri is leaked, Rj, J ≠ I is still pseudorandom; The robustness of the fuzzy extractor ensures that if a public help string Pj has been tampered with, the fuzzy extractor outputs that Pj has been tampered with. Now we still take the key agreement as an example to illustrate the specific use of the reusable robust fuzzy extractor. With the reusable robust fuzzy extractor, two users Alice and Bob with close secret information can make "multiple" key agreements, see fig. 12 and fig. 13. CRS generation: Alice uses rrFE. Init to generate CRS, solidifies the CRS in hardware, and sends the CRS to Bob through a secure channel. Key generation: Alice takes the secret information W in her possession as input, calls the generation algorithm rrFE. Gen (CRS, W), and generates a key R and a public helper string P; Key agreement: Alice sends a public helper string P of the key to Bob, and Bob invokes the recovery algorithm rrFE. Rep (CRS, P, W '). If W and W' are close enough, R can be correctly recovered. From the properties of reusable robust fuzzy extractors, we have that the following holds: The correctness of the fuzzy extractor guarantees that Alice and Bob will get the same Rj if the public help string Pj has not been tampered with; The reusability of the fuzzy extractor guarantees that each Rj, J ∈ [n] is pseudorandom, and even if a R _ I is leaked, Rj, J ≠ I is still pseudorandom; The robustness of the fuzzy extractor ensures that if a public help string P _ J has been tampered with, the fuzzy extractor will output a message to the user that P _ J has been tampered with, the key negotiation has failed, and another negotiation is required. References [1] Q. Alamélou, P. Berthier, C. Cachet, S.Cauchie, B. Fuller, P. Gaborit, and S. Simhadri.Pseudoentropic isometries: A new framework for fuzzy extractor reusability. In J. Kim, G. Ahn,S. Kim, Y. Kim, J. López, and T. Kim, editors,AsiaCCS 2018, pages 673–684. ACM, 2018. [2] D. Apon, C. Cho, K. Eldefrawy, and J. Katz.Efficient, reusable fuzzy extractors from LWE.In S. Dolev and S. Lodha, editors, CSCML2017, volume 10332 of LNCS, pages 1–18.Springer,Heidelberg, 2017. [3] X. Boyen. Reusable cryptographic fuzzy extractors.In V. Atluri, B. Pfitzmann, and P. D. McDaniel,editors, CCS 2004, pages 82–91. ACM, 2004. [4] X. Boyen, Y. Dodis, J. Katz, R. Ostrovsky, and A. D. Smith. Secure remote authentication using biometric data. In R. Cramer, editor,EUROCRYPT,volume 3494 of LNCS, pages 147–163. Springer, Heidelberg, 2005. [5] R. Canetti, B. Fuller, O. Paneth, L. Reyzin,and A. D. Smith. Reusable fuzzy extractors for low-entropy distributions. In M. Fischlin and J. Coron, editors, EUROCRYPT 2016,volume 9665 of LNCS, pages 117–146.Springer,Heidelberg, 2016. [6] R. Cramer, Y. Dodis, S. Fehr, C. Padró, and D.Wichs. Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors. In N. P. Smart, editor, EUROCRYPT 2008, volume 4965 of LNCS, pages 471–488.Springer, Heidelberg, 2008. [7] Y. Dodis, J. Katz, L. Reyzin, and A. D. Smith.Robust fuzzy extractors and authenticated key agreement from close secrets. In C. Dwork,editor, CRYPTO 2006, volume 4117 of LNCS,pages 232–250. Springer, Heidelberg, 2006. [8] Y. Dodis, L. Reyzin, and A. D. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In C. Cachin and J. Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 523–540.Springer, Heidelberg, 2004. [9] Y. Dodis and D. Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. In M. Mitzenmacher, editor, STOC 2009,pages 601–610. ACM, 2009. [10] B. Fuller, X. Meng, and L. Reyzin. Computational fuzzy extractors. In K. Sako and P. Sarkar,editors, ASIACRYPT 2013, volume 8269 of LNCS, pages 174–193. Springer, Heidelberg,2013. [11] D. Hofheinz. Circular chosen-ciphertext security with compact ciphertexts. In T. Johansson and P.Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 520–536. Springer,Heidelberg, 2013. [12] B. Kanukurthi and L. Reyzin. An improved robust fuzzy extractor. In R. Ostrovsky, R. D.Prisco, and I. Visconti, editors, SCN 2008,volume 5229 of LNCS, pages 156–171.Springer, Heidelberg, 2008. [13] V. Shoup. A computational introduction to number theory and algebra. Cambridge University Press, 2006. [14] Y. Wen and S. Liu. Reusable fuzzy extractor from LWE. In W. Susilo and G. Yang, editors, ACISP 2018, volume 10946 of LNCS, pages 13–27.Springer, Heidelberg, 2018. [15] Y. Wen and S. Liu. Robustly reusable fuzzy extractor from standard assumptions. Cryptology ePrint Archive, Report 2018/818, 2018. https://eprint.iacr.org/2018/818. [16] Y. Wen, S. Liu, and S. Han. Reusable fuzzy extractor from the decisional diffie-hellman assumption. Designs Codes and Cryptography,2018. Author Liu Shengli, part-time expert of Tongmoshi Laboratory, professor and doctoral supervisor of Department of Computer Science and Engineering, Shanghai Jiaotong University, mainly studies the theory and practice of public key cryptography. Wen Yunhua, Ph. D. candidate, Grade 2013, Shanghai Jiao Tong University,molecular distillation systems, focuses on the reusability and robustness of noisy extractors. (This article is selected from the second issue of Information Security and Communication Security in 2019) Original statement The original articles published on this WeChat public account are welcome to be forwarded by individuals. Without authorization, other media, Wechat public numbers and websites are not allowed to reproduce. Return to Sohu to see more Responsible Editor:. toptiontech.com