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.

P. Molin (with C. Neurohr), has implemented an algorithm (now integrated into the Magma software and available for the Arb certified calculation library) for numerical calculation of periods and Abel-Jacobi application of plane curves. This work is continuing with a view to adopting holonomic techniques and reaching higher dimensions. He has built (with A. Page) algorithms (now integrated into the Pari/GP software) for general Hecke characters.

A. Joux (with C. Pierrot) has built an algorithm for calculating discrete logarithms based on the Couveignes and Lercier representation, a new implementation technique for LLL (with T. Espitau)  and a homomorphic encryption algorithm based on Fermat’s modulo number calculus. Two other works on discrete logarithms, resp, with Gologlu and Ivonyis + Santha can also be mentioned. In cryptanalysis, he proposed a new approach to learning-with-error with small secret (with T. Espitau and N. Karchenko) and a cryptanalysis of systems based on finite field isomorphism (with D. Das). He participated in the design of two cryptographic signatures based on error-correcting codes and trilinear isomorphism respectively.

T. Feneuil and A. Joux (with M. Rivain) have designed two cryptographic signatures for which the security relies on the hardness to solve the syndrome decoding problem on random linear codes. T. Feneuil (with J. Maire, M. Rivain, and D. Vergnaud) has also proposed a third cryptographic signature scheme (or identification scheme) relying on the subset-sum problem. These three schemes use the MPC-in-the-Head framework, which converts a multiparty computation into an identification scheme.

J. C. Bajard (with P. Martins, L. Sousa and V. Zucca) proposed an improvement to the algorithms of a homomorphic cryptographic scheme by Fan and Vercauteren, where they use a hybrid representation of numbers. He has worked (with S. Duquesne) on “Montgomery-friendly” prime numbers, which are interesting for modular computation, in particular for cryptography based on isogenies, but also in computer arithmetic. He has constructed (with K. Fukushima, Th. Plantard, A. Sipasseuth) a generator of pairwise prime numbers respecting certain properties that can serve as the basis for number systems using the Chinese remainder theorem. Finally, he clarified (with J. Marrez, Th. Plantard, P. Véron) the criteria for the existence and construction of numeration systems based on Euclidean networks, which are also well suited to modular calculus.

Related Publications

  • [PDF] P. Molin and C. Neurohr, “Computing period matrices and the Abel-Jacobi map of superelliptic curves,” Mathematics of Computation, 2019.
    [Bibtex] 
    @article{molin:hal-02416012,
TITLE = {{Computing period matrices and the Abel-Jacobi map of superelliptic curves}},
AUTHOR = {Molin, Pascal and Neurohr, Christian},
URL = {https://inria.hal.science/hal-02416012},
JOURNAL = {{Mathematics of Computation}},
PUBLISHER = {{American Mathematical Society}},
YEAR = {2019},
PDF = {https://inria.hal.science/hal-02416012/file/periods.pdf},
HAL_ID = {hal-02416012},
HAL_VERSION = {v1},
}

  • [DOI] T. Feneuil, A. Joux, and M. Rivain, “Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature,” Designs, Codes and Cryptography, vol. 91, iss. 2, pp. 563-608, 2023.
    [Bibtex] 
    @article{feneuil:hal-04218321,
TITLE = {{Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature}},
AUTHOR = {Feneuil, Thibauld and Joux, Antoine and Rivain, Matthieu},
URL = {https://hal.science/hal-04218321},
JOURNAL = {{Designs, Codes and Cryptography}},
PUBLISHER = {{Springer Verlag}},
VOLUME = {91},
NUMBER = {2},
PAGES = {563-608},
YEAR = {2023},
MONTH = Feb,
DOI = {10.1007/s10623-022-01116-1},
KEYWORDS = {zero-knowledge, syndrome decoding, code-based signature},
HAL_ID = {hal-04218321},
HAL_VERSION = {v1},
}

  • [DOI] T. Feneuil, A. Joux, and M. Rivain, “Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs,” in CRYPTO 2022 – 42rd International Cryptology Conference, Santa Barbara (CA), United States, 2022, pp. 541-572.
    [Bibtex] 
    @inproceedings{feneuil:hal-04218105,
TITLE = {{Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs}},
AUTHOR = {Feneuil, Thibauld and Joux, Antoine and Rivain, Matthieu},
URL = {https://hal.science/hal-04218105},
BOOKTITLE = {{CRYPTO 2022 - 42rd International Cryptology Conference}},
ADDRESS = {Santa Barbara (CA), United States},
PUBLISHER = {{Springer Nature Switzerland}},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {13508},
PAGES = {541-572},
YEAR = {2022},
MONTH = Aug,
DOI = {10.1007/978-3-031-15979-4\_19},
KEYWORDS = {Zero-knowledge ; Syndrome decoding ; Code-based signature},
HAL_ID = {hal-04218105},
HAL_VERSION = {v1},
}

  • [DOI] T. Feneuil, J. Maire, M. Rivain, and D. Vergnaud, “Zero-Knowledge Protocols for the Subset Sum Problem from MPC-in-the-Head with Rejection,” in ASIACRYPT 2022 – 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, 2022, p. 371–402.
    [Bibtex] 
    @inproceedings{feneuil:hal-03941457,
TITLE = {{Zero-Knowledge Protocols for the Subset Sum Problem from MPC-in-the-Head with Rejection}},
AUTHOR = {Feneuil, Thibauld and Maire, Jules and Rivain, Matthieu and Vergnaud, Damien},
URL = {https://inria.hal.science/hal-03941457},
BOOKTITLE = {{ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security}},
ADDRESS = {Taipei, Taiwan},
EDITOR = {Shweta Agrawal and Dongdai Lin},
PUBLISHER = {{Springer}},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {13792},
PAGES = {371--402},
YEAR = {2022},
MONTH = Dec,
DOI = {10.1007/978-3-031-22966-4\_13},
KEYWORDS = {zero-knowledge ; subset-sum ; multi-party computation ; digital signatures},
HAL_ID = {hal-03941457},
HAL_VERSION = {v1},
}

  • [PDF] [DOI] A. Joux and C. Pierrot, “Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms,” Advances in Mathematics of Communications, 2022.
    [Bibtex] 
    @article{joux:hal-02173688,
TITLE = {{Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms}},
AUTHOR = {Joux, Antoine and Pierrot, C{\'e}cile},
URL = {https://hal.sorbonne-universite.fr/hal-02173688},
JOURNAL = {{Advances in Mathematics of Communications}},
PUBLISHER = {{AIMS}},
YEAR = {2022},
DOI = {10.48550/arXiv.1907.02689},
KEYWORDS = {Discrete logarithms ; Finite fields ; Elliptic bases},
PDF = {https://hal.sorbonne-universite.fr/hal-02173688v2/file/AlgoECdlog_journal.pdf},
HAL_ID = {hal-02173688},
HAL_VERSION = {v2},
}

  • [PDF] [DOI] D. Das and A. Joux, “On the Hardness of the Finite Field Isomorphism Problem,” in Eurocrypt 2023, Lyon, France, 2023, pp. 343-359.
    [Bibtex] 
    @inproceedings{das:hal-04294817,
TITLE = {{On the Hardness of the Finite Field Isomorphism Problem}},
AUTHOR = {Das, Dipayan and Joux, Antoine},
URL = {https://hal.science/hal-04294817},
BOOKTITLE = {{Eurocrypt 2023}},
ADDRESS = {Lyon, France},
PUBLISHER = {{Springer Nature Switzerland}},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {14008},
PAGES = {343-359},
YEAR = {2023},
MONTH = Apr,
DOI = {10.1007/978-3-031-30589-4\_12},
PDF = {https://hal.science/hal-04294817/file/2022-998.pdf},
HAL_ID = {hal-04294817},
HAL_VERSION = {v1},
}

  • [DOI] T. Espitau and A. Joux, “Certified lattice reduction,” Advances in Mathematics of Communications, vol. 14, iss. 1, pp. 137-159, 2020.
    [Bibtex] 
    @article{espitau:hal-02383752,
TITLE = {{Certified lattice reduction}},
AUTHOR = {Espitau, Thomas and Joux, Antoine},
URL = {https://hal.science/hal-02383752},
JOURNAL = {{Advances in Mathematics of Communications}},
PUBLISHER = {{AIMS}},
VOLUME = {14},
NUMBER = {1},
PAGES = {137-159},
YEAR = {2020},
MONTH = Feb,
DOI = {10.3934/amc.2020011},
KEYWORDS = {Lattice reduction ; Quadratic forms reduction ; Algorithmic number theory},
HAL_ID = {hal-02383752},
HAL_VERSION = {v1},
}

  • G. Ivanyos, A. Joux, and M. Santha, Discrete logarithm and Diffie-Hellman problems in identity black-box groups, 2019.
    [Bibtex] 
    @unpublished{ivanyos:hal-02350271,
TITLE = {{Discrete logarithm and Diffie-Hellman problems in identity black-box groups}},
AUTHOR = {Ivanyos, Gabor and Joux, Antoine and Santha, Miklos},
URL = {https://hal.sorbonne-universite.fr/hal-02350271},
NOTE = {working paper or preprint},
YEAR = {2019},
MONTH = Nov,
HAL_ID = {hal-02350271},
HAL_VERSION = {v1},
}

  • [PDF] F. Gölo{u g}lu and A. Joux, “A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms,” Mathematics of Computation, p. 1, 2019.
    [Bibtex] 
    @article{gololu:hal-01960765,
TITLE = {{A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms}},
AUTHOR = {G{\"o}lo{\u g}lu, Faruk and Joux, Antoine},
URL = {https://hal.science/hal-01960765},
JOURNAL = {{Mathematics of Computation}},
PUBLISHER = {{American Mathematical Society}},
PAGES = {1},
YEAR = {2019},
PDF = {https://hal.science/hal-01960765/file/Deg2Elimination.pdf},
HAL_ID = {hal-01960765},
HAL_VERSION = {v1},
}

  • [DOI] U. Chabaud, E. Diamanti, D. Markham, E. Kashefi, and A. Joux, “Optimal quantum-programmable projective measurement with linear optics,” Physical Review A, 2018.
    [Bibtex] 
    @article{chabaud:hal-01931757,
TITLE = {{Optimal quantum-programmable projective measurement with linear optics}},
AUTHOR = {Chabaud, Ulysse and Diamanti, Eleni and Markham, Damian and Kashefi, Elham and Joux, Antoine},
URL = {https://hal.sorbonne-universite.fr/hal-01931757},
NOTE = {11 pages, 7 figures},
JOURNAL = {{Physical Review A}},
PUBLISHER = {{American Physical Society }},
YEAR = {2018},
MONTH = Dec,
DOI = {10.1103/PhysRevA.98.062318},
HAL_ID = {hal-01931757},
HAL_VERSION = {v1},
}

  • D. Goudarzi, A. Joux, and M. Rivain, “How to Securely Compute with Noisy Leakage in Quasilinear Complexity,” in Advances in Cryptology – ASIACRYPT 2018 – 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part II, Springer, 2018, pp. 547-574.
    [Bibtex] 
    @incollection{goudarzi:hal-01960745,
TITLE = {{How to Securely Compute with Noisy Leakage in Quasilinear Complexity}},
AUTHOR = {Goudarzi, Dahmun and Joux, Antoine and Rivain, Matthieu},
URL = {https://hal.science/hal-01960745},
BOOKTITLE = {{Advances in Cryptology - {ASIACRYPT} 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part II}},
PUBLISHER = {{Springer}},
PAGES = {547-574},
YEAR = {2018},
MONTH = Oct,
HAL_ID = {hal-01960745},
HAL_VERSION = {v1},
}

  • D. Aggarwal, A. Joux, A. Prakash, and M. Santha, “A New Public-Key Cryptosystem via Mersenne Numbers,” in Crypto 2018, Santa-Barbara, United States, 2018, pp. 459-482.
    [Bibtex] 
    @inproceedings{aggarwal:hal-01960756,
TITLE = {{A New Public-Key Cryptosystem via Mersenne Numbers}},
AUTHOR = {Aggarwal, Divesh and Joux, Antoine and Prakash, Anupam and Santha, Miklos},
URL = {https://hal.science/hal-01960756},
BOOKTITLE = {{Crypto 2018}},
ADDRESS = {Santa-Barbara, United States},
PUBLISHER = {{Springer}},
SERIES = {Advances in Cryptology - Crypto 2018},
PAGES = {459-482},
YEAR = {2018},
HAL_ID = {hal-01960756},
HAL_VERSION = {v1},
}

  • [PDF] [DOI] J. Bajard, K. Fukushima, T. Plantard, and A. Sipasseuth, “Fast verification and public key storage optimization for unstructured lattice-based signatures,” Journal of Cryptographic Engineering, 2023.
    [Bibtex] 
    @article{bajard:hal-03959746,
TITLE = {{Fast verification and public key storage optimization for unstructured lattice-based signatures}},
AUTHOR = {Bajard, Jean-Claude and Fukushima, Kazuhide and Plantard, Thomas and Sipasseuth, Arnaud},
URL = {https://hal.sorbonne-universite.fr/hal-03959746},
JOURNAL = {{Journal of Cryptographic Engineering}},
PUBLISHER = {{Springer}},
SERIES = {Journal of Cryptographic Engineering (2023)},
YEAR = {2023},
MONTH = Jan,
DOI = {10.1007/s13389-023-00309-1},
KEYWORDS = {Lattice-based cryptography ; Digital signature ; Residue number systems ; Probabilistic verification.},
PDF = {https://hal.sorbonne-universite.fr/hal-03959746/file/2022_Journal_of_Cryptographic_Engineering_Probabilistic_Verification-2.pdf},
HAL_ID = {hal-03959746},
HAL_VERSION = {v1},
}

  • [PDF] [DOI] J. C. Bajard, K. Fukushima, T. Plantard, and A. Sipasseuth, “Generating Very Large RNS Bases,” IEEE Transactions on Emerging Topics in Computing, pp. 1-12, 2022.
    [Bibtex] 
    @article{bajard:hal-03719386,
TITLE = {{Generating Very Large RNS Bases}},
AUTHOR = {Bajard, Jean Claude and Fukushima, Kazuhide and Plantard, Thomas and Sipasseuth, Arnaud},
URL = {https://hal.sorbonne-universite.fr/hal-03719386},
JOURNAL = {{IEEE Transactions on Emerging Topics in Computing}},
PUBLISHER = {{Institute of Electrical and Electronics Engineers}},
PAGES = {1-12},
YEAR = {2022},
DOI = {10.1109/TETC.2022.3187072},
KEYWORDS = {Residue Number Systems ; Setwise Coprime ; Modular Arithmetic ; Cryptography},
PDF = {https://hal.sorbonne-universite.fr/hal-03719386/file/main_black_white.pdf},
HAL_ID = {hal-03719386},
HAL_VERSION = {v1},
}

  • [PDF] [DOI] J. Bajard, J. Marrez, T. Plantard, and P. Véron, “On Polynomial Modular Number Systems over $ \mathbb{Z}/{p}\mathbb{Z} $,” Advances in Mathematics of Communications, 2022.
    [Bibtex] 
    @article{bajard:hal-03611829,
TITLE = {{On Polynomial Modular Number Systems over $ \mathbb{Z}/{p}\mathbb{Z} $}},
AUTHOR = {Bajard, Jean-Claude and Marrez, J{\'e}r{\'e}my and Plantard, Thomas and V{\'e}ron, Pascal},
URL = {https://hal.science/hal-03611829},
JOURNAL = {{Advances in Mathematics of Communications}},
PUBLISHER = {{AIMS}},
YEAR = {2022},
DOI = {10.3934/amc.2022018},
KEYWORDS = {Finite field ; Polynomial Modular Number System ; Polynomial roots ; Modular Computation},
PDF = {https://hal.science/hal-03611829/file/1930-5346_2022018.pdf},
HAL_ID = {hal-03611829},
HAL_VERSION = {v1},
}

  • [PDF] [DOI] J. Bajard, K. Fukushima, S. Kiyomoto, T. Plantard, A. Sipasseuth, and W. Susilo, “Generating Residue Number System Bases,” in ARITH 2021- IEEE 28th Symposium on Computer Arithmetic, Virtual, France, 2021, pp. 86-93.
    [Bibtex] 
    @inproceedings{bajard:hal-03457951,
TITLE = {{Generating Residue Number System Bases}},
AUTHOR = {Bajard, Jean-Claude and Fukushima, Kazuhide and Kiyomoto, Shinsaku and Plantard, Thomas and Sipasseuth, Arnaud and Susilo, Willy},
URL = {https://hal.sorbonne-universite.fr/hal-03457951},
BOOKTITLE = {{ARITH 2021- IEEE 28th Symposium on Computer Arithmetic}},
ADDRESS = {Virtual, France},
PUBLISHER = {{IEEE}},
PAGES = {86-93},
YEAR = {2021},
MONTH = Jun,
DOI = {10.1109/ARITH51176.2021.00027},
KEYWORDS = {Residue Number Systems},
PDF = {https://hal.sorbonne-universite.fr/hal-03457951/file/5YVTBPLZ_main_edited_final.pdf},
HAL_ID = {hal-03457951},
HAL_VERSION = {v1},
}

  • [PDF] [DOI] J. Bajard and S. Duquesne, “Montgomery-friendly primes and applications to cryptography,” Journal of Cryptographic Engineering, vol. 11, iss. 4, p. pages 399–415, 2021.
    [Bibtex] 
    @article{bajard:hal-02883333,
TITLE = {{Montgomery-friendly primes and applications to cryptography}},
AUTHOR = {Bajard, Jean-Claude and Duquesne, Sylvain},
URL = {https://hal.sorbonne-universite.fr/hal-02883333},
JOURNAL = {{Journal of Cryptographic Engineering}},
PUBLISHER = {{Springer}},
VOLUME = {11},
NUMBER = {4},
PAGES = {pages 399--415},
YEAR = {2021},
MONTH = Nov,
DOI = {10.1007/s13389-021-00260-z},
PDF = {https://hal.sorbonne-universite.fr/hal-02883333/file/BaDueprintversion.pdf},
HAL_ID = {hal-02883333},
HAL_VERSION = {v1},
}

  • [PDF] J. Bajard, J. Eynard, P. Martins, L. Sousa, and V. Zucca, “An asymptotically faster version of FV supported on HPR,” in ARITH-2020 – 27th IEEE International Symposium on Computer Arithmetic, Portland, United States, 2020.
    [Bibtex] 
    @inproceedings{bajard:hal-02883325,
TITLE = {{An asymptotically faster version of FV supported on HPR}},
AUTHOR = {Bajard, Jean-Claude and Eynard, Julien and Martins, Paulo and Sousa, Leonel and Zucca, Vincent},
URL = {https://hal.sorbonne-universite.fr/hal-02883325},
NOTE = {Due to the Covid-19 crisis all around the world in 2020, the face-to-face meeting has been canceled. However, the paper selection process was completed. The accepted papers have been included in the ARITH-2020 proceedings and will soon be published on IEEE Xplore. They are also posted in the Programme section of this web site: http://arith2020.arithsymposium.org/},
BOOKTITLE = {{ARITH-2020 - 27th IEEE International Symposium on Computer Arithmetic}},
ADDRESS = {Portland, United States},
PUBLISHER = {{IEEE}},
YEAR = {2020},
MONTH = Jun,
KEYWORDS = {Fan-Vercauteren scheme ; Residue Number System ; Homomorphic Encryption},
PDF = {https://hal.sorbonne-universite.fr/hal-02883325/file/BEMSZ2020.pdf},
HAL_ID = {hal-02883325},
HAL_VERSION = {v1},
}

Comments are closed.