Search

Low-complexity lattice reduction algorithms are generally not optimized for solving the shortest basis problem (SBP). We fill this blank by tweaking the recently introduced sequential reduction (SR). In a quest for developing a provable and low-complexity reduction algorithm under the SR framework, we propose to employ successive interference cancellation (SIC) as a subroutine inside SR, and the whole algorithm is referred to as SR-SIC. On the theoretical front, we prove that the upper bound on the basis length of SR-SIC is better than those of major Lenstra, Lenstra, and Lovasz (LLL) based variants when the dimension of the lattice basis is no larger than 4. In practice, we show by simulations that SR-SIC yields higher information rate than LLL when designing integer-forcing linear receivers, in which SR-SIC also enjoys lower computational complexity.

The lattice size of a lattice polytope P was defined and studied by Schicho, and Castryck and Cools. They provided an “onion skins” algorithm for computing the lattice size of a lattice polygon P in $$\mathbb R^2$$ based on passing successively to the convex hull of the interior lattice points of P. We explain the connection of the lattice size to the successive minima of $$K=(P+(-P))^*$$ and to the lattice reduction with respect to the general norm that corresponds to K. It follows that the generalized Gauss algorithm of Kaib and Schnorr (which is faster than the “onion skins” algorithm) computes the lattice size of any convex body in $$\mathbb R^2$$ . We extend the work of Kaib and Schnorr to dimension three, providing a fast algorithm for lattice reduction with respect to the general norm defined by a convex origin-symmetric body $$K\subset \mathbb R^3$$ . We also explain how to recover the successive minima of K and the lattice size of P from the obtained reduced basis and therefore provide a fast algorithm for computing the lattice size of any convex body $$P\subset \mathbb R^3$$ .

Lattice reduction (LR) techniques have been widely adopted to enhance the detection performance with low additional complexity in spatial multiplexed multiple-input multiple-output (MIMO) systems. However, in large MIMO systems, the required number of iterations and the corresponding latency and complexity of the existing LR algorithms increase exponentially. In this brief, we propose a low-latency LR method based on Seysen’s algorithm (SA) for high-dimensional MIMO systems. The proposed algorithm introduces dual-index selection and simultaneously updates two basis pairs without the recalculation of metrics to reduce the latency and complexity. Additionally, it introduces a reduced candidate set to decrease the computational complexity and memory usage. The numerical results demonstrate that the proposed LR-aided linear detector outperforms the conventional Lenstra-Lenstra-Lovasz algorithm. Furthermore, the performance of the proposed method is comparable to that of SA; it achieves reductions of 40% and 12.5% in the number of iterations and computational complexity, respectively. The proposed 65-nm CMOS implementation achieves an overall latency of 196 ns and a throughput of 25.5 M matrix/s with a clock frequency of 357.1 MHz for $8 \times 8$ MIMO systems.

Due to the continuous demand for higher bit rates, the management of the spatio-temporal intersymbol interference in frequency-selective multiple-input multiple-output (MIMO) channels becomes increasingly important. For single-input single-output channels, equalized precoded partial-response signaling is capable of handling a large amount of intersymbol interference, but, to date, no equalization scheme with general partial-response signaling has been presented for the frequency-selective MIMO channel. Not only does this contribution extend partial-response signaling to the MIMO channel by proposing a general spatio-temporal partial-response precoder, but it also develops a minimum mean-squared-error optimization framework in which the equalization coefficients and the spatio-temporal target response are jointly optimized. Three iterative optimization algorithms are discussed, which update (part of) a row of the target impulse response matrix in each iteration. In particular, the third algorithm reformulates this row optimization as a lattice decoding problem. Numerical simulations confirm that the general partial-response signaling clearly outperforms the traditional full-response signaling in terms of the mean squared error and the bit error rate. The third optimization algorithm has a better performance but a higher complexity, compared to the first and the second algorithm.

In recent years, the block Korkine-Zolotarev (BKZ) and its variants such as BKZ 2.0 have been used as de facto algorithms to estimate the security of a lattice-based cryptosystem. In 2017, DeepBKZ was proposed as a mathematical improvement of BKZ, which calls LLL with deep insertions (DeepLLL) as a subroutine alternative to LLL. DeepBKZ can find a short lattice vector by smaller blocksizes than BKZ. In this paper, we develop a self-dual variant of DeepBKZ, as in the work of Micciancio and Walter for self-dual BKZ. Like DeepBKZ, our self-dual DeepBKZ calls both DeepLLL and its dual variant as main subroutines in order to accelerate to find a very short lattice vector. We also report experimental results of DeepBKZ and our self-dual DeepBKZ for random bases on the Darmstadt SVP challenge.

Let [Formula: see text] be an RSA public key with private exponent [Formula: see text] where [Formula: see text] and [Formula: see text] are large primes of the same bit size. At Eurocrypt 96, Coppersmith presented a polynomial-time algorithm for finding small roots of univariate modular equations based on lattice reduction and then succussed to factorize the RSA modulus. Since then, a series of attacks on the key equation [Formula: see text] of RSA have been presented. In this paper, we show that many of such attacks can be unified in a single attack using a new notion called Coppersmith’s interval. We determine a Coppersmith’s interval for a given RSA public key [Formula: see text] The interval is valid for any variant of RSA, such as Multi-Prime RSA, that uses the key equation. Then we show that RSA is insecure if [Formula: see text] provided that we have approximation [Formula: see text] of [Formula: see text] with [Formula: see text] [Formula: see text] The attack is an extension of Coppersmith’s result.

As a non-linear precoding alternative to Tomlinson-Harashima precoding (THP), in this paper, so-called lattice reduction aided precoding (LRP) is considered as a crosstalk precompensation technique for downstream transmission in G.fast DSL networks. First, a practically achievable bit-rate expression for LRP is proposed in function of the precoder and integer matrix. The problem then consists of a joint precoder and integer matrix design in order to maximize the weighted sum-rate (WSR) under per-line power constraints. For a fixed integer matrix, zero-forcing (ZF) precoder matrix design simplifies to gain scaling optimization with complex gain scalars, for which a successive lower bound maximization method is presented. Additionally, it is established that the achievable ZF-LRP sum-rate is upper bounded by the achievable ZF-THP sum-rate at high SNR. For computing the optimal precoder matrix, on the other hand, an efficient method is developed by leveraging on the equivalence between the WSR maximization and the weighted sum of mean squared error (MSE) minimization, leading to a locally-optimal MMSE-LRP solution. Simulations with a measured G.fast cable binder are provided to compare the proposed LRP schemes with THP schemes.

In MIMO OFDM (Multiple Input Multiple Output Orthogonal Frequency Division Multiplexing) cellular systems with frequency reuse factor of unity, the cell edge users experience interference termed as Inter Cell Interference (ICI). ICI degrades the throughput of the cell, when many users exist at cell edges. ICI can be minimized by proper optimal decoding techniques like Maximum Likelihood Decoding (MLD) which is too complex and not possible to implement practically. Suboptimal decoders like sphere decoder is used to achieve the performance near to MLD with reduced complexity. The sphere decoder begins the search process by choosing a proper initial search radius. The paper proposes an optimal radius choice algorithm, to determine the initial search radius for sphere decoder based on system specifications like size of MIMO, modulation technique, Signal to Noise Ratio statistics. A Look Up Table is prepared based on these statistics. A combination of radius selection and radius updation with pre processing is considered. The pre processing methods named Lattice Reduction is used to convert Integer Least Square problem to simple polynomial. Radius is updated using Probabilistic Tree Pruning or Increasing Radius Algorithm. Simulations demonstrate that Increasing Radius Algorithm performs better at larger SNR regions i.e. above 5 dB and Reducing Radius Search algorithm at lower SNR. The initial radius considered from LUT is very efficient selection of search radius. It leads to reduced difference, between final radius and selected radius. This difference is less than 10% for both IRS-SD and RRS-SD, without degrading the performance.

This paper proposes a high-efficient preprocessing algorithm for $16\times 16$ MIMO detections. The proposed algorithm combines a sorting-relaxed QR decomposition (SRQRD) and a modified greedy LLL (MGLLL) algorithm. First, SRQRD is conducted to decompose the channel matrices. This decomposition adopts a relaxed sorting strategy together with a paralleled Givens Rotation (GR) array scheme, which can reduce the processing latency by 60% compared with conventional sorted QR decomposition (SQRD). Then, an MGLLL algorithm is conducted to improve detection performance further. The MGLLL algorithm adopts a paralleled selection criterion, and only process the most urgent iterations. Thus the processing latency and column swaps can be reduced by 50% and 75%, respectively, compared with the standard LLL algorithm. Finally, the bit-error-rate (BER) performance of this preprocessing algorithm is evaluated using two MIMO detectors. Results indicate that this preprocessor suffers a negligible performance degradation compared with the combination of the standard LLL algorithm and SQRD. Based on this preprocessing algorithm, a pipelined hardware architecture is also designed in this paper. A series of systolic coordinated-rotation-digital-computer (CORDIC) arrays are utilized, and highly-pipelined circuits are designed, helping this architecture achieve high frequency performance. This architecture is implemented using 65-nm CMOS technology, which can work at a maximum frequency of 625 MHz to process channel matrices every 16 clock cycles. The latency is 0.9 us. Comparisons indicate that this preprocessor outperforms other similar designs in terms of latency, throughput, and gate-efficiency.

Recently, the calculus of Formal Concept Analysis (FCA) in the fuzzy setting is prolonged in bipolar fuzzy space for precise analysis of fuzzy attributes. In this process it is addressed that the attributes like bald (or tadpole) or not bald (not tadpole) cannot be defined through a precise or sharp boundaries. To deal with them, some evidence to support (i.e. true t A membership-values) or reject (i.e. false f A membership-values) the attributes is required in the given boundary 0 ≤ t A + f A ≤ 1 . Hence, the proposed method tried to provide the mathematical algebra of vague concept lattice and its navigation at user defined granules with an illustrative example. In addition, the vague entropy measurement is also computed to validate the results.

The public parameters of the RSA cryptosystem are represented by the pair of integers N and e . In this work, first we show that if e satisfies the Diophantine equation of the form e x 2 − ϕ ( N ) y 2 = z for appropriate values of x , y and z under certain specified conditions, then one is able to factor N . That is, the unknown y x can be found amongst the convergents of e N via continued fractions algorithm. Consequently, Coppersmith’s theorem is applied to solve for prime factors p and q in polynomial time. We also report a second weakness that enabled us to factor k instances of RSA moduli simultaneously from the given ( N i , e i ) for i = 1 , 2 , ⋯ , k and a fixed x that fulfills the Diophantine equation e i x 2 − y i 2 ϕ ( N i ) = z i . This weakness was identified by solving the simultaneous Diophantine approximations using the lattice basis reduction technique. We note that this work extends the bound of insecure RSA decryption exponents.

This paper presents a new low complexity sphere decoding (SD) for the generalized spatial modulation (GSM). We introduce a pre-processing stage using the lattice reduction (LR) aided minimum mean squared error (MMSE) equalization in the GSM systems. This stage speeds up the search in the decoding tree and provides a lattice dependent (LD) initial choice of the radius. Moreover, we derive a lattice independent (LI) initial radius that guarantees the optimal performance at a high signal-to-noise ratio (SNR). We also propose an iterative method to increase the radius in order to achieve the maximum likelihood (ML) performance at all SNRs. We show that the proposed algorithm achieves the ML performance while requiring prominently less computational complexity (CC) than an exhaustive search. In addition, we analyze the CC of the resulting algorithm at high SNRs and we derive an analytical expression for the complexity. The simulation results demonstrate a noticeable decrease in the CC of the proposed sphere decoding algorithm in comparison with its counterparts, particularly at low SNRs.

Sampling from the lattice Gaussian distribution has emerged as an important problem in coding, decoding, and cryptography. In this paper, lattice reduction technique is adopted to Gibbs sampler for lattice Gaussian sampling. First, with respect to lattice Gaussian distribution, we show the convergence rate of systematic scan Gibbs sampling is characterized by the Hirschfeld-Gebelein-Renyi maximal correlation among the multivariate of being sampled. Then, Lattice-reduction-aided Gibbs algorithm is proposed to sample from an equivalent lattice Gaussian distribution but with less correlated multivariate, thus leading to a better Markov mixing. After that, we extend the proposed lattice-reduction-aided Gibbs sampling to lattice decoding, where the choice of the standard deviation for the sampling is fully investigated. A customized solution that suits for each specific decoding case by Euclidean distance is given, which results in a better tradeoff between Markov mixing and sampler decoding. Based on it, a startup mechanism is also proposed for Gibbs sampler decoding, where decoding complexity can be reduced without performance loss. Moreover, the recycling Gibbs sampling that exploits the potential of samples is also considered to improve the decoding performance in lattice decoding. Simulation results based on large-scale uncoded multiple-input multiple-output detection are presented to confirm the performance gain and complexity reduction.

In this paper, a very low complexity Lattice Reduction technique, called Dual Shortest Longest Vector algorithm (SLV), is adopted to improve the Bit Error Rate (BER) performance of the Minimum Mean Square Error (MMSE) detector in high-load Massive MIMO systems, whereby resulting in the so-called SLV-aided MMSE (MMSE–SLV) detector. An efficient combination scheme of Generalized Group Detection (GGD) algorithm and the MMSE–SLV, called MMSE–GGD–SLV, is further proposed to enhance BER performance of the system more significantly. In order to do so, we first convert the Group Detection approach to the generalized one (GGD) by creating an arbitrary number of sub-systems. Then, an additional operation, i.e., channel matrix sorting, is applied to the GGD to reduce the error propagation between sub-systems. To make the detection complexities of the MMSE–GGD–SLV detector more practical, the MMSE–SLV detection procedure is only applied to the first sub-system. Various BER performance simulations and complexity analysis show that both the MMSE–GGD–SLV and the MMSE–SLV detectors noticeably outperform their conventional MMSE counterpart, yet at the cost of higher detection complexities. However, their complexities are kept at acceptable levels, which are much lower than those of the conventional BLAST detector. Therefore, the proposed detectors are very good candidates for signal recovery in high load Massive MIMO systems.

Lattice basis reduction algorithms have been used in cryptanalysis. The most famous algorithm is LLL, proposed by Lenstra, Lenstra, Lovasz, and one of its typical improvements is LLL with deep insertions (DeepLLL). A DeepLLL-reduced basis is LLL-reduced, and hence its quality is at least as good as LLL. In practice, DeepLLL often outputs a more reduced basis than LLL, but no theoretical result is known. First, we show provable output quality of DeepLLL, strictly better than that of LLL. Second, as a main work of this paper, we propose a new variant of DeepLLL. The squared-sum of Gram–Schmidt lengths of a basis is related with the computational hardness of lattice problems such as the shortest vector problem (SVP). Given an input basis, our variant monotonically decreases the squared-sum by a given factor at every deep insertion. This guarantees that our variant runs in polynomial-time.

Generalized Frequency Division Multiplexing (GFDM) is a promising candidate waveform for the air interface of the Fifth Generation (5G) communication networks. The flexibility of GFDM enables it to meet different application requirements of future networks. Nevertheless, the combination of GFDM and Multiple-Input Multiple-Output (MIMO) systems using Spatial Multiplexing (SM) is a necessity to achieve high spectral efficiency. However, spatial demultiplexing using common SM detection algorithms becomes an even more challenging task due to the inherent self-interference of GFDM. In this paper, we investigate a class of Lattice-Reduction-Aided (LRA) signal detection algorithms that can achieve an attractive tradeoff between performance and complexity in MIMO–GFDM systems. Simulation results show that with less increase in complexity, LRA algorithms can greatly improve the performance of the classical linear detector.

Preprocessing is applied to certain lattice reduction algorithms such as block Korkine–Zolotarev (BKZ) variants to reduce the search time in the enumeration tree for a shortest vector. The most classical form of preprocessing the authors observe is with polynomial time Lenstra–Lenstra–Lovasz algorithm to work with a slow enumeration-based algorithm like BKZ. The trade-off between the preprocessing and the enumeration stages in the context of time complexity of the whole algorithm is not well studied and explored. The main goal of this study is to re-investigate the preprocessing approach presented by Chen and Nguyen and improve its performance through optimisation. They extend the numeral results published by Haque et al. in IET Inf. Secur. for larger block sizes and report a comparison.

Massive multiple-input multiple-output (MIMO) is playing a crucial role in the fifth generation (5G) and beyond 5G (B5G) communication systems. Unfortunately, the complexity of massive MIMO systems is tremendously increased when a large number of antennas and radio frequency chains (RF) are utilized. Therefore, a plethora of research efforts has been conducted to find the optimal precoding algorithm with lowest complexity. The main aim of this paper is to provide insights on such precoding algorithms to a generalist of wireless communications. The added value of this paper is that the classification of massive MIMO precoding algorithms is provided with easily distinguishable classes of precoding solutions. This paper covers linear precoding algorithms starting with precoders based on approximate matrix inversion methods such as the truncated polynomial expansion (TPE), the Neumann series approximation (NSA), the Newton iteration (NI), and the Chebyshev iteration (CI) algorithms. The paper also presents the fixed-point iteration-based linear precoding algorithms such as the Gauss-Seidel (GS) algorithm, the successive over relaxation (SOR) algorithm, the conjugate gradient (CG) algorithm, and the Jacobi iteration (JI) algorithm. In addition, the paper reviews the direct matrix decomposition based linear precoding algorithms such as the QR decomposition and Cholesky decomposition (CD). The non-linear precoders are also presented which include the dirty-paper coding (DPC), Tomlinson-Harashima (TH), vector perturbation (VP), and lattice reduction aided (LR) algorithms. Due to the necessity to deal with a high consuming power by the base station (BS) with a large number of antennas in massive MIMO systems, a special subsection is included to describe the characteristics of the peak-to-average power ratio precoding (PAPR) algorithms such as the constant envelope (CE) algorithm, approximate message passing (AMP), and quantized precoding (QP) algorithms. This paper also reviews the machine learning role in precoding techniques. Although many precoding techniques are essentially proposed for a small-scale MIMO, they have been exploited in massive MIMO networks. Therefore, this paper presents the application of small-scale MIMO precoding techniques for massive MIMO. This paper demonstrates the precoding schemes in promising multiple antenna technologies such as the cell-free massive MIMO (CF-M-MIMO), beam space massive MIMO, and intelligent reflecting surfaces (IRSs). In-depth discussion on the pros and cons, performance-complexity profile, and implementation solidity is provided. This paper also provides a discussion on the channel estimation and energy efficiency. This paper also presents potential future directions in massive MIMO precoding algorithms. This research has been financially supported in part by the Research Council (TRC) of the Sultanate of Oman (agreement No. TRC/BFP/ASU/01/2018) and in part by the Discovery Grant from the Natural Sciences and Engineering Research Council of Canada. Massive multiple-input multiple-output (MIMO) is playing a crucial role in the fifth generation (5G) and beyond 5G (B5G) communication systems. Unfortunately, the complexity of massive MIMO systems is tremendously increased when a large number of antennas and radio frequency chains (RF) are utilized. Therefore, a plethora of research efforts has been conducted to find the optimal precoding algorithm with lowest complexity. The main aim of this paper is to provide insights on such precoding algorithms to a generalist of wireless communications. The added value of this paper is that the classification of massive MIMO precoding algorithms is provided with easily distinguishable classes of precoding solutions. This paper covers linear precoding algorithms starting with precoders based on approximate matrix inversion methods such as the truncated polynomial expansion (TPE), the Neumann series approximation (NSA), the Newton iteration (NI), and the Chebyshev iteration (CI) algorithms. The paper also presents the fixed-point iteration-based linear precoding algorithms such as the Gauss-Seidel (GS) algorithm, the successive over relaxation (SOR) algorithm, the conjugate gradient (CG) algorithm, and the Jacobi iteration (JI) algorithm. In addition, the paper reviews the direct matrix decomposition based linear precoding algorithms such as the QR decomposition and Cholesky decomposition (CD). The non-linear precoders are also presented which include the dirty-paper coding (DPC), Tomlinson-Harashima (TH), vector perturbation (VP), and lattice reduction aided (LR) algorithms. Due to the necessity to deal with a high consuming power by the base station (BS) with a large number of antennas in massive MIMO systems, a special subsection is included to describe the characteristics of the peak-to-average power ratio precoding (PAPR) algorithms such as the constant envelope (CE) algorithm, approximate message passing (AMP), and quantized precoding (QP) algorithms. This paper also reviews the machine learning role in precoding techniques. Although many precoding techniques are essentially proposed for a small-scale MIMO, they have been exploited in massive MIMO networks. Therefore, this paper presents the application of small-scale MIMO precoding techniques for massive MIMO. This paper demonstrates the precoding schemes in promising multiple antenna technologies such as the cell-free massive MIMO (CF-M-MIMO), beam space massive MIMO, and intelligent reflecting surfaces (IRSs). In-depth discussion on the pros and cons, performance-complexity profile, and implementation solidity is provided. This paper also provides a discussion on the channel estimation and energy efficiency. This paper also presents potential future directions in massive MIMO precoding algorithms.

International audience; We consider four variants of the RSA cryptosystem with an RSA modulus N = pq where the public exponent e and the private exponent d satisfy an equation of the form ed − k (p^2 − 1)( q^2 − 1 )= 1. We show that, if the prime numbers p and q share most significant bits, that is, if the prime difference |p − q| is sufficiently small, then one can solve the equation for larger values of d, and factor the RSA modulus, which makes the systems insecure.

The escalating demand for higher data rate and to provide service to multiple users simultaneously has increased the challenge of efficient spectrum utilization. The two important technologies required in 5G is Mmwave and Massive MIMO to use the benefit of wider bandwidth of mmwave and to mitigate interference using Massive MIMO Technology. In this paper we compare the BER (Bit Error Rate) of different LR (Lattice Reduction) aided Massive MIMO detection technique at 28GHz frequency. We use the QR decomposition as a preprocessing step in the entire MIMO detector. LRA (Lattice Reduction Aided) detectors performance-complexity tradeoff factor δ, (δ=3/4). Scattering Channel Model is used with 100 numbers of scatterers. We employ the different MIMO configuration, modulation techniques, multiple number of users, single and multiple data stream per user to compare and analyze the BER (Bit Error Rate) results. The results are analyzed for Brun's algorithm, Lenstra Lenstra Lovasz (LLL) algorithm, Complex LLL(CLLL) algorithm, Fixed Complexity LLL (fc-LLL) Algorithm, Efficient LLL(ELLL) Algorithm, Possible Swap LLL Algorithm (PSLLL), Greedy LLL algorithm, and LLL-MMSE algorithm.

This paper presents the first 802.11ax compliant iterative detection and decoding (IDD) receiver that supports up to 4 $\times$ 4 1024-QAM MIMO detection in the open literature. Soft-input-soft-output (SISO) MIMO detection is implemented with a lattice reduction aided (LRA) K-best searcher and a max-log list demapper. A hardware-efficient IDD receiver is proposed to achieve the required packet-rate (PER) with a feasible latency. The extrinsic information transfer (EXIT) chart is utilized to reduce the number of iterations for IDD. Given the 802.11ax latency constraint, the performance, power, area (PPA) design space is explored to identify the optimal IDD receiver architecture. 50% of IDD inner iterations are reduced with only a 0.05dB loss in PER. The proposed IDD receiver achieves a 1dB improvement in PER with 3.6$\times$ smaller area and 3.0 $\times$ lower power consumption when compared to the best non-IDD receiver.

An adversary armed with a quantum computer has algorithms at their disposal, which are capable of breaking our current methods of encryption. Even with the birth of post-quantum cryptography, some of best cryptanalytic algorithms are still quantum. Lattice reduction algorithms require several arithmetic operations such as addition, multiplication, and division. Resource counts of quantum circuits determine the practicality of simulating an operation on a quantum computer. Each of the previous operations are constructed from a single addition circuit designed by Takahashi et al. and implemented in the open-source software framework for quantum computing, ProjectQ. We also include a novel approach to designing a circuit for dot product which can be used in Gram-Schmidt orthogonalization, an algorithm often found in lattice reduction. Tiepelt and Szenpieniec provide a quantum circuit for the Gram-Schmidt orthogonalization algorithm. We design modifications to their circuit to better suit the implemented arithmetic operation circuits. Resource estimations are then given for small-dimensional cases.

Quadratic form reduction and lattice reduction are fundamental tools in computational number theory and in computer science, especially in cryptography. The celebrated Lenstra-Lenstra-Lov\'asz reduction algorithm (so-called LLL) has been improved in many ways through the past decades and remains one of the central methods used for reducing integral lattice basis. In particular, its floating-point variants-where the rational arithmetic required by Gram-Schmidt orthogonalization is replaced by floating-point arithmetic-are now the fastest known. However, the systematic study of the reduction theory of real quadratic forms or, more generally, of real lattices is not widely represented in the literature. When the problem arises, the lattice is usually replaced by an integral approximation of (a multiple of) the original lattice, which is then reduced. While practically useful and proven in some special cases, this method doesn't offer any guarantee of success in general. In this work, we present an adaptive-precision version of a generalized LLL algorithm that covers this case in all generality. In particular, we replace floating-point arithmetic by Interval Arithmetic to certify the behavior of the algorithm. We conclude by giving a typical application of the result in algebraic number theory for the reduction of ideal lattices in number fields., Comment: 23 pages

The LLL basis reduction algorithm was the first polynomial-time algorithm to compute a reduced basis of a given lattice, and hence also a short vector in the lattice. It approximates an NP-hard problem where the approximation quality solely depends on the dimension of the lattice, but not the lattice itself. The algorithm has applications in number theory, computer algebra and cryptography. In this paper, we provide an implementation of the LLL algorithm. Both its soundness and its polynomial running-time have been verified using Isabelle/HOL. Our implementation is nearly as fast as an implementation in a commercial computer algebra system, and its efficiency can be further increased by connecting it with fast untrusted lattice reduction algorithms and certifying their output. We additionally integrate one application of LLL, namely a verified factorization algorithm for univariate integer polynomials which runs in polynomial time.

We give a lattice reduction algorithm that achieves root Hermite factor \(k^{1/(2k)}\) in time \(k^{k/8+o(k)}\) and polynomial memory. This improves on the previously best known enumeration-based algorithms which achieve the same quality, but in time \(k^{k/(2e) + o(k)}\). A cost of \(k^{k/8 + o(k)}\) was previously mentioned as potentially achievable (Hanrot-Stehle’10) or as a heuristic lower bound (Nguyen’10) for enumeration algorithms. We prove the complexity and quality of our algorithm under a heuristic assumption and provide empirical evidence from simulation and implementation experiments attesting to its performance for practical and cryptographic parameter sizes. Our work also suggests potential avenues for achieving costs below \(k^{k/8 + o(k)}\) for the same root Hermite factor, based on the geometry of SDBKZ-reduced bases.

Lattice-based encryption schemes are often subject to the possibility of decryption failures, in which valid encryptions are decrypted incorrectly. Such failures, in large number, leak information about the secret key, enabling an attack strategy alternative to pure lattice reduction. Extending the “failure boosting” technique of D’Anvers et al. in PKC 2019, we propose an approach that we call “directional failure boosting” that uses previously found “failing ciphertexts” to accelerate the search for new ones. We analyse in detail the case where the lattice is defined over polynomial ring modules quotiented by \(\langle X^{N} + 1 \rangle \) and demonstrate it on a simple Mod-LWE-based scheme parametrized a la Kyber768/Saber. We show that for a given secret key (single-target setting), the cost of searching for additional failing ciphertexts after one or more have already been found, can be sped up dramatically. We thus demonstrate that, in this single-target model, these schemes should be designed so that it is hard to even obtain one decryption failure. Besides, in a wider security model where there are many target secret keys (multi-target setting), our attack greatly improves over the state of the art.

Lattice reduction is a popular preprocessing strategy in multiple-input multiple-output (MIMO) detection. In a quest for developing a low-complexity reduction algorithm for large-scale problems, this paper investigates a new framework called sequential reduction (SR), which aims to reduce the lengths of all basis vectors. The performance upper bounds of the strongest reduction in SR are given when the lattice dimension is no larger than 4. The proposed new framework enables the implementation of a hash-based low-complexity lattice reduction algorithm, which becomes especially tempting when applied to large-scale MIMO detection. Simulation results show that, compared to other reduction algorithms, the hash-based SR algorithm exhibits the lowest complexity while maintaining comparable error performance., Sequential reduction is not in the LLL family, but is generalizing greedy reduction (Nguyen and Stehle) and element-based reduction (Zhou and Ma)

Integer-forcing (IF) precoding is an alternative to linear precoding for multi-user (MU) multiple-input-multiple-output (MIMO) channels, with the potential to offer superior performance at a similar complexity. In this letter, a low-complexity suboptimal method is proposed to optimize the parameters of an IF scheme for any number of $K$ users. The proposed method involves solving a relaxation of the problem followed by the application of a lattice reduction algorithm and is shown to have an overall complexity of $\mathcal{O}(K^3)$. Simulation results show that the proposed method achieves a higher sum rate than a heuristic choice of parameters and significantly outperforms conventional linear precoding in all simulated scenarios., 13 pages, 4 figures, to appear in IEEE Wireless Communications Letters (WCL)

Lattice reduction (LR) has been extensively studied for data detection in uplink transmission. In this letter, we present a novel class of iterative LR algorithms in precoded downlink transmission. A unified framework is developed for this purpose, to reduce the precoder maximum row norm by iteratively minimizing the weighted sum of the precoder row-norms. We show that the resulting objective function can be minimized using the rounding-off technique or the sphere encoding (SE), traditionally used to determine the vector perturbation (VP) in downstream transmission. Different combinations of LR and VP techniques are investigated to assess their performance tradeoffs. Simulation results reveal that the proposed iterative SE-based LR outperforms the state-of-the-art Lenstra–Lenstra–Lovasz and Seysen algorithms. In addition, the proposed algorithm shifts the computational complexity from the costly per-symbol VP computation to the per-channel-realization precoder reduction, which is beneficial in slowly varying channels.

In Formal Concept Analysis (FCA), a concept lattice graphically portrays the underlying relationships between the objects and attributes of an information system. One of the key complexity problems of concept lattices lies in extracting the useful information. The unorganized nature of attributes in huge contexts often does not yield an informative lattice in FCA. Moreover, understanding the collective relationships between attributes and objects in a larger many valued context is more complicated. In this paper, we introduce a novel approach for deducing a smaller and meaningful concept lattice from which excerpts of concepts can be inferred. In existing attribute-based concept lattice reduction methods for FCA, mostly either the attribute size or the context size is reduced. Our approach involves in organizing the attributes into clusters using their structural similarities and dissimilarities, which is commonly known as attribute clustering, to produce a derived context. We have observed that the deduced concept lattice inherits the structural relationship of the original one. Furthermore, we have mathematically proved that a unique surjective inclusion mapping from the original lattice to the deduced one exists.

As a branch of sphere decoding, the K -best method has played an important role in detection in large-scale multiple-input-multiple-output (MIMO) systems. However, as the numbers of users and antennas grow, the preprocessing complexity increases significantly, which is one of the major issues with the K -best method. To address this problem, this paper proposes a preprocessing algorithm combining Cholesky sorted QR decomposition and partial iterative lattice reduction (CHOSLAR) for K -best detection in a 64-quadrature amplitude modulation (QAM) 16 $\times$ 16 MIMO system. First, Cholesky decomposition is conducted to perform sorted QR decomposition. Compared with conventional sorted QR decomposition, this method reduces the number of multiplications by 25.1% and increases parallelism. Then, a constant-throughput partial iterative lattice reduction method is adopted to achieve near-optimal detection accuracy. This method further increases parallelism, reduces the number of matrix swaps by 45.5%, and reduces the number of multiplications by 67.3%. Finally, a sorting-reduced K -best strategy is used for vector estimation, thereby, reducing the number of comparators by 84.7%. This method suffers an accuracy loss of only approximately 1.44 dB compared with maximum likelihood detection. Based on CHOSLAR, this paper proposes a fully pipelined very-large-scale-integration architecture. A series of different systolic arrays and parallel processing units achieves an optimal tradeoff among throughput, area consumption, and power consumption. This architectural layout is obtained via TSMC 65-nm 1P9M CMOS technology, and throughput metrics of 1.40 Gbps/W (throughput/power) and 0.62 Mbps/kG (throughput/area) are achieved, demonstrating that the proposed system is much more efficient than state-of-the-art designs.

A new low complexity lattice reduction algorithm was proposed, namely, the sorted integer Gauss transformation (SIGT). The SIGT algorithm can be interpreted as minimizing the longest basis vector first and assure that there was no integer projection between any two basis vectors. By applying simulation over Rayleigh fading channels, it was demonstrated that the proposed SIGT algorithm can have almost the same bit error rate (BER) performance as the LLL algorithm, while the SIGT algorithm requires only about half iteration as the LLL algorithm and the running time of each iteration for both algorithms were similar to each other. It is concluded that the SIGT algorithm can achieve almost the bit error rate (BER) performance, while the SIGT requires fewer iterations than the LLL.

In this paper, we investigate the transceiver design for multiple-input multiple-output visible light communication (VLC) systems that employ the integer-forcing (IF) lattice decoding technique. To facilitate the joint design of the transmitter precoder, the integer matrix and the receiver equalizer, we first give a necessary and sufficient condition for the integer matrix to be invertible over 1-D lattice. Based on this condition, we then propose a new method for choosing the integer matrix which achieves better performance than the existing lattice reduction method. Moreover, taking into account two typical constraints in VLC, we optimize transmit and receive matrices using the conditional gradient method or the projected gradient method. Finally, the integer matrix and the transmit and receive matrices are jointly optimized in an iterative manner. Simulation results are provided to demonstrate the performance improvement achieved by the proposed framework.

There exist two issues among popular lattice reduction (LR) algorithms that should cause our concern. The first one is Korkine-Zolotarev (KZ) and Lenstra-Lenstra-Lovasz (LLL) algorithms may increase the lengths of basis vectors. The other is KZ reduction suffers much worse performance than Minkowski reduction in terms of providing short basis vectors, despite its superior theoretical upper bounds. To address these limitations, we improve the size reduction steps in KZ and LLL to set up two new efficient algorithms, referred to as boosted KZ and LLL, for solving the shortest basis problem (SBP) with exponential and polynomial complexity, respectively. Both of them offer better actual performance than their classic counterparts, and the performance bounds for KZ are also improved. We apply them to designing integer-forcing (IF) linear receivers for multi-input multi-output (MIMO) communications. Our simulations confirm their rate and complexity advantages., MATLAB codes are available in: https://codeocean.com/2017/06/22/boosted-korkine-zolotarev-lpar-kz-rpar-and-lenstra-ndash-lenstra-ndash-lov%C3%A1sz-lpar-lll-rpar-algorithms/code

The LLL lattice reduction has been widely used to decrease the bit error rate (BER) of the Babai point, but its running time varies much from matrix to matrix. To address this problem, some fixed-complexity LLL reductions (FCLLL) have been proposed. In this letter, we propose two greedy selection-based FCLLL algorithms: GfcLLL(1) and GfcLLL(2). Simulations show that both of them give Babai points with lower BER in similar or much shorter CPU time than existing ones.

Independent methodology for analysis of concept lattice reduction.We use sets of proper implications holding in the original and reduced structure.Highlight the kinds of changes propitiated by the different classes of techniques.Four reduction techniques were used to illustrate the proposed methodology. Formal concept analysis (FCA) is a mathematical theory of data analysis with applications in many areas. The problem of obtaining a concept lattice of an appropriate size was identified in several applications as one of the most important problems of FCA. In order to deal with this problem several techniques with different characteristics were proposed for concept lattice reduction. However, there are currently no adequate methods to assess what types of knowledge transformations can result from a reduction. A methodology for analysis of concept lattice reduction is presented here. It is based on the use of sets of proper implications holding in the original and reduced formal contexts or concept lattices. Working with both sets of implications, the methodology is able to show what is preserved, eliminated, inserted or transformed by a reduction technique. Three classes of reduction techniques are analyzed from the standpoint of the methodology in order to highlight techniques of each class have in common with respect to the transformations performed. Such analysis is followed by specific examples in each class.

Register synthesis for multi-sequences has significance for the security of word-oriented stream ciphers. Feedback with carry shift registers (FCSRs) are promising alternatives to linear feedback shift registers for the design of stream ciphers. In this paper, we solve the FCSR synthesis problem for multi-sequences by two rational approximation algorithms using lattice theory. One is based on the lattice reduction greedy algorithm proposed by Nguyen and Stehle (ACM Trans Algorithms (TALG) 5(4):46, 2009). The other is based on the LLL algorithm which is a polynomial time lattice reduction algorithm. Both of these rational approximation algorithms can find the smallest common FCSR for a given multi-sequence but with different numbers of known terms. When the number of sequences within the multi-sequence is less than or equal to 3, the former is suggested because it has better time complexity and fewer terms are needed. Otherwise, the latter will have better time complexity.

Recently, lattice reduction (LR)-aided linear detectors (LDs) are shown to be very effective in multi-input–multi-output systems for low-complexity and small bit-error-rate (BER) performance. However, the LR algorithms in the previous LR-aided LDs mainly aim to improve the orthogonality of the channel matrix where only channel state information is used. In this study, the authors design a novel LR algorithm to enhance the BER performance of the LR-aided LDs. Unlike the previous LR algorithms, the proposed LR algorithm aims to decrease the modified Euclidean distance (MED) in the LR-aided LDs, whereas the MED utilises the received signal as well as the channel matrix. Note that the MED is directly related to the BER performance of the LR-aided LDs, thus decreasing the MED in the LR-aided LDs can help to reduce the BER of the LR-aided LDs. In the proposed LR algorithm, the partial column addition operation is used. The simulation results indicate that their LR-aided LDs exhibit smaller BER than the previous LR-aided LDs. Moreover, the computational complexity is also shown in the simulation results.

In this paper, we propose a list detection scheme for the uplink scenario of multiuser multiple-input–multiple-output (MU-MIMO) systems. The proposed technique employs a single lattice reduction (LR) transformation to modify the channel matrix between the users and the base station, which produces a new nearly orthogonal channel matrix and allows for a more efficient detection. After the LR transformation, a reliable candidate for the transmitted signal vector, which is provided by successive interference cancelation detection with a cancelation ordering strategy based on the mean square error in the LR domain, is obtained. An algorithm to decide if the current candidate has good quality or if it is necessary to further explore different orderings to improve the estimation quality is employed. The proposed algorithm sets a minimum number of candidates to be tested and employs a stopping criterion to keep the number of candidates from growing excessively. Simulation results indicate that the proposed variable list detection (VLD) scheme has a near-optimal performance while keeping its computational complexity well below that of the maximum-likelihood detector. An iterative detection and decoding scheme based on the VLD algorithm is also developed, producing an excellent performance that approaches the single-user scenario.

Based on the V-BLAST zero-padded block transmission scheme in the frequency-selective multiple-input multiple-output channels, we propose a two-stage lattice-reduction (LR)-aided decoder and prove analytically that it can achieve the maximum diversity gain, which is equal to the product of the number of receive-antennas and the number of multipath channel taps. In the proposed decoding method, at first, we decouple the detection problem into several reduced-size detection problems and perform the lattice reduction algorithm for the decoupled blocks. Then, by choosing a proper threshold, a clustering algorithm divides the blocks into the maximum two clusters. We prove that the corresponding blocks of the first cluster achieve the full diversity through their linear equalization. For the remainder of the blocks, based on the entire observations of the second cluster, we propose an LR-aided detection method, which decodes the information symbols in this cluster with full diversity. Our proposed two-stage LR-aided algorithm performs better than the conventional LR-aided detection in terms of both the decoding computational complexity and the error probability. Additionally, we prove analytically that at high signal-to-noise ratio, the decoding complexity of the proposed decoder is equal to that of decoding the first cluster.

Neighborhood search algorithms have been proposed for detection in large multiple-input multiple-output systems. They iteratively search for the best vector in a fixed neighborhood. A better way could be to look for an update which is not restricted to a fixed neighborhood. Motivated by this, we formulate a problem to maximize the reduction in maximum likelihood (ML) cost and use it to derive an expression for updating the current solution. Using this update and a likelihood function regarding the locations of errors, we propose an unconstrained likelihood ascent search (ULAS) algorithm. ULAS seeks to provide the maximum reduction in ML cost by finding an update which is not restricted to be in a fixed neighborhood. Using simulations, the proposed algorithm has been shown to provide better error performance for uncoded systems than existing algorithms, at lower complexity. We also show that ULAS is amenable to lattice reduction, which helps in obtaining two variants leading to further improvements in performance.

Lattice problems are considered as the key elements in many areas of computer science as well as in cryptography; the most important of which is the shortest vector problem and its approximate variants. Algorithms for this problem are known as lattice reduction algorithms. Currently, the most practical lattice reduction algorithm for such problems is the block Korkine–Zolotarev (BKZ) algorithm and its variants. The authors optimise both the pruning and the preprocessing parameters of the recursive (aborted, extreme pruned) preprocessing of the BKZ lattice reduction algorithm and improve the results from Asiacrypt'11 by Chen and Nguyen. The authors derive approximate closed-form complexity formulas (based on the sandpile model assumption model by Hanrot et al.) for the enumeration time which allow a simple estimation of complexity without running the simulation algorithm (by Chen and Nguyen) and asymptotically suggests a modified extreme pruning bounding profiles with different parameters. Hence, the authors’ contributions are in optimising and improving the analysis of the complexity upper bound estimates presented by Chen and Nguyen, based on the same recursive-BKZ preprocessing model.

Spread spectrum communication is a typical scheme for covert communication because of its low detectability and antijam characteristic. However, the associated design concerns multiple factors, such as cochannel multiple access interference (MAI) and spread spectrum gain. In this paper, the lattice reduction theory is applied to MAI cancellation of spread spectrum communication and a novel lattice reduction aided multiple user detection method is proposed. The near maximum likelihood (ML) performance of MAI resistance is verified by simulation and theoretical analysis. The superiority of detection performance in strong MAI scenarios is especially addressed. Based on the algorithm, a collaborative covert communication system design is proposed. Low-power covert signals can be transmitted at a higher bit rate with the same coverage as more high-power cochannel signals. The covert transmission performance can be improved significantly compared to traditional designs.

In recent years, the output of formal concept analysis has been widely spread in various research fields for knowledge processing tasks. In this process, a major issues arises when large number of formal concepts are generated from the given context. Available approaches lacks in user required dynamic reduction of concept lattice based on shape and size of the given problem. To overcome this problem, the current paper proposes a method to control the size of concept lattice based on user defined subset of attributes (or objects). Further the proposed method provides a way to select some of the important concepts generated from chosen subset of attributes. For this purpose properties of Shannon entropy is utilized by the proposed method to select some of the important concepts at different granulation of their computed weight. The analysis derived from the proposed method is also compared with recently published granulation tree method with an empirical analysis.

In this paper, we propose a lattice reduction algorithm for use with NTRU lattices. Given an NTRU lattice as its input, the algorithm computes an LLL-reduced basis. The proposed lattice reduction algorithm is more efficient than the classical LLL algorithm. Recently, a lattice reduction algorithm for ideal lattices, named iLLL, was proposed by Plantard, Susilo, and Zhang. This algorithm is identical to that of the LLL except for the fact that it contains an additional subroutine, named Reuse . The subroutine serves to further reduce a set of short vectors that has already been computed by the algorithm prior to its initiation. As a result, the iLLL is able to output an LLL-reduced basis more efficiently than the LLL is able to do so. However, the iLLL cannot be directly applied to an NTRU lattice, because it is not an ideal lattice. Yet, from the fact that an NTRU lattice is also a module lattice (a generalization of an ideal lattice), we can adapt the main idea behind the iLLL blockwisely in our approach to NTRU lattices. We demonstrate that the proposed algorithm (containing a modified version of the aforementioned subroutine Reuse ) is asymptotically n 2 times faster at outputting an LLL-reduced basis than the LLL when applied to NTRU lattices of dimension n . In the case of small n , our experiments show that the proposed algorithm is slightly faster at outputting an LLL-reduced basis than the LLL. In addition, we present an example of how to recover a private key of an NTRU encryption scheme by using the proposed algorithm in the case of n = 22 .