  Due to the rising privacy demand in data mining, Homomorphic Encryption (HE)
is receiving more and more attention recently for its capability to do
computations over the encrypted field. By using the HE technique, it is
possible to securely outsource model learning to the not fully trustful but
powerful public cloud computing environments. However, HE-based training scales
badly because of the high computation complexity. It is still an open problem
whether it is possible to apply HE to large-scale problems. In this paper, we
propose a novel general distributed HE-based data mining framework towards one
step of solving the scaling problem. The main idea of our approach is to use
the slightly more communication overhead in exchange of shallower computational
circuit in HE, so as to reduce the overall complexity. We verify the efficiency
and effectiveness of our new framework by testing over various data mining
algorithms and benchmark data-sets. For example, we successfully train a
logistic regression model to recognize the digit 3 and 8 within around 5
minutes, while a centralized counterpart needs almost 2 hours.
