Skyline queries are an important type of multi-criteria analysis with diverse applications in practice (e.g., personalized services and intelligent transport systems). In this paper, we study how to answer skyline queries efficiently and in a privacy-preserving way when the data are sensitive and distributedly owned by multiple parties. We adopt the classical honest-but-curious attack model, and design a suite of efficient protocols for skyline queries over horizontally partitioned data. We analyze in detail the efficiency of each of the proposed protocols as well as their privacy guarantees.