International Association for Cryptologic Research

International Association
for Cryptologic Research


On the Two-sided Permutation Inversion Problem

Gorjan Alagic , QuICS, University of Maryland, National Institute of Standards and Technology
Chen Bai , QuICS, University of Maryland, Dept. of Electrical and Computer Engineering, University of Maryland
Alexander Poremba , Computing and Mathematical Sciences, California Institute of Technology, CSAIL and Department of Mathematics, Massachusetts Institute of Technology
Kaiyan Shi , QuICS, University of Maryland, Dept. of Computer Science, University of Maryland
DOI: 10.62056/a0qj89n4e
Search ePrint
Search Google

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.

  title={On the Two-sided Permutation Inversion Problem},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 1},
  author={Gorjan Alagic and Chen Bai and Alexander Poremba and Kaiyan Shi},