About solving the Multidimensional Hidden Subset Sum Problem

Given a set of integers produced as subset-sums with respect to the same set of unknown weights, the hidden subset sum problem consists in recovering both the hidden weights and the chosen subsets. In this paper we consider an extension of this problem when the secret weights are multidimensional vectors, i.e. the Multidimensional Hidden Subset Sum Problem (Multi-HSSP). Specifically, we prove that
polynomial HSSP-solvers can be modified to lower the bound on the minimal modular size and their asymptotic complexity. For instance, if we have n secret weights of dimension n/2, we can heuristically solve Multi-HSSP with a modulus linear in n with running time O(n^7 ), given ≈ n^2 /2 subset-sums.