Post-Quantum Security of the Even-Mansour Cipher

• URL: http://arxiv.org/abs/2112.07530v1
• Date: Tue, 14 Dec 2021 16:43:34 GMT
• Title: Post-Quantum Security of the Even-Mansour Cipher
• Authors: Gorjan Alagic and Chen Bai and Jonathan Katz and Christian Majenz
• Abstract summary: Even-Mansour cipher is secure against classical attacks. Even-Mansour can still be proven secure in natural, "post-quantum" setting.
• Score: 14.141778162933013
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation $E$ from a public random permutation~$P:\{0,1\}^n \rightarrow \{0,1\}^n$. It is secure against classical attacks, with optimal attacks requiring $q_E$ queries to $E$ and $q_P$ queries to $P$ such that $q_E \cdot q_P \approx 2^n$. If the attacker is given \emph{quantum} access to both $E$ and $P$, however, the cipher is completely insecure, with attacks using $q_E, q_P = 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 $q_E \cdot q_P^2 \approx 2^n$ 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 $q_E \cdot q^2_P + q_P \cdot q_E^2 \approx 2^n$. 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.

Related papers

• Towards Unconditional Uncloneable Encryption [1.18749525824656]
  Uncloneable encryption is a cryptographic primitive which encrypts a classical message into a quantum ciphertext. We show that the adversary's success probability in the related security game converges quadratically as $1/2+1/ (2sqrtK)$, where $K$ represents the number of keys and $1/2$ is trivially achievable.
  arXiv  Detail & Related papers  (2024-10-30T14:40:06Z)
• Pseudorandom Permutations from Random Reversible Circuits [1.9567015559455132]
  We show that a random circuit of depth $n cdot tildeO(k2)$, with each layer consisting of $approx n/3$ random gates in a fixed nearest-neighbor architecture, yields almost $k$-wise independent permutations. We also show that the Luby-Rack-off construction of pseudorandom permutations from pseudorandom functions can be implemented with reversible circuits.
  arXiv  Detail & Related papers  (2024-04-23T00:50:57Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• Pseudorandom Isometries [6.0709446838151715]
  We introduce a new notion called $cal Q$-secure pseudorandom isometries (PRI) PRIs are efficient quantum circuits that map an $n$-qubit state to an $(n+m)$-qubit state. We demonstrate many cryptographic applications of PRIs, including, length extension theorems for quantum pseudorandomness notions.
  arXiv  Detail & Related papers  (2023-11-06T06:27:14Z)
• Quantum forgery attacks against OTR structures based on Simon's algorithm [3.845166861382186]
  A quantum forgery attack on OTR structure using Simon's algorithm is proposed. A variant of OTR structure (Pr/ost-OTR-Even-Mansour structure) is proposed. It is easy to generate the correct tag of any given message if attacker is allowed to change a single block in it.
  arXiv  Detail & Related papers  (2023-10-01T15:16:43Z)
• Quantum security of subset cover problems [1.4072904523937533]
  The security of many hash-based signature schemes relies on the subset cover problem or a variant of this problem. We prove that any quantum algorithm needs to make $Omegaleft(k+1)-frac2k2k+1-1cdot Nfrac2k-12k+1-1right)$ queries to the underlying hash functions. We also analyze the security of the general $(r,k)$-subset cover problem, which is the underlying problem.
  arXiv  Detail & Related papers  (2022-10-27T12:58:27Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.