Search

Quantum key distribution (QKD) is a popular protocol that provides information theoretically secure keys to multiple parties. Two important post-processing steps of QKD are 1) the information reconciliation (IR) step, where parties reconcile mismatches in generated keys through classical communication, and 2) the privacy amplification (PA) step, where parties distill their common key into a new secure key that the adversary has little to no information about. In general, these two steps have been abstracted as two distinct problems. In this work, we consider a new technique of performing the IR and PA steps jointly through sampling that relaxes the requirement on the IR step, allowing for more success in key creation. We provide a novel LDPC code construction known as Block-MDS QC-LDPC codes that can utilize the relaxed requirement by creating LDPC codes with pre-defined sub-matrices of full-rank. We demonstrate through simulations that our technique of sampling can provide notable gains in successfully creating secret keys., Comment: 7 pages, 1 figure, submitted to the International Symposium on Information Theory (ISIT) 2024

Data availability (DA) attack is a well-known problem in certain blockchains where users accept an invalid block with unavailable portions. Previous works have used LDPC and 2-D Reed Solomon (2DRS) codes with Merkle trees to mitigate DA attacks. These codes perform well across various metrics such as DA detection probability and communication cost. However, these codes are difficult to apply to blockchains with large blocks due to large decoding complexity and coding fraud proof size (2D-RS codes), and intractable code guarantees for large code lengths (LDPC codes). In this paper, we focus on large block size applications and address the above challenges by proposing the novel Polar Coded Merkle Tree (PCMT): a Merkle tree encoded using the encoding graph of polar codes. We provide a specialized polar code design algorithm called Sampling Efficient Freezing and an algorithm to prune the polar encoding graph. We demonstrate that the PCMT built using the above techniques results in a better DA detection probability and communication cost compared to LDPC codes, has a lower coding fraud proof size compared to LDPC and 2D-RS codes, provides tractable code guarantees at large code lengths (similar to 2D-RS codes), and has comparable decoding complexity to 2D-RS and LDPC codes., Comment: 36 pages, 10 figures, 2 tables, submitted to IEEE Journal on Selected Areas in Information Theory

In this paper, we present a novel variation of the coded matrix multiplication problem which we refer to as fully private grouped matrix multiplication (FPGMM). In FPGMM, a master wants to compute a group of matrix products between two matrix libraries that can be accessed by all workers while ensuring that any number of prescribed colluding workers learn nothing about which matrix products the master desires, nor the number of matrix products. We present an achievable scheme using a variant of Cross-Subspace Alignment (CSA) codes that offers flexibility in communication and computation cost. Additionally, we demonstrate how our scheme can outperform naive applications of schemes used in a related privacy focused coded matrix multiplication problem., Comment: 7 pages, 3 figures, submitted to the International Symposium on Information Theory (ISIT) 2023

In energy-time entanglement Quantum Key Distribution (QKD), two users extract a shared secret key from the arrival times (discretized as symbols) of entangled photon pairs. In prior work, Zhou et al. proposed a multi-level coding (MLC) scheme that splits the observed symbols into bit layers and utilizes binary Low-Density Parity-Check (LDPC) codes for reconciliation of the symbols. While binary LDPC codes offer low latency for key generation, splitting the symbols into bits results in a loss of key generation rate due to error propagation. Additionally, existing LDPC codes do not fully utilize the properties of the QKD channel to optimize the key rates. In this paper, we mitigate the above issues by first generalizing the MLC scheme to a non-binary(NB) MLC scheme that has layers with non-binary symbols and utilizes NB-LDPC codes. We show the NB-MLC scheme offers flexibility in system design. Additionally, we show that the NB-MLC scheme with a small symbol size per layer offers the best trade-off between latency and key rate. We then propose a framework to jointly optimize the rate and degree profile of the NB-LDPC codes that is tailored towards the QKD channel resulting in higher key rates than prior work., Comment: 5 pages, 4 figures, submitted to International Symposium on Topics in Coding

Modern distributed systems suffer from a phenomenon known as stragglers where computation nodes either break-down or are sufficiently slow, resulting in a large tail latency. Inspired by error correcting codes, researchers within the field of coded computation combat stragglers by cleverly encoding the data within the computations. One major endeavor is in the study of coded matrix-matrix multiplication where the task is to multiply two large matrices in a distributed manner. Most coded matrix computation work focuses on highly structured tasks which allows for easier code construction and analysis but limits the applicability for more general problems. For the first time, we consider the novel problem of multiplying many different matrices whose products may share matrices with no guaranteed regularity. Specifically, we consider the Variable Coded Distributed Batch Matrix Multiplication (VCDBMM) problem where the system is given two sets of matrices $\mathcal{A}=\{A_1,A_2,\dots,A_{|\mathcal{A}|}\}$ and $\mathcal{B}=\{B_1,B_2,\dots,B_{|\mathcal{B}|}\}$ and a set of computation goals $\mathcal{S} = \{(i_1,j_1),(i_2,j_2), \dots (i_{|\mathcal{S}|},j_{|\mathcal{S}|})\}$ and the objective is to calculate the matrix multiplication $A_iB_j$ for every $(i,j) \in \mathcal{S}$ in the presence of stragglers. Therefore, a good coding solution minimizes the recovery threshold (i.e., the number of workers that we need to wait for in order to compute the final output). Inspired by Cross-Subspace Alignment Codes, we construct Flexible Cross-Subspace Alignment Codes (FCSA) to solve the general VCDBMM problem. We provide two variants of FCSA codes that allow for a trade-off between the encoding/decoding complexity and the recovery threshold. We demonstrate that both variants are within a factor of two optimal under certain system constraints. We also generalize FCSA codes into Grouped FCSA codes where we group computations together to provide further flexibility between the computati

Modern distributed systems suffer from a phenomenon known as stragglers where computation nodes either break-down or are sufficiently slow, resulting in a large tail latency. Inspired by error correcting codes, researchers within the field of coded computation combat stragglers by cleverly encoding the data within the computations. One major endeavor is in the study of coded matrix-matrix multiplication where the task is to multiply two large matrices in a distributed manner. Most coded matrix computation work focuses on highly structured tasks which allows for easier code construction and analysis but limits the applicability for more general problems. For the first time, we consider the novel problem of multiplying many different matrices whose products may share matrices with no guaranteed regularity. Specifically, we consider the Variable Coded Distributed Batch Matrix Multiplication (VCDBMM) problem where the system is given two sets of matrices $\mathcal{A}=\{A_1,A_2,\dots,A_{|\mathcal{A}|}\}$ and $\mathcal{B}=\{B_1,B_2,\dots,B_{|\mathcal{B}|}\}$ and a set of computation goals $\mathcal{S} = \{(i_1,j_1),(i_2,j_2), \dots (i_{|\mathcal{S}|},j_{|\mathcal{S}|})\}$ and the objective is to calculate the matrix multiplication $A_iB_j$ for every $(i,j) \in \mathcal{S}$ in the presence of stragglers. Therefore, a good coding solution minimizes the recovery threshold (i.e., the number of workers that we need to wait for in order to compute the final output). Inspired by Cross-Subspace Alignment Codes, we construct Flexible Cross-Subspace Alignment Codes (FCSA) to solve the general VCDBMM problem. We provide two variants of FCSA codes that allow for a trade-off between the encoding/decoding complexity and the recovery threshold. We demonstrate that both variants are within a factor of two optimal under certain system constraints. We also generalize FCSA codes into Grouped FCSA codes where we group computations together to provide further flexibility between the computati

Light nodes in blockchain systems are known to be vulnerable to data availability (DA) attacks where they accept an invalid block with unavailable portions. Previous works have used LDPC and 2-D Reed Solomon (2D-RS) codes with Merkle Trees to mitigate DA attacks. While these codes have demonstrated improved performance across a variety of metrics such as DA detection probability, they are difficult to apply to blockchains with large blocks due to generally intractable code guarantees for large codelengths (LDPC), large decoding complexity (2D-RS), or large coding fraud proof sizes (2D-RS). We address these issues by proposing the novel Polar Coded Merkle Tree (PCMT) which is a Merkle Tree built from the encoding graphs of polar codes and a specialized polar code construction called Sampling-Efficient Freezing (SEF). We demonstrate that the PCMT with SEF polar codes performs well in detecting DA attacks for large block sizes., Comment: 9 pages, 4 figures, 2 tables, To appear in IEEE International Symposium on Information Theory (ISIT) 2022

Light nodes are clients in blockchain systems that only store a small portion of the blockchain ledger. In certain blockchains, light nodes are vulnerable to a data availability (DA) attack where a malicious node makes the light nodes accept an invalid block by hiding the invalid portion of the block from the nodes in the system. Recently, a technique based on LDPC codes called Coded Merkle Tree was proposed by Yu et al. that enables light nodes to detect a DA attack by randomly requesting/sampling portions of the block from the malicious node. However, light nodes fail to detect a DA attack with high probability if a malicious node hides a small stopping set of the LDPC code. In this paper, we demonstrate that a suitable co-design of specialized LDPC codes and the light node sampling strategy leads to a high probability of detection of DA attacks. We consider different adversary models based on their computational capabilities of finding stopping sets. For the different adversary models, we provide new specialized LDPC code constructions and coupled light node sampling strategies and demonstrate that they lead to a higher probability of detection of DA attacks compared to approaches proposed in earlier literature., Comment: 18 pages, 7 figures, 3 tables, accepted at IEEE Transactions on Communications (TCOM) 2022. This version reflects comments from reviewers at TCOM

A majority of coded matrix-matrix computation literature has broadly focused in two directions: matrix partitioning for computing a single computation task and batch processing of multiple distinct computation tasks. While these works provide codes with good straggler resilience and fast decoding for their problem spaces, these codes would not be able to take advantage of the natural redundancy of re-using matrices across batch jobs. In this paper, we introduce the Variable Coded Distributed Batch Matrix Multiplication (VCDBMM) problem which tasks a distributed system to perform batch matrix multiplication where matrices are not necessarily distinct among batch jobs. Inspired in part by Cross-Subspace Alignment codes, we develop Flexible Cross-Subspace Alignments (FCSA) codes that are flexible enough to utilize this redundancy. We provide a full characterization of FCSA codes which allow for a wide variety of system complexities including good straggler resilience and fast decoding. We theoretically demonstrate that, under certain practical conditions, FCSA codes are within a factor of 2 of the optimal solution when it comes to straggler resilience. Furthermore, our simulations demonstrate that our codes can achieve even better optimality gaps in practice, even going as low as 1.7., Comment: 35 pages, 8 figures, a part of this manuscript was published at IEEE Global Communications Conference (GLOBECOM) 2021

A popular method of improving the throughput of blockchain systems is by running smaller side blockchains that push the hashes of their blocks onto a trusted blockchain. Side blockchains are vulnerable to stalling attacks where a side blockchain node pushes the hash of a block to the trusted blockchain but makes the block unavailable to other side blockchain nodes. Recently, Sheng et al. proposed a data availability oracle based on LDPC codes and a data dispersal protocol as a solution to the above problem. While showing improvements, the codes and dispersal protocol were designed disjointly which may not be optimal in terms of the communication cost associated with the oracle. In this paper, we provide a tailored dispersal protocol and specialized LDPC code construction based on the Progressive Edge Growth (PEG) algorithm, called the dispersal-efficient PEG (DE-PEG) algorithm, aimed to reduce the communication cost associated with the new dispersal protocol. Our new code construction reduces the communication cost and, additionally, is less restrictive in terms of system design., Comment: 7 pages, 2 figures, 2 tables, To appear in Information Theory Workshop (ITW) 2021

In this paper, we propose a non-uniform windowed decoder for multi-dimensional spatially-coupled LDPC (MD-SC-LDPC) codes over the binary erasure channel. An MD-SC-LDPC code is constructed by connecting together several SC-LDPC codes into one larger code that provides major benefits over a variety of channel models. In general, SC codes allow for low-latency windowed decoding. While a standard windowed decoder can be naively applied, such an approach does not fully utilize the unique structure of MD-SC-LDPC codes. In this paper, we propose and analyze a novel non-uniform decoder to provide more flexibility between latency and reliability. Our theoretical derivations and empirical results show that our non-uniform decoder greatly improves upon the standard windowed decoder in terms of design flexibility, latency, and complexity., Comment: 7 pages, 5 figures, submitted to International Symposium on Information Theory (ISIT) 2020

In certain blockchain systems, light nodes are clients that download only a small portion of the block. Light nodes are vulnerable to data availability (DA) attacks where a malicious node hides an invalid portion of the block from the light nodes. Recently, a technique based on erasure codes called Coded Merkle Tree (CMT) was proposed by Yu et al. that enables light nodes to detect a DA attack with high probability. The CMT is constructed using LDPC codes for fast decoding but can fail to detect a DA attack if a malicious node hides a small stopping set of the code. To combat this, Yu et al. used well-studied techniques to design random LDPC codes with high minimum stopping set size. Although effective, these codes are not necessarily optimal for this application. In this paper, we demonstrate a more specialized LDPC code design to improve the security against DA attacks. We achieve this goal by providing a deterministic LDPC code construction that focuses on concentrating stopping sets to a small group of variable nodes rather than only eliminating stopping sets. We design these codes by modifying the Progressive Edge Growth algorithm into a technique called the entropy-constrained PEG (EC-PEG) algorithm. This new method demonstrates a higher probability of detecting DA attacks and allows for good codes at short lengths., Comment: 6 pages, 5 figures, To appear in Information Theory Workshop (ITW) 2020

A circulant-based spatially-coupled (SC) code is constructed by partitioning the circulants in the parity-check matrix of a block code into several components and piecing copies of these components in a diagonal structure. By connecting several SC codes, multi-dimensional SC (MD-SC) codes are constructed. In this paper, we present a systematic framework for constructing MD-SC codes with notably better cycle properties than their one-dimensional counterparts. In our framework, the multi-dimensional coupling is performed via an informed relocation of problematic circulants. This work is general in the terms of the number of constituent SC codes that are connected together, the number of neighboring SC codes that each constituent SC code is connected to, and the length of the cycles whose populations we aim to reduce. Finally, we present a decoding algorithm that utilizes the structures of the MD-SC code to achieve lower decoding latency. Compared to the conventional SC codes, our MD-SC codes have a notably lower population of small cycles, and a dramatic BER improvement. The results of this work can be particularly beneficial in data storage systems, e.g., 2D magnetic recording and 3D Flash systems, as high-performance MD-SC codes are robust against various channel impairments and non-uniformity., Comment: 34 pages, 10 figures, submitted to IEEE Transactions on Communications (TCOM)