Fine-grained complexity in a world without cryptography
From MaRDI portal
Cites work
- 3SUM, 3XOR, triangles
- \(k\)-SUM in the sparse regime: complexity and applications
- A cryptanalytic time-memory trade-off
- A public key cryptosystem and a signature scheme based on discrete logarithms
- A taxonomy of pairing-friendly elliptic curves
- Algorithmic Cryptanalysis
- An algorithmic framework for the generalized birthday problem
- Average-case fine-grained hardness
- Complexity of a determinate algorithm for the discrete logarithm
- Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds
- Conditional lower bounds for space/time tradeoffs
- Counting t-cliques: worst-case to average-case reductions and direct interactive proof systems
- Cryptography and Coding
- Data structures meet cryptography: 3SUM with preprocessing
- Exact weight subgraphs and the k-sum conjecture
- Fine-grained complexity in a world without cryptography
- Fine-grained cryptanalysis: tight conditional bounds for dense \(k\)-SUM and \(k\)-XOR
- Fine-Grained Cryptography
- Fine-grained non-interactive key exchange, revisited
- Fine-grained non-interactive key-exchange: constructions and lower bounds
- Foundations of Cryptography
- Hiding cliques for cryptographic security
- Higher lower bounds from the 3SUM conjecture
- scientific article; zbMATH DE number 4191111 (Why is no real title available?)
- scientific article; zbMATH DE number 1302835 (Why is no real title available?)
- scientific article; zbMATH DE number 7646025 (Why is no real title available?)
- scientific article; zbMATH DE number 7768374 (Why is no real title available?)
- Improved Generic Algorithms for Hard Knapsacks
- Improved quantum algorithms for the k-XOR problem
- Introduction to Modern Cryptography
- Low-memory attacks against two-round Even-Mansour using the 3-XOR problem
- New directions in cryptography
- New techniques for proving fine-grained average-case hardness
- Non-uniform cracks in the concrete: the power of free precomputation
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On a class of \(O(n^ 2)\) problems in computational geometry
- On building fine-grained one-way functions from strong average-case hardness
- On one-way functions and Kolmogorov complexity
- On some fine-grained questions in algorithms and complexity
- Polynomial formulations as a barrier for reduction-based hardness proofs
- Popular conjectures imply strong lower bounds for dynamic problems
- Proofs of Work from worst-case assumptions
- Public-Key Cryptographic Primitives Provably as Secure as Subset Sum
- Public-key cryptography from different assumptions
- Public-key cryptography in the fine-grained setting
- Refinements of the k-tree Algorithm for the Generalized Birthday Problem
- Rigorous Time/Space Trade-offs for Inverting Functions
- Space-efficient randomized algorithms for k-sum
- Subquadratic algorithms for 3SUM
- T5: Hashing five inputs with three compression calls
- The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
- The Discrete Logarithm problem with preprocessing
- The distinction between fixed and random generators in group-based assumptions
- The extended \(k\)-tree algorithm
- The state of elliptic curve cryptography
- Towards permissionless consensus in the standard model via fine-grained complexity
Cited in
(2)
This page was built for publication: Fine-grained complexity in a world without cryptography
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6891185)
