Papers updated in last 183 days (Page 3 of 2708 results)

Last updated:  2026-11-04
A New Approach to Improved PNB-based Attacks on Reduced-round ChaCha and Salsa
Goutam Paul, Anup Kumar Kundu, and Sucheta Chakrabarti
ChaCha and Salsa are two ARX based stream ciphers which are widely used in data encryption including TLS v1.3 standard, VPN software etc. Exploiting Probabilistic Neutral Bits (PNB) is one of the most significant cryptanalysis strategies for reduced-round versions of these ciphers. The seminal work using PNB by Aumasson et al. (FSE 2008) claims that the PNB set mostly depends on the output bit difference occurring in the intermediate round. The subsequent works mainly relied on the differential or differential-linear cryptanalysis, or multiple distinct input-output differentials for which the bias is higher than a threshold in the intermediate round. In this paper, we propose a new PNB set construction based on multiple output bit differences with respect to a single input bit difference only. We exploit the differentials to mount key recovery attacks using a multi-step procedure depending on our new PNB set. Our attack achieves a time complexity of $2^{167.90}$ for ChaCha20/7 and $2^{183.54}$ for Salsa20/8 in 256-bit versions, beating all the existing PNB-based attacks on ChaCha20/7 and Salsa20/8 by a significant margin. Further, both our time and data complexities for ChaCha20/7.5 are better than the latest published works by Flórez-Gutiérrez and Todo (Eurocrypt 2025 and Asiacrypt 2025). For 128-bit versions, our attack procedure results in a time complexity of $2^{115.24}$ for ChaCha20/6.5 and $2^{98.40}$ for Salsa20/7.5 respectively. We have experimentally validated the underlying independence assumptions across all ciphers, alongside our attack procedure on different reduced-round toy versions of ChaCha.
Last updated:  2026-11-04
Trapdoors Beyond Inversion: Recoverable Information in Public-Key Cryptography
Kanad Chakravarti, Shreyas Gupta, Bhavana Kanukurthi, and Girisha Shankar
Classical trapdoor functions recover complete preimages, whereas public-key decryption needs only designated information about an encryption input. We study this distinction through trapdoor hardcore functions (TDHFs), whose trapdoor recovers a prescribed value $h(x)$ from a public evaluation $f (x)$, while $h(x)$ remains pseudorandom given the public key and evaluation. For perfectly correct primitives, we show that adaptive TDHFs characterize IND-CCA2-secure public-key encryption. The constructive direction requires only a single recoverable bit and allows noninjective public evaluations. Extending the rejection-sampling approach, we show that adaptive pseudorandomness itself controls queries to unselected candidate evaluations, without requiring full inversion. We also prove that lossy TDHFs characterize lossy public-key encryption, identifying statistical hiding of the designated recovered value as the relevant lossiness requirement. Fiber samplability together with fiber hiding yields a parameter-preserving correspondence with lossy encryption and, through the known long-message transformation, almost-always lossy trapdoor functions when the recovered-value length exceeds the fiber-sampling randomness length. Ordinary TDHFs provide the corresponding characterization of IND-CPA encryption. Together, these results make explicit the roles of adaptive recovery, conditional sampling, and randomness costs in transformations between public-key encryption and full-inversion primitives.
Last updated:  2026-11-04
SoK: Cryptographic Erasure on Public Ledgers: Application-Layer Architectures, Key-Lifecycle Adversaries, and GDPR Art. 17 Sufficiency
Yitebeier Aikebaier
Public permissionless ledgers are append-only by design, yet are increasingly asked to host data subject to statutory erasure obligations (GDPR Art. 17, EDPB Guidelines 02/2025). The prevailing cryptographic response, redacting the chain itself, needs either a different chaining hash or the cooperation of every node, neither of which a controller on Bitcoin or Ethereum mainnet commands. This SoK systematizes the orthogonal application-layer design space, in which the ledger is left untouched and erasure is achieved by destroying the key material required to read the on-chain bytes. We organise the literature along two axes, data locus (on-chain ciphertext, anchor-only, or hybrid), key custody (single-custodian or threshold), and access gate (none, time, or witness), into a twelve-cell grid with canonical constructions from 1996 to 2026. We extend standard IND-CCA security with a key-lifecycle adversary model parametrised by HSM side-channel leakage, coercion fraction over the custody committee, and algorithmic-break horizon, give the security experiment as pseudo-code with adaptive corruption, cumulative leakage across key rotations, a decryption oracle, and a stronger post-destruction adversary class, and prove that the resulting Destruction-IND-CCA notion suffices for a semantic-security formalisation of the EDPB "render unrecoverable" criterion. We state what is provable per custody model: a concrete bound for single-custodian AEAD, a bound for Shamir threshold custody that grows with the number of rotations, an impossibility result for delay-only designs, and a reduction showing witness-gated erasure needs extractable witness encryption. Evaluating seven reference architectures against eleven engineering, cryptographic, and regulatory criteria, including a production RegTech engine measured at 2.6 × 10^3 events/s single-threaded (10^4 projected with connection pooling), we find that the literature has concentrated on chain-rewriting while the application-layer branch lacks a common threat-model vocabulary. We close this gap and identify five open problems: post-quantum destruction security, the leakage threshold of a custody scheme, decentralised lifecycle audit (with a multi-custody extension covering encrypted mempools), composition with ZKP selective disclosure, and erasure under multi-regime retention conflict.
Last updated:  2026-11-04
On Key Recovery from Exposed Neural XOR Activations in DES and TDES
Kwangjo Kim
We study the security of natural ReLU realizations of the Data Encryption Standard (DES) and two-key Triple DES (TDES) when an adversary can submit non-binary inputs and observe selected intermediate neural values. The attack exploits the piecewise-linear extension of XOR: paired inputs that differ in one expanded right-half bit reveal the corresponding round-key bit from the change in a natural XOR node. For DES, the resulting 48-bit first-round subkey leaves only the eight key-schedule bits omitted by PC-2; enumerating these bits and checking an intermediate value recovers the 56-bit effective master key. For two-key EDE TDES, the same technique recovers the first encryption subkey of K_1 and the last DES subkey used by the middle decryption under K_2; two independent 2^8 completions then recover the full 112-bit key pair. The exposed round subkey is recovered with a constant number of leakage observations per bit, giving query complexity linear in the targeted subkey length; the remaining searches are fixed-size for DES. Python experiments report exact recovery for 1,000 random DES keys and 1,000 random two-key TDES key pairs. These results concern a synthetic intermediate-oracle model for natural neural implementations and do not claim a physical attack on conventional DES/TDES hardware or software.
Last updated:  2026-11-04
Provenance Proofs: Linkable Zero-Knowledge Derivation Relations for Hierarchical Deterministic Wallets
Vincenzo Botta, Michal Pospieszalski, Emanuele Ragnoli, and Justus Ranvier
ZKPoSP proves that a public key or address was honestly derived from a hidden wallet seed, without revealing the seed or the private derivation state. This paper studies relationships among several derived values: whether public keys or addresses, possibly on different curves and different blockchains, share a hidden origin, which is the seed or an anchor of the wallet, and who else can recognize this relation. We give a model for such provenance proofs, with derivation proofs, which carry a link value, and provenance proofs, which show that several derivation statements share an origin. We define correctness, derivation soundness, provenance soundness, non-frameability and unlinkability. We give four constructions, which differ in who can link: only the user, with a joint proof or with commitments linked later; anyone within a linking context, with a deterministic tag, which can also act as a nullifier; or a designated authority, with an encryption of that tag. We prove, in sketch form, that the constructions satisfy the five properties under the security of the ZKPoSP derivation relations, the random oracle model, and the zero knowledge and simulation extractability of the proof system. We describe an application to cross-chain transfers from Bitcoin to Solana, in which the payout address must come from the same wallet as the source address, so that an attacker cannot substitute the destination. We report Plonky3 benchmarks of the derivation proofs on which the constructions are built.
Last updated:  2026-11-04
(R)Icy-DVRF: A Robust Distributed Verifiable Random Function Based on ROAST Signatures
Ahmet Ramazan Ağırtaş, Oğuz Yayla, and Melis Berçin Yılmaz
Ensuring robustness and liveness in distributed verifiable random functions (DVRFs) allows the protocol to maintain correct operation and guarantee output generation, even in the presence of malicious actors attempting to disrupt the process, delay cryptographic shares, or remain unresponsive. Because existing DVRF protocols typically rely on synchronous or semi-synchronous network assumptions, simultaneously achieving these properties remains a challenge. To address this limitation, this paper enhances the FROST-based Icy-DVRF protocol to achieve both robustness and liveness. Specifically, we propose (R)Icy-DVRF, a novel protocol that operates over an asynchronous network while maintaining a constant-size proof. This is achieved by integrating the ROAST coordination layer into the underlying FROST-based threshold evaluation and proof generation mechanism.
Last updated:  2026-11-04
Cryptographically Secure Digital Consent
F. Betül Durak, Abdullah Talayhan, and Serge Vaudenay
In the digital age, maintaining trust and security in third-party services is crucial, especially when it comes to consent for online actions executed by third parties. This work studies the concept of cryptographically secure digital consent. We provide a protocol which involves a client (the user) and an agent (which executes the action upon receiving consent) with the help of an identity manager (typically: an SSO service and/or a secure device). The client is required to keep no more than a consent password in addition to their existing authentication credentials. The design addresses several security challenges, including non-repudiability of consent. Security is maintained even if either the identity manager or the agent is compromised. Our protocol supports various applications, is compatible with existing identity managers, and is very simple. Our notion of an identity manager is broad, encompassing combinations of different authentication factors such as a password, a smartphone, a security device, biometrics, or national digital identity. We demonstrate applications for signing PDF documents, e-banking, and key recovery. Finally, we implement the PDF signing application, which is robust in the sense that a user can continue to use the signing service even after their devices are broken, lost, or stolen. Hence, an agent can sign on behalf of a user but remains liable for signatures released without consent, which removes a common trust assumption in existing solutions.
Last updated:  2026-11-04
Gaussian Difference Dynamics: Breaking the $2^{n/2}$ Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling
Yiming Gao, Xuyuan Han, and Honggang Hu
We give classical randomized algorithms in a word-RAM model that break the $2^{n/2}$ barrier for both discrete Gaussian sampling (DGS) and the Shortest Vector Problem (SVP). For every fixed $\alpha>1$, shifted DGS on arbitrary lattices at width $\sigma\ge\alpha\eta_{1/2}(L)$ takes $$ (3/2)^{n/2+o(n)}\text{ time} \qquad\text{and}\qquad (4/3)^{n/2+o(n)}\text{ space}. $$ These bounds match the Becker--Ducas--Gama--Laarhoven (BDGL) heuristic sieving exponents. At widths at least $3\eta_{1/2}(L)/2$, the same total cost suffices for an entire batch of $\lfloor(4/3)^{n/2}\rfloor$ samples jointly close to independent target Gaussians. For SVP on arbitrary lattices, our algorithm returns a shortest nonzero vector with high probability in $$ 2^{0.4130n+o(n)}\text{ time} \qquad\text{and}\qquad 2^{0.3138n+o(n)}\text{ space}. $$ As a corollary, we obtain centered DGS at every width with the same exponents, answering a question of Stephens-Davidowitz (SODA 2016). We introduce Gaussian difference dynamics (GDD), a framework for tracking expected counts and pairwise clustering of vectors through repeated differencing. A closed recursion for the first two counting moments controls these quantities relative to a Gaussian reference, without requiring independence within intermediate lists. Accurate moment bounds let us extract a Gaussian sample by weighted selection, while the weaker bounds needed to establish a shortest vector representation allow us to retain more differences. We perform these transitions on thin spherical shells, where the Gaussian rejection weights can be renormalized at subexponential cost. For batch sampling, we combine this geometry with the double rejection technique of Doulgerakis and Laarhoven to control the joint distribution of outputs while reusing vectors.
Last updated:  2026-11-04
Distance of RAA Codes over Large Finite Fields (with Applications in zkSNARKs and PCGs)
Pariya Akhiani and Yupeng Zhang
Error-correcting codes play a central role in modern cryptography, enabling efficient constructions of primitives such as zero knowledge proofs and secure multiparty computations. Among them, repeat-accumulate-accumulate (RAA) codes have recently attracted significant attention due to their linear-time encoding and good distance properties. However, prior work only established provable distance guarantees over the binary field or over finite fields whose size is smaller than the message length. The underlying techniques do not extend to larger fields. This restriction is significant, as many cryptographic constructions based on error-correcting codes operate over large finite fields. In this paper, we prove that RAA codes achieve constant relative distance $0<\delta\le \frac{1}{2}$ with high probability over large finite fields. Moreover, we resolve an open conjecture by showing for the first time that the distance of RAA codes improves over large fields. We provide both theoretical analysis and empirical evidence demonstrating that, compared to the binary case, large fields yield strictly better distance guarantees with much smaller failure probabilities. Our empirical evaluation shows that for message length $n=2^{20}$ and repetition factor $r=4$, the RAA code over a 31-bit prime field achieves relative distance $1/2$, except with failure probability $2^{-20}$. This is better than the best provable distance of $\delta = 0.2$ with failure probability $2^{-10}$ over the binary field. Leveraging our improved distance bounds, we obtain a 2.6$\times$ reduction in the proof size of a polynomial commitment scheme based on RAA codes compared to using the binary-field bound, and a 5.4$\times$ reduction compared to a prior construction based on expand-accumulate codes.
Last updated:  2026-11-04
Syndrome Decoding out of the Head: Structure-Aided Side-Channel Witness Recovery on SDitH
Jaeyeon Lee, Jaeho Jeon, and Young-Sik Kim
Regular syndrome decoding (RSD) underlies several code-based signature schemes, including SD-in-the-Head (SDitH). Its secret witness has exactly one nonzero coordinate per block, and the selected positions must satisfy a public syndrome equation. In this work, we show how these structural constraints can be exploited to recover the complete witness from imperfect side-channel information. We present a profiled power analysis of the witness-embedding operation in the SDitH Round-3 reference implementation. We train convolutional neural networks (CNNs) to classify the mux digits encoding each regular block and use their outputs to rank candidate positions. To correct errors in these predictions, we combine the resulting rankings with the public syndrome and the regularity constraints. We formulate this recovery problem as an affine correction system with block-validity constraints and analyze its rank, consistency, and uniqueness for the systematic parity-check matrix used in SDitH. Based on this analysis, we develop a quotient-syndrome decoder that identifies blocks whose true positions fall outside the initial candidate lists, avoiding exhaustive enumeration of block subsets. We evaluate our attack on an ARM Cortex-M4 using measured power traces. With a single target trace per key, our approach recovers all 100 test witnesses under -Os using 4,000 profiling traces, and 91 out of 100 under -O3 using 16,000 profiling traces. Each successful recovery matches all 616 serialized witness bits. These results demonstrate how the regular structure of RSD and the public syndrome can compensate for imperfect side-channel predictions, thereby enabling full-witness recovery.
Last updated:  2026-11-04
Differentially Oblivious Graph Ball Queries
Zimai Guo, Cheng Hong, and Zhechen Li
A graph ball query returns all vertices within distance $r$ of a source vertex. On $N$-vertex graphs with maximum degree at most $\Delta$, ordinary breadth-first search answers such queries with $O_{\Delta,r}(1)$ record accesses. These accesses depend on private edges and can reveal graph structure. Full obliviousness hides this dependence, but incurs substantial overhead. Differential obliviousness (DO) [Chan et al., SODA'2019] trades off between privacy and efficiency by relaxing full obliviousness to $(\varepsilon, \delta)$-differential privacy on the access traces of neighboring graphs. We study DO graph ball queries under three widely-adopted edge-level neighboring relations: add/delete, replacement, and $2$-switch. Starting from padded adjacency records, we charge all observable accesses, including preprocessing. For fixed $\Delta,r\ge2$, error probability $0<\beta<1/2$, and $0\le\delta\le(1-2\beta)/2$, we prove an $\Omega_{\Delta,r,\beta}(1+Ne^{-\varepsilon})$ expected lower bound at every sufficiently large connected graph and every public source. For every fixed $r\ge2$, we give $(\varepsilon,0)$-DO sampling algorithms with expected cost $O_{\Delta,r,\beta}(1+Ne^{-\varepsilon/C})$ using constant size of hidden workspace, where $C$ depends only on $\Delta,r$ and the neighboring relation. Especially, for $r=2$, we have $C=1$, which indicates that the algorithm achieves the tight bound under all three relations. Finally, we consider repeated queries on the same graph, where the cost of protected preprocessing can be amortized across queries. For fixed $\Delta,r,\beta$, we construct a linear-size reusable index with $(\varepsilon,0)$-DO preprocessing and constant query cost. The expected preprocessing cost is linear in $N$ when $\varepsilon$ exceeds a sufficiently large constant multiple of $\log N$.
Last updated:  2026-11-04
Fine-Grained Proof Complexity for Elementary Arithmetic in Extended Frege
Andrew Krapivin, Jiatu Li, and Elaine Shi
Proof complexity has historically focused on qualitative results, such as whether natural mathematical statements (e.g. the Pigeonhole Principle) admit polynomial-size proofs in certain proof systems (e.g. Resolution or Frege). In contrast to the rich theory of algorithm design, there is little understanding of how to design quantitatively efficient proofs. We initiate the study of fine-grained propositional proof complexity. Our motivation comes from an emerging line of cryptographic constructions such as the elegant work of Jain and Jin (2022), in which the efficiency of the resulting scheme is governed by the size of the underlying Extended Frege proofs. Our main result is that the basic laws of integer arithmetic —commutativity and associativity of addition and of multiplication, together with distributivity — admit Extended Frege proofs of quasi-linear size, when addition is implemented by the schoolbook algorithm and multiplication by an FFT-based algorithm. This seemingly elementary result turns out to be surprisingly non-trivial: the natural paper-and- pencil arguments for distributivity and for associativity of multiplication translate into Extended Frege proofs of quadratic size. To reach quasi-linear size, we develop a technique we call index generalization, which we believe will find wide application in the design of efficient propositional proofs.
Last updated:  2026-11-04
Affine Advantage in Guess-type Attacks on Goldreich’s PRGs: Generalization, Characterization and Countermeasures
Ximing Fu, Mo LI, and Shihan Lyu
The recent guess-type attack (Eurocrypt'26) on Goldreich's pseudorandom generators exploits the strong bias toward constants that can arise when some inputs of majority-based predicates are fixed. This attack has demonstrated substantial effectiveness against several concrete parameter instances (Eurocrypt'24\&'25, Asiacrypt'24). In this paper, we generalize this attack paradigm to arbitrary affine approximations, characterize its capabilities, and develop a new predicate as a countermeasure. We introduce a guess-and-affine-approximation (GAA) attack framework that generalizes existing guess-type attacks from constant approximations to arbitrary affine approximations of residual nonlinear predicates. To characterize the capacity of GAA attack, we introduce the bit-fixing affine advantage $\operatorname{adv}_{b'}(M_b)$, defined as the maximum affine advantage of a $b$-ary nonlinear predicate $M_b$ over all residuals with $b'$ unfixed inputs. For polynomial stretch $m=n^s$ and logarithmic nonlinear arity $b=\gamma\log_2 n$, we obtain the optimal attack complexities $C^\star$ linking bit-fixing affine advantages: (1) $C^\star>2^{cn}$ for every $c<2^{-(s-1)/\gamma}$ iff $\operatorname{adv}_{\theta b}(M_b)\to 0$ for every constant $\theta\in(0,1]$; (2) $C^\star=2^{o(n)}$ iff fixing only $o(b)$ predicate inputs can yield a residual with affine advantage $\frac{1}{2}-o(1)$, and the sufficient direction also holds for $b=\Omega(\log n)$. In particular, if $\operatorname{adv}_{b-r}(M_b) =\frac12- O\left(\frac{\log n}{n}\right)$ for $r\le s-1$, then $C^\star$ can further decrease to $n^{O(1)}$. These results complement prior analyses for arities $O(1)$, $\omega(1)\cap O(\log n)$, and $\Omega(n^{1/s})$. Guided by the results above, we introduce the $\XOR_a$--$\MODtwelve_b$ family as a predicate candidate. We prove that every $b'$-input residual of its nonlinear component retains algebraic degree and algebraic immunity $\Theta(b')$, matching the asymptotic orders of $\MAJ$ (STOC'16). Moreover, its bit-fixing affine advantage is at most $2^{-\Omega(b')}$, whereas $\operatorname{adv}_{\theta b}(\MAJ_b)\approx \frac12$ for every fixed $\theta\in(0,1)$. Analysis shows that, for $n=1024$, $m=n^2$, and $b=54$, $\XOR$--$\MODtwelve$ can achieve $\log C^\star \approx 737$, while $\XOR$--$\MAJ$ and $\XOR$--$\MODthree$ have cost exponents of only $182$ and $599$, respectively, under the specified attack. Furthermore, our experiments show that $\MODtwelve$ offers stronger resistance to belief-propagation-based attacks.
Last updated:  2026-11-04
Refined Bounds for the Smoothing Parameter of Lattices
Shanxiang Lyu
The smoothing parameter $\eta_\varepsilon(\Lambda)$ is a fundamental invariant in lattice-based cryptography. Zheng, Zhao, and Xu (AAECC 2021) proved $\eta_\varepsilon(\mathbb{Z}) \le \sqrt{\ln(\frac{2}{\varepsilon} + \frac{\varepsilon}{44})/\pi}$ and $\eta_\varepsilon(\Lambda) \le \sqrt{\ln(n - 1 + \frac{2n}{\varepsilon})/\pi}\,\mathrm{bl}(\Lambda)$. Guo, Liu, Wang, and Tian (PLOS One 2025) proposed $\eta_\varepsilon(\mathbb{Z}) \le \sqrt{\ln(\frac{2}{\varepsilon} + \frac{\varepsilon}{m})/\pi}$ for $0 < \varepsilon \le \frac{4}{m} - \frac{172}{m^6}$ ($m \ge 3$) and $\eta_\varepsilon(\Lambda) \le \sqrt{\ln((n - 1)(1 + \frac{2}{\varepsilon}))/\pi}\,\mathrm{bl}(\Lambda)$ under $\sqrt{\frac{24n+1}{n^2-1}} \le \varepsilon \le \sqrt{2}-1$. We establish three strictly sharper bounds that uniformly dominate both while removing the artificial lower bound on $\varepsilon$. First, for $0 < \varepsilon \le \rho(\mathbb{Z})-1 \approx 0.086435$, \[ \sqrt{\frac{\ln\!\left(\frac{2}{\varepsilon} + \frac{\varepsilon^2}{4} - \frac{3\varepsilon^5}{32}\right)}{\pi}} < \eta_\varepsilon(\mathbb{Z}) \le \sqrt{\frac{\ln\!\left(\frac{2}{\varepsilon} + \frac{\varepsilon^2}{4}\right)}{\pi}}; \] since Guo et al.'s condition forces $\frac{\varepsilon}{m} > \frac{\varepsilon^2}{4}$, our bound is strictly tighter for all admissible $(\varepsilon, m)$, improving the worst-case gap from $O(\varepsilon^2)$ to $O(\varepsilon^6)$. Second, for all $n \ge 2$ and $0 < \varepsilon < \min\{1, (\rho(\mathbb{Z})-1)n\}$, \[ \eta_\varepsilon(\Lambda) \le \sqrt{\frac{\ln\!\left(\frac{2}{\delta_n} + \frac{\delta_n^2}{4}\right)}{\pi}}\,\mathrm{bl}(\Lambda) < \sqrt{\frac{\ln\!\left(\frac{2n}{\varepsilon} + (n - 1) - \frac{(n^2 - 1)\varepsilon}{6n(1 + \varepsilon)}\right)}{\pi}}\,\mathrm{bl}(\Lambda), \] where $\delta_n = (1+\varepsilon)^{1/n} - 1$; the rational bound is strictly tighter than Guo et al.'s across $100\%$ of their validity window, while remaining valid as $\varepsilon \to 0^+$. Third, for any basis $\mathbf{B}$ with Gram--Schmidt vectors $\mathbf{b}_i^*$ and $M = \max_i \|\mathbf{b}_i^*\|$, define $N_\varepsilon(\mathbf{B}) = \sum_{i=1}^n (\varepsilon/2)^{M^2/\|\mathbf{b}_i^*\|^2 - 1} \in [1, n]$; then \[ \eta_\varepsilon(\Lambda) \le \sqrt{\ln\!\left(\frac{2}{\delta_{\mathrm{eff}}} + \frac{\delta_{\mathrm{eff}}^2}{4}\right)/\pi}\,M, \] where $\delta_{\mathrm{eff}} = \frac{n}{N_\varepsilon(\mathbf{B})}((1+\varepsilon)^{1/n}-1)$. For reduced bases with geometrically decaying Gram--Schmidt lengths, $N_\varepsilon(\mathbf{B}) = O(1)$ is independent of $n$, eliminating the $O(n)$ factor inside the logarithm.
Last updated:  2026-11-04
Decentralized Multi-Authority Attribute-Based Inner-Product FE: Large Universe and Unbounded
Pratish Datta and Tapas Pal
This paper presents the first decentralized multi-authority attribute-based inner product functional encryption (MA-ABIPFE) schemes supporting vectors of a priori unbounded lengths. The notion of AB-IPFE, introduced by Abdalla et al. [ASIACRYPT 2020], combines the access control functionality of attribute-based encryption (ABE) with the possibility of evaluating linear functions on encrypted data. A decentralized MA-ABIPFE defined by Agrawal et al. [TCC 2021] essentially enhances the ABE component of AB-IPFE to the decentralized multi-authority setting where several authorities can independently issue user keys involving attributes under their control. In MA-ABIPFE for unbounded vectors (MA-ABUIPFE), encryptors can encrypt vectors of arbitrary length under access policies of their choice whereas authorities can issue secret keys to users involving attributes under their control and vectors of arbitrary lengths. Decryption works in the same way as for MA-ABIPFE provided the lengths of the vectors within the ciphertext and secret keys match. We present two MA-ABUIPFE schemes supporting access policies realizable by linear secret sharing schemes (LSSS), in the significantly faster prime-order bilinear groups under decisional assumptions based on the target groups which are known to be weaker compared to their counterparts based in the source groups. The proposed schemes demonstrate different trade-offs between versatility and underlying assumptions. The first scheme allows each authority to control a bounded number of attributes and is proven secure under the well-studied decisional bilinear Diffie-Hellman (DBDH) assumption. On the other hand, the second scheme allows authorities to control exponentially many attributes, that is, supports large attribute universe, and is proven secure under a non-interactive q-type variant of the DBDH assumption called L-DBDH, similar to what was used in prior large-universe multi-authority ABE (MA-ABE) construction. When compared with the only known MA-ABIPFE scheme due to Agrawal et al. [TCC 2021], our schemes offer significantly higher efficiency while offering greater flexibility and security under weaker assumptions at the same time. Moreover, unlike Agrawal et al., our schemes can support the appearance of the same attributes within an access policy arbitrarily many times. Since efficiency and practicality is the prime focus of this work, we prove the security of our constructions in the random oracle model against static adversaries similar to prior works on MA-ABE with similar motivations and assumptions. On the technical side, we extend the unbounded IPFE techniques of Dufour-Sans and Pointcheval [ACNS 2019] to the context of MA-ABUIPFE by introducing a novel hash-decomposition technique.
Last updated:  2026-11-04
Locally Recoverable Data Availability Sampling with Derived Group Commitments
Seunghyun Cho, Eun-Young Seo, Saehoon Jeong, and Young-Sik Kim
Data availability sampling (DAS) enables a verifier to assess whether an encoded object is available for reconstruction without downloading it in full. Nodes that accumulate partial data additionally require disjoint recovery groups that they can certify and serve independently. We present LR-DAS, which commits to the source-group restrictions of a Tamo-Barg codeword, enabling every verifier to derive each group commitment as a public linear combination of the published commitments. While leveraging a linear derivation analogous to two-dimensional KZG designs, LR-DAS evaluates each derived group on its dedicated coset of a multiplicative subgroup, requiring only one diagonal scaling per group and achieving the optimal Singleton-type minimum distance. In the reference configuration, the minimum distance is $3.91$ times that of the source-compressed product code with the same commitment size, reference string, and local serving interface, and the number of uniform samples required for a light client to detect any fixed unrecoverable withholding pattern with probability $1-2^{-128}$ decreases from $991$ to $218$. The reference string has the degree of the local dimension rather than that of the global polynomial, no Fiat-Shamir transform is used, and a node holding authenticated values at any $r$ distinct positions of a group can produce valid openings for that group without auxiliary data. Against adaptive adversaries, we prove position binding, code binding, and canonicality in the algebraic group model under a discrete-logarithm assumption with auxiliary inputs, and we show by an explicit attack that degree enforcement is necessary.
Last updated:  2026-11-04
Blockchain-Anchored Proactive Refresh for Dynamic Threshold Services
Seunghyun Cho, Jaeyeon Lee, Myeongjun Kim, Hyunseok Jeong, and Young-Sik Kim
A long-lived threshold service must issue shares to participants that join after deployment, refresh them against a mobile adversary, and allow participants offline during a refresh to recover missed updates. We show that charging exposure solely to committed epochs is fundamentally insufficient: an aborted refresh attempt that publishes candidate update tokens can reveal the secret even if no committed epoch exceeds its corruption budget. To eliminate this exposure leakage, we index security by fine-grained states covering both committed epochs and aborted attempts. Each state's budget bounds all participants whose local material or public update records originate from that state, enforced via an append-only, durable release ledger that is never rolled back upon abort. A fixed dealer committee anchors encrypted update records in blockchain blob storage, enabling non-interactive recovery for offline participants without contacting dealers, while an interactive bisection dispute protocol deterministically attributes faulty records on chain. Our core cryptographic result is an explicit distribution-preserving shift of the actual generation transcript, establishing proactive secrecy and past-share unforgeability after dealer-state disclosure without idealizing the underlying subprotocols. An end-to-end Rust implementation benchmarks complete lifecycles across up to 1,280 participants on an EVM chain, demonstrating sub-second group recovery and practical gas costs.
Last updated:  2026-11-04
A note on zero-knowledge ring switching
Andrei Kochergin
We make the ring-switching technique of Diamond and Posen zero knowledge, resolving a problem left open in the literature. Over $\mathbb{F}_{2^n}$, our technique uses $n-1$ auxiliary masks and $n-1$ quadratic constraints, checked in zero knowledge by the underlying commitment scheme.
Last updated:  2026-11-04
Correlation Power Analysis on SHA-2-Based SLH-DSA
Jinwook Chang, Minjeong Lee, JIN YONG MIN, and Dong-Guk Han
The stateless hash-based digital signature algorithm (SLH-DSA) repeatedly processes a fixed secret seed with varying public addresses. This paper presents non-profiled correlation power analysis of the address-based pseudorandom function for all six SHA-2 parameter sets, using separate recovery paths through SHA-256 compression rounds and message-schedule expansion. The procedures account for the input layout in which a 22-byte compressed address precedes the secret seed. For the 256-bit sets, a two-stage joint procedure recovers two 16-bit secret portions. We evaluate an STM32F303 ARM Cortex-M4 implementation using 30 secret seeds and 5,000 measured power traces per seed for each evaluated condition. Each recovery stage is evaluated with the required preceding secret values supplied correctly; the reported rates are therefore conditional stage-wise results, not end-to-end seed recovery rates. Compression-round stages achieve 100% success under both forest-of-random-subsets and Winternitz one-time-signature-plus address conditions. Under forest-of-random-subsets addresses, all message-schedule stages achieve 100% success for the 128- and 192-bit sets. For both 256-bit variants, joint recovery achieves 100%, whereas recovery of message word $W_{12}$ achieves 66.7%; recovery of $W_7$ achieves 70.0% and 80.0% for the fast and small variants, respectively. An alternative first stage is also provided for 128-bit Winternitz one-time-signature-plus addresses. These results show that side-channel protection must cover both compression rounds and message-schedule expansion.
Last updated:  2026-11-03
Zero-Knowledge PCPs of Quasilinear Size via Locally Simulatable Sheaf Codes
Hadas Zeilberger, Jack O'Connor, Tom Gur, and Nicholas Spooner
We show that for every polynomial $T,b \colon \mathbb{N} \to \mathbb{N}$, there exist an $O(1)$-query probabilistically checkable proof (PCP) for $\operatorname{NTIME}(T)$ of length $\widetilde{O}\bigl(T(n)+b(n)^2\bigr)$, which is $b(n)$-query perfect zero knowledge. This strictly improves on the polynomial-length zero-knowledge PCPs of Gur, O'Connor, and Spooner (STOC 2024; STOC 2025). Our construction builds on the PCPs of Ben-Sasson and Sudan (SICOMP 2008) and Dinur (JACM 2007). We prove the zero-knowledge property of our PCPs via the new machinery of locally simulatable sheaf codes.
Last updated:  2026-11-03
New Post-Quantum IBE leveraging maturity, efficiency and security of standard schemes
Julien CAM
Many Identity-Based Encryption (IBE) schemes rely on the hardness of the Discrete Logarithm Problem, making them vulnerable to quantum attacks. In recent years, lattice-based cryptography has emerged as a source of Post-Quantum cryptosystems, for example with Kyber, Dilithium and Falcon chosen by NIST to be standardized as ML-KEM, ML-DSA and FN-DSA. Some IBEs have also been proposed over lattices, but they can still be considered as interesting theoretical constructions, the community's attention having been more on the NIST competition than on optimizing IBEs, assessing their security, and protecting them against physical attacks. So, in this paper, we build a new IBE scheme from the basic blocks of the highly studied ML-KEM, ML-DSA and ModFalcon, to put both their maturity and efficiency at the benefits of IBE. More precisely, we leverage the Module-NTRU trapdoor from ModFalcon to enable extraction of secret keys, we use the encryption and decryption algorithms from ML-KEM, and the modular arithmetic and Number-Theoretic Transform from ML-DSA. Therefore, being able to reuse code from widely deployed schemes, our IBE is much easier to implement and maintain in practice, and can benefit from existing (and future) optimizations, hardware accelerators, and side-channel protections, with very little to no additional work. We also prove the IND-sID-CPA-security of our scheme under standard assumptions, and precisely describe the algorithms and the choice of concrete parameters.
Last updated:  2026-11-03
An efficient Failure Probability Estimator for LWE-based encryption, and application to IBE
Julien CAM
In recent years, lattice-based cryptography has proven to be a source of post-quantum cryptosystems. In particular, the blueprint of Learning With Errors (LWE) encryption enabled the creation of Kyber, chosen by NIST to be standardized as ML-KEM. Because of the structure of LWE encryption, the decryption of a ciphertext can give an incorrect plaintext. This event (a decryption failure) happens randomly with some probability. Since this is a problem for both functionality and security, we must ensure that this failure probability is cryptographically negligible. Usually, this is assessed with theoretical approximations and upper-bounds. The authors of Kyber used a Python program to compute that probability more precisely, enabling to fine-tune the compression of the ciphertext, hence reducing its size. However, because of its performances, this program has been limited to Kyber, and all the other schemes are still studied theoretically. In this paper, we design a more efficient Failure Probability Estimator, that we implement in low-level languages (C and CUDA C++), to reach higher parameters used in real schemes based on structured LWE. We illustrate some benefits of our tool with two Identity-Based Encryption schemes. For the first scheme, our tool allows to reduce the size of the ciphertext by about 20%. For the second one, we reduce the failure probability (thus improving security) without impacting the scheme (key size, ciphertext size, etc.).
Last updated:  2026-11-03
Provable Recovery from Integer Quotients: Improved Bounds for Nonlinear Hidden Number Problems
Taehun Kang and Changmin Lee
The hidden number problem (HNP) asks whether a secret can be recovered from partial information about values linked to it by known algebraic relations. In cryptosystems where partial information about secret values or internal randomness is leaked across various scenarios, HNP techniques provide a foundational framework for security analysis and key-recovery attacks. For some HNPs with nonlinear relations, provable polynomial-time recovery guarantees have long remained unimproved, requiring a substantial fraction of the leading bits. We extend the provable recovery ranges for the modular inversion HNP (MIHNP), elliptic curve HNP (EC-HNP), and HNP with hidden multipliers (HNPHM), all modulo a prime $p$. For any sufficiently small constant $\varepsilon > 0$, we increase the tolerable fraction of unrevealed lower bits: for MIHNP, from $1/3-\varepsilon$ to $1/2-\varepsilon$; for EC-HNP, from $1/6-\varepsilon$ to $1/5-\varepsilon$; and for HNPHM, from $1/5-\varepsilon$ to $1/3-\varepsilon$. Our algorithm constructs polynomials that vanish modulo $p$ at the unrevealed lower bits, and reduces recovery to bounding their possible integer quotients by $p$ over the candidate range. While such a search can branch in general, we exploit the algebraic relations of each problem to prove that the expected search cost remains polynomial in $\log p$ over randomly sampled inputs. On every valid input, the algorithm returns the exact set of consistent secrets, achieving unique recovery with probability $1-o(1)$ as $p \to \infty$ for every fixed secret.
Last updated:  2026-11-03
Information Loss Is All You Need: TC⁰ Pseudorandomness from Worst-Case Lattices
Chen Qian
Pseudorandomness plays a central role in algorithms, complexity theory, and cryptography. We ask whether deterministic information loss alone can yield post-quantum pseudorandomness with $\mathrm{TC}^0$ evaluation. Learning with errors (LWE) hides linear measurements with random noise. Learning with rounding (LWR) replaces noise with deterministic rounding, but a standard polynomial-modulus hardness reduction requires parameters tailored to a predetermined sample bound. Decisional Diffie–Hellman offers a noiseless algebraic route to pseudorandomness, but its standard instantiations are vulnerable to quantum algorithms. We show that deterministic rounding achieves this under quantum worst-case lattice hardness, with fixed polynomial parameters and no predetermined sample bound. We introduce the learning with algebraic rounding (LAR) assumption, which applies an explicit integer rounding map to blocks of secret-dependent linear measurements and encodes the result in a lattice quotient. For one fixed family with polynomially bounded modulus and dimensions, its deterministic labels on exactly uniform, secret-independent public matrices are computationally indistinguishable from independent uniform labels for every polynomial number of classical random examples. Our classical reduction from Gaussian LWE, combined with the quantum worst-case reduction to LWE, bases LAR on GapSVP and SIVP over general lattices at approximation factor $\widetilde{O}(q)$, where $q$ is the modulus. To prove this, we develop a source-independent affine transport framework that may be of independent interest. Using public affine maps sampled independently of the hidden errors, it transports the Gaussian error law close to uniform on the rounding map’s zero-label fiber while preserving exactly uniform public matrices. For every fixed inverse-polynomial accuracy, we give a polynomial-time sampler for the same public parameter family. This yields the first post-quantum weak pseudorandom function with joint key-and-input evaluation in $\mathrm{TC}^0$, secure against uniform quantum polynomial-time distinguishers given any polynomial number of classical uniform random examples. We also establish the hardness of learning polynomial-size two-hidden-layer ReLU networks from noiseless uniform random examples, even for quantum polynomial-time improper learners.
Last updated:  2026-11-03
Beholder Signatures
Stefan Dziembowski, Sebastian Faust, Paweł Kędzior, Marcin Mielniczuk, Susil Kumar Mohanty, and Krzysztof Pietrzak
We introduce a new primitive, called beholder signatures, which, in some sense, are the opposite of blind signatures. In a beholder signature, one signs a commitment to a (potentially very long) message, and the signature attests that the parties participating in the signing process who know the secret key, jointly also know the entire committed message. This guarantee holds even against distributed adversaries that use secure multi-party computation (MPC) to produce the signature. We work in the distributed adversarial model (Dziembowski, Faust, and Lizurej, Crypto'23), where one assumes that it is infeasible to evaluate a large number of hash queries without any of the participating parties learning the input. We propose a construction of beholder signatures in the random oracle model. The starting point of our construction is proofs of complete knowledge, recently proposed by (Kelkar et al. CCS'24), which again build on Fischlin's transformation of a sigma protocol to a noninteractive, straight-line extractable zero-knowledge proof of knowledge. Our scheme is concretely efficient and comes with a proof-of-concept implementation using Schnorr as the underlying sigma protocol. The primary applications of beholder signatures can be found within the blockchain ecosystem. In particular, we describe how to use them to construct proofs of custody (Feist, 2021) that do not require ephemeral keys and are noninteractive. We also outline applications to data dissemination, data availability, and proofs of replication.
Last updated:  2026-11-03
Making Uncertified DAG BFT Provably Live with Linear Payload and Quadratic Metadata Communication
Nikita Polyanskii, Sebastian Mueller, and Ilya Vorobyev
Uncertified partially synchronous DAG BFT protocols such as Mysticeti achieve the lowest latency among DAG protocols by omitting per-block quorum certificates, but they lack rigorous liveness proofs: honest parties can desynchronize and never commit a leader again, even under synchrony. To avoid the quadratic communication cost of pushing full blocks, production implementations pull missing ancestors, which results in consensus request amplification, large tail latency, and vulnerability to Byzantine dissemination. We present Starfish, whose new Push pacemaker gives uncertified DAGs their first rigorous liveness proof, together with safety proofs and latency bounds in the actual message delay δ. Starfish makes Push practical by separating payloads from headers: parties push headers and Reed-Solomon fragments, data-availability certificates form on the DAG itself, and worst-case payload communication becomes linear, at the cost of increasing transaction latency by one round. We also show how multi-signatures and delayed history pushes can be applied to Starfish and Mysticeti, resulting in new protocols with quadratic happy-case metadata communication, the lowest among partially synchronous DAG BFTs. Without faults, at 100 validators on a synthetic WAN, Starfish sustains ≈257k tx/s at sub-second median latency against Mysticeti's ≈190k. Controlled experiments show that Byzantine selective dissemination can drive honest-transaction median latency under Pull to tens of seconds in both protocols; under Push dissemination, Starfish holds it within about two seconds across the whole fault range, at substantially lower communication cost than Push on Mysticeti. Starfish has replaced Mysticeti on a public blockchain's mainnet. An observational study comparing each validator with itself across the switch finds per-validator consensus requests down 86% and p99 consensus latency down 27%; well-connected validators pay the added round at +16% consensus latency, and bytes sent per sequenced byte rise by 133%.
Last updated:  2026-11-03
Decentralized Multi-Authority ABE for NC^1 from Computational-BDH
Pratish Datta, Ilan Komargodski, and Brent Waters
Decentralized multi-authority attribute-based encryption (𝖬𝖠-𝖠𝖡𝖤) is a strengthening of standard ciphertext-policy attribute-based encryption so that there is no trusted central authority: any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. Essentially, any party can act as an authority for some attribute by creating a public key of its own and issuing private keys to different users that reflect their attributes. This paper presents the first 𝖬𝖠-𝖠𝖡𝖤 proven secure under the standard search variant of bilinear Diffie-Hellman (CBDH) and in the random oracle model. Our scheme supports all access policies captured by 𝖭𝖢1 circuits. All previous constructions were proven secure in the random oracle model and additionally were based on decision assumptions such as the DLIN assumption, non-standard 𝑞-type assumptions, or subspace decision assumptions over composite-order bilinear groups.
Last updated:  2026-11-03
Shielded Bitcoin: Private Transfers on the Bitcoin L1
Clara Shikhelman, Mikhail Komarov, and Aleksei Moskvin
This paper introduces Shielded Bitcoin, a protocol for private transfer of Bitcoin directly on the Bitcoin L1, requiring no changes to Bitcoin consensus. Its design borrows from the architecture of Zcash and earlier shielded-note systems: value is held as encrypted notes, spends are marked by public nullifiers, and validity is established by zero-knowledge proofs. Unlike Zcash, Shielded Bitcoin introduces no dedicated consensus chain: all protocol data is published on Bitcoin, transfer validity is enforced through PIPEs v2 [ACG+26], and shielded state is reconstructed by deterministic replay of accepted transfers in Bitcoin order. At the metaprotocol transfer level, Shielded Bitcoin is non-custodial: spending authority remains with user-controlled wallet keys encrypted in a ciphertext, and neither indexers nor the replay layer receive authority to spend user notes. A shielded transfer does not publicly reveal its amount, sender, receiver, and place in the transfer graph, while keeping the validity of every encrypted state transition publicly verifiable. Shielded state, comprising the note tree, nullifier set, and block-level root history, is maintained entirely off-chain: any two correct implementations replaying the same Bitcoin history derive identical protocol state without coordination. The paper defines the transfer model, note structure, ciphertext-derived note leaves, nullifier rules, transaction binding, replay semantics, and publication assumptions. Peg-in and peg-out, the mechanisms by which value enters and exits the shielded transfer system, belong to the broader system and fall outside the scope of this paper.
Last updated:  2026-11-03
A Toolkit for Succinct Lattice-Based Zero Knowledge Proofs
Beatrice Biasioli, Madalina Bolboceanu, Vadim Lyubashevsky, Antonio Merino-Gallardo, Michał Osadnik, Gregor Seiler, and Patrick Steuer
The development of proof systems whose security relies on the hardness of lattice problems has been a fruitful research area in recent years. By leveraging the techniques introduced in LaBRADOR (Beullens, Seiler, Crypto 2023), the state-of-the-art lattice-based schemes have very fast provers and have output sizes under 100KB for arbitrarily large statements. These proofs are in fact the smallest, and often have the fastest provers, out of all post-quantum schemes. In addition to succinctness, many applications also require witness privacy. Achieving this can, in theory, be done by combining LaBRADOR with a linear-size zero-knowledge proof. While such a combination has already been described in the LaBRADOR paper itself, as well as in the works of Albrecht et al. (Eurocrypt 2024) and del Pino et al. (Crypto 2025), its concrete costs remained unexplored. In this work, we provide the first concrete construction and implementation that adds zero-knowledge proofs to LaBRADOR by integrating the linear-size zero-knowledge proof from (Lyubashevsky, Nguyen, Plançon, Crypto 2022) into the protocol. We describe the non-trivial challenges that this entails and show practicality of the construction by benchmarking several use-cases. We make the proof system and primitives accessible by extending the LaZer library (Lyubashevsky, Seiler, Steuer, CCS 2024) in a way that they can easily be used in other applications.
Last updated:  2026-11-03
TFNP in the Random Oracle Model
Noah Fleming, Mika Göös, Ziyi Guan, Oliver Korten, Daniel Mitropolsky, Toniann Pitassi, Artur Riazanov, Dmitry Sokolov, Tianqi Yang, and Weiqiang Yuan
We determine which major TFNP classes are hard in the random oracle model (ROM). Prior work establishes average-case hardness of highly structured subclasses of TFNP from strong cryptographic assumptions such as LWE and indistinguishability obfuscation. It is not known whether weaker assumptions such as one-way functions imply hardness of any of the standard TFNP subclasses, even in the worst case. The ROM, where all parties have query access to a random function, lies, morally, between these two regimes: a random function is one-way, but public-key cryptography cannot be built from it in a black-box way. We refer to this setting as \emph{Romantica}. Our first result settles a long-standing open problem: PPAD, the class of total search problems reducible to finding a Nash equilibrium, is hard on average in Romantica. Combined with the known hardness of PLS (local search), this gives average-case hardness of EoPL = PPAD \cap PLS. In contrast, we show that UEoPL can be solved in Romantica with polynomially many oracle queries by a computationally unbounded solver, a sharp distinction between EoPL and UEoPL. This resolves the black-box hardness landscape of all major TFNP classes in Romantica. Finally, we initiate the study of separations between TFNP subclasses in Romantica: PWPP and PPA do not reduce to PLS under \emph{public-coin} reductions.
Last updated:  2026-11-03
Orthus: Practical Sublinear Batch-Verification of Lattice Relations from Standard Assumptions
Madalina Bolboceanu, Jonathan Bootle, Vadim Lyubashevsky, Antonio Merino-Gallardo, and Gregor Seiler
The past several years have seen a rapid rise in practical lattice-based proof systems with linear-sized zero-knowledge proofs forming the foundation of many of the most efficient quantum-safe privacy protocols, and succinct proofs rapidly catching up and surpassing other quantum-safe alternatives in many metrics. A recent comparison of lattice-based aggregate signatures (Ethereum Foundation, 2025) involving the hash-based aggregate signature scheme Plonky3 and the instantiation of aggregate signatures from Falcon from the LaZer lattice library (Lyubashevsky, Seiler, Steuer, CCS 2024) using LaBRADOR (Beullens, Seiler, Crypto 2023), showed that lattice-based constructions have an advantage in terms of proof size and prover time, but are around an order of magnitude slower with regards to verification time. In general, it appears that slower verification times are the main obstacle to the adoption of succinct lattice-based proof systems. In this work, we introduce and implement Orthus, a proof system with sub-linear verification designed for relations that naturally arise in lattice-based constructions. Asymptotically, the verification time grows with the square root of the witness size, and for a concrete example of aggregating Falcon signatures our implementation reduces the verifier running time by a factor of $9X$ when aggregating $2^{17}$ signatures.
Last updated:  2026-11-03
Quantum Evolving Secret Sharing - revisited
Efrat Cohen and Anat Paskin-Cherniavsky
In evolving secret sharing, introduced by Komargodski et al., an infinite set of parties share a secret according to an infinite access structure (where minimal qualified sets are finite). In such schemes, par- ties arrive one by one, and and are given a share by the dealer. There is no additional communication incurred to a given party until the time of reconstruction, where share holders who show up combine their shares to reconstruct the secret if they form a qualified set. In this work, we revisit the notion of quantum evolving secret sharing schemes, we dub QESS, where a quantum secret is shared. Smoothly generalizing the above setting runs into difficulties due to the no-cloning theorem. In particular, values handed to previously arriving parties can not be copied by the dealer and used in the evaluation of future parties’ shares, as often done in evolving secret sharing schemes from the liter- ature. Indeed, attempts to formalize quantum evolving secret sharing, such as that on Chaudhury for the so called dynamic threshold setting and by Cohen et al. for general evolving access structures fell short from adhering to the minimally interactive communication pattern above. In this paper, we take a different approach, and consider a setting where several (possibly infinitely many) copies of a secret (known to the dealer) are generated by need. This approach has been used by Cakan et al. for (finite) quantum secret sharing (QSSS), allowing to circumvent the im- possibility of devising QSSS for monotone access structures which are not no-cloning - those that have disjoint pair of qualified sets. This setting is plausible in many applications, where the secret is known to the dealer at sharing time. Cakan et al. demonstrate that at most n copies of the secret prepared by the dealer, suffice to implement any monotone access structure. In the evolving setting, it is not clear how to devise QESS even for evolving no-cloning access structures. Introducing multiple copies of the secret allows to define QESS with a communication pattern similar to the classical setting, in which arbitrary (not necessarily no cloning) evolving access structures can be implemented. using c(t) ≤ t copies of the secret used to generate the shares of the first t parties - similarly to the finite setting. We study the copy number landscape for various evolving access struc- tures. For general access structures, c(t) ≤ t copies of the secret suffice to generate the shares of the first t parties - similarly to the finite setting. On the lower bound side, the no-cloning theorem implies c(t) = t is nec- essary for QESS. The main question we leave open is whether a single copy suffices for no-cloning evolving access structures, while 1 is the ex- act number of the finite setting. We prove that every no-cloning evolving access structure has a QESS with a finite copy number c(t) ≤ C, where the constant C depends on the particular access structure. Furthermore, for every T0, there exists a QESS as above with c(t) ≤ 1 for t ≤ T0. Our techniques generalize the hybrid technique of Cakan et al. abstract- ing their implicit approach of treating the access structure as a union of no-cloning access structures, and implementing each via exiting quantum erasure codes (QECC), which provide not privacy. Then, a copy of the secret, masked by a classical random key (via QOTP) is encoded by each of these codes. The classical keys are then classically shared via each of the access structure to provide privacy. While they rely on a union of no-cloning threshold access structures, we use arbitrary ones. This often reduces the resulting copy number already in the finite setting. Special care is required to share the QOTP keys for each access structure in the union, while keeping every party’s share finite.
Last updated:  2026-11-03
A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem
Daniel R. Simon
We present a polynomial-time quantum algorithm for the Dihedral Coset Problem (DCP). The algorithm is based on Regev's polynomial-time reduction of the Dihedral Subgroup Problem (DSP) to the modular subset sum problem, but uses a different technique to erase sample bits without use of a subset sum oracle. The algorithm can thus combine with Regev's reduction of lattice problems to DCP, improved by Brakerski, Kirshanova, Stehl{\'e} and Wen, to yield polynomial-time quantum algorithms for various lattice problems, such as finding a polynomial-factor approximation to the shortest vector in an $n$-dimensional lattice (SVP), and the ``learning with errors'' problem (LWE). The algorithm can tolerate a faulty sample rate as high as $1/O(\log{n})$, allowing the algorithm-reduction combination to efficiently solve, for example, SVP with a $\sqrt{n}$ polylog($n$) approximation factor, or LWE instances with $\alpha=\sqrt{n}$ polylog($n$). Note: The proof of Lemma 3 in the first draft incorrectly conflated pairwise independence over the uniform vs. actual distribution on D. The proof has been substantially updated, and now distinguishes clearly between them. Additional note: A new preprint, https://eprint.iacr.org/2026/1693, has been posted claiming to prove that the algorithm in this paper can't possibly work. We're in the process of evaluating it. Additional note October 7/26: The preprint has been updated with a note addressing the claims in https://eprint.iacr.org/2026/1693, as well as clarifications to the proof of Lemma 3 in response to comments by Sam Jaques. Additional note November 3/26: The note mentioned above has been updated with edits for greater clarity. The paper has also been reformatted.
Last updated:  2026-11-03
Differential Cryptanalysis of SPEEDY: Revised Security Evaluation and Improved Key Recovery Attack
Xinwei Yu, Wentao Zhang, Zairui Zhang, and Chunning Zhou
The resistance of a block cipher against differential cryptanalysis (DC) is a fundamental criterion for evaluating its security. SPEEDY is a family of low-latency SPS-type block ciphers designed by Leander et al. The designers presented two evaluations of SPEEDY against DC: the first restricted 1-bit-to-1-bit differential propagations through the S-box and used the higher-order branch numbers to estimate the maximum expected differential probability (EDP) of differential trails; the second imposed a structural restriction and assumed that all 1-bit-to-1-bit propagations through an active S-box are possible to estimate the minimum number of active S-boxes. Zhang later exhibited a counterexample to the designers' first evaluation and introduced the notion of partition branch number, relaxing some of the propagation restrictions to allow multi-bit-to-1-bit transitions on some S-box layers and refining the evaluation. However, these evaluations consider only restricted spaces of differential characteristics and therefore inaccurately estimate the security of SPEEDY against DC, which means that the resistance of SPEEDY against DC remains unclear so far. To address this problem, we propose an efficient search method based on search patterns. Unlike previous evaluations, our method imposes no a priori structural restrictions on the allowed differential characteristics; it uses computational pruning to keep the search tractable and performs a conservative security evaluation of the pruned region, thereby providing an accurate evaluation over the global space. At the framework level, we decompose an r-round differential characteristic into an (r-1)-round core trail and an r-round extended trail. By extending a core trail independently at both ends, the two additional S-box layers are handled by two separate models, each containing only one S-box layer and solvable efficiently. At the implementation level, we further introduce a short-round reuse via hash-map concatenation technique, which concatenates short-round core trails to construct longer-round core trails, thereby avoiding expensive long-round MILP models. For 4 rounds, we narrow the minimum number of active S-boxes from the previously reported 35 to [33,34] and find a characteristic with 34 active S-boxes outside the previous search spaces. We also obtain the highest-probability differential characteristics known to date for 2 to 5 rounds. In particular, the 2-, 3-, and 4-round characteristics disprove the designers' branch-number-based security claims. Furthermore, using the quasidifferential framework, we evaluate the found characteristics and obtain several 5-round distinguishers outperforming those used in existing key recovery attacks in terms of EDP. Finally, we optimize the probabilistic extension parameters used in a previous key recovery attack, which yields the best known key recovery attack on SPEEDY-7-192, with data complexity $2^{173.48}$ and time complexity $2^{173.69}$ encryptions.
Last updated:  2026-11-03
Toward Provable Security in Anamorphic Extension: New Constructions and Analysis
Nabanita Chakraborty and Ratna Dutta
Anamorphic encryption (AE) enables covert communication in adversarial settings where the receiver’s secret key may be exposed to a coercive adversary. Although existing AE constructions demonstrate the feasibility of this paradigm, their covert bandwidth rates are severely limited, particularly when built from conventional public-key encryption (PKE) schemes. This work develops a systematic approach to constructing bandwidth-efficient anamorphic extensions of residuosity-based PKEs. We first present a robust bit-wise anamorphic extension of the Goldwasser-Micali cryptosystem and a block variant that substantially improves covert throughput. We then construct an anamorphic extension of the Benaloh cryptosystem using an explicit, uniquely decodable embedding of covert messages together with a redundancy tag for robustness. Beyond individual constructions, we introduce a general Δ-structured public-key encryption framework that captures the common algebraic structure enabling anamorphic extensions and instantiate it with block Goldwasser-Micali, Paillier and Damgård-Jurik encryption. We further provide a formal analysis of key deniability, robustness, message loss and windowed decryption, counter-reuse attacks and forward security against subsequent sender coercion. The security of our constructions is established through IND-NA reductions to pseudorandom-function security. At the 128-bit security level, our Benaloh, block Goldwasser-Micali and Paillier constructions achieve approximately 0.46-0.48 covert bits per ciphertext bit under the comparison metric considered, demonstrating a substantial bandwidth improvement over the representative prior approaches. Overall, the proposed framework provides a unified foundation for designing efficient anamorphic extensions of structured public-key encryption schemes.
Last updated:  2026-11-03
The Price of Agreement in Secure Multiparty Computation
Ran Cohen, Pouyan Forghani, Juan Garay, and Vassilis Zikas
Secure multi-party computation (MPC) cannot guarantee output delivery, in general, in the dishonest-majority setting. Security of MPC is therefore relaxed to security with abort, where the adversary may prevent honest parties from obtaining their output. The standard notion of \emph{unanimous abort} (UA-MPC) ensures that either all honest parties obtain their output or all of them abort. Goldwasser and Lindell [JCRYPT '05] introduced the relaxed notion of \emph{selective abort}, allowing some honest parties to abort and others to obtain their output. While two-round SA-MPC can be achieved over point-to-point channels, two-round UA-MPC necessitates the second round to be over broadcast. The price of agreement in dishonest-majority MPC is thus tied to the round complexity of broadcast with unanimous abort (UA-broadcast). The round complexity of broadcast has been extensively studied for more than four decades. Garay, Katz, Koo, and Ostrovsky [FOCS '07] (GKKO) proved that the expected round complexity of broadcast protocols tolerating $t$ corruptions is at least $2n/(n-t)-1$. Their argument, however, relies on all honest parties obtaining an honest sender's input, and does not extend to UA-broadcast. Recently, Cohen {\em et al.} [TCC '26] showed that UA-MPC is possible in an expected constant number of rounds when a constant fraction of the parties is honest, and asked whether this extends to $n-o(n)$ corruptions. In this work we answer this question in the negative: Agreement alone already incurs the GKKO barrier. Concretely, we prove that for $t\leq n-2$, UA-broadcast---and hence UA-MPC---requires at least $t/(2(n-t))$ rounds in expectation, matching the asymptotic bound for broadcast without abort. As a corollary, expected-constant-round UA-MPC is possible if and only if a constant fraction of the parties is honest. Next, we consider UA-broadcast protocols that terminate in an {\em a-priori} known round, and show that the bound that the argument of GKKO gives for broadcast holds for them exactly. Combined with the broadcast protocol of Dolev and Strong [SICOMP '83], our bound is tight for arbitrarily many corruptions.
Last updated:  2026-11-03
Phantom Timing Leaks on Cortex-M4: A Pre-registered Evaluation of ML-KEM Decapsulation
Amadou Tidiane Anne
Fixed-versus-random timing tests in the style of dudect are a cheap first check of constant-time behaviour, and on microcontrollers the cycle counter makes them exact to the cycle. We report a pre-registered evaluation of ML-KEM decapsulation on an STM32F411 (Cortex-M4) covering nine implementations of PQM4 (clean, m4fspeed, m4fstack for ML-KEM-512/768/1024) and a positive control in which we restored the pre-KyberSlash division formulas. Each of the 44 campaigns used in the analysis has 100,000 trials and checks every result. With invalid ciphertexts (random bytes, or one modified byte), no difference is detected in 18 of 18 campaigns, and both classes always have exactly the same cycle count, while the control is detected every time (|t| up to 1,877). With fresh valid ciphertexts, however, all nine implementations are flagged, with differences of 4 to 15 cycles and |t| >= 19,000 (or infinite, when both classes have zero variance). A matched control, in which both classes run the same code before the measured call, removes the difference for seven of the nine. An A/A test, in which both classes decapsulate the same bytes, still yields |t| = 12,864 for one implementation. Deterministic few-cycle differences can therefore come from the measurement harness alone: on a part with flash wait states, an instruction cache and prefetching, they can appear when the code around the measured call changes. We also show that per-trial correctness checks matter: they exposed a functional bug in PQM4's ML-KEM-1024 m4fstack (220 wrong shared secrets out of 49,830), which upstream had fixed shortly before. We report every deviation from the pre-registration, including a build error of our own, and publish data, binaries and code (https://doi.org/10.5281/zenodo.23921418).
Last updated:  2026-11-03
Challenge Binding in FRESCO SPDZ2k: A Message-Level Case Study
Mingzhao Huang
FRESCO's SPDZ2k suite derives its batched MAC-check coefficients from a setup-time public seed, making the stream predictable before opening shares are sent. We examine this implementation path at a pinned revision. A source-level derivation accounts for low-limb carries and high-bit corrections and shows that the value-share shifts $e=(r_j,-r_i)$ preserve the check residual while retaining the original MAC shares. A message-level harness executes this deviation against unmodified honest opening code. The recorded sum/product outputs violate a relation required for every possible input of the corrupt party, and the test framework records normal completion. The retained evidence includes two-, three-, and four-party executions with dummy preprocessing. The predictable-seed attack template appears in Rushing at SPDZ, and FRESCO's issue tracker recorded the per-check randomness requirement in 2018; our contribution is the SPDZ2k public-seed path, its explicit kernel witness, and the implementation evidence. We also give a conditional single-opening analysis and assess a four-file candidate mitigation that rejects seven recorded tampering scenarios while preserving four honest baselines. Audit tools and descriptive corpora provide context. The proof concerns the specified value-share deviation; unrestricted malicious behavior, production preprocessing, and a complete mitigation argument remain outside the established result.
Last updated:  2026-11-03
Differentially $2^t$-uniform quadrinomials with high nonlinearity
Niki Spithaki, Enrico Piccione, Lilya Budaghyan, and Alexander Kholosha
In this paper, we discuss some cryptographic properties of a family of quadrinomials constructed as a generalization of a known family of APN quadrinomials. In particular, we show that this family produces differentially $2^t$-uniform quadrinomials with the same Walsh spectrum as the Gold power function $x^{2^t+1}$ over $\mathbb{F}_{2^n}$. We also discuss whether this family provides permutations.
Last updated:  2026-11-03
AsyRand: An Asynchronous Randomness Beacon via Look-Ahead Agreement
Liang Zhang, Binyang Hou, Zhengxuan Guo, Haibin Kan, Jiheng Zhang, and Moti Yung
Asynchronous randomness beacons must preserve agreement and sustain output generation despite Byzantine faults while preventing adversarial bias. We present $\mathsf{AsyRand}$, a publicly verifiable randomness beacon that combines publicly verifiable secret sharing (PVSS) with local-coin asynchronous binary agreement (ABA). Its Producer-Consumer design overlaps PVSS preparation with beacon generation and consumes one accepted PVSS object per output. Column agreement amortizes coordination across multiple outputs. Its look-ahead agreement fixes the successor column's accepted contributions before current contributions are revealed, while recent-contributor exclusion ensures an honest contribution in every $f+1$ consecutive outputs, where $f$ bounds the number of Byzantine parties. Under a production window $\ge2$, every fixed epoch completes with probability one. These mechanisms, together with PVSS secrecy and beacon chaining, provide unpredictability and bias resistance for fixed targets at least $f+1$ epochs ahead. The communication complexity is $O(n^2)$ per output in the optimistic case. We instantiate $\mathsf{AsyRand}$ using ALBATROSS PVSS (Cascudo et al., ASIACRYPT'20) and WaterBear Quadratic-ABA (Zhang et al., Usenix Security'23). Experiments with 16--121 parties across eight regions show that $\mathsf{AsyRand}$ achieves higher throughput than our implementations of GRandLine (Bacho et al., CCS'24) and SPURT (Das et al., S\&P'22). In the fault-free case, at 121 parties, $\mathsf{AsyRand}$ achieves $1.66\times$ and $14.03\times$ their respective throughput.
Last updated:  2026-11-03
Leakage-Resilient Computation via Matrix Refreshing
Stefan Dziembowski and Sebastian Faust
Leakage-resilient cryptography protects secrets against side-channel attacks, in which a physical implementation reveals partial information about its internal state. A fundamental primitive in this area is a leakage-resilient storage, which allows a secret to be stored in a way that remains secure even if an adversary learns some information about the storage's internal state. A popular approach represents a secret as the inner product of two $n$-bit vectors, called shares. The shares are stored and processed separately by two parts of the implementation, called the left and right parties. Because leakage accumulates over time, the shares must be refreshed repeatedly. We prove that a simple refresh, in which the left party multiplies its share by a uniform invertible matrix $M$ and the right party multiplies its share by $M^{-1}$, is secure under continual local leakage. After $T$ refreshes, each allowing at most $\lambda$ bits of leakage per party, the transcripts for two stored secrets are at statistical distance at most $C\cdot T\cdot 2^{6\lambda-n/9}$ for an absolute constant $C$. We also obtain a Boolean-circuit compiler with statistical privacy error at most $C\cdot S\cdot 2^{18\lambda-n/27}$ for $S$ operations and at most $\lambda$ bits of local leakage per party per operation. The guarantee covers repeated stateful evaluations with adaptively chosen public inputs, with $S$ counting all operations across invocations. Thus, for polynomial-size circuits, a constant leakage fraction is tolerated with share length depending only on the security parameter. We formalize the refreshing bound, the composition and compiler guarantees, and the expected-work bounds in Lean 4. Our results also provide efficient simulation: the leakage can be reproduced from the public inputs and the circuit outputs alone, with expected polynomial overhead.
Last updated:  2026-11-03
Mutual Correlated Agreement and List-Decoding: Improvements and Separations
Ignacio Manzur
At a high level our contribution is threefold: we improve the quantitative MCA error bound for polynomial generators, we prove a refinement of the implication from list-decodability to MCA, and we clarify that in general, these two notions are distinct. We show that, for every finite field $\mathbb{F}$, every nonempty seed set $S\subseteq\mathbb{F}$, every linear code $\mathcal{C} \subseteq \mathbb{F}^{n}$ of relative minimum distance $\delta_{\mathcal{C}}$ and every degree $d \geq 1$, the univariate powers generator $G_{d}(x) := (1,x,\dots,x^{d})$ has mutual correlated agreement for $\mathcal{C}$ at relative proximity parameter $\gamma$ with error $O(d\max\{1,n\gamma\}/|S|)$ below the smaller of the unique decoding radius and the generalized Johnson radius $J_{d+2}(\delta_{\mathcal{C}}) := 1-(1-\delta_{\mathcal{C}})^{1/(d+2)}$, with a one-coordinate margin below the latter when it is smaller. Then, we show that list-decodability at radius $p$ with list size $L$ implies MCA slightly above $1-\sqrt{1-p}$ (the improvement on the radius is dependent on the list size). The previous state-of-the-art result of Gao, Cai, Xu and Kan showed that list-decodability at radius $p<\delta_{\mathcal{C}}$ with list size $L$ implies mutual correlated agreement at every proximity parameter strictly below $1-\sqrt{1-p}$. Finally we construct two families of codes that show obstructions to any improvement of the $1-\sqrt{1-p}$ bound, or to strong converse statements. Informally, a bound of the form $\epsilon_{\mathsf{MCA}}(1-(1-p)^\alpha)\leq Q(n, L)/|\mathbb{F}|$ for some polynomial $Q$ and $\alpha > 1/2$ cannot hold for all linear codes $\mathcal{C}$ under the sole hypothesis that $\mathcal{C}$ is $(p,L)$-list-decodable. Similarly, for any distance $0<\delta<1$ and any $1-\sqrt{1-\delta}<p<\gamma<1$, there exists a family of linear codes with fixed positive rate and relative distance tending to $\delta$ such that $|\mathbb{F}|\epsilon_{\mathsf{MCA}}(\gamma)\leq \mathrm{poly}(n)$ but the list size at radius $p$ is $n^{\omega(1)}$. Both counterexample families exist over fields of any characteristic. Both MCA errors are for the line generator.
Last updated:  2026-11-03
The Generalised Tate Pairing over any field
Jonathan Komada Eriksen
We generalise a pairing on elliptic curves over finite fields, called the generalised Tate pairing, which is defined in terms of an arbitrary endomorphism of the curve, with certain trace requirements. We rederive this pairing from group cohomology, which allows us to generalise the pairing to principally polarized abelian varieties over any field, endomorphisms of any trace, and prove perfectness using a general duality theorem.
Last updated:  2026-11-03
Dual Coppersmith: Finding Small Roots Without Multivariate Polynomial Systems
Taehun Kang, Jebin Kim, Changmin Lee, and JeongHwan Lee
The multivariate Coppersmith algorithm is a central tool in public-key cryptanalysis for finding a small hidden root of modular polynomial equations. It consists of two stages. First, a lattice-reduction (LR) stage constructs auxiliary equations satisfied by the hidden root over $\mathbb Z$. Second, a root-recovery (RR) stage solves these equations. The RR stage can be a bottleneck: auxiliary polynomials may not isolate the root, and solving them can take exponential time in the worst case, even when LR is feasible. We introduce Dual Coppersmith, which replaces algebraic root recovery with geometric recovery from a modular orthogonal lattice. Our construction embeds the hidden root as a short lattice vector, and we prove that LLL recovers its direction whenever a sufficient gap separates it from all independent lattice vectors. The root can then be recovered directly from coordinate ratios. To analyze this gap, we propose a heuristic model for the second successive minimum by examining both the full lattice and a structured sublattice. Under this model, Dual Coppersmith achieves the standard Coppersmith product-size bound without solving an auxiliary polynomial system. Experiments on the approximate common divisor (ACD) and Herrmann-May (HM) problems support the model's predictions and demonstrate root recovery in higher-dimensional instances where the Gröbner-based baseline reaches its timeout.
Last updated:  2026-11-03
Optimizing Two-Step Primal LWE Attacks with PnJBKZ Simulation
Wenwen Xia, Leizhang Wang, GengWang, Dawu Gu, and Baocang Wang
Learning with Errors (LWE) and its variants underlie many lattice-based cryptosystems, making accurate concrete attack-cost estimates important for parameter selection. Practical primal attacks combine lattice-basis reduction with a final shortest-vector search, and their performance depends strongly on how these components are scheduled. We formalize the two-step strategy space considered in this work and propose PSSearch, a pruning-based method that selects a minimum estimated cost strategy under a specified reduction simulator and cost model. We instantiate the framework with a Pump-and-Jump BKZ (PnJBKZ) simulator supporting jump parameters \(J>1\), practical dimension-for-free settings, and LLL effects, together with a refined estimator for the dimension of the final SVP call. We integrate these components into a practical solver in G6K-GPU-Tensor and compare the PSSearch-selected strategies with its default heuristic strategy under comparable settings. On six TU Darmstadt LWE Challenge instances, the selected strategies achieve speedups of \(7.2\times\)--\(23.4\times\). Under the stated primal-attack and classical gate-count assumptions, the optimized two-step primal estimates for selected ML-KEM and ML-DSA parameter sets are \(3.4\)–\(4.6\) bits below the corresponding previous estimates; relative to the prescribed two-step baseline \(\mathsf{S}_0\), PSSearch provides an additional \(1.2\)–\(1.3\)-bit reduction. Along the tested relation \(\log_2 q=0.198n^{0.832}\), the empirically fitted advantage satisfies \(\Delta(\log_2T)=0.01887n-0.98\), where \(T\) denotes the estimated attack cost. These figures concern the primal-attack branch; the overall attack-cost estimate is determined by the minimum cost among all applicable attack families.
Last updated:  2026-11-03
Exploring Fault Injection Attacks on HQC and BIKE Beyond Fujisaki-Okamoto Verification
Thales B. Paiva, Lucas C. Cardoso, Keerthi Kamalakshan, Hariprasad Kelassery Valsaraj, Marcos A. Simplicio Jr., and Shivam Bhasin
Fault injection attacks have been extensively studied in the context of post-quantum cryptography, yet existing analyses on code-based KEMs largely focus on faults targeting the Fujisaki-Okamoto transform. This work presents new fault injection attacks against BIKE and HQC that operate beyond this commonly protected component and target less obvious instructions within the decapsulation process. The proposed attacks achieve full key recovery using only valid ciphertexts under NIST Level 1 parameters, requiring 17392 and approximately 3 million decapsulation queries for HQC and BIKE, respectively. In addition, we introduce a general approach to identify effective fault locations by analyzing decoder behavior under perturbed conditions. The attacks are experimentally validated on an STM32H7 microcontroller using laser fault injection, demonstrating high repeatability. These results reveal a broader attack surface and provide a foundation for more efficient fault attack analyses in future work.
Last updated:  2026-11-03
On the Inapplicability of Residue-Confined Error Attacks to CRT-FHE with Non-Degenerate Error Distributions
Anil Kumar Pradhan and Abhraneel Dutta
This paper responds to the cryptanalysis presented in “Key Recovery from Residue- Confined Errors in the Pradhan CRT-RLWE Construction” (Olejnik and Naskrecki, 2026), which claims key recovery and plaintext recovery against the CRT-FHE scheme introduced in “A New CRT-based Fully Homomorphic Encryption” (Pradhan et al., 2026). We demonstrate that the reported recovery attacks rely entirely on a deliberately con- structed error distribution whose support lies in the kernel of the CRT encoding function. Consequently, the effective encryption error is identically zero, reducing the attacked con- struction to a noiseless RLWE instance. The subsequent key-recovery and plaintext-recovery results therefore follow from the deliberate elimination of the encryption noise, rather than from any cryptanalytic method capable of recovering secrets from properly noise-bearing CRT-FHE ciphertexts. Crucially, the proposed attack neither removes nor estimates errors from normally generated CRT-FHE ciphertexts. Instead, it assumes an artificial error distribution specifically chosen to guarantee their annihilation during encoding. This condition does not hold for the intended centered-binomial error distribution, under which the probability that an entire error polynomial belongs to the encoder’s kernel is negligible at the reported parameters. Thus, the presented recovery procedures do not constitute attacks against the concrete CRT-FHE instantiation with its intended non-degenerate error distribution. We conclude that the reported key-recovery and plaintext-recovery results concern a deliberately degenerate, effectively zero-error instantiation and do not demonstrate a practical security compromise of CRT-FHE under its intended error sampling. We further show that the distributional mismatch identified in the claimed RLWE hardness reduction does not constitute a cryptanalytic attack. In fact, the CRT-encoded error distribution under the intended parameters admits an exact, invertible transformation to ordinary RLWE with an explicitly characterized non-degenerate ternary error law.
Last updated:  2026-11-03
Leakage-Tolerant Computation without Leakage-Free Setup
Yaohua Ma and Yifan Song
Leakage-tolerant multi-party computation (MPC) ensures that leakage from each honest party’s internal state reveals no more than the leakage from honest parties' individual inputs and outputs, beyond the standard security guarantee of MPC. Previous constructions either require a leakage-free preprocessing, or rely on indistinguishability obfuscation in the common reference string (CRS) model and only achieve semi-honest security. In the computational setting, assuming only an augmented non-committing encryption scheme, we show that every adaptively well-formed functionality admits a semi-honest leakage-tolerant MPC protocol, without any leakage-free preprocessing execution or CRS. Under the decisional Diffie–Hellman assumption, we further extend this result to malicious security in the CRS model for all deterministic functionalities. The limitation of deterministic functions is subject to an impossibility result of leakage-based coin-tossing protocols. In the information-theoretic setting, we show that secure erasure enables statistically secure leakage-tolerant MPC of arbitrary functionalities assuming strictly less than half of the participants are maliciously corrupted. We complement this construction with an impossibility result: without secure erasure, general-purpose statistically secure leakage-tolerant MPC with leakage-oblivious simulation, an important property to enable universal composition, is impossible in the plain model, even when all parties are honest. As a further application, we also obtain information-theoretic leakage-tolerant circuits against bounded communication leakage, while all prior works are restricted only to the weaker variant of leakage-resilient circuits.
Last updated:  2026-11-03
Exact SVP and CVP in Structured Lattices: Polynomial-Space Algorithms and Reductions
Jiseung Kim, Changmin Lee, and Yongha Son
Although module lattices possess richer algebraic structure than general lattices, their algorithmic benefits for exact shortest and closest vector problems (SVP and CVP) remain relatively unexplored. For general $N$-dimensional lattices, the fastest known polynomial-space algorithms take $N^{\Theta(N)}$ time, whereas known $2^{O(N)}$-time algorithms require exponential space. We investigate how the algebraic structure of modules over number fields can be exploited to obtain faster exact algorithms in polynomial space. We develop a common framework based on reduced module flags and lattice-point enumeration in Euclidean balls, with two complementary approaches. The first uses recursive subfield descent, yielding deterministic $2^{O(N)}$-time algorithms for both SVP and CVP on fixed-rank modules over totally real or CM fields with bounded root discriminant and bounded-degree subfield chains. Infinite unramified class field towers provide families of unbounded dimension satisfying these conditions. The second approach reduces lattice-point enumeration in Euclidean balls to exact SVP, without requiring a subfield chain or any bound on the root discriminant. For fixed-rank modules with root discriminant $\rho=d^{o(1)}$, where $d$ is the field degree, this reduction yields deterministic SVP and CVP algorithms in time $d^{d/(2\mathrm e)+o(d)}$. Furthermore, the second approach yields exact CVP algorithms for semistable lattices, including cyclotomic ideal lattices, without any restriction on the root discriminant. The resulting running times are $N^{N/(2\mathrm e)+o(N)}$ deterministically and $N^{N/(4\mathrm e)+o(N)}$ with randomization. While the two approaches above initially focus on fixed-rank modules, we further extend both to modules of growing rank. In particular, for modules of rank $\Theta(\log N)$ over fields with bounded root discriminant, we obtain deterministic SVP and CVP algorithms in times $(\log N)^{N/(2\mathrm e)+o(N)}$ and $(\log N)^{N/2+o(N)}$, respectively.
Last updated:  2026-11-03
The Fairest of Them All: Best-of-Both-Worlds Fair Leader Election
Chen-Da Liu-Zhang, Elisaweta Masserova, Kelsey Melissaris, Lawrence Roy, and Sophia Yakoubov
Fair leader election is the problem of sampling an unbiased random party out of a set of $n$ parties. The seminal impossibility result of Cleve (STOC 1986) applies to this setting, and shows that the result of the election cannot be unbiased against a dishonest majority. Recent work has achieved the weaker property of game-theoretic fairness, where behaving dishonestly cannot improve one’s chances of being elected. However, such protocols allow even a single corrupt party to bias the outcome. In this work, we introduce best-of-both-worlds (BoBW) fairness, where a small number $t_S$ of corrupt parties cannot bias the result, and even a larger number $t_{GT}$ of corrupt parties still cannot improve their collective election chances (CSP-fairness) nor hurt the election chances of any given honest party (MM-fairness). We present a protocol for BoBW fair leader election for $t_S + t_{GT} < n$. We then prove a generalization of Cleve’s impossibility, and show that this protocol is optimal. Next, in the setting of statistical security we find that BoBW fairness is uninteresting, as it is only possible for an honest majority, where we can get also unbiased leader election. Finally, in the setting of perfect security, we present a BoBW protocol achieving CSP-fairness and strong fairness for $t_S + 1 = t_{CSP} = \frac{n}{3}$, and prove that this is also optimal.
Last updated:  2026-11-03
BBB Secure Large-Tweak TBC from Ideal Block Ciphers
Arghya Bhattacharjee, Ritam Bhaumik, Nilanjan Datta, Avijit Dutta, Shibam Ghosh, and Sougata Mandal
At FSE'15, Mennink introduced the concept of designing beyond-birthday bound secure tweakable block cipher from an ideal block cipher. They proposed two tweakable block ciphers $\widetilde{F}[1]$ and $\widetilde{F}[2]$ that accept $n$-bit tweaks using a block cipher with an $n$-bit key and $n$-bit data. Mennink proved that the constructions achieve security up to $2^{2n/3}$ and $2^n$ queries, respectively, assuming the underlying block cipher is ideal. Later, at ASIACRYPT'16, Wang et al. proposed a class of $32$ new tweakable block ciphers derived from $n$-bit ideal block ciphers that achieve optimal security, i.e., security up to $2^n$ queries. The proposed designs by both Mennink and Wang et al. admit only $n$-bit tweaks. In FSE'23, Shen and Standaert proposed a tweakable block cipher $\widetilde{G}2$ that accepts $2n$-bit tweaks and achieves security up to $2^n$ queries. Their construction uses three block cipher calls, which was shown to be optimal for beyond-birthday-bound secure tweakable block ciphers accepting $2n$-bit tweaks. In this paper, we extend this line of research by considering the design of tweakable block ciphers that support $3n$-bit tweaks from an ideal block cipher with affine mixing. First, we show that there is a generic birthday-bound distinguishing attack on any such design with three block cipher calls if any of the block cipher keys are tweak-independent. We then propose a tweakable block cipher $\widetilde{\textsf{G}}3^*$, which leverages three block cipher calls with each key being dependent on the tweak. We demonstrate that $\widetilde{\textsf{G}}3^*$ achieve security up to $2^{2n/3}$ queries. Although primarily of theoretical interest, $\widetilde{\textsf{G}}3^*$ demonstrates that beyond-birthday-bound security for a $3n$-bit tweak can be achieved with only three block-cipher calls, thereby extending the known feasibility frontier for TBC design.Furthermore, we extend this result and propose an optimally secure construction, dubbed $\widetilde{\textsf{G}}3$, that uses four ideal block cipher calls with only one tweak-dependent key. Finally, we generalize this and propose an optimally secure tweakable block cipher $\widetilde{\textsf{G}}r$ that processes $rn$-bit tweaks using $(r+1)$ block cipher invocations with only one tweak-dependent block cipher key. Our experimental evaluation demonstrates that on platforms featuring AES-NI hardware acceleration, \tx{ZMAC} instantiated with $\widetilde{\textsf{G}}_3$ and $\widetilde{\textsf{G}}_4$ (i.e., $\widetilde{\textsf{G}}_r$ with $r=4$) outperforms all existing ideal-cipher-based TBC candidates.
Last updated:  2026-11-03
PS-BKZ: Decoupling Outer Propagation and Local Processing in BKZ by Parameter Separation
Hutao Song, Hua Guo, Yang Sun, Fengju Gao, Zongyang Zhang, and Qianhong Wu
This work provides a systematic study of parameter separation in Block Korkine–Zolotarev (BKZ) reduction. We propose a general framework with separate parameters for outer propagation and the dominant local computation. The framework covers the local parameter settings of standard BKZ and variants using extended preprocessing, dimensions for free, or progressive sieving, with corresponding adaptations to the outer operations. This allows less expensive local processing without narrowing the outer propagation range. Within this framework, we give idealized and executable constructions that use inner BKZ with a smaller blocksize to supply local vectors for larger outer blocks. We derive a worst-case quality bound for the idealized construction and analyze its quality–cost behavior using a practical fixed-point model. Experiments on the executable construction cover random q-ary bases up to dimension 300 and SVP Challenge bases up to dimension 240. The detailed comparisons at n ≥ 200 show lower mean root-Hermite factors (RHFs) and 14.1%–59.3% shorter mean running times than BKZ 2.0. Joint improvements generally become more frequent with dimension. On q-ary inputs against BKZ 2.0 with blocksize 50, their frequency increases from 15.56% at n = 150 to 73.33% at n = 300.
Last updated:  2026-11-03
Perseus: A Full-Stack System for Homomorphic Model Inference
Alessandro Zirilli, Davide Marincione, Evgenios M. Kornaropoulos, Giuseppe Ateniese, and Emanuele Rodolà
Large Language Models (LLMs) have made it exceptionally convenient for users to send their private data to model providers, which process them in plaintext. Fully Homomorphic Encryption (FHE) promises to secure remote inference by computing directly on encrypted data, yet it has remained prohibitively slow. The effort to make it practical remains fragmented, with most existing frameworks being closed-source, which keeps progress from compounding. We present Perseus, a free and open Python software library that supports the full stack of encrypted model inference, from the cryptographic backend and data packing, to encrypted nonlinearities and end-to-end model execution. Perseus ships with built-in novel optimizations, one at each level of the stack: in-kernel regeneration of key-switching keys at the (i) backend level, a complex variant of Cachemir packing at the (ii) data level, and a state-of-the-art bootstrap placer that is both packing- and magnitude-aware at the (iii) model level. Perseus achieves state-of-the-art latency across multiple models and modalities, within $3\%$ of the plaintext models' accuracy and perplexity. Remarkably, it is $3.96\times$ faster at single-token decoding than any other implementation on Llama-3-8B. We initiate, for the first time, a public speedrun on encrypted GPT-2, so that progress can compound.
Last updated:  2026-11-03
Finite-Batch q-ary OT Extension for High-Arity Private Lookup: Certified Radix--Code Co-Design
Zhuoran Zhang
High-arity oblivious transfer is a natural abstraction for private lookup: a $\delta$-bit table address selects one entry out of $2^\delta$ candidates. This paper characterizes the finite-batch design space of the CCG q-ary OT-extension family and derives certified radix-selection rules. For $q=2^r$, we formulate radix-code selection as a security-constrained discrete optimization problem that accounts for subfield-check padding, code dimension, required distance, base-OT count, and q-ary symbol width. We derive exact communication thresholds showing when reduced base OTs can compensate for larger q-ary encoding cost. Then we convert the Griesmer bound into communication lower bounds, yielding certificates for regions where non-binary radices cannot improve communication, are provably beneficial, or remain dependent on better code constructions. Finally, we instantiate the framework with simplex and BCH constructions and CodeTables entries, and verify the selected $\delta=12$ codes with Magma.
Last updated:  2026-11-03
Cryptanalysis of MinRank 2.0
Nicolas Aragon, Maxime Bros, Ray Perlner, Daniel Smith-Tone, and Javier Verbel
MinRank is an NP-complete problem underlying the security of several post-quantum schemes. It is the hardness assumption of the NIST second-round signature candidate Mirath and of the encryption schemes of Chatterjee et al.\ and Debris-Alazard et al.\ at Eurocrypt 2026. Moreover, it is ubiquitous in the cryptanalysis of multivariate schemes, among them the third-round candidates UOV, MAYO, QR-UOV, and SNOVA. In this work, we revisit the attacks on MinRank. On the combinatorial side, we improve the polynomial part of the kernel-search attack by sharing its linear algebra across guesses, which lowers its cost by 3 to 6 bits on the Mirath parameters and the Courtois challenges, and by up to 3 bits in combination with the hybrid approach. With the improved attack, we solved Courtois challenge~D, open since 2001: an instance over $\mathbb{F}_2$ with $19 \times 19$ matrices, $81$ unknowns, and target rank $10$, solved in 11434 CPU days, an estimated $2^{61}$ bit opetations. Our multi-threaded C++ code is publicly available. On the algebraic side, we show that the complexity of the Kipnis--Shamir (KS) attack is less understood than the literature suggests: the existing estimates rely on a generic Hilbert series that does not predict the rank of the Macaulay matrices of the KS equations. We prove a lower bound on the corank that explains the discrepancy, show that the attack requires a reduced instance with $k \leq m - r$, and derive corrected complexity estimates, which are $1$ to $24$ bits above the best other attack on every Mirath parameter set. We also extend the Support-Minors and Minors modelings with the field equations, which lowers their estimates over small fields: for $q = 2$ and $m = n = 22$, by 9 to 205 bits for Support-Minors and by 17 to 278 bits for Minors. The rank predictions behind the algebraic estimates are stated as assumptions and verified experimentally.
Last updated:  2026-11-03
Optimal Load-Balanced Scalable Distributed Agreement
Yuval Gelles and Ilan Komargodski
We consider the fundamental problem of designing classical consensus-related distributed abstractions for large-scale networks, where the number of parties can be huge. Specifically, we consider tasks such as Byzantine Agreement, Broadcast, and Committee Election, and our goal is to design scalable protocols in the sense that each honest party processes and sends a number of bits which is sub-linear in $n$, the total number of parties. In this work, we construct the first such scalable protocols for all of the above tasks. In our protocols, each party processes and sends $\tilde O (\sqrt n)$ bits throughout $\tilde O (1)$ rounds of communication, and correctness is guaranteed for at most $1/3-\epsilon$ fraction of static byzantine corruptions for every constant $\epsilon>0$ (in the full information model). All previous protocols for the considered agreement tasks were non-scalable, either because the communication complexity was linear or because the computational complexity was super polynomial. We complement our result with a matching lower bound showing that any Byzantine Agreement protocol must have $\Omega(\sqrt n)$ complexity in our model. Previously, the state of the art was the well-known $\tilde\Omega(\sqrt[3]{n})$ lower bound of Holtby, Kapron, and King (Distributed Computing, 2008).
Last updated:  2026-11-03
FixSampZ: A Fixed-Point Hardware-Efficient Discrete Gaussian Sampler for Falcon Signatures
Pushpendra Singh, Akshara K B, Utsav Banerjee, and Navin Kashyap
Falcon, a NIST-standardized post-quantum signature algorithm, offers compact signatures but relies on hardware-intensive floating-point arithmetic. Building on recent theoretical fixed-point formulations, we present a completely floating-point-free hardware architecture for SamplerZ, Falcon’s primary signing bottleneck. By utilizing zero-cost hardware bit-sliced retagging of fixed-point data, which software avoids due to instruction overheads, we enforce tighter data formats at every stage boundary without area or latency penalties. Furthermore, executing floor functions as trivial two's-complement arithmetic right shifts eliminates the complex floor-prediction and redundant data-paths required by floating-point designs. Implemented on UltraScale+ FPGA, our fixed-point sampler exactly matches all 1,024 official test vectors and requires 38% fewer LUTs, 21% less FFs and 36% less DSPs compared to the floating-point baseline, with 21% fewer cycles at a higher clock frequency. We also demonstrate that substituting the baseline ChaCha20 PRNG with lightweight NIST-standardized Ascon-XOF128 achieves further 2-3 × hardware resource savings with zero sampling latency overhead.
Last updated:  2026-11-03
Kaiburr: ML-KEM at (much) higher security
Swechchha Adhikari, Vadim Lyubashevsky, and Peter Schwabe
With deployment of standardized post-quantum cryptography well on the way, discussions continue about concrete choices of schemes and parameter sets. For example, while NIST standardized structured-lattice-based ML-KEM, European agencies like BSI and ANSSI favor unstructured-lattice-based FrodoKEM. Another discussion revolves around different approaches to hybrid deployments – either combining post-quantum schemes with "traditional" elliptic-curve cryptography (or RSA) or combining multiple different post-quantum schemes. The typical question for systems engineers to ask is what the "best" or "most conservative" approach is within a certain performance budget. In this paper we add a data point to this discussion by investigating how to scale ML-KEM to (much) higher security levels of the underlying MLWE problem. We first observe that increasing security simply by increasing the module rank $k$ quickly reaches a limit imposed by decryption failure probability. We then propose a generalization of the noise distribution, which enables scaling to much larger module rank and MLWE hardness, while preserving the essence of ML-KEM, most notably arithmetic in the ring $\mathbb{Z}_{3329}[X]/(X^{256}+1)$ and a simple and constant-time secret / noise generation. We select three concrete parameter sets of this high-security variant of ML-KEM, which we call Kaiburr. We present benchmarking results for optimized implementations of Kaiburr on 64-bit Intel CPUs and on the Asymmetric Cryptography Coprocessor (ACC) of the Pavona open-source silicon framework. Based on these benchmarks, we argue that, for example, a hybrid of FrodoKEM-976 and Kaiburr-1792 not only offers better performance than FrodoKEM-1344, it also offers protection against a broader range of hypothetical future attacks against (M)LWE.
Last updated:  2026-11-03
Improved Cryptanalysis of Local PRGs
Shihan Lyu, Mo LI, Chuhan Ma, and Ximing Fu
We present two seed-recovery attacks on a family of local PRGs, which map an $n$-bit random seed to an $m$-bit pseudorandom string by applying $\XorMaj$ predicates. For PRGs with large locality, we extend the Group-and-Solve (GAS, Eurocrypt 26) framework to Guess-Filter-Solve (GFS). GFS first guesses that a set of seed bits are all $1$s and then filters for outputs whose inputs to $\Maj$ contain a sufficiently large subset of the guessed bits. Then high-bias noisy equations can be collected for the correct guess and solved by specific solvers. Compared with GAS, GFS collects substantially more noisy equations with high bias and hence outperforms GAS significantly, especially when the output is short. For example, when the proposed asymptotic XOR-MAJ family (STOC 16) is instantiated with $n=256$ and $m=2^{16}$, the complexity for GFS is $2^{68.78}$ while it is $2^{157.91}$ for GAS. In addition, the asymptotic complexity of GFS is $2^{0.15n+o(n)}$. Independently, inspired by the Guess-and-Decode (GADec, TIT 22), we propose the Filter-Guess-Propagate (FGP) attack. Compared with GADec, FGP introduces two speed-up techniques at each iteration of Belief Propagation (BP): a filter scheme to reduce the number of equations and a dynamic-programming technique to update the log-likelihood ratios of variables efficiently. Together, these improvements enable FGP to perform fast BP and outperform GADec significantly. For $\XorMaj_{10,64}$ with $n=256$ and $m=2^{40}$ (Eurocrypt 24), the total complexity of FGP is $2^{52.66}$, whereas even a single BP iteration of GADec costs $2^{106.42}$. We further extend FGP to $\XorMod$ predicates and experimentally evaluate the resulting attack complexity. We also apply FGP to a ZKP protocol from Eurocrypt 25 and QuietOT from Asiacrypt 24, with only a small computational overhead. For the ZKP protocol, FGP leads to an attack on witness indistinguishability, while for QuietOT, it similarly yields an attack on OT receiver privacy.
Last updated:  2026-11-03
Quotienting Redundant Tables: Practical Master-Key Recovery from WBSLT White-Box AES
Jiseok Bang and Seungkwang Lee
Enlarging lookup-table addresses does not hide smaller selectors when the complete public table factors through a core with distinct rows and distinct columns. We demonstrate this condition in WBSLT, a white-box AES design presented at NDSS 2026 that reports resistance to several structural attacks. In the released general generator, the joint output of each group of four first-round TypeII tables has an exact 16 × 16 quotient of its 64 × 64 address space. Mapping its row and column classes to observed addresses recovers the original nibble partition of each AES input byte. Public tables implementing encoded XOR supply compatible output coordinates. Under the generator’s strictly linear input decoder, two 16-point restrictions of each keyed AES S-box then identify its embedded key byte; independent exhaustive checks confirm this property for all 256 byte keys. Using public tables and traces of chosen encoded inputs, we recover every key in 200 general instances that passed 200,000 reference AES block tests, after a median of 146 and at most 221 inputs. Separate 200-instance cohorts of the released optimized C source and its one-line functional repair also yield every key; only the repair passes the AES tests. An adjacent-round adaptation recovers 20/20 exact keys on a paired cohort without reconstructing the nibble partition. On those instances, our first-round route uses fewer live trace queries and less public table data. The exact quotient provides a concrete test for selector partitions that survive address enlargement.
Last updated:  2026-11-03
Secret Sharing Despite Non-Extractable Randomness
Divesh Aggarwal
Bosley and Dodis (TCC 2007) proved that a class of imperfect randomness sources that suffices for information-theoretic encryption of messages longer than the logarithm of the key length must admit deterministic extraction of nearly uniform bits, and asked whether the same is true of two-out-of-two secret sharing. Aggarwal, Chung, Obremski, and Ribeiro (TCC 2022) gave a positive answer for schemes that are in addition leakage-resilient or non-malleable; the original question remained open. We answer it in the negative. For every $b\ge2$ we construct a class of flat sources on $\{0,1\}^{b+2}$, each of min-entropy at least $b$, together with a perfectly correct and perfectly private two-out-of-two scheme that shares a $b$-bit secret into two $(b+1)$-bit shares using any source in the class, and we show that every deterministic map from $\{0,1\}^{b+2}$ to $\{0,1\}$ is at statistical distance at least $1/6$ from uniform on some source in the class. This implies that sharing a long enough secret does not require extractable randomness. The proof is a short parity argument. The idea of the construction extends to other thresholds: for two-out-of-$n$ and $r$-out-of-$r$ sharing we give perfect schemes with $(b+1)$-bit shares, private for classes of flat sources from which no single bit can be extracted with error below $1/(4n-2)$ and $1/(2(2^r-1))$, respectively.
Last updated:  2026-11-03
Tight Depth Lower Bounds for Stretch Amplification
Oliver Korten
We investigate the depth overhead of stretch-amplification for pseudorandom generators in the black-box model. We show that any black box construction of a PRG $H: \{0,1\}^m \to \{0,1\}^M$ which makes $\mathrm{poly}(n)$ queries to a PRG $G: \{0,1\}^n \to \{0,1\}^N$ in $d$ adaptive phases during each evaluation (and with a black-box reduction to the security of $G$) must satisfy: $M \leq (m + O(\log n)) \Bigl( \frac{N}{n - O(\log n)} \Bigr)^d$. This implies that the standard amplification procedure [GM'84, GGM'86] based on repeated composition of $G$ is essentially optimal. In particular, amplifying $n \mapsto n+1$ to $m \mapsto 2m$ requires depth overhead $d = \Omega(\frac{n}{\log n})$, and amplifying $n \mapsto 2n$ to $m \mapsto m^2$ requires depth overhead $d = \Omega(\log n)$; each of these bounds is tight up to a constant factor. As an immediate corollary we obtain tight lower bounds on the depth complexity of black-box constructions of PRFs from PRGs. Both of these problems (pertaining to amplification and PRF construction) have been studied in various prior works [V'05, MV'11, BJP'11, MV'15, BMM'24, ADV'26]. Despite progress on special cases in which the structure of the reductions is constrained, it was previously unknown whether completely parallel constructions ($d=1$) existed in every stretch regime. The kinds of amplification procedures we investigate have more recently found use outside of cryptography in the study of range avoidance ("Avoid") [K'21]. We show an analogous result in this setting: any black-box $\mathrm{FP^{NP}}$ reduction from an Avoid instance $G: \{0,1\}^n \to \{0,1\}^N$ to a second Avoid instance $H: \{0,1\}^m \to \{0,1\}^M$ which has "depth $d$" in the above sense must satisfy the same bound relating $n,N,m,M,d$. Using this impossibility result for Avoid, we construct an oracle relative to which $\mathrm{E} \not\subseteq \mathrm{NC}/\mathrm{poly}$ but $\mathrm{E^{NP}} \subseteq \mathrm{P}/\mathrm{poly}$. Our oracle separation implies that in the relativized setting, the bounded arithmetic theory $S^1_2$ cannot prove the existence of functions outside $\mathrm{P}/\mathrm{poly}$, even given as an axiom the existence of functions outside $\mathrm{NC}/\mathrm{poly}$.
Last updated:  2026-11-03
Reed-Solomon Codes Beyond Johnson: Efficient Decoding and Smaller Cryptographic Proofs
Quang Dao, Scott Duke Kominers, and Justin Thaler
List decoding Reed–Solomon codes is a central problem in coding theory and, together with mutual correlated agreement (MCA), underpins the soundness of many succinct cryptographic proofs. In this work, we give precise quantitative bounds on Reed–Solomon list decoding and MCA up to capacity, provide deterministic decoding algorithms that remain efficient over cryptographically large fields, and specialize our bounds to reduce proof sizes in implemented proof systems. Our bounds apply to arbitrary prescribed evaluation domains; beyond Johnson, they require sufficiently large field characteristic. Refining the hidden-derivative method of Brakensiek, Chen, Putterman, Zhang, and Zheng, we obtain an explicit agreement threshold $a_1(\rho)$ strictly below the Johnson bound $\sqrt{\rho}$, using only the first derivative, without requiring its evaluations in the received word. At agreement $a_1(\rho)+\eta_1$, where $\eta_1>0$, our sharper interpolation and candidate counts give list size $O_\rho(n/\eta_1^2)$ and MCA error $O_\rho(n^2/(q\eta_1^4))$ for codes of length $n$ over $\mathbb{F}_q$. Higher derivatives give explicit quantitative bounds up to capacity, uniformly over all rates, sharpening prior MCA results in Zheng's unpublished manuscript and Jeronimo's work, concurrent with ours. At fixed rate, for agreement gap $\eta_0>0$ above Johnson, we improve the MCA error bound of Ben-Sasson et al. (BCHKS) from $O_\rho(n/(q\eta_0^5))$ to $O_\rho(n/(q\eta_0^3))$, in every characteristic. Our decoders determine the values of the message and its derivatives at a point from the agreements with the received word, rather than enumerating them over the field as earlier hidden-derivative decoders do. With fast explicit field arithmetic, at fixed rate and a fixed positive gap above the respective threshold, deterministic decoding takes $\widetilde{O}(n\log q)$ bit operations above Johnson in every characteristic and $\widetilde{O}(n^3\log q)$ above our first-order curve in sufficiently large characteristic. Decoding remains polynomial in $n$ and $\log q$ at every fixed positive gap from capacity, under the same requirement of sufficiently large characteristic. Our first-derivative bounds give the first proof-size reductions in existing proof-system implementations from provable Reed–Solomon proximity-gap bounds beyond the Johnson radius. Relative to the deployed parameters and at unchanged security targets, we save 79.4 KB (11.1%) for ProveKit passport proofs, 13.2 KB (4.63%) for ZisK compressed final proofs, and 59.8 KB (4.85%) for LambdaVM CPU subproofs. We have formally verified the list-decoding and MCA bounds and concrete parameters in ArkLib, a Lean library for verified cryptographic proofs.
Last updated:  2026-11-03
Counterexamples to Beyond-Johnson Proximity Gaps over Binary Fields
Quang Dao, Scott Duke Kominers, Justin Thaler, and Kai Zhe Zheng
Many hash-based proof systems check that committed words are close to Reed–Solomon codewords by testing one random combination of them. Their soundness analysis uses a *proximity gap*: if the combination agrees with a codeword on many positions, so do the original words, on the same positions, except for a few *exceptional* challenges. Such gaps are known above the Johnson threshold, about $\sqrt\rho$ for rate $\rho$, and extending them below it would shrink proofs. Recent work does so in large characteristic, but not for the additive domains used over binary fields, where some of the fastest proof systems run. We show that on these domains, beyond-Johnson proximity gaps fail. Our first construction applies to any additive domain (a linear subspace) filling a constant fraction of a containing binary field, such as the length-$2^{27}$ domain of Binius64. Over a suitable extension challenge field and at rate $1/4$, it gives two words that can simultaneously match codewords on at most $25\%$ of the positions, while their combinations approach the $50\%$ Johnson threshold for superpolynomially many challenges. This rules out any $\mathrm{poly}(N)/|\mathbb F|$ bound on the exceptional probability below Johnson. The construction also rules out polynomial-size decoding lists below Johnson: one word agrees with superpolynomially many codewords at agreement approaching $50\%$. Earlier superpolynomial lists needed the rate, or the agreement–rate gap, to vanish. Our second and third constructions cover every additive domain, including the sparse domains used by LeanVM and Flock. At rate $1/16$, the second gives $(N-1)(N-2)/6$ exceptional challenges at the Johnson threshold itself, when the domain lies in a proper subfield of the challenge field. The third construction trades agreement for larger exception counts: at rate $1/2$ and length $2^{22}$, its combinations reach $53.125\%$ agreement from common agreement $50\%$, with probability at least $2^{-20}$ over a $192$-bit challenge field. Finally, at every fixed rate, some constant agreement above the rate makes every challenge exceptional, over $\mathrm{poly}(N)$-size challenge fields. All of our results are formally verified in Lean.
Last updated:  2026-11-02
Witness-Succinct Universally-Composable SNARKs
Chaya Ganesh, Yashvanth Kondi, Claudio Orlandi, Mahak Pancholi, Akira Takahashi, and Daniel Tschudi
Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) are becoming an increasingly fundamental tool in many real-world applications where the proof compactness is of the utmost importance, including blockchains. A proof of security for SNARKs in the Universal Composability (UC) framework (Canetti, FOCS'01) would rule out devastating malleability attacks. To retain security of SNARKs in the UC model, one must show their simulation-extractability such that the knowledge extractor is both black-box and straight-line, which would imply that proofs generated by honest provers are non-malleable. However, existing simulation-extractability results on SNARKs either lack some of these properties, or alternatively have to sacrifice witness succinctness to prove UC security. In this paper, we provide a compiler lifting any simulation-extractable NIZKAoK into a UC-secure one in the global random oracle model, importantly, while preserving the same level of witness succinctness. Combining this with existing zkSNARKs, we achieve, to the best of our knowledge, the first zkSNARKs simultaneously achieving UC-security and constant sized proofs.
Last updated:  2026-11-02
On the (Quantum) Communication Complexity of Secure MPC from a Random Oracle
Alexander Hoover, Giuseppe Persiano, and Kevin Yeo
Information-theoretic MPC among $n$ parties with $t$ corruptions can securely evaluate a circuit $C$ with $O(|C| \cdot t/(n-t))$ online communication in the preprocessing model and $O(|C| \cdot t/(n-2t))$ communication in the honest majority setting. Damg{\aa}rd, Larsen and Nielsen (CRYPTO 2019) showed that both communication bounds are tight for inner products. Fully homomorphic encryption and other assumptions known to imply public-key cryptography beat both communication bounds, but the communication complexity with symmetric-key cryptography alone is less understood. For MPC with preprocessing, we prove that the same $\Omega(|C| \cdot t/(n-t))$ lower bound holds in the random oracle model, so a random oracle cannot reduce the online communication. For honest majority MPC relative to a random oracle, we present an $\Omega(|C|)$ communication lower bound that is matched by a new construction for degree-2 polynomials (including inner products) when $n = O(\log \lambda)$, beating the information-theoretic bound. We also study quantum MPC. First, we prove that information-theoretic protocols with quantum communication (and preprocessing) cannot reduce communication compared to their classical counterparts. Furthermore, we extend our lower bound for MPC with preprocessing to protocols with a quantum-accessible random oracle, but use only classical communication. In contrast, with both quantum communication and a post-quantum one-way function, we present a simple two-party protocol that evaluates the two-party instance of these circuits with $\mathsf{poly}(\lambda, \log |C|)$ communication, beating these lower bounds. Finally, such communication savings do not come for free. We prove that there exist circuits $C$ such that every blackbox protocol with $o(|C|)$ quantum communication must perform $\Omega(|C|)$ cryptographic operations.
Last updated:  2026-11-02
Can FrodoKEM Run in a Millisecond? FPGA Says Yes!
Gökçe Düzyol, Muhammed Said Gündoğan, and Atakan Arslan
FrodoKEM is a post-quantum key encapsulation mechanism based on plain Learning With Errors (LWE). In contrast to module-lattice-based schemes, it relies on an unstructured variant of the LWE problem, providing more conservative and better-understood security guarantees. In this paper, we explore hardware-level parallelization of FrodoKEM's matrix multiplication, which dominates its execution time. Earlier high-throughput work by Howe et al. identified SHAKE as a performance bottleneck and replaced it with the Trivium stream cipher, which renders the implementation incompatible with the FrodoKEM specification. In contrast, our work adheres strictly to the specification, including its use of SHAKE as the PRNG, and introduces a parameterized architecture whose degree of parallelism is set by design-time parameters. We present operation-specific datapaths for FrodoKEM-640 on Artix-7 with 24 parallel multipliers for key generation and 32 for encapsulation and decapsulation, achieving 976-1077 operations per second, i.e., latencies of 0.93-1.02 ms. Among the earlier specification-compliant designs, this is the lowest latency and the lowest area-time product. The design shows that SHAKE is not a barrier to parallel matrix multiplication and that efficient, standard-compliant FrodoKEM implementations are practical for high-speed cryptographic applications.
Last updated:  2026-11-02
Improving Code Rate and Query Complexity for the Ligero-IOP System
Ignacio Cascudo, Carmit Hazay, and Muthu Venkitasubramaniam
This work presents two main contributions to the analysis and design of Ligero-style zero-knowledge proof systems. First, we analyze the original Ligero IOP in the list-decoding regime and show that mutual correlated agreement suffices to obtain improved soundness guarantees and lower query complexity, without modifying the protocol. Second, we propose a new variant of Ligero that incorporates out-of-domain sampling, leading to further soundness improvements and enabling Reed--Solomon code rates above $1/2$. The new protocol preserves the constant-round structure of the Ligero IOP and its compatibility with memory-efficient proving, while achieving perfect honest-verifier zero knowledge.
Last updated:  2026-11-02
Efficient Polynomial Multiplier Architectures for ML-KEM on Resource-Constrained FPGAs
Hossein Naderi Varandi and Raziye Salarifard
The Number Theoretic Transform (NTT) is a key component of polynomial multiplication in Kyber, making its efficient hardware implementation essential for post-quantum cryptographic applications. This paper presents two hardware architectures for Kyber polynomial arithmetic, supporting the NTT, inverse NTT (INTT) and point-wise multiplication (PWM) operations. The first architecture employs a single processing element (PE) to reduce hardware area, while the second uses two PEs to achieve higher throughput and efficiency. Both architectures incorporate a low-complexity modular multiplication and reduction method tailored to the Kyber modulus q = 3329, a unified butterfly unit supporting NTT, INTT, and PWM, and constant-geometry data access with dedicated address-generation algorithms. The dual-PE architecture is implemented without dedicated DSP blocks or BRAMs. FPGA implementation results demonstrate that the dual-PE architecture achieves the lowest area-time product and highest frequency among the evaluated state-of-the-art designs, while providing an effective trade-off between hardware area and execution time.
Last updated:  2026-11-02
The Cost of Rewinding for Succinct Arguments: Strict-Time Barriers and Expected-Time Security
Alessandro Chiesa, Ziyi Guan, William Wang, and Yuetian Wu
Succinct arguments are central cryptographic objects, underlying various applications such as blockchains and image authentication. Almost all succinct arguments used in practice follow the commit-and-open paradigm introduced by Kilian (STOC 1992): commit to a probabilistic proof, then open the few locations the verifier queries. Decades of work have generalized and optimized this paradigm, yet its exact provable security in the standard model remains unclear. Existing analyses proceed by rewinding, and they leave gaps: strict-time analyses lose an inverse-polynomial factor, while expected-time analyses are sharper but apply only to special cases of this paradigm. We resolve both gaps. On the negative side, we show that the strict-time loss is inherent: no strict polynomial-time reduction relying on a black-box extractor can achieve negligible knowledge error (unless the underlying language is easy). On the positive side, we give a new expected-time analysis, achieving negligible soundness and knowledge errors via an expected polynomial-time reduction against expected polynomial-time adversaries, at the full generality of the paradigm, capturing multi-round and functional variants such as polynomial and linear IOPs compiled with the corresponding commitments. This is the first standard-model analysis to reach this regime for succinct arguments deployed in practice.
Last updated:  2026-11-02
Complete Addition Law for Twisted Edwards Curves
Reza Rezaeian Farashahi, Ruhallah Mirzaei Aliarabi, and Peyman Shahbazi Dastjerdi
We construct complete addition laws in extended coordinates for twisted Edwards curves \(E_{a,d}:ax^2+y^2=1+dx^2y^2\), where \(a,d\in K^\times\), \(a\ne d\), and \(\operatorname{char}K\ne2\). If \(t\in K\) makes \((t^2-a)(t^2-d)\) a nonzero nonsquare, the construction yields a \(K\)-complete formula valid for every pair of \(K\)-rational points. The proof describes the exceptional fibres through the difference morphism. Over finite fields of odd cardinality \(q>16\), such a coefficient exists for every nonsingular parameter pair, including the same-square-class cases with full rational two-torsion. We give full and mixed evaluation schedules. Full addition costs \(8M+D_c\) in split elementary models and \(10M\) or \(12M\), plus fixed-constant costs, in the same-square-class cases. Doubling costs \(4M+4S+\min(D_a,D_d)\), independently of coefficient selection. Here \(M\) denotes a general field multiplication, \(S\) a squaring, and \(D_c\) multiplication by a fixed \(c\in K\).
Last updated:  2026-11-02
Complete Addition on Short Weierstrass Curves with Point-Free Lines
Ruhallah Mirzaei Aliarabi and Reza Rezaeian Farashahi
Let $E_{a,b}:Y^2Z=X^3+aXZ^2+bZ^3$ be a nonsingular short-Weierstrass curve over a field $K$ of characteristic different from $2$ and $3$. A nonvertical line $Y=mX+nZ$ has no $K$-rational point on the curve if and only if $x^3-m^2x^2+(a-2mn)x+b-n^2$ is rootless in $K$. We give coordinate changes and formulas for the corresponding $K$-complete Bosma--Lenstra addition law. An incidence count proves that such a line exists over every finite field in the stated characteristic. The classical five-multiplication cross-product identity reduces the output computation by one multiplication. For normalized horizontal, sloped, and depressed families, the full/full costs are $13M+5D+30A$, $13M+5D+33A$, and $13M+(2\text{ to }5)D+60A$, respectively. Horizontal normalization requires a nonzero cube parameter; the depressed family always contains a point-free line over $\mathbb{F}_p$ for $p\ge47$. The zero-line formula costs $11M+3D_a+2D_{3b}+28A$ and is complete over finite $K$ exactly when $\#E(K)$ is odd. We also give complete doubling formulas, account for changes of coordinates, and apply the five-product identity to published Hessian addition formulas.
Last updated:  2026-11-02
Distill and Conquer: Cryptanalytic Extraction of Local Rules in the Hard-Label Setting
Chun Li, Di Li, Liping Zhuang, Siqi Zhu, Yufeng Tang, Xingfu Yan, and Zheng Gong
Cryptanalytic extraction can expose proprietary neural network parameters, but unknown architectures and large parameter counts complicate recovery under hard-label access. Local class-pair rules offer a narrower target by making class-switching conditions explicit and predicting nearby labels under a specified sampling law. Distillation methods mainly return substitute models rather than explicit rules whose local agreement has been tested against the victim. We propose Distill–Probe–Extract to produce such rules without first identifying the victim architecture. Verified boundary events guide student training, and student gradients propose directions at boundary anchors refined through victim queries. Fresh hard-label queries then test the proposed rules, retaining validation inputs and victim labels for each accepted rule. On a digits multilayer perceptron and pooling convolutional networks, fixed-candidate comparisons isolate the savings from replacing victim-normal estimation with student gradients. For the multilayer perceptron, median recorded online cost decreases from 246 to 118 queries per attempt after student preparation. With preparation and failures counted, full Fashion-MNIST sessions produce 2.03–2.23 times Direct's accepted-rule count under the original validation gate at 320,000-call caps. At 320,000 calls, a separate student-level test on trained Blended watermarks yields 99.99% trigger agreement and 91.79% clean agreement, with all three seeds passing joint verification.
Last updated:  2026-11-02
Normal-Jet Masking: A Retraining-Free Defense Against Cryptanalytic Extraction of Neural Networks
Chun Li, Liping Zhuang, Di Li, Yufeng Tang, Ming Duan, and Zheng Gong
Cryptanalytic extraction (CEA) of piecewise-linear neural networks recovers hidden signatures and parameters by locating critical points or hard-label dual points that expose off-manifold geometry. Proposed mitigation methods include query monitoring, output perturbation, ownership verification, and extraction-aware training. Train to Defend (TTD) directly addresses CEA through extraction-aware training, but cannot protect an already-trained checkpoint without retraining. We propose Normal-Jet Masking (NJM), a post-training wrapper that leaves the source model unchanged. NJM calibrates a tangent–normal tube around protected data, keeps private normal-direction mask channels inactive inside the tube, and mixes their piecewise-linear activations into served outputs outside it. NJM targets the shared evidence-acquisition stage rather than one attack implementation: mask events enter both raw-logit (soft-label) critical finding and hard-label dual finding before downstream signature and parameter recovery. Across seven MLPs, NJM reduces raw-logit evidence F1 by 53.8–93.1%, raises query cost by 1.4–9.3×, and eliminates pure hard-label duals. On CNNs, it preserves at least 0.9993 agreement while lowering source precision. These results show that post-training geometric masking complements training-time hardening across soft- and hard-label CEA.
Last updated:  2026-11-02
Unique Signature Schemes with Tight Security in the Random Oracle Model via Hash-and-Subset-Sign
Thomas Attema, Lisa Kohl, and Joost van der Laan
Unique signatures are digital signature schemes, where each message has exactly one valid signature. The uniqueness property typically comes at a price: Most unique signature schemes are known to have a security loss at least linear in the number of signature queries when aiming for existential unforgeability under chosen message attacks (EUF-CMA) security, which was shown to be inherent in the standard model by Coron (EUROCRYPT 2002) for signature schemes where public keys are verifiable (i.e., where it can be efficiently checked whether a public key has unique signatures). The only known tight unique signature schemes in the literature that support verifiable public keys are variants of chain-based signatures (CRYPTO 2017, FC 2018, EUROCRYPT 2022), which achieve tight security in the random oracle model. To achieve constant security loss, however, these schemes require $\log q$ calls of the random oracle to sign and verify, where $q$ is an upper bound on the number of signatures generated using the scheme. In this work, we provide the first tight unique signature scheme with verifiable public keys which requires only a constant number (namely, six) random oracle queries to sign and verify. Specifically, we provide a general transformation akin to hash-and-sign which transforms a signature scheme with much weaker security (a variant of random unforgeability) into an EUF-CMA secure scheme. Signatures of our resulting scheme consist of at most 3 sub-signatures in parallel. Furthermore, we consider tightness in the multi-user setting, where the adversary may query signatures relative to many public keys, before deciding for which to forge. In this setting, we provide two constructions which achieve (1) a tight signature scheme, secure against semi-adaptive corruptions (i.e., where the adversary has to decide whether to corrupt a public key *before* making any signature queries relative to this key), and (2) a tight few-time signature scheme, secure against adaptive corruptions, where the scheme's setup is allowed to depend on an a-priori polynomial bound on the number of queries that the adversary has access to. These are the first unique signature schemes which are tightly secure in the multi-user model.
Last updated:  2026-11-02
Low-Space Quantum Discrete Logarithms on Genus-Two Jacobians
Uncategorized
Yan Huang, Yuling Chen, and Fangguo Zhang
Show abstract
Uncategorized
Quantum discrete logarithms on genus-two Jacobians require reversible arithmetic with controlled workspace. Generic divisor-addition formulas apply only outside an exceptional set, which must be accounted for in quantum phase computation. We give a randomized reduction using two fresh independent uniform public seeds in a finite abelian group of odd order to randomize a complete balanced addition tree. For inputs independent of the seeds, exceptional-pair densities bound the averaged phase-channel error and sampling failure probability. We apply this reduction to an odd-prime-order subgroup of a genus-two Jacobian over $\mathbb{F}_q$, where $q$ is an odd prime and the supplied curve model is a square-free monic quintic with zero quartic coefficient. Integer lifting, an independently shifted Legendre phase, and streaming Chinese remainder reconstruction yield a low-space sampler. For subgroup order $r=\Theta(q^2)$, the useful-sample probability is $1-\mathcal{O}(L/q)$, averaged over fresh seeds, for an exact uniform input state and ideal Fourier readout, where $L$ is the number of tree leaves. With window width $w=\Theta(\log_2 n)$, the sampler uses $10n+o(n)$ logical qubits, including both scalar registers, with $n=\lceil\log_2q\rceil$, and allows intermediate measurements, reset, and classical feedforward. For the Gaudry--Schost instance over $\mathbb{F}_{2^{127}-1}$, a $16$-bit window gives an analytic allocation of $1{,}971$ qubits and a capped-run Toffoli bound below $2^{60.561}$. A matched schedule derived from Chen et al.'s addition module uses $3{,}063$ qubits; both schedules retain the same $500$ scalar-input qubits. These comparisons are schedule-specific, and rotation synthesis is counted separately.
Last updated:  2026-11-02
Threshold Post-Quantum E-Voting from Lattice Commitments
Jalal Alizadeh, Yadigar Imamverdiyev, and Ali Huseynli
Lattice-based homomorphic e-voting protocols built on commitments, such as EVOLVE, keep ballots private against all but one authority and the tally verifiable even if all authorities collude, but need every authority to tally. We present T-EVOLVE, in which votes are Shamir-shared over the commitment message space: any t of n authorities that took part in the checking phase complete the tally, privacy holds against t-1 colluding authorities and verifiability against all. The voter proves that her committed shares form a Reed-Solomon codeword whose value at zero is a valid vote; the parity checks cost no communication, and tallying interpolates public column sums without norm growth. Complaints of authorities, including about ciphertexts that do not decrypt, are publicly verifiable given encryption with publicly verifiable opening, which we define and instantiate under LWE. We prove privacy, verifiability, individual verifiability and robustness in the classical random oracle model; the verifiability reduction is not tight and the parameters rest on classical hardness estimates. In our C implementation, a yes/no ballot for four authorities takes 109 KB without signatures, or 147 KB with the computed seed ciphertexts, and an authority aggregates 10^4 ballots in about three minutes per successful tally round on one core.
Last updated:  2026-11-02
Add/XNOR Chains: An NP-Complete Boolean-Arithmetic Problem at the Meet-in-the-Middle Barrier
Ping Wang, Mengxin Lv, Zishen Shen, and Fangguo Zhang
We introduce the Add/XNOR decision problem: given $n$ words of $n$ bits, decide whether they can be combined into zero by a left-associative chain in which each operator is either addition modulo $2^n$ or bitwise XNOR. We prove NP-completeness by a deterministic reduction from Subset-Sum{} in which four-bit guard fields and a parity normalization force every gadget to be all-additions or all-XNORs; hardness persists for every width that is a fixed rational power of the operand count, and 3-SAT reduces with linear parameter blow-up. The problem is a minimal model of Boolean--arithmetic mixing, and we give an exact theory of its linear and differential behaviour: a carry decomposition, closed forms for every single-bit linear correlation (for addition runs $z_1,\ldots,z_r$ the bit-$1$ correlation is $\prod_j2^{-z_j/2}\cos(z_j\pi/4)$, averaging exactly $(n+1)2^{-n}$), and an exact transposition differential with collision probability $2(5/8)^{m-1}-2^{-(m-1)}$, all confirmed experimentally. Both operations are triangular, which yields a low-bit dissection algorithm with worst-case time $\Ostar(2^{n/2})$ and space $\Ostar(2^{n/4})$ plus an explicit balance parameter; no technique we know of improves the exponent $1/2$. We explain why the representation technique that recently broke the $2^{n/2}$ barrier for Subset-Sum{} is not available to the natural formulation of non-commutative chains, report that CDCL solvers scale as roughly $2^{0.7n}$ in our experiments, and prove in an ideal chain model, where each operation is an independent random permutation, that planted search requires $\Omega(2^{(n-1)/2})$ oracle queries. We place the problem in the current fine-grained landscape, in which the 3SUM, APSP and (strong) exponential time hypotheses have been refuted: the conditional lower bound that the 3-SAT reduction would otherwise yield is void, and the exponential complexity of Add/XNOR is open in both directions.
Last updated:  2026-11-02
Construction and Classification of Minimum-Latency 5-Bit APN S-Boxes
Yaqi Qu, Xiutao Feng, and Ruanyiyang Sun
S-boxes serve as essential nonlinear building blocks in symmetric-key cryptography, where their cryptographic properties and hardware implementation costs jointly dictate the security and efficiency of lightweight primitives. This paper studies the construction and classification of minimum-latency 5-bit APN (Almost Perfect Nonlinear) permutations under a prescribed gate-delay model, using exact minimum latencies of Boolean component functions. Under the fixed gate-delay model of the NanGate 45nm standard cell library, we partition the search space into input-variable permutation (IP) equivalence classes to establish a comprehensive minimum-latency database covering all 5-input balanced nonlinear Boolean functions. This database delivers exact minimum latencies and gate-level implementations for all equivalence classes up to a latency of 150ps, while guaranteeing strict lower bounds on latency for classes exceeding that threshold, combining property filtering with circuit synthesis. We search the five affine equivalence classes of 5-bit APN permutations. For each affine transformation of the input, we use exact component-function latencies to select components with linearly independent masks and choose their polarities, obtaining S-box circuits without repeating gate-level synthesis for each candidate. Exhaustive search with latency-preserving input-variable permutation reduction establishes a minimum latency of 126.745ps over all 5-bit APN permutations under the prescribed gate-delay model, with explicit constructions attaining this minimum in every class.The classification results give the optimized latency distributions and numbers of optimal IP classes of input-affine transformations within each affine class. Comparisons with selected 5-bit S-box implementations under the same model show simultaneous reductions in some cases: latency decreases by $10.20\%$--$29.18\%$ and normalized gate area by $5.37\%$--$27.69\%$, while preserving the original S-box mappings.
Last updated:  2026-11-02
Revisiting Accountability in Accountable Tracing Signatures
Rei Naito, Kyoichi Asano, and Keita Emura
Accountable tracing signatures (ATS), introduced by Kohlweiss and Miers (PoPETs 2015), classify each group member (user) as either traceable or non-traceable. A traceable user corresponds to one in conventional group signature schemes whose identity can be revealed by the opener from a signature, whereas a non-traceable user cannot be identified from any signature they produce. The opener, who issues a witness, can certify a user's status via the Account algorithm. In this paper, we formalize accountability soundness, which ensures that no two witnesses can simultaneously certify a user as both traceable and non-traceable. We show that the Kohlweiss-Miers ATS scheme admits conflicting witnesses that violate this property. Since accountability is a fundamental aspect of ATS, as reflected in its name, such conflicting witnesses undermine the intended guarantees of the primitive. To address this issue, we propose a patched version of the Kohlweiss-Miers ATS scheme that provides accountability soundness. We also discuss the applicability of our attack to the lattice-based ATS scheme (Ling et al., CT-RSA 2019) and the isogeny-based ATS scheme (Shaw-Dutta, Indocrypt 2021), together with preliminary investigations of possible countermeasures. We emphasize that all our attacks fall outside the original security models.
Last updated:  2026-11-02
Optimizing FROST for Message Capacity
Philipp Jovanovic, Ben Riva, and Arnab Roy
The FROST threshold signature scheme achieves round optimal Schnorr signing through a double-nonce construction, but requires two presignatures per signature. Since each presignature demands an expensive distributed key generation (DKG) protocol, this overhead is significant for high-throughput applications. FROST builds on a core presignature protocol (that we call FROST-core) that uses hash-based re-randomization of presignatures. We investigate whether fewer presignatures can be used to sign multiple messages, improving FROST-core's \emph{message capacity}. We first show that the natural generalization of using $k$ presignatures for $k$ messages is insecure: an extended ROS attack enables forgery even for $k=2$. However, we prove that using $k+1$ presignatures for $k$ messages achieves security in the Generic Group Model combined with the Random Oracle Model. This improves message capacity from 50\% (standard FROST-core) to $\frac{k}{k+1}$, approaching 100\% as $k$ grows. We further extend our analysis to a modified FROST-core protocol in which a set of presignatures is generated by different parties and used for signing $k$ messages. Security holds as long as at least $k+1$ presignatures were created by honest parties. Update: We found a non-trivial ROS attack on our protocol by using AI tools. We plan to publish the attack and a proposed fix in the future. The proposed protocol in the current paper with $k+1$ presignatures for $k$ signatures is forgeable. We retain the article as is for reference.
Last updated:  2026-11-01
Verifiable Data on Bitcoin: FlatMerkle Commitments, Refutable Proofs, and FlatChecks
Sergio Demian Lerner
We give a method to publish data on Bitcoin and to verify properties of that data on Bitcoin itself, against a publisher who may lie. The data is a FlatMerkle file – a structured byte string whose ordinary SHA-256 supports logarithmic inclusion proofs and logarithmic proofs of malformation – placed in a transaction's annex or, at four times the cost but relayable by Bitcoin Core, in an output. We show that the publisher's ordinary Taproot signature, with a suitably chosen signature-hash type, binds the publisher to the published data in a form that a dispute can authenticate with a single SHA-256 compression plus the signature check, or with three compressions when no annex is used. Claims about the data, and claims about such claims, are published as proof messages in two formats: a plain encoding, refuted by revealing it whole, and a traced encoding that stores the verifier's output after each level, so that any false message is refuted by revealing at most five of its elements. The format, chosen by a cost model that weighs challenge bytes against published bytes, is fixed by public context so that no message can be read in two formats; chains of claims about claims settle at four logical elements. A dispute thus reduces to a few dozen SHA-256 compressions and one Schnorr verification per commitment – too large for Bitcoin Script, but small enough to adjudicate with an interactive bisection game, a chunked script in the manner of BitVM2, or a garbled circuit. The same technique verifies any locally refutable verifier, one whose every rejection is witnessed by a single check over a few words of a canonical trace. In a FlatCheck, the prover publishes only the proof; the trace, the verifier's intermediate values, is published only if a challenger asks for it, and the dispute then examines the single check he names. When the verifier splits into groups that each read a few parts of the proof, a challenge forces the trace of one group only. We give two examples: a toy L2 of signed transfers, whose 512-transfer batches cost 12,200 vbytes to claim, and a Bitcoin header-chain light client verified on Bitcoin itself, which claims a retarget period of 2,016 headers in 45,200 vbytes; a dispute over a local check costs about 37,500 and 49,200 vbytes, and one over a malformed trace about 77,100 and 99,800, independently of the number of groups. Verifying STARK proofs is another application. We also remove FlatMerkle's restriction to power-of-two sizes without padding.
Last updated:  2026-11-01
Key Recovery Against RLCE via the GIJS Distinguisher
Jacob Alperin-Sheriff
We present an experimental cryptanalysis of the RLCE cryptosystem at the heretofore secure $w=n-k$ parameter regime. Our attack relies crucially on the recent Ghoshal--Ishai--Jain--Sun (GIJS) distinguisher The attack shortens the public key at random positions, runs the GIJS distinguisher with \emph{every} column as hold-out, and uses this distinguisher to identify twin pairs based on how they appear across trials. Three pairs so identified are unmixed by a root-finding cascade, and Sidelnikov--Shestakov on the resulting $k \times (k+3)$ pure matrix recovers the key. We experimentally verify our attack by breaking the ID-0 (128-bit) in 30.5 core-hours (about 3 hours of wall time) on a standard higher-end laptop.
Last updated:  2026-11-01
Privacy Coins Under Viewing Key Compromise
Adrian Cinal
Anonymity guarantees of privacy-oriented cryptocurrencies are garnering negative attention from lawmakers who view them as antinomic to accountability. Having recognized their potential for innovation, however, regulators may not want to outright ban privacy coins but instead seek a middle ground where financial oversight is effective, and still some privacy is maintained. Mature designs, such as Zcash, Monero, or Firo, are expected to facilitate this through so-called viewing keys that can be disclosed to third parties for the purpose of supervision. This paper studies which privacy guarantees continue to hold once they have been. In doing so, it fills the gap in provable anonymity guarantees for Zcash and Firo under the compromise of the incoming viewing key, but nevertheless shows that malicious parties may happily surrender all their viewing keys and still find very efficient ways of evading financial monitoring. Of independent interest are several shortcomings identified in the prevailing security arguments for Monero.
Last updated:  2026-11-01
A Constant-Rate Compiler for Continual Memory Leakage
Shweta Agrawal, Anuja Modi, and Rajeev Raghunath
Leakage-resilient compilers transform any computation so that physical leakage from its implementation reveals nothing beyond its input-output behaviour. In this work, we investigate this question in the well-motivated continual memory leakage (CML) model, that captures a variety of relevant real-world side-channel attacks and subsumes several other well studied models in the leakage domain. In this model with two independently leaking components (at least two are necessary), all known general compilers tolerate only an inverse-polynomial leakage-rate. We give a compiler with constant leakage-rate, in the hybrid model with a simple inputless leak-free sampler as in Dziembowski and Faust (TCC 2012). It protects any deterministic computation on a fixed secret with public inputs and outputs, and comes with a transfer theorem: any security game in which the adversary has an oracle for the computation remains secure when every oracle call is replaced by a compiled evaluation that leaks continuously. Our compiler uses no computational assumption. Our main application is public-key encryption. Applied to the decryption of any IND-CCA2 secure PKE, the compiler gives IND-CCLA2 security, i.e. CCA2 security even when every decryption leaks, including after the challenge ciphertext, with the same public key, ciphertexts and encryption algorithm. Instantiating the base scheme gives such PKE from LWE and from LPN improving upon the previous best post-quantum constructions in this model, which supported only inverse-polynomial leakage-rate. We also obtain signatures, PRFs and MACs with constant leakage-rate via a natural generalization. Our key idea is to pack the entire configuration of a universal machine into one element of a large extension field, so that any computation keeps only a constant number of inner-product encodings in memory at any time, each for only a constant number of rounds. Our techniques are inspired by packing techniques in homomorphic encryption adapted to a completely different context. We are optimistic that our techniques will find other applications.
Last updated:  2026-11-01
The Information-Theoretic Limits of Hiding Among Decoys in the Shuffle Model
Pengcheng Su, Haibo Cheng, and Ping Wang
Hiding a genuine message among plausible decoys is a recurring principle in cryptography and privacy, underlying honeywords, symmetric encryption, and anonymous data collection. We study the information-theoretic security of mechanisms that release a uniformly shuffled sequence containing one genuine message and $n-1$ decoys over a $d$-symbol alphabet. We characterize how restrictions on decoy generation determine achievable secrecy. We distinguish four classes of decoy mechanisms: i.i.d., heterogeneous independent, correlated message-oblivious, and message-dependent. For every fixed $d\ge2$, the optimal worst-case mutual information over message priors is $\Theta_d(n^{-1})$ for both independent classes and $\Theta_d(n^{-2})$ for correlated message-oblivious mechanisms. A discrete spectral construction achieves the latter rate without knowledge of the prior. Message-dependent mechanisms achieve perfect secrecy when $n\ge d$. Moreover, even with $n=3$, heterogeneous decoys can improve upon i.i.d.\ decoys by an arbitrarily large multiplicative factor. These results quantify the distinct benefits of heterogeneity, correlation, and dependence on the genuine message. A key-symmetrization reduction shows that every perfectly correct symmetric encryption scheme with a key drawn uniformly from a key space of size $n$ admits a message-dependent shuffle construction without increasing plaintext leakage. This connects optimal message secrecy to preimage-constrained channel design and yields an exact characterization of key leakage for all message-leakage-optimal ciphers when the number of keys does not exceed the plaintext support size. For canonical mechanisms, whose decoys are drawn i.i.d.\ from a blanket distribution $Q$ independently of the genuine message, a unified likelihood-ratio representation yields exact expressions for mutual information, total-variation information, message recovery advantage, and expected posterior variance, together with explicit finite-sample remainder bounds for the mutual-information expansion. For a fixed non-degenerate message prior $P$, the leading asymptotic coefficient of message mutual information is minimized by $Q^*(y)\propto\sqrt{P(y)(1-P(y))}$, which generally differs from $P$. For binary alphabets, quasi-uniform blankets exactly minimize message total-variation information for every $n\ge2$, independently of the prior.
Last updated:  2026-11-01
Polynomial Batch Accumulators for Onboarding-Dominant Zero-Knowledge Membership Proofs
Samanta Karmaker, Sampad Sikder, Md Ariful Islam, and Md Sadek Ferdous
Zero-knowledge membership accumulators are conventionally tailored for slowly growing sets with frequent proof generation, creating severe efficiency bottlenecks for modern compliance architectures. Governance-driven applications like FATF customer due diligence, eIDAS 2.0 wallet issuance, and MiCA VASP authorization invert this structure. In this regime, rosters are ingested at an enterprise scale, while proofs are requested selectively. To resolve this mismatch, we introduce Polynomial Equation Batching (PEB), a membership accumulator for onboarding heavy workloads. PEB represents up to 128 members per batch as a characteristic polynomial and hashes its coefficients via Poseidon, seamlessly scaling to arbitrarily large populations through parallel batching. We present two variants: PEB-A, which maps member secrets directly to polynomial roots for maximum performance, and PEB-B, which hashes secrets in-circuit for hardened security. Implemented in Noir and Barretenberg on BN254, and evaluated for up to 1,048,576 members, PEB provides significant performance improvements. Compared to incremental Merkle trees, PEB-A achieves up to a 149.07x mean speedup in per-user initialization while incurring a modest 33.87% proof-generation overhead. Additionally, against static Merkle trees, PEB-A delivers a 15.71x speedup during setup. By shifting off-circuit overhead from hash evaluations to field multiplications, PEB provides a highly efficient, scalable solution for real-world zero-knowledge compliance systems.
Last updated:  2026-11-01
SoK: Multiple Concurrent Proposer Blockchains
Benjamin Marsh, Alejandro Ranchal-Pedrosa, and Max Resnick
Multiple concurrent proposer (MCP) protocols let several parties contribute transactions to the same ledger update. They can distribute communication and reduce one proposer's control over inclusion and order, but these benefits depend on how the contributions are combined. We describe a common architecture from transaction receipt through proposal formation, agreement, data recovery, ordering, execution, and state finality. Within it, we identify four direct MCP families: fixed proposal vectors, selected proposal collections, persistent proposal streams, and causal proposal DAGs. We compare them with constrained assembly, where several parties restrict a block assembled by one party. Across 39 configurations, we distinguish agreement and progress from service for a particular transaction, and compare hiding, ordering, communication, throughput, and latency at explicitly named endpoints. The comparison shows why additional proposers alone do not guarantee inclusion, why hiding does not settle who can react last, and why parallel disseminations need not improve useful execution. It also identifies the recovery, payment, and organizational assumptions needed to turn independent proposal rights into reliable transaction service.
Last updated:  2026-11-01
Highly Efficient and Round-Optimal Asymmetric PAKE
Zachary Barbanell and Jiayu Xu
An asymmetric Password-Authenticated Key Exchange (aPAKE) protocol allows a client, who holds a raw password, and a server, who holds a one-way mapping of the password, to jointly establish a cryptographically strong session key, without an authenticated channel. The standard security definition for aPAKE is in the Universal Composability (UC) framework. Despite its great potential of being used in practice, existing aPAKE protocols are either not round-optimal, computationally inefficient, or not proven secure. In this work, we present two aPAKE protocols that are 1 simultaneous round, UC-secure, have reasonable computational costs, and rely on mild cryptographic assumptions. Our first protocol is in the Random Oracle Model and the Algebraic Group Model (ROM+AGM), secure under the CDH assumption, and has computational cost comparable to the most efficient aPAKE protocols in the literature (1 simultaneous round or not). Our second protocol is in the ROM only and secure under the DDH assumption, and also has significantly lower computational cost than the only other UC-secure 1 simultaneous round aPAKE protocol. Interestingly, even our second protocol does not rely on the gap Diffie-Hellman assumption, which requires creative application of the forking lemma.
Last updated:  2026-11-01
CHAMPing at the Bit: Short Square-Root Collisions for Two-Generator Cayley Hashes
Freeman Slaughter
For $A,B\in\text{GL}(\mathbb{F}_p)$, a Cayley hash $\text{HM}(w)$ maps a bit string $w \in \{0,1\}$ to the corresponding product of $A$ and $B$. We construct collisions by finding two palindromes whose matrix products commute. A symmetric form shared by the two generators places the hash of every palindrome in a three-dimensional subspace containing the identity. Two such hashes commute when their traceless parts are proportional, which defines a class map with $p+2$ values, so the pigeonhole principle gives collisions of $4\lceil\log_2(p+3)\rceil$ bits. Under a uniformity heuristic, a dictionary search finds such a pair after about $\sqrt{\pi p/2}$ class evaluations. Adding one bit to each half-message gives an expected bound of $O(\sqrt p)$ evaluations, with no assumption on how the classes are distributed. When the common form is singular, the generators are simultaneously triangular and the same argument applies to ordinary words. For CHAMP-512 and CHAMP-1024, the heuristic search finds collisions of $512$ and $1024$ bits after about $2^{64}$ and $2^{128}$ class evaluations, and the one-bit-longer, distribution-independent variant finds collisions of $516$ and $1028$ bits at the same leading cost. This matches the asymptotic cost of an earlier commuting-product search for CHAMP, whose messages have $O(\log^2(p))$ bits, and improves on the bound of about $p$ given by an earlier palindrome restriction. For every pair over an odd prime field, this also shortens the collisions of the general algorithm of Mullan and Tsaban from $O(\log^2(p)/\log(\log(p)))$ to $4 \lceil \log_2(p+3) \rceil$ bits. Since the argument applies to every pair $A,B$, no pair of generators gives a $2\times2$ Cayley hash over $\mathbb{F}_p$ with collision resistance greater than $O(\sqrt p)$. We give an explicit proof-of-concept collision for the CHAMP matrices at a $36$-bit prime, and prove that every sufficiently short message can be recovered from its digest for the main CHAMP pair. To close, we demonstrate that since reversal and symbol exchange act as sign changes on quaternion coordinates, the alternative CHAMP pair possesses a much greater degree of symmetry, but do not yet see how to utilize this to find collisions below the square-root bound.
Last updated:  2026-10-31
Concrete Minimum Distance Bounds of Accumulate Codes over any Fixed Finite Field
Alexander R. Block, Himanshu Dongre, and Hendrik Waldner
We present a new concrete unified distance analysis of three accumulate-type error-correcting codes over any finite field, specifically the Repeat-Accumulate (RA), Repeat-Accumulate-Accumulate (RAA), and Expand-Accumulate (EA) codes. For message length $k$, codeword length $n$, finite field size $q>2$, and target relative minimum distance $\delta$, we give new upper bounds on the probability that each of the above codes do not have minimum distance at least $\delta$. Our bounds are concrete and explicit: they do not rely on $n$ or $q$ being sufficiently large. We present (multiple) closed-form upper bounds on the failure probability for each code, and complement these bounds with asymptotic analyses that (nearly) match prior-known asymptotic bounds. Our technical core is a new fine-grained union bound for accumulate codes, which may be of independent interest, that examines inputs to the accumulator from a purely distributional perspective, deriving properties that are necessary for an input vector to accumulate to a targeted output weight, and analyzing the probability the input distribution achieves these properties. This fine-grained union bound generalizes the input-output weight enumerator approach used by many prior works. Our concrete analysis shows that (1) the RA code has concretely small distance (a maximum of $\delta\leq 2.4979\times10^{-8}$ for $k=2^{40}$ and $q=2^{32}$, except with probability $2^{-60}$), and (2) the RAA and EA codes achieve somewhat large concrete distance for smaller field sizes $q \leq 2^{32}$. Concretely, for rate $k/n = 1/4$, $k\in\{2^{40},2^{50}\}$, and $q=2^{8}$, the RAA code has distance $\delta=1/8$ except with $2^{-60}$ probability, whereas the rate $1/2$ and $1/4$ EA code for the same $k$ and $q=2^{4}$, respectively, has distance $\delta\leq 0.0689756$ and $\delta \leq0.232955$ except with probability $2^{-60}$. For fields of size $q\geq 2^{32}$, under our concrete bounds, all codes experience a sharp drop-off in attainable minimum distance, as our analysis targets (small) fixed $q$.
Last updated:  2026-10-31
Private Accounts Without $O(N)$ Work Through a Hybrid State Model
Philipp Gackstatter, François Garillot, Marti Górny, Adrian Hamelink, Al Kindi, Philippe Laferrière, Robin Salen, Brian Seong, and Bobbin Threadbare
Privacy-preserving smart contracts face a scalability problem. In account-balance-vector designs, hiding which accounts changed requires that every transaction perform an indistinguishable update over the global state, so validators pay work linear in the number of accounts for every private transfer. UTXO systems avoid this by validating local spends, but do not provide the same account-style programming model. We argue that the usual "account vs.~UTXO" framing conflates state representation and execution model, two choices that can be made separately. Miden, an Ethereum Layer 2, separates them. It uses persistent accounts for programmability, asynchronous notes for value transfer, and client-side proving for execution. Validators verify proofs and update commitments without re-executing transactions or accessing uninvolved state. The result is an account-based platform with private transfers and private computation, while keeping validator work per transaction logarithmic in the number of accounts.
Last updated:  2026-10-31
MinMandate: Task-Hiding Payment Authorization for Web Agents
Ge Gao, Haining Yu, Zhichao Liu, Dongyang Zhan, Yuanxiao Zhu, and Zhongyun Hua
AI agents increasingly pay for Web services on behalf of their users to complete complex tasks. Such a task needs many payments, and the user usually must approve each one, forcing the agent to stop at every payment. Mechanisms such as the Agent Payments Protocol (AP2) therefore enable the user to sign one payment mandate in advance that bounds the agent's payments for the task. However, whoever checks the mandate can learn the task, which is often sensitive. Specifically, (1) the user's wallet can see the full mandate when it checks each payment, so it can trace every payment to the task; and (2) although each merchant sees only the payment it receives, it verifies that payment under a signing key that repeats across the task, so colluding merchants can link the payments and reconstruct the task. We present MinMandate, a task-hiding payment authorization system for AI agents in which the user approves a task-bounded payment mandate once. In MinMandate, the wallet checks each payment through a constant-size keyed-verification policy credential, which reveals neither what the mandate allows nor which mandate the payment comes from. Each merchant then accepts the wallet's one-time ticket as proof of payment and never sees the mandate or its signing key. Formally, we prove authorization soundness and unlinkability in our threat model. Our experiments show that the overhead of MinMandate is practical, with a payment taking 197 ms and under half of AP2's bytes. Notably, MinMandate cuts wallet-side tracing from every payment under AP2 to the level of random guessing. Moreover, from their own payment-request records alone, colluding merchants can reconstruct the user's task in 47% of the cases under AP2 but in only 8% under MinMandate.
Last updated:  2026-10-31
Beyond Standard Indifferentiability: Simulator Properties for Fiat-Shamir Security
Ashrujit Ghoshal and Sikhar Patranabis
The Fiat-Shamir transform converts public-coin interactive arguments into non-interactive arguments (NARGs). Its security is typically analyzed in the random-oracle model, while implementations instantiate the random oracle with structured hash constructions. Standard indifferentiability is the natural abstraction for justifying this replacement. Chiesa and Orru (TCC ’25), however, showed that standard indifferentiability does not generally preserve the information and reset behavior needed by common Fiat-Shamir extraction arguments, and proposed stronger notions of indifferentiability to bridge this gap. We show that standard indifferentiability can nevertheless be retained as the oracle-replacement abstraction. For knowledge soundness, we give generic transfer theorems for three extraction interfaces: proof-only straight-line extraction follows from standard indifferentiability alone; transcript-dependent extraction additionally requires transcript reconstruction; and rewinding extraction requires reconstruction for rewinding, preserving simulator behavior across invocations with the same hidden randomness. Our results apply to worst-case polynomial-time extractors. Moreover, we show that the rewinding requirement is inherent: assuming discrete-logarithm hardness, we construct a perfectly indifferentiable construction and fixed prover admitting error-free rewinding extraction in the ideal world, while every polynomial-time construction-world extractor succeeds only with negligible probability. We instantiate our framework for tagged prefix-free Merkle-Damgard and a fixed-output permutation sponge. The former admits exact transcript and rewinding reconstruction, while the latter admits exact transcript reconstruction and rewinding reconstruction with negligible statistical error incurred only once, independently of the number of restarts. For zero knowledge, we give a semantic formulation where one persistent simulator jointly generates the proof and public-oracle interaction. Here, standard indifferentiability alone yields a generic transfer theorem, requiring neither reconstruction property and incurring only the indifferentiability error. Thus standard indifferentiability provides a common oracle-replacement abstraction for knowledge soundness and semantic zero knowledge, with extraction-specific requirements isolated as separate simulator properties.
Last updated:  2026-10-31
Poly Versus Polyval
Kaushik Nath and Palash Sarkar
We revisit the basic construction of polynomial evaluation based hash function, which we call Poly, over binary extension fields $GF(2^n)$, where $n=64k$ and $k\geq 2$. Unlike GHASH, the NIST standard polynomial evaluation based hash function for $n=128$, Poly does not perform the unnecessary bit reversals of each $n$-bit block, and consequently is faster than GHASH. Further, Poly differs from Polyval, -- a faster alternative to GHASH, -- in that Poly performs usual reduction, while Polyval performs Montgomery reduction. We identify suitable choices of the field representing irreducible polynomials which make usual and Montgomery reductions efficient. We provide detailed algorithms, and associated proofs of correctness for both kinds of reductions. Based on the algorithms, we report carefully optimised assembly implementation of both Poly and Polyval for $n=128,256$ and $512$. Our theoretical analysis and experimental timing results show that for $n=128$, Polyval is faster than Poly, while for $n=256$ and $512$ (as well as for higher values of $n$), Poly is faster than Polyval. The cases $n=128$ and $n=256$ are of current relevance due to the ongoing NIST process for developing cryptographic accordions.
Last updated:  2026-10-31
Anamorphic Proofs of Knowledge from Prover Randomness
Zhi Lu, Songfeng Lu, and Jiaheng Zhang
Anamorphic encryption and signatures deliver a hidden message through a normal-looking ciphertext or signature. We move from hidden messages to hidden knowledge claims and introduce anamorphic proofs of knowledge, in which a single proof certifies its normal statement publicly while convincing a designated checker that the prover knows a witness for a separately registered anamorphic statement, such as a long-term credential. Our construction reuses a commitment the normal prover already makes to its own randomness. The prover adds a secret mask to the anamorphic witness and uses the sum as those coins, so the existing commitment carries the anamorphic statement while the public statement, proof format and length, and normal verifier remain unchanged. Two properties of the normal proof system suffice: its randomness commitment must be extractable, and the complete proof must be simulatable at a commitment that the checking key fixes in advance, which normal zero knowledge does not provide. The resulting normal and anamorphic modes are indistinguishable to an external observer, even given both witnesses and the normal prover's actual random coins. The same opening extractor gives anamorphic knowledge soundness and two guarantees against the checker: it cannot produce an accepting proof for a statement registered independently of its key, and it cannot produce a proof and witness for a statement of its own choice, in both cases at an unused label and after obtaining honest proofs at other labels. The checker learns neither witness. We instantiate the construction in random-base Compressed $\Sigma$ and in Bulletproofs with range aggregation in the random-oracle model. Finally, we show that three-move protocols with witness-assisted challenge transfer, including Schnorr and uncompressed representation protocols, cannot support the primitive in a local-checking model.
Last updated:  2026-10-31
SpreadMAYO: Unlocking Greater Parallelism for Faster MAYO Signatures on GPUs
Zhuoyu Xie, Tian Zhou, Fangyu Zheng, Yijing Ning, Yi Bian, Wangchen Dai, Jiankuo Dong, Yuewu Wang, Jingqiang Lin, and Jiwu Jing
Quantum computing threatens public-key cryptography, motivating post-quantum signature standardization. MAYO, a multivariate Round 3 candidate in NIST's additional signature process, offers compact keys and signatures. However, prior GPU implementations do not fully exploit parallelism within each MAYO operation: equation-slice partitioning serializes independent matrix work, while signing requires frequent synchronization among threads during linear-system construction and elimination. We present SpreadMAYO, a high-throughput GPU implementation of MAYO Round 3 that exposes greater parallelism and reduces synchronization through finer task partitioning and a revised signing pipeline. SpreadMAYO distributes matrix contractions across rows, output positions, and 64-bit limbs while reusing operands in registers. Each limb packs sixteen GF(16) coefficients; native 32-bit operations process its halves without lookup tables. For signing, threads privately accumulate columns with deferred polynomial reduction, transpose packed columns into rows using warp shuffles, and eliminate rows below each pivot in parallel. Additionally, we employ a hybrid AES design to accommodate different workloads and fuse key expansion with matrix computations to reduce global-memory traffic. On an NVIDIA GeForce RTX 4090, SpreadMAYO outperforms the Round 3 adapted GPU baseline by 2.33–3.71× in key generation, 4.40–6.93× in signing, and 3.42–5.13× in verification, reaching up to 10.75× in repeated-key server signing.
Last updated:  2026-10-31
Exact Error Bootstrapping and Comb Bootstrapping in FHEW/TFHE
Philippe Chartier and Mohammed Lemou
In FHEW and TFHE, bootstrapping evaluates the decryption function via a blind rotation, whose resolution limits the message space. We propose instead to bootstrap the \emph{error}. By rounding the ciphertext at a resolution that is a multiple of the message modulus, we preserve the message exactly. Reduction modulo a small integer then yields a noise-free encryption of the error, which a single blind rotation lifts exactly before it is subtracted. The message modulus is thus constrained solely by the noise and can be much larger than in standard TFHE. Since the error takes far fewer distinct values than the ring degree, a single blind rotation can also refresh several ciphertexts simultaneously. We call this procedure the comb bootstrap. Between refreshes, an integer remains encrypted in a single ciphertext, allowing additions modulo the message modulus and multiplications without programmable bootstrapping. Built on TFHE-rs, for $8$-bit integers on a single thread, our refresh is $3.5$ times faster than that of TFHE-rs, and $9.1$ times faster with the comb bootstrap; multiplication is $6.5$ times faster. In a residue number system, multiplication of integers modulo $\widehat P\ge 2^{32}$ is $19$ times faster than in TFHE-rs. The error bootstrap serves exclusively to refresh ciphertexts; evaluating any other function still requires programmable bootstrapping.
Last updated:  2026-10-31
Card-Based Protocols with Mixed Encoding: Computable Functions and the Minimum Number of Cards
Saeki Koizumi, Xiao-Nan Lu, and Hidetomo Nabeshima
Card-based cryptography performs secure computation with physical cards, where a bit is usually encoded by two cards but can also be encoded by a single card. We study mixed encoding, in which one player gives a single-card commitment and the other a two-card commitment, for perfectly secure protocols with finite runtime and public actions. Mizuki (Theoretical Computer Science, vol.~622, 2016) proposed an AND protocol with mixed encoding as a building block for the conjunction of many variables. To give a single-card commitment, a player chooses one of two cards of different types and must keep the other card hidden. We call this card a frozen card and include it in the number of cards. We show that a secure protocol in committed format never turns over a single-card input, and use this to determine the functions that can be computed when all inputs are single-card commitments and to characterize those that can be computed with mixed encoding, which include AND but not XOR. We prove that Mizuki's five-card protocol is card-minimal. No AND protocol with mixed encoding uses four cards, including the frozen card, even with arbitrary shuffles and a non-committed output. For formal verification, we express the existence of a protocol as a quantified Boolean formula (QBF) in which security is a quantifier alternation, and confirm this lower bound with QBF solvers for a class of protocols. We discuss the number and type of shuffles, and analyze Mizuki's protocol under injection attacks that change only the input.
Last updated:  2026-10-30
Efficient Scalable Oversight via Rewinding
Ziyi Guan, Yael Tauman Kalai, Ron Rothblum, and Zoe Xi
Scalable oversight asks how a weak verifier can check the outputs of computations performed by more powerful AI systems. One proposed approach uses relativizing interactive proofs, in which a weak verifier checks the output of a complex oracle-aided computation by interacting with one or more powerful provers. A prominent example is debate, which is highly efficient but assumes that one of two powerful AI models, or provers, is truthful. For certain classes of oracle-aided computations, this assumption can be removed, but at substantially greater computational cost. In this work, we introduce \emph{rewindable interactive proofs} (RIPs), a new model of relativizing interactive proofs for scalable oversight. In an RIP, the verifier may rewind the prover to an earlier state of the interaction and continue from there. This is possible when the prover is an AI model, since the verifier can save a snapshot of the model's state and later restore it. We construct a relativizing RIP for computations whose outputs are robust to changing a small fraction of oracle answers. Our construction is more efficient than prior relativizing proofs that do not assume a truthful prover, and it uses no cryptography. In our construction the honest prover runs in time linear in that of the original computation, and the verifier, after a one-time preprocessing step, runs in time nearly linear in the input length (which can be much smaller than the computation itself). We implement our protocol, report a preliminary MNIST experiment, and show that an RIP can be faster than a state-of-the-art deployed proof system. RIPs may be of independent interest. Rewinding is possible whenever the verifier controls the prover's machine, for example when the prover runs on trusted hardware or in a virtual machine whose state can be checkpointed.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.