arXiv:2607.13235v1 [cs.CR] 14 Jul 2026
Proof in a Bottle: Long-Lived Verifiable Secret Sharing via Pre-Quantum Commitment and Immutable Ledger Binding Markus Jakobsson
Keir Finlow-Bates
Artema LABS New York, USA [email protected]
Artema LABS Eura, Finland [email protected]
Abstract—Traditional secret sharing techniques such as Verifiable Secret sharing (VSS) are vulnerable to quantum attacks by a Cryptographically Relevant Quantum Computer (CRQC) running Shor’s algorithm. We observe that the binding a VSS needs is required only at the moment of dealing, and this binding can be made before any CRQC exists. We propose Proof in a Bottle (PiB), which decouples verifiability from long-term binding: standard Pedersen commitments provide zero-knowledge, publicly checkable consistency during a pre-quantum window, while a salted, indexbound hash of the share set, anchored to an immutable public ledger, preserves the binding established in that window into the post-quantum era. The guarantee is explicitly a commitnow, reveal-later one: it protects today’s honest dealings against tomorrow’s quantum adversary.
I. I NTRODUCTION Verifiable Secret Sharing (VSS) [1], [2] lets a dealer distribute shares of a secret so that (1) no fewer than t shareholders learn anything about the secret (secrecy), (2) any t or more reconstruct it (correctness), and (3) shareholders can check that the shares they hold are mutually consistent with a single degree-(t−1) polynomial (commitment, or binding). Pedersen VSS realizes this by committing to each polynomial coefficient as Cj = g aj hrj and exploiting homomorphism Q j so that each share (i, yi ) is checked against j Cji without revealing the coefficients. We introduce Proof in a Bottle (PiB,) which decouples zero-knowledge verifiability (Pedersen, pre-quantum) from long-lived binding (a salted, index-bound hash anchored to an immutable ledger), formalizing the resulting commit-now, reveal-later guarantee. A. The quantum threat The security of Pedersen commitments has two aspects: Hiding is perfect (information-theoretic): a commitment is a uniformly distributed group element, and for every candidate secret there is exactly one randomizer consistent with it, so the commitment reveals nothing, even to an unbounded adversary. Binding, by contrast, is computational and rests on DLP. A CRQC running Shor’s algorithm [3] recovers the trapdoor x = logg h. This breaks binding only. Concretely, the
Q j verification target Pi = j Cji is a fixed group element with logg Pi = yi + xRi ; knowing x, an adversary can take any ′ ′ value yi′ and solve Ri′ = ( logg Pi −yi′ )/x so that g yi hRi = Pi . ′ ′ The forged (yi , Ri ) passes the individual Pedersen check, and the forged values need not lie on any single degree(t−1) polynomial. Different qualified subsets then reconstruct different secrets: the split-brain failure in which different qualified subsets of shareholders reconstruct different secrets from a single, ostensibly valid dealing. What Shor does not yield is recovery of the true secret: from the commitment alone the adversary learns only the single linear relation yi +xRi , which every candidate secret satisfies. The failure is thus confined to binding (the commitments become malleable). We say the commitments become malleable when an adversary who has recovered the scheme’s trapdoor can open a fixed public commitment to values of its choosing; this is precisely a loss of the binding property (equivalently, the ability to equivocate), and it leaves hiding untouched. This distinction matters, because informal descriptions that speak of the adversary “recovering the secret and randomizers” overstate the damage: the secret is never exposed, only the guarantee that a unique one was committed. B. The temporal insight The binding a VSS requires is a property of the act of dealing: it must be impossible, once shares are committed, to later present a different consistent-looking sharing. Crucially, commitments can be timestamped to moments at which DLP is still hard. During such a pre-quantum window, Pedersen binding functions normally and sharing is publicly, zeroknowledge verifiable. If, at that moment, the entire share set is frozen against an immutable record, then a later CRQC cannot equivocate: the ledger already fixes which shares exist, and the equivocation freedom Shor grants is useless as the target is sealed. This is the mirror image of “harvest-now, decrypt-later”; we call it commit-now, reveal-later. It squarely addresses the realistic threat that commitments made today, under classical assumptions, will be attacked by a CRQC that arrives years later.
C. Contributions II. R ELATED W ORK VSS and commitments. Feldman’s VSS [1] is not malleable, but is vulnerable to a quantum attacker recovering the committed secret. Pedersen’s VSS [2], in contrast, protects the committed secret against a quantum attacker, but at the cost of being malleable. Public verifiability. Publicly Verifiable Secret Sharing (PVSS) [4], [5] lets any observer verify a dealing against public data, but does not protect against quantum attacks. Long-lived integrity. Anchoring a digest to an append-only record to obtain long-term, tamper-evident timestamps is the classical notarization idea of Haber and Stornetta [6], of which a blockchain is a modern, decentralized instantiation. PiB is long-term notarization of a VSS dealing: one of its novel contributions is to recognize that notarizing a binding commitment during the pre-quantum window is sufficient to carry binding across the boundary, without any post-quantum algebraic assumption on the commitment itself. Post-quantum VSS. Lattice-based VSS (e.g., from the Short Integer Solution problem) [7] offers binding under assumptions believed hard for quantum adversaries, but with large parameters, intricate zero-knowledge machinery, and audit burden. PiB is not a competitor on the same axis: it trades a new hardness assumption for a timing assumption plus an immutable-ledger assumption, and is best suited to settings where dealings can be committed ahead of the quantum horizon. III. P RELIMINARIES , D EFINITIONS , AND T HREAT M ODEL A. Cryptographic primitives Z∗p
Let p be a large prime defining Fp , and let g, h ∈ be public generators with logg h unknown to all parties at setup. The Pedersen commitment to m with randomizer r is C(m; r) = g m hr (mod p); it is perfectly hiding and computationally binding under DLP. Let H : {0, 1}∗ → {0, 1}N be a cryptographic hash function; we model it as a random oracle where hiding is argued, and rely on its secondpreimage resistance for binding. Against a quantum adversary, Grover search gives preimage and second-preimage resistance ≈ 2N/2 , while the BHT algorithm [8] gives collision resistance only ≈ 2N/3 ; our binding argument requires second-preimage resistance, so we quote 2N/2 . B. Security definitions Definition III.1 ((t, n)-VSS). A dealer shares s ∈ Fp among n parties. The scheme is a (t, n)-VSS if: (Correctness) any t honestly held shares reconstruct s; (Secrecy) any coalition of < t parties, together with all public data, has negligible advantage in distinguishing s from uniform; (Binding) once the dealing is published, no (possibly cheating) party can cause two qualified subsets to reconstruct different values, except with negligible probability. Here negligible means negligible in the hash length N , taken over the dated adversary of Section III-C (classical before τQ , quantum with O(2N/2 )
hash queries after), and conditioned on the ledger-immutability assumption (Assumption III.2); it is not the standard quantification over all PPT adversaries, since our adversary is unbounded in DLP after τQ . Definition III.2 (Preserved binding across an epoch). Fix a quantum horizon time τQ at which a CRQC first exists. Binding is preserved across τQ if the Binding property of Definition III.1 holds against an adversary who is classical before τQ and quantum after, for any dealing whose public commitment is timestamped at some τ0 < τQ . C. Threat model Quantum capability, dated. The adversary is classical before τQ and gains full Shor/Grover capability after τQ . In particular it can solve DLP/ECDLP only after τQ . • Corruption. After τQ the adversary may control up to t− 1 shareholders and may collude with a dealer who wishes to equivocate on a dealing that was already published before τQ . • Ledger. The adversary cannot rewrite ledger history that has been finalized under post-quantum-secure consensus (see Assumption III.2). • Goal. To induce split-brain: qualified subsets reconstructing different secrets from a pre-τQ dealing. •
D. Computational Assumptions Assumption III.1 (Pre-quantum commitment window). The public commitment of any dealing PiB protects is timestamped at some τ0 < τQ , i.e. while DLP is hard, and the dealing is publicly consistency-verifiable during [τ0 , τQ ). Assumption III.2 (Ledger transition and finality). Public ledgers in current use authenticate blocks and history with classical signatures and Proof-of-Work/Proof-of-Stake consensus that a CRQC would undermine. We assume that before τQ these ledgers migrate to post-quantum-secure consensus and signatures, and that any anchor PiB relies on is buried under sufficient post-quantum-finalized history before τQ . Under this assumption the anchor’s inclusion and ordering become immutable against the post-τQ adversary. We are explicit that Assumptions III.1–III.2 are loadbearing: they replace a post-quantum algebraic hardness assumption on the commitment with a timing plus immutability assumption on deployment. IV. T HE P RE -Q UANTUM C OMMITMENT M ODEL PiB is designed for a dealer who wishes to stockpile verifiable dealings ahead of the quantum horizon. Concretely, before τQ the dealer generates a large batch of independent (t, n) sharings {f (m) }M m=1 (for prospective threshold keys, escrowed secrets, key-rotation reserves, or future wallet provisioning) and publishes only the corresponding commitments and anchors (Section V). No secret or share need be revealed at publication time. Individual sharings are then activated (distributed to shareholders and, when needed, reconstructed) at arbitrary later times, possibly well after τQ .
The value of batching is that a single pre-quantum event fixes the binding of the entire reserve. Because each anchor is timestamped at τ0 < τQ (Assumption III.1) and finalized under transitioning consensus (Assumption III.2), the binding of every sharing in the batch is sealed while DLP still holds, regardless of when it is later opened. This is precisely the commit-now, reveal-later posture: the scheme presumes that the honest work of dealing happens today and that the adversary’s advantage materializes later, and it removes any benefit from that later advantage with respect to binding. Two consequences deserve emphasis. First, the window is a hard requirement: a dealing whose anchor is first published after τQ enjoys no protection, because a quantum dealer can then anchor an already-inconsistent set (Section VI, Proposition VI.4). Second, the reserve’s secrecy does not depend on the window at all: Pedersen hiding is perfect and, as shown below, the anchoring is arranged to leak nothing, so stockpiled secrets remain confidential indefinitely, whether opened before or after τQ .
D. Verification (zero-knowledge) Party i checks, without learning s: 1) Inclusion. Recompute ℓi = H(i∥yi ∥si ) and verify it against the published leaf set, or against Root via πi . 2) Consistency. Verify ?
g yi hRi =
We describe a single (t, n) sharing; a batch repeats it independently per m.
j
Cji = g
P
j j aj i
j j rj i
P
h
.
j=0
Both checks are zero-knowledge in s. Under Assumption III.1, the consistency check is meaningful (DLP hard) at least once during [τ0 , τQ ); public verifiability means any observer, not only shareholders, may perform it and record success onledger if desired. E. Reconstruction Any S ⊆ P with |S| = t recovers X Y −xj s = f (0) = yi xi − x j i∈S
V. T HE P I B P ROTOCOL
t−1 Y
(mod p),
j∈S, j̸=i
using only shares whose inclusion and consistency checks passed. VI. S ECURITY A NALYSIS
A. Setup
A. Preserved binding
Let P = {1, . . . , n}. The dealer picks a random polynomial f (x) = at−1 xt−1 + · · · + a1 x + s over Fp , with a0 = s the secret.
Proposition VI.1 (Binding preservation). Under Assumptions III.1 and III.2, and assuming H is second-preimage resistant against quantum adversaries (≈ 2N/2 work), PiB satisfies preserved binding (Definition III.2): except with negligible probability, no post-τQ adversary can cause any qualified subset to reconstruct a value other than the secret s⋆ fixed at τ0 .
B. Share generation and double commitment 1) Shares. For each i ∈ P, compute yi = f (i). 2) Coefficient commitments. Pick random rj and publish Cj = g aj hrj (mod p) for j = 0, . . . , t −P1. t−1 3) Share randomizers. By linearity, yi = j=0 aj ij and Pt−1 j the matching randomizer is Ri = j=0 rj i , so that Q j g yi hRi = j Cji . 4) Salted, index-bound leaves. Draw an independent uniform salt si ∈ {0, 1}κ per share and form the leaf ℓi = H( i ∥ yi ∥ si ). Binding the index i prevents one shareholder from representing another’s value; the secret salt si makes the leaf hiding (Proposition VI.3). 5) Anchor. For small n, publish the leaf set {ℓi }ni=1 . For large n, publish a single Merkle root Root = H MerkleTree(ℓ1 , . . . , ℓn ) . 6) Publish (pre-τQ ). Post a ledger transaction containing C = {C0 , . . . , Ct−1 }, the anchor (leaf set or Root), and a timestamp τ0 . C. Distribution Privately send to each i: the share (i, yi ); the randomizer Ri ; the salt si ; and (Merkle case) the authentication path πi for ℓi .
Proof sketch. By Assumption III.1, at τ0 < τQ DLP is hard, so Pedersen binding holds: the published C computationally determine unique coefficients {aj }, hence a unique polynomial f and shares yi⋆ = f (i), and the leaves ℓ⋆i = H(i∥yi⋆ ∥si ) that any observer can (and does) verify for consistency during the window. The anchor fixes exactly these leaves. To induce split-brain after τQ , the adversary must present, for some i in a qualified subset, a value yi′ ̸= yi⋆ that passes both checks. The consistency check is now trivially satisfiable: knowing x, set Ri′ = (logg Pi − yi′ )/x. The inclusion check, however, requires a salt s′i with H(i∥yi′ ∥s′i ) = ℓ⋆i (leaf-set case) or a path yielding the fixed Root (Merkle case). The former is a second preimage on H; the latter additionally requires either a second preimage or an internal Merkle collision. Both are infeasible at ≈ 2N/2 . The remaining avenue, namely replacing the anchor itself, requires rewriting finalized ledger history, excluded by Assumption III.2. Hence every share that passes both checks equals yi⋆ , and reconstruction yields s⋆ . Proposition VI.2 (No secret recovery). Even after τQ , an adversary controlling < t shares learns nothing about s⋆ from C and the anchor beyond negligible advantage; in particular Shor does not recover s⋆ .
TABLE I Feature Binding basis Binding type Timing assumption Ledger assumption Hiding Verification cost Communication Implementation risk
PiB (proposed)
Lattice-based VSS
2nd-preimage res. + immutable ledger Preserved from pre-quantum window Required (commit before τQ ) Required (PQ-finalized anchor) Perfect (Pedersen); anchor statistical O(t) modular exponentiations Small integers + Merkle path Low (standard libraries)
SIS/LWE (believed PQ-hard) Native post-quantum None None Scheme-dependent Matrix ops + lattice ZK Large keys/ciphertexts High (side channels, complex ZK)
Proof sketch. From C0 = g s hr0 and x = logg h, the adversary obtains only logg C0 = s + xr0 : one linear equation in the two unknowns s, r0 , satisfied by every candidate secret. This is Pedersen’s perfect hiding, which Shor does not affect. The anchor is handled in Proposition VI.3. B. Retained secrecy despite public hashing The naive scheme (hashing raw shares) breaks threshold secrecy: any party can confirm a guessed share by a single hash evaluation, collapsing Shamir’s perfect secrecy at the threshold boundary to a checkable computation. Salting repairs this. Proposition VI.3 (Threshold secrecy). Model H as a random oracle. If each salt si is uniform on {0, 1}κ and known only to the dealer and party i, any coalition T with |T | < t (given C, the anchor, all authentication paths it legitimately holds, and its own shares, randomizers, and salts) has advantage at most O(q 2−κ ) in determining s⋆ , where q is its number of oracle queries. This holds against a post-τQ adversary. Proof sketch. Consider any i ∈ / T . The coalition’s view of ℓi = H(i∥yi ∥si ) is, in the random-oracle model, independent of yi unless the coalition queries the oracle at the exact point i∥yi ∥si ; lacking si (uniform, secret), each guess of yi succeeds with probability 2−κ per query, giving the stated O(q 2−κ ) bound. Shor does not help: post-τQ the adversary learns logg Pi = yi + xRi , one equation in two unknowns per missing share, so the {yi }i∈T retain a free coordinate exactly / as in plain Shamir. The Pedersen commitments contribute nothing further, being perfectly hiding. Hence the missing shares are statistically undetermined and s⋆ is hidden up to the salt-guessing term. Choosing κ ≥ 2N keeps this negligible even against Grover.1 C. Ledger immutability and the transition assumption Assumption III.2 is where PiB’s binding ultimately rests, and it is a systems assumption, not an algebraic one. A ledger authenticated only by classical signatures is itself Shor-breakable; PiB therefore requires that the chosen ledger migrate to post-quantum consensus and signatures, and that any relied-upon anchor be buried under post-quantum-finalized depth, before τQ . Grover’s quadratic speedup on Proof-ofWork for chain re-organization is a constant-factor security 1 Secrecy is thus statistical, not perfect: the published leaf hashes admit a vanishing salt-guessing advantage. This is the price of a public, non-interactive anchor and is made negligible by the salt length.
erosion that must be absorbed by finalization depth or by postquantum finality gadgets. We regard the timely execution of this migration (already underway in standardization [9]) as the principal external dependency of the scheme, and note that a dealing loses no secrecy if the assumption fails, only the binding. Proposition VI.4 (Scope of the guarantee). PiB does not bind a dealer who is already quantum-capable at commit time. Such a dealer can, at τ0 ≥ τQ , anchor a set of mutually inconsistent shares that nonetheless pass every individual Pedersen check (choosing each Ri to fit), baking split-brain into the frozen set. Assumption III.1 excludes this case by fiat, and it is the realistic case: the concern motivating post-quantum migration is that present honest dealings will face a future CRQC. D. Comparison with lattice-based VSS Table I contrasts PiB with a post-quantum cryptographic lattice-based approach. Neither is unconditional: lattice VSS rests on SIS/LWE (believed quantum-hard), PiB on secondpreimage resistance plus a timing-and-immutability deployment assumption. VII. I MPLEMENTATION C ONSIDERATIONS Hash size. Binding rests on second-preimage resistance; against Grover this is ≈ 2N/2 , so N ≥ 256 (e.g. SHA3256) gives 128-bit security, and SHA3-512 a margin. We do not rely on collision resistance, whose quantum bound (BHT, ≈ 2N/3 ) would be weaker. • Salt length. Per Proposition VI.3, choose κ ≥ 2N so the salt-guessing advantage is negligible even under Grover; salts are distributed privately with shares and never published. • Ledger selection and timing. Select a chain with a credible post-quantum consensus roadmap and anchor batches early, leaving ample finalized depth before τQ (Assumption III.2). • Batch scale. For a reserve of M sharings over n parties, a single Merkle root per sharing (or one aggregate root over all batches) keeps on-ledger footprint small; inclusion proofs are O(log n).
•
VIII. L IMITATIONS The scheme’s guarantees are conditional and we restate the conditions plainly. (i) Preserved binding requires the commitment to predate τQ (Assumption III.1); it says nothing
about dealings first anchored in the quantum era. (ii) Binding rests on the ledger genuinely finalizing history under postquantum consensus before τQ (Assumption III.2); this is a deployment and governance dependency outside the cryptography. (iii) Anchor-induced secrecy is statistical, not perfect, made negligible by salt length. (iv) PiB provides no defense against a dealer who is quantum-capable at commit time (Proposition VI.4); protecting against such a dealer requires a commitment whose binding is itself post-quantum, at which point the Pedersen layer becomes redundant. Within these bounds, PiB is best understood as long-term, publicly verifiable notarization that carries a classically established VSS binding safely across the quantum horizon. IX. C ONCLUSION Post-quantum failure of Pedersen VSS affects binding, not hiding: Shor enables equivocation but does not reveal the secret. PiB secures binding at the time of dealing and preserves it by anchoring a salted, index-bound hash to an immutable, transitioning ledger, while retaining Pedersen’s pre-quantum zeroknowledge verification. The result is a commit-now, reveallater approach that protects today’s honest dealings against future quantum adversaries using only classical primitives. Rather than replacing lattice-based cryptography, PiB provides a practical and auditable option for long-term verifiable secret sharing. For any questions about licensing of this technology [10], please contact the organization of the authors. R EFERENCES [1] P. Feldman, “A practical scheme for non-interactive verifiable secret sharing,” in 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), 1987, pp. 427–438. [2] T. P. Pedersen, “Non-interactive and information-theoretic secure verifiable secret sharing,” in Advances in Cryptology — CRYPTO ’91, J. Feigenbaum, Ed. Springer Berlin Heidelberg, 1992, pp. 129–140. [3] P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124–134. [4] M. Stadler, “Publicly verifiable secret sharing,” in Advances in Cryptology — EUROCRYPT ’96, U. Maurer, Ed. Springer Berlin Heidelberg, 1996, pp. 190–199. [5] B. Schoenmakers, “A simple publicly verifiable secret sharing scheme and its application to electronic voting,” in Advances in Cryptology — CRYPTO’ 99, M. Wiener, Ed. Springer Berlin Heidelberg, 1999, pp. 148–164. [6] S. Haber and W. S. Stornetta, “How to time-stamp a digital document,” Journal of Cryptology, vol. 3, no. 2, pp. 99–111, 1991. [7] M. Ajtai, “Generating hard instances of lattice problems,” in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC ’96). Association for Computing Machinery, 1996, pp. 99–108. [8] G. Brassard, P. Høyer, and A. Tapp, “Quantum cryptanalysis of hash and claw-free functions,” in LATIN’98: Theoretical Informatics, C. L. Lucchesi and A. V. Moura, Eds. Springer Berlin Heidelberg, 1998, pp. 163–169. [9] National Institute of Standards and Technology, “Status report on the fourth round of the NIST post-quantum cryptography standardization process,” 2025. [10] M. Jakobsson and K. Finlow-Bates, “Proofs In a Bottle and QuantumSecure Threshold Sharing,” Patent application, 2026.