This content will become publicly available on April 9, 2025
In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This fundamental problem in query complexity appears in many contexts, particularly cryptography. In this work, we examine the setting in which the oracle allows for quantum queries to both the forward and the inverse direction of the permutation—except that the challenge value cannot be submitted to the latter. Within that setting, we consider three options for the inversion algorithm: whether it can get quantum advice about the permutation, whether the query algorithm can restrict the distribution with which the challenge input is sampled, and whether it must produce the entire preimage (search) or only the first bit (decision). We prove several theorems connecting the hardness of the resulting variations of the permutation inversion problem and establish lower bounds for them. Our results show that, perhaps surprisingly, the permutation inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse—provided it cannot query the challenge itself.
more » « less Award ID(s):
 2154705
 NSFPAR ID:
 10510031
 Publisher / Repository:
 IACR
 Date Published:
 Journal Name:
 IACR Communications in Cryptology
 Volume:
 1
 Issue:
 1
 ISSN:
 30065496
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Given a loop or more generally 1cycle r r of size L on a closed twodimensional manifold or surface, represented by a triangulated mesh, a question in computational topology asks whether or not it is homologous to zero. We frame and tackle this problem in the quantum setting. Given an oracle that one can use to query the inclusion of edges on a closed curve, we design a quantum algorithm for such a homology detection with a constant running time, with respect to the size or the number of edges on the loop r r , requiring only a single usage of oracle. In contrast, classical algorithm requires \Omega(L) Ω ( L ) oracle usage, followed by a linear time processing and can be improved to logarithmic by using a parallel algorithm. Our quantum algorithm can be extended to check whether two closed loops belong to the same homology class. Furthermore, it can be applied to a specific problem in the homotopy detection, namely, checking whether two curves are not homotopically equivalent on a closed twodimensional manifold.more » « less

Formulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a longstanding challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of “predicting an unqueried value” when the adversary can query in quantum superposition. We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use “partially blinded” oracle access to predict values in the blinded region. We support the proposal with a number of technical results. We begin by establishing that the notion coincides with EUFCMA in the classical setting and go on to demonstrate that the notion is satisfied by a number of simple guiding examples, such as random functions and quantumquerysecure pseudorandom functions. We then show the suitability of blind unforgeability for supporting canonical constructions and reductions. We prove that the “hashandMAC” paradigm and the Lamport onetime digital signature scheme are indeed unforgeable according to the definition. To support our analysis, we additionally define and study a new variety of quantumsecure hash functions called Bernoullipreserving. Finally, we demonstrate that blind unforgeability is strictly stronger than a previous definition of Boneh and Zhandry [EUROCRYPT ’13, CRYPTO ’13] and resolve an open problem concerning this previous definition by constructing an explicit function family which is forgeable yet satisfies the definition.more » « less

Largescale quantum computing is a significant threat to classical publickey cryptography. In strong "quantum access" security models, numerous symmetrickey 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 nonadaptive (i.e., prechallenge) 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 randomaccess codes, we show that the standard PRF and PRPbased encryption schemes are QCCA1secure when instantiated with quantumsecure primitives. We then revisit standard INDCPAsecure 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 (largemodulus version of) the wellknown BernsteinVazirani algorithm. We emphasize that our results should *not* be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., postquantum chosenplaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosenciphertext attacks (e.g., as a result of deployment in an inappropriate realworld setting) then quantum attacks are even more devastating than classical ones.more » « less

Lysyanskaya, Anna ; Handschuh, Helena (Ed.)We study the blackbox function inversion problem, which is the problem of finding x[N] such that f(x)=y, given as input some challenge point y in the image of a function f:[N][N], using T oracle queries to f and preprocessed advice 01S depending on f. We prove a number of new results about this problem, as follows. 1. We show an algorithm that works for any T and S satisfying TS2maxST=(N3) . In the important setting when ST, this improves on the celebrated algorithm of Fiat and Naor [STOC, 1991], which requires TS3N3. E.g., Fiat and Naor's algorithm is only nontrivial for SN23 , while our algorithm gives a nontrivial tradeoff for any SN12 . (Our algorithm and analysis are quite simple. As a consequence of this, we also give a selfcontained and simple proof of Fiat and Naor's original result, with certain optimizations left out for simplicity.) 2. We show a nonadaptive algorithm (i.e., an algorithm whose ith query xi is chosen based entirely on and y, and not on the f(x1)f(xi−1)) that works for any T and S satisfying S=(Nlog(NT)) giving the first nontrivial nonadaptive algorithm for this problem. E.g., setting T=Npolylog(N) gives S=(NloglogN). This answers a question due to CorriganGibbs and Kogan [TCC, 2019], who asked whether it was possible for a nonadaptive algorithm to work with parameters T and S satisfying T+SlogNo(N) . We also observe that our nonadaptive algorithm is what we call a guessandcheck algorithm, that is, it is nonadaptive and its final output is always one of the oracle queries x1xT. For guessandcheck algorithms, we prove a matching lower bound, therefore completely characterizing the achievable parameters (ST) for this natural class of algorithms. (CorriganGibbs and Kogan showed that any such lower bound for arbitrary nonadaptive algorithms would imply new circuit lower bounds.) 3. We show equivalence between function inversion and a natural decision version of the problem in both the worst case and the average case, and similarly for functions f:[N][M] with different ranges. All of the above results are most naturally described in a model with shared randomness (i.e., random coins shared between the preprocessing algorithm and the online algorithm). However, as an additional contribution, we show (using a technique from communication complexity due to Newman [IPL, 1991]) how to generically convert any algorithm that uses shared randomness into one that does not.more » « less

Fawzi, Omar ; Walter, Michael (Ed.)The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string x ∈ {0, 1}ⁿ given possibly nonstandard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of x. We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of Ω(n/log² n) for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greaterthan and equality functions.more » « less