Welcome to the resource topic for 2024/1366
Title:
Adaptive Successive Over-Relaxation Method for a Faster Iterative Approximation of Homomorphic Operations
Authors: Jungho Moon, Zhanibek Omarov, Donghoon Yoo, Yongdae An, Heewon Chung
Abstract:Homomorphic encryption is a cryptographic technique that enables arithmetic
operations to be performed on encrypted data. However, word-wise fully
homomorphic encryption schemes, such as BGV, BFV, and CKKS schemes, only
support addition and multiplication operations on ciphertexts. This limitation
makes it challenging to perform non-linear operations directly on the
encrypted data. To address this issue, prior research has proposed efficient
approximation techniques that utilize iterative methods, such as functional
composition, to identify optimal polynomials. These approximations are
designed to have a low multiplicative depth and a reduced number of
multiplications, as these criteria directly impact the performance of the
approximated operations.
In this paper, we propose a novel method, named as adaptive successive
over-relaxation (aSOR), to further optimize the approximations used in
homomorphic encryption schemes. Our experimental results show that the aSOR
method can significantly reduce the computational effort required for these
approximations, achieving a reduction of 2–9 times compared to state-of-the-art
methodologies. We demonstrate the effectiveness of the aSOR method by applying
it to a range of operations, including sign, comparison, ReLU, square root,
reciprocal of m-th root, and division. Our findings suggest that the aSOR method
can greatly improve the efficiency of homomorphic encryption for performing
non-linear operations.
ePrint: https://eprint.iacr.org/2024/1366
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .