CS Paper Radar

Constant-Rate Certified Deletion

Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada

cs.CR quant-ph ·submitted 2026-10-02 16:58 UTC · v1
top venue

Abstract

We present a unified framework for upgrading a broad class of cryptographic primitives to support constant-rate certified deletion. Previous constructions require a linear number of qubits per encrypted bit of certified-deletable plaintext. In contrast, we obtain the first constant-rate constructions in the plain model that achieve certified deletion while preserving everlasting security. Our approach applies to a wide range of "all-or-nothing"-type primitives based on BB84-style encodings, including commitment schemes, public-key encryption, attribute-based encryption, and fully homomorphic encryption. Beyond this class, we also obtain constant-rate certified deletion for primitives built from subspace coset states, such as blind delegation, secure software leasing, functional encryption, and differing-inputs iO, and CCA-PKE. Importantly, our framework does not introduce any additional assumptions beyond those required by the underlying certified deletion primitives. Finally, under the hardness of SIS, we show that public verifiability can be incorporated into BB84- and coset-based certified deletion. In combination with our constant-rate constructions, this yields publicly verifiable certified deletion schemes with constant rate.

Closest papers

Nearest neighbours by meaning across the whole index.

Semi-Quantum Cryptography with Certified Deletion

cs.CR quant-ph ·2026-09-30 ·Yael Tauman Kalai, Justin Raizes
similarity 0.80
Abstract

Certified deletion allows a client to upload encrypted data to a server as a quantum state, then later request that the server delete their data and detect whether the server complies. If verification passes, then the data on the server will remain hidden even if the decryption key is later leaked. In publicly verifiable certified deletion, the verification key is published so that anyone may check for deletion compliance. In this work, we give a general compiler to publicly verifiable certified deletion that allows the client to initially upload the *quantum* ciphertext using purely *classical* communication, assuming the post-quantum hardness of LWE in the plain model. Our approach can be applied to a wide variety of primitives, including commitments and public-key, attribute-based, identity-based, and fully-homomorphic encryption. Moreover, our constructions allow the client to classically manage the encrypted data beyond just verifying its deletion. The classical client may non-destructively audit the ciphertext via a Proof of No Intrusion to check whether it has been leaked to a third party. The classical client may also retrieve the data while simultaneously verifying its deletion from the server. Thus, they do not have to choose between retrieving the data and protecting it against future key leakage. As our core technical contribution, we give a classical-communication protocol and simulation technique that allows adapting purification-based security arguments for BB84-style states which are prepared through classical interaction. It makes the required purification available in a hybrid experiment, despite the classical transcript uniquely determining the prepared state in a real execution.

0.25

zk-DEAP: A Zero-Knowledge Decentralized Encrypted Aggregation Protocol

cs.CR ·2026-11-04 ·Jude Ramanan, Georgiana Haldeman, Noah Apthorpe
similarity 0.68
Abstract · 19 pages, 5 figures, 5 tables

Secure aggregation in domains such as federated learning, Internet of Things, and voting requires operating on private inputs while preserving confidentiality, verifying that each input satisfies constraints, and avoiding trusted parties. Existing protocols achieve at most two of these requirements. We present zk-DEAP, a protocol combining lifted ElGamal homomorphic encryption, FROST threshold cryptography, and zero-knowledge proofs (Bulletproofs, zk-SNARKs, or zk-STARKs) for fully decentralized, verifiable, privacy-preserving aggregation. Our core technical contribution is a cryptographic binding mechanism preventing substitution attacks, where a valid proof for one input is paired with a ciphertext encrypting a different, malicious value. For Bulletproofs, we bind via ciphertext-derived randomness modification. For zk-SNARKs/zk-STARKs, to bind across algebraic structures (a well-known challenge in practical cryptography), we introduce a novel blinded arithmetic hash commitment with an embedded Schnorr constraint. These binding techniques force the ZKP's private witness to equal the encrypted value, ensuring any circuit-verified constraint applies to the ciphertext. We implement three production-ready, defense-in-depth variants in Rust and evaluate across 5-500 participants. Compared to unverified aggregation, zk-DEAP adds modest overhead while providing cryptographic guarantees against input manipulation that statistical defenses cannot match.

0.28

Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS

cs.CR ·2026-11-12 ·Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Dario Fiore, Antonio Guimarães +1 more
publishedhot direction similarity 0.66
Abstract · Full version of a paper accepted at ASIACRYPT 2026. 92 pages

An important challenge in homomorphic encryption (HE) is ensuring the integrity of the encrypted computations. Although verifiable computation can address this in theory, making it practical is far from trivial. [Cascudo et al. CRYPTO 2025] recently proposed a solution to this problem for the CKKS scheme. In particular, they propose new succinct arguments that efficiently prove arithmetic circuits and range checks over the ring $R_q = \mathbb{Z}_q[Y]/(Y^N+1)$, and combine them to prove computations on CKKS ciphertexts. Despite the important progress, their work faces scalability challenges: the size of the polynomial commitment proofs, a large $O(N)$ overhead in range proofs, and the lack of an explicit method for efficient -- sublinear in circuit size -- verification. In this paper we present new techniques that remove all these bottlenecks. First, we provide a more efficient arithmetization of CKKS computations. Second, we introduce BatchFold, a new polynomial commitment for $R_q$ that supports batched evaluations and achieves shorter proofs. Third, we design packing, a novel algebraic technique that eliminates the need to commit to massive polynomials and removes the $O(N)$ overhead in range proofs. Finally, we introduce SparsePack, an efficient protocol for proving the evaluations of sparse, circuit-dependent polynomials, leveraging both packing and batched evaluations. We evaluate the efficiency of our solution on a generic neural network architecture, achieving proofs several orders of magnitude smaller and faster than prior approaches.

0.70

On the Construction of Trapdoor Claw-Free Functions with Certifiable Key

cs.CR quant-ph ·2026-09-22 ·Charles Lim, Yao Ma
similarity 0.65
Abstract

Trapdoor claw-free functions (TCFs) underpin much of classical-quantum cryptographic interaction, yet every TCF-based protocol states its guarantees relative to an honestly generated key. We give a family-agnostic abstraction of key certification for (noisy) TCF constructions, built on two notions: a certifiable key relation, an NP relation capturing a family's honest keys with witnesses recoverable from the trapdoor; and certified key generation, which emits with each key a certificate of membership satisfying completeness, certificate soundness with extractability, and key privacy. We instantiate certifiable key relations for different constructions, each met generically by a zero-knowledge argument of knowledge for the relation. As our main application, a generic compiler turns any TCF-based proof of quantumness into a zero-knowledge one, with each security property following from its counterpart in the certification scheme. Finally, we delimit the primitive's reach: for protocols resting on injective invariance, an accepting certificate is itself a family distinguisher, leaking exactly the bit such protocols must hide.

0.24

Z-Sigil: A Public-Key Cryptosystem with Chained Selection over a Fiber Bundle of Module-Lattice Keys

cs.CR cs.IT ·2026-09-29 ·Andrea Rondelli
theoryhot direction similarity 0.64
Abstract

Z-Sigil is a public-key cryptosystem in which the plaintext selects successive keys from a fixed module-lattice family. Messages are length-prefixed, zero-padded and divided into 32-byte blocks. Each public vector is a shared public matrix applied to a small secret vector, plus a small error. Key indices label torsion points of a flat Kähler torus; the secret family forms a section of a key bundle over them. A public nonce initializes a hash state that selects each block's key and bit mask. The sender updates the state with the plaintext block; the receiver does so after recovering it. The stream and nonce determine a discrete walk along which decryption reads the secret section. We specify the algorithms, prove correctness under an explicit noise condition and bound decoding failure for messages chosen after the public key. Under stated decisional Module-LWE assumptions, we establish IND-CPA confidentiality for the chain without modelling the state hash as a random oracle. The reduction covers quantum adversaries under quantum hardness assumptions, with classical keys, messages and ciphertexts; no concrete security level is established. With independent uniform selectors, a restricted direct-decryption model quantifies reduced fragment recovery under partial key exposure, without improving full-message recovery probability over an independent-block baseline. Known-plaintext and candidate-message attacks, and parallel candidate-table decryption, delimit this result. Neither a universal sequential lower bound nor authentication or chosen-ciphertext security is established. Replacing an earlier scalar-exposing proposal, we give an augmented-lattice interpretation, integral-transport obstructions and a noise budget for research on curved, nontrivial bundles. A byte-level specification, pseudocode, test vectors and numerical checks support verification.

0.34

Decisional Monogamy-of-Entanglement for Coset States and Applications to Unclonable Cryptography with Correlated Challenges

cs.CR quant-ph ·2026-08-19 ·Amit Behera, Alper Cakan, Vipul Goyal
hot direction similarity 0.63
Abstract

A main application of quantum information in cryptography is copy-protection, where we encode a functionality (such as a decryption key or software) into a reusable quantum state so that it cannot be split into two adversaries (called freeloaders) that both remain useful. Previous works have only shown security for independently sampled challenges for the two adversaries. A competing natural security notion is identical-challenge security where the adversaries receive the same challenge. This notion has many real-life applications and connections to other fundamental primitives such as unclonable bits (i.e. unclonable encryption) and unclonable lockboxes (i.e. copy-protection of point functions). Despite its importance and numerous attempts, achieving identical-challenge security in the plain model has remained open. We first make progress on the definitional foundations of copy-protection by introducing natural copy-protection security definitions that imply the previous ones (including identical-challenge security) and better capture the security intuitions and real-life use cases; and we also characterize the relationship between the previous definitions. Then, we show how to achieve in the plain model our new stronger definitions for copy-protection of general classes of functionalities. In particular, we resolve the long-standing open questions of copy-protection of point functions, copy-protection of compute-and-compare programs, and identical-challenge secure copy-protection of decryption keys and all puncturable functionalities. Our technical core is a new decisional monogamy-of-entanglement result for coset states, which both allows us to achieve our new results, and also significantly simplifies and unifies unclonable cryptography proofs. We believe this will have further applications and may be of independent interest.

0.25

An Agile Homomorphic Encryption and ML-KEM Scheme for Privacy-Preserving Health Data Processing

cs.CR ·2026-11-09 ·Daniel Resende, Nadia El Mrabet, Ulrich K{ü}hne
similarity 0.62
Abstract

The storage and processing of health data raise serious privacy concerns; therefore, the data must be encrypted. Fully Homomorphic Encryption (FHE) allows computations on encrypted data, which makes it a very promising technology in this context. However, although the efficiency of FHE algorithms has improved in recent years, they remain very complex. The security of several prominent FHE schemes is based on variants of the Learning With Errors (LWE) problem, which is also the basis of Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM), the new post-quantum standard for asymmetric encryption. In this paper, we propose an agile cryptographic scheme -combining ML-KEM and BGV -that allows efficient implementations in an embedded use case. We describe the parameter selection for the proposed scheme and show its feasibility with a proof-of-concept implementation.

0.42

zkSAS: Practical Zero-Knowledge Proofs for Verifiable Spectrum Access Management

cs.CR ·2026-09-23 ·Nishat F. Purbasha, Ifteher Alom, Eric W. Burger, Y. Thomas Hou, Wenjing Lou +1 more
published similarity 0.62
Abstract · Accepted for publication at the 2026 IEEE International Symposium on Spectrum Innovation (DySPAN), Washington, DC, USA, 2026

Dynamic Spectrum Access (DSA) through the Spectrum Access Systems (SAS) elevates spectral efficiency, yet existing centralized models face allocation logic opaqueness and a lack of independent verifiability. While blockchain-based SAS architectures offer transparency and verifiability by default, they introduce critical privacy risks and prohibitive on-chain computational overhead. We introduce zkSAS, a practical zero-knowledge proof (ZKP) system designed to address the verifiability and privacy gaps in SAS deployments, with direct applicability to both the existing CBRS SAS model and blockchain-based SAS models. The system features a suite of ZKP circuits, encompassing proofs of allocation constraint validity and proofs of move list validity to verify that channel assignments and move list-based incumbent protection measures, respectively, adhere to regulatory constraints without exposing sensitive user data. Comprehensive evaluation of our prototype in both centralized and blockchain-based settings indicates that while proof generation scales with spectrum user population, verification remains lightweight and constant-time. We envision that zkSAS offers a scalable and practical path to secure, verifiable dynamic spectrum sharing.

0.32