Crooked indifferentiability of the Feistel Construction

• URL: http://arxiv.org/abs/2404.09450v1
• Date: Mon, 15 Apr 2024 04:29:24 GMT
• Title: Crooked indifferentiability of the Feistel Construction
• Authors: Alexander Russell, Qiang Tang, Jiadong Zhu,
• Abstract summary: The Feistel construction is a fundamental technique for building pseudorandom permutations and block ciphers. This paper shows that a simple adaptation of the construction is resistant, even to algorithm substitution attacks.
• Score: 53.572703605492904
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Feistel construction is a fundamental technique for building pseudorandom permutations and block ciphers. This paper shows that a simple adaptation of the construction is resistant, even to algorithm substitution attacks -- that is, adversarial subversion -- of the component round functions. Specifically, we establish that a Feistel-based construction with more than $2000n/\log(1/\epsilon)$ rounds can transform a subverted random function -- which disagrees with the original one at a small fraction (denoted by $\epsilon$) of inputs -- into an object that is \emph{crooked-indifferentiable} from a random permutation, even if the adversary is aware of all the randomness used in the transformation. We also provide a lower bound showing that the construction cannot use fewer than $2n/\log(1/\epsilon)$ rounds to achieve crooked-indifferentiable security.

Related papers

• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• 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)
• Simple constructions of linear-depth t-designs and pseudorandom unitaries [40.72668922727092]
  Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. Two different notions of derandomisation have emerged: $t-designs are random unitaries that reproduce the first $t moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random.
  arXiv  Detail & Related papers  (2024-04-19T06:13:02Z)
• Correcting Subverted Random Oracles [55.4766447972367]
  We prove that a simple construction can transform a "subverted" random oracle which disagrees with the original one at a small fraction of inputs into an object that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings to use random oracles as a trusted black box.
  arXiv  Detail & Related papers  (2024-04-15T04:01:50Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms. Intrepid permutations have so far remained a fundamental open problem. We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• 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)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• A Closer Look at Robustness to L-infinity and Spatial Perturbations and their Composition [14.508683884152347]
  In adversarial machine learning, the popular $ell_infty$ threat model has been the focus of much previous work. We study how state-of-the-art $ell_infty$ defenses can be adapted to this novel threat model. We find that our newly proposed TRADES$_textAll$ strategy performs the strongest of all.
  arXiv  Detail & Related papers  (2022-10-05T21:57:14Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
  arXiv  Detail & Related papers  (2021-10-25T02:53:24Z)

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.