Estimating Key Sizes for High Dimensional Lattice-Based Systems

We revisit the estimation of parameters for use in applications of the BGV homomorphic encryption system, which generally require high dimensional lattices. In particular, we utilize the BKZ-2.0 simulator of Chen and Nguyen to identify the best lattice attack that can be mounted using BKZ in a given dimension at a given security level. Using this technique, we show that it should be possible to work with lattices of smaller dimensions than previous methods have recommended, while still maintaining reasonable levels of security. As example applications we look at the evaluation of AES via FHE operations presented at Crypto 2012, and the parameters for the SHE variant of BGV used in the SPDZ protocol from Crypto 2012.

• Publication year

  2013

• Venue

  IMA Conference on Cryptography and Coding

• Publication date

  2013-12-17

• Fields of study

  Mathematics, Materials Science, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-45239-0_17
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• (Leveled) Fully Homomorphic Encryption without Bootstrapping

  2014cited by this paper
• Practical Covertly Secure MPC for Dishonest Majority - Or: Breaking the SPDZ Limits

  2013cited by this paper
• Homomorphic Evaluation of the AES Circuit

  2012cited by this paper
• Multiparty Computation from Somewhat Homomorphic Encryption

  2012cited by this paper
• BKZ 2.0: Better Lattice Security Estimates

  2011cited by this paper
• Better Key Sizes (and Attacks) for LWE-Based Encryption

  2011influential reference
• Lattice Enumeration Using Extreme Pruning

  2010cited by this paper
• Fully homomorphic encryption using ideal lattices

  2009influential reference
• 1 . 2 Lattice-based cryptography

  2008cited by this paper
• Predicting Lattice Reduction

  2008influential reference
• LLL on the Average

  2006cited by this paper
• Lattice-Based Cryptography

  2006cited by this paper
• On the equidistribution of Hecke points

  2003influential reference
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems

  1991cited by this paper

• Leveled Homomorphic Encryption Schemes for Homomorphic Encryption Standard

  2025influential citation
• High-Speed Implementation of Lattice Enumeration with Discrete Pruning for Solving the SVP

  2024cites this paper
• NLSP: A novel lattice-based secure primitive for privacy-preserving smart grid communications

  2022cites this paper
• Improved Quantum Hypercone Locality Sensitive Filtering in Lattice Sieving

  2021cites this paper
• A Noise Study of the PSW Signature Family: Patching DRS with Uniform Distribution †

  2020cites this paper
• Improving the Security of the DRS Scheme with Uniformly Chosen Random Noise

  2019cites this paper
• Ring-LWE Public Key Encryption Processor

  2019cites this paper
• A journey towards practical fully homomorphic encryption

  2018cites this paper
• nGraph-HE: a graph compiler for deep learning on homomorphically encrypted data

  2018cites this paper
• Towards Efficient Arithmetic for Ring-LWE based Homomorphic Encryption. (Vers une arithmétique efficace pour le chiffrement homomorphe basé sur le Ring-LWE)

  2018cites this paper
• A Note on Ring-LWE Security in the Case of Fully Homomorphic Encryption

  2017cites this paper
• Manual for Using Homomorphic Encryption for Bioinformatics

  2017cites this paper
• New Approaches for Efficient Fully Homomorphic Encryption

  2017influential citation
• Bootstrapping Fully Homomorphic Encryption with Ring Plaintexts Within Polynomial Noise

  2017cites this paper
• Sieving for shortest vectors in ideal lattices: a practical perspective

  2017cites this paper
• Simultaneous approximation problems of p-adic numbers and p-adic knapsack cryptosystems - Alice in p-adic numberland

  2016cites this paper
• On the Efficiency of FHE-Based Private Queries

  2016cites this paper
• A Measure Version of Gaussian Heuristic

  2016influential citation
• New directions in nearest neighbor searching with applications to lattice sieving

  2016cites this paper
• Elliptic Curve Multiset Hash

  2016cites this paper
• Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator

  2016cites this paper
• Search problems in cryptography : from fingerprinting to lattice sieving

  2016cites this paper
• Practical, Predictable Lattice Basis Reduction

  2016cites this paper
• Post-quantum key exchange based on ring-LWE

  2016cites this paper
• Efficient (Ideal) Lattice Sieving Using Cross-Polytope LSH

  2016cites this paper
• Finding shortest lattice vectors faster using quantum search

  2015cites this paper
• Bootstrapping BGV ciphertexts with a wider choice of p and q

  2015cites this paper
• New constructions of cryptographic pseudorandom functions

  2015cites this paper
• Post-Quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem

  2015cites this paper
• Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing

  2015cites this paper
• Fast Lattice Point Enumeration with Minimal Overhead

  2015cites this paper
• Key Recovery for LWE in Polynomial Time

  2015cites this paper
• On the concrete hardness of Learning with Errors

  2015cites this paper
• A Practical Key Exchange for the Internet using Lattice Cryptography

  2015cites this paper
• Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing

  2015cites this paper
• Cryptanalysis of the Co-ACD Assumption

  2015cites this paper
• Homomorphic Autocomplete

  2015cites this paper
• Homomorphic AES evaluation using the modified LTV scheme

  2015cites this paper
• Design and Implementation of Lattice-Based Cryptography. (Conception and implémentation de cryptographie à base de réseaux)

  2014cites this paper
• SPRING: Fast Pseudorandom Functions from Rounded Ring Products

  2014cites this paper
• A Comparison of the Homomorphic Encryption Schemes FV and YASHE

  2014cites this paper
• Compact Ring-LWE Cryptoprocessor

  2014cites this paper
• A New Additive Homomorphic Encryption based on the co-ACD Problem

  2014cites this paper