37 citations · 93 across the 10 of their papers we have counts for
11 papers
An efficient quantum algorithm for lattice problems achieving subexponential approximation factor
Lior Eldar, Sean Hallgren
We give a quantum algorithm for solving the Bounded Distance Decoding (BDD) problem with a subexponential approximation factor on a class of integer lattices. The quantum algorithm…
Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
Jintai Ding, Vlad Gheorghiu, András Gilyén +2
Recently Chen and Gao~\cite{ChenGao2017} proposed a new quantum algorithm for Boolean polynomial system solving, motivated by the cryptanalysis of some post-quantum cryptosystems.…
Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs
Kirsten Eisentraeger, Sean Hallgren, Chris Leonardi +2
Computing endomorphism rings of supersingular elliptic curves is an important problem in computational number theory, and it is also closely connected to the security of some of th…
On Basing One-way Permutations on NP-hard Problems under Quantum Reductions
Nai-Hui Chia, Sean Hallgren, Fang Song
A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to av…
How hard is deciding trivial versus nontrivial in the dihedral coset problem?
Nai-Hui Chia, Sean Hallgren
We study the hardness of the dihedral hidden subgroup problem. It is known that lattice problems reduce to it, and that it reduces to random subset sum with density and also…
Classical Cryptographic Protocols in a Quantum World
Sean Hallgren, Adam Smith, Fang Song
Cryptographic protocols, such as protocols for secure function evaluation (SFE), have played a crucial role in the development of modern cryptography. The extensive theory of these…