[continued from previous message]

Tracing techniques have been used to identify users who have leaked their decryption keys in a secure multi-receiver encryption system. Very recently, in the field of distributed cryptography, where trust is distributed, Boneh et al. extended traitor
tracing to the framework of threshold decryption, where a single user doesn't hold the whole secret to decrypt but needs to collaborate with others. However, the tracing capacity in their collusion-secure codes-based schemes is still centralized: only
the authority holding the secret tracing key can perform tracing. We continue in the direction of not relying on a single entity and propose decentralizing tracing in this context so that the tracing procedure does not need to rely on any secret key and
can be done by anyone. Technically, as binary collusion-secure codes only support secret tracing, we switch to robust $q$-ary IPP codes supporting public tracing. This requires us to generalize the bipartite threshold KEM for two users in Boneh et al.'s
paper to $q$-partite KEM for q users. In terms of security, their static one-sided security in the binary case is not appropriate, which requires us to define an adaptive one-sided security notion for $q$-partite KEM to be compatible with $q$-ary IPP
codes. Finally, we generalize the Boneh et al. construction to achieve this security notion and achieve public traceability for threshold decryption without degrading efficiency.



## 2025/1348

* Title: The CRO Trilemma : a formal incompatibility between Confidentiality, Reliability and legal Opposability in Post-Quantum proof systems
* Authors: Thierry Emmanuel MINKA MI NGUIDJOI, MANI ONANA Flavien Serge, DJOTIO NDIÉ Thomas
* [Permalink](https://eprint.iacr.org/2025/1348)
* [Download](https://eprint.iacr.org/2025/1348.pdf)

### Abstract

This work establishes the CRO Trilemma: no post-quantum proof system can simultaneously satisfy the following three properties beyond negligible failure probability: (i) Confidentiality, quantified by Priv > 1 - negl(lambda); (ii) Reliability, with Rel >
1 - negl(lambda); and (iii) Legal Opposability, measured by contextual entropy H_Opp ≈ log |V_J|, where V_J denotes the validation space of a polynomial-time institutional verifier J.

The result formalizes the Invisible Authenticity Paradox through contextual entropy H(C) and quantum interpretability loss eta_q(C). Under standard quantum assumptions, we prove the following impossibility bound against QPT adversaries:

H_Opp <= (Priv * Rel) / (epsilon_eff * 2^H(C)) + eta_q(C) + negl(lambda)

A composable framework is introduced, including a composable model with verifier J (Algorithm 1), and an optimal entropy decomposition theorem (Theorem 2.3). Theoretical predictions are supported by empirical evidence indicating consistent violation of
the bound (Gamma_CRO > 0.8) across NIST PQC finalists (e.g., Dilithium) and structured ZKPs (e.g., STARKs, Groth16).



## 2025/1349

* Title: $\mathsf{HyperFond}$: A Transparent and Post-Quantum Distributed SNARK with Polylogarithmic Communication
* Authors: Yuanzhuo Yu, Mengling Liu, Yuncong Zhang, Shi-Feng Sun, Tianyi Ma, Man Ho Au, Dawu Gu
* [Permalink](https://eprint.iacr.org/2025/1349)
* [Download](https://eprint.iacr.org/2025/1349.pdf)

### Abstract

Recent years have witnessed the surge of academic researches and industrial implementations of succinct non-interactive arguments of knowledge (SNARKs). However, proving time remains a bottleneck for applying SNARKs to large-scale circuits. To accelerate
the proof generation process, a promising way is to distribute the workload to several machines running in parallel, the SNARKs with which feature are called distributed SNARKs. Nevertheless, most existing works either require a trusted setup, or rely on
quantum-insecure assumptions, or suffer from linear communication costs.

In this paper, we introduce $\mathsf{HyperFond}$, the first distributed SNARK that enjoys a transparent setup, post-quantum security and polylogarithmic communication cost, as well as the field-agnostic property (no reliance on specific choices of fields)
. To this end, we first propose a distributed proof system based on HyperPlonk (by Chen et al. in EUROCRYPT 2023). To instantiate the system, we then put forward a novel approach to distribute the multilinear polynomial commitment scheme in BaseFold (by
Zeilberger et al. in CRYPTO 2024), and also present a trade-off between communication cost and proof size. In $\mathsf{HyperFond}$, after committing to polynomial coefficients with quasilinear complexity, each sub-prover generates proofs with time linear
in subcircuit size.

We implement $\mathsf{HyperFond}$ using up to 16 machines. Experimental results demonstrate that the proving time of $\mathsf{HyperFond}$ is 14.3 $\times$ faster than HyperPlonk instantiated with BaseFold. We also compare to deVirgo (by Xie et al. in CCS
2022), so far the only post-quantum distributed SNARK, and achieve a 1.89 $\times$ speedup.



## 2025/1350

* Title: Rhyme: A Fiat-Shamir Lattice-based Signature with 3C Sampling
* Authors: Zhongxiang Zheng, Anyu Wang, Chunhuan Zhao, Guangwu Xu, Zhengtao Jiang, Sibo Feng, Zhichen Yan, Shuang Sun, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2025/1350)
* [Download](https://eprint.iacr.org/2025/1350.pdf)

### Abstract

In this paper, we propose a new postquantum lattice-based digital signature named Rhyme. The scheme is based on the Fiat-Shamir structure and does not rely on flooding, rejection sampling, or Gaussian convolution as previous methods. Instead, its
security is based on a variant of LWE combined with a new sampling method (3C sampling). We prove its security in ROM/QROM and provide concrete parameters as well as reference implementation to show that our scheme enjoys high efficiency and very compact
signature size compared with former results.



## 2025/1351

* Title: Revisiting the Generalized Birthday Problem and Equihash: Single or K Lists?
* Authors: Lili Tang, Yao Sun, Xiaorui Gong
* [Permalink](https://eprint.iacr.org/2025/1351)
* [Download](https://eprint.iacr.org/2025/1351.pdf)

### Abstract

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. Wagner's \(k\)-list algorithm (Crypto'02) for $\textsf{GBP}$ has advanced the
optimization of solving the syndrome decoding problem and established new cryptanalytic benchmarks for incremental cryptography and blind signatures. $\textsf{Equihash}$ (NDSS'16) underscores the critical advantages of $\textsf{GBP}$ in proof-of-work
design, particularly its ASIC-resistance in blockchain. While the k-list $\textsf{GBP}$ has been extensively studied, many schemes including $\textsf{Equihash}$ utilize a single-list variant (selecting hash values from a single list) without clear
theoretical grounding. In this work, we revisit these two long-conflated problems and fill in theoretical gaps in solving the single-list $\textsf{GBP}$.

In the realm of $\textsf{Equihash}$, the index-pointer technique has significantly weakened its ASIC-resistance. Our trade-off optimization to Wagner's algorithmic framework further diminishes this resistance by reducing peak memory by at least 50%
across most $\textsf{Equihash}$ parameters. To address this, we propose $\textsf{Sequihash}$, a PoW with enhanced ASIC-resistance, rigorously aligned with the $k$-list $\textsf{GBP}$. Furthermore, we explore the implications of $\textsf{GBP}$ in the
field of incremental hash and propose a new collision attack on 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}})$. Applying our attack to $\textsf{iSHAKE256}$, we reduce its security lower bound from \( 2^{256} \) to \( 2^{189} \).



## 2025/1352

* Title: InsPIRe: Communication-Efficient PIR with Silent Preprocessing
* Authors: Rasoul Akhavan Mahdavi, Sarvar Patel, Joon Young Seo, Kevin Yeo
* [Permalink](https://eprint.iacr.org/2025/1352)
* [Download](https://eprint.iacr.org/2025/1352.pdf)

### Abstract

We present InsPIRe that is the first private information retrieval (PIR) construction simultaneously obtaining both high-throughput and low query communication while using silent preprocessing (meaning no offline communication).
Prior PIR schemes with both high-throughput and low query communication required substantial offline communication of either downloading a database hint that is 10-100x larger than the communication cost of a single query (such as SimplePIR and DoublePIR
[Henzinger et al., USENIX Security 2023]) or streaming the entire database (such as Piano [Zhou et al., S&P 2024]).
In contrast, recent works such as YPIR [Menon and Wu, USENIX Security 2024] avoid offline communication at the cost of increasing the query size by 1.8-2x, up to 1-2 MB per query.
Our new PIR protocol, InsPIRe, obtains the best of both worlds by obtaining high-throughput and low communication without requiring any offline communication.
Compared to YPIR, InsPIRe requires 5x smaller cryptographic keys, requires up to 50% less online query communication while obtaining up to 25% higher throughput.
We show that InsPIRe enables improvements across a wide
range of applications and database shapes including the InterPlanetary File System and private device enrollment.

At the core of InsPIRe, we develop a novel ring packing algorithm, InspiRING, for transforming LWE ciphertexts into RLWE ciphertexts.
InspiRING is more amenable to the silent preprocessing setting that allows moving the majority of the necessary operations to offline preprocessing. InspiRING only requires two key-switching matrices whereas prior approaches needed logarithmic key-
switching matrices.
We also show that InspiRING has smaller noise growth and faster packing times than prior works in the setting when the total key-switching material sizes must be small.
To further reduce communication costs in the PIR protocol, InsPIRe performs the second level of PIR using homomorphic polynomial evaluation, which only requires one additional ciphertext from the client.



## 2025/1353

* Title: Introducing two ROS attack variants: breaking one-more unforgeability of BZ blind signatures
* Authors: Bruno M. F. Ricardo, Lucas C. Cardoso, Leonardo T. Kimura, Paulo S. Barreto, Marcos A. Simplicio Jr
* [Permalink](https://eprint.iacr.org/2025/1353)
* [Download](https://eprint.iacr.org/2025/1353.pdf)

### Abstract

In 2023, Barreto and Zanon proposed a three-round Schnorr-like blind signature scheme, leveraging zero-knowledge proofs to produce one-time signatures as an intermediate step of the protocol. The resulting scheme, called BZ, is proven secure in the
discrete-logarithm setting under the one-more discrete logarithm assumption with (allegedly) resistance to the Random inhomogeneities in a Overdetermined Solvable system of linear equations modulo a prime number $p$ attack, commonly referred to as ROS
attack. The authors argue that the scheme is resistant against a ROS-based attack by building an adversary whose success depends on extracting the discrete logarithm of the intermediate signing key. In this paper, however, we describe a distinct ROS
attack on the BZ scheme, in which a probabilistic polynomial-time attacker can bypass the zero-knowledge proof step to break the one-more unforgeability of the scheme. We also built a BZ variant that, by using one secure hash function instead of two, can
prevent this particular attack. Unfortunately, though, we show yet another ROS attack that leverages the BZ scheme's structure to break the one-more unforgeability principle again, thus revealing that this variant is also vulnerable. These results
indicate that, like other Schnorr-based strategies, it is hard to build a secure blind signature scheme using BZ's underlying structure.



## 2025/1354

* Title: Shred-to-Shine Metamorphosis in Polynomial Commitment Evolution
* Authors: Weihan Li, Zongyang Zhang, Sherman S. M. Chow, Yanpei Guo, Boyuan Gao, Xuyang Song, Yi Deng, Jianwei Liu
* [Permalink](https://eprint.iacr.org/2025/1354)
* [Download](https://eprint.iacr.org/2025/1354.pdf)

### Abstract

Polynomial commitment schemes (PCSs) enable verifying evaluations of committed polynomials. Multilinear (ML) PCSs from linear codes are favored for their prover time. Distributed MLPCSs further reduce it by enabling multiple provers to distribute both
commitment and proof generation.

We propose $\mathsf{PIP}_\mathsf{FRI}$, an FRI-based MLPCS that unites the linear prover time of PCSs from encodable codes with the compact proofs and fast verification of Reed–Solomon (RS) PCSs. By cutting FFT and hash overhead for both committing and
opening, $\mathsf{PIP}_\mathsf{FRI}$ runs $10\times$ faster in prover than the RS-based DeepFold (Usenix Security'25) while retaining competitive proof size and verifier time, and beats Orion (Crypto'22) from linear codes by $3.5$-fold in prover speed
while reducing proof size and verification time by $15$-fold.

Its distributed version $\mathsf{DePIP}_\mathsf{FRI}$ delivers the first code-based distributed SNARK for arbitrary circuits over a single polynomial, and further achieves accountability. $\mathsf{DePIP}_\mathsf{FRI}$ outperforms DeVirgo (CCS'22)---the
only prior code-based distributed MLPCS, limited to data-parallel circuits and lacking accountability---by $25\times$ in prover time and $7\times$ in communication, with the same number of provers.

A central insight in both constructions is the shred-to-shine technique. It further yields a group-based MLPCS of independent interest, with $16\times$ shorter structured reference string and $10\times$ faster opening time than multilinear KZG (TCC'13).



## 2025/1355

* Title: Unconditional Pseudorandomness against Shallow Quantum Circuits
* Authors: Soumik Ghosh, Sathyawageeswar Subramanian, Wei Zhan
* [Permalink](https://eprint.iacr.org/2025/1355)
* [Download](https://eprint.iacr.org/2025/1355.pdf)

### Abstract

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography, and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on
complexity-theoretic assumptions.

In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove the following:

(1) Any quantum state $2$-design yields unconditional pseudorandomness against both $\mathsf{QNC}^0$ circuits with arbitrarily many ancillae and $\mathsf{AC}^0 \circ \mathsf{QNC}^0$ circuits with nearly linear ancillae.

(2) Random phased subspace states, where the phases are picked using a $4$-wise independent function, are unconditionally pseudoentangled against the above circuit classes.

(3) Any unitary $2$-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local $\mathsf{QNC}^0$ adversaries, even with limited $\mathsf{AC}^0$ postprocessing.

Our indistinguishability results for $2$-designs stand in stark contrast to the standard setting of quantum pseudorandomness against $\mathsf{BQP}$ circuits, wherein they can be distinguishable from Haar random ensembles using more than two copies or
queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.



## 2025/1356

* Title: Group Signatures with Message-Dependent Opening Directly Imply Timed-Release Encryption
* Authors: Yuto Imura, Keita Emura
* [Permalink](https://eprint.iacr.org/2025/1356)
* [Download](https://eprint.iacr.org/2025/1356.pdf)

### Abstract

Group signatures (GS, Chaum and van Heyst, EUROCRYPT 1991) are digital signatures that allow a signer to anonymously prove the membership and also allow the special authority called the opener can identify the signer. Group signatures with message-
dependent opening (GS-MDO, Sakai et al., Pairing 2012) weakened the power of the opener by introducing another authority called the admitter who issues a message-dependent token. It would be a natural research topic to clarify whether cryptographic
primitives that are required to construct GS-MDO are stronger than those of GS or not, according to the enhanced functionality of GS-MDO. In this paper, we propose a generic construction of timed-release encryption (TRE) from GS-MDO. Note that Sakai et
al. have shown that GS-MDO implies identity-based encryption (IBE), and Nakai et al. (IWSEC 2009) and Matsuda et al. (Pairing 2010) demonstrated generic constructions of TRE from IBE. Thus, we do not show any new result from the viewpoint of feasibility.
We show that (1) GS-MDO directly implies TRE without employing the generic constructions of TRE from IBE, and (2) the proposed TRE construction provides public verifiability, that is not usually supported by TRE, because a TRE ciphertext is a group
signature in our construction. We also introduce a new security notion which we call token unforgeability where no adversary can forge a token even the adversary has the opener's secret key, and prove that token unforgeability is implied by opener
anonymity which is a fundamental security notion of GS-MDO. Our result implies that GS-MDO is a very strong cryptographic primitive.



## 2025/1357

* Title: How to Copy-Protect Malleable-Puncturable Cryptographic Functionalities Under Arbitrary Challenge Distributions
* Authors: Alper Çakan, Vipul Goyal
* [Permalink](https://eprint.iacr.org/2025/1357)
* [Download](https://eprint.iacr.org/2025/1357.pdf)

### Abstract

A quantum copy-protection scheme (Aaronson, CCC’09) encodes a functionality into a quantum state such that given this state, no efficient adversary can create two (possibly entangled) quantum states that are both capable of running the functionality.
There has been a recent line of works on constructing provably-secure copy-protection schemes for general classes of schemes in the plain model, and most recently the recent work of Çakan and Goyal (IACR Eprint, 2025) showed how to copy-protect all
cryptographically puncturable schemes with pseudorandom puncturing points.

In this work, we show how to copy-protect even a larger class of schemes. We define a class of cryptographic schemes called malleable-puncturable schemes where the only requirement is that one can create a circuit that is capable of answering inputs at
points that are unrelated to the challenge in the security game but does not help the adversary answer inputs related to the challenge. This is a flexible generalization of puncturable schemes, and can capture a wide range of primitives that was not
known how to copy-protect prior to our work.

Going further, we show that our scheme is secure against arbitrary high min-entropy challenge distributions whereas previous work has only considered schemes that are punctured at pseudorandom points.



## 2025/1358

* Title: Domain-Oriented Masking Revisited: More Efficient AES Implementations with Arbitrary Protection Order
* Authors: Feng Zhou, Hua Chen, Limin Fan, Junhuai Yang
* [Permalink](https://eprint.iacr.org/2025/1358)
* [Download](https://eprint.iacr.org/2025/1358.pdf)

### Abstract

Recent years have witnessed significant progress in composable masked AES designs based on Hardware Private Circuits (HPCs) under the Probe-Isolating Non-Interference (PINI) framework. However, these designs still suffer from substantial randomness
requirements and area overhead at higher protection orders. In this work, we revisit Domain-Oriented Masking (DOM), originally proposed by Gross et. al. in 2016, and leverage the DOM-$dep$ and DOM-$indep$ multipliers to construct efficient AES
implementations based on the Strong Non-Interference (SNI) framework. Our contributions include:
1. a comprehensive security analysis of DOM-$dep$ and DOM-$indep$, including their compositional security under the SNI framework;
2. more efficient masked AES implementations for arbitrary protection orders, reducing randomness and area overhead while maintaining latency comparable to state-of-the-art HPC3-based designs.
Specifically, our masked AES implementations maintain a latency of 41 clock cycles by using the Hadzic's decomposition for $F_2^8$ inverter. When $d <= 4$, they save at least 13% in area (RNG included) and reduce latency by 19.6% compared to the smallest
$d$-PINI round-based masked AES implementations provided by Cassiers et.al. (The current version focuses on the core construction and its initial evaluation. Source code has been made publicly available to facilitate verification. Further performance
optimizations and theoretical generalizations are underway and will appear in an upcoming revision.)



## 2025/1359

* Title: Runtime Code Generation for Constant-Time Secret-Indexed Array Accesses: Applications to PERK and NTRU
* Authors: Décio Luiz Gazzoni Filho, Rafael G. Flores e Silva, Alessandro Budroni, Marco Palumbi, Gora Adj
* [Permalink](https://eprint.iacr.org/2025/1359)
* [Download](https://eprint.iacr.org/2025/1359.pdf)

### Abstract

One of the main guidelines to prevent timing side-channel attacks against cryptographic implementations is to avoid array accesses indexed by secret data. However, alternatives and countermeasures often incur significant performance losses. We propose a
novel methodology for secure, constant-time implementation of algorithms that read and write to small arrays with secret-dependent indices, with a constant-factor performance impact compared to timing-unprotected accesses. It is specifically suitable for
simple in-order CPUs like those in embedded systems, e.g., the ARM Cortex-M4 core. Although our methodology is general, we illustrate it with secure implementation of permutation operations, such as composition, inversion, and sampling, the latter using
the Fisher-Yates shuffle. We apply this methodology to the post-quantum cryptosystems PERK and NTRU, bridging most of the performance gap to unprotected implementations that employ secret-dependent array accesses.



## 2025/1360

* Title: Towards more secure constructions of private set operation schemes
* Authors: Mojtaba Rfiee
* [Permalink](https://eprint.iacr.org/2025/1360)
* [Download](https://eprint.iacr.org/2025/1360.pdf)

### Abstract

A private set operation (PSO) scheme [Rafiee, Comput. J. 2020] is a cryptographic primitive that enables a user to securely outsource their dataset to cloud storage, and then when needed, securely issue common set operation queries to the server and
receive the results. In [Rafiee, Comput. J. 2020], the only security notion of the PSO schemes, named naSIM, is proposed. This security notion models a weak attacker who is far from the threats of practical environments, and providing stronger security
notions has been raised as an open problem. In this paper, we propose a new security notion for the PSO schemes, called aIND, and show that this concept is stronger than naSIM. Furthermore, we propose a new PSO construction that satisfies the security
notion aIND. We also show that our construction does not increase the computational and storage overheads compared to other existing constructions, despite covering a much higher level of security.



## 2025/1361

* Title: Exploring Kaneko’s bound: On multi-edges, loops and the diameter of the supersingular $\ell$-isogeny graph
* Authors: Sebastiano Boscardin, Sebastian A. Spindler
* [Permalink](https://eprint.iacr.org/2025/1361)
* [Download](https://eprint.iacr.org/2025/1361.pdf)

### Abstract

We analyze Kaneko's bound to prove that, away from the $j$-invariant $0$, edges of multiplicity at least three can occur in the supersingular $\ell$-isogeny graph $\mathcal{G}_\ell(p)$ only if the base field's characteristic satisfies $p < 4\ell^3$.
Further we prove a diameter bound for $\mathcal{G}_\ell(p)$, while also showing that most vertex pairs have a substantially smaller distance, in the directed case; this bound is then used in conjunction with Kaneko's bound to deduce that the distance of $
0$ and $1728$ in $\mathcal{G}_\ell(p)$ is at least one fourth of the graph's diameter if $p \equiv 11 \mathrel{\operatorname{mod}} 12$. We also study other phenomena in $\mathcal{G}_\ell(p)$ with Kaneko's bound and provide data to demonstrate that the
resulting bounds are optimal; for one of these bounds we investigate the connection between loop multiplicities in isogeny graphs and the factorization of the `diagonal' classical modular polynomial $\Phi_\ell(X,X)$ in positive characteristic.



## 2025/1362

* Title: Cryptanalysis of the best HFE-LL' Constructions
* Authors: Daniel Smith-Tone, Cristian Valenzuela
* [Permalink](https://eprint.iacr.org/2025/1362)
* [Download](https://eprint.iacr.org/2025/1362.pdf)

### Abstract

In the last few years, the old idea of internal perturbation for multivariate schemes has been resurrected. A form of this method was proposed with application to HFE and UOV and independently by another team for application to Rainbow. Most recently,
a newer and more efficient version of internal perturbation was proposed as an enhanced measure for securing HFE for encryption.

This efficient method, known as the LL' construction, is designed to add little complexity to HFE decryption while increasing the rank of the resulting map to resist the now very effective cryptanalyses powered by MinRank. The basic idea of the
construction is to have two small lists of binary linear forms which when multiplied produce rank $1$ quadratic forms. Random linear combinations of these products are then added to each of the HFE equations, resulting in a masked HFE. The main trick
to make the scheme usable is to encrypt an send many random messages so that statistically it is likely that the legitimate user can find a ciphertext that is not perturbed by the construction and which may be decrypted as a plain HFE ciphertext.

We show that this approach is not secure. In particular, we present a method to recover the noise support, a collection of quadratic forms spanning the set of LL' quadratic forms. We then are able to filter out the effect of these maps to recover a
compatible HFE map. Finally, we are able to complete the key recovery, achieving efficiently an equivalent private key.



## 2025/1363

* Title: Universally Composable Adaptor Signatures
* Authors: Paul Gerhart, Daniel Rausch, Dominique Schröder
* [Permalink](https://eprint.iacr.org/2025/1363)
* [Download](https://eprint.iacr.org/2025/1363.pdf)

### Abstract

Adaptor signatures extend the functionality of digital signatures by enabling the computation of pre-signatures on messages relative to statements in NP relations.
Pre-signatures are publicly verifiable objects that simultaneously hide and commit to a standard signature on the same message.
Anyone possessing a valid witness for the statement can adapt the pre-signature into a full signature under the underlying signature scheme.
Since adaptor signatures are commonly used as building blocks in larger systems—such as blockchain protocols—it is natural to seek a security definition within the Universal Composability (UC) framework.
A recent attempt by Tairi et al. (CCS'23) introduced the first UC functionality for adaptor signatures.

This paper makes both negative and positive contributions. On the negative side, we show that the functionality proposed by Tairi et al. suffers from critical limitations:
- The functionality fails to guarantee extractability and adaptability—the core security properties of adaptor signatures—to higher-level protocols.
- No adaptor signature scheme can realize the functionality.

On the positive side, we propose a new UC functionality that faithfully captures the latest security guarantees of adaptor signatures as formalized via game-based notions by Gerhart et al. (EUROCRYPT'24).
- Our functionality guarantees extractability, unique extractability, and pre-signature adaptability in a way that is composable and meaningful for higher-level protocols.
- We show that it is realizable by an enhanced Schnorr-based adaptor signature scheme that we construct. Our construction maintains compatibility with existing infrastructure and is efficient enough for practical deployment, particularly in Bitcoin-
like environments.



## 2025/1364

* Title: A Framework for Witness Encryption from Linearly Verifiable SNARKs and Applications
* Authors: Sanjam Garg, Mohammad Hajiabadi, Dimitris Kolonelos, Abhiram Kothapalli, Guru-Vamsi Policharla
* [Permalink](https://eprint.iacr.org/2025/1364)
* [Download](https://eprint.iacr.org/2025/1364.pdf)

### Abstract

Witness Encryption (WE) is a powerful cryptographic primitive, enabling applications that would otherwise appear infeasible. While general-purpose WE requires strong cryptographic assumptions, and is highly inefficient, recent works have demonstrated
that it is possible to design special-purpose WE schemes for targeted applications that can be built from weaker assumptions and can also be concretely efficient. Despite the plethora of constructions in the literature that (implicitly) use witness
encryption schemes, there has been no systematic study of special purpose witness encryption schemes.

In this work we make progress towards this goal by designing a modular and extensible framework, which allows us to better understand existing schemes and further enables us to construct new witness encryption schemes. The framework is designed around
simple but powerful building blocks that we refer to as "gadgets". Gadgets can be thought of as witness encryption schemes for small targeted relations (induced by linearly verifiable arguments) but they can be composed with each other to build larger,
more expressive relations that are useful in applications. To highlight the power of our framework we methodically recover past results, improve upon them and even provide new feasibility results.

The first application of our framework is a Registered Attribute-Based Encryption Scheme [Hohenberger et al. (Eurocrypt 23)] with linear sized common reference string (CRS). Numerous Registered Attribute-Based Encryption (R-ABE) constructions have
introduced though a black-box R-ABE construction with a linear--in the number of users--CRS has been a persistent open problem, with the state-of-the-art concretely being N^{1.58} (Garg et al. [GLWW, CRYPTO 24]). Empowered by our Witness Encryption
framework we provide the first construction of black-box R-ABE with linear-sized CRS. Our construction is based on a novel realization of encryption for DNF formulas that leverages encryption for set membership.

Our second application is a feasibility result for Registered Threshold Encryption (RTE) with succinct ciphertexts. RTE (Branco et al. [ASIACRYPT 2024] is an analogue of the recently introduced Silent Threshold Encryption (Garg et al. [GKPW, CRYPTO 24])
in the Registered Setting. We revisit Registered Threshold Encryption and provide an efficient construction, with constant-sized encryption key and ciphertexts, that makes use of our WE framework.

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