Paolo Palmieri, Ph.D.


Publications

You can find here my full list of publications and research papers, last updated in May, 2018. You may also have a look at my DBLP, Scopus and Google Scholar profiles, although these indexes may miss some references. My Erdős number is 4Paul Erdős   »
Pavol Hell   »
Jean-Jacques Quisquater   »
Olivier Pereira   »
Me   :)
.


Journal articles


[J6] Luca Calderoni, Paolo Palmieri, Dario Maio: Probabilistic Properties of the Spatial Bloom Filters and Their Relevance to Cryptographic Protocols. IEEE Transactions on Information Forensics and Security, vol. 13 (7), pp. 1710–1721, July 2018. ISSN 1556-6013

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.


[J5] Paolo Palmieri, Luca Calderoni, Dario Maio: An anonymous inter-network routing protocol for the Internet of Things. Journal of Cyber Security and Mobility, vol. 6 (2), pp. 127–146, April 2017. ISSN 2245-1439

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.


[J4] Luca Calderoni, Paolo Palmieri, Dario Maio: Location privacy without mutual trust: The spatial Bloom filter. Computer Communications, vol. 68, pp. 4–16, September 2015. ISSN 0140-3664

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.


[J3] Santiago Gaitan, Luca Calderoni, Paolo Palmieri, Marie-claire ten Veldhuis, Dario Maio, M. Birna van Riemsdijk: From Sensing to Action: Quick and Reliable Access to Information in Cities Vulnerable to Heavy Rain. IEEE Sensors Journal, vol. 14 (12), pp. 4175–4184, December 2014. ISSN 1530-437X

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.


[J2] Gildas Avoine, Luca Calderoni, Jonathan Delvaux, Dario Maio, Paolo Palmieri: Passengers information in public transport and privacy: Can anonymous tickets prevent tracking? International Journal of Information Management, vol. 34 (5), pp. 682–688, October 2014. ISSN 0268-4012

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.


[J1] Luca Calderoni, Dario Maio, Paolo Palmieri: Location-aware Mobile Services for a Smart City: Design, Implementation and Deployment. Journal of Theoretical and Applied Electronic Commerce Research, vol. 7 (3), pp. 74–87, December 2012. ISSN 0718-1876

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.


Conference papers (peer-reviewed)


[C15] Paolo Palmieri: Hash-based signatures for the Internet of Things. In: ACM International Conference on Computing Frontiers (CF 2018) - Malicious Software and Hardware in Internet of Things, Proceedings. ACM, 2018.

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.


[C14] Antonio Magnani, Luca Calderoni, Paolo Palmieri: Feather forking as a positive force: incentivising green energy production in a blockchain-based smart grid. In: 16th ACM International Conference on Mobile Systems, Applications, and Services (MobiSys 2018) - Cryptocurrencies and Blockchains for Distributed Systems, Proceedings. ACM, 2018.

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.


[C13] Paolo Palmieri, Luca Calderoni, Dario Maio: Private inter-network routing for Wireless Sensor Networks and the Internet of Things. In: ACM International Conference on Computing Frontiers (CF 2017) - Malicious Software and Hardware in Internet of Things, Proceedings. ACM, pp. 396–401, 2017. ISBN: 978-1-4503-4487-6

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.


[C12] Paolo Palmieri: Anonymity networks and access to information during conflicts: towards a distributed network organization. In: Cyber Conflict 2016, 8th International Conference (CyCon 2016). NATO Cooperative Cyber Defence Centre of Excellence Publications, pp. 263–275, 2016. ISBN 978-9949-9544-8-3

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.


[C11] Carlos Alberca Pozo, Sergio Pastrana Portillo, Guillermo Suarez-Tangil, Paolo Palmieri: Security Analysis and Exploitation of Arduino devices in the Internet of Things. In: ACM International Conference on Computing Frontiers (CF 2016) - Malicious Software and Hardware in Internet of Things, Proceedings. ACM, pp. 437–442, 2016. ISBN: 978-1-4503-4128-8

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.


[C10] Paolo Palmieri: Preserving Context Privacy in Distributed Hash Table Wireless Sensor Networks. In: Information and Communications Security - 17th International Conference (ICICS 2015), Revised Selected Papers. Lecture Notes in Computer Science, vol. 9543, pp. 436–444, Springer, 2016. ISBN 978-3-319-29813-9

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.


[C9] Paolo Palmieri, Johan Pouwelse: Paying the Guard: an Entry-Guard-based Payment System for Tor. In: Financial Cryptography and Data Security - 19th International Conference (FC 2015), Revised Selected Papers. Lecture Notes in Computer Science, vol. 8975, pp. 437–444, Springer, 2015. ISBN 978-3-662-47853-0

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.


[C8] Paolo Palmieri, Luca Calderoni, Dario Maio: Spatial Bloom Filters: Enabling Privacy in Location-aware Applications. In: Information Security and Cryptology – 10th International Conference (Inscrypt 2014), Revised Selected Papers. Lecture Notes in Computer Science, vol. 8957, pp. 16–36, Springer, 2015. ISBN 978-3-319-16744-2

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.


[C7] Paolo Palmieri, Johan Pouwelse: Key Management for Onion Routing in a True Peer to Peer Setting. In: Advances in Information and Computer Security - 9th International Workshop on Security (IWSEC 2014), Proceedings. Lecture Notes in Computer Science, vol. 8639, pp. 62–71, Springer, 2014. ISBN 978-3-319-09842-5

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.


[C6] Paolo Palmieri, Olivier Pereira: Unconditionally Secure Oblivious Transfer from Real Network Behavior. In: Advances in Information and Computer Security - 8th International Workshop on Security (IWSEC 2013), Proceedings. Lecture Notes in Computer Science, vol. 8231, pp. 168–182, Springer, 2013. ISBN 978-3-642-41382-7

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.


[C5] Niels Zeilemaker, Zekeriya Erkin, Paolo Palmieri, Johan A. Pouwelse: Building a privacy-preserving semantic overlay for Peer-to-Peer networks. In: 2013 IEEE International Workshop on Information Forensics and Security (WIFS 2013), pp. 79–84, IEEE, 2013. ISBN 978-1-4673-5593-3

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.


[C4] Paolo Palmieri, Olivier Pereira: Implementing Information-Theoretically Secure Oblivious Transfer from Packet Reordering. In: Information Security and Cryptology - 14th International Conference (ICISC 2011), Revised Selected Papers. Lecture Notes in Computer Science, vol. 7259, pp. 332–345, Springer, 2012. ISBN 978-3-642-31911-2

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.


[C3] Paolo Palmieri, Olivier Pereira: Secure Two-Party Computation over a Z-Channel. In: Provable Security - 5th International Conference (ProvSec 2011), Proceedings. Lecture Notes in Computer Science, vol. 6980, pp. 3–15, Springer, 2011. ISBN 978-3-642-24315-8

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.


[C2] Paolo Palmieri, Olivier Pereira: Building Oblivious Transfer on Channel Delays. In: Information Security and Cryptology - 6th International Conference (Inscrypt 2010), Revised Selected Papers. Lecture Notes in Computer Science, vol. 6584, pp. 125–138, Springer, 2011. ISBN 978-3-642-21517-9

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.


[C1] Paolo Palmieri, Olivier Pereira: Building Oblivious Transfer from communication delays (Extended Abstract). In: 30th Symposium on Information Theory in the Benelux (WIC09), Proceedings. Werkgemeenschap voor Informatie- en Communicatietheorie, pp. 201–208, 2009. ISBN 978-90-386-1852-4

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.


Ph.D. dissertation


[D1] Paolo Palmieri: Unconditional Secure Cooperation on Real-World Networks: the Case of Oblivious Transfer. Doctoral dissertation. Université catholique de Louvain, 122 pages, Belgium, 2013.

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.


Members of the jury:
Prof. Olivier PEREIRA Université catholique de Louvain Supervisor
Prof. Luc VANDENDORPE Université catholique de Louvain Chair
Prof. Olivier MARKOWITCH Université libre de Bruxelles
Prof. Claude OESTGES Université catholique de Louvain
Prof. Jean-Jacques QUISQUATER Université catholique de Louvain
Prof. Abdellatif ZAIDI Université Paris-Est Marne-la-Vallée