key: cord-0668810-3k0l7k4x authors: Tedeschi, Pietro; Bakiras, Spiridon; Pietro, Roberto Di title: SpreadMeNot: A Provably Secure and Privacy-Preserving Contact Tracing Protocol date: 2020-11-14 journal: nan DOI: nan sha: dbbd8ee086256d0461d7b5ecedbcdce1ddce98f0 doc_id: 668810 cord_uid: 3k0l7k4x Contact tracing via mobile applications is gaining significant traction in the battle against Covid-19. A plethora of contact tracing apps have been developed and deployed in several countries around the world. However, people are rightfully concerned about the security and privacy risks of such applications. To this end, the contribution of this work is twofold. First, we present an in-depth analysis of the security and privacy characteristics of the most prominent contact tracing protocols, under both passive and active adversaries. The results of our study indicate that all protocols are vulnerable to a variety of attacks, mainly due to the deterministic nature of the underlying cryptographic protocols. Our second contribution is the design of SpreadMeNot, a novel contact tracing protocol that can defend against most passive and active attacks, thus providing strong (provable) security and privacy guarantees that are necessary for such a sensitive application. Moreover, we experimentally demonstrate that SpreadMeNot---while being built on asymmetric crypto primitives---sports little overhead. Our detailed analysis, both formal and experimental, shows that SpreadMeNot satisfies security, privacy, and performance requirements, hence being an ideal candidate for building a contact tracing solution that can be adopted by the majority of the general public, as well as to serve as an open source reference for further developments in the field. The sudden outbreak of the COVID-19 coronavirus has fundamentally changed our society. The high infection rate of the virus facilitated its rapid spread around the world that resulted in the most deadly pandemic in recent history [1] . Unfortunately, according to health experts, COVID-19 will almost certainly not be the last pandemic, so we, as a society, should be prepared to tackle future outbreaks more effectively and efficiently. To this end, contact tracing-followed by aggressive testing-has proven to be a very valuable tool in the battle against COVID-19 [2] , [3] . In particular, contact tracing involves the early identification and notification of people that have been exposed to the virus by being in close proximity, for a given time in the near past, to a user that has tested positive. Traditionally, contact tracing has been performed exclusively by public health professionals, in the form of interviews. However, relying solely on patient interviews is not a very effective approach. First, it requires an enormous workforce to trace potential infection chains when there are thousands of new cases discovered daily. Second, face-to-face or even phone interviews regarding social contacts may feel like an invasion of privacy to many people, who might refrain from sharing all the relevant information. Finally, close contact with complete strangers is a regular theme in our daily lives (public transit, supermarkets, shopping malls, etc.), and such infection chains cannot be tracked with manual contact tracing methods [4] . Alternatively, digital contact tracing is a technology that is gaining significant traction among governments and public health officials. In a nutshell, digital contact tracing is generally achieved via mobile applications that leverage either the Bluetooth Low Energy (BLE) protocol or the Global Navigation Satellite System (GNSS) technologies to keep track of other mobile devices in their vicinity [5] . More specifically, every device periodically broadcasts a random beacon that is intercepted and recorded by the nearby devices. If a beacon is detected to be closer than a certain threshold (e.g., 2 meters) for a significant amount of time, the event is recorded permanently in the contact list maintained by that device. When a user tests positive for COVID-19, the public health authorities are given access to their device in order to release their random beacons (and/or contact list) to a centralized database. Subsequently, other devices will download the released information and identify whether they have been in contact with the infected individual. There have been a plethora of contact tracing apps implemented and used around the world. Singapore's TraceTogether app [6] was one of the first wide-scale deployments, while many other big players have entered the arena, including the European Union [7] , [8] and Apple/Google [9] . Nevertheless, people nowadays are very concerned about their privacy and may be unwilling to install and run a surveillancetype application [10] , [11] . Further, the energy tool of such applications and the perceived battery life shortening could limit the adoption of contact tracing by the general public. A solution that on one hand offers provable security and privacy guarantees, while on the other hand introduces only a little overhead, is in dire need. Contribution. To this end, the first contribution of this work is an in-depth analysis of the security and privacy characteristics of the most prominent contact tracing protocols. We look at the fundamental mechanisms incorporated in these methods, including the type of information that is collected, the location where that information is stored (centralized vs. decentralized vs. hybrid), and the cryptographic primitives involved in the generation of the random beacons. We also consider a wide range of adversarial behavior, ranging from simple passive (eavesdropping) attacks to more elaborate, active, ones such as replay and relay attacks. Our results indicate that, at the very least, all existing approaches are vulnerable to simple eavesdropping attacks that can de-anonymize an individual once they have tested positive for the coronavirus. Indeed, beacons are generated in a deterministic manner (e.g., using hashing) and are always transmitted in clear text. As such, an adversary can easily intercept them with off-the-shelf antennas, and tag them with time-stamped location information. Therefore, when users disclose their beacons (or contact lists), the adversary can track their entire location history over the past two weeks. This led us to our second contribution, which is the design of SpreadMeNot, a novel contact tracing protocol with very strong, provable privacy guarantees that protects the users' proximity data against sophisticated attacks. The main novelty of our protocol is the use of beacons that are generated with public-key cryptographic primitives. The probabilistic nature of public-key cryptography allows for the randomization of all previously transmitted beacons, so that they can be safely published without disclosing any identifiable information to an adversary. As such, SpreadMeNot is resilient to eavesdropping attacks. Furthermore, to strengthen our protocol against more powerful, active adversaries, we introduce a simple extension (based on digital signatures) that prevents an adversary from replaying previously transmitted beacons. Finally, we demonstrate with experiments 1 run on mobile phones that SpreadMeNot's overhead in terms of computations and energy consumption is very reasonable for an average smartphone device. Roadmap. The remainder of the paper is organized as follows. Section II introduces the technical background related to contact tracing technologies and public-key cryptography. Section III illustrates the generic contact tracing model and describes the adversarial behavior that we assume in this paper. Section IV presents our in-depth study on the security and privacy of the current state-of-the-art solutions. Section V introduces the SpreadMeNot protocol and Section VI investigates its performance in terms of computations and energy requirements. Section VII highlights some important optimizations that mitigate the cost of public-key cryptography, and Section VIII concludes our paper. II. TECHNICAL BACKGROUND In this section, we discuss briefly the wireless technologies that are employed by existing contact tracing protocols, including Bluetooth and satellite communications. We also introduce Elliptic Curve Cryptography (ECC), which is the underlying cryptographic primitive of SpreadMeNot. The wireless Bluetooth technology was conceived in the early 1990s at Ericsson and was intended to replace the RS- 1 The source code of SpreadMeNot will be released as open source when the paper accepted 232 data cable. Specifically, it allows fixed and mobile devices to exchange data over short distances using the Ultra High Frequency (UHF) spectrum. Bluetooth was first standardized as the IEEE 802.15.1 protocol, with the current standard maintained by the Bluetooth Special Interest Group (SIG). Nowadays, there is a wide range of applications that adopt Bluetooth technology to manage wireless devices such as headphones, mice, keyboards, and printers. More importantly, Bluetooth is the underlying technology for numerous novel applications, such as indoor localization, Internet of Things (IoT), contact tracing, gaming, smart-locking, networking, and data streaming, to name a few. For example, by placing Bluetooth transceivers around large shopping areas, we can enhance user experience via Bluetooth-based mobile advertising applications. Note that, under the current standard, a master Bluetooth device can establish a one-to-one communication with a maximum of 7 devices in an ad-hoc network. From the physical layer perspective, Bluetooth communications adopt the UHF frequency band and, in particular, the frequencies ranging from 2.402 GHz to 2.480 GHz. The modulation scheme is either Gaussian Frequency Shift Keying (GFSK) with a bit rate of 1 Mbits/sec, or Differential Phase Shift Keying (DPSK) with a maximum bit rate of 3 Mbits/sec. Furthermore, Bluetooth employs Frequency-Hopping Spread Spectrum (FHSS) and divides the spectrum into 79 channels, each with a bandwidth of 1 MHz. BLE accommodates 40 channels, each with a bandwidth of 2 MHz. The transmission range depends on the device class and its maximum transmission power, as shown in the Table I . Bluetooth v4.2 frames have an overall size of 2120 bits [12] . The message starts with the first 8 bits reserved to a preamble that is used to identify an upcoming Bluetooth message and allow the receiver to synchronize with the symbols emitted by the transmitter. An Access Address of 32 bits denotes the correlation code tuned to the physical channel. The Protocol Data Unit (PDU) consists of 2056 bits, and is reserved for Data TX and Advertising. Finally, the last 24 bits are devoted to an error-detection code (CRC) and store the checksum of all bytes in the PDU. The bottom part of Fig. 1 shows the contents of the PDU. It includes the Bluetooth packet Header (16 bits), the link-layer Payload (up to 2008 bits of data), and 32 bits of a Message Integrity Check (MIC) [13] . Note that Bluetooth RF operations take place according to a slot-based Time Division Multiple Access (TDMA) schedule. Specifically, assuming a data rate of 1 Mbits/sec and a packet size of 265 bytes, the transfer duration is 2.12 ms. Some proximity tracing solutions adopt GNSS technologies as a key element to approximate user location. Any smart device equipped with a GNSS module can receive RF signals originating from Medium Earth Orbit (MEO) satellites, located 19, 000 to 23, 000 km above Earth. Common GNSS devices are only able to receive in the Upper L-Band, i.e., in the 1.5 GHz range, with an accuracy of about 3 − 5 meters for the positioning [14] . Each satellite is synchronized with atomic clocks and sends a navigation signal that contains information about the delivery time and the deviation from its expected trajectory. Several GNSS technologies are available on the market, with the most popular one being Global Positioning System (GPS) that is operated by the United States Department of Defense. Other systems include the Russian GLONASS, the European GALILEO, and the Chinese BEIDOU. Nevertheless, GNSS technologies have some well-known weaknesses: they do not work in indoor environments, are extremely sensitive to jamming attacks, and are vulnerable to spoofing attacks if the RF signal is not encrypted [15] . GNSS technologies are widely adopted for several applications that span from location-based services to the monitoring and tracking of objects in remote areas. However, in the proximity tracing scenario, and compared to Bluetooth-based solutions, GNSS has the following drawbacks: (i) higher energy consumption due to the position sensors; (ii) lower accuracy in terms of proximity localization; and, (iii) an inability to work in close spaces, like buildings. Elliptic Curve Cryptography is a powerful approach to public-key cryptography that is based on the algebraic structure of elliptic curves over finite fields. ECC is considered as a better alternative to traditional schemes over finite fields because, for the same level of security, it offers much smaller keys and ciphertexts [16] . As such, ECC is more suitable for resource-constrained devices, such as smartphones or IoT devices. An elliptic curve defines a set of coordinates (x, y) that satisfy Eq. 1 below. In addition, a special point O, namely point at infinity, represents the point at the ends of all lines parallel to the y-axis. The elliptic curve domain parameters over the finite field F p are a sextuple E = (p, a, b, G, q, h), where: (i) p > 3 is an integer specifying the finite field F p ; (ii) a, b are the elements that define the elliptic curve; (iii) G ∈ E(F p ) is the generator point; (iv) prime q is the order of the subgroup generated by G; and, (v) integer h is the cofactor of the subgroup. In ECC, the private key is generated by choosing a uniformly random number x ∈ Z * q , i.e., a number in the interval [1, q) . The corresponding public key is then computed as P = xG. The security of ECC is based on the intractability of finding the discrete logarithm of a random elliptic curve point P with respect to a publicly known base point G. This is known as the Elliptic Curve Discrete Logarithm Problem (ECDLP). The bit-length n of the prime order q determines the security level of an ECC instantiation. We formally define the assumption behind the security of ECC schemes below. A function f is negligible if for every polynomial p(·) there exists N such that, for all integers n > N , it holds that f (n) < 1 p(n) . We denote a negligible function of n as negl(n). The ECDLP assumption is as follows: given P, G ∈ E(F p ) where P = xG, x ∈ Z q , and q ∈ {0, 1} n is the order of the elements P and G, a polynomial-time algorithm can output x with probability negl(n). In this section, we introduce the generic contact tracing environment assumed in our work (Section III-A) and present the details of the underlying adversarial model (Section III-B). We assume a typical BLE-based contact tracing environment, as illustrated in Fig. 2 . Users that have subscribed to the contact tracing system are constantly broadcasting ephemeral identifiers (or beacons 2 ) that are randomly generated according to SpreadMeNot's protocol specifications. Additionally, all users in proximity to a broadcasted beacon will temporarily store it into their local memory. A newly created beacon is valid for a fixed time window, in order to allow the surrounding devices to detect possible contagion events. In most existing applications, beacons are changing every 10 to 15 minutes, thus preventing malicious adversaries from tracking individual users. When a device receives the same beacon over a period of time that is considered significant by the public health authorities (and if the device is assumed to be sufficiently close to the beacon's source) the beacon is permanently stored in the contact list of the device. Based on the characteristics of the targeted virus, contact events can be safely erased after a few days (e.g., 14 days for COVID -19) . When a user is diagnosed as positive (e.g., the highlighted users in Fig. 2 ), the public health authorities will coordinate with the user to upload the stored contact list to their centralized database. The remaining users will periodically download the new contact lists from the database and check whether their own beacons are contained therein. If this is true, the user will be notified about the verified contagion event and will be given instructions for further actions. The adversary assumed in our work is very powerful and may perform both passive and active attacks. We assume that the adversary is equipped with a powerful antenna, which can be either a regular Bluetooth handheld device, or a Software Defined Radio (SDR) that is operated through a laptop/smartphone running an SDR-compatible software tool, such as GNURadio [17] . 1) Passive Attacks: Eavesdropping. We assume that the adversary is a global eavesdropper, able to detect and decode any message broadcasted on the Bluetooth communication channel. This capability allows the adversary to obtain all the information within the exchanged Bluetooth beacons, including the "rolling" standard ID adopted by Bluetooth technology and the ephemeral IDs of the underlying contact tracing protocol. In addition, the adversary locally enriches the intercepted beacon with appropriate metadata, such as time and location information. The adversary could hence conduct a cross-referencing analysis with data collected from various sources, including the "infected" beacons published by the public health authorities, background information on individual users, direct observation of user movements, etc.. The goals of an eavesdropping attack can be manifold. For example, the adversary may try to deanonymize users that have tested positive for the virus, track user locations over time, or identify social relationships among users. 2) Active Attacks: Replay. We also assume that the adversary has Bluetooth transmission capabilities. Thus, it can replay beacons previously acquired (via eavesdropping) from the Bluetooth communication channel. These beacons contain the ephemeral IDs of legitimate users and are, therefore, indistinguishable from legitimate beacons when processed by the contact tracing app. The goal of the adversary is to inject false contact events into the users' contact lists, hence increasing the chances for the user to falsely being considered a contagion riskconsequences could be, for instance, a mandatory, legally binding, period of quarantine for the attack's victim. Relay. This attack aims at bypassing replay attack countermeasures that may incorporate timing information within the beacons, thus limiting the time window where beacons can be replayed. It can be thought of as an amplified version of a replay attack, where the adversary instantaneously disseminates every captured beacon to multiple locations under its control. The beacons are then replayed immediately within each of those locations. The reason why replay/relay attacks are dangerous in the context of contact tracing is that they can be used to manipulate the recorded contact lists. Specifically, an adversary can install a powerful antenna at a busy location (e.g., a shopping mall) and start eavesdropping on the transmitted beacons. Then, it replays those beacons with a high transmit power so that they register as legitimate contacts to a large number of users (even if they are further away from the antenna). As a result, if one of these users has a positive diagnosis, there will be an overwhelming amount of false negative alerts that would saturate test centers (if suspect-positive users are tested) or likely result in mandatory quarantine if testing is not possible-hence imposing an unnecessary privation of personal freedom. Note that, in this work, we do not address Denial of Service (DoS) attacks that may be launched by an adversary to disrupt the operation of the contact tracing network. For example, the adversary might try to jam the Bluetooth communication channel or compromise the availability of the centralized database. We also assume that the disclosure of contact lists from infected users is done securely by the public health authorities. In other words, an adversary is not able to inject false data into the centralized database. Such attacks are independent from the underlying contact tracing protocol, and hence considered out of scope with respect to our contributions. In this section, we present an in-depth analysis of the security and privacy characteristics of the current state-of-theart contact tracing protocols. We focus our discussion on the following metrics. Architecture (C/D/H). In a centralized (C) architecture, all mobile devices forward their proximity data to a centralized database that is administered by the public health authorities. Conversely, in a decentralized (D) approach, the mobile devices do not share their data with the authorities, unless they test positive for the virus. Furthermore, the contact tracing operation is performed in a fully decentralized manner at the individual devices. Finally, in a hybrid (H) architecture, data collection follows the decentralized approach (nothing is disclosed to the authorities), while the contact tracing operation is performed at a centralized location-by having the infected individuals reveal their entire contact history to the health authorities. Clearly, the centralized (and to a lesser extent the hybrid) architecture requires users to fully trust the authorities from a security and privacy perspective. Privacy from Authority. This is a measure of the privacy that users enjoy with regards to the information that is disclosed to the public health authorities by the contact tracing application. For instance, in the absence of a fully decentralized architecture, a central authority can harm the privacy of the users by collecting sensitive data (e.g., GPS locations, contact lists) and/or performing statistical inference on the acquired data. Linkage Attack Resilience. A linkage attack attempts to identify users by analyzing an anonymized dataset, while cross-referencing it with external data sources, such as userspecific information, geolocation data, etc. [18] . For instance, the beacons released to the authorities by a user that had a positive test can potentially reveal his/her identity if the beacons can be linked to precise geographic locations. Replay/Relay Attack Mitigation. As explained previously, replay and relay attacks can be very damaging to the effectiveness of contact tracing. Therefore, contact tracing protocols must incorporate appropriate cryptographic mechanisms to limit their scope or, if possible, eliminate them altogether. Robustness against Eavesdropping. This metric quantifies the usefulness of the beacons that are collected by an eavesdropping adversary. For example, if users upload their previously transmitted beacons to a public database (when deemed infected), an adversary can leverage them to deanonymize the users. Ephemeral Identity. An ephemeral identity is the temporary ID associated with the real user identity and is contained inside the transmitted beacons. This is the minimum privacy guarantee that all contact tracing protocols should provide. Additionally, ephemeral IDs should change frequently, to prevent the tracking of user movements. Exposure of Geolocation Data. Some contact tracing protocols collect GPS data to perform the proximity testing operation. As such, when users are diagnosed as positive, their recent trajectories are disclosed to the public health authorities and, subsequently, to the general public. The cited approach is less private than BLE-based contact tracing, because it does not require from the adversary any effort to learn the detailed trajectory data. Open Source. The protocol and the code are released as open source to facilitate thorough security and privacy audits from both the industry and academia. Decentralized Privacy-Preserving Proximity Tracing (DP-3T) [8] . The DP-3T protocol is the product of a large consortium of European universities and research institutes. It is a fully decentralized protocol that leverages BLE beacons to exchange ephemeral IDs among the participating devices. As reported by Vaudenay [19] , the ephemeral identifiers are generated with an HMAC-SHA256 key, encrypted with AES-CTR or Salsa20. Further, these keys are kept in the device's memory and erased after they are no longer required by the health authorities (e.g., after 14 days). The keys are derived from a root key that is randomly generated every day. The analysis of Vaudenay highlights several security and privacy issues, including a replay attack which is possible due to the absence of message authentication codes. When a user is diagnosed as positive, DP-3T offers several options for disclosing their own beacons to the health authorities. The least private approach discloses all the past daily keys, while the more privacy-preserving option allows the user to choose which beacons to reveal. Apple/Google [9] . Apple and Google jointly designed and implemented a decentralized proximity tracing protocol that is very similar to DP-3T. Unlike other approaches, this protocol is fully integrated within the operating system, and exposes appropriate APIs to third-party developers in order to develop their own smartphone applications. From a privacy perspective, Apple and Google have not released their source code, so users must trust these companies (and their operating systems) with respect to data analysis [18] . With regards to the cryptographic specifications, the key schedule for contact tracing is organized into 3 main phases: (i) tracing key generation, (ii) daily tracing key generation, and (iii) rolling proximity identifier generation. The tracing key generation procedure is executed when contact tracing is first enabled on the mobile device. The 32-byte tracing key is derived via a Cryptographic Random Number Generator and is stored on the device. From this tracing key, an HMAC Key Derivation Function (HKDF), such as HMAC-SHA256, is employed to derive a 16-byte daily tracing key that is valid for a 24-hour time window, based on Unix epoch time. Finally, the rolling proximity identifiers exchanged within the BLE beacons are 16-byte ephemeral IDs, derived from the daily tracing key through an HMAC-SHA256 operation [20] . Berke et al. [21] . This is a GPS-based solution that also adheres to the decentralized architecture. Specifically, the mobile devices are constantly monitoring the users' location, by recording their GPS coordinates every t minutes. Therefore, each point in the user's location history has three dimensions, namely longitude, latitude, and time. When a user is diagnosed as infected, their location history is uploaded to the health authorities' server, thus allowing other devices to download it and look for possible contagion events. To preserve privacy, precise GPS coordinates are replaced by larger geographic areas, and the resulting point-intervals are obfuscated with a hash function like SHA256. In addition, the authors propose a technique where the server and individual clients invoke a private set intersection protocol to identify contagion events, without disclosing the patient's location history. In terms of security, an adversary can either broadcast fake GPS signals [22] (GPS spoofing) or perform a GPS jamming attack [23] , in order to disrupt the proximity tracing operation. Hamagen [24] . Hamagen is a COVID-19 exposure prevention app that was developed by Israel's Ministry of Health. It is fully decentralized and leverages GPS measurements to identify possible COVID-19 exposure events. Once an hour, the installed application downloads a file with an anonymous list of locations, times, and dates that confirmed (from the Ministry) patients have visited in the past. The app will then perform a cross-reference on the (timestamped) locations visited by the user and determine whether the user is at risk of exposure. Note that, the application exploits GPS, Bluetooth, and WiFi to improve the accuracy of geolocation. Additionally, it does not rely on any cryptographic primitives. Corona 100m [25] . This is South Korea's centralized and GPS-based solution that publicly informs citizens (and the health authorities) of known cases within 100 meters of where they are. It is worth noticing that this application crossreferences credit card data, medical records from hospitals, social networks graphs, and video surveillance footage, thus raising serious privacy concerns among the citizens. Pan-European Privacy-Preserving Proximity Tracing (PEPP-PT) [7] . The PEPP-PT protocol is the European Union's solution to digital contact tracing. PEPP-PT is a hybrid approach based on BLE technology and is compliant with the EU's General Data Protection Regulation (GDPR) privacy laws. Unlike DP-3T and Apple/Google, PEPP-PT mandates that the users' BLE beacons (ephemeral IDs) are generated and distributed by the public health authorities. Specifically, during registration, each user is assigned a random ID by the system. Then, for each contact tracing epoch t, the system selects a global secret key K t and encrypts (using AES) all user IDs with the same key. The resulting ciphertexts are the ephemeral IDs that are distributed in advance to the individual users. When testing positive for the coronavirus, users release their logged contact lists to the authorities, who are then able to perform the contact tracing operation at the centralized server, since they can identify the IDs of all contacts by decrypting the beacons with the secret keys. Clearly, this approach is less privacy-preserving than the decentralized solutions, because it allows anyone who owns the AES keys to track all registered citizens. Temporary Contact Numbers (TCN) [26] . TCN is a fully decentralized protocol proposed by the Coalition Network. It leverages BLE communications and its operation is very similar to DP-3T and Apple/Google. In other words, mobile devices generate their own ephemeral IDs that are broadcasted to other devices in their proximity. Each device gradually builds its own private contact list that is not shared with the authorities. After a positive diagnosis, users upload their keys to the centralized database, in order to allow other devices to reconstruct the corresponding ephemeral IDs and measure their exposure risk. The main difference in TCN is that the device generates a public and private key pair (based on Ed25519 curves) so that other devices can verify the authenticity of the reconstructed ephemeral IDs. In particular, the public-key is used as an input to the SHA256 hash function that generates the ephemeral IDs, while the private key is used to sign the report that is sent to the health authorities after the user is diagnosed as positive. BlueTrace [27] . BlueTrace was one of the first protocols to enjoy a wide-scale deployment since it was the fundamental building block in Singapore's TraceTogether app. Its operation is quite similar to PEPP-PT, i.e., a hybrid approach where the ephemeral IDs are generated by the public health authorities. As such, the contact tracing operation is performed in a centralized manner by the health authorities, after the positively diagnosed individuals upload their contact logs to the centralized server. The system maintains a global secret key for the generation of the ephemeral IDs and, during registration, every user is assigned a unique ID. Then, the peruser ephemeral IDs are generated by encrypting a messagecomprising the user ID, the validity period (start and expiration), an initialization vector, and an authentication tag-with an AES256-GCM cipher and Base64 encoding the resulting ciphertext. To minimize the effect of replay attacks, the validity period of each ephemeral ID is set to 15 minutes [27] . Private Automated Contact Tracing (PACT) [28] . PACT is another contact tracing protocol that follows the decentralized approach of DP-3T and Apple/Google. In particular, every device generates its own ephemeral IDs through a Pseudorandom Function (PRF) that takes as input a random 256-bit seed (which changes every hour) and the current time measured at one-minute precision. Furthermore, a newly diagnosed patient will upload all the random seeds from the recent past to the centralized database, in order to allow other users to reconstruct the ephemeral IDs and estimate their exposure risk. Note that, similar to other approaches, PACT reduces the risk of replay attacks by including timestamps into the generation of the ephemeral IDs. Whisper [29] . Whisper is the only proximity tracing protocol thus far in the literature that employs public-key cryptography. It is a fully distributed protocol that leverages BLE communications to monitor and log contact events. Specifically, every device periodically generates a fresh public/private key pair, based on Ed25519 elliptic curves. Additionally, unlike other protocols, Whisper operates in two phases. In the first phase, the device periodically scans the BLE channel to detect other Whisper devices in its proximity. For each discovered device, the protocol initiates a connection (phase two), during which the two devices perform a Diffie-Hellman key exchange to generate a shared key K. For each key K, the device computes two hash digests using the BLAKE2-160 hash function: the tell-token is the hash digest of K and the device's own public-key, while the hear-token is the hash digest of K and the connecting peer's public-key. After a positive diagnosis, the device uploads its own tell-tokens to the centralized database, which enables other devices to compare them against their own hear-tokens. The major advantage of Whisper in terms of privacy is that the published tell-tokens do not reveal any information to an adversary, because it is infeasible to compute the underlying shared keys. IoTrace [4] . IoTrace is a novel IoT-enabled approach to contact tracing. Specifically, in IoTrace, mobile devices neither receive the broadcasted beacons nor maintain individual contact lists. Instead, the deployed IoT devices collect every beacon that is transmitted around them and send all data to a centralized server. When a user tests positive for the coronavirus, the mobile device releases its transmitted beacons to the authorities who then publish all the beacons that are considered in close proximity to the user. The remaining users periodically download the updated database and perform the exposure notification function in a distributed manner. The key characteristic of IoTrace is the reduced energy cost on mobile devices, due to the absence of frequent scanning operations to identify transmitted beacons. However, in this contribution, we only focus on peer-to-peer contact tracing that is performed without the use of an existing IoT infrastructure. As such, we do not include IoTrace in our comparison. In this section, we discuss the security and privacy characteristics of the aforementioned protocols. Our results are summarized in Table II. GNSS Solutions. GNSS-based protocols rely on geolocation data to perform proximity tracing. As such, there are several concerns regarding their accuracy, security, and privacy. First, it is worth noting that, with the exception of Corona 100m which is a centralized approach, GNSS protocols offer perfect privacy to all citizens that do not contract COVID-19. This is because mobile devices do not send any information to the health authorities. However, for the individuals that test positive, these protocols reveal their (partial or full) trajectories over an extended period of time to the health authorities. As such, they are prone to linkage attacks that may crossreference the published geolocation data with background information about the users. Even though the protocol by Berke et al. employs hashing to obfuscate the trajectories, it is still vulnerable to brute-force attacks that can easily deanonymize the locations. In terms of security, GNSS solutions are not susceptible to replay/relay and eavesdropping attacks, because they do not broadcast any data on the wireless channel [30] . On the other hand, GNSS signals can be spoofed by a malicious adversary, due to the lack of encryption/authentication in consumer GNSS products. Such attacks may allow an adversary to manipulate the GPS measurements that are collected by the contact tracing application. Another limitation of GNSS-based contact tracing is that generic devices such as smartphones, are provided with a recreational grade (accuracy within ±7.6m) GNSS receiver. This is not sufficient to determine "real" contagion events and may result in an overwhelming amount of false-negatives. Additionally, in an urban/sub-urban scenario, the shadowing and multipath fading effects further undermine the geolocation accuracy. Finally, the risk of COVID-19 exposure is significantly higher in indoor environments where, unfortunately, GNSS localization is infeasible. Centralized Solutions. Corona 100m is the only truly centralized protocol appearing in our literature review. This is not surprising, since centralized approaches come with significant security and privacy concerns. For example, in the case of Corona 100m, the app continuously reports its location to the public health authorities and is notified whether a confirmed case is within 100m of that location. As a result, every citizen that is actively using the app can be tracked by the authorities. Consequently, Corona 100m offers no privacy from the authority and it is also vulnerable to linkage attacks, because geolocation data can be cross-referenced with external sources to reveal sensitive user information. Even in an ideal world where the authorities are honest and trusted by the general public, the vast amount of valuable data stored at the centralized database serves as an open invitation to malicious hackers. Hybrid Solutions. The two notable protocols that fall into this category are PEPP-PT and BlueTrace. Although the contact logs are stored in a decentralized manner (on the mobile devices) and are only disclosed if a user is diagnosed as positive, hybrid solutions can potentially result in a complete privacy breach. Recall that, under the hybrid model, the health authorities generate and distribute the ephemeral IDs to all devices, in order to perform the contact tracing task at their own server. As such, an eavesdropping adversary with access to the encryption keys that generate the ephemeral IDs can reconstruct the movements of every registered user. Consequently, hybrid solutions have no privacy from authority and are extremely vulnerable to linkage and eavesdropping attacks. Also note that, the authority is not anonymizing the user identities, but is instead utilizing a pseudonym schema that can be vulnerable to several attacks described in the literature, such as single position attack, context linking attack, multiple position and context linking attack, multiple position attack, and compromised trusted authority [31] . In other words, hybrid protocols demand a complete trust to the authorities on behalf of the users. Finally, both PEPP-PT and BlueTrace incorporate timestamp data into the generated ephemeral IDs, which limits the effect of replay attacks (although the timing information is relatively coarse). On the other hand, they both fail to protect against relay attacks, since they do not take into account geolocation data. Decentralized Solutions. Here we focus on BLE-based protocols that utilize symmetric key algorithms, including DP-3T, Apple/Google, TCN, and PACT. As explained previously, their algorithms are quite similar and, therefore, they share the same security and privacy characteristics. First, similar to the decentralized GNSS-based protocols (Hamagen and Berk et al.), they offer perfect privacy to the vast majority of users who never contract the coronavirus. Furthermore, the beacons collected by an eavesdropping adversary cannot be used to de-anonymize them, because they never disclose their own beacons to the health authorities. Conversely, positively diagnosed users do not enjoy any privacy, because the disclosed ephemeral IDs can place them at precise locations by an eavesdropping adversary (or regular users who may trace those beacons inside their stored contact logs). As a result, decentralized protocols are not resilient against linkage attacks. In terms of replay attacks, all protocols use time as an input to the beacon generation process, thus reducing the risk of contact log manipulation by an active adversary. Note, however, that time is approximated in the scale of minutes, so there is still a sufficiently large time window that attackers can exploit. On the other hand, none of the aforementioned protocols utilize geolocation and they are, therefore, vulnerable to relay attacks. A notable advantage of BLE technology with regards to localization is its accuracy, which makes it an ideal candidate for effective contact tracing. Specifically, every transmitted beacon contains information about the time of arrival and the Received Signal Strength (RSS). The latter is a key parameter for wireless positioning and aids in deriving the distance between two Bluetooth enabled devices, by leveraging a radio propagation model [32] . However, from a privacy perspective, Table II COMPARISON OF OUR SOLUTION AGAINST THE STATE-OF-THE-ART APPROACHES. NONE: , LOW: , MEDIUM: , HIGH: Features DP-3T [8] A/G [9] Berke et al. [21] Hamagen [24] Corona 100m [25] PEPP-PT [7] TCN [26] BlueTrace [27] PACT [28] Whisper [29] SpreadMeNot it is crucial that the device's operating system implements a rolling MAC address protocol (e.g., by randomizing its last 3 bytes), in order to prevent the tracking of individual users. It is also recommended that the schedule of the ephemeral IDs follows that of the MAC address randomization. A final remark concerns the security of the database server. Even though contact tracing is performed in a decentralized manner, the server plays a crucial role as a proxy for the distribution of the "infected" beacons. As such, the security of the health authorities' infrastructure is of paramount importance, even in the decentralized architecture [33] . Public-key Solutions. Whisper is the only contact tracing protocol in the literature that employs public-key cryptography. Specifically, it allows any two mobile devices to exchange a secret contact ID (tell-token and hear-token) that is infeasible to compute without knowledge of the underlying public keys. As a result, when diagnosed users disclose their own telltokens to the centralized server, the authorities cannot map them to precise locations. In other words, Whisper offers excellent privacy from authority and is immune to eavesdropping attacks. However, the tokens that are stored by the mobile devices contain timing information, so individual mobile devices may be able to launch linkage attacks against the published tokens that are present in their memory. Another limitation of Whisper is that it does not employ any mechanism to mitigate replay/relay attacks. Finally, we should mention that Whisper is a complex protocol that does not rely simply on broadcasted beacons. Instead, to compute a new pair of tokens, the two devices have to establish a peer-to-peer connection and perform a Diffie-Hellman key exchange. In the next section, we introduce SpreadMeNot, a novel public-key based protocol that avoids the pitfalls of Whisper and is an excellent candidate for secure and privacy-preserving contact tracing. In this section, we describe in detail our proposed solution for privacy-preserving contact tracing. In Section V-A we give a brief overview of the scheme and present the cryptographic experiment that will be the basis of our security proof. In Section V-B we introduce our construction and prove its security. In Section V-C we propose a simple extension that mitigates several active attacks, and in Section V-D we analyze the privacy properties of our protocol in comparison to the existing state-of-the-art approaches. The SpreadMeNot protocol consists of a tuple of algorithms Π = (GenKey, GenBeacon, RandBeacon, Test) that operate as follows. 1) GenKey: It takes as input a security parameter n and outputs a private key x and a public-key P . 2) GenBeacon: It takes as input a public-key P and outputs a beacon C. 3) RandBeacon: It takes as input a beacon C and outputs a randomized version C . It takes as input a beacon C and a private key x, and outputs true if the beacon is generated under publickey P . Initially, every user executes the GenKey algorithm to generate their public/private key pair. However, in this setting, the public-key is irrelevant to the rest of the users and does not need to be shared (but it does not have to be secret). At regular intervals (e.g., every 15 minutes), the user's app will invoke the GenBeacon algorithm to generate a fresh random beacon. That beacon will be broadcast continuously until the next interval, in order for the surrounding devices to detect the user as a potential contact. Note that only significant events are stored on each device, i.e., beacons that are very close to the user (say, within 2 meters) for a sufficiently long time duration. Based on the characteristics of the virus, old contact events (e.g., older than two weeks) are automatically erased. If a user tests positive for COVID-19, he publishes his contact list on the centralized database managed by the public health authorities. The list consists of all the beacons that are currently stored on his device. More importantly, the published list is first permuted and all its entries are randomized. Specifically, for each stored beacon C, algorithm RandBeacon is invoked to produce a new beacon C that is indistinguishable from C. Finally, the published contact list is downloaded by all mobile devices that subsequently apply algorithm Test on every beacon. If any instance of Test outputs true, the user infers that he has been in close proximity to the infected individual. In terms of security, we want beacons generated by different public keys to be indistinguishable from each other. Therefore, we define an eavesdropping adversary A that has access to all transmitted and (randomized) published beacons. The objective of A is to distinguish beacons that are generated from a specific public-key P . Experiment Exp eav A,Π (n), as shown in Figure 3 , formulates the security of our protocol Π = (GenKey, GenBeacon, RandBeacon, Test) with security parameter n, under an eavesdropping adversary A. We say that A succeeds in this experiment if Conversely, our scheme is secure if A fails in this experiment. Beacon Indistinguishability Experiment Exp eav A,Π (n) 1) On input a security parameter n, GenKey generates two private keys x 0 , x 1 and the corresponding public keys P 0 , P 1 ; the public keys are given to A. A calls GenBeacon an arbitrary number of times. 3) The challenger selects a random bit b ←$ {0, 1}. If b = 0, the challenger uses GenBeacon to generate a beacon C 0 , under public-key P 0 . If b = 1, the challenger generates C 1 under public-key P 1 . Assume an elliptic curve group G of prime order q and let G be a generator of G. This information is public and shared by all users. Also, n is the security parameter that determines the precise construction of the group G. Our protocol Π is instantiated as follows. 1) GenKey: On input a security parameter n, choose a uniformly random private key x ∈ Z * q and set the publickey P = xG. 2) GenBeacon: On input a public-key P , choose a uniformly random r ∈ Z * q and output beacon C = (rG, rP ). 3) RandBeacon: On input a beacon C = (rG, rP ), choose a uniformly random r ∈ Z * q and output C = (r rG, r rP ) = (r G, r P ). On input a beacon C = (rG, rP ) and a private key x, compute A = xrG. If A = rP , output true; otherwise, output false. It can be easily verified that the protocol is correct, i.e., if algorithm Test returns true, the input beacon is generated under public-key P , since xG = P . The following theorem proves the security of our scheme. Theorem 1. There is no polynomial-time adversary A that succeeds in Exp eav A,Π (n). Proof. The only information that the adversary has is a beacon C = (rG, rP ). If A succeeds in the experiment, it means that it can distinguish between rx 0 G and rx 1 G with nonnegligible probability. Note that, it is infeasible to derive any of the secret values r, x 0 , x 1 , due to the ECDLP assumption. Since r, x 0 , x 1 are uniformly random in Z * q , both rx 0 G and rx 1 G would appear as random elements in G. The probability of distinguishing between any two random group elements is negligible in log q, where q is the order of G and log q is the order of the security parameter n. Since A is polynomial-time, the experiment succeeds with probability negl(n) larger than a random guess, which concludes our proof. The downside of using public-key cryptography is that it facilitates impersonation attacks. That is, if an adversary has knowledge of a user's public key, he can trivially generate valid beacons on his behalf. Even worse, knowledge of a user's public key is not really necessary; instead, the adversary may intercept a single beacon and then use algorithm RandBeacon to generate new, valid beacons at will. In addition to impersonation attacks, it is also essential to protect against other active attacks, including replay and relay attacks. To this end, we propose a simple solution, based on timestamps, localization data, and digital signatures, to mitigate such attacks. First, we assume that the users' mobile devices are synchronized to within a few seconds and every device knows its approximate location (longitude and latitude). Then, every beacon is transmitted with an attached Unix timestamp, which represents the current time, and the user's current coordinates. In addition, the beacon includes a digital signature that is computed as follows. 1) Let C = (rG, rP ) be the current beacon, let T be the corresponding Unix timestamp, and let L be the user's current location. 2) Let d = rx mod q be the private key associated with public-key P = rP = rxG, i.e., the second term of the beacon. 3) Use the Elliptic Curve Digital Signature Algorithm (ECDSA) algorithm to generate the signature σ of message L||T ||rG||rP , under private key d. 4) Broadcast beacon C = (L, T, rG, rP, σ). At the receiver side, the device will first verify that T is within the synchronization threshold and L sufficiently close. Then, it will use the public-key P = rP to verify signature σ. If any of these tests fail, the beacon will be discarded. As such, any attempt from an adversary to re-use that beacon (or a randomized version of it) at subsequent timestamps (or remote locations) will fail. Note that, to save valuable resources, it is not necessary to verify a signature as soon as it is received. Recall that a beacon is only stored in the contact list if it has been received multiple times over a sufficiently long time interval. Therefore, the device can simply defer the signature verification process until a beacon is inserted into the contact list. We now discuss the security and privacy characteristics of our protocol, with respect to Table II . In terms of privacy, SpreadMeNot has several clear advantages over the current state-of-the-art approaches. First, it is immune to eavesdropping attacks, because the published information (from infected users) is randomized and, thus, cannot be linked to any previously intercepted beacon by an adversary. As such, SpreadMeNot also protects the privacy of the users who have been positively diagnosed. Second, the infected user never reveals his/her own beacons and, therefore, cannot be traced inside a malicious user's contact list, which may include detailed timestamp and location information for each contact. More importantly, the published contact lists are permuted and do not include any identifiable information besides the two elliptic curve points (i.e., the signatures and all metadata are removed). As a result, even if an adversary matches a beacon inside the published contact list, it is impossible to tie that beacon to a specific location and timestamp. Consequently, our protocol is very resilient against linkage attacks. Finally, by attaching a digital signature in every transmitted beacon, SpreadMeNot is the first protocol in the literature that mitigates both replay and relay attacks. We evaluated the cryptographic component of SpreadMeNot on an LG Google Nexus 5X, equipped with a hexa-core 64bit CPU (4 × 1.4 GHz Cortex-A53 and 2 × 1.8 GHz Cortex-A57) ARMv8-A. The wireless communications module was evaluated on a Qualcomm Atheros QCA6174A SoC hardware platform with built-in IEEE 802.11ac radio, Bluetooth v4.2, and Bluetooth Low Energy. The device supports the standard 256-QAM modulation and utilizes 1, 216 KB RAM and 448 KB ROM for Wi-Fi, and 192 KB RAM and 672 KB ROM for Bluetooth [34] . In particular, the cryptographic operations of the Spread-MeNot protocol where implemented in C++, with the well known OpenSSL 1.1.1d C library [35] , using Android Native Development Kit (NDK) with Android 8.1 Oreo OS [36] . For the experimental evaluation, we selected four elliptic curves, i.e., secp128r1, secp160r1, secp192k1, and secp256k1. According to NIST's latest guidelines, these curves provide security levels of 64, 80, 96, and 128 bits, respectively [37] . Furthermore, following NIST's recommendations, we adopted the SHA256 hash function for the digital signatures. We considered the following two performance metrics for our protocol: (i) CPU time for the beacon generation function; and, (ii) energy consumption for the computations and TX/RX operations. Specifically, to estimate the energy consumption due to the public-key cryptographic primitives, we focused on the protocol's basic operation-the elliptic curve point-scalar multiplication-which is by far the most CPU intensive operation. To this end, we leveraged the power profile component of the Android OS that outputs the current consumption values for sensors and CPUs and the approximate battery drain caused by the component over time. The power profile is provided by the device manufacturer [38] . After performing the scalar-point multiplication, we estimated the current drained at 105.87 mA. Therefore, we concluded that this value is the instantaneous current drained by the CPU to perform the elliptic curve operation. Additionally, we measured the battery voltage at 3.9 V, using a common battery monitoring application. Fig. 4 illustrates the CPU time that is required to perform a single scalar-point multiplication for various security levels. At 80 bits security, the operation takes 1.1196 ms to complete and it consumes ≈ 0.4623 mJ of energy. When we require 128 bits security, the cost is approximately doubled, i.e., 2.4030 ms of CPU time and ≈ 0.9922 mJ of consumed energy. The tests related to the CPU time were repeated 5, 000 times and, in Fig. 4 , we report the mean value and the 95% confidence intervals. To measure the energy consumption and transmission time during the beacon broadcast operation, we assumed the Bluetooth v4.2 standard, where the data transmission rate is 1 Mbps. Nevertheless, given the multipath and slow fading effects that negatively affect RF communications (due to scattering, reflection, and diffraction), we adopted a conservative stance and assumed that the maximum throughput is 0.8 Mbps. We evaluated SpreadMeNot at the MAC layer, where the Bluetooth v4.2 standard sets the maximum frame size at 265 bytes (using packet length extension), which translates to a maximum payload size of 251 octets [39] . Thus, if the protocol needs to transmit larger payloads, they must be fragmented. Note that, the amount of transferred data is related to the desired security level, i.e., the communication cost increases for more secure elliptic curve groups. However, one technique to reduce the payload size is to employ point compression, where only one coordinate is transmitted for each elliptic curve point. The energy consumption of the TX and RX operations for the Qualcomm Atheros QCA6174A SoC module can be computed from the area underlying the current consumption curve, as depicted in Eq. 2. Here, E is the energy consumption (measured in mJ), i(t) is the instantaneous current drain (in mA), τ is the operation duration, and 1.8 V is the minimum voltage of the QCA6174A board (in Volts). This translates to ≈ 46 mA in TX mode and ≈ 42 mA in RX mode, for the Bluetooth v4.2 protocol. Fig. 5 illustrates the total energy consumption and the time required to complete one beacon exchange under the Spread-MeNot protocol. First, the energy consumption ranges from a minimum of 2.552 mJ to a maximum of 6.260 mJ, based on the underlying security level. Similarly, for 64 bits security, the average time to complete the exchange is 8.274 ms, where 5.6837 ms are required for the cryptographic operations (i.e., beacon generation, and signature generation and verification), while 2.5903 ms are devoted to the exchange of the crypto material. For 128 bits security, the time to complete the protocol increases to 18.288 ms, where 14.418 ms are devoted to the cryptographic computations and 3.87 ms are related to the exchange of the crypto material. We emphasize that the overall duration of the beacon exchange can be affected by the configuration of the operating system features at the MAC link-layer, and also various RF phenomena at the PHY layer. Assuming the standard-compliant MAC frames in Bluetooth v4.2, Table III summarizes the different cost associated with a single beacon exchange in the SpreadMeNot protocol. The results confirm that, even at the highest security level, SpreadMeNot is feasible for resource-constrained smart devices. Indeed, the battery capacity of the LG Google Nexus 5X smartphone is 41, 796 J (2, 700 mAh) so, for 128 bits security, our protocol consumes ≈ 1.5 · 10 −7 % of the battery capacity. Also note that the payload size is well within the standard's limit, so beacons can be transmitted within a single MAC frame. Our experimental evaluation detailed in the previous section illustrates the feasibility of public-key cryptography in the context of contact tracing. Compared to the state-of-the-art symmetric key approaches, such as Apple/Google, Spread-MeNot shows a more sustained overhead, though compensated from much stronger security and privacy guarantees. In our evaluation, we focused on the beacon exchange process, which is the most frequently performed operation, like for the vast majority of contact tracing apps. However, one operation where the performance of SpreadMeNot is orders of magnitude more expensive with respect to other solutions is the exposure notification operation. Though, it should be noted that this operation is invoked much less frequently, and could be easily outsourced, as discussed later. In detail, in the event of a positive diagnosis, the app has to re-randomize all beacons in its contact list prior to uploading them to the centralized server. Assuming an average of 200 significant contact events per day, over a period of 14 days, this amounts to 2, 800 entries. Recall that the RandBeacon function necessitates two point-scalar multiplications and, based on the results of Fig. 4 , the entire process may consume (for 128 bits security) up to 13.44 s of computing time and 5.55 J of energy. Additionally, the communication cost to upload the beacons is 179.2 KB. Again, these costs may be dramatically reduced: cut by half if we choose 80 bits security, or completely removed if we resort to outsourcing, as discussed in the following. An even more resource-demanding operation is the actual contact tracing, where individual devices have to identify possible contagion events, after downloading the latest contact lists coming from recently diagnosed patients. Assuming that this operation is performed on a daily basis, the typical number of beacons that need to be matched would be in the order of millions (e.g., 5.6 million, if there are 2, 000 new cases with 2, 800 stored beacons each). In this example, the smartphone would consume (for 128 bits security) approximately 3.7 h of computing time and 5, 556 J of energy. There is also a communication cost of 360 MB to download the beacons from the centralized server. Again, these costs may be dramatically reduced: cut by half if we choose 80 bits security, or completely removed if we resort to outsourcing, as discussed in the following. Despite the highlighted cost, we strongly believe that SpreadMeNot's superior security and privacy properties offset any argument regarding its performance. More importantly, the cited costs are easily mitigated by separating the online and offline components of the protocol. Specifically, it is worth noting that all the point-scalar multiplications in the beacon generation process can be performed offline. There are a total of three such operations: two for computing the beacon itself and one for computing the digital signature (which is input-independent). Therefore, we can pre-compute offline a large number of random elliptic curve points that may be used during the online phase (beacon exchange) by the device. Consequently, the beacon generation process can be reduced to computing just one hash function and two integer multiplications modulo q. Both are very cheap operationsinvolved in the computation of the digital signature. Similarly, all the remaining expensive operations (contact list maintenance and contact tracing) may be safely moved into the offline module. Contact list maintenance involves the verification of all signatures for the beacons that are inserted into the list (to detect replay/relay attacks), and the re-randomization of the accepted beacons in order to minimize the online computational cost in the event of a positive diagnosis. More importantly, contact tracing is also independent of the protocol's everyday operations and may be performed in an offline fashion. To this end, we propose the following two approaches for handling the offline operations: • Night mode: The offline work will be performed during night time, when the smartphone is charging and connected to the home WiFi network. • Desktop app: A companion desktop app will be developed to handle the offline tasks. The user will periodically sync the smartphone with the desktop app, in order to upload and download the necessary information. Note that this one would be the preferred solution, as modern desktop CPUs can perform the cryptographic operations significantly faster. Also, the app will implement multithreading to take advantage of the multiple CPU cores, since all the protocol's operations are highly parallelizable. In this paper, we have provided two main contributions in the domain of digital contact tracing. We first performed a thorough evaluation of the privacy and security characteristics of the main contact tracing apps, focusing on their basic mechanisms. Our results showed that the most prominent solutions fail to protect the privacy of positively diagnosed individuals, as well as being vulnerable to a variety of active and passive attacks. To cope with the above-highlighted shortcomings, our second contribution was the design of SpreadMeNot, a novel, provably secure contact tracing protocol that protects the privacy of all users while at the same time being resilient against most passive and active attacks, including eavesdropping and replay/relay attacks. Although SpreadMeNot is based on public-key cryptographic primitives that are computationally expensive, we experimentally showed that the induced overhead can be easily handled by modern smartphones. In addition, we have demonstrated that all resource-intensive operations can be safely moved into an offline module, thus rendering SpreadMeNot's online proximity tracing task extremely lightweight. Given the strong and provable security and privacy properties, combined with the experimentally proved sustainable overhead, we argue that SpreadMeNot is the ideal candidate for digital contact tracing. Finally, the open source nature of this project will also pave the way for further solutions in the domain. Roberto Di Pietro, ACM Distinguished Scientist, is Full Professor in Cybersecurity at HBKU-CSE. Previously, he was in the capacity of Global Head Security Research at Nokia Bell Labs, and Associate Professor (with tenure) of Computer Science at University of Padova, Italy. He also served 10+ years as senior military technical officer. Overall, he has been working in the cybersecurity field for 23+ years, leading both technology-oriented and research-focused teams in the private sector, government, and academia (MoD, United Nations HQ, EUROJUST, IAEA, WIPO). His main research interests include security and privacy for wired and wireless distributed systems (e.g. Blockchain technology, Cloud, IoT, On-line Social Networks), virtualization security, applied cryptography, computer forensics, and data science. Other than being involved in M&A of start-up-and having founded one (exited)-, he has been producing 230+ scientific papers and patents over the cited topics, has co-authored three books, edited one, and contributed to a few others. He is serving as an AE for ComCom, ComNet, PerCom, Journal of Computer Security, and other Intl. journals. In 2011-2012 he was awarded a Chair of Excellence from University Carlos III, Madrid. In 2020 he received the Jean-Claude Laprie Award for having significantly influenced the theory and practice of Dependable Computing. A Study of the Privacy of COVID-19 Contact Tracing Apps Quantifying SARS-CoV-2 transmission suggests epidemic control with digital contact tracing Demystifying COVID-19 digital contact tracing: A survey on frameworks and mobile apps IoTrace: A Flexible, Efficient, and Privacy-Preserving IoT-enabled Architecture for Contact Tracing On using Bluetooth-Low-Energy for contact tracing TraceTogether Pan-European Privacy-Preserving Proximity Tracing Decentralized Privacy-Preserving Proximity Tracing: Overview of Data Protection and Security Privacy-Preserving Contact Tracing Vetting Security and Privacy of Global COVID-19 Contact Tracing Applications Anonymity Preserving IoT-Based COVID-19 and Other Infectious Disease Contact Tracing Model Bluetooth Specification Version 4 Inside Bluetooth low energy Global Positioning System Standard Positioning Service Performance Standard (GPS SPS PS) A Survey and Analysis of the GNSS Spoofing Threat and Countermeasures Guide to Elliptic Curve Cryptography Software Defined Radio: Enabling Technologies Security Analysis of the COVID-19 Contact Tracing Specifications by Analysis of DP3T Contact Tracing -Cryptography Specification Assessing Disease Exposure Risk with Location Data: A Proposal for Cryptographic Preservation of Privacy Drive Me Not: GPS Spoofing Detection via Cellular Network: (Architectures, Models, and Experiments) A study of GPS jamming and anti-jamming Israeli Health Ministry. (2020) Hamagen Corona 100m Temporary Contact Numbers Protocol BlueTrace: A privacy-preserving protocol for community-driven contact tracing across borders PACT:Private Automated Contact Tracing Whisper Tracing -an open and privacy first protocol for contact tracing A First Look at Privacy Analysis of COVID-19 Contact Tracing Mobile Applications A classification of location privacy attacks and approaches Bluetooth positioning using RSSI and triangulation methods A Survey of COVID-19 Contact Tracing Apps OpenSSL -Cryptography and SSL/TLS Toolbox Android (Operating System) Recommendation for key management: Part 1 -General Measuring Power Values -Android Open Source Project Higher Speed -How Fast Can It Be This publication was partially supported by awards NPRP11S-0109-180242 from the QNRF-Qatar National Research Fund, a member of The Qatar Foundation. The information and views set out in this publication are those of the authors and do not necessarily reflect the official opinion of the QNRF.