ABSTRACT. CSI-FiSh is one of the most efficient isogeny-based signature schemes, which is proven to be secure in the Quantum Random Oracle Model (QROM). However, there is a bottleneck in CSI-FiSh in the threshold setting, which is that its public key needs to be generated by using $k-1$ secret keys. This leads to very inefficient threshold key generation protocols and also forces the parties to store $k-1$ secret shares. We present CSI-SharK, a new variant of CSI-FiSh that has more Sharing-friendly Keys and is as efficient as the original scheme. This is accomplished by modifying the public key of the ID protocol, used in the original CSI-FiSh, to the equal length Structured Public Key (SPK), generated by a single secret key, and then proving that the modified ID protocol and the resulting signature scheme remain secure in the QROM. We translate existing CSI-FiSh-based threshold signatures and Distributed Key Generation (DKG) protocols to the CSI-SharK setting. We find that DKG schemes based on CSI-SharK outperform the state-of-the-art actively secure DKG protocols from the literature by a factor of about $3$, while also strongly reducing the communication cost between the parties. We also uncover and discuss a flaw in the key generation of the actively secure CSI-FiSh based threshold signature Sashimi, that can prevent parties from signing. Finally, we discuss how (distributed) key generation and signature schemes in the isogeny setting are strongly parallelizable and we show that by using $C$ independent CPU threads, the total runtime of such schemes can basically be reduced by a factor $C$. As multiple threads are standard in modern CPU architecture, this parallelizability is a strong incentive towards using isogeny-based (distributed) key generation and signature schemes in practical scenarios.

ABSTRACT. A common structure in stream ciphers makes use of linear and nonlinear shift registers with a nonlinear output function drawing from both registers. We refer to these as Grain-like keystream generators. A recent development in lightweight ciphers is a modification of this structure to include a non-volatile key register, which allows key bits to be fed into the state update of the nonlinear register. Sprout and Plantlet are examples of this modified structure. The authors of these ciphers argue that including these key bits in the internal state update provides increased security, enabling the use of reduced register sizes below the commonly accepted rule of thumb that the state size should be at least twice the key size. In this paper, we analyse Plantlet and show that the security of this design depends entirely on the choice of the output function. Specifically, the contribution from the nonlinear register to the output function determines whether a key recovery attack is possible. We make a minor modification to Plantlet’s output function which allows the contents of the linear register to be recovered using an algebraic attack during keystream generation. This information then allows partial recovery of the contents of the nonlinear register, after which the key bits and the remaining register contents can be obtained using a guess and check approach, with a complexity significantly lower than exhaustive key search. Note that our attack is not successful on the existing version of Plantlet, though it only requires minor modifications to the filter function in order for the attack to succeed. However, our results clearly demonstrate that including the key in the state update during keystream generation does not increase the security of Plantlet. In fact, this feature was exploited to recover the key during keystream generation without the need to consider the initialisation process. This paper provides design guidelines for choosing both suitable output functions and the register stages used for inputs to these functions in order to resist the attacks we applied.

ABSTRACT. Authenticated Encryption (AE) achieves privacy and au- thenticity with a single scheme. It is possible to obtain an AE scheme gluing them together an encryption scheme (privacy secure) and a Mes- sage Authentication Code (authenticity secure). This approach is called a generic composition and its security has been studied by Namprempre et al. [NRS14]. They looked into all the possible gluings of an encryp- tion scheme with a secure MAC to obtain a nonce-based AE-scheme. The encryption scheme is either IV-based (that is, with an additional random input, the initialization vector [IV]) or nonce-based (with an input to be used once, the nonce). Nampremepre et al. assessed the se- curity/insecurity of all possible composition combinations except for 4 (N4, A10, A11 and A12). Berti et al. [BPP18a] showed that N4 is inse- cure and that the remaining modes (A10, A11, and A12) are either all secure or insecure. Here, we prove that these modes are all insecure with a counterexample.

ABSTRACT. A key encapsulation mechanism (KEM) is a basic building block for key exchange which must be combined with long-term keys in order to achieve authenticated key exchange (AKE). Although several KEM-based AKE protocols have been proposed, KEM-based modular building blocks are not available. We provide a KEM-based authenticator and a KEM-based protocol in the Authenticated Links model (AM), in the terminology of Canetti and Krawczyk (2001). Using these building blocks we achieve a set of generic AKE protocols. By instantiating with post quantum primitives we are able to propose several new post-quantum secure AKE protocols.

ABSTRACT. Correlation cube attacks were proposed by Liu et al. at EUROCRYPT 2018, which targeted a modern symmetric-key cryptosystem based on nonlinear feedback shift registers. The main idea of correlation cube attacks lies in recovering the secret key by exploiting conditional correlation properties between the superpoly of a cube and a specific set of low-degree polynomials called a basis. In this paper, we propose a new correlation cube attack based on the division property. The new attack expresses a given superpoly p as $fg\oplus h$ and calculates correlation probabilities for all possible f, where f only involves key variables. This novel idea breaks the restriction on the basis used in the original attack and provides more choices to find good correlation probabilities, thus making the correlation cube attack much more powerful. Besides, the first application of the division property to correlation cube attacks is given, which aided by MILP modeling techniques facilitates the search for desirable cubes. As illustrations, we apply the new correlation cube attack to Trivium. For 844-round Trivium, we can recover about 4-bit key information on average with the time complexity $2^{45}$, which could be fully verified by experiments. This is so far the best key recovery attack for 844-round Trivium.

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. 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. 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. At ASIACRYPT 2020, Alamati et al. formalized the framework of group actions for abstracting isogeny-based cryptosystems. At CRYPTO 2022, Abdalla et al. extended the framework to represent the quardratic twist of elliptic curves, and proposed the first provably secure and tightly-secure one-round isogeny-based password authenticated key exchange (PAKE) scheme (X-GA-PAKE) by a bit-by-bit approach. However, in X-GA-PAKE, for the password length $\ell$, the number of group actions per party is $5\ell$ and the communication complexity per party is $2\ell$, thus there is a problem in efficiency. In this paper, we propose an efficient one-round PAKE scheme that reduces the number of group actions and the communication complexity compared to X-GA-PAKE. In X-GA-PAKE, it is necessary to send/receive $2\ell$ elements to prevent trivial attacks using twists, but in our scheme, by reducing $\ell$ elements of them to the number of common reference string (CRS), we can reduce the number of group actions per party to $4\ell+2|CRS|$ and the communication complexity per party to $\ell+|CRS|$. In addition, we show the tight security in the one-round PAKE security model based on the same assumptions as in X-GA-PAKE.

ABSTRACT. In homomorphic signatures for subset predicates (HSSB), each message (to be signed) is a set. Any signature on a set M allows us to derive a signature on any subset M' of M. Its superset version, which should be called homomorphic signatures for superset predicates (HSSP), allows us to derive a signature on any superset M' of M. In this paper, we propose homomorphic signatures for subset and superset mixed predicates (HSSM) as a simple combination of HSSB and HSSP. In HSSM, any signature on a message of a set-pair (M, W) allows us to derive a signature on any (M', W') such that M' is a subset of M and W' is a superset of W. We propose an original HSSM scheme which is unforgeable under the decisional linear assumption and completely context-hiding. We show that HSSM has various applications, which include disclosure-controllable HSSB, disclosure-controllable redactable signatures, (key-delegatable) superset/subset predicate signatures, and wildcarded identity-based signatures.

ABSTRACT. Compiler provenance is significant in investigating the source-level indicators of binary code, like development-environment, source compiler, and optimization settings. Not only does compiler provenance analysis have important security applications in malware and vulnerability analysis, but it is also very challenging to extract useful artifacts from binary when high-level language constructs are missing. Previous works applied machine-learning techniques to predict the source compiler of binaries. However, most of the work is done on the binaries compiled on Linux operating system. We highlight the importance and need to explore Windows compilers and the complicated binaries compiled on the latest versions of these compilers. Therefore, we construct a large dataset of real-world binaries compiled with four major compilers on Windows and four most common optimization settings. The complexity of the optimized program leads us to identify specific patterns in the binaries that contribute to source compiler and specific optimization level. To address these observations, we propose an improved model based upon the state-of-the-art,~\oglassesX, and incorporate streamlined alignment padding features in the existing model. Thus, our improved model learns alignment instructions from binary code of portable executables and libraries using the attention mechanism. We conduct an extensive experimentation on a dataset of 296,169 unique and complex binary code generated from C/C++ applications. We show that our improved model surpasses state-of-the-art by a large margin in predicting source compiler and optimization flag of complex compiled code.

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. 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. 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. Despite offering numerous advantages, public decentralized cryptocurrencies such as Bitcoin suffer from scalability issues such as high transaction latency and low throughput. The vast array of so-called Layer-2 solutions tackling the scalability problem focus on throughput, and consider latency as a secondary objective. However, in the context of retail payments, instant finality of transactions is arguably a more pressing concern, besides the overarching concern for privacy.

In this paper, we provide an overlay network providing privacy-friendly low latency payments in a retail market privately. Our approach follows that of a recent work called Snappy, which achieved low latency but exposed identities of customers and their transaction histories. Our construction ensures this data is kept private, while providing merchants with protection against double-spending attacks. Although our system is still based upon customers registering with a collateral, crucially this collateral is reusable over time.

The technical novelty of our work comes from randomness-reusable threshold encryption (RRTE), a cryptographic primitive we designed specifically for the following features: %Although earlier attempts at double-spending protection worked by maintaining some form of ledger, RRTE lets us overcome this model restriction, by allowing a private database \emph{without} user identifiers to be used. our construction provable guarantees payments to merchants, preserves the secret identity of honest customers and prevents their transactions from being linked. We also present an implementation of our construction, showing the capacity for fast global payments in a retail setting with a delay of less than 1 second.

ABSTRACT. Quite a lot of block ciphers proposed in recent years are families of ciphers that conveniently support multiple block lengths and key lengths. The essential security requirements for a family of block ciphers are: (1) Each cipher instance from family is secure; (2) Cipher instances do not endanger each other's security, namely, by one or more cipher instances, other instances cannot be predicted. However, traditional cryptanalysis methods always assess the security of a special member of the family cipher, such as differential cryptanalysis, linear cryptanalysis, integral cryptanalysis. Related-cipher attacks focus on the security between cipher instances. This paper researches the security of Ballet-128 and ANT-128 against related-cipher attacks. Since their key schedules do not rely on the round number of encryption, we consider the related-cipher attack with equivalent keys by limiting the 256-bit key space. As a result, we recover the secret key of the full Ballet-128/128 with just one chosen plaintext pairs and one call of Ballet-128/128 and Ballet-128/256, which means Ballet-128 is insecure against related-cipher attack. For ANT-128, we show that there exist at most 6-round related-cipher distinguishers between ANT-128/128 and ANT-128/256, and launch a 9-round key-recovery attack on ANT-128/128 based on a 6-round related-cipher distinguisher with time complexity about $2^{60.9}$.

ABSTRACT. Cryptographic hash functions are used inside many applications that critically rely on their resistance against cryptanalysis attacks and the correctness of their implementations. Nevertheless, vulnerabilities in cryptographic hash function implementations can remain unnoticed for more than a decade, as shown by the recent discovery of a buffer overflow in the implementation of SHA-3 in the eXtended Keccak Code Package (XKCP), impacting Python, PHP, and several other software projects. In this paper, we explore the application of formal methods to the five finalist submission packages to the NIST SHA-3 competition, allowing us to rediscover vulnerabilities in the implementations of Keccak and BLAKE, and discover a new vulnerability in the implementation of Grøstl. We also show how the same approach rediscovers a vulnerability affecting 11 out of the 12 implemented cryptographic hash functions in Apple's CoreCrypto library. Our approach consists of removing certain lines of code and then using KLEE as a tool to prove functional equivalence. We discuss the advantages and limitations of our approach and hope that our attempt to consolidate some earlier approaches can lead to new insights.

ABSTRACT. Searchable Encryption (SE) allows users to perform a keyword search over encrypted documents. In Eurocrypt'04, Boneh et al. introduced Public-key Encryption with Keyword Search (PEKS). Broadcast Encryption with Keyword Search (BEKS) is a natural progression to allow some amount of access control. Unfortunately, PEKS and BEKS both suffer from the keyword guessing attack (KGA). In the case of KGA, an adversary guesses the keyword encoded in a trapdoor by creating a ciphertext on a sequence of keywords of its choice and testing them against the trapdoor. In ACISP'21, Liu et al. introduced a variant of BEKS called Broadcast Authenticated Encryption with Keyword Search (BAEKS), which tried to mitigate KGA in BEKS. This construction did not argue consistency and achieved weaker security in the random oracle model.

In this work, we first introduce the notion of consistency for BAEKS and introduce security models much stronger than those of Liu et al. We propose a new statistically-consistent construction of BAEKS in the standard model that achieves security in the newly introduced models. Our proposal is proven adaptively secure under the well-studied bilateral Matrix Diffie-Hellman Assumption and still achieves asymptotic efficiency similar to that of Liu et al.

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. Encryption protects internet users’ data security and privacy but makes network traffic classification a much harder problem. Network traffic classification is essential for identifying and predicting user behavior which is important for the overall task of network management. Deep learning methods used to tackle this problem have produced promising results. However, the conditions on which these experiments are carried out raise questions about their effectiveness when applied in the real world. We tackle this problem by modelling network traffic as graphs and applying deep learning for classification. We design a graph classifier based on higher order graph neural network with the aim of optimum generalization. To demonstrate the robustness of our model, we cross validate it on the ISCXVPN and USTC-TFC datasets with varying input specifications. We use our model to demonstrate the impact of network data truncation on traffic classification and define benchmarks for input specifications. Our best results outperform the state-of-the-art in terms of generalization strength.

ABSTRACT. SPEEDY is a family of ultra-lightweight block ciphers designed by Leander et al. at TCHES 2021. There are three recommended variants denoted as SPEEDY-r-192 with r ∈ {5, 6, 7}. All of them support the 192-bit block and the 192-bit key. The main focus during its design is to ensure hardware-aware low latency, thus, whether it is designed to have enough security is worth to be studied. Recently, the full-round security of SPEEDY-7-192 is announced to be broken by Boura et al. at EUROCRYPT 2023 under the chosen-ciphertext setting, where a round-reduced attack on SPEEDY-6-192 is also proposed. However, no valid attack on SPEEDY-5-192 is given due to its more restricted security parameters. Up to now, the best key recovery attack on this variant only covers 3 rounds proposed by Rohit et al. at AFRICACRYPT 2022. In this paper, we give three full-round attacks on SPEEDY-7-192. Using the divide-and-conquer strategy and other new proposed techniques, we found a 5.5-round differential distinguisher which can be used to mount the first chosen-plaintext full-round key recovery attack. With a similar strategy, we also found a 5-round linear distinguisher which leads to the first full-round attack under the known-plaintext setting. Meanwhile, the 5.5-round differential distinguisher also helps us slightly improve the full-round attack in the chosen-ciphertext setting compared with the previous result. Besides, we also present a 4-round differential attack on SPEEDY-5-192, which is the best attack on this variant in terms of the number of rounds so far. A faster key recovery attack covering the same rounds is also given using a differential-linear distinguisher. Both attacks cannot threaten its full-round security.

ABSTRACT. In this paper, a new variant of differential cryptanalysis is developed by applying the idea of the boomerang attack on the truncated differential. We call this variant a triangle differential cryptanalysis since it utilizes the difference of every pair in an input and output triple. Similar to the boomerang attack, the triangle differential cryptanalysis combines two independent truncated differential distinguishers of two parts of a cryptosystem into a distinguisher of the whole cryptosystem. It provides a new perspective on the differential propagation, and so it is possible to break the limit of the traditional truncated differential. An MILP modeling technique is also provided for the triangle differential distinguisher search against general SPN ciphers. To demonstrate the power of this new type of differential distinguishers, we apply it to SKINNY64 and CRAFT. For SKINNY64, an 11-round triangle differential distinguisher is obtained, while the previous longest truncated differential distinguisher is 10-round. For CRAFT, a 13-round triangle differential distinguisher is obtained, while the previous longest truncated differential distinguisher is 12-round. Besides, compared with the best distinguishers other than the truncated differential distinguishers, there are still some improvements on the probabilities for both SKINNY64 and CRAFT.

ABSTRACT. Homomorphic secret sharing (HSS) allows participants to share their private data among computing servers for joint computation of a public function without fully homomorphic encryption. It can serve as a competitive alternative to somewhat/fully homomorphic encryption (HE) in some scenarios. While the existing HSS schemes that enable computation on private data from independent multiple parties either only support a small number of parties for computing constant-degree polynomials, or involve relatively complex multi-key HE in their constructions. In this paper, we first introduce the formal notion of multi-key HSS, and propose a multi-key two-server HSS scheme from LWE without multi-key HE, by leveraging the technique of homomorphic linear combination that previously used to construct multi-key FHE from GSW-FHE in [1]. As a result, our scheme supports secure outsourcing computation of restricted multiplication straight-line (RMS) programs over private data from multiple independent sources, and the number of input clients and the degree of evaluated polynomials can be as high as a polynomial in the security parameter. Finally, we prove the security of the multi-key HSS scheme, and provide a concrete implementation.

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. 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.

ABSTRACT. A verifiable random function (VRF) allows the generation of a random number with publicly verifiable proof, showing that the random number is honestly generated. The practical VRF used in real-world applications considers the security of uniqueness, pseudorandomness, and unpredictability under malicious key generation. In this paper, we propose the security model of {\it related-key attack} to VRF for capturing attacks like tampering attacks. We propose a new construction of VRF that satisfies the RKA security together with the existing security requirements. We implement our VRF construction and demonstrate that our scheme is practical for real-world applications.