Search

As blockchains continue to seek to scale to a larger number of nodes, the communication complexity of protocols has become a significant priority as the network can quickly become overburdened. Several schemes have attempted to address this, one of which uses coded computation to lighten the load. Here we seek to address one issue with all such coded blockchain schemes known to the authors: transaction confirmation. In a coded blockchain, only the leader has access to the uncoded block, while the nodes receive encoded data that makes it effectively impossible for them to identify which transactions were included in the block. As a result, a Byzantine leader might choose not to notify a sender or receiver of a transaction that the transaction went into the block, and even with an honest leader, they would not be able to produce a proof of a transaction's inclusion. To address this, we have constructed a protocol to send the nodes enough information so that a client sending or receiving a transaction is guaranteed to not only be notified but also to receive a proof of that transaction's inclusion in the block. Crucially, we do this without substantially increasing the bit complexity of the original coded blockchain protocol., To appear in 2023 IEEE International Symposium on Information Theory

Linear real-valued computations over distributed datasets are common in many applications, most notably as part of machine learning inference. In particular, linear computations which are quantized, i.e., where the coefficients are restricted to a predetermined set of values (such as $\pm 1$), gained increasing interest lately due to their role in efficient, robust, or private machine learning models. Given a dataset to store in a distributed system, we wish to encode it so that all such computations could be conducted by accessing a small number of servers, called the access parameter of the system. Doing so relieves the remaining servers to execute other tasks, and reduces the overall communication in the system. Minimizing the access parameter gives rise to an access-redundancy tradeoff, where smaller access parameter requires more redundancy in the system, and vice versa. In this paper we study this tradeoff, and provide several explicit code constructions based on covering codes in a novel way. While the connection to covering codes has been observed in the past, our results strictly outperform the state-of-the-art, and extend the framework to new families of computations., Accepted to ISIT 2023

The covering radius is a fundamental property of linear codes that characterizes the trade-off between storage and access in linear data-query protocols. The generalized covering radius was recently defined by Elimelech and Schwartz for applications in joint-recovery of linear data-queries. In this work we extend a known bound on the ordinary covering radius to the generalized one for all codes satisfying the chain condition -- a known condition which is satisfied by most known families of codes. Given a generator matrix of a special form, we also provide an algorithm which finds codewords which cover the input vectors within the distance specified by the bound. For the case of Reed-Muller codes we provide efficient construction of such generator matrices, therefore providing a faster alternative to a previous generalized covering algorithm for Reed-Muller codes., 8 pages, 9 figures. Conference paper accepted to 2023 IEEE International Symposium on Information Theory

Private inference refers to a two-party setting in which one has a model (e.g., a linear classifier), the other has data, and the model is to be applied over the data while safeguarding the privacy of both parties. In particular, models in which the weights are quantized (e.g., to 1 or -1) gained increasing attention lately, due to their benefits in efficient, private, or robust computations. Traditionally, private inference has been studied from a cryptographic standpoint, which suffers from high complexity and degraded accuracy. More recently, Raviv et al. showed that in quantized models, an information theoretic tradeoff exists between the privacy of the parties, and a scheme based on a combination of Boolean and real-valued algebra was presented which attains that tradeoff. Both the scheme and the respective bound required the computation to be done exactly. In this work we show that by relaxing the requirement for exact computation, one can break the information theoretic privacy barrier of Raviv et al., and provide better privacy at the same communication costs. We provide a scheme for such approximate computation, bound its error, show its improved privacy, and devise a respective lower bound for some parameter regimes., To appear in 2023 IEEE International Symposium on Information Theory

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 bit complexity dramatically such that it grows logarithmically with the number of nodes. Second, with the adoption of techniques from Information Dispersal and State Machine Replication, the system is resilient to Byzantine faults and achieves linear message complexity. Third, we propose a novel 2-dimensional sharding strategy, which inherently supports cross-shard transactions, alleviating the need for complicated communication protocols between shards, while keeping the computation and storage benefits of sharding.

A Sidon space is a subspace of an extension field over a base field in which the product of any two elements can be factored uniquely, up to constants. This paper proposes a new public-key cryptosystem of the multivariate type which is based on Sidon spaces, and has the potential to remain secure even if quantum supremacy is attained. This system, whose security relies on the hardness of the well-known MinRank problem, is shown to be resilient to several straightforward algebraic attacks. In particular, it is proved that the two popular attacks on the MinRank problem, the kernel attack, and the minor attack, succeed only with exponentially small probability. The system is implemented in software, and its hardness is demonstrated experimentally., Appeared in Public-Key Cryptography - PKC 2021, 24th IACR International Conference on Practice and Theory of Public Key Cryptography

In a Private Information Retrieval (PIR) protocol, a user can download a file from a database without revealing the identity of the file to each individual server. A PIR protocol is called $t$-private if the identity of the file remains concealed even if $t$ of the servers collude. Graph based replication is a simple technique, which is prevalent in both theory and practice, for achieving erasure robustness in storage systems. In this technique each file is replicated on two or more storage servers, giving rise to a (hyper-)graph structure. In this paper we study private information retrieval protocols in graph based replication systems. The main interest of this work is maximizing the parameter $t$, and in particular, understanding the structure of the colluding sets which emerge in a given graph. Our main contribution is a $2$-replication scheme which guarantees perfect privacy from acyclic sets in the graph, and guarantees partial-privacy in the presence of cycles. Furthermore, by providing an upper bound, it is shown that the PIR rate of this scheme is at most a factor of two from its optimal value for an important family of graphs. Lastly, we extend our results to larger replication factors and to graph-based coding, which is a similar technique with smaller storage overhead and larger PIR rate.

In this paper, we introduce a new channel model we term the q-ary multi-bit channel (QMBC). This channel models a memory device, where q-ary symbols (q=2^s) are stored in the form of current/voltage levels. The symbols are read in a measurement process, which provides a symbol bit in each measurement step, starting from the most significant bit. An error event occurs when not all the symbol bits are known. To deal with such error events, we use GF(q) low-density parity-check (LDPC) codes and analyze their decoding performance. We start with iterative-decoding threshold analysis, and derive optimal edge-label distributions for maximizing the decoding threshold. We later move to finite-length iterative-decoding analysis and propose an edge-labeling algorithm for improved decoding performance. We then provide finite-length maximum-likelihood decoding analysis for both the standard non-binary random ensemble and LDPC ensembles. Finally, we demonstrate by simulations that the proposed edge-labeling algorithm improves finite-length decoding performance by orders of magnitude., Comment: 26 pages, 8 figures, submitted to IEEE Transactions on Information Theory

A novel technique for construction of minimum storage regenerating (MSR) codes is presented. Based on this technique, three explicit constructions of MSR codes are given. The first two constructions provide access-optimal MSR codes, with two and three parities, respectively, which attain the sub-packetization bound for access-optimal codes. The third construction provides longer MSR codes with three parities, which are not access-optimal, and do not necessarily attain the sub-packetization bound. In addition to a minimum storage in a node, all three constructions allow the entire data to be recovered from a minimal number of storage nodes. That is, given storage $\ell$ in each node, the entire stored data can be recovered from any $2\log_2 \ell$ for 2 parity nodes, and either $3\log_3\ell$ or $4\log_3\ell$ for 3 parity nodes. Second, in the first two constructions, a helper node accesses the minimum number of its symbols for repair of a failed node (access-optimality). The generator matrix of these codes is based on perfect matchings of complete graphs and hypergraphs, and on a rational canonical form of matrices. The goal of this paper is to provide a construction of such optimal codes over the smallest possible finite fields. For two parities, the field size is reduced by a factor of two for access-optimal codes compared to previous constructions. For three parities, in the first construction the field size is $6\log_3 \ell+1$ (or $3\log_3 \ell+1$ for fields with characteristic 2), and in the second construction the field size is larger, yet linear in $\log_3\ell$. Both constructions with 3 parities provide a significant improvement over existing previous works, since only non-explicit constructions with exponential field size (in $\log_3\ell$) were known so far.