Sketching in Adversarial Environments  

      Ilya Mironov       Moni Naor      Gil Segev     

Abstract:

This paper introduces the adversarial sketch model, that 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.

In the adversarial sketch model several parties are interested in computing a joint function in the presence of an adversary that dynamically chooses their inputs. These inputs are provided to the parties in an on-line manner, and each party incrementally updates a compressed sketch of its input. The parties are not allowed to communicate, they do not share any secret information, and any public information they share is known to the adversary in advance. Then, the parties engage in a protocol in order to evaluate the function on their current inputs using only the compressed sketches.

The main technical contribution is an explicit and deterministic encoding scheme that enjoys two seemingly conflicting properties: incrementality and high distance.

Paper: PDF. Slides: ppt.

Related On-Line Papers:

Back to: On-Line PublicationsRecent Papers

Back Home