Tight security proofs for the bounded-storage model

ABSTRACT

(MATH) In the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversary's storage capacity is bounded, say by s bits, even if her computational power is unlimited. Assume that a random t-bit string R is either publicly available (e.g. the signal of a deep space radio source) or broadcast by one of the legitimate parties. If s$xi;t, the adversary can store only partial information about R. The legitimate sender Alice and receiver Bob, sharing a short secret key K initially, can therefore potentially generate a very long n-bit one-time pad X with n»|K| about which the adversary has essentially no information, thus at first glance apparently contradicting Shannon's bound on the key size of a perfect cipher.All previous results in the bounded-storage model were partial or far from optimal, for one of the following reasons: either the secret key K had in fact to be longer than the derived one-time pad, or t had to be extremely large (tρns), or the adversary was assumed to be able to store only actual bits of R rather than arbitrary s bits of information about R, or the adversary could obtain a non-negligible amount of information about X.In this paper we prove the first non-restricted security result in the bounded-storage model, exploiting the full potential of the model: K is short, X is very long (e.g. gigabytes), t needs to be only moderately larger than s, and the security proof is optimally strong. In fact, we prove that s/t can be arbitrarily close to 1 and hence the storage bound is essentially optimal.

REFERENCES

• 1: Y. Aumann, Y. Z. Ding, and M. O. Rabin. Everlasting security in the bounded storage model. To appear in IEEE Transactions on Information Theory, Apr. 2002.
• 2: Yonatan Aumann , Michael O. Rabin, Information Theoretically Secure Communication in the Limited Storage Space Model, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.65-79, August 15-19, 1999
• 3: K. Azuma. Weighted sums of certain dependent random variables. Tohoku (MATH). Journal, (19):357--367, 1967.
• 4: Charles H. Bennett , François Bessette , Gilles Brassard , Louis Salvail , John Smolin, Experimental quantum cryptography, Journal of Cryptology, v.5 n.1, p.3-28, 1992
• 5: Christian Cachin , Claude Crepeau , Julien Marcil, Oblivious Transfer with a Memory-Bounded Receiver, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.493, November 08-11, 1998
• 6: Christian Cachin , Ueli M. Maurer, Unconditional Security Against Memory-Bounded Adversaries, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.292-306, August 17-21, 1997
• 7: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 8: Yan Zong Ding, Oblivious Transfer in the Bounded Storage Model, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.155-170, August 19-23, 2001
• 9: Yan Zong Ding , Michael O. Rabin, Provable everlasting security in the bounded storage model, 2001
• 10: Yan Zong Ding , Michael O. Rabin, Hyper-Encryption and Everlasting Security, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.1-26, March 14-16, 2002
• 11: D. Dubhashi and A. Panconesi. Concentration of measure for the analysis of randomised algorithms. draft available at http://www.dsi.uniroma1.it/~ale, Oct. 1998.
• 12: S. Goldwasser and S. Micali. Probabilistic Encryption. Journal of Computer and System Sciences, 28:270--299, 1984.
• 13: J. L. Massey and I. Ingemarsson. The Rip van Winkle cipher - a simple and provably computationally secure cipher with a finite key. In Proc. IEEE Int. Symp. Information Theory (Abstracts), page 146, 1985.
• 14: Ueli M. Maurer, Conditionally-perfect secrecy and a provably-secure randomized cipher, Journal of Cryptology, v.5 n.1, p.53-66, 1992
• 15: U. Maurer. Secret key agreement by public discussion. IEEE Transaction on Information Theory, 39:733--742, 1993.
• 16: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 17: C. E. Shannon. Communication theory of secrecy systems. Bell System Technical Journal, 28:656--715, 1949.
• 18: J. H. Van Lint, Introduction to Coding Theory, Springer-Verlag New York, Inc., Secaucus, NJ, 1998

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

General Terms:
Design, Management, Performance, Security, Theory