Audit logs, providing information about the current and past states of systems, are one of the most important parts of modem computer systems. Providing security for audit logs on an untrusted machine in a large distributed system is a challenging task, especially in the presence of active adversaries. In such a system, it is critical to have forward security such that when an adversary compromises a machine, she cannot modify or forge the log entries accumulated before the compromise. Unfortunately, existing secure audit logging schemes have significant limitations that make them impractical for real-life applications: Existing Public Key Cryptography (PKC) based schemes are computationally expensive for logging in task intensive or resource-constrained systems, while existing symmetric schemes are not publicly verifiable and incur significant storage and communication overheads. In this paper, we propose a novel forward secure and aggregate logging scheme called Blind-Aggregate-Forward (BAF) logging scheme, which is suitable for large distributed systems. BAF can produce publicly verifiable forward secure and aggregate signatures with near-zero computational, storage, and communication costs for the loggers, without requiring any online Trusted Third Party (TTP) support. We prove that BAF is secure under appropriate computational assumptions, and demonstrate that BAF is significantly more efficient and scalable than the previous schemes. Therefore, BAF is an ideal solution for secure logging in both task intensive and resource-constrained systems.
