A Low-Depth Homomorphic Circuit for Logistic Regression Model Training

Eric Crockett

Abstract

Machine learning is an important tool for analyzing large data sets, but its use on sensitive data may be limited by regulation. One solution to this problem is to perform machine learning tasks on encrypted data using homomorphic encryption, which enables arbitrary computation on encrypted data. We take a fresh look at one specific task: training a logistic regression model on encrypted data. The most important factor in the efficiency of a solution is the multiplicative depth of the homomorphic circuit. Two prior works have given circuits with multiplicative depth of five per training iteration. We optimize one of these solutions, by Han et al. [Han+18], and give a circuit with half the multiplicative depth per iteration on average, which allows us to perform twice as many training iterations in the same amount of time. In the process of improving the state-of-the-art circuit for this task, we identify general techniques to improve homomorphic circuit design for two broad classes of algorithms: iterative algorithms, and algorithms based on linear algebra over real numbers. First, we formalize the encoding scheme from [Han+18] for encoding linear algebra objects as plaintexts in the CKKS homomorphic encryption scheme. We also show how to use this encoding to homomorphically compute many basic linear algebra operations, including novel operations not discussed in prior work. This “toolkit” is generic, and can be used in any application based on linear algebra. Second, we demonstrate how generic compiler techniques for loop optimization can be used to reduce the multiplicative depth of iterative algorithms.

Note: Fixed several small typos.

Available format(s)
Category
Applications
Publication info
Published elsewhere. MAJOR revision.Workshop on Applied Homomorphic Cryptography 2020
Keywords
applicationshomomorphic encryptionckkslogistic regressionmodel traininglinear algebra
Contact author(s)
ericcro @ amazon com
History
2021-01-09: last of 3 revisions
See all versions
Short URL
https://ia.cr/2020/1483

CC BY

BibTeX

@misc{cryptoeprint:2020/1483,
author = {Eric Crockett},
title = {A Low-Depth Homomorphic Circuit for Logistic Regression Model Training},
howpublished = {Cryptology ePrint Archive, Paper 2020/1483},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1483}},
url = {https://eprint.iacr.org/2020/1483}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.