Papers updated in last 183 days (Page 15 of 2708 results)
Three-Round Weak Non-Malleable Zero-Knowledge Argument
Non-malleable zero-knowledge argument(NMZK) is a strong notion of zero-knowledge argument that ensures security against man-in-the-middle(MIM) attacks. While three-round constructions exist for various weak zero-knowledge arguments under standard assumptions, all known (weak) NMZK protocols in the plain model have required at least four rounds.
In this work, we construct the \emph{first three-round weak non-malleable zero-knowledge argument} under standard cryptographic assumptions. Our protocol satisfies weak zero-knowledge and $\epsilon$-non-malleability, where the latter allows an $\epsilon$ probability gap between the MIM experiment and the stand-alone experiment for any polynomial inverse $\epsilon$. Our construction relies only on well-established primitives, such as the existence of two-message oblivious transfer protocols and delayed-input WI arguments, non-interactive commitments, and circuit-privacy fully homomorphic encryptions.
Free Linear Online Phase for Secure Multiparty Shuffle
Shuffling is a fundamental operation in secure multiparty computation (MPC), yet existing maliciously secure protocols for shuffling $m$ elements among $n$ parties require at least $n^2m$ online communication and computation, compared with $O(nm)$ in the semi-honest additive-sharing setting.
We formalize and extend the \emph{permute-in-turn paradigm}, which constructs MPC shuffles from permutation protocols, capturing the methodology adopted in most prior works. Our generic transformations achieve semi-honest or malicious security with only $O(C_{\mathrm{BC}}+nm)$ online communication and computation, where $C_{\mathrm{BC}}$ is the cost of one parallel broadcast
(allowing unanimous abort).
Our transformations are \emph{for free} in two senses:
they yield linear online phases without
exceeding the overall asymptotic cost of applying $n$ MPC permutations,
while \emph{freeing} the online phase of the shuffle protocol
from dependence on the MPC permutation protocol.
This decoupling allows future work to optimize permutation protocols independently
while benefiting all MPC shuffle protocols that follow the paradigm.
Instantiated with additive and Shamir secret sharing, our transformations yield the first maliciously secure shuffles with $O(C_{\mathrm{BC}}+nm)$ online cost, improving previous bounds of $O(Bn^2m)$ and $O(n^2m\log m)$, respectively, where $B$ is a cut-and-choose parameter. We formally prove semi-honest and universally composable (UC) security for the corresponding transformations. For $m=2^{12}$ and $n=15$, our prototype achieves over $60\times$ lower online runtime and $120\times$ lower online communication than prior work, with only a $1.3\times$ increase in total runtime.
A RAM-Efficient Implementation of Falcon
We present a RAM-efficient implementation of Falcon: RAM usage has shrunk to about 11 kB, down from about 31 kB in the previous implementation of Falcon-512. This code is furthermore faster on Arm Cortex M4, with average signature generation cost down to 13.45 million cycles. Optimization techniques include a novel variant of the FFT, replacement of some floating-point operations with modular integer computations, delayed addition of input within the Fast Fourier sampling process, and an alternate signature reassembly process. More than half of the floating-point operations have been removed. The resulting implementation is now small enough to allow use in small embedded systems such as smart cards.
Attacking an RSA-like Cryptosystem Using Continued Fractions and Lattices
Let $N = pq$ be the product of two balanced primes. Cotan and Te\c seleanu (2023) introduced a family of RSA-like cryptosystems defined by $ed - k(p^n - 1)(q^n - 1) = 1$, where $n \geq 1$, encompassing classical RSA ($n=1$) and the Elkamchouchi–Elshenawy–Shaban variant ($n=2$). We present a new attack for $n=3$ that integrates continued fractions with lattice-based methods, naturally extending previous results for $n = 1, 2, 4, 6$.
A Generalized Wiener-type Attack Against a Family RSA-like Cryptosystem
Let $N = pq$ be the product of two balanced prime numbers $p$ and $q$. In 2023, Cotan and Te\c seleanu introduced a family of RSA-like cryptosystems based on the key equation $ed - k(p^n - 1)(q^n - 1) = 1$, where $n \geq 1$. Note that when $n = 1$, we obtain the classical RSA system, while $n = 2$ yields the variant proposed by Elkamchouchi, Elshenawy, and Shaban. In this paper, we present a novel attack that combines continued fractions with lattice-based methods for the case $n = 6$. This represents a natural continuation of previous research, which successfully applied similar techniques for $n = 1, 2, 4$.
A Generalized Wiener-type Attack Against a Family RSA-like Cryptosystems
Let $N = pq$ be the product of two balanced prime numbers $p$ and $q$. In 2023, Cotan and Te\c seleanu introduced a family of RSA-like cryptosystems based on the key equation $ed - k(p^n - 1)(q^n - 1) = 1$, where $n \geq 1$. Note that when $n = 1$, we obtain the classical RSA scheme, while $n = 2$ yields the variant proposed by Elkamchouchi, Elshenawy, and Shaban. In this paper, we present a novel attack that combines continued fractions with lattice-based methods for the case $n = 2^i$, where $i > 2$ is an integer. This represents a natural continuation of previous research, which successfully applied similar techniques for $n = 1, 2, 4$.
General Review of Hash-Based Signatures
The advent of quantum computing threatens the security assumptions underpinning classical public-key cryptographic algorithms such as RSA and ECC. As a response, the cryptographic community has focused on developing quantum-resistant alternatives, with hash-based signature schemes emerging as a compelling option due to their reliance on well-understood hash functions rather than number-theoretic hardness assumptions. This paper presents a comprehensive review of hash-based signature schemes, covering the foundational building blocks (Lamport signatures, Winternitz one-time signatures, Merkle trees, and FORS) as well as the three standardized constructions: XMSS (RFC 8391), LMS (RFC 8554), and the stateless SPHINCS+ (FIPS 205 / SLH-DSA). A systematic comparison highlights the trade-offs between statefulness, signature size, and implementation complexity. Furthermore, the paper analyzes several notable cryptanalytic attacks, examining for each the attack model, applicable constructions, complexity, and known countermeasures. By discussing both their strengths and vulnerabilities, this work provides a unified reference for understanding the design landscape of hash-based signatures as practical candidates for post-quantum digital signatures.
NetAdapt: Network-Adaptive Hybrid Protocol Assignment for PPML
The widespread use of machine learning on sensitive data makes Privacy-Preserving Machine Learning (PPML) essential for data confidentiality. Current state-of-the-art PPML systems employ hybrid protocol designs to evaluate various operators to achieve better performance; yet, existing hybrid approaches adopt fixed protocol assignments without considering the deployment setting, resulting in inefficiencies across diverse network environments, such as LANs and WANs. To address this, we introduce NetAdapt, a cost-model-driven framework that automatically assigns FHE and MPC protocols to optimize inference efficiency under varying network conditions, by designing a predictive cost model based on the dialect of the Multi-Level Intermediate Representation (MLIR)’s Tensor Operator Set Architecture (TOSA), and an ILP-based solver for managing the cross-protocol conversion while dynamically updating FHE costs based on homomorphic multiplication depth. Experimental results demonstrate that NetAdapt delivers $6.68\times$ to $12.92\times$ improvements in inference running time compared to state-of-the-art solutions, allowing network-agnostic PPML.
HAWK with Hint: Algebraic Key Recovery from Side-Channel Leakage
We investigate how partial physical leakage can be amplified through public algebraic relations, using HAWK as a concrete case study of implementation security in an algebraically structured post-quantum signature scheme. HAWK is a lightweight, floating-point-free lattice-based signature scheme whose discrete Gaussian sampler can expose side-channel information during signing. We formalize such leakage as HAWK with Hint and study full-coefficient, exact-sign, and noisy-sign leakage. Our polynomial-time recovery algorithms combine sampler hints with public signing information and HAWK's Gram-matrix public-key structure, showing that complete sampler-output recovery is not necessary for full key recovery.
For HAWK-1024, we obtain the following results under the stated threat models. With full coefficient leakage, a single signature suffices for secret-key recovery by directly solving the induced linear system. On the HAWK-1024 reference implementation, we identify all 2,048 coefficient-sampler invocations in each of 14 measured signing traces, extract all 28,672 coefficient signs without error, and recover the fixed key using the Category II attack. In separate controlled experiments over 100 independently generated keys, Category II achieves 100% success using 14 exact-sign signatures in approximately 157 seconds. Under the independent sign-error model, Category III achieves 100% success using 420 signatures at a 10% error rate and 13,397 signatures at a 40% error rate. The latter setting requires approximately 178 seconds. These results show that coarse and even erroneous sampler leakage can become sufficient for full key recovery when combined with HAWK's public algebraic structure.
Impossible Polytopic Attack Revisited: Low-Data Distinguishers and Attacks
Block ciphers including several variants of the well-known \textsf{AES}, the newly proposed tweakable block cipher \textsf{Deoxys-BC} (standardized by ISO/IEC and renamed Deoxys-TBC), and \textsf{ChiLow} (EUROCRYPT 2025) adopt key sizes larger than their block sizes. These designs offer security higher than the block size. This paper evaluates the security of such ciphers by revisiting the Impossible Polytopic Attack (\ipa{}, proposed by Tyge Tiessen at EUROCRYPT 2016). We show that \ipa{} can build longer-round distinguishers, enabling attacks on more rounds. Moreover, the attack is applicable under the known-plaintext (KP) setting. Towards this end, we first formalize the distinguisher from Tiessen’s original work and establish a generic framework for distinguisher construction. We further propose two novel methods to lower the corresponding construction complexity. Moreover, we develop two dedicated key-recovery techniques, namely the plaintext‑grouping technique and the partition-guess-filter technique. The former allows cryptanalysis on more rounds of target ciphers, while the latter substantially lowers the overall attack complexity. Finally, we build the first framework for \ipa{}. We apply our method to the chosen-plaintext/ciphertext (CP/CC) and KP scenarios under the single-key setting. As a result, we obtain new distinguishers and attacks against \textsf{AES}, \textsf{Deoxys-BC}, \textsf{Joltik-BC}, \textsf{LED-128}, and \textsf{ChiLow-32}. Notably, 10-round attacks are constructed on \textsf{Deoxys-BC-384} and \textsf{Joltik-BC-192}. Compared with impossible differential attacks, which are closely related and extensively studied, the proposed results outperform such attacks by one round. Furthermore, a novel full-round attack on \textsf{ChiLow-32} is constructed under the KP setting, achieving the state-of-the-art attack with optimal data complexity and overall complexity.
A Formal Security Analysis of a MACsec Key Agreement Protocol Using Tamarin
MACsec Key Agreement (MKA) is the IEEE 802.1X key-management protocol used to establish and maintain Secure Associations for MACsec deployments. Although MKA is widely deployed, machine-checked analyses of its core key-agreement logic remain scarce. This paper presents a formal analysis of a simplified two-party MKA exchange using the Tamarin prover. We model the initial session establishment and a subsequent rekey round, and verify secrecy, authentication, agreement, ordering, and freshness properties. The analysis confirms these guarantees under a Dolev--Yao adversary when the pre-shared Connectivity Association Key (CAK) is not compromised. We also identify a structural weakness: a malicious or compromised Key Server can inject an arbitrary Secure Association Key (SAK) that the Server accepts. This finding clarifies the trust assumptions of MKA and motivates additional verification or binding mechanisms for partially trusted deployments.
Sparse Hermite Interpolation Method for Discrete-CKKS Functional Bootstrapping
Discrete CKKS is a promising approach for performing high-throughput homomorphic computations over encrypted discrete data. Although it relies on CKKS, an approximate FHE scheme, as the computation engine, discrete CKKS can achieve exact correctness. The core operation of discrete CKKS is functional bootstrapping, a mechanism which enables evaluating an arbitrary function over a bounded discrete domain by representing it as a lookup table and computing it as part of bootstrapping. Simultaneously, the same procedure enables reducing the input ciphertext noise using Hermite interpolation methods. This noise reduction feature is critical for both supporting arbitrary computations and improving the efficiency of their evaluation, by providing more noise budget between bootstrapping invocations.
In this paper, we first show that both state-of-the-art Hermite interpolation noise reduction methods by Bae et al. (ASIACRYPT'24) and Alexandru et al. (CRYPTO'25) have a limited noise reduction ability for distinct structural reasons. We then propose a new method that can efficiently overcome these limitations by using a CKKS-friendly *arbitrary-order* Hermite interpolation. We call this method "sparse" trigonometric Hermite interpolation because both constraints and coefficients have convenient sparsity properties, which allow us to achieve efficiency comparable to the fastest prior method by Alexandru et al., while attaining superior noise reduction. In the process, we develop a metric that measures the noise budget between consecutive functional bootstrapping invocations, and use it to compare all methods on equal footing. We implement our new method in OpenFHE and experimentally demonstrate its noise reduction advantage over prior methods.
On Publicly Verifiable Tokens in Group Signatures with Message-Dependent Opening
Group signatures (GSs; Chaum and van Heyst, EUROCRYPT 1991) are digital signatures that allow a signer to anonymously prove group membership, while still enabling a special authority, called the opener, to identify the signer when necessary. Group Signatures with Message-Dependent Opening (GS-MDO; Sakai et al., Pairing 2012) weaken the power of the opener by introducing another authority, the admitter, who issues a message-dependent token. In previous GS-MDO schemes, these tokens can be viewed as signatures. Therefore they can be publicly verified using the verification algorithm of the underlying signature scheme. However, no explicit notion of public verifiability for tokens, meaning the ability to publicly verify whether a token can be used for opening a group signature, has been defined so far. Clarifying this implicit security property is important for understanding the feasibility of GS-MDO. In this paper, we formally define public verifiability of tokens. We establish a proper relationship between verifying a token as a signature and verifying that the token can be used for opening, which typically requires the opener's secret key. We also show that the Ohara et al. pairing-based GS-MDO scheme (AsiaCCS 2013), the Libert et al. lattice-based GS-MDO scheme (ACNS 2016), and the Libert et al. pairing-based GS-MDO scheme (CT-RSA 2014) satisfy our definition, suggesting that our formalization is reasonable. Finally, we discuss how publicly verifiable tokens can be used to provide accountability for the admitter, enabling them to demonstrate that tokens have been honestly generated according to the token-generation algorithm.
Fast Difficulty Adjustment in Proof-of-Work Consensus
One of the main hallmarks of proof-of-work (PoW) consensus protocols is their ability to adjust the difficulty of the PoW, so that it accurately reflects the level of participation and hence maintains security in a setting where protocol participation is unknown and may over time change dramatically. Importantly, this enables the protocol to retain its fundamental characteristics (such as the regularity of dispensing new tokens) irrespectively of the number of parties running the protocol (also known as ``miners'') at any given time.
The speed with which difficulty can be adjusted is a fundamental feature of a blockchain protocol: The faster the rate with which the difficulty is adjusted, the more agile the protocol is in the face of fluctuating participation. In this work, we put forward, for the first time, a blockchain protocol that performs difficulty adjustment in constant time; prior provably secure designs only offered protocols with, at best, poly-logarithmic overhead for difficulty adjustment. Our construction is based on the parallel-chain approach and a new target recalculation function that adjusts mining difficulty making use of information from all chains in the past epoch via a novel application of approximate-agreement techniques that may be of independent interest.
Unbounded Broadcast and KP-ABE with Sublinear Ciphertext from Pairings
We present the first pairing-based unbounded broadcast encryption
and key-policy attribute-based encryption (KP-ABE) with sublinear
ciphertext size. Here, unbounded means set-up and the public
parameters do not impose a bound on the size of the broadcast set,
attribute length, or policy size.
- Our broadcast encryption scheme supports an unbounded number of users, and achieves
\[ |mpk| = O(1), |ct| = O(\sqrt{N}), |sk| = O(\sqrt{N})\]
where $N$ denotes an upper bound on the size of the broadcast set.
- Our KP-ABE supports boolean formula and span programs, and achieves
\[ |mpk| = O(1), |ct| = O(\sqrt{N}), |sk| = O(\sqrt{N} \cdot |f|)\]
where $N$ is the attribute length and $|f|$ the policy size.
We prove adaptive security for the broadcast encryption and
selective security for the KP-ABE,
based on the $k$-Lin assumption in the standard model without random
oracles.
Information-theoretic two-server PIR requires $(6-o(1))\log n$ bits of communication
We prove that every information-theoretic two-server private information retrieval scheme for $n$-bit databases requires $(6-o(1))\log n$ bits of communication. This improves on the $5$ of Wehner and de Wolf (ICALP 2005), who had raised the $4.4$ of Kerenidis and de Wolf (STOC 2003), who in turn had raised Mann's original $4$ (M.Sc.\ thesis, 1998). Our proof follows the quantum route of the earlier bounds: encode the database in a quantum state, recover an entry from enough copies of it, and apply Nayak's bound (FOCS 1999) on quantum random access codes. Previous proofs read that entry as a binary outcome with a small bias toward the correct answer, and pay the inverse square of that bias to amplify it. We instead allow a real-valued outcome whose mean is the correct answer, and pay only its second moment. The same readout strategy improves the other lower bounds of Wehner and de Wolf, for smooth codes and locally decodable codes. In particular, it drops the linearity assumption in the lower bounds of Goldreich, Karloff, Schulman, and Trevisan (CCC 2002) almost for free.
ALKAID: Accelerating Three-Party Boolean Circuits by Mixing Correlations and Redundancy (Full Version)
Secure three-party computation (3PC) with semi-honest security under an honest majority offers notable efficiency in computation and communication; for Boolean circuits, each party sends a single bit for every AND gate, and nothing for XOR. However, round complexity remains a significant challenge, especially in high-latency networks. Some works can support multi-input AND and thereby reduce online round complexity, but they require \textit{exponential} communication for generating the correlations in either preprocessing or online phase. How to extend the AND gate to multi-input while maintaining high correlation generation efficiency is still not solved.
To address this problem, we propose a round-efficient 3PC framework ALKAID for Boolean circuits through improved multi-input AND gate. By mixing correlations and redundancy, we propose a concretely efficient correlation generation approach for small input bits $N<4$ and shift the correlation generation to the preprocessing phase. Building on this, we create a round-efficient AND protocol for general cases with $N>4$. Exploiting the improved multi-input AND gates, we design fast depth-optimized parallel prefix adder and share conversion primitives in 3PC, achieved with new techniques and optimizations for better concrete efficiency. We further apply these optimized primitives to enhance the efficiency of secure non-linear functions in machine learning. We implement ALKAID and extensively evaluate its performance. Compared to state of the arts like ABY3 (CCS'2018), Trifecta (PoPETs'2023), and METEOR (WWW'2023), ALKAID enjoys $1.5\times$--$2.5\times$ efficiency improvements for boolean primitives and non-linear functions, with better or comparable communication.
PRISM: Efficient zkSNARKs for RNS-Based Homomorphic Encryption
Homomorphic Encryption (HE) enables computations on encrypted data without decryption, but it does not guarantee the integrity or correctness of the performed operations. To address this limitation, verifiable HE (vHE) has been proposed. However, achieving efficient vHE for RNS-based HE schemes (e.g., BFV/BGV/CKKS) remains challenging: While the Residue Number System (RNS) boosts performance of HE via multi-modulus ciphertext representations, it significantly complicates the cross-field consistency checks in vHE. We observe that existing vHEs for RNS-based HE suffer from at least one of the following limitations: they do not readily extend to the zero-knowledge setting (Atapoor et al., CiC 2024), incur linear proof size & verifier cost (Zhou et al., S&P 2025), or are designed for a modified HE scheme (Cascudo et al., Crypto 2025).
We present $\mathsf{PRISM}$, the first practical zkSNARK for standard RNS-based HEs. Our techniques are threefold: (1) a new cryptographic primitive called Multiple-Field Polynomial Commitment Scheme (MF-PCS) that efficiently prove the cross-field modulo relations, which is the key bottleneck in RNS-based HE verification; (2) a novel Polynomial Interactive Oracle Proof (PIOP) for (inverse) number theoretic transforms with $O(N)$ prover time and $O(\log N)$ verifier time in a model with an offline phase; (3) upgrading MF-PCS and PIOPs to achieve zero-knowledge with small overhead via Vector Oblivious Linear Evaluation (VOLE) correlations. We fully implemented $\mathsf{PRISM}$ and evaluated it against state-of-the-art schemes. Compared to Zhou et al. which has the fastest prover time, $\mathsf{PRISM}$ has $3.5\times$ slower prover time, but up to $7.8\times$ faster verifier time and $7.8\times$ smaller proof size. Compared to Atapoor et al. which has the smallest proof size, $\mathsf{PRISM}$ has $5.5\times$ larger proof size, but roughly $10.1\times$ faster prover time and $2.6\times$ faster verifier time.
Random Robust Secret Sharing with Perfect Privacy and its Applications
Secret Sharing schemes allow a dealer to distribute $n$ shares $s_1,\ldots, s_n$ of a secret $s$ so that any $t$ shares suffice to reconstruct the secret, while any $t-1$ shares reveal no information about $s$. In fact, schemes such as Shamir Secret Sharing satisfy a stronger guarantee called $(t\!-\!1)$-perfect privacy, meaning that for any subset $S \subseteq [n]$ with $|S| \le t-1$, the joint distribution $(s_i)_{i \in S}$ is uniformly distributed over its domain. This strong guarantee is essential for applications such as fuzzy password-authenticated key exchange (fPAKE) and conditional encryption --- a recent cryptographic primitive introduced to enable secure personalized password typo correction. Unfortunately, Shamir secret sharing is not robust: corrupted shares can prevent correct reconstruction or cause reconstruction of an incorrect secret. Existing robust secret sharing schemes address this issue but necessarily sacrifice perfect privacy. We introduce and construct Random Robust Secret Sharing with Perfect Privacy (RRSS), a new notion that preserves $(t\!-\!1)$-perfect privacy while providing robustness against random share corruptions. In our schemes, the secret is recovered with high probability even if an arbitrary subset of up to $n-t$ shares is independently corrupted at random. We demonstrate the utility of RRSS through two applications. First, we present the first practically efficient fPAKE construction that tolerates Hamming errors. Second, we obtain the first efficient conditional encryption scheme for arbitrary Hamming distances, improving upon prior work that achieved efficiency only for constant distances. We implement both constructions and empirically demonstrate their practicality.
How to prove more false statements: Fiat–Shamir limitations on (generated) R1CS
The Fiat--Shamir (FS) transformation is a technique that converts interactive protocols into non-interactive ones.
FS is secure in idealized models such as the random oracle model (ROM) (if the interactive protocol satisfies a condition known as state-restoration soundness).
It is known that there are protocols whose FS transformation is secure in the ROM, yet insecure when instantiated with any concrete hash function. Historically, these protocols were contrived (as in, they were designed so their FS transformation would be unsound).
Khovratovich, Rothblum and Soukhanov (CRYPTO 2025) showed that a class of natural (and practically deployed) protocols based on a protocol of Goldwasser, Kalai and Rothblum (JACM 2015) was also unsound when compiled with FS and any concrete hash function.
We extend the attack to a different class of protocols: those whose instances are generated by running a program.
This setting covers concrete trends in modern proof systems, in which the computation to be proven is described by a program (often adversarialy generated) which is then either compiled or autonomously converted into an instance of target relation such as rank-1 constraint satisfaction (R1CS). We show that, when the conversion process is "expressive enough", an adversary controlling the program code can break soundness of the non-interactive proof system.
The attacks generalize to a wide class of protocols: any protocol in which a cheating prover can prepare an accepting transcript before the statement is bound. We show that variants of the Spartan (CRYPTO 2020) and Aurora (EUROCRYPT 2019) proof systems for R1CS fall in this class.
Complementing the attacks, we formalize a mitigation: deriving the first Fiat--Shamir challenge from the generated statement, rather than from the program that generates it, provably reduces the soundness of the compiled protocol to that of the underlying protocol for the non-generated relation.
Additions, Multiplications, and the Interaction In-Between: Optimizing MPC Protocols via Leveled Linear Secret Sharing (Full Version)
Secure multiparty computation (MPC) enables distrusting parties in a distributed system to compute on their private inputs without compromising their privacy. For many secret-sharing-based approaches, including some of today's most efficient MPC protocols, there is a pattern where two shared values are locally multiplied into some intermediate representation that is immediately and interactively translated back into sharings of the product. The intermediate representation is often still a full-fledged but different secret sharing scheme. This has been used to efficiently compute dot products by computing the sum of all intermediate products and then interactively translating only the sum instead of translating each individual product. Beyond that, the intermediate representation or secret sharing scheme has mostly been seen only as a necessary interim step, leaving most of its potential untapped.
We change that by proposing the paradigm of leveled linear secret sharing, which allows dynamic switching between the original secret sharing and the previously only intermediate one more freely, while enabling arbitrary linear computations in any of the domains. Prior multiplications are split into a non-interactive multiplication that switches from one to the other secret sharing, and an interactive upgrade back to the original secret sharing domain. The upgrade now does not necessarily follow each multiplication immediately, but just needs to be placed somewhere before the next multiplication is computed, possibly upgrading the linear aggregation of many multiplications' results. We apply this idea to improve three-party computation on replicated sharings (CCS'16), n-party BGW-style protocols (STOC'88), and masked secret sharing protocols such as ABY2.0 (USENIX Security'21). We build a novel optimizer that optimally selects which gate of a circuit is evaluated in which domain. With that, we improve communication by 10-37% for many circuits. Furthermore, we implement our generalization for replicated sharing, measure run time improvements of mostly 10-26% in a LAN, and make a full implementation of the protocol and our novel optimizer publicly available.
One Proof to Rule Them All: Practical, Sublinear Verification for Actively Secure MPC on $\mathbb{Z}_{2^k}$ with Dishonest Majority and a Dealer (Full Version)
Towards bridging the gap between passively and actively secure multiparty computation (MPC), the use of sublinear distributed zero-knowledge (DZK) proofs gained popularity. Such proofs enable extending a passively secure protocol by adding a verification step whose communication is sublinear in the circuit size. For arbitrarily many parties and a dishonest majority, adding a trusted dealer enables efficient computation, as recently shown by Asterisk (IEEE S&P'24) without requiring DZK. This setting is also compatible with DZK, as shown by Boyle et al. (CRYPTO'21). Unfortunately, their approach is not tailored to computation over a ring $\mathbb{Z}_{2^k}$, often favored for concrete efficiency and practicality, resulting in high computational overhead. In the honest majority setting with few parties, Li et al. (CCS'24) optimized DZK to rings, achieving significant performance improvements.
In this work, we propose the first sublinear verification protocol that is both, designed for the $n$-party dishonest majority setting with a dealer, and tailored to computation over a ring $\mathbb{Z}_{2^k}$, combining and improving upon both approaches above. Previous approaches used $n$ DZK proofs to check correct behavior for each individual party. Instead, we show how to verify in a single, novel DZK proof that all parties together behave correctly. This decreases the communication complexity for verification from $\mathcal{O}(n \cdot \log m)$ to $\mathcal{O}(n + \log m)$ ring elements per party for $m$ multiplications. Hence, for the first time, active security using DZK scales well with the number of parties $n$. We provide the first public implementation for DZK with arbitrary $n$ and a dealer and show its practical efficiency. For $m=10^6$ multiplications across 30 layers, communication increases by only 0.7% over the passively secure base protocol with only moderate computation overhead. This becomes especially useful in a WAN setting, where we achieve active security at only 34% run time overhead over the passive variant. Compared to Asterisk (IEEE S&P'24), our protocol has 1.8x better communication and improves run time by 2.5x in WAN and 11.9x in LAN.
Maverick: Private and Verifiable LLM Inference Made Practical via Matrix-Vector Multiplication Delegation
Open-source large language models (LLMs) are increasingly competitive with closed-source models while offering transparency and the ability to run inference without exposing user inputs to a service provider. However, running large-scale models locally requires substantial computational resources. In practice, users may still resort to a third-party provider, giving rise to privacy and correctness concerns. Existing solutions that address these problems often impose substantial server overhead or introduce additional trust assumptions.
In this paper, we present Maverick, a novel approach to private and verifiable LLM inference based on a protocol for delegating matrix-vector multiplication, a dominant operation in LLMs. At its core, Maverick provides, to our knowledge, the first information-theoretically sound verification protocol for matrix-vector multiplication delegation with transparent preprocessing, efficient (batch) verification, and virtually no server overhead. We combine this verification primitive with LPN-based pseudorandom masking to provide input privacy.
We implement our matrix-vector delegation primitive and use it to build an end-to-end prototype of Maverick, which we evaluate on Qwen3-4B by measuring throughput in tokens per second. We evaluate client configurations with 1-8 threads. With one client thread and a CPU server using up to 128 threads, Maverick achieves throughput gains over local inference of up to 17x when privacy masks are generated online, 45x when they are precomputed, and 44x when only verification is required. With four client threads, the corresponding gains are 13x, 18x, and 17x. When server computation is no longer the bottleneck, client-side microbenchmarks with simulated network delay show speedups of 12x-20x, 34x-135x, and 38x-157x.
Basis Rigidity of the AES S-box and Generic Rigidity of Inversion under Affine Transformations
The AES S-box is constructed from finite field inversion followed by a
fixed affine transformation. Since inversion possesses intrinsic
Frobenius symmetries among its coordinate realizations, we study how
these basis symmetries are altered by outer affine transformations.
We first develop a deterministic rigidity criterion for transformed
inversion and apply it to the AES S-box. This shows that the linear part of the AES S-box affine transformation
alone makes the transformed inversion map basis rigid. We then investigate the corresponding generic problem when
the outer invertible linear transformation varies. The existence of a nontrivial common linear stabilizer is reduced to a
conjugacy problem for semilinear candidates arising from two sided
linear equivalences of inversion, which we characterize in terms of relative norms and Frobenius
orbits. We also determine the dimensions of the associated centralizer
algebras exactly. These structural results imply that, for a uniformly
chosen outer linear transformation, the probability that the linear stabilizer is nontrivial is bounded by $2^{-\Omega(n^2)}$, with sharper
finite dimensional bounds obtained from the exact conjugacy condition. Computational experiments independently verify the AES rigidity result,
the conjugacy and centralizer formulas, and the finite dimensional
estimates in small dimensions.
Structure-Preserving Compressing Primitives, Revisited
Structure-preserving (SP) cryptography enables the modular composition of pairing-based primitives through the definition of cryptographic algorithms whose public inputs and outputs are group elements and whose computations are generic group operations or pairings. Despite their potential usefulness, obtaining compressing primitives such as accumulators and vector commitments in the SP setting has remained a long-standing challenge, partly due to known impossibility results [Abe et al. Eurocrypt 2012].
Recently, [Krenn, Mir, and Slamanig PKC 2026] proposed the first SP vector commitments (SPVC) and accumulators (SPA) that circumvent these barriers via the adoption of structured message spaces that, albeit restricted, enable interesting applications such as constant-size pairing-based ring signatures.
In this work, we revisit the security of these recent constructions with a twofold contribution. First, we identify attacks against the recently proposed SPVC, SPA, and ring signature schemes.
Second, we present new constructions of SPVCs and SPAs that preserve the efficiency and structure-preserving nature of the original designs while achieving the desired standard security notions of position-binding and collision-resistance respectively.
Specifically, we construct a new SPVC with constant-size proofs and verification under the power discrete logarithm assumption in the algebraic group model. Building upon it, we introduce a new notion of SPA with extended message spaces and give a construction achieving collision resistance and constant-size membership proofs under the same assumption. Finally, we apply our techniques to obtain constant-size ring signatures in bilinear groups.
OAEP† Transform in the Post-Quantum World
We provide a new variant of OAEP called OAEP†, which converts an almost trapdoor injective function (ATIF) to a public-key encryption (PKE) scheme. The resulting PKE not only has CCA security but also enjoys pseudo-randomness, anonymity, and robustness under chosen-ciphertext attacks in the quantum random oracle (QRO) model.
Compared with the plain OAEP and its variants whose structure does not serve the quantum world very well, our OAEP† is designed with a new structure, admitting more flexible choices for ATIF and enjoying better security and efficiency. For OAEP†, we present two instantiations of ATIF from NTRU, which yield two practical post-quantum PKE schemes from lattices. The resulting PKE schemes are comparable to Kyber and NTRU-HPS derived from FO transform. The performance evaluations show that one of our PKE schemes is faster than Kyber512, and the other shares the same basic underlying structure with NTRU- hps2048677 but can additionally encrypt 132 bytes message.
Our OAEP† does not use the (third) additional hash function (unlike Q-OAEP) and has a tighter security reduction (than Q-OAEP), and thus answers the open problems proposed by the authors of NTRU, who proposed the NTRU KEM candidates in NIST’s third round of post-quantum cryptography standardization. And replacing the FO transform with OAEP† in NTRU-HPS (one of NTRU KEM in the third round) yields a CCA-secure PKE scheme that is as efficient as the original NTRU-HPS (from FO) but better than the PKE hybrid from NTRU-HPS and a symmetric encryption.
Besides NTRU, ATIF also has instantiations from isogenies/lattices. So OAEP† yields post-quantum CCA-secure PKE/KEM schemes from lattices/isogenies in the QRO model as well, suggesting the wide applicability of OAEP† in the quantum world.
Quantum Oracle Distribution Switching and Applications to Falcon and Ring Signatures
Motivated by digital signature algorithms ranging from Falcon to fully-anonymous ring signatures used in Signal-style key exchange, such as Gandalf, we revisit a fundamental problem in post-quantum security proofs: distinguishing oracle functions whose outputs are sampled independently from distributions $P$ and $Q$ that are close. In the context of signatures, closeness is often measured via Rényi divergences, which yield multiplicative bounds in the classical setting. A counterexample shows that such multiplicative-error bounds for distinguishers with classical oracle access have no analogue for quantum access, and we provide two alternative approaches based on small-range distributions and reprogramming techniques. We also give a concrete, optimal bound for the case where $P$ and $Q$ are close in statistical distance. We apply these techniques to the motivating constructions. (i) We give the first QROM security proof for Falcon that avoids oracle indistinguishability arguments based on statistical distance. This is crucial, as Falcon's ROM proof relies on Rényi divergence, while the statistical distance induced by its parameters is too large to yield meaningful bounds. (ii) We formalize and abstract the ring signature construction used in Gandalf as a modular framework by defining ring trapdoor preimage-sampleable functions (RPSFs), for which we obtain two QROM proofs.
We also provide two QROM security proofs for AOS ring signatures, adapting existing QROM techniques. Together with our results on RPSF-based ring signatures, this yields QROM security proofs for a broad class of fully-anonymous linear ring signature constructions, including Gandalf and the AOS-based constructions Erebor and MayoRS.
Sprinkle the Salt: RO-combiners with $\mathcal{O}(n)$ random bits
At Crypto 2023, Dodis, Ferguson, Goldin, Hall, and Pietrzak [DFGHP23] introduced and constructed Random Oracle (RO) combiners, rejuvenating the well-studied area of cryptographic combiners. RO-combiners are (salted) hash function modes of operation over multiple underlying compression functions that achieve indifferentiability as long as at least one of the underlying compression functions is ideal.
Unfortunately, the security of RO-combiners turns out to be a multi-stage game, and the well-established indifferentiability results for hash function modes cannot be lifted to RO-combiners via the composition theorem. There have been two works aiming to construct RO-combiners from scratch. [DFGHP23] built an indifferentiable compression-function combiner, whose deployment requires a new hash implementation, limiting its scope. The follow-up work by Dodis, Goldin, and Hall [DGH25] at Eurocrypt 2025 constructed the first secure RO-combiner capable of handling a large but fixed-length message using \MD hashing. However, implementing their construction either requires a random salt larger than the message length (potentially exponential in the security parameter) or incurs up to an exponential number of calls to the underlying \MD hash.
In this paper, we introduce a new design principle for robust RO-combiners that yields efficient and instantly deployable solutions. At the same time, the principle is generic, enabling the construction of robust variable-input-length RO-combiners from a wide class of popular hashing modes.
Our main result constructs robust RO-combiners from standard \emph{preimage-aware} hash constructions by salting each compression function call and applying a post-processor. The required salt size is $\mathcal{O}(n)$ for $n/2$-bit security and is independent of the input message size. Moreover, the combiner makes only a single call to each of the underlying hash modes. We show instantiations using both linear \MD and tree hashing.
From an instantiation perspective, with only a simple modification to message padding, our variable-length \MD combiner can be readily obtained with SHA-256 or Blake2. The combiner requires just $1408$ bits of randomness while achieving $128$-bit security and a message processing rate of $320$ bits per compression-function call.
Verifiable Weighted Secret Sharing based on Chinese Remainder Theorem
In this work, we present the first practical verifiable weighted secret sharing (VWSS) scheme based on the Chinese Remainder Theorem (CRT). Classical secret sharing schemes, such as Shamir’s, assume participants with equal weights, which is inadequate for emerging applications like stake-based DAO voting and proof-of-stake blockchains, where parties naturally have unequal voting power or stakes. While prior work (e.g., Garg et al., Crypto'23) demonstrated that CRT-based (ramp) secret sharing can support weighted access structures more efficiently than linear secret sharing schemes, existing constructions only guarantee security against honest-but-curious dealers. In contrast to traditional linear secret sharing schemes, extending verifiability to CRT-based weighted secret sharing remains challenging, as current approaches either fail to support weighted access structures or incur prohibitive computational overhead on the dealer, limiting their practicality.
To address this gap, we develop novel $\Sigma$-protocols for the \emph{unbounded} proof-of-mod (UPoM) relation using integer commitments in groups of unknown order, which may be of independent interest. Combining our UPoM protocols and new observations on the structural properties of CRT-based secret sharing, we construct a VWSS scheme in which the dealer broadcasts only $O(|A|)$ commitments to secret shares, where $A$ is a subset of parties whose total weight meets the reconstruction threshold $T$. This improves upon the closest prior CRT-based VWSS scheme (Shehata et al., CVC'25), which requires the dealer to broadcast commitments to the secret shares of all parties. Concretely, for a system with four participants and total weight $524$, our scheme generates VWSS proofs in around $0.2$ seconds, \emph{orders of magnitude faster} than the construction of CVC'25, highlighting its practicality for real-world applications.
Honest Majority MPC Achieving GOD with $O(|C|)$ Communication From Pairwise Random OLE Correlations
In this work, we study the communication complexity of information-theoretic MPC with guaranteed output delivery (GOD) in the honest majority setting $(t<n/2)$.
The recent work by Song and Ye (EUROCRYPT 2025) gives an honest majority MPC in the random oblivious linear evaluation (OLE) preprocessing model that computes an arithmetic circuit of size $|C|$ with malicious security with abort at the cost of $O(|C|)$ of both communication in field elements and total number of random OLE correlations. We explore the possibility of deriving a similar result for the stronger security notion of GOD. Specifically, we ask the question: `` Is it possible to construct an information-theoretic honest majority MPC in the random OLE preprocessing model that computes an arithmetic circuit of size $|C|$ and achieves GOD with $O(|C|)$ field elements of communication and $O(|C|)$ amount of random OLE correlations in total? ''
We resolve the above question in the affirmative by providing a concrete construction. To achieve our result, we mainly rely on two techniques. First, we propose a new secret sharing scheme which we refer to as detectable secret sharing. It is a packed secret sharing scheme with an authentication mechanism. Second, to efficiently verify the computation and locate an error when faults occur, we extensively make use of the virtual transcript technique introduced in the work by Goyal, Song, and Zhu (CRYPTO 2020).
Our construction is in the random OLE preprocessing model where we assume random OLEs between each pair of parties. By instantiating the random OLEs from various assumptions, we obtain three honest majority MPC protocols with GOD with the following security and communication: (1) the first one achieves information-theoretic security with offline communication of $O(|C|n)$ elements and online communication of $O(|C|)$ elements, (2) the second one achieves computational security with $\tilde{O}(|C|)$ elements of communication only from a random oracle, and (3) the third one achieves computational security with $O(|C|)$ elements of communication from pseudorandom correlation generators (PCG).
Pushforward Problems and Applications to Isogeny-based Cryptography
Let $E$ and $E'$ be two supersingular elliptic curves and let $\varphi: E\to E'$ be an isogeny of known degree $d$. Given a basis $(P, Q)$ of $E[N]$ together with $(\varphi(P), \varphi(Q))$, it is possible to recover $\varphi$ provided that $N$ is sufficiently large and smooth, and that the torsion basis can be represented over a small extension of the base field.
In this work, we consider the more general setting where the $N$-torsion may not be efficiently representable. To address this setting, we introduce a new framework for encoding torsion information via an oracle that computes pushforwards of $N$-isogenies under $\varphi$. We then show that there exist instances for which access to the pushforward oracle allows for an efficient isogeny recovery.
Beyond their theoretical interest, these instances have direct cryptographic implications. We show a practical attack against the threshold signature scheme recently proposed by Kim, Kim, and Lee. We also identify weak instances for Basso's oblivious pseudorandom function, and we refine the security discussion for Leroux and Roméas's updatable encryption scheme.
A Generalized ISD Framework for Large-Weight Syndrome Decoding
Syndrome decoding ($\mathsf{SD}$) over $\mathbb{F}_2$ has long been a central problem in code-based cryptography. Large-weight syndrome decoding ($\mathsf{LWSD}$) is a recent variant whose ternary case was introduced by Debris-Alazard, Sendrier and Tillich (ASIACRYPT '19) in the security analysis of the $\mathsf{Wave}$ signature. It has different hardness characteristics from the classical low-weight $\mathsf{SD}$ problem. However, the security analysis of $\mathsf{LWSD}$ is still limited, and existing work mostly focuses on ternary instances.
In this work, we study information set decoding (ISD) algorithms for $\mathsf{LWSD}$ over non-binary fields. Building on the ternary work of Bricout et al. (SAC '19), we give a generalized ISD framework for $\mathsf{LWSD}$ over $\mathbb{F}_q$. The framework is formulated as a single binary merge tree that unifies splitting-based, representation-based, and hybrid ISD algorithms. In particular, it captures known large-weight decoding algorithms as special cases and allows the merge pattern to be optimized together with the other ISD parameters.
We evaluate the framework both asymptotically and concretely. For the asymptotic analysis, we give algorithmic landscapes for the whole $\mathsf{LWSD}$ regime and show which ISD algorithm gives the smallest asymptotic complexity for each instance. We also provide representative asymptotic complexities for several $\mathsf{LWSD}$ instances, including those corresponding to existing work. For the concrete analysis, we provide bit complexity estimates for the $\mathsf{Wave}$ parameter sets. These estimates remain above the claimed security levels.
Parallel Kac’s Walk Generates PRU
Ma and Huang recently proved that the PFC construction, introduced by Metger, Poremba, Sinha and Yuen [MPSY24], gives an adaptive-secure pseudorandom unitary family PRU. Their proof developed a new path recording technique [MH25].
In this work, we show that a linear number of sequential repetitions of the parallel Kac's Walk, introduced by Lu, Qin, Song, Yao and Zhao [LQS+26], also forms an adaptive-secure PRU, confirming a conjecture therein. Moreover, it additionally satisfies strong security against adversaries making inverse queries. This gives an alternative PRU construction, and provides another instance demonstrating the power of the path recording technique. We also discuss some further simplifications and implications.
Certified-Everlasting Quantum NIZK Proofs
We study non-interactive zero-knowledge proofs (NIZKs) for NP satisfying: 1) statistical soundness, 2) computational zero-knowledge (ZK) and 3) certified-everlasting zero-knowledge (CE-ZK). The CE-ZK property allows a verifier of a quantum proof to revoke the proof in a way that can be checked (certified) by the prover. Conditioned on successful certification, the verifier's state can be efficiently simulated with only the statement, in a statistically indistinguishable way. Our contributions regarding these certified-everlasting NIZKs (CE-NIZKs) are as follows:
- We identify a barrier to obtaining CE-NIZKs in the CRS model via generalizations of known interactive ZK proofs that satisfy CE-ZK.
- We circumvent this by constructing CE-NIZK using non-black-box use of NIZK for NP satisfying certain properties, along with OWFs. As a result, we obtain CE-NIZKs for NP in the CRS model, based on polynomial hardness of the learning with errors (LWE) assumption.
- In addition, we observe that the aforementioned barrier does not apply to the shared EPR model. We leverage this to construct CE-NIZK for NP in this model based on any statistical binding hidden bits generator, which is known from LWE. The only quantum computation here involves single-qubit measurements of the EPR pairs.
Rank Measures and Exponential Lower Bounds for Multilinear Secret Sharing
Multilinear secret sharing can amortize share size over a vector secret, so scalar linear lower bounds need not survive normalization by the secret dimension. We prove that the Razborov–G´al rank measure does survive this amortization: every multi-target monotone span program satisfies a rank inequality in which the target dimension appears multiplicatively. Combined with the characteristic-separated witnesses of Pitassi and Robere, this gives an explicit family of access structures whose average and maximum multilinear information ratios are exponential over every finite field, settling the worst-case order at $2^{\Theta(n)}$. We also study arbitrary sharing algorithms with affine-linear reconstruction under non-perfect security notions, including the pairwise statistical security of Beimel–Othman–Peter and the partial privacy of Jafari–Khazaei. Combining these affine-reconstruction results with the degree-reduction theorem of Beimel–Othman–Peter gives corresponding fixed-degree lower bounds under both security notions, in particular for subexponential secret dimension.
Fault Injection Attacks on Torsion Masking
In 2022, a string of attacks on SIDH was released that made use of the now infamous Kani's Lemma. Since then, several new and exciting isogeny-based protocols have emerged that both avoid the attacks, while at the same time, leverage the power of Kani's Lemma to improve their efficiency. One common technique to do so has been the inclusion of masked torsion points. This is when a protocol publishes information about how a secret isogeny acts on a large torsion subgroup, but masks the exact image points by multiplying them by some secret scalars.
In this work, we present the first analysis of the physical security of the masked torsion point technique. We provide fault injection attacks on the signature scheme PRISM, and the public-key encryption schemes POKÉ and FESTA. Our fault model is standard in the literature, and can be implemented inexpensively. Most notably, three of the five attacks presented only require one or two first-order faults, which is significantly less than what is needed to attack other isogeny-based cryptosystems that do not use torsion masking.
Learning with Alternating Moduli, Arora-Ge over Composite Moduli, and Weak PRFs
In TCC 2018, Boneh, Ishai, Passelègue, Sahai, and Wu propose candidates of weak and strong PRFs by evaluating linear functions over coprime moduli alternatively. Such PRFs can be evaluated by low-depth circuits and are MPC-friendly. However, they have not been able to base the security of their PRFs on well-formed assumptions other than assuming that the PRF constructions themselves are secure.
In this paper, we formalize a new assumption called Learning with Alternating Moduli (LAM). We show that over certain large moduli, the LAM assumption is as hard as the Learning with Errors (LWE) assumption. For LAM over constant moduli, we do not know how to base its hardness on the LWE assumption. Instead, we provide
(i) polynomial-time attacks on LAM with constant prime-power moduli and certain constant non-prime-power moduli, and
(ii) evidence of the sub-exponential hardness of LAM with other moduli by analyzing the effect of typical attacks.
More specifically, we put forward two new attacks. The first attack is a recursive algorithm that solves LWE with certain constant composite moduli and error distributions. The algorithm extends the Arora-Ge algorithm for LWE from prime moduli to composite moduli, and it also solves LAM for certain parameters. The second attack is a polynomial-time attack that rules out the existence of weak PRFs in $\mathsf{NC}^0[p]$ for any prime $p$.
Based on our studies, we propose candidate weak PRFs in $\mathsf{NC}^0[p_1,p_2]$ for some distinct primes $p_1,p_2$ based on LAM over constant moduli, or the Learning with Rounding (LWR) assumption over constant moduli. Compared to the weak PRF candidates by Boneh et al., our weak PRF candidates live in the same complexity class while having the advantage of being based on well-formed assumptions.
Pushing Collision Attacks on SHA-2 to 39 Steps
The SHA-2 family is a U.S. federal standard and mainly includes SHA-256 and SHA-512. In particular, SHA-256 plays a central role in real-world applications and is widely regarded as one of the most important hash functions in use today. At CRYPTO 2026, Li et al. proposed collision attacks up to 37-step SHA-2, but they could not reach 38 steps due to the low-probability uncontrolled part in the corresponding differential characteristics. In this paper, we propose an improved search procedure to find high-quality differential characteristics for 38-step SHA-256 and SHA-512, respectively. Exploiting the special shape of the 38-step differential characteristics, the meet-in-the-middle method to fulfill the corresponding differential conditions is extremely memory-efficient. Consequently, we successfully achieve the first 38-step collision attack on both SHA-256 and SHA-512, whose time complexity is $2^{104.3}$ and $2^{125.4}$, respectively. The memory complexity of the 38-step collision attack is negligible. The methods are also applied to the 36-step and 37-step collision attacks on SHA-2 published at CRYPTO 2026, leading to a significant improvement in both time and memory complexity. In particular, the time complexity of the collision attack on 36-step SHA-256 is only $2^{57}$ and the memory complexity is negligible. We have verified this collision attack by providing the first colliding message pair for 36-step SHA-256. More remarkably, we apply the new method to 39 steps of SHA-2 and obtain the first effective collision attack on 39-step SHA-512, with a time complexity of $2^{178}$
and negligible memory complexity. However, the method does not yield an effective collision attack on 39-step SHA-256 due to the same issue arising from the low-probability uncontrolled part. Overall, this work further pushed the limit of memory-efficient collision attacks on round-reduced SHA-2 and significantly advances the state of the art.
DualMS 2.0: Practical Lattice-Based Two-Round Fiat-Shamir Multi-Signature with Better Efficiency
Uncategorized
Uncategorized
We present a more practical lattice-based two-round Fiat–Shamir multi-signature scheme that achieves a substantial reduction in signature size compared with DualMS, the state-of-the-art two-round lattice-based Fiat-Shamir multi-signature. Our main technical contribution is a new simulation technique that enables individual signatures to be sampled from distributions with smaller parameters, yielding significant concrete efficiency gains. In addition, through applying the specific modulus-rounding optimization, we can further reduce the sizes of signature and aggregated public-key.
Concretely, compared with DualMS, our scheme reduces the signature size by 62.4%, and the aggregated public-key size by 37.5%. For example, with 32 signers, our signature and aggregated public-key are approximately 8.86 KB and 4.38 KB (versus 19.72 KB and 6.94 KB in DualMS) respectively, and for 1024 signers, our signature and aggregated public-key are approximately 11.62 KB and 6.56 KB (versus 30.91 KB and 10.5 KB in DualMS).
Moreover, in order to show the practicality of our scheme, we implement our scheme in Go language using the open-source library Lattigo, and then analyze its performance on computation and communication, through both local and WAN experiments. To the best of our knowledge, our scheme achieves the smallest concrete signature sizes among all existing two-round lattice-based multi-signature schemes following Fiat–Shamir with abort paradigm. These results suggest that our scheme is practical and well-suited for real-world deployment.
Extendable Weighted Evolving Threshold Secret Sharing Schemes over Polynomial Quotient Rings
In conventional $(k,n)$ secret sharing schemes, a dealer distributes shares of a secret among $n$ participants such that any subset of at least $k$ participants can reconstruct the secret. While such schemes often fail to accommodate practical scenarios in which participants have different management permissions over the secret. To address this problem, weighted $(t,n)$ secret sharing was introduced. In this case, each participant is assigned a specific weight, and the dealer distributes a share to each participant according to their weight, so that any subset of participants whose sum of weights is at least $t$ can recover the secret. However, in weighted $(t,n)$ secret sharing schemes, the number of participants $n$ is known in advance. When $n$ is uncertain and even grows over time, traditional weighted $(t,n)$ secret sharing schemes remain inadequate in such dynamic environments. To solve the problem, we propose the concept of a weighted evolving $t$-threshold secret sharing. Based on the prefix codes, we first propose a construction of a weighted evolving $3$-threshold scheme over the polynomial quotient ring for an $\ell$-bit secret. And then we extend the framework to a general weighted evolving $t$-threshold scheme for any $t\geq 3$. Moreover, we prove the correctness and security of the proposed scheme by leveraging the properties of the polynomial quotient ring and prefix codes. Finally, we analyze the corresponding share size. The result shows that for the $m$-th participant with the weight $w_m$ satisfying $1\leq w_m\leq t-1$, the size of the corresponding share is $w_m(t-1-\frac{w_m-1}{2})(\ell_m-1)+w_m\ell$ bits, where $\ell_m$ denotes the length of a binary prefix code of encoding integer $m$. In contrast, a baseline scheme that allocates $w_m$ independent full evolving shares to this participant would require $w_m(t-1)(\ell_m-1)+w_m\ell$ bits. Our proposed scheme saves $\frac{(w_m-1)w_m}{2}(\ell_m-1)$ bits, thereby achieving a smaller share size.
A Post-Quantum Cryptography Recommendation System with TLS Validation for Heterogeneous Environments
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.
Robust Additive Randomized Encodings With Transparent Setup
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.
Partially Non-Interactive Two-Round Threshold and Multi-Signatures with Tighter and Adaptive Security
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.
VAHANA: Hardware-Aware Noise Addition Against Gradient Inversion Attacks
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.
A Note on the Security Analysis of Areion
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.
ReinsPIRe: High-Throughput, Low-Communication PIR with Server Preprocessing
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.
MERIDIAN: A Toroid-Inspired Permutation Block Cipher for Constrained Environments
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 from FESTA
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.
Obfuscating Non-Evasive Programs: Making Witness Encryption Positional
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.
Velox: Scalable Fair Asynchronous MPC from Lightweight Cryptography
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.
Computationally Efficient Asynchronous MPC with Linear Communication and Low Additive Overhead
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.
Malicious Security Comes Free in SPDZ
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.
SoK: Zero-Knowledge Friendly Hash Functions over Prime Fields
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.
Sample-then-Correct: Practical fuzzy extractors for biometrics beyond the iris
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.
ASCON-Based Lightweight Cryptographic Provenance for Distinguishing Physiological Events, Sensor Faults, and Cyberattacks in IoMT
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.
Two-Round Threshold Signatures with Adaptive TS-UF-1 Security from MDDH
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.
A Forgery Attack against Frobenius-UOV
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-Malleable Reductions of Knowledge
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.
MamaBearZKP: A Holistic Co-design of Prime Fields and Proving Stacks for High-Throughput ZKP on Modern CPUs
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.
Symmetric and Asymmetric Anonymous Authenticated KEM
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.
Reproducible Design-Space Study of Lightweight Lattice-Based Authentication and Signatures for Blockchain Transactions
Uncategorized
Uncategorized
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.
Decryption-Failure Rate with Multidimensional Lattice Decoders: Unified Framework, Theory Refinement, and More Accurate Evaluation
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.
Attacks and Remedies for Randomness in AI (and with AI): Cryptanalysis of PHILOX and THREEFRY
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.
SDDT: An Operation Skip Attack Framework for Bitslice Ciphers—Validated on PIPO
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.
Security Properties of Iterated Random Functions
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.
Pairing-based Succinct Half-Chosen VOLE
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.
Homomorphic Functional Encryption: Trustless Key Derivation for Functional Encryption
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.
Generic Ring-Signature Transforms for Fiat-Shamir with Aborts and Hash-and-Sign with Retry
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.
Towards Worst-case Hardness for Low-Noise LPN
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.
Towards Practical Privacy-Preserving SAT Solving
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.
Coral: General and Efficient Framework for Homomorphic Evaluation of Symmetric Ciphers
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.
Computing 256-bit elliptic curve discrete logarithms in 26 days on a fault-tolerant trapped-ion quantum computer with 20,000 qubits
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\%$.
Adding more parallelism to the AEGIS authenticated encryption algorithms
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.
Threshold Encryption with Internally Motivated Corruptions
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.
Trapdoor Functions with Secure Key Leasing and Copy Protection
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.
Secrecy in Squirrel and the Post-Compromise Security of a Ratchet
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.
Why Johnny Should Not Delegate Email Encryption to Gateways
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.
Secure Multi-party Matrix Invertibility Testing over Small Finite Fields
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.
Deterministic Partial Algorithms for Matrix-Space Conjugacy over Finite Fields
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.
NTPIR: Efficient Silent-Preprocessing PIR using NTR
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.
Tightly and Adaptively Secure Two-Round Threshold Signatures from DDH
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.
Revisiting Simple Power Analysis of Polynomial Multiplication in the HQC Implementation
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.
OptiMix: Scalable and Distributed Approaches for Latency Optimization in Modern Mixnets
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.
Faster CoeffToSlot and SlotToCoeff for Sparsely Packed Ciphertexts with Application to CKKS Bootstrapping
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.
A Better Bivariate Resultant Attack on Round-Reduced Poseidon
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.
On Compressing Linearly Shared Correlations
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.
ZHE: Efficient Zero-Knowledge Proofs for HE Evaluations
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.
Bandwidth Efficient Partial Authorized PSI
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.
Polynomial Time Cryptanalytic Extraction of Deep Neural Networks in the Hard-Label Setting (Extended Version)
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.
SCA-MAYO: Demystifying Side-channel Security of MAYO Signature Scheme
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.
Fast Batch Matrix Multiplication in Ciphertexts
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.
Chosen-Block BAA Codes: Fast, Near the Gilbert–Varshamov Bound, and Field-Agnostic
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.
Auntie: Unobservable Contracts from Zerocash and Trusted Execution Environments
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.
Optimal Bucket Set Construction for Multi-scalar Multiplication with Endomorphisms
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: A Tutorial and Survey
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.
Nothing Up My Matrix: Kleptographic Backdoors in ZK-friendly Hash Functions
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.
Batch-Puncturing Circuit CP-ABE (and More) from Lattices
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.
Extending the SPHINCS+ Framework: Varying the Tree Heights and Chain Lengths
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.
Threshold Fully Deniable Interactive Encryption
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.
Secure and Updatable Single Password Authentication
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.