Recent zbMATH articles in MSC 68M14https://www.zbmath.org/atom/cc/68M142021-04-16T16:22:00+00:00WerkzeugBeyond honest majority: the round complexity of fair and robust multi-party computation.https://www.zbmath.org/1456.941042021-04-16T16:22:00+00:00"Patra, Arpita"https://www.zbmath.org/authors/?q=ai:patra.arpita"Ravi, Divya"https://www.zbmath.org/authors/?q=ai:ravi.divyaSummary: Two of the most sought-after properties of multi-party computation (MPC) protocols are fairness and guaranteed output delivery (GOD), the latter also referred to as robustness. Achieving both, however, brings in the necessary requirement of malicious-minority. In a generalised adversarial setting where the adversary is allowed to corrupt both actively and passively, the necessary bound for a \(n\)-party fair or robust protocol turns out to be \(t_a+t_p<n\), where \(t_a\), \(t_p\) denote the threshold for active and passive corruption with the latter subsuming the former. Subsuming the malicious-minority as a boundary special case, this setting, denoted as dynamic corruption, opens up a range of possible corruption scenarios for the adversary. While dynamic corruption includes the entire range of thresholds for \((t_a,t_p)\) starting from \((\lceil\frac{n}{2}\rceil-1,\lfloor n/2 \rfloor)\) to \((0,n-1)\), the boundary corruption restricts the adversary only to the boundary cases of \((\lceil\frac{n}{2} \rceil-1,\lfloor n/2\rfloor)\) and \((0,n-1)\). Notably, both corruption settings empower an adversary to control majority of the parties, yet ensuring the count on active corruption never goes beyond \(\lceil\frac{n}{2}\rceil-1\). We target the round complexity of fair and robust MPC tolerating dynamic and boundary adversaries. As it turns out, \(\lceil n/2\rceil+1\) rounds are necessary and sufficient for fair as well as robust MPC tolerating dynamic corruption. The non-constant barrier raised by dynamic corruption can be sailed through for a boundary adversary. The round complexity of 3 and 4 is necessary and sufficient for fair and GOD protocols respectively, with the latter having an exception of allowing 3 round protocols in the presence of a single active corruption. While all our lower bounds assume pair-wise private and broadcast channels and are resilient to the presence of both public (CRS) and private (PKI) setup, our upper bounds are broadcast-only and assume only public setup. The traditional and popular setting of malicious-minority, being restricted compared to both dynamic and boundary setting, requires 3 and 2 rounds in the presence of public and private setup respectively for both fair as well as GOD protocols.
For the entire collection see [Zbl 1428.94008].Emergent open-endedness from contagion of the fittest.https://www.zbmath.org/1456.680132021-04-16T16:22:00+00:00"Abrahão, Felipe S."https://www.zbmath.org/authors/?q=ai:abrahao.felipe-s"Wehmuth, Klaus"https://www.zbmath.org/authors/?q=ai:wehmuth.klaus"Ziviani, Artur"https://www.zbmath.org/authors/?q=ai:ziviani.arturSummary: This paper presents a theoretical investigation of the general problem of emergent irreducible information in networked populations of computable systems. In particular, we narrow our scope to study this problem in algorithmic networks composed of randomly generated Turing machines that follow a susceptible-infected-susceptible contagion model of imitation of the fittest neighbor. We show that there is a lower bound for the stationary prevalence (i.e., the average density of infected nodes by the fittest nodes) that triggers expected (local) emergent openendedness, that is, that triggers an unlimited increase of the expected local emergent algorithmic complexity (or information) of a node as the population size grows. In addition, we show that static networks with a power-law degree distribution following the Barabási-Albert model satisfy this lower bound and thus display expected (local) emergent openendedness.A method of protected distribution of data among unreliable and untrusted nodes.https://www.zbmath.org/1456.680322021-04-16T16:22:00+00:00"Kosolapov, Yuriĭ V. Vladimirovich"https://www.zbmath.org/authors/?q=ai:kosolapov.yurii-v-vladimirovich"Pevnev, Fedor Sergeevich"https://www.zbmath.org/authors/?q=ai:pevnev.fedor-sergeevichSummary: We consider a model of protecting the confidentiality and recoverability of data in a distributed storage system. It is assumed that informational blocks are coded into the code blocks. Then the blocks are divided into parts and distributed among repositories of the distributed storage. A modification of the code noising method is constructed which simultaneously provides computational resistance to coalition attacks on confidentiality of stored data. Moreover, the modification also provides protection from the failure of a part of the storage nodes. Confidentiality protection is provided for coalitions of greater cardinality than in the case of using the classical method of code noising. It is shown that computational resistance is based on the complexity of solving one well-known problem of theoretical coding.The broadcast message complexity of secure multiparty computation.https://www.zbmath.org/1456.940772021-04-16T16:22:00+00:00"Garg, Sanjam"https://www.zbmath.org/authors/?q=ai:garg.sanjam"Goel, Aarushi"https://www.zbmath.org/authors/?q=ai:goel.aarushi"Jain, Abhishek"https://www.zbmath.org/authors/?q=ai:jain.abhishekSummary: We study the broadcast message complexity of secure multiparty computation (MPC), namely, the total number of messages that are required for securely computing any functionality in the broadcast model of communication.
MPC protocols are traditionally designed in the simultaneous broadcast model, where each round consists of every party broadcasting a message to the other parties. We show that this method of communication is sub-optimal; specifically, by eliminating simultaneity, it is, in fact, possible to reduce the broadcast message complexity of MPC.
More specifically, we establish tight lower and upper bounds on the broadcast message complexity of \(n\)-party MPC for every \(t<n\) corruption threshold, both in the plain model as well as common setup models. For example, our results show that the optimal broadcast message complexity of semi-honest MPC can be much lower than \(2n\), but necessarily requires at least three rounds of communication. We also extend our results to the malicious setting in setup models.
For the entire collection see [Zbl 1428.94008].