[continued from previous message]

We overcome all of these issues with a proactive Refresh procedure. Since the Paillier decryption key is part of the secret that must be proactively refreshed, our first improvement is to radically accelerate key generation by replacing one of Lindell's
ZK proofs -- which requires 80 Paillier ciphertexts for statistical security $2^{-40}$ -- with a much faster "weak" proof that requires only 2 Paillier ciphertexts, and which proves a weaker statement about a Paillier ciphertext that we show is
sufficient in the context of our scheme. Secondly, our more efficient key generation procedure also makes frequent proactive Refreshes practical. Finally, we show that adding noise to one party's key share suffices to avoid the need to reset the public
verification key when certain bad behavior is detected. Instead, we prove that our Refresh procedure, performed after each detection, suffices for addressing the attack, allowing the system to continue functioning without disruption to applications that
rely on the verification key.

Our scheme is also very efficient, competitive with the best constructions that do not provide proactive security, and state-of-the-art among the few results that do. Our optimizations to ECDSA key generation speed up runtime and improve bandwidth over
Lindell's key generation by factors of 7 and 13, respectively. Our Key Generation protocol requires 20% less bandwidth than existing constructions, completes in only 3 protocol messages, and executes much faster than all but OT-based key generation. For
ECDSA signing, our extra Refresh protocol does add a 10X latency and 5X bandwidth overhead compared to Lindell. However, this still fits in 150 ms runtime and about 5.4 KB of messages when run in our AWS cluster benchmark.



## 2024/1832

* Title: How to Delete Without a Trace: Certified Deniability in a Quantum World
* Authors: Alper Çakan, Vipul Goyal, Justin Raizes
* [Permalink](https://eprint.iacr.org/2024/1832)
* [Download](https://eprint.iacr.org/2024/1832.pdf)

### Abstract

Is it possible to comprehensively destroy a piece of quantum information, so that nothing is left behind except the memory of that one had it at some point? For example, various works, most recently Morimae, Poremba, and Yamakawa (TQC '24), show how to
construct a signature scheme with certified deletion where a user who deletes a signature on $m$ cannot later produce a signature for $m$. However, in all of the existing schemes, even after deletion the user is still able keep irrefutable evidence that $
m$ was signed, and thus they do not fully capture the spirit of deletion.

In this work, we initiate the study of certified deniability in order to obtain a more comprehensive notion of deletion. Certified deniability uses a simulation-based security definition, ensuring that any information the user has kept after deletion
could have been learned without being given the deleteable object to begin with; meaning that deletion leaves no trace behind! We define and construct two non-interactive primitives that satisfy certified deniability in the quantum random oracle model:
signatures and non-interactive zero-knowledge arguments (NIZKs). As a consequence, for example, it is not possible to delete a signature/NIZK and later provide convincing evidence that it used to exist. Notably, our results utilize uniquely quantum
phenomena to bypass Pass's (CRYPTO '03) celebrated result showing that deniable NIZKs are impossible even in the random oracle model.



## 2024/1833

* Title: Private Neural Network Training with Packed Secret Sharing
* Authors: Hengcheng Zhou
* [Permalink](https://eprint.iacr.org/2024/1833)
* [Download](https://eprint.iacr.org/2024/1833.pdf)

### Abstract

We present a novel approach for training neural networks that leverages packed Shamir secret sharing scheme. For specific training protocols based on Shamir scheme, we demonstrate how to realize the conversion between packed sharing and Shamir sharing
without additional communication overhead. We begin by introducing a method to locally convert between Shamir sharings with secrets stored at different slots. Building upon this conversion, we achieve free conversion from packed sharing to Shamir sharing.
We then show how to embed the conversion from Shamir sharing to packed sharing into the truncation used during the training process without incurring additional communication costs. With free conversion between packed sharing and Shamir sharing, we
illustrate how to utilize the packed scheme to parallelize certain computational steps involved in neural network training. On this basis, we propose training protocols with information-theoretic security between general $n$ parties under the semi-honest
model. The experimental results demonstrate that, compared to previous work in this domain, applying the packed scheme can effectively improve training efficiency. Specifically, when packing $4$ secrets into a single sharing, we observe a reduction of
more than $20\%$ in communication overhead and an improvement of over $10\%$ in training speed under the WAN setting.



## 2024/1834

* Title: Scutum: Temporal Verification for Cross-Rollup Bridges via Goal-Driven Reduction
* Authors: Yanju Chen, Juson Xia, Bo Wen, Kyle Charbonnet, Hongbo Wen, Hanzhi Liu, Yu Feng
* [Permalink](https://eprint.iacr.org/2024/1834)
* [Download](https://eprint.iacr.org/2024/1834.pdf)

### Abstract

Scalability remains a key challenge for blockchain adoption. Rollups—especially zero-knowledge (ZK) and optimistic rollups—address this by processing transactions off-chain while maintaining Ethereum’s security, thus reducing gas fees and improving
speeds. Cross-rollup bridges like Orbiter Finance enable seamless asset transfers across various Layer 2 (L2) rollups and between L2 and Layer 1 (L1) chains. However, the increasing reliance on these bridges raises significant security concerns, as
evidenced by major hacks like those of Poly Network and Nomad Bridge, resulting in losses of hundreds of millions of dollars. Traditional security analysis methods such as static analysis and fuzzing are inadequate for cross-rollup bridges due to their
complex designs involving multiple entities, smart contracts, and zero-knowledge circuits. These systems require reasoning about temporal sequences of events across different entities, which exceeds the capabilities of conventional analyzers.
In this paper, we introduce a scalable verifier to systematically assess the security of cross-rollup bridges. Our approach features a comprehensive multi-model framework that captures both individual behaviors and complex interactions using temporal
properties. To enhance scalability, we approximate temporal safety verification through reachability analysis of a graph representation of the contracts, leveraging advanced program analysis techniques. Additionally, we incorporate a conflict-driven
refinement loop to eliminate false positives and improve precision. Our evaluation on mainstream cross-rollup bridges, including Orbiter Finance, uncovered multiple zero-day vulnerabilities, demonstrating the practical utility of our method. The tool
also exhibited favorable runtime performance, enabling efficient analysis suitable for real-time or near-real-time applications.



## 2024/1835

* Title: Hybrid Zero-Knowledge from Garbled Circuits
* Authors: Masayuki Abe, Miguel Ambrona, Miyako Ohkubo
* [Permalink](https://eprint.iacr.org/2024/1835)
* [Download](https://eprint.iacr.org/2024/1835.pdf)

### Abstract

We present techniques for constructing zero-knowledge argument systems from garbled circuits, extending the GC-to-ZK compiler by Jawurek, Kerschbaum, and Orlandi (ACM CCS 2023) and the GC-to-Σ compiler by Hazay and Venkitasubramaniam (J. Crypto, 2020)
to the following directions:

- Our schemes are hybrid, commit-and-prove zero-knowledge argument systems that establish a connection between secrets embedded in algebraic commitments and a relation represented by a Boolean circuit.
- Our schemes incorporate diverse cross-domain secrets embedded within distinct algebraic commitments, simultaneously supporting Pedersen-like commitments and lattice-based commitments.

As an application, we develop circuit-represented compositions of Σ-protocols that support attractive access structures, such as weighted thresholds, that can be easily represented by a small circuit. For predicates P1, . . . , Pn individually
associated with a Σ-protocol, and a predicate C represented by a Boolean circuit, we construct a Σ-protocol for proving C(P1, . . . , Pn) = 1. This result answers positively an open question posed by Abe, et. al., at TCC 2021.



## 2024/1836

* Title: Symmetric Encryption on a Quantum Computer
* Authors: David Garvin, Oleksiy Kondratyev, Alexander Lipton, Marco Paini
* [Permalink](https://eprint.iacr.org/2024/1836)
* [Download](https://eprint.iacr.org/2024/1836.pdf)

### Abstract

Classical symmetric encryption algorithms use $N$ bits of a shared
secret key to transmit $N$ bits of a message over a one-way channel in
an information theoretically secure manner. This paper proposes a hybrid quantum-classical symmetric cryptosystem that uses a quantum computer to generate the secret key. The algorithm leverages quantum circuits to
encrypt a message using a one-time pad-type technique whilst requiring
a shorter classical key. We show that for an $N$-qubit circuit, the
maximum number of bits needed to specify a quantum circuit grows as
$N^{3/2}$ while the maximum number of bits that the quantum circuit
can encode grows as $N^2$. We do not utilise the full expressive
capability of the quantum circuits as we focus on second order Pauli expectation values only. The potential exists to encode an exponential
number of bits using higher orders of Pauli expectation values.
Moreover, using a parameterised quantum circuit (PQC), we could
further augment the amount of securely shared information by
introducing a secret key dependence on some of the PQC parameters.
The algorithm may be suitable for an early fault-tolerant quantum
computer implementation as some degree of noise can be tolerated.
Simulation results are presented along with experimental results on
the 84-qubit Rigetti Ankaa-2 quantum computer.



## 2024/1837

* Title: A Query Reconstruction Attack on the Chase-Shen Substring-Searchable Symmetric Encryption Scheme
* Authors: Zichen Gui, Kenneth G. Paterson, Sikhar Patranabis
* [Permalink](https://eprint.iacr.org/2024/1837)
* [Download](https://eprint.iacr.org/2024/1837.pdf)

### Abstract

Searchable symmetric encryption (SSE) enables queries over symmetrically encrypted databases. To achieve practical efficiency, SSE schemes incur a certain amount of leakage; however, this leads to the possibility of leakage cryptanalysis, i.e.,
cryptanalytic attacks that exploit the leakage from the target SSE scheme to subvert its data and query privacy guarantees. Leakage cryptanalysis has been widely studied in the context of SSE schemes supporting either keyword queries or range queries,
often with devastating consequences. However, little or no attention has been paid to cryptanalysing substring-SSE schemes, i.e., SSE schemes supporting arbitrary substring queries over encrypted data. This is despite their relevance to many real-world
applications, e.g., in the context of securely querying outsourced genomic databases. In particular, the first ever substring-SSE scheme, proposed nearly a decade ago by Chase and Shen (PoPETS '15), has not been cryptanalysed to date.

In this paper, we present the first leakage cryptanalysis of the substring-SSE scheme of Chase and Shen. We propose a novel inference-based query reconstruction attack that: (i) exploits a reduced version of the actual leakage profile of their scheme,
and (ii) assumes a weaker attack model as compared to the one in which Chase and Shen originally claimed security. We implement our attack and experimentally validate its success rate and efficiency over two real-world datasets. Our attack achieves high
query reconstruction rate with practical efficiency, and scales smoothly to large datasets containing $100,000$ strings.

To the best of our knowledge, ours is the first and only query reconstruction attack on (and the first systematic leakage cryptanalysis of) any substring-SSE scheme till date.



## 2024/1838

* Title: Pushing the QAM method for finding APN functions further
* Authors: Nadiia Ichanska, Simon Berg, Nikolay S. Kaleyski, Yuyin Yu
* [Permalink](https://eprint.iacr.org/2024/1838)
* [Download](https://eprint.iacr.org/2024/1838.pdf)

### Abstract

APN functions offer optimal resistance to differential attacks and are instrumental in the design of block ciphers in cryptography. While finding APN functions is very difficult in general, a promising way to construct APN functions is through symmetric
matrices called Quadratic APN matrices (QAM). It is known that the search space for the QAM method can be reduced by means of orbit partitions induced by linear equivalences. This paper builds upon and improves these approaches in the case of homogeneous
quadratic functions over $\mathbb{F}_{2^n}$ with coefficients in the subfield $\mathbb{F}_{2^m}$. We propose an innovative approach for computing orbit partitions for cases where it is infeasible due to the large search space, resulting in the
applications for the dimensions $(n,m)=(8,4)$, and $(n,m)=(9,3)$. We find and classify, up to CCZ-equivalence, all quadratic APN functions for the cases of $(n,m)=(8,2),$ and $(n,m)=(10,1)$, discovering a new APN function in dimension $8$. Also, we show
that an exhaustive search for $(n,m) = (10,2)$ is infeasible for the QAM method using currently available means, following partial searches for this case.



## 2024/1839

* Title: Cryptographically Secure Digital Consent
* Authors: F. Betül Durak, Abdullah Talayhan, Serge Vaudenay
* [Permalink](https://eprint.iacr.org/2024/1839)
* [Download](https://eprint.iacr.org/2024/1839.pdf)

### Abstract

In the digital age, the concept of consent for online actions executed by third parties is crucial for maintaining trust and security in third-party services.
This work introduces the notion of cryptographically secure digital consent, which aims to replicate the traditional consent process in the online world.
We provide a flexible digital consent solution that accommodates different use cases and ensures the integrity of the consent process.

The proposed framework involves a client (referring to the user or their devices), an identity manager (which authenticates the client), and an agent (which executes the action upon receiving consent).
It supports various applications and ensures compatibility with existing identity managers.
We require the client to keep no more than a password. The design addresses several security and privacy challenges, including preventing offline dictionary attacks, ensuring non-repudiable consent, and preventing unauthorized actions by the agent.
Security is maintained even if either the identity manager or the agent is compromised, but not both.

Our notion of an identity manager is broad enough to include combinations of different authentication factors such as a password, a smartphone, a security device, biometrics, or an e-passport. We demonstrate applications for signing PDF documents, e-
banking, and key recovery.



## 2024/1840

* Title: Ideal Pseudorandom Codes
* Authors: Omar Alrabiah, Prabhanjan Ananth, Miranda Christ, Yevgeniy Dodis, Sam Gunn
* [Permalink](https://eprint.iacr.org/2024/1840)
* [Download](https://eprint.iacr.org/2024/1840.pdf)

### Abstract

Pseudorandom codes are error-correcting codes with the property that no efficient adversary can distinguish encodings from uniformly random strings. They were recently introduced by Christ and Gunn [CRYPTO 2024] for the purpose of watermarking the
outputs of randomized algorithms, such as generative AI models. Several constructions of pseudorandom codes have since been proposed, but none of them are robust to error channels that depend on previously seen codewords. This stronger kind of robustness
is referred to as adaptive robustness, and it is important for meaningful applications to watermarking.

In this work, we show the following.
- Adaptive robustness: We show that the pseudorandom codes of Christ and Gunn are adaptively robust, resolving a conjecture posed by Cohen, Hoover, and Schoenbach [S&P 2025]. Our proof involves several new ingredients, combining ideas from both
cryptography and coding theory and taking hints from the analysis of Boolean functions.
- Ideal security: We define an ideal pseudorandom code as one which is indistinguishable from the ideal functionality, capturing both the pseudorandomness and robustness properties in one simple definition. We show that any adaptively robust pseudorandom
code for single-bit messages can be bootstrapped to build an ideal pseudorandom code with linear information rate, under no additional assumptions.
- CCA security: In the setting where the encoding key is made public, we define a CCA-secure pseudorandom code in analogy with CCA-secure encryption. We show that any adaptively robust public-key pseudorandom code for single-bit messages can be used to
build a CCA-secure pseudorandom code with linear information rate, in the random oracle model.

Together with the result of Christ and Gunn, it follows that there exist ideal pseudorandom codes assuming the $2^{O(\sqrt{n})}$-hardness of LPN. This extends to CCA security in the random oracle model. These results immediately imply stronger robustness
guarantees for generative AI watermarking schemes, such as the practical quality-preserving image watermarks of Gunn, Zhao, and Song (2024).



## 2024/1841

* Title: Verifying Jolt zkVM Lookup Semantics
* Authors: Carl Kwan, Quang Dao, Justin Thaler
* [Permalink](https://eprint.iacr.org/2024/1841)
* [Download](https://eprint.iacr.org/2024/1841.pdf)

### Abstract

Lookups are a popular way to express repeated constraints in state-of-the art SNARKs. This is especially the case for zero-knowledge virtual machines (zkVMs), which produce succinct proofs of correct execution for programs expressed as bytecode according
to a specific instruction set architecture (ISA). The Jolt zkVM (Arun, Setty & Thaler, Eurocrypt 2024) for RISC-V ISA employs Lasso (Setty, Thaler & Wahby, Eurocrypt 2024), an efficient lookup argument for massive structured tables, to prove correct
execution of instructions. Internally, Lasso performs multiple lookups into smaller subtables, then combines the results.

We present an approach to formally verify Lasso-style lookup arguments against the semantics of instruction set architectures. We demonstrate our approach by formalizing and verifying all Jolt 32-bit instructions corresponding to the RISC-V base
instruction set (RV32I) using the ACL2 theorem proving system. Our formal ACL2 model has undergone extensive validation against the Rust implementation of Jolt. Due to ACL2's bit-blasting, rewriting, and developer-friendly features, our formalization is
highly automated.

Through formalization, we also discovered optimizations to the Jolt codebase, leading to improved efficiency without impacting correctness or soundness. In particular, we removed one unnecessary lookup each for four instructions, and reduced the sizes of
three subtables by 87.5\%.



## 2024/1842

* Title: Zero-Knowledge Location Privacy via Accurate Floating-Point SNARKs
* Authors: Jens Ernstberger, Chengru Zhang, Luca Ciprian, Philipp Jovanovic, Sebastian Steinhorst
* [Permalink](https://eprint.iacr.org/2024/1842)
* [Download](https://eprint.iacr.org/2024/1842.pdf)

### Abstract

We introduce Zero-Knowledge Location Privacy (ZKLP), enabling users to prove to third parties that they are within a specified geographical region while not disclosing their exact location. ZKLP supports varying levels of granularity, allowing for
customization depending on the use case. To realize ZKLP, we introduce the first set of Zero-Knowledge Proof (ZKP) circuits that are fully compliant to the IEEE 754 standard for floating-point arithmetic.
Our results demonstrate that our floating point circuits amortize efficiently, requiring only $64$ constraints per multiplication for $2^{15}$ single-precision floating-point multiplications. We utilize our floating point implementation to realize the
ZKLP paradigm. In comparison to a baseline, we find that our optimized implementation has $15.9 \times$ less constraints utilizing single precision floating-point values, and $12.2 \times$ less constraints when utilizing double precision floating-point
values. We demonstrate the practicability of ZKLP by building a protocol for privacy preserving peer-to-peer proximity testing - Alice can test if she is close to Bob by receiving a single message, without either party revealing any other information
about their location. In such a configuration, Bob can create a proof of (non-)proximity in $0.26 s$, whereas Alice can verify her distance to about $470$ peers per second.



## 2024/1843

* Title: Khatam: Reducing the Communication Complexity of Code-Based SNARKs
* Authors: Hadas Zeilberger
* [Permalink](https://eprint.iacr.org/2024/1843)
* [Download](https://eprint.iacr.org/2024/1843.pdf)

### Abstract

We prove that Basefold(Crypto 2024) is secure in the $\textit{list decoding regime}$, within the double Johnson bound and with error probability $\frac{O(n)}{|F|}$. At the heart of this proof is a new, stronger statement for $\textit{correlated agreement}
$, which roughly states that if a linear combination of vectors $\pi_L + r \pi_R$ agrees with a codeword at every element in $S \subset [n]$, then so do $\pi_L, \pi_R$. Our result is purely combinatorial and therefore extends to any finite field and any
linear code. As such, it can be applied to any coding-based multilinear Polynomial Commitment Scheme to reduce its communication complexity.



## 2024/1844

* Title: KLaPoTi: An asymptotically efficient isogeny group action from 2-dimensional isogenies
* Authors: Lorenz Panny, Christophe Petit, Miha Stopar
* [Permalink](https://eprint.iacr.org/2024/1844)
* [Download](https://eprint.iacr.org/2024/1844.pdf)

### Abstract

We construct and implement an efficient post-quantum commutative cryptographic group action based on combining the SCALLOP framework for group actions from isogenies of oriented elliptic curves on one hand with the recent Clapoti method for polynomial-
time evaluation of the CM group action on elliptic curves on the other.
We take advantage of the very attractive performance of $(2^e, 2^e)$-isogenies between products of elliptic curves in the theta coordinate system.
To successfully apply Clapoti in dimension $2$, it is required to resolve a particular quadratic diophantine norm equation, for which we employ a slight variant of the KLPT algorithm.
Our work marks the first practical instantiation of the CM group action for which both the setup as well as the online phase can be computed in (heuristic) polynomial time.



## 2024/1845

* Title: Single-Server Client Preprocessing PIR with Tight Space-Time Trade-off
* Authors: Zhikun Wang, Ling Ren
* [Permalink](https://eprint.iacr.org/2024/1845)
* [Download](https://eprint.iacr.org/2024/1845.pdf)

### Abstract

This paper partly solves the open problem of tight trade-off of client storage and server time in the client preprocessing setting of private information retrieval (PIR). In the client preprocessing setting of PIR, the client is allowed to store some
hints generated from the database in a preprocessing phase and use the hints to assist online queries. We construct a new single-server client preprocessing PIR scheme. For a database with $n$ entries of size $w$, our protocol uses $S=O((n/T) \cdot (\log
n + w))$ bits of client storage and $T$ amortized server probes over $n/T$ queries, where $T$ is a tunable online time parameter. Our scheme matches (up to constant factors) a $ST = \Omega(nw)$ lower bound generalized from a recent work by Yeo (EUROCRYPT
2023) and a communication barrier generalized from Ishai, Shi, and Wichs (CRYPTO 2024).

From a technical standpoint, we present a novel organization of hints where each PIR query consumes a hint, and entries in the consumed hint are relocated to other hints. We then present a new data structure to track the hint relocations and use small-
domain pseudorandom permutations to make the hint storage sublinear while maintaining efficient lookups in the hints.



## 2024/1846

* Title: The LaZer Library: Lattice-Based Zero Knowledge and Succinct Proofs for Quantum-Safe Privacy
* Authors: Vadim Lyubashevsky, Gregor Seiler, Patrick Steuer
* [Permalink](https://eprint.iacr.org/2024/1846)
* [Download](https://eprint.iacr.org/2024/1846.pdf)

### Abstract

The hardness of lattice problems offers one of the most promising
security foundations for quantum-safe cryptography. Basic schemes
for public key encryption and digital signatures are already close to standardization at NIST and several other standardization bodies,
and the research frontier has moved on to building primitives with
more advanced privacy features. At the core of many such primi-
tives are zero-knowledge proofs. In recent years, zero-knowledge
proofs for (and using) lattice relations have seen a dramatic jump
in efficiency and they currently provide arguably the shortest, and
most computationally efficient, quantum-safe proofs for many sce-
narios. The main difficulty in using these proofs by non-experts
(and experts!) is that they have a lot of moving parts and a lot of
internal parameters depend on the particular instance that one is
trying to prove.
Our main contribution is a library for zero-knowledge and suc-
cinct proofs which consists of efficient and flexible C code under-
neath a simple-to-use Python interface. Users without any back-
ground in lattice-based proofs should be able to specify the lattice
relations and the norm bounds that they would like to prove and the
library will automatically create a proof system, complete with the
intrinsic parameters, using either the succinct proofs of LaBRADOR
(Beullens and Seiler, Crypto 2023) or the linear-size, though smaller
for certain application, proofs of Lyubashevsky et al. (Crypto 2022).
The Python interface also allows for common operations used in
lattice-based cryptography which will enable users to write and pro-
totype their full protocols within the syntactically simple Python
environment.
We showcase some of the library’s usefulness by giving protocol implementations for blind signatures, anonymous credentials, the
zero-knowledge proof needed in the recent Swoosh protocol (Gaj-
land et al., Usenix 2024), proving knowledge of Kyber keys, and an
aggregate signature scheme. Most of these are the most efficient,
from a size, speed, and memory perspective, known quantum-safe
instantiations.



## 2024/1847

* Title: Notions of Quantum Reductions and Impossibility of Statistical NIZK
* Authors: Chuhan Lu, Nikhil Pappu
* [Permalink](https://eprint.iacr.org/2024/1847)
* [Download](https://eprint.iacr.org/2024/1847.pdf)

### Abstract

Non-Interactive Zero-Knowledge Arguments (NIZKs) are cryptographic protocols that enable a prover to demonstrate the validity of an $\mathsf{NP}$ statement to a verifier with a single message, without revealing any additional information. The soundness
and zero-knowledge properties of a NIZK correspond to security against a malicious prover and a malicious verifier respectively. Statistical NIZKs (S-NIZKs) are a variant of NIZKs for which the zero-knowledge property is guaranteed to hold information-
theoretically. Previous works have shown that S-NIZKs satisfying a weak version of soundness known as static soundness exist based on standard assumptions. However, the work of Pass (TCC 2013) showed that S-NIZKs with the stronger \emph{adaptive}
soundness property are inherently challenging to obtain. The work proved that standard (black-box) proof techniques are insufficient to prove the security of an S-NIZK based on any standard (falsifiable)
assumption. We extend this result to the setting where parties can perform quantum computations and communicate using quantum information, while the quantum security reduction is restricted to query the adversary classically. To this end, we adapt the
well-known meta-reduction paradigm for showing impossibility results to the quantum setting. Additionally, we reinterpret our result using a new framework for studying quantum reductions, which we believe to be of independent interest.



## 2024/1848

* Title: Non-Interactive Zero-Knowledge Proofs with Certified Deletion
* Authors: Kasra Abbaszadeh, Jonathan Katz
* [Permalink](https://eprint.iacr.org/2024/1848)
* [Download](https://eprint.iacr.org/2024/1848.pdf)

### Abstract

We introduce the notion of non-interactive zero-knowledge (NIZK) proofs with certified deletion. Our notion enables the recipient of a quantum NIZK proof for a (quantumly hard) NP statement to delete the proof and collapse it into a classical deletion
certificate. Once this certificate is successfully validated, we require the recipient of the proof to lose their ability to find accepting inputs to NIZK verification.

We formally define this notion and build several candidate constructions from standard cryptographic assumptions. In particular, we propose a primary construction from classical NIZK for NP and one-way functions, albeit with two limitations: (i) deletion
certificates are only privately verifiable, and (ii) both prover and verifier are required to be quantum algorithms. We resolve these hurdles in two extensions that assume the quantum hardness of the learning with errors problem. The first one achieves
publicly verifiable certificates, and the second one requires merely classical communication between classical provers and quantum verifiers.

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