Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based

DOI10.1007/978-3-642-40041-4_5zbMath1310.94148OpenAlexW56544557MaRDI QIDQ2845661

Amit Sahai, Brent Waters, Craig Gentry

Publication date: 2 September 2013

Published in: Advances in Cryptology – CRYPTO 2013 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-40041-4_5

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items

Constraining and Watermarking PRFs from Milder Assumptions, Almost Tight Security in Lattices with Polynomial Moduli – PRF, IBE, All-but-many LTF, and More, New Ideas to Build Noise-Free Homomorphic Cryptosystems, A Lattice-Based Approach to Privacy-Preserving Biometric Authentication Without Relying on Trusted Third Parties, An Improved Leveled Fully Homomorphic Encryption Scheme over the Integers, Fully Homomorphic Encryption with Auxiliary Inputs, Trapdoors for Ideal Lattices with Applications, Blending FHE-NTRU Keys – The Excalibur Property, Predicate Encryption for Circuits from LWE, Coded-BKW: Solving LWE Using Lattice Codes, An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices, Multi-key FHE from LWE, Revisited, Deniable Attribute Based Encryption for Branching Programs from LWE, Targeted Homomorphic Attribute-Based Encryption, Towards a Simpler Lattice Gadget Toolkit, Shorter Lattice-Based Group Signatures via “Almost Free” Encryption and Other Optimizations, Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS, Privacy-preserving blueprints, Functional commitments for all functions, with transparent setup and from SIS, Batch bootstrapping. I: A new framework for SIMD bootstrapping in polynomial modulus, Batch bootstrapping. II: Bootstrapping in polynomial modulus only requires \(\tilde{O}(1)\) FHE multiplications in amortization, Succinct vector, polynomial, and functional commitments from lattices, Algebraic restriction codes and their applications, Optimisations and tradeoffs for HElib, Privately puncturing PRFs from lattices: adaptive security and collusion resistant pseudorandomness, HDDA: DataSifter: statistical obfuscation of electronic health records and other sensitive datasets, Revisiting the Sparsification Technique in Kannan’s Embedding Attack on LWE, Multi-key Homomorphic Proxy Re-Encryption, Multikey Fully Homomorphic Encryption and Applications, Unnamed Item, Lattice-Based Identity-Based Homomorphic Conditional Proxy Re-Encryption for Secure Big Data Computing in Cloud Environment, Deterministic compression with uncertain priors, Non-commutative arithmetic circuits with division, Decision trees, protocols and the entropy-influence conjecture, Locally testable codes and cayley graphs, Invitation games and the price of stability, Welfare maximization and truthfulness in mechanism design with ordinal preferences, Coordination mechanisms from (almost) all scheduling policies, Private interactive communication across an adversarial channel, Tree codes and a conjecture on exponential sums, Foundations of Homomorphic Secret Sharing, Capacity of non-malleable codes, Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications, Adversarial hypothesis testing and a quantum stein's lemma for restricted measurements, Sequential decision making with vector outcomes, Learning mixtures of arbitrary distributions over large discrete domains, Why do simple algorithms for triangle enumeration work in the real world?, Black-box obfuscation for d-CNFs, Candidate weak pseudorandom functions in AC ⁰ ○ MOD ₂, Iterated group products and leakage resilience against NC1, Building one-time memories from isolated qubits, Attribute-efficient evolvability of linear functions, Energy-efficient circuit design, Rate-independent computation in continuous chemical reaction networks, Testers and their applications, On the automorphism groups of strongly regular graphs I, Faster private release of marginals on small databases, Mechanism design in large games, Redrawing the boundaries on purchasing data from privacy-sensitive individuals, Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems, Complexity of approximating CSP with balance / hard constraints, Integer feasibility of random polytopes, Multireference alignment using semidefinite programming, Partial tests, universal tests and decomposability, High dimensional expanders and property testing, Parameterized testability, Direct sum fails for zero error average communication, Rational arguments, Boolean Functions for Homomorphic-Friendly Stream Ciphers, Compact Inner Product Encryption from LWE, Practical Fully Homomorphic Encryption for Fully Masked Neural Networks, Fractional LWE: A Nonlinear Variant of LWE, Ring Packing and Amortized FHEW Bootstrapping, Circuit-Private Multi-key FHE, FHE over the Integers: Decomposed and Batched in the Post-Quantum Regime, Separating IND-CPA and Circular Security for Unbounded Length Key Cycles, Private Puncturable PRFs from Standard Lattice Assumptions, Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack, On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL, Somewhat/Fully Homomorphic Encryption: Implementation Progresses and Challenges, On the Black-box Use of Somewhat Homomorphic Encryption in NonInteractive Two-Party Protocols, The truth behind the myth of the folk theorem, Expanders with respect to Hadamard spaces and random graphs, Limits of local algorithms over sparse random graphs, Watermarking cryptographic functionalities from standard lattice assumptions, Multi-theorem preprocessing NIZKs from lattices, Tighter security proofs for GPV-IBE in the quantum random oracle model, Provably Secure (Broadcast) Homomorphic Signcryption, Two-round \(n\)-out-of-\(n\) and multi-signatures and trapdoor commitment from lattices, Two-round \(n\)-out-of-\(n\) and multi-signatures and trapdoor commitment from lattices, Adaptive oblivious transfer with access control from lattice assumptions, Adaptively secure MPC with sublinear communication complexity, Classical Homomorphic Encryption for Quantum Circuits, How to Use Indistinguishability Obfuscation: Deniable Encryption, and More, Homomorphic Proxy Re-Authenticators and Applications to Verifiable Multi-User Data Aggregation, Towards Round-Optimal Secure Multiparty Computations: Multikey FHE Without a CRS, Unnamed Item, Homomorphic Encryption, Lattice-Based SNARGs and Their Application to More Efficient Obfuscation, On the deductive security of queries to confidential databases in cloud computing systems, Deniable fully homomorphic encryption from learning with errors, Counterexamples to new circular security assumptions underlying iO, SO-CCA secure PKE from pairing based all-but-many lossy trapdoor functions, Attribute-based signatures from lattices: unbounded attributes and semi-adaptive security, Adaptively secure distributed PRFs from LWE, White box traitor tracing, Universal product learning with errors: a new variant of \textsf{LWE} for lattice-based cryptography, Lattice-based HRA-secure attribute-based proxy re-encryption in standard model, Transciphering, using FiLIP and TFHE for an efficient delegation of computation, On a dual/hybrid approach to small secret LWE. A dual/enumeration technique for learning with errors and application to security estimates of FHE schemes, Constructive \(t\)-secure homomorphic secret sharing for low degree polynomials, Faster Gaussian sampling for trapdoor lattices with arbitrary modulus, Homomorphic lower digits removal and improved FHE bootstrapping, Bootstrapping for approximate homomorphic encryption, Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems, PGAS: privacy-preserving graph encryption for accurate constrained shortest distance queries, Tightly secure ring-LWE based key encapsulation with short ciphertexts, Garbled circuits with sublinear evaluator, Practical non-interactive publicly verifiable secret sharing with thousands of parties, Single-server private information retrieval with sublinear amortized time, Bootstrapping for helib, Privacy-preserving computation in cyber-physical-social systems: a survey of the state-of-the-art and perspectives, From FE combiners to secure MPC and back, Leveraging linear decryption: rate-1 fully-homomorphic encryption and time-lock puzzles, Compressible FHE with applications to PIR, Incrementally verifiable computation via incremental PCPs, Improved filter permutators for efficient FHE: better instances and implementations, A survey of lattice based expressive attribute based encryption, Cryptographic algorithms for privacy-preserving online applications, Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression, FHEW with Efficient Multibit Bootstrapping, Private Computation on Encrypted Genomic Data, On Key Recovery Attacks Against Existing Somewhat Homomorphic Encryption Schemes, Adaptive Key Recovery Attacks on NTRU-Based Somewhat Homomorphic Encryption Schemes, Towards Tightly Secure Lattice Short Signature and Id-Based Encryption, A Homomorphic Proxy Re-encryption from Lattices, Preventing Adaptive Key Recovery Attacks on the GSW Levelled Homomorphic Encryption Scheme, Flattening NTRU for evaluation key free homomorphic encryption, Computational fuzzy extractor from LWE, Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds, Secure MPC: laziness leads to GOD, Adaptively secure inner product encryption from LWE, Multi-client oblivious RAM with poly-logarithmic communication, Efficient homomorphic comparison methods with optimal complexity, Simpler statistically sender private oblivious transfer from ideals of cyclotomic integers, An efficient quantum somewhat homomorphic symmetric searchable encryption, Succinct LWE sampling, random polynomials, and obfuscation, Ring-based identity based encryption -- asymptotically shorter MPK and tighter security, Towards tight adaptive security of non-interactive key exchange, Vector and functional commitments from lattices, Direct computation of branching programs and its applications to more efficient lattice-based cryptography, Simulatable verifiable random function from the LWE assumption, Maliciously circuit-private multi-key FHE and MPC based on LWE, Multi-bit Leveled Homomorphic Encryption via $$\mathsf {Dual.LWE}$$ -Based, Cryptanalysis of a Homomorphic Encryption Scheme Over Integers, Lattice-based FHE as secure as PKE, Cryptogenography, Limits of random oracles in secure computation, Unsupervised Machine Learning on encrypted data, Efficient AGCD-based homomorphic encryption for matrix and vector arithmetic, Verifiably encrypted signatures with short keys based on the decisional linear problem and obfuscation for encrypted VES, Trusted computing with addition machines. I, How to securely outsource the extended Euclidean algorithm for large-scale polynomials over finite fields, A multi-key SMC protocol and multi-key FHE based on some-are-errorless LWE, On the structure of Boolean functions with small spectral norm, Round-Optimal Password-Based Group Key Exchange Protocols in the Standard Model, Decompositions of Triangle-Dense Graphs, Adaptively secure distributed PRFs from \(\mathsf{LWE}\), Minimizing the Number of Bootstrappings in Fully Homomorphic Encryption, Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits, TFHE: fast fully homomorphic encryption over the torus, Candidate iO from homomorphic encryption schemes, Boosting verifiable computation on encrypted data, Decentralized multi-authority \textbf{\textsf{ABE}} for \textbf{\textsf{DNF}}s from \textbf{\textsf{LWE}}, Post-quantum multi-party computation, High-precision bootstrapping of RNS-CKKS homomorphic encryption using optimal minimax polynomial approximation and inverse sine function, Multiparty reusable non-interactive secure computation from LWE, Candidate obfuscation via oblivious LWE sampling, Bifurcated signatures: folding the accountability vs. anonymity dilemma into a single private signing scheme, An efficient CCA-secure access control encryption for any policy, Accelerating Homomorphic Computations on Rational Numbers, Bootstrapping fully homomorphic encryption over the integers in less than one second, Round-optimal verifiable oblivious pseudorandom functions from ideal lattices, Flexible and efficient verifiable computation on encrypted data, FHE Circuit Privacy Almost for Free, Cryptanalysis of GGH15 Multilinear Maps, Circuit-ABE from LWE: Unbounded Attributes and Semi-adaptive Security, How to Prove Knowledge of Small Secrets, Lattice-Based Fully Dynamic Multi-key FHE with Short Ciphertexts, Breaking the Circuit Size Barrier for Secure Computation Under DDH, Integer polynomial recovery from outputs and its application to cryptanalysis of a protocol for secure sorting, A new scale-invariant homomorphic encryption scheme, A new Gaussian sampling for trapdoor lattices with arbitrary modulus, Tightly secure signature schemes from the LWE and subset sum assumptions, Keyed-fully homomorphic encryption without indistinguishability obfuscation, An optimized GHV-type HE scheme: simpler, faster, and more versatile, Access control encryption from group encryption, Password protected secret sharing from lattices, A practical adaptive key recovery attack on the LGM (GSW-like) cryptosystem, Verifiable Decryption for Fully Homomorphic Encryption, Parameter optimization and larger precision for (T)FHE, MPClan: protocol suite for privacy-conscious computations, Batched fully homomorphic encryption from TFHE, Lattice-based signatures with tight adaptive corruptions and more, A note on the post-quantum security of (ring) signatures, Bounded functional encryption for Turing machines: adaptive security from general assumptions, ABE for circuits with constant-size secret keys and adaptive security, Achievable \textsf{CCA2} relaxation for homomorphic encryption, mrNISC from LWE with polynomial modulus, Homomorphic encryption: a mathematical survey, mrNISC from LWE with polynomial modulus, EvalRound algorithm in CKKS bootstrapping, FINAL: faster FHE instantiated with NTRU and LWE, Triply adaptive UC NIZK, Multi-key fully homomorphic encryption from NTRU and (R)LWE with faster bootstrapping, Cumulatively all-lossy-but-one trapdoor functions from standard assumptions, Scooby: improved multi-party homomorphic secret sharing based on FHE, Towards case-optimized hybrid homomorphic encryption. Featuring the \textsf{Elisabeth} stream cipher, Compact and tightly selective-opening secure public-key encryption schemes, Polynomial-time cryptanalysis of the subspace flooding assumption for post-quantum \(i\mathcal{O} \), Optimal single-server private information retrieval, Computing primitive idempotents in finite commutative rings and applications, Reverse firewalls for adaptively secure MPC without setup, Balanced non-adjacent forms, Transciphering framework for approximate homomorphic encryption, Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE, Time-release cryptography from minimal circuit assumptions, Public-key watermarking schemes for pseudorandom functions, Leveled Hierarchical Identity-Based Fully Homomorphic Encryption from Learning with Rounding, Spatial encryption revisited: from delegatable multiple inner product encryption and more, Scooby: improved multi-party homomorphic secret sharing based on FHE, Fully homomorphic encryption scheme and Fermat’s little theorem, Coefficient grouping for complex affine layers, Fast blind rotation for bootstrapping FHEs, Accelerating HE operations from key decomposition technique, How to use (plain) witness encryption: registered ABE, flexible broadcast, and more, Cryptography with certified deletion, Lattice-based timed cryptography, A lower bound for proving hardness of learning with rounding with polynomial modulus, Candidate iO from homomorphic encryption schemes, Classical Homomorphic Encryption for Quantum Circuits