IEICE TRANSACTIONS on Fundamentals
Revisiting the Orthogonal Lattice Algorithm in Solving General Approximate Common Divisor Problem
Summary :
Due to the property of supporting arbitrary operation over the encrypted data, fully homomorphic encryption (FHE) has drawn considerable attention since it appeared. Some FHE schemes have been constructed based on the general approximate common divisor (GACD) problem, which is widely believed intractable. Therefore, studying the GACD problem's hardness can provide proper security parameters for these FHE schemes and their variants. This paper aims to study an orthogonal lattice algorithm introduced by Ding and Tao (Ding-Tao algorithm) to solve the GACD problem. We revisit the condition that Ding-Tao algorithm works and obtain a new bound of the GACD samples' number based on geometric series assumption. Simultaneously, we also give an analysis of the bound given in the previous work. To further verify the theoretical results, we conduct experiments on Ding-Tao algorithm under our bound. We show a comparison with the experimental results under the previous bound, which indicates the success probability under our bound is higher than that of the previous bound with the growth of the bound.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.3 pp.195-202
- Publication Date
- 2022/03/01
- Publicized
- 2021/12/07
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2021CIP0021
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
Authors
Xiaoling YU
Taiyuan University of Technology
Yuntao WANG
Japan Advanced Institute of Science and Technology
Chungen XU
Nanjing University of Science and Technology
Tsuyoshi TAKAGI
The University of Tokyo
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Xiaoling YU, Yuntao WANG, Chungen XU, Tsuyoshi TAKAGI, "Revisiting the Orthogonal Lattice Algorithm in Solving General Approximate Common Divisor Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E105-A, no. 3, pp. 195-202, March 2022, doi: 10.1587/transfun.2021CIP0021.
Abstract: Due to the property of supporting arbitrary operation over the encrypted data, fully homomorphic encryption (FHE) has drawn considerable attention since it appeared. Some FHE schemes have been constructed based on the general approximate common divisor (GACD) problem, which is widely believed intractable. Therefore, studying the GACD problem's hardness can provide proper security parameters for these FHE schemes and their variants. This paper aims to study an orthogonal lattice algorithm introduced by Ding and Tao (Ding-Tao algorithm) to solve the GACD problem. We revisit the condition that Ding-Tao algorithm works and obtain a new bound of the GACD samples' number based on geometric series assumption. Simultaneously, we also give an analysis of the bound given in the previous work. To further verify the theoretical results, we conduct experiments on Ding-Tao algorithm under our bound. We show a comparison with the experimental results under the previous bound, which indicates the success probability under our bound is higher than that of the previous bound with the growth of the bound.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021CIP0021/_p
Copy
@ARTICLE{e105-a_3_195,
author={Xiaoling YU, Yuntao WANG, Chungen XU, Tsuyoshi TAKAGI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Revisiting the Orthogonal Lattice Algorithm in Solving General Approximate Common Divisor Problem},
year={2022},
volume={E105-A},
number={3},
pages={195-202},
abstract={Due to the property of supporting arbitrary operation over the encrypted data, fully homomorphic encryption (FHE) has drawn considerable attention since it appeared. Some FHE schemes have been constructed based on the general approximate common divisor (GACD) problem, which is widely believed intractable. Therefore, studying the GACD problem's hardness can provide proper security parameters for these FHE schemes and their variants. This paper aims to study an orthogonal lattice algorithm introduced by Ding and Tao (Ding-Tao algorithm) to solve the GACD problem. We revisit the condition that Ding-Tao algorithm works and obtain a new bound of the GACD samples' number based on geometric series assumption. Simultaneously, we also give an analysis of the bound given in the previous work. To further verify the theoretical results, we conduct experiments on Ding-Tao algorithm under our bound. We show a comparison with the experimental results under the previous bound, which indicates the success probability under our bound is higher than that of the previous bound with the growth of the bound.},
keywords={},
doi={10.1587/transfun.2021CIP0021},
ISSN={1745-1337},
month={March},}
Copy
TY - JOUR
TI - Revisiting the Orthogonal Lattice Algorithm in Solving General Approximate Common Divisor Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 195
EP - 202
AU - Xiaoling YU
AU - Yuntao WANG
AU - Chungen XU
AU - Tsuyoshi TAKAGI
PY - 2022
DO - 10.1587/transfun.2021CIP0021
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E105-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2022
AB - Due to the property of supporting arbitrary operation over the encrypted data, fully homomorphic encryption (FHE) has drawn considerable attention since it appeared. Some FHE schemes have been constructed based on the general approximate common divisor (GACD) problem, which is widely believed intractable. Therefore, studying the GACD problem's hardness can provide proper security parameters for these FHE schemes and their variants. This paper aims to study an orthogonal lattice algorithm introduced by Ding and Tao (Ding-Tao algorithm) to solve the GACD problem. We revisit the condition that Ding-Tao algorithm works and obtain a new bound of the GACD samples' number based on geometric series assumption. Simultaneously, we also give an analysis of the bound given in the previous work. To further verify the theoretical results, we conduct experiments on Ding-Tao algorithm under our bound. We show a comparison with the experimental results under the previous bound, which indicates the success probability under our bound is higher than that of the previous bound with the growth of the bound.
ER -
English
