(2026-04) SPoCK; Sequential Proofs of Complete Knowledge
2026-04-15
A proof of knowledge certifies that the prover “knows” a secret. This property is established by the existence of an extractor that, given access to the prover, can extract the secret. Unfortunately, this does not imply that a single entity has access to the secret in the clear, as it may be secret-shared among several parties and the proof computed using multiparty computation (MPC), or the secret may be embedded in a trusted execution environment (TEE) that only allows limited access to it.
Often, the ability to encumber a secret in this way breaks the security of a system; vote selling in e-voting schemes is one example. To address this, two recent papers introduced the notions of “Proofs of Complete Knowledge” (PoCK) [Kelkar et al., CCS’24] and “Individual Cryptography” [Dziembowski et al., CRYPTO’23]. While the goals and constructions in those works differ, both rely on the same key idea to prevent encumbrance. To compute a proof, the prover must evaluate a hash function on a huge number of inputs. One then assumes that only a fraction of those can be encumbered, while for the rest the prover must know the inputs in the clear, and these clear inputs are sufficient to extract the secret. Computing a huge number of hashes is a challenge even for an honest prover (who has the secret in the clear), so those works suggest using outdated Bitcoin mining hardware to make the scheme practical.
By forcing the prover to evaluate the hashes in a sequential manner, we could get meaningful security against encumbrance with far fewer hashes, especially against MPC, where round complexity is a major bottleneck.
As a concrete instantiation of this idea, we define and construct Sequential Proofs of Complete Knowledge (SPoCK). Our construction uses the PoCK of Kelkar et al. (which are based on Fischlin’s straight-line extractable proofs of knowledge). The computation of this PoCK is then embedded into the computation of the Proof of Sequential Work from [Cohen&Pietrzak, EUROCRYPT’18]. SPoCK thus have the potential to enable complete-knowledge or individual-cryptography primitives where honest parties can use standard hardware. We also propose a variant of this scheme that requires a large amount of memory throughout the evaluation, providing better security also against TEEs.