IACR Communications in Cryptology
Not a member yet
283 research outputs found
Sort by
EWEMrl: A White-Box Secure Cipher with Longevity
Full text linkWe propose the first updatable white-box secure cipher, EWEMrl, and its natural extension EWEMxl, both achieving longevity against non-adaptive read-only malware. The notion of longevity, introduced by Koike et al., addresses continuous code leakage and is stronger than incompressibility. While Yoroi claimed longevity, but was broken by Isobe and Todo. Given the prevalence of continuous leakage, developing such ciphers is crucial in white-box cryptography. Precisely, we have the following. We first present EWEMr (Extended WEM against non-adaptive read-only adversaries), a generalization of WEM (White-box Even-Mansour). WEM is the first (and possibly only) white-box cipher based on EM, replacing its key addition layer with a secret Sbox. EWEMr achieves a high space-hardness bound in the non-adaptive model, with a new generic proof strategy, but does not provide longevity. Instead, it serves as the base for EWEMrl. We also present EWEMx, which uses EWEMr as subroutines and achieves a high space-hardness bound in the stronger adaptive model. While EWEMx does not achieve longevity, it is the base design for EWEMxl. We next propose EWEMrl, that achieves longevity against non-adaptive read-only malware. None of the existing ciphers, such as SPNbox and SPACE, is designed for longevity. We show that EWEMrl ensures (against non-adaptive read-only adversaries) (1) longevity, (2) high space-hardness in both known-space and chosen-space settings, and (3) security against hybrid code-lifting attacks. Finally, we introduce EWEMxl, a natural extension of EWEMrl with a structure similar to EWEMx. EWEMxl achieves (2) and (3) in the stronger adaptive model while maintaining (1) in the same non-adaptive and read-only setting. In summary, our proposals EWEMrl and EWEMxl provide longevity against non-adaptive read-only malware while ensuring security confidence in the black-box setting. </p
Quantum pseudoresources imply cryptography
Full text linkWhile one-way functions (OWFs) serve as the minimal assumption for computational cryptography in the classical setting, in quantum cryptography, we have even weaker cryptographic assumptions such as pseudo-random states, and EFI pairs, among others. Moreover, the minimal assumption for computational quantum cryptography remains an open question. Recently, it has been shown that pseudoentanglement is necessary for the existence of quantum cryptography (Goulão and Elkouss 2024), but no cryptographic construction has been built from it.In this work, we study the cryptographic usefulness of quantum pseudoresources—a pair of families of quantum states that exhibit a gap in their resource content yet remain computationally indistinguishable. We show that quantum pseudoresources imply a variant of EFI pairs, which we call EPFI pairs, and that these are equivalent to quantum commitments and thus EFI pairs. Our results suggest that, just as randomness is fundamental to classical cryptography, quantum resources may play a similarly crucial role in the quantum setting.Finally, we focus on the specific case of entanglement, analyzing different definitions of pseudoentanglement and their implications for constructing EPFI pairs. Moreover, we propose a new cryptographic functionality that is intrinsically dependent on entanglement as a resource. </p
Mobile Cell-Based Road Pricing with Verifiable User Privacy
Full text link We present a novel road pricing protocol which, unlike existing solutions, provides verifiable privacy guarantees to users without requiring any dedicated hardware. Instead, our protocol makes use of the GNSS capabilities of users\u27 cell phones to track their travel history. This makes it a cost-effective and accessible solution to pay-per-use road pricing. The novelty of our approach lies in the use of a hybrid cryptosystem to ensure user privacy. Specifically, the service provider divides the monitored area into cells, assigning each a key. Some keys are genuine public keys with known private keys, while others are hash outputs designed to appear identical to the real keys, making it impossible for users to distinguish between them. As users travel, their data is encrypted with these keys before being shared. The service provider is therefore only able to decrypt data encrypted with real keys, allowing for random checking. At the end of the protocol, the provider shares the preimages of the hash outputs with the users, proving non-knowledge of the associated private keys. We evaluate our protocol\u27s security and show that it provides resistance to misbehaving users, dishonest service providers, and third-party listeners. Additionally, we instantiate our protocol using ElGamal encryption and the SHA-256 hash function, and provide a proof-of-concept implementation with benchmarking results. </p
Non-Profiled Higher-Order Side-Channel Attacks against Lattice-Based Post-Quantum Cryptography
Full text link In this work, we present methods for conducting higher-order non-profiled side-channel attacks on Lattice-Based Cryptography (LBC). Our analysis covers two scenarios: one where the device leakage is known and follows Hamming weight model, and another where the leakage model is not Hamming weight based and unknown to the attacker. We focus on the Post-Quantum Cryptography (PQC) standards, the Dilithium digital signature (i.e. ML-DSA) and the Kyber key encapsulation (i.e. ML-KEM) algorithms. For Hamming weight leakage, we develop efficient higher-order Correlation Power Analysis (HOCPA) attacks in which the attacker must compute a function known as the optimal prediction function. We revisit the definition of optimal prediction function and introduce a recursive method for computing it efficiently. Our approach is particularly useful when a closed-form formula is unavailable, as in LBC. Then, we introduce sin and cos prediction functions, which prove optimal for HOCPA attacks against second and higher-order masking protection. We validate our methods through simulations and real-device experiments on open-source masked implementations of Dilithium and Kyber on an Arm Cortex-M4. On the real device, we achieve full secret-key recovery using only 700 and 2400 traces for second and third-order masked implementations of Dilithium, and 2200 and 14500 traces for second and third-order masked implementations of Kyber, respectively. For the unknown leakage scenarios, we leverage generic Side-Channel Analysis (SCA) distinguishers. A key challenge here is the injectivity of modular multiplications in NTT based polynomial multiplication, typically addressed by bit-dropping in the literature. However, we experimentally show that bit-dropping is largely inefficient against protected implementations of LBC. To overcome this limitation, we present a novel two-step attack to Kyber, combining generic distinguishers and lattice reduction techniques. Our approach decreases the number of predictions from q^2 to q and does not rely on bit-dropping. Our experimental results demonstrate a speed-up of up to 23490x in attack run-time over the baseline along with improved success rate. In certain scenarios, higher-order attacks become feasible only through the proposed approach, as classical methods are shown to be unsuccessful. </p
FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism
Full text link Large-scale quantum computers capable of implementing Shor\u27s algorithm pose a significant threat to the security of the most widely used public-key cryptographic schemes. This risk has motivated substantial efforts by standards bodies and government agencies to identify and standardize quantum-safe cryptographic systems. Among the proposed solutions, lattice-based cryptography has emerged as the foundation for some of the most promising protocols. This paper describes FrodoKEM, a family of conservative key-encapsulation mechanisms (KEMs) whose security is based on generic, “unstructured” lattices. FrodoKEM is proposed as an alternative to the more efficient lattice schemes that utilize algebraically structured lattices, such as the recently standardized ML-KEM scheme. By relying on generic lattices, FrodoKEM minimizes the potential for future attacks that exploit algebraic structures while enabling simple and compact implementations. Our plain C implementations demonstrate that, despite its conservative design and parameterization, FrodoKEM remains practical. For instance, the full protocol at NIST security level 1 runs in approximately 0.97 ms on a server-class processor, and 4.98 ms on a smartphone-class processor. FrodoKEM obtains (single-target) IND-CCA security using a variant of the Fujisaki-Okamoto transform, applied to an underlying public-key encryption scheme called FrodoPKE. In addition, using a new tool called the Salted Fujisaki-Okamoto (SFO) transform, FrodoKEM is also shown to tightly achieve multi-target security, without increasing the FrodoPKE message length and with a negligible performance impact, based on the multi-target IND-CPA security of FrodoPKE. </p
Standard Model Signatures from Dual Identification Schemes
Full text link In this paper we introduce dual tag-based identification () schemes. Inspired by a recent signature scheme by Chevallier-Mames, we present a general transformation that converts schemes into signature schemes via parallel-OR proofs and the Fiat-Shamir transformation. The security of this approach does not rely on the random oracle model; it only requires the hash function to be correlation intractable relative to some simple function . We present two instantiations of schemes: one that explains the Chevallier-Mames signature scheme, which is based on the -Strong Diffie-Hellman assumption, and another that relies on a slightly weaker assumption, the -Diffie-Hellman assumption. </p
Construction of Hadamard-based MixColumns Matrices Resistant to Related-Differential Cryptanalysis
Full text link In this paper, we study MDS matrices that are specifically designed to prevent the occurrence of related differentials. We investigate MDS matrices with a Hadamard structure and demonstrate that it is possible to construct 4 X 4 Hadamard matrices that effectively eliminate related differentials. Incorporating these matrices into the linear layer of AES-like block-ciphers/hash functions significantly mitigates the attacks that exploit the related differentials property. The central contribution of this paper is to identify crucial underlying relations that determine whether a given 4 X 4 Hadamard matrix exhibits related differentials. By satisfying these relations, the matrix ensures the presence of related differentials, whereas failing to meet them leads to the absence of such differentials. This offers effective mitigation of recently reported attacks on reduced-round AES. Furthermore, we propose a faster search technique to exhaustively verify the presence or absence of related differentials in 8 X 8 Hadamard matrices over finite field of characteristic 2 which requires checking only a subset of involutory matrices in the set. Although most existing studies on constructing MDS matrices primarily focus on lightweight hardware/software implementations, our research additionally introduces a novel perspective by emphasizing the importance of MDS matrix construction in relation to their resistance against differential cryptanalysis. </p
Breaking BASS
Full text link We provide several attacks on the BASS signature scheme introduced by Grigoriev, Ilmer, Ovchinnikov and Shpilrain in 2023. We lay out a trivial forgery attack which generates signatures passing the scheme\u27s probabilistic signature verification with high probability. Generating these forgeries is faster than generating signatures honestly. Moreover, we describe a key-only attack which allows us to recover an equivalent private key from a signer\u27s public key. The time complexity of this recovery is asymptotically the same as that of signing messages. </p
Unsupervised Horizontal Attacks against Public-Key Primitives with DCCA - From Deep Canonical Correlation Analysis to Deep Collision Correlation Attacks -
Full text link In order to protect against side-channel attacks, masking countermeasure is widely considered. Its application on asymmetric cryptographic algorithms, such as RSA implementations, rendered multiple traces aggregation inefficient and led to the development of single trace horizontal attacks. Among these horizontal attacks proposed in the literature, many are based on the use of clustering techniques or statistical distinguishers to identify operand collisions. These attacks can be difficult to implement in practice, as they often require advanced trace pre-processing, including the selection of points of interest, a step that is particularly complex to perform in a non-profiling context. In recent years, numerous studies have shown the effectiveness of deep learning in security evaluation for conducting side-channel attacks. However, few attentions have been given to its application in asymmetric cryptography and horizontal attack scenarios. Additionally, the majority of deep learning attacks tend to focus on profiling attacks, which involve a supervised learning phase. In this paper, we propose a new non-profiling horizontal attack using an unsupervised deep learning method called Deep Canonical Correlation Analysis. In this approach, we propose to use a siamese neural network to maximize the correlation between pairs of modular operation traces through canonical correlation analysis, projecting them into a highly correlated latent space that is more suitable for identifying operand collisions. Several experimental results, on simulated traces and a protected RSA implementation with up-to-date countermeasures, show how our proposal outperformed state-of-the-art attacks despite being simpler to implement. This suggests that the use of deep learning can be impactful for security evaluators, even in a non-profiling context and in a fully unsupervised way. </p
Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption
Full text linkPlaintext-ciphertext matrix multiplication (PC-MM) is an indispensable tool in privacy-preserving computations such as secure machine learning and encrypted signal processing. While there are many established algorithms for plaintext-plaintext matrix multiplication, efficiently computing plaintext-ciphertext (and ciphertext-ciphertext) matrix multiplication is an active area of research which has received a lot of attention. Recent literature have explored various techniques for privacy-preserving matrix multiplication using fully homomorphic encryption (FHE) schemes with ciphertext packing and Single Instruction Multiple Data (SIMD) processing. On the other hand, there hasn\u27t been any attempt to speed up PC-MM using unpacked additively homomorphic encryption (AHE) schemes beyond the schoolbook method and Strassen\u27s algorithm for matrix multiplication. In this work, we propose an efficient PC-MM from unpacked AHE, which applies Cussen\u27s compression-reconstruction algorithm for plaintext-plaintext matrix multiplication in the encrypted setting. We experimentally validate our proposed technique using a concrete instantiation with the additively homomorphic elliptic curve ElGamal encryption scheme and its software implementation on a Raspberry Pi 5 edge computing platform. Our proposed approach achieves up to an order of magnitude speedup compared to state-of-the-art for large matrices with relatively small element bit-widths. Extensive measurement results demonstrate that our fast PC-MM is an excellent candidate for efficient privacy-preserving computation even in resource-constrained environments. </p