  Machine learning (ML) classifiers are invaluable building blocks that have
been used in many fields. High quality training dataset collected from multiple
data providers is essential to train accurate classifiers. However, it raises
concern about data privacy due to potential leakage of sensitive information in
training dataset. Existing studies have proposed many solutions to
privacy-preserving training of ML classifiers, but it remains a challenging
task to strike a balance among accuracy, computational efficiency, and
security. In this paper, we propose Heda, an efficient privacypreserving scheme
for training ML classifiers. By combining homomorphic cryptosystem (HC) with
differential privacy (DP), Heda obtains the tradeoffs between efficiency and
accuracy, and enables flexible switch among different tradeoffs by parameter
tuning. In order to make such combination efficient and feasible, we present
novel designs based on both HC and DP: A library of building blocks based on
partially HC are proposed to construct complex training algorithms without
introducing a trusted thirdparty or computational relaxation; A set of
theoretical methods are proposed to determine appropriate privacy budget and to
reduce sensitivity. Security analysis demonstrates that our solution can
construct complex ML training algorithm securely. Extensive experimental
results show the effectiveness and efficiency of the proposed scheme.
