| 1. |
- Budroni, Alessandro, et al.
(författare)
-
Improvements on Making BKW Practical for Solving LWE
- 2021
-
Ingår i: Cryptography. - : MDPI AG. - 2410-387X. ; 5:4
-
Tidskriftsartikel (refereegranskat)abstract
- The learning with errors (LWE) problem is one of the main mathematical foundations of post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum–Kalai–Wasserman (BKW) algorithm. This paper presents new improvements of BKW-style algorithms for solving LWE instances. We target minimum concrete complexity, and we introduce a new reduction step where we partially reduce the last position in an iteration and finish the reduction in the next iteration, allowing non-integer step sizes. We also introduce a new procedure in the secret recovery by mapping the problem to binary problems and applying the fast Walsh Hadamard transform. The complexity of the resulting algorithm compares favorably with all other previous approaches, including lattice sieving. We additionally show the steps of implementing the approach for large LWE problem instances. We provide two implementations of the algorithm, one RAM-based approach that is optimized for speed, and one file-based approach which overcomes RAM limitations by using file-based storage.
|
|
| 2. |
- Budroni, Alessandro, et al.
(författare)
-
Making the BKW Algorithm Practical for LWE
- 2020
-
Ingår i: Progress in Cryptology – INDOCRYPT 2020 : 21st International Conference on Cryptology in India Bangalore, India, December 13–16, 2020 Proceedings - 21st International Conference on Cryptology in India Bangalore, India, December 13–16, 2020 Proceedings. - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. - 9783030652777 - 9783030652760 ; 12578, s. 417-439
-
Konferensbidrag (refereegranskat)abstract
- The Learning with Errors (LWE) problem is one of the main mathematical foundations of post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum-Kalai-Wasserman (BKW) algorithm. This paper presents new improvements for BKW-style algorithms for solving LWE instances. We target minimum concrete complexity and we introduce a new reduction step where we partially reduce the last position in an iteration and finish the reduction in the next iteration, allowing non-integer step sizes. We also introduce a new procedure in the secret recovery by mapping the problem to binary problems and applying the FastWalsh Hadamard Transform. The complexity of the resulting algorithm compares favourably to all other previous approaches, including lattice sieving. We additionally show the steps of implementing the approach for large LWE problem instances. The core idea here is to overcome RAM limitations by using large file-based memory.
|
|
| 3. |
- Guo, Qian, et al.
(författare)
-
Coded-BKW with Sieving
- 2017
-
Ingår i: Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. - Cham : Springer International Publishing. - 0302-9743. - 9783319706948 - 9783319706931 ; 10624, s. 323-346
-
Konferensbidrag (refereegranskat)abstract
- The Learning with Errors problem (LWE) has become a central topic in recent cryptographic research. In this paper, we present a new solving algorithm combining important ideas from previous work on improving the BKW algorithm and ideas from sieving in lattices. The new algorithm is analyzed and demonstrates an improved asymptotic performance. For Regev parameters q = n^2 and noise level \sigma = n^1.5/(\sqrt{2\pi} \log_2^2 n), the asymptotic complexity is 2^{0.895n} in the standard setting, improving on the previously best known complexity of roughly 2^{0.930n}. Also for concrete parameter instances, improved performance is indicated.
|
|
| 4. |
- Guo, Qian, et al.
(författare)
-
Information Set Decoding with Soft Information and some cryptographic applications
- 2017
-
Ingår i: IEEE International Symposium on Information Theory (ISIT). - 9781509040964 ; , s. 1793-1797
-
Konferensbidrag (refereegranskat)abstract
- The class of information set decoding algorithms is the best known way of decoding general codes, i.e. codes that admit no special structure, in the Hamming metric. Stern's algorithm is the origin of the most efficient algorithms in this class. In this paper we consider the same decoding problem but for a channel with soft information. We give a version of Stern's algorithm for a channel with soft information that includes some novel steps of ordering vectors in lists, based on reliability values. We then demonstrate how this new algorithm can be used in a few cryptographic applications, including a very efficient attack on a recently proposed McEliece-type cryptosystem.
|
|
| 5. |
- Guo, Qian, et al.
(författare)
-
On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving
- 2019
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448. ; 65:8, s. 5243-5259
-
Tidskriftsartikel (refereegranskat)abstract
- The Learning with Errors problem (LWE) has become a central topic in recent cryptographic research. In this paper, we present a new solving algorithm combining important ideas from previous work on improving the Blum-Kalai-Wasserman (BKW) algorithm and ideas from sieving in lattices. The new algorithm is analyzed and demonstrates an improved asymptotic performance. For the Regev parameters $q=n^2$ and noise level $\sigma = n^{1.5}/(\sqrt{2\pi}\log_{2}^{2}n)$, the asymptotic complexity is $2^{0.893n}$ in the standard setting, improving on the previously best known complexity of roughly $2^{0.930n}$. The newly proposed algorithm also provides asymptotic improvements when a quantum computer is assumed or when the number of samples is limited.
|
|
| 6. |
- Guo, Qian, et al.
(författare)
-
Some Cryptanalytic and Coding-Theoretic Applications of a Soft Stern Algorithm
- 2019
-
Ingår i: Advances in Mathematics of Communications. - : American Institute of Mathematical Sciences (AIMS). - 1930-5346 .- 1930-5338. ; 13:4, s. 559-578
-
Tidskriftsartikel (refereegranskat)abstract
- Using the class of information set decoding algorithms is the best known way of decoding general codes, i.e. codes that admit no special structure, in the Hamming metric. The Stern algorithm is the origin of the most efficient algorithms in this class. We consider the same decoding problem but for a channel with soft information. We give a version of the Stern algorithm for a channel with soft information that includes some novel steps of ordering vectors in lists, based on reliability values. We demonstrate how the algorithm constitutes an improvement in some cryptographic and coding theoretic applications. We also indicate how to extend the algorithm to include multiple iterations and soft output values.
|
|
