On the Complexity of the LWR-Solving BKW Algorithm

Hiroki OKADA; Atsushi TAKAYASU; Kazuhide FUKUSHIMA; Shinsaku KIYOMOTO; Tsuyoshi TAKAGI

doi:10.1587/transfun.2019CIP0022

IEICE TRANSACTIONS on Fundamentals

Open Access
On the Complexity of the LWR-Solving BKW Algorithm

Hiroki OKADA, Atsushi TAKAYASU, Kazuhide FUKUSHIMA, Shinsaku KIYOMOTO, Tsuyoshi TAKAGI

Full Text Views

32

Cite this

Free PDF (1.1MB)

Summary :

The Blum-Kalai-Wasserman algorithm (BKW) is an algorithm for solving the learning parity with noise problem, which was then adapted for solving the learning with errors problem (LWE) by Albrecht et al. Duc et al. applied BKW also to the learning with rounding problem (LWR). The number of blocks is a parameter of BKW. By optimizing the number of blocks, we can minimize the time complexity of BKW. However, Duc et al. did not derive the optimal number of blocks theoretically, but they searched for it numerically. Duc et al. also showed that the required number of samples for BKW for solving LWE can be dramatically decreased using Lyubashevsky's idea. However, it is not shown that his idea is also applicable to LWR. In this paper, we theoretically derive the asymptotically optimal number of blocks, and then analyze the minimum asymptotic time complexity of the algorithm. We also show that Lyubashevsky's idea can be applied to LWR-solving BKW, under a heuristic assumption that is regularly used in the analysis of LPN-solving BKW. Furthermore, we derive an equation that relates the Gaussian parameter σ of LWE and the modulus p of LWR. When σ and p satisfy the equation, the asymptotic time complexity of BKW to solve LWE and LWR are the same.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.1 pp.173-182

Publication Date: 2020/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.2019CIP0022

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category

Authors

Hiroki OKADA
  KDDI Research, Inc.
Atsushi TAKAYASU
  The University of Tokyo
Kazuhide FUKUSHIMA
  KDDI Research, Inc.
Shinsaku KIYOMOTO
  KDDI Research, Inc.
Tsuyoshi TAKAGI
  The University of Tokyo

Keyword

lattice, learning with errors, learning with rounding, Blum-Kalai-Wasserman algorithm

Cite this

Copy

Hiroki OKADA, Atsushi TAKAYASU, Kazuhide FUKUSHIMA, Shinsaku KIYOMOTO, Tsuyoshi TAKAGI, "On the Complexity of the LWR-Solving BKW Algorithm" in IEICE TRANSACTIONS on Fundamentals, vol. E103-A, no. 1, pp. 173-182, January 2020, doi: 10.1587/transfun.2019CIP0022.
Abstract: The Blum-Kalai-Wasserman algorithm (BKW) is an algorithm for solving the learning parity with noise problem, which was then adapted for solving the learning with errors problem (LWE) by Albrecht et al. Duc et al. applied BKW also to the learning with rounding problem (LWR). The number of blocks is a parameter of BKW. By optimizing the number of blocks, we can minimize the time complexity of BKW. However, Duc et al. did not derive the optimal number of blocks theoretically, but they searched for it numerically. Duc et al. also showed that the required number of samples for BKW for solving LWE can be dramatically decreased using Lyubashevsky's idea. However, it is not shown that his idea is also applicable to LWR. In this paper, we theoretically derive the asymptotically optimal number of blocks, and then analyze the minimum asymptotic time complexity of the algorithm. We also show that Lyubashevsky's idea can be applied to LWR-solving BKW, under a heuristic assumption that is regularly used in the analysis of LPN-solving BKW. Furthermore, we derive an equation that relates the Gaussian parameter σ of LWE and the modulus p of LWR. When σ and p satisfy the equation, the asymptotic time complexity of BKW to solve LWE and LWR are the same.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2019CIP0022/_p

Copy

@ARTICLE{e103-a_1_173,
author={Hiroki OKADA, Atsushi TAKAYASU, Kazuhide FUKUSHIMA, Shinsaku KIYOMOTO, Tsuyoshi TAKAGI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Complexity of the LWR-Solving BKW Algorithm},
year={2020},
volume={E103-A},
number={1},
pages={173-182},
abstract={The Blum-Kalai-Wasserman algorithm (BKW) is an algorithm for solving the learning parity with noise problem, which was then adapted for solving the learning with errors problem (LWE) by Albrecht et al. Duc et al. applied BKW also to the learning with rounding problem (LWR). The number of blocks is a parameter of BKW. By optimizing the number of blocks, we can minimize the time complexity of BKW. However, Duc et al. did not derive the optimal number of blocks theoretically, but they searched for it numerically. Duc et al. also showed that the required number of samples for BKW for solving LWE can be dramatically decreased using Lyubashevsky's idea. However, it is not shown that his idea is also applicable to LWR. In this paper, we theoretically derive the asymptotically optimal number of blocks, and then analyze the minimum asymptotic time complexity of the algorithm. We also show that Lyubashevsky's idea can be applied to LWR-solving BKW, under a heuristic assumption that is regularly used in the analysis of LPN-solving BKW. Furthermore, we derive an equation that relates the Gaussian parameter σ of LWE and the modulus p of LWR. When σ and p satisfy the equation, the asymptotic time complexity of BKW to solve LWE and LWR are the same.},
keywords={},
doi={10.1587/transfun.2019CIP0022},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - On the Complexity of the LWR-Solving BKW Algorithm
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 173
EP - 182
AU - Hiroki OKADA
AU - Atsushi TAKAYASU
AU - Kazuhide FUKUSHIMA
AU - Shinsaku KIYOMOTO
AU - Tsuyoshi TAKAGI
PY - 2020
DO - 10.1587/transfun.2019CIP0022
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E103-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2020
AB - The Blum-Kalai-Wasserman algorithm (BKW) is an algorithm for solving the learning parity with noise problem, which was then adapted for solving the learning with errors problem (LWE) by Albrecht et al. Duc et al. applied BKW also to the learning with rounding problem (LWR). The number of blocks is a parameter of BKW. By optimizing the number of blocks, we can minimize the time complexity of BKW. However, Duc et al. did not derive the optimal number of blocks theoretically, but they searched for it numerically. Duc et al. also showed that the required number of samples for BKW for solving LWE can be dramatically decreased using Lyubashevsky's idea. However, it is not shown that his idea is also applicable to LWR. In this paper, we theoretically derive the asymptotically optimal number of blocks, and then analyze the minimum asymptotic time complexity of the algorithm. We also show that Lyubashevsky's idea can be applied to LWR-solving BKW, under a heuristic assumption that is regularly used in the analysis of LPN-solving BKW. Furthermore, we derive an equation that relates the Gaussian parameter σ of LWE and the modulus p of LWR. When σ and p satisfy the equation, the asymptotic time complexity of BKW to solve LWE and LWR are the same.
ER -

IEICE TRANSACTIONS on Fundamentals