6
$\begingroup$

Elliptic curve cryptography makes it very easy to check if a curve point is valid. If it’s on the curve, and is not a low order point, then it’s valid. An extra check that it is canonical might be needed, but that’s also easy.

On the other hand, post-quantum cryptosystems generally don’t allow validating inputs without the secret key. This gives rise to a wide variety of chosen-ciphertext assisted side channel attacks, which can leak the whole secret key. This makes implementations on devices like smart cards much harder.

Why do post-quantum cryptosystems generally have this unfortunate property? I know that CSIDH does not have this problem, and that one can avoid it for other systems using a zero-knowledge proof. But I have yet to see those deployed.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Because it is an inherent / emergent property of the mathematical problem? I'm pretty sure that nobody designed for the secret to be required for input validation... However, this is a rather shallow insight, so I hope somebody can give an answer and dive deeper into this particular "why". $\endgroup$ Commented 2 days ago
  • 1
    $\begingroup$ I would challenge the premise. You can't publicly check whether say a Cramer-Shoup ciphertext is valid either. $\endgroup$ Commented 2 days ago
  • $\begingroup$ Hm am I out of the loop with the nomenclature or isn't this true for OTP too? You can hardly validate the ciphertext with the key. $\endgroup$ Commented yesterday
  • $\begingroup$ @pipe: With symmetric crypto (which OTP is), there typically isn't a way a validate a ciphertext without the secret key (or even with the secret key if the method doesn't have ciphertext expansion). Instead, symmetric crypto specifically aims at a ciphertext that is indistinguishable from random. $\endgroup$ Commented 9 hours ago

1 Answer 1

Reset to default
6
$\begingroup$

Why do post-quantum cryptosystems generally have this unfortunate property?

Here is one way to approach this: for both lattice-based KEMs (e.g. ML-KEM) and code-based KEMs (e.g. HQC), the encapsulation works (at a high level) like this: they take a purely linear system, and then sprinkle in some errors (to prevent an adversary from taking advantage of the linearity).

Now, if somewhere were able to distinguish the result from a random ciphertext, they might be able to use that to deduce the errors that were inserted (e.g. by testing potential error bits; whether removing an error bit made it look more like a valid lattice point/code word). If they could do that and remove the errors, we'd be left with a purely linear system, which could easily be broken.

Because of this, the designers make sure that the ciphertexts are indistinguishable from random, which prevents the adversary from deducing the errors, but also prevents an easy way to distinguish possible ciphertexts from random.

Instead, we just have to be careful with the postdecapsulation check (which is also needed to address attacks that take a valid ciphertext and tweak it slightly, to see if increases the error to the point where it cannot be decapsulated correctly).

Now, not all PQ algorithms follow this 'tweaked linear system' model; CSIDH doesn't, which is why the above logic doesn't apply to them.

Improve this answer
$\endgroup$

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.