La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Revisiting the Orthogonal Lattice Algorithm in Solving General Approximate Common Divisor Problem Revisiter l'algorithme de réseau orthogonal pour résoudre le problème général du diviseur commun approximatif

Xiaoling YU, Yuntao WANG, Chungen XU, Tsuyoshi TAKAGI

  • Vues en texte intégral

    1

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.3 pp.195-202
Date de publication
2022/03/01
Publicisé
2021/12/07
ISSN en ligne
1745-1337
DOI
10.1587/transfun.2021CIP0021
Type de manuscrit
Special Section PAPER (Special Section on Cryptography and Information Security)
Catégories

Auteurs

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

Mots-clés

Table des matières