International Association
for Cryptologic Research

Organizations relying on RSA-OAEP encryption in protocols such as JWE, SAML, and OIDC face a critical challenge: transitioning to post-quantum cryptography without disrupting operational continuity. This paper presents a phased migration strategy that uses RSA-KEM-ML-KEM composite Key Encapsulation Mechanisms as an intermediary step between current RSA-OAEP encryption and the target state of pure ML-KEM adoption. We formalize the RSA-KEM-ML-KEM construction, prove IND-CCA2 security via a Split-Key PRF combiner, and integrate it into the Hybrid Public-Key Encryption (HPKE) framework. Our implementation demonstrates that composite schemes enable quantum-resistant encryption while preserving existing RSA key infrastructure, though with measurable throughput trade-offs that inform migration timelines. We analyze protocol-specific integration for JWE, SAML, and OIDC encryption use cases, providing decision frameworks for transitioning from RSA-OAEP through composite approaches to pure post-quantum encryption. This work contributes a formally analyzed transition mechanism and practical migration guidance for organizations seeking to adopt quantum-resistant encryption in RSA-dependent systems, validated through application to identity and access management protocols.

Using the language of categories, we introduce a novel framework abstracting the key algorithmic features of the Deuring correspondence between supersingular elliptic curves and quaternion orders and of the post-quantum signature scheme SQIsign based on it. We then show how to construct an interactive identification scheme and digital signature within this framework, and also instantiate more advanced primitives, such as a chameleon hash function. We present two distinct instantiations of the framework based on isogenies of supersingular elliptic curves: the first recovers (one-dimensional) SQIsign, while the second leads to the recently published SQInstructor.

FrodoKEM is an unstructured LWE-based key encapsulation mechanism (KEM), widely recognized for its conservativeness and robustness. However, there remains a performance gap of approximately one order of magnitude between FrodoKEM and structured LWE-based KEMs, which severely limits its competitiveness during the standardization process. This work proposes the fastest hardware implementation of FrodoKEM to date, which is also configurable, achieving up to 2.5× speedup over prior hardware designs. Specifically, for the most time-consuming module, modular matrix multiplication, a block matrix processing approach is adopted, where the computation is reformulated into block-level operations and further mapped to vector inner-product computations. Based on this formulation, two optimized architectures are proposed for vector inner-product computation using a carry-save-adder (CSA)-based Wallace tree structure, achieving improvements in resource efficiency while eliminating the use of DSP resources. By fixing the block size to 4×4, the data generation rate using parallel SHAKE-based random number generators is precisely matched with the data consumption rate of matrix multiplication, thereby improving hardware utilization efficiency. The proposed design is implemented in Verilog and verified on both Xilinx Virtex-7 and Artix-7 FPGA platforms, as well as ASIC implementation.

Digital signature schemes based on isogenies are among the most compact signatures achieving post-quantum security. Recent advances, especially those leveraging higher-dimensional isogenies, have also made such schemes practically efficient. However, comparatively little attention has been devoted to endowing these signatures with additional privacy-enhancing properties, such as the re-randomization of keys and the adaptation of signatures to new public keys. Although some results exist in the isogeny group action setting, these signatures suffer from a subexponential quantum attack which renders them rather inefficient.

In this work, we initiate the first systematic study of privacy-enhancing isogeny-based signatures outside the group-action framework. We base our exploration on the notion of signatures with randomizable keys developed by Celi et al. (FC'24), which aims to unify privacy notions related to key updatability and signature adaptation. In particular, we analyze which of their privacy notions can be achieved from the state-of-the-art signatures SQIsign, PRISM and the hash-and-sign signature scheme derived from the Deuring verifiable unpredictable function (DeuringVUF).

To this end, we naturally extend SQIsign to an SWRK scheme that allows key randomization, and enhance both PRISM and the DeuringVUF signature to additionally allow for message adaptation. We show that, due to the deterministic nature of the signatures, the DeuringVUF signature achieves perfect adaptability. We formally prove all three of our modifications achieve unlinkability against unbounded adversaries, and remain unforgeable under the same assumptions as the original schemes.

The hardness of the Learning Parity with Noise (LPN) problem is a foundational assumption in cryptography, forming the basis of constructions ranging from symmetric-key primitives to public-key encryption and beyond. A central open question is whether the average-case hardness of LPN can be based on worst-case complexity assumptions, as has been achieved for the analogous Learning With Errors (LWE) problem.

Existing worst-case-to-average-case reductions for LPN [BLVW19, YZ21] rely on statistical smoothing of linear codes, which inherently limits the resulting average-case hardness to noise rates as large as $1/2 - 1/\mathrm{poly}(n)$, which is insufficient for public-key applications.

We explore a new approach towards obtaining such reductions: rather than requiring that random sparse combinations of the rows of the generator matrix of a code be statistically close to uniform, we only require that they be computationally indistinguishable from uniform. This leads to a clean win-win structure: we show that any efficient LPN solver can be transformed into a pair of efficient algorithms $(S, D)$ such that for every matrix $A$ of appropriate dimensions over $\mathbb{F}_2$, either $S$ decodes the code generated by $A$ from random noise, or $D$ distinguishes random noisy codewords of the dual of this code from uniform.

By instantiating this reduction with appropriate parameters, we obtain the average-case hardness of LPN with inverse-polynomial noise rate $n^{-\alpha}$ for any constant $\alpha < 1$, assuming the worst-case simultaneous hardness of decoding a code from random noise and distinguishing random noisy codewords of its dual from uniform. In particular, setting $\alpha = 1/2$, our reduction yields LPN hardness in the parameter regime required for Alekhnovich's construction of public-key encryption [Ale03], a regime that was previously inaccessible via worst-case reductions.

We study the security of the Fiat-Shamir transformation when applied to multi-round oracle proofs in the standard model, showing that Interactive Oracle Proofs (IOPs) can be transformed via Fiat-Shamir into Non-interactive Zero-knowledge (NIZK) arguments.

We obtain our result in two steps. First, we show that instantiating Kilian's transformation with an IOP satisfying a mild Zero-Knowledge (ZK) property called semi-Honest-Verifier ZK (semi-HVZK), and a commitment scheme that is extractable and equivocal, yields a ZK argument. We then obtain provably-secure NIZK arguments from our interactive ZK arguments by instantiating Fiat-Shamir with a Correlation-Intractable Hash (CIH) function. The second step involves carefully defining an appropriate "bad relation" for which CIHs are known to exist. Existence of CIH for our bad relation requires the underlying semi-HVZK IOP to have an additional "doom checkability" property which we introduce. Roughly, doom checkability guarantees that one can efficiently check whether a non-empty partial IOP transcript is "doomed" in the sense that it will lead the verifier to reject. We then show that IOPs based on the "MPC in the Head" paradigm are doom checkable.

Our results show that the Fiat-Shamir paradigm can be applied to semi-HVZK IOPs to yield provably-secure NIZKs. This extends similar results known for single-round IOPs (i.e., Probabilistically Checkable Proofs) and interactive proofs (IPs), and establishes the soundness of this method. Along the way, we also prove composition theorems for semi-HVZK IOPs, which might be of independent interest, and use them to improve the soundness error of linear-time IOPs and interactive arguments from the literature.

Isogeny-based cryptography is a kind of cryptography whose security relies on the computational hardness of the isogeny problem. This field is gaining attention as a promising candidate for post-quantum cryptography. Among the notable schemes within this category is SQIsign, a signature schemes that has been submitted to the NIST Post-Quantum Cryptography Standardization competition. In this paper, we introduce a new isogeny-based signature scheme, $\Delta$-SQIsign, which represents a significant departure from existing isogeny-based signatures including SQIsign. The key distinction in our scheme lies in its use of the degree of isogeny as a challenge within the underlying $\Sigma$-protocol. Then, the prover outputs an isogeny of the given degree as a response. To construct such a scheme, we introduce a new algorithm, called $\Delta$-KLPT, which is a variant of GeneralizedKLPT. Similar to GeneralizedKLPT, our algorithm outputs an ideal equivalent to a given ideal with a fixed norm; however, under certain conditions, it can produce an ideal of smaller norm than GeneralizedKLPT.

Real-time group communication protocols, such as Zoom and Microsoft Teams, aim to provide end-to-end security for audio and video conferences even in the presence of a malicious server. Despite their widespread deployment, particularly since the COVID-19 pandemic, their intended security guarantees lack comprehensive formalization. Prior work largely focuses on Zoom, and analyzes its security in models that rely on restrictive assumptions, such as the existence of a trusted server at certain points in time or a long-lived leader that never leaves the group. Moreover, existing analyses assume that group-specific session states of group members are secure and incorruptible, leaving the impact of potential full state compromise on group security unexplored.

In this work, we propose a set of essential security guarantees for real time group communication with state-compromise resilience against fully malicious servers and provide the first construction that provably satisfies all of these guarantees. To formally prove that our design achieves its goal, we formalize a novel continuous group key distribution protocol and introduce an associated security model that captures all the intended guarantees. We propose a generic construction that is provably secure in this model and suggest both classical and post-quantum secure instantiations.

Besides these main design goals, we introduce a novel multi-recipient authenticated key encapsulation mechanism, which serves as a building block for our generic construction. We define two core security notions for maKEM, propose both concrete and generic constructions, and prove their security in the random oracle model and the standard model, respectively.

Although the state-of-the-art neural network model extraction attack in the hard-label setting by Carlini {\em et al.} at EUROCRYPT 2025 has polynomial-time complexity in theory, its dual-point clustering relies on singular value decomposition (SVD) with a time complexity of $\mathcal{O}(n^2 \cdot (d^{(k)})^3)$, resulting in huge runtime in practice. To address this computational bottleneck, this work transforms Carlini {\em et al.}'s geometric-view hard-label attack into an algebraic framework, and proposes a novel Approximate Signature Vector (ASV) method to achieve efficient parameter extraction on Fully Connected Neural Networks (FCNNs) by leveraging two key observations: high-dimensional random vectors are nearly orthogonal, and neurons in practical DNNs tend to learn disentangled features. The proposed ASV method replaces SVD-based rank checking with simple inner-product operations, reducing the clustering complexity to $\mathcal{O}(n \cdot (d^{(k)})^3)$ on average. Furthermore, this paper presents the first model extraction attack against hard-label max-pooling Convolutional Neural Networks (CNNs) by proposing an advanced ASV method with a kernel-centric clustering scheme instead of the neuron-centric clustering, which fully exploits the property of weight sharing in convolutions and fills the cryptanalysis gap. Experiments on a 64-64$\times 4$-10 FCNN and LeNet-5 (CNN) with max pooling demonstrate that our ASV method drastically cuts clustering time, and improves the overall efficiency in the model extraction.

Functional bootstrapping combines ciphertext refreshing with the evaluation of a target function, and has become a central tool for evaluating non-linear functions in homomorphic encryption. In the CKKS scheme, functional bootstrapping typically represents the target function as a trigonometric polynomial over the exponential basis generated by the bootstrapping procedure. Existing CKKS functional bootstrapping methods then evaluate this polynomial using standard baby-step giant-step techniques, whose multiplicative depth grows logarithmically with the polynomial degree. As a result, non-smooth function evaluations or high-degree lookup tables require a large modulus budget and often a larger ring degree, leading to higher evaluation latency. This is especially inefficient for applications that require only hundreds of parallel evaluations, where the large SIMD capacity of CKKS is not fully utilized.

We present \textsf{SWIFT}, a shallow and SIMD-aware functional bootstrapping framework for CKKS. The key idea is to exploit the exponential map \(h(x)=\exp(2\pi i x)\) used in CKKS bootstrapping, which satisfies \(h(\ell x)=h(x)^\ell\) for $\ell\in \mathbb Z$. Thus, the powers required for trigonometric polynomial evaluation can be obtained directly as \(h(\ell x)\) during bootstrapping, rather than generated by homomorphic multiplications after bootstrapping. To realize this idea efficiently, \textsf{SWIFT} packs the scaled inputs \(\ell x\) into SIMD slots and evaluates the exponential map on them in parallel. It then reconstructs the target trigonometric polynomial from the resulting powers. As a result, the multiplicative depth of polynomial evaluation becomes independent of the polynomial degree and can be reduced to constant depth, even depth one.

This shallow structure reduces the required modulus budget and enables high-degree polynomial evaluation at smaller ring degrees. It also lowers the key-switching cost from the standard \(\Theta(\sqrt d)\) cost to \(\Theta(\log d)\) or \(\Theta(d^{1/4})\), depending on our parameter regime. Our implementation shows that computations previously requiring \(\log N=16\) or \(\log N=17\) can be performed at \(\log N=15\). For lookup tables, \textsf{SWIFT} achieves up to a \(38.1\times\) latency improvement over prior CKKS functional bootstrapping methods at batch size \(128\). For ReLU evaluation at batch size \(256\), it achieves a \(5.21\times\) latency improvement over the previous method. These results demonstrate that CKKS functional bootstrapping can be made latency-efficient for batch sizes on the order of hundreds by using SIMD capacity as a computational resource rather than only as a batching mechanism.

The recent study of fixed-key differential probabilities mainly follows two complementary approaches. The first derives key-dependent constraints from the internal structure of the primitive. This approach is intuitive, but a complete theory is difficult to build. The second approach is based on quasidifferentials. It is complete in theory when all quasidifferentials are considered, but exhaustive enumeration is usually infeasible in practice. In this paper, we relate quasidifferentials to concrete key-dependent constraints. This gives new insights into quasidifferentials. Each quasidifferential with a nonzero mask carries one relation, equating a linear parity of the involved key bits to a generally nonlinear Boolean function of the intermediate-state bits, and the relations that share these bits together constrain the key. Under the common threshold-based treatment, where only quasidifferential trails with sufficiently large absolute correlation are kept, some constraints on intermediate-state bits may be lost. This can produce an incomplete quasidifferential trail set with respect to the induced intermediate-state constraints. This, for example, can result in the fixed-key differential probabilities computed by quasidifferential aggregation to become negative on some key subspaces. To obtain a more precise distribution of fixed-key differential probabilities over the key space, we decouple quasidifferential trails according to their induced constraints. After decoupling, each resulting quasidifferential trail set is locally complete, so the derived probability distribution for the particular subspace is always valid. The decoupling also reduces the number of trails in each set, improving the efficiency of the quasidifferential method. As a result, our method yields a finer-grained key-space partition that could allow us to better approximate the true distribution under the quasidifferential framework. We instantiate this decoupling strategy in the threshold-based setting and apply it to differential trails of GIFT-64, GIFT-128, SKINNY-64, SKINNY-128, and RECTANGLE. The resulting locally complete trail sets always give valid fixed-key differential probability distributions and are no coarser than direct threshold-based quasidifferential aggregation. They coincide with direct aggregation when the retained trails are already locally complete. In our experiments, using our decoupling method is actually better for many evaluated trails and refines the key-space restrictions reported by prior constraint-detection frameworks. As each quasidifferential is a constraint, the same insight also let us write the induced linear and nonlinear key constraints explicitly for the bit-wise ciphers GIFT-64, GIFT-128, and RECTANGLE, addressing a limitation of the Trail-Estimator constraint detector described in Peyrin, Tan, Zhang and Zhou at FSE, 2025.

Synchronized multi-signatures allow for non-interactive aggregation of signatures generated within the same time step. This primitive is particularly well-suited for high-throughput blockchain protocols like Ethereum, where many distributed signers must validate the same block within a synchronized slot. In this work, we present Lemur, a post-quantum synchronized multi-signature from (module) lattices that improves upon the state-of-the-art in efficiency, scalability, and flexibility. Lemur follows the blueprint of Squirrel/Chipmunk (CCS 2022/2023) but introduces a fundamental redesign of the foundations of the overall framework. Our revisit of the framework is also motivated by the fact that our evaluation of Chipmunk's parameter sets, using the state-of-the-art lattice security estimation methods, suggests a substantially lower concrete security level (approximately 30 bits rather than the claimed 112 bits). First, we revisit the underlying building block of key-homomorphic one-time signature (KOTS) and introduce a novel security reduction based on a new lattice problem: the Dual Hint-MLWE assumption, which may be of independent interest. We then provide a formal reduction from the standard Module-LWE problem to Dual Hint-MLWE, which overall enables us to base the security of Lemur on the standard Module-LWE and Module-SIS assumptions. By shifting from a statistical security argument to a computational one, our KOTS design enjoys much better compactness and scalability. Second, we optimize the underlying homomorphic vector commitment (HVC) by transitioning from Ring-SIS to the Module-SIS setting and extending the commitment domain from vectors to matrices. This generalization reduces opening size and improves aggregation efficiency. After rectifying the parameters of Chipmunk for a fair comparison, our results show that Lemur's KOTS size achieves up to an order of magnitude improvement over Chipmunk's KOTS. In particular, aggregating 1 million one-time signatures requires under 8 KB. For the total multi-signature size, Lemur demonstrates around $2\times$ improvement over Chipmunk. To showcase our design, we provide a full-fledged Rust implementation. Our benchmarks demonstrate an aggregate signature size of 380 KB for $2^{20}$ signers. Stateful signing takes roughly 4.2 ms for a Merkle tree of height 20, while batch verification for an aggregate of 1024 signers completes in 15.0 ms ($\approx$ 14.6 $\mu$s per signer).

We study generic committing attacks—where ciphertexts decrypt under more than one context, i.e., key, nonce, associated data—for sponge-based authenticated encryption. As our main contribution, we give three new committing attacks which outperform existing attacks. One of our attacks provides a counterexample showing that the previous proof for the committing security of Ascon-like schemes with zero-padding does not extend to all parameter choices: in case of 128-bit tags and 256-bit zero-padding, the existing analysis claims 192-bit security; our attack reduces this by 62 bits down to 130-bit. Our attacks are applicable to the standardized scheme Ascon. As a further contribution, we analyze existing attack strategies for a generic sponge construction with various design features such as key-blinding, zero-padding, and state-update-functions.

Asynchronous distributed key generation (ADKG) is a fundamental primitive for building threshold cryptosystems and fault-tolerant distributed protocols in adversarial network settings. A central objective in this line of work is to achieve ADKG with $O(n^2)$ communication and constant round complexity under minimal setup assumptions. Recent progress has led to subcubic-communication ADKG protocols under different trade-offs. Feng and Tang (CRYPTO 2025) presented an ADKG protocol with $O(n^2)$ communication and $O(1)$ rounds, but at the cost of a cubic-communication setup phase in which each party posts a linear-sized public key on a public bulletin board. In contrast, Abraham et al. (PODC 2026) achieved an ADKG protocol with a standard setup phase, where each party posts only a constant-sized public key, but with $O(n^{2+1/k})$ communication and $O(k)$ rounds for a tunable parameter $k\leq \log{n}$. These results leave open whether one can simultaneously obtain constant-round complexity and quadratic communication under a standard setup phase.

In this work, we resolve this open problem by presenting the first ADKG protocol that achieves $O(n^2)$ communication and $O(1)$ rounds while requiring only a standard setup phase in which each party posts a constant-sized public key on a public bulletin board. Our protocol is resilient to a strongly adaptive adversary corrupting up to $f < n/3$ parties and assumes only random oracles and secure erasures, both of which are also assumed by prior subcubic-communication ADKG constructions.

This paper introduces a geometric framework for Q2 quantum distinguishers by combining the geometric approach to classical symmetric-key cryptanalysis with the generalized correlation extraction algorithm. Our main technical tool shows that one superposition query, followed by appropriate (unitary) change-of-basis operations, prepares a ``correlation state'' whose amplitudes are the entries of the geometric correlation matrix in the chosen basis. This yields a unified preparation-measurement template that recovers several known quantum distinguishers: (1) hidden structure detection via support constraints in Fourier-type bases (e.g., Simon, Bernstein-Vazirani, Deutsch-Jozsa), and (2) event probability deviation tests via amplitude estimation (covering standard quantizations of linear and differential distinguishers). We analyze when relevant distinguishing mass is diluted across many basis states, identify it as a cause of poor query efficiency in several recent distinguishers, and provide basis-specific mechanisms to concentrate the signal (phase-oracle row restriction in the Fourier setting; chosen-plaintext subset-state restriction in the quasidifferential setting) to restore quadratic advantage. We illustrate the framework on Fourier and quasidifferential instantiations and discuss obstacles for non-unitary integral bases.

In this paper we introduce a simple and unified approach, based on generic proof systems, to prove knowledge of any isogeny between two principally polarized abelian varieties in any dimension, assuming that the $2^m$-torsion is accessible for sufficiently large $m$. Previous generic proof approaches were only able to prove knowledge of a smooth degree isogeny between elliptic curves, where for each small prime factor $\ell$ of the degree, bespoke constraints had to be derived, typically from (a variant of) the $\ell$-th modular polynomial. Our approach is much simpler in that it relies on proving knowledge of a $2^n$-isogeny between two principally polarized abelian varieties in any dimension. Furthermore, our approach is unified in that the constraints are essentially the same for each dimension, resulting in a simpler and easier-to-optimize algorithm. Our construction has immediate applications to proving knowledge of an isogeny of any degree between two elliptic curves, by using a higher dimensional representation. Indeed, by a result of Robert, any isogeny can be embedded in a $2^n$-isogeny by increasing the dimension, and conversely, the knowledge of a $2^n$-isogeny between products of varieties implies the knowledge of an isogeny of degree $\leq 2^n$ between a factor of the domain and codomain. Our generic proof does not disclose the degree of the secret isogeny, nor does it rely on knowing the endomorphism ring, thereby solving an open problem posed by Beullens, De Feo, Galbraith, and Petit in 2023. Two use cases are immediate. First, if one wants to prove knowledge of any isogeny between two supersingular curves over $\mathbb{F}_{p^2}$, e.g. during the generation of an elliptic curve with unknown endomorphism ring. Second, to prove knowledge of a secret isogeny coming from the class group action on oriented supersingular elliptic curves, e.g. CSIDH with curves defined over $\mathbb{F}_p$. Computing such group actions is typically done using qt-Pegasis, which naturally results in a 4-dimensional representation of the isogeny. Lastly, we propose two tailored zero-knowledge proof systems that improve proving time and proof size without loss of generality and provide the first implementation in dimension 2 and 4 by implementing both proof systems in Rust.

We present improved distributed broadcast and MST algorithms that are unconditionally secure against an eavesdropper controlling a fixed set of at most $f$ edges in an $n$-node $m$-edge $D$-diameter graph. We strive for secure algorithms with sublinear round and subquadratic message complexities (in $n$) for any $f$. This is in contrast to the exponential or polynomial dependence on $f$ in prior works. Our main results are: Secure broadcast algorithm, for sending an $O(\log n)$-bit message, that runs in $\tilde{O}(D+\sqrt{n})$ rounds and $\tilde{O}(n^{3/2})$ messages. This matches the state-of-the-art bounds for \emph{insecure} broadcast by [Ghaffari and Kuhn, and Gmyr and Pandurangan, DISC 2018]. Our bounds also improve over the $\tilde{O}(D+\sqrt{f n})$-round complexity and $\tilde{O}(\sqrt{f n}\cdot m)$ message complexity of secure broadcast by [Hitron, Parter and Yogev, DISC 2022]. Secure MST algorithm with sublinear round and subcubic message complexities that improve over the algorithm by [Hitron, Parter and Yogev, ITCS 2023] in the entire regime. In particular, when $f=\Theta(n)$, we improve the round complexity from $\tilde O(n^{3/2})$ to $\tilde O(n^{2/3})$, and the message complexity from $\tilde O(n^{3})$ to $\tilde O(n^{7/3})$.

Our algorithms are randomized and their correctness and (statistical) security hold with high probability. The algorithms are based on a combination of techniques: Karger's sampling, tree packing and sparse recovery sketches.

Proximity testing is crucial to location-privacy applications, from discovering nearby friends to enabling UAV collision avoidance. In such settings, users must determine proximity without revealing their exact locations. This motivates privacy-preserving proximity testing (PPPT) protocols revealing only if the proximity condition holds, while hiding both parties’ inputs. However, most existing PPPT protocols rely on strong assumptions (e.g., non-colluding servers) or require simultaneous interaction, limiting their practicality. Moreover, they typically define proximity using metric distances (e.g., Euclidean distance), failing to support richer membership queries for complex regions like buildings or parks. To address these, we introduce a new primitive called Geometric Fuzzy Matching (GFM), which generalizes fuzzy matching to arbitrary $n$-dimensional regions. In GFM, the receiver specifies a region and learns only whether the sender’s location lies within it, without revealing either party’s input. This approach captures both classical distance-based proximity checks (for any Minkowski $\ell_p$ norm, $1 \leq p \leq \infty$), as well as membership tests for complex regions, providing a unified framework for diverse proximity queries. In low-dimensional settings, our protocol improves on distance-based checks compared to state-of-the-art van Baarsen et al. (EUROCRYPT 2024) for $\ell_\infty$ and maintains stable practical efficiency for $\ell_p$ norms under large distance thresholds or for $p \geq 4$, where previous approaches quickly become computationally prohibitive. It is also the first to support fuzzy matching over arbitrary geometric regions, enabling proximity queries in complex spaces. Our implementation confirms these results and demonstrates the protocol’s efficiency and applicability across diverse PPPT scenarios.

A leakage-tolerant circuit (LTC) can be viewed as a black-box implementation of a given functionality f with respect to a leakage class L in the sense that any leakage function L ∈ L applied to the circuit’s internal wires can be simulated by a similar leakage function L′ ∈L applied only to the circuit’s inputs and outputs. Previous works have demonstrated extensive applications of LTCs in constructing variants of leakage-resilient circuits (LRC): black-box construction of both stateless and stateful LRCs, and construction of deterministic stateful LRCs which only require external fresh randomness in the first invocation. However, feasibility results for LTCs are still limited to simple leakage classes, including only probing leakage, depth-1 AC0 leakage, and parity leakage. In this work, we instantiate the study of constructing LTCs and deterministic stateful LRCs against AC0 leakage, obtaining the following results: – We present the first construction of LTCs against generic AC0 leakage. As a corollary, we also construct LTCs against parity leakage with efficient simulation, refuting a conjecture proposed by Ishai and Song (Eurocrypt 2024). – We provide a generic framework to convert LTCs into computationally secure deterministic LRCs assuming one-way functions, and instantiate the paradigm for k-CNF leakage (with a sufficiently small k). This is the first instance of deterministic stateful LRCs against non-decomposable leakage.

Public-key authenticated encryption with keyword search (PAEKS), introduced by Huang and Li (Information Sciences 2017), was proposed to provide trapdoor privacy, whereby keyword information is protected from being revealed through trapdoors. To prevent the keyword guessing attack, however, a trapdoor needs to be generated separately for each sender, and the search complexity grows with the number of senders even when searching for a single keyword. To address this inefficiency, we propose a generic construction of search-efficient PAEKS. We revisit the approach of Wang et al. (IEEE Transactions on Information Forensics and Security 2024), in which senders are organized into sender groups. Our construction is simple yet effective where all senders belonging to the same group share a single public-secret key pair, and the search complexity depends only on the number of sender groups rather than the number of individual senders. We further introduce ciphertext indistinguishability against insiders, which ensures that no keyword information is revealed from ciphertexts, even if they are generated by other members of the same sender group. We also take into account an impossibility result by Yoshida and Emura (IEICE Transactions, 2026), which shows that trapdoor privacy against sender-group members cannot be achieved in the scheme of Wang et al. To address this limitation, we introduce trapdoor indistinguishability against outsiders, which guarantees that no keyword information is revealed from trapdoors generated for non-group members. Our generic construction yields search-efficient group-oriented PAEKS schemes from pairings and lattices.