You are looking at a specific version 20191001:150904 of this paper. See the latest version.

Paper 2019/1114

A Hybrid of Dual and Meet-in-the-Middle Attack on Sparse and Ternary Secret LWE

Jung Hee Cheon and Minki Hhan and Seungwan Hong and Yongha Son

Abstract

The dual attack is one of the most efficient attack algorithms for the Learning with Errors (LWE) problem. Recently, an efficient variant of the dual attack for sparse and small secret LWE was reported by Albrecht [Eurocrypt 2017], which forces some LWE-based cryptosystems, especially fully homomorphic encryptions (FHE), to change parameters. In this work, we propose a new hybrid of dual and meet-in-the-middle (MITM) attack, which outperforms the improved variant on the same LWE parameter regime. To this end, we adapt the MITM attack for NTRU due to Odlyzko to LWE, and give a rigorous analysis for it. The performance of our MITM attack depends on the relative size of error and modulus, and hence for a large modulus LWE samples, our MITM attack works well for quite large error. We then combine our MITM attack with Albrecht's observation that understands the dual attack as dimension-error tradeoff, which finally yields our hybrid attack. We also implement a sage module that estimates the attack complexity of our algorithm upon {\sf LWE-estimator}, and our attack shows significant performance improvement for the LWE parameter for FHE. For example, for the LWE problem with dimension $n=2^{15}$, modulus $q=2^{628}$ and ternary secret key with Hamming weight 64 which is one parameter set used for {\sf HEAAN} bootstrapping [Eurocrypt 2018], our attack takes $2^{112.5}$ operations and $2^{70.6}$ bit memory while the previous best attack requires $2^{127.2}$ operations as reported by {\sf LWE-estimator}.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
CryptanalysisFully homomorphic encryptionLearning with ErrorsMeet-in-the-middle.
Contact author(s)
emsskk @ gmail com
History
2019-10-01: received
Short URL
https://ia.cr/2019/1114
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.