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:

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:

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

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

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:

The algorithm \(\mathcal{G}\) is able to decode when the number of errors is less than \(t\). In other words, here \eqref{org1ae1fb6} 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{org1ae1fb6}.

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:

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?

…And many coffees. Now I remember my personal motto that I must never forget: When I have an idea, either:

• it's just a bad idea;
• someone already had the same idea and often even better articulated;
• both!

In addition, in this post, I must plead guilty of beeing ultracrepidarian (not beyond the shoe) by offering opinions beyond my expertise. Hm, it seems I’m going to continue…

Well, I’ve read parts of a book chapter A Survey on Code-Based Cryptography – where the almost two hundred of pages don’t read as a novel but are still quite readable for one used to mathematical notations and some algebra. This book chapter sets on the correct rail the slap-dash I wrote above. Hum, my understanding is still quite limited, hence it surely remains uncorrected errors in what follows below, so please apply an error correcting code when reading my prose. Bah otherwise, instead of such prose, it’s better to directly dive into code-based cryptography literature!

Why is the exchange of compressed public-key more complex than it might appears at first? Because McEliece cryptosystem relies on two assumptions:

1. Decoding a random linear code is hard,
2. and The public code is not distinguishable from a random code.

Although one could envisage having security without indistinguishibility, then cryptographers like to err on the side of caution; I guess… or I bet! Being distinguishable paves the way for hypothetical structural strategies.

Roughly, the attacker has two possibilities: (a) recover the clear message from both the encrypted message \(c=mH+e\) and the public-key \((H, t)\) – these both only –, or (b) recover the private-key. The keystone of the both attacks is to potentially exploit some structure exposed when the cryptosystem does not behave “randomly”.