International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Space-Deniable Proofs

Authors:
Jesko Dujmovic , Helmholtz Center for Information Security and Saarland University
Christoph U. Günther , Institute of Science and Technology Austria
Krzysztof Pietrzak , Institute of Science and Technology Austria
Download:
Search ePrint
Search Google
Conference: TCC 2025
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.
BibTeX
@inproceedings{tcc-2025-36256,
  title={Space-Deniable Proofs},
  publisher={Springer-Verlag},
  author={Jesko Dujmovic and Christoph U. Günther and Krzysztof Pietrzak},
  year=2025
}