Incremental Time-Deniable Signatures

Digital signatures guarantee long-term public verifiability and non-repudiation. However, in some applications, signatures can be stored by several actors and, later on (e.g., if leaked after an attack), those signatures could be adversarially used, beyond their original purposes. In particular, such risks are possible in scenarios (e.g., DKIM) where short-lived authentication (in contrast to long-term public verifiability) suffices and the use of digital signatures is an overkill exposing vulnerabilities due to deniability issues. Motivated by the above problem, a very recent work of Beck et al. (PETS 2023, IACR eprint 2022/1018) formally defines and constructs Time-Deniable Signatures, illustrating their benefits (among them, the major feature of non-requiring special external infrastructures) compared to prior formulations such as Epochal Signatures (S&P 2021), Forward-Forgeable Signatures (Usenix 2021) and Short-Lived Signatures (Asiacrypt 2022). Their construction requires an HIBE scheme that satisfies a special key-indistinguishability property and in the conclusions of their work they explicitly mention as an open problem for future work the important direction of obtaining non-HIBE based time-deniable signatures. In this work, as the main contribution, we show a construction of a Time-Deniable Signature that is conceptually simpler and concretely more efficient than the one presented by Beck et al. Our construction achieves perfect deniability and moreover does not require Hierarchical Identity-Based Encryption (HIBE), therefore solving the above open problem. The main idea behind our design, compared to the work of Beck et al., consists of exploiting the fact that in concrete scenarios even though the space of possible timestamps is not a-priori bounded, it is still relatively small and its size slowly increases over time. We will therefore relax the definition of Beck et al. to leverage the constraints on the size of the timestamp space, and we name the resulting primitive “Incremental” Time-Deniable Signature scheme.