  Multidimensional signals like 2-D and 3-D images or videos are inherently
sensitive signals which require privacy-preserving solutions when processed in
untrustworthy environments, but their efficient encrypted processing is
particularly challenging due to their structure, dimensionality and size. This
work introduces a new cryptographic hard problem denoted m-RLWE (multivariate
Ring Learning with Errors) which generalizes RLWE, and proposes several
relinearization-based techniques to efficiently convert signals with different
structures and dimensionalities. The proposed hard problem and the developed
techniques give support to lattice cryptosystems that enable encrypted
processing of multidimensional signals and efficient conversion between
different structures. We show an example cryptosystem and prove that it
outperforms its RLWE counterpart in terms of security against basis-reduction
attacks, efficiency and cipher expansion for encrypted image processing, and we
exemplify some of the proposed transformation techniques in critical and
ubiquitous block-based processing applications
