International Association
for Cryptologic Research

Finite field arithmetic is central to several cryptographic algorithms on embedded devices like the ARM Cortex-M4, particularly for elliptic curve and isogeny-based cryptography. However, rapid algorithm evolution, driven by initiatives such as NIST’s post-quantum standardization, might frequently render hand-optimized implementations obsolete. We address this challenge with m4-modarith, a library generating C code with inline assembly for the Cortex-M4 that rivals custom-tuned assembly, enabling agile development in this ever-changing landscape. Our generated modular multiplications obtains fast performances, competitive with hand-optimized assembly implementations published in the literature, even outperforming some of them for Curve25519. Two contributions are pivotal to this success. First, we introduce a novel multiplication strategy that matches the memory access complexity of the operand caching method while being applicable to a larger cache size for Cortex-M4 implementations. Second, we generalize an efficient pseudo-Mersenne reduction strategy, and formally prove its correctness and applicability for most primes of cryptographic interest. Our generator allowed agile optimization of SQIsign’s NIST PQC Round 2 submission, improving level 1 verification from 123 Mcycles to only 54 Mcycles, a $2.3\times$ speedup. As an additional case study, we use our generator to improve performance of portable implementations of RFC~7748 by up to $2.2\times$.

Proving the validity of ballots is a central element of verifiable elections. Such proofs can however create challenges when one desires to make a protocol receipt-free. We explore the challenges raised by validity proofs in the context of protocols where threshold receipt-freeness is obtained by secret sharing an encryption of a vote between multiple authorities. In such contexts, previous solutions verified the validity of votes by decrypting them after passing them through a mix-net. This approach however creates subtle privacy risks, especially when invalid votes leak structural patterns that threaten receipt-freeness. We propose a different approach of threshold receipt-free voting in which authorities re-randomize ballot shares then jointly compute a ZK proof of ballot validity before letting the ballots enter a (possibly homomorphic) tallying phase. Our approach keeps the voter computational costs limited while offering verifiability and improving the ballot privacy of previous solutions. We present two protocols that enable a group of servers to verify and publicly prove that encrypted votes satisfy some validity properties: Minimix, which preserves prior voter-side behavior with minimal overhead, and Homorand, which requires voters to submit auxiliary data to facilitate validation over large vote domains. We show how to use our two protocols within a threshold receipt-free voting framework. We provide formal security proofs and efficiency analyses to illustrate trade-offs in our designs.

Physical attacks pose a major challenge to the secure implementation of cryptographic algorithms. Although significant progress has been made in countering passive attacks such as side-channel analysis (SCA), protection against fault attacks is still less developed. One reason for this is the broader and more complex nature of fault attacks, which makes it difficult to create standardized fault evaluation methodologies for countermeasures like those used for SCA. This makes it easier to overlook potential vulnerabilities that attackers could exploit. RS-Mask, published at HOST 2020, is such a countermeasure that has been affected by the absence of a systematic analysis method. The fundamental concept behind the countermeasure is to maintain a uniform distribution of variables, regardless of whether they are faulty or correct. This property is particularly effective against Statistical Ineffective Fault Attacks (SIFA), which exploit the dependency between fault propagation and the secret data.

In this work, we present several fault scenarios involving single fault injections on the AES implementation protected with RS-Mask, where the fault propagation depends on the secret data. This happens because the random space mapping used in RS-Mask countermeasure retains a dependency on the secret data, as it is derived based on the S-box input. To address this, we propose a new countermeasure based on the core concept of RS-Mask, implementing a single mapping for all S-box inputs, involving an intrinsic duplication. Next, we evaluate the effectiveness of the new countermeasure against fault attacks by comparing the fault detection rate across all possible fault locations and values for every input. Additionally, we examine the output differences between faulty and correct outputs for each input. Our results show that the detection rate is uniform for each input, which ensures security against statistical attacks utilizing both effective and ineffective faults. Moreover, the output differences being uniform for each input ensures security against differential fault attacks.

Homomorphic encryption (HE) offers strong privacy guarantees by enabling computation over encrypted data. However, the performance of tensor operations in HE is highly sensitive to how the plaintext data is packed into ciphertexts. Large tensor programs introduce numerous possible layout assignments, making it both challenging and tedious for users to manually write efficient HE programs.

In this paper, we present Rotom, a compilation framework that autovectorizes tensor programs into optimized HE programs. Rotom systematically explores a wide range of layout assignments, applies state-of-the-art optimizations, and automatically finds an equivalent, efficient HE program. At its core, Rotom utilizes a novel, lightweight ApplyRoll layout conversion operator to easily modify the underlying data layouts and unlock new avenues for performance gains. Our evaluation demonstrates that Rotom scalably compiles all benchmarks in under 5 minutes, reduces rotations in manually optimized protocols by up to 4×, and achieves up to 80× performance improvement over prior systems.

The synchrony model allows Byzantine Agreement (BA) protocols to be deterministic, tolerate minority faults, and achieve the asymptotically optimal $O(n)$ rounds, and $O(n^2)$ bits of communication where $n$ is the number of parties. We study the deterministic BA problem in a model in which every communication link is either synchronous or partially synchronous. Our main result for this model is that feasibility implies optimality: For every $\frac{n}{3}\leq f<\frac{n}{2}$, the minimal network conditions required for BA to be solvable against $f$ byzantine faults, are also sufficient for it to be solvable optimally, i.e., with $O(f)$ rounds and $O(f^2)$ communication. In particular, BA against minority byzantine faults can be solved when the synchronous links in the network form a mere path ($f$ synchronous links) as efficiently (up to constant factors) as when all communication links are synchronous ($\Omega(f^2)$ synchronous links).

High-throughput technologies (e.g., the microarray) have fostered the rapid growth of gene expression data collection. These biomedical datasets, increasingly distributed among research institutes and hospitals, fuel various machine learning applications such as anomaly detection, prediction or clustering. In particular, unsupervised classification techniques based on biclustering like the Cheng and Church Algorithm (CCA) have proven to adapt particularly well to gene expression data. However, biomedical data is highly sensitive, hence its sharing across multiple entities introduces privacy and security concerns, with an ever-present threat of accidental disclosure or leakage of private patient information. To address such threat, this work introduces a novel, highly efficient privacy-preserving protocol based on secure multiparty computation (MPC) between two servers to compute CCA. Our protocol performs operations relying on an additive secret sharing and function secret sharing, leading us to reformulate the steps of the CCA into MPC-friendly equivalents. Leveraging lightweight cryptographic primitives, our new technique named FunBic-CCA is first to exploit the efficiency of function secret sharing to achieve fast evaluation of the CCA biclustering algorithm.

Evaluating the security of a device against side-channel attacks is a difficult task. One prominent strategy for this purpose is to characterize the distribution of the rank of the correct key among the different key hypotheses produced by a maximum likelihood attack, depending on the number of measured traces. In practice, evaluators can estimate some statistics of the rank that are used as security indicators---e.g., the arithmetic and geometric mean rank, the median rank, the $\alpha$-marginal guesswork, or the success rate of level $L$. Yet, a direct estimation becomes time-consuming as security levels increase.

In this work, we provide new bounds on these figures of merit in terms of the mutual information between the secret and its side-channel leakages. These bounds provide theoretical insights on the evolution of the figures of merit in terms of noise level, computational complexity (how many keys are evaluated) and data complexity (how many side-channel traces are used for the attack). To the best of our knowledge, these bounds are the first to formally characterize security guarantees that depend on the computational power of the adversary, based on a measure of their informational leakages. It follows that our results enable fast shortcut formulas for the certification laboratories, potentially enabling them to speed up the security evaluation process. We demonstrate the tightness of our bounds on both synthetic traces (in a controlled environment) and real-world traces from two popular datasets (Aisylab/AES\_HD and SMAesH).