International Association
for Cryptologic Research

Key Encapsulation Mechanisms (KEMs) are a critical building block for hybrid encryption and modern security protocols, notably in the post-quantum setting. Given the asymmetric public key of a recipient, the primitive establishes a shared secret key between sender and recipient. In recent years, a large number of abstract designs and concrete implementations of KEMs have been proposed, notably in the context of the NIST selection process for post-quantum primitives. The traditional security notion for KEMs has been the IND-CCA notion that was designed for public-key encryption (PKE). In recent work additional properties, such as robustness and anonymity, were lifted from the PKE setting to the KEMs setting.

In this work we introduce several stronger security notions for KEMs. Our new properties formalize in which sense outputs of the KEM uniquely determine, i.e., bind, other values. Our new notions are based on two orthogonal observations: First, unlike PKEs, KEMs establish a unique key, which leads to natural binding properties for the established keys. Our new binding properties can be used, e.g., to prove the absence of attacks that were not captured by prior security notions, such as re-encapsulation attacks. If we regard KEMs as one-pass key exchanges, our key-binding properties correspond to implicit key agreement properties. Second, to prove the absence of weak keys, we have to consider not only honestly generated key pairs but also adversarially-generated key pairs.

We define a hierarchy of security notions for KEMs based on our observations. We position properties from the literature within our hierarchy, provide separating examples, and give examples of real world KEMs in the context of our hierarchy.

In recent years, actively secure SPDZ-like protocols for dishonest majority, like SPD$\mathbb Z_{2^k}$, Overdrive2k, and MHz2k, over base rings $\mathbb Z_{2^k}$ have become more and more efficient. In this paper, we present a new actively secure MPC protocol Multipars that outperforms these state-of-the-art protocols over $\mathbb Z_{2^k}$ by more than a factor of 2 in the two-party setup in terms of communication. Multipars is the first actively secure N-party protocol over $\mathbb Z_{2^k}$ that is based on linear homomorphic encryption (LHE) in the offline phase (instead of oblivious transfer or somewhat homomorphic encryption in previous works). The strong performance of Multipars relies on a new adaptive packing for BGV ciphertexts that allows us to reduce the parameter size of the encryption scheme and the overall communication cost. Additionally, we use modulus switching for further size reduction, a new type of enhanced CPA security over $\mathbb Z_{2^k}$, a truncation protocol for Beaver triples, and a new LHE-based offline protocol without sacrificing over $\mathbb Z_{2^k}$.

We have implemented Multipars and therewith provide the fastest preprocessing phase over $\mathbb Z_{2^k}$. Our evaluation shows that Multipars offers at least a factor of 8 lower communication costs and up to a factor of 15 faster runtime in the WAN setting compared to the currently best available actively secure MPC implementation over $\mathbb Z_{2^k}$.

We present a side-channel attack on CRYSTALS-Dilithium, a post-quantum secure digital signature scheme, with two variants of post-processing. The side-channel attack exploits information leakage in the secret key unpacking procedure of the signing algorithm to recover the coefficients of the polynomials in the secret key vectors ${\bf s}_1$ and ${\bf s}_2$ by profiled deep learning-assisted power analysis. In the first variant, one half of the coefficients of ${\bf s}_1$ and ${\bf s}_2$ is recovered by power analysis and the rest is derived by solving a system of linear equations based on ${\bf t} = {\bf A}{\bf s}_1 + {\bf s}_2$, where ${\bf A}$ and ${\bf t}$ are parts of the public key. This case assumes knowledge of the least significant bits of the vector ${\bf t}$, ${\bf t}_0$. The second variant waives this requirement. However, to succeed, it needs a larger portion of ${\bf s}_1$ to be recovered by power analysis. The remainder of ${\bf s}_1$ is obtained by lattice reduction. Once the full ${\bf s}_1$ is recovered, all the other information necessary for generating valid signatures can be trivially derived from the public key. We evaluate both variants on an ARM Cortex-M4 implementation of Dilithium-2. The profiling stage (trace capture and neural network training) takes less than 10 hours. In the attack assuming that ${\bf t}_0$ is known, the probability of successfully recovering the full vector ${\bf s}_1$ from a single trace captured from a different from profiling device is non-negligible (9%). The success rate approaches 100% if multiple traces are available for the attack. Our results demonstrate the necessity of protecting the secret key of CRYSTALS-Dilithium from single-trace attacks and call for a reassessment of the role of compression of the public key vector ${\bf t}$ in the security of CRYSTALS-Dilithium implementations.

This paper studies a multi-party private set union (mPSU), a fundamental cryptographic problem that allows multiple parties to compute the union of their respective datasets without revealing any additional information. We propose an efficient mPSU protocol which is secure in the presence of any number of colluding semi-honest participants. Our protocol avoids computationally expensive homomorphic operations or generic multi-party computation, thus providing an efficient solution for mPSU.

The crux of our protocol lies in the utilization of new cryptographic tools, namely, Membership Oblivious Transfer (mOT) and Conditional Oblivious Pseudorandom Function (cOPRF). We believe that the mOT and cOPRF may be of independent interest.

We implement our mPSU protocol and evaluate their performance. Our protocol shows an improvement of up to $55\times$ and $776.18\times$ bandwidth cost compared to the existing state-of-the-art protocols.

We study the following broad question about cryptographic primitives: is it possible to achieve security against an arbitrary $\mathsf{poly}(n)$-time adversary with $O(\log n)$-size messages? It is common knowledge that the answer is ``no'' unless information-theoretic security is possible. In this work, we revisit this question by considering the setting of cryptography with public information and computational security.

We obtain the following results, assuming variants of well-studied intractability assumptions:

1) A private simultaneous messages (PSM) protocol for every $f:[n]\times[n]\to\{0, 1\}$ requiring $(1+\epsilon)\log n$-bit messages for most functions and $(2+\epsilon)\log n$-bit messages for the remaining ones. We apply this towards non-interactive secure 3-party computation with similar message size in the preprocessing model, improving over previous 2-round protocols.

2) A secret-sharing scheme for any ``forbidden-graph'' access structure on $n$ nodes with $O(\log n)$ share size.

3) On the negative side, we show that computational threshold secret-sharing schemes with public information require share size $\Omega(\log \log n)$. For arbitrary access structures, we show that computational security does not help with 1-bit shares.

The above positive results guarantee that any adversary of size $n^{o(\log n)}$ achieves an $n^{-\Omega(1)}$ distinguishing advantage. We show how to make the advantage negligible by slightly increasing the asymptotic message size, still improving over all known constructions. The security of our constructions is based on the conjectured hardness of variants of the planted clique problem, which was extensively studied in the algorithms, statistical inference, and complexity theory communities. Our work provides the first applications of such assumptions improving the efficiency of mainstream cryptographic primitives, gives evidence for the necessity of such assumptions, and suggests new questions in this domain that may be of independent interest.

Recently, a novel secure quantum bit commitment (QBC) protocol has been proposed [29]. However, the protocol requires Alice and Bob to share Bell states in advance, making the protocol lacking in practicality. In this paper, we propose two new unconditionally secure quantum bit commitment protocols that do not require pre-shared Bell states based on entangled and non-entangled states, respectively. Their security stems from quantum mechanical properties such as quantum superposition, quantum entanglement, no-cloning theorem, and no-communication theorem. Furthermore, by combining the proposed QBC with Yao's quantum oblivious transfer (QOT) model, we can obtain an unconditionally secure QOT protocol.

A file system provides secure deletion if, after a file is deleted, an attacker with physical possession of the storage device cannot recover any data from the deleted file. Unfortunately, secure deletion is not provided by commodity file systems. Even file systems which explicitly desire to provide secure deletion are challenged by the subtleties of hardware controllers on modern storage devices; those controllers obscure the mappings between logical blocks and physical blocks, silently duplicate physical blocks, and generally make it hard for host-level software to make reliable assumptions about how file data is kept on the device. State-of-the-art frameworks for secure deletion also have no crash consistency, meaning that an ill-timed power outage or software fault will desynchonize keys and the associated encrypted file data, corrupting the file system.

In this paper, we present Holepunch, a new software-level approach for implementing secure deletion. Holepunch treats the storage device as a black box, providing secure deletion via cryptographic erasure. Holepunch uses per-file keys to transparently encrypt outgoing file writes and decrypt incoming file reads, ensuring that all physical data in the storage device is always encrypted. Holepunch uses puncturable pseudorandom functions (PPRFs) to quickly access file keys; upon the deletion of file $f$, Holepunch updates the PPRF so that, even if the PPRF is recovered, the PPRF cannot be used to generate $f$'s key. By using PPRFs instead of the key trees leveraged by prior work, Holepunch reduces both the memory pressure caused by key management and the number of disk IOs needed to access files. Holepunch stores its master key in secure TPM storage, and uses a novel journaling scheme to provide crash consistency between TPM state and on-disk state.

Modern secure messaging protocols typically aim to provide deniability. Achieving this requires that convincing cryptographic transcripts can be forged without the involvement of genuine users. In this work, we observe that parties may wish to revoke deniability and avow a conversation after it has taken place. We propose a new protocol called Not-on-the-Record-Yet (NOTRY) which enables users to prove a prior conversation transcript is genuine. As a key building block we propose avowable designated verifier proofs which may be of independent interest. Our implementation incurs roughly 8× communication and computation overhead over the standard Signal protocol during regular operation. We find it is nonetheless deployable in a realistic setting as key exchanges (the source of the overhead) still complete in just over 1ms on a modern computer. The avowal protocol induces only constant computation and communication performance for the communicating parties and scales linearly in the number of messages avowed for the verifier—in the tens of milliseconds per avowal.

Hard lattice problems are predominant in constructing post-quantum cryptosystems. However, we need to continue developing post-quantum cryptosystems based on other quantum hard problems to prevent a complete collapse of post-quantum cryptography due to a sudden breakthrough in solving hard lattice problems. Solving large multivariate quadratic systems is one such quantum hard problem.

Unbalanced Oil-Vinegar is a signature scheme based on the hardness of solving multivariate equations. In this work, we present a post-quantum digital signature algorithm VDOO (Vinegar-Diagonal-Oil-Oil) based on solving multivariate equations. We introduce a new layer called the diagonal layer over the oil-vinegar-based signature scheme Rainbow. This layer helps to improve the security of our scheme without increasing the parameters considerably. Due to this modification, the complexity of the main computational bottleneck of multivariate quadratic systems i.e. the Gaussian elimination reduces significantly. Thus making our scheme one of the fastest multivariate quadratic signature schemes. Further, we show that our carefully chosen parameters can resist all existing state-of-the-art attacks. The signature sizes of our scheme for the National Institute of Standards and Technology's security level of I, III, and V are 96, 226, and 316 bytes, respectively. This is the smallest signature size among all known post-quantum signature schemes of similar security.

Constant-time C software for various post-quantum KEMs has been submitted by the KEM design teams to the SUPERCOP testing framework. The ref/*.c and ref/*.h files together occupy, e.g., 848 lines for ntruhps4096821, 928 lines for ntruhrss701, 1316 lines for sntrup1277, and 2613 lines for kyber1024.

It is easy to see that these numbers overestimate the inherent complexity of software for these KEMs. It is more difficult to systematically measure this inherent complexity.

This paper takes these KEMs as case studies and applies consistent rules to streamline the ref software for the KEMs, while still passing SUPERCOP's tests and preserving the decomposition of specified KEM operations into functions. The resulting software occupies 381 lines for ntruhps4096821, 385 lines for ntruhrss701, 472 lines for kyber1024, and 478 lines for sntrup1277. This paper also identifies the external subroutines used in each case, identifies the extent to which code is shared across different parameter sets, quantifies various software complications specific to each KEM, and finds secret-dependent timings in kyber*/ref.

This work investigates the security of the Ascon authenticated encryption scheme in the context of fault attacks, with a specific focus on Differential Fault Analysis (DFA). Motivated by the growing significance of lightweight cryptographic solutions, particularly Ascon, we explore potential vulnerabilities in its design using DFA. By employing a novel approach that combines faulty forgery in the decryption query under two distinct fault models, leveraging bit-flip faults in the first phase and bit-set faults in the second, we successfully recover the complete Ascon key. This study sheds light on the impact of key whitening in the final permutation call and discusses potential threats when this safeguard is absent. Additionally, we consider the implications of injecting multiple bit-flip faults at the S-box input, suggesting alternative strategies for compromising the state space. Our findings contribute valuable insights into the gray-box security landscape of Ascon, emphasizing the need for robust defenses to ensure the integrity and resilience of lightweight cryptographic primitives against diverse fault attacks.

In recent years, deep learning-based side-channel analysis (DLSCA) has become an active research topic within the side-channel analysis community. The well-known challenge of hyperparameter tuning in DLSCA encouraged the community to use methods that reduce the effort required to identify an optimal model. One of the successful methods is ensemble learning. While ensemble methods have demonstrated their effectiveness in DLSCA, particularly with AES-based datasets, their efficacy in analyzing symmetric-key cryptographic primitives with different operational mechanics remains unexplored. Ascon was recently announced as the winner of the NIST lightweight cryptography competition. This will lead to broader use of Ascon and a crucial requirement for thorough side-channel analysis of its implementations. With these two considerations in view, we utilize an ensemble of deep neural networks to attack two implementations of Ascon. Using an ensemble of five multilayer perceptrons or convolutional neural networks, we could find the secret key for the Ascon-protected implementation with less than 3 000 traces. To the best of our knowledge, this is the best currently known result. We can also identify the correct key with less than 100 traces for the unprotected implementation of Ascon, which is on par with the state-of-the-art results.

The Automatic Certificate Management Environment protocol (ACME) has significantly contributed to the widespread use of digital certificates in safeguarding the authenticity and privacy of Internet data. These certificates are required for implementing the Transport Layer Security (TLS) protocol. However, it is well known that the cryptographic algorithms employed in these certificates will become insecure with the emergence of quantum computers. This study assesses the challenges in transitioning ACME to the post-quantum landscape using Post-Quantum Cryptography (PQC). To evaluate the cost of ACME's PQC migration, we create a simulation environment for issuing PQC-only and hybrid digital certificates. Our experiments reveal performance drawbacks associated with the switch to PQC or hybrid solutions. However, considering the high volume of certificates issued daily by organizations like Let's Encrypt, the performance of ACME is of utmost importance. To address this concern, we propose a novel challenge method for ACME. Compared to the widely used HTTP-01 method, our findings indicate an average PQC certificate issuance time that is 4.22 times faster, along with a potential reduction of up to 35% in communication size.

Instant Runoff Voting (IRV) is one example of ranked-choice voting. It provides many known benefits when used in elections, such as minimising vote splitting, ensuring few votes are wasted, and providing resistance to strategic voting. However, the voting and tallying procedures for IRV are much more complicated than those of plurality and are both error-prone and tedious. Many automated systems have been proposed to simplify these procedures in IRV. Some of these also employ cryptographic techniques to protect the secrecy of ballots and enable verification of the tally. Nearly all of these cryptographic systems require a set of trustworthy tallying authorities (TAs) to perform the decryption of votes and/or running of mix servers, which adds significant complexity to the implementation and election management. We address this issue by proposing Camel: an E2E verifiable solution for IRV that requires no TAs. Camel employs a novel representation and a universally verifiable shifting procedure for ballots that facilitate the elimination of candidates as required in an IRV election. We combine these with a homomorphic encryption scheme and zero-knowledge proofs to protect the secrecy of the ballots and enable any party to verify the well-formedness of the ballots and the correctness of the tally in an IRV election. We examine the security of Camel and prove it maintains ballot secrecy by limiting the learned information (namely the tally) against a set of colluding voters.

Aggregation of message authentication codes (MACs) is a proven and efficient method to preserve valuable bandwidth in resource-constrained environments: Instead of appending a long authentication tag to each message, the integrity protection of multiple messages is aggregated into a single tag. However, while such aggregation saves bandwidth, a single lost message typically means that authentication information for multiple messages cannot be verified anymore. With the significant increase of bandwidth-constrained lossy communication, as applications shift towards wireless channels, it thus becomes paramount to study the impact of packet loss on the diverse MAC aggregation schemes proposed over the past 15 years to assess when and how to aggregate message authentication. Therefore, we empirically study all relevant MAC aggregation schemes in the context of lossy channels, investigating achievable goodput improvements, the resulting verification delays, processing overhead, and resilience to denial-of-service attacks. Our analysis shows the importance of carefully choosing and configuring MAC aggregation, as selecting and correctly parameterizing the right scheme can, e.g., improve goodput by 39% to 444%, depending on the scenario. However, since no aggregation scheme performs best in all scenarios, we provide guidelines for network operators to select optimal schemes and parameterizations suiting specific network settings.

In this work, we introduce FANNG-MPC, a versatile secure multi-party computation framework capable to offer active security for privacy preserving machine learning as a service (MLaaS). Derived from the now deprecated SCALE-MAMBA, FANNG is a data-oriented fork, featuring novel set of libraries and instructions for realizing private neural networks, effectively reviving the popular framework. To the best of our knowledge, FANNG is the first MPC framework to offer actively secure MLaaS in the dishonest majority setting, specifically two parties.

FANNG goes beyond SCALE-MAMBA by decoupling offline and online phases and materializing the dealer model in software, enabling a separate set of entities to produce offline material. The framework incorporates database support, a new instruction set for pre-processed material, including garbled circuits and convolutional and matrix multiplication triples. FANNG also implements novel private comparison protocols and an optimized library supporting Neural Network functionality. All our theoretical claims are substantiated by an extensive evaluation using an open-sourced implementation, including the private evaluation of popular neural networks like LeNet and VGG16.

Private computation of nonlinear functions, such as Rectified Linear Units (ReLUs) and max-pooling operations, in deep neural networks (DNNs) poses significant challenges in terms of storage, bandwidth, and time consumption. To address these challenges, there has been a growing interest in utilizing privacy-preserving techniques that leverage polynomial activation functions and kernelized convolutions as alternatives to traditional ReLUs. However, these alternative approaches often suffer from a trade-off between achieving faster private inference (PI) and sacrificing model accuracy. In particular, when applied to much deeper networks, these methods encounter training instabilities, leading to issues like exploding gradients (resulting in NaNs) or suboptimal approximations. In this study, we focus on PolyKervNets, a technique known for offering improved dynamic approximations in smaller networks but still facing instabilities in larger and more complex networks. Our primary objective is to empirically explore optimization-based training recipes to enhance the performance of PolyKervNets in larger networks. By doing so, we aim to potentially eliminate the need for traditional nonlinear activation functions, thereby advancing the state-of-the-art in privacy-preserving deep neural network architectures.

In this brief note, we flesh out some details of the recently proposed Simplex atomic broadcast protocol, and modify it so that leaders disperse blocks in a more communication efficient fashion, while maintaining the simplicity and excellent latency characteristics of the protocol.

Cryptocurrency networks crucially rely on digital signature schemes, which are used as an authentication mechanism for transactions. Unfortunately, most major cryptocurrencies today, including Bitcoin and Ethereum, employ signature schemes that are susceptible to quantum adversaries, i.e., an adversary with access to a quantum computer can forge signatures and thereby spend coins of honest users. In cryptocurrency networks, signature schemes are typically not executed in isolation, but within a so-called cryptographic wallet. In order to achieve security against quantum adversaries, the signature scheme and the cryptographic wallet must withstand quantum attacks.

In this work, we advance the study on post-quantum secure signature and wallet schemes. That is, we provide the first formal model for deterministic threshold wallets and we show a generic post-quantum secure construction from any post-quantum secure threshold signature scheme with rerandomizable keys. We then instantiate our construction from the isogeny-based signature scheme CSI-FiSh and we show that our instantiation significantly improves over prior work.

In this work, we present the first low-latency, second-order masked hardware implementation of Ascon that requires no fresh randomness using only $d+1$ shares. Our results significantly outperform any publicly known second-order masked implementations of AES and Ascon in terms of combined area, latency and randomness requirements. Ascon is a family of lightweight authenticated encryption and hashing schemes selected by NIST for standardization. Ascon is tailored for small form factors. It requires less power and energy while attaining the same or even better performance than current NIST standards. We achieve the reduction of latency by rearranging the linear layers of the Ascon permutation in a round-based implementation. We provide an improved technique to achieve implementations without the need for fresh randomness. It is based on the concept of changing of the guards extended to the second-order case. Together with the reduction of latency, we need to consider a large set of additional conditions which we propose to solve using a SAT solver. We have formally verified both, our first- and second-order implementations of Ascon using CocoAlma for the first two rounds. Additionally, we have performed a leakage assessment using t-tests on all 12 rounds of the initial permutation. Finally, we provide a comparison of our second-order masked Ascon implementation with other results.