ZAPs and Non-Interactive Witness Indistinguishability from Indistinguishability Obfuscation, by Nir Bitansky and Omer Paneth
We present new constructions of two-message and one-message witness-indistinguishable proofs (ZAPs and NIWIs). This includes:
ZAP (or, equivalently, non-interactive zero-knowledge in the common random string model) from indistinguishability obfuscation and one-way functions.
NIWIs from indistinguishability obfuscation and one-way permutations.
The previous construction of ZAPs [Dwork and Naor, FOCS 00] was based on trapdoor permutations. The two previous NIWI constructions were based either on ZAPs and a derandomization-type complexity assumption [Barak, Ong, and Vadhan CRYPTO 03], or on a specific number theoretic assumption in bilinear groups [Groth, Sahai, and Ostrovsky, CRYPTO 06].
Optimal Resilience Broadcast against Locally Bounded and General Adversaries, by Aris Pagourtzis, Giorgos Panagiotakos, Dimitris Sakavalas
We study the Reliable Broadcast problem in incomplete networks, under the locally bounded adversarial model (Koo, 2004), that is, there is a known bound on the number of players that a Byzantine adversary controls in each player\'s neighborhood. We generalize the model
to the more realistic non-uniform case, by allowing this bound to vary from node to node.
We first settle an open question of Pelc and Peleg (2005) in the affirmative, by showing that Koo\'s Certified Propagation Algorithm (CPA) for ad hoc networks is indeed unique, that is, it can tolerate as many local corruptions as any other non-faulty algorithm, thus having optimal resilience. Actually, we prove the stronger result that a natural extension of CPA is unique for the non-uniform model. We do this by providing a necessary and sufficient condition for reliable broadcast in ad hoc networks. On the other hand, we show that it is NP-hard to check whether this condition holds for a given graph G.
We also study known topology networks and prove that a topological condition, shown by Pelc and Peleg to be necessary for the existence of a Broadcast algorithm, is also sufficient. This leads to an optimal resilience algorithm for known networks as well. On the downside, we prove that PPA is inefficient. However, we are able to provide evidence showing that probably no efficient protocol of optimal resilience exists.
We take one more step, by considering a hybrid between ad hoc and known topology networks: each node knows a part of the network, namely a connected subgraph containing itself. We show that this partial knowledge model allows for more accurate reliable broadcast
Finally, we show that our results extend to the general adversary model. This, among others, means that an appropriate adaptation of CPA is unique against general adversaries in ad hoc networks.