Verifiable Secret-Sharing(VSS) is a fundamental primitive in secure distributed computing that allows a designated dealer to share a secret amongnparties in the presence of an adversary controlling at mosttof them. We study VSS in the presence ofcomputationally-boundedadversaries. Known VSS protocols tolerate up totstaperfectsecurity (Appan et al. IEEE IT 2023) where the threshold conditions arenotknown to be optimal or withstatistical security(Appan et al. TCC 2023) where the threshold conditions are optimal, but the parties need to performexponentialamount of computation and communication. Using our VSS protocol, we design a secureMulti-Party Computation(MPC) protocol in theplain Public Key Infrastructure (PKI) model, i.e., without assuming an expensive trusted setup. Although our proposed MPC protocol incurs higher communication complexity than state-of-the-art network-agnostic MPC protocols, it motivates alternative directions for designingcomputationally inexpensiveMPC protocols based on a plain PKI setup, which has not been explored in the domain of computationally secure networkagnostic MPC and offers valuable insights into designing it.

In this work, we initiate the study of network-agnostic perfectly-secure multi-party computation (MPC) against general (non-threshold) adversaries, where the corruption capacity of the adversary is specified through an adversary structure, which is a set of potentially corrupt subsets of parties. Known MPC protocols are designed either assuming a synchronous network where every sent message is guaranteed to be delivered within some known time or assuming an asynchronous network where no timing assumptions are made and every sent message is eventually delivered. Perfectly-secure MPC protocols in the synchronous network can be designed as long as the underlying adversary structure satisfies the$ {{\mathcal {Q}}}^{(3)}$condition, meaning that the union of no three subsets from the adversary structure covers the entire set of parties. On the other hand, perfectly-secure MPC protocols in the asynchronous network can be designed only against$ {{\mathcal {Q}}}^{(4)}$adversary structures, meaning that the union of no four subsets from the adversary structure covers the entire set of parties. A natural question is whether a single MPC protocol exists, which remains secure even if the parties are unaware of the network conditions at execution time. That is, if the synchrony is satisfied throughout the protocol execution then the protocol should be secure against any$ {{\mathcal {Q}}}^{(3)}$adversary structure. However, even if any synchrony assumption is violated during the execution, the protocol should still be secure against any$ {{\mathcal {Q}}}^{(4)}$adversary structure. We answer the above question affirmatively. Fix any adversary structure${\mathcal {Z}}_{s}$and${\mathcal {Z}}_{a}$satisfying$ {{\mathcal {Q}}}^{(3)}$and$ {{\mathcal {Q}}}^{(4)}$conditions respectively, such that${\mathcal {Z}}_{a} \subset {\mathcal {Z}} _{s}$. We show the existence of a network-agnostic perfectly-secure MPC protocol tolerating${\mathcal {Z}}_{s}$and${\mathcal {Z}}_{a}$in synchronous and asynchronous networks respectively as long as the$ {{\mathcal {Q}}}^{(3, 1)}$condition is satisfied, meaning that the union of no three subsets from${\mathcal {Z}}_{s}$and one subset from${\mathcal {Z}}_{a}$covers the entire set of parties. Our result generalizes the result of Appan, Chandramouli and Choudhury (IEEE Transactions on IT, 2023), which presents the only known perfectly-secure network-agnostic MPC protocol against threshold adversaries.

In this work, we study perfectly-secure multi-party computation (MPC) against general (non-threshold) adversaries. Known protocols in a synchronous network are secure against $Q^{(3)}$ adversary structures, while in an asynchronous network, known protocols are secure against $Q^{(4)}$ adversary structures. A natural question is whether there exists a single protocol which remains secure against $Q^{(3)}$ and $Q^{(4)}$ adversary structures in a synchronous and in an asynchronous network respectively, where the parties are not aware of the network type. We design the first such best-of-both-worlds protocol against general adversaries. Our result generalizes the result of Appan, Chandramouli and Choudhury (PODC 2022), which presents a best-of-both-worlds perfectly-secure protocol against threshold adversaries. To design our protocol, we present two important building blocks which are of independent interest. The first building block is a best-of-both-worlds perfectly-secure Byzantine agreement (BA) protocol for $Q^{(3)}$ adversary structures, which remains secure both in a synchronous, as well as an asynchronous network. The second building block is a best-of-both-worlds perfectly-secure verifiable secret-sharing (VSS) protocol, which remains secure against $Q^{(3)}$ and $Q^{(4)}$ adversary structures in a synchronous network and an asynchronous network respectively.

Securemulti-party computation(MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of$n$mutually distrusting parties to carry out any joint computation of their private inputs, without disclosing any additional information about their inputs. MPC withinformation-theoreticsecurity (also calledunconditional security) provides the strongest security guarantees and remains secure even againstcomputationally unboundedadversaries.Perfectly-secureMPC protocols are a class of information-theoretically secure MPC protocols, which provide all the security guarantees in anerror-freefashion. The focus of this work is perfectly-secure MPC. Known protocols are designedassumingeither asynchronousorasynchronouscommunication network. It is well known that perfectly-securesynchronousMPC is possible as long as the adversary can corrupt any$t_{s} < n/3$parties. On the other hand, perfectly-secureasynchronousMPC protocols can tolerate up to$t_{a} < n/4$corrupt parties. A natural question is does there exist asingleMPC protocol for the setting where the parties arenot awareof the exact network type and which can tolerate up to$t_{s} < n/3$corruptions in a synchronous network and up to$t_{a} < n/4$corruptions in anasynchronousnetwork. We design such abest-of-both-worldsperfectly-secure MPC protocol, provided$3t_{s} + t_{a} < n$holds. For designing our protocol, we design two important building blocks which are of independent interest. The first building block is a best-of-both-worldsByzantine agreement(BA) protocol tolerating$t < n/3$corruptions which remains securebothin a synchronous as well as asynchronous network. The second building block is a polynomial-based best-of-both-worldsverifiable secret-sharing(VSS) protocol, which can tolerate up to$t_{s}$and$t_{a}$corruptions in asynchronousand in anasynchronousnetwork respectively.

Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. The optimal resilience for perfectly-secure MPC in synchronous and asynchronous networks is t < n/3 and t < n/4 respectively, where n is the number of parties and t is the number of corruptions. A natural question is whether there exists a protocol tolerating ts < n/3 corruptions in a synchronous network and ta < n/4 corruptions in an asynchronous network. We design such a protocol, if 3ts + ta < n. For our protocol, we present a perfectly-secure Byzantine agreement (BA) protocol, tolerating t < n/3 corruptions in any network and a perfectly-secure verifiable secret-sharing (VSS) protocol, tolerating ts and ta corruptions in a synchronous and an asynchronous network respectively.

We present almost-surely terminating asynchronous Byzantine agreement (ABA) protocols with a constant expected running time, in two different settings. The first protocol is in a completely asynchronous setting and has non-optimal resilience, outperforming the communication complexity of all the existing protocols in the asynchronous setting. The second protocol has optimal resilience and considers a hybrid setting for the first time, where the parties are available with one synchronous round at the beginning of the protocol execution, after which the network is completely asynchronous.

The problem of Byzantine Agreement (BA) is of interest to both the distributed computing and cryptography communities. Following well-known results from distributed computing literature, the BA problem in the asynchronous network setting encounters inevitable non-termination issues. The impasse is overcome via randomization that allows construction of BA protocols in two flavors of termination guarantee—with overwhelming probability and with probability one. The latter type, termed as almost-surely terminating BA, is the main focus of this article. An eluding problem in the domain of almost-surely terminating BA is achieving a constant expected running time. Our primary contribution in this work makes significant progress in this direction. In a setting with n parties and an adversary with unbounded computing power controlling at most t parties in a Byzantine fashion, we present two almost-surely terminating BA protocols in the asynchronous setting: ○ With the optimal resilience of t < n /3, our first protocol runs for an expected O ( n ) time. The existing protocols in the same setting either run for an expected O ( n 2 ) time (Abraham et al., PODC 2008) or require exponential computing power from the honest parties (Wang, CoRR 2015). In terms of communication complexity, our construction outperforms all the known constructions with t < n /3 that offer almost-surely terminating feature. ○ With the resilience of t < n /3 + ϵ for any ϵ > 0, our second protocol runs for an expected O (1/ϵ) time. The expected running time of our protocol turns constant when ϵ is a constant fraction. The known constructions with a constant expected running time either require ϵ to be at least 1 (Feldman-Micali, STOC 1988 and Patra-Pandu Rangan, PODC 2010), implying t < n /4, or call for exponential computing power from the parties (Wang, CoRR 2015). We follow the traditional route of building BA via common coin protocol that in turn reduces to Asynchronous Verifiable Secret-Sharing (AVSS). Our constructions are built on a variant of AVSS that is termed as shunning . A shunning AVSS fails to offer the properties of AVSS when the corrupt parties strike, but allows the honest parties to locally detect and shun a set of corrupt parties for any future communication. Our shunning AVSS with t < n /3 and t < n /3 + ϵ guarantee Ω( n ) and, respectively, Ω(ϵ t 2 ) conflicts to be revealed when failure occurs. Turning this shunning AVSS to a common coin protocol efficiently constitutes yet another contribution of this work. As a secondary contribution, we show the power of the shunning technique and present a highly efficient cryptographically secure shunning AVSS, which is used further to design an asynchronous BA protocol with the optimal resilience of t < n /3 in the cryptographic setting. Our construct achieves an amortized expected communication complexity of O ( n 2 ) bits for reaching agreement on a single bit while consuming a constant expected running time. This property has been achieved for the first time in the cryptographic setting and that, too, with standard cryptographic assumptions. The best-known existing construction (Cachin et al., CCS 2002), while still needing more communication complexity than ours, is proven secure only in the Random-Oracle Model (ROM).

We revisit the problem of distributed consensus in directed graphs tolerating crash failures; we improve the round and communication complexity of the existing protocols. Moreover, we prove that our protocol requires the optimal number of communication rounds, required by any protocol belonging to a specific class of crash-tolerant consensus protocols in directed graphs.

parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can maliciously corrupt any t out of the n parties. Most of the known efficient MPC protocols are designed in the offline- online framework introduced in a seminal work by Beaver in CRYPTO 1991. In this framework, the parties generate shared random and private multiplication-triples during the offline phase, which are used later in the online phase for securely evaluating the multiplication gates in the circuit representing f . The efficiency of the MPC protocols in this framework then relies on efficient ways of implementing the offline phase. In this paper, we propose a new and simple framework for generating shared and private random multiplication triples with unconditional security. The existing protocols approach this problem by first producing shared pairs of private and random values, followed by securely computing the shared product of each pair of values. The latter task involves a multiplication protocol for shared values that are typically communication intensive. Our framework takes a completely different approach and shuns the use of multiplication protocol. Namely, we ask the parties to verifiably share random multiplication triples and then securely extract shared random multiplication triples unknown to the adversary, from the shared triples. Realizing our framework in the asynchronous and hybrid network setting,1 we present the first ever MPC protocols with a linear (in the number of parties) communication overhead per multiplication gate in the circuit representing f . These are significant improvements over the best known existing MPC protocols in the asynchronous and hybrid network setting with communication complexity O(n2) and O(n3), respectively. Our framework when applied to the synchronous setting results in round-efficient MPC protocols.

Multiparty computation (MPC) among n parties can tolerate up to t<n/2 active corruptions in a synchronous communication setting; however, in an asynchronous communication setting, the resiliency bound decreases to only t < n/3 active corruptions. We improve the resiliency bound for asynchronous MPC (AMPC) to match synchronous MPC using non-equivocation.

We consider the problem of k-out-of-n secret sharing, capable of identifying up to t cheaters, with probability at least (1 - ε), for a given error parameter ε. In any such secret sharing scheme, t < k/2 and the lower bound of |Vi| ≥ |S| - 1 / ε + 1 holds. Here Vi denotes the set of all possible ith share, that can be assigned to the ith party and S denotes the set of all possible secrets. To the best of our knowledge, there does not exist any computationally efficient secret sharing scheme with k = 2t+1 (the minimum value of k), where |Vi| exactly matches the lower bound. We show that it is possible to match this bound in the amortized sense.

Asynchronous Verifiable Secret Sharing (AVSS) is a fundamental primitive in secure distributed computing. It finds significant application in problems like asynchronous Byzantine Agreement (ABA) and Asynchronous Multiparty Computation (AMPC). In [4], we presented a new asynchronous primitive called Asynchronous Weak Commitment (AWC) and used it to construct an AVSS scheme, which is thus far the most communication efficient AVSS scheme. Through this brief announcement, we wish to make our result visible to the Distributed Computing community.

Perfectly reliable message transmission (PRMT) is one of the fundamental problems in distributed computing. It allows a sender to reliably transmit a message to a receiver in an unreliable network, even in the presence of a computationally unbounded adversary. In this article, we study the inherent trade-off between the three important parameters of the PRMT protocols, namely, the network connectivity ( n ), the round complexity ( r ), and the communication complexity by considering the following generic question (which can be considered as the holy grail problem) in the context of the PRMT protocols. Given an n -connected network, a message of size ℓ (to be reliably communicated) and a limit c for the total communication allowed between the sender and the receiver, what is the minimum number of communication rounds required by a PRMT protocol to send the message, such that the communication complexity of the protocol is O( c )? We answer this interesting question by deriving a nontrivial lower bound on the round complexity. Moreover, we show that the lower bound is tight in the amortized sense, by designing a PRMT protocol whose round complexity matches the lower bound. The lower bound is the first of its kind, that simultaneously captures the inherent tradeoff between the three important parameters of a PRMT protocol.

We design a three phase communication optimal perfectly secure message transmission (OPSMT) protocol tolerating a computationally unbounded mobile mixed adversary. This improves the nine phase OPSMT protocol of [2].

In this paper, we re-visit the problem of unconditionally secure message transmission (USMT) from a sender S to a receiver R, who are part of a distributed synchronous network, modeled as an arbitrary directed graph. Some of the intermediate nodes between S and R can be under the control of an adversary having unbounded computing power. Desmedt and Wang [4] 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 S and 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 [4] does not hold good for arbitrary directed networks, where the intermediate nodes can perform some computation, beside acting as message forwarding nodes. We then give the characterization of USMT in arbitrary directed networks, considering the entire network as a whole. As far our knowledge is concerned, this is the first ever 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 At with unbounded computing power actively controls at most t = ([n/3] − 1) out of n parties in Byzantine fashion. In this setting, we say that π is a t-resilient, (1 − ε)-terminating Asynchronous Byzantine Agreement (ABA) protocol, if π satisfies all the properties of Byzantine Agreement (BA) in asynchronous settings tolerating At and terminates (i.e every honest party terminates π with probability at least (1 − ε). In this work, we present a new t-resilient, (1 − ε)-terminating ABA protocol which privately communicates O(Cn6 κ) bits and A-casts1 O(Cn6 κ) bits, where ε = 2−Ω(κ) and C is the expected running time of the protocol. 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 − ε)-terminating ABA protocol of [5] in the same settings, which privately communicates O(Cn11 κ4) bits and A-casts O(Cn11 κ2 log(n)) bits, where ε = 2−Ω(κ) and C = O(1). So our ABA achieves a huge gain in communication complexity in comparison to the ABA of [5], while keeping all other properties in place. In another landmark work, in PODC 2008, Abraham et. al [1] proposed a t-resilient, 1-terminating (called as almost-surely terminating in [1]) ABA protocol which privately communicates O(Cn6 log n) bits and A-casts O(Cn6 log n) bits. But ABA protocol of Abraham et. al. takes polynomial (C = O(n2)) expected time to terminate. Hence the merits of our ABA protocol over the ABA of Abraham et. al. are: (i) For any κ < n2 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 κ), whereas ABA of Abraham et. al. takes polynomial expected time. 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 [5, 1].

No abstract available.

In this paper, we study the inherent tradeoff between the network connectivity, phase complexity and communication complexity of perfectly reliable message transmission (PRMT) problem in undirected synchronous network, tolerating a mixed adversary A(tb,tf), who has unbounded computing power and can corrupt tb and tf nodes in the network in Byzantine and fail-stop fashion respectively.

No abstract available.

No abstract available.

MOTIVATION: Given a large set of potential features, such as the set of all gene-expression values from a microarray, it is necessary to find a small subset with which to classify. The task of finding an optimal feature set of a given size is inherently combinatoric because to assure optimality all feature sets of a given size must be checked. Thus, numerous suboptimal feature-selection algorithms have been proposed. There are strong impediments to evaluate feature-selection algorithms using real data when data are limited, a common situation in genetic classification. The difficulty is compound. First, there are no class-conditional distributions from which to draw data points, only a single small labeled sample. Second, there are no test data with which to estimate the feature-set errors, and one must depend on a training-data-based error estimator. Finally, there is no optimal feature set with which to compare the feature sets found by the algorithms. RESULTS: This paper describes a genetic test bed for the evaluation of feature-selection algorithms. It begins with a large biological feature-label dataset that is used as an empirical distribution and, using massively parallel computation, finds the top feature sets of various sizes based on a given sample size and classification rule. The user can draw random samples from the data, apply a proposed algorithm, and evaluate the proficiency of the proposed algorithm via three different measures (code provided). A key feature of the test bed is that, once a dataset is input, a single command creates the entire test bed relative to the dataset. The particular dataset used for the first version of the test bed comes from a microarray-based classification study that analyzes a large number of microarrays, prepared with RNA from breast tumor samples from each of 295 patients. AVAILABILITY: The software and supplementary material are available at http://public.tgen.org/tgen-cb/support/testbed/ CONTACT: [email protected].

MOTIVATION: Intervention in a gene regulatory network is used to avoid undesirable states, such as those associated with a disease. Several types of intervention have been studied in the framework of a probabilistic Boolean network (PBN), which is a collection of Boolean networks in which the gene state vector transitions according to the rules of one of the constituent networks and where network choice is governed by a selection distribution. The theory of automatic control has been applied to find optimal strategies for manipulating external control variables that affect the transition probabilities to desirably affect dynamic evolution over a finite time horizon. In this paper we treat a case in which we lack the governing probability structure for Boolean network selection, so we simply have a family of Boolean networks, but where these networks possess a common attractor structure. This corresponds to the situation in which network construction is treated as an ill-posed inverse problem in which there are many Boolean networks created from the data under the constraint that they all possess attractor structures matching the data states, which are assumed to arise from sampling the steady state of the real biological network. RESULTS: Given a family of Boolean networks possessing a common attractor structure composed of singleton attractors, a control algorithm is derived by minimizing a composite finite-horizon cost function that is a weighted average over all the individual networks, the idea being that we desire a control policy that on average suits the networks because these are viewed as equivalent relative to the data. The weighting for each network at any time point is taken to be proportional to the instantaneous estimated probability of that network being the underlying network governing the state transition. The results are applied to a family of Boolean networks derived from gene-expression data collected in a study of metastatic melanoma, the intent being to devise a control strategy that reduces the WNT5A gene's action in affecting biological regulation. AVAILABILITY: The software is available on request. SUPPLEMENTARY INFORMATION: The supplementary Information is available at http://ee.tamu.edu/~edward/tree

Probabilistic Boolean Networks, which form a subclass of Markovian Genetic Regulatory Networks, have been recently introduced as a rule-based paradigm for modeling gene regulatory networks. In an earlier paper, we introduced external control into Markovian Genetic Regulatory networks. More precisely, given a Markovian genetic regulatory network whose state transition probabilities depend on an external (control) variable, a Dynamic Programming-based procedure was developed by which one could choose the sequence of control actions that minimized a given performance index over a finite number of steps. The control algorithm of that paper, however, could be implemented only when one had perfect knowledge of the states of the Markov Chain. This paper presents a control strategy that can be implemented in the imperfect information case, and makes use of the available measurements which are assumed to be probabilistically related to the states of the underlying Markov Chain.