A compressed cryptic diner with approximations

Let consider a \(t\) error \((n, k)\) linear code where:

• \(\mathcal{G}\) is an efficient decoding algorithm,
• \(G\) is any generator \((k, n)\) matrix of this linear code.

Such error correcting code holds the property:

\begin{equation} \label{org730345f} \Big(xG + y\Big)\mathcal{G} = x \quad\quad \forall x,\quad \forall y,\quad ||y||_{0}\leq t \end{equation}

It means: once the message \(x\) of length \(k\) is encoded, i.e., \(xG\) of length \(n\), it can still be decoded although it contains at most \(t\) errors. Here the link between \((n, k)\) and \(t\) is let as an exercise for the reader.

Please note that \(||\cdot ||_{0}\) defined as a procedure that counts the non-zero elements isn’t a mathematical norm; it’s an abuse terminology and notation. Despite not being a norm, the associated metric, known as Hamming distance, is a valid distance.

The notation might appear weird, especially the left application; why not? Concretely, the message \(x\) is of length \(k\) and is a row vector, then the encoded message is of length \(n>k\). All in all, in summary:

• Encoding: apply the matrix-vector product \(xG\),
• Decoding: apply the algorithm \(\Big(\cdot\Big)\mathcal{G}\).

The McEliece cryptosystem is an encryption algorithm developed by Robert McEliece in 1978 and based on error correcting code. Although probably not designed initially for post-quantum cryptography, it is a now a candidate for post-quantum cryptography, because the claim¹ – without knowing \(\mathcal{G}\), decoding is NP-hard – resists to quantum attacks². Hence, the McEliece cryptosystem exploits two strategies:

• The encoding matrix \(G\) is obfuscated,
• As many errors as possible are added, up to \(t\), when encrypting.

Thus, the asymmetric cryptosystem reads:

• \(\Big\{\mathcal{G}, S, P\Big\}\) is the private key, where:
  • \(S\) is a random non-singular \((k, k)\) matrix,
  • \(P\) is a random permutation \((n, n)\) matrix.
• \(\Big\{H, t\Big\}\) is the public key, where \(H = SGP\).

The encryption of the message \(m\) is straightforward: \(c = mH + e\) where \(||e||_{0}=t\). Then the encrypted message \(c\) can be exchanged and only the person knowing the private key is able to decode.

Deciphering applies \(P^{-1}\mathcal{G}S^{-1}\) to the encrypted message \(c\). Namely, it reads:

\begin{eqnarray*} cP^{-1}\mathcal{G}S^{-1} &=& \Big(mH + e \Big)P^{-1}\mathcal{G}S^{-1} \\ &=& \Big(mSGP + e \Big)P^{-1}\mathcal{G}S^{-1} \\ &=& \Big(mSGPP^{-1} + eP^{-1} \Big)\mathcal{G}S^{-1} \\ &=& \Big(mSG + eP^{-1} \Big)\mathcal{G}S^{-1} \end{eqnarray*}

Considering \eqref{org730345f}, a part of the last line from above reads:

\begin{equation*} \Big(mSG + eP^{-1} \Big)\mathcal{G} = \Big(xG + y \Big)\mathcal{G} = x = mS \end{equation*}

where \(||y||_{0}=||eP^{-1}||_0=||e||_{0}=t\) because \(P^{-1}\) is a permutation matrix. Finally,

\begin{eqnarray*} cP^{-1}\mathcal{G}S^{-1} &=& \Big(mS \Big)S^{-1} \\ &=& m \end{eqnarray*}

So far, so good!

What’s one annoying problem with McEliece cryptosystem? The size of the keys and especially the public key, since the public key might be broadly shared with many peers.

Now, what follows draws my naive “intuition” which is surely incorrect and wrong!

Let consider \(\mathcal{C}\) an algorithm that is able to “approximate” a matrix, e.g., \(A=\Big(G\Big)\mathcal{C}\). Such approximation means the encoding produces errors, i.e., \(xA = xG + \varepsilon_{x}\). Therefore, the question becomes the control of \(||\varepsilon||_0\) compared to the errors \(t\) that the error correcting code is able to correct. It’s probably very difficult to get an explicit formal bound, thus, the engineer in me would be tempted to evaluate it: generate \(i\) random message and compute \(\mathbb{E}(||x_iA - x_iG||_0)\). Arf.

Again, \(A\) is an approximation of the encoding application of \(G\), so it means that \(A\) and \(G\) have the same matrix size. The idea is to then reduce the public key size by a lossless compression, still keeping the two key ingredients (obfuscation and as much as possible errors).

Assuming such approximation algorithm, the public key becomes \(F=SAP\) and the encrypted message \(c^\prime = mF + e^\prime\) where \(||e^\prime||_0\) depends on \(t\) and also the error of approximation \(||\varepsilon||_0\).

The deciphering reads similarly as before:

\begin{eqnarray*} cP^{-1}\mathcal{G}S^{-1} &=& \Big(mF + e^{\prime} \Big)P^{-1}\mathcal{G}S^{-1} \\ &=& \Big(mSA P + e^{\prime} \Big)P^{-1}\mathcal{G}S^{-1} \\ &=& \Big(mSA + e^\prime P^{-1} \Big)\mathcal{G}S^{-1} \\ &=& \Big(mSG + \varepsilon + e^{\prime}P^{-1} \Big)\mathcal{G}S^{-1} \end{eqnarray*}

The algorithm \(\mathcal{G}\) is able to decode when the number of errors is less than \(t\). In other words, here \eqref{org730345f} holds if \(||\varepsilon + e^{\prime}P^{-1}||_0\leq t\).

It’s where all becomes very tedious:

1. It’s probably difficult to get a bound for \(||\varepsilon||_0\).
2. Triangle inequality doesn’t help much about \eqref{org730345f}.

All that said, it doesn’t answer either to the these fundamental questions:

• Does the public key \(F\) lossless compress compared to \(H\)?
• A good rate of a lossless compression means the public key \(F\) owns an internal structure, therefore, does it open surfaces of attack?

Warning: /The usual notation by compressed sensing community is column vector and not row vector. Well, it’s left or right matrix-vector product and some transpose around. For consistency, the previous notation is kept; it does not matter much. Be aware when reading literature!/

Let \(x\) a signal of length \(p=kn\). Let \(\Psi\) a basis \((p, p)\) matrix where \(x=\chi\Psi\) and \(||\chi||_0\leq ||x||_0\). Let \(\Phi\) a measure \((p, q)\) matrix where \(q < p\); it means \(q\) samples of \(x\).

The Compress Sensing problem solves:

\begin{equation*} s = argmin~~||z||_{i} \quad such~that \quad ||x\Phi - z\Psi\Phi||_{j} \end{equation*}

where the choice of the norms is let as an exercise³ for the reader. The key here is about the choice of the pair \((\Psi, \Phi)\): it must satisfy the Compressed Sensing properties, e.g., Restricted Isometry Property (RIP), Exact Reconstruction Principle, Uniform Uncertainty Principle (UUP), etc.

The idea of Compress Sensing is to capture a sparse representation of a signal with few measures. And under some constrainted conditions, there is no loss between the original signal and its sparse representation.

Let consider the approximation algorithm for a \((k, n)\) matrix named \(X\):

• \(x=\Big(X\Big)\mathcal{V}\) where \(\mathcal{V}\) is an algorithm which transforms the \((k, n)\) matrix into a \(kn\) vector; assuming such algorithm is invertible.
• Solve the Compress Sensing problem.
• \(y=s\Psi\).
• Return \(Y=\Big(y\Big)\mathcal{V}^{-1}\) where \(\mathcal{V}^{-1}\) transforms back the \(kn\) vector into a \((k, n)\) matrix.

The question becomes the control of the error of the approximation. For instance, is it possible to bound \(||x - s\Psi||\) in term of errors \(t\)?

If we consider \(A\) the resulting approximated encoding matrix by such Compressed Sensing algorithm, then the faulty encoding process is \(xA = xG + \varepsilon_{x}\) for any message \(x\). The question: is \(||\varepsilon_{x}||_0\) controllable with decoding errors rate \(t\)?

If yes – huge assumption! –, it means one ingredient is satisfied, what about the other? Is \(A\) obfuscated enough? If yes – another huge assumption! – then \(A\) can be used as a public key. The approximated matrix is built to be sparse so well lossless compressed, but such compression, does it provide elements for an attack?

If the approximated encoding matrix \(A\) isn’t obfuscated enough, then the public key generation needs the application of matrices \(S\) and \(P\). Does the result keep sparsity property for being lossless compressed? If no, doomed!

If the error isn’t controllable with the decoding errors rate \(t\), woof, almost doomed too.

That’s all for my naive still dumb intuition. Ready for yet another compressed cryptic diner with approximations?