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

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

arXiv:2608.22645v1 [cs.CR] 23 Aug 2026

Emory University, Atlanta, GA 30322, USA navid.azimi@emory.edu 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 postquantum alternatives remains challenging, as the strict resource limits of smart contracts prohibit the native on-chain verification of computationally intensive post-quantum proofs. To address these challenges, we present 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 Rq = Zq [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 the Ring-SIS assumption, theft resistance to Ring-SIS for rings of honestly generated deposits, and anonymity to Ring-LWE and an explicit decisional linking assumption, all in the classical random-oracle model. To overcome strict on-chain opcode and storage limits, Obscura-PQ evaluates all verification relations entirely in the number-theoretic-transform (NTT) domain. We split the 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. Keywords: Post-Quantum Cryptography · Lattice-Based Cryptography · Linkable Ring Signatures · Blockchain Privacy · Algorand · Onchain Verification · Smart Contracts

1

Introduction

The transparency of public blockchains [56] underpins their security and auditability, yet it inherently undermines user privacy: adversaries can trace the

2

N. Azimi

flow of funds, cluster addresses, and deanonymize users through transactiongraph analysis [11,51,64]. Privacy-preserving protocols and decentralized mixers address this issue [17,21,54]: on Ethereum [67], Tornado Cash [61] severs the onchain link between depositors and withdrawers using zk-SNARKs over a Merkle accumulator [52, 53]; Möbius [50] achieves trustless tumbling from linkable ring signatures; Zether [22] provides confidential account balances; Obscura [12] deploys a non-custodial LSAG-based privacy protocol natively on Algorand; and Monero’s CryptoNote lineage [36, 58, 65] deploys linkable ring signatures at the base layer. All of these systems share a single point of failure: their unforgeability or soundness, and the long-term secrecy of their published commitments, ultimately rest on discrete-logarithm or pairing assumptions in elliptic-curve groups, all of which Shor’s algorithm breaks [66]. The threat is not merely the hypothetical future breakage of future transactions. Because a blockchain is an immutable public record, every commitment, ring, and nullifier published under classical assumptions is archived permanently; a quantum adversary arriving decades from now can retroactively recover the secret behind each deposit, link deposits to withdrawals, and dissolve every anonymity set ever formed. Unlike signatures, which can be rotated, privacy protocols face harvest-now, deanonymize-later as the default attack, and this can be prevented by making the published transcript post-quantum secure from the outset. A second, orthogonal obstacle is the execution environment. High-throughput blockchains such as Algorand [35] preserve fast finality and predictable fees by imposing strict per-transaction opcode budgets, flat state models, and small argument-size limits on their virtual machines [6,9]. Lattice-based zero-knowledge machinery is far heavier than its elliptic-curve counterpart: a single polynomial multiplication in a post-quantum ring already exceeds the entire pooled execution budget of a transaction group, and a single lattice commitment is more than an order of magnitude larger than an elliptic-curve point. No deployed smart-contract privacy protocol that we are aware of verifies a post-quantum anonymous spend natively on-chain. Proposed Approach. We present Obscura-PQ, the post-quantum version of the Obscura protocol [12]: a decentralized, non-custodial privacy protocol for Algorand whose entire cryptographic core is post-quantum. Obscura-PQ is a fixeddenomination privacy pool: a user deposits by publishing a coin, and later withdraws to a fresh address by proving, without revealing which one, that they own one of the coins in a self-selected ring of on-chain deposits, while publishing a key image that makes double-spends detectable. The construction works over the power-of-two cyclotomic ring Rq = Zq [X]/(X n + 1) with n = 512 and q = 12289 (the ring underlying Falcon-512 [33]) and follows the commitment-and-serial-number paradigm of Lattice RingCT and MatRiCT [3, 30]. A coin is a Ring-SIS binding commitment C = a1 k + a2 s + a4 e (a rank-one module commitment in the style of [13]) to a unique short spend secret k, short randomness s, and a short serial-number blinding term e; the key image is the deterministic Ring-LWE serial number sn = a3 k + e, revealed in

Obscura-PQ: Post-Quantum Privacy for Algorand

3

full at withdrawal; and the one-out-of-r spend proof is an AOS/Borromean-style challenge chain [1, 48] over two response-sharing linear relations, one opening the commitment, one producing the serial number, closed at the true index with rejection-sampled short responses [43, 44]. The two-relation response sharing that binds the serial number to the coin serves as the lattice analogue to the parallel-equation structure of CLSAG [36]. While the compressed responsesharing closure of DualRing [68] shares a similar intuition, it remains structurally distinct: DualRing employs a ring of challenges with a single response, whereas our construction relies on a sequential challenge chain. The public parameters a1 , a2 , a3 , a4 are nothing-up-my-sleeve hash outputs, so the protocol has no trusted setup. Soundness and linkability reduce to Ring-SIS [3, 45], and anonymity to Ring-LWE [46], in the random-oracle model. Key Challenges and Technical Solutions. Two problems separate this design from a routine instantiation. First, a sound post-quantum key image. A key image supports double-spend detection only if it satisfies three properties at once: it must be deterministic, so that every spend of a given coin yields the same image; it must be derived from a unique secret, so that a malicious signer cannot equip one coin with several valid images; and it must be member-hiding, so that publishing it reveals nothing about which ring member it corresponds to. Obscura-PQ derives all three properties from commitment binding. The uniqueness of the spend secret k and the blinding term e is guaranteed by the Ring-SIS assumption, as computing a second short opening for the commitment C would yield a Ring-SIS collision. This unique opening deterministically fixes the serial number sn = a3 k + e. Revealing sn in the clear compromises neither the secret nor the anonymity of the transaction: because sn forms a valid Ring-LWE sample (where k acts as the secret and e = Hshort (k) as the error), it is pseudorandom in the random-oracle model and computationally unlinkable to C. Furthermore, while e is derived deterministically to allow honest signers to remain stateless, the soundness of the protocol relies strictly on e being algebraically bound to C via the term a4 e, rather than on the hash derivation. Consequently, a malicious signer who commits using an arbitrary short e is inextricably pinned to that same e for all future spending attempts. Finally, because the signing protocol shares response coordinates across both verification relations, every verifying signature guarantees that one short opening simultaneously opens some ring commitment and yields the published serial number. Second, native on-chain lattice verification. Verifying the signature requires, for each ring member, four forward number-theoretic transforms (NTTs) of degree-512 polynomials, a pointwise relation evaluation, norm checks on the responses, and a hash-chain update. This workload collides with the AVM’s resource model on two fronts: a single forward NTT with its norm check costs more than the entire pooled budget of an Algorand transaction group, and the proof, at 32+3072r bytes for ring size r, exceeds the 2 048-byte application-argument limit for any r. Obscura-PQ overcomes both obstacles with four mutually supporting techniques. (i) All relations are evaluated in the NTT domain: commitments are

4

N. Azimi

stored, and serial numbers transported, as forward transforms, so the verifier never computes an inverse NTT. (ii) Each forward NTT is split at a fixed butterfly length into two execution phases, nine phases per ring member in total, each provisioned with pooled opcode budget through inner “no-op” application calls. (iii) Proofs are streamed into an application-owned transport box before verification begins; all transient storage deposits are fronted by the withdrawer and refunded atomically at settlement. (iv) Commitments and nullifiers reside in a flat key–value box-storage model [7], which supports O(1) membership and double-spend checks without a global Merkle accumulator. Contributions. This paper makes the following contributions: – Protocol design. We propose Obscura-PQ, a post-quantum privacy protocol whose anonymous spend is a lattice linkable ring signature built from a Ring-SIS binding commitment, a deterministic linear serial number, and an AOS/Borromean-style challenge chain over two response-sharing relations. Every Fiat–Shamir challenge is computed over the full settlement context (recipient, relayer, fee, and application identifier), defeating replay and fee/relayer front-running, and the public parameters are nothing-up-mysleeve. – On-chain execution model for lattice verification. We show how to run the verifier natively on a strictly budgeted virtual machine: a frequencydomain wire format that eliminates inverse transforms, table-driven negacyclic NTTs split across opcode-pooled phases, box-streamed proof transport with refundable storage accounting, and a per-member phase machine whose state survives across transaction groups. The resulting verifier is correct for every ring size up to the protocol cap. – Security analysis. We give a precise threat model and reductions: theft resistance (unforgeability) and double-spend soundness to Ring-SIS, signer ambiguity and unlinkability to Ring-LWE and an explicit decisional linking assumption for the serial number closed with the rejection-sampling zeroknowledge argument, and replay resistance to context binding, all in the random-oracle model. Because the fully splitting Falcon-512 ring does not admit invertible short challenge differences, our extractor recovers a relaxed opening and our unforgeability statement is proved for rings of honestly generated deposits (see Appendix A, Remark 1). – End-to-end implementation. We provide a complete, open-source fullstack deployment on the Algorand testnet, featuring a PyTeal smart contract compiled to AVM bytecode, a local Python-based prover, and a React client interface. Figure 1 illustrates the end-to-end architecture. The remainder of the paper is organized as follows: Section 2 surveys related work, and Section 3 establishes the necessary cryptographic and system preliminaries. We formalize the core construction in Section 4 and detail the protocol flows in Section 5. The system design is then presented in two parts: Section 6 describes the on-chain execution

Obscura-PQ: Post-Quantum Privacy for Algorand

5

Public Commitments {Ci }

On-Chain: Algorand Virtual Machine (AVM)

Off-Chain: Client & Prover Client App (Deposit) CoinKeyGen: C = a1 k + a2 s + a4 e

Deposit Group (20.101 ALGO, NTT(C))

Submit

deposit Handler (Check Denomination, Write NTT(C))

Write BC (C)

Box Storage Commitments BC (NTT(C), 1024 B)

Save Ring Formation (Fetch & Shuffle, Recency-Biased Decoys)

Local Storage Coin Secret (k, s) Blinding e

{Ci }

Load Client App (Withdraw) Context µ: recipient m

Dummy App (OpUp Target / Aux Ref. Carriers)

((k, s, e), µ)

Local Prover sn = a3 k + e, Sign w/ Rejection: σ = (c0 , {(zk,i , zs,i , ze,i )})

Check {Ci }

1828r OpUps Withdrawal Groups (sn∗ , NTT(sn), σ, R, µ)

Stream σ via init/put proof

Lattice Verifier (9r prep ntt phases: split NTT + chain fold) marker = 9r; pay m

Box Storage Nullifiers BN (sn∗ ) Write BN (sn∗ )

withdraw: Closure c = c0 , Nullifier Write & 3 Inner Payments

Fig. 1. Obscura-PQ protocol end-to-end architecture. Solid arrows denote protocol actions and transaction submissions; dashed arrows denote reads of on-chain public state. The Client App initiates both phases. Deposit: the client runs CoinKeyGen, sampling a short coin secret (k, s) with deterministic blinding e = Hshort (k), computes the Ring-SIS commitment C = a1 k + a2 s + a4 e, stores (k, s, e) locally, and submits a deposit group (20.101 ALGO, NTT(C)). The on-chain deposit handler checks the fixed denomination and writes NTT(C) into commitment Box Storage BC . Withdrawal: the client loads (k, s, e), specifies context µ (including recipient m), and fetches public commitments {Ci } from BC to form a recency-biased, shuffled ring R. The local prover then computes the serial number sn = a3 k + e and, with rejection sampling, a lattice AOS/Borromean-style linkable ring signature σ = (c0 , {(zk,i , zs,i , ze,i )}); the digest sn∗ is the nullifier. Because σ exceeds application-argument limits, the client streams it onchain via init/put_proof. The lattice verifier reads {Ci } from BC , expands its opcode budget via 1828r inner opup calls to a dummy application, and verifies σ natively through 9r sequential prep_ntt phases (split NTT and Fiat–Shamir chain fold). After asserting chain closure c = c0 (marker = 9r), the withdraw handler records sn∗ in nullifier Box Storage BN if unspent and settles with three inner payments to m.

model, while Section 7 covers the implementation and its validation. Finally, Section 8 analyzes security and privacy, Section 9 develops the cost model, and Section 10 concludes. Formal definitions and security arguments are deferred to Appendix A.

2

Related Work

Smart-Contract Privacy Pools. Tornado Cash [61] pioneered SNARK-based privacy pools on Ethereum, achieving pool-wide anonymity via Groth16 proofs [37] over a Merkle accumulator at the cost of a trusted setup and pairing-heavy verification; Zerocoin and Zerocash [17, 54] established the commitment/nullifier paradigm at the base layer. Möbius [50] replaces SNARKs with linkable ring signatures for trustless tumbling, and Zether [22] provides confidential balances; both are elliptic-curve-based. Obscura [12] brought the ring-signature privacy pool paradigm to Algorand, introducing the flat box-storage state model with

6

N. Azimi

O(1) membership checks and the inner-transaction opcode-pooling on which the present work builds; its LSAG core, like all of the above, rests on discretelogarithm assumptions. Obscura-PQ is its post-quantum evolution: it keeps the setup-free, accumulator-free ring paradigm and the box-based state architecture, but makes the entire published transcript post-quantum, which, as Sections 6 and 9 show, changes the execution problem qualitatively, since lattice verification no longer fits within any single transaction group. Linkable Ring Signatures. The key-image mechanism originates with LSAG [40] and CryptoNote [65], refined by MLSAG [58] and CLSAG [36] in Monero. Obscura-PQ’s two response-sharing relations are the lattice analogue of CLSAG’s parallel equations. Among post-quantum constructions, Raptor [42] builds linkable ring signatures from NTRU trapdoors; Lattice RingCT [3], the one-out-of-many framework of Esgin et al. [29], and MatRiCT [30] develop the commitment-and-serial-number approach that Obscura-PQ instantiates; DualRing [68] gives a compressible challenge-ring, single-response closure with a lattice instantiation; and Calamari and Falafl [19] achieve logarithmic-size (linkable) ring signatures from isogenies and lattices respectively, with verifiers that are, however, far beyond current on-chain budgets. To our knowledge, none of these schemes has previously been deployed natively inside a deployed smart contract. On-Chain Verification Under Budget Constraints. While empirical deanonymization studies of deployed privacy coins and protocols [18, 39, 55] motivate the client-side decoy discipline detailed in Section 5, the primary bottleneck for smart-contract privacy remains on-chain verification. Existing zero-knowledge proof systems struggle in this environment: post-quantum succinct systems like STARKs [16] feature transparent setups and sublinear verification, yet their proof sizes and verifier costs are completely impractical under strict per-group opcode limits. Conversely, highly efficient inner-product arguments like Bulletproofs [23] rely on classical discrete-logarithm assumptions. Obscura-PQ bridges this gap. By leveraging a split-transform phase machine and box-persisted state, it provides, to our knowledge, the first demonstration that complex structuredlattice verification can be systematically decomposed to run natively within highly constrained smart-contract execution environments.

3

Preliminaries

This section formalizes the algebraic setting, the hardness assumptions, the signature paradigm, and the blockchain execution model that underpin ObscuraPQ. 3.1

Cryptographic Foundations

The Ring Rq and the Negacyclic NTT. All arithmetic takes place in the cyclotomic quotient ring Rq = Zq [X]/(X n + 1),

n = 512,

q = 12289,

Obscura-PQ: Post-Quantum Privacy for Algorand

7

the ring underlying the Falcon signature scheme [33], which NIST selected for post-quantum standardization. Since 2n | q − 1, the modulus splits completely and Rq supports a full negacyclic number-theoretic transform (NTT): a bijective evaluation map NTT : Rq → Znq under which ring multiplication becomes pointwise multiplication, computable with n2 log2 n = 2304 butterfly operations [41]. We write x̂ = NTT(x) and ⊙ for pointwise multiplication modulo q. For f ∈ Rq we write ∥f ∥2 for the squared Euclidean norm of its integer coefficient vector; short elements are those with small norm. Hardness Assumptions. Obscura-PQ relies on two standard structured-lattice assumptions and the random-oracle heuristic: – B1 (Ring-SIS) [45, 59]: Given uniformly random a1 , . . . , am ∈ Rq , it is computationally infeasible to find short polynomials f1 , . . . , fm , not all zero, P such that i ai fi = 0. In Obscura-PQ, the Ring-SIS assumption guarantees three critical properties: • Commitment Binding: The coin commitment C = a1 k + a2 s + a4 e is a rank-one module instance over (a1 , a2 , a4 ). Opening C to two distinct short triples yields a direct Ring-SIS collision. • Unforgeability: An adversary cannot forge a valid spend proof for an uncorrupted coin without finding a short solution to the underlying linear relations. • Serial-Number Soundness: Because the opening (k, e) is uniquely pinned by commitment binding, the deterministic serial number sn = a3 k + e is strictly fixed per coin. A malicious signer cannot equip a single coin with multiple valid serial numbers without computing a Ring-SIS collision. – B2 (Ring-LWE) [46]: For a public uniform a ∈ Rq and short x, y, the sample (a, ax + y) is computationally indistinguishable from uniform. In Obscura-PQ, this assumption provides the hiding properties necessary for anonymity and unlinkability, applying in two distinct contexts: • Commitment Hiding: The coin commitment C = a1 k + a2 s + a4 e acts as a Ring-LWE sample), making it pseudorandom and computationally hiding its opening. • Serial-Number Pseudorandomness: The serial number sn = a3 k + e takes the exact form of a Ring-LWE sample with secret k and short error e. Because e = Hshort (k) is derived deterministically, sn is formally a selfcorrelated-noise Ring-LWE instance. By modeling Hshort as a random oracle with short outputs, e acts as an independent short error to any adversary that has not queried the oracle at k. Consequently, recovering k from sn reduces to search Ring-LWE, and linking a deposit to a withdrawal reduces to decisional Ring-LWE in the random-oracle model (see Appendix A, Assumption 2 and Remark 1). – B3 (Random-Oracle Model) [15]: The hash function instantiating the Fiat–Shamir transform [31] is modeled as a random oracle. While the security reductions presented in this paper operate within the classical random-oracle model (ROM), the intended long-term deployment model requires security

8

N. Azimi

in the quantum-accessible ROM (QROM) [20,27]. A formal QROM analysis of the composed scheme remains an important direction for future work (see Section 8). Both lattice assumptions are quantum-hard, no quantum algorithm better than generic lattice reduction is known, and they underlie NIST-selected post-quantum signatures, including the standardized ML-DSA (CRYSTALS-Dilithium) and Falcon [28, 33]. In contrast to SNARK-based pools, no trusted setup is required anywhere in the protocol. Fiat–Shamir with Aborts. In lattice-based sigma protocols, the prover’s response has the form z = y + χ · w, where y is a short random mask, χ a sparse challenge, and w the secret. Published naively, the distribution of z leaks w. Lyubashevsky’s rejection sampling technique [43, 44] restarts the signing attempt unless z falls within an acceptance region, making the accepted distribution (nearly) independent of the secret; verifiers additionally enforce a norm bound ∥z∥2 ≤ β 2 , which is essential for soundness, since without it the verification relations are satisfiable trivially. Linkable Ring Signatures. A ring signature [1, 25, 63] lets a signer sign on behalf of an ad-hoc set of public keys without revealing which one it controls; unlike group signatures [24], no manager or coordination is needed. Linkable ring signatures [40] add a key image (linking tag): a deterministic public function of the signing secret that is identical across all signatures produced with that secret, enabling double-spend detection while preserving signer ambiguity [36,58,65]. Post-quantum linkable ring signatures follow two main paradigms: trapdoor- or preimage-based tags [42], and the commitment-and-serial-number approach of Lattice RingCT and MatRiCT [3, 30], in which the tag’s uniqueness is inherited from the binding of a lattice commitment. Obscura-PQ adopts the latter paradigm, combined with the sequential challenge-chain ring closure of AOS [1] and Borromean ring signatures [48], and a two-equation responsesharing structure that is the lattice analogue of the parallel equations that bind the key image in CLSAG [36]. We note that DualRing [68] realizes a structurally different (challenge-ring, single-response) closure that admits logarithmic compression. While we borrow its response-sharing intuition, we explicitly reject its challenge-ring construction in favor of a linear-size AOS-style chain. Although the AOS-style chain yields larger proof sizes, its sequential structure is essential for our design: it allows the heavy lattice arithmetic to be paused, persisted to storage, and resumed, which maps directly onto the phase-decomposed onchain verifier required by Algorand’s strict execution limits (Section 6). Sublinear post-quantum ring signatures also exist [19], at the cost of substantially heavier verifiers; we discuss the trade-off in Section 2. 3.2

Blockchain Execution Model

Obscura-PQ targets the Algorand Virtual Machine (AVM) [6], whose resource model shapes the entire on-chain design:

Obscura-PQ: Post-Quantum Privacy for Algorand

9

Opcode Budget and Inner-Transaction Pooling. Every application call executes under a deterministic per-transaction budget of 700 opcode units, pooled across the transactions of an atomic group [9, 10]. A contract may issue inner transactions; each inner application call contributes a further 700 units to the shared pool. By bursting inner calls to a stateless “dummy” application (whose single method simply approves), a contract provisions computational headroom dynamically, a technique we refer to as OpUp pooling. The pooled budget of a single group is nevertheless capped at roughly 1.9 × 105 units, which is below the cost of one forward NTT: post-quantum verification therefore cannot fit in one group and must be decomposed into a sequence of groups with persistent intermediate state (Section 6). Box Storage and Minimum Balance. Algorand box storage [7] is an unbounded key–value store scoped to an application. Obscura-PQ stores each commitment and each nullifier as an individual box, so ring-membership and double-spend checks are O(1) assertions on box existence, with no Merkle accumulator, no inclusion proofs, and no global state contention. Every box locks a minimum balance requirement (MBR) of 2500 + 400 · (key + value) micro-ALGO in the application account [7]; boxes are also the only mutable storage that survives across transaction groups, which the protocol exploits to persist verification state. Several further consensus limits matter: application arguments are capped at 2 048 bytes in total, each transaction carries at most 8 box/application/account references, each box reference adds only 1 024 bytes of I/O budget charged against the full size of every touched box, an atomic transaction group holds at most 16 transactions, and, although the number of boxes is unbounded, a single box value may not exceed 32 768 bytes [5]. The last limit is the one that ultimately caps the ring size (Section 9), since the transport box grows linearly in r; the 16transaction cap merely dictates that the transport upload be split across several groups at the largest ring sizes.

4

Cryptographic Construction

This section formalizes the lattice linkable ring signature at the core of ObscuraPQ. The scheme consists of the algorithms CoinKeyGen, SN, Sign, Verify, and Link; Appendix A gives the formal syntax and security definitions. 4.1

Public Parameters and Challenge Space

Four public ring elements a1 , a2 , a3 , a4 ∈ Rq are derived by a nothing-up-mysleeve hash-to-ring map, aj = Hring (DOM_PP ∥ j),

j ∈ {1, 2, 3, 4},

where the index j is encoded as four big-endian bytes, Hring expands SHA256 [57] in counter mode (SHA-256(seed∥counter) blocks) and reads successive 16-bit big-endian chunks modulo q, and DOM_PP is the fixed domain-separation

10

N. Azimi Table 1. Obscura-PQ system parameters.

Symbol

Meaning

Value

n, q η ς β2 w H rmax

ring degree and modulus of Rq = Zq [X]/(X + 1) width of the centred-binomial secret distribution standard deviation of the mask distribution squared-norm acceptance bound per response Hamming weight of ternary challenges (|C| > 2256 ) random oracle (challenge chain, H2C, Hring , nullifier) on-chain ring-size cap n

512, 12289 2 2500 4.2 × 109 48 SHA-256 10

string OBSCURA-PQ/DOM_PP/v2. Anyone can re-derive and audit the parameters; there is no trusted setup. The challenge space C consists of sparse ternary polynomials: elements of R
q with exactly w = 48 nonzero coefficients, each ±1. Its size satisfies |C| = 512 48 · 248 > 2256 , so challenges carry at least 256 bits of entropy. A deterministic map H2C : {0, 1}256 → C expands a 32-byte seed into positions and signs via SHA256 counter-mode blocks, skipping collisions; sparsity makes multiplication by a challenge a cheap signed-shift accumulation (O(nw) additions, no transform), which both the prover and the on-chain verifier exploit. All remaining protocol parameters are collected in Table 1. 4.2

Coin Generation (CoinKeyGen) and Serial Number (SN)

To deposit, a user samples a coin opening and publishes a binding commitment: 1. Sample the spend secret k and commitment randomness s independently from the centred binomial distribution with parameter η = 2 (coefficients in [−2, 2]), and derive the deterministic short serial-number blinding e = Hshort (k), a centred-binomial element expanded from k under a domainseparated hash. 2. Compute the coin commitment C = a1 k + a2 s + a4 e ∈ Rq , a rank-one Ring-SIS commitment in the style of [13], and publish its forward transform NTT(C) (1 024 bytes: 512 coefficients of 2 bytes). Binding follows from B1: opening C to a second short triple (k ′ , s′ , e′ ) ̸= (k, s, e) yields the Ring-SIS collision a1 (k −k ′ )+a2 (s−s′ )+a4 (e−e′ ) = 0. Hiding follows from B2. Each coin uses fresh, independent randomness, so compromise of one coin does not propagate. The serial number (key image) of a coin is the deterministic Ring-LWE image sn = a3 k + e ∈ Rq ,

Obscura-PQ: Post-Quantum Privacy for Algorand

11

computed by SN(k) at withdrawal time and revealed in full, transported as NTT(sn). The compact double-spend key is its digest
sn∗ = SHA-256 pack(NTT(sn)) . Because the opening (k, e) is unique (binding) and sn is deterministic in it, every spend of a coin, honest or adversarial, yields the identical sn∗ ; and because sn = a3 k + e has the form of a Ring-LWE sample (with e = Hshort (k) modeled as a random-oracle short error), recovering k from sn (search Ring-LWE) and deciding whether a given commitment shares its k with a given serial number (decisional Ring-LWE in the random-oracle model, Remark 1) are both hard, so revealing sn neither exposes the secret nor links the withdrawal to a deposit. The blinding e is bound into C via a4 e, so its determinism, hence double-spend soundness, follows from binding rather than from the honest hash derivation. 4.3

The Two Verification Relations and the Wire Format

Fix a ring of commitments C = (C0 , . . . , Cr−1 ) and a serial number sn. For a response triple (zk,i , zs,i , ze,i ) and challenge χi ∈ C, define the two responsesharing linear relations tpk = a1 zk,i + a2 zs,i + a4 ze,i − χi Ci , i

tsn = a3 zk,i + ze,i − χi sn. i

(1)

The first opens the ring commitment; the second reproduces the serial number. Both consume the same responses zk,i and ze,i , which is what binds the published serial number to the spent coin: a witness satisfying both relations at one index is a single short (k, e) that simultaneously opens Ci and satisfies sn = a3 k + e (Appendix A). By linearity of the NTT, the relations are evaluated pointwise in the frequency domain (note the identity multiplier on ze,i in the second relation, whose transform is the all-ones vector): c tpk i = â1 ⊙ ẑk,i +â2 ⊙ ẑs,i +â4 ⊙ ẑe,i − χ̂i ⊙ Ĉi ,

sn = â ⊙ ẑ ˆ (2) tc 3 k,i + ẑe,i − χ̂i ⊙ sn. i

This motivates the protocol’s wire format: commitments are stored as NTT(C), the serial number is transported as NTT(sn), the fixed-base transforms â1 , â2 , â3 , â4 are precomputed once at deployment, and the Fiat–Shamir chain hashes the packed frequency-domain images. Consequently the verifier computes only forward transforms of per-member data (zk,i , zs,i , ze,i , χi ) and never an inverse transform. Since the NTT is a bijection on Rq , binding is preserved and NTT(sn) determines sn exactly, the serial number remains revealed in full. 4.4

Signing (Sign)

The message is the settlement context µ = recipient(32) ∥ relayer(32) ∥ fee(8) ∥ appID(8) (80 bytes, big-endian),

12

N. Azimi

binding all values an adversary could profitably alter. The signer holds the opening (k, s, e) of Cπ at a secret index π ∈ [0, r) and proceeds as follows; the Fiat– Shamir chain values ci ∈ {0, 1}256 seed the ternary challenges χi = H2C(ci ), and the chain-update function is  
c
sn ∥ (i+1 mod r) , c ˆ ∥ pack tpk ci+1 mod r = H µ ∥ pack(sn) t ∥ pack i i with the index encoded as 2 bytes. 1. Commitment at the true index. Sample short masks yk , ys , ye from the rounded Gaussian Dς and compute c tpk π = â1 ⊙ ŷk + â2 ⊙ ŷs + â4 ⊙ ŷe ,

sn = â ⊙ ŷ + ŷ , tc 3 k e π

then derive cπ+1 by the chain update. 2. Decoy simulation. For i = π+1, . . . , π−1 (indices mod r): sample responses zk,i , zs,i , ze,i ← Dς , set χi = H2C(ci ), evaluate the relations (2), and derive ci+1 by the chain update. 3. Closure. At the true index, set χπ = H2C(cπ ) and close over the integers: zk,π = yk + χπ k,

zs,π = ys + χπ s,

ze,π = ye + χπ e.

4. Rejection sampling. Compute the standard Fiat–Shamir-with-aborts acceptance probability [44], a product of the per-response factors   Y 1 −2⟨zx,π , χπ x⟩ + ∥χπ x∥2 ρ = exp M 2ς 2 x∈{k,s,e}

for a bounding constant M , and accept with probability ρ. If rejected, or if any of ∥zk,π ∥2 , ∥zs,π ∥2 , ∥ze,π ∥2 exceeds β 2 , restart from step 1 with fresh masks. The probabilistic acceptance ratio decouples the distribution of accepted responses exactly from the secret (k, s, e). The signature is σ =

c0 , {(zk,i , zs,i , ze,i )}r−1 i=0 ,

of size exactly 32 + 3072r bytes (responses are packed as 512 signed 16-bit coefficients each). Sparsity of χπ and shortness of (k, s, e) keep the closure short, so honest responses pass the bound with overwhelming probability while the bound excludes the trivial (unboundedly long) solutions an adversary could otherwise construct. 4.5

Verification (Verify) and Linking (Link)

ˆ σ), the verifier sets c ← c0 and, for i = 0, . . . , r − 1: Given (C, µ, sn, 1. asserts the norm bounds ∥zk,i ∥2 ≤ β 2 , ∥zs,i ∥2 ≤ β 2 , and ∥ze,i ∥2 ≤ β 2 on the raw signed coefficient vectors;

Obscura-PQ: Post-Quantum Privacy for Algorand

13

2. computes χi = H2C(c) and the frequency-domain images (2); 3. updates c by the chain-update function. It accepts iff the final c equals c0 (ring closure). Link declares two withdrawals linked iff their nullifiers sn∗ coincide. Verification performs, per member, exactly four forward NTTs (for zk,i , zs,i , ze,i , and χi ), one pointwise combine, three norm checks, and one hash. This cost profile drives the on-chain design detailed in Section 6. Norm checks are performed on the raw signed integers as transmitted; checking a reduced representative would wrap around and be unsound.

5

Protocol Description

Obscura-PQ operates in two phases, deposit and withdrawal, mediated by a fixed-denomination pool contract. Throughout, BC and BN denote the on-chain commitment and nullifier box sets. 5.1

Deposit Phase

As illustrated in Figure 2, the user runs CoinKeyGen locally, stores the opening (k, s, e), and submits an atomic group of two transactions: an application call deposit carrying NTT(C), and a payment of the fixed denomination denom to the application address. The contract asserts the group shape, the payment amount and receiver, and the payload length; asserts that the commitment box keyed by
"c" ∥ SHA-256 NTT(C) does not yet exist (duplicate commitments are rejected); creates the box with value NTT(C); and increments a deposit counter. The 1 024-byte box locks an MBR of 425,300 micro-ALGO in the application account, the protocol’s principal per-deposit storage cost, which is deducted from the eventual payout (Section 9). The serial number is not published at deposit; only the commitment is. 5.2

Anonymity-Set Construction

Prior to withdrawal the client forms a ring C = (C0 , . . . , Cr−1 ) of on-chain commitments containing its own coin at a secret index, entirely off-chain: 1. Fetch the commitment boxes and verify the user’s own commitment is present; 2. Query the indexer for recent deposits and order the decoy pool by recency; decoy sampling that fails to mimic plausible spending behavior enables statistical deanonymization [39, 55], and recency bias counters temporal intersection attacks; 3. Draw decoys uniformly from a bounded recent pool (the 20 most recent valid decoys), avoiding the deterministic “always the newest r−1” selection; 4. Randomly select r − 1 decoy commitments from the recent pool (up to the maximum ring size rmax ), insert the user’s own commitment, and apply a Fisher–Yates shuffle [32] seeded from a cryptographically secure generator, making the signer’s position uniform.

14

N. Azimi

Client Application

Local Prover

Smart Contract

Box Storage

CoinKeyGen Request (POST /keygen) Sample k, s ∼ CBD(η=2); Derive e = Hshort (k); C = a1 k + a2 s + a4 e mod q Coin Secret (k, s, e) (3072 B), NTT(C) (1024 B)

Store (k, s, e) in localStorage TxGroup[deposit(NTT(C)), Pay(20.101 ALGO)]

Assert BC (H(NTT(C))) = ⊥

Write BC (H(NTT(C))) ← NTT(C)

Increment global depositCount

Fig. 2. Deposit phase sequence diagram. The client application delegates CoinKeyGen to the local prover, which samples the short coin secret (k, s) from a centred binomial distribution (η = 2), derives the deterministic blinding e = Hshort (k), and computes the Ring-SIS commitment C = a1 k + a2 s + a4 e mod q over the cyclotomic ring. The client stores the returned coin secret locally and submits an atomic transaction group pairing the deposit application call with the fixed-denomination payment of 20.101 ALGO. The smart contract verifies the payment, rejects duplicate commitments, allocates a new commitment box keyed by the hash of NTT(C) in on-chain storage, and increments the global deposit counter.

5.3

Withdrawal Phase

As depicted in Figure 3, the withdrawal phase begins off-chain. The client assembles the context µ (recipient, relayer, total fee, application ID) and requests a proof from the local prover, receiving sn∗ , NTT(sn), and σ. In the implementation, the withdrawing wallet self-relays: it fronts all transaction fees, and the total is bound into µ as the fee and reimbursed from the pool at settlement. The protocol equally supports third-party relayers; because the relayer address and fee are signature-bound, a relayer can neither redirect funds nor overcharge. However, a relayer network is not part of the current implementation. On-chain, the withdrawal spans a sequence of transaction groups (all constructed and signed in a single wallet interaction), detailed in Section 6: the proof is streamed into a transport box, 9r verification phases recompute the challenge chain member by member, and the final withdraw call checks closure and settles. Settlement is atomic: the contract deletes the transient boxes, records sn∗ in BN , and issues three inner payments, the payout denom − fee − cstor to the recipient (where cstor = 441,000 micro-ALGO covers the permanent commitment and nullifier MBRs), the bound fee to the relayer, and the refund of all fronted transient MBRs.

Obscura-PQ: Post-Quantum Privacy for Algorand

Client Application

Local Prover

Smart Contract

Dummy App

15

Box Storage

Fetch commitments {Ci } (algod/indexer) Form ring R (recency-biased decoys, Fisher–Yates shuffle) Sign((k, s, e), R, µ) POST /generate proof

sn = a3 k + e; AOS/Borromean chain with norm-based rejection sampling sn∗ , NTT(sn), σ = (c0 , {(zk,i , zs,i , ze,i )}) TxGroup[Pay(MBR), init proof(sn∗ , len)] Create Bp (sn∗ ) put proof: stream payload (≤1960 B chunks) Write NTT(sn) ∥ ring keys ∥ c0 ∥ r·(zk ∥zs ∥ze ) into Bp 9r× prep ntt(sn∗ , phase) groups, strict order 1828r Inner opup Calls (250/175 per phase) Split NTTs + chain fold: update Bp /"v"/"w"/"s"; read BC (Ci ) and re-assert ring id (combine, per member) withdraw(sn∗ , ring keys, µ) Assert marker = 9r; Fiat–Shamir closure: running c = c0 Assert BN (sn∗ ) = ⊥; BC (Ci ) ̸= ⊥

∀Ci ∈ R

Delete Bp /"v"/"w"/"s"; Write BN (sn∗ ) ← ⊤ 3 inner payments: DENOM−fee−441k → recipient, fee and MBR refund → relayer

Fig. 3. Withdrawal phase sequence diagram. The client application constructs an anonymity set from on-chain public commitments and delegates signing to the local prover, which derives the serial number sn = a3 k+e and produces the AOS/Borromeanstyle lattice ring signature under norm-based rejection sampling. Because the signature exceeds application-argument limits, the client first creates a proof transport box (init_proof) and streams the payload into it in chunks (put_proof). Verification then runs as 9r strictly ordered prep_ntt groups that perform the split NTTs and fold the Fiat–Shamir challenge chain, expanding the opcode budget via 1828r inner opup calls to a dummy application and re-asserting each ring member’s commitment against Box Storage. The final withdraw call asserts chain closure (c = c0 ), validates the nullifier and ring membership, deletes the transient boxes, records the nullifier, and settles the payment with three inner transactions.

16

5.4

N. Azimi

Double-Spend Prevention

The digest sn∗ is the nullifier. The contract binds it to the transported serial number by recomputing sn∗ = SHA-256(pack(NTT(sn))), asserts that no box "n"∥sn∗ exists, and creates that box atomically with the payout. Because the opening (k, e) is unique by commitment binding and sn = a3 k + e is deterministic, any second spend of the same coin presents the identical sn∗ and reverts, regardless of the decoy set chosen. A malicious signer cannot substitute a fresh serial number: a verifying signature with sn′ ̸= a3 k + e would require opening Cπ to a second short opening (a Ring-SIS collision) or violating relation (1) (Appendix A).

6

On-Chain Execution

This section describes how the verifier of Section 4.5 executes natively on the AVM. The main difficulty is quantitative: verifying one ring member requires four degree-512 forward NTTs, and a single forward NTT with its norm check consumes approximately 2.05 × 105 opcode units (measured on the deployed contract via the node’s simulate endpoint), whereas one transaction group pools at most about 1.9×105 units. Lattice verification therefore cannot fit in any single group, and the design decomposes it into a resumable sequence of groups with box-persisted intermediate state. 6.1

Proof Transport via Box Streaming

The proof material, NTT(sn) (1 024 B), the r ring-member identifiers (32 B each), the chain seed c0 (32 B), and the responses (3072r B), totals 1056 + 3104r bytes and exceeds the 2 048-byte application-argument limit for any r ≥ 1. The client therefore streams it into an application-owned transport box keyed "p"∥sn∗ before verification begins: 1. init_proof: an atomic group in which a payment covering the transport box’s MBR plus the transient-state MBR (482,600 micro-ALGO) precedes the application call that creates the box; the funder’s address is recorded in the box header, and only the funder may write to or clear the box. 2. put_proof: the payload is written in chunks of at most 1 960 bytes (the residual application-argument budget), bounds-checked against the declared length. Because each write is offset-addressed and mutually independent (the box becomes load-bearing only when prep_ntt first reads it), the chunks need not share one atomic group; when their number would exceed the 16transaction group cap, they are split across several sequential groups, each carrying enough box references to cover the transport box’s full-size I/O budget. Writing is frozen permanently once verification starts. 3. clear_proof: at any time before settlement the funder may delete the flow boxes and reclaim the full fronted MBR. Box keys are deterministic in sn∗ , so a withdrawal that failed mid-flow leaves recognizable state; the client detects and clears it automatically before retrying (self-healing).

Obscura-PQ: Post-Quantum Privacy for Algorand

17

All transient MBRs are refunded at settlement, so the permanent state growth of a withdrawal is the empty nullifier box alone. 6.2

Split NTTs and the Per-Member Phase Machine

Each forward NTT is split at butterfly length 32 into two opcode-pooled phases: a heavy half (norm check and signed-to-modular reduction of the input, the ψpremultiplication fused with the bit-reversal permutation, and butterfly stages up to length 32; 250 inner OpUp calls) and a light half (stages 64 through 512; 175 inner OpUps). Intermediate buffers persist in box storage between phases: response transforms overwrite their slots in the transport box in place, and the challenge transform lives in a dedicated box "w"∥sn∗ . All coefficient products are bounded by q 2 ≈ 1.5×108 < 264 , so native 64-bit arithmetic suffices; the twiddlefactor, ψ-power, and bit-reversal tables are compile-time constants generated from a reference implementation (Section 7). Verification of member i comprises nine phases, invoked as successive prep_ntt application calls (Figure 4): phases 0–1 transform zk,i , phases 2–3 transform zs,i , phases 4–5 transform ze,i , and phases 6–7 derive χi = H2C(c) from the running chain value and transform it. Finally, phase 8 performs the pointwise two-relation combine (2). It reads the fixed-base transforms from the parameter box and the member’s commitment box, re-asserts that the claimed ring identifier equals the SHA-256 digest of the stored commitment, and folds the chain update into a running-state box "s"∥sn∗ . Phase 0 of member 0 additionally seeds the state box with c0 and the settlement context (recipient, relayer, fee). A marker box "v"∥sn∗ enforces strict phase ordering; because the challenge of member i depends on member i−1’s relation images, members are processed strictly in order. The per-member cost is 4 × (250 + 175) + 128 = 1828 inner OpUp calls ≈ 1.828 ALGO at the 1 000 micro-ALGO minimum fee, which, together with the growing transportbox MBR, is the practical force keeping rings small (Section 9). Auxiliary opup calls in each group act purely as reference carriers, working around the 8reference and box-I/O-budget limits. 6.3

Settlement and Method Semantics

After all 9r phases, the withdraw call asserts: the transport-box layout and the equality of the submitted ring identifiers with the box copy; the binding sn∗ = SHA-256(pack(NTT(sn))); the marker value 9r (all phases complete); ring closure, i.e., the running chain value equals c0 ; the absence of the nullifier box; the existence and digest-match of every ring member’s commitment box; and fee + cstor < denom. It then deletes the flow boxes, creates the nullifier box, and issues the three inner payments of Section 5.3. Table 2 summarizes the contract interface.

18

N. Azimi

Loop Core: 9r prep ntt Groups

init proof MBR payment + box create

put proof  1056+3104r  chunks 1960

NTT(zk,i ) 2 phases (250+175)

NTT(zs,i ) 2 phases (250+175)

NTT(ze,i ) 2 phases (250+175)

χi , NTT(χi ) 2 phases (250+175)

combine + chain fold (128)

withdraw closure check + settlement

repeated in order for members i = 0, . . . , r − 1 (9r prep ntt groups; 1828 inner OpUps per member)

Fig. 4. The withdrawal pipeline as a sequence of atomic transaction groups. Parenthesized numbers are the inner OpUp calls provisioning each phase’s pooled opcode budget. Intermediate transforms persist in box storage between groups; a marker box enforces strict phase ordering, and the final withdraw call asserts that the running Fiat– Shamir chain closed back to c0 before settling. The loop core consists of 9r prep_ntt groups.

Every assertion failure reverts its group, and settlement values (recipient, relayer, fee) are read from the state box, the same values every challenge was computed over, so the payout cannot deviate from what the signature authorized. The nullifier is recorded iff the chain closed, and funds move iff the nullifier is recorded. The groups of the pipeline are not atomic with one another; a midflow abort strands only refundable boxes, which the self-healing path reclaims. Phase submission is permissionless: any account may advance the pipeline for a given sn∗ . This never endangers funds, because settlement pays only to the settlement context folded into the challenge chain and any mismatched context makes closure fail; it does mean that a pipeline seeded with an incorrect context, for instance by a party that races the first phase, will not close and must be cleared and restarted by its funder. The design therefore guarantees fund safety but not censorship-resistant liveness for a targeted withdrawal.

7

Implementation

Obscura-PQ is deployed as a full-stack application partitioned into three trust domains (Figure 5); the complete implementation source code is publicly available (see Code Availability). Smart-Contract Layer. The contract is written in PyTeal [8] (version 0.27.0) and compiles to TEAL v10 bytecode. All lattice arithmetic, the table-driven negacyclic NTT, signed-to-modular reduction, norm accumulation, the sparse ternary challenge expansion, and the pointwise combine, is implemented directly in TEAL subroutines over byte-packed coefficient arrays. The 4 096-byte fixedbase transforms would push the approval program past its 8 192-byte (four-page) size cap and exceed the 2 048-byte argument limit, so they are provisioned once at deployment into a dedicated parameter box and read only by the combine phase.

Obscura-PQ: Post-Quantum Privacy for Algorand

19

Table 2. Smart-contract methods (routing on the first application argument). Method

Guard and effect

deposit

group of 2 with denom payment; commitment box absent ⇒ create "c"∥H(NTT(C)), increment counter creator-only, deploy-time; stream the 4 096-byte fixedbase transforms â1 ∥â2 ∥â3 ∥â4 into the pp box preceding payment ≥ transport MBR + 482,600; payload length = 1056 + 3104r, r ∈ [1, rmax ]; box absent ⇒ create "p"∥sn∗ , record funder sender is the recorded funder; verification not started; bounds-checked chunk write sender is the recorded funder ⇒ delete flow boxes, refund the full MBR marker equals the requested phase, phase < 9r ⇒ run the phase’s substep, issue its inner OpUps, advance the marker all settlement assertions above ⇒ delete flow boxes, create "n"∥sn∗ , three inner payments unconditional approve (budget target / reference carrier)

init_params / put_params init_proof

put_proof clear_proof prep_ntt

withdraw opup

Local Prover. CoinKeyGen, SN, and Sign execute in a local Python prover exposing an HTTP API on localhost. The prover must run on the user’s own machine: the coin opening (k, s, e) is the spend authority, and any party obtaining it can steal the coin and break anonymity. In the current implementation the secret travels between browser and prover over local HTTP and is persisted in plaintext browser storage with manual export/import; a hardened deployment would use an in-process (WebAssembly) prover or authenticated local IPC and an encrypted secret store. Signing takes milliseconds to seconds, dominated by the O(r) ring pass and a small expected number of rejection-sampling restarts.

Client Application. The client is a React/TypeScript application handling wallet integration [60], ring formation (recency-biased decoy selection over a bounded recent pool, Fisher–Yates shuffling seeded by crypto.getRandomValues() [49]), fee and box-reference planning across the pipeline’s transaction groups, proof streaming, phase submission, and self-healing cleanup of stranded flows. The repository additionally ships deployment scripts (which provisions the dummy application, funds the contract, and uploads the parameter box), a bytecodeverification script that recompiles the PyTeal source and compares it byte-forbyte against the deployed program, and two analysis tools (a transaction-graph explorer and an indexer-backed transaction classifier) used to audit ledger state.

20

N. Azimi

Fetch commitments {Ci }

Local Prover Enclave (localhost:5000)

Client Environment Local RPC

Client Application (Obscura.tsx)

/keygen, /generate proof

Algorand Blockchain (AVM) Blockchain Indexer (State Queries, Decoy Recency)

Prover API (backend server.py, Flask) Obscura Contract (obscura contract.py / ntru teal.py)

Wallet Provider (Signs All Groups Up Front)

Lattice Engine (obscura engine.py, ntru ring.py)

Box Storage (BC , BN , pp; transient p/v/w/s)

Dummy Application (OpUp Target / Aux Ref. Carriers) Submit TxGroups: deposit / init+put proof / 9r×prep ntt / withdraw

Fig. 5. Obscura-PQ implementation architecture. The system is partitioned into three distinct trust domains. The client environment handles decoy selection and transaction construction, with the wallet provider signing all withdrawal groups in a single prompt. The local prover enclave, a Flask service on localhost:5000, executes the heavy lattice arithmetic (coin sampling, Ring-SIS commitment, and AOS/Borromean-style signing with rejection sampling) without exposing the coin secret (k, s, e) to the network. The Algorand blockchain enforces state transitions, utilizing the indexer for state queries and decoy recency ordering, Box Storage for membership and nullifier checks alongside the public-parameter and transient withdrawal-flow boxes, and a dummy application for opcode pooling and auxiliary box-reference carrying.

8

Security and Privacy Analysis

We analyze Obscura-PQ under an explicit adversarial model. Formal definitions, theorem statements, and proofs are given in Appendix A; this section states the guarantees, their assumptions, and their limitations.

8.1

Threat Model

We assume a public, immutable ledger: a globally passive adversary [26] observes every commitment, every ring, every serial number, every context µ, and every signature. An active adversary may submit malformed signatures, attempt double-spends and replays, fabricate ring members, choose serial numbers adversarially, act as a malicious relayer or block proposer, and tamper with transport boxes mid-upload. The quantum adversary may run Shor’s and Grover’s algorithms [38, 66]. We assume the Algorand consensus layer and AVM semantics are correct [35], and that Sign executes in a trusted local environment; a remote prover would trivially break both anonymity and theft resistance. Network-layer deanonymization and endpoint compromise are out of scope.

Obscura-PQ: Post-Quantum Privacy for Algorand

8.2

21

Guarantees

Unforgeability and Theft Resistance. The challenge chain is relaxed specialsound: two accepting transcripts that share relation images but differ in one challenge yield, by the standard extractor, a relaxed short opening (z̄k , z̄s , z̄e ) satisfying a1 z̄k + a2 z̄s + a4 z̄e = χ̄ Ci and a3 z̄k + z̄e = χ̄ sn for the challenge difference χ̄ (Theorem 2; the extractor recovers an exact opening only relative to χ̄, as short challenge differences are not invertible in the fully splitting ring). Producing a verifying withdrawal for a ring of honest deposits without knowing a ring member’s opening therefore breaks Ring-SIS. Two implementation details are essential to soundness and are enforced on-chain: the norm bounds on every raw response (without which the relations are trivially satisfiable), and the ringexistence check with digest matching (without which an adversary could inject a fabricated commitment whose opening it knows). The transport-box freeze prevents rewriting a response after its norm has been checked. Signer Ambiguity and Unlinkability. After rejection sampling, the true-index responses are distributed (up to negligible statistical distance) like the forwardsampled decoy responses and independently of (k, s, e); every challenge is a random-oracle output independent of the signer index; and the commitment C = a1 k + a2 s + a4 e is pseudorandom under Ring-LWE, so the transcript is simulatable from (C, µ, sn) alone. The only residual signer-dependent value is the serial number sn = a3 k + e, which has the form of a Ring-LWE sample with the deterministic error e = Hshort (k); modelling Hshort as a random oracle it hides k, so its linkage to a commitment is hard under decisional Ring-LWE in the random-oracle model (Remark 1). Consequently no probabilistic polynomialtime adversary identifies the signer with probability non-negligibly exceeding 1/r (Theorem 3), and no observer links a deposit to a withdrawal beyond the 1/r ring ambiguity. Deciding whether a commitment and a serial number share the same k reduces to decisional Ring-LWE (in the ROM), and recovering the short k from sn is the search Ring-LWE problem. The anonymity set is the ring, of size at most rmax , not the whole pool (see Section 8.3). Linkability, Double-Spend Prevention, and Non-Frameability. Every verifying signature carries the serial number a3 k + e of the unique short opening of one ring member (Theorem 4); uniqueness is commitment binding, not an honesty assumption, so double-spend detection is sound even against a malicious signer who deliberately deviates from the signing algorithm. Conversely, to pre-spend or block an honest user’s coin an adversary would have to produce a verifying signature carrying that coin’s serial number, which by the extraction argument requires the coin’s own opening (Lemma 2). The contract enforces nullifier uniqueness atomically with the payout, so each coin is spendable exactly once. Replay and Front-Running Resistance. The full context µ (recipient, relayer, fee, and application identifier) is hashed into every challenge; altering any component breaks ring closure (Lemma 3). The contract additionally settles to the values

22

N. Azimi

stored in the chain-bound state box, so a malicious relayer or proposer cannot redirect the payout or inflate the fee even at the settlement step. Replaying an executed withdrawal is blocked by the recorded nullifier, and the applicationidentifier binding blocks cross-deployment replay. Auditability. As in accountable-privacy designs [34], a user may voluntarily disclose a coin opening (k, s, e) to an auditor, who can verify the deterministic blinding e = Hshort (k) and can then verify both the deposit commitment C = a1 k + a2 s + a4 e and the withdrawal serial number sn = a3 k + e, establishing provenance without affecting any other participant’s anonymity. 8.3

Limitations and Open Gaps

We state explicitly what the analysis does not establish. – Ring-bounded anonymity. Signer ambiguity is 1/r, not pool-wide hiding as in accumulator-based SNARK pools. Operational behavior (immediate withdrawal after deposit, correlated timing, small pools) can degrade the effective anonymity below the cryptographic ceiling [18, 39, 55]; the client’s recency-biased selection and secure shuffling mitigate but cannot eliminate this. – Anonymity in the ROM and self-correlated serial-number noise. Anonymity and unlinkability reduce to decisional Ring-LWE in the randomoracle model (ROM). Because the serial-number error e = Hshort (k) is a deterministic function of the secret k (bound into the commitment via a4 e), the serial number sn = a3 k + e constitutes a self-correlated-noise Ring-LWE instance. Consequently, the reduction models Hshort as a random oracle rather than claiming a black-box reduction to standard decisional Ring-LWE (see Assumption 3 and Remark 1); recovering k from sn remains search RingLWE. A standard-model reduction could be achieved by sampling e independently and storing it as part of the coin, though this would increase the size of the persisted secret. Separately, because short challenge differences are not guaranteed to be invertible in the fully splitting Falcon-512 ring, our unforgeability extractor recovers a relaxed opening. This extraction is nevertheless sufficient to prove theft resistance and non-frameability (Appendix A, Remark 1). – Classical ROM proofs. The reductions in Appendix A are in the classical random-oracle model, following the analysis templates of [29, 44, 68]. A dedicated QROM analysis [20, 27] of the composed scheme has not been carried out. – Sampler simplification. The implemented mask sampler uses a rounded Gaussian with a norm-bound-only acceptance test, rather than a constanttime discrete Gaussian equipped with the full Fiat–Shamir-with-aborts acceptance ratio [44]. Furthermore, while true-index responses are conditioned on the norm bound via rejection sampling, decoy responses are drawn from the unconditioned mask distribution. Because the formal zero-knowledge

Obscura-PQ: Post-Quantum Privacy for Algorand

23

simulation argument assumes the full acceptance ratio and identically distributed responses across all indices, the theoretical anonymity guarantee holds exactly only for the idealized sampler. A production deployment must implement the fully hardened sampler to achieve the stated bounds. – Liveness under permissionless phase submission. Because the prep_ntt method imposes no sender checks (Section 6), any account can advance the withdrawal pipeline. While this permissionless design cannot lead to fund theft or redirection (since settlement is strictly bound to the context folded into the challenge chain, and any mismatch causes verification to fail) it does introduce a liveness vulnerability. A malicious third party could race the first phase or squat the transport box, forcing a targeted withdrawal to abort and requiring the user to restart the process. Consequently, the current design prioritizes fund safety over censorship-resistant liveness. Restricting phase submission and box creation exclusively to the proof funder would eliminate this denial-of-service vector. – Concrete parameters. While the ring parameters (n, q) are inherited directly from Falcon-512, the remaining parameters (η, ς, β, w) were selected primarily to ensure correctness and efficient rejection-sampling termination. Because these values have not yet been calibrated against a formal lattice estimator [4], we do not claim a specific bit-security level for the current parameter set. – Unaudited implementation. The TEAL transcription of the lattice arithmetic is validated through extensive mirror testing and live on-chain execution. However, it has not yet been subjected to formal verification or a third-party security audit.

9

Cost Analysis

AVM opcode pricing, transaction fees, and storage deposits are deterministic: they depend strictly on protocol constants and the ring size r, rather than network congestion. This section develops the resulting closed-form cost model and evaluates the protocol’s performance on the Algorand testnet. We explicitly distinguish between exact theoretical costs and empirical measurements. Specifically, the proof transport size (Figure 6) and the storage MBRs (Figure 7) are derived in closed form from the protocol constants. In contrast, the remaining metrics including inner opup calls (Figure 8), transaction fees (Figure 9), total wall-clock runtime (Figure 10), local proof generation time (Figure 11), local proof size (Figure 12), and the detailed latency breakdowns for deposits (Figure 13) and withdrawals (Figure 14) are empirical results drawn directly from live executions on the Algorand testnet. Communication. The signature is 32+3072r bytes and the full transport payload (serial-number transform, ring identifiers, chain seed, responses) is 1056 + 3104r bytes, streamed in at most ⌈(1056 + 3104r)/1960⌉ chunks (Figure 6). As detailed in Figure 12, the raw proof size scales deterministically with the anonymity set,

24

N. Azimi

reaching over 30 KB at the maximum ring size. This linear growth in r is intrinsic to the AOS/Borromean challenge-chain structure, as in classical LSAG; what changes in the lattice setting is the constant, 3 104 bytes per member versus 96 for an elliptic-curve instantiation [12], which is why box streaming, rather than argument passing, is unavoidable. Execution. Verification costs 9r phase groups and 1828r inner OpUp calls. As illustrated in Figure 8, this dynamic budget provisioning leads to an O(r) scaling in the total number of inner transactions. Consequently, this translates to about 1.828r ALGO of inner fees, plus a fixed overhead of transport and settlement transactions (Figure 7). Furthermore, Figure 9 contrasts this linearly scaling withdrawal fee against the constant 0.001 ALGO deposit fee, highlighting the asymmetric cost profile of the protocol. The denomination is derived in the contract from the worst case at r = rmax :
denom = 60 + 1860 rmax · 103 + 425,300 + 15,700 + 106 = 20,101,000 micro-ALGO. where 1860 over-approximates the per-member OpUps plus phase and referencecarrier transactions, 60 covers the fixed overhead, the two MBR terms cover the permanent boxes, and 106 is slack. The recipient receives denom − fee − 441,000 micro-ALGO; the fee is the withdrawer’s actual fronted total, bound into µ and reimbursed to the (self-)relayer. Storage. Table 3 itemizes the box MBRs. Permanent state grows by one 1 024byte commitment box per deposit (≈ 0.425 ALGO locked) and one empty nullifier box per withdrawal (≈ 0.016 ALGO); all verification-flow boxes, including the large transport box (≈ 8.77 ALGO of MBR at r = 10), are deleted at settlement and their deposits refunded. Compared with accumulator-based designs, the flat state model trades Merkle-update computation and state contention for O(N ) box storage with a per-deposit constant. Scalability Trade-off. Both cost curves are linear in r, so the protocol cannot approach the pool-wide anonymity sets of succinct-proof pools. With the threeresponse wire format, the cap rmax = 10 is a hard structural limit rather than merely an economic one: the single transport box holds 1088+3104r bytes, which is 32 128 B at r = 10 and thus fits within Algorand’s 32 768-byte per-box ceiling. The on-chain arithmetic is correct for any r, and per-member fees plus the growing transport MBR make rings near the cap costly in any case. Raising it would require splitting the transport across multiple boxes (each independently bounded by 32 768 bytes), a straightforward but currently unimplemented extension. Off-chain signing is O(r) ring operations plus a small expected number of rejection restarts and completes in milliseconds to seconds. As shown in Figure 11, the proof generation time remains sub-second across all measured ring sizes, indicating that the computational burden on the client’s local prover is negligible compared to the on-chain verification workload. On-chain verification

Obscura-PQ: Post-Quantum Privacy for Algorand

25

·104 Signature σ (32 + 3072r) Transport payload (1056 + 3104r)

Size (bytes)

3

2

1

0 1

2

3

4

5 6 Ring Size r

7

8

9

10

Fig. 6. Proof and transport sizes versus ring size, computed from the wire format of Section 4. Every payload exceeds the AVM’s 2 048-byte application-argument limit, necessitating box-streamed transport; the transport box adds the serial-number transform, the ring identifiers, and a funder header to the signature itself.

Fee (ALGO)

20

Inner OpUp fees (1.828r) Fee envelope (0.06 + 1.86r)

15 10 5 0 1

2

3

4

5 6 Ring Size r

7

8

9

10

Fig. 7. Withdrawal verification fees versus ring size, computed from the AVM’s deterministic fee schedule at the 0.001-ALGO minimum fee. The lower curve is the inner OpUp cost of the 9r verification phases (1828 calls per member); the upper curve is the envelope used to derive the denomination, additionally covering the outer phase, reference-carrier, transport, and settlement transactions. The actual fronted fee is bound into the signature context µ and reimbursed from the pool at settlement.

26

N. Azimi

Table 3. Box storage and minimum-balance accounting (micro-ALGO; MBR = 2500+ 400(key + value)). Box

Value size (B) MBR

commitment "c"∥H(NTT(C)) 1024 nullifier "n"∥sn∗

0

parameters pp

4096

transport "p"∥sn∗

1088 + 3104r

challenge "w"∥sn∗

1024

state "s"∥sn∗

104

marker "v"∥sn∗

8

Lifetime

425,300

permanent, per deposit 15,700 permanent, per withdrawal 1,641,700 permanent, deploy-time 2500 + 400(1121 + 3104r) flow, refunded 425,300 flow, refunded 57,300 flow, refunded 18,900 flow, appfunded, deleted

spans 9r +O(1) sequential transaction groups and therefore finishes within a correspondingly bounded number of blocks. The wall-clock latencies in Figure 10, broken down in Figures 13 and 14, are Algorand testnet measurements dominated by transaction submission and network confirmation; they characterize the deployment environment rather than the protocol itself, and we report them for completeness rather than as an intrinsic protocol benchmark. 9.1

Latency Breakdown

To better understand the end-to-end performance characteristics of the protocol, the total wall-clock latencies are decomposed into discrete operational stages measured directly within the client application. As illustrated in Figure 13, the deposit workflow consists of four sequential stages: 1. Deposit Detail Generation: The client requests a new coin from the local prover enclave, which samples the coin secret (k, s), derives the deterministic blinding e (storing the full tuple (k, s, e)), and computes the Ring-SIS commitment C. 2. Transaction Construction: The client hashes the commitment to derive the box storage key and constructs the atomic transaction group, pairing the deposit application call with the fixed-denomination payment. 3. Transaction Submission: The client delegates the transaction group to the wallet provider for cryptographic signing and submits the signed group to the Algorand node’s REST API.

Obscura-PQ: Post-Quantum Privacy for Algorand

27

4. Network Confirmation: The client polls the node, waiting for the submitted transaction group to be committed to a block by the Algorand consensus protocol. Because the deposit phase involves only a constant-time commitment generation and a single atomic transaction group, all latency components remain independent of the ring size r. Conversely, Figure 14 details the five stages of the withdrawal workflow: 1. Withdrawal Data Generation: The client queries the blockchain indexer for recent commitments, selects a recency-biased decoy pool, inserts the user’s true commitment, and applies a Fisher–Yates shuffle to form the anonymity set. 2. Proof Generation: The client delegates the ring and settlement context to the local prover enclave to produce the lattice ring signature. 3. Transaction Construction: The client calculates the dynamic fee budget and constructs the sequence of transaction groups required for verification: the init_proof box allocation, the put_proof chunked payload streaming, the 9r prep_ntt phases with their inner opup calls and auxiliary reference carriers, and the final withdraw settlement group. 4. Transaction Submission: The client delegates the entire sequence of transaction groups to the wallet provider for signing in a single prompt, and then sequentially submits them to the Algorand node. 5. Network Confirmation: The client polls the node, waiting for the final withdraw transaction group to be confirmed, which guarantees that the entire verification pipeline succeeded and the funds were settled. As shown in Figure 14, the off-chain stages (Data Generation, Proof Generation, and Transaction Construction) execute in sub-second or near-second time. The linear growth in total withdrawal latency is driven entirely by the on-chain stages (Transaction Submission and Network Confirmation), which must sequentially process the 9r+O(1) transaction groups required to overcome the AVM’s opcode limits.

10

Conclusion

We presented Obscura-PQ, a decentralized, non-custodial privacy protocol that demonstrates the practical feasibility of post-quantum cryptography on highly constrained public blockchains. By evaluating all relations in the number-theoretictransform (NTT) domain, splitting table-driven NTTs across opcode-pooled execution phases, and leveraging box-streamed proof transport, we successfully deployed a setup-free lattice linkable ring signature natively on the Algorand testnet. Our construction binds a Ring-SIS commitment to a deterministic RingLWE serial number using an AOS/Borromean-style challenge chain, achieving double-spend soundness, unforgeability, and anonymity in the classical randomoracle model without relying on a global Merkle accumulator.

N. Azimi

Number of Inner Transactions

28

2

·104 Inner Transactions

1.5 1 0.5 0 1

2

3

4

5 6 Ring Size

7

8

9

10

Transaction Fee (ALGO)

Fig. 8. Number of inner transactions issued during the withdrawal phase versus ring size. To overcome the strict per-transaction AVM opcode budget, the verifier splits the NTT-based lattice ring signature check into nine phases per ring member and dynamically provisions execution budget through grouped inner opup calls. Each ring member requires 1828 inner transactions (4 × (250 + 175) + 128), leading to an O(r) scaling in the total number of inner transactions.

Deposit Fee Withdrawal Fee

101 100 10−1 10−2 10−3 1

2

3

4

5 6 Ring Size

7

8

9

10

Fig. 9. Deposit and withdrawal transaction fees as a function of ring size (logarithmic fee axis). The deposit fee remains constant at 0.001 ALGO, since depositing only requires a standard payment transaction and a box allocation for the coin commitment. Conversely, the withdrawal fee scales linearly with the ring size: the on-chain lattice verification provisions its AVM opcode budget through 1828 inner opup calls per ring member (≈ 1.828 ALGO each), plus phase and auxiliary reference-carrier transactions, raising the total fee from 1.92 ALGO at r = 1 to 18.66 ALGO at r = 10.

Obscura-PQ: Post-Quantum Privacy for Algorand

29

Time (ms)

Deposit Total Time Withdrawal Total Time 105

104

1

2

3

4

5 6 Ring Size

7

8

9

10

Proof Generation Time (ms)

Fig. 10. End-to-end deposit and withdrawal latency across varying ring sizes (logarithmic time axis). The deposit process exhibits a stable latency profile of roughly 5–7 s regardless of the anonymity set size, as its operations are constant-time. In contrast, withdrawal latency grows linearly from about 58 s at r = 1 to 468 s at r = 10, driven not by off-chain signing but by the on-chain verification workload: submitting the 9r phase groups and their 1828r inner opup transactions required to cover the lattice verification opcode cost.

800

Proof Generation Time

600 400 200 0 1

2

3

4

5 6 Ring Size

7

8

9

10

Fig. 11. Post-quantum ring signature proof generation time versus ring size. The offchain local prover executes the AOS/Borromean-style Sign algorithm over the cyclotomic ring Rq = Zq [X]/(X 512 + 1), q = 12289. Unlike the on-chain verification cost, signing remains sub-second (mean values between 359.20 ms and 526.00 ms) across all measured ring sizes; the run-to-run variation stems mainly from norm-based rejection sampling, which restarts the signing attempt until all responses satisfy the short-vector norm bounds.

30

N. Azimi ·104 Proof Size

Proof Size (bytes)

3

2

1

0 1

2

3

4

5 6 Ring Size

7

8

9

10

Fig. 12. Proof size growth as a function of ring size. The packed signature σ = (c0 , {(zk,i , zs,i , ze,i )}r−1 i=0 ) comprises a 32-byte initial challenge and, per ring member, three 512-coefficient response polynomials stored at 2 bytes per coefficient, yielding a deterministic size of 3072r + 32 bytes. Since this payload far exceeds applicationargument limits, it is uploaded in chunks into a dedicated proof box, and the smart contract shape-checks the ring size to r ∈ [1, 10], dictating the practical upper bound of the anonymity set. 8,000

Time (ms)

6,000 4,000 2,000 0 1

2

3

4

5 6 Ring Size

Deposit Detail Generation Transaction Submission Total Deposit Time

7

8

9

10

Transaction Construction Network Confirmation

Fig. 13. Breakdown of deposit latency versus ring size. The total deposit time is decomposed into four discrete operational stages: deposit detail generation, transaction construction, transaction submission, and network confirmation. Because the deposit phase involves only a constant-time Ring-SIS commitment generation and a standard atomic transaction group with a single box allocation, all latency components remain independent of the ring size r, with the total dominated by network confirmation and transaction submission.

Obscura-PQ: Post-Quantum Privacy for Algorand

31

106

Time (ms)

105 104 103 102 101 1

2

3

4

5 6 Ring Size

Withdrawal Data Generation Transaction Construction Network Confirmation

7

8

9

10

Proof Generation Transaction Submission Total Withdrawal Time

Fig. 14. Breakdown of withdrawal latency versus ring size (logarithmic time axis). The off-chain stages (withdrawal data generation, proof generation, and transaction construction) all remain at or below roughly one second irrespective of the ring size. The end-to-end time is instead dominated by transaction submission, which grows linearly from about 52 s at r = 1 to 461 s at r = 10 as the client submits the 9r on-chain verification phase groups carrying 1828r inner opup transactions, while the final network confirmation wait stays constant at roughly 5.3 s.

Several important directions remain for future work. On the cryptographic front, a formal security analysis in the quantum-accessible random-oracle model (QROM) [27] and the calibration of concrete bit-security parameters using formal lattice estimators [4] are necessary next steps. Furthermore, a production deployment requires a fully hardened, constant-time discrete Gaussian sampler with the complete Fiat–Shamir-with-aborts acceptance ratio [44]. On the protocol side, exploring sublinear post-quantum accumulators or logarithmic ring signatures [16, 19] could enable significantly larger anonymity sets, provided their verifiers remain compatible with our phase-decomposed execution model. Additionally, integrating confidential amounts in the style of MatRiCT [30] and establishing a third-party relayer network utilizing our signature-bound relayer role would greatly expand the protocol’s utility. Finally, formal verification of the TEAL phase machine and independent security audits remain critical prerequisites for mainnet deployment.

Code Availability To facilitate reproducibility and public auditing, the complete source code is available at https://github.com/n-azimi/Obscura-PQ. The repository includes the PyTeal smart contract, local lattice prover, React client, test suites, and

32

N. Azimi

ledger-analysis utilities. All empirical measurements reported in Section 9 were derived directly from Algorand testnet executions of this implementation.

A

Formal Definitions and Security Arguments

This appendix formalizes the lattice linkable ring signature underlying ObscuraPQ and relates each security property to the assumptions of Section 3. The arguments follow established analysis templates for Fiat–Shamir-with-aborts sigma protocols and commitment-based linkable ring signatures [3, 29, 44, 68]. We present the reductions, indicating precisely where each assumption enters, and we flag the points at which the implemented scheme deviates from the analyzed abstraction (Remark 1). All reductions are in the classical random-oracle model. We are deliberately conservative about what is proven: the extractor recovers a relaxed opening rather than an exact one (Theorem 2). The anonymity argument reduces to decisional Ring-LWE in the random-oracle model : the serial number sn = a3 k + e has the form of a Ring-LWE sample, and modelling Hshort as a random oracle makes its deterministic error e = Hshort (k) behave as an independent short error unless the adversary queries the oracle at the secret k (an event bounded by key recovery). We flag this self-correlated-noise caveat explicitly in Remark 1. A.1

Notation

Table 4 fixes notation. Throughout, “short” means bounded Euclidean norm, and all hash calls are domain-separated instances of SHA-256 modeled as random oracles. Table 4. Summary of notation. Symbol

Description

Rq , n, q quotient ring Zq [X]/(X n + 1), n = 512, q = 12289 a1 , a2 , a3 , a4 nothing-up-my-sleeve public parameters in Rq (k, s, e), C = a1 k + a2 s + a4 e coin opening (short; e = Hshort (k)) and rank-one RingSIS coin commitment sn = a3 k + e, sn∗ serial number (key image) and its SHA-256 nullifier digest C, r, π ring of commitments, ring size, secret signer index µ context: recipient ∥ relayer ∥ fee ∥ appID (80 bytes) C, w sparse ternary challenge space, Hamming weight 48 ci , χi = H2C(ci ) 256-bit chain values and derived ternary challenges yk , ys , ye ; zk,i , zs,i , ze,i Gaussian masks (width ς = 2500); per-member responses β2 squared-norm acceptance bound, 4.2 × 109 σ = (c0 , {(zk,i , zs,i , ze,i )}i ) signature BC , BN commitment and nullifier box sets x̂ = NTT(x), ⊙ frequency-domain image and pointwise product

Obscura-PQ: Post-Quantum Privacy for Algorand

A.2

33

Hardness Assumptions and the Commitment

We restate the assumptions of Section 3 in the precise forms the reductions use. Throughout, the public parameters a1 , a2 , a3 , a4 are treated as uniform in Rq ; this is the nothing-up-my-sleeve heuristic, justified in the ROM by modeling Hring as a (programmable) random oracle, so a reduction may embed a challenge instance in the aj by reprogramming Hring . “Short” means squared Euclidean norm at most a stated bound. Assumption 1 (Ring-SIS, binding; B1). For a vector a of uniform elements in Rq of length 3, and a norm bound B = O(β), no PPT algorithm outputs a nonzero short vector f such that ⟨a, f ⟩ = 0 except with negligible probability. In particular, the coin C = a1 k + a2 s + a4 e is binding: a second short opening (k ′ , s′ , e′ ) ̸= (k, s, e) yields the collision a1 (k − k ′ ) + a2 (s − s′ ) + a4 (e − e′ ) = 0, which is a Ring-SIS solution for a = (a1 , a2 , a4 ). Assumption 2 (Ring-LWE, commitment and serial-number hiding; B2). For uniform a and short x, y, the sample (a, ax + y) is computationally indistinguishable from uniform on Rq × Rq (decisional Ring-LWE [46]). Two consequences are used. (i) The
coin C = a1 k + a2 s + a4 e can be rewritten as −1 a2 (a−1 2 a1 )k + (a2 a4 )e + s whenever a2 is invertible. Since a1 , a4 are uniform, −1 a−1 2 a1 and a2 a4 are uniform, making the inner term a rank-2 Module-LWE sample with secret (k, e)T and error s. Thus, C is computationally indistinguishable from uniform and hides its opening. (ii) The serial number sn = a3 k + e has the form of a Ring-LWE sample, but with the deterministic error e = Hshort (k). Modelling Hshort as a random oracle with short outputs, for any adversary that does not query the oracle at k the value e is a uniform short element independent of k; then sn is distributed exactly as a genuine Ring-LWE sample and, jointly with C (which reuses the same e), the pair is distributed as in the independenterror variant. Under this modelling sn hides k, recovering k from sn is search Ring-LWE (equivalently bounded-distance decoding of a3 k + e = sn with short (k, e)), and the residual event that the adversary queries Hshort (k) is itself a key recovery, bounded by the same search hardness (Remark 1). Assumption 3 (Serial-number linking; decisional Ring-LWE in the ROM). For uniform a1 , a2 , a3 , a4 and independent short k, k ′ , s, e, e′ , the distributions

a1 k + a2 s + a4 e, a3 k + e and a1 k + a2 s + a4 e, a3 k ′ + e′ are computationally indistinguishable. Equivalently, given a commitment and a candidate serial number, no PPT algorithm decides whether they share the committed secret k, except with negligible advantage. For independent e, e′ this is a direct consequence of Assumption 2; the deployed scheme instead uses the deterministic e = Hshort (k), for which the statement holds in the random-oracle model, as discussed below and in Remark 1. The blinded serial number sn = a3 k + e carries a short error, so the linking statement 3 holds in the random-oracle model : modelling Hshort as a random

34

N. Azimi

oracle, the joint view (a1 k +a2 s+a4 e, a3 k +e) is, up to the negligible probability that the adversary queries Hshort (k), distributed exactly as in the independenterror variant, for which replacing sn by a uniform element (one decisional RingLWE hop) and reintroducing an independent a3 k ′ + e′ (a second hop) makes the two distributions identical. Because e = Hshort (k) is not an independent error, this is a random-oracle argument, not a black-box reduction to standard decisional Ring-LWE; without the ROM, Assumption 3 should be read as a self-correlated-noise Ring-LWE assumption in its own right (Remark 1), and the clean standard-model reduction is recovered only by the alternative that samples e independently and stores it in the coin. This is the lattice analogue of the key-image indistinguishability relied on in the commitment-and-serialnumber line [3, 30, 68]; Section 3 folds both uses of Ring-LWE into the single assumption B2. Recovering the short k from sn is the search Ring-LWE problem and is likewise covered by Assumption 2. A.3

Scheme Syntax and Correctness

Definition 1 (Lattice Linkable Ring Signature). Relative to public parameters pp = (a1 , a2 , a3 , a4 ) and a random oracle H, the scheme is the tuple of PPT algorithms (CoinKeyGen, SN, Sign, Verify, Link):
– (k, s, e), C ← CoinKeyGen(1λ ): sample short k, s from the centred binomial distribution, derive the short blinding e = Hshort (k), and output the coin C = a1 k + a2 s + a4 e; – sn ← SN(k): output the deterministic serial number sn = a3 k + e with e = Hshort (k);
– (σ, sn) ← Sign (k, s, e), C, π, µ : on input an opening (k, s, e) of Cπ ∈ C and a message µ, output a signature and the serial number, per Section 4.4; – {0, 1} ← Verify(C, µ, sn, σ): verify the norm bounds, recompute the challenge chain, and accept iff it closes, per Section 4.5; – Link: two verifying tuples are linked iff their serial-number digests sn∗ coincide. Theorem 1 (Correctness). For every ring C, index π, and message µ, an honestly generated signature is accepted by Verify except with negligible probability over the signer’s randomness, and honest signing terminates after an expected O(1) rejection restarts. Proof. At the true index, substituting the closure zk,π = yk + χπ k, zs,π = ys + χπ s, ze,π = ye + χπ e into (1) gives tpk π = a1 (yk + χπ k) + a2 (ys + χπ s) + a4 (ye + χπ e) − χπ Cπ = a1 yk + a2 ys + a4 ye , tsn π = a3 (yk + χπ k) + (ye + χπ e) − χπ (a3 k + e) = a3 yk + ye , which matches the prover’s commitment step; at every decoy index the verifier recomputes the same relation images from the same responses and challenges. Every chain value therefore coincides with the prover’s and the chain closes to c0 ,

Obscura-PQ: Post-Quantum Privacy for Algorand

35

provided every response passes the norm check. The true-index responses pass by construction (rejection sampling). The decoy responses are drawn from Dς and, in the implemented signer, are not conditioned on the bound; a single decoy coefficient vector violates ∥·∥2 ≤ β 2 only with probability negligible in n (see the termination estimate below), so a union bound over the 3(r − 1) ≤ 3rmax decoy responses leaves acceptance overwhelming. This is why the statement is “except with negligible probability” rather than perfect; a signer that also norm-checks its decoys would make correctness perfect. For termination: each coefficient of χπ k and χπ s is a signed sum of at most w terms of magnitude at most η, so ∥χπ k∥∞ ≤ wη = 96 ≪ ς and ∥z•,π ∥2 concentrates around the mask mean nς 2 = 3.2 × 109 . The acceptance bound β 2 = 4.2 × 109 exceeds this mean five standard deviations of ∥z∥2 √ by roughly 8 2 (whose standard deviation is ς 2n ≈ 2 × 10 ). The discrete Gaussian rejection sampling completes in expected M attempts, where M ≈ 3 is chosen based on the worst-case norm of the secret offset, yielding an expected O(1) restarts [44]. (The deployed implementation simplifies this by omitting the probability ratio; see Section 8.3 and Remark 1.) ⊔ ⊓
48 Lemma 1 (Challenge Space). |C| = 512 > 2256 , and in the ROM each 48 · 2 distinct chain input maps to an independent uniform 256-bit value ci ; hence a collision among any polynomial number Q of oracle queries, or the prediction of an unqueried chain value, occurs with probability at most O(Q2 2−256 ) and Q 2−256 respectively, both negligible. Proof. The count is direct: a challenge is determined by the
choice of w = 48 positions out of n = 512 and a sign per position, and log2 512 48 +48 > 256. Chain values are outputs of distinct random-oracle queries, since the 2-byte index and c sn c the packed relation images pack(tpk i )∥pack(ti ) separate the inputs; the collision and prediction bounds are then the standard birthday and guessing bounds. The seed ci carries at most 256 bits of entropy, so H2C(ci ) realizes at most 2256 of the |C| challenges, which is the relevant unpredictability parameter. ⊓ ⊔ A.4

Security Experiments

We fix the experiments the theorems refer to. In each, the challenger generates pp, answers random-oracle queries by lazy sampling, and maintains a list L of honest coins created through the oracle Ocoin (runs CoinKeyGen, stores (k, s, e), returns C), a corruption oracle Ocorrupt (j) (returns the opening of the j-th honest coin and marks it corrupted), and a signing oracle Osign (j, C, µ) (aborts unless Cj ∈ C; otherwise returns Sign with the j-th opening at its index in C). Definition 2 (Unforgeability / Theft Resistance). A wins Expuf if, given pp and the three oracles, it outputs a verifying tuple (C∗ , µ∗ , sn∗ , σ ∗ ) such that (i) every Ci ∈ C∗ is an honest, uncorrupted coin in L, and (ii) sn∗ was never returned by Osign . The scheme is unforgeable if Pr[A wins] is negligible for every PPT A.

36

N. Azimi

Definition 3 (Anonymity / Signer Ambiguity). For b ∈ {0, 1}, Expanon b runs A with pp and the three oracles; A outputs (C, µ, i0 , i1 ) where Ci0 , Ci1 ∈ C are honest and never queried to Ocorrupt or Osign . The challenger returns (σ, sn) ← Sign with the opening of Cib , and A outputs a guess b′ . The advantage is Pr[b′ = b] − 21 . The non-corruption/non-signing restriction on i0 , i1 is intrinsic to linkable ring signatures: two spends of one coin publish the identical serial number and are, by design, linkable. A.5

Unforgeability

Theorem 2 (Unforgeability / Theft Resistance). In the ROM, under Assumption 1 (with Hring programmable) and Assumption 2, no PPT adversary wins Expuf except with negligible probability. Proof. We construct a reduction B that uses a successful adversary A to solve the Ring-SIS problem (Assumption 1). Let QH be the maximum number of random oracle queries made by A. The reduction B is given a Ring-SIS challenge a = (a1 , a2 , a4 ) and programs Hring such that the corresponding public parameters match a, while generating a3 honestly. B handles Ocoin by generating honest coin openings (ki , si , ei ) and storing them, answering Ocorrupt and Osign using these known openings. Suppose A outputs a successful forgery (C∗ , µ∗ , sn∗ , σ ∗ ) with probability ε. The signature σ ∗ contains responses and a challenge chain that closes. By Lemma 1, except with probability at most QH 2−256 , the chain values were obtained via queries to H. By the General Forking Lemma [14, 62], B can rewind A to the oracle query corresponding to the target index π (the index where the response relations were first queried), feed it a different random oracle response, and obtain a second accepting transcript with probability ε′ ≥ (ε − QH 2−256 )2 /QH . sn The two accepting transcripts share the relation images (tpk π , tπ ) but have ′ distinct challenges χπ ̸= χπ . Subtracting the two instances of (1) at π yields: a1 z̄k + a2 z̄s + a4 z̄e = χ̄ Cπ ,

a3 z̄k + z̄e = χ̄ sn∗ ,

′ ′ ′ where z̄k = zk,π − zk,π , z̄s = zs,π − zs,π , z̄e = ze,π − ze,π , and χ̄ = χπ − χ′π . ′ Since χπ , χπ ∈ C are distinct, χ̄ ̸= 0. Because both transcripts satisfy the norm bounds, ∥z̄k ∥, ∥z̄s ∥, ∥z̄e ∥ ≤ 2β. This gives a relaxed opening of Cπ , which is the standard extracted witness format for lattice-based sigma protocols over rings where short challenge differences may lack inverses [29, 44, 68]. By the rules of Expuf , Cπ is an uncorrupted honest coin generated by B, so B knows its exact opening (kπ , sπ , eπ ) where Cπ = a1 kπ + a2 sπ + a4 eπ and its true serial number snπ = a3 kπ + eπ . Subtracting the known honest relation from the extracted one gives, writing δk = z̄k − χ̄kπ , δs = z̄s − χ̄sπ , δe = z̄e − χ̄eπ :

a1 δk + a2 δs + a4 δe = 0, We now consider three cases:

a3 δk + δe = χ̄(sn∗ − snπ ).

Obscura-PQ: Post-Quantum Privacy for Algorand

37

1. (δk , δs , δe ) ̸= (0, 0, 0). The first equation directly yields a short, nonzero solution to the Ring-SIS instance for (a1 , a2 , a4 ), breaking Assumption 1 [2, 45]. 2. (δk , δs , δe ) = (0, 0, 0) and sn∗ ̸= snπ . Then the second equation implies χ̄(sn∗ − snπ ) = 0. In the Fiat–Shamir transform, the serial number sn∗ is committed to before the challenge χπ is generated. For any fixed ∆sn = sn∗ − snπ ̸= 0, ∆sn is non-zero modulo at least one prime ideal p of Rq . Because the challenge space C is sufficiently large and well-distributed, the probability over the independent choices of χπ , χ′π ∈ C that χπ ≡ χ′π (mod p) is strictly bounded away from 1 (and is small for our parameters). Thus, conditioned on a successful fork, χ̄∆sn ̸= 0 with non-negligible probability, which yields a contradiction. Hence, this case does not prevent the reduction from succeeding. 3. (δk , δs , δe ) = (0, 0, 0) and sn∗ = snπ . This means the adversary successfully computed the exact scaled responses z̄k = χ̄kπ , z̄s = χ̄sπ , z̄e = χ̄eπ for a coin it never corrupted. Under Assumption 2, the commitment Cπ computationally hides (kπ , sπ , eπ ) [13, 46], so the adversary’s probability of correctly guessing this exact relation is negligible. Therefore, if ε is non-negligible, B breaks Assumption 1 with non-negligible probability ε′ , contradicting the hardness of Ring-SIS [2]. The on-chain ring-existence check with digest matching (Section 6) enforces condition (i) operationally, confining C∗ to genuine deposits and excluding adversarially fabricated commitments with adversary-known openings. ⊔ ⊓ A.6

Signer Ambiguity and Unlinkability

Theorem 3 (Signer Ambiguity). In the ROM, under Assumption 2 (commitment hiding), Assumption 3 (serial-number linking), and the zero-knowledge property of the rejection-sampled sigma protocol, every PPT adversary has negligible advantage in Expanon . Consequently no PPT adversary identifies the signer within a ring of size r with t corrupted members with probability exceeding 1/(r − t) by more than a negligible amount. Proof. We prove this via a sequence of indistinguishable games, starting with the real anonymity experiment for a fixed bit b ∈ {0, 1}. Let Advi denote the adversary’s advantage in Gamei . Game0 : This is the real Expanon experiment. The challenger generates the b signature using the exact opening (kib , sib , eib ) of Cib . Game1 : We modify the challenger to construct the signature σ using the zeroknowledge simulator. Instead of executing the real Sign algorithm, the challenger randomly samples all responses zk,j , zs,j , ze,j ← Dς for all j ∈ {0, . . . , r − 1}, sn computes the relation images tpk j and tj directly, and programs the random oracle H to enforce chain closure. By the honest-verifier zero-knowledge (HVZK) property of the rejection-sampled sigma protocol [43,44], the accepted responses in Game0 are within negligible statistical distance ∆ from the unconditioned

38

N. Azimi

mask distribution used in Game1 . Thus, |Adv0 − Adv1 | ≤ ∆, which is negligible. At this point, the signature σ is generated without knowledge of the secret index ib or its witness. The adversary’s view depends on b only through the published serial number sn = a3 kib + eib . Game2 : We replace the serial number sn = a3 kib + eib with sn′ = a3 k ′ + ′ e , where k ′ , e′ are freshly sampled independent short elements. Distinguishing Game1 from Game2 is exactly the task of deciding whether a serial number shares a secret with a specific commitment. We argue in the random-oracle model, modelling Hshort as a random oracle with short outputs. Let Qk be the event that A queries Hshort at the challenge secret kib . Conditioned on ¬Qk , the deterministic error eib = Hshort (kib ) is, in A’s view, a uniform short element independent of kib and shared between Cib and sn; the view is then exactly that of the independent-error variant, in which (by Assumption 2 [13, 46]) Cib hides its opening and sn = a3 kib + eib is a genuine Ring-LWE sample, so (Cib , a3 kib + eib ) is indistinguishable from (Cib , a3 k ′ + e′ ) by two decisional Ring-LWE hops (the linking statement 3). Hence |Adv1 −Adv2 | ≤ 2εlwe +Pr[Qk ], where Pr[Qk ] ≤ QH δ and δ bounds the per-query probability of recovering the committed kib (search Ring-LWE, equivalently Assumption 1 on the coin); all terms are negligible. In Game2 , the entire view provided to the adversary, including the signature σ and the serial number sn′ , is completely independent of the bit b. Therefore, the adversary’s advantage in Game2 is exactly 0. Summing the bounds, the adversary’s total advantage in Expanon is bounded by ∆ + εlink , which is negligible. Consequently, no PPT adversary can identify the signer among the r − t honest, uncorrupted members with probability exceeding 1/(r − t) by more than a negligible amount, satisfying the standard anonymity game for linkable ring signatures [3, 40]. ⊔ ⊓ Corollary 1 (Deposit–Withdrawal Unlinkability). Under the same assumptions, no PPT observer links a specific deposit C to a withdrawal beyond the 1/(r − t) ring ambiguity: the withdrawal publishes only (C, µ, sn, σ), the transcript is simulatable from these, and deciding whether C and sn = a3 k + e share the committed k reduces to decisional Ring-LWE in the random-oracle model (Assumption 2; see Remark 1 for the self-correlated-noise caveat of the deterministic e = Hshort (k)); recovery of k from sn is the search Ring-LWE problem. A.7

Linkability, Non-Frameability, and Protocol-Level Security

Theorem 4 (Linkability). Except with negligible probability, every verifying tuple carries sn = a3 k + e for the unique short (k, e) opening some ring member, and any two verifying spends of the same coin produce identical nullifiers sn∗ . In particular, an adversary holding one coin cannot output two verifying withdrawals with distinct nullifiers. Proof. By the extraction established in Theorem 2 (following the linkability framework of [3,40]), any verifying tuple implies the existence of an extractor that recovers a short (relaxed) witness (z̄k , z̄s , z̄e ) satisfying a1 z̄k + a2 z̄s + a4 z̄e = χ̄Cπ alongside the serial-number relation a3 z̄k + z̄e = χ̄ sn for the published sn.

Obscura-PQ: Post-Quantum Privacy for Algorand

39

By the binding property of the commitment (Assumption 1), the short opening (k, s, e) of Cπ is unique. As shown in the proof of Theorem 2, this implies z̄k = χ̄k and z̄e = χ̄e except with negligible probability. Substituting these into the serial-number relation yields χ̄(a3 k + e − sn) = 0. Because sn is committed to before the random oracle challenge is generated, the probability that the challenge difference χ̄ annihilates a non-zero ∆sn = a3 k + e − sn is strictly bounded away from 1. Thus, conditioned on a successful extraction, any verifying transcript must have sn = a3 k + e. Because sn = a3 k + e is a deterministic function of that unique opening, the serial number attached to a given coin is permanently fixed. Since the nullifier sn∗ is a deterministic collision-resistant digest of NTT(sn), it is also fixed. Therefore, any two verifying spends of the same coin must produce the identical nullifier sn∗ , making double-spends trivially detectable. ⊔ ⊓ Lemma 2 (Non-Frameability). No PPT adversary can produce a verifying withdrawal carrying the serial number of an honest user’s unspent coin, except with negligible probability. Proof. A framing attempt requires the adversary to broadcast a verifying withdrawal carrying the serial number sn = a3 k + e belonging to an honest, unspent coin, aligning with the non-frameability (non-slanderability) definitions formalized in [36]. By Theorems 2 and 4, the existence of such a verifying tuple implies that the adversary implicitly knows a short (relaxed) opening of the honest coin. Because the coin is uncorrupted and its secret (k, s, e) was never revealed, constructing this signature constitutes a successful forgery under the strict rules of Expuf . By Theorem 2, this allows a reduction to break Assumption 1 (Ring-SIS) or Assumption 2 (Ring-LWE). Therefore, a PPT adversary has negligible probability of pre-spending an honest coin or maliciously publishing its nullifier to cause a future honest withdrawal to be rejected as a double-spend. ⊓ ⊔ Lemma 3 (Replay Resistance and Context Binding). A verifying withdrawal cannot be replayed, and none of recipient, relayer, fee, or application identifier can be altered after signing, except with negligible probability. Proof. The settlement context µ (comprising the recipient, relayer, fee, and application ID) prefixes the input to every Fiat–Shamir chain-update hash H [15, 31]. Altering even a single bit of any component in µ after the signature has been generated cascades through the random oracle, completely randomizing the output challenges. By Lemma 1, the mutated challenge chain will fail to close back to c0 except with negligible probability ≈ 2−256 . Consequently, an adversary attempting to redirect the funds or alter the fee must forge an entirely new signature, which is computationally infeasible under Theorem 2. Operationally, the smart contract tightly couples verification and payout by settling only to the specific µ values recorded in the chain-bound state box. This closes the gap between signature verification and payout construction, ensuring the AVM strictly enforces the cryptographically authorized intent. Finally, replay of a successfully executed withdrawal is prevented unconditionally by the flat

40

N. Azimi

O(1) state check against the nullifier box, and the inclusion of the appID securely isolates the proof from cross-deployment replay attacks. ⊓ ⊔ Corollary 2 (Double-Spend Resistance of the Protocol). Each deposit is withdrawable at most once: the contract asserts the absence of "n"∥sn∗ and creates it atomically with the payout, and by Theorem 4 every spend of a given coin presents the identical sn∗ . AVM group atomicity guarantees that the nullifier is recorded iff the chain closed and funds move iff the nullifier is recorded. Distinct coins map to distinct nullifiers except with negligible probability: if two coins had the same serial number, then a3 k1 + e1 = a3 k2 + e2 , yielding a3 (k1 − k2 ) + (e1 − e2 ) = 0, which is a Ring-SIS collision for (a3 , 1). Furthermore, NTT is a bijection, so distinct serial numbers give distinct packed images, and a nullifier collision would require a SHA-256 collision, negligible in the random-oracle model; hence one coin’s withdrawal cannot pre-register or block another’s. Remark 1 (Abstraction Gaps and Scope of the Proofs). We state explicitly where the arguments are conditional, complementing Section 8.3. – Relaxed extraction and soundness gap. The extractor of Theorem 2 recovers a relaxed opening with relaxation factor χ̄, not an exact opening, and we do not rely on χ̄ being invertible; in the fully splitting ring (X n + 1 factors into n linear terms modulo q = 12289, since 2n | q − 1) short challenge differences are not guaranteed invertible, so techniques that assume invertibility do not apply. This is a direct consequence of the ring choice: MatRiCT [30] and DualRing-LB [68] obtain exact (relaxed) openings and full balance/soundness against rings containing adversarial members precisely because they work over partially splitting rings in which short challenge differences are invertible [47], whereas we deliberately adopt the fully splitting Falcon-512 ring so that the on-chain verifier can evaluate every relation through a native negacyclic NTT (Section 6). The reduction we give avoids inversion by subtracting the honest opening, which is sound for theft resistance and non-frameability but does not upgrade to an exact-opening or knowledge-soundness statement. For the same reason we state Expuf (Definition 2) over an all-honest ring: extending theft resistance to a balance-style notion over rings that also contain adversarially generated decoys (as in the MatRiCT model [30]) is standard in principle but requires the invertiblechallenge-difference machinery, which the fully splitting ring does not provide; we leave a dedicated relaxed-soundness analysis for this ring as future work. – Deterministic serial-number error (self-correlated noise). The blinding is e = Hshort (k), a deterministic function of k, so sn = a3 k + e is not a standard Ring-LWE sample with an independent error but a self-correlatednoise instance. The anonymity and unlinkability results (Theorem 3, Corollary 1) are therefore stated in the random-oracle model: with Hshort a random oracle, e acts as an independent short error unless the adversary queries the oracle at the secret k, and that event reduces to key recovery (search RingLWE, equivalently Assumption 1 on the coin). We do not claim a black-box

Obscura-PQ: Post-Quantum Privacy for Algorand

41

reduction to standard decisional Ring-LWE; recovering k from sn is search Ring-LWE (bounded-distance decoding of a3 k + e = sn with short (k, e)). A clean standard-model reduction is recovered by the alternative design that samples e independently at coin generation and stores it in the coin secret (at the cost of a larger persisted opening); we adopt the hash-derived e because it allows deterministic recovery from a minimal persisted seed and inherits determinism from commitment binding rather than from the hash. – Rejection sampling with a hash-derived secret. Although k and e = Hshort (k) are not independent, the Fiat–Shamir-with-aborts zero-knowledge argument is unaffected: the honest-verifier simulator samples every response zk,i , zs,i , ze,i from Dς and never evaluates Hshort , so the accepted-response distribution is independent of the secret regardless of correlations among (k, s, e); the correlation enters only the acceptance probability (termination), where e, short by the random-oracle modelling of Hshort , is covered by the same norm and M -bound analysis as k and s. Consequently the joint “double-constrained” test (zk,π − χπ k ∗ and ze,π − χπ Hshort (k ∗ ) both short) conveys no advantage against the idealized full-ratio sampler; against the norm-bound-only sampler actually implemented it inherits only the residual leakage already noted under the sampler simplification, negligible for the single spend a coin admits at ς = 2500. – Sampler simplification. The implemented sampler applies a norm-boundonly acceptance test on rounded-Gaussian masks, and does not condition the decoy responses on the bound, rather than the full Fiat–Shamir-with-aborts acceptance ratio (M ≈ 3) assumed by the zero-knowledge step of Theorem 3. The zero-knowledge (hence anonymity) guarantee is therefore exact only for the idealized full-ratio sampler; the correctness statement (Theorem 1) is correspondingly “with overwhelming probability” rather than perfect. – Concrete parameters. The parameter set (η, ς, β, w) has not been calibrated against lattice-reduction estimates [4], so no numeric bit-security level is claimed; only the ring (n, q) is inherited from Falcon-512. – Model. All reductions are classical-ROM; the deployed post-quantum setting warrants a QROM analysis [20, 27] of the composed scheme, which we leave open. The structural results are the most robust: uniqueness of the serial number (Theorem 4), double-spend resistance (Corollary 2), and context binding (Lemma 3) hold as stated, relying only on Assumption 1 and the random oracle. The quantitative unforgeability and anonymity guarantees are conditional on the items above.

References 1. Abe, M., Ohkubo, M., Suzuki, K.: 1-out-of-n signatures from a variety of keys. IEICE transactions on fundamentals of electronics, communications and computer sciences 87(1), 131–140 (2004)

42

N. Azimi

2. Ajtai, M.: Generating hard instances of lattice problems. In: Proceedings of the twenty-eighth annual ACM symposium on theory of computing. pp. 99–108. ACM (1996) 3. Alberto Torres, W.A., Steinfeld, R., Sakzad, A., Liu, J.K., Kuchta, V., Bhattacharjee, N., Au, M.H., Cheng, J.: Post-quantum one-time linkable ring signature and application to ring confidential transactions in blockchain (lattice ringct v1. 0). In: Australasian Conference on Information Security and Privacy. pp. 558–576. Springer (2018) 4. Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. Journal of Mathematical Cryptology 9(3), 169–203 (2015) 5. Algorand Foundation: Algorand protocol parameters. https://dev.algorand.co/ concepts/protocol/protocol-parameters/, last accessed: 2026-08-15 6. Algorand Foundation: Algorand virtual machine (avm) specification, https:// developer.algorand.org/docs/get-details/dapps/avm/, last accessed: 2026-08-08 7. Algorand Foundation: Box storage, https://dev.algorand.co/concepts/ smart-contracts/storage/box/, last accessed: 2026-08-23 8. Algorand Foundation: Pyteal: Algorand smart contracts in python. https://github. com/algorand/pyteal, last accessed: 2026-05-03 9. Algorand Foundation: Smart contract costs & constraints, https://dev.algorand. co/concepts/smart-contracts/costs-constraints/, last accessed: 2026-08-08 10. Algorand Foundation: Transaction fees, https://dev.algorand.co/concepts/ transactions/fees/#pooled-transaction-fees, last accessed: 2026-08-09 11. Androulaki, E., Karame, G.O., Roeschlin, M., Scherer, T., Capkun, S.: Evaluating user privacy in bitcoin. In: International conference on financial cryptography and data security. pp. 34–51. Springer (2013) 12. Azimi, N.: Obscura: Privacy-preserving protocol for the algorand blockchain using lsag ring signatures. arXiv preprint arXiv:2605.02077 (2026) 13. Baum, C., Damgård, I., Lyubashevsky, V., Oechsner, S., Peikert, C.: More efficient commitments from structured lattice assumptions. In: International conference on security and cryptography for networks. pp. 368–385. Springer (2018) 14. Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: Proceedings of the 13th ACM conference on computer and communications security. pp. 390–399. ACM (2006) 15. Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: Proceedings of the 1st ACM conference on computer and communications security. pp. 62–73. ACM (1993) 16. Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Report 2018/046 (2018) 17. Ben-Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza, M.: Zerocash: Decentralized anonymous payments from bitcoin. In: 2014 IEEE symposium on security and privacy (SP). pp. 459–474. IEEE (2014) 18. Béres, F., Seres, I.A., Benczúr, A.A., Quintyne-Collins, M.: Blockchain is watching you: Profiling and deanonymizing ethereum users. In: 2021 IEEE international conference on decentralized applications and infrastructures (DAPPS). pp. 69–78. IEEE (2021) 19. Beullens, W., Katsumata, S., Pintore, F.: Calamari and falafl: Logarithmic (linkable) ring signatures from isogenies and lattices. In: International conference on the theory and application of cryptology and information security. pp. 464–492. Springer (2020)

Obscura-PQ: Post-Quantum Privacy for Algorand

43

20. Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: International conference on the theory and application of cryptology and information security. pp. 41–69. Springer (2011) 21. Bonneau, J., Narayanan, A., Miller, A., Clark, J., Kroll, J.A., Felten, E.W.: Mixcoin: Anonymity for bitcoin with accountable mixes. In: International conference on financial cryptography and data security. pp. 486–504. Springer (2014) 22. Bünz, B., Agrawal, S., Zamani, M., Boneh, D.: Zether: Towards privacy in a smart contract world. In: International conference on financial cryptography and data security. pp. 423–443. Springer (2020) 23. Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: Short proofs for confidential transactions and more. In: 2018 IEEE symposium on security and privacy (SP). pp. 315–334. IEEE (2018) 24. Chaum, D., van Heyst, E.: Group signatures. In: Workshop on the theory and application of cryptographic techniques. pp. 257–265. Springer (1991) 25. Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: Annual international cryptology conference. pp. 174–187. Springer (1994) 26. Dingledine, R., Mathewson, N., Syverson, P.F., et al.: Tor: The second-generation onion router. In: USENIX security symposium. vol. 4, pp. 303–320 (2004) 27. Don, J., Fehr, S., Majenz, C., Schaffner, C.: Security of the fiat–shamir transformation in the quantum random-oracle model. In: Annual international cryptology conference. pp. 356–383. Springer (2019) 28. Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehlé, D.: Crystals-dilithium: A lattice-based digital signature scheme. IACR Transactions on Cryptographic Hardware and Embedded Systems 2018(1), 238–268 (2018) 29. Esgin, M.F., Steinfeld, R., Liu, J.K., Liu, D.: Lattice-based zero-knowledge proofs: New techniques for shorter and faster constructions and applications. In: Annual international cryptology conference. pp. 115–146. Springer (2019) 30. Esgin, M.F., Zhao, R.K., Steinfeld, R., Liu, J.K., Liu, D.: Matrict: efficient, scalable and post-quantum blockchain confidential transactions protocol. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. pp. 567–584 (2019) 31. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Conference on the theory and application of cryptographic techniques. pp. 186–194. Springer (1986) 32. Fisher, R.A., Yates, F.: Statistical tables for biological, agricultural and medical research. Oliver and Boyd (1953) 33. Fouque, P.A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Prest, T., Ricosset, T., Seiler, G., Whyte, W., Zhang, Z., et al.: Falcon: Fast-fourier latticebased compact signatures over ntru. Submission to the NIST’s post-quantum cryptography standardization process 36(5), 1–75 (2018) 34. Garman, C., Green, M., Miers, I.: Accountable privacy for decentralized anonymous payments. In: International conference on financial cryptography and data security. pp. 81–98. Springer (2016) 35. Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: Scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th symposium on operating systems principles. pp. 51–68. ACM (2017) 36. Goodell, B., Noether, S., RandomRun: Concise linkable ring signatures and forgery against adversarial keys. Cryptology ePrint Archive, Report 2019/654 (2019)

44

N. Azimi

37. Groth, J.: On the size of pairing-based non-interactive arguments. In: Annual international conference on the theory and applications of cryptographic techniques. pp. 305–326. Springer (2016) 38. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the twenty-eighth annual ACM symposium on theory of computing. pp. 212–219. ACM (1996) 39. Kumar, A., Fischer, C., Tople, S., Saxena, P.: A traceability analysis of monero’s blockchain. In: European symposium on research in computer security. pp. 153– 173. Springer (2017) 40. Liu, J.K., Wei, V.K., Wong, D.S.: Linkable spontaneous anonymous group signature for ad hoc groups. In: Australasian conference on information security and privacy. pp. 325–335. Springer (2004) 41. Longa, P., Naehrig, M.: Speeding up the number theoretic transform for faster ideal lattice-based cryptography. In: International Conference on Cryptology and Network Security. pp. 124–139. Springer (2016) 42. Lu, X., Au, M.H., Zhang, Z.: Raptor: A practical lattice-based (linkable) ring signature. In: International conference on applied cryptography and network security. pp. 110–130. Springer (2019) 43. Lyubashevsky, V.: Fiat-shamir with aborts: Applications to lattice and factoringbased signatures. In: International conference on the theory and application of cryptology and information security. pp. 598–616. Springer (2009) 44. Lyubashevsky, V.: Lattice signatures without trapdoors. In: Annual international conference on the theory and applications of cryptographic techniques. pp. 738– 755. Springer (2012) 45. Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: International colloquium on automata, languages, and programming. pp. 144–155. Springer (2006) 46. Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Annual international conference on the theory and applications of cryptographic techniques. pp. 1–23. Springer (2010) 47. Lyubashevsky, V., Seiler, G.: Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 204–224. Springer (2018) 48. Maxwell, G., Poelstra, A.: Borromean ring signatures. Tech. rep., Blockstream (6 2015), https://github.com/Blockstream/borromean_paper, accessed: 2026-08-23 49. MDN Web Docs: Crypto.getrandomvalues() - web apis, https://developer.mozilla. org/docs/Web/API/Crypto/getRandomValues, last accessed: 2026-08-15 50. Meiklejohn, S., Mercer, R.: Möbius: Trustless tumbling for transaction privacy. Proceedings on Privacy Enhancing Technologies 2018(2), 105–121 (2018) 51. Meiklejohn, S., Pomarole, M., Jordan, G., Levchenko, K., McCoy, D., Voelker, G.M., Savage, S.: A fistful of bitcoins: characterizing payments among men with no names. In: Proceedings of the 2013 internet measurement conference. pp. 127– 140. ACM (2013) 52. Mendonca, A., Shi, H., Huynh, T., Pryvalov, I., Herzberg, A.: Efficient merkle-tree consistent accumulator. In: 2026 56th Annual IEEE International Conference on Dependable Systems and Networks (DSN). pp. 366–378. IEEE (2026) 53. Merkle, R.C.: A digital signature based on a conventional encryption function. In: Conference on the theory and application of cryptographic techniques. pp. 369–378. Springer (1987)

Obscura-PQ: Post-Quantum Privacy for Algorand

45

54. Miers, I., Garman, C., Green, M., Rubin, A.D.: Zerocoin: Anonymous distributed e-cash from bitcoin. In: 2013 IEEE symposium on security and privacy (SP). pp. 397–411. IEEE (2013) 55. Möser, M., Soska, K., Heilman, E., Lee, K., Heffan, H., Srivastava, S., Hogan, K., Hennessey, J., Miller, A., Narayanan, A., Christin, N.: An empirical analysis of traceability in the monero blockchain. Proceedings on Privacy Enhancing Technologies 2018(3), 143–163 (2018) 56. Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system. https://bitcoin.org/ bitcoin.pdf (2008) 57. National Institute of Standards and Technology: Secure hash standard (shs). FIPS PUB 180-4 (2015) 58. Noether, S., Mackenzie, A., et al.: Ring confidential transactions. Ledger 1, 1–18 (2016) 59. Peikert, C., Rosen, A.: Lattices that admit logarithmic worst-case to average-case connection factors. In: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. pp. 478–487 (2007) 60. Pera Wallet: Pera wallet connect: Javascript sdk for web dapp integration. https: //github.com/perawallet/connect, last accessed: 2026-08-15 61. Pertsev, A., Semenov, R., Storm, R.: Tornado cash privacy solution version 1.4. Tornado cash privacy solution version 1(6) (2019) 62. Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. Journal of cryptology 13(3), 361–396 (2000) 63. Rivest, R.L., Shamir, A., Tauman, Y.: How to leak a secret. In: International conference on the theory and application of cryptology and information security. pp. 552–565. Springer (2001) 64. Ron, D., Shamir, A.: Quantitative analysis of the full bitcoin transaction graph. In: International conference on financial cryptography and data security. pp. 6–24. Springer (2013) 65. van Saberhagen, N.: Cryptonote v 2.0. https://www.getmonero.org/ru/resources/ research-lab/pubs/whitepaper_annotated.pdf (2013) 66. Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th annual symposium on foundations of computer science. pp. 124–134. Ieee (1994) 67. Wood, G.: Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper 151, 1–32 (2014) 68. Yuen, T.H., Esgin, M.F., Liu, J.K., Au, M.H., Ding, Z.: Dualring: Generic construction of ring signatures with efficient instantiations. In: Annual international cryptology conference. pp. 251–281. Springer (2021)

Related documents

• SilentLedger: Privacy-Preserving Auditing for Blockchains with Complete Non-Interactivity#1062793
• Quantum Inversion of Units in Group Rings: Block Dimension, Not Commutativity, Governs Hardness#997600
• Deanonymizable Scoped Linkable Ring Signatures#178805
• Blockchain from the Perspective of Privacy and Anonymisation: A Systematic Literature Review#400465
• No Country for Old Privacy: The Evolving Challenges of Anonymity in Bitcoin#329021