CS Paper Radar

Redactable blockchains and polynomial equations

Alexander Demin, Alexey Ovchinnikov, Vladimir Shpilrain

cs.CR cs.NI ·submitted 2026-08-19 19:34 UTC · v1
published

Abstract

We develop new tools for constructing redactable authenticated data structures with post-quantum security. In our construction, inverting the proposed one-way function means solving a polynomial equation (or a system of polynomial equations) in more than one variable. This is presently considered quantum-safe, i.e., there is no known quantum algorithm that could solve this problem efficiently if parameters are chosen wisely.

Comment
12 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Obscura-PQ: Post-Quantum Privacy-Preserving Protocol for the Algorand Blockchain Using Lattice-Based Linkable Ring Signatures

cs.CR ·2026-08-23 ·Navid Azimi
similarity 0.66
Abstract

Public blockchains expose the complete transaction graph, and the privacy protocols deployed to obscure it rely almost exclusively on elliptic-curve cryptography, whose discrete-logarithm foundations fall to Shor's algorithm. Because ledgers are immutable, every anonymity set published today under classical assumptions can be retroactively deanonymized by a future quantum adversary. Transitioning to post-quantum alternatives remains challenging, as strict smart-contract resource limits prohibit native on-chain verification of computationally intensive post-quantum proofs. To address these challenges, we present \emph{Obscura-PQ}, a decentralized, non-custodial post-quantum privacy protocol that verifies natively on the Algorand blockchain. Its core is a setup-free lattice linkable ring signature over the cyclotomic ring $\mathcal{R}_q = \mathbb{Z}_q[X]/(X^{512}+1)$. A deposit is a Ring-SIS binding commitment to a short secret; a withdrawal proves knowledge of a ring opening via an AOS/Borromean-style challenge chain over two response-sharing linear relations with rejection-sampled short responses, while publishing a deterministic Ring-LWE serial number for double-spend detection. We reduce double-spend soundness and linkability to Ring-SIS, theft resistance to Ring-SIS for honestly generated deposits, and anonymity to Ring-LWE and an explicit decisional linking assumption in the classical random-oracle model. To overcome strict on-chain opcode and storage limits, Obscura-PQ evaluates verification relations entirely in the NTT domain. We split forward NTTs across opcode-pooled execution phases and stream oversized proofs through refundable box storage, enabling $O(1)$ membership and double-spend checks. We provide a complete Algorand testnet implementation, demonstrating native on-chain verification of a post-quantum privacy protocol under strict smart-contract limits.

0.25

PQ-Vault: Provably Quantum-Safe Asset Custody for Unmodified Ethereum

cs.CR quant-phcs.DCcs.IT ·2026-10-21 ·Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng
theory similarity 0.63
Abstract · 14 pages + 11 pages of appendices

A quantum computer could recover the key of any Ethereum account whose public key appears on chain. We prove that no sidechain or bridge that leaves Ethereum's rules unchanged can protect such accounts: their funds must move into a contract whose release condition relies only on quantum-safe primitives. We design \emph{PQ-Vault}, a custody system for unmodified Ethereum combining this vault, a quantum-safe proof-of-stake sidechain whose checkpoints carry compact certificates, and an optimistic dispute protocol. We give the first security proof of compact certificates against quantum attackers and a matching attack: with classically chosen parameters, the guarantee falls from 128 to about 60 bits, and a simple rule restores it. We show that a common seed-update rule in hash-chain proof of stake lets an attacker steer chosen slots and profit from splitting its stake, and give an election whose steering gain and inclusion delay are provably bounded against quantum attackers. Since compressing certificates with a pairing-based SNARK breaks quantum security, we use fraud proofs that need a single signature check. For 65,536 validators, a certificate is 0.8 MB, 260 times smaller than all signatures, and verifies in about 20 ms; the vault accepts a checkpoint for about 420,000 gas.

0.17

Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation

cs.CR quant-ph ·2026-10-23 ·Frédéric Dupuis, Rémi Ligez, Khaireddine Medhioub, Louis Salvail, Louis-Charles Thibodeau
similarity 0.63
Abstract · Revised the Introduction and added a Technical Overview section. Corrected typos and minor notation issues. No changes to the results

In this paper, we show for the first time that post-quantum one-way permutations are sufficient for perfect zero-knowledge classical arguments for all of NP with security guaranteed against quantum adversaries. We first establish that Naor, Ostrovsky, Venkatesan, and Yung's bit commitment scheme built from any permutation using interactive hashing, called the NOVY scheme, is sum-binding and collapse-binding against quantum polynomial-time committers provided the permutation is post-quantum one-way. We then show that the collapse-binding property of the NOVY scheme allows for Blum's perfect zero-knowledge argument for HAMCYCLE to remain so exactly as it stands against quantum adversaries.

0.33

Thresholding Post-Quantum Signatures

cs.CR ·2026-08-27 ·Francesco De Sclavis, Matteo Nardelli, Marco Pedicini
similarity 0.62
Abstract

Threshold signature schemes distribute the signing process among $T$ parties out of $N$. They enable a variety of applications and their research is also motivated by a recent NIST call. However, applications are dominated by pre-quantum signatures, which are more efficient but not secure in the post-quantum setting. This paper investigates existing post-quantum signatures, based on a variety of paradigms: lattice problems, one-way (hash) functions, cryptographic group actions, isogenies and multivariate systems. We propose a classification (divided by paradigm) of existing tools that are used to build $T$-out-of-$N$ schemes from digital signatures. We also include general approaches based on FHE, MPC or ZKP.

0.22

Compact Shielded CSV: Post-Quantum, Private, Lightweight Client-Side Validation Blockchain

cs.CR ·2026-09-25 ·Dragos I. Ilie, Uri Lee, Iain D. Stewart, Jonathan Zhu, Elliot Jones +1 more
similarity 0.61
Abstract

We propose Compact Shielded CSV, a private client-side validation blockchain for peer-to-peer payments designed for the postquantum era. Upgrading existing blockchains to quantum-resistant cryptography substantially increases on-chain overhead. By keeping all large cryptographic artifacts off-chain, Compact Shielded CSV keeps a minimal on-chain footprint independent of the size of the underlying cryptographic proofs and signatures. For a single input transaction, the onchain footprint is just 3 hashes (3x32 bytes): a nullifier, a degriefer, and a commitment to the transaction. We introduce the degriefer - a novel mechanism that enforces ownership and prevents double-spending using only hash commitments, eliminating the need for on-chain signatures entirely. These properties make Compact Shielded CSV a promising foundation for private, scalable, post-quantum digital payments.

0.27

Semi-Quantum Cryptography with Certified Deletion

cs.CR quant-ph ·2026-09-30 ·Yael Tauman Kalai, Justin Raizes
similarity 0.61
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

A Post-Quantum Interactive Hashing Theorem

cs.CR quant-ph ·2026-11-04 ·Céline Chevalier, Laurent Holin, Quoc-Huy Vu
theoryhot direction similarity 0.61
Abstract

Interactive hashing, introduced by Ostrovsky, Venkatesan, and Yung [OVY93], is a building block in many cryptographic protocols, including perfectly hiding commitments from one-way permutations [NOVY92]. Its multi-output generalization is a key ingredient in constructions of statistical zero-knowledge arguments for NP and statistically hiding commitments from arbitrary one-way functions [NOV06,HR07]. In this note, we give a post-quantum security proof for this multi-output interactive hashing protocol with arbitrary relations.

0.21

Quantum Key Exchange from Public Quantum Money

cs.CR quant-ph ·2026-11-04 ·Eli Goldin, Tomoyuki Morimae
theory similarity 0.60
Abstract · 43 pages, 1 figure

Two-message quantum key exchange (2QKE) cannot be realized in a statistically secure way, and therefore some computational assumptions are required. So far, the known weakest assumption for 2QKE is the existence of one-way functions (OWFs). Can we construct 2QKE from a weaker assumption than OWFs? In this paper, we give the first complete characterization of 2QKE. We show that the following four primitives are (existentially) equivalent: everlasting-secure 2QKE, standard 2QKE, efficiently-verifiable state puzzles (EV-StatePuzzs), and one-time secure digital signatures with quantum signatures and signing keys. Because EV-StatePuzzs are potentially weaker than OWFs [Kretschmer, Qian and Tal 2025], the equivalence implies that 2QKE are potentially weaker than OWFs. Moreover, our result shows the equivalence between standard 2QKE and everlasting-secure 2QKE, which means that everlasting security comes for free. Finally, one-shot signatures, quantum lightning, and public-key quantum money mini-schemes imply EV-StatePuzzs, and therefore, our result also gives a new lowerbound, namely everlasting-secure 2QKE, of these public-key unclonable primitives. We also show that one-shot signatures imply QPKE with quantum public keys. [Kitagawa, Morimae,Nishimaki and Yamakawa, 2024] constructed QPKE with quantum public keys from OWFs, and it was open whether QPKE with quantum public keys can be constructed from an assumption weaker than or incomparable to OWFs. Our result gives a potential answer to this question since one-shot signatures seem to be incomparable with OWFs. Moreover, QPKE constructed from one-shot signatures has an additional functionality, which we call certified freeze, that allows the receiver to publish a publicly verifiable classical certificate that computationally binds the receiver to an upper bound on the total number of distinct valid ciphertexts under its verification key.

0.31