Recently I came across an interesting looking cryptography article Ring-LWE Ciphertext Compression and Error Correction: Tools for Lightweight Post-Quantum Cryptography by Markku-Juhani O. Saarinen, which specifically state

Ciphertext compression can significantly increase the probability of decryption errors.

Which I wonder now, does this indeed mean compressing the ciphertext, which I undertand isn't sensible (basically since encryption should randomize the output so it doesn't really compress after the operation) or doing the compression in the same go? Analogously to how AEAD does encryption and authentication.

I tried to gleanse something from the paper and read about this from the Internet, but being a rather layman on encryption methdos certainly doesn't help.


1 Answer 1


It does indeed mean to compress the ciphertext.

In very simplified terms:

You can think of the ciphertext generated by a Ring-LWE scheme as a bunch of numbers modulo a number $p$, in this case the prime 12289. Indeed, this output is effectively indistinguishable from uniformly random for someone who doesn't know the private key, as per the worst-case hardness theorem for Ring-LWE.

Decryption involves manipulating these numbers using the private key, resulting in a bunch of other numbers modulo $p$. Then, it tests whether these numbers are closer to 0, or 12289. How far away these numbers are from either 0 or 12289 is the error. The error is introduced by the encryption process itself, and is essential to the security of the system. Obviously, if the error is bigger than 12289/2, decryption won't be correct! Parameters are chosen such that the probability that this happens is exceedingly small.

Now, the way that this compression works is by compressing the numbers modulo 12289 all the way down to modulo 256. So if (approximately) $x \in [0, 48)$, then we map: $x \mapsto 0$. If $x \in [48,96)$, we map: $x \mapsto 1$, etc.

Obviously, we lose information, and we introduce a bit more error. Due to the nature of the decryption process, this error is magnified further, quite significantly so. But if the error was small enough to begin with, we can get away with the compression, and we can utilize all the benefits of 8 bit modular arithmetic, which is huge on hardware like AVR.

  • $\begingroup$ And to fix the introduced error, the method intrduces error correction code XECC, which is efficient (e.g. fast). OK, thanks, I think I got the hunch now. Quite a smart system idea. :) $\endgroup$
    – Veksi
    Nov 25, 2016 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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