CS Paper Radar

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

Navid Azimi

cs.CR ·submitted 2026-08-23 23:03 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.71
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

PQLN: Post-Quantum Security for the Bitcoin Lightning Network's Off-Chain Surfaces

cs.CR cs.NI ·2026-09-12 ·Ahmet Kurt, Abdul-Salem Beibitkhan, Yacoub Hanna, Abdullah Aydeger
similarity 0.68
Abstract

A cryptographically relevant quantum computer will break the elliptic-curve cryptography behind Bitcoin and its Lightning Network, the most widely used payment channel network. Even a post-quantum consensus upgrade of Bitcoin would not cover Lightning's off-chain surfaces, so its gossip, peer transport, invoices, payment onions, and offers need separate protection. An adversary can already record Lightning's encrypted traffic today and decrypt it once such a computer exists. Lightning can therefore move to post-quantum cryptography now, without waiting for Bitcoin, and stop such harvest-now-decrypt-later attacks along with node impersonation, invoice forgery, and payment deanonymization. In this paper, we propose PQLN, a hybrid post-quantum extension of Lightning that protects all of these surfaces with the lattice-based standards ML-DSA and ML-KEM. PQLN distributes post-quantum node identities through Lightning's gossip, hybridizes the transport handshake, adds post-quantum signatures to invoices, commits post-quantum keys in offers, and makes payment onions hybrid. Since post-quantum material is much larger than its elliptic-curve counterpart, we introduce techniques that fit it into Lightning's existing message formats and size limits. We analyze the security of PQLN against a quantum adversary and implement it in rust-lightning, a major Lightning implementation. Our evaluation with real Lightning nodes shows that PQLN nodes interoperate with unmodified nodes. The added cryptographic operations take at most 0.33 milliseconds, and the main cost is communication, since gossip data grows about tenfold with ML-DSA and about fourfold with the smaller Falcon. To our knowledge, PQLN is the first post-quantum design, implementation, and evaluation for Lightning.

0.08

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.68
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

Cryptocurrencies in the Quantum Age: Migration Paths to PQC

cs.CR ·2026-08-24 ·Aleksei Kodukhov
similarity 0.66
Abstract · 9 pages

Quantum computers pose a fundamental threat to blockchain systems that rely on elliptic-curve cryptography. This work reviews the quantum vulnerabilities and associated economic risks of major blockchain platforms, with a focus on Bitcoin, Ethereum, and Solana. We distinguish between at-rest, on-spend, and on-setup attacks and identify the blockchain components most exposed to quantum adversaries. We further review practical migration strategies toward post-quantum security, including NIST-standardized digital signatures and emerging solutions for Solana, Algorand, and Ethereum.

0.18

Redactable blockchains and polynomial equations

cs.CR cs.NI ·2026-08-19 ·Alexander Demin, Alexey Ovchinnikov, Vladimir Shpilrain
published similarity 0.66
Abstract · 12 pages

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.

0.49

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

cs.CR ·2026-11-04 ·Jude Ramanan, Georgiana Haldeman, Noah Apthorpe
similarity 0.65
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

Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation

cs.CR quant-ph ·2026-09-30 ·Alexandru Gheorghiu, Aparna Gupte, Vojtěch Havlíček, Yunchao Liu
similarity 0.65
Abstract

We construct protocols for classically verifiable quantum advantage and classical verification of $\mathsf{BQP}$ computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of $\mathsf{BQP}\neq\mathsf{BPP}$, we construct a two-message quantum-advantage protocol that is efficiently and publicly verifiable. Our result can be viewed as a rigorous cryptographic foundation for the heuristic quantum advantage proposals based on \emph{peaked random circuit sampling} of Aaronson and Zhang (arXiv:2404.14493). We also construct two simple protocols for classically verifying arbitrary $\mathsf{BQP}$ computations. The first protocol is privately verifiable and assumes only the existence of qiO. This gives a rare example of a nontrivial cryptographic application of (quantum) iO that does not make additional computational hardness assumptions. The second protocol additionally assumes post-quantum one-way functions and is \emph{publicly verifiable}. To our knowledge, this is the first publicly verifiable protocol for classical verification of $\mathsf{BQP}$ computations under computational assumptions in the standard model. As qiO is the basis for our results, we propose an approach to constructing qiO by adapting the local-mixing framework of Canetti--Chamon--Mucciolo--Ruckenstein.

0.26

Semi-Quantum Cryptography with Certified Deletion

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