International Association
for Cryptologic Research

The evasive LWE assumption, proposed by Wee [Eurocrypt'22 Wee] for constructing a lattice-based optimal broadcast encryption, has shown to be a powerful assumption, adopted by subsequent works to construct advanced primitives ranging from ABE variants to obfuscation for null circuits. However, a closer look reveals significant differences among the precise assumption statements involved in different works, leading to the fundamental question of how these assumptions compare to each other. In this work, we initiate a more systematic study on evasive LWE assumptions: (i) Based on the standard LWE assumption, we construct simple counterexamples against three private-coin evasive LWE variants, used in [Crypto'22 Tsabary, Asiacrypt'22 VWW, Crypto'23 ARYY] respectively, showing that these assumptions are unlikely to hold. (ii) Based on existing evasive LWE variants and our counterexamples, we propose and define three classes of plausible evasive LWE assumptions, suitably capturing all existing variants for which we are not aware of non-obfuscation-based counterexamples. (iii) We show that under our assumption formulations, the security proofs of [Asiacrypt'22 VWW] and [Crypto'23 ARYY] can be recovered, and we reason why the security proof of [Crypto'22 Tsabary] is also plausibly repairable using an appropriate evasive LWE assumption.

We will present here new multivariate encryption algorithms. This is interesting since few multivariate encryption scheme currently exist, while their exist many more multivariate signature schemes. Our algorithms will combine several ideas, in particular the idea of the LL’ perturbation originally introduced, but only for signature, in [GP06]. In this paper, the LL’ perturbation will be used for encryption and will greatly differ from [GP06]. As we will see, our algorithms resists to all known attacks (in particular Gröbner attacks and MinRank attacks) and have reasonable computation time.

In this paper, we aim to enhance and automate advanced techniques for impossible differential attacks. To demonstrate these advancements, we present improved attacks on the LBlock and HIGHT block ciphers. More precisely, we (a) introduce a methodology to automatically invert symmetric ciphers when represented as directed acyclic graphs, a fundamental step in the search for impossible differential trails and in key recovery techniques; (b) automate the search for impossible differential distinguishers, reproducing recent techniques and results; (c) present a new hybrid model combining cell-wise properties and bit-wise granularity; (d) integrate these techniques in the automated tool CLAASP; (e) demonstrate the effectiveness of the tool by reproducing a state-of-the-art 16-round impossible differential for LBlock previously obtained using a different technique and exhibiting a new 18-round improbable trail; (f) improve the state-of-the-art single-key recovery of HIGHT for 27 rounds, by automating the use of hash tables to current state-of-the-art results.

In this short paper we consider a format preserving encryption when a nonce is available. The encryption itself mimics a stream cipher where the keystream is of a (non-binary) radix $R$. We give a few practical and efficient ways to generate such a keystream from a binary keystream generator.

In many lightweight cryptography applications, low area and latency are required for efficient implementation. The gate count in the cipher and the circuit depth must be low to minimize these two metrics. Many optimization strategies have been developed for the linear layer, led by the Boyer-Peralta (BP) algorithm. The Advanced Encryption Standard (AES) has been a focus of extensive research in this area. However, while the linear layer uses only XOR gates, the S-box, which is an essential nonlinear component in symmetric cryptography, uses various gate types, making optimization challenging, particularly as the bit size increases.

In this paper, we propose a new framework for a heuristic search to optimize the circuit depth or XOR gate count of S-box circuits. Existing S-box circuit optimization studies have divided the nonlinear and linear layers of the S-box, optimizing each separately, but limitations still exist in optimizing large S-box circuits. To extend the optimization target from individual internal components to the entire S-box circuit, we extract the XOR information of each node in the target circuit and reconstruct the nodes based on nonlinear gates. Next, we extend the BP algorithm-based heuristics to address nonlinear gates and incorporate this into the framework. It is noteworthy that the effects of our framework occur while maintaining the AND gate count and AND depth without any increase.

To demonstrate the effectiveness of the proposed framework, we apply it to the AES, SNOW3G, and Saturnin S-box circuits. Our results include depth improvements by about 40% and 11% compared to the existing AES S-box [BP10] and Saturnin super S-box [CDL+20] circuits, respectively. We implement a new circuit for the SNOW3G S-box, which has not previously been developed, and apply our framework to reduce its depth. We expect the proposed framework to contribute to the design and implementation of various symmetric-key cryptography solutions.

A long-standing question in the blockchain community is which class of computations are efficiently expressible in cryptocurrencies with limited scripting languages, such as Bitcoin Script. Such languages expose a reduced trusted computing base, thereby being less prone to hacks and vulnerabilities, but have long been believed to support only limited classes of payments.

In this work, we confute this long-standing belief by showing for the first time that arbitrary computations can be encoded in today's Bitcoin Script, without introducing any language modification or additional security assumptions, such as trusted hardware, trusted parties, or committees with secure majority. In particular, we present $\mathsf{BitVM}$, a two-party protocol realizing a generic virtual machine by a combination of cryptographic and incentive mechanisms. We conduct a formal analysis of $\mathsf{BitVM}$, characterizing its functionality, system assumptions, and security properties. We further demonstrate the practicality of our approach: in the optimistic case (i.e., in the absence of disputes between parties), our protocol requires just three on-chain transactions, whereas in the pessimistic case, the number of transactions grows logarithmically with the size of the virtual machine. This work not only solves a long-standing theoretical problem, but it also promises a strong practical impact, enabling the development of complex applications in Bitcoin.

In this paper we define the novel concept token-based key exchange (TBKE), which can be considered a cross between non-interactive key exchange (NIKE) and attribute-based encryption (ABE). TBKE is a scheme that allows users within an organization to generate shared keys for a subgroup of users through the use of personal tokens and secret key. The shared key generation is performed locally and no interaction between users or with a server is needed.

The personal tokens are derived from a set of universal tokens and a master secret key which are generated and stored on a trusted central server. Users are only required to interact with the server during setup or if new tokens are provided. To reduce key escrow issues the server can be erased after all users have received their secret keys. Alternatively, if the server is kept available TBKE can additionally provide token revocation, addition and update. We propose a very simple TBKE protocol using bilinear pairings. The protocol is secure against user coalitions based upon a novel hidden matrix problem. The problems requires an adversary to compute where the adversary must compute a matrix product in the exponent, where some components are given in the clear and others are hidden as unknown exponents. We argue that the hidden matrix problem is as hard as dLog in the bilinear group model.

In this paper, we present a batching technique for oracles corresponding to codewords of a Reed–Solomon code. This protocol is inspired by the round function of the STIR protocol (CRYPTO 2024). Using this oracle batching protocol, we propose a construction of a practically efficient accumulation scheme, which we call BOIL. Our accumulation scheme can be initiated with an arbitrary correlated holographic IOP, leading to a new class of PCD constructions. The results of this paper were originally given as a presentation at zkSummit12.

This paper studies quantum linear key-recovery attacks on block ciphers. The first such attacks were last-rounds attacks proposed by Kaplan et al. (ToSC 2016), which combine a linear distinguisher with a guess of a partial key. However, the most efficient classical attacks use the framework proposed by Collard et al. (ICISC 2007), which computes experimental correlations using the Fast Walsh-Hadamard Transform. Recently, Schrottenloher (CRYPTO 2023) proposed a quantum version of this technique, in which one uses the available data to create a quantum \emph{correlation state}, which is a superposition of subkey candidates where the amplitudes are the corresponding correlations. A limitation is that the good subkey is not marked in this state, and cannot be found easily.

In this paper, we combine the correlation state with another distinguisher. From here, we can use Amplitude Amplification to recover the right key. We apply this idea to Feistel ciphers and exemplify different attack strategies on LOKI91 before applying our idea on the CAST-128 and CAST-256 ciphers. We demonstrate the approach with two kinds of distinguishers, quantum distinguishers based on Simon's algorithm and linear distinguishers. The resulting attacks outperform the previous Grover-meet-Simon attacks.

This work proposes a multi-level compiler framework to transform programs with loop structures to efficient algorithms over fully homomorphic encryption (FHE). We observe that, when loops operate over ciphertexts, it becomes extremely challenging to effectively interpret the control structures within the loop and construct operator cost models for the main body of the loop. Consequently, most existing compiler frameworks have inadequate support for programs involving non-trivial loops, undermining the expressiveness of programming over FHE. To achieve both efficient and general program execution over FHE, we propose CHLOE, a new compiler framework with multi-level control-flow analysis for the effective optimization of compound repetition control structures. We observe that loops over FHE can be classified into two categories depending on whether the loop condition is encrypted, namely, the transparent loops and the oblivious loops. For transparent loops, we can directly inspect the control structures and build operator cost models to apply FHE-specific loop segmentation and vectorization in a fine-grained manner. Meanwhile, for oblivious loops, we derive closed-form expressions and static analysis techniques to reduce the number of potential loop paths and conditional branches. In the experiment, we show that \NAME can compile programs with complex loop structures into efficient executable codes over FHE, where the performance improvement ranges from $1.5\times$ to $54\times$ (up to $10^{5}\times$ for programs containing oblivious loops) when compared to programs produced by the-state-of-the-art FHE compilers.

We propose a solution for optimized scaling of multi-party computation using the MP-SPDZ framework (CCS’20). It does not use manual optimization but extends the compiler and the virtual machine of the framework, thus providing an improvement for any user. We found that our solution improves timings four-fold for a simple example in MP-SPDZ, and it improves an order of magnitude on every framework using secret sharing considered by Hastings et al. (S&P’19) either in terms of time or RAM usage. The core of our approach is finding a balance between communication round optimization and memory usage.

Oblivious pseudorandom function (OPRF) is a two-party cryptographic protocol that allows the receiver to input $x$ and learn $F(x)$ for some PRF $F$, only known to the sender. For private set intersection (PSI) applications, OPRF protocols have evolved to enhance efficiency, primarily using symmetric key cryptography. Current state-of-the-art protocols, such as those by Rindal and Schoppmann (Eurocrypt '21), leverage vector oblivious linear evaluation (VOLE) and oblivious key-value store (OKVS) constructions.

In this work, we identify a flaw in an existing security proof, and present practical attacks in the malicious model, which results in additional PRF evaluations than the previous works' claim. In particular, the attack for malicious model is related to the concept of OKVS overfitting, whose hardness is conjectured in previous works. Our attack is the first one to discuss the concrete hardness of OKVS overfitting problem.

As another flavour of contribution, we generalize OKVS-based OPRF constructions, suggesting new instantiations using a VOLE protocol with only Minicrypt assumptions. Our generalized construction shows improved performance in high-speed network environments, narrowing the efficiency gap between the OPRF constructions over Cryptomania and Minicrypt.

We present a garbling scheme for Boolean circuits with 1 bit per gate communication based on either ring learning with errors (RLWE) or NTRU assumption, with key-dependent message security. The garbling consists of 1) a homomorphically encrypted seed that can be expanded to encryption of many pseudo-random bits and 2) one-bit stitching information per gate to reconstruct garbled tables from the expanded ciphertexts. By using low-complexity PRGs, both the garbling and evaluation of each gate require only O(1) homomorphic addition/multiplication operations without bootstrapping.

In this study, we present the first side-channel attack on the ARADI block cipher, exposing its vulnerabilities to physical attacks in non-profiled scenarios. We propose a novel bitwise divide-and-conquer methodology tailored for ARADI, enabling key recovery. Furthermore, based on our attack approach, we present a stepwise method for recovering the full 256-bit master key. Through experiments on power consumption traces from an ARM processor, we demonstrate successful recovery of target key bits, validating the effectiveness of our proposed method. Our findings highlight critical weaknesses in physical security of ARADI and underscore the necessity of implementing effective countermeasures to address side-channel vulnerabilities.

As advancements in quantum computing present potential threats to current cryptographic systems, it is necessary to reconsider and adapt existing cryptographic frameworks. Among these, Grover's algorithm reduces the attack complexity of symmetric-key encryption, making it crucial to evaluate the security strength of traditional symmetric-key systems. In this paper, we implement an efficient quantum circuit for the ARIA symmetric-key encryption and estimate the required quantum resources. Our approach achieves a reduction of over 61\% in full depth and over 65.5\% in qubit usage compared to the most optimized previous research. Additionally, we estimate the cost of a Grover attack on ARIA and evaluate its post-quantum security strength.

This article generalizes the widely-used GLV decomposition for scalar multiplication to a broader range of elliptic curves with moderate CM discriminant \( D < 0 \) (up to a few thousand in absolute value). Previously, it was commonly believed that this technique could only be applied efficiently for small \( D \) values (e.g., up to \( 100 \)). In practice, curves with \( j \)-invariant \( 0 \) are most frequently employed, as they have the smallest possible \( D = -3 \). This article participates in the decade-long development of numerous real-world curves with moderate \( D \) in the context of ZK-SNARKs. Such curves are typically derived from others, which limits the ability to generate them while controlling the magnitude of \( D \). The most notable example is so-called "lollipop" curves demanded, among others, in the Mina protocol.

Additionally, the new results are relevant to one of the "classical" curves (with \( D = -619 \)) from the Russian ECC standard. This curve was likely found using the CM method (with overwhelming probability), though this is not explicitly stated in the standard. Its developers seemingly sought to avoid curves with small \( D \) values, aiming to mitigate potential DLP attacks on such curves, and hoped these attacks would not extend effectively to \( D = -619 \). One goal of the present article is to address the perceived disparity between the \( D = -3 \) curves and the Russian curve. Specifically, the Russian curve should either be excluded from the standard for potential security reasons or local software should begin leveraging the advantages of the GLV decomposition.

This work investigates constructions of threshold fully homomorphic encryption with low communication, i.e., with small ciphertexts and small decryption shares. In this context, we discuss in detail the technicalities for achieving full-fledged threshold FHE, and put forward limitations regarding prior works, including an attack against the recent construction of Boudgoust and Scholl [ASIACRYPT 2023]. In light of our observations, we generalize the definition of threshold fully homomorphic encryption by adding an algorithm which allows to introduce additional randomness in ciphertexts before they are decrypted by parties. In this setting, we are able to propose a construction which offers small ciphertexts and small decryption shares.

As dataset sizes continue to grow, users face increasing difficulties in performing processing tasks on their local machines. From this, privacy concerns about data leakage have led data owners to upload encrypted data and utilize secure range queries to cloud servers. To address these challenges, order-revealing encryption (ORE) has emerged as a promising solution for large numerical datasets. Building on this, delegatable order-revealing encryption (DORE) was introduced, allowing operations between encrypted datasets with different secret keys in multi-client ORE environments. DORE operates through authorization tokens issued by the data owner. However, security concerns had arisen about unauthorized users exploiting data without permission, leading to the development of a secure order-revealing encryption scheme (SEDORE). These attacks can result in unauthorized data access and significant financial losses in modern cloud service providers (CSPs) utilizing pay-per-query systems. In addition, efficient delegatable order-revealing encryption (EDORE), which improves speed and storage compared to SEDORE with identical security levels, was also introduced. Although both SEDORE and EDORE were designed to be robust against these attacks, we have identified that they still retain the same vulnerabilities within the same threat model. To address these issues, we propose Verifiable Delegatable Order-Revealing Encryption (VDORE), which protects against attacks by using the Schnorr Signature Scheme to verify the validity of the token that users send. We propose a precise definition and robust proof to improve the unclear definition and insufficient proof regarding token unforgeability in the SEDORE. Furthermore, the token generation algorithm in VDORE provides about a $1.5\times$ speed-up compared to SEDORE.

Quantum computing has attracted substantial attention from researchers across various fields. In case of the symmetric key cryptography, the main problem is posed by the application of Grover's search. In this work, we focus on quantum analysis of the lightweight block cipher LED.

This paper proposes an optimized quantum circuit for LED, minimizing the required number of qubits, quantum gates, and circuit depth. Furthermore, we conduct Grover's attack and Search with Two Oracles (STO) attack on the proposed LED cipher, estimating the quantum resources required for the corresponding attack oracles. The STO attack outperforms the usual Grover's search when the state size is less than the key size. Beyond analyzing the cipher itself (i.e., the ECB mode), this work also evaluates the effectiveness of quantum attacks on LED across different modes of operation.

With the emergence of DeFi, attacks based on re-ordering transactions have become an essential problem for public blockchains. Such attacks include front-running or sandwiching transactions, where the adversary places transactions at a particular place within a block to influence a financial asset’s market price. In the Ethereum space, the value extracted by such attacks is often referred to as miner/maximal extractable value (MEV), which to date is estimated to have reached a value of more than USD 1.3B. A promising approach to protect against MEV is to hide the transaction data so block proposers cannot choose the order in which transactions are executed based on the transactions’ content. This paper describes the cryptographic protocol underlying the Shutter network. Shutter has been available as an open-source project since the end of 2021 and has been running in production since Oct. 2022.