Many cloud and cryptocurrency applications rely on verifying the integrity of outsourced computations, in which a verifier can efficiently verify the correctness of a computation made by an untrusted prover. State-of-the-art protocols for verifiable computation require that the computation task be expressed as arithmetic circuits, and the number of multiplication gates in the circuit is the primary metric that determines performance. At the present, a programmer could rely on two approaches for expressing the computation task, either by composing the circuits directly through low-level development tools; or by expressing the computation in a high-level program and rely on compilers to perform the program-to-circuit transformation. The former approach is difficult to use but on the other hand allows an expert programmer to perform custom optimizations that minimize the resulting circuit. In comparison, the latter approach is much more friendly to non-specialist users, but existing compilers often emit suboptimal circuits. We present xJsnark, a programming framework for verifiable computation that aims to achieve the best of both worlds: offering programmability to non-specialist users, and meanwhile automating the task of circuit size minimization through a combination of techniques. Specifically, we present new circuit-friendly algorithms for frequent operations that achieve constant to asymptotic savings over existing ones; various globally aware optimizations for short- and long- integer arithmetic; as well as circuit minimization techniques that allow us to reduce redundant computation over multiple expressions. We illustrate the savings in different applications, and show the framework's applicability in developing large application circuits, such as ZeroCash, while minimizing the circuit size as in low-level implementations.

Blockchains and more general distributed ledgers are becoming increasingly popular as efficient, reliable, and persistent records of data and transactions. Unfortunately, they ensure reliability and correctness by making all data public, raising confidentiality concerns that eliminate many potential uses.

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 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 criminal smart contracts (CSCs) can facilitate leakage of confidential information, theft of cryptographic keys, and various real-world crimes (murder, arson, terrorism).

Emerging smart contract systems over decentralized cryptocurrencies allow mutually distrustful parties to transact safely without trusted third parties. In the event of contractual breaches or aborts, the decentralized blockchain ensures that honest parties obtain commensurate compensation. Existing systems, however, lack transactional privacy. All transactions, including flow of money between pseudonyms and amount transacted, are exposed on the blockchain. We present Hawk, a decentralized smart contract system that does not store financial transactions in the clear on the blockchain, thus retaining transactional privacy from the public's view. A Hawk programmer can write a private smart contract in an intuitive manner without having to implement cryptography, and our compiler automatically generates an efficient cryptographic protocol where contractual parties interact with the blockchain, using cryptographic primitives such as zero-knowledge proofs. To formally define and reason about the security of our protocols, we are the first to formalize the blockchain model of cryptography. The formal modeling is of independent interest. We advocate the community to adopt such a formal model when designing applications atop decentralized blockchains.

An implicit goal of Bitcoin's reward structure is to diffuse network influence over a diverse, decentralized population of individual participants. Indeed, Bitcoin's security claims rely on no single entity wielding a sufficiently large portion of the network's overall computational power. Unfortunately, rather than participating independently, most Bitcoin miners join coalitions called mining pools in which a central pool administrator largely directs the pool's activity, leading to a consolidation of power. Recently, the largest mining pool has accounted for more than half of network's total mining capacity. Relatedly, "hosted mining" service providers offer their clients the benefit of economies-of-scale, tempting them away from independent participation. We argue that the prevalence of mining coalitions is due to a limitation of the Bitcoin proof-of-work puzzle -- specifically, that it affords an effective mechanism for enforcing cooperation in a coalition. We present several definitions and constructions for "nonoutsourceable" puzzles that thwart such enforcement mechanisms, thereby deterring coalitions. We also provide an implementation and benchmark results for our schemes to show they are practical.

The widespread usage of WLANs and mobile devices has fostered the interest in localization systems for wireless environments. The majority of research in the context of wireless-based localization systems has focused on device-based active localization, in which devices are attached to tracked entities. Recently, device-free passive localization (DfP) has been proposed where the tracked entity is neither required to carry devices nor to participate actively in the localization process. Previous studies have focused on small areas and/or controlled environments. In this paper, we present the design, implementation, and analysis of Nuzzer, a large-scale DfP localization system, which tracks entities in real environments, rich in multipath. We first present probabilistic techniques for DfP localization of a single entity and evaluate their performance both analytically and in typical office buildings. Our results show that Nuzzer gives location estimates with less than 2-meters median distance error. We then give an algorithm for estimating the number of entities in an area of interest and localizing them into coarse-grained zones to enhance the scalability of the system. This indicates the suitability of Nuzzer to a large number of application domains.

WLAN Device-free passive (DfP) indoor localization is an emerging technology enabling the localization of entities that do not carry any devices nor participate actively in the localization process using the already installed wireless infrastructure. This technology is useful for a variety of applications such as intrusion detection, smart homes and border protection. We present the design, implementation and evaluation of RASID, a DfP system for human motion detection. RASID combines different modules for statistical anomaly detection while adapting to changes in the environment to provide accurate, robust, and low-overhead detection of human activities using standard WiFi hardware. Evaluation of the system in two different testbeds shows that it can achieve an accurate detection capability in both environments with an F-measure of at least 0.93. In addition, the high accuracy and low overhead performance are robust to changes in the environment as compared to the current state of the art DfP detection systems.

Developing a robust and reliable vehicle detection and speed estimation system that alerts drivers about driving conditions and helps them avoid joining traffic jams is an important problem that has attracted lots of attention recently. In this paper, we introduce a novel RF-based vehicle motion detection and speed estimation system (ReVISE). Our system leverages the fact that the presence of objects in an RF environment affects the received signal strength and hence, can be used to detect and identify different characteristics of the objects in an area of interest. Our long-term vision for ReVISE is to leverage common wireless networks, such as WiFi or cellular, to detect the density of traffic and estimate the car speed based on the mobile devices carried by users. This gives us an edge over the current techniques for traffic estimation as we do not require any specialized hardware and the cellular signal strength information is available from all cell phones, providing large-scale ubiquitous traffic estimation. We present the design and analysis of ReVISE including its vehicle detection and speed estimation modules. The detection module can differentiate between an empty street, stationary cars, and moving cars based on a multi-class SVM approach that uses features from the RF signal strength. We also present two novel speed estimation techniques based on statistical and curve fitting approaches. Evaluation of ReVISE in a real testbed shows that the proposed techniques can detect vehicle motion with an accuracy of 100% and estimate the vehicle speed with an accuracy of 90% in typical streets. This highlights the feasibility and promise of using RF for vehicle detection and speed estimation.

WLAN Device-free Passive (DfP) localization is an emerging technology that uses the widely deployed WiFi networks for detecting and localizing human presence within indoor environments. This paper presents an accurate and low-overhead technique for detecting human presence based on non-parametric statistical anomaly detection. This technique constructs profiles capturing the signal strength characteristics when no human is present within the area of interest and uses these profiles to identify any anomalies in the signal strength due to human motion activity. To adapt to changes in the environment, the constructed profiles are regularly updated by signal strength readings with low anomaly probability. Exponential smoothing is then used to reduce the effect of noisy readings in order to enhance the detection accuracy. Our work proved to be more robust and accurate than other DfP detection techniques, achieving a high detection accuracy of 4.7% miss detection rate and 3.8% false alarm rate, while requiring minimal deployment overhead.