International Association
for Cryptologic Research

Extended Affine (EA) equivalence is the equivalence relation between two vectorial Boolean functions $F$ and $G$ such that there exist two affine permutations $A$, $B$, and an affine function $C$ satisfying $G = A \circ F \circ B + C$. While a priori simple, it is very difficult in practice to test whether two functions are EA-equivalent. This problem has two variants: EA-testing deals with figuring out whether the two functions can be EA-equivalent, and EA-recovery is about recovering the tuple $(A,B,C)$ if it exists. In this paper, we present a new efficient algorithm that efficiently solves the EA-recovery problem for quadratic functions. Though its worst-case complexity is obtained when dealing with APN functions, it supersedes all previously known algorithms in terms of performance, even in this case. This approach is based on the Jacobian matrix of the functions, a tool whose study in this context can be of independent interest. In order to tackle EA-testing efficiently, the best approach in practice relies on class invariants. We provide an overview of the literature on said invariants along with a new one based on the ortho-derivative which is applicable to quadratic APN functions, a specific type of functions that is of great interest, and of which tens of thousands need to be sorted into distinct EA-classes. Our ortho-derivative-based invariant is both very fast to compute, and highly discriminating.

In this paper, we present a new technique which can be used to find better linear approximations in ARX ciphers. Using this technique, we present the first explicitly derived linear approximations for 3 and 4 rounds of ChaCha and, as a consequence, it enables us to improve the recent attacks against ChaCha. Additionally, we present new differentials for 3 and 3.5 rounds of ChaCha that, when combined with the proposed technique, lead to further improvement in the complexity of the Differential-Linear attacks against ChaCha.

Blockchain technologies have received a great amount of attention, and its immutability is paramount to facilitate certain applications requiring persistent records. However, in many other use-cases, tremendous real-world incidents have exposed the harm of strict immutability. For example, illicit data stored in immutable blockchain poses numerous challenge for law enforcement agencies such as Interpol, and millions of dollars are lost due to the vulnerabilities of immutable smart contract. Moreover, ``Right to be Forgotten" (a.k.a. data erasure) has been imposed in new European Union's General Data Protection Regulation, thus causing immutable blockchains no longer compatible with personal data. Therefore, it is imperative (even legally required) to design efficient redactable blockchain protocols in a controlled way.

In this paper, we present a generic approach of designing redactable blockchain protocol in the permissionless setting with instant redaction, applied to both proof-of-stake blockchain and proof-of-stake blockchain with just different instantiations to randomly select ``committees'' according to stake or computational power. Our protocol can achieve the security against 1/2 (mildly adaptive) adversary bound, which is optimal in the blockchain protocol. It also offers public verifiability for redactable chains, where any edited block in the chain is publicly verifiable. Compared to previous solutions in permissionless setting, our redaction operation can be completed instantly, even only within one block in synchronous network, which is desirable for redacting harmful or sensitive data. Moreover, our protocol is compatible with most current blockchains requiring only minimal changes. Furthermore, we define the first ideal functionality of redactable blockchain following the language of universal composition, and prove that our protocol can achieve the security property of redactable common prefix, chain quality, and chain growth. Finally, we develop a proof-of-concept implementation, and conduct extensive experiments to evaluate the overhead incurred by redactions. The experimental results show that the overhead remains minimal for both online nodes and re-spawning nodes, which demonstrates the high efficiency of our design.

In addition to providing quantum-safe traditional PKI, lattices support advanced primitives such as identity-based encryption (IBE). These schemes have shown promising results in terms of practicality, but still have disadvantages such as the reliance on a single master key. Hierarchical identity-based encryption (HIBE) schemes address this problem, as well as lending themselves to more realistic organisational structures. To date, several HIBE schemes over lattices have been proposed but there has been little in the way of practical evaluation.

This paper provides the first complete C implementation and benchmarking of Latte, a promising HIBE scheme proposed by the United Kingdom (UK) The National Cyber Security Centre (NCSC) in 2017 and endorsed by European Telecommunications Standards Institute (ETSI). We also propose further optimisations for the KeyGen, Delegate, and sampling components of Latte. As expected, the KeyGen, Extract, and Delegate components are the most time consuming, with Extract experiencing a 35% decrease in op/s from the first to second hierarchical level at 80-bit security. Our optimised implementation of the Delegate function takes 1 second at this security level on a desktop machine at 4.2GHz, significantly faster than the order of minutes estimated in the ETSI technical report. Furthermore, our optimised Latte Encrypt/Decrypt implementation reaches speeds up to 4.6x faster than the ETSI implementation.

We introduce a new definition for key updates, called backward-leak uni-directional key updates, in updatable encryption (UE). This notion is a variant of uni-directional key updates for UE. We show that there exist UE schemes that are secure in the bi-directional key updates setting, but not secure in the backward-leak uni-directional key updates setting. This result is a contrast to the equivalence theorem by Jiang (Asiacrypt 2020), which says security in the bi-directional key updates setting is equivalent to security in the uni-directional key updates setting (we call the latter ``forward-leak uni-directional'' key updates to distinguish two types of uni-directional key updates in this paper).

We also construct two UE schemes with the following features.

- The first scheme is post-quantum secure in the backward-leak uni-directional key updates setting under the learning with errors assumption.

- The second scheme is secure in the no-directional key updates setting and based on indistinguishability obfuscation and one-way functions. This solves the open problem left by Jiang at Asiacrypt 2020.

We focus on exploring more potential of Longa and Sica's algorithm (ASIACRYPT 2012), which is an elaborate iterated Cornacchia algorithm that can compute short bases for 4-GLV decompositions. The algorithm consists of two sub-algorithms, the first one in the ring of integers $\mathbb{Z}$ and the second one in the Gaussian integer ring $\mathbb{Z}[i]$. We observe that $\mathbb{Z}[i]$ in the second sub-algorithm can be replaced by another Euclidean domain $\mathbb{Z}[\omega]$ $(\omega=\frac{-1+\sqrt{-3}}{2})$. As a consequence, we design a new twofold Cornacchia-type algorithm with a theoretic upper bound of output $C\cdot n^{1/4}$, where $C=\frac{3+\sqrt{3}}{2}\sqrt{1+|r|+|s|}$ with small values $r, s$ given by the curve. Besides, we give some applications of our new algotithm in some cuvres not considered in Longa and Sica's algorithm.

Succinct non-interactive arguments of knowledge (SNARKs) have found numerous applications in the blockchain setting and elsewhere. The most efficient SNARKs require a distributed ceremony protocol to generate public parameters, also known as a structured reference string (SRS). Our contributions are two-fold: 1. We give a security framework for non-interactive zero-knowledge arguments with a ceremony protocol. 2. We revisit the ceremony protocol of Groth's SNARK [Bowe et al., 2017]. We show that the original construction can be simplified and optimized, and then prove its security in our new framework. Importantly, our construction avoids the random beacon model used in the original work.

At Asiacrypt 2020, Moriya et al. introduced two new IND-CPA secure supersingular isogeny based Public Key Encryption (PKE) protocols: SiGamal and C-SiGamal. Unlike the PKEs canonically derived from SIKE and CSIDH, the new protocols provide IND-CPA security without the use of random oracles. SiGamal and C-SiGamal are however not IND-CCA secure. Moriya et al. suggested a variant of SiGamal that could be IND-CCA secure, but left its study as an open problem.

In this paper, we revisit the protocols introduced by Moriya et al. First, we show that the SiGamal variant suggested by Moriya et al. for IND-CCA security is, in fact, not IND-CCA secure. Secondly, we propose a new isogeny-based PKE protocol named InSIDH, obtained by simplifying SiGamal. InSIDH has smaller public keys and ciphertexts than (C-)SiGamal and it is more efficient. We prove that InSIDH is IND-CCA secure under CSIDH security assumptions and one Knowledge of Exponent-type assumption we introduce. Interestingly, InSIDH is also much closer to the CSIDH protocol, facilitating a comparison between SiGamal and CSIDH.

Verifiable random functions (VRFs), introduced by Micali, Rabin and Vadhan (FOCS’99), are the public-key equivalent of pseudorandom functions. A public verification key and proofs accompanying the output enable all parties to verify the correctness of the output. However, all known standard model VRFs have a reduction loss that is much worse than what one would expect from known optimal constructions of closely related primitives like unique signatures. We show that:

1. Every security proof for a VRF that relies on a non-interactive assumption has to lose a factor of Q, where Q is the number of adversarial queries. To that end, we extend the meta-reduction technique of Bader et al. (EUROCRYPT’16) to also cover VRFs. 2. This raises the question: Is this bound optimal? We answer this question in the affirmative by presenting the first VRF with a reduction from the non-interactive qDBDHI assumption to the security of VRF that achieves this optimal loss.

We thus paint a complete picture of the achievability of tight verifiable random functions: We show that a security loss of Q is unavoidable and present the first construction that achieves this bound.

The LWE problem with its ring variants is today the most prominent candidate for building efficient public key cryptosystems resistant to quantum computers. NTRU-type cryptosystems use an LWE-type variant with small max-norm secrets, usually with ternary coefficients from the set $\{-1,0,1\}$. The presumably best attack on these schemes is a hybrid attack that combines lattice reduction techniques with Odlyzko's Meet-in-the-Middle approach. Odlyzko's algorithm is a classical combinatorial attack that for key space size ${\cal S}$ runs in time ${\cal S}^{0.5}$. We substantially improve on this Meet-in-the-Middle approach, using the representation technique developed for subset sum algorithms. Asymptotically, our heuristic Meet-in-the-Middle attack runs in time roughly ${\cal S}^{0.25}$, which also beats the ${\cal S}^{\frac 1 3}$ complexity of the best known quantum algorithm.

For the round-3 NIST post-quantum encryptions NTRU-Encrypt and NTRU-Prime we obtain non-asymptotic instantiations of our attack with complexity roughly ${\cal S}^{0.35}$. As opposed to other combinatorial attacks, our attack benefits from larger LWE field sizes $q$, as they are often used in modern lattice-based signatures. For example, for BLISS signatures we obtain non-asymptotic combinatorial attacks in between ${\cal S}^{0.31}$ and ${\cal S}^{0.35}$, for GLP signatures in ${\cal S}^{0.3}$.

Our attacks do not invalidate the security claims of the aforementioned schemes. However, they establish improved combinatorial upper bounds for their security. We leave it is an open question whether our new Meet-in-the-Middle attack in combination with lattice reduction can be used to speed up the hybrid attack.

Keywords: Meet in the Middle, Representation Technique, NTRU/BLISS/GLP

This work introduces a new interactive oracle proof system based on the MPC-in-the-Head paradigm. To improve concrete efficiency and offer flexibility between computation time and communication size, a generic proof construction based on multi-round MPC protocols is proposed, instantiated with a specific protocol and implemented and compared to similar proof systems. Performance gains over previous work derive from a multi-party multiplication check optimized for the multi-round and MPC-in-the-Head settings. Of most interest among implementation optimizations is the use of identical randomness across repeated MPC protocol executions in order to accelerate computation without excessive cost to the soundness error. The new system creates proofs of SHA-256 pre-images of 43KB in 53ms with 16 MPC parties, or 23KB in 188ms for 128 parties. As a signature scheme, the non-interactive variant produces signatures, based on the AES-128 circuit, of 19KB in 4.2ms; this is 35% faster and 33 % larger than the Picnic3 scheme (13kB in 5.3ms for 16 parties) which is based on the 90% smaller LowMC circuit.

Mesh messaging applications allow users in relative proximity to communicate without the Internet. The most viable offering in this space, Bridgefy, has recently seen increased uptake in areas experiencing large-scale protests (Hong Kong, India, Iran, US, Zimbabwe, Belarus), suggesting its use in these protests. It is also being promoted as a communication tool for use in such situations by its developers and others. In this work, we report on a security analysis of Bridgefy. Our results show that Bridgefy, as analysed, permitted its users to be tracked, offered no authenticity, no effective confidentiality protections and lacked resilience against adversarially crafted messages. We verified these vulnerabilities by demonstrating a series of practical attacks on Bridgefy. Thus, if protesters relied on Bridgefy, an adversary could produce social graphs about them, read their messages, impersonate anyone to anyone and shut down the entire network with a single maliciously crafted message.

The introduction of the automatic search boosts the cryptanalysis of symmetric-key primitives to some degree. However, the performance of the automatic search is not always satisfactory for the search of long trails or ciphers with large state sizes. Compared with the extensive attention on the enhancement for the search with the mixed integer linear programming (MILP) method, few works care for the acceleration of the automatic search with the Boolean satisfiability problem (SAT) or satisfiability modulo theories (SMT) method. This paper intends to fill this vacancy. Firstly, with the additional encoding variables of the sequential counter circuit for the original objective function in the standard SAT method, we put forward a new encoding method to convert the Matsui's bounding conditions into Boolean formulas. This approach does not rely on new auxiliary variables and significantly reduces the consumption of clauses for integrating multiple bounding conditions into one SAT problem. Then, we evaluate the accelerating effect of the novel encoding method under different sets of bounding conditions. With the observations and experience in the tests, a strategy on how to create the sets of bounding conditions that probably achieve extraordinary advances is proposed. The new idea is applied to search for optimal differential and linear characteristics for multiple ciphers. For PRESENT, GIFT-64, RECTANGLE, LBlock, TWINE, and some versions in SIMON and SPECK families of block ciphers, we obtain the complete bounds (full rounds) on the number of active S-boxes, the differential probability, as well as the linear bias. The acceleration method is also employed to speed up the search of related-key differential trails for GIFT-64. Based on the newly identified 18-round distinguisher with probability $2^{-58}$, we launch a 26-round key-recovery attack with $2^{60.96}$ chosen plaintexts. To our knowledge, this is the longest attack on GIFT-64. Lastly, we note that the attack result is far from threatening the security of GIFT-64 since the designers recommended users to double the number of rounds under the related-key attack setting.

This paper presents three attack vectors of bit-wise cryptanalysis including rotational, bit-wise differential, and zero-sum distinguishing attacks on the AND-RX permutation Friet-PC, which is implemented in a lightweight authenticated encryption scheme Friet. First, we propose a generic procedure for a rotational attack on AND-RX cipher with round constants. By applying the proposed attack to Friet-PC, we can construct an 8-round rotational distinguisher with a time complexity of 2^{102}. Next, we explore single- and dual-bit differential biases, which are inspired by the existing study on Salsa and ChaCha, and observe the best bit-wise differential bias with 2^{−9.552}. This bias allows us to practically construct a 9-round bit-wise differential distinguisher with a time complexity of 2^{20.044}. Finally, we construct 13-, 15-, 17-, and 30-round zero-sum distinguishers with time complexities of 2^{31}, 2^{63}, 2^{127}, and 2^{383}, respectively. To summarize our study, we apply three attack vectors of bit-wise cryptanalysis to Friet-PC and show their superiority as effective attacks on AND-RX ciphers.

Sharding is an emerging technique to overcome scalability issues on blockchain based public ledgers. Without sharding, every node in the network has to listen to and process all ledger protocol messages. The basic idea of sharding is to parallelize the ledger protocol: the nodes are divided into smaller subsets that each take care of a fraction of the original load by executing lighter instances of the ledger protocol, also called shards. The smaller the shards, the higher the efficiency, as by increasing parallelism there is less overhead in the shard consensus.

In this vein, we propose a novel approach that leverages the sharding safety-liveness dichotomy. We separate the liveness and safety in shard consensus, allowing us to dynamically tune shard parameters to achieve essentially optimal efficiency for the current corruption ratio of the system. We start by sampling a relatively small shard (possibly with a small honesty ratio), and we carefully trade-off safety for liveness in the consensus mechanism to tolerate small honesty without losing safety. However, for a shard to be live, a higher honesty ratio is required in the worst case. To detect liveness failures, we use a so-called control chain that is always live and safe. Shards that are detected to be not live are resampled with increased shard size and liveness tolerance until they are live, ensuring that all shards are always safe and run with optimal efficiency. As a concrete example, considering a population of 10K parties, 30% corruption and 60-bit security, our design permits shards of size 200 parties in contrast to 6K parties in previous designs.

Moreover, in this highly concurrent execution setting, it is paramount to guarantee that both the sharded ledger protocol and its sub protocols (e.g., the shards) are secure under composition. To prove the security of our approach, we present ideal functionalities capturing a sharded ledger as well as ideal functionalities capturing the control chain and individual shard consensus, which needs adjustable liveness. We further formalize our protocols and prove that they securely realize the sharded ledger functionality in the UC framework.

The inherent difficulty of maintaining stateful environments over long periods of time gave rise to the paradigm of serverless computing, where mostly-stateless components are deployed on demand to handle computation tasks, and are teared down once their task is complete. Serverless architecture could offer the added benefit of improved resistance to targeted denial-of-service attacks, by hiding from the attacker the physical machines involved in the protocol until after they complete their work. Realizing such protection, however, requires that the protocol only uses stateless parties, where each party sends only one message and never needs to speaks again. Perhaps the most famous example of this style of protocols is the Nakamoto consensus protocol used in Bitcoin: A peer can win the right to produce the next block by running a local lottery (mining), all while staying covert. Once the right has been won, it is executed by sending a single message. After that, the physical entity never needs to send more messages.

We refer to this as the You-Only-Speak-Once (YOSO) property, and initiate the formal study of it within a new model that we call the YOSO model. Our model is centered around the notion of roles, which are stateless parties that can only send a single message. Crucially, our modelling separates the protocol design, that only uses roles, from the role-assignment mechanism, that assigns roles to actual physical entities. This separation enables studying these two aspects separately, and our YOSO model in this work only deals with the protocol-design aspect.

We describe several techniques for achieving YOSO MPC; both computational and information theoretic. Our protocols are synchronous and provide guaranteed output delivery (which is important for application domains such as blockchains), assuming honest majority of roles in every time step. We describe a practically efficient computationally-secure protocol, as well as a proof-of-concept information theoretically secure protocol.

Abstract

Modern cryptographic algorithms have an enormous key diversity, so if we want to test their strength for all the keys, it will take practically an infinite time. To avoid this, we use the sampling method, in which we examine a much smaller number of keys n and then we make estimation for the total key population N with a predetermined sampling error. For the generation of the n cipher outputs (samples) with the n corresponding keys, the critical questions are how many samples we will test and how large must be the size of each sample. The general rule is that, the sampling error is reduced as we increase the number of the samples. But since the tests must be executed in an acceptable time, we must compromise the above rule with some additional factors, such as the type of the cryptographic cipher, the kind and the size of the plain information and of course the available computer power. In this study we examine the interrelations of all the above factors, and we propose applicable solutions.

Keywords: Cryptography, Data encryption, Communication security, Computer security, Data security, Information security.

Event date: 21 August to 16 August 2021
Submission deadline: 25 April 2021

Event date: 19 July to 20 July 2021

Event date: 4 October to 6 October 2021
Submission deadline: 10 May 2021
Notification: 30 June 2021