



01459nas a2200145   4500008004100000245005100041210004300092260001400135520105500149100001901204700001401223700002301237700001601260856003701276       2023                        eng d00aOn the Two-sided Permutation Inversion Problem0 aTwosided Permutation Inversion Problem  c6/23/20233 a<p>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.</p>1 aAlagic, Gorjan1 aBai, Chen1 aPoremba, Alexander1 aShi, Kaiyan  uhttps://arxiv.org/abs/2306.13729