Selected Areas in Cryptography

Anonymous communication networks (ACNs) aim to thwart an adversary, who controls or observes chunks of the communication network, from determining the respective identities of two communicating parties. We focus on low-latency ACNs such as Tor, which target a practical level of anonymity without incurring an unacceptable transmission delay.

While several definitions have been proposed to quantify the level of anonymity provided by high-latency, message-centric ACNs (such as mix-nets and DC-nets), this approach is less relevant to Tor, where user–destination pairs communicate over secure overlay circuits. Moreover, existing evaluation methods of traffic analysis attacks on Tor appear somewhat ad hoc and fragmented. We propose a fair evaluation framework for such attacks against onion routing systems by identifying and discussing the crucial components for evaluation, including how to consider various adversarial goals, how to factor in the adversarial ability to collect information relevant to the attack, and how these components combine to suitable metrics to quantify the adversary’s success.

Ride Hailing Services (RHS) have become a popular means of transportation, and with its popularity comes the concerns of privacy of riders and drivers. ORide is a privacy-preserving RHS proposed at the USENIX Security Symposium 2017 and uses Somewhat Homomorphic Encryption (SHE). In their protocol, a rider and all drivers in a zone send their encrypted coordinates to the RHS Service Provider (SP) who computes the squared Euclidean distances between them and forwards them to the rider. The rider decrypts these and selects the optimal driver with least Euclidean distance.

In this work, we demonstrate a location-harvesting attack where an honest-but-curious rider, making only a single ride request, can determine the exact coordinates of about half the number of responding drivers even when only the distance between the rider and drivers are given. The significance of our attack lies in inferring locations of other drivers in the zone, which are not (supposed to be) revealed to the rider as per the protocol.

We validate our attack by running experiments on zones of varying sizes in arbitrarily selected big cities. Our attack is based on enumerating lattice points on a circle of sufficiently small radius and eliminating solutions based on conditions imposed by the application scenario. Finally, we propose a modification to ORide aimed at thwarting our attack and show that this modification provides sufficient driver anonymity while preserving ride matching accuracy.

The Boneh-Katz transformation (CT-RSA 2005) converts a selectively-secure identity/tag-based encryption scheme into a public-key encryption scheme secure against chosen-ciphertext attacks. We show that if the underlying primitives are pseudorandom, then the public-key encryption scheme obtained by the Boneh-Katz transformation is also pseudorandom. A similar result holds for oblivious sampleability (Canetti and Fischlin (CRYPTO 2001)). As applications, we can construct

Cryptographic keys are increasingly stored in dedicated hardware or behind software interfaces. Doing so limits access, such as permitting only signing via ECDSA. This makes using them in existing ring and group signature schemes impossible as these schemes assume the ability to access the private key for other operations. We present a \(\varSigma \)-protocol that uses a committed public key to verify an ECDSA or Schnorr signature on a message, without revealing the public key. We then discuss how this protocol may be used to derive ring signatures in combination with Groth–Kohlweiss membership proofs and other applications. This scheme has been implemented and source code is freely available.

Arbiter based Physical Unclonable Function (sometimes called Physically Unclonable Function, or in short PUF) is a hardware based pseudorandom bit generator. The pseudorandomness in the output bits depends on device specific parameters. For example, based on the delay parameters, an n-length Arbiter PUF can be considered as an n-variable Boolean function. We note that the random variation of the delay parameters cannot exhaust all the Boolean functions and the class is significantly smaller as well as restricted. While this is expected (as the autocorrelation property in certain cases is quite biased), we present a more disciplined and first theoretical combinatorial study in this domain. Our work shows how one can explore the functions achieved through an Arbiter based PUF construction with random delay parameters. Our technique mostly shows limitation of such functions from the angle of cryptographic evaluation as the subclass of the Boolean function can be identified with much better efficiency (much less complexity) than random. On the other hand, we note that under certain constraints on the weights of inputs, such a simple model of Arbiter PUFs provide good cryptographic parameters in terms of differential analysis. In this regard, we theoretically solve the problem of autocorrelation properties in a restricted space of input variables with a fixed weight. Experimental evidences complement our theoretical findings.

We examine Multi-Party Computation protocols in the active-security-with-abort setting for \(\mathcal {Q}_2\) access structures over small and large finite fields \(\mathbb {F}_p\) and over rings \(\mathbb {Z}_{p^k}\). We give general protocols which work for any \(\mathcal {Q}_2\) access structure which is realised by a multiplicative Extended Span Program. We generalize a number of techniques and protocols from various papers and compare the different methodologies. In particular we examine the expected communication cost per multiplication gate when the protocols are instantiated with different access structures.

One of the finalists in the NIST Lightweight Cryptography competition is \(\mathsf {Elephant}\) v2, a parallelizable, permutation-based authenticated encryption scheme. The original first/second-round submission \(\mathsf {Elephant}\) v1/v1.1 was proven secure against nonce-respecting adversaries in the single-user setting. For the final round, the mode has undergone certain subtle modifications, the most important one being a change in the authentication portion of the mode. These changes require a new dedicated security proof.

In this work, we prove the security of the \(\mathsf {Elephant}\) v2 mode. First of all, our proof shows that \(\mathsf {Elephant}\) v2 is indeed a secure authenticated encryption scheme and that its security against nonce-respecting adversaries is on par with that of \(\mathsf {Elephant}\) v1/v1.1. In addition, our security analysis is in the multi-user setting and demonstrates that \(\mathsf {Elephant}\) v2 fares well if multiple devices use \(\mathsf {Elephant}\) v2 with independent keys. Moreover, our proof shows that \(\mathsf {Elephant}\) v2 even ensures authenticity under nonce misuse.

In this paper, we develop an S-box designing method by considering an interplay between an S-box and a linear layer, which enhances security against differential cryptanalysis. The basic idea can be found in bitslice-friendly ciphers such as Serpent and bit-permutation ciphers such as PRESENT. In those designs, S-boxes were chosen so that the branch number is not too small, which rapidly diffuses differences. We apply a similar analysis to other constructions. The first target is extended generalized Feistel networks (EGFN) and its instance Lilliput, which has an XOR layer after the standard GFN. We show that security of EGFN can be enhanced by using an S-box that does not allow any difference \(\varDelta \) to be mapped to the same \(\varDelta \) with a high probability, say \(2^{-2}\) for a 4-bit S-box. The second target is AES-like ciphers that use a binary matrix in MixColumns. We focus on the chain of differences \(\varDelta A \rightarrow \varDelta B \rightarrow \varDelta C \rightarrow \cdots \) over the S-box, where each transition occurs with a high probability. We show that security of such AES-like ciphers can be enhanced if the maximum length of the chains is short. As a proof-of-concept, we evaluate Lilliput, Midori, and SKINNY with the new S-box satisfying the property.

A large number of the symmetric-key mode of operations, such as classical CBC-MAC, have serial structures. While a serial mode gives an implementation advantage in terms of required memory or footprint compared to the parallel counterparts, it wastes the capability of parallel process even when it is available. The problem is becoming more relevant as lightweight cryptography is going to be deployed in the real world. In this article, we propose an alternative implementation strategy for serial MAC modes and serial authenticated encryption (AE) modes that allows 2-block parallel operation for verification/decryption. Our proposal maintains the original functionality and security. It is simple yet novel, and generally applicable to a wide range of existing modes including two NIST recommendations, CMAC and CCM. We demonstrate the effectiveness of our proposal by showing several case studies with software implementations.

We consider the related-tweak impossible differential cryptanalysis of TweAES. It is one of the underlying primitives of Authenticated Encryption with Associated Data (AEAD) scheme ESTATE which was accepted as one of second-round candidates in the NIST Lightweight Cryptography Standardization project. Firstly, we reveal several properties of TweAES, which show what kinds of distinguishers are more effective in recovering keys. With the help of automatic solver Simple Theorem Prover (STP), we achieve many 5.5-round related-tweak impossible differentials with fixed input differences and output differences that just have one active byte. Then, we implement 8-round key recovery attacks against TweAES based on one of these 5.5-round distinguishers. Moreover, another 5.5-round distinguisher that has four active bytes at the end is utilized to mount a 7-round key recovery attack against TweAES, which needs much lower attack complexities than the 6-round related-tweak impossible differential attack of TweAES in the design document. Our 8-round key recovery attack is the best one against TweAES in terms of the number of rounds and complexities so far.

One of the well-known superiorities of GIFT-64 over PRESENT lies in the correction of the strong linear hull effect. However, apart from the investigation of the 9-round linear hull effect in the design document, we find no linear attack result on GIFT-64. Although we do not doubt the security of GIFT-64 regarding the linear cryptanalysis, the actual resistance of the cipher to the linear attack should be evaluated since it promotes a comprehensive perception of the soundness of GIFT-64. Motivated by this observation, we implement an automatic search and find a 12-round linear distinguisher whose dominating trail is an optimal linear characteristic. Following that, the first 19-round linear attack is launched by utilising the newly identified distinguisher. On the other side, we notice that the previous differential attack of GIFT-64 covering 20 rounds claims the entire codebook. To reduce the data complexity of the 20-round attack, we apply the automatic method to exhaustively check 13-round differential trails with probabilities no less than \(2^{-64}\) and identify multiple 13-round differentials facilitating 20-round attacks without using the full codebook. One of the candidate differentials with the maximum probability and the minimum number of guessed subkey bits is then employed to realise the first 20-round differential attack without relying on the complete codebook. Given the newly obtained results, we conjecture that the resistances of GIFT-64 against differential and linear attacks do not have a significant gap. Also, we note that the attack results in this paper are far from threatening the security of GIFT-64.

The cube attack is a powerful cryptanalysis technique against symmetric primitives, especially for stream ciphers. One of the key step in a cube attack is recovering the superpoly. The division property has been introduced to cube attacks with the aim first to identify variables/monomials that are not involved in the superpoly. Recently, some improved versions of this technique allowing the recovery of the exact superpoly have been developed and applied on various stream ciphers [13, 15].

In this paper, we propose a new model to recover the exact superpoly of a stream cipher given a cube. We model the polynomials involved in the stream cipher as a directed graph. It happens that this structure handles some of the monomial cancellations more easily than those based on division property, and this leads to better timing results. We propose two implementations of our model, one in MILP and one in CP, which are up to 10 times faster than the original division property-based model from Hao et al. [13], and consistently 30 to 60 times faster than the monomial prediction-based model from Hu et al. [15].

We propose a tool for automated truncation of differential trails in ciphers using modular addition, bitwise rotation, and XOR (ARX). The tool takes as input a differential trail and produces as output a set of truncated differential trails. The set represents all possible truncations of the input trail according to certain predefined rules. A linear-time algorithm for the exact computation of the differential probability of a truncated trail that follows the truncation rules is proposed. We further describe a method to merge the set of truncated trails into a compact set of non-overlapping truncated trails with associated probability and we demonstrate the application of the tool on block cipher Speck64.

We have also investigated the effect of clustering of differential trails around a fixed input trail. The best cluster that we have found for 15 rounds has probability \(2^{-55.03}\) (consisting of 389 unique output differences) which allows us to build a distinguisher using 128 times less data than the one based on just the single best trail, which has probability \(2^{-62}\). Moreover, we show examples for Speck64 where a cluster of trails around a suboptimal (in terms of probability) input trail results in higher overall probability compared to a cluster obtained around the best differential trail.

The k-XOR problem can be generically formulated as the following: given many n-bit strings generated uniformly at random, find k distinct of them which XOR to zero. This generalizes collision search (two equal elements) to a k-tuple of inputs.

At EUROCRYPT 2020, Naya-Plasencia and Schrottenloher defined a class of quantum merging algorithms for the k-XOR problem, obtained by combining quantum search. They represented these algorithms by a set of merging trees and obtained the best ones through linear optimization of their parameters.

In this paper, we give a simplified representation of merging trees that makes their analysis easier. We give better quantum algorithms for the Single-solution k-XOR problem by relaxing one of the previous constraints, and making use of quantum walks. Our algorithms subsume or improve over all previous quantum algorithms for Single-solution k-XOR. For example, we give an algorithm for 4-XOR (or 4-SUM) in quantum time \(\widetilde{\mathcal {O}}(2^{7n/24})\).

In this paper, we study quantum key-recovery attacks on block ciphers. While it is well known that a quantum adversary can generically speed up an exhaustive search of the key, much less is known on how to use specific vulnerabilities of the cipher to accelerate this procedure. In this context, we show how to convert classical boomerang and mixing boomerang attacks into efficient quantum key-recovery attacks. In some cases, we can even obtain a quadratic speedup, the same as simple differential attacks. We apply this technique to a 5-round attack on SAFER++.

The Oil and Vinegar signature scheme, proposed in 1997 by Patarin, is one of the oldest and best understood multivariate quadratic signature schemes. It has excellent performance and signature sizes but suffers from large key sizes on the order of 50 KB, which makes it less practical as a general-purpose signature scheme. To solve this problem, this paper proposes MAYO, a variant of the UOV signature scheme whose public keys are two orders of magnitude smaller. MAYO works by using a UOV map \(\mathcal {P}:\mathbb {F}_q^n \rightarrow \mathbb {F}_q^n\) with an unusually small oil space, which makes it possible to represent the public key very compactly. The usual UOV signing algorithm fails if the oil space is too small, but MAYO works around this problem by “whipping up” the oil and vinegar map \(\mathcal {P}\) into a larger map \(\mathcal {P}^\star :\mathbb {F}_q^{kn} \rightarrow \mathbb {F}_q^m\), that does have a sufficiently large oil space. With parameters targeting NISTPQC security level I, MAYO has a public key size of only 614 Bytes and a signature size of 392 Bytes. This makes MAYO more compact than state-of-the-art lattice-based signature schemes such as Falcon and Dilithium. Moreover, we can choose MAYO parameters such that, unlike traditional UOV signatures, signatures provably only leak a negligible amount of information about the private key.

Stateful hash-based signature schemes are one of the most promising post-quantum signature schemes. Among them, XMSS and \(\mathrm {XMSS^{MT}}\) have already been specified in RFC 8391 and NIST SP 800-208. The signing time is exponential if the schemes are naively implemented. To reduce the signing time, Merkle tree traversal algorithms are used and the most time/memory efficient one is the BDS algorithm. We focus on \(\mathrm {XMSS^{MT}}\) (layered XMSS) with the BDS algorithm. Since \(\mathrm {XMSS^{MT}}\) is vulnerable to incorrect state management, the algorithm and state structure must be simple. Also, the state size for the BDS algorithm must be reduced in order to implement the scheme in resource-constrained devices. To achieve these objectives, we propose a simple and memory-efficient signature-generation algorithm for \(\mathrm {XMSS^{MT}}\).

In this paper, we propose a lattice-based encryption scheme with a short ciphertext size. Our scheme is somewhat hybrid of the NTRU type encryptions and RLWE based encryptions. In particular, the ciphertext of the scheme is a ring element as NTRU type encryptions, yet it can be compressible as RLWE based encryption schemes. Furthermore, we present a key-encapsulation mechanism that is more efficient than a direct construction from our encryption scheme.

The IND-CPA security of the schemes is based on the RLWE assumption and the NTRU assumption. Our parameterizations show that the schemes enjoy almost the same public key size as the NIST PQC finalist lattice-based candidates, yet the ciphertext size is only about \(37\%\) of them.

The Sidon cryptosystem [21] is a new multivariate encryption scheme based on the theory of Sidon spaces which was presented at PKC 2021. As is usual for this kind of schemes, its security relies on the hardness of solving particular instances of the MQ problem and of the MinRank problem. A nice feature of the scheme is that it enjoys a homomorphic property due the bilinearity of its public polynomials. Unfortunately, we will show that the Sidon cryptosystem can be broken by a polynomial time key-recovery attack. This attack relies on the existence of solutions to the underlying MinRank instance which lie in a subfield and which are inherent to the structure of the secret Sidon space. We prove that such solutions can be found in polynomial time. Our attack consists in recovering an equivalent key for the cryptosystem by exploiting these particular solutions, and this task can be performed very efficiently.

In this paper, we investigate the problem of constructing postquantum-secure verifiable delay functions (VDFs), particularly based on supersingular isogenies. Isogeny-based VDF constructions have been proposed before, but since verification relies on pairings, they are broken by quantum computers. We propose an entirely different approach using succinct non-interactive arguments (SNARGs), but specifically tailored to the arithmetic structure of the isogeny setting to achieve good asymptotic efficiency. We obtain an isogeny-based VDF construction with postquantum security, quasi-logarithmic verification, and requiring no trusted setup. As a building block, we also construct non-interactive arguments for isogeny walks in the supersingular graph over \(\mathbb F_{p^2}\), which may be of independent interest.

We present the first post-quantum secure Key-Updatable Public-Key Encryption (UPKE) construction. UPKE has been proposed as a mechanism to improve the forward-secrecy and post-compromise security of secure messaging protocols, but the hardness of all existing constructions rely on discrete logarithm assumptions. We focus our assessment on isogeny-based cryptosystems due to their suitability for performing a potentially unbounded number of update operations, a practical requirement for secure messaging where user conversations can occur over months, if not years.

We begin by formalizing two UPKE variants in the literature as Symmetric and Asymmetric UPKE, which differ in how encryption and decryption keys are updated. We argue that Asymmetric UPKE constructions in the literature cannot be straightforwardly instantiated using SIDH nor CSIDH. We then describe a SIDH construction that partially achieves the required security notions for Symmetric UPKE, but due to existing mathematical limitations, cannot provide fine-grained forward secrecy. Finally, we present a CSIDH Symmetric UPKE construction that requires a parameter set in which the class group structure is fully known. We discuss open problems which are applicable to any cryptosystem with similar requirements for continuous operations over the secret domain.

We present a polynomial-time adaptive attack on the genus-2 variant of SIDH (G2SIDH) and describe an improvement to its secret selection procedure. G2SIDH is a generalisation of the Supersingular Isogeny Diffie–Hellman key exchange into the genus-2 setting and achieves the same security as SIDH while using fields a third of the size.

We analyze the keyspace of G2SIDH and achieve an improvement to the secret selection by using symplectic bases for the torsion subgroups. This allows for the near uniform sampling of secrets without needing to solve multiple linear congruences as suggested by Flynn–Ti. More generally, using symplectic bases enables us to classify and enumerate isogeny kernel subgroups and thus simplify the secret sampling step for general genus-2 SIDH-style constructions.

The proposed adaptive attack on G2SIDH is able to recover the secret when furnished with an oracle that returns a single bit of information. We ensure that the maliciously generated information provided by the attacker cannot be detected by implementing simple countermeasures, forcing the use of the Fujisaki–Okamoto transform for CCA2-security. We demonstrate this attack and show that it is able to recover the secret isogeny in all cases of G2SIDH using a symplectic basis before extending the strategy to arbitrary bases.