  Skyline computation is an increasingly popular query, with broad
applicability in domains such as healthcare, travel and finance. Given the
recent trend to outsource databases and query evaluation, and due to the
proprietary and sometimes highly sensitivity nature of the data (e.g., in
healthcare), it is essential to evaluate skylines on encrypted datasets.
Several research efforts acknowledged the importance of secure skyline
computation, but existing solutions suffer from at least one of the following
shortcomings: (i) they only provide ad-hoc security; (ii) they are
prohibitively expensive; or (iii) they rely on unrealistic assumptions, such as
the presence of multiple non-colluding parties in the protocol.
  Inspired from solutions for secure nearest-neighbors (NN) computation, we
conjecture that the most secure and efficient way to compute skylines is
through result materialization. However, this approach is significantly more
challenging for skylines than for NN queries. We exhaustively study and provide
algorithms for pre-computation of skyline results, and we perform an in-depth
theoretical analysis of this process. We show that pre-computing results while
minimizing storage overhead is NP-hard, and we provide dynamic programming and
greedy heuristics that solve the problem more efficiently, while maintaining
storage at reasonable levels. Our algorithms are novel and applicable to
plain-text skyline computation, but we focus on the encrypted setting where
materialization reduces the cost of skyline computation from hours to seconds.
Extensive experiments show that we clearly outperform existing work in terms of
performance, and our security analysis proves that we obtain a smaller (and
quantifiable) data leakage than competitors.
