4
$\begingroup$

I posted this question on the cryptography stack exchange with a bounty, but I haven’t gotten much attention. I think part of the reason might be that I’m really interested in the use of group theory in cryptography — not cryptography and computational efficiency per se. For full transparency though, here is a link to the cryptography stack exchange post.

Review of SVP and HSP

SVP: Given a lattice $L$ in a normed vector space $V$, the shortest vector problem asks you to find the point in the lattice with the smallest norm. This is a hard problem, in a certain sense of the word “hard,” and is related to cracking certain lattice-based cryptosystems like NTRU.

HSP: Let $G$ be a group, $H$ a subgroup of $G$, and $f: G \rightarrow X$ a set-map. We say that $f$ hides the subgroup $H$ if for all $a,b \in G$, we have that $f(a) = f(g)$ if and only if $a$ and $b$ are in the same coset of $H$. Suppose you’re given an oracle for some $f:G \rightarrow X$, and you know that $f$ is hiding some subgroup $H$ of $G$. The hidden subgroup problem asks if you can efficiently find a generating set for $H$. Here efficiently is barring strategies like “compute $f(g)$ for every $g \in G$.” Several problems that underpin cryptosystems such as factoring and computing discrete logarithms can be viewed as instances of the hidden subgroup problem.

Question

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$
7
  • 2
    $\begingroup$ Can you clarify something for those of us not familiar with these topics? For the HSP, you require $G$ to be a finite group, but the wikipedia article only requires $X$ to be finite. So do you really require $G$ to be finite? $\endgroup$
    – 2'5 9'2
    Commented May 23 at 4:46
  • $\begingroup$ Ahh good catch. $G$ need not be finite, but for computability reasons it’s often handy for it to be. For example, the quantum algorithms used to solve factoring as a hidden subgroup problem uses a superposition over all points in $G$, necessitating that $G$ is finite. But this doesn’t matter for my purposes, and I am more than happy to have an infinite $G$. I have removed the word “finite” from the post. $\endgroup$
    – Joe
    Commented May 23 at 16:31
  • 1
    $\begingroup$ OK, cool. Some natural groups to think about here could be infinite, but finitely generated. So still something you could work with computationally. $\endgroup$
    – 2'5 9'2
    Commented May 24 at 1:48
  • $\begingroup$ Looks like yes. en.wikipedia.org/wiki/Hidden_subgroup_problem. See the 'instance' table $\endgroup$
    – Gopal Anantharaman
    Commented May 28 at 21:54
  • 1
    $\begingroup$ @GopalAnantharaman So that table doesn’t actually give a reference! The idea that “SVP can be reduced to a dihedral HSP” seems to be oft quoted, but I can’t actually find a reference! $\endgroup$
    – Joe
    Commented May 28 at 22:44

0

Reset to default

You must log in to answer this question.