Lattice-Based DAPS and Generalizations: Self-enforcement in Signature Schemes

Authors: D. Boneh, S. Kim, and V. Nikolaenko

Double authentication preventing signatures (DAPS) is a mechanism, due to Poettering and Stebila, for protecting certificate authorities (CAs) from coercion. We construct the first lattice-based DAPS signatures, thereby providing the first post-quantum DAPS system. We go further and generalize DAPS to a more general mechanism we call predicate authentication preventing signatures (PAPS). Here, for a given k-ary predicate φ, a PAPS system for φ is regular signature scheme. However, if the signer ever signs k messages m1, …, mk such that φ(m1, … , mk) is true then these k signatures reveal the signer’s secret key. This self-enforcement mechanism incentivizes the signer to never sign conflicting messages, namely messages that satisfy the predicate φ. The k conflicting messages can be signed at different times and the signatures may be generated independently of one another. We further generalize to the case when the signatures are generated by multiple signers. We motivate these primitives, give precise definitions, and provide several constructions. These primitives are challenging to construct and give rise to many new elegant open research questions.

In proceedings of ACNS 2017, pp. 457-477.

Full paper: pdf