Computer Security – ESORICS 2020

Tamarin is a popular tool dedicated to the formal analysis of security protocols. One major strength of the tool is that it offers an interactive mode, allowing to go beyond what push-button tools can typically handle. Tamarin is for example able to verify complex protocols such as TLS, 5G, or RFID protocols. However, one of its drawback is its lack of automation. For many simple protocols, the user often needs to help Tamarin by writing specific lemmas, called “sources lemmas”, which requires some knowledge of the internal behaviour of the tool.In this paper, we propose a technique to automatically generate sources lemmas in Tamarin. We prove formally that our lemmas indeed hold, for arbitrary protocols that make use of cryptographic primitives that can be modelled with a subterm convergent equational theory (modulo associativity and commutativity). We have implemented our approach within Tamarin. Our experiments show that, in most examples of the literature, we are now able to generate suitable sources lemmas automatically, in replacement of the hand-written lemmas. As a direct application, many simple protocols can now be analysed fully automatically, while they previously required user interaction.

A common primitive in election and auction protocols is a plaintext equivalence test (PET) in which two ciphertexts are tested for equality of their plaintexts, and a verifiable proof of the test’s outcome is provided. The most commonly-cited PETs require at least one honest party, but many applications claim universal verifiability, at odds with this requirement. If a test that relies on at least one honest participant is mistakenly used in a place where a universally verifiable proof is needed, then a collusion by all participants can insert a forged proof of equality into the tallying transcript. We show this breaks universal verifiability for the JCJ/Civitas scheme among others, because the only PETs they reference are not universally verifiable. We then demonstrate how to fix the problem.

ARINC 429 is the most common data bus in use today in civil avionics. Despite this, the protocol lacks any form of source authentication. A technician with physical access to the bus is able to replace a transmitter by a rogue device, and receivers will accept its malicious data as they have no method of verifying the authenticity of messages.Updating the protocol would close off security loopholes in new aircrafts but would require thousands of airplanes to be modified. An interim solution is required. We propose a hardware fingerprinting method for the ARINC 429 data bus, and analyze its performance in a sender authentication setting. Our approach relies on the observation that changes in hardware, such as replacing a transmitter or a receiver with a rogue one, modify the electric signal of the transmission.In this paper we explore the feasibility of designing an intrusion detection system based on hardware fingerprinting. Our analysis includes both a theoretical Markov-chain model and an extensive empirical evaluation. For this purpose, we collected a data corpus of ARINC 429 data traces, which may be of independent interest since, to the best of our knowledge, no public corpus is available.In our experiments, we show that it is feasible for an intrusion detection system to achieve a near-zero false alarms per second, while detecting a rogue transmitter in under 50 ms, and detecting a rogue receiver in under 3 s. This would allow a rogue component installed by a malicious technician to be detected during the pre-flight checks, well before the aircraft takes off. This is made possible due to the fact that we rely on the analog properties, and not on the digital content of the transmissions. Thus we are able to detect a hardware switch as soon as it occurs, even if the data that is being transmitted is completely normal.

In this paper we point out an overlooked subtlety in providing proper security definitions of anonymous identity-based encryption (anonymous IBE) and its applications such as searchable encryption. Namely, we find that until now there is no discussion whether the widely used indistinguishability-based notion of anonymity for IBE implies simulation-based definition of anonymity, which directly captures the intuition that recipients’ IDs are not leaked from ciphertexts. We compensate this undesirable situation by providing a simulation-based notion, which requires that a ciphertext can be simulated without knowing the associated ID, by specializing the anonymity notion defined for more generalized notion of attribute-based encryption in previous work to the setting of IBE and then proving that this definition is equivalent to the conventional indistinguishability-based definition. We note that while the final result is something one would expect, our proof is not completely trivial. In particular, previous proofs that show the equivalence between semantic security and indistinguishability-based one in the setting where the security of payload is the main concern do not work immediately in our setting due to the difference between the semantics of identities and messages and the existence of the key extraction oracles.

A Private Information Retrieval (PIR) protocol allows a client to retrieve arbitrary elements from a database stored in a server without revealing to the server any information about the requested element. PIR is an important building block of many privacy-preserving protocols, and its efficient implementation is therefore of prime importance. Several concrete, practical PIR protocols have been proposed and implemented so far, particularly based on very low-depth somewhat homomorphic encryption. The main drawback of these protocols, however, is their large communication cost, especially in terms of the server’s reply, which grows like $$O(d\root d \of {n})$$ for an n-element database, where d is a parameter typically chosen as 2 or 3.In this paper, we describe an efficient PIR protocol called SHECS-PIR, based on deeper circuits and GSW-style homomorphic encryption. SHECS-PIR reduces the communication cost down to $$O(\log n)$$ removing all other factors apart from database size while maintaining a high level of efficiency. In fact, for large databases, we achieve faster server processing time in addition to more compact queries.

Puncturable encryption (PE), proposed by Green and Miers at IEEE S&P 2015, is a kind of public key encryption that allows recipients to revoke individual messages by repeatedly updating decryption keys without communicating with senders. PE is an essential tool for constructing many interesting applications, such as asynchronous messaging systems, forward-secret zero round-trip time protocols, public-key watermarking schemes and forward-secret proxy re-encryptions. This paper revisits PEs from the observation that the puncturing property can be implemented as efficiently computable functions. From this view, we propose a generic PE construction from the fully key-homomorphic encryption, augmented with a key delegation mechanism (DFKHE) from Boneh et al. at Eurocrypt 2014. We show that our PE construction enjoys the selective security under chosen plaintext attacks (that can be converted into the adaptive security with some efficiency loss) from that of DFKHE in the standard model. Basing on the framework, we obtain the first post-quantum secure PE instantiation that is based on the learning with errors problem, selective secure under chosen plaintext attacks (CPA) in the standard model. We also discuss about the ability of modification our framework to support the unbounded number of ciphertext tags inspired from the work of Brakerski and Vaikuntanathan at CRYPTO 2016.

Linear attack is a powerful known-plaintext cryptanalysis method on block ciphers, which has been successfully applied in DES, KATAN, SPECK and other ciphers. In this paper, we use deep learning networks to achieve linear attack on DES with plain-cipher pairs. Comparing with traditional linear attack algorithm, our work requires less knowledge about complex cryptanalysis as neural network can work well by data-driven. Thus, this paper has three main contributions. First, a new linear attack architecture based on deep residual network was proposed to train discriminative neural networks with auto-generated plain-cipher pair data. The results indicate that trained neural networks can effectively learn algorithmic representations of the XOR distributions of given linear expression on DES. Second, several novel neural network-based algorithms were designed to efficiently enforce key recovery on round-reduced DES using trained networks with moderate full and partial bits of linear expression as inputs. Third, as far as we know, it is the first time that neural networks are used to achieve known-plaintext attack on complex block ciphers.

The safety of artificial intelligence systems has aroused great concern due to the vulnerability of deep neural networks. Studies show that malicious modifications to the inputs of a network classifier, can fool the classifier and lead to wrong predictions. These modified inputs are called adversarial samples. In order to resolve this challenge, this paper proposes a novel and effective framework called Detection by Attack (DBA) to detect adversarial samples by Undercover Attack. DBA works by converting the difficult adversarial detection problem into a simpler attack problem, which is inspired by the espionage technique. It appears to be attacking the system, but it is actually defending the system. Reviewing the literature shows that this paper is the first attempt to introduce a detection method that can effectively detect adversarial samples in both images and texts. Experimental results show that the DBA scheme yields state-of-the-art detection performances in both detector-unaware ( $$95.66\%$$ detection accuracy on average) and detector-aware ( $$2.10\%$$ attack success rate) scenarios. Furthermore, DBA is robust to the perturbation size and confidence of adversarial samples. The code is available at https://github.com/Mrzhouqifei/DBA.

Online recommendation services, such as e-commerce sites, rely on a vast amount of knowledge about users/items that represent an invaluable resource. Part of this acquired knowledge is public and can be accessed by anyone through the Internet. Unfortunately, that same knowledge can be used by competitors or malicious users. A large body of research proposes methods to attack recommender systems, but most of these works assume that the attacker knows or can easily access the rating matrix. In practice, this information is not directly accessible, but can only be gathered via crawling.Considering such real-life limitations, in this paper, we assess the impact of different crawling approaches when attacking a recommendation service. From the crawled information, we mount different shilling attacks. We determine the value of the collected knowledge through the reconstruction of the user/item neighborhood. Our results show that while crawling can indeed bring knowledge to the attacker (up to 65% of neighborhood reconstruction), this will not be enough to mount a successful shilling attack in practice.

Active re-identification attacks pose a serious threat to privacy-preserving social graph publication. Active attackers create fake accounts to enforce structural patterns that can be used to re-identify legitimate users on published anonymised graphs, even without additional background knowledge. So far, this type of attacks has only been studied in the scenario where the inherently dynamic social graph is published once. In this paper, we present the first active re-identification attack in the more realistic scenario where a dynamic social graph is periodically published. Our new attack leverages tempo-structural patterns, created by a dynamic set of sybil nodes, for strengthening the adversary. We evaluate our new attack through a comprehensive set of experiments on real-life and synthetic dynamic social graphs. We show that our new attack substantially outperforms the most effective static active attack in the literature by increasing success probability by at least two times and efficiency by at least 11 times. Moreover, we show that, unlike the static attack, our new attack remains at the same level of efficiency as the publication process advances. Additionally, we conduct a study on the factors that may thwart our new attack, which can help design dynamic graph anonymisation methods displaying a better balance between privacy and utility.

We analyse whether the smartcards of the JavaCard platform correctly validate primality of domain parameters. The work is inspired by Albrecht et al. [1], where the authors analysed many open-source libraries and constructed pseudoprimes fooling the primality testing functions. However, in the case of smartcards, often there is no way to invoke the primality test directly, so we trigger it by replacing (EC)DSA and (EC)DH prime domain parameters by adversarial composites. Such a replacement results in vulnerability to Pohlig-Hellman [30] style attacks, leading to private key recovery.Out of nine smartcards (produced by five major manufacturers) we tested (See https://crocs.fi.muni.cz/papers/primality_esorics20 for more information), all but one have no primality test in parameter validation. As the JavaCard platform provides no public primality testing API, the problem cannot be fixed by an extra parameter check, making it difficult to mitigate in already deployed smartcards.

Maude-NPA is an analysis tool for cryptographic security protocols that takes into account the algebraic properties of the cryptosystem. Maude-NPA can reason about a wide range of cryptographic properties. However, some algebraic properties, and protocols using them, have been beyond Maude-NPA capabilities, either because the cryptographic properties cannot be expressed using its equational unification features or because the state space is unmanageable. In this paper, we provide a protocol transformation that can safely get rid of cryptographic properties under some conditions. The time and space difference between verifying the protocol with all the crypto properties and verifying the protocol with a minimal set of the crypto properties is remarkable. We also provide, for the first time, an encoding of the theory of bilinear pairing into Maude-NPA that goes beyond the encoding of bilinear pairing available in the Tamarin tool.

Trigger-action platforms empower users to interconnect various physical devices and online services with custom automation. While providing convenience, their centralized design raises privacy concerns for end users. Unlike prior work that consider privacy leakage to action services, we consider privacy leakage to compromised platforms. After investigating potential privacy exposure to a popular trigger-action platform, IFTTT, we identified three types of leakages: event data, trigger event presence, and device possession. We also found that 91% of the top 500 triggers on IFTTT potentially leak sensitive information to the platform, and 25% leak implicitly. To achieve the paradoxical goal of hiding the event data and presence while asking the platform to trigger corresponding actions when an event occurs, we propose Obfuscated Trigger-Action Platform (OTAP) and Anonymous Trigger-Action Platform (ATAP). ATAP additionally provides device set confidentiality at the cost of minor platform modification. Our schemes can preserve user privacy without sacrificing convenience, and are incrementally deployable in various use cases. Our work addresses a crucial missing piece in securing the trigger-action ecosystem, and can be integrated with solutions that ensure integrity against untrusted platforms or solutions that address untrusted vendor services and users.

Advanced Persistent Threats (APTs) are one of the main challenges in modern computer security. They are planned and performed by well-funded, highly-trained and often state-based actors. The first step of such an attack is the reconnaissance of the target. In this phase, the adversary tries to gather as much intelligence on the victim as possible to prepare further actions. An essential part of this initial data collection phase is the identification of possible gateways to intrude the target.In this paper, we aim to analyze the data that threat actors can use to plan their attacks. To do so, we analyze in a first step 93 APT reports and find that most (80%) of them begin by sending phishing emails to their victims. Based on this analysis, we measure the extent of data openly available of 30 entities to understand if and how much data they leak that can potentially be used by an adversary to craft sophisticated spear phishing emails. We then use this data to quantify how many employees are potential targets for such attacks. We show that 83% of the analyzed entities leak several attributes of uses, which can all be used to craft sophisticated phishing emails.

The threat of a cryptographically relevant quantum computer contributes to an increasing interest in the field of post-quantum cryptography (PQC). Compared to existing research efforts regarding the integration of PQC into the Transport Layer Security (TLS) protocol, industrial communication protocols have so far been neglected. Since industrial cyber-physical systems (CPS) are typically deployed for decades, protection against such long-term threats is needed. In this work, we propose two novel solutions for the integration of post-quantum (PQ) primitives (digital signatures and key establishment) into the industrial protocol Open Platform Communications Unified Architecture (OPC UA): a hybrid solution combining conventional cryptography with PQC and a solution solely based on PQC. Both approaches provide mutual authentication between client and server and are realized with certificates fully compliant to the X.509 standard. Moreover, we implement the two solutions and measure and evaluate their performance across three different security levels. All selected algorithms (Kyber, Dilithium, and Falcon) are candidates for standardization by the National Institute of Standards and Technology (NIST). We show that Falcon is a suitable option—especially—when using floating-point hardware provided by our ARM-based evaluation platform. Our proposed hybrid solution provides PQ security for early adopters but comes with additional performance and communication requirements. Our solution solely based on PQC shows superior performance across all evaluated security levels in terms of handshake duration compared to conventional OPC UA but comes at the cost of increased sizes for handshake messages.

In secret handshake schemes, the members in the same organization can anonymously authenticate each other and commonly negotiate a secret key for communication. Since its proposing in 2003, secret handshake schemes become an important privacy protection cryptographic technique on internet applications. In this paper, a secret handshake scheme based on coding theory (we call $$\mathsf {CSH}$$ ) is presented. This is the first code-based secret handshake scheme. $$\mathsf {CSH}$$ is constructed by combining the CFS signature system and Stern’s identification system, thus the security of $$\mathsf {CSH}$$ relies on the syndrome decoding problem just like the two above systems. Moreover, as far as we know, $$\mathsf {CSH}$$ is the first scheme to use a generic construction of Fiat-Shamir paradigm in secret handshake schemes. This may lead to a more generic framework construction.

Mix nets are often used to provide privacy in modern security protocols, through shuffling. Some of the most important applications, such as secure electronic voting, require mix nets that are verifiable. In the literature, numerous techniques have been proposed to make mix nets verifiable. Some of them have also been employed for securing real political elections.With the looming possibility of quantum computers and their threat to cryptosystems based on classical hardness assumptions, there is significant pressure to migrate mix nets to post-quantum alternatives. At present, no verifiable and practical post-quantum mix net with external auditing is available as a drop-in replacement of existing constructions. In this paper, we give the first such construction.We propose a verifiable decryption mix net which solely employs practical lattice-based primitives. We formally prove that our mix net provides a high level of verifiability, and even accountability which guarantees that misbehaving mix servers can also be identified. Verification is executed by a (temporarily trusted) public auditor whose role can easily be distributed. To demonstrate practicality for real-world systems, we provide detailed performance benchmarks on our stand-alone implementation based only on the most conservative lattice hardness assumptions.

As a widely used privacy-preserving technique for cryptocurrencies, Stealth Address constitutes a key component of Ring Confidential Transaction (RingCT) protocol and it was adopted by Monero, one of the most popular privacy-centric cryptocurrencies. Recently, Liu et al. [EuroS&P 2019] pointed out a flaw in the current widely used stealth address algorithm that once a derived secret key is compromised, the damage will spread to the corresponding master secret key, and all the derived secret keys thereof. To address this issue, Liu et al. introduced Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key (PDPKS scheme), which captures the functionality, security, and privacy requirements of stealth address in cryptocurrencies. They further proposed a paring-based PDPKS construction and thus provided a provably secure stealth address algorithm. However, while other privacy-preserving cryptographic tools for RingCT, such as ring signature, commitment, and range proof, have successfully found counterparts on lattices, the development of lattice-based stealth address scheme lags behind and hinders the development of quantum-resistant privacy-centric cryptocurrencies following the RingCT approach.In this paper, we propose the first lattice-based PDPKS scheme and prove its security in the random oracle model. The scheme provides (potentially) quantum security not only for the stealth address algorithm but also for the deterministic wallet. Prior to this, the existing deterministic wallet algorithms, which have been widely adopted by most Bitcoin-like cryptocurrencies due to its easy backup/recovery and trustless audits, are not quantum resistant.

Adaptor signatures, also known as scriptless scripts, have recently become an important tool in addressing the scalability and interoperability issues of blockchain applications such as cryptocurrencies. An adaptor signature extends a digital signature in a way that a complete signature reveals a secret based on a cryptographic condition. It brings about various advantages such as (i) low on-chain cost, (ii) improved fungibility of transactions, and (iii) advanced functionality beyond the limitation of the blockchain’s scripting language.In this work, we introduce the first post-quantum adaptor signature, named $${\mathsf {LAS}}$$ . Our construction relies on the standard lattice assumptions, namely Module-SIS and Module-LWE. There are certain challenges specific to the lattice setting, arising mainly from the so-called knowledge gap in lattice-based proof systems, that makes the realization of an adaptor signature and its applications difficult. We show how to overcome these technical difficulties without introducing additional on-chain costs. Our evaluation demonstrates that $${\mathsf {LAS}}$$ is essentially as efficient as an ordinary lattice-based signature in terms of both communication and computation. We further show how to achieve post-quantum atomic swaps and payment channel networks using $${\mathsf {LAS}}$$ .

Private function evaluation (PFE) allows to obliviously evaluate a private function on private inputs. PFE has several applications such as privacy-preserving credit checking and user-specific insurance tariffs. Recently, PFE protocols based on universal circuits (UCs), that have an inevitable superlinear overhead, have been investigated thoroughly. Specialized public key-based protocols with linear complexity were believed to be less efficient than UC-based approaches.In this paper, we take another look at the linear-complexity PFE protocol by Katz and Malka (ASIACRYPT’11): We propose several optimizations and split the protocol in different phases that depend on the function and inputs respectively. We show that HE-based PFE is practical when instantiated with state-of-the-art ECC and RLWE-based homomorphic encryption. Our most efficient implementation outperforms the most recent UC-based PFE implementation of Alhassan et al. (JoC’20) in communication for all circuit sizes and in computation starting from circuits of a few thousand gates already.

Machine learning has proved invaluable for a range of different tasks, yet it also proved vulnerable to evasion attacks, i.e., maliciously crafted perturbations of input data designed to force mispredictions. In this paper we propose a novel technique to verify the security of decision tree models against evasion attacks with respect to an expressive threat model, where the attacker can be represented by an arbitrary imperative program. Our approach exploits the interpretability property of decision trees to transform them into imperative programs, which are amenable for traditional program analysis techniques. By leveraging the abstract interpretation framework, we are able to soundly verify the security guarantees of decision tree models trained over publicly available datasets. Our experiments show that our technique is both precise and efficient, yielding only a minimal number of false positives and scaling up to cases which are intractable for a competitor approach.

As machine learning is deployed in more settings, including in security-sensitive applications such as malware detection, the risks posed by adversarial examples that fool machine-learning classifiers have become magnified. Black-box attacks are especially dangerous, as they only require the attacker to have the ability to query the target model and observe the labels it returns, without knowing anything else about the model. Current black-box attacks either have low success rates, require a high number of queries, produce adversarial images that are easily distinguishable from their sources, or are not flexible in controlling the outcome of the attack. In this paper, we present AdversarialPSO, (Code available: https://github.com/rhm6501/AdversarialPSOImages ) a black-box attack that uses few queries to create adversarial examples with high success rates. AdversarialPSO is based on Particle Swarm Optimization, a gradient-free evolutionary search algorithm, with special adaptations to make it effective for the black-box setting. It is flexible in balancing the number of queries submitted to the target against the quality of the adversarial examples. We evaluated AdversarialPSO on CIFAR-10, MNIST, and Imagenet, achieving success rates of 94.9%, 98.5%, and 96.9%, respectively, while submitting numbers of queries comparable to prior work. Our results show that black-box attacks can be adapted to favor fewer queries or higher quality adversarial images, while still maintaining high success rates.

Deep neural networks based object detection models have revolutionized computer vision and fueled the development of a wide range of visual recognition applications. However, recent studies have revealed that deep object detectors can be compromised under adversarial attacks, causing a victim detector to detect no object, fake objects, or mislabeled objects. With object detection being used pervasively in many security-critical applications, such as autonomous vehicles and smart cities, we argue that a holistic approach for an in-depth understanding of adversarial attacks and vulnerabilities of deep object detection systems is of utmost importance for the research community to develop robust defense mechanisms. This paper presents a framework for analyzing and evaluating vulnerabilities of the state-of-the-art object detectors under an adversarial lens, aiming to analyze and demystify the attack strategies, adverse effects, and costs, as well as the cross-model and cross-resolution transferability of attacks. Using a set of quantitative metrics, extensive experiments are performed on six representative deep object detectors from three popular families (YOLOv3, SSD, and Faster R-CNN) with two benchmark datasets (PASCAL VOC and MS COCO). We demonstrate that the proposed framework can serve as a methodical benchmark for analyzing adversarial behaviors and risks in real-time object detection systems. We conjecture that this framework can also serve as a tool to assess the security risks and the adversarial robustness of deep object detectors to be deployed in real-world applications.

We construct two tightly secure signature schemes based on the computational Diffie-Hellman (CDH) and factoring assumptions in the random oracle model. Our schemes are proven secure in the multi-user setting, and their security loss is constant and does not depend on the number of users or signing queries. They are the first schemes that achieve this based on standard search assumptions, as all existing schemes we are aware of are either based on stronger decisional assumptions, or proven tightly secure in the less realistic single-user setting. Under a concrete estimation, in a truly large scale, the cost of our CDH-based scheme is about half of Schnorr and DSA (in terms of signature size and running time for signing).

In 2016, Švenda et al. (USENIX 2016, The Million-key Question) reported that the implementation choices in cryptographic libraries allow for qualified guessing about the origin of public RSA keys. We extend the technique to two new scenarios when not only public but also private keys are available for the origin attribution – analysis of a source of GCD-factorable keys in IPv4-wide TLS scans and forensic investigation of an unknown source. We learn several representatives of the bias from the private keys to train a model on more than 150 million keys collected from 70 cryptographic libraries, hardware security modules and cryptographic smartcards. Our model not only doubles the number of distinguishable groups of libraries (compared to public keys from Švenda et al.) but also improves more than twice in accuracy w.r.t. random guessing when a single key is classified. For a forensic scenario where at least 10 keys from the same source are available, the correct origin library is correctly identified with average accuracy of 89% compared to 4% accuracy of a random guess. The technique was also used to identify libraries producing GCD-factorable TLS keys, showing that only three groups are the probable suspects.

We study the verification of security properties at the state machine level of a minimalistic device, called the MAC-in-the-Box (MITB). This device computes a message authentication code based on the SHA-3 hash function and a key that is stored on device, but never output directly. It is designed for secure password storage, but may also be used for secure key-exchange and second-factor authentication. We formally verify, in the HOL4 theorem prover, that no outside observer can distinguish this device from an ideal functionality that provides only access to a hashing oracle. Furthermore, we propose protocols for the MITB’s use in password storage, key-exchange and second-factor authentication, and formally show that it improves resistance against host-compromise in these three application scenarios.

The purpose of this paper is to test the accuracy of worst-case heuristic bounds on the noise growth in ring-based homomorphic encryption schemes. We use the methodology of Iliashenko (Ph.D. thesis, 2019) to provide a new heuristic noise analysis for the BGV scheme. We demonstrate that for both the BGV and FV schemes, this approach gives tighter bounds than previous heuristic approaches, by as much as 10 bits of noise budget. Then, we provide experimental data on the noise growth of HElib and SEAL ciphertexts, in order to evaluate how well the heuristic bounds model the noise growth in practice. We find that, in spite of our improvements, there is still a gap between the heuristic estimate of the noise and the observed noise in practice. We extensively justify that a heuristic worst-case approach inherently leads to this gap, and hence leads to selecting significantly larger parameters than needed. As an additional contribution, we update the comparison between the two schemes presented by Costache and Smart (CT-RSA, 2016). Our new analysis shows that the practical crossover point at which BGV begins to outperform FV occurs for very large plaintext moduli, well beyond the crossover point reported by Costache and Smart.

Due to substantial profit gain and economic rewards, decentralized cryptocurrency systems have become primary targets for attackers. Double-spending is one of the most rudimentary and collective risks. Even without high hash power, attackers can still increase the probability of double-spending by bribing other miners to subvert the consensus agreement. This kind of attack is called bribery attack and a number of bribery attack models have been proposed during last few years. The evaluation and comparison of bribery attack models remain problematic due to the lack of systematic methods to quantify them. In particular, the costs and benefits of attackers are rarely considered which influenced by many factors. We propose a quantitative analysis method for previous bribery attack models. For further exploration, we design a bribery attack model and introduce profit formulations based on our analysis method. We experimentally prove that our model can reduce costs and increase benefits of bribery attacks compared with comparable models. The result shows our quantitative method is instructive both for bribery attack designing and analyzing.

Software updates for blockchain systems become a real challenge when they impact the underlying consensus mechanism. The activation of such changes might jeopardize the integrity of the blockchain by resulting in chain splits. Moreover, the software update process should be handed over to the community and this means that the blockchain should support updates without relying on a trusted party. In this paper, we introduce the notion of updatable blockchains and show how to construct blockchains that satisfy this definition. Informally, an updatable blockchain is a secure blockchain and in addition it allows to update its protocol preserving the history of the chain. In this work, we focus only on the processes that allow securely switching from one blockchain protocol to another assuming that the blockchain protocols are correct. That is, we do not aim at providing a mechanism that allows reaching consensus on what is the code of the new blockchain protocol. We just assume that such a mechanism exists (like the one proposed in NDSS 2019 by Zhang et al.), and show how to securely go from the old protocol to the new one. The contribution of this paper can be summarized as follows. We provide the first formal definition of updatable ledgers and propose the description of two compilers. These compilers take a blockchain and turn it into an updatable blockchain. The first compiler requires the structure of the current and the updated blockchain to be very similar (only the structure of the blocks can be different) but it allows for an update process more simple, efficient. The second compiler that we propose is very generic (i.e., makes few assumptions on the similarities between the structure of the current blockchain and the update blockchain). The drawback of this compiler is that it requires the new blockchain to be resilient against a specific adversarial behaviour and requires all the honest parties to be online during the update process. However, we show how to get rid of the latest requirement (the honest parties being online during the update) in the case of proof-of-work and proof-of-stake ledgers.

The abundance and rich varieties of data are enabling many transformative applications of big data analytics that have profound societal impacts. However, there are also increasing concerns regarding the improper use of individual data owner’s private data. In this paper, we propose PrivacyGuard, a system that leverages blockchain smart contract and trusted execution environment (TEE) to enable individual’s control over the access and usage of their private data. Smart contracts are used to specify data usage policy, i.e., who can use what data under which conditions and what analytics to perform, while the distributed blockchain ledger is used to keep an irreversible and non-repudiable data usage record. To address the efficiency problem of on-chain contract execution and to prevent exposing private data on the publicly viewable blockchain, PrivacyGuard incorporates a novel TEE-based off-chain contract execution engine along with a protocol to securely commit the execution result onto blockchain. We have built and deployed a prototype of PrivacyGuard with Ethereum and Intel SGX. Our experiment result demonstrates that PrivacyGuard fulfills the promised privacy goal and supports analytics on data from a considerable number of data owners.

Identity-based cryptography (IBC) is fundamental to security and privacy protection. Identity-based authenticated encryption (i.e., signcryption) is an important IBC primitive, which has numerous and promising applications. After two decades of research on signcryption, recently a new cryptographic primitive, named higncryption, was proposed. Higncryption can be viewed as privacy-enhanced signcryption, which integrates public key encryption, entity authentication, and identity concealment (which is not achieved in signcryption) into a monolithic primitive. Here, briefly speaking, identity concealment means that the transcript of protocol runs should not leak participants’ identity information.In this work, we propose the first identity-based higncryption ( $$\mathsf {IBHigncryption}$$ ). The most impressive feature of $$\mathsf {IBHigncryption}$$ , among others, is its simplicity and efficiency. The proposed $$\mathsf {IBHigncryption}$$ scheme is essentially as efficient as the fundamental CCA-secure Boneh-Franklin IBE scheme [12], while offering entity authentication and identity concealment simultaneously. Compared to the identity-based signcryption scheme [8], which is adopted in the IEEE P1363.3 standard, our $$\mathsf {IBHigncryption}$$ scheme is much simpler, and has significant efficiency advantage in total. Besides, our $$\mathsf {IBHigncryption}$$ enjoys forward $$\mathsf {ID}$$ -privacy, receiver deniability and x-security simultaneously. In addition, the proposed $$\mathsf {IBHigncryption}$$ has a much simpler setup stage with smaller public parameters, which in particular does not have the traditional master public key.

Deployment of DNSSEC, although increasing, still suffers from many practical issues that results in a false sense of security. While many domains outsource zone management, they also have to outsource DNSSEC key management to the DNS operator, making the operator an attractive target for attackers. Moreover, DNSSEC does not provide any sort of protection in the case the operator itself decides to serve false information, for example, if it gets compromised.In this work, we show how to use techniques from threshold ECDSA: (1) to protect keys such that domains do not reveal their signing keys to a DNS operator, and (2) to protect the operational integrity of DNS operator. As a result of being highly specialized, prior work on threshold ECDSA has focused on a limited set of threat models, and none have so far considered techniques to amortize signature generation. Our work takes a different approach and presents a generic technique for obtaining a threshold ECDSA protocol from any secure multiparty computation protocol that works over an appropriate finite field. We show how this technique lends itself to very efficient threshold signing protocols by comparing it against state-of-the-art protocols from both academia and industry. For similar threat models, our protocols are as fast as the previous best protocol in terms of signing, and up to an order of magnitude faster for key generation on a fast network. Finally, we show how to integrate our application into a widely used DNS management software and demonstrate through experiments the overhead compared to traditional DNSSECs.

Private information retrieval (PIR) allows a client to retrieve data from a database without the database server learning what data is being retrieved. Although many PIR schemes have been proposed in the literature, almost all of these focus on retrieval of a single database element, and do not consider more flexible retrieval queries such as basic range queries. Furthermore, while practically-oriented database schemes aiming at providing flexible and privacy-preserving queries have been proposed, to the best of our knowledge, no formal treatment of range queries has been considered for these. In this paper, we firstly highlight that a simple extension of the standard PIR security notion to range queries, is insufficient in many usage scenarios, and propose a stronger security notion aimed at addressing this. We then show a simple generic construction of a PIR scheme meeting our stronger security notion, and propose a more efficient direct construction based on function secret sharing – while the former has a round complexity logarithmic in the size of the database, the round complexity of the latter is constant. Finally, we report on the practical performance of our direct construction.

Bitcoin-like blockchains use a proof-of-work (PoW) mechanism, where security holds if the majority of the computing power is under the control of honest players. However, this assumption has been seriously challenged recently, and Bitcoin-like systems fail if this assumption is violated. In this work we propose a novel 2-hop blockchain protocol that combines PoW and proof-of-stake (PoS) mechanisms. Our analysis shows that the protocol is secure as long as the honest players control a majority of the collective resources (which consist of both computing power and stake). In particular, even if the adversary controls more than 50% of the computing power, security still holds if the honest parties hold sufficiently high stake in the system. As an added contribution, our protocol also remains secure against adaptive adversaries.

We initiate a systematic study on the light-client protocol of permissionless blockchains, in the setting where full nodes and light clients are rational. In the game-theoretic model, we design a superlight-client protocol to enable a light client to employ some relaying full nodes (e.g., two or one) to read the blockchain. The protocol is “generic”, i.e., it can be deployed disregarding underlying consensuses, and it is also “superlight”, i.e., the computational cost of the light client to predicate the (non)existence of a transaction in the blockchain becomes a small constant. Since our protocol resolves a fundamental challenge of broadening the usage of blockchain technology, it captures a wide variety of important use-cases such as multi-chain wallets, DApp browsers and more.

While various covert botnets were proposed in the past, they still lack complete anonymization for their servers/botmasters or suffer from slow communication between the botmaster and the bots. In this paper, we propose a new generation hybrid botnet that covertly and efficiently communicates over Bitcoin Lightning Network (LN), called LNBot. LN is a payment channel network operating on top of Bitcoin network for faster Bitcoin transactions with negligible fees. Exploiting various anonymity features of LN, we designed a scalable two-layer botnet which completely anonymize the identity of the botmaster. In the first layer, the botmaster sends commands anonymously to the C&C servers through LN transactions. Specifically, LNBot allows botmaster’s commands to be sent in the form of surreptitious multihop LN payments, where the commands are encoded with ASCII or Huffman encoding to provide covert communications. In the second layer, C&C servers further relay those commands to the bots they control in their mini-botnets to launch any type of attacks to victim machines. We implemented a proof-of-concept on the actual LN and extensively analyzed the delay and cost performance of LNBot. Our analysis show that LNBot achieves better scalibility compared to the other similar blockchain botnets with negligible costs. Finally, we also provide and discuss a list of potential countermeasures to detect LNBot activities and minimize its impacts.