Tassos Dimitriou

Reputation systems constitute one of the few workable mechanisms for distributed applications in which users can be made accountable for their actions. By collecting user experiences in reputation profiles, participants are encouraged to interact more with well-behaving peers hence better online behavior is motivated.

In this work, we develop a privacy-preserving reputation scheme for collaborative systems such as P2P networks in which peers can represent themselves with different pseudonyms when interacting with others. All these pseudonyms, however, are bound to the same reputation token. This allows honest peers maintain their good record even when switching to a new pseudonym, while preventing malicious peers from making a fresh start. Apart from an initial offline setup phase which is only needed to ensure reputation soundness but not privacy, our system is truly decentralized. Using an append-only distributed ledger such as Bitcoin’s blockchain, we show how participants can make anonymous yet verifiable assertions about their own reputation. Thus the system maintains soundness, peer-pseudonym unlinkability as well as unlinkability among pseudonyms of the same peer. We formally prove these properties, we discuss ways to eliminate the setup phase and we evaluate the efficiency of the various operations.

In this work we present DPTS, a data payment and transfer scheme that uses bitcoin payments to reward users for detailed electricity measurements they submit to a utility provider. DPTS emphasizes both privacy and fairness of transactions; not only it allows participants to earn bitcoins in a way that cannot be linked to their actions or identities but also ensures that data is delivered if and only if an appropriate payment is received. While DPTS is described in the smart grid setting, the protocol can also be applied in other areas where incentives are used to increase user participation. One such important area is participatory or crowd-sensing, where individuals use their smartphones to report sensed data back to a campaign administrator and obtain a reward for it. DPTS allows users to enjoy the benefits of participation without compromising anonymity. The proposal is coupled with a security analysis showing the privacy-preserving character of the system along with an efficiency analysis demonstrating the feasibility of our approach.

Most electronic voting systems today satisfy the basic requirements of privacy, unreusability, eligibility and fairness in a natural and rather straightforward way. However, receipt-freeness, incoercibility and universal verifiability are much harder to implement and in many cases they require a large amount of computation and communication overhead. In this work, we propose a blockchain-based voting system which achieves all the properties expected from secure elections without requiring too much from the voter. Coercion resistance and receipt-freeness are ensured by means of a randomizer token — a tamper-resistance source of randomness which acts as a black box in constructing the ballot for the user. Universal verifiability is ensured by the append-only structure of the blockchain, thus minimizing the trust placed in election authorities. Additionally, the system has linear overhead when tallying the votes, hence it is scalable and practical for large scale elections.

This is an expanded version of the paper below…

In this work we develop a rewarding framework that can be used as a building block in crowd-sensing applications. Our protocol allows users to submit data and obtain Bitcoin payments in a privacy-preserving manner, preventing curious providers from linking the data or the payments back to the user. At the same time, we thwart malicious user behavior such as double-redeeming attempts where a user tries to obtain rewards for multiple submissions of the same data. More importantly, we ensure the fairness of the exchange; by relying on the Blockchain, we eliminate the trust placed on third parties in traditional fair exchange protocols. Finally, our system is highly efficient as most of the protocol steps do not utilize the Blockchain network. When they do, we only rely on simple Bitcoin transactions as opposed to prior works that are based on the use of highly complex smart contracts.

The emergence of cloud computing gave users the capability to offload computations that cannot be executed locally to cloud servers with large computational power. One such computationally demanding problem is solving large satisfiability (SAT) instances. Although many problems from AI, circuit verification, etc. can be converted to SAT, outsourcing SAT instances may leak considerable information that can put a user’s security at risk. Hence the privacy of outsourcing computations to the cloud is a major issue. In this work we look at the techniques of Qin et al. (Qin and Jia., 2014; Qin and Du., 2018) which have been used to obfuscate SAT formulas before they are released to the cloud. We came up with a realistic attack against their technique that demonstrates how a malicious cloud provider can obtain significant information about the underlying SAT instance. Our work shows that ad hoc schemes cannot offer the required security guarantees for outsourcing SAT computations, hence more formal frameworks should be used instead.

Containers emerged as a lightweight alternative to virtual machines (VMs) that offer better microservice architecture support. The value of the container market is expected to reach 2.7 billion in 2020 as compared to 762 million in 2016. Although they are considered the standardized method for microservices deployment, playing an important role in cloud computing emerging fields such as service meshes, market surveys show that container security is the main concern and adoption barrier for many companies. In this paper, we survey the literature on container security and solutions. We have derived four generalized use cases that should cover security requirements within the host-container threat landscape. The use cases include: (I) protecting a container from applications inside it, (II) inter-container protection, (III) protecting the host from containers, and (IV) protecting containers from a malicious or semi-honest host. We found that the first three use cases utilize a software-based solutions that mainly rely on Linux kernel features (e.g., namespaces, CGroups, capabilities, and seccomp) and Linux security modules (e.g., AppArmor). The last use case relies on hardware-based solutions such as trusted platform modules (TPMs) and trusted platform support (e.g., Intel SGX). We hope that our analysis will help researchers understand container security requirements and obtain a clearer picture of possible vulnerabilities and attacks. Finally, we highlight open research problems and future research directions that may spawn further research in this area.

In this work we present REWARDS (pRivacy prEserving reWARDing Scheme), a generic framework to be used for reward collection in the smart grid and other loyalty systems. A useful functionality to motivate user participation in such systems is to provide for a privacy-preserving mechanism to reward users for the electricity data they submit to a utility provider. Our lightweight scheme allows participants to earn and redeem incentives in a way that cannot be linked to their actions or identities.

While our presentation focuses around the smart electricity grid, the generic character of REWARDS makes it a perfect candidate for other application domains and loyalty systems where user participation is critical to the success of the application. One such important paradigm is mobile crowd-sensing, where users contribute data sensed with their smart devices to a campaign administrator and expect a reward for them.

We have analyzed the security properties of our scheme and showed that our reward tokens are indeed privacy-respecting; rewards are unlinkable to each other and token transactions do not leak any information about the user. Additionally, we have showed that our solution is highly efficient in terms of computation, communication and storage overhead, thus guaranteeing good performance in practice.

The use of Location Based Services (LBS) allow mobile users to interact with the environment and query for the location of persons, objects and services. Such applications can be used to get directions to the nearest gas station or point of interest, locate a friend on a map, receive an alert while approaching a traffic accident, get informed about an upcoming social event, and so on. However, the proliferation of LBS systems may undermine user privacy since the frequent collection of location data may reveal considerable information about an individual’s daily habits and profile. The challenge therefore is to develop effective security schemes that allow the use of these services in a way that mimics face-to-face private encounters where users can deny what have been said in the meeting. The question then becomes: can we offer a similar service in the LBS setting where users can deny their whereabouts? In this work, we present a decentralized Deniable LBS scheme which gives users the ability to deny being in a particular location even if this location has been monitored by an internal or external party. We discuss the deniability and security properties offered by our solution and perform an evaluation of the system in realistic deployment settings. To the best of our knowledge this is the first work that applies deniability in the LBS setting.

Localization is the method of estimating the location of a wireless node using measured inputs such as distances from nodes with known locations. When the measured distances from anchor nodes are used for localization, compromised nodes that are involved in the process can give false information that produces inaccurate location estimates. This paper proposes a Generalized Likelihood Ratio (GLRT) based approach to find the compromised nodes that deliberately give false information. After detecting such malicious nodes, the measurements given by them are eliminated from the localization computation to improve the location estimate. The proposed method works for Gaussian range measurement errors, which is considered more realistic, as compared to a method available in literature that works only for uniformly distributed range errors. Extensive simulations were carried out to assess the performance of the algorithm under various conditions. The proposed method was found to give better localization accuracy as compared to previous methods available in the literature which address the same problem. Simulations also showed that the algorithm performs well even when some of the assumptions used in the algorithm do not hold true.

A useful functionality to motivate user engagement in participatory sensing applications is to provide for a privacy-preserving mechanism to \emph{reward} users for the sensed data they submit to a utility provider. In this work we develop a lightweight token mechanism that allows participants to earn and redeem incentives in a way that cannot be linked to their actions or identities. Users do not have to maintain a collection of anonymous tokens but only a single one, which can be used to \emph{aggregate} multiple rewards collected by them. This increases the privacy offered by the system.

We have analyzed the security properties of our scheme and showed that our reward mechanism is privacy-respecting. Additionally, we have showed that it is highly efficient, thus outperforming previous solutions and guaranteeing good performance in practice.

Participatory or crowd-sensing applications process sensory data contributed by users and transform them to simple visualizations (such as for example noise or pollution levels) that help create an accurate representation of the surrounding environment. Although contributed data is of great interest to individuals, the involvement of citizens and community groups, however, is still limited. Hence, incentivizing users to increase participation seems crucial for the success of participatory sensing.

In this paper, we develop a privacy-preserving rewarding scheme which allows campaign administrators to reward users for the data they contribute. Our system of anonymous tokens allow users to enjoy the benefits of participation while at the same time ensuring their anonymity. Moreover, rewards can be accumulated together thus further increasing the level of privacy offered by the system. Our proposal is coupled with a security analysis showing the privacy-preserving character of the system along with an efficiency analysis demonstrating the feasibility of our approach in realistic deployment settings.

The smart grid leverages infrastructural support to achieve fine-grained power consumption monitoring in an attempt to offer higher efficiency, reliability, and security. Such functionality, however, requires the collection of fine-grained usage data which may raise serious concerns with respect to consumer privacy. Thus far, existing work has solely focused on the problem of privately aggregating energy measurements. However, these solutions do not allow the provider to acquire detailed energy measurements which are essential for maintaining the network, debugging configuration problems, etc. In this work, we address this problem and we propose an authentication scheme that allows a smart meter to anonymously interact with the utility provider when submitting detailed consumption data. We then move one step further, enabling the incorporation of anonymous rewarding mechanisms in the smart grid in exchange for detailed measurements that users report. We argue that such rewarding mechanisms provide solid incentives for users to accept the release of their detailed energy consumption; we show that our proposal does not leak any information about the identity of users—even when redeeming the rewards. Finally, we implement a prototype based on our proposal and we evaluate its performance in realistic deployment settings.

Mobile Crowdsensing (MCS) has emerged as a new paradigm for data collection and knowledge representation, where people use their devices to interact with the environment and create a more accurate picture of their surroundings. In many MCS scenarios it is desirable to give micro-payments to contributors as an incentive for their participation. However, to further encourage participants to use the system, one important requirement is protection of user privacy. In this work we present a multi-attribute reverse auction mechanism as an efficient way to offer incentives to users by allowing them to determine their own price for the data they provide, but also as a way to motivate them to submit better quality data. Our auction protocol guarantees bidders’ anonymity and suggests a new rewarding mechanism that enables winners to claim their reward without being linked to the data they contributed. We have analyzed our protocol and showed that it offers strong security and privacy guarantees in all phases of the auction process, from bidding to rewarding. Additionally, we have implemented the protocol using off-the-shelf cryptographic primitives; our experiments show that the protocol is scalable, it can be applied to a large class of auctions and remains efficient from both a computation and communication point of view so that it can be run to the users’ mobile devices.

Software-defined networking is a promising networking paradigm for achieving programmability and centralized control in communication networks. These features simplify network management and enable innovation in network applications and services such as routing, virtual machine migration, load balancing, security, access control, and traffic engineering. The routing application can be optimized for power efficiency by routing flows and coalescing them such that the least number of links is activated with the lowest link rates. However, in practice, flow coalescing can generally overflow the flow tables, which are implemented in a size-limited and power-hungry ternary content addressable memory (TCAM). In this paper, a set of practical constraints is imposed to the software-defined networking routing problem, namely, size-limited flow table and discrete link rate constraints, to ensure applicability in real networks. Because the problem is NP-hard and difficult to approximate, a low-complexity particle swarm optimization–based and power-efficient routing (PSOPR) heuristic is proposed. Performance evaluation results revealed that PSOPR achieves more than 90% of the optimal network power consumption while requiring only 0.0045% to 0.9% of the optimal computation time in real-network topologies. In addition, PSOPR generates shorter routes than the optimal routes generated by CPLEX.

Location Based Services (LBS) are often used in applications that allow users to interact with the environment and query for the location of persons, objects and services. However, such systems may undermine user privacy since the frequent collection of location data may reveal considerable information about an individual’s daily habits and profile. In this work, we present our Deniable-LBS scheme which gives users the ability to deny being in a particular location even if this location has been monitored by an internal or external party.

In a node replication attack, an adversary creates replicas of captured sensor nodes in an attempt to control information that is reaching the base station or, more generally, compromise the functionality of the network. In this work, we develop fully distributed and completely decentralized schemes to detect and evict multiple imposters in mobile wireless sensor networks (MWSNs). The proposed schemes not only quarantines these malicious nodes but also withstand collusion against collaborating imposters trying to blacklist legitimate nodes of the network. Hence the completeness and soundness of the protocols is guaranteed. Our protocols are coupled with extensive mathematical and experimental results, proving the viability of our proposals, thus making them fit for realistic mobile sensor network deployments.

The smart electricity grid introduces new opportunities for fine-grained consumption monitoring. Such functionality, however, requires the constant collection of electricity data that can be used to undermine consumer privacy. In this work, we address this problem by proposing two decentralized protocols to securely aggregate the measurements of n smart meters. The first protocol is a very lightweight one, it uses only symmetric cryptographic primitives and provides security against honest-but-curious adversaries. The second protocol is public-key based and considers the malicious adversarial model; malicious entities not only try to learn the private measurements of smart meters but also disrupt protocol execution. Both protocols do not rely on centralized entities or trusted third parties to operate. Additionally, we show that they are highly scalable owning to the fact that every smart meter has to interact with only a few others, thus requiring only O(1) work and memory overhead. Finally, we implement a prototype based on our proposals and we evaluate its performance in realistic deployment settings.

RFID, which stands for Radio Frequency Identification, is a relatively new technology often envisioned as an enabler of the Internet of Things. The widespread use of this technology, however, introduces many security and privacy risks since tags contain information that can be easily obtained by anyone with a reader. Eventually this can lead to tracking of users, profiling and violation of their basic right to privacy.

In this work we make an important step in providing for RFID privacy by letting users control all the tags they possess. The moment a person buys a tagged object and becomes the owner of it, no one should be able to find any information about the object or have access to the tag. We do this by developing and formalizing the notion of a key-evolving RFID system. In particular, (i) we explain how such a system can be made forward secure using pseudo-random generators and functions, (ii) we derive concrete results based on the security of the underlying primitives, and (iii), we explain how this can be realized in practice using a protocol that achieves secure ownership transfer and controlled delegation without relying on Trusted Third Parties.

In many mobile crowd-sensing scenarios it is desirable to give micro-payments to contributors as an incentive for their participation. However, to further encourage participants to use the system, one important requirement is protection of user privacy. In this work we present a reverse auction mechanism as an efficient way to offer incentives to users by allowing them to determine their own price for the data they provide, but also as a way to motivate them to submit better quality data. At the same time our auction protocol guarantees bidders’ anonymity and suggests a new rewarding mechanism that enables winners to claim their reward without being linked to the data they contributed. Our protocol is scalable, can be applied to a large class of auctions and remains both computation- and communication-efficient so that it can be run to the mobile devices of users.

In a node replication attack, an adversary creates replicas of captured sensor nodes in an attempt to control information that is reaching the base station or, more generally, compromise the functionality of the network. In this work, we develop fully distributed and completely decentralized schemes to detect and evict multiple imposters in mobile wireless sensor networks (MWSNs). The proposed schemes not only quarantine these malicious nodes but also withstand collusion against collaborating imposters trying to blacklist legitimate nodes of the network. Hence the completeness and soundness of the protocols are guaranteed. Our protocols are coupled with extensive mathematical and experimental results, proving the viability of our proposals, thus making them fit for realistic mobile sensor network deployments.

In typical mobile sensing architectures, sensing data are collected from users and stored in centralized servers at third parties, making it difficult to effectively protect users’ privacy. A better way to protect privacy is to upload sensing data on personal data stores, which are owned and controlled by the users, enabling them to supervise and limit personal data disclosure and exercise access control to their data. The problem however remains how data requesters can discover the users who can offer them the data they need. In this paper we suggest a mobile sensing platform that enables data requesters to discover data producers within a specific geographic region and acquire their data. Our platform protects the anonymity of both requesters and producers, while at the same time it enables the incorporation of trust frameworks, incentive mechanisms and privacy-respecting reputation schemes. We also present extensive experimental results that demonstrate the efficiency of our approach in terms of scalability, load balancing and performance.

The smart-grid is gaining increasing attention nowadays, owing to its premise to offer increased reliability, performance and a balanced utilization of energy. However, the current design of smart-grids raises serious concerns with respect to the privacy and anonymity of users. Thus far, the literature has solely focused on the problem of privately aggregating energy reports and has not addressed the privacy threats that can occur through other intelligent operations that take place in the smart grid such as planning the energy distribution in the smart grid.

In this paper, we propose a novel solution that enables the planning of energy distribution in the grid without leaking any information about the energy requests of individual smart meters. We also implement a prototype based on our proposal and we evaluate its performance in realistic deployment settings.

In this work we make an important step in providing for RFID privacy by letting users control all the tags they possess. The moment a person buys a tagged object and becomes the owner of it, no one should be able to find any information about the object or have access to the tag. We do this by developing and formalizing the notion of a key-evolving RFID system. In particular, (i) we explain how such a system can be made forward secure using pseudo-random generators and functions, (ii) we derive concrete results based on the security of the underlying primitives, and (iii), we show how this can be effectively realized in practice.

In this work, we describe two decentralized protocols that can be used to securely aggregate the electricity measurements of n smart meters. The first protocol is a very lightweight one, it uses only symmetric cryptographic primitives and provides security against honest-but-curious adversaries. The second one is public-key based and its focus in on the malicious adversarial model; malicious entities not only try to learn the private measurements of smart meters but can also disrupt protocol execution. Both protocols do not rely on centralized entities or trusted third parties to operate and they are highly scalable owning to the fact that every smart meter has to interact with only a few other meters. Both are very efficient in practice requiring only O(1) work and memory overhead per meter, thus making these protocols fit for real-life smart grid deployments..

Several protocols have been proposed to date to defend against wormhole attacks in wireless networks by adopting synchronized clocks, positioning devices, or directional antennas. These requirements and assumptions limit their applicability especially in the case of mobile networks where the degree of association and de-association between the nodes is relatively high. In this work, we present a novel lightweight countermeasure for the wormhole attack, called LDAC (Localized-Decentralized Algorithm for Countering wormholes). It is completely localized and works by looking for simple evidence that no attack is taking place, using only connectivity information, as implied by the underlying communication graph. LDAC is not confined to static networks but extends naturally to dynamic and even mobile ones. Rigorous arguments that prove the correctness of the algorithm are coupled with detailed performance evaluation along with an implementation on real sensor devices that demonstrates its efficiency in terms of memory requirements and processing overhead.

In this paper, we describe a decentralized privacy-preserving protocol for securely casting trust ratings in distributed reputation systems. Our protocol allows n participants to cast their votes in a way that preserves the privacy of individual values against both internal and external attacks. The protocol is coupled with an extensive theoretical analysis in which we formally prove that our protocol is resistant to collusion against as many as n − 1 corrupted nodes in both the semi-honest and malicious adversarial models.

The behavior of our protocol is tested in a real P2P network by measuring its communication delay and processing overhead. The experimental results uncover the advantages of our protocol over previous works in the area; without sacrificing security, our decentralized protocol is shown to be almost one order of magnitude faster than the previous best protocol for providing anonymous feedback.

Crowd-sensing applications are based on the contribution of user-related context information and as such, they are particularly vulnerable to privacy-compromising attacks. In this paper we focus on the problem of information discovery by data consumers who can pose queries to mobile users providing sensed data. The way to protect the privacy of these mobile users is through the use of cloud-based agents, which obfuscate user location and enforce the sharing practices of their owners. The cloud agents organise themselves in a structure, namely a quadtree, that enables queriers to contact directly the mobile users in the area of interest and, based on their own criteria, select the ones to get sensing data from. The tree is kept in a decentralized manner, stored and maintained by the mobile agents themselves, thus avoiding the privacy implications of previous, centralized techniques. Our proposed solution complements and expands upon prior work in the area while it is shown experimentally to be both scalable, efficient and easy to maintain.

The smart-grid is gaining increasing attention nowadays, owing to its premise to oer increased reliability and performance. However, the current design of smart-grids raises serious concerns with respect to privacy and anonymity of users.

In this paper, we address the problem of enhancing the privacy of users in the smart grid throughout the reporting and the billing phases. To that end, we propose a taxonomy of solutions that enable (i) the privacy-preserving aggregation of smart meters’ energy consumption reports without relying on a single point of trust, (ii) the anonymous tasking, e.g., the outsourcing of (maintenance) tasks to smart meters, and (iii) the privacy-preserving billing and barter of energy between the utility provider and the smart meters. To the best of our knowledge, this is the first contribution that comprehensively addresses privacy issues in the tasking and energy-trading processes in smart grids. Our proposed solutions complement previous work in the area and can be easily integrated within existing smart grids.

In this paper, we describe a decentralized privacy-preserving protocol for securely casting trust ratings in distributed reputation systems. Our protocol allows N participants to cast their votes in a way that preserves the privacy of individual values against both internal and external attacks. The protocol is coupled with an extensive theoretical analysis in which we formally prove that our protocol is resistant to collusion against as many as N-1 corrupted nodes in the semi-honest model.

The behavior of our protocol is tested in a real P2P network by measuring its communication delay and processing overhead. The experimental results uncover the advantages of our protocol over previous works in the area; without sacrificing security, our decentralized protocol is shown to be almost one order of magnitude faster than the previous best protocol for providing anonymous feedback.

In this work we study the problem of querier privacy in the Participatory Sensing domain. While prior work has attempted to protect the privacy of people contributing sensing data from their mobile phones, little or no work has focused on the problem of querier privacy. Motivated by a novel communication model in which clients may directly query participatory sensing networks operated by potentially untrusted adversaries, we provide a privacy-preserving access control scheme for participatory sensing applications that focuses on the privacy of the querier. Contrary to past solutions, we enable queriers to have access to the data provided by participating users without placing any trust in third parties or reducing the scope of queries. Additionally, our approach naturally extends the traditional pull/push models of participatory sensing and integrates nicely with mobile social networks, a new breed of sensing which combines mobile sensor devices with personal sensing environments.

An Unattended Wireless Sensor Network (UWSN) is a recently introduced type of sensor network in which realtime data delivery of information is replaced by periodic, offline collection of the sensed data. In this work we focus on UWSNs operating in a hostile environment where the goal of an attacker is to prevent targeted data from ever reaching the sink. More precisely, we study the Data Authentication problem in the presence of a Mobile Adversary who is aiming to target a sensor's data and modify it without being detected.

Inspired by the pollination process in nature, we propose two schemes that diffuse data footprints in the network using message carrying "butterflies". These schemes greatly increase the robustness of the network against data modification attempts by the mobile adversary. Extensive analytical and experimental results confirm the superiority of both Pollination and Pollination Light over previous protocols in terms of both security and communication overhead.

A journal version of the paper below…

In this invited paper, we focus on attacks and defense mechanisms in additive reputation systems. We start by surveying the most important protocols that aim to provide privacy between individual voters. Then, we categorize attacks against additive reputation systems considering both malicious querying nodes and malicious reporting nodes that collaborate in order to undermine the vote privacy of the remaining users. To the best of our knowledge this is the rst work that provides a description of such malicious behavior against such systems. In light of this analysis we demonstrate the ineciencies of existing protocols.

The expansion of both pervasive computing and sensor networking enables the design and proliferation of intelligent sensor-based applications. At the same time, sensor network security is a very important research area whose goal is to maintain a high degree of confidentiality, integrity and availability of both information and network resources. However, a common threat that is often overlooked in the design of secure sensor network applications is the existence of spyware programs. As most researchers try to defend against adversaries who plan to physically compromise sensor nodes and disrupt network functionality, the risk of spyware programs and their potential for damage and information leakage is bound to increase in the years to come. This work demonstrates Spy-Sense, a spyware tool that allows the injection of stealthy exploits in the heart of each node in a sensor network. Spy-Sense is undetectable, hard to recognize and get rid of, and once activated, it runs in a discrete background operation without interfering or disrupting normal network operation. It provides the ability of executing a stealthy exploit sequence that can be used to achieve the intruder's goals while reliably evading detection. To the best of our knowledge, this is the first instance of a spyware program that is able to crack the confidentiality and functionality of a sensor network. By exposing the vulnerabilities of sensor networks to spyware attacks, we hope to instigate discussion on these critical issues because sensor networks will never succeed without adequate provisions on security and privacy.

As the domains of pervasive computing and sensor networking are expanding, there is an ongoing trend towards assistive living and healthcare support environments that can effectively assimilate these technologies according to human needs. Most of the existing research in assistive healthcare follows a more passive approach and has focused on collecting and processing data using a static-topology and an application-aware infrastructure. However, with the technological advances in sensing, computation, storage, and communications, a new era is about to emerge changing the traditional view of sensor-based assistive environments where people are passive data consumers, with one where people carry mobile sensing elements involving large volumes of data related to everyday human activities. This evolution will be driven by people centric sensing and will turn mobile phones into global mobile sensing devices enabling thousands new personal, social, and public sensing applications. In this paper, we discuss our vision for people-centric sensing in assistive healthcare environments and study the security challenges it brings. This highly dynamic and mobile setting presents new challenges for information security, data privacy and ethics, caused by the ubiquitous nature of data traces originating from sensors carried by people. We aim to instigate discussion on these critical issues because people-centric sensing will never succeed without adequate provisions on security and privacy. To that end, we discuss the latest advances in security and privacy protection strategies that hold promise in this new exciting paradigm. We hope this work will better highlight the need for privacy in people-centric sensing applications and spawn further research in this area.

In this work we study the problem of query privacy in large scale sensor networks. Motivated by a novel trust model in which clients query networks owned by trusted entities but operated by potentially untrusted adversaries, we consider several proposals for protecting the identities of the queried sensors.

Our schemes do not rely on the use of public key cryptography nor do they make any assumptions on the topology of the network. Inspired by the data-centric communication model and the collaborative nature of sensor networks, our proposals distribute the data in random locations to be later retrieved by random direction queries, using only local computations and total absence of coordination. It is perhaps of interest to note that query privacy is achieved using only lightweight, symmetric cryptographic primitives.

Extensive analytical and experimental results confirm that the proposed protocols can achieve their goals using only minimal communication and storage overhead.

During the last few years there has been an increasing number of people-centric sensing projects. These combine location information with sensors available on mobile phones, giving birth to a different dimension in sensing our environment and providing us with new opportunities to create collective intelligence systems to address urban-scale problems, like air pollution, noise, traffic, etc. However, as people are directly involved in the collection process, they often inadvertently reveal information about themselves, raising new and important privacy concerns. While standard privacy enhancing technologies exist, they do not fully cover the many peculiarities of these new pervasive applications. The ubiquitous nature of the communication and the storage of location traces compose a complex set of threats on privacy, which we overview in this article. Then, we go through the latest advances in security and privacy protection strategies and we discuss how they fit with this new paradigm of people-centric sensing applications. We hope this work will better highlight the needs for privacy in urban sensing applications and spawn further research in this area.

This work proposes an effective method of fighting spam by developing Inexpensive Email Addresses (IEA), a stateless system of Disposable Email Addresses (DEAs). IEA can cryptographically generate exclusive email addresses for each sender, with the ability to re-establish a new email address once the old one is compromised. IEA accomplishes proof-of-work by integrating a challenge-response mechanism to be completed before an email is accepted in the recipient's mail system. The system rejects all incoming emails and instead embeds the challenge inside the rejection notice of Standard Mail Transfer Protocol (SMTP) error messages. The system does not create an out-of-band email for the challenge, thus eliminating email backscatter in comparison to other challenge-response email systems. The system is also effective in identifying spammers by exposing the exact channel, i.e. the unique email address that was compromised, so misuse could be traced back to the compromising party. Usability is of utmost concern in building such a system by making it friendly to the end-user and easy to setup and maintain by the system administrator.

See paper below.

A number of protocols have been proposed to date to defend against wormhole attacks in wireless networks by adopting synchronized clocks, positioning devices, or directional antennas. In this work, we introduce a novel approach for detecting wormhole attacks. The proposed algorithm is completely localized and works by looking for simple evidence that no attack is taking place, using only connectivity information as implied by the underlying communication graph, and total absence of coordination. Unlike many existing techniques, it does not use any specialized hardware, making it extremely useful for real-world scenarios. Most importantly, however, the algorithm can always prevent wormholes, irrespective of the density of the network, while its efficiency is not affected even by frequent connectivity changes. We also provide an analytical evaluation of the algorithm's correctness along with an implementation on real sensor devices that demonstrates its efficiency in terms of memory requirements and processing overhead.

Currently proposed solutions to secure code dissemination in wireless sensor networks (WSNs) involve the use of expensive public-key digital signatures. In this work we present Scatter, a secure code dissemination scheme that enables sensor nodes to authenticate the program image efficiently. To achieve this, we use a scheme that offers source authentication in the group setting like a public-key signature scheme, but with signature and verification times much closer to those of a MAC. In this way, Scatter avoids the use of Elliptic Key Cryptography and manages to surpass all previous attempts for secure code dissemination in terms of energy consumption, memory and time efficiency. Besides the design and theoretical analysis of the solution, we also report the experimental evaluation of Scatter in two different hardware platforms, Mica2 and MicaZ, which proves its efficiency in practice.

The pervasive interconnection of autonomous sensor devices has given birth to a broad class of exciting new applications. At the same time, however, the unattended nature and the limited resources of sensor nodes have created an equal number of vulnerabilities that attackers can exploit in order to gain access in the network and the information transferred within. While much work has been done on trying to defend these networks, little has been done on suggesting sophisticated tools for proving how vulnerable sensor networks are. This work demonstrates a tool that allows both passive monitoring of transactional data in sensor networks, such as message rate, mote frequency, message routing, etc., but also discharge of various attacks against them. To the best of our knowledge, this is the first instance of an attack tool that can be used by an adversary to penetrate the confidentiality and functionality of a sensor network. Results show that our tool can be flexibly applied to different sensor network operating systems and protocol stacks giving an adversary privileges to which she is not entitled to. We hope that our tool will be used proactively, to study the weaknesses of new security protocols, and, hopefully, to enhance the level of security provided by these solutions even further.

Malicious code (or malware) is defined as software designed to execute attacks on software systems and fulfill the harmful intents of an attacker. As lightweight embedded devices become more ubiquitous and increasingly networked, they present a new and very disturbing target for malware developers. In this paper, we demonstrate how to execute malware on wireless sensor nodes that are based on the von Neumann architecture. We achieve this by exploiting a buffer overflow vulnerability to smash the call stack and intrude a remote node over the radio channel. By breaking the malware into multiple packets, the attacker can inject arbitrarily long malicious code to the node and completely take control of it. Then we proceed to show how the malware can be crafted to become a self-replicating worm that broadcasts itself and propagates over the network hop-by-hop, infecting all the nodes. To our knowledge, this is the first instance of a self-propagating worm that can execute arbitrary code. We also provide a complete implementation of our attack, measure its effectiveness in terms of time taken for the worm to propagate to the entire sensor network and, finally, suggest possible countermeasures.

As the amount of information resources on the Web keeps increasing so are the concerns for information integrity, confidentiality and authenticity. In Web 2.0 users are producers as well as consumers of content and metadata, which makes guaranteeing the authenticity and integrity of information critical. The scale of the Web requires that any proposals in this direction require minimal (if any) infrastructural or administrative changes. This paper proposes the use of ID-based cryptography (IBC) to address requirements for integrity and authenticity of Web resources using either the URL/URI of a resource or the DNS name part of it. This approach presents certain challenges, which are discussed along with the pros and cons of different designs and implementations.

We consider the problem of cooperative intrusion detection in wireless sensor networks where the nodes are equipped with local detector modules and have to identify the intruder in a distributed fashion. The detector modules issue suspicions about an intrusion in the sensor's neighborhood. We formally define the problem of intrusion detection and identify necessary and sufficient conditions for its solvability. Based on these conditions we develop a generic algorithm for intrusion detection and present simulations and experiments which show the effectiveness of our approach.

As pervasive interconnection of autonomous sensor devices gave birth to a broad class of exciting new applications, security emerges as a central requirement. Wireless sensor networks are vulnerable to attacks as they are frequently deployed in open and unattended environments. In this paper, we describe the wormhole attack, a severe routing attack against sensor networks that is particularly challenging to defend against. We detail its characteristics and study its effects on the successful operation of a sensor network. We present state-of-the-art research for addressing wormhole related problems in wireless sensor networks and discuss the relative strengths and shortcomings of the proposed solutions. To date, most of the proposed defenses focus on preventive mechanisms that can be applied to protect sensor networks from this kind of attacks. However, no work has been published regarding the possibility of using more sophisticated methods, like intrusion detection systems, to achieve a more complete and autonomic defense mechanism against wormhole attackers. We present our work on intrusion detection and describe how LIDeA, a lightweight IDS framework, can be used for defending against wormhole attackers.

In this work we introduce RFID-DOT, a protocol for secure access, Delegation and Ownership Transfer of tags along with a model for formally defining privacy in such an environment. As current RFID tags emit constant identifiers that may help in identifying user habits and tracking of people, RFID-DOT allows a user to securely own tagged products. Once a person becomes the owner of such an item, no one can have access to the tag nor find any information about it. Thus user privacy is guaranteed. Additionally, the protocol is secure against such attacks as tag cloning, tag/reader spoofing, eavesdropping, desynchronization and so on.

Furthermore, since we don't expect a tagged item to stay with same owner forever, we provide the means to achieve ownership transfer and release without compromising the privacy of future or past owners. And in the unlikely case where user privacy is compromised, it can be restored in a simple and intuitive manner. Thus RFID-DOT achieves a very strong notion of security that is necessary in RFID ownership transfer: forward and backward privacy.

Wireless sensor networks are vulnerable to adversaries as they are frequently deployed in open and unattended environments. Preventive mechanisms can be applied to protect them from an assortment of attacks. However, more sophisticated methods, like intrusion detection systems, are needed to achieve a more autonomic and complete defense mechanism, even against attacks that have not been anticipated in advance.

In this paper, we present a lightweight intrusion detection system, called LIDeA (Lightweight Intrusion DEtection Architecture), designed for wireless sensor networks. LIDeA is based on a distributed architecture, in which nodes overhear their neighboring nodes and collaborate with each other in order to successfully detect an intrusion. We show how such a system can be implemented in TinyOS, which components and interfaces are needed, and what is the resulting overhead imposed.

Within the hospital or extended care environment, there is an overwhelming need for constant monitoring of vital body functions and support for patient mobility. Tomorrow's biomedical networks will address these needs by incorporating new technologies like wireless sensor networks into their infrastructure. However, wireless transmission of sensitive patient data presents some obvious security concerns. In this paper we discuss these concerns and how they are addressed by existing systems. We also discuss issues that need further consideration, such as run-time composition of security services depending on the criticality of data transmitted along with a solution for practical sensor systems using TinyOS. Finally, we propose intrusion detection as a future research direction for biomedical sensor networks and we elaborate on the main components of such a system.

One of the reasons that the research of intrusion detection in wireless sensor networks has not advanced significantly is that the concept of "intrusion" is not clear in these networks. In this paper we investigate in depth one of the most severe attacks against sensor networks, namely the sinkhole attack, and we emphasize on strategies that an attacker can follow to successfully launch such an attack. Then we propose specific detection rules that can make legitimate nodes become aware of the threat, while the attack is still taking place. Finally, we demonstrate the attack and present some implementation details that emphasize the little effort that an attacker would need to put in order to break into a realistic sensor network.

Radio Frequency IDentification (RFID) is a method of remotely storing and retrieving data using small and inexpensive devices called RFID tags. However, the widespread use of RF Identification also introduces serious security and privacy risks since information about tags can easily be retrieved by hidden readers, thus leading to violation of user privacy and tracking of individuals by the tags they carry.

In this work we propose a proxy agent framework that uses a personal device for privacy enforcement and increased protection against eavesdropping, impersonation and cloning attacks. Using the proxy a user decides when and where information will be released. In particular, the user can put tags under her control, authenticate requests, release tags, transfer them to new owners, and so on. This is the first framework that unifies previous attempts and presents detailed protocols for all the operations required in such a proxy environment.

In this paper, we propose a novel hybrid system for handling reputation in Super-Peer-based networks by combining the personal history of each user's interactions with other users, the opinions of peer-friends together with global ratings of peers as they emerge from all of their interactions with other users of the network. We introduce the notion of peer friends in a P2P network and use it to prevent malicious collectives from reducing the reputation of a peer in the network. We also present a secure distributed framework that ensures that trust reports remain encrypted and are never opened during the submission or aggregation process. Computational results from our distributed prototype simulation show that our solution compares favorably with all other proposed methods for handling reputation when subject to various malicious strategies.

Wireless sensor networks have emerged as an exciting new area of research in computer science. Continuously shrinking battery powered nodes are equipped with processing, sensing and RF capabilities. However, deploying a network into a realistic environment requires iteratively reprogramming dozens of nodes, locating them throughout an area large enough to produce an interesting radio topology, and instrumenting them to extract debugging and performance data.

A number of testbed approaches have been proposed by universities and industry to ease the burden imposed by this deployment exercise. These testbeds vary in the number and type of motes employed and the manner they are connected to the central computer  system. For example a separate wired back-channel is usually used for reprogramming, network management and data logging issues. However, this introduces increased cost due to additional hardware equipment required and exhibits low scalability. In this work, we present an efficient and low cost sensor network testbed that exploits only the wireless channel to transfer data and offers an additional number of benefits to users and  administrators like ease of deployment, ease of use, no need of a wired infrastructure, coping with multiple users at the same time and most importantly scalability.

Hierarchical processing in sensor networks offers a number of operational advantages that cannot be met by flat networks of sensors. Using hierarchical architectures and in-network processing of information, the communication overhead is minimized by combining data coming from different sources, thus eliminating redundancy, minimizing the number of transmissions and eventually saving valuable network energy.

In this work we focus on securing this aggregation process for all levels of the network hierarchy. Additionally, we explain how commands can be disseminated securely using the pre-established keys. Our protocol is simple and scalable, offering efficiency in terms of computation, communication and storage overhead. Most importantly, however, it is suited for dynamic networks where configuration actions may change the way the network operates, allowing for cluster reorganization and adaptive formation of new clusters.

In this work we study the problem of Intrusion Detection is sensor networks and we propose a lightweight scheme that can be applied to such networks. Its basic characteristic is that nodes monitor their neighborhood and collaborate with their nearest neighbors to bring the network back to its normal operational condition. We emphasize in a distributed approach in which, even though nodes don't have a global view, they can still detect an intrusion and produce an alert. We apply our design principles for the blackhole and selective forwarding attacks by defining appropriate rules that characterize malicious behavior. We also experimentally evaluate our scheme to demonstrate its effectiveness in detecting the afore-mentioned attacks.

In this paper, we describe SuperTrust (Super Peer Trust Handling), a secure framework designed to handle trust relationships in Super peer networks. What distinguishes SuperTrust from other contributions is that trust reports remain encrypted and are never opened during the submission or aggregation processes, thus guaranteeing privacy and anonymity of transactions. As reputations of peers influence their future interactions, we argue that such systems must have properties like fairness and soundness, persistence, eligibility and unreusability of reports, perhaps similar to the properties of current electronic voting systems.

SuperTrust is a decentralized protocol, based on K-redundant Super peer networks, that guarantees the aforementioned properties and is in some sense complementary to the models proposed for building trust among peers. Additionally the framework is very efficient and minimizes the effects of collusion of malicious Super peers/aggregators. We have tested the framework on a large subset of peers and demonstrated via simulations its superior performance with respect to network stress and response time, when compared to the other proposed protocols.

Short paper. For the full version see above…

In this paper we introduce a link layer security platform for wireless sensor networks. At the heart of this platform, lies our key management module facilitating an efficient scalable post-distribution key establishment that allows the platform to provide different security services. We have developed this framework under TinyOs and have tested it with MICA2 motes. To the best of our knowledge this is the first implemented security platform for sensor networks that provides acceptable resistance against node capture attacks and replay attacks. The provision of security services is completely transparent to the user of the framework. Furthermore, being highly scalable and lightweight, this platform is appropriate to be used in a wireless sensor network of hundreds of nodes.

We present .Sense, an end-to-end security framework for sensor network data acquisition, monitoring and command. In order to provide security service inside the sensor network two security protocols are implemented. The first is a key establishment algorithm in which sensor nodes agree on common keys to use for securing communications among them. The second is a scheme in which the base station can issue commands in authenticated manner to the network. We are also using typical security schemes such as SSL to connect the end-users to the system. A user friendly graphical interface has also been implemented to ease the data analysis process for a non sophisticated end-user.

A companion paper to the one below describing our own version of securing Deluge.

Current in-network programming protocols for sensor networks allow an attacker to gain control of the network or disrupt its proper functionality by disseminating malicious code and reprogramming the nodes. We provide a protocol that yields source authentication in the group setting like a public-key signature scheme, only with signature and verification times much closer to those of a MAC. We show how this can be applied to an existing in-network programming scheme, namely Deluge, to authenticate code update broadcasts. Our implementation shows that our scheme imposes only a minimal computation and communication overhead to the existing cost of network programming and uses memory resources efficiently, making it practical for use in sensor networks.

Identification by RFID technology has many benefits for users and companies such as better supply chain and inventory management, improved logistics, better product information and control that may eventually lead to improved customer service. However, consumer reaction clearly shows an increasing concern about the use of this technology in violating user privacy and tracking of individuals by the tags they carry.

In this work we propose a solution to the RFID privacy problem that has the potential to guarantee user privacy without requiring changes to existing infrastructure or reducing business value from the use of RFID technology. We give emphasis to the development of a lightweight protocol that does not incur costly overheads with respect to computation, storage as well as time and effort needed for deployment configuration. For RFID technology to be widely used, security should ship as a “default" and require no significant effort to configure. We demonstrate the security and efficiency properties of our protocol and we offer some interesting time/space tradeoffs that may lead to further improvements.

Nodes in sensor networks do not have enough topology information to make efficient routing decisions. To relay messages through intermediate sensors, geographic routing has been proposed as such a solution. Its greedy nature, however, makes routing inefficient especially in the presence of topology voids or holes. In this paper we present GRAViTy (Geographic Routing Around Voids In any TopologY of sensor networks), a simple greedy forwarding algorithm that combines compass routing along with a mechanism that allows packets to explore the area around voids and bypass them without significant communication overhead. Using extended simulation results we show that our mechanism outperforms the right-hand rule for bypassing voids and that the resulting paths found well approximate the corresponding shortest paths. GRAViTy uses a cross-layered approach to improve routing paths for subsequent packets based on experience gained by former routing decisions. Furthermore, our protocol responds to topology changes, i.e. failure of nodes, and efficiently adjusts routing paths towards the destination.

We study the problem of data propagation in sensor networks, comprised of a large number of very small and low-cost nodes, capable of sensing, communicating and computing. The distributed co-operation of such nodes may lead to the accomplishment of large sensing tasks, having useful applications in practice. We present a new protocol for data propagation towards a control center (sink) that avoids flooding by probabilistically favoring certain (close to optimal) data transmissions. Motivated by certain applications (see [1, 15]) and also as a starting point for a rigorous analysis, we study here lattice-shaped sensor networks. We however show that this lattice shape emerges even in randomly deployed sensor networks of sufficient sensor density. Our work is inspired and builds upon the directed diffusion paradigm of [15].

This protocol is very simple to implement in sensor devices, uses only local information and operates under total absence of co-ordination between sensors. We consider a network model of randomly deployed sensors of sufficient density. As shown by a geometry analysis, the protocol is correct, since it always propagates data to the sink, under ideal network conditions (no failures). Using stochastic processes, we show that the protocol is very energy efficient. Also, when part of the network is inoperative, the protocol manages to propagate data very close to the sink, thus in this sense it is robust. We finally present and discuss large-scale simulation findings validating the analytical results.

The fact that sensor networks are deployed in wide dynamically changing environment and usually left unattended, calls for nomadic, diverse and autonomic behavior. The nature of security threats in such networks as well as the nature of the network itself raise additional security challenges, so new mechanisms and architectures must be designed to protect them. In an autonomic communication context these mechanisms must be based on self-healing, self-configuration and self-optimization in order to enforce high-level security policies. In this work we discuss the research challenges posed by sensor network security as they apply to the autonomic communication setting.

RFID identification is a new technology that will become ubiquitous as RFID tags will be applied to every-day items in order to yield great productivity gains or "smart" applications for users. However, this pervasive use of RFID tags opens up the possibility for various attacks violating user privacy.

In this work we present an RFID authentication protocol that enforces user privacy and protects against tag cloning. We designed our protocol with both tag-to-reader and reader-to-tag authentication in mind; unless both types of authentication are applied, any protocol can be shown to be prone to either cloning or privacy attacks. Our scheme is based on the use of a secret shared between tag and database that is refreshed to avoid tag tracing. However, this is done in such a way so that efficiency of identification is not sacrificed. Additionally, our protocol is very simple and it can be implemented easily with the use of standard cryptographic hash functions.

In analyzing our protocol, we identify several attacks that can be applied to RFID protocols and we demonstrate the security of our scheme. Furthermore, we show how \emph{forward privacy} is guaranteed; messages seen today will still be valid in the future, even after the tag has been compromised.

In this work we present a protocol for key establishment in wireless sensor networks. Our protocol is designed so that it supports security of data with various sensitivity levels. In particular, the protocol allows the establishment of a key that can be used for communication with the base station, pairwise keys that can be used to communicate with immediate neighbors and keys that allow for secure in-network processing. This last form of operation includes both secure aggregation and dissemination processing and is beneficial to sensor networks as it saves energy and increases network lifetime. Our proposed protocol is simple and scalable and exhibits resiliency against node capture and replication as keys are localized. Finally, our protocol allows incremental addition of new nodes and revocation of compromised ones, while at the same time offers efficiency in terms of computation, communication and storage requirements.

IWe consider the problem of securing communication between sensor nodes in large-scale sensor networks. We propose a distributed, deterministic key management protocol designed to satisfy authentication and confidentiality, without the need of a key distribution center. Our scheme is scalable and it is resilient against node capture and replication. Furthermore, it is suited for data fusion and aggregation processing. Finally, we describe a mechanism for evicting compromised nodes as well as adding new ones. A security analysis is discussed and simulation experiments are presented.

In this work we present new security mechanisms that can be used to provide secure in-network processing n wireless sensor networks. In particular, this means that we design the security mechanisms with both aggregation and dissemination in mind. Secure aggregation implies that data is forwarded from the sensors in a secure and authenticated way. Thus an adversary cannot issue false data into the network unless of course a particular sensor node has been compromised. Secure dissemination requires that lower level nodes are able to authenticate commands issued by their parents in the hierarchy. For both directions, protection is also provided against eavesdropping and tampering of data.

Our protocol is simple and scalable and most importantly offers resiliency against node capture and replication as compromised nodes cannot be used to populate and eventually take over the network. Furthermore, it requires minimal key material (just three keys) for the majority of the sensors.

A journal version of the previous paper.

In this work we present a routing algorithm for sensor networks that utilizes smart antennas to propagate information about a sensed event towards a receiving centre. The novelty of our approach lies in the fact that our protocol uses only local information and total absence of coordination between sensors. We provide detailed experimental analysis that demonstrates the feasibility of our approach, the necessity of using smart antennas in sensor networks and the advantages that are presented to communication links due to their use. Our protocol is suited for those cases where unexpected changes to the environment (i.e. a fire, a person entering a restricted area, etc.) must be propagated quickly back to the base station without the use of complicated protocols that may deplete the network from its resources. Our protocol is very easy to implement as nodes do not have to decide whether or not to forward the message; the protocol ensures packet delivery and low energy consumption solely by the use of smart antennas on sensor nodes.

We present a protocol for key establishment in sensor networks. Unlike random key pre-distribution schemes our protocol does not rely on probabilistic key sharing among sensors. During a quick bootstrapping phase, nodes use their pre-deployed key material to form groups or clusters of small size that share a common key. Inter-cluster communication is then achieved by nodes sharing cluster keys. Our scheme is \emph{scalable} and provides \emph{resiliency} against node capture and replication. This is due to the fact that keys are localized; keys that appear in some part of the network are not used again. So, even if a node is compromised and its keys exposed, an adversary can have access only to a very small portion of the network centered around the compromised node. What is more important however, is that our protocol is optimized for \emph{message broadcast}; when a node has to broadcast a message it doesn't have to encrypt it each time with a key targeted for a specific neighbor. This saves energy and makes re-transmissions unnecessary. Furthermore, our scheme is suited for \emph{data fusion} and aggregation processing; if necessary, nodes can "peak" at encrypted data using their cluster key and decide upon forwarding or discarding redundant information.

We present a methodology for proving in Zero Knowledge the validity of selecting a subset of a set belonging to predefined family of sets. We apply this methodology in conjunction with electronic voting to provide extended ballot options.

Our proposed voting scheme supports multiple parties and the selection of a number of candidates from one and only one of these parties. We have implemented this system and provide measures of its computational and communication complexity. We prove that the complexity is linear with respect to the total number of candidates and the number of parties participating in the election.

The Centralized Ad-hoc Network Architecture is an enhancement to the HIPERLAN/2 standard that uses additional bandwidth at 60 GHz to improve performance. From the network security point of view the new architecture introduces several additional issues that have to be addressed in order to achieve node authentication, data integrity, confidentiality and immunity to Data Link layer protocol attacks. In this paper, we identify these issues and propose ways of resolving them building on the existing security mechanisms of the HIPERLAN/2 standard.

One of the most eminent problems in sensor networks is the routing of data to a central destination in a robust and efficient manner. In this work we propose a new scalable protocol for propagating information about a sensed event towards a receiving center. Using only local information and total absence of coordination between sensors our protocol achieves to propagate the sensed data to a receiving center by activating only those nodes that lie very close to the optimal path between the source of the event and the destination, resulting in low activation of the network's sensors. Thus the protocol is very energy efficient. Furthermore, our protocol is robust as it manages to propagate the information even when sensors fail with certain probability.

Optimization algorithms try to locate optimal solutions in a search graph, whose nodes represent all feasible solutions for the given problem. Two nodes in the search graph are neighboring if one solution results from the other by making a small local change. Such a search graph, however, should not be confused with the input graph, which is usually exponentially smaller than the former. The search graph is implicitly defined by the problem at hand and doesn't have to be computed explicitly.

It is well known that the definition of the search graph (or the neighborhood of solutions) plays an important role on the success of the underlying algorithm. In this work we study different neighborhoods for testing satisfiability of Boolean formulas and we give evidence that it is possible to determine in advance the effect a neighborhood has on the quality of the solutions found. We also show how the choice of the right neighborhood gives rise to simple optimization algorithms that work very well in practice.

A journal version of the paper below…

Consider k particles, 1 red and k-1 white, chasing each other on the nodes of a graph G. If the red one catches one of the white, it infects it with its color. The newly red particles are now available to infect more white ones. When is it the case that all white will become red? It turns out that this simple question is an instance of information propagation between random walks and has important applications to mobile computing where a set of mobile hosts acts as an intermediary for the spread of information.

In this paper we model this problem by k concurrent random walks and we develop a set of probabilistic tools that we use to obtain upper bounds on the expected value on the time to infect all the white particles with the red color. We demonstrate that our bounds are tight for special cases (lollipop graphs) but when G is a clique or has nice expansion properties, we prove much smaller bounds for the infection time. We have also evaluated and validated all our results by large scale experiments which we also present and discuss. In particular, the experiments demonstrate that our analytical results for these expander graphs are tight.

We study the problem of data propagation in sensor networks, comprised of a large number of very small and low-cost nodes, capable of sensing, communicating and computing. The distributed co-operation of such nodes may lead to the accomplishment of large sensing tasks, having useful applications in practice. We present a new protocol for data propagation towards a control center that avoids flooding by probabilistically favoring certain data transmissions.

This protocol is very simple, uses only local information and operates under total absence of co-ordination between sensors. As shown by a geometry analysis, the protocol always propagates data to the sink, under ideal network conditions (no failures). Using stochastic processes, we show that the protocol is very energy efficient and present large-scale experimental findings validating the analytical results.

A Journal version of the paper below…

Smart Dust is comprised of a vast number of ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities that co-operate to accomplish a large sensing task. Smart Dust can be very useful in practice i.e. in the local detection of a remote crucial event and the propagation of data reporting its realization to a control center.

In this work, we have implemented and experimentally evaluated four protocols (PFR, LTP and two variations of LTP which we here introduce) for local detection and propagation in smart dust networks, under new, more general and realistic modeling assumptions. We comparatively study, by using extensive experiments, their behavior highlighting their relative advantages and disadvantages. All protocols are very successful. In the setting we considered here, PFR seems to be faster while the LTP based protocols are more energy efficient.

A Journal version of the two papers below…

We present a generator for SAT instances that produces formulas whose hardness can be finely tuned by two parameters p and delta that control the weights of the clauses. Under the right choice of these parameters an easy-hard-easy pattern in the search complexity emerges which is similar to the patterns observed for traditional SAT distributions.

What is remarkable, however, is that the generated distributions seem to lie in the middle ground between decision and optimization problems. Increasing the value of p from 0 to 1 has the effect of changing the shape of the computational cost from an easy-hard-easy pattern typical of decision problems to an easy-hard pattern which is typical of optimization problems. Thus our distributions seem to bridge the gap between decision and optimization versions of SAT.

While it is known how to generate satisfiable instances by reducing certain computational problems to SAT, it is not known how a similar generator can be developed directly for k-SAT.

In this work we improve upon previous results in many ways. First, we give a generator for instances of MAX k-SAT, the version of k-SAT where one wants to maximize the number of satisfied clauses. Second, we provide a useful characterization of the optimal solution. In our model not only we know how the optimal solution looks like but we also prove it is unique. Finally, we show that our generator has certain useful computational properties among which is the ability to control the hardness of the generated instances, the appearance of an easy-hard-easy pattern in the search complexity for good assignments and a new type of phase transition which is related to the uniqueness of the optimal solution.

This work demonstrates the fact that it is possible to experimentally show connections between the combinatorial characteristics of the search space and heuristic performance.

In this work we make a first attempt to explain the hardness of the CLIQUE problem by revealing the combinatorial characteristics of the space of all possible cliques for graphs generated according to the above distribution. In particular, we consider how the search space decomposes into smaller regions of related solutions by imposing a quality threshold to them. If these regions possess a combinatorial property, the so called "local expansion", then these regions can be effectively sampled by using enough particles and thus discover the optimal solution.

Most importantly however, sampling can be used to deduce properties of the search space. These properties can then help optimize heuristic performance and design heuristics that take advantage of this information. Thus the goal of this work is not to compare clique-finding heuristics but to exhibit a way to reveal the combinatorial characteristics of the search space, verify this information experimentally and use it to design good heuristics.

In this work we apply Go with the Winners to the graph bisection problem, a problem of great significance in VLSI design. We show that Go with the Winners approximates the best solution in random graphs of certain densities with planted bisections in polynomial time. We also develop a set of probabilistic tools that may be useful in the analysis of similar problems.

In particular, our results easily extend to hypergraph bisection, whereas it is not clear whether the other known techniques do.

As a result we obtain a randomized algorithm that solves the broadest range of instances for this problem.

Combinatorial algorithms usually combine a greedy approach, which attempts to find better solutions by making small changes, with randomization to prevent the algorithm from getting into a "mental fix".

These algorithms have been widely used and tested. Intuitively the combination of randomness and local optimization would seem to give them some advantage over either alone. However, their efficiency and effectiveness have never been analyzed in a satisfactory manner. In particular, very little is known about the types of problems for which they perform well, the expected trade-off between optimality of the solution found and time spent searching, or how to set the various parameters optimally.

In this work a new algorithm (Go with the Winners) and combinatorial property is introduced so that every problem having this property can be solved efficiently using our algorithm. Thus, this work attempts for the first time to formalize the notion of successful local search in terms of the structural properties of the problem's solutions.