Worst-case hardness for LPN and cryptographic hashing via code smoothing

DOI10.1007/978-3-030-17659-4_21MaRDI QIDQ2292709zbMATH OpenOpenAlexFDO

Authors Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs

Publication date 4 February 2020

Full work available at URL https://hdl.handle.net/1721.1/137866.2

Mathematics Subject Classification ID

Cryptography (94A60) Decoding (94B35)

Recommendations

• Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN
• Collision resistant hashing from sub-exponential learning parity with noise
• LPN decoded
• Solving LPN using covering codes
• Cryptography from learning parity with noise

Cited in

(26)

• Anonymous IBE, leakage resilience and circular security from new assumptions
• Breaking the circuit size barrier for secure computation under quasi-polynomial LPN
• Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN
• On the complexity of collision resistant hash functions: new and old black-box separations
• Collision resistant hashing from sub-exponential learning parity with noise
• New constructions of collapsing hashes
• Statistically sender-private OT from LPN and derandomization
• Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN
• An iterative correction method for practically LPN solving
• Cryptography from planted graphs: security with logarithmic-size messages
• Combinatorially homomorphic encryption
• Pseudorandomness of decoding, revisited: adapting OHCP to code-based cryptography
• The Boneh-Katz transformation, revisited: pseudorandom/obliviously-samplable PKE from lattices and codes and its application
• The hardness of LPN over any integer ring and field for PCG applications
• Lossy cryptography from code-based assumptions
• Non-interactive zero-knowledge from LPN and MQ
• The quantum decoding problem
• Somewhat homomorphic encryption from linear homomorphism and sparse LPN
• Lossy cryptography from code-based assumptions dense-sparse LPN: a new subexponentially hard LPN variant in SZK
• Limitations of the decoding-to-LPN reduction via code smoothing
• Worst and average case hardness of decoding via smoothing bounds
• Slightly sublinear trapdoor hash functions and PIR from low-noise LPN
• A minrank-based encryption scheme à la Alekhnovich-Regev
• Attacks on Goldreich's pseudorandom generators by grouping and solving
• The syndrome weight distribution in quasi-cyclic codes, applications to BIKE and HQC
• Learning with errors with output dependencies: LWE, LWR, and physical learning problems under the same umbrella

This page was built for publication: Worst-case hardness for LPN and cryptographic hashing via code smoothing

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