Paper 2020/1619
Getting Rid of Linear Algebra in Number Theory Problems
Paul Kirchner and PierreAlain Fouque
Abstract
We revisit some wellknown 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 highlevel 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 AreaTime cost. Finally, we show new AT costs for computing a discrete logarithm over an adversarial basis in finite fields.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 number theorydiscrete logarithmfactorizationVDF
 Contact author(s)

paul kirchner @ irisa fr
pierrealain fouque @ irisa fr  History
 20210104: last of 2 revisions
 20201231: received
 See all versions
 Short URL
 https://ia.cr/2020/1619
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1619, author = {Paul Kirchner and PierreAlain Fouque}, title = {Getting Rid of Linear Algebra in Number Theory Problems}, howpublished = {Cryptology ePrint Archive, Paper 2020/1619}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1619}}, url = {https://eprint.iacr.org/2020/1619} }