In ($t, n$) -threshold secret sharing, a secret$S$is distributed among$n$participants such that any subset of size$t$can recover$S$, while any subset of size$t-1$or fewer learns nothing about it. For information-theoretic secret sharing, it is known that the share size must be at least as large as the secret, i.e.,$|S|$. When computational security is employed using cryptographic encryption with a secret key$K$, previous work has shown that the share size can be reduced to$\frac{S \mid}{t}+|K|$. In this paper, we present a construction achieving a share size of$\frac{|S|+|K|}{t}$. We further prove that, under reasonable assumptions on the encryption utilized, this share size is optimal.

We present CHOKE, a novel code-based hybrid key-encapsulation mechanism (KEM) designed to securely and efficiently transmit multiple session keys simultaneously. By encoding n independent session keys with an individually secure linear code and encapsulating each resulting coded symbol using a separate KEM, CHOKE achieves computational individual security–each key remains secure as long as at least one underlying KEM remains unbroken. Compared to traditional serial or combiner-based hybrid schemes, CHOKE reduces computational and communication costs by an n-fold factor. Furthermore, we show that the communication cost of our construction is optimal under the requirement that each KEM must be used at least once.

Federated learning (FL) is an emerging paradigm that allows a central server to train machine learning models using remote users' data. Despite its growing popularity, FL faces challenges in preserving the privacy of local datasets, its sensitivity to poisoning attacks by malicious users, and its communication overhead, especially in large-scale networks. These limitations are often individually mitigated by local differential privacy (LDP) mechanisms, robust aggregation, compression, and user selection techniques, which typically come at the cost of accuracy. In this work, we presentcompressed private aggregation (CPA), allowing massive deployments to simultaneously communicate at extremely low bit rates while achieving privacy, anonymity, and resilience to malicious users. CPA randomizes a codebook for compressing the data into a few bits using nested lattice quantizers, while ensuring anonymity and robustness, with a subsequent perturbation to hold LDP. CPA-aided FL is proven to converge in the same asymptotic rate as FL without privacy, compression, and robustness considerations, while satisfying both anonymity and LDP requirements. These analytical properties are empirically confirmed in a numerical study, where we demonstrate the performance gains of CPA compared with separate mechanisms for compression and privacy, as well as its robustness in mitigating the harmful effects of malicious users.

The use of Mutual Information (MI) as a measure to evaluate the efficiency of cryptosystems has an extensive history. However, estimating MI between unknown random variables in a high-dimensional space is challenging. Recent advances in machine learning have enabled progress in estimating MI using neural networks. This work presents a novel application of MI estimation in the field of cryptography. We propose applying this methodology directly to estimate the MI between plaintext and ciphertext in a chosen plaintext attack. The leaked information, if any, from the encryption could potentially be exploited by adversaries to compromise the computational security of the cryptosystem. We evaluate the efficiency of our approach by empirically analyzing multiple encryption schemes and baseline approaches. Furthermore, we extend the analysis to novel network coding-based cryptosystems that provide individual secrecy and study the relationship between information leakage and input distribution.

In this work, we introduce a new technique for taking a single-secret sharing scheme with a general access structure and transforming it into an individually secure multi-secret sharing scheme where every secret has the same general access structure. To increase the information rate, we consider Individual Security which guarantees zero mutual information with each secret individually, for any unauthorized subsets. Our approach involves identifying which shares of the single-secret sharing scheme can be replaced by linear combinations of messages. When$m-1$shares are replaced, our scheme obtains an information rate of$m/\vert S\vert$, where$S$is the set of shares. This provides an improvement over the information rate of$1/\vert S\vert$in the original single-secret sharing scheme.

We consider the problem of secure distributed ma-trix multiplication in which a user wishes to compute the product of two matrices with the assistance of honest but curious servers. We show how to construct polynomial schemes for the outer product partitioning which take advantage of the user's ability to precompute, and provide bounds for our technique. We show that precomputation allows for a reduction in the order of the time complexity for the cases where the number of colluding servers is a fixed percentage of the number of servers. Furthermore, with precomputation, any percentage (less than 100%) of collusions can be tolerated, compared to the upper limit of 50% for the case without precomputation.

We present a novel multi-legitimate-users hybrid universal network-coding cryptosystem which provides secure Post-Quantum (PQ) cryptography at high communication rates for users with varying levels of data access permission. In previous work, which considered only a single legitimate user network, it was shown how to combine an information-theoretically secure encoder together with partial encryption to obtain PQ security guarantees, even in the presence of an all-observing eavesdropper. This construction was called HUNCC. We provide a new hybrid PQ cryptosystem for broadcast setting, calling it B-HUNCC. Specifically, we consider a scenario in which there are two sets of messages: public messages, which must be available to all legitimate “restricted and unrestricted” users in the noiseless network, and confidential messages, which must be available only to unrestricted users with appropriate access permission and hidden from other users in the multi-path noiseless network. Under this multi-legitimate-user setting, we provide an efficient hybrid solution: i) A capacity-achieving individually secure broadcast coding scheme that guarantees individual information-theoretic security for restricted users who can select to obtain any subset of the links and ii) a PQ cryptosystem that, by post-encrypting a small part of the transmitted data, guarantees individual indistinguishability under chosen ciphertext attack (individual IND-CCA1) against restricted users who may obtain the entirety network's links but without appropriate access permission, at high information rates.

Linear hashes are known to possess error-correcting capabilities. However, in most applications, non-linear hashes with pseudorandom outputs are utilized instead. It has also been established that classical non-systematic random codes, both linear and non-linear, are capacity achieving in the asymptotic regime. Thus, it is reasonable to expect that non-linear hashes might also exhibit good error-correcting capabilities. In this paper, we show this to be the case. Our proof is based on techniques from multiple access channels. As a consequence, we show that Systematic Random Non-Linear Codes (S-RNLC) are capacity achieving in the asymptotic regime. We validate our results by comparing the performance of the Secure Hash Algorithm (SHA) with that of Systematic Random Linear Codes (SRLC) and S-RNLC, demonstrating that SHA performs equally.

Federated learning (FL) allows a central server to train a model using remote users’ data. FL faces challenges in preserving the local datasets privacy and in its communication overhead; which is considerably dominant in large-scale networks. These limitations are often mitigated individually by local differential privacy (LDP) mechanisms, compression, and user-selection techniques, which often come at the cost of accuracy. In this work we present compressed private aggregation (CPA), which allows massive deployments to simultaneously communicate at extremely low bit-rates while achieving privacy, anonymity, and resilience to malicious users. CPA randomizes a code-book for compressing the data into a few bits, ensuring anonymity and robustness, with a subsequent perturbation to hold LDP. We provide both a theoretical analysis and a numerical study, demonstrating the performance gains of CPA compared with separate mechanisms for compression and privacy.

The problem of mismatched guesswork considers the additional cost incurred by using a guessing function which is optimal for a distribution q when the random variable to be guessed is actually distributed according to a different distribution p. This problem has been well-studied from an asymptotic perspective, but there has been little work on quantifying the difference in guesswork between optimal and suboptimal strategies for a finite number of symbols. In this non-asymptotic regime, we consider a definition for mismatched guesswork which we show is equivalent to a variant of the Kendall tau permutation distance applied to optimal guessing functions for the two distributions. We use this formulation to bound the cost of guesswork under mismatch given a bound on the total variation distance between those distributions.

With the large bandwidths available in the terahertz regime, directional transmissions can exhibit angular dispersion, i.e., frequency-dependent radiation direction. Unfortunately, angular dispersion introduces new security threats as increased bandwidth necessarily yields a larger signal footprint in the spatial domain and potentially benefits an eavesdropper. This paper is the first study of secure transmission strategies on angularly dispersive links. Based on information theoretic foundations, we propose a transmission strategy that channelizes the wideband transmission in frequency, and performs secure coding across frequency channels. With model-driven evaluations and over-the-air experiments, we show that the proposed method exploits the properties of angular dispersion to realize secure wideband transmissions, despite the increased signal footprint and even for practical irregular beams with side lobes and asymmetry. In contrast, without the proposed cross-channel coding strategy, angularly dispersive links can suffer from significant security degradation when bandwidth increases. In addition, we find that the security degradation due to bandwidth increment for angularly dispersive links is secondary compared to other factors including the selected secrecy rate or the directivity of the link. Nonetheless, we find that a higher angular dispersion level, i.e., a larger angular spread with the same bandwidth, results in a higher security degradation as bandwidth increases.

We consider the problem of secure and reliable communication over a noisy multipath network. Previous work considering a noiseless version of our problem proposed a hybrid universal network coding cryptosystem (HUNCC). By combining an information-theoretically secure encoder together with partial encryption, HUNCC is able to obtain security guarantees, even in the presence of an all-observing eavesdropper. In this paper, we propose a version of HUNCC for noisy channels (N-HUNCC). This modification requires four main novelties. First, we present a network coding construction which is jointly, individually secure and error-correcting. Second, we introduce a new security definition which is a computational analogue of individual security, which we call individual indistinguishability under chosen ciphertext attack (individual IND-CCA1), and show that N-HUNCC satisfies it. Third, we present a noise based decoder for N-HUNCC, which permits the decoding of the encoded-then-encrypted data. Finally, we discuss how to select parameters for N-HUNCC and its error-correcting capabilities.

This paper is eligible for the Jack Keil Wolf ISIT Student Paper Award. We generalize a previous framework for designing utility-optimal differentially private (DP) mechanisms via graphs, where datasets are vertices in the graph and edges represent dataset neighborhood. The boundary set contains datasets where an individual’s response changes the binary-valued query compared to its neighbors. Previous work was limited to the homogeneous case where the privacy parameter ε across all datasets was the same and the mechanism at boundary datasets was identical. In our work, the mechanism can take different distributions at the boundary and the privacy parameter ε is a function of neighboring datasets, which recovers an earlier definition of personalized DP as special case. The problem is how to extend the mechanism, which is only defined at the boundary set, to other datasets in the graph in a computationally efficient and utility optimal manner. Using the concept of strongest induced DP condition we solve this problem efficiently in polynomial time (in the size of the graph).

We extend a previous framework for designing differentially private (DP) mechanisms via randomized graph colorings that was restricted to binary functions, corresponding to colorings in a graph, to multi-valued functions. As before, datasets are nodes in the graph and any two neighboring datasets are connected by an edge. In our setting, we assume that each dataset has a preferential ordering for the possible outputs of the mechanism, each of which we refer to as a rainbow. Different rainbows partition the graph of datasets into different regions. We show that if the DP mechanism is pre-specified at the boundary of such regions and behaves identically for all same-rainbow boundary datasets, at most one optimal such mechanism can exist and the problem can be solved by means of a morphism to a line graph. We then show closed form expressions for the line graph in the case of ternary functions. Treatment of ternary queries in this paper displays enough richness to be extended to higher-dimensional query spaces with preferential query ordering, but the optimality proof does not seem to follow directly from the ternary proof.

A notable result from analysis of Boolean functions is the Basic Invariance Principle (BIP), a quantitative nonlinear generalization of the Central Limit Theorem for multilinear polynomials. We present a generalization of the BIP for bivariate multilinear polynomials, i.e., polynomials over two n-length sequences of random variables. This bivariate invariance principle arises from an iterative application of the BIP to bound the error in replacing each of the two input sequences. In order to prove this invariance principle, we first derive a version of the BIP for random multilinear polynomials, i.e., polynomials whose coefficients are random variables. As a benchmark, we also state a naive bivariate invariance principle which treats the two input sequences as one and directly applies the BIP. Neither principle is universally stronger than the other, but we do show that for a notable class of bivariate functions, which we term separable functions, our subtler principle is exponentially tighter than the naive benchmark.

With the large bandwidths available in the terahertz regime, directional transmissions can exhibit angular dispersion, i.e., frequency-dependent radiation direction. Unfortunately, angular dispersion introduces new security threats as increased bandwidth necessarily yields a larger signal footprint in the spatial domain and potentially benefits an eavesdropper. This paper is the first study of secure transmission strategies on angularly dispersive links. Based on information theoretic foundations, we propose to channelize the wideband transmission in frequency, and perform secure coding across frequency channels. With over-the-air experiments, we show that the proposed method exploits the properties of angular dispersion to realize secure wideband transmissions, despite the increased signal footprint and even for practical irregular beams with side lobes and asymmetry. In contrast, without the proposed cross-channel coding strategy, angularly dispersive links can suffer from significant security degradation when bandwidth increases.

We present a framework for designing differentially private (DP) mechanisms for binary functions via a graph representation of datasets. Datasets are nodes in the graph and any two neighboring datasets are connected by an edge. The true binary function we want to approximate assigns a value (or true color) to a dataset. Randomized DP mechanisms are then equivalent to randomized colorings of the graph. A key notion we use is that of the boundary of the graph. Any two neighboring datasets assigned a different true color belong to the boundary. Under this framework, we show that fixing the mechanism behavior at the boundary induces a unique optimal mechanism. Moreover, if the mechanism is to have a homogeneous behavior at the boundary, we present a closed expression for the optimal mechanism, which is obtained by means of a pullback operation on the optimal mechanism of a line graph. For balanced mechanisms, not favoring one binary value over another, the optimal (ε, 6)-DP mechanism takes a particularly simple form, depending only on the minimum distance to the boundary, on ε, and on 6. A full version of this paper can be found in [1].

We study the differentially private multi-group aggregation (PMGA) problem. This setting involves a single server and$n$users. Each user belongs to one of$k$distinct groups and holds a discrete value. The goal is to design schemes that allow the server to find the aggregate (sum) of the values in each group (with high accuracy) under communication and local differential privacy constraints. The privacy constraint guarantees that the user’s group remains private. This is motivated by applications where a user’s group can reveal sensitive information, such as his religious and political beliefs, health condition, or race. We propose a novel scheme, dubbed Query and Aggregate (Q&A) for PMGA. The novelty of Q&A is that it is an interactive aggregation scheme. In Q&A, each user is assigned a random query matrix, to which he sends the server an answer based on his group and value. We characterize the Q&A scheme’s performance in terms of accuracy (MSE), privacy, and communication. We compare Q&A to the Randomized Group (RG) scheme, which is non-interactive and adapts existing randomized response schemes to the PMGA setting. We observe that typically Q&A outperforms RG, in terms of privacy vs. utility, in the high privacy regime.

Distributed computation plays an essential role in cloud and edge computing. Data such as images, audio, and text can be represented as matrices to facilitate efficient computation, especially in the domains of distributed machine learning, computer vision, and signal processing. Many coded computation algorithms have been proposed for big data applications to securely partition and distribute matrices to parallel worker devices. However, these proposals have yet to be adapted for mobile platforms beyond theoretical means. Mobile IoT networks can greatly benefit from secure distributed computing, however, commercial devices such as smartphones and tablets are much more limited in resources compared to platforms in data centers, requiring special design considerations. We investigate existing distribution schemes from an operational complexity and security viewpoint and study their performance in several mobile IoT networks, identifying performance bottlenecks in regards to communication and computation costs. From our findings, we propose new, scalable algorithms optimized to handle the unique constraints of mobile IoT. Extensive evaluations of our proposals on publicly available image classification datasets show how distributed learning can be specially optimized to enhance runtime and battery performance on mobile IoT by over 10×.

We present a wideband time frequency coding scheme which combines the impulsive frequency shift keying scheme, shown to achieve the additive white Gaussian noise channel capacity in the wideband regime, with pulse position modulation. This coding scheme allows for information to be encoded in the position of the signal, which impulsive frequency shift keying does not take advantage of. We show that this scheme achieves rates which are comparable with the additive white Gaussian noise channel capacity upper bound, and performs well under a wide range of fading statistics and bandwidths. We show that our proposed scheme outperforms the impulsive frequency shift keying in lower bandwidths, even without optimization of the duty cycle. The scheme is also shown to perform similarly to impulsive frequency shift keying with smaller duty cycles in the wideband regime, indicating that continually decreasing duty cycles are not necessary to achieve rates on the order of additive white Gaussian noise channel capacity. We also discuss comparisons with other spread-spectrum signaling methods under noncoherent fading.

We study a class of private information retrieval (PIR) methods that we call one-shot schemes. The intuition behind one-shot schemes is the following. The user's query is regarded as a dot product of a query vector and the message vector (database) stored at multiple servers. Privacy, in an information theoretic sense, is then achieved by encrypting the query vector using a secure linear code, such as secret sharing. Several PIR schemes in the literature, in addition to novel ones constructed here, fall into this class. One-shot schemes provide an insightful link between PIR and data security against eavesdropping. However, their download rate is not optimal, i.e., they do not achieve the PIR capacity. Our main contribution is two transformations of one-shot schemes, which we call refining and lifting. We show that refining and lifting one-shot schemes gives capacity-achieving schemes for the cases when the PIR capacity is known. In the other cases, when the PIR capacity is still unknown, refining and lifting one-shot schemes gives, for most parameters, the best download rate so far.

We consider the problem of secure distributed matrix multiplication (SDMM) in which a user wishes to compute the product of two matrices with the assistance of honest but curious servers. We construct polynomial codes for SDMM by studying a combinatorial problem on a special type of addition table, which we call the degree table. The codes are based on arithmetic progressions, and are thus named GASP (Gap Additive Secure Polynomial) Codes. GASP Codes are shown to outperform all previously known polynomial codes for secure distributed matrix multiplication in terms of download rate.

We consider the problem of secure distributed matrix multiplication (SDMM) in which a user wishes to compute the product of two matrices with the assistance of honest but curious servers. We construct polynomial codes for SDMM by studying a recently introduced combinatorial tool called the degree table. Maximizing the download rate of a polynomial code for SDMM is equivalent to minimizing N, the number of distinct elements in the corresponding degree table. We propose new constructions of degree tables with a low number of distinct elements. These new constructions lead to a general family of polynomial codes for SDMM, which we call GASP,. (Gap Additive Secure Polynomial codes) parametrized by an integer r. GASProutperforms all previously known polynomial codes for SDMM. We also present lower bounds on N and show that GASPrachieves the lower bounds in the case of no server collusion.

We study private information retrieval (PIR) on coded data with possibly colluding servers. Devising PIR schemes with optimal download rate in the case of collusion and coded data is still open in general. We provide a lifting operation that can transform what we call one-shot PIR schemes for two messages into schemes for any number of messages. We apply this lifting operation on existing PIR schemes and describe two immediate implications. First, we obtain novel PIR schemes with improved download rate in the case of MDS coded data and server collusion. Second, we provide a simplified description of existing optimal PIR schemes on replicated data as lifted secret sharing based PIR.

This paper introduces BIGnav, a new multiscale navigation technique based on Bayesian Experimental Design where the criterion is to maximize the information-theoretic concept of mutual information, also known as information gain. Rather than simply executing user navigation commands, BIGnav interprets user input to update its knowledge about the user's intended target. Then it navigates to a new view that maximizes the information gain provided by the user's expected subsequent input. We conducted a controlled experiment demonstrating that BIGnav is significantly faster than conventional pan and zoom and requires fewer commands for distant targets, especially in non-uniform information spaces. We also applied BIGnav to a realistic application and showed that users can navigate to highly probable points of interest on a map with only a few steps. We then discuss the tradeoffs of BIGnav--including efficiency vs. increased cognitive load--and its application to other interaction tasks.

Considering a poset metric as a generalization of Hamming's metric, the packing radius of a code is not necessarily a function of the minimal distance. In this work we show, without any restriction on the poset, that the relation between the weight and the packing radius of a vector is equivalent to a generalization of the classical partition problem. We also generalize the well renown heuristic and deterministic algorithms of Karmakar-Karp and Korf, respectively, using an algebraic approach to the Differencing Method.