TY - JOUR
T1 - Efficient Lattice Gadget Decomposition Algorithm with Bounded Uniform Distribution
AU - Jeon, Sohyun
AU - Lee, Hyang Sook
AU - Park, Jeongeun
N1 - Publisher Copyright:
CCBY
PY - 2021
Y1 - 2021
N2 - A gadget decomposition algorithm is commonly used in many advanced lattice cryptography applications which support homomorphic operations over ciphertexts to control the noise growth. For a special structure of a gadget, the algorithm is digit decomposition. If such algorithm samples from a subgaussian distribution, that is, the output is randomized, it gives more benefits on output quality. One of the important advantages is Pythagorean additivity which makes the resulting noise contained in a ciphertext grow much less than naive digit decomposition. Therefore, the error analysis becomes cleaner and tighter than the use of other measures like Euclidean norm and infinity norm. Even though such advantage can also be achieved by use of discrete Gaussian sampling, it is not attractive for practical performance due to a large factor in resulting noise and the complex computation of the exponential function, whereas a more relaxed probability condition is required for a subgaussian distribution. Nevertheless, subgaussian sampling has barely received an attention so far, thus no practical algorithms was implemented before an efficient algorithm is presented by Genis et al., recently. In this paper, we present a practically efficient gadget decomposition algorithm where output follows a subgaussian distribution. We parallelize the existing practical subgaussian gadget decomposition algorithm, using a bounded uniform distribution. Our algorithm is divided into two independent subalgorithms and only one algorithm depends on the input. Therefore, the other algorithm can be considered as precomputation. As an experimental result, our algorithm performs over 50% better than the existing algorithm.
AB - A gadget decomposition algorithm is commonly used in many advanced lattice cryptography applications which support homomorphic operations over ciphertexts to control the noise growth. For a special structure of a gadget, the algorithm is digit decomposition. If such algorithm samples from a subgaussian distribution, that is, the output is randomized, it gives more benefits on output quality. One of the important advantages is Pythagorean additivity which makes the resulting noise contained in a ciphertext grow much less than naive digit decomposition. Therefore, the error analysis becomes cleaner and tighter than the use of other measures like Euclidean norm and infinity norm. Even though such advantage can also be achieved by use of discrete Gaussian sampling, it is not attractive for practical performance due to a large factor in resulting noise and the complex computation of the exponential function, whereas a more relaxed probability condition is required for a subgaussian distribution. Nevertheless, subgaussian sampling has barely received an attention so far, thus no practical algorithms was implemented before an efficient algorithm is presented by Genis et al., recently. In this paper, we present a practically efficient gadget decomposition algorithm where output follows a subgaussian distribution. We parallelize the existing practical subgaussian gadget decomposition algorithm, using a bounded uniform distribution. Our algorithm is divided into two independent subalgorithms and only one algorithm depends on the input. Therefore, the other algorithm can be considered as precomputation. As an experimental result, our algorithm performs over 50% better than the existing algorithm.
KW - Bounded uniform distribution
KW - Encryption
KW - Gadget decomposition
KW - Gaussian distribution
KW - Heuristic algorithms
KW - Lattice gadget
KW - Lattices
KW - Licenses
KW - Matrix decomposition
KW - Random variables
KW - Subgaussian distribution
UR - http://www.scopus.com/inward/record.url?scp=85100504330&partnerID=8YFLogxK
U2 - 10.1109/ACCESS.2021.3053288
DO - 10.1109/ACCESS.2021.3053288
M3 - Article
AN - SCOPUS:85106844165
JO - IEEE Access
JF - IEEE Access
SN - 2169-3536
ER -