Emerging applications in manufacturing, wireless communication, and molecular data storage require robust coding schemes that remain effective under physical distortions where codewords may be arbitrarily fragmented and partially missing. To address such challenges, we propose a new family of error-correcting codes, termed $(t,s)$-break-resilient codes ($(t,s)$-BRCs). A $(t,s)$-BRC guarantees correct decoding of the original message even after up to~$t$ arbitrary breaks of the codeword and the complete loss of some fragments whose total length is at most~$s$. This model unifies and generalizes previous approaches, extending break-resilient codes (which handle arbitrary fragmentation without fragment loss) and deletion codes (which correct bit losses in unknown positions without fragmentation) into a single information-theoretic framework. We develop a theoretical foundation for $(t,s)$-BRCs, including a formal adversarial channel model, lower bounds on the necessary redundancy, and explicit code constructions that approach these bounds.

We consider the problem of encoding information in a system ofN=K+Rprocessors that operate in a decentralized manner, i.e., without a central processor which orchestrates the operation. The system involvesKsource processors, each holding some data modeled as a vector over a finite field. The remainingRprocessors are sinks, and each of which requires a linear combination of all data vectors. These linear combinations are distinct from one sink to another, and are specified by a generator matrix of a systematic linear code. To capture the communication cost of decentralized encoding, we adopt a linear network model in which the process proceeds in consecutive communication rounds. In every round, every processor sends and receives one message through each one of itspports. Moreover, inspired by network coding literature, we allow processors to transfer linear combinations of their own data and previously received data. We propose a framework that addresses the problem on two levels. On theuniversallevel, we provide a solution to the decentralized encoding problem foranypossible linear code. On thespecificlevel, we further optimize our solution towards systematic Reed-Solomon codes, as well as their variant, Lagrange codes, for their prevalent use in coded storage and computation systems. Our solutions are based on a newly-defined collective communication operation calledall-to-all encode.

3D printing brings about a revolution in con-sumption and distribution of goods, but poses a significant risk to public safety. Any individual with internet access and a commodity printer can now produce untraceable firearms, keys, and dangerous counterfeit products. To aid government authorities in combating these new security threats, objects are often tagged with identifying information. This information, also known as fingerprints, is written into the object using various bit embedding techniques, such as varying the width of the molten thermoplastic layers. Yet, due to the adversarial nature of the problem, it is important to devise tamper-resilient fingerprinting techniques, so that the fingerprint could be extracted even if the object was damaged. This paper focuses on a special type of adversarial tampering, where the adversary breaks the object to at most a certain number of parts. This gives rise to a new adversarial coding problem, which is formulated and investigated herein. We survey the existing technology, present an abstract problem definition, provide lower bounds for the required redundancy, and construct a code which attains it up to asymptotically small factors.

We define all-to-all encode, a collective communication operation serving as a primitive in decentralized computation and storage systems. Consider a scenario where every processor initially has a data packet and requires a linear combination of all data packets; the linear combinations are distinct from one processor to another, and are specified by a generator matrix of an error correcting code. We use a linear network model, in which processors transmit linear combinations of their data and previously received packets, and adopt a standard synchronous system setting to analyze its communication cost. We provide a universal algorithm which computes any matrix in this model by only varying intermediate coefficients, and prove its optimality. When the generator matrix is of the Vandermonde or Lagrange type, we further optimize the communication efficiency of the proposed algorithm.

Although blockchain, the supporting technology of various cryptocurrencies, has offered a potentially effective framework for numerous decentralized trust management systems, its performance is still sub-optimal in real-world networks. With limited bandwidth, the communication complexity for nodes to process a block scales with the growing network size and hence becomes the limiting factor of blockchain’s performance.In this paper, we suggest a re-design of existing blockchain systems, which addresses the issue of the communication burden. First, by employing techniques from Coded Computation, our scheme guarantees correct verification of transactions while reducing the communication complexity dramatically such that it grows logarithmically with network size. Second, by adopting techniques from Information Dispersal and State Machine Replication, our design is provably resilient to Byzantine faults under standard cryptographic assumptions.1

Although blockchain, the supporting technology of Bitcoin and various cryptocurrencies, has offered a potentially effective framework for numerous applications, it still suffers from the adverse affects of the impossibility triangle. Performance, security, and decentralization of blockchains normally do not scale simultaneously with the number of participants in the network. The recent introduction of error correcting codes in sharded blockchain by Li et al. partially settles this trilemma, boosting throughput without compromising security and decentralization. In this paper, we improve the coded sharding scheme in three ways. First, we propose a novel 2-Dimensional Sharding strategy, which inherently supports cross-shard transactions, alleviating the need for complicated inter-shard communication protocols. Second, we employ distributed storage techniques in the propagation of blocks, improving latency under restricted bandwidth. Finally, we incorporate polynomial cryptographic primitives of low degree, which brings coded blockchain techniques into the realm of feasible real-world parameters.