Tamper-proofing log files Problem Overview

I want to securely store log files so the contents are secret, and they can't be modified without detection.

The files will be encrypted using authenticated encryption (AES in GCM mode), with a random IV and symmetric key for each file. The symmetric key will be encrypted using the public part of an RSA key pair. Both the IV and encrypred symmetric key will be included in the additional authenticated data.

This gives me confidentiality, integrity and authenticity - but only for each individual log file.

For example, let's say I have log files 2013-01-01.log, 2013-01-05.log and 2013-02-09.log - an attacker could delete 2013-01-05.log without detection.

I've come up with 2 possible solutions.

Possible Solution 1

The program could maintain an encrypted (and possible RSA-signed) 'counter file', which would contain a sequence number that would be incremented every time we write a new log file. The sequence number would become part of the log filename, and would also be included in the additional authenticated data. We could therefore detect any 'gaps' from missing files.

Possible Solution 2

The program could maintain an encrypted (and possible RSA-signed) 'database file', which would contain the filenames of all previously written log files. We could therefore detect any 'gaps' from missing files.

The Question

I'd like feedback on my 2 possible solutions - do they work, do they need some changed, have I missed anything?

Or are there better solutions to my problem?
"Efﬁcient, Compromise Resilient and Append-only

Cryptographic Schemes for Secure Audit Logging" ​ (PDF)

gives a publicly verifiable approach that allows fine-grained verification,

but it is in the Random Oracle Model.

The Simple Method:

The verifier and logger start with a seed for a

forward-secure pseudo-random number generator.

To denote a valid ending of a log, put the string of

the next $b$ bits of the PRNG's output into the log.

To add a log entry, get the next $\:b+k\:$ bits of the PRNG's output,

put into the log the encryption of the log entry and the mac of that

ciphertext using the last $k$ of the $\:b+k\:$ bits of PRNG output as the

mac key, then erase those $\:b+k\:$ bits and the previous PRNG state.