Publications
162 results found
Wang J, Ling C, 2023, Polar sampler: A novel Bernoulli sampler using polar codes with application to integer Gaussian sampling, DESIGNS CODES AND CRYPTOGRAPHY, ISSN: 0925-1022
Lyu S, Wang Z, Ling C, et al., 2022, Better Lattice Quantizers Constructed From Complex Integers, IEEE TRANSACTIONS ON COMMUNICATIONS, Vol: 70, Pages: 7932-7940, ISSN: 0090-6778
Ling C, Ross B, 2022, Wang algebra: from theory to practice, IEEE Open Journal of Circuits and Systems, Vol: 3, Pages: 274-285, ISSN: 2644-1225
Wang algebra was initiated by Ki-Tung Wang as a short-cut method for the analysis of electrical networks. It was later popularized by Duffin and has since found numerous applications in electrical engineering and graph theory. This is a semi-tutorial paper on Wang algebra, its history, and modern applications. We expand Duffin’s historic notes on Wang algebra to give a full account of Ki-Tung Wang’s life. A short proof of Wang algebra using group theory is presented. We exemplify the usefulness of Wang algebra in the design of T-coils. Bridged T-coils give a significant advantage in bandwidth, and were widely adopted in Tektronix oscilloscopes, but design details were guarded as a trade secret. The derivation presented in this paper, based on Wang algebra, is more general and simpler than those reported in literature. This novel derivation has not been shared with the public before.
Wang J, Ling C, 2022, Polar coding for Ring-LWE-based public key encryption, CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES, Vol: 15, Pages: 397-431, ISSN: 1936-2447
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.
Grover C, Mendelsohn A, Ling C, et al., 2022, Non-commutative Ring Learning with Errors from Cyclic Algebras, JOURNAL OF CRYPTOLOGY, Vol: 35, ISSN: 0933-2790
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
- Author Web Link
- Cite
- Citations: 1
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, Liu L, Lyu S, et al., 2022, Quantum-safe cryptography: crossroads of coding theory and cryptography, SCIENCE CHINA-INFORMATION SCIENCES, Vol: 65, ISSN: 1674-733X
Mital N, Kralevska K, Ling C, et al., 2021, Functional broadcast repair of multiple partial failures in wireless distributed storage systems, IEEE Journal on Selected Areas in Information Theory, Vol: 2, Pages: 1093-1107, ISSN: 2641-8770
We consider a distributed storage system with n nodes, where a user can recover the stored file from any k nodes, and study the problem of repairing r partially failed nodes. We consider broadcast repair , that is, d surviving nodes transmit broadcast messages on an error-free wireless channel to the r nodes being repaired, which are then used, together with the surviving data in the local memories of the failed nodes, to recover the lost content. First, we derive the trade-off between the storage capacity and the repair bandwidth for partial repair of multiple failed nodes, based on the cut-set bound for information flow graphs. It is shown that utilizing the broadcast nature of the wireless medium and the surviving contents at the partially failed nodes reduces the repair bandwidth per node significantly. Then, we list a set of invariant conditions that are sufficient for a functional repair code to be feasible. We further propose a scheme for functional repair of multiple failed nodes that satisfies the invariant conditions with high probability, and its extension to the repair of partial failures. The performance of the proposed scheme meets the cut-set bound on all the points on the trade-off curve for all admissible parameters when k is divisible by r , while employing linear subpacketization, which is an important practical consideration in the design of distributed storage codes. Unlike random linear codes, which are conventionally used for functional repair of failed nodes, the proposed repair scheme has lower overhead, lower input-output cost, and lower computational complexity during repair.
Liu L, Shi J, Ling C, 2021, Polar Lattices for Lossy Compression, IEEE TRANSACTIONS ON INFORMATION THEORY, Vol: 67, Pages: 6140-6163, ISSN: 0018-9448
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.
Wang Z, Xia Y, Lyu S, et al., 2021, Reinforcement Learning-Aided Markov Chain Monte Carlo For Lattice Gaussian Sampling, IEEE Information Theory Workshop (ITW), Publisher: IEEE
Saliba C, Luzzi L, Ling C, 2021, A reconciliation approach to key generation based on Module-LWE, IEEE International Symposium on Information Theory (ISIT), Publisher: IEEE, Pages: 1636-1641
Zheng M, Gu J, Ma M, et al., 2021, Joint Source-Channel Polar Coding for Biased Bernoulli Sources at Short Blocklengths, 11th International Symposium on Topics in Coding (ISTC), Publisher: IEEE, ISSN: 2165-4700
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
- Author Web Link
- Cite
- Citations: 4
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.
Shi J, Ling C, Simeone O, et al., 2020, Coded Computation Against Straggling Channel Decoders in the Cloud for Gaussian Channels, IEEE International Symposium on Information Theory (ISIT), Publisher: IEEE, Pages: 156-161
- Author Web Link
- Cite
- Citations: 1
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
- Author Web Link
- Cite
- Citations: 5
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.
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.