On the concrete hardness of the Approximate GCD problem - Lima, Éricles A. A. B.; Pereira, Hilder V. L. (Anais do Simpósio Brasileiro de Cibersegurança (SBSeg); 2026: Anais do XXVI Simpósio Brasileiro de CibersegurançaDO - 10.5753/sbseg.2026.29379, 2026)
O problema do Máximo Divisor Comum Aproximado (AGCD, na sigla em inglês) tem se mostrado um fundamento teórico importante para várias construções criptográficas, principalmente devido ao seu uso em esquemas de criptografia homomórfica e de criptografia pós-quântica. Este trabalho analisa a dificuldade concreta do AGCD, mostrando como o custo dos algoritmos conhecidos varia em relação ao número de operações básicas. Em seguida, com base nessa análise, fornecemos uma ferramenta para estimar a dificuldade concreta de qualquer instância do AGCD. Por fim, usamos nossa ferramenta para estimar o nível de segurança de esquemas existentes baseados em AGCD