
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

On the Complexity of the LWRSolving BKW Algorithm
Hiroki OKADA Atsushi TAKAYASU Kazuhide FUKUSHIMA Shinsaku KIYOMOTO Tsuyoshi TAKAGI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E103A
No.1
pp.173182 Publication Date: 2020/01/01
Online ISSN: 17451337
DOI: 10.1587/transfun.2019CIP0022
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Keyword: lattice, learning with errors, learning with rounding, BlumKalaiWasserman algorithm,
Full Text: FreePDF(1.1MB)
Summary:
The BlumKalaiWasserman 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 LWRsolving BKW, under a heuristic assumption that is regularly used in the analysis of LPNsolving 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.

