International Association
for Cryptologic Research

In ToSC 2021(2), Sun et al. implemented an automatic search with the Boolean satisfiability problem (SAT) method on GIFT-128 and identified a 19-round linear approximation with the expected linear potential being $2^{-117.43}$, which is utilised to launch a 24-round attack on the cipher. In this addendum, we discover a new 19-round linear approximation with a lower expected linear potential. However, in the attack, one more round can be appended after the distinguisher. As a result, we improve the previous optimal linear attack by one round and put forward a 25-round linear attack. Given that the optimal differential attack on GIFT-128, for now, covers 27-round, the resistances of the cipher against differential and linear attacks still have a 2-round gap.

Isogeny-based cryptography is one of the main candidates of post-quantum cryptography. To realize efficient computations, one usually uses formulas of scalar multiplications and isogeny computations on elliptic curves using only one coordinate in isogeny-based cryptography. The $x$-coordinate of Montgomery curves is the most standard, and we sometimes use the $x$-coordinate of Montgomery$^-$ curves, the $w$-coordinate of Edwards curves, and the $w$-coordinate of Huff's curves.

In this paper, we define a novel function on elliptic curves called the generalized Montgomery coordinate that has the four coordinates described above as special cases. For a generalized Montgomery coordinate, we construct an explicit formula of scalar multiplication which includes the division polynomial, and both a formula of an image point under an isogeny and that of a coefficient of the codomain curve.

Finally, we expect numerous applications for the generalized Montgomery coefficient. As an experimental study, we present two applications of the theory of a generalized Montgomery coordinate. The first one is to construct a new efficient formula to compute isogenies on Montgomery curves. This formula is more efficient than the previous one for high degree isogenies as the $\sqrt{\vphantom{2}}$\'{e}lu's formula in our implementation. The second one is to construct a new generalized Montgomery coordinate for Montgomery$^-$ curves used for CSURF.

In this work, we first propose a new functional bootstrapping with TFHE for evaluating any function of domain and codomain the real torus T by using a small number of bootstrappings. This result improves some aspects of previous approaches: like them, we allow for evaluating any functions, but with better precision. In addition, we develop more efficient multiplication and addition over ciphertexts building on the digit-decomposition approach. As a practical application, our results lead to an efficient implementation of ReLU, one of the most used activation functions in deep learning. The paper is concluded by extensive experimental results comparing each building block as well as their practical relevance and trade-offs.

Firekite is a synchronous stream cipher using a pseudo-random number generator (PRNG) whose security relies on the hardness of the \textit{Learning Parity with Noise} (LPN) problem. It is one of a few LPN-based symmetric encryption schemes and it can be very efficiently implemented on a low-end SoC FPGA. The designers, Bogos, Korolija, Locher, and Vaudenay, demonstrated appealing properties of Firekite such as requiring only one source of cryptographically strong bits, small key size, high attainable throughput, and a concrete measurement for the bit level security depending on the selected practical parameters. We propose distinguishing and key-recovery attacks on Firekite by exploiting the structural properties of its PRNG. We adopt several \textit{birthday-paradox} techniques to show that a particular sum of Firekite's output has a low Hamming weight with higher probability than the random case. We achieve the best distinguishing attacks with complexities $2^{66.75}$ and $2^{106.75}$ for Firekite's parameters corresponding to $80$-bit and $128$-bit security, respectively. By applying the distinguishing attacks and an additionally suggested algorithm, one can also recover the secret matrix used in the Firekite PRNG, which is built from the secret key bits. This key recovery attack works on most large parameter sets and has slightly larger complexity, for example $2^{69.87}$ on the $80$-bit security parameters $n=16384, m = 216, k = 216$.

Some recent research articles [23, 24] addressed an explicit specification of indicators that specify bent functions in the so-called $\mathcal{C}$ and $\mathcal{D}$ classes, derived from the Maiorana- McFarland ($\mathcal{M}$) class by C. Carlet in 1994 [5]. Many of these bent functions that belong to $\mathcal{C}$ or $\mathcal{D}$ are provably outside the completed $\mathcal{M}$ class. Nevertheless, these modifications are performed on affine subspaces, whereas modifying bent functions on suitable subsets may provide us with further classes of bent functions. In this article, we exactly specify new families of bent functions obtained by adding together indicators typical for the $\mathcal{C}$ and $\mathcal{D}$ class, thus essentially modifying bent functions in $\mathcal{M}$ on suitable subsets instead of subspaces. It is shown that the modification of certain bent functions in $\mathcal{M}$ gives rise to new bent functions which are provably outside the completed $\mathcal{M}$ class. Moreover, we consider the so-called 4-bent concatenation (using four different bent functions on the same variable space) of the (non)modified bent functions in $\mathcal{M}$ and show that we can generate new bent functions in this way which do not belong to the completed $\mathcal{M}$ class either. This result is obtained by specifying explicitly the duals of four constituent bent functions used in the concatenation. The question whether these bent functions are also excluded from the completed versions of $\mathcal{PS}$, $\mathcal{C}$ or $\mathcal{D}$ remains open and is considered difficult due to the lack of membership indicators for these classes.

We address the problem of learning a machine learning model from training data that originates at multiple data owners, while providing formal privacy guarantees regarding the protection of each owner's data. Existing solutions based on Differential Privacy (DP) achieve this at the cost of a drop in accuracy. Solutions based on Secure Multiparty Computation (MPC) do not incur such accuracy loss but leak information when the trained model is made publicly available. We propose an MPC solution for training DP models. Our solution relies on an MPC protocol for model training, and an MPC protocol for perturbing the trained model coefficients with Laplace noise in a privacy-preserving manner. The resulting MPC+DP approach achieves higher accuracy than a pure DP approach, while providing the same formal privacy guarantees. Our work obtained first place in the iDASH2021 Track III competition on confidential computing for secure genome analysis.

QR-UOV is a variant of UOV with smaller keys proposed at Asiacrypt 2021. In this paper, we show that QR-UOV can be constructed by a smaller UOV over an extension field.

We extend a previous framework for designing differentially private (DP) mechanisms via randomized graph colorings that was restricted to binary functions, corresponding to colorings in a graph, to multi-valued functions. As before, datasets are nodes in the graph and any two neighboring datasets are connected by an edge. In our setting, we assume each dataset has a preferential ordering for the possible outputs of the mechanism, which we refer to as a rainbow. Different rainbows partition the graph of datasets into different regions. We show that when the DP mechanism is pre-specified at the boundary of such regions, at most one optimal mechanism can exist. Moreover, if the mechanism is to behave identically for all same-rainbow boundary datasets, the problem can be greatly simplified and solved by means of a morphism to a line graph. We then show closed form expressions for the line graph in the case of ternary functions. Treatment of ternary queries in this paper displays enough richness to be extended to higher-dimensional query spaces with preferential query ordering, but the optimality proof does not seem to follow directly from the ternary proof.

Bent functions are optimal combinatorial objects and have been studied over the last four decades. Secondary construction plays a central role in constructing bent functions since it may generate bent functions outside the primary classes of bent functions. In this study, we improve a theoretical framework of the secondary construction of bent functions in terms of the composition of Boolean functions. Based on this framework, we propose several constructions of bent functions through the composition of a balanced Boolean function and dually isomorphic (DI) bent functions defined herein. In addition, we present a construction of self-dual bent functions.

We introduce verifiable partially-decryptable commitments (VPDC), as a building block for constructing efficient privacy-preserving protocols supporting auditability by a trusted party. A VPDC is an extension of a commitment along with an accompanying proof, convincing a verifier that (i) the given commitment is well-formed and (ii) a certain part of the committed message can be decrypted using a (secret) trapdoor known to a trusted party.

We first formalize VPDCs and then introduce a general decryption feasibility result that overcomes the challenges in relaxed proofs arising in the lattice setting. Our general result can be applied to a wide class of Fiat-Shamir based protocols and may be of independent interest.

Next, we show how to extend the commonly used lattice-based `Hashed-Message Commitment' (HMC) scheme into a succinct and efficient VPDC. In particular, we devise a novel `gadget'-based Regev-style (partial) decryption method, compatible with efficient relaxed lattice-based zero-knowledge proofs. We prove the soundness of our VPDC in the setting of adversarial proofs, where a prover tries to create a valid VPDC output that fails in decryption.

To demonstrate the effectiveness of our results, we extend a private blockchain payment protocol, MatRiCT, by Esgin et al. (ACM CCS '19) into a formally auditable construction, which we call MatRiCT-Au, with very low communication and computation overheads over MatRiCT.

In this work, we study hybrid exact/relaxed zero-knowledge proofs from lattices, where the proved relation is exact in one part and relaxed in the other. Such proofs arise in important real-life applications such as those requiring verifiable PRF evaluation and have so far not received significant attention as a standalone problem.

We first introduce a general framework, LANES+, for realizing such hybrid proofs efficiently by combining standard relaxed proofs of knowledge RPoK and the LANES framework (due to a series of works in Crypto'20, Asiacrypt'20, ACM CCS'20). The latter framework is a powerful lattice-based proof system that can prove exact linear and multiplicative relations. The advantage of LANES+ is its ability to realize hybrid proofs more efficiently by exploiting RPoK for the high-dimensional part of the secret witness while leaving a low-dimensional secret witness part for the exact proof that is proven at a significantly lower cost via LANES.

We apply our LANES+ framework to construct substantially shorter proofs of rounding, which is a central tool for verifiable deterministic lattice-based cryptography. Based on our rounding proof, we then design an efficient long-term verifiable random function (VRF), named LaV. LaV leads to the shortest VRF outputs among the proposals of standard (i.e., long-term and stateless) VRFs based on quantum-safe assumptions. Of independent interest, we also present a general framework for the construction of efficient VRFs (in the random oracle model) and generalized results for challenge difference invertibility, a fundamental soundness security requirement for many proof systems.

Related-key attacks (RKA) are powerful cryptanalytic attacks, where the adversary can tamper with the secret key of a cryptographic scheme. Since their invention, RKA security has been an important design goal in cryptography, and various works aim at designing cryptographic primitives that offer protection against related-key attacks. At EUROCRYPT'03, Bellare and Kohno introduced the first formal treatment of related-key attacks focusing on pseudorandom functions and permutations. This was later extended to cover other primitives such as signatures and public key encryption schemes, but until now, a comprehensive formal security analysis of authenticated encryption schemes with associated data (AEAD) in the RKA setting has been missing. The main contribution of our work is to close this gap for the relevant class of nonce-based AEAD schemes. To this end, we revisit the common approach to construct AEAD from encryption and message authentication. We extend the traditional security notion of AEAD to the RKA setting and consider an adversary that can tamper with the key $K_e$ and $K_m$ of the underlying encryption and MAC, respectively. We study two security models. In our weak setting, we require that tampering will change both $K_e$ and $K_m$, while in our strong setting, tampering can be arbitrary, i.e., only one key might be affected. We then study the security of the standard composition methods by analysing the nonce-based AEAD schemes N1 (Encrypt-and-MAC), N2 (Encrypt-then-MAC), and N3 (MAC-then-Encrypt) due to Namprempre, Rogaway, and Shrimpton (EUROCRYPT'03). We show that these schemes are weakly RKA secure, while they can be broken under a strong related-key attack. Finally, based on the N3 construction, we give a novel AEAD scheme that achieves our stronger notion.

In this work, we study the security of sponge-based authenticated encryption schemes against quantum attackers. In particular, we analyse the sponge-based authenticated encryption scheme SLAE as put forward by Degabriele et al. (ASIACRYPT'19). We show that the scheme achieves security in the post-quantum (QS1) setting in the quantum random oracle model by using the one-way to hiding lemma. Furthermore, we analyse the scheme in a fully-quantum (QS2) setting. There we provide a set of attacks showing that SLAE does not achieve ciphertext indistinguishability and hence overall does not provide the desired level of security.

Cryptography is increasingly deployed in applications running on open devices in which the software is extremely vulnerable to attacks, since the attacker has complete control over the execution platform and the software implementation itself. This creates a challenge for cryptography: design implementations of cryptographic algorithms that are secure, not only in the black-box model, but also in this attack context that is referred to as the white-box adversary model. Moreover, emerging applications such as mobile payment, mobile contract signing or blockchain-based technologies have created a need for white-box implementations of public-key cryptography, and especially of signature algorithms.

However, while many attempts were made to construct white-box implementations of block-ciphers, almost no white-box implementations have been published for what concerns asymmetric schemes. We present here a concrete white-box implementation of the well-known HFE signature algorithm for a specific set of internal polynomials. For a security level $2^{80}$, the public key size is approximately 62.5 MB and the white-box implementation of the signature algorithm has a size approximately 256 GB.

In 2009, Dinur and Shamir proposed the cube attack, an algebraic cryptanalysis technique that only requires black box access to a target cipher. Since then, this attack has received both many criticisms and endorsements from crypto community; this work aims at revising and collecting the many attacks that have been proposed starting from it. We categorise all of these attacks in five classes; for each class, we provide a brief summary description along with the state-of-the-art references and the most recent cryptanalysis results. Furthermore, we extend and refine the new notation we proposed in 2021 and we use it to provide a consistent definition for each attack family. Finally, in the appendix, we provide an in-depth description of the kite attack framework, a cipher independent tool we firstly proposed in 2018 that implements the kite attack on GPUs. To prove its effectiveness, we use Mickey2.0 as a use case, showing how to embed it in the framework.

Payment channel networks (PCNs) provide a faster and cheaper alternative to transactions recorded on the blockchain. Clients can trustlessly establish payment channels with relays by locking coins and then send signed payments that shift coin balances over the network's channels. Although payments are never published, anyone can track a client's payment by monitoring changes in coin balances over the network's channels. We present Twilight, the first PCN that provides a rigorous differential privacy guarantee to its users. Relays in Twilight run a noisy payment processing mechanism that hides the payments they carry. This mechanism increases the relay's cost, so Twilight combats selfish relays that wish to avoid it using a trusted execution environment (TEE) that ensures they follow its protocol. The TEE does not store the channel's state, which minimizes the trusted computing base. Crucially, Twilight ensures that even if a relay breaks the TEE's security, it cannot break the integrity of the PCN. We analyze Twilight in terms of privacy and cost and study the trade-off between them. We implement Twilight using Intel's SGX framework and evaluate its performance using relays deployed on two continents. We show that a route consisting of 4 relays handles 820 payments/sec.

Firstly, we improve the evaluation theory of differential propagation for modular additions and XORs, respectively. By introducing the concept of $additive$ $sums$ and using signed differences, we can add more information of value propagation to XOR differential propagation to calculate the probabilities of differential characteristics more precisely. Based on our theory, we propose the first modeling method to describe the general ARX differential propagation, which is not based on the Markov cipher assumption. Secondly, we propose an automatic search tool for differential characteristics with more precise probabilities in ARX ciphers. We find that some differential characteristics that used to be valid become impossible, and some probabilities that used to be underestimated increase. In applications, for CHAM-64/128 (one of the underlying block ciphers in COMET, one of 32 second-round candidates in NIST’s lightweight cryptography standardization process), we find that there is no valid $39$-round differential characteristic with a probability of $2^{-63}$ computed using previous methods, and we correct the probabilities to $2^{-64}$ and $2^{-64}$ instead of $2^{-65}$ and $2^{-65}$ computed using previous methods for two 39-round differential characteristics starting from the $1$-st round, respectively; however, if we search for differential characteristics starting from the $5$-th round, the two differential characteristics are invalid, which means that the round constants can affect the security of ARX ciphers against differential cryptanalysis; for Alzette with $c = \tt{0xb7e15162}$ (one of the S-boxes in SPARKLE, one of 10 finalists in NIST’s lightweight cryptography standardization process), we correct the probabilities to $0$ and $2^{-22}$ instead of $2^{-23}$ and $2^{-23}$ computed using previous methods for two 4-round differential characteristics, respectively; for XTEA, we correct the probabilities to $0$ and $2^{-49}$ instead of $2^{-58}$ and $2^{-56}$ computed using previous methods for two 10-round differential characteristics, respectively. Moreover, for Alzette with $c = \tt{0xb7e15162}$, XTEA, the $\tt{quarterround}$ function of Salsa20, and the round function of Chaskey, we find some invalid DCs that Leurent’s ARX Toolkit cannot detect. Thirdly, we propose a SAT-based automatic search tool for impossible differential characteristics in ARX ciphers. We find some distinguishers ignored by previous methods. In applications, for CHAM-64/128, we find five $20$-round and nineteen $19$-round impossible differential characteristics starting from the $3$-rd round for the first time. However, if we search for impossible differential characteristics starting from the $1$-st round, we cannot find any $20$-round impossible differential characteristic, which means that the round constants can affect the security of ARX ciphers against impossible differential cryptanalysis. Moreover, we find more impossible differential characteristics for 18-round, 16-round, 14-round, and 12-round CHAM-64/128, respectively. According to our results, the differential (resp. impossible differential) attack constructed by the previous methods of placing a DC (resp. an ID) anywhere in a block cipher may be invalid.

This paper proposes functional cryptanalysis, a flexible and versatile approach to analyse symmetric-key primitives with two primary features. Firstly, it is a generalization of multiple attacks including (but not limited to) differential, rotational and rotational-xor cryptanalysis. Secondly, it is a theoretical framework that unifies all of the aforementioned cryptanalysis techniques and at the same time opens up possibilities for the development of new cryptanalytic approaches. The main idea of functional cryptanalysis is the usage of binary relations in the form of functions, hence the name functional, instead of binary operations like in a classical settings of "differential"-like cryptanalysis. We establish the theoretical foundations of functional cryptanalysis from standard terminologies. This work also presents an interpretation of functional cryptanalysis from the point of view of commutative algebra. In particular, we exhibit an algorithm to compute the functional probability (hence differential, rotational, and rotational-xor probability) using Grobner bases. We demonstrate the applicability of functional cryptanalysis against reduced-round Xoodoo and compare it against the best differential. To avoid dealing with invalid differential trails, we propose a method to construct a valid differential trail using Satisfiability Modulo Theory (SMT). To the best of our knowledge, this is the first time the SMT model is used to construct a valid differential while previous approaches rely on Mixed-Integer Linear Programming (MILP) model. Lastly, we remark that the use of non-translation functionals shares analogous advantages and limitations with the use of nonlinear approximations in linear cryptanalysis.

Vehicular-to-Everything (V2X) communications enable vehicles to exchange messages with other entities, including nearby vehicles and pedestrians. V2X is, thus, essential for establishing an Intelligent Transportation System (ITS), where vehicles use information from their surroundings to reduce traffic congestion and improve safety. To avoid abuse, V2X messages should be digitally signed using valid digital certificates. Messages sent by unauthorized entities can then be discarded, while misbehavior can lead to the revocation of the corresponding certificates. One challenge in this scenario is that messages must be verified shortly after arrival (e.g., within centiseconds), whereas vehicles may receive thousands of them per second. To handle this issue, some solutions propose prioritization or delayed-verification mechanisms, while others involve signature schemes that support batch verification. In this manuscript, we discuss two mechanisms that complement such proposals, enabling the authentication of a sequence of messages from the same source with one single signature verification. Our analysis shows that the technique can reduce the number of verified signatures by around 90% for reliable communication channels, and by more than 65% for a maximum packet loss rate of 20%.

In a ring-signature-based anonymous cryptocurrency, signers of a transaction are hidden among a set of potential signers, called a ring, whose size is much smaller than the number of all users. The ring-membership relations specified by the sets of transactions thus induce bipartite transaction graphs, whose distribution is in turn induced by the ring sampler underlying the cryptocurrency.

Since efficient graph analysis could be performed on transaction graphs to potentially deanonymise signers, it is crucial to understand the resistance of (the transaction graphs induced by) a ring sampler against graph analysis. Of particular interest is the class of partitioning ring samplers. Although previous works showed that they provide almost optimal local anonymity, their resistance against global, e.g. graph-based, attacks were unclear.

In this work, we analyse transaction graphs induced by partitioning ring samplers. Specifically, we show (partly analytically and partly empirically) that, somewhat surprisingly, by setting the ring size to be at least logarithmic in the number of users, a graph-analysing adversary is no better than the one that performs random guessing in deanonymisation up to constant factor of 2.