English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The dual attack is one of the most efficient attack algorithms for 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 paper, 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 a dimension-error tradeoff, which finally yields our hybrid attack. We also implement a sage module that estimates the attack complexity of our algorithm upon <italic>LWE-estimator</italic>, and our attack shows significant performance improvement for the LWE parameter for FHE. For example, for the LWE problem with dimension <inline-formula> <tex-math notation="LaTeX">$n=2^{15}$ </tex-math></inline-formula>, modulus <inline-formula> <tex-math notation="LaTeX">$q=2^{628}$ </tex-math></inline-formula>, and ternary secret key with Hamming weight 64 which is one parameter set used for <italic>HEAAN</italic> bootstrapping (Eurocrypt 2018), our attack takes 2112.5 operations and 270.6 bit memory, while the previous best attack requires 2127.2 operations as reported by the <italic>LWE-estimator</italic>.

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