In symmetric key cryptography, an ideal model is a heuristic technique commonly used to validate the security of cryptographic schemes. With the emergence of quantum computation, some traditional cryptographic schemes have become vulnerable to quantum-based attacks. This motivates interest of quantum ideal models. The proposed research focuses on investigating time-space trade-offs and lower bounds in two quantum ideal models: the random permutation model and the ideal cipher model.

In the quantum random permutation model, the adversary gets access to quantum oracles for both the forward and the inverse direction of a permutation. In this model, we focus on the permutation inversion problem. In this problem, the task is to find the pre-image of some challenge value -- without querying the inverse oracle on the challenge. This is a fundamental problem in query complexity, and relevant to cryptography. We prove several theorems connecting the hardness of variations of the inversion problem, and establish a number of time-space trade-offs and 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.

In the quantum ideal cipher model, the adversary gets quantum access to a large family of random permutations indexed by keys. The tweakable block cipher construction LRW is typically studied in this model. For LRW, classical oracle access to the secretly keyed construction is also provided to the adversary. Recently developed techniques can be used to give a lower bound on the query complexity of distinguishing LRW from an ideal tweakable block cipher. Building on this result, we aim to extend our analysis to the related XEX construction, which is widely used in disk encryption. We expect to demonstrate that using longer keys for the underlying block ciphers does not enhance the security of LRW and XEX. On the other hand, in the FX construction, increasing the key length of the underlying block cipher does enhance the classical security. We aim to prove that the same result holds in the quantum ideal cipher model.