Diagnostic and classification algorithms play an important role in data analysis, with applications in areas such as health
care, fault diagnostics, or benchmarking. Branching programs (BP) is a popular representation model for describing the underlying
classification/diagnostics algorithms. Typical application scenarios involve a client who provides data and a service provider
(server) whose diagnostic program is run on client’s data. Both parties need to keep their inputs private.
We present new, more efficient privacy-protecting protocols for remote evaluation of such classification/diagnostic programs.
In addition to efficiency improvements, we generalize previous solutions – we securely evaluate private linear branching programs
(LBP), a useful generalization of BP that we introduce. We show practicality of our solutions: we apply our protocols to the
privacy-preserving classification of medical ElectroCardioGram (ECG) signals and present implementation results. Finally,
we discover and fix a subtle security weakness of the most recent remote diagnostic proposal, which allowed malicious clients
to learn partial information about the program.