Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications

DOI10.1145/2554797.2554815zbMath1364.94595OpenAlexW2053327080MaRDI QIDQ2988877

Erez Druk, Yuval Ishai

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.2554815

zbMATH Keywords

cryptographyerror-correcting codesGilbert-Varshamov boundlinear-time encodable codes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear codes (general theory) (94B05) Cryptography (94A60) Decoding (94B35)

Related Items (10)

Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ Binary AMD Circuits from Secure Multiparty Computation ⋮ Recent Advances in Non-perfect Secret Sharing Schemes ⋮ Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier ⋮ Actively secure arithmetic computation and VOLE with constant computational overhead ⋮ Brakedown: linear-time and field-agnostic SNARKs for R1CS ⋮ Orion: zero knowledge proof with linear prover time ⋮ How to recover a secret with \(O(n)\) additions ⋮ Rate-1, Linear Time and Additively Homomorphic UC Commitments ⋮ Bounded Indistinguishability and the Complexity of Recovering Secrets

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: Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications