  Outlier detection is widely used in practice to track the anomaly on
incremental datasets such as network traffic and system logs. However, these
datasets often involve sensitive information, and sharing the data to third
parties for anomaly detection raises privacy concerns. In this paper, we
present a privacy-preserving outlier detection protocol (PPOD) for incremental
datasets. The protocol decomposes the outlier detection algorithm into several
phases and recognises the necessary cryptographic operations in each phase. It
realises several cryptographic modules via efficient and interchangeable
protocols to support the above cryptographic operations and composes them in
the overall protocol to enable outlier detection over encrypted datasets. To
support efficient updates, it integrates the sliding window model to
periodically evict the expired data in order to maintain a constant update
time. We build a prototype of PPOD and systematically evaluates the
cryptographic modules and the overall protocols under various parameter
settings. Our results show that PPOD can handle encrypted incremental datasets
with a moderate computation and communication cost.
