Paper 2020/1619

Getting Rid of Linear Algebra in Number Theory Problems

Paul Kirchner and Pierre-Alain Fouque


We revisit some well-known cryptographic problems in a black box modular ring model of computation. This model allows us to compute with black box access to the ring $\mathbb{Z}/m\mathbb{Z}$. We develop new generic ring algorithms to recover $m$ even if it is unknown. At the end, Maurer's generic algorithm allows to recover an element from its black box representation. However, we avoid Maurer's idealized model with CDH oracle for the multiplication in the hidden ring by introducing a new representation compatible with ring operations. An element is encoded by its action over the factor basis. Consequently, we can multiply two elements with classical descent computations in sieving algorithms. As the algorithms we propose work without using an expensive linear algebra computation at the end, even though they manipulate large sparse matrices, we can exploit a high-level of parallelism. Then, we consider general groups such as imaginary quadratic class group and the Jacobian of a hyperelliptic curve, and obtain new methods for group order computation. The repeated squaring problem and the adaptive root problem used in the construction of Verifiable Delay Functions are particularly easy to solve in the black box modular ring, the high degree of parallelism provided by our method allows a reduction in the time to solve them. We improve the smoothing time, and as a result, we break Verifiable Delay Functions and factorize weak keys with lower Area-Time cost. Finally, we show new AT costs for computing a discrete logarithm over an adversarial basis in finite fields.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
number theorydiscrete logarithmfactorizationVDF
Contact author(s)
paul kirchner @ irisa fr
pierre-alain fouque @ irisa fr
2021-01-04: last of 2 revisions
2020-12-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Paul Kirchner and Pierre-Alain Fouque},
      title = {Getting Rid of Linear Algebra in Number Theory Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1619},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.