We introduceInfo-Commit, an information-theoretic protocol for polynomial commitment and verification. With the help of a trusted initializer, a succinct commitment to a private polynomial$f$is provided to the user. The user then queries the server to obtain evaluations of$f$at several inputs chosen by the user. The server provides the evaluations along with proofs of correctness which the user can verify against the initial commitment.Info-Commithas four main features. Firstly, the user is able to detect, with high probability, if the server has responded with evaluations of the same polynomial initially committed to. Secondly,Info-Commitprovides rigorous privacy guarantees for the server: upon observing the initial commitment and the response provided by the server to$m$evaluation queries, the user only learns$O(m^{2})$symbols about the coefficients of$f$. Thirdly, the verifiability and the privacy guarantees are unconditional regardless of the computational power of the two parties. Lastly,Info-Commitis doubly-efficient in the sense that in the evaluation phase, the user runs in$O(\sqrt {d})$time and the server runs in$O(d)$time, where$d-1$is the degree of the polynomial$f$.

Cloud computing platforms have created the possibility for computationally limited users to delegate demanding tasks to strong but untrusted servers. Verifiable computing algorithms help build trust in such interactions by enabling the server to provide a proof of correctness of his results which the user can check very efficiently. In this article, we present a doubly-efficient interactive algorithm for verifiable polynomial evaluation. Unlike the mainstream literature on verifiable computing, the soundness of our algorithm is information-theoretic and cannot be broken by a computationally unbounded server. By relying on basic properties of error correcting codes, our algorithm enforces a dishonest server to provide false results to problems which become progressively easier to verify. After roughly logd rounds, the user can verify the response of the server against a look-up table that has been pre-computed during an initialization phase. For a polynomial of degree d, we achieve a user complexity of O(dϵ), a server complexity of O(d1+ϵ), a round complexity of O(logd) and an initialization complexity of O(d1+ϵ).

We study the problem of verifiable polynomial evaluation in the user-server and multi-party setups. We propose INTERPOL, an information-theoretically verifiable algorithm that allows a user to delegate the evaluation of a polynomial to a server, and verify the correctness of the results with high probability and in sublinear complexity. Compared to the existing approaches which typically rely on cryptographic assumptions, INTERPOL stands out in that it does not assume any computational limitation on the server. INTERPOL relies on decomposition of polynomial evaluation into two matrix multiplications, and injection of computation redundancy in the form of locally computed parities with secret coefficients for verification. Furthermore, by generalizing INTERPOL to a multiparty setting consisting of a network of n untrusted nodes, where each node is interested in evaluating the same polynomial, we demonstrate that we can achieve an overall computational complexity comparable to a trusted setup, while guaranteeing information-theoretic verification at each node.

We introduce Coded State Machine (CSM), an information-theoretic framework to securely and efficiently execute multiple state machines on Byzantine nodes. The standard method of solving this problem is using State Machine Replication, which achieves high security at the cost of low efficiency. CSM simultaneously achieves the optimal linear scaling in storage, throughput, and security with increasing network size. The storage is scaled via the design of Lagrange coded states and coded input commands that require the same storage size as their origins. The computational efficiency is scaled using a novel delegation algorithm, called INTERMIX, which is an information-theoretically verifiable matrix-vector multiplication algorithm of independent interest.

A new scheme for the problem of centralized coded caching with non-uniform demands is proposed. The distinguishing feature of the proposed placement strategy is that it admits equal sub-packetization for all files while allowing the users to allocate more cache to the files which are more popular. This creates natural broadcasting opportunities in the delivery phase which are simultaneously helpful for the users who have requested files of different popularities. For the case of two files, we propose a new delivery strategy based on interference alignment which enables each user to decode his desired file following a two-layer peeling decoder. Furthermore, we extend the existing converse bounds for uniform demands under uncoded placement to the nonuniform case. To accomplish this, we construct$N!$auxiliary users, corresponding to all permutations of the$N$files, each caching carefully selected sub-packets of the files. Each auxiliary user provides a different converse bound. The overall converse bound is the maximum of all these$N!$bounds. We prove that our achievable delivery rate for the case of two files meets this converse, thereby establishing the optimal expected memory-rate trade-off for the case of$K$users and two files with arbitrary popularities under uncoded placement.

We introduce the Fixed Cluster Repair System (FCRS) as a novel architecture for Distributed Storage Systems (DSS) that achieves a small repair bandwidth while guaranteeing a high availability. Specifically, we partition the set of servers in a DSS into s clusters and allow a failed server to choose any cluster other than its own as its repair group. Thereby, we guarantee an availability of s-1. We characterize the repair bandwidth vs. storage trade-off for the FCRS under functional repair and show that the minimum repair bandwidth can be improved by an asymptotic multiplicative factor of 2/3 compared to the state of the art coding techniques that guarantee the same availability. Furthermore, we introduce cubic codes designed to minimize the repair bandwidth of the FCRS under the exact repair model. We prove an asymptotic multiplicative improvement of 0.79 in the minimum repair bandwidth compared to the existing exact repair coding techniques that achieve the same availability. We show that cubic codes are information-theoretically optimal for the FCRS with 2 and 3 complete clusters. A full version of this paper is accessible at: https://arxiv.org/pdf/1710.02653.pdf.

The classical distributed storage problem can be modeled by a k-uniform complete hyper-graph where vertices represent servers and hyper-edges represent users. Hence each hyper-edge should be able to recover the full file using only the memories of the vertices associated with it. This paper considers the generalization of this problem to arbitrary hyper-graphs and to the case of multiple files, where each user is only interested in one, a problem we will refer to as the graphical distributed storage problem (GDSP). Specifically, we make progress in the analysis of minimum-storage codes for two main subproblems of the GDSP which extend the classical model in two independent directions: the case of an arbitrary graph with multiple files, and the case of an arbitrary hyper-graph with a single file.

A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order O(nψ log(nψ)), where ψ = √P∥h∥2+ 1 depends on the transmission power and the norm of the channel vector. We will then extend our results to integer-forcing and finally introduce a more general class of lattices for which the SVP and the closest vector problem can be approximated within a constant factor.

In this paper, we evaluate the saturation throughput for an IEEE 802.11 based wireless network considering capture effect at the receiver, while nodes transmit with random powers. In this respect, we consider a scenario consisting of a specific number of wireless nodes. Then, we derive the transmission as well as collision probabilities with respect to the perfect capture effect. In order to maximize the saturation throughput we set up an optimization problem and obtain how to compute optimum values for the probabilities corresponding to different power levels. By providing the numerical results, we deduce that power randomization may lead to a significant improvement in saturation throughput.