We present attacks that use only the volume of responses to range queries to reconstruct databases. Our focus is on practical attacks that work for large-scale databases with many values and records, without requiring assumptions on the data or query distributions. Our work improves on the previous state-of-the-art due to Kellaris \emph{et al.} (CCS 2016) in all of these dimensions. Our main attack targets reconstruction of database counts and involves a novel graph-theoretic approach. It generally succeeds when $R$, the number of records, exceeds $N^2/2$, where $N$ is the number of possible values in the database. For a uniform query distribution, we show that it requires volume leakage from only $O(N^2 \log N)$ queries (cf.\ $O(N^4 \log N)$ in prior work). We present two ancillary attacks. The first identifies the value of a new item added to a database using the volume leakage from fresh queries, in the setting where the adversary knows or has previously recovered the database counts. The second shows how to efficiently recover the ranges involved in queries in an online fashion, given an auxiliary distribution describing the database. Our attacks are all backed with mathematical analyses and extensive simulations using real data.

To protect database confidentiality even in the face of full compromise while supporting standard functionality, recent academic proposals and commercial products rely on a mix of encryption schemes. The common recommendation is to apply strong, semantically secure encryption to the “sensitive” columns and protect other columns with property-revealing encryption (PRE) that supports operations such as sorting. We design, implement, and evaluate a new methodology for inferring data stored in such encrypted databases. The cornerstone is the multinomial attack, a new inference technique that is analytically optimal and empirically outperforms prior heuristic attacks against PRE-encrypted data. We also extend the multinomial attack to take advantage of correlations across multiple columns. These improvements recover PRE-encrypted data with sufficient accuracy to then apply machine learning and record linkage methods to infer the values of columns protected by semantically secure encryption or redaction. We evaluate our methodology on medical, census, and union-membership datasets, showing for the first time how to infer full database records. For PRE-encrypted attributes such as demographics and ZIP codes, our attack outperforms the best prior heuristic by a factor of 16. Unlike any prior technique, we also infer attributes, such as incomes and medical diagnoses, protected by strong encryption. For example, when we infer that a patient in a hospital-discharge dataset has a mental health or substance abuse condition, this prediction is 97% accurate.

We introduce BitML, a domain-specific language for specifying contracts that regulate transfers of bitcoins among participants, without relying on trusted intermediaries. We define a symbolic and a computational model for reasoning about BitML security. In the symbolic model, participants act according to the semantics of BitML, while in the computational model they exchange bitstrings, and read/append transactions on the Bitcoin blockchain. A compiler is provided to translate contracts into standard Bitcoin transactions. Participants can execute a contract by appending these transactions on the Bitcoin blockchain, according to their strategies. We prove the correctness of our compiler, showing that computational attacks on compiled contracts are also observable in the symbolic model.

Nowadays, mobile banking becomes a popular tool which consumers can conduct financial transactions such as shopping, monitoring accounts balance, transferring funds and other payments. Consumers dependency on mobile needs, make people take a little bit more interest in mobile banking. The use of the one-time password which is sent to the user mobile phone by short message service (SMS) is a vulnerability which we want to solve with proposing a new scheme called S-Mbank. We replace the authentication using the one-time password with the contactless smart card to prevent attackers to use the unencrypted message which is sent to the user's mobile phone. Moreover, it deals vulnerability of spoofer to send an SMS pretending as a bank's server. The contactless smart card is proposed because of its flexibility and security which easier to bring in our wallet than the common passcode generators. The replacement of SMS-based authentication with contactless smart card removes the vulnerability of unauthorized users to act as a legitimate user to exploit the mobile banking user's account. Besides that, we use public-private key pair and PIN to provide two factors authentication and mutual authentication. We use signcryption scheme to provide the efficiency of the computation. Pair based text authentication is also proposed for the login process as a solution to shoulder-surfing attack. We use Scyther tool to analyze the security of authentication protocol in S-Mbank scheme. From the proposed scheme, we are able to provide more security protection for mobile banking service.

While businesses shift their databases to the cloud, they continue to depend on them to operate correctly. Alarmingly, cloud services constantly face threats from exploits in the privileged computing layers (e.g. OS, Hypervisor) and attacks from rogue datacenter administrators, which tamper with the database's storage and cause it to produce incorrect results. Although integrity verification of outsourced storage and file systems is a well-studied problem, prior techniques impose prohibitive overheads (up to 30x in throughput) and place additional responsibility on clients. We present VeritasDB, a key-value store that guarantees data integrity to the client in the presence of exploits or implementation bugs in the database server. VeritasDB is implemented as a network proxy that mediates communication between the unmodified client(s) and the unmodified database server, which can be any off-the-shelf database engine (e.g., Redis, RocksDB, Apache Cassandra). The proxy transforms each client request before forwarding it to the server and checks the correctness of the server's response before forwarding it to the client. To ensure the proxy is trusted, we use the protections of modern trusted hardware platforms, such as Intel SGX, to host the proxy's code and trusted state, thus completely eliminating trust on the cloud provider. To maintain high performance in VeritasDB while scaling to large databases, we design an authenticated Merkle B+-tree that leverages features of SGX (modest amount of protected RAM, direct access to large unprotected RAM, and CPU parallelism) to implement several novel optimizations based on caching, concurrency, and compression. On standard YCSB and Visa transaction workloads, we observe an average overhead of 2.8x in throughput and 2.5x in latency, compared to the (insecure) system with no integrity checks --- using CPU parallelism, we bring the throughput overhead down to 1.05x.

Payment channels emerged recently as an efficient method for performing cheap \emph{micropayments} in cryptocurrencies. In contrast to traditional on-chain transactions, payment channels have the advantage that they allow for nearly unlimited number of transactions between parties without involving the blockchain. In this work, we introduce \emph{Perun}, an off-chain channel system that offers a new method for connecting channels that is more efficient than the existing technique of ``routing transactions'' over multiple channels. To this end, Perun introduces a technique called ``virtual payment channels'' that avoids involvement of the intermediary for each individual payment. In this paper we formally model and prove security of this technique in the case of one intermediary, who can be viewed as a ``payment hub'' that has direct channels with several parties. Our scheme works over any cryptocurrency that provides Turing-complete smart contracts. As a proof of concept, we implemented Perun's smart contracts in \emph{Ethereum}.

Online advertising is a multi-billion dollar industry, forming the primary source of income for many publishers offering free web content. Serving advertisements tailored to users' interests greatly improves the effectiveness of advertisements, which benefits both publishers and users. The privacy of users, however, is threatened by the widespread collection of data that is required for behavioural advertising. In this paper, we present BAdASS, a novel privacy-preserving protocol for Online Behavioural Advertising that achieves significant performance improvements over the state of the art without disclosing any information about user interests to any party. BAdASS ensures user privacy by processing data within the secret-shared domain, using the heavily fragmented shape of the online advertising landscape to its advantage and combining efficient secret-sharing techniques with a machine learning method commonly encountered in existing advertising systems. Our protocol serves advertisements within a fraction of a second, based on highly detailed user profiles and widely used machine learning methods.

OpenStack is the prevalent open-source, non-proprietary package for managing cloud services and data centers. It is highly complex and consists of multiple inter-related components which are developed by separate, loosely coordinated groups. We initiate an effort to provide a rigorous and holistic security analysis of OpenStack. Our analysis has the following key features: -It is user-centric: It stresses the security guarantees given to users of the system, in terms of privacy, correctness, and timeliness of the services. -It provides defense in depth: It considers the security of OpenStack even when some of the components are compromised. This departs from the traditional design approach of OpenStack, which assumes that all services are fully trusted. -It is modular: It formulates security properties for individual components and uses them to assert security properties of the overall system. We base our modeling and security analysis in the universally composable (UC) security framework, which has been so far used mainly for analyzing security of cryptographic protocols. Indeed, demonstrating how the UC framework can be used to argue about security-sensitive systems which are mostly non-cryptographic in nature is another main contribution of this work. Our analysis covers only a number of core components of OpenStack. Still, it uncovers some basic and important security trade-offs in the design. It also naturally paves the way to a more comprehensive analysis of OpenStack.

Blockchain technology like Bitcoin is a rapidly growing field of research which has found a wide array of applications. However, the power consumption of the mining process in the Bitcoin blockchain alone is estimated to be at least as high as the electricity consumption of Ireland which constitutes a serious liability to the widespread adoption of blockchain technology. We propose a novel instantiation of a proof of human-work which is a cryptographic proof that an amount of human work has been exercised, and show its use in the mining process of a blockchain. Next to our instantiation there is only one other instantiation known which relies on indistinguishability obfuscation, a cryptographic primitive whose existence is only conjectured. In contrast, our construction is based on the cryptographic principle of multiparty computation (which we use in a black box manner) and thus is the first known feasible proof of human-work scheme. Our blockchain mining algorithm called uMine, can be regarded as an alternative energy-efficient approach to mining.

Searchable symmetric encryption (SSE) schemes are commonly proposed to enable search in a protected unstructured documents such as email archives or any set of sensitive text files. However, some SSE schemes have been recently proposed in order to protect relational databases. Most of the previous attacks on SSE schemes have only targeted its common use case, protecting unstructured data. In this work, we propose a new inference attack on relational databases protected via SSE schemes. Our inference attack enables a passive adversary with only basic knowledge about the meta-data information of the target relational database to recover the attribute names of some observed queries. This violates query privacy since the attribute name of a query is secret.

In the last decade, location information became easily obtainable using off-the-shelf mobile devices. This gave a momentum to developing Location Based Services (LBSs) such as location proximity detection, which can be used to find friends or taxis nearby. LBSs can, however, be easily misused to track users, which draws attention to the need of protecting privacy of these users. In this work, we address this issue by designing, implementing, and evaluating multiple algorithms for Privacy-Preserving Location Proximity (PPLP) that are based on different secure computation protocols. Our PPLP protocols are well-suited for different scenarios: for saving bandwidth, energy/computational power, or for faster runtimes. Furthermore, our algorithms have runtimes of a few milliseconds to hundreds of milliseconds and bandwidth of hundreds of bytes to one megabyte. In addition, the computationally most expensive parts of the PPLP computation can be precomputed in our protocols, such that the input-dependent online phase runs in just a few milliseconds.

This paper takes a critical look at the recent trend of building electronic voting systems on top of block chain technology. Even though being very appealing from the election integrity perspective, block chains have numerous technical, economical and even political drawbacks that need to be taken into account. Selecting a good trade-off between desirable properties and restrictions imposed by different block chain implementations is a highly non-trivial task. This paper aims at bringing some clarity into performing this task. We will mostly be concentrating on public permissionless block chains and their applications as bulletin board implementations as these are the favourite choices in majority of the recent block chain based voting protocol proposals.

Machine learning on encrypted data is a cryptographic method for analyzing private and/or sensitive data while keeping privacy. In the training phase, it takes as input an encrypted training data and outputs an encrypted model without using the decryption key. In the prediction phase, it uses the encrypted model to predict results on new encrypted data. In each phase, no decryption key is needed, and thus the privacy of data is guaranteed while the underlying encryption is secure. It has many applications in various areas such as finance, education, genomics, and medical field that have sensitive private data. While several studies have been reported on the prediction phase, few studies have been conducted on the training phase due to the inefficiency of homomorphic encryption (HE), leaving the machine learning training on encrypted data only as a long-term goal. In this paper, we propose an efficient algorithm for logistic regression on encrypted data, and evaluate our algorithm on real financial data consisting of 422,108 samples over 200 features. Our experiment shows that an encrypted model with a sufficient Kolmogorov Smirnow statistic value can be obtained in $\sim$17 hours in a single machine. We also evaluate our algorithm on the public MNIST dataset, and it takes $\sim$2 hours to learn an encrypted model with 96.4% accuracy. Considering the inefficiency of HEs, our result is encouraging and demonstrates the practical feasibility of the logistic regression training on large encrypted data, for the first time to the best of our knowledge.

Post 9/11, journalists, scholars and activists have pointed out that secret laws --- a body of law whose details and sometime mere existence is classified as top secret --- were on the rise in all three branches of the US government due to growing national security concerns. Amid heated current debates on governmental wishes for exceptional access to encrypted digital data, one of the key issues is: which mechanisms can be put in place to ensure that government agencies follow agreed-upon rules in a manner which does not compromise national security objectives? This promises to be especially challenging when the rules, according to which access to encrypted data is granted, may themselves be secret. In this work we show how the use of cryptographic protocols, and in particular, the use of zero-knowledge proofs can ensure accountability and transparency of the government in this extraordinary, seemingly deadlocked, setting. We propose an efficient record-keeping infrastructure with versatile publicly verifiable audits that preserve perfect (information-theoretic) secrecy of record contents as well as of the rules by which the records are attested to abide. Our protocol is based on existing blockchain and cryptographic tools including commitments and zero-knowledge SNARKs, and satisfies the properties of indelibility (i.e., no back-dating), perfect data secrecy, public auditability of secret data with secret laws, accountable deletion, and succinctness. We also propose a variant scheme where entities can be required to pay fees based on record contents (e.g., for violating regulations) while still preserving data secrecy. Our scheme can be directly instantiated on the Ethereum blockchain (and a simplified version with weaker guarantees can be instantiated with Bitcoin).

In response to upcoming performance and security challenges of anonymity networks like Tor, it will be of crucial importance to be able to develop and deploy performance improvements and state-of-the-art countermeasures. In this paper, we therefore explore different deployment strategies and review their applicability to the Tor network. In particular, we consider flag day, dual stack, translation, and tunneling strategies and discuss their impact on the network, as well as common risks associated with each of them. In a simulation based evaluation, which stems on historical data of Tor, we show that they can practically be applied to realize significant protocol changes in Tor. However, our results also indicate that during the transitional phase a certain degradation of anonymity is unavoidable with current viable deployment strategies.

We introduce a new concept called brokered delegation. Brokered delegation allows users to flexibly delegate credentials and rights for a range of service providers to other users and third parties. We explore how brokered delegation can be implemented using novel trusted execution environments (TEEs). We introduce a system called DelegaTEE that enables users (Delegatees) to log into different online services using the credentials of other users (Owners). Credentials in DelegaTEE are never revealed to Delegatees and Owners can restrict access to their accounts using a range of rich, contextually dependent delegation policies. DelegaTEE fundamentally shifts existing access control models for centralized online services. It does so by using TEEs to permit access delegation at the user's discretion. DelegaTEE thus effectively reduces mandatory access control (MAC) in this context to discretionary access control (DAC). The system demonstrates the significant potential for TEEs to create new forms of resource sharing around online services without the direct support from those services. We present a full implementation of DelegaTEE using Intel SGX and demonstrate its use in four real-world applications: email access (SMTP/IMAP), restricted website access using a HTTPS proxy, e-banking/credit card, and a third-party payment system (PayPal).

Zerocoin (Miers et. al, IEEE S&P’13), designed as an extension to Bitcoin and similar cryptocurrencies, was the first anonymous cryptocurrency proposal which supports large anonymity sets. We identify a cryptographic denial-of-spending attack on the original Zerocoin protocol and a second Zerocoin protocol (Groth and Kohlweiss, EUROCRYPT’15), which enables a network attacker to destroy money of honest users. The attack leads to real-world vulnerabilities in multiple cryptocurrencies, which rely on implementations of the original Zerocoin protocol. The existence of the attack does not contradict the formal security analyses of the two Zerocoin protocols but exposes the lack of an important missing property in the security model of Zerocoin. While the security definitions model that the attacker should not be able to create money out of thin air or steal money from honest users, it does not model that the attacker cannot destroy money of honest users. Fortunately, there are simple fixes for the security model and for both protocols.

We present Strain, a new auction protocol running on top of blockchains and guaranteeing bid confidentiality against fully-malicious parties. As our goal is efficiency and low blockchain latency, we abstain from using traditional, highly interactive MPC primitives such as secret shares. We focus on a slightly weaker adversary model than MPC which allows Strain to achieve constant latency in both the number of parties and the bid length. The main idea behind Strain is a new maliciously-secure two-party comparison mechanism executed between any pair of bids in parallel. Using zero-knowledge proofs, Strain broadcasts the outcome of comparisons on the blockchain in a way that all parties can verify each outcome. Strain's latency is not only asymptotically optimal, but also efficient in practice, requiring a total of just 4 blocks of the underlying blockchain. Strain provides typical auction security requirements such as non-retractable bids against fully-malicious adversaries.

The Internet of Things (IoT) has become a reality: small connected devices feature in everyday objects including childrens' toys, TVs, fridges, heating control units, etc. Supply chains feature sensors throughout, and significant investments go into researching next-generation healthcare, where sensors monitor wellbeing. A future in which sensors and other (small) devices interact to create sophisticated applications seems just around the corner. All of these applications have a fundamental need for security and privacy and thus cryptography is deployed as part of an attempt to secure them. In this paper we explore a particular type of flaw, namely side channel information, on the protocol level that can exist despite the use of cryptography. Our research investigates the potential for utilising packet length and timing information (both are easily obtained) to extract interesting information from a system. We find that using these side channels we can distinguish between devices, different programs running on the same device including which sensor is accessed. We also find it is possible to distinguish between different types of ICMP messages despite the use of encryption. Based on our findings, we provide a set of recommendations to efficiently mitigate these side channels in the IoT context.

State channels are a leading approach for improving the scalability of blockchains and cryptocurrencies. They allow a group of distrustful parties to optimistically execute an application-defined program amongst themselves, while the blockchain serves as a backstop in case of a dispute or abort. This effectively bypasses the congestion, fees and performance constraints of the underlying blockchain in the typical case. However, state channels introduce a new and undesirable assumption that a party must remain on-line and synchronised with the blockchain at all times to defend against execution fork attacks. An execution fork can revert a state channel’s history, potentially causing financial damage to a party that is innocent except for having crashed. To provide security even to parties that may go off-line for an extended period of time, we present Pisa, a protocol enables such parties to delegate to a third party, called the custodian, to cancel execution forks on their behalf. To evaluate Pisa, we provide a proof-of-concept implementation for a simplified Sprites and we demonstrate that it is cost-efficient to deploy on the Ethereum network.

We present three smart contracts that allow a briber to fairly exchange bribes to miners who pursue a mining strategy benefiting the briber. The first contract, CensorshipCon, highlights that Ethereum’s uncle block reward policy can directly subsidise the cost of bribing miners. The second contract, HistoryRevisionCon, rewards miners via an in-band payment for reversing transactions or enforcing a new state of another contract. The third contract, GoldfingerCon, rewards miners in one cryptocurrency for reducing the utility of another cryptocurrency. This work is motivated by the need to understand the extent to which smart contracts can impact the incentive mechanisms involved in Nakamoto-style consensus protocols.

Deep Learning (DL) models have caused a paradigm shift in our ability to comprehend raw data in various important fields, ranging from intelligence warfare and healthcare to autonomous transportation and automated manufacturing. A practical concern, in the rush to adopt DL models as a service, is protecting the models against Intellectual Property (IP) infringement. The DL models are commonly built by allocating significant computational resources that process vast amounts of proprietary training data. The resulting models are therefore considered to be the IP of the model builder and need to be protected to preserve the owner's competitive advantage. This paper proposes DeepSigns, a novel end-to-end IP protection framework that enables insertion of coherent digital watermarks in contemporary DL models. DeepSigns, for the first time, introduces a generic watermarking methodology that can be used for protecting DL owner's IP rights in both white-box and black-box settings, where the adversary may or may not have the knowledge of the model internals. The suggested methodology is based on embedding the owner's signature (watermark) in the probability density function (pdf) of the data abstraction obtained in different layers of a DL model. DeepSigns can demonstrably withstand various removal and transformation attacks, including model compression, model fine-tuning, and watermark overwriting. Proof-of-concept evaluations on MNIST, and CIFAR10 datasets, as well as a wide variety of neural network architectures including Wide Residual Networks, Convolution Neural Networks, and Multi-Layer Perceptrons corroborate DeepSigns' effectiveness and applicability.

Over the past few years, the increased affordability of genome sequencing and the ensuing availability of genetic data have propelled important progress in precision medicine and enabled a market for personal genomic testing. This yields exciting new opportunities for faster and more accurate diagnosis, personalized treatments, and genetically tailored wellness plans. At the same time, however, it also creates important security and privacy threats. In this paper, we present a new cryptographic protocol, PAPEETE (Private, Authorized, fast PErsonal gEnomic TEsting) suitable for running different types of tests on users' genetic data--specifically, SNPs. The protocol, which builds on additively homomorphic encryption, provides privacy for both users and test facilities, and it guarantees that the test is authorized by an appropriate authority like the FDA. Finally, we present a prototype implementation of PAPEETE, and an experimental evaluation that attests to the real-world practicality of our techniques.

By representing data in a unary way, the identity of the bits can be used as a printing pad to stain the data with the identity of its handlers. Passing data will identify its custodians, its pathway, and its bona fide. This technique will allow databases to recover from a massive breach as the thieves will be caught when trying to use this 'sticky data'. Heavily traveled data on networks will accumulate the 'fingerprints' of its holders, to allow for a forensic analysis of fraud attempts, or data abuse. Special applications for the financial industry, and for intellectual property management. Fingerprinting data may be used for new ways to balance between privacy concerns and public statistical interests. This technique might restore the identification power of the US Social Security Number, despite the fact that millions of them have been compromised. Another specific application regards credit card fraud. Once the credit card numbers are 'sticky' they are safe. The most prolific application though, may be in conjunction with digital money technology. The BitMint protocol, for example, establishes its superior security on 'sticky digital coins'. Advanced fingerprinting applications require high quality randomization. The price paid for the fingerprinting advantage is a larger data footprint -- more bits per content. Impacting both storage and transmission. This price is reasonable relative to the gained benefit.

In [1], an abstract accounting model for UTXO-based cryptocurrencies has been presented. However, that model considered only the simplest kind of transaction (known in Bitcoin as pay-to-pubkey-hash) and also abstracted away all aspects related to authorization. This paper extends that model to the general case where the transaction contains validator (a.k.a. scriptPubKey) scripts and redeemer (a.k.a. scriptSig) scripts, which together determine whether the transac- tion’s fund transfers have been authorized.

One of the tasks in the $2017$ iDASH secure genome analysis competition was to enable training of logistic regression models over encrypted genomic data. More precisely, given a list of approximately $1500$ patient records, each with $18$ binary features containing information on specific mutations, the idea was for the data holder to encrypt the records using homomorphic encryption, and send them to an untrusted cloud for storage. The cloud could then apply a training algorithm on the encrypted data to obtain an encrypted logistic regression model, which can be sent to the data holder for decryption. In this way, the data holder could successfully outsource the training process without revealing either her sensitive data, or the trained model, to the cloud. Our solution to this problem has several novelties: we use a multi-bit plaintext space in fully homomorphic encryption together with fixed point number encoding; we combine bootstrapping in fully homomorphic encryption with a scaling operation in fixed point arithmetic; we use a minimax polynomial approximation to the sigmoid function and the $1$-bit gradient descent method to reduce the plaintext growth in the training process. As a result, our training over encrypted data takes $0.4$ -- $3.2$ hours per iteration of gradient descent.

Distance bounding (DB) protocols allow a prover to convince a verifier that they are within a distance bound. A public key distance bounding relies on the public key of the users to prove their identity and proximity claim. There has been a number of approaches in the literature to formalize security of public key distance bounding protocols. In this paper we extend an earlier work that formalizes security of public key DB protocols using an approach that is inspired by the security definition of identification protocols, and is referred to it as distance-bounding identification (DBID). We first show that if protocol participants have access to a directional antenna, many existing protocols that have been proven secure, will become insecure, and then show to revise the previous model to include this new capability of the users. DBID approach provides a natural way of modeling man-in-the-middle attack in line with identification protocols, as well as other attacks that are commonly considered in distance bounding protocols. We propose a new DBID scheme, called Poxy, with security proof. We compare the existing public key DB models, and prove the security of the scheme known as ProProx, in our model.

QUIC is a secure transport protocol developed by Google and implemented in Chrome in 2013, currently representing one of the most promising solutions to decreasing latency while intending to provide security properties similar with TLS. In this work we shed some light on QUIC's strengths and weaknesses in terms of its provable security and performance guarantees in the presence of attackers. We first introduce a security model for analyzing performance-driven protocols like QUIC and prove that QUIC satisfies our definition under reasonable assumptions on the protocol's building blocks. However, we find that QUIC does not satisfy the traditional notion of forward secrecy that is provided by some modes of TLS, e.g., TLS-DHE. Our analyses also reveal that with simple bit-flipping and replay attacks on some public parameters exchanged during the handshake, an adversary could easily prevent QUIC from achieving minimal latency advantages either by having it fall back to TCP or by causing the client and server to have an inconsistent view of their handshake leading to a failure to complete the connection. We have implemented these attacks and demonstrated that they are practical. Our results suggest that QUIC's security weaknesses are introduced by the very mechanisms used to reduce latency, which highlights the seemingly inherent trade off between minimizing latency and providing `good' security guarantees.

Blockchains have become a buzzword and many blockchain proponents believe that smart contract is a panacea to redefine the digital economy. The community has a misconception that any kind of contracts could be implemented as a blockchain smart contract. There is no doubt that Turing-complete scripting languages in blockchain techniques such as Ethereum can be used to draft many important smart contracts. However, digital economy is much more than Turing-complete smart contracts. Many protocols/contracts in our daily life could not be implemented using Turing- complete smart contracts. As an example, we formulate an Obama-Trump contract and show that this kind of contract could not be implemented using blockchain smart contract techniques. It is straightforward to observe that many contracts in our daily life could be described in terms of an Obama-Trump contract. As a background discussion, we also give a comprehensive review of historical cryptographic currency techniques, bitcoin smart contract techniques, and Turing-complete smart contract techniques in modern blockchains.

We consider reputation systems in the Universal Composability Framework where users can anonymously rate each others products that they purchased previously. To obtain trustworthy, reliable, and honest ratings, users are allowed to rate products only once. Everybody is able to detect users that rate products multiple times. In this paper we present an ideal functionality for such reputation systems and give an efficient realization that is usable in practical applications.

This paper proposes DeepMarks, a novel end-to-end framework for systematic fingerprinting in the context of Deep Learning (DL). Remarkable progress has been made in the area of deep learning. Sharing the trained DL models has become a trend that is ubiquitous in various fields ranging from biomedical diagnosis to stock prediction. As the availability and popularity of pre-trained models are increasing, it is critical to protect the Intellectual Property (IP) of the model owner. DeepMarks introduces the first fingerprinting methodology that enables the model owner to embed unique fingerprints within the parameters (weights) of her model and later identify undesired usages of her distributed models. The proposed framework embeds the fingerprints in the Probability Density Function (pdf) of trainable weights by leveraging the extra capacity available in contemporary DL models. DeepMarks is robust against fingerprints collusion as well as network transformation attacks, including model compression and model fine-tuning. Extensive proof-ofconcept evaluations on MNIST and CIFAR10 datasets, as well as a wide variety of deep neural networks architectures such as Convolutional Neural Networks (CNNs) and Wide Residual Networks (WRNs), corroborate the effectiveness and robustness of DeepMarks framework

A public blockchain is proposed in an attempt to enable the coin holders to participate in verifying mathematical theorems for public access. Incentives are designed to encourage any party to contribute their knowledge by buying tokens of mathematical propositions that they believe are true. The proposed blockchain is a platform for people to exchange their belief in mathematical propositions. An implementation of this blockchain proposal, once established, will provide the general public with an easy and instant access to reliable knowledge without having to read difficult proofs or having to blindly trust a small number of experts. Conversely, experts from various fields may find it much easier for making their work appreciated by more people, leading to a better impact. According to the incentive inherently provided by the blockchain, they can even earn significantly if they do prove some theorems that were not previously known by the blockchain. Foundations who are interested in the validity of a particular proposition not yet explicitly recorded on the blockchain can donate a fund, which will distribute to experts who contribute positive efforts toward solving the specified problems. Only the people who erroneously create or buy tokens of a proposition that is eventually proven false will lose money. A reference design of the proposed blockchain that attempts to achieve the above-mentioned goal is described and reasoned.

Geosocial applications collect (and record) users’ precise location data to perform proximity computations, such as notifying a user or triggering a service when a friend is within geographic proximity. With the growing popularity of mobile devices that have sophisticated localization capability, it becomes more convenient and tempting to share location data. But the precise location data in plaintext not only exposes user’s whereabouts but also mobility pa erns that are sensitive and cannot be changed easily. This paper proposes cryptographic protocols on top of spatial cloaking to reduce the resolution of location and balance between data utility and privacy. Specifically, we interest in the setting that allows users to send periodic updates of precise coordinates and define privacy preferences to control the granularity of the location, both in an encrypted format. Our system supports three kinds of user queries — “Where is this user?”, “Who is nearby?”, and “How close is this user from another user?”. Also, we develop a new algorithm to improve the multidimensional data access by reducing significant masking error. Our prototype and various performance evaluations on different platforms demonstrated that our system is practical.

Establishing friendship relationships on Facebook often entails information sharing which is based on the social trust and implicit contract between users and their friends. In this context, Facebook offers applications (Apps) developed by third-party application providers (AppPs), which may grant access to users' personal data via Apps installed by their friends. Such access takes place outside the circle of social trust with the user not being aware whether a friend has installed an App collecting her data. In some cases, one or more AppPs may cluster several Apps and thus gain access to a collection of personal data. As a consequence privacy risks emerge. Previous research has mentioned the need to quantify privacy risks on Online Social Networks (OSNs). Nevertheless, most of the existing works do not focus on the personal data disclosure via Apps. Moreover, the problem of personal data clustering from AppPs has not been studied. In this work, we perform a general analysis of the privacy threats stemming from the personal data requested by Apps installed by the user’s friends from a technical and legal point of view. In order to assist users, we propose a model and a privacy scoring formula to calculate the amount of personal data that may be exposed to AppPs. Moreover, we propose algorithms that based on clustering, computes the visibility of each personal data to the AppPs.

In this paper we propose a rank based algorithm for sorting encrypted data using monomials. Greedy Sort is a sorting technique that achieves to minimize the depth of the homomorphic evaluations. It is a costly algorithm due to excessive ciphertext multiplications and its implementation is cumbersome. Another method Direct Sort has a slightly deeper circuit than Greedy Sort, nevertheless it is simpler to implement and scales better with the size of the input array. Our proposed method minimizes both the circuit depth and the number of ciphertext multiplications. In addition to its performance, its simple design makes it more favorable compared to the alternative methods which are hard to parallelize, e.g. not suitable for fast GPU implementations. Furthermore, we improve the performance of homomorphic sorting algorithm by adapting the SIMD operations alongside message slot rotation techniques. This method allow us to pack $N$ integers into a single ciphertext and compute $N$ comparisons at once, thus reducing $\mathcal{O}(N^2)$ comparisons to $\mathcal{O}(N)$.

Cryptocurrencies are historically divided in two broad groups with respect to the style of transactions that they accept. In the account-based style, each address is seen as an account with a balance, and transactions are transfers of value from one account to another. In the UTXO-based style, transactions inductively spend outputs generated by previous trans- actions and create new unspent outputs, and there is no intrinsic notion of account associated with an address. Each style has advantages and disadvantages. This paper formally defines: the two styles; translations that allow to simulate one style by the other; new transaction types that allow both styles of transactions to co-exist on the same ledger; and a new transaction type that combines features from both styles.

Security concerns have been raised since big data became a prominent tool in data analysis. For instance, many machine learning algorithms aim to generate prediction models using training data which contain sensitive information about individuals. Cryptography community is considering secure computation as a solution for privacy protection. In particular, practical requirements have triggered research on the efficiency of cryptographic primitives. This paper presents a practical method to train a logistic regression model while preserving the data confidentiality. We apply the homomorphic encryption scheme of Cheon et al. (ASIACRYPT 2017) for an efficient arithmetic over real numbers, and devise a new encoding method to reduce storage of encrypted database. In addition, we adapt Nesterov's accelerated gradient method to reduce the number of iterations as well as the computational cost while maintaining the quality of an output classifier. Our method shows a state-of-the-art performance of homomorphic encryption system in a real-world application. The submission based on this work was selected as the best solution of Track 3 at iDASH privacy and security competition 2017. For example, it took about six minutes to obtain a logistic regression model given the dataset consisting of 1579 samples, each of which has 18 features with a binary outcome variable.

Secure search is the problem of securely retrieving from a database table (or any unsorted array) the records matching specified attributes, as in SQL ``SELECT...WHERE...'' queries, but where the database and the query are encrypted. Secure search has been the leading example for practical applications of Fully Homomorphic Encryption (FHE) since Gentry's seminal work in 2009, attaining the desired properties of a single-round low-communication protocol with semantic security for database and query (even during search). Nevertheless, the wide belief was that the high computational overhead of current FHE candidates is too prohibitive in practice for secure search solutions (except for the restricted case of searching for a uniquely identified record as in SQL UNIQUE constrain and Private Information Retrieval). This is due to the high degree in existing solutions that is proportional at least to the number of database records m. We present the first algorithm for secure search that is realized by a polynomial of logarithmic degree (log m)^c for a small constant c>0. We implemented our algorithm in an open source library based on HElib, and ran experiments on Amazon's EC2 cloud with up to 100 processors. Our experiments show that we can securely search to retrieve database records in a rate of searching in millions of database records in less than an hour on a single machine. We achieve our result by: (1) Designing a novel sketch that returns the first strictly-positive entry in a (not necessarily sparse) array of non-negative real numbers; this sketch may be of independent interest. (2) Suggesting a multi-ring evaluation of FHE -- instead of a single ring as in prior works -- and leveraging this to achieve an exponential reduction in the degree.

Mounting deanonymization attacks on the unreachable Bitcoin nodes -- these nodes do not accept incoming connections -- residing behind the NAT is a challenging task. Such an attack was first given by Biryukov, Khovratovich and Pustogarov based on their observation that a node can be uniquely identified in a single session by their directly-connected neighbouring nodes (ACM CCS'15). However, the BKP15 attack is less effective across multiple sessions. To address this issue, Biryukov and Pustogarov later on devised a new strategy exploiting certain properties of address-cookies (IEEE S&P'15). Unfortunately, the BP15 attack is also rendered ineffective by the present modification to the Bitcoin client. In this paper, we devise an efficient method to link the sessions of unreachable nodes, even if they connect to the Bitcoin network over the Tor. We achieve this using a new approach based on organizing the block-requests made by the nodes in a Bitcoin session graph. This attack also works against the modified Bitcoin client. We performed experiments on the Bitcoin main network, and were able to link consecutive sessions with a precision of 0.90 and a recall of 0.71. We also provide counter-measures to mitigate the attacks.

Distributed ledgers (e.g. blockchains) enable financial institutions to efficiently reconcile cross-organization transactions. For example, banks might use a distributed ledger as a settlement log for digital assets. Unfortunately, these ledgers are either entirely public to all participants, revealing sensitive strategy and trading information, or are private but do not support third-party auditing without revealing the contents of transactions to the auditor. Auditing and financial oversight are critical to proving institutions are complying with regulation. This paper presents zkLedger, the first system to protect ledger participants' privacy and provide fast, provably correct auditing. Banks create digital asset transactions that are visible only to the organizations party to the transaction, but are publicly verifiable. An auditor sends queries to banks, for example "What is the outstanding amount of a certain digital asset on your balance sheet?" and gets a response and cryptographic assurance that the response is correct. zkLedger has two important benefits over previous work. First, zkLedger provides fast, rich auditing with a new proof scheme using Schnorr-type non-interactive zero-knowledge proofs. Unlike zkSNARKs, our techniques do not require trusted setup and only rely on widely-used cryptographic assumptions. Second, zkLedger provides *completeness*; it uses a columnar ledger construction so that banks cannot hide transactions from the auditor, and participants can use rolling caches to produce and verify answers quickly. We implement a distributed version of zkLedger that can produce provably-correct answers to auditor queries on a ledger with a hundred thousand transactions in less than 10 milliseconds.

We present eclipse attacks on Ethereum nodes that exploit the peer-to-peer network used for neighbor discovery. Our attacks can be launched using only two hosts, each with a single IP address. Our eclipse attacker monopolizes all of the victim's incoming and outgoing connections, thus isolating the victim from the rest of its peers in the network. The attacker can then filter the victim's view of the blockchain, or co-opt the victim's computing power as part of more sophisticated attacks. We argue that these eclipse-attack vulnerabilities result from Ethereum's adoption of the Kademlia peer-to-peer protocol, and present countermeasures that both harden the network against eclipse attacks and cause it to behave differently from the traditional Kademlia protocol. Several of our countermeasures have been incorporated in the Ethereum geth 1.8 client released on February 14, 2018.

In this paper, we propose P2KMV, a novel privacy-preserving counting sketch, based on the k minimum values algorithm. With P2KMV, we offer a versatile privacy-enhanced technology for obtaining statistics, following the principle of data minimization, and aiming for the sweet spot between privacy, accuracy, and computational efficiency. As our main contribution, we develop methods to perform set operations, which facilitate cardinality estimates under strong privacy requirements. Most notably, we propose an efficient, privacy-preserving algorithm to estimate the set intersection cardinality. P2KMV provides plausible deniability for all data items contained in the sketch. We discuss the algorithm's privacy guarantees as well as the accuracy of the obtained estimates. An experimental evaluation confirms our analytical expectations and provides insights regarding parameter choices.

Hardware manipulations pose a serious threat to numerous systems, ranging from a myriad of smart-X devices to military systems. In many attack scenarios an adversary merely has access to the low-level, potentially obfuscated gate-level netlist. In general, the attacker possesses minimal information and faces the costly and time-consuming task of reverse engineering the design to identify security-critical circuitry, followed by the insertion of a meaningful hardware Trojan. These challenges have been considered only in passing by the research community. The contribution of this work is threefold: First, we present HAL, a comprehensive reverse engineering and manipulation framework for gate-level netlists. HAL allows automating defensive design analysis (e.g., including arbitrary Trojan detection algorithms with minimal effort) as well as offensive reverse engineering and targeted logic insertion. Second, we present a novel static analysis Trojan detection technique ANGEL which considerably reduces the false-positive detection rate of the detection technique FANCI. Furthermore, we demonstrate that ANGEL is capable of automatically detecting Trojans obfuscated with DeTrust. Third, we demonstrate how a malicious party can semi-automatically inject hardware Trojans into third-party designs. We present reverse engineering algorithms to disarm and trick cryptographic self-tests, and subtly leak cryptographic keys without any a priori knowledge of the design’s internal workings.

This paper presents Hermes – a practical data security scheme with a reference implementation, which enables distributed sharing and collaboration, enforcing access control with the help of cryptographic methods (public key cryptography and traditional symmetric cryptography).

Secure instant messaging is utilized in two variants: one-to-one communication and group communication. While the first variant has received much attention lately (Frosch et al., EuroS&P16; Cohn-Gordon et al., EuroS&P17; Kobeissi et al., EuroS&P17), little is known about the cryptographic mechanisms and security guarantees of secure group communication in instant messaging. To approach an investigation of group instant messaging protocols, we first provide a comprehensive and realistic security model. This model combines security and reliability goals from various related literature to capture relevant properties for communication in dynamic groups. Thereby the definitions consider their satisfiability with respect to the instant delivery of messages. To show its applicability, we analyze three widely used real-world protocols: Signal, WhatsApp, and Threema. Since these protocols and their implementations are mostly undocumented for the public and two out of three applications among them are closed source, we describe the group protocols employed in Signal, WhatsApp, and Threema. By applying our model, we reveal several shortcomings with respect to the security definition. Therefore we propose generic countermeasures to enhance the protocols regarding the required security and reliability goals. Our systematic analysis reveals that (1) the communications' integrity – represented by the integrity of all exchanged messages – and(2) the groups' closeness – represented by the members' ability of managing the group – are not end-to-end protected. We additionally show that strong security properties, such as Future Secrecy which is a core part of the one-to-one communication in the Signal protocol, do not hold for its group communication.

Various safety-critical devices, such as industrial control systems, medical devices, and home automation systems, are configured through web interfaces from remote hosts that are standard PCs. The communication link from the host to the safety-critical device is typically easy to protect, but if the host gets compromised, the adversary can manipulate any user-provided configuration settings with severe consequences including safety violations. In this paper, we propose IntegriKey, a novel system for user input integrity protection in compromised host. The user installs a simple plug-and-play device between the input peripheral and the host. This device observes user input events and sends a trace of them to the server that compares the trace to the application payload received from the untrusted host. To prevent subtle attacks where the adversary exchanges values from interchangeable input fields, we propose a labeling scheme where the user annotates input values. We built a prototype of IntegriKey, using an embedded USB bridge, and our experiments show that such integrity protection adds only minor delay. We also developed a UI analysis tool that helps developers to protect their services and evaluated it on commercial safety-critical systems.

In the past years, the security of Bitcoin-like protocols has been intensively studied. However, previous investigations are mainly focused on the single-mode version of Bitcoin protocol, where the protocol is running among full nodes (miners). In this paper, we initiate the study of multi-mode cryptocurrency protocols. We generalize the recent framework by Garay et al. (Eurocrypt 2015) with new security definitions that capture the security of realistic cryptocurrency systems (e.g. Bitcoin with full and lightweight nodes). We provide the first rigorous security model for addressing the "blockchain bloat" issue. As an immediate application of our new framework, we analyze the security of existing blockchain pruning proposals for Bitcoin aiming to improve the storage efficiency of network nodes by pruning unnecessary information from the ledger.

Generally ciphers project a fixed measure of security, defined by the com- plexity of their algorithms. Alas, threat is variable, and should be met with matching security. It is useless to project insu cient security, and it is wasteful and burden- some to over-secure data. BitFlip comes with threat-adjustable flexibility, established via: (i) smart decoy strategy, (ii) parallel encryption, (iii) uniform letter frequency adjustment – tools which enable the BitFlip user to (a) adjust its ciphertexts to match the appraised threat, and (b) sustain security levels for aging keys. The use of these threat-adjusting tools may be automated to allow (1) AI engines to enhance the security service of the cipher, and (2) to enable remote hard-to-access IoT devices to keep aging keys useful, and preserve precious energy by matching security to the ad-hoc threat level. BitFlip may also be operated in a zero-leakage mode where no attributes of a conversation are disclosed, up to full steganographic levels. BitFlip se- curity is two-dimensional: intractability and equivocation, both may be conveniently increased to meet quantum cryptanalytic attacks.

Bitcoin relies on the Unspent Transaction Outputs (UTXO) set to efficiently verify new generated transactions. Every unspent out- put, no matter its type, age, value or length is stored in every full node. In this paper we introduce a tool to study and analyze the UTXO set, along with a detailed description of the set format and functionality. Our analysis includes a general view of the set and quantifies the difference between the two existing formats up to the date. We also provide an ac- curate analysis of the volume of dust and unprofitable outputs included in the set, the distribution of the block height in which the outputs where included, and the use of non-standard outputs.

This paper is devoted to the study of transaction fees in massively replicated open blockchain systems. In such systems, like Bitcoin, a snapshot of current state required for the validation of transactions is being held in the memory, which eventually becomes a scarce resource. Uncontrolled state growth can lead to security issues. We propose a modification of a transaction fee scheme based on how much additional space will be needed for the objects created as a result of transaction processing and for how long will they live in the state. We also work out the way to combine fees charged for different resources spent (bandwidth, random-access state memory, processor cycles) in a composite fee and demonstrate consistency of the approach by analyzing the statistics from Ethereum network. We show a possible implementation for state-related fee in a form of regular payments to miners.

The distinguishing feature of the Internet of Things is that many devices get interconnected. The threat of side-channel attacks in this setting is less understood than the threat of traditional network and software exploitation attacks that are perceived to be more powerful. This work is a case study of Thread, an emerging network and transport level stack designed to facilitate secure communication between heterogeneous IoT devices. We perform the first side-channel vulnerability analysis of the Thread networking stack. We leverage various network mechanisms to trigger manipulations of the security material or to get access to the network credentials. We choose the most feasible attack vector to build a complete attack that combines network specific mechanisms and Differential Electromagnetic Analysis. When successfully applied on a Thread network, the attack gives full network access to the adversary. We evaluate the feasibility of our attack in a TI CC2538 setup running OpenThread, a certified open-source implementation of the stack. The full attack does not succeed in our setting. The root cause for this failure is not any particular security feature of the protocol or the implementation, but a side-effect of a feature not related to security. We summarize the problems that we find in the protocol with respect to side-channel analysis, and suggest a range of countermeasures to prevent our attack and the other attack vectors we identified during the vulnerability analysis. In general, we demonstrate that elaborate security mechanisms of Thread make a side-channel attack not trivial to mount. Similar to a modern software exploit, it requires chaining multiple vulnerabilities. Nevertheless, such attacks are feasible. Being perhaps too expensive for settings like smart homes, they pose a relatively higher threat to the commercial setting. We believe our experience provides a useful lesson to designers of IoT protocols and devices.

We proposed a zero-contention in cache lines a cache policy between REE and TEE to prevent from TruSpy attacks in a kernel memory of an embedded system. We suggested that delay time of data path of REE is equal or similar to that of data path of TEE to prevent timing side-channel attacks.

A growing body of research on Bitcoin and other permissionless cryptocurrencies that utilize Nakamoto's blockchain has shown that they do not easily scale to process a high throughput of transactions, or to quickly approve individual transactions; blocks must be kept small, and their creation rates must be kept low in order to allow nodes to reach consensus securely. As of today, Bitcoin processes a mere 3-7 transactions per second, and transaction confirmation takes at least several minutes. We present SPECTRE, a new protocol for the consensus core of cryptocurrencies that remains secure even under high throughput and fast confirmation times. At any throughput, SPECTRE is resilient to attackers with up to 50\% of the computational power (up until the limit defined by network congestion and bandwidth constraints). SPECTRE can operate at high block creation rates, which implies that its transactions confirm in mere seconds (limited mostly by the round-trip-time in the network). Key to SPECTRE's achievements is the fact that it satisfies weaker properties than classic consensus requires. In the conventional paradigm, the order between any two transactions must be decided and agreed upon by all non-corrupt nodes. In contrast, SPECTRE only satisfies this with respect to transactions performed by honest users. We observe that in the context of money, two conflicting payments that are published concurrently could only have been created by a dishonest user, hence we can afford to delay the acceptance of such transactions without harming the usability of the system. Our framework formalizes this weaker set of requirements for a cryptocurrency's distributed ledger. We then provide a formal proof that SPECTRE satisfies these requirements.

Searchable symmetric encryption (SSE) enables data owners to conduct searches over encrypted data stored by an untrusted server, retrieving only those encrypted files that match the search queries. Several recent schemes employ a server-side encrypted index in the form of a search tree where each node stores a bit vector denoting for each keyword whether any file in its subtree contains that keyword. Our work is motivated by the observation that the way data is distributed in such a search tree has a big impact on the cost of searches. For single-keyword queries, it impacts the number of different paths that must be followed to find all the matching files; for multi-keyword queries, the arrangement of the tree also impacts the number of nodes visited during the search on paths that do not lead to any satisfying data elements. We present three algorithms that improve the performance of SSE schemes based on tree indexes and prove that for cases where the search cost is high, the cost of our algorithms converges to the cost of the optimal tree. In our experiments, the resulting search trees outperform the arbitrary search trees used in previous works by a factor of up to two

This paper presents an independent security review of a popular encrypted cloud storage service (ECS) SpiderOakONE. Contrary to previous work analyzing similar programs, we formally define a minimal security requirements for confidentiality in ECS which takes into account the possibility that the ECS actively turns against its users in an attempt to break the confidentiality of the users' data. Our analysis uncovered several serious issues, which either directly or indirectly damage the confidentiality of a user's files, therefore breaking the claimed Zero- or No-Knowledge property (e.g., the claim that even the ECS itself cannot access the users' data). After responsibly disclosing the issues we found to SpiderOak, most have been fixed.

The standard acceptance policy for a cryptocurrency transaction at most exchanges is to wait until the transaction is placed in the blockchain and followed by a certain number of blocks. However, as noted by Sompolinsky and Zohar, the amount of time for blocks to arrive should also be taken into account as it affects the probability of double spending. Specifically, they propose a dynamic policy for transaction acceptance that depends on both the number of confirmations and the amount of time since transaction broadcast. In this work we study the implications of using such a policy compared with the standard option that ignores block timing information. Using an exact expression for the probability of double spend, via numerical results, we analyze time to transaction acceptance (performance) as well as the time and cost to perform a double spend attack (security). We show that while expected time required for transaction acceptance is improved using a dynamic policy, the time and cost to perform a double spend attack for a particular transaction is reduced.

We explicitly present a homomorphic encryption scheme with a flexible encoding of plaintexts. We prove its security under the LWE assumption, and innovatively show how the scheme can be used to handle computations over both binary strings and real numbers. In addition, using the scheme and its features, we build fast and secure systems of - linear regression using gradient descent, namely finding a reasonable linear relation between data items which remain encrypted. Compared to the best previous work over a simulated dataset of $10^8$ records each with 20 features, our system dramatically reduces the server running time from about 8.75 hours (of the previous work) to only about 10 minutes. - biometric authentication, in which we show how to reduce ciphertext sizes by half and to do the computation at the server very fast, compared with the state-of-the-art. Moreover, as key rotation is a vital task in practice and is recommended by many authorized organizations for key management, - we show how to do key rotation over encrypted data, without any decryption involved, and yet homomorphic properties of ciphertexts remain unchanged. In addition, our method of doing key rotation handles keys of different security levels (e.g., 80- and 128-bit securities), so that the security of ciphertexts and keys in our scheme can be "updated", namely can be changed into a higher security level.

More than ten years ago, a devastating data substitution attack was shown to successfully compromise all previously proposed remote attestation techniques. In fact, the authors went further than simply attacking previously proposed methods: they called into question whether it is theoretically possible for remote attestation methods to exist in face of their attack. Subsequently, it has been shown that it is possible, by relying on self-modifying code. We show that it is possible to create remote attestation that is secure against all data substitution attacks, without relying on self-modifying code. Our proposed method relies on a construction of the checksum process that forces frequent L2 cache overflows if any data substitution attack takes place.

We build a privacy-preserving deep learning system in which many learning participants perform neural network-based deep learning over a combined dataset of all, without actually revealing the participants' local data. To that end, we revisit the previous work by Shokri and Shmatikov (ACM CCS 2015) and point out that local data information may be actually leaked to an honest-but-curious server. We then move on to fix that problem via building an enhanced system with following properties: (1) no information is leaked to the server; and (2) accuracy is kept intact, compared to that of the ordinary deep learning system also over the combined dataset. Our system is a bridge between deep learning and cryptography: we utilise stochastic gradient descent (SGD) applied to neural networks, in combination with additively homomorphic encryption. We show that our usage of encryption adds tolerable overhead to the ordinary deep learning system.

Security and privacy are fundamental objectives characterizing contemporary cloud computing. Despite the wide adoption of encryption for protecting data in transit and at rest, data in use remains unencrypted inside cloud processors and memories, as computation is not applicable on encrypted values. This limitation introduces security risks, as unencrypted values can be leaked through side-channels or hardware Trojans. To address this problem, encrypted architectures have recently been proposed, which leverage homomorphic encryption to natively process encrypted data using datapaths of thousands of bits. In this case, additional security protections are traded for higher performance penalties, which drives the need for more efficient architectures. In this work, we develop benchmarks specifically tailored to encrypted computers, to enable comparisons across different architectures. Our benchmark suite, dubbed TERMinator, is unique as it avoids 'termination problems' that prohibit making control-flow decisions and evaluating early termination conditions based on encrypted data, as these can leak information. Contrary to generic suites that ignore the fundamental challenges of encrypted computation, our algorithms are tailored to the security primitives of the target encrypted architecture, such as the existence of branching oracles. In our experiments, we compiled our benchmarks for the Cryptoleq architecture and evaluated their performance for a range of security parameters.

Remote Attestation (RA) is a popular means of detecting malware presence (or verifying its absence) on embedded and IoT devices. It is especially relevant to low-end devices that are incapable of protecting themselves against infection. Malware that is aware of ongoing or impending attestation and aims to avoid detection can relocate itself during computation of the attestation measurement. In order to thwart such behavior, prior RA techniques are either non-interruptible or explicitly forbid modification of storage during measurement computation. However, since the latter can be a time-consuming task, this curtails availability of device's other (main) functions, which is especially undesirable, or even dangerous, for devices with time- and/or safety-critical missions. In this paper, we propose SMARM, a light-weight technique, based on shuffled measurements, as a defense against roving malware. In SMARM, memory is measured in a randomized and secret order. This does not impact device's availability -- the measurement process can be interrupted, even by malware, which can relocate itself at will. We analyze various malware behaviors and show that, while malware can escape detection in a single attestation instance, it is highly unlikely to avoid eventual detection.

Smart Cities draw a nice picture of a connected city where useful services and data are ubiquitous, energy is properly used and urban infrastructures are well orchestrated. Fulfilling this vision in our cities implies unveiling citizens data and assets. Thus, security and data privacy appear as crucial issues to consider. In this paper, we study a way of offering a secured energy management service for diagnosis and classification of buildings in a district upon their energy efficiency. Our remote service can be beneficial both for local authorities and householders without revealing private data. Our framework is designed such that the private data is permanently encrypted and that the server performing the labeling algorithm has no information about the sensitive data and no capability to decrypt it. The underlying cryptographic technology used is homomorphic encryption, allowing to perform calculations directly on encrypted data. We present here the prototype of a crypto-classification service for energy consumption profiles involving different actors of a smart city community, as well as the associated performances results. We assess our proposal atop of real data taken from an Irish residential district and we show that our service can achieve acceptable performances in terms of security, execution times and memory requirements.

Two post-quantum password-based authenticated key exchange (PAKE) protocols were proposed at CT-RSA 2017. Following this work, we give much more efficient and portable C++ implementation of these two protocols. We also choose more compact parameters providing 200-bit security. Compared with original implementation, we achieve 21.5x and 18.5x speedup for RLWE-PAK and RLWE-PPK respectively. Compare with quantum-vulnerable J-PAKE protocol, we achieve nearly 8x speedup. We also integrate RLWE-PPK into TLS to construct a post-quantum TLS ciphersuite. This allows simpler key management, mutual authentication and resistant to phishing attack. Benchmark shows that our ciphersuite is indeed practical.

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. Although such codes do not exist if the family of "tampering functions" \cF is completely unrestricted, they are known to exist for many broad tampering families \cF. One such natural family is the family of tampering functions in the so called {\em split-state} model. Here the message m is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with L and R {\em individually}. The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes, motivating the question of designing efficient non-malleable codes in this model. Prior to this work, non-malleable codes in the split-state model received considerable attention in the literature, but were either (1) constructed in the random oracle model [DPW10], or (2) relied on advanced cryptographic assumptions (such as non-interactive zero-knowledge proofs and leakage-resilient encryption) [LL12], or (3) could only encode 1-bit messages [DKO13]. As our main result, we build the first efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model. The heart of our construction uses the following new property of the inner-product function <L,R> over the vector space F_p^n (for any prime p and large enough dimension n): if L and R are uniformly random over F_p^n, and f,g: F_p^n \rightarrow F_p^n are two arbitrary functions on L and R, the joint distribution (<L,R>,<f(L),g(R)>) is ``close'' to the convex combination of "affine distributions" {(U,c U+d)| c,d \in F_p}, where U is uniformly random in F_p. In turn, the proof of this surprising property of the inner product function critically relies on some results from additive combinatorics, including the so called {\em Quasi-polynomial Freiman-Ruzsa Theorem} (which was recently established by Sanders [San12] as a step towards resolving the Polynomial Freiman-Ruzsa conjecture [Gre05]).

This work shows that weighted majority voting games occur in cryptocurrencies. In particular, two such games are highlighted. The first game, which we call the Rule Game, pertains to the scenario where the entities in the system engage in a voting procedure to accept or reject a change of rules. The second game, which we call the Attack Game, refers to the scenario where a group of entities in a cryptocurrency system can form a coalition to engage in double spending. For the Rule Game we provide analysis to argue that the Coleman’s preventive power measure is the appropriate tool for measuring a player’s influence in the game while for the Attack Game, we define a notion of stability based on the notion of minimal winning coalitions. For both the Rule Game and the Attack Game, we show how to analyse the games based on a snapshot of real world data for Bitcoin which is presently the most popular of all the cryptocurrencies.

The wisdom of the crowd is a valuable asset in today's society. It is not only important in predicting elections but also plays an essential rôle in marketing and the financial industry. Having a trustworthy source of opinion can make forecasts more accurate and markets predictable. Until now, a fundamental problem of surveys is the lack of incentives for participants to provide accurate information. Classical solutions like small monetary rewards or the chance of winning a prize are often not very attractive and also do not prevent multiple entries or randomly filling in answers. In this work, we present a framework that solves both problems via a customizable incentivization framework. Apart from predicting events, this framework can also be used to govern decentralized autonomous organizations.

The disassembled code of an executable program can be seen as a graph representing the possible sequence of instructions (Control Flow Graph). grap is a YARA-like tool, completely open-source, and able to detect graph patterns, defined by the analyst, within an executable program. We used grap to detect cryptographic algorithms: we created patterns for AES and ChaCha20 that are based on parts of the assembly code produced by compiling popular implementations (available in LibreSSL and libsodium). Our approach is thus based on the algorithms and their structure and does not rely on constant detection.

Efficiently searchable and easily deployable encryption schemes enable an untrusted, legacy service such as a relational database engine to perform searches over encrypted data. The ease with which such schemes can be deployed on top of existing services makes them especially appealing in operational environments where encryption is needed but it is not feasible to replace large infrastructure components like databases or document management systems. Unfortunately all previously known approaches for efficiently searchable encryption are vulnerable to inference attacks where an adversary can use knowledge of the distribution of the data to recover the plaintext with high probability. In this paper, we present the first efficiently searchable, easily deployable database encryption scheme that is provably secure against inference attacks even when used with real, low-entropy data. Ours is also the only efficiently searchable construction that provides any provable security for protecting multiple related attributes (columns) in the same database. Using this ESE construction as a building block, we give an efficient construction for performing range queries over encrypted data. We implemented our constructions in Haskell and used them to query encrypted databases of up to 10 million records. In experiments with a local Postgres database and with a Google Cloud Platform database, the response time for our encrypted queries is not excessively slower than for plaintext queries. With the use of parallel query processing, our encrypted queries can achieve similar and in some cases superior performance to queries on the plaintext.

The advent of Bitcoin paved the way for a plethora of blockchain systems supporting diverse applications beyond cryptocurrencies. Although in-depth studies of the protocols, security, and privacy of blockchains are available, there is no formal model of the transaction semantics that a blockchain is supposed to guarantee. In this work, we fill this gap, motivated by the observation that the semantics of transactions in blockchain systems can be captured by a directed acyclic graph. Such a transaction graph, or TDAG, generally consists of the states and the transactions as transitions between the states, together with conditions for the consistency and validity of transactions. We instantiate the TDAG model for three prominent blockchain systems: Bitcoin, Ethereum, and Hyperledger Fabric. We specify the states and transactions as well as the validity conditions of the TDAG for each one. This demonstrates the applicability of the model and formalizes the transaction-level semantics that these systems aim for.

User convenience and strong security are often at odds, and most security applications need to find some sort of balance between these two (often opposing) goals. The Resource Public Key Infrastructure (RPKI) [8], a security infrastructure built on top of interdomain routing, is not exempt from this issue. The RPKI uses the maxLength attribute to reduce the amount of information that must be explicitly recorded in its cryptographic objects. MaxLength also allows operators to easily reconfigure their networks with- out modifying their RPKI objects. However, we argue that the maxLength attribute strikes the wrong balance between security and user convenience. In particular, we argue that maxLength is commonly configured in a manner that either obviates the security benefis provided by the RPKI or causes legitimate routes to appear invalid, without providing performance improvements. Therefore, we argue that the maxLength attribute should be eliminated from the RPKI.

After the development of practical searchable encryption constructions, allowing for secure searches over an encrypted dataset outsourced to an untrusted server, at the expense of leaking some information to the server, many new attacks have recently been developed, targeting this leakage in order to break the confidentiality of the dataset or of the queries, through leakage abuse attacks. These works helped to understand the importance of considering leakage when analyzing the security of searchable encryption schemes, but did not explain why these attacks were so powerful despite the existence of rigorous security definitions and proofs, or how they could be efficiently and provably mitigated. This work addresses these questions by first proposing an analysis of existing leakage abuse attacks and a way to capture them in new security definitions. These new definitions also help us to devise a way to thwart these attacks and we apply it to the padding of datasets, in order to hide the number of queries’ results, and to provide provable security of some schemes with specific leakage profile against some common classes of leakage abuse attacks. Finally, we give experimental evidence that our countermeasures can be implemented efficiently, and easily applied to existing searchable encryption schemes.

In order to be useful in the real world, efficient cryptographic constructions often reveal, or ``leak,'' more information about their plaintext than one might desire. Up until now, the approach for addressing leakage when proposing a new cryptographic construction has focused entirely on qualifying exactly what information is leaked. Unfortunately there has been no way to predict what the real-world impact of that leakage will be. In this paper, we argue in favor of an analytical approach for quantifying the vulnerability of leaky cryptographic constructions against attacks that use leakage to recover the plaintext or other sensitive information. In contrast to the previous empirical and ad-hoc approach for identifying and assessing such vulnerabilities, analytical techniques can be integrated much earlier in the design lifecycle of a new construction, and the results of the analysis apply much more broadly across many different kinds of data. We applied the proposed framework to evaluate the leakage profiles of five recent constructions for deterministic and order-revealing encryption. Our analysis discovered powerful attacks against every construction that we analyzed, and with only one possible exception, the attack allows the adversary to recover virtually any plaintext with only an exponentially small probability of error. We hope that these results, together with the proposed analytical framework, will help spur the development of new efficient constructions with improved leakage profiles that meaningfully limit the power of leakage abuse attacks in the real world.

Thumbnail preserving encryption (TPE) was suggested by Wright et al. as a way to balance privacy and usability for online image sharing. The idea is to encrypt a plaintext image into a ciphertext image that has roughly the same thumbnail as well as retaining the original image format. At the same time, TPE allows users to take advantage of much of the functionality of online photo management tools, while still providing some level of privacy against the service provider. In this work we present three new approximate TPE encryption schemes. In our schemes, ciphertexts and plaintexts have perceptually similar, but not identical, thumbnails. Our constructions are the first TPE schemes designed to work well with JPEG compression. In addition, we show that they also have provable security guarantees that characterize precisely what information about the plaintext is leaked by the ciphertext image. We empirically evaluate our schemes according to the similarity of plaintext and ciphertext thumbnails, increase in file size under JPEG compression, preservation of perceptual image hashes, among other aspects. We also show how approximate TPE can be an effective tool to thwart inference attacks by machine-learning image classifiers, which have shown to be effective against other image obfuscation techniques.

On-line commercial transactions involve an inherent mistrust between participant parties since, sometimes, no previous relation exists between them. Such mistrust may be a deadlock point in a trade transaction where the buyer does not want to perform the payment until the seller sends the good and the seller does not want to do so until the buyer pays for the purchase. In this paper we present a fair protocol for data trading where the commercial deal, in terms of delivering the data and performing the payment, is atomic since the seller cannot redeem the payment unless the buyer obtains the data and the buyer cannot obtain the data without performing the payment. The protocol is based on Bitcoin scripting language and the fairness of the protocol can be probabilistically enforced.

Password checking systems traditionally allow login only if the correct password is submitted. Recent work on typo-tolerant password checking suggests that usability can be improved, with negligible security loss, by allowing a small number of typographical errors. Existing systems, however, can only correct a handful of errors, such as accidentally leaving caps lock on or incorrect capitalization of the first letter in a password. This leaves out numerous kinds of typos made by users, such as transposition errors, substitutions, or capitalization errors elsewhere in a password. Some users therefore receive no benefit from existing typo-tolerance mechanisms. We introduce personalized typo-tolerant password checking. In our approach, the authentication system learns over time the typos made by a specific user. In experiments using Mechanical Turk, we show that 45% of users would benefit from personalization. We therefore design a system, called TypTop, that securely implements personalized typo-tolerance. Underlying TypTop is a new stateful password-based encryption scheme that can be used to store recent failed login attempts. Our formal analysis shows that security in the face of an attacker that obtains the state of the system reduces to the difficulty of a brute-force dictionary attack against the real password. We implement TypTop for Linux and Mac OS login and report on a proof-of-concept deployment.

Bitcoin is a potentially disruptive new crypto-currency based on a decentralized open-source protocol which is gradually gaining popularity. Perhaps the most important question that will affect Bitcoin's success, is whether or not it will be able to scale to support the high volume of transactions required from a global currency system. We investigate the restrictions on the rate of transaction processing in Bitcoin as a function of both the bandwidth available to nodes and the network delay, both of which lower the efficiency of Bitcoin's transaction processing. The security analysis done by Bitcoin's creator Satoshi Nakamoto~\cite{nakamoto2008bitcoin} assumes that block propagation delays are negligible compared to the time between blocks---an assumption that does not hold when the protocol is required to process transactions at high rates. We improve upon the original analysis and remove this assumption. Using our results, we are able to give bounds on the number of transactions per second the protocol can handle securely. Building on previously published measurements by Decker and Wattenhofer~\cite{Decker2013Information}, we show these bounds are currently more restrictive by an order of magnitude than the bandwidth needed to stream all transactions. We additionally show how currently planned improvements to the protocol, namely the use of transaction hashes in blocks (instead of complete transaction records), will dramatically alleviate these restrictions. Finally, we present an easily implementable modification to the way Bitcoin constructs its main data structure, the blockchain, that immensely improves security from attackers, especially when the network operates at high rates. This improvement allows for further increases in the number of transactions processed per second. We show that with our proposed modification, significant speedups can be gained in confirmation time of transactions as well. The block generation rate can be securely increased to more than one block per second -- a 600 fold speedup compared to today's rate, while still allowing the network to processes many transactions per second.

Privacy for arbitrary encrypted remote computation in the cloud depends on the running code on the server being obfuscated from the standpoint of the operator in the computer room. This paper shows formally as well as practically that that may be arranged on a platform with the appropriate machine code architecture, given the obfuscating compiler described.

The electronic chip of the Estonian ID card is widely used in Estonia to identify the cardholder to a machine. For example, the electronic ID card can be used to collect rewards in customer loyalty programs, authenticate to public printers and self-checkout machines in libraries, and even unlock doors and gain access to restricted areas. This paper studies the security aspects of using the Estonian ID card for this purpose. The paper shows that the way the ID card is currently being used provides little to no assurance to the terminal about the identity of the cardholder. To demonstrate this, an ID card emulator is built, which emulates the electronic chip of the Estonian ID card as much as possible and is able to successfully impersonate the real ID card to the terminals deployed in practice. The exact mechanisms used by the terminals to authenticate the ID card are studied and possible security improvements for the Estonian ID card are discussed.

Scaling the transaction throughput of decentralized blockchain ledgers such as Bitcoin and Ethereum has been an ongoing challenge. Two-party duplex payment channels have been designed and used as building blocks to construct linked payment networks, which allow atomic and trust-free payments between parties without exhausting the resources of the blockchain. Once a payment channel, however, is depleted (e.g., because transactions were mostly unidirectional) the channel would need to be closed and re-funded to allow for new transactions. Users are envisioned to entertain multiple payment channels with different entities, and as such, instead of refunding a channel (which incurs costly on-chain transactions), a user should be able to leverage his existing channels to rebalance a poorly funded channel. To the best of our knowledge, we present the first solution that allows an arbitrary set of users in a payment channel network to securely rebalance their channels, according to the preferences of the channel owners. Except in the case of disputes (similar to conventional payment channels), our solution does not require on-chain transactions and therefore increases the scalability of existing blockchains. In our security analysis, we show that an honest participant cannot lose any of its funds while rebalancing. We finally provide a proof of concept implementation and evaluation for the Ethereum network.

Blockchains and more general distributed ledgers are becoming increasingly popular as efficient, reliable, and persistent records of data and transactions. Unfortunately, they ensure reliability and correctness by making all data public, raising confidentiality concerns that eliminate many potential uses. In this paper we present Solidus, a protocol for confidential transactions on public blockchains, such as those required for asset transfers with on-chain settlement. Solidus operates in a framework based on real-world financial institutions: a modest number of banks each maintain a large number of user accounts. Within this framework, Solidus hides both transaction values and the transaction graph (i.e., the identities of transacting entities) while maintaining the public verifiability that makes blockchains so appealing. To achieve strong confidentiality of this kind, we introduce the concept of a Publicly-Verifiable Oblivious RAM Machine (PVORM). We present a set of formal security definitions for both PVORM and Solidus and show that our constructions are secure. Finally, we implement Solidus and present a set of benchmarks indicating that the system is efficient in practice.

Recent proposals for trusted hardware platforms, such as Intel SGX and the MIT Sanctum processor, offer compelling security features but lack formal guarantees. We introduce a verification methodology based on a trusted abstract platform (TAP) that formally models idealized enclaves and a parameterized adversary. We present machine-checked proofs showing that the TAP satisfies the three key security properties needed for secure remote execution: integrity, confidentiality and secure measurement. We then present machine-checked proofs showing that SGX and Sanctum are refinements of the TAP under certain parameterizations of the adversary, demonstrating that these systems implement secure enclaves for the stated adversary models.

Using dynamic Searchable Symmetric Encryption, a user with limited storage resources can securely outsource a database to an untrusted server, in such a way that the database can still be searched and updated efficiently. For these schemes, it would be desirable that updates do not reveal any information a priori about the modifications they carry out, and that deleted results remain inaccessible to the server a posteriori. If the first property, called forward privacy, has been the main motivation of recent works, the second one, backward privacy, has been overlooked. In this paper, we study for the first time the notion of backward privacy for searchable encryption. After giving formal definitions for different flavors of backward privacy, we present several schemes achieving both forward and backward privacy, with various efficiency trade-offs. Our constructions crucially rely on primitives such as constrained pseudo-random functions and puncturable encryption schemes. Using these advanced cryptographic primitives allows for a fine-grained control of the power of the adversary, preventing her from evaluating functions on selected inputs, or decrypting specific ciphertexts. In turn, this high degree of control allows our SSE constructions to achieve the stronger forms of privacy outlined above. As an example, we present a framework to construct forward-private schemes from range-constrained pseudo-random functions. Finally, we provide experimental results for implementations of our schemes, and study their practical efficiency.

Several access control systems are based on the users’ physical location/proximity to the access point. Distance- Bounding (DB) protocols constitute a classical solution to calculate the distance between a trusted verifier (e.g., an access point) and an untrusted prover (e.g., a pervasive device). The main limitation of DB is that the prover and the verifier need to lie in each other’s communication range. In this paper, we introduce the concept of Multi-Hop Distance-Estimation (MHDE) protocols, which enable a verifier to authenticate a possibly far-away prover and estimate its distance to this prover, when they are not in the communication range of each other, using an ad-hoc network of pervasive devices. More precisely, our contributions are three-fold, since we provide: (1) a formal definition for MHDE; (2) a threat model for MHDE that considers a powerful and distributed adversary; and (3) implementation of MHDE protocols with different settings. Additionally, we demonstrate our protocol to be secure in the considered threat model, and we provide a performance analysis regarding the accuracy of the distance estimation and the tolerance of limited mobility of the nodes. The results are promising in order to adopt MHDE in a distributed setting.

Machine learning algorithms, such as neural networks, create better predictive models when having access to larger datasets. In many domains, such as medicine and &#64257;nance, each institute has only access to limited amounts of data, and creating larger datasets typically requires collaboration. However, there are privacy related constraints on these collaborations for legal, ethical, and competitive reasons. In this work, we present a feasible protocol for learning neural networks in a collaborative way while preserving the privacy of each record. This is achieved by combining Differential Privacy and Secure Multi-Party Computation with Machine Learning.

Logic locking is a technique that's proposed to protect outsourced IC designs from piracy and counterfeiting by untrusted foundries. A locked IC preserves the correct functionality only when a correct key is provided. Recently, the security of logic locking is threatened by a new attack called SAT attack, which can decipher the correct key of most logic locking techniques within a few hours even for a reasonably large key-size. This attack iteratively solves SAT formulas which progressively eliminate the incorrect keys till the circuit is unlocked. In this paper, we present a circuit block (referred to as Anti-SAT block) to enhance the security of existing logic locking techniques against the SAT attack. We show using a mathematical proof that the number of SAT attack iterations to reveal the correct key in a circuit comprising an Anti-SAT block is an exponential function of the key-size thereby making the SAT attack computationally infeasible. Besides, we address the vulnerability of the Anti-SAT block to various removal attacks and investigate obfuscation techniques to prevent these removal attacks. More importantly, we provide a proof showing that these obfuscation techniques for making Anti-SAT un-removable would not weaken the Anti-SAT block's resistance to SAT attack. Through our experiments, we illustrate the effectiveness of our approach to securing modern chips fabricated in untrusted foundries.

Keeping track of financial transactions (e.g., in banks and blockchains) means keeping track of an ever-increasing list of exchanges between accounts. In fact, many of these transactions can be safely “forgotten”, in the sense that purging a set of them that compensate each other does not impact the network’s semantic meaning (e.g., the accounts’ balances). We call nilcatenation a collection of transactions having no effect on a network’s semantics. Such exchanges may be archived and removed, yielding a smaller, but equivalent ledger. Motivated by the computational and analytic benefits obtained from more compact representations of numerical data, we formalize the problem of finding nilcatenations, and propose detection methods based on graph and lattice-reduction techniques. Atop interesting applications of this work (e.g., decoupling of centralized and distributed databases), we also discuss the original idea of a “community-serving proof of work”: finding nilcatenations constitutes a proof of useful work, as the periodic removal of nilcatenations reduces the transactional graph’s size.

We present a certificate access management system to support the USDOT's proposed rule on Vehicle-to-Vehicle (V2V) communications, Federal Motor Vehicle Safety Standard (FMVSS) No.~150. Our proposal, which we call Binary Hash Tree based Certificate Access Management (BCAM) eliminates the need for vehicles to have bidirectional connectivity with the Security Credential Management System (SCMS) for certificate update. BCAM significantly improves the ability of the SCMS to manage large-scale software and/or hardware compromise events. Vehicles are provisioned at the start of their lifetime with all the certificates they will need. However, certificates and corresponding private key reconstruction values are provided to the vehicle encrypted, and the keys to decrypt them are only made available to the vehicles shortly before the start of the validity periods of those certificates. Vehicles that are compromised can be effectively removed from the V2V system by preventing them from decrypting the certificates. We demonstrate that the system is feasible with a broadcast channel for decryption keys and other revocation information, even if that channel has a relatively low capacity.

Intel SGX enclaves provide hardware enforced confidentiality and integrity guarantees for running pure computations (\ie, OS-level side-effect-free code) in the cloud environment. In addition, SGX remote attestation enables enclaves to prove that a claimed enclave is indeed running inside a genuine SGX hardware and not some (adversary controlled) SGX simulator. Since cryptographic protocols do not compose well, especially when run concurrently, SGX remote attestation is only a necessary pre-condition for securely instantiating an enclave. In practice, one needs to analyze all the different interacting enclaves as a \textit{single protocol} and make sure that no sub-computation of the protocol can be simulated outside of the enclave. In this paper we describe protocol design problems under (a) sequential-composition, (b) concurrent-composition, and (c) enclave state malleability that must be taken into account while designing new enclaves. We analyze Intel provided EPID \textsf{Provisioning} and \textsf{Quoting} enclave and report our (largely positive) findings. We also provide details about how SGX uses EPID Group Signatures and report (largely negative) results about claimed anonymity guarantees.

The Bitcoin whitepaper states that security of the system is guaranteed as long as honest miners control more than half of the current total computational power. The whitepaper assumes a static difficulty, thus it is equally hard to solve a cryptographic proof-of-work puzzle for any given moment of the system history. However, the real Bitcoin network is using an adaptive difficulty adjustment mechanism. In this paper we introduce and analyze a new kind of attack on a mining difficulty retargeting function used in Bitcoin. A malicious miner is increasing his mining profits from the attack, named coin-hopping attack, and, as a side effect, an average delay between blocks is increasing. We propose an alternative difficulty adjustment algorithm in order to reduce an incentive to perform coin-hopping, and also to improve stability of inter-block delays. Finally, we evaluate the presented approach and show that the novel algorithm performs better than the original algorithm of Bitcoin.

In distributed storage systems, documents are shared among multiple Cloud providers and stored within their respective storage servers. In social secret sharing-based distributed storage systems, shares of the documents are allocated according to the trustworthiness of the storage servers. This paper proposes a trust mechanism using machine learning techniques to compute evidence-based trust values. Our mechanism mitigates the effect of colluding storage servers. More precisely, it becomes possible to detect unreliable evidence and establish countermeasures in order to discourage the collusion of storage servers. Furthermore, this trust mechanism is applied to the social secret sharing protocol AS$^3$, showing that this new evidence-based trust mechanism enhances the protection of the stored documents.

The polynomials defining the LFSRs of the linux Kernel PRNG are irreducible but not primitive. As a result, the space of numbers generated by these LFSRs does not fill all the space. We propose in this paper more optimal polynomials which increase by a factor of 3 the space of the random numbers generated by these LFSRs. The polynomials used in the current implementation of the PRNG and the point presented here, do not conclude a practical attack on the PRNG.

Distributed storage allows to outsource a document to the cloud such that multiple users can easily access the file. The protection of the document stored relies on secret sharing, which generates and distributes shares of the document to the storage servers. However, the users have to trust that a certain amount of storage servers behaves honestly and do not lose (retrievability) or reveal (confidentiality) the document. To address this so called social secret sharing schemes were developed that allow to adjust the distribution of shares according to the experience made with the involved storage servers. In this work, we provide a framework called AS$^3$ that allows to build social secret sharing schemes based on dynamic secret sharing. The resulting protocol has more freedom in adjusting the parameters of the shares distribution and therefore leads to more efficient and accurate solutions as well as an optimal storage consumption. Furthermore, we provide measures to detect and to prevent that the document is lost or accidentally revealed to individual storage servers. We also demonstrate how to compute trust values for storage servers, how to initialize trust values for newcomers, and provide a proof of concept implementation.

This paper presents TumbleBit, a new unidirectional unlinkable payment hub that is fully compatible with today's Bitcoin protocol. TumbleBit allows parties to make fast, anonymous, off-blockchain payments through an untrusted intermediary called the Tumbler. TumbleBit's anonymity properties are similar to classic Chaumian eCash: no one, not even the Tumbler, can link a payment from its payer to its payee. Every payment made via TumbleBit is backed by bitcoins, and comes with a guarantee that Tumbler can neither violate anonymity, nor steal bitcoins, nor ``print money'' by issuing payments to itself. We prove the security of TumbleBit using the real/ideal world paradigm and the random oracle model. Security follows from the standard RSA assumption and ECDSA unforgeability. We implement TumbleBit, mix payments from 800 users and show that TumbleBit's off-blockchain payments can complete in seconds.

Linear regression is an important statistical tool that models the relationship between some explanatory values and an outcome value using a linear function. In many current applications (e.g. predictive modelling in personalized healthcare), these values represent sensitive data owned by several different parties that are unwilling to share them. In this setting, training a linear regression model becomes challenging and needs specific cryptographic solutions. In this work, we propose a new system that can train a linear regression model with 2-norm regularization (i.e. ridge regression) on a dataset obtained by merging a finite number of private datasets. Our system is composed of two phases: The first one is based on a simple homomorphic encryption scheme and takes care of securely merging the private datasets. The second phase is a new ad-hoc two-party protocol that computes a ridge regression model solving a linear system where all coefficients are encrypted. The efficiency of our system is evaluated both on synthetically generated and real-world datasets.

Since first introduced by Satoshi Nakamoto in 2008, Bitcoin has become the biggest and most well-known decentralized digital currency. Its anonymity allows users all over the world to make transactions with each other and keep their identities hidden. However, protecting private key becomes a very important issue because it is the only access to a unique account and can hardly be recovered if missing. Storing an encrypted backup of private key and its corresponding advanced key is a traditional but effective way, and many other techniques help to make the backup harder to obtain by attackers. While in this paper, we introduce a new backup scheme that can provide protection when an attacker manages to obtain the backup. It is based on Bitcoin system and ECDSA signature scheme. The biggest difference is the generation and recovery of the backup processes are both related with some specific transactions on blockchain, thus it creates a gap for legal users and attackers who manages to obtain backup to recover key. The gap is decided by the number of accounts and transactions on the blockchain which increases rapidly with the growth of Bitcoin's popularity and therefore strengthens the security of our scheme at the same time. What's more, our technique can also be combined with former ones to achieve better security.

Memory encryption is used in many devices to protect memory content from attackers with physical access to a device. However, many current memory encryption schemes can be broken using Differential Power Analysis (DPA). In this work, we present MEAS---the first Memory Encryption and Authentication Scheme providing security against DPA attacks. The scheme combines ideas from fresh re-keying and authentication trees by storing encryption keys in a tree structure to thwart first-order DPA without the need for DPA-protected cryptographic primitives. Therefore, the design strictly limits the use of every key to encrypt at most two different plaintext values. MEAS prevents higher-order DPA without changes to the cipher implementation by using masking of the plaintext values. MEAS is applicable to all kinds of memory, e.g., NVM and RAM, and has memory overhead comparable to existing memory authentication techniques without DPA protection, e.g., 7.3% for a block size fitting standard disk sectors.

Software-update mechanisms are critical to the security of modern systems, but their typically centralized design presents a lucrative and frequently attacked target. In this work, we propose CHAINIAC, a decentralized software-update framework that eliminates single points of failure, enforces transparency, and provides efficient verifiability of integrity and authenticity for software-release processes. Independent $\textit{witness servers}$ collectively verify conformance of software updates to release policies, $\textit{build verifiers}$ validate the source-to-binary correspondence, and a tamper-proof release log stores collectively signed updates, thus ensuring that no release is accepted by clients before being widely disclosed and validated. The release log embodies a $\textit{skipchain}$, a novel data structure, enabling arbitrarily out-of-date clients to efficiently validate updates and signing keys. Evaluation of our CHAINIAC prototype on reproducible Debian packages shows that the automated update process takes the average of 5 minutes per release for individual packages, and only 20 seconds for the aggregate timeline. We further evaluate the framework using real-world data from the PyPI package repository and show that it offers clients security comparable to verifying every single update themselves while consuming only one-fifth of the bandwidth and having a minimal computational overhead.

We provide a practical solution to performing cross-user machine learning through aggregation on a sensitive dataset distributed among privacy-concerned users. We focus on a scenario in which a single company wishes to obtain the distribution of aggregate features, while ensuring a high level of privacy for the users. We are interested in the case where users own devices that are not necessarily powerful or online at all times, like smartphones or web browsers. This premise makes general solutions, such as general multiparty computation (MPC), less applicable. We design an efficient special-purpose MPC protocol that outputs aggregate features to the company, while keeping online presence and computational complexity on the users’ side at a minimum. This basic protocol is secure against a majority of corrupt users, as long as they do not collude with the company. If they do, we still guarantee security, as long as the fraction of corrupt users is lower than a certain, tweakable, parameter. We propose different enhancements of this solution: one guaranteeing some degree of active security, and one that additionally ensures differential privacy. Finally, we report on the performance of our implementation on several realistic real-world use-cases across different devices.

Classroom voting is an important pedagogical technique in which students learn by voting on the answers to questions. The same voting platform is also often used for exercises such as rating lecturer performance and voting for prizes. In this paper, we present VCV, an end-to-end (E2E) verifiable classroom voting system built based on the DRE-i protocol. Our system provides E2E verifiability without tallying authorities; it supports voting through mobile phones with constrained computing resources; it reports the tallying results instantly after voting is finished along with cryptographic proofs that enable the public to verify the tallying integrity. Since 2013, the VCV system has been used regularly in real classroom teaching, as well as academic prize competitions, in Newcastle University with positive user feedback. Our experience suggests that E2E verifiable voting through the internet and using mobile phones is feasible for daily routine activities such as classroom voting.

The SSL protocol has been widely used for verifying digital identities and to secure Internet traffic since the early days of the web. Although X.509 certificates have been in existence for more than two decades, individual user uptake has been low due to the high cost of issuance and maintenance of such certs. This has led to a situation whereby users are able to verify the identity of an organization or e-commerce retailer via their digital certificate, but organizations have to rely on weak username and password combinations to verify the identity of customers registered with their service. We propose the X509Cloud framework which enables organizations to issue certificates to their users at zero cost, and allows them to securely store and disseminate client certificates using the Bitcoin inspired blockchain protocol. This in turn will enable organizations and individuals to authenticate and to securely communicate with other users on the Internet.