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$\delta $(not necessarily two) hints, for Bob to observe$\nu $(not necessarily two) of the hints, and for Eve to observe$\eta $(not necessarily one) of the hints is also discussed. This models scenarios where hints are stored on fail-prone disks.

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.

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

Channel coding over arbitrarily permuted parallel channels was first studied by Willems and coworkers. This paper introduces capacity-achieving polar coding schemes for arbitrarily permuted parallel channels where the component channels are memoryless, binary-input, and output-symmetric.

A polar coding scheme is suggested for the binary-input memoryless symmetric and degraded wire-tap channel. The provided scheme achieves the entire rate-equivocation region for the considered model.

A capacity-achieving polar coding scheme is introduced for reliable communications over a set of parallel communication channels. They are assumed to be arbitrarily-permuted memoryless binary-input and output-symmetric (MBIOS) channels, and they form a set of (stochastically) degraded channels. The general case where the parallel channels are not necessarily degraded is addressed in the full paper version [3], though the suggested scheme is not capacity-achieving in the general case.

A message independence property and some new performance upper bounds are derived in this work for erasure, list, and decision-feedback schemes with linear block codes transmitted over memoryless symmetric channels. Similar to the classical work of Forney, this work is focused on the derivation of some Gallager-type bounds on the achievable tradeoffs for these coding schemes, where the main novelty is the suitability of the bounds for both random and structured linear block codes (or code ensembles). The bounds are applicable to finite-length codes and to the asymptotic case of infinite block length, and they are applied to low-density parity-check code ensembles.

The performance of nonbinary linear block codes is studied in this paper via the derivation of new upper bounds on the block error probability under maximum-likelihood (ML) decoding. The transmission of these codes is assumed to take place over a memoryless and symmetric channel. The new bounds, which are based on the Gallager bounds and their variations, are applied to the Gallager ensembles of nonbinary and regular low-density parity-check (LDPC) codes. These upper bounds are also compared with sphere-packing lower bounds. This study indicates that the new upper bounds are useful for the performance evaluation of coded communication systems which incorporate nonbinary coding techniques.

The performance analysis of non-binary linear block codes is studied under ML decoding where it is assumed that the transmission takes place over memoryless symmetric channels. Gallager-type bounds are derived, and the proposed bounds are exemplified for expurgated regular ensembles of non-binary low-density parity-check (LDPC) codes. These bounds are also compared with classical and recent improved sphere-packing bounds, indicating that these bounding techniques are informative for the performance evaluation of coded communication systems which incorporate non-binary coding techniques.

An inner bound on the deterministic-code capacity region of the two-user discrete memoryless arbitrarily varying general broadcast channel (AVGBC) was characterized by Jahn, assuming that the common message capacity is nonzero; however, he did not indicate how one could decide whether the latter capacity is positive. Csiszaacuter and Narayan's result for the single-user arbitrarily varying channel (AVC) establishes the missing part in Jahn's characterization. Nevertheless, being based on Ahlswede's elimination technique, Jahn's characterization is not applicable for symmetrizable channels under state constraint. Here, the various notions of symmetrizability for the two-user broadcast AVC are defined. Sufficient non-symmetrizability condition that renders the common message capacity of the AVGBC positive is identified using an approach different from Jahn's. The decoding rules we use establish an achievable region under state and input constraints for the family of degraded message sets codes over the AVGBC