The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
En raison de sa capacité à prendre en charge des opérations arbitraires sur les données chiffrées, le chiffrement entièrement homomorphe (FHE) a attiré une attention considérable depuis son apparition. Certains schémas FHE ont été construits sur la base du problème général du diviseur commun approximatif (GACD), qui est largement considéré comme insoluble. Par conséquent, l’étude de la difficulté du problème GACD peut fournir des paramètres de sécurité appropriés pour ces schémas FHE et leurs variantes. Cet article vise à étudier un algorithme de réseau orthogonal introduit par Ding et Tao (algorithme de Ding-Tao) pour résoudre le problème GACD. Nous revisitons la condition selon laquelle l'algorithme de Ding-Tao fonctionne et obtenons une nouvelle limite du nombre d'échantillons GACD basée sur l'hypothèse de séries géométriques. Simultanément, nous donnons également une analyse de la limite donnée dans le travail précédent. Pour vérifier davantage les résultats théoriques, nous menons des expériences sur l'algorithme de Ding-Tao sous notre limite. Nous montrons une comparaison avec les résultats expérimentaux sous la limite précédente, ce qui indique que la probabilité de succès sous notre limite est supérieure à celle de la limite précédente avec la croissance de la limite.
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
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.
Copier
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
Copier
@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},}
Copier
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 -