Stateful signatures like the NIST standardized signature schemes LMS and XMSS provide an efficient and mature realization of post-quantum secure signature schemes. They are recommended for long-term use cases like e.g. firmware signing. However, stateful signature schemes require to properly manage a so-called state. In stateful signature schemes like LMS and XMSS, signing keys consist of a set of keys of a one-time signature scheme and it has to be guaranteed that each one-time key is used only once. This is done by updating a state in each signature computation, basically recording which one-time keys have already been used. While this is straightforward in centralized systems, in distributed systems like secure enclaves consisting of e.g. multiple hardware security modules (HSMs) with limited communication keeping a distributed state that at any point in time is consistent among all parties involved presents a challenge. This challenge is not addressed by the current standardization processes. In this paper we present a security model for the distributed key management of post-quantum secure stateful signatures like XMSS and LMS. We also present a simple, efficient, and easy to implement protocol proven secure in this security model, i.e. the protocol guarantees at any point in time a consistent state among the parties in a distributed system, like a distributed security enclave. The security model is defined in the universal composabilty (UC) framework by Ran Canetti by providing an ideal functionality for the distributed key management for stateful signatures. Hence our protocol remains secure even if arbitrarily composed with other instances of the same or other protocols, a necessity for the security of distributed key management protocols. Our main application are security enclaves consisting of HSMs, but the model and the protocol can easily be adapted to other scenarios of distributed key management of stateful signature schemes.

This paper presents a hardware-conscious analysis of the quantum acceleration of the classical 3-round Keccak-256 preimage attack using Grover’s Algorithm. While the theo- retical quantum speed-up from T cl ≈ 2 ^57.8 (classical) to T qu ≈ 2 ^28.9 (quantum) is mathe- matically sound, the practical implementation overhead is so extreme that attacks remain wholly infeasible in both resource and runtime dimensions. Using Qiskit-based circuit synthesis, we derive that a 3-round Keccak quantum oracle requires: • 9,600 Toffoli gates (with uncomputation for reversibility) • 3,200 logical qubits (1,600 state + 1,600 auxiliary) • 7.47 × 10 13 total 2-qubit gates (full Grover search) • 3.2 million physical qubits (with quantum error correction) — PROHIBITIVE • 0.12 years (43 days) to 2,365+ years execution time, depending on machine assumptions These barriers—particularly the physical qubit requirements, circuit depth, and error accumulation—render the quantum attack infeasible for any foreseeable quantum computer. Consequently, SHA-3 security is not threatened by quantum computers for preimage attacks. We emphasize the critical importance of hardware-aware complexity analysis in quantum cryptanalysis: the elegant asymptotic theory of Grover’s Algorithm hides an engineering overhead so prohibitive that the quantum approach becomes infeasible from both resource and implementation perspectives.

We study the problem of random-access authenticated encryption. In this setting, one wishes to encrypt (resp., decrypt) a large payload in an online matter, i.e., using a limited amount of memory, while allowing for the processing of plaintext (resp., ciphertext) segments to be in a random order. Prior work has studied online AE for in-order (streaming) encryption and decryption, and later work added additional constraints to support random access decryption. The result is complicated notions that are not built from the start to account for random access. We thus provide a new, clean-state treatment to the random-access setting. We introduce random-access authenticated encryption (raAE) schemes, which captures AEAD that provides random-access encryption and decryption. We introduce formal security definitions for raAE schemes that cover confidentiality, integrity, and commitment. We prove relationships with existing notions, showing that our simpler treatment does not sacrifice achievable security. Our implications also result in the first treatment of commitment security for online AEAD as well, an increasingly important security goal for AEAD. We then exercise our formalization with a practice-motivated case study: FIPS-compliant raAE. We introduce an raAE scheme called FLOE (Fast Lightweight Online Encryption) that is FIPS compliant, compatible with existing AES-GCM APIs that mandate random nonces, and yet can provide secure, random-access, committing encryption of orders of magnitude more data than naive approaches that utilize AES-GCM. FLOE was designed in close collaboration with leading cloud data platform Snowflake, where it will soon be used in production to protect sensitive data.

The advent of large-scale quantum computers poses a fundamental threat to widely deployed public-key cryptographic schemes such as RSA and elliptic curve digital signatures. In response, the National Institute of Standards and Technology has standardized several post-quantum cryptographic algorithms, including the Stateless Hash-Based Digital Signature Algorithm (SLH-DSA) specified in FIPS 205. While SLH-DSA offers strong, conservative security guarantees based solely on cryptographic hash functions, its practical adoption depends on a clear understanding of its hardware cost and performance characteristics relative to classical standards. This paper presents a unified hardware benchmarking study of SLH-DSA against RSA, DSA, ECDSA, and EdDSA. All algorithms are implemented at the register-transfer level in Verilog HDL and synthesized on the same Xilinx Artix-7 FPGA platform to ensure a fair comparison. The evaluation focuses on key hardware metrics, including logic utilization, memory usage, DSP consumption, operational latency, maximum clock frequency, and throughput for key generation, signing, and verification. The results demonstrate that SLH-DSA is logic- and memory-intensive, with significantly higher signing latency and larger signature sizes compared to classical schemes. However, its verification performance is highly competitive, and its public key size remains extremely small. In contrast, classical schemes are primarily arithmetic-bound and rely heavily on DSP resources. The findings highlight that SLH-DSA represents a viable post-quantum solution for applications prioritizing long-term security assurance and efficient verification, such as firmware authentication and digital archiving, despite its higher signing cost.

The growth of advanced cryptographic applications has driven the development of arithmetization-oriented (AO) ciphers over large finite fields, which are designed to minimize multiplicative complexity. However, this design advantage of AO ciphers could also serve as an attack vector. For instance, the \textsf{AIM} one-way function in the post-quantum signature \AIMer proposed at CCS 2023 has been broken by several works soon after its publication. The designers then promptly developed secure patches and proposed an enhanced version, \textsf{AIM2}, which was updated to the latest version of \AIMer that has been selected as one of the winners of the Korean PQC Competition in early 2025. In this paper, we focus on the algebraic security of AIM2 over $\mathbb{F}_{2^n}$. First, we introduce a resultant-minimized model that reduces eliminations by using a non-$k$ based substitution strategy and linearized-polynomial decomposition, achieving an attack time complexity of $2^{188.76}$ ($2^{195.05}$) primitive calls of \textsf{AIM2-III} when $\omega=2$ ($\omega=2.373$), indicating that the designers have been over-optimistic in the evaluation of their security margin; Second, we propose a subfield reduction technique for the case that exponents approach subfield extension sizes, equation degrees collapse sharply, \textit{e.g.,} the exponent $e_2=141\mapsto 13$ in \textsf{AIM2-V} when considering the subfield $\mathbb{F}_{2^{128}}$. This can lower the algebraic attack complexity to $2^{295.97}$ primitive calls at $\omega=2$, which improves upon designers' estimated bound of Gr\"{o}bner basis attack by about $2^{100}$. Besides, based on our attack methods, we have identified some weak parameter choices, which could provide concrete design guidance for \textsf{AIM2} construction, especially for the exponent of its Mersenne S-box. Finally, to address the potential vulnerabilities, we further propose \textsf{AIM2-patch} with a simple secure patch on \textsf{AIM2}, which can prevent key elimination, neutralize linearized-polynomial decomposition, and raise algebraic attack complexity, while incurring negligible overheads in \AIMer scheme.

The wide deployment of the generative pre-trained transformer (GPT) has raised privacy concerns for both clients and servers. While cryptographic primitives can be employed for secure GPT inference to protect the privacy of both parties, they introduce considerable performance overhead. To accelerate secure inference, this study proposes a public decoding and secure verification approach that utilizes public GPT models, motivated by the observation that securely decoding one and multiple tokens takes a similar latency. The client uses the public model to generate a set of tokens, which are then securely verified by the private model for acceptance. The efficiency of our approach depends on the acceptance ratio of tokens proposed by the public model, which we improve from two aspects: (1) a private sampling protocol optimized for cryptographic primitives and (2) model alignment using knowledge distillation. Our approach improves the efficiency of secure decoding while maintaining the same level of privacy and generation quality as standard secure decoding. Experiments demonstrate a $2.1\times \sim 6.0\times$ speedup compared to standard decoding across three pairs of public-private models and different network conditions.

Transformer models have gained significant attention due to their power in machine learning tasks. Their extensive deployment has raised concerns about the potential leakage of sensitive information during inference. However, when being applied to Transformers, existing approaches based on secure two-party computation (2PC) bring about efficiency limitations in two folds: (1) resource-intensive matrix multiplications in linear layers, and (2) complex non-linear activation functions like $\mathsf{GELU}$ and $\mathsf{Softmax}$. This work presents a new two-party inference framework $\mathsf{Nimbus}$ for Transformer models. For the linear layer, we propose a new 2PC paradigm along with an encoding approach to securely compute matrix multiplications based on an outer-product insight, which achieves $2.9\times \sim 12.5\times$ performance improvements compared to the state-of-the-art (SOTA) protocol. For the non-linear layer, through a new observation of utilizing the input distribution, we propose an approach of low-degree polynomial approximation for $\mathsf{GELU}$ and $\mathsf{Softmax}$, which improves the performance of the SOTA polynomial approximation by $2.9\times \sim 4.0\times$, where the average accuracy loss of our approach is 0.08\% compared to the non-2PC inference without privacy. Compared with the SOTA two-party inference, $\mathsf{Nimbus}$ improves the end-to-end performance of BERT inference by $2.7\times \sim 4.7\times$ across different network settings.

Group signatures allow a group member to sign messages on behalf of the group while preserving the signer’s anonymity, making them invaluable for privacy-sensitive applications. As quantum computing advances, post-quantum security in group signatures becomes essential. Symmetric primitives (SP) offer a promising pathway due to their simplicity, efficiency, and well-understood security foundations. In this paper, we introduce the first \textit{forward-secure dynamic group signature} (FSDGS) framework relying solely on SP. We begin with \textit{hierarchical hypertree group signatures} (HHGS), a basic scheme that securely organizes keys of one-time signatures (OTS) in a hypertree using puncturable pseudorandom functions to enable on-demand key generation and forward security, dynamic enrollment, and which provides resilience against attacks that exploit registration patterns by obfuscating the assignment and usage of keys. We then extend this foundation to HHGS^+, which orchestrates multiple HHGS instances in a generic way, significantly extending the total signing capacity to $O(2^{60})$, which outperforms HHGS's closest competitors while keeping signatures below 8 kilobytes. We prove the security of both schemes in the standard model. Our results outline a practical SP-driven pathway toward post-quantum-secure group signatures suitable for resource-constrained client devices.

Transitioning existing classical two-party secure messaging protocols to post-quantum protocols has been an active movement in practice in recent years: Apple’s PQ3 protocol and the recent Triple Ratchet protocol being investigated by the Signal team with academics (Dodis et al. Eurocrypt’25). However, due to the large communication overhead of post-quantum primitives, numerous design choices non-existent in the classical setting are being explored, rendering comparison of secure messaging protocols difficult, if not impossible. In this work, we thus propose a new pragmatic metric to measure how secure a messaging protocol is given a particular communication pattern, enabling a concrete methodology to compare secure messaging protocols. We uncover that there can be no “optimal” protocol, as different protocols are often incomparable with the respect to worst-case (adversarial) messaging behaviors, especially when faced with real-world bandwidth constraints. We develop a comprehensive framework to experimentally compare various messaging protocols under given bandwidth limits and messaging behaviors. Finally, we apply our framework to compare several new and old messaging protocols. Independently, we also uncover untapped optimizations which we call opportunistic sending, leading to better post-quantum messaging protocols. To capture these optimizations, we further propose sparse continuous key agreement as a fundamental building block for secure messaging protocols, which could be of independent interest.

The Oil and Vinegar (OV) trapdoor is widely used in signature schemes such as UOV and MAYO. Recently, Esposito et al. proposed OliVier, an encryption scheme based on this trapdoor. However, the OV trapdoor was originally designed for signatures, and adapting it to encryption introduces inherent challenges. We identify two such challenges and analyze how OliVier addresses the first, while showing that the unresolved second challenge enables a practical key-recovery attack. We conclude that any scheme using the OV trapdoor for encryption must also solve this second problem, for which no efficient solution is currently known.

Designing practically secure masked circuits remains a central problem in the field of cryptographic implementation. While most masking schemes have been proven secure in the classical probing model, this model fails to capture more advanced side-channel attacks such as horizontal attacks. In recent years, the community has shifted toward the more realistic random probing model, which offers stronger guarantees. Yet, balancing strong security with practical efficiency continues to be a significant challenge. In this work, we introduce new tools and constructions that significantly improve the design and analysis of random probing secure circuits. First, we formalize new security notions that combine the benefits of cardinal and general Random Probing Composability (RPC), two recently introduced notions enabling more flexible and efficient composition of secure gadgets. We then show how uniformly random permutations can be applied to transform any cardinal or general RPC gadget into a so-called uniformly cardinal RPC gadget, thereby enhancing security at low cost. Using these techniques, we propose the first non-linear multiplication gadget, inspired by the recursive construction from CHES 2016, that achieves concrete cardinal RPC security. We provide a detailed comparison with state-of-the-art multiplication gadgets in terms of both random probing advantage and implementation complexity. Building upon this gadget, we design a tighter random probing compiler that strategically uses permutations to improve security bounds while preserving efficiency. Finally, we apply our compiler to the AES and demonstrate improved performance and security compared to existing methods.

Securing sensitive data for long-term storage in the cloud is a challenging problem. Updatable encryption (UE) enables changing the encryption key of encrypted data in the cloud while the plaintext and all versions of the key remain secret from the cloud storage provider, making it an efficient alternative for companies that seek to outsource their data storage. The most secure UE schemes to date follow robust security models, such as the one by Boyd et al. from CRYPTO 2020, and rely exclusively on asymmetric cryptography, thus incurring a substantial performance cost. In contrast, the Nested UE construction of Boneh et al. from ASIACRYPT 2020 achieves much better efficiency with symmetric cryptography, but it provides weaker security guarantees. Boyd et al. further suggest that attaining robust UE security inherently requires the use of asymmetric cryptography. In this work, we show for the first time that symmetric UE schemes are not inherently limited in their security and can achieve guarantees on par with, and even beyond, Boyd’s UE model. To this end, we extend Boyd’s framework to encompass the class of ciphertext-dependent UE schemes and introduce indistinguishability-from-random (IND\$) as a stronger refinement of indistinguishability. While our IND\$ notion primarily streamlines the proofs of advanced security properties within the model, it yields practical privacy advantages: ciphertexts do not exhibit a recognizable structure that could otherwise distinguish them from arbitrary data. We then introduce two robustly secure symmetric UE constructions, tailored to different target security levels. Our schemes are built on a novel design paradigm that combines symmetric authenticated encryption with ciphertext re-randomization, leveraging for the first time the use of pseudorandom number generators in a one-time-pad style. This approach enables both robust security and high efficiency, including in AES-based implementations. Our first scheme, PUE-List, delivers encryption up to 600× faster than prior asymmetric schemes of similar robustness, while matching Boneh et al.’s efficiency and achieving the stronger security level of Boyd et al. Our second scheme, PUE-One, further boosts performance with constant-time decryption 24× faster than all previously known UE schemes, overcoming the main bottleneck in Boneh’s design, while trading off some security, yet still significantly surpassing the guarantees of Boneh’s Nested scheme.

Garbling schemes allow two parties to compute a joint function on private inputs without revealing them. Yet, a semi-honest garbler might exploit hardware/software sidechannel leakages from the evaluator. An alarming threat with no concrete solution yet. Using the homomorphic properties of ElGamal encryption, we can prevent such leakage-based attacks.

Anonymous tokens are cryptographic protocols for restricting the access to online resources to eligible users. After proving eligibility to the token issuer, the client receives a set of tokens. Later, it can prove eligibility to a resource provider by sending one of the tokens received from the issuer. The anonymous token protocol ensures that the resource provider cannot link received tokens to their issuance, even if it colludes with the token issuer. Recently, Faut et al. (EuroS\&P’25) introduced the concept of policy-based anonymous tokens, in which an issuer provides a single pre-token to a client, who can locally derive multiple tokens according to a publicly announced policy. The major advantage of policy-based tokens is that the communication complexity of the issuance phase is constant. While the work of Faut et al. constitutes a promising step in a new direction, their protocol still lacks several desirable properties known from standard anonymous tokens -- most notably, the ability to bind a pre-token and all tokens derived from it to a private metadata bit or a publicly known metadata string. In this work, we present a new framework for policy-based anonymous token schemes in the random oracle model. Our framework includes two concretely practical constructions -- one based on equivalence class signatures and one on algebraic MACs -- as well as a communication-optimized, though less practical, construction based on zkSNARKs. All three constructions can be configured to support private metadata bits, public metadata, or both. We formalize the notion of policy-based anonymous tokens with a private metadata bit and public metadata, and we prove security of the two primary constructions: the equivalence-class-signature-based scheme and the algebraic-MAC-based scheme. Finally, we provide an experimental evaluation and comparison of all our constructions alongside the most relevant related work. Our results demonstrate that our two primary constructions achieve significant efficiency improvements over the scheme of Faut et al., both in terms of computation communication.

Recently, $\mathsf{NTRU}$+$\mathsf{Sign}$ was proposed as a new compact signature scheme, following `Fiat-Shamir with Aborts' (FSwA) framework. Its compactness is mainly based on their novel NTRU-based key structure that fits well with bimodal distributions in the FSwA framework. However, despite its compactness, $\mathsf{NTRU}$+$\mathsf{Sign}$ fails to provide a diverse set of parameters that can meet some desired security levels. This limitation stems from its reliance on a ring $\mathbb{Z}_q[x]/\langle x^n+1 \rangle$, where $n$ is restricted to powers of two, limiting the flexibility in selecting appropriate security levels. To overcome this limitation, we propose a revised version of $\mathsf{NTRU}$+$\mathsf{Sign}$ by adopting a ring $\mathbb{Z}_q[x]/\langle x^n-x^{n/2}+1\rangle$ from cyclotomic trinomials, where $n=2^{i}3^{j}$ for some positive integers $i$ and $j$. Our parameterization offers three distinct security levels: approximately $120$, $190$, and $260$ bits, while preserving the compactness in $\mathbb{Z}_q[x]/\langle x^n+1 \rangle$. We implement these re-parameterized $\mathsf{NTRU}$+$\mathsf{Sign}$ schemes, showing that the performance of $\mathsf{NTRU}$+$\mathsf{Sign}$ from cyclotomic trinomials is still comparable to previous lattice-based signature schemes such as $\mathsf{Dilithium}$ and $\mathsf{HAETAE}$.

As a theoretical cornerstone of post-quantum cryptography, the Learning With Errors (LWE) problem serves as the security foundation for standardized algorithms such as Kyber and Dilithium. Recently, a framework for provable dual attacks on LWE has been proposed by Pouly et al. in Eurocrypt 2024, addressing the limitations in effectiveness caused by existing methods' reliance on heuristic assumptions in LWE dual attacks. Their paper also poses an open problem on how to formally integrate modulus switching into this framework to reduce attack costs. The main purpose of this paper is to give a solution of this open problem by presenting an improved provable dual attack method that incorporates modulus switching and Chinese Remainder Theorem (CRT) techniques. First, we design a modulus switching mechanism that eliminates practical errors via the Poisson summation formula. By embedding the inherent noise from modulus switching into a rational lattice framework, our approach effectively preventing the risk of attack failure caused by the merging of such errors with LWE noise. Theoretical guarantees (Theorems \ref{main_theorem} and \ref{main_theorem_entire}) rigorously quantify the parameter ranges for successful attacks. Second, we introduce a CRT-based secret recovery method that aggregates partial secrets from independent sub-attacks. By leveraging the Chinese Remainder Theorem to reconstruct full secrets from congruence relations, our method adapts to arbitrary secret distributions. Furthermore, by using a tighter variant of Banaszczyk's measure inequality, we obtain a precise parameter range for the dual attack's efficacy through rigorous mathematical proof, and achieve the same complementary gap with the contradictory regime (proposed by Ducas et al.) as in Pouly et al.'s work. Experiments show $4$-$5$ bits superior performance in attack estimation compared to the original framework.

Fully homomorphic encryption (FHE) enables clients with small devices to securely delegate their computations to powerful servers. However, to delegate these computations, a client should generate and transmit several gigabytes of FHE keys to the server. Reducing the size of FHE keys without compromising efficiency is therefore highly desirable, particularly for applications involving mobile and IoT devices. In this work, we propose two new key management systems, $\textsf{KG}^{+}$ and $\textsf{BTS}^{+}$, which reduce the client-side cost of FHE. The $\textsf{KG}^{+}$ system significantly reduces the key size without any compromise in the efficiency of homomorphic computation compared to the state-of-the-art key management system by Lee-Lee-Kim-No [Asiacrypt 2023]. The $\textsf{BTS}^{+}$ system further reduces the key size at the expense of granularity in homomorphic computation. Our systems rely on a new ring switching technique for keys that bridges FHE keys with different parameters. This technique decouples the rings of FHE keys during transmission and computation. In our approach, the client generates and sends ``transmission keys'' with size-optimal parameters, and the server generates ``evaluation keys'' with computation-optimal parameters. We evaluate the communication costs of $\textsf{KG}^{+}$ and $\textsf{BTS}^{+}$ on the tasks studied in Lee-Lee-Kim-No. The transmission key sizes for CKKS bootstrapping with ring dimension $2^{16}$ are $325$--$609$ MB for $\textsf{KG}^{+}$ and $285$ MB for $\textsf{BTS}^{+}$. These are $3.09$--$4.37\times$ and $3.51$--$9.30\times$ smaller than Lee-Lee-Kim-No, respectively. For the secure ResNet-20 inference, the key sizes for $\textsf{KG}^{+}$ and $\textsf{BTS}^{+}$ are $325$--$609$ MB and $285$ MB, respectively. These are $3.95$--$5.73\times$ and $4.53$--$12.25\times$ smaller than Lee-Lee-Kim-No.

HMAC and its variant NMAC are among the most widely used methods for keying a cryptographic hash function to obtain a PRF or a MAC. Yet, even after nearly three decades of research, their generic PRF security still remains poorly understood, where the compression function of the underlying hash function is treated as a black box and accessible to the adversary. Although a series of works have exploited compression function queries to mount generic attacks, proving tight bounds on the generic PRF security of HMAC and NMAC remains a challenging open question until now. In this paper, we establish tight bounds on the generic PRF security of HMAC and NMAC. Our bounds capture the influence of the number of construction queries, the number of compression function queries, and the maximal block length of a message on their security. The proofs are carried out in the multi-user setting and the bounds hold regardless of the number of users. In addition, we present matching attacks to demonstrate that our bounds are essentially tight. Taken together, our results close a longstanding gap in the generic PRF security analysis of HMAC and NMAC.

Hamming Quasi-Cyclic (HQC), recently selected by NIST for standardization, does not employ ciphertext compression, unlike its lattice-based counterpart Kyber. In lattice-based encryption, ciphertext compression is a standard post-processing step, typically implemented through coefficient-wise rounding. In contrast, analogous methods have not yet been explored in code-based cryptography. We address this gap by developing techniques to reduce ciphertext sizes in schemes defined over the Hamming metric, with a particular focus on HQC. To support this approach, the decryption failure rate (DFR) analysis is generalized. Specifically, we revisit the modeling of the error that must be correctable with probability $2^{-\lambda}$ to achieve $\lambda$ bits of security; previously, only tractable under an independence assumption. We propose a more accurate model of the error distribution, which takes dependencies between the coefficients into account. Confirmed by extensive simulations, the proposed model sharpens the DFR analysis and, hence, our understanding of the security of HQC. Building on this generalized framework, we present a ciphertext compression mechanism that enables a precise DFR analysis and is therefore transparent with respect to security. This is achieved by carefully designing a quantization code with a direct-product structure, aligned with HQC's error-correcting code. For the parameters proposed in the round 4 submission, our techniques reduce HQC ciphertext sizes by up to 4.7%; a proof-of-concept implementation confirms that this improvement comes without noticeable loss in efficiency. Reductions of up to 10% are achievable through a trade-off with public-key size.

We propose a Pairing-based Polynomial Consistency Protocol (PPCP) that verifies the equivalence of polynomial commitments generated under different basis representations, such as the coefficient and Lagrange bases. By leveraging pairing relations, PPCP proves that two commitments correspond to an identical underlying polynomial vector without revealing the polynomial itself. This enables efficient proof aggregation and recursive composition across heterogeneous SNARK systems that adopt distinct polynomial encodings.

The industry is moving away from passwords for authentication and authorization, with hardware devices for storing long-term cryptographic keys emerging as the leading alternative. However, these devices often have limited displays and remain vulnerable to theft, malware, or tricking users into signing malicious payloads. Current systems provide little fallback security in such cases. Any solution must also meet strict requirements: compatibility with industry standards, scalability to handle high request volumes, and high availability. We present a novel design for authentication and authorization that meets these demands. Our approach virtualizes the authenticating/authorizing party via a two-party signing protocol with a helper entity, ensuring that keys remain secure even if a device is compromised and that every signed message conforms to a security policy. We formalize the required properties for such protocols and show how they are met by existing schemes (e.g., FROST for Schnorr, Boneh–Haitner–Lindell-Segev'25 for ECDSA). Motivated by the widespread use of ECDSA (FIDO2/Passkeys, blockchains), we introduce a new, optimized two-party ECDSA protocol that is significantly more efficient than prior work. At its core is a new variant of exponent-VRF, improving on earlier constructions and of independent interest. We validate our design with a proof-of-concept virtual authenticator for the FIDO2 Passkeys framework.

Finding intersections across sensitive data is a core operation in many real-world data-driven applications, such as healthcare, anti-money laundering, financial fraud, or watchlist applications. These applications often require large-scale collaboration across thousands or more independent sources, such as hospitals, financial institutions, or identity bureaus, where all records must remain encrypted during storage and computation, and are typically outsourced to dedicated/cloud servers. Such a highly distributed, large-scale, and encrypted setting makes it very challenging to apply existing solutions, e.g., (multi-party) private set intersection (PSI) or private membership test (PMT). In this paper, we present Distributed and Outsourced PSI (DO-PSI), an efficient and scalable PSI protocol over outsourced, encrypted, and highly distributed datasets. Our key technique lies in a generic threshold fully homomorphic encryption (FHE) based framework that aggregates equality results additively, which ensures high scalability to a large number of data sources. In addition, we propose a novel technique called \textit{nonzero-preserving mapping}, which maps a zero vector to zero and preserves nonzero values. This allows homomorphic equality tests over a smaller base field, substantially reducing computation while enabling higher-precision representations. We implement DO-PSI and conduct extensive experiments, showing that ours substantially outperforms existing methods in both computation and communication overheads. Our protocol handles a billion-scale set distributed and outsourced to a thousand data owners within one minute, directly reflecting large-scale deployment scenarios, and achieves up to an 11.16$\times$ improvement in end-to-end latency over prior state-of-the-art methods.

Multi-tenant direct-to-cell (D2C) Low Earth Orbit (LEO) satellite networks pose significant risks to users’ location privacy by linking Mobile Network Operator (MNO)- managed identities with Satellite Network Operator (SNO)- visible locations. Existing privacy solutions are ill-suited to the resource-constrained hardware and orbital dynamics of these satellite environments. We present LPG (Location Privacy Game), the first protocol-layer solution offering user-configurable location privacy for D2C LEO. LPG achieves this via identity-location decoupling: SNOs provide connectivity without visibility of user identity, while MNOs manage service and billing without access to precise location information. LPG enables offline secure authentication and key agreement without revealing user identity to satellites, supports user-configurable location disclosure at chosen geographic granularity for essential service needs, and ensures fair billing between MNOs and SNOs through privacy-preserving settlement. Our implementation on a real-world in-orbit LEO satellite and commercial mobile phones demonstrates that LPG is practical and viable in resource-constrained, highly-dynamic LEO environments.

A multi-party private join (MPPJ) protocol enables multiple source parties to provide a receiver party with the inner joins over their respective datasets, while revealing as little information as possible. There is currently no protocol that directly and efficiently enables such a MPPJ beyond the two- or three-party setting. The presently known protocols either achieve weaker functionality (e.g., multi- party private set intersection protocols) or more general ones (e.g., private-join-compute and generic secure multi-party computation protocols) and are therefore more costly to run for the sources. This work formally introduces MPPJ as an explicit goal, and proposes an efficient, helper-assisted protocol that achieves 𝑛-party inner joins with small leakage and close-to-optimal overhead for the sources. Specifically, for 𝑛 databases with 𝑚 rows, it requires only a single 𝑂 (𝑚) upload from the sources to the helper, and a single 𝑂 (𝑛 · 𝑚) download from the helper to the receiver. Moreover, the helper is entirely oblivious: it enables the efficiency and simplicity goals we are striving for, but it does not learn anything about the computation it facilitates. We formally model and prove the security of our protocol from standard assumptions, in the passive-adversary model. Then, we provide an open-source implementation and an extensive performance evaluation. According to our experiments, our protocol requires 1.02 to 20 times less communication than a current private-join-compute protocol (with no computation over the join) for 2 to 6 parties and input database sizes from 1.5K to 250K records. Finally, we demonstrate the versatility of our approach by extending our protocol to threshold-joins.

The GINX method in TFHE enables low-latency ciphertext bootstrapping with relatively small bootstrapping keys but is limited to binary or ternary key distributions. In contrast, the AP method supports arbitrary key distributions, albeit at the cost of significantly large bootstrapping keys. Building on AP, automorphism-based methods, introduced in LMK⁺ (EUROCRYPT 2023), achieve smaller key sizes. However, each automorphism application necessitates a key switch, introducing additional computational overhead and noise accumulation. This paper advances automorphism-based methods in two important ways. First, it proposes a novel traversal blind rotation algorithm that optimizes the number of key switches for a given key material. Second, it introduces a new external product that is automorphism-parametrized and seamlessly applies an automorphism to one of the input ciphertexts. Together, these techniques substantially reduce the number of key switches, resulting in faster bootstrapping and improved noise control. As an independent contribution, we introduce a comprehensive theoretical framework for analyzing the expected number of automorphism key switches. The predictions of this framework perfectly align with the results of extensive numerical experiments, demonstrating its practical relevance. In typical settings, by leveraging additional key material, the LLW⁺ approach (TCHES 2024) reduces the number of key switches by 17% compared to LMK⁺. Our combined techniques achieve a 46% reduction using similar key material and can eliminate an arbitrary large number (e.g., more than 99%) of key switches with only a moderate (9x) increase in key material size. As a result, the total bootstrapping runtime decreases by more than 34%.

Abstract. Designated verifier signature allows a signer to designate a verifier who can verify the signature. A strong designated verifier signature (SDVS) enhances privacy by ensuring that the signature itself does not leak information about the signer’s identity to anyone other than the designated verifier. Non-delegatability is a property, as it prevents the signer’s ability to generate valid signatures from being delegated to others. This property is important for SDVS applications such as e-voting. To date, post-quantum SDVS schemes with non-delegatability have been proposed. These schemes are lattice-based or hash-based schemes. While isogeny-based SDVS schemes have been proposed, none of the existing works provide a proof of non-delegatability. In this paper, we present the first isogeny-based SDVS scheme with a formal proof of non-delegatability. Our construction uses the quadratic twists of elliptic curves. The security of our scheme is proven under the commutative supersingular isogeny gap Diffie–Hellman assumption and the group action inversion problem assumption in the random oracle model.

Folding is a recent technique for building efficient recursive SNARKs. Several elegant folding protocols have been proposed, such as Nova, Supernova, Hypernova, Protostar, and others. However, all of them rely on an additively homomorphic commitment scheme based on discrete log, and are therefore not post-quantum secure and require a large (256-bit) field. In this work we present LatticeFold, the first lattice-based folding protocol based on the Module SIS problem. This folding protocol naturally leads to an efficient recursive lattice-based SNARK and an efficient PCD scheme. LatticeFold supports folding low-degree relations, such as R1CS, as well as high-degree relations, such as CCS. The key challenge is to construct a secure folding protocol that works with the Ajtai commitment scheme. The difficulty is ensuring that extracted witnesses are low norm through many rounds of folding. We present a novel technique using the sumcheck protocol to ensure that extracted witnesses are always low norm no matter how many rounds of folding are used. Since LatticeFold can operate over a small (64-bit) field, our evaluation of the final proof system suggests that it is as performant as Hypernova, while providing plausible post-quantum security. Moreover, LatticeFold operates over the same module structure used by fully homomorphic encryption (FHE) and lattice signatures schemes, and can therefore benefit from software optimizations and custom hardware designed to accelerate these lattice schemes.

The module-lattice-based digital signature standard, formerly known as CRYSTALS-DILITHIUM, is a lattice-based post-quantum cryptographic scheme. In August 2024, the National Institute of Standards and Technology officially standardized ML-DSA under FIPS 204. ML-DSA generates one valid signature and multiple rejected signatures during a single signing process. Most side-channel attacks targeting ML-DSA have focused solely on the valid signature, while largely neglecting the hints contained in rejected signatures. Building on prior SASCA frameworks originally proposed for ML-DSA, in this paper we present an efficient and fully practical instantiation of a private-key recovery attack on ML-DSA that jointly exploits side-channel leakages from both valid and rejected signatures within a unified factor graph. This concrete instantiation maximizes the information extracted from a single signing attempt and minimizes the number of required traces for full key recovery. We conducted a proof-of-concept experiment with both reference and ASM-optimized implementations on a Cortex-M4 core chip, where the results demonstrate that incorporating rejected signatures reduces the required number of traces by at least $50.0\%$ for full key recovery. Moreover, we show that using only rejected signatures suffices to recover the key with fewer than $30$ traces under our setup. Our findings highlight that protecting rejected signatures is crucial, as their leakage provides valuable side-channel information. We strongly recommend implementing countermeasures for rejected signatures during the signing process to mitigate potential threats.

Secure two-party machine learning has made substantial progress through the use of mixed-mode protocols. Despite these advancements, existing approaches often suffer from efficiency bottlenecks due to the inherent mismatch between the optimal domains of various cryptographic primitives, such as Homomorphic Encryption and Oblivious Transfer. In response to these challenges, we introduce the \tNAME{} framework, which features an efficient modulus conversion protocol. This breakthrough enables seamless integration of the most suitable cryptographic subprotocols within their optimal modulus domains, allowing linear computations to be executed over a prime modulus and nonlinear computations over a two-power modulus, with a minimal modulus conversion overhead. We further establish new benchmarks for the performance of fundamental primitives, namely comparison and multiplication, across various two-party techniques, together with our practical optimizations to improve efficiency. By incorporating these techniques, \tNAME{} demonstrates significant performance enhancements over state-of-the-art solutions: \romannumeral1) we report a $6\times$-$100\times$ improvement for approximated truncations with 1-bit error tolerance; \romannumeral2) an average of $5\times$ (resp. $4\times$) reduction in communication (resp. runtime) for machine learning functions; \romannumeral3) and a 25\%-99\% improvement in cost-efficiency for private inference of deep neural networks and 50\% improvement in private training of gradient boosting decision trees.

We present an extend-and-prune fault Injection attack on serial implementations of Learning With Rounding that drop the least-significant bits. By iteratively isolating and recovering progressively larger key portions via faults, the attack recovers the secret key.

We extend a PUF-based authentication protocol with key refresh, hierarchical groups, and revocation. Our framework enables secure communication among enrolled devices without server interaction, allowing group leaders to derive subordinate keys and the server to exclude compromised parties through controlled key updates.

We incorporate a meet-in-the-middle strategy into the enumeration algorithm, enabling a tunable time-memory trade-off. The algorithm can achieve a minimum asymptotic time complexity of \(n^{n/(4e) + o(n)}\), which, in return, demands memory of the same order. This represents a square-root improvement over the state-of-the-art enumeration algorithms. More generally, our approach attains a time complexity of~$n^{cn/(2e) + o(n)}$ with memory usage \(n^{(1-c)n/(2e) + o(n)}\), where $c$ is any constant satisfying \(\frac{1}{2} \leq c < 1\). Our approach decouples the head and tail blocks of the lattice basis. For a properly selected parameter, each enumeration space becomes asymptotically the square root of the original search space. Each tail vector is then extended to the head block space to find its closest vectors using an efficient neighboring search algorithm. Among all pairs of neighboring vectors that we iterate through, the shortest difference vector is then the solution to the Shortest Vector Problem (SVP). Apart from the exact version of the algorithm which is of theoretical interest, we also propose heuristic strategies to improve the practical efficiency. First, we show the adaptation of our algorithm to pruned enumeration. Then we show that with a particularly chosen backbone lattice (rescaled~\(\mathbb{Z}^n\)), we are able to accelerate the neighboring search process to an extremely efficient degree. Finally, we optimize parameters and give a practical cost estimation to show how much acceleration we could bring using this new algorithm.

Security protocols enable authentication, key distribution, and secure information exchange, making them essential for network security, yet flaws in their design can lead to attacks. To prevent this, formal verification methods are vital for analyzing protocol correctness. The Dolev–Yao (DY) \cite{Dy} model introduced formalization for name-stamp and cascade protocols, where users apply public-key operations on messages. Brook and Otto \cite{DY-extension} later distinguished between symmetric and non-symmetric cascade protocols, noting that all DY cases were symmetric and that attacker choices were not fully addressed. They highlighted the incomplete characterization of an attacker’s power as an open problem. In this work, we extend the DY model by systematically analyzing all remaining symmetric two-party cascade protocol cases, aiming to provide a more complete foundation for building formal verification tools.

Verifiable Secret Sharing (VSS) is a fundamental primitive in threshold cryptography and multi-party computation. It preserves secrecy, integrity, and availability of a shared secret for a fixed set of parties, with a subset of them being malicious. In practical applications, especially when the secret sharing is expected to be maintained over long durations, the VSS scheme should be able to cater to a dynamic setting where involved parties may change. The primitive known as Dynamic Proactive Secret Sharing (DPSS) is beneficial here, as it facilitates the secure transfer of secrets from the original committee to a new committee. Nevertheless, prior works on DPSS protocols either rely on unrealistic time bounds on message delivery or have a high computational cost, which limits their scalability beyond tens of parties. In this work, we present a scalable asynchronous DPSS protocol that utilizes lightweight cryptographic tools, such as hash functions and symmetric-key encryption. Our protocol achieves full security and optimal fault tolerance with amortized linear communication costs. Unlike existing solutions, our proposed protocol is also post-quantum secure. By balancing computation and communication, our approach offers practical performance at scale. Our implementation results demonstrate improved scalability and efficiency, surpassing the current state-of-the-art achieving a $22.1\times$ lower latency than the prior best work. Furthermore, our solution also scales gracefully with increasing $n$ and reshares a batch of $100,000$ secrets between committees of sizes $n=112$ parties in under a minute.

We report on our experiences with the ongoing European standardisation efforts related to the EU Cyber Resilience Act (CRA) and provide interim (November 2025) estimates on the direction that European cryptography regulation may take, particularly concerning the algorithm ``allow list'' and PQC transition requirements in products. The CRA has a wide-ranging set of security requirements, including security patching and the use of cryptography (data integrity, confidentiality for data at rest and data in transit). However, the Cyber Resilience Act itself is a legal text devoid of technical detail -- it does not specify the type of cryptography deemed appropriate to satisfy its requirements. The technical implications of CRA are being detailed in approximately 40 new standards from the three European standardisation organisations, CEN, CENELEC, and ETSI. While the resulting ETSI standards can be expected to be available for free even in the drafting stage, the CEN and CENELEC standards will probably require a per-reader license fee. This, despite recent legal rulings asserting that product security and safety standards are part of EU law due to their legal effects. We outline some of the risks associated with the partially closed standardisation process, including active impact minimisation by vendors concerned with engineering costs, a lack of public review leading to lower technical quality, and an increased potential for backdoors. Taking a recent (2024) example of cryptographic requirements in such standards, we observe that the definitions and language in the Radio Equipment Directive (RED DA) harmonised standard (EN 18031 series) may allow vendors to take an approach where weak cryptography is considered ``best practice'' right until exploitation is feasible. Recognising recent developments such as the EU Post-Quantum Cryptography transition roadmap, many CRA standardisation working groups are moving towards a ``State-of-the-Art Cryptography'' (SOTA Cryptography) model where approved mechanism listings are published by the European Cybersecurity Certification Group (ECCG). CRA-compliant products may still support other cryptographic mechanisms, but only SOTA is permitted as a safe default for Internet-connected products.

Along with the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) stan- dardization process, efficient hardware acceleration for PQC has become a priority. Among the NIST-selected PQC digital signature schemes, FALCON shows great promise due to its compact key sizes and efficient Signature Verification procedure. However, FALCON is regarded as highly computationally com- plex, and as a result, few works for hardware acceleration of FALCON can be found in the literature, where the few existing ones only target high-performance. To fill the gap, this paper presents a Lightweight and Efficient hardware accelerator for the Signature Verification portion of FALCON (LEAF), specifically for resource-constrained applications. We propose an efficient design strategy, including a novel data dependence flow, to maximize the utilization of very small resources for all arithmetic procedures. Then, the proposed full-hardware LEAF is built, containing an ultra-lightweight number theoretical transform (NTT) core with a novel twiddle factor access pattern. Finally, we conduct a thorough evaluation to demonstrate the efficiency of LEAF. To the best of our knowledge, this is the first lightweight and mean- while most resource-efficient FALCON Signature Verification full- hardware accelerator in the literature, offering 65% and 66% less aggregate resource usage and achieving 24% and 14% less equivalent area-time product (eATP), compared to the state-of- the-art for FALCON-512 and FALCON-1024, respectively. We hope that this work can spur further research in the field.

A distribution is k-incompressible, Yao [FOCS ’82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy, Hastad, Impagliazzo, Levin, and Luby [SICOMP 99], and to other cryptographic hardness assumptions, was unclear. We advance towards a better understating of this notion, showing that a k-incompressible distribution has (k−2) bits of next-block pseudoentropy, a refinement of pseudoentropy introduced by Haitner, Reingold, and Vadhan [SICOMP ’13]. We deduce that a samplable distribution X that is (H(X) + 2)-incompressible, implies the existence of one-way functions.

We present arya-STARK, a unified post-quantum secure framework that enables Aggregation-Robust Yet Authentic training in Federated Learning through transparent zk-STARK proofs. Current federated learning deployments remain vulnerable to malicious or Byzantine clients capable of submitting statistically valid yet adversarial gradients, while also relying on quantum-fragile primitives for authentication. arya-STARK bridges these gaps by combining (i) transparent, hash-based zk-STARK proofs to verify gradient-descent updates at the AIR level, (ii) CRYSTALS-Dilithium signatures to guarantee post-quantum authentication of client commitments, and (iii) a Byzantine-resilient aggregation layer integrating $\ell_2$-clipping and trimmed-mean filtering to mitigate poisoning and backdoor attacks. We introduce a new finite-field encoding scheme that supports exact reconstruction of signed real-valued gradients inside STARK execution traces, enabling full verifiability without leaking client data. Our Rust-based proof-of-concept demonstrates that arya-STARK achieves scalable proof generation, microsecond-level verification, and strong robustness against up to 20% Byzantine clients while preserving high model accuracy. To our knowledge, this is the first system to unify post-quantum authentication, transparent zero-knowledge verification, and Byzantine-robust aggregation into a single architecture for secure federated learning.

CVRFs are PRFs that unify the properties of verifiable and constrained PRFs. Since they were introduced concurrently by Fuchsbauer and Chandran-Raghuraman-Vinayagamurthy in 2014, it has been an open problem to construct CVRFs without using heavy machinery such as multilinear maps, obfuscation or functional encryption. We solve this problem by constructing a prefix-constrained verifiable PRF that does not rely on the aforementioned assumptions. Essentially, our construction is a verifiable version of the Goldreich-Goldwasser-Micali PRF. To achieve verifiability we leverage degree-2 algebraic PRGs and bilinear groups. In short, proofs consist of intermediate values of the Goldreich-Goldwasser-Micali PRF raised to the exponents of group elements. These outputs can be verified using pairings since the underlying PRG is of degree 2. We prove the selective security of our construction under the Decisional Square Diffie-Hellman (DSDH) assumption and a new assumption, which we dub recursive Decisional Diffie-Hellman (recursive DDH). We prove the soundness of recursive DDH in the generic group model assuming the hardness of the Multivariate Quadratic (MQ) problem and a new variant thereof, which we call MQ+. Last, in terms of applications, we observe that our CVRF is also an exponent (C)VRF in the plain model. Exponent VRFs were recently introduced by Boneh et al. (Eurocrypt’25) with various applications to threshold cryptography in mind. In addition to that, we give further applications for prefix-CVRFs in the blockchain setting, namely, stake-pooling and compressible randomness beacons.

Migrating to quantum-resistant cryptographic algorithms, specifically the NIST-standardized Module Learning with Errors (MLWE) primitives, would inevitably result in data transmission overhead in secure transport protocols due to their larger key, ciphertext, and signature sizes. Would the connection setup cost noticeably affect application performance? This study evaluates MLWE's performance impact on practical use cases that rely on TLS 1.3 via real-world experiments. We analyze three distinct scenarios by sharing empirical and experimental data of applications interfacing with cloud service TLS endpoints, Web user metrics, and mutual TLS connections. We argue that some cloud applications will not be significantly affected due to their unconstrained environment. We show that Web performance degradation will remain below 10% for common webpages, corresponding to time delays of under 100ms, which users are unlikely to perceive. For mutual TLS applications, our experiments show that MLWE noticeably affects Time-to-First-Byte, almost doubling the connection times compared to plain TLS. However, when evaluating Time-to-Last-Byte, a metric more closely tied to application performance, the overall impact drops to about 15% for ~150KB data transfers in fast or slow networks. This impact is much lower for large client-server round trips. While these results are reassuring that MLWE could unnoticeably be introduced in common TLS use cases, they do not diminish the value of data trimming techniques proposed in the literature (e.g., session resumption, intermediate certificate authority suppression) to speed up connections.

zkVMs promise general-purpose verifiable computation through ISA-level compatibility with modern programs and toolchains. However, compatibility extends further than just the ISA; modern programs often cannot run or even compile without an operating system and libc. zkVMs attempt to address this by maintaining forks of language-specific runtimes and statically linking them into applications to create self-contained unikernels, but this ad-hoc approach leads to version hell and burdens verifiable applications (vApps) with an unnecessarily large trusted computing base. We solve this problem with ZeroOS, a modular library operating system (libOS) for vApp unikernels; vApp developers can use off-the-shelf toolchains to compile and link only the exact subset of the Linux ABI their vApp needs. Any zkVM team can easily leverage the ZeroOS ecosystem by writing a ZeroOS bootloader for their platform, resulting in a reduced maintainence burden and unifying the entire zkVM ecosystem with consolidated development and audit resources. ZeroOS is free and open-sourced at https://github.com/LayerZero-Labs/ZeroOS

Quantum authentication is a procedure that sends a quantum message to a receiver without being imperceptibly changed in the channel. How to formalize a proper authentication model is a highly non-trivial task. Existing models have various flaws: they either do not capture serious concerns or are over restricted. Most importantly, none of them have addressed the threat from the verification queries. We show that there is a quantum authentication scheme that is secure when no verification query is allowed while it is completely insecure when verification queries are additionally permitted. The threat of verification queries is not artificial. Our attack only needs to know if a forged authentication message is valid or not. It captures the concern that the adversary can watch if the receiver accepts an authentication or not, without even reading the message authenticated. We propose a quantum authentication model that captures the authentication of multiple messages under the same key as well as the verification queries. We allow the attacker to have his own state entangled with the authentication message. Finally, we propose an authentication framework abstracted from the AQA method in Garg et al. (CRYPTO'17) and prove the security in our model. Our result reduces the security of an authentication protocol to certain properties of its component primitives. We also prove that an impersonation attack implies a substitution attack. To our knowledge, this is the first time to confirm this result.

The Fiat-Shamir (FS) transform is a prolific and powerful technique for compiling public-coin interactive protocols into non-interactive ones. Roughly speaking, the idea is to replace the random coins of the verifier with the evaluations of a complex hash function. The FS transform is known to be sound in the random oracle model (i.e., when the hash function is modeled as a totally random function). However, when instantiating the random oracle using a concrete hash function, there are examples of protocols in which the transformation is not sound. So far all of these examples have been contrived protocols that were specifically designed to fail. In this work we show such an attack for a standard and popular interactive succinct argument, based on the GKR protocol, for verifying the correctness of a non-determinstic bounded-depth computation. For every choice of FS hash function, we show that a corresponding instantiation of this protocol, which was been widely studied in the literature and used also in practice, is not (adaptively) sound when compiled with the FS transform. Specifically, we construct an explicit circuit for which we can generate an accepting proof for a false statement. We further extend our attack and show that for every circuit $C$ and desired output $y$, we can construct a functionally equivalent circuit $C^*$, for which we can produce an accepting proof that $C^*$ outputs $y$ (regardless of whether or not this statement is true). This demonstrates that any security guarantee (if such exists) would have to depend on the specific implementation of the circuit $C$, rather than just its functionality. Lastly, we also demonstrate versions of the attack that violate non-adaptive soundness of the protocol -- that is, we generate an attacking circuit that is independent of the underlying cryptographic objects. However, these versions are either less practical (as the attacking circuit has very large depth) or make some additional (reasonable) assumptions on the underlying cryptographic primitives.

We give new constructions of cycles of pairing-friendly elliptic curves with a view towards unbounded recursive pairing-based proof systems. Unlike the only known prior cycle of elliptic curves - the ordinary MNT cycle - our construction uses elliptic curves that are supersingular. A trade-off of our approach is that the supersingular cycles are defined over extension fields (quadratic extensions in the optimal case), which makes elements and computations in $\mathbb{G}_1$ less compact and efficient than those in the MNT cycle. On the other hand, the supersingular cycles in this paper offer a key advantage over their MNT counterpart: every instance of our infinite family of supersingular curves can be efficiently constructed via Broker's algorithm, whereas it is only feasible to construct a relatively small, bounded number of MNT instances via the CM method. In other words, while both constructions give infinite families of pairing-friendly curves in theory, only the supersingular construction gives rise to infinite numbers of cycles that can be realised in practice. Supersingular cycles offer benefits that are relevant in the context of recursive pairing-based proof systems. They afford flexibility in the choices of underlying finite fields; one can choose primes $p$ for which the underlying field arithmetic is efficient and for which $p-1$ is divisible by a large power of 2. Or, as we study in detail, using supersingular cycles unlocks the possibility of connecting the cycle with other pairing-friendly elliptic curves that are defined over much smaller finite fields, where proof system arithmetic is much more efficient. Indeed, constructing these so-called lollipops of pairing-friendly curves was the motivating problem (posed by researchers back in 2019) that inspired the present work.

Cloud computing enables data processing, storing and sharing in untrusted environments whose growing adoption necessitates a focus on data security and privacy. Inner product functional encryption (IPFE) is a promising cryptographic technique that enables fine-grained access control over sensitive data in untrusted cloud environments. Post-quantum cryptography focuses on developing cryptographic protocols resilient to quantum computer attacks, with lattice structures being crucial in designing these protocols. This paper aims to implement the lattice-based public key unbounded IPFE (uIPFE) scheme proposed by Dutta et al. (2022) [1] which ensures that no specific vector’s length bound needs to be fixed during public parameter generation. Furthermore, we extend the ALS-IPFE scheme of Agrawal et al. (2016) [2] to create a new public key scheme uIPFE #1, achieving adaptive indistinguishability security in the random oracle model under the Learning with Errors assumption, while avoiding trapdoor generation and pre-image sampling algorithms. This work aims to enhance the practical applicability of uIPFE in cloud computing environments. We implement both the schemes uIPFE and uIPFE #1 in C programming language and execute the code on IBM Power 9 server. Moreover, we analyze the running time and discuss the performance of both schemes based on varying message vector lengths.

Authenticity and confidentiality are crucial for maintaining a secure information infrastructure. Confidentiality prevents unauthorized disclosure, while authenticity ensures origin of the data.. Authenticated encryption ensures both simultaneously by protecting data from access and verifying integrity. This paper presents a NeevAs cipher suite offering authenticated encryption with associated data (AEAD) and hashing, based on a sponge-based duplex construction. The scheme included concurrent absorption, a novel sponge method, where associated data is absorbed into the capacity part and plaintext into the rate part simultaneously. This reduces permutation calls typically required for associated data processing compared to existing sponge based designs. In the NeevAs cipher suite, the modified Neeva hash function generates the security tag, and the Ascon S-box provides efficiency and resistance against differential and boomerang attacks. The design targets lightweight cryptography, minimizing permutation calls to enhance efficiency and reduce resource consumption, making it well-suited for resource-constrained devices.

The rapid growth of quantum technologies highlights the need for scalable models of computation that go beyond qubits and exploit the richer structure of Qudits. This paper introduces a novel and efficient approach for defining universal gate sets specifically designed for higher-dimensional Qudit systems (N ≥ 2), addressing the limitations of traditional qubit-based approaches. We present a systematic methodology for constructing fundamental Qudit gates through the inherent structure of Qudit operators, providing a robust theoretical foundation for universal quantum computation with Qudits. Our rigorously proven universal and minimal gate set enables more efficient quantum circuit design. We demonstrate the construction of multidimensional extensions of controlled operations from these fundamental elements. To facilitate practical application, we provide a Python-based algorithm for decomposing arbitrary multi-Qudit operations, accompanied by detailed time- and space-complexity analyses. The framework is further validated through end-to-end implementations of Grover’s algorithm and QKD, comparing traditional gate constructions with circuits entirely synthesized from the proposed universal gate set. These validations demonstrate not only the functional equivalence of the decomposed circuits, but also their direct relevance to the advancement of cryptographic protocols, paving the way for more efficient and secure Qudit-based quantum cryptography.

The Polynomial Modular Number System (PMNS) is a non-positional number system for modular arithmetic. A PMNS is defined by a tuple $(p, n, \gamma, \rho, E)$, where $p$, $n$, $\gamma$ and $\rho$ are positive non-zero integers and $E\in\mathbb{Z}_{n}[X]$ is a monic polynomial such that $E(\gamma) \equiv 0 \pmod p$. The PMNS is a redundant number system. This redundancy property has already been used to randomise the data during the Elliptic Curve Scalar Multiplication (ECSM). In this paper, we refine the results on redundancy and propose several new results on PMNS. More precisely, we study a generalisation of the Montgomery-like internal reduction method proposed Negre and Plantard, along with some improvements on parameter bounds for smaller memory cost to represent elements in this system. We also show how to perform equality test in the PMNS. This open problem has been a limitation for the use of PMNS in cryptography. Finally, as an application, we show the use of the Elliptic Curve Diffie Hellman key agreement protocol with PMNS, without needing another number system. We also provide SageMath and C implementations. We make some comparisons with the OpenSSL library.

We provide several attacks on the BASS signature scheme introduced by Grigoriev, Ilmer, Ovchinnikov and Shpilrain in 2023. We lay out a trivial forgery attack which generates signatures passing the scheme's probabilistic signature verification with high probability. Generating these forgeries is faster than generating signatures honestly. Moreover, we describe a key-only attack which allows us to recover an equivalent private key from a signer's public key. The time complexity of this recovery is asymptotically the same as that of signing messages.

Fuzzy-labeled private set intersection (PSI) outputs the corresponding label if there is a ``fuzzy'' match between two items, for example, when the Hamming distance is low between the two items. Such protocols can be applied in privacy-preserving biometric authentication, proximity testing, and so on. The only fuzzy-labeled PSI protocol designed for practical purposes is by Uzun et al. (USENIX’21), which is based on homomorphic encryption. This design puts constraints on the item size, label size, and communication cost since it is difficult for homomorphic encryption to support large plaintext space and it is well-known that the ciphertext-expansion factor is large. Our construction begins with a new primitive which we call vector ring-oblivious linear evaluation (vector ring-OLE). This primitive does not rely on existing instantiations of ring-OLE over the quotient ring, but leverages the more efficient vector-OLE. It is ideal for building unbalanced threshold-labeled PSI and is also of independent interest. Our main contribution, fuzzy-labeled PSI, is bootstrapped from our threshold-labeled PSI protocol. Through a prototype implementation, we demonstrate our communication cost is up to $4.6\times$ better than the prior state-of-the-art with comparable end-to-end latency while supporting a significantly higher label size.

Fresh re-keying is a countermeasure against side-channel analysis where an ephemeral key is derived from a long-term key using a public random value. Popular instances of such schemes rely on key-homomorphic primitives, so that the re-keying process is easy to mask and the rest of the (e.g., block cipher) computations can run with cheaper countermeasures. The main requirement for these schemes to be secure is that the leakages of the ephemeral keys do not allow recovering the long-term key. The Learning with Physical Rounding (LWPR) problem formalizes this security in a practically-relevant model where the adversary can observe noise-free leakages. It can be viewed as a physical version of the Learning With Rounding (LWR) problem, where the rounding is performed by a leakage function and therefore does not have to be computed explicitly. In this paper, we first consolidate the intuition that LWPR cannot be secure in a serial implementation context without additional countermeasures (like shuffling), due to attacks exploiting worst-case leakages that can be mounted with practical data complexity. We then extend the understanding of LWPR in a parallel implementation setting. On the one hand, we generalize its robustness against cryptanalysis taking advantage of any (i.e., not only worst-case) leakage. A previous work claimed security in the specific context of a Hamming weight leakage function. We clarify necessary conditions to maintain this guarantee, based on the degree of the leakage function and the accuracy of its coefficients. On the other hand, we show that parallelism inherently provides good security against attacks exploiting worst-case leakages. We finally confirm the practical relevance of these findings by validating our assumptions experimentally for an exemplary implementation.

In the past, Secure Onboard Communication (SecOC) has been defined to serve as the foundational mechanism for securing in-vehicle networks. For over a decade, it has been used in hundreds of millions of automotive systems. Its application-layer design and AUTOSAR-based specification have enabled broad adoption across diverse platforms. However, this design also introduces challenges: software-centric dependencies complicate full hardware integration and can limit scalability in resource-constrained electronic control units, particularly as bandwidth demands continue to grow. To address these constraints, CANsec has been proposed to address the security objectives of CAN XL. As a Layer 2 security protocol, CANsec aims to overcome SecOC’s shortcomings and offer modern guarantees comparable to MACsec. However, the CANsec specification remains under active development even after several years of work, leaving a gap between conceptual goals and practical deployment. This paper proposes a pragmatic and standards-aligned solution: it re-uses existing MACsec specifications and implementations as the security engine for CAN XL. MACsec, standardized for over two decades and widely scrutinized in both academic and industrial contexts, offers robust and well-understood security functions. Our approach introduces a lightweight wrapper that maps CAN XL frames to virtual Ethernet frames, enabling MACsec to provide confidentiality, integrity, authenticity, and freshness. We formally define the wrapping process, frame formats, and protocol data units, while preserving MACsec’s security properties, adapting them to the constraints and requirements of automotive networks. This enables a practical and secure path forward for CAN XL deployment, leveraging mature cryptographic algorithms and protocols without compromising performance or assurance. To support standardization and practical adoption, we have submitted this approach to the CAN in Automation (CiA) CANsec specification task force, CiA's IG 04 SIG 01 TF 03 CAN XL security, contributing to the ongoing effort to define an efficient, standardized and interoperable security solution for CAN XL.

We analyze security aspects of the SecureDNA system regarding its system design, engineering, and implementation. This system enables DNA synthesizers to screen order requests against a database of hazards. By applying novel cryptography involving distributed oblivious pseudorandom functions, the system aims to keep order requests and the database of hazards secret. Discerning the detailed operation of the system in part from source code (Version 1.0.8), our analysis examines key management, certificate infrastructure, authentication, and rate-limiting mechanisms. We also perform the first formal-methods analysis of the mutual authentication, basic request, and exemption-handling protocols. Without breaking the cryptography, our main finding is that SecureDNA's custom mutual authentication protocol SCEP achieves only one-way authentication: the hazards database and keyservers never learn with whom they communicate. This structural weakness violates the principle of defense in depth and enables an adversary to circumvent rate limits that protect the secrecy of the hazards database, if the synthesizer connects with a malicious or corrupted keyserver or hashed database. We point out an additional structural weakness that also violates the principle of defense in depth: inadequate cryptographic bindings prevent the system from detecting if responses, within a TLS channel, from the hazards database were modified. Consequently, if a synthesizer were to reconnect with the database over the same TLS session, an adversary could replay and swap responses from the database without breaking TLS. Although the SecureDNA implementation does not allow such reconnections, it would be stronger security engineering to avoid the underlying structural weakness. We identify these vulnerabilities and suggest and verify mitigations, including adding strong bindings. Software Version 1.1.0 fixes SCEP with our proposed SCEP+ protocol. Our work illustrates that a secure system needs more than sound mathematical cryptography; it also requires formal specifications, sound key management, proper binding of protocol message components, and careful attention to engineering and implementation details.

We present a practical, non-interactive threshold decryption scheme. It can be proven CCA secure with respect to adaptive corruptions in the random oracle model under the decisional Diffie-Hellman assumption. Our scheme, called TDH2a, is a minor modification on the TDH2 scheme presented by Shoup and Gennaro at Eurocrypt 1998, which was proven secure against static corruptions under the same assumptions. The design and analysis of TDH2a are based on a straightforward extension of the simple information-theoretic argument underlying the security of the Cramer-Shoup encryption scheme presented at Crypto 1998. We also present another variant, TDH2abc, which offers a higher degree of backward compatibility with TDH2, allowing one to effectively "hot swap" TDH2abc in to replace TDH2 in a "live" system, without changing the public encryption key, so that any extant ciphertexts remain decryptable.

In the Web2 world, users control their accounts using credentials such as usernames and passwords, which can be reset or recovered by centralized servers if the user loses them. In the decentralized Web3 world however, users control their accounts through cryptographic private-public key pairs which are much more complex to manage securely. In addition, the decentralized nature of Web3 makes account recovery impossible in the absence of predetermined recovery mechanisms. With the proliferation of blockchains and cryptocurrencies over the last years, it is crucial to provide users secure, usable and reliable ways to recover their accounts and assets. However, up to this day, no Web3 recovery method has adequately achieved all three of the above required properties. For instance, conventional ``mnemonic" backups which can deterministically reconstruct a private key require verbatim recall of a fixed word list, creating an unpleasant usability/security trade-off. In this work, we present a fully-offline protocol called LifeXP$^{+}$, that allows a user to reconstruct a cryptographically-secure private key from a natural-language story, which a user always remembers, such an memorable life event. To ensure usability of our protocol, key reconstruction can work even when the story is later retold with different wording or grammar, only requiring to preserve the semantics. The protocol combines pre-trained sentence embeddings to capture semantics, locality-sensitive hashing to quantize embeddings into stable bit strings, a cryptographic fuzzy extractor that corrects bit errors caused by paraphrasing, and a biometric factor that is fused with the linguistic factor to boost entropy and enhance security. In our paper we describe the design, show that the protocol achieves the required properties, and provide an evaluation based on publicly-available datasets which runs completely offline on commodity hardware, showcasing its feasibility.

Anonymous rate-limited tokens are a special type of credential that can be used to improve the efficiency of privacy-preserving authentication systems like Privacy Pass. In such a scheme, a user obtains a "token dispenser" by interacting with an issuer, and the dispenser allows the user to create up to a pre-determined number $k$ of unlinkable and publicly verifiable tokens. Unlinkable means that one should not be able to tell that two tokens originate from the same dispenser, but also they cannot be linked to the interaction that generated the dispenser. Furthermore, we can limit the rate at which these tokens are created by linking each token to a context (e.g., the service we are authenticating to), and imposing a limit $N \leq k$ such that seeing more than $N$ tokens for the same context will reveal the identity of the user. Constructions of such tokens were first given by Camenisch, Hohenberger and Lysyanskaya (EUROCRYPT '05) and Camenisch, Hohenberger, Kohlweiss, Lysyanskaya, and Meyerovich (CCS '06). In this work, we present the first construction of \emph{everlasting} anonymous rate-limited tokens, for which unlinkability holds against computationally unbounded adversaries, whereas other security properties (e.g., unforgeability) remain computational. Our construction relies on pairings. While several parameters in our construction unavoidably grow with $k$, the key challenge we resolve is ensuring that the complexity of dispensing a token is independent of the parameter $k$. We are motivated here by the goal of providing solutions that are robust to potential future quantum attacks against the anonymity of previously stored tokens. A construction based on post-quantum secure assumptions (e.g., based on lattices) would be rather inefficient---instead, we take a pragmatic approach dispensing with post-quantum security for properties not related to privacy.

At NeurIPS 2024, Kera et al. introduced the use of transformers for computing Groebner bases, a central object in computer algebra with numerous practical applications. In this paper, we improve this approach by applying Hierarchical Attention Transformers (HATs) to solve systems of multivariate polynomial equations via Groebner bases computation. The HAT architecture incorporates a tree-structured inductive bias that enables the modeling of hierarchical relationships present in the data and thus achieves significant computational savings compared to conventional flat attention models. We generalize to arbitrary depths and include a detailed computational cost analysis. Combined with curriculum learning, our method solves instances that are much larger than those in Kera et al. (2024 Learning to compute Groebner bases)

The Linear Code Equivalence (LCE) problem and the Matrix Code Equivalence (MCE) problem are two examples of code-based hard problems that have gained attention as candidates for use in post-quantum cryptography. They are straightforward to implement, can be viewed as group actions, and offer a good trade-off between compactness and performance in the realm of post-quantum group actions. With the community gaining confidence in the security of these problems, new variants of these problems have been introduced to achieve particular functionalities in advanced protocols or efficiency improvements. A natural question is then whether the problem variants are as secure as the original ones. In this work, we consider three problem variants of LCE or MCE. We first consider a variant based on LCE, and reduce it to the original LCE assumption. This problem was presented in a prior version of the blind signature scheme, proposed by Duong, Khuc, Qiao, Susilo and Zhang. Second, we analyse an MCE variant, MIMCE, proposed in the context of another blind signature scheme, by Kutcha, Legrow and Persichetti, and show that the parameters proposed are not sufficient to reach the claimed bit security. Finally, we consider a multi-sample version of MIMCE which we solve in polynomial time.

We propose BLASter, a proof of concept LLL implementation that demonstrates the practicality of multiple theoretical improvements. The implementation uses the segmentation strategy from Neumaier–Stehlé (ISSAC 2016), parallelism and Seysen's reduction that was proposed by Kirchner–Espitau–Fouque (CRYPTO 2021) and implemented in OptLLL, and the BLAS library for linear algebra operations. It consists of only 1000 significant lines of C++ and Python code, and is made publicly available. For q-ary lattices that fplll can handle without multiprecision (dimension <180), BLASter is considerably faster than fplll, OptLLL and Ryan–Heninger's flatter (CRYPTO 2023), without degrading output reduction quality. Thanks to Seysen's reduction it can further handle larger dimension without resorting to multiprecision, making it more than 10x faster than flatter and OptLLL, and 100x faster than fplll in dimensions 256 to 1024. It further includes segmented BKZ and segmented deep-LLL variants. The latter provides bases as good as BKZ-15 and has a runtime that is only a couple of times more than our LLL baseline. This remains a proof of concept: the effective use of higher precision—which is needed to handle \(\textit{all}\) lattices—has further obstacles and is left for future work. Still, this work contains many lessons learned, and is meant to motivate and guide the development of a robust and modern lattice reduction library, which shall be much faster than fplll.

Private Simultaneous Messages (PSM) is a minimal model for secure computation, where two parties, Alice and Bob, have private inputs $x,y$ and a shared random string. Each of them sends a single message to an external party, Charlie, who can compute $f(x,y)$ for a public function $f$ but learns nothing else. The problem of narrowing the gap between upper and lower bounds on the communication complexity of PSM has been widely studied, but the gap still remains exponential. In this work, we study the communication complexity of PSM from a different perspective and introduce a special class of PSM, referred to as \textit{ideal PSM}, in which each party's message length attains the minimum, that is, their messages are taken from the same domain as inputs. We initiate a systematic study of ideal PSM with a complete characterization, several positive results, and applications. First, we provide a characterization of the class of functions that admit ideal PSM, based on permutation groups acting on the input domain. This characterization allows us to derive asymptotic upper bounds on the total number of such functions and a complete list for small domains. We also present several infinite families of functions of practical interest that admit ideal PSM. Interestingly, by simply restricting the input domains of these ideal PSM schemes, we can recover most of the existing PSM schemes that achieve the best known communication complexity in various computation models. As applications, we show that these ideal PSM schemes yield novel communication-efficient PSM schemes for functions with sparse or dense truth-tables and those with low-rank truth-tables. Furthermore, we obtain a PSM scheme for general functions that improves the constant factor in the dominant term of the best known communication complexity. An additional advantage is that our scheme simplifies the existing construction by avoiding the hierarchical design of internally invoking PSM schemes for smaller functions.

Ateniese et al. (CRYPTO 2019/JoC 2021) introduced a cryptographic primitive which they call matchmaking encryption (ME), and Identity-based ME (IB-ME) is its identity-based variant. IB-ME supports an equality matching where a sender (encryptor) indicates a receiver's (decryptor's) identity (rcv) in addition to their own ID ($\sigma$), and a receiver indicates a sender's identity (snd) in addition to the own identity ($\rho$). A ciphertext is decrypted if $(\sigma,\rho)=$(snd,rcv). In this paper, we pay attention to the search condition of public key authenticated encryption with keyword search (PAEKS) (Huang-Li, Information Sciences 2017) is reminiscent of the equality matching. We introduce a public key variant of ME which we call PK-ME, and propose a generic construction of PK-ME from PAEKS. As a conceptual contribution, our work lies in revealing a connection between ME and public key searchable encryption, which were independently researched so far. Due to the generic construction of PAEKS (Li-Boyen, IACR CiC 2024), we can instantiate the proposed generic construction from pairings or lattices. We also introduce a weaker version of authenticity and show that it can be instantiated from several complexity assumptions. Finally, we discuss the advantage/disadvantage of PK-ME compared to IB-ME.

Fully Homomorphic Encryption (FHE) enables secure computation over encrypted data, offering a breakthrough in privacy-preserving computing. Despite its promise, the practical deployment of FHE has been hindered by the significant computational overhead, especially in general-purpose bootstrapping schemes. In this work, we build upon the recent advancements of [LY23] to introduce a variant of the functional/programmable bootstrapping. By carefully sorting the steps of the blind rotation, we reduce the overall number of external products without compromising correctness. To further enhance efficiency, we propose a novel modulus-switching technique that increases the likelihood of satisfying pruning conditions, reducing computational overhead. Extensive benchmarks demonstrate that our method achieves a speedup ranging from 1.75x to 8.28x compared to traditional bootstrapping and from 1.26x to 2.14x compared to [LY23] bootstrapping techniques. Moreover, we show that this technique is better adapted to the IND-CPA-D security model by reducing the performance downgrade it implies.

We revisit the longstanding open problem of implementing Nakamoto's proof-of-work (PoW) consensus based on a real-world computational task $T(x)$ (as opposed to artificial random hashing), in a truly permissionless setting where the miner itself chooses the input $x$. The challenge in designing such a Proof-of-Useful-Work (PoUW) protocol, is using the native computation of $T(x)$ to produce a PoW certificate with prescribed hardness and with negligible computational overhead over the worst-case complexity of $T(\cdot)$ -- This ensures malicious miners cannot ``game the system" by fooling the verifier to accept with higher probability compared to honest miners (while using similar computational resources). Indeed, obtaining a PoUW with $O(1)$-factor overhead is trivial for any task $T$, but also useless. Our main result is a PoUW for the task of Matrix Multiplication $\mathsf{MatMul}(A,B)$ of arbitrary matrices with $1+o(1)$ multiplicative overhead compared to na\"ive $\mathsf{MatMul}$ (even in the presence of Fast Matrix Multiplication-style algorithms, which are currently impractical). We conjecture that our protocol has optimal security in the sense that a malicious prover cannot obtain any significant advantage over an honest prover. This conjecture is based on reducing hardness of our protocol to the task of solving a batch of low-rank random linear equations which is of independent interest. Since $\mathsf{MatMul}$s are the bottleneck of AI compute as well as countless industry-scale applications, this primitive suggests a concrete design of a new L1 base-layer protocol, which nearly eliminates the energy-waste of Bitcoin mining -- allowing GPU consumers to reduce their AI training and inference costs by ``re-using" it for blockchain consensus, in exchange for block rewards (2-for-1). This blockchain is currently under construction.

The meet-in-the-middle (MITM) attack is a powerful cryptanalytic technique leveraging time-memory tradeoffs to break cryptographic primitives. Initially introduced for block cipher cryptanalysis, it has since been extended to hash functions, particularly preimage attacks on AES-based compression functions. Over the years, various enhancements such as superposition MITM (Bao et al., CRYPTO 2022) and bidirectional propagations have significantly improved MITM attacks, but at the cost of increasing complexity of automated search models. In this work, we propose a unified mixed integer linear programming (MILP) model designed to improve the search for optimal pre-image MITM attacks against AES-based compression functions. Our model generalizes previous approaches by simplifying both the modeling and the corresponding attack algorithm. In particular, it ensures that all identified attacks are valid. The results demonstrate that our framework not only recovers known attacks on AES and Whirlpool but also discovers new attacks with lower memory complexities, and new quantum attacks.

We introduce the notion of non-interactive zero-knowledge (NIZK) arguments with certified deletion, a new primitive that enables the recipient of a (quantum) NIZK argument to delete it and obtain a (classical) certificate proving such deletion. We formalize this notion and propose two candidate constructions from standard cryptographic assumptions. Our first construction is based on classical NIZK arguments and quantum-hard one-way functions, but requires both the prover and verifier to run quantum algorithms. We then present an extension based on the learning with errors problem that allows the prover to be classical. Our results have applications to signatures of knowledge and anonymous credentials with certified deletion, which we also define and construct.

A zero-knowledge proof of machine learning (zkML) enables a party to prove that it has correctly executed a committed model using some public input, without revealing any information about the model itself. An ideal zkML scheme should conceal both the model architecture and the model parameters. However, existing zkML approaches for neural networks primarily focus on hiding model parameters. For convolutional neural network (CNN) models, these schemes reveal the entire architecture, including number and sequence of layers, kernel sizes, strides, and residual connections. In this work, we initiate the study of architecture-private zkML for neural networks, with a focus on CNN models. Our core contributions includes 1) parametrized rank-one constraint system (pR1CS), a generalization of R1CS, allowing the prover to commit to the model architecture in a more friendly manner; 2) a proof of functional relation scheme to demonstrate the committed architecture is valid. Our scheme matches the prover complexity of BFG+23 (CCS'23), the current state-of-the-art in zkML for CNNs. Concretely, on VGG16 model, when batch proving 64 instances, our scheme achieves only 30% slower prover time than BFG+23 (CCS'23) and 2.3$\times$ faster than zkCNN (CCS'21). This demonstrates that our approach can hide the architecture in zero-knowledge proofs for neural networks with minor overhead. In particular, proving a matrix multiplication using our pR1CS can be at least 3$\times$ faster than using conventional R1CS, highlighting the effectiveness of our optimizations.

Cube attack is one of the most powerful approaches for recovering keys of stream ciphers. Practical cube attacks generate several superpolys first and solve the system constructed by these superpolys afterward. Unlike previous practical attacks, we propose a new cube attack that transfers the difficulty of generating easy-solving superpolys to solving the system built by numerous nonlinear ones. In the offline phase, we recovered lots of nonlinear superpolys by improving the approach proposed by Delaune et al. at SAC 2022 in theory. In the online phase, taking advantage of the sparsity and asymmetry of these numerous superpolys, we present a new testing method to solve the constructed system efficiently. As applications, the latest attack could practically recover the keys for 820- and 832-round Trivium with the time complexity no more extensive than $2^{46}$ and $2^{50}$, while the previous highest number of rounds of Trivium that can be attacked practically is 830. We believe the proposed approach can be used to attack more rounds of Trivium and other stream ciphers.

Signal's handshake protocol non-interactively generates a shared key between two parties for secure communication. The underlying protocol X3DH, on which the post-quantum hybrid successor, PQXDH, builds, computes three to four individual Diffie-Hellman (DH) keys by combining the long-term identity keys and the ephemeral secrets of the two parties. Each of these DH operations serves a different purpose, either to authenticate the derived key or to provide forward secrecy. We present here an improved protocol for X3DH, which we call MuDH, and an improved protocol for PQXDH, pq-MuDH. Instead of computing the individual DH keys, we run a single multi-valued DH operation for integrating all contributions simultaneously into a single DH key. Our approach is based on techniques from batch verification (Bellare et al., Eurocrypt 1998), where one randomizes each contribution of the individual keys to get a secure scheme. The solution results in execution times of roughly 60% of the original protocol, both in theory and in our benchmarks on mobile and desktop platforms. Our modifications are confined to the key derivation step, both Signal’s server infrastructure for public key retrieval and the message flow remain unchanged.

Post-quantum cryptography (PQC) is essential to securing data in the quantum computing era, and standardization efforts led by NIST have driven extensive research on practical and efficient implementations. With the emerging deployment of ARMv9-A processors in mobile and edge devices, optimizing PQC algorithms for this architecture is becoming increasingly important. Among the NIST-selected digital signature schemes, ML-DSA stands out due to its strong security and efficiency, making it suitable for general purposes. In this work, we present a highly optimized implementation of ML-DSA for the ARMv9-A architecture, leveraging the SVE2 vector instruction set. We propose a vector-friendly sparse polynomial multiplication scheme and introduce an early-check mechanism that significantly reduces redundant computation in the signature validity check. We also design a tailored conditional instruction pipeline to further enhance efficiency. Our implementation achieves a 70.7% performance improvement in signature generation compared to the baseline implementation, establishing the first highly vectorized ML-DSA implementation on ARMv9-A by SVE2 extension. These results demonstrate the practicality of deploying high-performance post-quantum signatures on next-generation mobile and edge platforms.

We present a unified framework for constructing registered attribute-based encryption (RABE) and registered functional encryption (RFE) from the standard (bilateral) $k$-Lin assumption in asymmetric bilinear pairing groups. Specifically, our schemes capture the following functionalities. - RABE for logspace Turing machines. We present the first RABE for deterministic and nondeterministic logspace Turing machines (TMs), corresponding to the uniform complexity classes $\mathsf L$ and $\mathsf{NL}$. That is, we consider policies $g$ computable by a TM with a polynomial time bound $T$ and a logarithmic space bound $S$. The public parameters of our schemes scale only with the number of states of the TM, but remain independent of the attribute length and the bounds $T,S$. Thus, our system is capable of verifying unbounded-length attributes $\mathbf y$ while the maximum number of states needs to be fixed upfront. - RFE for attribute-based attribute-weighted sums (AB-AWS). Building upon our RABE, we develop RFE for AB-AWS. In this functionality, a function is described by a tuple $f=(g,h)$, takes $(\mathbf y, \{(\mathbf x_j, \mathbf z_j)\}_{j\in[N]})$ as input for an unbounded integer $N$, and outputs $\sum_{j\in[N]}\mathbf z_jh(\mathbf x_j)^\top$ if and only if $g(\mathbf y) = 0$. Here, $\{\mathbf z_j\}_j$ are private inputs that are hidden in the ciphertext, whereas $\mathbf y$ and $\{\mathbf x_j\}_j$ can be public. Our construction can instantiate $g,h$ with deterministic logspace TMs, while a previous construction due to [Pal and Schädlich, Eprint 2025] only supports arithmetic branching programs (ABPs), i.e. a non-uniform model of computation. - RFE for attribute-based quadratic functions (AB-QF). Furthermore, we build the first RFE for AB-QF with compact ciphertexts. In this functionality, a function is described by a tuple $f=(g,\mathbf h)$, takes input $(\mathbf y,(\mathbf z_1,\mathbf z_2))$ and outputs $(\mathbf z_1\otimes\mathbf z_2)\mathbf h^\top$ if and only if $g(\mathbf y)=0$. Here, $(\mathbf z_1, \mathbf z_2)$ are private inputs whereas the attribute $\mathbf y$ is public. Policies can be computed by ABPs or deterministic logspace TMs. Prior to our work, the only known construction of RFE for quadratic functions from standard assumptions [Zhu et al., Eurocrypt 2024] did not provide any access control. Conceptually, we transfer the framework of [Lin and Luo, Eurocrypt 2020], which combines linear FE with information-theoretic garbling schemes, from standard to registered FE. At the core of our constructions, we introduce a novel RFE for inner products with user-specific pre-constraining of the functions which enables the on-the-fly randomization of garbling schemes akin to standard inner-product FE. This solves an open question raised in [Zhu et al., Asiacrypt 2023] who constructed RABE from predicate encodings but left open the problem of building RABE in a more general setting from linear garbling schemes.

We propose two novel instantiations for the NICE-PAKE and TEMPO protocols, which were presented by Alnahawi et al. (ePrint:2024/1957), and Arriaga, Barbosa and Jarecki (ePrint:2025/1399) repectively. Our instantiations are not formally analyzed yet, but build upon known KEM security assumptions and well-studied PAKE designs. Therefore, we believe there is a great chance that a formal proof in the Universal Composability (UC) framework should also hold. Our constructions combine three concepts: 1) Lattice KEMs with Splittable public keys of the form As+e as introduced in Arriaga et al. (AC24:ABJS), Alnahawi et al. (ePrint:2024/1957) and Arriaga et al. (ePrint:2025/1399). 2) The Programmable Only Once Function (POPF) realized as a 2-round Feistel (2F) as in McQuoid, Rosulek and Roy (CCS20:MRR) and Arriaga , Barbosa and Jarecki (ePrint:2025/231). 3) Rerandomizable KEM as introduced in Duverger et al. (CCS25:DFJ+). Similar to the aforementioned works, our goal is to eliminate the usage of the Ideal Cipher (IC) in (O)EKE-style KEM-based PQC PAKEs, the motivation of which is adequately and extensively explained in the cited literature. Our main contribution lies within the following two aspects: 1) Mitigating malicious public key generation attacks in the NICE-PAKE construction. 2) Defining a mechanism to realize the missing group operation in the 2F public key authentication step in NoIC-PAKE. Briefly put, we utilize the rerandomization procedure of (CCS25:DFJ+) to sample a second uniform MLWE sample, which is in turn used to shift the initiator's public key forming another fresh sample that yields indistinguishable from uniform. By doing so, we assume that we can enhance the security of NICE-PAKE to withstand a certain class of attacks, and reduce the computational complexity of the 2F instantiation relying on obfuscation in the OQUAKE variant of the 2F PAKE, which was introduced by Vos et al. (ePrint:2025/1343). Obviously, we cannot ascertain the security of our proposed constructions without conducting a complete and thorough formal analysis. Hence, remaining open questions and future work include defining an indistinguishable UC simulator in the ideal UC world that is also capable of extracting adversarial password guesses. Further, we need to identify the concrete KEM properties required to prove security in UC via the common game-hopping reductionist proof approach.

We consider 3 related cryptographic primitives, private information retrieval (PIR) protocols, conditional disclosure of secrets (CDS) protocols, and secret-sharing schemes; these primitives have many applications in cryptography. We study these primitives requiring information-theoretic security. The complexity of the three primitives has been dramatically improved in the last few years and they are closely related, i.e., the 2-server PIR protocol of Dvir and Gopi (J. ACM 2016) was transformed to construct the CDS protocols of Liu, Vaikuntanathan, and Wee (CRYPTO 2017, Eurocrypt 2018) and these CDS protocols are the main ingredient in the construction of the best-known secret-sharing schemes. To date, the message size required in PIR and CDS protocols and the share size required in secret-sharing schemes are not understood and there are big gaps between their upper bounds and lower bounds. The goal of this paper is to try to better understand the upper bounds by simplifying current constructions and supplying tools for improving their complexity. We obtain the following results: - We simplify, abstract, and generalize the 2-server PIR protocol of Dvir and Gopi (J. ACM 2016), the recent multi-server PIR protocol of Ghasemi, Kopparty, and Sudan (STOC 2025), and the 2-server and multi-server CDS protocols of Liu et al.\ (CRYPTO 2017, Eurocrypt 2018) and Beimel, Farr\`as, and Lasri (TCC 2023). In particular, we present one PIR protocol generalizing both the 2-server and multi-server PIR protocols using general share conversions. For $k\geq 3$ servers, our main contribution is a simpler proof the correctness of the protocol, avoiding the partial derivatives and interpolation polynomials used by Ghasemi et al. - In addition to simplifying previous protocols, our 2-server protocols can use a relaxed variant of matching vectors over any $m$ that is the product of two distinct primes. Our constructions do not improve the communication complexity of PIR and CDS protocols; however, construction of better relaxed matching vectors over \emph{any} $m$ that is the product of two distinct primes will improve the communication complexity of $2$-server PIR and $2$-server CDS protocols. - In many applications of secret-sharing schemes it is important that the scheme is linear, e.g., by using the fact that parties can locally add shares of two secrets and obtain shares of the sum of the secrets. In an independent result, we provide a construction of linear secret-sharing schemes for $n$-party access structures with improved share size of $2^{0.7563n}$. Previously, the best share size for linear secret-sharing schemes was $2^{0.7576n}$ and it is known that for most $n$-party access structures the shares' size is at least $2^{0.5n}$. This result is achieved by a reduction to unbalanced CDS protocols (compared to balanced CDS protocols in previous constructions).

Randomized functional encryption (rFE) generalizes functional encryption (FE) by incorporating randomized functionalities. Randomized multi-input functional encryption (rMIFE) extends rFE to accommodate multi-input randomized functionalities. In this paper, we reassess the framework of rFE/rMIFE enhancing our understanding of this primitive and laying the groundwork for more secure and flexible constructions in this field. Specifically, we make three key contributions: - Stronger IND definition: We show the prevailing indistinguishability-based security definition protects only against malicious decryptors and leaves systems vulnerable to malicious encryptors -- a critical requirement for rFE/rMIFE since their inception. We then propose a refined IND notion that simultaneously handles both threats. - Separating counterexample: Illustrating this definitional gap, we meticulously craft an rFE scheme -- using standard tools (FE, PRF, PKE, simulation‑sound NIZK) -- that satisfies the old definition yet is blatantly insecure in practice (and where this insecurity would be precluded by our enhanced definition). - Adaptive, unbounded‑message rMIFE: The sole, viable prior rMIFE construction by Goldwasser et al. [EUROCRYPT 2014] permits only a fixed message bound per encryption slot and offers merely selective security. Leveraging sub‑exponentially secure indistinguishability obfuscation and techniques of Goyal et al. [ASIACRYPT 2016] built for deterministic MIFE, we give the first rMIFE scheme that supports an unbounded number of messages per slot and attains full adaptive security.

This paper presents the first adaptively secure streaming functional encryption (sFE) scheme for P/Poly. sFE extends traditional FE to vast and/or dynamically evolving data sets, enabling incremental encryption of streaming inputs and iterative partial decryption over encrypted prefixes. The proposed sFE scheme is built from indistinguishability obfuscation for P/Poly and injective PRGs. We achieve this result via two core technical contributions which may be of independent interest. First, we introduce a novel "gluing" mechanism to achieve adaptive security by intertwining two schemes, each possessing one aspect of adaptive security. Second, we enhance the powerful Koppula-Lewko-Waters [STOC 2015] framework with a "sliding window" technique, enabling authenticated iterative computation with fresh inputs at each iteration. Prior work by Guan, Korb, and Sahai [CRYPTO 2023] constructed sFE but only under a (semi-adaptive) function-selective security model, requiring all functional keys to be queried before observing any ciphertext. This severe limitation precludes practical scenarios and leaves adaptive security as a crucial open challenge — explicitly highlighted by their work — which we address in this paper.

Zero-knowledge virtual machines (zkVMs) rely on tabular constraint systems whose verification semantics include gate, lookup, and permutation relations, making correctness auditing substantially more challenging than in arithmetic-circuit DSLs such as Circom. In practice, ensuring that witness-generation code is consistent with these constraints has become a major source of subtle and hard-to-detect bugs. To address this problem, we introduce a high-level semantic model for tabular constraint systems that provides a uniform, circuit-irrelevant interpretation of row-wise constraints and their logical interactions. This abstraction enables an inductive, row-indexed reasoning principle that checks consistency without expanding the full circuit, significantly improving scalability. We implement this methodology in ZIVER and show that it faithfully captures real zkVM designs and automatically validates the consistency of diverse SP1 chip components.

Hash-based signature schemes offer a promising post-quantum alternative for Bitcoin, as their security relies solely on hash function assumptions similar to those already underpinning Bitcoin's design. We provide a comprehensive overview of these schemes, from basic primitives to SPHINCS+ and its variants, and investigate parameter selection tailored to Bitcoin's specific requirements. By applying recent optimizations such as SPHINCS+C, TL-WOTS-TW, and PORS+FP, and by reducing the allowed number of signatures per public key, we achieve significant size improvements over the standardized SPHINCS+ (SLH-DSA).We provide public scripts for reproducibility and discuss limitations regarding key derivation, multi-signatures, and threshold signatures.

Broadcast, though often used as a black box in cryptographic protocols, is expensive to realize in terms of rounds and communication complexity. We investigate the minimal use of broadcast in round-optimal information-theoretic MPC, with statistical security. For information-theoretic MPC with guaranteed output delivery, four rounds of communication are necessary and sufficient (Applebaum, Kachlon and Patra, FOCS 2020; Applebaum, Kachlon and Patra, STOC 2023). We show that broadcast is unavoidable in the second and third rounds of statistical MPC protocols. To complement our lower bounds, we modify the protocol of Applebaum, Kachlon and Patra (STOC 2023) to make use of broadcast only in the second and third round. Along the way, we show that the sharing phase of any three-round information-theoretic VSS protocol must also make use of broadcast in the second and third rounds.

In this work, we analyze the mathematical aspect of the MAYO signature scheme. Following the specification of MAYO, we generate the keys where the secret key is a matrix and the public key is a system of quadratic polynomial of multiple variables; then use them to sign. During the signing procedure, we disprove the claim that the polynomial only has a constant part and a linear part after sampling values for the vinegar variables. Technically, we provide the mathematical expression of an arbitrarily polynomial of the system after substitution and discover that in addition of having a constant part and a linear part, the polynomial also has a quadratic part. The quadratic state of the polynomials after substitution allows us to conclude that signing fails with the third attempt of MAYO.

We study a new variant of the $k$-sum problem. In the classical formulation, one is given $k$ lists of binary vectors and must find one vector from each list such that their sum is the zero vector. In our variant, vectors are instead chosen from the set $\{-1,1\}^m$. First, we analyse how the complexity of the original problem changes when one use $\pm 1$ vectors. We show that this variant achieves better than square-root complexity when using more than two lists, although its overall complexity for $k \geq 4$ is worse than that for the binary case. As an application of our algorithms, we present a combinatorial attack strategy for a recently proposed variant of the Inhomogeneous Short Integer Solution (ISIS) problem known as the randomised one-more ISIS assumption. Our combinatorial attack is more effective than previous combinatorial attacks on this problem. We further consider a generalised setting of the $k$-sum problem in which the target sum is not the zero vector, but a given integer vector $Y \in \mathbb{Z}_p^m$ that is known to be a sum of $\pm 1$ vectors. We study the complexity of reconstructing such a decomposition of $Y$ using $k$ lists of candidate vectors. Our analysis shows that, as the number of lists increases, the problem becomes solvable in approximately cube-root time.

The hardness of finding isogenies of degree $d$ between supersingular elliptic curves is a fundamental assumption in isogeny-based cryptography. Let $E_1$ and $E_2$ be supersingular elliptic curves defined over $\mathbb{F}_{p^2}$, and let $d$ be a smooth integer. %removed > p^{1/2} part. At CRYPTO~2024, Benčina et al.\ proposed an algorithm with time complexity $\widetilde{O}(\max\{p^{1/2}, d/p^{5/8}\})$ in the classical setting and $\widetilde{O}(\max\{p^{1/4}, d^{1/2}/p^{1/4}\})$ in the quantum setting. In this work, we first observe that their analysis omits a sub-exponential factor $\exp(O(\log^{3/4} p))$. We then improve their result to $\widetilde{O}(\max\{p^{1/2}, \exp(O(\log^{4/5} p)) \cdot d/p^{2/3}\})$ classically and $\widetilde{O}(\max\{p^{1/4}, \exp(O(\log^{4/5} p)) \cdot d^{1/2}/p^{1/3}\})$ quantumly. Our approach relies on small-root bounds for Coppersmith’s method applied to a four-variable integer equation. To this end, we adapt the explicit asymptotic formulas for small-root bounds introduced by Feng et al.\ (CRYPTO~2025) in the modular setting to the integer setting. As an additional application, we strengthen the attack of Benčina et al.\ on the SIDH signature scheme by Basso et al. (ACNS~2024). We expect that these refined techniques for Coppersmith’s method will be valuable for further post-quantum cryptanalysis.

We establish the following theorem: Let $\mathsf{O}_0, \mathsf{O}_1, \mathsf{R}$ be random functions from $\{0,1\}^n$ to $\{0,1\}^n$, $n \in \mathbb{N}$. For all polynomial-query-bounded distinguishers $\mathsf{D}$ making at most $q=\mathsf{poly}(n)$ queries to each oracle, there exists a poly-time oracle simulator $\mathsf{Sim}^{(\cdot)}$ and a constant $c>0$ such that the probability is negligible, that is $$\left|\Pr\left[{\mathsf{D}^{(\mathsf{O}_0+\mathsf{O}_1),(\mathsf{O}_0,\mathsf{O}_1,\mathsf{O}_0^{-1},\mathsf{O}_1^{-1})}(1^n)=1}\right]-\Pr\left[{\mathsf{D}^{\mathsf{R},\mathsf{Sim}^\mathsf{R}}(1^n)=1}\right]\right| = negl(n).$$

An oblivious pseudorandom function (OPRF) is an interactive protocol between a client and server, where the client aims to evaluate a keyed pseudorandom function for a key held by the server, without revealing its input. OPRFs are a versatile tool for enhancing privacy, inciting extensive research and standardization efforts in this area. The round-efficient 2Hash-Diffie-Hellman OPRF is widely deployed, but unfortunately, it is prone to quantum attacks. The search for post-quantum alternatives started in 2019 and is currently more disputed, with several candidates on the table. Given the lack of test of time of post-quantum OPRFs and their underlying cryptographic assumptions, hybridization can help mitigate risks in this interim period. Most preferably, we want to combine existing classical deployments like 2HashDH with post-quantum candidates. However, analogous two-party settings like oblivious transfer, where both parties have security requirements, indicate that combining OPRFs might be trickier than it is for hashing or encryption. In this paper, we give combiners for OPRFs with minimal overhead over the combined schemes. We also formally prove that "ideal'' combiners, i.e., ones that do not make additional assumptions on how an underlying OPRF may break, cannot exist. Our constructions avoid this theoretical result by assuming the underlying OPRFs to satisfy certain statistical guarantees. Crucially, these extra conditions are satisfied by both the 2Hash-Diffie-Hellman OPRF and the currently most efficient post-quantum candidates, rendering our results suitable for upgrading existing deployments with quantum-safe guarantees already today.

Secure multiparty computation (MPC) is perhaps the most popularparadigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case ofunconditional (information-theoretic) security, protocols are known which tolerate a dishonest minorityof players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource and seek to minimize the number of rounds in which it is invoked. 1. We construct an MPC protocol which uses the broadcast channel only three times in a preprocessing phase, after which it is never required again. Ours is the first unconditionally secure MPC protocol for $t < n/2$ to achieve such a low number of broadcast rounds. In contrast, combining the best previous techniques yields a protocol with twenty four broadcast rounds. 2. In the negative direction, we show a lower bound of two broadcast rounds for the specific functionality of Weak Secret Sharing (a.k.a. Distributed Commitment), also a very natural functionality and central building block of many MPC protocols. The broadcast-efficient MPC protocol relies on new constructions of Pseudosignatures and Verifiable Secret Sharing, both of which might be of independent interest.

Wave is a code-based digital signature scheme. Its hardness relies on the unforgeability of the signature and the indistinguishability of its public key, a parity check matrix of a ternary $(U, U+V)$-code. The best known attacks involve solving the Decoding Problem using the Information Set Decoding algorithm (ISD) to defeat these two problems. Our main contribution is the description of a quantum smoothed Wagner’s algorithm within the ISD framework, which improves the forgery attack on Wave in the quantum setting. We also recap the best known key and forgery attacks against Wave in both classical and quantum settings. For each one, we express their time complexity as function of Wave parameters and deduce its claimed security.

Supersingular elliptic curve isogeny graphs underlie isogeny-based cryptography. For isogenies of a single prime degree $\ell$, their structure has been investigated graph-theoretically. We generalise the notion of $\ell$-isogeny graphs to $L$-isogeny graphs (studied in the prime field case by Delfs and Galbraith), where $L$ is a set of small primes dictating the allowed isogeny degrees in the graph. We analyse the graph-theoretic structure of $L$-isogeny graphs. Our approaches may be put into two categories: cycles and graph cuts. On the topic of cycles, we provide: a count for the number of cycles in the $L$-isogeny graph with cyclic kernels using traces of Brandt matrices; an efficiently computable estimate based on this approach; and a third ideal-theoretic count for a certain subclass of $L$-isogeny cycles. We provide code to compute each of these three counts. On the topic of graph cuts, we compare several algorithms to compute graph cuts which minimise a measure called the edge expansion, outlining a cryptographic motivation for doing so. Our results show that a greedy neighbour algorithm out-performs standard spectral algorithms for computing optimal graph cuts. We provide code and study explicit examples. Furthermore, we describe several directions of active and future research.

Private Information Retreival (PIR) schemes without preprocessing are known to incur linear server computation per client query. Several recent works have shown that by relying on a one-time preprocessing phase, we can get around this barrier, and achieve sublinear computation per query without relying on any cryptographic assumptions. Beimel et al. (CRYPTO'00) first showed a family of schemes whose bandwidth and computation per query scale as fast as $n^{O(1/S)}$ where $S$ denotes the number of servers and $n$ denotes the database size. Unfortunately, their schemes are not practical partly because the servers must each store an encoded version of the database, and the encoding length grows sharply as we increase $S$. The recent work of Singh et al. (TCC'24) showed how to achieve similar bandwidth scaling but without the server space blowup. To get this, they rely on a different type of preprocessing called client-specific preprocessing, where the stateful client stores some hints and the servers store only the original database. Unfortunately, Singh et al.'s result is completely impractical due to the reliance on Dvir and Gopi's PIR as a building block. We propose Zelda (short for ZEro-Leakage Data Access), the first concretely efficient, information-theoretic multi-server PIR scheme with sublinear computation. Our work makes both theoretical and practical contributions. On the theoretical front, we devise a unified framework for constructing multi-server PIR with client-specific preprocessing. This gives us a parametrizable family of schemes that asymptotically outperform all prior constructions in the same setting, including Singh et al. (TCC'24) and Ishai et al. (CRYPTO'24). On the practical front, Zelda is conceptually simple, self-contained, and does not rely on any underlying PIR as a building block. We implemented Zelda and open sourced our code. We compared the concrete performance of Zelda with a state-of-the-art PIR scheme called QuarterPIR (Eurocrypt'24), which relies on pseudorandom functions for security. Experimental results show that Zelda outperforms QuarterPIR in terms of online response time and client space (assuming typical fiber optical links), at the price of increased costs for offline maintenance operations.

Privacy-preserving decision tree inference is a fundamental primitive in privacy-critical applications such as healthcare and finance, yet existing protocols rely heavily on secure selection, which accounts for more than half of the total cost. We introduce a new paradigm that eliminates this limitation by replacing multiple secure selections with a single permutation, whose cost is comparable to that of a single secure selection. Our scheme significantly reduces both computation and communication overhead compared to SOTA. Comprehensive benchmarks show an 86 % reduction in model evaluation versus the state-of-the-art FSS protocol by Ji et al., and a 99.9 % reduction versus the OT-based protocol of Ma et al. Overall, our benchmark shows that our protocol achieves a performance improvement of 20 tiems over Ma et al.’s scheme and 4.5 times over Ji et al.’s scheme.

The threshold secret sharing scheme enables a dealer to distribute the share to every participant such that the secret is correctly recovered from a certain amount of shares. The traditional $(k, n)$ threshold secret sharing scheme requires that the number of participants $n$ is known in advance. In contrast, the evolving secret sharing scheme allows that $n$ can be uncertain and even ever-growing. In this paper, we consider the evolving secret sharing scenario. Based on the prefix codes, we propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $\ell$-bit secret over a polynomial ring, with correctness and perfect security. The proposed scheme is the first evolving $k$-threshold secret sharing scheme by generalizing Shamir's scheme onto a polynomial ring. Besides, the proposed scheme also establishes the connection between prefix codes and the evolving schemes for $k\geq2$. The analysis shows that the size of the $t$-th share is $(k-1)(\ell_t-1)+\ell$ bits, where $\ell_t$ denotes the length of a binary prefix code of encoding integer $t$. In particular, when $\delta$ code is chosen as the prefix code, the share size is $(k-1)\lfloor\lg t\rfloor+2(k-1)\lfloor\lg ({\lfloor\lg t\rfloor+1}) \rfloor+\ell$, which improves the prior best result $(k-1)\lg t+6k^4\ell\lg{\lg t}\cdot\lg{\lg {\lg t}}+ 7k^4\ell\lg k$, where $\lg$ denotes the binary logarithm. Specifically, when $k=2$, the proposal also provides a unified mathematical decryption for prior evolving $2$-threshold secret sharing schemes and also achieves the minimal share size for a single-bit secret, which is the same as the best-known scheme.

Most adaptively secure identity-based encryption (IBE) constructions from lattices in the standard model follow the framework proposed by Agrawal et al. (EUROCRYPT 2010). However, this framework has an inherent restriction: the modulus is quadratic in the trapdoor norm. This leads to an unnecessarily large modulus, reducing the efficiency of the IBE scheme. In this paper, we propose a novel framework for adaptively secure lattice-based IBE in the standard model, that removes this quadratic restriction of modulus while keeping the dimensions of the master public key, secret keys, and ciphertexts unchanged. More specifically, our key observation is that the original framework has a \textit{natural} cross-multiplication structure of trapdoor. Building on this observation, we design two novel algorithms with non-spherical Gaussian outputs that fully utilize this structure and thus remove the restriction. Furthermore, we apply our framework to various IBE schemes with different partitioning functions in both integer and ring settings, demonstrating its significant improvements and broad applicability. Besides, compared to a concurrent work by Ji et al. (PKC 2025), our framework is significantly simpler in design, and enjoys a smaller modulus, a more compact master public key and shorter ciphertexts.

Cross-chain bridges have emerged as key components of blockchain infrastructure, enabling digital assets to flow across chains and benefit from non-native features. While early bridge designs were fraught with brittle trust assumptions, more recent designs, even within Bitcoin's script limits, can operate in a trust-minimized setting. Given this ever-increasing expansion of blockchain bridge systems, a critical question regarding custody arises: When a user's coins cross a bridge back and forth, is there a possibility that they are substituted with other coins upon return? Naturally, if cryptocurrencies were truly fungible, this would not be a consequential event. Nevertheless, chain analytics algorithms as applied to Bitcoin, Ethereum, and other popular chains can trace coins' provenance up to their minting event, thereby highlighting the possibility that users may end up with "tainted" coins upon receiving their coins from a peg-out bridge operation. Similarly, this also highlights the possibility that bridges could become an attraction for money laundering. To address these considerations, we put forward the concept of ownership preservation for blockchain bridges and we observe that existing multi-sig and BitVM bridges fail to satisfy it. We then present a novel BitVM-based bridge that enables Bitcoin to connect bidirectionally with another DeFi supporting chain in an ownership-preserving and trust-minimized manner. We also observe that our ownership-preserving design is the first Bitcoin bridge to facilitate the transfer of Bitcoin NFTs, Ordinals, across chains, extending in this way their potential value and use cases.

Simulation is a fundamental technique in cryptography, central to security proofs, probably most well-known is its use for showing zero-knowledge. In this paper, we consider simulations no longer being merely a proof technique, but to constructively use simulators of non-interactive zero-knowledge proofs (NIZKs) as an integral component of cryptographic designs. We have occasionally seen such a use, e.g., in designated verifier signatures (DVS), deniable encryption, or the recent concept of anamorphic encryption. However, it was never explicity explored as a stand-alone concept, which is the goal of this paper. By embedding simulated proofs directly into concrete systems, we unlock cryptographic functionalities that were previously out of reach under standard assumptions or required prohibitively complex techniques. In other words, by incorporating simulated proofs into the ``real'' world, rather than the simulated one, we achieve conceptually more elegant primitives. As a primer, we construct a secure signature scheme whose security hinges on a simulated proof of a false statement, i.e., the ludicrous statement $1 = 2$. To illustrate the broader potential of this approach, we present new and simple constructions of chameleon hash functions with strong privacy guarantees (e.g., full indistinguishability), that do not require a trusted setup. Additionally, we present a very simple DVS with tight security proofs and a strengthened notion of non-transferability. Based on the zero-knowledge guarantees of the underlying NIZKs, the resulting constructions achieve privacy even if the adversary is allowed to choose the random coins to set up the cryptographic material. To model this, we introduce the notion of trapdoor-detectable zero-knowledge, which may be of independent interest.

Verifying the security of masked hardware and software implementations, under advanced leakage models, remains a significant challenge, especially when accounting for glitches, transitions and CPU micro-architectural specifics. Existing verification approaches are either restricted to small hardware gadgets, small programs on CPUs such as Sboxes, limited leakage models, or require hardware-specific prior knowledge. In this work, we present aLEAKator, an open-source framework for the automated formal verification of masked cryptographic accelerators and software running on CPUs from their HDL descriptions. Our method introduces mixed-domain simulation, enabling precise modeling and verification under various (including robust and relaxed) 1-probing leakage models, and supports variable signal granularity without being restricted to 1-bit wires. aLEAKator also supports verification in the presence of lookup tables, and does not require prior knowledge of the target CPU architecture. Our approach is validated against existing tools and real-world measurements while providing innovative results such as the verification of a full, first-order masked AES on various CPUs.

Single Secret Leader Election (SSLE) protocol facilitates the election of a single leader per round among a group of registered nodes while ensuring unpredictability. Ethereum has identified SSLE as an essential component in its development roadmap and has adopted it as a potential solution to counteract potential attacks. However, we identify a new form of attack termed the state uniqueness attack that is caused by malicious leaders proposing multiple publicly verifiable states. This attack undermines the property of uniqueness in subsequent leader elections and, with high probability, leads to violations of fundamental security properties of the over-layer protocol such as liveness. The vulnerability stems inherently from the designs reducing the uniqueness guarantee to a unique state per election, and can be generalized to the existing SSLE constructions. We further quantify the severity of this attack based on theoretical analysis and real-world executions on Ethereum, highlighting the critical challenges in designing provably secure SSLE protocols. To address the state uniqueness attack while ensuring both security and practical performance, we present a universal SSLE protocol called Mobius that does not rely on extra trust assumptions. Specifically, Mobius prevents the generation of multiple verifiable states for each election and achieves a unique state across consecutive executions through an innovative approximately-unique randomization mechanism. In addition to providing a comprehensive security analysis in the Universal Composability framework, we develop a proof-of-concept implementation of Mobius, and conduct extensive experiments to evaluate the security and overhead. The experimental results show that Mobius exhibits enhanced security while significantly reducing communication complexity throughout the protocol execution, achieving over 80% reduction in the registration phase.

Polynomial secret sharing schemes generalize the linear ones by adding more expressivity and giving room for efficiency improvements. In these schemes, the secret is an element of a finite field, and the shares are obtained by evaluating polynomials on the secret and some random field elements, i.e., for every party there is a set of polynomials that computes the share of the party. Notably, for general access structures, the best known polynomial schemes have better share size than the best known linear ones. This work investigates the properties of the polynomials and the fields that allow these efficiency gains and aims to characterize the access structures that benefit from them. We focus first on ideal schemes, which are optimal in the sense that the size of each share is the size of the secret. We prove that, under some restrictions, if the degrees of the sharing polynomials are not too big compared to the size of the field, then its access structure is a port of an algebraic matroid. This result establishes a new connection between ideal schemes and matroids, extending the known connection between ideal linear schemes and linearly representable matroids. For general polynomial schemes, we extend these results and analyze their privacy and correctness. Additionally, we show that given a set of polynomials over a field of large characteristic, one can construct linear schemes that realize the access structure determined by these polynomials; as a consequence, polynomial secret sharing schemes over these fields are not stronger than linear schemes. While there exist ports of algebraic matroids that do not admit ideal schemes, we demonstrate that they always admit schemes with statistical security and information ratio tending to one. This is achieved by considering schemes where the sharings are points in algebraic varieties.

Secure two-party computation (2PC)-based privacy-preserving machine learning (ML) has made remarkable progress in recent years. However, most existing works overlook the privacy challenges that arise during the data preprocessing stage. Although some recent studies have introduced efficient techniques for privacy-preserving feature selection and data alignment on well-structured datasets, they still fail to address the privacy risks involved in transforming raw data features into ML-effective numerical representations. In this work, we present ALIOTH, an efficient 2PC framework that securely transforms raw categorical and numerical features into Weight-of-Evidence (WoE)-based numerical representations under both vertical and horizontal data partitions. By incorporating our proposed partition-aware 2PC protocols and vectorization optimizations, ALIOTH efficiently generates WoE-transformed datasets in secret. To demonstrate scalability, we conduct experiments on diverse datasets. Notably, ALIOTH can transform 3 million data samples with 100 features securely within half an hour over a wide-area network. Furthermore, ALIOTH can be seamlessly integrated with existing 2PC-based ML frameworks. Empirical evaluations on real-world financial datasets show ALIOTH improves both the predictive performance of logistic regression and 2PC training efficiency.

Encrypted messaging systems provide end-to-end security for users but obstruct content moderation, making it difficult to combat online abuses. Traceability offers a promising solution by enabling platforms to identify the originator/spreader of messages, yet this capability can be abused for mass surveillance of innocent messages. To mitigate this risk, existing approaches restrict traceability to (problematic) messages that are reported by multiple users or are on a predefined blocklist. However, these solutions either overtrust a specific entity (e.g., the party defining the blocklist) or rely on the unrealistic assumption of non-collusion between servers run by a single platform. In this paper, we propose an abuse-resistant source tracing scheme that distributes traceability across distinct real-world entities. Specifically, we formally define its syntax and prove its security properties. Our scheme realizes two essential principles: minimal trust, which ensures that traceability cannot be abused as long as a single participant involved in tracing is honest, even if all others collude; and minimal information disclosure, which prevents participants from acquiring any information (e.g., communication parties' identities) unnecessary for tracing. We implemented our scheme using techniques deployed by Signal, and our evaluation shows it offers comparable performance to state-of-the-art schemes that are vulnerable to abuse.

We present fully adaptive secure threshold IBE and threshold signatures, which rely on the $k$-Linear assumption in the standard model over asymmetric pairing groups. In particular, our threshold signature scheme achieves a non-interactive signing process and an adaptively secure guarantee as strong as Das-Ren (CRYPTO'24), while their proof relies on the random oracle model. We achieve our results by following steps: First, we design two threshold IBE schemes against adaptive corruptions in the composite-order and prime-order groups by adopting the dual system groups encoding. Second, we provide a generic transform from threshold IBE to threshold signatures, following Naor's paradigm, which reduces the fully adaptive corruption security of threshold signatures to threshold IBE. Third, we present two threshold signatures instantiations in composite-order and prime-order groups.

We introduce audience injection attacks, a novel class of vulnerabilities that impact widely used Web-based authentication and authorization protocols, including OAuth 2.0, OpenID Connect, FAPI, CIBA, the Device Authorization Grant, and various well-established extensions, such as Pushed Authorization Requests, Token Revocation, Token Introspection, and their numerous combinations. These protocols underpin services for billions of users across diverse ecosystems worldwide, spanning low-risk applications like social logins to high-risk domains such as open banking, insurance, and healthcare. Audience injection attacks exploit a critical weakness in a core security mechanism of these protocols - the handling of so-called audiences in signature-based client authentication mechanisms. This vulnerability allows attackers to compromise fundamental security objectives whenever these mechanisms are utilized across two or more server endpoints. They enable the attacker to impersonate users and gain unauthorized access to their resources, even in high-security protocol families specifically designed for sensitive applications. We responsibly disclosed these vulnerabilities to the relevant standardization bodies, which recognized their severity. In collaboration with these organizations, we developed fixes and supported a coordinated response, leading to an ongoing effort to update a dozen of standards, numerous major implementations, and far-reaching ecosystems.

We revisit the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, $\KpolyA$---that is, determining whether a string is ``structured" (i.e., $K^t(x) < n-1$) or ``random" (i.e., $K^{\poly(t)} \geq n-1$)---suffices to imply the existence of one-way functions (OWF). Liu-Pass (CRYPTO'25) recently showed that worst-case hardness of a \emph{boundary} version of $\KpolyA$---where, roughly speaking, the goal is to decide whether given an instance $x$, (a) $x$ is $K^\poly$-random (i.e., $K^{\poly(t)}(x) \geq n-1$), or just close to $K^\poly$-random (i.e., $K^{t}(x) < n-1$ \emph{but} $K^{\poly(t)}> n - \log n$)---characterizes OWF, but with either of the following caveats (1) considering a non-standard notion of \emph{probabilistic $K^t$}, as opposed to the standard notion of $K^t$, or (2) assuming somewhat strong, and non-standard, derandomization assumptions. In this paper, we present an alternative method for establishing their result which enables significantly weakening the caveats. First, we show that boundary hardness of the more standard \emph{randomized} $K^t$ problem suffices (where randomized $K^t(x)$ is defined just like $K^t(x)$ except that the program generating the string $x$ may be randomized). As a consequence of this result, we can provide a characterization also in terms of just ``plain" $K^t$ under the most standard derandomization assumption (used to derandomize just $\BPP$ into $\P$)---namely $\E \not\subseteq {\sf ioSIZE}[2^{o(n)}]$. Our proof relies on language compression schemes of Goldberg-Sipser (STOC'85); using the same technique, we also present the the first worst-case to average-case reduction for the \emph{exact} $\KpolyA$ problem (under the same standard derandomization assumption), improving upon Hirahara's celebrated results (STOC'18, STOC'21) that only applied to a \emph{gap} version of the $\KpolyA$ problem, referred to as $\GapKpolyA$, where the goal is to decide whether $K^t(x) \leq n-O(\log n))$ or $K^{\poly(t)}(x) \geq n-1$ and under the same derandomization assumption.

The threat of practical quantum attacks has catapulted viable alternatives like Post-Quantum Cryptography (PQC) into prominence. The adoption and integration of standardized PQC primitives across the entire digital stack are promoted by various standardization bodies, governments, and major corporate houses. A serious challenge in quantum migration is to ensure that there is no hidden backdoor in the PQC implementations of a hybrid cryptosystem (support for both pre-quantum and post-quantum algorithms), which are often procured from a third-party vendor. In this manuscript, we investigate the possibility of a kleptographic backdoor on the NIST-recommended key-encapsulation mechanism CRYSTALS-Kyber. The modified Kyber key-generation algorithm achieves indistinguishable decryption failure probability compared to the original CRYSTALS-Kyber. The kleptographic module is also implemented in FPGA, embedded inside the CRYSTALS- Kyber accelerator with a very low area overhead (283 LUTs or 2% of total area), and thus can easily pass performance and functionality tests.