Privacy-preserving Naive Bayes classifiers secure against the substitution-then-comparison attack

Naive Bayes (NB) is a simple but highly practical classifier, with a wide range of applications including spam filters, cancer diagnosis and face recognition, to name a few examples only. Consider a situation where a user requests a classification service from a NB classifier server, both the user and the server do not want to reveal their private data to each other. This paper focuses on constructing a privacy-preserving NB classifier that is resistant to an easy-to-perform, but difficult-to-detect attack, which we call the substitution-then-comparison (STC) attack. Without resorting to fully homomorphic encryptions, which has a high computational overhead, we propose a scheme which avoids information leakage under the STC attack. Our key technique involves the use of a “double-blinding” technique, and we show how to combine it with additively homomorphic encryptions and oblivious transfer to hide both parties' privacy. Furthermore, a completed evaluation shows that the construction is highly practical - most of the computations are in the server's offline phase, and the overhead of online computation and communication is small for both parties.