We propose a new cryptographic primitive, a *seekable sequential key generator* (SSKG), that combines these two properties and has direct application in secure logging. We rigorously formalize the required security properties and give a provably-secure construction based on the integer factorization problem. We further optimize the scheme in various ways, preparing it for real-world deployment. As a byproduct, we develop the notion of a *shortcut one-way permutation* (SCP), which might be of independent interest.
Our work is highly relevant in practice. Indeed, our SSKG implementation has become part of the logging service of the systemd system manager, a core component of many modern commercial Linux-based operating systems.
Category / Keywords: secret-key cryptography / secure logging, forward security, seekability, shortcut permutation Publication Info: A preliminary version of this paper appears in the proceedings of ESORICS 2013. This is the full version. Date: received 17 Jun 2013 Contact author: bertram poettering at rhul ac uk Available format(s): PDF | BibTeX Citation Version: 20130618:091941 (All versions of this report) Discussion forum: Show discussion | Start new discussion