Keyword private information retrieval (Keyword PIR) enables a client to retrieve the value associated with a keyword from a database while keeping the queried keyword private, thereby generalizing traditional private information retrieval, known as index PIR. The state-of-the-art by Hao et al. (USENIX 2025) has several limitations. First, their generic construction requires three invocations of an underlying index-PIR protocol. Second, to reduce this overhead, they propose a specialized design combining SimplePIR with hash tables. However, this approach inherits SimplePIR's large client-side hint, resulting in substantial per-database storage costs on the client side. Moreover, it allows clients to retrieve information beyond the value associated with the queried keyword. In this work, we present a novel and practical Keyword PIR framework that addresses these limitations. Our construction extends the hintless KsPIR scheme of Luo et al. (CCS 2024) to the keyword setting, ensuring that a semi-honest client retrieves only the value corresponding to the queried keyword. The construction leverages the linear homomorphic technique of Peikert and Pepin (TCC 2025). To accelerate homomorphic evaluation, we design a baby-step giant-step (BSGS) implementation and an offline/online decomposition based on a Galois-theoretic formulation. Experimental results show a mean online speedup of $2.65\times$ over the generic framework when instantiated with the same index-PIR scheme, for databases containing up to $2^{22}$ entries.

Anonymous communication systems aim to hide which user sent which message, but existing designs sit at two extremes: efficient, centralized mixnets that rely on at least one honest mix server, and fully decentralized protocols such as DC-nets and MPC-based shuffles that avoid trusted mixers at the cost of high communication and fragility under disruption. This paper introduces \emph{verifiable self-mix} (VSM), a new anonymity architecture for privately shuffling messages posted on a public bulletin board. In VSM, users \emph{self-mix} their encrypted messages by writing them to secret locations in a public table. A preprocessing protocol, \emph{Unique Number Selection} (UNS), assigns every user a distinct hidden mix location; an anonymization protocol, \emph{Secure Mapping of Private Permutation} (SMPP), ensures that each such location contains exactly that user's ciphertext, without revealing the mapping from users to locations. Because each user learns their own final location, VSM provides \emph{unconditional individual verifiability}: after an optional decryption step, users can check that their message appears at the correct slot without running any cryptographic checks. We formally define VSM and prove anonymity, integrity, and self-verifiability in the malicious model. We then present several concrete instantiations. Our UNS protocols rely on either trusted hardware or multiple servers running plaintext-equivalence tests and require only constant private memory, making them suitable for constrained trusted execution environments. Our SMPP constructions allow trade-offs between trust and bandwidth, achieving $O(n)$ ciphertext uploads per user (or $O(\log n)$ in theory under FHE, at substantial setup cost), while avoiding the pairwise shared-pad state and interactive disruption-resolution typical of classic DC-net designs.

—Internet-of-Things (IoT) nodes must protect sensed data while operating with limited processing capability, memory, and battery capacity. In August 2025, the National Institute of Standards and Technology (NIST) finalized SP 800-232, which standardizes the Ascon family for constrained devices. This paper presents ASCON-Edge, a reproducible protocol for evaluating the security, performance, memory cost, and directly measured energy cost of standardized Ascon-AEAD128 on resource-constrained IoT nodes. The protocol compares Ascon-AEAD128 with AES 128-GCM and ChaCha20-Poly1305 using identical message sizes, associated data, timing boundaries, build conditions, and security tests. It defines a deterministic workload, a nonce uniqueness and replay policy, a hardware-freeze record, raw-data fields, statistical summaries, direct-energy rules, and functional acceptance criteria. It also separates AEAD guarantees from application-layer responsibilities for replay prevention and key handling. A targeted literature synthesis motivates a final-standard, workload-aware comparison protocol. This is a methodology and reproducibility paper: it reports deterministic packet-format overhead, but deliberately does not claim hardware benchmark measurements before a frozen platform and raw data are available.

Neural networks based machine learning models are used in many classification problems yet privacy issues in model usage are mostly unresolved. When a model owner provides their model to other parties for inference, either the model owner has to share the parameters of the model or the model user must share their query and result with the model owner. Depending on the usage scenario, the user’s query or query result could contain sensitive information that the model provider should not see. And on the other hand, the model parameters themselves could be a valuable business secret or leak private training data. In such cases, neural network inference must be performed in a privacy preserving manner, for example, using secure multi-party computation (MPC). We propose protocols for the private inference of neural networks and evaluate them within the Sharemind MPC secure computation framework. Our protocols are based on the per-tensor quantisation scheme in PyTorch which maps floating point model parameters to 8-bit integer values. Quantisation improves the efficiency of our protocols and our protocols are interoperable with models trained using PyTorch. We extend constant round integer convolution and matrix multiplication protocols for quantised model weights, propose constant round protocols for re-quantising values and analyse the optimal secret share bit width for efficient re-quantisation. The resulting protocols are used to evaluate the VGG16 image classification network with an amortised throughput of 24.3 s per image classification in a LAN setting.

In a social key recovery scheme, users back up their secret keys (typically using Shamir's secret sharing) with their social connections, known as a set of guardians. This places a heavy burden on the guardians, as they must manage their shares both securely and reliably. Finding and managing such a set of guardians may not be easy, especially when the consequences of losing a key are significant. We take an alternative approach of social recovery within a community, where each member already holds a secret key (with possibly an associated public key) and uses other community members as their guardians forming a mutual dependency among themselves. Potentially, each member acts as a guardian for upto $(n-1)$ other community members. Therefore, in this setting, using standard Shamir's sharing leads to a linear ($O(n)$) blow-up in the internal secret storage of the guardian for each key recovery. Our solution avoids this linear blowup in internal secret storage by relying on a novel secret-sharing scheme, leveraging the fact that each member already manages a secret key. In fact, our scheme does not require guardians to store anything beyond their own secret keys. We propose the first formal definition of a social key recovery scheme for general access structures in the community setting. We prove that our scheme is secure against any malicious and adaptive adversary that may corrupt up to $t$ parties. As a main technical tool, we use a new notion of secret sharing, that enables $(t+1)$ out of $n$ sharing of a secret even when the shares are generated independently -- we formalize this as bottom-up secret sharing (BUSS), which may be of independent interest. Finally, we provide an implementation benchmarking varying the number of guardians both in a regional, and geo-distributed setting. For instance, for 8 guardians, our backup protocol takes around 146-149 ms in a geo-distributed WAN setting, and 4.9-5.9 ms in the LAN setting; for recovery protocol, the timings are approximately the same for the WAN setting (as network latency dominates), and 1.2-1.4 ms for the LAN setting.

This paper presents a pairing-based non-interactive batch argument (BARG) for NP in the common reference string (CRS) model with constant-size proofs and constant-cost verification. Our construction is fully black-box in its use of the underlying group and achieves a weak form of somewhere extractability under a new $q$-type assumption in composite-order pairing groups. We further show that this extractability guarantee implies somewhere soundness. Prior pairing-based BARGs in this setting suffer from proof size and verification cost proportional to the size of the Boolean circuit computing the NP relation, and our work removes this dependence. Technically, our starting point is the Waters--Wu framework [Asiacrypt'25] and the main idea is to replace the univariate polynomial commitment with a bivariate polynomial commitment together with univariate sumcheck arguments. This allows us to compress both wire and gate checks into a constant number of algebraic identities, leading to constant-size proofs and constant-cost verification. As a demonstration of the resulting somewhere-sound BARG, we show that it simplifies and improves existing generic constructions of NIZKs and rate-1 BARGs. In particular, we obtain: -a generic construction of NIZKs for NP from our somewhere-sound BARG, together with a one-time dual-mode commitment scheme with extraction and a leakage-resilient weak pseudorandom function. The resulting proof size is independent of the circuit size, whereas prior work incurs circuit-size-dependent proof overhead and either requires a local PRG or commits to all internal wires; -a generic construction of rate-1 BARGs from pairing-based assumptions by combining the somewhere sound BARG obtained from our construction with existing rate-1 fully local somewhere-extractable hashing. The resulting proof size is $h+\mathsf{poly}(\lambda,\log\ell)$, whereas prior work either requires proof size $h+o(h)\mathsf{poly}(\lambda,\log\ell)$ or relies on a RAM SNARG with partial-input soundness. Both generic constructions rely on weaker or fewer cryptographic primitives than prior work and the construction of NIZK also avoids the complicated parameter selection in prior work.

A proof of solvency (or proof of reserves) is a zero-knowledge proof produced by a centralized cryptocurrency exchange to demonstrate that it holds enough cryptocurrency to cover all customer balances, while revealing nothing beyond solvency itself. A key challenge in building practical end-to-end proofs of solvency is the cryptographic mismatch between asset keys and modern succinct non-interactive arguments of knowledge (SNARKs): many deployed account-based cryptocurrency systems use secp256k1, whereas efficient SNARKs are built over pairing-friendly curves such as bls12-381. Bridging these two settings is therefore necessary for any private end-to-end construction. We introduce Xiezhi, an end-to-end proof of solvency protocol that avoids directly translating keys across curves (which is expensive) and instead transfers asset-ownership claims into the SNARK-friendly setting with much lower proving overhead. A Rust prototype over bls12-381 shows that the reusable key-ownership phase remains practical for real-world exchanges, while the recurring asset proof has constant-size proofs and constant-time verification. For liabilities, the column-wise range proof scales linearly in proving time but keeps proof size and auditor verification independent of the number of users for fixed precision; with 32-bit balances, proofs are below 10 KB and verify in under 8 ms. These results indicate that Xiezhi offers practical end-to-end private proofs of solvency with substantially lower proving overhead than prior circuit-based end-to-end approaches.

Bitcoin's proof-of-work (PoW)-based protocol is remarkable for how little it asks of its participants. Not only can miners take breaks from work whenever they please, but it is almost unique in offering a path of contrition: corrupt miners can reclaim honest status simply by resuming mining on the longest chain. The protocol only requires that honest miners hold the majority of computational power at any given time. Analogous proof-of-stake (PoS) protocols, usually formalized via the sleepy model of Pass and Shi (2017), have fallen short of matching this robustness. In fact, sleepy consensus protocols in the plain PKI model must heavily restrict fluctuations in adversarial participation over time. The recent work of Efron, Neu, Pitassi (2025) enables fully fluctuating participation in the sleepy model by introducing the external adversary model. Their protocol, however, relies on verifiable delay functions (VDFs), a strong cryptographic primitive that somewhat resembles PoW, by assuming that the adversary cannot compute sequential work significantly faster than honest nodes. In this work, we design a sleepy consensus protocol for fully fluctuating participation with an external adversary under an honest majority, from minimal assumptions: a public key infrastructure (PKI) and a verifiable random function (VRF). In particular, we make no VDF or hardware assumptions. Our key technique is graded wakeness, a novel primitive that allows nodes to form consistent opinions on which other nodes are awake. We further extend our protocol to handle uncorruption, where corrupt nodes return to honesty. This extension requires only a mild additional assumption on the unpredictability of VRF outputs for liveness.

The Domain Name System (DNS) was conceived with reliability, speed, and scalability in mind, with limited consideration for privacy. Different solutions have been proposed to make DNS more privacy preserving, mostly focusing on confidentiality in transit and networking approaches to achieve unlinkability. However, DNS queries are still observable in plaintext during processing. In this work, we investigate how to achieve privacy against all involved servers through private DNS lookups via single-server private information retrieval (PIR). For this, we design a new PIR protocol that is optimized for the DNS setting. In addition to using ideas from NTTlessPIR (Li et al., CRYPTO 2024), we design a new algorithm to efficiently perform RLWE-based matrix-vector multiplication. As opposed to previous methods, it does not require NTT-friendly plaintext moduli, uses only a single key-switching key, and causes significantly lower noise growth. For a single database of 2 billion entries (the estimated number of domains in the world), our protocol allows clients to perform PIR queries with about 80KB of communication, and less than 5 seconds of server computation time. This outperforms all previous PIR schemes in terms of communication cost, at only slightly increased runtime. Additionally, our end-to-end evaluation of iterative DNS resolution across three nameservers shows sub-second lookups in smaller settings and under 5 seconds with 264KB communication for querying .com domains, which can be practical when used selectively for privacy-sensitive web browsing activities.

Vector oblivious linear evaluation (VOLE) is a type of correlation that is widely used in multiparty computation (MPC) and zero-knowledge (ZK) proofs. Recently, the generation of VOLE correlation has become very efficient due to the pseudorandom correlation generator (PCGs) paradigm (Boyle et al. CCS 2018) and SoftSpokenOT (Roy Crypto 2022). This has driven a line of research on VOLE-based ZK, which enjoys linear prover time, low memory cost and post-quantum security. However, most existing works build VOLE and VOLE-based ZK over finite fields, whereas the constructions over integer rings are less satisfactory, especially in terms of communication and public verifiability. In this work, we address some of these problems using a newly introduced primitive called subring VOLE (srVOLE), which is a generalization of subfield VOLE to Galois rings. Specifically, (1) We propose two maliciously secure srVOLE protocols. One is a PCG-like protocol that achieves extremely low amortized communication. The other is a SoftSpoken-like protocol, which is compatible with the VOLE-in-the-head (VOLEitH) technique and thus can be used to construct publicly verifiable VOLE-based ZK. (2) We find that the VOLE correlation over $\mathbb{Z}_{2^k}$ used in Moz$\mathbb{Z}_{2^k}$arella (Baum et al. Crypto 2022) is a special case of our srVOLE. Therefore, based on our construction, their designated-verifier ZK protocol can be made publicly verifiable. (3) We adapt the QuickSilver (Yang et al. CCS 2021) protocols to any Galois ring and compare with existing VOLE-based ZK protocols over rings. For circuit satisfiability, our protocol only communicates 1 subring element per multiplication gate, reducing the communication by more than half. For polynomial satisfiability, our protocol supports arbitrary low-degree relations, overcoming the restrictions of existing work on degree-2 relations.

This work studies asynchronous verifiable secret sharing (AVSS) and asynchronous multi-party computation (AMPC) in the blockchain-hybrid model, where parties have black-box access to an ideal (asynchronous) blockchain functionality providing only persistence and eventual liveness. Motivated by the practical deployment of MPC in blockchain applications such as privacy-preserving payments and threshold wallets, we investigate whether blockchain access can improve the classical resilience bound of $n > 3t$, where $n$ is the total number of parties, and $t$ is the number of parties that can be compromised by an adversary. In particular, in the blockchain-hybrid model, we provide a comprehensive set of lower and upper bounds across three cryptographic settings: (i) no trusted setup, (ii) trusted setup with Minicrypt assumptions, (iii) trusted setup with public-key assumptions. 1. We show that without a trusted setup, or under Minicrypt assumptions, even with a setup, the classical resilience bound for AMPC is inherent: AMPC is impossible for $n \leq 3t$, even against weaker fail-stop or omission adversaries. 2. We establish separations between AVSS and AMPC in the intermediate regime $2t < n \leq 3t$: against a fail-stop adversary, unlike AMPC, AVSS is possible for $n>2t$ without any setup. Moreover, against a Byzantine adversary, again unlike AMPC, AVSS is possible for $n>2t$ under Minicrypt assumptions with a setup. 3. In contrast, under public-key assumptions with trusted setup, we construct an AMPC protocol tolerating Byzantine adversaries whenever $n>2t$. Our protocol leverages threshold homomorphic encryption, threshold signatures, commitments, and zero-knowledge proofs to minimize on-chain communication, achieving blockchain communication complexity independent of the circuit size. In the process, we define an efficient agreement on a common subset primitive for large messages in the blockchain-hybrid model, which can be of independent interest for secure distributed computing systems.

Quantum computers threaten the elliptic-curve signatures used by Bitcoin and Ethereum once a public key appears on-chain. Hidden-key credentials, including those controlling Bitcoin P2PKH/P2WPKH outputs and unused Ethereum EOAs, have a different risk profile: their public keys are hidden behind hash-derived addresses, but classical spending reveals them. We propose a migration design that separates revealed-key and hidden-key credentials. Revealed-key credentials may use hybrid classical/post-quantum authorization only while the legacy signing secret remains uncompromised; after quantum recovery of that secret, an independent rescue policy or pre-committed recovery credential is required to distinguish the owner from an attacker. Hidden-key credentials use STARK-verifiable ownership relations that bind a legacy identifier to a commitment to a post-quantum public key without explicitly publishing the legacy elliptic-curve public key as a public value. Complete enrollment opens the commitment and verifies post-quantum key possession. The design adds one-way migration-registry semantics, quantum hash-security analysis, scenario-based network-capacity evaluation, and an SP1-based prototype. We distinguish Groth16/PLONK wrapping, which is only a current-EVM compatibility path, from an intended quantum-era transparent verification path; the exact post-quantum security of a concrete SP1 deployment depends on the pinned SP1 version, proof mode, and all cryptographic subarguments used by that configuration.

Folding schemes compress many instances of a relation into a single accumulated one and, via composition with the Fiat-Shamir heuristic, yield SNARKs for arbitrarily large computations. However, essentially every folding scheme beyond Nova itself (including the lattice-based SuperNeo [NS26], LatticeFold(+) [BC24,BC25], and Cyclo [GLLO26]) is only randomizing, not blinding (i.e. honest-verifier zero-knowledge): its folding transcript leaks information about the witnesses being folded. We present LatticeBlindFold, a first lattice-based, plausibly post-quantum-secure analogue of the NovaBlindFold protocol [KS23,KS25], obtained by making SuperNeo blinding. This is a first step, intended to establish feasibility; for simplicity we restrict to the interactive setting. We also hope the note serves as a record of the difficulties one encounters in achieving zero-knowledge for lattice-based folding schemes. Our central technical device is the ABDLOP commitment scheme [BDL+16,LNP22], used as a commit-and-prove backbone. We mask SuperNeo's Sum-Check transcript via Libra-style polynomial masking, replace its plaintext evaluation hints with ABDLOP commitments checked homomorphically, and employ rejection sampling so that the randomized folded instance-witness pair, salts included, is simulatable. Since ABDLOP is only known to be secure over the base ring R_F and not over the extension ring R_K that SuperNeo's Sum-Check runs over, we give a component-wise instantiation of ABDLOP over R_K, translating every relation into a pair of R_F-relations once, at the level of public parameters. The resulting protocol is complete, knowledge-sound, and blinding (when a single fresh R1CS instance is folded), with security reducing to Module-SIS/Module-LWE assumptions over cyclotomic rings (together with the Extended-MLWE variant of [LNS20]). Completeness moves from perfect completeness to a statistical one, due to the introduction of rejection sampling. The price of blinding is paid through the parameters rather than the asymptotics. Rejection sampling forces a norm-decomposition depth k = Θ(log n_F), whereas SuperNeo needs only k = Θ(1). We record as a corollary an accumulator-free variant, dropping the prover-sampled blinding pairs that the main protocol carries for interface compatibility with SuperNeo's folding step, which saves a few decomposition digits (k = 26 rather than 31 at our parameters) at no cost in blinding. At a matched k the two schemes agree in prover time, verifier time, and communication up to constant factors, but measured against SuperNeo at its native parameters LatticeBlindFold carries a Θ(log n_F) multiplicative overhead in all three. Once again, all security figures we quote are interactive; a Fiat-Shamir transform instantiation would require a higher degree fields while here we focus on degree 2 for simplicity of exposition. LatticeBlindFold inherits SuperNeo's compatibility with small-field arithmetic and offers a modular, plausibly post-quantum-safe route to introducing zero-knowledge on top of a SNARK. We stress the shape of what we prove here: the LatticeBlindFold step is a single interactive step, taking its input uncommitted and outputting k committed evaluation claims together with the ABDLOP openings certifying them. Turning it into a deployable wrapper requires a decider for those claims, whether by having a downstream verifier consume them directly or by arithmetizing the ABDLOP verification; we do not construct one here, and neither recursive composition nor the instance-in/instance-out folding interface is claimed. This work is directly motivated by the Jolt Atlas zkML framework [BCDG26].

Digital identity systems are becoming increasingly prevalent, driven by regulatory efforts such as the European Digital Identity (EUDI) Wallet. Yet these systems usually do not achieve strong privacy guarantees as offered by anonymous credentials, since they rely on standardized curves and widespread signature schemes like ECDSA that are incompatible with pairing-based primitives underpinning most anonymous credential constructions. Recent work bridges this gap by retrofitting such legacy credentials with anonymous-credential properties via zero-knowledge proofs, requiring no issuer-side modifications. However, none of these constructions supports delegation: the ability for users to pass on a restricted credential derived from their own to another party, while all parties along the delegation chain maintain full anonymity. Delegatable anonymous credentials (DACs) provide exactly these guarantees, but are likewise incompatible with existing deployments. We present the first DAC scheme built directly on top of legacy credentials. Our construction requires no issuance infrastructure changes, and yields constant-size credentials independent of delegation depth, with full unlinkability along the chain and selective attribute disclosure at every level. We instantiate it for credentials based on JSON Web Tokens (JWTs) signed with ECDSA using Plonky2 as the recursive proving backend, contributing a secure in-circuit JWT parser that closes vulnerabilities in prior work and a Plonky2 extension for cyclic recursion with per-step zero-knowledge. At 64 attributes, delegation takes 1.2 s and verification only 3.3 ms, with a constant proof size across all delegation levels

NTRU-based encryption enjoys compact keys and ciphertexts and admits non-interactive distributed decryption, making it an attractive basis for threshold encryption with applications to threshold FHE, threshold signatures, and electronic voting. All known protocols, however, assume a secret key shared by a trusted dealer. The public NTRU key $h = f^{-1}g$ is a nonlinear function of the secret, so distributed key generation (DKG) techniques for LWE-based schemes do not apply, and generic MPC is prohibitively expensive. We present the first dedicated DKG protocol for NTRU. Each party publishes an NTRU sample, defining a joint public key whose secret key is shared multiplicatively, and a multiplicative-to-additive (MtA) conversion yields the additive sharing required for non-interactive decryption. The protocol runs in few rounds and is actively secure with abort. At the heart of our DKG lies the MtA conversion, for which we give two efficient lattice-based certified constructions; one from additively homomorphic NTRU encryption and one from homomorphic secret sharing, both of which may be of independent interest. We demonstrate the protocol by building a threshold variant of NTRU-Encrypt, which we prove secure and instantiate with concrete parameters.

Cryptographic protocols are the foundation of secure digital communication, yet their design remains error-prone, as evidenced by the vulnerabilities that have plagued even the most widely adopted protocols throughout history. Security properties are typically formalized using either trace properties or indistinguishability, each addressing distinct security guarantees, such as agreement and authenticity for the former and anonymity and strong secrecy for the latter. Formal verification of cryptographic protocols spans both symbolic and computational models. While symbolic techniques enable automation and scalability, they do not provide computational security guarantees. Computational models, though robust, are harder to formalize and automate. Recent advances, such as the Computationally Complete Symbolic Attacker (CCSA) model and its logic, the Bana-Comon Logic (BC Logic), bridge this gap by supporting both trace properties and indistinguishability. However, despite significant progress in proof assistants, automating indistinguishability remains a challenge due to its combination of unstructured equality theories, complex non-classical calculus, and partially inductive reasoning—all requiring expert knowledge in both cryptography and logic. This paper introduces a novel approach to automate indistinguishability proofs in the CCSA model, implemented in the automated prover CryptoVampire2. We extend CryptoVampire to support indistinguishability by designing golgge, a Prolog-inspired backtracking engine over equality graphs (e-graphs), which provides strong, rewrite-driven equational reasoning capabilities. We adapt the BC Logic rules to this new framework, yielding semantically compatible statements. The effectiveness of our approach is demonstrated by automating all indistinguishability goals in the Squirrel repository.

Hybrid signatures are a practical approach to post-quantum migration, but their security analysis becomes subtle when two Fiat-Shamir (FS) components are binded through a single shared challenge. This paper presents the first machine-checked proof of EUF-CMA security for the FS-FS hybrid construction of Bindel and Hale (2023) formalised in EasyCrypt in the Random Oracle Model (ROM). The proof is parametrised over abstract component interfaces and establishes the intended either-component security guarantee: for either choice of component, a hybrid forgery can be reduced to an EUF-CMA forgery against that component, together with the collision resistance of the message digest and a random-oracle guessing term. In this ROM formulation, the proof does not require an independent second-preimage-resistance assumption for the challenge hash. The mechanisation makes explicit two proof obligations arising from the hybrid structure and the abstract digest: an invariant linking the lazy-oracle state to an explicit query log at the verification point, and a module-restriction framing argument for the digest-collision reduction. We further machine-check honest-signing correctness for a concrete Schnorr-Schnorr instantiation and instantiate the abstract security proof with a Schnorr-Okamoto component pair without changing the core game-hopping argument. The formalisation thereby makes explicit the assumptions, invariants, and composition structure underlying the security argument for the FS-FS hybrid.

Supporting privacy-preserving analytics across large Internet of Things (IoT) populations remains difficult. Resource-constrained devices may be unable to execute expensive multi-party computation (MPC) preprocessing or remain in a sustained many-party online protocol. We present a remotely attested, trusted execution environment (TEE)-assisted authenticated MPC multiplication scheme for large-scale edge intelligence. The TEE is deliberately restricted to the offline phase: before task-time compute committees are selected according to current edge availability and resource conditions, an Intel Software Guard Extensions (SGX) enclave provisions fine-grained authenticated material to authorized edge devices and then leaves the computation path. When a task arrives, a smaller set of $m<n$ compute committees aggregates the delegated device shares, the input owners inject their private data and model parameters through preprocessed masks, and the committees perform authenticated online multiplication without re-entering the TEE. We establish the correctness and authentication invariants of the committee-level computation and analyze the remotely attested deployment under an explicit TEE trust assumption. A hardware-SGX prototype implements the integrated scheme. The prototype generates batches of 10 million triples; at $l=1$ million in the evaluated three-recipient configuration, it achieves a $12.17\times$ preprocessing speedup over the evaluated MP-SPDZ MASCOT baseline. A separate stress test packages one preprocessing row for 100,000 recipients, and integrated tests reject ciphertext and online message-authentication-code (MAC) tampering. These results show that our scheme substantially improves preprocessing performance over the evaluated software-only protocol and is well suited to resource-constrained edge-intelligence deployments, underscoring its strong practical utility.

Threshold secret sharing schemes (TSSS) enable a dealer to distribute a secret among multiple participants such that only authorized subsets can reconstruct the secret while unauthorized subsets obtain no information. Existing secret sharing schemes (SSS) are often constrained by limited secret size, non-threshold access structures, or the absence of mechanisms for verifying the authenticity of shares and the integrity of the reconstructed secret. In this paper, we propose a novel $(k,n)$-threshold secret sharing scheme based on linear Maximum Distance Separable (MDS) codes. The proposed construction supports the sharing of comparatively larger secrets by representing the secret as a matrix over a finite field and exploits the linearity of MDS codes to achieve efficient share generation and reconstruction. To strengthen reliability, the scheme incorporates cryptographic hash functions for share authentication and integrity verification of the reconstructed secret. We prove that the proposed scheme satisfies correctness and perfect secrecy, thereby providing unconditional security against unauthorized coalitions. Experimental evaluation demonstrates that the proposed construction achieves efficient share generation and reconstruction while outperforming existing code-based secret sharing schemes in terms of supported secret size, scalability, and practical runtime.

Open-weight models allow clients to run LLMs locally, thus keeping their data private from untrusted providers. However, running large models requires massive hardware and storage resources (especially challenging on resource-constrained devices like smartphones), limiting local execution to smaller models. This leaves clients with a frustrating compromise: settle for a less-capable model that can be run locally, or sacrifice privacy by sending queries to an external server. We present an efficient protocol that allows a client to privately and verifiably outsource LLM inference of an open-weight model to a pair of malicious (but non-colluding) servers. Privacy implies that neither server learns anything about the client's queries. At the same time, the client can verify the claimed result using information posted by the model owner along with the model weights. Compared to prior state-of-the-art for private LLM inference (SIGMA, PETS' 24) -- which does not provide verifiability -- our protocol is $\approx$11--14$\times$ faster while imposing no overhead at the servers (beyond the cost of inference in the original model). Our protocol also scales to larger models not supported by prior work: for example, with our protocol a client can run the Llama 2-70B model using just 179~MB of local storage (instead of the 140~GB required to run the model locally).

Li et al. (IEEE Transactions on Dependable and Secure Computing 2026) proposed proxy-free public key authenticated encryption with ciphertext update and keyword search (proxy-free PAUKS). In this short note, we demonstrate that keyword information is leaked from updated ciphertexts. We also demonstrate that our attack is effective against the PAUKS scheme proposed by Li et al. (IEEE Transactions on Information Forensics and Security 2023).

Privacy is a fundamental requirement of modern digital payment systems, which process highly sensitive financial data, including account balances and transaction amounts. Unauthorized disclosure of this information can compromise users’ financial privacy and expose them to fraud or other forms of financial abuse. A key challenge in this setting is to verify that a payment amount does not exceed the payer’s available balance without revealing either the payment amount or the balance. A common approach is to employ zero-knowledge range proofs (ZKRPs). However, because conventional ZKRPs require public bounds, verifying a private value against private bounds requires multiple ZKRP instances, resulting in substantial computational and communication overhead that can increase latency and lead to cascading failures at scale. Motivated by the sequential nature of transactions in real-world payment systems, we formalize the problem of Sequential Private Range Verification (SPRV) and propose a framework, Persephone, that exploits the sequential structure of linked verifications rather than treating each verification independently. Within Persephone, we design and leverage a novel zero-knowledge proof primitive, ZK-MultNNP, to solve SPRV efficiently. Experimental results demonstrate that Persephone reduces total proving time by at least 3× compared to a ZKRP-based baseline. Furthermore, in a digital payment scenario, Persephone completes all transaction verifications within the 400 ms Doherty threshold, compared to only 30% of verifications for the ZKRP-based baseline.

Polynomial commitment schemes (PCSs) are fundamental building blocks of modern zkSNARKs and often dominate their concrete prover and verifier costs. We introduce $\mathsf{Quasar}$, a field-agnostic PCS for multilinear polynomials that combines Quasi-Abelian (QA) codes with BaseFold (Zeilberger et al., CRYPTO 2024) through code switching (Ron-Zewi and Rothblum, JACM 2024). For a polynomial of length $N$ and security parameter $\lambda$, $\mathsf{Quasar}$ achieves concretely fast $O(N\log N)$ commitment, $O(N)$ evaluation time, and $O(\lambda\log^2 N)$ proof size and verifier time. Our starting point is a recent work of Li et al. (CRYPTO 2026), which shows that QA codes have fast encoding and strong concrete distance. This opens the door to building efficient PCSs from QA codes via Brakedown's paradigm (Golovnev et al., CRYPTO 2023). However, a direct instantiation, called QAPCS, inherits square-root proof size and verifier time, falling short of practical efficiency when $N$ is as large as $2^{25}$. We overcome this crucial limitation by showing that QA codes are essentially code-switchable. In contrast to existing code-switching arguments that utilize algebraic structures of either generator matrices or parity-check matrices, we look into QA encoding algorithms and propose an efficient encoding-oriented argument. Consequently, $\mathsf{Quasar}$ simultaneously enjoys fast proving from QAPCS, and polylogarithmic verification of BaseFold. We implement $\mathsf{Quasar}$ over the 127-bit Mersenne prime field with rate $1/2$ and 100-bit security. Under the 32-thread CPU setting, $\mathsf{Quasar}$ accelerates commitment and evaluation over BaseFold by $13.6\times$--$20.6\times$ and $5.2\times$--$63.8\times$, respectively. It is also $2.2\times$--$6.0\times$ faster in commitment than Brakedown and $2.1\times$--$4.0\times$ faster in commitment and $17.4\times$--$237.6\times$ faster in evaluation than BrakingBase, while providing smaller proofs and faster verification than both. Compared with QAPCS, it achieves up to $4.3\times$ faster verification and $2.9\times$ smaller proofs. Moreover, we observe that QA encoding naturally exposes massive parallelism, enabling a GPU acceleration strategy that is not directly available to the other code families. Across message lengths from $2^{12}$ to $2^{25}$, the GPU encoder is $32.9\times$--$148.3\times$ faster than the 32-thread CPU implementation. Over polynomial sizes $2^{20}$--$2^{29}$, the commitment with GPU acceleration further achieve a $3.4\times$--$16.7\times$ speedup relative to its 32-thread CPU implementation.

This paper initiates a concrete-security treatment of two-party secure computation. The first step is to propose, as target, a simple, indistinguishability-based definition that we call InI. This could be considered a poor choice if it were weaker than standard simulation-based definitions, but it is not; we show that for functionalities satisfying a condition called invertibility, that we define and show is met by functionalities of practical interest like PSI and its variants, the two definitions are equivalent. Based on this, we move forward to study the concrete security of a canonical OPRF-based construction of PSI, giving a tight proof of InI security of the constructed PSI protocol based on the security of the OPRF. This leads us to the concrete security of OPRFs, where we show how different DH-style assumptions on the underlying group yield proofs of different degrees of tightness, including some that are tight, for the well-known and efficient 2H-DH OPRF, and thus for the corresponding DH PSI protocol. We then give a new PSI protocol, called salted-DH PSI, that is as efficient as DH-PSI, yet enjoys tighter proofs.

We present a hybrid password-authenticated key exchange (PAKE) protocol that is secure against harvest-now-decrypt-later (HNDL) attacks by quantum adversaries, and is universally composable under the parallel composition framework of Lyu and Liu (EUROCRYPT 2025). Existing hybrid PAKE constructions combine a classical PAKE with a post-quantum (PQ) PAKE, with the overall security intended to rely on the stronger of the two. However, identifying which PAKE is stronger is non-trivial, given the limited maturity of post-quantum PAKE designs. Recognizing that the immediate quantum threat is passive, we propose a different hybrid compiler: rather than combining two PAKEs, we encapsulate a classical PAKE within a standard post-quantum Key Encapsulation Mechanism (KEM). This modular separation avoids the fragility of post-quantum password handling while neutralizing HNDL attacks. Our compiler works with any two-pass or three-pass PAKEs. As a concrete instantiation, we construct a three-pass protocol that combines J-PAKE and a post-quantum KEM. We also implement the resulting protocol and provide performance results demonstrating that the hybrid construction remains practical, with the complete handshake executing in $2.81\text{ ms}$. This construction has the distinctive advantage that it does not require any ideal cipher, (constant-time) hash-to-curve, or trusted setup assumptions. Within the Lyu-Liu framework, we show that J-PAKE satisfies the notion of a Full DH-type PAKE. We model the KEM as a password-independent Simulatable DH-type component satisfying the minimal simulation properties required for parallel composition. To capture the prospective quantum threat, we formalize a stronger variant of the standard HNDL threat model—where the quantum adversary is explicitly granted the plaintext password—and prove that our protocol achieves Session Key Security and Post-Quantum Forward Secrecy. Our construction relies solely on standardized and widely deployed primitives, yielding a hybrid PAKE that is UC-secure, efficient, and well-suited for real-world deployment during the post-quantum transition.

We present the first folding framework that achieves sublinear verification and communication when a single prover must convince a verifier of $k$ independent R1CS instances. - $\mathbf{FLIP}$ (Fold-Inner-Product) folds the $k$ instance-witness pairs in only $\log k$ rounds. Built on the homomorphic two-tier commitment of Abe et al. (CRYPTO 2010), FLIP transmits $O(\log k)$ group elements. - $\mathbf{r \operatorname{-} Groth}$ is a commit-and-prove variant of Groth16 that natively handles relaxed R1CS. It retains Groth16’s three-element proof and two pairing checks, requires only a slightly modified (instance-independent) trusted setup, and does not rely on elliptic-curve cycles or foreign-field arithmetic. Combined, FLIP + r-Groth replace the $k-1$ extra Groth16 proofs demanded by aggregation schemes and avoid the heavy verifier-in-circuit logic of recursive systems. The total prover work is essentially one Groth16 run plus light folding, while the verifier processes $O(\log k)$ group elements and two pairings. This design is immediately applicable to roll-ups, Proof-of-Space, and other "proving-as-a-service" scenarios where all witnesses reside on a single machine.

We present Olingo, a framework for threshold lattice signatures that is the first to offer all desired properties for real-world implementations of quantum-secure threshold signatures: small keys and signatures, low communication and round complexity, non-interactive online signing, distributed key generation (DKG), and identifiable abort. Our starting point is the framework by Gur, Katz, and Silde (PQCrypto 2024). We change the underlying signature scheme to Raccoon (Katsumata et al, Crypto 2024), remove the trapdoor commitments, extend the scheme from two to three rounds, and then apply numerous improvements and optimizations to achieve all the above properties. We provide detailed proofs of security for our new framework and present concrete parameters and benchmarks. At the $128$-bit security level, for up to $1024$ parties and supporting $2^{60}$ signatures, our scheme has $4.4$ KB public keys and $11.3$ KB signatures; while signing requires communication of $852$ KB per party using the LaBRADOR proof system (Beullens and Seiler, Crypto 2023). An optimistic non-interactive version of our scheme requires only $76$ KB communication per party.

Polynomial commitment schemes allow a prover to commit to a large polynomial and later prove a claimed evaluation at a chosen point. They are a core component of many efficient SNARKs, and the cost of their evaluation phase directly affects SNARK prover time. Reed--Solomon-based schemes already offer small proofs and fast verification, but generating an evaluation proof for a large polynomial remains expensive. We present LiftWHIR, a Reed--Solomon-based polynomial commitment scheme that reduces prover time in the evaluation phase. LiftWHIR combines interleaved coding with the DEEP(ITCS'20) technique to reduce proving an evaluation of a large polynomial to two smaller tasks: a proximity test on a shorter codeword and evaluation of a smaller polynomial. The use of DEEP simultaneously reduces the number of queries required by the proximity test. We then use WHIR(EUROCRYPT'25) to prove both resulting tasks, keeping verification and communication costs low. LiftWHIR trades a modest increase in proof size and verifier time for a substantial reduction in prover time. At $n=2^{20}$ over a 255-bit prime field and code rate $1/2$ (resp., $1/4$), LiftWHIR reduces the evaluation phase to 167 ms (resp., 169 ms), yielding a $4.4\times$ (resp., $6.7\times$) speedup over WHIR. Including commitment, LiftWHIR achieves total prover times of 808 ms (resp., 1,474 ms), corresponding to overall prover speedups of $1.61\times$ (resp., $1.55\times$). Verification time increases from 0.55 ms to 0.76 ms (resp., 0.40 ms to 0.51 ms), while proof size is $1.46\times$ (resp., $1.33\times$) that of WHIR. We further instantiate Spartan(CRYPTO'20) with LiftWHIR and compare it with a Spartan variant instantiated with WHIR. LiftWHIR speeds up proving by $1.9\times$, while verification time increases only from 3.86ms to 4.62ms, at the cost of a $42\%$ increase in proof size.

Ring signatures enable a user to sign anonymously on behalf of a group, providing a fundamental building block for privacy-preserving applications such as anonymous credentials and private transactions. Existing post-quantum constructions, however, face a persistent tension between efficiency and rigorous quantum security: practical schemes are typically analysed only in the classical random oracle model (ROM), whereas schemes with proofs in the quantum random oracle model (QROM) either incur multi-megabyte signatures, lack implementations, or rely on reductions too loose to support concrete parameter selection. We present PegaRing, the first post-quantum ring signature to combine practical performance with concretely parameterised security in QROM. At the 128-bit security level and a ring size of 1024, PegaRing produces 28KB signatures, reducing signature size by a factor of 88 relative to the smallest prior concretely parameterised QROM-secure construction. Our implementation signs in 4.325 ms and verifies in 3.074 ms. Compared with the state-of-the-art VOLE-in-the-head ring signature, which is proven secure only in classical ROM, PegaRing reduces signing and verification latency by factors of 2.65 and 3.80, respectively, while providing security in QROM. Finally, when using the first message-dependent Fiat-Shamir challenge as the boundary between offline and online computation, PegaRing's online signing phase takes 0.018 ms, compared with 7.611 ms for VOLE-in-the-head construction, achieving a reduction of more than 400 times. These results substantially narrow the gap between rigorous quantum security and practical performance for post-quantum ring signatures and make QROM-secure anonymous authentication feasible for various anonymity sets.

This work introduces SandwichPIR, the first single-server PIR protocol that implements the overwhelming majority of the server computation as dense 8-bit integer matrix multiplications on GPU tensor cores and requires no offline communication. For a 4 GB database with 32 KB records, SandwichPIR answers a query in 8.2 ms and communicates 688 KB of data. This amounts to a server throughput of 488 GB/s and is $88\times$ faster than the best CPU-based protocol that does not rely on offline communication. The performance of SandwichPIR shines when processing a batch of queries from many independent clients. This moves the server from a memory-bandwidth-bound regime into a compute-bound regime. A single Nvidia L40S GPU can process a batch of 128 queries to the same 4 GB database in 21.0 ms. This gives an amortized per-query processing time of 0.16 ms and an effective throughput of roughly 24 TB/s. This is $50\times$ higher than the single-query throughput. With a fleet of 8 GPUs, SandwichPIR can process a batch of 128 queries to a 256 GB database in 119 ms and achieves an effective throughput of nearly 270 TB/s. Finally, we show how to use SandwichPIR to enable private access to (text-only) English Wikipedia (8 GB compressed). Retrieving an article (up to 128 KB) requires 768 KB of client-server communication, with an estimated total end-to-end latency under 200 ms over a broadband network connection. By processing 64 queries at a time, a single GPU can handle over 2,500 queries per second (with a computational cost of \$0.20 per million queries based on current AWS pricing).

Keyword private information retrieval (PIR) allows a client to retrieve a record associated with a keyword from a database without revealing any information about the keyword. In the standard single-server setting, existing hintless keyword PIR protocols incur substantial communication and computation costs. In this paper, we propose an efficient approach to generate $k$-hot vectors (i.e., vectors with exactly $k$ non‑zero components) in homomorphic-encryption form, and present a bucket-merging technique to decrease the maximum size of buckets. Based on these techniques, we construct LetoPIR, a hintless keyword PIR protocol that outperforms previous PIR protocols in the same setting. Compared to the state-of-the-art hintless keyword PIR scheme, SparsePIR (USENIX'23), LetoPIR achieves a $12.4\times \sim 17.0\times$ improvement in communication cost for databases ranging from $256$ MB to $4$ GB with records of $256$ bytes, and more than $3.0\times$ improvement in computation cost for the $256$ MB database. Compared to the state-of-the-art keyword PIR scheme with client hint, KPIR (USENIX'25), LetoPIR reduces the communication cost by $51.4\times \sim184.8\times$, while achieving a similar (even better) computation cost.

Private information retrieval (PIR) enables a client to retrieve a record without revealing the index.Among existing PIR protocols with database-independent preprocessing, for each query, the protocols with low communication often take from several seconds to tens of seconds, while the faster protocols require hundreds of kilobytes for communication. In this paper, we propose three techniques for different-type ciphertext conversions: (1) the first one is to generate a two-orbit SIMD selector from encrypted bits; (2) the second one is to convert a packed $\mathsf{RLWE}$ ciphertext into an aligned monomial $\mathsf{RGSW}$ ciphertext; (3) the third one is to produce an arbitrary monomial $\mathsf{RGSW}$ ciphertext from encrypted bits. Building on these techniques, we design a new PIR protocol (called Atom), achieving the best of both worlds (i.e., having not only low communication but also fast computation). We implemented Atom and evaluated its performance for $256$ B records and databases from $256$ MB to $8$ GB. Specifically, Atom takes $3.0 \sim 3.8$ KB of online communication (i.e., the total communication, excluding the setup phase that can be run only once and reused for multiple queries), and takes $0.4 \sim 5.0$ seconds per query. Compared to the state-of-the-art KsPIR (CCS'24), Atom reduces the online communication cost by a factor of $40.5\times \sim 51.3\times$, while its running time is comparable to KsPIR ($0.2 \sim 5.2$ seconds per query).

End-to-end cloud storage solutions are deployed at large scale, yet recent works have demonstrated severe attacks against their confidentiality and integrity. Motivated by this, a first formal treatment of secure cloud storage was given at CRYPTO 2024 by Backendal, Davis, Günther, Haller and Paterson (BDGHP). They define syntax and security notions, capturing client-to-client security of cloud storage schemes with respect to a password distribution. They also give an efficient construction using the Two-Hash Diffie-Hellman (2HDH) OPRF and standard cryptographic building blocks, which they prove secure under selective corruptions in the random oracle model. However, several aspects of practical security guarantees remain open. We extend and refine the work of BDGHP along multiple dimensions, advancing the analysis of secure cloud storage schemes. First, we prove that their construction can be proven secure against adaptive corruptions (with a slight modification), circumventing technical challenges posed by file sharing. Second, we modularize the scheme further by introducing an abstraction for the authentication procedure. This allows us to identify the concrete role of 2HDH and alternative instantiations. Third, we introduce a weaker model that captures adversaries who can arbitrarily control the network, except during registration. This allows us to prove concrete guarantees about online password guessing attacks, whereas the stronger model inherently allows for offline guessing. Finally, we formalize and prove explicit authentication, relying on the security of our new authentication abstraction and the MAC scheme, where the latter was previously not used in the security analysis.

Secure multiparty computation (MPC) enables mutually distrustful parties to jointly compute functions over private data without revealing their inputs. A central paradigm in MPC is the secret-sharing-based model, where secret sharing underpins the efficient realization of arithmetic, comparison, numerical, and Boolean operations on shares of private inputs. In this paper, we systematize protocols for these operations, with particular attention to two foundational contributions \cite{ChidaGHIKLN18,NO07} that devised secure multiplication and comparison. Our survey provides a unified, self-contained exposition that highlights the composability, performance trade-offs, and implementation choices of these protocols. We further demonstrate how they support practical privacy-preserving systems, including recommender systems, distributed optimization platforms, and e-voting infrastructures. By clarifying the protocol landscape and connecting it to deployed and emerging applications, we identify concrete avenues for improving efficiency, scalability, and integration into real-world MPC frameworks. Our goal is to bridge theory and practice, equipping both researchers and practitioners with a deeper understanding of secret-sharing-based MPC as a foundation for privacy technologies.

Hash-based constructions occupy a distinctive position among post-quantum signatures: their security reduces to well-tested properties of hash functions rather than to newer assumptions such as lattices or isogenies. This work focuses on stateful schemes instead of stateless, because the former are considerably more efficient. However, they have the problem of state handling, since reusing a one-time key twice enables signature forgeries. Despite threshold signatures mitigate this problem by spreading trust among a set of disjoint parties, building them from hash-based schemes is difficult, since these lack the homomorphic structure needed to recombine partial signatures, and generic multiparty computation can be expensive for hash-based constructions. Kelsey, Lang and Lucks recently proposed Haystack, the first threshold scheme for hash-based signatures producing standard LMS or XMSS signatures, at the cost of a fully trusted setup and a large common reference value. We analyze Haystack along two dimensions: performance and security. First, as Haystack lacks an implementation and realistic benchmarking, we implement the protocol in Java and produce a network-aware evaluation of its viability in real deployments, concluding that it performs comparably to other post-quantum threshold schemes. Second, we relax the trust placed in the dealer. For that, we introduce a variant of the setup built on an optimistic, lightweight MPC-based partial-DKG. It does not remove the dealer's ability to forge, but it prevents it from impersonating trustees within the signing protocol, while preserving the standard signature format. Also, an optional succinct-argument layer provides public auditability. We further consider a full-DKG setting with no dealer and where the trustees run the entire setup under MPC. Both variants are implemented in MP-SPDZ and their costs have been analyzed.

Gao et al. (IEEE Internet of Things Journal, 2025) proposed a medical data sharing system for digital twin environments using identity-based encryption (IBE), public-key encryption with keyword search (PEKS), and blockchain technologies. In this short note, we show that Gao et al.'s system allows unauthorized users to access other patients' medical data. We further show that the search server can obtain information about the queried keywords from the trapdoors (search queries). In addition, we analyze the procedure used to retrieve, from the blockchain, the IPFS (InterPlanetary File System) addresses storing encrypted medical data and encrypted keywords. Since these addresses are derived from labels that can be computed solely from public information and keywords, and because the keywords themselves are provided to the search server, we demonstrate that searchable encryption is unnecessary in the first place. Based on our security analysis, we argue that the proposed system requires a fundamental redesign.

Threshold ECDSA has been an active research topic in recent years, driven by its wide-ranging applications, particularly in blockchain domains. In these real-world applications, robustness is a critical requirement. It ensures that a signature is successfully generated as long as $t+1$ honest parties are present, regardless of malicious behavior from others. Existing robust constructions generally fall into two categories: those based on threshold linearly homomorphic encryption (TLHE) and those leveraging the Multiplicative-to-Additive (MtA) paradigm. The TLHE-based approach (e.g., WMC24 in NDSS'24) achieves constant sending communication per party but incurs an expensive online phase. In contrast, the MtA-based approach (e.g., TX25 in S\&P'25) is online-friendly, requiring only elliptic-curve group operations during the online phase. However, it has the drawback of requiring $O(n)$ sending communication per party when $n$ parties are involved. In this work, we propose ARES, a robust threshold ECDSA scheme designed to reduce both communication and computational overhead within the online-friendly MtA framework. To improve the communication efficiency of TX25, we propose verifiable non-interactive multiplication (VNIM), a new primitive which endows standard non-interactive multiplication with public verifiability. Simultaneously, we leverage super-invertible matrices and packed secret sharing to amortize the overall costs. Specifically, when setting the packing parameter of packed secret sharing to $\ell = 1$ (i.e., without secret packing), ARES exhibits linear communication complexity while already achieving an approximately $50\%$ improvement over TX25. When configuring $\ell = t/3$ with $t \ge 12$, ARES achieves lower communication overhead than WMC24, requiring a constant $\approx 4.5\text{ KB}$ per party. Furthermore, setting $\ell = t/2$ reduces the amortized communication cost to roughly $3\text{ KB}$ per party. On the other hand, amortizing across $\ell$ signatures incurs a trade-off by increasing the required party size by $\ell$.

We present SALSAA, a more efficient and more versatile extension of the state-of-the-art lattice-based fully-succinct argument frameworks, ``RoK, paper, SISsors (RPS)'' and ``RoK and Roll (RnR)'' [Klooß, Lai, Nguyen, and Osadnik; ASIACRYPT'24, '25], integrating the sumcheck technique as a main component. This integration enables us to design an efficient norm-check protocol (controlling the norm during witness extraction) with a strictly linear-time prover while reducing proof sizes by 2-3$\times$ compared to the previous quasi-linear-time norm-check in RPS/RnR, eliminating a central performance bottleneck. The sumcheck integration also allows us to natively support a wider class of relations, including rank-1 constraint systems (R1CS), which are widely used to express real-world computations. To demonstrate the versatility and efficiency of our framework, we showcase three impactful applications achieved by different RoKs (Reductions of Knowledge) compositions: (i) a lattice-based succinct argument of knowledge with a linear-time prover, achieving a verifier time of $41$ ms, prover runtime of $10.61$ s, and proof size of $979$ KB for a witness of $2^{28}$ $\mathbb{Z}_q$ elements; (ii) a polynomial commitment scheme with matching performance; and (iii) the first lattice-based folding scheme natively operating on $\ell_2$-norm-bounded witnesses, achieving highly efficient verification in $2.28$ ms and producing a proof of just $73$ KB for a witness of $2^{28}$ $\mathbf{Z}_q$ elements, outperforming prior works for the family of linear relations. We provide a modular, concretely efficient Rust implementation of our framework, benchmarked over cyclotomic rings with AVX-512-accelerated NTT-based arithmetic, demonstrating the practical efficiency of our approach.

Blockchain light clients (LCs) are agents with limited computational or storage resources that cannot maintain a fully validated copy of the ledger. They rely on service providers (SPs), typically full nodes, to access data required for tasks such as constructing a transaction (Tx) or interacting with off-chain applications. We introduce Cavefish, a novel protocol for UTxO-based platforms that enables LCs to interact with the ledger and submit a transaction (Tx) with minimal trust, storage, and computation, without having to synchronize to the chain. The LC specifies a Tx (e.g., by specifying a source address rather than source UTxOs, a destination and value, and a change address), and the SP constructs it, including a payment to the SP as an additional output. The LC needs to verify Tx before signing it, but the SP cannot reveal it without fear of losing its compensation. In order to resolve this two-sided trust problem, we propose a variant of the predicate blind signature (PBS) scheme of Fuchsbauer and Wolf (Eurocrypt 2024), which enables the SP to obtain valid Schnorr signatures on Tx, but only after proving to LC that Tx satisfies the specification. Cavefish achieves a trustless interaction in which the LC fulfills their transaction goal, and the SP receives fair compensation for their effort. As transactions only need to stay private until posted, our PBS variant relaxes the unlinkability requirements of blind signatures. We implement and benchmark the Non-interactive Argument of Knowledge component of Cavefish on two major UTxO-based blockchains, using two different zero-knowledge proving systems.

Recently, the notion of dynamic zk-SNARKs was introduced. A dynamic zk-SNARK augments a standard zk-SNARK with an efficient update algorithm. Given a valid source statement-witness pair $(x,w)$ together with a verifying proof $p$, and a valid target statement-witness pair $(x',w')$, the update algorithm outputs a verifying proof $p'$ for $(x',w')$. Crucially, $p'$ is not recomputed from scratch; instead, the update algorithm takes time roughly proportional to the Hamming distance between $(x,w)$ and $(x',w')$, analogous to how dynamic data structures update the result of a computation after a small change. In this paper, we initiate the study of designated-verifier dynamic zk-SNARKs: dynamic zk-SNARKs in which only a designated verifier, holding secret verification state, can be convinced by a proof. Following recent advances in designated-verifier zk-SNARKs---such as efficient post-quantum designated verifier SNARKs (CCS 2021) and designated verifier SNARKs with very small proofs (CRYPTO 2025)---we construct a designated-verifier dynamic zk-SNARK with $O(\log n)$ update time, constant proof size, and concrete efficiency. Our construction significantly outperforms Dynalog (both asymptotically and concretely), the only publicly verifiable dynamic zk-SNARK with polylogarithmic update time (Wang et al., 2024). The concrete efficiency of our construction enables, for the first time, an efficient implementation of a dynamic proof of index: Given a digest $d$ of an arbitrary set and a digest $d'$ of its sorted index (e.g., binary search tree), we produce a SNARK proof certifying the consistency of $d$ and $d'$. More importantly, this proof can be updated in sublinear time when the underlying set changes---for example, when an element is modified or inserted, potentially altering the sorted order. We demonstrate applications of designated-verifier dynamic proofs of index to verifiable dynamic database outsourcing, where a client outsources a database and later maintains verifiable indices for efficient query answering, even under arbitrary database updates.

To enhance the security of stealth addresses and protect user privacy, Liu et al. (EuroS&P 2019) proposed a Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Keys (PDPKS). In this scheme, the payee generates a master public/secret key pair, and the payer derives a public key from the payee's master public key and binds the cryptocurrency asset to the resulting derived public key. The payee then verifies, using the master secret key, whether the derived public key has been correctly generated from the master public key. In this paper, we show that a public-key encryption (PKE) scheme secure against chosen-ciphertext attacks (CCA) can be generically constructed from PDPKS. Specifically, we utilize unlinkability, which hides the master public key from which a derived public key originates, to conceal plaintext information from ciphertexts. We also simulate the decryption oracle by leveraging the derived public key checking algorithm. In addition, to guarantee the correctness of the proposed PKE scheme, we rely on the consistency of PDPKS introduced by Emura (IACR CiC 2025). Given the motivation behind PDPKS, namely the construction of stealth addresses in a provably secure manner, unlinkability is regarded as the core security property of PDPKS. Our result shows that achieving this core security property essentially requires CCA-secure PKE, or cryptographic primitives of equivalent strength, and that such primitives are indispensable for constructing PDPKS.

Motivated by applications to efficient secure computation, we consider the following problem of encrypted matrix–vector product (EMVP). Let $\mathbb F$ be a finite field. In an offline phase, a client uploads an encryption of a matrix $M \in \mathbb F^{m\times \ell}$ to a server, keeping only a short secret key. The server stores the encrypted matrix \(\hat{M}\). In the online phase, the client may repeatedly send encryptions \(\hat{ q}_i\) of query vectors \(q_i \in \mathbb F^\ell\), which enables the client and the server to locally compute compact shares of the matrix–vector product \(Mq_i\). The server learns nothing about \(M\) or \(q_i\). The shared output can either be revealed to the client or processed by another protocol. We present efficient EMVP protocols based on variants of the learning parity with noise (LPN) assumption and the related learning subspace with noise (LSN) assumption. Our EMVP protocols are field-agnostic in the sense that the parties only perform arithmetic operations over \(\mathbb F\), and are close to optimal with respect to both communication and computation. In fact, for sufficiently large \(\ell\) (typically a few hundreds), the online computation and communication costs of our LSN-based EMVP can be \emph{less than twice} the costs of computing \(Mq_i\) in the clear. Combined with suitable secure post-processing protocols on the secret-shared output, our EMVP protocols are useful for a variety of secure computation tasks, including encrypted fuzzy search and secure ML. Our technical approach builds on recent techniques for private information retrieval in the secret-key setting. The core idea is to encode the matrix \(M\) and the queries \(q_i\) using a pair of secret dual linear codes, while defeating algebraic attacks by adding noise.

This work presents a private instant messaging protocol that leverages the public log layer of blockchains as the message transport layer, while the cryptographic state is kept only by client applications. Thanks to the properties of public ledgers, this approach achieves strong censorship resistance, while also revealing the economic and cryptographic limits of on-chain messaging. Notably, given the transparency of public ledgers, and since reading and writing operations are in most cases outsourced to third-party providers that may be curious, a well-known concern is direct metadata leakage. We address this both at first contact and during the conversation: for first contact, we propose two alternative discovery mechanisms, one based on long-term key encapsulation with trial decryption, the other on a private signaling service backed by trusted hardware. For the ongoing conversation, we show that topic rotation, driven by the off-chain cryptographic state, suffices to prevent topic and conversation linkability. As our main contribution, we provide an in-depth analysis of Verbeth's metadata leakage under different adversarial assumptions for both phases.

Additive Randomized Encodings (AREs) provide a lightweight route to non-interactive secure computation: each party locally produces a randomized encoding of its input, and an evaluator learns only the function value from the sum of these encodings. Prior frameworks for constructing AREs for general functions ultimately hinge on an efficient ARE for string oblivious transfer (SOT), making SOT the core efficiency bottleneck. We revisit this final step and present improved ARE constructions for SOT. First, we streamline the recent PKE-based approach by directly constructing the required one-sided ARE (OSARE) for SOT. This yields a perfectly correct, statistically one-sided secure OSARE for SOT of size $\mathcal{O}(\lambda)$, improving the intermediate overhead and, consequently, the overall size of the resulting PKE-based ARE. Second, we give a pairing-free ARE for SOT under the Squaring DDH assumption. Our construction is compatible with Halevi et al.'s efficient equality-to-SOT methodology: we build an ARE for Rabin-OT that embeds a message in the equality-checking procedure and then transform it to SOT while incurring only constant-factor communication overhead and no additional correctness error. The resulting ARE for SOT has size $\mathcal{O}(\lambda)$ and negligible correctness error.

We present Thunderbolt, an off-chain protocol that transfers Bitcoin UTXO ownership with seconds-scale latency, requires no channel graph, no routing, and no liquidity rebalancing, and lets the recipient be offline at the time of transfer. A single UTXO is locked once on-chain under a fixed public key jointly held by the current owner and a threshold committee; ownership then passes through an unbounded sequence of holders; each transfer is a purely off-chain, asynchronous operation whose on-chain cost is zero. The chain sees exactly two transactions regardless of how many transfers occur. The core invariant is an algebraic cancellation: at each transfer the recipient's fresh secret is added to the holder's share and subtracted from the committee's share, so both shares rotate while the on-chain key stays fixed. To enforce this, the recipient publishes an invoice to a shared append-only ledger (the Thunderbolt Ledger): a public commitment, an encrypted copy for himself, and an encrypted copy for the committee, together with a zero-knowledge proof that all three encode the same fresh secret. The sender fetches the invoice, verifies the proof, homomorphically folds her secret into the recipient's ciphertext to produce a new ownership credential, and publishes the result with a second zero-knowledge proof. Both proofs use a single Sigma-protocol response to force the same witness across elliptic-curve and Paillier verification equations, requiring no trusted setup. The committee operates under a standard $(t,n)$-threshold honest-majority assumption: at most $t{-}1$ of $n$ members may be corrupted. The recipient decrypts at any later time; the committee subtracts the fresh secret from its share. By binding each transfer to a distinct fresh secret and context identifier, multiple UTXOs can be transferred independently in parallel. On our benchmark machine, a complete off-chain transfer finishes in 1022ms with a combined proof size of 3.8KB. General-purpose SNARK (Succinct Non-interactive Argument of Knowledge) backends are orders of magnitude slower on the same relations: even a reduced-parameter instantiation already exceeds our native proving time by two orders of magnitude, and a faithful realization at the deployed 3072-bit Paillier modulus exceeds the memory budget of consumer hardware.

Distributed shuffling is a core primitive underlying mix-nets, electronic voting, and, more recently, single secret leader election (SSLE) protocols for proof-of-stake blockchains. In these settings, a collection of resource-constrained parties jointly permutes a list of ciphertexts or commitments in order to conceal the correspondence between inputs and outputs. Existing security analyses of such protocols typically rely on heuristic anonymity measures or implicitly assume honest behavior; therefore, they fail to capture statistical dependencies that arise when shuffling is partial and some participants are corrupted. In this work, we introduce a new security model for distributed shuffling that accurately reflects the setting of real-world attacks by explicitly accounting for adversarial corruption and information leakage. Our model allows an adversary to corrupt a subset of shufflers and track selected elements throughout the execution, as well as query the resulting permutation afterwards. We then turn to studying Whisk in this model, the shuffle-based SSLE mechanism proposed for Ethereum. Leveraging Markov-chain techniques, we show that security can only be guaranteed for more stringent parameters than currently proposed. We evaluate the performance impact of changing these parameters on the Ethereum network.

Multi-party private set intersection (MPSI) enables multiple parties to securely compute the intersection of their private datasets without revealing any information beyond the intersection itself. However, as the number of participants scales, the performance of multi-party PSI protocols is significantly influenced, with the number of interaction rounds emerging as a critical bottleneck. In this paper, we propose a novel MPSI protocol and its updatable extension based on function secret sharing and oblivious key-value stores, achieving optimal one-pass online interaction. Our construction guarantees security in the semi-honest model, resisting collusion among any $n-1$ parties when the Leader is honest, and among any $n-2$ parties when the Leader is corrupted—an assumption that aligns well with many practical deployment scenarios. Furthermore, our multi-party updatable PSI (MUPSI) protocol allows parties to efficiently compute the intersection over dynamically updated sets. Our MUPSI protocol achieves collusion resistance against any $n-1$ participants, assuming an honest Leader. It ensures that both computational and communication complexities scale exclusively with the size of the updates rather than the entire datasets, exhibiting superior performance particularly when handling unbalanced sets and large participant cohorts. All proposed protocols exhibit strong scalability with respect to participant count. We demonstrate the superiority of our protocols through implementation and comparison with state-of-the-art MPSI protocols. Experiments show that when the number of participants ranges from $20$ to $140$ and the set size ranges from $2^{12}$ to $2^{20}$, our MPSI protocol is competitive. Notably, in the WAN setting with $140$ participants and a set size of $2^{20}$, the running time is reduced by $49.1\times$ compared with GLW+24. Our MUPSI protocol avoids PSI operations on entire sets, achieving a reduction in running time by an order of magnitude.

XtM (XOR-then-MAC) is provably optimal against quantum adversaries. As of March 2025, no production cryptographic library implements it. HKDF, with weaker security guarantees, is deployed in 91% of the 44 libraries we examined. This gap is not accidental.This Systematization of Knowledge (SoK) introduces the (A, P, φ) framework to explain it: A measures authentication strength, P measures IETF standardization maturity, and φ measures implementation complexity. To our knowledge, this is the first falsifiable, quantitative model predicting cryptographic adoption grounded in observable software engineering indicators. We apply this framework to seven combiner families and 44 cryptographic libraries, validate φ against measured integration LOC across 9 real-world repositories, and derive predictions verifiable by 2028.Our evidence suggests that implementation complexity is a first-order explanatory factor in cryptographic adoption. The most deployable construction is not the most secure one in isolation: it is the most secure one engineers can integrate, audit, and maintain at scale.

An oblivious key-value store is a data structure that can encode and decode $n$ key-value pairs in a table of size $m$ obliviously. After encoding, one cannot distinguish the encoded key-value pairs from other key-value pairs in the input domain. In this paper, we first propose a data structure called Peelable Garbled Bloom Filter (PGBF), which encodes the key-value pairs in a similar way to peeling and unpeeling an \emph{onion}. Specifically, it can divide the key-value pair set (i.e., onion) as multiple subsets (i.e., peels) and order them from the outermost peel to the innermost peel by using a counting Bloom filter. However, using a small expansion rate (i.e., $\eta=m/n$) in PGBF will result in a non-empty core issue with non-negligible probability. To handle this issue, we propose Multi-PGBF by combining multiple PGBFs to do the peelings and unpeelings recursively. In addition, we propose a variant C-Multi-PGBF by clustering a large set into small sets to achieve faster encoding efficiency. Our experiments show that Multi-PGBF and C-Multi-PGBF obtain the best encoding and decoding efficiency. Multi-PGBF improves the encoding time of RR (CCS’22) by $65.1\%\sim 77.6\%$, while C-Multi-PGBF improves the encoding time of the clustered RR variant by $60.2\%\sim 64.7\%$. For decoding, Multi-PGBF is $28.6\%\sim 62.4\%$ faster than RR (CCS'22) and $89.7\%\sim 96.3\%$ faster than RB-OKVS (Usenix'23). When integrated into the state-of-the-art two-party and multi-party private set intersection protocols (Eurocrypt'21, Usenix'24), Multi-PGBF and C-Multi-PGBF lead to faster protocols than those using existing OKVS constructions in most settings.

We present Grand Danois, a new post-quantum multilinear polynomial commitment scheme from lattices for polynomials over $\mathbb{F}_q$ that achieves polylogarithmic $O(\lambda \ell)$ verification complexity and proof sizes. We build on the general approach introduced in Hachi (ePrint 2026/156) with three key changes. First, we switch to the vanishing Short Integer Solution (vSIS) assumption to obtain structured public parameters for our commitment scheme and utilize this structure to design a sumcheck protocol amenable to succinct verification. Second, rather than casting ring relations into $\mathbb{F}_{q^k}[X]$, via the residual technique of Hachi, we express multiplication by fixed $\mathcal{R}_q$ elements through its rotation matrix, which lets the verifier fold each row of the constraint matrix in time linear rather than quadratic in the ring degree $d$. Third, we modify the quadratic relation used in Hachi and Greyhound (CRYPTO 2024) so that it becomes compatible with proving norm bounds using Johnson-Lindenstrauss projections. This is achieved through an adaptation of the structured projection strategy introduced in RoK and Roll (ASIACRYPT 2025). This has the benefit for communication complexity in that proving norm bounds and correct polynomial evaluation are integrated into a single protocol, reducing the number of commitments sent by the prover. Furthermore, we impose additional structure on our random projections to reduce the witness size even more aggressively during each round of recursion without sacrificing verification complexity. Under the vSIS assumption, our construction yields an estimated proof size of roughly $80$ KB for $2^{32}$-size polynomial evaluations.

The notion of Best-of-Both-Worlds introduced in the work of Ishai et al. (CRYPTO 2006) investigated whether an MPC protocol can simultaneously provide two incomparable security guarantees depending on the number of corrupted parties. As a special case of this, Chaum et al. initiated the study of protocols that tolerate unbounded corruption within a certain adversary structure and PPT corruption of any number of parties beyond that. More recently, Acharya et al. (CRYPTO 2023) formalized this notion as MPC with fall-back security. Although the feasibility of such protocols has now been thoroughly studied in prior works, most of the existing protocols require round complexity linear in the number of parties and the computation size. In this work, we study the round complexity of MPC with fall-back security in the threshold corruption setting, presenting constant-round protocols for optimal thresholds. We present a semi-honest fall-back secure protocol for $t < \frac{n}{2}$ with 3 rounds, in the plain model, whereas the best known protocol in the same setting takes at least 11 rounds. In the CRS model, we present a maliciously fall-back secure protocol for the same threshold with 4 rounds, satisfying unanimous abort (UA). Finally, we extend this to a 5-round protocol that satisfies fairness in the presence of unbounded adversaries for $t < \frac{n}{2}$ corruptions and UA tolerating PPT adversaries for arbitrary corruption beyond that. In the malicious setting, we construct the first constant-round fall-back secure protocols.

We present a practical framework $\mathsf{DumboMix}$ for asynchronous anonymous broadcasts with guaranteed output delivery (G.O.D., a.k.a. robustness), enabling a set of $n$ servers to privately solicit $N$ messages from distinct clients, such that these messages remain secret until they are revealed in uniform random order. Here, asynchronous G.O.D. ensures that all messages are eventually randomly mixed despite (i) arbitrary malicious behaviors by up to $\lfloor (n-1)/3 \rfloor$ Byzantine servers and (ii) unpredictable network delays and jitters. At the core of $\mathsf{DumboMix}$, we first propose a couple of practical mixing methods $\mathsf{DumboMix1}$ and $\mathsf{DumboMix2}$ for Shamir-secret-shared multi-party computation (MPC) over $\mathbb{Z}_p$, along with their server-optimized variants. When randomly mixing $N$ messages, their online phases require only $\mathcal{O}(1)$ multiplicative depth, expected $\mathcal{O}(N^2)$ scalar multiplications (between public and shared values), and up to $\mathcal{O}(N)$ MPC multiplications (between shared values). Moreover, assuming a robust underlying MPC framework, they guarantee that all revealed inputs are uniformly shuffled. In contrast, existing techniques fail to achieve all these performance and functionality features: The DC-net variant $\mathsf{Blinder}$ (CCS’20) may reveal a non-negligible fraction of inputs without shuffling them; Butterfly switching networks in secret-shared MPC (CCS’19) incur $\mathcal{O}(\log^2 N)$ multiplicative depth; RabbitMix (Security’24) requires $\mathcal{O}(N^2)$ MPC multiplications; and PowerMix (CCS’19) incurs $N^{3}/2$ scalar multiplications. We finally implement our new mixing methods within $\mathsf{DumboMPC\text{++}}$, our computation-optimized implementation of the state-of-the-art robust AMPC framework $\mathsf{DumboMPC}$ (Security’25), which provides more concretely efficient offline preprocessing while preserving asynchronous G.O.D. and optimal resilience. We then conduct extensive evaluations with $n=4$ to $31$ servers under varying network settings, revealing that our new mixing methods achieve 44.8--65.9× (resp. 37.1--52.7×), 4.8--7.1× (resp. 3.9--5.5×), and 2.7--4.0× (resp. 5.1--7.2×) speedups over RabbitMix, PowerMix, and the butterfly switching network, respectively, when shuffling 1024 messages in LAN (resp. WAN).

\emph{Modular Polynomial Commitment Schemes (Mod-PCS)} extend standard PCSs by enabling provable evaluation of integer polynomials modulo a random modulus, providing a natural foundation for SNARKs that operate directly over large integers without emulating arithmetic in finite fields. Only two Mod-PCS constructions are known. The first (Campanelli and Hall-Andersen, IACR ePrint 2024) serves primarily as a feasibility result and is impractical and not post-quantum secure due to its reliance on groups of unknown order. The second (Garetta et al., CRYPTO 2025) introduces the weaker notion of \emph{relaxed} Mod-PCS, but is not fully succinct: committing to a multilinear polynomial with $N$ terms and $B$-bit coefficients requires $O(\sqrt{N}B)$ proof size and verification time. We present a black-box transformation that builds relaxed Mod-PCS from any standard PCS, enabling new constructions. Instantiating our transformation with a tensor-code PCS yields the first relaxed Mod-PCS with $O(\log (N+B))$ proof size and verifier time, which is transparent and plausibly post-quantum secure. Using this scheme within the framework of Garetta et al., we obtain the first fully succinct SNARK for the Customizable Constraint System over $\mathbb{Z}_B$, achieving $O(B\log N + N\log N \log B)$ prover time and $O(\log (N+B))$ verifier time and proof size. Our approach relies on a commitment-switching technique for integer polynomials and a new batched integer commitment scheme from any PCS. We further introduce improved arguments for integer addition and multiplication, correctness of the number-theoretic transform, and general Diophantine relations over committed integers.

Threshold signatures are deployed in settings where an adversary may run many concurrent signing sessions and corrupt signers adaptively. Two-round schemes make this especially delicate. Their first-round messages are independent of the signed message and can be preprocessed offline, so a later corruption must reveal randomness that is consistent with commitments already published in prior transcripts. Existing adaptive constructions address this tension by adding rounds, relying on algebraic or knowledge assumptions, or paying non-tight losses from guessing the corruption pattern, the decisive session, or the final transcript. We construct $\mathsf{TPilaf}$, the first two-round threshold signature scheme that combines partially non-interactive signing with a fully tight proof against adaptive corruptions. The scheme is pairing-free and is built in prime-order groups from the $\mathsf{MDDH}$ assumption in the random-oracle model. Its first-round messages can be generated offline, and any threshold set of signers can aggregate their second-round shares into a single publicly verifiable signature. The proof combines two ingredients. First, we introduce a linearly homomorphic dual-mode commitment with targetable opening. This lets the simulator open an already fixed commitment to the aggregate target imposed by a later Fiat-Shamir challenge. Second, we use profile-wise zero-sum masking with posterior completion. Corruption openings and signing responses are therefore sampled from the exact conditional law while values already visible to the adversary remain cached. Together, these tools enable a delayed branch-decision argument. The reduction waits until the adversary's own queries determine the last touched coordinate, completes only latent state, and then binds the forged hidden branch. The final bound has no combinatorial loss in the number of users, threshold, sessions, or corruption patterns, and contains only the explicit bad-event and assumption terms appearing in the theorem.

An adaptor signature scheme can be seen as committing to a signature using an NP statement, in such a way that (1) the commitment, called a presignature, is verifiable, (2) the corresponding witness enables opening the commitment (adapting the presignature), and (3) seeing a valid commitment-opening (presignature-signature) pair leaks the witness. In the blockchain space, where signed transactions must be broadcast to the public to take effect, this last property allows "forcing" a party to leak a witness for possibly multiple presignatures issued for the same NP statement. This then gives rise to many applications such as atomic swaps or payment channels. Importantly, in prevailing adaptor signature schemes, presignatures are already technically signatures, in that they are non-interactive zero-knowledge proofs of knowledge of the signing key. This has a number of consequences, most important being that the presignature constitutes evidence of intent to participate in a protocol based on adaptor signatures. Perhaps surprisingly, however, for many practical applications, this strong "binding" of presignatures turns out to be non-essential. In this work, we revisit the definitions of adaptor signature schemes, demonstrating that prevailing security requirements are often too strict. To this end, we formally define fair signature exchange (FSE) and abandon the assumption implicit in prior work that adaptor-based FSE must be "symmetric" with both parties using the same adaptor signature scheme. The resulting relaxation of security requirements leads us to the notion of presignature deniability, an extension to adaptor signature schemes that we define formally and construct from various assumptions.

Dynamic universal accumulators compress an evolving set into a short digest with membership and non-membership witnesses for each element. Bilinear Pairing (BP) accumulators offer succinct witnesses and fast verification, but their public parameters size, witness generation and dynamic costs scale linearly with the set size in the trapdoorless setting. To address this bottleneck, we present HACC, a trapdoorless hierarchical accumulator that organizes capacity-bounded BP accumulators over ordered buckets into a $t$-ary tree. By fixing the node capacity $t$, HACC is a pairing-based accumulator whose public parameters can be independent of the set size $n$. Its ordered buckets yield native non-membership proofs and $\mathcal{O}(t\log_t n)$ witness generation cost, and non-cascading bucket split and merge mechanisms keep it fully dynamic at worst-case $\mathcal{O}(t\log_t n)$ dynamic cost with amortized $\mathcal{O}(1)$ witness updates. Its witnesses are of size $\mathcal{O}(\log_t n)$ and verify with as many pairings, which an optional path compression via polynomial multiproofs reduces to a constant for read-heavy epoch-based settings. We prove HACC correct and sound under the $t$-SDH assumption in the random oracle model. Experimentally, under comparable budgets, HACC accelerates element update and witness generation by $8.0\times$--$5087\times$ over a monolithic BP accumulator (Nguyen, CT-RSA'05, Damgård et al., eprint'08, and Srinivasan et al., CCS'22) while consuming $15.6\times$--$15933\times$ smaller public parameters.

We present $\textsf{Sluice}$, a read-write streaming Groth16 prover that reduces $\textit{prove-phase}$ random-access working memory from $\mathcal{O}(N)$ to $\mathcal{O}(\log N)$ once the CRS, QAP, and witness are materialized as private streams. It preserves the standard Groth16 interface: a proof of 3 group elements, 3-pairing verification, and unchanged verifier contracts. Our key technical contribution is $\textit{Split-Butterfly-Merge}$ ($\mathsf{SBM}$), an NTT algorithm in the read-write streaming model with $\mathcal{O}(\log N)$ memory, $\mathcal{O}(N \log N)$ total I/O, and $\mathcal{O}(\log N)$ sequential passes over external storage. Combining SBM with streaming sparse R1CS evaluation and chunked Pippenger MSM yields a verifier-compatible Groth16 proving path that exchanges RAM for sequential storage I/O and wall-clock time. Our prototype uses a fixed-window MSM engineering point; the measurements validate memory reduction and proof compatibility, while the theorem states the asymptotically tuned MSM schedule. We implement $\textsf{Sluice}$ over BN-254. Direct prove-only runs produce valid 128-byte proofs through $N=2^{25}$. The same-size bounded-memory comparison is at $N=2^{23}$: $\textsf{Sluice}$ succeeds under an 8GB Linux cgroup cap, whereas the standard prover is killed under 8GB and 12GB caps and succeeds only at 16GB. These results position $\textsf{Sluice}$ as a storage-rich, RAM-limited proving option rather than a replacement for optimized in-memory provers.

Repeat--accumulate--accumulate (RAA) codes are sparse random linear codes with linear-time encoders. Although RAA ensembles can have linear minimum distance with high probability, this does not determine how often a randomly sampled code falls below a prescribed relative-distance threshold. We determine this lower-tail probability and identify the rare mechanisms that dominate it. Let \(n\) be the message length, \(r\ge4\) a fixed repetition factor, and \(N=rn\) the block length. For the randomly scaled ensemble \[ G=R\Pi_1V_1A\Pi_2V_2A, \] where \(R\) is repetition, \(A\) is the prefix-sum accumulator, \(\Pi_1,\Pi_2\) are independent uniform interleavers, and \(V_1,V_2\) have independent uniform nonzero diagonal entries in \(\mathbb F_q\), we prove that, for every fixed \(0<\delta\le1/2\) and \(\gamma>0\), \[ q-1\ge\gamma N \quad\Longrightarrow\quad \mathbb P[d_{\min}(G)\le\delta N] =\Theta_{r,\delta,\gamma}(N^{1-r}). \] For the unscaled ensemble \[ G_0=R\Pi_1A\Pi_2A, \] if \(\operatorname{char}(\mathbb F_q)>r\) and \(0<\delta\le1/10\), then \[ \mathbb P[d_{\min}(G_0)\le\delta N] =\Theta_{r,\delta}(N^{2-r}). \] Thus random scaling improves the failure probability by one power of \(N\). We also prove \[ \mathbb P[d_{\min}(G)\le\delta N] =\Omega_{r,\delta}\!\left( N^{1-\lceil r/2\rceil}(q-1)^{-\lfloor r/2\rfloor} \right), \] showing that linear field growth is necessary, in asymptotic order, for the constant-factor \(N^{1-r}\) law.

Expand–accumulate (EA) codes are sparse linear codes underlying constructions of correlated pseudorandomness and field-agnostic succinct arguments. In “Field-Agnostic SNARKs from Expand–Accumulate Codes” (CRYPTO 2024), Block et al. conjectured that a single fixed-row-weight EA component already achieves constant relative distance with inverse-polynomial failure probability. We prove this conjecture in a stronger, field-uniform form. For every rate $R\in(0,1)$, there exists $\delta_R>0$ such that, for every target exponent $C>0$, one can choose $\gamma=\gamma(R,C)>0$ for which the fixed-row ensemble with $t=\lceil\gamma\log N\rceil$ satisfies \[ \mathbb{P}\!\left[ \min_{x\in\mathbb{F}_q^{\lfloor RN\rfloor}\setminus\{0\}} \operatorname{wt}(xEA) \le \delta_R N \right] \le N^{-C} \] for all sufficiently large $N$. The same constants work for every prime power $q$; in particular, the field may vary arbitrarily with the block length. Thus, a single fixed-row-weight EA component is asymptotically good over all finite fields, and its polynomial reliability exponent can be made arbitrarily large by increasing the row-weight constant. The proof separates sparse and high-weight messages. Sparse messages are handled through expansion and a compact analysis of accumulator cancellations, while high-weight messages are controlled by a surplus of linear constraints over large fields and a stochastic accumulator analysis over bounded fields. A terminal-boundary obstruction shows that, for $t=\Theta(\log N)$, inverse-polynomial failure is qualitatively optimal.

Anonymous tokens with private metadata bit (ATPM) have received increased interest as a method for anonymous user authentication while also allowing the issuer to embed trust signals inside the token that are only readable by the authority who holds the secret key. However, all existing ATPM protocols require interaction during issuance as the client must send a blinded request and wait for the issuer to sign, introducing latency and scalability bottlenecks. In this work, we present the first Non-interactive Anonymous Token (NIAT) scheme with a private metadata bit. Our design builds on structure-preserving signatures on equivalence classes (SPS-EQ) and recent advances in non-interactive blind signatures. With NIAT, tokens can be issued without any online interaction, enabling asynchronous pre-computation and drastically reducing issuer workload. We formalize NIAT security definitions, propose an efficient construction under standard assumptions and experimentally evaluate its performance. We also present an extension to our NIAT construction that allows the identification of clients who attempt to double-spend a token (i.e., present the same token twice) and argue that non-interactive schemes are uniquely positioned to offer this essential feature.

Lattice-based blind signatures have attracted significant attention in recent years due to the rapid growth of digital currencies, the increasing demand for privacy-preserving digital interactions, and the ongoing transition toward quantum-resistant cryptographic primitives. While blind signatures provide anonymity guarantees, achieving fairness without compromising privacy to a third party remains a challenging problem. Blind adaptor signatures (BAS) address this limitation by enriching blind signatures with conditional-execution functionality, enabling fair exchange while preserving user anonymity. In particular, a BAS scheme allows a user to engage in an atomic swap with a verifier using an adapted blind signature obtained from a signer, thereby maintaining privacy against the signer while ensuring fairness between the user and the verifier. In this work, we observe that the ABDLOP commit-and-prove framework (CRYPTO 2022) exhibits a dichotomic structure that can be leveraged to realize adaptor functionality. Building on this, we propose a lattice-based blind adaptor signature (L-BAS) scheme that simultaneously achieves fairness along with the privacy guarantees of blind signing. Compared with the underlying lattice-based blind signature scheme, our construction incurs only a modest overhead, increasing the signature size by approximately 5.2 KB while largely preserving the efficiency of the original system. We formally analyze the security of the proposed construction and prove that it satisfies extractability, unique extractability, computational pre-verification soundness, one-more unforgeability, and blindness under standard lattice-based assumptions. Our results demonstrate that fairness can be incorporated into lattice-based blind signatures with minimal performance degradation, making the proposed scheme a practical candidate for privacy-preserving and quantum-resistant fair exchange applications.

In dynamic group signature schemes (GSS), forward security ensures that newly joined members cannot generate valid signatures for past time periods. Additionally, non-frameability prevents even privileged entities, such as the group manager or key issuer, from falsely attributing signatures to honest users. Most GSS either lack non-frameability or face significant efficiency challenges when updating signing keys to ensure forward security. In this paper, we introduce a forward-secure dynamic group signature scheme that guarantees non-frameability. We also present an alternative scheme that, while lacking non-frameability, offers higher efficiency compared to existing schemes with comparable security. For both protocols, we propose efficient revocation mechanisms that allow an authority to revoke users without requiring re-registering existing users. Additionally, we propose a technique that enables the verification process of both protocols to be performed in batches. We prove the security of our schemes, ensuring the standard dynamic GSS security notions; anonymity, traceability and non-frameability (second scheme). Experimental results demonstrate that our schemes are competitive in both computational and communication efficiency when compared to existing literature.

Lattice-based zero-knowledge proofs are now efficient enough for practical use, but in all known constructions a single prover holds the entire witness and is therefore a single point of failure. Thresholdizing them is understood only for three-round $\Sigma$-protocols, which certify shortness only $\textit{approximately}$. The $\textit{exact}$ statements needed by applications such as anonymous credentials require more rounds and rely on rejection sampling, and neither property survives thresholdization. We construct the first lattice-based threshold zero-knowledge proof systems for exact relations. The witness is Shamir-shared among $\mathtt{n}$ parties, any $\mathtt{t}$ of them can jointly produce a proof, and the proof has the same form as a single-prover proof, only a factor $\sqrt{\mathtt{t}}$ larger, with verification unchanged. We thresholdize the product proof of Attema, Lyubashevsky, and Seiler (CRYPTO 2020) and the exact proof of Esgin, Nguyen, and Seiler (ASIACRYPT 2020), making both rejection-free using Hint-MLWE and evaluating them over threshold homomorphic encryption. We define threshold commit-and-prove protocols with the corresponding zero-knowledge and simulation-extractability notions, and prove our constructions secure against passive adversaries that statically corrupt at most $\mathtt{t}-1$ parties. Of independent interest, we show that the Fiat--Shamir transforms of both proof systems are simulation-extractable in the random oracle model, and that MLWE remains hard when secrets are drawn from the subring fixed by a ring automorphism.

Private Set Operations (PSO) enable mutually untrusted parties to securely compute arbitrary functions (e.g., union, intersection, and cardinality) over their private input sets. These operations have wide applications in many real-world scenarios. Existing PSO protocols fall short of practical deployment for several reasons. (1) \textit{Function-specific}. Real-world privacy-preserving applications often require multiple set operations within the same task, while existing solutions typically address individual functionalities (e.g., intersection or union) in isolation, making it difficult and costly to support diverse set operations in a unified and efficient manner. (2) \textit{Lacking malicious security}. As PSO is commonly employed in highly sensitive applications, it is often necessary to provide strong security guarantees against malicious adversaries. Unfortunately, most existing works only achieve semi-honest security, which limits their practical applicability. (3) \textit{Restricted settings}. The majority of existing works focus exclusively on the two-party setting. How to extend them securely and efficiently to the multi-party setting while tolerating a malicious majority remains unclear. To date, designing a maliciously secure multi-party PSO (mPSO) framework that efficiently supports diverse set operations remains an open challenge. This paper presents the \textit{first} maliciously secure mPSO framework, named UM-PSO, that supports a broad range of set operations with practical efficiency. At the core of our framework is a function-independent preprocessing phase that prepares a reusable pool of secret-shared items, which can then be leveraged to securely compute diverse set functionalities in the online phase. To achieve malicious security efficiently, we design verification mechanisms on top of SPDZ-based authenticated secret sharing, along with tailored techniques and optimizations to further improve practical performance. We implement our protocols and report concrete performance results. For a representative setting with 5 parties and a total of $2^{12}$ 128-bit items, our framework achieves an online running time of $0.627$ seconds and incurs $3.35$ MB of communication. Compared to the baselines, our framework achieves up to $51\times$ speedup and up to a $76\times$ reduction in communication.

Modern public-key cryptography is threatened by advances in quantum computing. As a result, there has been a shift towards cryptographic algorithms that can resist attacks by a quantum computer. However, these algorithms use significantly longer keys, and produce larger ciphertexts and digital signatures than their classical counterparts. These bigger sizes pose problems for devices that are bandwidth- and/or power-limited, and wish to establish a secure, quantum resistant communication channel with another device. In order to reduce the overhead of using these algorithms in challenging environments while maintaining security posture, we present Compact Authenticated Key Exchange – Hiding Identities (CAKE-HI). To evaluate our protocol, we compare the key exchange handshake size and computational efficiency of mutual authenticated TLS and CAKE-HI. Measurements show that CAKE-HI significantly reduces the handshake size and the computational overhead of establishing a quantum-secure link. In addition, we formalize and prove security properties about CAKE-HI in the symbolic and computational model using the protocol analysis frameworks Verifpal and CryptoVerif.

Oblivious transfer (OT) is a foundational tool in secure computation. Random OT-correlated pairs of the form $(r_0,r_1)$ and $(b,r_b)$, where $r_0,r_1,b \stackrel{{}_\$}{\leftarrow} \{0,1\}$, significantly speed up secure computation protocols. Pseudorandom correlation functions (PCFs), introduced by Boyle et al. (FOCS 2020), are an efficient means of non-interactively generating correlated pairs. In a PCF, two parties store short keys that are used to locally generate large amounts of correlated pairs. While pre-quantum PCFs for OT achieve highly compact key sizes (e.g., $30$ kB), a significant gap remains in the post-quantum regime, where existing solutions rely on lattices or learning-parity-with-noise-style assumptions and yield much larger keys. We construct compact post-quantum PCFs for OT. Our construction has key sizes in the range of $100$ kB, approaching the compactness of pre-quantum PCFs and seven times smaller than the most compact state-of-the-art post-quantum alternatives. The key size of our PCF remains invariant regardless of the target number of OTs, in contrast to prior alternatives. We estimate a throughput of $7$ OTs per second for our PCF. We additionally provide a security proof in the quantum random oracle model, constituting the first such analysis of a post-quantum PCF. The core of our construction is a new, compact constrained pseudorandom function (CPRF) for inner-product membership predicates. Its security is based on a natural extension of the parallelization problem, which we introduce as the parallelization problem with auxiliary inputs. We provide an extensive analysis of this assumption as well as an implementation of our construction.

We present the first fully distributed, code-based polynomial commitment scheme (PCS) that achieves linear prover time and polylogarithmic communication for multilinear polynomials. Our construction builds on Brakedown with proof composition. We design a distributed proof of correct linear encoding. Codeword validity is reduced to a sumcheck relation over the sparse parity-check matrix, whereas systematic consistency is verified through multilinear evaluation checks. These techniques preserve linear prover complexity while reducing the communication size between sub-provers to polylogarithmic scale. We implement our construction and evaluate it on multilinear polynomials ranging in size from $2^{22}$ to $2^{28}$. The prover exhibits near-linear parallel scalability. Compared with existing evaluated distributed PCS implementations with 8 parties, it reduces communication by at least $13\times$ at every tested polynomial size, while its prover time remains within $1.31\times$ of the fastest implementation. These results demonstrate that our asymptotic communication improvements translate into substantial concrete savings while retaining efficient proving.

Folding/Accumulation schemes are a powerful tool for building scalable proof systems. However, standard approaches for leveraging folding schemes, such as IVCs or PCDs, require embedding hash functions (modeled as random oracles) into recursive circuits, introducing both security concerns and significant proving overhead. We re-envision how to use folding schemes, and introduce Symphony, the first proving paradigm that leverages folding schemes as a black box without embedding hashes in SNARK circuits. It is memory-efficient, parallelizable, and plausibly post-quantum secure, with polylogarithmic proof size and verification. The (low-memory) prover requires O(log log n) passes of the input data and its computation is dominated by committing to the input witnesses. A core component of our construction is a new lattice-based folding scheme that compresses a large number of NP-complete statements into one in a single shot. Furthermore, we design a generic compiler that converts a folding scheme into a SNARK without embedding the Fiat-Shamir circuit into proven statements.

Practical implementations of synchronous MPC protocols typically require each party to advance to the next round as soon as they have received all expected messages. This deviates from the theoretical synchronous round-based model, where instead each party advances in the next round after a timeout. To capture this gap between theory and practice, Asharov, Chandramouli, Cohen and Ishai in Eurocrypt 2025 proposed a new model where the adversary is super-rushing. In this, the adversary can see future messages of some honest parties before delivering current-round messages to slower ones. In this work, we study super-rushing security in both the computational and statistical settings, and design round-preserving compilers that transform standard synchronous MPC protocols into ones secure against super-rushing adversaries. Ours is the first work to investigate the security of computational MPC protocols against a super-rushing adversary.

Zero-knowledge execution of high-level programs proceeds by repeatedly evaluating CPU steps. Each such step privately selects and evaluates an instruction (possibly involving memory access) from a rich instruction set. Building on this paradigm, ZEE (Heath et al., S&P'21) realized a full toolchain supporting arbitrary $\texttt{ANSI C}$ programs, demonstrating this capability by proving SIR- and CVE-reported bugs in off-the-shelf Linux programs $\texttt{sed}$ and $\texttt{gzip}$. We revamp the state of the art by building a new constant-round ZK system ZEE200, which is about $20\text{-}40\times$ faster than ZEE. ZEE200 is built on a novel and convenient cryptographic framework for efficiently proving general statements represented as real-world programs. Our framework integrates several crucial recent advances, such as Tight ZK CPU (Yang et al., CCS'24) and fast ZK RAM (Yang and Heath, USENIX Security'24). We develop better encodings for $\mathbb{Z}_{2^{32}}$ arithmetic, and numerous low-level optimizations. Compared to ZEE's $\approx 10$ KHz CPU speed on a limited ISA, ZEE200 runs at $\approx 200$ KHz (still on a commodity laptop and a LAN!), while supporting a much richer ISA. For example, we rerun a ZEE's benchmark, proving a SIR-reported vulnerability in off-the-shelf Linux utility $\texttt{sed}$. On a 2021 ThinkPad X1 Carbon Gen 9 under a simulated $1$Gbps LAN (single-threaded), ZEE200 completed the proof in $1.5$ seconds, compared to ZEE's $30.1$ seconds, a $20\times$ improvement.

Secure comparison is a fundamental building block frequently employed in various applications of secure multiparty computation, such as secure machine learning. Such protocols based on secret sharing (SS) typically excel in throughput, but they historically suffer from higher (online) round complexity. To address this issue, Attrapadung et al. (AsiaCCS 2022) proposed a protocol with two online rounds in the client-aided model (i.e., assuming a trusted third party in the offline phase), and Lu et al. (USENIX Security 2025) proposed a protocol with three online rounds in the plain model. In this paper, we propose a plaintext comparison protocol with two online rounds in the plain model. While keeping the lowest online round complexity, our protocol also reduces the total bit complexity. For example, for the case of 64-bit integers, the total bit complexity of our protocol is 25.7% of Lu et al.'s protocol and 23.3% of Attrapadung et al.'s protocol adjusted to the plain model.

Linear error-correcting codes with fast encoding and high minimum distance are a central primitive across modern cryptography. They appear prominently in at least two domains: (1) pseudorandom correlation generators (PCGs), which enable sublinear-communication generation of correlations such as oblivious transfer and vector oblivious linear evaluation, and (2) zero-knowledge proof systems, where linear-time encoders underpin proof soundness and scalability. In both settings, the prover or sender must multiply by a large generator matrix $\mathbf{G}$, often with dimensions in the millions, making computational efficiency the dominant bottleneck. We propose a generalized paradigm for building crypto-friendly binary codes with provable minimum distance. Roughly speaking, these codes are based on randomized turbo codes such as repeat-accumulate codes. We prove linear asymptotic minimum distance and compute the exact expected weight spectrum for concrete sizes. We observe that our codes approach the Gilbert-Varshamov distance bound and outperform prior constructions. We construct several novel codes, the most promising of which we call Block-Accumulate codes. Among codes with provable distance, our code is $8\times$ faster than the state of the art on a CPU and $50\times$ faster on a GPU; even against aggressive parameters with conjectured distance, it is $3\times$ and $20\times$ faster, respectively. Under these parameters, this yields overall PCG speedups of $2.5\times$ on the CPU and $15\times$ on the GPU, achieving a projected 200$+$ million OTs per second, or about 100 million binary Beaver triples per second, on the GPU (excluding the one-time 10 ms GGM seed expansion). We also observe a $2\times$ encoding speedup and half the peak memory consumption in the Blaze zero-knowledge (PCS) scheme of Brehm et al. (EUROCRYPT~'25).

We propose a new private Approximate Nearest Neighbor (ANN) search scheme named Pacmann that allows a client to perform ANN search in a vector database without revealing the query vector to the server. Unlike prior constructions that run encrypted search on the server side, Pacmann carefully offloads limited computation and storage to the client, no longer requiring computationally-intensive cryptographic techniques. Specifically, clients run a graph-based ANN search, where in each hop on the graph, the client privately retrieves local graph information from the server. To make this efficient, we combine two ideas: (1) we adapt a leading graph-based ANN search algorithm to be compatible with private information retrieval (PIR) for subgraph retrieval; (2) we use a recent class of PIR schemes that trade offline preprocessing for online computational efficiency. Pacmann achieves significantly better search quality than the state-of-the-art private ANN search schemes, showing up to 2.5$\times$ better search accuracy on real-world datasets than prior work and reaching 90\% quality of a state-of-the-art non-private ANN algorithm. Moreover on large datasets with up to 100 million vectors, Pacmann shows better scalability than prior private ANN schemes with up to $63\%$ reduction in computation time and $24\%$ reduction in overall latency.

The main barrier to practical fully homomorphic encryption remains the latency and cost of bootstrapping, the ciphertext refresh step that enables unbounded computation. We design new methods that reduce both the latency and the circuit depth of bootstrapping in the FHEW/TFHE framework, which represents the state-of-the-art for lightweight bootstrapping and for computing deep and unstructured Boolean functions over encrypted data. Our first contribution leverages LWE with a sparse small-norm secret, an assumption known to be equivalent to standard LWE and already widely used in FHE constructions. For an LWE secret of dimension $n$ and Hamming weight $h$, we obtain bootstrapping procedures whose arithmetic complexity decreases from $\tilde O(n^2)$ to $\tilde O(n h)$ $\mathbb{Z}_q$ multiplications while preserving the same asymptotic number of additions. Concretely, this yields a $4.5$--$7.5\times$ practical speedup for gate and functional bootstrapping over the state-of-the-art OpenFHE implementation. Our second contribution introduces a new RLWE variant with structured secrets, called \emph{\mainrlwevarianttext}, and uses it to significantly reduce the circuit depth of FHEW/TFHE bootstrapping via a new relinearization-free BV multiplication technique. In concrete parameter settings, this reduces the number of sequential NTT/INTT layers required for bootstrapping to just 3, compared to more than 500 in standard FHEW/TFHE, while keeping the overall number of unit 32 or 64-bit word operations comparable to standard FHEW/TFHE bootstrapping. This substantial depth reduction suggests the potential for significantly lower bootstrapping latency on parallel, high-throughput architectures such as GPUs. Finally, we analyze the security of the new RLWE assumption underlying our depth reduction, including worst-case-to-average-case and search-to-decision reductions, as well as evaluations against concrete attacks.

We remove the Boneh--Lipton conjecture from the proof of Corrigan-Gibbs and Wu (CRYPTO~2024) that Jacobi signatures modulo $N=p^2q$ are one-way. This relates the one-wayness of the pseudorandom generator proposed by Damg{\aa}rd in 1988 to a standard number-theoretic problem alone.

Several decentralized applications and blockchains, such as blockchain-based voting systems or Proof-of-Social-Capital, require a strict one-account-per-person policy, yet public identity records often expose sensitive attributes or enable offline attribution. This work presents a Proof-of-Uniqueness blockchain-based registry that composes an issuer-signed verifiable credential, two zero-knowledge proofs, a threshold verifiable oblivious pseudorandom function (vOPRF), and a smart contract. The first proof authorizes a blinded evaluation of an issuer's certified canonical identifier, and the second validates the OPRF transcript and binds the resulting global nullifier to a wallet. The design further binds issuer authorization, credential status, validity bounds, canonical encoding, and replay state. Its person-level guarantee is conditional on a stable injective identifier within a coordinated issuance namespace and a stable, valid OPRF key. Confidentiality holds against public observers and against fewer than the OPRF threshold of nodes, but not against an issuer that actively probes its own identifiers. Our prototype couples Noir and UltraPlonk circuits, three local threshold OPRF nodes, and a Solidity contract. For one fixed-schema credential input, it derives a single wallet-bound deterministic nullifier, verifies a real 2,144-byte proof on-chain, and rejects a repeated nullifier with $O(1)$ lookups. One real enrollment consumes 615k gas, and proof construction takes about 65 seconds on one desktop software thread.

Private Set Union (PSU) allows two parties to compute the union of their private sets while revealing nothing beyond the union. Existing PSU protocols mainly follow two paradigms: reverse private membership test (RPMT) and invertible Bloom lookup table (IBLT). IBLT-based protocols achieve linear complexity using lightweight symmetric-key operations and offer excellent concrete efficiency. RPMT, on the other hand, provides a more general membership-testing functionality that can serve as a reusable building block for PSU and other private-set computations. However, existing RPMT-based protocols either rely on costly building blocks, such as public-key operations and generic secure two-party computation, or incur super-linear complexity. This raises a natural question: can the generality of the RPMT paradigm be retained while matching the asymptotic and concrete efficiency of IBLT-based PSU? In this work, we answer this question affirmatively by introducing a lightweight mechanism for multi-query membership testing. Our mechanism yields a concretely efficient multi-query RPMT (mqRPMT) protocol that is useful beyond PSU and may be of independent interest. Building on this protocol, we construct a PSU protocol with linear computation and communication complexity. Our construction avoids expensive public-key operations and generic secure two-party computation, relying instead on efficient symmetric-key primitives. We extensively evaluate our protocol against state-of-the-art PSU protocols from both the RPMT and IBLT paradigms. Compared with the leading RPMT-based PSU protocol from PKC 2024, our construction is $41.7\times$ $-$ $48.9\times$ faster in the LAN setting and up to $4.5\times$ faster in WAN settings. Compared with the leading IBLT-based PSU protocol from EUROCRYPT 2026, our protocol achieves competitive and, in several metrics, superior performance: it is $1.9\times$ $-$ $2.5\times$ faster in LAN settings and reduces communication by up to $1.4\times$. These results demonstrate that the broader applicability of the RPMT abstraction need not come at the cost of asymptotic or concrete efficiency.

The idea of computing on encrypted data without decryption dates back to the notion of privacy homomorphisms introduced by Rivest, Adleman, and Dertouzos (1978). Their proposals built using the elegant structure of Chinese Remainder Theorem (CRT), were later shown to be insecure under simple known-plaintext attacks. Subsequent CRT-based fully homomorphic encryption (FHE) over the integers addresses this algebraic transparency by injecting noise and basing security on approximate common divisor–type assumptions, but the resulting designs are burdened by large public keys and costly ciphertext refresh procedures. In this work, we develop a new CRT-based FHE scheme whose security relies on the Ring-LWE (RLWE) hardness assumption. For this purpose, we introduce the CRT-RLWE problem. We show that the problem is at least as hard as the RLWE, thereby positioning our construction within the established post-quantum security landscape of RLWE-based cryptography. Our scheme retains an explicit CRT embedding, separating a message component modulo a prime-power plaintext modulus and an auxiliary CRT component, while using RLWE-style key and ring arithmetic for compactness and efficiency. Finally, we make it fully homomorphic by using a new bootstrapping procedure, that adopts the recryption paradigm for BGV/BFV schemes utilizing the linear transformation and digit extraction techniques.

In many secure multiparty computation (MPC) applications, the semantic domains of some operands are much smaller than the underlying arithmetic field or ring. The arithmetic domain is typically chosen to meet computation and security requirements (e.g., a 128-bit prime field), whereas the actual data may consist of only a few bits, such as 4-bit values in a 16-category classification task. This mismatch can lead to substantial communication and computation overhead in existing MPC protocols, which typically treat data of different ranges uniformly. We introduce UFO$_\mathrm{s}$, an ultra-fast toolkit for MPC on small elements, with optimized protocols for one-hot encoding, comparison, and digit decomposition. For $t=2^k$, our random one-hot vector generator attains, in the fan-in-two arithmetic-circuit model, the lower bounds of $t-\log t-1$ multiplication gates and $\lceil\log\log t\rceil$ multiplication depth. Our comparison protocol applies to any public small domain, while DigitDecomp avoids binary expansion and supports any public base $t>1$. Using these primitives, we construct a higher-radix sorting protocol for large field elements. Experiments confirm the resulting gains in random one-hot vector generation, digit decomposition, and sorting. In particular, our sorting protocol achieves a $3.4\times$ online and $1.4\times$ offline speedup over Hamada et al.'s radix-sort baseline when sorting $2^{16}$ elements among five parties.

A universal, dynamic accumulator is a verifiable data structure that compresses a set of elements (e.g., unspent coins, issued public key certificates, etc.) into a succinct digest while supporting addition and deletion of elements alongside efficient proving of (non-)membership in that set. In many applications, valid (non-)membership proofs are a prerequisite to accessing a service (e.g., sending a private payment transaction, establishing a TLS connection, etc.). Typically, newly added or deleted elements necessitate updating all existing (non-)membership proofs per update. Thus, intermittently connected clients will possess invalid (non-)membership proofs whenever they reconnect. In this work, we design, implement, and evaluate algorithms for the RSA and bilinear accumulators that allow a resource-constrained client to privately delegate the updates of its (non-)membership proofs to an untrusted server. We define and prove security in a game-based framework under standard assumptions. We also study proof delegation in the batch setting. The online client algorithms are constant-time, i.e., independent of the updated set size $k$, compared to prior $\mathcal{O}(k),\mathcal{O}(\sqrt{k})$ works. The private delegation algorithms for membership proofs incur an asymptotically constant computational overhead for the server (e.g., $6.12\times$ overhead when $2^{10}$ elements were added in the offline phase to the RSA accumulator) compared to the non-private membership proof creation algorithms.

Motivated by the 2026 COLDCARD incident, this paper studies cryptographic asset recovery after self-custodial seed-generation failures. Self-custodial hardware wallets depend on secure entropy sources for seed generation. If an RNG implementation or design failure reduces seed entropy, an adversary may reconstruct wallet signing keys through offline search. Such weaknesses may also be discovered long after wallet creation, placing existing self-custodial assets at risk. To prevent large-scale exploitation after such a failure is identified, a hardware manufacturer or security response team may perform a protective sweep of affected assets into a protected recovery treasury. Asset redistribution then creates a fundamental authentication problem: once the signing key can be reconstructed by both the legitimate owner and an adversary, possession of that key no longer uniquely identifies the legitimate controller. We propose Z-SCAPE, a zero-knowledge recovery-credential protocol for privacy-preserving asset recovery after seed-generation failures and protective sweeps. Before compromise, the user commits to a recovery credential consisting of a 256-bit recovery secret $r$ generated from an entropy source intended to be independent of the transaction-signing seed, and an RNG-independent personal record $P$. After an incident, the prover proves knowledge of $(P,r)$ in zero knowledge for the pre-bound wallet identifier $W$, while binding the proof to the incident-specific protected-asset reference, a fresh verifier nonce, an expiry value, and a fresh recovery destination. The verifier derives the protected-asset reference from authenticated protective-transfer records rather than accepting an arbitrary asset set from the claimant. The protocol enables recovery claims without revealing $P$, $r$, or the compromised wallet private keys, while preventing replay, destination substitution, and cross-wallet protected-asset substitution. Z-SCAPE provides concrete integration mechanisms for Bitcoin and Ethereum and enables only assets recorded as protectively transferred from the proved wallet to be returned to the fresh destination bound to an accepted recovery proof.

We propose NAIBI-Full, a lattice-based key encapsulation mechanism (KEM) together with its forward-secure ephemeral key-agreement protocols, built on the regular representation $\rho$ of the non-split commutative algebra $\mathcal{A}_\alpha = R_q[y]/(y^k - \alpha)$ over $R_q = \mathbb{Z}_q[x]/(x^n + 1)$, with $k \in \{2,3\}$ and $\alpha$ a non-$k$-th power. Each party publishes the full matrix $\mathbf{t} = A\rho(\mathbf{s}) + \mathbf{e} \in R_q^{k \times k}$; because $\rho(\mathcal{A}_\alpha)$ is commutative, the cross-product collapses to small noise and a Peikert hint closes the gap to exact agreement, even though the public matrix $A$ is fully generic in $M_k(R_q)$. Hardness rests on a single, well-localised assumption: structured-secret Module-LWE $\mathrm{MLWE}_\rho$, which we identify exactly with a $\rho(y)$-linked $k$-sample MLWE problem via column decomposition, placing it inside the well-cryptanalysed MLWE landscape of ML-KEM. NAIBI-Full is the conservative member of the family: a clean account in terms of a standard lattice assumption, at the cost of $k^2$-element public keys and ciphertexts. Three primitives follow from this single core: an IND-CCA2 KEM (the $\mathrm{FO}^{\not\bot}$ transform, i.e. with implicit rejection, in the ROM and QROM) and two forward-secure ephemeral protocols, ephemeral-static and ephemeral-ephemeral. For the KEM we prove in addition a statistical, decapsulation-level binding correctness guarantee, with collision probability at most $(2/3 + 1/(3q))^{\lceil n/2 \rceil} + (8/q)^{n/2} + 2^{-256}$, below $2^{-148}$ at every parameter set. That binding survives in the malicious-key model on the public-key axis (MAL-BIND-K-PK, with a $q_H$ factor on the mechanism term), with no distributional assumption on the adversarial keys: the property ML-KEM is known to lack, and which the seed key format of FIPS 203 (which does restore the ciphertext axis) still leaves unattained. The statistical modality attaches to the accept branch; on the rejection branch, where no KEM admits a statistical guarantee, the rejection key hashes the public key, without which the notion falls to a one-line attack reusing a single $z$ across two malicious keys. We deliberately offer no static-static mode, since it would inherit the active key-mismatch attacks of the Ding/Peikert/NewHope family; NAIBI-Full is confined to its key-mismatch-resistant deployments. Parameter sets cover NIST security Categories 1, 3 and 5, all with $\delta \le 2^{-128}$.

Continuous group key agreement (CGKA), the cryptographic core of Messaging Layer Security (MLS, RFC 9420), provides key management for large end-to-end encrypted group chats. It refreshes the group's keys as members join and leave, but offers no way for a designated auditor to recover past epoch keys, and no way to check that such recovery remains possible. Regulated deployments in finance, healthcare, and government therefore resort to plaintext server logging, abandoning end-to-end encryption entirely. Simply adding a key escrow admits a silent escrow failure: the group accepts an epoch whose escrow holds unrecoverable material, with no visible anomaly until a later audit. Addressing this, we introduce auditable CGKA (Au-CGKA), an MLS-shaped protocol in which every admitted epoch carries a proof. The proof binds that epoch's key material to a well-defined secret recoverable by a threshold auditor committee. Every member checks that binding against the epoch secret it derives and refuses the commit if the two disagree, so auditability guarantees that the secret of every epoch an honest member accepts is threshold-recoverable. We give a post-quantum protocol, Π_A, realizing this property with STARK proofs. The committer escrows the epoch secret to an auditor committee, and the escrow ciphertext is a STARK-friendly encryption of Shamir shares. Its well-formedness is proven in-circuit at MLS commit time. We prototype Au-CGKA in Rust with the proofs on a zero-knowledge, post-quantum custom multi-stage STARK. On an Apple M5 Pro, an auditability proof takes 1.38 s with proof-size 15.31 MB and verifies in 0.17 s, at every group size; the relation it proves is independent of the group size. The proof is checked at admission and then discarded, so it costs bandwidth on the commit and nothing in storage; the only persistent overhead is the fixed-size escrow. Adaptive post-quantum security holds in the secure-erasure model with straight-line reductions in the quantum random-oracle model, and carries to the implemented backend under a stated assumption; privacy and escrow soundness follow as game-based guarantees.

Fully Homomorphic Encryption (FHE) enables computations on encrypted data, ensuring privacy for outsourced computation. However, verifying the integrity of FHE computations remains a significant challenge, especially for bootstrapping, the most computationally intensive operation in FHE. Prior approaches, including zkVM-based solutions and general-purpose SNARKs, suffer from inefficiencies, with proof generation time ranging from several hours to days. In this work, we propose HasteBoots, a succinct argument tailored for TFHE with programmable bootstrapping. By designing efficient protocols for arithmetic operations over quotient rings, HasteBoots achieves proof generation in a few seconds for TFHE evaluation with programmable bootstrapping, significantly outperforming the state-of-the-art, Zama (CCS'25). Moreover, HasteBoots supports batching multiple TFHE evaluations and bootstrappings, a feature that prior work cannot practically support due to prohibitive proving cost. HasteBoots can prove a batch of 16 operations within one minute, while maintaining succinct verification, requiring only 126 ms and a proof size of 0.28 MB. Our approach demonstrates the potential for scalable and efficient verifiable FHE, paving the way for practical, privacy-preserving computations.

Post-quantum migration of Transport Layer Security (TLS) is often described as replacing a classical key-exchange algorithm with a post-quantum alternative. This framing is incomplete: TLS distributes security across key establishment, authentication, resumption and pre-shared keys (PSKs), traffic-secret evolution, and the X.509/PKIX ecosystem. These functions have different security objectives, failure modes, lifecycle dependencies, and deployment constraints. This Systematization of Knowledge (SoK) develops a functional framework for analyzing post-quantum TLS migration as an architectural problem rather than a single algorithm transition. We systematize classical, pure post-quantum, and hybrid key establishment; TLS 1.3 PSK modes and resumption; KeyUpdate; ML-KEM; ML-DSA and SLH-DSA; hybrid and composite authentication; X.509/PKIX and trust-anchor migration; HSM dependencies; interoperability; performance; deployment environments; cryptographic inventory; and crypto-agility. We classify evidence by mechanism, security objective, source of keying material, forward-secrecy behavior, quantum threat, post-compromise behavior, communication and computational cost, interoperability dependency, standardization status, deployment evidence, and migration complexity. We explicitly separate finalized standards from evolving Internet-Drafts and implementation-specific evidence. The systematization produces four analytical conclusions. First, confidentiality migration and authentication migration are coupled operationally but distinct security programs. Second, hybrid ECDHE-ML-KEM is a strong transitional architecture for confidentiality migration when the relevant TLS integration and implementation support are available, because its security objective can tolerate failure of one component; the exact security claim nevertheless depends on the standardized construction and its assumptions. Third, PSKs, resumption, and KeyUpdate are not interchangeable forms of rekeying: their security depends on the provenance and role of the secret, while KeyUpdate remains within an existing traffic-secret lineage and does not create an independent post-quantum secret. Fourth, deployment readiness is constrained as much by certificates, trust stores, HSMs, middleboxes, inventory, and interoperability as by primitive availability. We therefore derive a migration decision framework that prioritizes HNDL-sensitive data, controlled hybrid deployment, interoperability testing, staged authentication and PKI migration, and observable retirement of classical-only mechanisms.

Secure function evaluation (SFE) and private function evaluation (PFE) are fundamental primitives in multiparty computation. In SFE, multiple parties jointly compute a \textit{public} function over private inputs while revealing nothing beyond the output, whereas in PFE the function itself is \textit{private} and known only to a designated party. In this work, we focus on the semi-honest setting and present more efficient information-theoretic constructions for both SFE and PFE. For SFE, the classical BGW protocol incurs $O(n^2)$ communication per multiplication gate. The DN protocol (Damg\aa rd and Nielsen, Crypto 2007) reduces the amortized communication to linear but still require an additional $O(n^2)$ term, yielding $O(m^* n + n^2)$ communication for $m^*$ multiplication gates. This becomes suboptimal in the regime $m^*= o(n)$. We introduce a simple technique that removes this quadratic overhead, achieving strictly linear $O(m^* n)$ communication. For PFE, the only existing information-theoretic approach relies on universal circuits, which results in $O(m^5n+n^2)$ complexity for arithmetic circuits. We develop new techniques that avoid universal circuits entirely. Combined with our SFE improvements, this yields an honest-majority PFE protocol achieving $O(m^2n)$ communication for circuit size $m$. We further obtain improved efficiency in special cases, including a three-party protocol with $O(m^{4/3})$ communication, and an $n$-party protocol tolerating one corruption with $O(m^{(2n-2)/(2n-3)}n)$ communication.

A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to jointly establish a cryptographic session key, in the "password-only" setting where the only information shared in advance is a low-entropy password. In recent years, the One-encryption EKE with 2-round Feistel cipher (OEKE-2F) protocol, a compiler from Key Encapsulation Mechanism (KEM) to PAKE, has received much attention, for the following reasons: (1) When instantiated with the Diffie–Hellman KEM, it is the most computationally efficient PAKE protocol to date that is secure in the Universal Composability (UC) framework; and (2) When instantiated with a post-quantum KEM, it provides a generic way to construct efficient PAKE protocols based on post-quantum assumptions. Unfortunately, the community cannot agree upon what the OEKE-2F protocol exactly is: part of the second protocol message is an RO hash of the KEM key, together with any number of the following: - The password, - The KEM public key, - The first protocol message, and - The KEM ciphertext. This yields 16 potential variants of OEKE-2F; only two of them have been studied in the literature, and their pros and cons are poorly understood. In this work, we present a comprehensive analysis of *all 16 variants* of OEKE-2F, proving the UC-security of each of them. The general takeaway is that the "hash everything" version requires the fewest security properties of the underlying KEM scheme, and the more items we remove from the hash, the more security requirements the KEM scheme has to satisfy — although all of the additional KEM properties are still mild. We pinpoint the exact KEM properties each version of OEKE-2F needs, and thoroughly explain the rationales. The significance of this work lies in that it helps the community converge upon the "right" version of OEKE-2F, and perhaps also in that this is the first paper by the author that is over 100 pages.

Traditional deniable encryption denies the \emph{content} of secret communications by allowing plausible alternative plaintexts under coercion. But the recognizable use of a deniable-encryption tool can itself defeat the purpose: a revealed plaintext becomes suspicious once a coercer detects that a non-standard tool was used, and fully encrypted, format-anomalous traffic is already detected and acted upon by deployed censorship systems. This motivates a second axis of deniability, the deniability of the mechanism's \emph{use}, which we call \emph{second-order deniability} (2OD) and treat as a design goal rather than a single achievable primitive. We decompose 2OD into two formally separate properties: \emph{content deniability} (CD), that a coercer holding all disclosed keys cannot identify the true message among decoys, and \emph{existence deniability} (ED), that the transmitted ciphertext is indistinguishable from the output of a fixed, standard reference protocol. We give game-based definitions of CD and ED, prove that the two are logically independent, and present PhantomCrypt, a construction that composes False-Bottom Encryption (CD) with Invisible Encryption (ED) under a post-quantum hybrid KEM/AEAD envelope. We are deliberate about what each guarantee buys. ED, as we define and prove it, is the indistinguishability of the transmitted ciphertext \emph{object} from a single, explicitly specified reference distribution (a standard hybrid KEM/AEAD wrapper over an unmodified cover string); it reduces to KEM and AEAD security. It is \emph{not} a claim of traffic-analysis resistance, and it is conditional on an assumption we make explicit rather than prove: that the chosen cover string is itself unremarkable to the observer. CD we prove negligible in the random-oracle model, conditioned on the secrecy of a pre-shared seed, with the residual advantage controlled by two explicit quantities: the seed's entropy relative to the field size, and a cover-concentration term that we introduce here and bound by a min-entropy admissibility condition validated on real text. Post-quantum security enters through the envelope only: ED reduces to ML-KEM and AEAD security against a quantum distinguisher, whereas the CD argument is statistical and stated in the classical random-oracle model, so we claim a post-quantum \emph{envelope} rather than post-quantum deniability wholesale and leave a QROM treatment of composed CD open. We further show that this coupling is sharp: a feasibility threshold separates a regime where strong deniability holds from one where it is information-theoretically impossible, governed by the seed-entropy margin relative to the plausible-message entropy. We are explicit about the boundary throughout: ED is object-level indistinguishability, not a defense against traffic analysis or device-side software forensics, and we state where full 2OD does and does not hold. A proof-of-concept implementation encrypts a 32-byte message with three decoys in under 10\,ms on commodity hardware, with scaling measured across cover-text length and decoy count.

Key transparency enables a centralized encrypted messaging provider to publicly commit to the public keys it distributes, allowing clients to detect potentially malicious keys. Recent deployments by WhatsApp and iMessage demonstrate the promise of this approach, but they rely on third-party global auditors to detect misbehavior by the key server. No existing system supports auditing efficiently enough to be done by lightweight end users while also providing scalability to billions of users and short epoch latency. We present $\mathsf{Aegon}$, a key transparency scheme designed for global-scale encrypted messaging. Building on ideas from $\mathsf{IronDict}$, $\mathsf{Aegon}$ avoids per-epoch work that scales with the full dictionary size: its server computation depends only on the number of updates in the current epoch, eliminating global invariance proofs and enabling epoch latency of under a minute ($500\times$ reduction compared to $\mathsf{IronDict}$). $\mathsf{Aegon}$ further introduces a sharded dictionary design that reduces global parameters to shard-dependent sizes and enables horizontal scaling. To control long-term storage, $\mathsf{Aegon}$ uses proof caching to safely discard historical dictionary snapshots, so storage grows only with retained history. We provide a production-grade Rust implementation of $\mathsf{Aegon}$ and demonstrate practical scalability to a dictionary with $4$ billion entries, comparing it against the public codebase of WhatsApp Key Transparency ($\mathsf{AKD}$). At the throughput of $1{,}250$ updates per second, $\mathsf{Aegon}$ produces constant-size auditor proofs of under $30$ KB, verifiable in under $65$ ms and independent of the number of updates per epoch or of the directory fill. At a fully-populated $2^{32}$-entry directory, this is roughly an $80{,}000\times$ reduction in audit proof size and a $370\times$ reduction in verify time relative to $\mathsf{AKD}$. All other server and client operations remain highly efficient and comparable to $\mathsf{AKD}$, while $\mathsf{Aegon}$ achieves stronger privacy guarantees.

Function secret sharing (FSS) gives two parties succinct keys whose local evaluations add up to a hidden function value. Removing the dealer is the natural next step for preprocessing-based secure computation, but malicious security then requires more than checking a finished key: the generation transcript, the function the key actually computes, and every released evaluation share must all be bound to one execution. We call this the cross-phase binding problem, and we solve it. We present VeriFSS, a dealer-free two-party FSS scheme with active security, proved in the standard simulation-based framework against one static malicious corruption. The construction rests on a two-plane key: the distributed generator produces a key for the paired function $x\mapsto(f_\theta(x),\Lambda f_\theta(x))$, where $\Lambda$ is a secret global authentication scalar. The second plane makes every local evaluation an authenticated sharing for free, which yields online report binding without vector commitments, extractable hashing, or per-point interaction. It also supplies the ingredient the audit was missing: we prove a moment-fidelity lemma showing that a corrupted party cannot misreport the full-domain moments of its own sealed key except with probability $3/|E|$ over the challenge set $E$, and a shape-identification lemma showing that three moment equations pin a point function down exactly, with error $2n/|E|$ over any field. The proof isolates the coefficient of the square monomial in the support polynomial and is therefore characteristic-free; in characteristic two an odd-size equal-weight support defeats the support equation on its own, and we show the position equation takes over. A discrete-derivative reduction carries both lemmas to comparison functions, and a Galois-ring variant covers fixed-point payloads over $\mathbb{Z}_{2^k}$ by a $2$-adic valuation argument, so no non-additive lift into a binary field is ever needed. Generation costs two rounds and five field elements per party per level; certification adds $O(n)$ elements with no dependence on the domain size, and a dynamic cross-domain aggregation certifies arbitrarily many heterogeneous instances under one challenge and a constant number of rounds. We then lift the general-purpose FSS gates of Boyle et al. (EUROCRYPT 2021): every gate that is a public affine post-processing of a constant number of DPF/DCF evaluations---interval containment, splines, ReLU, arithmetic shift, bit decomposition, zero test, table lookup---inherits active security at no additional online cost. We evaluate our construction using a C++ implementation that certifies keys over $\mathbb{F}_{p^2}$ ($p=2^{61}-1$) and $\mathrm{GF}(2^{128})$, realises the gate layer, and agrees bit‑for‑bit on every exported test vector. A certified DPF key at $n=16$ takes $5.7$ ms to generate and $3.3$ ms to certify. Certified DPF keys are $5.4\%$ larger than the semi-honest dealer-free baseline at $n=16$, and aggregated certification traffic converges to $1{,}282$ bytes per instance while the round count stays constant. Replaying the certified execution between two processes over TCP shows what that constancy is worth: at a $50$ ms round trip a session takes $1.15$ s, and the figure is unchanged whether one key or sixty-four are certified together, so wide-area certification of a whole preprocessing session is latency-bound by a single key. A campaign of $1{,}400$ injected generation deviations plus shape, moment and release forgeries is rejected without exception in six of seven deviation classes; the seventh is rejected in exactly the $105$ of $200$ trials in which the attacked index bit is one, which is a quantitatively exact confirmation of the single-bit selective-failure predicate that we model explicitly in the ideal functionality, matching the leakage profile of the best known actively secure distributed DPF.

In this work, we present a new framework for signature-free, post-quantum secure authenticated key exchange (AKE) that simultaneously satisfies: (1) exchanging at most two standard ciphertexts of a key encapsulation mechanism (KEM); (2) computational symmetry; (3) perfect forward secrecy (PFS); (4) strong resilience to secret-state exposure; (5) strong resistance to decryption-error attacks; (6) admitting instantiations based on the native structure of \textsf{ML-KEM} under the \textsf{MLWE} assumption; and (7) provable security in both the random oracle model (ROM) and the quantum-accessible random oracle model (QROM) under the post-id $\mathsf{eCK}\mbox{-}\mathsf{PFS}$ framework. This resolves several fundamental open questions in the literature. The core technical building block is a new cryptographic primitive, called an \emph{authenticated forward-secure} KEM (AFS-KEM), which unifies authentication and forward secrecy within a single KEM abstraction and may be of independent interest.

A blind signature scheme allows a user to interact with a signer to obtain a valid signature on a message, while ensuring that the signer cannot learn any information on the message being signed, nor link a given couple message-signature to the specific interaction that produced it (blindness). In round-optimal (i.e., two-move) blind signature schemes, a user sends a request (typically a commitment) for a message, and the signer responds with a signature. To achieve blindness, the resulting blind signature usually consists of a zero-knowledge proof of knowledge of a valid signature from the signer on a request. This reliance on zero-knowledge proofs has become the main bottleneck in reducing the blind signature size. In particular, state-of-the-art lattice-based blind signature schemes are instantiated based on the zero-knowledge proof system from [Lyubashevsky et al., EUROCRYPT, 2022], which results in blind signatures of at least 22 KB. In this work, we carefully design a blind signature protocol following the classical lattice-based Σ-protocol as in [Ducas et al., CRYPTO, 2013], so that the last component naturally forms a short preimage of the hash of the message, as a classical GPV signature. As a result, this removes the need for zero-knowledge proofs in the blind signature. Eventually, this design allows us to obtain a significantly more compact blind signature of size 4.7 KB, with concurrent security under the Module-SIS assumption. As a trade-off, our protocol may require more than one round with small probability, due to the rejection sampling in lattice-based Σ-protocols. Under our proposed parameters, however, the expected number of rounds for honest users can be as small as 1.1, which is very close to optimal. To minimize the number of rounds, we require users to prove that they failed to derive a blind signature in the previous round, before starting a new one. This technique yields a moderately looser bound on the expected number of rounds for malicious users, who will be forced to terminate in at most 2.6 rounds.

Authenticated data structures are widely used to compute compact digests of evolving collections of elements and to support efficient verification of element inclusion. However, the authenticated collection often should not grow forever: older elements may expire and no longer require verification. Many implemented append-only approaches, for example used in Certificate Transparency (CT), do not directly support this setting, since previously accumulated elements remain part of the authenticated state indefinitely. In this work, we introduce a pruning accumulator, a stateful accumulator that supports both incremental addition of new elements and pruning of an old prefix of previously accumulated elements. The resulting digest represents the unpruned sequence, while pruned elements are removed from the authenticated state. Unpruned elements continue to support proof-of-inclusion verification, proof updates, update verification, and consistency checks. This captures applications that require authenticated, incrementally maintained state over a moving window of elements. We present two constructions of Merkle-tree-based pruning accumulators, both with efficient accumulation, prefix pruning, proof generation, proof updating, and verification. The constructions preserve the standard Merkle-tree style of verification for active elements while reducing long-term storage requirements. We provide formal definitions, correctness and security analysis, an open-source implementation, and experimental evaluation demonstrating the performance benefits of pruning.

BitVM2 brought arbitrary program execution to Bitcoin, yielding the first light-client-based bridge to its second layers and reducing the trust required at setup to a single honest participant. Its successors, BitVM3 and BABE, move the disputed computation off-chain into Garbled Circuits (GCs), cutting worst-case on-chain dispute costs by roughly three orders of magnitude and so opening participation beyond well-capitalized operators; BABE in turn cuts the off-chain storage and setup costs of BitVM3's garbled circuits by a comparable factor. What still reaches the chain, however, is bulkier than it need be. BitVM2 commits its data with compact Winternitz one-time signatures (WOTS), whereas BitVM3 and BABE must reveal GC input labels on-chain and so fall back on far bulkier Lamport signatures, which play two roles at once: GC input labels and Bitcoin-verifiable commitments. WOTS cannot simply be substituted, because its hash chains are monotonic---an evaluator holding one state's preimage can hash forward and obtain several active labels on a single input wire, destroying the circuit's privacy. Recovering BitVM2's compactness therefore calls for a practical GC whose input labels are WOTS signatures---a construction that has remained out of reach. We close this gap with a non-interactive \emph{WOTS-to-Lamport translation gadget}: the garbler commits on-chain using compact WOTS chains, and the evaluator expands them off-chain into exactly the orthogonal Lamport labels the GC consumes, learning nothing about the mutually exclusive ones. A naive translation table that enumerated messages would be exponentially large. Two symmetries bring it down to quadratic: reconstruction from a Shamir sharing depends only on \emph{how many} shares are held and not on \emph{which}, which collapses the exponentially many messages onto the single checksum weight WOTS already computes; and monotonicity, the very property that made WOTS unusable, orders an evaluator's access by inclusion. We model the gadget as a garbling scheme and prove it adaptively private. Applied to BABE, it restores WOTS-scale commitments to a GC-based protocol, cutting total on-chain script size by more than $3\times$ and bringing dispute transactions within Bitcoin's standardness limit.

Secure group messaging protocols, now standardized by the IETF as Messaging Layer Security (MLS), provide end-to-end encryption for billions of users. The cryptographic core of these protocols is continuous group key agreement (CGKA), a primitive designed to maintain a shared secret among a dynamic group while providing security guarantees like forward secrecy and post-compromise security. A critical challenge for CGKA is achieving efficiency, particularly sublinear complexity (in the size of the group), for group operations. While practical tree-based protocols like TreeKEM offer logarithmic complexity in ideal (so-called "fair-weather") scenarios, their performance degrades to linear in the worst-case, and even realistic average-case, scenarios. This performance collapse raises the fundamental question of whether any CGKA protocol can achieve provably sublinear worst-case complexity. Prior work has established significant barriers to this goal, including black-box impossibility results ruling out efficient constructions from standard public-key encryption. Theoretical solutions circumvent these barriers using powerful tools like indistinguishability obfuscation ($i\mathcal{O}$), but these constructions are astronomically inefficient and often provide weaker security guarantees, such as lacking forward secrecy. This leaves a wide gap between practical protocols with poor worst-case guarantees and theoretical solutions that are entirely impractical. In this paper, we narrow this gap by presenting the first CGKA protocol that achieves provably logarithmic worst-case complexity for both computation and communication. Our first construction is based on a falsifiable and plausibly post-quantum assumption called decomposed learning with errors (decomposed LWE), and achieves basic CGKA security (only group members know the key) and post-compromise security, but not forward secrecy. We then show how to extend our scheme in the random oracle model to achieve optimal security (including forward secrecy) while retaining worst-case sublinear communication. However, the forward-secure refresh operation takes linear time in the group size, while still producing compact ciphertexts. Our work is the first to establish that worst-case efficient CGKA is theoretically possible from simple falsifiable assumptions. Moreover, it offers a plausible roadmap towards concretely efficient constructions.

Multi-party computation (MPC) enables multiple parties to jointly process sensitive data without revealing their inputs. However, existing MPC protocols remain inefficient for high-dimensional sparse data. In plaintext, sparse linear algebra algorithms address this problem using two fundamental primitives, Scatter and Gather. We propose SparseMPC, an outsourced MPC protocol that securely implements Scatter and Gather and uses them to perform sparse matrix multiplication. Our protocol supports an arbitrary number of data owners and provides a low memory footprint, constant round complexity, and low communication cost. Beyond sparse matrix multiplication, SparseMPC provides a foundation for efficiently realizing a broader class of sparse computations in outsourced MPC.

Autonomous agents are increasingly used to plan and execute paid workflows on behalf of users. Existing agentic-payment frameworks support this delegation through merchant-admission authorization credentials but require the user to specify merchants before execution. However, complex paid workflows often span multiple services and merchants, and agents may choose among them based on intermediate results. This creates two limitations: (1) requiring the user to choose each merchant in advance either limits the agent's adaptability or forces the user back into the loop; and (2) reusing a stable identifier across merchants lets observers link separate paid calls and infer the user's broader intent. To address these limitations, we introduce MinMandate, which grants adaptive merchant selection within user-approved task bounds and derives fresh per-call payment views without introducing a stable cross-merchant identifier. Extensive experiments on AgentDojo tasks demonstrate that, when 50% of merchants are unavailable, MinMandate improves task success by 32.7 percentage points on average across four tested planners compared with an AP2 baseline that preauthorizes one merchant per service class. Reintroducing a reusable public payment-layer handle in the Stable Handle ablation raises attacker task-recovery success by 27.4 percentage points on average, isolating the privacy cost of a stable join handle. The code is available at https://github.com/Zora-G/minmandate.

Anamorphic cryptography targets the scenario in which a dictator does not forbid the use of cryptography but requires all users to reveal their secret keys to them. Thus, the dictator can decrypt all honestly generated ciphertexts. The approach for bypassing this is to identify spots, such as random nonces, in existing cryptographic protocols in which secret messages can be hidden using an additional secret double key. So far, the literature mostly focused on identifying such spots in simple primitives like public-key encryption or signatures; only recently, an initial work identified limited spots in Signal's Double Ratchet Algorithm. We are the first to leverage the statefulness of cryptographic communication protocols to employ continuously updated double states and, thereby, achieve Forward Security: Even if the adversary (i) observes all traffic, (ii) knows all users' regular secret key material at any stage of the protocol execution, and (iii) at some point learns the secret double state, the entire protocol execution looks benign although covert messages were previously hidden in the traffic anamorphically. We formalize this notion and also cover robustness and authenticity, which appear to be particularly relevant in the messaging context. In this new model, we study four of the most relevant messaging protocols and identify hiding spots therein: Signal's Double Ratchet, Signal's Triple Ratchet, Apple's PQ3, and the two-party core of the Messaging Layer Security Standard. We focus on the cryptographic parts of these protocols and, despite their complexity, identify surprisingly few anamorphic hiding spots. We prove that all these protocols offer forward secure, authenticated anamorphic channels and we evaluate their bandwidths: While 16 bits can be embedded in every epoch of the Double Ratchet, Triple Ratchet and PQ3 provide 176 bits, respectively 256 bits, of bandwidth per post-quantum epoch, and MLS provides 688 bits per epoch.

A key challenge in digital credential systems is revocation, that is, the ability to revoke credentials post-issuance and verify their status upon presentation. While anonymous credentials enhance privacy over classical credentials (e.g., by providing unlinkability), they complicate revocation. Existing revocation schemes for anonymous credentials often suffer from high client or verifier computation, long delays before revocation takes effect (e.g., epoch-based settings), or require updates to all users with each revocation. We present an efficient, real-time revocation system for anonymous credentials with decentralized revocation authorities based on a novel primitive called Private Record Certification (PRC). PRC enables users to obtain a certificate for a record stored in a server-managed database without the servers learning which record was requested. This primitive is of independent interest, and we construct it by combining techniques from private information retrieval and secure multi-party computation. Our revocation scheme outsources its costs to the revocation authorities and has minimal overhead for clients and verifiers, while ensuring the communication costs are sublinear in the number of credentials for the revocation authorities. We build a prototype and demonstrate that our system achieves sub-second real-time latency at a scale of over 1 billion credentials, with an online operational cost of 2.5$ per server for processing 1 million PRC queries.

Oblivious Key-Value Stores (OKVS) (Garimella et al., CRYPTO 2021), once encoded, provide indistinguishability over keys and random values. This is an important property in many secure computation applications, such as private set intersection and multi-key searchable encryption. We introduce an Updatable Oblivious Key-Value Store with access control (UOKVS), a dynamic extension of OKVS that supports insertions over time. We provide meaningful security in the presence of updates by equipping UOKVS with fine-grained access control. As a building block in UOKVS, we provide the first analysis of oblivious insertions for Cuckoo hashing, which may be of independent interest. We show the application of UOKVS to multi-key searchable encryption where a data owner wishes to share parts of a multimap with multiple clients. We construct an oblivious multimap with insertions from UOKVS and private information retrieval (PIR). Unlike prior multi-key searchable encryption schemes, our construction supports sharing without replicating data across authorized users, substantially reducing storage costs in addition to stronger privacy guarantees. We implement our multi-key searchable encryption construction on a dataset containing up to 24 million entries using the Enron email dataset. For keywords matching 100 documents on a WAN, query processing completes in $0.6$ seconds using FrodoPIR as the underlying PIR protocol. By comparison, the scheme of Wang and Papadopoulos (Cloud Computing 2023) achieves a query time of $0.6$ seconds and also incurs data replication and leaks access patterns. Our construction reduces leakage, maintains performance, and only requires a $3.1$x storage overhead.