Sketching in adversarial environments

ABSTRACT

We formalize a realistic model for computations over massive data sets. The model, referred to as the {\em adversarial sketch model}, unifies the well-studied sketch and data stream models together with a cryptographic flavor that considers the execution of protocols in "hostile environments", and provides a framework for studying the complexity of many tasks involving massive data sets.

The adversarial sketch model consists of several participating parties: honest parties, whose goal is to compute a pre-determined function of their inputs, and an adversarial party. Computation in this model proceeds in two phases. In the first phase, the adversarial party chooses the inputs of the honest parties. These inputs are sets of elements taken from a large universe, and provided to the honest parties in an on-line manner in the form of a sequence of insert and delete operations. Once an operation from the sequence has been processed it is discarded and cannot be retrieved unless explicitly stored. During this phase the honest parties are not allowed to communicate. Moreover, they do not share any secret information and any public information they share is known to the adversary in advance. In the second phase, the honest parties engage in a protocol in order to compute a pre-determined function of their inputs.

In this paper we settle the complexity (up to logarithmic factors) of two fundamental problems in this model: testing whether two massive data sets are equal, and approximating the size of their symmetric difference. We construct explicit and efficient protocols with sublinear sketches of essentially optimal size, poly-logarithmic update time during the first phase, and poly-logarithmic communication and computation during the second phase. Our main technical contribution is an explicit and deterministic encoding scheme that enjoys two seemingly conflicting properties: incrementality and high distance, which may be of independent interest.

REFERENCES

• 1: James Abello , Panos M. Pardalos , Mauricio G. C. Resende, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 2: P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Geometric approximation via core sets. Combinatorial and Computational Geometry - MSRI Publications, pages 1--30, 2005.
• 3: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 4: 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
• 5: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 6: Mihai Bādoiu , Sariel Har-Peled , Piotr Indyk, Approximate clustering via core-sets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509947]
• 7: Ziv Bar-Yossef , Christos H. Papadimitriou, The complexity of massive data set computations, University of California at Berkeley, Berkeley, CA, 2002
• 8: Ziv Bar-Yossef , T. S. Jayram , Robert Krauthgamer , Ravi Kumar, Approximating Edit Distance Efficiently, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.550-559, October 17-19, 2004 [doi>10.1109/FOCS.2004.14]
• 9: 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
• 10: M. Bellare and D. Micciancio. A new paradigm for collision-free hashing: Incrementality at reduced cost. In EUROCRYPT ’97, pages 163--192, 1997.
• 11: M. Blum, W. S. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the correctness of memories. Algorithmica, 12(2/3):225--244, 1994.
• 12: Dan Boneh , Matthew K. Franklin, An Efficient Public Key Traitor Tracing Scheme, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.338-353, August 15-19, 1999
• 13: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 14: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Computer Networks and ISDN Systems, v.29 n.8-13, p.1157-1166, Sep. 1997
• 15: E. J. Candès and T. Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. on Infor. Theory, 52(12):5406--5425, 2006.
• 16: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 17: G. Cormode and S. Muthukrishnan. Combinatorial algorithms for compressed sensing. In SIROCCO, pages 280--294, 2006.
• 18: D. L. Donoho. Compressed sensing. IEEE Trans. on Infor. Theory, 52(4):1289--1306, 2006.
• 19: Tomas Feder , Moni Naor , Eyal Kushilevitz , Noam Nisan, Amortized Communication Complexity, SIAM Journal on Computing, v.24 n.4, p.736-750, Aug. 1995 [doi>10.1137/S0097539792235864]
• 20: Joan Feigenbaum , Yuval Ishai , Tal Malkin , Kobbi Nissim , Martin J. Strauss , Rebecca N. Wright, Secure multiparty computation of approximations, ACM Transactions on Algorithms (TALG), v.2 n.3, p.435-472, July 2006 [doi>10.1145/1159892.1159900]
• 21: Joan Feigenbaum , Sampath Kannan , Martin J. Strauss , Mahesh Viswanathan, An Approximate L¹-Difference Algorithm for Massive Data Streams, SIAM Journal on Computing, v.32 n.1, p.131-151, 2003 [doi>10.1137/S0097539799361701]
• 22: R. Gennaro, S. Halevi, and T. Rabin. Secure hash-and-sign signatures without the random oracle. In EUROCRYPT ’99, pages 123--139, 1999.
• 23: Phillip B. Gibbons , Yossi Matias, Synopsis data structures for massive data sets, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.909-910, January 17-19, 1999, Baltimore, Maryland, United States
• 24: A. C. Gilbert , M. J. Strauss , J. A. Tropp , R. Vershynin, One sketch for all: fast algorithms for compressed sensing, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250824]
• 25: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 26: Monika R. Henzinger , Prabhakar Raghavan , Sridhar Rajagopalan, Computing on data streams, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 27: Piotr Indyk, Explicit constructions for compressed sensing of sparse signals, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.30-33, January 20-22, 2008, San Francisco, California
• 28: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 29: P. Indyk and D. P. Woodruff. Polylogarithmic private approximations and efficient matching. In 3rd TCC, pages 245--264, 2006.
• 30: 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]
• 31: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces, SIAM Journal on Computing, v.30 n.2, p.457-474, 2000 [doi>10.1137/S0097539798347177]
• 32: T. Moran, M. Naor, and G. Segev. Deterministic history-independent strategies for storing information on write-once memories. In 34th ICALP, pages 303--315, 2007.
• 33: 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]
• 34: 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]
• 35: Naom Nisan , Amnon Ta-Shma, Extracting randomness: a survey and new constructions, Journal of Computer and System Sciences, v.58 n.1, p.148-173, Feb. 1999 [doi>10.1006/jcss.1997.1546]
• 36: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
• 37: Michael Siper, Expanders, randomness, or time versus space, Journal of Computer and System Sciences, v.36 n.3, p.379-383, June 1988 [doi>10.1016/0022-0000(88)90035-9]
• 38: Amnon Ta-Shma , Christopher Umans† , David Zuckerman‡, Lossless Condensers, Unbalanced Expanders, And Extractors, Combinatorica, v.27 n.2, p.213-240, March 2007 [doi>10.1007/s00493-007-0053-2]
• 39: H. S. Witsenhausen and A. D. Wyner. Interframe coder for video signals. U.S. patent 4,191,970, 1980.
• 40: 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:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
data stream model., massive data sets, sketch model