Constrained inhomogeneous spherical equations: average-case hardness

Abstract

In this paper we analyze computational properties of the Diophantine problem (and its search variant) for spherical equations ${\prod }_{i=1}^m{z}_i^{-1}{c}_i{z}_i=1$ (and its variants) over the class of finite metabelian groups $G_{p,n}={\mathbb{Z}}_p^n⋊{\mathbb{Z}}_p^{\ast }$, where $n\in \mathbb{N}$ and $p$ is prime. We prove that the problem of finding solutions for certain constrained spherical equations is computationally hard on average (assuming that some lattice approximation problem is hard in the worst case).

Published in the journal of Groups, Complexity, Cryptology