Recommender systems rely on large datasets of historical data and entail serious privacy risks. A server offering Recommendation as a Service to a client might leak more information than necessary regarding its recommendation model and dataset. At the same time, the disclosure of the client's preferences to the server is also a matter of concern. Devising privacy-preserving protocols using general cryptographic primitives (e.g., secure multi-party computation or homomorphic encryption), is a typical approach to overcome privacy concerns, but in conjunction with state-of-the-art recommender systems often yields far-from-practical solutions. In this paper, we tackle this problem from the direction of constructing crypto-friendly machine learning algorithms. In particular, we propose CryptoRec, a secure two-party computation protocol for Recommendation as a Service, which encompasses a novel recommender system. This model possesses two interesting properties: (1) It models user-item interactions in an item-only latent feature space in which personalized user representations are automatically captured by an aggregation of pre-learned item features. This means that a server with a pre-trained model can provide recommendations for a client whose data is not in its training set. Nevertheless, re-training the model with the client's data still improves accuracy. (2) It only uses addition and multiplication operations, making the model straightforwardly compatible with homomorphic encryption schemes. We demonstrate the efficiency and accuracy of CryptoRec on three real-world datasets. CryptoRec allows a server with thousands of items to privately answer a prediction query within a few seconds on a single PC, while its prediction accuracy is still competitive with state-of-the-art recommender systems computing over clear data.