In this talk, we introduce a new NP-complete variant of the multivariate quadratic problem. The computational challenge involves finding a solution to an algebraic system that meets the « regular » constraint, meaning that each block of the solution vector contains only one nonzero entry. Following this, we adapt and compare various techniques of cryptanalysis to study the asymptotic complexity of the average instance.