Paolo Palmieri

In this paper we compare two probabilistic data structures for association queries derived from the well-known Bloom filter: the shifting Bloom filter (ShBF), and the spatial Bloom filter (SBF). With respect to the original data structure, both variants add the ability to store multiple subsets in the same filter, using different strategies. We analyse the performance of the two data structures with respect to false positive probability, and the inter-set error probability (the probability for an element in the set of being recognised as belonging to the wrong subset). As part of our analysis, we extended the functionality of the shifting Bloom filter, optimising the filter for any non-trivial number of subsets. We propose a new generalised ShBF definition with applications outside of our specific domain, and present new probability formulas. Results of the comparison show that the ShBF provides better space efficiency, but at a significantly higher computational cost than the SBF.

The evolution of mobile phones into smartphones, and the diffusion of location-based services (LBS), are cornerstones of the digital era, but at the same time introduced a number of challenges to the privacy of individuals. Traditional information (as names, addresses and phone numbers) shared across the Internet with an increased number of services is now frequently coupled with positional data. With such detailed information, service providers are able to infer with alarming precision a number of sensitive information about their users, including religious, sexual and political preferences, as well as details of their social relationships and private life in general. To the extreme, this can lead to manipulation and threats to an individual’s autonomy and freedom. When certain privileged actors with access to this information can learn everything about us, their actions can directly condition our everyday life, making factitious and unnatural. Privacy-preserving and secure location-based services are thus essential in allowing us to enjoy the many benefits of the digital era, while preventing threats to our fundamental rights.

A number of articles were selected for this Special Issue, each of which makes a significant contribution to the debate on new directions in location privacy. Some articles are significantly extended versions of papers presented at the 2019 Location Privacy Workshop (LPW), while others are original contributions. Specifically, we received 15 original research papers that underwent two rounds of reviews, performed by 40 independent experts within the field. Among the received submissions, 8 papers were selected for publication in the Special Issue, resulting in an acceptance rate of approximately 50%.

Artificial intelligence (AI) algorithms achieve outstanding results in many application domains such as computer vision and natural language processing. The performance of AI models is the outcome of complex and costly model architecture design and training processes. Hence, it is paramount for model owners to protect their AI models from piracy – model cloning, illegitimate distribution and use. IP protection mechanisms have been applied to AI models, and in particular to deep neural networks, to verify the model ownership. State-of-the-art AI model ownership protection techniques have been surveyed. The pros and cons of AI model ownership protection have been reported. The majority of previous works are focused on watermarking, while more advanced methods such fingerprinting and attestation are promising but not yet explored in depth. This study has been concluded by discussing possible research directions in the area.

The classical Bloom filter data structure is a crucial component of hundreds of cryptographic protocols. It has been used in privacy preservation and secure computation settings, often in conjunction with the (somewhat) homomorphic properties of ciphers such as Paillier's. In 2014, a new data structure extending and surpassing the capabilities of the classical Bloom filter has been proposed. The new primitive, called spatial Bloom filter (SBF) retains the hash-based membership-query design of the Bloom filter, but applies it to elements from multiple sets. Since its introduction, the SBF has been used in the design of cryptographic protocols for a number of domains, including location privacy and network security. However, due to the complex nature of this probabilistic data structure, its properties had not been fully understood. In this paper we address this gap in knowledge and we fully explore the probabilistic properties of the SBF. In doing so, we define a number of metrics (such as emersion and safeness) useful in determining the parameters needed to achieve certain characteristics in a filter, including the false positive probability and inter-set error rate. This will in turn enable the design of more efficient cryptographic protocols based on the SBF, opening the way to their practical application in a number of security and privacy settings.

With the diffusion of the Internet of Things (IoT), computing is becoming increasingly pervasive, and different heterogeneous networks are integrated into larger systems. However, as different networks managed by different parties and with different security requirements are interconnected, security becomes a primary concern. IoT nodes, in particular, are often deployed “in the open”, where an attacker can gain physical access to the device. As nodes can be deployed in unsurveilled or even hostile settings, it is crucial to avoid escalation from successful attacks on a single node to the whole network, and from there to other connected networks. It is therefore necessary to secure the communication within IoT networks, and in particular, maintain context information private, including the network topology and the location and identity of the nodes.

In this paper, we propose a protocol achieving anonymous routing between different interconnected networks, designed for the Internet of Things and based on the spatial Bloom filter (SBF) data structure. The protocol enables private communication between the nodes through the use of anonymous identifiers, which hide their location and identity within the network. As routing information is encrypted using a homomorphic encryption scheme, and computed only in the encrypted domain, the proposed routing strategy preserves context privacy, preventing adversaries from learning the network structure and topology. This, in turn, significantly reduces their ability to gain valuable network information from a successful attacks on a single node of the network, and reduces the potential for attack escalation.

Location-aware applications are one of the biggest innovations brought by the smartphone era, and are effectively changing our everyday lives. But we are only starting to grasp the privacy risks associated with constant tracking of our whereabouts. In order to continue using location-based services in the future without compromising our privacy and security, we need new, privacy-friendly applications and protocols. In this paper, we propose a new compact data structure based on Bloom filters, designed to store location information. The spatial Bloom filter (SBF), as we call it, is designed with privacy in mind, and we prove it by presenting two private positioning protocols based on the new primitive. The protocols keep the user’s exact position private, but allow the provider of the service to learn when the user is close to specific points of interest, or inside predefined areas. At the same time, the points and areas of interest remain oblivious to the user. The two proposed protocols are aimed at different scenarios: a two-party setting, in which communication happens directly between the user and the service provider, and a three-party setting, in which the service provider outsources to a third party the communication with the user. A detailed evaluation of the efficiency and security of our solution shows that privacy can be achieved with minimal computational and communication overhead. The potential of spatial Bloom filters in terms of generality, security and compactness makes them ready for deployment, and may open the way for privacy preserving location-aware applications.

Cities need to constantly monitor weather to anticipate heavy storm events and reduce the impact of floods. Information describing precipitation and ground conditions at high spatio-temporal resolution is essential for taking timely action and preventing damages. Traditionally, rain gauges and weather radars are used to monitor rain events, but these sources provide low spatial resolutions and are subject to inaccuracy. Therefore, information needs to be complemented with data from other sources: from citizens’ phone calls to the authorities, to relevant on-line media posts, which have the potential of providing timely and valuable information on weather conditions in the city. This information is often scattered through different, static, and not-publicly-available databases. This makes it impossible to use it in an aggregate, standard way, and therefore hampers efficiency of emergency response. In this paper we describe information sources relating to a heavy rain event in Rotterdam on October 12-14, 2013. Rotterdam weather monitoring infrastructure is composed of a number of rain gauges installed at different locations in the city, as well as a weather radar network. This sensing network is currently scarcely integrated and logged data are not easily accessible during an emergency. Therefore, we propose a reliable, efficient and low-cost ICT infrastructure that takes information from all relevant sources, including sensors as well as social and user contributed information and integrates them into a unique, cloud-based interface. The proposed infrastructure will improve efficiency in emergency responses to extreme weather events and, ultimately, guarantee more safety to the urban population.

Modern public transportation companies often record large amounts of information. Privacy can be safeguarded by discarding nominal tickets, or introducing anonymization techniques. But is anonymity at all possible when everything is recorded? In this paper we discuss travel information management in the public transport scenario and we present a revealing case study (relative to the city of Cesena, Italy), showing that even anonymous 10-ride bus tickets may betray a user's privacy expectations. We also propose a number of recommendations for the design and management of public transport information systems, aimed at preserving the users' privacy, while retaining the useful analysis features enabled by the e-ticketing technology.

A smart city is a high-performance urban context, where citizens are more aware of, and more integrated into the city life, thanks to an intelligent city information system. In this paper we design, implement and deploy a smart application that retrieves and conveys to the user relevant information on the user's surroundings. This case study application let us discuss the challenges involved in creating a location-aware mobile service based on live information coming from the city IT infrastructure. The service, that is currently being deployed in the Italian city of Cesena, has been designed with the goal of being a general model for future applications. In particular, we discuss location-aware and mobile development, cloud and cluster based geographical data storage, and spatial data computation. For each of these topics we provide implementation and deployment solutions based on currently available technology. In particular we propose an architecture based on a complex On-Line Transaction Processing (OLTP) infrastructure. Furthermore, this paper represents the first comprehensive, scientific study on the subject.

The increasing demand for smart context-aware services and the increased use of location-based services (LBS) have resulted in the proliferation of mobile devices equipped with geolocation sensors (including GPS, geomagnetic field sensor, accelerometer, proximity sensor, et cetera). As a result, service providers and telecommunications companies can collect massive mobility datasets, often for millions of subscribers. To provide a degree of privacy, dataset owners normally replace personal identifiers such as name, address, and social security number (SSN) with pseudorandom identifiers prior to publication or sale. However, it has been repeatedly shown how sensitive information can be easily extracted or inferred from individuals' mobility data even when personal identifiers are removed. Knowledge of the extent to which location data can be de-anonymized is therefore crucial, in order to design appropriate privacy mechanisms that can prevent re-identification.

In this paper, we propose and implement two novel and highly effective de-anonymization techniques: the Forward and KL algorithms. Our work utilizes a hidden Markov model (which incorporates Spatio-temporal trajectories) in a novel way to generate user mobility profiles for target users. Using real-world datasets containing mobility trajectories from the city of Shanghai, we evaluate the robustness of the proposed attack techniques. From the evaluation score, our attack techniques successfully re-identify up to 85% anonymized users in the GeoLife (Shanghai) datasets. This significantly exceeds current comparable de-anonymization techniques, which have a success rate of 40% to 45%.

This paper outlines an ad-hoc architectural design and a practical implementation of a secure, distributed, fault tolerant and scalable infrastructure comprised of a distributed network of electronics hardware systems that remotely generate cryptographic keys, store them, digitally sign cryptographic transactions based on such keys, and record the transactions on a blockchain. The proposed solution is suitable to service both crypto-finance and non-finance applications, and the physical infrastructure is designed to be implemented using off-the-shelf industrial electronics, which further sustains the already scalable-by-design infrastructure architecture.

The use of traditional encryption techniques in Database Management Systems is limited, as encrypting data within the database can prevent basic functionalities such as ordering and searching. Advanced encryption techniques and trusted hardware, however, can enable standard functionalities to be achieved on encrypted databases, and a number of such schemes have been proposed in the recent literature. In this survey, different approaches towards database security through software/hardware components are explored and compared based on performance and security, and relevant attacks are discussed.

Location-aware applications have witnessed massive worldwide growth in recent years due to the introduction and advancement of smartphones. Most of these applications rely on the Global Positioning System (GPS) which is not available in indoor environments. As a result, Wi-Fi fingerprinting is becoming increasingly popular as an alternative as it allows localizing users in indoor environments, has lower power consumption, and is also more economical as it does not require a dedicated sensor other than a Wi-Fi card. The technique allows a service provider (SP) to construct a Wi-Fi database (called radio map) that can be used as a reference point to localize a user. However, this process does not preserve the user privacy, as the location can only be computed interactively with the SP. The service provider may also reveal sensitive information on the indoor space (e.g. the building map) to the user. Thus, we need an indoor localization protocol that addresses the privacy of both parties. In this paper, we present a privacy-preserving cryptographic protocol for indoor Wi-Fi localization, that prevents the SP from learning the exact location of the user outside of certain pre-defined sensitive areas, while keeping the SP's database secure. Thus, both parties cannot learn anything about each other's input beyond the implicit output revealed.

While numerous digital signature schemes exist in the literature, most real-world system rely on RSA-based signature schemes or on the digital signature algorithm (DSA), including its elliptic curve cryptography variant ECDSA.

In this position paper we review a family of alternative signature schemes, based on hash functions, and we make the case for their application in Internet of Things (IoT) settings. Hash-based signatures provide postquantum security, and only make minimal security assumptions, in general requiring only a secure cryptographic hash function. This makes them extremely flexible, as they can be implemented on top of any hash function that satisfies basic security properties. Hash-based signatures also feature numerous parameters defining aspects such as signing speed and key size, that enable trade-offs in constrained environments. Simplicity of implementation and customization make hash based signatures an attractive candidate for the IoT ecosystem, which is composed of a number of diverse, constrained devices.

Climate change represents a serious threat to the health of our planet and imposed a discussion upon energy waste and production. In this paper we propose a smart grid architecture relying on blockchain technology aimed at discouraging the production and distribution of non-renewable energy as the one derived from fossil fuel. Our model relies on a reverse application of a recently introduced attack to the blockchain based on chain forking. Our system involves both a central authority and a number of distributed peers representing the stakeholders of the energy grid. This system preserves those advantages derived from the blockchain and it also address some limitations such as energy waste for mining operations. In addition, the reverse attack we rely on allows to mitigate the behavior of a classic blockchain, which is intrinsecally self-regulated, and to trigger a sort of ethical action which penalizes non-renewable energy producers. Blacklisted stakeholders will be induced to provide their transaction with higher fees in order to preserve the selling rate.

As computing becomes increasingly pervasive, different heterogeneous networks are connected and integrated. This is especially true in the Internet of Things (IoT) and Wireless Sensor Networks (WSN) settings. However, as different networks managed by different parties and with different security requirements are integrated, security becomes a primary concern. WSN nodes, in particular, are often deployed "in the open", where a potential attacker can gain physical access to the device. As nodes can be deployed in hostile or difficult scenarios, such as military battlefields or disaster recovery settings, it is crucial to avoid escalation from successful attacks on a single node to the whole network, and from there to other connected networks. It is therefore crucial to secure the communication within the WSN, and in particular, maintain context information, such as the network topology and the location and identity of base stations (which collect data gathered by the sensors) private.

In this paper, we propose a protocol achieving anonymous routing between different interconnected IoT or WSN networks, based on the Spatial Bloom Filter (SBF) data structure. The protocol enables communications between the nodes through the use of anonymous identifiers, thus hiding the location and identity of the nodes within the network. The proposed routing strategy preserves context privacy, and prevents adversaries from learning the network structure and topology, as routing information is encrypted using a homomorphic encryption scheme, and computed only in the encrypted domain. Preserving context privacy is crucial in preventing adversaries from gaining valuable network information from a successful attacks on a single node of the network, and reduces the potential for attack escalation.

Access to information is crucial during conflicts and other critical events such as population uprisings. An increasing number of social interactions happen in the cyberspace, while information exchanges at the infrastructural level (monitoring systems, sensor networks, etc.) are now also based on Internet and wireless links, rather than ad-hoc, isolated wired networks. However, the nature of the Internet allows powerful hostile actors to block, censor or redirect communication to and from specific Internet services, through a number of available techniques.

Anonymity networks such as Tor provide a way to circumvent traditional strategies for restricting access to online resources, and make communication harder to trace and identify. Tor, in particular, has been successfully used in past crises to evade censorship and Internet blockades (Egypt, 2011, and Iran, 2012). Anonymity networks can provide essential communication tools during conflicts, allowing information exchanges to be concealed from external observers, anonymized, and made resilient to imposed traffic controls and geographical restrictions. However, the design of networks such as Tor makes them vulnerable to large-scale denial of service attacks, as shown by a recent (March 2015) DDoS targeted at Tor hidden services.

In this paper we analyze the structural weaknesses of Tor with regard to denial of service attacks, and we propose a number of modifications to the structure of the Tor network aimed at improving its resilience to a large coordinated offensive run by a hostile actor in a conflict scenario. In particular, we introduce novel mechanisms that allow relay information to be propagated in a distributed and peer-to-peer manner. This eliminates the need for directory services, and allows the deployment of Tor-like networks in hostile environments, where centralized control is impossible. The proposed improvements concern the network organization, but preserve the underlying onion routing mechanism, which is at the base of Tor’s anonymity.

The pervasive presence of interconnected objects enables new communication paradigms where devices can easily reach each other while interacting within their environment. The so-called Internet of Things (IoT) represents the integration of several computing and communications systems aiming at facilitating the interaction between these devices. Arduino is one of the most popular platforms used to prototype new IoT devices due to its open, flexible and easy-to-use architecture. Ardunio Yun is a dual board microcontroller that supports a Linux distribution and it is currently one of the most versatile and powerful Arduino systems. This feature positions Arduino Yun as a popular platform for developers, but it also introduces unique infection vectors from the security viewpoint. In this work, we present a security analysis of Arduino Yun. We show that Arduino Yun is vulnerable to a number of attacks and we implement a proof of concept capable of exploiting some of them.

Wireless Sensor Networks (WSN) are often deployed in hostile or difficult scenarios, such as military battlefields and disaster recovery, where it is crucial for the network to be highly fault tolerant, scalable and decentralized. For this reason, peer-to-peer primitives such as Distributed Hash Table (DHT), which can greatly enhance the scalability and resilience of a network, are increasingly being introduced in the design of WSN's. Securing the communication within the WSN is also imperative in hostile settings. In particular, context information, such as the network topology and the location and identity of base stations (which collect data gathered by the sensors and are a central point of failure) can be protected using traffic encryption and anonymous routing.

In this paper, we propose a protocol achieving a modified version of onion routing over wireless sensor networks based on the DHT paradigm. The protocol prevents adversaries from learning the network topology using traffic analysis, and therefore preserves the context privacy of the network. Furthermore, the proposed scheme is designed to minimize the computational burden and power usage of the nodes, through a novel partitioning scheme and route selection algorithm.

When choosing the three relays that compose a circuit, Tor selects the first hop among a restricted number of relays called entry guards, pre-selected by the user himself. The reduced number of entry guards, that until recently was fixed to three, helps in mitigating the effects of several traffic analysis attacks. However, recent literature indicates that the number should be further reduced, and the time during which the user keeps the relays as guards increased. Therefore, developers of Tor recently proposed selecting only one entry guard, which is to be used by the user for all circuits and for a prolonged period of time (nine months). While this design choice was made to increase the security of the protocol, it also opens an unprecedented opportunity for a market mechanism where relays get paid for traffic by the users.

In this paper, we propose to use the entry guard as the point-of-sale: users subscribe to their entry guard of choice, and deposit an amount that will be used for paying for the circuits. From the entry guard, income is then distributed to the other relays included in circuits through an inter-relay accounting system. While the user may pay the entry guard using BitCoins, or any other anonymous payment system, the relays exchange I Owe You (IOU) certificates during communication, and settle their balances only at synchronized, later points in time. This novel deferred payment approach overcomes the weaknesses of the previously proposed Tor payment mechanisms: we separate the user's payment from the inter-relay payments, and we effectively unlink both from the chosen path, thus preserving the secrecy of the circuit.

The wide availability of inexpensive positioning systems made it possible to embed them into smartphones and other personal devices. This marked the beginning of location-aware applications, where users request personalized services based on their geographic position. The location of a user is, however, highly sensitive information: the user's privacy can be preserved if only the minimum amount of information needed to provide the service is disclosed at any time. While some applications, such as navigation systems, are based on the users' movements and therefore require constant tracking, others only require knowledge of the user's position in relation to a set of points or areas of interest. In this paper we focus on the latter kind of services, where location information is essentially used to determine membership in one or more geographic sets. We address this problem using Bloom Filters (BF), a compact data structure for representing sets. In particular, we present an extension of the original Bloom filter idea: the Spatial Bloom Filter (SBF). SBF's are designed to manage spatial and geographical information in a space efficient way, and are well-suited for enabling privacy in location-aware applications. We show this by providing two multi-party protocols for privacy-preserving computation of location information, based on the known homomorphic properties of public key encryption schemes. The protocols keep the user's exact position private, but allow the provider of the service to learn when the user is close to specific points of interest, or inside predefined areas. At the same time, the points and areas of interest remain oblivious to the user.

Onion routing is a technique for anonymous and privacy preserving communication at the base of popular Internet anonymity tools such as Tor. In onion routing, traffic is relayed by a number of intermediary nodes (called relays) before it reaches the intended destination. To guarantee privacy and prevent tampering, each packet is encrypted multiple times in a layered manner, using the public keys of the relays. Therefore, this mechanism makes two important assumptions: first, that the relays are able to communicate with each other; second, that the user knows the list of available relays and their respective public keys. Tor implements therefore a distributed directory listing the relays and their keys. When a user is not able to communicate with relays directly, he has to use special bridge servers to connect to the onion network.

This construction, however, does not work in a fully peer to peer setting, where each peer only knows a limited number of other peers and may not be able to communicate with some of them due, for instance, to NAT or firewalls. In this paper we propose a key management scheme for onion routing that overcomes these problems. The proposed solution does not need a directory system and does not imply knowledge of all active relays, while it guarantees the secure distribution of public keys. We also present an alternative strategy for building circuit of relays based on bloom filters. The proposed construction overcomes some of the structural inefficiencies of the Tor design, and opens the way for implementing onion routing over a true peer to peer overlay network.

Secure multi-party computation (MPC) deals with the problem of shared computation between parties that do not trust each other: they are interested in performing a joint task, but they also want to keep their respective inputs private. In a world where an ever-increasing amount of computation is outsourced, for example to the cloud, MPC is a subject of crucial importance. However, unconditionally secure MPC protocols have never found practical application: the lack of realistic noisy channel models, that are required to achieve security against computationally unbounded adversaries, prevents implementation over real-world, standard communication protocols.

In this paper we show for the first time that the inherent noise of wireless communication can be used to build multi-party protocols that are secure in the information-theoretic setting. In order to do so, we propose a new noisy channel, the Delaying-Erasing Channel (DEC), that models network communication in both wired and wireless contexts. This channel integrates erasures and delays as sources of noise, and models reordered, lost and corrupt packets. We provide a protocol that uses the properties of the DEC to achieve Oblivious Transfer (OT), a fundamental primitive in cryptography that implies any secure computation. In order to show that the DEC reflects the behavior of wireless communication, we run an experiment over a 802.11n wireless link, and gather extensive experimental evidence supporting our claim. We also analyze the collected data in order to estimate the level of security that such a network can provide in our model. We show the flexibility of our construction by choosing for our implementation of OT a standard communication protocol, the Real-time Transport Protocol (RTP). Since the RTP is used in a number of multimedia streaming and teleconference applications, we can imagine a wide variety of practical uses and application settings for our construction.

Searching a Peer-to-Peer (P2P) network without using a central index has been widely investigated but proved to be very difficult. Various strategies have been proposed, however no practical solution to date also addresses privacy concerns.

By clustering peers which have similar interests, a semantic overlay provides a method for achieving scalable search. Traditionally, in order to find similar peers, a peer is required to fully expose its preferences for items or content, therefore disclosing this private information. However, in a hostile environment, such as a P2P system, a peer can not know the true identity or intentions of fellow peers.

In this paper, we propose two protocols for building a semantic overlay in a privacy-preserving manner by modifying existing solutions to the Private Set Intersection (PSI) problem. Peers in our overlay compute their similarity to other peers in the encrypted domain, allowing them to find similar peers. Using homomorphic encryption, peers can carrying out computations on encrypted values, without needing to decrypt them first.

We propose two protocols, one based on the inner product of vectors, the other on multivariate polynomial evaluation, which are able to compute a similarity value between two peers. Both protocols are implemented on top of an existing P2P platform and are designed for actual deployment. Using a supercomputer and a dataset extracted from a real world instance of a semantic overlay, we emulate our protocols in a network consisting of a thousand peers. Finally, we show the actual computational and bandwidth usage of the protocols as recorded during those experiments.

If we assume that adversaries have unlimited computational capabilities, secure computation between mutually distrusting players can not be achieved using an error-free communication medium. However, secure multi-party computation becomes possible when a noisy channel is available to the parties. For instance, the Binary Symmetric Channel (BSC) has been used to implement Oblivious Transfer (OT), a fundamental primitive in secure multi-party computation. Current research is aimed at designing protocols based on real-world noise sources, in order to make the actual use of information-theoretically secure computation a more realistic prospect for the future.

In this paper, we introduce a modified version of the recently proposed Binary Discrete-time Delaying Channel (BDDC), a noisy channel based on communication delays. We call our variant Reordering Channel (RC), and we show that it successfully models packet reordering, the common behavior of packet switching networks that results in the reordering of the packets in a stream during their transit over the network. We also show that the protocol implementing oblivious transfer on the BDDC can be adapted to the new channel by using a different sending strategy, and we provide a functioning implementation of this modified protocol. Finally, we present strong experimental evidence that reordering occurrences between two remote Internet hosts are enough for our construction to achieve statistical security against honest-but-curious adversaries.

In secure two-party computation, two mutually distrusting parties are interested in jointly computing a function, while preserving the privacy of their respective inputs. However, when communicating over a clear channel, security against computationally unbounded adversaries is impossible. Thus is the importance of noisy channels, over which we can build Oblivious Transfer (OT), a fundamental primitive in cryptography and the basic building block for any secure multi-party computation. The noisy channels commonly used in current constructions are mostly derived from the Binary Symmetric Channel (BSC), which is modified to extend the capabilities of an attacker. Still, these constructions are based on very strong assumptions, in particular on the error probability, which makes them hard to implement.

In this paper, we provide a protocol achieving oblivious transfer over a Z-channel, a natural channel model in various contexts, ranging from optical to covert communication. The protocol proves to be particularly efficient for a large range of error probabilities p (e.g., for 0.17 ≤ p ≤ 0.29 when a security parameter ε = 10− 9 is chosen), where it requires a limited amount of data to be sent through the channel. Our construction also proves to offer security against unfair adversaries, who are able to select the channel probability within a fixed range. We provide coding schemes that can further increase the efficiency of the protocol for probabilities distant from the range mentioned above, and also allow the use of a Z-channel with an error probability greater than 0.5. The flexibility and the efficiency of the construction make an actual implementation of oblivious transfer a more realistic prospect.

In the information-theoretic setting, where adversaries have unlimited computational power, the fundamental cryptographic primitive Oblivious Transfer (OT) cannot be securely achieved if the parties are communicating over a clear channel. To preserve secrecy and security, the players have to rely on noise in the communication. Noisy channels are therefore a useful tool to model noise behavior and build protocols implementing OT. This paper explores a source of errors that is inherently present in practically any transmission medium, but has been scarcely studied in this context: delays in the communication.

In order to have a model for the delays that is both general and comparable to the channels usually used for OT – such as the Binary Symmetric Channel (BSC) – we introduce a new noisy channel, the Binary Discrete-time Delaying Channel (BDDC). We show that such a channel realistically reproduces real-life communication scenarios where delays are hard to predict and we propose a protocol for achieving oblivious transfer over the BDDC. We analyze the security of our construction in the semi-honest setting, showing that our realization of OT substantially decreases the protocol sensitivity to the user’s knowledge of the channel compared to solutions relying on other channel properties, and is very efficient for wide ranges of delay probabilities. The flexibility and generality of the model opens the way for future implementation in media where delays are a fundamental characteristic.

In a scenario with two mutually distrusting players, Oblivious Transfer, a rather fundamental primitive in the design of cryptographic protocols, cannot be implemented with unconditional security over a standard, error-free communication medium. Various results, however, show that we can make use of noisy channels, where we can exploit errors in the communication to our advantage in order to implement OT in a secure fashion. First tested against standard primitives like the Binary Symmetric Channel, it has later been demonstrated how to build OT over a fair number of new noisy channels models proposed over the years. However, these models are usually derived from the BSC itself, and different sources of noise have been scarcely explored.

In this paper we propose a new noisy channel primitive, called Binary Discrete-time Delaying Channel. The aim is to model a realistic scenario in communication systems, while basing it on as few assumptions as possible. In particular, we make use of a rarely used error source, the delays in communication. We also provide a way to securely build OT over this new model in the semi-honest scenario, and then we add some robustness to the protocol, mitigating the influence of a cheating transmitter. The flexibility and generality of this new model may open the way for future implementation, especially in media where delays are a fundamental characteristic, as in the case of wireless communications.

Historically, cryptography was created and used to deliver messages between people in such a way that only the intended receiver would be able to read them. The two persons communicating trusted each other, but not the rest of the world - for instance, not the message bearer. But what happens if we assume instead that even the receiver of a message may not be trusted by the sender, while both still have an interest in communicating? This problem is addressed by secure multi-party computation, that studies communication and shared computation between mutually distrusting parties. In a world where most of the communication happens over the Internet, and where an ever-increasing amount of computation is outsourced, for example to the cloud, multiparty computation is a subject of crucial importance. However, unconditionally secure multi-party protocols have never found practical application: the lack of realistic noisy channel models, that are required to achieve security against computationally unbounded adversaries, prevents implementation over real-world, standard communication protocols.

In this thesis, we study the properties and characteristics of noisy channels, and we introduce new models based on real-world error sources that have never been studied in this context, such as delays. On the contrary, previous works mostly focused on theoretical noisy channels that have little in common with the reality of network communication. We show that the models we propose are suitable for multi-party computation by building on each of them a protocol for oblivious transfer, a fundamental cryptographic primitive that implies any secure computation. Thanks to the realism of our noisy channels, we are able to provide the first working implementation of unconditionally secure oblivious transfer over both wired and wireless networks and different Internet protocols, which we test thoroughly in an extensive set of experiments. Our constructions are not only more realistic, but also more flexible, as they allow larger ranges of error probabilities. This will eventually open the way for the widespread use of unconditionally secure multi-party computation.