*00:17* [Pub][ePrint]
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 modelto 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

algorithms.

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.

*00:17* [Pub][ePrint]
Stronger Security Notions for Decentralized Traceable Attribute-Based Signatures and More Efficient Constructions, by Essam Ghadafi
Traceable attribute-based signatures extend standard attribute-based signatures by granting a designated tracing authority the power to revoke the anonymity of signatures by revealing who signed them. Such a feature is important in deterring abuse and enforcing accountability.In this work, we revisit the notion of Decentralized Traceable Attribute-Based Signatures (DTABS) introduced by El Kaafarani et al. (CT-RSA 2014) and improve the state-of-the-art in two directions: Firstly, we provide a new stronger security model which circumvents some shortcomings in existing models. Our model minimizes the trust placed in attribute authorities and hence provides, among other things, a stronger definition for non-frameability. In addition, unlike previous models, our model

captures the notion of tracing soundness which ensures that even if all parties in the system are fully corrupt, no one but the user who produced the signature could claim authorship of the signature.

Secondly, we provide a generic construction that is secure w.r.t.\\

our strong security model and show two example instantiations in the standard model which are much more efficient than existing constructions (secure under weaker security definitions).