The performance and complexity of two complex lattice reduction (LR) algorithms used in multiple input-multiple output (MIMO) detection are compared in this paper. The Seysen's algorithm (SA) has been previously p...
详细信息
ISBN:
(纸本)9781424414833
The performance and complexity of two complex lattice reduction (LR) algorithms used in multiple input-multiple output (MIMO) detection are compared in this paper. The Seysen's algorithm (SA) has been previously proposed as a low-complexity alternative to the real version of the Lenstra-Lenstra-Lovasz (lll) algorithm while providing a better performance in LR-aided linear detectors. However, this paper shows that the SA has a higher complexity than the complex version of the lll algorithm, due to its more computationally intensive preprocessing stage and its higher complexity per iteration. In addition, both the SA and the complex lll algorithm provide practically the same performance when used in LR-aided successive interference cancellation (SIC) detectors.
We prove an algebraic analogue of Pataki-Tural lemma (Pataki-Tural, arXiv:0804.4014, 2008) - the main tool in analysing the so-called overstretched regime of NTRU. Our result generalizes this lemma from Euclidean latt...
详细信息
ISBN:
(纸本)9783031643804;9783031643811
We prove an algebraic analogue of Pataki-Tural lemma (Pataki-Tural, arXiv:0804.4014, 2008) - the main tool in analysing the so-called overstretched regime of NTRU. Our result generalizes this lemma from Euclidean lattices to modules over any number field enabling us to look at NTRU as rank-2 module over cyclotomic number fields with a rank-1 dense submodule generated by the NTRU secret key. For Euclidean lattices, this overstretched regime occurs for large moduli q and enables to detect a dense sublattice in NTRU lattices leading to faster NTRU key recovery. We formulate an algebraic version of this event, the so-called Dense Submodule Discovery (DSD) event, and heuristically predict under which conditions this event happens. For that, we formulate an algebraic version of the Geometric Series Assumption an heuristic tool that describes the behaviour of algebraic lattice reduction algorithms. We verify this assumption by implementing an algebraic lll - an analog of classical lll lattice reduction that operates on the module level. Our experiments verify the introduced heuristic, enabling us to predict the algebraic DSD event.
Let N = pq be an RSA modulus where p, q are large primes of the same bitsize and phi(N) = (p - 1) (q - 1). We study the class of the public exponents e for which there exist integers X, Y, Z satisfying eX + phi(N)Upsi...
详细信息
Let N = pq be an RSA modulus where p, q are large primes of the same bitsize and phi(N) = (p - 1) (q - 1). We study the class of the public exponents e for which there exist integers X, Y, Z satisfying eX + phi(N)Upsilon = NZ, with vertical bar XY vertical bar < root 2/6 N-1/2 and all prime factors of vertical bar Y vertical bar are less than 10(40). We show that these exponents are of improper use in RSA cryptosystems and that their number is at least O(N-1/2) where epsilon is a small positive constant. Our method combines continued fractions, Coppersmith's lattice-based technique for finding small roots of bivariate polynomials and H. W. Lenstra's elliptic curve method (ECM) for factoring.
In this paper, we propose a new column swapping traverse Lenstra-Lenstra-Lovasz algorithm (lll) for low-complexity lattice reduction aided multiple-input multiple-output (MIMO) detection. The original lll algorithm pe...
详细信息
ISBN:
(纸本)9781509025978
In this paper, we propose a new column swapping traverse Lenstra-Lenstra-Lovasz algorithm (lll) for low-complexity lattice reduction aided multiple-input multiple-output (MIMO) detection. The original lll algorithm performs a swapping with an adjacent column progressively when it doesn't satisfy Lovasz condition. However, this algorithm has a trouble in hardware implementation because its complexity and run-time are variable. This correspondence proposes the modified lll algorithm which performs a swapping only with the column apart from predefined number of leaping. In the case of the modified column swapping traverse, it clearly decreases the number of iterations and execution time especially for the worst-case situations. Simulation result shows that the proposed lll algorithm aided MIMO detection achieves more reduced complexity while maintaining similar performance compared to the original algorithm for hardware implementation.
For RSA, May showed a deterministic polynomial time equivalence of computing d to factoring N(= pq). On the other hand, Takagi showed a variant of RSA such that the decryption algorithm is faster than the standard RSA...
详细信息
ISBN:
(纸本)9783540716761
For RSA, May showed a deterministic polynomial time equivalence of computing d to factoring N(= pq). On the other hand, Takagi showed a variant of RSA such that the decryption algorithm is faster than the standard RSA, where N = p(r)q while ed = 1 mod (p - 1) (q - 1). In this paper, we show that a deterministic polynomial time equivalence also holds in this variant. The coefficient matrix T to which lll algorithm is applied is no longer lower triangular, and hence we develop a new technique to overcome this problem.
Lattice reduction is an effective technique for improving the performance of MIMO data detection, in this paper, we analyze lattice reduction processing on the basis lattice and the dual lattice for MIMO detection and...
详细信息
ISBN:
(纸本)9781424458981
Lattice reduction is an effective technique for improving the performance of MIMO data detection, in this paper, we analyze lattice reduction processing on the basis lattice and the dual lattice for MIMO detection and investigate the parameters which affect the complexity of the lll algorithm. Through use of the dual lattice in the lll algorithm, the BER performances are improved about 2.2dB at BER=10(-5) for the 8x8 MIMO system compared to the lll algorithm. We demonstrate the dual lattice as the reduced lattice can diminish the effect of noise with low complexity.
In this paper we construct the multi-dimensional p-adic approximation lattices by using simultaneous approximation problems (SAP) of p-adic numbers and we estimate the l(infinity) norm of the p-adic SAP solutions theo...
详细信息
In this paper we construct the multi-dimensional p-adic approximation lattices by using simultaneous approximation problems (SAP) of p-adic numbers and we estimate the l(infinity) norm of the p-adic SAP solutions theoretically by applying Dirichlet's principle and numerically by using the lll algorithm. By using the SAP solutions as private keys, the security of which depends on NP-hardness of SAP or the shortest vector problems (SVP) of p-adic lattices, we propose a p-adic knapsack cryptosystem with commitment schemes, in which the sender Alice prepares ciphertexts and the verification keys in her p-adic numberland.
This paper proposes an improved lattice-reduction aided (LRA) MMSE detection with successive interference cancellation (SIC) using both the forward and the backward (F&B) reduction lll algorithms. We also apply a ...
详细信息
ISBN:
(纸本)9781424426805
This paper proposes an improved lattice-reduction aided (LRA) MMSE detection with successive interference cancellation (SIC) using both the forward and the backward (F&B) reduction lll algorithms. We also apply a simple list detection to the F&B-LRA MMSE with SIC. The proposed detector provides good BER performance relatively close to that with the ML detection for both QPSK and 16QAM in the 8x8 MIMO system.
This paper proposes an improved lattice-reduction aided (LRA) MMSE detection based on the Gram-Schmidt orthogonalization. With the proposed detection, much reliable estimate can be achieved, compared to the convention...
详细信息
ISBN:
(纸本)9781424426805
This paper proposes an improved lattice-reduction aided (LRA) MMSE detection based on the Gram-Schmidt orthogonalization. With the proposed detection, much reliable estimate can be achieved, compared to the conventional LRA detection. The BERs are much closer to those with the ML detection in the 4x4 MIMO and the 8x8 MIMO systems.
Lattice reduction aided (LRA) detection with the lll algorithm has been investigated to achieve the MIMO channel capacity with low computational complexity. This paper proposes an improved LRA-MMSE detection using the...
详细信息
ISBN:
(纸本)9781424426430
Lattice reduction aided (LRA) detection with the lll algorithm has been investigated to achieve the MIMO channel capacity with low computational complexity. This paper proposes an improved LRA-MMSE detection using the forward and the backward reduction lll algorithms for the 8x8 MIMO to obtain more reliable estimates of the transmitted signals. The proposed method achieved much better BERs than the conventional LRA detection. The transmit signal energy could be saved about 3.5dB at BER=10(-5), and the BER slope became much steeper, which is almost the same as that with the maximum likelihood detection.
暂无评论