Paper 2023/985

On the Two-sided Permutation Inversion Problem

Gorjan Alagic, University of Maryland, College Park
Chen Bai, University of Maryland, College Park
Alexander Poremba, California Institute of Technology
Kaiyan Shi, University of Maryland, College Park

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.

Available format(s)
Publication info
A minor revision of an IACR publication in CIC 2024
permutation inversionquantum advice
Contact author(s)
galagic @ gmail com
cbai1 @ terpmail umd edu
aporemba @ caltech edu
kshi12 @ umd edu
2024-04-22: revised
2023-06-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gorjan Alagic and Chen Bai and Alexander Poremba and Kaiyan Shi},
      title = {On the Two-sided Permutation Inversion Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2023/985},
      year = {2023},
      doi = {10.62056/a0qj89n4e},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.