The focus of this paper is on the public communication required for generating a maximal-rate secret key (SK) within the multiterminal source model of Csiszár and Narayan. Building on the prior work of Tyagi for the two-terminal scenario, we derive a lower bound on the communication complexity, RSK, defined to be the minimum rate of public communication needed to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by RCO, is an upper bound on RSK. For the class of pairwise independent network (PIN) models defined on uniform hypergraphs, we show that a certain Type S condition, which is verifiable in polynomial time, guarantees that our lower bound on RSKmeets the RCOupper bound. Thus, the PIN models satisfying our condition are RSK-maximal, indicating that the upper bound RSK≤ RCOholds with equality. This allows us to explicitly evaluate RSKfor such PIN models. We also give several examples of PIN models that satisfy our Type S condition. Finally, we prove that for an arbitrary multiterminal source model, a stricter version of our Type S condition implies that communication from all terminals (omnivocality) is needed for establishing an SK of maximum rate. For three-terminal source models, the converse is also true: omnivocality is needed for generating a maximal-rate SK only if the strict Type S condition is satisfied. However, for the source models with four or more terminals, counterexamples exist showing that the converse does not hold in general.

In this paper, we address the problem of characterizing the instances of the multiterminal source model of Csiszár and Narayan in which communication from all terminals is needed for establishing a secret key of maximum rate. We give an information-theoretic sufficient condition for identifying such instances. We believe that our sufficient condition is in fact an exact characterization, but we are only able to prove this in the case of the three-terminal source model.

Mobile nodes observing correlated data communicate using an insecure bidirectional switch to generate a secret key, which must remain concealed from the switch. We are interested in fault-tolerant secret key rates, i.e., the rates of secret key generated even if a subset of nodes drop out before the completion of the communication protocol. We formulate a new notion of fault-tolerant secret key capacity, and present an upper bound on it. This upper bound is shown to be tight when the random variables corresponding to the observations of nodes are exchangeable. Further, it is shown that one round of interaction achieves the fault-tolerant secret key capacity in this case. The upper bound is also tight for the case of a pairwise independent network model consisting of a complete graph, and can be attained by a noninteractive protocol.

Current user interfaces for online video consumption are mostly browser based, lean forward, require constant interaction and provide a fragmented view of the total content available. For easier consumption, the user interface and interactions need to be redesigned for less interruptive and lean back experience. In this paper, we describe Personalized Video, an application that converts the online video experience into a personalized lean back experience. It has been implemented on the Windows platform and integrated with intuitive user interactions like gesture and face recognition. It also supports group personalization for concurrent users.

Traditional 1D and 2D barcodes provide high data density, but they are visually jarring and require isolated white margins for placement. In this work, we introduce new machine-readable "smarts" for paper documents, called paper widgets. Like barcodes, paper widgets contain digital data which can be read upon scanning and decoding. However, unlike barcodes, they have very small footprint (fraction of sq.cm.), and carry a human-readable component that provides visual meaning. Furthermore, paper widgets can be placed and recovered in a distributed fashion from any position on a document image. For example, they can be positioned right beside contents of interest, and need not be confined to isolated white margins. We describe how all these widget properties can be simultaneously achieved using simple operations that are robust to print-scan distortions. In particular, we highlight a novel constrained coding technique that helps combat print-scan intersymbol interference (ISI), and a Gabor-filtering based extraction that accurately identifies widget regions from any position on a scanned document image. Experimental evaluations reveal that paper widgets can be recovered from print-scan distortions with near-100% accuracy.

The Hopper-Blum (HB) protocol, which uses noised linear parities of a shared key for authentication, has been proposed for light-weight applications such as RFID. Recently, algorithms for decoding linear codes have been specially designed for use in passive attacks on the HB protocol. These linear coding attacks have resulted in the need for long keys in the HB protocol, making the protocol too complex for RFID in some cases. In this work, we propose the NLHB protocol, which is a non-linear variant of the HB protocol. The non-linearity is such that passive attacks on the NLHB protocol continue to be provably hard by reduction. However, the linear coding attacks cannot be directly adapted to the proposed NLHB protocol because of the non-linearity. Hence, smaller key sizes appear to be sufficient in the NLHB protocol for the same level of security as the HB protocol. We construct specific instances of the NLHB protocol and show that they can be significantly less complex for implementation than the HB protocol, in spite of the non-linearity. Further, we propose an extension, called the NLHB+ protocol, that is provably secure against a class of active attack models.

We introduce the fixed-rate bit stuff (FRB) algorithm for efficiently encoding and decoding maximum-runlength-limited (MRL) sequences. Our approach is based on a simple, variable-rate technique calledbit stuffing. Bit stuffing produces near- capacity achieving codes for a wide range of constraints, but encoding is variable-rate, which is unacceptable in most applications. In this work, we design near-capacity fixed-rate codes using a three-step procedure. The fixed-length input data block first undergoes iterative preprocessing, followed by variable-rate bit stuffing, and finally dummy-bit padding to a fixed output length. The iterative preprocessing is key to achieving high encoding rates. We discuss rate computation for the proposed FRB algorithm and show that the asymptotic (in input block length) encoding rate is close to the average rate of the variable-rate bit stuff code. Then, we proceed to explore the effect of decreasing/increasing the number of preprocessing iterations. Finally, we derive a lower bound on the encoding rate with finite-length input blocks and tabulate the parameters required to design FRB codes with rate close to$100/101$and$200/201$.

(0,G/I) constraints arise in magnetic recording systems that use partial-response equalization with maximum-likelihood sequence detection (PRML). In this paper, we present simple variable-rate and fixed-rate encoding algorithms for (0,G/I) constraints that come quite close to the constraint capacity. Both algorithms are based on the concept of bit stuffing. We first describe the variable-rate encoding algorithm, and discuss rate computations based on a Markov chain model. The average encoding rates for 1 les G les 15 and 14 les I les 10 are tabulated. It is seen that the variable-rate bit stuff algorithm generates greater than 99% efficiency (0,G/I) codes for a wide range of the values of G and I. Then we present a fixed-rate version of the variable-rate stuff algorithm, and tabulate required parameters for the design of fixed-rate (0,G/I) codes with rate close to 100/101 and 200/201

This correspondence presents two variable-rate encoding algorithms that achieve capacity for the (d,k) constraint when k=2d+1, or when k-d+1 is not prime. The first algorithm, symbol sliding, is a generalized version of the bit flipping algorithm introduced by Aviran In addition to achieving capacity for (d,2d+1) constraints, it comes close to capacity in other cases. The second algorithm is based on interleaving and is a generalized version of the bit stuffing algorithm introduced by Bender and Wolf. This method uses fewer than k-d biased bit streams to achieve capacity for (d,k) constraints with k-d+1 not prime. In particular, the encoder for (d,d+2/sup m/-1) constraints 2 /spl les/ m < /spl infin/ requires only m biased bit streams.

Recent years have seen tremendous growth in the deployment of wireless local area networks (WLANs). An important design issue in such networks is that of distributed scheduling. The lack of centralized control leads to multiple users competing for channel access. This leads to significant throughput degradation. Existing approaches, such as the slotted Aloha protocol and IEEE 802.11 DCF, also fail to provide differentiated service to users. The upcoming IEEE 802.11e enhanced DCF incorporates additional mechanisms to provide support for service differentiation. However, the level of differentiation achieved with these mechanisms is difficult to quantify. In this paper, we propose a class of distributed scheduling algorithms, regulated contention medium access control (RCMAC), which provides dynamic prioritized access to users for service differentiation in a quantifiable manner. Furthermore, by regulating multi-user contention, RCMAC achieves higher throughput when traffic is bursty, as is typically the case. In addition to WLANs, the basic concepts of RCMAC have applications in ad hoc networks and emerging sensor networks.

Binary sequences where successive ones are separated by at most k consecutive zeros, are said to be k-constrained. We introduce a new fixed-rate algorithm for efficiently encoding and decoding k-constrained sequences. Our approach is based on bit stuffing proposed by Bender and Wolf. Bit stuffing is a simple algorithm that can produce near-optimal codes for a wide range of constraints. While bit stuffing achieves rates very close to the noiseless capacity, encoding is variable-rate, which severely limits its practical use. In this paper, we present a fixed-rate version of the bit stuff algorithm. High encoding efficiency is achieved by iterative pre-processing of the fixed-length input data to conform it to bit insertion. The encoder then inserts bits to produce a fixed-length output word. Rate computations for the proposed encoding algorithm are discussed, and upper and lower bounds are derived for the asymptotic (in input block length) encoding rate. It is seen that encoding rates very close to the average bit stuff rate are possible with long, fixed-length, input and output blocks. Upper and lower bounds on the asymptotic encoding rate are listed for values of k = 1 to 15

A class of distributed scheduling algorithms, Regulated Contention Medium Access Control (RCMAC), which provides dynamic prioritized access to users for service differentiation, is considered in this paper. In addition to WLANs, the basic concepts of RCMAC have applications in multihop cellular and ad hoc networks and emerging sensor networks. Furthermore, by regulating multiuser contention, RCMAC achieves higher throughput when traffic is bursty. In this paper, differential function with two special cases like weight proportional and old base regulation is presented. Arrivals at each user are bursty, generated using standard two-state Markov model and the multiplicative increase/decrease rule are employed.

This paper considers the problem of capacity equivalence for a general class of (M,d,k) run-length-limited constraints, namely we look for pairs (M,d,k) and (M',d',k') that have the same capacity. Our approach is based on a time domain interpretation where the characteristic (M,d,k) polynomial is viewed as an impulse train and factorization is related to convolution in discrete time. Using this interpretation, we first derive the known binary equivalence relations and then generalize to the M-ary case.

Wireless sensor networks (WSN) are event based systems that rely on the collective effort of several microsensor nodes. Reliable event detection at the sink is based on collective information provided by source nodes and not on any individual report. Hence, conventional end-to-end reliability definitions and solutions are inapplicable in the WSN regime and would only lead to a waste of scarce sensor resources. However, the absence of reliable transport altogether can seriously impair event detection. Hence, the WSN paradigm necessitates a collective phevent-to-sink reliability notion rather than the traditional end-to-end notion. To the best of our knowledge, reliable transport in WSN has not been studied from this perspective before.In order to address this need, a new reliable transport scheme for WSN, the event-to-sink reliable transport (ESRT) protocol, is presented in this paper. ESRT is a novel transport solution developed to achieve reliable event detection in WSN with minimum energy expenditure. It includes a congestion control component that serves the dual purpose of achieving reliability and conserving energy. Importantly, the algorithms of ESRT mainly run on the sink, with minimal functionality required at resource constrained sensor nodes. ESRT protocol operation is determined by the current network state based on the reliability achieved and congestion condition in the network. If the event-to-sink reliability is lower than required, ESRT adjusts the reporting frequency of source nodes aggressively in order to reach the target reliability level as soon as possible. If the reliability is higher than required, then ESRT reduces the reporting frequency conservatively in order to conserve energy while still maintaining reliability. This self-configuring nature of ESRT makes it robust to random, dynamic topology in WSN. Analytical performance evaluation and simulation results show that ESRT converges to the desired reliability with minimum energy expenditure, starting from any initial network state.