International Association
for Cryptologic Research

The CKKS scheme is traditionally recognized for approximate homomorphic encryption of real numbers, but BLEACH (Drucker et al., JoC 2024) extends its capabilities to handle exact computations on binary or small integer numbers.Despite this advancement, BLEACH’s approach of simulating XOR gates via (a−b)2 incurs one multiplication per gate, which is computationally expensive in homomorphic encryption. To this end, we introduce XBOOT, a new framework built upon BLEACH’s blueprint but allows for almost free evaluation of XOR gates. The core concept of XBOOT involves lazy reduction, where XOR operations are simulated with the less costly addition operation, a+b, leaving the management of potential overflows to later stages. We carefully handle the modulus chain and scale factors to ensure that the overflows are managed during the CKKS bootstrapping phase, preserving the correct XOR result without extra cost. We use AES-CKKS transciphering as a benchmark to test the capability of XBOOT, and achieve a throughput exceeding one kilobyte per second, which represents a 2.5x improvement over the state-of-the-art (Aharoni et al., HES 2023). Moreover, XBOOT enables the practical execution of tasks with extensive XOR operations that were previously challenging for CKKS. For example, we can do Rasta-CKKS transciphering at over two kilobytes per second, more than 10x faster than the baseline without XBOOT.

The machine learning problem of model extraction was first introduced in 1991 and gained prominence as a cryptanalytic challenge starting with Crypto 2020. For over three decades, research in this field has primarily focused on ReLU-based neural networks. In this work, we take the first step towards the cryptanalytic extraction of PReLU neural networks, which employ more complex nonlinear activation functions than their ReLU counterparts. We propose a raw output-based parameter recovery attack for PReLU networks and extend it to more restrictive scenarios where only the top-m probability scores are accessible. Our attacks are rigorously evaluated through end-to-end experiments on diverse PReLU neural networks, including models trained on the MNIST dataset. To the best of our knowledge, this is the first practical demonstration of the PReLU neural network extraction across three distinct attack scenarios.

The machine learning problem of extracting neural network parameters has been proposed for nearly three decades. Functionally equivalent extraction is a crucial goal for research on this problem. When the adversary has access to the raw output of neural networks, various attacks, including those presented at CRYPTO 2020 and EUROCRYPT 2024, have successfully achieved this goal. However, this goal is not achieved when neural networks operate under a hard-label setting where the raw output is inaccessible. In this paper, we propose the first attack that theoretically achieves functionally equivalent extraction under the hard-label setting, which applies to ReLU neural networks. The effectiveness of our attack is validated through practical experiments on a wide range of ReLU neural networks, including neural networks trained on two real benchmarking datasets (MNIST, CIFAR10) widely used in computer vision. For a neural network consisting of $10^5$ parameters, our attack only requires several hours on a single core.

The differential-linear attack is one of the most effective attacks against ARX ciphers. However, two technical problems are preventing it from being more effective and having more applications: (1) there is no efficient method to search for good differential-linear approximations. Existing methods either have many constraints or are currently inefficient. (2) partitioning technique has great potential to reduce the time complexity of the key-recovery attack, but there is no general tool to construct partitions for ARX ciphers. In this work, we step forward in solving the two problems. First, we propose a novel idea for generating new good differential-linear approximations from known ones, based on which new searching algorithms are designed. Second, we propose a general tool named partition tree, for constructing partitions for ARX ciphers. Based on these new techniques, we present better attacks for two ISO/IEC standards, i.e., LEA and Speck. For LEA, we present the first 17-round distinguisher which is 1 round longer than the previous best distinguisher. Furthermore, we present the first key recovery attacks on 17-round LEA-128, 18-round LEA-192, and 18-round LEA-256, which attack 3, 4, and 3 rounds more than the previous best attacks. For Speck, we find better differential-linear distinguishers for Speck48 and Speck64. The first differential-linear distinguishers for Speck96 and Speck128 are also presented.