# Post quantum security experiment

In cryptography there are 4 basic attack classifications:

• Ciphertext-Only Attack
• Known-Plaintext Attack
• Chosen-Plaintext Attack
• Chosen-Ciphertext Attack

In Katz & Lindell's textbook (2nd edition) one can find a security definition and experiment for those attacks. E.g. to define CPA-security. Those experiment are between a arbitrary adversary and a challenger. I was wondering, if there exists such a definition and experiment for post quantum security. If this is the case, can someone write them down? If that's not the case, can someone explain why?

• As far as I understand it, there should not be a security definition for post quantum, because it only affects the power of an arbitrary adversary. But do we still have a probabilistic polynomialtime adversary? Oct 28 at 11:25
• BPQ defines the class of the problem, not the attack model! Oct 28 at 11:40

Cryptanalysis with adversaries capable of submitting superpositions of inputs and interpreting superpositions of outputs does exist, but is still relatively new with relatively little work. The earliest example that I'm aware of Zhandry's work on quantum-secure pseudo-random functions. I don't think the term "quantum chosen message" was introduced prior to Boneh and Zhandry's work on quantum-secure MACs. There does seem to be a separation between this and the classical security models. There's also use of a (non-adaptive) quantum chosen ciphertext adversary in LWE analysis by Alagic et al. for example.

It's not clear to me how a quantum chosen message attack could be realised in practice unless users implement their cryptography on quantum hardware or if adversaries are somehow able to clone a classical implementation to quantum hardware (but are somehow unable to read the key from the classical implementation while cloning).

• "if adversaries are somehow able to clone a classical implementation to quantum hardware (but are somehow unable to read the key from the classical implementation while cloning)." - this actually is the case for "whitebox cryptography", where the attacker is given a full description (including an obscured key), and whose goal is to do something (e.g. rederive the key) he couldn't do with a blackbox implementation. Oct 28 at 12:43
• "does exist" uses a liberal interpretation of exists, common to all works on quantum cryptanalysys, comparable to that in worldbuilder.
– fgrieu
Oct 28 at 14:29
• @fgrieu: Well, yes. The analysis exists; what the implications of the analysis are is a different matter. On the other hand, there's a lot of classical cryptanalysis of block ciphers that depend on very extreme attack models and so perhaps the quantum adversary model should be considered in the highly over-engineered world of symmetric cryptography. Oct 28 at 14:40
• Good point: much work on classical cryptanalysis is as far from today's reality (as an engineer using crypto like me perceives it) as work on quantum cryptanalysis is!
– fgrieu
Oct 28 at 15:22

COA, CPA, CCA are not defined according to a specific adversary. The adversary could be a PPT, an unbounded adversary (then we obtain information-theoretically security) or a polynomial-time-quantum computer (but it's true, in the literature sometime people precise (not always for good reasons) the adversary is a PPT).

So, COA, CPA, CCA doesn't need to be redefined in a post-quantum world.

The big change in a such world is the fact that, it's no more absurd to consider an adversary which breaks DLog or RSA, then the statement $$\text{There is an adversary which break the security of the system.}\implies \text{There is an adversary which breaks DLog/RSA}$$ is always true (because the right part is always true), and then doesn't has anymore practical interest.

Historically, we have two major cryptology algorithms in Quantum Computing;

1. Shor's algorithm internally uses period finding to factor the RSA modulus and solve the discrete logarithm.

In both cases, all parameters are public, the attacker that uses Cryptographical Quantum Computer only uses the public RSA modulus and public parameters of the Elliptical Curve.

2. Grover's Algorithm is designed to search on unstructured data. If we turn into breaking block ciphers then one applies the known-plaintext attack as in the brute-forcing a block cipher.

A proposal on this subject is made for the NIST quantum proposals, in 2019 by Băetu et.al

Many post-quantum cryptosystems which have been proposed in the National Institute of Standards and Technology (NIST) standardization process follow the same meta-algorithm, but in different algebras or different encoding methods. They usually propose two constructions, one being weaker and the other requiring a random oracle. We focus on the weak version of nine submissions to NIST. Submitters claim no security when the secret key is used several times. In this paper, we analyze how easy it is to run a key recovery under multiple key reuse. We mount a classical key recovery under plaintext checking attacks (i.e., with a plaintext checking oracle saying if a given ciphertext decrypts well to a given plaintext) and a quantum key recovery under chosen ciphertext attacks. In the latter case, we assume quantum access to the decryption oracle.

Further;

• Key Recovery under Plaintext Checking Attack (KR-PCA) : This model makes sense when an adversary can play with a server with a modified ciphertext and check if it still decrypts to the same plaintext as before.