nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

A Reusable Fuzzy Extractor with Practical Storage Size: Modifying Canetti et al.’s Construction

verfasst von : Jung Hee Cheon, Jinhyuck Jeong, Dongwoo Kim, Jongchan Lee

Erschienen in: Information Security and Privacy

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

After the concept of a Fuzzy Extractor (FE) was first introduced by Dodis et al., it has been regarded as one of the candidate solutions for key management utilizing biometric data. With a noisy input such as biometrics, FE generates a public helper value and a random secret key which is reproducible given another input similar to the original input. However, “helper values” may cause some leakage of information when generated repeatedly by correlated inputs, thus reusability should be considered as an important property. Recently, Canetti et al. (Eurocrypt 2016) proposed a FE satisfying both reusability and robustness with inputs from low-entropy distributions. Their strategy, the so-called Sample-then-Lock method, is to sample many partial strings from a noisy input string and to lock one secret key with each partial string independently.

In this paper, modifying this reusable FE, we propose a new FE with size-reduced helper data hiring a threshold scheme. Our new FE also satisfies both reusability and robustness, and requires much less storage memory than the original. To show the advantages of this scheme, we analyze and compare our scheme with the original in concrete parameters of the biometric, IrisCode. As a result, on 1024-bit inputs, with false rejection rate 0.5 and error tolerance 0.25, while the original requires about 1 TB for each helper value, our scheme requires only 300 MB with an additional 1.35 GB of common data which can be used for all helper values.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Reusable Fuzzy Extractor from LWE

Nächstes Kapitel 21 - Bringing Down the Complexity: Fast Composable Protocols for Card Games Without Secret State

Robustness can easily be satisfied by the random-oracle-based transform of [10] as mentioned in [9]. Thus, we only focus on the reusability in this paper.

The false rejection rate is the probability that the reproducing algorithm \({\mathsf {Rep}}\) fails to regenerate the secret value even though a legitimate input is given.

We refers the formal definition of robustness to [11].

One can also use SHA3 or other hash functions.

We take \(\delta = 1/2\) for convenience. One can achieve \(\delta = 1/2^b\) increasing \(\ell \) to \(b\ell \).

In fact, we should take into account the min-entropy of the partial biometric, but we will assume that the min-entropy is k for simplicity.

In fact, we should take the size of nonce so that the resulting locker is \(\ell \)-composable, i.e., no collision occurs among \(\ell \) nonces. In our cases, 144 (= 224−80) bit is sufficient for the size of nonce.

Canetti et al. [9] mentioned that with sophisticated samplers, one can decrease the required storage. However, it can only decrease the storage for index, and the storage for \({\mathsf {lock}}\)s can not be decreased.

We can also consider a divisor d of \(n' \le n\), and follow the construction taking \(n'\) instead of n.

For convenience, we only consider the partitions whose elements have the same cardinality. An analogous statement can be made for more general partitions.

Note that, in (\(\tau , m\)) threshold scheme, the size of secret k is \(D(m_p-1)\) for some \(D \in \mathbb {Z}_{>0}\). We take D satisfying proper security.

https://eprint.iacr.org/.

Canetti et al.’s construction requires \(\ell \) or \(\ell \rho \) -composable digital lockers, and \(\ell \ge N(m+1)\) in our parameter settings.

Since Time(\({\mathsf {RA}}\)) \(\approx \) Time(\({\mathsf {DA}}\)), maximal time of \({\mathsf {Rep}}\) is much bigger than that of \({\mathsf {Gen}}\), and we only consider the time of \({\mathsf {Rep}}\).

The space for “Mat. for \({\mathsf {DA}}\)” is excluded since it is a common data for every users. It doesn’t affect the tendency in this graph overall.

Erkin, Z., Franz, M., Guajardo, J., Katzenbeisser, S., Lagendijk, I., Toft, T.: Privacy-preserving face recognition. In: Goldberg, I., Atallah, M.J. (eds.) PETS 2009. LNCS, vol. 5672, pp. 235–253. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03168-7_14CrossRef

Kulkarni, R., Namboodiri, A.M.: Secure hamming distance based biometric authentication. In: International Conference on Biometrics, ICB 2013, pp. 1–6 (2013). https://doi.org/10.1109/ICB.2013.6613008

Karabat, C., Kiraz, M.S., Erdogan, H., Savas, E.: THRIVE: threshold homomorphic encryption based secure and privacy preserving biometric verification system. EURASIP J. Adv. Sig. Process. 2015, 71 (2015). https://doi.org/10.1186/s13634-015-0255-5CrossRef

Cheon, J.H., Chung, H., Kim, M., Lee, K.: Ghostshell: secure biometric authentication using integrity-based homomorphic evaluations. IACR Cryptology ePrint Archive 2016, 484 (2016)

Dodis, Y., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 523–540. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_31CrossRef

Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.D.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97–139 (2008). https://doi.org/10.1137/060651380MathSciNetCrossRefMATH

Apon, D., Cho, C., Eldefrawy, K., Katz, J.: Efficient, reusable fuzzy extractors from LWE. In: Dolev, S., Lodha, S. (eds.) CSCML 2017. LNCS, vol. 10332, pp. 1–18. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-60080-2_1CrossRef

Fuller, B., Meng, X., Reyzin, L.: Computational fuzzy extractors. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8269, pp. 174–193. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42033-7_10CrossRef

Canetti, R., Fuller, B., Paneth, O., Reyzin, L., Smith, A.: Reusable fuzzy extractors for low-entropy distributions. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 117–146. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_5CrossRef

10.

Boyen, X., Dodis, Y., Katz, J., Ostrovsky, R., Smith, A.: Secure remote authentication using biometric data. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 147–163. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_9CrossRef

11.

Dodis, Y., Kanukurthi, B., Katz, J., Reyzin, L., Smith, A.D.: Robust fuzzy extractors and authenticated key agreement from close secrets. IEEE Trans. Inf. Theory 58(9), 6207–6222 (2012). https://doi.org/10.1109/TIT.2012.2200290MathSciNetCrossRefMATH

12.

Shamir, A.: How to share a secret. Commun. ACM 11, 612–613 (1979). https://doi.org/10.1145/359168.359176MathSciNetCrossRefMATH

13.

Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of the AFIPS 1979 National Computer Conference, pp. 313–317 (1979). https://doi.org/10.1109/AFIPS.1979.98

14.

Ishizu, H., Ogihara, T.: A study on long-term storage of electronic data. In: Proceedings of the IEICE General Conference, vol. D-9-10, no. 1, p. 125 (2004)

15.

Fujii, Y.: A fast (2, n)-threshold scheme and its application. In: Proceedings of the CSS 2005, pp. 631–636 (2005)

16.

Kurihara, J., Kiyomoto, S., Fukushima, K., Tanaka, T.: A fast (3, n)-threshold secret sharing scheme using exclusive-OR operations. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 91(1), 127–138 (2008). https://doi.org/10.1093/ietfec/e91-a.1.127CrossRef

17.

Kurihara, J., Kiyomoto, S., Fukushima, K., Tanaka, T.: A New (k, n)-threshold secret sharing scheme and its extension. In: Wu, T.-C., Lei, C.-L., Rijmen, V., Lee, D.-T. (eds.) ISC 2008. LNCS, vol. 5222, pp. 455–470. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85886-7_31CrossRef

18.

Canetti, R., Tauman Kalai, Y., Varia, M., Wichs, D.: On symmetric encryption and point obfuscation. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 52–71. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11799-2_4CrossRef

19.

Lynn, B., Prabhakaran, M., Sahai, A.: Positive results and techniques for obfuscation. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 20–39. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_2CrossRef

20.

Canetti, R., Dakdouk, R.R.: Obfuscating point functions with multibit output. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 489–508. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_28CrossRef

21.

Hollingsworth, K.P., Bowyer, K.W., Flynn, P.J.: Improved iris recognition through fusion of hamming distance and fragile bit distance. IEEE Trans. Pattern Anal. Mach. Intell. 33(12), 2465–2476 (2011). https://doi.org/10.1109/TPAMI.2011.89CrossRef

22.

Daugman, J.: Probing the uniqueness and randomness of iriscodes: results from 200 billion iris pair comparisons. Proc. IEEE 94(11), 1927–1935 (2006). https://doi.org/10.1109/JPROC.2006.884092CrossRef

23.

Desoky, A.I., Ali, H.A., Abdel-Hamid, N.B.: Enhancing iris recognition system performance using templates fusion. Ain Shams Eng. J. 3(2), 133–140 (2012). https://doi.org/10.1109/ISSPIT.2010.5711758CrossRef

Titel: A Reusable Fuzzy Extractor with Practical Storage Size: Modifying Canetti et al.’s Construction
verfasst von: Jung Hee Cheon
Jinhyuck Jeong
Dongwoo Kim
Jongchan Lee
Verlag: Springer International Publishing
Buch: Information Security and Privacy
Print ISBN: 978-3-319-93637-6

Electronic ISBN: 978-3-319-93638-3

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-93638-3_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner