Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Exposure-Resilient Functions and All-or-Nothing Transforms

  • Conference paper
  • First Online:

Abstract

We study the problem ofpartial key exposure. Standard cryptographic definitions and constructions do not guarantee any security even if a tiny fraction of the secret key is compromised. We show how to build cryptographic primitives that remain secure even when an adversary is able to learnalmost all of the secret key.

The key to our approach is a new primitive of independent interest, which we call anExposure-Resilient Function (ERF) — a deterministic function whose output appears random (in a perfect, statistical or computational sense) even ifalmost all the bits of the input are known.ERF’s by themselves efficiently solve the partial key exposure problem in the setting where the secret is simply a random value, like in privatekey cryptography. They can also be viewed as very secure pseudorandom generators, and have many other applications.

To solve the general partial key exposure problem, we use the (generalized) notion of anAll-Or-Nothing Transform (AONT), aninvertible (randomized) transformationT which, nevertheless, reveals “no information” aboutx even ifalmost all the bits ofT(x) are known. By applying anAONT to the secret key of any cryptographic system, we obtain security against partial key exposure. To date, the only known security analyses ofAONT candidates were made in the random oracle model.

We show how to constructERF’s andAONT’s with nearly optimal parameters. Our computational constructions are based on any one-way function. We also provide several applications and additional properties concerning these notions.

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. M. Bellare, S. Miner. A Forward-Secure Digital Signature Scheme. InProc. of Crypto, pp. 431–448, 1999.

    Google Scholar 

  2. M. Bellare, P. Rogaway. Optimal Asymetric Encryption. InProc. of EuroCrypt, pp. 92–111, 1995.

    Google Scholar 

  3. G. Blackley. Safeguarding Cryptographic Keys. InProc. of AFIPS 1979 National Computer Conference, 1979.

    Google Scholar 

  4. V. Boyko. On the Security Properties of the OAEP as an All-or-Nothing Transform. InProc. of Crypto, pp. 503–518, 1999.

    Google Scholar 

  5. R. Canetti, O. Goldreich and S. Halevi. The Random-Oracle Model, Revisited. InProc. of STOC, pp. 209–218, 1998.

    Google Scholar 

  6. B. Chor, J. Friedman, O. Goldreich, J. Hastad, S. Rudich, R. Smolensky. The Bit Extraction Problem ort-resilient Functions. InProc. of FOCS, pp. 396–407, 1985.

    Google Scholar 

  7. W. Diffie, P. van Oorschot and M. Wiener. Authentication and authenticated key exchanges.Designs, Codes and Cryptography, 2:107–125, 1992.

    Article  Google Scholar 

  8. A. Dornan. New Viruses Search For Strong Encryption Keys. InPlanetIT Systems Management News, March, 1999,http://www.planetit.com/techcenters/docs/systems_management/news/PIT19990317S0015.

  9. O. Goldreich. Foundations of Cryptography (Fragments of a Book). Available athttp://www.wisdom.weizmann.ac.il/home/oded/public_html/frag.html

  10. O. Goldreich. A Note on Computational Indistinguishability. InIPL, 34:277–281, 1990.

    Article MATH MathSciNet  Google Scholar 

  11. O. Goldreich, S. Goldwasser and S. Micali. How to construct random functions.Journal of the ACM, 33(4):210–217, 1986.

    Article MathSciNet  Google Scholar 

  12. J. Hastad, R. Impagliazzo, L. Levin, M. Luby. A Pseudorandom generator from any one-way function. InProc. of STOC, 1989.

    Google Scholar 

  13. R. Impagliazzo, L. Levin, M. Luby. Pseudorandom Generation from one-way functions. InProc. of STOC, pp. 12–24, 1989.

    Google Scholar 

  14. M. Jakobsson, J. Stern, M. Yung. Scramble All, Encrypt Small. InProc. of Fast Software Encryption, pp. 95–111, 1999.

    Google Scholar 

  15. H. Krawczyk. Secret Sharing Made Short. InProc. of Crypto, pp. 136–146, 1993.

    Google Scholar 

  16. F. MacWilliams, J. Sloane. Theory of Error-Correcting Codes, Amsterdam, 1981.

    Google Scholar 

  17. J. Naor, M. Naor. Small-Bias Probability Spaces: Efficient Constructions and Applications. InSIAM J. Computing, 22(4):838–856, 1993.

    Article MATH MathSciNet  Google Scholar 

  18. R. Raz, O. Reingold, S. Vadhan. Error Reduction for Extractors. In Proc. of FOCS, pp. 191–201, 1999.

    Google Scholar 

  19. R. Rivest. All-or-Nothing Encryption and the Package Transform. InFast Software Encryption,LNCS, 1267:210–218, 1997.

    Chapter  Google Scholar 

  20. A. Shamir. How to share a secret. InCommunic. of the ACM, 22:612–613, 1979.

    Article MATH MathSciNet  Google Scholar 

  21. A. Shamir, N. van Someren. Playing “hide and seek” with stored keys. InProc. of Financial Cryptography, 1999.

    Google Scholar 

  22. S._U. Shin, K. H. Rhee. Hash functions and the MAC using all-or-nothing property. InProc. of Public Key Cryptography,LNCS, 1560:263–275, 1999.

    Chapter  Google Scholar 

  23. N. van Someren. How not to authenticate code. Crypto’98 Rump Session, Santa Barbara, 1998.

    Google Scholar 

  24. A. Srinivasan, D. Zuckerman. Computing with Very Weak Random Sources. InProc. of FOCS, pp. 264–275, 1994.

    Google Scholar 

  25. D. Stinson. Something About All or Nothing (Transforms). Available fromhttp://cacr.math.uwaterloo.ca/~dstinson/papers/AON.ps, 1999.

  26. L. Trevisan. Construction of Extractors Using PseudoRandom Generators. In Proc. of STOC, pp. 141–148, 1999.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, New York, 10598, USA

    Ran Canetti & Shai Halevi

  2. Lab. for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA, 02149, USA

    Yevgeniy Dodis & Amit Sahai

  3. IBM T.J. Watson Research Center and Department of Computer Science, Technion, Haifa, 32000, Israel

    Eyal Kushilevitz

Authors
  1. Ran Canetti

    You can also search for this author inPubMed Google Scholar

  2. Yevgeniy Dodis

    You can also search for this author inPubMed Google Scholar

  3. Shai Halevi

    You can also search for this author inPubMed Google Scholar

  4. Eyal Kushilevitz

    You can also search for this author inPubMed Google Scholar

  5. Amit Sahai

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Electrical Engineering - ESAT / COSIC, Katholieke Universiteit Leuven, Kardinaal Mercierlaan 94, B-3001, Heverlee, Belgium

    Bart Preneel

Rights and permissions

Copyright information

© 2000 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Canetti, R., Dodis, Y., Halevi, S., Kushilevitz, E., Sahai, A. (2000). Exposure-Resilient Functions and All-or-Nothing Transforms. In: Preneel, B. (eds) Advances in Cryptology — EUROCRYPT 2000. EUROCRYPT 2000. Lecture Notes in Computer Science, vol 1807. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45539-6_33

Download citation

Publish with us

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