Cryptology ePrint Archive: Report 2020/1483
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.
Category / Keywords: applications / applications, homomorphic encryption, ckks, logistic regression, model training, linear algebra
Original Publication (with major differences): Workshop on Applied Homomorphic Cryptography 2020
Date: received 25 Nov 2020, last revised 8 Jan 2021
Contact author: ericcro at amazon com
Available format(s): PDF | BibTeX Citation
Note: Fixed several small typos.
Version: 20210109:010417 (All versions of this report)
Short URL: ia.cr/2020/1483
[ Cryptology ePrint archive ]