On the Hardness of the Asymmetric Learning With Errors Problem

Jiang ZHANG; Shuqin FAN

doi:10.11999/JEIT190685

Volume 42 Issue 2

Feb. 2020

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2020 > 42(2): 327-332

Jiang ZHANG, Shuqin FAN. On the Hardness of the Asymmetric Learning With Errors Problem[J]. Journal of Electronics & Information Technology, 2020, 42(2): 327-332. doi: 10.11999/JEIT190685

Citation:

Jiang ZHANG, Shuqin FAN. On the Hardness of the Asymmetric Learning With Errors Problem[J]. Journal of Electronics & Information Technology, 2020, 42(2): 327-332. doi: 10.11999/JEIT190685

Jiang ZHANG, Shuqin FAN. On the Hardness of the Asymmetric Learning With Errors Problem[J]. Journal of Electronics & Information Technology, 2020, 42(2): 327-332. doi: 10.11999/JEIT190685

Citation:

Jiang ZHANG, Shuqin FAN. On the Hardness of the Asymmetric Learning With Errors Problem[J]. Journal of Electronics & Information Technology, 2020, 42(2): 327-332. doi: 10.11999/JEIT190685

PDF( 577 KB)

On the Hardness of the Asymmetric Learning With Errors Problem

doi: 10.11999/JEIT190685

Jiang ZHANG^,,
Shuqin FAN

State Key Laboratory of Cryptology, Beijing 100878, China

Funds: The National Key Research and Development Program of China (2017YFB0802005, 2018YFB0804105), The National Natural Science Foundation of China (61602046, 61932019), The Young Elite Scientists Sponsorship Program by China Association for Science and Technology (2016QNRC001)

Received Date: 2019-09-14
Rev Recd Date: 2019-11-20

Available Online: 2019-11-29

Publish Date: 2020-02-19

Abstract

Abstract

Due to the advantages such as the worst-case hardness assumption, lattice-based cryptography is believed to the most promising research direction in post-quantum cryptography. As one of the two main hard problems commonly used in lattice-based cryptography, Learning With Errors (LWE) problem is widely used in constructing numerous cryptosystems. In order to improve the efficiency of lattice-based cryptosystems, Zhang et al. (2019) introduced the Asymmetric LWE (ALWE) problem. In this paper, the relation between the ALWE problem and the standard LWE problem is studied, and it shows that for certain error distributions the two problems are polynomially equivent, which paves the way for constructing secure lattice-based cryptosystems from the ALWE problem.
- Post-qauntum cryptography,
- Lattice-based cryptography,
- Learning With Errors (LWE)

FullText(HTML)

References(10)

References

SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484–1509. doi: 10.1137/S0097539795293172

NSA. National Security Agency. Cryptography today[EB/OL]. https://www.nsa.gov/ia/programs/suiteb_cryptography/, 2015.

NIST. Post-quantum cryptography standardization[EB/OL]. http://csrc.nist.gov/groups/ST/post-quantum-crypto/submission-requirements/index.html, 2016.

中国科学技术学会. 科普时报: 中国科协发布12个领域60大科技难题[EB/OL]. http://www.cast.org.cn/art/2018/6/22/art_90_77662.html, 2018.

REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]. The 37th Annual ACM Symposium on Theory of Computing, Baltimore, USA, 2005: 84–93.

AJTAI M. Generating hard instances of lattice problems (extended abstract)[C]. The 28th Annual ACM Symposium on Theory of Computing, Philadelphia, USA,1996: 99–108.

ZHANG Jiang, YU Yu, FAN Shuqin, et al. Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes[R]. Cryptology ePrint Archive 2019/510, 2019.

APPLEBAUM B, CASH D, PEIKERT C, et al. Fast cryptographic primitives and circular-secure encryption based on hard learning problems[C]. The 29th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2009: 595–618.

MICCIANCIO D and REGEV O. Worst-case to average-case reductions based on Gaussian measures[C]. The 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004: 372–381.

PEIKERT C. An efficient and parallel Gaussian sampler for lattices[C]. The 30th Annual Conference on Advances in Cryptology, Santa Barbara, USA, 2010: 80–97.

Relative Articles

Supplements(0)

Cited By

Proportional views