Virtual backbone structures are of fundamental importance in mobile ad hoc networks (MANET) as they are essential to support various applications such as service discovery and provision, multicast, routing, etc. In this paper we consider a very natural approach for the creation of virtual backbones, based on weakly-dominating sets, and investigate its security properties against Byzantine adversaries that can corrupt up to a given threshold of nodes. We formalize the notion of secure protocols for the creation and management of virtual backbones, and design a distributed protocol generating weakly-dominating virtual backbones, that is both efficient, according to standard MANET metrics, and secure against Byzantine adversaries corrupting up to a given threshold of nodes

Reliable server pooling (rSerPool) is an architecture and a set of protocols allowing a service provider to run several servers that can reliably provide the same service. Should a particular server fail while providing its service, another server can efficiently replace it. This property is attractive not only for wired but also for wireless networks. However, the unique characteristics of mobile ad hoc networks (MANETs) bring serious reliability and security challenges to the application of rSerPool. In this paper, we perform a comprehensive investigation of the security of rSerPool in MANET against both server failures and, especially, Byzantine attacks. We formulate security requirements for rSerPool in MANET and design efficient, distributed, and survivable security solutions for both main phases of rSerPool: service discovery and service provision. Specifically, we secure the service discovery phase by using a secure multiple-dominating set creation protocol, and the service provision phase by using a novel type of threshold signature scheme. Both protocols address novel security goals and are of independent interest as they can find applications to other areas; most notably, the construction of a distributed and survivable public-key infrastructure in MANET.

Approximate message authentication codes (AMACs) for binary alphabets have been introduced recently as noise-tolerant authenticators. Different from conventional “hard” message authentications that are designed to detect even the slightest changes in messages, AMACs are designed to tolerate a small amount of noise in messages for applications where slight noise is acceptable, such as in multimedia communications. Binary AMACs, however, have several limitations. First, they do not naturally deal with messages having$N$-ary alphabets$(N≫2)$. AMACs are distance-preserving codes; i.e., the distance between two authentication tags reflects the distance between two messages. Binary representation of$N$-ary alphabets, however, may destroy the original distance information between$N$-ary messages. Second, binary AMACs lack a means to adjust authentication sensitivity. Different applications may require different sensitivities against noise. AMACs for$N$-ary alphabets are designed as a cryptographic primitive to overcome the limitations of binary AMACs.$N$-ary AMACs not only directly process messages having$N$-ary alphabets but also provide sensitivity control on the authentication of binary and of$N$-ary messages. The generalized$N$-ary AMAC algorithm and its probabilistic model are developed. A statistical analysis characterizing the behavior of$N$-ary AMACs is provided along with the simulations illustrating their properties. Security analysis under chosen message attack is also developed.

The paper introduces a new construct of message authentication codes called DBMAC. It can not only provide the message authentication functionality but also localize a few errors in the message. DBMAC uses a conventional MAC in its construction such that it inherits the conventional MACs resistance to forgeries. Furthermore, the division and butterfly structure gives the capability of localizing a few errors. Our construction can be proved to have almost optimal asymptotic tag length. We also extensively analyze the error correction capabilities of our construction for small message length values.