The security of block ciphers such as AES-128, AES-192, and AES-256 relies on the assumption that their ciphertext outputs are computationally indistinguishable from random permutations. While distinguishers have been proposed for reduced-round variants or under non-standard models such as known-key or chosen-key settings, no effective distinguisher has been demonstrated for the full-round AES ciphers in the standard secret-key model. This work introduces FESLA (Feature Enhanced Statistical Learning Attack), a hybrid statistical learning framework that integrates outputs from a suite of classical statistical tests with machine learning and deep learning classifiers to construct ciphertext-only distinguishers for AES-128, AES-192, and AES-256. In contrast to existing approaches based on handcrafted or bitwise features, FESLA aggregates intermediate statistical metrics as features, enabling the capture of persistent structural biases in ciphertext distributions. Experimental evaluation across multiple datasets demonstrates consistent 100% classification accuracy using Support Vector Machines, Random Forests, Multi-Layer Perceptron, Logistic Regression, and Naïve Bayes classifiers. Generalization and robustness are confirmed through k-fold cross-validation, including on previously unseen ciphertext samples. These results establish the first ciphertext-only distinguishers for full-round AES-128, AES-192, and AES-256 under the secret-key model, and underscore the potential of machine learning–augmented cryptanalysis based on principled statistical feature engineering.

Organizations increasingly need to collaborate by performing a computation on their combined dataset, while keeping their data hidden from each other. Certain kinds of collaboration, such as collaborative data analytics and AI, require a level of performance beyond what current cryptographic techniques for distributed trust can provide. This is because the organizations run software in different trust domains, which can require them to communicate over WANs or the public Internet. In this paper, we explore how to instead run such applications using fast datacenter-type LANs. We show that, by carefully redesigning distributed trust frameworks for LANs, we can achieve up to order-of-magnitude better performance than naïvely using a LAN. Then, we develop deployment models for Distributed But Proximate Trust (DBPT) that allow parties to use a LAN while remaining physically and logically distinct. These developments make secure collaborative data analytics and AI significantly more practical and set new research directions for developing systems and cryptographic theory for high-performance distributed trust.

Non-interactive publicly verifiable secret sharing (PVSS) schemes enable the decentralized (re-)sharing of secrets in adversarial environments, allowing anyone to verify the correctness of distributed shares. Such schemes are essential for large-scale decentralized applications, including committee-based systems that require both transparency and robustness. However, existing PVSS schemes rely on group-based cryptography, making them vulnerable to quantum attacks and limiting their suitability for post-quantum applications. In this work, we propose the first practical, fully lattice-based, non-interactive PVSS scheme, grounded on standard lattice assumptions for post-quantum security. At the heart of our design lies a generic framework that transforms vector commitments and linear encryption schemes into practical PVSS protocols. We enhance vector commitments by incorporating proof of smallness, ensuring that encrypted shares are both verifiable and privacy-preserving. Our construction introduces two tailored lattice-based encryption schemes, each supporting efficient proofs of decryption correctness. This framework provides strong verifiability guarantees while maintaining low proof sizes and computational efficiency.

As a case study in cryptographic binding, we present a formal-methods analysis of the cryptographic channel binding mechanisms in the Fast IDentity Online (FIDO) Universal Authentication Framework (UAF) authentication protocol, which seeks to reduce the use of traditional passwords in favor of authentication devices. First, we show that UAF's channel bindings fail to mitigate protocol interaction by a Dolev-Yao adversary, enabling the adversary to transfer the server's authentication challenge to alternate sessions of the protocol. As a result, in some contexts, the adversary can masquerade as a client and establish an authenticated session with a server (e.g., possibly a bank server). Second, we implement a proof-of-concept man-in-the-middle attack against eBay's open source FIDO UAF implementation. Third, we propose and formally verify improvements to UAF. The weakness we analyze is similar to the vulnerability discovered in the Needham-Schroeder protocol over 25 years ago. That this vulnerability appears in the FIDO UAF standard highlights the strong need for protocol designers to bind messages properly and to analyze their designs with formal-methods tools. To our knowledge, we are first to carry out a formal-methods analysis of channel binding in UAF and first to exhibit details of an attack on UAF that exploits the weaknesses of UAF's channel binding. Our case study illustrates the importance of cryptographically binding context to protocol messages to prevent an adversary from misusing messages out of context.

With the rapid advancement of 5G networks and the increasing demand for secure application access, the Authentication and Key Management for Applications (AKMA) framework was developed by the 3rd Generation Partnership Project (3GPP) to provide unified authentication and key management for diverse 5G services. In response to the security and privacy concerns identified in the current AKMA protocol, as outlined in 3GPP TR 33.835, Yang et al. proposed an enhanced, standard-compatible 5G AKMA protocol known as AKMA+[14]. This paper presents a comprehensive analysis of AKMA+, discovering two critical vulnerabilities: (1) the compromise of the AKMA Anchor Function (AAnF), which enables adversaries to impersonate legitimate users; and (2) the persistent storage of multiple anchor keys, which heightens the risk of key exposure. These vulnerabilities arise from the reliance on the authentication framework inherent in existing AKMA+ models. This architectural dependency introduces fundamental security risks that cannot be adequately mitigated through incremental modifications to the current design. Furthermore, we observe that AKMA+ faces challenges in aligning with the standard account-based authentication model, which is incompatible with existing user practices within information systems. Additionally, we find that providing account-based authentication functionality without compromising privacy poses significant difficulties.

The private set operation (PSO) scheme [Rafiee-Khazaei, Comput. J. 2020] is a cryptographic primitive that enables a user to securely outsource their dataset to cloud server, and then when needed, securely issue common set operation queries to the server and receive the results. This primitive has always been of interest to researchers because it supports set operations, which are the most basic mathematical operations and are used in a wide range of real-world applications. In previous research, security notions such as: naSIM and aIND have been introduced for it. In this paper, we develop the standard security notions for PSO schemes: an adaptive version of simulation-based security notion (aSIM) and a non-adaptive version of indistinguishability-based security notion (naIND). We also study the relation between these security notions and determine their implications and separations. In addition to these, we also provide a summary of the available PSO constructions and their security level, and introduce research potentials in this regard.

A private set operation (PSO) scheme [Rafiee, Comput. J. 2020] is a cryptographic primitive that enables a user to securely outsource their dataset to cloud storage, and then when needed, securely issue common set operation queries to the server and receive the results. In [Rafiee, Comput. J. 2020], the only security notion of the PSO schemes, named naSIM, is proposed. This security notion models a weak attacker who is far from the threats of practical environments, and providing stronger security notions has been raised as an open problem. In this paper, we propose a new security notion for the PSO schemes, called aIND, and show that this concept is stronger than naSIM. Furthermore, we propose a new PSO construction that satisfies the security notion aIND. We also show that our construction does not increase the computational and storage overheads compared to other existing constructions, despite covering a much higher level of security.

In recent years and with the emergence of the industrial revolution, the secure data sharing schemes have been developed in IoT platforms and have been recognized as a hot topic in industry and academia. These schemes enable IoT devices to securely share their sensed data in industrial environments with clients through an appropriate infrastructure and intermediary entities. The research conducted in this field shows the existence of various security challenges and solutions. Data privacy, data authentication, fairness and accountability are some of the most important security features presented. Recently, in paper [Sengupta-Ruj-Bit, TNSM 2023] proposed a secure sharing scheme and claimed that it covers all the mentioned security features even when entities collude with each other. In this paper, we investigate the security analysis of this scheme, and show that it does not cover the claimed fairness property. Therefore, the mentioned scheme is vulnerable and cannot be used as a valid scheme in real-world applications.

Among standardization efforts for space and interplanetary network security, the Internet Engineering Task Force (IETF) is driv- ing work on space network security, accounting for the unique proper- ties of space environments that make space communication challenging. This includes long, variable-length delays, packet loss, and intermittent end-to-end connectivity. Within these efforts, there is a focus on using IP-based protocols for security, and in particular the use of the QUIC protocol. This is unsurprising given QUIC’s growing popularity and of- fer of optimization intended for reducing latency. However, QUIC uses the Transport Layer Security (TLS) key exchange handshake protocol, which was originally designed for ‘connect and forget’ style Internet con- nections at scale. It is also session-based, where protocol participants require reestablishment of the session for each reconnection – a costly maneuver in the space setting. Furthermore, TLS by default does not achieve strong post-compromise security properties within sessions, ex- hibiting a risk under long-lived connections, and need for synchronous handshakes to counteract this are in functional contrast to the space environment, which has intermittent end-to-end connectivity. We address both drawbacks of QUIC by introducing QUIC-MLS: a vari- ant of QUIC which replaces the session-based, synchronous TLS hand- shake with the standardized continuous key agreement protocol, Mes- saging Layer Security (MLS), which achieves asynchronous forward se- crecy and post-compromise security. In addition to the design itself, we implement our design and provide benchmarks, and analyze our new construction in a formal cryptographic model.

We present a cryptanalysis of a multi-party key exchange protocol over a modified supertropical semiring, as proposed in a recent work of R. Ponmaheshkumar, J. Ramalingam, and R. Perumal. Building on the established methods for solving linear systems $A \otimes x=b$ over the tropical semiring, as well as on our recent work on solving such systems over layered semirings such as the symmetrized and supertropical semirings, we develop a method to compute a solution of $A \otimes x=b$ over the above mentioned modified supertropical semiring. This method enables the attacker to recover the shared secret key by solving the one-sided linear system derived from the public messages of the protocol. Our findings show that this modified supertropical platform does not provide the intended security and motivate further exploration of secure semiring-based constructions.

Algebraic cryptanalysis is an important and versatile tool in the evaluation of the security of various cryptosystems especially in multivariate cryptography. Its effectiveness can be determined by analyzing the Polynomial System Solving problem (PoSSo). However, the polynomial systems arising from cryptanalytic algebraic models often exhibit structure that is crucial for the solving complexity and is often not well understood. In this paper we turn our focus to multi-homogeneous systems that very often arise in algebraic models. Despite their overwhelming presence, both the theory and the practical solving methods are not complete. Our work fills this gap. We develop a theory for multi-homogeneous systems that extends the one for regular and semi-regular sequences. We define "border-regular" systems and provide exact statements about the rank of a specific submatrix of the Macaulay that we associate to these systems. We then use our theoretical results to define Multi-homogeneous XL - an algorithm that extends XL to the multi-homogeneous case. We further provide fully optimized implementation of Multi-homogeneous XL that uses sparse linear algebra and can handle a vast parameter range of multi-homogeneous systems. To the best of our knowledge this is the first implementation of its kind, and we make it publicly available.

The transition to post-quantum cryptography involves balancing the long-term threat of quantum adversaries with the need for post-quantum algorithms and their implementations to gain maturity safely. Hybridization, i.e. combining classical and post-quantum schemes, offers a practical and safe solution. We introduce a new security notion for hybrid signatures, Hybrid EU-CMA, which captures cross-protocol, separability, and recombination attacks that may occur during the post-quantum transition, while encompassing standard unforgeability guarantees. Using this framework, we adapt the Fiat-Shamir (with or without aborts) transform to build hybrid signature schemes that satisfy our notion from two identification schemes. Compared to simple concatenation of signatures, our construction (i) has no separability issues, (ii) reduces signature size, (iii) runs faster, and (iv) remains easily implementable. As a concrete application, we propose Silithium, a hybrid signature combining the identification schemes underlying EC-Schnorr and ML-DSA. Implementing Silithium requires only an ML-DSA implementation supporting the ``external $\mu$'' option during verification and an elliptic curve library. In the security analysis, we show that our scheme can be safely used along with ML-DSA and either EC-Schnorr or ECDSA. A proof-of-concept OpenSSL implementation demonstrates its practicality, simplicity, and performance.

Authenticated encryption (AE) provides both authenticity and privacy. We investigate the security of generically composing unauthenticated encryption and authentication in a quantum setting where adversarial queries as well as the responses to those may be in superposition. This extends the work from Bellare and Namprempre in 2000, who considered the classical setting. First, we disprove a claim made by Soukharev et al. at PQCrypto 2016. Namely, we show that a chosen-plaintext (IND-qCPA) secure symmetric encryption scheme and a plus-one unforgeable message authentication code (MAC) exist, such that their generic (Encrypt-then-MAC) composition fails to achieve chosen-ciphertext (IND-qCCA) security. On the other hand, we show that a stronger MAC (namely a qPRF) suffices for the composed scheme to be IND-qCCA secure. Furthermore, the IND-qCCA notion proposed in related work assumes a randomized encryption operation. We propose to replace the randomness by a nonce, and to authenticate associated data, in addition to the message.

Emotion recognition has been an actively researched topic in the field of HCI. However, multimodal datasets used for emotion recognition often contain sensitive personal information, such as physiological signals, facial images, and behavioral patterns, raising significant privacy concerns. In particular, the privacy issues become crucial in workplace settings because of the risks such as surveillance and unauthorized data usage caused by the misuse of collected datasets. To address this issue, we propose an Encrypted Emotion Recognition (EER) framework that performs real-time inference on encrypted data using the CKKS homomorphic encryption (HE) scheme. We evaluated the proposed framework using publicly available WESAD and Hide-and-seek datasets, demonstrating successful stress/emotion recognition under encryption. The results demonstrated that encrypted inference achieved similar accuracy to plaintext inference, with accuracy of 0.966 (plaintext) vs. 0.967 (ciphertext) on the WESAD dataset, and 0.868 for both cases on the Hide-and-Seek dataset. Encrypted inference was performed on a GPU, with average inference times of 333 milliseconds for the general model and 455 milliseconds for the personalized model. Furthermore, we validated the feasibility of semi-supervised learning and model personalization in encrypted environments, enhancing the framework’s real-world applicability. Our findings suggest that the EER framework provides a scalable, privacy-preserving solution for emotion recognition in domains such as healthcare and workplace settings, where securing sensitive data is of critical importance.

Ledger-based systems that support rich applications often suffer from two limitations. First, validating a transaction requires re-executing the state transition that it attests to. Second, transactions not only reveal which application had a state transition but also reveal the application's internal state. We design, implement, and evaluate ZEXE, a ledger-based system where users can execute offline computations and subsequently produce transactions, attesting to the correctness of these computations, that satisfy two main properties. First, transactions *hide all information* about the offline computations. Second, transactions can be *validated in constant time* by anyone, regardless of the offline computation. The core of ZEXE is a construction for a new cryptographic primitive that we introduce, *decentralized private computation* (DPC) schemes. In order to achieve an efficient implementation of our construction, we leverage tools in the area of cryptographic proofs, including succinct zero knowledge proofs and recursive proof composition. Overall, transactions in ZEXE are 968 bytes regardless of the offline computation, and generating them takes less than a minute plus a time that grows with the offline computation. We demonstrate how to use ZEXE to realize privacy-preserving analogues of popular applications: private decentralized exchanges for user-defined fungible assets and regulation-friendly private stablecoins.

We introduce Coral, a system for proving in zero- knowledge that a committed byte stream corresponds to a structured object in accordance to a Context Free Grammar. Once a prover establishes the validity of the parsed object with Coral, they can selectively prove facts about the object—such as fields in Web API responses or in JSON Web Tokens—–to third parties or blockchains. Coral reduces the problem of correct parsing to a few simple checks over a left-child right-sibling tree and introduces a novel segmented memory abstraction that unifies and extends prior constructions for RAM in zkSNARKs. Our implementation of Coral runs on a standard laptop, and non-interactively proves the parsing of real Web responses (JSON) and files (TOML and C) in seconds. The resulting proofs are small and cheap to verify.

This paper is about the proximity gaps phenomenon for Reed-Solomon codes. Very roughly, the proximity gaps phenomenon for a code $\mathcal C \subseteq \mathbb F_q^n$ says that for two vectors $f,g \in \mathbb F_q^n$, if sufficiently many linear combinations $f + z \cdot g$ (with $z \in \mathbb F_q$) are close to $\mathcal C$ in Hamming distance, then so are both $f$ and $g$, up to a proximity loss of $\varepsilon^*$. Determining the optimal quantitative form of proximity gaps for Reed--Solomon codes has recently become of great interest because of applications to interactive proofs and cryptography, and in particular, to scalable transparent arguments of knowledge (STARKs) and other modern hash based argument systems used on blockchains today. Our main results show improved positive and negative results for proximity gaps for Reed-Solomon codes of constant relative distance $\delta \in (0,1)$. 1. For proximity gaps up to the unique decoding radius $\delta/2$, we show that arbitrarily small proximity loss $\varepsilon^* > 0$ can be achieved with only $O_{\varepsilon^*}(1)$ exceptional $z$'s (improving the previous bound of $O(n)$ exceptions). 2. For proximity gaps up to the Johnson radius $J(\delta)$, we show that proximity loss $\varepsilon^* = 0$ can be achieved with only $O(n)$ exceptional $z$'s (improving the previous bound of $O(n^2)$ exceptions). This significantly reduces the soundness error in the aforementioned arguments systems. 3. In the other direction, we show that for some Reed--Solomon codes and some $\delta$, proximity gaps at or beyond the Johnson radius $J(\delta)$ with arbitrarily small proximity loss $\varepsilon^*$ needs to have at least $\Omega(n^{1.99})$ exceptional $z$'s. 4. More generally, for all constants $\tau$, we show that for some Reed-Solomon codes and some $\delta = \delta(\tau)$, proximity gaps at radius $\delta - \Omega_{\tau}(1)$ with arbitrarily small proximity loss $\varepsilon^*$ needs to have $n^{\tau}$ exceptional $z$'s. 5. Finally, for all Reed-Solomon codes, we show that improved proximity gaps imply improved bounds for their list-decodability. This shows that improved bounds on the list-decoding radius of Reed-Solomon codes is a prerequisite for any new proximity gaps results beyond the Johnson radius.

In p-noisy coin-tossing, Alice and Bob obtain fair coins which are of opposite values with probability p. Its Oblivious-Transfer (OT) complexity refers to the least number of OTs required by a semi-honest perfectly secure 2-party protocol for this task. We show a tight bound of Θ(log 1/p) for the OT complexity of p-noisy coin-tossing. This is the first instance of a lower bound for OT complexity that is independent of the input/output length of the function. We obtain our result by providing a general connection between the OT complexity of randomized functions and the complexity of Secure Zero Communication Reductions (SZCR), as recently de- fined by Narayanan et al. (TCC 2020), and then showing a lower bound for the complexity of an SZCR from noisy coin-tossing to (a predicate corresponding to) OT.

Fault attacks have historically been one of the most popular gray-box attacks in Cryptographic literature. In such attacks, an attacker tries to inject perturbations while executing a cipher and exploit the faulty outputs to recover the key. While the efficiency of such an attack is measured by number of faults required and size of the reduced key-space, another pivotal temporal parameter in the point of fault injection which has not received considerable attention. In this work, we plug this gap for a special class of ciphers namely DEFAULT and BAKSHEESH which boast of an SBox with one or more linear structures (LS). We make new observations which lead to the improvement of Division Property based fault attacks (DIFA) introduced by Kundu et al. in ACNS 2023. We show that these linear structures are particularly responsible for giving the higher fault penetration in these ciphers. We improve the state-of-the-art for BAKSHEESH from 30 to 28 rounds and for DEFAULT from 75 to 72 using the single round random nibble fault model. While for BAKSHEESH we are able to uniquely recover the key, for DEFAULT, we are able to reduce the key-space to $2^{64}$. This leads to the best fault attacks on BAKSHEESH and DEFAULT in terms of number of rounds penetrated for fault injection. Our work reiterates the fact that a property induced (in this case LS in SBox)) for some particular Cryptographic purposes (like fault attack resistance) may manifest orthogonally for another (increasing fault penetration) and thus adds value to block cipher design space exploration and fault attack counter-measure development.

The rapid advancements in quantum computing pose a significant threat to widely used cryptographic standards such as RSA and Elliptic-Curve Diffie-Hellman (ECDH), which are fundamental to securing digital communications and protecting sensitive data worldwide. The increasing feasibility of "harvest now, decrypt later" strategies where adversaries collect encrypted data today with the intent of decrypting it once quantum computing reaches sufficient maturity underscores the urgency of transitioning toward quantum-resistant cryptographic solutions. A pragmatic approach to maintaining security during this transitional period is the adoption of hybrid cryptographic techniques, which integrate traditional cryptographic mechanisms with post-quantum cryptography (PQC) and Quantum Key Distribution (QKD). This paper presents a comprehensive review of hybrid cryptographic approaches, focusing on their incorporation into widely adopted security protocols such as TLS 1.3 and QUIC. We examine the key challenges associated with deploying hybrid cryptography, including performance trade-offs, security guarantees, and compatibility with existing infrastructure. Beyond protocol-level implementations, we explore the initiatives undertaken by global standardization bodies and leading technology firms to facilitate a seamless transition toward a quantum-secure future. By analyzing current strategies and insights from early adopters, we identify the critical factors that organizations must consider to effectively implement hybrid cryptographic solutions, ensuring resilience against emerging cryptographic threats.

In our increasingly interconnected world, the security of embedded devices plays a critical role in protecting sensitive information. Evaluating this security requires a meticulous examination of how cryptographic processes are implemented within the hardware of these devices. One widely employed technique for this purpose is Power Side Channel Analysis. At the heart of Correlation Power Side Channel Analysis lies the concept of the power consumption model, which helps to simulate power consumption while executing cryptographic operations on hardware. In this model, along with the hypothetical secret key, is correlated with the actual power consumption during the execution of a cryptographic operation under an unknown secret key. This approach enables the detection of potential vulnerabilities in cryptographic implementations. In this research, we introduce a novel power leakage model called the Technology library Power Leakage Model. This model is rooted in semiconductor technology. By aligning our model closely with specific semiconductor technology, we achieve a more realistic representation of power consumption. Our study provides compelling evidence for the effectiveness of the Power Leakage Model. We successfully extracted secret keys from an AES implementation using Correlation Power Analysis (CPA). Importantly, our Power Leakage Model can be adapted to accommodate various semiconductor technologies such as $55nm$ or $14nm$ technologies. In this work, we also compared the newly proposed leakage model with the Hamming Distance model and empirically evaluated that both models perform similarly when linear correlation techniques are used in CPA.

We introduce time-lock encrypted storage (tTLES), a storage service provided by blockchains. In tTLES, clients store encrypted values towards a future decryption time $\tau_{tgt}$ (measured in block height). The security of tTLES requires that a value is decrypted only if (i) the encrypted value is included in the blockchain, and (ii) the time $\tau_{tgt}$ has passed. This is crucially different from existing schemes, which only enforce either of these conditions but not both. We formalize tTLES, and present an efficient protocol that relies on (in a black-box manner) a threshold identity-based encryption scheme, and a recent batch threshold decryption scheme. Finally, we discuss various applications that will benefit from tTLES.

Homomorphic Encryption (HE) technology allows for processing encrypted data, breaking through data isolation barriers and providing a promising solution for privacy-preserving computation. The integration of HE technology into Convolutional Neural Network (CNN) inference shows potential in addressing privacy issues in identity verification, medical imaging diagnosis, and various other applications. The CKKS HE algorithm stands out as a popular option for homomorphic CNN inference due to its capability to handle real number computations. However, challenges such as computational delays and resource overhead present significant obstacles to the practical implementation of homomorphic CNN inference, largely due to the complex nature of HE operations. In addition, current methods for speeding up homomorphic CNN inference primarily address individual images or large batches of input images, lacking a solution for efficiently processing a moderate number of input images with fast homomorphic inference capabilities, which is more suitable for edge computing applications. In response to these challenges, we introduce a novel leveled homomorphic CNN inference scheme aimed at reducing latency and improving throughput using the CKKS scheme. Our proposed inference strategy involves mapping multiple inputs to a set of ciphertext by exploiting the sliding window properties of convolutions to utilize CKKS's inherent Single-Instruction-Multiple-Data (SIMD) capability. To mitigate the delay associated with homomorphic CNN inference, we introduce optimization techniques, including mask-weight merging, rotation multiplexing, stride convolution segmentation, and folding rotations. The efficacy of our homomorphic inference scheme is demonstrated through evaluations carried out on the MNIST and CIFAR-10 datasets. Specifically, results from the MNIST dataset on a single CPU thread show that inference for 163 images can be completed in 10.4 seconds with an accuracy of 98.9%, which is a 6.9 times throughput improvement over state-of-the-art works. Comparative analysis with existing methodologies highlights the superior performance of our proposed inference scheme in terms of latency, throughput, communication overhead, and memory utilization.

Private Simultaneous Messages (PSM) and Conditional Disclosure of Secrets (CDS) are two fundamental primitives in information-theoretic cryptography. In a PSM protocol, each party sends a single message to a referee, who can then compute a function $f$ of their private inputs but learns nothing else. A CDS protocol follows the same model as PSM, but the goal is to disclose a secret shared among all parties to the referee if and only if the function $f$ evaluates to $1$. Minimizing the communication complexity of these primitives is a central question in this area. Since the best known constructions for general functions require high communication complexity, recent studies have attempted to obtain more efficient constructions by focusing on symmetric functions, whose outputs are invariant under permutations of inputs. However, the extent to which exploiting symmetry can improve efficiency has remained unclear. In this work, we show upper and lower bounds that relate the optimal communication complexities of PSM and CDS for symmetric functions to those for general functions. When the number of parties is larger than the input domain size, our upper bound for PSM improves the best known communication complexity for symmetric functions. Furthermore, our upper bound for CDS demonstrates for the first time that symmetry can be exploited to reduce communication in CDS protocols. In contrast, when the number of parties is constant, our lower bounds show that focusing on symmetric functions yields only a constant-factor improvement. We also derive an analogous implication for PSM protocols under a plausible conjecture. In addition, our new constructions for symmetric functions lead to improvements over the state-of-the-art results in related models such as ad hoc PSM and secret sharing.

Side-channel analysis (SCA) exploits physical leakages such as power consumption or electromagnetic emissions to extract secret information from cryptographic implementations. Leakage model is the critical link between observable physical emanations (e.g., power consumption) and internal cryptographic states. When a leakage model fails to match the device’s underlying physical leakage, even powerful attacks like Correlation Power Analysis (CPA) are rendered ineffective. This fundamental challenge limits the success of traditional SCA, especially against noisy or masked targets. In this work, we introduce the Neural Leakage Model (NLM), a novel neural network architecture trained to learn and accurately characterize complex physical leakage to enhance CPA. Moving beyond NLM's superior attack performance, we directly address the critical ``black box'' problem in deep learning-based side-channel analysis (DLSCA) by proposing a novel methodology to transform the trained NLM into a mathematically equivalent, closed-form polynomial expression. This provides interpretability, offering evaluators transparent insight into the precise leakage model the network has learned. We validate NLM’s performance across four diverse datasets spanning three platforms, from low-end microcontrollers to high-end multi-core ARM systems and dedicated FPGAs. Notably, NLM successfully recovers the secret key from the highly challenging and noisy CHES2025 dataset, representing the first known successful CPA attack on this benchmark. Furthermore, NLM demonstrates superior or comparable performance when extended to higher-order CPA against masking countermeasures. Our findings establish NLM as a powerful, generalizable, and interpretable approach to modern side-channel analysis.

We study linear-time prover SNARKs and make the following contributions: We provide a framework for transforming a univariate polynomial commitment scheme into a multilinear polynomial commitment scheme. Our transformation is generic, can be instantiated with any univariate scheme and improves on prior transformations like Gemini (EUROCRYPT 2022) and Virgo (S&P 2020) in all relevant parameters: proof size, verification complexity, and prover complexity. Instantiating the above framework with the KZG univariate polynomial commitment scheme, we get SamaritanPCS -- the first multilinear polynomial commitment scheme with constant proof size and linear-time prover. The proof size is just 368 bytes, which is the smallest among all multilinear polynomial commitment schemes. Our scheme also has excellent batching properties, wherein proving $k$ evaluations over the hypercube of size n incurs $O(n+k\sqrt{n})$ cryptographic work, resulting in substantially amortized prover work over several evaluations. We construct LogSpartan -- a new multilinear PIOP for R1CS based on recent techniques for lookup arguments. Compiling this PIOP using SamaritanPCS gives Samaritan -- a SNARK in the universal and updatable SRS setting. Samaritan has linear-time prover, logarithmic verification and logarithmic proof size. Concretely, its proof size is one of the smallest among other known linear-time prover SNARKs without relying on concretely expensive proof recursion techniques. For an R1CS instance with 1 million constraints, Samaritan (over the BLS12-381 curve) has a proof size of 6.2KB. We compare Samaritan with other linear-time prover SNARKs in the updatable setting. We asymptotically improve on the $\log^2(n)$ proof size of Spartan. Unlike Libra (CRYPTO 2019), the argument size of Samaritan is independent of the circuit depth. Compared to Gemini (EUROCRYPT 2022), SamaritanPCS achieves $3\times$ smaller argument size at 1 million constraints. We are competitive with the very recently proposed MicroSpartan (S&P 2025) and linear-time SNARKs for the Plonkish constraint system such as HyperPlonk (EUROCRYPT 2023).

The sparse secret Learning with Errors (LWE) problem is a widely used assumption in efficient fully homomorphic constructions. In [Wenger et al. IEEE S\&P 2025] two approaches, `Cool and Cruel’ (C+C) and the machine learning based `SALSA', were benchmarked against the well established primal attack on sparse secrets. The authors concluded that C+C outperforms SALSA and both outperform the primal attack. In this work we show that the apparently novel C+C is an instantiation of a known dual attack [Albrecht, EUROCRYPT 2017]. To argue this we introduce a framework for dimension reduction in the bounded distance decoding problem that may be of independent interest. Furthermore we prove that the C+C `phenomenon' is an expression of the geometry of the well known Z-shape basis in $q$-ary lattices, despite claims to the contrary. We also show that a correctly parametrised primal attack outperforms C+C both in parameter regimes studied by Wenger et al. and in new parameter regimes. To support this claim, we provide an open source implementation of two variants of the primal attack that are relevant for sparse secret LWE: Drop+Solve [May--Silverman, CaLC 2001] and Guess+Verify [Albrecht et al. SAC 2019].

We investigate shift-invariant transformations, also known as rotation-symmetric vectorial Boolean functions, on $n$ bits that are induced from Boolean functions on $k$ bits, for $k\leq n$. We consider such transformations that are not necessarily permutations, but are, in some sense, almost bijective, and study their cryptographic properties. In this context, we define an almost lifting as a Boolean function for which there is an upper bound on the number of collisions of its induced transformation that does not depend on $n$. We show that if a Boolean function with diameter $k$ is an almost lifting, then the maximum number of collisions of its induced transformation is $2^{k-1}$ for any $n$. Moreover, we search for functions in the class of almost liftings that have good cryptographic properties and for which the non-bijectivity does not cause major security weaknesses. These functions generalize the well-known map $\chi$ used in the Keccak hash function.

This paper establishes the computational complexity of the Quasi-Cyclic Syndrome Decoding Problem (QC-SDP). We introduce a novel characterization of Quasi-Cyclic (QC) codes that generalizes their structure and reveals connections to random codes. Building on this characterization, we prove that QC-SDP is NP-hard and that its decision variant is NP-complete. These results provide the first formal complexity treatment of QC-SDP in its general form, addressing a fundamental open question in code-based cryptography. We also discuss the practical implications and limitations of these theoretical findings for cryptographic applications.

The security of many arithmetization-oriented (AO) hash functions depends of the hardness of Constrained-input constrained-output (CICO) problems. These problems have received significant attention from the cryptographic community in recent years, with notable advances in Gröbner basis and resultant-based attacks, yet progress has mainly been limited to CICO problems restricted to a single output. In this work, we build on the "FreeLunch method" of Bariant et al. (Crypto 2024) that constructs Gröbner bases "for free" in this particular case, and extend it to CICO problems with multiple outputs. More precisely, we consider tools for solving weighted polynomial systems, and show how to apply them in the AO setting. This results in new polynomial modelings, more efficient methods for computing the initial Gröbner basis under certain assumptions, and improved complexity estimates for the change of ordering step, derived from tighter upper bounds on the ideal degree. We apply our framework to Poseidon, Neptune and XHash8, where our assumptions are experimentally verified, and theory matches practice. For Griffin and ArionHash our assumptions are not verified, leaving us with improved, yet loose, upper bounds on the ideal degree. While our results do not threaten the security of any full-round hash function, they provide new insights into the security of these primitives under more general CICO problems.

Anonymous payment protocols based on Zerocash (IEEE S&P 2014) have seen widespread deployment in decentralized cryptocurrencies, as have derivative protocols for private smart contracts. Despite their strong privacy properties, these protocols have a fundamental scaling limitation in that they require every consensus participant to maintain a perpetually growing set of nullifiers --- unlinkable revocation tokens used to detect double-spending --- which must be stored, queried and updated by all validating nodes. This set grows linearly in the number of historic transactions and cannot be discarded without the undesirable effect of destroying unspent funds. In this short note, we introduce a new technique that enables continual, permanent pruning of nullifiers by validators, without imposing significant computation, bandwidth or latency overhead for users, and without compromising privacy. Our main contribution is a general model we call oblivious synchronization, whereby users ask untrusted remote services (which ingest and process the public ledger) to create succinct proofs that coins are unspent and otherwise valid. Crucially, these services are fully oblivious to their clients' transaction details and cannot link their clients to any transactions that ultimately appear on the public ledger. Moreover, these services only keep ephemeral state per client and users can freely switch between services without incurring redundant computational effort.

This work addresses the problem of Byzantine Fault-Tolerant (BFT) Total-Order Broadcast (TOB) in a dynamically available setting, where parties can transition between online and offline states without knowing the number of active parties. Existing dynamically available protocols rely on a synchronous network assumption, which means their latency remains tied to the pessimistic network delay $\Delta$, even when the actual network delay is $\delta << \Delta$. This raises the question of whether a dynamically available BFT TOB protocol can maintain safety and liveness under synchrony while committing blocks at a rate closer to the actual network delay. We answer this question affirmatively by designing the first dynamically available BFT TOB protocol that can commit blocks at the rate of $O(\Delta_{ideal})$ where $\Delta_{ideal} < 2\delta$.

We revisit multivariate commitments based on the hardness of solving systems of multivariate quadratic (MQ) equations over finite fields. We analyze a simple construction where a message µ is committed as c = (µ + F(r), G(r)), with F and G random quadratic maps. We prove that the scheme is computationally hiding assuming the intractability of the MQ problem. Its binding property reduces to solving random bilinear systems. We prove that this problem is NP-complete and study the performance of existing algebraic and hybrid attacks. We show that this commitment is well-suited for integration with zero-knowledge proofs. Using the Threshold-computation-in-the-Head framework, we construct zero-knowledge efficient arguments of knowledge for the opening and arguments for relations on committed values. We apply this to construct an efficient blind signature scheme à la Fischlin, and we demonstrate that our techniques yield a fully multivariate construction of signatures with efficient protocols, enabling practical post-quantum anonymous credentials.

ZK-SNARKs, a fundamental component of privacy-oriented payment systems, identity protocols, or anonymous voting systems, are advanced cryptographic protocols for verifiable computation: modern SNARKs allow to encode the invariants of a program, expressed as an arithmetic circuit, in an appropriate constraint language from which short, zero-knowledge proofs for correct computations can be constructed. One of the most important computations that is run through SNARK systems is the verification of Merkle tree (MT) opening proofs, which relies on the evaluation of a fixed-input-length (FIL) cryptographic compression function over binary MTs. As classical, bit-oriented hash functions like SHA-2 are not compactly representable in SNARK frameworks, Arithmetization-Oriented (AO) cryptographic designs have emerged as an alternative, efficient solution. Today, the majority of AO compression functions are built from the Sponge permutation-based hashing mode. While this approach allows cost savings, compared to blockcipher-based modes, as it does not require key-scheduling, AO blockcipher schedulers are often cheap to compute. Furthermore, classical bit-oriented cryptography has long studied how to construct provably secure compression functions from blockciphers, following the Preneel-Govaerts-Vandewalle (PGV) framework. The potential efficiency gains together with the strong provable security foundations in the classic setting, motivate the study of AO blockcipher-based compression functions. In this work, we propose PGV-LC and PGV-ELC, two AO blockcipher-based FIL compression modes inspired by and extending the classical PGV approach, offering flexible input and output sizes and coming with provable security guarantees in the AO setting. We prove the collision and preimage resistance in the ideal cipher model, and give bounds for collision and opening resistance over MTs of arbitrary arity. We compare experimentally the PGV-ELC mode over the HADES blockcipher with its popular and widely adopted Sponge instantiation, Poseidon, and its improved variant Poseidon2. Our resulting constructions are up to 3× faster than Poseidon and 2× faster than Poseidon2 in native x86 execution, up to 1.5× faster in the Groth16 SNARK framework, and up to 1.9× faster in the Plonky2 framework. Finally, we study the benefits of using MTs of arity wider than two, proposing a new strategy to obtain a compact R1CS constraint system in such case. In fact, by combining an efficient parametrization of the HADES blockcipher over the PGV-ELC mode, together with an optimal choice of the MT arity, we measured an improvement of up to 9× in native MT construction time, and up to 2.5× in proof generation time, compared to Poseidon over binary MTs.

Healthcare data sharing is fundamental for advancing medical research and enhancing patient care, yet it faces significant challenges in privacy, data ownership, and interoperability due to fragmented data silos across institutions and strict regulations (e.g., GDPR, HIPAA). To bridge these gaps, we propose MtDB, a novel decentralized database architecture addressing secure data sharing in multi-tenant database ecosystems. MtDB employs blockchain for metadata coordination and sharing, IPFS for distributed data addressing, a universal SQL query interface for data access, and Intel SGX for integrity-protected query execution with enforced access control. We provide an open-source implementation demonstrating MtDB’s capabilities for secure, patient-centric healthcare data sharing while preserving ownership and enforcing policies. Experimental results show MtDB achieves 35 milliseconds query latency for indexed queries over 400M multi-tenant medical records while maintaining cryptographic security guarantees, with only 1.2–1.3× performance overhead compared to non-secure baselines.

Electronic voting systems claiming to provide verifiability are seeing increased adoption. Previous work on analyzing these systems has focused on vulnerabilities arising in the specification and implementation of the core protocol and primitives; once the system has been analyzed for these vulnerabilities and appropriate fixes deployed, one might have hoped that the systems would provide the claimed security. In this paper, we discuss two categories of vulnerabilities which still seem prevalent in otherwise carefully designed, implemented, and audited systems. We present ten examples of vulnerabilities or weaknesses in these categories drawn from the SwissPost and Belenios systems. Our discussion covers why vulnerabilities in these categories maybe escaping detection and what can be done about it; all the solutions we considered are unsatisfactory and our aim is to highlight this area as an important open problem.

MEV (Maximal Extractable Value) remains one of the most corrosive forces in blockchain systems, enabling frontrunning, sandwiching, and other manipulations that directly exploit users. The core culprit is the transparent mempool: validators see transactions before they are ordered. Encrypted mempools are a promising solution by hiding transaction contents until after ordering. We present the first integration of encrypted mempools with a high-performance BFT protocol. Our system uses a cryptographic scheme based on recent work on batched threshold encryption, and improves on the cryptographic state of the art in this line of work. The system ensures confidentiality of transactions during ordering while sustaining performance on par with leading BFT designs. Specifically, the proposal-to-execution latency of our system yields only a 27 ms overhead (14%) compared to the baseline. The result is a practical consensus layer that simultaneously defends against MEV and delivers the throughput and latency needed for real deployments. This work closes the gap between cryptographic defenses and production-ready consensus, showing that robust MEV protection and high performance can, in fact, coexist.

The ARADI block cipher is developed by the U.S. National Security Agency (NSA) as part of its efforts to design secure and efficient cryptographic algorithms. In this paper, we present the first detailed analysis of the lightweight block cipher ARADI under differential fault attacks. Although ARADI is structured around word-wise operations, its security fundamentally depends on bit-level properties, making it vulnerable to carefully crafted fault models. Bit-based fault models require a large number of faults, while word-based models reduce the number of faults but make precise identification of fault locations difficult. To overcome these limitations, we introduce a new nibble-based approach using permissible nibble differences (PNDs). This model provides an effective tradeoff between the number of required faults and the complexity of identifying fault positions. In our attack, the adversary randomly injects nibble faults before the last two rounds and constructs differential equations involving unknown key variables without knowing the exact fault values. Our results demonstrate that, with at most 108 random fault injections, the entire master key of ARADI can be recovered within a practical time complexity. This work reveals previously unexplored vulnerabilities of ARADI under fault attacks and highlights the need to evaluate lightweight cipher designs using nibble-level fault models, along with the traditional bit- and word-level analyses.

Side-channel attacks can uncover sensitive data by analyzing information leakages of cryptographic hardware devices caused by the power consumption, timing, electromagnetic, glitches, etc. An attack exploiting these leakages is the differential power analysis (DPA). Threshold Implementation (TI), introduced by Nikova et al. [JoC 24(2):292-321, 2011], was proposed to resist DPA on hardware implementations of block ciphers and eliminate information leakage due to glitches. TI is based on secret sharing and multi-party computation. Since the cost of implementing a TI is directly proportional to the number of shares, minimizing the number of shares is of importance. Note that Nikova et al. proved that, for a target function of algebraic degree $t\geq 2$, the lower bound on the number of shares to implement a TI is $t+1$. And we call a TI with $t+1$ shares an optimal TI. However, achieving this bound is challenging. To date, the only universal construction for any bijective function of algebraic degree $t\geq 2$ achieves a TI with $t+2$ shares, which was proposed by Piccione et al. [IEEE TIT 69(10):6700-6710, 2023]. Only two studies managed to implement optimal TIs. They either concentrated on the Feistel structure or were based on Shannon's expansion. It should be noted that adding randomness can meet the $t+1$ bound, but generating randomness is expensive in practice. Consequently, this paper endeavors to fill this gap by systematically investigating the substitution-boxes (S-boxes to be brief) that can achieve optimal TIs without additional randomness. In this paper, inspired by the Feistel structure in the design of S-boxes, we present two constructions of bijective S-boxes with optimal TIs. Of particular interest is the S-boxes constructed from two permutations exhibiting nonzero nonlinearity, making them potential candidates for S-boxes with desirable properties. For applications, our constructions can interpret the existence of $3$-share or $4$-share TIs for certain functions in $3$, $4$ and $5$ variables, as previously reported by Bilgin et al. [CHES 7428:76-91, 2012] and Božilov et al. [ToSC 2017(1):398-404, 2017], including $\mathcal{Q}_5^{25}$, which cannot be interpreted by the previous works. We also give the bijective S-boxes, which are Examples 4 to 11, that possess the optimal TIs by our results.

For computing square roots in a finite field $GF(q)$ where $q - 1 = 2^n m$ for an odd integer $m$ and some integer $n$, the classic Tonelli-Shanks algorithm starts with an exponentiation (the exponent has size about $\log_2 q - n$ bits), followed by a discrete logarithm computation in the subgroup of $2^n$-th roots of unity in $GF(q)$; the latter operation has cost $O(n^2)$ multiplications in the field, which is prohibitive when $n$ is large. Bernstein proposed an optimized variant with lookup tables, leading to a runtime cost of $O((n/w)^2)$, using $w$-bit tables of cumulative size $O(2^w n/w)$. Sarkar recently improved on the runtime cost, down to $O((n/w)^{1.5})$, with the same overall storage cost. In this short note, we explore the use of a straightforward divide-and-conquer variant of the Pohlig-Hellman algorithm, bringing the asymptotic cost down to $O(n\log n)$, and further study some additional optimizations. The result appears to be competitive, at least in terms of number of multiplications, for some well-known fields such that the 224-bit field used in NIST standard elliptic curve P-224 (for which $n = 96$).

Private information retrieval (PIR) allows a client to query a public database privately and serves as a key building block for privacy-enhancing applications. Minimizing query size is particularly important in many use cases, for example when clients operate on low-power or bandwidth-constrained devices. However, existing PIR protocols exhibit large query sizes: to query $2^{25}$ records, the smallest query size of 14.8KB is reported in Respire [Burton et al., CCS'24]. Respire is based on fully homomorphic encryption (FHE), where a common approach to lower the client-to-server communication cost is transciphering. When combining the state-of-the-art transciphering [Bon et al., CHES'24] with Respire, the resulting protocol (referred to as T-Respire) has a 336B query size, while incurring a 16.2x times higher server computation cost than Respire. Our work introduces a novel alternative to transciphering for reducing the client-to-server communication: the client transmits only one component of a high-precision LWE ciphertext, from which we design a modular procedure to extract the inputs for the subsequent homomorphic computation. The efficiency of this approach is demonstrated by our Pirouette protocol, which achieves a query size of just 36B. This represents a 9.3x reduction compared to T-Respire and a 420x reduction to Respire. For queries over $2^{25}$ records, the single-core server computation in Pirouette is only 2x slower than Respire and 8.1x faster than T-Respire, and the server computation is highly parallelizable. Furthermore, Pirouette requires no database-specific hint for clients, and its variant PirouetteH enables additional tradeoffs among query size, throughput, and offline communication, demonstrating the flexibility of our design.

Embedded devices commonly rely on digital signatures to ensure both integrity and authentication. For example, digital signatures are typically verified during the boot process or firmware updates to verify the integrity of a system. They are also used to ensure authenticity of a communication party in secure protocols. Fault injection can be used to tamper with a device in order to cause malfunctioning during cryptographic computations. For example, fault injections can be used to disturb digital signing operations. With the right type of fault an attacker can compute private keys from faulted signatures. However, fault injections can also be used during verification to get maliciously crafted digital signatures accepted during signature verification with catastrophic consequences for the security of an embedded device. In this paper, we introduce new non-obvious fault injection attacks on the verification routines of Dilithium and Falcon signature schemes, which allow an attacker to get signatures for arbitrary messages accepted by fault injection. We demonstrate the feasibility of our attacks by simulations using an ARM Cortex-M4 and the pqm4 library as a target of evaluation and pinpoint vulnerable instructions. Finally, we propose and discuss possible countermeasures against these attacks.

In 2012, the Tor project expressed the need to upgrade Tor’s onion encryption scheme to protect against tagging attacks and thereby strengthen its end-to-end integrity protection. Tor proposal 261, where each encryption layer is processed by a strongly secure, yet relatively expensive tweakable wide-block cipher, is the only concrete candidate replacement to be backed by formal, yet partial, security proofs (Degabriele and Stam, EUROCRYPT 2018, and Rogaway and Zhang, PoPETS 2018). We identify the functionality and security desiderata for Tor’s onion encryption, and propose an alternative onion encryption scheme, called Counter Galois Onion (CGO), that follows a minimalistic, modular design and includes several improvements over proposal 261. CGO’s underlying primitive is an updatable tweakable split-domain cipher accompanied with a new security notion, that augments the recently introduced rugged pseudorandom permutation (Degabriele and Karadžić, CRYPTO 2022). Thus, we relax the security compared to a tweakable wide-block cipher, allowing for more efficient designs. We show that our security notion for updatable tweakable split-domain ciphers successfully hybridizes, which allows us to argue informally that CGO meets the full security requirements. Finally, we suggest a concrete instantiation for the updatable tweakable split-domain cipher, called UIV+, prove its security, and benchmark our full CGO scheme against Tor’s existing onion encryption scheme, demonstrating a clear performance gain at the proxy and at exit and entry routers, at the expense of a mild slowdown at intermediate routers.

Recent advances in fast protocols for \textit{vector oblivious linear evaluation} (VOLE) have inspired a family of new VOLE-based lightweight designated-verifier NIZK protocols (Weng et al., S\&P 2021, Baum et al., Crypto 2021, Dittmer et al., ITC 2021, Yang et al., CCS 2021). In particular, the Line-Point Zero Knowledge (LPZK) protocol of Dittmer et al.\ has the advantage of being entirely non-cryptographic given a single instance of a random VOLE correlation. We present improvements to LPZK through the introduction of additional structure to the correlated randomness. Using an efficiently realizable variant of the VOLE correlation, we reduce the online proof size of LPZK by roughly 2x: from roughly 2 field elements per multiplication gate, or 1 element in the random oracle variant, to only 1 or $\tfrac{1}{2}$ elements respectively. In particular, we get the first practical VOLE-based NIZK that breaks the 1-element-per-multiplication barrier. We implemented an optimized version of our protocol and compared it with other recent VOLE-based NIZK protocols. In the typical case where communication is the bottleneck, we get at least 2x performance improvement over all previous VOLE-based protocols. When prover computation is the bottleneck, we outperform all non-LPZK protocols by at least $2$-$3$x and (our optimized implementation of) LPZK by roughly 30%, obtaining a $2$-$3$x slowdown factor compared to plain circuit evaluation.

A variety of cryptographic applications are enabled by the properties of bilinear pairings on elliptic curves. Thus, efficient pairing computation is of crucial importance for practical deployments of pairing-based cryptographic protocols. One of the most important technical approaches is to construct pairing variants with short Miller loops in efficiency. Driven by this motivation, the variants of Tate pairings such as the ate and the optimal ate pairings, are successively proposed. Moreover, on specific pairing-friendly curves admitting efficiently computable automorphisms, the number of basic Miller iterations can be further reduced to $\log_2(r)/2\varphi(k)$, where $\varphi$ and $k$ denote the Euler's totient function and the embedding degree with respect to $r$, respectively. Such pairings are named as the super-optimal ate pairings. Nevertheless, several curves are not compatible with the existing methods for constructing super-optimal ate pairings as they admit no non-trivial automorphisms. This paper aims to establish a framework for constructing super-optimal ate pairings on more pairing-friendly curves employing degree-$n$ endomorphisms with $n > 1$. In practice, small degree endomorphisms (e.g. $n = 2, 3$) can be computed efficiently and are primarily considered for enhancing the performance of pairing computations. More precisely, pairing-friendly curves with CM-discriminants $7$ and $11$ are equipped with degrees-$2$ and $3$ endomorphisms, respectively, possessing the potential for constructing super-optimal ate pairings. For example, we exploit degree-$2$ endomorphism (resp. degree-$3$ endomorphism) and provide explicit formulas for the super-optimal ate pairings on family GG22D7 with CM-discriminant \(D = 7\) and embedding degree \(k = 22\) (resp. GG28D11 with CM-discriminant \(D = 11\) and embedding degree \(k = 28\)). Additionally, we select a pairing-friendly curve GG22D7-457 at the 192-bit security level for implementation, and present detailed computational procedure, concrete cost analysis, together with the experimental results. The results illustrate that our new super-optimal pairing formula derives a saving of about \(31.9\%\) \(\mathbb{F}_{p}\)-multiplications for the Miller loop on GG22D7-457 compared to the previous method. In terms of CPU clock cycles, leveraging our new formula is $26.0\%$ faster. This work expands the application of super-optimal pairings, and thus offer a broader range of choices of curves for pairing-based cryptography.

No $t$-resilient Byzantine Agreement (or Reliable Broadcast) protocol can guarantee agreement among $n$ correct processes in a non-synchronous network if the actual number of faulty processes $f$ is $\geq n - 2t$. This limitation highlights the need to augment such fragile protocols with mechanisms that detect safety violations, such as forensic support and accountability. This paper introduces simple and efficient techniques to address this challenge by proposing a new generic transformation, $\mathcal{ABC}^{++}$. The transformation leverages two key primitives: $\textit{ratifier}$ and the $\textit{propagator}$. By sequentially composing these primitives with any closed-box Byzantine Agreement (or Reliable Broadcast) protocol, $\mathcal{ABC}^{++}$ produces a robust counterpart that provides both (adaptively-secure) forensic support and ($1$-delayed adaptively-secure) accountability. The transformation incurs a subquadratic additive communication overhead, with only $1$ round of overhead for decision and forensic support, and $2$ additional rounds for detection in case of a safety violation (or $O\big(\log n \big)$ additional rounds with optimized communication). The generality of $\mathcal{ABC}^{++}$ offers a compelling general alternative to the subquadratic forensic support solution by Sheng et al. (FC'23) tailored to HotStuff-like protocols, while being more efficient than the (strongly-adaptively-secure) quadratic $\mathcal{ABC}$ accountable transformation (IPDPS'22, JPDC'23). Moreover, it provides the first subquadratic accountable Byzantine Agreement (or Reliable Broadcast) protocols against a ($1$-delayed) adaptive adversary. Finally, any subquadratic accountable Reliable Broadcast protocol can be integrated into the $\tau_{scr}$ transformation (ICDCS'22) to produce an improved variant, $\tau_{scr}^{++}$. This new version compiles any deterministic (and even beyond) protocol into its accountable counterpart with subquadratic multiplicative communication overhead, significantly improving upon the original quadratic overhead in $\tau_{scr}$.

Rejection sampling is a crucial security mechanism in lattice-based signature schemes that follow the Fiat-Shamir with aborts paradigm, such as ML-DSA/CRYSTALS-Dilithium. This technique transforms secret-dependent signature samples into ones that are statistically close to a secret-independent distribution (in the random oracle model). While many side-channel attacks have directly targeted sensitive data such as nonces, secret keys, and decomposed commitments, fewer studies have explored the potential leakage associated with rejection sampling. Notably, at HOST 2021, Karabulut \etal showed that leakage from rejected signatures' challenges can undermine, but not entirely break, the security of the Dilithium scheme. Motivated by the above, we convert the problem of key recovery (from the leakage of rejection sampling) to an integer linear programming problem (ILP), where rejected responses of unique Hamming weights set upper/lower constraints of the product between the challenge and the private key. We formally study the worst-case complexity of the problem as well as empirically confirm the practicality of the rejected signature's challenge attack. For all three security levels of Dilithium-2/3/5, our attack recovers the private key in seconds or minutes with a 100\% Success Rate (SR). Our attack leverages knowledge of the rejected signature's challenge and response, and thus we propose methods to extract this information by exploiting single-trace side-channel leakage from Number Theoretic Transform (NTT) operations and functions associated with the response generation procedure. We demonstrate the practicality of this rejected signature's challenge attack by using real power consumption on an ARM Cortex-M4 microcontroller. To the best of our knowledge, it is the first practical and efficient side-channel key recovery attack on ML-DSA/Dilithium that targets the rejection sampling procedure. Furthermore, we discuss some countermeasures to mitigate this security issue.

Hyperelliptic curve cryptography (HECC) is a candidate to standardization which is a competitive alternative to elliptic curve cryptography (ECC). We extend Regev's algorithm to this setting. For genus-two curves relevant to cryptography, this yields a quantum attack up to eight times faster than the state-of-the-art. This implies that HECC is slightly weaker than ECC. In a more theoretical direction, we give a mathematical proof that Regev's algorithm obtains its full speedup with respect to Shor's when the genus is high, a setting which is already known to be inadequate for cryptography.

End-to-end encrypted (E2EE) messaging platforms serving hundreds of millions of users face a fundamental vulnerability: users must trust service providers to distribute authentic public keys. This problem creates opportunities for sophisticated man-in-the-middle attacks and surveillance. While key transparency systems promise to eliminate this trust requirement, existing solutions have failed to achieve practical deployment due to prohibitive cost in computation and bandwidth, and inadequate infrastructure. Our main innovation is the integration of a zero-knowledge virtual machine to create a “rollup” architecture on a third-party data availability layer via which every user automatically checks the integrity of the whole key directory. Counterintuitively, this approach yields substantial performance improvements over custom-built zk proof circuits and enables verification of targeted policies within the cryptographic proof system. We introduce PRISM, the first practically deployable key transparency protocol that eliminates hidden backdoors in E2EE services through automatic, trust-minimized verification. Our system advances beyond previous approaches by proving not just structural validity of key directory updates, but their semantic correctness as well. Previous solutions require some form of manual interaction by the user. This burden prevented wide spread adoption. Our solution however eliminates user intervention entirely. This paper is intended as an overview rather than an exhaustive specification. Our implemented system already integrates additional components whose full complexity exceeds the scope of this short presentation.

Blind signature schemes are essential for privacy-preserving applications such as electronic voting, digital currencies or anonymous credentials. In this paper, we revisit Fischlin's framework for round-optimal blind signature schemes and its recent efficient lattice-based instantiations. Our proposed framework compiles any post-quantum hash-and-sign signature scheme into a blind signature scheme. The resulting scheme ensures blindness by design and achieves one-more unforgeability, relying solely on the unforgeability of the underlying signature scheme and the random oracle model. To achieve this we introduce the notion of commit-append-and-prove (CAP) systems, which generalizes traditional commit-and-prove system by making their commitments updatable before proving. This building block allows us to unlock the technical challenges encountered when generalizing previous variants of the Fischlin's framework to any hash-and-sign signature scheme. We provide efficient CAP system instantiations based on recent MPC-in-the-Head techniques. We showcase our framework by constructing blind versions of UOV and Wave, thereby introducing the first practical blind signatures based on multivariate cryptography and code-based cryptography. Our blind UOV signatures range from 3.8 KB to 11 KB, significantly outperforming previous post-quantum blind signatures, such as the 22 KB lattice-based blind signatures, which were the most compact until now.

Deep learning-based profiled side-channel analysis (SCA) targeting cryptographic implementations has attracted significant attention in recent years. Generalizable deep learning mechanisms, such as contrastive learning-based profiled SCA (CL-SCA), can enhance the effectiveness of SCA without reliance on specific network architectures and hyperparameters. This independence enables robust adaptation across diverse attack scenarios. Nonetheless, CL-SCA relies heavily on data augmentation and may mistakenly push apart physical leakage traces that should belong to the same class, which interferes with the extraction of discriminative features crucial for SCA performance. To address these limitations, we propose a profiled SCA method based on supervised contrastive learning, called SupCL-SCA. This method enhances the learning of discriminative features that facilitate key recovery by leveraging supervised information to guide the extraction of similarities in feature space. Compared with state-of-the-art methods, SupCL-SCA not only retains their general applicability and inherent advantages but also eliminates reliance on complex data augmentation and multi-stage training. Additionally, we propose a cosine distance-based Intra-Inter Distance Ratio (IIDR) metric to assess the discriminative capability of models in deep learning-based profiled SCA methods. We evaluate SupCL-SCA on three publicly available datasets covering different implementations and platforms. Experimental results show that SupCL-SCA consistently reduces the number of traces required to recover the key compared to the original methods, demonstrating enhanced attack capability.

Cryptography is a fundamental building block of many security features like secure boot, remote attestation, trusted platform module (TPM), memory/disk encryption, and secure communication, providing confidentiality, data integrity, authentication, and non-repudiation. Post-Quantum Cryptography (PQC) marks an important milestone in the history of modern cryptography. It encompasses cryptographic algorithms designed to withstand cryptanalytic attacks from both quantum and classical computers. Organizations around the world are currently in the process of migrating to the PQC algorithms standardized by the National Institute of Standards and Technologies (NIST). Compared to the previous changes of cryptographic algorithms, the transition to PQC poses new challenges. We exemplify some of them by analyzing implementation attacks (e.g., side-channel and fault injection) and countermeasures applicable to the signature generation of the Elliptic Curve Digital Signature Algorithm (ECDSA), a widely used cryptographic algorithm, and the Module-Lattice-Based Digital Signature Algorithm (ML-DSA), a quantum-resistant algorithm set to replace the former.

We compare three recent works on collusion deterrence mechanisms [SP'24, Eurocrypt'25, CCS'25] in privacy-preserving multi-party computations. They follow the same whistleblowing structure where an evidence collection module collects collusion evidence, and a mechanism assigns payments to deter incentive-driven parties from collusion. For evidence collection module, two works [SP'24, Eurocrypt'25] provide a general method for generating collusion evidence while tolerating pre-existing leakage. The other work [CCS'25] abstracts evidence generation away, except for transparent service applications where the output is treated as the evidence. For the incentive mechanisms, two works [SP'24, Eurocrypt'25] consider a mix of rational and malicious parties, and rational parties can act as an individual or as a member of a strong coalition, inside which parties trust each other and never harm other members. When parties act as individuals, given bounded malicious parties, one can design mechanisms to disincentivize collusion. When parties act as a coalition, the mechanisms can only limit the size of coalitions for exclusive secrets, i.e., more parties learning the secret reduces the value received by individuals. The most recent work [CCS'25] only models rational parties but considers colluding parties establishing retaliatory contracts to discourage betrayal among colluders. It was shown to be impossible to maintain non-collusion outcome if retaliatory contracts can impose unbounded penalties, and feasible to guarantee non-collusion otherwise. This is weaker than a strong coalition but admits mechanisms protecting secrets of a general nature.

Private Set Intersection (PSI) protocols allow a querier to determine whether an item exists in a dataset without revealing the query or exposing non-matching records. It has many applications in fraud detection, compliance monitoring, healthcare analytics, and secure collaboration across distributed data sources. In these cases, the results obtained through PSI can be sensitive and even require some kind of downstream computation on the associated data before the outcome is revealed to the querier, computation that may involve floating-point arithmetic, such as the inference of a machine learning model. Although many such protocols have been proposed, and some of them even enable secure queries over distributed encrypted sets, they fail to address the aforementioned real-world complexities. In this work, we present the first encrypted label selection and analytics protocol construction, which allows the querier to securely retrieve not just the results of intersections among identifiers but also the outcomes of downstream functions on the data/label associated with the intersected identifiers. To achieve this, we construct a novel protocol based on an approximate CKKS fully homomorphic encryption that supports efficient label retrieval and downstream computations over real-valued data. In addition, we introduce several techniques to handle identifiers in large domains, e.g., 64 or 128 bits, while ensuring high precision for accurate downstream computations. Finally, we implement and benchmark our protocol, compare it against state-of-the-art methods, and perform evaluation over real-world fraud datasets, demonstrating its scalability and efficiency in large-scale use case scenarios. Our results show up to 1.4$\times$ to 6.8$\times$ speedup over prior approaches and select and analyze encrypted labels over real-world datasets in under 65 sec., making our protocol practical for real-world deployments.

Although the lattice-estimator predicts that Learning with Errors instances having small and very sparse secrets can be broken by hybrid attacks with modest computational resources, no efficient open-source implementation of these attacks exists. This work implements the so-called Guess + Verify attack (G+V) analysed by Albrecht et al. (SAC'19), containing three improvements: (1) cuBLASter, a GPU-based implementation of the lattice basis reduction software BLASter by Ducas et al. (ASIACRYPT'25); (2) a dimension reduction technique for the BDD instance; and (3) a batched variant of Babai’s Nearest Plane algorithm. On bases of dimension 512 and above, cuBLASter outperforms BLASter. We also integrate the GPU implementation of the General Sieve Kernel by Ducas et al. (EUROCRYPT'21) into cuBLASter’s BKZ framework. Running G+V on the benchmark instances by Wenger et al. (IEEE SP'25), we show that G+V achieves significantly higher success rates than the Cool&Cruel attack (C+C) by Nolte et al. (AFRICACRYPT'24) on almost all instances, and G+V's average CPU and GPU utilization is substantially lower than the minimum reported by C+C.

With the widespread deployment of machine learning services, concerns about potential misconduct by service providers have emerged. Providers may deviate from their promised methodologies when delivering their services, undermining customer trust. Zero-knowledge proofs (ZKPs) offer a promising solution for customers to verify service integrity while preserving the intellectual property of the model weights. However, existing ZKP systems for convolutional neural networks (CNNs) impose significant computational overhead on the prover, hindering their practical deployment. To address this challenge and facilitate real-world deployment of ZKPs for CNNs, we introduce VerfCNN, a novel and efficient ZKP system for CNN inference. The core innovation of VerfCNN lies in a specialized protocol for proving multi-channel convolutions, achieving optimal prover complexity that matches the I/O size of the convolution. Our design significantly reduces the prover overhead for verifiable CNN inference. Experiments on VGG-16 demonstrate that our system achieves a prover time of just 12.6 seconds, offering a 6.7× improvement over zkCNN (CCS'21). Remarkably, VerfCNN incurs only a 10× overhead compared to plaintext inference on CPU, whereas general-purpose zkSNARKs typically impose overheads exceeding 1000×. These results underscore VerfCNN's strong potential to enhance the integrity and transparency of real-world ML services.

Multi-party Private Set Intersection (mPSI) enables $n(n\geq3)$ parties, each holding a set of size $m$, to jointly compute their intersection while preserving the confidentiality of each set, which is essential for privacy-preserving data analysis and secure database queries. Existing mPSI protocols have limitations in achieving both sufficient security and practical efficiency. This paper presents a novel and efficient mPSI construction in the semi-honest model while resisting arbitrary collusion attacks. Our construction works in the offline/online paradigm. Given the corruption threshold $t$, the online phase achieves linear total computational and communication complexity, that is $O((n+t)m)$, and solely uses symmetric operations. This makes our construction theoretically outperform the existing works. The technical core of the construction is our newly extracted primitive called reducible zero-sharing, which allows $t(t<n)$ parties to obtain shares of zero for items in the intersection of $n$ parties' input set, while resisting up to $t-1$ colluding parties. We present a practical construction of reducible zero-sharing in the offline/online paradigm by leveraging the homomorphic property of oblivious key-value store (OKVS). With extensive experiments, we demonstrate that our construction outperforms state-of-the-art works in terms of online running time and communication cost. Specifically, compared to works with sufficient security, the online running time of our mPSI construction is $9.57-114.46\times$ faster in the LAN setting, $2.69-28.41\times$ faster in the WAN setting, while the communication cost is $0.29-28.70\times$ lower. Notably, the total performance (offline+online) still obtains up to $18.73\times$ improvement. Compared with works with practical efficiency, our mPSI construction achieves similar performance while providing stronger security.

Migration to quantum-safe cryptography represents a significant technological shift, addressing the vulnerabilities of traditional cryptographic primitives, such as KEMs and digital signatures. Yet, a number of challenges remain, especially in the development of secure solutions for sophisticated cryptographic applications. One of them is Smart-ID, European server-supported (threshold) signing service. To address this issue, we present $\textsf{Electrum}$, a fail-stop server-supported signature scheme designed to enhance security of existing Smart-ID service. $\textsf{Electrum}$ combines multiprime RSA-based signatures with fail-stop features: providing not only unforgeability against classical adversaries but also allowing to prove that a given signature is a forgery made by classical and/or quantum adversaries. Proposed protocol can be seen as a temporary remedy against the quantum threat until standardised threshold signature schemes become a common practice. To prove security of $\textsf{Electrum}$, we introduce a new ideal functionality $\mathcal{F}^{\textsf{SplFS}}$ for a fail-stop server-supported signing in the Universal Composability model. We show that $\textsf{Electrum}$ protocol securely realizes the proposed functionality $\mathcal{F}^{\textsf{SplFS}}$.

State-of-the-art actively secure multiparty computation protocols, like SPDZ (Damgård et al., CRYPTO 2012), use correlated randomness, like Beaver triples, to achieve a highly efficient online phase. For a long time, the generation of the correlated randomness in the offline phase relied on classical cryptographic primitives, like somewhat homomorphic encryption or oblivious transfer, that required significant communication. More recently, Boyle et al. (FOCS 2020) defined a new primitive called pseudorandom correlation functions (PCFs) to generate correlated randomness non-interactively. PCFs set up keys for each party in an initial interactive phase, which can then be used by the parties to generate a large number of shares of the correlated randomness without further communication. In the random oracle model (ROM), two-party PCFs can be generically constructed based on evaluating a weak pseudorandom function (WPRF) using a powerful-enough homomorphic secret sharing scheme. However, the concrete efficiency of instantiations of this approach has not been analyzed so far. There are also some works that construct PCFs based on other approaches, but they cannot be used for correlations of degree $\ge 2$ (e.g., Beaver triples) over large rings/fields (such as those used in SPDZ). In this paper, we improve the complexity and concrete efficiency of PCFs over large rings/fields by presenting a new generic PCF based on the hardness of the ring-learning with rounding (Ring-LWR) problem and FHE. We only share BFV keys in the initial interactive phase. The two parties then use the random oracle to locally sample BFV (pseudo-)ciphertexts encrypting pseudorandom plaintexts. We use a new bootstrapping algorithm for these (pseudo-)ciphertexts that reduces initially saturated noise to a level where the parties can use the homomorphic properties of the BFV scheme to correlate the encrypted randomness locally. Both parties can then produce, without further interaction, shares of the correlated randomness with their secret key share. Our new PCF works with any form of correlated randomness that can be expressed as an arithmetic circuit over a base ring $\mathbb Z_t$ or field $\mathbb F_{p^d}$, e.g., Beaver or matrix triples.

We construct a pseudorandom correlation function (PCF) for oblivious linear evaluation (OLE) from sparse LPN over any finite field. The programmability property of our PCF implies a PCF for any multiparty degree-two correlation, e.g., Beaver triples. Our PCF is the first PCF for degree-two correlations from a well-established cryptographic assumption, apart from (inefficient) generic PCFs based on homomorphic secret sharing or fully homomorphic encryption. Our PCF outperforms the previously fastest PCF for Beaver triples (Boyle et al., Crypto 2022) by 3.2-28x. We build on the recent pseudorandom correlation generator (PCG) by Miao et al. (Asiacrypt 2025) and extend it to a PCF using a recursive approach similar to Braun et al. (Asiacrypt 2025). Moreover, we extend these techniques to support authenticated degree-two correlations in the important two-party case.

The recently introduced Counter Galois Onion (CGO) is a new symmetric onion encryption scheme designed to replace the current one used by Tor, with integration in Tor’s Rust implementation Arti ongoing. Intuitively, CGO uses an updatable tweakable split-domain cipher as its building block, which provides it with the necessary non-malleability properties while attaining better performance than the alternative approach of realising it from a wide blockcipher (with full SPRP security). However, onion encryption as used in Tor with various functionality features and security trade-offs, is not that well-studied by the cryptographic community. As a result, the requirements of this important primitive which protects the privacy of millions of users on a daily basis, is not well understood and whether CGO fulfills all its security goals unclear. In this work, we initiate the study of real-world symmetric onion encryption by presenting a new security model capturing Tor’s leaky pipes functionality, associated data, and partial forward security, neither of which were covered previously. We then use this new security model to solidify the security claims of CGO in the forward direction by proving that if the underlying primitive is a suitably secure tweakable split-domain cipher, then CGO is a secure onion encryption scheme.

In this paper, we present formally verified proofs of the popular KZG Polynomial Commitment Schemes (PCSs), including the security proofs for the properties of correctness, polynomial binding, evaluation binding and hiding. Polynomial commitment schemes have various applications in cryptography and computer science, including verifiable computation, blockchain and cryptocurrencies, secure multi-party computation as well as in the construction of ZK-SNARKs. To validate security, we utilise EasyCrypt, an interactive theorem prover that allows for formal verification of cryptographic primitives and protocols. This approach enforces correct proofs which cover all required cases and formalising assumptions reducing the risk of overlooked vulnerabilities. This formalisation validates the current understanding of KZG's PCSs as secure while clarifying various issues in the original claims.

We study the problem of minimizing the total weight of (potentially many) participants of a distributed protocol, a necessary step when the original values are large but the scheme to be deployed scales poorly with the weights. We assume that $\alpha$ fraction of the original weights can be corrupted and we must output new weights with at most $\beta$ adversarial fraction, for $\alpha < \beta$. This problem can be viewed from the prism of electing a small committee that does the heavy work, a powerful tool for making distributed protocols scalable. We solve the variant that requires giving parties potentially multiple seats in the committee and counting each seat towards the cost of the solution. Moreover, we focus on the "deterministic" version of the problem where the computed committee must be secure for any subset of parties that can be corrupted by the adversary; such a committee can be smaller than a randomly sampled one in some cases and is useful when security against adaptive corruptions is desired but parties in the sub-protocol speak multiple times. Presented are new algorithms for the problem as well as analysis of prior work. We give two variants of the algorithm Swiper (PODC 2024) that significantly improve the running time without sacrificing the quality of the output, with the second one, in fact, improving the output. We prove, however, that all known algorithms, including our two variants of Swiper, have worst case approximation ratio $\Omega(n)$. To counter that, we give the first polynomial time algorithm with approximation factor $n / \log^2 n$ and also the first sub-exponential time exact algorithm, practical for some real-world inputs. Of theoretical interest is another polytime algorithm that we present, based on linear programming, whose output is no worse than an optimal solution to the problem with slightly different parameters. We implemented and tested previous and new algorithms, comparing them on the stake distributions of popular proof-of-stake blockchains, and found that our second variant of Swiper computes solutions extremely close to the optimal, confirmed by our exact algorithm.

This work describes vulnerabilities in the specification of AEAD modes and Key Wrap in two cryptographic message formats. Firstly, this applies to AEAD packets as introduced in the novel LibrePGP specification that is implemented by the widely used GnuPG application. Secondly, we describe vulnerabilities in the AES-based AEAD schemes as well as the Key Wrap Algorithm specified in the Cryptographic Message Syntax (CMS). These new attacks exploit the possibility to downgrade AEAD or AES Key Wrap ciphertexts to valid legacy CFB- or CBC-encrypted related ciphertexts and require that the attacker learns the content of the legacy decryption result. This can happen in two principal ways: either due to the human recipient returning the decryption output to the attacker as a quote or due to a programmatic decryption oracle in the receiving system that reveals information about the plaintext. The attacks effect the decryption of low-entropy plaintext blocks in AEAD ciphertexts and, in the case of LibrePGP, also the manipulation of existing AEAD ciphertexts. For AES Key Wrap in CMS, full key decryption is possible. Some of the attacks require multiple successful oracle queries. The attacks thus demonstrate that CCA2 security is not achieved by the LibrePGP and CMS AEAD or Key Wrap encryption in the presence of a legacy cipher mode decryption oracle.

CROSS is a post-quantum secure digital signature scheme submitted to NIST’s Call for Additional Signatures which was recently selected for round 2. It features signature and key sizes in the range of SLH-DSA while providing a substantially faster signing operation. Within this work, we provide the first passive side-channel attack on the scheme. The attack recovers the secret key from all except one parameter sets from a single power trace while requiring at maximum two power traces for the R-SDP(G) 1 Fast instance. To successfully mount the attack, we show how to recover the secret key from side-channel information gained from the syndrome computation in CROSS’ identification protocol. We furthermore show how the hypothesis space for the attack can be restricted using information from the published signature.

This paper proposes modular security proofs for some identification scheme (IDS)-based signature schemes in the multivariate quadratic (MQ) setting. More precisely, our contributions include concrete security reduction for both 3-pass and 5-pass MQDSS signature schemes in the random oracle model. Although no formal security argument for the former was available in the literature, the one for the latter provides only a qualitative treatment. Our concrete analysis shows that the 3-pass scheme enjoys a comparatively tighter reduction. This result, considered in conjunction with a reported attack on the 5-pass MQDSS from the NIST PQC competition, thus indicates that contrary to the initial suggestion, the 3-pass MQDSS could be a better choice at a concrete security level. Our next focus is on the only blind signature scheme available in the MQ-setting, proposed by Petzoldt et al. While the security of the original scheme was discussed in a non-standard and significantly weak model; we propose a concrete security reduction for a slightly modified scheme in the standard one-more unforgeability (OMF) model. Central to all our modular proofs are new forking algorithms. The forking algorithm/lemma has been widely used in the formal security reduction of numerous cryptographic schemes, mainly in the discrete logarithm and RSA setting. The abstractions proposed here allow multiple forkings at the same index while satisfying certain additional conditions for the underlying IDS in the MQ-setting. Thus, the forking algorithms capture the nuances of the MQ-setting while being agnostic of the underlying structure.

Efficient implementation of pairing-based cryptosystems relies on high-performance arithmetic in finite fields $\mathbb{F}_{p}$ and their extensions $\mathbb{F}_{p^k}$, where $k$ denotes the embedding degree. A small embedding degree is crucial since a part of the arithmetic for pairing computation occurs in $\mathbb{F}_{{p}^k}$, including squaring, multiplication, and Frobenius operations. In this paper, we present a fast and efficient method for computing the Frobenius endomorphism in the finite field $\mathbb{F}_{p^k}$, along with an analysis of its computational complexity. Furthermore, we introduce an optimization for cyclotomic cubing operations tailored to several pairing-friendly elliptic curves, which are essential for the calculation of Tate pairing and its derivatives.

Traceable ring signatures enhance ring signatures by adding an accountability layer. Specifically, if a party signs two different messages within the protocol, their identity is revealed. Another desirable feature is $\textit{extendability}$. In particular, $\textit{extendable threshold}$ ring signatures (ETRS) allow to $\textit{non-interactively}$ update already finalized signatures by enlarging the ring or the set of signers. Combining traceability and extendability in a single scheme is unexplored and would offer a new tool for privacy-preserving voting schemes in scenarios where the voters are not known in advance. In this paper, we show how to reconcile both properties by introducing and constructing a new cryptographic primitive called Tetris. Notably, our Tetris construction simultaneously achieves strong anonymity and linear-size signatures, which is the main technical challenge in existing techniques. To solve this challenge, we develop a new approach to traceability that leads to several conceptual and technical contributions. Among those, we introduce and construct, based on Groth-Sahai proofs, $\textit{extendable}$ shuffle arguments that can be $\textit{non-interactively}$ updated by several provers.

Homomorphic encryption schemes based on the Ring-Learning-with-Errors problem require accurate ciphertext noise analysis to ensure correctness and security. However, ring multiplications during homomorphic computations make the noise in the result ciphertexts difficult to characterize. Existing average-case noise analyses derive a bound on the noise by either assuming it follows a Gaussian distribution, or giving empirical formulae, with strong independence assumption and the Central Limit Theorem extensively applied. In this work, we question the validity of these methods, by showing that the noise exhibits a heavy-tailed distribution via exact calculation of its variance and kurtosis, for both independent and dependent noises. The heavy-tailedness suggests the failing probability of bounds derived from these methods may not be negligible, and we experimentally demonstrate several cases where the noise growth is underestimated.

In this note we identify major issues with “Exact Coset Sampling for Quantum Lattice Algorithms” by Zhang. The issues include: • in the first version, the proposed algorithm requires foreknowledge of the answer to compute the answer; • in the latest version, the proposed algorithm displays basic misunderstandings of quantum mechanics. We believe the existence of these issues refute the author’s claims.

In searchable encryption, a data owner outsources data to a server while allowing efficient search by clients. A multimap associates keywords with a variable number of documents. We consider the setting with multiple owners and multiple clients (Wang and Papadopolous, Cloud Computing 2023). The goal is for each owner to store a multimap and grant access to clients. Prior work shares three weaknesses: * Restricting patterns of adversarial behavior, * Duplicating any data shared with a new client, and * Leaking each client's access pattern and share pattern. We present MARS, the first SSE for multiple owners and clients that considers security for an arbitrary collection of adversarial parties. Our scheme only leaks the volume of the result size and the number of requested keywords, both of which can be padded. No data is replicated. Our scheme combines 1) private information retrieval (PIR) to protect search patterns, 2) efficient delegation of the ability to index keywords and decrypt records, and 3) tabulation hashing to allow a single query for locations associated with a keyword. The first two items can be thought of as a keyword unkeyed PIR where the data owner gives the client the identifiers for individual keywords and keys to decrypt records. Our system is implemented on multimaps up to size $24$ million (the Enron dataset) with total time of $1.2$s for keywords that match $100$ documents. This is in comparison to a time $.500$s for Wang and Papadapolous, which replicates data and has access, sharing, and query equality leakage. Storage overhead is a factor of $6.6$. Our implementation uses FrodoPIR as the underlying PIR. Our system can incorporate batch or doubly-efficient unkeyed PIR as their performance improves.

TFHE bootstrapping is typically limited to a small plaintext space, with an exponential increase in cost for larger plaintext spaces. To bootstrap larger integers, one can use digit decomposition, a procedure that iteratively extracts and bootstraps a part of the larger plaintext space. Conventional state-of-the-art methods typically extract bits starting from the least significant bits (LSBs) and progress to the most significant bits (MSBs). However, we introduce a DirtyMSB extraction procedure that enables the digit decomposition from MSBs to LSB for the first time. However, this procedure introduces a small error during the extraction procedure. We demonstrate how to compensate this error in subsequent iterations. Compared to traditional LSB-to-MSB digit decomposition, our method improves the throughput, with for example an increase of 20% for a 5-bit plaintext and 50% increase for an 8-bit plaintext. In contrast to LSB-to-MSB methods, our extracted output ciphertexts have fresh noise, allowing us to directly use the extracted outputs for further computation without the need for an additional bootstrap or less efficient parameters. We demonstrate the applicability of our method by improving large-scale addition and scalar multiplication. Our method is particularly effective for vector addition operations, accelerating the addition of 1000 16-bit numbers by a factor of $\times2.75$. Furthermore, we demonstrate a $\times2.27$ speedup over the state-of-the-art implementation of scalar multiplication.

In this paper, we present a new type of algebraic attack that applies to many recent arithmetization-oriented families of permutations, such as those used in Griffin, Anemoi, ArionHash, and XHash8, whose security relies on the hardness of the constrained-input constrained-output (CICO) problem. We introduce the FreeLunch approach: the monomial ordering is chosen so that the natural polynomial system encoding the CICO problem already is a Gröbner basis. In addition, we present a new dedicated resolution algorithm for FreeLunch systems of complexity lower than applicable state-of-the-art FGLM algorithms. We show that the FreeLunch approach challenges the security of fullround instances of Anemoi, Arion and Griffin. We confirm these theoretical results with experimental results on those three permutations. In particular, using the FreeLunch attack combined with a new technique to bypass 3 rounds of Griffin, we recover a CICO solution for 7 out of 10 rounds of Griffin in less than four hours on one core of AMD EPYC 7352 (2.3GHz).

The pseudorandom-function oracle-Diffie–Hellman (PRF-ODH) assumption has been introduced recently to analyze a variety of DH-based key exchange protocols, including TLS 1.2 and the TLS 1.3 candidates, as well as the extended access control (EAC) protocol. Remarkably, the assumption comes in different flavors in these settings and none of them has been scrutinized comprehensively yet. In this paper here we therefore present a systematic study of the different PRF-ODH variants in the literature. In particular, we analyze their strengths relative to each other, carving out that the variants form a hierarchy. We further investigate the boundaries between instantiating the assumptions in the standard model and the random oracle model. While we show that even the strongest variant is achievable in the random oracle model under the strong Diffie–Hellman assumption, we provide a negative result showing that it is implausible to instantiate even the weaker variants in the standard model via algebraic black-box reductions to common cryptographic problems.

Our work aims to minimize interaction in secure computation due to the high cost and challenges associated with communication rounds, particularly in scenarios with many clients. In this work, we revisit the problem of secure aggregation in the single-server setting where a single evaluation server can securely aggregate client-held individual inputs. Our key contribution is the introduction of One-shot Private Aggregation ($\mathsf{OPA}$) where clients speak only once (or even choose not to speak) per aggregation evaluation. Since each client communicates only once per aggregation, this simplifies managing dropouts and dynamic participation, contrasting with multi-round protocols and aligning with plaintext secure aggregation, where clients interact only once. We construct $\mathsf{OPA}$ based on LWR, LWE, class groups, DCR and demonstrate applications to privacy-preserving Federated Learning (FL) where clients {speak once}. This is a sharp departure from prior multi-round FL protocols whose study was initiated by Bonawitz et al. (CCS, 2017). Moreover, unlike the YOSO (You Only Speak Once) model for general secure computation, $\mathsf{OPA}$ eliminates complex committee selection protocols to achieve adaptive security. Beyond asymptotic improvements, $\mathsf{OPA}$ is practical, outperforming state-of-the-art solutions. We benchmark logistic regression classifiers for two datasets, while also building an MLP classifier to train on MNIST, CIFAR-10, and CIFAR-100 datasets. We build two flavors of $\mathsf{OPA}$ (1) from (threshold) key homomorphic PRF and (2) from seed homomorphic PRG and secret sharing. The threshold Key homomorphic PRF addresses shortcomings observed in previous works that relied on DDH and LWR in the work of Boneh et al. (CRYPTO, 2013), marking it as an independent contribution to our work. Moreover, we also present new threshold key homomorphic PRFs based on class groups or DCR or the LWR assumption.

In SAC'14, Biham and Carmeli presented a novel attack on DES, involving a variation of Partitioning Cryptanalysis. This was further extended in ToSC'18 by Biham and Perle into the Conditional Linear Cryptanalysis in the context of Feistel ciphers. In this work, we formalize this cryptanalytic technique for Substitution-Permutation Networks and derive several properties. A conditional approximation is then used to approximate the $inv: GF(2^8) \to GF(2^8) : x \to x^{254}$ function, which forms the only source of non-linearity in the AES. By extending the approximation to encompass the full AES round function, a linear distinguisher for 4-round AES using $2^{125.72}$ known-plaintexts is constructed; the existence of which is often understood to be impossible. We furthermore demonstrate how to recover 32 key bits directly from this distinguisher with no data or time overhead. In addition to suggesting a new approach to advancing the cryptanalysis of the AES, this result moreover demonstrates a caveat in the standard interpretation of the Wide Trail Strategy — the design framework underlying many SPN-based ciphers published in recent years.

We present a simple and efficient Byzantine Agreement protocol in the mixed fault model where up to $t$ parties can be Byzantine, up to $s$ parties can be send-omission, and up to $r$ parties can be receive-omission such that $2t+s+r<n$. Our synchronous protocol greatly improves over the efficiency of the state-of-the-art solution due to Loss and Stern [TCC '23]. Specifically, our protocol incurs an expected communication complexity of $O(n^2)$ instead of $O(n^5)$ in their construction, while maintaining the same resilience. Our protocol terminates in an expected constant number of rounds, provided that a constant fraction of parties are non-faulty.

We study the practicality of a primal hybrid lattice attack on LWE. Despite significant research efforts, the state-of-the-art in practical LWE record computations so far is the plain primal attack with Kannan's embedding. Building on an idea by Espitau and Kirchner, Bernstein proposed in 2023 an LWE hybrid attack that asymptotically outperforms the primal attack. In a nutshell, Bernstein's attack enumerates some coordinates of an LWE key and uses the sophisticated Batch-CVP {\em (Randomized) Slicer} algorithm to solve LWE in a dimension-reduced lattice. The practical implications of this attack however remain widely unclear. One of the major obstacles for judging practicality is the lack of a fast, fully functional Slicer implementation. For the first time, we provide an efficient Slicer implementation that includes all required algorithmic ingredients like locality sensitive hashing. Building on our Slicer implementation, we implement a generalization of Bernstein's algorithm. While Bernstein's attack works only for LWE, ours also applies to a more general BDD setting. Let $(\mathbf{B}, \mathbf{t})$ be a BDD instance, where the target $\mathbf{t}$ is off from the $d$-dimensional lattice $\mathcal{L}(\mathbf{B})$ by some error~$\mathbf{e}$, sampled coordinate-wise from a distribution $\mathcal{D}$. We show that for hard BDD instances, our BDD hybrid asymptotically speeds up primal's complexity of $T=2^{0.292d + o(d)}$ down to $T^{1-\mathcal{K}}$, where $\mathcal{K} \approx \big(1+\frac{H(\mathcal{D})}{0.058}\big)^{-1}$ with $H(\cdot)$ the Shannon entropy. Depending on $\mathcal{D}$, the constant $\mathcal{K}$ can be small, making practical improvements difficult. We test our Slicer-based implementation inside an implementation of our BDD hybrid lattice attack to tackle LWE instances. We choose two ternary LWE secrets with different entropies $H(\mathcal{D})$ as used in NTRU, and the centered binomial distribution as used in Kyber. For all three distributions in all tested LWE dimensions $n \in [160, 210]$, our Slicer-based implementation practically demonstrates measurable speedups over the primal attack, up to a factor of $5$. We also show that for parameters as originally suggested by Regev, the hybrid attack cannot improve over primal.

This paper introduces DAWN, a compact and efficient NTRU encryption utilizing double encoding, which is provably secure under the NTRU assumption and the Ring-LWE assumption. We propose a technique for NTRU encryption called the zero divisor encoding. Unlike the polynomial encoding technique proposed by Hoffstein and Silverman (2001) and the vector encoding technique proposed by Zhang, Feng, and Yan in NEV (Asiacrypt 2023), our zero divisor encoding technique leverages the algebraic structure of the ring used in NTRU, enabling greater ciphertext compression while maintaining negligible decryption failure. We further develop a paradigm for NTRU encryption called the double encoding paradigm to maximize the potential of the zero divisor encoding. This paradigm transforms optimizing an NTRU-based encryption into constructing a better encoding within the NTRU context, providing more concrete direction for scheme development. Several previous NTRU encryptions can be situated within this paradigm with different parameters, facilitating direct comparison. We instantiate this paradigm based on the provably IND-CPA secure NTRU variant by Stehlé and Steinfeld (Eurocrypt 2011) to achieve an IND-CPA secure PKE, and subsequently employ the Fujisaki-Okamoto transformation to achieve an IND-CCA secure KEM. We present two parameter settings of DAWN: DAWN-$\alpha$ minimizes ciphertext size, achieving lengths of 436 bytes under NIST-I security and 973 bytes under NIST-V security; DAWN-$\beta$ minimizes the combined size of the public key and ciphertext, attaining combined sizes of 964 bytes under NIST-I security and 2054 bytes under NIST-V security. DAWN achieves superior compactness and performance among current lattice-based KEMs without introducing additional security assumptions. Compared to NEV (Asiacrypt 2023), the previously leading NTRU-based KEM in balancing compactness and performance, DAWN demonstrates 20%-29% greater compactness at approximate security levels and decryption failure probabilities, while executing 1.1X-2.0X faster in a complete ephemeral key exchange process.

An RSA generalization using complex integers was introduced by Elkamchouchi, Elshenawy, and Shaban in 2002. This scheme was further extended by Cotan and Teșeleanu to Galois fields of order $n \geq 1$. In this generalized framework, the key equation is $ed - k (p^n-1)(q^n-1) = 1$, where $p$ and $q$ are prime numbers. Note that, the classical RSA, and the Elkamchouchi \emph{et al.} key equations are special cases, namely $n=1$ and $n=2$. In addition to introducing this generic family, Cotan and Teșeleanu describe a continued fractions attack capable of recovering the secret key $d$ if $d < N^{0.25n}$. This bound was later improved by Teșeleanu using a lattice based method. In this paper, we explore other lattice attacks that could lead to factoring the modulus $N = pq$. Namely, we propose a series of partial exposure attacks that can aid an adversary in breaking this family of cryptosystems if certain conditions hold.

Guo, Li, and Qin proposed a lightweight certificateless encryption (CLE) scheme designed for IoT environments (\textit{Discover Computing}, 2025). This paper demonstrates that the proposed scheme does not achieve CCA security, contrary to the authors' claim. Specifically, we identify two critical points. First, since the ciphertext retains a multiplicative ElGamal structure, it can always be re-randomized using arbitrary randomness. Second, based on this property, an adversary can transform a challenge ciphertext into another valid ciphertext of the same plaintext, and then query the decryption oracle with the transformed ciphertext to recover the challenge plaintext. This attack exploits a definitional gap in the CCA game, where only direct decryption queries on the challenge ciphertext are prohibited. In this work, we formalize the attack procedure and verify its validity based on implementation.

The Hamming Quasi-Cyclic (HQC) scheme has recently been standardized as a post-quantum key encapsulation mechanism (KEM), emphasizing the importance of efficient and secure hardware realizations on embedded platforms. However, HQC relies heavily on sparse–dense polynomial multiplications, where conventional shift-and-add architectures remain both performance- and security-critical. In FPGA implementations, these multiplications dominate execution time—occupying 59.5%, 56.1%, and 58.3% of the total latency for KeyGen, Encap, and Decap, respectively—and are further vulnerable to correlation power analysis (CPA) due to deterministic, index-driven memory access patterns. As countermeasures, parallelization improves performance at the cost of additional area. Dummy insertion with random shuffling mitigates leakage but incurs extra cycle overhead. To address this, we propose a co-designed dummy-inserted parallel shift-and-add multiplier for HQC. The design integrates dummy insertion and two-index parallelism in a complementary manner, achieving reduced cycles with area efficiency while providing intrinsic resistance to CPA. Implemented on a Xilinx Artix-7 FPGA, the proposed architecture achieves up to a 1.25× speedup over the baseline sequential multiplier while maintaining near–state-of-the-art area–time efficiency—incurring only a 1.16× AT overhead to simultaneously deliver accelerated performance and CPA resistance. Test Vector Leakage Assessment (TVLA) measurements and theoretical analysis confirm that the parallel architecture effectively suppresses power-based side-channel leakage and provides inherent resistance against CPA—reducing significant leakage points from 4.29% to 0.09%. This work demonstrates that performance and side-channel resistance can be jointly optimized through synergistic hardware–algorithm co-design, offering a practical and scalable HQC accelerator for post-quantum embedded systems.

The KHAPE-HMQV protocol is a state-of-the-art highly efficient asymmetric password-authenticated key exchange protocol that provides several desirable security properties, but has the drawback of being vulnerable to quantum adversaries due to its reliance on discrete logarithm-based building blocks: solving a single discrete logarithm allows the attacker to perform an offline dictionary attack and recover the password. We show how to modify KHAPE-HMQV to make the protocol quantum-annoying: a classical adversary who has the additional ability to solve discrete logarithms can only break the protocol by solving a discrete logarithm for each guess of the password. While not fully resistant to attacks by quantum computers, a quantum-annoying protocol could offer some resistance to quantum adversaries for whom discrete logarithms are relatively expensive. Our modification to the protocol is small: encryption (using an ideal cipher) is added to one message. Our analysis uses the same ideal cipher model assumption as the original analysis of KHAPE, and quantum annoyingness is modelled using an extension of the generic group model which gives a classical adversary a discrete logarithm oracle.

Mersenne number schemes are a new strain of potentially quantum-safe cryptosystems that use sparse integer arithmetic modulo a Mersenne prime to encrypt messages. Two Mersenne number based schemes were submitted to the NIST post-quantum standardization process: Ramstake and Mersenne-756839. Typically, these schemes admit a low but non-zero probability that ciphertexts fail to decrypt correctly. In this work we show that the information leaked from failing ciphertexts can be used to gain information about the secret key. We present an attack exploiting this information to break the IND-CCA security of Ramstake. First, we introduce an estimator for the bits of the secret key using decryption failures. Then, our estimates can be used to apply the Slice-and-Dice attack due to Beunardeau et al. at significantly reduced complexity to recover the full secret. We implemented our attack on a simplified version of the code submitted to the NIST competition. Our attack is able to extract a good estimate of the secrets using $2^{12}$ decryption failures, corresponding to $2^{74}$~failing ciphertexts in the original scheme. Subsequently the exact secrets can be extracted in about $2^{46}$ quantum computational steps.

Verifiable Secret Sharing (VSS) schemes are fundamental building blocks in distributed cryptography. While most existing works focus on threshold structures, many real-world applications require more general access structures, where participants have different levels of power and only certain subsets are authorized to reconstruct the secret. Existing computational VSS schemes for general access structures typically rely on Discrete Logarithm (DL)-based homomorphic commitments, which limits their applicability, particularly in scenarios requiring Post-Quantum (PQ) security. In this work, we present a generalized version of $\mathrm{\Pi}$, a unified framework introduced at PKC 2025 for constructing computational VSS schemes without relying on homomorphic commitments. Our framework supports arbitrary monotone $\mathcal{Q}_2$ access structures, encompassing replicated and threshold secret sharing (e.g., Shamir's scheme), while preserving the efficiency and modularity of $\mathrm{\Pi}$. Notably, it requires only a random oracle and any commitment scheme satisfying hiding and binding, making it compatible with a wide range of instantiations, including PQ-secure commitments. In particular, our hash-based instantiation yields the first symmetric-key-based VSS scheme for general access structures. Compared to prior general-access VSS schemes based on homomorphic commitments (e.g., variants of Pedersen scheme from FC 2003), our DL-based constructions eliminate the need for homomorphic commitments and achieve asymptotic improvements in verification and reconstruction costs. We believe that this extension enhances the versatility of the original $\mathrm{\Pi}$ framework and paves the way for its deployment in a broader range of practical distributed systems.

To mitigate trust concerns in the setup phase of pairing-based zk-SNARKs, the primary solution has been the sampling of the Structured Reference String (SRS) using an MPC protocol. In 2017, Bowe, Gabizon, and Miers introduced the Powers of Tau MPC protocol for sampling a universal SRS, which has since become the main SRS generation protocol for numerous practical projects. The protocol's designers showed that for a circuit with $2^{21}$ multiplication gates, verifying the universal SRS for Groth16 zk-SNARK could take $55$ minutes for a single update. However, they clarified that "the verification is not run by individual users; it is done by the coordinator and anyone who wishes to verify the transcript of the protocol after completion". This note demonstrates the importance of verifying the final SRS by either $\textit{each}$ individual end-user or $\textit{all}$ ceremony participants to mitigate potential attacks. We discuss simple attack scenarios that highlight vulnerabilities if $\textit{each}$ end-user or $\textit{all}$ participants fail to verify the final SRS. Additionally, by leveraging batching and aggregating techniques, we introduce an efficient verification algorithm for the (original) Powers of Tau protocol, substantially reducing SRS verification time and making it practical even for large-scale ceremonies. In the case of rejection, a more efficient recursive verification approach aids in identifying malicious parties more effectively. This note aims to enhance procedural understanding of SRS generation ceremonies through the Powers of Tau protocol and improve the reliability of current ceremonies against potential threats.

The MPC-in-the-Head paradigm is a promising approach for constructing post-quantum signature schemes. Its significance is underscored by NIST's selection of six signatures based on this paradigm and its variants, TC-in-the-Head and VOLE-in-the-Head, among the fourteen round-2 candidates in its additional post-quantum cryptography standardization process. Recent works by Aguilar-Melchor et al. (ASIACRYPT 2023), Hülsing et al. (CRYPTO 2024), and Baum et al. (CRYPTO 2025) have established EUF-CMA security for these signatures in the Quantum Random Oracle Model (QROM). However, their proofs do not account for crucial optimization techniques such as rejection sampling and grinding, rendering them inapplicable to practical schemes like the NIST round-2 candidates Mirath and RYDE. This paper addresses this gap by analyzing the QROM security of MPC-in-the-Head signatures that incorporate these optimizations, with a focus on Mirath and RYDE. We make two main contributions: 1) We provide a new (strong) EUF-CMA security proof that accommodates rejection sampling and grinding. We also present a new EUF-NMA security proof compatible with these optimizations, by extending the techniques of Don et al. (CRYPTO 2022) and Aguilar-Melchor et al. (ASIACRYPT 2023). 2) We also point out a gap in the EUF-CMA security proof of the MPC-in-the-Head signature schemes using correlated-tree techniques, MQOM, SBC (Huth and Joux, CRYPTO 2024), and rBN++ (Kim, Lee, and Son, EUROCRYPT 2025).

During NIST's post-quantum cryptography standardization process, two generic transforms, Fujisaki-Okamoto (FO) and OAEP, are widely used to achieve the IND-CCA security. For instance, the final winner Kyber has utilized FO, and a variant of the 3rd-round finalist NTRU has utilized OAEP. The FO and OAEP are both constructed in the random oracle model (ROM), so to evaluate their post-quantum security, a security proof in the quantum random oracle model (QROM) is required. So far, the QROM security proof of FO has been given and improved by a sequence of works, however, the QROM security proof of OAEP has not been fully explored: current proofs either introduced an extra plaintext-confirming hash to the ciphertext (TCC 2016), or required parameter restrictions and a quantum collision-resistant term (PKC 2022). In this paper, by reorganizing the proof route, we give a new QROM security proof of plain OAEP. The key techniques used in our proof are the compressed oracle technique proposed by Zhandry (CRYPTO 2019) and the Fixed Permutation One-Way to Hiding recently proposed by Jaeger (Eprint 2024/797), and our proof has the following three advantages: \begin{itemize} \item Similar to Ebrahimi’s proof (PKC 2022), our proof also achieves the stronger IND-qCCA security, where the decryption oracle can be accessed in superposition. \item The parameter restrictions "$n+k_1\geq k_0$" and "$k_0-n=\mathcal{O}(n)$" introduced in Ebrahimi’s proof (PKC 2022) are removed. \item The reliance on the collision resistance of quantum random oracles required in Ebrahimi’s proof (PKC 2022) is avoided, and hence our security bound does not introduce the quantum collision-resistant term "$\mathcal{O}(q^3/2^{n+k_1})$". \end{itemize}

Recently, Hövelmanns, Hülsing, and Majenz introduced a security notion called Find Failing Plaintext – Non Generic (FFP-NG), which captures the ability of an adversary to find decryption failures by making non-trivial use of the public key. A first analysis of this property for lattice-based schemes was presented by Majenz and Sisinni, who showed that the Learning With Errors (LWE) problem reduces to breaking the FFP-NG security of the PVW scheme with discrete Gaussian noise. In this work, we generalize their result by analysing the FFP-NG security of widely used schemes based on Ring-LWE and Module-LWE. To keep our analysis as general as possible, we consider a family of subgaussian distributions that includes, among others, discrete Gaussians and centered binomials.

The Cheon-Kim-Kim-Song (CKKS) scheme is a fully homomorphic encryption scheme that traditionally supports only the evaluation of smooth functions. Recent works have enabled the evaluation of arbitrary (discontinuous) integer functions represented as lookup tables (LUT) on small inputs using the method of functional bootstrapping (FBT). Although well-suited for small integers (up to around 10 bits), the efficiency of FBT quickly declines for large LUTs, and a considerable increase in both runtime and memory requirements is observed. Building on CKKS functional bootstrapping, we propose in this paper two functional bootstrapping algorithms, specifically designed to target larger LUTs (up to 20 bits). For a 16-bit LUT, our implementation in OpenFHE achieves a speed-up of 47.5 in amortized time and 95.1 in latency for single-threaded execution, compared to the state-of-the-art CKKS-based functional bootstrapping method of Alexandru et al. (CRYPTO'25).

The Fiat-Shamir transformation is a general principle to turn any public-coin interactive proof into non-interactive one (with security then typically analyzed in the random oracle model). While initially used for 3-round protocols, many recent constructions use it for multi-round protocols. However, in general the soundness error of the Fiat-Shamir transformed protocol degrades exponentially in the number of rounds. On the positive side, it was shown that for the special class of $(k_1,\dots,k_\mu)$-special-sound $\Sigma$-protocols, which is a natural multi-round generalization of the well-known class of special-sound protocols, the loss is actually only linear in the number of random oracle queries, and independent of the number of rounds, which is optimal. A natural next question is whether this positive result extends to the Fiat-Shamir transformation of so-called $(\Gamma_1,\dots,\Gamma_\mu)$-special-sound protocols. This notion was recently defined and analyzed in the interactive case; it captures a larger class of protocols, namely where the special-soundness property is characterized by a general access structure, rather than a threshold. We show in this work that this is indeed the case. Concretely, we show that the Fiat-Shamir transformation of any $(\Gamma_1, \ldots, \Gamma_\mu)$-special-sound interactive proof is knowledge sound under the same condition on $\Gamma_1,\dots,\Gamma_\mu$ for which the original interactive proof is knowledge sound. Furthermore, also here the loss is linear in the number of random oracle queries and independent of the number of rounds. In light of the above, one might suspect that our argument follows as a straightforward combination of the above mentioned prior works. However, this is not the case. The approach used for $(k_1,\dots,k_\mu)$-special-sound protocols, which is based on an extractor that samples without replacement, does not (seem to) generalize; on the other hand, the other approach, which uses an extractor based on sampling with replacement, comes with an additional loss that would blow up in the recursive multi-round analysis. Thus, new techniques are necessary to handle the above complications.

We analyze the post-quantum security of succinct interactive arguments constructed from interactive oracle proofs (IOPs) and vector commitment schemes. Specifically, we prove that an interactive variant of the *BCS transformation* is secure in the standard model against quantum adversaries when the vector commitment scheme is collapse binding. Prior work established the post-quantum security of Kilian's succinct interactive argument, a special case of the BCS transformation for one-message IOPs (i.e., PCPs). That analysis is inherently limited to one message because the reduction, like all prior quantum rewinding reductions, aims to extract classical information (a PCP string) from the quantum argument adversary. Our reduction overcomes this limitation by instead extracting a *quantum algorithm* that implements an IOP adversary; representing such an adversary classically may in general require exponential complexity. Along the way we define *collapse position binding*, which we propose as the ``correct'' definition of collapse binding for vector commitment schemes, eliminating shortcomings of prior definitions. As an application of our results, we obtain post-quantum secure succinct arguments, in the standard model (no oracles), with the *best asymptotic complexity known*.

Indistinguishability Obfuscation (iO) renders indistinguishable any pair of same-sized and functionally identical circuits. Since its introduction by Barak et al. (Crypto ’01), iO has become the holy grail of modern cryptography due to the myriad of applications it enables. Despite several theoretical constructions (including recent breakthrough results from well-studied assumptions), practically efficient frameworks for iO have remained out of reach. In this paper, we formally introduce the notion of Hardware-based indistinguishability obfuscation (HiO) with an aim to make iO practical. Further, we present a novel framework called Hardware-based Circuit Obfuscation from Data Encryption (HardCODE) for realizing highly efficient HiO. Given a simple tamper-proof hardware to store a fixed size secret key, our proposed HardCODE framework yields a provably secure hardware module that achieves iO for all poly-sized circuits, while additionally relying on any one-way function and certain (heuristic but widely studied) assumptions on substitution-permutation networks (used extensively in the design of secure block ciphers). We practically instantiate HardCODE from widely deployed realizations of a simple HSM (Hardware Security Module), and the substitution-permutation network underlying the PRESENT block cipher (an ISO standard for lightweight cryptography). We then use this instance of HardCODE to obfuscate, without loss of generality, the C-17 circuit of the ISCAS-85 benchmark suite, while incurring very small practical overheads. To the best of our knowledge, this constitutes the first practical demonstration of iO.

Oblivious pseudorandom functions (OPRFs) allow the blind evaluation of a pseudorandom function, which makes them a versatile building block that enjoys usage in numerous applications. So far, security of OPRFs is predominantly captured in the Universal Composability (UC) framework, where an ideal functionality covers the expected security and privacy properties. While the OPRF functionality appears intuitive at first, the ideal-world paradigm also comes with a number of challenges: from imposing idealized building blocks when building OPRFs, to the lack of modularity, and requiring intricate UC knowledge to securely maneuver their usage. Game-based definitions are a simpler way to cover security properties. They model each property in a single game, which grants modularity in formalizing, proving, and using OPRFs. Interestingly, the few game-based works on OPRFs each re-invent the security model, with considerable variation. Thus, the advantages of the game-based approach remain out of reach: definitions are not easily accessible and comparability across works is low. In this work, we therefore systematize all existing notions into a clear, hierarchical framework. We unify or separate properties, making hidden relations explicit. This effort reveals the necessity of two novel properties: an intermediate privacy notion and a stronger unpredictability notion. Finally, we analyze the two most prominent constructions in our framework: HashDH and 2HashDH. The former does not achieve UC security, but has advantages in applications that require key rotation or updatability; yet it lacks a security analysis. We show that it achieves most security properties in our framework. We also observe that HashDH and 2HashDH do not satisfy our strongest privacy notion, indicating that the guarantees by the UC functionality are not as well understood as we might expect them to be. Overall, we hope that our framework facilitates the usage and design of OPRFs.

It is a common practice for symmetric-key ciphers is to encode a cryptanalysis problem as an instance of the Mixed Integer Linear Programming (MILP) and then run the instance with an efficient solver. For this purpose, it is essential to model the components in a way that is compatible with the MILP formulation while preserving the characteristics of the cipher. In this work, we look at the problem of efficiently encoding a substitution box (SBox for short). More specifically, we take the evaluation tables, namely, the Difference Distribution Table (DDT), the Linear Approximation Table (LAT), the Division Property Table (DPT) and the Boomerang Connectivity Table (BCT). In the current stage, the only model proposed/used in the literature is to look for the positive samples (i.e., non-zero) entries in the evaluation table and encode for that (this ultimately leads to the minimum number of active SBoxes for the target cipher). In our first contribution, we experiment with the complementary concept of using the negative samples (i.e., treating the zero entries as non-zero entries and vice versa), finally a proper recovery procedure is performed to get back to the original problem. In our second contribution, we observe that the top row and column of each table (which are always taken into consideration by the past researchers) are actually redundant, as those are inherently taken care of through additional constraints at another level. We thus propose a simplified model that removes those row and column. We show the efficacy of our proposals by furnishing results on the evaluation tables on multiple SBoxes. Our proposals often reduce the number of constraints for certain SBox evaluation tables (depending on the properties of the table) from the state-of-the-art results.

Deniable authentication is a very desirable guarantee for secure messaging — and in particular Off-The-Record messaging: it allows a sender Alice to authenticate her messages while retaining plausible deniability on whether she authenticated any of her messages. While deniable authentication is not achievable in standard Public-Key Infrastructures, Dodis et al. (TCC ’09) have shown that it is achievable in so-called Key-Registration with Knowledge setups. These guarantee: 1. dishonest parties’ key-pairs are honestly generated; and 2. dishonest parties have access to their secret keys. However, these are expensive assumptions, and it is unclear how to securely realize them in practice. In this paper we study the weakest setup requirements that are sufficient to enable deniable authentication. One of our main findings is that deniable authentication does require an expensive — but not necessarily impractical — Key-Registration procedure. Roughly, this procedure must guarantee that if a user’s key registration is successful, then the user can extract by themselves valid secret keys from their interaction with the registration authority. We show this setup is sufficient by capturing it via an appropriate security model and then proving the anonymity of a ring signature based on it. On the other hand, we explain why this setup seems inherently necessary by listing a series of attacks that void deniability as soon as a user manages to successfully register a public key for which it can convincingly claim it does not know a valid (corresponding) secret key. The requirements we identify for key-registration protocols are expensive, but not necessarily impractical. Our second main contribution is showing how to amortize the per-user Key-Registration cost, which brings deniable authentication guarantees a step closer to practicality.

The growing need for secure computation has spurred interest in cryptographic techniques that operate on encrypted data without revealing its content. Fully Homomorphic Encryption (FHE), especially LWE-based schemes, enables such processing while preserving confidentiality. Decentralized computing offers scalable resources without requiring in-house servers, but it relies heavily on the confidentiality guarantees of underlying schemes. While many existing protocols successfully protect input privacy, function confidentiality remains a largely overlooked but crucial aspect of secure delegated computation. In this work, we present a novel Oblivious Universal Function (OUF) scheme that enables a client to outsource computation of an arbitrary function to an untrusted server while hiding both the input data and the function being applied. Our construction leverages LWE-based FHE and a virtual-tape evaluation model to support composable, non-interactive, and reusable function execution. Crucially, the server remains oblivious not only to the encrypted inputs but also to the structure, type, and identity of the function it is executing. OUF thus bridges the gap between theoretical privacy guarantees and practical secure computation in decentralized environments.

In a secret sharing scheme for a monotone access structure $\mathcal{A}:\{0,1\}^n\rightarrow \{0,1\}$, a dealer can share a secret $s$ to $n$ parties such that any authorized subset of parties $A\in\mathcal{A}$ can recover $s$ while all other subsets learn nothing about $s$. In this work, we study fully anonymous secret sharing (FASS), which strengthens standard secret sharing by requiring the following properties: - Share Anonymity. The shares belonging to any unauthorized set of parties not only hide the secret, but also all identifiable information such as party identities and whether or not the shares were generated together. In particular, it suffices that such shares be uniform and independent. - Anonymous Reconstruction. The reconstruction algorithm does not need to know the reconstructing set of parties. Efficient FASS exists for threshold access structures. For general access structures, the only known construction relies on a monotone DNF representation of $\mathcal{A}$ and has per-party share size $\Omega(\ell n)$ where $\ell$ is the number of minterms of $\mathcal{A}$. This leaves an exponential gap between standard secret sharing and FASS even for simple access structures. Moreover, even in the threshold case, known schemes could not achieve optimal robust reconstruction when mixing shares of multiple secrets. Motivated by a recent work of Eldridge et al. [USENIX'24], who demonstrated an application of FASS to stalker detection, we initiate a systematic study of FASS, obtaining the following main results. - Near-Optimal Information-Theoretic FASS. We obtain strong lower bounds, showing that the dependence on the DNF size is generally inherent. In particular, the share size can be exponential in the number of parties or even in the minimum CNF size. This stands in sharp contrast to standard secret sharing, where no super-polynomial lower bounds are known, and where the share size is upper bounded by the CNF size. For DNF with $\ell$ small minterms, we improve the previous upper bound to $\tilde O(\ell)$, matching our lower bound up to a polylogarithmic factor. - Computational FASS. We show that the above negative results can be circumvented in the computational setting, obtaining FASS schemes with succinct shares. Under the learning with errors (LWE) assumption, we present a general compiler from standard secret sharing to FASS that preserves the share size of the underlying scheme. For natural graph access structures, we directly construct succinct FASS from either one-way functions or bilinear maps. - Robust FASS. We show that simple modifications of our computational FASS schemes can allow for robust reconstruction of a polynomially unbounded number of secrets from any mixture of their authorized shares.

Anonymous communication networks (ACNs) aim to thwart an adversary, who controls or observes chunks of the communication network, from determining the respective identities of two communicating parties. We focus on low-latency ACNs such as Tor, which target a practical level of anonymity without incurring an unacceptable transmission delay. While several definitions have been proposed to quantify the level of anonymity provided by high-latency, message-centric ACNs (such as mix-nets and DC-nets), this approach is less relevant to Tor, where user–destination pairs communicate over secure overlay circuits. Moreover, existing evaluation methods of traffic analysis attacks on Tor appear somewhat ad hoc and fragmented. We propose a fair evaluation framework for such attacks against onion routing systems by identifying and discussing the crucial components for evaluation, including how to consider various adversarial goals, how to factor in the adversarial ability to collect information relevant to the attack, and how these components combine to suitable metrics to quantify the adversary's success.

Approximate nearest neighbor search (ANNS), also known as vector search, is an important building block for various applications, such as recommendation systems, biometric authentication, and machine learning. In this work, we are interested in the private ANNS problem, where the client wants to learn (and can only learn) the ANNS results without revealing the query to the server. Previous private ANNS works either suffer from high communication cost (Chen et al., USENIX Security 2020) or work under a stronger security assumption of two non-colluding servers (Servan-Schreiber et al., SP 2022). We present Panther, an efficient private ANNS framework under the single server setting. Panther achieves its high performance via several novel co-designs of private information retrieval, secret-sharing, garbled circuits, and homomorphic encryption. We made extensive experiments using Panther on four public datasets, showing that Panther could answer an ANNS query on $10$ million points in $18$ seconds with $284$ MB of communication. This is more than $7.8\times$ faster and $20\times$ more compact than Chen et al..