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.
Back to: On-Line Publications, Recent Papers