Related papers: On the Two-sided Permutation Inversion Problem

On the Two-sided Permutation Inversion Problem

URL: http://arxiv.org/abs/2306.13729v2
Date: Mon, 22 Apr 2024 02:00:33 GMT
Title: On the Two-sided Permutation Inversion Problem
Authors: Gorjan Alagic, Chen Bai, Alexander Poremba, Kaiyan Shi,
Abstract summary: We study the setting in which the oracle allows for quantum queries to both the forward and inverse direction of the permutation. We prove several theorems connecting the hardness of the resulting variations of the inversion problem. Our results indicate that, perhaps surprisingly, the inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse.
Score: 45.69327512339002
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This is a fundamental problem in query complexity, and 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 two options for the inversion algorithm: whether it can get quantum advice about the permutation, 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 inversion problem, and establish a number of lower bounds. Our results indicate that, perhaps surprisingly, the inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse, provided it cannot query the challenge itself.

Related papers

Permutation Superposition Oracles for Quantum Query Lower Bounds [14.957648729581502]
We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs. We show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model.
arXiv Detail & Related papers (2024-07-12T19:27:13Z)
Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
Sponge hashing is a widely used class of cryptographic hash algorithms. Intrepid permutations have so far remained a fundamental open problem. We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
arXiv Detail & Related papers (2024-03-07T18:46:58Z)
One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
arXiv Detail & Related papers (2023-01-05T11:05:22Z)
Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z)
Penalty Weights in QUBO Formulations: Permutation Problems [0.0]
optimisation algorithms designed to work on quantum computers have been of research interest in recent years. Many of these solver can only optimise problems that are in binary and quadratic form. There are many optimisation problems that are naturally represented as permutations. We propose new static methods of calculating penalty weights which lead to more promising results.
arXiv Detail & Related papers (2022-06-20T22:00:38Z)
Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z)
Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
Zhandry studied interactions between quantum query algorithms and the quantum oracle corresponding to random functions. We introduce a similar interpretation for the case when the oracle corresponds to random permutations instead of random functions. Because both random functions and random permutations are highly significant in security proofs, we hope that the present framework will find applications in quantum cryptography.
arXiv Detail & Related papers (2021-03-16T11:05:48Z)
Multiview Sensing With Unknown Permutations: An Optimal Transport Approach [42.62524143925126]
We take a fresh look at the problem of recovering a signal subject to unknown permutations through the lens of optimal transport. We exploit this by introducing a regularization function that promotes the more likely permutations in the solution. We show that, even though the general problem is not convex, an appropriate relaxation of the resulting regularized problem allows us to exploit the well-developed machinery of OT and develop a tractable algorithm.
arXiv Detail & Related papers (2021-03-12T18:48:18Z)
Quantum Permutation Synchronization [88.4588059792167]
We present QuantumSync, the quantum algorithm for solving a quantum vision problem in the context of computer vision. We show how to insert permutation constraints into a QUBO problem and to solve the constrained QUBO problem on the current generation of the abatic quantum DWave computer.
arXiv Detail & Related papers (2021-01-19T17:51:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.