On the concrete hardness of the Approximate GCD problem
Resumo
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
Referências
Ajtai, M. (1998). The shortest vector problem in ℓ2 is np-hard for randomized reductions. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pages 10–19. ACM.
Albrecht, M., Chase, M., Chen, H., Ding, J., Goldwasser, S., Gorbunov, S., Halevi, S., Hoffstein, J., Laine, K., Lauter, K., Lokam, S., Micciancio, D., Moody, D., Morrison, T., Sahai, A., and Vaikuntanathan, V. (2018). Homomorphic encryption security standard. Technical report, HomomorphicEncryption.org, Toronto, Canada.
Albrecht, M. R. (2017). On dual lattice attacks against small-secret lwe and parameter choices in helib and seal. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 103–129. Springer.
Albrecht, M. R., Bai, S., Fouque, P.-A., Kirchner, P., Stehlé, D., and Wen, W. (2020). Faster enumeration-based lattice reduction: root hermite factor time. In Annual International Cryptology Conference, pages 186–212. Springer.
Albrecht, M. R., Bai, S., Li, J., and Rowell, J. (2021). Lattice reduction with approximate enumeration oracles: practical algorithms and concrete performance. In Annual International Cryptology Conference, pages 732–759. Springer.
Albrecht, M. R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E. W., and Stevens, M. (2019). The general sieve kernel and new records in lattice reduction. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 717–746. Springer.
Albrecht, M. R., Göpfert, F., Virdia, F., and Wunderer, T. (2017). Revisiting the expected cost of solving usvp and applications to lwe. In International Conference on the Theory and Application of Cryptology and Information Security, pages 297–322. Springer.
Albrecht, M. R., Player, R., and Scott, S. (2015). On the concrete hardness of learning with errors. Cryptology ePrint Archive.
Alkim, E., Ducas, L., Pöppelmann, T., and Schwabe, P. (2016). Post-quantum key tExchange—Au new hope. In 25th USENIX security symposium (USENIX Security 16), pages 327–343.
Aquiles Lima, and Lima Pereira, H. (2026). Agcd estimator. [link].
Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., Stehlé, D., et al. (2019). Crystals-kyber algorithm specifications and supporting documentation. NIST PQC Round, 2(4):1–43.
Bajard, J.-C., Eynard, J., Hasan, M. A., and Zucca, V. (2017). A full rns variant of fv like somewhat homomorphic encryption schemes. In Selected Areas in Cryptography (SAC 2016), volume 10532 of Lecture Notes in Computer Science, pages 423–442. Springer.
Becker, A., Ducas, L., Gama, N., and Laarhoven, T. (2016). New directions in nearest neighbor searching with applications to lattice sieving. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 10–24. SIAM.
Bellare, M., Desai, A., Jokipii, E., and Rogaway, P. (1997). A concrete security treatment of symmetric encryption. In Proceedings 38th annual symposium on foundations of computer science, pages 394–403. IEEE.
Bi, J., Coron, J.-S., Faugère, J.-C., Nguyen, P. Q., Renault, G., and Zeitoun, R. (2014). Rounding and chaining lll: finding faster small roots of univariate polynomial congruences. In International Workshop on Public Key Cryptography, pages 185–202. Springer.
Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., and Stehle, D. (2018). Crystals - kyber: A cca-secure module-lattice-based kem. In 2018 IEEE European Symposium on Security and Privacy, pages 353–367.
Brakerski, Z. and Vaikuntanathan, V. (2011). Efficient fully homomorphic encryption from (standard) lwe. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 97–106.
Chailloux, A. and Loyer, J. (2021). Lattice sieving via quantum random walks. In International Conference on the Theory and Application of Cryptology and Information Security, pages 63–91. Springer.
Chen, Y. and Nguyen, P. Q. (2011). Bkz 2.0: Better lattice security estimates. In International Conference on the Theory and Application of Cryptology and Information Security, pages 1–20. Springer.
Cheon, J. H., Coron, J.-S., Kim, J., Lee, M. S., Lepoint, T., Tibouchi, M., and Yun, A. (2013). Batch fully homomorphic encryption over the integers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 315–335. Springer.
Cheon, J. H., Han, K., Kim, A., Kim, M., and Song, Y. (2019). A full rns variant of approximate homomorphic encryption. In Selected Areas in Cryptography (SAC 2018), volume 11349 of Lecture Notes in Computer Science, pages 347–368. Springer.
Cheon, J. H. and Stehlé, D. (2015). Fully homomophic encryption over the integers revisited. In Annual international conference on the theory and applications of cryptographic techniques, pages 513–536. Springer.
Chillotti, I., Gama, N., Georgieva, M., and Izabachène, M. (2020). Tfhe: Fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1):34–91.
Coron, J.-S., Lepoint, T., and Tibouchi, M. (2014). Scale-invariant fully homomorphic encryption over the integers. In International Workshop on Public Key Cryptography, pages 311–328. Springer.
Coron, J.-S., Naccache, D., and Tibouchi, M. (2012). Public key compression and modulus switching for fully homomorphic encryption over the integers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 446–464. Springer.
Coron, J.-S. and Pereira, H. V. L. (2019). On kilian’s randomization of multilinear map encodings. In Galbraith, S. D. and Moriai, S., editors, Advances in Cryptology – ASI- ACRYPT 2019, pages 325–355, Cham. Springer International Publishing.
Ding, J., Kim, S., Takagi, T., and Wang, Y. (2018). Why 1.02? the root hermite factor of lll and stochastic sandpile models. arXiv preprint arXiv:1804.03285.
Ding, J. and Tao, C. (2014). A new algorithm for solving the approximate common divisor problem and cryptanalysis of the fhe based on gacd. IACR Cryptol. ePrint Arch., 2014:42.
Feo, L. D. (2017). Mathematics of isogeny based cryptography.
Galbraith, S. D., Gebregiyorgis, S. W., and Murphy, S. (2016). Algorithms for the approximate common divisor problem. LMS Journal of Computation and Mathematics, 19(A):58–72.
Gama, N. and Nguyen, P. Q. (2008). Predicting lattice reduction. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 31–51. Springer.
Guo, Q. and Johansson, T. (2021). Faster dual lattice attacks for solving lwe with applications to crystals. In International Conference on the Theory and Application of Cryptology and Information Security, pages 33–62. Springer.
Halevi, S. and Shoup, V. (2014). Algorithms in helib. In Advances in Cryptology – CRYPTO 2014, volume 8616 of Lecture Notes in Computer Science, pages 554–571. Springer.
Hermite, C. (1850). Extraits de lettres de m. ch. hermite à m. jacobi sur différents objects de la théorie des nombres. Journal für die reine und angewandte Mathematik (Crelles Journal), 1850(40):261–278.
Johnson, D., Menezes, A., and Vanstone, S. (2001). The elliptic curve digital signature algorithm (ecdsa). Int. J. Inf. Secur., 1(1):36–63.
Kim, J., Lee, M. S., Yun, A., and Cheon, J. H. (2013). Crt-based fully homomorphic encryption over the integers. Cryptology ePrint Archive.
Korkine, A. and Zolotareff, G. (1873). Sur les formes quadratiques. Mathematische Annalen, 6(3):366–389.
Korkine, A. and Zolotareff, G. (1877). Sur les formes quadratiques positives. Mathematische Annalen, 11(2):242–292.
Laarhoven, T. (2015). Sieving for shortest vectors in lattices using angular locality-sensitive hashing. In Annual Cryptology Conference, pages 3–22. Springer.
Laarhoven, T., Mosca, M., and Van De Pol, J. (2015). Finding shortest lattice vectors faster using quantum search. Designs, Codes and Cryptography, 77(2):375–400.
Lee, E., Lee, J. W., Kim, Y. S., and No, J.-S. (2022). Optimization of homomorphic comparison algorithm on rns-ckks scheme. IEEE Access, 10:26163–26176.
Lima Pereira, H. V. (2020). Homomorphic encryption and multilinear maps based on the approximate-gcd problem.
MATZOV, I. Report on the security of lwe: improved dual lattice attack, 2022. URL: [link].
Nguyen, P. and Stern, J. (1997). Merkle-hellman revisited: a cryptanalysis of the quvanstone cryptosystem based on group factorizations. pages 198–212.
Peikert, C. (2016). A decade of lattice cryptography. Found. Trends Theor. Comput. Sci., 10(4):283–424.
Pereira, H. V. L. (2020). Efficient agcd-based homomorphic encryption for matrix and vector arithmetic. In International Conference on Applied Cryptography and Network Security, pages 110–129. Springer.
Pereira, H. V. L. (2021). Bootstrapping fully homomorphic encryption over the integers in less than one second. In IACR international conference on public-key cryptography, pages 331–359. Springer.
van Dijk, M., Gentry, C., Halevi, S., and Vaikuntanathan, V. (2010). Fully homomorphic encryption over the integers. In Advances in Cryptology – EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 24–43. Springer.
Xu, J., Sarkar, S., and Hu, L. (2018). Revisiting orthogonal lattice attacks on approximate common divisor problems and their applications. Cryptology ePrint Archive.
Zhao, Z. and Ding, J. (2023). Practical improvements on bkz algorithm. In International Symposium on Cyber Security, Cryptology, and Machine Learning, pages 273–284. Springer.
Zhao, Z., Ding, J., and Yang, B.-Y. (2024). Bgj15 revisited: Sieving with streamed memory access. Cryptology ePrint Archive.
Albrecht, M., Chase, M., Chen, H., Ding, J., Goldwasser, S., Gorbunov, S., Halevi, S., Hoffstein, J., Laine, K., Lauter, K., Lokam, S., Micciancio, D., Moody, D., Morrison, T., Sahai, A., and Vaikuntanathan, V. (2018). Homomorphic encryption security standard. Technical report, HomomorphicEncryption.org, Toronto, Canada.
Albrecht, M. R. (2017). On dual lattice attacks against small-secret lwe and parameter choices in helib and seal. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 103–129. Springer.
Albrecht, M. R., Bai, S., Fouque, P.-A., Kirchner, P., Stehlé, D., and Wen, W. (2020). Faster enumeration-based lattice reduction: root hermite factor time. In Annual International Cryptology Conference, pages 186–212. Springer.
Albrecht, M. R., Bai, S., Li, J., and Rowell, J. (2021). Lattice reduction with approximate enumeration oracles: practical algorithms and concrete performance. In Annual International Cryptology Conference, pages 732–759. Springer.
Albrecht, M. R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E. W., and Stevens, M. (2019). The general sieve kernel and new records in lattice reduction. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 717–746. Springer.
Albrecht, M. R., Göpfert, F., Virdia, F., and Wunderer, T. (2017). Revisiting the expected cost of solving usvp and applications to lwe. In International Conference on the Theory and Application of Cryptology and Information Security, pages 297–322. Springer.
Albrecht, M. R., Player, R., and Scott, S. (2015). On the concrete hardness of learning with errors. Cryptology ePrint Archive.
Alkim, E., Ducas, L., Pöppelmann, T., and Schwabe, P. (2016). Post-quantum key tExchange—Au new hope. In 25th USENIX security symposium (USENIX Security 16), pages 327–343.
Aquiles Lima, and Lima Pereira, H. (2026). Agcd estimator. [link].
Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., Stehlé, D., et al. (2019). Crystals-kyber algorithm specifications and supporting documentation. NIST PQC Round, 2(4):1–43.
Bajard, J.-C., Eynard, J., Hasan, M. A., and Zucca, V. (2017). A full rns variant of fv like somewhat homomorphic encryption schemes. In Selected Areas in Cryptography (SAC 2016), volume 10532 of Lecture Notes in Computer Science, pages 423–442. Springer.
Becker, A., Ducas, L., Gama, N., and Laarhoven, T. (2016). New directions in nearest neighbor searching with applications to lattice sieving. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 10–24. SIAM.
Bellare, M., Desai, A., Jokipii, E., and Rogaway, P. (1997). A concrete security treatment of symmetric encryption. In Proceedings 38th annual symposium on foundations of computer science, pages 394–403. IEEE.
Bi, J., Coron, J.-S., Faugère, J.-C., Nguyen, P. Q., Renault, G., and Zeitoun, R. (2014). Rounding and chaining lll: finding faster small roots of univariate polynomial congruences. In International Workshop on Public Key Cryptography, pages 185–202. Springer.
Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., and Stehle, D. (2018). Crystals - kyber: A cca-secure module-lattice-based kem. In 2018 IEEE European Symposium on Security and Privacy, pages 353–367.
Brakerski, Z. and Vaikuntanathan, V. (2011). Efficient fully homomorphic encryption from (standard) lwe. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 97–106.
Chailloux, A. and Loyer, J. (2021). Lattice sieving via quantum random walks. In International Conference on the Theory and Application of Cryptology and Information Security, pages 63–91. Springer.
Chen, Y. and Nguyen, P. Q. (2011). Bkz 2.0: Better lattice security estimates. In International Conference on the Theory and Application of Cryptology and Information Security, pages 1–20. Springer.
Cheon, J. H., Coron, J.-S., Kim, J., Lee, M. S., Lepoint, T., Tibouchi, M., and Yun, A. (2013). Batch fully homomorphic encryption over the integers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 315–335. Springer.
Cheon, J. H., Han, K., Kim, A., Kim, M., and Song, Y. (2019). A full rns variant of approximate homomorphic encryption. In Selected Areas in Cryptography (SAC 2018), volume 11349 of Lecture Notes in Computer Science, pages 347–368. Springer.
Cheon, J. H. and Stehlé, D. (2015). Fully homomophic encryption over the integers revisited. In Annual international conference on the theory and applications of cryptographic techniques, pages 513–536. Springer.
Chillotti, I., Gama, N., Georgieva, M., and Izabachène, M. (2020). Tfhe: Fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1):34–91.
Coron, J.-S., Lepoint, T., and Tibouchi, M. (2014). Scale-invariant fully homomorphic encryption over the integers. In International Workshop on Public Key Cryptography, pages 311–328. Springer.
Coron, J.-S., Naccache, D., and Tibouchi, M. (2012). Public key compression and modulus switching for fully homomorphic encryption over the integers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 446–464. Springer.
Coron, J.-S. and Pereira, H. V. L. (2019). On kilian’s randomization of multilinear map encodings. In Galbraith, S. D. and Moriai, S., editors, Advances in Cryptology – ASI- ACRYPT 2019, pages 325–355, Cham. Springer International Publishing.
Ding, J., Kim, S., Takagi, T., and Wang, Y. (2018). Why 1.02? the root hermite factor of lll and stochastic sandpile models. arXiv preprint arXiv:1804.03285.
Ding, J. and Tao, C. (2014). A new algorithm for solving the approximate common divisor problem and cryptanalysis of the fhe based on gacd. IACR Cryptol. ePrint Arch., 2014:42.
Feo, L. D. (2017). Mathematics of isogeny based cryptography.
Galbraith, S. D., Gebregiyorgis, S. W., and Murphy, S. (2016). Algorithms for the approximate common divisor problem. LMS Journal of Computation and Mathematics, 19(A):58–72.
Gama, N. and Nguyen, P. Q. (2008). Predicting lattice reduction. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 31–51. Springer.
Guo, Q. and Johansson, T. (2021). Faster dual lattice attacks for solving lwe with applications to crystals. In International Conference on the Theory and Application of Cryptology and Information Security, pages 33–62. Springer.
Halevi, S. and Shoup, V. (2014). Algorithms in helib. In Advances in Cryptology – CRYPTO 2014, volume 8616 of Lecture Notes in Computer Science, pages 554–571. Springer.
Hermite, C. (1850). Extraits de lettres de m. ch. hermite à m. jacobi sur différents objects de la théorie des nombres. Journal für die reine und angewandte Mathematik (Crelles Journal), 1850(40):261–278.
Johnson, D., Menezes, A., and Vanstone, S. (2001). The elliptic curve digital signature algorithm (ecdsa). Int. J. Inf. Secur., 1(1):36–63.
Kim, J., Lee, M. S., Yun, A., and Cheon, J. H. (2013). Crt-based fully homomorphic encryption over the integers. Cryptology ePrint Archive.
Korkine, A. and Zolotareff, G. (1873). Sur les formes quadratiques. Mathematische Annalen, 6(3):366–389.
Korkine, A. and Zolotareff, G. (1877). Sur les formes quadratiques positives. Mathematische Annalen, 11(2):242–292.
Laarhoven, T. (2015). Sieving for shortest vectors in lattices using angular locality-sensitive hashing. In Annual Cryptology Conference, pages 3–22. Springer.
Laarhoven, T., Mosca, M., and Van De Pol, J. (2015). Finding shortest lattice vectors faster using quantum search. Designs, Codes and Cryptography, 77(2):375–400.
Lee, E., Lee, J. W., Kim, Y. S., and No, J.-S. (2022). Optimization of homomorphic comparison algorithm on rns-ckks scheme. IEEE Access, 10:26163–26176.
Lima Pereira, H. V. (2020). Homomorphic encryption and multilinear maps based on the approximate-gcd problem.
MATZOV, I. Report on the security of lwe: improved dual lattice attack, 2022. URL: [link].
Nguyen, P. and Stern, J. (1997). Merkle-hellman revisited: a cryptanalysis of the quvanstone cryptosystem based on group factorizations. pages 198–212.
Peikert, C. (2016). A decade of lattice cryptography. Found. Trends Theor. Comput. Sci., 10(4):283–424.
Pereira, H. V. L. (2020). Efficient agcd-based homomorphic encryption for matrix and vector arithmetic. In International Conference on Applied Cryptography and Network Security, pages 110–129. Springer.
Pereira, H. V. L. (2021). Bootstrapping fully homomorphic encryption over the integers in less than one second. In IACR international conference on public-key cryptography, pages 331–359. Springer.
van Dijk, M., Gentry, C., Halevi, S., and Vaikuntanathan, V. (2010). Fully homomorphic encryption over the integers. In Advances in Cryptology – EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 24–43. Springer.
Xu, J., Sarkar, S., and Hu, L. (2018). Revisiting orthogonal lattice attacks on approximate common divisor problems and their applications. Cryptology ePrint Archive.
Zhao, Z. and Ding, J. (2023). Practical improvements on bkz algorithm. In International Symposium on Cyber Security, Cryptology, and Machine Learning, pages 273–284. Springer.
Zhao, Z., Ding, J., and Yang, B.-Y. (2024). Bgj15 revisited: Sieving with streamed memory access. Cryptology ePrint Archive.
Publicado
01/09/2026
Como Citar
LIMA, Éricles A. A. B.; PEREIRA, Hilder V. L..
On the concrete hardness of the Approximate GCD problem. In: SIMPÓSIO BRASILEIRO DE CIBERSEGURANÇA (SBSEG), 26. , 2026, Armação dos Búzios/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 865-880.
DOI: https://doi.org/10.5753/sbseg.2026.29379.
