@article {2626, title = {On Quantum Chosen-Ciphertext Attacks and Learning with Errors}, journal = {Cryptography}, volume = {4}, year = {2020}, month = {3/21/2020}, pages = {10}, abstract = {

Large-scale quantum computing poses a major threat to classical public-key cryptography. Recently, strong \“quantum access\” 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\−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 \“just as secure\” quantumly as it is classically. The algorithm at the core of our attack is a new variant of the well-known Bernstein\–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.

}, doi = {https://doi.org/10.3390/cryptography4010010}, author = {Gorjan Alagic and Stacey Jeffery and Maris Ozols and Alexander Poremba} } @article {2219, title = {On non-adaptive quantum chosen-ciphertext attacks and Learning with Errors}, journal = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2019, June 3-5, 2019, University of Maryland, College Park, Maryland, USA}, year = {2019}, pages = {1:1-1:23 }, abstract = {

Large-scale quantum computing is a significant threat to classical public-key cryptography. In strong \"quantum access\" security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally 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. Using a bound on quantum random-access codes, we show that the standard PRF- and PRP-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives. We then revisit standard IND-CPA-secure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key uses a linear number of decryption queries, and this is optimal. The algorithm at the core of our attack is a (large-modulus version of) the well-known Bernstein-Vazirani algorithm. 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.\ 

}, doi = {https://doi.org/10.4230/LIPIcs.TQC.2019.1}, url = {https://arxiv.org/abs/1808.09655}, author = {Gorjan Alagic and Stacey Jeffery and Maris Ozols and Alexander Poremba} } @article {1989, title = {Quantum Algorithms for Graph Connectivity and Formula Evaluation}, year = {2017}, month = {2017/04/03}, abstract = {

We give a new upper bound on the quantum query complexity of deciding st-connectivity on certain classes of planar graphs, and show the bound is sometimes exponentially better than previous results. We then show Boolean formula evaluation reduces to deciding connectivity on just such a class of graphs. Applying the algorithm for st-connectivity to Boolean formula evaluation problems, we match the O( \√ N) bound on the quantum query complexity of evaluating formulas on N variables, give a quadratic speed-up over the classical query complexity of a certain class of promise Boolean formulas, and show this approach can yield superpolynomial quantum/classical separations. These results indicate that this st-connectivity-based approach may be the \“right\” way of looking at quantum algorithms for formula evaluation.

}, url = {https://arxiv.org/abs/1704.00765}, author = {Stacey Jeffery and Shelby Kimmel} } @proceedings {1388, title = {Partial-indistinguishability obfuscation using braids}, year = {2014}, month = {2014/08/21}, abstract = {

An obfuscator is an algorithm that translates circuits into functionally-equivalent similarly-sized circuits that are hard to understand. Efficient obfuscators would have many applications in cryptography. Until recently, theoretical progress has mainly been limited to no-go results. Recent works have proposed the first efficient obfuscation algorithms for classical logic circuits, based on a notion of indistinguishability against polynomial-time adversaries. In this work, we propose a new notion of obfuscation, which we call partial-indistinguishability. This notion is based on computationally universal groups with efficiently computable normal forms, and appears to be incomparable with existing definitions. We describe universal gate sets for both classical and quantum computation, in which our definition of obfuscation can be met by polynomial-time algorithms. We also discuss some potential applications to testing quantum computers. We stress that the cryptographic security of these obfuscators, especially when composed with translation from other gate sets, remains an open question.

}, url = {http://arxiv.org/abs/1212.6358}, author = {Gorjan Alagic and Stacey Jeffery and Stephen P. Jordan} } @article {1258, title = {A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates}, year = {2013}, month = {2013/02/28}, abstract = { We present an extension to the quantum walk search framework that facilitates quantum walks with nested updates. We apply it to give a quantum walk algorithm for 3-Distinctness with query complexity ~O(n^{5/7}), matching the best known upper bound (obtained via learning graphs) up to log factors. Furthermore, our algorithm has time complexity ~O(n^{5/7}), improving the previous ~O(n^{3/4}). }, url = {http://arxiv.org/abs/1302.7316v1}, author = {Andrew M. Childs and Stacey Jeffery and Robin Kothari and Frederic Magniez} }