Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Key Derivation without Entropy Waste

  • Conference paper

Abstract

We revisit the classical problem of converting an imperfect source of randomness into a usable cryptographic key. Assume that we have some cryptographic applicationP that expects a uniformly randomm-bit keyR and ensures that the best attack (in some complexity class) againstP(R) has success probability at mostδ. Our goal is to design a key-derivation function (KDF)h that converts any random sourceX of min-entropyk into a sufficiently “good” keyh(X), guaranteeing thatP(h(X)) has comparable securityδ′ which is ‘close’ toδ.

Seeded randomness extractors provide a generic way to solve this problem forall applicationsP, with resulting securityδ′ = 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 onk (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 sourceX or the applicationP.

In this work we obtain the following new positive and negative results in this regard:

  • Efficient samplability of the sourceX 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 forall unpredictability applicationsP (e.g., signatures, MACs, one-way functions, etc.) and can either: (1) extractall of the entropyk = m with a very modest security loss\(\delta'=O(\delta\cdot \log\left({1}/{\delta}\right))\), or alternatively, (2) achieve essentially optimal securityδ′ = 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})\) whenk = m, and would need\(k\ge m+\log\left({1}/{\delta}\right)\) to getδ′ = 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 applicationP, 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.

Similar content being viewed by others

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  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–163. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  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–20. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  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–212 (2005)

    Google Scholar 

  4. Bellare, M., Rompel, J.: Randomness-efficient oblivious sampling. In: 35th Annual Symposium on Foundations of Computer Science, pp. 276–287. IEEE (1994)

    Google Scholar 

  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–180. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  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–469. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  7. Chor, B., Goldreich, O.: On the power of two-point based sampling. Journal of Complexity 5, 96–106 (1989)

    Article MATH MathSciNet  Google Scholar 

  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–608. IEEE (2011)

    Google Scholar 

  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–510. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  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–403. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  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–139 (2008)

    Article MATH MathSciNet  Google Scholar 

  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–635. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  14. Dodis, Y., Yu, Y.: Overcoming weak expectations. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 1–22. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  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–381. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  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–1396 (1999)

    Article MATH MathSciNet  Google Scholar 

  17. Krawczyk, H.: Cryptographic Extraction and Key Derivation: The HKDF Scheme. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 631–648. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  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–101. IEEE, Cambridge (2003)

    Google Scholar 

  19. Nisan, N., Zuckerman, D.: Randomness is linear in space. Journal of Computer and System Sciences 52(1), 43–53 (1996)

    Article MATH MathSciNet  Google Scholar 

  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–168 (1999)

    Google Scholar 

  21. Reingold, O., Shaltiel, R., Wigderson, A.: Extracting randomness via repeated condensing. SIAM J. Comput. 35(5), 1185–1209 (2006)

    Article MATH MathSciNet  Google Scholar 

  22. Radhakrishnan, J., Ta-Shma, A.: Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Computing 13(1), 2–24 (2000)

    MATH MathSciNet  Google Scholar 

  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–25 (1989)

    Google Scholar 

  24. Trevisan, L., Vadhan, S.: Extracting randomness from samplable distributions. In: 41st Annual Symposium on Foundations of Computer Science, pp. 32–42. IEEE, Redondo Beach (2000)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. New York University, USA

    Yevgeniy Dodis

  2. IST Austria, Austria

    Krzysztof Pietrzak

  3. Northeastern University, USA

    Daniel Wichs

Authors
  1. Yevgeniy Dodis

    You can also search for this author inPubMed Google Scholar

  2. Krzysztof Pietrzak

    You can also search for this author inPubMed Google Scholar

  3. Daniel Wichs

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Départment d’informatique, Ecole normale supérieure, 45, rue d’Ulm, 75230, Paris Cedex 05, France

    Phong Q. Nguyen

  2. Department of Computer Science, University of Bristol, Merchant Venturers Building, Woodland Road, BS8 1UB, Bristol, UK

    Elisabeth Oswald

Rights and permissions

Copyright information

© 2014 International Association for Cryptologic Research

About this paper

Cite this paper

Dodis, Y., Pietrzak, K., Wichs, D. (2014). Key Derivation without Entropy Waste. In: Nguyen, P.Q., Oswald, E. (eds) Advances in Cryptology – EUROCRYPT 2014. EUROCRYPT 2014. Lecture Notes in Computer Science, vol 8441. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-55220-5_6

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp