SJSidharth Jaggi

Sidharth Jaggi

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Sidharth Jaggi has a total of 54 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Covert Communication over Adversarially Jammed Channels

    by Qiaosheng Zhang, Mayank Bakshi, Sidharth Jaggi

    Suppose that a transmitter Alice potentially wishes to communicate with a receiver Bob over an adversarially jammed binary channel. An active adversary James eavesdrops on their communication over a binary symmetric channel (BSC(q)), and may maliciously flip (up to) a certain fraction p of their transmitted bits based on his observations. We consider a setting where the communication must be simultaneously covert as well as reliable, i.e., James should be unable to accurately distinguish whether or not Alice is communicating, while Bob should be able to correctly recover Alice's message with high probability regardless of the adversarial jamming strategy. We show that, unlike the setting with passive adversaries, covert communication against active adversaries requires Alice and Bob to have a shared key (of length at least Omega(log n)) even when Bob has a better channel than James. We present lower and upper bounds on the information-theoretically optimal throughput as a function of the channel parameters, the desired level of covertness, and the amount of shared key available. These bounds match for a wide range of parameters of interest. We also develop a computationally efficient coding scheme (based on concatenated codes) when the amount of shared key available is $\Omega(\sqrt{n} \log n)$, and further show that this scheme can be implemented with much less amount of shared key when the adversary is assumed to be computationally bounded.

  • Open Access

    Quadratically Constrained Myopic Adversarial Channels

    by Yihan Zhang, Shashank Vatedka, Sidharth Jaggi, Anand Sarwate

    We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most $2\log(n)$ bits in one sub-regime, and at most $\Omega(n)$ bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability, and a Plotkin-type push attack for the converse in a subregion of the NSRs, both of which which may be of independent interest. We also give bounds on the secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping.

  • Open Access

    Communication Efficient Secret Sharing in the Presence of Malicious Adversary

    by Rawad Bitar, Sidharth Jaggi

    Consider the communication efficient secret sharing problem. A dealer wants to share a secret with $n$ parties such that any $k\leq n$ parties can reconstruct the secret and any $z<k$ parties eavesdropping on their shares obtain no information about the secret. In addition, a legitimate user contacting any $d$, $k\leq d \leq n$, parties to decode the secret can do so by reading and downloading the minimum amount of information needed. We are interested in communication efficient secret sharing schemes that tolerate the presence of malicious parties actively corrupting their shares and the data delivered to the users. The knowledge of the malicious parties about the secret is restricted to the shares they obtain. We characterize the capacity, i.e. maximum size of the secret that can be shared. We derive the minimum amount of information needed to to be read and communicated to a legitimate user to decode the secret from $d$ parties, $k\leq d \leq n$. Error-correcting codes do not achieve capacity in this setting. We construct codes that achieve capacity and achieve minimum read and communication costs for all possible values of $d$. Our codes are based on Staircase codes, previously introduced for communication efficient secret sharing, and on the use of a pairwise hashing scheme used in distributed data storage and network coding settings to detect errors inserted by a limited knowledge adversary.

  • Open Access

    Quadratically Constrained Two-way Adversarial Channels

    by Yihan Zhang, Shashank Vatedka, Sidharth Jaggi

    We study achievable rates of reliable communication in a power-constrained two-way additive interference channel over the real alphabet where communication is disrupted by a power-constrained jammer. This models the wireless communication scenario where two users Alice and Bob, operating in the full duplex mode, wish to exchange messages with each other in the presence of a jammer, James. Alice and Bob simultaneously transmit their encodings $ \underline{x}_A $ and $\underline{x}_B $ over $ n $ channel uses. It is assumed that James can choose his jamming signal $ \underline{s} $ as a noncausal randomized function of $ \underline{x}_A $ and $ \underline{x}_B $, and the codebooks used by Alice and Bob. Alice and Bob observe $ \underline{x}_A+\underline{x}_B +\underline{s}$, and must recover each others' messages reliably. In this article, we provide upper and lower bounds on the capacity of this channel which match each other and equal $ \frac{1}{2}\log\left(\frac{1}{2} + \mathsf{SNR}\right) $ in the high-$\mathsf{SNR}$ regime (where $\mathsf{SNR}$, signal to noise ratios, is defined as the ratio of the power constraints of the users to the power constraint of the jammer). We give a code construction based on lattice codes, and derive achievable rates for large $\mathsf{SNR}$. We also present upper bounds based on two specific attack strategies for James. Along the way, sumset property of lattices for the achievability and general properties of capacity-achieving codes for memoryless channels for the converse are proved, which might be of independent interest.

  • Open Access

    Undetectable Radios: Covert Communication under Spectral Mask Constraints

    by Qiaosheng, Eric Zhang, Matthieu R. Bloch, Mayank Bakshi, Sidharth Jaggi

    We consider the problem of covert communication over continuous-time additive white Gaussian noise (AWGN) channels under spectral mask constraints, wherein two legitimate parties attempt to communicate reliably in the presence of an eavesdropper that should be unable to estimate if communication takes place. The spectral mask constraint is imposed to restrict excessive radiation beyond the bandwidth of interest. We develop a communication scheme with theoretical reliability and covertness guarantees based on pulse amplitude modulation (PAM) with Binary Phase Shift Keying (BPSK) and root raised cosine (RRC) carrier pulses. Given a fixed transmission duration T and a spectral mask with bandwidth parameter W, we show that one can reliably and covertly transmit $O(\sqrt{WT})$ bits of information. We characterize the constant behind the $O$ and show that it is tight under some conditions.

  • Nearly Optimal Sparse Group Testing

    by Venkata Gandikota, Elena Grigorescu, Sidharth Jaggi, Samson Zhou

    Group testing is the process of pooling arbitrary subsets from a set of n items so as to identify, with a minimal number of tests, a “small” subset of d defective items. In “classical” non-adaptive group testing, it is known that when d is substantially smaller than n, Θ(dlog(n)) tests are both information-theoretically necessary and sufficient to guarantee recovery with high probability. Group testing schemes in the literature that meet this bound require most items to be tested Ω(log(n)) times, and most tests to incorporate Ω(n/d) items. Motivated by physical considerations, we study group testing models in which the testing procedure is constrained to be “sparse.” Specifically, we consider (separately) scenarios in which 1) items are finitely divisible and hence may participate in at most γ ∈ o(log(n)) tests; or 2) tests are size-constrained to pool no more than ρ ∈ o(n/d) items per test. For both scenarios, we provide information-theoretic lower bounds on the number of tests required to guarantee high probability recovery. In particular, one of our main results shows that γ-finite divisibility of items forces any non-adaptive group testing algorithm with the probability of recovery error at most ϵ to perform at least γd(n/d) (1-5ϵ)/γ tests. Analogously, for ρ-sized constrained tests, we show an information-theoretic lower bound of Ω(n/ρ) tests for high-probability recovery-hence in both settings the number of tests required grows dramatically (relative to the classical setting) as a function of n. In both scenarios, we provide both randomized constructions and explicit constructions of designs with computationally efficient reconstruction algorithms that require a number of tests that is optimal up to constant or small polynomial factors in some regimes of n, d, γ, and ρ. The randomized design/reconstruction algorithm in the ρ-sized test scenario is universal-independent of the value of d, as long as ρ ∈ o(n/d). We also investigate the effect of unreliability/noise in test outcomes, and show that whereas the impact of noise in test outcomes can be obviated with a small (constant factor) penalty in the number of tests in the ρ-sized tests scenario, there is no group-testing procedure, regardless of the number of tests, that can combat noise in the γ-divisible scenario.


  • Open Access

    Nearly Optimal Sparse Group Testing

    by Venkata Gandikota, Elena Grigorescu, Sidharth Jaggi, Samson Zhou

    Group testing is the process of pooling arbitrary subsets from a set of $n$ items so as to identify, with a minimal number of tests, a "small" subset of $d$ defective items. In "classical" non-adaptive group testing, it is known that when $d$ is substantially smaller than $n$, $\Theta(d\log(n))$ tests are both information-theoretically necessary and sufficient to guarantee recovery with high probability. Group testing schemes in the literature meeting this bound require most items to be tested $\Omega(\log(n))$ times, and most tests to incorporate $\Omega(n/d)$ items. Motivated by physical considerations, we study group testing models in which the testing procedure is constrained to be "sparse". Specifically, we consider (separately) scenarios in which (a) items are finitely divisible and hence may participate in at most $\gamma \in o(\log(n))$ tests; or (b) tests are size-constrained to pool no more than $\rho \in o(n/d)$items per test. For both scenarios we provide information-theoretic lower bounds on the number of tests required to guarantee high probability recovery. In both scenarios we provide both randomized constructions (under both $\epsilon$-error and zero-error reconstruction guarantees) and explicit constructions of designs with computationally efficient reconstruction algorithms that require a number of tests that are optimal up to constant or small polynomial factors in some regimes of $n, d, \gamma,$ and $\rho$. The randomized design/reconstruction algorithm in the $\rho$-sized test scenario is universal -- independent of the value of $d$, as long as $\rho \in o(n/d)$. We also investigate the effect of unreliability/noise in test outcomes. For the full abstract, please see the full text PDF.

  • Open Access

    Computationally Efficient Covert Communication

    by Qiaosheng Zhang, Mayank Bakshi, Sidharth Jaggi

    In this paper, we design the first computationally efficient codes for simultaneously reliable and covert communication over Binary Symmetric Channels (BSCs). Our setting is as follows: a transmitter Alice wishes to potentially reliably transmit a message to a receiver Bob, while ensuring that the transmission taking place is covert with respect to an eavesdropper Willie (who hears Alice's transmission over a noisier BSC). Prior works show that Alice can reliably and covertly transmit O(\sqrt{n}) bits over n channel uses without any shared secret between Alice and Bob. One drawback of prior works is that the computational complexity of the codes designed scales as 2^{\Theta(\sqrt{n})}. In this work we provide the first computationally tractable codes with provable guarantees on both reliability and covertness, while simultaneously achieving the best known throughput for the problem.

  • Open Access

    Quadratically Constrained Channels with Causal Adversaries

    by Tongxin Li, Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg, Anand D. Sarwate

    We consider the problem of communication over a channel with a causal jamming adversary subject to quadratic constraints. A sender Alice wishes to communicate a message to a receiver Bob by transmitting a real-valued length-$n$ codeword $\mathbf{x}=x_1,...,x_n$ through a communication channel. Alice and Bob do not share common randomness. Knowing Alice's encoding strategy, an adversarial jammer James chooses a real-valued length-n noise sequence $\mathbf{s}=s_1,..,s_n$ in a causal manner, i.e., each $s_t (1<=t<=n)$ can only depend on $x_1,...,x_t$. Bob receives $\mathbf{y}$, the sum of Alice's transmission $\mathbf{x}$ and James' jamming vector $\mathbf{s}$, and is required to reliably estimate Alice's message from this sum. In addition, Alice and James's transmission powers are restricted by quadratic constraints $P>0$ and $N>0$. In this work, we characterize the channel capacity for such a channel as the limit superior of the optimal values of a series of optimizations. Upper and lower bounds on the optimal values are provided both analytically and numerically. Interestingly, unlike many communication problems, in this causal setting Alice's optimal codebook may not have a uniform power allocation - for certain SNR, a codebook with a two-level uniform power allocation results in a strictly higher rate than a codebook with a uniform power allocation would.

  • Open Access

    Communication over an Arbitrarily Varying Channel under a State-Myopic Encoder

    by Amitalok J. Budkuley, Sidharth Jaggi

    We study the problem of communication over a discrete arbitrarily varying channel (AVC) when a noisy version of the state is known non-causally at the encoder. The state is chosen by an adversary which knows the coding scheme. A state-myopic encoder observes this state non-causally, though imperfectly, through a noisy discrete memoryless channel (DMC). We first characterize the capacity of this state-dependent channel when the encoder-decoder share randomness unknown to the adversary, i.e., the randomized coding capacity. Next, we show that when only the encoder is allowed to randomize, the capacity remains unchanged when positive. Interesting and well-known special cases of the state-myopic encoder model are also presented.