Topics in Cryptology – CT-RSA 2022

Multicast Key Agreement (MKA) is a long-overlooked natural primitive of large practical interest. In traditional MKA, an omniscient group manager privately distributes secrets over an untrusted network to a dynamically-changing set of group members. The group members are thus able to derive shared group secrets across time, with the main security requirement being that only current group members can derive the current group secret. There indeed exist very efficient MKA schemes in the literature that utilize symmetric-key cryptography. However, they lack formal security analyses, efficiency analyses regarding dynamically changing groups, and more modern, robust security guarantees regarding user state leakages: forward secrecy (FS) and post-compromise security (PCS). The former ensures that group secrets prior to state leakage remain secure, while the latter ensures that after such leakages, users can quickly recover security of group secrets via normal protocol operations.

We therefore present rigorous, stronger MKA security definitions that provide increasing levels of security in the case of both user and group manager state leakage, and that are suitable for modern applications, such as SGM. We then construct a formally secure MKA protocol with strong efficiency guarantees for dynamic groups. Finally, we run experiments which show that the left-balanced binary tree structure used in TreeKEM can be replaced with red-black trees in MKA for better efficiency.

Goh and Jarecki (Eurocrypt 2003) showed how to get a signature scheme from the computational Diffie-Hellman assumption, and they introduced the name EDL for signatures of this type. The corresponding EDL family of signature schemes is remarkable for several reasons: elegance, simplicity and tight security. However, EDL security proofs stand in the random oracle model, and, to the best of our knowledge, extending this family without using an idealization of hash functions has never been successful.

In this paper, we propose a new signature scheme belonging to the EDL family, which is simple, natural and efficient, without using the random oracle model. Our scheme is based on the very same assumption than the Boneh-Boyen scheme, namely the strong Diffie-Hellman assumption, with the precision that our groups are not bound to being bilinear. We also make use of a correlation-intractable hash function, for a particular relation related to discrete-logarithm.

In addition to the theoretical interest of extending the EDL family without the random oracle model, our scheme is also one of the very few schemes which achieve discrete-log security properties without relying on pairings.

In the third round of the NIST PQC standardization process, the only isogeny-based candidate, SIKE, suffers from slow performance when compared to other contenders. The large-degree isogeny computation performs a series of isogenous mappings between curves, to account for about 80% of SIKE’s latency. Here, we propose, implement, and evaluate a new method for computing large-degree isogenies of an odd power. Our new strategy for this computation avoids expensive recomputation of temporary isogeny results. We modified open-source libraries targeting x86, ARM64, and ARM32 platforms. Across each of these implementations, our new method achieves 10% and 5% speedups in SIKE’s key encapsulation and decapsulation operations, respectively. Additionally, these implementations use 3% less stack space at only a 48 byte increase in code size. Given the benefit and simplicity of our approach, we recommend this method for current and emerging SIKE implementations.

At PQCrypto-2020, Castryck and Decru proposed CSURF (CSIDH on the surface) as an improvement to the CSIDH protocol. Soon after that, at Asiacrypt-2020, together with Vercauteren they introduced radical isogenies as a further improvement. The main improvement in these works is that both CSURF and radical isogenies require only one torsion point to initiate a chain of isogenies, in comparison to Vélu isogenies which require a torsion point per isogeny. Both works were implemented using non-constant-time techniques, however, in a realistic scenario, a constant-time implementation is necessary to mitigate risks of timing attacks. The analysis of constant-time CSURF and radical isogenies was left as an open problem by Castryck, Decru, and Vercauteren. In this work we analyze this problem. A straightforward constant-time implementation of CSURF and radical isogenies encounters too many issues to be cost effective, but we resolve some of these issues with new optimization techniques. We introduce projective radical isogenies to save costly inversions and present a hybrid strategy for integration of radical isogenies in CSIDH implementations. These improvements make radical isogenies almost twice as efficient in constant-time, in terms of finite field multiplications. Using these improvements, we then measure the algorithmic performance in a benchmark of CSIDH, CSURF and CRADS (an implementation using radical isogenies) for different prime sizes. Our implementation provides a more accurate comparison between CSIDH, CSURF and CRADS than the original benchmarks, by using state-of-the-art techniques for all three implementations. Our experiments illustrate that the speed-up of constant-time CSURF-512 with radical isogenies is reduced to about 3% in comparison to the fastest state-of-the-art constant-time CSIDH-512 implementation. The performance is worse for larger primes, as radical isogenies scale worse than Vélu isogenies.

Many central banks, as well as blockchain systems, are looking into distributed versions of interbank payment systems, in particular the netting procedure. When executed in a distributed manner this presents a number of privacy problems. This paper studies a privacy-preserving netting protocol to solve the gridlock resolution problem in such Real Time Gross Settlement systems. Our solution utilizes Multi-party Computation and is implemented in the SCALE MAMBA system, using Shamir secret sharing scheme over three parties in an actively secure manner. Our experiments show that, even for large throughput systems, such a privacy-preserving operation is often feasible.

The Cheon-Kim-Kim-Song (CKKS) homomorphic encryption scheme is currently the most efficient method to perform approximate homomorphic computations over real and complex numbers. Although the CKKS scheme can already be used to achieve practical performance for many advanced applications, e.g., in machine learning, its broader use in practice is hindered by several major usability issues, most of which are brought about by relatively high approximation errors and the complexity of dealing with them.

We present a reduced-error CKKS variant that removes the approximation errors due to the Learning With Errors (LWE) noise in the encryption and key switching operations. We propose and implement its Residue Number System (RNS) instantiation that has a lower error than the original CKKS scheme implementation based on multiprecision integer arithmetic. While formulating the RNS instantiation, we also develop an intermediate RNS variant that has a smaller approximation error than the prior RNS variant of CKKS. The high-level idea of our main RNS-related improvements is to remove the approximate scaling error using a novel procedure that computes level-specific scaling factors. The rescaling operations and scaling factor adjustments in our implementation are done automatically.

We implement both RNS variants in PALISADE and compare their approximation error and efficiency to the prior RNS variant. Our results for uniform ternary secret key distribution, which is the most efficient setting included in the community homomorphic encryption security standard, show that the reduced-error CKKS RNS implementation typically has an approximation error that is 6 to 9 bits smaller for computations with multiplications than the prior RNS variant. The results for the sparse secret setting, which was used for the original CKKS scheme, imply that our reduced-error CKKS RNS implementation has an approximation error up to 12 bits smaller than the prior RNS variant.

We introduce lattice-based practical seed-recovery attacks against two efficient number-theoretic pseudo-random number generators: the fast knapsack generator and a family of combined multiple recursive generators. The fast knapsack generator was introduced in 2009 by von zur Gathen and Shparlinski. It generates pseudo-random numbers very efficiently with strong mathematical guarantees on their statistical properties but its resistance to cryptanalysis was left open since 2009. The given attacks are surprisingly efficient when the truncated bits do not represent a too large proportion of the internal states. Their complexities do not strongly increase with the size of parameters, only with the proportion of discarded bits.

A multiple recursive generator is a pseudo-random number generator based on a constant-recursive sequence. A combined multiple recursive generator is a pseudo-random number generator based on combining two or more multiple recursive generators. L’Écuyer presented the general construction in 1996 and a popular instantiation deemed MRG32k3a in 1999. We use algebraic relations of both pseudo-random generators with underlying algebraic generators to show that they are cryptographically insecure. We provide a theoretical analysis as well as efficient implementations.

The deterministic ECDSA and EdDSA signature schemes have found plenty of applications since their publication, e.g., block chain and Internet of Thing, and have been stated in RFC 6979 and RFC 8032 by IETF respectively. Their theoretical security can be guaranteed within certain well-defined models, and since no randomness is required by the algorithms anymore their practical risks from the flaw of random number generators are mitigated. However, the situation is not really optimistic, since it has been gradually found that delicately designed fault attacks can threaten the practical security of the schemes.

In this paper, based on the random fault models of intermediate values during signature generation, we propose a lattice-based fault analysis method to the deterministic ECDSA and EdDSA algorithms. By virtue of the algebraic structures of the deterministic algorithms, we show that, when providing with some faulty signatures and an associated correct signature of the same input message, some instances of SVP or CVP problems in some lattice can be constructed to recover the signing key. The allowed faulty bits in the method are close to the size of the signing key, and obviously bigger than that allowed by the existing differential fault attacks. In addition, the lattice-based approach supports more alternative targets of fault injection, which further improves its applicability when comparing with the existing approaches.

We perform some experiments to demonstrate the effectiveness of the key recovery method. In particular, for deterministic ECDSA/EdDSA algorithm with 256-bit signing key, the key can be recovered efficiently with significant probability even if the targets are affected by 250/247 faulty bits. However, this is impractical for the existing enumerating approaches.

Majority of lattice-based encryption schemes allow the possibility of decryption failures. It is now understood that this property makes such encryption systems susceptible to the so-called decryption failure attack. In such an attack, an adversary can use a large number of ciphertexts that cause decryption failures to help to recover a private key. In PQC2020, Bindel and Schanck observed that successful decryptions also imply some information about the secret as the secret vector must be away from certain spherical caps. In this paper, we revisit this problem by exploring certain geometric properties in lattice based schemes. We are able to produce more tools for crypt-analysis and operations of these schemes and provide a more accurate interpretation of the information brought from successful decryptions to enhance the failure boosting. By using (recent) precise formulas, we develop some techniques to accurately characterize relationships between a private key and successful queries to the decryption oracle. A finer estimation of the valid proportion of key candidates that can be excluded from successful queries is given. The decryption failure probability is also more accurately analysed. Our discussion addresses and corrects previous errors and our experimental data is usable in assessing the IND-CCA security of (R/M)-LWE/LWR based systems.

In order to provide benefits in the areas of fully homomorphic encryption (FHE), multi-party computation (MPC), post-quantum signature schemes, or efficient masked implementations for side-channel resistance, reducing the number of multiplications has become a quite popular trend for the symmetric cryptographic primitive designs. With an aggressive design strategy exploiting the extremely simple and low-degree S-box and low number of rounds, Pyjamask, the fundamental block cipher of the AEAD with the same name, has the smallest number of AND gates per bit among all the existing block ciphers (except LowMC or Rasta which work on unconventional plaintext/key sizes). Thus, although the AEAD Pyjamask  stuck at the second round of the NIST lightweight cryptography standardization process, the block cipher Pyjamask  itself still attracts a lot of attention. Not very unexpectedly, the low degree and the low number of rounds are the biggest weakness of Pyjamask. At FSE 2020, Dobraunig et al. successfully mounted an algebraic and higher-order differential attack on full Pyjamask-96, one member of the Pyjamask  block cipher family. However, the drawback of this attack is that it has to use the full codebook, which makes the attack less appealing. In this paper, we take integral attacks as our weapon, which are also sensitive to the low degree. Based on a new 11-round integral distinguisher found by state-of-the-art detection techniques, and combined with the relationship between round keys that reduces the involved keys, we give the key recovery attack on the full Pyjamask-96 without the full codebook for the first time. Further, the algebraic and higher-order differential technique does not work for Pyjamask-128, the other member of the Pyjamask  block cipher family. To better understand the security margin of Pyjamask-128, we present the first third-party cryptanalysis on Pyjamask-128 up to 11 out of 14 rounds.

SKINNY-AEAD is one of the second-round candidates of the Lightweight Cryptography Standardization project held by NIST. SKINNY-AEAD M1 is the primary member of six SKINNY-AEAD schemes, while SKINNY-AEAD M3 is another member with a small tag. In the design document, only security analyses of their underlying primitive SKINNY-128-384 are provided. Besides, there are no valid third-party analyses on SKINNY-AEAD M1/M3 according to our knowledge. Therefore, this paper focuses on constructing the first third-party security analyses on them under a nonce-respecting scenario. By taking the encryption mode of SKINNY-AEAD into consideration and exploiting several properties of SKINNY, we can deduce some necessary constraints on the input and tweakey differences of related-tweakey impossible differential distinguishers. Under these constraints, we can find distinguishers suitable for mounting powerful tweakey recovery attacks. With the help of the automatic searching algorithms based on STP, we find some 14-round distinguishers. Based on one of these distinguishers, we mount a 20-round and an 18-round tweakey recovery attack on SKINNY-AEAD M1/M3. To the best of our knowledge, all these attacks are the best ones so far.

In 2015, the block cipher Kalyna has been approved as the new encryption standard of Ukraine. The cipher is a substitution-permutation network, whose design is based on AES, but includes several different features. Most notably, the key expansion in Kalyna is designed to resist recovering the master key from the round keys.

In this paper we present a cache attack on the Kalyna key expansion algorithm. Our attack observes the cache access pattern during key expansion, and uses the obtained information together with one round key to completely recover the master key. We analyze all five parameter sets of Kalyna. Our attack significantly reduces the attack cost and is practical for the Kalyna-128/128 variant, where it is successful for over 97% of the keys and has a complexity of only \(2^{43.58}\). To the best of our knowledge, this is the first attack on the Kalyna key expansion algorithm.

As a secondary contribution we observe that the additive key whitening used in Kalyna facilitates first round cache attacks. Specifically, we design an attack that can recover the full first round key with only seven adaptively chosen plaintexts.

Deep learning-based side-channel analysis performance heavily depends on the dataset size and the number of instances in each target class. Both small and imbalanced datasets might lead to unsuccessful side-channel attacks. The attack performance can be improved by generating traces synthetically from the obtained data instances instead of collecting them from the target device, but this is a cumbersome and challenging task.

We propose a novel data augmentation approach based on conditional Generative Adversarial Networks (cGAN) and Siamese networks, enhancing the attack capability. We also present a quantitative comparative deep learning-based side-channel analysis between a real raw signal leakage dataset and an artificially augmented leakage dataset. The analysis is performed on the leakage datasets for both symmetric and public-key cryptographic implementations. We investigate non-convergent networks’ effect on the generation of fake leakage signals using two cGAN based deep learning models.

The analysis shows that the proposed data augmentation model results in a well-converged network that generates realistic leakage traces, which can be used to mount deep learning-based side-channel analysis successfully even when the dataset available from the device is not optimal. Our results show that the datasets enhanced with “faked” leakage traces are breakable (while not without augmentation), which might change how we perform deep learning-based side-channel analysis.

The SIDH key exchange is the main building block of SIKE, the only isogeny based scheme involved in the NIST standardization process. In 2016, Galbraith et al. presented an adaptive attack on SIDH. In this attack, a malicious party manipulates the torsion points in his public key in order to recover an honest party’s static secret key, when having access to a key exchange oracle. In 2017, Petit designed a passive attack (which was improved by de Quehen et al. in 2020) that exploits the torsion point information available in SIDH public key to recover the secret isogeny when the endomorphism ring of the starting curve is known.

In this paper, firstly, we generalize the torsion point attacks by de Quehen et al. Secondly, we introduce a new adaptive attack vector on SIDH-type schemes. Our attack uses the access to a key exchange oracle to recover the action of the secret isogeny on larger subgroups. This leads to an unbalanced SIDH instance for which the secret isogeny can be recovered in polynomial time using the generalized torsion point attacks. Our attack is different from the GPST adaptive attack and constitutes a new cryptanalytic tool for isogeny based cryptography. This result proves that the torsion point attacks are relevant to SIDH (Disclaimer: this result is applicable to SIDH-type schemes only, not to SIKE.) parameters in an adaptive attack setting. We suggest attack parameters for some SIDH primes and discuss some countermeasures.

It is well known that already the length of encrypted messages may reveal sensitive information about encrypted data. Fingerprinting attacks enable an adversary to determine web pages visited by a user and even the language and phrases spoken in voice-over-IP conversations.

A Posteriori Openable Public Key Encryptions (APOPKE) allow any user to generate a constant-size key that decrypts the messages they have sent over a chosen period of time. As an important feature, the period can be dynamically chosen after the messages have been sent. This primitive was introduced in 2016 by Bultel and Lafourcade. They also defined the Chosen-Plaintext Attack (CPA) security for APOPKE, and designed a scheme called GAPO, which is CPA secure in the random oracle model. In this paper, we formalize the Chosen-Ciphertext Attack (CCA) security for APOPKE, then we design a scheme called CHAPO (for CHosen-ciphetext attack resistant A Posteriori Openable encryption), and we prove its CCA security in the standard model. CHAPO is approximately twice as efficient as GAPO and is more generic. We also give news applications, and discuss the practical impact of its CCA security.

We propose a Dynamic Universal Accumulator in the Accumulator Manager setting for bilinear groups which extends Nguyen’s positive accumulator and Au et al. [4] and Damgård and Triandopoulos non-membership proof mechanism [20]. The new features include support for batch addition and deletion operations as well as a privacy-friendly batch witness update protocol, where the witness update information is the same for all users. Together with a non-interactive zero-knowledge protocol, these make the proposed scheme suitable as an efficient and scalable Anonymous Credential System, accessible even by low-resource users. We show security of the proposed protocol in the Generic Group Model under a (new) generalized version of the t-SDH assumption and we demonstrate its practical relevance by providing and discussing an implementation realized using state-of-the-art libraries.

Laconic Function Evaluation (LFE) protocols, introduced by Quach et al. in FOCS’18, allow two parties to evaluate functions laconically, in the following manner: first, Alice sends a compressed “digest” of some function – say \(\mathscr {C}\) – to Bob. Second, Bob constructs a ciphertext for his input \( M \) given the digest. Third, Alice, after getting the ciphertext from Bob and in full knowledge of her circuit, can recover \(\mathscr {C}( M )\) and (ideally) nothing more about Bob’s message. The protocol is said to be laconic if the sizes of the digest, common reference string (\(\mathsf {crs}\)) and ciphertext are much smaller than the circuit size \(|\mathscr {C}|\).

Quach et al.  put forward a construction of laconic function evaluation for general circuits under the learning with errors (LWE) assumption (with sub-exponential approximation factors), where all parameters grow polynomially with the depth but not the size of the circuit. Under LWE, their construction achieves the restricted notion of selective security where Bob’s input \( M \) must be chosen non-adaptively before even the \(\mathsf {crs}\) is known.

In this work, we provide the first construction of LFE for \(\mathsf {NC}^1\), which satisfies adaptive security from the ring learning with errors assumption (with polynomial approximation factors). The construction is based on the functional encryption scheme by Agrawal and Rosen (TCC 2017).

In this paper we propose Fasta, a stream cipher design optimised for implementation over popular fully homomorphic encryption schemes. A number of symmetric encryption ciphers have been recently proposed for FHE applications, e.g. the block cipher LowMC, and the stream ciphers Rasta (and variants), FLIP and Kreyvium. The main design criterion employed in these ciphers has typically been to minimise the multiplicative complexity of the algorithm. However, other aspects affecting their efficient evaluation over common FHE libraries are often overlooked, compromising their real-world performance. Whilst Fasta may also be considered as a variant of Rasta, it has its parameters and linear layer especially chosen to allow efficient implementation over the BGV scheme, particularly as implemented in the HElib library. This results in a speedup by a factor of 25 compared to the most efficient publicly available implementation of Rasta. Fasta ’s target is BGV, as implemented in HElib. However the design ideas introduced in the cipher could also be potentially employed to achieve improvements in the homomorphic evaluation in other popular FHE schemes/libraries. We do consider such alternatives in this paper (e.g. BFV and BGVrns, as implemented in SEAL and PALISADE), but argue that, unlike BGV in HElib, it is more challenging to make use of their parallelism in a Rasta-like stream cipher design.

Serpent was originally proposed in 1998 and is one of the most studied block ciphers. In this paper we improve knowledge of its security by providing the current best attack on this cipher, which is a 12-round differential-linear attack with lower data, time and memory complexities than the best previous attacks. Our improvements are based on an improved conditional key guessing technique that exploits the properties of the Sboxes.

This paper proposes Pholkos, a family of heavyweight tweakable block ciphers with state and key sizes of \({\ge }256\) and tweaks of either 128 or 256 bits. When encrypting large chunks of data under the same key, modes with Pholkos do not require “beyond-birthday security” since it provides “bigger birthday security”. This also makes it a good choice for quantum-secure authenticated encryption modes like QCB. Pholkos runs at 1–2 cycles per byte on Intel 6-th generation and more recent, following design principles from Haraka, AESQ, and the TWEAKEY framework. Building on the AES round function not only boosts software performance but also improves security, employing knowledge from two decades of cryptanalysis of the AES.

Multi-signatures are used to attest that a given collection of n parties, indexed by their respective public keys, have all signed a given message. A recent popular application of multi-signatures is to be found in consensus protocols to attest that a qualified subset of a global set of n validators have reached agreement. In this paper, we point out that the traditional security model for multi-signatures is insufficient for this new application, as it assumes that every party in the set participates in every multi-signature computation and that is honest. None of these assumptions hold in the typical adversarial scenarios in consensus protocols (aka. byzantine agreement), where malicious players can launch a denial-of-service attack by injecting malformed individual signatures and cause liveness to halt. We address this by introducing a new multi-signature variant called robust subgroup multi-signatures, whereby any eligible subgroup of signers from the global set can produce a multi-signature on behalf of the group, in the presence of a byzantine adversary. We provide syntax and security definitions thereof and argue that existing unforgeability security proofs for multi-signatures do not carry over to the consensus setting; a consequence of this observation is that many multi-signature based consensus protocols are left lacking a rigorous security proof for correctness. To remediate this we propose several constructions which we prove secure under widely held cryptographic assumptions using our newly introduced formal definitions and also improve upon multi-signature computation time. Finally, we report on benchmarks from a proof-of-concept implementation.