The search functionality is under construction.

The search functionality is under construction.

The learning with errors (LWE) problem is considered as one of the most compelling candidates as the security base for the post-quantum cryptosystems. For the application of LWE based cryptographic schemes, the concrete parameters are necessary: the length *n* of secret vector, the moduli *q* and the deviation *σ*. In the middle of 2016, Germany TU Darmstadt group initiated the LWE Challenge in order to assess the hardness of LWE problems. There are several approaches to solve the LWE problem via reducing LWE to other lattice problems. Xu et al.'s group solved some LWE Challenge instances using Liu-Nguyen's adapted enumeration technique (reducing LWE to BDD problem) [23] and they published this result at ACNS 2017 [32]. In this paper, at first, we applied the progressive BKZ on the LWE challenge cases of *σ*/*q*=0.005 using Kannan's embedding technique. We can intuitively observe that the embedding technique is more efficient with the embedding factor *M* closer to 1. Then we will analyze the optimal number of samples *m* for a successful attack on LWE case with secret length of *n*. Thirdly based on this analysis, we show the practical cost estimations using the precise progressive BKZ simulator. Simultaneously, our experimental results show that for *n* ≥ 55 and the fixed *σ*/*q*=0.005, the embedding technique with progressive BKZ is more efficient than Xu et al.'s implementation of the enumeration algorithm in [32][14]. Moreover, by our parameter setting, we succeed in solving the LWE Challenge over (*n*,*σ*/*q*)=(70, 0.005) using 2^{16.8} seconds (32.73 single core hours).

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.12 pp.2162-2170

- Publication Date
- 2018/12/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E101.A.2162

- Type of Manuscript
- Special Section PAPER (Special Section on Information Theory and Its Applications)

- Category
- Cryptography and Information Security

Yuntao WANG

Kyushu University,The University of Tokyo

Yoshinori AONO

National Institute of Communication and Technology

Tsuyoshi TAKAGI

The University of Tokyo,Kyushu University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Yuntao WANG, Yoshinori AONO, Tsuyoshi TAKAGI, "Hardness Evaluation for Search LWE Problem Using Progressive BKZ Simulator" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 12, pp. 2162-2170, December 2018, doi: 10.1587/transfun.E101.A.2162.

Abstract: The learning with errors (LWE) problem is considered as one of the most compelling candidates as the security base for the post-quantum cryptosystems. For the application of LWE based cryptographic schemes, the concrete parameters are necessary: the length *n* of secret vector, the moduli *q* and the deviation *σ*. In the middle of 2016, Germany TU Darmstadt group initiated the LWE Challenge in order to assess the hardness of LWE problems. There are several approaches to solve the LWE problem via reducing LWE to other lattice problems. Xu et al.'s group solved some LWE Challenge instances using Liu-Nguyen's adapted enumeration technique (reducing LWE to BDD problem) [23] and they published this result at ACNS 2017 [32]. In this paper, at first, we applied the progressive BKZ on the LWE challenge cases of *σ*/*q*=0.005 using Kannan's embedding technique. We can intuitively observe that the embedding technique is more efficient with the embedding factor *M* closer to 1. Then we will analyze the optimal number of samples *m* for a successful attack on LWE case with secret length of *n*. Thirdly based on this analysis, we show the practical cost estimations using the precise progressive BKZ simulator. Simultaneously, our experimental results show that for *n* ≥ 55 and the fixed *σ*/*q*=0.005, the embedding technique with progressive BKZ is more efficient than Xu et al.'s implementation of the enumeration algorithm in [32][14]. Moreover, by our parameter setting, we succeed in solving the LWE Challenge over (*n*,*σ*/*q*)=(70, 0.005) using 2^{16.8} seconds (32.73 single core hours).

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.2162/_p

Copy

@ARTICLE{e101-a_12_2162,

author={Yuntao WANG, Yoshinori AONO, Tsuyoshi TAKAGI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Hardness Evaluation for Search LWE Problem Using Progressive BKZ Simulator},

year={2018},

volume={E101-A},

number={12},

pages={2162-2170},

abstract={The learning with errors (LWE) problem is considered as one of the most compelling candidates as the security base for the post-quantum cryptosystems. For the application of LWE based cryptographic schemes, the concrete parameters are necessary: the length *n* of secret vector, the moduli *q* and the deviation *σ*. In the middle of 2016, Germany TU Darmstadt group initiated the LWE Challenge in order to assess the hardness of LWE problems. There are several approaches to solve the LWE problem via reducing LWE to other lattice problems. Xu et al.'s group solved some LWE Challenge instances using Liu-Nguyen's adapted enumeration technique (reducing LWE to BDD problem) [23] and they published this result at ACNS 2017 [32]. In this paper, at first, we applied the progressive BKZ on the LWE challenge cases of *σ*/*q*=0.005 using Kannan's embedding technique. We can intuitively observe that the embedding technique is more efficient with the embedding factor *M* closer to 1. Then we will analyze the optimal number of samples *m* for a successful attack on LWE case with secret length of *n*. Thirdly based on this analysis, we show the practical cost estimations using the precise progressive BKZ simulator. Simultaneously, our experimental results show that for *n* ≥ 55 and the fixed *σ*/*q*=0.005, the embedding technique with progressive BKZ is more efficient than Xu et al.'s implementation of the enumeration algorithm in [32][14]. Moreover, by our parameter setting, we succeed in solving the LWE Challenge over (*n*,*σ*/*q*)=(70, 0.005) using 2^{16.8} seconds (32.73 single core hours).},

keywords={},

doi={10.1587/transfun.E101.A.2162},

ISSN={1745-1337},

month={December},}

Copy

TY - JOUR

TI - Hardness Evaluation for Search LWE Problem Using Progressive BKZ Simulator

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 2162

EP - 2170

AU - Yuntao WANG

AU - Yoshinori AONO

AU - Tsuyoshi TAKAGI

PY - 2018

DO - 10.1587/transfun.E101.A.2162

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E101-A

IS - 12

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - December 2018

AB - The learning with errors (LWE) problem is considered as one of the most compelling candidates as the security base for the post-quantum cryptosystems. For the application of LWE based cryptographic schemes, the concrete parameters are necessary: the length *n* of secret vector, the moduli *q* and the deviation *σ*. In the middle of 2016, Germany TU Darmstadt group initiated the LWE Challenge in order to assess the hardness of LWE problems. There are several approaches to solve the LWE problem via reducing LWE to other lattice problems. Xu et al.'s group solved some LWE Challenge instances using Liu-Nguyen's adapted enumeration technique (reducing LWE to BDD problem) [23] and they published this result at ACNS 2017 [32]. In this paper, at first, we applied the progressive BKZ on the LWE challenge cases of *σ*/*q*=0.005 using Kannan's embedding technique. We can intuitively observe that the embedding technique is more efficient with the embedding factor *M* closer to 1. Then we will analyze the optimal number of samples *m* for a successful attack on LWE case with secret length of *n*. Thirdly based on this analysis, we show the practical cost estimations using the precise progressive BKZ simulator. Simultaneously, our experimental results show that for *n* ≥ 55 and the fixed *σ*/*q*=0.005, the embedding technique with progressive BKZ is more efficient than Xu et al.'s implementation of the enumeration algorithm in [32][14]. Moreover, by our parameter setting, we succeed in solving the LWE Challenge over (*n*,*σ*/*q*)=(70, 0.005) using 2^{16.8} seconds (32.73 single core hours).

ER -