3
$\begingroup$

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:

  1. Generate keyspace using some security parameter.
  2. Randomly pick two keys.
  3. Generate a random permutation.
  4. Shuffle the matrix coefficients using the random permutation and key.
  5. Decrypt the resulting matrix using the random permutation and key.
$\endgroup$
  • $\begingroup$ Sorry, that's incomprehensible. $\;$ Why don't you link to the paper? $\;$ What's the "matrix" of step 4? $\;$ Is one of the two keys generated in step 2 used in step 4 and the other in step 5? If yes, the "symmetric" tag in the question likely is wrong; if no, why do we generate two keys and seem to use only one? $\endgroup$ – fgrieu Mar 23 '15 at 15:53
  • $\begingroup$ Actually the matrix is input matrix for outsourcing to cloud for inversion. Yes two keys of step 2 are used for encrytion in step 4 and decryption in step 5. $\endgroup$ – Shamminuj Rahman Mar 23 '15 at 15:56
  • $\begingroup$ ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6613485 $\endgroup$ – Shamminuj Rahman Mar 23 '15 at 15:57
  • 2
    $\begingroup$ Based on this preprint, each of steps 4 and 5 use both keys (not just one as implied by the lack of plural for the word key in points 4 and 5 of the question), and the cryptography indeed is symmetric. It belongs to the Snake Oil genre, specifically the Cryptography-using-reals-without-taking-into-account-precision sub-genre. $\endgroup$ – fgrieu Mar 23 '15 at 17:11
  • 1
    $\begingroup$ I have retracted my close vote since we now know the article, that makes the question answerable, even slightly entertaining, and certainly revealing of the ineffectiveness of the review process in some IEEE publications. $\endgroup$ – fgrieu Mar 24 '15 at 12:13
8
$\begingroup$

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>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.

$\endgroup$
  • $\begingroup$ Thanks. After getting Y from X through this cryptographic system ,if I generate a random n*n matrix Z and then compute X * Y * Z and outsource this to cloud , how much security will it provide? $\endgroup$ – Shamminuj Rahman Mar 24 '15 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.