This question is potentially relevant to NIST post-quantum cryptography standards, involving code-based cryptosystems such as McEliece, BIKE and HQC.

For these cryptosystems, it seems that an attacker can use a "decoding one out of many" strategy as described here to decrypt one out of a list of $n$ ciphertexts, for a cost of approximately $\sqrt{n}$ times less than the cost of attacking a single ciphertext.

I don't think the security definition given in the NIST CFP explicitly covers this scenario. However, it does seem like if you're worried about $2^{64}$ decryption queries from a CCA adversary, it seems reasonable to be worried about $2^{64}$ target ciphertexts.

How concerned should one be about this? How much security does one need against these kinds of attacks?

(Note the above paper is cited in the BIKE and HQC specs, but only in the context of assessing security loss due to the use of quasi-cyclic matrices, not in the context of assessing security loss due to multiple ciphertexts. The paper is cited by the Classic McEliece in the sense of a multi ciphertext attack.)

This question is crossposted on PQC forum.



Your Answer

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