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