Sketching in adversarial environments

We formalize a realistic model for computations over massive data sets. The model, referred to as the adversarial sketch model, unifies the well-studied sketch and data stream mod-els together with a cryptographic flavor that considers the execution of protocols in “hostile environments”, and pro-vides a framework for studying the complexity of many tasks involving massive data sets. The adversarial sketch model consists of several partici-pating 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 par-ties 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 par-ties are not allowed to communicate. Moreover, they do not share any secret information and any public informa-tion 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 computa-tion during the second phase. Our main technical contribu-∗Due to space limitations a more complete version is avail-able a