01459nas a2200145 4500008004100000245005100041210004300092260001400135520105500149100001901204700001401223700002301237700001601260856003701276 2023 eng d00aOn the Two-sided Permutation Inversion Problem0 aTwosided Permutation Inversion Problem c6/23/20233 a

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.

1 aAlagic, Gorjan1 aBai, Chen1 aPoremba, Alexander1 aShi, Kaiyan uhttps://arxiv.org/abs/2306.1372901696nas a2200145 4500008004100000245005300041210005100094260001500145520127900160100001901439700001401458700001901472700002201491856003701513 2022 eng d00aPost-Quantum Security of the Even-Mansour Cipher0 aPostQuantum Security of the EvenMansour Cipher c12/14/20213 a

The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation E from a public random permutation~P:{0,1}n→{0,1}n. It is secure against classical attacks, with optimal attacks requiring qE queries to E and qP queries to P such that qE⋅qP≈2n. If the attacker is given \emph{quantum} access to both E and P, however, the cipher is completely insecure, with attacks using qE,qP=O(n) queries known. In any plausible real-world setting, however, a quantum attacker would have only \emph{classical} access to the keyed permutation~E implemented by honest parties, even while retaining quantum access to~P. Attacks in this setting with qE⋅q2P≈2n are known, showing that security degrades as compared to the purely classical case, but leaving open the question as to whether the Even-Mansour cipher can still be proven secure in this natural, "post-quantum" setting. We resolve this question, showing that any attack in that setting requires qE⋅q2P+qP⋅q2E≈2n. Our results apply to both the two-key and single-key variants of Even-Mansour. Along the way, we establish several generalizations of results from prior work on quantum-query lower bounds that may be of independent interest. 

1 aAlagic, Gorjan1 aBai, Chen1 aKatz, Jonathan1 aMajenz, Christian uhttps://arxiv.org/abs/2112.0753001152nas a2200157 4500008004100000245007900041210006900120260001400189520065900203100001900862700001400881700001900895700002200914700002000936856003800956 2022 eng d00aPost-Quantum Security of the (Tweakable) FX Construction, and Applications0 aPostQuantum Security of the Tweakable FX Construction and Applic c8/29/20223 a

The FX construction provides a way to increase the effective key length of a block cipher E. We prove security of a tweakable version of the FX construction in the post-quantum setting, i.e., against a quantum attacker given only classical access to the secretly keyed construction while retaining quantum access to E, a setting that seems to be the most relevant one for real-world applications. We then use our results to prove post-quantum security—in the same model—of the (plain) FX construction, Elephant (a finalist of NIST's lightweight cryptography standardization effort), and Chaskey (an ISO-standardized lightweight MAC

1 aAlagic, Gorjan1 aBai, Chen1 aKatz, Jonathan1 aMajenz, Christian1 aStruck, Patrick uhttps://eprint.iacr.org/2022/1097