Public-key cryptography from different assumptions

DOI10.1145/1806689.1806715zbMath1293.94052OpenAlexW1972913305MaRDI QIDQ2875143

Boaz Barak, Avi Wigderson, Benny Applebaum

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806715

zbMATH Keywords

public key cryptographylearning parity with noiseexpander graphsdensest subgraph problemlearning juntas3LIN

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items (32)

Expander-based cryptography meets natural proofs ⋮ On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Cryptography from Learning Parity with Noise ⋮ The Densest $k$-Subhypergraph Problem ⋮ A dichotomy for local small-bias generators ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Cryptographic hardness of random local functions. Survey ⋮ Information-theoretic thresholds from the cavity method ⋮ Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error ⋮ Public-key encryption from homogeneous CLWE ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN ⋮ Indistinguishability obfuscation ⋮ Input locality and hardness amplification ⋮ On the security of Goldreich's one-way function ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Solving the learning parity with noise's open question ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ Structure Versus Hardness Through the Obfuscation Lens ⋮ New Algorithms for Learning in Presence of Errors ⋮ Candidate One-Way Functions Based on Expander Graphs ⋮ Expander-Based Cryptography Meets Natural Proofs ⋮ On the One-Way Function Candidate Proposed by Goldreich ⋮ Fine-Grained Cryptography ⋮ Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of Public-Key Cryptography ⋮ Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning ⋮ Computational barriers in minimax submatrix detection

This page was built for publication: Public-key cryptography from different assumptions