### Distinguishing LWE Instances Using Fourier Transform: A Refined Framework and its Applications

Zhao Chunhuan, Zheng Zhongxiang, Wang Xiaoyun, and Xu Guangwu

##### Abstract

As a fundamental tool in lattice-based cryptosystems, discrete Gaussian samplers play important roles in both efficiency and security of lattice-based schemes. Approximate discrete rounded Gaussian sampler, central binomial sampler and bounded uniform sampler are three types of error samplers that are commonly used in the designs of various schemes. However, known cryptanalytics about error samplers concentrate on their standard deviations and no analysis about distinct structures of distributions have been proposed. In this paper, we address this problem by considering the dual attack for LWE instances and investigating Fourier transforms of these distributions. We introduce the concept of local width which enables us to get a more detailed look of these distributions and the distinguish advantages. We make an analysis of dual attack for different distributions and provide a novel measure model to describe the differences. Within this refined framework, we also propose a novel type of error sampler which can achieve high efficiency, security as well as flexibility.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
discrete Gaussian samplinglatticedistinguish advantageLWEdual attack
Contact author(s)
zhengzx13 @ tsinghua org cn
History
Short URL
https://ia.cr/2019/1231

CC BY

BibTeX

@misc{cryptoeprint:2019/1231,
author = {Zhao Chunhuan and Zheng Zhongxiang and Wang Xiaoyun and Xu Guangwu},
title = {Distinguishing LWE Instances  Using Fourier Transform: A Refined Framework and its Applications},
howpublished = {Cryptology ePrint Archive, Paper 2019/1231},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/1231}},
url = {https://eprint.iacr.org/2019/1231}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.