Encrypted databases, a popular approach to protecting data from compromised database management systems (DBMS’s), use abstract threat models that capture neither realistic databases, nor realistic attack scenarios. In particular, the “snapshot attacker” model used to support the security claims for many encrypted databases does not reflect the information about past queries available in any snapshot attack on an actual DBMS. We demonstrate how this gap between theory and reality causes encrypted databases to fail to achieve their “provable security” guarantees.

This paper proposes DeepSecure, a novel framework that enables scalable execution of the state-of-the-art Deep Learning (DL) models in a privacy-preserving setting. DeepSecure targets scenarios in which neither of the involved parties including the cloud servers that hold the DL model parameters or the delegating clients who own the data is willing to reveal their information. Our framework is the first to empower accurate and scalable DL analysis of data generated by distributed clients without sacrificing the security to maintain efficiency. The secure DL computation in DeepSecure is performed using Yao’s Garbled Circuit (GC) protocol. We devise GC-optimized realization of various components used in DL. Our optimized implementation achieves more than 58-fold higher throughput per sample compared with the best prior solution. In addition to our optimized GC realization, we introduce a set of novel low-overhead pre-processing techniques which further reduce the GC overall runtime in the context of deep learning. Extensive evaluations of various DL applications demonstrate up to two orders-of-magnitude additional runtime improvement achieved as a result of our pre-processing methodology. We also provide mechanisms to securely delegate GC computations to a third party in constrained embedded settings.

This paper presents a unified framework that supports different types of privacy-preserving search queries over encrypted cloud data. In the framework, users can perform any of the multi-keyword search, range search and k-nearest neighbor search operations in a privacy-preserving manner. All three types of queries are transformed into predicate-based search leveraging bucketization, locality sensitive hashing and homomorphic encryption techniques. The proposed framework is implemented using Hadoop MapReduce, and its efficiency and accuracy are evaluated using publicly available real data sets. The implementation results show that the proposed framework can effectively be used in moderate sized data sets and it is scalable for much larger data sets provided that the number of computers in the Hadoop cluster is increased. To the best of our knowledge, the proposed framework is the first privacy-preserving solution, in which three different types of search queries are effectively applied over encrypted data.

Real world physical shopping offers customers the privilege of maintaining their privacy by giving them the option of using cash, and thus providing no personal information such as their names and home addresses. On the contrary, electronic shopping mandates the use of all sorts of personally identifiable information for both billing and shipping purposes. Cryptocurrencies such as Bitcoin have created a stimulated growth in private billing by enabling pseudonymous payments. However, the anonymous delivery of the purchased physical goods is still an open research problem. In this work, we present a blockchain-based physical delivery system called Lelantos that within a realistic threat model, offers customer anonymity, fair exchange and merchant-customer unlinkability. Our system is inspired by the onion routing techniques which are used to achieve anonymous message delivery. Additionally, Lelantos relies on the decentralization and pseudonymity of the blockchain to enable pseudonymity that is hard to compromise, and the distributed consensus mechanisms provided by smart contracts to enforce fair irrefutable transactions between distrustful contractual parties.

Unpredictability is an important security property of Physically Unclonable Function (PUF) in the context of statistical attacks, where the correlation between challenge-response pairs is explicitly exploited. In existing literature on PUFs, Hamming Distance test, denoted by $\mathrm{HDT}(t)$, was proposed to evaluate the unpredictability of PUFs, which is a simplified case of the Propagation Criterion test $\mathrm{PC}(t)$. The objective of these testing schemes is to estimate the output transition probability when there are $t$ or less than $t$ bits flips, and ideally, this probability value should be 0.5. In this work, we show that aforementioned two testing schemes are not enough to ensure the unpredictability of a PUF design. We propose a new test which is denoted as $\mathrm{HDT}(\mathbf{e},t)$. This testing scheme is a fine-tuned version of the previous schemes, as it considers the flipping bit pattern vector $\mathbf{e}$ along with parameter $t$. As a contribution, we provide a comprehensive discussion and analytic interpretation of $\mathrm{HDT}(t)$, $\mathrm{PC}(t)$ and $\mathrm{HDT}(\mathbf{e},t)$ test schemes for Arbiter PUF (APUF), XOR PUF and Lightweight Secure PUF (LSPUF). Our analysis establishes that $\mathrm{HDT}(\mathbf{e},t)$ test is more general in comparison with $\mathrm{HDT}(t)$ and $\mathrm{PC}(t)$ tests. In addition, we demonstrate a few scenarios where the adversary can exploit the information obtained from the analysis of $\mathrm{HDT}(\mathbf{e},t)$ properties of APUF, XOR PUF and LSPUF to develop statistical attacks on them, if the ideal value of $\mathrm{HDT}(\mathbf{e},t)=0.5$ is not achieved for a given PUF. We validate our theoretical observations using the simulated and FPGA implemented APUF, XOR PUF and LSPUF designs.

The mechanism for traditional Searchable Symmetric Encryption is pay-then-use. That is to say, if a user wants to search some documents that contain special keywords, he needs to pay to the server firstly, then he can enjoy search service. Under this situation, these kinds of things will happen: After the user paying the service fees, the server may either disappear because of the poor management or returning nothing. As a result, the money that the user paid cannot be brought back quickly. Another case is that the server may return incorrect document sets to the user in order to save his own cost. Once such events happen, it needs the arbitration institution to mediate which will cost a long time. Besides, to settle the disputes the user has to pay to the arbitration institution. Ideally, we deeply hope that when the user realizes the server has a tendency to cheat in the task of searching, he can immediately and automatically withdraw his money to safeguard his right. However, the existing SSE protocols cannot satisfy this demand. To solve this dilemma, we find a compromised method by introducing the block chain into SSE. Our scheme achieves three goals stated below. Firstly, when the server does not return any thing to user after he gets the search token, the user can get some compensation from the server, because the server can infer some important information from the Index and this token. Besides, the user also doesn't pay the service charge. Secondly, if the documents that the server returns are false, the server cannot receive service fees, meanwhile, he will be punished. Lastly, when the user receives some bitcoin from server at the beginning, he may terminate the protocol. Under this situation, the server is a victim. In order to prevent such thing from happening, the server will broadcast a transaction to redeem his pledge after an appointed time.

Although the transactions on the Bitcoin blockchain have the main purpose of recording currency transfers, they can also carry a few bytes of metadata. A sequence of transaction metadata forms a subchain of the Bitcoin blockchain, and it can be used to store a tamper-proof execution trace of a smart contract. Except for the trivial case of contracts which admit any trace, in general there may exist inconsistent subchains which represent incorrect contract executions. A crucial issue is how to make it difficult, for an adversary, to subvert the execution of a contract by making its subchain inconsistent. Existing approaches either postulate that subchains are always consistent, or give weak guarantees about their security (for instance, they are susceptible to Sybil attacks). We propose a consensus protocol, based on Proof-of-Stake, that incentivizes nodes to consistently extend the subchain. We empirically evaluate the security of our protocol, and we show how to exploit it as the basis for smart contracts on Bitcoin.

With the synchronous development of both cloud computing and machine learning techniques, the clients are preferring to resort to the cloud server with substantial resources to train learning model. However, in this outsourcing paradigm it is of vital significance to address the privacy concern of client's data. Many researchers have been focusing on preserving the privacy of client's data in learning model. Recently, Wang et al. presented a privacy-preserving single-layer perceptron learning for e-healthcare scheme with using paillier cryptosystem and claimed that their scheme can protect the privacy of user's medical information. By analysing the process of iteration and the communication between the cloud and the user, we present that the honest-but-curious cloud can obtain the private medical information. Besides, the leakage of medical cases will lead to the exposure of the specific single-layer perceptron model of e-healthcare, which has gigantic commercial value.

Zero-confirmation transactions, i.e., transactions that have been broadcast but are still pending to be included in the blockchain, have gained attention in order to enable fast payments in Bitcoin, shortening the time for performing payments. Fast payments are desirable in certain scenarios, for instance, when buying in vending machines, fast food restaurants, or withdrawing from an ATM. Despite being fast propagated through the network, zero-confirmation transactions are not protected against double-spending attacks, since the double spending protection Bitcoin offers relays on the blockchain and, by definition, such transactions are not yet included in it. In this paper, we propose a double-spending prevention mechanism for Bitcoin zero-confirmation transactions. Our proposal is based on exploiting the flexibility of the Bitcoin scripting language together with a well known vulnerability of the ECDSA signature scheme to discourage attackers from performing such an attack.

This paper is devoted to the study of the problem of running compression algorithms in the encrypted domain, using a (somewhat) Fully Homomorphic Encryption (FHE) scheme. We do so with a particular focus on conservative compression algorithms. Despite of the encrypted domain Turing-completeness which comes with the magic of FHE operators, we show that a number of subtleties crop up when it comes to running compression algorithms and, in particular, that guaranteed conservative compression is not possible to achieve in the FHE setting. To illustrate these points, we analyze the most elementary conservative compression algorithm of all, namely Run-Length Encoding (RLE). We first study the way to regularize this algorithm in order to make it (meaningfully) fit within the constraints of a FHE execution. Secondly, we analyze it from the angle of optimizing the resulting structure towards (as much as possible) FHE execution efficiency. The paper is concluded by concrete experimental results obtained using the Fan-Vercauteren cryptosystem as well as the Armadillo FHE compiler.

Storing the large-scale data on the cloud server side becomes nowadays an alternative for the data owner with the popularity and maturity of the cloud computing technique, where the data owner can manage the data with limited resources, and the user issues the query request to the cloud server instead of the data owner. As the server is not completely trusted, it is necessary for the user to perform results authentication to check whether or not the returned results from the cloud server are correct. We investigate in this paper how to perform efficient data update for the result authentication of the outsourced univariate linear function query. We seek to outsource almost all the data and computing to the server, and as few data and computations as possible are stored and performed on the data owner side, respectively. We present a novel scheme to achieve the security goal, which is divided into two parts. The first part is a verification algorithm for the outsourced computing of line intersections, which enables the data owner to store most of the data on the server side, and to execute less of the computing of the line intersections. The second part is an authentication data structure Two Level Merkle B Tree for the outsourced univariate linear function query, where the top level is used to index the user input and authenticate the query results, and the bottom level is used to index the query condition and authenticate the query results. The authentication data structure enables the data owner to update the data efficiently, and to implement the query on the server side. The theoretic analysis shows that our proposed scheme works with higher efficiency.

Logic encryption is a hardware security technique that uses extra key inputs to lock a given combinational circuit. A recent study by Subramanyan et al. shows that all existing logic encryption techniques can be successfully attacked. As a countermeasure, SARLock was proposed to enhance the security of existing logic encryptions. In this paper, we re- evaluate the security of these approaches. A SAT-based at- tack called Double DIP is proposed and shown to success- fully defeat SARLock-enhanced encryptions.

Logistic regression is a powerful machine learning tool to classify data. When dealing with sensitive data such as private or medical information, cares are necessary. In this paper, we propose a secure system for protecting both the training and predicting data in logistic regression via homomorphic encryption. Perhaps surprisingly, despite the non-polynomial tasks of training and predicting in logistic regression, we show that only additively homomorphic encryption is needed to build our system. Indeed, we instantiate our system with Paillier, LWE-based, and ring-LWE-based encryption schemes, highlighting the merits and demerits of each instance. Our system is very scalable in both the dataset size and dimension, tolerating big size for example of hundreds of millions ($10^8$s) records. Besides examining the costs of computation and communication, we carefully test our system over real datasets to demonstrate its accuracies and other related measures such as F-score and AUC.

Neural Networks (NN) are today increasingly used in Machine Learning where they have become deeper and deeper to accurately model or classify high-level abstractions of data. Their development however also gives rise to important data privacy risks. This observation motives Microsoft researchers to propose a framework, called Cryptonets. The core idea is to combine simplifications of the NN with Fully Homomorphic Encryptions (FHE) techniques to get both confidentiality of the manipulated data and efficiency of the processing. While efficiency and accuracy are demonstrated when the number of non-linear layers is small (eg $2$), Cryptonets unfortunately becomes ineffective for deeper NNs which let the problem of privacy preserving matching open in these contexts. This work successfully addresses this problem by combining the original ideas of Cryptonets' solution with the batch normalization principle introduced at ICML 2015 by Ioffe and Szegedy. We experimentally validate the soundness of our approach with a neural network with $6$ non-linear layers. When applied to the MNIST database, it competes the accuracy of the best non-secure versions, thus significantly improving Cryptonets.

In the paper, we present designs for multiple blockchain consensus primitives and a novel blockchain system, all based on the use of trusted execution environments (TEEs), such as Intel SGX-enabled CPUs. First, we show how using TEEs for existing proof of work schemes can make mining equitably distributed by preventing the use of ASICs. Next, we extend the design with proof of time and proof of ownership consensus primitives to make mining energy- and time-efficient. Further improving on these designs, we present a blockchain using a proof of luck consensus protocol. Our proof of luck blockchain uses a TEE platform's random number generation to choose a consensus leader, which offers low-latency transaction validation, deterministic confirmation time, negligible energy consumption, and equitably distributed mining. Lastly, we discuss a potential protection against up to a constant number of compromised TEEs.

Cross-VM attacks have emerged as a major threat on commercial clouds. These attacks commonly exploit hardware level leakages on shared physical servers. A co-located machine can readily feel the presence of a co-located instance with a heavy computational load through performance degradation due to contention on shared resources. Shared cache architectures such as the last level cache (LLC) have become a popular leakage source to mount cross-VM attack. By exploiting LLC leakages, researchers have already shown that it is possible to recover fine grain information such as cryptographic keys from popular software libraries. This makes it essential to verify implementations that handle sensitive data across the many versions and numerous target platforms, a task too complicated, error prone and costly to be handled by human beings. Here we propose a machine learning based technique to classify applications according to their cache access profiles. We show that with minimal and simple manual processing steps feature vectors can be used to train models using support vector machines to classify the applications with a high degree of success. The profiling and training steps are completely automated and do not require any inspection or study of the code to be classified. In native execution, we achieve a successful classification rate as high as 98\% (L1 cache) and 78\% (LLC) over 40 benchmark applications in the Phoronix suite with mild training. In the cross-VM setting on the noisy Amazon EC2 the success rate drops to 60\% for a suite of 25 applications. With this initial study we demonstrate that it is possible to train meaningful models to successfully predict applications running in co-located instances.

The public nature of the blockchain has been shown to be a severe threat for the privacy of Bitcoin users. Even worse, since funds can be tracked and tainted, no two coins are equal, and fungibility, a fundamental property required in every currency, is at risk. With these threats in mind, several privacy-enhancing technologies have been proposed to improve transaction privacy in Bitcoin. However, they either require a deep redesign of the currency, breaking many currently deployed features, or they address only specific privacy issues and consequently provide only very limited guarantees when deployed separately. The goal of this work is to overcome this trade-off. Building on CoinJoin, we design ValueShuffle, the first coin mixing protocol compatible with Confidential Transactions, a proposed enhancement to the Bitcoin protocol to hide payment values in the blockchain. ValueShuffle ensures the anonymity of mixing participants as well as the confidentiality of their payment values even against other possibly malicious mixing participants. By combining CoinJoin with Confidential Transactions and additionally Stealth Addresses, ValueShuffle provides comprehensive privacy (payer anonymity, payee anonymity, and payment value privacy) without breaking with fundamental design principles or features of the current Bitcoin system. Assuming that Confidential Transactions will be integrated in the Bitcoin protocol, ValueShuffle makes it possible to mix funds of different value as well as to mix and spend funds in the same transaction, which overcomes the two main limitations of previous coin mixing protocols.

Cloud storage platforms promise a convenient way for users to share files and engage in collaborations, yet they require all files to have a single owner who unilaterally makes access control decisions. Existing clouds are, thus, agnostic to the notion of shared ownership. This can be a significant limitation in many collaborations because, for example, one owner can delete files and revoke access without consulting the other collaborators. In this paper, we first formally define a notion of shared ownership within a file access control model. We then propose two possible instantiations of our proposed shared ownership model. Our first solution, called Commune, relies on secure file dispersal and collusion-resistant secret sharing to ensure that all access grants in the cloud require the support of an agreed threshold of owners. As such, Commune can be used in existing clouds without modifications to the platforms. Our second solution, dubbed Comrade, leverages the blockchain technology in order to reach consensus on access control decision. Unlike Commune, Comrade requires that the cloud is able to translate access control decisions that reach consensus in the blockchain into storage access control rules, thus requiring minor modifications to existing clouds. We analyze the security of our proposals and compare/evaluate their performance through implementation integrated with Amazon S3.

Side-Channel Attacks (SCA) are considered a serious threat against embedded cryptography. Therefore security critical chips must be tested for SCA resistance before deployment or certification. SCA are powerful but can need a lot of computation power, especially in the presence of countermeasures. The computation complexity of these attacks can be reduced by selecting a small subset of points where leakage prevails. In this paper, we propose a method to detect relevant leakage points in side-channel traces. The method is based on Normalized Inter-Class Variance (NICV). A key advantage of NICV over state-of-the-art is that NICV does neither need a clone device nor the knowledge of secret parameters of the crypto-system. NICV has a low computation requirement and it detects leakage using public information like input plaintexts or output ciphertexts only. It can also be used to test the efficiency of leakage models, the quality of traces and robustness of countermeasures. A theoretical rationale of NICV with practical application on real crypto-systems are provided to support our claims.

Many online services let users query public datasets such as maps, flight prices, or restaurant reviews. Unfortunately, the queries to these services reveal highly sensitive information that can compromise users’ privacy. This paper presents Splinter, a system that protects users’ queries on public data and scales to realistic applications. A user splits her query into multiple parts and sends each part to a different provider that holds a copy of the data. As long as any one of the providers is honest and does not collude with the others, the providers cannot determine the query. Splinter uses and extends a new cryptographic primitive called Function Secret Sharing (FSS) that makes it up to an order of magnitude more efficient than prior systems based on Private Information Retrieval and garbled circuits. We develop protocols extending FSS to new types of queries, such as MAX and TOPK queries. We also provide an optimized implementation of FSS using AES-NI instructions and multicores. Splinter achieves end-to-end latencies below 1.6 seconds for realistic workloads including a Yelp clone, flight search, and map routing.

Sanctum offers the same promise as SGX, namely strong provable isolation of software modules running concurrently and sharing resources, but protects against an important class of additional software attacks that infer private information from a program's memory access patterns. We follow a principled approach to eliminating entire attack surfaces through isolation, rather than plugging attack-specific privacy leaks. Sanctum demonstrates that strong software isolation is achievable with a surprisingly small set of minimally invasive hardware changes, and a very reasonable overhead. Sanctum does not change any major CPU building block. Instead, we add hardware at the interfaces between building blocks, without impacting cycle time. Our prototype shows a 2% area increase in a Rocket RISC-V core. Over a set of benchmarks, Sanctum's worst observed overhead for isolated execution is 15.1% over an idealized insecure baseline, and 2.7% average overhead over a representative insecure baseline.

For decades, the Network Time Protocol (NTP) has been used to synchronize computer clocks over untrusted network paths. This work takes a new look at the security of NTP's datagram protocol. We argue that NTP's datagram protocol in RFC5905 is both underspecified and flawed. The NTP specifications do not sufficiently respect (1) the conflicting security requirements of different NTP modes, and (2) the mechanism NTP uses to prevent off-path attacks. A further problem is that (3) NTP's control-query interface reveals sensitive information that can be exploited in off-path attacks. We exploit these problems in several attacks that remote attackers can use to maliciously alter a target's time. We use network scans to find millions of IPs that are vulnerable to our attacks. Finally, we move beyond identifying attacks by developing a cryptographic model and using it to prove the security of a new backwards-compatible client/server protocol for NTP.

We present four attacks on three cryptographic schemes intended for securing log files against illicit retroactive modification. Our first two attacks regard the LogFAS scheme by Yavuz et al. (Financial Cryptography 2012), whereas our third and fourth attacks break the BM- and AR-FssAgg schemes by Ma (AsiaCCS 2008). All schemes have an accompanying security proof, seemingly contradicting the existence of attacks. We point out flaws in these proofs, resolving the contradiction.

We give an overview of the scripting languages used in existing cryptocurrencies, and in particular we review in some detail the scripting languages of Bitcoin, Nxt and Ethereum, in the context of a high-level overview of Distributed Ledger Technology and cryptocurrencies. We survey different approaches, and give an overview of critiques of existing languages. We also cover technologies that might be used to underpin extensions and innovations in scripting and contracts, including technologies for verification, such as zero knowledge proofs, proof-carrying code and static analysis, as well as approaches to making systems more efficient, e.g. Merkelized Abstract Syntax Trees.

A Bit-Mixer is a function of fixed size input and output, which computes uncorrelated output from correlated input values, and its behavior is altered by parameters, called keys. Several bit-mixer constructions have been published with very fast, power efficient implementations in electronic hardware, having very little side channel leakage. In this paper a dozen cryptographic applications are discussed, in most of which the output of the employed bit-mixers are hidden from an adversary. In these cases bit-mixers don’t have to satisfy strict cryptographic requirements, but the security of the applications is improved by reducing exploitable correlations among intermediate values, and by diminishing side channel leakage of electronic implementations

There have been many efforts to strengthen security of Instant Messaging (IM) system. One of the typical technologies is the conventional message encryption using a secret or private key. However, the key is fundamentally vulnerable to a bruteforce attack, causing to acquire the original message. In this respect, a countermeasure was suggested as the way to generating plausible-looking but fake plaintexts, which is called Honey Encryption (HE). In this paper, we present a HE-based statistical scheme and design a Honey Chatting application, which is robust to eavesdropping. Besides, we verify the effectiveness of the Honey Chatting by comparing the entropy of decrypted messages through experiments.

Honey encryption (HE) is a new technique to overcome the weakness of conventional password-based encryption (PBE). However, conventional honey encryption still has the limitation that it works only for binary bit streams or integer sequences because it uses a fixed distribution-transforming encoder (DTE). In this paper, we propose a variant of honey encryption called visual honey encryption which employs an adaptive DTE in a Bayesian framework so that the proposed approach can be applied to more complex domains including images and videos. We applied this method to create a new steganography scheme which significantly improves the security level of traditional steganography.

Bitcoin smart contracts allow the development of new protocols on top of Bitcoin itself. This usually involves the definition of complex scripts, far beyond the requirement of a single signature. In this paper we introduce the concept of private key locked transactions, a novel type of transactions that allows the atomic verification of a given private key (belonging to an asymmetric key pair) during the script execution.

Smart contracts are computer programs that can be correctly executed by a network of mutually distrusting nodes, without the need of an external trusted authority. Since smart contracts handle and transfer assets of considerable value, besides their correct execution it is also crucial that their implementation is secure against attacks which aim at stealing or tampering the assets. We study this problem in Ethereum, the most well-known and used framework for smart contracts so far. We analyse the security vulnerabilities of Ethereum smart contracts, providing a taxonomy of common programming pitfalls which may lead to vulnerabilities. We show a series of attacks which exploit these vulnerabilities, allowing an adversary to steal money or cause other damage.

Oblivious RAM (ORAM) protocols are powerful techniques that hide a client's data as well as access patterns from untrusted service providers. We present an oblivious cloud storage system, ObliviSync, that specifically targets one of the most widely-used personal cloud storage paradigms: synchronization and backup services, popular examples of which are Dropbox, iCloud Drive, and Google Drive. This setting provides a unique opportunity because the above privacy properties can be achieved with a simpler form of ORAM called write-only ORAM, which allows for dramatically increased efficiency compared to related work. Our solution is asymptotically optimal and practically efficient, with a small constant overhead of approximately 4x compared with non-private file storage, depending only on the total data size and parameters chosen according to the usage rate, and not on the number or size of individual files. Our construction also offers protection against timing-channel attacks, which has not been previously considered in ORAM protocols. We built and evaluated a full implementation of ObliviSync that supports multiple simultaneous read-only clients and a single concurrent read/write client whose edits automatically and seamlessly propagate to the readers. We show that our system functions under high work loads, with realistic file size distributions, and with small additional latency (as compared to a baseline encrypted file system) when paired with Dropbox as the synchronization service.

Data deduplication, aiming to eliminate duplicate data, has been widely used in cloud storage to reduce the amount of storage space and save bandwidth. Unfortunately, as an increasing number of sensitive data are stored remotely, the encryption, the simplest way for data privacy, is not compatible with data deduplication. Though many research efforts have been devoted to securing deduplication, they all are subject to performance, security, and applicability limitations. Here, we propose two encrypted deduplication schemes, SDedup and XDedup, both based on Merkle puzzle. To the best of our knowledge, XDedup is the first brute-force resilient encrypted deduplication with only symmetrically cryptographic two-party interactions. The analysis and numerical simulations are conducted to demonstrate the performance and practicality of SDedup and XDedup.

Smart metering, smart parking, health, environment monitoring, and other applications drive the deployment of the so-called Internet of Things (IoT). Whilst cost and energy efficiency are the main factors that con- tribute to the popularity of commercial devices in the IoT domain, secu- rity features are increasingly desired. Security features typically guarantee authenticity of devices and/or data, as well as confidentiality of data in transit. Our study finds that whilst cryptographic algorithms for confi- dentiality and authenticity are supported in hardware on a popular class of devices, there is no adequate support for random number generation available. We show how to passively manipulate the on-board source for randomness, and thereby we can completely undermine the security pro- vided by (otherwise) strong cryptographic algorithms, with devastating results.

Man-in-the-middle attacks in TLS due to compromised CAs have been mitigated by log-based PKI enhancements such as Certificate Transparency. However, these log-based schemes do not offer sufficient incentives to logs and monitors, and do not offer any actions that domains can take in response to CA misbehavior. We propose IKP, a blockchain-based PKI enhancement that offers automatic responses to CA misbehavior and incentives for those who help detect misbehavior. IKP’s decentralized nature and smart contract system allows open participation, offers incentives for vigilance over CAs, and enables financial recourse against misbehavior. We demonstrate through a game theoretic model and through an Ethereum prototype implementation that the incentives and increased deterrence offered by IKP are technically and economically viable.

Searchable Symmetric Encryption aims at making possible searching over an encrypted database stored on an untrusted server while keeping privacy of both the queries and the data, by allowing some small controlled leakage to the server. Recent work shows that dynamic schemes -- in which the data is efficiently updatable -- leaking some information on updated keywords are subject to devastating adaptative attacks breaking the privacy of the queries. The only way to thwart this attack is to design \emph{forward private} schemes whose update procedure does not leak if a newly inserted element matches previous search queries. This work proposes ${\Sigma o\phi o\varsigma}$ as a forward private SSE scheme with performance similar to existing less secure schemes, and that is conceptually simpler (and also more efficient) than previous forward private constructions. In particular, it only relies on trapdoor permutations and does not use an ORAM-like construction. We also explain why ${\Sigma o\phi o\varsigma}$ is an optimal point of the security/performance tradeoff for SSE. Finally, an implementation and evaluation results demonstrate its practical efficiency.

Clock glitch based Differential Fault Analysis (DFA) attack is a serious threat to cryptographic devices. Previous error detection schemes for cryptographic devices target improving the circuit reliability and cannot resist such DFA attacks. In this paper, we propose a novel faulty clock detection method which can be easily implemented either in FPGAs or integrated circuits to detect the glitches in system clock. Results show that the proposed method can detect glitches efficiently while needs very few system resource. It is also highly reconfigurable to tolerant clock inherent jitters, and will not involve complex design work for different processing technologies.

We introduce secure channel injection (SCI) protocols, which allow one party to insert a private message into another party's encrypted communications. We construct an efficient SCI protocol for communications delivered over TLS, and use it to realize anonymous proofs of account ownership for SMTP servers. This allows [email protected] to prove ownership of some email address @mail.com, without revealing ``alice'' to the verifier. We show experimentally that our system works with standard email server implementations as well as Gmail. We go on to extend our basic SCI protocol to realize a ``blind'' certificate authority: the account holder can obtain a valid X.509 certificate binding [email protected] to her public key, if it can prove ownership of some email address @mail.com. The authority never learns which email account is used.

Since hundreds of certificate authorities (CAs) can issue browser-trusted certificates, it can be difficult for domain owners to detect certificates that have been fraudulently issued for their domain. Certificate Transparency (CT) is a recent standard by the Internet Engineering Task Force (IETF) that aims to construct public logs of all certificates issued by CAs, making it easier for domain owners to monitor for fraudulently issued certificates. To avoid relying on trusted log servers, CT includes mechanisms by which monitors and auditors can check whether logs are behaving honestly or not; these mechanisms are primarily based on Merkle tree hashing and authentication proofs. Given that CT is now being deployed, it is important to verify that it achieves its security goals. In this work, we define four security properties of logging schemes such as CT that can be assured via cryptographic means, and show that CT does achieve these security properties. We consider two classes of security goals: those involving security against a malicious logger attempting to present different views of the log to different parties or at different points in time, and those involving security against malicious monitors who attempt to frame an honest log for failing to include a certificate in the log. We show that Certificate Transparency satisfies these security properties under various assumptions on Merkle trees all of which reduce to collision resistance of the underlying hash function (and in one case with the additional assumption of unforgeable signatures).

We develop a systematic approach for analyzing client-server applications that aim to hide sensitive user data from untrusted servers. We then apply it to Mylar, a framework that uses multi-key searchable encryption (MKSE) to build Web applications on top of encrypted data. We demonstrate that (1) the Popa-Zeldovich model for MKSE does not imply security against either passive or active attacks; (2) Mylar-based Web applications reveal users’ data and queries to passive and active adversarial servers; and (3) Mylar is generically insecure against active attacks due to system design flaws. Our results show that the problem of securing client-server applications against actively malicious servers is challenging and still unsolved. We conclude with general lessons for the designers of systems that rely on property-preserving or searchable encryption to protect data from untrusted servers.

Web advertisements, an integral part of today's web browsing experience, financially support countless websites. Meaningful advertisements, however, require behavioral targeting, user tracking and profile fingerprinting that raise serious privacy concerns. To counter privacy issues and enhance usability, adblockers emerged as a popular way to filter web requests that do not serve the website's main content. Despite their popularity, little work has focused on quantifying the privacy provisions of adblockers. In this paper, we develop a quantitative approach to objectively compare the privacy of adblockers. We propose a model based on a set of privacy metrics that captures not only the technical web architecture, but also the underlying corporate institutions of the problem across time and geography. We investigate experimentally the effect of various combinations of ad-blocking software and browser settings on 1000 Web sites. Our results highlight a significant difference among adblockers in terms of filtering performance, in particular affected by the applied configurations. Besides the ability to judge the filtering capabilities of existing adblockers and their particular configurations, our work provides a general framework to evaluate new adblocker proposals.

Logic encryption protects integrated circuits (ICs) against intellectual property (IP) piracy and over- building attacks by encrypting the IC with a key. A Boolean satisfiability (SAT) based attack breaks all existing logic encryption technique within few hours. Recently, a defense mechanism known as Anti-SAT was presented that protects against SAT attack, by rendering the SAT-attack effort exponential in terms of the number of key gates. In this paper, we highlight the vulnerabilities of Anti-SAT and propose signal probability skew (SPS) attack against Anti-SAT block. SPS attack leverages the structural traces in Anti-SAT block to identify and isolate Anti-SAT block. The attack is 100% successful on all variants of Anti-SAT block. SPS attack is scalable to large circuits, as it breaks circuits with up to 22K gates within two minutes.

Web applications rely on servers to store and process confidential information. However, anyone who gains access to the server (e.g., an attacker, a curious administrator, or a government) can obtain all of the data stored there. This paper presents Mylar, a platform that provides end-to-end encryption to web applications. Mylar protects the confidentiality of sensitive data fields against attackers that gained access to servers. Mylar stores sensitive data encrypted on the server, and decrypts that data only in users’ browsers. Mylar addresses three challenges in making this approach work. First, Mylar allows the server to perform keyword search over encrypted documents, even if the documents are encrypted with different keys. Second, Mylar allows users to share keys securely in the presence of an active adversary. Finally, Mylar ensures that client-side application code is authentic, even if the server is malicious. Results with a prototype of Mylar built on top of the Meteor framework are promising: porting 6 applications required changing just 36 lines of code on average, and the performance overheads are modest, amounting to a 17% throughput loss and a 50 ms latency increase for sending a message in a chat application.

Physical Unclonable Functions (PUFs) provide cryptographic keys for embedded systems without secure non-volatile key storage. Several error correction schemes for key generation with PUFs were introduced, analyzed and implemented over the last years. This work abstracts from the typical algorithmic level and provides an algebraic view to reveal fundamental similarities and differences in the security of these error correction schemes. An algebraic core is introduced for key generation with Physical Unclonable Functions (PUFs). It computes the secret key through the helper data from the input PUF response and an optional random number. For nearly uniformly distributed PUF responses, the leakage of the secret key and the helper data can be brought to zero if and only if the rank of the algebraic core is equal to the sum of the ranks of the key generating part and the rank of the helper data generating part. This rank criterion has the practical advantage that a security check can be performed for linear codes at an early design stage of an algorithm. The criterion is applied to state-of-the-art approaches to show that fuzzy commitment and systematic low leakage coding are the only analyzed schemes that achieve zero leakage.

This paper proposes a decentralised and privacy-preserving local electricity trading market. The proposed market employs a bidding protocol based upon secure multiparty computations and allows users to trade their excess electricity among themselves. The bid selection and calculation of the clearance price at which the electricity is traded are performed by the market in a decentralised and privacy-preserving manner. We implemented the market in C++ and tested its performance with realistic data sets. Our simulation results show that the market tasks can be performed for 2500 bids in less than five minutes in the online phase, showing its feasibility for a typical electricity trading period of, for example, 30 minutes.

Amid growing concerns of government surveillance and corporate data sharing, web users increasingly demand tools for preserving their privacy without placing trust in a third party. Unfortunately, existing centralized reputation systems need to be trusted for either privacy, correctness, or both. Existing decentralized approaches, on the other hand, are either vulnerable to Sybil attacks, present inconsistent views of the network, or leak critical information about the actions of their users. In this paper, we present Beaver, a decentralized anonymous marketplace that is resistant against Sybil attacks on vendor reputation, while preserving user anonymity. Beaver allows its participants to enjoy open enrollment, and provides every user with the same global view of the reputation of other users through public ledger based consensus. Various cryptographic primitives allow Beaver to offer high levels of usability and practicality, along with strong anonymity guarantees. Operations such as creating a listing, purchasing an item, and leaving feedback take just milliseconds to compute and require generating just a few kilobytes of state while often constructing convenient anonymity sets of hundreds of transactions.

The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently being considered by the IRTF (Internet Research Task Force) as a new de-facto standard for password hashing. An older version (Argon2i-A) of the same algorithm was chosen as the winner of the recent Password Hashing Competition. An important competitor to Argon2i-B is the recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs, Boneh and Schechter. A key security desiderata for any such algorithm is that evaluating it (even using a custom device) requires a large amount of memory amortized across multiple instances. Alwen and Blocki (CRYPTO 2016) introduced a class of theoretical attacks against Argon2i-A and BH. While these attacks yield large asymptotic reductions in the amount of memory, it was not, a priori, clear if (1) they can be extended to the newer Argon2i-B, (2) the attacks are effective on any algorithm for practical parameter ranges (e.g., 1GB of memory) and (3) if they can be effectively instantiated against any algorithm under realistic hardware constrains. In this work we answer all three of these questions to the affirmative for all three algorithms. It is also the first work to analyze the security of Argon2i-B. In more detail, we extend the theoretical attacks of Alwen and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal demonstrating severe asymptotic deficiencies in its security. Next we introduce several novel heuristics for improving the attack's concrete memory efficiency even when on-chip memory bandwidth is bounded. We then simulate our attacks on randomly sampled Argon2i-A, Argon2i-B and BH instances and measure the resulting memory consumption for various practical parameter ranges and for a variety of upperbounds on the amount of parallelism available to the attacker. Finally we describe, implement and test a new heuristic for applying the Alwen-Blocki attack to functions employing a technique developed by Corrigan-Gibs et al. for improving concrete security of memory-hard functions. We analyze the collected data and show the effects various parameters have on the memory consumption of the attack. In particular, we can draw several interesting conclusions about the level of security provided by these functions. \begin{itemize} \item For the Alwen-Blocki attack to fail against practical memory parameters, Argon2i-B must be instantiated with more than 10 passes on memory. The current IRTF proposal calls even just 6 passes as the recommended ``paranoid'' setting. \item More generally, the parameter selection process in the proposal is flawed in that it tends towards producing parameters for which the attack is successful (even under realistic constraints on parallelism). \item The technique of Corrigan-Gibs for improving security can also be overcome by the Alwen-Blocki attack under realistic hardware constraints. \item On a positive note, both the asymptotic and concrete security of Argon2i-B seem to improve on that of Argon2i-A. \end{itemize}

Private Set Intersection (PSI) allows two parties to compute the intersection of private sets while revealing nothing more than the intersection itself. PSI needs to be applied to large data sets in scenarios such as measurement of ad conversion rates, data sharing, or contact discovery. Existing PSI protocols do not scale up well, and therefore some applications use insecure solutions instead. We describe a new approach for designing PSI protocols based on permutation-based hashing, which enables to reduce the length of items mapped to bins while ensuring that no collisions occur. We denote this approach as Phasing, for Permutation-based Hashing Set Intersection. Phasing can dramatically improve the performance of PSI protocols whose overhead depends on the length of the representations of input items. We apply Phasing to design a new approach for circuit-based PSI protocols. The resulting protocol is up to 5 times faster than the previously best Sort-Compare-Shuffle circuit of Huang et al. (NDSS 2012). We also apply Phasing to the OT-based PSI protocol of Pinkas et al. (USENIX Security 2014), which is the fastest PSI protocol to date. Together with additional improvements that reduce the computation complexity by a logarithmic factor, the resulting protocol improves run-time by a factor of up to 20 and can also have similar communication overhead as the previously best PSI protocol in that respect. The new protocol is only moderately less efficient than an insecure PSI protocol that is currently used by real-world applications, and is therefore the first secure PSI protocol that is scalable to the demands and the constraints of current real-world settings.

Over the past few years, the microprocessor industry has introduced accelerated cryptographic capabilities through instruction set extensions. Although powerful and resistant to side-channel analysis such as cache and timing attacks, these instructions do not implicitly protect against power-based side-channel attacks, such as DPA. This paper provides a specific example with Intel's AES-NI cryptographic instruction set extensions, detailing a DPA, along with results, showing two ways to extract AES keys by simply placing a magnetic field probe beside two capacitors on a motherboard hosting an Intel Core i7 Ivy Bridge microprocessor. Based on the insights of the DPA, methods are then presented on how to mitigate the leaks, in software, providing a dial for diverting the optimal amount of resources required for a prescribed security requirement.

Client puzzles have been proposed as a mechanism for proving legitimate intentions by providing ``proofs of work'', which can be applied to discourage malicious usage of resources. A typical problem of puzzle constructions is the difference in expected solving time on different computing platforms. We call puzzles which can be solved independently of client computing resources \emph{fair client puzzles}. We propose a construction for client puzzles requiring widely distributed computational effort for their solution. These puzzles can be solved using the mining process of Bitcoin, or similar cryptocurrencies. Adapting existing definitions, we show that our puzzle construction satisfies formal requirements of client puzzles under reasonable assumptions. We describe a way of transforming our client puzzles for use in denial of service scenarios and demonstrate a practical construction.

The goal of searchable encryption (SE) is to enable a client to execute searches over encrypted files stored on an untrusted server while ensuring some measure of privacy for both the encrypted files and the search queries. Research has focused on developing efficient SE schemes at the expense of allowing some small, well-characterized "(information) leakage" to the server about the files and/or the queries. The practical impact of this leakage, however, remains unclear. We thoroughly study file-injection attacks--in which the server sends files to the client that the client then encrypts and stores--on the query privacy of single-keyword and conjunctive SE schemes. We show such attacks can reveal the client's queries in their entirety using very few injected files, even for SE schemes having low leakage. We also demonstrate that natural countermeasures for preventing file-injection attacks can be easily circumvented. Our attacks outperform prior work significantly in terms of their effectiveness as well as in terms of their assumptions about the attacker's prior knowledge.

We study practical order-revealing encryption (ORE) with a well-defined leakage profile (the information revealed about the plaintexts from their ciphertexts), a direction recently initiated by Chenette, Lewi, Weis, and Wu (CLWW). ORE, which allows public comparison of plaintext order via their ciphertexts, is a useful tool in the design of secure outsourced database systems. We first show a general construction of ORE with reduced leakage as compared to CLWW, by combining ideas from their scheme with a new type of ''property-preserving'' hash function. We then show how to construct such a hash function efficiently based on bilinear maps. Our resulting ORE scheme is fairly practical: for n-bit plaintexts, ciphertexts consists of about 4n group elements, and order comparison requires about n^2 pairings. The leakage is, roughly speaking, the ''equality pattern'' of the most-significant differing bits, whereas CLWW's is the location and values of the most-significant differing bits. We also provide a generalization of our scheme that improves the leakage and/or efficiency. To analyze the quality of our leakage profile, we show several additional results. In particular, we show that order-\emph{preserving} (OPE) encryption, an important special case of ORE scheme in which ciphertexts are ordered, cannot be secure wrt.our leakage profile. This implies that our ORE scheme is the first one without multilinear maps that is proven secure wrt.a leakage profile unachievable by OPE. We also also show that our generalized scheme meets a ''semantically meaningful'' one-wayness notion that schemes with the leakage of CLWW do not.

In the cloud computing era, in order to avoid computational burdens, many organizations tend to outsource their computations to third-party cloud servers. In order to protect service quality, the integrity of computation results need to be guaranteed. In this paper, we develop a game theoretic framework which helps the outsourcer to minimize its cost while ensuring the integrity of the outsourced computation. We then apply the proposed framework to two collaborative filtering algorithms and demonstrate the equilibriums together with the corresponding minimal costs. Finally, we show that, by including the intermediate results in the final output, further cost reduction can be achieved.

Identity Theft is the fastest rising crime in the United States with about 7% of US adult population victimized annually. This frightening scope warrants a bold government intervention. Here is a detailed proposal. "Cyber Passport" addresses itself to the main threat: a breach of a merchant, bank, or government department resulting in theft of identities of millions of citizens, which for a long time live in fear of residual violations. The solution is based on two principles: (i) online transactions may require a randomized, readily replaceable, short lived code (cyber passport); (ii) the cyber passport will be comprised of a working code, and of an un-stored code which is known only to the issuing agency and to the individual recipient. When implemented these two principles will prevent a massive violation - the biggest plague today. The un-stored code cannot be stolen from any business database because it is not stored there. Hackers will still be able to steal everything but they will have to go retail, no more wholesale theft. Cyber-Passport is not a panacea, but it brings the threat down to size. The program will be optional for citizens, and voluntary for participating establishments facing the public. It will require some legislation, a non-trivial administration, and the use of modern cryptographic technology. Albeit, an organic growth implementation plan is presented herewith.

Radio-Frequency Identification (RFID) tags have been widely used as a low-cost wireless method for detection of counterfeit product injection in supply chains. In order to adequately perform authentication, current RFID monitoring schemes need to either have a persistent online connection between supply chain partners and the back-end database or have a local database on each partner site. A persistent online connection is not guaranteed and local databases on each partner site impose extra cost and security issues. We introduce a new method in which we use 2-3kb Non-Volatile Memory (NVM) in RFID tags themselves to function as a very small “encoded local database”. Our method allows us to get rid of local databases and there is no need to have any connection between supply chain partners and the back-end database except when they want to verify products. We formally define black-box software unclonability and prove our scheme to satisfy this property. To this purpose, we introduce a simple “XOR-ADD” function and prove it is hard to predict its challenge-response behavior if given only one challenge response pair. The XOR-ADD function with control logic can be implemented using at most 170 gates. This implies that our scheme is compatible with the strict power consumption constraints of cheap EPC Class 1 Gen 2 RFIDs.

Proof of Work (PoW) powered blockchains currently account for more than 90% of the total market capitalization of existing digital currencies. Although the security provisions of Bitcoin have been thoroughly analysed, the security guarantees of variant (forked) PoW blockchains (which were instantiated with different parameters) have not received much attention in the literature. In this paper, we introduce a novel quantitative framework to analyse the security and performance implications of various consensus and network parameters of PoW blockchains. Based on our framework, we devise optimal adversarial strategies for double-spending and selfish mining while taking into account real world constraints such as network propagation, different block sizes, block generation intervals, information propagation mechanism, and the impact of eclipse attacks. Our framework therefore allows us to capture existing PoW-based deployments as well as PoW blockchain variants that are instantiated with different parameters, and to objectively compare the tradeoffs between their performance and security provisions.

Testing of electronic components is indispensable to minimize malfunction and failure of complex electronic systems. Currently, functionality and performance of these electronic components are the main parameters tested. However, validation of performance is not enough when the applications are safety or security critical. Therefore the security and trust of devices must also be tested before validation for such applications. In this paper, we promote the use of On-Chip Power noise Measurements (OCM), in order to test security using side-channel techniques. We then propose for the first time a standard side-channel measurement setup using OCM. Finally, we provide some key ideas on methodology to integrate the validation of hardware security and trust in the standard testing flow, exploiting OCM.

Private database query (PDQ) processing has received much attention from the fields of both cryptography and databases. While previous approaches to design PDQ protocols exploit several cryptographic tools concurrently, recently the appearance of fully homomorphic encryption (FHE) schemes enables us to design PDQ protocols without the aid of additional tools. However, to the best of our knowledge, all currently existing FHE-based PDQ protocols focus on protecting only constants in query statements, together with the client's data stored in the database server. In this paper, we provide a FHE-based PDQ protocol achieving better security, protecting query types as well as constants in query statements for conjunctive, disjunctive, and threshold queries with equality comparison. Our contributions are three-fold: First, we present a new security definition that reflects our enhanced security model which additionally protects query types in query statements. Second, we provide a new design for PDQ protocols using FHE schemes. To do this, we come up with a method to homomorphically evaluate our encrypted target queries on the encrypted database. Thereafter, we apply it to construct a protocol and show its security under our enhanced security definition in the semi-honest model. Finally, we provide proof-of-concept implementation results of our PDQ protocol. According to our rudimentary experiments, it takes 40 seconds to perform a query on 2352 elements consisting of 11 attributes of 40-bit using Brakerski-Gentry-Vaikuntanathan's leveled FHE with SIMD techniques for 80-bit security, yielding an amortized rate of just 0.12 seconds per element.

In this short technical summary, the authors describe how the mathematical primitives of Ring Confidential Transactions may be used to provide anonymous identity authentication services in a similar manner to "Anonrep" but in a trustless (or permissioned), distributed manner, and with the additional security and resilience provided by a blockchain. The use of the mathematics in the RingCT paper additionally, and importantly, allows for combining different types of authentication in a seamless manner, in essence if the Bitcoin or Monero blockchain is a single "thread," then the protocol here allows one to "weave" such threads together. The resulting protocol is dubbed an "Identity Chain" and provides anonymous authentication working in a lightweight and interoperable manner between any number of different service providers running different identity chains.

Private query processing is a very attractive problem in the fields of both cryptography and databases. In this work, we restrict our attention to the efficiency aspect of the problem, particularly for basic queries with conditions on various combinations of \emph{equality}. Without loss of generality, these conditions can be regarded as a Boolean function, and this Boolean function can then be evaluated at ciphertexts produced by a fully homomorphic encryption (FHE) scheme \emph{without decryption}. From the efficiency perspective, the remaining concern is to efficiently test the equality function without severely downgrading the performance of FHE-based querying solutions. To this end, we first analyze the multiplicative depth required for an equality test algorithm with respect to the plaintext space inhabited by general FHE schemes. The primary reason for this approach is that given an equality test algorithm, its efficiency is measured in terms of the multiplicative depth required to construct its arithmetic circuit expression. Indeed, the implemented equality test algorithm dominates the entire performance of FHE-based query solutions, apart from the performance of the underlying FHE scheme. Then, we measure the multiplicative depth considering an FHE scheme that takes an extension field as its plaintext space and that supports the depth-free evaluation of Frobenius maps. According to our analysis, when the plaintext space of an FHE scheme is a field of characteristic $2$, the equality test algorithm for $\ell$-bit messages requires the lowest multiplicative depth $\lceil\log{\ell}\rceil$. Furthermore, we design a set of private query protocols for conjunctive, disjunctive, and threshold queries based on the equality test algorithm. Similarly, applying the equality test algorithm over $\mathbb{F}_{2^{\ell}}$, our querying protocols require the minimum depths. More specifically, a multiplicative depth of $\lceil\log{\ell}\rceil+\lceil\log{(1+\rho)}\rceil$ is required for conjunctive and disjunctive queries, and a depth of $\lceil\log{\ell}\rceil+2\lceil\log{(1+\rho)}\rceil$ is required for threshold conjunctive queries, when their query conditions have $\rho$ attributes to be compared. Finally, we provide a communication-efficient version of our solutions, though with additional computational costs, when an upper bound $\delta$ ($0\leq \delta\leq 1$) on the selectivity of a database is given. Consequently, we reduce the communication cost from $n$ to approximately $\lfloor\delta n\rfloor$ ciphertexts with $\lceil\log{n}\rceil$ additional depth when the database consists of $n$ tuples.

The rapid expansion and increased popularity of cloud computing comes with no shortage of privacy concerns about outsourcing computation to semi-trusted parties. Leveraging the power of encryption, in this paper we introduce Cryptoleq: an abstract machine based on the concept of One Instruction Set Computer, capable of performing general-purpose computation on encrypted programs. The program operands are protected using the Paillier partially homomorphic cryptosystem, which supports addition on the encrypted domain. Full homomorphism over addition and multiplication, which is necessary for enabling general-purpose computation, is achieved by inventing a heuristically obfuscated software re-encryption module written using Cryptoleq instructions and blended into the executing program. Cryptoleq is heterogeneous, allowing mixing encrypted and unencrypted instruction operands in the same program memory space. Programming with Cryptoleq is facilitated using an enhanced assembly language that allows development of any advanced algorithm on encrypted datasets. In our evaluation, we compare Cryptoleq's performance against a popular fully homomorphic encryption library, and demonstrate correctness using a typical Private Information Retrieval problem.

The Open Smart Grid Protocol (OSGP) is a widely used industry standard for exchanging sensitive data between devices inside of smart grids. For message confidentiality, OSGP implements a customised form of the RC4 stream cipher. In this work, we show how already known weaknesses of RC4 can be exploited to successfully attack the OSGP implementation as well. The attack modification is able to effectively derive the secret OSGP encryption and decryption key, given that an attacker can accumulate the cipher streams of approximately 90,000 messages. The possession of this key allows the attacker to decrypt all data intercepted on the OSGP smart grid and thereby obtain privacy critical information of its participants.

We remark that the Lei et al.'s scheme [IEEE Transactions on Cloud Computing, 1 (1), 78-87, 2013] fails, because the verifying equation does not hold over the infinite field R. For the field R, the computational errors should be considered seriously.

The Lightweight Secure Physically Unclonable Function (LSPUF) was proposed as a secure composition of Arbiter PUFs with additional XOR based input and output networks. But later, researchers proposed a Machine Learning (ML) based modeling attack on $x$-XOR LSPUF, and they also empirically showed that pure ML based modeling is not computationally scalable if the parameter $x$ of $x$-XOR LSPUF is larger than nine. Besides this pure computational attack using only challenge-response pairs (CRPs), there are other proposals for modeling attacks on LSPUF using timing and power side-channel information, reliability information and photonic side-channel information of an LSPUF instance. % In this paper, we proposed another pure computational attack (i.e. without any side-channel information) on multibit output LSPUF variants using both cryptanalysis and ML techniques together. We, first, cryptanalyze the output network of LSPUF to reduce the computational efforts required by previously proposed pure ML based modeling of an $x$-XOR LSPUF. Specifically, we model an LSPUF instance, while its output bit is defined as $x$-XOR PUF, using the ML modeling of $y$-XOR PUF where $y<x$. From the computational complexity view point, our proposed modeling attack is efficient and scalable than previously proposed pure ML based modeling of LSPUFs with respect to both data and time complexities. We demonstrate the effectiveness of our proposed attack using the Matlab based simulation of LSPUFs and LSPUFs implemented on Xilinx Artix-7 Field Programmable Gate Arrays (FPGAs).

Over the last few years, data storage in cloud based services has been very popular due to easy management and monetary advantages of cloud computing. Recent developments showed that such data could be leaked due to various attacks. To address some of these attacks, encrypting sensitive data before sending to cloud emerged as an important protection mechanism. If the data is encrypted with traditional techniques, selective retrieval of encrypted data becomes challenging. To address this challenge, efficient searchable encryption schemes have been developed over the years. Almost all of the existing searchable encryption schemes are developed for keyword searches and require running some code on the cloud servers. However, many of the existing cloud storage services (e.g., Dropbox, Box, Google Drive, etc.) only allow simple data object retrieval and do not provide computational support needed to realize most of the searchable encryption schemes. In this paper, we address the problem of efficient execution of complex search queries over wide range of encrypted data types (e.g., image files) without requiring customized computational support from the cloud servers. To this end, we provide an extensible framework for supporting complex search queries over encrypted multimedia data. Before any data is uploaded to the cloud, important features are extracted to support different query types (e.g., extracting facial features to support face recognition queries) and complex queries are converted to series of object retrieval tasks for cloud service. Our results show that this framework may support wide range of image retrieval queries on encrypted data with little overhead and without any change to underlying data storage services.

We introduce the concept of canary numbers, to be used in health tests for true random number generators. Health tests are essential components of true random number generators because they are used to detect defects and failures of the entropy source. These tests need to be lightweight, low-latency and highly reliable. The proposed solution uses canary numbers which are an extra output of the entropy source of lower quality. This enables an early-warning attack detection before the output of the generator is compromised. We illustrate the idea with 2 case studies of true random number generators implemented on a Xilinx Spartan-6 FPGA.

Evaluating the practical security of Ring-LWE based cryptography has attracted lots of efforts recently. Indeed, some differences from the standard LWE problem enable new attacks. In this paper we discuss the security of Ring-LWE as found in Fully Homomorphic Encryption (FHE) schemes. These schemes require parameters of very special shapes, that an attacker might use to its advantage. First we present the specificities of this case and recall state-of-the-art attacks, then we derive a new special-purpose attack. Our experiments show that this attack has unexpected performance and confirm that we need to study the security of special parameters sets carefully.

Thanks to their anonymity (pseudonymity) and elimination of trusted intermediaries, cryptocurrencies such as Bitcoin have created or stimulated growth in many businesses and communities. Unfortunately, some of these are criminal, e.g., money laundering, illicit marketplaces, and ransomware. Next-generation cryptocurrencies such as Ethereum will include rich scripting languages in support of {\em smart contracts}, programs that autonomously intermediate transactions. In this paper, we explore the risk of smart contracts fueling new criminal ecosystems. Specifically, we show how what we call {\em criminal smart contracts} (CSCs) can facilitate leakage of confidential information, theft of cryptographic keys, and various real-world crimes (murder, arson, terrorism). We show that CSCs for leakage of secrets (à la Wikileaks) are efficiently realizable in existing scripting languages such as that in Ethereum. We show that CSCs for theft of cryptographic keys can be achieved using primitives, such as Succinct Non-interactive ARguments of Knowledge (SNARKs), that are already expressible in these languages and for which efficient supporting language extensions are anticipated. We show similarly that authenticated data feeds, an emerging feature of smart contract systems, can facilitate CSCs for real-world crimes (e.g., property crimes). Our results highlight the urgency of creating policy and technical safeguards against CSCs in order to realize the promise of smart contracts for beneficial goals.

A cryptographic contract and enforcement technology would guarantee release of a data decryption key to an authorized party if and only if predetermined contract requirements are satisfied. Threshold secret sharing can be used to eliminate the need for access to the hidden key under normal circumstances. It can also eliminate the liability and burden normally carried by device manufacturers or service providers when they store the decryption keys of their customers. Blockchain technology provides a mechanism for a public audit trail of the creation and release of the hidden key. The use of peer-to-peer mix-net network overlay technology can be added to insure that the blockchain audit trail documents the release of the key even if an all-powerful entity forces actors to act under duress.

Besides attracting a billion dollar economy, Bitcoin revolutionized the field of digital currencies and influenced many adjacent areas. This also induced significant scientific interest. In this survey, we unroll and structure the manyfold results and research directions. We start by introducing the Bitcoin protocol and its building blocks. From there we continue to explore the design space by discussing existing contributions and results. In the process, we deduce the fundamental structures and insights at the core of the Bitcoin protocol and its applications. As we show and discuss, many key ideas are likewise applicable in various other fields, so that their impact reaches far beyond Bitcoin itself.

Recent advances in Deep Learning (DL) allow for solving complex AI problems that used to be very hard. While this progress has advanced many fields, it is considered to be bad news for CAPTCHAs (Completely Automated Public Turing tests to tell Computers and Humans Apart), the security of which is based on the hardness of learning problems. In this paper we introduce DeepCAPTCHA, a new and secure CAPTCHA scheme based on adversarial examples, an inherit limitation of the current Deep Learning networks. These adversarial examples are constructed inputs, computed by adding a small and specific perturbation called adversarial noise to correctly classified items, causing the targeted DL network to misclassify them. We show that plain adversarial noise is insufficient to achieve secure CAPTCHA schemes, which leads us to introduce immutable adversarial noise - an adversarial noise resistant to removal attempts. We implement a proof of concept system and its analysis shows that the scheme offers high security and good usability compared to the best existing CAPTCHAs.

Physically Unclonable Functions (PUFs) have been an emerging topic in hardware security and trust in recent years, and many different kinds of PUFs have been presented in the literature. An important criterion is always the diversity of PUF responses for different devices, called inter-device uniqueness. A very popular uniqueness metric consists of calculating the pairwise hamming distance between the response bit-strings of all devices, assuming that all response bits are uncorrelated. Such correlations, however, should be regarded when a statement about inter-device uniqueness is made. We therefore propose a novel correlation metric to fulfil this requirement. Furthermore, we show that the hamming distance metric is actually redundant when at the same time the also popular bit-aliasing metric is applied.

Log files are the primary source of information when the past peration of a computing system needs to be determined. Keeping correct and accurate log files is importantfor after-the-fact forensics, as well as for system administration, maintenance, and auditing. Therefore, a line of research has emerged on how to cryptographically protect the integrity of log files even against intruders who gain control of the logging machine. We contribute to this line of research by devising a scheme where one can verify integrity not only of the log file as a whole, but also of excerpts. This is helpful in various scenarios, including cloud provider auditing.

Although Bitcoin is often perceived to be an anonymous currency, research has shown that a user's Bitcoin transactions can be linked to compromise the user's anonymity. We present solutions to the anonymity problem for both transactions on Bitcoin's blockchain and off the blockchain (in so called micropayment channel networks). We use an untrusted third party to issue anonymous vouchers which users redeem for Bitcoin. Blind signatures and Bitcoin transaction contracts (aka smart contracts) ensure the anonymity and fairness during the bitcoin $\leftrightarrow$ voucher exchange. Our schemes are practical, secure and anonymous.

We describe the design, implementation, and evaluation of Popcorn, a media delivery system that hides clients' consumption (even from the content distributor). Popcorn relies on a powerful cryptographic primitive: private information retrieval (PIR). With novel refinements that leverage the properties of PIR protocols and media streaming, Popcorn scales to the size of Netflix's library (8000 movies) and respects current controls on media dissemination. The dollar cost to serve a media object in Popcorn is 3.87 times that of a non-private system.

FIDO, German e-ID, Idemix and U-Prove constitute privacy-enhanced public-key infrastructures allowing users to authenticate in an anonymous way. This however hampers timely revocation in a privacy friendly way. From a legal perspective, revocation typically should be effective within 24 hours after user reporting. It should also be backward unlinkable, i.e. user anonymity cannot be removed after revocation. We describe a new, generic revocation mechanism based on pairing based encryption and apply it to supplement the systems mentioned. This allows for both flexible and privacy friendly revocation. Protocol execution takes less than a quarter of a second on modern smartcards. An additional property is that usage after revocation is linkable, allowing users to identify fraudulent usage after revocation. Our technique is the first Verifier Local Revocation scheme with backwards unlinkable revocation for the systems mentioned. This also allows for a setup resembling the well-known Online Certificate Status Protocol (OCSP). Here the service provider sends a pseudonym to a revocation provider that returns its status. As the information required for this is not secret the status service can be distributed over many cloud services. In addition to the status service our technique also supports the publication of a central revocation list.

As the new SHA-3 standard, the security and reliability of Keccak have attracted a lot of attentions. Previous works already show that both software and hardware implementations of Keccak have strong side-channel power (electromagnetic) leakages, and these leakages can be easily used by attackers to recover secret key bits. Meanwhile, Keccak is vulnerable to random errors and injected faults, which will cause errors in the computation results. In this paper, we introduce a scheme based on the round rotation invariance property of Keccak to reduce the side-channel leakages while improve its reliability. The proposed scheme is resource friendly. Side-channel analysis results show that this method can efficiently reduce the side-channel leakages of Keccak implementations. Meanwhile, fault injection simulation results show that the proposed scheme can effectively improve the reliability of Keccak implementation, with error coverage almost 100%.

We describe the use of secure multi-party computation for performing a large-scale privacy-preserving statistical study on real government data. In 2015, statisticians from the Estonian Center of Applied Research (CentAR) conducted a big data study to look for correlations between working during university studies and failing to graduate in time. The study was conducted by linking the database of individual tax payments from the Estonian Tax and Customs Board and the database of higher education events from the Ministry of Education and Research. Data collection, preparation and analysis were conducted using the Sharemind secure multi-party computation system that provided end-to-end cryptographic protection to the analysis. Using ten million tax records and half a million education records in the analysis, this is the largest cryptographically private statistical study ever conducted on real data.

We identify two attacks on the Network Time Protocol (NTP)'s cryptographically-authenticated broadcast mode. First, we present a replay attack that allows an on-path attacker to indefinitely stick a broadcast client to a specific time. Second, we present a denial-of-service (DoS) attack that allows an off-path attacker to prevent a broadcast client from ever updating its system clock; to do this, the attacker sends the client a single malformed broadcast packet per query interval. Our DoS attack also applies to all other NTP modes that are `ephemeral' or `preemptable' (including manycast, pool, etc). We then use network measurements to give evidence that NTP's broadcast and other ephemeral/preemptable modes are being used in the wild. We conclude by discussing why NTP's current implementation of symmetric-key cryptographic authentication does not provide security in broadcast mode, and make some recommendations to improve the current state of affairs.

Digital currencies like Bitcoin rely on cryptographic primitives to operate. However, past experience shows that cryptographic primitives do not last forever: increased computational power and advanced cryptanalysis cause primitives to break frequently, and motivate the development of new ones. It is therefore crucial for maintaining trust in a crypto currency to anticipate such breakage. We present the first systematic analysis of the effect of broken primitives on Bitcoin. We identify the core cryptographic building blocks and analyze the various ways in which they can break, and the subsequent effect on the main Bitcoin security guarantees. Our analysis reveals a wide range of possible effects depending on the primitive and type of breakage, ranging from minor privacy violations to a complete breakdown of the currency. Our results lead to several observations on, and suggestions for, the Bitcoin migration plans in case of broken cryptographic primitives.

SSL/TLS is the de facto protocol for providing secure communication over the Internet. It relies on the Web PKI model for authentication and secure key exchange. Despite its relatively successful past, the number of Web PKI incidents observed have increased recently. These incidents revealed the risks of forged certificates issued by certificate authorities without the consent of the domain owners. Several solutions have been proposed to solve this problem, but no solution has yet received widespread adaption due to complexity and deployability issues. In this paper, we propose a practical mechanism that enables servers to get their certificate views across the Internet, making detection of a certificate substitution attack possible. The origin of the certificate substitution attack can also be located by this mechanism. We have conducted simulation experiments and evaluated our proposal using publicly available, real-world BGP data. We have obtained promising results on the AS-level Internet topology.

This paper compares attack outcomes w.r.t. profiled single trace attacks of four different lightweight ciphers in order to investigate which of their properties, if any, contribute to attack success. We show that mainly the diffusion properties of both the round function and the key schedule play a role. In particular, the more (reasonably statistically independent) intermediate values are produced in a target implementation, the better attacks succeed. A crucial aspect for lightweight ciphers is hence the key schedule which is often designed to be particularly light. This design choice implies that information from all round keys can be easily combined which results in attacks that succeed with ease.

Test generation for \emph{Hardware Trojan Horses} (HTH) detection is extremely challenging, as Trojans are designed to be triggered by very rare logic conditions at internal nodes of the circuit. In this paper, we propose a \textit{Genetic Algorithm} (GA) based Automatic Test Pattern Generation (ATPG) technique, enhanced by automated solution to an associated \textit{Boolean Satisfiability} problem. The main insight is that given a specific internal trigger condition, it is not possible to attack an arbitrary node (payload) of the circuit, as the effect of the induced logic malfunction by the HTH might not get propagated to the output. Based on this observation, a fault simulation based framework has been proposed, which enumerates the feasible payload nodes for a specific triggering condition. Subsequently, a compact set of test vectors is selected based on their ability to detect the logic malfunction at the feasible payload nodes, thus increasing their effectiveness. Test vectors generated by the proposed scheme were found to achieve higher detection coverage over large population of HTH in ISCAS benchmark circuits, compared to a previously proposed logic testing based Trojan detection technique.

In [13.] Dutch government proposes an identity scheme supporting personal data exchange of pupils with private e-textbook publishers. This design propagates sharing personal numbers of pupils among private parties violating the data minimisation principle in privacy laws. We describe a privacy friendly alternative, giving pupils (and parents) control on exchange of their personal data. Three generic forms based on homomorphic encryption are used as building blocks. These forms do not yield personal numbers, or even personal data from a legal perspective, and have strong, unlinkability properties. Only if required a school provides a party with a party-specific {\em pseudonym} identifying a pupil. For this the school is provided an {\em encrypted pseudonym} by a central party based on a {\em polymorphic pseudonym} formed by the school. Only intended parties, not even schools, have access to pseudonyms. Different publishers can send pupil test results to a school without being able to assess whether pupils are identical. We also describe support for privacy friendly attributes and user inspection as required by privacy laws.

In this report we describe our efforts in analysing log files produced by the Estonian i-voting system in the KOV2013, EP2014 and RK2015 elections in combination with other information available, so as to detect attacks against the i-voting system, detect system malfunctions and study voter behaviour.

Current cryptocurrencies, starting with Bitcoin, build a decentralized blockchain based transaction ledger, maintained through proofs-of-work that also serve to generate a monetary supply. Such decentralization has benefits, such as independence from national political control, but also significant limitations in terms of computational costs and scalability. We introduce RSCoin, a cryptocurrency framework in which central banks maintain complete control over the monetary supply, but rely on a distributed set of authorities, or mintettes, to prevent double-spending. While monetary policy is centralized, RSCoin still provides strong transparency and auditability guarantees. We demonstrate, both theoretically and experimentally, the benefits of a modest degree of centralization, such as the elimination of wasteful hashing and a scalable system for avoiding double-spending attacks.

We introduce a homomorphic batching technique that can be used to pack multiple ciphertext messages into one ciphertext for parallel processing. One is able to use the method to batch or unbatch messages homomorphically to further improve the flexibility of encrypted domain evaluations. In particular, we show various approaches to implement Number Theoretic Transform (NTT) homomorphically in FFT speed. Also, we present the limitations that we encounter in application of these methods. We implement homomorphic batching in various settings and present concrete performance figures. Finally, we present an implementation of a homomorphic NTT method which we process each element in an independent ciphertext. The advantage of this method is we are able to batch independent homomorphic NTT evaluations and achieve better amortized time.

With the rapid progress in fully homomorpic encryption (FHE) and somewhat homomorphic encryption (SHE) schemes, we are wit- nessing renewed efforts to revisit privacy preserving protocols. Several works have already appeared in the literature that provide solutions to these problems by employing FHE or SHE techniques. These applications range from cloud computing to computation over confidential patient data to several machine learning problems such as classifying privatized data. One application where privacy is a major concern is web search – a task carried out on a daily basis by billions of users around the world. In this work, we focus on a more surmountable yet essential version of the search problem, i.e. autocomplete. By utilizing a SHE scheme we propose concrete solutions to a homomorphic autocomplete problem. To investigate the real-life viability, we tackle a number of problems in the way towards a practical implementation such as communication and computational efficiency.

Instead of simply using two-dimensional $User \times Item$ features, advanced recommender systems rely on more additional dimensions (e.g. time, location, social network) in order to provide better recommendation services. In the first part of this paper, we will survey a variety of dimension features and show how they are integrated into the recommendation process. When the service providers collect more and more personal information, it brings great privacy concerns to the public. On another side, the service providers could also suffer from attacks launched by malicious users who want to bias the recommendations. In the second part of this paper, we will survey attacks from and against recommender service providers, and existing solutions.

This paper describes a smart contract programming lab conducted in our undergraduate security class at the University of Maryland. Through our experiences, we have gained various insights on why it is difficult to create a safe smart contract. This lab also led to new insights for cybersecurity education.

In this article we present how we can use fast F_{p²} multiplication to speed-up arithmetic on elliptic curves. We use parallel computations for multiplication in F_{p²} which is not much slower than multiplication in F_{p}. We show two applications of this method. In the first we show that using twisted Edwards curves over F_{p²} with fast computable endomorphism (GLV-GLS method) may be nowadays on of the fastest (or even the fastest) solution in hardware applications. In the second we show how we can speed-up point scalar multiplication on NIST P-224 and NIST P-256 curves. We use field extension (F_{p²}) to find isomorphic to these curves twisted Hessian curves over F_{p²}. Our solution is faster than classic solutions up to 28.5% for NIST P-256 and up to 27.2% for NIST P-224 if we consider solution invulnerable for side channel attacks. We can also use different formula for point doubling and points addition and then our solution is faster up to 21.4% for NIST P-256 and up to 19.9% for NIST P-224 comparing to classic solutions.

End-to-end verifiable voting schemes typically involves voters handling an encrypted ballot in order to confirm that their vote is accurately included in the tally. While this may be technically valid, from a public acceptance standpoint is may be problematic: many voters may not really understand the purpose of the encrypted ballot and the various checks that they can perform. In this paper we take a different approach and revisit an old idea: to provide each voter with a private tracking number. Votes are posted on a bulletin board in the clear along with their associated tracking number. This is appealing in that it provides voters with a very simple, intuitive way to verify their vote, in the clear. However, there are obvious drawbacks: we must ensure that no two voters are assigned the same tracker and we need to keep the trackers private. In this paper, we propose a scheme that addresses both of these problems: we ensure that voters get unique trackers and we close off the coercer's window of opportunity by ensuring that the voters only learn their tracking numbers after votes have been posted. The resulting scheme provides receipt-freeness, and indeed a good level of coercion-resistance while also providesinga more immediately understandable form of verifiability. The cryptographyis under the bonnet as far as the voter is concerned. The basic scheme still has a problem in some contexts: if the coercer is himself a voter there is a chance that the coerced voter might light on the coercer's tracker, or the coercer simply claims that it is his. We argue that in many contexts this may be an acceptable threat when weighed against the more transparent verification provided by the scheme. Nonetheless, we describe some elaborations of the basic scheme to mitigate such threats.

A silicon Physical Unclonable Function (PUF) is a hardware security primitive which implements a unique and unclonable function on a chip which, given a challenge as input, computes a response by measuring and leveraging (semiconductor process) manufacturing variations which differ from PUF to PUF. In this paper, we observe that by equipping a PUF with a small, constant-sized, tamper-resistant state, whose content cannot be modified, but can be read by adversaries, new and powerful cryptographic applications of PUFs become feasible. In particular, we show a new hardware concept which we call a Programmable Logically erasable PUF (PLayPUF). Its distinctive feature is that it allows the selective erasure of single challenge-response pairs (CRPs) without altering any other PUF-CRPs. The selective erasure of a CRP can be programmed a-priori by using a counter to indicate how many times the CRP can be read out before erasure. We show PLayPUFs can realize forward and {\it backward} secure key management schemes for public key encryption. The new notion of backward security informally means that even if an attacker uncovers a session key through the key management interface, the legitimate user will detect this leakage before he will ever use the session key. Backward security and its implementation via PLayPUFs allow the construction of novel, self-recovering certificate authorities (CAs) without relying on a digital master key. Our new CAs immediately detect key exposure through their interfaces, and recover from it without stopping their service, and without ever issuing certificates based on such exposed keys. This is a crucial step forward in implementing secure key management. We deliver a full proof-of-concept implementation of our new scheme on FPGA together with detailed performance data, as well as formal definitions of our new concepts, including the first definition of stateful PUFs.

In this paper we analyze three methods to detect cache-based side-channel attacks in real time, preventing or limiting the amount of leaked information. Two of the three methods are based on machine learning techniques and all the three of them can successfully detect an attacker in about one fifth of the time required to complete the attack. There were no false positives in our test environment. Moreover we could not measure a change in the execution time of the processes involved in the attack, meaning there is no perceivable overhead. We also analyze how the detection systems behave with a modified version of one of the spy processes. With some optimization we are confident these systems can be used in real world scenarios.

Bitcoin is the first decentralized crypto-currency that is currently by far the most popular one in use. The bitcoin transaction syntax is expressive enough to setup digital contracts whose fund transfer can be enforced automatically. In this paper, we design protocols for the bitcoin voting problem, in which there are n voters, each of which wishes to fund exactly one of two candidates A and B. The winning candidate is determined by majority voting, while the privacy of individual vote is preserved. Moreover, the decision is irrevocable in the sense that once the outcome is revealed, the winning candidate is guaranteed to have the funding from all n voters. As in previous works, each voter is incentivized to follow the protocol by being required to put a deposit in the system, which will be used as compensation if he deviates from the protocol. Our solution is similar to previous protocols used for lottery, but needs an additional phase to distribute secret random numbers via zero-knowledge-proofs. Moreover, we have resolved a security issue in previous protocols that could prevent compensation from being paid.

The rapid development of genome sequencing technology allows researchers to access large genome datasets. However, outsourcing the data processing to the cloud poses high risks for personal privacy. The aim of this paper is to give a practical solution for this problem using homomorphic encryption. In our approach, all the computations can be performed in an untrusted cloud without requiring the decryption key or any interaction with the data owner, which preserves the privacy of genome data. In this paper, we present evaluation algorithms for secure computation of the minor allele frequencies and chi-squared statistic in a genome-wide association studies setting. We also describe how to privately compute the Hamming distance and approximate Edit distance between encrypted DNA sequences. Finally, we compare performance details of using two practical homomorphic encryption schemes - the BGV scheme by Gentry, Halevi and Smart and the YASHE scheme by Bos, Lauter, Loftus and Naehrig. Such an approach with the YASHE scheme analyzes data from 400 people within about 2 seconds and picks a variant associated with disease from 311 spots. For another task, using the BGV scheme, it took about 65 seconds to securely compute the approximate Edit distance for DNA sequences of size 5K and figure out the differences between them.

Motivated by the security and functional limitations of satellite positioning systems, we explore a design of a Wide-Area Secure Positioning System. The main goals of this system are strong spoofing resilience, location verification, and privacy. We propose a realization of a Wide-Area Secure Positioning System and show that this solution is viable and can fulfill our defined security goals. Specifically, our system is composed of a secure positioning infrastructure to obtain reliable location information of an entity and a location verification architecture that allows others to be convinced of certain location properties of such an entity. The proposed system enables the verification of location claims in a privacy-preserving manner, thus enhancing existing security solutions and supporting future location-based applications.

This paper describes the forensic analysis of what the authors believe to be the most sophisticated smart card fraud encountered to date. In 2010, Murdoch et al. [7] described a man-in-the-middle attack against EMV cards. [7] demonstrated the attack using a general purpose FPGA board, noting that miniaturization is mostly a mechanical challenge, and well within the expertise of criminal gangs. This indeed happened in 2011, when about 40 sophisticated card forgeries surfaced in the field. These forgeries are remarkable in that they embed two chips wired top-to-tail. The first chip is clipped from a genuine stolen card. The second chip plays the role of the man-in-the-middle and communicates directly with the point of sale (PoS) terminal. The entire assembly is embedded in the plastic body of yet another stolen card. The forensic analysis relied on X-ray chip imaging, side-channel analysis, protocol analysis, and microscopic optical inspections.

A recent trend in cryptography is to construct cryptosystems that are secure against physical attacks. Such attacks are usually divided into two classes: the \emph{leakage} attacks in which the adversary obtains some information about the internal state of the machine, and the \emph{tampering} attacks where the adversary can modify this state. One of the popular tools used to provide tamper-resistance are the \emph{non-malleable codes} introduced by Dziembowski, Pietrzak and Wichs (ICS 2010). These codes can be defined in several variants, but arguably the most natural of them are the information-theoretically secure codes in the k-split-state model (the most desired case being k=2). Such codes were constucted recently by Aggarwal et al.~(STOC 2014). Unfortunately, unlike the earlier, computationally-secure constructions (Liu and Lysyanskaya, CRYPTO 2012) these codes are not known to be resilient to leakage. This is unsatisfactory, since in practice one always aims at providing resilience against both leakage and tampering (especially considering tampering without leakage is problematic, since the leakage attacks are usually much easier to perform than the tampering attacks). In this paper we close this gap by showing a non-malleable code in the $2$-split state model that is secure against leaking almost a $1/12$-th fraction of the bits from the codeword (in the bounded-leakage model). This is achieved via a generic transformation that takes as input any non-malleable code $(\Enc,\Dec)$ in the $2$-split state model, and constructs out of it another non-malleable code $(\Enc',\Dec')$ in the $2$-split state model that is additionally leakage-resilient. The rate of $(\Enc',\Dec')$ is linear in the rate of $(\Enc,\Dec)$. Our construction requires that $\Dec$ is \emph{symmetric}, i.e., for all $x, y$, it is the case that $\Dec(x,y) = \Dec(y,x)$, but this property holds for all currently known information-theoretically secure codes in the $2$-split state model. In particular, we can apply our transformation to the code of Aggarwal et al., obtaining the first leakage-resilient code secure in the split-state model. Our transformation can be applied to other codes (in particular it can also be applied to a recent code of Aggarwal, Dodis, Kazana and Obremski constructed in the work subsequent to this one).

Modular reduction is the basic building block of many public-key cryptosystems. BCH codes require repeated polynomial reductions modulo the same constant polynomial. This is conceptually very similar to the implementation of public-key cryptography where repeated modular reduction in $\mathbb{Z}_n$ or $\mathbb{Z}_p$ are required for some fixed $n$ or $p$. It is hence natural to try and transfer the modular reduction expertise developed by cryptographers during the past decades to obtain new BCH speed-up strategies. Error correction codes (ECCs) are deployed in digital communication systems to enforce transmission accuracy. BCH codes are a particularly popular ECC family. This paper generalizes Barrett's modular reduction to polynomials to speed-up BCH ECCs. A BCH$(15,7,2)$ encoder was implemented in Verilog and synthesized. Results show substantial improvements when compared to traditional polynomial reduction implementations. We present two BCH code implementations (regular and pipelined) using Barrett polynomial reduction. These implementations, are respectively 4.3 and 6.7 faster than an improved BCH LFSR design. The regular Barrett design consumes around 53$\%$ less power than the BCH LFSR design, while the faster pipelined version consumes 2.3 times more power than the BCH LFSR design.

A Bitcoin wallet is a set of private keys known to a user and which allow that user to spend any Bitcoin associated with those keys. In a hierarchical deterministic (HD) wallet, child private keys are generated pseudorandomly from a master private key, and the corresponding child public keys can be generated by anyone with knowledge of the master public key. These wallets have several interesting applications including Internet retail, trustless audit, and a treasurer allocating funds among departments. A specification of HD wallets has even been accepted as Bitcoin standard BIP32. Unfortunately, in all existing HD wallets---including BIP32 wallets---an attacker can easily recover the master private key given the master public key and any child private key. This vulnerability precludes use cases such as a combined treasurer-auditor, and some in the Bitcoin community have suspected that this vulnerability cannot be avoided. We propose a new HD wallet that is not subject to this vulnerability. Our HD wallet can tolerate the leakage of up to m private keys with a master public key size of O(m). We prove that breaking our HD wallet is at least as hard as the so-called ``one more'' discrete logarithm problem.

While much has changed in Internet security over the past decades, textual passwords remain as the dominant method to secure user web accounts and they are proliferating in nearly every new web services. Nearly every web services, no matter new or aged, now enforce some form of password creation policy. In this work, we conduct an extensive empirical study of 50 password creation policies that are currently imposed on high-profile web services, including 20 policies mainly from US and 30 ones from mainland China. We observe that no two sites enforce the same password creation policy, there is little rationale under their choices of policies when changing policies, and Chinese sites generally enforce more lenient policies than their English counterparts. We proceed to investigate the effectiveness of these 50 policies in resisting against the primary threat to password accounts (i.e. online guessing) by testing each policy against two types of weak passwords which represent two types of online guessing. Our results show that among the total 800 test instances, 541 ones are accepted: 218 ones come from trawling online guessing attempts and 323 ones come from targeted online guessing attempts. This implies that, currently, the policies enforced in leading sites largely fail to serve their purposes, especially vulnerable to targeted online guessing attacks.