Distributed common randomness generation (i.e., the common coin problem) is a cornerstone of randomized distributed computing. While a long line of research has sought scalable solutions, the asynchronous setting remains a challenge. Specifically, while Blum et al. (TCC'21) achieved sub-quadratic communication complexity, their approach lacks “balance”: certain nodes must still send Ω(n) messages, creating a scalability bottleneck. Furthermore, their solution only tolerates a 1/3 - ε fraction of corrupted nodes, whereas the classic construction by Cachin et al. (PODC'00) tolerates up to 1/2 under the same setup assumptions.

Git services such as GitHub, have been widely used to manage projects and enable collaborations among multiple entities. Just as in messaging and cloud storage, where end-to-end security has been gaining increased attention, such a level of security is also demanded for Git services. Content in the repositories (and the data/code supply-chain facilitated by Git services) could be highly valuable, whereas the threat of system breaches has become routine nowadays. However, existing studies of Git security to date (mostly open source projects) suffer in two ways: they provide only very weak security, and they have a large overhead.

Multi-valued Validated Byzantine Agreement (MVBA) is vital for asynchronous distributed protocols like asynchronous BFT consensus and distributed key generation, making performance improvements a long-standing goal. Existing communication-optimal MVBA protocols rely on computationally intensive public-key cryptographic tools, such as non-interactive threshold signatures, which are also vulnerable to quantum attacks. While hash-based MVBA protocols have been proposed to address these challenges, their higher communication overhead has raised concerns about practical performance. We present a novel MVBA protocol with adaptive security, relying exclusively on hash functions to achieve post-quantum security. Our protocol delivers near-optimal communication, constant round complexity, and significantly reduced latency compared to existing schemes, though it has sub-optimal resilience, tolerating up to 20% Byzantine corruptions instead of the typical 33%. For example, with n = 201 and input size 1.75 MB, it reduces latency by 81% over previous hash-based approaches.

There is a recent surge of studies on dynamic-committee proactive secret sharing (DPSS), in which not only will the shares be periodically refreshed (proactive secret sharing), but also the parties who hold the shares will be dynamically changed. It has direct applications in blockchain systems that require committees to manage confidential information, as well as in decentralized storage networks with dynamic participant involvement. Despite substantial attention, DPSS still has high communication complexity, particularly with large-size input data. In this article, we initiate the study of dynamic-committee proactive information dispersal (DPID). From a conceptual perspective, we can regard DPID as DPSS without the requirement for confidentiality. We model and construct DPID schemes with significantly reduced complexity. To demonstrate its efficiency, we also present a general framework for compiling our DPID into DPSS. By integrating our DPID construction, we achieve the first DPSS with much lower communication complexity for large-size data, whose benefits can be clearly shown in our experiments.

Directed Acyclic Graph (DAG) based protocols have shown great promise to improve the performance of blockchains. The CAP theorem shows that it is impossible to have a single system that achieves both liveness (known as dynamic availability) and safety under network partition. This paper explores two types of DAG-based protocols prioritizing liveness or safety, named structured dissemination and Graded Common Prefix (GCP), respectively. For the former, we introduce the first DAG-based protocol with constant expected latency, providing high throughput dynamic availability under the sleepy model. Its expected latency is 3Δ and its throughput linearly scales with participation. We validate these expected performance improvements over existing constant latency sleepy model BFT by running prototypes of each protocol across multiple machines. The latter, GCP, is a primitive that provides safety under network partition, while being weaker than standard consensus. As a result, we are able to obtain a construction that runs in only 2 communication steps, as opposed to the 4 steps of existing low latency partially synchronous BFT. In addition, GCP can easily avoid relying on single leaders' proposals, becoming more resilient to crashes. We also validate these theoretical benefits of GCP experimentally. We leverage our findings to extend the Ebb-and-Flow framework, where two BFT sub-protocols allow different types of clients in the same system to prioritize either liveness or safety. Our extension integrates our two types of DAG-based protocols. This provides a hybrid DAG-based protocol with high throughput, dynamical availability, and finality under network partitions, without running a standard consensus protocol twice as required in existing work.

Syndrome-based early epidemic warning plays a vital role in preventing and controlling unknown epidemic outbreaks. It monitors the frequency of each syndrome, issues a warning if some frequency is aberrant, identifies potential epidemic outbreaks, and alerts governments as early as possible. Existing systems adopt a cloud-assisted paradigm to achieve cross-facility statistics on the syndrome frequencies. However, in these systems, all symptom data would be directly leaked to the cloud, which causes critical security and privacy issues. In this paper, we first analyze syndrome-based early epidemic warning systems and formalize two security notions, i.e., symptom confidentiality and frequency confidentiality, according to the inherent security requirements. We propose extsf{EpiOracle}, a cross-facility early warning scheme for unknown epidemics. EpiOracle ensures that the contents and frequencies of syndromes will not be leaked to any unrelated parties; moreover, our construction uses only a symmetric-key encryption algorithm and cryptographic hash functions (e.g., [CBC]AES and SHA-3), making it highly efficient. We formally prove the security of EpiOracle in the random oracle model. We also implement an EpiOracle prototype and evaluate its performance using a set of real-world symptom lists. The evaluation results demonstrate its practical efficiency.

Recent progresses in asynchronous Byzantine fault-tolerant (BFT) consensus, e.g.$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$(CCS' 22) and$\mathsf {Tusk}$(EuroSys' 22), show promising performance through decoupling transaction dissemination and block agreement. However, when executed with a larger number$n$of nodes, like several hundreds, they would suffer from significant degradation in performance. Their dominating scalability bottleneck is the huge authenticator complexity: each node has to multicast$\mathcal {O}(n)$quorum certificates (QCs) and subsequently verify them for each block. This paper systematically investigates and resolves the above scalability issue. We first propose a signature-free asynchronous BFT consensus$\mathsf {FIN}\textrm {-}\mathsf {NG}$that adapts a recent signature-free asynchronous common subset protocol FIN (CCS' 23) into the state-of-the-art framework of concurrent broadcast and agreement. The liveness of$\mathsf {FIN}\textrm {-}\mathsf {NG}$relies on our non-trivial redesign of FIN's multi-valued validated Byzantine agreement towards achieving optimal quality.$\mathsf {FIN}\textrm {-}\mathsf {NG}$greatly improves the performance of FIN and already outperforms$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$in most deployment settings. To further overcome the scalability limit of$\mathsf {FIN}\textrm {-}\mathsf {NG}$due to$\mathcal {O}(n^{3})$messages, we propose$\mathsf {JUMBO}$, a scalable instantiation of$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$, with only$\mathcal {O}(n^{2})$complexities for both authenticators and messages. We use various aggregation and dispersal techniques for QCs to significantly reduce the authenticator complexity of original$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$implementations by up to$\mathcal {O}(n^{2})$orders. Finally, we implement our designs in Golang and experimentally demonstrated their enhanced scalability with hundreds of Amazon's AWS instances.$\mathsf {JUMBO}$and FIN-NG significantly outperform the state-of-the-art in (nearly) all deployment settings. Especially, when$n\ge$196,$\mathsf {JUMBO}$can attain a throughput that is more than 4× that of FIN and$\mathsf {Dumbo}\textrm {-}\mathsf {NG}$.

Recent progress of randomized fully asynchronous BFT consensus not only presents appealing performance but also ensures superior robustness against an asynchronous adversary that can arbitrarily delay network communication. But these results are mostly discussed in a static setting with fixed nodes. The root reason for the limit is the heavy dependence on a pre-configured threshold cryptosystem, which is critical to practically generate common randomness for overcoming FLP impossibility, but also fixes a designated set of participants. Even worse, most existing asynchronous BFT protocols rely on another strong assumption that messages sent among honest nodes must eventually be delivered, which could be plausible in the static setting (as all nodes can stay online forever to deliver messages) but becomes elusive in a dynamic blockchain, because a departing node might stop transmitting messages and subsequently cause inevitable message omissions as well as potential security violations To accommodate the enticing asynchronous BFT consensus into real-world blockchains where participating nodes are joining and leaving, we introduce Turritopsis, a novel dynamic asynchronous BFT framework that can (i) efficiently re-configure threshold cryptosystem to accommodate the change of consensus nodes and (ii) tolerate admissible message omissions caused by leaving participants. We first propose a dedicatedly optimized asynchronous distributed key refresh protocol that can quickly reset key materials of discrete logarithm threshold cryptosystem (e.g. BLS threshold signature), from which common randomness can be derived to ensure both safety and liveness despite the rotation of participating nodes. We then extend asynchronous BFT to tolerate a combination oftByzantine nodes andlhonest leaving nodes, where 3t+ 2lis smaller than the total numbernof currently participating nodes. This allows us to tolerate up tolleaving nodes that might behave like crashes due to their departures, while simultaneously preserving maximal resilience against ꜖(n– 2l)/3˩ malicious corruptions. We instantiated Turritopsis and implemented it in Python 3. Extensive experiments were conducted, spanning a network of up ton= 60 AWS EC2 nodes across 15 cities, revealing that Turritopsis exhibits performance closely comparable to its fixed-committee counterpart in both latency and throughput.

Exchange-assisted data trading (EADT) has become an essential paradigm in current data marketplaces. With data exchanges, sellers and buyers can trade data in an efficient and convenient way. However, existing EADT systems are vulnerable to privacy violations. Sensitive information about the data owned by sellers (manifested as attributes of the data) and the purchasing requirements of buyers (manifested as interests) are highly susceptible to leakage. On the one hand, buyers and sellers have direct access to the type of data supplied or desired before the data transaction is established. On the other hand, the information about transactions between the seller and buyer is transparent to the exchange, including the content of the transaction contract. In addition, the participants are likely to repudiate the content of previously accepted contracts or trigger a bidding war by contract first authorized by others, which raises threats towards authenticity and fairness. In this paper, we investigate the contract agreement in actual EADT systems, enumerate the inherent requirements of secrecy and fairness, and formally define them. Then we propose a privacy-preserving and fair contract agreement framework, dubbed PFCA, which consists of order-matching, negotiation, and authorization. We further propose a practical instantiation of PFCA, dubbed BestPFCA, utilizing efficient private set intersection (PSI), secure messaging (SM), and three-party signature (TPS). In addition, we also implement a BestPFCA prototype and conduct a comprehensive performance evaluation, which demonstrates the efficiency and practicality of BestPFCA.

The cloud has become pervasive, and we ask: how can we protect cloud data against the cloud itself? For secure user-to-user communication via a cloud server, End-to-End encryption has been formally studied, building on existing TLS channels without requiring new primitives. However, enabling user-to-same-user secure outsourced data storage–solving the analogous problem of “privacy from the server” while (1) relying on existing infrastructure and (2) supporting user mobility, remains open. Existing proposals, like password-protected secret sharing, target the same goal but are incompatible with existing cloud storage services. Specifically, they lack the simplicity needed to directly utilize existing cloud storage without requiring changes on the cloud side. Here, we propose a novel system for securely storing private data in existing cloud storage with the help of a key server (necessary, given the requirements). In our system, user data is secure against threats from the cloud server, the key server, and illegitimate users. Only the legitimate user can access the data on any device using a correct passphrase. Most importantly, our system does not require the storage server to support any newly programmable operations. Moreover, leveraging the existing App login, our system requires only one passphrase, which never leaves the user’s device and remains hidden from both servers. The security is proved under formal models, and its efficiency is demonstrated by experiments conducted on Amazon S3. Notably, a preliminary variant, based on our principles, was deployed by Snapchat in their My Eyes Only module, serving hundreds of millions of users!

The classical distributed key generation protocols (DKG) are resurging due to their widespread applications in blockchain. While efforts have been made to improve DKG communication, practical large-scale deployments are still yet to come due to various challenges, including the heavy overhead (particularly broadcast) in adversarial cases. In this paper, we propose a practical DKG for DLog-based cryptosystems, which achieves (quasi-)linear computation and communication per-node cost with the help of a common coin, even in the face of the maximal amount of Byzantine nodes. Moreover, our protocol is secure against adaptive adversaries, which can corrupt less than half of all nodes. The key to our improvements lies in delegating the most costly operations to an Any-Trust group together with a set of techniques for adaptive security. Moreover, we present a generic transformer that enables us to efficiently deploy a conventional distributed protocol like our DKG, even when the participants have different weights.

Targeted Denial-of-Service (DoS) attacks have been a practical concern for permissionless blockchains. Potential solutions, such as random sampling, are adopted by blockchains. However, the associated security guarantees have only been informally discussed in prior work. This is due to the fact that existing adversary models are either not fully capturing this attack or giving up certain design choices (as in the sleepy model or asynchronous network model), or too strong to be practical (as in the mobile Byzantine adversary model). This paper provides theoretical foundations and desired properties for consensus protocols that resist against targeted DoS attacks. In particular, we define the Mobile Crash Adaptive Byzantine (MCAB) model to capture such an attack. In addition, we identify and formalize two properties for consensus protocols under the MCAB model, and analyze their trade-offs. As case studies, we prove that Ouroboros Praos and Algorand are secure in our MCAB model, giving the first formal proofs supporting their security guarantee against targeted DoS attacks, which were previously only informally discussed. We also illustrate an application of our properties to secure a streamlined BFT protocol, chained Hotstuff, against targeted DoS attacks.

In recent years, opportunistic traders have extracted hundreds of millions of dollars from blockchains by reordering financial transactions. The problem stems from the fact that blockchains implement a state machine replication that orders transactions in any consistent order, regardless of the order in which these transactions were received. Existing attempts at enforcing the order perceived by honest participants suffer from cyclic dependencies or message delays. In this paper, we propose the Asynchronous Ordered Atomic Broadcast (AOAB) protocol. It does not suffer from cyclic dependencies or message delays because (i) it assigns an absolute timestamp to transactions, and (ii) it tolerates unbounded message delays. Besides being the first protocol to solve this problem, AOAB is communication-optimal and resilience-optimal. In particular, AOAB makes use of threshold signatures and information dissemination to reach a communication complexity of$\mathcal{O}(n\ell+\lambda n^{2})$, where$n$is the number of processes,$\ell$is the input (transaction) size and$\lambda$is the security parameter. This is optimal when$\ell\geq\lambda n$,

In blockchain applications such as digital goods exchange, private data may be transmitted from a data owner to a recipient through a transfer transaction. However, these blockchain applications often assume the underlying blockchain system is secure and reliable, and thus do not consider transaction failures. We find that a failed transfer transaction may disclose the private data to the recipient, but the data owner may not receive tokens as payments or the ledger may not correctly record the data trail. To handle transaction failures and protect private data, we propose a novel transaction commit-controlled release (CORE) protocol. With CORE, the private data can only be obtained by an intended recipient after the transfer transaction is committed, the data owner receives tokens, and the ledger correctly records the data trail. We perform security analysis of CORE, implement CORE and evaluate its performance over representative public and permissioned blockchains. The results of our extensive experiments show CORE introduces minor overhead in terms of transaction latency and transaction fees. We are the first to identify and address the generic private data disclosure issues in both public and permissioned blockchains.

Several distributed protocols, including distributed key generation (DKG) and interactive consistency (IC), depend on O(n) instances of Byzantine Broadcast or Byzantine Agreement among n nodes, resulting in Θ(n3) communication overhead.

Blockchain technologies have drawn a lot of attentions, and its immutability is paramount to applications requiring persistent records. However, tremendous real-world incidents have exposed the harm of strict immutability, such as the illicit data stored on Bitcoin and the loss of millions of dollars in vulnerable smart contracts. Moreover, “Right to be Forgotten” has been imposed in new General Data Protection Regulation (GDPR) of European Union, which is incompatible with blockchain's immutability. Therefore, it is imperative to design efficient redactable blockchain in a controlled way. In this paper, we present a generic design of redactable blockchain protocols in the permissionless setting, applied to both proof-of-stake and proof-of-work blockchains. Our protocol can (1) maintain the same adversary bound requirement as the underlying blockchain, (2) support various network environments, (3) offer public verifiability for any redaction, and (4) achieve instant redaction, even only within one slot in the best case, which is desirable for redacting harmful data. Furthermore, we define the first ideal protocol of redactable blockchain and conduct security analysis following the language of universal composition. Finally, we develop a proof-of-concept implementation showing that the overhead remains minimal for both online and re-spawning nodes, which demonstrates the high efficiency of our design.

Peer-to-peer (P2P) content delivery is up-and-coming to provide benefits comprising cost-saving and scalable peak-demand handling compared with centralized content delivery networks (CDNs), and also complementary to the popular decentralized storage networks such as Filecoin. However, reliable P2P delivery demands proper enforcement of delivery fairness, i.e., the deliverers should be rewarded in line with their in-time delivery. Unfortunately, most existing studies on delivery fairness are on the basis of non-cooperative game-theoretic assumptions that are arguably unrealistic in the ad-hoc P2P setting. We propose an expressive yet still minimalist security requirement for desired fair P2P content delivery, and give two efficient blockchain-enabled and monetary-incentivized solutions${\mathsf {FairDownload}}$and${\mathsf {FairStream}}$for P2P downloading and P2P streaming scenarios, respectively. Our designs not only ensure delivery fairness where deliverers are paid (nearly) proportional to their in-time delivery, but also guarantee exchange fairness where content consumers and content providers are also fairly treated. The fairness of each party can be assured even when other two parties collude to arbitrarily misbehave. Our protocols provide a general design of fetching content chunk from any specific position so the delivery can be resumed in the presence of unexpected interruption. Further, our systems are efficient in the sense of achieving asymptotically optimal on-chain costs and optimal delivery communication. We implement the prototype and deploy on the Ethereum Ropsten network. Extensive experiments in both LAN and WAN settings are conducted to evaluate the on-chain costs as well as the efficiency of downloading and streaming. Experimental results show the practicality and efficiency of our protocols.

An urgent demand of deploying BFT consensus (e.g., atomic broadcast) over the Internet is raised for implementing (permissioned) blockchain services. The deterministic synchronous protocols can be simple and fast in good network conditions, but are subject to denial-of-service (or even safety vulnerability) when synchrony assumption fails. Asynchronous protocols, on the contrary, are robust against the adversarial network, but are substantially more complicated and slower for the inherent use of randomness.

Despite recent progresses of practical asynchronous Byzantine-fault tolerant (BFT) consensus, the state-of-the-art designs still suffer from suboptimal performance. Particularly, to obtain maximum throughput, most existing protocols \rev with guaranteed linear amortized communication complexity require each participating node to broadcast a huge batch of transactions, which dramatically sacrifices latency. Worse still, the ƒ slowest nodes' broadcasts might never be agreed to output and thus can be censored (where ƒ is the number of faults). Implementable mitigation to the threat either uses computationally costly threshold encryption or incurs communication blow-up by letting the honest nodes to broadcast redundant transactions, thus causing further efficiency issues.

Efficient asynchronous Byzantine agreement (BA) protocols were mostly studied with private setups, e.g., pre-setup threshold cryptosystem. Challenges remain to reduce the large communication in the absence of such setups. Recently, Abraham et al. (PODC’21) presented the first asynchronous validated BA (VBA) with expected $\mathcal{O}$(n3) messages and $\mathcal{O}$ (1) rounds, relying on only public key infrastructure (PKI) setup, but the design still costs $\mathcal{O}$ (λn3logn) bits. Here n is the number of parties, and λ is a cryptographic security parameter.In this paper, we reduce the communication of private-setup free asynchronous BA to expected $\mathcal{O}$(λn3) bits. At the core of our design, we give a systematic treatment of common randomness protocols in the asynchronous network, and proceed as:•We give an efficient reasonably fair common coin protocol in the asynchronous setting with only PKI setup. It costs only $\mathcal{O}$ (λn3) bit and $\mathcal{O}$(1) rounds, and ensures that with at least 1/3 probability, all honest parties can output a common bit that is as if randomly flipped. This directly renders more efficient private-setup free asynchronous binary agreement (ABA) with expected $\mathcal{O}$(λn3) bits and $\mathcal{O}$(1) rounds.•Then, we lift our common coin to attain perfect agreement by using a single ABA. This gives us a reasonably fair random leader election protocol with expected $\mathcal{O}$(λn3) communication and expected constant rounds. It is pluggable in all existing VBA protocols (e.g., Cachin et al., CRYPTO’01; Abraham et al., PODC’19; Lu et al., PODC’20) to remove the needed private setup or distributed key generation (DKG). As such, the communication of private-setup free VBA is reduced to expected $\mathcal{O}$(λn3) bits while preserving fast termination in expected $\mathcal{O}$(1) rounds. Moreover, our result paves a generic path to private-setup free asynchronous BA protocols, as it is not restricted to merely improve Abraham et al.’s specific VBA protocol (PODC’21).Our results and techniques could be found useful and interesting for a broad array of applications such as asynchronous DKG and DKG-free asynchronous random beacon that is friendly for dynamic participation and reconfiguration.

With the emergence of large-scale decentralized applications, a scalable and efficient Byzantine Fault Tolerant (BFT) protocol of hundreds of replicas is desirable. Although the throughput of existing leader-based BFT protocols has reached a high level of 105requests per second for a small scale of replicas, it drops significantly when the scale increases.This paper focuses on preserving high throughput as the BFT protocol’s scale is increasing. We identify and analyze a major bottleneck to leader-based BFT protocols due to the excessive workload of the leader at large scales. A new metric of scaling factor is defined to capture whether a BFT protocol will get stuck when the scale gets larger, which can be used to measure the performance of throughput and scalability of BFT protocols. We propose "Leopard", the first leader-based BFT protocol that scales to multiple hundreds of replicas, and more importantly, preserves high throughput. We remove the bottleneck by introducing a technique of achieving the ideal constant scaling factor, which takes full advantage of the idle resource and balances the workload of the leader among all replicas. We implemented Leopard and evaluated its performance compared to HotStuff, a state-of-the-art leader-based BFT protocol. We ran extensive experiments with up to 600 replicas. The results show that Leopard achieves significant throughput improvements. In particular, the throughput of Leopard remains at a high level of 105when the scale is 600. It achieves a 5× throughput over HotStuff when the scale is 300, and the gap becomes wider as the scale further increases.

With the rapid evolution of the blockchain technologies, the interoperability of different blockchain systems is emerging as one of the essential features of blockchains. Sidechains, a mechanism providing communications between different blockchains, have been heralded as the crucial factor of blockchain interoperability. However, there are still issues that need to be addressed in terms of security and feasibility. In this article, for proof-of-stake (PoS) and proof-of-work (PoW) blockchains, we propose efficient sidechain constructions with fast cross-chain transfers and small proof size by novel cross-chain certificate generation process and committee selection methods. Moreover, we also provide an extra functionality of supporting instant cross-chain transfers, such that emergent cross-chain transactions can be processed immediately. Compared to prior sidechains, our PoS sidechain construction can achieve faster cross-chain transfers, which improves the promptness of cross-chain transfers. While our PoW sidechain construction is more efficient with smaller proof size, reducing the storage and bandwidth overhead. Furthermore, we formally prove our sidechain constructions satisfying the properties of atomicity and timeliness. Finally, we develop a proof-of-concept implementation of our sidechains, and the experimental results show our constructions is not only faster, but also efficient with low storage and bandwidth overhead.

Though the retailer gift card has been an ultra-practical marketing tactic to attract customers to spend more, it, on the contrary, also places a great number of customers in troublesome situations due to its current limitations. First, dealing with unwanted gift cards is often time-consuming, costly, or even risky due to the frequent occurrences of gift card resale frauds. Worse still, the issuance and redemption of gift cards happen inside the retailer as in a “black-box,” indicating that a compromised retailer can cheat customers (or even third-party auditors) to deny the issuances of some unredeemed gift cards. This paper proposes a practical middle-layer solution based on blockchain to address the fundamental issues of the existing gift card system, with incurring minimal changes to the current infrastructure.

HoneyBadgerBFT, proposed by Miller et al. [34] as the first practical asynchronous atomic broadcast protocol, demonstrated impressive performance. The core of HoneyBadgerBFT (HB-BFT) is to achieve batching consensus using asynchronous common subset protocol (ACS) of Ben-Or et al., constituted with n reliable broadcast protocol (RBC) to have each node propose its input, followed by n asynchronous binary agreement protocol (ABA) to make a decision for each proposed value (n is the total number of nodes).

With the rapid popularity of blockchain, decentralized human intelligence tasks (HITs) are proposed to crowdsource human knowledge without relying on vulnerable third-party platforms. However, the inherent limits of blockchain cause decentralized HITs to face a few "new" challenges. For example, the confidentiality of solicited data turns out to be the sine qua non, though it was an arguably dispensable property in the centralized setting. To ensure the "new" requirement of data privacy, existing decentralized HITs use generic zero-knowledge proof frameworks (e.g., SNARK), but scarcely perform well in practice, due to the inherently expensive cost of generality.We present a practical decentralized protocol for HITs, which also achieves the fairness between requesters and workers. At the core of our contributions, we avoid the powerful yet highlycostly generic zk-proof tools and propose a special-purpose scheme to prove the quality of encrypted data. By various nontrivial statement reformations, proving the quality of encrypted data is reduced to efficient verifiable decryption, thus making decentralized HITs practical. Along the way, we rigorously define the ideal functionality of decentralized HITs and then prove the security due to the ideal/real paradigm.We further instantiate our protocol to implement a system called Dragoon1, an instance of which is deployed atop Ethereum to facilitate an image annotation task used by ImageNet. Our evaluations demonstrate its practicality: the on-chain handling cost of Dragoon is even less than the handling fee of Amazon's Mechanical Turk for the same ImageNet HIT.

Multi-valued validated asynchronous Byzantine agreement (MVBA), proposed in the elegant work of Cachin et al. (CRYPTO '01), is fundamental for critical fault-tolerant services such as atomic broadcast in the asynchronous network. It was left as an open problem to asymptotically reduce the O(ℓn2 + λn2 + n3) communication (where n is the number of parties, ℓ is the input length, and λ is the security parameter). Recently, Abraham et al. (PODC '19) removed the n3 term to partially answer the question when input is small. However, in other typical cases, e.g., building atomic broadcast through MVBA, the input length ℓ ≥ λn, and thus the communication is dominated by the ℓn2 term and the problem raised by Cachin et al. remains open.

Blockchain technology has been increasingly used for decentralizing cloud-based Internet of Things (IoT) architectures to address limitations faced by centralized systems. While many existing efforts are successful in decentralization with multiple servers (i.e., full nodes) to handle faulty nodes, an important issue has arisen that external clients have to rely on a relay node to communicate with the full nodes in the blockchain. Compromization of such relay nodes may result in a security breach and even a blockage of IoT sensors from the network. In this article, we propose blockchain-based decentralized IoT management systems for censorship resistance, which include a “diffusion” function to deliver all messages from sensors to all full nodes and an augmented consensus protocol to check data losses, replicate processing outcome, and facilitate opportunistic outcome delivery. We also leverage public key aggregation to reduce communication complexity and signature verification. The experimental results from proof-of-concept implementation and deployment in a real distributed environment show the feasibility and effectiveness in achieving censorship resistance.

Blockchain, as an emerging decentralized architecture and distributed computing paradigm underlying Bitcoin and other cryptocurrencies, has attracted intensive attention in both research and applications recently. Blockchain, especially powered by chain-coded smart contracts, has the full potential of revolutionizing increasingly centralized cyber-physical-social systems (CPSSs) for constructions and applications, and reshaping traditional knowledge automation workflows. The key advantage of blockchain technology lies in the fact that it can enable the establishment of secured, trusted, and decentralized autonomous ecosystems for various scenarios, especially for better usage of the legacy devices, infrastructure, and resources.

Modern big data computing systems exemplified by Hadoop employ parallel processing based on distributed storage. The results produced by parallel tasks such as computing modules in scientific workflows or reducers in the MapReduce framework are typically stored in a distributed file system across multiple data nodes. However, most existing systems do not provide a mechanism to compose such distributed information, as required by many big data applications. We construct analytical cost models and formulate a Distributed Information Composition problem in Big Data Systems, referred to as DIC-BDS, to aggregate multiple datasets stored as data blocks in Hadoop Distributed File System (HDFS) using a composition operator of specific complexity to produce one final output. We rigorously prove that DIC-BDS is NP-complete, and propose two heuristic algorithms: Fixed-window Distributed Composition Scheme (FDCS) and Dynamic-window Distributed Composition Scheme with Delay (DDCS-D). We conduct extensive experiments in Google clouds with various composition operators of commonly considered degrees of complexity including O(n), O(n log n), and O(n^2). Experimental results illustrate the performance superiority of the proposed solutions over existing methods. Specifically, FDCS outperforms all other algorithms in comparison with a composition operator of complexity O(n) or O(n log n), while DDCS-D achieves the minimum total composition time with a composition operator of complexity O(n^2). These algorithms provide an additional level of data processing for efficient information aggregation in existing workflow and big data systems.

We design and implement the first private and anonymous decentralized crowdsourcing system ZebraLancer, and overcome two fundamental challenges of decentralizing crowdsourcing, i.e. data leakage and identity breach. First, our outsource-then-prove methodology resolves the tension between blockchain transparency and data confidentiality, which is critical in crowdsourcing use-case. ZebraLancer ensures: (i) a requester will not pay more than what data deserve, according to a policy announced when her task is published via the blockchain; (ii) each worker indeed gets a payment based on the policy, if he submits data to the blockchain; (iii) the above properties are realized not only without a central arbiter, but also without leaking the data to the open blockchain. Furthermore, the transparency of blockchain allows one to infer private information about workers and requesters through their participation history. On the other hand, allowing anonymity will enable a malicious worker to submit multiple times to reap rewards. ZebraLancer overcomes this problem by allowing anonymous requests/submissions without sacrificing the accountability. The idea behind is a subtle linkability: if a worker submits twice to a task, anyone can link the submissions, or else he stays anonymous and unlinkable across tasks. To realize this delicate linkability, we put forward a novel cryptographic concept, i.e. the common-prefix-linkable anonymous authentication. We remark the new anonymous authentication scheme might be of independent interest. Finally, we implement our protocol for a common image annotation task and deploy it in a test net of Ethereum. The experiment results show the applicability of our protocol with the existing real-world blockchain.

Blockchain technology has been increasingly used for decentralizing cloud-based Internet of Things (IoT) architectures to address some limitations faced by centralized systems. While many existing efforts are successful in leveraging blockchain for decentralization with multiple servers (full nodes) to handle faulty nodes, an important issue has arisen that external clients (also called lightweight clients) have to rely on a relay node to communicate with the full nodes in the blockchain. Compromization of such relay nodes may result in a security breach and even a blockage of IoT sensors from the network. We propose censorship resistant decentralized IoT management systems, which include a "diffusion" function to deliver all messages from sensors to all full nodes and an augmented consensus protocol to check data loss, replicate processing outcome, and facilitate opportunistic outcome delivery. We also leverage the cryptographic tool of aggregate signature to reduce the complexity of communication and signature verification.

This tutorial will present a systematic overview of {\em kleptography}: stealing information subliminally from black-box cryptographic implementations; and {\em cliptography}: defending mechanisms that clip the power of kleptographic attacks via specification re-designs (without altering the underlying algorithms). Despite the laudatory history of development of modern cryptography, applying cryptographic tools to reliably provide security and privacy in practice is notoriously difficult. One fundamental practical challenge, guaranteeing security and privacy without explicit trust in the algorithms and implementations that underlie basic security infrastructure, remains. While the dangers of entertaining adversarial implementation of cryptographic primitives seem obvious, the ramifications of such attacks are surprisingly dire: it turns out that -- in wide generality -- adversarial implementations of cryptographic (both deterministic and randomized) algorithms may leak private information while producing output that is statistically indistinguishable from that of a faithful implementation. Such attacks were formally studied in Kleptography. Snowden revelations has shown us how security and privacy can be lost at a very large scale even when traditional cryptography seems to be used to protect Internet communication, when Kleptography was not taken into consideration. We will first explain how the above-mentioned Kleptographic attacks can be carried out in various settings. We will then introduce several simple but rigorous immunizing strategies that were inspired by folklore practical wisdoms to protect different algorithms from implementation subversion. Those strategies can be applied to ensure security of most of the fundamental cryptographic primitives such as PRG, digital signatures, public key encryptions against kleptographic attacks when they are implemented accordingly. Our new design principles may suggest new standardization methods that help reducing the threats of subverted implementation. We also hope our tutorial to stimulate a community-wise efforts to further tackle the fundamental challenge mentioned at the beginning.

Notable recent security incidents have generated intense interest in adversaries which attempt to subvert---perhaps covertly---crypto\-graphic algorithms. In this paper we develop (IND-CPA) Semantically Secure encryption in this challenging setting. This fundamental encryption primitive has been previously studied in the "kleptographic setting," though existing results must relax the model by introducing trusted components or otherwise constraining the subversion power of the adversary: designing a Public Key System that is kletographically semantically secure (with minimal trust) has remained elusive to date. In this work, we finally achieve such systems, even when all relevant cryptographic algorithms are subject to adversarial (kleptographic) subversion. To this end we exploit novel inter-component randomized cryptographic checking techniques (with an offline checking component), combined with common and simple software engineering modular programming techniques (applied to the system's black box specification level). Moreover, our methodology yields a strong generic technique for the preservation of any semantically secure cryptosystem when incorporated into the strong kleptographic adversary setting.

Key extraction via measuring a physical quantity is a class of information theoretic key exchange protocols that rely on the physical characteristics of the communication channel, to enable the computation of a shared key by two parties that share no prior secret information. The key is supposed to be information theoretically hidden to an eavesdropper. Despite the recent surge of research activity in the area, concrete claims about the security of the protocols typically rely on channel abstractions that are not fully experimentally substantiated. In this paper, we propose a novel methodology for the experimental security analysis of these protocols. The crux of our methodology is a falsifiable channel abstraction that is accompanied by an efficient experimental approximation algorithm of the conditional min-entropy available to the parties given the view of the eavesdropper. We focus on the signal strength between two wirelessly communicating transceivers as the measured quantity, and we use an experimental setup to compute the conditional min-entropy of the channel given the view of the attacker which we find to be linearly increasing. Armed with this understanding of the channel, we showcase the methodology by providing a general protocol for key extraction in this setting that is shown to be secure for a concrete parameter selection. In this way, we provide a comprehensively analyzed wireless key extraction protocol that is demonstrably secure against passive adversaries assuming our falsifiable channel abstraction. Our use of hidden Markov models as the channel model and a dynamic programming approach to approximate conditional min-entropy might be of independent interest, while other possible instantiations of our methodology can be feasible and may be motivated by this paper.

We put forth a new cryptographic primitive called a Traitor Deterring Scheme (TDS). A TDS is a multi-recipient public-key encryption scheme where an authority issues decryption keys to a set of users. The distinguishing feature of a TDS is that secret-keys are issued only after the users provide some private information as a form of collateral. The traitor deterring property ensures that if a malicious coalition of users (aka "traitors") produces an unauthorized (aka "pirate") decryption device, any recipient of the device will be able to recover at least one of the traitors' collaterals with only black-box access to the device. On the other hand, honest users' collaterals are guaranteed to remain hidden. In this fashion a TDS deincentivizes malicious behavior among users.

Identity-Based Encryption (IBE) provides a compelling solution to the PKI management problem, however it comes with the serious privacy consideration that a trusted party (called the PKG) is required to generate (and hence also know) the secret keys of all users. This inherent key escrow problem is considered to be one of the major reasons hindering the wider utilization of IBE systems. In order to address this problem, Goyal [ 20 ] introduced the notion of accountable authority IBE (A-IBE), in which a judge can differentiate the PKG from the user as the source of a decryption software. Via this “tracing” mechanism, A-IBE deters the PKG from leaking the user’s secret key and hence offers a defense mechanism for IBE users against a malicious PKG. All previous works on A-IBE focused on specialized constructions trying to achieve different properties and efficiency enhancements. In this paper for the first time we show how to add accountability to any IBE scheme using oblivious transfer (OT), with almost the same ciphertext efficiency as the underlying IBE. Furthermore, we extend our generic construction to support identity reuse without losing efficiency. This property is desirable in practice as users may accidentally lose their secret keys and they -naturally- prefer not to abandon their identities. How to achieve this property was open until our work. Along the way, we first modify the generic construction and develop a new technique to provide public traceability generically. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Abstract We consider the problem of minimizing the communication in single-database private information retrieval protocols in the case where the length of the data to be transmitted is large. We present first rate-optimal protocols for 1-out-of-n computationallyprivate information retrieval (CPIR), oblivious transfer (OT), and strong conditional oblivious transfer (SCOT). These protocols are based on a new optimalrate leveled homomorphic encryption scheme for large-output polynomial-size branching programs, that might be of independent interest. The analysis of the new scheme is intricate: the optimal rate is achieved if a certain parameter s is set equal to the only positive root of a degree-(m + 1) polynomial, where m is the length of the branching program. We show, by using Galois theory, that even when m = 4, this polynomial cannot be solved in radicals. We employ the Newton-Puiseux algorithm to find a Puiseux series for s, and based on this, propose a Θ (logm)-time algorithm to find an integer approximation to s.

How is it possible to prevent the sharing of cryptographic functions? This question appears to be fundamentally hard to address since in this setting the owner of the key is the adversary: she wishes to share a program or device that (potentially only partly) implements her main cryptographic functionality. Given that she possesses the cryptographic key, it is impossible for her to be prevented from writing code or building a device that uses that key. She may though be deterred from doing so. We introduce leakage-deterring public-key cryptosystems to address this problem. Such primitives have the feature of enabling the embedding of owner-specific private data into the owner's public-key so that given access to any (even partially functional) implementation of the primitive, the recovery of the data can be facilitated. We formalize the notion of leakage-deterring in the context of encryption, signature, and identification and we provide efficient generic constructions that facilitate the recoverability of the hidden data while retaining privacy as long as no sharing takes place.