International Association
for Cryptologic Research

MAYO is a popular high-calorie condiment as well as an auspicious candidate in the ongoing NIST competition for additional post-quantum signature schemes achieving competitive signature and public key sizes. In this work, we present high-speed implementations of MAYO using the AVX2 and Armv7E-M instruction sets targeting recent x86 platforms and the Arm Cortex-M4. Moreover, the main contribution of our work is showing that MAYO can be even faster when switching from a bitsliced representation of keys to a nibble-sliced representation. While the bitsliced representation was primarily motivated by faster arithmetic on microcontrollers, we show that it is not necessary for achieving high performance on Cortex-M4. On Cortex-M4, we instead propose to implement the large matrix multiplications of MAYO using the Method of the Four Russians (M4R), which allows us to achieve better performance than when using the bitsliced approach. This results in up to 21% faster signing. For AVX2, the change in representation allows us to implement the arithmetic much faster using shuffle instructions. Signing takes up to 3.2 times fewer cycles and key generation and verification enjoy similar speedups. This shows that MAYO is competitive with lattice-based signature schemes on x86 CPUs, and only a factor 2-6 slower than lattice-based signature schemes on Cortex-M4.

We prove that two variants of the Fujisaki-Okamoto (FO) transformations are selective opening secure (SO) against chosen-ciphertext attacks in the quantum random oracle model (QROM), assuming that the underlying public-key encryption scheme is one-way secure against chosen-plaintext attacks (OW-CPA). The two variants we consider are $\mathsf{FO}^{\not{\bot}}$ (Hofheinz, Hövelmanns, and Kiltz, TCC 2017) and $\mathsf{U}^{\not{\bot}}_\mathsf{m}$ (Jiang et al., CRYPTO 2018). This is the first correct proof in the QROM.

The previous work of Sato and Shikata (IMACC 2019) showed the SO security of $\mathsf{FO}^{\not{\bot}}$ in the QROM. However, we identify a subtle gap in their work. To close this gap, we propose a new framework that allows us to adaptively reprogram a QRO with respect to multiple queries that are computationally hard to predict. This is a property that can be easily achieved by the classical ROM, but is very hard to achieve in the QROM. Hence, our framework brings the QROM closer to the classical ROM.

Under our new framework, we construct the first tightly SO secure PKE in the QROM using lossy encryption. Our final application is proving $\mathsf{FO}^{\not{\bot}}$ and $\mathsf{U}^{\not{\bot}}_\mathsf{m}$ are bi-selective opening (Bi-SO) secure in the QROM. This is a stronger SO security notion, where an adversary can additionally corrupt some users' secret keys.

Deep learning-based profiling side-channel analysis has gained widespread adoption in academia and industry due to its ability to uncover secrets protected by countermeasures. However, to exploit this capability, an adversary must have access to a clone of the targeted device to obtain profiling measurements and know secret information to label these measurements. Non-profiling attacks avoid these constraints by not relying on secret information for labeled data. Instead, they attempt all key guesses and select the most successful one. Deep learning approaches form the foundation of several non-profiling attacks, but these methods often suffer from high computational complexity and limited performance in practical applications.

This work explores the performance of multi-output regression (MOR) models in side-channel analysis. We start with the recently proposed multi-output regression (MOR) approach for non-profiling side-channel analysis. Then, we significantly improve its performance by updating the 1) loss function, 2) distinguisher, and 3) employing a novel concept of validation set to reduce overfitting. We denote our approach as MORE - Multi-Output Regression Enhanced, which emphasizes significantly better attack performance than MOR. Our results demonstrate that combining the MORE methodology, ensembles, and data augmentation presents a potent strategy for enhancing non-profiling side-channel attack performance and improving the reliability of distinguishing key candidates.

Weightwise degree-d functions are Boolean functions that take the values of a function of degree at most d on each set of fixed Hamming weight. The class of weightwise affine functions encompasses both the symmetric functions and the Hidden Weight Bit Function (HWBF). The good cryptographic properties of the HWBF, except for the nonlinearity, motivates to investigate a larger class with functions that share the good properties and have a better nonlinearity. Additionally, the homomorphic friendliness of symmetric functions exhibited in the context of hybrid homomorphic encryption and the recent results on homomorphic evaluation of Boolean functions make this class of functions appealing for efficient privacy-preserving protocols.

In this article we realize the first study on weightwise degree-d functions, focusing on weightwise affine and weightwise quadratic functions. We show some properties on these new classes of functions, in particular on the subclass of cyclic weightwise functions. We provide balanced constructions and prove nonlinearity lower bounds for all cyclic weightwise affine functions and for a family of weightwise quadratic functions. We complement our work with experimental results, they show that other cyclic weightwise linear functions than the HWBF have better cryptographic parameters, and considering weightwise quadratic functions allows to reach higher algebraic immunity and substantially better nonlinearity.

The need for energy optimizations in modern systems forces CPU vendors to provide Dynamic Voltage Frequency Scaling (DVFS) interfaces that allow software to control the voltage and frequency of CPU cores. In recent years, the accessibility of such DVFS interfaces to adversaries has amounted to a plethora of fault attack vectors. In response, the current countermeasures involve either restricting access to DVFS interfaces or including additional compiler-based checks that let the DVFS fault occur but prevent an adversary from weaponizing it. However, such countermeasures are overly restrictive because (1) they prevent benign, non-SGX processes from utilizing DVFS, and (2) rely upon a less practical threat model than what is acceptable for Intel SGX. In this work, we hence put forth a new countermeasure perspective. We reason that all DVFS fault attacks are helped by system design decisions that allow an adversary to search through the entire space of frequency/voltage pairs which lead to DVFS faults on the victim system. Using this observation, we classify such frequency/voltage pairs causing DVFS faults as unsafe system states. We then develop a kernel module level countermeasure (in non-SGX execution context) that polls core frequency/voltage pairs to detect when the system is in an unsafe state, and force it back into a safe state. Our countermeasure completely prevents DVFS faults on three Intel generation CPUs: Sky Lake, Kaby Lake R, and Comet Lake, while allowing accessibility of DVFS features to benign non-SGX executions (something which prior works fail to achieve). Additionally, we also put forth the notion of maximal safe state, allowing our countermeasure to be implemented both as microcode (on the micro-architecture level) and as model-specific register (on the hardware level), as opposed to prior countermeasures which can not be implemented at the hardware level. Finally, we evaluate the overhead of our kernel module's execution on SPEC2017, observing an minuscule overhead of 0.28%.

Large transformer-based models have realized state- of-the-art performance on lots of real-world tasks such as natural language processing and computer vision. However, with the increasing sensitivity of the data and tasks they handle, privacy has become a major concern during model deployment. In this work, we focus on private inference in two-party settings, where one party holds private inputs and the other holds the model. We introduce BumbleBee, a fast and communication-friendly two-party private transformer inference system. Our contributions are three-fold: Firstly, we present optimized homomorphic encryption-based proto- cols that enable the multiplication of large matrices with 80 – 90% less communication cost than existing methods. Secondly, we offer a general method for designing efficient and accurate protocols for non-linear activation functions in transformers. Our activation protocols have demonstrated speed and reduced the communication overhead by 80 – 95% over two existing methods. Finally, we conducted intensive benchmarks on several large transformer models. Results show that BumbleBee is more than one order of magnitude faster than Iron (NeurIPS22).

In STOC 2019 Canetti et al. showed how to soundly instantiate the Fiat-Shamir transform assuming that prover and verifier have access to the key of a ??????????? ??????????? ℎ??ℎ ???????? ??? ??????????? ?????ℎ???? ?????????. The transform requires the starting protocol to be a special 3-round public-coin scheme that Canetti et al. call ???????? ?????-????????. One downside of the Canetti et al. approach is that the key of the hash function can be used only once (or a pre-determined bounded number of times). That is, each new zero-knowledge proof requires a freshly generated hash key (i.e., a freshly generated setup). This is in contrast to what happens with the standard Fiat-Shamir transform, where the prover, having access to the same hash function (modeled as a random-oracle), can generate an unbounded number of proofs that are guaranteed to be zero-knowledge and sound.

As our main contribution, we extend the results of Canetti et al., by proposing a multi-theorem protocol that follows the Fiat-Shamir paradigm and relies on correlation intractable hash functions. Moreover, our protocol remains zero-knowledge and sound even against adversaries that choose the statement to be proven (and the witness for the case of zero-knowledge) adaptively on the key of the hash function. Our construction is presented in the form of a compiler, that follows the Fiat-Shamir paradigm, which takes as input any trapdoor sigma-protocol for the NP-language $L$ and turns it into a non-interactive zero-knowledge protocol that satisfies the properties we mentioned. To be best of our knowledge, ours is the first compiler that follows the Fiat-Shamir paradigm to obtain a multi-theorem adaptive NIZK relying on correlation intractable hash functions.

Oblivious RAM (ORAM) is a general-purpose technique for hiding memory access patterns. This is a fundamental task underlying many secure computation applications. While known ORAM schemes provide optimal asymptotic complexity, despite extensive efforts, their concrete costs remain prohibitively expensive for many interesting applications. The current state-of-the-art practical ORAM schemes are suitable only for somewhat small memories (Square-Root ORAM or Path ORAM).

This work presents a novel concretely efficient ORAM construction based on recent breakthroughs in asymptotic complexity of ORAM schemes (PanORAMa and OptORAMa). We bring these constructions to the realm of practically useful schemes by relaxing the restriction on constant local memory size. Our design provides a factor of at least $6$ to $8$ improvement over an optimized variant of Path ORAM for a set of reasonable memory sizes (e.g., 1GB, 1TB) and with the same local memory size. To our knowledge, this is the first practical implementation of an ORAM based on the full hierarchical ORAM framework. Prior to our work, the belief was that hierarchical ORAM-based constructions were inherently too expensive in practice. We implement our design and provide extensive evaluation and experimental results.

Differential-Linear (DL) cryptanalysis is a well known cryptanalytic technique that combines differential and linear cryptanalysis. Over the years, multiple techniques were proposed to increase its strength and applicability. Two relatively recent ones are: The partitioning technique by Leurent and the use of neutral bits adapted by Beierle et al. to DL cryptanalysis.

In this paper we compare these techniques and discuss the possibility of using them together to achieve the best possible DL attacks. We study the combination of these two techniques and show that in many cases they are indeed compatible. We demonstrate the strength of the combination in two ways. First, we present the first DL attack on 4-round Xoodyak and an extension to 5-round in the related key model. We show that the attacks are possible only by using these two techniques simultaneously. In addition, using the combination of the two techniques we improve a DL attack on 9-round DES. We show that the partitioning technique mainly reduces the time complexity, and the use of neutral bits mainly reduces the data complexity, while the combination of them reduces both the time and data complexities.

Post-quantum cryptographic (PQC) algorithms, especially those based on the learning with errors (LWE) problem, have been subjected to several physical attacks in the recent past. Although the attacks broadly belong to two classes -- passive side-channel attacks and active fault attacks, the attack strategies vary significantly due to the inherent complexities of such algorithms. Exploring further attack surfaces is, therefore, an important step for eventually securing the deployment of these algorithms. Also, it is important to test the robustness of the already proposed countermeasures in this regard.

In this work, we propose a new fault attack on side-channel secure masked implementation of LWE-based key-encapsulation mechanisms (KEMs) exploiting fault propagation. The attack typically originates due to an algorithmic modification widely used to enable masking, namely the Arithmetic-to-Boolean ($\mathtt{A2B}$) conversion. We exploit the data dependency of the adder carry chain in $\mathtt{A2B}$ and extract sensitive information, albeit masking (of arbitrary order) being present. As a practical demonstration of the exploitability of this information leakage, we show key recovery attacks of Kyber, although the leakage also exists for other schemes like Saber. The attack on Kyber targets the decapsulation module and utilizes Belief Propagation (BP) for key recovery. To the best of our knowledge, it is the first attack exploiting an algorithmic component introduced to ease masking rather than only exploiting the randomness introduced by masking to obtain desired faults (as done by Delvaux). Finally, we performed both simulated and electromagnetic (EM) fault-based practical validation of the attack for an open-source first-order secure Kyber implementation running on an STM32 platform.

Sponge based constructions have gained significant popularity for designing lightweight authenticated encryption modes. Most of the authenticated ciphers following the Sponge paradigm can be viewed as variations of the Transform-then-permute construction. It is known that a construction following the Transform-then-permute paradigm provides security against any adversary having data complexity $D$ and time complexity $T$ as long as $DT \ll 2^{b-r}$. Here, $b$ represents the size of the underlying permutation, while $r$ pertains to the rate at which the message is injected. The above result demonstrates that an increase in the rate leads to a degradation in the security of the constructions, with no security guaranteed to constructions operating at the full rate, where $r=b$. This present study delves into the exploration of whether adding some auxiliary states could potentially improve the security of the Transform-then-permute construction.

Our investigation yields an affirmative response, demonstrating that a special class of full rate Transform-then-permute with additional states, dubbed frTtP+, can indeed attain security when operated under a suitable feedback function and properly initialized additional state. To be precise, we prove that frTtP+ provides security as long as $D \ll 2^{s/2}$ and $T \ll 2^{s}$, where $s$ denotes the size of the auxiliary state in terms of bits. To demonstrate the applicability of this result, we show that the construction $Orange-Zest_{mod}$ belongs to this class, thereby obtaining the desired security. In addition, we propose a family of full-rate Transform-then-permute construction with a Beetle-like feedback function, dubbed \textsf{fr-Beetle}, which also achieves the same level of security.

Recently, Servan-Schreiber et al. (S&P 2023) proposed a new notion called private access control lists (PACL) for function secret sharing (FSS), where the FSS evaluators can ensure that the FSS dealer is authorized to share the given function with privacy assurance. In particular, for the secret sharing of a point function $f_{\alpha, \beta}$, namely distributed point function (DPF), the authors showed how to efficiently restrict the choice of $\alpha$ via a specific PACL scheme from verifiable DPF. In this work, we show their scheme is insecure due to the lack of assessment of $\beta$, and we fix it using an auxiliary output. We then propose more fine-grained policy constraints for DPF. Our schemes allow an attribute-based access control w.r.t. $\alpha$, and a template restriction for $\beta$. Furthermore, we show how to reduce the storage size of the constraint representation from $O(N)$ to $O(\log N)$, where $N$ is the number of constraints. Our benchmarks show that the amortized running time of our attribute-based scheme and logarithmic storage scheme is $2.5\times$ - $3\times$ faster than the state-of-the-art with $2^{15}$ constraints.

We show that the Cherbal-Benchetioui key agreement scheme [Comput. Electr. Eng., 109, 108759 (2023)] fails to keep user anonymity, not as claimed. The scheme simply thinks that user anonymity is equivalent to protecting the user's real identity. But the true anonymity means that the adversary cannot attribute different sessions to target entities, which relates to entity-distinguishable, not just identity-revealable.

Private Set Intersection (PSI) is a well-studied secure two-party computation problem in which a client and a server want to compute the intersection of their input sets without revealing additional information to the other party. With this work, we present nested Cuckoo hashing, a novel hashing approach that can be combined with additively homomorphic encryption (AHE) to construct an efficient PSI protocol for unbalanced input sets. We formally prove the security of our protocol against semi-honest adversaries in the standard model. Our protocol yields client computation and communication complexity that is sublinear in the server’s set size and is thus of interest to clients with limited resources. The implementation and empirical evaluation of our protocol using the exponential ElGamal and BGV/BFV encryption schemes attests to state-of-the-art practical performance.

An $(n, t)$-Non-Interactive Verifiable Secret Sharing (NI-VSS) scheme allows a dealer to share a secret among $n$ parties, s.t. all the parties can verify the validity of their shares and only a set of them, i.e., more than $t$, can access the secret. In this paper, we introduce $\Pi$, as a unified framework for building NI-VSS schemes in the majority honest setting. Notably, $\Pi$ does not rely on homomorphic commitments; instead, builds upon any commitment scheme that extra to its core attributes hiding and binding, it might be homomorphic and/or PQ-secure.

- When employing Discrete Logarithm (DL)-based commitments, $\Pi$ enables the construction of two novel NI-VSS schemes, named $\Pi_P$ and $\Pi_F$. In comparison to the well-known Pedersen and Feldman VSS schemes, both $\Pi_P$ and $\Pi_F$ require $O(1)$ exponentiations in the verification process, as opposed to $O(t)$, albeit at the expense of a slightly slower sharing phase and increased communication. - By instantiating $\Pi$ with a hash-based commitment scheme, we obtain the first PQ-secure NI-VSS scheme in the $\it{plain}$ model, labeled $\Pi_{LA}$ (pronounced [paɪla]). $\Pi_{LA}$ outperforms the recent random oracle-based construction by Atapoor, Baghery, Cozzo, and Pedersen from Asiacrypt'23 by a constant factor in all metrics. $\Pi_{LA}$ can also be viewed as an amplified version of the $\it{simple}$ NI-VSS scheme, proposed by Gennaro, Rabin, and Rabin, at PODC'98. - Building upon $\Pi_F$, we construct a Publicly VSS (PVSS) scheme, labeled $\Pi_S$, that can be seen as a new variant of Schoenmakers' scheme from Crypto'99. To this end, we first define the Polynomial Discrete Logarithm (PDL) problem, as a generalization of DL and then build a variant of the Schnorr Proof of Knowledge (PoK) scheme based on the new hardness assumption. We think the PDL relation and the associated PoK scheme can be independently interesting for Shamir-based threshold protocols.

We believe $\Pi$ is general enough to be employed in various contexts such as lattices, isogenies, and an extensive array of practical use cases.

We design a SNARKs/STARKs-optimized AEAD scheme based on the $\texttt{MonkeySpongeWrap}$ (ToSC 2023(2)) and the RPO permutation (ePrint 2022/1577).

QARMAv2 represents a family of lightweight block ciphers introduced in ToSC 2023. This new iteration, QARMAv2, is an evolution of the original QARMA design, specifically constructed to accommodate more extended tweak values while simultaneously enhancing security measures. This family of ciphers is available in two distinct versions, referred to as QARMAv2-$b$-$s$, where ‘$b$’ signifies the block length, with options for both 64-bit and 128-bit blocks, and ‘$c$’ signifies the key length. In this paper, for the first time, we present differential fault analysis (DFA) of all the QARMAv2 variants- QARMAv2-64, and QARMAv2-128 by introducing an approach to utilize the fault propagation patterns at the nibble level, with the goal of identifying relevant faulty ciphertexts and vulnerable fault positions. This technique highlights a substantial security risk for the practical implementation of QARMAv2. By strategically introducing six random nibble faults into the input of the $(r − 1)$-th and $(r − 2)$-th backward rounds within the $r$-round QARMAv2-64, our attack achieves a significant reduction in the secret key space, diminishing it from the expansive $2^{128}$ to a significantly more smaller set of size $2^{32}$. Additionally, when targeting QARMAv2-128-128, it demands the introduction of six random nibble faults to effectively reduce the secret key space from $2^{128}$ to a remarkably reduced $2^{24}$. To conclude, we also explore the potential extension of our methods to conduct DFA on various other iterations and adaptations of the QARMAv2 cryptographic scheme. To the best of our knowledge, this marks the first instance of a differential fault attack targeting the QARMAv2 tweakable block cipher family, signifying an important direction in cryptographic analysis.

Since 2016’s NIST call for standardization of post-quantum cryptographic primitives, developing efficient post-quantum secure digital signature schemes has become a highly active area of research. The difficulty in constructing such schemes is evidenced by NIST reopening the call in 2022 for digital signature schemes, because of missing diversity in existing proposals. In this work, we introduce the new post-quantum digital signature scheme MiRitH. As direct successor of a scheme recently developed by Adj, Rivera-Zamarripa and Verbel (Africacrypt ’23), it is based on the hardness of the MinRank problem and follows the MPC-in-the-Head paradigm. We revisit the initial proposal, incorporate design-level improvements and provide more efficient parameter sets. We also provide the missing justification for the quantum security of all parameter sets following NIST metrics. In this context we design a novel Grover-amplified quantum search algorithm for solving the MinRank problem that outperforms a naive quantum brute-force search for the solution. MiRitH obtains signatures of size 5.7 kB for NIST category I security and therefore competes for the smallest signatures among any post-quantum signature following the MPCitH paradigm. At the same time MiRitH offers competitive signing and verification timings compared to the state of the art. To substantiate those claims we provide extensive implementations. This includes a reference implementation as well as optimized constant-time implementations for Intel processors (AVX2), and for the ARM (NEON) architecture. The speed-up of our optimized AVX2 implementation relies mostly on a redesign of the finite field arithmetic, improving over existing implementations as well as an improved memory management.

Classic MLaaS solutions suffer from privacy-related risks since the user is required to send unencrypted data to the server hosting the MLaaS. To alleviate this problem, a thriving line of research has emerged called Privacy-Preserving Machine Learning (PPML) or secure MLaaS solutions that use cryptographic techniques to preserve the privacy of both the input of the client and the output of the server. However, these implementations do not take into consideration the possibility of transferability of known attacks in classic MLaaS settings to PPML settings. In this paper, we demonstrate that it is possible to transfer existing model-extraction attacks using adversarial examples to PPML settings due to relaxed constraints on the abilities of the adversary. We show a working example of an end-to-end attack on an image processing application built using a popular FHE-based framework, namely Concrete-ML. We successfully create a cloned model with just 5000 queries, which is, in fact, 10× less than the size of the training set of the victim model, while incurring only a 7% loss in accuracy. Further, we incorporate the well-known defense strategy against such attacks and show that our attack is still able to clone the model. Finally, we evaluate the different defense rationales that exist in literature and observe that such model stealing attacks are difficult to prevent in secure MLaaS settings.

Leader for the US NIST Cryptographic Technology Group. This position formulates and conducts/leads/manages and consults on an exceptionally difficult research program or policy issues of major scope, complexity, importance, and impact in the field of cryptography. Promotes and disseminates wide application of program results through significant publications, presentations, or authoritative reports/analyses and in national and international Standard Development Organizations. Work directly with national and international stakeholders ranging from other federal agencies, other national governments, academia, and industry to gain consensus, communicate organizational value and deconflict mission priorities. Manages a group of researchers, scientists, and support staff. Position open to U.S. Citizens Only.

Closing date for applications:

Contact: tiffani.brown@nist.gov

More information: https://www.usajobs.gov/job/756714700