Algebraic attacks against random local functions and their countermeasures
From MaRDI portal
Publication:5361904
DOI10.1145/2897518.2897554zbMath1377.94027OpenAlexW2415206359MaRDI QIDQ5361904
Shachar Lovett, Benny Applebaum
Publication date: 29 September 2017
Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2897518.2897554
Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
On the fast algebraic immunity of threshold functions ⋮ On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ On the algebraic immunity of direct sum constructions ⋮ Improved filter permutators for efficient FHE: better instances and implementations ⋮ Actively secure arithmetic computation and VOLE with constant computational overhead ⋮ On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator ⋮ Worst-case subexponential attacks on PRGs of constant degree or constant locality ⋮ Oblivious transfer with constant computational overhead ⋮ Non-interactive zero-knowledge from non-interactive batch arguments ⋮ Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN ⋮ Indistinguishability obfuscation ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Projective Arithmetic Functional Encryption and Indistinguishability Obfuscation from Degree-5 Multilinear Maps ⋮ Non-interactive zero-knowledge in pairing-free groups from weaker assumptions ⋮ Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification ⋮ Pseudorandom Functions: Three Decades Later
