Paper 2009/195

Secure Evaluation of Private Linear Branching Programs with Medical Applications

Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Ahmad-Reza Sadeghi, and Thomas Schneider


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.

Note: This is the full version of the ESORICS 2009 paper.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ESORICS 2009
Contact author(s)
thomas schneider @ trust rub de
2009-06-29: revised
2009-05-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mauro Barni and Pierluigi Failla and Vladimir Kolesnikov and Riccardo Lazzeretti and Ahmad-Reza Sadeghi and Thomas Schneider},
      title = {Secure Evaluation of Private Linear Branching Programs with Medical Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2009/195},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.