Candidate weak pseudorandom functions in AC 0 ○ MOD 2

DOI10.1145/2554797.2554821zbMath1364.94519OpenAlexW1988413780MaRDI QIDQ2988885

Andrej Bogdanov, Siyao Guo, Adi Akavia, Alon Rosen, Akshay Kamath

Publication date: 19 May 2017

Published in: Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

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

zbMATH Keywords

learning parity with noiseparallel cryptographyweak pseudorandom functions\(\mathrm{AC}^0\circ\mathrm{MOD}_2\)inapproximability of \(\mathrm{AC}^0\)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Related Items (18)

Expander-based cryptography meets natural proofs ⋮ Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes ⋮ Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ MPC-friendly symmetric cryptography from alternating moduli: candidates, protocols, and applications ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Approximate-Deterministic Public Key Encryption from Hard Learning Problems ⋮ Adventures in crypto dark matter: attacks, fixes and analysis for weak pseudorandom functions ⋮ (Pseudo) random quantum states with binary phase ⋮ On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator ⋮ Correlated pseudorandomness from expand-accumulate codes ⋮ Expand-convolute codes for pseudorandom correlation generators from LPN ⋮ Unnamed Item ⋮ Two-Round Man-in-the-Middle Security from LPN ⋮ Unconditionally secure computation against low-complexity leakage ⋮ Correction to: ``Unconditionally secure computation against low-complexity leakage ⋮ Adventures in crypto dark matter: attacks and fixes for weak pseudorandom functions ⋮ Pseudorandom Functions: Three Decades Later

Cites Work

• Unnamed Item
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• (Leveled) fully homomorphic encryption without bootstrapping
• Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
• Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Trapdoors for hard lattices and new cryptographic constructions
• Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness
• Evaluating Branching Programs on Encrypted Data
• Bounds for Width Two Branching Programs
• Fully homomorphic encryption using ideal lattices
• Public-key cryptosystems from the worst-case shortest vector problem
• Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
• New lattice-based cryptographic constructions
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: Candidate weak pseudorandom functions in AC ⁰ ○ MOD ₂