1
$\begingroup$

Since code-based PKEs work by correcting error introduced into the ciphertext, and since truncating ciphertext constitutes both saving in bandwidth and introducing "errors", my question being:

  1. can we achieve the combined goal by using truncating?
  2. is there any scheme that does that? if not why?
$\endgroup$
2
  • $\begingroup$ Interesting question, I've looked for some examples, however, couldn't find a related one. Yes, once can gain some space, however, does it worth? $\endgroup$
    – kelalaka
    Nov 23, 2023 at 21:34
  • $\begingroup$ Cross-posted on the PQC Google mailing list. $\endgroup$
    – DannyNiu
    Nov 24, 2023 at 3:51

1 Answer 1

2
$\begingroup$

I'm not aware of a scheme that does this, but I'm not an expert so there may well be such a scheme and I just don't know it.

As I see it, the main issue is that most code-based crypto uses linear codes, and truncation is a linear operation. So correcting a truncated codeword (also known as erasure correction) can be done efficiently even if you have a randomized description of the code.

You could mix errors and erasures, but (depending on the scheme) this might just be equivalent to encoding with a shorter code and then adding errors -- which is to say, it might be the same as an error-only scheme with different parameters.

Also, for some code-based cryptosystems this trick seems inapplicable to begin with. For example, although the original McEliece cryptosystem sent corrupted ciphertexts, modern versions of it such as "Classic McEliece" are based on Niederreiter's improvement, where you send the syndrome instead. I don't see how truncation would help there.

You might be able to do something in the direction you suggested though, where instead of truncating you would round to the nearest codeword of a second code. Or maybe it would work with some kind of code where the truncation operation works over a different field than the encoding operation (or similar) so that it's not just a linear operation. Or maybe you could use a deletion-correcting code, and delete data from random locations within the codeword.

$\endgroup$

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.