Algorithmic Number Theory

The frontiers between computable objects, algorithms (above section), computational number theory and applications to security of cryptographic systems are very porous. This union of research fields is mainly driven by the algorithmic improvement to solve presumably hard problems relevant to cryptography, such as computation of discrete logarithms, resolution of hard subset-sum problems, decoding of random binary codes and search for close and short vectors in lattices. While factorization and discrete logarithm problems have a long history in cryptography, the recent post-quantum cryptosystems introduce a new variety of presumably hard problems/objects/algorithms with cryptographic relevance: the shortest vector problem (SVP), the closest vector problem (CVP) or the computation of isogenies between elliptic curves, especially in the supersingular case.

Related Publications

  • F. Göloglu and A. Joux, “A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms,” IACR cryptology eprint archive, vol. 2018, p. 430, 2018.
    [Bibtex] 
    @article{DBLP:journals/iacr/GologluJ18,
author = {Faruk G{\"{o}}loglu and
Antoine Joux},
title = {A Simplified Approach to Rigorous Degree 2 Elimination in Discrete
Logarithm Algorithms},
journal = {{IACR} Cryptology ePrint Archive},
volume = {2018},
pages = {430},
year = {2018},
url = {https://eprint.iacr.org/2018/430},
timestamp = {Tue, 14 Aug 2018 17:08:14 +0200},
biburl = {https://dblp.org/rec/bib/journals/iacr/GologluJ18},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
  • [PDF] R. Barbulescu and S. Duquesne, “Updating key size estimations for pairings,” Journal of cryptology, vol. published online, to appear in print, 2018.
    [Bibtex] 
    @article{barbulescu:hal-01534101,
TITLE = {{Updating key size estimations for pairings}},
AUTHOR = {Barbulescu, Razvan and Duquesne, Sylvain},
URL = {https://hal.archives-ouvertes.fr/hal-01534101},
journal = {Journal of Cryptology},
volume={published online, to appear in print},
YEAR = {2018},
MONTH = Dec,
PDF = {https://hal.archives-ouvertes.fr/hal-01534101/file/main.pdf},
HAL_ID = {hal-01534101},
HAL_VERSION = {v2},
}
  • [PDF] R. Barbulescu and S. Shinde, A complete classification of ECM-friendly families using modular curves, 2018.
    [Bibtex] 
    @unpublished{barbulescu:hal-01822144,
TITLE = {{A complete classification of ECM-friendly families using modular curves}},
AUTHOR = {Barbulescu, Razvan and Shinde, Sudarshan},
URL = {https://hal.archives-ouvertes.fr/hal-01822144},
NOTE = {working paper or preprint},
YEAR = {2018},
MONTH = Jun,
PDF = {https://hal.archives-ouvertes.fr/hal-01822144/file/applications-elliptic-curves.pdf},
HAL_ID = {hal-01822144},
HAL_VERSION = {v1},
}
  • [PDF] [DOI] J. Biasse, T. Espitau, P. Fouque, A. Gélin, and P. Kirchner, “Computing generator in cyclotomic integer rings,” in 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2017), Paris, France, 2017, pp. 60-88.
    [Bibtex] 
    @inproceedings{biasse:hal-01518438,
TITLE = {{Computing generator in cyclotomic integer rings}},
AUTHOR = {Biasse, Jean-Fran{\c c}ois and Espitau, Thomas and Fouque, Pierre-Alain and G{\'e}lin, Alexandre and Kirchner, Paul},
URL = {https://hal.archives-ouvertes.fr/hal-01518438},
BOOKTITLE = {{36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2017)}},
ADDRESS = {Paris, France},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {10210},
PAGES = {60-88},
YEAR = {2017},
MONTH = Apr,
DOI = {10.1007/978-3-319-56620-7\_3},
PDF = {https://hal.archives-ouvertes.fr/hal-01518438/file/142.pdf},
HAL_ID = {hal-01518438},
HAL_VERSION = {v1},
}
  • [PDF] R. Barbulescu and S. Duquesne, “Updating key size estimations for pairings,” Journal of cryptology, vol. published online, to appear in print, 2018.
    [Bibtex] 
    @article{barbulescu:hal-01534101,
TITLE = {{Updating key size estimations for pairings}},
AUTHOR = {Barbulescu, Razvan and Duquesne, Sylvain},
URL = {https://hal.archives-ouvertes.fr/hal-01534101},
journal = {Journal of Cryptology},
volume={published online, to appear in print},
YEAR = {2018},
MONTH = Dec,
PDF = {https://hal.archives-ouvertes.fr/hal-01534101/file/main.pdf},
HAL_ID = {hal-01534101},
HAL_VERSION = {v2},
}
  • [PDF] [DOI] A. Gélin and A. Joux, “Reducing number field defining polynomials: an application to class group computations,” in Algorithmic Number Theory Symposium XII, Kaiserslautern, Germany, 2016, p. 315–331.
    [Bibtex] 
    @inproceedings{gelin:hal-01362144,
TITLE = {{Reducing number field defining polynomials: an application to class group computations}},
AUTHOR = {G{\'e}lin, Alexandre and Joux, Antoine},
URL = {https://hal.archives-ouvertes.fr/hal-01362144},
BOOKTITLE = {{Algorithmic Number Theory Symposium XII}},
ADDRESS = {Kaiserslautern, Germany},
SERIES = {LMS Journal of Computation and Mathematics},
VOLUME = {19},
NUMBER = {A},
PAGES = {315--331 },
YEAR = {2016},
MONTH = Aug,
DOI = {10.1112/S1461157016000255},
PDF = {https://hal.archives-ouvertes.fr/hal-01362144/file/Gelin_2016_Reducing_number.pdf},
HAL_ID = {hal-01362144},
HAL_VERSION = {v1},
}
  • [PDF] R. Barbulescu, “A brief history of pairings,” in International Workshop on the Arithmetic of Finite Fields WAIFI 2016, Gand, Belgium, 2016.
    [Bibtex] 
    @inproceedings{barbulescu:hal-01363444,
TITLE = {{A brief history of pairings}},
AUTHOR = {Barbulescu, Razvan},
URL = {https://hal.archives-ouvertes.fr/hal-01363444},
BOOKTITLE = {{International Workshop on the Arithmetic of Finite Fields WAIFI 2016}},
ADDRESS = {Gand, Belgium},
ORGANIZATION = {{Universit{\'e} de Gand}},
PUBLISHER = {{Springer}},
SERIES = { Arithmetic of Finite Fields -- WAIFI 2016},
VOLUME = {10064},
YEAR = {2016},
MONTH = Jul,
KEYWORDS = { finite fields ; elliptic curves ; pairings},
PDF = {https://hal.archives-ouvertes.fr/hal-01363444/file/waifi2016.pdf},
HAL_ID = {hal-01363444},
HAL_VERSION = {v1},
}
  • [PDF] R. Barbulescu, P. Gaudry, and T. Kleinjung, “The Tower Number Field Sieve,” in ASIACRYPT 2015, Auckland, New Zealand, 2015, pp. 31-58.
    [Bibtex] 
    @inproceedings{barbulescu:hal-01155635,
TITLE = {{The Tower Number Field Sieve}},
AUTHOR = {Barbulescu, Razvan and Gaudry, Pierrick and Kleinjung, Thorsten},
URL = {https://hal.archives-ouvertes.fr/hal-01155635},
BOOKTITLE = {{ASIACRYPT 2015}},
ADDRESS = {Auckland, New Zealand},
ORGANIZATION = {{International Association of Cryptologic Research}},
EDITOR = {Tetsu Iwata and Jung Hee Cheon},
PUBLISHER = {{Springer}},
SERIES = {Advances in cryptology-Asiacrypt 2015},
VOLUME = {9453},
PAGES = {31-58},
YEAR = {2015},
MONTH = Nov,
KEYWORDS = {discrete logarithm ; number field sieve ; pairings},
PDF = {https://hal.archives-ouvertes.fr/hal-01155635/file/TNFS.pdf},
HAL_ID = {hal-01155635},
HAL_VERSION = {v1},
}
  • [DOI] R. Barbulescu, P. Gaudry, A. Guillevic, and F. Morain, “Improving NFS for the discrete logarithm problem in non-prime finite fields,” in Eurocrypt 2015 – 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 2015, pp. 129-155.
    [Bibtex] 
    @inproceedings{barbulescu:hal-01112879,
TITLE = {{Improving NFS for the discrete logarithm problem in non-prime finite fields}},
AUTHOR = {Barbulescu, Razvan and Gaudry, Pierrick and Guillevic, Aurore and Morain, Fran{\c c}ois},
URL = {https://hal.inria.fr/hal-01112879},
BOOKTITLE = {{Eurocrypt 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques}},
ADDRESS = {Sofia, Bulgaria},
EDITOR = {Marc Fischlin and Elisabeth Oswald},
SERIES = {Advances in Cryptology -- EUROCRYPT 2015},
VOLUME = {9056},
PAGES = {129-155},
YEAR = {2015},
MONTH = Apr,
DOI = {10.1007/978-3-662-46800-5\_6}
}
  • [PDF] [DOI] R. Barbulescu, P. Gaudry, A. Joux, and E. Thomé, “A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic,” in Eurocrypt 2014, Copenhagen, Denmark, 2014, pp. 1-16.
    [Bibtex] 
    @inproceedings{barbulescu:hal-00835446,
TITLE = {{A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic}},
AUTHOR = {Barbulescu, Razvan and Gaudry, Pierrick and Joux, Antoine and Thom{\'e}, Emmanuel},
URL = {https://hal.inria.fr/hal-00835446},
BOOKTITLE = {{Eurocrypt 2014}},
ADDRESS = {Copenhagen, Denmark},
EDITOR = {Phong Q. Nguyen and Elisabeth Oswald},
PUBLISHER = {{Springer}},
SERIES = {Advances in Cryptology - EUROCRYPT 2014},
VOLUME = {8441},
PAGES = {1-16},
YEAR = {2014},
MONTH = May,
DOI = {10.1007/978-3-642-55220-5\_1},
PDF = {https://hal.inria.fr/hal-00835446/file/article.pdf},
HAL_ID = {hal-00835446},
HAL_VERSION = {v2},
}
  • [DOI] A. Joux and C. Pierrot, “Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms – Simplified Setting for Small Characteristic Finite Fields,” in 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, 2014, pp. 378-397.
    [Bibtex] 
    @inproceedings{joux:hal-01213649,
TITLE = {{Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms - Simplified Setting for Small Characteristic Finite Fields}},
AUTHOR = {Joux, Antoine and Pierrot, C{\'e}cile},
URL = {https://hal.archives-ouvertes.fr/hal-01213649},
BOOKTITLE = {{20th International Conference on the Theory and Application of Cryptology and Information Security}},
ADDRESS = {Kaoshiung, Taiwan},
PUBLISHER = {{Springer Berlin Heidelberg}},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {8873},
PAGES = {378-397},
YEAR = {2014},
MONTH = Dec,
DOI = {10.1007/978-3-662-45611-8\_20},
HAL_ID = {hal-01213649},
HAL_VERSION = {v1},
}
  • [PDF] [DOI] R. Barbulescu and C. Pierrot, “The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields,” LMS Journal of Computation and Mathematics, vol. 17, p. 230–246, 2014.
    [Bibtex] 
    @article{barbulescu:hal-00952610,
TITLE = {{The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields}},
AUTHOR = {Barbulescu, Razvan and Pierrot, C{\'e}cile},
URL = {https://hal.inria.fr/hal-00952610},
JOURNAL = {{LMS Journal of Computation and Mathematics}},
PUBLISHER = {{London Mathematical Society}},
VOLUME = {17},
PAGES = {230--246},
YEAR = {2014},
DOI = {10.1112/S1461157014000369},
KEYWORDS = {Discrete logarithm problem ; finite fields ; number field sieve},
PDF = {https://hal.inria.fr/hal-00952610/file/MNFS_version2.pdf},
HAL_ID = {hal-00952610},
HAL_VERSION = {v2},
}
  • A. Joux, “A one round protocol for tripartite Diffie-Hellman,” J. cryptology, vol. 17, iss. 4, p. 263–276, 2004.
    [Bibtex] 
    @article {JouxTDH,
AUTHOR = {Joux, Antoine},
TITLE = {A one round protocol for tripartite {D}iffie-{H}ellman},
JOURNAL = {J. Cryptology},
FJOURNAL = {Journal of Cryptology. The Journal of the International Association for Cryptologic Research},
VOLUME = {17},
YEAR = {2004},
NUMBER = {4},
PAGES = {263--276}
}
  • A. Joux and R. Lercier, “Improvements to the general number field sieve for discrete logarithms in prime fields. a comparison with the gaussian integer method,” Math. comput., vol. 72, iss. 242, pp. 953-967, 2003.
    [Bibtex] 
    @article{DBLP:journals/moc/JouxL03,
author = {Antoine Joux and
Reynald Lercier},
title = {Improvements to the general number field sieve for discrete
logarithms in prime fields. A comparison with the gaussian
integer method},
journal = {Math. Comput.},
volume = {72},
number = {242},
year = {2003},
pages = {953-967},
ee = {http://dx.doi.org/10.1090/S0025-5718-02-01482-5},
bibsource = {DBLP, http://dblp.uni-trier.de}
}

Comments are closed.