  Machine learning models are often provisioned as a cloud-based service where
the clients send their data to the service provider to obtain the result. This
setting is commonplace due to the high value of the models, but it requires the
clients to forfeit the privacy that the query data may contain. Homomorphic
encryption (HE) is a promising technique to address this adversity. With HE,
the service provider can take encrypted data as a query and run the model
without decrypting it. The result remains encrypted, and only the client can
decrypt it. All these benefits come at the cost of computational cost because
HE turns simple floating-point arithmetic into the computation between long
(degree over 1024) polynomials. Previous work has proposed to tailor deep
neural networks for efficient computation over encrypted data, but already high
computational cost is again amplified by HE, hindering performance improvement.
In this paper we show hyperdimensional computing can be a rescue for
privacy-preserving machine learning over encrypted data. We find that the
advantage of hyperdimensional computing in performance is amplified when
working with HE. This observation led us to design HE-HDC, a machine-learning
inference system that uses hyperdimensional computing with HE. We carefully
structure the machine learning service so that the server will perform only the
HE-friendly computation. Moreover, we adapt the computation and HE parameters
to expedite computation while preserving accuracy and security. Our
experimental result based on real measurements shows that HE-HDC outperforms
existing systems by 26~3000 times with comparable classification accuracy.
