[continued from previous message]

## 2025/1142

* Title: OnionPIRv2: Efficient Single-Server PIR
* Authors: Yue Chen, Ling Ren
* [Permalink](https://eprint.iacr.org/2025/1142)
* [Download](https://eprint.iacr.org/2025/1142.pdf)

### Abstract

This paper presents OnionPIRv2, an efficient implementation of OnionPIR incorporating standard orthogonal techniques and engineering improvements. OnionPIR is a single-server PIR scheme that improves response size and computation cost by utilizing
recent advances in somewhat homomorphic encryption (SHE) and carefully composing two lattice-based SHE schemes to control the noise growth of SHE. OnionPIRv2 achieves $2.5$x-$3.6$x response overhead for databases with moderately large entries (around $4$
KB or above) and up to $1600$ MB/s server computation throughput.



## 2025/1143

* Title: Wedges, oil, and vinegar -- An analysis of UOV in characteristic 2
* Authors: Lars Ran
* [Permalink](https://eprint.iacr.org/2025/1143)
* [Download](https://eprint.iacr.org/2025/1143.pdf)

### Abstract

The Unbalanced Oil and Vinegar construction (UOV) has been the backbone of multivariate cryptography since the fall of HFE-based schemes. In fact, 7 UOV-based schemes have been submitted to the NIST additional call for signatures, and 4 of these made it
to the second round. For efficiency considerations, most of these schemes are defined over a field of characteristic 2. This has as a side effect that the polar forms of the UOV public maps are not only symmetric, but also alternating.

In this work, we propose a new key-recovery attack on UOV in characteristic 2 that makes use of this property. We consider the polar forms of the UOV public maps as elements of the exterior algebra. We show that these are contained in a certain subspace
of the second exterior power that is dependent on the oil space. This allows us to define relations between the polar forms and the image of the dual of the oil space under the Plücker embedding. With this, we can recover the secret oil space using
sparse linear algebra.

This new attack has an improved complexity over previous methods and reduces the security by 4, 11, and 20 bits for uov-Ip, uov-III, and uov-V, respectively. Furthermore, the attack is applicable to MAYO$_2$ and improves on the best attack by 28 bits.



## 2025/1144

* Title: Parasol Compiler: Pushing the Boundaries of FHE Program Efficiency
* Authors: Rick Weber, Ryan Orendorff, Ghada Almashaqbeh, Ravital Solomon
* [Permalink](https://eprint.iacr.org/2025/1144)
* [Download](https://eprint.iacr.org/2025/1144.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) is a key technology to enable privacy-preserving computation. While optimized FHE implementations already exist, the inner workings of FHE are technically complex. This makes it challenging, especially for non-experts,
to develop highly-efficient FHE programs that can exploit the advanced hardware of today. Although several compilers have emerged to help in this process, due to design choices, they are limited in terms of application support and the efficiency levels
they can achieve.

In this work, we showcase how to make FHE accessible to non-expert developers while retaining the performance provided by an expert-level implementation. We introduce Parasol, a novel end-to-end compiler encompassing a virtual processor with a custom
Instruction Set Architecture (ISA) and a low-level library that implements FHE operations. Our processor integrates with existing compiler toolchains, thereby providing mainstream language support. We extract parallelism at multiple levels via our
processor design and its computing paradigm. Specifically, we champion a Circuit Bootstrapping (CBS)-based paradigm, enabling efficient FHE circuit composition with multiplexers. Furthermore, Parasol’s underlying design highlights the benefits of
expressing FHE computations at a higher level—producing highly compact program representations. Our experiments demonstrate the superiority of Parasol, in terms of runtime (up to 17x faster), program size (up to 22x smaller), and compile time (up to
32x shorter) compared to the current state-of-the-art. We expect the FHE computing paradigm underlying Parasol to attract future interest since it exposes added parallelism for FHE accelerators to exploit.



## 2025/1145

* Title: Dynamic Group Signatures with Verifier-Local Revocation
* Authors: Callum London, Daniel Gardham, Constantin Catalin Dragan
* [Permalink](https://eprint.iacr.org/2025/1145)
* [Download](https://eprint.iacr.org/2025/1145.pdf)

### Abstract

Group Signatures are fundamental cryptographic primitives that allow users to sign a message on behalf of a predefined set of users, curated by the group manager. The security properties ensure that members of the group can sign anonymously and without
fear of being framed. In dynamic group signatures, the group manager has finer-grained control over group updates while ensuring membership privacy (i.e., hiding when users join and leave). The only known scheme that achieves standard security properties
and membership privacy has been proposed by Backes et al. CCS 2019. However, they rely on an inefficient revocation mechanism that re-issues credentials to all active members during every group update, and users have to rely on a secure and private
channel to join the group.
In this paper, we introduce a dynamic group signature that supports verifier-local revocation, while achieving strong security properties, including membership privacy for users joining over a public channel. Moreover, when our scheme is paired with
structure-preserving signatures over equivalence class it enjoys a smaller signature size compared to Backes et al. Finally, as a stand-alone contribution we extend the primitive Asynchronous Remote Key Generation (Frymann et al. CCS 2020) with trapdoors
and introduce new security properties to capture this new functionality, which is fundamental to the design of our revocation mechanism



## 2025/1146

* Title: QV-net: Decentralized Self-Tallying Quadratic Voting with Maximal Ballot Secrecy
* Authors: Zibo Zhou, Zongyang Zhang, Feng Hao, Bowen Zheng, Zulkarnaim Masyhur * [Permalink](https://eprint.iacr.org/2025/1146)
* [Download](https://eprint.iacr.org/2025/1146.pdf)

### Abstract

Decentralized e-voting enables secure and transparent elections without relying on trusted authorities, with blockchain emerging as a popular platform. It has compelling applications in Decentralized Autonomous Organizations (DAOs), where governance
relies on voting with blockchain-issued tokens. Quadratic voting (QV), a mechanism that mitigates the dominance of large token holders, has been adopted by many DAO elections to enhance fairness. However, current QV systems deployed in practice publish
voters' choices in plaintext with digital signatures. The open nature of all ballots comprises voter privacy, potentially affecting voters' honest participation. Prior research proposes using cryptographic techniques to encrypt QV ballots, but they work
in a centralized setting, relying on a trusted group of tallying authorities to administrate an election. However, in DAO voting, there is no trusted third party.

In this paper, we propose QV Network (QV-net), the first decentralized quadratic voting scheme, in which voters do not need to trust any third party other than themselves for ballot secrecy. QV-net is self-tallying with maximal ballot secrecy. Self-
tallying allows anyone to compute election results once all ballots are cast. Maximal ballot secrecy ensures that what each voter learns from QV-net is nothing more than the tally and their own ballot. We provide an open-source implementation of QV-net
to demonstrate its practicality based on real-world DAO voting settings, reporting only a few milliseconds for voting and a maximum of 255 milliseconds for tallying.

The exceptional efficiency of QV-net is attributed to the design of two new Zero-Knowledge Argument of Knowledge (ZKAoK) protocols for QV ballot secrecy and integrity. Previous works generally rely on pairing-friendly curves to prove the well-formedness
of an encrypted QV ballot. But they incur heavy computation and large data sizes. We tackle the challenges of appropriately formalizing and proving ZKAoK relations for QV without using these curves. Specifically, we develop a succinct ZKAoK to prove a
new relation: the sum of squares of a private vector's components equals a private scalar. We also introduce the first aggregated range proof to prove that values committed under different keys fall within their respective ranges. Together, these two new
zero-knowledge protocols enable us to build an efficient decentralized QV scheme and are of independent interest.



## 2025/1147

* Title: Jigsaw: Doubly Private Smart Contracts
* Authors: Sanjam Garg, Aarushi Goel, Dimitris Kolonelos, Rohit Sinha
* [Permalink](https://eprint.iacr.org/2025/1147)
* [Download](https://eprint.iacr.org/2025/1147.pdf)

### Abstract

Privacy is a growing concern for smart contracts on public ledgers.
In recent years, we have seen several practical systems for privacy-preserving smart contracts, but they only target privacy of on-chain data, and rely on trusted off-chain parties with user data -- for instance, a decentralized finance application (e.g.
exchange) relies on an off-chain matching engine to process client orders that get settled on-chain, where privacy only applies to the on-chain data.
Privacy conscious users demand stronger notions of privacy, for their identity and their data, from all other parties in the ecosystem.

We propose a novel framework for smart contracts that ensures {\em doubly private}
execution, addressing {both on-chain and off-chain privacy} requirements.
In our framework, clients submit their requests in a privacy-preserving manner to a group of (potentially mutually untrusting) servers. These servers collaboratively match client requests without learning any information about the data or identities of
the clients.

We then present {\em Jigsaw}, an efficient cryptographic realization of our proposed framework. {\em Jigsaw} builds on the ZEXE architecture (Bowe et al., S\&P 2020), which leverages zkSNARKs, and extends Collaborative zkSNARKs (Ozdemir and Boneh, USENIX
2022) to enable proof generation by a group of servers.

In Jigsaw, we introduce a novel collaborative zkSNARK construction that achieves low latency and reduced proving time, and showcase these advantages over sample applications ranging from trading in a decentralized exchange to auctions and voting.
Our experiments demonstrate that {\em Jigsaw} is roughly $40-50$x faster in proof generation and uses orders-of-magnitude less bandwidth than the naive approach of using off-the-shelf Collaborative zkSNARKs.



## 2025/1148

* Title: On the Composition of Single-Keyed Tweakable Even-Mansour for Achieving BBB Security
* Authors: Avik Chakraborti, Mridul Nandi, Suprita Talnikar, Kan Yasuda
* [Permalink](https://eprint.iacr.org/2025/1148)
* [Download](https://eprint.iacr.org/2025/1148.pdf)

### Abstract

Observing the growing popularity of random permutation (RP)-based designs (e.g, Sponge), Bart Mennink in CRYPTO 2019 has initiated an interesting research in the direction of RP-based pseudorandom functions (PRFs). Both are claimed to achieve beyond-the-
birthday-bound (BBB) security of $2n/3$ bits ($n$ being the input block size in bits) but require two instances of RPs and can handle only one-block inputs. In this work, we extend research in this direction by providing two new BBB-secure constructions
by composing the tweakable Even-Mansour appropriately. Our first construction requires only one instance of an RP and requires only one key. Our second construction extends the first to a nonce-based Message Authentication Code (MAC) using a universal
hash to deal with multi-block inputs. We show that the hash key can be derived from the original key when the underlying hash is the Polyhash. We provide matching attacks for both constructions to demonstrate the tightness of the proven security bounds.



## 2025/1149

* Title: An Efficient Encryption Scheme Based on $(U+V, U+W)$ Codes
* Authors: Yang Yang, Fangguo Zhang
* [Permalink](https://eprint.iacr.org/2025/1149)
* [Download](https://eprint.iacr.org/2025/1149.pdf)

### Abstract

In this paper, we propose an improvement to the McEliece encryption scheme by replacing the Goppa code with a $(U+V,U+W)$ code. Specifically, we embed the generator matrices of a split Reed-Solomon code into the generator matrix of the $(U+V,U+W)$ code.
This approach disrupts the algebraic structure of Reed-Solomon codes, thereby enhancing resistance against structural attacks targeting such codes, while simultaneously preserving their excellent error-correcting capabilities. As a result, the proposed
scheme achieves a significant reduction in public key size. Under the hardness assumptions of the decoding problem and the code distinguishing problem for $(U+V,U+W)$ codes, we prove that the scheme achieves indistinguishability under chosen-plaintext
attacks (IND-CPA security). Finally, we provide recommended parameters for various security levels and compare the proposed scheme with other code-based public key encryption schemes.



## 2025/1150

* Title: Lightweight Sorting in Approximate Homomorphic Encryption
* Authors: Lorenzo Rovida, Alberto Leporati, Simone Basile
* [Permalink](https://eprint.iacr.org/2025/1150)
* [Download](https://eprint.iacr.org/2025/1150.pdf)

### Abstract

Sorting encrypted values is an open research problem that plays a crucial role in the broader objective of providing efficient and practical privacy-preserving online services.
The current state of the art work by Mazzone, Everts, Hahn and Peter (USENIX Security '25) proposes efficient algorithms for ranking, indexing and sorting based on the CKKS scheme, which deviates from the compare-and-swap paradigm, typically used by
sorting networks, using a permutation-based approach. This allows to build shallow sorting circuits in a very simple way.
In this work, we follow up their work and explore different approaches to approximate the nonlinear functions required by the encrypted circuit (where only additions and multiplications can be evaluated), and we propose simpler solutions that allow for
faster computations and smaller memory requirements.

In particular, we drastically reduce the upper bound on the depth of the circuits from 65 to 20, making our circuits usable in relatively small rings such as $N=2^{16}$, even for sorting values while preserving up to three decimal places. As an example,
our circuit sorts 128 values with duplicates in roughly 20 seconds on a laptop, using roughly 1 GB of memory, maintaining a precision of 0.01.
Furthermore, we propose an implementation of a swap-based bitonic network that is not based on approximations of the sgn$(x)$ function, which scales linearly with the number of values, useful when the number of available slots is small.



## 2025/1151

* Title: Faster signature verification with 3-dimensional decomposition
* Authors: Vojtech Suchanek, Marek Sys, Lukasz Chmielewski
* [Permalink](https://eprint.iacr.org/2025/1151)
* [Download](https://eprint.iacr.org/2025/1151.pdf)

### Abstract

We introduce a novel technique for verifying Schnorr signatures using fast endomorphisms. Traditionally, fast endomorphisms over prime field curves are used to decompose a scalar into two scalars of half of the size. This work shows that the context of
the verification of signatures allows for the decomposition into three scalars of a third of the size. We apply our technique to three scenarios: verification of a single Schnorr signature, batch verification, and verification of BLS signatures within
the Blind Diffie-Hellman key exchange protocol. Our experiments on AMD x86 and ARM Cortex-M4 platforms show performance improvements of approximately 20%, 13%, and 27%, respectively. The technique can also be used to accelerate the verification of ECDSA
signatures, provided that one additional bit of information is appended to the signature.

As part of our work, we analyze the performance of 3-dimensional lattice reduction algorithms, which are critical for multi-scalar decompositions. To identify the most efficient approach, we experimentally compare Semaev’s algorithm --- known for its
best asymptotic complexity --- with the simpler Lagrange’s algorithm. Our results reveal that, despite its simplicity, Lagrange’s algorithm is nearly twice as fast as Semaev’s in practice.



## 2025/1152

* Title: ZK-ProVer: Proving Programming Verification in Non-Interactive Zero-Knowledge Proofs
* Authors: Haoyu Wei, Jingyu Ke, Ruibang Liu, Guoqiang Li
* [Permalink](https://eprint.iacr.org/2025/1152)
* [Download](https://eprint.iacr.org/2025/1152.pdf)

### Abstract

Program verification ensures software correctness through formal methods but incurs substantial computational overhead. It typically encodes program execution into formulas that are verified using a SAT solver and its extensions. However, this process
exposes sensitive program details and requires redundant computations when multiple parties need to verify correctness. To overcome these limitations, zero-knowledge proofs (ZKPs) generate compact, reusable proofs with fast verification times, while
provably hiding the program’s internal logic. We propose a two-phase zero-knowledge protocol that hides program implementation details throughout verification. Phase I uses a zero-knowledge virtual machine (zkVM) to encode programs into SAT formulas
without
revealing their semantics. Phase II employs the encoding of resolution proofs for UNSAT instances and circuits for satisfying assignment verification for SAT instances through PLONKish circuits. Evaluation on the Boolector benchmark demonstrates that our
method achieves verification time that is efficient and is independent of clause width for UNSAT instances and formula size for SAT instances. The resulting ZKPs enable efficient verification of program properties while providing strong end-to-end
privacy guarantees.



## 2025/1153

* Title: Privacy-aware White and Black List Searching for Fraud Analysis
* Authors: William J Buchanan, Jamie Gilchrist, Zakwan Jaroucheh, Dmitri Timosenko, Nanik Ramchandani, Hisham Ali
* [Permalink](https://eprint.iacr.org/2025/1153)
* [Download](https://eprint.iacr.org/2025/1153.pdf)

### Abstract

In many areas of cybersecurity, we require access to Personally Identifiable Information (PII), such as names, postal addresses and email addresses. Unfortunately, this can lead to data breaches, especially in relation to data compliance regulations such
as GDPR. An Internet Protocol (IP) address is an identifier that is assigned to a networked device to enable it to communicate over networks that use IP. Thus, in applications which are privacy-aware, we may aim to hide the IP address while aiming to
determine if the address comes from a blacklist. One solution to this is to use homomorphic encryption to match an encrypted version of an IP address to a blacklisted network list. This matching allows us to encrypt the IP address and match it to an
encrypted version of a blacklist. In this paper, we use the OpenFHE library \cite{OpenFHE} to encrypt network addresses with the BFV homomorphic encryption scheme. In order to assess the performance overhead of BFV, we implement a matching method using
the OpenFHE library and compare it against partial homomorphic schemes, including Paillier, Damgard-Jurik, Okamoto-Uchiyama, Naccache-Stern and Benaloh. The main findings are that the BFV method compares favourably against the partial homomorphic methods
in most cases.



## 2025/1154

* Title: Evaluation of Modular Polynomials from Supersingular Elliptic Curves
* Authors: Maria Corte-Real Santos, Jonathan Komada Eriksen, Antonin Leroux, Michael Meyer, Lorenz Panny
* [Permalink](https://eprint.iacr.org/2025/1154)
* [Download](https://eprint.iacr.org/2025/1154.pdf)

### Abstract

We present several new algorithms to evaluate modular polynomials of level $\ell$ modulo a prime $p$ on an input $j$.
More precisely, we introduce two new generic algorithms, sharing the following similarities: they are based on a CRT approach; they make use of supersingular curves and the Deuring correspondence; and, their memory requirements are optimal.

The first algorithm combines the ideas behind a hybrid algorithm of Sutherland in 2013 with a recent algorithm to compute modular polynomials using supersingular curves introduced in 2023 by Leroux. The complexity (holding around several plausible
heuristic assumptions) of the resulting algorithm matches the $O(\ell^3 \log^{3} \ell + \ell \log p)$ time complexity of the best known algorithm by Sutherland, but has an optimal memory requirement.

Our second algorithm is based on a sub-algorithm that can evaluate modular polynomials efficiently on supersingular $j$-invariants defined over $\mathbb{F}_p$, and achieves heuristic complexity quadratic in both $\ell$ and $\log j$, and linear in $\
log p$. In particular, it is the first generic algorithm with optimal memory requirement to obtain a quadratic complexity in~$\ell$.

Additionally, we show how to adapt our method to the computation of other types of modular polynomials such as the one stemming from Weber's function.

Finally, we provide an optimised implementation of the two algorithms detailed in this paper, though we emphasise that various modules in our codebase
may find applications outside their use in this paper.



## 2025/1155

* Title: On the Security of Group Ring Learning with Errors
* Authors: Andrew Mendelsohn, Charles Grover, Cong Ling
* [Permalink](https://eprint.iacr.org/2025/1155)
* [Download](https://eprint.iacr.org/2025/1155.pdf)

### Abstract

We propose a dimension-reducing transformation on Group Ring Learning with Errors (GRLWE) samples. We exhibit an efficiently computable isomorphism which takes samples defined over the group rings used in the construction of GRLWE to twice as many
samples defined over matrix rings, in half the dimension. This is done by composing two maps: the first map is a transformation showing that the group rings used are orders in central simple algebras, and the second map takes the obtained central simple
algebra to a matrix ring. When combined with lattice reduction on the resulting matrix samples, this gives an attack on the GRLWE problem. We extend this attack to other groups proposed for cryptographic use by the creators of GRLWE, and display some
numerical results quantifying the effects of the transformation, using the `Lattice Estimator'. We then give a family of groups from which GRLWE-style group rings can be constructed which are immune to our attack, namely the generalized quaternion groups.
Finally, we discuss the merits and vulnerabilities of a number of different forms of structured LWE.



## 2025/1156

* Title: An efficient construction of Raz's two-source randomness extractor with improved parameters
* Authors: Cameron Foreman, Lewis Wooltorton, Kevin Milner, Florian J. Curchod * [Permalink](https://eprint.iacr.org/2025/1156)
* [Download](https://eprint.iacr.org/2025/1156.pdf)

### Abstract

Randomness extractors are algorithms that distill weak random sources into near-perfect random numbers. Two-source extractors enable this distillation process by combining two independent weak random sources. Raz’s extractor (STOC '05) was the first to
achieve this in a setting where one source has linear min-entropy (i.e., proportional to its length), while the other has only logarithmic min-entropy in its length. However, Raz's original construction is impractical due to a polynomial computation time
of at least degree 4. Our work solves this problem by presenting an improved version of Raz's extractor with quasi-linear computation time, as well as a new analytic theorem with reduced entropy requirements. We provide comprehensive analytical and
numerical comparisons of our construction with others in the literature, and we derive strong and quantum-proof versions of our efficient Raz extractor. Additionally, we offer an easy-to-use, open-source code implementation of the extractor and a
numerical parameter calculation module.



## 2025/1157

* Title: General Multi-Prime Multi-Power RSA - A Generalization of RSA and CRT-RSA to Regular Integers Modulo $n$
* Authors: Klaus Dohmen, Mandy Lange-Geisler
* [Permalink](https://eprint.iacr.org/2025/1157)
* [Download](https://eprint.iacr.org/2025/1157.pdf)

### Abstract

Based on a sharpening of Carmichael’s theorem and Euler’s theorem we generalize RSA and CRT-RSA to arbitrary integer moduli $n > 1$, while restricting messages to integers $m$ which are regular modulo $n$, meaning that they have a John-von-Neumann
pseudoinverse modulo $n$. We prove the correctness and completeness of our encryption and decryption method for this class of messages, and show that the restriction to regular integers is negligible, since under reasonable assumptions almost all
integers are regular modulo $n$.



## 2025/1158

* Title: Bridging Bitcoin to Second Layers via BitVM2
* Authors: Robin Linus, Lukas Aumayr, Zeta Avarikioti, Matteo Maffei, Andrea Pelosi, Orfeas Thyfronitis Litos, Christos Stefo, David Tse, Alexei Zamyatin
* [Permalink](https://eprint.iacr.org/2025/1158)
* [Download](https://eprint.iacr.org/2025/1158.pdf)

### Abstract

A holy grail in blockchain infrastructure is a trustless bridge between Bitcoin and its second layers or other chains. We make progress toward this vision by introducing the first light-client based Bitcoin bridge. At the heart of its design lies BitVM2-
core, a novel paradigm that enables arbitrary program execution on Bitcoin, combining Turing-complete expressiveness with the security of Bitcoin consensus. BitVM2-bridge advances prior approaches by reducing the trust assumption from an honest majority (
t-of-n) to existential honesty (1-of-n) during setup. Liveness is guaranteed with only one rational operator, and any user can act as a challenger, enabling permissionless verification. A production-level implementation of BitVM2 has been developed and a
full challenge verification has been executed on the Bitcoin mainnet.



## 2025/1159

* Title: $\mathsf{DekartProof}$: Efficient Vector Range Proofs and Their Applications
* Authors: Dan Boneh, Trisha Datta, Rex Fernando, Kamilla Nazirkhanova, Alin Tomescu
* [Permalink](https://eprint.iacr.org/2025/1159)
* [Download](https://eprint.iacr.org/2025/1159.pdf)

### Abstract

Let $p$ be a prime and consider a committed vector $\vec{v} = (v_1, \ldots, v_m) \in \mathbb{F}_p^m$.
We develop new techniques for succinctly proving in zero-knowledge that all the elements of $\vec{v}$ are in the range $\{0,1,\ldots,n\}$ for some $n<p$.
We refer to this as a batched zero-knowledge range proof, or a batched ZKRP. This problem comes up often in cryptography: it is needed in publicly verifiable secret sharing (PVSS), confidential transactions, and election protocols.
Our approach makes use of a multilinear polynomial commitment scheme and the sum check protocol to efficiently provide a batch range proof for the entire vector.
Along the way we introduce a new type of a Polynomial Interactive Oracle Proof (PIOP) we call a Homomorphic PIOP that can be compiled into a SNARK.
We use an HPIOP to construct a new efficient zero-knowledge version of the sum check protocol.
We compare our new techniques with existing range proofs and lookup arguments.



## 2025/1160

* Title: Black-box Approaches to Authenticated Dictionaries: New Constructions and Lower Bounds
* Authors: Francesca Falzon, Harjasleen Malvai, Emanuel Opel
* [Permalink](https://eprint.iacr.org/2025/1160)
* [Download](https://eprint.iacr.org/2025/1160.pdf)

### Abstract

Authenticated dictionaries (ADs) enable secure lookups to a dictionary hosted by an untrusted server and are a key component of various real-world applications, including transparency systems and cryptocurrencies. Despite significant overlap in
techniques for building ADs and related primitives, such as memory checkers and accumulators (i.e., authenticated sets), these relationships have yet to be formalized.

In this work, we give a rigorous treatment of ADs and prove their precise connection to the latter two cornerstone primitives. We start by laying out the minimal algorithms and security properties needed in practice and introduce a new security notion
for ADs called write-committing, which requires update proofs to guarantee an exact count of changes.

We prove that any AD built from a black-box authenticated set (AS) makes at least $\Omega(\log n)$ AS calls per lookup and obeys a trade-off between lookups and updates. With optimal lookups, such a scheme requires at least $\Omega(\log n/\log\log n)$ AS
calls per update.
We also resolve the open question of constructing a secure AD from only black-box access to an AS and present two schemes adhering to the trade-off: one with optimal lookup overhead and the other with higher lookup complexity, but which only requires two
AS calls for an update.

Finally, we make strides towards unifying memory checkers and ADs. To this end, we present two constructions for memory checkers with black-box access to an AD: one that incurs constant overhead (but needs write-committing) and a second that only
requires the AD to be lookup-secure but incurs logarithmic overhead. We then give a simple AD construction using a memory checker as a black-box, with $\mathcal{O}(1)$ overhead.

Our results demonstrate the inherent limitations of ADs built from accumulators but lay the foundation for extending existing results on memory checkers and other primitives, such as vector commitments, to ADs.



## 2025/1161

* Title: High-Performance FPGA Accelerator for the Post-quantum Signature Scheme CROSS
* Authors: Patrick Karl, Francesco Antognazza, Alessandro Barenghi, Gerardo Pelosi, Georg Sigl
* [Permalink](https://eprint.iacr.org/2025/1161)
* [Download](https://eprint.iacr.org/2025/1161.pdf)

### Abstract


[continued in next message]

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