Attribute-based signatures (ABS) provide fine-grained control over who can generate digital signatures and have many real-world applications. This paper presents a pair of fast ABS schemes: one for Key-Policy ABS (KP-ABS) and another for Signature-Policy ABS (SP-ABS). Both schemes support expressive policies using Monotone Span Programs (MSP), and offer practical features such as large universe, arbitrary attributes, and adaptive security. Most notably, we provide the first implementation of MSP-based ABS schemes and demonstrate that our schemes achieve the best-known asymptotic and concrete performance in this domain. Asymptotically, key generation, signing and verification time scale linearly with the number of attributes; verification requires only two pairing operations. In concrete terms, for 100 attributes, our KP-ABS scheme performs key generation, signing, and verification in 0.16s, 0.10s, and 0.13s, respectively; our SP-ABS scheme achieves times of 0.082s, 0.26s, and 0.21s for the same operations.

At Asiacrypt'25, Lapiha and Prest proposed a lattice-based IND-CCA threshold key-encapsulation mechanism (TKEM) obtained from a threshold identity-based encryption (TIBE) and a signature scheme. Their construction relies on a variant of the Boneh-Canetti-Halevi-Katz (BCHK) transform, instantiated with a lattice-based TIBE. However it suffers from large ciphertexts at 540 KiB for $\kappa = 128$ bits of security. We present substantial improvements to their TIBE, resulting in the first concretely efficient lattice-based IND-CCA TKEM, with ciphertexts just under 30 KiB for a threshold $T = 32$, $Q = 2^{45}$ queries, and the same $\kappa$. Our design simplifies the original framework by leveraging the power of random oracles already present in their construction. We further enhance efficiency by adopting approximate computations where appropriate and by replacing module-NTRU trapdoors with NTRU trapdoors, achieving a remarkable eighteenfold reduction in ciphertext size. Finally, leveraging recent developments in secret sharing, we ensure the verifiability of key-extraction shares even in the presence of malicious parties.

Password-Authenticated Public Key Encryption (PAPKE) enables secure encryption using only a shared, human-memorable password—eliminating the need for trusted intermediaries or pre-established infrastructure. It allows a sender to encrypt a message for a recipient, using the recipient's password-authenticated public key and a shared password, while provably resisting man-in-the-middle and offline dictionary attacks. PAPKE's support for reusable password-authenticated public keys makes it especially suitable for asynchronous, PKI-free communication scenarios. An important open problem is to construct PAPKE schemes that are secure against quantum adversaries, as existing instantiations rely on Diffie-Hellman assumptions. The PAPKE-IC construction (ACNS 2019) is generic and admits integration with post-quantum PKE schemes. However, the scheme assumes an Ideal Cipher (IC) over the public key domain, which is large for most post-quantum PKE schemes. While an IC is typically instantiated using a block cipher, standard block ciphers operate over much smaller domains (e.g., 128 or 256 bits). Alternatively, one can use an 8-round Feistel network, which achieves indifferentiability from an ideal cipher, or domain extenders. The latter are inefficient at the domain sizes required, making the efficient and secure instantiation of the IC in PAPKE-IC, in combination with post-quantum PKE, particularly challenging. In this paper, we propose PAPKE-HIC, a UC-secure PAPKE scheme built from a PKE scheme and a Half-Ideal Cipher (HIC, introduced at EUROCRYPT 2023), which circumvents the challenges of instantiating ideal ciphers over large domains. We provide a detailed security proof of PAPKE-HIC and establish precise requirements for the underlying PKE: strong robustness, one-wayness, ciphertext anonymity, and pseudo-uniformity of public keys. Our analysis identifies a gap in the original PAPKE-IC security proof, motivating the introduction of a novel property, which we denote Decryption Robustness (DROB-CCA). Although DROB-CCA is implied by strong robustness (SROB-CCA), the reduction is not tight and incurs a quadratic security loss. We analyze which PKE schemes directly satisfy DROB-CCA, and conclude by presenting concrete instantiations of PAPKE-HIC. To our knowledge, this is the first practical, post-quantum instantiation of the PAPKE primitive.

Subversion-resilient Authenticated key-exchange (AKE) aims to achieve the guarantees of secure AKE even in the presence of an adversary that has tampered with parts of the protocol's implementation. One way to achieve subversion-resilient AKE is the use of Reverse Firewalls (RFs), an untrusted third-party that can restore security. Recent work [18] highlights the challenges of designing RFs for practical secure channel-establishment. This paper extends existing RF-based subversion-resilient AKE at three levels: security definitions, constructions, and the use of formal verification. First, we introduce a useful relaxation of the notion of security in subversion-resilient AKE with RFs: the goal is no longer to prevent all exfiltration, but rather to restore to the AKE protocol a property lost upon subversion. We focus specifically on authenticating and (key-)securing RFs. We also discuss subversion-resilience against a spectrum of compromises, designing a flexible framework in which protocols are proved secure with respect to adversaries that can tamper with some components of the implementation, but perhaps not others. Our ultimate goal is to achieve post-quantum secure subversion-resilient key-exchange. Far from being trivial, this requires the introduction of a malleable-yet-secure notion of key encapsulation, which we dub re-randomizable Key Encapsulation Mechanism. We carefully formalize this new primitive and instantiate it first based on a classical Diffie-Hellman KEM and one based on Kyber. Finally, we lay the foundations for the formal verification of RF based protocols, by formally proving our protocol with the CryptoVerif prover, in addition to computational-security proofs in usual Bellare-Rogaway methodology.

The study of memory-hard functions (MHFs) has so far focused mainly on provable guarantees on the expected minimum cumulative memory complexity (CMC) required per \emph{evaluation} when amortized over multiple instances. Such results, however, say nothing about whether the passwords in a compromised password bank remain \emph{unrecoverable}. Indeed, a construction can be memory-hard while still leaking information about its input. We provide the first formal treatment of the unrecoverability of graph-based data-independent MHFs (iMHFs) in the multi-instance setting. Multi-instance security is the widely accepted security model when inputs have low entropy or are correlated, and requires the adversarial effort to scale linearly with the number of instances broken. To prove these results, we extend the ex-post-facto pebbling technique of Alwen and Serbinenko (STOC'15) and the unguessability reductions of Farshim and Tessaro (EUROCRYPT'21). We then combine the two resulting frameworks to bound the number of guesses of adversaries with a given \emph{maximum} CMC (over the random oracle and adversary coins) in terms of the pebbling complexity of the graph underlying the iMHF. Combined with known lower bounds on the pebbling complexity of Catena's underlying graph, we obtain concrete unrecoverability bounds for Catena, showing in particular that adversarial advantage diminishes exponentially with the number of instances recovered, with the per-instance advantage growing linearly in the maximum CMC of the adversary.

In this paper, we present some research on quantum complexity measurements for applying Grover's search algorithm to recover the key of a stream cipher, Atom. As a foundational step, we propose a novel and complete quantum gate-level design of Atom. We incorporate a quantum lookup table to implement the key filtering with a specific decimal counter value during the keystream generation phase, which is absent in the only known previous work on the quantum attack against Atom. Based on the proposed design, we present an algorithm based on Grover's search to recover the key of Atom. Considering the limited qubit capacity of the IBM Qiskit simulator, the proposed search algorithm, with a round-reduced initialization phase, is simulated for 3-qubit key recovery with a probability greater than 0.9. We provide resource estimations for the proposed quantum algorithms. We also perform optimizations on the resources required by the proposed Grover oracle and present a benchmark for Grover's search algorithm on Atom. The research findings in this paper claim that Atom satisfies NIST Level 1 security.

In this work, we initiate the study of aborting hash functions, i.e., hash functions that may abort on a non-negligible fraction of inputs. We introduce the aborting random oracle model (aROM), an idealized framework that extends the standard random oracle model (ROM) to account for aborts. Within this model, we derive bounds for various security notions and establish generic indifferentiability results demonstrating how to construct aborting random oracles from standard ones. Consequently, the derived bounds ultimately hold in the standard ROM. In this way, the aROM and its associated bounds provide a convenient and easy-to-use framework for analyzing cryptographic constructions that rely on potentially aborting hash functions. To illustrate the utility of our framework, we apply our techniques to two settings: (1) the analysis of SNARK-friendly incomparable hypercube encodings, a core primitive in hash-based signature schemes, and (2) the analysis of grinding in Fiat–Shamir-based non-interactive arguments. Through our generic indifferentiability results, we can easily translate these analyses into concrete security bounds in the standard (non-aborting) random oracle model.

Central bank digital currencies (CBDCs) and other related digital asset platforms have the potential to revolutionize the financial world. While these platforms have been deployed in test environments by virtually all large financial institutions, including central banks, there are still several limitations of these systems that prevent widespread adoption. These include (i) privacy, (ii) security against quantum adversaries, and (iii) auditability. In this work, we undertake (to our knowledge) the first formal study of these systems. While there have been many digital asset platforms implemented, we do not know of any formal model for a fundamentally UTXO-based digital asset platform/CBDC. Our first contribution is a formal modeling of a UTXO-based private digital asset system that meets our requirements listed above. This model is loosely based upon the open source software that we found came the closest to meeting our requirements, Linux Foundation Decentralized Trust (LFDT) Zeto. In the course of our formal modeling, we helped to improve the security of Zeto. We then provide an efficient construction of such a system, which we call Qurrency. Qurrency is an efficient UTXO-based privacy-preserving token system that includes an auditing mechanism and is secure against "harvest now, decrypt later" attacks, which is critically important for several central banks, including the Bank of Brazil. We implemented our construction to show that it is practically efficient and can be used on any EVM-based blockchain system with ease.

This paper presents an accelerated implementation of the Hamming Quasi-Cyclic (HQC) key encapsulation mechanism by leveraging additive Fast Fourier Transform (FFT) for polynomial multiplication (polymuls). A common challenge when applying FFT-based polymuls to HQC are the polynomial degrees fractionally greater than powers of two, making standard FFT polymuls inefficient for those parameters. We introduce a novel combination of additive FFT with the Chinese Remainder Theorem (CRT) to multiply such just-above-power-of-two degree polynomials. Further optimizations are achieved by caching the FFT transforms of the public and secret keys during or after key generation and reusing the transform of the shared random polynomial during the encapsulation and decapsulation processes. This approach significantly reduces redundant computations. The effectiveness of these optimizations is evaluated across various hardware platforms, including x86-64 with AVX2 and Galois Field New Instructions (GFNI), as well as ARM NEON on Apple M1 and Cortex-A72 processors. Benchmarks show that on platforms with long carry-less multiplication instructions like PCLMULQDQ, the proposed caching and reuse strategies allow FFT-based implementations to outpace traditional Toom-Karatsuba methods in the Encap and Decap operations of the HQC scheme, even with comparable raw multiplication speeds. On platforms lacking long carry-less multiplication instructions, the additive FFT approach already gives the superior performance.

Threshold signature schemes allow a group of users to jointly generate a digital signature, providing resilience against faults and enhancing decentralization. With the advent of post-quantum cryptography, lattice-based threshold signatures have gained attention as viable PQ-threshold solutions. Nevertheless, existing constructions are limited in terms of their scalability, robustness. Worse, none is compatible with standardized schemes, particularly with the NIST-selected and standardized Module-Lattice-based Digital Signature Algorithm (ML-DSA) algorithm. In this work, we present the first threshold signature scheme that is fully compatible with ML-DSA, supporting secure and efficient signing for a small number of parties, with an average communication per party upper bounded by 1 MB up to 6 parties. Our construction leverages advanced short secret sharing techniques and integrates optimized rejection sampling to achieve a favorable balance between communication efficiency and correctness in distributed environments. We implement our construction in Go and evaluate its performance across local, LAN, and WAN network settings. Our benchmarks demonstrate that our threshold ML-DSA scheme is not only practically deployable but also well-suited for real-world applications, including multi-device cryptocurrency wallets, threshold-based TLS authentication, and for Tor's directory authorities.

Hamming Quasi-Cyclic (HQC) was a candidate algorithm in the fourth round of the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) standardization process and was ultimately selected as a standardized cryptographic scheme in the latest round. To date, although HQC has been optimized for FPGA, CPU, and other platforms, research on GPU-based parallel acceleration remains significantly underexplored. Given this, our research aims to investigate the feasibility and efficiency of hand-optimized HQC implementations on GPU, addressing the current research gap in GPU-based implementations of code-based cryptographic algorithms. In this paper, we introduce a High-performance Implementation of GPU-based HQC, named HIGH. First, we propose a novel architecture for coding-based PQC implementations, significantly reducing redundant global memory access through core fusion. Second, we design a HIKD structure for HIGH, combining a high-order multiplication scheme (HIK) and a low-order multiplication scheme (HID), achieving an impressive 85.6\% improvement over Official fourth round Optimized Implementation. Third, through extensive experimentation, we sought the optimal HIKD combination and identified the optimal parallel parameters, leveraging these optimizations, HIGH surpasses current state-of-the-art benchmarks, with Key Generation, Encapsulation, and Decapsulation performance increased by 20$\times$, 32$\times$, and 39$\times$, respectively.

Secret sharing serves as a critical primitive for distributed systems; however, traditional protocols lack the adaptability required for dynamic environments with unpredictable participant turnover. While Dynamic-Committee Proactive Secret Sharing (DPSS) attempts to address this, existing synchronous solutions suffer from a critical vulnerability: they necessitate a multi-round hand-off phase that effectively imposes a "quiescent window." This requirement forces committee membership to remain static during transitions, directly contradicting the premise of a fully dynamic adversary. In this work, we propose a Fully Dynamic-Committee model that eliminates the quiescent window by supporting committee reconfiguration in every round. We present two primary contributions. First, we introduce a suite of three perfectly secure Fully Dynamic Verifiable Secret Sharing (FDVSS) schemes that support per-round committee reconfiguration. Among them, our main construction, FDVSS-1, achieves near-optimal round complexity (four rounds) and polynomial communication ($O(n^4)$). Second, building on FDVSS, we construct a perfectly secure Fully Dynamic-Committee Proactive Secret Sharing (FDPSS) protocol. FDPSS achieves share redistribution in a single communication round, removing "quiescent window" during the hand-off phase. Our protocols require no trusted setup and provide optimal resilience ($t < n/3$) against a Byzantine adversary, offering a robust solution for fault-tolerant distributed systems in highly dynamic networks.

Abuse reporting tools like message franking allow end-to-end encrypted (E2EE) messaging platforms to verify user-generated abuse reports as part of their platform content moderation policies. While the lightweight message franking protocol deployed by WhatsApp and Meta's Messenger is designed with the assumption that the moderator and the platform processing messages are the same entity, proposals for other message franking-style protocols allow for a separation between the platform and moderator, albeit at a higher cost. This paper introduces new techniques for third-party moderation on E2EE messaging platforms. First, we develop a simple scheme with near-optimal performance that matches the cost of the deployed scheme on the client side, and we demonstrate the inherent necessity of increased server-side costs. Next, we introduce new techniques that allow E2EE messaging platforms to work with multiple vetted moderators, giving users options in their choice of moderators for messages they send to their friends. Verifiable abuse reporting in a multi-moderator setting requires new security notions to capture deniability requirements with respect to the platform and other moderators, as well as new privacy requirements with respect to users' choices of moderator(s). We comprehensively study these requirements and propose protocols for verifiable abuse reporting in this setting, offering a range of security and performance tradeoffs for different deployment scenarios. We evaluate the performance of our proposed schemes, showing that in many cases they match or exceed the performance of prior schemes that only support a single moderator.

Lightweight keystream generators are widely used in resource-constrained digital systems, where implementation efficiency in area, power, and logic structure is a primary design concern. Conventional designs predominantly employ shift-register-based state propagation, in which diffusion is inherently coupled with sequential data movement. This work investigates an alternative architectural approach in which state mixing is achieved through sparse interaction among state variables, enabling a decoupling between diffusion and register propagation. We present \emph{SIR}, a sparse-interaction keystream generator with a 128-bit internal state composed of a nonlinear 64-bit primary state and a 64-bit auxiliary linear state. The primary state is updated using a compact four-input Boolean function applied over a fixed sparse neighbourhood, while the auxiliary state provides lightweight round-dependent perturbation. This structure realizes diffusion through parallel combinational interaction, leading to a distinct hardware profile characterized by reduced reliance on sequential storage and increased distributed logic. The architectural behaviour is evaluated through diffusion and statistical experiments, showing rapid propagation of local perturbations across the state within 14--15 rounds and no observable low-order dependence between internal state variables and output in the tested regime. Hardware implementation on a Xilinx Artix-7 FPGA requires 183 LUTs and 177 flip-flops, while ASIC synthesis using a 45\,nm standard-cell library results in an area of 3079 gate equivalents. Comparative evaluation with Grain-128, Trivium, and Espresso under identical implementation conditions demonstrates that the proposed architecture provides a competitive trade-off between combinational logic and sequential resources. The results indicate that sparse-interaction-based state evolution constitutes a viable architectural alternative for lightweight keystream generation, particularly in hardware-oriented and FPGA-based design settings.

A keyword $\mathbf{s}$ is a subsequence of a text $\mathbf{t}$ if $\mathbf{s}$ can be obtained by deleting some characters from $\mathbf{t}$; otherwise, $\mathbf{s}$ is a non-subsequence of $\mathbf{t}$. (Non-)subsequence relationships arise in various fields, including genetic analysis, blockchains, and natural language processing. Recently, Ling et al. (SCN 2024) proposed a succinct argument for non-subsequences based on multivariate sumcheck (Lund et al., FOCS 1990) whose prover's running time is at least $\mathcal{O}(n + N + |\Sigma|)$, where $n$ and $N$ are respectively the lengths of strings $\mathbf{s}$ and $\mathbf{t}$, and $\Sigma$ is the alphabet over which $\mathbf{s}$ and $\mathbf{t}$ are defined. As shown in their work, proving non-subsequence relationships is non-trivial since one needs to decompose such an argument into smaller components for sumcheck, permutation, and lookup. We propose a subsequence scheme that separates proving (non-)subsequences into the following two phases: (i) a preprocessing phase and (ii) a (non-)subsequence proving phase, assuming $n \ll N$ (i.e., $|\mathbf{s}| \ll |\mathbf{t}|$). Specifically, we can generate a one-time preprocessing proof with inputs $\mathbf{t}$ and $\Sigma$, without any knowledge of $\mathbf{s}$. When $\mathbf{s}$ is known, we can determine whether $\mathbf{s}$ is a subsequence of $\mathbf{t}$ and prove the corresponding statement. Employing cached quotients (IACR ePrint 2022/1763), we achieve a running time quasi-linear in $N + |\Sigma|$ for preprocessing, while the running time of proving a (non-)subsequence relationship is $\mathcal{O}(n \log_2 (N + |\Sigma|))$ for each query $\mathbf{s}$. Since $n \ll N$ and $\log_2(N + |\Sigma|)$ grows sub-linearly with the text size, this saves the prover's running time, assuming a preprocessing depending only on $\mathbf{t}$ is computed in advance. Hence, we achieve a \textit{text-sub-linear} proving time.

We present a deterministic framework for navigating $p$-isogeny graphs of genus $g \ge 2$, addressing the lack of canonical and auditable primitives in higher dimensions. The framework integrates two components: the Certified $p$-Isogeny Step (PICS) and a Non-Decomposition Certificate (ND). PICS constructs the unique Frobenius-compatible inseparable isogeny by extracting kernel directions from Hasse--Witt invariants and differential subresultant profiles, thereby eliminating randomized kernel selection. Complementarily, ND serves as an algebraic filter that rejects Jacobians compatible with product decompositions by enforcing cyclicity in the associated differential operator module. We prove that the rejection density scales asymptotically as $O(p^{-1})$. Experimental validation using a C-based backend over 256-bit prime fields demonstrates that the certification logic incurs a relative overhead of less than $0.2\%$ compared to the mandatory Hasse--Witt computation. By enforcing strict determinism and structural safety, the resulting transition unit provides a verifiable primitive for auditable parameter generation and isogeny-based time-lock puzzles.

We revisit the question of whether it is possible to build succinct non-interactive arguments ($\mathsf{SNARG}$s) for all of $\mathsf{NP}$ under standard assumptions using non-signaling probabilistically checkable proofs [Kalai-Raz-Rothblum, STOC' 14]. In particular, we observe that using exponential-length PCPs appears to circumvent all of the existing barriers. For our main result, we give a candidate non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ and prove its soundness under: - the learning with errors assumption (or other standard assumptions such as bilinear maps), and - a mathematical conjecture about multivariate polynomials over the reals. In more detail, our conjecture is an upper bound on the minimum total coefficient size of Nullstellensatz proofs (Potechin-Zhang, ICALP 2024) of membership in a concrete polynomial ideal. We emphasize that this is not a cryptographic assumption or any form of computational hardness assumption. Of particular interest is the fact that our security analysis makes non-black-box use of the $\mathsf{SNARG}$ adversary, circumventing the black-box barrier of Gentry and Wichs (STOC '11). This gives a blueprint for constructing $\mathsf{SNARG}$s for $\mathsf{NP}$ that is not subject to the Gentry-Wichs barrier.

We show that a simple eavesdropper listening in on classical communication between potentially entangled quantum parties will eventually be able to impersonate any of the parties. Furthermore, the attack is efficient if one-way puzzles do not exist. As a direct consequence, one-way puzzles are implied by reusable authentication schemes over classical channels with quantum pre-shared secrets that are potentially evolving. As an additional application, we show that any quantum money scheme that can be verified through only classical queries to any oracle cannot be information-theoretically secure. This significantly generalizes the prior work by Ananth, Hu, and Yuen (ASIACRYPT'23) where they showed the same but only for the specific case of random oracles. Therefore, verifying black-box constructions of quantum money inherently requires coherently evaluating the underlying cryptographic tools, which may be difficult for near-term quantum devices.

Among the countermeasures against side-channel analysis attacks, masking offers formal security guarantees and composability, yet remains challenging to implement efficiently in hardware due to physical defaults like glitches and transitions. Low-latency masking techniques aim to mitigate the performance penalties but can inadvertently compromise security in certain architectural contexts. In particular, the recently proposed Time Sharing Masking (TSM) technique enables single-cycle masked implementations with composability under the SNI and PINI notions but fails to satisfy stronger composability guarantees required in iterative designs, i.e., OPINI. In this work, we show that TSM-based constructions can exhibit first-order leakage when used in single-register feedback architecture, such as round-based implementations of ciphers. To address this, we propose two new masking schemes: TSM+, a more efficient variant of TSM satisfying only PINI (but not SNI), and OTSM, a construction satisfying OPINI, enabling secure round-based designs. Our improved round-based masked implementations of PRINCE and AES ensure security in latency-critical applications under both glitch- and transition-extended probing model while demanding for slightly more area consumption.

Batch arguments (BARGs) are non-interactive arguments for conjunctions of NP statements, with proof size that is sublinear in the number of statements. Several previous works studied the communication complexity of BARGs, focusing both on the CRS size and on the additive overhead of the proof, defined as the difference between the proof size and the size $m$ of a single NP witness: - Devadas et al.~[FOCS 22] constructed BARGs with additive overhead that is independent of $m$, however, their CRS size is polynomial in $m$. - Paneth and Pass [FOCS 22] constructed BARGs where the CRS size is independent of $m$, but with higher additive overhead $m^{1-\epsilon}$. Under the hardness of LWE, we construct BARGs where both the CRS size the additive overhead of the proof are independent of $m$. Such BARGs can be recursively composed an unbounded polynomial number of times without losing succinctness. Along the way, we also considerably simplify the construction of fully local somewhere extractable hash functions used in the construction of Devadas et al.

We study the design of Oblivious RAMs (ORAMs) that allow a client to access memory outsourced to a remote, untrusted server without revealing the client’s data access pattern. We are interested in concretely efficient constructions and prior works have yielded different ORAM frameworks with various trade-offs. Tree-based constructions such as RingORAM [Ren et al., USENIX’15] obtain low communication overhead, but require client storage of linear position maps and two roundtrip queries. Hierarchical schemes such as FutORAMa [Asharov et al., CCS’23] further reduce communication at the cost of more roundtrips during queries. Finally, SQRT-ORAM [Goldreich, STOC ’87] enables fast queries of one roundtrip and one block of communication at the cost of larger amortized communication costs. We present two new constructions, LatORAM and Lat 2 ORAM, that simultaneously obtain the positive traits of all three types of ORAM constructions. Online queries are blazing fast with one roundtrip and a single block of communication like SQRT-ORAM. Fixing the client memory sizes for comparison, the online communication cost of our constructions are 5-8x smaller than RingORAM and 5-10x smaller than FutORAMa even though both RingORAM and FutORAM a require multiple roundtrips per online query. Furthermore, our total amortized communication is also up to 50% smaller. To obtain our constructions, we present a new lazy approach of lateral stash growth that delays large shuffles. Of independent interest, we present improved oblivious merging schemes for specific settings important for our ORAMs. Our constructions solely rely on symmetric cryptography.

We study a new pairing, beyond the Weil and Tate pairing. The Weil pairing is a non-degenerate pairing $E[m] \times E[m] \to \mu_{m}$, which operates on the kernel of $[m]$. Similarly, when $\mu_{m} \subseteq \mathbb{F}_q^*$, the Tate pairing is a non-degenerate pairing $E[m](\mathbb{F}_q) \times E(\mathbb{F}_q) / [m]E(\mathbb{F}_q) \to \mu_{m}$, which connects the kernel and the rational cokernel of $[m]$. We define a pairing \[ \langle{\quad}\rangle_m : E(\mathbb{F}_q) / [m]E(\mathbb{F}_q) \times E(\mathbb{F}_q) / [m]E(\mathbb{F}_q) \to \mu_{m}\] on the rational cokernels of $[m]$, filling the gap left by the Weil and Tate pairing. When $E[m] \subseteq E(\mathbb{F}_q)$, this pairing is non-degenerate, and can be computed using three Tate pairings, and two discrete logarithms in $\mu_{m}$, assuming a basis for $E[m]$. For $m = \ell$ prime, this pairing allows us to study $E(\mathbb{F}_q) / [\ell]E(\mathbb{F}_q)$ directly and to simplify the computation for a basis of $E[\ell^k]$, and more generally the Sylow $\ell$-torsion. This finds natural applications in isogeny-based cryptography when computing $\ell^k$-isogenies.