On Perfect and Adaptive Security in Exposure-Resilient Cryptography

  • Yevgeniy Dodis
  • Amit Sahai
  • Adam Smith
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


We consider the question of adaptive security for two related cryptographic primitives: all-or-nothing transforms and exposure-resilient functions. Both are concerned with retaining security when an intruder learns some bits of a string which is supposed to be secret: all-or-nothing transforms (AONT) protect their input even given partial knowledge of the output; exposure-resilient functions (ERF) hide their output even given partial exposure of their input. Both of these primitives can be defined in the perfect, statistical and computational settings and have a variety of applications in cryptography. In this paper, we study how these notions fare against adaptive adversaries, who may choose which positions of a secret string to observe on the fly.

In the perfect setting, we prove a new, strong lower bound on the constructibility of (perfect) AONT. This applies to both standard and adaptively secure AONT. In particular, to hide an input as short as log n bits, the adversary must see no more than half of the n-bit output. This bound also provides a new impossibility result on the existence of (ramp) secret-sharing schemes [6] and relates to a combinatorial problem of independent interest: finding “balanced” colorings of the hypercube.

In the statistical setting, we show that adaptivity adds strictly more power to the adversary. We relate and reduce the construction of adaptive ERF's to that of almost-perfect resilient functions [19], for which the adversary can actually set some of the input positions and still learn nothing about the output. We give a probabilistic construction of these functions which is essentially optimal and substantially improves on previous constructions of [19, 5]. As a result, we get nearly optimal adaptively secure ERF's and AONT's. Finally, extending the statistical construction we obtain optimal computational adaptive ERF's, “public-value” AONT's and resilient functions.


Block Cipher Pseudorandom Generator Perfect Setting Computational Setting Balance Coloring 
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.


  1. 1.
    M. Bellare and A. Boldyreva. The Security of Chaffing and Winnowing. In Proc. of Asiacrypt, 2000.Google Scholar
  2. 2.
    M. Bellare, J. Rompel. Randomness-Efficient Oblivious Sampling. In Proc. of 35th FOCS, pp. 276–287, 1994.Google Scholar
  3. 3.
    C. Benett, G. Brassard, J. Robert. Privacy Amplification by public discussion. In SIAM J. on Computing, pp. 17(2):210–229, 1988.CrossRefGoogle Scholar
  4. 4.
    J. Bierbrauer, K. Gopalakrishnan, D. Stinson. Orthogonal Arrays, resilient functions, error-correcting codes and linear programming bounds. In SIAM J. of Discrete Math, 9: 424–452, 1996.zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    J. Bierbrauer, H. Schellwat. Almost Independent and Weakly Biased Arrys: Efficient Constructions and Cryptologic Applications. In Proc. of CRYPTO, pp. 531–543, 2000.Google Scholar
  6. 6.
    G. R. Blakley and C. Meadows. Security of Ramp Schemes. In Proc. of CRYPTO, pp. 242–268, 1984.Google Scholar
  7. 7.
    M. Blaze. High Bandwidth Encryption with low-bandwidth smartcards. In Fast Software Encryption, pp. 33–40, 1996.Google Scholar
  8. 8.
    C. Blundo, A. De Santis, U. Vaccaro. Efficient Sharing of Many Secrets. In Proc. of STACS, LNCS 665, pp. 692–703, 1993.Google Scholar
  9. 9.
    V. Boyko. On the Security Properties of the OAEP as an All-or-Nothing Transform. In Proc. of Crypto, pp. 503–518, 1999.Google Scholar
  10. 10.
    R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz and A. Sahai. Exposure-Resilient Functions and All-Or-Nothing Transforms. In Proc. of EuroCrypt, 2000.Google Scholar
  11. 11.
    L. Carter and M. Wegman. Universal classes of hash functions. JCSS, vol. 18, pp. 143–154, 1979.zbMATHMathSciNetGoogle Scholar
  12. 12.
    B. Chor, J. Friedman, O. Goldreich, J. Håstad, S. Rudich, R. Smolensky. The Bit Extraction Problem or t-resilient Functions. In Proc. of FOCS, pp. 396–407, 1985.Google Scholar
  13. 13.
    Y. Dodis. Exposure-Resilient Cryptography. Ph.D. Thesis., MIT, 2000.Google Scholar
  14. 14.
    A. Desai. The security of All-or-Nothing Encryption: Protecting Against Exhaustive Key Search In Proc. of CRYPTO, pp. 359–375, 2000.Google Scholar
  15. 15.
    J. Friedman. On the Bit Extraction Problem In Proc. of FOCS, pp. 314–319, 1992.Google Scholar
  16. 16.
    O. Goldreich. Foundations of Cryptography (Fragments of a Book). URL: html/frag.html
  17. 17.
    W.-A. Jackson and K. Martin. A Combinatorial Interpretation of Ramp Schemes Australasian Journal of Combinatorics, 14 (1996), 51–60.zbMATHMathSciNetGoogle Scholar
  18. 18.
    M. Jakobsson, J. Stern, M. Yung. Scramble All, Encrypt Small. In Proc. of Fast Software Encryption, pp. 95–111, 1999.Google Scholar
  19. 19.
    K. Kurosawa, T. Johansson and D. Stinson. Almost k-wise independent sample spaces and their cryptologic applications. Submitted to J. of Cryptology, preliminary version appeared in Proc. of EuroCrypt, pp. 409–421, 1997.Google Scholar
  20. 20.
    S. Matyas, M. Peyravian and A. Roginsky. Encryption of Long Blocks Using a Short-Block Encryption Procedure. Available at
  21. 21.
    W. Ogata and K. Kurosawa. Some Basic Properties of General Nonperfect Secret Sharing Schemes. Journal of Universal Computer Science, Vol.4, No. 8 (1998), pp. 690–704.zbMATHMathSciNetGoogle Scholar
  22. 22.
    L. H. Ozarow and A. D. Wyner. Wire-Tap Channel II In Proc. of EUROCRYPT, pp. 33–50, 1984.Google Scholar
  23. 23.
    R. Rivest. All-or-Nothing Encryption and the Package Transform. In Fast Software Encryption, LNCS, 1267: 210–218, 1997.CrossRefGoogle Scholar
  24. 24.
    R. Rivest. Chaffing and Winnowing: Confidentiality without Encryption. CryptoBytes (RSA Laboratories), 4(1):12–17, 1998.Google Scholar
  25. 25.
    A. Shamir. How to share a secret. In Communic. of the ACM, 22:612–613, 1979.zbMATHCrossRefMathSciNetGoogle Scholar
  26. 26.
    S. U. Shin, K. H. Rhee. Hash functions and the MAC using all-or-nothing property. In Proc. of Public Key Cryptography, LNCS, 1560:263–275, 1999.CrossRefGoogle Scholar
  27. 27.
    L. Trevisan and S. Vadhan. Extracting randomness from samplable distributions In Proc. of FOCS, 2000.Google Scholar
  28. 28.
    U. Vazirani. Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Semi-Random Sources. In Combinatorica, 7(4):375–392, 1987.zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Yevgeniy Dodis
    • 1
  • Amit Sahai
    • 2
  • Adam Smith
    • 3
  1. 1.Department of Computer ScienceNew York UniversityNew YorkUSA
  2. 2.Department of Computer SciencePrinceton UniversityPrincetonUSA
  3. 3.Laboratory for Computer ScienceMassachusetts Institute of TechnologyCambridgeUSA

Personalised recommendations