On building fine-grained one-way functions from strong average-case hardness

DOI10.1007/978-3-031-07085-3_20MaRDI QIDQ2170063zbMATH OpenOpenAlexFDO

Authors Chris Brzuska, Geoffroy Couteau

Publication date 30 August 2022

Full work available at URL https://doi.org/10.1007/978-3-031-07085-3_20

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cryptography (94A60)

Recommendations

• Average-case fine-grained hardness
• On basing one-way functions on NP-hardness
• On average-case hardness in \textsf{TFNP} from one-way functions
• An Infinitely-Often One-Way Function Based on an Average-Case Assumption
• An infinitely-often one-way function based on an average-case assumption

Cites work

• A cryptanalytic time-memory trade-off
• Advances in Cryptology – CRYPTO 2004
• Average Case Complete Problems
• Average-case fine-grained hardness
• Basing Weak Public-Key Cryptography on Strong One-Way Functions
• Decoding of Reed Solomon codes beyond the error-correction bound
• Fine-Grained Cryptography
• Fixing cracks in the concrete: random oracles with auxiliary input, revisited
• scientific article; zbMATH DE number 1303133 (Why is no real title available?)
• scientific article; zbMATH DE number 4185033 (Why is no real title available?)
• Merkle Puzzles Are Optimal — An O(n2)-Query Attack on Any Key Exchange from a Random Oracle
• Merkle puzzles in a quantum world
• Notions of black-box reductions, revisited
• NP is as easy as detecting unique solutions
• On basing one-way functions on NP-hardness
• On basing size-verifiable one-way functions on NP-hardness
• On Worst‐Case to Average‐Case Reductions for NP Problems
• One way functions and pseudorandom generators
• Proofs of Work from worst-case assumptions
• Pseudorandom generators without the XOR lemma
• Public-key cryptography in the fine-grained setting
• Random Oracles and Auxiliary Input
• Random oracles and non-uniformity
• Random-Self-Reducibility of Complete Sets
• Secure communications over insecure channels
• Theory of Cryptography
• Theory of Cryptography

Cited in

(14)

• On average-case hardness in \textsf{TFNP} from one-way functions
• Security-preserving hardness-amplification for any regular one-way function
• An Infinitely-Often One-Way Function Based on an Average-Case Assumption
• An infinitely-often one-way function based on an average-case assumption
• Average-case fine-grained hardness
• Fine-grained non-interactive key-exchange: constructions and lower bounds
• Fine-grained secure attribute-based encryption
• On one-way functions and sparse languages
• Fine-grained non-interactive key exchange, revisited
• \(k\)-SUM in the sparse regime: complexity and applications
• On sequential functions and fine-grained cryptography
• On building fine-grained one-way functions from strong average-case hardness
• On Wagner's k-tree algorithm over integers
• Fine-grained complexity in a world without cryptography

This page was built for publication: On building fine-grained one-way functions from strong average-case hardness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2170063)