O(δ), provided that we start with entropy \(k\ge m+2\log\left({1}/{\delta}\right)-O(1)\) . By a result of Radhakrishnan and Ta-Shma, this bound on k (called the “RT-bound- is also known to be tight in general. Unfortunately, in many situations the loss of \(2\log\left({1}/{\delta}\right)\) bits of entropy is unacceptable. This motivates the study KDFs with less entropy waste by placing some restrictions on the source X or the application P. In this work we obtain the following new positive and negative results in this regard: Efficient samplability of the source X does not help beat the RT-bound for general applications. This resolves the SRT (samplable RT) conjecture of Dachman-Soled et al. [DGKM12] in the affirmative, and also shows that the existence of computationally-secure extractors beating the RT-bound implies the existence of one-way functions. We continue in the line of work initiated by Barak et al. [BDK+11] and construct new information-theoretic KDFs which beat the RT-bound for large but restricted classes of applications. Specifically, we design efficient KDFs that work for all unpredictability applications P (e.g., signatures, MACs, one-way functions, etc.) and can either: (1) extract all of the entropy k--em class="a-plus-plus">m with a very modest security loss \(\delta'=O(\delta\cdot \log\left({1}/{\delta}\right))\) , or alternatively, (2) achieve essentially optimal security δ′--em class="a-plus-plus">O(δ) with a very modest entropy loss \(k \ge m+\log\!\log\left({1}/{\delta}\right)\) . In comparison, the best prior results from [BDK+11] for this class of applications would only guarantee \(\delta'=O(\sqrt{\delta})\) when k--em class="a-plus-plus">m, and would need \(k\ge m+\log\left({1}/{\delta}\right)\) to get δ′--em class="a-plus-plus">O(δ). The weaker bounds of [BDK+11] hold for a larger class of so-called “square-friendly-applications (which includes all unpredictability, but also some important indistinguishability, applications). Unfortunately, we show that these weaker bounds are tight for the larger class of applications. We abstract out a clean, information-theoretic notion of (k,δ,δ--unpredictability extractors, which guarantee “induced-security δ-for any δ-secure unpredictability application P, and characterize the parameters achievable for such unpredictability extractors. Of independent interest, we also relate this notion to the previously-known notion of (min-entropy) condensers, and improve the state-of-the-art parameters for such condensers." />
Key Derivation without Entropy Waste
详细信息    查看全文
  • 作者：Yevgeniy Dodis (17)
    Krzysztof Pietrzak (18)
    Daniel Wichs (19)
  • 刊名：Lecture Notes in Computer Science
  • 出版年：2014
  • 出版时间：2014
  • 年：2014
  • 卷：8441
  • 期：1
  • 页码：93-110
  • 参考文献：1. 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-63. Springer, Heidelberg (2005) CrossRef
    2. Barak, B., Dodis, Y., Krawczyk, H., Pereira, O., Pietrzak, K., Standaert, F.-X., Yu, Y.: Leftover hash lemma, revisited. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.?6841, pp. 1-0. Springer, Heidelberg (2011) CrossRef
    3. Barak, B., Halevi, S.: A model and architecture for pseudo-random generation with applications to /dev/random. In: Proceedings of the 12th ACM Conference on Computer and Communication Security, pp. 203-12 (2005)
    4. Bellare, M., Rompel, J.: Randomness-efficient oblivious sampling. In: 35th Annual Symposium on Foundations of Computer Science, pp. 276-87. IEEE (1994)
    5. Barak, B., Shaltiel, R., Tromer, E.: True random number generators secure in a changing environment. In: Walter, C.D., Ko?, ?.K., Paar, C. (eds.) CHES 2003. LNCS, vol.?2779, pp. 166-80. Springer, Heidelberg (2003) CrossRef
    6. Canetti, R., Dodis, Y., Halevi, S., Kushilevitz, E., Sahai, A.: Exposure-resilient functions and all-or-nothing transforms. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol.?1807, pp. 453-69. Springer, Heidelberg (2000) CrossRef
    7. Chor, B., Goldreich, O.: On the power of two-point based sampling. Journal of Complexity?5, 96-06 (1989) CrossRef
    8. Elisa Celis, L., Reingold, O., Segev, G., Wieder, U.: Balls and bins: Smaller hash families and faster evaluation. In: Ostrovsky, R. (ed.) FOCS, pp. 599-08. IEEE (2011)
    9. Dodis, Y., Gennaro, R., H?stad, J., Krawczyk, H., Rabin, T.: Randomness extraction and key derivation using the CBC, cascade and HMAC modes. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol.?3152, pp. 494-10. Springer, Heidelberg (2004) CrossRef
    10. Dachman-Soled, D., Gennaro, R., Krawczyk, H., Malkin, T.: Computational extractors and pseudorandomness. In: Cramer, R. (ed.) TCC 2012. LNCS, vol.?7194, pp. 383-03. Springer, Heidelberg (2012) CrossRef
    11. Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing?38(1), 97-39 (2008) CrossRef
    12. Dodis, Y., Pietrzak, K., Wichs, D.: Key derivation without entropy waste. Cryptology ePrint Archive, Report 2013/708 (2013), http://eprint.iacr.org/
    13. Dodis, Y., Ristenpart, T., Vadhan, S.: Randomness condensers for efficiently samplable, seed-dependent sources. In: Cramer, R. (ed.) TCC 2012. LNCS, vol.?7194, pp. 618-35. Springer, Heidelberg (2012) CrossRef
    14. Dodis, Y., Yu, Y.: Overcoming weak expectations. In: Sahai, A. (ed.) TCC 2013. LNCS, vol.?7785, pp. 1-2. Springer, Heidelberg (2013) CrossRef
    15. Gennaro, R., Krawczyk, H., Rabin, T.: Secure hashed diffie-hellman over non-DDH groups. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol.?3027, pp. 361-81. Springer, Heidelberg (2004) CrossRef
    16. H?stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: Construction of pseudorandom generator from any one-way function. SIAM Journal on Computing?28(4), 1364-396 (1999) CrossRef
    17. Krawczyk, H.: Cryptographic Extraction and Key Derivation: The HKDF Scheme. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.?6223, pp. 631-48. Springer, Heidelberg (2010) CrossRef
    18. Kamp, J., Zuckerman, D.: Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. In: 44th Annual Symposium on Foundations of Computer Science, pp. 92-01. IEEE, Cambridge (2003)
    19. Nisan, N., Zuckerman, D.: Randomness is linear in space. Journal of Computer and System Sciences?52(1), 43-3 (1996) CrossRef
    20. Raz, R., Reingold, O.: On recycling the randomness of states in space bounded computation. In: Proceedings of the 31st ACM Symposium on the Theory of Computing, pp. 159-68 (1999)
    21. Reingold, O., Shaltiel, R., Wigderson, A.: Extracting randomness via repeated condensing. SIAM J. Comput.?35(5), 1185-209 (2006) CrossRef
    22. Radhakrishnan, J., Ta-Shma, A.: Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Computing?13(1), 2-4 (2000)
    23. Siegel, A.: On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications (extended abstract). In: FOCS, pp. 20-5 (1989)
    24. Trevisan, L., Vadhan, S.: Extracting randomness from samplable distributions. In: 41st Annual Symposium on Foundations of Computer Science, pp. 32-2. IEEE, Redondo Beach (2000) CrossRef
  • 作者单位：Yevgeniy Dodis (17)
    Krzysztof Pietrzak (18)
    Daniel Wichs (19)

    17. New York University, USA
    18. IST Austria, Austria
    19. Northeastern University, USA
  • ISSN：1611-3349
文摘
We revisit the classical problem of converting an imperfect source of randomness into a usable cryptographic key. Assume that we have some cryptographic application P that expects a uniformly random m-bit key R and ensures that the best attack (in some complexity class) against P(R) has success probability at most δ. Our goal is to design a key-derivation function (KDF) h that converts any random source X of min-entropy k into a sufficiently “good-key h(X), guaranteeing that P(h(X)) has comparable security δ-which is ‘close-to δ. Seeded randomness extractors provide a generic way to solve this problem for all applications P, with resulting security δ′--em class="a-plus-plus">O(δ), provided that we start with entropy \(k\ge m+2\log\left({1}/{\delta}\right)-O(1)\) . By a result of Radhakrishnan and Ta-Shma, this bound on k (called the “RT-bound- is also known to be tight in general. Unfortunately, in many situations the loss of \(2\log\left({1}/{\delta}\right)\) bits of entropy is unacceptable. This motivates the study KDFs with less entropy waste by placing some restrictions on the source X or the application P. In this work we obtain the following new positive and negative results in this regard: Efficient samplability of the source X does not help beat the RT-bound for general applications. This resolves the SRT (samplable RT) conjecture of Dachman-Soled et al. [DGKM12] in the affirmative, and also shows that the existence of computationally-secure extractors beating the RT-bound implies the existence of one-way functions. We continue in the line of work initiated by Barak et al. [BDK+11] and construct new information-theoretic KDFs which beat the RT-bound for large but restricted classes of applications. Specifically, we design efficient KDFs that work for all unpredictability applications P (e.g., signatures, MACs, one-way functions, etc.) and can either: (1) extract all of the entropy k--em class="a-plus-plus">m with a very modest security loss \(\delta'=O(\delta\cdot \log\left({1}/{\delta}\right))\) , or alternatively, (2) achieve essentially optimal security δ′--em class="a-plus-plus">O(δ) with a very modest entropy loss \(k \ge m+\log\!\log\left({1}/{\delta}\right)\) . In comparison, the best prior results from [BDK+11] for this class of applications would only guarantee \(\delta'=O(\sqrt{\delta})\) when k--em class="a-plus-plus">m, and would need \(k\ge m+\log\left({1}/{\delta}\right)\) to get δ′--em class="a-plus-plus">O(δ). The weaker bounds of [BDK+11] hold for a larger class of so-called “square-friendly-applications (which includes all unpredictability, but also some important indistinguishability, applications). Unfortunately, we show that these weaker bounds are tight for the larger class of applications. We abstract out a clean, information-theoretic notion of (k,δ,δ--unpredictability extractors, which guarantee “induced-security δ-for any δ-secure unpredictability application P, and characterize the parameters achievable for such unpredictability extractors. Of independent interest, we also relate this notion to the previously-known notion of (min-entropy) condensers, and improve the state-of-the-art parameters for such condensers.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址：北京市海淀区学院路29号 邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700