5
$\begingroup$

I’m a mathematician trying to get into cryptography. I have a somewhat silly question, but I can’t seem to find a proper answer anywhere. I am interested in whether or not there is a way to directly view the Shortest Vector Problem (SVP) in a finite dimensional lattice as an instance of the Hidden Subgroup Problem (HSP).

Looking around online, I can see that SVP is intimately related to the dihedral hidden subgroup problem. Indeed, Oded Regev has given a quantum reduction from a certain unique shortest vector problem to dihedral coset sampling. The thing is, I’m not particularly interested in the quantum computation aspect — I merely want to understand if SVP can be viewed as a case of HSP, in the same way that other “hard problems” that underpin cryptosystems like factoring and discrete logarithms can.

If I am understanding Regev’s result correctly, such a solution might not be possible. Regev’s reduction from Unique SVP to HSP cannot be carried out efficiently on a classical computer. But it seems that Regev is primarily interested in the quantum aspect and fleshing out a connection between lattice problems and quantum computation. So it could be that there is some other way.

Any resources would be greatly appreciated. Thanks

$\endgroup$

1 Answer 1

2
$\begingroup$

Regev's result is not quite a reduction of unique short vector problem to the hidden dihedral subgroup problem, but as you note a reduction to the quantum dihedral coset problem. This problem accepts as input a superposition of a large number of coset representatives of a reflection subgroup, and outputs a generator for the subgroup.

As the input here is a quantum state, this cannot be performed on a classical device.

The connection to the hidden dihedral subgroup problem is the strong belief that a quantum algorithm for solving this problem in polynomial time will begin by constructing a large superposition of coset representatives and the performing some sort of quantum Fourier analysis/representation theory on the superposition in order to concentrate output into a form that provides information on the generator. This assumption is not unreasonable as Shor's algorithm uses this framework to solve the hidden abelian subgroup problem.

Note that in a "black box" group the hidden abelian subgroup problem will take at least $|S|^{1/2}$ classical operations and I believe a similar result holds for classical operation and the hidden dihedral subgroup problem.

There are quantum solutions to the hidden dihedral subgroup problem that run in subexponential time, but the reduction process makes this a superexponential algorithm for uSVP.

There is also a dihedral quantum Fourier transform, but an efficient method to extract generator information form this has not yet been found.

This account provides a succinct and readable introduction to some of the ideas.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.