International Association
for Cryptologic Research

Can we sense our location in an unfamiliar environment by taking a sublinear-size sample of our surroundings? Can we efficiently encrypt a message that only someone physically close to us can decrypt? To solve this kind of problems, we introduce and study a new type of hash functions for finding shifts in sublinear time. A function $h:\{0,1\}^n\to \mathbb{Z}_n$ is a $(d,\delta)$ {\em locality-preserving hash function for shifts} (LPHS) if: (1) $h$ can be computed by (adaptively) querying $d$ bits of its input, and (2) $\Pr [ h(x) \neq h(x \ll 1) + 1 ] \leq \delta$, where $x$ is random and $\ll 1$ denotes a cyclic shift by one bit to the left. We make the following contributions.

Near-optimal LPHS via Distributed Discrete Log: We establish a general two-way connection between LPHS and algorithms for distributed discrete logarithm in the generic group model. Using such an algorithm of Dinur et al. (Crypto 2018), we get LPHS with near-optimal error of $\delta=\tilde O(1/d^2)$. This gives an unusual example for the usefulness of group-based cryptography in a post-quantum world. We extend the positive result to non-cyclic and worst-case variants of LPHS.

Multidimensional LPHS: We obtain positive and negative results for a multidimensional extension of LPHS, making progress towards an optimal 2-dimensional LPHS.

Applications: We demonstrate the usefulness of LPHS by presenting cryptographic and algorithmic applications. In particular, we apply multidimensional LPHS to obtain an efficient "packed" implementation of homomorphic secret sharing and a sublinear-time implementation of location-sensitive encryption whose decryption requires a significantly overlapping view.

Asynchronous BFT consensus can implement robust mission-critical decentralized services in the unstable or even adversarial wide-area network without relying on any form of timing assumption. Starting from the work of HoneyBadgerBFT (CCS 2016), several studies tried to push asynchronous BFT towards practice. In particular, in a recent work of Dumbo (CCS 2020), they redesigned the protocol backbone and used one multi-valued validated Byzantine agreement (MVBA) to replace $n$ concurrent asynchronous binary agreement (ABA) protocols and dramatically improved the performance.

Despite those efforts, asynchronous BFT protocols remain to be slow, and in particular, the latency is still quite large. There are two reasons contributing to the inferior performance: (1) the reliable broadcast (RBC) protocols still incur substantial costs; (2) the MVBA protocols are quite complicated and heavy, and all existing constructions need dozens of rounds and take the majority of he overall latency.

We first present a new construction of asynchronous BFT that replaces RBC instance with a cheaper broadcast component. It not only reduces the $O(n^3)$ message complexity incurred by $n$ RBCs to $O(n^2)$, but also saves up to 67% communications (in the presence of a fair network scheduler). Moreover, our technical core is a new MVBA protocol, Speeding MVBA, which is concretely more efficient than all existing MVBAs. It requires only 6 rounds in the best case and expected 12 rounds in the worst case (by contrast, several dozens of rounds in the MVBA from Cachin et al. [12] and the recent Dumbo-MVBA [32], and around 20 rounds in the MVBA from Abraham et al. [4]). Our new technique of the construction might be of independent interests.

We implemented Speeding Dumbo and did extensive tests among up to 150 EC2 t2.medium instances evenly allocated in 15 AWS regions across the globe. The experimental results show that Speeding Dumbo reduces the latency to about a half of Dumbo's, and also doubles the throughput of Dumbo, through all system scales from 4 nodes to 150 nodes. We also did tests to benchmark individual components such as the broadcasts and the MVBA protocols, which may be of interests for future improvements.

Blockchain is a type of Distributed Ledger Technology (DLT) that has been included in various types of fields due to its numerous benefits: transparency, efficiency, reduced costs, decentralization, and distributivity realized through public-key cryptography and hash functions. At the same time, the increased progress of quantum computers and quantum-based algorithms threatens the security of the classical cryptographic algorithms, in consequence, it represents a risk for the Blockchain technology itself. This paper briefly presents the most relevant algorithms and procedures that have contributed to the progress of quantum computing and the categories of post-quantum cryptosystems. We also included a description of the current quantum capabilities because their evolution directly influences the necessity of increasing post-quantum research. Further, the paper continues as a guide to understanding the fundamentals of blockchain technology, and the primitives that are currently used to ensure security. We provide an analysis of the most important cryptocurrencies according to their ranking by market capitalization (MC) in the context of quantum threats, and we end up with a review of post-quantum blockchain (PQB) schemes proposals.

This work investigates a generic way of combining two very effective and well-studied cryptanalytic tools, proposed almost 18 years apart, namely the boomerang attack introduced by Wagner in FSE 1999 and the yoyo attack by Ronjom et. al. in Asiacrypt 2017. In doing so, the s-box switch and ladder switch techniques are leveraged to embed a yoyo trail inside a boomerang trail. As an immediate application, a 6-round key recovery attack on AES-128 is mounted with time complexity of $2^{78}$. A 10-round key recovery attack on recently introduced AES-based tweakable block cipher Pholkos is also furnished to demonstrate the applicability of the new technique on AES-like constructions. The results on AES are experimentally verified by applying and implementing them on a small scale variant of AES. We provide arguments that draw a relation between the proposed strategy with the retracing boomerang attack devised in Eurocrypt 2020. To the best of our knowledge, this is the first attempt to merge the yoyo and boomerang techniques to analyze SPN ciphers and warrants further attention as it has the potential of becoming an important cryptanalysis tool.

Bootstrapping parameters for the approximate homomorphic-encryption scheme of Cheon et al., CKKS (Asiacrypt 17), are usually instantiated using sparse secrets to be efficient. However, using sparse secrets constrains the range of practical parameters within a tight interval, as they must support a large enough depth for the bootstrapping circuit but also be secure with respect to the sparsity of their secret.

We present a bootstrapping procedure for the CKKS scheme that combines both dense and sparse secrets. Our construction enables the use of parameters for which the homomorphic capacity is based on a dense secret, yet with a bootstrapping complexity that remains the one of a sparse secret and with a large security margin. Moreover, this also enables us to easily parameterize the bootstrapping circuit so that it has a negligible failure probability that, to the best of our knowledge, has never been achieved for the CKKS scheme. When using the parameters of previous works, our bootstrapping procedures enables a faster procedure with an increased precision and lower failure probability. For example we are able to bootstrapp a plaintext of $\mathbb{C}^{32768}$ in 20.2 sec, with 32.11 bits of precision, 285 bits of modulus remaining, a failure probability of $2^{-138.7}$ and 128 bit security.

Accelerated by the increased interconnection of highly accessible devices, the demand for effective and efficient protection of hardware designs against SCA is ever rising, causing its topical relevance to remain immense in both, academia and industry. Among a wide range of proposed countermeasures against SCA, masking is a highly promising candidate due to its sound foundations and well-understood security requirements. In addition, formal adversary models have been introduced, aiming to accurately capture real-world attack scenarios while remaining sufficiently simple to efficiently reason about the SCA resilience of designs. Here, the $d$-probing model is the most prominent and well-studied adversary model. Its extension, introduced as the robust $d$-probing model, covers physical defaults occurring in hardware implementations, particularly focusing on combinational recombinations (glitches), memory recombinations (transitions), and routing recombinations (coupling). With increasing complexity of modern cryptographic designs and logic circuits, formal security verification becomes ever more cumbersome. This started to spark innovative research on automated verification frameworks. Unfortunately, these verification frameworks mostly focus on security verification of hardware circuits in the presence of glitches, but remain limited in identification and verification of transitional leakage. To this end, we extend SILVER, a recently proposed tool for formal security verification of masked logic circuits, to also detect and verify information leakage resulting from combinations of glitches and transitions. Based on extensive case studies, we further confirm the accuracy and practical relevance of our methodology when assessing and verifying information leakage in hardware implementations.

The verifier-local revocation mechanism (VLR) is an ideal function of group signature. As long as the verifier knows the revocation list, he/she can verify the legitimacy of the signer, prevent the revoked user from impersonating a legitimate user for signature, ensure the timeliness of signature information and save resources. Group signature is often required to realize users' dynamic addition and revocation. Therefore, an efficient lattice signature scheme with a local revocation mechanism and alter the number of users has become an important topic. In this paper, a zero-knowledge proof scheme on the lattice has been proposed. Based on it, a group signature scheme with VLR has been constructed. This scheme can effectively join and revocation without generating the key pair again. The tracking mechanism uses an encryption scheme. As long as given a correct tracking key, the signer index can be opened quickly. And this algorithm has short public key, logarithmic signature length, and efficient implementation of the VLR function.

This paper refutes the conventional wisdom that information-theoretic BFT is impractical. We design and implement WaterBear, the first practical information-theoretic asynchronous Byzantine fault-tolerant (BFT) protocol. We also present a more efficient, quantum-secure asynchronous BFT protocol, WaterBear-QS, which, compared to WaterBear, additionally uses a collision-resistant hash function.

We show that WaterBear and WaterBear-QS are efficient under both failure-free and failure scenarios, achieving comparable performance to the state-of-the-art asynchronous BFT protocols. In particular, our failure case evaluation is thus far the most comprehensive evaluation for asynchronous BFT settings.

Reaching consensus is the single most crucial problem in fault-tolerant distributed computing. This paper studies asynchronous consensus with Byzantine failures commonly known as asynchronous binary Byzantine agreement (ABA). ABA is a key component as well as a bottleneck for (almost) all known asynchronous Byzantine fault-tolerant (BFT) protocols and asynchronous multi-party computation (MPC) with guaranteed output. This paper addresses two significant problems in ABA: we propose the first common-coin based ABA with 2 steps only in a round and the first practical solution on running ABA in a fully parallelizable manner. We first present Pillar, a new round-based ABA protocol using common coins, having 2 steps in a round. Pillar can be directly used to improve all practical asynchronous BFT protocols implemented and MPC protocols achieving guaranteed output. To demonstrate the performance of Pillar, we use it in the BEAT protocol based on the classic framework of Ben-Or, Kemler, and Rabin and HoneyBadgerBFT, and implement a new BFT protocol, called ACE, providing up to 2x the throughput of BEAT. We go on to suggest reproposable ABA (RABA), a generalized ABA primitive that allows a replica to change its mind and vote twice. In contrast to conventional ABA, RABA requires the protocol to be biased towards 1, but does not require external validity (via, e.g., expensive threshold signatures). We use Pillar to build Pisa, a signature-free RABA protocol that is as efficient as Pillar. We also show how to turn some other ABA protocols (including the one by Cachin, Kursawe, and Shoup) to RABA. We then propose a novel asynchronous BFT framework built on reliable broadcast (RBC) and RABA. This leads to the first fully parallelizable asynchronous BFT protocol, allowing all ABA instances to run in a strictly concurrent manner. Our concrete instantiation, called PACE, consistently and significantly outperforms existing asynchronous BFT protocols in terms of all metrics, having much fewer steps than all asynchronous BFT implemented for all practically large systems. PACE provides 6x the throughput of BEAT when there are 91 replicas. Such a solution can be directly used as a solution to run ABA in parallel, a procedure needed not just in BFT but in interactive consistency and MPC with guaranteed output. Our result, therefore, identifies RABA as a first-class primitive in distributed computing. Also, the PACE framework lays the foundation on information-theoretic asynchronous BFT and asynchronous BFT without public-key cryptography.

We propose a conceptually intuitive technique called algebraic meet-in-the-middle (MITM) attack in this paper. Different from the common MITM attacks where some intermediate state values are stored, several sets of linear equations will be stored in the algebraic MITM attack. Moreover, at the matching phase, it is necessary to first perform some linear transformations on the to-be-matched intermediate state value and only partial state bit information is used for the match. Once a match is found, retrieve the corresponding linear equation system and solve it to recover the full necessary information. This new technique fits very well with LowMC, a popular and important design using partial nonlinear layers. Based on it, we can reduce the memory complexity of the simple difference enumeration attack over state-of-the-art. Moreover, while an efficient algebraic technique to retrieve the full key from a differential trail of LowMC has been proposed at CRYPTO 2021, its time complexity is still exponential in the key size. In this work, we show how to reduce it to constant time when there are a sufficiently large number of active S-boxes in the trail. Specifically, the guess-and-determine strategy is no more adopted at the key-recovery phase, instead, we recover the full key by directly solving an overdefined system of quadratic equations. With the above new techniques, the attacks on LowMC and \mbox{LowMC-M} published at CRYPTO 2021 are further improved and some LowMC instances could be broken for the first time. Our results seem to indicate that partial nonlinear layers are still not well-understood.

An accountable subgroup multi-signature is a kind of multi-signature scheme in which any subgroup S of the group G of potential signers jointly sign a message $m$, ensuring that each member of S is accountable for the resulting signature. In this paper we propose three novel pairing-based accountable subgroup multi-signature (ASM) schemes. In the first one, we use Feldman's verifiable secret sharing scheme as an implicit authentication and proof-of-possession for setting up the group G. In the second one, the members participating in authentication is decided by the subgroup itself. In the third one, we consider a designated combiner managing the authentication process. All schemes that we propose here require fewer computations in signature generation, signature aggregation and verification phases than the pairing-based ASM scheme proposed by Boneh, Drijvers and Neven. Moreover, our first and the third ones solve the open problem of constructing an ASM scheme in which the subgroup S of signers is not known before the signature generation. Besides, we give a method of eliminating the combiner in case of knowing the subgroup of signers S in advance. Further we extend our proposed schemes to aggregated versions. For $n$ accountable subgroup multi-signatures, aggregated versions of our proposed schemes output an aggregated signature with size of a single group element and require $n+1$ pairings in aggregated signature verification, whereas the partial aggregated ASM scheme of Boneh, Drijvers and Neven gives an aggregated signature with size of $n+1$ group elements and requires $2n+1$ pairings in aggregated signature verification.

(Fully) homomorphic encryption ((F)HE) allows users to publicly evaluate circuits on encrypted data. Although public homomorphic evaluation property has various applications, (F)HE cannot achieve security against chosen ciphertext attacks (CCA2) due to its nature. To achieve both the CCA2 security and homomorphic evaluation property, Emura et al. (PKC 2013) introduced keyed-homomorphic public key encryption (KH-PKE) and formalized its security denoted by KH-CCA security. KH-PKE has a homomorphic evaluation key that enables users to perform homomorphic operations. Intuitively, KH-PKE achieves the CCA2 security unless adversaries have a homomorphic evaluation key. Although Lai et al. (PKC 2016) proposed the first keyed-fully homomorphic encryption (keyed-FHE) scheme, its security relies on the indistinguishability obfuscation (iO), and this scheme satisfies a weak variant of KH-CCA security. Here, we propose a generic construction of a KH-CCA secure keyed-FHE scheme from an FHE scheme secure against non-adaptive chosen ciphertext attack (CCA1) and a strong dual-system simulation-sound non-interactive zero-knowledge (strong DSS-NIZK) argument system by using the Naor-Yung paradigm. We show that there are a strong DSS-NIZK and an IND-CCA1 secure FHE scheme that are suitable for our generic construction. This shows that there exists a keyed-FHE scheme from simpler primitives than iO.

In this paper we study the security of the Bluetooth stream cipher E0 from the viewpoint it is a "difference stream cipher", that is, it is defined by a system of explicit difference equations over the finite field GF(2). This approach highlights some issues of the Bluetooth encryption such as the invertibility of its state transition map, a special set of 14 bits of its 132-bit state which when guessed imply linear equations among the other bits and finally a very small number of spurious keys compatible with a keystream of about 60 bits. Exploiting these issues, we implement an algebraic attack using Grobner bases, SAT solvers and Binary Decision Diagrams. Testing activities suggest that the version based on Grobner bases is the best one and it is able to attack E0 in about 2^79 seconds on an Intel i9 CPU. To the best of our knowledge, this work improves any previous attack based on a short keystream, hence fitting with Bluetooth specifications.

We construct the first tightly secure signature schemes in the multi-user setting with adaptive corruptions from lattices. In stark contrast to the previous tight constructions whose security is solely based on number-theoretic assumptions, our schemes are based on the Learning with Errors (LWE) assumption which is supposed to be post-quantum secure. The security of our scheme is independent of the numbers of users and signing queries, and it is in the non-programmable random oracle model. Our LWE-based scheme is compact namely, its signatures contain only a constant number of lattice vectors.

At the core of our construction are a new abstraction of the existing lossy identification (ID) schemes using dual-mode commitment schemes and a refinement of the framework by Diemert et al. (PKC 2021) which transforms a lossy ID scheme to a signature using sequential OR proofs. In combination, we obtain a tight generic construction of signatures from dual-mode commitments in the multi-user setting. Improving the work of Diemert et al., our new approach can be instantiated using not only the LWE assumption, but also an isogeny-based assumption. We stress that our LWE-based lossy ID scheme in the intermediate step uses a conceptually different idea than the previous lattice-based ones.

Of independent interest, we formally rule out the possibility that the aforementioned ``ID-to-Signature'' methodology can work tightly using parallel OR proofs. In addition to the results of Fischlin et al. (EUROCRYPT 2020), our impossibility result shows a qualitative difference between both forms of OR proofs in terms of tightness.

Crypto-ransomware has a process to encrypt the victim's files, and crypto-ransomware requests the victim for money for a key to decrypt the encrypted file. In this paper, we present new approaches to prevent crypto-ransomware by detecting block cipher algorithms for Internet of Things (IoT) platforms. The generic software of the AVR package and the lightweight block cipher library (FELICS) written in C language was trained through the neural network, and then we evaluated the result. Unlike the previous technique, the proposed method does not extract sequence and frequency characteristics, but considers opcodes and opcode sequences as words and sentences, performs word embedding, and then inputs them to the neural network based on the encoder structure of the transformer model. Through this approach, the file size was reduced by 0.5 times while maintaining a similar level of classification performance compared to the previous method. The detection success rate for the proposed method was evaluated with the F-measured value, which is the harmonic mean of precision and recall. In addition to achieving 98% crypto-ransomware detection success rates, classification by benign firmware and lightweight cryptography algorithm, Substitution-Permutation-Network (SPN) structure, Addition-Rotation-eXclusive-or structure (ARX) and normal firmware classification are also possible.

This paper considers the capability of 4-round Keccak-224/256/384/512 against the cryptanlysis involved by the quantum algorithm. In order to effectively find the corresponding rotational number for the rotational counterpart of preimage, we first establish a probabilistic algorithm based on the Grover search to guess a possible rotational number by using the fixed relations of bits pairs in some coordinates. This is committed to achieving that each iteration of searching the rotational counterparts contains only one run of 4-round Keccak variant applied for the verification, which can reduce the attack complexity in the quantum setting. Based on finding the rotational number under an acceptable randomness, we construct two attack models to focus on the recovery of preimage. In the first model, the Grover’s algorithm serves as finding out a rotational counterpart of the preimage. Through 64 attempts of checking the correct rotational number, the desired preimage can be obtained. In the second model, we abstract the finding of rotational counterparts into searching vertexes on a hypercube, and then, the SKW quantum algorithm is used to deal with the finding of the vertexes acted as rotational counterparts. Compared to the recent works in classical setting, we greatly reduce the attack complexity of preimage recovery. Furthermore, the first attack model is superior to the generic quantum preimage attack for 4-round Keccak-224/256/384/512, and the second model has slightly lower attack effect but more practicality on the 4-round Keccak-512/384, that is, the model is exponentially easier to implement in quantum circuit than both our first attack model and the generic quantum preimage attack.

The aim of this paper is to provide an overview on the newest results regarding the security of identity-based encryption schemes from quadratic residuosity. It is shown that the only secure schemes are the Cocks and Boneh-Gentry-Hamburg schemes (except of anonymous variations of them).

Coconut [NDSS 2019] is an attribute-based credential scheme with threshold issuance. We analyze its security properties. To this end, we define an ideal functionality for attribute-based access control with threshold issuance. We describe a construction that realizes our functionality. Our construction follows Coconut with a few changes. In particular, it modifies the protocols for blind issuance of credentials and for credential show so that user privacy holds against computationally unbounded adversaries. The modified protocols are slightly more efficient than those of Coconut. Our construction also extends the public key, which seems necessary to prove unforgeability.

Many decentralized systems rely on flooding protocols for message dissemination. In such a protocol, the sender of a message sends it to a randomly selected set of peers. These peers again send the message to their randomly selected peers, until every network participant has received the message. This type of protocols clearly fail in face of an adaptive adversary who can simply corrupt all peers of the sender and thereby prevent the message from being delivered. Nevertheless, flooding protocols are commonly used within protocols that aim to be cryptographically secure, most notably in blockchain protocols. While it is possible to revert to static corruptions, this gives unsatisfactory security guarantees, especially in the setting of a blockchain that is supposed to run for an extended period of time. To be able to provide meaningful security guarantees in such settings, we give precise semantics to what we call $\delta$-delayed adversaries in the Universal Composability (UC) framework. Such adversaries can adaptively corrupt parties, but there is a delay of time $\delta$ from when an adversary decides to corrupt a party until they succeed in overtaking control of the party. Within this model, we formally prove the intuitive result that flooding protocols are secure against $\delta$-delayed adversaries when $\delta$ is at least the time it takes to send a message from one peer to another plus the time it takes the recipient to resend the message. To this end, we show how to reduce the adaptive setting with a $\delta$-delayed adversary to a static experiment with an Erdős–Rényi graph. Using the established theory of Erdős–Rényi graphs, we provide upper bounds on the propagation time of the flooding functionality for different neighborhood sizes of the gossip network. More concretely, we show the following for security parameter $\kappa$, point-to-point channels with delay at most $\Delta$, and $n$ parties in total, with a sufficiently delayed adversary that can corrupt any constant fraction of the parties: If all parties send to $\Omega(\kappa)$ parties on average, then we can realize a flooding functionality with maximal delay $\mathcal{O}\bigl(\Delta \cdot \log (n) \bigr)$; and if all parties send to $\Omega\bigl( \sqrt{\kappa n \log (n)} \bigr)$ parties on average, we can realize a flooding functionality with maximal delay $\mathcal{O}(\Delta)$.

Arguments of knowledge are powerful cryptographic primitives that allow a prover to demonstrate that it knows a satisfying witness to a prescribed statement. Tremendous progress has been made in developing efficient argument systems by leveraging homomorphic structure in an increasingly composable and recursive manner. However, the extent to which homomorphisms can be composed and manipulated in the service of efficient argument systems is still not well understood. To this end, we introduce reductions of knowledge, a generalization of arguments of knowledge, which reduce checking a statement in one relation to checking a derived statement in another, and better capture the composable and recursive nature of arguments over homomorphisms. We construct and study the tensor reduction, which is capable of reducing any homomorphic statement composed via the tensor product, and provides knowledge soundness unconditionally when working over vector spaces. We show that tensor reductions generalize a large class of prior recursive techniques including the ubiquitous sumcheck protocol. We additionally show that tensor reductions can be employed to construct reductions of knowledge with logarithmic communication for familiar linear algebraic statements, and in turn, these can be composed to recover a reduction of knowledge for NP with logarithmic communication.