ABSTRACT. Plaintext structures are a commonly-used technique for improving differential cryptanalysis. Generally, there are two types of plaintext structures, multiple-differential structures and truncated-differential structures. Both types have been widely used in cryptanalysis of S-box-based ciphers while for SPECK, an Addition-Rotation-XOR (ARX) cipher, the truncated-differential structure has not been used so far. In this paper, we investigate the properties of modular addition and propose a method to construct truncated-differential structures for SPECK. Moreover, we show that a combination of both types of structures is also possible for SPECK. For recovering the key of SPECK, we propose dedicated algorithms and apply them to various differential distinguishers, which helps to obtain a series of improved attacks on all variants of SPECK. The results show that the combination of both structures helps to improve the data and time complexity at the same time, as in the cryptanalysis of S-box-based ciphers.

ABSTRACT. The emergence of advanced cryptographic protocols has promoted the developments of many applications, such as secure multi-party computation (MPC). For this reason, new symmetric-key primitives have been designed to natively support the finite field $\mathbb{F}_p$ with odd characteristic for better efficiencies. However, some well-studied symmetric cryptanalytic methods and techniques over $\mathbb{F}_2^n$ cannot be applied to these new primitives over $\mathbb{F}_p$ directly. Considering less standard design approaches adopted in these novel MPC-friendly ciphers, these proposals are in urgent need of full investigations, generalizations of the traditional cryptanalytic tools and techniques to $\mathbb{F}_p$ will also contribute to better understand the security of these new designs.

In this paper, we first show that the Fast Fourier Transform (FFT) technique for the estimations of correlation, introduced by Collard \etal at ICISC 2007, can be applied to $\mathbb{F}_p$ and significantly improves the complexity of Matsui's \textit{Algorithm 2} over $\mathbb{F}_p$. Then, we formalize the differential-linear (DL) cryptanalysis to $\mathbb{F}_p$. Inspired by the differential-linear connectivity table (DLCT) introduced by Bar-On \etal at EUROCRYPT 2019, we also include the DLCT into the consideration, and find the relation between DLCT and differential distribution table (DDT) over $\mathbb{F}_p$. Finally, we mount key recovery attacks on a version of HADESMiMC, which is a SHARK-like MPC-friendly block cipher proposed by Grassi \etal at EUROCRYPT 2020. We denote this version as HADESMiMC-128 in this paper. For linear cryptanalysis with the FFT technique, we can attack 7 rounds of HADESMiMC-128. For DL cryptanalysis, a 7-round key recovery attack of HADESMiMC-128 is also mounted but with better time and data complexity. It should be noted that the attacks are still far from threatening the security of the full 14-round HADESMiMC-128.

ABSTRACT. Introduced in 2017, Middle-Product Learning with Error (MPLWE) and its variants offer a way to construct cryptographic primitives which preserve the efficiency of those based on Polynomial-LWE (PLWE) and are at least as secure as them over a broad choice of number fields. Based on MPLWE, a series of cryptographic schemes have been proposed, including public key encryption (PKE), digital signatures, and identity-based encryption (IBE). In this paper, we extend this line of research and propose a new IBE scheme that is adaptively secure in the standard model from MPLWE. Existing IBE schemes from MPLWE only offer selective security or rely on the random oracle model. We follow the blueprint of Agrawal et al. at EUROCRYPT2010 and adapt the well-known partitioning technique to the MPLWE setting. The resulting scheme offers similar efficiency to schemes based on PLWE under a milder assumption.

ABSTRACT. Practical implementations of advanced lattice-based constructions have received much attention since the first practical scheme instantiated over NTRU lattices, proposed by Prest et al (Asiacrypt 2014). They are using powerful lattice-based building blocks which allow to build Gaussian preimage sampling and trapdoor generation efficiently. In this paper, we propose two different constructions and implementations of identity-based encryption schemes (IBE) using approximate variants of "gadget-based" trapdoors introduced by Chen et al. (Asiacrypt 2019). Both constructions are proven secure. Our first IBE scheme is an adaptation of the Bert et al. scheme (PQCrypto 2021) to the approximate setting, relying on the Module-LWE hardness assumption and making use of the Micciancio-Peikert paradigm with approximate trapdoors. The second IBE relies on a variant of the NTRU hardness assumption. We provide several timings and a comparison analysis to explain our results. The two different instantiations give interesting trade-offs in terms of security and efficiency and both benefit from the use of approximate trapdoors. Though our second IBE construction is less efficient than others NTRU-based IBEs, we believe our work provides useful insights into efficient advanced lattice-based constructions

ABSTRACT. We present a quantumly secure identity-based signature scheme based on the standard short integer solution problem, featuring tight security reductions in the quantum random oracle model and the classic random oracle model. The scheme has short signatures. Each signature contains a single lattice vector plus a single bit. Compared to the existing tightly secure, short lattice identity-based signature schemes by Pan and Wagner (PQCrypto'21), our scheme has a shorter signature size, stronger unforgeability, relies on a weaker assumption, and has a detailed proof in the quantum random oracle model.

ABSTRACT. Identity-based signatures (IBS) can be verified using the signer identity information as the public key, and hence, there is no need for the certificate management that proves the corresponding public key ownership. Unfortunately, none of the existing IBS schemes has security proven as tight as the discrete logarithm (DL) problem, the hardest problem in the cyclic group setting, under the standard EUF-CMA security model. Recently, the introduction of proving security in the algebraic group model (AGM), where the adversary's computation is algebraic, enables some ordinary signature schemes to be proven tightly reducible under DL assumption and EUF-CMA. To date, however, it remains unknown whether IBS schemes can also be proven as secure as the DL problem in the AGM. Achieving tight security in IBS schemes under standard EUF-CMA is challenging, due to the need to take extra precautions against adaptive queries on user private keys by the adversary. In this work, we show, for the first time, an IBS scheme with tight security under DL assumption and EUF-CMA in the AGM. The scheme features a minimal signature size of two group elements, with a reduction loss factor of two.

ABSTRACT. The most crucial step in the cryptanalysis of symmetric ciphers is finding a distinguisher, usually a property that can distinguish the targeted cipher from random permutations. How to get longer distinguishers of various cryptanalysis methods of symmetric ciphers is widely studied in the classical setting. However, there are few works concerning this problem in the quantum setting. With the rapid development of quantum techniques, more and more people believe that quantum computers would come true in the future. Then it is also essential to investigate how to get distinguishers by using quantum computing.

In the present paper, we present quantum algorithms for finding impossible differentials and zero-correlation linear hulls, which are distinguishers for the two powerful attacks against symmetric ciphers of impossible differential attack and zero-correlation linear attack. Compared with classical methods, the proposed quantum algorithms possess many advantages. Firstly, our quantum algorithm for finding impossible differentials obtains the input and output differences by solving linear equations systems instead of searching in a limited space; Secondly, our quantum algorithm for zero-correlation linear hulls can investigate the key schedule's effect; Thirdly, the only computation cost of our algorithms is solving linear equations systems, and the size of the systems is not increasing as the round number increases.

The core idea is using Berstein-Vazirani algorithm to find 1-linear structures of Boolean functions. We check the proposed quantum algorithm's validity with the SIMON block cipher family and RC5 block cipher. We show that the proposed algorithms can discover some 11-round, 12-round, 13-round, 16-round, 19-round impossible differentials and zero-correlation linear hulls of SIMON block cipher family when considering the key schedules and 2.5-round impossible differential of RC5 when considering the round subkeys.

ABSTRACT. Code-based cryptography is a candidate for post-quantum cryptography and the security of code-based cryptosystems relate to the hardness of the syndrome decoding problem. The Information Set Decoding (ISD) algorithm initiated by Prange is a typical method for solving the syndrome decoding problem. Various methods have been proposed that make use of exponentially large lists to accelerate the ISD algorithm. Furthermore, Bernstein (PQCrypto 2010) and Kachigar and Tillich (PQCrypto 2017) applied Grover's algorithm and quantum walks to obtain ¥emph{quantum} ISD algorithms that are much faster than their classical ones. These quantum ISD algorithms also require exponentially large lists as the classical algorithms, and they must be kept in quantum states. In this paper, we propose a new quantum ISD algorithm by combining Both and May's classical ISD algorithm (PQcrypto 2018), Grover's algorithm, and Kirshanova's quantum walk (PQCrypto 2018). The proposed algorithm keeps an exponentially large list in the quantum state just like the existing quantum ISD algorithms, but the list size is much smaller. Although the proposed algorithm is slower than the existing algorithms when there is sufficient quantum memory, it is fastest when the amount of quantum memory is limited. Due to the property, we believe that our algorithm will be the fastest ISD algorithm in actual quantum computing since large-scale quantum computers seem hard to realize.

ABSTRACT. In this paper, we propose a new family of highly efficient and quantum-secure AES-based block cipher dubbed Ghidle, which supports a key of size 256 bits and a state size of 256 or 512 bits. The large state size implies a “bigger birthday bound” security when these are embedded in modes of operations. Ghidle achieves high efficiency in both the encryption and the decryption by taking advantage of three consecutive executions of AES rounds in AES-NI, while Pholkos, which is an existing quantum-secure block cipher is designed to be fast for only encryption performance due to the limitation of two consecutive executions of AES rounds. We run benchmarks of Ghidle on x86( 64) and arm64 environments and compare their performance with Pholkos. In our performance evaluation on modern x86 processors, the decryption of Ghidle-512 outperforms that of Pholkos-512 by about 54% while the encryption performance remains the same. We also evaluate the performance on mobile devices with arm64-based processors and the result shows that Ghidle-256 outperforms Pholkos-256 by about 32% for decryption while the encryption remains almost the same. Furthermore, Ghidle-512 outperforms Pholkos-512 by about 21% and 53% for both encryption and decryption, respectively.

ABSTRACT. In post-quantum cryptography, hash-based signature schemes are attractive choices because of the weak assumptions. Most existing hash-based signature schemes are proven secure against post-quantum chosen message attacks (CMAs), where the adversaries are able to execute quantum computations and classically query to the signing oracle. In some cases, the signing oracle is also considered quantum-accessible, meaning that the adversaries are able to send queries with superpositions to the signing oracle. Considering this, Boneh and Zhandry propose a stronger security notion called existential unforgeability under quantum chosen message attacks (EUF-qCMA). We call it quantum-access security (or Q2 security in some literature). The quantum-access security of practical signature schemes is lacking in research, especially of the hash-based ones. In this paper, we analyze the quantum-access security of hash-based signature schemes in two directions. First, we show concrete quantum chosen message attacks (or superposition attacks) on existing hash-based signature schemes, such as SPHINCS and SPHINCS+. The complexity of the attacks is obviously lower than that of optimal classical chosen message attacks, implying that quantum chosen message attacks are more threatening than classical ones to these schemes. Second, we propose a simple variant of SPHINCS+ and give security proof against quantum chosen message attacks. As far as we know, it is the first practical stateless hash-based signature scheme against quantum chosen message attacks with provable security.