[continued from previous message]

- We propose two simple constructions of MA-ID-NIKE schemes from indistinguishability obfuscation (iO) and multilinear maps, respectively. These constructions achieve only selective security, but can be leveraged to adaptive security for small groups of
users (that want to be able to agree on a joint shared key) in the random oracle model.
- We give a simple and elegant construction of MA-ID-NIKEs from identity-based encryption (IBE) and universal samplers. This construction achieves adaptive security also for large groups of users based on the adaptive security of the used universal
samplers. Universal samplers, in turn, are known to be achievable using iO in the random oracle model. As a nice feature, the same construction yields hierarchical MA-ID-NIKEs or public-key NIKEs when instantiated with hierarchical IBE or public-key
encryption instead of IBE schemes.
While these results are clearly only feasibility results, they do demonstrate the achievability of a concept that itself has very practical use cases.



## 2025/311

* Title: Malleable SNARKs and Their Applications
* Authors: Suvradip Chakraborty, Dennis Hofheinz, Roman Langrehr, Jesper Buus Nielsen, Christoph Striecks, Daniele Venturi
* [Permalink](https://eprint.iacr.org/2025/311)
* [Download](https://eprint.iacr.org/2025/311.pdf)

### Abstract

Succinct non-interactive arguments of knowledge (SNARKs) are variants of non-interactive zero-knowledge proofs (NIZKs) in which complex statements can be proven in a compact way. SNARKs have had tremendous impact in several areas of cryptography,
including verifiable computing, blockchains, and anonymous communication. A recurring concept in many applications is the concept of recursive SNARKs, in which a proof references a previous proof to show an evolved statement.

In this work, we investigate malleable SNARKs, a generalization of this concept of recursion. An adaptation of the existing concept of malleable NIZKs, malleable SNARKs allow to modify SNARK proofs to show related statements, but such that such mauled
proofs are indistinguishable from “properly generated” fresh proofs of the related statement. We show how to instantiate malleable SNARKs for universal languages and relations, and give a number of applications: the first post-quantum RCCA-secure
rerandomizable and updatable encryption schemes, a generic construction of reverse firewalls, and an unlinkable (i.e., computation-hiding) targeted malleable homomorphic encryption scheme.

Technically, our malleable SNARK construction relies on recursive proofs, but with a twist: in order to support the strong indistinguishability properties of mauled and fresh SNARK proofs, we need to allow an unbounded recursion depth. To still allow for
a reasonable notion of extractability in this setting (and in particular to guarantee that extraction eventually finishes with a “proper” witness that does not refer to a previous SNARK proof), we rely on a new and generic computational primitive
called adversarial one-way function (AOWF) that may be of independent interest. We give an AOWF candidate and prove it secure in the random oracle model.



## 2025/312

* Title: Traceable Verifiable Random Functions
* Authors: Dan Boneh, Aditi Partap, Lior Rotem
* [Permalink](https://eprint.iacr.org/2025/312)
* [Download](https://eprint.iacr.org/2025/312.pdf)

### Abstract

A threshold verifiable random function (threshold VRF) is a VRF where the evaluation key is secret shared among $n$ parties, and a quorum of $t$ parties is needed to evaluate the VRF. Threshold VRFs are used widely in practice in applications such as
randomness beacons and deterministic wallets. Despite their long history, the question of accountability for leaking key shares in a threshold VRF has not been studied. Specifically, consider a set of $f$ parties who use their key shares to create an
evaluation box $E$ that lets anyone evaluate the VRF at any point in the domain of the VRF. When $f$ is less than the threshold $t$, this box $E$ must also take as input $t-f$ additional evaluation shares. Our goal is to design a threshold VRF where
there is a tracing algorithm that can trace any such box $E$ to the coalition of $f$ parties that created it, using only blackbox access to $E$. The risk of tracing should deter the coalition from selling such a box. Questions in this vein were
previously explored in the context of threshold decryption and secret sharing. Here we define and study traceability for a threshold VRF.

Our traceable threshold VRF is built from a VRF based on Paillier encryption. The starting point for our tracing algorithm is the tracing technique of Boneh-Partap-Rotem (Crypto 2024) designed for tracing leaks in the context of secret sharing. However,
there are multiple technical challenges in making this approach work, and we develop the necessary tools to overcome all these challenges. The end result is a threshold VRF with a provably secure tracing algorithm.



## 2025/313

* Title: Lattice-based $\Sigma$-Protocols for Polynomial Relations with Standard Soundness
* Authors: Lizhen Zhang, Shang Gao, Bin Xiao
* [Permalink](https://eprint.iacr.org/2025/313)
* [Download](https://eprint.iacr.org/2025/313.pdf)

### Abstract

We propose new techniques for enhancing the efficiency of $\Sigma$-protocols in lattice settings.
One major challenge in lattice-based $\Sigma$-protocols is restricting the norm of the extracted witness in soundness proofs.
Most of existing solutions either repeat the protocol several times or opt for a relaxation version of the original relation.
Recently, Boneh and Chen have propose an innovative solution called $\mathsf{LatticeFold}$,
which utilizes a sum-check protocol to enforce the norm bound on the witness.
In this paper, we elevate this idea to efficiently proving multiple polynomial relations without relaxation.
Simply incorporating the techniques from $\mathsf{LatticeFold}$ into $\Sigma$-protocols leads to inefficient results;
therefore, we introduce several new techniques to ensure efficiency.
First, to enable the amortization in [AC20] for multiple polynomial relations,
we propose a general linearization technique to reduce polynomial relations to homomorphic ones.
Furthermore, we generalize the folding protocol in LatticeFold, enabling us to efficiently perform folding and other complex operations multiple times without the need to repeatedly execute sum-checks. Moreover, we achieve zero-knowledge by designing
hiding claims and elevating the zero-knowledge sum-check protocol [XZZ+19] on rings.
Our protocol achieves standard soundness, thereby enabling the efficient integration of the compressed $\Sigma$-protocol theory [AC20, ACF21] in lattice settings.



## 2025/314

* Title: Towards Optimally Secure Deterministic Authenticated Encryption Schemes
* Authors: Yu Long Chen, Avijit Dutta, Ashwin Jha, Mridul Nandi
* [Permalink](https://eprint.iacr.org/2025/314)
* [Download](https://eprint.iacr.org/2025/314.pdf)

### Abstract

The public comments received for the review process for NIST (SP) 800-38A pointed out two important issues that most companies face: (1) the limited security that AES can provide due to its 128-bit block size and (2) the problem of nonce-misuse in
practice. In this paper, we provide an alternative solution to these problems by introducing two optimally secure deterministic authenticated encryption (DAE) schemes, denoted as DENC1 and DENC2 respectively. We show that our proposed constructions
improve the state-of-the-art in terms of security and efficiency. Specifically, DENC1 achieves a robust security level of $O(r^2\sigma^2\ell/2^{2n})$, while DENC2 attains a near-optimal security level of $O(r\sigma/2^{n})$, where $\sigma$ is the total
number of blocks, $\ell$ is maximum number of blocks in each query, and $r$ is a user-defined parameter closely related to the rate of the construction. Our research centers on the development of two IV-based encryption schemes, referred to as IV1 and
IV2, which respectively offer security levels of $O(r^2\sigma^2\ell/2^{2n})$ and $O(r\sigma/2^{n})$. Notably, both of our DAE proposals are nearly rate 1/2 constructions. In terms of efficiency, our proposals compare favorably with state-of-the-art AE
modes on contemporary microprocessors.



## 2025/315

* Title: Cryptanalysis of Full SCARF
* Authors: Antonio Flórez-Gutiérrez, Eran Lambooij, Gaëtan Leurent, Håvard Raddum, Tyge Tiessen, Michiel Verbauwhede
* [Permalink](https://eprint.iacr.org/2025/315)
* [Download](https://eprint.iacr.org/2025/315.pdf)

### Abstract

SCARF is a tweakable block cipher dedicated to cache address randomization, proposed at the USENIX Security conference. It has a 10-bit block, 48-bit tweak, and 240-bit key. SCARF is aggressively optimized to meet the harsh latency constraints of cache
address randomization, and uses a dedicated model for its security claim.
The full version of SCARF has 8 rounds, and its designers claim security up to $2^{40}$ queries and $2^{80}$ computations. In this work we present a distinguisher against 6-round SCARF under the collision model with time and query complexity $2^{30}$,
and a key-recovery attack against the full 8-round SCARF under the encryption-decryption model with $2^{39}$ queries and time $2^{76.2}$. As part of the attack, we present a novel method to compute the minimal number of right pairs following a
differential characteristic when the input pairs are restricted to a subspace of the domain of the primitive.



## 2025/316

* Title: $\mathsf{Zinc}$: Succinct Arguments with Small Arithmetization Overheads from IOPs of Proximity to the Integers
* Authors: Albert Garreta, Hendrik Waldner, Katerina Hristova, Luca Dall'Ava
* [Permalink](https://eprint.iacr.org/2025/316)
* [Download](https://eprint.iacr.org/2025/316.pdf)

### Abstract

We introduce $\mathsf{Zinc}$, a hash-based succinct argument for integer arithmetic. $\mathsf{Zinc}$'s goal is to provide a practically efficient scheme that bypasses the arithmetization overheads that many succinct arguments present. These overheads
can be of orders of magnitude in many applications. By enabling proving statements over the integers, we are able to arithmetize many operations of interest with almost no overhead. This includes modular operations involving any moduli, not necessarily
prime, and possibly involving multiple moduli in the same statement. In particular, $\mathsf{Zinc}$ allows to prove statements for the ring $\mathbb{Z}/n\mathbb{Z}$ for arbitrary $n\geq 1$. Importantly, and departing from prior work, our schemes are
purely code and hash-based, and do not require hidden order groups. In its final form, $\mathsf{Zinc}$ operates similarly to other hash-based schemes using Brakedown as their PCS, and at the same time it benefits from the arithmetization perks brought by
working over $\mathbb{Z}$ (and $\mathbb{Q}$) natively.

At its core, $\mathsf{Zinc}$ is a succinct argument for proving relations over the rational numbers $\mathbb{Q}$, even though when applied to integer statements, an honest prover and verifier will only operate with small integers. $\mathsf{Zinc}$
consists of two main components: 1) $\mathsf{Zinc}$-$\mathsf{PIOP}$, a framework for proving algebraic statements over the rationals by reducing modulo a randomly chosen prime $q$, followed by running a suitable PIOP over $\mathbb{F}_q$ (this is similar
to the approach taken in prior works, with the difference that we use localizations of $\mathbb{Q}$ to enable prime modular projection); and 2) $\mathsf{Zip}$, a Brakedown-type polynomial commitment scheme built from an IOP of proximity to the integers,
a novel primitive that we introduce. The latter primitive guarantees that a prover is using a polynomial with coefficients close to being integral. With these two primitives in place, one can use a lookup argument over the rationals to ensure that the
witness contains only integer elements.



## 2025/317

* Title: Minicrypt PIR for Big Batches
* Authors: Nico Döttling, Jesko Dujmovic, Julian Loss, Maciej Obremski
* [Permalink](https://eprint.iacr.org/2025/317)
* [Download](https://eprint.iacr.org/2025/317.pdf)

### Abstract

We present PIR protocols for offline/online two-server setting where a client $C$ wants to privately retrieve a batch of entries from database of size $N$ by interacting with a servers $S_1$. The client has interacted with a server $S_2$ ahead of time,
not colluding with $S_1$. We present simple protocols based on one-way functions that substantially improve on the query complexity or runtime over existing works. Concrete instantiations of our general paradigm lead to batch PIR protocols with the
following parameters:
- A protocol for batches of $\sqrt{N}$, where $C,S_1$, and $S_2$ each spend a total of $\tilde{O}(N)$ work and exchange $\tilde{O}(\sqrt{N})$ bits of communication. This yields an amortized complexity of $\tilde{O}(\sqrt{N})$ work and $\tilde{O}(1)$
communication per query in the batch.
- A more balanced protocol for batches of size $N^{1/3}$ in which $C$ spends a total of $\tilde{O}(N^{2/3})$ work, $S_1$ and $S_2$ spend $\tilde{O}(N)$ work, and the total communication is of size $\tilde{O}(N^{2/3})$.
Our protocols have immediate applications such as Private Set Intersection (PSI) in the two-server setting with preprocessing and unbalanced set sizes.



## 2025/318

* Title: Traceable Verifiable Secret Sharing and Applications
* Authors: Karim Baghery, Ehsan Ebrahimi, Omid Mirzamohammadi, Mahdi Sedaghat
* [Permalink](https://eprint.iacr.org/2025/318)
* [Download](https://eprint.iacr.org/2025/318.pdf)

### Abstract

A secret sharing scheme allows a trusted dealer to divide a secret among multiple parties so that a sufficient number of them can recover the secret, while a smaller group cannot. In CRYPTO'21, Goyal, Song, and Srinivasan introduced Traceable Secret
Sharing (TSS), which enhances traditional secret sharing by enabling the identification of parties involved in secret reconstruction, deterring malicious behavior like selling shares. Recently, Boneh, Partap, and Rotem (CRYPTO'24) presented two more
efficient TSS schemes. However, these existing TSS schemes assume that all distributed shares are valid and shareholders act honestly during the secret reconstruction phase. In this paper, we introduce Traceable Verifiable Secret Sharing (TVSS), a
concept designed to ensure both traceability and verifiability in the face of malicious actions by either the dealer or shareholders. We propose a general strategy for transforming a Shamir-based, computationally secure Verifiable Secret Sharing (VSS)
scheme into an efficient TVSS scheme. Building on this strategy, we construct two practical TVSS schemes in the honest-majority setting, based on well-known VSS schemes proposed by Feldman (SFCS'87) and Pedersen (CRYPTO'91). Our proposed TVSS schemes
retain public shareholder indexes, enhancing flexibility in designing accountable threshold protocols (e.g., Distributed Key Generation protocols) using TVSS. Compared to the original VSS schemes, the individual share size in the new TVSS schemes
increases by only a single field element and is just two or three times the size of the main secret.
Motivated by a recent study on Accountable Threshold Cryptosystems (ATCs) by Boneh, Partap, and Rotem (CRYPTO'24), and by leveraging our proposed Feldman-based TVSS scheme, we also introduce an efficient ATC based on ElGamal cryptosystem. This new ATC
enables a tracer to uniquely identify the parties involved in the decryption process while introducing minimal overhead to existing actively secure (and/or robust) threshold protocols built on the ElGamal cryptosystem.



## 2025/319

* Title: Single Trace Side-Channel Vulnerabilities Discovery Using Statistical Leakage Simulator
* Authors: Jinyi Qiu
* [Permalink](https://eprint.iacr.org/2025/319)
* [Download](https://eprint.iacr.org/2025/319.pdf)

### Abstract

This paper presents a novel single-trace side-channel attack on FALCON—a lattice-based post-quantum digital signature protocol recently approved for standardization by NIST. We target the discrete Gaussian sampling operation within the FALCON key
generation scheme and use a single power measurement trace to succeed. Notably, negating the ‘shift right 63-bit’ operation (for 64-bit values) leaks critical information about the ‘-1’ vs. ‘0’ assignments to intermediate coefficients. These
leaks enable full recovery of the generated secret keys. The proposed attack is simulated on the ELMO simulator running both reference and optimized software implementation from FALCON’s NIST Round 3 package. Statistical analysis with 20k tests reveals
a full key-recovery success rate of 100% for FALCON-512. This work highlights the vulnerability of current software solutions to single-trace attacks and underscores the urgent need to develop single-trace resilient software for embedded systems in the
presilicon phase.



## 2025/320

* Title: Committing Authenticated Encryption: Generic Transforms with Hash Functions
* Authors: Shan Chen, Vukašin Karadžić
* [Permalink](https://eprint.iacr.org/2025/320)
* [Download](https://eprint.iacr.org/2025/320.pdf)

### Abstract

Recent applications and attacks have highlighted the need for authenticated encryption (AE) schemes to achieve the so-called committing security beyond privacy and authenticity. As a result, several generic solutions have been proposed to transform a non-
committing AE scheme to a committing one, for both basic unique-nonce security and advanced misuse-resistant (MR) security. We observe that all existing practical generic transforms are subject to at least one of the following limitations: (i) not
committing to the entire encryption context, (ii) involving non-standard primitives, (iii) not being a black-box transform, (iv) providing limited committing security. Furthermore, so far, there has been no generic transform that can directly elevate a
basic AE scheme to a committing AE scheme that offers MR security. Our work fills these gaps by developing black-box generic transforms that crucially rely on hash functions, which are well standardized and widely deployed.

First, we construct three basic transforms that combine AE with a single hash function, which we call $\mathsf{HtAE}, \mathsf{AEaH}$ and $\mathsf{EtH}$. They all guarantee strong security, and $\mathsf{EtH}$ can be applied to both AE and basic privacy-
only encryption schemes. Next, for MR security, we propose two advanced hash-based transforms that we call $\mathsf{AEtH}$ and $\mathsf{chaSIV}$. $\mathsf{AEtH}$ is an MRAE-preserving transform that adds committing security to an MR-secure AE scheme. $\
mathsf{chaSIV}$ is the first generic transform that can directly elevate basic AE to one with both committing and MR security; moreover, $\mathsf{chaSIV}$ also works with arbitrary privacy-only encryption schemes. Both of them feature a simple design and
ensure strong security.

For performance evaluation, we compare our transforms to similar existing ones, both in theory and through practical implementations. The results show that our $\mathsf{AEaH}$ achieves the highest practical efficiency among basic transforms, while $\
mathsf{AEtH}$ excels in MRAE-preserving transforms. Our MRAE-lifting transform $\mathsf{chaSIV}$ demonstrates comparable performance to MRAE-preserving ones and surpasses them for messages larger than approximately $360$ bytes; for longer messages, it
even outperforms the benchmark, non-committing standardized $\mathsf{AES}\text{-}\mathsf{GCM}\text{-}\mathsf{SIV}$.



## 2025/321

* Title: Differential Cryptanalysis of the Reduced Pointer Authentication Code Function used in Arm’s FEAT_PACQARMA3 Feature
* Authors: Roberto Avanzi, Orr Dunkelman, Shibam Ghosh
* [Permalink](https://eprint.iacr.org/2025/321)
* [Download](https://eprint.iacr.org/2025/321.pdf)

### Abstract

The Pointer Authentication Code ($\textsf{PAC}$) feature in the Arm architecture is used to enforce the Code Flow Integrity ($\textsf{CFI}$) of running programs.
It does so by generating a short $\textsf{MAC}$ - called the $\textsf{PAC}$ - of the return address and some additional context information upon function entry, and checking it upon exit.
An attacker that wants to overwrite the stack with manipulated addresses now faces an additional hurdle, as they now have to guess, forge, or reuse $\textsf{PAC}$ values.
$\textsf{PAC}$ is deployed on billions of devices as a first line of defense to harden system software and complex programs against software exploitation.

The original version of the feature uses a 12-round version the $\textsf{QARMA-64}$ block cipher.
The output is then truncated to between 3 and 32 bits, in order to be inserted into unused bits of 64-bit pointers.
A later revision of the specification allows the use of an 8-round version of $\textsf{QARMA-64}$.
This reduction may introduce vulnerabilities such as high-probability distinguishers, potentially enabling key recovery attacks.
The present paper explores this avenue.

A cryptanalysis of the $\textsf{PAC}$ computation function entails restricting the inputs to valid virtual addresses, meaning that certain most significant bits are fixed to zero,
and considering only the truncated output.
Within these constraints, we present practical attacks on various $\textsf{PAC}$ configurations.
These attacks, while not presenting immediate threat to the $\textsf{PAC}$ mechanism, show that some versions of the feature
do miss the security targets made for the original function.
This offers new insights into the practical security of constructing $\textsf{MAC}$ from truncated block ciphers, expanding on the mostly theoretical understanding of creating PRFs from truncated PRPs.

We note that the results do not affect the security of $\textsf{QARMA-64}$ when used with the recommended number of rounds for general purpose applications.



## 2025/322

* Title: Partial and Fully Homomorphic Matching of IP Addresses Against Blacklists for Threat Analysis
* Authors: William J Buchanan, Hisham Ali
* [Permalink](https://eprint.iacr.org/2025/322)
* [Download](https://eprint.iacr.org/2025/322.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 IP address is a typical identifier which is used to map a network address to a person. 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 convert network addresses into the BFV homomorphic encryption method. In order to assess the performance impact of BFV, it implements a matching method using the OpenFHE library and compares this against the partial
homomorphic methods of 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/323

* Title: A Generic Approach to Adaptively-Secure Broadcast Encryption in the Plain Model
* Authors: Yao-Ching Hsieh, Brent Waters, David J. Wu
* [Permalink](https://eprint.iacr.org/2025/323)
* [Download](https://eprint.iacr.org/2025/323.pdf)

### Abstract

Broadcast encryption allows a user to encrypt a message to $N$ recipients with a ciphertext whose size scales sublinearly with $N$. The natural security notion for broadcast encryption is adaptive security which allows an adversary to choose the set of
recipients after seeing the public parameters. Achieving adaptive security in broadcast encryption is challenging, and in the plain model, the primary technique is the celebrated dual-systems approach, which can be implemented over groups with bilinear
maps. Unfortunately, it has been challenging to replicate the dual-systems approach in other settings (e.g., with lattices or witness encryption). Moreover, even if we focus on pairing-based constructions, the dual-systems framework critically relies on
decisional (and source-group) assumptions. We do not have constructions of adaptively-secure broadcast encryption from search (or target-group) assumptions in the plain model.

Gentry and Waters (EUROCRYPT 2009) described a compiler that takes any semi-statically-secure broadcast encryption scheme and transforms it into an adaptively-secure scheme in the random oracle model. While semi-static security is easier to achieve and
constructions are known from witness encryption as well as search (and target-group) assumptions on pairing groups, the transformed scheme relies on random oracles. In this work, we show that using publicly-sampleable projective PRGs, we can achieve
adaptive security in the plain model. We then show how to build publicly-sampleable projective PRGs from many standard number-theoretic assumptions (e.g., CDH, LWE, RSA).

Our compiler yields the first adaptively-secure broadcast encryption scheme from search assumptions as well as the first such scheme from witness encryption in the plain model. We also obtain the first adaptively-secure pairing-based scheme in the plain
model with $O_\lambda(N)$-size public keys and $O_\lambda(1)$-size ciphertexts (where $O_\lambda(\cdot)$ suppresses polynomial factors in the security parameter $\lambda$). Previous adaptively-secure pairing-based schemes in the plain model with $O_\
lambda(1)$-size ciphertexts required $O_\lambda(N^2)$-size public keys.



## 2025/324

* Title: Fine-Grained Complexity in a World without Cryptography
* Authors: Josh Alman, Yizhi Huang, Kevin Yeo
* [Permalink](https://eprint.iacr.org/2025/324)
* [Download](https://eprint.iacr.org/2025/324.pdf)

### Abstract

The study of fine-grained cryptography has proliferated in recent years due to its allure of potentially relying on weaker assumptions compared to standard cryptography. As fine-grained cryptography only requires polynomial gaps between the adversary and
honest parties, it seems plausible to build primitives relying upon popular hardness assumptions about problems in $\mathbf{P}$ such as $k$-$\mathsf{SUM}$ or $\mathsf{Zero}$-$k$-$\mathsf{Clique}$. The ultimate hope is that fine-grained cryptography could
still be viable even if all current cryptographic assumptions are false, such as if $\mathbf{P} = \mathbf{NP}$ or if we live in Pessiland where one-way functions do not exist.

In our work, we consider whether this approach is viable by studying fine-grained complexity when all standard cryptographic assumptions are false. As our main result, we show that many popular fine-grained complexity problems are easy to solve in the
average-case when one-way functions do not exist. In other words, many candidate hardness assumptions for building fine-grained cryptography are no longer options in Pessiland. As an example, we prove that the average-case $k$-$\mathsf{SUM}$ and $\mathsf{
Zero}$-$k$-$\mathsf{Clique}$ conjectures are false for sufficiently large constant $k$ when no one-way functions exist. The average-case $\mathsf{Zero}$-$k$-$\mathsf{Clique}$ assumption was used to build fine-grained key-exchange by Lavigne et al. [
CRYPTO'19].

We also show that barriers for reductions in fine-grained complexity may be explained by problems in cryptography. First, we show that finding faster algorithms for computing discrete logarithms is equivalent to designing average-case equivalence between
$k$-$\mathsf{SUM}$ and $k$-$\mathsf{CYC}$ (an extension of $k$-$\mathsf{SUM}$ to cyclic groups). In particular, finding such a reduction from $k$-$\mathsf{CYC}$ to $k$-$\mathsf{SUM}$ could potentially lead to breakthrough algorithms for the discrete
logarithm, factoring, RSA and quadratic residuosity problems. Finally, we show that discrete logarithms with preprocessing may be reduced to the $k$-$\mathsf{CYC}$-$\mathsf{Index}$ problem, and we present faster algorithms for average-case $k$-$\mathsf{
SUM}$-$\mathsf{Index}$ and $k$-$\mathsf{CYC}$-$\mathsf{Index}$.



## 2025/325

* Title: On Quantum Money and Evasive Obfuscation
* Authors: Mark Zhandry
* [Permalink](https://eprint.iacr.org/2025/325)
* [Download](https://eprint.iacr.org/2025/325.pdf)

### Abstract

We show a black box barrier against constructing public key quantum money from obfuscation for evasive functions. As current post-quantum obfuscators based on standard assumptions are all evasive, this shows a fundamental barrier to achieving public key
quantum money from standard tools. Our impossibility applies to black box schemes where (1) obfuscation queries made by the mint are classical, and (2) the verifier only makes (possibly quantum) evaluation queries, but no obfuscation queries. This class
seems to capture any natural method of using obfuscation to build quantum money.

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