Membership inference attacks (MIAs) pose a significant threat to the privacy of machine learning models and are widely used as tools for privacy assessment, auditing, and machine unlearning. While prior MIA research has primarily focused on performance metrics such as AUC, accuracy, and TPR@low FPR—either by developing new methods to enhance these metrics or using them to evaluate privacy solutions—we found that it overlooks the disparities among different attacks. These disparities, both between distinct attack methods and between multiple instantiations of the same method, have crucial implications for the reliability and completeness of MIAs as privacy evaluation tools. In this paper, we systematically investigate these disparities through a novel framework based on coverage and stability analysis. Extensive experiments reveal significant disparities in MIAs, their potential causes, and their broader implications for privacy evaluation. To address these challenges, we propose an ensemble framework with three distinct strategies to harness the strengths of state-of-the-art MIAs while accounting for their disparities. This framework not only enables the construction of more powerful attacks but also provides a more robust and comprehensive methodology for privacy evaluation.

Recent work on large language models (LLMs) has increasingly focused on post-training and alignment with datasets curated to enhance instruction following, world knowledge, and specialized skills. However, most post-training datasets used in leading open- and closed-source LLMs remain inaccessible to the public, with limited information about their construction process. This lack of transparency has motivated the recent development of open-source post-training corpora. While training on these open alternatives can yield performance comparable to that of leading models, systematic comparisons remain challenging due to the significant computational cost of conducting them rigorously at scale, and are therefore largely absent. As a result, it remains unclear how specific samples, task types, or curation strategies influence downstream performance when assessing data quality. In this work, we conduct the first comprehensive side-by-side analysis of two prominent open post-training datasets: Tulu-3-SFT-Mix and SmolTalk. Using the Magpie framework, we annotate each sample with detailed quality metrics, including turn structure (single-turn vs. multi-turn), task category, input quality, and response quality, and we derive statistics that reveal structural and qualitative similarities and differences between the two datasets. Based on these insights, we design a principled curation recipe that produces a new data mixture, TuluTalk, which contains 14% fewer samples than either source dataset while matching or exceeding their performance on key benchmarks. Our findings offer actionable insights for constructing more effective post-training datasets that improve model performance within practical resource limits. To support future research, we publicly release both the annotated source datasets and our curated TuluTalk mixture.

The Singleton bound provides a fundamental limit on the maximum possible size of an error-correcting code of a given length and distance. However, recent work by Zhang et. al. [IEEE Trans. Comm., Dec. 2023] showed that in the context of the wiretap multipath network when the adversary has limited knowledge about the codewords and a vanishing probability of decoding error is permitted, a rate higher than the Singleton bound is achievable. Their results, however, are confined to an ideal setting where the adversary is allowed to behave non-causally. Motivated by real-world scenarios, this work considers communication over a wiretap multipath network in the presence of a causal adversary (i.e., the adversary which is only allowed to use the observations up to the current time slot to decide the current jamming strategy) and in the presence of passive feedback from the receiver to the transmitter. We characterize both the capacity and secrecy capacity of the wiretap multipath network, either with or without passive feedback. We observe that in comparison to the non-causal and non-feedback setting, the capacity and secrecy capacity can be strictly higher for a wide variety of parameters, demonstrating the benefits of causality and feedback.

We propose LESS-VFL, a communication-efficient feature selection method for distributed systems with vertically partitioned data. We consider a system of a server and several parties with local datasets that share a sample ID space but have different feature sets. The parties wish to collaboratively train a model for a prediction task. As part of the training, the parties wish to remove unimportant features in the system to improve generalization, efficiency, and explainability. In LESS-VFL, after a short pre-training period, the server optimizes its part of the global model to determine the relevant outputs from party models. This information is shared with the parties to then allow local feature selection without communication. We analytically prove that LESS-VFL removes spurious features from model training. We provide extensive empirical evidence that LESS-VFL can achieve high accuracy and remove spurious features at a fraction of the communication cost of other feature selection approaches.

Maximum distance separable (MDS) codes are often considered to have the optimal error correction capability against malicious adversaries because they achieve the Singleton bound in terms of the rate-distance tradeoff. However, by allowing a vanishing probability of decoding error and considering an adversary with limited knowledge, it is interesting to understand whether a rate higher than the Singleton bound is achievable, and if so, what the optimal rate is. To answer these questions, we instantiate the aforementioned problem as a communication problem where the transmission medium is a wiretap multipath network that consists of multiple parallel links. A malicious adversary is able to eavesdrop on a subset of links, and also jam on a potentially overlapping subset of links. The primary objective is to ensure the communication is robust to adversarial jamming; additionally, another goal is to guarantee that the communication is information-theoretically secure with respect to the adversary. We present a complete characterization of both capacity and secrecy capacity as functions of the number of links that can be eavesdropped and/or jammed. Our achievability schemes are computationally efficient, and rely on a non-trivial combination of MDS codes and a pairwise hashing scheme.

Federated learning has emerged as a privacy-preserving machine learning approach where multiple parties can train a single model without sharing their raw training data. Federated learning typically requires the utilization of multi-party computation techniques to provide strong privacy guarantees by ensuring that an untrusted or curious aggregator cannot obtain isolated replies from parties involved in the training process, thereby preventing potential inference attacks. Until recently, it was thought that some of these secure aggregation techniques were sufficient to fully protect against inference attacks coming from a curious aggregator. However, recent research has demonstrated that a curious aggregator can successfully launch a disaggregation attack to learn information about model updates of a target party. This paper presents DeTrust-FL, an efficient privacy-preserving federated learning framework for addressing the lack of transparency that enables isolation attacks, such as disaggregation attacks, during secure aggregation by assuring that parties’ model updates are included in the aggregated model in a private and secure manner. DeTrust-FL proposes a decentralized trust consensus mechanism and incorporates a recently proposed decentralized functional encryption scheme in which all parties agree on a participation matrix before collaboratively generating decryption key fragments, thereby gaining control and trust over the secure aggregation process in a decentralized setting. Our experimental evaluation demonstrates that DeTrust-FL outperforms state-of-the-art FE-based secure multi-party aggregation solutions in terms of training time and reduces the volume of data transferred. In contrast to existing approaches, this is achieved without creating any trust dependency on external trusted entities.

Shamir's secret sharing scheme is widely used in many cryptographic protocols such as secure multi-party computation. It allows a secret to be distributed to$n$parties such that any$t$parties learn no information about the secret, whereas any$t+1$parties can recover the secret. However, the worst-case recovery guarantees come at the price of$O(n^{2})$computation cost. This quadratic cost limits its scalability to applications involving only a small number of participants. This paper presents a framework, called FastShare, for designing secret sharing schemes that ensures worst-case security guarantees at a lower computation cost by relaxing the recovery constraint from worst-case to average-case in a statistical sense. In particular, FastShare considers the setup where each party takes part in the recovery process with some probability$\rho$, independently of others. The core idea of FastShare is to construct a ‘signal’ using the secret and random masks by inserting zeros at judiciously chosen locations, and take its finite field fast Fourier transform (FFT) to generate the shares. We present a scheme designed using FastShare where the judicious zero placement ensures that the shares form a codeword of a locally recoverable code. The locality property along with the FFT allows us to recover the secret with$O(n\log n)$computational complexity, from a ‘random’ subset of shares of large enough size. We analyze its security and recovery thresholds, and characterize a trade-off between$\rho$and the probability of successfully recovering the secret. Further, we carry out numerical simulations to demonstrate the applicability of the proposed scheme for a wide range of values of$n$.

We study the problem of estimating at a central server the mean of a set of vectors distributed across several nodes (one vector per node). When the vectors are high-dimensional, the communication cost of sending entire vectors may be prohibitive, and it may be imperative for them to use sparsification techniques. While most existing work on sparsified mean estimation is agnostic to the characteristics of the data vectors, in many practical applications such as federated learning, there may be spatial correlations (similarities in the vectors sent by different nodes) or temporal correlations (similarities in the data sent by a single node over different iterations of the algorithm) in the data vectors. We leverage these correlations by simply modifying the decoding method used by the server to estimate the mean. We provide an analysis of the resulting estimation error as well as experiments for PCA, K-Means and Logistic Regression, which show that our estimators consistently outperform more sophisticated and expensive sparsification methods.

The paper presents techniques for analyzing the expected download time in distributed storage systems that employ systematic availability codes. These codes provide access to hot data through the systematic server containing the object and multiple recovery groups. When a request for an object is received, it can be replicated (forked) to the systematic server and all recovery groups. We first consider the low-traffic regime and present the close-form expression for the download time. By comparison across systems with availability, maximum distance separable (MDS), and replication codes, we demonstrate that availability codes can reduce download time in some settings but are not always optimal. In the high-traffic regime, the system contains multiple inter-dependent Fork-Join queues, making exact analysis intractable. Accordingly, we present upper and lower bounds on the download time, and an M/G/1 queue approximation for several cases of interest. Via extensive numerical simulations, we evaluate our bounds and demonstrate that the M/G/1 queue approximation has a high degree of accuracy.

Erasure coding has been recognized as a powerful method to mitigate delays due to slow or straggling nodes in distributed systems. This work shows that erasure coding of data objects can flexibly handle skews in the request rates. Coding can help boost theservice rate region, that is, increase the overall volume of data access requests that the system can handle. This paper aims to postulate the service rate region as an important consideration in the design of erasure-coded distributed systems. We highlight several open problems that can be grouped into two broad threads: 1) characterizing the service rate region of a given code and finding the optimal request allocation, and 2) designing the underlying erasure code for a given service rate region. As contributions along the first thread, we find the rate regions of maximum-distance-separable, locally repairable, and simplex codes. We show the effectiveness of hybrid codes that combine replication and erasure coding in terms of code design. We also discover fundamental connections between multi-set batch codes and the problem of maximizing the service rate region.

Motivated by recent developments in serverless systems for large-scale computation as well as improvements in scalable randomized matrix algorithms, we develop OverSketched Newton, a randomized Hessian-based optimization algorithm to solve large-scale convex optimization problems in serverless systems. OverSketched Newton leverages matrix sketching ideas from Randomized Numerical Linear Algebra to compute the Hessian approximately. These sketching methods lead to inbuilt resiliency against stragglers that are a characteristic of serverless architectures. Depending on whether or not the problem is strongly convex, we propose different iteration updates using the approximate Hessian. For both cases, we establish convergence guarantees for OverSketched Newton, and we empirically validate our results by solving large-scale supervised learning problems on real-world datasets. Experiments demonstrate a reduction of ~50% in total running time on AWS Lambda, compared to state-of-the-art distributed optimization schemes.

We develop a communication-efficient distributed learning algorithm that is robust against Byzantine worker machines. We propose and analyze a distributed gradient-descent algorithm that performs a simple thresholding based on gradient norms to mitigate Byzantine failures. We show the (statistical) error-rate of our algorithm matches that of Yin et al., 2018, which uses more complicated schemes (like coordinate-wise median or trimmed mean). Furthermore, for communication efficiency, we consider a generic class of δ-approximate compressors from Karimireddy et al., 2019, that encompasses sign-based compressors and top-k sparsification. Our algorithm uses compressed gradients and gradient norms for aggregation and Byzantine removal respectively. We establish the statistical error rate of the algorithm for arbitrary (convex or non-convex) smooth loss function. We show that, in certain regime of δ, the rate of convergence is not affected by the compression operation. We have experimentally validated our results and shown good performance in convergence for convex (least-square regression) and non-convex (neural network training) problems.

Distributed implementations of gradient-based methods, wherein a server distributes gradient computations across worker machines, need to overcome two limitations: delays caused by slow running machines called stragglers, and communication overheads. Recently, Ye and Abbe [ICML 2018] proposed a coding-theoretic paradigm to characterize a fundamental trade-off between computation load per worker, communication overhead per worker, and straggler tolerance. However, their proposed coding schemes suffer from heavy decoding complexity and poor numerical stability. In this paper, we develop a communication-efficient gradient coding framework to overcome these drawbacks. Our proposed framework enables using any linear code to design the encoding and decoding functions. When a particular code is used in this framework, its block-length determines the computation load, dimension determines the communication overhead, and minimum distance determines the straggler tolerance. The flexibility of choosing a code allows us to gracefully trade-off the straggler threshold and communication overhead for smaller decoding complexity and higher numerical stability. Further, we show that using a maximum distance separable (MDS) code generated by a random Gaussian matrix in our framework yields a gradient code that is optimal with respect to the trade-off and, in addition, satisfies stronger guarantees on numerical stability as compared to the previously proposed schemes. Finally, we evaluate our proposed framework on Amazon EC2 and demonstrate that it reduces the average iteration time by 16% as compared to prior gradient coding schemes.

We consider the problem of stealthy communication over a multipath network in the presence of an active adversary. The multipath network consists of multiple parallel noiseless links, and the adversary is able to eavesdrop and jam a subset of links. We consider two types of jamming- erasure jamming and overwrite jamming. We require the communication to be both stealthy and reliable, i.e., the adversary should be unable to detect whether or not meaningful communication is taking place, while the legitimate receiver should reconstruct any potential messages from the transmitter with high probability simultaneously. We provide inner and outer bounds on the stealthy capacities under both adversarial erasure and adversarial overwrite jamming.

We study the problem of Private Information Retrieval (PIR) in the presence of prior side information. The problem setup includes a database of K independent messages possibly replicated on several servers, and a user that needs to retrieve one of these messages. In addition, the user has some prior side information in the form of a subset of M messages, not containing the desired message and unknown to the servers. This problem is motivated by practical settings in which the user can obtain side information opportunistically from other users or has previously downloaded some messages using classical PIR schemes. The objective of the user is to retrieve the required message with downloading minimum amount of data from the servers while achieving information-theoretic privacy in one of the following two scenarios: (i) the user wants to protect jointly the identities of the demand and the side information; (ii) the user wants to protect only the identity of the demand, but not necessarily the side information. To highlight the role of side information, we focus first on the case of a single server (single database). In the first scenario, we prove that the minimum download cost is K - M messages, and in the second scenario it is [K/(M + 1)] messages, which should be compared to K messages-the minimum download cost in the case of no side information. Then, we extend some of our results to the case of the database replicated on multiple servers. Our proof techniques relate PIR with side information to the index coding problem. We leverage this connection to prove converse results, as well as to design achievability schemes.

We consider a multi-user variant of the private information retrieval problem described as follows. Suppose there are D users, each of which wants to privately retrieve a distinct message from a server with the help of a trusted agent. We assume that the agent has a subset of M messages whose indices are unknown to the server. The goal of the agent is to collectively retrieve the users' requests from the server. For this problem, we introduce the notion of individual-privacy - the agent is required to protect the privacy only for each individual user (but may leak some correlations among user requests). We refer to this problem as Individually-Private Information Retrieval with Side Information (IPIR-SI).We first establish a lower bound on the capacity, which is defined as the maximum achievable download rate, of the IPIR-SI problem by presenting a novel achievability protocol. Next, we characterize the capacity of IPIR-SI problem for M = 1 and D = 2. In the process of characterizing the capacity for arbitrary M and D we present a novel combinatorial conjecture, that may be of independent interest.

Distributed implementations of gradient-based methods, wherein a server distributes gradient computations across worker machines, suffer from slow running machines, called stragglers. Gradient coding is a coding-theoretic framework to mitigate stragglers by enabling the server to recover the gradient sum in the presence of stragglers. Approximate gradient codes are variants of gradient codes that reduce computation and storage overhead per worker by allowing the server to approximately reconstruct the gradient sum.In this work, our goal is to construct approximate gradient codes that are resilient to stragglers selected by a computationally unbounded adversary. Our motivation for constructing codes to mitigate adversarial stragglers stems from the challenge of tackling stragglers in massive-scale elastic and serverless systems, wherein it is difficult to statistically model stragglers. Towards this end, we propose a class of approximate gradient codes based on balanced incomplete block designs (BIBDs). We show that the approximation error for these codes depends only on the number of stragglers, and thus, adversarial straggler selection has no advantage over random selection. In addition, the proposed codes admit computationally efficient decoding at the server. Next, to characterize fundamental limits of adversarial straggling, we consider the notion of adversarial threshold - the smallest number of workers that an adversary must straggle to inflict certain approximation error. We compute a lower bound on the adversarial threshold, and show that codes based on symmetric BIBDs maximize this lower bound among a wide class of codes, making them excellent candidates for mitigating adversarial stragglers.

Pseudo-Boolean functions are functions whose input variables are binary and output is in the real numbers. These functions show up in many different applications in computer science, finance and economics to name a few. Pseudo-Boolean functions lend themselves to a spectral representation, which is closely related to the Walsh-Hadamard Transform from signal processing. In some problems, the coefficients of the spectral representation are active only on the low-degree terms. In this work, we present a method for computationally-efficient recovery of these low-degree coefficients. Our method is based on evaluating the input pseudo-Boolean function at points given by the codewords of a codebook, and then performing a Walsh-Hadamard Transform on the resulting signal. Codes having high rates and good minimum distance properties yield sets of evaluations points whose size is close to the number of low-degree coefficients. In particular perfect codes, such as Hamming Codes or the Golay Code, enable efficient recovery with optimal number of evaluations of the function.

Private Information Retrieval (PIR) problem has recently attracted a significant interest in the information-theory community. In this problem, a user wants to privately download one or more messages belonging to a database with copies stored on a single or multiple remote servers. In the single server scenario, the user must have prior side information, i.e., a subset of messages unknown to the server, to be able to privately retrieve the required messages in an efficient way.In the last decade, there has also been a significant interest in Locally Recoverable Codes (LRCs), a class of storage codes in which each symbol can be recovered from a limited number of other symbols. More recently, there is an interest in cooperative locally recoverable codes, i.e., codes in which multiple symbols can be recovered from a small set of other code symbols.In this paper, we establish a relationship between coding schemes for the single-server PIR problem and LRCs. In particular, we show the following results: (i) PIR schemes designed for retrieving a single message are equivalent to classical LRCs; and (ii) PIR schemes for retrieving multiple messages are equivalent to cooperative LRCs. These equivalence results allow us to recover upper bounds on the download rate for PIR-SI schemes, and to obtain a novel rate upper bound on cooperative LRCs. We show results for both linear and non-linear codes.

We extend the notion of locality from the Hamming metric to the rank and subspace metrics. Our main contribution is to construct a class of array codes with locality constraints in the rank metric. Our motivation for constructing such codes stems from the need to design codes for efficient data recovery from correlated and/or mixed (i.e., complete and partial) failures in distributed storage systems. Specifically, the proposed local rank-metric codes can recover locally from crisscross errors and erasures, which affect a limited number of rows and/or columns of the storage array. We also derive a Singlet-on-like upper bound on the minimum rank distance of (linear) codes with rank-locality constraints. Our proposed construction achieves this bound for a broad range of parameters. The construction builds upon Tamo and Barg's method for constructing locally repairable codes with optimal minimum Hamming distance. Finally, we construct a class of constant-dimension subspace codes (also known as Grassmannian codes) with locality constraints in the subspace metric. The key idea is to show that a Grassmannian code with locality can be easily constructed from a rank-metric code with locality by using the lifting method proposed by Silva et al. We present an application of such codes for distributed storage systems, wherein nodes are connected over a network that can introduce errors and erasures.

Quantum error-correcting codes can be used to protect qubits involved in quantum computation. This requires that logical operators acting on protected qubits be translated to physical operators (circuits) acting on physical quantum states. We propose a mathematical framework for synthesizing physical circuits that implement logical Clifford operators for stabilizer codes. Circuit synthesis is enabled by representing the desired physical Clifford operator in CN×Nas a 2m×2m binary sym-plectic matrix, where N=2m. We show that for an [[ m, m-k ]] stabilizer code every logical Clifford operator has 2k(k+1)/2symplectic solutions, and we enumerate them efficiently using symplectic transvections. The desired circuits are then obtained by writing each of the solutions as a product of elementary symplectic matrices. For a given operator, our assembly of all of its physical realizations enables optimization over them with respect to a suitable metric. Our method of circuit synthesis can be applied to any stabilizer code, and this paper provides a proof of concept synthesis of universal Clifford gates for the well-known [[ 6,4,2 ]] code. Programs implementing our algorithms can be found at https://github.com/nrenga/symplectic-arxiv18a.

We consider the problem of stealth communication over a multipath network in the presence of an active adversary. The multipath network consists of multiple parallel noiseless links, and the adversary is able to eavesdrop and jam a subset of links. We consider two types of jamming - erasure jamming and overwrite jamming. We require the communication to be both stealthy and reliable, i.e., the adversary should be unable to detect whether or not meaningful communication is taking place, while the legitimate receiver should reconstruct any potential messages from the transmitter with high probability simultaneously. We provide inner bounds on the robust stealth capacities under both adversarial erasure and adversarial overwrite jamming.

A locally repairable code with availability has the property that every code symbol can be recovered from multiple, disjoint subsets of other symbols of small size. In particular, a code symbol is said to have (r, t)-availability if it can be recovered from t disjoint subsets, each of size at most r. A code with availability is said to be rate optimal, if its rate is maximum among the class of codes with given locality, availability, and alphabet size. This paper focuses on rate-optimal binary, linear codes with small availability, and makes three contributions. First, it establishes tight upper bounds on the rate of binary linear codes with (r, 2) and (2, 3) availability. Second, it establishes a uniqueness result for binary rate-optimal codes, showing that for certain classes of binary linear codes with (r, 2) and (2, 3)-availability, any rate-optimal code must be a direct sum of shorter rate-optimal codes. Finally, it presents a class of locally repairable codes associated with convex polyhedra, especially, focusing on the codes associated with the Platonic solids. It demonstrates that these codes are locally repairable with t = 2, and that the codes associated with (geometric) dual polyhedra are (coding theoretic) duals of each other.

We consider the problem of designing repair efficient distributed storage systems, which are information-theoretically secure against a passive eavesdropper that can gain access to a limited number of storage nodes. We present a framework that enables design of a broad range of secure storage codes through a joint construction of inner and outer codes. As case studies, we focus on two specific families of storage codes: (i) minimum storage regenerating (MSR) codes, and (ii) maximally recoverable (MR) codes, which are a class of locally repairable codes (LRCs). The main idea of this framework is to utilize the existing constructions of storage codes to jointly design an outer coset code and inner storage code. Finally, we present a construction of an outer coset code over small field size to secure locally repairable codes presented by Tamo and Barg for the special case of an eavesdropper that can observe any subset of nodes of maximum possible size.

In many practical settings, there is a need to design distributed storage codes with certain locality constraints. For a code C, its i-th symbol is said to have locality r if it can be recovered by accessing some other r symbols of C. Locally repairable codes (LRCs) are the family of codes such that every symbol has small locality.

In distributed storage systems, a special sub-class of locally repairable codes, referred to as availability codes, has been proposed to enable recovery of each data block from one of its repair groups. A repair group typically contains a small number of nodes and does not overlap with any other repair group of the same data block. Availability codes have several important benefits, including high degree of fault tolerance, efficient recovery from failures, and efficient access to data by multiple users. In this paper, we study the availability codes from a queuing-theoretical perspective. Specifically, we analyze the average time necessary to download a block of data under the Poisson request arrival model in two service/scheduling scenarios. We compare the availability codes with several alternatives such as MDS codes and replication schemes. Our results indicate that availability codes can minimize the download time in some settings, but are not always optimal.

We consider the problem of communication over a multi-path network in the presence of a causal adversary. The limited-view causal adversary is able to, based on the current and past observations, eavesdrop on a subset of links and also jam on a potentially overlapping subset of links. The goal is to ensure that the communication takes place reliably and secretly. We study two adversarial models - additive and overwrite jamming. For both adversarial models, we consider communication models both without and with passive feedback from decoder to encoder, i.e., the encoder sees everything that the decoder sees. The problem assumes transmissions are in the large alphabet regime. For both types of jamming models, we find the capacity under three scenarios - reliability without feedback, reliability and secrecy without feedback, and reliability with feedback. We observe that in comparison to the non-causal setting the capacity with a causal adversary is strictly increased for a wide variety of parameter settings, and present our intuition through several examples.

We consider reliable and secure communication of information over a multipath network. A transmitter Alice sends messages to the receiver Bob in the presence of a hidden adversary Calvin. The adversary Calvin can both eavesdrop and jam on (possibly non-identical) subsets of transmission links. The goal is to communicate reliably (intended receiver can understand the messages) and secretly (adversary cannot understand the messages). Two kinds of jamming, additive and overwrite, are considered. Additive jamming corresponds to wireless network model while overwrite jamming corresponds to wired network model and storage systems. The multipath network consists of C parallel links. Calvin can both jam and eavesdrop any zionumber of links, can eavesdrop (but not jam) any zi/onumber of links, and can jam (but not eavesdrop) any zo/inumber of links. We present the first “complete” information-theoretic characterization of maximum achievable rate as a function of the number of links that can be jammed and/or eavesdropped for equal and unequal link capacity multipath networks under additive and overwrite jamming in the large alphabet regime. Our achievability and converse proofs require non-trivial combination of information theoretic and coding theoretic ideas and our achievability schemes are computationally efficient. The PHaSE-Saving techniques1are used for achievability while a “stochastic” singleton bound is obtained for converse.

We consider the scenario wherein a transmitter Alice wants to (potentially) communicate to the intended receiver Bob over a multipath network, i.e., a network consisting of multiple parallel links, in the presence of a passive eavesdropper Willie, who observes an unknown subset of links. A primary goal of our communication protocol is to make the communication “deniable”, i.e., Willie should not be able to reliably estimate whether or not Alice is transmitting any covert information to Bob. Moreover, if Alice is indeed actively communicating, her covert messages should be information-theoretically “hidable” in the sense that Willie's observations should not leak any information about Alice's (potential) message to Bob - our notion of hidability is slightly stronger than the notion of information-theoretic strong secrecy well-studied in the literature. We demonstrate that deniability does not imply either hidability or (weak or strong) information-theoretic secrecy; nor does information-theoretic secrecy imply deniability. We present matching inner and outer bounds on the capacity for deniable and hidable communication over multipath networks.

We survey here recent work pertaining to “deniable” communication - i.e., talking without being detected. We first highlight connections to other related notions (anonymity and secrecy). We then contrast the notions of deniability and secrecy. We highlight similarities and distinctions of deniability with a variety of related notions (LPD communications, stealth, channel resolvability) extant in the literature.