When Are Fuzzy Extractors Possible?

详细信息    查看全文

• 关键词：Fuzzy extractors ; Secure sketches ; Information theory ; Biometric authentication ; Error ; tolerance ; Key derivation ; Error ; correcting codes
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：10031
• 期：1
• 页码：277-306
• 全文大小：567 KB
• 参考文献：1.Ahlswede, R., Csiszár, I.: Common randomness in information theory and cryptography - I: secret sharing. IEEE Trans. Inf. Theory 39(4), 1121–1132 (1993)MathSciNet CrossRef MATH
  2.Ash, R.: Information Theory. Intersciene Publishers, New York (1965)MATH
  3.Barak, B., Canetti, R., Lindell, Y., Pass, R., Rabin, T.: Secure computation without authentication. J. Cryptology 24(4), 720–760 (2011)MathSciNet CrossRef MATH
  4.Bennett, C.H., Brassard, G., Robert, J.M.: Privacy amplification by public discussion. SIAM J. Comput. 17(2), 210–229 (1988)MathSciNet CrossRef MATH
  5.Bitansky, N., Canetti, R., Kalai, Y.T., Paneth, O.: On virtual grey box obfuscation for general circuits. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 108–125. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-44381-1_​7 CrossRef
  6.Blanton, M., Hudelson, W.M.P.: Biometric-based non-transferable anonymous credentials. In: Qing, S., Mitchell, C.J., Wang, G. (eds.) ICICS 2009. LNCS, vol. 5927, pp. 165–180. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-11145-7_​14 CrossRef
  7.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). doi:10.​1007/​11426639_​9 CrossRef
  8.Brostoff, S., Sasse, M.: Are passfaces more usable than passwords?: a field trial investigation. In: McDonald, S., Waern, Y., Cockton, G. (eds.) People and Computers, pp. 405–424. Springer, London (2000)
  9.Carter, L., Wegman, M.N.: Universal classes of hash functions. J. Comput. Syst. Sci. 18(2), 143–154 (1979)MathSciNet CrossRef MATH
  10.Csiszár, I., Körner, J.: Broadcast channels with confidential messages. IEEE Trans. Inf. Theory 24(3), 339–348 (1978)MathSciNet CrossRef MATH
  11.Daugman, J.: Probing the uniqueness and randomness of iriscodes: results from 200 billion iris pair comparisons. Proc. IEEE 94(11), 1927–1935 (2006)CrossRef
  12.Daugman, J.: How iris recognition works. IEEE Trans. Circ. Syst. Video Technol. 14(1), 21–30 (2004)CrossRef
  13.Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97–139 (2008)MathSciNet CrossRef MATH
  14.Ellison, C., Hall, C., Milbert, R., Schneier, B.: Protecting secret keys with personal entropy. Future Gener. Comput. Syst. 16(4), 311–318 (2000)CrossRef
  15.Fano, R.: Transmission of Information: A Statistical Theory of Communications. MIT Press Classics, M.I.T. Press, New York (1961)MATH
  16.Frankl, P., Füredi, Z.: A short proof for a theorem of Harper about Hamming-spheres. Discrete Math. 34(3), 311–313 (1981)MathSciNet CrossRef MATH
  17.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). doi:10.​1007/​978-3-642-42033-7_​10 CrossRef
  18.Fuller, B., Smith, A., Reyzin, L.: When are fuzzy extractors possible? IACR Cryptology ePrint Archive 2014, 961 (2014)
  19.Gassend, B., Clarke, D., Van Dijk, M., Devadas, S.: Silicon physical random functions. In: Proceedings of the 9th ACM Conference on Computer and Communications Security, pp. 148–160. ACM (2002)
  20.Hao, F., Anderson, R., Daugman, J.: Combining crypto with biometrics effectively. IEEE Trans. Comput. 55(9), 1081–1088 (2006)CrossRef
  21.Harper, L.H.: Optimal numberings and isoperimetric problems on graphs. J. Comb. Theory 1(3), 385–393 (1966)MathSciNet CrossRef MATH
  22.Hayashi, M., Tyagi, H., Watanabe, S.: Secret key agreement: general capacity and second-order asymptotics. In: 2014 IEEE International Symposium on Information Theory, pp. 1136–1140. IEEE (2014)
  23.Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13–30 (1963)MathSciNet CrossRef MATH
  24.Holenstein, T.: Strengthening key agreement using hard-core sets. Ph.D. thesis, ETH Zurich (May 2006), reprint as vol. 7 of ETH Series in Information Security and Cryptography, ISBN 3-86626-088-2, Hartung-Gorre Verlag, Konstanz (2006)
  25.Holenstein, T., Renner, R.: One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 478–493. Springer, Heidelberg (2005). doi:10.​1007/​11535218_​29 CrossRef
  26.Ignatenko, T., Willems, F.M.: Biometric security from an information-theoretical perspective. Found. Trends Commun. Inf. Theory 7(2–3), 135–316 (2012)MATH
  27.Juels, A., Wattenberg, M.: A fuzzy commitment scheme. In: Sixth ACM Conference on Computer and Communication Security, pp. 28–36. ACM, November 1999
  28.Linnartz, J.-P., Tuyls, P.: New shielding functions to enhance privacy and prevent misuse of biometric templates. In: Kittler, J., Nixon, M.S. (eds.) AVBPA 2003. LNCS, vol. 2688, pp. 393–402. Springer, Heidelberg (2003). doi:10.​1007/​3-540-44887-X_​47 CrossRef
  29.Maurer, U.M.: Secret key agreement by public discussion from common information. IEEE Trans. Inf. Theory 39(3), 733–742 (1993)MathSciNet CrossRef MATH
  30.Mayrhofer, R., Gellersen, H.: Shake well before use: intuitive and secure pairing of mobile devices. IEEE Trans. Mob. Comput. 8(6), 792–806 (2009)CrossRef
  31.Monrose, F., Reiter, M.K., Wetzel, S.: Password hardening based on keystroke dynamics. Int. J. Inf. Secur. 1(2), 69–83 (2002)CrossRef MATH
  32.Nisan, N., Zuckerman, D.: Randomness is linear in space. J. Comput. Syst. Sci. 52(1), 43–52 (1996)MathSciNet CrossRef MATH
  33.Pappu, R., Recht, B., Taylor, J., Gershenfeld, N.: Physical one-way functions. Science 297(5589), 2026–2030 (2002)CrossRef
  34.Renner, R., Wolf, S.: The exact price for unconditionally secure asymmetric cryptography. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 109–125. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-24676-3_​7 CrossRef
  35.Renner, R., Wolf, S.: Simple and tight bounds for information reconciliation and privacy amplification. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 199–216. Springer, Heidelberg (2005). doi:10.​1007/​11593447_​11 CrossRef
  36.Skoric, B., Tuyls, P.: An efficient fuzzy extractor for limited noise. Cryptology ePrint Archive, Report 2009/030 (2009)
  37.Suh, G.E., Devadas, S.: Physical unclonable functions for device authentication and secret key generation. In: Proceedings of the 44th Annual Design Automation Conference, pp. 9–14. ACM (2007)
  38.Tuyls, P., Goseling, J.: Capacity and examples of template-protecting biometric authentication systems. In: Maltoni, D., Jain, A.K. (eds.) BioAW 2004. LNCS, vol. 3087, pp. 158–170. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-25976-3_​15 CrossRef
  39.Tuyls, P., Schrijen, G.-J., van Škorić, B., Geloven, J., Verhaegh, N., Wolters, R.: Read-proof hardware from protective coatings. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 369–383. Springer, Heidelberg (2006). doi:10.​1007/​11894063_​29 CrossRef
  40.Tyagi, H., Watanabe, S.: Converses for secret key agreement and secure computing. IEEE Trans. Inf. Theo. 61(9) (2015)
  41.Wang, Y., Rane, S., Draper, S.C., Ishwar, P.: A theoretical analysis of authentication, privacy and reusability across secure biometric systems. IEEE Trans. Inf. Forensics Secur. 6(6), 1825–1840 (2012)CrossRef
  42.Wyner, A.D.: The wire-tap channel. Bell Syst. Tech. J. 54(8), 1355–1387 (1975)MathSciNet CrossRef MATH
  43.Zviran, M., Haga, W.J.: A comparison of password techniques for multilevel authentication mechanisms. Comput. J. 36(3), 227–237 (1993)CrossRef
  
• 作者单位：Benjamin Fuller (15)
  Leonid Reyzin (16)
  Adam Smith (17)
  
  15. University of Connecticut, Storrs, CT, USA
  16. Boston University, Boston, MA, USA
  17. Pennsylvania State University, University Park, PA, USA
  
• 丛书名：Advances in Cryptology ¨C ASIACRYPT 2016
• ISBN：978-3-662-53887-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：10031

文摘

Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a high-entropy secret into the same uniformly distributed key. A minimum condition for the security of the key is the hardness of guessing a value that is similar to the secret, because the fuzzy extractor converts such a guess to the key.