Impossible differential cryptanalysis and impossible polytopic cryptanalysis are among the most effective techniques for evaluating the security of block ciphers. However, previous automatic search methods for their distinguishers—dimpossible differentials and impossible polytopic transitions—neither account for the influence of the key schedule in single-key settings nor are applicable to block ciphers featuring large S-boxes, variable rotations, or key-dependent permutations. Furthermore, existing approaches fail to search for clusters of impossible differentials when all details of a block cipher are considered. In contrast to previous methods that focus solely on the propagation of differences or s-difference, we redefine impossible differentials and impossible (s+ 1)-polytopic transitions based on state propagation. This redefinition enables us to overcome the limitations inherent in earlier methodologies. Theoretically, we demonstrate that traditional definitions of impossible differentials and impossible (s+ 1)-polytopic transitions correspond to subsets of our redefined concepts, which offer broader analytical perspectives. Technically, we reformulate the automatic search model and develop an SAT-based tool to efficiently evaluate our redefined impossible differentials and impossible (s+ 1)-polytopic transitions. Building upon this foundational search method, we construct a comprehensive framework for detecting clusters of impossible differentials and impossible (s+1)-polytopic transitions. This framework not only fully incorporates the details and differential properties of block ciphers but is also applicable to those employing large S-boxes while considering the full linear layer. As a result, we derive new impossible differentials for GIFT64, PRINTcipher48/96, MISTY1, RC5-32/64/128 and SPECK, as well as new clusters of impossible differentials for SPECK, DES and ARIA. In assessing resistance against impossible differentials, we apply our method to evaluate the security of GIFT64, PRINTcipher48/96, MISTY1, SPECK, SIMON, and DES while accounting for all details of the block ciphers. Moreover, we propose acceleration strategies and apply them to evaluate the security of MISTY1 and AES-128. Notably, we prove that no 5-round impossible differentials with one active input byte and one active output byte exist for AES-128, even when considering the dependencies among three consecutive round keys. Finally, in exploring new impossible (s+1)-polytopic transition, we apply our approach to PRINTcipher48, GIFT64, RC5-32/64 and SIMON32-64, successfully yielding the corresponding distinguishers for the first time.

The impossible boomerang attack is a powerful cryptanalytic technique, but existing key recovery methods face several limitations that restrict its applicability. Specifically, the key pre-guessing is coarse-grained, S-box details are ignored in the differential propagation, the complexity estimation and the key guessing order determination remain rudimentary. To overcome these issues, we introduce three key improvement measures. First, we propose a flexible partial key and difference pre-guessing technique based on directed graphs, enabling selective identification of required keys and differences for generating partial pairs and quartets. Second, we propose a pre-sieving technique to early eliminate invalid quartets by exploiting cipher-specific details. Third, we introduce an automatic key-guessing strategy based on the same directed graphs to efficiently determine valid guessing orders. We integrate these techniques to develop a unified key recovery framework for impossible boomerang attacks, accompanied by a formal and precise characterization of the overall complexity. This is the first framework to support flexible key and difference pre-guessing while incorporating block cipher details during key recovery for impossible boomerang attacks. Crucially, it enables the automatic generation of detailed recovery steps, a capability missing in prior work. As applications, under the four related-key/tweakey setting, we apply the framework to ARADI, a low-latency cipher proposed by the National Security Agency (NSA), and SKINNYe v2, a threshold-implementation-friendly cipher proposed at EUROCRYPT 2020. For ARADI, we achieve the first full-round attack with 2130data, 2253.78time, and 2235.75memory complexity. For SKINNYe v2, we present the first 34-round impossible boomerang attack with 266data, 2253.75time, and 2239.75memory complexity. These results demonstrate the framework’s significance and its substantial improvement in advancing the impossible boomerang attack.

Fuzzy Private Set Intersection (FPSI) is a cryptographic protocol that extends traditional PSI to enable privacy-preserving similarity matching, allowing the receiver to learn elements from the sender’s set with "δ − close" of the receiver’s elements, computing {yj| dist(xi, yj) ≤ δ, xi∈ X, yj∈ Y } where δ is predefined threshold. However, the current state-of-the-art integer-based approach by Chakraborti et al. (USENIX’23) suffers from excessive computation overhead, large communication costs, and limited scalability, hindering practical deployment.We construct two semi-honest $\Pi _{{\text{FPSI}}}^{{\text{int}}}$ for different scenarios. Along with compact Prefix Trie preprocessing, for the balanced settings, we propose $\Pi _{{\text{FPSI}}}^{{\text{OKVS}}}$ leveraging OKVS and subVOLE. For unbalanced scenarios, we introduce $\Pi _{{\text{FPSI}}}^{{\text{HE}}}$ protocol combining optimization techniques including Paterson-Stockmeyer algorithms and multiple algorithmic improvements.We implement our protocols in C++ using 32-bit IPv4 and 128-bit IPv6 addresses across balanced and unbalanced scenarios under single-threaded LAN environment. our balanced $\Pi _{{\text{FPSI}}}^{{\text{OKVS}}}$ protocol achieves 24.7-58.4× computational speedup across all scales and 9.9× communication reduction compared to Chakraborti et al. (USENIX'23) for datasets up to 1 million addresses. For unbalanced scenarios, our $\Pi _{{\text{FPSI}}}^{{\text{HE}}}$ protocol demonstrates superior scalability, enabling mobile devices with only 4K datasets against 16 million server elements in 56.74 seconds with 22.8 MB communication, achieving 2.8-38.5× speedup over the (USENIX'23).

Abstract In this paper, we consider a secure multi-party shuffling (MPS), in which multiple participants provide private datasets and enable to obtain secret shared values of randomly permuted whole dataset while protecting the privacy of each individual input and the permutation. MPS stands as a foundational tool for the randomized algorithm, with broad utility in a large amount of domains, offering enhancements in privacy while concurrently reducing costs. And its applications encompass machine learning, secure function evaluation, and anonymous communication. Recently, Chase, Ghosh, and Poburinnaya (2020 Secret-shared shuffle. Advances in Cryptology-ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part III 26, pp. 342-372. Springer.) introduced an innovative two-party protocol known as SSS, where participants can effectively produce additive secret shares of a shuffled dataset while preserving the privacy. Indeed, this approach transforms challenge of shuffling a dataset into the task of shuffling pseudorandom values, leading to a significant enhancement in both communication and computation efficiency. We would like to generalize the SSS in Chase, Ghosh, and Poburinnaya (2020 Secret-shared shuffle. Advances in Cryptology-ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part III 26, pp. 342-372. Springer.) to a novel multi-party variant, all while maintaining its efficiency. However, it turns out that this is not straightforward. Specifically, the communication complexity is trivially blown up about $O(m^{3}n\log n)$, where $m$ denotes the number of participants and $n$ denotes the length of message. We further reduce the cost to be linear in the number of participants. Moreover, our novel MPS operates within the preprocessing model, with the security against static semi-honest adversaries. Furthermore, our protocols rely exclusively on the oblivious transfer during the preprocessing phase and symmetric-key primitives in online phase to avoid the comparatively heavy public-key operations associated with previous MPS protocols.

Permutations with low multiplication depth over prime fields are highly valuable in the design of symmetric ciphers that are compatible with fully homomorphic encryption (FHE). Quadratic permutations, which have the lowest depth, have been widely used in prior designs. In this paper, we propose a construction method that can give new quadratic permutations over Fpm, and cryptographic properties such as differential uniformity and Walsh spectrum of these permutations are also characterized. We give sufficient conditions for permutations over Fpnto attain a differential uniformity ofpn−1forn≥ 3. Furthermore, it is proven that for these permutations, the maximal 2-norm of Walsh coefficients remains bounded bypn−1, provided either the lastn− 1 entries of the input mask or the lastn− 1 entries of the output mask form a nonzero vector. As an application, we design a new FHE-friendly stream cipher named YuS based on a new quadratic permutation over Fp3and a fixed linear mapping. According to our implementation, achieves YuS faster evaluation times and higher throughput compared to Masta, Pasta, Pastav2and HERA in almost all instances for both BGV and BFV schemes at 80-bit and 128-bit security levels.

As the practical applications of fully homomorphic encryption (FHE), secure multi‐party computation (MPC) and zero‐knowledge (ZK) proof continue to increase, so does the need to design and analyze new symmetric‐key primitives that can adapt to these privacy‐preserving protocols. These designs typically have low multiplicative complexity and depth with the parameter domain adapted to their application protocols, aiming to minimize the cost associated with the number of nonlinear operations or the multiplicative depth of their representation as circuits. In this paper, we propose two differential fault attacks against a one‐way function RAIN used for Rainier (CCS 2022), a signature scheme based on the MPC‐in‐the‐head approach and an FHE‐friendly cipher HERA used for the RtF framework (Eurocrypt 2022), respectively. We show that our attacks can recover the keys for both ciphers by only injecting a fault into the internal state and requiring only one normal and one faulty ciphertext blocks. Thus, we can use only the practical complexity of 2 26.6 /2 28.8 /2 30.4 bit operations to break the full‐round RAIN with 128/192/256‐bit keys. For full‐round HERA with 80/128‐bit key, our attack is practical with complexity the complexity of 2 20 encryptions with about 2 16 memory.

With the growing practical applications of fully homomorphic encryption (FHE), secure multi-party computation (MPC), and zero-knowledge proofs (ZK), there has been an increasing need to design and analyze symmetric primitives that have low multiplication complexity and depth. In this paper, we propose a permutation constructed upon a 4-round nonlinear feedback resistor over$ \mathbb {F}_{q}^{4}$. Our proposed permutation has a multiplication depth of 2 and a multiplication complexity of 4. Significantly, its maximum differential/linear probability is bounded by$q^{-2}$. Based on this nonlinear function, we propose a new family of block ciphers over$ \mathbb {F}_{q}^{16}$called$ \mathsf {YuX}$, whose decryption circuit is highly efficient for FHE evaluation. We further provide specific instantiations, denoted as$ \mathsf {Yu_{2}X}$and$ \mathsf {Yu_{\mathrm {p}}X}$, wherein$q$takes the form of either$2^{n}$or a prime$p$, respectively. Furthermore, we conduct a comprehensive security analysis of$ \mathsf {YuX}$within certain parameters against various cryptanalysis methods employing automatic analysis tools, including the differential attack, linear attack, impossible differential attack, zero-correlation attack, and integral attack, as well as Gröbner basis and linearization attacks. Our research indicates that$ \mathsf {YuX}$maintains a robust security margin against those attacks. Finally, we present a detailed implementation of$ \mathsf {Yu_{2}X}$and$ \mathsf {Yu_{\mathrm {p}}X}$employing the BGV homomorphic encryption scheme. In comparison to ciphers over a field of characteristic 2, the outcomes evince that$ \mathsf {Yu_{2}X}$-8 (over$ \mathbb {F}_{2^{8}}^{16}$) and$ \mathsf {Yu_{2}X}$-16 (over$ \mathbb {F}_{2^{16}}^{16}$) achieve remarkably competitive throughputs, boasting performance approximately 12 times, 17 times, and 9 times superior to AES-128, CHAGHRI, and LowMC-128 (under 128-bit security), respectively. Furthermore, when juxtaposed with ciphers over a field of characteristic$p$, the outcomes affirm that the throughput of$ \mathsf {Yu_{\mathrm {p}}X}$-65537 (over$ \mathbb {F}_{65537}^{16}$) retains considerable competitiveness, registering an approximate fivefold enhancement relative to HERA. Evidently,$ \mathsf {YuX}$exhibits superior throughput compared to a majority of symmetric ciphers within this category.

Abstract Lightweight block ciphers are the essential encryption algorithm for devices with limited resources. Its goal is to ensure the security of data transmission through resource-constrained devices. Impossible differential cryptanalysis is one of the most effective cryptanalysis on block ciphers, and assessing the ability of resisting this attack is a basic design criterion. Shadow is a lightweight block cipher proposed by Guo et al. (IEEE Internet Things J 8(16):13014–13023, 2021). It utilizes a combination of ARX operations and generalized Feistel structure to overcome the weakness of the traditional Feistel structure that only diffuses half in one round. In this paper, we focus on the differential property of Shadow and its security against impossible differential cryptanalysis. First, we use the SAT method to automatically search for a full-round impossible differential distinguisher of Shadow-32. Then, based on the experimental results, we prove that Shadow has a differential property with probability 1 based on the propagation of the state. Further, we can obtain an impossible differential distinguisher for an arbitrary number of rounds of Shadow. Finally, we perform a full key recovery attack on the full-round Shadow-32 and Shadow-64. Both experimentally and theoretically, our results indicate that Shadow is critically flawed, and regardless of the security strength of the internal components and the number of rounds applied, the overall cipher remains vulnerable to impossible differential cryptanalysis.

Abstract The division property method is a technique for automatic searching integral distinguishers on block ciphers. Previous methods only use word-based division property to search integral distinguishers for block ciphers with large S-boxes. Since using bit-based division property may find longer integral distinguishers than word-based division property, we propose a method to automatically search the integral distinguishers based on bit-based division property for block ciphers with large S-boxes. To achieve this goal, we propose a new division property propagation table for S-boxes. Theoretically, we prove that using both the new table and the traditional method to describe the bit-based division property propagation rule of S-box will lead to the same integral distinguishers. Technically, we design a mixed-integer linear programming-based tool to search the integral distinguisher based on the new table, which helps to search new integral distinguishers for block ciphers with large S-boxes efficiently. As a result, we apply our tool to derive new integral distinguishers and get the tight bound on the rounds that no integral distinguishers exist for ICEBERG, KHAZAD, Camellia, CS-Cipher, ITUbee and SMS4. Besides, to show the availability of our integral distinguishers, we form the present best five-round and the first six-round integral attack for ICEBERG as an example.

Abstract AEGIS is one of the authenticated encryption with associated data designs selected for the final portfolio of the CAESAR competition. It combines the AES round function and simple Boolean operations to update its large state and extract a keystream to achieve an excellent software performance. The AEGIS family consists of AEGIS-128, AEGIS-256 and AEGIS-128L, which use 5, 6 and 8 parallel AES round functions to process 128, 128 and 256 bits message block per step with slightly different output functions separately. Surprisingly, very few cryptanalytic results on AEGIS have been published so far. This paper presents the first guess-and-determine attacks on AEGIS family. Firstly, we propose a new observation on the structure of AEGIS that the relations of fixed variables remain in the outputs at consecutive steps under some conditions on the AND operations, and the vectorial bitwise AND operation is biased, which is able to derive the additional variables added directly. Secondly, we add several techniques, such as divide and conquer on byte-based columns, reduction by meet in the middle and simplification through constraints on variables, for each AEGIS member. Finally, we conduct guess-and-determine attacks on AEGIS-128, AEGIS-256 and AEGIS-128L and result in a complexity of $2^{309}$, $2^{437}$ and $2^{384}$ to $2^{416}$, respectively. Although neither attack threatens the practical security of AEGIS, it has great significance to evaluate the resistance of such structure compared with their large internal state exploited of 640, 768 and 1024 bits. It is also the first internal state recovery attack on AEGIS without nonce reusing, while only distinguishing attacks on AEGIS exist up to now.

Abstract This paper investigates the security of counter mode encryption with authentication tag (COMET), one of the 32 second-round candidates in National Institute of Standards and Technology’s lightweight cryptography standardization process, against differential cryptanalysis. CHAM-64/128 is a block cipher chosen as one of the underlying block ciphers in COMET for hardware-oriented applications, and a differential characteristic with a high probability for CHAM-64/128 is useful for forgery attacks on COMET. However, we find that the optimal $\mathbf{39}$-round differential characteristic for CHAM-64/128 proposed by Roh et al., which is the longest differential characteristic of CHAM-64/128, is invalid. Then, we propose a new method of distinguishing an $\mathbf{m}$-bit block cipher from an $\mathbf{m}$-bit random permutation using a differential characteristic with a probability not higher than $\mathbf{2^{-m}}$. Using our method, we use two $\mathbf{39}$-round differential characteristics with a probability of $\mathbf{2^{-64}}$ for CHAM-64/128 to distinguish $\mathbf{39}$-round-reduced CHAM-64/128 from a $\mathbf{64}$-bit random permutation, respectively. Furthermore, we refine the probabilities of two differentials with the same input and output differential masks as the two $\mathbf{39}$-round differential characteristics, respectively. Finally, we present the first forgery attacks on COMET with the two differentials without using weak keys. Our forgery attacks follow the nonce-misuse scenario. It should be noticed that this attack does not invalidate the security claims of the designers.

Abstract SIMON is one of the lightweight block ciphers designed by the National Security Agency in 2013, and a technical report including security analysis was published by the design team nearly 4 years later. As for the linear attack, it is claimed that ‘the single‐path probabilities (and linear correlations) dip below 2 −block size for 12, 16, 20, 29, and 38 rounds for SIMON32, 48, 64, 96, and 128, respectively’. However, the design team does not show details on how to get the result and there are also no published papers verified the result yet. In the present paper, an upper bound of squared correlation of SIMON‐like functions is given. As an important application of this bound, how to find optimal linear characteristics of SIMON and SIMECK under the Markov assumption with Matsui's branch‐and‐bound algorithm is shown. The authors’ results confirm the claim of the design team. Furthermore, the best‐known linear‐hull distinguishers for SIMON and SIMECK is also given.

In this paper, we propose an automatic tool to search for optimal differential and linear trails in ARX ciphers. It’s shown that a modulo addition can be divided into sequential small modulo additions with carry bit, which turns an ARX cipher into an S-box-like cipher. From this insight, we introduce the concepts of carry-bit-dependent difference distribution table (CDDT) and carry-bit-dependent linear approximation table (CLAT). Based on them, we give efficient methods to trace all possible output differences and linear masks of a big modulo addition, with returning their differential probabilities and linear correlations simultaneously. Then an adapted Matsui’s algorithm is introduced, which can find the optimal differential and linear trails in ARX ciphers. Besides, the superiority of our tool’s potency is also confirmed by experimental results for round-reduced versions of HIGHT and SPECK. More specifically, we find the optimal differential trails for up to 10 rounds of HIGHT, reported for the first time. We also find the optimal differential trails for 10, 12, 16, 8 and 8 rounds of SPECK32/48/64/96/128, and report the provably optimal differential trails for SPECK48 and SPECK64 for the first time. The optimal linear trails for up to 9 rounds of HIGHT are reported for the first time, and the optimal linear trails for 22, 13, 15, 9 and 9 rounds of SPECK32/48/64/96/128 are also found respectively. These results evaluate the security of HIGHT and SPECK against differential and linear cryptanalysis. Also, our tool is useful to estimate the security in the design of ARX ciphers.

Abstract The 5G mobile communication system is coming with a main objective, known also as IMT-2020, that intends to increase the current data rates up to several gigabits per second. To meet an accompanying demand of the super high-speed encryption, EIA and EEA algorithms face some challenges. The 3GPP standardization organization expects to increase the security level to 256-bit key length, and the international cryptographic field responds actively in cipher designs and standard applications. SNOW-V is such a proposal offered by the SNOW family design team, with a revision of the SNOW 3G architecture in terms of linear feedback shift register (LFSR) and finite state machine (FSM), where the LFSR part is new and operates eight times the speed of the FSM, consisting of two shift registers and each feeding into the other, and the FSM increases to three 128-bit registers and employs two instances of full AES encryption round function for update. It takes a 128-bit IV, employs 896-bit internal state and produces 128-bit keystream blocks. The result is competitive in pure software environment, making use of both AES-NI and AVX acceleration instructions. Thus, the security evaluation of SNOW-V is essential and urgent, since there is scarcely any definite security bound for it. In this paper, we propose a byte-based guess-and-determine attack on SNOW-V with complexity $2^{406}$ using only seven keystream blocks. We first improve the heuristic guessing-path auto-searching algorithm based on dynamic programming by adding initial guessing set, which is iteratively modified by sieving out the unnecessary guessing variables, in order to correct the guessing path according to the cipher structure and finally launch smaller guessing basis. For the specific design, we split all the computing units into bytes and rewrite all the internal operations correspondingly. We establish a backward-clock linear equation system according to the circular construction of the LFSR part. Then we further simplify the equations to adapt to the input requirements of the heuristic guessing-path auto-searching algorithm. Finally, the derived guessing path needs modification for the pre-simplification and post-reduction. This is the first complete guess-and-determine attack on SNOW-V as well as the first specific security evaluation to the full cipher.

TRIVIUM is a stream cipher of the finalists by eSTREAM project and has been accepted as ISO standard. Although the design has a simple structure, no attack on its full cipher has been found yet. In this study, based on Maximov and Biryukov's attack, the authors present an improved guess‐and‐determine attack on TRIVIUM. Analysis details are provided corresponding to TRIVIUM specifications for better comprehension, and errors that may lead to higher attack complexity in the original attack are pointed and corrected. They further bring in some techniques like backward‐clock equation collection, quadratic equations, linear transformation to improve the attack. In addition, they integrate with time‐memory‐data tradeoffs from the framework, based on the analysis of the coefficient matrices form of derived linear equation systems on the internal state. In this way, better use of the imposed quadratic conditions can be made, which leads to reduced attack complexity by filtering out the impossible keystreams before solving the equation systems. Their attack offers more parameter selections, and gives several borderline results compared with the key exhaustive search. The new attack behaves better in the original case. It also verifies the necessity of data requirement imposed on TRIVIUM, which is questioned in TRIVIUM specifications.

Guess‐and‐determine attack is a cryptanalysis method that has been applied to various stream ciphers. In this study, the authors study the guess‐and‐determine attacks on two ISO standardised, P anama ‐like stream ciphers: MUGI and Enocoro. Utilising the word‐oriented structure of the two ciphers, they are able to launch heuristic guess‐and‐determine attacks in a more efficient manner. Their first target MUGI is both an ISO standard and a Japanese‐government‐selected CRYPTREC standard. By splitting its basic 64‐bit words into 16‐bit quarter‐words, they are able to conduct a guess‐and‐determine attack with complexity 2 388 , much lower than its 1216‐bit internal state size. Enocoro is a lightweight stream cipher family. It has two versions named according to key‐length as Enocoro‐80 and Enocoro‐128v2. They provide the specific guessing paths and they are able to launch guess‐and‐determine attacks on Enocoro‐80 and Enocoro‐128v2 with complexities 2 88 and 2 144 , respectively. In addition to specific attacking results, they also find some generic rules that may help to improve the efficiency of guess‐and‐determine attacks in the future.

Carlet and colleagues conjectured that for any almost bent (AB) functionF, there exists a linear functionLsuch thatF+Lis a permutation. Budaghyan and colleagues found a new class of AB functions which is extended affine (EA)-inequivalent to any power functions and can also serve as a counterexample for the conjecture. They checked with the help of a computer that there are no linear functionsLonF25such thatx2i+1+(x2i+x) Tr (x2i+1+x)+L(x) is a permutation. In this paper, we prove that there are no permutations EA-equivalent to the AB functionx2i+1+(x2i+x) Tr (x2i+1+x) onF22m+1for anym≥ 2 and there are no permutations EA-equivalent to the APN functionx2i+1+(x2i+x+1) Tr (x2i+1) on \BBF22mform≥ 2 either. Furthermore, we present some results about characterizations of permutation polynomials of the typeL(x2i+1)+L'(x) on \BBF22m, which is essential in the construction of functions Carlet-Charpin-Zinoviev-equivalent to the Gold functions. We obtain all the linear functionsL(x) such thatx+L(x2i+1) is a permutation on \BBF22mwhen |ker(L)| ≥ 22m-2.