Atomic cross-chain swaps mitigate the interoper-ability challenges faced by current cryptocurrencies, thereby facilitating inter-currency exchange and trading between the distrusting users. Although numerous atomic swaps protocols utilizing Hash Timelock Contracts have been deployed and put into practice, they are substantially far from universality due to their inherent dependence of rich scripting language supported by the underlying blockchains. The recently proposed Universal Atomic Swaps protocol [IEEE S&P'22] represents a significant advancement in the field of scriptless cross-chain swaps by ingeniously delegating scripting functionalities to cryptographic locking mechanisms, particularly the adaptor signatures and timed commitment schemes. However, we identify a new form of attack termed the double-claiming attack that leverages these scriptless functionalities to undermine atomicity with a high probability. This attack is inherent to the designs adopted by the existing scriptless cross-chain swaps protocols as well as the payment channel networks. We further quantify the severity of this attack based on real-word swap transactions processed by the most widely deployed decentralized exchange platforms, highlighting the critical challenges in designing universal atomic swaps. To address the double-claiming attack while ensuring both security and practical universality, we also present a cross-chain swaps protocol called PipeSwap. Specifically, PipeSwap protects the frozen coins from being double-claimed by a novelly designed paradigm of pipelined coins flow that utilizes the techniques of two-hop swap and two-hop refund. In addition to a comprehensive security analysis in the Universal Composability framework, we develop a proof-of-concept implementation of PipeSwap with Schnorr/ECDSA signatures, and conduct extensive experiments to evaluate the overhead. The experimental results show that PipeSwap can be performed in less than 1.7 seconds while maintaining less than 7 kb of communication overhead on commodity machines.

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.

Sidechains have been widely used to improve the interoperability and scalability of blockchain systems. Despite several interesting sidechain constructions have been proposed in the literature, they suffer from the following downsides: (1) their designs do not easily support pluggable consensus mechanisms, and (2) their communication and storage costs for cross-chain operations are not yet optimized. In this work, we first propose Ge-Co, a generic sidechain construction to realize secure asset transfers between blockchains, supporting different consensus algorithms, such as Proof-of-Stake (PoS) and Proof-of-Work (PoW). Our design is built on top of the proposed voting committee selection approach and threshold signature schemes (TSS) and meanwhile, it achieves optimally succinct and constant proof size, only yielding lightweight communication and storage costs. Ge-Co works in the semi-adaptive corruption model. To provide stronger security, we further propose PoS-Co, a PoS-based sidechain construction in the fully-adaptive corruption model. PoS-Co is based on the proposed anonymous committee selection approach, and preserves optimally succinct proof. We also formally prove that Ge-Co can achieve the security properties of atomicity and timeliness. Finally, we develop a proof-of-concept (PoC) implementation for Ge-Co, and the results demonstrate that the design is efficient and practical.

Abstract With the rapid development of blockchains, blockchain systems are moving on from a stand-alone manner to cross-chain interactions, and achieving interoperability is emerging as one of the essential features of blockchains. Unfortunately, existing mechanisms such as XCLAIM mostly focus on exchanging assets between two blockchains and it is slow and expensive to process each cross-chain trade among more than two blockchains as multiple transactions are required. In this paper, we present Interopera, a decentralized and efficient cross-chain trading protocol among two or more blockchains. Interopera atomically processes each cross-chain trade faster and more cheaply with fewer transactions by a two-phase lock/unlock process. Interopera also achieves efficient cross-chain communication by our presented Partitioned-FlyClient and Tx-FlyClient. Partitioned-FlyClient is based on FlyClient but more efficient with smaller proof size, reducing the storage and bandwidth overheads. Tx-FlyClient maintains efficiency even when cross-chain trades become frequent, instead of other mechanisms only being effective under low cross-chain trades volumes. We also develop a proof-of-concept implementation and the results demonstrate high efficiency of our protocol.

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.

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 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.

Proxy re-encryption (PRE) provides a promising solution for encrypted data sharing in public cloud. When data owner Alice is going to share her encrypted data with data consumer Bob, Alice generates a re-encryption key and sends it to the cloud server (proxy); by using it, the proxy can transform Alice's ciphertexts into Bob's without learning anything about the underlying plaintexts. Despite that existing PRE schemes can prevent the proxy from recovering Alice's secret key by collusion attacks with Bob, due to the inherent functionality of PRE, it is inevitable that the proxy and Bob together are capable to gain and distribute Alices decryption capabilities. Even worse, the malicious proxy can deny that it has leaked the decryption capabilities and has very little risk of getting caught. To tackle this problem, we introduce the concept of Accountable Proxy Re-Encryption (APRE), whereby if the proxy is accused to abuse the re-encryption key for distributing Alice's decryption capability, a judge algorithm can decide whether it is innocent or not. We then present a non-interactive APRE scheme and prove its CPA security and accountability under DBDH assumption in the standard model. Finally, we show how to extend it to a CCA secure one.

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).

OAuth 2.0 is one of the most widely used Internet protocols for authorization/single sign-on (SSO) and is also the foundation of the new SSO protocol OpenID Connect. Due to its complexity and its flexibility, it is difficult to comprehensively analyze the security of the OAuth 2.0 standard, yet it is critical to obtain practical security guarantees for OAuth 2.0. In this paper, we present the first computationally sound security analysis of OAuth 2.0. First, we introduce a new primitive, the three-party authenticated secret distribution (3P-ASD for short) protocol, which plays the role of issuing the secret and captures the token issue process of OAuth 2.0. As far as we know, this is the first attempt to formally abstract the authorization technology into a general primitive and then define its security. Then, we present a sufficiently rich three-party security model for OAuth protocols, covering all kinds of authorization flows, providing reasonably strong security guarantees and moreover capturing various web features. To confirm the soundness of our model, we also identify the known attacks against OAuth 2.0 in the model. Furthermore, we prove that two main modes of OAuth 2.0 can achieve our desired security by abstracting the token issue process into a 3P-ASD protocol. Our analysis is not only modular which can reflect the compositional nature of OAuth 2.0, but also fine-grained which can evaluate how the intermediate parameters affect the final security of OAuth 2.0.

Proof-of-stake blockchain protocols are becoming one of the most promising alternatives to the energy-consuming proof-of-work protocols. However, one particularly critical threat in the PoS setting is the well-known long-range attacks caused by secret key leakage (LRSL attack). Specifically, an adversary can attempt to control/compromise accounts possessing substantial stake at some past moment such that double-spend or erase past transactions, violating the fundamental persistence property of blockchain. Puncturable signatures provide a satisfying solution to construct practical proof-of-stake blockchain resilient to LRSL attack, despite of the fact that existent constructions are not efficient enough for practical deployments. In this paper, we provide an in-depth study of puncturable signatures and explore its applications in the proof-of-stake blockchain. We formalize a security model that allows the adversary for adaptive signing and puncturing queries, and show a construction with efficient puncturing operations based on the Bloom filter data structure and strong Diffie-Hellman assumption. The puncturing functionality we desire is for a particular part of message, like prefix, instead of the whole message. Furthermore, we use puncturable signatures to construct practical proof-of-stake blockchain protocols that are resilient to LRSL attack, while previously the forward-secure signature is used to immunize this attack. We implement our scheme and provide experimental results showing that in comparison with the forward-secure signature, our construction performs substantially better on signature size, signing and verification efficiency, significantly on key update efficiency.

The traditional security notion of proxy re-encryption (PRE) focuses on preventing the proxy learning anything about the encrypted messages. However, such a basic security requirement is clearly not enough for scenarios where the proxy can collude with Bob. A desirable security goal is, therefore, to prevent a malicious proxy colluding with Bob to re-delegate Alice’s decryption right. In 2005, Ateniese et al. first proposed this intriguing problem called non-transferability, in the sense that the only way for Bob to transfer Alice’s decryption capability is to expose his own secret key. However, no solutions have achieved this property. In this paper, we positively resolve this open problem. In particular, we give the first construction of non-transferable PRE where the attacker is allowed to obtain one pair of keys consisting of Bob’s secret key and the corresponding re-encryption key. Using indistinguishability obfuscation and k-unforgeable authentication as main tools, our scheme is provably secure in the standard model. The essential idea behind our approach is to allow Bob’s secret key to be evoked in the process of decrypting Alice’s ciphertext while hiding the fact that only Bob could decrypt it by the obfuscated program. In addition, we also show a negative result: a CPA secure PRE scheme with ‘error-freeness’ property cannot be non-transferable.

Transport Layer Security (TLS) is one of the most widely used Internet protocols for secure communications. TLS 1.3, the next-generation protocol, is currently under development, with the latest candidate being draft-18. For flexibility and compatibility, TLS supports various ciphersuites and offers configurable selection of multiple protocol versions, which unfortunately opens the door to practical attacks. For example, although TLS 1.3 is now proven secure separately, coexisting with previous versions may be subject to backwards compatibility attacks. In this paper, we present a formal treatment of the multi-ciphersuite and backwards-compatibility security of TLS 1.3 (specifically, draft-18). We introduce a multi-stage security model, covering all known kinds of compositional interactions (w.r.t. ciphersuites and protocol versions) and reasonably strong security notions. Then we dissect the cross-ciphersuite attack regarding TLS 1.2 in our model, and show that the TLS 1.3 handshake protocol satisfies the multi-ciphersuite security, highlighting the strict necessity of including more information in the signature. Furthermore, we demonstrate how the backwards compatibility attack by Jager et al. can be identified owing to our model, and prove that the handshake protocol can achieve our desired strong security if certain countermeasures are adopted. Our treatment is also applicable to analyzing other protocols.

The Transport Layer Security (TLS) protocol is by far the most widely deployed protocol for securing communications and the Internet Engineering Task Force (IETF) is currently developing TLS 1.3 as the next-generation TLS protocol. The TLS standard features multiple modes of handshake protocols and supports many combinational running of successive TLS handshakes over multiple connections. Although each handshake mode is now well-understood in isolation, their composition in TLS 1.2 remains problematic, and yet it is critical to obtain practical security guarantees for TLS. In this paper, we present the first formal treatment of multiple handshakes protocols of TLS 1.3 candidates. First, we introduce a multi-level&stage security model, an adaptation of the BellareRogaway authenticated key exchange model, covering all kinds of compositional interactions between different TLS handshake modes and providing reasonably strong security guarantees. Next, we prove that candidate handshakes of TLS 1.3 draft meet our strong notion of multiple handshakes security. Our results confirm the soundness of TLS 1.3 security protection design. Such a multi-level&stage approach is convenient for analyzing the compositional design of the candidates with different session modes, as they establish dependencies of multiple sessions. We also identify the triple handshake attack of Bhargavan et al. on TLS 1.2 within our multiple handshakes security model. We show generically that the proposed fixes (RFC 7627) for TLS 1.2 offer good protection against multiple handshakes attacks.

ABSTRACT Strong designated verifier signature (SDVS) makes it possible for a signer to convince a designated verifier that he or she has signed a message in such a way that the designated verifier cannot transfer the signature to any third party and no third party can even verify the validity of the signature. Recently, Kang et al. proposed an identity‐based SDVS (IBSDVS) scheme that is claimed to be unforgeable and strong. However, in this paper, we show that their scheme is actually forgeable, delegatable, and not strong. We then propose an improved efficient IBSDVS scheme with short signature size and provide formal security proofs based on the computational Diffie–Hellman assumption in the random oracle model. We also show that the performance of our scheme outperforms all the existing IBSDVS schemes known in the literature. Furthermore, we propose an extension of our scheme achieving the stronger notion of nondelegatability and provide formal security proofs. The extended scheme is also showed to achieve high efficiency and short signature size. Copyright © 2012 John Wiley & Sons, Ltd.

Abstract A cross‐realm client‐to‐client password‐authenticated key agreement (C2C‐PAKA) protocol allows network clients from different realms managed by different servers to agree on a session key in an authentic manner based on easily memorizable passwords. In this paper, we present a generic framework for constructing a cross‐realm C2C‐PAKA protocol from any secure smart card‐based password authentication (PA‐SC) protocol. The security proof of our construction can be derived from the underlying PA‐SC protocol employing the same assumptions. Our generic framework appears to be the first one with provable security. In addition, compared with similar protocols, the instantiation of our construction achieves improved efficiency. Copyright © 2010 John Wiley & Sons, Ltd.