One way functions and pseudorandom generators
From MaRDI portal
Publication:1100894
DOI10.1007/BF02579323zbMath0641.68061MaRDI QIDQ1100894
Publication date: 1987
Published in: Combinatorica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Random number generation in numerical analysis (65C10)
Related Items
One-way permutations and self-witnessing languages ⋮ A New Pseudorandom Generator from Collision-Resistant Hash Functions ⋮ On universal learning algorithms ⋮ Magnifying computing gaps. Establishing encrypted communication over unidirectional channels ⋮ Quantum algorithms for the \(k\)-XOR problem ⋮ MPC-friendly symmetric cryptography from alternating moduli: candidates, protocols, and applications ⋮ Time hierarchies for cryptographic function inversion with advice ⋮ One-way functions and circuit complexity ⋮ Simultaneous Secrecy and Reliability Amplification for a General Channel Model ⋮ Efficient Pseudorandom Functions via On-the-Fly Adaptation ⋮ Proofs of proximity for context-free languages and read-once branching programs ⋮ Sparse pseudorandom distributions ⋮ Pseudorandom sources for BPP ⋮ One-way permutations in NC 0 ⋮ Mathematical problems in cryptology ⋮ On-line/off-line digital signatures ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ Proofs of Work from worst-case assumptions ⋮ A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module ⋮ From FE combiners to secure MPC and back ⋮ The function-inversion problem: barriers and opportunities ⋮ Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions ⋮ ON THE CIRCUIT-SIZE OF INVERSES ⋮ Hardness-preserving reductions via cuckoo hashing ⋮ A tight computational indistinguishability bound for product distributions ⋮ Universal amplification of KDM security: from 1-key circular to multi-key KDM ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Query complexity in errorless hardness amplification ⋮ Feebly secure cryptographic primitives ⋮ Circuit complexity of linear functions: gate elimination and feeble security ⋮ The complexity of inverting explicit Goldreich's function by DPLL algorithms ⋮ Simple and more efficient PRFs with tight security from LWE and matrix-DDH ⋮ On the theory of average case complexity ⋮ Almost everywhere high nonuniform complexity ⋮ On the Security of the Winternitz One-Time Signature Scheme ⋮ Non-interactive proofs of proximity ⋮ The communication complexity of addition ⋮ On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography ⋮ Practical construction and analysis of pseudo-randomness primitives ⋮ On the complexity of compressing obfuscation ⋮ Easiness assumptions and hardness tests: Trading time for zero error ⋮ Basing Weak Public-Key Cryptography on Strong One-Way Functions ⋮ Degradation and Amplification of Computational Hardness ⋮ Simulation theorems via pseudo-random properties ⋮ The complexity of ODDnA ⋮ Traceable ring signatures: general framework and post-quantum security ⋮ Pseudorandom generators from regular one-way functions: new constructions with improved parameters ⋮ On complete one-way functions ⋮ Symmetry of information and one-way functions ⋮ Algebraic cryptography: new constructions and their security against provable break ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ Query Complexity in Errorless Hardness Amplification ⋮ Three XOR-Lemmas — An Exposition ⋮ On Yao’s XOR-Lemma ⋮ On Security Preserving Reductions – Revised Terminology ⋮ Prediction-preserving reducibility ⋮ A Feebly Secure Trapdoor Function ⋮ Advice Lower Bounds for the Dense Model Theorem ⋮ Universal Constructions and Robust Combiners for Indistinguishability Obfuscation and Witness Encryption ⋮ Some consequences of the existnce of pseudorandom generators ⋮ Shared generation of pseudo-random functions ⋮ Quantum lower bounds for the Goldreich-Levin problem ⋮ Semigroups and one-way functions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Pseudorandom Functions: Three Decades Later ⋮ Randomness vs time: Derandomization under a uniform assumption ⋮ \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
Cites Work
This page was built for publication: One way functions and pseudorandom generators
