We introduce the WIDESEAS protocol for lattice-based Private Information Retrieval (PIR), and we give performance numbers for its recent implementation in the EncryptedQuery open-source PIR software. This protocol uses the fully homomorphic Brakerski--Fan--Vercauteren (BFV) encryption scheme, as opposed to the Paillier scheme, which is used in all earlier versions of EncryptedQuery. We show that the homomorphic capabilities of BFV result in smaller query sizes (due to a query-shrinking technique based on batching and ciphertext multiplication), higher response generation rates (due to using relinearization to keep ciphertexts small; due to caching certain products of query elements in the NTT domain; due to using the distributive law to achieve a quadratic reduction in the total number of ciphertext multiplications; due to using lazy reduction to speed up modular multiplies; and, due to exploiting properties of inverse NTTs over periodic data, and forward NTTs over sparse data, for the purpose of accelerating plain multiplications), and comparable response sizes (due to using modulus switching to discard redundant ciphertext information prior to transmitting the response). For instance, running a single thread (with Turbo Boost disabled) on a MacBook Pro equipped with a 2.8 GHz Intel core i7, and using a $20$-bit hash and a $2^{15}$-byte data chunk size (which allows us to search for a single targeted selector), our implementation can (i) generate a query of size $64\ \mathrm{MiB}$ in around $0.41\ {\rm seconds,}$ (ii) process a query against a $1\ \mathrm{TiB}$ database (comprised of $2^{20}$-many $1\ \mathrm{MiB}$ records) at a rate of $23.67\ \mathrm{MiB/s}$ (which is at least two orders of magnitude faster than the Paillier-based version of EncryptedQuery), and (iii) generate a response of size $4\ \mathrm{MiB}$ in around $0.51\ \mathrm{days}{\rm .}$ We expect a speed up on server class machines. Our implementation uses the Microsoft SEAL library along with a small amount of custom code.

In this work, we demonstrate the use the CKKS homomorphic encryption scheme to train a large number of logistic regression models simultaneously, as needed to run a genome-wide association study (GWAS) on encrypted data. Our implementation can train more than 30,000 models (each with four features) in about 20 minutes. To that end, we rely on a similar iterative Nesterov procedure to what was used by Kim, Song, Kim, Lee, and Cheon to train a single model [KSKLC18]. We adapt this method to train many models simultaneously using the SIMD capabilities of the CKKS scheme. We also performed a thorough validation of this iterative method and evaluated its suitability both as a generic method for computing logistic regression models, and specifically for GWAS.

Logic locking has emerged as a promising solution against IP piracy and modification by untrusted entities in the integrated circuit design process. However, its security is challenged by boolean satisfiability (SAT) based attacks. Criteria that are critical to SAT attack success on obfuscated circuits includes scan architecture access to the attacker and/or that the circuit under attack is combinational. To address this issue, we propose a dynamically-obfuscated scan chain (DOSC) technique in resisting SAT attack in an obfuscated sequential design by restricting scan access only to authorized users.

Experience shows that most researchers and developers tend to treat plain-domains (those that are not prefixed with “www” sub-domains, e.g. “example.com”) as synonyms for their equivalent www-domains (those that are prefixed with “www” sub-domains, e.g. “www.example.com”). In this paper, we analyse datasets of nearly two million plain-domains against their equivalent www-domains to answer the following question: Do plain-domains and their equivalent www-domains differ in TLS security configurations and certificates? If so, to what extent? Our results provide evidence of an interesting phenomenon: plain-domains and their equivalent www-domains differ in TLS security configurations and certificates in a non-trivial number of cases. Furthermore, www-domains tend to have stronger security configurations than their equivalent plain-domains. Interestingly, this phenomenon is more prevalent in the most-visited domains than in randomly-chosen domains. Further analysis of the top domains dataset shows that 53.35% of the plain-domains that show one or more weakness indicators (e.g. expired certificate) that are not shown in their equivalent www-domains perform HTTPS redirection from HTTPS plain-domains to their equivalent HTTPS www-domains. Additionally, 24.71% of these redirections contains plain-text HTTP intermediate URLs. In these cases, users see the final www-domains with strong TLS configurations and certificates, but in fact, the HTTPS request has passed through plain-domains that have less secure TLS configurations and certificates. Clearly, such a set-up introduces a weak link in the security of the overall interaction.

Homomorphic Encryption is a breakthrough technology which can enable private cloud storage and computation solutions, and many applications have been described in the literature in the last few years. But before Homomorphic Encryption can be adopted in medical, health, and financial sectors to protect data and patient and consumer privacy, it will have to be standardized, most likely by multiple standardization bodies and government agencies. An important part of standardization is broad agreement on security levels for varying parameter sets. Although extensive research and benchmarking has been done in the research community to establish the foundations for this effort, it is hard to find all the information in one place, along with concrete parameter recommendations for applications and deployment. This document is the first Homomorphic Encryption Standard (HES) approved by the Homomorphicencryption.org community in 2018. It captures the collective knowledge on the state of security of these schemes, specifies the schemes, and recommends a wide selection of parameters to be used for homomorphic encryption at various security levels. We describe known attacks and their estimated running times in order to make these security parameter recommendations.

The increasing communication capabilities of vehicles are paving the way for promising road safety and traffic management applications. But the rise of connected vehicles also potentially introduces many security and privacy concerns. Thus, a vision of a successful cooperative vehicular network relies on strong security properties. Proposals such as the Security Credential Management System (SCMS) fulfil these security requirements with the concept of pseudonym certificates, relying on large-scale PKI. But since the on-board units performing these cryptographic operations are usually resource-constrained devices, it is important to consider ways to optimize and devise efficient implementations of the proposed algorithms. In this work, we study optimizations on the mathematical and algorithmic aspects of the validation of implicit certificates and the verification of ECDSA signatures used in the SCMS. We propose efficient algorithms to validate batches of implicit certificates, providing significant savings compared to the sequential validation of the individual certificates. We also propose optimizations to the verification of ECDSA signatures when the verification is performed with an implicit certificate. Although we focus our work on the SCMS and V2X communications, our contributions are more general and apply to every system combining ECQV and ECDSA.

At present, the access control schemes in the power grid are centralized. In the centralized system, the data of the network sensor nodes is transmitted by centralized nodes, and the data itself may be illegally tamped with or lost, which can lead to reduced system reliability. For this feature, we apply blockchain technology to the design of access control schemes. In this paper, we propose a blockchain-based access control scheme that is suitable for multiple scenarios in the smart grid. Our access control scheme is based on an identity-based combined encryption, signature and signcryption scheme. In addition, we design a consensus algorithm in the power system for the consortium blockchain architecture to solve the key escrow problem of the untrusted third parties. Our scheme also ensures the confidentiality, integrity, authentication and non-repudiation of the data. Compared with the existing work, our scheme can use the same key pair to encrypt, sign and signcrypt the message, which has lower computation and communication costs in multiple scenarios of smart grids.

In order to propagate transactions and blocks, today’s blockchain systems rely on unstructured peer-to-peer overlay networks. In such networks, broadcast is known to be an inefficient operation in terms of message complexity and overhead. In addition to the impact on the system performance, inefficient or delayed block propagation may have severe consequences regarding security and fairness of the consensus layer. Therefore, we introduce Kadcast, a novel peer-to-peer protocol for block propagation in blockchain networks. Kadcast utilizes the well-known structured overlay topology of Kademlia to realize an efficient broadcast operation with tunable overhead. As our protocol is based on UDP, we incorporate forward error correction (FEC) to increase reliability while still maintaining its lightweight protocol architecture. To this end, we build a probabilistic model to analyze Kadcast’s resilience to packet losses as well as random and adversarial node failures. Moreover, we evaluate Kadcast’s block delivery performance, broadcast reliability, efficiency, and security based on advanced network simulations, which confirm the merits of the Kadcast protocol.

One way of investigating how genes affect human traits would be with a genome-wide association study (GWAS). Genetic markers, known as single-nucleotide polymorphism (SNP), are used in GWAS. This raises privacy and security concerns as these genetic markers can be used to identify individuals uniquely. This problem is further exacerbated by a large number of SNPs needed, which produce reliable results at a higher risk of compromising the privacy of participants. We describe a method using homomorphic encryption (HE) to perform GWAS in a secure and private setting. This work is based on a semi-parallel logistic regression algorithm proposed to accelerate GWAS computations. Our solution involves homomorphically encrypted matrices and suitable approximations that adapts the original algorithm to be HE-friendly. Our best implementation took $24.70$ minutes for a dataset with $245$ samples, $4$ covariates and $10643$ SNPs. We demonstrate that it is possible to achieve GWAS with homomorphic encryption with suitable approximations.

Intel SGX enables protected enclaves on untrusted computing platforms. An important part of SGX is its remote attestation mechanism that allows a remote verifier to check that the expected enclave was correctly initialized before provisioning secrets to it. However, SGX attestation is vulnerable to relay attacks where the attacker, using malicious software on the target platform, redirects the attestation and therefore the provisioning of confidential data to a platform that he physically controls. Although relay attacks have been known for a long time, their consequences have not been carefully examined. In this paper, we analyze relay attacks and show that redirection increases the adversary's abilities to compromise the enclave in several ways, enabling for instance physical and digital side-channel attacks that would not be otherwise possible. %We also explain why commonly suggested solutions like trust on first use (TOFU) are inadequate to prevent relay attacks. We propose ProximiTEE, a novel solution to prevent relay attacks. Our solution is based on a trusted embedded device that is attached to the target platform. Our device verifies the proximity of the attested enclave, thus allowing attestation to the intended enclave regardless of malicious software, such as a compromised OS, on the target platform. The device also performs periodic proximity verification which enables secure enclave revocation by detaching the device. Although proximity verification has been proposed as a defense against relay attacks before, this paper is the first to experimentally demonstrate that it can be secure and reliable for TEEs like SGX. Additionally, we consider a stronger adversary that has obtained leaked SGX attestation keys and emulates an enclave on the target platform. To address such emulation attacks, we propose a second solution where the target platform is securely initialized by booting it from the attached embedded device.

IoT systems are vulnerable to various cyber attacks as they form a subset of the In- ternet. Insider attacks find more significance since many devices are configured to access the Internet without intrusion detection systems or firewalls in place. The current work focuses on three insider attacks, namely, blackhole attack, sinkhole attack and wormhole attack. A distrib - uted trust based intrusion detection system is proposed to detect these attacks. The trust scores are compared with those existing in immutable distributed ledger and used to arrive at a deci- sion to include or exclude a node.

The Lightning Network is a second layer technology running on top of Bitcoin and other Blockchains. It is composed of a peer-to-peer network, used to transfer raw information data. Some of the links in the peer-to-peer network are identified as payment channels, used to conduct payments between two Lightning Network clients (i.e., the two nodes of the channel). Payment channels are created with a fixed credit amount, the channel capacity. The channel capacity, together with the IP address of the nodes, is published to allow a routing algorithm to find an existing path between two nodes that do not have a direct payment channel. However, to preserve users' privacy, the precise balance of the pair of nodes of a given channel (i.e. the bandwidth of the channel in each direction), is kept secret. Since balances are not announced, second-layer nodes probe routes iteratively, until they find a successful route to the destination for the amount required, if any. This feature makes the routing discovery protocol less efficient but preserves the privacy of channel balances. In this paper, we present an attack to disclose the balance of a channel in the Lightning Network. Our attack is based on performing multiple payments ensuring that none of them is finalized, minimizing the economical cost of the attack. We present experimental results that validate our claims, and countermeasures to handle the attack.

Location data is an important piece of contextual information in location-driven features for geosocial and pervasive computing applications. In this paper, we propose to geo-hash locations using space-filling curves, which are dimension reduction techniques that preserve locality. The proposed location referencing method is agnostic to specific maps or precoded location models and can effectively preserve users’ location privacy based on user preferences. We employ post-quantum-secure encryption on location data and privacy preferences to minimize the risk of data leakage. We also design three algorithms to homomorphically compute geospatial queries on the encrypted location data without revealing either user locations or user preferences. One of the three proposed algorithms reduces the multiplicative depth by more than half; thus, significantly speeding up homomorphic computations. We then present a prototype of the proposed system and algorithms using a somewhat homomorphic encryption scheme and our optimization techniques. A systematic evaluation of the prototype demonstrates its utility in spatial cloaking.

Decision tree and its generalization of random forests are a simple yet powerful machine learning model for many classification and regression problems. Recent works propose how to privately evaluate a decision tree in a two-party setting where the feature vector of the client or the decision tree model (such as the threshold values of its nodes) is kept a secret from another party. However, these works cannot be extended trivially to support the outsourcing setting where a third-party who should not have access to the model or the query. Furthermore, their use of an interactive comparison protocol does not support branching program, hence requires interactions with the client to determine the comparison result before resuming the evaluation task. In this paper, we propose the first secure protocol for collaborative evaluation of random forests contributed by multiple owners. They outsource evaluation tasks to a third-party evaluator. Upon receiving the client’s encrypted inputs, the cloud evaluates obliviously on individually encrypted random forest models and calculates the aggregated result. The system is based on our new secure comparison protocol, secure counting protocol, and a multi-key somewhat homomorphic encryption on top of symmetric-key encryption. This allows us to reduce communication overheads while achieving round complexity lower than existing work.

This article, for the first time, demonstrates Cross-device Deep Learning Side-Channel Attack (X-DeepSCA), achieving an accuracy of $>99.9\%$, even in presence of significantly higher inter-device variations compared to the inter-key variations. Augmenting traces captured from multiple devices for training and with proper choice of hyper-parameters, the proposed 256-class Deep Neural Network (DNN) learns accurately from the power side-channel leakage of an AES-128 target encryption engine, and an N-trace ($N\leq10$) X-DeepSCA attack breaks different target devices within seconds compared to a few minutes for a correlational power analysis (CPA) attack, thereby increasing the threat surface for embedded devices significantly. Even for low SNR scenarios, the proposed X-DeepSCA attack achieves $\sim10\times$ lower minimum traces to disclosure (MTD) compared to a traditional CPA.

Along with blockchain technology, smart contracts have found intense interest in lots of practical applications. A smart contract is a mechanism involving digital assets and some parties, where the parties deposit assets into the contract and the contract redistributes the assets among the parties based on provisions of the smart contract and inputs of the parties. Recently, several smart contract systems are constructed that use zk-SNARKs to provide privacy-preserving payments and interconnections in the contracts (e.g. Hawk [IEEE S&P, 2016] and Gyges [ACM CCS, 2016]). Efficiency of such systems severely are dominated by efficiency of the underlying UC-secure zk-SNARK that is achieved using COCO framework [Kosba et al., 2015] applied on a non-UC-secure zk-SNARK. In this paper, we show that recent progresses on zk-SNARKs, allow one to simplify the structure and also improve the efficiency of both systems with a UC-secure zk-SNARK that has simpler construction and better efficiency in comparison with the currently used ones. To this end, we first show that given a NIZK argument which guarantees non-black-box simulation (knowledge) soundness, one can construct a UC-secure NIZK that has simpler construction and better efficiency than the ones that currently are used in Hawk and Gyges. We believe, new technique can be of independent interest.

Physical Unclonable Functions (PUFs) and, in particular, XOR Arbiter PUFs have gained much research interest as an authentication mechanism for embedded systems. One of the biggest problems of (strong) PUFs is their vulnerability to so called machine learning attacks. In this paper we take a closer look at one aspect of machine learning attacks that has not yet gained the needed attention: the generation of the sub-challenges in XOR Arbiter PUFs fed to the individual Arbiter PUFs. Specifically, we look at one of the most popular ways to generate sub-challenges based on a combination of permutations and XORs as it has been described for the "Lightweight Secure PUF". Previous research suggested that using such a sub-challenge generation increases the machine learning resistance significantly. Our contribution in the field of sub-challenge generation is three-fold: First, drastically improving attack results by Rührmair et al., we describe a novel attack that can break the Lightweight Secure PUF in time roughly equivalent to an XOR Arbiter PUF without transformation of the challenge input. Second, we give a mathematical model that gives insight into the weakness of the Lightweight Secure PUF and provides a way to study generation of sub-challenges in general. Third, we propose a new, efficient, and cost-effective way for sub-challenge generation that mitigates the attack strategy we used and outperforms the Lightweight Secure PUF in both machine learning resistance and resource overhead.

Smart contracts allow for exchange of coins according to program rules. While it is well known that so called bribery contracts can influence the incentive mechanism of a Nakamotostyle consensus, we present a more fine-grained bribery attack incentivizing a temporary censorship against a specific account. To this end, we introduce three different bribery contracts on the blockchain where each uniquely manipulates the rewards that a rational miner would receive. Additionally, we formalize the established bribery mechanisms as a Markov game and show for each game the existence of equilibria leading to successful censorships. Finally, we compare the bribery mechanisms with respect to the scalability of the attack costs and the strategic dominance. Our work is motivated by off-chain protocols including payment and state channels which require to publish transactions within a certain amount of time. In such off-chain protocols a temporary censorship attack can result into significant financial damage.

Permissioned Blockchain has become quite popular with enterprises forming consortium since it prioritizes trust over privacy. One of the popular platforms for distributed ledger solution, Hyperledger Fabric, requires a transaction to be endorsed or approved by a group of special members known as endorsers before undergoing validation. To endorse a transaction, an endorser mentions its identity along with the signature so that it can be verified later. However, for certain transactions, difference in opinion may exist among endorsers. Disclosing the identity of an endorser may lead to conflict within the consortium. In such cases, an endorsement policy which not only allows an endorser to support a transaction discreetly, but at the same time takes into account the decision of the majority is preferred. Thus we propose an Anonymous Endorsement System which uses a threshold endorsement policy in order to address the issue. To realize a t-out-of-n endorsement policy, using any of the existing threshold ring signature for our endorsement system would have violated the privacy of endorsers as either the identity or the secret key of the endorsers get revealed to the party who recombines the signature after collecting each signature share. All these factors motivated us to design a new ring signature scheme, called Fabric's Constant-Sized Linkable Ring Signature (FCsLRS) with Transaction-Oriented linkability for hiding identity of the endorsers. We have implemented the signature scheme in Golang and analyzed its security and performance by varying the RSA (Rivest-Shamir-Adleman) modulus size. Feasibility of implementation is supported by experimental analysis. Signature and tag generation time is quite fast and remains constant irrespective of change in message length or endorsement set size for a given RSA modulus value, assuming all the endorsers generates their signature in parallel. Each verifier is required to count and check individual valid ring signature. If the aggregate is above the threshold value, stated by the endorsement policy, then it confirms that the transaction is valid. This increases the verification time depending on the threshold value, but has very little effect on the scalability since generally $t<<n$. Lastly, we also discuss the integration of the scheme on v1.2 Hyperledger Fabric.

Classification algorithms and tools become more and more powerful and pervasive. Yet, for some use cases, it is necessary to be able to protect data privacy while benefiting from the functionalities they provide. Among the tools that may be used to ensure such privacy, we are focusing in this paper on functional encryption. These relatively new cryptographic primitives enable the evaluation of functions over encrypted inputs, outputting cleartext results. Theoretically, this property makes them well-suited to the process of classification over encrypted data. Indeed, its design enables one to perform the classification algorithm over encrypted inputs (i.e. without knowing the inputs) while only getting the input classes as a result in the clear. In this paper, we study the security and privacy issues of classifiers using today practical functional encryption schemes. We provide an analysis of the information leakage about the input data that are processed in the encrypted domain with state-of-the-art functional encryption schemes. This study, based on experiments ran on two datasets (MNIST and Census Income), shows that neural networks are able to partially recover information that should have been kept secret. Hence, great care should be taken when using the currently available functional encryption schemes to build (seemingly) privacy-preserving classification services. It should be emphasized that this work does not attack the cryptographic security of functional encryption schemes, it rather warns the community against the fact that they should be used with caution for some use cases and that the current state-of-the-art may lead to some operational weaknesses that could be mitigated in the future once more powerful functional encryption schemes are available.

We show that garbled circuits are a practical choice for secure evaluation of neural network classifiers. At the protocol level, we start with the garbling scheme of Ball, Malkin & Rosulek (ACM CCS 2016) for arithmetic circuits and introduce new optimizations for modern neural network activation functions. We develop fancy-garbling, the first implementation of the BMR16 garbling scheme along with our new optimizations, as part of heavily optimized garbled-circuits tool that is driven by a TensorFlow classifier description. We evaluate our constructions on a wide range of neural networks. We find that our approach is up to 100x more efficient than straight-forward boolean garbling (depending on the neural network). Our approach is also roughly 40% more efficient than DeepSecure (Rouhani et al., DAC 2018), the only previous garbled-circuit-based approach for secure neural network evaluation, which incorporates significant optimization techniques for boolean circuits. Furthermore, our approach is competitive with other non-garbled-circuit approaches for secure neural network evaluation.

The basic concept behind the emergence of Internet of Things (IoT) is to connect as many objects to the Internet as possible in an attempt to make our lives better in some way. However, connecting everyday objects like your car or house to the Internet can open up major security concerns. In this paper, we present a novel security framework for the Message Queue Transport Telemetry (MQTT) protocol based on publish/subscribe messages in order to enhance secure and privacy-friendly Internet of Things services. MQTT has burst onto the IoT scene in recent years due to its lightweight design and ease of use implementation necessary for IoT. Our proposed solution provides 3 security levels. The first security level suits for lightweight data exchanges of non-tampered messages. The second security level enhances the privacy protection of data sources and data receivers. The third security level offers robust long-term security with mutual authentication for all parties. The security framework is based on light cryptographic schemes in order to be suitable for constrained and small devices that are widely used in various IoT use cases. Moreover, our solution is tailored to MQTT without using additional security overhead.

Secure multi-party computation (MPC) allows multiple parties to jointly compute the output of a function while preserving the privacy of any individual party's inputs to that function. As MPC protocols transition from research prototypes to real-world applications, the usability of MPC-enabled applications is increasingly critical to their successful deployment and wide adoption. Our Web-MPC platform, designed with a focus on usability, has been deployed for privacy-preserving data aggregation initiatives with the City of Boston and the Greater Boston Chamber of Commerce. After building and deploying an initial version of this platform, we conducted a heuristic evaluation to identify additional usability improvements and implemented corresponding application enhancements. However, it is difficult to gauge the effectiveness of these changes within the context of real-world deployments using traditional web analytics tools without compromising the security guarantees of the platform. This work consists of two contributions that address this challenge: (1) the Web-MPC platform has been extended with the capability to collect web analytics using existing MPC protocols, and (2) this capability has been leveraged to conduct a usability study comparing the two version of Web-MPC (before and after the heuristic evaluation and associated improvements). While many efforts have focused on ways to enhance the usability of privacy-preserving technologies, this study can serve as a model for using a privacy-preserving data-driven approach in evaluating or enhancing the usability of privacy-preserving websites and applications deployed in real-world scenarios. The data collected in this study yields insights about the interplay between usability and security that can help inform future implementations of applications that employ MPC.

Current blockchains are restricted by the low throughput. Aimed at this problem, we propose Txilm, a protocol that compresses the size of transaction presentation in each block and thus saves the bandwidth of the blockchain network. In this protocol, a block carries short hashes of TXIDs instead of complete transactions. Combined with the transaction list sorted by TXIDs, Txilm realizes 80 times of data size reduction compared with the original blockchains. We also evaluate the probability of hash collisions, and provide methods of resolving such collisions. Finally, we design strategies to protect against possible attacks on Txilm.

We reveal Revelio, a new privacy-preserving proof of reserves protocol for Grin exchanges. By design, Revelio allows the detection of collusion between exchanges while hiding the identities of the outputs owned by the exchange in a larger anonymity set of outputs.

ByzCoin, a promising alternative of Bitcoin, is a scalable consensus protocol used as a building block of many research and enterprise-level decentralized systems. In this paper, we show that ByzCoin is unsuitable for deployment in an anopen, adversarial network and instead introduceMOTOR. MOTORis designed as a secure, robust, and scalable consensus suitable for permissionless sharded blockchains. MOTORachieves these properties by making four key design choices: (a) it prioritizes robustness in adversarial environments while maintaining adequate scalability, (b) it employees provably correct cryptography that resists DoS attacks from individual nodes, (c) it deploys unpredictable rotating leaders to defend against mildly-adaptive adversaries and prevents censorship, and (d) it creates an incentive compatible reward mechanism. These choices are materialized as (a) a “rotating subleader” communication pattern that balances the scalability needs with the robustness requirements under failures, (b) deployment of provable secure BLS multi-signatures, (c) use of deterministic thresh-old signatures as a source of randomness and (d) careful design of the reward allocation mechanism. We have implemented MOTORand compare it withByzCoin. We show that MOTORcan scale similar to ByzCoin with an at most2xoverhead whereas it maintains good performance even under high-percentage of faults, unlike ByzCoin.

Voting systems are the tool of choice when it comes to settle an agreement of different opinions. We propose a solution for a trustless, censorship-resilient and scalable electronic voting platform. By leveraging the blockchain together with the functional encryption paradigm, we fully decentralize the system and reduce the risks that a voting provider, like a corrupt government, does censor or manipulate the outcome.

Tor is a network based on the onion routing infrastructure and provides many advantages, including tracking avoidance, research, wider access and, unfortunately, illegal activities. To achieve this, the client will connect to a TOR circuit consisting of nodes chosen under certain restrictions. The purpose of this paper is to draw attention of the narrow range of available and constraints obedient nodes. This is of interest because it impacts the anonymity and the privacy of users and their internet traffic.

Convolutional neural networks (CNNs) is a category of deep neural networks that are primarily used for classifying image data. Yet, their continuous gain in popularity poses important privacy concerns for the potentially sensitive data that they process. A solution to this problem is to combine CNNs with Fully Homomorphic Encryption (FHE) techniques. In this work, we study this approach by focusing on two popular FHE schemes, TFHE and HEAAN, that can work in the approximated computational model. We start by providing an analysis of the noise after each principal homomorphic operation, i.e. multiplication, linear combination, rotation and bootstrapping. Then, we provide a theoretical study on how the most important non-linear operations of a CNN (i.e. max, Abs, ReLU), can be evaluated in each scheme. Finally, we measure via practical experiments on the plaintext the robustness of different neural networks against perturbations of their internal weights that could potentially result from the propagation of large homomorphic noise. This allows us to simulate homomorphic evaluations with large amounts of noise and to predict the effect on the classification accuracy without a real evaluation of heavy and time-consuming homomorphic operations. In addition, this approach enables us to correctly choose smaller and more efficient parameter sets for both schemes.

This paper is focused on an open question regarding the correlation and the power of the NIST statistical test suite. If we found some correlation between these statistical tests, then we can improve the testing strategy by executing only one of the tests that are correlated. Using the Galton-Pearson “product-moment correlation coefficient”, by simulation, we found a high correlation between five couples of this statistical tests: (frequency, cumulative sums forward), (frequency, cumulative sums reverse), (cumulative sums forward, cumulative sums reverse), (random excursions, random excursions variant), and (serial 1, serial 2).

We present a protocol for a cryptoeconomic fair exchange of data previously owned by the purchaser for tokens that functions even when both parties are anonymous. This enables peer-to-peer data storage without identity verification. We use a smart contract on a decentralized ledger as a trusted third party. Actual data transfer can take place with any standard anonymous exchange channel. Due to the anonymity of the parties, the smart contract cannot punish either party's off-ledger reputation. Furthermore, the contract has limited power to arbitrate fault in off-ledger disputes. Thus, an important feature of our protocol is a collateral mechanism that collectively punishes both Alice and Bob if either of them abandons the protocol or cheats. However, we prove that parameters can be chosen such that the collateral can be made, subject to data size, arbitrarily low and still result in an expected financial loss if either Alice or Bob cheats. We are able to achieve this due to our non-standard use of error-correcting codes. In addition, the protocol allows those storing the data to exchange it without the client's participation.

Opaque predicates are a commonly used technique in program obfuscation, intended to add complexity to control flow and to insert dummy code or watermarks. However, there are many attacks known to detect opaque predicates and remove dummy code. We survey these attacks and argue that many types of programs cannot be securely obfuscated using opaque predicates. In particular we explain that most previous works on control flow obfuscation have introduced predicates that are easily distinguished from naturally occurring predicates in code, and hence easily removed by an attacker. We state two conditions that are necessary for a program to be suitable for control flow obfuscation. We give an integrated approach to control flow obfuscation that simultaneously obfuscates real predicates and introduces opaque predicates. The opaque predicates are indistinguishable from the obfuscated real predicates in the program. If an attacker applies the usual approaches (both static and dynamic) to identify and remove opaque predicates then they are likely to remove critical functionality and introduce errors. We have implemented our obfuscator in LLVM. We provide an analysis of the performance of the resulting obfuscated code.

We present CellTree, a new architecture for distributed data repositories. The repository allows data to be stored in largely independent, and highly programmable cells, which are “assimilated” into a tree structure. The data in the cells are allowed to change over time, subject to each cell’s own policies; a cell’s policies also govern how the policies themselves can evolve. A design goal of the architecture is to let a CellTree evolve organically over time, and adapt itself to multiple applications. Different parts of the tree may be maintained by different sets of parties interested in the respective parts, and the core mechanisms used for maintaining the tree can also vary across the tree and over time. We present provable guarantees of liveness, correctness and consistency (the last one being a generalization of the typical blockchain guarantee of “persistence,” when data is dynamic), when the CellTree architecture is instantiated using a simple set of modules. These properties can be guaranteed for individual cells that satisfy requisite trust assumptions, even if these trust assumptions do not hold for other cells in the tree. We also discuss several features of a CellTree that can be exploited by applications. We leave it for future work to develop full-fledged applications on top of this powerful architecture.

One of Bitcoin’s core security guarantees is that, for an attacker to be able to successfully interfere with the Bitcoin network and reverse transactions, they need to control 51% of total hash power. Eyal et al., however, significantly reduces Bitcoin’s security guarantee by introducing another type of attack, called "Selfish Mining". The key idea behind selfish mining is for a miner to keep its discovered blocks private, thereby intentionally forking the chain. As a result of a selfish mining attack, even a miner with 25% of the computation power can bias the agreed chain with its blocks. After Eyal's original paper, the concept of selfish mining has been actively studied within the Bitcoin community for several years. This paper studies a fundamental problem regarding the selfish mining strategy under the existence of mining pools. For this, we propose a new attack strategy, called "Detective Mining", and show that selfish mining pool is not profitable anymore when other miners use our strategy.

Blockchain-based smart contract platforms like Ethereum have become quite popular as a way to remove trust and add transparency to distributed applications. While different types of important applications can be easily built on such platforms, there does not seem to be an easy way to add a meaningful level of privacy to them. In this paper, we propose Zether, a fully-decentralized, confidential payment mechanism that is compatible with Ethereum and other smart contract platforms. We take an account-based approach similar to Ethereum for efficiency and usability. We design a new smart contract that keeps the account balances encrypted and exposes methods to deposit, transfer and withdraw funds to/from accounts through cryptographic proofs. We describe techniques to protect Zether against replay attacks and front-running situations. We also develop a mechanism to enable interoperability with arbitrary smart contracts. This helps to make several popular applications like auctions, payment channels, voting, etc. confidential. As a part of our protocol, we propose $\Sigma$-Bullets, an improvement of the existing zero-knowledge proof system, Bulletproofs. $\Sigma$-Bullets make Bulletproofs more inter-operable with Sigma protocols, which is of general interest. We implement Zether as an Ethereum smart contract and show the practicality of our design by measuring the amount of gas used by the Zether contract. A Zether confidential transaction costs about 0.014 ETH or approximately $1.51 (as of early Feb, 2019). We discuss how small changes to Ethereum, which are already being discussed independently of Zether, would drastically reduce this cost.

In this paper we give an efficient and compact reformulation of NIST collision estimate test given in SP-800 90B. We correct an error in the formulation of the test and show that the test statistic can be computed in a much easier way. We also propose a revised algorithm for the test based on our findings.

Inspired by the literature on side-channel attacks against cryptographic implementations, we describe a framework for the analysis of location privacy. It allows us to revisit (continuous) re-identification attacks with a combination of information theoretic and security metrics. Our results highlight conceptual differences between re-identification attacks exploiting leakages that are internal or external to a pseudonymised database. They put forward the amount of data to collect in order to estimate a predictive model as an important -- yet less discussed -- dimension of privacy assessments. They finally leverage recent results on the security evaluations/certification of cryptographic implementations to connect information theoretic and security metrics, and to formally bound the risk of re-identification with external leakages.

Transactions are arguably the most important part in the bitcoin mechanism, with everything else facilitating the proper creation, propagation and validation; culminating with their addition to the public ledger – the blockchain. One crucial measure inevitably intertwined with transactions is, throughput, the number of transactions confirmed (or added to the blockchain) per second, or simply, tps. Understanding throughput capacity from different angles remains of paramount importance for gaining insights into the underlying infrastructure. We compute the exact upper bound for the maximal transaction throughput of the bitcoin protocol and obtain 27 tps. The previous best known bound for the average transaction throughput is 7 tps. All results are based on legacy infrastructure, i.e., pre-SegWit era.

This work studies the problem of automatically penalizing intentional or unintentional data breach (APB) by a receiver/custodian receiving confidential data from a sender. We solve this problem for multimedia data by augmenting a blockchain on-chain smart contract between the sender and receiver with an off-chain cryptographic protocol, such that any significant data breach from the receiver is penalized through a monetary loss. Towards achieving the goal, we develop a natural extension of oblivious transfer called doubly oblivious transfer (DOT) which, when combined with robust watermarking and a claim-or-refund blockchain contract provides the necessary framework to realize the APB protocol in a provably secure manner. In our APB protocol, a public data breach by the receiver leads to her Bitcoin (or other blockchain) private signing key getting revealed to the sender, which allows him to penalize the receiver by claiming the deposit from the claim- or-refund contract. Interestingly, the protocol also ensures that the malicious sender cannot steal the deposit, even as he knows the original multimedia document or releases it in any form. We implement our APB protocol, develop the required smart contract for Bitcoin and observe our system to be efficient and easy to deploy in practice for multimedia documents. We analyze our DOT-based design against partial adversarial leakages and observe it to be robust against even small leakages.

Theft from cryptocurrency exchanges due to cyberattacks or internal fraud is a major problem. Exchanges can partially alleviate customer concerns by providing periodic proofs of solvency. We describe MProve, a proof of reserves protocol for Monero exchanges which can be combined with a known proof of liabilities protocol to provide a proof of solvency. It is the first protocol for Monero which provides address privacy by allowing an exchange to hide its own addresses within a larger anonymity set. MProve also provides a simple proof of non-collusion between exchanges.

Blockchain technologies recently received a considerable amount of attention. While the initial focus was mainly on the use of blockchains in the context of cryptocurrencies such as Bitcoin, application scenarios now go far beyond this. Most blockchains have the property that once some object, e.g., a block or a transaction, has been registered to be included into the blockchain, it is persisted and there are no means to modify it again. While this is an essential feature of most blockchain scenarios, it is still often desirable - at times it may be even legally required - to allow for breaking this immutability in a controlled way. Only recently, Ateniese et al. (EuroS&P 2017) proposed an elegant solution to this problem on the block level. Thereby, the authors replace standard hash functions with so-called chameleon-hashes (Krawczyk and Rabin, NDSS 2000). While their work seems to offer a suitable solution to the problem of controlled re-writing of blockchains, their approach is too coarse-grained in that it only offers an all-or-nothing solution. We revisit this idea and introduce the novel concept of policy-based chameleonhashes (PCH). PCHs generalize the notion of chameleon-hashes by giving the party computing a hash the ability to associate access policies to the generated hashes. Anyone who possesses enough privileges to satisfy the policy can then find arbitrary collisions for a given hash. We then apply this concept to transaction-level rewriting within blockchains, and thus support fine-grained and controlled modifiability of blockchain objects. Besides modeling PCHs, we present a generic construction of PCHs (using a strengthened version of chameleon-hashes with ephemeral trapdoors which we also introduce), rigorously prove its security, and instantiate it with efficient building blocks. We report first implementation results.

We present a practical solution to design a secure logging system that provides confidentiality, integrity, completeness, and non-repudiation. To the best of our knowledge, our solution is the first practical implementation of a logging system that brings all the above security aspects together. Our proposed library makes use of a Dynamic Searchable Symmetric Encryption (DSSE) scheme to provide keyword search operations through encrypted logs without decryption. This helps us to keep each log confidential, preventing unauthorized users from decrypting the encrypted logs. Moreover, we deploy a set of new features such as log sequence generation and digital signatures on top of the DSSE scheme, which makes our library a complete proof of concept solution for a secure logging system, providing all the necessary security assurances. We also analyze the library's performance on a real setting, bootstrapping with 10,000 lines of logs. Based on our observation, the entire search operation for a keyword takes about 10 milliseconds. Although SELL v1.0 is developed purely in Python without any low level optimization, the benchmarks show promising timing results for all the operations.

Second-order analyses have shown a great interest to defeat first level of masking protections. Their practical realization remains tedious in a lot of cases. This is partly due to the difficulties of achieving a fine alignment of two areas that are combined together afterward. Classical protections makes therefore use of random jitter or shuffling to make the alignment difficult or even impossible. This paper extends Scatter attack to high-order analyses. Processing the jointdistribution of two selection of points, it becomes possible to retrieve the secret key even when traces are not fully aligned. The results presented in this paper are validated through practical experimentation and compared with existing window-based techniques, such as the FFT. Scatter shows the best results when misalignment is significant. This illustrates that Scatter offers an alternative to existing high-order attacks and can target all kinds of cryptography implementations, regardless they are executed in hardware or software. With the ability to exploit several leakage points, it may be valuable also when applying a second-order attack on aligned traces.

Bit-decomposition is a powerful tool which can be used to design constant round protocols for bit-oriented multiparty computation (MPC) problems, such as comparison and Hamming weight computation. However, protocols that involve bit-decomposition are expensive in terms of performance. In this paper, we introduce a set of protocols for distributed exponentiation without bit-decomposition. We build upon the current state-of-the-art by Ning and Xu [ASIACRYPT 2010 & ASIACRYPT 2011], in terms of round and multiplicative complexity. We consider different cases where the inputs are either private or public and present privacy-preserving protocols for each case. Our protocols offer perfect security against passive and active adversaries and have constant multiplicative and round complexity, for any fixed number of parties. Furthermore, we showcase how these primitives can be used, for instance, to perform secure distributed decryption for some public key schemes, that are based on modular exponentiation.

To achieve security and privacy for data stored on the cloud, we need the ability to secure data in compute. Equality comparisons, ``$x=y, x\neq y$'', have been widely studied with many proposals but there is much room for improvement for order comparisons, ``$x < y,~x \leq y, x > y$ and $x \geq y$''. Most protocols for order comparisons have some limitation, either leaking some information about the data or requiring several rounds of communication between client and server. In addition, little work has been done on retrieving with compound conditions, mixing several equality and order comparisons. Fully homomorphic encryption (FHE) promises the ability to compute arbitrary functions on encrypted data without sacrificing privacy and without communication, but its potential has yet to be fulfilled. Particularly, private comparisons for database queries using FHE are expensive to compute. In this work, we design efficient private database query (PDQ) protocols which support order comparisons and compound conditions. To this end, we first present a private comparison algorithm on encrypted integers using FHE, which scales efficiently for the length of input integers, by applying techniques from finite field theory. Then, we consider two scenarios for PDQ protocols, the first for retrieving data based on one order comparison and the second based on a conjunction of one order and four equality conditions. The proposed algorithm and protocols are implemented and tested to determine their performance in practice. The proposed comparison algorithm takes about 20.155 seconds to compare 697 pairs of 64-bit integers using Brakerski-Gentry-Vaikuntanathan's leveled FHE scheme with single instruction multiple data (SIMD) techniques at more than 110 bits of security. This yields an amortized rate of just 29 milliseconds per comparison. On top of that, we show that our techniques achieve an efficient PDQ protocol for one order and four equality comparisons, achieving an amortized time and communication cost of 36 milliseconds and 154 bytes per database element.

A decision graph is a well-studied classifier and has been used to solve many real-world problems. We assumed a typical scenario between two parties in this study, in which one holds a decision graph and the other wants to know the class label of his/her query without disclosing the graph and query to the other. We propose a novel protocol for this scenario that can obliviously evaluate a graph that is designed by an efficient data structure called the graph level order unary degree sequence (GLOUDS). The time and communication complexities of this protocol are linear to the number of nodes in the graph and do not include any exponential factors. The experiment results revealed that the actual runtime and communication size were well concordant with theoretical complexities. Our method can process a graph with approximately 500 nodes in only 11 s on a standard laptop computer. We also compared the runtime of our method with that of previous methods and confirmed that it was one order of magnitude faster than the previous methods.

Enabling cryptographically enforced access controls for data hosted in untrusted cloud is attractive for many users and organizations. However, designing efficient cryptographically enforced dynamic access control system in the cloud is still challenging. In this paper, we propose Crypt-DAC, a system that provides practical cryptographic enforcement of dynamic access control. Crypt-DAC revokes access permissions by delegating the cloud to update encrypted data. In Crypt-DAC, a file is encrypted by a symmetric key list which records a file key and a sequence of revocation keys. In each revocation, a dedicated administrator uploads a new revocation key to the cloud and requests it to encrypt the file with a new layer of encryption and update the encrypted key list accordingly. Crypt-DAC proposes three key techniques to constrain the size of key list and encryption layers. As a result, Crypt-DAC enforces dynamic access control that provides efficiency, as it does not require expensive decryption/re- encryption and uploading/re-uploading of large data at the administrator side, and security, as it immediately revokes ac- cess permissions. We use formalization framework and system implementation to demonstrate the security and efficiency of our construction.

In order to achieve a truthful distributed ledger, homogeneous nodes in Blockchain systems will propagate messages on a P2P network so that they can synchronize the status of the ledger. Currently, blockchain systems target on achieving better scalability and higher throughput to support divergent applications which will lead to heavier message propagation, especially the broadcasting of blocks. The heavier traffic on the P2P network will cause longer latency of block synchronization, which may damage system consistency and expose the system to potential attacks. Even worse, when heavy communication consumes a lot of network capacity, nodes in the P2P network may not relay blocks to save their bandwidth. This may damage the efficiency of network synchronization. In order to alleviate the problems, we propose an improved block broadcasting protocol which elaborates block data sharding and financial incentive mechanisms. In the proposed scheme, a block is sliced into pieces in order to keep the network traffic smooth and speed up content delivery. Any node which relays a piece of the block will get benefits with financial rewards. By applying data sharding, our proposed scheme speed up the block broadcasting and therefore shorten the synchronization time by 90\%, which is shown in our simulation experiments. In addition, we carry out game theoretical analysis to prove that nodes are efficiently incentivized to relay blocks honestly and actively.

In this paper, we motivate the need for image encryption techniques that preserve certain visual features in images and hide all other information, to balance privacy and usability in the context of cloud-based image storage services. In particular, we introduce the concept of ideal or exact Thumbnail-Preserving Encryption (TPE), a special case of format-preserving encryption, and present a concrete construction. In TPE, a ciphertext is itself an image that has the same thumbnail as the plaintext (unencrypted) image, but that provably leaks nothing about the plaintext beyond its thumbnail. We provide a formal security analysis for the construction, and a prototype implementation to demonstrate compatibility with existing services. We also study the ability of users to distinguish between thumbnail images preserved by TPE. Our findings indicate that TPE is an efficient and promising approach to balance usability and privacy concerns for images. Our code and a demo are available at http://photoencryption.org.

Logic encryption is an important hardware security technique that introduces keys to modify a given combinational circuit in order to lock the functionality from unauthorized uses. Traditional methods are all ad hoc approaches based on inserting lock gates with keys on randomly selected signals in the original circuit. Thus, it was not a surprise that a SAT-based attack developed by Subramanyan et al. successfully defeated almost all of them. New approaches such as SARLock and Anti-SAT were then developed to defend against SAT-based attack. However, they are still vulnerable with extremely low error rates. In this paper, we present a theory on logic encryption that provides a complete understanding on the design space and the trade-o between error rate and attack complexity. An e cient general design scheme is derived from the theory and some speci c designs are also suggested. We also suggest a method to insert one-way function to burden the SAT engine, and a method to obfuscate the whole design. In addition, as an application of the theory, we also develop a scienti c encryption benchmark for approximate attacks. We test our encryption designs and obfuscation techniques by the SAT-based attack, and the results have veri ed the robustness of our approach.

The threat of side-channels is becoming increasingly prominent for resource-constrained internet-connected devices. While numerous power side-channel countermeasures have been proposed, a promising approach to protect the non-invasive electromagnetic side-channel attacks has been relatively scarce. Today's availability of high-resolution electromagnetic (EM) probes mandates the need for a low-overhead solution to protect EM side-channel analysis (SCA) attacks. This work, for the first time, performs a white-box analysis to root-cause the origin of the EM leakage from an integrated circuit. System-level EM simulations with Intel 32 nm CMOS technology interconnect stack, as an example, reveals that the EM leakage from metals above layer 8 can be detected by an external non-invasive attacker with the commercially available state-of-the-art EM probes. Equipped with this `white-box' understanding, this work proposes \textit{STELLAR}: Signature aTtenuation Embedded CRYPTO with Low-Level metAl Routing, which is a two-stage solution to eliminate the critical signal radiation from the higher-level metal layers. Firstly, we propose routing of the entire cryptographic cores power traces using the local lower-level metal layers, whose leakage cannot be picked up by an external attacker. Then, the entire crypto IP is embedded within a Signature Attenuation Hardware (SAH) which in turn suppresses the critical encryption signature before it routes the current signature to the highly radiating top-level metal layers. System-level implementation of the STELLAR hardware with local lower-level metal routing in TSMC 65 nm CMOS technology, with an AES-128 encryption engine (as an example cryptographic block) operating at 40 MHz, shows that the system remains secure against EM SCA attack even after $1 M$ encryptions, with $67\%$ energy efficiency and $1.23\times$ area overhead compared to the unprotected AES.

With increasing autonomous features of vehicles, key issues of robotic- and automotive engineering converge toward each other. Closing existing security gaps of device communication networks will be an enabling feature for connecting autonomously interacting systems in a more secure way. We introduce a novel approach for deriving a secret key using a lightweight cipher in the firmware of a low-end control unit. In this approach, we propose to use a non-standardized lightweight algorithm with unique hardware based parameters to prevent duplicate key generation. The randomness of the selected cipher was assessed by applying the NIST statistical test suite to produced key values. By evaluating the method on a typical low-end automotive platform, we could demonstrate the realistic applicability of the solution. The proposed method counteracts a known security issue in device communication between control units not only present in automotive solutions but also in the robotics domain. The security of the implemented solution has been compared to current automotive guidelines and recommendations for the security of resource constrained devices, also present in robotics. This approach allows low-end communication systems to be enhanced by message- and device authentication.

Cryptocurrencies have provided a promising infrastructure for pseudonymous online payments. However, low throughput has significantly hindered the scalability and usability of cryptocurrency systems for increasing numbers of users and transactions. Another obstacle to achieving scalability is the requirement for every node to duplicate the communication, storage, and state representation of the entire network. In this paper, we introduce the Asynchronous Consensus Zones, which scales blockchain system linearly without compromising decentralization or security. We achieve this by running multiple independent and parallel instances of single-chain consensus systems termed as zones. The consensus happens independently within each zone with minimized communication, which partitions the workload of the entire network and ensures a moderate burden for each individual node as the network grows. We propose eventual atomicity to ensure transaction atomicity across zones, which achieves the efficient completion of transactions without the overhead of a two-phase commit protocol. Additionally, we propose Chu-ko-nu mining to ensure the effective mining power in each zone to be at the same level of the entire network, making an attack on any individual zone as hard as that on the full network. Our experimental results show the effectiveness of our work: on a testbed including 1,200 virtual machines worldwide to support 48,000 nodes, our system delivers 1,000x throughput and 2,000x capacity over the Bitcoin and Ethereum networks.

Physical attacks are a known threat posed against secure embedded systems. Notable among these is laser fault injection, which is often considered as the most effective fault injection technique. Indeed, laser fault injection provides a high spatial accuracy, which enables an attacker to induce bit-level faults. However, experience gained from attacking 8-bit targets might not be relevant on more advanced micro-architectures, and these attacks become increasingly challenging on 32-bit microcontrollers. In this article, we show that the flash memory area of a 32-bit microcontroller is sensitive to laser fault injection. These faults occur during the instruction fetch process, hence the stored value remains unaltered. After a thorough characterisation of the induced faults and the associated fault model, we provide detailed examples of bit-level corruption of instructions and demonstrate practical applications in compromising the security of real-life codes. Based on these experimental results, we formulate a hypothesis about the underlying micro-architectural features that explain the observed fault model.

Proof-of-stake-based (in short, PoS-based) blockchains aim to overcome scalability, effi- ciency, and composability limitations of the proof-of-work paradigm, which underlies the security of several mainstream cryptocurrencies including Bitcoin. Our work puts forth the first (global universally) composable (GUC) treatment of PoS-based blockchains in a setting that captures—for the first time in GUC—arbitrary numbers of parties that may not be fully operational, e.g., due to network problems, reboots, or updates of their OS that affect all or just some of their local resources including their network interface and clock. This setting, which we refer to as dynamic availability, naturally captures decentralized environments within which real-world deployed blockchain protocols are assumed to operate. We observe that none of the existing PoS-based blockchain protocols can realize the ledger functionality under dynamic availability in the same way that bitcoin does (using only the information available in the genesis block). To address this we propose a new PoS-based protocol, “Ouroboros Genesis”, that adapts one of the latest cryptographically-secure PoS-based blockchain protocols with a novel chain selection rule. The rule enables new or offline parties to safely (re-)join and bootstrap their blockchain from the genesis block without any trusted advice—such as checkpoints—or assumptions regarding past availability. We say that such a blockchain protocol can “bootstrap from genesis.” We prove the GUC security of Ouroboros Genesis against a fully adaptive adversary controlling less than half of the total stake. Our model allows adversarial scheduling of messages in a network with delays and captures the dynamic availability of participants in the worst case. Importantly, our protocol is effectively independent of both the maximum network delay and the minimum level of availability— both of which are run-time parameters. Proving the security of our construction against an adaptive adversary requires a novel martingale technique that may be of independent interest in the analysis of blockchain protocols.

One of three tasks in a secure genome analysis competition called IDASH 2018 was to develop a solution for privacy-preserving GWAS computation based on homomorphic encryption. The scenario is that a data holder encrypts a number of individual records, each of which consists of several phenotype and genotype data, and provide the encrypted data to an untrusted server. Then, the server performs a GWAS algorithm based on homomorphic encryption without the decryption key and outputs the result in encrypted state so that there is no information leakage on the sensitive data to the server. We develop a privacy-preserving semi-parallel GWAS algorithm by applying an approximate homomorphic encryption scheme HEAAN. Fisher scoring and semi-parallel GWAS algorithms are modified to be efficiently computed over homomorphically encrypted data with several optimization methodologies; substitute matrix inversion by an adjoint matrix, avoid computing a superfluous matrix of super-large size, and transform the algorithm into an approximate version. Our modified semi-parallel GWAS algorithm based on homomorphic encryption which achieves 128-bit security takes $30$--$40$ minutes for $245$ samples containing $10,000$--$15,000$ SNPs. Compared to the true $p$-value from the original semi-parallel GWAS algorithm, the $F_1$ score of our $p$-value result is over $0.99$.

Public blockchains can be abused to covertly store and disseminate potentially harmful digital content. Consequently, this threat jeopardizes the future of such applications and poses a serious regulatory issue. In this work, we show the severity of the problem by demonstrating that blockchains can be exploited as a covert bulletin board to secretly store and distribute arbitrary content. More specically, all major blockchain systems use randomized cryptographic primitives, such as digital signatures and non-interactive zero-knowledge proofs, and we illustrate how the uncontrolled randomness in such primitives can be maliciously manipulated to enable covert communication and hidden persistent storage. To clarify the potential risk, we design, implement and evaluate our technique against the widely-used ECDSA signature scheme, the CryptoNote's ring signature scheme, and Monero's ring condential transactions. Importantly, the signicance of the demonstrated attacks stems from their undetectability, their adverse eect on the future of decentralized blockchains, and their serious repercussions on users' privacy and crypto funds. Finally, besides presenting the attacks, we examine existing countermeasures and devise two new steganography-resistant blockchain architectures to practically thwart this threat in the context of blockchains.

A landmark security property of smart contracts is liquidity: in a non-liquid contract, it may happen that some funds remain frozen. The relevance of this issue is witnessed by a recent liquidity attack to the Ethereum Parity Wallet, which has frozen 160M USD within the contract, making this sum unredeemable by any user. We address the problem of verifying liquidity of Bitcoin contracts. Focussing on itML, a contracts DSL with a computationally sound compiler to Bitcoin, we study various notions of liquidity. Our main result is that liquidity of BitML contracts is decidable, in all the proposed variants. To prove this, we first transform the infinite-state semantics of BitML into a finite-state one, which focusses on the behaviour of any given set of contracts, abstracting the moves of the context. With respect to the chosen contracts, this abstraction in sound and complete. Our decision procedure for liquidity is then based on model-checking the finite space of states of the abstraction. The computational soundness of the BitML compiler allows to lift this result from the symbolic to the computational level: if our decision procedure establishes that a contract is liquid, then it will be such also under a computational adversary, and vice versa.

In the era of lightweight cryptography, designing cryptographically good and power efficient 4x4 S-boxes is a challenging problem. While the optimal cryptographic properties are easy to determine, verifying the power efficiency of an S-box is non-trivial. The conventional approach of determining the power consumption using commercially available CAD-tools is highly time consuming, which becomes formidable while dealing with a large pool of S-boxes. This mandates development of an automation that should quickly characterize the power efficiency from the Boolean function representation of an S-box. In this paper, we present a supervised machine learning assisted automated framework to resolve the problem for 4x4 S-boxes, which turns out to be 14 times faster than traditional approach. The key idea is to extrapolate the knowledge of literal counts, AND-OR-NOT gate counts in SOP form of the underlying Boolean functions to predict the dynamic power efficiency. The experimental results and performance of our novel technique depicts its superiority with high efficiency and low time overhead. We demonstrate effectiveness of our framework by reporting a set of power efficient optimal S-boxes from a large set of S-boxes. We also develop a deterministic model using results obtained from supervised learning to predict the dynamic power of an S-box that can be used in an evolutionary algorithm to generate cryptographically strong and low power S-boxes.

How to train a machine learning model while keeping the data private and secure? We present CodedPrivateML, a fast and scalable approach to this critical problem. CodedPrivateML keeps both the data and the model information-theoretically private, while allowing efficient parallelization of training across distributed workers. We characterize CodedPrivateML's privacy threshold and prove its convergence for logistic (and linear) regression. Furthermore, via experiments over Amazon EC2, we demonstrate that CodedPrivateML can provide an order of magnitude speedup (up to $\sim 34\times$) over the state-of-the-art cryptographic approaches.

The wide deployment of tokens for digital assets on top of Ethereum implies the need for powerful trading platforms. Vickrey auctions have been known to determine the real market price of items as bidders are motivated to submit their own monetary valuations without leaking their information to the competitors. Recent constructions have utilized various cryptographic protocols such as ZKP and MPC, however, these approaches either are partially privacy-preserving or require complex computations with several rounds. In this paper, we overcome these limits by presenting Trustee as a Vickrey auction on Ethereum which fully preserves bids' privacy at a relatively much lower fees. Trustee consists of three components: a front-end smart contract deployed on Ethereum, an Intel SGX enclave, and a relay to redirect messages between them. Initially, the enclave generates an Ethereum account and ECDH key-pair. Subsequently, the relay publishes the account's address and ECDH public key on the smart contract. As a prerequisite, bidders are encouraged to verify the authenticity and security of Trustee by using the SGX remote attestation service. To participate in the auction, bidders utilize the ECDH public key to encrypt their bids and submit them to the smart contract. Once the bidding interval is closed, the relay retrieves the encrypted bids and feeds them to the enclave that autonomously generates a signed transaction indicating the auction winner. Finally, the relay submits the transaction to the smart contract which verifies the transaction's authenticity and the parameters' consistency before accepting the claimed auction winner. As part of our contributions, we have made a prototype for Trustee available on Github for the community to review and inspect it. Additionally, we analyze the security features of Trustee and report on the transactions' gas cost incurred on Trustee smart contract.

Background Privacy-preserving computations on genomic data, and more generally on medical data, is a critical path technology for innovative, life-saving research to positively and equally impact the global population. It enables medical research algorithms to be securely deployed in the cloud because operations on encrypted genomic databases are conducted without revealing any individual genomes. Methods for secure computation have shown significant performance improvements over the last several years. However, it is still challenging to apply them on large biomedical datasets. Methods The HE Track of iDash 2018 competition focused on solving an important problem in practical machine learning scenarios, where a data analyst that has trained a regression model (both linear and logistic) with a certain set of features, attempts to find all features in an encrypted database that will improve the quality of the model. Our solution is based on the hybrid framework Chimera that allows for switching between different families of fully homomorphic schemes, namely TFHE and HEAAN. Results Our solution is one of the finalist of Track 2 of iDash 2018 competition. Among the submitted solutions, ours is the only bootstrapped approach that can be applied for different sets of parameters without re-encrypting the genomic database, making it practical for real-world applications. Conclusions This is the first step towards the more general feature selection problem across large encrypted databases.

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely ``unrelated value''. Although such codes do not exist if the family of ``tampering functions'' \cF allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families \cF. The family which received the most attention is the family of tampering functions in the so called (2-part) {\em split-state} model: here the message x is encoded into two shares L and R, and the attacker is allowed to {\em arbitrarily} tamper with each L and R individually. Despite this attention, the following problem remained open: Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate}: |L|=|R|=O(|x|). In this work, we make progress towards obtaining this result. Specifically, we (a) develop a generalization of non-malleable codes, called {\em non-malleable reductions}; (b) show simple composition theorem for non-malleable reductions; (c) build a variety of such reductions connecting various (independently interesting) tampering families $\cF$ to each other; (d) construct several new non-malleable codes in the split-state model by applying the composition theorem to a series of easy to understand reductions. In particular, we design an unconditionally secure non-malleable code with 5 parts where the size of each part is quadratic in the length of the message, and state a conjecture under which we obtain a constant rate 2 part non-malleable code in the split-state model. Of independent interest, we show several ``independence amplification'' reductions, showing how to reduce split-state tampering of very few parts to an easier question of split-state tampering with a much larger number of parts. \paragraph{Note.} Some time after publishing the paper (it was presented at STOC 2015), Xin Li pointed out that one of the proofs in the paper had a mistake. In particular, we had incorrectly claimed a proof of Conjecture 26. We would like to emphasize that we still believe that Conjecture 26 is true but we do not have a proof.

Link Prediction is an important and well-studied problem for social networks. Given a snapshot of a graph, the link prediction problem predicts which new interactions between members are most likely to occur in the near future. As networks grow in size, data owners are forced to store the data in remote cloud servers which reveals sensitive information about the network. The graphs are therefore stored in encrypted form. We study the link prediction problem on encrypted graphs. To the best of our knowledge, this secure link prediction problem has not been studied before. We use the number of common neighbors for prediction. We present three algorithms for the secure link prediction problem. We design prototypes of the schemes and formally prove their security. We execute our algorithms in real-life datasets.

Relative cryptographic semantic security for encrypted words of user data at runtime holds in the emerging field of encrypted computing, in conjunction with an appropriate instruction set and compiler. An information obfuscation calculus for program compilation in that context is introduced here that quantifies the security exactly, improving markedly on the result.

The Zerocoin protocol is a set of cryptographic algorithms which embedded in a cryptocurrency provide anonymous swap of tokens in a mathematically provable way by using cryptographic accumulators. Functionally it can be described as a black box where an actor can introduce an arbitrary number of coins, and later withdraw them without leaving evidence of connection between both actions. The withdrawing step admits a destination for the coins different from the original minter, but unconditionally requires a previous mint action and does not accept the transfer of coins without leaving the accumulator, thus exposing the traceability of the coins. We propose an alternative design which for the first time combines the virtues of Zerocoin with those of Confidential Transactions offering fully-featured anonymous transactions between individuals with private amounts.

Logic encryption is a powerful hardware protection technique that uses extra key inputs to lock a circuit from piracy or unauthorized use. The recent discovery of the SAT-based attack with Distinguishing Input Pattern (DIP) generation has rendered all traditional logic encryptions vulnerable, and thus the creation of new encryption methods. However, a critical question for any new encryption method is whether security against the DIP-generation attack means security against all other attacks. In this paper, a new high-level SAT-based attack called SigAttack has been discovered and thoroughly investigated. It is based on extracting a key-revealing signature in the encryption. A majority of all known SAT-resilient encryptions are shown to be vulnerable to SigAttack. By formulating the condition under which SigAttack is effective, the paper also provides guidance for the future logic encryption design.

Logic encryption has attracted much attention due to increasing IC design costs and growing number of untrusted foundries. Unreachable states in a design provide a space of flexibility for logic encryption to explore. However, due to the available access of scan chain, traditional combinational encryption cannot leverage the benefit of such flexibility. Cyclic logic encryption inserts key-controlled feedbacks into the original circuit to prevent piracy and overproduction. Based on our discovery, cyclic logic encryption can utilize unreachable states to improve security. Even though cyclic encryption is vulnerable to a powerful attack called CycSAT, we develop a new way of cyclic encryption by utilizing unreachable states to defeat CycSAT. The attack complexity of the proposed scheme is discussed and its robustness is demonstrated.

Cyclic logic encryption is newly proposed in the area of hardware security. It introduces feedback cycles into the circuit to defeat existing logic decryption techniques. To ensure that the circuit is acyclic under the correct key, CycSAT is developed to add the acyclic condition as a CNF formula to the SAT-based attack. However, we found that it is impossible to capture all cycles in any graph with any set of feedback signals as done in the CycSAT algorithm. In this paper, we propose a behavioral SAT-based attack called BeSAT. BeSAT observes the behavior of the encrypted circuit on top of the structural analysis, so the stateful and oscillatory keys missed by CycSAT can still be blocked. The experimental results show that BeSAT successfully overcomes the drawback of CycSAT.

Dissidents, journalists, and others require technical means to protect their privacy in the face of compelled access to their digital devices (smartphones, laptops, tablets, etc.). For example, authorities increasingly force disclosure of all secrets, including passwords, to search devices upon national border crossings. We therefore present the design, implementation, and evaluation of a new system to help victims of compelled searches. Our system, called BurnBox, provides self-revocable encryption: the user can temporarily disable their access to specific files stored remotely, without revealing which files were revoked during compelled searches, even if the adversary also compromises the cloud storage service. They can later restore access. We formalize the threat model and provide a construction that uses an erasable index, secure erasure of keys, and standard cryptographic tools in order to provide security supported by our formal analysis. We report on a prototype implementation, which showcases the practicality of BurnBox.

Secure report is the problem of a client that retrieves all records matching specified attributes from a database table at the server (e.g. cloud), as in SQL SELECT queries, but where the query and the database are encrypted. Here, only the client has the secret key, but still the server is expected to compute and return the encrypted result. Secure report is theoretically possible with Fully Homomorphic Encryption (FHE). However, the current state-of-the-art solutions are realized by a polynomial of degree that is at least linear in the number $m$ of records, which is too slow in practice even for very small databases. We present the first solution that is realized by a polynomial that attains degree independent of the number of records $m$, as well as the first implementation of an FHE solution to Secure report. This is by suggesting a novel paradigm that forges a link between cryptography and modern data summarization techniques known as coresets (core-sets), and sketches in particular. The key idea is to compute only a coreset of the desired report. Since the coreset is small, the client can quickly decode the desired report that the server computes after decrypting the coreset. We implemented our main reporting system in an open source library. This is the first implemented system that can answer such database queries when processing only FHE encrypted data and queries. As our analysis promises, the experimental results show that we can run Secure report queries on billions records in minutes on an Amazon EC2 server, compared to less than a hundred-thousands in previous FHE based solutions.

Third-party applications on Facebook can collect personal data of the users who install them, but also of their friends. This raises serious privacy issues as these friends are not notified by the applications nor by Facebook, and they have not given consent. This paper presents a detailed multi-faceted study of the collateral information collection of the applications on Facebook. To investigate the views of the users, we designed a questionnaire and collected the responses of 114 participants. The results show that participants are concerned about the collateral information collection and in particular about the lack of notification and of mechanisms to control the data collection. Based on real data, we compute the likelihood of collateral information collection affecting users: we show that the probability is significant and greater than 80% for popular applications such as TripAdvisor. We also demonstrate that a substantial amount of profile data can be collected by applications, which enables application providers to profile users. To investigate whether collateral information collection is an issue to users’ privacy we analysed the legal framework in light of the new General Data Protection Regulation. We provide a detailed analysis of the entities involved and investigate which entity is accountable for the collateral information collection. To provide countermeasures, we propose a privacy dashboard extension that implements privacy scoring computations to enhance transparency towards collateral information collection. Furthermore, we discuss alternative solutions highlighting other countermeasures such as notification and access control mechanisms, cryptographic solutions and application auditing. To the best of our knowledge, this is the first work that provides a detailed multi-faceted study of this problem and that analyses the threat of user profiling by application providers.

We propose a proof of work protocol that computes the discrete logarithm of an element in a cyclic group. Individual provers generating proofs of work perform a distributed version of the Pollard rho algorithm. Such a protocol could capture the computational power expended to construct proof-of-work-based blockchains for a more useful purpose, as well as incentivize advances in hardware, software, or algorithms for an important cryptographic problem. We describe our proposed construction and elaborate on challenges and potential trade-offs that arise in designing a practical proof of work.

Distributed credit networks, such as Ripple and Stellar, are becoming popular as an alternative means for financial transactions. However, the current designs do not preserve user privacy or are not truly decentralized. In this paper, we explore the creation of a distributed credit network that preserves user and transaction privacy and unlinkability. We propose BlAnC, a novel, fully decentralized blockchain-based credit network where credit transfer between a sender-receiver pair happens on demand. In BlAnC, multiple concurrent transactions can occur seamlessly, and malicious network actors that do not follow the protocols and/or disrupt operations can be identified efficiently. We perform security analysis of our proposed protocols in the universal composability framework to demonstrate its strength, and discuss how our network handles operational dynamics. We also present preliminary experiments and scalability analyses.

We show that the problem of reconstructing encrypted databases from access pattern leakage is closely related to statistical learning theory. This new viewpoint enables us to develop broader attacks that are supported by streamlined performance analyses. As an introduction to this viewpoint, we first present a general reduction from reconstruction with known queries to PAC learning. Then, we directly address the problem of $\epsilon$-approximate database reconstruction ($\epsilon$-ADR) from range query leakage, giving attacks whose query cost scales only with the relative error $\epsilon$, and is independent of the size of the database, or the number $N$ of possible values of data items. This already goes significantly beyond the state of the art for such attacks, as represented by Kellaris et al. (ACM CCS 2016) and Lacharité et al. (IEEE S&P 2018). We also study the new problem of $\epsilon$-approximate order reconstruction ($\epsilon$-AOR), where the adversary is tasked with reconstructing the order of records, except for records whose values are approximately equal. We show that as few as ${\mathcal{O}}(\epsilon^{-1} \log \epsilon^{-1})$ uniformly random range queries suffice. Our analysis relies on an application of learning theory to PQ-trees, special data structures tuned to compactly record certain ordering constraints. We then show that when an auxiliary distribution is available, $\epsilon$-AOR can be enhanced to achieve $\epsilon$-ADR; using real data, we show that devastatingly small numbers of queries are needed to attain very accurate database reconstruction. Finally, we generalize from ranges to consider what learning theory tells us about the impact of access pattern leakage for other classes of queries, focusing on prefix and suffix queries. We illustrate this with both concrete attacks for prefix queries and with a general lower bound for all query classes.

While financially advantageous, outsourcing key steps such as testing to potentially untrusted Outsourced Semiconductor Assembly and Test (OSAT) companies may pose a risk of compromising on-chip assets. Obfuscation of scan chains is a technique that hides the actual scan data from the untrusted testers; logic inserted between the scan cells, driven by a secret key, hide the transformation functions between the scan- in stimulus (scan-out response) and the delivered scan pattern (captured response). In this paper, we propose ScanSAT: an attack that transforms a scan obfuscated circuit to its logic- locked version and applies a variant of the Boolean satisfiability (SAT) based attack, thereby extracting the secret key. Our empirical results demonstrate that ScanSAT can easily break naive scan obfuscation techniques using only three or fewer attack iterations even for large key sizes and in the presence of scan compression.

The deployment of Genome-wide association studies (GWASs) requires genomic information of a large population to produce reliable results. This raises significant privacy concerns, making people hesitate to contribute their genetic information to such studies. We propose two provably secure solutions to address this challenge: (1) a somewhat homomorphic encryption approach, and (2) a secure multiparty computation approach. Unlike previous work, our approach does not rely on adding noise to the input data, nor does it reveal any information about the patients. Our protocols calculate the $\chi^2$ statistic in a privacy-preserving manner, without revealing any information other than the significance of the statistic; hence not even the statistic value itself. We significantly increased the efficiency of our protocols by introducing a new masking technique to perform the secure comparison. Our implementations demonstrated that both approaches are efficient. The secure multiparty computation technique completes its execution in approximately 2~ms for data contributed by one million subjects.

Logistic regression is a popular technique used in machine learning to construct classification models. Since the construction of such models is based on computing with large datasets, it is an appealing idea to outsource this computation to a cloud service. The privacy-sensitive nature of the input data requires appropriate privacy preserving measures before outsourcing it. Homomorphic encryption enables one to compute on encrypted data directly, without decryption, and can be used to mitigate the privacy concerns raised by using a cloud service. In this paper, we propose an algorithm (and its implementation) to train a logistic regression model on a homomorphically encrypted dataset. The core of our algorithm consists of a new iterative method that can be seen as a simplified form of the fixed Hessian method, but with a much lower multiplicative complexity. We test the new method on two interesting real life applications: the first application is in medicine and constructs a model to predict the probability for a patient to have cancer, given genomic data as input; the second application is in finance and the model predicts the probability of a credit card transaction to be fraudulent. The method produces accurate results for both applications, comparable to running standard algorithms on plaintext data. This article introduces a new simple iterative algorithm to train a logistic regression model that is tailored to be applied on a homomorphically encrypted dataset. This algorithm can be used as a privacy-preserving technique to build a binary classification model and can be applied in a wide range of problems that can be modelled with logistic regression. Our implementation results show that our method can handle the large datasets used in logistic regression training.

The security of web communication via the SSL/TLS protocols relies on safe distributions of public keys associated with web domains in the form of $\mathsf{X.509}$ certificates. Certificate authorities (CAs) are trusted third parties that issue these certificates. However, the CA ecosystem is fragile and prone to compromises. Starting with Google's Certificate Transparency project, a number of research works have recently looked at adding transparency for better CA accountability, effectively through public logs of all certificates issued by certification authorities, to augment the current $\mathsf{X.509}$ certificate validation process into SSL/TLS. In this paper, leveraging recent progress in blockchain technology, we propose a novel system, called $\mathsf{CTB} $, that makes it impossible for a CA to issue a certificate for a domain without obtaining consent from the domain owner. We further make progress to equip $\mathsf{CTB}$ with certificate revocation mechanism. We implement $\mathsf{CTB}$ using IBM's Hyperledger Fabric blockchain platform. $\mathsf{CTB}$'s smart contract, written in Go, is provided for complete reference.

Bitcoin, the first successful cryptocurrency, uses the blockchain structure and PoW mechanism to generate blocks. PoW makes an adversary difficult to control the network until she retains over 50\% of the hashrate of the total network. Another cryptocurrency, Ethereum, also uses this mechanism and it did not make problem before. In PoW research, however, several attack strategies are studied. In this paper, we researched selfish mining in the pooled mining environment and found the pooled mining exposes mining information of the block which adversary is mining to the random miners. Using this leaked information, other miners can exploit the selfish miner. At the same time, the adversary loses revenue than when she does honest mining. Because of the existence of our counter method, the adversary with pooled mining cannot do selfish mining easily on Bitcoin or blockchains using PoW.

We propose a formal model of Bitcoin transactions, which is sufficiently abstract to enable formal reasoning, and at the same time is concrete enough to serve as an alternative documentation to Bitcoin. We use our model to formally prove some well-formedness properties of the Bitcoin blockchain, for instance that each transaction can only be spent once. We release an open-source tool through which programmers can write transactions in our abstract model, and compile them into standard Bitcoin transactions.

In recent years, there has been enormous research attention in privacy-preserving biometric authentication, which enables a user to verify him or herself to a server without disclosing raw biometric information. Since biometrics is irrevocable when exposed, it is very important to protect its privacy. In IEEE TIFS 2018, Zhou and Ren proposed a privacy-preserving user-centric biometric authentication scheme named PassBio, where the end-users encrypt their own templates, and the authentication server never sees the raw templates during the authentication phase. In their approach, it takes about 1 second to encrypt and compare 2000-bit templates based on Hamming distance on a laptop. However, this result is still far from practice because the size of templates used in commercialized products is much larger: according to NIST IREX IX report of 2018 which analyzed 46 iris recognition algorithms, size of their templates varies from 4,632-bit (579-byte) to 145,832-bit (18,229-byte). In this paper, we propose a new privacy-preserving user-centric biometric authentication (HDM-PPBA) based on Hamming distance, which shows a big improvement in efficiency to the previous works. It is based on our new single-key function-hiding inner product encryption, which encrypts and computes the Hamming distance of 145,832-bit binary in about 0.3 seconds on Intel Core i5 2.9GHz CPU. We show that it satisfies simulation-based security under the hardness assumption of Learning with Errors (LWE) problem. The storage requirements, bandwidth and time complexity of HDM-PPBA depend linearly on the bit-length of biometrics, and it is applicable to any large templates used in NIST IREX IX report with high efficiency.

We propose a secure computation solution for blockchain networks. The correctness of computation is verifiable even under malicious majority condition using information-theoretic Message Authentication Code (MAC), and the privacy is preserved using Secret-Sharing. With state-of-the-art multiparty computation protocol and a layer2 solution, our privacy-preserving computation guarantees data security on blockchain, cryptographically, while reducing the heavy-lifting computation job to a few nodes. This breakthrough has several implications on the future of decentralized networks. First, secure computation can be used to support Private Smart Contracts, where consensus is reached without exposing the information in the public contract. Second, it enables data to be shared and used in trustless network, without disclosing the raw data during data-at-use, where data ownership and data usage is safely separated. Last but not least, computation and verification processes are separated, which can be perceived as computational sharding, this effectively makes the transaction processing speed linear to the number of participating nodes. Our objective is to deploy our secure computation network as an layer2 solution to any blockchain system. Smart Contracts\cite{smartcontract} will be used as bridge to link the blockchain and computation networks. Additionally, they will be used as verifier to ensure that outsourced computation is completed correctly. In order to achieve this, we first develop a general MPC network with advanced features, such as: 1) Secure Computation, 2) Off-chain Computation, 3) Verifiable Computation, and 4)Support dApps' needs like privacy-preserving data exchange.

Decentralized cryptocurrencies based on blockchains provide attractive features, including user privacy and system transparency, but lack active control of money supply and capabilities for regulatory oversight, both existing features of modern monetary systems. These limitations are critical, especially if the cryptocurrency is to replace, or complement, existing fiat currencies. Centralized cryptocurrencies, on the other hand, provide controlled supply of money, but lack transparency and transferability. Finally, they provide only limited privacy guarantees, as they do not offer recipient anonymity or payment value secrecy. We propose a novel digital currency, called PRCash, where the control of money supply is centralized, money is represented as value-hiding transactions for transferability and improved privacy, and transactions are verified in a distributed manner and published to a public ledger for verifiability and transparency. Strong privacy and regulation are seemingly conflicting features, but we overcome this technical problem with a new regulation mechanism based on zero-knowledge proofs. Our implementation and evaluation shows that payments are fast and large-scale deployments practical. PRCash is the first digital currency to provide control of money supply, transparency, regulation, and privacy at the same time, and thus make its adoption as a fiat currency feasible.

Adversary models have been integral to the design of provably-secure cryptographic schemes or protocols. However, their use in other computer science research disciplines is relatively limited, particularly in the case of applied security research (e.g., mobile app and vulnerability studies). In this study, we conduct a survey of prominent adversary models used in the seminal field of cryptography, and more recent mobile and Internet of Things (IoT) research. Motivated by the findings from the cryptography survey, we propose a classification scheme for common app-based adversaries used in mobile security research, and classify key papers using the proposed scheme. Finally, we discuss recent work involving adversary models in the contemporary research field of IoT. We contribute recommendations to aid researchers working in applied (IoT) security based upon our findings from the mobile and cryptography literature. The key recommendation is for authors to clearly define adversary goals, assumptions and capabilities.

While modern block ciphers, such as AES, have a block size of at least 128 bits, there are many 64-bit block ciphers, such as 3DES and Blowfish, that are still widely supported in Internet security protocols such as TLS, SSH, and IPsec. When used in CBC mode, these ciphers are known to be susceptible to collision attacks when they are used to encrypt around $2^{32}$ blocks of data (the so-called birthday bound). This threat has traditionally been dismissed as impractical since it requires some prior knowledge of the plaintext and even then, it only leaks a few secret bits per gigabyte. Indeed, practical collision attacks have never been demonstrated against any mainstream security protocol, leading to the continued use of 64-bit ciphers on the Internet. In this work, we demonstrate two concrete attacks that exploit collisions on short block ciphers. First, we present an attack on the use of 3DES in HTTPS that can be used to recover a secret session cookie. Second, we show how a similar attack on Blowfish can be used to recover HTTP BasicAuth credentials sent over OpenVPN connections. In our proof-of-concept demos, the attacker needs to capture about 785GB of data, which takes between 19-38 hours in our setting. This complexity is comparable to the recent RC4 attacks on TLS: the only fully implemented attack takes 75 hours. We evaluate the impact of our attacks by measuring the use of 64-bit block ciphers in real-world protocols. We discuss mitigations, such as disabling all 64-bit block ciphers, and report on the response of various software vendors to our responsible disclosure of these attacks.

We design and implement, PwoP, an efficient and scalable system for intrusion-tolerant and privacy-preserving multi-sensor fusion. PwoP develops and unifies techniques from dependable distributed systems and modern cryptography, and in contrast to prior works, can 1) provably defend against pollution attacks where some malicious sensors lie about their values to sway the final result, and 2) perform within the computation and bandwidth limitations of cyber-physical systems. PwoP is flexible and extensible, covering a variety of application scenarios. We demonstrate the practicality of our system using Raspberry Pi Zero W, and we show that PwoP is efficient in both failure-free and failure scenarios.

Cloud computing is becoming the preferred solution for efficiently dealing with the increasing amount of genomic data. Yet, outsourcing storage and processing of sensitive data, such as genomic data, comes with important concerns related to privacy and security. This calls for new sophisticated techniques that ensure data protection from untrusted cloud providers and still enables researchers to obtain useful information. We present a novel privacy-preserving algorithm for fully outsourcing the storage of large genomic data files to a public cloud and enable researchers to efficiently search for variants of interest. To preserve data and query confidentiality from possible leakage, our solution exploits optimal encoding for genomic variants and combines it with homomorphic encryption and private information retrieval. The proposed algorithm is implemented in C++ and evaluated on real data as part of the 2016 iDash genome privacy-protection challenge. Results show that our solution outperforms the state-of-the-art and enables researchers to search over millions of encrypted variants in a few seconds. As opposed to prior beliefs that sophisticated privacy-enhancing technologies (PETs) are unpractical for real operational settings, our solution demonstrates that, in the case of genomic data, PETs can represent very efficient enablers.

Proofs of liabilities are used for applications, function like banks or Bitcoin exchanges, to prove the sums of money in their dataset that they should owe. The Maxwell protocol, a cryptographic proof of liabilities scheme which relies on a data structure well known as the summation Merkle tree, utilizes a Merkle approach to prove liabilities in the decentralized setting, i.e., clients independently verify they are in the dataset with no trusted auditor. In this paper, we go into the Maxwell protocol and the summation Merkle tree. We formalize the Maxwell protocol and show it is not secure. We present an attack with which the proved liabilities using the Maxwell protocol are less than the actual value. This attack can have significant consequences: A Bitcoin exchange controlling a total of $n$ client accounts can present valid liabilities proofs including only one account balance in its dataset. We suggest two improvements to the Maxwell protocol and the summation Merkle tree, and present a formal proof for the improvement that is closest in spirit to the Maxwell protocol. Moreover, we show the DAM scheme, a micropayment scheme of Zerocash which adopts the Maxwell protocol as a tool to disincentivize double/multiple spending, is vulnerable to an multi-spending attack. We show the Provisions scheme, which adopts the Maxwell protocol to extend its privacy-preserving proof of liabilities scheme, is also infected by a similar attack.

Proof-of-Stake (PoS) protocols have been actively researched for the past few years. PoS finds direct applicability in permissionless blockchain platforms and emerges as one of the strongest candidates to replace the largely inefficient Proof of Work mechanism that is currently plugged in the majority of existing permissionless blockchain systems. Although a number of PoS variants have been proposed, these protocols suffer from a number of security shortcomings. Namely, most existing PoS variants are either subject to the nothing at stake, the long range, or the stake grinding attacks which considerably degrade security in the blockchain. These shortcomings do not result from a lack of foresight when designing these protocols, but are inherently due to the ease of manipulating "stake" when compared to other more established variants, such as "work". In this paper, we address these problems and propose a secure Proof of Stake protocol, PoTS, that leverages Trusted Execution Environments (TEEs), such as Intel SGX, to ensure that each miner can generate at most one block per "height" for strictly increasing heights—thus thwarting the problem of nothing at stake and a large class of long-range attacks. In combination with TEEs, PoTS additionally uses cryptographic techniques to also prevent grinding attacks and protect against posterior corruption. We show that our protocol is secure, in the sense of well-established cryptographic notions for blockchain protocols, down to realistic hardware assumptions on TEE and well-established cryptographic assumptions. Finally, we evaluate the performance of our proposal by means of implementation. Our evaluation results show that PoTS offers a strong tradeoff between security of performance of the underlying PoS protocol.

So far, the topic of merged mining has mainly been considered in a security context, covering issues such as mining power centralization or crosschain attack scenarios. In this work we show that key information for determining blockchain metrics such as the fork rate can be recovered through data extracted from merge mined cryptocurrencies. Specifically, we reconstruct a long-ranging view of forks and stale blocks in Bitcoin from its merge mined child chains, and compare our results to previous findings that were derived from live measurements. Thereby, we show that live monitoring alone is not sufficient to capture a large majority of these events, as we are able to identify a non-negligible portion of stale blocks that were previously unaccounted for. Their authenticity is ensured by cryptographic evidence regarding both, their position in the respective blockchain, as well as the Proof-of-Work difficulty. Furthermore, by applying this new technique to Litecoin and its child cryptocur rencies, we are able to provide the first extensive view and lower bound on the stale block and fork rate in the Litecoin network. Finally, we outline that a recovery of other important metrics and blockchain characteristics through merged mining may also be possible.

We present a simple, deterministic protocol for ledger consensus that tolerates Byzantine faults. The protocol is executed by $n$ servers over a synchronous network and can tolerate any number $t$ of Byzantine faults with $t<n/3$. Furthermore, the protocol can offer (i) transaction processing at full network speed, in the optimistic case where no faults occur, (ii) instant confirmation: the client can be assured in a single round-trip time that a submitted transaction will be settled, (iii) instant proof of settlement: the client can obtain a receipt that a submitted transaction will be settled. A derivative, equally simple, binary consensus protocol can be easily derived as well. We also analyze the protocol in case of network splits and temporary loss of synchrony arguing the safety of the protocol when synchrony is restored. Finally, we examine the covert adversarial model showing that Byzantine resilience is increased to $t<n/2$.

Blockchain is being praised as a technological innovation which allows to revolutionize how society trades and interacts. This reputation is in particular attributable to its properties of allowing mutually mistrusting entities to exchange financial value and interact without relying on a trusted third party. A blockchain moreover provides an integrity protected data storage and allows to provide process transparency. In this article we critically analyze whether a blockchain is indeed the appropriate technical solution for a particular application scenario. We differentiate between permissionless (e.g., Bitcoin/Ethereum) and permissioned (e.g. Hyperledger/Corda) blockchains and contrast their properties to those of a centrally managed database. We provide a structured methodology to determine the appropriate technical solution to solve a particular application problem. Given our methodology, we analyze in depth three use cases --- Supply Chain Management, Interbank and International Payments, and Decentralized Autonomous Organizations and conclude the article with an outlook for further opportunities.

In this paper, we construct a Lattice-based one-time Linkable Ring Signature (L2RS) scheme, which enables the public to verify if two or more signatures were generated by same signatory, whilst still preserving the anonymity of the signatory. The L2RS provides unconditional anonymity and security guarantees under the Ring Short Integer Solution (Ring-SIS) lattice hardness assumption. The proposed L2RS scheme is extended to be applied in a protocol that we called Lattice Ring Condential transaction (Lattice RingCT) RingCT v1.0, which forms the foundation of the privacy-preserving protocol in any post-quantum secure cryptocurrency such as Hcash.

Transaction throughput, confirmation latency and confirmation reliability are fundamental performance measures of any blockchain system in addition to its security. In a decentralized setting, these measures are limited by two underlying physical network attributes: communication capacity and speed-of-light propagation delay. Existing systems operate far away from these physical limits. In this work we introduce Prism, a new proof-of-work blockchain protocol, which can achieve 1) security against up to 50% adversarial hashing power; 2) optimal throughput up to the capacity C of the network; 3) confirmation latency for honest transactions proportional to the propagation delay D, with confirmation error probability exponentially small in the bandwidth-delay product CD ; 4) eventual total ordering of all transactions. Our approach to the design of this protocol is based on deconstructing the blockchain into its basic functionalities and systematically scaling up these functionalities to approach their physical limits.

Scalability of distributed ledgers is a key adoption factor. As an alternative to blockchain-based protocols, directed acyclic graph (DAG) protocols are proposed with the intention to allow a higher volume of transactions to be processed. However, there is still limited understanding of the behaviour and security considerations of DAG-based systems. We present an asynchronous, continuous time, and multi-agent simulation framework for DAG-based cryptocurrencies. We model honest and semi-honest actors in the system to analyse the behaviour of one specific cryptocurrency, IOTA. Our simulations show that the agents that have low latency and a high connection degree have a higher probability of having their transactions accepted in the network with honest and semi-honest strategies. Last, the simulator is built with extensibility in mind. We are in the process of implementing SPECTRE as well as including malicious agents.

Unspent Transaction Outputs (UTXOs) are the internal mechanism used in many cryp- tocurrencies to represent coins. Such representation has some clear benefits, but also entails some complexities that, if not properly handled, may leave the system in an inefficient state. Specifically, inefficiencies arise when wallets (the software responsible for transferring coins between parties) do not manage UTXOs properly when performing payments. In this paper, we study three cryptocurrencies: Bitcoin, Bitcoin Cash and Litecoin, by analyzing the actual state of their UTXO sets, that is, the status of their sets of spendable coins. These three cryptocurrencies are the top-3 UTXO based cryptocurrencies by market capitalization. Our analysis shows that the usage of each cryptocurrency is quite different, and let to different results. Furthermore, it also points out that the management of the transactions has not been always performed efficiently and then the actual state of the UTXO set for each cryptocurrency is far from ideal.

This document details analyses of verifiability properties of the CH-Vote v1.3 electronic voting protocol, as defined by the preprint publication [12]. Informally, these properties are: • Individual verifiability: a voter is convinced that a ballot confirmed as coming from the voter contains his intended vote • Ballot verifiability: all ballots that are confirmed contain correct votes • Eligibility uniqueness: there are no two distinct entries in the list of confirmed ballots which correspond to the same voter • Confirmed as intended: if a confirmed ballot is on the bulletin board for some voter, then that ballot records that voter’s voting intention • Universal verifiability: any party can verify that the votes on this board were tallied correctly The analyses employ the currently well-established approach used within the scientific community. Specifically, they rely on mathematical abstractions for the adversary and for the system under analysis, as well as mathematical formulations of the properties to be established. Mathematical proofs are then used to establish that (under certain assumptions) the security properties hold. We provide two types of analysis (which differ in the level of abstraction at which they operate). Part I contains a pen-and-paper computational/cryptographic analysis. Part II describes an automated symbolic analysis. Broadly speaking, both the symbolic and the computational analyses conclude that CH-Vote satisfy the desired security properties under several assumptions. The assumptions include, for example, computational assumptions (which mathematical problems are assumed to be hard), trust assumptions (which parties, if any, are assumed to behave honestly and what are parties assume to know before they interact with the system). Besides the concrete mathematical statements the analyses led to a number of recommendations which aim to improve the security. Part III concludes with a number of recommendations which reflect assumptions made in the analyses and weaknesses that were identified. The recommendations also sum up the results of a (light) code review of the code available via GitHub 1 – commit 9b0e7c9fcd409, from April 2017.

Bilinear pairings on elliptic curves are an active research field in cryptography. First cryptographic protocols based on bilinear pairings were proposed by the year 2000 and they are promising solutions to security concerns in different domains, as in Pervasive Computing and Cloud Computing. The computation of bilinear pairings that relies on arithmetic over finite fields is the most time-consuming in Pairing-based cryptosystems. That has motivated the research on efficient hardware architectures that improve the performance of security protocols. In the literature, several works have focused in the design of custom hardware architectures for pairings, however, flexible designs provide advantages due to the fact that there are several types of pairings and algorithms to compute them. This work presents the design and implementation of a novel programmable cryptoprocessor for computing bilinear pairings over binary fields in FPGAs, which is able to support different pairing algorithms and parameters as the elliptic curve, the tower field and the distortion map. The results show that high flexibility is achieved by the proposed cryptoprocessor at a competitive timing and area usage when it is compared to custom designs for pairings defined over singular/supersingular elliptic curves at a 128-bit security level.

Fairness in classification has become an increasingly relevant and controversial issue as computers replace humans in many of today’s classification tasks. In particular, a subject of much recent debate is that of finding, and subsequently achieving, suitable definitions of fairness in an algorithmic context. In this work, following the work of Hardt et al. (NIPS’16), we consider and formalize the task of sanitizing an unfair classifier C into a classifier C' satisfying an approximate notion of "equalized odds", or fair treatment. Our main result shows how to take any (possibly unfair) classifier C over a finite outcome space, and transform it—-by just perturbing the output of C—according to some distribution learned by just having black-box access to samples of labeled, and previously classified, data, to produce a classifier C' that satisfies fair treatment; we additionally show that our derived classifier is near-optimal in terms of accuracy. We also experimentally evaluate the performance of our method.