PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Navid Azimi

arXiv:2608.22645v1cs.CR

TL;DR

Public blockchains preserve transaction histories, while deployed privacy systems largely rely on quantum-vulnerable elliptic-curve assumptions and constrained smart contracts cannot readily verify post-quantum proofs. Obscura-PQ introduces a setup-free lattice linkable ring-signature privacy pool for Algorand, using phased NTT-domain verification and box-streamed proofs, and demonstrates native testnet deployment; its reductions remain in the classical random-oracle model.

  • Problem

    Immutable blockchain transcripts using elliptic-curve assumptions can be retroactively deanonymized by quantum adversaries, while strict smart-contract limits hinder native post-quantum verification.

  • Method

    Obscura-PQ combines Ring-SIS commitments, deterministic Ring-LWE serial numbers, and an AOS/Borromean-style lattice linkable ring proof with NTT-domain, phased, box-streamed Algorand verification.

  • Results

    The paper demonstrates a setup-free lattice linkable ring signature verified natively on the Algorand testnet, with double-spend soundness, unforgeability, and anonymity claimed in the classical random-oracle model.

  • Takeaways & Limitations

    Post-quantum privacy spending can be deployed natively on a constrained public blockchain without a global Merkle accumulator or trusted setup.

  • Takeaways & Limitations

    The formal security reductions use the classical random-oracle model, while a formal quantum-accessible ROM analysis remains open.

Abstract

from arXiv · show

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.

1 Introduction

Obscura-PQ addresses retrospective quantum deanonymization and Algorand’s resource constraints with a setup-free, non-custodial lattice privacy pool verified natively on-chain. Its protocol combines Ring-SIS commitments, deterministic Ring-LWE serial numbers, lattice linkable ring proofs, and split, box-streamed verification.

  • Motivation: Immutable classical privacy transcripts can be retroactively deanonymized by quantum adversaries because their elliptic-curve assumptions succumb to Shor’s algorithm.The paper frames post-quantum protection as necessary from publication onward, not merely after quantum computers arrive.
  • Motivation: Strict AVM opcode and argument limits prevent a lattice proof from fitting into one transaction group or application call.A forward NTT exceeds the pooled group budget, while proof size is 32+3072r bytes for ring size r.
  • Protocol Design: Obscura-PQ is a fixed-denomination, decentralized, non-custodial pool whose withdrawals prove ownership of one deposit in a self-selected ring without revealing the member.A deterministic key image makes double-spends detectable while preserving signer ambiguity.
  • Protocol Design: The construction uses a Ring-SIS commitment, deterministic Ring-LWE serial number, and AOS/Borromean-style challenge chain over two response-sharing relations.Rejection-sampled short responses support the lattice proof, while context-bound challenges protect against replay and fee or relayer front-running.
  • On-Chain Execution: Verification runs in the NTT domain, splits forward transforms across opcode-pooled phases, streams proofs through refundable boxes, and stores commitments and nullifiers as key–value boxes.The verifier avoids inverse NTTs, persists phase state across groups, and supports O(1) membership and double-spend checks.
  • Deployment: The paper provides a complete Algorand testnet deployment with a PyTeal contract, local Python prover, and React client interface.The implementation demonstrates native on-chain verification under the protocol’s strict smart-contract limits.

2 Related Work

Prior privacy pools and linkable ring-signature systems provide useful paradigms but rely on classical elliptic-curve assumptions or costly proof systems. Obscura-PQ retains setup-free ring-based design while targeting native post-quantum verification under constrained smart-contract budgets.

  • Smart-Contract Privacy Pools: Tornado Cash uses Groth16 proofs and a Merkle accumulator, while Möbius and Zether use elliptic-curve-based linkable rings or confidential balances.These systems illustrate the trade-offs between trusted setup, pairing-heavy verification, and classical cryptographic assumptions.
  • Smart-Contract Privacy Pools: Obscura-PQ preserves Obscura’s setup-free, accumulator-free ring paradigm and box-based state architecture while making the published transcript post-quantum.Its post-quantum evolution changes the execution problem because lattice verification does not fit ordinary constrained execution.
  • Linkable Ring Signatures: Obscura-PQ’s two response-sharing relations provide a lattice analogue of CLSAG’s parallel equations, but its challenges form a sequential chain unlike DualRing’s single-response ring.The comparison distinguishes the construction’s proof structure from related linkable ring signatures.
  • On-Chain Verification Under Budget Constraints: STARK proof sizes and verifier costs are impractical under strict opcode limits, whereas Bulletproofs remain based on discrete-logarithm assumptions.The paper positions split-transform execution and box-persisted state as a way to decompose structured-lattice verification natively.

3 Preliminaries

The paper grounds Obscura-PQ in structured-lattice assumptions, rejection-sampled lattice proofs, and Algorand’s constrained execution model. These foundations explain both its privacy claims and its need for phased, persistent on-chain verification.

  • Hardness Assumptions: Ring-SIS underpins commitment binding, unforgeability, and serial-number soundness by making short collisions computationally infeasible.Distinct short openings or multiple valid serial numbers would yield a Ring-SIS collision.
  • Hardness Assumptions: Ring-LWE provides hiding for commitments and pseudorandomness for serial numbers, with deterministic e=Hshort(k) modeled as self-correlated noise through a random oracle.The paper distinguishes this modeled instance from a black-box reduction to standard decisional Ring-LWE.
  • Security Model: The security reductions use the classical random-oracle model, while the intended deployment model requires a quantum-accessible ROM whose formal analysis remains open.This is an explicit scope boundary for the paper’s long-term security claims.
  • Fiat–Shamir with Aborts: Rejection sampling makes accepted lattice responses nearly independent of the secret, and verifiers enforce response norm bounds.The technique prevents the naive response distribution from leaking the witness.
  • Blockchain Execution Model: Algorand provides 700 opcode units per application call, pooled within groups and expandable through inner calls, but the group cap remains below one forward NTT’s cost.Verification therefore requires sequential groups with persistent intermediate state.
  • Blockchain Execution Model: Box storage enables O(1) commitment and nullifier existence checks and persists verification state across transaction groups.The transport box’s 32,768-byte value limit ultimately caps ring size, while other consensus limits constrain references and group composition.

4 Cryptographic Construction

Obscura-PQ builds a setup-free lattice linkable ring signature from Ring-SIS commitments, deterministic Ring-LWE serial numbers, and a two-relation AOS/Borromean challenge chain. Verification uses frequency-domain relations, rejection-sampled responses, and Fiat–Shamir closure.

  • Public Parameters and Challenge Space: The scheme comprises CoinKeyGen, SN, Sign, Verify, and Link over a cyclotomic ring with publicly auditable, setup-free parameters.The public ring elements are derived by a nothing-up-my-sleeve hash-to-ring map, so anyone can re-derive the parameters.
  • Coin Generation and Serial Number: A coin is a Ring-SIS binding commitment to short spend secret k, randomness s, and deterministic blinding e, while SN produces the serial number sn = a3k + e.The commitment is published as NTT(C), and the compact double-spend key is the digest of the serial number.
  • Verification Relations: The withdrawal proof uses two response-sharing linear relations that jointly open one commitment and reproduce its serial number at the same hidden ring index.Shared responses bind the serial number to the spent coin through a single short witness (k, e).
  • Signing and Rejection Sampling: The prover simulates decoy responses, closes the Fiat–Shamir chain at the true index, and applies rejection sampling so accepted responses are independent of the secret.Responses exceeding β2 are rejected and regenerated with fresh masks.
  • Verification and Wire Format: The verifier checks raw-response norm bounds, evaluates four forward NTTs per ring member, updates the challenge chain, and accepts only when the final challenge equals c0.Frequency-domain evaluation preserves the relations while avoiding inverse NTTs.

5 Protocol Description

Obscura-PQ implements a fixed-denomination privacy pool in which users deposit commitments and later withdraw by proving ownership of one hidden member of a self-selected ring. The protocol uses local proving, bounded decoy selection, streamed withdrawal proofs, and deterministic nullifiers for atomic settlement and double-spend prevention.

  • Deposit: Deposits use an atomic application-call and payment group, reject duplicate commitments, store NTT(C) in a commitment box, and increment the deposit counter.The fixed denomination is 20.101 ALGO in the deposit sequence.
  • Anonymity-Set Construction: Before withdrawal, the client forms a ring of on-chain commitments containing its coin at a secret index and selects decoys from the 20 most recent valid deposits.Decoys are sampled uniformly from a bounded recent pool rather than always selecting the newest entries.
  • Withdrawal: The local prover derives the serial number and ring signature, while the client binds recipient, relayer, fee, and application ID into the settlement context.The wallet may self-relay or use a third-party relayer because the relayer address and fee are signature-bound.
  • Withdrawal: Oversized proofs are streamed through a transport box, verified across 9r ordered phases, and finalized only after challenge-chain closure and ring-membership checks.The withdrawal sequence deletes transient boxes and settles through three inner transactions.
  • Double-Spend Prevention: A deterministic nullifier digest is recorded atomically with payout, so a second spend of the same coin presents the identical digest and reverts.Substituting another valid serial number would require a second short commitment opening or violation of the serial-number relation.

6 On-Chain Execution

The on-chain verifier overcomes Algorand’s opcode and argument limits by splitting NTT work across pooled execution phases and streaming proofs through refundable box storage. A persistent phase machine preserves intermediate state until atomic settlement.

  • Execution Constraints: 2.05 × 10^5 opcode units for one forward NTT with norm checking exceeds the approximately 1.9×10^5 units pooled by one transaction group.This prevents lattice verification from fitting within a single group.
  • Proof Transport: 1056+3104r bytes of proof material exceeds the 2,048-byte application-argument limit for every r ≥ 1, so proofs are streamed into a transport box.The transport box is initialized with refundable MBR funding and populated in chunks of at most 1,960 bytes.
  • Settlement: 48-byte-equivalent transient state is not retained after settlement: all transient MBRs are refunded, leaving only the empty nullifier box as permanent withdrawal state.The settlement call deletes flow boxes before issuing the payout and related payments.
  • NTT Execution: Each forward NTT is divided into heavy and light halves, provisioned with 250 and 175 inner OpUp calls respectively, while intermediate buffers persist in box storage.The split occurs at butterfly length 32 and response transforms overwrite transport-box slots in place.
  • Per-Member Verification: Each ring member requires nine prep_ntt phases covering three response transforms, challenge expansion, and a final pointwise two-relation combine.The phase machine also re-asserts ring-identifier digests and folds the challenge update into persistent state.
  • Opcode Pooling: 1828 inner OpUp calls per member provision the pooled budget, with auxiliary calls also carrying references around Algorand’s reference and box-I/O limits.The stated cost is 4 × (250 + 175) + 128 = 1828 inner OpUp calls.
  • Settlement Semantics: The design guarantees fund safety but not censorship-resistant liveness for a targeted withdrawal when an incorrect context prevents challenge-chain closure.A failed mid-flow can be cleared and restarted by its funder because transient boxes are refundable.

7 Implementation

The implementation separates client, local-prover, and blockchain responsibilities into three trust domains. PyTeal/TEAL executes the verifier on-chain, while a local Python service performs heavy lattice arithmetic and the client coordinates wallets, rings, fees, proof transport, and cleanup.

  • Architecture: Obscura-PQ is deployed as a full-stack application with three trust domains and publicly available implementation source code.The domains are represented by the client environment, local prover enclave, and Algorand blockchain.
  • Smart-Contract Layer: The smart-contract layer uses PyTeal 0.27.0 compiled to TEAL v10, implementing NTTs, norm checks, challenge expansion, and pointwise relations directly in TEAL.Fixed-base transforms are provisioned once in a dedicated parameter box to respect program and argument limits.
  • Client and Prover: The local Python prover performs CoinKeyGen, serial-number generation, and signing, while the client handles wallet integration, ring formation, transaction planning, proof streaming, and self-healing cleanup.The prover runs on the user’s machine because possession of the opening is the spend authority.
  • Blockchain Layer: The blockchain layer enforces state transitions and uses the indexer, Box Storage, and a dummy application for queries, membership checks, nullifier checks, opcode pooling, and reference carrying.The architecture keeps heavy lattice arithmetic in the prover while retaining native verification and state enforcement on-chain.

8 Security and Privacy Analysis

The analysis establishes soundness, unlinkability, replay resistance, and auditability under stated lattice assumptions, while identifying bounded anonymity and several implementation and modeling limitations.

  • Security guarantees: Valid withdrawals for rings of honest deposits without a known opening reduce to Ring-SIS, with norm checks, ring-existence checks, and transport-box freezing essential to soundness.The extractor recovers a relaxed opening because short challenge differences are not invertible in the fully splitting ring.
  • Security guarantees: Signer identification and deposit-withdrawal linking remain bounded by 1/r under Ring-LWE and an explicit decisional linking assumption in the random-oracle model.The anonymity set is the selected ring, of size at most rmax, rather than the entire pool.
  • Security guarantees: Deterministic serial numbers derived from unique committed openings make double-spend detection sound even when a signer deviates from the signing algorithm.The construction ties each verifying withdrawal to the unique short opening of a ring member.
  • Security guarantees: Hashing the recipient, relayer, fee, and application identifier into every challenge prevents replay, payout redirection, fee inflation, and cross-deployment replay.Settlement uses chain-bound state values, while recorded nullifiers block replayed withdrawals.
  • Security guarantees: Users can voluntarily disclose a coin opening to auditors, who can verify its commitment and serial number without affecting other participants’ anonymity.The auditor checks e = Hshort(k), the deposit commitment, and the withdrawal serial number.
  • Limitations and open gaps: The guarantees have important boundaries: the analysis is classical-ROM only, the implemented sampler differs from the idealized one, liveness is vulnerable to phase squatting, parameters lack calibrated bit-security claims, and the implementation lacks formal verification and third-party audit.The authors state that a QROM analysis has not been carried out and that a hardened sampler is required for the stated anonymity bounds.

9 Cost Analysis

The cost analysis shows constant-size deposit overhead but withdrawal costs, proof transport, storage, and latency that grow linearly with ring size. On-chain execution and network confirmation dominate withdrawal performance, while off-chain work remains near-constant or sub-second.

  • Communication: Proof transport grows linearly as 1056 + 3104r bytes, exceeding the 2 048-byte argument limit and requiring streamed box storage.The raw signature is 32 + 3072r bytes and exceeds 30 KB at the maximum ring size.
  • Execution: Verification requires 9r phase groups and 1828r inner OpUp calls, producing O(r) execution and approximately 1.828r ALGO in inner fees.Withdrawal also includes fixed transport and settlement overhead, whereas deposits cost 0.001 ALGO.
  • Storage: Permanent storage grows by one 1 024-byte commitment box per deposit and one nullifier box per withdrawal, while verification-flow boxes are refunded at settlement.At r = 10, the large transport box requires approximately 8.77 ALGO of MBR.
  • Scalability Trade-off: The practical anonymity-set cap is rmax = 10 because the 32 128-byte transport box reaches Algorand’s 32 768-byte per-box ceiling.Increasing the cap would require splitting transport across multiple boxes, which is currently unimplemented.
  • Latency Breakdown: Deposit latency remains independent of ring size, whereas withdrawal latency grows because transaction submission and confirmation sequentially process 9r+O(1) groups.Off-chain withdrawal stages remain sub-second or near-second; measured wall-clock latency is deployment-environment dependent.

10 Conclusion

Obscura-PQ demonstrates native Algorand testnet deployment of a setup-free lattice linkable ring signature using NTT-domain verification and streamed proof transport. The implementation achieves the stated security properties in the classical random-oracle model, but its costs and current ring-size limit constrain scalability, while quantum-model analysis remains future work.

  • Conclusion: Obscura-PQ was deployed natively on the Algorand testnet using NTT-domain relations, opcode-pooled NTT phases, and box-streamed proof transport.The construction binds a Ring-SIS commitment to a deterministic Ring-LWE serial number through an AOS/Borromean-style challenge chain.
  • Conclusion: The protocol achieves double-spend soundness, unforgeability, and anonymity in the classical random-oracle model without a global Merkle accumulator.These properties follow from the stated Ring-SIS and Ring-LWE-based construction.
  • Performance: Proof generation remains sub-second across measured ring sizes, while on-chain verification scales with 9r phase groups and 1828r inner transactions per ring member.The client-side prover is therefore much less burdensome than on-chain verification in the reported measurements.
  • Scalability: The proof size is 3072r + 32 bytes, and the protocol shape-checks ring sizes to r ∈ [1, 10].The upper bound is dictated by the transport box and the per-box size ceiling.
  • Future Work: Future work requires QROM security analysis, concrete bit-security calibration, and a hardened constant-time discrete Gaussian sampler with the complete acceptance ratio.The authors also identify sublinear post-quantum verification as a future protocol direction.

Code Availability

The complete Obscura-PQ implementation is publicly available to support reproducibility and auditing. It includes the smart contract, prover, client, tests, and ledger-analysis utilities.

  • Code Availability: The repository provides the PyTeal smart contract, local lattice prover, React client, and test suites.It also includes utilities for analyzing ledger data.
  • Code Availability: All empirical measurements in Section 9 were obtained from Algorand testnet executions of this implementation.

A Formal Definitions and Security Arguments

The appendix formalizes Obscura-PQ’s lattice linkable ring signature and connects its security properties to the assumptions introduced earlier. It presents reductions based on established Fiat–Shamir-with-aborts and commitment-based linkable-ring-signature analyses while identifying deviations from the analyzed abstraction.

  • Formal Definitions and Security Arguments: The appendix gives reductions showing where each security assumption enters the analysis.It follows established templates for Fiat–Shamir-with-aborts sigma protocols and commitment-based linkable ring signatures.
  • Formal Definitions and Security Arguments: The analysis explicitly flags points where the implemented scheme deviates from the analyzed abstraction.

A.1 Notation

The notation section defines “short” elements by bounded Euclidean norm and identifies the signature, commitment, nullifier boxes, and NTT-domain operations.

  • “Short” denotes elements bounded by Euclidean norm, and hash calls are domain-separated SHA-256 random-oracle instances.
  • The notation includes the signature σ, commitment and nullifier box sets, and NTT representations ˆx with frequency-domain pointwise products.

A.2 Hardness Assumptions and the Commitment

The paper models commitment hiding, serial-number privacy, and security properties through Ring-SIS, Ring-LWE, and random-oracle assumptions. It establishes correctness, theft resistance, anonymity, linkability, replay resistance, and double-spend resistance, while limiting extraction and anonymity claims under its fully splitting ring and deterministic-noise model.

  • The commitment C is computationally indistinguishable from uniform under a rank-2 Module-LWE view, while the serial number sn hides k under the random-oracle treatment of deterministic error.The deterministic error e = Hshort(k) makes the serial-number argument self-correlated rather than a black-box reduction to standard decisional Ring-LWE.
  • Honest signatures are accepted except with negligible probability, and honest signing terminates after an expected O(1) rejection restarts.Rejection sampling ensures true-index responses satisfy the norm bound; implemented decoy responses violate it only with negligible probability.
  • Theorem 2 proves theft resistance in the random-oracle model under the stated Ring-SIS assumptions, with ring-existence and digest matching restricting commitments to genuine deposits.
  • Signer identification among r − t honest ring members exceeds 1/(r − t) only by a negligible amount, yielding deposit–withdrawal unlinkability under the stated assumptions.The unlinkability argument replaces the serial number with an independent value in a random-oracle game, making the adversary’s final distinguishing advantage negligible.
  • Every verifying spend of one coin produces the same serial number, preventing distinct-nullifier withdrawals and supporting linkability and non-frameability.The serial number is fixed by the unique short opening, while producing an honest user’s serial number for an unspent coin is negligible-probability.
  • The protocol records each nullifier atomically with payout, giving O(1) double-spend checks, while replay and recipient, relayer, fee, and appID alterations are prevented except negligibly.
  • Because the fully splitting Falcon-512 ring lacks guaranteed invertible short challenge differences, extraction yields only a relaxed opening and theft resistance is stated for honestly generated rings.The paper does not claim exact-opening or knowledge-soundness security against rings containing adversarially generated decoys.
  • The anonymity and unlinkability proofs rely on the random-oracle model because e = Hshort(k) is deterministic and therefore not an independent Ring-LWE error.
Loading 2608.22645v1…