International Association
for Cryptologic Research

As NIST is putting the final touches on the standardization of PQC (Post Quantum Cryptography) public key algorithms, it is a racing certainty that peskier cryptographic attacks undeterred by those new PQC algorithms will surface. Such a trend in turn will prompt more follow-up studies of attacks and countermeasures. As things stand, from the attackers’ perspective, one viable form of attack that can be implemented thereupon is the so-called “side-channel attack”. Two best-known countermeasures heralded to be durable against side-channel attacks are: “masking” and “hiding”. In that dichotomous picture, of particular note are successful single-trace attacks on some of the NIST’s PQC then-candidates, which worked to the detriment of the former: “masking”. In this paper, we cast an eye over the latter: “hiding”. Hiding proves to be durable against both side-channel attacks and another equally robust type of attacks called “fault injection attacks”, and hence is deemed an auspicious countermeasure to be implemented. Mathematically, the hiding method is fundamentally based on random permutations. There has been a cornucopia of studies on generating random permutations. However, those are not tied to implementation of the hiding method. In this paper, we propose a reliable and efficient verification of permutation implementation, through employing Fisher–Yates’ shuffling method. We introduce the concept of an ?-th order permutation and explain how it can be used to verify that our implementation is more efficient than its previous-gen counterparts for hiding countermeasures.

Existing protocols for proving the correct execution of a RAM program in zero-knowledge are plagued by a processor expressiveness trade-off : supporting fewer instructions results in smaller processor circuits (which improves performance), but may result in more program execution steps because non-supported instruction must be emulated over multiple processor steps (which diminishes performance).

We present Dora, a concretely efficient zero-knowledge protocol for RAM programs that sidesteps this tension by making it (nearly) free to add additional instructions to the processor. The computational and communication complexity of proving each step of a computation in Dora, is constant in the number of supported instructions. Dora is also highly generic and only assumes the existence of linearly homomorphic commitments. We implement Dora and demonstrate that on commodity hardware it can prove the correct execution of a processor with thousands of instruction, each of which has thousands of gates, in just a few milliseconds per step.

A recent preprint [ePrint 2023/1475] suggests the use of polynomials over a tropical algebra to construct a digital signature scheme "based on" the problem of factoring such polynomials, which is known to be NP‑hard. This short note presents two very efficient forgery attacks on the scheme, bypassing the need to factorize tropical polynomials and thus demonstrating that security in fact rests on a different, empirically easier problem.

In this paper, we describe an algorithm to compute chains of $(2,2)$-isogenies between products of elliptic curves in the theta model. The description of the algorithm is split into various subroutines to allow for a precise field operation counting.

We present a constant time implementation of our algorithm in Rust and an alternative implementation in SageMath. Our work in SageMath runs ten times faster than a comparable implementation of an isogeny chain using the Richelot correspondence. The Rust implementation runs up to forty times faster than the equivalent isogeny in SageMath and has been designed to be portable for future research in higher-dimensional isogeny-based cryptography.

In the attacker models of Side-Channel Attacks (SCA) and Fault Injection Attacks (FIA), the opponent has access to a noisy version of the internal behavior of the hardware. Since the end of the nineties, many works have shown that this type of attacks constitutes a serious threat to cryptosystems implemented in embedded devices. In the state-of-the-art, there exist several countermeasures to protect symmetric encryption (especially AES-128). Most of them protect only against one of these two attacks (either SCA or FIA). The main known counter-measure against SCA is masking; it makes the complexity of SCA growing exponentially with its order d. The most general version of masking is based on error correcting codes. It has the advantage of offering in principle a protection against both types of attacks (SCA and FIA), but all the functions implemented in the algorithm need to be masked accordingly, and this is not a simple task in general. We propose a particular version of such construction that has several advantages: it has a very low computation complexity, it offers a concrete protection against both SCA and FIA, and finally it allows flexibility: being not specifically dedicated to AES, it can be applied to any block cipher with any S-boxes. In the state-of-art, masking schemes all come with pros and cons concerning the different types of complexity (time, memory, amount of randomness). Our masking scheme concretely achieves the complexity of the best known scheme, for each complexity type

Given a set of matrices $\mathbf{A} := \{A_0, \dotsc, A_{k-1}\}$, and a matrix $M$ guaranteed to be the product of some ordered subset of $\mathbf{L}\subset\mathbf{A}$, can $\mathbf{L}$ be efficiently recovered? We begin by observing that the answer is positive under some assumptions on $\mathbf{A}$.

Noting that appropriate transformations seem to make $\mathbf{L}$'s recovery difficult we provide the blueprint of two new public-key cryptosystems based upon this problem.

We term those constructions "blueprints because, given their novelty, we are still uncertain of their exact security. Yet, we daringly conjecture that even if attacks are found on the proposed constructions, these attacks could be thwarted by adjustments in the key generation, key size or the encryption mechanism, thereby resulting on the long run in fully-fledged public-key cryptosystems that do not seem to belong to any of the mainstream public-key encryption paradigms known to date.

Secure multi-party computation (MPC) enables (joint) computations on sensitive data while maintaining privacy. In real-world scenarios, asymmetric trust assumptions are often most realistic, where one somewhat trustworthy entity interacts with smaller clients. We generalize previous two-party computation (2PC) protocols like MUSE (USENIX Security'21) and SIMC (USENIX Security'22) to the three-party setting (3PC) with one malicious party, avoiding the performance limitations of dishonest-majority inherent to 2PC.

We introduce two protocols, Auxiliator and Socium, in a machine learning (ML) friendly design with a fast online phase and novel verification techniques in the setup phase. These protocols bridge the gap between prior 3PC approaches that considered either fully semi-honest or malicious settings. Auxiliator enhances the semi-honest two-party setting with a malicious helper, significantly improving communication by at least two orders of magnitude. Socium extends the client-malicious setting with one malicious client and a semi-honest server, achieving substantial communication improvement by at least one order of magnitude compared to SIMC.

Besides an implementation of our new protocols, we provide the first open-source implementation of the semi-honest 3PC protocol ASTRA (CCSW'19) and a variant of the malicious 3PC protocol SWIFT (USENIX Security'21).

Private Simultaneous Messages (PSM) is a minimal model of secure computation, where the input players with shared randomness send messages to the output player simultaneously and only once. In this field, finding upper and lower bounds on communication complexity of PSM protocols is important, and in particular, identifying the optimal one where the upper and lower bounds coincide is the ultimate goal. However, up until now, functions for which the optimal communication complexity has been determined are few: An example of such a function is the two-input AND function where $(2\log_2 3)$-bit communication is optimal. In this paper, we provide new upper and lower bounds for several concrete functions. For lower bounds, we introduce a novel approach using combinatorial objects called abstract simplicial complexes to represent PSM protocols. Our method is suitable for obtaining non-asymptotic explicit lower bounds for concrete functions. By deriving lower bounds and constructing concrete protocols, we show that the optimal communication complexity for the equality and majority functions with three input bits are $3\log_2 3$ bits and $6$ bits, respectively. We also derive new lower bounds for the $n$-input AND function, three-valued comparison function, and multiplication over finite rings.

A central direction of research in secure multiparty computation with dishonest majority has been to achieve three main goals:

1. reduce the total number of rounds of communication (to four, which is optimal); 2. use only polynomial-time hardness assumptions, and 3. rely solely on cryptographic assumptions in a black-box manner.

This is especially challenging when we do not allow a trusted setup assumption of any kind. While protocols achieving two out of three goals in this setting have been designed in recent literature, achieving all three simultaneously remained an elusive open question. Specifically, it was answered positively only for a restricted class of functionalities. In this paper, we completely resolve this long-standing open question. Specifically, we present a protocol for all polynomial-time computable functions that does not require any trusted setup assumptions and achieves all three of the above goals simultaneously.

We introduce a new notion called ${\cal Q}$-secure pseudorandom isometries (PRI). A pseudorandom isometry is an efficient quantum circuit that maps an $n$-qubit state to an $(n+m)$-qubit state in an isometric manner. In terms of security, we require that the output of a $q$-fold PRI on $\rho$, for $ \rho \in {\cal Q}$, for any polynomial $q$, should be computationally indistinguishable from the output of a $q$-fold Haar isometry on $\rho$.

By fine-tuning ${\cal Q}$, we recover many existing notions of pseudorandomness. We present a construction of PRIs and assuming post-quantum one-way functions, we prove the security of ${\cal Q}$-secure pseudorandom isometries (PRI) for different interesting settings of ${\cal Q}$.

We also demonstrate many cryptographic applications of PRIs, including, length extension theorems for quantum pseudorandomness notions, message authentication schemes for quantum states, multi-copy secure public and private encryption schemes, and succinct quantum commitments.

Among secure multi-party computation protocols, linear secret sharing schemes often do not rely on cryptographic assumptions and are among the most straightforward to explain and to implement correctly in software. However, basic versions of such schemes either limit participants to evaluating linear operations involving private values or require those participants to communicate synchronously during a computation phase. A straightforward, information-theoretically secure extension to such schemes is presented that can evaluate arithmetic sum-of-products expressions that contain multiplication operations involving non-zero private values. Notably, this extension does not require that participants communicate during the computation phase. Instead, a preprocessing phase is required that is independent of the private input values (but is dependent on the number of factors and terms in the sum-of-products expression).

Motivated by the fact that broadcast is an expensive, but useful, resource for the realization of multi-party computation protocols (MPC), Cohen, Garay, and Zikas (Eurocrypt 2020), and subsequently Damgård, Magri, Ravi, Siniscalchi and Yakoubov (Crypto 2021), and, Damgård, Ravi, Siniscalchi and Yakoubov (Eurocrypt 2023), focused on ??-?????? ????????? ??????? ???. In particular, the authors focus on two-round MPC protocols (in the CRS model), and give tight characterizations of which security guarantees are achievable if broadcast is available in the first round, the second round, both rounds, or not at all.

This work considers the natural question of characterizing broadcast optimal MPC in the plain model where no set-up is assumed. We focus on four-round protocols, since four is known to be the minimal number of rounds required to securely realize any functionality with black-box simulation. We give a complete characterization of which security guarantees, (namely selective abort, selective identifiable abort, unanimous abort and identifiable abort) are feasible or not, depending on the exact selection of rounds in which broadcast is available.

It is well-known that Asynchronous Total Order Broadcast (ATOB) requires randomisation and that at most $t < n/3$ out of $n$ players are corrupted. This is opposed to synchronous total-order broadcast (STOB) which can tolerate $t < n/2$ corruptions and can be deterministic. We show that these requirements can be conceptually separated, by constructing an ATOB protocol which tolerates $t < n/2$ corruptions from blackbox use of Common Coin and Reliable Broadcast. We show the power of this conceptually simple contribution by reproving, using simpler protocols, existing results on STOB with optimistic responsiveness and asynchronous fallback. We also use the framework to prove the first ATOB with sub-quadratic communication and optimal corruption threshold $t < n/3$, new ATOBs with covert security and mixed adversary structures, and a new STOB with asymmetric synchrony assumptions.

We study the concrete security of a fundamental family of succinct interactive arguments, stemming from the works of Kilian (1992) and Ben-Sasson, Chiesa, and Spooner ("BCS", 2016). These constructions achieve succinctness by combining probabilistic proofs and vector commitments.

Our first result concerns the succinct interactive argument of Kilian, realized with any probabilistically-checkable proof (PCP) and any vector commitment. We establish the tightest known bounds on the security of this protocol. Prior analyses incur large overheads unsuitable for concrete security, or assume special (and restrictive) properties of the underlying PCP.

Our second result concerns an interactive variant of the BCS succinct non-interactive argument, which here we call IBCS, realized with any public-coin interactive oracle proof (IOP) and any vector commitment. We establish tight bounds on the security of this protocol. While this variant has been informally discussed in the literature, no prior security analysis, even asymptotic, existed before this work.

Finally, we study the capabilities and limitations of succinct arguments based on vector commitments. We show that a generalization of the IBCS protocol, which we call the Finale protocol, is secure when realized with any public-query IOP (a notion that we introduce) that satisfies a natural "random continuation sampling" (RCS) property. We also show a partial converse: if the Finale protocol satisfies the RCS property (which in particular implies its security), then so does the underlying public-query IOP.

Homomorphic encryption (HE) has gained broad attention in recent years as it allows computations on encrypted data enabling secure cloud computing. Deploying HE presents a notable challenge since it introduces a performance overhead by orders of magnitude. Hence, most works target accelerating server-side operations on hardware platforms, while little attention has been given to client-side operations. In this paper, we present a novel design methodology to implement and accelerate the client-side HE operations on area-constrained hardware. We show how to design an optimized floating-point unit tailored for the encoding of complex values. In addition, we introduce a novel hardware-friendly algorithm for modulo-reduction of floating-point numbers and propose various concepts for achieving efficient resource sharing between modular ring and floating-point arithmetic. Finally, we use this methodology to implement an end-to-end hardware accelerator, Aloha-HE, for the client-side operations of the CKKS scheme. In contrast to existing work, Aloha-HE supports both encoding and encryption and their counterparts within a unified architecture. Aloha-HE achieves a speedup of up to 59x compared to prior hardware solutions.

$\mathbb{Z}^n$ is one of the simplest types of lattices, but the computational problems on its rotations, such as $\mathbb{Z}$SVP and $\mathbb{Z}$LIP, have been of great interest in cryptography. Recent advances have been made in building cryptographic primitives based on these problems, as well as in developing new algorithms for solving them. However, the theoretical complexity of $\mathbb{Z}$SVP and $\mathbb{Z}$LIP are still not well understood.

In this work, we study the problems on rotations of $\mathbb{Z}^n$ by exploiting the symmetry property. We introduce a randomization framework that can be roughly viewed as `applying random automorphisms’ to the output of an oracle, without accessing the automorphism group. Using this framework, we obtain new reduction results for rotations of $\mathbb{Z}^n$. First, we present a reduction from $\mathbb{Z}$LIP to $\mathbb{Z}$SCVP. Here $\mathbb{Z}$SCVP is the problem of finding the shortest characteristic vectors, which is a special case of CVP where the target vector is a deep hole of the lattice. Moreover, we prove a reduction from $\mathbb{Z}$SVP to $\gamma$-$\mathbb{Z}$SVP for any constant $\gamma = O(1)$ in the same dimension, which implies that $\mathbb{Z}$SVP is as hard as its approximate version for any constant approximation factor. Second, we investigate the problem of finding a nontrivial automorphism for a given lattice, which is called LAP. Specifically, we use the randomization framework to show that $\mathbb{Z}$LAP is as hard as $\mathbb{Z}$LIP. We note that our result can be viewed as a $\mathbb{Z}^n$-analogue of Lenstra and Silverberg's result in [JoC2017], but with a different assumption: they assume the $G$-lattice structure, while we assume the access to an oracle that outputs a nontrivial automorphism.

Auerbach, Cash, Fersch, and Kiltz (CRYPTO 2017) initiated the study of memory tightness of reductions in cryptography in addition to the standard tightness related to advantage and running time and showed the importance of memory tightness when the underlying problem can be solved efficiently with large memory. Diemert, Geller, Jager, and Lyu (ASIACRYPT 2021) and Ghoshal, Ghosal, Jaeger, and Tessaro (EUROCRYPT 2022) gave memory-tight proofs for the multi-challenge security of digital signatures in the random oracle model.

This paper studies the memory-tight reductions for _post-quantum_ signature schemes in the _quantum_ random oracle model. Concretely, we show that signature schemes from lossy identification are multi-challenge secure in the quantum random oracle model via memory-tight reductions. Moreover, we show that the signature schemes from lossy identification achieve more enhanced securities considering _quantum_ signing oracles proposed by Boneh and Zhandry (CRYPTO 2013) and Alagic, Majenz, Russel, and Song (EUROCRYPT 2020). We additionally show that signature schemes from preimage-sampleable functions achieve those securities via memory-tight reductions.

We present two new constructions for private information retrieval (PIR) in the classical setting where the clients do not need to do any preprocessing or store any database dependent information, and the server does not need to store any client-dependent information.

Our first construction HintlessPIR eliminates the client preprocessing step from the recent LWE-based SimplePIR (Henzinger et. al., USENIX Security 2023) by outsourcing the "hint" related computation to the server, leveraging a new concept of homomorphic encryption with composable preprocessing. We realize this concept on RLWE encryption schemes, and thanks to the composibility of this technique we are able to preprocess almost all the expensive parts of the homomorphic computation and reuse across multiple executions. As a concrete application, we achieve very efficient matrix vector multiplication that allows us to build HintlessPIR. For a database of size 8GB, HintlessPIR achieves throughput about 3.7GB/s without requiring any client or server state. We additionally formalize the matrix vector multiplication protocol as LinPIR primitive, which may be of independent interests.

In our second construction TensorPIR we reduce the communications of HintlessPIR from square root to cubic root in the database size. For this purpose we extend our HE with preprocessing techniques to composition of key-switching keys and the query expansion algorithm. We show how to use RLWE encryption with preprocessing to outsource LWE decryption for ciphertexts generated by homomorphic multiplications. This allows the server to do more complex processing using a more compact query under LWE.

We implement and benchmark HintlessPIR which achieves better concrete costs than TensorPIR for a large set of databases of interest. We show that it improves the communication of recent preprocessing constructions when clients do not have large numbers of queries or database updates frequently. The computation cost for removing the hint is small and decreases as the database becomes larger, and it is always more efficient than other constructions with client hints such as Spiral PIR (Menon and Wu, S&P 2022). In the setting of anonymous queries we also improve on Spiral's communication.

Masking is a well-known and provably secure countermeasure against side-channel attacks. However, due to additional redundant computations, integrating masking schemes is expensive in terms of performance. The performance overhead of integrating masking countermeasures is heavily influenced by the design choices of a cryptographic algorithm and is often not considered during the design phase. In this work, we deliberate on the effect of design choices on integrating masking techniques into lattice-based cryptography. We select Scabbard, a suite of three lattice-based post-quantum key-encapsulation mechanisms (KEM), namely Florete, Espada, and Sable. We provide arbitrary-order masked implementations of all the constituent KEMs of the Scabbard suite by exploiting their specific design elements. We show that the masked implementations of Florete, Espada, and Sable outperform the masked implementations of Kyber in terms of speed for any order masking. Masked Florete exhibits a $73\%$, $71\%$, and $70\%$ performance improvement over masked Kyber corresponding to the first-, second-, and third-order. Similarly, Espada exhibits $56\%$, $59\%$, and $60\%$ and Sable exhibits $75\%$, $74\%$, and $73\%$ enhanced performance for first-, second-, and third-order masking compared to Kyber respectively. Our results show that the design decisions have a significant impact on the efficiency of integrating masking countermeasures into lattice-based cryptography.

Physical attacks are serious threats to cryptosystems deployed in the real world. In this work, we propose a microarchitectural end-to-end attack methodology on generic lattice-based post-quantum key encapsulation mechanisms to recover the long-term secret key. Our attack targets a critical component of a Fujisaki-Okamoto transform that is used in the construction of almost all lattice-based key encapsulation mechanisms. We demonstrate our attack model on practical schemes such as Kyber and Saber by using Rowhammer. We show that our attack is highly practical and imposes little preconditions on the attacker to succeed. As an additional contribution, we propose an improved version of the plaintext checking oracle, which is used by almost all physical attack strategies on lattice-based key-encapsulation mechanisms. Our improvement reduces the number of queries to the plaintext checking oracle by as much as 39% for Saber and approximately 23% for Kyber768. This can be of independent interest and can also be used to reduce the complexity of other attacks.