150 results found
Stern S, Ling C, Fischer RFH, 2022, Algorithms and bounds for complex and quaternionic lattices with application to MIMO transmission, IEEE Transactions on Information Theory, Vol: 68, Pages: 4491-4517, ISSN: 0018-9448
Lattices are a popular field of study in mathematical research, but also in more practical areas like cryptology or multiple-input/multiple-output (MIMO) transmission. In mathematical theory, most often lattices over real numbers are considered. However, in communications, complex-valued processing is usually of interest. Besides, by the use of dual-polarized transmission as well as by the combination of two time slots or frequencies, four-dimensional (quaternion-valued) approaches become more and more important. Hence, to account for this fact, well-known lattice algorithms and related concepts are generalized in this work. To this end, a brief review of complex arithmetic, including the sets of Gaussian and Eisenstein integers, and an introduction to quaternion-valued numbers, including the sets of Lipschitz and Hurwitz integers, are given. On that basis, generalized variants of two important algorithms are derived: first, of the polynomial-time LLL algorithm, resulting in a reduced basis of a lattice by performing a special variant of the Euclidean algorithm defined for matrices, and second, of an algorithm to calculate the successive minima—the norms of the shortest independent vectors of a lattice—and its related lattice points. Generalized bounds for the quality of the particular results are established and the asymptotic complexities of the algorithms are assessed. These findings are extensively compared to conventional real-valued processing. It is shown that the generalized approaches outperform their real-valued counterparts in complexity and/or quality aspects. Moreover, the application of the generalized algorithms to MIMO communications is studied, particularly in the field of lattice-reduction-aided and integer-forcing equalization.
Joseph D, Martinez AJ, Ling C, et al., 2022, Quantum mean-value approximator for hard integer-value problems, PHYSICAL REVIEW A, Vol: 105, ISSN: 2469-9926
Mital N, Ling C, Gunduz D, 2022, Secure distributed matrix computation with discrete fourier transform, IEEE Transactions on Information Theory, Vol: 68, Pages: 1-1, ISSN: 0018-9448
We consider the problem of secure distributed matrix computation (SDMC), where a user queries a function of data matrices generated at distributed source nodes. We assume the availability of N honest but curious computation servers, which are connected to the sources, the user, and each other through orthogonal and reliable communication links. Our goal is to minimize the amount of data that must be transmitted from the sources to the servers, called the upload cost, while guaranteeing that no T colluding servers can learn any information about the source matrices, and the user cannot learn any information beyond the computation result. We first focus on secure distributed matrix multiplication (SDMM), considering two matrices, and propose a novel polynomial coding scheme using the properties of finite field discrete Fourier transform, which achieves an upload cost significantly lower than the existing results in the literature. We then generalize the proposed scheme to include straggler mitigation, and to the multiplication of multiple matrices while keeping the input matrices, the intermediate computation results, as well as the final result secure against any T colluding servers. We also consider a special case, called computation with own data, where the data matrices used for computation belong to the user. In this case, we drop the security requirement against the user, and show that the proposed scheme achieves the minimal upload cost. We then propose methods for performing other common matrix computations securely on distributed servers, including changing the parameters of secret sharing, matrix transpose, matrix exponentiation, solving a linear system, and matrix inversion, which are then used to show how arbitrary matrix polynomials can be computed securely on distributed servers using the proposed procedure
Wang J, Ling C, 2021, How to construct polar codes for ring-LWE-based public key encryption., Entropy (Basel, Switzerland), Vol: 23, Pages: 1-24, ISSN: 1099-4300
There exists a natural trade-off in public key encryption (PKE) schemes based on ring learning with errors (RLWE), namely: we would like a wider error distribution to increase the security, but it comes at the cost of an increased decryption failure rate (DFR). A straightforward solution to this problem is the error-correcting code, which is commonly used in communication systems and already appears in some RLWE-based proposals. However, applying error-correcting codes to those cryptographic schemes is far from simply installing an add-on. Firstly, the residue error term derived by decryption has correlated coefficients, whereas most prevalent error-correcting codes with remarkable error tolerance assume the channel noise to be independent and memoryless. This explains why only simple error-correcting methods are used in existing RLWE-based PKE schemes. Secondly, the residue error term has correlated coefficients leaving accurate DFR estimation challenging even for uncoded plaintext. It can be found in the literature that a tighter DFR estimation can effectively create a DFR margin. Thirdly, most error-correcting codes are not well designed for safety considerations, e.g., syndrome decoding has a nonconstant time nature. A code good at error correcting might be weak under a variety of attacks. In this work, we propose a polar coding scheme for RLWE-based PKE. A relaxed "independence" assumption is used to derive an uncorrelated residue noise term, and a wireless communication strategy, outage, is used to construct polar codes. Furthermore, some knowledge about the residue noise is exploited to improve the decoding performance. With the parameterization of NewHope Round 2, the proposed scheme creates a considerable DRF margin, which gives a competitive security improvement compared to state-of-the-art benchmarks. Specifically, the security is improved by 28.8%, while a DFR of 2-149 is achieved a for code rate pf 0.25, n=1024,q= 12,289, and binomial paramete
Wang Z, Liu L, Ling C, 2021, Sliced lattice Gaussian sampling: convergence improvement and decoding optimization, IEEE Transactions on Wireless Communications, Vol: 69, Pages: 2599-2612, ISSN: 1536-1276
Sampling from the lattice Gaussian distribution has emerged as a key problem in coding and decoding while Markov chain Monte Carlo (MCMC) methods from statistics offer an effective way to solve it. In this paper, the sliced lattice Gaussian sampling algorithm is proposed to further improve the convergence performance of the Markov chain targeting at lattice Gaussian sampling. We demonstrate that the Markov chain arising from it is uniformly ergodic, namely, it converges exponentially fast to the stationary distribution. Meanwhile, the convergence rate of the underlying Markov chain is also investigated, and we show the proposed sliced sampling algorithm entails a better convergence performance than the independent Metropolis-Hastings-Klein (IMHK) sampling algorithm. On the other hand, the decoding performance based on the proposed sampling algorithm is analyzed, where the optimization with respect to the standard deviation σ>0 of the target lattice Gaussian distribution is given. After that, a judicious mechanism based on distance judgement and dynamic updating for choosing σ is proposed for a better decoding performance. Finally, simulation results based on multiple-input multiple-output (MIMO) detection are presented to confirm the performance gain by the convergence enhancement and the parameter optimization.
Joseph D, Callison A, Ling C, et al., 2021, Two quantum Ising algorithms for the shortest-vector problem, Physical Review A: Atomic, Molecular and Optical Physics, Vol: 103, Pages: 1-12, ISSN: 1050-2947
Quantum computers are expected to break today's public key cryptography within a few decades. New cryptosystems are being designed and standardized for the postquantum era, and a significant proportion of these rely on the hardness of problems like the shortest-vector problem to a quantum adversary. In this paper we describe two variants of a quantum Ising algorithm to solve this problem. One variant is spatially efficient, requiring only O(Nlog2N) qubits, where N is the lattice dimension, while the other variant is more robust to noise. Analysis of the algorithms' performance on a quantum annealer and in numerical simulations shows that the more qubit-efficient variant will outperform in the long run, while the other variant is more suitable for near-term implementation.
Zheng M, Hamilton A, Ling C, 2021, Covert communications with a full-duplex receiver in non-coherent rayleigh fading, IEEE Transactions on Communications, Vol: 69, Pages: 1882-1895, ISSN: 0090-6778
In a majority of research on covert communications, knowledge about channel state information (CSI) of main channel and/or warden channel is assumed to be known or partially known. However, a covert user may not afford to perform channel estimation in practice, and acquiring the warden’s CSI is even impossible. In this paper, we investigate covert communications over non-coherent Rayleigh fading channels, in both i.i.d. fast fading and slow fading cases. We observe that the purpose of covert communication in many scenarios is to hide the existence of the sender, not the receiver. Therefore, we allow the receiver to work in full-duplex mode such that it can emit artificial noise (AN) while receiving signals simultaneously. We analyse the achievable covert rates with fixed and varying AN power and show that in both fast and slow fading cases, it is possible to achieve a positive covert rate. For the slow fading case, we further extend the proposed strategy to a multi-user scenario, in which multiple other users share the same spectral resource and cause interference at the warden. Extensive simulations are performed to verify the correctness of our analysis, which provide new insights on the AN design problem in non-coherent channels.
Mital N, Gunduz D, Ling C, 2020, Coded caching in a multi-server system with random topology, IEEE Transactions on Communications, Vol: 68, Pages: 4620-4631, ISSN: 0090-6778
Cache-aided content delivery is studied in a multi-server system with P servers and K users, each equipped with a local cache memory. In the delivery phase, each user connects randomly to any ρ out of P servers. Thanks to the availability of multiple servers, which model small-cell base stations (SBSs), demands can be satisfied with reduced storage capacity at each server and reduced delivery rate per server; however, this also leads to reduced multicasting opportunities compared to the single-server scenario. A joint storage and proactive caching scheme is proposed, which exploits coded storage across the servers, uncoded cache placement at the users, and coded delivery. The delivery latency is studied for both successive and parallel transmissions from the servers. It is shown that, with successive transmissions the achievable average delivery latency is comparable to the one achieved in the single-server scenario, while the gap between the two depends on ρ, the available redundancy across the servers, and can be reduced by increasing the storage capacity at the SBSs. The optimality of the proposed scheme with uncoded cache placement and MDS-coded server storage is also proved for successive transmissions.
Joseph D, Ghionis A, Ling C, et al., 2020, Not-so-adiabatic quantum computation for the shortest vector problem, Physical Review Research, Vol: 2, Pages: 1-13, ISSN: 2643-1564
Since quantum computers are known to break the vast majority of currently used cryptographic protocols, a variety of new protocols are being developed that are conjectured, but not proved, to be safe against quantum attacks. Among the most promising is lattice-based cryptography, where security relies upon problems like the shortest vector problem. We analyze the potential of adiabatic quantum computation for attacks on lattice-based cryptography, and give numerical evidence that even outside the adiabatic regime such methods can facilitate the solution of the shortest vector and similar problems.
Campello A, Ling C, Belfiore J-C, 2020, Semantically secure lattice codes for compound MIMO channels, IEEE Transactions on Information Theory, Vol: 66, Pages: 1572-1584, ISSN: 0018-9448
We consider compound multi-input multi-output (MIMO) wiretap channels where minimal channel state information at the transmitter (CSIT) is assumed. Code construction is given for the special case of isotropic mutual information, which serves as a conservative strategy for general cases. Using the flatness factor for MIMO channels, we propose lattice codes universally achieving the secrecy capacity of compound MIMO wiretap channels up to a constant gap (measured in nats) that is equal to the number of transmit antennas. The proposed approach improves upon existing works on secrecy coding for MIMO wiretap channels from an error probability perspective, and establishes information theoretic security (in fact semantic security). We also give an algebraic construction to reduce the code design complexity, as well as the decoding complexity of the legitimate receiver. Thanks to the algebraic structures of number fields and division algebras, our code construction for compound MIMO wiretap channels can be reduced to that for Gaussian wiretap channels, up to some additional gap to secrecy capacity.
Porter C, Lyu S, Ling C, 2020, On the optimality of Gauss's algorithm over Euclidean imaginary quadratic Fields, IEEE Information Theory Workshop (ITW), Publisher: IEEE, Pages: 185-189, ISSN: 2475-420X
In this paper, we continue our previous work on the reduction of algebraic lattices over imaginary quadratic fields for the special case when the lattice is spanned over a two dimensional basis. In particular, we show that the algebraic variant of Gauss's algorithm returns a basis that corresponds to the successive minima of the lattice in polynomial time if the chosen ring is Euclidean.
Lyu S, Porter C, Ling C, 2020, Lattice Reduction Over Imaginary Quadratic Fields, IEEE TRANSACTIONS ON SIGNAL PROCESSING, Vol: 68, Pages: 6380-6393, ISSN: 1053-587X
Lyu S, Wen J, Weng J, et al., 2020, On low-complexity lattice reduction algorithms for large-scale MIMO detection: the blessing of sequential reduction, IEEE Transactions on Signal Processing, Vol: 68, Pages: 257-269, ISSN: 1053-587X
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.
Lyu S, Campello A, Ling C, 2019, Ring Compute-and-Forward Over Block-Fading Channels, IEEE TRANSACTIONS ON INFORMATION THEORY, Vol: 65, Pages: 6931-6949, ISSN: 0018-9448
Ling C, Belfiore J-C, 2019, Achieving AWGN Channel Capacity With Lattice Gaussian Coding (vol 60, pg 5918, 2014), IEEE TRANSACTIONS ON INFORMATION THEORY, Vol: 65, Pages: 5281-5281, ISSN: 0018-9448
Mital N, Kralevska K, Ling C, et al., 2019, Practical Functional Regenerating Codes for Broadcast Repair of Multiple Nodes, IEEE International Symposium on Information Theory (ISIT), Publisher: IEEE, Pages: 221-225
Li C, Gan L, Ling C, 2019, Coprime sensing via Chinese remaindering over quadratic fields-part I: array designs, IEEE Transactions on Signal Processing, Vol: 67, Pages: 2898-2910, ISSN: 1053-587X
A coprime antenna array consists of two or more sparse subarrays featuring enhanced degrees of freedom (DOF) and reduced mutual coupling. This paper introduces a new class of planar coprime arrays, based on the theory of ideal lattices. In quadratic number fields, a splitting prime p can be decomposed into the product of two distinct prime ideals, which give rise to the two sparse subarrays. Their virtual difference coarray enjoys a quadratic gain in DOF, thanks to the generalized Chinese remainder theorem (CRT). To enlarge the contiguous aperture of the coarray, we present hole-free symmetric CRT arrays with simple closed-form expressions. The ring of Gaussian integers and the ring of Eisenstein integers are considered as examples to demonstrate the procedure of designing coprime arrays. With Eisenstein integers, our design yields a difference coarray that is a subset of the hexagonal lattice, offering a significant gain in DOF over the rectangular lattice, given the same physical areas. Maximization of CRT arrays in the aspect of essentialness and the superior performance in the context of angle estimation will be presented in the companion paper (Part II).
Wang Z, Ling C, 2019, Lattice gaussian sampling by Markov Chain Monte Carlo: bounded distance decoding and trapdoor sampling, IEEE Transactions on Information Theory, Vol: 65, Pages: 3630-3645, ISSN: 0018-9448
Sampling from the lattice Gaussian distribution plays an important role in various research fields. In this paper, the Markov chain Monte Carlo (MCMC)-based sampling technique is advanced in several fronts. First, the spectral gap for the independent Metropolis-Hastings-Klein (MHK) algorithm is derived, which is then extended to Peikert's algorithm and rejection sampling; we show that independent MHK exhibits faster convergence. Then, the performance of bounded distance decoding (BDD) using MCMC is analyzed, revealing a flexible trade-off between the decoding radius and complexity. MCMC is further applied to trapdoor sampling, again offering a trade-off between security and complexity. Finally, the independent multiple-try Metropolis-Klein (MTMK) algorithm is proposed to enhance the convergence rate. The proposed algorithms allow parallel implementation, which is beneficial for practical applications.
Li C, Gan L, Ling C, 2019, Coprime sensing via Chinese remaindering over quadratic fields-part II: generalizations and applications, IEEE Transactions on Signal Processing, Vol: 67, Pages: 2911-2922, ISSN: 1053-587X
The practical application of a new class of coprime arrays based on the Chinese remainder theorem (CRT) over quadratic fields is presented in this paper. The proposed CRT arrays are constructed by ideal lattices embedded from coprime quadratic integers with B 1 and B 2 being their matrix representations, respectively, whereby the degrees of freedom (DOF) surges toO(Idet(B 1 B 2 )I)with I det(B 1 )I + I det(B 2 )I sensors. The geometrical constructions and theoretical foundations were discussed in the accompanying paper in great detail, while this paper focuses on aspects of the application of the proposed arrays in two-dimensional (2-D) remote sensing. A generalization of CRT arrays based on two or more pairwise coprime ideal lattices is proposed with closed-form expressions on sensor locations, the total number of sensors, and the achievable DOF. The issues pertaining to the coprimality of any two quadratic integers are also addressed to explore all possible ideal lattices. Exploiting the symmetry of lattices, sensor reduction methods are discussed with the coarray remaining intact for economic maximization. In order to extend conventional angle estimation techniques based on uniformly distributed arrays to the method that can exploit any coarray configurations based on lattices, this paper introduces a hexagon-to-rectangular transformation to 2-D spatial smoothing, providing the possibility of finding more compact sensor arrays. Examples are provided to verify the feasibility of the proposed methods.
Zheng M, Ling C, Chen W, et al., 2019, Polar coding strategies for the interference channel with partial-joint decoding, IEEE Transactions on Information Theory, Vol: 65, Pages: 1973-1993, ISSN: 0018-9448
Existing polar coding schemes for the two-user interference channel follow the original idea of Han and Kobayashi, in which component messages are encoded independently and then mapped by some deterministic functions (i.e., homogeneous superposition coding). In this paper, we propose a new polar coding scheme for the interference channel based on the heterogeneous superposition coding approach of Chong, Motani, and Garg. We prove that fully joint decoding (the receivers simultaneously decode both senders’ common messages and the intended sender’s private message) in the Han–Kobayashi strategy can be simplified to two types of partial-joint decoding, which are friendly to polar coding with practical decoding algorithms. The proposed coding scheme requires less auxiliary random variables and no deterministic functions and can be efficiently constructed. Furthermore, we extend this result to interference networks and show that partial-joint decoding is a general method for designing heterogeneous superposition polar coding schemes in interference networks.
Campello A, Dadush D, Ling C, 2019, AWGN-goodness is enough: capacity-achieving lattice codes based on dithered probabilistic shaping, IEEE Transactions on Information Theory, Vol: 65, Pages: 1961-1971, ISSN: 0018-9448
In this paper we show that any sequence of infinite lattice constellations which is good for the unconstrained Gaussian channel can be shaped into a capacity-achieving sequence of codes for the power-constrained Gaussian channel under lattice decoding and non-uniform signalling. Unlike previous results in the literature, our scheme holds with no extra condition on the lattices (e.g. quantization-goodness or vanishing flatness factor), thus establishing a direct implication between AWGNgoodness, in the sense of Poltyrev, and capacity-achieving codes. Our analysis uses properties of the discrete Gaussian distribution in order to obtain precise bounds on the probability of error and achievable rates. In particular, we obtain a simple characterization of the finite-blocklength behavior of the scheme, showing that it approaches the optimal dispersion coefficient for high signalto- noise ratio. We further show that for low signal-to-noise ratio the discrete Gaussian over centered lattice constellations cannot achieve capacity, and thus a shift (or “dither”) is essentially necessary.
Liu L, Yan Y, Ling C, et al., 2019, Construction of capacity-achieving lattice codes: Polar lattices, IEEE Transactions on Communications, Vol: 67, Pages: 915-928, ISSN: 0090-6778
In this paper, we propose a new class of lattices constructed from polar codes, namely polar lattices, to achieve the capacity (1/2) log(1+SNR) of the additive white Gaussiannoise (AWGN) channel. Our construction follows the multilevel approach of Forney et al., where we construct a capacity-achieving polar code on each level. The component polar codes are shown to be naturally nested, thereby, fulfilling the requirement of the multilevel lattice construction. We prove that the polar lattices are AWGN-good. Furthermore, using the technique of source polarization, we propose discrete Gaussian shaping over the polar lattice to satisfy the power constraint. Both the construction and shaping are explicit, and the overall complexity of encoding and decoding is O(N log N) for any fixed target error probability.
Liu L, Ling C, 2019, Algebraic Polar Lattices for Fast Fading Channels, 10th IEEE International Symposium on Turbo Codes & Iterative Information Processing (ISTC), Publisher: IEEE, ISSN: 2165-4700
Mital N, Kralevska K, Ling C, et al., 2019, Storage-repair bandwidth trade-off for wireless caching with partial failure and broadcast repair, IEEE Information Theory Workshop (ITW), Publisher: IEEE, Pages: 41-45
Repair of multiple partially failed cache nodes is studied in a distributed wireless content caching system, where r out of a total of n cache nodes lose part of their cached data. Broadcast repair of failed cache contents at the network edge is studied; that is, the surviving cache nodes transmit broadcast messages to the failed ones, which are then used, together with the surviving data in their local cache memories, to recover the lost content. The trade-off between the storage capacity and the repair bandwidth is derived. It is shown that utilizing the broadcast nature of the wireless medium and the surviving cache contents at partially failed nodes significantly reduces the required repair bandwidth per node.
Lyu S, Porter C, Ling C, 2019, Performance limits of lattice reduction over imaginary quadratic fields with applications to compute-and-forward, IEEE Information Theory Workshop (ITW), Publisher: Institute of Electrical and Electronics Engineers, Pages: 480-484
Bases in the complex field, along with direct-sums defined by rings of imaginary quadratic integers, induce algebraic lattices. In this work, we examine the properties and reduction of such lattices. Focusing on algebraic Lenstra-Lenstra-Lovász (ALLL) reduction, we show that to satisfy Lovás condition requires the ring to be Euclidean. The proposed algorithm can be used to design network coding matrices in compute-and-forward (C & F).
Wang Z, Ling C, 2019, Slice Sampling for Lattice Gaussian Distribution, IEEE International Symposium on Information Theory (ISIT), Publisher: IEEE, Pages: 2589-2593
Li C, Gan L, Ling C, 2019, 3D COPRIME ARRAYS IN SPARSE SENSING, 44th IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Publisher: IEEE, Pages: 4200-4204, ISSN: 1520-6149
Zheng M, Liu L, Ling C, 2019, On the Polarization of Renyi Entropy, IEEE International Symposium on Information Theory (ISIT), Publisher: IEEE, Pages: 2094-2098
Lyu S, Ling C, 2019, Hybrid vector perturbation precoding: the blessing of approximate message passing, IEEE Transactions on Signal Processing, Vol: 67, Pages: 178-193, ISSN: 1053-587X
Vector perturbation (VP) precoding is a promising technique for multiuser communication systems operating in the downlink. In this work, we introduce a hybrid framework to improve the performance of lattice reduction (LR) aided precoding in VP. First, we perform a simple precoding using zero forcing (ZF) or successive interference cancellation (SIC) based on a reduced lattice basis. Since the signal space after LR-ZF or LR-SIC precoding can be shown to be bounded to a small range, then along with sufficient orthogonality of the lattice basis guaranteed by LR, they collectively pave the way for the subsequent application of an approximate message passing (AMP) algorithm, which further boosts the performance of any suboptimal precoder. Our work shows that the AMP algorithm can be beneficial for a lattice decoding problem whose data symbols lie in integers ℤ and entries of the lattice basis may not be i.i.d. Gaussian. Numerical results confirm that the low-complexity AMP algorithm can improve the symbol error rate performance of LR-aided precoding significantly. Finally, the hybrid scheme is also proven effective when solving the data detection problem of massive MIMO systems without using LR.
Zheng M, Chen W, Ling C, 2018, Polar coding for noncoherent block fading channels, 10th International Conference on Wireless Communications and Signal Processing (WCSP), Publisher: IEEE, ISSN: 2325-3746
In this paper, we consider the problem of polar coding for block fading channels without any instantaneous channel state information (CSI). We first decompose a block fading channel of T c symbols per coherent interval into T c binary-input sub-channels in a mutual-information-preserving way, and then design a multilevel (MLC) polar coding scheme for them. The proposed scheme achieves the ergodic mutual information of binary-input block fading channels with only channel distribution information (CDI). Simulations results are presented to compare the performance of the proposed MLC scheme and polar codes designed for i.i. d. fading channels with interleaving, which can provide some guidance for practical designs.
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.