International Association
for Cryptologic Research

Implantable Medical Devices (IMDs) operate for many years in an ecosystem where device loss, backend compromise, and physical capture are realistic long-term threats. While prior work has extensively studied secure pairing and access control, existing IMD architectures typically rely on long-lived secrets. As a result, the compromise of a single credential can retroactively expose years of sensitive patient telemetry. Limiting such damage requires Perfect Forward Secrecy (PFS), yet achieving PFS in IMDs is challenging due to strict energy constraints, intermittent connectivity, and safety requirements. Public-key cryptography is often too costly for frequent use on implants and physical-layer defences rely on fragile assumptions In this work, we present a symmetric-only communication protocol that provides forward secrecy for IMDs while remaining robust to device loss and state desynchronisation. The protocol evolves cryptographic state across sessions using lightweight primitives on the implant, ensuring that past communications remain confidential even if the IMD or associated client devices are compromised later. To address the safety risks of desynchronisation, we introduce a threshold-assisted recovery mechanism that enables secure resynchronisation via a distributed backend without trusting any single client or server. The design preserves patient-centric control and supports controlled emergency access without undermining long-term confidentiality. We formally analyse the protocol using ProVerif and demonstrate feasibility through implementations on a 16-bit MSP430 and a 32-bit ARM Cortex-M33 microcontroller.

Many important applications of fully homomorphic encryption (FHE) require *high-precision* arithmetic, e.g., plaintext rings $\mathbb{Z}_p$ for a huge prime or power-of-two modulus $p$. The classic FHE schemes are poorly suited to this, because the inverse error rate of fresh ciphertexts, and the error growth under homomorphic multiplication, are both larger than $p$, which results in large and inefficient parameters. While there are now several works addressing this problem, the landscape for *exact* (as opposed to approximate) FHE is highly fragmented: known solutions either work only for certain rare plaintext moduli having very special forms (sometimes using non-standard ciphertext rings that lack other important features for FHE), or have quite complicated and high-latency constructions.

This work gives a very simple and general technique for high-precision exact FHE, in which the error rates and growth match those of prior schemes with *exponentially smaller* precision, and which has good practical efficiency. In contrast to all prior works, our scheme works for *any integer modulus*, and also over *any underlying (number) ring*---or even with no structured ring at all, making it the first solution that can be based on plain LWE. It is also *fully compatible with prior FHE techniques* for fast ring arithmetic, plaintext packing and SIMD operations, bootstrapping, etc. For plaintext ring $\mathbb{Z}_{2^{64}}$, our (preliminary, unoptimized, single-threaded) implementation does homomorphic multiplication in just tens of milliseconds, and supports a two- to three-fold increase in multiplicative depth versus classic FHE schemes at typical security levels.

This paper investigates the multiplicative properties of linear codes in secret sharing schemes. To address the limitation that certain access structures cannot be realized by ideal linear codes, we introduce the notion of shortest linear codes as an ideal benchmark for code length. Since explicitly determining such shortest codes is generally computationally difficult, we propose an explicit construction that, for any given access structure, produces a length-efficient linear code whose induced the access structure. On this basis, we further define multiplicative ideal linear codes and multiplicative length-efficient linear codes, and derive necessary and sufficient conditions for the existence of multiplicativity. The effectiveness of the proposed approach is demonstrated by concrete examples. Compared with the construction of Cramer et al., the multiplicative linear codes obtained in this work have smaller length.

A one-time memory (OTM) is a useful cryptographic primitive, classically modeled after a non-interactive oblivious transfer. It is well known that secure OTMs (and more generally one-time deterministic programs) cannot exist in the standard model in either the classical or quantum setting due to Broadbent et al. (CRYPTO'13). Broadbent et al.\ circumvented this impossibility by assuming the existence of hardware tokens that cannot be queried in superposition. In this work, we take a different approach. Building on Liu's assumption (ITCS'23) that adversaries are limited to depth-bounded quantum circuits, we present two OTM constructions. The first is efficiently realizable and secure against adversaries restricted to constant-depth quantum circuits. The second is a feasibility result that achieves security against adversaries limited to $\mathcal{O}(\lambda^\gamma)$-depth quantum circuits by ensuring that a successful attack would necessarily require deeper quantum computations, where $\lambda^\gamma$ is a polynomial in the security parameter $\lambda$. Our results therefore extend prior work, which either relied on hardware assumptions or considered only constant-depth-bounded adversaries. As a result, by combining our proposed quantum OTMs with the framework of Broadbent et al. (CRYPTO'13), one can also realize quantum one-time programs (OTPs) for deterministic programs.

A promising direction for enabling private queries to large language models (LLMs) is with homomorphic encryption (HE). An open problem is performing token sampling under HE. In this paper, we introduce Hyperion, an efficient HE algorithm for inverse transform sampling, enabling private token sampling with 1 comparison depth, $O(1)$ amortized comparisons, and $O(\log n)$ rotations. We implement our approach and demonstrate that it samples tokens in 0.14 seconds for 32k tokens ($\approx 4.4\, \mu\mathrm{s}$ per token) on GPU, achieving a $100\times$ latency improvement over prior work.

Anonymous messaging systems, such as privacy-preserving blockchains and private messaging applications, need to protect recipient privacy: ensuring no linkage between the recipient and the message. This raises the question: how can untrusted servers assist in delivering the pertinent messages to each recipient, without requiring the recipient to linearly scan all messages or revealing the intended recipient of each message? Oblivious message retrieval (OMR), a recently proposed primitive, addresses this issue by using homomorphic encryption in the single-server setting.

This work introduces $\mathsf{InstantOMR}$, a novel OMR scheme that combines TFHE functional bootstrapping with standard RLWE operations in a hybrid design, achieving significant improvements in both latency and parallelizability compared to prior BFV-based schemes. We propose a two-layer bootstrapping architecture and hybrid use of TFHE and regular RLWE homomorphic operations for $\mathsf{InstantOMR}$. Our implementation, using the $\mathsf{Primus}$-$\mathsf{fhe}$ library (and estimates based on $\mathsf{TFHE}$-$\mathsf{rs}$), demonstrates that $\mathsf{InstantOMR}$ offers the following key advantages:

- Low latency: $\mathsf{InstantOMR}$ achieves ${\sim} 860\times$ lower latency than $\mathsf{SophOMR}$, the state-of-the-art single-server OMR construction. This translates directly into reduced recipient waiting time (by the same factor) in the streaming setting, where the detector processes incoming messages on-the-fly and returns a digest immediately upon the recipient becoming online.

- Optimal parallelizability: $\mathsf{InstantOMR}$ scales near-optimally with available CPU cores (by processing messages independently), so for high core counts, it is faster than SophOMR (whose parallelism is constrained by its reliance on BFV).

In this work, we model the end-to-end pipeline of the advertising ecosystem, allowing us to identify two main issues with the current trajectory of private advertising proposals. First, prior work has largely considered ad targeting and engagement metrics individually rather than in composition. This has resulted in privacy notions that, while reasonable for each protocol in isolation, fail to compose to a natural notion of privacy for the ecosystem as a whole, permitting advertisers to extract new information about the audience of their advertisements. The second issue serves to explain the first: we prove that perfect privacy is impossible for any, even minimally, useful advertising ecosystem, due to the advertisers' expectation of conducting market research on the results.

Having demonstrated that leakage is inherent in advertising, we re-examine what privacy could realistically mean in advertising, building on the well-established notion of sensitive data in a specific context. We identify that fundamentally new approaches are needed when designing privacy-preserving advertising subsystems in order to ensure that the privacy properties of the end-to-end advertising system are well aligned with people's privacy desires.

Yao's famous protocol for secure 2-party computation, based on garbled circuits, is well-known to be insecure against an actively corrupt garbler. We introduce a new and extremely simple variant of Yao's protocol that is fully secure against active adversaries, for a certain class of functions that we call conditionally input-revealing.

We then show how to use this new protocol as the basis for fuzzy password authenticated key exchange (fuzzy PAKE). In fuzzy PAKE, two parties each hold a low-entropy secret (e.g., a password), and they interact to obtain a secure high-entropy key if and only if the passwords are sufficiently ``close.'' Our new fuzzy PAKE protocol supports completely arbitrary predicates for password ``closeness''. Compared to prior fuzzy PAKE protocols, ours is roughly $2\times$ cheaper in communication, computation, and round complexity.

Certified deletion ensures that encrypted data can be irreversibly deleted, preventing future recovery even if decryption keys are later exposed. Although existing works have achieved certified deletion across various cryptographic primitives, they rely on central authorities, leading to inherent escrow vulnerabilities. This raises the question of whether certified deletion can be achieved in decentralized frameworks such as Registered Attribute-Based Encryption (RABE) that combines fine-grained access control with user-controlled key registration. This paper presents the first RABE schemes supporting certified deletion and certified everlasting security. Specifically, we obtain the following:

- We first design a privately verifiable RABE with Certified Deletion (RABE-CD) scheme by combining our newly proposed shadow registered ABE (Shad-RABE) with one-time symmetric key encryption with certified deletion.

- We then construct a publicly verifiable RABE-CD scheme using Shad-RABE, witness encryption, and one-shot signatures, allowing any party to validate deletion certificates without accessing secret keys.

- We also extend to privately verifiable RABE with Certified Everlasting Deletion (RABE-CED) scheme, integrating quantum-secure RABE with the certified everlasting lemma. Once a certificate is produced, message privacy becomes information-theoretic even against unbounded adversaries.

- We finally realize a publicly verifiable RABE-CED scheme by employing digital signatures for the BB84 states, allowing universal verification while ensuring that deletion irreversibly destroys information relevant to decryption.

You Only Speak Once (YOSO) secure Multi-Party Computation (MPC) provides scalability and adaptive security by distributing the computation across a sequence of anonymous committees. This relies on role assignment, which sets up the infrastructure necessary for the members of one committee to send secret messages to members of subsequent committees without knowing their identities. Existing approaches to role assignment suffer from significant limitations: high broadcast complexity, reliance on secure computation (which creates a circular dependency), or the requirement of an overwhelming honest majority among available nodes in order to guarantee output delivery in the MPC.

In this work, we introduce Nested YOSO MPC, which overcomes all of these drawbacks by departing from the traditional threshold adversary structure. We design our MPC to run over a sequence of size-$m^2$ committees, each composed of $m$ subcommittees of size $m$. This MPC is secure (with guaranteed output delivery) as long as most subcommittees on each committee have an honest majority. Our efficient, setup-free role assignment protocol guarantees an honest majority on most subcommittees as long as $(\frac{1}{2} + \epsilon)N$ of the available participants are honest, where $\epsilon$ is a constant and $N$ is the total number of available participants.

As a complementary contribution, we prove that no MPC with polylogarithmic (in $N$) broadcast complexity can rely on $\frac{N}{2} + o(\frac{N}{polylog(N)})$ honest parties, indicating that our construction is near-optimal in terms of the number of corruptions it can tolerate.

Anamorphic signatures (Kutylowski {\it et al.}, Crypto'23) provide a way to covertly use encryption by hiding ciphertexts inside digital signatures without a dictator noticing. Recently (Asiacrypt'24), Jaeger and Stracovsky advocated stronger security notions for the primitive. Their notion of dictator unforgeability requires a dictator's inability to produce fresh signatures that decrypt to a meaningful covert message. The notion of recipient unforgeability requires that anamorphic receivers cannot forge signatures even after having observed anamorphic signatures on messages of their choice. To date, the known schemes satisfying all these properties simultaneously rely on the "randomness replacement" technique. As a result, they are restricted to short anamorphic messages either because their anamorphic decryption mechanism involves an exhaustive search step, or because they embed the anamorphic plaintext in a public random salt (which is typically short in compatible signature schemes like RSA-PSS). In this paper, we present anamorphic signatures that depart from the randomness replacement paradigm and make it possible to encrypt longer anamorphic plaintexts. We show that (generalized) Okamoto-Schnorr signatures, as well as GQ and $2^t$-root signatures all have anamorphic modes satisfying the three desired security properties. The ratio between the lengths of anamorphic plaintexts and signatures can even be very close to $1$ for appropriate parameters. We also discuss an extension to Lyubashevsky's lattice-based signatures.

NTRU-based bootstrapping is a high-performance variant of FHEW-like bootstrapping schemes. Its main computational bottleneck lies in the blind rotation step, which involves numerous external products. In this work, we propose multiple techniques to reduce the number of these costly operations, including the use of block binary keys, block ternary keys, and the integration of block keys with the key unrolling method. Specifically, our approach reduces the number of external products to $n/\ell$ for block keys $\mathbf{B}_{k,\ell}$ ($\mathbf{T}_{k,\ell}$), compared to $n$ in FINAL (ASIACRYPT 2021) and $n/2$ in the key unrolling approach (CHES 2024). When combining block keys with key unrolling, the number can further be reduced to $n/2\ell$ .

We implemented our algorithms using the CHIFHE library. Under 128-bit security settings, using block binary keys $\mathbf{B}_{k,\ell}$ ($\ell=4$), block ternary keys $\mathbf{T}_{k,\ell}$ ($\ell=4$) and key unrolling on $\mathbf{B}_{n/2,2}$ achieve a speedup of $1.12\times$ over the key unrolling method (CHES 2024) and $1.73\times$ over FINAL (ASIACRYPT 2021). Notably, the last $2$ algorithms increase memory usage by less than 15MB compared to the key unrolling method (CHES 2024).

With the rapid development of quantum computing, traditional public-key cryptosystems are increasingly vulnerable, making post-quantum cryptography (PQC) a critical area for securing future information systems. As a prominent code-based key encapsulation mechanism (KEM), Classic McEliece offers strong quantum security. However, its large public key size and complex decoding process introduce significant performance bottlenecks, hindering its practical deployment on mobile and edge devices. To address these challenges, we propose RACE (Rapid ARM Cryptographic Engine), a systematic acceleration framework tailored for ARMv8 architectures, designed to enhance the efficiency of Classic McEliece while preserving its constant-time security guarantees. In the key generation phase, we introduce an implicit data layout and in-place transformation strategy based on LUP decomposition, coupled with NEON SIMD vectorization. For the encapsulation phase, we optimize error vector generation with constant-time techniques and batch-loading strategies to reduce memory access redundancy during matrix-vector multiplications. In the decapsulation phase, we apply lane-level fusion and dual-lane butterfly fusion techniques, leveraging NEON instructions to parallelize field multiplication and fast fourier transform (FFT) butterfly operations. Experiments on three ARMv8 platforms (Kunpeng 920, Apple M1, Apple M2 Pro) demonstrate significant speedups of RACE compared to the official vec implementation. For the McEliece8192128 parameter set, key generation is accelerated by 1.33$\times$, 1.90$\times$, and 2.04$\times$, encapsulation by 1.33$\times$, 1.23$\times$, and 1.26$\times$, and decapsulation by 1.27$\times$, 1.68$\times$, and 1.66$\times$, respectively. RACE also outperforms open-source libraries, particularly in decapsulation, where speedups reach several hundred times. These results validate the practical applicability and deployment potential of RACE in mobile and edge computing environments.

The transition of cryptographic primitives to the post-quantum era necessitates the rigorous translation of asymptotic security proofs into concrete parameter instantiations. This paper evaluates the practical realizability of the Decentralized Multi-Authority Attribute-Based Encryption (MA-ABE) scheme by Datta, Komargodski, and Waters (Eurocrypt 2021), a seminal construction relying exclusively on the Learning With Errors (LWE) assumption. While DKW21 eliminates the reliance on bilinear maps, offering resilience against quantum adversaries, our comprehensive numerical audit reveals a profound dichotomy between its theoretical soundness and practical feasibility. We demonstrate that the convergence of constraints derived from LWE hardness and the noise flooding technique required for simulation-based security forces the modulus-to-noise ratio into a super-polynomial regime. Consequently, the requisite parameters---particularly the smudging bound $\hat{B}$---scale astronomically ($\approx 10^{47}$), rendering the scheme unimplementable on existing computational substrates. Beyond identifying this "Parameter Wall," this work proposes a radical architectural reconfiguration to bridge the gap between theory and practice. We introduce novel optimization strategies including the transition to non-commutative Module-LWE structures, the invention of Coset-Restricted Lattice Hashing to minimize pre-image norms, and the adoption of Entropic Smudging via Lossy Trapdoors. Furthermore, we explore Isospectral Lattice Deformations and Learning With Rounding (LWR) transformations to decouple security constraints from decryption correctness, outlining a viable roadmap for practical post-quantum access control.

We study the problem of constructing Boolean garbling schemes that are both succinct$-$with garbled circuit size significantly smaller than the original circuit$-$and have low-depth garbling algorithms, where the garbling process runs in parallel time logarithmic in the circuit size. Prior schemes achieve one but not the other, unless relying on indistinguishability obfuscation ($\mathsf{iO}$), which is prohibitively inefficient, relies on a combination of multiple assumptions, and achieves only polynomial garbling depth $\mathsf{poly}(\lambda,\log |C|)$.

We resolve this tension by presenting the first garbling schemes that are both succinct and admit garbling algorithms in $\mathsf{NC}^1$, based only on standard group and lattice assumptions. Our main results include: • $\textbf{One-bit-per-gate garbling}$ with logarithmic garbling depth based on DDH or RLWE and the existence of a local PRG. • $\textbf{Succinct privacy-free garbling}$ of size linear in the circuit depth $D$ (and sublinear in the circuit size $|C|$), based on DDH or RLWE. • $\textbf{Reusable, fully succinct garbling}$ with logarithmic garbling depth, based on decomposable LWE.

The DDH-based one-bit-per-gate scheme has tunably small inverse polynomial correctness and privacy errors, which can be made negligible at the cost of increasing garbling depth to $\mathsf{poly}(\lambda)$.

As further extension, we also obtain the first attribute-based encryption schemes with succinct keys and low-depth key generation.

At a conceptual level, our constructions are derived from a unified framework that subsumes all prior approaches to succinct garbling. It identifies the common source of high-depth garbling, and provides a general methodology for reducing garbling depth without sacrificing succinctness, applicable across different techniques and assumptions.

We present the first construction of attribute-based laconic function evaluation (AB-LFE) from the decisional composite residuosity (DCR) assumption. This yields the first example of computationally succinct secure computation from a group-based assumption, avoiding reliance on noisy lattice assumptions such as LWE. Our construction builds on recent work in fully homomorphic MACs and homomorphic secret sharing by Ishai, Li and Lin (FOCS 2025) and Meyer, Orlandi, Roy, and Scholl (Crypto 2025), which we extend by constructing a fully homomorphic MAC for packed vector operations, where the evaluation time of one party is independent of the vector length.

As applications, we obtain full-fledged laconic function evaluation (LFE) from the combination of DCR and standard LWE, avoiding the need for sub-exponential modulus-to-noise ratio LWE used in previous work. We also obtain the first constrained pseudorandom function whose master evaluation key is succinct in the constraint.

These results highlight the unexplored power of group-based cryptography for succinct secure computation.

The interest in verifiable credential systems has gained traction as eIDAS 2.0 Regulation has been published. This regulation instructs EU member states to provide their citizens with digital identity wallets (EUDI Wallet) that must store the credentials and enable privacy-preserving presentation of identity information to relying parties. This new digital identity system requires defining new protocols and procedures to perform tasks involving the disclosure of identity information. One of such procedures is the delegation of attestation, as is reported in the EUDI Wallet Reference Implementation Roadmap.

In this work, we address the problem of constructing secure processes for the delegation of verifiable presentations derived from both verifiable and anonymous credentials. Our goal is to enable a credential holder (the delegator) to securely delegate another party (the delegatee) to present a credential on their behalf. We introduce the notion of a verifiable presentation delegation scheme, formalizing the core algorithms, namely delegation issuance, delegated presentation, and presentation verification, and defining the relevant security properties that such a scheme should satisfy: the correctness, the unforgeability, and, when the scheme is built on top of anonymous credentials, even the unlinkability. We present two concrete instantiations of delegation schemes: the first is built on top of mdoc verifiable credentials, the credential format currently supported by the EUDI Wallet Architecture and Reference Framework (EUDI ARF), while the second is built on top of BBS anonymous credentials. Finally, we discuss and analyze the security of our constructions in terms of the security properties we have introduced.

Secure multi-party computation (MPC) enables $N$ parties to jointly evaluate any function over their private inputs while preserving confidentiality. While decades of research have produced concretely efficient protocols for small to moderate numbers of participants, scaling MPC to thousands of parties remains a central challenge. Most of the existing approaches either incur per-party costs linear in $N$, due to pairwise computations, or rely on heavy cryptographic tools such as homomorphic encryption, which introduces prohibitive overheads when evaluating Boolean circuits.

In this work, we introduce a new lightweight approach to designing semi-honest MPC protocols with per-party, per-gate computation and communication costs that are independent of $N$. Our construction leverages the Sparse Learning Parity with Noise (Sparse LPN) assumption in the random oracle model to achieve per-gate costs of $O(k^2 \cdot c(\lambda))$ computation and $O(c(\lambda))$ communication, where $k$ is the sparsity parameter for the Sparse LPN assumption and $c(\lambda)$ is an arbitrarily small super-constant in the security parameter $\lambda$. Assuming Sparse LPN remains hard for any super-constant sparsity, this yields the first semi-honest MPC protocol in the dishonest-majority setting with per-party per-gate costs bounded by an arbitrarily small super-constant overhead in $\lambda$.

Structurally, our MPC instantiates a Beaver style MPC with the required correlations generated efficiently. Departing from prior approaches that generate Beaver triples silently (Boyle et al., 2019; 2020; 2022) or using homomorphic computation (Damgård et al., 2012) for Beaver style MPC, the focus of this work rests on efficiently generating a weaker correlation. In particular, using Sparse LPN we show that if we relax the correctness requirement in generating random Beaver triples to permit a tunably small inverse-polynomial error probability, such triples can be silently generated with arbitrarily small super-constant per-party computation. We then show that such correlations can be used in an efficient online phase similar to Beaver's protocol (with a tiny super-constant factor blow-up in communication).

Collecting statistics from users of software and online services is crucial to improve service quality, yet obtaining such insights while preserving individual privacy remains a challenge. Recent advances in function secret sharing (FSS) make it possible for scalable privacy-preserving measurement (PPM), which leads to ongoing standardization at the IETF. However, FSS-based solutions still face several challenges for streaming analytics, where messages are continuously sent, and secure computation tasks are repeatedly performed over incoming messages. We introduce a new cryptographic primitive called streaming function secret sharing (SFSS), a new variant of FSS that is particularly suitable for secure computation over streaming messages. We formalize SFSS and propose concrete constructions, including SFSS for point functions, predicate functions, and feasibility results for generic functions. SFSS powers several promising applications in a simple and modular fashion, including conditional transciphering, policy-hiding aggregation, and attribute-hiding aggregation. In particular, our SFSS formalization and constructions identify security flaws and efficiency bottlenecks in existing solutions, and SFSS-powered solutions achieve the expected security goal with asymptotically and concretely better efficiency and/or enhanced functionality.

Modular reduction over binary extension fields $\mathbb{F}_{2^m}$ is a fundamental operation in cryptographic implementations, including GCM and Elliptic Curve Cryptography. Traditional reduction algorithms (e.g., linear LFSR-based methods) are highly sensitive to the algebraic structure of the defining polynomial. This sensitivity is especially acute for trinomials $P(x) = x^m + x^t + 1$, where cryptographic standards have historically mandated the use of ``friendly'' polynomials (with small $t$) to avoid the linear performance degradation associated with ``random'' or ``unfriendly'' parameters. In this paper, we challenge this constraint by introducing Suwako, a novel reduction algorithm. By exploiting the self-similar algebraic structure of the reduction map, Suwako transforms the reduction process from a serial iterative chain (dependent on the degree gap $\Delta = m-t$) into a logarithmic-depth binary-doubling structure. We theoretically prove that Suwako achieves $O(\log m)$ folding depth for arbitrary trinomials, regardless of the position of the middle term $t$. Furthermore, unlike window-based or Montgomery/Barrett reduction methods, Suwako requires no pre-computation, making it optimal for dynamic environments.