Recommender systems have become an indispensable component in online services during recent years. Effective recommendation is essential for improving the services of various online business applications. However, serious privacy concerns have been raised on recommender systems requiring the collection of users' private information for recommendation. At the same time, the success of e-commerce has generated massive amounts of information, making scalability a key challenge in the design of recommender systems. As such, it is desirable for recommender systems to protect users' privacy while achieving high-quality recommendations with low-complexity computations. This paper proposes a scalable privacy-preserving item-based top-N recommendation solution, which can achieve high-quality recommendations with reduced computation complexity while ensuring that users' private information is protected. Furthermore, the computation complexity of the proposed method increases slowly as the number of users increases, thus providing high scalability for privacy-preserving recommender systems. More specifically, the proposed approach consists of two key components: (1) MinHash-based similarity estimation and (2) client-side privacy-preserving prediction generation. Our theoretical and experimental analysis using real-world data demonstrates the efficiency and effectiveness of the proposed approach.