Bikash Kumar Dey

Manoj Mishra, Bikash Kumar Dey, Vinod M. Prabhakaran et al.

In this paper, we study the problem of obtaining $1$-of-$2$ string oblivious transfer (OT) between users Alice and Bob, in the presence of a passive eavesdropper Eve. The resource enabling OT in our setup is a noisy broadcast channel from Alice to Bob and Eve. Apart from the OT requirements between the users, Eve is not allowed to learn anything about the users' inputs. When Alice and Bob are honest-but-curious and the noisy broadcast channel is made up of two independent binary erasure channels (connecting Alice-Bob and Alice-Eve), we derive the $1$-of-$2$ string OT capacity for both $2$-privacy (when Eve can collude with either Alice or Bob) and $1$-privacy (when no such collusion is allowed). We generalize these capacity results to $1$-of-$N$ string OT and study other variants of this problem. When Alice and/or Bob are malicious, we present a different scheme based on interactive hashing. This scheme is shown to be optimal for certain parameter regimes. We present a new formulation of multiple, simultaneous OTs between Alice-Bob and Alice-Cathy. For this new setup, we present schemes and outer bounds that match in all but one regime of parameters. Finally, we consider the setup where the broadcast channel is made up of a cascade of two independent binary erasure channels (connecting Alice-Bob and Bob-Eve) and $1$-of-$2$ string OT is desired between Alice and Bob with $1$-privacy. For this setup, we derive an upper and lower bound on the $1$-of-$2$ string OT capacity which match in one of two possible parameter regimes.

Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg et al.

We consider the problem of communicating a message $m$ in the presence of a malicious jamming adversary (Calvin), who can erase an arbitrary set of up to $pn$ bits, out of $n$ transmitted bits $(x_1,\ldots,x_n)$. The capacity of such a channel when Calvin is exactly causal, i.e. Calvin's decision of whether or not to erase bit $x_i$ depends on his observations $(x_1,\ldots,x_i)$ was recently characterized to be $1-2p$. In this work we show two (perhaps) surprising phenomena. Firstly, we demonstrate via a novel code construction that if Calvin is delayed by even a single bit, i.e. Calvin's decision of whether or not to erase bit $x_i$ depends only on $(x_1,\ldots,x_{i-1})$ (and is independent of the "current bit" $x_i$) then the capacity increases to $1-p$ when the encoder is allowed to be stochastic. Secondly, we show via a novel jamming strategy for Calvin that, in the single-bit-delay setting, if the encoding is deterministic (i.e. the transmitted codeword is a deterministic function of the message $m$) then no rate asymptotically larger than $1-2p$ is possible with vanishing probability of error, hence stochastic encoding (using private randomness at the encoder) is essential to achieve the capacity of $1-p$ against a one-bit-delayed Calvin.

Manoj Mishra, Tanmay Sharma, Bikash K. Dey et al.

We study the following private data transfer problem: Alice has a database of files. Bob and Cathy want to access a file each from this database (which may or may not be the same file), but each of them wants to ensure that their choices of file do not get revealed even if Alice colludes with the other user. Alice, on the other hand, wants to make sure that each of Bob and Cathy does not learn any more information from the database than the files they demand (the identities of which will be unknown to her). Moreover, they should not learn any information about the other files even if they collude. It turns out that it is impossible to accomplish this if Alice, Bob, and Cathy have access only to private randomness and noiseless communication links. We consider this problem when a binary erasure broadcast channel with independent erasures is available from Alice to Bob and Cathy in addition to a noiseless public discussion channel. We study the file-length-per-broadcast-channel-use rate in the honest-but-curious model. We focus on the case when the database consists of two files, and obtain the optimal rate. We then extend to the case of larger databases, and give upper and lower bounds on the optimal rate.

Deepesh Data, Bikash Kumar Dey, Manoj Mishra et al.

In secure multiparty computation, mutually distrusting users in a network want to collaborate to compute functions of data which is distributed among the users. The users should not learn any additional information about the data of others than what they may infer from their own data and the functions they are computing. Previous works have mostly considered the worst case context (i.e., without assuming any distribution for the data); Lee and Abbe (2014) is a notable exception. Here, we study the average case (i.e., we work with a distribution on the data) where correctness and privacy is only desired asymptotically. For concreteness and simplicity, we consider a secure version of the function computation problem of Körner and Marton (1979) where two users observe a doubly symmetric binary source with parameter p and the third user wants to compute the XOR. We show that the amount of communication and randomness resources required depends on the level of correctness desired. When zero-error and perfect privacy are required, the results of Data et al. (2014) show that it can be achieved if and only if a total rate of 1 bit is communicated between every pair of users and private randomness at the rate of 1 is used up. In contrast, we show here that, if we only want the probability of error to vanish asymptotically in block length, it can be achieved by a lower rate (binary entropy of p) for all the links and for private randomness; this also guarantees perfect privacy. We also show that no smaller rates are possible even if privacy is only required asymptotically.

Manoj Mishra, Bikash Kumar Dey, Vinod M. Prabhakaran et al.

We consider oblivious transfer between Alice and Bob in the presence of an eavesdropper Eve when there is a broadcast channel from Alice to Bob and Eve. In addition to the secrecy constraints of Alice and Bob, Eve should not learn the private data of Alice and Bob. When the broadcast channel consists of two independent binary erasure channels, we derive the oblivious transfer capacity for both 2-privacy (where the eavesdropper may collude with either party) and 1-privacy (where there are no collusions).