# Tamper-evident audit logs

I want to be able to detect tampering in a log file that is under the control of an untrusted party. I am not interested in secrecy, only the integrity of the contents in the file - so I want to detect if entries have been removed/changed. The solution that I seem to have found from a short google search is to use hash chains linking the current log entry to all other previous entries. The untrusted party publishes the hashes with some acceptable frequency such that any tampering after the time of publishing can be detected. Is there any technique that will accomplish something similar without the need for publishing the hashes frequently?

-
Where do the logs come from in the first place? Are you are sending them to an untrusted server from a trusted one, or do they originate in an untrusted location? –  figlesquidge Nov 26 '13 at 16:16

To denote a valid ending of a log, append the string of the next $b$ bits of the PRNG's output
to the end of the log. $\;\;$ To add a log entry, get the next $\:b\hspace{-0.03 in}+\hspace{-0.03 in}k\:$ bits of the PRNG's output,
use the last $k$ of those bits to mac the new content, append the concatenation of the new
content with its mac to the log, and then erase those $\:b\hspace{-0.03 in}+\hspace{-0.03 in}k\:$ bits and the previous PRNG state.