Score:11

Requirements for security against multi-target attacks, for McEliece and other code-based cryptosystems?

dk flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.