Annina Bracher

The secrecy of a distributed-storage system for passwords is studied. The encoder, Alice, observes a length-n password and describes it using two hints, which she stores in different locations. The legitimate receiver, Bob, observes both hints and the eavesdropper, Eve, only one. In one scenario— the “guessing version”—we require that the expected number of guesses it takes Bob to guess the password approach one as n tends to infinity, and in the second—the “listsize version”— that the expected size of the shortest list that Bob must form to guarantee that it contain the password approach one. Assuming that Alice cannot control which hint Eve observes, the largest normalized (by n) exponent that can be guaranteed for the expected number of guesses it takes Eve to guess the password is characterized for each scenario. Key to the proof are new results on Massey–Arikan guessing, Bunte–Lapidoth task-encoding, and the close relation between them. A generalization that allows for Alice to produce δ (not necessarily two) hints, for Bob to observe v (not necessarily two) of the hints, and for Eve to observe η (not necessarily one) of the hints is also discussed. This models scenarios where hints are stored on fail-prone disks.

Two correlated sources emit a pair of sequences, each of which is observed by a different encoder. Each encoder produces a rate-limited description of the sequence it observes, and the two descriptions are presented to a guessing device that repeatedly produces sequence pairs until correct. The number of guesses until correct is random, and it is required that it have a moment (of some prespecified order) that tends to one as the length of the sequences tends to infinity. The description rate pairs that allow this are characterized in terms of the Rényi entropy and the Arimoto–Rényi conditional entropy of the joint law of the sources. This solves the guessing analog of the Slepian–Wolf distributed source-coding problem. The achievability is based on random binning, which is analyzed using a technique by Rosenthal.

The zero-error feedback capacity of the Gel’fand- Pinsker channel is established. It can be positive even if the channel’s zero-error capacity is zero in the absence of feedback. Moreover, the error-free transmission of a single bit may require more than one channel use. These phenomena do not occur when the state is revealed to the transmitter causally, a case that is solved here using Shannon strategies. Cost constraints on the channel inputs or channel states are also discussed, as is the scenario where—in addition to the message—also the state sequence must be recovered.

The capacity of the semideterministic discrete memoryless broadcast channel (SD-BC) with partial message side-information (P-MSI) at the receivers is established. In the setting without a common message, it is shown that P-MSI to the stochastic receiver alone can increase capacity, whereas P-MSI to the deterministic receiver can only increase capacity if also the stochastic receiver has P-MSI. The latter holds only for the setting without a common message: if the encoder also conveys a common message, then P-MSI to the deterministic receiver alone can increase capacity. These capacity results are used to show that feedback from the stochastic receiver can increase the capacity of the SD-BC without P-MSI and the sum-rate capacity of the SD-BC with P-MSI at the deterministic receiver. The link between P-MSI and feedback is a feedback code, which—roughly speaking—turns feedback into P-MSI at the stochastic receiver, and hence helps the stochastic receiver mitigate experienced interference. For the case, where the stochastic receiver has full MSI (F-MSI) and can thus fully mitigate experienced interference also in the absence of feedback, it is shown that feedback cannot increase capacity.

The rate region of the task-encoding problem for two correlated sources is characterized using a novel parametric family of dependence measures. The converse uses a new expression for the $\rho$-th moment of the list size, which is derived using the relative $\alpha$-entropy.

The identification (ID) capacity region of the two-receiver broadcast channel (BC) is shown to be the set of rate-pairs for which, for some distribution on the channel input, each receiver's ID rate does not exceed the mutual information between the channel input and the channel output that it observes. Moreover, the capacity region's interior is achieved by codes with deterministic encoders. The results are obtained under the average-error criterion, which requires that each receiver reliably identify its message whenever the message intended for the other receiver is drawn at random. They hold also for channels whose transmission capacity region is to-date unknown. Key to the proof is a new ID code construction for the single-user channel. An extension to the three-receiver BC is also discussed: an inner bound on the ID capacity region is obtained, and that is shown to be in some cases tight.

We study the secrecy of a distributed-storage system for passwords. The encoder, Alice, observes a length-n password and describes it using δ s-bit hints, which she stores in different locations. The legitimate receiver, Bob, observes ν of those hints. In one scenario we require that the expected number of guesses it takes Bob to guess the password approach 1 as n tends to infinity, and in the other that the expected size of the shortest list that Bob must form to guarantee that it contain the password approach 1. The eavesdropper, Eve, sees η <; ν hints. Assuming that Alice cannot control which hints Bob and Eve observe, we characterize for each scenario the largest normalized (by n) exponent that we can guarantee for the expected number of guesses it takes Eve to guess the password.

In this paper, we present novel probabilistic recovery guarantees for sparse signals subject to sparse interference, covering varying degrees of knowledge of the signal and interference support. Our results assume that the sparsifying dictionaries are characterized by coherence parameters and we require randomness only in the signal and/or interference. The obtained recovery guarantees show that one can recover sparsely corrupted signals with overwhelming probability, even if the sparsity of both the signal and interference scale (near) linearly with the number of measurements.