Abstract The Blum-Kalai-Wasserman (BKW) algorithm is a significant combinatorial algorithm used to tackle the Learning with Errors (LWE) and Learning with Rounding (LWR) problems. In 2015, Duc et al. (in: Oswald and Fischlin (eds) EUROCRYPT 2015, Springer, Berlin, 2015) proposed the first BKW algorithm applied directly to LWR, which consists of the reduction phase and the solving phase. In this paper, we propose an improved LWR-solving BKW algorithm. For the reduction phase, we design a novel coding method with relaxed collision conditions and introduce a post-processing stage and for the solving phase, we switch to a more efficient Fast Fourier Transform (FFT) distinguisher with pruning. Compared to previous LWR-solving BKW algorithms, our new BKW algorithm achieves a time complexity improvement of 4.0–48.5 bits for the instances considered. Additionally, by incorporating a novel heuristic method in the reduction phase, our algorithm further improves the sample complexity by 3.7–48.7 bits.

Abstract The existing physical layer security schemes, which are based on the key generation model and the wire-tap channel model, achieve security by utilizing channel reciprocity entropy and noise entropy, respectively. In contrast, we propose a novel secure transmission framework that combines noise entropy with reciprocity entropy, achieved by inserting reciprocity entropy into the frozen bits of polar codes. Note that in real-world scenarios, when eavesdroppers employ polynomial-time attacks, the bit error rate (BER) increases due to the introduction of computational entropy. To achieve indistinguishability security, we convert the practical physical layer security metric, BER, into the average min-entropy, a widely accepted concept in cryptography. The simulation results demonstrate that the eavesdropper’s BER can be significantly increased without compromising the communication performance of the legitimate receiver. Under concrete parameters we selected, when compared to the joint scheme of physical layer key generation and one time pad, the modular semantically-secure scheme based on the wire-tap channel model, and the simple channel entropy combination scheme, our scheme achieves a message rate approximately 1.2 times, 3.8 times, and 1.4 times better, respectively. Experimental testing validates the feasibility of our scheme.

Abstract The Learning With Errors (LWE) problem is widely used in lattice-based cryptography, which is the most promising post-quantum cryptography direction. There are a variety of LWE-solving methods, which can be classified into four groups: lattice methods, algebraic methods, combinatorial methods, and exhaustive searching. The Blum–Kalai–Wasserman (BKW) algorithm is an important variety of combinatorial algorithms, which was first presented for solving the Learning Parity With Noise (LPN) problem and then extended to solve LWE. In this paper, we give an overview of BKW algorithms for solving LWE. We introduce the framework and key techniques of BKW algorithms and make comparisons between different BKW algorithms and also with lattice methods by estimating concrete security of specific LWE instances. We also briefly discuss the current problems and potential future directions of BKW algorithms.

Abstract In this paper, we study the hybrid dual attack over learning with errors (LWE) problems for any secret distribution. Prior to our work, hybrid attacks are only considered for sparse and/or small secrets. A new and interesting result from our analysis shows that for most cryptographic use cases a hybrid dual attack outperforms a standalone dual attack, regardless of the secret distribution. We formulate our results into a framework of predicting the performance of the hybrid dual attacks. We also present a few tricks that further improve our attack. To illustrate the effectiveness of our result, we re-evaluate the security of all LWE related proposals in round 3 of NIST’s post-quantum cryptography process, and improve the state-of-the-art cryptanalysis results by 2-15 bits, under the BKZ-core-SVP model.