[continued from previous message]

In this paper, we propose a new ZK-friendly hash function, dubbed $\mathsf{Polocolo}$, that employs an S-box constructed using power residues. Our approach reduces the numbers of gates required for table lookups, in particular, when combined with Plonk,
allowing one to use such nonlinear layers over multiple rounds. We also propose a new MDS matrix for the linear layer of $\mathsf{Polocolo}$. In this way, $\mathsf{Polocolo}$ requires fewer Plonk gates compared to the state-of-the-art ZK-friendly hash
functions. For example, when $t = 8$, $\mathsf{Polocolo}$ requires $21\%$ less Plonk gates compared to Anemoi, which is currently the most efficient ZK-friendly hash function, where $t$ denotes the size of the underlying permutation in blocks of $\mathbb
F_p$. For $t = 3$, $\mathsf{Polocolo}$ requires $24\%$ less Plonk gates than Reinforced Concrete, which is one of the recent lookup-based ZK-friendly hash functions.



## 2025/927

* Title: Enhancing Meme Token Market Transparency: A Multi-Dimensional Entity-Linked Address Analysis for Liquidity Risk Evaluation
* Authors: Qiangqiang Liu, Qian Huang, Frank Fan, Haishan Wu, Xueyan Tang
* [Permalink](https://eprint.iacr.org/2025/927)
* [Download](https://eprint.iacr.org/2025/927.pdf)

### Abstract

Meme tokens represent a distinctive asset class within the cryptocurrency ecosystem, characterized by high community engagement, significant market volatility, and heightened vulnerability to market manipulation. This paper introduces an innovative
approach to assessing liquidity risk in meme token markets using entity-linked address identification techniques. We propose a multi-dimensional method integrating fund flow analysis, behavioral similarity, and anomalous transaction detection to identify
related addresses. We develop a comprehensive set of liquidity risk indicators tailored for meme tokens, covering token distribution, trading activity, and liquidity metrics. Empirical analysis of tokens like BabyBonk, NMT, and BonkFork validates our
approach, revealing significant disparities between apparent and actual liquidity in meme token markets. The findings of this study provide significant empirical evidence for market participants and regulatory authorities, laying a theoretical foundation
for building a more transparent and robust meme token ecosystem.



## 2025/928

* Title: HAWK: Having Automorphisms Weakens Key
* Authors: Daniël M. H. van Gent, Ludo N. Pulles
* [Permalink](https://eprint.iacr.org/2025/928)
* [Download](https://eprint.iacr.org/2025/928.pdf)

### Abstract

The search rank-2 module Lattice Isomorphism Problem (smLIP), over a cyclotomic ring of degree a power of two, can be reduced to an instance of the Lattice Isomorphism Problem (LIP) of at most half the rank if an adversary knows a nontrivial automorphism
of the underlying integer lattice. Knowledge of such a nontrivial automorphism speeds up the key recovery attack on HAWK at least quadratically, which would halve the number of security bits.

Luo et al. (ASIACRYPT 2024) recently found an automorphism that breaks omSVP, the initial underlying hardness assumption of HAWK. The team of HAWK amended the definition of omSVP to include this so-called symplectic automorphism in their submission to
the second round of NIST's standardization of additional signatures. This work provides confidence in the soundness of this updated definition, assuming smLIP is hard, since there are plausibly no more trivial automorphisms that allow winning the omSVP
game easily.

Although this work does not affect the security of HAWK, it opens up a new attack avenue involving the automorphism group that may be theoretically interesting on its own.



## 2025/929

* Title: The DROP Protocol: Dispute Resolution via Observation in Public for Verifiable, In-Person Voting
* Authors: Josh Benaloh, Michael Naehrig, Olivier Pereira
* [Permalink](https://eprint.iacr.org/2025/929)
* [Download](https://eprint.iacr.org/2025/929.pdf)

### Abstract

Dispute resolution has been a significant challenge in verifiable election protocols since such protocols were first proposed more than forty years ago. This work explores the problem from a new perspective and offers strong dispute resolution for in-
person voting by depending on observers.

It proposes a simple definition of dispute resolution as a property of a voting protocol---a definition that is independent of any other security goal. It also presents the DROP protocol, a verifiable, in-person voting protocol that runs in the presence
of observers who will always reach a correct conclusion in the case of a dispute without ever being able to compromise privacy or facilitate coercion.



## 2025/930

* Title: SEEC: Memory Safety Meets Efficiency in Secure Two-Party Computation
* Authors: Henri Dohmen, Robin Hundt, Nora Khayata, Thomas Schneider
* [Permalink](https://eprint.iacr.org/2025/930)
* [Download](https://eprint.iacr.org/2025/930.pdf)

### Abstract

Secure Multi-Party Computation (MPC) allows multiple parties to perform privacy-preserving computation on their secret data. MPC protocols based on secret sharing have high throughput which makes them well-suited for batch processing, where multiple
instances are evaluated in parallel.
So far, practical implementations of secret sharing-based MPC protocols mainly focus on runtime and communication efficiency, so the memory overhead of protocol implementations is often overlooked. Established techniques to reduce the memory overhead for
constant-round garbled circuit protocols cannot be directly applied to secret sharing-based protocols because they would increase the round complexity. Additionally, state-of-the-art implementations of secret sharing-based MPC protocols are implemented
in C/C++ and may exhibit memory unsafety and memory leaks, which could lead to undefined behavior.

In this paper, we present SEEC: SEEC Executes Enormous Circuits, a framework for secret sharing-based MPC
with a novel approach to address memory efficiency and safety without compromising on runtime and communication efficiency. We realize SEEC in Rust, a language known for memory-safety at close-to-native speed. To reduce the memory footprint, we develop
an in-memory representation for sub-circuits. Thus, we never inline sub-circuit calls during circuit evaluation, a common issue that blows up memory usage in MPC implementations.
We compare SEEC with the state-of-the-art secret sharing-based MPC frameworks ABY (NDSS'15), MP-SPDZ (CCS'20), and MOTION (TOPS'22) w.r.t. runtime, memory, and communication efficiency. Our results show that our reliable and memory-safe implementation
has competitive or even better performance.



## 2025/931

* Title: Multivalued Broadcast with Optimal Length
* Authors: Gabriel Dettling, Martin Hirt, Chen-Da Liu-Zhang
* [Permalink](https://eprint.iacr.org/2025/931)
* [Download](https://eprint.iacr.org/2025/931.pdf)

### Abstract

A multi-valued broadcast protocol allows a sender $P_s$ to broadcast an $\ell$-bit message $m$ to $n$ recipients.
For all relevant models, multi-valued broadcast protocols with asymptotically optimal communication complexity $\mathcal{O}(\ell n)+\mathrm{Poly}(n)$ have been published.

Despite their very low communication complexity, these protocols perform poorly in modern networks.
Even if the network allows all $n$ parties to send messages at the same time, the execution time of the protocols is proportional to $\ell n$ (instead of $\ell$).
Even if the network allows to use all bilateral channels at the same time, the execution time is still proportional to $\ell$ (instead of $\ell/n$).

We ask the natural question whether multi-valued broadcast protocols exist which take time proportional to $\ell$ if parties can simultaneously send messages, and even take time proportional to $\ell/n$ if the bilateral channels can be used
simultaneously. We provide a complete characterization of multi-valued broadcast with a two-fold answer:

On the negative side, we prove that for $t<n$, multi-valued broadcast requires time proportional to $\ell n$, if parties can simultaneously send messages, respectively take time proportional to $\ell$ if bilateral channels can be used simultaneously.

On the positive side, we prove that for $t < (1-\epsilon)n$ (for any fixed $\epsilon$), multi-valued broadcast in time proportional to $\ell$ (when parties can send messages simultaneously), respectively proportional to $\ell/n$ (if bilateral channels
can be used simultaneously) is possible. We provide such protocols both with cryptographic security as well as with statistical security.



## 2025/932

* Title: Integral cryptanalysis in characteristic $p$
* Authors: Tim Beyne, Michiel Verbauwhede
* [Permalink](https://eprint.iacr.org/2025/932)
* [Download](https://eprint.iacr.org/2025/932.pdf)

### Abstract

Integral and ultrametric integral cryptanalysis are generalized to finite rings of prime characteristic $p$ that are isomorphic to a product of fields. This extends, for instance, the complete state of the art in integral cryptanalysis from $\mathbf{F}_2^
n$ to $\mathbf{F}_q^n$, for all prime powers $q$. A compact representation of transition matrices, based on convex polyhedra, is introduced to ensure that the proposed methods are computationally efficient even for large $p$.
Automated tools are developed and applied to a few generic and several concrete primitives. The analysis shows that previous degree estimates for Feistel-GMiMC, HadesMiMC, AES-Prime, small-pSquare and mid-pSquare are overly optimistic. Furthermore,
except for AES-Prime, these primitives do not meet their design criteria unless their number of rounds is substantially increased.



## 2025/933

* Title: Fast elliptic curve scalar multiplications in SN(T)ARK circuits
* Authors: Liam Eagen, Youssef El Housni, Simon Masson, Thomas Piellard
* [Permalink](https://eprint.iacr.org/2025/933)
* [Download](https://eprint.iacr.org/2025/933.pdf)

### Abstract

Proof systems of arbitrary computations have found many applications in recent years. However, the proving algorithm has a consequent complexity tied to the size of the computation being proved. Thus, proving large computations is quite inefficient. One
of these large computations is the scalar multiplication over an elliptic curve. In this work, we provide new techniques for reducing the time corresponding to proving a scalar multiplication, using integer lattice reduction or a (half) extended
Euclidean algorithm in a ring of integers. We investigate optimizations in the case of small (complex multiplication) discriminant curves, and its generalization for multi scalar multiplications as used in signature verification. We provide an optimized
Golang implementation for different elliptic curves in different proof systems settings. The speed-up in proving time is between 22% and 53% compared to the previous state-of-the-art.



## 2025/934

* Title: Diving Deep Into UC: Uncovering and Resolving Issues in Universal Composability
* Authors: Céline Chevalier, Éric Sageloli
* [Permalink](https://eprint.iacr.org/2025/934)
* [Download](https://eprint.iacr.org/2025/934.pdf)

### Abstract

Introduced by Canetti in 2001, Universal Composability (UC) is a widely adopted security model that enables the specification and proof of security for a broad range of protocols, offering strong security guarantees.
At its core lies the universal composition theorem (UC theorem), which ensures that protocols proven secure within the framework remain secure even when deployed in real-world environments with multiple instances of them.

In this work, we present two key contributions. First, we identify several problems with the UC framework, in particular the UC Theorem. They include counterexamples, limitations that make it unusable for important classes of protocols, and weaknesses in
its proof. These problems reveal flaws in nearly all the fundamental concepts of UC.

Secondly, we update the main concepts of UC to address these problems. Although these revisions are nontrivial, our updated definitions are intended to stay as closely aligned with the original model as possible, while providing greater simplicity
overall. To ensure the validity of these updates, we present a proof of the updated UC theorem, which is more detailed and modular than the original.



## 2025/935

* Title: Side-channel safe conditional moves and swaps
* Authors: David Santos, Michael Scott
* [Permalink](https://eprint.iacr.org/2025/935)
* [Download](https://eprint.iacr.org/2025/935.pdf)

### Abstract

Constant-time implementations are a cornerstone of secure
cryptographic systems, particularly in the context of key exchange protocols and digital signature schemes. These implementations are designed to eliminate timing side-channel vulnerabilities by ensuring that the program’s execution time is independent
of secret data. A fundamental building block for achieving constant-time behavior is the conditional move operation. Unlike traditional branching constructs (such as if statements), which may introduce data-dependent timing variations, conditional moves
allow developers to write logic that behaves identically at the hardware level regardless of input values. As a result, they are widely used in cryptographic libraries and standards to ensure both functional correctness and resistance to timing attacks.
In this work, we describe our efforts to implement elliptic curve cryptography with some immunity against certain power leakage side-channel attacks, using standard C and Rust code.



## 2025/936

* Title: Justvengers: Batched VOLE ZK Disjunctions in $\mathcal{O}(R{+}B{+}C)$ Communication
* Authors: Yibin Yang
* [Permalink](https://eprint.iacr.org/2025/936)
* [Download](https://eprint.iacr.org/2025/936.pdf)

### Abstract

Recent progress on zero-knowledge proofs (ZKPs) based on vector oblivious linear evaluation (VOLE) offers a promising paradigm for scaling ZKPs over extremely large statements. In particular, VOLE-based ZK is currently the best choice in terms of end-to-
end execution time. However, VOLE-based ZK incurs high communication overhead — it usually scales linearly with the circuit size.

To mitigate this, existing literature considers VOLE-based ZK over structured statements. In this work, we focus on the batched disjunctive statement — $\mathcal{P}$ and $\mathcal{V}$ agree on $B$ fan-in $2$ circuits $\mathcal{C}_1, \ldots, \mathcal{C}_
{B}$ over a field $\mathbb{F}$; each circuit is of size $C$ with $n_{\mathit{in}}$ inputs. $\mathcal{P}$'s goal is to demonstrate the knowledge of $R$ witnesses $(\mathit{id}_j \in [B]$, $\boldsymbol{w}_j \in \mathbb{F}^{n_{\mathit{in}}})$ for each $j \
in [R]$ s.t. $\forall j \in [R], \mathcal{C}_{\mathit{id}_j}(\boldsymbol{w}_j) = 0$ where neither $\boldsymbol{w}_j$ nor $\mathit{id}_j$ is revealed. Batched disjunctive statements are effective, e.g., in emulating the CPU execution inside ZK. Note, the
naïve solution results in a circuit of size $\mathcal{O}(RBC)$.

To prove such a statement using VOLE-based ZK, the prior state-of-the-art protocol $\mathsf{Antman}$ (Weng et al., CCS'22) incurred $\mathcal{O}(BC + R)$ communication by additionally relying on AHE, whereas $\mathsf{Batchman}$ (Yang et al., CCS'23)
achieved $\mathcal{O}(RC + B)$ communication using only VOLE.

In this work, we combine these two protocols non-trivially and present a novel protocol $\mathsf{Justvengers}$ — targeting the batched disjunctive statement — that incurs only $\mathcal{O}(R + B + C)$ communication and $\mathcal{O}(BC + (B + C)R\log
R)$ computation for prover, using AHE and VOLE.



## 2025/937

* Title: Attacking Poseidon via Graeffe-Based Root-Finding over NTT-Friendly Fields
* Authors: Antonio Sanso, Giuseppe Vitto
* [Permalink](https://eprint.iacr.org/2025/937)
* [Download](https://eprint.iacr.org/2025/937.pdf)

### Abstract

This paper explores the algebraic structure of the Poseidon and Poseidon2 permutations
over NTT-friendly finite fields, with a focus on preimage recovery via root-finding
techniques. We introduce an algorithm for efficiently identifying single roots of high-degree
univariate polynomials that emerge from these constructions, based on the Graeffe transform
and the tangent Graeffe method. Our approach is evaluated on reduced-round bounty
instances of these permutations at various security levels, as proposed by the Ethereum
Foundation, demonstrating practical effectiveness. These results yield new insights into the
security of permutation-based cryptographic primitives instantiated over NTT-friendly prime
fields.



## 2025/938

* Title: PSYLOCKE: Provably Secure Logic Locking with Practical Efficiency
* Authors: Yohei Watanabe, Kyoichi Asano, Haruka Hirata, Tomoki Ono, Mingyu Yang, Mitsugu Iwamoto, Yang Li, Yuko Hara
* [Permalink](https://eprint.iacr.org/2025/938)
* [Download](https://eprint.iacr.org/2025/938.pdf)

### Abstract

Logic locking is an obfuscation technique designed to protect the intellectual property of hardware designs and has attracted considerable attention for over a decade. However, most logic locking schemes have been developed heuristically, leading the
field into a cat-and-mouse game between attackers and defenders. Indeed, several proposed schemes have already been broken. While recent works have introduced provably secure logic locking, they often incur impractical overhead or fail to support the
ASIC design paradigm while offering strong theoretical security guarantees.

In this work, we propose PSYLOCKE, a provably secure and practically efficient logic locking scheme that balances formal security guarantees with implementation feasibility. We introduce a new security paradigm that formalizes logic locking under
predetermined allowable leakage, such as circuit topology, and we provide refined definitions of resilience against specific attacks. Our analysis bridges general security definitions and attack resilience, quantifying how leakage impacts the success of
real-world attacks. PSYLOCKE is provably secure under topology leakage and achieves significant efficiency improvement compared to existing provably secure logic locking schemes. Alongside our theoretical analysis, we demonstrate through quantitative
evaluations using widely-used benchmark circuits that PSYLOCKE strikes a favorable balance between practical performance and security. Concretely, PSYLOCKE reduced the Area-Power-Delay overhead by an order of magnitude while achieving the same security
level, compared to the existing provably secure logic locking scheme.



## 2025/939

* Title: On the security of one certificateless aggregate signature scheme with dynamic revocation in vehicular ad-hoc networks
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2025/939)
* [Download](https://eprint.iacr.org/2025/939.pdf)

### Abstract

We show that the certificateless signature scheme [Veh. Commun. 47: 100763 (2024)] is insecure, because an adversary can launch forgery attack for any message. The signer's certificateless public key is not tightly bound to the system public key. The
inherent flaw results in that the adversary can find an efficient signing algorithm functionally equivalent to the valid signing algorithm. The findings in this note could be helpful for newcomers who are not familiar with the designing techniques for
certificateless signatures.



## 2025/940

* Title: Special Genera of Hermitian Lattices and Applications to HAWK
* Authors: Guilhem Mureau
* [Permalink](https://eprint.iacr.org/2025/940)
* [Download](https://eprint.iacr.org/2025/940.pdf)

### Abstract

In its decisional form, the module-Lattice Isomorphism Problem (decision module-LIP) has received first attention in a paper by Ling, Liu and Mendelsohn. The authors gave a polynomial-time algorithm to distinguish spinor genera within the genus of a
quadratic binary $\mathcal{O}_F$-lattice, assuming that $\mathcal{O}_F$ is a principal ideal domain. However, this algorithm would not impact cryptographic schemes based on decision module-LIP for lattices such as those employed in HAWK, i.e., for binary
$\mathcal{O}_K$-lattices equipped with an Hermitian form (with $K$ a cyclotomic number field). Motivated by HAWK's framework, we investigate a concept that serves as an analogue of the spinor genus for Hermitian lattices, called special genus. This
notion was studied by Shimura who provided a complete set of invariants for describing special genera. Building on this result, we propose an algorithm to determine whether two Hermitian lattices belong to the same special genus. Specifically for HAWK's
lattice and sibblings, our algorithm runs in classical polynomial-time. Nevertheless we provide numerical evidence suggesting that the ability to distinguish special genera does not, in practice, constitute a significative advantage for solving decision
module-LIP.



## 2025/941

* Title: Proof of Exponentiation: Enhanced Prover Efficiency for Algebraic Statements
* Authors: Zhuo Wu, Shi Qi, Xinxuan Zhang, Yi Deng, Kun Lai, Hailong Wang
* [Permalink](https://eprint.iacr.org/2025/941)
* [Download](https://eprint.iacr.org/2025/941.pdf)

### Abstract

Recent years have seen the widespread adoption of zkSNARKs constructed over small fields, including but not limited to, the Goldilocks field, small Mersenne prime fields, and tower of binary fields. Their appeal stems primarily from their efficacy in
proving computations with small bit widths, which facilitates efficient proving of general computations and offers significant advantages, notably yielding remarkably fast proving efficiency for tasks such as proof of knowledge of hash preimages.
Nevertheless, employing these SNARKs to prove algebraic statements (e.g., RSA, ECDSA signature verification) presents efficiency challenges.

To address this problem, we first define a new circuit model: arithmetic circuits with additional \textit{exponentiation gates}. These gates serve as fundamental building blocks for establishing more intricate algebraic relations. Then we present a \
textit{Hash-committed Commit-and-Prove (HCP)} framework to construct Non-interactive Zero-knowledge (NIZK) proofs for the satisfiability of these circuits. Specifically, when proving knowledge of group exponentiations in discrete logarithm hard groups
and RSA groups, compared to verifying complex group exponentiations within SNARK circuits, our approach requires proving only more lightweight computations within the SNARK, such as zk-friendly hash functions (e.g., Poseidon hash function). The number of
these lightweight computations depends solely on the security parameter. This differentiation leads to substantial speedups for the prover relative to direct SNARK methods, while maintaining competitive proof size and verification cost.



## 2025/942

* Title: On the (in)security of Proofs-of-Space based Longest-Chain Blockchains * Authors: Mirza Ahad Baig, Krzysztof Pietrzak
* [Permalink](https://eprint.iacr.org/2025/942)
* [Download](https://eprint.iacr.org/2025/942.pdf)

### Abstract

The Nakamoto consensus protocol underlying the Bitcoin blockchain uses proof of work as a voting mechanism. Honest miners who contribute hashing power towards securing the chain try to extend the longest chain they are aware of. Despite its simplicity,
Nakamoto consensus achieves meaningful security guarantees assuming that at any point in time, a majority of the hashing power is controlled by honest parties. This also holds under ``resource variability'', i.e., if the total hashing power varies
greatly over time.

Proofs of space (PoSpace) have been suggested as a more sustainable replacement for proofs of work. Unfortunately, no construction of a ``longest-chain'' blockchain based on PoSpace, that is secure under dynamic availability, is known. In this work, we
prove that without additional assumptions no such protocol exists. We exactly quantify this impossibility result by proving a bound on the length of the fork required for double spending as a function of the adversarial capabilities. This bound holds for
any chain selection rule, and we also show a chain selection rule (albeit a very strange one) that almost matches this bound.

Concretely, we consider a security game in which the honest parties at any point control $\phi>1$ times more space than the adversary. The adversary can change the honest space by a factor $1\pm \varepsilon$ with every block (dynamic availability), and ``
replotting'' the space (which allows answering two challenges using the same space) takes as much time as $\rho$ blocks.

We prove that no matter what chain selection rule is used, in this game the adversary can create a fork of length $\phi^2\cdot \rho / \varepsilon$ that will be picked as the winner by the chain selection rule.

We also provide an upper bound that matches the lower bound up to a factor $\phi$. There exists a chain selection rule (albeit a very strange one) which in the above game requires forks of length at least $\phi\cdot \rho / \varepsilon$.



Our results show the necessity of additional assumptions to create a secure PoSpace based longest-chain blockchain. The Chia network in addition to PoSpace uses a verifiable delay function.
Our bounds show that an additional primitive like that is necessary.



## 2025/943

* Title: On the Adaptive Security of Key-Unique Threshold Signatures
* Authors: Elizabeth Crites, Chelsea Komlo, Mary Maller
* [Permalink](https://eprint.iacr.org/2025/943)
* [Download](https://eprint.iacr.org/2025/943.pdf)

### Abstract

In this work, we investigate the security assumptions required to prove the adaptive security of threshold signatures. Adaptive security is a strong notion of security that allows an adversary to corrupt parties at any point during the execution of the
protocol, and is of practical interest due to recent standardization efforts for threshold schemes. Towards this end, we give two different impossibility results.

We begin by formalizing the notion of a key-unique threshold signature scheme, where public keys have a unique correspondence to secret keys and there is an efficient algorithm for checking that public keys are well-formed. Key-uniqueness occurs in many
threshold schemes that are compatible with standard, single-party signatures used in practice, such as BLS, ECDSA, and Schnorr signatures.

Our first impossibility result demonstrates that it is impossible to prove the adaptive security of any key-unique threshold signature scheme under any non-interactive computational assumption for a broad class of reductions, in the range $⌊t/2⌋< t_c
≤ t$, where $n$ is the total number of parties, $t_c$ is the number of corrupted parties, and $t+ 1$ is the threshold. We begin by ruling out full adaptive security (i.e., $t_c = t$ corruptions) for key-unique threshold signatures under non-interactive
computational assumptions, including, but not limited to, the discrete logarithm (DL), computational Diffie-Hellman (CDH), and q-Strong Diffie-Hellman (q-SDH) assumptions. We then generalize this impossibility result for all $t_c$ such that $⌊t/2⌋< t_
c ≤ t$.

Our second impossibility result applies specifically to key-unique threshold Schnorr signatures, currently an active area of research. We demonstrate that, even under the interactive computational assumptions One-More Discrete Logarithm (OMDL) and
Algebraic OMDL (AOMDL), it is impossible to prove adaptive security for $⌊t/2⌋< t_c ≤ t$ in the programmable ROM with rewinding.

Taken together, our results underscore the difficulty of achieving adaptive security for key-unique threshold signatures. However, we believe this work can open a new line of research, by indicating assumptions and properties to aim for when constructing
adaptively secure threshold schemes.



## 2025/944

* Title: Succinct Witness Encryption for Batch Languages and Applications
* Authors: Lalita Devadas, Abhishek Jain, Brent Waters, David J. Wu
* [Permalink](https://eprint.iacr.org/2025/944)
* [Download](https://eprint.iacr.org/2025/944.pdf)

### Abstract

Witness encryption allows one to encrypt a message to an $\mathsf{NP}$ relation $\mathcal{R}$ and a statement $x$. The corresponding decryption key is any valid $\mathsf{NP}$ witness $w$. In a succinct witness encryption scheme, we require that the size
of the ciphertext be sublinear in the size of the $\mathsf{NP}$ relation. Currently, all realizations of succinct witness encryption for $\mathsf{NP}$ rely on strong assumptions such as pseudorandom obfuscation, extractable witness encryption, or
differing-inputs obfuscation. Notably, none of these notions are known from standard assumptions.

In this work, we consider a relaxation of succinct witness encryption for $\mathsf{NP}$ to the setting of batch $\mathsf{NP}$. In this setting, one encrypts to an $\mathsf{NP}$ relation $\mathcal{R}$ together with $K$ statements $x_1, \ldots, x_K$. In
the basic version, one can decrypt if they have a witness $w_1, \ldots, w_K$ for all $K$ statements. The succinctness requirement is that the size of the ciphertext should be sublinear in the number of instances $K$, but is allowed to grow with the size
of the $\mathsf{NP}$ relation (i.e., the size of a single instance). More generally, we can also impose a (monotone) policy $P \colon \{0,1\}^K \to \{0,1\}$ over the $K$ instances. In this case, decryption is possible only if there exists $w_1, \ldots, w_
K$ such that $P(\mathcal{R}(x_1, w_1), \ldots, \mathcal{R}(x_K, w_K)) = 1$.

In this work, we initiate a systematic study of succinct witness encryption for batch languages. We start with two simple constructions that support CNF and DNF policies based on plain witness encryption in conjunction with a somewhere statistically
sound batch argument for $\mathsf{NP}$ or a function-binding hash function. Then, using indistinguishability obfuscation, we show how to support policies that can be computed by read-once bounded-space Turing machines. The latter construction is in fact
a unique witness map for monotone-policy batch $\mathsf{NP}$, and as such, also gives a SNARG for monotone-policy batch $\mathsf{NP}$ where the size of the common reference string is sublinear in the number of instances.

Finally, we demonstrate some immediate applications of succinct witness encryption for batch languages. We construct new succinct computational secret sharing schemes for CNFs, DNFs, and weighted threshold policies. We also show how to build distributed
monotone-policy encryption, a notion that generalizes recent trustless primitives like distributed broadcast encryption and threshold encryption with silent setup.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)