What is this cryptosystem called? From a paper Outsourcing Large Matrix Inversion Computation to A Public Cloud (IEEE Transactions on Cloud Computing, Vol. 1, N°1, 2013; alternate source requiring registration; preprint), I got to know about an encryption-decryption system. As I know only the basics of cryptography, I can't just figure out which cryptosystem this is. The basic algorithm is:


Generate keyspace using some security parameter.
Randomly pick two keys.
Generate a random permutation.
Shuffle the matrix coefficients using the random permutation and key.
Decrypt the resulting matrix using the random permutation and key.
Review of the paper

The paper's goal is to offload to a server the computation of the inverse of a (non-singular) $n\times n$ matrix $X$ of (the floating-point approximation of) real numbers, while keeping $X$ and $X^{-1}$ confidential.

Towards that goal, the paper's method is to


draw a secret key consisting of two random permutations and $2n$ non-zero random real numbers (that key will be used for a single matrix $X$);
transform $X$ yielding $Y$ according to the key by performing rows and columns swaps and scalings:

swap rows according to one permutation;
swap columns according to the other;
multiply each raw by a secret random real non-zero value;
multiply each column by a secret random real non-zero value;

send the result $Y$ to the server
obtain the alleged $Y^{-1}$
transforms the alleged $Y^{-1}$ into the alleged $X^{-1}$ by performing rows and columns scalings and swaps:

multiply each raw by the secret random real non-zero value formerly used for the column of same index
multiply each column by the secret random real non-zero value formerly used for the row of same index
swap rows according to the inverse of the permutation formerly used for columns;
swap columns according to the inverse of the other permutation;

verify the result by recomputing some of the coefficients of $X\cdot X^{-1}$ and checking if that's $1$ for the diagonal and $0$ elsewhere.


The paper


rightly observes that for large enough $n$, the bulk of the work is offloaded to the server (the client has $\mathcal O(n^2)$ work, when the server has $\mathcal O(n^\rho)$ works for $2.373\le\rho\le3$ depending on the matrix inversion technique used by the server);
has a section on Security Guarantee that culminates in the imprecise


  the cloud cannot recover X from Y by trivial means.(..) the security analysis follows an informal approach. A meaningful and challenging future work lies in giving a rigorous proof of security.

claims in the abstract (too optimistically at the very least) that it


  fulfills the goals of correctness, security, robust cheating resistance, and high efficiency

wrongly ignores issues of numerical stability in the verification procedure (as well as underflow and overflow that could occur in the scaling process), and is thus incorrect as described (the cheating resistance test has false positives in any implementation with bounded bandwidth to the server);
is insecure from a cryptographic standpoint for $n&gt;1$, in particular because:

the number of elements equal to zero (or of very small magnitude) in $X$ is the same as in $Y$;
for even $n$ and $X$ with no zero elements, the sign of the product of all entries in $X$ is the same as in $Y$;
at least for moderate $n$, given $Y$ and $2n-1$ out of $n^2$ elements of a random $X$, it is typically possible to determine the $n^2-2n+1$ unknown elements of $X$, and a key equivalent to the original one.



Source and name of the cryptographic algorithm

The algorithm used to transform the matrix belongs to symmetric homomorphic cryptography. It is named disguise by Mikhail J. Atallah, Konstantinos N. Pantazopoulos, John R. Rice, Eugene H. Spafford: Secure Outsourcing of Scientific Computations, Technical report of the Department of Computer Sciences of Purdue University (1999), where it appears in section 1.4.1, with the same notation as the 2013 article discussed (which sadly does not cite this apparent inspiration).

The 1999 paper correctly identifies the security shortcomings of disguises (section 4.1), when the 2013 paper sidesteps theses. The 1999 paper has a section (3.1.2) on matrix inversion using this disguise technique, but what the 2013 article describes is more focused and slightly simpler.

Update: an earlier reference is by Mikhail J. Atallah, Konstantinos N. Pantazopoulos, Eugene H. Spafford: Secure Outsourcing of Some Computations, Technical report of the Department of Computer Sciences of Purdue University (1996); but there the technique is not yet named.