International Association
for Cryptologic Research

This study presents an efficient persistent memory encryption mechanism, named Crystalor, which efficiently realizes a secure persistent/non-volatile memory based on an authentication tree with structural optimization, such as the split counter (SC). Crystalor can completely exploit the advantage of metadata compression techniques, whereas existing mechanisms are incompatible with such optimization. Meanwhile, Crystalor incurs almost no latency overhead under the nominal operation conditions for realizing the crash consistency/recoverability. We implement Crystalor with a state-of-the-art parallelizable authentication tree instance, namely ELM (IEEE TIFS 2022), and evaluate the effectiveness by both algorithmic analyses and system-level simulation in comparison with the existing state-of-the-art ones (e.g., SCUE in HPCA 2023). For protecting a 4 TB memory, Crystalor requires 29–62% fewer clock cycles per memory read/write operation than SCUE owing to the compatibility with the SC. In addition, Crystalor and SCUE require 312GB and 554GB memory overheads for metadata, respectively, which indicates that Crystalor achieves a reduction of memory overhead by 44%. The result of the system-level simulation using the gem5 simulator indicates that Crystalor achieves a reduction of the workload execution time by up to 11.5% from SCUE. Moreover, Crystalor can offer a lazy recovery, which makes recovery several thousand times faster than SCUE.

We show that the Xu et al.'s authentication and key agreement scheme [IEEE Trans. Ind. Informatics, 18(10), 7118-7127, 2022] is flawed. (1) It confused some operations for bilinear maps and presented some inconsistent computations. (2) It failed to keep anonymity, not as claimed. The adversary can use any device's public key stored in the blockchain to test some verification equations so as to reveal the identity of a target device.

The Peregrine signature scheme is one of the candidates in the ongoing Korean post-quantum cryptography competition. It is proposed as a high-speed variant of Falcon, which is a hash-and-sign signature scheme over NTRU lattices and one of the schemes selected by NIST for standardization. To this end, Peregrine replaces the lattice Gaussian sampler in the Falcon signing procedure with a new sampler based on the centered binomial distribution. While this modification offers significant advantages in terms of efficiency and implementation, it does not come with a provable guarantee that signatures do not leak information about the signing key. Unfortunately, lattice-based signature schemes in the hash-and-sign paradigm that lack such a guarantee (such as GGH, NTRUSign or DRS) have generally proved insecure.

In this paper, we show that Peregrine is no exception, by demonstrating a practical key recovery attack against it. We observe that the support of Peregrine signatures is a hidden transformation of some public distribution and still leaks information about the signing key. By adapting the parallelepiped-learning technique of Nguyen and Regev (Eurocrypt 2006), we show that the signing key can be recovered from a relatively small number of signatures. The learning technique alone yields an approximate version of the key, from which we can recover the exact key using a decoding technique due to Thomas Prest (PKC 2023).

For the reference implementation (resp. the official specification version) of Peregrine-512, we fully recover the secret key with good probability in a few hours given around 25,000 (resp. 11 million) signature samples.

In an effort to circumvent the high cost of standard countermeasures against side-channel attacks in post-quantum cryptography, some works have developed low-cost detection-based countermeasures. These countermeasures try to detect maliciously generated input ciphertexts and react to them by discarding the ciphertext or secret key. In this work, we take a look at two previously proposed low-cost countermeasures: the ciphertext sanity check and the decapsulation failure check, and demonstrate successful attacks on these schemes. We show that the first countermeasure can be broken with little to no overhead, while the second countermeasure requires a more elaborate attack strategy that relies on valid chosen ciphertexts. Thus, in this work, we propose the first chosen-ciphertext based side-channel attack that only relies on valid ciphertexts for key recovery. As part of this attack, a third contribution of our paper is an improved solver that retrieves the secret key from linear inequalities constructed using side-channel leakage from the decryption procedure. Our solver is an improvement over the state-of-the-art Belief Propagation solvers by Pessl and Prokop, and later Delvaux. Our method is simpler, easier to understand and has lower computational complexity, while needing less than half the inequalities compared to previous methods.

HQC is a code-based key encapsulation mechanism (KEM) that was selected to move to the fourth round of the NIST post-quantum standardization process. While this scheme was previously targeted by side-channel assisted chosen-ciphertext attacks for key recovery, we notice that all of these attacks use malformed ciphertexts, which can be easily detected since they cause a decapsulation failure. In this case, designers may chose as a countermeasure to refresh the key whenever a failure occurs, making these previous attacks ineffective. In this work, we present the first side-channel assisted chosen-ciphertext attacks using valid ciphertexts which can be carried out in a stealthy manner for key recovery. Our attacks target side-channel leakage from two different operations within the Reed-Muller decoder used for decryption, and can recover the secret key with 100% success rate, even in the presence of errors in side-channel information. All our experiments are performed on the open-source implementation of HQC KEM taken from the pqm4 library, with our attacks validated using both the power and EM side-channel. We also demonstrate novel key recovery attacks which also work on shuffled implementations, and discuss applicability of our attack to masking countermeasures. To the best of our knowledge, we are not aware of a side-channel protected design for HQC KEM, and thus we believe our work stresses the need towards more research on secure and efficient masking and hiding countermeasures for HQC KEM.

Power analysis of public-key algorithms is a well-known approach in the community of side-channel analysis. We usually classify operations based on the differences in power traces produced by different basic operations (such as modular exponentiation) to recover secret information like private keys. The more accurate the segmentation of power traces, the higher the efficiency of their classification. There exist two commonly used methods: one is equidistant segmentation, which requires a fixed number of basic operations and similar trace lengths for each type of operation, leading to limited application scenarios; the other is peak-based segmentation, which relies on personal experience to configure parameters, resulting in insufficient flexibility and poor universality.

In this paper, we propose an automated power trace segmentation method based on reinforcement learning algorithms, which is applicable to a wide range of common implementation of public-key algorithms. Reinforcement learning is an unsupervised machine learning technique that eliminates the need for manual label collection. For the first time, this technique is introduced into the field of side-channel analysis for power trace processing. By using prioritized experience replay optimized Deep Q-Network algorithm, we reduce the number of parameters required to achieve accurate segmentation of power traces to only one, i.e. the key length. We also employ various techniques to improve the segmentation effectiveness, such as clustering algorithm, enveloped-based feature enhancement and fine-tuning method. We validate the effectiveness of the new method in nine scenarios involving hardware and software implementations of different public-key algorithms executed on diverse platforms such as microcontrollers, SAKURA-G, and smart cards. Specifically, one of these implementations is protected by time randomization countermeasures. Experimental results show that our method has good robustness on the traces with varying segment lengths and differing peak heights. After employ the clustering algorithm, our method achieves an accuracy of over 99.6% in operations recovery. Besides, power traces collected from these devices have been uploaded as databases, which are available for researchers engaged in public-key algorithms to conduct related experiments or verify our method.

The Lightning network (LN) addresses Bitcoin’s scalability issues by providing fast and private payment processing. In order to mitigate failures caused by insufficient channel capacities, LN introduced multi-path payments. To the best of our knowledge, the effect of multi-path payments remains unclear. In this paper, we therefore study the impact of multi-path payments on performance and privacy. We identify metrics quantifying the aforementioned properties and utilise them to evaluate the impact of multi-path payments. To this end, we develop a simulator implementing pathfinding in LN using single and multi-path payments as well as various pathfinding algorithms. We find that, while the success rate of multi-path payments is up to 20% higher, the impact of multi-path payments on performance otherwise remains within limits. On the other hand, the impact on privacy appears to be greater, e.g., multi-path payments are more likely to encounter an on-path adversary and the relationship anonymity is more likely to be compromised by colluding intermediate hops. However, multi-path payments are less likely to be deanonymised based on the path lengths.

Lattice reduction algorithms such as BKZ (Block-Korkine-Zolotarev) play a central role in estimating the security of lattice-based cryptography. The subroutine in BKZ which finds the shortest vector in a projected sublattice can be instantiated with enumeration algorithms. The enumeration procedure can be seen as a depth-first search on some ``enumeration tree'' whose nodes denote a partial assignment of the coefficients, corresponding to lattice points as a linear combination of the lattice basis with the coefficients. This work provides a concrete analysis for the cost of quantum lattice enumeration based on Montanaro's quantum tree backtracking algorithm. More precisely, we give a concrete implementation in the quantum circuit model. We also show how to optimize the circuit depth by parallelizing the components. Based on the circuit designed, we discuss the concrete quantum resource estimates required for lattice enumeration.

We present staircase attack, the first attack on the incentive mechanism of the Proof-of-Stake (PoS) protocol used in Ethereum 2.0 beacon chain. Our attack targets the penalty of the incentive mechanism that penalizes inactive participation. Our attack can make honest validators suffer from penalties, even if they strictly follow the specification of the protocol. We show both theoretically and experimentally that if the adversary controls 29.6% stake in a moderate-size system, the attack can be launched continuously, so eventually all honest validators will lose their incentives. In contrast, the adversarial validators can still receive incentives, and the stake owned by the adversary can eventually exceed the $1/3$ threshold (system assumption), posing a threat to the security properties of the system.

In practice, the attack feasibility is directly related to two parameters: the number of validators and the parameter MAX_ATTESTATION, the maximum number of attestations (i.e., votes) that can be included in each block. We further modify our attack such that, with current system setup (850,000 validators and MAX_ATTESTATION=128), our attack can be launched continuously with a probability of 80.25%. As a result, the incentives any honest validator receives are only 28.9% of its fair share.

Digital signatures are a cornerstone of security and trust in cryptography, providing authenticity, integrity, and non-repudiation. Despite their benefits, traditional digital signature schemes suffer from inherent immutability, offering no provision for a signer to retract a previously issued signature. This paper introduces the concept of a withdrawable signature scheme, which allows for the retraction of a signature without revealing the signer's private key or compromising the security of other signatures the signer created before. This property, defined as ``withdrawability'', is particularly relevant in decentralized systems, such as e-voting, blockchain-based smart contracts, and escrow services, where signers may wish to revoke or alter their commitment.

The core idea of our construction of a withdrawable signature scheme is to ensure that the parties with a withdrawable signature are not convinced whether the signer signed a specific message. This ability to generate a signature while preventing validity from being verified is a fundamental requirement of our scheme, epitomizing the property of withdrawability. After formally defining security notions for withdrawable signatures, we present two constructions of the scheme based on the pairing and the discrete logarithm. We provide proofs that both constructions are unforgeable under insider corruption and satisfy the criteria of withdrawability. We anticipate our new type of signature will significantly enhance flexibility and security in digital transactions and communications.

One-way functions are central to classical cryptography. They are both necessary for the existence of non-trivial classical cryptosystems, and sufficient to realize meaningful primitives including commitments, pseudorandom generators and digital signatures. At the same time, a mounting body of evidence suggests that assumptions even weaker than one-way functions may suffice for many cryptographic tasks of interest in a quantum world, including bit commitments and secure multi-party computation.

This work studies one-way state generators [Morimae-Yamakawa, CRYPTO 2022], a natural quantum relaxation of one-way functions. Given a secret key, a one-way state generator outputs a hard to invert quantum state. A fundamental question is whether this type of quantum one-wayness suffices to realize quantum cryptography. We obtain an affirmative answer to this question by proving that one-way state generators with pure state outputs imply quantum bit commitments and secure multiparty computation.

Along the way, we build an intermediate primitive with classical outputs, which we call a (quantum) one-way puzzle. Our main technical contribution is a proof that one-way puzzles imply quantum bit commitments.

Private Information Retrieval (PIR) facilitates the retrieval of database entries by a client from a remote server without revealing which specific entry is being queried. The preprocessing model has emerged as a significant technique for constructing efficient PIR systems, allowing parties to execute a one-time, query-independent offline phase, and then a fast online retrieval phase. In particular, Corrigan-Gibbs and Kogan (EUROCRYPT 2020) presented a new framework for constructing PIR with sublinear online time. Nevertheless, their protocol is deemed impractical in the single-server setting due to the heavy use of Fully Homomorphic Encryption (FHE). More recently, two state-of-the-art (SOTA) single-server PIR protocols (Zhou et al., S&P 2024 and Mughees-Ren, ePrint 2023) have eliminated FHE, at the price of linear offline communication. However, the client-side storage is still relatively large ($\tilde{O}(\sqrt{n})$), which poses challenges to practical deployment, especially when the client has limited computation and storage capabilities. To address such limitation, we propose a novel PIR protocol Pai, which only requires constant online time, communication, and client-side storage. The price we pay is only a $1$ - $5\times$ increase in offline communication, which would be acceptable since it is a one-time cost.Building upon our Pai, we also present a Symmetric KPIR (KSPIR) PaiKSPIR and a Chargeable KSPIR (CKSPIR) PaiCKSPIR. These two variants of PIR offer enhanced functionalities while maintaining computational complexities similar to the original Pai.

In addition to providing rigorous theoretical proofs of correctness and privacy for Pai, we have undertaken comprehensive protocol implementations and conducted extensive experiments to validate their high efficiency. Our empirical findings demonstrate that our protocols achieve notably higher online efficiency than SOTA protocols, e.g., Pai exhibits $8.8$ - $91.8\times$ better online communication cost and $2.5$ - $8.8\times$ better online time. Given the superior online time and storage, our protocol is well-suited for practical deployment.

Finding isogenies between supersingular elliptic curves is a natural algorithmic problem which is known to be equivalent to computing the curves' endomorphism rings. When the isogeny is additionally required to have a specific degree $d$, the problem appears to be somewhat different in nature, yet it is also considered a hard problem in isogeny-based cryptography. Let $E_1,E_2$ be supersingular elliptic curves over $\mathbb{F}_{p^2}$. We present improved classical and quantum algorithms that compute an isogeny of degree $d$ between $E_1$ and $E_2$ if it exists. Let the sought-after degree be $d = p^{1/2+ \epsilon}$ for some $\epsilon>0$. Our essentially memory-free algorithms have better time complexity than meet-in-the-middle algorithms, which require exponential memory storage, in the range $1/2\leq\epsilon\leq 3/4$ on a classical computer and quantum improvements in the range $0<\epsilon<5/2$.

The Number Theoretic Transform (NTT) is a powerful mathematical tool with a wide range of applications in various fields, including signal processing, cryptography, and error correction codes. In recent years, there has been a growing interest in efficiently implementing the NTT on hardware platforms for lattice-based cryptography within the context of NIST's Post-Quantum Cryptography (PQC) competition. The implementation of NTT in cryptography stands as a pivotal advancement, revolutionizing various security protocols. By enabling efficient arithmetic operations in polynomial rings, NTT significantly enhances the speed and security of lattice-based cryptographic schemes, contributing to the development of robust homomorphic encryption, key exchange, and digital signature systems.

This article presents a new implementation of the Number Theoretic Transform for FPGA platforms. The focus of the implementation lies in achieving a flexible trade-off between resource usage and computation speed. By strategically adjusting the allocation of BRAM and DSP resources, the NTT computation can be optimized for either high-speed processing or resource conservation. The proposed implementation is specifically designed for polynomial multiplication with a degree of 256, accommodating coefficients of various bit sizes. Furthermore, the constant-geometry (Pease) method was utilized as an alternative to the Cooley-Tukey graph method, resulting in a notable simplification of BRAM addressing procedures. This adaptability renders it suitable for cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber, which use 256-degree polynomials.

Internet voting systems are supposed to meet the same high standards as traditional paper-based systems when used in real political elections: freedom of choice, universal and equal suffrage, secrecy of the ballot, and independent verifiability of the election result. Although numerous Internet voting systems have been proposed to achieve these challenging goals simultaneously, few come close in reality.

We propose a novel publicly verifiable and practically efficient Internet voting system, DeVoS, that advances the state of the art. The main feature of DeVoS is its ability to protect voters' freedom of choice in several dimensions. First, voters in DeVoS can intuitively update their votes in a way that is deniable to observers but verifiable by the voters; in this way voters can secretly overwrite potentially coerced votes. Second, in addition to (basic) vote privacy, DeVoS also guarantees strong participation privacy by end-to-end hiding which voters have submitted ballots and which have not. Finally, DeVoS is fully compatible with Perfectly Private Audit Trail, a state-of-the-art Internet voting protocol with practical everlasting privacy. In combination, DeVoS offers a new way to secure free Internet elections with strong and long-term privacy properties.

We introduce the Order vs. Chaos (OvC) classifier, a novel language-model approach for side-channel attacks combining the strengths of multitask learning (via the use of a language model), multimodal learning, and deep metric learning. Our methodology offers a viable substitute for the multitask classifiers used for learning multiple targets, as put forward by Masure et al. We highlight some well-known issues with multitask classifiers, like scalability, balancing multiple tasks, slow learning, large model sizes, and the need for complex hyperparameter tuning. Thus, we advocate language models in side-channel attacks.

We demonstrate improvements in results on different variants of ASCAD-V1 and ASCAD-V2 datasets compared to the existing state-of-the-art results. Additionally, we delve deeper with experiments on protected simulated datasets, allowing us to control noise levels and simulate specific leakage models. This exploration facilitates an understanding of the ramifications when the protective scheme's masks do not leak and allows us to further compare our approach with other approaches. Furthermore, with the help of unprotected simulated datasets, we demonstrate that the OvC classifier, uninformed of the leakage model, can parallelize the proficiency of a conventional multi-class classifier that is leakage model-aware. This finding implies that our methodology sidesteps the need for predetermined a leakage model in side-channel attacks.

Isogeny computations in CSIDH (Asiacrypt 2018) are described using a commutative group G acting on the set of supersingular elliptic curves. The commutativity property gives CSIDH enough flexibility to allow the creation of many cryptographic primitives and protocols. Nevertheless, these operations are limited and more complex applications have not yet been proposed.

When calling the composition of two group elements of G addition, our goal in this work is to explore exponentiation, multiplication with public elements, and multiplication between secret elements of this group. We first introduce a two-party interactive protocol for multiplication of secret group elements. Then, we explore zero-knowledge proofs of these different arithmetic operations. We present two types of approaches, using either standard sigma protocols or the MPC-in-the-Head paradigm. Most of our proofs need a trusted setup, which can be removed in the MPC-in-the-Head setting using cut-and-choose techniques. We conclude this work by presenting an oblivious pseudorandom function based on our new framework, that is competitive with current state-of-the-art designs.

Tightly secure cryptographic schemes can be implemented with standardized parameters, while still having a sufficiently high security level backed up by their analysis. In a recent work, Pan and Wagner (Eurocrypt 2023) presented the first tightly secure two-round multi-signature scheme without pairings, called Chopsticks. While this is an interesting first theoretical step, Chopsticks is much less efficient than its non-tight counterparts.

In this work, we close this gap by proposing a new tightly secure two-round multi-signature scheme that is as efficient as non-tight schemes. Our scheme is based on the DDH assumption without pairings. Compared to Chopsticks, we reduce the signature size by more than a factor of 3 and the communication complexity by more than a factor of 2.

Technically, we achieve this as follows: (1) We develop a new pseudorandom path technique, as opposed to the pseudorandom matching technique in Chopsticks. (2) We construct a more efficient commitment scheme with suitable properties, which is an important primitive in both our scheme and Chopsticks. Surprisingly, we observe that the commitment scheme does not have to be binding, enabling our efficient construction.

Ethereum is a decentralized and permissionless network offering several attractive features. However, block proposers in Ethereum can exploit the order of transactions to extract value. This phenomenon, known as maximal extractable value (MEV), not only disrupts the optimal functioning of different protocols but also undermines the stability of the underlying consensus mechanism.

In this work, we present a new method to alleviate the MEV problem by separating transaction inclusion and execution, keeping transactions encrypted before execution. We formulate the notion of multiparty delay encryption (MDE) and construct a practical MDE scheme based on time-lock puzzles. Unlike other encryption-based methods, our method excels in scalability (in terms of transaction decryption), efficiency (minimizing communication and storage overhead), and security (with minimal trust assumptions). To demonstrate the effectiveness of our MDE scheme, we have implemented it on a local Ethereum testnet. We also prove that with the presence of just one honest attestation aggregator per slot, the MEV threat can be significantly mitigated in a practical way.

Goldwasser-Kalai-Rothblum protocol (GKR) for layered circuits is a sumcheck-based argument of knowledge for layered circuits, running in $\sim 2\mu \ell$ amount of rounds, where $\ell$ is the amount of layers and $\mu$ is the average layer logsize.

For a layer $i$ of size $2^{\mu_i}$ the main work consists of running a sumcheck protocol of the form \[\underset{x,y}{\sum} \text{Add}_i(x,y,z)(f(x)+f(y)) + \text{Mul}_i(x,y,z)f(x)f(y)\] over a $2^{2\mu_i}$-dimensional cube, where $\text{Add}_i(x,y,z)$ and $\text{Mul}_i(x,y,z)$ are (typically relatively sparse) polynomials called "wiring predicates".

We present a different approach, based on the (trivial) observation that multiplication can be expressed through linear operations and squaring. This leads to the different wiring, which is marginally more efficient even in a worst-case scenario, and decreases the amount of communication $\sim 2 \times$ in the case where wiring predicates are sparse.