Break this cipher! (math)

[nslay]

NOTE: \mathbf{} is broken ... I made vectors bold but they do not appear so.

I wandered into this cipher idea accidentally last night.  This cipher is very simple, but it does not appear trivial to break.
First off, the cipher operation is a linear transformation of the form

[latex]
\mathbf{c} = M \mathbf{x}
[/latex]

where [latex]\mathbf{c} \in \mathbb{R}^n[/latex] is the cipher text, [latex]\mathbf{x} \in \mathbb{R}^n[/latex] is the input block of data and [latex]M \in \mathbb{R}^{n \times n}[/latex] of the form

[latex]
M = PZR
[/latex]

Here [latex]P,R[/latex] are randomly generated invertible [latex]n \times n[/latex] matrices and [latex]Z[/latex] is an [latex]n \times n[/latex] singular matrix of the form

[latex]
Z = n I - \mathbf{1} \mathbf{1}^T \quad \text{where } \mathbf{1} = \begin{bmatrix}
1 \\
1 \\
\vdots \\
1 \\
\end{bmatrix}
[/latex]

(Sorry, [latex]\mathbf{1}[/latex] vector should be bold)

As a consequence, the matrix [latex]M[/latex] is also singular and the factorization is not unique (beyond mere scalar factors!).  However, even though [latex]M[/latex] is not invertible, this linear transformation can still be reversed with additional information.
Denote [latex]\mathbf{v} \in \mathbb{R}^n[/latex] to be the secret key either shared in advance or generated by some key agreement protocol.  Now we require the matrix [latex]R[/latex] to be randomly generated so that [latex]\mathbf{v} = R^T \mathbf{1}[/latex] (again \mathbf{} is broken, [latex]\mathbf{1}[/latex] should be bolded as it is a vector).  In addition to the cipher text [latex]\mathbf{c}[/latex], the value [latex]k = \mathbf{v}^T \mathbf{x}[/latex] is also provided to invert [latex]M[/latex].

The matrix [latex]Z[/latex] has the property that rows and columns sum to [latex]0[/latex].  I call these types of matrices zero sum matrices and they can be used to easily solve problems with summation-based constraints as unconstrained problems (an alternative to Lagrange multipliers for example).  [latex]Z[/latex] projects [latex]\mathbb{R}^n[/latex] into [latex]\{ \mathbf{x}\ :\ \mathbf{1}^T \mathbf{x} = 0,\ \mathbf{x} \in \mathbb{R}^n \}[/latex], the space of vectors whose components sum to [latex]0[/latex].  Any linear transformation with [latex]Z[/latex] discards the summation information of [latex]\mathbf{x}[/latex].  However, if the component sum of [latex]\mathbf{x}[/latex] is known, then this linear transformation can be inverted.  In our particular problem

[latex]
\mathbf{x} = \frac{1}{n} ( Z \mathbf{x} + \mathbf{1} (\mathbf{1}^T \mathbf{x}) )
[/latex]

(Sorry, [latex]\mathbf{1}[/latex] vector should be bold)

So, inverting [latex]M[/latex] works like this:
Given [latex]P,R,\mathbf{c},k[/latex]

1) Solve [latex]P \mathbf{y} = \mathbf{c}[/latex]
2) Compute [latex]\mathbf{z} = \frac{1}{n} ( \mathbf{y} + \mathbf{1} k )[/latex] (Sorry, [latex]\mathbf{1}[/latex] vector should be bold)
3) Solve [latex]R \mathbf{x} = \mathbf{z}[/latex] to recover [latex]\mathbf{x}[/latex]

Here's the crypto scheme:
Bob wants to securely share [latex]\mathbf{x} \in \mathbb{R}^n[/latex] with Alice.  Bob and Alice both have the secret key [latex]\mathbf{v}[/latex].

Alice	Bob
[latex]\mathbf{v}[/latex]	[latex]\mathbf{v},\mathbf{x}[/latex]

1) Alice randomly generates invertible [latex]P,R \in \mathbb{R}^{n \times n}[/latex] so that [latex]\mathbf{v} = R^T \mathbf{1}[/latex] (Sorry, [latex]\mathbf{1}[/latex] vector should be bold) and computes

[latex]
M = PZR
[/latex]

Alice shares [latex]M[/latex] with Bob.

Alice	Bob
[latex]\mathbf{v},P,R,M[/latex]	[latex]\mathbf{v},\mathbf{x},M[/latex]

2) Bob computes [latex]\mathbf{c} = M \mathbf{x}[/latex] and [latex]k = \mathbf{v}^T \mathbf{x}[/latex] and shares [latex]\mathbf{c},k[/latex] with Alice

Alice	Bob
[latex]\mathbf{v},P,R,M,\mathbf{c},k[/latex]	[latex]\mathbf{v},\mathbf{x},M,\mathbf{c},k[/latex]

3) Alice solves

[latex]
P \mathbf{y} = \mathbf{c}
\mathbf{z} = \frac{1}{n} ( \mathbf{y} + \mathbf{1} k )
R \mathbf{x} = \mathbf{z}
[/latex]

(Sorry, [latex]\mathbf{1}[/latex] vector should be bold)

to recover [latex]\mathbf{x}[/latex].

Alice	Bob
[latex]\mathbf{v},P,R,M,\mathbf{c},k,\mathbf{x}[/latex]	[latex]\mathbf{v},\mathbf{x},M,\mathbf{c},k[/latex]

Example Problem:
If you have the time and interest, I'd be curious if any of you could break the following example ciphertext:

[latex]
\mathbf{c} = \begin{bmatrix}
8856 \\
-16178 \\
246 \\
102128 \\
50331 \\
110304 \\
-6464 \\
-71322 \\
-13541 \\
-45762 \\
\end{bmatrix}
[/latex]

[latex]
k = 17409
[/latex]

Given

[latex]
M = \begin{pmatrix}
-156 & 96 & -10 & 34 & 32 & 134 & -162 & 296 & 268 & -138 \\
148 & -178 & -30 & 78 & 224 & -452 & -124 & -38 & -254 & 474 \\
84 & 236 & 0 & -216 & 372 & 194 & 58 & -344 & 428 & 302 \\
572 & 148 & 570 & 42 & 216 & 352 & 94 & 88 & 174 & 156 \\
204 & 6 & 140 & 64 & 127 & 269 & 223 & -79 & 273 & 177 \\
336 & -56 & 440 & 216 & -142 & 496 & 372 & 224 & -178 & 58 \\
-36 & 146 & -30 & 134 & 292 & -206 & 78 & -324 & 408 & -38 \\
-358 & -262 & -290 & -18 & 186 & -318 & -176 & -52 & 164 & 146 \\
6 & 144 & 50 & -154 & 53 & 1 & -143 & -21 & 57 & -117 \\
-58 & -12 & -440 & -68 & -334 & -268 & 34 & -82 & -466 & 86 \\
\end{pmatrix}
[/latex]

Copy and paste for matlab/octave input

Code Select Expand


c = [ 8856 -16178 246 102128 50331 110304 -6464 -71322 -13541 -45762 ]';
k = 17409;
M = [ -156 96 -10 34 32 134 -162 296 268 -138;
148 -178 -30 78 224 -452 -124 -38 -254 474;
84 236 0 -216 372 194 58 -344 428 302;
572 148 570 42 216 352 94 88 174 156;
204 6 140 64 127 269 223 -79 273 177;
336 -56 440 216 -142 496 372 224 -178 58;
-36 146 -30 134 292 -206 78 -324 408 -38;
-358 -262 -290 -18 186 -318 -176 -52 164 146;
6 144 50 -154 53 1 -143 -21 57 -117;
-58 -12 -440 -68 -334 -268 34 -82 -466 86 ];


[rabbit]

This looks very interesting, but it's been years since my Linear and Number Theory classes.

[nslay]

The pseudoinverse almost gives you the input vector [latex]\mathbf{x}[/latex] (2% relative error ... though the residual is quite large).  However, that's due to my poorly generated matrices [latex]P,R[/latex] which have low variance.  If [latex]P,R[/latex] have a large variance, then the relative error blows up.  So, [latex]P,R[/latex] must be generated with care, otherwise the pseudoinverse can almost decipher [latex]\mathbf{c}[/latex].

[nslay]

One can also allow [latex]Z[/latex] to be arbitrary where
[latex]
Z = \text{diag}(\mathbf{w}) - \frac{\mathbf{w} \mathbf{w}^T}{\mathbf{1}^T \mathbf{w}} \qquad \mathbf{w} \in \mathbb{R}^n
[/latex]

The vector [latex]\mathbf{w}[/latex] is chosen so that [latex]R^T \mathbf{w} = \mathbf{v}[/latex].  This allows [latex]R[/latex] to be random without needing adjustment as in the first post.

The cipher still works the same way
[latex]
\mathbf{c} = M \mathbf{x}
k = \mathbf{v}^T \mathbf{x}
[/latex]

Deciphering is modified slightly
[latex]
P \mathbf{y} = \mathbf{c}
\mathbf{z} = \text{diag}(\mathbf{w})^{-1} ( \mathbf{y} + \frac{k \mathbf{w}}{\mathbf{1}^T \mathbf{w}} )
R \mathbf{x} = \mathbf{z}
[/latex]