Paper 2025/1723

Space-Deniable Proofs

Christoph U. Günther, Institute of Science and Technology Austria

Krzysztof Pietrzak, Institute of Science and Technology Austria

Abstract

We introduce and construct a new proof system called Non-interactive Arguments of Knowledge or Space (NArKoS), where a space bounded prover can convince a verifier they know a secret, while having access to sufficient space allows one to forge indistinguishable proofs without the secret. An application of NArKoS are space-deniable proofs, which are proofs of knowledge (say for authentication in access control) that are sound when executed by a lightweight device like a smart-card or an RFID chip that cannot have much storage, but are deniable (in the strong sense of online deniability) as the verifier, like a card reader, can efficiently forge such proofs. We construct NArKoS in the random oracle model using an OR-proof combining a sigma protocol (for the proof of knowledge of the secret) with a new proof system called simulatable Proof of Transient Space (simPoTS). We give two different constructions of simPoTS, one based on labelling graphs with high pebbling complexity, a technique used in the construction of memory-hard functions and proofs of space, and a more practical construction based on the verifiable space-hard functions from TCC'24 where a prover must compute a root of a sparse polynomial. In both cases, the main challenge is making the proofs efficiently simulatable.

Note: Added a subexponential attack (due to Salil Vadhan) against the assumption underlying our second construction.

@misc{cryptoeprint:2025/1723,
      author = {Jesko Dujmovic and Christoph U. Günther and Krzysztof Pietrzak},
      title = {Space-Deniable Proofs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1723},
      year = {2025},
      doi = {10.1007/978-3-032-12290-2_6},
      url = {https://eprint.iacr.org/2025/1723}
}