Oblivious Transfer (OT) is one of the fundamental building blocks in cryptography that enables various privacy-preserving applications. Constructing efficient OT schemes has been an active research area. This paper presents three efficient two-round pairing-free k-out-of-n oblivious transfer protocols with standard security. Our constructions follow the minimal communication pattern: the receiver sends k messages to the sender, who responds with n+k messages, achieving the lowest data transmission among pairing-free k-out-of-n OT schemes. Furthermore, our protocols support adaptivity and enable the sender to encrypt the n messages offline, independent of the receiver’s variables, offering significant performance advantages in one-sender-multiple-receiver scenarios. We provide security proofs under the Computational Diffie-Hellman (CDH) and RSA assumptions, without relying on the Random Oracle Model. Our protocols combine minimal communication rounds, adaptivity, offline encryption capability, and provable security, making them well-suited for privacy-preserving applications requiring efficient oblivious transfer.

We construct the first Batched Threshold Encryption scheme with a \emph{transparent} setup where public parameters are \emph{independent} of the batch size. As a result batches of arbitrary sizes can be decrypted, without imposing an a priori fixed bound. We prove security under a constant size assumption -- the decisional bilinear square Diffie--Hellman assumption. Setup is just a distributed key generation protocol to sample secret shares of a random value. Ciphertexts consist of two $\mathbb{G}_1$ elements, one $\mathbb{G}_2$ element and the encrypted message, plus a NIZK for CCA security (two $\mathbb{F}$ elements with a sigma protocol). Partial decryptions are a single $\mathbb{G}_1$ element, computed with one scalar multiplication. Decrypting a batch of $B$ ciphertexts costs $O(B)$ pairings and $O(B\log^2 B)$ group operations. In the ramp setting, with a gap between the reconstruction threshold $t$ and corruption threshold $f$ as in consensus protocols with $n\ge3f+1$, we construct a pairing-free batched threshold encryption scheme from DDH whose partial decryptions are $2B/(t-f)$ group elements, and reduce the aggregation cost of our pairing-based scheme to $O(B\log^2(B/(t-f)))$ group operations.

We consider two main classes of synchronous round-efficient Byzantine Agreement (BA) protocols: \emph{expected constant rounds} and \emph{early-stopping}. Randomized protocols can terminate in expected constant rounds, and early-stopping protocols' worst-case round complexity depends on the actual number of corrupted parties $f\le t$, with $\min(t+1, f+2)$ being optimal. In this work, we combine the benefits of both classes, proposing a protocol that has constant round-complexity in expectation and $O(f)$ in the worst case. We present our protocol in the form of a compiler that can lift a broad class of expected-constant-round BA protocols, including Feldman--Micali and Katz--Koo, to {\em also} achieve near-optimal $O(f)$ worst-case complexity. This yields the {\em first} treatment of perfectly secure BA protocols for $t<n/3$ that is both expected constant-round and near-optimal ($O(f)$) early stopping. Assuming a PKI, we show a variant of the compiler with a better round complexity, tolerating $t<n/2$ corruptions. We also extend our results to parallel broadcast, also known as interactive consistency (IC). We give a compiler that runs $N$ Byzantine agreement instances in parallel while preserving both guarantees, expected constant rounds and $O(f)$ rounds in the worst case. Parallel broadcast then follows with one extra round for $t<n/2$. To the best of our knowledge, this is the first compiler of its kind, and the first IC protocol with such expected and worse round-complexity. Finally, by combining our protocol with standard (fast) sequential composition techniques, we obtain a valid candidate to execute \emph{multi-party computation protocols} that require broadcast as their hybrid. By running existing MPC constructions using our broadcast protocol, we obtain the first MPC protocol that requires constant rounds of P2P communication in expectation and $O(f)$ rounds in the worst case.

We present DAVINCI, a decentralized end-to-end verifiable voting protocol with no trusted coordinator. The protocol is structured as a zero-knowledge (ZK) rollup: the election is a ZK-verified state machine in which every transition, from ballot submission to final tallying, is encoded as a circuit constraint, so that no actor can force the protocol into an invalid state without breaking the underlying proof system. A decentralized set of sequencers handles ballot validation and aggregation off-chain, while Ethereum serves as a public bulletin board and a data-availability layer via EIP-4844 blobs. For ballot secrecy, DAVINCI uses threshold ElGamal with distributed key generation; for receipt-freeness, sequencers re-encrypt ciphertexts before storing them, and voters may revote at any time. To make revoting effective against bribery and coercion, DAVINCI introduces silent revoting on every state update, sequencers also re-randomize a random subset of stored ballots, and we quantify how well this hides overwrites among routine refreshes. Our open-source implementation shows that DAVINCI supports large-scale elections with succinct on-chain verification and ballot proofs generated on commodity devices, under the honest-device assumption shared by several deployed verifiable-voting systems.

Lookup table polynomial interactive oracle proofs (LUT PIOPs) make SNARK arithmetizations concise, yet almost all efficient constructions assume field arithmetic. We show that directly instantiating them over a composite residue ring \(\mathbb Z_Q\) can be unsound: component-wise set checks preserve the residue multiset in each CRT component but lose the alignment across components. We formalize this obstruction, which we call the CRT alignment ambiguity. To overcome this ambiguity, we present GlueLUT, a family of efficient LUT PIOPs over residue rings. GlueLUT runs the lookup over an auxiliary field while retaining the arithmetic proof over \(\mathbb Z_Q\), and then proves consistency between the two witness representations. Our first construction, GlueLUT-4Sq, introduces a cross-modulus consistency (CMC) PIOP, which proves that witnesses over two coprime moduli encode the same integer vector. We construct the CMC PIOP via a range-check PIOP over the product ring using the Lagrange four-square decompositions, structured Johnson–Lindenstrauss projections, and a GKR-style consistency check. For a witness of size \(n\), a table of size \(m\), and security parameter \(\lambda\), GlueLUT-4Sq has \(O(n+m)\) algebraic prover work after witness generation and \(O(\operatorname{poly}(\lambda,\log n,\log m))\) verifier work and proof size. Our second construction, GlueLUT-Fold, uses random rank-one folded consistency checks to achieve better concrete prover efficiency and has \(O(n+m)\) prover work, at the cost of \(O(\sqrt n+\operatorname{poly}(\lambda,\log n,\log m))\) verifier work; its proof size is \(O(\log n+\log m)\). We implement GlueLUT-4Sq and GlueLUT-Fold as stand-alone PIOPs and report prototype results that corroborate our theoretical efficiency analysis.

We improve recent generic proof systems for isogeny knowledge by Cong, Lai, Levin based on circuit satisfiability, by using radical isogeny descriptions to prove a path in the underlying isogeny graph. We then present a new generic construction for a verifiable random function (VRF) based on a one-more type hardness assumption and zero-knowledge proofs. We argue that isogenies fit the constraints of our construction and instantiate the VRF with a CGL walk and our new proofs. As a different contribution, we also propose a new VRF in the effective group action description of isogenies. Our protocol takes a novel approach based on the polynomial-in-the-exponent technique, but without the need of a trusted setup or heavy preprocessing. We compare our protocols to the current state-of-the-art isogeny VRFs by Leroux and Lai, with a particular emphasis on computational efficiency.

Witness encryption over blockchain state aims to release a secret on a ledger condition without a key custodian. Validators with enough stake to construct a valid fork witness can obtain the secret although the condition never holds on the canonical chain. They finalize a private fork that satisfies the condition, and keeping the fork hidden withholds the conflicting votes that slashing needs. We propose slashable secrecy to address this gap with Ethereum’s native slashing rules, without an additional key-custody committee or separate collateral. In executions where the condition never holds on the finalized canonical chain through completion, an information advantage yields evidence of those votes against keys the adversary controlled, or a solution to a designated hard problem. We give a construction from a witness KEM and prove slashable secrecy conditionally on its extraction interface. We bound the implicated historical stake under changing validator weights. For an archived Ethereum mainnet state, the historical evidence-weight floor exceeds 3.5 percent of its active stake, about 1.44 million ETH, under stated budget and coverage assumptions. Experiments on a synthetic Ethereum network confirm native processing of the evidence, without WE decryption. Two limitations remain. A witness KEM satisfying the full relation and extraction interface remains uninstantiated. Enforcement requires that the evidence is available, converted to native form and included while its signers remain eligible.

Selfish mining profits in Nakamoto consensus because difficulty adjustment mechanisms (DAMs) misinterpret uncounted orphans as hash-rate contraction. Although orphan-aware DAMs record orphaned proof-of-work, strict same-epoch inclusion rules enable an orphan exclusion attack (OEA): an adversary can race private forks near epoch boundaries to permanently exclude honest tail orphans from retargeting, restoring substantial profits in short-epoch protocols. We propose the pipelined buffer difficulty adjustment mechanism (PB-DAM), which partitions each epoch into an accountable prefix and a settlement buffer of depth $d$. Pipelining estimation windows across epochs grants honest miners a grace period to report prefix uncles while advancing buffer work to subsequent retargets, closing the boundary gap without heuristic damping. Random-walk excursion bounds demonstrate that OEA success decays exponentially with $d$ for all $\alpha \le \alpha^\star < 1/2$, reducing the time-averaged profit advantage to $O(\varepsilon)$. Under stylized dynamic scheduling models, intermittent idling is analytically shown to be unable to raise the gross reward rate above $\alpha$. Simulations confirm that buffer depths $d = 16$ neutralize selfish mining even at $L = 64$ when $\alpha = 0.40$, and systems recover from a $50\%$ hash-rate crash within $2.2 \pm 0.8$ epochs, incurring under $1\%$ block capacity overhead.

Good-case latency, studied in early fast-consensus protocols (Martin and Alvisi, DSN 2005) and formalized by Abraham, Nayak, Ren, and Xiang (DISC 2020), captures a natural efficiency goal: when the sender is honest, agreement should be reached quickly for the honest parties. In the standard classical model, however, there exists a barrier for any $f\geq n/3$ corrupted parties. Specifically, synchronous broadcast requires good-case latency at least $\Delta+\delta$ for $f\geq n/3$, where $\delta$ is the actual, unknown message-delay bound and $\Delta \gg \delta$ is its known, conservative upper bound. Under partial synchrony, consistency and liveness cannot even both hold for $f \geq n/3$ (Dwork, Lynch, and Stockmeyer, JACM 1988). In this work we study the use of quantum information to get past these classical barriers, and specifically using one-shot signatures (OSS) (Amos et al., STOC 2020, Shmueli and Zhandry, CRYPTO 2025). OSS prevents even a corrupt signer from issuing signatures on different messages under the same verification key, which provides cryptographic non-equivocation without trusted hardware assumptions. Assuming OSS and a public-key infrastructure, we obtain two main results against quantum polynomial-time static corruptions. First, under synchrony, we construct a state-machine replication (SMR) protocol without clients, with optimal $\delta$ good-case latency, tolerating any $f<n$ corruptions among $n$ parties. Second, under partial synchrony, we obtain SMR with $2\cdot \delta$ good-case latency which is consistent under any number of corruptions and live assuming $2n>f$. Specifically, a corrupt majority may cause progress to stop, but cannot create conflicting histories. Such an always consistent protocol is impossible classically (without assumptions like trusted hardware) even if liveness is only required to hold against a single corrupt party. In both our SMR protocols, communication is entirely classical, with only local quantum computation.

Subversion attacks where the attacker aims to replace parts of a cryptographic system by manipulated parts in an undetectable manner have been shown to model both theoretical and practical attacks such as supply chain attacks. Originally proposed by Young and Yung (CRYPTO 1996), interest in them has increased dramatically after the revelations about the inner workings of intelligence agencies due to Snowden and the following paper by Bellare, Paterson, and Rogaway (CRYPTO 2014). One of the most promising countermeasures against such attacks are cryptographic reverse firewalls, proposed by Mironov and Stephens-Davidowitz (EUROCRYPT 2015), which are small devices used by the parties with the aim to rerandomize the protocol message to remove possible leakage. A wide range of protocols and corresponding firewalls have been developed based on this notion. The usage of such firewalls, however, also introduces another attack surface as an attacker might also corrupt these firewalls. In most works, this problem is either not addressed or treated as if in this case, the complete party using the firewall is compromised. However, as firewalls typically only perform rerandomization without knowledge of secret key material, this is a very coarse over-approximation, as an honest party Alice is now treated as maliciously corrupted. Instead, the main security problem comes from the fact that the firewall can impersonate Alice. In this paper, we introduce the notion of impersonation resilience, which allows us to develop protocols that are also secure against such a corrupted firewall and thus result in an honest complete party. We show a generic compiler that transforms subversion-resilient protocols for commitment or coin toss into protocols that are also impersonation resilient. Following a recent research line, our protocols and security analysis are built on the Universal Composability (UC) framework of Canetti. Of independent interest, we show that existing UC subversion models are either too strong and do not allow secure string commitments, or too weak and allow trivially secure protocols. We addressed this by developing a new, intermediate UC subversion model.

In this paper, we introduce a new hash algorithm in that we used the Collatz problem, focusing on its conditional branching structure, an element often overlooked despite the fame of the 3x + 1 conjecture. This hash algorithm takes an arbitrary-length input and produces a fixed length 512/384/256 bit output. The presented hash algorithm is in the category of strong one-way Hash Function (OWHF), and this hash algorithm is designed by focusing on its use in password storing and Pseudo-Random Number Generator (PRNG). Until now, quantum computers also didn’t show any speedup in the Collatz conjecture problem, so the proving and disproving of the Collatz conjecture is still a big question, so we believe that there is no structural attack on this hash algorithm.

TLA$^+$ (Temporal Logic of Actions) is a formal specification language well-suited for distributed systems. However, writing proper TLA$^+$ scripts requires high domain expertise. When it comes to modeling Byzantine behaviors for Byzantine fault-tolerant consensus protocols, the simulation of malicious behavior is a fundamental challenge: overly simplified modeling misses critical vulnerabilities, and verbose modeling leads to state-space explosion. In this paper, we present TLAssist, a large language model (LLM)-assisted tool for semi-automated TLA$^+$ generation tailored for Byzantine reliable broadcast (RBC) protocols. We provide a highly structured workflow and domain-specific data format to improve the quality of LLM prompts. Using five RBC protocols as case studies, we have some interesting findings. First, the specification generated by TLAssist outperforms many open-source TLA$^+$ scripts we are aware of, including those written by domain experts. Second, TLAssist can assist domain experts in identifying deep design flaws. Notably, our case study on the (2,3,4)-Optimistic RBC (a CCS'25 distinguished paper) captures a subtle issue that causes the violation of the totality property. Finally, TLAssist is useful for non-experts. Namely, we show that by revising the protocols slightly, the generated error traces effectively show complex corner cases that can facilitate understanding of the design.

Incrementally verifiable computation (IVC) [Valiant, TCC '08] allows one to iteratively prove that a configuration $x_0$ reaches a configuration $x_T$ via $T$ repeated applications of a (possibly non-deterministic) machine $\mathcal{M}$. An IVC scheme is fully succinct if the proof size is independent of both $T$ and the size of the intermediate configurations. In this work, we develop a new indistinguishability obfuscation ($i\mathcal{O}$)-based approach to IVC that avoids the extraction-based security analyses central to prior constructions. Assuming subexponential hardness of $i\mathcal{O}$ and one-way functions, we construct an adaptively sound fully succinct IVC scheme for deterministic computations. This yields the first IVC for deterministic computations that does not rely on algebraic assumptions. Under the same assumptions, we further obtain a fully succinct two-hop IVC scheme for $\mathsf{NP}$ with non-adaptive soundness, allowing one to prove that $x_0$ reaches $x_2$ via an intermediate configuration $x_1$. This is the first IVC scheme for $\mathsf{NP}$ achieving full succinctness. Our constructions are based on a new connection between IVC and secret sharing for $s$-$t$ connectivity in graphs.

The Internet of Things (IoT) comprises a vast array of interconnected devices that rely heavily on wireless communication to enable applications in domains such as healthcare, transportation, and smart environments. However, intrinsic vulnerabilities in wireless networks, such as susceptibility to eavesdropping, impersonation, and message tampering, require the development of robust yet lightweight authentication mechanisms. To address these concerns, we introduce AEBAP, an efficient authentication protocol based on elliptic curve cryptography (ECC), specifically designed for secure communication in resource-constrained IoT environments. AEBAP ensures mutual authentication, data integrity, and resilience against both passive and active attacks by leveraging the cryptographic strength and computational efficiency of ECC. We evaluate the protocol’s performance through experimental implementation and analyze its security using both informal reasoning and formal verification tools, including Scyther and ProVerif. The results demonstrate that AEBAP achieves strong security guarantees with minimal computational and communication overhead, making it a promising solution for securing next-generation wireless IoT systems

The FROST threshold signature scheme achieves round optimal Schnorr signing through a double-nonce construction, but requires two presignatures per signature. Since each presignature demands an expensive distributed key generation (DKG) protocol, this overhead is significant for high-throughput applications. FROST builds on a core presignature protocol (that we call FROST-core) that uses hash-based re-randomization of presignatures. We investigate whether fewer presignatures can be used to sign multiple messages, improving FROST-core's message capacity. We first show that the natural generalization of using $k$ presignatures for $k$ messages is insecure: an extended ROS attack enables forgery even for $k=2$. However, we prove that using $k+1$ presignatures for $k$ messages achieves security in the Generic Group Model combined with the Random Oracle Model. This improves message capacity from 50% (standard FROST-core) to $\frac{k}{k+1}$, approaching 100% as $k$ grows. We further extend our analysis to a modified FROST-core protocol in which a set of presignatures is generated by different parties and used for signing $k$ messages. Security holds as long as at least $k+1$ presignatures were created by honest parties.

Threshold cryptographic primitives have not been widely adopted in real-world distributed systems (i.e., beyond the closed committee model) presumably due to state-synchronization overhead and complex certification processes for the shareholders. These are both aspects of infrastructure overreliance, an assumption that is usually glossed over in their design. In this work, we propose OSST, a real-time threshold identification protocol that achieves non-interactivity and non-reliance on public shares by means of direct proof interpolation. Given a Shamir $(n, t)$-shared secret $x$, the proposed scheme allows any $t^* \ge t$ (but no less) shareholders to prove over designated communication channels that their key shares interpolate to $x$ without revealing any information beyond that. Provers do not engage in distributed computations, sending their packets to the verifier asynchronously; conversely, verifiers need only know the combined public key $y \equiv g ^ x$, without need to pre-validate and register the individual member identities. The protocol is intended for use in permissionless or unmanaged meshes that lack both overlay networks and trust infrastructure or governance, a use case space that has been tacitly neglected as ''niche'' by the current mainstream. No publicly verifiable setup is required beyond distributing $x$ according to Shamir's secret sharing (or equivalent distributed key generation scheme) and advertising its public counterpart; in particular, the protocol is intended to be secure against impersonation without relying on the auditability of any advertized public shares. We provide evidence that this has good chances to hold true by giving a security proof in the random oracle model under the one-more discrete-logarithm (OMDL) hardness assumption.

Oblivious Transfer (OT) is a fundamental building block for secure computation, in which a sender holds two messages and a receiver learns exactly one of them, without revealing which one was chosen and without learning the other. While generic constructions for Universally Composable (UC) OT exist, instantiating them from post-quantum assumptions remains challenging, particularly under adaptive corruption. In this work, we present the first adaptively UC-secure OT protocol based on Group Actions, specifically assuming weakly pseudorandom Effective Group Actions (EGA) like CSIDH. We adhere to the framework of [BC15], which derives an adaptively UC-secure OT protocol from SPHF-friendly extractable and equivocable (E²) commitment schemes. The central challenge in instantiating this construction from group actions is the lack of SPHF-friendly IND-CCA encryption. Classical CCA transformations such as Fujisaki-Okamoto destroy the algebraic structure required for building SPHFs over ciphertexts, while known group action-based schemes offer no native mechanism to prove ciphertext validity. To overcome this obstacle, we construct from group actions an IND-CCA encryption scheme with enough algebraic structure to efficiently recognize valid ciphertexts. Our contributions are threefold: (1) a verifiable chameleon hash function with perfect soundness in the standard model, (2) an SPHF-friendly, publicly verifiable IND-CCA encryption scheme in the random oracle model, and (3) we combine these to build an SPHF-friendly E² commitment scheme and derive a fully adaptively secure OT protocol in the UC framework. This is the first construction of its kind under group action assumptions, enabling post-quantum secure OT with adaptive security guarantees. These building blocks may also be of independent interest e.g., to obtain digital signatures, non-malleable commitment schemes, or verifiable encryption.

Folding schemes combine a batch of relation instances into one accumulator. For quadratic relations, applying the fold directly creates a mixed term for every pair of inputs. We present CauchyFold, a lattice protocol that folds one accumulator with \(k\) fresh quadratic instances without enumerating these pairwise terms. The companion work [WX26] uses Cauchy folding coefficients to represent the mixed contribution through a vector-valued polynomial of degree below \(k\). We give two algorithms that compute its coefficients with quasi-linear arithmetic in \(k\) for fixed relation dimensions. The protocol commits this polynomial before the folding challenge. Since the folding coefficients need not be short integers, it computes the fold over an extension field and canonically re-encodes the result as bits. This preserves the accumulator’s commitment layout and honest opening bound. For classical resettable provers, we give explicit extraction-error and expected-time bounds for a folding node with a fixed-depth reduction chain. It recovers valid source openings or a short nonzero vector in the kernel of a commitment matrix. A compiled profile at \(k=1024\) uses 162.67 KiB of no-retry interactive communication, excluding incoming commitments and the CRS.

Inner Product Arguments (IPA) [BCC+16,BBB+17] are a family of proof systems with $O(\log n)$ sized proofs, $O(n)$ time verifiers, and transparent setup. Bootle, Chiesa and Sotiraki [BCS21] observed that an IPA can be viewed as a sumcheck protocol [LFKN92] where the summed polynomial is allowed to have coefficients in a group rather than a field. We leverage this viewpoint to improve the performance of multi-linear polynomial commitments based on IPA. Specifically, - We introduce a simplified variant of Halo-style accumulation that works for multilinear evaluation claims, rather than only univariate ones as in [BGH19,BCMS20]. - We show that the size $n$ MSM the IPA verifier performs can be replaced by a ``group variant'' of $\mathsf{basefold}$[ZCF23]. This reduces the verifier complexity from $O(n)$ to $O_{\lambda}(\log^2 n)$ time at the expense of an additional $4n$ scalar multiplications for the IPA prover.

We give an elementary construction of large Reed-Solomon lists on multiplicative subgroups. For every fixed rational rate $\rho\in(0,1)$, suitable sequences of lengths give lists of size at least $2^{(2-o(1))H(\rho)/\eta}$ at agreement fraction $\rho+\eta$ as $\eta\to0$, where $H$ is binary entropy. This doubles the leading entropy exponent of the antipodal lower bound stated by Arnon, Boneh, and Fenzi, building on the construction of Krachun, Kazanin, and Haböck. If the reduced denominator of $\rho$ is a power of two, the lengths can also be chosen as powers of two. The construction lifts subsets with a prescribed product from a quotient subgroup of size $s$. This fixes a coefficient while losing at most a factor $s$ in the number of subsets. More precisely, for $n=hs$, $h\ge2$, and $1\le m\le s-2$, a code of dimension $\kappa=mh$ on a subgroup of order $n$ has a word with at least $\binom{s-1}{m+1}/s$ codewords at agreement $\kappa+2h-1$. This holds over every field containing the required roots of unity. Consequently, the exponent constant $c_2$ in the universal list-size conjecture of the S-two whitepaper must satisfy $c_2\ge2$.

The Fiat--Shamir transformation is a fundamental paradigm in cryptography for compiling interactive public-coin protocols into non-interactive arguments. While this transformation has been extensively studied for public-coin protocols, the setting of private-coin protocols, where the verifier's messages depend on secret randomness, remains largely unexplored. To date, there are no candidate transformations for private-coin protocols, neither in the standard model nor in idealized settings. In this work, we present a generic transformation that compiles any 3-message private-coin interactive proof into a non-interactive argument in the standard model, while preserving zero-knowledge. Our construction relies on sub-exponentially secure indistinguishability obfuscation, pseudorandom functions, and input-hiding obfuscation (IHO). As a corollary, this rules out the existence of 3-message weak zero-knowledge proofs with small enough soundness error. We complement this positive result by showing that the reliance on IHO is inherent: any secure Fiat--Shamir transformation for general private-coin protocols necessarily implies the existence of IHO. Finally, we rule out Fiat--Shamir transformations for multi-round private-coin protocols. Specifically, assuming the existence of collision-resistant hash functions, we prove that no such transformation exists in the multi-round setting.

One of the most important fundamental elements in guaranteeing data security is data access management. The two primary security components of data access control are typically authorisation and authentication. Data access control is the selective restriction of data access. First, we present an effective data access control mechanism for medical devices that are implanted in this study. Through a signcryption method with proxy reencryption (DAC-PRE), the protocol guarantees anonymous data access control and supports the user’s anonymity behaviour. The security is proven in oracle model. Our experimental analysis shows the proposed protocol has low computational cost.

A $(T,N)$-threshold signature scheme distributes a signing key among $N$ participants so that any $T$ participants can jointly generate a valid signature, while fewer than $T$ cannot. In this work, we first introduce a threshold one-time signature scheme with \emph{identifiable abort} based on a variant of Lamport one-time signature and Shamir secret sharing, enabling authorized participants to jointly reconstruct signatures from partial signatures. We then extend the scheme to support multiple messages using multi-layer Merkle trees. One-time signatures introduce specific coordination challenges: participants must agree on both the message and the one-time key index to avoid unsafe key reuse. We address this using a bulletin-board mechanism for consensus. Under this framework, our construction produces signatures with one message from the bulletin board to each signer and one response message from each signer, while the bulletin board may require additional communication to reach agreement. With a simple majority-vote bulletin board, the scheme signs in four rounds. Subject to this coordination constraint, the construction inherits the guarantees of the underlying threshold framework: Universal Composability (UC) unforgeability with identifiable abort, non-UC robustness, and a bulletin-board mechanism that is UC-secure with an honest super-majority and robust when the central aggregator is honest.

We present the first rigorous security analysis of the Resource Public Key Infrastructure (RPKI), an IETF standard for protecting inter-domain routing from basic yet effective attacks: prefix and subprefix hijacks. Existing evaluations of RPKI's security focus on empirical studies: adoption measurements, simulations evaluating the security provided by different adoption levels, and identification of implementation and specification flaws. In contrast, we focus on rigorous, modular security specifications and analysis of RPKI, including its interactions with the Border Gateway Protocol (BGP) and the Internet Protocol (IP). We identify sufficient conditions for RPKI to provably achieve its goals (requirements), under explicit, well-defined assumptions (models). We show that existing RPKI deployments do not always meet these conditions, e.g., because of circular dependencies, and propose standard-compliant improvements that restore them.

Post-quantum signature schemes such as ML-DSA, FN-DSA (Falcon), and SLH-DSA have significantly larger keys and signatures than their classical counterparts, making compact multiparty signing an increasingly important research problem. We survey more than 30 schemes published between 2021 and 2026, covering threshold and dis tributed signing, proof-based aggregation, and algebraic half-aggregation. Our survey shows that most existing work is designed around blockchain and validator-consensus applications, where large numbers of mostly ho mogeneous signers sign a common message and accountability is typically represented by a compact signer set. We found that a different and practically important setting has received little attention: institutional multiparty document signing, where tens to hundreds of signers may use different post-quantum schemes or parame ter sets during a gradual migration, while requiring non-interactive sign ing and exact per-signer accountability. To study this gap, we develop an eight-dimensional taxonomy based on deployment requirements and sys tematically classify existing approaches. We also formulate three testable hypotheses and propose a common benchmark methodology for evalu ating communication, computation, verification cost, scalability, signer heterogeneity, and accountability. Our analysis finds no published study that quantitatively evaluates the institutional workload across the ag gregation paradigms covered in our survey. We therefore identify the key experimental and architectural requirements for assessing whether ex isting post-quantum aggregation techniques can support heterogeneous, accountable, and non-interactive institutional signing.

There is currently a strong interest in designing standard-compatible threshold cryptographic primitives, a trend bolstered by NIST's Call for Multi-Party Threshold Schemes (NIST IR 8214C). While Multi-Party Computation (MPC) can be applied to the construction of threshold Key Encapsulation Mechanism (KEM) from NIST standard ML-KEM scheme to preserve the compatibility with ML-KEM, such a direct construction yields a high number of threshold decapsulation rounds as many as 384 for MK-KEM-512. In this paper, we optimise the round complexity of MPC-based threshold ML-KEM decapsulation. Our first construction (Scheme A) uses masked predicates, parallel coin expansion and global scheduling methods to improve the round complexity of MPC-based ML-KEM decapsulation, while maintaining ML-KEM encapsulation, public key and ciphertext formats. For ML-KEM-512, 768 and 1024, our construction improves the round complexity to 145, 218, and 290, respectively. We also introduce a variant (Scheme B) that uses an MPC-friendly variant of Kyber KEM and KangarooTwelve hash to further improve the round complexity to $35$ at the security level of ML-KEM-512, without full ML-KEM compatibility. In the semi-honest MPC model, we prove Scheme A security by exact composition with ML-KEM, and Scheme B IND-CCA security in the QROM from Module-LWE and negligible decryption failure.

The knowledge soundness of an interactive proof is often proven via various ``special soundness (SS)'' frameworks which separate knowledge extraction into: (1) extracting accepting transcripts conforming to some structure; (2) recovering a witness from structure-conforming transcripts. However, even access-structure SS [TCC'23], one of the most general, does not handle proof systems employing probabilistic tests, a protocol design technique common in more advanced and especially succinct proof systems. The reason is that its extraction strategy decides whether a challenge is ``useful'' from the challenges used in previous transcripts alone, ignoring the prover messages. While predicate SS [CRYPTO'24] captures probabilistic tests, it does not capture access structures and forgoes the combinatorial nature and simplicity of SS. We introduce adaptive special soundness (AdSS), which generally captures extraction strategies that adaptively pick challenges for the prover taking the history of entire transcripts into account. AdSS in particular captures protocols employing probabilistic tests, formally generalises access-structure SS, and provides a simpler interface than predicate SS while retaining the same expressiveness under mild conditions. We provide knowledge extractors for AdSS protocols with optimal knowledge error $\kappa$ and almost optimal tradeoffs between extraction probability and runtime. To demonstrate the utility of AdSS, we provide a new (knowledge) soundness analysis of Kilian's succinct argument, resolving an open problem in [TCC'24]. In passing, we tighten the existing soundness error bound and unify the analyses in the strict and expected polynomial time regimes. We also provide a range of other examples, from simple ones showing how AdSS captures prior notions, to a new analysis of lattice-based Bulletproofs with unstructured challenges, which improves modularity and covers certain rings beyond $\mathbb{Z}$ compared to [TCC'23].

We introduce an optimization to the Tamarin prover that reduces its search space. The optimization applies to protocol models that use equational theories with cancellative operators, for example, when modelling Diffie-Hellman groups or bilinear pairings. We prove the optimization's soundness and evaluate its performance.

The FRI protocol (ICALP '18) is one of the most influential and widely deployed building blocks at the core of modern SNARK systems. While its concrete security is well understood, existing security proofs are intricate and technically complex. In this work, we present a significantly simpler security analysis of FRI, in particular its round-by-round soundness. Our approach is more accessible to a broader audience, lowering the barrier to understanding this fundamental protocol. Furthermore, the simplicity of our analysis may pave the way for future formal verification efforts of modern SNARK constructions.

Feige, Lapidot, and Shamir [FOCS'90] presented a generic approach for building non-interactive zero-knowledge proofs via the notion of hidden-bits generators (HBGs). At a high level, an HBG allows a prover to statistically commit to a $k$-bit pseudorandom string in the CRS model with a succinct commitment. Later, the prover can open this pseudorandom string at an arbitrary subset $S \subseteq [k]$ of positions by providing a proof $\pi_S$. The hiding property requires that unopened positions remain pseudorandom. In this work, we study the efficiency of HBGs, focusing on direct constructions that make black-box use of cryptography. We obtain the following results: Succinct CRS: Assuming learning with errors (LWE), we construct an HBG with {\em succinct} CRS of size $\mathsf{poly}(\lambda,\log k)$ for generating $k$ hidden bits. This achieves an exponential improvement over a recent sequence of works by Waters [STOC'24], Branco et al.~[EUROCRYPT'25], and Waters, Wee, Wu~[EUROCRYPT'25] that required a CRS of size at least $k \cdot \mathsf{poly}(\lambda)$. Batch opening: Using pairings, we construct an HBG with batch opening, where the proof size for any subset is $ \mathsf{poly}(\lambda)$. Previously, this was only known from the Naccache-Stern public-key cryptosystem [Groth, ASIACRYPT'10]. Succinct CRS and Batch opening: Assuming the hardness of RSA, we construct an HBG where both the CRS and the opening proof for any subset are of size $ \mathsf{poly}(\lambda,\log k)$. No black-box constructions achieving this efficiency were previously known.

Oblivious Linear Evaluation (OLE) is the arithmetic analogue of the well-know oblivious transfer primitive. It allows a sender, holding an affine function $f(x)=a+bx$ over a finite field or ring, to let a receiver learn $f(w)$ for a $w$ of the receiver's choice. In terms of security, the sender remains oblivious of the receiver's input $w$, whereas the receiver learns nothing beyond $f(w)$ about $f$. In recent years, OLE has emerged as an essential building block to construct efficient, reusable and maliciously-secure two-party computation. In this work, we present efficient two-round protocols for OLE over large fields based on the Learning with Errors (LWE) assumption, providing a full arithmetic generalization of the oblivious transfer protocol of Peikert, Vaikuntanathan and Waters (CRYPTO 2008). At the technical core of our work is a novel extraction technique which allows to determine if a non-trivial multiple of some vector is close to a $q$-ary lattice.

We present $\mathsf{Accordion}$, a new proof system that works in two steps: - $\textit{Accumulate}$: The first building block is a multi-folding scheme that efficiently accumulates $k$ different instances of a degree-$d$ polynomial relation into a single accumulated instance, without using recursion. Our scheme builds on the Protostar [Bünz & Chen, ASIACRYPT '23] and Protogalaxy [Eagen & Gabizon, ePrint 2023/1106] line of work, improving further the verifier efficiency. It supports the same expressive class of relations, arbitrary-degree polynomial constraints, enabling efficient folding for CCS, Plonkish constraints, and even custom gates. - $\textit{Decide}$: The second block is a SNARK decider for the folding scheme, which efficiently proves the validity of the resulting accumulated instance using off-the-shelf optimized building blocks. We give a concrete instantiation consisting of a Plonk-based proof plus an additional KZG polynomial commitment opening. This design is especially attractive in batch-aggregation settings where a prover collects many independent witnesses, folds them into a single accumulator, and then runs one succinct decider to certify the entire batch. Our scheme avoids costly recursion overheads. We implement $\mathsf{Accordion}$ and evaluate it against a highly optimized Plonk proving pipeline ($\texttt{midnight-zk}$). For $k=64$ instances, $\mathsf{Accordion}$ is up to $2.5\times$ faster than computing $k$ Plonk proofs for SHA-256 preimages, with a $3\times$ faster verifier and $4\times$ smaller proofs. Its prover is also an order of magnitude faster than using IVC to aggregate the $k$ proofs.

Traceable secret sharing complements traditional schemes by enabling the identification of parties who sell their shares. Recently, two independent works extended traceable secret sharing to general access structures. Goyal, Jain, and Partap [EC'26] introduced a model in which a reconstruction box is augmented with a label $I \subseteq [n]$ and is only required to distinguish between two secrets when queried with the shares of parties in $I$. Based on how this label relates to the corrupted set $J$ that built the box, they defined two notions of traceability. If $I \cap J = \emptyset$, the model is called $\emptyset$-strong traceability, for which they presented a construction based on indistinguishability obfuscation (iO). Otherwise, their model is calledstrong traceability, for which they proved an impossibility result. Farràs and Guiot [EC'26] proposed a different model, which we call hiding traceability, where the reconstruction box has no label and the access structure is hidden from the parties. In this work, we improve traceable secret sharing for general access structures in three directions. First, we present a fully information-theoretic scheme for the $\emptyset$-strong traceability model, eliminating the need for strong cryptographic assumptions. This resolves an open question posed by Goyal, Jain, and Partap, who asked what are the minimal assumptions needed in the $\emptyset$-strong traceability model. Second, motivated by the impossibility of strong traceability, we introduce a relaxed notion calledhidden mildly strong traceability. This model is relevant in practice and bridges the strong and hidden models. For this setting, we present an information-theoretic scheme for general access structures. Finally, we consider the more general model of stateful traceability, where reconstruction boxes may keep state across queries, and we prove an impossibility result for this setting.

Blind signatures are a central primitive for privacy-preserving applications such as e-cash, anonymous credentials, and e-voting. Classical constructions such as blind Schnorr adapt an ordinary signature scheme while producing signatures that follow the same format and distribution as those generated by the ordinary signing algorithm. This property is particularly relevant in settings where blind and non-blind signatures coexist within the same infrastructure. Achieving an analogous result for lattice-based Fiat--Shamir signatures, with security based on the underlying ordinary signature scheme, has remained open. We present $\mathsf{BRaccoon}$, the first concurrently secure lattice-based realization of the ``blind signatures from a signature assumption'' paradigm of Fuchsbauer and Wolf (EUROCRYPT~2024). Our construction builds on the rejection-free lattice signature scheme $\mathsf{Raccoon}$, yielding signatures that retain the algebraic format and verification relation of $\mathsf{Raccoon}$. At a high level, we introduce blinding at the commitment stage and enforce correct challenge and response generation via linearly homomorphic encryption combined with $\mathsf{NIZK}$ proofs. Since these proofs already bind the hidden message to the resulting signature, their relation can naturally incorporate predicates on that message, providing a direct route toward predicate blind signatures. A central technical challenge stems from discrete Gaussian sampling, where blinding induces a non-trivial distributional shift that precludes direct security reductions. To overcome this, we introduce a modified scheme $\mathsf{Raccoon}^\star$ that explicitly captures this shift. We analyze one-more unforgeability through non-rounded versions of $\mathsf{Raccoon}^\star$ and $\mathsf{Raccoon}$. The deployed blind-signing protocol retains rounding. For a concrete instantiation, we encode the lattice relations and the non-linear challenge computation in a common mixed Boolean and arithmetic relation. Our instantiation retains SHA3-256 and SHAKE256 and proves both protocol statements using the ZK-LaBRADOR toolkit. For up to $2^{32}$ signing queries, its total communication is estimated at approximately $862$ KB.

Mobile access within public finance and enterprise environments often requires lightweight anonymous authentication, allowing users to prove authorization without disclosing their identities. Group Time-based One-Time Passwords (GTOTP) has recently been proposed as a lightweight primitive meeting this need with post-quantum security. To address dynamic group membership, Cao et al. introduced DGTOne, the first dynamic GTOTP construction. It employs chameleon hashes to precompute a fixed set of Merkle-tree leaves (mount points), into which conventional TOTP verification points (VPs) contributed by group members are adaptively inserted. However, DGTOne partitions mount points by time epochs, so they can expire and become unusable, causing capacity waste due to unpredictable join times. Moreover, its outsourced proof generation requires verifiers to be online each epoch to fetch refreshed credentials from Registration Authority (RA), defeating offline verification needed in mobile access. We address these limitations with two new schemes. First, we propose NWDGT, a no-wastage DGTOTP design that constructs Merkle trees of members' verification points (VP-trees) on demand, eliminating expired mount points at the cost of added handling latency. To mitigate this latency, we introduce LWDGT, which instantiates multiple small one-time signature (OTS) trees whose leaves (OTS public keys) serve as mount points. New members' VPs are signed immediately using unused leaves, achieving low wastage. We formally prove that the wastage rate of LWDGT is, with overwhelming probability, lower than that of DGTOne. By modeling the registration process and optimizing OTS-tree size, for deployments with up to 500 members (209 initially, 20 added monthly), LWDGT reduces mount point wastage rate by 10.2% over one year compared to DGTOne.

Keyword Private Information Retrieval (KPIR) enables clients to retrieve database entries by keyword without revealing their query, with many efficient schemes relying on Fully Homomorphic Encryption (FHE). However, existing FHE-based KPIR schemes fix parameters to a bounded computation depth, which becomes a bottleneck in privacy-sensitive settings such as distributed ledger systems and private web search, where databases grow dynamically and clients are lightweight: exceeding this bound incurs significant overhead, forces larger parameters, and leaves any post-retrieval computation to the client or to communication-heavy interactive protocols. We introduce Keyword PIR with Computation (KPIR-C), a new paradigm that enables arbitrary, non-interactive server-side computation on query responses while preserving query privacy. Unlike prior designs, KPIR-C fixes parameters independently of database size or computation depth by leveraging bootstrapping via a co-design of Torus Fully Homomorphic Encryption (TFHE) and KPIR that keeps bootstrapping overhead practical. We further introduce Keyword PIR with Default (KPIR-D) to handle mismatched queries non-interactively. We instantiate KPIR-C with two constructions: one based on equality circuits and constant-weight codes, and one based on Learning With Errors (LWE)-based KPIR, offering complementary communication-runtime trade-offs. We demonstrate experimentally that both achieve competitive performance compared to state-of-the-art KPIR schemes that do not support arbitrary computation.

The Signal Protocol is a two-party secure messaging protocol used in applications such as Signal, WhatsApp, Google Messages and Facebook Messenger and is used by billions daily. It consists of two core components, one of which is the Double Ratchet protocol that has been the subject of a line of work that aims to understand and formalise exactly what security it provides. Existing models capture strong guarantees including resilience to state exposure in both forward security (protecting past secrets) and post-compromise security (restoring security), adaptive state corruptions, message injections and out-of-order message delivery. Due to this complexity, prior work has failed to provide security guarantees that do not degrade in the number of interactions, even in the single-session setting. Given the ubiquity of the Double Ratchet in practice, we explore tight security bounds for the Double Ratchet in the multi-session setting. To this end, we revisit the modelling of Alwen, Coretti and Dodis (EUROCRYPT 2019) who decompose the protocol into modular, abstract components, notably continuous key agreement (CKA) and forward-secure AEAD (FS-AEAD). To enable a tight security proof, we propose a CKA security model that provides one-way security under key checking attacks. We show that multi-session security of the Double Ratchet can be tightly reduced to the multi-session security of CKA and FS-AEAD, capturing the same strong security guarantees as Alwen et al. Our result improves upon the bounds of Alwen et al. in the random oracle model. Even so, we are unable to provide a completely tight proof for the Double Ratchet based on standard Diffie-Hellman assumptions, and we conjecture it is not possible. We thus go a step further and analyse CKA based on key encapsulation mechanisms (KEMs). In contrast to previous works, our new analysis allows for tight constructions based on the DDH and post-quantum assumptions.

Fully anonymous perfect threshold secret sharing combines exactly uniform unauthorized shares with reconstruction from unlabeled share values. Con, Li, and Mazor proved that short-share schemes exist for every threshold, leaving efficient general constructions and constant rate open. We address both questions. First, we give an explicit one-bit scheme with $(2t-3)\lceil\log_2n\rceil$-bit shares, expected-polynomial-time sharing, and deterministic polynomial-time reconstruction. The key is an exact sampler for localized affine relations, including collision patterns. Second, an affine-hull compiler turns any one-bit primitive with alphabet $\{0,1\}^b$ into a long-secret scheme with additive share overhead $b(t-1)\lceil\log_2(n+1)\rceil$, up to field-alignment padding. Authorized payloads determine an affine space; a short anonymously shared certificate identifies the secret within it. Instantiation gives $L+O(t^2\log^2n)$-bit shares and rate $1/2$ at $L=\Theta(t^2\log^2n)$. For fixed $2\le t<n$, the rate approaches one, which the classical bound of Kishimoto et al. shows is unattainable at any finite nontrivial secret alphabet. Finally, we prove the universal bound $|\Omega|\ge(n-t+1)(n-t+2)$ for $3\le t\le n-2$. Together with Con--Li--Mazor's specialized threshold-three construction, this establishes the exact fixed-length optimum of $2m$ share bits for $(t,n)=(3,2^m)$, $m\ge3$. All guarantees are information-theoretic and exact. The technical work is done by GPT 6 Astra.

Symbolic protocol verifiers must make a difficult tradeoff: their models and counterexamples should be accessible to protocol designers, but their results must still have a precise meaning. Verifpal addresses the first goal with a compact modeling language and source-level attack explanations. Its original analysis engine, introduced in 2019, had only a preliminary account of its guarantees. This paper presents and evaluates the replacement engine. The engine searches backward from a violated security query to candidate attacker actions. It then runs every session and peer configuration of the protocol together as one execution under those actions, in which each injected value must be derivable from what that same execution has already disclosed, and evaluates the query on that execution. We specify this process from the term algebra and primitive registry through knowledge deduction, bounded sessions, peer configurations, execution, and counterexample presentation. We also give a single-history reference semantics, prove that every execution the engine judges is a history of that semantics, prove termination under the engine's search bounds, and state exactly what each result category establishes. Our evaluation combines targeted regression models, mutation analysis, corpus measurements, and comparisons with ProVerif, Tamarin, and Scyther. It shows that the engine can express and find attacks that require several sessions, different peer assignments, or staged compromise, while exposing the implementation choices that limit its search. The result is an auditable account of Verifpal as a bounded counterexample finder: every reported attack is an explicit protocol execution, but a passing query is not an unbounded proof, and no report is a machine-checked certificate.

The standardization of post-quantum cryptography, notably ML-KEM, introduces a severe network bottleneck: large public keys and ciphertexts often exceed the Maximum Transmission Unit (MTU) limits of UDP-based protocols. This size explosion inevitably leads to unreliable IP-layer fragmentation or forces complex protocol workarounds. To overcome this, we propose a novel design philosophy for post-quantum Authenticated Key Exchange (AKE). We challenge the rigid cryptographic paradigm that mandates negligible decryption failure rates (DFR). By safely trading minor, manageable decryption failures for aggressive size compression, we drastically reduce the bandwidth footprint of lattice KEMs in ephemeral exchanges. We demonstrate this approach via a compact AKE for the Internet Key Exchange protocol (IKEv2). Integrating standard ML-KEM into IKEv2 currently necessitates the high-latency IKE_INTERMEDIATE exchange (RFC 9242) to distribute large payloads. By employing our compressed KEM design (800-byte public key, 928-byte ciphertext), the entire key exchange fits within the initial IKE_SA_INIT packet, completely eliminating the need for RFC 9242. To ensure that protocol aborts caused by decryption failures do not introduce security vulnerabilities, we formalize IND-CPAF (Indistinguishability under Chosen Plaintext Attack with Failures) to rigorously bound failure-dependent leakage. More importantly, we prove our IKEv2 instantiation still secure in the classical Canetti-Krawczyk model. Finally, our implementation in the strongSwan IPsec library confirms a fragmentation-free handshake: over 10,000 real-world connections, it achieves a 48.8 ms average setup time---matching classical ECDH---and keeps initial packets strictly under the 1280-byte IPv6 MTU, with merely a 0.002% retry rate.

Communication is a central efficiency bottleneck in garbled circuits. Rosulek and Roy (CRYPTO 2021) introduced \emph{slicing} and \emph{dicing}, obtaining a garbling scheme in which XOR gates require no communication and each two-input AND gate costs \(1.5\lambda + 5\) bits, where \(\lambda\) is the security parameter. In this work, we investigate the power of these techniques for garbling gates of larger fan-in. We develop a linear-algebraic framework that yields concrete constructions and asymptotic bounds. For three- and four-input gates, we obtain constructions with communication costs $7\lambda/3 + 35$ and $15\lambda/4 + O(1)$ bits, respectively. For arbitrary fan-in \(n\), we give a construction for any single-output gate with communication cost bounded by \(22 \cdot 2^n\lambda/n + 2^n\) bits. Our constructions are compatible with free-XOR, and all hash queries within each gate are nonadaptive. We prove security of the framework in the random-oracle model and under a circular correlation robustness (CCR) condition for any number of slices. We also evaluate simple uses of the three-input construction against the best two-input circuits collected in our experiments, finding evidence of communication savings on control circuits.

Polynomial commitment schemes (PCSs) allow a prover to commit to a polynomial and later prove its evaluations succinctly. Among hash-based constructions, FRI (Ben-Sasson et al., ICALP 2018) and its follow-up works achieve polylogarithmic proofs by recursively ``folding'' Reed-Solomon (RS) codes. However, their concrete evaluation costs remain relatively high, as the first few folding rounds operate on the largest codewords and dominate the prover work. We present \emph{ReedWeave}, a Reed-Solomon PCS that successfully incorporates interleaving with folding, achieving the best of the two worlds. ReedWeave decomposes a degree-$d$ polynomial into $m$ smaller components and commits to their RS encodings over a common domain. Under our novel decomposition, a random linear combination of these codewords is exactly an $m$-ary folding. At a high level, ReedWeave starts with an $m$-ary folding, followed by standard binary folding as in FRI. The prover costs are substantially reduced in the sense that at the very beginning it suffices to do interleaved-RS encoding rather than standard RS encoding. That is, we reduce prover costs from $\mathcal{O}(d \log d)$ to $\mathcal{O}(d\log(d/m))$ for constant code rate while maintaining efficient polylogarithmic verification. Moreover, our approach essentially works for arbitrary $m$, relaxing the smoothness requirements of the underlying fields by a multiplicative factor of $m$. We benchmark our Rust implementation over Goldilocks using 32 threads and targeting 100-bit security. At $d=2^{24}$, $\rho=1/4$, and $m=64$, the DEEP variant commits in $475.0$ ms, opens in $111.6$ ms, verifies in $2.07$ ms, and produces a $594.7$ KiB proof. Compared with FRI (ICALP 2018), commitment, opening, and verification are $6.9\times$, $51.5\times$, and $4.2\times$ faster, respectively. Against STIR (CRYPTO 2024), the corresponding speedups are $2.9\times$, $68.5\times$, and $2.1\times$. Its proof is only $0.69\times$ the size of FRI's and $2.31\times$ that of STIR's.

Fair data exchange (FDE) ties payment to recovery of data matching an agreed commitment. Code-based FDE offers near-plaintext communication, but the sampled-ElGamal baseline incurs costly in-circuit checks when low redundancy requires many samples. We replace auxiliary ElGamal ciphertexts with direct KZG authentication and external witness linking. This leaves only field arithmetic in the consistency circuit and permits a BLS12-381 instantiation with EVM precompile support for settlement-key verification. We prove correctness, soundness, and zero knowledge under an external KZG setup in the algebraic group and random oracle models. Our implementation reduces aggregate sender computation from \(179.6\) to \(2.75\) seconds (\(65.3\times\)) for a \(2\,\)MiB file at redundancy \(\beta\approx1.1\), relative to the sampled-ElGamal baseline. Bulk ciphertext remains about \(1.1\times\) the plaintext size. The corresponding EVM implementation reduces gas for successful seller settlement by a factor of \(31.3\).

Central Bank Digital Currencies (CBDCs) aim to replicate the utility of physical cash in the digital era by balancing privacy with regulatory auditability. Despite recent advancements, existing CBDC schemes suffer from limited concurrency and the lack of offline payment confirmation, forcing users to process concurrent payments one by one and requiring counterparts to remain online. These constraints severely limit CBDC's applicability in high-frequency, real-world payment scenarios. This paper proposes PulpoPay, the first CBDC scheme to provide high concurrency and offline confirmation, while maintaining auditable privacy. To achieve high concurrency and offline confirmation, PulpoPay, at its core, introduces a coin-based payment protocol that facilitates users to concurrently withdraw, transfer, and deposit coins without synchronization or online requirements for counterparts. For auditable privacy, we leverage signatures on randomizable ciphertexts to enable fine-grained auditing without compromising privacy. Furthermore, we design a coin identifier with offline-checkable uniqueness to resist double-spending attacks even in disconnected (offline) environments. We formally prove PulpoPay's security within the Universal Composability (UC) framework. We implement a prototype of PulpoPay. Experimental results demonstrate that (1) a payment with an offline receiver can be finished within 0.3~s using a mobile phone; (2) PulpoPay outperforms the state-of-the-art PEReDi [CCS'22] in the scenarios of concurrent payments. For a typical setting of 200 concurrent payments, PulpoPay reduces processing time by at least 66.89% and communication overhead by at least 76.45%. This advantage becomes even more significant as the number of concurrent payments grows.

Fuzzy Password-Authenticated Key Exchange (fuzzy PAKE) was introduced at Eurocrypt'18, enabling two parties to securely establish a shared cryptographic key using passwords that are close and potentially low-entropy. This is a generalization of standard PAKE and is particularly useful for handling mistyped passwords or inherently “noisy” samples such as biometrics. While this primitive sounds promising, existing definitions and protocols face several challenges: they may suffer from gapped leakage (namely, leakage of a small amount of information from failed authentications), or they may be restricted to Hamming distance. We review the functionality and describe our contributions below: 1. Leakage under Reuse. We show that, when a password may be reused across multiple sessions, any leakage from the functionality has the same eventual compromise consequence under repeated use. Concretely, we construct an efficient ideal-world adversary that recovers an n-character password within O(n) active sessions, assuming it starts from a password not too far from the target. Our attack applies to both Hamming distance and Minkowski (L_p) distance under reasonable parameter choices. This implies that, for common distance metrics in practical settings, several notions of leakage are effectively unified when passwords are reused, thereby resolving an open question from Eurocrypt'18. 2. Supporting L_p Distances. We propose substantially more efficient protocols for generalized Minkowski (L_p) and Hamming distances in the random oracle model. As a key technical step, we show how to achieve malicious security using only a semi-honestly secure oblivious key-value store, while addressing several subtleties in the proof. Concretely, compared with existing approaches for L_2 distance, our protocol reduces runtime by about 86% and bandwidth by about 99%.

Multiparty private set union (MPSU) enables a group of mutually distrusting parties, each holding a private set, to learn the union of their sets without revealing additional information. MPSU is a fundamental primitive with applications to privacy-preserving tasks such as cyber-risk assessment and private record matching. State-of-the-art MPSU protocols require parties to sequentially shuffle encrypted values in order to hide which party contributed which inputs to the final result. We introduce a new paradigm for semi-honest MPSU that eliminates the need for such shuffling. This allows the protocol to run in constant rounds regardless of how many parties are involved. The resulting protocol also benefits from improved parallelism, an information-theoretic online phase, and native support for unbalanced input sizes, a situation most prior works must handle by padding inputs to hide individual input sizes. We implement and evaluate our protocol across a range of party counts, input sizes, and network conditions. In the unbalanced setting, where parties hold unequal-sized inputs, our protocol significantly outperforms the state-of-the-art schemes PULSE (CCS ’25) and DZBC25 (USENIX Security ’25). In the balanced setting, it achieves an order-of-magnitude improvement over PULSE in most settings and outperforms DZBC25 in WAN deployments with 100ms latency.

In a zkTLS protocol, a user proves to a third party a property of data obtained from an online service over TLS, revealing nothing beyond the statement proven. Each existing scheme, however, comes with its own security model, written for that scheme alone, so the schemes are not proven secure against a common definition. The root cause is a mismatch of levels: existing models are stated at the level of TLS and therefore reflect how each construction handles it. Yet TLS is only the transport, and a zkTLS proof is about the application-layer protocol executed over it. We therefore introduce the first transport-agnostic security model for zkTLS, stated at the application layer and mentioning neither TLS nor any particular construction. The resulting notion, Zero-Knowledge Proof of Protocol Execution (zkPoPE), defines what it means for a party that has executed an arbitrary two-party protocol with a counterparty to prove, in zero knowledge, that its private input and the reply it received satisfy a chosen property, and, crucially, that the reply comes from a real execution with that counterparty rather than being fabricated. This proof-of-execution requirement separates zkPoPE from a NIZK over the input--reply pair: knowing a satisfying pair does not by itself show that an execution occurred. We formalize zkPoPE as a UC ideal functionality F_{zkpope}. We then introduce the Reclaim Protocol, a zkTLS scheme that UC-realizes F_{zkpope} under a deployment-aligned trust model and underlies a production system. Reclaim builds on Distributed-AEAD, a new three-party authenticated-encryption primitive of independent interest. On a lower-mid-range phone, Reclaim attests to a 1200kB response in 7.28s, two orders of magnitude beyond any size previously benchmarked for zkTLS.

Secure aggregation with input validation enables a server to securely compute the summation of private data from multiple clients while verifying that the inputs satisfy specific constraints. However, the practical deployment of this paradigm at scale is hindered by two primary limitations. First, existing schemes suffer from severe efficiency bottlenecks due to their reliance on generic, computationally expensive zero-knowledge proofs (ZKPs). Second, the scope of input validation is currently restricted to norm checks (e.g., $L_2$ and $L_\infty$) against public bounds. This paper presents \textsf{Vespa}, a single-server secure aggregation scheme that simultaneously achieves practical efficiency and expands validation capabilities to support both \textit{norm checks against public bounds} and \textit{similarity checks against private server inputs}. Specifically, we design a novel validity-weighted secure aggregation protocol over committed inputs, built upon highly efficient vector oblivious linear evaluation (VOLE). To efficiently realize input validation, we introduce customized $L_2$ and $L_\infty$ norm checks based on VOLE-based ZKPs, centered around optimized range proofs with reduced range sizes. Furthermore, we extend our framework to support advanced similarity-based checks against private server inputs, instantiated with widely used Euclidean and cosine similarities. This allows \textsf{Vespa} to first filter out invalid inputs using norm checks, followed by performing fine-grained validation via similarity metrics. We compare our scheme with the state-of-the-art secure aggregation works, including RoFL (S\&P 2023), ACORN (USENIX Security 2023), and Armadillo (CCS 2025), and extensive evaluation shows that our $L_2$ and $L_\infty$ norm checks achieve runtime improvements of up to $2\sim 3$ and $1\sim 3$ orders of magnitude, respectively. Our similarity checks also achieve practical performance, consuming only around $94$ seconds for an $818$k-entry vector.

Accommodating cryptographic authenticity with strong user privacy assurances has been the primary motivation for anonymous credentials systems. Their features have recently come into the spotlight with the European Digital Identity (EUDI) wallet initiative, insisting on the need for efficient and private solutions based on well-understood security foundations for high assurances. This coincides with the post-quantum transition, but current quantum-safe solutions based on standard assumptions are still lagging behind the ones on ad-hoc interactive assumptions performance-wise. In this paper, we present several techniques to improve the efficiency of anonymous credentials from standard lattice assumptions, narrowing the gap with more efficient but also more exotic ones. Alongside other optimizations, our main contributions focus on the zero-knowledge protocol of Lyubashevsky, Nguyen, Plançon (Crypto'22), currently the efficiency bottleneck of lattice privacy-oriented constructions, for which we identify several sources of improvements that may be on independent interest.

Spending limits are the workhorse of custody policy, yet in every deployed threshold-signing stack they live outside the signing protocol—in centralized policy engines, on-chain covenants, or hardware co-signers—where they leak budget state, bind to a single chain, or add a trusted bypass surface. The workload is compounding: agent payments passed one hundred million transfers on a single chain in under a year. We initiate the study of protocol-native spending limits: per-epoch budgets secret-shared among the signers and enforced inside the signing session, with unchanged on-chain verification. We first show that the natural approach fails: gating a threshold signature with a passively secure MPC comparison admits a deterministic bypass. For the class of linear gatein-combination protocols we prove that every member signs over-budget transactions with probability one, disguised against any transcript auditor up to the statistical masking bound. We then construct BTS, a budgeted threshold Schnorr scheme with a formal budget-soundness definition for honest-majority configurations. The gap is closed with an authenticated gate: in implementation, every attack attempt is caught before a signature is produced, at a measured cost of 3.4–3.7× multiplications and five extra rounds. Batched over k=20 payments, enforcement amortizes to about one network round trip per payment in our WANmodeled prototype.

Cashu, the dominant deployed Chaumian ecash system, has grown to 31 specification documents, 58 indexed mints, and seven interoperable wallets, while the cryptographic literature has studied only its blind-signature core. Every incident in the system’s short audited history, including a cross-mint theft disclosed in early 2026, is compositional: it emerges from keyset rotation, wallet recovery, and multi-mint identity. We give the first system-level security analysis of a deployed ecash system, built on a five-layer model, a nine-property family (three properties new), and a stateful one-more-unforgeability theorem whose proof separates forgery from theft; the deployed attacks commit theft without forging anything. We reproduce the disclosed theft end-to-end, exhibit a strictly stronger public-key-claim variant, and measure all 58 indexed mints: every reachable mint declares support for DLEQ proofs, the sole remaining defense, yet declarations are unauthenticated the guardrail sits with the issuer, not the wallet. A theft theorem gives necessary and sufficient conditions for prevention, and replaying three fixes shows the cheapest one costs honest issuers nothing. A defect taxonomy and a three-system comparison suggest a broader lesson: recoverability is not free. All artifacts are pure standard-library Python and pass the 49 o cial test vectors.

Token-weighted governance can fingerprint individual voters: when weights are unequal and externally known, the exact weighted tally may reveal who voted which way. Publishing only the winning outcome hides the tally from the public, but a system that reconstructs the tally in order to decide still hands it to whoever runs the computation. Publishing only the winner is not the same as computing only the winner. We present a verifiable protocol for weighted DAO votes in which no protocol role ever receives the weighted tally in plaintext. Each ballot proves in zero knowledge that its encrypted contribution is exactly zero or the voter’s registered weight. Trustees add accepted contributions and compare the sum with a threshold entirely under encryption using the Cortier–Gaudry–Yang (CGY) conditional-gate toolbox, and decrypt only the final decision. A public verifier checks that the computation consumed exactly the ciphertexts accepted by the governance contract. We prove accepted-result correctness even when all trustees are malicious; restricted-I/O SUC security of the tally against static active corruption of any sub-threshold trustee coalition, which is any four of five in our reference instance; and winner-only disclosure relative to the real sealed board. With 1,024 voters, the encrypted tally takes 157 s and independent replay 115 s, while ballot proving dominates the 28.5-minute end-to-end pipeline. A fresh Arbitrum Sepolia execution exercises the complete public-chain path

SNARKs based on error-correcting codes require codes that simultaneously support fast encoding and large relative distance. Reed--Solomon codes achieve the optimal rate--distance tradeoff given by the Singleton bound, but their fast encoding relies on FFT-friendly fields, limiting their applicability to field-agnostic constructions. In this work, we revisit expand--accumulate (EA) codes, a simple family of linear codes with efficient encoding over arbitrary fields. Although extensively studied in prior work, existing distance guarantees are weak, and practical instantiations have relied on conjectured results. We prove that EA codes with exact-weight expansion matrices, over sufficiently large fields, achieve a rate--distance tradeoff that approaches the Singleton bound with high probability, resolving these conjectures. Building on this result, we construct \textsf{Flare}, a field-agnostic polynomial commitment scheme based on EA codes. At its core is an efficient IOPP for EA codes that leverages code switching. For statements of size $M$, \textsf{Flare} achieves $O(M\log M)$ prover time and $O(\lambda\log^2 M)$ proof size, improving upon the $O(\sqrt{\lambda M})$ proof size of prior constructions based on EA codes (Block et al., CRYPTO 2024). Comprehensive evaluations show that \textsf{Flare} achieves compact proofs while maintaining competitive prover efficiency. For proving circuits of size $2^{22}$, \textsf{Flare} produces the smallest proofs of approximately $16$~MiB. Compared with BaseFold (Zeilberger et al., CRYPTO 2024) and ERA (Baweja et al., ASIACRYPT 2026), it reduces proof size by $1.66\times$ and $1.47\times$, respectively, while maintaining comparable prover efficiency. Compared with Brakedown (Golovnev et al., CRYPTO 2023), \textsf{Flare} produces $4.85\times$ smaller proofs at the cost of only a $1.50\times$ slower prover.

Oblivious RAM (ORAM) protocols enable a resource-constrained client to outsource data to an untrusted server, and access this data without revealing what is being accessed. While ORAM protocols are almost optimal, concretely efficient ORAM protocols incur sub-optimal bandwidth overhead and require multiple roundtrips of communication between the client and the server. In this work, we introduce write-public ORAM: a relaxed variant of ORAM that hides what data is being read, but not what data is being updated on the server. We present wpORAM, a write-public ORAM that modifies Path ORAM to achieve a log N-factor improvement in bandwidth and roundtrips over Path ORAM during writes. The asymptotic cost of reads in wpORAM remains the same as Path ORAM, with a slight slowdown in practice. wpORAM, when used with a Trusted Execution Environment (TEE), can implement a dynamic Private Information Retrieval scheme that efficiently updates data stored in a public database. We use wpORAM to implement a private blockchain RPC server that enables blockchain clients to query RPC nodes without revealing their queries to the server operator. Our evaluation shows that, while syncing with the latest blockchain state, our RPC node achieves a 3-4x speedup over Path ORAM. Our RPC node can serve reads with a slowdown of approximately 23% compared to Path ORAM.

Many cryptographic protocols rely on affine message authentication tags of the form \({\boldsymbol\sigma}=\Delta{\boldsymbol x}+{\boldsymbol k}\), the batch version of information-theoretic MAC. Generating the tags for a long message vector typically requires communication linear in its length. Recent chosen-input VOLE protocols achieve succinct communication, but do not allow the authenticator’s key $k$ to be fixed in advance. We introduce $\mathit{batch\text{-}MAC}$, a primitive that authenticates a chosen message vector in two messages while allowing the authenticator’s key vector to be generated beforehand from a short seed. For a vector of length \(m\), we construct batch-MACs with \(O(m^{2/3}\lambda)\) communication under the decisional composite residuosity (DCR) assumption and \(\operatorname{poly}(\log m,\lambda)\) communication under the learning with errors assumption. Both constructions require a common reference string (CRS). We find applications in constrained pseudorandom functions, 2-message 2PC, and succinct zero-knowledge arguments.

Adaptor signatures enable conditional payments on blockchain networks: a pre-signature is bound to a public instance $Y$ and can be completed into a valid signature by any party knowing a witness $y$ with $\mathcal{R}(Y,y)=1$, while the pre-signature and full signature together allow the signer to extract $y$. Existing constructions only support specific algebraically-structured relations, lose witness privacy, or have significant overhead both in signature size and computation. We present a practical adaptor signature framework for arbitrary NP relations, built from a new primitive we call Online/Offline NIZK whose proof is separated into online and offline parts. The key property is that the witness can be extracted from the online part knowing the randomness used in the offline part. We give two generic constructions: a basic scheme achieving witness hiding, and an instance-hiding scheme achieving a new, stronger forward-secure privacy notion we introduce. We instantiate our framework for the AES-128 relation using the VOLE-in-the-Head paradigm and the FAEST post-quantum signature scheme. The resulting complete signature is $11.6$ kB, roughly $60\%$ smaller than the state-of-the-art adaptor signature for NP (Ciampi et al., CT-RSA '25), and our implementation is an order of magnitude faster in overall signature generation, verification, and extraction.

Recent works have studied Byzantine agreement (BA) in the mixed-fault model with resilience threshold $n>2t+r+s$, where $n$ is the number of parties, $t$ is the number of Byzantine parties, $r$ is the number of receive-faulty parties, and $s$ is the number of send-faulty parties. In particular, Feng et al.~(ASIACRYPT~2025) proposed a BA protocol with optimal resilience, expected asymptotically quadratic communication complexity, and expected constant round complexity. However, existing BA protocols guarantee a meaningful output $v$ only when all parties hold the same input $v$. Such a guarantee is insufficient for efficient construction of atomic broadcast protocols, leaving efficient atomic broadcast in the mixed-fault setting as an open problem. In this paper, we present the first atomic broadcast protocol (UABC) with optimal resilience in the mixed-fault model. In addition, our protocol achieves communication complexity $\mathcal{O}(n\ell+n^2\lambda^2)$ when $t=\Theta(n)$, where $\ell$ is the input size and $\lambda$ is the security parameter. This complexity is asymptotically optimal for moderately large $\ell$, namely when $\ell\ge n\lambda^2$. At the core of our design is an undead verifiable information dispersal (UVID) protocol, which allows an input to be efficiently dispersed and later reconstructed in the mixed-fault setting. Leveraging UVID together with the undead multi-valued consensus (ASIACRYPT~2025), we further construct a new primitive called weak undead multi-valued validated Byzantine agreement (wUMVBA) and its optimized variant (Opt-wUMVBA). Unlike standard multi-valued validated Byzantine agreement, wUMVBA and Opt-wUMVBA guarantee that the output is either a meaningful value satisfying the validity predicate or $\bot$. Moreover, the probability of outputting $\bot$ is at most $(t+s)/n$. Finally, by leveraging Opt-wUMVBA, we obtain our optimal atomic broadcast protocol for the mixed-fault setting.

The rapid expansion of quantum computing threatens the security foundations of classical public-key cryptography, including RSA and ECC, both vulnerable to Shor's algorithm. For the automotive industry, where secure communication underpins critical functions such as over-the-air (OTA) updates, secure boot, firmware signing, PKI validation, and vehicle-to-everything (V2X) connectivity, this threat demands early and informed migration planning. This paper presents a cross-platform performance evaluation of NIST-selected and candidate Post-Quantum Cryptography (PQC) algorithms integrated into the Transport Layer Security (TLS) protocol, in both standalone and hybrid (classical + PQC) configurations. Signature schemes CROSS, MAYO, SPHINCS+ (SHA and SHAKE variants), ML-DSA, and FALCON are evaluated alongside key encapsulation mechanisms including FrodoKEM, BIKE, and ML-KEM. Testing spans two representative platforms: a resource-constrained Raspberry Pi 4B (Broadcom BCM2711, 4GB RAM) representing embedded automotive ECUs, and an Ubuntu-based Intel Core i5 system representing backend or gateway infrastructure. Execution time, memory consumption, and CPU core utilization are measured across algorithm-KEM combinations to characterize real-world feasibility. Results indicate lattice-based schemes offer a strong balance of performance, interoperability, and long-term assurance suited to V2X and PKI-heavy communication, while compact signature schemes such as MAYO and FALCON better serve resource-constrained operations like secure boot and firmware signing, where verification speed and low memory footprint are prioritized over frequent key exchange. The study further identifies a critical dependency of PQC feasibility on 64-bit architecture, highlighting the limitations of legacy 32-bit automotive chipsets that lack dedicated cryptographic accelerators. These findings offer practical, use-case-specific guidance for automotive OEMs and suppliers navigating the transition from classical to quantum-resistant cryptography, supporting risk-informed decisions across onboard and offboard vehicle communication architectures.

We construct the first non-trivial weighted threshold encryption scheme with silent setup. The CRS and each public key consists of O(W) group elements, where W is the maximum committee weight. Both the weight assignments and the threshold for decryption can be dynamically chosen at encryption time. Each partial decryption is a single G1 element computed non-interactively with one scalar multiplication, independent of the party's weight. The CPA ciphertext is two G_1 elements, improving upon the shortest known unweighted scheme, and CCA security costs two additional field elements. We prove security in the generic bilinear group model.

Range proofs are a fundamental building block of lattice-based proof systems. Existing approaches relying on standard Johnson-Lindenstrauss (JL) struggle to provide succinctness: unstructured JL incurs linear verifier complexity, while structured JL introduced in RoK and Roll [ASIACRYPT'25] produce large projection vectors that need to be sent in costly committed form. For a witness of dimension $m$ and a security parameter $\lambda$, the JL projection vector is $O(\lambda),$ but the projection matrix is $O(\lambda m)$. Structured JL can be represented in $\widetilde O(\rho \lambda^2)$, but the resulting projection length grows to $\widetilde O(m / \rho)$ for any trade-off parameter $\rho > 1$. \hspace{5mm} In this paper, we introduce Tensor Train Random Projection (TTRP) to lattice-based cryptography, offering a ``best of both world" structured JL variant. The Tensor Train (TT) matrix representation drops to $\widetilde O(\lambda)$, while maintaining the projection vector at $O(\lambda)$. \hspace{5mm} We show that TTRP can be seamlessly integrated into proof systems by linearizing the well-formedness of the projection with the sum-check protocol. Concretely, using TTRP + sum-check as a drop-in replacement for existing range proof techniques yields an approximate shortness check with $O(\lambda \log m (\log\log m)^2)$ verifier complexity and proof size around $4$ KB for relevant parameter settings.

We propose an efficient threshold mechanism that is well suited for certain hash-based signatures. Our proposal has a number of compelling features: • The final signature assembled from a quorum of signature shares has the same format as a non-threshold hash-based signature. In particular, the verifier is unaware that the signer is thresholdized. Moreover, we can add and remove parties and change the threshold without changing the public key. • Our framework can be used to thresholdize one-time signature schemes, such as Winternitz, and a few-time schemes, such as XMSS, HORS, FORS, and PORS+FP. • The public key and the signatures reveal nothing about the number of parties $n$ or the threshold $t$. • An instantiation of our framework scales well to a large number of parties $n$ and a large threshold $t$. One limitation of the framework is that it does not support an efficient distributed key generation protocol (DKG). Another limitation is that the framework does not directly apply to SLH-DSA. It is primarily designed for the Winternitz, XMSS, and FORS schemes.

Robust asynchronous threshold Schnorr signatures enable honest parties to complete signing despite malicious behavior and network delays. To reduce online latency, these schemes typically follow an offline–online paradigm. The parties prepare batches of shared nonces in the offline phase and consume them to generate signatures online. In high-throughput constructions such as SPRINT (Benhamouda et al.~Eurocrypt 2024), super-invertible matrices are used to extract multiple nonces and their corresponding commitments from a single execution of the nonce-generation protocol. However, the associated group operations incur substantial computational overhead. We identify several computational bottlenecks in SPRINT and present $\mathsf{DASH}$, a suite of robust asynchronous threshold Schnorr signature protocols that substantially improve computational efficiency while retaining SPRINT’s amortized linear communication cost. Our contributions are threefold. First, we propose distributing the group computations involved in nonce extraction among the parties. This reduces the amortized computational cost from $\mathcal{O}(\log n)$ to $\mathcal{O}(1)$ group operations per signature per party. To enable this distributed computation, we employ a batching technique that allows each dealer to distribute $L$ nonce polynomials simultaneously. Second, we introduce an efficient batched share-verification procedure that jointly checks shares of all $L$ polynomials. For concrete parameters, this can accelerate share verification by a factor of $40-60$. We also introduce a simple agreement protocol via player elimination, which could be of independent interest. Finally, under a stronger honest-majority assumption, we develop a packed two-stage online reconstruction protocol that enables parties to reconstruct signatures through error correction. This eliminates the need for signature-share verification, and consequently, avoids the expensive group operations performed by the aggregator in SPRINT. Surprisingly, even in the worst case, our $\mathsf{DASH}$ protocols preserve the same asymptotic amortized computation and communication costs, provided that $L \gg n\log n$. %We prove the security of all $\mathsf{DASH}$ variants in the random oracle model under the standard discrete logarithm assumption.

Threshold ring signatures (TRS) enable a quorum of $T$ users to jointly sign a message while hiding which $T$ of the $N$ ring members participated, supporting privacy-preserving endorsement in ad-hoc settings. That said, many deployments do not need anonymity over every $T$-subset of a ring: when the approval pattern is already public, a structured ring can be sufficient. In this work, we first formalize this setting as a structured threshold ring signature (sTRS) and introduce $\mathsf{LoTRS}$, a lattice-based sTRS that avoids a dedicated leader and keeps interaction to the optimal number of two rounds by separating the threshold signing relation from the anonymity mechanism. To the best of our knowledge, $\mathsf{LoTRS}$ is the first construction in which a TRS variant is obtained by combining: (i) an aggregated signing layer: a two-round lattice-based multisignature protocol producing an aggregated signature relation, with (ii) a selection-hiding layer: a $1$-out-of-$N$ proof that hides the chosen ring element supporting that relation. While it is natural to use a $T$-out-of-$N$ proof to build a TRS, our $\mathsf{LoTRS}$ exploits a $1$-out-of-$N$ proof to significantly improve efficiency. $\mathsf{LoTRS}$ concretely instantiates the aggregated signing layer using $\mathsf{DualMS}$ (Crypto'23) and the selection-hiding layer arising from Esgin et al.'s lattice-based one-out-of-many proof (IEEE S&P'22). Our $(T, N\!\cdot\!T)$-$\mathsf{LoTRS}$ construction achieves $\mathsf{polylog}(N, T)$ signature size and outperforms $(T, N)$-TRS schemes significantly. For example, for $N=100$ and $T=50$, our analytic signature size is $52.66$ KiB, which is $\approx2.3 \times$ smaller than the previously best performing lattice-based scheme $\mathsf{LastRings}$ by Jeon et al (ISC'25). Our Rust reference implementation further supports practicality: for $T=16$ and $N=32$, i.e., structured ring size $T\cdot N = 512$, it produces $42.72$ KiB signatures, with mean signing time $151.4$ ms and verification time $54.56$ ms in a release build on a Ryzen AI 9 HX 370 laptop.

Folding is a core technique in building efficient code-based polynomial commitment schemes with polylogarithmic proof size and verification. To date, there are two families of linear error-correcting codes that have been known to allow folding, i.e., Reed-Solomon (RS) codes and foldable codes. However, neither admits optimal proximity gaps, which constitutes a fundamental bottleneck in the resulting proof sizes. In this work, we give the first folding scheme that enjoys optimal proximity gaps. Specifically, we construct IOPPs (interactive oracle proofs of proximity) for both folded RS (FRS) codes and univariate multiplicity (UM) codes, which achieve optimal proximity gaps $1-R-\varepsilon$ as shown in a recent work of Goyal and Guruswami (STOC 2026), where $R$ is the code rate and $0<\varepsilon<1-R$. Our key observation is that the typical even/odd folding commutes with polynomial reduction for suitably paired moduli, enabling consistency checks via the Chinese remainder theorem. This implies a new generic folding framework that recovers the FRI folding for RS codes and enables efficient folding for FRS and UM codes. We further refine the optimal proximity gap analysis for FRS and UM codes, yielding tighter concrete soundness bounds. Our IOPPs have $O(N)$ prover time and oracle proof size, together with $O(\lambda\log{N})$ query complexity and verification time, where $N$ is the block length and $\lambda$ is the security parameter. These bounds match the asymptotic complexity of FRI while attaining optimal proximity gaps and allowing smaller underlying fields at the same security level. E.g., a $128$-bit field suffices for $100$-bit security.

Incremental preprocessing in private information retrieval (PIR) schemes refers to handle insertions, modifications, and deletions to the database without requiring complete preprocessing after each update. This broadens the applicability of PIR in practical scenarios. However, two major issues remain: the concept of incremental preprocessing for the single-server PIR is still not established, and the row-level update strategy (iSimplePIR (Row-level)) introduces excessive unnecessary overhead. This paper aims to efficiently extend incremental preprocessing to the single-server setting. To our knowledge, we are the first to propose the formal definition of single-server incremental PIR. Besides, we construct an entry-level incremental scheme (iSimplePIR (Entry-level)) based on SimplePIR (USENIX ’23). iSimplePIR (Entry-level) supports real-time updates of individual entries, as well as optimization of communication for scenarios with certain update cycles by incorporating a row aggregation mechanism. For a 1\% column-major update in a 1GB database, iSimplePIR (Entry-level) achieves a 224$\times$ reduction in preprocessing computation overhead and a 4.2$\times$ reduction in both communication and monetary costs compared to iSimplePIR (Row-level). When applied to password breach detection with completely random entry updates, iSimplePIR (Entry-level) reduces preprocessing time by 86$\times$. Meanwhile, our method can be combined with various SimplePIR-based schemes to reduce preprocessing costs, such as DoublePIR, Authenticated PIR (based on the LWE assumption), VeriSimplePIR, and YPIR.

Secure merge considers the problem of combining two sorted lists into a single sorted secret-shared list. Merge is a fundamental building block for many real-world applications. For example, secure merge can implement a large number of SQL-like database joins, which are essential for almost any data processing task such as privacy-preserving fraud detection, ad conversion rates, data deduplication, and many more. We present two constructions with a communication bandwidth and rounds tradeoff. Logstar, our bandwidth-optimized construction, takes inspiration from Falk and Ostrovsky (ITC, 2021) and runs in $O(n\log^*n)$ time and communication with $O(\log n)$ rounds. In particular, for all conceivable $n$, the $\log^*n$ factor will be equal to the constant $2$, and therefore we achieve a near-linear running time. Median, our rounds-optimized construction, builds on the classic parallel medians-based insecure merge approach of Valiant (SIAM J. Comput., 1975), later explored in the secure setting by Blunk et al. (ITC, 2025), and requires $O(n \log^c n)$, $c \approx 1.71$, communication with $O(\log \log n)$ rounds. We introduce two additional constructions that merge input lists of different sizes. SquareRootMerge merges lists of sizes $n^{\frac{1}{2}}$ and $n$ and runs in $O(n)$ time and communication with $O(\log n)$ rounds. CubeRootMerge is closely inspired by Blunk et al.'s (ITC, 2025) construction and merges lists of sizes $n^{\frac{1}{3}}$ and $n$. It runs in $O(n)$ time and communication with $O(1)$ rounds. We optimize our constructions for concrete efficiency. Despite extensive research, efficient secure merge still relies on Batcher's merging network or generic sorting, with $O(n\log n)$ circuit size and $O(\log n)$ depth. Ours are the first constructions to lower their concrete costs through better asymptotics and small constants. Two-party implementations of all four protocols show that, for $n=2^{20}$ 32-bit elements per list, Logstar reduces online communication by $2.09\times$ versus Batcher and $3.69\times$ versus shuffled quicksort. Median reduces Batcher's online rounds by $19.0\%$, using $2.03\times$ its online communication. For unequal inputs, SquareRootMerge and CubeRootMerge reduce Batcher's online communication by $3.34\times$ and $4.69\times$, respectively.

Multiparty Private Set Union (MPSU) allows multiple parties to compute the union of their private sets while revealing no additional information beyond the prescribed output. Existing practical MPSU protocols typically manipulate individual elements and rely on a distributed shuffle to hide element ownership, introducing an $O(n)$ round-complexity bottleneck. We present United, a shuffle-free MPSU framework based on a new data-structure abstraction, Oblivious Insert-Only Invertible Sketches (OIIS). Rather than anonymizing an element-wise intermediate representation, the parties directly construct a protected symmetric sketch of the union. Conditional oblivious insertion ensures that each distinct union element is inserted exactly once while hiding the insertion condition and modified locations. We provide two realizations of OIIS. Our HE-based construction instantiates OIIS with a standard Invertible Bloom Lookup Table protected by multi-key partially homomorphic encryption, while our MPC-based construction uses additive secret sharing and introduces a new row-local power-sum OIIS technique for efficient conditional insertion. We implement and evaluate both constructions. Across the evaluated configurations, our MPC-based construction achieves up to $3.10\times$ lower runtime in LAN settings, while our HE-based construction achieves up to $2.73\times$ lower runtime in WAN settings compared with prior MPSU protocols.

We present the first polynomial-time attacks against certain parameter choices of the low-dimensional vector representation (LDVR) problem, introduced by Crites, Katz, Komlo, Tessaro, and Zhu (CRYPTO '25) to prove the adaptive security of FROST in the Algebraic Group Model. Building on work by Crites and Stewart (CRYPTO '25), they also show that every attack against LDVR directly yields an adaptive attack—i.e., one leveraging adaptive corruptions—against any threshold Schnorr signature that exposes to the attacker the values $g^{\mathrm{sk}_i}$ for the secret-key shares $\mathrm{sk}_i$ held by the signers, where $g$ is a generator of the underlying group. This class of protocols includes FROST (Komlo and Goldberg, SAC '20), Sparkle (Crites, Komlo, and Maller, CRYPTO '23), Lindell's three-round protocol (CiC '24), along with other masking-free protocols. Consequently, our results give the first polynomial-time adaptive attacks against a class of practical threshold signatures. Our attacks require a large, but still polynomial, number of signers: asymptotically, we require $n = \Theta(\log^2 p)$ signers and corrupt $t_c = \Theta(\log p)$ of them. For the prime-order subgroup of Curve25519, concrete and optimized instantiations of our attack require $n=5020$ signers and corrupt $204$ of them. This exceeds the signer counts commonly encountered in practice, but falls within the scenarios considered by NIST's call for threshold signatures. At the theoretical level, our results also yield a non-artificial separation between static and adaptive security based on a real-world multi-party protocol. Our results arise from a new reduction from LDVR to structured subset-sum problems determined by the evaluation points of the polynomial used to secret-share the signing key. We further show that allowing these evaluation points to be chosen adversarially can lead to substantially more efficient attacks.

Traditional secure multiparty computation (MPC) protocols assume a fixed set of participants throughout the computation. Dynamic MPC (DMPC) relaxes this assumption by permitting parties to join or leave during the process. However, practical deployment of DMPC in Internet settings favors tolerating asynchrony and achieving guaranteed output delivery (GOD). Recently, AD-MPC [CCS 2025] introduced an asynchronous DMPC (ADMPC) achieving this goal, but its reliance on per-epoch preprocessing and masking randomness incurs substantial concrete overhead. In this paper, we present Continuum, a concretely efficient ADMPC protocol with GOD. We introduce an aggregated hand-off protocol that ensures transfer consistency across epochs while eliminating per-epoch masking randomness, and a batch multiplication protocol based on the BGW paradigm that defers degree reduction to the hand-off phase and aggregates verification for all multiplications into succinct proofs. Together, these protocols enable a non-interactive computation phase with interaction concentrated in an efficient hand-off phase, overcoming the primary concrete inefficiencies of prior ADMPC designs. We implement Continuum and evaluate its performance on up to 128 geographically distributed servers. In experiments on 22 servers with circuits of depth 6 and width 100, Continuum reduces linear-gate transfer latency from 76.60s to 15.13s (80% reduction) and multiplication-gate evaluation time from 476.62s to 35.67s (93% reduction), compared with AD-MPC, while preserving strong security guarantees.

We propose a new variant of the Fiat–Shamir transformation where the Fiat-Shamir hash is instantiated by an external verifiable random function (VRF) service. We prove that soundness holds as long as the VRF secret key remains hidden from the prover, i.e., assuming no collusion between the prover and the VRF evaluator. Crucially, due to the public verifiability of VRF outputs, the VRF computation itself need not be trusted beyond the key-generation phase. This yields the first NIZK compiler in a non-idealized model that is both practical and provably sound. Our transformation can be instantiated using extensively deployed blockchain-based VRF services. Moreover, it naturally supports distributed VRF services, allowing the no-collusion assumption to be relaxed: soundness holds even if the prover colludes with up to a threshold number of evaluators. In this setting, distributed key generation for the VRF further eliminates trust in the setup. A distinctive feature of our approach is that the verification step is local and does not require accessing the VRF. This is particularly advantageous for recursive proof systems such as incrementally verifiable computation, where the verification circuit must be embedded within the circuit for which a proof needs to be generated. This enables construction of the first provable and practical recursive proof -- bypassing well-known impossibilities in the random oracle model. We demonstrate the real-world utility of our framework with an implementation for the GKR protocol.

For many applications of SNARKs, a key bottleneck is proving large batches of standard cryptographic hash evaluations, such as SHA-256, Keccak, or BLAKE3. We introduce Flock, a hash-based SNARK for extremely fast proving of such batched Boolean computations. Flock proves batches of the same R1CS circuit (plus input/output relations between them), can prove hash-chains and Merkle path openings, and in principle can be extended to full-fledged hash-based signature verification. At its core, Flock combines new optimizations for the lincheck and zerocheck protocols with an aggressively optimized proof-of-concept implementation co-designed by coding agents. On a single core of an M4 Max processor, Flock proves 82k evaluations of the BLAKE3 compression function, 42k SHA-256 compressions, and 30k Keccak permutations per second — less than a $250\times$ overhead over native execution. On ten cores, throughput exceeds 660k BLAKE3 compressions per second; in proving SHA-256, Flock is more than $9\times$ faster than Binius64, the prior state of the art, and more than $500\times$ faster than the fastest elliptic curve-based SNARK we measured against.

We construct the first polynomial commitment in groups of unknown order that simultaneously requires no trusted setup, has quasilinear prover time, and has constant-size opening proofs. Our main technical contribution is a transparent class group realization of the subset-product accumulator relation introduced by Morphic accumulators (CRYPTO ’26). It supports accumulating a fixed family of class group elements and proving prescribed algebraic relations among the accumulated elements, yielding constant-size range arguments with quasilinear prover time. Combining these range proofs with the DewTwo framework (CRYPTO ’25) gives the first transparent polynomial commitment with quasilinear prover time and constant-size openings. Concretely, our construction also gives the shortest known opening proofs (1.3 KB) among transparent polynomial commitments. We prove security under falsifiable class group assumptions and also develop new extraction techniques over dyadic rationals, which may be of independent interest.

We present protocols where one entity, the server, evaluates a circuit with encrypted inputs from the second party, the client. We give secret key somewhat additive homomorphic schemes where the client has perfect privacy (server is computationally unbounded). The key idea for client privacy is the permutation table which consists of rows of vectors modulo a prime integer m: The initial row is (1, d2, ..., dc) where di-1|di, di > N(a + 1)di-1, for an integer N which is a power of 2 and integer a, 2 <= i <= c. Subsequent rows are integer multiples of the 1st row, modulo m. The permutation table has a subset of rows (vectors) whose components are relatively short (facilitating addition without overflowing m) and which map to every possible vector modulo N (giving perfect privacy since every plaintext vector is possible given a ciphertext vector from the table.) We give a 2-party computation (2PC) protocol that also incorporates server inputs where the client has perfect privacy, assuming the server is semi-honest in the setup protocol. Client privacy is statistical if the server is malicious during the setup protocol. Server privacy only holds against a computationally bounded adversary since it depends on the hardness of a variant of the HSSP (Hidden Subset Sum Problem) and the DDH (Decisional Diffie Hellman Assumption). We leverage the Castagnos Laguillaumie linear homomorphic public key encryption for setup. The 2PC protocol maintains circuit privacy, without circuit expansion, except for leaking the number of AND gates to the client. Scaling the 2PC protocol via separate encryption parameters for smaller subcircuits allows the ciphertext size to remain constant as circuit size grows.

Computing smooth-degree isogenies between supersingular elliptic curves with known endomorphism rings is a fundamental task in isogeny-based cryptography. Via the Deuring correspondence, this task is equivalent to finding a connecting ideal of smooth norm between the corresponding quaternion maximal orders. KLPT-type algorithms address this problem by transforming a known connecting ideal into an equivalent ideal of smooth norm. Although connecting ideals of norm approximately $p$ are expected to exist, the best known such algorithms for general input only achieve norm $\widetilde{O}(p^{4.5})$. In this paper, we propose $\Delta$-KLPT$^+$, a new KLPT-type algorithm that lowers this bound to $\widetilde{O}(p^4)$. Our construction builds on $\Delta$-KLPT, which attains a smaller norm bound but requires two input ideals of the same prime norm. To extend $\Delta$-KLPT to arbitrary inputs, we introduce a new subroutine IdealNormReduce, which reduces the common norm of an ideal pair. By iterating IdealNormReduce, we obtain two ideals with a common norm below $p$. Then we apply $\Delta$-KLPT to the resulting ideal pair to obtain a desired connecting ideal of smooth norm. As an application, we construct Delfar, a fully anonymous isogeny-based ring signature scheme. Compared to Erebor-full, Delfar achieves shorter signatures and lower signing and verification costs for large rings.

We present Couplet, a new pairing-based multivariate polynomial commitment scheme (PCS). Couplet is the first multivariate PCS whose opening proofs are solely two group elements. In addition, for the case of multilinear polynomials, Couplet is the first constant-proof PCS with a prover that requires only a sublinear number of group operations. We achieve those properties simultaneously at the expense of a quasilinear, polynomial-specific, one-time preprocessing phase, whose cost can be amortized over multiple subsequent openings. On BN254, our implementation opens multilinear polynomials with $20$ variables about $20\times$ faster than Mercury after preprocessing, breaking even in total prover time after roughly 100 openings. Our approach generalizes to batched evaluation proofs, yielding a constant-size proof for multiple evaluation points without using random oracles. Applications include verifying repeated inferences of a committed model as well as more efficient auditable authenticated dictionaries. Our main technique involves compressing Papamanthou--Shi--Tamassia (PST) evaluation proofs, giving a single commitment which encodes all $\log n$ quotient polynomials which are normally given out separately in a PST proof. In doing this, we reduce the verification to a univariate sumcheck problem, which we solve with techniques from Groth16 using a single additional group element. We prove extractability in the algebraic group model under a parameterized discrete-logarithm assumption. We give hiding variants and prove perfect zero-knowledge of the opening protocols. All opening protocols are noninteractive and require no random oracle.

Certified deletion enables a party to prove that it has erased the sensitive information contained in a quantum state. Bartusek and Raizes (CRYPTO 2024) gave the first secret-sharing scheme with privately verifiable deletion. Subsequently, Katz and Sela (EUROCRYPT 2025) constructed secret-sharing schemes with publicly verifiable deletion under computational assumptions. Constructing such a publicly verifiable scheme without cryptographic assumptions remains open. In this work, we introduce an intermediate notion called unanimously verifiable deletion. While private verification relies on the dealer and public verification allows any third party to verify deletion, unanimous verification assigns the verification responsibility to the parties in the secret-sharing scheme themselves. We construct an information-theoretically secure linearly homomorphic threshold secret-sharing batch scheme with adaptive unanimously verifiable deletion. In particular, to obtain its linear-homomorphic property, we exploit a linearly homomorphic structure of BB84-type states that enables linear transformations on encoded values while preserving certified deletion. More generally, this structure can be used to upgrade certain primitives with certified deletion to their linearly homomorphic counterparts. As another major contribution, we demonstrate an application of this batch scheme by constructing outsourced multi-party computation (MPC) protocols for arbitrary arithmetic circuits. Our outsourced MPC has semi-honest classical clients and malicious quantum servers, achieves adaptive unanimously verifiable deletion security in the trusted-preprocessing and security-with-abort setting against a rushing adversary, and supports public output reconstruction. The adversary may adaptively corrupt up to $n-1$ clients. For the servers, during the online execution, at most $t$ corrupted servers may remain undeleted and at least $t+1$ honest servers must remain undeleted, for any $t<n/2$. After successful finalization, all servers may be corrupted without revealing additional information about the remaining clients' inputs beyond the public output and the corrupted clients' inputs.

MPC-based privacy-preserving machine learning (PPML) typically operates over finite rings rather than floating-point arithmetic, making arithmetic overflow an inherent risk. Existing overflow-detection techniques generally require the evaluation of nonlinear functions, resulting in substantial computation and communication overhead. We propose Soft Boundary Detection, which reduces boundary verification to probabilistic functions over partitioned intervals, with a cost comparable to that of linear computation. Building on this abstraction, we develop an efficient mechanism for detecting arithmetic overflow in PPML workloads. Moreover, we show that Soft Boundary Detection naturally extends to the malicious-adversary setting. In ring-based computation, it further avoids the need to choose a ring space substantially larger than the actual data range to ensure soundness against malicious behavior. Our framework provides two key benefits: (1) highly efficient arithmetic overflow detection, and (2) active security without requiring ring extension or enlarging the underlying ring space. Experimental results demonstrate that our approach substantially strengthens security while retaining high efficiency, providing a practical solution for robust and actively secure PPML.

Lattice-based proof systems are one of the leading routes to quantum-safe succinct proofs. Existing lattice-based schemes come with inherent limitations arising from the coupling between the commitment and constraint domains. First, commitment efficiency is restricted by the need for invertible challenge differences, which precludes the use of fully splitting moduli that enable the fastest lattice arithmetic. Second, the characteristic of the constraint field must equal the commitment modulus. This limits the efficiency of proving binary computations, including standard hash function evaluations. We present $\mathsf{LaBinius}$, a lattice-based polynomial commitment scheme, in which the evaluation arithmetic is separated from that of the commitment. The commitment runs over a composite modulus, and all of its prime factors are NTT-friendly. The evaluation claim lives in a binary extension field, without bitness checks or overhead over a binary arithmetisation. We implement the scheme with AVX-512 kernels and connect it to the $\mathsf{Binius}$ and $\mathsf{Flock}$ front ends in an almost black-box way, which lets us use their arithmetisations tailored to binary fields. As a result, we obtain a SNARK for standard hashes. Proving $\mathsf{Keccak}$-$\mathsf{256}$, $\mathsf{SHA}$-$\mathsf{256}$ and $\mathsf{BLAKE3}$ on one core, our prover takes at most $1.2$ times as long as the hash-based prover supplied with each system, and we obtain a single-core throughput of over $67{,}000$ $\mathsf{BLAKE3}$ compressions per second with verification in under $40$ milliseconds. With $\mathsf{LaBRADOR}$ as a recursive compressor, the prover takes less than twice as long as the hash-based provers at the largest sizes we consider, while the proof size is below $100$ KiB. This is about five times smaller than the proofs of $\mathsf{Binius}$ and $\mathsf{Flock}$ at those sizes and constitutes the smallest quantum-safe proof of a standard hash evaluation to date.

The Groth16 verification equation has a compact algebraic description, yet garbling its Boolean implementation can require tens of gigabytes. We show how to garble this computation using native elliptic-curve group operations. Motivated by proof verification in trust-minimized Bitcoin bridges, we construct a projective partial garbling scheme for conditional disclosure on invalid Groth16 proofs. For a fixed verification key and public statement, evaluation reveals a garbler-held secret when the supplied proof is invalid and hides the secret when it is valid. The proof itself remains public. The main technical challenge is handling a pairing whose two arguments are supplied by the evaluator. We introduce a rekeying gadget that resolves this using a single private scalar multiplication. Building on Argo MAC (Eagen and Lai, 2026), BABE (Garg et al., 2026), and Duty-Free Bits (Khambhati et al., 2026), we prove a composition theorem for partial garbling across input representations and apply it to transform group encodings into bitwise projective encodings. This requires extending the projectivization technique of Duty-Free Bits to quadratic extension fields. The resulting garbled program has size $O(\lambda^2)$ bits, where $\lambda$ is the computational security parameter. We prove privacy under the decisional Diffie-Hellman assumption, in the random oracle model. Our BN254 implementation produces a 2.4 MiB garbled program, including projectivization, compared with the 48 GB reported for Boolean garbling of Groth16. Thus, we improve over prior state of the art in Groth16 garbling by over four orders of magnitude.

In verifiable outsourcing, an untrusted server runs an expensive computation and produces a succinct proof (called a SNARK) of the results. In many scenarios, the computation accesses a RAM that the server maintains a commitment to (persistent RAM) or that is initially zero (volatile RAM). But, SNARKs for such scenarios are limited by the high overheads associated with existing techniques for RAM checking. We develop new proofs about volatile, persistent, and sparse persistent RAM that reduce SNARK proving times. Our results include both asymptotic and concrete improvements---including a proving time reduction of up to 51.3$\times$ for persistent RAM. Along the way, we apply two tools that may be of independent interest. First, we generalize an existing construction to convert any algebraic interactive proof (AIP) into a SNARK. An AIP is a public-coin, non-succinct, interactive proof with a verifier that is an arithmetic circuit. Second, we apply Bézout's identity for polynomials to construct new AIPs for uniqueness and disjointness. These are useful for showing the independence of accesses to different addresses.

Known lower bounds prohibit the construction of very-efficient authenticated dictionaries that support both insertions and deletions. It remains an open question, however, whether it may be possible to construct very efficient authenticated dictionaries that are \emph{insertion-only}. The current paper answers this question in the affirmative, providing the constructions that strictly dominate the classic Merkle tree in the incremental setting. Our first result is an authenticated incremental dictionary, called the exponential Verkle forest, that supports retrieval queries with time and proof size $O(\log \log n)$ and that supports insertions with time and proof size $O(\log \log \log n)$. The data structure also offers an \emph{amortized} bound of $O(1)$ for insertions. Building on this, we also present a full-query version of the dictionary, supporting both retrieval and exclusion queries. This data structure continues to support retrieval queries in time and proof size $O(\log \log n)$, while supporting all other operations in time and proof size $O(\log n)$. Our results take a purely data-structural perspective on authenticated data structures, seeking to achieve the best bounds possible with the cryptographic primitives (collision-resistant hashing and position-binding vector commitments) that already exist. We also give partial evidence, in the form of a lower bound that applies to a natural class of data structures, that our $O(\log \log n)$ query bound is optimal for any solution with linear construction time.

Folding schemes are gaining traction recently as they are suited to prove streaming computations with low memory footprint. In particular, there has been a growing interest in post-quantum folding schemes for more expressive relations, and with improved proof sizes. While the landscape is vast, every lattice-based construction, such as Latticefold+, (Super)Neo, and Cyclo, heavily rely on the sumcheck protocol. Sumcheck gives efficient proving times, but the verifier circuits become very large, partially because of the many random oracle invocations required. When folding sequential computations, this significantly inflates the recursive overhead, as the prover must run the verification at every iteration. We present ProtogaLattice, a new lattice-based folding scheme for general high-degree polynomial relations that drastically reduces the size of the verifier's circuits. Our folding backbone deviates from the sumcheck approach and uses algebraic techniques. Our contribution is twofold: i) a folding scheme that combines multiple instances of polynomial relations into accumulators for a bounded number of iterations, and ii) a bootstrapping protocol to reduce the norm of the witnesses underlying these accumulators, which can be used in complement to our bounded-depth folding scheme to unlock unlimited depth. A full iteration of ProtogaLattice for witnesses of length $2^{30}$ gives a 4$\times$ shorter proof size than the state-of-the-art, with only $8.13$ KB. Additionally, ProtogaLattice requires less random oracle evaluations and achieves a smaller verifier circuit than its sumcheck counterparts. Our techniques open new directions towards building efficient lattice-based proofs for expressive relations and that present small recursion overheads, challenging the established sumcheck-based approaches.

Correlation-robust (CR) hashing and its variants are central components in efficient secure-computation protocols, including OT extension, garbled-circuit optimizations such as Free-XOR and half-gates, and GGM-style tree constructions. In practice, these hashes are typically instantiated from block ciphers such as AES. Prominent constructions include the Matyas-Meyer-Oseas (MMO) construction and its variants such as \(\widehat{\mathsf{MMO}}\). Existing analyses, however, are classical and do not cover quantum adversaries with superposition access to the underlying random permutation or ideal cipher. We establish post-quantum security for these practical block-cipher-based CR hashes. In the quantum ideal cipher model (QICM), we prove multi-user tweakable correlation robustness with leakage (mTCRL) for the MMO construction, and multi-user tweakable circular correlation robustness with leakage (mTCCRL) for \(\widehat{\mathsf{MMO}}\) and the Encryption-with-Feed-Forward ($\mathsf{EncFF}$) construction. These results also imply the corresponding leakage-free and single-user guarantees: CR and TCR for MMO, and CR, CCR, TCR, and TCCR for \(\widehat{\mathsf{MMO}}\) and \(\mathsf{EncFF}\). Security in the quantum random permutation model (QRPM) follows as a special case. We further verify that, in the QICM/QRPM, the above MMO-type constructions securely instantiate CR-type hashes used in various existing protocol analyses. This covers several representative analyses involving OT extension, half-gates garbling, (correlated) GGM trees, and certain distributed point/comparison function constructions. When the remaining components are post-quantum secure or modeled as ideal functionalities, the resulting protocol instantiations are post-quantum secure in the corresponding model. Technically, our proof relies on the reprogramming-and-resampling technique of Alagic et al.~(Eurocrypt 2022). To handle adaptive key leakage, as needed for some malicious OT-extension analyses, we introduce the conditional min-entropy with leakage (cmel) advantage, which separates leakage-induced entropy loss from the quantum ideal-cipher analysis. Without leakage, our bounds guarantee security up to roughly \(2^{\rho/3}\) queries, where \(\rho\) is the min-entropy of the secret shift.

Zero-knowledge proofs of knowledge are a fundamental building block in many isogeny-based cryptographic protocols, such as signature schemes based on identification-to-signature transformations, or multi-party ceremonies that avoid a trusted setup, in particular for generating supersingular elliptic curves with unknown endomorphism rings. In this paper, we construct SPRINT, an efficient polynomial IOP-based proof system that encodes the radical $2$-isogeny formulas into a system of multivariate polynomials. When combined with the recent polynomial commitment scheme (PCS) DeepFold, our construction yields substantial improvements over state-of-the-art isogeny proofs of knowledge. For the SQIsign NIST-I prime $p=5 \cdot 2^{248}-1$, our implementation takes only a few milliseconds for proving and verification, with proof sizes around 80 kB. Compared to the previous state-of-the-art proof system by den Hollander, Mula, Slamanig & Spindler (PQCrypto'26), we achieve speedups ranging from $1.1\times$ to $22.7\times$ for the prover and from $4.4\times$ to $109\times$ for the verifier, while achieving proof sizes that are $1.4\times$ to $17.5\times$ smaller, across different instantiations and parameter sets. Moreover, we study the weak simulation extractability of our proof system, which we can use as a starting point for a modular construction of signatures. We show that any Fiat–Shamir compiled interactive proof with a so-called canonical simulator is weakly simulation-extractable. We expect this general result to be applicable to other proof systems and thus of independent interest. Building on SPRINT and our wSE result, we introduce a new family of signature schemes whose security solely relies on the $\ell$-isogeny path problem, a foundational problem in isogeny-based cryptography. As a concrete instantiation, we construct a signature scheme using DeepFold as the PCS. Across the different parameter sets, a prototype implementation of our scheme sees significantly faster signing times than the highly optimized NIST specification for SQIsign, at the cost of much larger signature sizes and excluding a one-time precomputation phase. When this phase is instead included with the signing time, we still get almost on-par timings. Meanwhile our signature scheme relies on weaker assumptions and is constant-time when instantiated with a suitable PCS. Even though our signatures are large, the framework offers flexibility for tradeoffs and optimizations – both within a given PCS and by switching to alternative PCS constructions. In particular, it will naturally inherit efficiency gains from future advances in plausibly post-quantum secure PCS constructions.

We introduce RisePIR, the first preprocessing keyword private information retrieval (PIR) scheme that absorbs insert, update, and delete on its key-value store at a cost proportional to the number of mutations alone. Where the static state-of-the-art schemes ChalametPIR and $\mathsf{KPIR}^{\mathsf{index}}$ re-run their preprocessing from scratch on every change, RisePIR patches its preprocessing in place and stays as practical as both in the online phase. We give a generic construction of incremental preprocessing keyword PIR from any updatable preprocessing index PIR, an index PIR that efficiently supports in-place update. The construction rests on our $d$-ary Segmented Cuckoo Filter, a cuckoo filter that confines the $j$-th candidate bucket of every key to the $j$-th of $d$ segments and stays dynamic under partial-key cuckoo hashing. Instantiating the construction over FrodoPIR and SimplePIR, each equipped with the entry-level hint patch of iSimplePIR, gives RisePIR-F and RisePIR-S, both secure under decisional LWE. On a store of about one million keys, both variants patch their hint in place in 0.06–4.7 ms per mutation, five to six orders of magnitude faster than the 56–686 s full re-run of the preprocessing phase. Their online phase stays competitive with ChalametPIR and $\mathsf{KPIR}^{\mathsf{index}}$ in both asymptotic and concrete cost. We deploy RisePIR-S as a privacy-preserving eth_getBalance service over the $2.05 \times 10^{8}$ accounts of Ethereum mainnet, so that a wallet reads a balance without revealing to its RPC provider which account it holds. The running service answers a private query in 0.69 s and absorbs each block's changes in 5.6 ms, well inside the 12 s block interval. The filter and RisePIR ship as an open-source Rust implementation, together with the benchmark harness behind every number in this paper.

Polynomial commitment schemes (PCSs) are fundamental cryptographic primitives, with applications to SNARKs, data availability, and privacy preserving protocols. Many efficient transparent PCSs are built from interactive oracle proofs of proximity (IOPPs) for codes in the Hamming metric. In constructions based on the fast Reed-Solomon IOPP (FRI), low degree polynomials are encoded as Reed-Solomon (RS) codewords over suitable evaluation domains, and FRI is used to test proximity to the RS code. The efficiency of this approach relies on fast Fourier transform (FFT) based encoding and recursive proximity testing through folding operations. Motivated by applications of rank metric codes in post quantum cryptography, random linear network coding, and distributed storage, we develop an analogous framework based on Gabidulin codes, the rank metric counterparts of RS codes. These codes encode $q$-linearized polynomials of bounded $q$-degree over $\mathbb F_{q^m}$ by evaluating them at $\mathbb F_q$-linearly independent points in this field. We construct a recursive FFT for these polynomials and show that its algebraic structure supports both proximity testing for Gabidulin codes and succinct verification of polynomial evaluations, yielding a FRI-style PCS for $q$-linearized polynomials. Our contributions are as follows. \begin{enumerate} \item[(1)] \textbf{FFT algorithms for $q$-linearized polynomials.} For every $O(1)$-smooth positive integer $n\mid m$, we construct an $\mathbb F_q$-linearly independent evaluation set $\mathcal A\subseteq\mathbb F_{q^m}$ of size $n$. On this set, we present FFT and inverse FFT algorithms for evaluating and interpolating $q$-linearized polynomials of $q$-degree less than $n$ over $\mathbb F_{q^m}$. Both algorithms require $O(n\log n)$ operations in $\mathbb F_{q^m}$. Consequently, Gabidulin codes defined over $\mathcal A$ admit encoding with the same complexity. \item[(2)] \textbf{A FRI-style IOPP for Gabidulin codes.} The recursive structure of our FFT induces a folding operation that reduces a Gabidulin code instance of length $n$ to one of length $n/2$. Combining this operation with recent proximity gap results for Gabidulin codes, we construct a FRI-style IOPP, which we call the Fast Gabidulin IOPP (FGI). The soundness analysis accounts for the Frobenius twists introduced by folding and their effect on rank metric proximity. \item[(3)] \textbf{A FGI based PCS for $q$-linearized polynomials.} The usual quotient based opening reduction in PCSs for ordinary polynomials does not directly preserve for $q$-linearized polynomials. We instead use the FGI folding structure to recursively reduce the proximity claim and the evaluation claim together. Combined with Merkle tree commitments, this yields a transparent PCS for $q$-linearized polynomials with polylogarithmic proof size and verification time. \end{enumerate}

The increasing deployment of unmanned aerial vehicles (UAVs) in communication, surveillance, and other mission-critical applications has created a growing requirement for efficient mechanisms to preserve the integrity of exchanged data. UAV platforms may operate under computational, memory, energy, and communication constraints, making lightweight cryptographic techniques an important consideration for secure data processing. This paper investigates the applicability of lightweight cryptography for UAV data integrity using two extendable-output functions (XOFs), Ascon-XOF128 and SHAKE128. A mathematical framework is developed to represent UAV messages, cryptographic processing, integrity verification, and relevant security and performance metrics. The two XOF constructions are analyzed with respect to their internal structures, sponge-based processing, security properties, computational characteristics, and suitability for resource-constrained UAV communication. A comparative evaluation framework is established using message-size and output-length variations, with performance and integrity-related measures including execution time, throughput, computational cost, memory usage, communication overhead, and Hamming-distance-based analysis. The study aims to provide an evidence-based comparison of Ascon-XOF128 and SHAKE128 for UAV data-integrity workloads and to identify the practical trade-offs between lightweight resource requirements and cryptographic integrity performance.

The cosine function is widely used in machine-learning applications, but evaluating it on secret-shared data is difficult. Conventional approaches use polynomial approximations or lookup tables, whose costs grow substantially over large input domains. More recent protocols first reduce the private input modulo the cosine period, but securely performing this modular reduction also incurs significant cost. We present a period-aligned two-party cosine protocol. Based on the cosine addition rule, it rescales each share so that a wrap of the input modulus corresponds to a full $2\pi$ period and therefore does not change the recombined cosine. Each party evaluates sine and cosine locally on its share, while the secure computation uses only two cross-party products and one fixed-point output conversion. We evaluate the protocol directly on synthetic inputs and within private RFF-based RBF-SVM prediction. Comparisons with the protocol of Xing et al. (NDSS 2025) and Guo et al. (USENIX Security 2026) demonstrate better efficiency of our proposed protocol.

Private aggregation schemes enable aggregation of sensitive data across clients without leaking any individual client's input. Their applications include privacy-preserving federated learning, private heavy hitters, and anonymous systems. Many private aggregation schemes assume two non-colluding servers and aim to guarantee privacy even when one server is malicious, i.e., the malicious server learns an aggregation result that includes all honest client inputs. However, many private aggregation schemes in the literature fail to achieve privacy, which we believe is in large part due to a lack of formalism for the nuanced variations of privacy guarantees. In this work, we present ideal functionalities for several variants of private aggregation. We also formalize a common paradigm underlying most prior private aggregation schemes. The formal treatment helps us identify security flaws or underspecifications in existing private aggregation schemes. We then present modular modifications or fill in critical details to help prior schemes in the share-aggregate paradigm securely realize the private aggregation functionalities we formally define, including in settings where clients may have unreliable networks.

The Signal protocol is a prominent messaging protocol that secures communication for billions of users. It powers WhatsApp, the most widely used messaging application worldwide, and the Signal app, popular among privacy-conscious users. Extensive research in the computational and Dolev-Yao settings provides strong formal security guarantees for the protocol itself. However, a gap remains between the guarantees of the protocol specification and the implementation’s actual behavior at runtime. In this work, we bridge this gap by applying SpecMon, a recently proposed runtime monitor, to check whether observed executions conform to formal protocol models. To this end, we instrument two applications (WhatsApp Web and Signal Desktop) to capture their interactions with the network and the cryptographic components. Using this instrumentation, we develop two multiset-rewrite models that are compatible with Tamarin, thus enabling verification. We derive the first model of WhatsApp Web’s implementation of the Signal protocol and the most detailed model to date of Signal’s original protocol. Monitoring establishes that observed executions conform to these models, relative to the trusted event extraction and the symbolic abstraction. For the core components of the Signal protocol, we verify authentication and secrecy properties. Finally, monitoring reveals previously undocumented differences between the original libsignal library and WhatsApp’s fork. We evaluate our methodology and demonstrate its reproducibility. Developing the WhatsApp Web model, instrumenting the app, adding fuzzing, and running the experiments took three person-weeks. We also demonstrate efficient monitoring of real-world applications and detection of deliberately injected security faults, with low overhead in our measured setting.

A sender wishes to broadcast a message across an open, permissionless network (e.g., on the dark web) such that whoever is around and active reaches agreement, even if the sender is malicious. Crucially, no a priori knowledge of the number of parties or their identities is given, and no assumptions are made regarding the number of honest parties or existence of resource-allocation mechanisms, like proof-of-work or stake. The above is an instance of Byzantine broadcast (BB) with unknown-participants (UP Broadcast). Despite extensive research on dishonest-majority BB, existing approaches (such as Dolev-Strong broadcast) fail in this setting, as they rely on knowing the number of parties or corruption bounds. A key challenge, which might appear as an inherent limitation, is that malicious parties can join dynamically, making it difficult for honest parties to terminate without violating consistency. In this work, we provide the first definitions of UP Broadcast, accommodating both static and dynamic participation under arbitrarily many corruptions. We show that the problem is solvable by introducing a novel primitive called active-parties set agreement (APSA), which we use to construct a polynomial-time deterministic UP Broadcast protocol (as well as UP Interactive Consistency). Our protocols guarantee consistency and validity for all honest parties active throughout the execution. Furthermore, we settle the round complexity of UP Broadcast by proving that our deterministic protocols are round-optimal, matching a lower bound that holds even for randomized protocols. Finally, while we establish negative results for unrestricted dynamic participation where parties may join late, we formulate best-possible guarantees for late-joining parties alongside matching round-optimal constructions.

We study $t$-out-of-$n$ threshold fully homomorphic encryption (ThFHE) based on Shamir secret sharing (SSS) in the asynchronous setting. With SSS, a partial decryption share is a single ring element; this allows to avoid the large number of ring elements stored per party required by prior strongly secure constructions based on $\{0,1\}$ reconstruction coefficients. However, this reduction introduces a fundamental trade-off: Lagrange reconstruction during distributed decryption severely amplifies noise, forcing a substantially larger ciphertext modulus. In this work, we give SSS-based asynchronous ThFHE constructions over standard RLWE-based FHE schemes (BFV, BGV, and CKKS) for both standard and strong simulation security. Through tight analysis of the modulus constraints, our constructions simultaneously reduce the required modulus, compared with prior asynchronous Shamir-based constructions, and the per-party storage, compared with the prior strongly secure construction. For example, for $n=512$ under standard simulation security, our analysis reduces the modulus overhead of distributed decryption by $33 \%$ at $t=n/2$ and by up to $90\%$ for $t$ close to $n$, relative to the prior works. Under strong simulation security, the per-party storage for $n=16$ and $t=8$ at $128$-bit security drops from $79$ GB in prior work to $897$ KB.

Succinct polynomial commitment schemes are a key building block in succinct non-interactive arguments of knowledge (SNARKs). Existing succinct lattice-based polynomial commitment schemes take a "split-and-fold" strategy making use of homomorphism to compress proof size to $O(\text{polylog} N)$ for polynomials of size $N$. Prior works either (1) incur superlogarithmic verifier work (e.g., $O(\sqrt{N})$), (2) incur concretely large proof sizes and verifier work (e.g., hundreds of MB), or (3) rely on non-standard lattice assumptions. We proprose a new succinct polynomial commitment scheme Maltese that operates over a Merkle tree commitment of the lattice-based Ajtai hash function. We employ a folding strategy and propose new sum-check-based reductions for managing norm growth of the tree commitment over folding rounds. Maltese is secure under the standard Module-SIS assumption and produces opening proofs of $335$KB for multilinear polynomials of size $N=2^{30}$; proofs are around $300\times$ smaller than prior work with polylogarithmic verifier complexity but between $2$-$6\times$ larger than prior work with larger verifier complexity or stronger structured assumptions.

Systems for private group-by aggregation (e.g., computing histograms, min/max values, or averages) let a confidential virtual machine (CVM) generate statistics from streaming user data. A particular challenge in such systems is ensuring that the CVM's memory-access patterns do not reveal (too much) private information to the untrusted host. While it is possible to rely on oblivious RAM (ORAM), doing so imposes a significant performance penalty and requires allocating sufficient memory to handle a worst-case data stream. We introduce ROGA, a scheme for Resizable Oblivious Group-by Aggregation. ROGA uses an extension of oblivious single-access machines and thus improves performance, both asymptotically and concretely, relative to using ORAM. It also incorporates a novel, differentially oblivious resizing mechanism that ensures the allocated memory is within a constant factor of the memory used by a non-oblivious solution. ROGA also parallelizes cleanly across multiple cores for improved performance. We implement ROGA in Rust and use Binsec/Rel to verify trace noninterference of its compiled fixed-capacity operations, resize estimator, and fixed-work noise sampler, showing that executions with equal public parameters have identical branch-target and memory-address traces for all secret inputs. The only data-dependent branch is the differentially private resize decision. Compared to state-of-the-art oblivious schemes for confidential analytics (which do not support private resizing), ROGA is up to 50.4$\times$ faster when sharded across 64 logical cores, and private resizing cuts memory by up to 14$\times$ compared to domain-provisioned instances. In a case study, ROGA using 16 cores processes the standard network statistics of a 277-million-packet backbone trace with $5.3\times$ end-to-end overhead over a non-oblivious pipeline while exactly matching the reference output.

Internet voting aims at guaranteeing both vote secrecy and verifiability. Advanced deployed systems, such as in Estonia or Switzerland, put a strong emphasis on cast-as-intended: even when a voter uses a corrupt device, they should be able to check that their intended vote is included in the tally. One approach relies on return codes, written on a voting card. This enables cast-as-intended even when the voter uses a single device that may be corrupted. While convenient for voters, this requires to generate the codes in a secure manner. This approach is deployed in Switzerland but the current system requires a single trusted setup authority: an offline component that is assumed to correctly generate the voting data. We propose a novel protocol that allows to distribute the trust during the setup. At the heart of our system lies an asymmetric protocol where several parties create the voting material, while allowing one of these parties to remain offline during the voting phase. Usability constraints are taken into account in our design, both in terms of computational complexity (linear setup and tally) and in terms of user experience (we ask the voter to type a high-entropy string only once). Our protocol is therefore a candidate for the next generation e-voting protocol in Switzerland. We provide an implementation of our protocol, demonstrating its practicability. Moreover, we formally prove vote privacy and verifiability. Our analysis takes into account the presence of short codes that an attacker can guess with non-negligible probability and reveals that making a significant change to the result remains exponentially hard.

Verifiable election systems allow voters to verify that their secret ballots were accurately recorded and counted, while enabling anyone to verify the announced tallies. However, two practical obstacles stand between this guarantee and actual verification. First, public election records can be prohibitively large: for an election with one million ballots, deployed systems may publish more than 100GB of cryp- tographic data. Second, most existing systems protect ballot privacy through encryption, introducing key management—usually one of the most cumbersome and error-prone components of election administration. We present Haechi, a keyless verifiable election scheme for in-person voting, based on cryptographic vector commitments rather than encryption. At the core of Haechi is a new zero-knowledge proof of ballot well-formedness based on Compressed Σ-protocol theory. Our proof scheme proves the validity of an entire ballot using only a logarithmic number of group elements in the number of the ballot options. This allows all of a voter’s selections to be encoded into a single vector commitment. With this approach, Haechi reduces the data required for public verification by more than an order of magnitude compared to prior in-person verifiable election systems. Haechi thereby makes verifications for large-scale election considerably more practical. We also give a post-quantum instantiation of Haechi based on lattice commitments, which preserves the same keyless workflow at the cost of larger election records.

We put forward a generalization of attribute-based signcryption, called anonymous attribute-based signcryption (A$^2$BSC). Beyond message confidentiality and ciphertext unforgeability, A$^2$BSC further requires \textit{ciphertext anonymity}: no information about the signcryptor's attributes or ciphertext-related attributes/policies is leaked, regardless of the decryption outcome. Specifically, we begin by establishing the syntax and security notions for A$^2$BSC within a \textit{unified} framework, which encompasses various variants (key-policy, ciphertext-policy, dual-policy, and a hierarchical dual-policy variant called Special A$^2$BSC). Then, we construct a Special A$^2$BSC scheme for \textit{general policies} (modeled as bounded-depth Boolean circuits) from the succinct learning with errors and the basis-augmented short integer solution assumptions in the standard model, hence achieving post-quantum security. This naturally yields lattice-based instantiations of both ciphertext-policy and dual-policy A$^2$BSC. Beyond its independent interest, we also show the expressiveness and generality of our A$^2$BSC by exploring its application to matchmaking encryption (ME) and arranged matchmaking encryption (AME) proposed by Ateniese et al. (Crypto '19). As a byproduct, we give generic constructions of both ME and AME for \textit{arbitrary policies} against unbounded collusions, and strengthen the CPA-privacy of (A)ME to achieve CCA security. The latter is achieved for free in our construction, as A$^2$BSC natively provides CCA security. Overall, our new solution enhances the diversity of approaches for building the advanced primitive (A)ME.

Xue, Lu, and Au design a logarithmic-size verifiable shuffle for rerandomized ElGamal ciphertexts by combining a KZG permutation argument with a tagged inner-product argument, with cost $(2\log N+11) \mathbb{G}_1 + 8 \mathbb{F}$. We reduce the communication and computation of their construction by observing that the rerandomization vector $\boldsymbol{\rho} \in \mathbb{F}^N$, despite being utilized as a full witness vector, only enters the consistency equations through the scalar $\rho^* =\langle\boldsymbol{a}, \boldsymbol{\rho} \rangle$. We bind this scalar into an existing KZG commitment and replace XLA's two-vector consistency argument with a one-sided folding proof, while preserving the original relation, polynomial degrees, and powers-of-$\tau$ setup. We show that the the naive scalarization is unsound. Applied correctly, the committed scalar indeed permits extraction of the full rerandomization vector. We present two variants: Variant A has proof size $(2\log_2 N+8) \mathbb{G}_1 + 5 \mathbb{F}$, while Variant B adds one group element but removes one interactive round. Under XLA's grouped base-scalar-pair accounting, the prover's exponentiation count decreases from approximately $18N$ to $13N$ (or $14N$, for Variant B), and the verifier's drops from approximately $7N$ to $6N$. Each proof is a constant $240$ B smaller than XLA's; in a $4$-server mix-net election protocol with $N = 2^{10}$ ballots, our Variant A mixing proof costs $5.88$ KiB in total, about $14\%$ smaller than XLA.

Linkable ring signatures (LRS) let a member sign on behalf of a group anonymously while ensuring that any two signatures by the same signer are publicly linkable, a major component in e-voting and cryptocurrencies. Random systems of multivariate quadratic (MQ) equations are one of the most conservative post-quantum assumptions, yet there are only two MQ-based LRS's in the literature: the first is due to Omar, Padhye, and Dey, and the second by Namdeo, Mishra, and Srivastava. Both of these schemes are built from Sakumoto-style identification protocols whose soundness for signatures is well-established, but in the ring setting was never re-examined. We present a sumset attack that lets a signer with no knowledge of an MQ solution universally forge accepting signatures in both protocols. In the same vein, we show that the four-challenge MQ protocol of Monteiro, Goya, and Terada (as transcribed in Namdeo, Mishra, and Srivastava) has soundness error $3/4$ instead of the claimed $1/2$, and this bound is tight. Its natural repair does achieve $1/2$, but is only $3$-special sound, so the two-transcript extraction argument upon which their LRS relies upon does not hold regardless. We then build PyuQuMuQu, a plausibly post-quantum MQ-based LRS from a $5$-pass proof with a $d$-dimensional vector first challenge and an additively split second challenge, whose soundness error is $\frac{1}{2} + \frac{N}{2(q^d-1)}$ for a ring with $N \leq q^d-1$ members. We demonstrate anonymity, linkability, and non-slanderability in the random-oracle model under explicitly stated assumptions involving random MQ maps. PyuQuMuQu attains $355$ kB signature sizes for a ring with $4$ members $128$ bits of security.

An oblivious pseudorandom function (OPRF) is a two-party protocol that enables a client to obtain $F_k(x)$ on an input $x$ without learning the server-held key $k$, while the server learns nothing about $x$. OPRF is a fundamental building block in a wide range of privacy-preserving applications, including password-authenticated key exchange (PAKE), private set intersection (PSI), and distributed function secret sharing. In this work, we present the first concrete, high-throughput, post-quantum secure, verifiable distributed OPRF (dOPRF) tolerating $t < n/2$ malicious servers and a malicious client over replicated secret sharing, extending the recently introduced Gold OPRF of Yang et al. (IEEE S&P 2025) to a threshold setting. We adopt an offline-online paradigm and introduce new protocol designs for both phases. (i) In the offline phase, we develop efficient protocols for batched generation of replicated secret sharing of $\alpha^e$ whose cost is independent of $e$. We present two complementary approaches, each designed for different parameter regimes: the first leverages a degenerate additive encoding under which exponentiation commutes with secret sharing; the second employs $t+1$ designated dealers that prove dual-share consistency via non-interactive zero-knowledge proofs, instantiated using both VOLE-in-the-Head and Ligero, yielding post-quantum security based solely on collision-resistant hashing. (ii) In the online phase, we propose a constant-round protocol that tightly integrates secure multiplication-and-opening with distributed zero-knowledge proof (DZKP) verification, reducing communication in every setting we evaluate and computation in all but the largest batched setting, compared to naively using the standard DZKP framework. (iii) We give a verifiable input protocol that enforces a possibly-malicious client providing well-formed inputs; its well-formedness check is absorbed into a hash exchange the online protocol already performs, and it lowers the client's upload from a full replicated share to one field element per server per input. Our end-to-end benchmarks show that the construction substantially outperforms the state-of-the-art Legendre-PRF dOPRF of Kaluđerović et al. (ESORICS 2025) in terms of communication across all evaluated settings, and remains practical up to $(n,t)=(9,4)$, a regime where prior approaches become bandwidth- or memory-prohibitive.