Mastodawn

#eprint Revision of Human-Extractable ZK Proofs of Knowledge: A Solution to Dark DAOs by Zeyuan Yin, Leiyuan Tian, Bingsheng Zhang, Kui Ren (https://ia.cr/2026/511)

Human-Extractable ZK Proofs of Knowledge: A Solution to Dark DAOs

A Decentralized Autonomous Organization (DAO) is a pioneering evolution to realize a decentralized democratic governance over a blockchain. In a DAO, stakeholders usually make collective decisions through secure on-chain voting. Recently, Dark DAO (Austgen et al., arXiv:2311.03530) was proposed as a decentralized cartel that enables automated vote-buying. It attacks the inalienable authentication of a remote e-voting system by leveraging key encumbrance via MPC or TEEs, enabling a voter to pass the authentication without knowing the actual key. To defend against this new type of attack, the notions of individual knowledge (Dziembowski et al., CRYPTO '23) and complete knowledge (Kelkar et al., CCS '24) were proposed, ensuring that the prover has unencumbered knowledge of a secret. However, their solutions rely on TEEs or ASICs, which are difficult to deploy on blockchain. Inspired by the human-extractable CAPTCHA puzzles proposed by Kumarasubramanian et al. (PKC '13), we propose a new primitive called human-extractable zero-knowledge proofs of knowledge (HE-ZKPoK) as an alternative solution to Dark DAOs. Our HE-ZKPoK protocol forces the prover to solve human-extractable CAPTCHA puzzles along with completing a standard zero-knowledge proof of knowledge, avoiding the need for specialized hardware. As a result, any human entity can extract the witness merely by looking at the prover's CAPTCHA queries and the associated puzzles. With this property, we conclude that if a voter sells his vote, his secret key will be fully exposed, thus deterring voters from engaging in vote-buying.

IACR Cryptology ePrint Archive

eprint-revision May 15

#eprint Revision of A Post-Quantum Accountable Sanitizable Signature Scheme Based on Unbalanced Oil and Vinegar by Zhiwei Wang (https://ia.cr/2026/827)

A Post-Quantum Accountable Sanitizable Signature Scheme Based on Unbalanced Oil and Vinegar

Sanitizable signature schemes~(SSS) allow a designated sanitizer to modify admissible portions of a signed message while preserving the validity of the original signer's authorisation. All existing SSS constructions satisfying the Brzuska et~al.\ security framework rely on classical number-theoretic assumptions broken by Shor's algorithm. We present \textsf{UOV-San}, the first sanitizable signature scheme based entirely on multivariate cryptography. The construction employs a dual-signature architecture with strict key separation enforced by a two-message interactive signing protocol: the signer holds only $\sk_S$ and the public chameleon key~$\ck$; the sanitizer holds $\sk_\mathit{San}$ and the trapdoor key~$\tk$. We introduce a new \textsf{PreColl} (preimage collision) assumption capturing the hardness of finding distinct inputs to the public quadratic map that collide under $P$ (not only under $H_2 \circ P$). Combined with the collision resistance of a random oracle we obtain an implementable multivariate chameleon hash requiring no random-oracle programming. \textsf{UOV-San} provably achieves \emph{unforgeability}, \emph{immutability}, and \emph{accountability}---including against a malicious signer---under MQ, OVD, PreColl, and sEUF-CMA in the random oracle model with classical adversaries. We forgo transparency and privacy: these properties are structurally incompatible with the dual-signature architecture and key-separation requirement, and are operationally unnecessary for our target application domains (supply chain audit, government document redaction, blockchain audit trails). Experimental evaluation confirms practical signing times under 5\,ms and verification times under 2\,ms on commodity hardware.

IACR Cryptology ePrint Archive

eprint-revision May 15

#eprint Revision of Lightning, Field-Agnostic Super-Efficient Polynomial Commitment Scheme by Wenjie Qu, Yanpei Guo, Jiaheng Zhang (https://ia.cr/2026/258)

Lightning, Field-Agnostic Super-Efficient Polynomial Commitment Scheme

Polynomial commitment schemes (PCS) are a fundamental building block of modern zkSNARKs. In this paper, we propose \emph{Lightning}, a new coding-based PCS that achieves state-of-the-art prover efficiency. Our main technical contribution is a new linear code family, the \emph{Lightning code}, which can be instantiated from any base code with constant relative distance. Compared to the base code, Lightning code significantly reduces encoding cost by trading off relative distance. We integrate Lightning code into the standard coding-based PCS framework of Ligero and Brakedown. Experimental results show that Lightning PCS reduces prover commitment time by up to $2.3\times$ compared to the fastest prover configuration of Brakedown, at the cost of a $2.1\times$ increase in proof size. Overall, Lightning provides a practical mechanism for trading proof size for prover efficiency in coding-based PCS constructions.

IACR Cryptology ePrint Archive

eprint-revision May 15

#eprint Revision of Beyond the 1/2 Bound: On the Theory and Practice of Biprimality Tests by ChihYun Chuang, IHung Hsu, TingFang Lee (https://ia.cr/2024/2072)

Beyond the 1/2 Bound: On the Theory and Practice of Biprimality Tests

The Boneh-Franklin (BF) biprimality test, a cornerstone of distributed RSA key generation, has a universally accepted worst-case soundness error of $1/2$. We show that this two-decade-old bound is not tight and present a collection of results that refine and generalize this fundamental test. Our contributions are threefold: \textbf{(1) A Tight Soundness Bound for the BF Test:} Our primary contribution is a rigorous proof that the worst-case acceptance probability of the BF test for a non-RSA modulus is at most $1/4$, not the long-accepted $1/2$. By constructing cases that meet this bound, we establish that it is tight. This fundamental result allows existing protocols to halve the required iterations, thereby improving the efficiency of verifying valid moduli while maintaining the same security level. \textbf{(2) A Generalized Test for Universal Applicability and a Nuanced Verdict:} We introduce a versatile Lucas-sequence-based test that resolves the long-standing limitation of the BF test to Blum integers. While we prove its soundness error is theoretically and empirically superior in the vast majority of cases, our analysis, based on a performance model parameterized by simulation, indicates a trade-off. For the specific task of generating Blum integers, the exceptional local computation speed of the BF test suggests it maintains a practical advantage in latency-sensitive environments. This nuanced finding underscores the interplay between theoretical soundness error and real-world performance. \textbf{(3) New Protocols for an Expanded Design Space:} We construct new distributed verification protocols that realize our foundational insights. Our Lucas-based protocol provides the first efficient, provably secure solution for generating all standard RSA moduli in the semi-honest model, alongside a maliciously secure variant for Blum integers. This fills a gap for applications requiring generality and, combined with our comparative analysis, provides a clearer and more complete toolkit for protocol designers. Overall, our work refines the theoretical bounds of biprimality testing and provides a more efficient and versatile foundation for distributed RSA key generation.

IACR Cryptology ePrint Archive

eprint-revision May 15

#eprint Revision of Issuer-Hiding for BBS Anonymous Credentials via Randomizable Keys by Andrea Flamini, Karla Friedrichs, Anja Lehmann (https://ia.cr/2026/369)

Issuer-Hiding for BBS Anonymous Credentials via Randomizable Keys

Anonymous credentials (AC) equip users with credentials on attested attributes, which enable them to prove verifiable yet data-minimizing statements over their attributes. However, in standard ACs, each credential presentation reveals the credential issuer, which could be more information than intended and necessary, e.g., when merely proving age or personhood. Issuer-Hiding Anonymous Credentials (IHAC) address this limitation and hide the issuer in the presentation. That is, they only reveal that the user has a credential from an issuer within a certain trust set, referred to as the policy. Recent works by Sanders and Traoré, and Katz and Sefranek show how to add issuer-hiding to PS- and BBS-based credentials while keeping presentations compact, i.e., not scaling in the number of issuers. However, both constructions require the verifier to generate dedicated policy key pairs, turning verification into a secret key operation. Managing these verifier-specific keys introduces additional complexity and affects the resulting practical privacy and security guarantees. In this work, we propose two IHAC schemes from BBS signatures that achieve compact presentations without the need of such verifier-specific keys. At the core of our schemes is a technique to randomize BBS public keys and adapt the signatures accordingly, which we believe to be of independent interest.

IACR Cryptology ePrint Archive

eprint-revision May 15

#eprint Revision of AgentCrypt: Advancing Privacy and (Secure) Computation in AI Agent Collaboration by Harish Karthikeyan, Yue Guo, Leo de Castro, Antigoni Polychroniadou, Leo Ardon, Udari Madhushani Sehwag, Sumitra Ganesh, Manuela Veloso (https://ia.cr/2025/2216)

AgentCrypt: Advancing Privacy and (Secure) Computation in AI Agent Collaboration

As AI agents increasingly operate in real-world, multi-agent environments, ensuring reliable and context-aware privacy in agent communication is critical, especially to comply with evolving regulatory requirements. Traditional access controls are insufficient, as privacy risks in agentic applications often arise after access is granted; agents may use information in ways that compromise privacy, such as messaging humans, sharing context with other agents, making tool calls, persisting data, or generating arbitrary functions of private information. Existing approaches often treat privacy as a binary constraint, whether data is shareable or not, overlooking nuanced, role-specific, and computation-dependent privacy needs essential for regulatory compliance. Agents, including those based on large language models, are inherently probabilistic and heuristic. There is no formal guarantee of how an agent will behave for any query, making them ill-suited for operations critical to security. To address this, we introduce AgentCrypt, a three-tiered framework for fine-grained, secure agent communication that adds a protection layer atop any AI agent platform. AgentCrypt spans unrestricted data exchange (Level 1) to fully encrypted computation using techniques such as homomorphic encryption (Level 3). Unlike much of the recent work, our approach guarantees that the privacy of tagged data is always preserved—even when the underlying AI model makes errors. AgentCrypt ensures privacy across diverse interactions and enables computation on otherwise inaccessible data, overcoming barriers such as data silos. We implemented and tested it with Langgraph and Google ADK, demonstrating versatility across platforms. We also introduce a benchmark dataset simulating privacy-critical tasks at all privacy levels, enabling systematic evaluation and fostering the development of regulatable machine learning systems for secure agent communication and computation.

IACR Cryptology ePrint Archive

eprint-revision May 15

#eprint Revision of Secret-Key PIR from One-Way Functions by Nir Bitansky, Noam Mazor (https://ia.cr/2026/865)

Secret-Key PIR from One-Way Functions

In secret-key private information retrieval (SK-PIR), the client in an offline phase processes the database using a short secret key. In the online phase the client could then use the secret key to make queries to the server, without revealing the entries accessed, and using only sublinear communication $o(N)$ in the database size $N$. While (non-SK) PIR requires public-key cryptography, recent work provides evidence that SK-PIR may not. In particular, Chen, Ishai, Mour, and Rosen (STOC 26) construct SK-PIR with communication $N^{\varepsilon}$, for any $\varepsilon$, from high-noise LPN, which is not known to imply public-key cryptography. We construct SK-PIR with online communication $\tilde{O}(\sqrt{N)}$, under the minimal assumption of one-way functions. More generally we can achieve client-to-server communication $\tilde{O}(N_c)$ and server-to-client communication $\tilde{O}(N_s)$ as long as $N_c \cdot N_s \geq N$. Our construction is simple and is based on garbled circuits with an uncorrelated input encoding property, which is satisfied by schemes from the literature.

IACR Cryptology ePrint Archive

eprint-revision May 15

#eprint Revision of Zinc+: SNARKs for Polynomial Rings by Alexander Abdugafarov, Albert Garreta, Amit Kumar, Michał Osadnik, Psi Vesely, Ilia Vlasov, Kai Zhe Zheng (https://ia.cr/2026/855)

Zinc+: SNARKs for Polynomial Rings

Nearly all succinct proof systems express computations as algebraic constraints over a finite field. Operations not native to this field, such as bitwise manipulation, modular arithmetic, and lattice-ring operations, require an arithmetization step that can inflate the witness size by one or more orders of magnitude. We introduce Universal Constraint Systems (UCS) and Zinc$+$. The first is a relation that can express the above constraints with minimal overhead. The second is a framework for building SNARKs for UCS. Concretely, UCS consists of algebraic constraints and ideal membership predicates over multiple polynomial rings simultaneously, such as $\mathbb{F}_q[X], \mathbb{Q}[X], \mathbb{Z}[X]$, etc. Zinc$+$ SNARKs are built from 1) a PIOP for UCS, and 2) a hash-based IOPP for multilinear polynomials over $R=\mathbb{Q}[X]$ or $R=\mathbb{F}_q[X]$. For 1), we provide a general compiler that takes standard finite-field PIOPs and turns them into a PIOP for UCS. The IOPP in 2) depends on $R$: for $R=\mathbb{F}_q[X]$, we construct it via a black-box lift of any existing IOPP for $\mathbb{F}_q$, and for $R=\mathbb{Q}[X]$, we present a novel tensor IOPP design, instantiated with the new code family below. We introduce Integer Pseudo-Reed Solomon (IPRS) codes, a new family of MDS codes over $\mathbb{Q}$ and $\mathbb{Q}[X]$. While not Reed-Solomon codes, these codes have optimal MDS relative minimal distance, support efficient FFT-based encoding, and have bounded norm growth when encoding (unlike a naïve lift of Reed-Solomon codes to the integers). Our unoptimized, open-source, implementation proves 7 SHA-256 compressions followed by the multi-scalar multiplication (MSM) part of an ECDSA verification (the bulk of the work), with the following performance, benchmarked on a MacBook Air M4, without zero-knowledge: Prover time: 40.6 ms, Verifier time: 7.0 ms, Proof size: 198 KB. Zinc$+$ can be instantiated end-to-end or as a lightweight extension to any existing hash-based SNARK over~$\mathbb{F}_q$.

IACR Cryptology ePrint Archive

eprint-revision May 15

#eprint Revision of A Primer on Dependency in Polynomial Product: Identify, Exploit, and Trim by Yijian Liu, Jiangxia Ge, Yu Zhang, Jiabo Wang, Xianhui Lu (https://ia.cr/2026/802)

A Primer on Dependency in Polynomial Product: Identify, Exploit, and Trim

Many lattice-based encryption schemes admit a negligible but nonzero decryption failure rate (DFR), which is tied to both correctness and security through failure-based attacks. Several module-lattice constructions (e.g., LAC at NIST PQC Round 2 and DAWN at Asiacrypt 2025), as well as average-case noise analyses in FHE, estimate the DFR from one-coordinate marginals combined with an independence approximation across the coefficients of polynomial products. Geometrically, this approximation models the noise as uniformly distributed on a sphere. In the rare-event regime relevant to concrete security, the approximation can be optimistic: polynomial convolution introduces structured dependencies with no analogue in unstructured lattice settings, and the true noise spreads towards a cube rather than a sphere. To make this effect explicit, we study polynomial products in power-of-two cyclotomic rings through a norm-wise decomposition. The decomposition separates an outer term (corresponding to the sphere's radius), which is effectively captured by coefficient-wise models, from an inner term (representing the uneven parts of the spherical surface) that measures convolution-induced dependencies. This gives an exact account of the heavier tails observed in polynomial products and of the gap between independence-based estimates and actual failure behavior. This perspective has consequences for both attacks and design. On the attack side, it yields a principled proxy criterion for constructing high-DFR candidate ciphertexts in failure-based attacks. In particular, it explains why the attack of Guo et al. (Asiacrypt 2019) remains effective against LAC under fixed Hamming-weight sampling, and it improves failure-finding efficiency by identifying the underlying class of bad randomness pairs beyond pattern-based subsets. On the design side, it motivates trimming high-dependency samples during key generation and encryption. We provide a certified trimmed DFR bound based on conditional spectral control and a complementary three-vector heuristic DFR bound with experimental validation for calibrated interpretation. We formalize the resulting approach as generic frameworks TrimPKE and TrimKEM, prove security in the QROM while accounting for rejection, and instantiate them for LAC and DAWN as case studies.

IACR Cryptology ePrint Archive

eprint-revision May 15

#eprint Revision of On the Regularity of the Generalized Birthday Problem by Lili Tang, Yao Sun, Xiaorui Gong (https://ia.cr/2025/1351)

On the Regularity of the Generalized Birthday Problem

The Generalized Birthday Problem ($\textsf{GBP}$), which seeks $k$ hash values from $k$ lists whose XOR is zero, is a fundamental problem across multiple cryptographic domains. While the k-list $\textsf{GBP}$ has been extensively studied, many schemes including $\textsf{Equihash}$ (NDSS'16) utilize a single-list variant (selecting hash values from a single list) without clear theoretical grounding. Our work first reveals that k-list $\textsf{GBP}$ implicitly exhibits a regularity property, a block-wise structure that has been thoroughly studied by Esser and Santini (Crypto'24) in the context of Syndrome Decoding Problem. Such structured regularity can often be leveraged to design efficient protocols and enable new functionalities. In this work, we revisit these two long-conflated $\textsf{GBP}$s and initiate a systematic study of the regularity in $\textsf{GBP}$ realm. $\textbf{Complexity.}$ In the worst-case setting, we develop a novel ISD-based framework for $\textsf{GBP}$. When $k/n > 0.188$ and $k/n > 0.11$ for the regular and non-regular cases, respectively, the proposed algorithms surpass the worst-case complexity of $2^{n/2}$. Through numerical optimization, we heuristically demonstrate that for any constant $k/n > 0$, the advanced ISD algorithms such as BJMM achieve an asymptotic complexity superior to the birthday bound when applied to density-one $\textsf{GBP}$ instances. Our results disprove the average-case to worst-case $k$-$\textsf{XOR}$ conjecture when $k$ is non-constant. In the average-case regime, we fill in theoretical gaps in solving the single-list $\textsf{GBP}$ and show that the regular variant exhibits a $\sqrt{2}$-factor difference in the exponent, which extends naturally to the $k$-$\textsf{SUM}$ problem and offers new insights on its complexity. $\textbf{Implications for Cryptography.}$ We analyze the impact of regularity on incremental hash and propose a new collision attack against the ID-based incremental hash (Eurocrypt'97). Our attack achieves an asymptotic time complexity of $\mathcal{O}(\sqrt{n} \cdot 2^{\sqrt{2n}})$, significantly improving upon the previous Wagner's bound of $\mathcal{O}(2^{\sqrt{4n}})$ (Crypto'02). Applying our attack to $\textsf{iSHAKE256}$, we reduce its security lower bound from $ 2^{256} $ to $ 2^{189} $. In the realm of $\textsf{Equihash}$, the index-pointer technique has significantly weakened its ASIC-resistance. To address this, we propose $\textsf{Requihash}$, a PoW with enhanced ASIC-resistance and smaller solution size, rigorously aligned with the regular $k$-list $\textsf{GBP}$.

IACR Cryptology ePrint Archive