



02525nas a2200169   4500008004100000245006600041210006200107260001400169300000700183490000600190520198300196100001902179700002002198700001702218700002302235856009702258       2020                        eng d00aOn Quantum Chosen-Ciphertext Attacks and Learning with Errors0 aQuantum ChosenCiphertext Attacks and Learning with Errors  c3/21/2020  a100 v43 a<p>Large-scale quantum computing poses a major threat to classical public-key cryptography. Recently, strong &ldquo;quantum access&rdquo; security models have shown that numerous symmetric-key cryptosystems are also vulnerable. In this paper, we consider classical encryption in a model that grants the adversary quantum oracle access to encryption and decryption, but where we restrict the latter to non-adaptive (i.e., pre-challenge) queries only. We formalize this model using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. We show that the standard pseudorandom function ( PRF )-based encryption schemes are QCCA1 -secure when instantiated with quantum-secure primitives. Our security proofs use a strong bound on quantum random-access codes with shared randomness. Revisiting plain IND&minus;CPA -secure Learning with Errors ( LWE ) encryption, we show that leaking only a single quantum decryption query (and no other leakage or queries of any kind) allows the adversary to recover the full secret key with constant success probability. Information-theoretically, full recovery of the key in the classical setting requires at least a linear number of decryption queries. Our results thus challenge the notion that LWE is unconditionally &ldquo;just as secure&rdquo; quantumly as it is classically. The algorithm at the core of our attack is a new variant of the well-known Bernstein&ndash;Vazirani algorithm. Finally, we emphasize that our results should not be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones.</p>1 aAlagic, Gorjan1 aJeffery, Stacey1 aOzols, Maris1 aPoremba, Alexander  uhttps://www.quics.umd.edu/publications/quantum-chosen-ciphertext-attacks-and-learning-errors