International Association
for Cryptologic Research

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.

In this report, we perform an in-depth analysis of the RSA authentication feature used in the secure boot procedure of Xilinx Zynq-7000 SoC device. The First Stage Boot Loader (FSBL) is a critical piece of software executed during secure boot, which utilizes the RSA authentication feature to validate all the hardware and software partitions to be mounted on the device. We analyzed the implementation of FSBL (provided by Xilinx) for the Zynq-7000 SoC and identified a critical security flaw, whose exploitation makes it possible to load an unauthenticated application onto the Zynq device, thereby bypassing RSA authentication. We also experimentally validated the presence of the vulnerability through a Proof of Concept (PoC) attack to successfully mount an unauthenticated software application on an RSA authenticated Zynq device. The identified flaw is only present in the FSBL software and thus can be easily fixed through appropriate modification of the FSBL software. Thus, the first contribution of our work is the identification of a critical security flaw in the FSBL software to bypass RSA authentication.

Upon bypassing RSA authentication, an attacker can mount any unauthenticated software application on the target device to mount a variety of attacks. Among the several possible attacks, we are interested to perform recovery of the encrypted bitstream in the target boot image of the Zynq-7000 device. To the best of our knowledge, there does not exist any prior work that has reported a practical bitstream recovery attack on the Zynq-7000 device. In the context of bitstream recovery, Ender et al. in 2020 proposed the Starbleed attack that is applicable to standalone Virtex-6 and 7-series Xilinx FPGAs. The design advisory provided by Xilinx as a response to the Starbleed attack claims that the Zynq-7000 SoC is resistant “due to the use of asymmetric and/or symmetric authentication in the boot/configuration process that ensures configuration is authenticated prior to use". Due to the security flaw found in the FSBL, we managed to identify a novel approach to mount the Starbleed attack on the Zynq-7000 device for full bitstream recovery. Thus, as a second contribution of our work, we present the first practical demonstration of the Starbleed attack on the Zynq-7000 SoC. We perform experimental validation of our proposed attacks on the PYNQ-Z1 platform based on the Zynq-7000 SoC.

The privacy-preserving machine learning (PPML) has gained growing importance over the last few years. One of the biggest challenges is to improve the efficiency of PPML so that the communication and computation costs of PPML are affordable for large machine learning models such as deep learning. As we know, linear algebra such as matrix multiplication occupies a significant part of the computation in the deep learning such as deep convolutional neural networks (CNN). Thus, it is desirable to propose the MPC protocol specialized for the matrix operations. In this work, we propose a dishonest majority MPC protocol over matrix rings which supports matrix multiplication and addition. Our MPC protocol can be seen as a variant of SPDZ protocol, i.e., the MAC and global key of our protocol are vectors of length $m$ and the secret of our protocol is an $m\times m$ matrix. Compared to the classic SPDZ protocol, our MPC protocol reduces the communication complexity by at least $m$ times. We also show that our MPC protocol is as efficient as [11] which also presented a dishonest majority MPC protocol specialized for matrix operations. The MPC protocol [11] resorts to the homomorphic encryption scheme (BFV scheme) to produce the matrix triples in the preprocessing phase. This implies that their protocol only supports the matrix operations over integer rings or prime fields of large size. On the contrary, we resort to vector oblivious linear evaluations and random vector oblivious linear evaluations to generate correlated randomness in the preprocessing phase. Thus, the matrices of our MPC protocol can be defined over any finite field or integer ring. Due to the small size of our MAC, the communication complexity of our MPC protocol remains almost the same regardless of the size of the field or the ring.

We introduce protocols for classical verification of quantum depth (CVQD). These protocols enable a classical verifier to differentiate between devices of varying quantum circuit depths, even in the presence of classical computation. The goal is to demonstrate that a classical verifier can reject a device with a quantum circuit depth of no more than $d$, even if the prover employs additional polynomial-time classical computation to deceive. Conversely, the verifier accepts a device with a quantum circuit depth of $d'>d$.

Previous results for separating hybrid quantum-classical computers with various quantum depths require either quantum access to oracles or interactions between the classical verifier and the quantum prover. However, instantiating oracle separations can significantly increase the quantum depth in general, and interaction challenges the quantum device to keep the qubits coherent while waiting for the verifier's messages. These requirements pose barriers to implementing the protocols on near-term devices.

In this work, we present a two-message protocol under the quantum hardness of learning with errors and the random oracle heuristic. An honest prover only needs classical access to the random oracle, and therefore any instantiation of the oracle does not increase the quantum depth. To our knowledge, our protocol is the first non-interactive CVQD, the instantiation of which using concrete hash functions, e.g., SHA-3, does not require additional quantum depth.

Our second protocol seeks to explore the minimality of cryptographic assumptions and the tightness of the separations. To accomplish this, we introduce an untrusted quantum machine that shares entanglements with the target machine. Utilizing a robust self-test, our protocol certifies the depth of the target machine with information-theoretic security and nearly optimal separation.