We settle the exact round complexity of three-party computation (3PC) in honest-majority setting, for a range of security notions such as selective abort, unanimous abort, fairness and guaranteed output delivery. Selective abort security, the weakest in the lot, allows the corrupt parties to selectively deprive some of the honest parties of the output. In the mildly stronger version of unanimous abort, either all or none of the honest parties receive the output. Fairness implies that the corrupted parties receive their output only if all honest parties receive output and lastly, the strongest notion of guaranteed output delivery implies that the corrupted parties cannot prevent honest parties from receiving their output. It is a folklore that the implication holds from the guaranteed output delivery to fairness to unanimous abort to selective abort. We focus on two network settings– pairwise-private channels without and with a broadcast channel.In the minimal setting of pairwise-private channels, 3PC with selective abort is known to be feasible in just two rounds, while guaranteed output delivery is infeasible to achieve irrespective of the number of rounds. Settling the quest for exact round complexity of 3PC in this setting, we show that three rounds are necessary and sufficient for unanimous abort and fairness. Extending our study to the setting with an additional broadcast channel, we show that while unanimous abort is achievable in just two rounds, three rounds are necessary and sufficient for fairness and guaranteed output delivery. Our lower bound results extend for any number of parties in honest majority setting and imply tightness of several known constructions.The fundamental concept of garbled circuits underlies all our upper bounds. Concretely, our constructions involve transmitting and evaluating only constant number of garbled circuits. Assumption-wise, our constructions rely on injective (one-to-one) one-way functions.

Zero-knowledge (ZK) protocols are undoubtedly among the central primitives in cryptography, lending their power to numerous applications such as secure computation, voting, auctions, and anonymous credentials to name a few. The study of efficient ZK protocols for non-algebraic statements has seen rapid progress in recent times, relying on secure computation techniques. The primary contribution of this work lies in constructing efficient UC-secure constant round ZK protocols from garbled circuits that are secure against adaptive corruptions, with communication linear in the size of the statement. We begin by showing that the practically efficient ZK protocol of Jawurek et al. (CCS 2013) is adaptively secure when the underlying oblivious transfer (OT) satisfies a mild adaptive security guarantee. We gain adaptive security with little to no overhead over the static case. A conditional verification technique is then used to obtain a three-round adaptively secure zero-knowledge argument in the non-programmable random oracle model (NPROM). Our three-round protocol yields a proof size that is shorter than the known UC-secure practically-efficient schemes in the short-CRS model with the right choice of security parameters.We draw motivation from state-of-the-art non-interactive secure computation protocols and leveraging specifics of ZK functionality show a two-round protocol that achieves static security. It is a proof, while most known efficient ZK protocols and our three round protocol are only arguments.

Verifiable Secret Sharing (VSS) is a fundamental primitive used in many distributed cryptographic tasks, such as Multiparty Computation (MPC) and Byzantine Agreement (BA). It is a two phase (sharing, reconstruction) protocol. The VSS and MPC protocols are carried out among n parties, where t out of n parties can be under the influence of a Byzantine (active) adversary, having unbounded computing power. It is well known that protocols for perfectly secure VSS and perfectly secure MPC exist in an asynchronous network iff n \geq 4t+1. Hence, we call any perfectly secure VSS (MPC) protocol designed over an asynchronous network with n=4t+1 as optimally resilient VSS (MPC) protocol. A secret is d-shared among the parties if there exists a random degree-d polynomial whose constant term is the secret and each honest party possesses a distinct point on the degree-d polynomial. Typically VSS is used as a primary tool to generate t-sharing of secret(s). In this paper, we present an optimally resilient, perfectly secure Asynchronous VSS (AVSS) protocol that can generate d-sharing of secret for any d, where t \leq d \leq 2t. This is the first optimally resilient, perfectly secure AVSS of its kind in the literature. Specifically, our AVSS can generate d-sharing of \ell \geq 1 secrets from F concurrently, with a communication cost of O(\ell n^2 \log{|F|}) bits, where F is a finite field. Communication complexity wise, the best known optimally resilient, perfectly secure AVSS is reported in [BH07]. The protocol of [BH07] can generate t-sharing of \ell secrets concurrently, with the same communication complexity as our AVSS. However, the AVSS of [BH07] and [BCG93] (the only known optimally resilient perfectly secure AVSS, other than [BH07]) does not generate d-sharing, for any d > t. Interpreting in a different way, we may also say that our AVSS shares \ell(d+1 -t) secrets simultaneously with a communication cost of O(\ell n^2 \log{|F|}) bits. Putting d=2t (the maximum value of d), we notice that the amortized cost of sharing a single secret using our AVSS is only O(n \log{|F|}) bits. This is a clear improvement over the AVSS of [BH07] whose amortized cost of sharing a single secret is O(n^2 \log{|F|}) bits. As an interesting application of our AVSS, we propose a new optimally resilient, perfectly secure Asynchronous Multiparty Computation (AMPC) protocol that communicates O(n^2 \log|F|) bits per multiplication gate. The best known optimally resilient perfectly secure AMPC is due to [BH07], which communicates O(n^3 \log|F|) bits per multiplication gate. Thus our AMPC improves the communication complexity of the best known AMPC of [BH07] by a factor of \Omega(n).

This dissertation deals with three most important as well as fundamental problems in secure distributed computing, namely Verifiable Secret Sharing (VSS), Byzantine Agreement (BA) and Multiparty Computation (MPC). VSS is a two phase protocol (Sharing and Reconstruction) carried out among $n$ parties in the presence of a centralized adversary who can corrupt up to $t$ parties. Informally, the goal of the VSS protocol is to share a secret $s$, among the $n$ parties during the sharing phase in a way that would later allow for a unique reconstruction of this secret in the reconstruction phase, while preserving the secrecy of $s$ until the reconstruction phase. VSS is used as a key tool in MPC, BA and many other secure distributed computing problems. It can take many different forms, depending on the underlying network (synchronous or asynchronous), the nature (passive or active) and computing power (bounded or unbounded) of the adversary, type of security (cryptographic or information theoretic) etc. We study VSS in information theoretic setting over both synchronous as well as asynchronous network, considering an active unbounded powerful adversary. Our main contributions for VSS are: \begin{itemize} \item In synchronous network, we carry out in-depth investigation on the round complexity of VSS by allowing a probability of error in computation and show that existing lower bounds for the round complexity of error-free VSS can be circumvented by introducing a negligible probability of error. \item We study the communication and round efficiency of VSS in synchronous network and present a robust VSS protocol that is simultaneously communication efficient and round efficient. In addition, our protocol is the best known communication and round efficient protocol in the literature. \item In asynchronous network, we study the communication complexity of VSS and propose a number of VSS protocols. Our protocols are highly communication efficient and show significant improvement over the existing protocols in terms of communication complexity. \end{itemize} The next problem that we deal with is Byzantine Agreement (BA). BA is considered as one of the most fundamental primitives for fault tolerant distributed computing and cryptographic protocols. BA among a set of $n$ parties, each having a private input value, allows them to reach agreement on a common value even if some of the malicious parties (at most $t$) try to prevent agreement among the parties. Similar to the case of VSS, several models for BA have been proposed during the last three decades, considering various aspects like the underlying network, the nature and computing power of adversary, type of security. One of these models is BA over asynchronous network which is considered to be more realistic network than synchronous in many occasions. Though important, research in BA in asynchronous network has received much less attention in comparison to the BA protocols in synchronous network. Even the existing protocols for asynchronous BA involve high communication complexity and in general are very inefficient in comparison to their synchronous counterparts. We focus on BA in information theoretic setting over asynchronous network tolerating an active adversary having unbounded computing power and mainly work towards the communication efficiency of the problem. Our contributions for BA are as follows: \begin{itemize} \item We propose communication efficient asynchronous BA protocols that show huge improvement over the existing protocols in the same setting. Our protocols for asynchronous BA use our VSS protocols in asynchronous network as their vital building blocks. \item We also construct a communication optimal asynchronous BA protocol for sufficiently long message size. Precisely, our asynchronous BA communicates O(\ell n) bits for \ell bit message, for sufficiently large \ell. \end{itemize} The studies on VSS and BA naturally lead one towards MPC problems. The MPC can model almost any known cryptographic application and uses VSS as well as BA as building blocks. MPC enables a set of $n$ mutually distrusting parties to compute some function of their private inputs, such that the privacy of the inputs of the honest parties is guaranteed (except for what can be derived from the function output) even in the presence of an adversary corrupting up to $t$ of the parties and making them misbehave arbitrarily. Much like VSS and BA, MPC can also be studied in various models. Here, we attempt to solve MPC in information theoretic setting over synchronous as well as asynchronous network, tolerating an active unbounded powerful adversary. As for MPC, our main contributions are: \begin{itemize} \item Using one of our synchronous VSS protocol, we design a synchronous MPC that minimizes the communication and round complexity simultaneously, where existing MPC protocols try to minimize one complexity measure at a time (i.e the existing protocols minimize either communication complexity or round complexity). \item We study the communication complexity of asynchronous MPC protocols and design a number of protocols for the same that show significant gain in communication complexity in comparison to the existing asynchronous MPC protocols. \item We also study a specific instance of MPC problem called Multiparty Set Intersection (MPSI) and provide protocols for the same. \end{itemize} In brief, our work in this thesis has made significant advancement in the state-of-the-art research on VSS, BA and MPC by presenting several inherent lower bounds and efficient/optimal solutions for the problems in terms of their key parameters such as communication complexity and time/round complexity. Thus our work has made a significant contribution to the field of secure distributed computing by carrying out a foundation research on the three most important problems of this field.

Secure multiparty computation (MPC) allows a set of $n$ parties to securely compute an agreed function, even if up to $t$ parties are under the control of an adversary. In this paper, we propose a new Asynchronous secure multiparty computation (AMPC) protocol that provides information theoretic security with $n = 4t+1$, where $t$ out of $n$ parties can be under the influence of a Byzantine (active) adversary ${\cal A}_t$ having unbounded computing power. Our protocol communicates O(n^2 \log|{\mathbb F}|) bits per multiplication and involves a negligible error probability of $2^{-\Omega(\kappa)}$, where $\kappa$ is the error parameter and ${\mathbb F}$ is the field over which the computation is carried out. The best known information theoretically secure AMPC with $n=4t+1$ communicates O(n^3 \log|{\mathbb F}|) bits per multiplication and does not involve any error probability in computation. Though a negligible error probability is involved, our AMPC protocol provides the best communication complexity among all the known AMPC protocols providing information theoretic security. Moreover, the communication complexity of our AMPC is same as the communication complexity of the best known AMPC protocol with cryptographic assumptions. As a tool for our AMPC protocol, we propose a new method of efficiently generating (t,2t)-sharing of multiple secrets concurrently in asynchronous setting, which is of independent interest.

We study the problem of Perfectly Reliable Message Transmission}(PRMT) and Perfectly Secure Message Transmission (PSMT) between two nodes S and R in an undirected synchronous network, a part of which is under the influence of an all powerful mobile Byzantine adversary. In ACISP 2007 Srinathan et. al. has proved that the connectivity requirement for PSMT protocols is same for both static and mobile adversary thus showing that mobility of the adversary has no effect on the possibility of PSMT (also PRMT) protocols. Similarly in CRYPTO 2004, Srinathan et. al. has shown that the lower bound on the communication complexity of any multiphase PSMT protocol is same for static and mobile adversary. The authors have also designed a $O(t)$ phase (A phase is a send from S to R or R to S or both) protocol satisfying this bound where $t$ is the maximum number of nodes corrupted by the Byzantine adversary. In this work, we design a three phase bit optimal PSMT protocol using a novel technique, whose communication complexity matches the lower bound proved in CRYPTO 2004 and thus significantly reducing the number of phases from $O(t)$ to three. Further using our novel technique, we design a three phase bit optimal PRMT protocol which achieves reliability with constant factor overhead against a mobile adversary. These are the first ever constant phase optimal PRMT and PSMT protocols against mobile Byzantine adversary. We also characterize PSMT protocols in directed networks tolerating mobile adversary. All the existing PRMT and PSMT protocols abstracts the paths between S and R as wires, neglecting the intermediate nodes in the paths. However, this causes significant over estimation in the communication complexity as well as round complexity (Round is different from phase. Round is a send from one node to its immediate neighbor in the network} of protocols. Here, we consider the underlying paths as a whole instead of abstracting them as wires and derive a tight bound on the number of rounds required to achieve reliable communication from S to R tolerating a mobile adversary with arbitrary roaming speed (By roaming speed we mean the speed with which the adversary changes the set of corrupted node). We show how our constant phase PRMT and PSMT protocols can be easily adapted to design round optimal and bit optimal PRMT and PSMT protocols provided the network is given as a collection of vertex disjoint paths.

In this work we focus on two basic secure distributed computation tasks- Probabilistic Weak Secret Sharing (PWSS) and Probabilistic Verifiable Secret Sharing (PVSS). PVSS allows a dealer to share a secret among several players in a way that would later allow a unique reconstruction of the secret with negligible error probability. PWSS is slightly weaker version of PVSS where the dealer can choose not to disclose his secret later. Both of them are well-studied problems. While PVSS is used as a building block in every general probabilistic secure multiparty computation, PWSS can be used as a building block for PVSS protocols. Both these problems can be parameterized by the number of players ($n$) and the fault tolerance threshold ($t$) which bounds the total number of malicious (Byzantine) players having {\it unbounded computing power}. We focus on the standard {\it secure channel model}, where all players have access to secure point-to-point channels and a common broadcast medium. We show the following for PVSS: (a) 1-round PVSS is possible iff $t=1$ and $n>3$ (b) 2-round PVSS is possible if $n>3t$ (c) 4-round PVSS is possible if $n>2t$. For the PWSS we show the following: (a) 1-round PWSS is possible iff $n>3t$ and (b) 3-round PWSS is possible if $n>2t$. All our protocols are {\it efficient}. Comparing our results with the existing trade-off results for perfect (zero error probability) VSS and WSS, we find that probabilistically relaxing the conditions of VSS/WSS helps to increase fault tolerance significantly.

We study the interplay of network connectivity and the issues related to the possibility, feasibility and optimality for {\it unconditionally reliable message transmission} (URMT) and {\it unconditionally secure message transmission} (USMT) in an undirected {\it synchronous} network, under the influence of an adaptive {\it mixed} adversary ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$, who has {\it unbounded computing power} and can corrupt $t_b$, $t_o$, $t_f$ and $t_p$ nodes in the network in Byzantine, {\it omission}, {\it fail-stop} and passive fashion respectively. In URMT problem, a sender {\bf S} and a receiver {\bf R} are part of a distributed network, where {\bf S} and {\bf R} are connected by intermediate nodes, of which at most $t_b, t_o, t_f$ and $t_p$ nodes can be under the control of ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$. {\bf S} wants to send a message $m$ which is a sequence of $\ell$ field elements from a finite field ${\mathbb F}$ to {\bf R}. The challenge is to design a protocol, such that after interacting in phases\footnote{A phase is a send from {\bf S} to {\bf R} or viceversa.} as per the protocol, {\bf R} should output $m' = m$ with probability at least $1 - \delta$, where $0 < \delta < \frac{1}{2}$. Moreover, this should happen, irrespective of the adversary strategy of ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$. The USMT problem has an additional requirement that ${\mathcal A}_{(t_b,t_o,t_f,t_p)}$ should not know anything about $m$ in {\it information theoretic} sense. In this paper, we answer the following in context of URMT and USMT: (a) {\sc Possibility:} when is a protocol possible in a given network? (b) {\sc Feasibility:} Once the existence of a protocol is ensured then does there exists a polynomial time protocol on the given network? (c) {\sc Optimality: } Given a message of specific length, what is the minimum communication complexity (lower bound) needed by any protocol to transmit the message and how to design a protocol whose total communication complexity matches the lower bound on the communication complexity? Finally we also show that {\it allowing a negligible error probability significantly helps in the possibility, feasibility and optimality of both reliable and secure message transmission protocols.} To design our protocols, we propose several new techniques which are of independent interest.

In this work, we initiate the study of round complexity of {\it unconditionally secure weak secret sharing} (UWSS) and {\it unconditionally secure verifiable secret sharing} (UVSS) \footnote{In the literature, these problems are also called as statistical WSS and statistical VSS \cite{GennaroVSSSTOC01} respectively.} in the presence of an {\it all powerful} $t$-active adversary. Specifically, we show the following for UVSS: (a) 1-round UVSS is possible iff $t=1$ and $n>3$, (b) 2-round UVSS is possible if $n>3t$ and (c) 5-round {\it efficient} UVSS is possible if $n>2t$. For UWSS we show the following: (a) 1-round UWSS is possible iff $n>3t$ and (b) 3-round UWSS is possible if $n>2t$. Comparing our results with existing results for trade-off between fault tolerance and round complexity of perfect (zero error) VSS and WSS \cite{GennaroVSSSTOC01,FitziVSSTCC06,KatzVSSICALP2008}, we find that probabilistically relaxing the conditions of VSS/WSS helps to increase fault tolerance significantly.

In the problem of perfectly reliable message transmission} (PRMT), a sender {\bf S} and a receiver {\bf R} are connected by $n$ bidirectional synchronous channels. A mixed adversary ${\mathcal A}_{(t_b,t_f,t_p)}$ with {\it infinite computing power} controls $t_b, t_f$ and $t_p$ channels in Byzantine, fail-stop and passive fashion respectively. Inspite of the presence of ${\mathcal A}_{(t_b,t_f,t_p)}$, {\bf S} wants to reliably send a message $m$ to {\bf R}, using some protocol, without sharing any key with {\bf R} beforehand. After interacting in phases\footnote{A phase is a send from {\bf S} to {\bf R} or vice-versa} as per the protocol, {\bf R} should output $m' = m$, without any error. In the problem of {\it perfectly secure message transmission} (PSMT), there is an additional constraint that ${\mathcal A}_{(t_b,t_f,t_p)}$ should not know {\it any} information about $m$ in {\it information theoretic} sense. The adversary can be either static\footnote{A static adversary corrupts the same set of channels in each phase of the protocol. The choice of the channel to corrupt is decided before the beginning of the protocol.} or mobile.\footnote{A mobile adversary can corrupt different set of channels in different phases of the protocol.} The {\it connectivity requirement}, {\it phase complexity} and {\it communication complexity} are three important parameters of any interactive PRMT/PSMT protocol and are well studied in the literature when the channels are controlled by a static/mobile Byzantine adversary. However, when the channels are controlled by mixed adversary ${\mathcal A}_{(t_b,t_f,t_p)}$ , we encounter several surprising consequences. In this paper, we study the problem of PRMT and PSMT tolerating "static/mobile mixed adversary". We prove that even though the connectivity requirement for PRMT is same against both static and mobile mixed adversary, the lower bound on communication complexity for PRMT tolerating mobile mixed adversary is more than its static mixed counterpart. This is interesting because against only "Byzantine adversary", the connectivity requirement and the lower bound on the communication complexity of PRMT protocols are same for both static and mobile case. Thus our result shows that for PRMT, mobile mixed adversary is more powerful than its static counterpart. As our second contribution, we design a four phase communication optimal PSMT protocol tolerating "static mixed adversary". Comparing this with the existing three phase communication optimal PSMT protocol against "static Byzantine adversary", we find that additional one phase is enough to design communication optimal protocol against static mixed adversary. Finally, we show that the connectivity requirement and lower bound on communication complexity of any PSMT protocol is same against both static and mobile mixed adversary, thus proving that mobility of the adversary has no effect in PSMT. To show that our bound is tight, we also present a worst case nine phase communication optimal PSMT protocol tolerating mobile mixed adversary which is first of it's kind. This also shows that the mobility of the adversary does not hinder to design constant phase communication optimal PSMT protocol. In our protocols, we have used new techniques which can be effectively used against both static and mobile mixed adversary and are of independent interest.

In this paper, we re-visit the problem of {\it unconditionally reliable message transmission} (URMT) and {\it unconditionally secure message transmission} (USMT) in a {\it directed network} under the presence of a threshold adaptive Byzantine adversary, having {\it unbounded computing power}. Desmedt et.al \cite{Desmedt} have given the necessary and sufficient condition for the existence of URMT and USMT protocols in directed networks. Though their protocols are efficient, they are not communication optimal. In this paper, we prove for the first time the lower bound on the communication complexity of URMT and USMT protocols in directed networks. Moreover, we show that our bounds are tight by giving efficient communication optimal URMT and USMT protocols, whose communication complexity satisfies our proven lower bounds.

We study the problem of unconditionally reliable message transmission (URMT), where two non-faulty players, the sender S and the receiver R are part of a synchronous network modeled as a directed hypergraph, a part of which may be under the influence of an adversary having unbounded computing power. S intends to transmit a message $m$ to R, such that R should correctly obtain S's message with probability at least $(1-\delta)$ for arbitrarily small $\delta > 0$. However, unlike most of the literature on this problem, we assume the adversary modeling the faults is threshold mixed, and can corrupt different set of nodes in Byzantine, passive and fail-stop fashion simultaneously. The main contribution of this work is the complete characterization of URMT in directed hypergraph tolerating such an adversary. Working out a direct characterization of URMT over directed hypergraphs tolerating threshold mixed adversary is highly un-intuitive. So we first propose a novel technique, which takes as input a directed hypergraph and a threshold mixed adversary on that hypergraph and outputs a corresponding digraph, along with a non-threshold mixed adversary, such that URMT over the hypergraph tolerating the threshold mixed adversary is possible iff a special type of URMT is possible over the obtained digraph, tolerating the corresponding non-threshold mixed adversary}. Thus characterization of URMT over directed hypergraph tolerating threshold mixed adversary reduces to characterizing special type of a URMT over arbitrary digraph tolerating non-threshold mixed adversary. We then characterize URMT in arbitrary digraphs tolerating non-threshold mixed adversary and modify it to obtain the characterization for special type of URMT over digraphs tolerating non-threshold mixed adversary. This completes the characterization of URMT over the original hypergraph. Surprisingly, our results indicate that even passive corruption, in collusion with active faults, substantially affects the reliability of URMT protocols! This is interesting because it is a general belief that passive corruption (eavesdropping) does not affect reliable communication.

We propose an efficient information theoretic secure asynchronous multiparty computation (AMPC) protocol with optimal fault tolerance; i.e., with $n = 3t+1$, where $n$ is the total number of parties and $t$ is the number of parties that can be under the influence of a Byzantine (active) adversary ${\cal A}_t$ having unbounded computing power. Our protocol communicates O(n^5 \kappa)$ bits per multiplication and involves a negligible error probability of $2^{- O(\kappa)}$, where $\kappa$ is the error parameter. As far as our knowledge is concerned, the only known AMPC protocol with $n = 3t+1$ providing information theoretic security with negligible error probability is due to \cite{BenOrPODC94AsynchronousMPC}, which communicates $\Omega(n^{11} \kappa^4)$ bits and A-Casts $\Omega(n^{11} \kappa^2 \log(n))$ bits per multiplication. Here A-Cast is an asynchronous broadcast primitive, which allows a party to send the same information to all other parties identically. Thus our AMPC protocol shows significant improvement in communication complexity over the AMPC protocol of \cite{BenOrPODC94AsynchronousMPC}. As a tool for our AMPC protocol, we introduce a new asynchronous primitive called Asynchronous Complete Verifiable Secret Sharing (ACVSS), which is first of its kind and is of independent interest. For designing our ACVSS, we employ a new asynchronous verifiable secret sharing (AVSS) protocol which is better than all known communication-efficient AVSS protocols with $n=3t+1$.

In this paper, we re-visit the problem of {\it perfectly reliable message transmission} (PRMT) and {\it perfectly secure message transmission}(PSMT) in a {\it directed network} under the presence of a threshold adaptive Byzantine adversary, having {\it unbounded computing power}. Desmedt et.al have given the necessary and sufficient condition for the existence of PSMT protocols in directed networks. In this paper, we first show that the necessary and sufficient condition (characterization) given by Desmedt et.al does not hold for two phase\footnote{A phase is a send from sender to receiver or vice-versa.} PSMT protocols. Hence we provide a different necessary and sufficient condition for two phase PSMT in directed networks. We also derive the lower bound on communication complexity of two phase PSMT and show that our lower bound is {\it asymptotically tight} by designing a two phase PSMT protocol whose communication complexity satisfies the lower bound. Though the characterization for three or more phase PSMT is resolved by the result of Desmedt et. al, the lower bound on communication complexity for the same has not been investigated yet. Here we derive the lower bound on the communication complexity of three or more phase PSMT in directed networks and show that our lower bound is {\it asymptotically tight} by designing {\it communication optimal} PSMT protocols. Finally, we characterize the class of directed networks over which communication optimal PRMT or PRMT with constant factor overhead is possible. By communication optimal PRMT or PRMT with constant factor overhead, we mean that the PRMT protocol is able to send $\ell$ field elements by communicating $O(\ell)$ field elements from a finite field $\mathbb F$. To design our protocols, we use several techniques, which are of independent interest.

In this paper, we re-visit the problem of {\it unconditionally secure message transmission} (USMT) from a sender {\bf S} to a receiver {\bf R}, who are part of a distributed synchronous network, modeled as an {\it arbitrary} directed graph. Some of the intermediate nodes between {\bf S} and {\bf R} can be under the control of the adversary having {\it unbounded} computing power. Desmedt and Wang \cite{Desmedt} have given the characterization of USMT in directed networks. However, in their model, the underlying network is abstracted as directed node disjoint paths (also called as wires/channels) between {\bf S} and {\bf R}, where the intermediate nodes are oblivious, message passing nodes and perform no other computation. In this work, we first show that the characterization of USMT given by Desmedt et.al \cite{Desmedt} does not hold good for {\it arbitrary} directed networks, where the intermediate nodes perform some computation, beside acting as message forwarding nodes. We then give the {\it true} characterization of USMT in arbitrary directed networks. As far our knowledge is concerned, this is the first ever {\it true} characterization of USMT in arbitrary directed networks.

Consider a completely asynchronous network consisting of n parties where every two parties are connected by a private channel. An adversary A_t with unbounded computing power actively controls at most t < n / 3 parties in Byzantine fashion. In these settings, we say that \pi is a $t$-resilient, $(1-\epsilon)$-terminating Asynchronous Byzantine Agreement (ABA) protocol, if $\pi$ satisfies all the properties of Byzantine Agreement (BA) in asynchronous settings tolerating A_t and terminates (i.e every honest party terminates $\pi$) with probability at least $(1-\epsilon)$. In this work, we present a new $t$-resilient, $(1-\epsilon)$-terminating ABA protocol which privately communicates O(C n^{5} \kappa) bits and A-casts O(C n^{5} \kappa) bits, where $\epsilon = 2^{-O(\kappa)$ and C is the expected running time of the protocol. Here A-Cast is a primitive in asynchronous world, allowing a party to send the same value to all the other parties. Hence A-Cast in asynchronous world is the parallel notion of broadcast in synchronous world. Moreover, conditioned on the event that our ABA protocol terminates, it does so in constant expected time; i.e., C = O(1). Our ABA protocol is to be compared with the only known $t$-resilient, $(1-\epsilon)$-terminating ABA protocol of \cite{CanettiSTOC93} in the same settings, which privately communicates O(C n^{11} \kappa^{4}) bits and A-casts O(C n^{11} \kappa^2 \log(n)) bits, where $\epsilon = 2^{-O(\kappa)} and C = O(1). So our ABA achieves a huge gain in communication complexity in comparison to the ABA of \cite{CanettiSTOC93}, while keeping all other properties in place. In another landmark work, in PODC 2008, Abraham et. al \cite{DolevAsynchronousBAPODC2008} proposed a $t$-resilient, $1$-terminating (called as almost-surely terminating in \cite{DolevAsynchronousBAPODC2008}) ABA protocol which communicates O(C n^{6} \log{n}) bits and A-casts O(C n^{6} \log{n}) bits. But ABA protocol of Abraham et. al. takes polynomial (C = O(n^2)) expected time to terminate. Hence the merits of our ABA protocol over the ABA of Abraham et. al. are: (i) For any \kappa < n^3 \log{n}, our ABA is better in terms of communication complexity (ii) conditioned on the event that our ABA protocol terminates, it does so in constant expected time (the constant is independent of n, t and \kappa), whereas ABA of Abraham et. al. takes polynomial expected time. However, it should be noted that our ABA is only $(1-\epsilon)$-terminating whereas ABA of Abraham et al. is almost-surely terminating. Summing up, in a practical scenario where a faster and communication efficient ABA protocol is required, our ABA fits the bill better than ABA protocols of \cite{CanettiSTOC93,DolevAsynchronousBAPODC2008}. For designing our ABA protocol, we present a novel and simple asynchronous verifiable secret sharing (AVSS) protocol which significantly improves the communication complexity of the only known AVSS protocol of \cite{CanettiSTOC93} in the same settings. We believe that our AVSS can be used in many other applications for improving communication complexity and hence is of independent interest.

In this paper, we re-visit the problem of unconditionally secure multiparty set intersection in information theoretic model. Li et.al \cite{LiSetMPCACNS07} have proposed a protocol for $n$-party set intersection problem, which provides unconditional security when $t < \frac{n}{3}$ players are corrupted by an active adversary having {\it unbounded computing power}. Moreover, they have claimed that their protocol takes six rounds of communication and incurs a communication complexity of ${\cal O}(n^4m^2)$, where each player has a set of size $m$. However, we show that the round complexity and communication complexity of the protocol in \cite{LiSetMPCACNS07} is much more than what is claimed in \cite{LiSetMPCACNS07}. We then propose a {\it novel} unconditionally secure protocol for multiparty set intersection problem with $n > 3t$ players, which significantly improves the "actual" round and communication complexity (as shown in this paper) of the protocol given in \cite{LiSetMPCACNS07}. To design our protocol, we use several tools which are of independent interest.