The complexity of online memory checking

ABSTRACT

We consider the problem of storing a large file on a remote and unreliable server. To verify that the file has not been corrupted, a user could store a small private (randomized) “fingerprint” on his own computer. This is the setting for the well-studied authentication problem in cryptography, and the required fingerprint size is well understood. We study the problem of sublinear authentication: suppose the user would like to encode and store the file in a way that allows him to verify that it has not been corrupted, but without reading the entire file. If the user only wants to read q bits of the file, how large does the size s of the private fingerprint need to be? We define this problem formally, and show a tight lower bound on the relationship between s and q when the adversary is not computationally bounded, namely: s × q = Ω(n), where n is the file size. This is an easier case of the online memory checking problem, introduced by Blum et al. [1991], and hence the same (tight) lower bound applies also to that problem.

It was previously shown that, when the adversary is computationally bounded, under the assumption that one-way functions exist, it is possible to construct much better online memory checkers. The same is also true for sublinear authentication schemes. We show that the existence of one-way functions is also a necessary condition: even slightly breaking the s × q = Ω(n) lower bound in a computational setting implies the existence of one-way functions.

REFERENCES

• 1: Miklós Ajtai, The invasiveness of off-line memory checking, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509981]
• 2: Ateniese, G., Burns, R., Curtmola, R., Herring, J., Kissner, L., Peterson, Z., and Song, D. 2007. Provable data possession at untrusted stores. Cryptology ePrint Archive, Report 2007/202.
• 3: L. Babai , P. G. Kimmel, Randomized Simultaneous Messages: Solution Of A Problem Of Yao In Communication Complexity, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.239, June 24-27, 1997
• 4: Amos Beimel , Yuval Ishai , Eyal Kushilevitz, General constructions for information-theoretic private information retrieval, Journal of Computer and System Sciences, v.71 n.2, p.213-247, August 2005 [doi>10.1016/j.jcss.2005.03.002]
• 5: Amos Beimel , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, One-way functions are essential for single-server private information retrieval, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.89-98, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301277]
• 6: Mihir Bellare , Oded Goldreich , Shafi Goldwasser, Incremental Cryptography: The Case of Hashing and Signing, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.216-233, August 21-25, 1994
• 7: Mihir Bellare , Oded Goldreich , Shafi Goldwasser, Incremental cryptography and application to virus protection, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.45-56, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225080]
• 8: Mihir Bellare , Russell Impagliazzo , Moni Naor, Does Parallel Repetition Lower the Error in Computationally Sound Protocols?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p.374, October 19-22, 1997
• 9: Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust pcps of proximity, shorter pcps and applications to coding, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007361]
• 10: Eli Ben-Sasson , Madhu Sudan, Simple PCPs with poly-log rate and query complexity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060631]
• 11: Blum, M., Evans, W. S., Gemmell, P., Kannan, S., and Naor, M. 1994. Checking the correctness of memories. Algorithmica 12, 2/3, 225--244.
• 12: Manuel Blum , Sampath Kannan, Designing programs that check their work, Journal of the ACM (JACM), v.42 n.1, p.269-291, Jan. 1995 [doi>10.1145/200836.200880]
• 13: Bowers, K. D., Juels, A., and Oprea, A. 2008. Proofs of retrievability: Theory and implementation. Cryptology ePrint Archive, Report 2008/175.
• 14: Benny Chor , Eyal Kushilevitz , Oded Goldreich , Madhu Sudan, Private information retrieval, Journal of the ACM (JACM), v.45 n.6, p.965-981, Nov. 1998 [doi>10.1145/293347.293350]
• 15: Dwaine Clarke , G. Edward Suh , Blaise Gassend , Ajay Sudan , Marten van Dijk , Srinivas Devadas, Towards Constant Bandwidth Overhead Integrity Checking of Untrusted Data, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.139-153, May 08-11, 2005
• 16: Crescenzo, G. Di, Malkin, T., and Ostrovsky, R. 2000. Single database private information retrieval implies oblivious transfer. In Proceedings of EUROCRYPT. 122--138.
• 17: Dwork, C., Naor, M., Rothblum, G. N., and Vaikuntanathan, V. 2009. How efficient can memory checking be? In Proceedings of the Theory of Cryptography Conference (TCC), to appear.
• 18: Fiat, A., and Tassa, T. 2001. Dynamic traitor tracing. J. Cryptology 14, 3, 211--223.
• 19: Some improvements to total degree tests, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.190, January 04-06, 1995
• 20: Pete Gemmell , Moni Naor, Codes for interactive authentication, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.355-367, January 1994, Santa Barbara, California, United States
• 21: Gilbert, E. N., MacWilliams, F. J., and Sloane, N. J. A. 1974. Codes which detect deception. Bell Syst. Tech. J. 53, 3, 405--424.
• 22: O. Goldreich, Towards a theory of software protection and simulation by oblivious RAMs, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.182-194, January 1987, New York, New York, United States [doi>10.1145/28395.28416]
• 23: Oded Goldreich, Foundations of Cryptography: Volume 1, Cambridge University Press, New York, NY, 2006
• 24: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 25: Oded Goldreich , Rafail Ostrovsky, Software protection and simulation on oblivious RAMs, Journal of the ACM (JACM), v.43 n.3, p.431-473, May 1996 [doi>10.1145/233551.233553]
• 26: Oded Goldreich , Madhu Sudan, Locally testable codes and PCPs of almost-linear length, Journal of the ACM (JACM), v.53 n.4, p.558-655, July 2006 [doi>10.1145/1162349.1162351]
• 27: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 28: R. Impagliazzo, A personal view of average-case complexity, Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), p.134, June 19-22, 1995
• 29: R. Impagliazzo , M. Luby, One-way functions are essential for complexity based cryptography, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.230-235, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63483]
• 30: Ari Juels , Burton S. Kaliski, Jr., Pors: proofs of retrievability for large files, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315317]
• 31: Justesen, J. 1972. Class of constructive asymptotically good algebraic codes. IEEE Trans. Inf. Theory 18, 5, 652--656.
• 32: Katz, J., and Koo, C.-Y. 2005. On constructing universal one-way hash functions from arbitrary one-way functions. Cryptology ePrint Archive, Report 2005/328.
• 33: Jonathan Katz , Luca Trevisan, On the efficiency of local decoding procedures for error-correcting codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.80-86, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335315]
• 34: Joe Kilian, A note on efficient zero-knowledge proofs and arguments (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.723-732, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129782]
• 35: Ilan Kremer , Noam Nisan , Dana Ron, On randomized one-round communication complexity, Computational Complexity, v.8 n.1, p.21-49, June 1999 [doi>10.1007/s000370050018]
• 36: E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p.364, October 19-22, 1997
• 37: Kushilevitz, E., and Ostrovsky, R. 2000. One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval. In Proceedings of EUROCRYPT. 104--121.
• 38: S. Micali, CS proofs, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, p.436-453, November 20-22, 1994 [doi>10.1109/SFCS.1994.365746]
• 39: Micali, S., Peikert, C., Sudan, M., and Wilson, D. A. 2005. Optimal error correction against computationally bounded noise. In Proceedings of TCC. 1--16.
• 40: Dalit Naor , Moni Naor , Jeffrey B. Lotspiech, Revocation and Tracing Schemes for Stateless Receivers, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.41-62, August 19-23, 2001
• 41: Joseph (Seffi) Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 42: Moni Naor , Guy N. Rothblum, Learning to impersonate, Proceedings of the 23rd international conference on Machine learning, p.649-656, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143926]
• 43: Naor, M., Segev, G., and Smith, A. 2006. Tight bounds for unconditional authentication protocols in the manual channel and shared key models. In Proceedings of CRYPTO. 214--231.
• 44: M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
• 45: Ilan Newman , Mario Szegedy, Public vs. private coin flips in one round communication games (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.561-570, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238004]
• 46: R. Ostrovsky, Efficient computation on oblivious RAMs, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.514-523, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100289]
• 47: Ostrovsky, R., and Wigderson, A. 1993. One-way fuctions are essential for non-trivial zero-knowledge. In Proceedings of ISTCS. 3--17.
• 48: J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100269]
• 49: Shacham, H., and Waters, B. 2008. Compact proofs of retrievability. Cryptology ePrint Archive, Report 2008/073.
• 50: Wegman, M. N., and Carter, L. 1981. New hash functions and their use in authentication and set equality. J. Comput. Syst. Scie. 22, 265--279.
• 51: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]

INDEX TERMS

Primary Classification:
  E. Data
  E.0 GENERAL

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Security, Theory

Keywords:
Memory checking, authentication