From Newsgroup: sci.crypt

## In this issue
1. [2025/1315] NetAdapt: Network-Adaptive Hybrid Protocol ...
2. [2025/1845] HE-based On-the-Fly MPC, Revisited: Universal ...
3. [2026/653] Random Robust Secret Sharing with Perfect Privacy ...
4. [2026/978] Verifying Consensus Protocols from LLM-assisted ...
5. [2026/1037] On Publicly Verifiable Tokens in Group Signatures ...
6. [2026/1047] Round-Optimal Subversion-Resilient UC PAKE from ...
7. [2026/1157] A Simple and Unified Approach for Proving Knowledge ...
8. [2026/1780] The Limits of $t$-Private Share Conversion
9. [2026/1895] Large-Universe (Multi-Authority) ABE from LWE
10. [2026/1904] When Module Lattice Leaks: Horizontal Fusion ...
11. [2026/1908] A Generalized Wiener-type Attack Against a Family ...
12. [2026/1914] AIPA: Anonymous Image Provenance Authentication in ...
13. [2026/1915] A RAM-Efficient Implementation of Falcon
14. [2026/1956] PRISM: Efficient zkSNARKs for RNS-Based Homomorphic ...
15. [2026/1957] More Efficient Secret-Shared Joins with ...
16. [2026/1958] Arithmetic for Large-Characteristic Finite Fields ...
17. [2026/1959] Information-theoretic two-server PIR requires ...
18. [2026/1960] Unbounded Broadcast and KP-ABE with Sublinear ...
19. [2026/1961] A Formal Security Analysis of a MACsec Key ...
20. [2026/1962] Compare Before Clearing: Exact Integral-Comparison ...
21. [2026/1963] Impossible Polytopic Attack Revisited: Low-Data ...
22. [2026/1964] Three-Round Weak Non-Malleable Zero-Knowledge Argument
23. [2026/1965] Lattice-based Threshold Traitor Tracing with Public ...
24. [2026/1966] Design and Analysis of Isogeny-Based Strong ...
25. [2026/1967] Azkaban: A Zero-Knowledge Abstract Analysis for ...
26. [2026/1968] The Closest-Vector Problem over Cyclotomics and its ...
27. [2026/1969] Efficient Polynomial System Solving via Dixon ...
28. [2026/1970] Multi-Party Distributed Point Functions, Revisited
29. [2026/1971] Component-Dual Compression and the Exact ...
30. [2026/1972] Criminology: Refined Techniques for Compression ...
31. [2026/1973] Addition-Efficient MDS Matrices from ...
32. [2026/1974] Exact-Coset Response Existence in SQIsign-like ...
33. [2026/1975] Oblivious Signaling
34. [2026/1976] Properties of the Me Operation and Me-Scalar ...
35. [2026/1977] Lattice-based Secret-Key Functional Encryption for ...
36. [2026/1978] Succinct Two-Round Two-Party Signing from PCFs
37. [2026/1979] From Specs to Apps: Verifying and Monitoring Models ...
38. [2026/1980] Better Security Proofs for X3DH and XHMQV
39. [2026/1981] Parallelized Authenticated Encryption with Tag ...
40. [2026/1982] Cryptanalysis of the Alternative Mod-2/Mod-3 Weak PRF
41. [2026/1983] Akita: A High-Performance Lattice-Based Polynomial ...
## 2025/1315
* Title: NetAdapt: Network-Adaptive Hybrid Protocol Assignment for PPML
* Authors: Yuntian Chen, Tianpei Lu, Zhanyong Tang, Bingsheng Zhang, Zhiyuan Ning, Zhiying Shi, Kui Ren
* [Permalink](https://eprint.iacr.org/2025/1315)
* [Download](https://eprint.iacr.org/2025/1315.pdf)
### Abstract
The widespread use of machine learning on sensitive data makes Privacy-Preserving Machine Learning (PPML) essential for data confidentiality. Current state-of-the-art PPML systems employ hybrid protocol designs to evaluate various operators to achieve better performance; yet, existing hybrid approaches adopt fixed protocol assignments without considering the deployment setting, resulting in inefficiencies across diverse network environments, such as LANs and WANs. To address this, we introduce NetAdapt, a cost-model-driven framework that automatically assigns FHE and MPC protocols to optimize inference efficiency under varying network conditions, by designing a predictive cost model based on the dialect of the Multi-Level Intermediate Representation (MLIR)rCOs Tensor Operator Set Architecture (TOSA), and an ILP-based solver for managing the cross-protocol conversion while dynamically updating FHE costs based on homomorphic multiplication depth. Experimental results demonstrate that NetAdapt delivers $6.68\times$ to $12.92\times$ improvements in inference running time compared to state-of-the-art solutions, allowing network-agnostic PPML.
## 2025/1845
* Title: HE-based On-the-Fly MPC, Revisited: Universal Composability, Approximate and Imperfect Computation, Circuit Privacy
* Authors: Ganyuan Cao, Sylvain Chatel, Christian Knabenhans
* [Permalink](https://eprint.iacr.org/2025/1845)
* [Download](https://eprint.iacr.org/2025/1845.pdf)
### Abstract
On-the-fly multi-party computation (OtF-MPC, L||pez-Alt, Tromer, and Vaikuntanathan, STOC 2012) allows clients to join a computation dynamically without remaining online, while outsourcing the computation to an untrusted but powerful server. Existing OtF-MPC constructions rely on composing multi-party homomorphic encryption with zero-knowledge or succinct arguments. While both components have seen substantial efficiency and expressivity improvements in recent years, the security of their composition has not been revisited under these modern refinements.
In this work, we revisit OtF-MPC through the lens of composable security. We extend the original analysis to systematically capture recent advances in these two building blocks, and to reason about their secure composition. We focus on multi-group homomorphic encryption (MGHE), a unifying abstraction that generalizes threshold and multi-key HE, and emerges as the natural backbone for OtF-MPC.
Our contributions are fourfold.
(1) We introduce the first Universal Composability (UC) ideal functionality for MGHE, jointly modeling client and server privacy, approximate or imperfect computation, and threshold security. (2) We define fine-grained security notions for MGHE and show that they are sufficient to realize this functionality against semi-malicious adversaries. (3) We revisit generic compilers that combine MGHE with any-simulation-extractable zkSNARKs, and prove that they realize OtF-MPC against fully malicious adversaries. (4) We introduce a split-witness ideal functionality for NIZKs, which separates the witness component that must be supplied by the ideal adversary from an existential component that only needs to be certified. We show that a Naor--Yung-style composition of MGHE and split-witness NIZKs realizes OtF-MPC while avoiding full extraction from the NIZK
## 2026/653
* Title: Random Robust Secret Sharing with Perfect Privacy and its Applications * Authors: Mohammad Hassan Ameri, Jeremiah Blocki
* [Permalink](https://eprint.iacr.org/2026/653)
* [Download](https://eprint.iacr.org/2026/653.pdf)
### Abstract
Secret Sharing schemes allow a dealer to distribute $n$ shares $s_1,\ldots, s_n$ of a secret $s$ so that any $t$ shares suffice to reconstruct the secret, while any $t-1$ shares reveal no information about $s$. In fact, schemes such as Shamir Secret Sharing satisfy a stronger guarantee called $(t\!-\!1)$-perfect privacy, meaning that for any subset $S \subseteq [n]$ with $|S| \le t-1$, the joint distribution $(s_i)_{i \in S}$ is uniformly distributed over its domain. This strong guarantee is essential for applications such as fuzzy password-authenticated key exchange (fPAKE) and conditional encryption --- a recent cryptographic primitive introduced to enable secure personalized password typo correction. Unfortunately, Shamir secret sharing is not robust: corrupted shares can prevent correct reconstruction or cause reconstruction of an incorrect secret. Existing robust secret sharing schemes address this issue but necessarily sacrifice perfect privacy. We introduce and construct Random Robust Secret Sharing with Perfect Privacy (RRSS), a new notion that preserves $(t\!-\!1)$-perfect privacy while providing robustness against random share corruptions. In our schemes, the secret is recovered with high probability even if an arbitrary subset of up to $n-t$ shares is independently corrupted at random. We demonstrate the utility of RRSS through two applications. First, we present the first practically efficient fPAKE construction that tolerates Hamming errors. Second, we obtain the first efficient conditional encryption scheme for arbitrary Hamming distances, improving upon prior work that achieved efficiency only for constant distances. We implement both constructions and empirically demonstrate their practicality.
## 2026/978
* Title: Verifying Consensus Protocols from LLM-assisted TLA$^+$: A Case Study of Byzantine Reliable Broadcast
* Authors: Shuhe Cao, Xin Wang, Chenxu Wang, Xiao Sui, Sisi Duan
* [Permalink](https://eprint.iacr.org/2026/978)
* [Download](https://eprint.iacr.org/2026/978.pdf)
### Abstract
TLA$^+$ (Temporal Logic of Actions) is a formal specification language well-suited for distributed systems. However, writing proper TLA$^+$ scripts requires high domain expertise. When it comes to modeling Byzantine behaviors for Byzantine fault-tolerant consensus protocols, the simulation of malicious behavior is a fundamental challenge: overly simplified modeling misses critical vulnerabilities, and verbose modeling leads to state-space explosion.
In this paper, we present TLAssist, a large language model (LLM)-assisted tool for semi-automated TLA$^+$ generation tailored for Byzantine reliable broadcast (RBC) protocols. We provide a highly structured workflow and domain-specific data format to improve the quality of LLM prompts. Using five RBC protocols as case studies, we have some interesting findings. First, the specification generated by TLAssist outperforms many open-source TLA$^+$ scripts we are aware of, including those written by domain experts. Second, TLAssist can assist domain experts in identifying deep design flaws. Notably, our case study on the (2,3,4)-Optimistic RBC (a CCS'25 distinguished paper) captures a subtle issue that causes the violation of the totality property. Finally, TLAssist is useful for non-experts. Namely, we show that by revising the protocols slightly, the generated error traces effectively show complex corner cases that can facilitate understanding of the design.
## 2026/1037
* Title: On Publicly Verifiable Tokens in Group Signatures with Message-Dependent Opening
* Authors: Takuma Watanabe, Keita Emura
* [Permalink](https://eprint.iacr.org/2026/1037)
* [Download](https://eprint.iacr.org/2026/1037.pdf)
### Abstract
Group signatures (GSs; Chaum and van Heyst, EUROCRYPT 1991) are digital signatures that allow a signer to anonymously prove group membership, while still enabling a special authority, called the opener, to identify the signer when necessary. Group Signatures with Message-Dependent Opening (GS-MDO; Sakai et al., Pairing 2012) weaken the power of the opener by introducing another authority, the admitter, who issues a message-dependent token. In previous GS-MDO schemes, these tokens can be viewed as signatures. Therefore they can be publicly verified using the verification algorithm of the underlying signature scheme. However, no explicit notion of public verifiability for tokens, meaning the ability to publicly verify whether a token can be used for opening a group signature, has been defined so far. Clarifying this implicit security property is important for understanding the feasibility of GS-MDO. In this paper, we formally define public verifiability of tokens. We establish a proper relationship between verifying a token as a signature and verifying that the token can be used for opening, which typically requires the opener's secret key. We also show that the Ohara et al. pairing-based GS-MDO scheme (AsiaCCS 2013), the Libert et al. lattice-based GS-MDO scheme (ACNS 2016), and the Libert et al. pairing-based GS-MDO scheme (CT-RSA 2014) satisfy our definition, suggesting that our formalization is reasonable. Finally, we discuss how publicly verifiable tokens can be used to provide accountability for the admitter, enabling them to demonstrate that tokens have been honestly generated according to the token-generation algorithm.
## 2026/1047
* Title: Round-Optimal Subversion-Resilient UC PAKE from Malleable Trapdoor Smooth Projective Hash Functions
* Authors: Behzad Abdolmaleki, Suvradip Chakraborty, Shahram Khazaei, Lorenzo Magliocco, Nahid Roustaeifar, Behzad Vahdani, Daniele Venturi
* [Permalink](https://eprint.iacr.org/2026/1047)
* [Download](https://eprint.iacr.org/2026/1047.pdf)
### Abstract
Password-Authenticated Key Exchange (PAKE) allows two parties to establish a common high-entropy secret from a possibly low-entropy pre-shared secret such as a password. In this paper, we revisit the question of constructing PAKE protocols with subversion resilience in the framework of universal composability (UC), where the latter roughly means that UC security still holds even if one of the two parties is malicious and the honest party's code has been subverted (in an undetectable manner). The latter goal was recently achieved by Chakraborty, Magliocco, Magri and Venturi (ASIACRYPT 2024), based on sanitation of oblivious transfer protocols and dual-mode cryptosystems via cryptographic reverse firewalls (Mironov and Stephens-Davidowitz, EUROCRYPT 2015). Our contributions are as follows:
- We introduce so-called malleable trapdoor smooth projective hash functions (M-TSPHF), as an enhancement of trapdoor smooth projective hash functions (Benhamouda et al., CRYPTO 2013). Our extension incorporates new properties including key malleability and element rerandomizability.
- We give a generic construction of subversion-resilient UC PAKE based on M-TSPHF and other standard cryptographic primitives. As we demonstrate, our PAKE protocol can be instantiated efficiently yielding an improved round and communication complexity with respect to the previous protocol of Chakraborty et al. In particular, our PAKE protocol achieves round optimality, as it concludes in a single round.
## 2026/1157
* Title: A Simple and Unified Approach for Proving Knowledge of Isogenies between Abelian Varieties
* Authors: Jonathan Komada Eriksen, Riccardo Invernizzi, Jannik Spiessens, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2026/1157)
* [Download](https://eprint.iacr.org/2026/1157.pdf)
### Abstract
In this paper we introduce a simple and unified approach, based on generic proof systems, to prove knowledge of any isogeny between two principally polarized abelian varieties in any dimension, assuming that the $2^m$-torsion is accessible for sufficiently large $m$. Previous generic proof approaches were only able to prove knowledge of a smooth degree isogeny between elliptic curves, where for each small prime factor $\ell$ of the degree, bespoke constraints had to be derived, typically from (a variant of) the $\ell$-th modular polynomial.

Our approach is much simpler in that it relies on proving knowledge of a $2^n$-isogeny between two principally polarized abelian varieties in any dimension. Furthermore, our approach is unified in that the constraints are essentially the same for each dimension, resulting in a simpler and easier-to-optimize algorithm. Our construction has immediate applications to proving knowledge of an isogeny of any degree between two elliptic curves, by using a higher dimensional representation. Indeed, by a result of Robert, any isogeny can be embedded in a $2^n$-isogeny by increasing the dimension, and conversely, the knowledge of a $2^n$-isogeny between products of varieties implies the knowledge of an isogeny of degree $\leq 2^n$ between a factor of the domain and codomain. Our generic proof does not disclose the degree of the secret isogeny, nor does it rely on knowing the endomorphism ring, thereby solving an open problem posed by Beullens, De Feo, Galbraith, and Petit in 2023.

Two use cases are immediate. First, if one wants to prove knowledge of any isogeny between two supersingular curves over $\mathbb{F}_{p^2}$, e.g. during the generation of an elliptic curve with unknown endomorphism ring. Second, to prove knowledge of a secret isogeny coming from the class group action on oriented supersingular elliptic curves, e.g. CSIDH with curves defined over $\mathbb{F}_p$. Computing such group actions is typically done using qt-Pegasis, which naturally results in a 4-dimensional representation of the isogeny.

Lastly, we propose two tailored zero-knowledge proof systems that improve proving time and proof size without loss of generality and provide the first implementation in dimension 2 and 4 by implementing both proof systems in Rust.
## 2026/1780
* Title: The Limits of $t$-Private Share Conversion
* Authors: Bar Alon
* [Permalink](https://eprint.iacr.org/2026/1780)
* [Download](https://eprint.iacr.org/2026/1780.pdf)
### Abstract
Private information retrieval (PIR) protocols allow a user to retrieve an entry from a database held by several servers without revealing any information about the index to any individual server. State-of-the-art information-theoretic PIR protocols are based on a combination of matching vectors over the ring $\mathbb{Z}_m$ and decoding polynomials (Efremenko, SICOMP 2012; Dvir and Gopi, STOC 2015; Ghasemi, Kopparty, and Sudan, STOC 2025). Decoding polynomials are sparse polynomials over a field $\mathbb{F}_q$, where $q$ is a prime power coprime to $m$, that evaluate to a nonzero value at $1$ and to $0$ on a certain set of inputs determined by $m$.
The properties of decoding polynomials were abstracted by Beimel, Ishai, Kushilevitz, and Orlov (CCC 2012) through the notion of share conversions. Share conversions allow a set of parties to locally convert a secret shared under one scheme into a related secret shared under another scheme. They constructed a share conversion from $\mathbb{Z}_m$ to $\mathbb{F}_{q}$ for various values of $m$ and prime-powers $q$. More recent PIR protocols by Dvir and Gopi and by Ghasemi et al. were abstracted by Alon, Beimel, and Lasri (TCC 2025). The share conversion they considered transforms shares from the ring $\mathbb{Z}_m$ to a finite field $\mathbb{F}_q$, where $q$ is a prime-power coprime to $m$.
We observe that if the initial conversion is based on a $t$-private secret-sharing scheme, then the resulting PIR protocol of Alon et al. is also $t$-private: no set of $t$ servers learns any information about the user's index. We call such share conversions $t$-private share conversions. Moreover, the resulting PIR protocol could potentially achieve communication complexity better than that of the best-known $t$-private PIR protocols, due to Woodruff and Yekhanin (CCC 2005) and Barkol, Ishai, and Weinreb (APPROX-RANDOM 2007). This raises the natural question of whether $t$-private share conversions exist.
We show that there is no $t$-private share conversion from $\mathbb{Z}_m$ to $\mathbb{F}_q$ when $t\geq 2$ and $q$ is coprime to $m$. As a result, the PIR framework of Alon et al. cannot be instantiated in a way that yields a $t$-private PIR protocol. We further generalize the result to conversions whose output is in the ring $\mathbb{Z}_{m'}$.
## 2026/1895
* Title: Large-Universe (Multi-Authority) ABE from LWE
* Authors: Pratish Datta, Yannis Rouselakis, Junichi Tomida, Nikhil Vanjani
* [Permalink](https://eprint.iacr.org/2026/1895)
* [Download](https://eprint.iacr.org/2026/1895.pdf)
### Abstract
An attribute-based encryption (ABE) scheme is "large-universe" if its attribute universe is superpolynomial and is not enumerated during setup. In the multi-authority setting, we further require that each authority can independently manage a superpolynomial set of attributes and dynamically issue an arbitrary polynomial number of secret keys per user. Although large-universe (multi-authority) ABE from pairings is well studied, explicit lattice-based constructions have remained elusive. In the centralized setting, a standard workaround is to instantiate lattice-based ABE for general circuits and encode each attribute as a bit string; however, unless one adopts non-standard lattice assumptions, this approach typically yields prohibitively large ciphertexts. In the multi-authority setting, even though lattice-based ABE for general circuits is known, this bit-encoding approach applied to those schemes does not yield a genuine large-universe construction. We close this gap by presenting the first lattice-based large-universe (multi-authority) ABE schemes under the Learning With Errors (LWE) assumption, achieving ciphertext and key sizes that are comparable to those in the pairing-based setting. Concretely, we construct:
rCo a large-universe key-policy ABE scheme with ciphertext size $O(t)$;
rCo a large-universe ciphertext-policy ABE scheme with ciphertext size $O(|f|)$; and
rCo a large-universe multi-authority ABE scheme,
where $t$ is the number of attributes, $|f|$ is the policy size, and the $O(\cdot)$ notation suppresses $\tilde{O}(\lambda)$ factors. All schemes support policies in disjunctive normal form (DNF) and are proved secure in the random oracle model. We further develop more efficient variants of our key-policy and ciphertext-policy ABE schemes over ideal lattices under the Ring-LWE assumption, aiming for practical performance on the order of seconds to minutes. Experimental results from our implementations confirm practical runtimes and memory consumption, providing concrete evidence that large-universe lattice-based ABE is feasible for efficient real-world deployment.
## 2026/1904
* Title: When Module Lattice Leaks: Horizontal Fusion Attacks on ML-DSA Implementation
* Authors: Yuhan Zhao, Dalin He, Wei Cheng, Yuejun Liu, Jingdian Ming, Yongbin Zhou
* [Permalink](https://eprint.iacr.org/2026/1904)
* [Download](https://eprint.iacr.org/2026/1904.pdf)
### Abstract
The standardization of ML-DSA has shifted the cryptographic community's focus toward its practical security. While profiled attacks against its implementations are well studied with a few traces, non-profiling attacks are widely assumed to require large trace complexity. We challenge this by introducing horizontal fusion attacks, demonstrating that non-profiling, few-trace key recovery is highly practical against ML-DSA, even against masked implementations.
We expose a structural vulnerability in the module lattice from a side-channel perspective. In particular, in ML-DSA's matrix-vector multiplication ($\hat{\mathbf{A}} \circ \hat{\mathbf{y}}$), the row-wise reuse of the ephemeral secret vector $\hat{\mathbf{y}}$ indicates that one single signature generation exposes $k$ (the row-wise size of $\hat{\mathbf{A}}$) leakage instances of the same secret-dependent intermediate value, each with a distinct and known coefficient of $\hat{\mathbf{A}}$. However, exploiting this in practice is highly non-trivial due to noise and/or compiler optimizations. To overcome this, we propose a variance-based weighted fusion strategy. This approach weights each operation by how far its leading candidate is separated from the runner-up candidates, and the signing relation ($\mathbf{y} = \mathbf{z} - c \cdot \mathbf{s}_1$) lets us extract the signed coefficients of the secret key. Moreover, we introduce a fast, INTT-based algebraic sieve that further increases the success rate of key recovery.
Putting together, we achieve full key recovery using merely 4 traces against ML-DSA-87 (the highest security parameter set) with non-profiling correlation analysis. On the state-of-the-art first-order masked ML-DSA implementation, our attack extracts the secret key using no more than 90 traces. To the best of our knowledge, these non-profiling results establish a new record in trace complexity for both unprotected and first-order masked ML-DSA implementations, even comparable to these profiling-based attacks.
## 2026/1908
* Title: A Generalized Wiener-type Attack Against a Family RSA-like Cryptosystems
* Authors: George Teseleanu
* [Permalink](https://eprint.iacr.org/2026/1908)
* [Download](https://eprint.iacr.org/2026/1908.pdf)
### Abstract
Let $N = pq$ be the product of two balanced prime numbers $p$ and $q$. In 2023, Cotan and Te\c seleanu introduced a family of RSA-like cryptosystems based on the key equation $ed - k(p^n - 1)(q^n - 1) = 1$, where $n \geq 1$. Note that when $n = 1$, we obtain the classical RSA scheme, while $n = 2$ yields the variant proposed by Elkamchouchi, Elshenawy, and Shaban. In this paper, we present a novel attack that combines continued fractions with lattice-based methods for the case $n = 2^i$, where $i > 2$ is an integer. This represents a natural continuation of previous research, which successfully applied similar techniques for $n = 1, 2, 4$.
## 2026/1914
* Title: AIPA: Anonymous Image Provenance Authentication in Online Social Networks via Unlinkable Pseudonym Certificates and zk-SNARKs
* Authors: Linsheng Yu, Yanqing Yao
* [Permalink](https://eprint.iacr.org/2026/1914)
* [Download](https://eprint.iacr.org/2026/1914.pdf)
### Abstract
Generative AI has made high-fidelity deepfakes easy to produce, and online social networks (OSNs) spread them widely across users and platforms. Publicly verifying an image's provenance, i.e., where an image came from and what edits it has undergone, can help combat deepfakes. The Coalition for Content Provenance and Authenticity (C2PA) offers an industry standard, but depends on trusted software and hardware. Through digital signatures and zero-knowledge proofs, cryptographic image authentication eliminates the reliance on trusted editors. However, deploying such schemes in OSNs faces three problems: preserving signer privacy, maintaining provenance authenticity across edits, and ensuring efficient verification. To ensure signer anonymity in image provenance, we propose an unlinkable pseudonym certificate scheme (UPCS) based on anonymous credentials, which reduces online signing and verification to ordinary digital signature operations taking only 0.017 and 0.066 ms. Building on UPCS, zk-SNARKs, and hash chains, we propose an anonymous image provenance authentication (AIPA) scheme, ensuring the authenticity of provenance and editing history of an image as it propagates across mutually untrusted editors, while preserving signer privacy. To achieve efficient verification in OSNs, we introduce VIMz-Loua, a GPU-accelerated image proof system with a dedicated JPEG-compression circuit, whose proofs remain a constant 448 B and verify in 6-12 ms across image sizes. We formally prove the security of UPCS and AIPA, and implement an end-to-end workflow in a simulated OSN environment, where the full multi-edit provenance lineage is only 40.2 KB (6.5% of the published image), and is verified in 4.28 s.
## 2026/1915
* Title: A RAM-Efficient Implementation of Falcon
* Authors: Thomas Pornin
* [Permalink](https://eprint.iacr.org/2026/1915)
* [Download](https://eprint.iacr.org/2026/1915.pdf)
### Abstract
We present a RAM-efficient implementation of Falcon: RAM usage has shrunk to about 11 kB, down from about 31 kB in the previous implementation of Falcon-512. This code is furthermore faster on Arm Cortex M4, with average signature generation cost down to 13.45 million cycles. Optimization techniques include a novel variant of the FFT, replacement of some floating-point operations with modular integer computations, delayed addition of input within the Fast Fourier sampling process, and an alternate signature reassembly process. More than half of the floating-point operations have been removed. The resulting implementation is now small enough to allow use in small embedded systems such as smart cards.
## 2026/1956
* Title: PRISM: Efficient zkSNARKs for RNS-Based Homomorphic Encryption
* Authors: Zhelei Zhou, Yun Li, Zhaomin Yang, Cheng Hong, Tao Wei
* [Permalink](https://eprint.iacr.org/2026/1956)
* [Download](https://eprint.iacr.org/2026/1956.pdf)
### Abstract
Homomorphic Encryption (HE) enables computations on encrypted data without decryption, but it does not guarantee the integrity or correctness of the performed operations. To address this limitation, verifiable HE (vHE) has been proposed. However, achieving efficient vHE for RNS-based HE schemes (e.g., BFV/BGV/CKKS) remains challenging: While the Residue Number System (RNS) boosts performance of HE via multi-modulus ciphertext representations, it significantly complicates the cross-field consistency checks in vHE. We observe that existing vHEs for RNS-based HE suffer from at least one of the following limitations: they do not readily extend to the zero-knowledge setting (Atapoor et al., CiC 2024), incur linear proof size & verifier cost (Zhou et al., S&P 2025), or are designed for a modified HE scheme (Cascudo et al., Crypto 2025).
We present $\mathsf{PRISM}$, the first practical zkSNARK for standard RNS-based HEs. Our techniques are threefold: (1) a new cryptographic primitive called Multiple-Field Polynomial Commitment Scheme (MF-PCS) that efficiently prove the cross-field modulo relations, which is the key bottleneck in RNS-based HE verification; (2) a novel Polynomial Interactive Oracle Proof (PIOP) for (inverse) number theoretic transforms with $O(N)$ prover time and $O(\log N)$ verifier time in a model with an offline phase; (3) upgrading MF-PCS and PIOPs to achieve zero-knowledge with small overhead via Vector Oblivious Linear Evaluation (VOLE) correlations. We fully implemented $\mathsf{PRISM}$ and evaluated it against state-of-the-art schemes. Compared to Zhou et al. which has the fastest prover time, $\mathsf{PRISM}$ has $3.5\times$ slower prover time, but up to $7.8\times$ faster verifier time and $7.8\times$ smaller proof size. Compared to Atapoor et al. which has the smallest proof size, $\mathsf{PRISM}$ has $5.5\times$ larger proof size, but roughly $10.1\times$ faster prover time and $2.6\times$ faster verifier time.
## 2026/1957
* Title: More Efficient Secret-Shared Joins with Multiplicity via Oblivious Sort Expansion
* Authors: Xiaoxin Du, Xiaojie Guo, Pinzhi Chen, Tong Li, Zheli Liu
* [Permalink](https://eprint.iacr.org/2026/1957)
* [Download](https://eprint.iacr.org/2026/1957.pdf)
### Abstract
Secret-shared SQL-style join is a fundamental building block in secure collaborative data analysis. In practice, join operations frequently involve duplicate keys, giving rise to one-to-many (Join-OM) and many-to-many (Join-MM) relationships. Supporting such joins requires obliviously materializing all matching row pairs. Existing protocols achieve this in two costly ways: they either perform oblivious sorting over a larger expanded input or rely on multiple aggregation trees that incur additional logarithmic rounds.
In this work, we present highly efficient protocols for Join-OM and Join-MM over secret-shared databases in the standard semi-honest setting. Our core contribution is Oblivious Sort Expansion (OSE), a novel constant-round protocol that may be of independent interest. Rather than obliviously sorting the expanded input from scratch, we sort only the original input and use OSE to derive the sorted order after expansion. For Join-OM, OSE eliminates the redundant sorting overhead introduced by input expansion in the state-of-the-art protocol by Asharov et al. (CCS 2023). For Join-MM, we combine OSE with local linear operations to obtain an aggregation-tree-free Join-MM protocol. Experimental results show that our protocols consistently outperform prior protocols, reducing both runtime and communication costs by approximately $27\%$ and $65\%$ for Join-OM and Join-MM, respectively.
## 2026/1958
* Title: Arithmetic for Large-Characteristic Finite Fields in CKKS
* Authors: Daehyun Jang, Junho Lee
* [Permalink](https://eprint.iacr.org/2026/1958)
* [Download](https://eprint.iacr.org/2026/1958.pdf)
### Abstract
Seur\'e and Suvanto (ePrint 2026/1102) recently showed that, for small-characteristic primes $p$, arithmetic over $\mathbb{F}_{p^r}$ can be homomorphically evaluated in CKKS via a techniquethey call \emph{spectral encoding}. Their construction is, however, restricted to small characteristic: ciphertext multiplication amplifies the error by the operator norm of the multiplied plaintext.
Under the spectral encoding, a field element in $\mathbb F_{p^r}$ is encoded to a plaintext with operator norm at most $O(rp)$. The error
therefore grows by a factor of $rp$ in the worst case, limiting the supported size of the characteristic prime $p$.
In this work, we propose \emph{bi-spectral encoding}, which decomposes the coefficients of the plaintext polynomials used in the spectral encoding of Seur\'e and Suvanto. With a decomposition parameter $d$, a field element in $\mathbb F_{p^r}$ can be encoded to a plaintext with operator norm $O(rd{p^{1/d}})$, for a suitable choice of encoding parameters. We give a comprehensive analysis of error growth and derive a bound on error amplification under multiplication.
For fields with a 256-bit prime characteristic (secp256k1) and extension degrees $1$, $2$, and $4$, we provide numerical simulations of error amplification and compute the maximum multiplication counts attainable in each case.
We further present a bootstrapping procedure that reduces both the size of the plaintext and its noise.
## 2026/1959
* Title: Information-theoretic two-server PIR requires $(6-o(1))\log n$ bits of communication
* Authors: Keewoo Lee
* [Permalink](https://eprint.iacr.org/2026/1959)
* [Download](https://eprint.iacr.org/2026/1959.pdf)
### Abstract
We prove that every information-theoretic two-server private information retrieval scheme for $n$-bit databases requires $(6-o(1))\log n$ bits of communication. This improves on the $5$ of Wehner and de Wolf (ICALP 2005), who had raised the $4.4$ of Kerenidis and de Wolf (STOC 2003), who in turn had raised Mann's original $4$ (M.Sc.\ thesis, 1998). Our proof follows the quantum route of the earlier bounds: encode the database in a quantum state, recover an entry from enough copies of it, and apply Nayak's bound (FOCS 1999) on quantum random access codes. Previous proofs read that entry as a binary outcome with a small bias toward the correct answer, and pay the inverse square of that bias to amplify it. We instead allow a real-valued outcome whose mean is the correct answer, and pay only its second moment. The same readout strategy improves the other lower bounds of Wehner and de Wolf, for smooth codes and locally decodable codes. In particular, it drops the linearity assumption in the lower bounds of Goldreich, Karloff, Schulman, and Trevisan (CCC 2002) almost for free.
## 2026/1960
* Title: Unbounded Broadcast and KP-ABE with Sublinear Ciphertext from Pairings * Authors: Junichi Tomida, Hoeteck Wee
* [Permalink](https://eprint.iacr.org/2026/1960)
* [Download](https://eprint.iacr.org/2026/1960.pdf)
### Abstract
We present the first pairing-based unbounded broadcast encryption
and key-policy attribute-based encryption (KP-ABE) with sublinear
ciphertext size. Here, unbounded means set-up and the public
parameters do not impose a bound on the size of the broadcast set,
attribute length, or policy size.
- Our broadcast encryption scheme supports an unbounded number of users, and achieves
\[ |mpk| = O(1), |ct| = O(\sqrt{N}), |sk| = O(\sqrt{N})\]
where $N$ denotes an upper bound on the size of the broadcast set.
- Our KP-ABE supports boolean formula and span programs, and achieves
\[ |mpk| = O(1), |ct| = O(\sqrt{N}), |sk| = O(\sqrt{N} \cdot |f|)\]
where $N$ is the attribute length and $|f|$ the policy size.
We prove adaptive security for the broadcast encryption and
selective security for the KP-ABE,
based on the $k$-Lin assumption in the standard model without random
oracles.
## 2026/1961
* Title: A Formal Security Analysis of a MACsec Key Agreement Protocol Using Tamarin
* Authors: Halil -#brahim Kaplan
* [Permalink](https://eprint.iacr.org/2026/1961)
* [Download](https://eprint.iacr.org/2026/1961.pdf)
### Abstract
MACsec Key Agreement (MKA) is the IEEE 802.1X key-management protocol used to establish and maintain Secure Associations for MACsec deployments. Although MKA is widely deployed, machine-checked analyses of its core key-agreement logic remain scarce. This paper presents a formal analysis of a simplified two-party MKA exchange using the Tamarin prover. We model the initial session establishment and a subsequent rekey round, and verify secrecy, authentication, agreement, ordering, and freshness properties. The analysis confirms these guarantees under a Dolev--Yao adversary when the pre-shared Connectivity Association Key (CAK) is not compromised. We also identify a structural weakness: a malicious or compromised Key Server can inject an arbitrary Secure Association Key (SAK) that the Server accepts. This finding clarifies the trust assumptions of MKA and motivates additional verification or binding mechanisms for partially trusted deployments.
## 2026/1962
* Title: Compare Before Clearing: Exact Integral-Comparison Frontiers for Lattice Extraction
* Authors: Xiang Wang, Shihui Fu
* [Permalink](https://eprint.iacr.org/2026/1962)
* [Download](https://eprint.iacr.org/2026/1962.pdf)
### Abstract
Lattice extraction often produces openings normalized by challenge differences, whereas an inconsistency must ultimately yield a short integral SIS relation. Clearing each extracted branch before comparison removes every denominator obstruction carried by that branch, including factors irrelevant to the mismatch that is eventually tested.
We formalize direct integral comparison for generic polynomial block systems. If block \(a\) has width \(r_a\) and the two extraction centers differ on \(J\), the minimum worst-case coefficient degree is \(\max\{\max_a r_a,\sum_{a\in J} r_a\}\). Within a branch-separated polynomial integralize-then-compare architecture, it is \(2\sum_a r_a\). The coordinate case gives \(\max\{1,h\}\) and \(2L\), where \(h=|J|\).
Exact conditional resampling obtains the required partially synchronized successful executions without a reciprocal-success loss. The coordinate schedule uses at most \(2L+1\) additional retry invocations in unconditional expectation.
Two cases illustrate the bounds. For Cyclo-style coordinate folding, one unsynchronized coordinate has the same certified radius as same-root synchronization. For two independently extracted Esgin-style Vandermonde stars, direct comparison has degree \(\binom{k+1}{2}\) in the anchor-universal polynomial-linear model. The degree is \(k^2\) within the stated branch-separated integralize-then-compare architecture.
## 2026/1963
* Title: Impossible Polytopic Attack Revisited: Low-Data Distinguishers and Attacks
* Authors: Yongqiang Li
* [Permalink](https://eprint.iacr.org/2026/1963)
* [Download](https://eprint.iacr.org/2026/1963.pdf)
### Abstract
Block ciphers including several variants of the well-known \textsf{AES}, the newly proposed tweakable block cipher \textsf{Deoxys-BC} (standardized by ISO/IEC and renamed Deoxys-TBC), and \textsf{ChiLow} (EUROCRYPT 2025) adopt key sizes larger than their block sizes. These designs offer security higher than the block size. This paper evaluates the security of such ciphers by revisiting the Impossible Polytopic Attack (\ipa{}, proposed by Tyge Tiessen at EUROCRYPT 2016). We show that \ipa{} can build longer-round distinguishers, enabling attacks on more rounds. Moreover, the attack is applicable under the known-plaintext (KP) setting. Towards this end, we first formalize the distinguisher from TiessenrCOs original work and establish a generic framework for distinguisher construction. We further propose two novel methods to lower the corresponding construction complexity. Moreover, we develop two dedicated key-recovery techniques, namely the plaintextrCagrouping technique and the partition-guess-filter technique. The former allows cryptanalysis on more rounds of target ciphers, while the latter substantially lowers the overall attack complexity. Finally, we build the first framework for \ipa{}. We apply our method to the chosen-plaintext/ciphertext (CP/CC) and KP scenarios under the single-key setting. As a result, we obtain new distinguishers and attacks against \textsf{AES}, \textsf{Deoxys-BC}, \textsf{Joltik-BC}, \textsf{LED-128}, and \textsf{ChiLow-32}. Notably, 10-round attacks are constructed on \textsf{Deoxys-BC-384} and \textsf{Joltik-BC-192}. Compared with impossible differential attacks, which are closely related and extensively studied, the proposed results outperform such attacks by one round. Furthermore, a novel full-round attack on \textsf{ChiLow-32} is constructed under the KP setting, achieving the state-of-the-art attack with optimal data complexity and overall complexity.
## 2026/1964
* Title: Three-Round Weak Non-Malleable Zero-Knowledge Argument
* Authors: Xinxuan Zhang, Yuanju Wei, Zhichao Wang, Zhongliang Zhang, Ming Yang, Ruida Wang, Yi Deng, Hailong Wang
* [Permalink](https://eprint.iacr.org/2026/1964)
* [Download](https://eprint.iacr.org/2026/1964.pdf)
### Abstract
Non-malleable zero-knowledge argument(NMZK) is a strong notion of zero-knowledge argument that ensures security against man-in-the-middle(MIM) attacks. While three-round constructions exist for various weak zero-knowledge arguments under standard assumptions, all known (weak) NMZK protocols in the plain model have required at least four rounds.
In this work, we construct the \emph{first three-round weak non-malleable zero-knowledge argument} under standard cryptographic assumptions. Our protocol satisfies weak zero-knowledge and $\epsilon$-non-malleability, where the latter allows an $\epsilon$ probability gap between the MIM experiment and the stand-alone experiment for any polynomial inverse $\epsilon$. Our construction relies only on well-established primitives, such as the existence of two-message oblivious transfer protocols and delayed-input WI arguments, non-interactive commitments, and circuit-privacy fully homomorphic encryptions.
## 2026/1965
* Title: Lattice-based Threshold Traitor Tracing with Public Traceability
* Authors: S|-bastien Canard, Nathan Papon, Duong Hieu Phan
* [Permalink](https://eprint.iacr.org/2026/1965)
* [Download](https://eprint.iacr.org/2026/1965.pdf)
### Abstract
Since the introduction of Threshold Traitor Tracing by Boneh, Partap and Rotem at CRYPTO '24, several works have extended the functionalities within the framework or improved the parameters. However, most of the existing solution fall short in providing post quantum security guarantees. The only lattice-based construction, due to Das et al. from EUROCRYPT '26, achieves post-quantum security but is limited to private tracing: a dedicated tracing authority holds a secret tracing key. In a threshold system, where the fundamental goal is to distribute trust, such a single point of failure is undesirable.

In this work, we construct the first threshold traitor tracing scheme that simultaneously achieves post-quantum security and public traceability, where anyone can trace a pirate decoder without any secret tracing key.
Our core building block is a Q-Partite Threshold Public Key Encryption (QTPKE) scheme, which is known to imply threshold traitor tracing when combined with a robust IPP code: we build QTPKE from plain Learning With Errors (LWE) using a key-shifting mechanism on top of Regev's encryption scheme thresholdised via {0,1}-Linear Secret Sharing. We finally prove the security of our scheme in the standard model under standard lattice assumptions.
## 2026/1966
* Title: Design and Analysis of Isogeny-Based Strong Designated Verifier Signature
* Authors: Abhinav Sharma, Vikas Srivastava
* [Permalink](https://eprint.iacr.org/2026/1966)
* [Download](https://eprint.iacr.org/2026/1966.pdf)
### Abstract
Strong designated-verifier signatures provide authentication while restricting verification to a chosen verifier and protecting the signer from transferable evidence. Designing such signatures in the post-quantum setting is challenging because authentication, signer privacy, simulation, and efficiency must be achieved simultaneously. Recently, Renan proposed CSI-SDVS, a compact post-quantum strong designated-verifier signature scheme built from CSIDH-style commutative isogeny class-group actions. We show that its response design, $z_i=b_i-s_i$, breaks privacy of the signer's identity: because the PSI experiment reveals both candidate signer secret keys, an adversary can reconstruct the signing randomness and identify the actual signer with overwhelming probability. We validate the attack over 30,000 executions, obtaining 100\% signer identification in the main 128-bit experiment and for $\eta\in \{1,2,4,8\}$. In the following, we propose an isogeny-based strong designated verifier signature. We prove correctness, non-transferability, signer privacy, and strong unforgeability under Gap Parallelization in the random-oracle model. For $\eta=1$, the redesigned signature is 113 bytes compared with 49 bytes in CSI-SDVS, while signer key sizes remain unchanged.
## 2026/1967
* Title: Azkaban: A Zero-Knowledge Abstract Analysis for Neural Networks
* Authors: Sankha Das, Lucien L. K. Ng, Yibin Yang, Vladimir Kolesnikov, Teodora Baluta
* [Permalink](https://eprint.iacr.org/2026/1967)
* [Download](https://eprint.iacr.org/2026/1967.pdf)
### Abstract
Deep neural networks (DNNs) are increasingly used in sensitive applications, where certifying properties such as adversarial robustness and fairness is crucial. Several recent works propose DNN certification systems using zero-knowledge proofs (ZKPs)rCo cryptographic primitives that allow verifying certificates while maintaining confidentiality of the model. While certification algorithms typically treat the DNN as a function over reals, naively translating these algorithms into finite-precision implementations can result in unsound certification due to rounding errors. In ZKPs, this unsoundness is amplified due to a larger precision loss from fixed-point arithmetic emulated using finite fields. In this work, we highlight an overlooked gap in the soundness of prior protocols. We propose AZKABAN, a system for zero-knowledge abstract interpretation-based analysis with end-to-end soundness. We introduce operators for sound interval analysis over finite-fields, including efficient ZKP-amenable algorithms for inner-products and division, while preventing privacy leaks due to non-linear activations. We implement our system which is comprehensive in terms of supporting both feed-forward and convolutional neural networks. AZKABAN improves over the state-of-the-art ZK individual fairness certification protocol by up to two orders of magnitude in end-to-end proof time. Further, it scales to much larger models than those considered in the state-of-the-art. AZKABAN also provides, to our knowledge, the first solution for ZK robustness certification.
## 2026/1968
* Title: The Closest-Vector Problem over Cyclotomics and its Application to Homomorphic Encryption
* Authors: Natalie Lang, Dana Dachman-Soled
* [Permalink](https://eprint.iacr.org/2026/1968)
* [Download](https://eprint.iacr.org/2026/1968.pdf)
### Abstract
We study rounding error in the Closest-Vector Problem (CVP) over cyclotomic lattices of arbitrary order \(m\), motivated by its role in approximate homomorphic encryption (HE), where lattice-based rounding directly affects the noise and precision of key operations. For the worst-case analysis, we derive a new covering-radius upper bound. For the average-case analysis, we study the efficient approximate solution given by BabairCOs nearest-plane algorithm, whose error upper bounds that of exact nearest-point rounding. For an arbitrary lattice and a target sampled uniformly from a fundamental domain, we show that BabairCOs error has independent uniform coordinates in the GramrCoSchmidt basis. This determines its mean-squared error (MSE); for cyclotomic lattices, we further show that the squared error concentrates around its mean.
Using the tensor decomposition of cyclotomics, we express our bounds in terms of the prime-power decomposition of \(m\), revealing provably improved rounding for non-power-of-two cyclotomics over their power-of-two counterparts while retaining efficient arithmetic for broad families of indices. We apply these results to approximate HE, where improved rounding-error bounds inform the choice of encryption parameters. Our concrete evaluation yields parameter choices with simultaneously smaller lattice dimension and ciphertext modulus at fixed output precision and target security level, illustrating the potential of non-power-of-two cyclotomic rings for approximate HE.
## 2026/1969
* Title: Efficient Polynomial System Solving via Dixon Resultants: Applications to AO Primitives
* Authors: Haohai Suo, Jiamin Cui
* [Permalink](https://eprint.iacr.org/2026/1969)
* [Download](https://eprint.iacr.org/2026/1969.pdf)
### Abstract
Solving multivariate polynomial systems is a fundamental problem in cryptanalysis, with increasing relevance in algebraic attacks on arithmetization-oriented (AO) primitives. Current approaches primarily rely on Gr||bner bases or the Sylvester resultant. However, Gr||bner basis methods typically rely on FGLM to change the monomial order, which applies only to zero-dimensional ideals, whereas the Sylvester resultant eliminates only one variable at a time, limiting its flexibility in multivariate elimination.
We revisit the Dixon resultant as an efficient and flexible tool for eliminating several variables simultaneously. We derive refined upper bounds on the Dixon matrix size via lattice-path counting and analyze the complexity under several determinant computation models, yielding explicit complexity estimates. For well-determined systems, the Dixon resultant is a viable alternative to Gr||bner basis methods; moreover, it is attractive for elimination in underdetermined systems, whereas Gr||bner basis methods remain preferable for overdetermined ones.
We present an efficient open-source C implementation, DRSolve, with multiple determinant methods and a degree-aware submatrix selection strategy to mitigate the impact of extraneous factors. Experiments show that our implementation is competitive with the state-of-the-art Gr||bner basis solvers Magma and msolve on randomly generated well-determined systems, with significant advantages in the low-variable/high-degree regime, while Magma and msolve remain preferable in the high-variable/low-degree regime.
Finally, we formulate three elimination strategies for polynomial systems arising from AO primitives: direct elimination, iterative elimination, and reduction-based hybrid elimination. We demonstrate these strategies on Poseidon, Vision, and Xhash12, yielding complexity reductions in many cases.
## 2026/1970
* Title: Multi-Party Distributed Point Functions, Revisited
* Authors: Elaine Shi, Tianyao Gu, Xuanye Zheng, Yue Yang, Yiping Liu, Yucheng Fu
* [Permalink](https://eprint.iacr.org/2026/1970)
* [Download](https://eprint.iacr.org/2026/1970.pdf)
### Abstract
In this paper, we revisit the design of multi-party distributed point functions (DPFs) and make several new contributions that advance the state of the art. We begin by revisiting security amplification, a fundamental tool underlying many DPF constructions. In particular, the recent landmark work of Goel, Wang, and Wang (CRYPTO'25) critically relies on security amplification and, for a general polynomial number of parties, gives the only known construction based on one-way functions (OWFs) that achieves sublinear dependence on the input domain size. Unfortunately, due to a known gap in the proof of the security amplification theorem of Boyle et al. (CRYPTO'22), we currently still lack a fully established security amplification theorem for DPFs.
We fill this gap by providing a new proof of security amplification for DPFs with tight parameters. Equipped with this security amplification theorem as a key technical tool, we develop several new techniques that asymptotically improve the communication cost of multi-party DPFs in both the honest-majority and corrupt-majority settings. Our main results are summarized below, where $N$ denotes the input domain size, $m$ denotes the number of parties, and $t$ denotes the corruption threshold:
In the all-but-one-corrupt setting, we describe a new scheme based on OWFs with $\widetilde{O}_\lambda\left(N^{\frac12 + \epsilon} \cdot \sqrt{m}\right)$ share size where $\epsilon > 0$ is an arbitrarily small constant. In comparison, the best previously known OWF-based construction due to Goel et al. incurs $\widetilde{O}_\lambda\left(N^{\frac12 + \epsilon}\cdot m^3\right)$ share size.
In the honest-majority setting, assuming $m > (1+\epsilon)D t$ for some integer $D \ge 2$ and arbitrarily small constant $\epsilon > 0$, we construct a new OWF-based scheme with share size $\widetilde{O}_\lambda(N^{\frac{1+\epsilon}{2D}})$, as well as an information-theoretically secure scheme with share size $\widetilde{O}(N^{1/D})$. Both constructions achieve an exponential factor
improvement in their dependence on $m$ and $t$ compared to the state-of-the-art schemes of Bunn, Kushilevitz, and Ostrovsky.
## 2026/1971
* Title: Component-Dual Compression and the Exact Characteristic-Two Contribution Region of the Relaxed Non-Fano Port
* Authors: Shahram Khazaei, Maghsood Parviz
* [Permalink](https://eprint.iacr.org/2026/1971)
* [Download](https://eprint.iacr.org/2026/1971.pdf)
### Abstract
Jafari and Khazaei (Journal of Cryptology, 2021) introduced a kernel-based lower-bound method for linear secret-sharing schemes by fixing one minimal qualified coalition and comparing its participant components with those arising from auxiliary minimal qualified coalitions. These comparisons form a star. We extend the same mechanism from stars to coalition-labelled trees and obtain new characteristic-two inequalities for the relaxed-line non-Fano port $\widehat N$. For this access structure, the tree method is strictly stronger than the star method, yielding facet inequalities not implied by the star inequalities. We also show that the tree method does not determine the full contribution region.
To complete the analysis of $\widehat N$, we introduce component-dual compression (CDC). CDC replaces each share by the span of the components selected from minimal reconstructions and realizes the duals of these compressed spaces in a common coordinate system indexed by the original minimal coalitions. This yields the remaining lower-bound inequalities. Together with matching constructions, the star, tree, and CDC bounds determine the complete characteristic-two linear contribution region of $\widehat N$, with maximum and average linear information ratios $5/4$.
## 2026/1972
* Title: Criminology: Refined Techniques for Compression Side-Channel Attacks
* Authors: Yuanming Song, Lenka Marekov|i, Kenneth G. Paterson
* [Permalink](https://eprint.iacr.org/2026/1972)
* [Download](https://eprint.iacr.org/2026/1972.pdf)
### Abstract
It has been known for two decades that performing compression before encryption is dangerous, because it introduces a side channel leaking information about plaintexts through ciphertext lengths: the compressed plaintext length may be visible in the ciphertext length, and the amount of compression obtained is plaintext-dependent; hence an adversary can obtain some leakage about the plaintext via observation of ciphertext lengths. This issue was first pointed out by Kelsey (FSE 2002) and turned into a practical plaintext recovery attack in the form of the CRIME attack on SSL and TLS by Rizzo and Duong in 2012. A long series of variations and attacks against other systems followed. Despite the known dangers, the compress-then-encrypt paradigm is still prevalent in practice today. This may be because the compression-based side channel is susceptible to noise and may require a large number of queries to enable plaintext recovery, and so can be mitigated by either adding noise (e.g. with random padding) or limiting an adversary's interaction with the system.
We demonstrate that this side channel is much more powerful than previously thought. We focus on the widely-used DEFLATE algorithm in our analysis. We present novel techniques that enable strong amplification of small length differences arising during compression. Our telescoping and chaining amplification techniques exploit the way in which DEFLATE replaces common strings by shorter back-references. Our collision-based amplification technique focusses on exploiting hash table collisions in DEFLATE implementations. This involves a deeper examination (and exploitation) of the internals of DEFLATE than in previous works. These insights result in compressed length differences growing linearly with the length of queries. Compared with length differences of a few bits or bytes in prior work, our new amplification techniques thus enable us to defeat existing noise-based countermeasures.
Finally, we introduce the concept of CRIME automata, these being carefully crafted query strings that enable an attacker to exert fine control over the internal behaviour of DEFLATE and produce differences in the output lengths of the compressor according to various criteria (such as whether the DEFLATE sliding window contains a given target string). In turn, our automata are composed in a modular fashion from gadgets having different functions, including matching against target strings, performing logical operations between other gadgets, and, most importantly, amplifying differences in output lengths using the above-mentioned techniques. We provide multiple, concrete automata designs that serve different attack goals. These designs are supported by experiments and a publicly available codebase demonstrating the power, flexibility, and practical impact of our CRIME automata approach.
## 2026/1973
* Title: Addition-Efficient MDS Matrices from Superconcentrators (Full Version) * Authors: Jooyoung Lee, Seungmin Park, Mincheol Son
* [Permalink](https://eprint.iacr.org/2026/1973)
* [Download](https://eprint.iacr.org/2026/1973.pdf)
### Abstract
MDS matrices are a key structure for providing optimal diffusion in symmetric primitives. However, the theoretical analysis of their cost remains limited. This issue is particularly relevant to arithmetization-oriented permutations, where designs often either use costly MDS matrices or sacrifice the MDS property to reduce the number of constraints.
This paper studies the number of fan-in-two additions needed to implement MDS matrices. We represent fan-in-two addition constraints by a directed acyclic graph and derive lower bounds on the number of additions using the established result that any such computation graph implementing an MDS matrix must be a superconcentrator.
Building on size-reduction lemmas for superconcentrators, we present a recursive algorithm that improves both lower and upper bounds for $t\times t$ matrices with $t\leq 8$. As a result, we obtain explicit MDS matrices over large primes for $t=3,4,5,6,7,8$, requiring $5,8,12,16,21,26$ additions, respectively. These bounds are tight for $t\leq 6$. We also use the same superconcentrator graphs as templates for MDS matrices with $k$-bit words. For $t=5,6,7$, our matrices require fewer XORs than the state of the art for most considered parameter choices in this line of work.
## 2026/1974
* Title: Exact-Coset Response Existence in SQIsign-like Protocols: Beyond Additive Hom Geometry
* Authors: Ti-Hong Qin, Hong-Yu Tang, Zong-Bin Wang, Wen-Lun Pan
* [Permalink](https://eprint.iacr.org/2026/1974)
* [Download](https://eprint.iacr.org/2026/1974.pdf)
### Abstract
Arithmetic response existence is a prerequisite for signing, but is not implied by a large number of bounded-degree isogenies. We study how endpoint collisions, exact level-structure constraints, and sampling dependence affect this existence problem for supersingular curves in characteristic $p$. For every binary degree filter independent of the endpoints and every $1 \le D < p$, we prove the mean-square endpoint discrepancy bound $\mathcal{V}_a \ll_\delta p^\delta(D^2 + D^{7/2}/p) + P_a^2/p^2$, where $P_a$ counts the allowed cyclic kernels on each source curve. The proof combines square-divisor inversion with classical BrandtrCoHecke and harmonically weighted Petersson estimates. Filters with $P_a \ge cD^2$ for fixed $c>0$ give existence probability $1-o(1)$ for independent uniform endpoints above $p^{1/2+\gamma}$; every filter gives $o(1)$ below $p^{1/2-\gamma}$, for fixed $\gamma>0$. The Weil pairing converts the two cosets of the kernel of the quadratic determinant character into degree filters. Combining this observation with an exact-coset incidence bound yields opposite existence probabilities at the same degree bound: $1-o(1)$ for this subgroup and $o(1)$ for split and nonsplit Cartan normalizers, although all three induce the same additive Hom-lattice condition. These are idealized experiments with different challenge-space sizes. We also give challenge-preserving primitive reduction and explicit joint-distribution transfer conditions.
## 2026/1975
* Title: Oblivious Signaling
* Authors: Mirza Kamrul Bashar Shuhan, Foteini Baldimtsi, Giuseppe Ateniese
* [Permalink](https://eprint.iacr.org/2026/1975)
* [Download](https://eprint.iacr.org/2026/1975.pdf)
### Abstract
An anonymous messaging service has to solve a basic routing problem: a server must deliver an encrypted message to its recipient without learning who the recipient is. Broadcasting all ciphertexts hides the destination but forces every recipient to constantly scan for new messages. Oblivious Message Retrieval (OMR; CRYPTO~'22) tackles this by using fully homomorphic encryption (FHE) to let an untrusted server perform message retrieval on a recipient's behalf without learning which messages are pertinent.
We introduce Oblivious Signaling, which shifts this cost from retrieval to sending. The server maintains a fixed-size encrypted inbox for each recipient. When a sender submits a message, the server applies the same homomorphic update to every inbox: the intended inbox absorbs the message, and the rest remain unchanged at the plaintext level. The update is uniform, can be parallelized across inboxes, and ties the delivery cost strictly to the size of the anonymity set rather than global traffic. Recipients retrieve by fetching and decrypting their inbox, so checking for new messages is independent of the global traffic.
We formalize receiver privacy against an untrusted server, even when it colludes with other users, give a concrete construction based on fully homomorphic encryption, and analyze the resulting "digital postage'' trade-off: delivery is expensive, but checking is cheap. Our prototype identifies practical regimes in which this cost-model shift is preferable to scan-based retrieval, even with highly optimized OMR implementations. This cost model is well-suited to settings where recipients check frequently, and messages arrive sporadically, and it naturally discourages high-volume spam.
## 2026/1976
* Title: Properties of the Me Operation and Me-Scalar Multiplication on Elliptic Curves over Finite Fields
* Authors: Masaaki Shirase
* [Permalink](https://eprint.iacr.org/2026/1976)
* [Download](https://eprint.iacr.org/2026/1976.pdf)
### Abstract
The M operation was introduced by Yura as an alternative to the max operation appearing in the box-ball system (BBS) to construct a BBS over finite fields. The Me operation is a version of the M operation for an elliptic curve $E$ over a finite field ${\mathbb F}_p$. As with the M operation, the Me operation satisfies the idempotent law and does not satisfy the associative law. Nevertheless, for $P,Z \in E({\mathbb F}_p)$ and $n \in {\mathbb N}$, the 1st Me-scalar multiplication $P_{n,Z}^{\,I}$ with auxiliary element $Z$ can be defined. Moreover, for $P,Z \in E({\mathbb F}_p)$ and $n \in {\mathbb Q}_+$, the 2nd Me-scalar multiplication $P_{n,Z}^{II}$ with auxiliary element $Z$ can be defined. This paper shows the following properties that may be useful to construct cryptographic protocols: $(P_{n_0,Z}^{\,I})_{n_1,Z}^{\,I}=(P_{n_1,Z}^{\,I})_{n_0,Z}^{\,I}$, $(P_{n_0,Z}^{II})_{n_1,Z}^{II}=(P_{n_1,Z}^{II})_{n_0,Z}^{II}=P_{n_0n_1,Z}^{II}$; the 1st MeDLP and the 2nd MeDLP, which are Me versions of the ECDLP, are difficult to solve on classical computers under certain conditions; the 1st MeCDH and the 2nd MeCDH, which are Me versions of the ECCDH, are NOT difficult to solve; and the sequence $\{ P_{n,Z}^{II}:n=1,2,3,\ldots \}$ is nonperiodic unless it is constant.
## 2026/1977
* Title: Lattice-based Secret-Key Functional Encryption for Constant-Degree Polynomials
* Authors: Valerio Cini, Russell W. F. Lai, Akin |Lnal, Ivy K. Y. Woo
* [Permalink](https://eprint.iacr.org/2026/1977)
* [Download](https://eprint.iacr.org/2026/1977.pdf)
### Abstract
We present a lattice-based construction of secret-key functional encryption (FE) for low-norm polynomials of any constant degree $d$, hence also for $\mathsf{NC}^{0}$ circuits. We rely on two core ingredients:
1. New trapdoor and preimage sampling algorithms for certain degree-$d$ tensor-structured matrices, used to generate functional secret keys.
2. A new $k$-LWE-style assumption where short preimages of non-zero images with respect to the above tensor-structured matrix are given as hints, under which we prove that our secret-key FE scheme is selectively secure (under unbounded collusion). To gain confidence in the new assumption, we prove that the standard LWE assumption implies the degree-$1$ case and cryptanalyse the $d > 1$ case.
As a corollary, we obtain a new pathway to post-quantum secure indistinguishability obfuscation (iO), conditioned on the above new assumption, standard LWE, and the existence of polynomial-stretch pseudorandom generators in $\mathsf{NC}^{0}$. Along the way, we give a new, simple (public-key) FE scheme for linear functions with selective security under the standard LWE assumption.
## 2026/1978
* Title: Succinct Two-Round Two-Party Signing from PCFs
* Authors: Lennart Braun, Geoffroy Couteau, Kelsey Melissaris, Mahshid Riahinia, Elahe Sadeghi
* [Permalink](https://eprint.iacr.org/2026/1978)
* [Download](https://eprint.iacr.org/2026/1978.pdf)
### Abstract
We introduce new two-party threshold signature schemes with strong efficiency and security. The application of our methodology to the two most popular signatures, Schnorr and ECDSA, yields two-round, two-party, stateless and deterministic signing with 4-12 ms of computation on one core of a standard laptop, extremely low communication -- 96 B for Schnorr, and 128 B for ECDSA -- and full concurrent simulatable security. At the heart of our approach is a new pseudorandom correlation function (PCF) for vector-OLE that admits an efficient key generation protocol; we design an end-to-end maliciously-secure and highly parallelizable DKG for this PCF and, using this DKG, we obtain an estimated runtime of 44 s for the (one-time) distributed setup of Schnorr and ECDSA on one core of a standard laptop.
## 2026/1979
* Title: From Specs to Apps: Verifying and Monitoring Models of Signal and WhatsApp
* Authors: Moustafa Said, Aurora Naska, Kevin Morio, Robert K|+nnemann
* [Permalink](https://eprint.iacr.org/2026/1979)
* [Download](https://eprint.iacr.org/2026/1979.pdf)
### Abstract
The Signal protocol is a prominent messaging protocol that se-
cures communication for billions of users. It powers WhatsApp,
the most widely used messaging application worldwide, and the
Signal app, popular among privacy-conscious users. Extensive re-
search in the computational and Dolev-Yao settings provides strong
formal security guarantees for the protocol itself. However, a gap
remains between the guarantees of the protocol specification and
the implementationrCOs actual behavior at runtime.
In this work, we bridge this gap by applying SpecMon, a recently
proposed runtime monitor, to check whether observed executions
conform to formal protocol models. To this end, we instrument two
applications (WhatsApp Web and Signal Desktop) to capture their
interactions with the network and the cryptographic components.
Using this instrumentation, we develop two multiset-rewrite models
that are compatible with Tamarin, thus enabling verification. We
derive the first model of WhatsApp WebrCOs implementation of the
Signal protocol and the most detailed model to date of SignalrCOs
original protocol. Monitoring establishes that observed executions
conform to these models, relative to the trusted event extraction
and the symbolic abstraction. For the core components of the Signal
protocol, we verify authentication and secrecy properties. Finally,
monitoring reveals previously undocumented differences between
the original libsignal library and WhatsApprCOs fork.
We evaluate our methodology and demonstrate its reproducibil-
ity. Developing the WhatsApp Web model, instrumenting the app,
adding fuzzing, and running the experiments took three person-
weeks. We also demonstrate efficient monitoring of real-world
applications and detection of deliberately injected security faults,
with low overhead in our measured setting.
## 2026/1980
* Title: Better Security Proofs for X3DH and XHMQV
* Authors: Jiawei Bao, Jiaxin Pan, Runzhi Zeng
* [Permalink](https://eprint.iacr.org/2026/1980)
* [Download](https://eprint.iacr.org/2026/1980.pdf)
### Abstract
The Signal protocol is used by billions of users daily and recognized as the gold standard for end-to-end encrypted messaging. Its initial handshake protocol X3DH uses XEdDSA to sign its semi-static key and allows parties to derive a session key asynchronously. The protocol is implemented over Curve25519, relying on the assumed 128-bit hardness for solving Discrete Logarithms (DL). Previous non-tight reductions incur a large loss in the number of sessions, and the resulting concrete security guarantees fall far below the intended 128-bit security level. This motivates the development of tight security bounds for these protocols.
In this paper, we improve the security analysis of X3DH and its recent enhancement XHMQV (Fiedler et al., CRYPTO'25) by providing tight security reductions under multi-user DiffierCoHellman (DH) assumptions (Kiltz et al., CT-RSA'23) in the Random Oracle Model. Unlike prior work, our proofs are in the more realistic multi-Test setting. The variant of X3DH that we analyze hashes additional context into the session key. Although this modification is minor, it yields tight security bounds and provides a stronger justification for the use of Curve25519. In light of our results, the Signal developers plan to adopt the same modification.
## 2026/1981
* Title: Parallelized Authenticated Encryption with Tag Combiners
* Authors: Christoph Dobraunig, Charlotte Lefevre
* [Permalink](https://eprint.iacr.org/2026/1981)
* [Download](https://eprint.iacr.org/2026/1981.pdf)
### Abstract
When looking at authenticated encryption schemes, we have schemes that process the input data by having serial calls to their underlying building blocks, like duplex-based constructions, and schemes that allow for parallel calls to their underlying building blocks, like the Galois Counter Mode (GCM). Naturally, one can parallelize a serial scheme by distributing the data to encrypt over different calls to the serial scheme. However, there are many different choices to be made, like how to choose the nonce for the different instances, or if and how to combine the multiple tags into a single one. In this paper, we investigate different possible choices providing proofs for their security. Interestingly, we see a huge variance in the provable properties and hence, the security in making a serial scheme parallel. Or, motivating the problem more generally, we are investigating tag combiners, where the single tags to be combined are secret to the adversary.
## 2026/1982
* Title: Cryptanalysis of the Alternative Mod-2/Mod-3 Weak PRF
* Authors: Augustin Bariant, Christina Boura, Baptiste Germon, Rachelle Heim, Charles Meyer-Hilfiger, Tyge Tiessen
* [Permalink](https://eprint.iacr.org/2026/1982)
* [Download](https://eprint.iacr.org/2026/1982.pdf)
### Abstract
The alternative mod-$2$/mod-$3$ function is one of the most widely used weak PRF constructions in modern cryptographic protocols. Despite its practical importance, its security has received relatively limited attention, with the main cryptanalytic results consisting of two distinguishing attacks due respectively to Cheon et al. and Johansson et al. In this work, we revisit the cryptanalysis of this primitive by analyzing the output distribution of the weak PRF under fixed Hamming weights for both the secret key and the inputs. This refined analysis allows us to isolate and amplify statistical biases that were averaged out in previous works. Using this approach, we derive a new distinguishing attack with asymptotic data and time complexity $\mathcal O(2^{0.099n})$. We implemented the attack for the original parameter set $n=384$, thereby obtaining the first practical attack against this instance of the construction. We then introduce a generic technique, called the splitting strategy, which consists in partially fixing or guessing part of the secret key in order to amplify the biases while introducing an additional computational cost that can be efficiently handled using Fast Fourier Transform-like techniques. This leads to the currently best known attack against the construction, with asymptotic data, time, and memory complexities $\widetilde{\mathcal O}(2^{0.09n})$. This last technique also provides a useful time-memory trade-off for estimating the security of real-world constructions when the available data is bounded: we show that the weak PRF offers less than $128$-bit security for $n = 510$ when the data is limited to $2^{45}$. Finally, we revisit the attack of Johansson et al. and provide a corrected and refined analysis of the underlying bias, showing that the statistical behavior of the attack differs significantly once the Hamming weight of the secret key is taken into account. This new analysis explains phenomena previously observed experimentally but left unexplained. Thanks to this approach we are able to identify a large class of keys for which the attack performs much better asymptotically than anticipated by Johansson et al.
## 2026/1983
* Title: Akita: A High-Performance Lattice-Based Polynomial Commitment Scheme
* Authors: Quang Dao, Omid Bodaghi, Amirhossein Khajehpour, Giuseppe Vitto, Mohammadtaghi Badakhshan, Markos Georghiades, Fengrun Liu, Jiapeng Zhang, Justin Thaler
* [Permalink](https://eprint.iacr.org/2026/1983)
* [Download](https://eprint.iacr.org/2026/1983.pdf)
### Abstract
Lattice-based polynomial commitment schemes (PCSs) promise post-quantum SNARKs with two properties that elliptic curves provide and hash-based schemes, today's deployed post-quantum default, do not: concretely small proofs and commitment time proportional to the number of nonzero entries in the committed polynomial rather than its length. The second property is essential to Twist and Shout (CRYPTO 2026), the fastest known memory-checking arguments and a core component of the Jolt zero-knowledge virtual machine (zkVM): their prover commits to enormous polynomials that are almost entirely zero. Yet despite a wave of recent work, existing lattice-based PCSs achieve at most two of the three properties that deployment demands: small proof size, fast verification, and soundness from standard assumptions such as Module-SIS.
We present Akita, a lattice-based PCS that achieves all three. We improve on the square-root-time verifier of Hachi (ePrint 2026), our direct predecessor, through a new setup offloading technique: the public setup matrices are committed ahead of time, and the verifier's work in processing them is deferred and proved against these commitments. For any fixed $k\ge2$, this reduces verification time to $\widetilde O_{k,\lambda}(N^{1/k})$ while preserving $\widetilde O_{k,\lambda}(\log N)$ proof size, $\widetilde O_{k,\lambda}(N)$ prover time, and security from standard Module-SIS. We also optimize every fold from root to tail and iterate the fold to completion. This includes an optimized digit range check, relation-specific ring dimensions and subring challenges, complementary methods for embedding field evaluations and checking ring relations, commitments compressed to $128$bytes each, and exact Euclidean norm checks for tighter Module-SIS parameters.
Beyond the core protocol, Akita provides the capabilities needed for deployment in a zkVM: batched openings of separately committed polynomials, low-communication distributed proving, and an offline planner for selecting secure parameters under configurable cost objectives. We implement Akita in Rust and benchmark it against existing lattice-based and hash-based PCSs. Across these benchmarks, Akita produces proofs of only $61$-$70$KB, matching Greyhound's when both schemes are calibrated to the same security level, while verifying $10\times$ to $94\times$ faster. Akita's prover uses the least memory: beyond storing the polynomial itself, its memory overhead grows sublinearly in the polynomial size. We also integrate Akita into Jolt. For every program size we evaluate, Jolt-with-Akita achieves a $1.3\times$ to $2.2\times$ prover speedup and $2.2\times$ to $7.4\times$ verifier speedup over Jolt-with-Dory, while matching it in proof size, with every proof remaining below $100$KB.
--- Synchronet 3.22a-Linux NewsLink 1.2