The k-nearest neighbor query is widely used in various applications. Due to security and privacy concerns, it is important to protect the confidentiality of sensitive information. However, existing solutions either violate the privacy requirements (i.e., data, query, result or indirect privacy) or scale badly with the data size. We first highlight the vulnerabilities of additive homomorphic encryption-based approaches. We then conduct in-depth research on the Privacy-Preserving k-Nearest Neighbor (PPkNN) query to simultaneously address the aforementioned concerns. Using the secret sharing technique and a model of two non-colluding servers, we design a Basic PPkNN (BPPkNN) protocol for arbitrary dimensional datasets. BPPkNN obliviously rearranges the dataset in a divide-and-conquer manner, reducing interaction rounds from linear to sublinear. We further propose a Voronoi-based PPkNN (VPPkNN) protocol for geo-location datasets, which uses the Voronoi diagram for index construction and a greedy algorithm for index compression. By obliviously accessing only a small portion of the dataset, VPPkNN significantly reduces expensive operations. We prove that our protocols simultaneously preserve data, query, result, and indirect privacy. Experimental results demonstrate that our protocols outperform existing approaches by at least an order of magnitude in query response time and, for the first time, scale to datasets with one million points.