The choice of a post-quantum cryptography (PQC) algorithm for a concrete deployment is governed by device performance, network conditions, and the practical constraints of TLS stacks, factors that algorithm-centric guidance does not capture. This paper presents a recommendation system that ranks key-encapsulation and signature candidates using benchmarks measured on the target machines and a physically grounded cost model, and confirms as recommended only those candidates that pass end-to-end TLS handshake validation. In experiments on three hardware placements composed of macOS, Linux, and Raspberry Pi machines, the recommended signature algorithm at NIST security level 3 reverses with the server hardware. Handshakes whose server flight exceeds the initial congestion window incur an additional 124 ms on a 160 ms link, far more than the 44 ms attributable to the extra bytes alone. The validation gate further exposes deployment obstacles invisible to microbenchmarks: a standardized signature scheme whose certificates are issued but rejected by the TLS stack, and a wire-format incompatibility between generations of the same crypto provider.

Additive randomized encodings (AREs) reduce the computation of an m-party function f(x1, . . . , xm) to independently encoding each input and adding the resulting encodings in an Abelian group, so that their sum reveals nothing but the output. Robust AREs (RAREs) additionally protect against collusions between the evaluator and some of the parties, guaranteeing that even if some of the input encodings are completely controlled by the adversary, the partial sum of the remaining (honest) input encodings leaks no more than the residual function f(x_H, ·) obtained by fixing the honest inputs x_H. Much of the appeal of RAREs come from the fact that they imply robust non-interactive secure computation in the shuffle model, where parties send messages to the evaluator through anonymous communication channels. Existing constructions of general-purpose RARE either assume ideal obfuscation or rely on structured public parameters generated using secret randomness that must remain hidden. We construct general-purpose RARE with transparent setup. Assuming indistinguishability obfuscation (which is necessary) and LWE, both with subexponential security, we show that every efficient function admits an efficient RARE in the common random string model. We also show how to eliminate public parameters altogether in the honest-majority setting. The main technical observation behind our construction is that non-robust ARE, which exist assuming only one-way functions, can be leveraged to protect from spoofing of honest party encodings.

Threshold and multi-signature schemes enable a group of signers to jointly sign messages. In the pairing-free discrete-logarithm setting, there have been extensive research efforts on two-round threshold and multi-signature schemes. A prominent category is partially non-interactive schemes, where the first round is message-independent and can be preprocessed offline. However, there exist gaps in security properties between partially non-interactive schemes and fully online schemes. While there are fully online schemes that achieve rewinding-free or fully adaptive security based on standard assumptions, existing partially non-interactive schemes require the adversary to act algebraically or rely on non-standard assumptions for these properties. We bridge this gap by proposing a family of new constructions of partially non-interactive threshold and multi-signature schemes. Central to our constructions is a technique that renders HBMS (Bellare and Dai, Asiacrypt 2021) and its variants partially non-interactive. Specifically, we present the following instances: -- The first partially non-interactive two-round multi-signature scheme with a rewinding-free reduction under standard assumptions. This scheme provides a tighter security guarantee against non-algebraic adversaries than all prior partially non-interactive schemes. -- The first partially non-interactive two-round threshold signature scheme achieving fully adaptive security against non-algebraic adversaries under standard assumptions.

Federated learning (FL) enables clients to collaboratively train a global model by sharing gradient updates instead of raw data. However, recent studies show that these shared gradients can be exploited to reconstruct private training data through gradient inversion attacks, posing a serious threat to client privacy. A common defense strategy is gradient obfuscation, which perturbs gradients before transmission; however, it relies on costly hardware components, such as Gaussian samplers and floating-point (FP) multipliers, making it unsuitable for resource-constrained edge devices. Approximate circuits—extensively studied in computer architecture and VLSI for their energy, area, and latency benefits—offer a promising defense. Yet despite its success in machine learning accelerators, it remains underexplored for privacy-preserving FL. This work introduces variational approximate hardware-aware noise addition (VAHANA), a hardware-efficient method that integrates stochastic perturbations directly into the computation using approximate circuits and only $4$ bits of uniform randomness, eliminating the need for Gaussian sampling or FP multiplication. We integrate VAHANA into the open-source RISC-V CV32E40P softcore using a hardware–software co-design approach, implementing custom instruction extensions that accelerate privacy-preserving operations with improved execution efficiency in both time and area. Evaluation on Kintex-$7$ FPGA shows that VAHANA reduces memory footprint by $34$$\%$ and reduces latency by up to $28.1$$\times$, while maintaining resilience against gradient inversion attacks on Medical MNIST, CIFAR-10, and CIFAR-100 datasets.

Areion is a family of AES-based permutations designed for fast hashing and authenticated encryption of short messages. We identify errors in how its security analysis converts active S-box counts into differential and linear probability bounds, and give corrected calculations.

We present ReinsPIRe, a new single-server PIR with higher throughput (smaller computation costs) than all previous schemes that avoid offline communication. The crux of ReinsPIRe is new techniques for leveraging preprocessing in the common reference string (CRS) model to bring down the compute cost significantly. We show that the majority of the server's FHE operations may completely avoid NTT polynomial encodings while maintaining the ability to efficiently multiply polynomials using matrix operations. As a result, most computation may be performed with moduli that are natively supported by modern hardware substantially improving throughput. Furthermore, our techniques result in more compact cryptographic materials reducing memory bandwidth bottlenecks. To obtain ReinsPIRe, we apply our new techniques to the prior InsPIRe construction [Mahdavi et al., S&P 2026] to obtain a higher throughput single-server PIR while maintaining the same low communication costs. ReinsPIRe obtains 5.9 GB/s throughput per server core that is a 2x improvement. We apply ReinsPIRe to improve two different applications. First, we consider the in-storage PIR setting where large databases are stored in external memory (such as SSD) that introduces additional storage I/O costs. In this model, ReinsPIRe obtains 3.3x better throughput than prior works due to its smaller cryptographic material. Secondly, we present a verifiable PIR scheme vReinsPIRe building upon our formulation of server computation as matrix operations. vReinsPIRe provides the smallest online communication cost while using nearly 50x smaller long-term client storage compared to prior works with low online communication.

We introduce MERIDIAN, a 128-bit block cipher designed for resource-constrained environments as a lightweight alternative to AES-128. MERIDIAN retains the AES-128 interface, including a 128-bit block, 128-bit key, and 4×4 byte state, while reusing the standard AES S-box. This enables compatibility with existing AES-128 modes such as ECB, CBC, CFB, OFB, CTR, XTS, CMAC, CCM, and GCM, and allows implementations to reuse established S-box ROMs and GF(28) inverse circuits. The cipher is based on three round operations: Directional Substitution (DS), Meridian Diffusion (MD), and Admittance Mixing (AM), followed by a round constant. Its state is represented over the discrete torus Z4 × Z4. The MD layer combines two orthogonal byte permutations, meridian and parallel, with column mixing to obtain full byte diffusion within three rounds without requiring MDS multiplication. MERIDIAN uses twelve rounds and avoids an expanded key schedule. We present MILP-verified differential and linear bounds, including exact active-S-box counts up to eleven rounds and a sub-additive bound for twelve rounds. We also provide AES-aligned cryptanalysis covering differential, linear, integral, biclique, slide, related-key, invariant-subspace, fault, meet-in-the-middle, and algebraic attacks. A reproducible fifteen-experiment benchmark suite compares MERIDIAN directly with AES-128, including key agility, cold-start latency, energy, masking cost, memory, throughput, and hardware complexity. Empirical results show that MERIDIAN reaches strict avalanche behavior in three rounds, matches AES-128 in entropy and NIST SP 800-22 fitness, reduces unrolled gate count, lowers RAM usage, and improves constrained-device efficiency. MERIDIAN is proposed as a research prototype for further public cryptanalysis. Erratum and resolution: The originally specified round function was not a permutation. Aumasson reported a key-independent DS collision, which we reproduce and which collapses 33.7% of a natural 65 536-state class; we further establish that AM is a singular F2-linear map for 98.10% of round-key bit-planes—an independent break—and that the published one-round differential bound is exceeded 13.37-fold. All are neutralised here. Appendix D specifies MERIDIAN-v2, which evaluates both state-dependent layers in two checkerboard phases so that no layer overwrites the neighbours it reads; DS′ and AM′ are proved bijective for every key, so the cipher is a permutation and decryption inverts encryption on all inputs. Replacing the rotation index (c mod 7) + 1 by c ∧ 7 makes it uniform and XOR compatible, revising the twelve-round bound from 2−288 to 2−240. Corrected code, a reproducer for each defect, and the first published 128-bit test vectors are included. The MILP active-S-box count must be re-verified for v2, which has had no third-party cryptanalysis.

Updatable public-key encryption (UPKE) is a cryptographic primitive that was proposed for secure messaging to provide forward secrecy in public-key settings. It extends standard public-key encryption with a key-update mechanism that lets anyone update a receiver’s public key and issue a corresponding token for updating the secret key. Unlike traditional forward secrecy where all past messages should remain secure after a key leakage, UPKEs guarantee security only as long as at least one honest update has occurred. While classically-secure efficient instantiations of UPKE are known from Diffie-Hellman assumptions, constructing \emph{efficient post-quantum secure} UPKE schemes with \emph{unbounded} updates remains an active research area. For example, prior lattice-based constructions have update tokens of size 1486 KiB. While isogeny group action based constructions offer acceptable sizes, their quantum security is still subject to debate. Designing efficient isogeny-based UPKEs, which are not based on group actions, is still an open problem. In this work, we propose a new isogeny-based UPKE that relies on a dimension-four version of the $\mathsf{FESTA}$ public-key encryption scheme. It allows an unbounded number of updates. Moreover, we provide a formal security proof based on the $\mathsf{CIST}^2$ problem introduced in $\mathsf{FESTA}$ and on the $\mathsf{IND\text{-}KLPT}$ assumption which states that outputs of the $\mathsf{KLPT}$ algorithm are indistinguishable from random isogenies of the same degree. Our UPKE is compact, with public keys, ciphertexts and update tokens of size 0.4 KiB, 2.13 KiB and 2.13 KiB, respectively; hence being the second most compact post-quantum UPKE after isogeny group action based ones. When compared to SILBE, the prior isogeny-based UPKE which did not rely on isogeny group actions, our UPKE is several orders of magnitude more efficient.

Indistinguishability obfuscation ($i\mathcal{O}$) is a powerful cryptographic tool that enables many cryptographic capabilities. Due to its expressivity, constructing $i\mathcal{O}$ is challenging, and existing constructions based on well-founded assumptions all require multiple algebraic assumptions, including an assumption on bilinear groups. If we consider post-quantum constructions, existing candidates all rely on new heuristic assumptions. Due to the challenges in realizing $i\mathcal{O}$, a parallel line of work has aimed to build obfuscation for restricted classes of functionalities, such as point functions, compute-and-compare programs, and most broadly, null circuits (i.e., circuits that always output $\bot$) from weaker assumptions. Thus far, these techniques have all been limited to supporting evasive programs (i.e., programs where it is difficult for an evaluator to find an input where the program's output is not $\bot$). In this work, we introduce a new notion called cutoff-$i\mathcal{O}$. In cutoff-$i\mathcal{O}$, we can obfuscate a circuit $C$ together with a secret cutoff $t$. Then, given an input $(w, i)$, the obfuscated program outputs $C(w, i)$ if $i > t$ and $\bot$ otherwise. Security essentially stipulates that the obfuscated program should hide the cutoff $t$. Cutoff-$i\mathcal{O}$ is an example of obfuscation for a non-evasive function class and implies notions like positional witness encryption, which was previously only known from $i\mathcal{O}$. Our main result is showing how to construct cutoff-$i\mathcal{O}$ from witness encryption and the learning with errors (LWE) assumption. Thus, our approach shows how to lift an obfuscation scheme for an evasive function class (e.g., witness encryption, and more broadly, null-$i\mathcal{O}$) to an obfuscation scheme for a non-evasive function class. By relying on the implication to positional witness encryption, we obtain (from the same set of assumptions) a collusion-resistant broadcast-and-trace scheme with public tracing and ciphertext size $N^{\varepsilon} \cdot \mathsf{poly}(\lambda)$, where $N$ is the number of users in the system and $\varepsilon > 0$ is an arbitrary constant. Previously, such an implication was only known from $i\mathcal{O}$ (or from bilinear groups for the special case where $\varepsilon = 1/2$). Our construction also extends to the registration-based setting where users can sample their own keys and there is no central key-issuing authority. Additionally, we show that cutoff-$i\mathcal{O}$ and LWE can be used to obtain a somewhere-statistically correlation-intractable hash function for efficiently enumerable relations as well as a non-interactive batch argument for $\mathsf{NP}$ (BARG) with somewhere-statistical soundness.

Multi-party computation (MPC) enables a set of mutually $n$ distrusting parties to compute any function on their private inputs. Mainly, MPC facilitates agreement on the function’s output while preserving the secrecy of honest inputs, even against a subset of $t$ parties controlled by an adversary. With applications spanning from anonymous broadcast to private auctions, MPC is considered a cornerstone of distributed cryptography, and significant research efforts have been aimed at making MPC practical in the last decade. However, most libraries either make strong assumptions like the network being bounded synchronous, or incur high computation overhead from the extensive use of expensive public-key operations that prevent them from scaling beyond a few dozen parties. This work presents Velox, an asynchronous MPC protocol that offers fairness against an optimal adversary corrupting up to $t<\frac{n}{3}$ parties. Velox significantly enhances practicality by leveraging lightweight cryptographic primitives - such as symmetric-key encryption and hash functions - which are 2-3 orders of magnitude faster than public-key operations, resulting in substantial computational efficiency. Moreover, Velox is highly communication-efficient, with linear amortized communication relative to circuit size and only $\mathcal{O}(n^3)$ field elements of additive overhead. Concretely, Velox requires just $9.33$ field elements per party per multiplication gate, more than $10\times$ reduction compared to the state of the art. Moreover, Velox also offers Post-Quantum Security as lightweight cryptographic primitives retain their security against a quantum adversary. We implement Velox comprehensively, covering both offline and online phases, and evaluate its performance on a geographically distributed testbed through a real-world application: anonymous broadcast. Our implementation securely shuffles a batch of $k=256$ messages in $4$ seconds with $n=16$ parties and $18$ seconds with $n=64$ parties, a $36\times$ and $28.6\times$ reduction in latency compared to the prior best work. At scale with $n=112$ parties, Velox is able to shuffle the same batch of messages in under $50$ seconds from end to end, illustrating its effectiveness and scalability. Overall, our work removes significant barriers faced by prior asynchronous MPC solutions, making asynchronous MPC practical and efficient for large-scale deployments involving $100$s of parties.

We explore the setting of asynchronous multi-party computation (AMPC) with optimal resilience $n=3t+1$, and develop an efficient protocol that optimizes both communication and computation. The recent work by Goyal, Liu-Zhang, and Song [Crypto' 24] was the first to achieve AMPC with amortized linear communication cost without using computationally heavy public-key cryptography. However, its $\mathcal{O}(n^{14})$ additive communication overhead renders it impractical for most real-world applications. It is possible to reduce the communication overhead significantly by leveraging cryptographic tools such as %random oracle hash, homomorphic commitments, public-key cryptography, or zero-knowledge proofs; however, the corresponding AMPC protocols introduce computation overhead of $\Omega(nC)$ public-key cryptographic operations that become bottleneck as $n$ grows. Overall, achieving AMPC with linear communication complexity, low additive communication overhead, and low computation overhead remains an open challenge. In this work, we resolve this efficiency challenge by utilizing the random oracle model. By relying solely on computationally efficient primitives such as random oracle hash and symmetric-key cryptography, our protocol is not only efficient in terms of computation and communication overhead but also post-quantum secure. For a circuit with $C$ multiplication gates, our protocol achieves $\mathcal{O}(Cn)$ communication per multiplication gate with an additive overhead of $\mathcal{O}(n^4)$ communication. In terms of computation, our protocol only introduces an additive overhead of $\mathcal{O}(n^5)$ hash computations independent of the circuit size.

We study the communication complexity of SPDZ-type MPC protocols in the dishonest majority setting with maximum corruption, where $t=n-1$ out of $n$ parties can be corrupted. In the semi-honest setting, the state-of-the-art SPDZ protocol achieves an amortized communication cost of $4n$ field elements per multiplication gate, assuming a pseudorandom correlation generator (PCG) that prepares random Beaver triples silently in the offline phase. However, achieving security against malicious adversaries typically incurs a substantial overhead. Existing works either blow up the communication by incurring $10n$ field elements per gate or an additional overhead of $O(\sqrt{|C|}\cdot n^3)$, or additionally require an additively homomorphic encryption scheme. In this work, we construct a maliciously secure SPDZ-type protocol with the same amortized communication complexity as the semi-honest variant, i.e., $4n$ field elements per multiplication gate, assuming a PCG for \emph{tensor-product} correlations. We note that the tensor-product correlations come free in communication as by-products from almost all existing constructions of PCGs for random Beaver triples, although additional local computation is required. These by-products allow us to construct an efficient preprocessing phase and a recursive check protocol, which enables an online evaluation of the circuit without authenticating all the wire values. The recursive check requires sublinear communication in $|C|$, though it incurs an $O(k)$ overhead on the online computational cost compared to the semi-honest baseline.

Zero-Knowledge (ZK) proof systems have become a cornerstone of privacy-preserving technologies and blockchain scalability. However, traditional hash functions are often inefficient within ZK protocols due to their high constraint complexity in arithmetic circuits. While various ZK-friendly hash functions have been proposed to address this bottleneck, their diverse algebraic structures and varying security margins make it difficult for practitioners to select the optimal primitive. We conduct a systematic survey of ZK-friendly hash functions, covering both algorithmic design paradigms and modes of operation. We consolidate the relevant algebraic cryptanalysis techniques and review the third-party cryptanalysis of each design. For parameter sets broken by the best known attacks, we estimate the minimum number of rounds needed to withstand them - not as new recommendations, but to bring all constructions to a comparable level. On this basis, we analyze each construction across different arithmetization styles (R1CS, AIR, PLONK), both theoretically, by deriving the underlying constraint or gate counts, and empirically, through extensive benchmarks. This paper comes with a fully open-source implementation suite comprising a SageMath/Python reference framework, native Rust implementations, in-circuit implementations, and a reusable TikZ figure library.

Fuzzy extractors derive stable cryptographic keys from noisy biometric measurements (Dodis et al., EUROCRYPT 2004). Despite nearly three decades of research, existing fuzzy extractor constructions do not provide strong security for the biometric modalities deployed on modern devices, particularly fingerprints and facial recognition. Recent attacks highlight the gap between known analysis of theoretical constructions and the security levels required for practical deployment (Zhu and Wang, PoPETS 2025). We close this gap. Compared with sample-then-lock baselines (Shukla et al., CCS 2025), our construction improves security for the fingerprint and face biometrics from $44$ to $72$ bits and from $59$ to $84$ bits, respectively. For iris biometric, we improve security from $105$ to $111$ bits. Our construction, sample-then-correct, combines two existing approaches: digital lockers and secure sketches based on error-correcting codes. We embed secure sketches within a collection of digital lockers that an honest party can open with good probability. The construction naturally achieves the benefits of both approaches. We prove security in an extension of the generic group model that measures natural attacks the adversary can conduct. These gains are achieved while maintaining authentication accuracy comparable to prior work, with true accept rates near $90\%$ when multiple readings are available and approximately $60\%$ from a single reading. Our implementation authenticates in under one second on a single CPU thread.

Continuous monitoring in the Internet of Medical Things (IoMT) creates an attribution problem: an abnormal sample may rep- resent a genuine physiological event, an accidental sensor fault, or a deliberate cyberattack. Conventional anomaly detectors estimate whether data are unusual, but cannot establish who produced a sample, which software processed it, or whether it was replayed. This paper proposes Verifiable Medical Sensor Provenance (VMSP), a lightweight chain of authenticated records spanning sensing, gateway processing, and clinical ingestion. We implemented Ascon-AEAD128 and Ascon-Hash256 record pro- tection, converted verification outcomes into machine-learning features, and evaluated 12,000 generated windows. Macro-F1 increased from 0.644 for signal-only classification and 0.807 with device health to 0.976 with Ascon-derived provenance; attack recall increased from 0.398 to 1.000. For a 64-byte payload, the prototype added 68 bytes and measured median encryption and verification times of 0.282 and 0.297 ms on an x86-64 host. These measurements establish a reproducible software proof of concept, not clinical or embedded-device performance.

In this paper, we construct threshold signatures (TS) to achieve adaptive TS-UF-1 security and identifiable abort. Our TS construction has two rounds. We prove its adaptive TS-UF-1 security in the random oracle model (ROM) under the MDDH (covering DDH) assumption in pairing-free groups. To the best of our knowledge, there are only two TS schemes, namely GLRS26 (Gerhart et al., Eurocrypt 2026) and Dazzle (Chen, PKC 2025), enjoying two rounds, identifiable abort and adaptive security from DDH in pairing-free groups in the ROM. However, both schemes only achieve adaptive TS-UF-0 security. Therefore, our construction yields the first TS scheme enjoying adaptive TS-UF-1 security and identifiable abort, free of pairing.

Frobenius-UOV (F-UOV) is a multivariate signature scheme by Macario-Rat over $\mathbb{F}_{p^e}$ whose public equations are quadratic over $\mathbb{F}_p$ but have high degree over $\mathbb{F}_{p^e}$. A message can be forged by solving a six-term univariate equation in $\mathbb{F}_{p^e}$, which can be reduced to a univariate equation containing three monomials with exponents $p^{a_k}+p^{b_k}$ for $k=0,1,2$ and a constant term, where the constants $a_k$ and $b_k$ are fixed by the specification. We show that the choice of constants $a_k,b_k$ of F-UOV allows one to solve the univariate equation efficiently without knowledge of the secret key, leading to a forgery attack. The attack introduces a variable representing a Frobenius power of $x$, derives two low-degree bivariate equations, and solves them using a so-called linearized resultant. Under heuristics assumptions on the success probabilities, the average complexity is $\tilde{\mathcal{O}}(ep^6)$ field operations. For the $128$-, $192$-, and $256$-bit security instances, our estimates are approximately $2^{45}$, $2^{52}$, and $2^{53}$ field operations, respectively. This attack may be mitigated by changing the choice of the exponents $a_k$ and $b_k$.

Non-malleability for non-interactive zero-knowledge proofs requires that, given a proof for a statement, it is infeasible to derive a valid proof for a related statement without knowing a corresponding witness. We introduce a modular framework for analyzing non-malleable reductions of knowledge (RoKs). A reduction of knowledge transforms the task of proving knowledge for a source relation into proving knowledge for a target relation, often simpler or more structured. RoKs are an extremely useful tools for compositions. We identify different settings in which the composition of two RoKs, and in particular two non-interactive RoKs obtained via the Fiat-Shamir transform, preserves simulation extractability, and thus non-malleability. Our framework isolates simple and concrete properties required from each component, including novel forms of zero knowledge and new security notions that are easier to verify than full simulation extractability. This yields a systematic toolbox for establishing non malleability in modular proof systems. Finally, we illustrate the power of our approach by analyzing LaBRADOR (Beullens and Seiler, CRYPTO’23), a lattice based proof system for R1CS. We provide the first analysis of its simulation extractability and, since LaBRADOR is not zero knowledge, we design a zero knowledge variant that preserves its practical efficiency and sublinear proof size. Our results show that non-malleability for advanced proof systems can be achieved modularly, significantly simplifying the security analysis.

Sum-check and Fast Fourier Transforms (FFTs) dominate the computational cost of modern zero-knowledge proving systems, such as HyperPlonk (Eurocrypt 2023) and FRI-based schemes like DeepFold (USENIX Security 2025). Despite numerous optimizations, existing efforts remain fragmented across algorithmic, protocol, and implementation layers, leaving significant CPU performance potential untapped. We present MamaBearZKP, a co-designed framework that bridges these layers to enable high-throughput ZK proving on modern CPUs. At its core, MamaBearZKP leverages MamaBear, a 49-bit prime field ($p = 2^{49} - 2^{34} + 1$), and introduces a systematic vectorization framework specifically tailored for the AVX-512IFMA execution model. By treating field arithmetic, protocol structure, and low-level hardware primitives as a unified optimization target, MamaBearZKP achieves unprecedented efficiency. We instantiate our framework in a HyperPlonk-DeepFold prover and obtain single-thread speedups of up to $42\times$, $33\times$, $15\times$, $21\times$, and $21\times$ for ZeroCheck, ProductCheck, DeepFold Commit, DeepFold Open, and end-to-end proof generation, respectively, compared to a Goldilocks-based baseline on the same platform. With 8-thread execution, the corresponding speedups increase to as much as $64\times$, $47\times$, $81\times$, $45\times$, and $45\times$. Across our end-to-end evaluations, MamaBearZKP also achieves up to $18\times$ single-thread speedup over Plonky3, which already uses an AVX-512 BabyBear backend. Rather than resulting from isolated improvements, these gains arise from a synergistic cascading effect: the 49-bit field’s headroom enables efficient lazy reduction, which paves the way for high-performance fused fold-and-evaluate kernels. The efficiency of these kernels facilitates a unified stay-packed dataflow throughout the HyperPlonk and DeepFold stacks; it is precisely this end-to-end dataflow that materializes the hardware throughput of AVX-512IFMA into realized performance gains.

The terms Signcryption, Split KEM, and Authenticated Key-Encapsulation Mechanism (AKEM) are often used synonymously to capture the amalgamation of a KEM and a Digital Signature Scheme in a single primitive. This means that a sender Alice can encapsulate a symmetric secret to the public key of receiver Bob, and Bob can use Alice's public key to verify that Alice was indeed the sender. Some constructions of AKEM additionally use symmetric pre-shared key material between Alice and Bob to redundantly protect the confidentiality and authenticity of the encapsulated symmetric secret. So far, only special variants of such redundancy have been studied in the literature. Furthermore, beyond confidentiality and authenticity, anonymity of senders and receivers is a desirable property of AKEM that has received little attention yet. In this work, we begin with formally defining strong compatible notions of confidentiality, authenticity, and anonymity for AKEM. In these notions, Alice and Bob can redundantly protect the encapsulated secret using all possible combinations of asymmetric sender key, asymmetric receiver key, and symmetric pre-shared key material. For every such combination, we develop an efficient construction from standard primitives. Our consideration of anonymity and the use of symmetric pre-shared key material provokes the study of a tagging and detection mechanism: When Bob receives a ciphertext that is anonymously protected with a pre-shared key, he needs to detect which out of multiple candidate pre-shared keys to use for decryption. We prove that this detection cannot be substantially more efficient than preforming trial decryptions, even when permitting pre-computation. This result is of independent interest and may have broader applications as we prove its equivalence to 1-out-of-n multi-key decryption, resp. verification, in Symmetric Encryption and Message Authentication Codes.

Quantum computers threaten the classical public-key primitives (RSA, ECDSA) used by most blockchains today; NIST has therefore standardized lattice-based signatures (ML-DSA, FIPS 204; and FN-DSA, a FALCON-based scheme being finalized as FIPS 206) and mandated a transition of the underlying cryptosystems. This report describes a reproducible, teaching-level study of the design space of lightweight lattice-based authentication and signatures for blockchain-style transactions. We study two constructions: (i) Track A, a symmetric LWE authentication tag whose matrix is derived per transaction from SHA-256 ("one transaction, one matrix"), and (ii) Track B, a ringless public-key lattice signature in the Lyubashevsky Fiat-Shamir-with-Aborts style. Our contribution is methodological rather than a claim of a new provably secure scheme: we (a) propose a parameter instantiation workflow that combines a root-Hermite/core-SVP estimator with scaled-down LLL embedding attacks and validate the two layers against each other; (b) study a message-derived matrix variant that removes the need to transmit a matrix seed; and (c) release an open, fully reproducible benchmark (E1-E4) that follows recent methodological critiques of ML-DSA evaluation by reporting full latency distributions and rejection-sampling worst cases instead of means only. All code, data, seeds, and figures are public. We do not claim formal security proofs; formal analysis and module/ring-structured instantiations are left to future work.

Using a multidimensional lattice block code complicates decryption-failure analysis in two distinct ways. A norm or BDD certificate need not equal the implemented message-failure event, and structured polynomial products can make the residual coordinates dependent. We record every estimate by its decoder event, residual law, tail engine, and ciphertext/key aggregation. This event-aligned framework yields finite directional bounds for arbitrary residual laws and a finite Gaussian reference calculation for the gap between a radial certificate and a polyhedral decoding cell. ML-KEM is included only as a scalar consistency check; the main analysis concerns non-scalar lattice-coded block decoders. For BW-KEM, whose deployed algorithm is a BDD for the 32-dimensional Barnes--Wall lattice $BW_{32}$, we keep the published radius event fixed. We extend its Gaussian product limit to bounded centered coefficient laws and prove joint convergence for every fixed decoder block. A noncentral chi-squared mixture then retains the terminal discrete noise exactly under the Gaussian product reference. The original Chernoff calculation has the same large-deviation exponent but may lose a polynomial prefactor. Across five measurable diagnostic points, the mixture exponent and the empirical exponent of the exact any-block BDD event differ by at most 1.116 bits; the original reference-law log probabilities lie 3.131--3.585 bits above the simulated values. For prime-degree CTRU and DTRU, we derive the adjacent coefficient covariance, prove a joint normal limit for nonadjacent coordinates of bounded-coefficient products, and introduce a parity-separated public block assignment. It removes the identified adjacent covariance from every decoder block in the second-order product model. Under the Gaussian BDD reference, the single CTRU-Prime row decreases by 137.116 bits; the single DTRU-Prime row gives a conditional, scalar-anchored decrease of 73.299 bits. Paired complete-map experiments separately quantify the certificate-to-decoder gap for CTRU and DTRU. Each numerical claim is labeled as a rigorous bound, a reference-law calculation, or a diagnostic measurement; none of the Prime reference values is presented as an exact DFR.

In this work, we address the critical yet understudied question of the security of the most widely deployed pseudorandom number generators (PRNGs) in AI applications. We show that these generators are vulnerable to practical and low-cost attacks by introducing both manual and automated cryptanalysis techniques. For this we partially, and to the best of our knowledge for the first time, take advantage of AlphaEvolve, a novel evolutionary coding agent guided by Large Language Models, to automate the discovery of complex cryptographic distinguishers. Finally, we present a cryptographically secure and well-understood alternative, which has a negligible effect on the overall AI/ML workloads. More generally, we recommend the use of cryptographically strong PRNGs in all contexts where randomness is required, as past experience has repeatedly shown that security requirements may arise unexpectedly even in applications that appear uncritical at first.

Bitslice implementations are widely adopted in lightweight cryptography (LWC) due to their efficiency and inherent resilience to side-channel attacks. However, this paper reveals that their decomposition of the S-box exposes critical vulnerabilities to the operation skip fault model. Unlike data corruption faults suffering from high-entropy diffusion, we identify that skipping bitwise operations induces strongly restricted differential patterns. To exploit this characteristic, we propose the Skip-induced Difference Distribution Table (SDDT), a framework mapping operation omissions to output differences. We validate this approach on the block cipher PIPO through practical experiments, successfully recovering the master key from deeper rounds with fewer faults than previously possible. Our findings underscore the fragility of bitslice designs against precise operation skip faults.

Iteration of a cryptographic hash function is a common practice in many applications, typically used to enhance resistance against various attacks (e.g., to slow down dictionary attacks in password hashing). While the security properties of (non-iterated) cryptographic hash functions are well studied and understood by the cryptographic community, their iterated counterparts have received comparatively little attention. Even in idealized models such as the random oracle model, preimage and collision resistance of an iterated hash function do not seem to be fully characterized. The security of an iterated random function has mainly been studied through its indistinguishability from the (non-iterated) random function. Bhaumik et al. (ASIACRYPT 2017) analyse the collision resistance of an iterated random function, but in a model where the adversary has oracle access to the iterated random function (and not the random function itself). Kogan et al. (CCS 2017) then study the preimage resistance of an iterated random function in the random oracle model, but focus only on finding preimages for the last iteration step. In this paper we complete the picture by providing attacks and matching upper bounds for preimage and collision resistance of an iterated random function \(H^k\), where \(H \colon [n] \to [n]\) is modelled as a random oracle. While collision resistance is essentially unaffected by iterations, we prove that the situation is very different in the case of preimage resistance. Specifically, we present a concrete attack on preimage resistance of \(H^k\) with advantage \(\Omega(\frac{qk}{n})\) assuming \(q = \Omega(k)\), where \(q\) denotes the number of \(H\)-oracle queries made by the adversary. We complement our attack with an upper bound \(\mathcal{O}(\frac{qk+k^2}{n})\), which is tight in the \(q = \Omega(k)\) regime. Finally, we show that iteration weakens preimage resistance only for random functions: when \(H\) is a permutation, preimage resistance remains essentially unaffected.

Succinct Non-Interactive Half-Chosen VOLE allows a sender with a vector $\boldsymbol x$ of length $n$ and a receiver with a scalar $y$ to establish a pair of additive shares of $\boldsymbol x \cdot y$, by simultaneous exchange of succinct messages. Recent works construct NIHC-VOLE with $O(n^{2/3} \lambda)$ communication from various assumptions (Abram, Roy and Scholl, Eurocrypt 24) and poly-logarithmic communication from LWE (Abram, Malavolta and Roy, STOC 25). We explore how bilinear pairings can improve group-based NIHC-VOLE schemes. • In the public setup setting, our scheme has online communication of $O(\sqrt{n \log n})$ group elements. The scheme relies on a new BDDH-like assumption. • In the designated receiver setting, our scheme has online communication of only 3 group elements and reusable offline communication of $O(n)$ group elements. The scheme relies on the bilinear power DDH assumption.

In this paper, we study the trust assumptions underlying key generation in functional encryption (FE) schemes, as well as the information leakage that can arise from the use of functional decryption keys. FE schemes typically rely on a trusted key curator who holds the master secret key and derives functional decryption keys. This requirement makes the curator a central point of trust and a particularly sensitive target for compromise. We show how homomorphic encryption (HE) can be used to mitigate this problem by allowing FE key-derivation algorithms to be evaluated homomorphically. Building on prior work on function-blind key derivation [CHL20], we extend this approach to a three-party deployment in which the key curator does not hold the FE master secret key in the clear. The resulting construction preserves function blindness while protecting the master secret key from the curator, thereby reducing the trust assumptions associated with conventional FE key management. Additionally, to test the applicability of our approach, we made a proof-of-concept implementation and ran a series of benchmarks. Finally, as a way to support open science and reproducible research, we make our code publicly available.

Ring signatures provide signer anonymity for ad hoc sets of public keys. Generic Abe-Ohkubo-Suzuki (AOS) transforms are well understood for plain Fiat--Shamir and hash-and-sign signatures, but not for their rejection-sampling variants: Fiat--Shamir with aborts (FSwA) and hash-and-sign with retry (HSwR). We formalize AOS ring transforms for FSwA and HSwR and analyze their security in the quantum random-oracle model. For unforgeability, we reduce security under adaptive ring-signing queries to security without signing queries using essentially the same assumptions as in security proofs for the corresponding ordinary signatures; handling adaptive corruption additionally requires the simulation property to remain valid after key exposure. Strong unforgeability additionally requires response uniqueness and special soundness for FSwA, or second-preimage resistance and non-invertibility for HSwR. The residual no-signing-query requirement admits generic reductions, but with loss exponential in the number of honest keys. Finally, an ML-DSA case study shows that augmented public keys achieve the required key-exposure simulation while identifying its limitations; we also identify conditions for candidate HSwR instantiations.

The hardness of the Learning Parity with Noise (LPN) problem is a foundational assumption in cryptography, forming the basis of constructions ranging from symmetric-key primitives to public-key encryption and beyond. A central open question is whether the average-case hardness of LPN can be based on worst-case complexity assumptions, as has been achieved for the analogous Learning With Errors (LWE) problem. Existing worst-case-to-average-case reductions for LPN [BLVW19, YZ21] rely on statistical smoothing of linear codes, which inherently limits the resulting average-case hardness to noise rates as large as $1/2 - 1/\mathrm{poly}(n)$, which is insufficient for public-key applications. We explore a new approach towards obtaining such reductions: rather than requiring that random sparse combinations of the rows of the generator matrix of a code be statistically close to uniform, we only require that they be computationally indistinguishable from uniform. This leads to a clean win-win structure: we show that any efficient LPN solver can be transformed into a pair of efficient algorithms $(S, D)$ such that for every matrix $A$ of appropriate dimensions over $\mathbb{F}_2$, either $S$ decodes the code generated by $A$ from random noise, or $D$ distinguishes random noisy codewords of the dual of this code from uniform. By instantiating this reduction with appropriate parameters, we obtain the average-case hardness of LPN with inverse-polynomial noise rate $n^{-\alpha}$ for any constant $\alpha < 1$, assuming the worst-case simultaneous hardness of decoding a code from random noise and distinguishing random noisy codewords of its dual from uniform. In particular, setting $\alpha = 1/2$, our reduction yields LPN hardness in the parameter regime required for Alekhnovich's construction of public-key encryption [Ale03], a regime that was previously inaccessible via worst-case reductions.

Privacy-preserving Boolean satisfiability (SAT) solvers allow multiple distrustful parties to solve the conjunction of their private formulas without revealing their inputs. Prior work on privacy-preserving SAT solvers, i.e., ppSAT (USENIX Security 2022), fails to solve formulas of practical size and complexity because it supports only the most basic SAT-solving algorithm. We bring privacy-preserving SAT solving closer to practicality by introducing ppCDCL. Through carefully orchestrated oblivious data structures and solver architecture, our new solver enables conflict-driven clause learning (CDCL) and efficient propagation, the two most important features of modern plaintext SAT solvers. Evaluation results show that ppCDCL outperforms ppSAT in both capability and efficiency. It solves significantly more instances: 98% vs. 65% on the Haplotype benchmarks and 84% vs. 28% on the larger, more diverse SATLIB benchmarks. Furthermore, it solves 36% of SATLIB instances within 1,000 seconds compared to only 4% for ppSAT.

Fully homomorphic encryption (FHE) enables computation directly on encrypted data, but encrypting data under FHE imposes client-side computational costs and produces large ciphertexts. Transciphering addresses these costs by allowing the client to upload symmetric ciphertexts while the server homomorphically evaluates symmetric decryption to obtain FHE ciphertexts. However, transciphering itself can become a performance bottleneck, and a general framework for efficiently supporting structurally diverse symmetric ciphers is still lacking. To fill this gap, we present Coral, a general and efficient transciphering framework built on TFHE. Rather than mapping an entire decryption circuit to a uniform evaluation strategy, Coral decomposes it at operation boundaries and provides optimized procedures for four recurring computational modules: linear Boolean operations, sparse low-degree Boolean functions, modular additions, and small-domain substitutions. These procedures share compatible ciphertext interfaces, allowing them to be reused and composed across different ciphers. Together, these optimized procedures enable Coral to achieve high efficiency without sacrificing generality. We instantiate Coral for Trivium, AES, ChaCha20, and ZUC, covering both individual and combined nonlinear structures. Compared with the corresponding baselines, our implementations achieve speedups of up to $4.055\times$ for ZUC under single-threaded execution and up to $5.517\times$ for ChaCha20 under fully parallel execution.

One of the strengths of our recently proposed Walking Cat Architecture for a trapped-ion quantum computer is that it is straightforward to extend and optimize for a specific application. As a proof-of-concept, here we present such optimizations for solving the $256$-bit elliptic curve discrete logarithm problem (ECDLP) on $\mathtt{secp256k1}$, which is the elliptic curve used by blockchain technologies such as Bitcoin, using Shor's algorithm. We optimize the circuits from Schrottenloher's recent work and arrive at a logical quantum circuit for solving the ECDLP using about $1450$ qubits and $40\cdot 10^6$ Toffoli gates, with a rigorous lower bound on the logical-level success probability that holds with confidence at least $1-2^{-128}$, as well as a heuristic estimate thereof. Using our compilation toolchain in combination with manual optimization of the logical layout and integrated routing, we produce estimates for the logical measurement depth and the required number of physical qubits by compiling all components to measurement schedules that obey the architectural constraints. A key ingredient is a fast CCZ magic-state factory and a depth-one CCZ state injection, reducing the execution time of CCZ gates by a factor of $31$. We increase the logical-measurement parallelism using non-overlapping cat-based measurements in parallel, and we leverage the recently proposed logical CliNR protocol to speed up Clifford operations. To reduce the qubit overhead, we introduce a more efficient loss correction protocol, design a layout that allows us to recycle the CliNR ancilla qubits, and provision reusable cat-state resources according to the circuit's peak measurement parallelism. All results and optimizations combined, we conclude that a trapped-ion quantum computer based on our architecture would be able to solve the ECDLP on $\mathtt{secp256k1}$ in approximately $25.7$ days using $19{,}397$ physical qubits with an estimated success probability of $63\%$.

While the round function of the AEGIS authenticated encryption algorithms is highly parallelizable, their mode of operation is not. We introduce two new modes to overcome that limitation: AEGIS-128X and AEGIS-256X, that require minimal changes to existing implementations and retain the security properties of AEGIS-128L and AEGIS-256.

In recent years, threshold encryption has gained a lot of interest, particularly due to its potential use in encrypted mempools in blockchains. Standard security models allow the adversary to corrupt parties either statically (i.e., fixed at the onset of the game) or adaptively (i.e., via an oracle one-by-one, depending on keys and ciphertexts). In this work, we observe that neither of these models captures the case in which a party decides to become corrupted based on secret information. For instance, in an encrypted mempool application with randomly rotating committees, an adversary may set up a smart contract that pays parties who reveal their decryption share, and parties decide whether to claim it based on, say, whether they are on the next committee. Such corruptions are not fixed in advance, but they are also not chosen solely by an external adversary based on public information. We initiate the formal study of such internally motivated corruptions and partial decryptions. We introduce a security framework in which each party's corruption behavior may depend on its local secret state. That is, on a corruption, the adversary can submit a motivation function and all parties for which this motivation function outputs $1$ (on their secret information) are corrupted. A similar internally motivated behavior is allowed for releasing partial decryptions. We then study threshold encryption under this stronger notion of security. In particular, we show: - Negative Results: We show that for certain classes of motivation functions and number of queries, no threshold encryption scheme can satisfy security. We also show a concrete practical attack with internally motivated corruptions against a scheme that has been proven secure with standard corruptions. - Positive Results: We give two efficient classes of constructions from the (Bilinear) Diffie-Hellman assumptions in the random oracle model. The first is secure when partial decryptions on the challenge ciphertext are internally motivated. The second additionally allows internally motivated corruptions.

Inspired by the no-cloning theorem in quantum theory, a variety of quantum cryptographic primitives with unclonable functionalities, such as secure key leasing and copy protection, have been proposed and attracted significant attention. However, trapdoor functions (TDFs), fundamental primitives in public-key cryptography, have not been extensively studied in these areas. In this work, we initiate a study of TDFs in both secure key leasing and copy protection settings. We first introduce the definition of TDFs with secure key leasing (TDF-SKL), which enables leasing and deleting of quantum trapdoors. We formalize TDF-SKL both with and without domain sampler, and give a construction of TDF-SKL without domain sampler based on the LWE assumption and a construction of TDF-SKL with domain sampler based on any standard PKE schemes combined with hinting pseudorandom generators [Koppula and Waters, CRYPTO 2019]. Next, we define TDFs with copy protection (TDF-CP), where the inversion functionality is copy protected by a quantum trapdoor. We establish a construction of TDF-CP assuming indistinguishability obfuscation and the LWE assumption, following a modular framework of copy protection proposed by Ananth and Behera [CRYPTO 2024]. We also present applications of TDF-SKL and TDF-CP. Existing constructions of public-key encryption with secure key leasing (PKE-SKL) and single-decryptor encryption (SDE) suffer from a critical vulnerability: quantum decryption keys may be destroyed after decrypting maliciously chosen ciphertexts. We construct PKE-SKL schemes and SDE schemes with robust quantum decryption keys that remain reusable after decrypting arbitrary ciphertexts from TDF-SKL and TDF-CP, respectively.

Ratchets are critical cryptographic protocols deployed in many secure messaging applications such as Signal Messenger, WhatsApp, and Apple's iMessage PQ3, which aim for strong guarantees such as Post-Compromise Security (PCS). Computer-aided cryptography can be used to increase confidence in security protocols but, until now, has been unable to prove PCS in the computational model for a ratchet due to the complexity of the cryptographic arguments involved. Existing mechanized PCS analyses have been limited to the symbolic model. We tackle this problem with Squirrel, which is well-suited to study such stateful protocols. The task is still a challenge, due to the intricate reasoning required, and because Sqirrel's indirect modeling of secrecy has difficulties in scaling to such a complex proof. To address these issues, we develop a novel logical framework in Squirrel that allows to reason on secrecy as a first-class notion, and we validate our approach by verifying the PCS of an asymmetric ratchet. This provides the first mechanized computational proof of PCS to date for a ratchet, and possibly for any protocol.

Email encryption based on S/MIME and, to a lesser extent, PGP is widely deployed in enterprise environments, often through centralised server-side encryption gateways that decrypt and sign messages on behalf of end users. Gateways can also be run locally to implement encryption for email clients that do not natively support it. We systematically analyse the security of four such products: SEPPmail, CipherMail, Cisco Email Security Appliance, and the Proton Mail Bridge. We identify 29 attacks which allow an adversary to fully decrypt messages and confuse users on the authenticity of received emails. To this end, we exploit the legacy cryptographic primitives in S/MIME and the backwards compatibility features for PGP, adapt well-known attacks such as EFAIL (Poddebniak et al., USENIX Security 2018) to this setting, and expose novel attack vectors such as the error signals produced by email infrastructure. Our findings show that moving cryptographic operations to gateways strips important signals that email clients rely on. This re-enables attacks like EFAIL, which were largely considered resolved, and introduces exploitable features in how the security status of emails is communicated. Such systems also expose sensitive decrypted plaintext to intermediate email infrastructure, which was not designed to handle it. We conclude that delegating cryptographic operations to a gateway undermines the end-to-end security model that PGP and S/MIME were designed to provide.

Multi-party matrix invertibility testing over finite fields of small order or characteristic is a pivotal operation for thresholdizing multivariate quadratic~(MQ) signature schemes. However, achieving perfect privacy in a constant number of rounds remains a challenge: existing solutions either suffer from information leakage, failing to provide perfect privacy, or require high computational and communication overhead, in particular, when $p\leq n$, where $p$ and $n$ denote the characteristic of the underlying field and the matrix size, respectively. To address this limitation, we propose two protocols for multi-party testing of matrix invertibility. The first protocol extends the Cramer-Damg{\aa}rd protocol to fields of small order by employing the field lifting technique. The second protocol is based on multi-party computation of the Samuelson-Berkowitz algorithm, specifically designed for fields of small characteristic. Both protocols are formalized in the arithmetic black-box~(ABB) model with Shamir's secret sharing scheme. We show that both protocols achieve perfect privacy while allowing for a tradeoff between input-independent offline rounds and input-dependent online rounds, where the input corresponds to the shared matrices. Specifically, the first protocol runs in $7$ offline rounds with communication complexity $O(Nn^4)$ and in $3$ online rounds with communication complexity $O(n^4)$, and the second protocol runs in $3$ offline rounds with communication complexity $O(n^4)$ and in $9$ online rounds with communication complexity $O(n^4)$, where $n$ is the matrix size and $N$ is the number of parties.

Given two ordered families of square matrices over a finite field, we seek an ambient conjugation and an invertible mixing of the family that carry one input to the other. The matrices need not be linearly independent. We give deterministic partial algorithms in an explicit finite-field model: source-side recognition certifies completeness against every target, and every returned transporter is verified. For a matrix space with nondegenerate trace pairing, two successive orthogonal projections produce an intrinsic matrix pair. A characteristic-wise nonzero polynomial certificate gives source density at least $1-(6n^2-4)s/q-2/q^3$, where $n\geq 3$ is the matrix size, $2\leq m\leq n^2-2$ is the number of slices, and $s=\min\{m,n^2-m\}$. Thus the density tends to one whenever $n^2s=o(q)$. A complementary one-dimensional-hull construction, together with low-dimensional and endpoint solvers, gives a recognized source family of iid-uniform mass greater than $9/(1216q)$ for every prime power $q$ and all positive $n,m$. Both algorithms have bit complexity polynomial in $n,m,\log q$. An image-and-kernel lift recovers the declared coefficient action, including dependent presentations. We separate the exceptional odd-characteristic two-by-two case and the arithmetic limitations of higher-moment constructions from the universal partial guarantee.

Private Information Retrieval (PIR) enables a client to query a database without revealing the requested index. In the silent preprocessing model, existing protocols typically adopt a two-layer pipeline: a first-layer retrieval based on LWE, followed by an RLWE ring-packing stage and a second-layer homomorphic column retrieval, with ring packing being the primary performance bottleneck. We observe that NTRU supports the homomorphic operations required by this pipeline while representing each ciphertext with a single ring element, suggesting its potential to replace RLWE for a more compact intermediate representation. However, NTRU lacks RLWE's public randomness component, which is required in the offline/online separation of most existing PIR schemes. We introduce NTPIR to address this challenge through three techniques: (1) Pack-then-switch: we perform ring packing in the RLWE domain and transform the result to NTRU via a single key switch, preserving the offline preprocessing structure while yielding compact, single-element packed intermediates. (2) Split-point picking: this method integrates second-layer column selection with response packing, reducing automorphism complexity from linear to square-root complexity in the number of packed second-layer inputs. (3) Optimized arithmetic: we employ FFT-based polynomial multiplication and approximate gadget decomposition to improve the computational efficiency of the underlying homomorphic operations, with concrete correctness error at most $2^{-40}$. On databases ranging from 1 to 8GB, NTPIR achieves up to a $1.81\times$ server-side online speedup over InsPIRe$^{(2)}$ (S&P'26). At 8\,GB, preprocessing step is $7$--$41\times$ faster than InsPIRe$^{(2)}$. In addition, at the highest-throughput configuration, NTPIR sustains 8,609MB/s on an 8GB database, corresponding to a $1.38\times$ speedup over InsPIRe$^{(2)}$, $1.8\times$ over SimpleYPIR, and $2.0\times$ over HintlessPIR.

Threshold signatures enable a set of $n$ parties to jointly generate signatures under a single public key such that any subset of at least $t+1$ parties can produce a valid signature, whereas any coalition of at most $t$ parties cannot. They constitute a fundamental primitive for distributed trust and are widely deployed in systems such as certification authorities, blockchains, and multiparty wallets. Modern applications require strong security guarantees under realistic adversarial models, including resistance to adaptive corruptions, tight security reductions, and low interaction complexity—most notably, a minimal number of communication rounds. Recent progress has produced threshold signature schemes in pairing-free groups that achieve tight and adaptive security with three rounds of interaction. This leaves open the central question of whether one can simultaneously achieve tight security, adaptive security, and two-round signing under a standard, non-interactive hardness assumption. In this work, we resolve this question by presenting TZAR, the first two-round threshold signature scheme that is tightly and adaptively secure under the standard decisional Diffie-Hellman (DDH) assumption in pairing-free cyclic groups. Our construction achieves full adaptive security against up to $t < n$ corruptions and admits a tight security reduction with only constant-factor loss. Consequently, TZAR provides strong provable security guarantees and minimizes interaction by requiring only two signing rounds, an important advantage for latency-sensitive distributed environments.

The Hamming Quasi-Cyclic (HQC) scheme is a post-quantum key encapsulation mechanism recently selected for standardization by NIST, making the security of its implementations a critical concern. In this work, we revisit the side-channel resistance of the latest HQC reference implementation, with a focus on its polynomial multiplication routine used in decryption. While prior work demonstrated a simple power analysis (SPA) attack against a lookup-table-based multiplication, the updated implementation replaces this with a bitwise schoolbook multiplication. Despite these modifications, we show that the updated function schoolbook_mul still shows clear, visually distinguishable variations in power consumption that depend on secret data. Using these patterns, an attacker can recover individual bits of the secret polynomial, demonstrating that SPA remains effective against the updated design. To address this vulnerability, we analyze potential countermeasures and propose a zero-cost mitigation based on swapping operand roles so that the mask computation depends only on public data. This eliminates direct leakage of secret-dependent control flow while preserving performance.

Mixnets provide network-level anonymity, traded off with increased communication latency, which consequently limits their applicability to only latency-tolerant applications, shrinking the anonymity set to clients engaged in such use cases. Addressing this issue requires optimizing latency, as recently explored in LARMix (NDSS’24) and LAMP (NDSS’25) through node arrangement and strategic routing. However, these approaches are tailored to specific mixnet designs, rely on simplified models and trust assumptions, or suffer from limited practical efficiency. In contrast, OptiMix bridges these gaps by introducing a general low-latency mixnet model adaptable to all well-established designs. To this end, we first propose an efficient distributed protocol for arranging nodes in mixnets that achieves low-latency properties while maintaining unbiasability against adversaries. Second, we introduce novel strategic routing schemes that optimize communication latency. Third, we design a load-balancing algorithm that evenly distributes traffic without undermining the latency-optimized characteristics of the routing strategies. Fourth, we conduct extensive evaluations using data from the deployed Nym mixnet, demonstrating substantial latency reductions with minimal anonymity loss across various mixnet designs—achieving up to $4\times$ performance gains over state-of-the-art solutions. Finally, considering that latency reduction incurs either anonymity degradation or increased bandwidth overhead—as stated by the anonymity trilemma—we propose a cover-routing mechanism that enables clients to benefit from low-latency mixnets without compromising anonymity, at the modest cost of generating additional cover traffic.

CKKS bootstrapping is a central tool for restoring the available modulus budget of approximate ciphertexts, thereby enabling homomorphic computations beyond a fixed leveled circuit. A key component is the pair of linear transformations CoeffToSlot and SlotToCoeff, which move data to the slot representation for homomorphic modular reduction and then back to the coefficient representation. In the sparse packing setting of Cheon et al. (EUROCRYPT 2018), the useful data occupy a short effective slot vector that is repeated across the full slot space. Existing methods for this setting mainly use the smaller effective dimension, whereas our approach exploits the repetition pattern itself to obtain simpler and cheaper transformations. We use the repeated slot pattern to improve the efficiency of both CoeffToSlot and SlotToCoeff. Each transform keeps multiplicative depth \(1\) and uses fewer homomorphic operators. Let \(N\) be the ring dimension, let the packed vector have length \(n/2\), and write \(r=N/n\) for the repetition factor. For each transform, when \(n\le r/2\), the cost is one plaintext-ciphertext multiplication and \(O(\log n)\) rotations. When \(n>r/2\), the cost is \(2n/r\) plaintext-ciphertext multiplications and \(O(\sqrt{2n/r}+\log r)\) rotations. We also analyze the auxiliary slots produced by the new \textsf{CoeffToSlot} layout and prove that they satisfy the same sub-Gaussian range bound as the desired coefficient slots. Consequently, under sparse-secret encapsulation, our bounds give \(K=24\) for \(p_{\mathrm{fail}}<2^{-128}\), compared with \(K=16\) for the standard layout. We implement the proposed transforms in OpenFHE using its default multithreaded configuration and evaluate them as part of the CKKS bootstrapping pipeline with sparse-secret encapsulation. For \(N=2^{16}\) and the tested effective sparse dimensions \(64\leq n/2\leq 1024\), our transforms are \(2.08\times\) to \(8.87\times\) faster than OpenFHE's depth \(1\) sparse linear transforms, yielding a \(1.22\times\) to \(6.07\times\) speedup in end-to-end bootstrapping. For \(64\leq n/2\leq 512\), our algorithm is slightly faster in end-to-end bootstrapping than OpenFHE's depth \(2\) baseline (whose time is \(1.03\times\) to \(1.25\times\) that of our algorithm) while using two fewer levels, and is comparable to the depth \(3\) baseline (whose time is \(0.86\times\) to \(1.07\times\) that of our algorithm) while using four fewer levels. The timings include the resulting EvalMod overhead associated with the larger \(K\) required by our layout. Overall, the results show that slot repetition can reduce the practical cost of CKKS bootstrapping for sparsely packed ciphertexts.

Poseidon is one of the most popular arithmetization-oriented (AO) hash function, due to its good performances both in evaluation and in Zero-knowledge proof protocols. It is for instance used in the Plonky3 library, and has been considered for use in the Ethereum protocol. The security of Arithmetization-oriented hash functions is commonly evaluated through the CICO-k problem, which consists in controlling simultaneously k coordinates in the input and output of the permutation. This problem is in particular relevant to finding preimages in sponge or compression mode and solving zero-test problems. Depending on the size of the underlying field, different values of k may be relevant. In this paper, we focus on the case of k=2, that was the subject of the recent bounty program by the Ethereum foundation. In this setting, one can model the CICO-2 problem as a bivariate system P(X, Y) = Q(X, Y) = 0 where the polynomials have total degree delta = d^(RF +RP). The best known methods for solving bivariate systems are algorithms for computing bivariate resultants. Over a generic system with coefficients over a finite field, the best algorithms achieve an asymptotic bit complexity that is linear in delta^(2+eps) log(q)^(1+eps), which is close to optimal, given that the input and output of the algorithm have bit size delta^2 log (q). However, the polynomial systems that stem from Poseidon are more structured, leading to a resultant that has degree DI = d^(2RF + RP), which is much less than what one would expect from a random bivariate system of degree d^(RF + RP). This fact has already been exploited in a previous work that used an evaluation-interpolation approach to compute the bivariate resultant in time that is quasi-linear in d^(3 RF + 2 RP). In this work, we exploit this fact by adapting another bivariate resultant algorithm to the special setting where the degree of the resultant of the equations is much lower than delta^2. By doing a careful analysis of the algorithm for systems with such property, we show that under some heuristics, the CICO-2 problem on Poseidon can be solved in time that is quasi-linear in DI delta^(1-1/w), where 2 <= w < 2.38 is the exponent of matrix multiplication. We validate our approach by implementing our attack on reduced versions of the Poseidon permutation, and show a practical speedup compared to the previous approaches.

Compressing correlated randomness is a key component of secure computation protocols in the silent preprocessing model and has received significant attention in recent years. Most existing constructions target additive correlations, where the parties receive additive shares of a relation. Beyond additive correlations, much less is known: more general linear correlations can be compressed using pseudorandom secret sharing, generic constructions for richer linear-output correlations can be obtained by combining LWE-based multiparty HSS with share conversion, in regimes where the share-conversion overhead is efficient, and general correlations can be compressed using indistinguishability obfuscation. In this work, we advance the study of compression for useful forms of correlated randomness beyond additive output sharing (concretely, linear-output correlations, together with a constrained variant capturing random permutations), without resorting to $iO$, introducing new techniques, new feasibility results, and relying on more diverse assumptions. We provide several constructions for pseudorandom correlation generators and functions using direct HSS- and LPN/MQ-based techniques. Concretely, we focus on two types of correlations in this work. First, we introduce pseudorandom permutation functions, where each party obtains a portion of a pseudorandom permutation $\pi$ over the set $\set{1,\dots, n}$, such that a single party learns nothing about the full permutation beyond its own output. We give a three-party construction of a pseudorandom correlation function (PCF) for permutations from homomorphic secret sharing satisfying a special share programmability property. This construction can be instantiated from a variety of standard assumptions and can even be concretely efficient (generating pseudorandom permutations in a fraction of a second). We describe two applications of pseudorandom permutation functions: one in anonymous broadcast and the other in single secret leader election. Second, we introduce pseudorandom correlation generators for classical correlations (such as Beaver triples) where additive secret sharing is replaced with threshold secret sharing. We obtain pseudorandom correlation functions for degree-$1$ Shamir shares of $\mathsf{NC}^1$ correlations from a variety of standard assumptions. We also introduce two new PCG constructions for threshold-shared constant-degree correlations in the regimes where either the privacy threshold $t$ or $n-t$ is a constant. These constructions rely on the conjunction of the LPN and MQ assumptions.

Homomorphic Encryption (HE) allows computations on encrypted data without decryption. It can be used where the users’ information are to be processed by an untrustful server, and has been a popular choice in privacy-preserving applica- tions. However, in order to obtain meaningful results, we have to assume an honest-but-curious server, i.e., it will faithfully follow what was asked to do. If the server is malicious, there is no guarantee that the computed result is correct. The notion of verifiable HE (vHE) is introduced to detect malicious server’s behaviors, but current vHE schemes are either more than four orders of magnitude slower than the underlying HE operations (Atapoor et. al, CIC 2024) or fast but incompatible with server- side private inputs (Chatel et. al, CCS 2024). In this work, we propose a vHE framework ZHE: effi- cient Zero-Knowledge Proofs (ZKPs) that prove the correct execution of HE evaluations while protecting the server’s private inputs. More precisely, we first design two new highly- efficient ZKPs for modulo operations and (Inverse) Number Theoretic Transforms (NTTs), two of the basic operations of HE evaluations. Then we build a customized ZKP for HE evaluations, which is scalable, enjoys a fast prover time and has a non-interactive online phase. Our ZKP is applicable to all Ring-LWE based HE schemes, such as BGV and CKKS. Finally, we implement our protocols for both BGV and CKKS and conduct extensive experiments on various HE workloads. Compared to the state-of-the-art works, our prover time is very fast: our prover overhead (measured by how many times slower than the underlying HE computation) is one to two orders of magnitude cheaper than state-of-the-arts.

Recent attacks on private set intersection (PSI) and PSI-like protocols have demonstrated that input privacy can be compromised when parties maliciously choose their inputs, even in protocols proven secure against malicious adversaries. To counter such attacks, Authorized PSI (APSI) introduces a judge who authorizes the elements of the parties before the intersection is computed. Falzon and Markatou (PETS 2025) proposed Partial-APSI, a privacy-preserving variant of APSI that prevents revealing the entire set to a judge. Their Partial-APSI protocol requires significant bandwidth overhead due to the use of bilinear pairings and because the judge must sign each element in the input set. In this work, we present a bandwidth-efficient Partial-APSI protocol that outperforms Falzon and Markatou, both asymptotically and empirically. For example, for sets of size $2^{20}$, we require around $21\times$ less bandwidth and are about $6\times$ faster over a LAN network. In addition to our protocol, we model the real-world behavior of rational parties through a game-theoretic analysis. We introduce payout mechanisms for detected cheating and establish lower bounds on their values, ensuring that the best strategy for rational parties is to provide honest input.

Deep neural networks (DNNs) are valuable assets, yet black-box access to them raises security concerns about parameter extraction by malicious adversaries. Recent work by Carlini et al. (Crypto’20) and Canales-Martínez et al. (Eurocrypt’24) drew a parallel between model extraction and block-cipher key recovery via chosen-plaintext attacks. Using tools from differential cryptanalysis, they showed that all weights and biases of black-box ReLU-based DNNs can be recovered with a polynomial number of queries and polynomial-time post-processing. However, their attacks assume access to the exact numerical values of the output logits, enabling the computation of derivatives. To overcome this limitation, Chen et al. (Asiacrypt’24) studied the more realistic hard-label setting in which the attacker observes only the final classification label (e.g., “dog” or “car”). They proposed an extraction method that uses a polynomial number of oracle queries but has exponential running time. Moreover, their algorithm applies only to a restricted family of architectures, handles only binary classifiers, and is demonstrated only on very small networks with at most four neurons across up to two hidden layers. In this paper, we introduce new techniques that, for the first time, achieve cryptanalytic extraction of DNN parameters in the hardest hard-label setting using both a polynomial number of queries and polynomial-time computation for a broad class of ReLU-based networks. We validate our approach on a DNN trained on CIFAR-10 with 832 neurons in four hidden layers and nearly one million parameters in total. We further present an end-to-end black-box implementation of our attack, which we evaluate on a smaller artificial network, and extend our methods to leaky-ReLU activations. Our results show that, for our scenarios, all weights of a ReLU-based DNN can be efficiently recovered by analyzing only the geometric shape of its decision boundaries.

Multivariate quadratic (MQ)-based digital signature schemes are promising candidates for the ongoing post-quantum (PQ) standardization procedure due to their compact signatures and fast verification. However, the side-channel security of their recent optimized and protected implementations remains underexplored. This work presents novel side-channel attacks on the MQ-based signature scheme MAYO, targeting both unprotected and masked implementations. We develop the first non-profiled single-trace correlation power attack against the recent nibble-sliced implementation of MAYO. Next, we evaluate two masking approaches proposed for MQ-based signatures. Our findings indicate that masking sensitive variables alone leaves the implementation vulnerable to single-trace attacks, and that masking only public variables also fails to provide the intended protection. To assess the second case, we consider both profiled and blind adversaries. The blind setting adopts a recent deep-learning-based blind side-channel analysis framework and demonstrates secret-key recovery without access to the masked public values or a cloned device. We validate our attacks on an STM32F3 Cortex-M4 platform and demonstrate that recently proposed countermeasures do not provide adequate protection against realistic single-trace adversaries. Finally, we discuss how the underlying attack methodology extends to other MQ-based signature schemes and present a strengthened masking and refreshing countermeasure that mitigates the proposed attacks.

Encrypted matrix multiplication (MM) is a fundamental primitive in privacy-preserving machine learning and encrypted data search, but it remains a significant performance bottleneck. Recently, Bae et al.~(Crypto’24) and Park~(Eurocrypt’25) introduced novel algorithms for ciphertext–plaintext (CPMM) and ciphertext–ciphertext (CCMM) matrix multiplications. These algorithms reduce encrypted MM operations to plaintext matrix multiplications (PPMM), enabling implementation through highly optimized BLAS libraries. While these reduction-based methods offer significant improvements, their benefit is limited to scenarios where the matrix dimension $d$ is comparable to the ring dimension $N$ in RLWE-based CKKS schemes. As a result, they fall short for matrix multiplications involving small or medium-sized matrices. We extend the reduction-based CPMM/CCMM into small-sized matrix operations by batching instances. We encode a batch of matrices into a single matrix over algebraic integers, where each entry is obtained by applying the inverse Discrete Fourier Transform to the batch matrix entries at the same position. This encoding enables reductions of encrypted batch MM algorithms to a small number of batch PPMMs, which can be efficiently accelerated by BLAS libraries. Our batch encrypted MM flexibly accommodates diverse matrix dimensions and batch sizes independent of the ring dimension $N$, thereby extending its applicability to practical real-world settings. For two $d \times d$ matrices with $N/d$ batches, our batch CPMM and CCMM algorithms achieve $O(d^2N)$ cost, improving over Bae et al.'s $O(dN^2)$ and Jiang et al.'s $O(d^2N\log N)$~(CCS'18). We further extend our techniques to rectangular matrices, achieving $O(dN^2)$ for multiplying a $d \times N$ matrix by an $N \times N$ matrix, improving previous $O(N^3)$ methods. A proof-of-concept implementation validates these improvements: multiplying 128 batches of $64 \times 64$ matrices takes $0.20$s (CPMM) and $1.08$s (CCMM), yielding $240\times$ and $52\times$ speedups over previous methods. For a $64 \times 2048$ by $2048 \times 2048$ multiplication, our CCMM completes in $7.5$s, achieving a $29\times$ speedup compared to Park's algorithm.

Block-Accumulate-Accumulate (BAA) codes provide fast encoding for pseudorandom correlation generators and code-based zero-knowledge. We replace their independently sampled local maps with repeated copies of one fixed short code. This chosen-block construction retains the two permutation-prefix-sum rounds while allowing the constituent code to be selected for distance and efficient implementation. Over $\mathbb{F}_2$, exact weight-distribution propagation gives finite-length distance guarantees. Suitable constituents yield numerical asymptotic distance estimates reaching $99.99\%$ of the Gilbert-Varshamov (GV) distance at rate $1/2$. Our practical binary instantiations encode about a million message symbols in $23$-$24$ ms on one CPU thread and under $6$ ms on $24$-$32$ threads. Over larger fields, we add random nonzero coordinate scalings and account for cancellations. For every field of size $q\ge2^{127}$, including $128$-bit prime fields, Reed-Solomon constituents certify relative distances $0.30$ and $0.60$ at rates $1/2$ and $1/4$, respectively. At message dimension $k=2^{20}$, each distance bound fails with probability below $2^{-137}$ under independent uniform sampling of the permutations and nonzero scalings. The rate-$1/4$ asymptotic distance estimate reaches $81\%$ of large-field GV. To investigate the gap between this estimate and GV, we identify permutation patterns that force low-weight codewords regardless of the nonzero coordinate scalings.

Privacy-oriented cryptocurrencies like Zerocash only support direct payments and not the execution of more complex contracts. Bitcoin and Ethereum, on the other hand, cannot guarantee privacy, and using them for contract execution leaves open questions about the fungibility of proceeds and requires contract designers to take frontrunning countermeasures. This work reconciles the two worlds and develops a lightweight protocol for decentralized execution of complex contracts that (1) is undetectable to the network at large, (2) maintains anonymity of the potentially mutually distrustful counterparties and unlinkability of their repeated interactions, (3) guarantees fair termination, and (4) is immediately resistant to frontrunning and miner bribery attacks. This is achieved by leveraging the confidentiality and anonymity guarantees of Zerocash and the verifiability and flexibility of trusted execution environments.

We develop the method of Luo, Fu and Gong (LFG) - as extended by Fan, Kuchta, Sica and Xu (FKSX) to use endomorphism scalars - in order to find best families suitable for multi-scalar multiplication (MSM) for any number $n$ of points and with adjustable storage. In particular we lower storage requirements by an average of 67% and decrease the number of curve operations by an average of 7% (and up to 10.6%), relative to the LFG method. Compared to Pippenger's variant (standard when $n$ is large), we manage to improve performance by an average 6% for an MSM with $n\in [2^{10},2^{21}]$, while at the same time decreasing storage by up to 15.8% using the BLS12-381 curve. We also improve the FKSX performance, due to a smaller bucket set, by around 7%. This is done by finding the optimal bucket set in the endomorphism case and by providing a fast algorithm to generate an associated Hamiltonian path with short edges. The proposed method is suitable for immediate software deployment at all sizes where MSM is currently used commercially, such as for Zcash and blockchain. Code to generate all ordered bucket sets is provided in a repository.

Private information retrieval (PIR) is a fundamental primitive for protecting user privacy. It enables a user to retrieve entries from a public database without revealing which entries are being retrieved. PIR has been studied in many settings, e.g., with information-theoretic or computational security, with a single server or multiple non-colluding servers, and with or without preprocessing to the database. In this article, we describe several PIR schemes that we believe are accessible to readers without prior knowledge in PIR. Although conceptually simple, these schemes capture the main ideas underlying mainstream design paradigms. We also describe extensions of PIR that support keyword queries and batch queries. Beyond describing the schemes themselves, we characterize the concrete efficiency of different PIR paradigms, provide guidance on selecting a paradigm in practice, and discuss practical applications of PIR. We hope this article helps readers understand the current research landscape in PIR and serves as a starting point for exploring more advanced topics in the field.

ZK-friendly hash functions are often built from algebraic SPN permutations. The matrix provides diffusion by mixing the state elements after the S-box layer. However, there is no uniform convention for selecting matrices for the linear layer across primitives. Matrix selection may follow a transparent nothing-up-my-sleeve procedure or prioritize implementation efficiency. Some specifications instead treat any MDS matrix as admissible. This parameter-selection freedom also persists in practice, as some deployed implementations replace the concrete matrix proposed in the original specification with an alternative instantiation. We show that adversarial use of this freedom can create a kleptographic attack surface. In this paper, we study kleptographic backdoors embedded in the matrices of ZK-friendly hash functions. Assuming that a malicious designer controls matrix selection, the designer can choose a matrix that maps a chosen input to a chosen output under appropriate round and parameter conditions. The resulting matrix is MDS and passes the additional matrix security checks required by the target primitive. Three case studies show that such a backdoor could have critical security consequences in real-world deployments. In Plonky3, it would allow a prover to control a Fiat--Shamir challenge and make the verifier accept an invalid claim. In Neptune Cash, it would permit creating a digest collision between the program that checks whether a transaction is valid and one that omits this check, enabling counterfeit currency. Finally, in Plonky2, it would enable a forged Merkle-tree membership proof for an attacker-chosen element. Our results show that satisfying the MDS condition and other security requirements is insufficient to establish that a matrix is trustworthy. Its generation process must also be transparent and verifiable.

Puncturable attribute-based encryption ($\mathsf{PABE}$) not only supports fine-grained access control over encrypted data, but also enables users to revoke the decryption capability for specific messages by puncturing tags, thereby achieving fine-grained forward security. It finds wide applications in scenarios such as sharing government classified documents and personal health records. However, existing $\mathsf{PABE}$ schemes only support tag-by-tag puncturing, where each puncturing operation is done through key delegation, which causes the key size to grow with the number of punctured tags. This inefficiency makes $\mathsf{PABE}$ impractical in scenarios that require frequent puncturing or mass revocations. To address this limitation, it is crucial to support batch puncturing of tags, i.e., the decryption capability for messages associated with multiple tags can be revoked simultaneously via a single puncture. In this work, we construct a ciphertext-policy attribute-based encryption ($\mathsf{CPABE}$) scheme for circuits with batch-puncturing. Notably, the size of the punctured key in our scheme is independent of the number of punctured tags, as well as the size and depth of the circuits. This is achieved by leveraging the evasive learning with errors ($\mathsf{LWE}$) and tensor $\mathsf{LWE}$ assumptions. In addition, we observe that puncturable $\mathsf{CPABE}$ can be re-stated by dual-policy $\mathsf{ABE}$ ($\mathsf{DPABE}$) with key delegation, and generalize batch-puncturing $\mathsf{CPABE}$ to provide the first lattice-based construction of $\mathsf{DPABE}$ for circuits. Moreover, inspired by the observation of Agrawal and Yamada (Eurocrypt '20), we introduce the puncturing property into optimal broadcast encryption ($\mathsf{BE}$), capturing a new primitive called puncturable $\mathsf{BE}$, which allows the receiver to securely erase sensitive messages without communicating with the authority.

The SPHINCS+ framework provides the underlying architecture for modern quantum resistant stateless hash-based signatures. Notable examples include the NIST standard SLH-DSA and its recent variants such as SPHINCS-α and SPHINCS+C. We extend the hypertree structure that underlies the SPHINCS+ framework by allowing trees of different heights to appear on different layers, and we plug generalized hash-based one-time signatures with chains of different lengths into the hypertree. We give a reduction showing how the security proof for the SPHINCS+ framework extends to these structural generalizations. These generalizations lead to an enlarged design space, opening up the possibility for finer-grained trade-offs. We perform a systematic exploration of the parameter space for the generalized structure guided by a thorough theoretical cost analysis that minimizes the number of variables to be enumerated in the searching process. As a result, we identify many parameter sets superior to state-of-the-art stateless hash-based signature schemes in terms of signature size, signing or verification efficiency. In particular, we provide some parameter settings not only enjoying smaller signature size, but also more efficient in signing and verification. The improvement can be significant if we do not pursue optimizing all performance metrics simultaneously. One of our 128-bit secure constructions intended to balance all metrics with size and verification speed as priorities is 9.8% smaller than SPHINCS+C-128s (27.6% smaller than SPHINCS+-128s, 18.3% smaller than SPHINCS-α-128s, and 22.5% smaller than SPHINCS+FP-128s). Further size reduction is possible with a greater sacrifice in speed. Moreover, we apply our technique to schemes supporting less than 264 signatures. We provide implementations and benchmark results for representative parameter sets.

Deniable Encryption (Canetti et al., CRYPTO 1997) enables parties to produce fake internal states making any transcript consistent with any plaintext of their choice. Fully Deniable Encryption (FDE) (Canetti et al., CRYPTO 2020) achieves the strongest two-party guarantee since both sender and receiver can independently fabricate randomness, even with mutually inconsistent claimed plaintexts, and anyone can fake the receiver's side. However, FDE addresses only post-execution coercion and remains confined to the two-party setting, which leaves both adaptive coercion (where parties may be coerced at any round during execution) and threshold deniability (where secrets are distributed among $n$ parties) as open problems. In this work, we resolve the threshold gap and take a definitional step toward the adaptive one. We design Threshold Fully Deniable Interactive Encryption (TFDE) via FDE with a universal thresholdizer, equivocable commitments, and non-committing encryption via a four-layer equivocation pipeline so that any coalition of fewer than~$t_S$ senders and~$t_R$ receivers can produce per party fake states indistinguishable from honest executions, while satisfying all standard threshold public key encryption properties; like FDE itself, which is a feasibility result. Moreover, we formalize Strong Off-the-Record Deniability (SORD), a new notion that captures adaptive mid-execution coercion and consistent fake claims by both parties.

Passwords remain the dominant authentication method despite weaknesses such as offline dictionary attacks and password reuse. Single Password Authentication (SPA) mitigates these risks by protecting high entropy secrets under one memorable password and distributing them across untrusted storage providers. However, existing SPA schemes cannot prevent preemption and overwrite attacks by storage providers, and they lack secure, efficient support for secret and password updates. We present UpSPA, an efficient, secure, and updatable threshold SPA that addresses both limitations without requiring changes on the login server. UpSPA prevents preemption through a storage provider specific high entropy identifier secret, supports secret updates via implicit authentication, and enables password updates via explicit authentication using a password protected signing key. We prove security in the ideal real paradigm, including resistance to offline dictionary attacks under standard static threshold corruption assumptions. Our evaluation shows low overhead and competitive performance compared to a prior SPA scheme that does not support updates.

We study the uniform key-space complexity of information-theoretic target-distribution semantic security (TDSS) for symmetric encryption. Given a message distribution \(P\), we ask for the minimum size of a uniform key space such that observing the ciphertext improves the optimal prediction probability of any Boolean predicate of the message by at most \(\varepsilon\). Our main construction is a sample-based encryption scheme with \(\kappa\) keys: for a secret key $k\in[\kappa]$, the message is placed in the $k$-th position, and each of the remaining $\kappa-1$ positions is filled with an independent sample from a dummy distribution $P_{D}$. When \(P_D=P\), the posterior distribution of the message conditional on the ciphertext is exactly the empirical distribution of \(\kappa\) independent samples from \(P\). This gives a universal semantic-security bound of \(1/(2\sqrt \kappa)\), so \(\kappa=O(\varepsilon^{-2})\) keys suffice for every message distribution, independently of the message-space size. We prove a complementary lower bound in terms of \(\|P\|_2\), matching this rate up to constants for sufficiently flat distributions. In particular, for the uniform distribution on \(|\mathcal{M}|\) messages, the optimal key-space size is $\Theta\!\left(\min\{|\mathcal{M}|,\varepsilon^{-2}\}\right).$ The same framework recovers and generalizes the classical key-length scaling of entropic security: taking \(P_D\) uniform on \(\{0,1\}^n\), a mixture-and-cloning argument protects every source of min-entropy at least \(h\) using $n-h+2\log(1/\varepsilon)+O(1)$ secret-key bits. It also yields a broader source-family view of information-theoretic semantic security, showing that short-key TDSS is possible for any family of sources with bounded second-order R\'enyi divergence from a common reference distribution. We further study zero-advantage TDSS (i.e., $\varepsilon=0$) for restricted predicate classes \(\mathcal F\). We show that a perfectly correct cipher achieving zero-advantage TDSS for $\mathcal F$ with a uniform $\kappa$-element key space exists if and only if $P$ admits a decomposition into $\kappa$-sparse posteriors that preserve the prior Bayes-optimal prediction for every $f\in\mathcal F$. This sparse-convex characterization implies that \(|\mathcal F|+1\) keys always suffice. Surprisingly, point, threshold, and interval predicates can all be protected exactly with only two keys for every message distribution. Our results connect information-theoretic encryption with sparse convex decompositions and the shuffle model, and provide a systematic view of zero-advantage and approximate TDSS with short secret keys.

Secure communication in the Internet of Things (IoT) requires lightweight protocols that scale across unicast, multicast, and broadcast settings. Existing solutions typically depend on centralized gateways, which introduce single points of failure and scalability limitations. We propose TreeCast, a distributed group key establishment protocol that organizes devices into a binary tree of hashed Diffie–Hellman secrets, which naturally unifies unicast, multicast, and broadcast in a single scalable hierarchical structure. This design yields logarithmic rekey costs, efficient subtree derivation with efficient device addition and revocation in large and dynamic IoT environments and strong security properties including authentication, partial forward secrecy, and post-compromise recovery. We present a detailed security analysis and to demonstrate practical viability, implement TreeCast on an Arm Cortex-M33 using only software cryptography, without any hardware accelerators. Our measurements show that TreeCast performs key establishment and rekeying within realistic IoT timing and energy budgets, achieving sub-millisecond tree updates and low memory footprint. These results establish TreeCast as a lightweight, scalable, and deployable solution for secure communication in next-generation IoT networks.

As digital identity verification becomes increasingly pervasive, existing privacy-preserving approaches are still limited by complex circuit designs, large proof sizes, trusted setups, or high latency. We present Vega, a practical zero-knowledge proof system that proves statements about existing credentials without revealing anything else. Vega is simple, does not require a trusted setup, and is more efficient than the prior state-of-the-art: for a 1920-byte credential, Vega achieves 92 ms proving time, 23 ms verification time, 108 kB proofs, and a 464 kB proving key. For smaller credentials (896 bytes), these drop to 62 ms proving, 17 ms verification, and 83 kB proofs. At the heart of Vega are two principles that together enable a lightweight proof system that pays only for what it needs. First, fold-and-reuse proving exploits repetition and folding opportunities (i) across presentations, by pushing repeated work to a rerandomizable precomputation; (ii) across uniform hashing steps, by folding many steps into a single step; and (iii) for zero-knowledge, by folding the public-coin transcript with a random one. Second, lookup-centric arithmetization extracts relevant values from credential bytes, both for extracting relevant fields without full in-circuit parsing, and to enable length-hiding hashing.

We present an efficient attack on a knot-based Diffie--Hellman key exchange proposed by Sconza and Wildi. In the proposal, the two parties exchange oriented knots, combine them under connected sum to obtain a common knot, and derive the shared secret by evaluating a finite type invariant of degree $m$ on it. We show the scheme is insecure for every choice of finite type invariant. The shared secret can be computed from the public transcript at roughly three times the cost of running the scheme honestly. The attack maps knots into a truncated Polyak space $\mathcal{P}_m$, in which connected sum becomes multiplication and every element of the image is invertible, so the public knot can simply be divided out. This bypasses all countermeasures put in place by the proposed protocol. Independently of the attack, we show that the key space is too small for the parameters proposed. A degree-$m$ invariant takes $O(c^{m})$ values on knots represented with diagrams consisting of $c$ crossings. For the suggested crossing number, reaching the $128$ bits claimed would require $m\ge 10$, at which point a single evaluation of the invariant costs in the order of $2^{50}$ operations.

Isogeny group action based signatures are obtained from a sigma protocol with high soundness error, say $\frac{1}{2}$ for its most basic variant. One needs to independently repeat the sigma protocol $O(\lambda)$ times to reduce the soundness error to negligible (with $\lambda$ being the security parameter). These repetitions come with a considerable efficiency and size overhead. On the other hand, quaternion isogeny-based signatures such as SQIsign and PRISM are directly obtained from a sigma protocol with a negligible soundness error. The secret key in SQIsign and PRISM is a random supersingular isogeny, and both schemes are insecure when the secret isogeny arises from the supersingular isogeny group action setting. In this paper, we propose WaterSQI and PRISMO, variants of SQIsign and PRISM respectively, suited for secret isogenies that arise from the supersingular isogeny group action setting. They use a sigma protocol whose soundness error is negligible without requiring parallel repetitions. They are hence more compact and $O(\lambda)$ times more efficient compared to Generalised CSI-FiSh (the generalisation of CSI-FiSh to large parameters using generic isogeny group action evaluation algorithms such as Clapotis/KLaPoTi/PEGASIS). For example, for our proof of concept implementation with a 2000 bits prime in Sagemath, PRISMO, when compared to Generalised CSI-FiSh with the same public key size, is about 80x faster for signing and 1457x faster for verification, while also being 29x more compact (signature size). Moreover, we prove that WaterSQI is a quantum proof of knowledge of the full endomorphism ring.

Quadratic Boolean functions (that is, Boolean functions of algebraic degree at most 2), bent Boolean functions (i.e. maximally nonlinear Boolean functions in even numbers of variables) and, as we observe in this paper, partially-bent Boolean functions (i.e. affine extensions of bent functions to linear super-spaces), share a strong property: all their restrictions to affine hyperplanes are plateaued (i.e. have a Walsh transform valued in a set of the form $\{0,\pm \lambda\}$, where $\lambda$ is a positive integer called the amplitude). In this paper we determine for any $n$ and $k<n$ the class $C^n_k$ of those $n$-variable Boolean functions whose restrictions to all $k$-dimensional affine subspaces of $\F_2^n$ are plateaued (of any amplitude). We show that, for any $n\geq 4$, $C^n_{n-1}$ equals the class of partially-bent functions, and for $3 \leq k \leq n-2$, $C^n_k$ equals the class of quadratic functions (while for $0\leq k\leq 2$, it equals of course the class of all Boolean functions). This provides a new characterization (after almost 20 years) of partially-bent functions and a hierarchy among $n$-variable Boolean functions by six nested classes, each of which happens to be, for any $n\geq 5$, strictly included in the next one: quadratic functions, partially-bent functions, the restrictions of $(n+1)$-variable partially-bent functions to $\F_2^n$, plateaued functions, the restrictions of $(n+1)$-variable plateaued functions to $\F_2^n$, and all Boolean functions. We leave open the two problems of determining exactly what are the third and fifth of these classes, but we begin the study of the first of these two classes by characterizing the situation where a plateaued function $g$ has a restriction $f$ to an affine hyperplane $H$ that is plateaued. We also characterize when $g$ is partially-bent. Our characterization of partially-bent (resp., quadratic) functions extends to strongly plateaued vectorial functions. We state an open question on vectorial functions that happens to be related to an important one on crooked functions.

We consider (boolean or arithmetic) circuits in which every gate may compute an arbitrary function of its input gates. We show a novel tradeoff between a circuit's size and its fan-in: \begin{quote} Any function which may be computed using $s$ fan-in $2$ gates can alternatively be computed using $s/3\ (1+O(1/\sqrt{k}))$ fan-in $k$ gates. \end{quote} This asymptotically improves the previous bound of $2s/5\ (1+O(1/k))$ by Charbit, Couteau, Meyer, and Naserasr [TCC'24]. Among other applications, this improves the communication complexity of secure multiparty computation in the correlated randomness model. \emph{Any} $n$-input $m$-output circuit with $s$ internal gates (over arbitrary binary gates) can be securely computed in the correlated randomness model with per party communication $s/3 + n + m$ and computation $\widetilde{O}(s)$. Our paper stands at the intersection of cryptography, complexity theory, and graph theory, but our main technical contribution is one to extremal combinatorics: we establish that every order-$n$ $2$-degenerate graph admits a planarising set of size at most $\lfloor n/3 \rfloor$. Our main conceptual contribution is to relate the existence of sublinear-size (directed) $k$-path transversals to well-studied graph parameters. Along the way, we uncover a recurringly overstated lemma throughout the literature on sublinear-size vertex-separators and hyperfinite graphs. According to this lemma, any monotone graph class admitting sublinear-size balanced vertex separators should be weakly hyperfinite. However, this is contradicted by a graph class put forward by [Moshkovitz and Shapira, Random Structures \& Algorithms'15]. Unfortunately, the lemma appears in highly influencial works such as [Henzinger, Klein, Rao, and Subramanian, STOC'94 \& JCSS'97], or the textbook of Nešetřil and Ossona de Mendez [\emph{Sparsity}, Springer'12], and in turn it is used in a significant number of papers. Thankfully a slightly weaker version of this lemma is true, with a caveat on how sublinear the vertex separators needs to be, and we provide the correction as a service to the community.

For a linear code $C\subseteq\mathbb{F}_q^n$, we say that $C$ satisfies the proximity-gaps property up to distance $\delta_1$ if, for every $\delta_2>\delta_1$ and every $f,g\in\mathbb{F}_q^n$, at least one of which is $\delta_2$-far from $C$ in relative Hamming distance, there are only a small fraction—typically at most $\operatorname{poly}(n)/q$—of exceptional coefficients $z\in\mathbb{F}_q$ for which $f+zg$ is $\delta_1$-close to $C$. The work [BGKS20] shows that every linear code of relative distance $\delta$ satisfies proximity gaps up to the one-and-a-half Johnson radius \[ J_{3/2}(\delta)=1-(1-\delta)^{1/3}. \]We prove that this threshold is tight for general linear codes at every distance $0<\delta<1$. Specifically, for every $0<\delta<1$, we construct a linear code of relative distance arbitrarily close to $\delta$ and words $f,g\in\mathbb{F}_q^n$ that are both \[ 1-(1-\delta)^{4/9} \]far from the code, but for which a constant fraction of coefficients $z\in\mathbb{F}_q$ make $f+zg$ nearly $J_{3/2}(\delta)$-close to the code. Our counterexamples continue to hold even when a fixed amount of distance-dependent slack is allowed.

Let $H_1:=\liminf_{n\to\infty}(p_{n+1}-p_n)$, where $p_n$ is the $n$-th prime. The twin-prime conjecture asserts that $H_1=2$. Zhang [Zha14] proved the first finite bound, $H_1<7\times10^7$. Maynard [May15] improved this bound to $H_1\le600$. Polymath [D. 14b] subsequently established $H_1\le246$. Stadlmann [Sta26] further improved the bound to $H_1\le240$. In this paper, we prove $H_1\leq236$.

Dynamic zkSNARKs were recently introduced by Wang et al. [Eurocrypt, 2026]. This primitive extends standard zkSNARKs with an update algorithm that adapts a proof to a new statement in time sublinear in the circuit size, provided the witness changes in few positions. However, existing constructions either need a circuit-specific setup or, in the universal case, send over $130$ group elements and require over $180$ pairings. As is the case for universal zkSNARKs, dynamic ones can be built from dynamic arguments for Hadamard products and linear relations. Wang et al. handle the latter in the particular case of a permutation matrix, via a sparse argument---a protocol whose prover runs in time proportional to the Hamming weight of the witness. Nevertheless, their techniques do not directly extend to the arbitrary matrices arising in constraint systems such as R1CS or CCS. Furthermore, the standard approach for proving general linear relations is unsuitable for the sparse setting because of a witness-independent step: the prover commits to an auxiliary polynomial determined by the matrices alone, and is hence dense regardless of how sparse the witness might be. Our first contribution is a sparse zkSNARK for linear relations, which we build from a fully witness-dependent argument together with what we call a rational encoding of the matrices. As our second contribution, we develop a compiler that turns any sparse argument for a linear relation into a dynamic one, while preserving the zero-knowledge property of the underlying scheme. Instantiated for Plonk and R1CS-lite, our techniques yield universal dynamic zkSNARKs with at most $20$ group elements per proof and $23$ verifier pairings---over $6.5\times$ and $7.8\times$ fewer than the state of the art---as well as asymptotically faster updates. We also show how both of our constructions can be de-amortized.

In 2021, Bruna, Regev, Song and Tang introduced the continuous analogue of LWE, CLWE. Shortly after, Gupte, Vafa, and Vaikuntanathan showed a classical reduction from LWE to CLWE and from discrete-CLWE (secret from a discrete set) to LWE. In this paper, we show two results. The first result is a search-to-decision reduction for CLWE. The search-to-decision reduction works similarly to the standard reduction for LWE. The main difference between the reductions is the continuous nature of the CLWE secret. As a consequence, our reduction can find the secret up to a polynomial error $n^{-k}$ for some constant $k$. The second and our main result is the reduction from CLWE to discrete-CLWE. The reduction is an identity reduction, i.e. samples are passed as-is to the distinguisher. To prove the distinguisher can accept the samples we employ tools from analytic number theory. These tools allow us to show that the set $\frac{1}{r} \cdot \mathbb{Z}^n$ with fixed $\ell_2$ norm $r$, i.e. integer vectors projected onto the unit sphere, can mimic the unit sphere $S^{n-1}$ for some $r > r'$. By completing this missing link, we can show that LWE is equivalent to CLWE i.e. $\text{LWE} \equiv \text{CLWE}$ and existing or new results on each problem apply to the other.

FUTURE is a lightweight block cipher with a 64-bit block, a 128-bit key and $10$ rounds, proposed at AFRICACRYPT 2022 for low-latency hardware. This study analyzes FUTURE in the related-key setting with a bit-level constraint model that carries the exact weights of the differential distribution table and the exact entries of the boomerang connectivity table, and whose objective function $2w_0 + 2w_1 + w_{\mathrm{bct}} = -\log_2(p^2q^2r)$ optimizes both sub-ciphers and the middle layer of the sandwich framework together. The model returns a full-round distinguisher whose objective function value $36$ is optimal over all switching rounds and whose probability is $P = \hat{p}^2\,\bar{r}\,\hat{q}^2 = 11\cdot 2^{-39} \approx 2^{-35.54}$, at a cost of $2^{37.54}$ queries under four related keys and $2^{37.54}$ XOR operations. Running it on the full cipher over $2^{44.34}$ quartets returns $341$ right quartets and an experimental probability of $2^{-35.92}$, in $63.9$ hours on an ordinary personal computer; at the previous full-round probability $2^{-45.8}$ the same computer would take about $6.8$ years. The distinguisher is therefore a practical one, and improves the best previously known full-round related-key boomerang distinguisher of FUTURE by a factor of $2^{10.26}$ in probability, in data and in time. An $8$-round distinguisher placed into the unified key recovery framework further gives a full-round attack with $2^{51.05}$ data, $2^{64}$ time and $2^{64}$ memory, whose time complexity attains the optimum of the framework at any memory within the codebook and improves the best previously known attack by a factor of $2^{6}$.

Proving the correctness of computations over a large dataset via succinct non-interactive arguments of knowledge (SNARKs) entails the large overhead of ``loading'' the dataset in the SNARK. However, certain computations may only need to access a small fraction of the dataset (e.g., a database query that only accesses a subset of table rows and then computes an aggregation function). The standard way of \emph{efficiently} proving such computations is to use \emph{lookup arguments with sublinear prover complexity} to load only necessary data to the SNARK. Unfortunately, all prior schemes are \emph{static}: even a single change to the dataset forces the prover to re-run an expensive pre-processing step, linear to the dataset size. The only exemption is the recent work of Dutta et al., (CCS'24) that proposed a lookup argument with \emph{amortized} sublinear updates---based on re-running the pre-processing phase periodically, when too many changes have been accumulated. In this work, we present Rogue, the first lookup argument with sublinear prover time and updates that \emph{always} take time proportional only to the number of incurred changes. Indeed, Rogue is actually a \emph{matrix lookup argument}, supporting entire row lookups in time proportional to the number of rows (and independent of their size)! It has very good practical performance, e.g., for a $2^{20}\times 2^7$ matrix and $2^{10}$ row accesses, Rogue achieves $\times 21$-$942$ and $\times 76$-$30000$ faster lookups and updates, respectively, compared to prior works. We then use Rogue to build RogueDB, the first verifiable database system for arbitrary SQL queries that supports authenticated indexes, hence achieves prover time sublinear to the database. Compared with prior schemes with succinct proofs, vSQL (Zhang et al., IEEE S\&P'17) and PoneglyphDB (Gu et al., SIGMOD'25), we get $\times 42.8$-$\times 8624.1$ and $\times 149.6$-$\times 11362.4$ faster prover times, for various SQL queries from the TPC-H benchmark.

NIST standardised the lattice-based key-encapsulation mechanism ML-KEM and the lattice-based digital signature scheme ML-DSA in 2024. Both compute a forward number-theoretic transform (NTT) over secret-bearing polynomials; the NTT's twiddle constants are a documented fault-attack surface. Published attacks zero every twiddle at once on ML-KEM key generation, or individual twiddles on ML-DSA signing. Countermeasures detect or mask such faults but none quantifies how much a single-twiddle perturbation disturbs the secret. This paper does, for key generation: the exact rank at each NTT layer of the linear map from the secret to the difference between a correct and a faulted run, for arbitrary twiddle perturbations, bit-flips included. Through that map, a single twiddle fault reveals as many independent linear combinations of a secret polynomial as there are butterflies using the twiddle, an exact count and not just a bound; stacking one fault per layer collapses the map's kernel to two coefficients of that polynomial for ML-KEM and one for ML-DSA. This kernel is the same whichever twiddle is hit in each layer, and no fault set, however large, shrinks it; the rank and kernel are machine-checked in Lean 4. ML-KEM publishes the faulted key uncompressed, so an attacker recovers all but those coefficients for all but a small fraction of keys; ML-DSA compresses its key, leaving the exact recovered count open. The exact per-layer rank tells countermeasure designers how much each layer's fault disturbs the secret.

Adaptor signatures have emerged as a powerful contract-minimal mechanism for fair exchange on blockchains, enabling efficient and privacy-preserving atomic swaps and conditional payments. However, existing adaptor schemes are limited to narrow classes of NP relations (e.g., discrete logarithm secrets) and specific signature schemes, limiting their scope both in terms of constructions and applications. This work addresses this gap by presenting a new framework that supports arbitrary NP relations and a broad range of signature schemes, significantly extending the reach of adaptor signatures beyond prior works and broadening the design space for adaptor signature constructions. Our framework also yields adaptor signatures that are compatible with today's blockchain systems. More specifically, we devise two general compilers for adaptor signatures. First, we show how to efficiently lift adaptor signatures from structured languages (such as discrete log relations) to general NP languages with the help of degree-$2$ homomorphic encryption, resulting in adaptors for standard signature schemes and general NP languages. Secondly, we develop a compiler that transforms any signature scheme with a subliminal channel into an adaptor signature scheme for general NP languages using circuit-private fully homomorphic encryption. Signatures with subliminal channels enable the encoding of witnesses in the signing randomness, and include randomness-recoverable schemes like Schnorr, ECDSA, CL, BBS, as well as salted versions of deterministic signatures schemes like BLS and RSA. Both constructions achieve a novel property called statement truth privacy, which guarantees that a buyer learns nothing about the underlying statement, not even its truth, unless the protocol successfully completes.

In this work, we study the communication complexity of constant-round MPC with guaranteed output delivery (GOD) in Minicrypt. We construct the first MPC protocol in this setting with linear communication complexity of $O(|C|n\kappa+Dn^3\kappa^3+W_I{\sf poly}(n,\kappa))$ bits under the assumption of a random oracle, where $|C|$ is the circuit size, $D$ is the circuit depth, $W_I$ is the number of input wires, and $\kappa$ is the security parameter. In comparison, the previously best-known construction with linear communication ($O(|C|n)$), presented by Goyal et al. (CRYPTO 2020), requires $O(D+n^2)$ round complexity. When targeting $O(D)$ round complexity, the best-known result by Agarwal et al. (ASIACRYPT 2024) still requires $O(|C|n^3)$ communication complexity. More communication is needed to achieve constant round complexity, even with non-black-box use of the underlying cryptographic primitives.

Blind signatures and multi‑signatures are well‑known primitives, but blind multi‑signatures (BMS), which combine both these primitives, were only recently formalized by Karantaidou et al (CCS'24). A BMS scheme allows a user to obtain a compact signature on a common hidden message from a group of signers such that even if the signers collude, they cannot learn the message or link the final signature to any particular interaction. In this paper, we introduce BMuSig2, a 2-round concurrently secure blind multi-signature scheme whose signatures and verification match standard Schnorr signatures. This design enables systems using Schnorr signatures to adopt BMuSig2 as a drop-in replacement, requiring changes only to the issuance phase, while leaving verification unchanged. BMuSig2 builds on MuSig2 multi-signatures (CRYPTO’21) and integrates techniques from a recent blind signature scheme (CRYPTO’24) that leverages non-interactive zero-knowledge (NIZK) arguments and public-key encryption (PKE) to achieve concurrent security. We formally prove the security of BMuSig2 by relying on the unforgeability of MuSig2 and the security of the underlying NIZK and PKE components. We also provide a proof-of-concept implementation to demonstrate its practical efficiency.

As machine learning increasingly moves to edge devices, model owners must trust predictions produced on devices and inputs outside their direct control. This trust is challenged by adversarial inputs, where carefully crafted perturbations can induce incorrect predictions. Existing black-box defenses can detect such inputs using microarchitectural signals, but provide no privacy-preserving mechanism for a remote model owner to verify the detection outcome. In this work, we introduce VERA, a framework for verifiable and privacy-preserving adversarial detection at the edge. VERA combines lightweight Hardware Performance Counter (HPC) monitoring with Zero-Knowledge Range Proofs (ZKRPs). Adversarial perturbations can alter internal activation patterns and consequently the microarchitectural behavior of inference, which can be captured through HPC measurements. Rather than revealing these potentially sensitive measurements, VERA allows an edge device to prove that a committed HPC value lies within a calibrated benign range without disclosing the value itself. This avoids the overhead of general-purpose zk-SNARKs and enables lightweight verification on resource-constrained devices. We formalize VERA as a black-box framework that can combine an HPC-based adversarial detector with an interactive ZKRP, which can also be made non-interactive using the Fiat--Shamir transform. We evaluate VERA against multiple adversarial attacks on MNIST and CIFAR-10. Our results show millisecond-scale verification overhead, with proof-generation costs amortizable across batches of inferences. To the best of our knowledge, VERA is the first framework to provide privacy-preserving cryptographic evidence that an edge inference exhibits microarchitectural behavior within a calibrated benign regime.

We study those $(n,n)$-permutations, and more generally those balanced $(n,m)$-functions, whose component functions all admit a derivative equal to constant function 1 (this property itself implies balancedness). We call these functions quadratic-like permutations (resp. quadratic-like balanced functions) since all quadratic balanced functions have this property. We show that all Feistel permutations, all crooked permutations and (more generally) all balanced strongly plateaued functions have this same property and we observe that the notion is affine invariant. We also study in each of these classes and in the class of quadratic-like APN permutations the "reversed" property that every derivative in a nonzero direction has a component function equal to constant function 1, and we show that this property can be satisfied only if $m\geq n$. We also show that all the quadratic-like power permutations $F(x)=x^d$, $x\in \mathbb F_{2^n}$ must be quadratic, which generalizes a well-known similar result on power crooked functions. We give several constructions of quadratic-like permutations and balanced functions outside the three classes of quadratic balanced functions, permutations affine equivalent to Feistel permutations and crooked permutations. We characterize the property by the Walsh transform.

This paper introduces Neo, a new lattice-based folding scheme for CCS, an NP-complete relation that generalizes R1CS, Plonkish, and AIR. Neo's folding scheme can be viewed as adapting the folding scheme in HyperNova (CRYPTO'24), which assumes elliptic-curve based linearly homomorphic commitments, to the lattice setting. Unlike HyperNova, Neo can use “small” prime fields (e.g., over the Goldilocks prime). Additionally, Neo provides plausible post-quantum security. Prior to Neo, folding schemes in the lattice setting, notably LatticeFold (ePrint 2024/257), worked with constraint systems defined over a cyclotomic polynomial ring. This structure allows packing a fixed batch of constraint systems over a small prime field into a single constraint system over a polynomial ring. However, it introduces significant overheads, both for committing to witnesses (e.g., the commitment scheme cannot take advantage of bit-width of values), and within the folding protocol itself (e.g., the sum-check protocol is run over cyclotomic polynomial rings). Additionally, the required ring structure places restrictions on the choice of primes (e.g., LatticeFold is not compatible with the Goldilocks field). Neo addresses these problems, by drawing inspiration from both HyperNova and LatticeFold. A key contribution is a folding-friendly instantiation of Ajtai's commitments, with "pay-per-bit" commitment costs i.e., the commitment costs scale with the bit-width of the scalars (e.g., committing to a vector of bits is $32\times$ cheaper than committing to a vector of $32$-bit values). This scheme commits to vectors over a small prime field. It does so by transforming the provided vector into a matrix and committing to that matrix. We prove that this commitment scheme provides the desired linear homomorphism for building a folding scheme. Additionally, like HyperNova, Neo runs a single invocation of the sum-check protocol, where in HyperNova it is over the scalar field of an elliptic curve and in Neo it is over an extension of a small prime field.

We construct the first folding scheme that simultaneously achieves six desirable properties: plausible post-quantum security, pay-per-bit commitment costs, field-native arithmetic (the sum-check and norm checks run purely over a small field), support for general (non-SIMD) constraint systems, small-field support (e.g., Goldilocks), and low recursion overheads. No existing scheme satisfies all six: group-based schemes (e.g., HyperNova) lack post-quantum security and are tied to large elliptic-curve fields; lattice-based schemes (e.g., LatticeFold) require expensive ring arithmetic, lose pay-per-bit costs, and impose SIMD constraints; and hash-based schemes (e.g., Arc) incur large verifier circuits. We present two lattice-based folding schemes for CCS, an NP-complete relation generalizing R1CS, Plonkish, and AIR, called Neo and SuperNeo. Neo satisfies five of the six properties but requires SIMD constraint systems; SuperNeo removes this restriction and satisfies all six. SuperNeo also natively supports CCS relations over arbitrary extension fields of the field underlying the Ajtai commitment, without relying on an NTT embedding. Both run a single invocation of the sum-check protocol over a small field extension and achieve pay-per-bit costs via new folding-friendly instantiations of Ajtai commitments under the Module-SIS assumption. At the core of our constructions are two new norm-preserving embeddings of field vectors into ring vectors that respect an evaluation homomorphism required for folding. We also introduce interactive reductions, a framework that generalizes reductions of knowledge and enables modular security proofs for composed lattice-based protocols.

We present Symplex, a pairing-based zkSNARK for R1CS that preserves the syntax of Groth16: a $2G_1{+}1G_2$ proof, and a verifier with three pairings and one public-input multi-scalar multiplication (MSM), while {\it strictly reducing prover cost}. For constraint count $n$, wire count $m$, public-input count $\ell$, and $\kappa=\min\{n,m+1\}$, Symplex's prover uses four FFTs of size $n$ rather than the six of our coset-Lagrange Groth16 comparator, and its larger $G_1$-MSM has width $m+n-\ell+4$ rather than the adaptively based Groth16 width $2\kappa+m+n-\ell+3$. The matched Groth16 prover derives three length-$n$ vectors from the R1CS instance, converts each between coefficient and evaluation form, and commits the quotient with a size-$n$ coset-Lagrange column, resulting in six FFTs in total. Its usual monomial quotient column has one fewer CRS element but requires a final inverse FFT. Symplex instead uses the partial-fraction techniques of Jutla, Nema, Roy (EuroCrypt 2026) allowing the output-wire selector polynomials to be precomputed into the per-wire CRS bundles during setup. So, only the left- and right-wire vectors require FFT-based processing at proving time. The verifier is unchanged (three pairings, one public-input MSM). On a BLS12-381 prototype of Symplex that shares sparse R1CS, FFT, and pairing code with Groth16, a Circom circuit chaining SHA-256 ten times gives a $1.84\times$ prover speedup with online verification at $\approx 2.6\,\mathrm{ms}$ for both schemes. The uniform algebraic extraction argument, perfect completeness, and perfect zero-knowledge are machine-checked in Lean~4. Polymath (Lipmaa, CRYPTO 2024) and PARI (Dellepere, Mishra, and Shirzad, USENIX Security 2026) shrink the proof using a squared R1CS arithmetization. Polymath proves soundness in the AGMOS model, and PARI does not provide zero-knowledge in the stated construction. Symplex keeps Groth16's proof shape and standard R1CS arithmetization, and is proved knowledge-sound in the standard Generic Group Model.

Zero-knowledge proofs of set membership underpin privacy-preserving constructions such as ring signatures and anonymous credentials. Existing succinct constructions rely mainly on the Fiat--Shamir transform in the Random Oracle Model (ROM), while standard-model non-interactive proofs from post-quantum assumptions remain either generic and inefficient or asymptotically compact yet concretely impractical. A key obstacle is that existing lattice-based zero-knowledge systems operate over a single ambient modulus, forcing heterogeneous components to be homogenized, inflating parameters and weakening reductions. We introduce the first \emph{compact lattice-based NIZK arguments for set membership in the standard model} with proof size logarithmic in the set cardinality. Our construction matches the logarithmic proof size of accumulator-based ROM constructions while achieving post-quantum security without random oracles. The main technical ingredient is a new trapdoor $\Sigma$-protocol supporting linear relations modulo multiple heterogeneous moduli, allowing such relations to be handled at their native moduli without homogenization. This yields a modular approach to compact proofs compatible with lattice accumulators. As an application, we construct lattice-based ring signatures of size $O(\log R)\cdot \widetilde{O}(\lambda^{2})$ bits, improving the dependence on the security parameter $\lambda$ quadratically over the plain-model construction of Chatterjee et al. (CRYPTO~2021) while retaining optimal logarithmic dependence on the ring size $R$. Our construction is in the CRS model, which partly enables this improvement. The scheme achieves statistical anonymity and unforgeability under standard Module-LWE and Module-SIS assumptions. We also develop two additional tools of independent interest: (i) a generalized Merkle-tree accumulator over module lattices with base-$B$ decomposition, enabling finer efficiency--assumption trade-offs; and (ii) a message-binding technique that removes the need for costly lattice one-time signatures in standard-model ring signatures.

Spartan is a SNARK for R1CS that can be instantiated with any multilinear polynomial commitment scheme. We instantiate Spartan over a binary field, using Ligerito as the commitment scheme along with the ring-switching technique of Diamond and Posen; we refer to the instantiation as BinarySpartan. It is transparent, so it requires no trusted setup, and it provides polylogarithmic-sized proofs. Its security rests on a hash function, so it is plausibly post-quantum secure. We apply well-known optimizations to Spartan and sum-check. We implement and evaluate BinarySpartan end to end. On a MacBook Pro M4 Max (using only its 12 performance cores, and without GPU/Metal acceleration), BinarySpartan proves BLAKE3 at 872,000 hashes/second, SHA-256 at 401,000 hashes/second, and Keccak-f at 287,000 permutations/second, including witness generation. All three clear the 200,000 hashes/second rate proposed as sufficient for a post-quantum Ethereum transition, as well as the roughly 37,000–180,000 hashes/second a possible post-quantum Bitcoin transition would require. At comparable security, BinarySpartan is 16.3–37.8× faster than Plonky3, 6.3–15.7× faster than Binius64, and 4.0× faster than Hashcaster, which only supports Keccak. On all three hash functions, BinarySpartan’s peak throughput matches or exceeds that of Flock, the prior state-of-the-art system. On BLAKE3 and Keccak, BinarySpartan also reaches those rates on far less memory: Flock needs 1.9× and 5.3× more to reach its own best rates. We also evaluate BinarySpartan on the Ethereum Foundation’s client-side proving benchmark, where it proves a single SHA-256 of a 2 KiB message in 6.2 ms, the fastest in the suite and 4.2× faster than Flock.

Batch encryption enables a holder of the secret key to publish a succinct pre-decryption key for a set of ciphertexts, such that exactly that set can be decrypted while other ciphertexts remain secret. Existing constructions either rely on epochs or, when epochless, suffer from large public parameters (quadratic in the batch size) and are vulnerable to censorship. In this work, we present an epochless, censorship-resistant batch encryption scheme with linear-sized public parameters, constant-sized pre-decryption keys and ciphertexts, and efficient batch decryption. Our construction extends the partial fraction techniques of Jutla, Nema, and Roy's threshold encryption scheme: we exploit partial fraction decomposition such that publishing a single group element as the pre-decryption key lets the decryptor decrypt all ciphertexts in the batch. We prove CCA security of our scheme, and show how to thresholdize it. Our results directly benefit applications such as encrypted mempools for MEV mitigation and time-lock encrypted storage.

Securely shuffling a secret-shared list is a vital sub-protocol in numerous applications, including secure sorting, secure list merging, secure graph processing, oblivious RAM, and anonymous broadcast. We demonstrate how to convert the folklore constant-round protocol for secure shuffling, which employs a delegated Fisher-Yates shuffle using rerandomizable encryption, into a maliciously secure constant-round protocol. This gives the first ever protocol that has linear end-to-end time and communication for a two-party secret-shared shuffle with malicious security. We prove the security of our protocol under the ``linear targeted malleability'' assumption on the homomorphic encryption system, as well as the natural assumptions of efficient ciphertext validity checks and rerandomizability. We also introduce a novel assumption, which we call weak predicability, and show that it is sufficient for security.

Partial fraction decomposition is a fundamental technique in mathematics where products of rational functions can be expressed as sums of fractions. While rational functions have been used in various cryptographic constructions, their rich algebraic structure has not been systematically explored as a direct foundation for building cryptographic primitives. In this work, we describe and exploit two key properties of partial fraction decomposition: (1) the decomposition property itself, which enables efficient set membership testing, and (2) a novel linear independence property arising from the non-singularity of Cauchy matrices, which enables threshold cryptography. We present two main applications. First, we construct a key-value commitment scheme where a dictionary is represented as a linear combination of partial fractions. Our scheme achieves constant-size commitments (a single group element) and proofs, supports homomorphic updates enabling stateless operation, and provides efficient membership and non-membership proofs through simple pairing equations. We also introduce Credential-based Key-Value Commitments, where keys are registered via Boneh-Boyen signatures, enabling applications in permissioned settings. Second, we construct a dynamic threshold encryption scheme leveraging the linear independence of partial fraction products. Our scheme achieves compact ciphertexts, supports public preprocessing of public keys to a succinct encryption key, enables dynamic threshold selection at encryption time, and provides robustness through share verification without random oracles. In particular, we achieve the shortest CPA-secure ciphertext size of 3 group elements, given logarithmic size preprocessed encryption key. We prove security of our constructions in the standard model under new $q$-type assumptions and establish their generic hardness in the generic bilinear group model. Our work demonstrates that working directly with the algebraic structure of rational fractions, rather than converting to polynomial representations, yields elegant and efficient cryptographic constructions with concrete advantages over prior work.

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

The 25 year-old NTRU problem is an important computational assumption in public-key cryptography. However, from a reduction perspective, its relative hardness compared to other problems on Euclidean lattices is not well-understood. Its decision version reduces to the search Ring-LWE problem, but this only provides a hardness upper bound. We provide two answers to the long-standing open problem of providing reduction-based evidence of the hardness of the NTRU problem. First, we reduce the worst-case approximate Shortest Vector Problem over ideal lattices to an average-case search variant of the NTRU problem. Second, we reduce another average-case search variant of the NTRU problem to the decision NTRU problem.

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

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

Message authentication codes (MAC) are ubiquitous and are considered to be the most important tool employed to ensure authenticity of messages in the symmetric key setting. In this work, we aim to empower MACs with a newly added functionality of updatablility, i.e., the goal is to construct a MAC scheme where the authentication tag for a message can be updated with every update to the message without recomputing the tag for the entire message. Such a functionality can be useful in several scenarios, primarily where the storage of a frequently changing large message is delegated to an un-trusted server. In such a scenario it may be infeasible for an user to download the entire message and recompute the tag for every update. Bellare et al. [CRYPTO'94, STOC'95] introduced a new class of history-free updatable MACs, which can update a message tag without requiring any previous information. However, their update algorithm takes the entire document as an input, which can be impractical in many real-world scenarios. We introduce a new class of MACs called updatable message authentication codes (UdMACs). An UdMAC allows an existing message tag to be updated using only the previous tag, the message update, and a small state, without accessing the previous message. We systematically develop UdMACs, provide syntax for UdMAC, propose formal security notion. We then present two constructions: $\concatu$ and $\xoru$, which support two distinct message updates, namely, concatenation and xor difference. We analyze both the constructions in details and prove security of the construction in the newly proposed security model.

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

Post-election Risk-Limiting Audits (RLAs) provide statistical guarantees of election outcomes by hand-counting randomly selected paper ballots. However, standard RLAs assume that ballots remain unaltered in storage between election day and the audit, but voters cannot verify this assumption. Prior frameworks, such as VAULT (E-VOTE-ID 2019), attempt to make the audit process verifiable, but they require the public to trust the Election Authority (EA) to honestly sample ballots at random and correctly interpret the voters' choices into cryptographic commitments. Furthermore, they are typically ballot-level, requiring a 1-to-1 mapping between individual paper ballots and digital records. The EA also needs to interactively open commitments during the audit. To address these limitations, we propose the first verifiable batch-level RLA scheme, which shifts the trust anchor from the EA directly to the voter and operates on groups of ballots (batches) to eliminate individual tracking hurdles. Our scheme introduces a peel-and-vote paper ballot design with removable flaps containing pre-printed cryptograms. A voter selects a candidate by removing the corresponding flap, and retains the flap as a receipt, while the same cryptogram printed on the receipt is also published on a bulletin board. In our scheme, a batch contains a group of cryptographically related ballots that are randomly distributed across the precincts before the election. Once all cryptograms in a batch are published, anyone can independently compute the tally for that batch, achieving a self-tallying property. Intuitively, our scheme transforms a national-scale election into many smaller self-tallying elections: one for each batch. Based on historical US election data, we show that when the ballot loss rates remain below 0.5%, the scheme enables tally verification for 61% of randomly selected ballots with a batch size of 100, or 37% with a batch size of 200. These figures are substantially higher than the 0.01-0.3% sampling coverage typically achieved in RLAs. This improvement stems from the fact that auditing is built directly into the paper ballot design in our scheme as an always-on feature, rather than being treated as an optional manual post-election process.

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

A common pipeline of cryptographic research is: a theory paper asks an interesting question which triggers a line of works; then the problem remains dormant until technology catches up and makes the problem potentially relevant for practice; this triggers a renewed interest which at times pushes the originally theoretical ideas to practice. Several highly influential ideas have followed this pipeline: e.g., the original work on Oblivious RAMs by Goldreich and Ostrovsky [STOC'87\&90], polynomial commitments by Kate, Zaverucha, and Goldberg [ASIACRYPT'10], and many others. A problem that shows early signs of this pattern is early-stopping Byzantine Agreement (esBA): esBA protocols whose round complexity depends on the number $f$ of {\em actually} faulty parties rather than on (an upper bound on) the number $t$ of {\em potentially} faulty parties. Although it is fair to say that esBA protocols are not (yet) within the practical realm, their potential to improve large scale distributed systems like blockchain ledgers has fueled a number of recent novel results pushing the envelope in esBA feasibility (e.g., Loss and Nielsen [EUROCRYPT'24] and Elsheimy, Loss, and Papamanthou [ASIACRYPT'24]). The original starting point of this work has been to advance on the above feasibility questions. But as is common for problems following this trajectory, renewed interest often comes with observations about issues in the assumed definitions and models. Interestingly, our investigation revealed an issue with how the existing literature has been computing the round complexity of such protocols, which yields (previously unobserved) inconsistencies in the literature of esBA and more generally of synchronous protocols. In a nutshell, the inconsistencies stem from the fact that the last round of several esBA protocols has parties terminating as soon as they send a message to other parties, i.e., they don't need to wait to receive messages sent to them in that round. So, should we count this as an extra round or not? As we observe, different works give different answers to this question, and the answer one adopts affects the claimed tightness of the corresponding bounds. Building on the above observation, our work proposes a fine-grained manner of counting synchronous rounds that is both intuitive and resolves these inconsistencies. In a nutshell, our counting distinguishes between rounds in which parties might both send and receive messages, and rounds in which parties only need to send messages. Examining the existing literature through the lens of this round-counting methodology exposes gaps and new open questions in the relevant literature. We resolve these gaps and extend the landscape by several new results.

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

Miner extractable value (MEV) in automated market makers allows block builders to profit from transaction ordering and injected trades, imposing costs on users and contributing to builder centralization. We introduce Otter (Optimal Truthful Trading with Excess Redistribution), a two-asset batch AMM that achieves provable MEV resilience when the consensus layer provides censorship resilience and block space is uncongested. In particular, Otter makes truthful behavior a dominant strategy for both users and builders. Consequently, a builder cannot profit from strategic deviations, including reordering bids or injecting sybil bids. These guarantees continue to hold even when the builder is itself a trader with intrinsic value. Moreover, we show that our mechanism maximizes social welfare, in a strong sense, within a natural class of mechanisms satisfying the desired game-theoretic properties. To achieve these guarantees, we introduce a new paradigm called surplus redistribution, which provably prevents residual surplus from being captured as MEV by redirecting it to the broader community. Specifically, the pool's output tokens need not be distributed entirely among the users in the current batch. Instead, any residual surplus may be transferred, for example, to a smart contract governed by the decentralized community. The accumulated surplus can subsequently be used to benefit community members in ways that preserve the mechanism's game-theoretic guarantees --- for example, by subsidizing traders' transaction fees, rewarding liquidity providers, or returning assets to the pool to reduce price impact and slippage for future traders. Our approach relies on the underlying consensus layer to provide censorship resilience. We motivate the necessity of this assumption through an impossibility result showing that the desired game-theoretic guarantees become unattainable when the builder is additionally allowed to censor transactions. Thus, our results also provide a mathematically formal demonstration of how consensus-level security guarantees can fundamentally expand what is achievable at the application (i.e., smart-contract) layer. Finally, we establish additional results characterizing the builder fee structures compatible with our desired incentive guarantees.

Evaluating the hardness of the Shortest Vector Problem (SVP) is essential for selecting secure parameters in lattice-based cryptography. The fastest current SVP solvers are based on variants of G6K, but their large memory consumption remains a major bottleneck, making high-dimensional executions difficult. A common strategy for alleviating this memory bottleneck is strong basis reduction preprocessing before a sieve-based algorithm. This strategy can solve SVP instances in higher dimensions than standalone G6K under the same memory constraints, but the time required for basis reduction becomes a major issue. ProPnjBKZ, a fast basis reduction algorithm optimized by Wang et al., is currently used as a promising preprocessing method for solving high-dimensional SVP instances. In this paper, we identify that, in the ProPnjBKZ-based SVP-solving pipeline, memory resources can remain underutilized during the preprocessing phase, since ProPnjBKZ requires less memory than the subsequent high-dimensional sieving process. Based on this observation, we propose AH-BKZ, which exploits such unused computational resources by asynchronously running multiple SVP oracles, thereby accelerating basis reduction. Our experiments show that, compared with ProPnjBKZ-based preprocessing, AH-BKZ reduces the overall runtime by up to 23.1% and by 18.6% on average among successful runs for dimensions 124-148 under comparable peak memory constraints. Moreover, in a supplementary experiment conducted in a larger computational environment, AH-BKZ set new solving records for dimension 163 in the TU Darmstadt SVP Challenge and for dimension 164 in the Ideal Lattice Challenge.

BOGI-based ciphers extend the design space of GIFT by combining 4-bit S-boxes with bit permutations satisfying the ``Bad Output must go to Good Input'' principle. Prior work reduced this space to 41,472 parameter representatives, but did not determine whether their complete differential and linear trail spaces were distinct. We define DC/LC-equivalence in terms of weight-preserving bijections between the differential and linear trail sets of two ciphers for an arbitrary number of rounds, and give sufficient conditions based on permutation characteristics and trail reversal. For each pair of mixing permutations and each 4-bit permutation, we decide exactly whether the required initial word permutation exists. The relations generated by these transformations and trail reversal partition the 41,472 ciphers into 864 classes of size 48 for BOGI-64 and 5,184 classes of size 8 for BOGI-128. Using the BOGI-128 classification, we perform differential and linear best-trail searches through round 20, completing both searches for 5,081 classes. These results and additional threshold decisions show that the earliest round at which both best-trail weights reach 128 bits is round 19, attained by at least 59 classes. The class containing GIFT-128 reaches both thresholds at round 22. Thus, at least 59 classes reach both thresholds three rounds earlier than the GIFT-128 class. We also compare selected BOGI-64 and BOGI-128 instances with GIFT in hardware and software. The resulting security and implementation data can support component selection in future GIFT-based primitives.